Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Budget-balanced and nearly efficient randomized mechanisms: public goods and beyond
Author: Guo, M.
Naroditskiy, V.
Conitzer, V.
Greenwald, A.
Jennings, N.
Citation: Internet and Network Economics: Proceedings of 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011, 2011 / Chen, N., Elkind, E., Koutsoupias, E. (ed./s), pp.158-169
Publisher: Springer
Publisher Place: UK
Issue Date: 2011
ISBN: 9783642255090
ISSN: 0302-9743
Conference Name: International Workshop on Internet and Network Economics (WINE) (11 Dec 2011 - 14 Dec 2011 : Singapore)
Statement of
Mingyu Guo, Victor Naroditskiy, Vincent Conitzer, Amy Greenwald, and Nicholas R. Jennings
Abstract: 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 [7] 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.
Rights: © Springer-Verlag Berlin Heidelberg 2011
RMID: 0020135602
DOI: 10.1007/978-3-642-25510-6_14
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_88030.pdfRestricted Access245.06 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.