Search papers, labs, and topics across Lattice.
This paper introduces \texttt{SNSW-Alg}, a novel algorithm that addresses the stable marriage problem by maximizing Nash social welfare while ensuring stability among participants. The authors demonstrate that their approach not only enhances fairness across various preference distributions but also maintains competitive performance in terms of regret and other fairness metrics. Empirical results indicate that matchings produced by \texttt{SNSW-Alg} are statistically Pareto-undominated compared to traditional stable matchings based on alternative fairness criteria.
Achieving fairness in stable matching without sacrificing stability, \texttt{SNSW-Alg} significantly outperforms traditional methods in equity across diverse preference distributions.
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.
