2026/07/20 by Isabel Fernandez Abad, Sophie Klumper, Guido Schäfer
#cs.GT
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 α∈ (0,1]. We provide a complete characterization of the stability-efficiency tradeoff under asymmetric valuations. This tradeoff depends on the degree of asymmetry μ∈ (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 α≤ μ/(μ+1), our algorithm achieves 1-efficiency; for larger α, it computes an α-stable matching achieving at least (1/α)⋅ μ/(μ+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.