title: Budget-Balanced and Nearly Efficient Randomized  Mechanisms: Public Goods and Beyond
creator: Guo, M
creator: Naroditskiy, Victor
creator: Conitzer, V
creator: Greenwald, Amy
creator: Jennings, Nicholas R
subject: Mechanism Design
subject: Incentive Engineering
description: 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.
date: 2011-12
type: Article
type: PeerReviewed
format: application/pdf
identifier: http://www.orchid.ac.uk/eprints/15/1/paper_73.pdf
identifier:   Guo, M and Naroditskiy, Victor and Conitzer, V and Greenwald, Amy and Jennings, Nicholas R  (2011) Budget-Balanced and Nearly Efficient Randomized Mechanisms: Public Goods and Beyond.  Proc. of the 7th Workshop on Internet and Network Economics.      (In Press)  
relation: http://www.orchid.ac.uk/eprints/15/