1st International Workshop on Computational Social Choice
Amsterdam, 6-8 December 2006

Invited Talk: Noam Nisan

  Noam Nisan
School of Computer Science and Engineering
The Hebrew University of Jerusalem

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.