3 Search Results for "Moulin, Hervé"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.28
New Characterizations of Core Imputations of Matching and b-Matching Games

Authors: Vijay V. Vazirani

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We give new characterizations of core imputations for the following games: 1) The assignment game. 2) Concurrent games, i.e., general graph matching games having non-empty core. 3) The unconstrained bipartite b-matching game (edges can be matched multiple times). 4) The constrained bipartite b-matching game (edges can be matched at most once). The classic paper of Shapley and Shubik [Shapley and Shubik, 1971] showed that core imputations of the assignment game are precisely optimal solutions to the dual of the LP-relaxation of the game. Building on this, Deng et al. [Deng et al., 1999] gave a general framework which yields analogous characterizations for several fundamental combinatorial games. Interestingly enough, their framework does not apply to the last two games stated above. In turn, we show that some of the core imputations of these games correspond to optimal dual solutions and others do not. This leads to the tantalizing question of understanding the origins of the latter. We also present new characterizations of the profits accrued by agents and teams in core imputations of the first two games. Our characterization for the first game is stronger than that for the second; the underlying reason is that the characterization of vertices of the Birkhoff polytope is stronger than that of the Balinski polytope.
Cite as

Vijay V. Vazirani. New Characterizations of Core Imputations of Matching and b-Matching Games. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 28:1-28:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vazirani:LIPIcs.FSTTCS.2022.28,
  author =	{Vazirani, Vijay V.},
  title =	{{New Characterizations of Core Imputations of Matching and b-Matching Games}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.28},
  URN =		{urn:nbn:de:0030-drops-174207},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.28},
  annote =	{Keywords: LP-duality theory, cooperative game theory, core of a game, assignment game, general graph matching game, bipartite b-matching game}
}
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.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}
}
  • Refine by Author
  • 2 Moulin, Hervé
  • 1 Vazirani, Vijay V.

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory

  • Refine by Keyword
  • 1 Assignment
  • 1 LP-duality theory
  • 1 VCG mechanisms
  • 1 Vickrey-Clarke-Groves mechanisms
  • 1 assignment
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2007
  • 1 2022

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact