Computer Science Colloquium, 2007-2008

Liad Blumrosen
Microsoft
December 19, 2007

Title: Can simple markets achieve good results?

Abstract:
evenue from electronic commerce and Internet-based advertising has been growing exponentially in the last decade, hand in hand with the birth of large-scale marketplaces (e.g., eBay and Amazon), information providers ( e.g., Google and Yahoo) and web-based social networks (e.g., MySpace and Facebook). Participants in such systems have access to information that is known only to them (like how much buyers are willing to pay for commodities), and economic mechanisms are designed to gather sufficient information for computing the desired outcomes. Complex communication protocols are often required in order to achieve good results, whereas practical and behavioral reasons encourage the use of simple communication exchanges.

This talk will survey several results characterizing tradeoffs between the simplicity of markets and their achievable economic properties. On the positive side, nearly optimal markets exist even when the agents have restricted expressive power. On the negative side, we show that the communication overhead of computing equilibrium-supporting prices may be significant. Finally, we show that simple pricing schemes cannot support close-to-optimal results in ascending-price multi-unit auctions.

Based on joint works with Moshe Babaioff, Michal Feldman, Moni Naor, Noam Nisan, Michael Schapira and Ilya Segal.

 


Benny Pinkas