13 September 2007, Computational Social Choice Seminar, Krzysztof Apt
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.