Search Results

Documents authored by Aziz, Haris

Document
DOI: 10.4230/DagRep.11.6.124
Matching Under Preferences: Theory and Practice (Dagstuhl Seminar 21301)

Authors: Haris Aziz, Péter Biró, Tamás Fleiner, and Bettina Klaus

Published in: Dagstuhl Reports, Volume 11, Issue 6 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21301 "Matching Under Preferences: Theory and Practice". The seminar featured a mixture of technical scientific talks, survey talks, open problem presentations, working group sessions, five-minute contributions ("rump session"), and a panel discussion. This was the first Dagstuhl seminar that was dedicated to matching under preferences.
Cite as

Haris Aziz, Péter Biró, Tamás Fleiner, and Bettina Klaus. Matching Under Preferences: Theory and Practice (Dagstuhl Seminar 21301). In Dagstuhl Reports, Volume 11, Issue 6, pp. 124-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{aziz_et_al:DagRep.11.6.124,
  author =	{Aziz, Haris and Bir\'{o}, P\'{e}ter and Fleiner, Tam\'{a}s and Klaus, Bettina},
  title =	{{Matching Under Preferences: Theory and Practice (Dagstuhl Seminar 21301)}},
  pages =	{124--146},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{6},
  editor =	{Aziz, Haris and Bir\'{o}, P\'{e}ter and Fleiner, Tam\'{a}s and Klaus, Bettina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.6.124},
  URN =		{urn:nbn:de:0030-drops-155826},
  doi =		{10.4230/DagRep.11.6.124},
  annote =	{Keywords: market design, matching under preferences, matching with distributional constraints, organ exchange, stable matching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.99
Shapley meets Shapley

Authors: Haris Aziz and Bart de Keijzer

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

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.
Cite as

Haris Aziz and Bart de Keijzer. Shapley meets Shapley. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 99-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{aziz_et_al:LIPIcs.STACS.2014.99,
  author =	{Aziz, Haris and de Keijzer, Bart},
  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 =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.99},
  URN =		{urn:nbn:de:0030-drops-44504},
  doi =		{10.4230/LIPIcs.STACS.2014.99},
  annote =	{Keywords: matching games, Shapley, counting complexity}
}
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 About DROPS Imprint Privacy Contact