Why would an electronic commerce conference want me, a complexity theorist, as a PC member? Electronic commerce has many surprising connections to computational complexity. Consider complex auction situations where different buyers wish to purchase different items with varying needs for combinations of these auctions. One needs to design such auctions which decisions made by the buyers, as well as determining the winner must be computationally efficient. This in addition to the usual needs of auctions to be revenue generating, robust against players trying to cheat the system and other notions of "fairness."
In a more philosophical sense, what is a large financial market but some sort of massive parallel computation device that takes pieces of information and produces prices for securities. How can we model and analyze this process? Computational complexity should play a major role in understanding this model of computing and allow us to develop more efficient financial markets.
Post a Comment