1st International Workshop on Computational Social Choice
Amsterdam, 6-8 December 2006
Invited Talk: Noam Nisan
Approximation Mechanisms and Characterization of Implementable Social Choice Rules
The emerging field of Algorithmic Mechanism Design studies strategic implementations of social-choice functions that arise in computational settings -- most importantly, various resource allocation rules. The clash between computational constraints and incentive constraints is at the heart of this field. This happens whenever one wishes to implement a computationally-hard social choice function (e.g. an allocation rule). In such cases, approximations or heuristics are computationally required, but it is not at all clear whether these can be strategically implemented.
This talk will demonstrate many of the issues involved by looking in depth at a representative problem: multi-unit auctions.
The talk will have the flavor of a survey and is based on my previous joint work with Amir Ronen, Ilya Segal, Ahuva Mu'alem, Ron Lavi, and Shahar Dobzinski.