%A M Guo
%A Victor Naroditskiy
%A V Conitzer
%A Amy Greenwald
%A Nicholas R Jennings
%J Proc. of the 7th Workshop on Internet and Network Economics
%T Budget-Balanced and Nearly Efficient Randomized
Mechanisms: Public Goods and Beyond
%X Many scenarios where participants hold private information
require payments to encourage truthful revelation. Some of these scenarios have
no natural residual claimant who would absorb the budget surplus or cover
the deficit. Faltings proposed the idea of excluding one
agent uniformly at random and making him the residual claimant. Based on this
idea, we propose two classes of public good mechanisms and derive optimal ones
within each class: Faltings' mechanism is optimal in one of the classes. We
then move on to general mechanism design settings, where we prove guarantees on
the social welfare achieved by Faltings' mechanism. Finally, we analyze a
modification of the mechanism where budget balance is achieved without
designating any agent as the residual claimant.
%D 2011
%L orchid15