Large 00012

Query Complexity and Computational Complexity of Combinatorial Auctions

Jan Vondrak

Recorded 12 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


The problem of combinatorial auctions is one of the basic questions in algorithmic mechanism design: how can we allocate m items to n agents with private valuations of different combinations of items, so that the agents are motivated to reveal their true valuations and the outcome is (approximately) optimal in terms of social welfare? While approximation algorithms exist for several non-trivial classes of valuations, they typically do not motivate agents to report truthfully. The classical VCG mechanism, although truthful, is not computationally efficient. Thus the main question is whether the requirements of truthfulness and computational efficiency can be combined, or whether they are incompatible.

Until recently, it was not known whether there is any gap between the power of truthful and non-truthful mechanisms for combinatorial auctions. Recent progress led to the first such separation (by Dobzinski). The initial hardness results were valid only for deterministic mechanisms in the value oracle model. More recently, they have been extended to randomized mechanisms, and also to computational hardness for succinctly represented valuations. I will discuss these developments and some remaining open questions.

Watched 1017 times.