Budget-Balanced and Nearly Efficient Randomized Mechanisms: Public Goods and Beyond
OA Location
Author(s)
Guo, M
Naroditskiy, V
Conitzer, V
Greenwald, A
Jennings, NR
Type
Conference Paper
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 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 Issued
2011-12-11
Date Acceptance
2011-12-11
Citation
Lecture Notes in Computer Science, 2011, 7090, pp.158-169
ISBN
978-3-642-25509-0
Publisher
Springer Berlin Heidelberg
Start Page
158
End Page
169
Journal / Book Title
Lecture Notes in Computer Science
Volume
7090
Copyright Statement
© Springer Verlag 2011. The final publication is available at Springer viahttp://dx.doi.org/10.1007/978-3-642-25510-6_14
Identifier
http://eprints.soton.ac.uk/272897/
Source
7th Workshop on Internet and Network Economics
Subjects
Artificial Intelligence & Image Processing
08 Information And Computing Sciences
Publication Status
Published
Start Date
2011-12-11
Finish Date
2011-12-14
Coverage Spatial
Singapore