License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07271.16
URN: urn:nbn:de:0030-drops-11608
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1160/
Go to the corresponding Portal

Moulin, Hervé

Strategy-proof assignment with a vanishing budget surplus

pdf-format:
07271.MoulinHerve.ExtAbstract.1160.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{moulin:DagSemProc.07271.16,
  author =	{Moulin, Herv\'{e}},
  title =	{{Strategy-proof assignment with a vanishing budget surplus}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1160},
  URN =		{urn:nbn:de:0030-drops-11608},
  doi =		{10.4230/DagSemProc.07271.16},
  annote =	{Keywords: VCG mechanisms, assignment, asymptotic budget balance, worst case analysis}
}

Keywords: VCG mechanisms, assignment, asymptotic budget balance, worst case analysis
Collection: 07271 - Computational Social Systems and the Internet
Issue Date: 2007
Date of publication: 02.10.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI