|
Abstract |
We study the necessity of interaction between individuals for obtaining approximately efficient allocation of resources. Starting with Hayek's classical work, the role of interaction and communication in markets has received significant attention in economic thinking. We consider this issue in the framework of simultaneous communication complexity. We analyze the amount of communication required for achieving an approximately efficient allocation in two different settings: multi-item auctions with unit demand bidders (bipartite matching) and combinatorial auctions with sub-additive bidders. For both settings we show that non-interactive systems have enormous communication costs relative to interactive ones. On the other hand, we show that quite limited interaction already suffices.
Joint work with ShaharDobzinski and Sigal Oren. |
|
Affiliation |
Noam Nisan won an ACM Distinguished Dissertation Award for his Ph.D. thesis, on pseudorandomnumber generators. Noam Nisan won the Michael Bruno Memorial Award in 2004. In 2012 Noam Nisan won the Gödel Prize, shared with five other recipients, for his work with Amir Ronen in which he coinedthe phrase "algorithmic mechanism design" and presented many applications of this type of problem within computer science. |
