Maximum Matchings and Popularity
share
Let G be a bipartite graph where every node has a strict ranking of its neighbors. For every node, its preferences over neighbors extend naturally to preferences over matchings. Matching N is more popular than matching M if the number of nodes that prefer N to M is more than the number that prefer M to N. A maximum matching M in G is a "popular max-matching" if there is no maximum matching in G that is more popular than M. Such matchings are relevant in applications where the set of admissible solutions is the set of maximum matchings and we wish to find a best maximum matching as per node preferences. It is known that a popular max-matching always exists in G. Here we show a compact extended formulation for the popular max-matching polytope. So when there are edge costs, a min-cost popular max-matching in G can be computed in polynomial time. This is in contrast to the min-cost popular matching problem which is known to be NP-hard. We also consider Pareto-optimality, which is a relaxation of popularity, and show that computing a min-cost Pareto-optimal matching/max-matching is NP-hard.
READ FULL TEXT