Hamada, Koki ;
Miyazaki, Shuichi ;
Yanagisawa, Hiroki
StrategyProof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists
Abstract
In the stable marriage problem (SM), a mechanism that always outputs a stable matching is called a stable mechanism. One of the wellknown stable mechanisms is the manoriented GaleShapley algorithm (MGS). MGS has a good property that it is strategyproof to the men's side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a manstrategyproof mechanism. Unfortunately, MGS is not a womanstrategyproof mechanism. (Of course, if we flip the roles of men and women, we can see that the womanoriented GaleShapley algorithm (WGS) is a womanstrategyproof but not a manstrategyproof mechanism.) Roth has shown that there is no stable mechanism that is simultaneously manstrategyproof and womanstrategyproof, which is known as Roth's impossibility theorem.
In this paper, we extend these results to the stable marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth's impossibility theorem takes over to SMTI. Therefore, we focus on the onesidedstrategyproofness. In SMTI, one instance can have stable matchings of different sizes, and it is natural to consider the problem of finding a largest stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratios used in the theory of approximation algorithms. We say that a stablemechanism is a capproximatestable mechanism if it always returns a stable matching of size at least 1/c of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI1TM, where only men's lists can contain ties (and women's lists must be strictly ordered).
Our results are summarized as follows: (i) MAX SMTI admits both a manstrategyproof 2approximatestable mechanism and a womanstrategyproof 2approximatestable mechanism. (ii) MAX SMTI1TM admits a womanstrategyproof 2approximatestable mechanism. (iii) MAX SMTI1TM admits a manstrategyproof 1.5approximatestable mechanism. All these results are tight in terms of approximation ratios. Also, all these results apply for strategyproofness against coalitions.
BibTeX  Entry
@InProceedings{hamada_et_al:LIPIcs:2019:11505,
author = {Koki Hamada and Shuichi Miyazaki and Hiroki Yanagisawa},
title = {{StrategyProof Approximation Algorithms for the Stable Marriage Problem with Ties and Incomplete Lists}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {9:19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11505},
URN = {urn:nbn:de:0030drops115059},
doi = {10.4230/LIPIcs.ISAAC.2019.9},
annote = {Keywords: Stable marriage problem, strategyproofness, approximation algorithm, ties, incomplete lists}
}
28.11.2019
Keywords: 

Stable marriage problem, strategyproofness, approximation algorithm, ties, incomplete lists 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 