Almost budget-balanced VCG mechanisms to assign multiple objects

• 成果类型: Article
• 署名作者: Moulin, Herve
• 署名单位: Rice University
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2008.03.003
• 发表日期: 2009
• 页码: 96-119
• 关键词: VCG mechanisms; Worst case analysis; Budget surplus or deficit; Asymptotic budget-balance

摘要

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 (L) over cap (n, p) satisfies (L) over cap (n, p) <= (L) over cap (n, left perpendicular/2right perpendicular) <= 4/3 root n. If p/n is bounded away from 1/2, (L) over cap (n, p) converges to zero exponentially in n. Participation is voluntary in the optimal mechanism achieving (L) over cap (n, p) if p = 1, but not if p >= 2. Among voluntary mechanisms, the optimal efficiency loss is not significantly larger than (L) over cap (n, p) if p/n <= 1/2. But it does not converge to zero in n if p/n > 1/2. (C) Elsevier Inc. All rights reserved.