DagSemProc.07271.16.pdf
- Filesize: 187 kB
- 12 pages
Document
Strategy-proof assignment with a vanishing budget surplus
Author
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7271
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-10-02
Cite As Get BibTex
Hervé Moulin. Strategy-proof assignment with a vanishing budget surplus. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07271.16
Abstract
A VCG mechanism to assign p identical objects is feasible is cash transfers yield no deficit. The efficiency loss of such a mechanism is the worst ratio of budget surplus to efficient surplus. We compute the optimal efficiency loss for all n and p, when we also require Voluntary Participation as well as when we do not. Without the VP requirement, the optimal efficiency loss converges to zero uniformly in p, and exponentially fast if p is fixed. With the VP requirement asymptotic budget balance is only true is p is not larger than n/2.
Subject Classification
Keywords
- VCG mechanisms
- assignment
- asymptotic budget balance
- worst case analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads