Almost budget-balanced VCG mechanisms to assign multiple objects

Herve Moulin

Journal of Economic Theory, 2009, vol. 144, issue 1, 96-119

Abstract: Subsidy-free VCG mechanisms assign p identical objects to n agents. The efficiency loss is the largest ratio of budget surplus to efficient surplus, over all profiles of non-negative valuations. The smallest efficiency loss satisfies . If is bounded away from , converges to zero exponentially in n. Participation is voluntary in the optimal mechanism achieving if p=1, but not if p[greater-or-equal, slanted]2. Among voluntary mechanisms, the optimal efficiency loss is not significantly larger than if . But it does not converge to zero in n if .

Keywords: VCG; mechanisms; Worst; case; analysis; Budget; surplus; or; deficit; Asymptotic; budget-balance (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (48)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0022-0531(08)00062-8
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jetheo:v:144:y:2009:i:1:p:96-119

Access Statistics for this article

Journal of Economic Theory is currently edited by A. Lizzeri and K. Shell

More articles in Journal of Economic Theory from Elsevier
Bibliographic data for series maintained by Catherine Liu ().