Popular Matchings with Two-Sided Preferences and One-Sided Ties

Abstract

We are given a bipartite graph $G = (A \cup B, E)$ where each vertex has a preference list ranking its neighbors: in particular, every $a \in A$ ranks its neighbors in a strict order of preference, whereas the preference lists of $b \in B$ may contain ties. A matching M is popular if there is no matching $M'$ such that the number of vertices that prefer $M'$ to M exceeds the number that prefer M to $M'$. We show that the problem of deciding whether G admits a popular matching or not is $\mathsf {NP}$-hard. This is the case even when every $b \in B$ either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each $b \in B$ puts all its neighbors into a single tie. That is, all neighbors of b are tied in b’s list and and b desires to be matched to any of them. Our main result is an $O(n^2)$ algorithm (where $n = |A \cup B|$) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not.

Á. Cseh—Work done while visiting TIFR, supported by the Deutsche Telekom Stiftung.