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 electio...