Researchers find efficiency gains by relaxing stability in matchings

In a new arXiv preprint, Fernandez Abad, Klumper, and Schäfer tackle the classic tension between stability and social welfare in matching markets. They propose α-stable matchings, a relaxation where a blocking pair only forms if both agents can improve their valuations by more than a factor of 1/α (α in (0,1]). This models realistic behavior: agents won't disrupt a match for trivial gains. The authors provide a complete characterization of the tradeoff in markets with asymmetric valuations, introducing a parameter μ that bounds the ratio between any two agents' valuations for a given partner.

Their main result is a polynomial-time algorithm that constructs an α-stable matching with provable efficiency guarantees. The algorithm inflates the values of an optimal matching and then runs the classic Gale-Shapley algorithm on the modified instance. For α ≤ μ/(μ+1), it achieves 1-efficiency (optimal social welfare). For larger α, it guarantees at least (1/α)·μ/(μ+1) of the optimal welfare. The authors also show that finding the absolute best α-stable matching is NP-hard, even for α close to 1, highlighting the inherent difficulty of the problem. This work has implications for market design (e.g., medical residency matching, school choice) where slight instability can significantly improve overall welfare.