Two Problems in Max-size Popular Matchings

With T. Kavitha
Algorithmica, 81(7):2738–2764, 2019

We study popular matchings in the many-to-many matching problem, which is given by a graph G = (V,E) and, for every agent u∈V, a capacity cap(u) ≥ 1 and a preference list strictly ranking her neighbors. A matching in G is popular if it weakly beats every matching in a majority vote when agents cast votes for one matching versus the other according to their preferences. First, we show that when G = (A∪B,E) is bipartite, e.g., when matching students to courses, every pairwise stable matching is popular. In particular, popular matchings are guaranteed to exist. Our main contribution is to show that a max-size popular matching in G can be computed in linear time by the 2-level Gale–Shapley algorithm, which is an extension of the classical Gale–Shapley algorithm. We prove its correctness via linear programming. Second, we consider the problem of computing a max-size popular matching in G = (V,E) (not necessarily bipartite) when every agent has capacity 1, e.g., when matching students to dorm rooms. We show that even when G admits a stable matching, this problem is NP-hard, which is in contrast to the tractability result in bipartite graphs.