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.SWAT.2016.23
URN: urn:nbn:de:0030-drops-60450
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6045/
Go to the corresponding LIPIcs Volume Portal

Gupta, Sushmita ; Iwama, Kazuo ; Miyazaki, Shuichi

Total Stability in Stable Matching Games

pdf-format:
LIPIcs-SWAT-2016-23.pdf (0.5 MB)

Abstract

The stable marriage problem (SMP) can be seen as a typical game, where each player wants to obtain the best possible partner by manipulating his/her preference list. Thus the set Q of preference lists submitted to the matching agency may differ from P, the set of true preference lists. In this paper, we study the stability of the stated lists in Q. If Q is not Nash equilibrium, i.e., if a player can obtain a strictly better partner (with respect to the preference order in P) by only changing his/her list, then in the view of standard game theory, Q is vulnerable. In the case of SMP, however, we need to consider another factor, namely that all valid matchings should not include any "blocking pairs" with respect to P. Thus, if the above manipulation of a player introduces blocking pairs, it would prevent this manipulation. Consequently, we say Q is totally stable if either Q is a Nash equilibrium or if any attempt at manipulation by a single player causes blocking pairs with respect to P. We study the complexity of testing the total stability of a stated strategy. It is known that this question is answered in polynomial time if the instance (P,Q) always satisfies P=Q. We extend this polynomially solvable class to the general one, where P and Q may be arbitrarily different.

BibTeX - Entry

@InProceedings{gupta_et_al:LIPIcs:2016:6045,
  author =	{Sushmita Gupta and Kazuo Iwama and Shuichi Miyazaki},
  title =	{{Total Stability in Stable Matching Games}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{23:1--23:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6045},
  URN =		{urn:nbn:de:0030-drops-60450},
  doi =		{10.4230/LIPIcs.SWAT.2016.23},
  annote =	{Keywords: stable matching, Gale-Shapley algorithm, manipulation, stability, Nash equilibrium}
}

Keywords: stable matching, Gale-Shapley algorithm, manipulation, stability, Nash equilibrium
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

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