13 September 2007, Computational Social Choice Seminar, Krzysztof Apt

Abstract

This talk will deal with the problem of mechanism design for public project problems.

It is well-known that for several natural decision problems no budget balanced Groves mechanisms exist. This motivated recent research in designing variants of feasible Groves mechanisms (termed as `redistribution of VCG (Vickrey-Clarke-Groves) payments') that generate reduced deficit.

We first show that, in contrast to the case of the auction mechanisms considered in [Cavallo '06] and [Guo and Conitzer '07], for the public project problems no feasible Groves mechanism can reduce the deficit inherently present in VCG mechanism.

This brings us to a study of sequential Groves mechanisms. We show that then other dominant strategies than truth-telling may exist and that in the case public project problems they can be used to reduce deficit.

The talk will be self-contained and all the relevant notions will be introduced and motivated. Based on a joint work with Arantza Estévez-Fernández.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle at illc.uva.nl).