License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.99
URN: urn:nbn:de:0030-drops-44504
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4450/
Go to the corresponding LIPIcs Volume Portal

Aziz, Haris ; de Keijzer, Bart

Shapley meets Shapley

pdf-format:
8.pdf (0.7 MB)

Abstract

This paper concerns the analysis of the Shapley value in matching games. Matching games constitute a fundamental class of cooperative games which help understand and model auctions and assignments. In a matching game, the value of a coalition of vertices is the weight of the maximum size matching in the subgraph induced by the coalition. The Shapley value is one of the most important solution concepts in cooperative game theory. After establishing some general insights, we show that the Shapley value of matching games can be computed in polynomial time for some special cases: graphs with maximum degree two, and graphs that have a small modular decomposition into cliques or cocliques (complete k-partite graphs are a notable special case of this). The latter result extends to various other well-known classes of graph-based cooperative games. We continue by showing that computing the Shapley value of unweighted matching games is #P-complete in general. Finally, a fully polynomial-time randomized approximation scheme (FPRAS) is presented. This FPRAS can be considered the best positive result conceivable, in view of the #P-completeness result.

BibTeX - Entry

@InProceedings{aziz_et_al:LIPIcs:2014:4450,
  author =	{Haris Aziz and Bart de Keijzer},
  title =	{{Shapley meets Shapley}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{99--111},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4450},
  URN =		{urn:nbn:de:0030-drops-44504},
  doi =		{10.4230/LIPIcs.STACS.2014.99},
  annote =	{Keywords: matching games, Shapley, counting complexity}
}

Keywords: matching games, Shapley, counting complexity
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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