文章基本信息

标题：Total Stability in Stable Matching Games
本地全文：下载
作者：Sushmita Gupta ; Kazuo Iwama ; Shuichi Miyazaki 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：53
页码：23:1-23:12
DOI：10.4230/LIPIcs.SWAT.2016.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：stable matching; Gale-Shapley algorithm; manipulation; stability; Nash equilibrium