Quasi-Popular Matchings, Optimality, and Extended Formulations

Let $G$ be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching $M$ in $G$ is popular if $M$ does not lose a head-to-head election against any matching. Popular matchings generalize stable matchings. Unfortunately, when there are edge costs, to find or even approximate up to any factor a popular matching of minimum cost is NP-hard. Let $\mathrm{opt}$ be the cost of a min-cost popular matching. Our goal is to efficiently compute a matching of cost at most $\mathrm{opt}$ by paying the price of mildly relaxing popularity. Our main positive results are two bicriteria algorithms that find in polynomial time a “quasi-popular” matching of cost at most $\mathrm{opt}$. Moreover, one of the algorithms finds a quasi-popular matching of cost at most that of a min-cost popular fractional matching, which could be much smaller than $\mathrm{opt}$. Key to the other algorithm is a polynomial-size extended formulation for an integral polytope sandwiched between the popular and quasi-popular matching polytopes. We complement these results by showing that it is NP-hard to find a quasi-popular matching of minimum cost and that both the popular and quasi-popular matching polytopes have near-exponential extension complexity.