DROPS

Document

Efficient cost sharing with a cheap residual claimant

Authors: Hervé Moulin

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract

For the cooperative production problem where the commons is a one dimensional convex cost function, I propose the residual mechanism to implement the efficient production level . In contrast to the familiar cost sharing methods such as serial, average and incremental, the residual mechanism may subsidize an agent with a null demand. IFor a large class of smooth cost functions, the residual mechanism generates a budget surplus that is, even in the worst case, vanishes as 1/logn where n is the number of participants. Compare with the serial, average and incremental mechanisms, of which the budget surplus, in the worst case, converges to the efficient surplus as n grows. The second problem is the assignment among n agents of p identical objects and cash transfers to compensate the losers. We assume p<n, and compute the optimal competitive performance among all VCG mechanisms generating no budget deficit. It goes to zero exponentially fast in n if the number of objects is fixed; and as (n)^(1/2) uniformly in p. The mechanism generates envy, and net utilities are not co-monotonic to valuations. When p>n/2, it may even fail to achieve voluntary participation.

Cite as

Hervé Moulin. Efficient cost sharing with a cheap residual claimant. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{moulin:DagSemProc.07261.7,
  author =	{Moulin, Herv\'{e}},
  title =	{{Efficient cost sharing with a cheap residual claimant}},
  booktitle =	{Fair Division},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.7},
  URN =		{urn:nbn:de:0030-drops-12312},
  doi =		{10.4230/DagSemProc.07261.7},
  annote =	{Keywords: Assignment, cost sharing, Vickrey-Clarke-Groves mechanisms, competitive analysis}
}

Document

DOI: 10.4230/DagSemProc.07271.16

Strategy-proof assignment with a vanishing budget surplus

Authors: Hervé Moulin

Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)

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.

Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07271.16},
  URN =		{urn:nbn:de:0030-drops-11608},
  doi =		{10.4230/DagSemProc.07271.16},
  annote =	{Keywords: VCG mechanisms, assignment, asymptotic budget balance, worst case analysis}
}

Search Results

Documents authored by Moulin, Hervé

Efficient cost sharing with a cheap residual claimant

Abstract

Cite as

Strategy-proof assignment with a vanishing budget surplus

Abstract

Cite as

Thanks for your feedback!

Could not send message