Invited Talk: Noam Nisan

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

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.