License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.28
URN: urn:nbn:de:0030-drops-174207
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17420/
Go to the corresponding LIPIcs Volume Portal

Vazirani, Vijay V.

New Characterizations of Core Imputations of Matching and b-Matching Games

pdf-format:
LIPIcs-FSTTCS-2022-28.pdf (0.6 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2022/17420},
  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}
}

Keywords: LP-duality theory, cooperative game theory, core of a game, assignment game, general graph matching game, bipartite b-matching game
Collection: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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