Fair Stable Matching: A Nash Social Welfare Approach

While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability, they may fall short of achieving equitable outcomes among participants. We study the role of Nash social welfare (NSW) as a fairness objective in the classic stable marriage problem. We develop textttSNSW-Alg that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in tildeO(n4) time, where n is the number of men or women. We demonstrate that textttSNSW-Alg balances equity while preserving stability. We empirically evaluate our methods across diverse preference distributions, demonstrating significant gains in fairness without substantial losses in other key measures such as regret, egalitarian criterion, and sex equality. Our findings suggest that the stable matching produced by textttSNSW-Alg is statistically Pareto-undominated by stable matchings based on other fairness measures - regret, egalitarian, and sex equality. This study offers compelling insights for designing fair-stable matching.