Moulin, Hervé
Efficient cost sharing with a cheap residual claimant
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 comonotonic to valuations. When p>n/2, it may even fail to achieve voluntary participation.
BibTeX  Entry
@InProceedings{moulin:DSP:2007:1231,
author = {Herv{\'e} Moulin},
title = {Efficient cost sharing with a cheap residual claimant},
booktitle = {Fair Division},
year = {2007},
editor = {Steven Brams and Kirk Pruhs and Gerhard Woeginger},
number = {07261},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1231},
annote = {Keywords: Assignment, cost sharing, VickreyClarkeGroves mechanisms, competitive analysis}
}
Keywords: 

Assignment, cost sharing, VickreyClarkeGroves mechanisms, competitive analysis 
Seminar: 

07261  Fair Division

Issue date: 

2007 
Date of publication: 

26.11.2007 