Gupta, Sushmita ;
Iwama, Kazuo ;
Miyazaki, Shuichi
Total Stability in Stable Matching Games
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:123:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770118},
ISSN = {18688969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6045},
URN = {urn:nbn:de:0030drops60450},
doi = {10.4230/LIPIcs.SWAT.2016.23},
annote = {Keywords: stable matching, GaleShapley algorithm, manipulation, stability, Nash equilibrium}
}
2016
Keywords: 

stable matching, GaleShapley algorithm, manipulation, stability, Nash equilibrium 
Seminar: 

15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Issue date: 

2016 
Date of publication: 

2016 