Maximum Matchings and Popularity

. Let \ (G = (A B, E) \) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching \ (M\) in \ (G\) is a popular max-matching if there is no maximum matching more popular than \ (M\). In other words, for any maximum matching \ (N\), the number of nodes that prefer \ (M\) to \ (N\) is at least the number of nodes that prefer \ (N\) to \ (M\). It is known that popular max-matchings always exist in \ (G\) and one such matching can be efficiently computed. In this paper we are in the weighted setting, i. e. , there is a cost function \ (c: E R\), and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching. Keywordsbipartite graphsstable matchingsdual certificatesMSC codes68W9968Q17