When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07261.7
URN: urn:nbn:de:0030-drops-12312
Go to the corresponding Portal

Moulin, Hervé

Efficient cost sharing with a cheap residual claimant

07261.MoulinHerve.ExtAbstract.1231.pdf (0.1 MB)


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.

BibTeX - Entry

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-12312},
  doi =		{10.4230/DagSemProc.07261.7},
  annote =	{Keywords: Assignment, cost sharing, Vickrey-Clarke-Groves mechanisms, competitive analysis}

Keywords: Assignment, cost sharing, Vickrey-Clarke-Groves mechanisms, competitive analysis
Collection: 07261 - Fair Division
Issue Date: 2007
Date of publication: 26.11.2007

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