Kavitha, Telikepalli
Stable Matchings with OneSided Ties and Approximate Popularity
Abstract
We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices in A rank their neighbors in a strict order of preference while vertices in B are allowed to have weak rankings, i.e., ties are allowed in their preferences. Stable matchings always exist in G and are easy to find, however popular matchings need not exist and it is NPcomplete to decide if one exists. This motivates the "approximately popular" matching problem.
A wellknown measure of approximate popularity is low unpopularity factor. We show that when each tie in G has length at most k, there always exists a stable matching whose unpopularity factor is at most k. Our proof is algorithmic and we compute such a stable matching in polynomial time. Our result can be considered to be a generalization of Gärdenfors' result (1975) which showed that when rankings are strict, every stable matching is popular.
There are several applications where the size of the matching is its most important attribute. What one seeks here is a maximum matching M such that there is no maximum matching more popular than M. When rankings are weak, it is NPhard to decide if G admits such a matching. When ties are onesided and of length at most k, we show a polynomial time algorithm to find a maximum matching whose unpopularity factor within the set of maximum matchings is at most 2k.
BibTeX  Entry
@InProceedings{kavitha:LIPIcs.FSTTCS.2022.22,
author = {Kavitha, Telikepalli},
title = {{Stable Matchings with OneSided Ties and Approximate Popularity}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {22:122:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17414},
URN = {urn:nbn:de:0030drops174144},
doi = {10.4230/LIPIcs.FSTTCS.2022.22},
annote = {Keywords: Bipartite graphs, Maximum matchings, Unpopularity factor}
}
14.12.2022
Keywords: 

Bipartite graphs, Maximum matchings, Unpopularity factor 
Seminar: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 