Source-linked AI summary
Fair Stable Matching: A Nash Social Welfare Approach
Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar
TL;DR
Stable matching algorithms can preserve stability while producing inequitable outcomes between the two sides. This paper maximizes Nash social welfare over stable matchings using SNSW-Alg, an efficient algorithm built on rotation-poset methods. Across diverse preference distributions, the NSW-optimal stable matching statistically outperforms egalitarian, regret, and sex-equality alternatives overall.
Problem
Stable matching can favor one side, while existing fairness measures may perform poorly on other measures, motivating a better overall fairness objective.
Method
The paper maximizes Nash social welfare under rank-induced utilities over stable matchings using SNSW-Alg, built on the rotation-poset framework.
Results
˜O(n4) running time and empirical studies across 100K randomly generated instances per setting show that NSW-optimal stable matchings statistically outperform egalitarian, regret, and sex-equality matchings overall.
Takeaways & Limitations
SNSW coupled with stability yields a fair outcome that is statistically Pareto-undominated by stable matchings based on regret, egalitarian, and sex equality.
Takeaways & Limitations
The model assumes equally sized sides, strict preferences, and that no agent prefers being unmatched to any possible match.
Abstract
from arXiv · showhide
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 \emph{Nash social welfare} (NSW) as a fairness objective in the classic \emph{stable marriage problem}. We develop \texttt{SNSW-Alg} that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in $\tilde{\mathcal{O}}(n^4)$ time, where $n$ is the number of men or women. We demonstrate that \texttt{SNSW-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 \texttt{SNSW-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.
1 Introduction
The paper frames stable marriage as a fairness problem because stability can favor one side, then proposes Nash social welfare as a stability-preserving fairness objective. It introduces SNSW-Alg and evaluates it against alternative stable-matching criteria.
- Motivation: Stable matching prevents blocking pairs but can produce asymmetric outcomes, including a male-optimal matching that is women-pessimal.The reverse holds when women propose, highlighting the tension between stability and fairness.
- Motivation: Existing egalitarian and minimum-regret criteria can improve some agents’ outcomes while imposing poor matches on others or performing poorly on other measures.The paper motivates a measure that performs better overall across fairness dimensions.
- Approach: The paper proposes maximizing Nash social welfare over stable matchings to balance fairness and efficiency.The objective is applied under rank-induced utilities while preserving stability.
- Approach: SNSW-Alg is a polynomial-time algorithm designed to find a stable matching that optimizes the proposed NSW objective.Its design builds on the rotation-poset framework used for stable-matching optimization.
- Evaluation: In empirical comparisons across diverse preference distributions, SNSW-Alg is evaluated against four stable-matching approaches and fairness measures.The evaluation considers fairness alongside regret, egalitarian, and sex-equality criteria.
2 Model and Background
The stable marriage model formalizes two-sided matching under strict preferences, while stability can conflict with fairness. The paper reviews established fairness criteria and motivates maximizing Nash social welfare over stable matchings.
- Model and stability: Stable matching excludes blocking pairs, ensuring no unmatched man and woman would both prefer one another to their assigned partners.A stable matching always exists for any preference instance, and the set of stable matchings is denoted Π≻.
- Model and stability: The man-optimal Gale-Shapley outcome gives men their best stable partners but women their least-preferred stable partners, creating an inherent fairness asymmetry.The woman-proposing version reverses these roles, producing the woman-optimal and men-pessimal outcome.
- Fairness criteria: Egalitarian, minimum-regret, and sex-equality stable matchings optimize different fairness measures: total ranks, worst dissatisfaction, and the satisfaction gap between sides.Each criterion selects an optimal stable matching for its own objective, but these objectives can conflict.
- Fairness criteria: In the example, the egalitarian matching has regret 4, whereas the minimum-regret matching has egalitarian value 11, illustrating trade-offs between fairness objectives.The table summarizes this conflict by showing Me dominates Mr on µe while Mr dominates Me on µr.
- Nash social welfare: The paper proposes maximizing Nash social welfare, the geometric mean of agents’ utilities, over the set of stable matchings.Although unconstrained NSW matching can be computed by maximum-weight bipartite matching, it need not be stable; the paper instead exploits the rotation-poset structure.
- Nash social welfare: For the Table 2 instance, the NSW-maximizing stable matching performs well on both egalitarian and sex-equality measures, with µe = 15 and µd = 3.The same instance contrasts with stable matchings optimized separately for egalitarian value or sex equality.
3 Our Approach
The paper maximizes Nash social welfare over stable matchings by adapting the rotation-poset framework and weighted closed-subset optimization. SNSW-Alg is proven to return the Nash-welfare-optimal stable matching in O(n^4 log n), or \tilde{O}(n^4), time.
- Our Approach: SNSW-Alg maximizes Nash social welfare over the set of stable matchings, rather than over all possible matchings.The stable-matching restriction enables use of the rotation-poset framework, whereas unrestricted NSW optimization is generally NP-hard.
- Our Approach: The algorithm starts from a Gale-Shapley stable matching, identifies rotations, and represents their precedence constraints in a rotation poset.Successive rotation elimination produces reduced preference lists, while the poset records which rotations must precede others.
- Our Approach: A capacitated s-t network converts the weighted rotation-poset problem into a minimum-cut problem whose solution yields a maximum-weight closed subset.Negative-weight rotations connect to the source, positive-weight rotations to the sink, and original precedence edges receive infinite capacity.
- Our Approach: NSW optimization becomes maximum-weight closed-subset selection by assigning each rotation a logarithmic-utility weight.Because NSW is a product of utilities, logarithms convert the objective into a sum that can be encoded through rotation weights.
- Theoretical Analysis of SNSW-Alg: SNSW-Alg outputs the stable matching that maximizes Nash social welfare for every preference profile.The algorithm eliminates the rotations in the selected closed subset from the man-oriented shortlists.
4 Empirical Evaluation
The empirical evaluation compares SNSW-Alg with fairness-oriented baselines across diverse preference distributions using normalized statistical measures. Results indicate that SNSW-Alg achieves balanced performance across fairness criteria and is Pareto-undominated in pairwise comparisons.
- Setup: Preference lists are generated iteratively by sampling choices according to agents’ popularity profiles and removing selected partners.This process continues until each agent’s preference list is complete.
- Baselines and metrics: SNSW-Alg is compared with Egalitarian-Alg, Min-Regret-Alg, and Sex-equal-Alg across four fairness measures.The baselines optimize egalitarianism, regret, and sex equality, respectively.
- Evaluation Metrics: Baseline performance deteriorates on non-optimized fairness metrics, whereas SNSW-Alg achieves a more balanced profile across all four measures.The evaluation uses empirical means across 100K instances and normalizes statistical measures to [0, 1], with 0 as best.
- Setup: The experiments use 100,000 instances with n = 25 across uniform and three popularity-based preference distributions.The popularity-based distributions use uniform, triangular, and half-normal popularity profiles.
- Observations: SNSW-Alg is Pareto-undominated in all six pairwise fairness-measure comparisons for n = 25.Its Vargha-Delaney A12 measure is strictly greater than 0.5 on measures outside those it optimizes.
- Observations: SNSW-Alg’s circular-plot area is at least 93.5% smaller than every benchmark when all four measures are compared simultaneously.The evaluation interprets smaller circular-plot area as fairer.
5 Related Work
Related work spans stable matching mechanisms, fairness criteria for stable marriage, and Nash social welfare in allocation and matching settings. The paper positions its contribution within these strands.
- Matching Theory: Matching-theory research includes stable assignment, kidney exchange, and refugee-resettlement mechanisms addressing stability, efficiency, or incentives.Examples include Gale–Shapley assignment, kidney exchange design, and refugee-resettlement mechanisms.
- Fairness in Stable Marriage Problem: Stable-marriage fairness research introduced egalitarian, regret, and sex-equality criteria with corresponding optimal stable matchings or algorithms.Prior work includes an O(n^4) egalitarian algorithm and an O(n^2) minimum-regret algorithm.
- Nash social welfare: Nash social welfare has been extensively studied in one-sided allocation, while Jain and Vaish [2024] are identified as the sole prior work applying it to two-sided markets.The cited literature covers strategic allocation, indivisible goods, coverage, many-to-one matching, and divisible items.
6 Conclusion
The paper proposes optimizing Nash social welfare under rank-induced utilities while maintaining stability, and develops SNSW-Alg for this purpose. Empirically, the NSW-optimal stable matching outperforms the compared fairness objectives across tested settings.
- Conclusion: SNSW-Alg outputs the Nash-social-welfare-optimal stable matching under rank-induced utilities.The paper proves the algorithm’s correctness and reports a running time of ˜O(n^4).
- Conclusion: Across 100K instances per setting and uniform and popularity-based preference distributions, the NSW-optimal stable matching statistically outperforms egalitarian, regret, and sex-equality approaches.The paper concludes that the proposed measure µnsw coupled with stability yields a fair outcome.
B Experimental Evaluations
The experimental evaluations include circular plots for uniform, triangular, normal, and uniform default distributions.
- A circular plot is presented for the uniform distribution.
- A circular plot is presented for the triangular distribution.
- Circular plots are also presented for the normal and uniform default distributions.