ALBERT

Description: 〈h3〉Abstract〈/h3〉 〈p〉We study popular matchings in the many-to-many matching problem, which is given by a graph 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 and, for every agent 〈span〉 〈span〉\(u\in V\)〈/span〉 〈/span〉, a capacity 〈span〉 〈span〉\(\textsf {cap}(u) \ge 1\)〈/span〉 〈/span〉 and a preference list strictly ranking her neighbors. A matching in 〈em〉G〈/em〉 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 〈span〉 〈span〉\(G = (A\cup B,E)\)〈/span〉 〈/span〉 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 〈em〉G〈/em〉 can be computed in linear time by the 〈em〉2-level Gale–Shapley〈/em〉 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 〈span〉 〈span〉\(G = (V,E)\)〈/span〉 〈/span〉 (not necessarily bipartite) when every agent has capacity 1, e.g., when matching students to dorm rooms. We show that even when 〈em〉G〈/em〉 admits a stable matching, this problem is 〈span〉 〈span〉\(\mathsf {NP}\)〈/span〉 〈/span〉-hard, which is in contrast to the tractability result in bipartite graphs.〈/p〉