Beyond Stability: Improved Efficiency Guarantees for $α$-Stable Matchings
2026-07-20 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors explore how to balance stable matchings, where no pair wants to switch, with achieving the best overall happiness in the market. They introduce a relaxed version called α-stability, where agents only change partners if the improvement is large enough. Their findings show this relaxation can lead to better total happiness, especially when agent preferences are uneven. They also design an efficient algorithm to find the best α-stable matchings and prove that finding the absolute best α-stable matching is computationally hard for values of α near full stability.
Stable matchingMarket designSocial welfareα-stabilityGale-Shapley algorithmAsymmetric valuationsComputational complexityNP-hardMatching algorithms
Authors
Isabel Fernandez Abad, Sophie Klumper, Guido Schäfer
Abstract
Stable matching mechanisms are fundamental to market design but face an inherent tension between stability and social welfare optimality. We study a natural relaxation of stability, termed $α$-stability, which models agents as willing to deviate only when the potential improvement is sufficiently large. Under $α$-stability, no pair of agents can deviate and improve their valuations by more than a factor of $1/α$, with $α\in (0,1]$. We provide a complete characterization of the stability-efficiency tradeoff under asymmetric valuations. This tradeoff depends on the degree of asymmetry $μ\in (0,1]$, which bounds the ratio between agents' valuations for any pair. Our results show that relaxing stability can substantially improve achievable efficiency guarantees. We further present a polynomial-time algorithm that computes an $α$-stable matching attaining the best possible efficiency guarantee. For $α\le μ/(μ+1)$, our algorithm achieves 1-efficiency; for larger $α$, it computes an $α$-stable matching achieving at least $(1/α)\cdot μ/(μ+1)$ of the optimal social welfare. Remarkably, our algorithm inflates the values of an optimal matching and then applies the Gale-Shapley algorithm to the modified instance. Finally, we show that computing an optimal $α$-stable matching is NP-hard, even under slight relaxations of stability, i.e., for $α$ close to 1.