Abstract:

Revenue 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.