APPROXIMATION MECHANISMS AND CHARACTERIZATION OF IMPLEMENTABLE SOCIAL CHOICE RULES

Abstract: 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.

Location: 
Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus
Dates: 
Sunday, January 14, 2007 - 16:15 to 18:15
Old Lecturers: 
NOAM NISAN
Old Lecturers University: 
THE HEBREW UNIVERSITY