2 Search Results for "Moulin, Herv�"

Document
DOI: 10.4230/DagSemProc.07261.7
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-dev.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-dev.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}
}
  • Refine by Author
  • 2 Moulin, Hervé

  • Refine by Classification

  • Refine by Keyword
  • 1 Assignment
  • 1 VCG mechanisms
  • 1 Vickrey-Clarke-Groves mechanisms
  • 1 assignment
  • 1 asymptotic budget balance
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 2 2007

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact