Beyond Stability: Improved Efficiency Guarantees for $\hat{I}\pm$-Stable Matchings

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 $\hat{I}\pm$-stability, which models agents as willing to deviate only when the potential improvement is sufficiently large. Under $\hat{I}\pm$-stability, no pair of agents can deviate and improve their valuations by more than a factor of $1/\hat{I}\pm$, with $\hat{I}\pm \in (0,1]$. We provide a complete characterization of the stability-efficiency tradeoff under asymmetric valuations. This tradeoff depends on the degree of asymmetry $\hat{I}¼\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 $\hat{I}\pm$-stable matching attaining the best possible efficiency guarantee. For $\hat{I}\pm \le \hat{I}¼/(\hat{I}¼+1)$, our algorithm achieves 1-efficiency; for larger $\hat{I}\pm$, it computes an $\hat{I}\pm$-stable matching achieving at least $(1/\hat{I}\pm )\cdot \hat{I}¼/(\hat{I}¼+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 $\hat{I}\pm$-stable matching is NP-hard, even under slight relaxations of stability, i.e., for $\hat{I}\pm$ close to 1.

14 pages, 2 figures