Zero entry barriers in an NP-complete world: Transaction streams and the complexity of electronic commerce

The adoption of electronic markets in an industry has a disintermediation potential because it can create a direct link between the producer and the consumer (without the need for the intermediation role of distributors). Electronic markets lower the search cost, allowing customers to choose among more providers (which ultimately reduces both the costs for the customer and the profits for the producer). Electronic markets on the Internet have the opposite effect: they lower some entry barriers and result in more intermediators (e.g. there are over three hundred thousand bookstores on the Internet). Transaction streams model how transactions on the Internet are being conducted and help explain the types of new intermediators that are appearing on the Internet. We present a computational model of transaction streams and prove that in transaction stream based electronic markets, searching for the best price is NP-complete. Implications of the findings presented and challenges for the further development of electronic commerce are also discussed.