Fairness--Stability Trade-offs in Many-to-One Matching

Abstract

We study the trade-off between firm-side fairness and coalition stability in many-to-one matching markets with transferable payments. For a fixed matching $X$, we characterize the largest supportable core factor by a bottleneck financing problem: $\alpha (X)=1/\Phi (X)$, where $\Phi (X)={\min }_{z\ge 0}{\max }_i{R}_i(X,z)$. This yields a polynomial-time linear program and local sensitivity formulas for one-worker reallocations. We then develop a maximum-edge round algorithm and a broader class of mutual-top safe choices. Every safe execution is EF1 and, with $t=\delta (A)$ denoting the minimum positive-edge quality, guarantees $\alpha (X)\ge \max \{t,1/[m-(m-1)t]\}$ and $SW(X)/OPT\ge t+(1-t)/m$. These bounds give finite-firm lower and upper bounds for the EF1--core minimax frontier, with exact results for two firms and for three firms when $\delta \le 1/2$; as the number of firms grows, the tight scale-free stability rate is $\delta$. We also extend the financing formulation to stronger $EF{X}^{+}$ fairness and capacity-constrained markets.