Fair Stable Matching: A Nash Social Welfare Approach

FAIR S TABLE M ATCHING : A NASH S OCIAL W ELFARE A PPROACH

arXiv:2609.02354v1 [cs.GT] 2 Sep 2026

A P REPRINT Rasheed Machine Learning Lab IIIT Hyderabad Hyderabad, India mohammad.ahmed@research.iiit.ac.in

Parth Desai Machine Learning Lab IIIT Hyderabad Hyderabad, India parth.desai@research.iiit.ac.in

Ganesh Ghalme Department of AI IIT Hyderabad Hyderabad, India ganeshghalme@ai.iith.ac.in

Sujt Gujar Machine Learning Lab IIIT Hyderabad Hyderabad, India sujit.gujar@iiit.ac.in

September 3, 2026

A BSTRACT 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 SNSW-Alg that finds a stable matching that maximizes Nash social welfare under rank-induced utilities in Õ(n4 ) time, where n is the number of men or women. We demonstrate that 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 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

Matching markets are economic settings where agents are paired based on preferences and compatibility. Unlike many economic markets, these do not rely on price signals for allocation. Instead, structured mechanisms determine who matches with whom, taking into account the preferences of both sides (e.g., students and colleges [Gale and Shapley, 1962], workers and firms [Revilla, 2007], organ donors and recipients [Roth et al., 2004]). Matching theory has two main branches: (i) Matching with transferable utility, where utility is transferable among agents (usually involving monetary transfers), and (ii) Matching with non-transferable utility, where transfers aren’t possible (e.g., school admissions, organ donations). In this paper, we study the stable marriage problem which falls under the non-transferable utility setting. Fairness in Matchings. The stable marriage problem involves two (most often equally sized) groups - typically referred to as men and women - in which each individual seeks to match with a member of the opposite group based on personal preferences. A central concept in the stable marriage problem is stability. A matching is stable if there are no blocking pairs - that is, no unmatched man and woman who would both prefer each other over their assigned partners. Stability is critical because unstable matchings are inherently fragile and prone to collapse, as participants may have incentives to deviate from the outcome. The celebrated Gale-Shapley algorithm [Gale and Shapley, 1962] outputs a stable matching which is optimal for the proposing side.

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

The male-optimal matching gives every man the best partner he could have in any stable matching. However, this often comes at the expense of the other side; it is highly unfair to women, who receive their least-preferred partners amongst all stable matchings. Conversely, running the algorithm with women proposing yields the female-optimal and male-pessimal outcome. This inherent asymmetry highlights a tension between stability and fairness, sparking a vast literature on improving equity and efficiency in practical matching mechanisms. Existing approaches for Fair Matching. There have been studies on various alternative criteria for improving fairness and social welfare in stable matchings. The egalitarian stable matching [Irving et al., 1987] minimizes the total sum of ranks (i.e., how far down each partner is in their preference list), promoting overall satisfaction. As we show later, the egalitarian approach may sometimes offer a very good match to the majority at the cost of some agents receiving very poor matches. To balance such situations, the minimum-regret stable matching [Gusfield, 1987] minimizes the worst individual dissatisfaction, ensuring that the least-satisfied participant is as well off as possible. The sex equal stable matching [Kato, 1993] minimizes the difference between the sum of men’s ranks and the sum of women’s ranks, focusing on minimizing the disparity across the two sides. These refinements offer ways to balance efficiency and equity while maintaining stability. However, each measure optimizes some aspect of the agents; overall, to improve fairness across all agents, we believe a new approach is warranted. Our Approach. We propose to maximize a suitably defined Nash social welfare (NSW) objective over the set of all stable matchings. Note that, if we ignore stability and capacity constraints, maximizing NSW is, in general, an NP-hard problem [Jain and Vaish, 2024]. However, under stability and capacity constraints (where each agent wants to match with exactly one agent), the problem assumes a special structure. By building upon the rotation poset framework introduced in [Irving et al., 1987], we can design an efficient algorithm to optimize NSW while preserving stability. Irving et al. [1987] constructs a capacitated directed graph based on the preferences and rotation posets of stable matchings for optimizing the additive egalitarian criterion. A challenge in our case was addressing the gap between the non-linear NSW criterion and the additive rotation poset framework. We bridge this gap by converting the NSW criterion into an equivalent additive objective. Our key idea is to appropriately adjust the edge weights in the graph to maximize NSW. However, it poses another challenge - we need a max-flow algorithm, and our weights are no longer integral, as in [Irving et al., 1987]. We then propose using Dinic’s algorithm [Dinitz, 2006] with dynamic trees by [Sleator and Tarjan, 1981] rather than Ford-Fulkerson, as proposed by Irving et al. [1987]. We prove that our updated formulation enables SNSW-Alg to compute a stable matching that maximizes NSW in polynomial time, specifically within a time complexity of Õ(n4 ). To evaluate the effectiveness of our approach in achieving fairness, we conduct an empirical study comparing three stable matching algorithms: (i) one that minimizes the sum of ranks (egalitarian), (ii) one that minimizes the worst rank (minimum regret), and (iii) one that minimizes the differences across the two sides (sex equal). Across various distributions of preference profiles, our experiments demonstrate that SNSW-Alg is statistically Pareto undominated among the four methods in most measured dimensions, highlighting its strong performance in balancing fairness and efficiency. Our Contributions. Our contributions in this work are as follows. (i) To the best of our knowledge, we are first to propose a novel objective for the stable marriage problem: maximizing Nash social welfare (NSW) over the space of stable matchings, balancing fairness and efficiency. (ii) Toward this, we propose a polynomial-time algorithm SNSW-Alg. (iii) We conduct an extensive empirical evaluation across diverse preference distributions, comparing four stable matching objectives.

2

Model and Background

In this section, we first explain our model and notation (Section 2.1) and then the required prerequisites (Section 2.2). We show the need for a newer fairness measure by example. 2.1

Model

We consider a two-sided market N consisting of two types of agents: one side, called men M , and the other, women W . Each agent is interested in matching with exactly one agent on the other side and has a preference over the other side, denoted by ≻a for an agent a ∈ N . We assume (i) both sides have an equal number of agents, n, (ii) no agent prefers to be unmatched over any possible match from the other side, and (iii) the preferences are strict. We refer to ≻= ((≻a )a∈N ) as the original preference list. A matching M(≻) outputs a match for each agent. Let r(mi , wj ) (or, r(wk , ml )) represent the rank of agent wj (or, ml ) in ≻mi (or, ≻wk ). We assumed a 0-indexed ranking, that is, the best possible match has rank 0. Motivated by Budish and Cantillon [2009], we consider ur(mi , wj ) = n − r(mi , wj ) (or, 2

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

ur(wk , ml ) = n − r(wk , ml )) to be the utility of man mi (or, woman wk ) on being matched to woman wj (or, man ml ). Let Σ denote the set of all possible matchings. 2.2

Preliminaries

We denote match of an agent a ∈ N under matching M as Ma . In a matching M, if r(mi , wj ) < r(mi , Mmi ) and r(wj , mi ) < r(wj , Mwj ) , then (mi , wj ) would prefer to match with each other over the matching M. Such a pair is called a blocking pair [Gale and Shapley, 1962]. A matching M is said to be a stable matching if it does not contain any blocking pairs [Gale and Shapley, 1962]. It is desirable to obtain a stable matching; otherwise, agents in blocking pairs may prefer to match with each other outside the market. It is a well-known result that for any arbitrary instance of ≻, a stable matching always exists [Gale and Shapley, 1962]. Let Π≻ be the set of all possible stable matchings when the agents’ original preference list is ≻. A carefully constructed instance (≻) may yield an exponential number of stable matchings (in n) [Knuth, 1997]. The Gale-Shapley algorithm1 [Gale and Shapley, 1962] outputs one such stable matching Mo (≻) (assuming men propose to women). Similarly, it would output Mz (≻) if women proposed to men. The stable matching Mo (≻) is characteristic in that it is “man-optimal”, i.e., each man gets the best possible match possible under the constraint of stability. In other words, ∀mi ∈ M, r(mi , Mo mi ) = minM∈Π≻ r(mi , Mmi ). The stable matching Mo is not only “man-optimal” but also “women-pessimal”, i.e., ∀wj ∈ W, r(wj , Mo wj ) = maxM∈Π≻ r(wj , Mwj ). Similarly, Mz is “woman-optimal” and “men-pessimal”. Though Mo (or, Mz ) satisfies the criterion of stability, it is an unfair matching for W (or, M ). This concern has motivated research beyond the Gale-Shapley algorithm to introduce fairness in matching. Fairness in Matching. The set of all stable matchings forms a lattice [Knuth, 1997]. It is desirable to determine a matching that is not only stable but also fair to all the agents. Towards this, there exist multiple optimal stable matchings in the literature - egalitarian stable matching [Irving et al., 1987], minimum-regret stable matching [Gusfield, 1987], and sex equal stable matching [Kato, 1993]. These stable matchings are optimal with respect to three fairness measures - egalitarian, regret, and sex equality. Egalitarian criterion is defined as the total sum of ranks of all matches. X X µe (M) = r(mi , Mmi ) + r(wj , Mwj ) mi ∈M

wj ∈W

Regret is defined as the worst individual dissatisfaction across men and women.   µr (M) = max max r(mi , Mmi ), max r(wj , Mwj ) mi ∈M

wj ∈W

Sex-equality is defined as the absolute difference between the total satisfaction of men and women. X X µd (M) = r(mi , Mmi ) − r(wj , Mwj ) mi ∈M

wj ∈W

Definition 1 (Egalitarian Stable Matching). [Irving et al., 1987] A stable matching Me (≻) is egalitarian if it minimizes the egalitarian criterion across all stable matchings. Me (≻) = arg min µe (M) M∈Π≻

Definition 2 (Minimum-Regret Stable Matching). [Gusfield, 1987] A stable matching Mr (≻) is minimum-regret if it minimizes the regret across all stable matchings. Mr (≻) = arg min µr (M) M∈Π≻

Definition 3 (Sex-Equal Stable Matching). [Kato, 1993] A stable matching Md (≻) is sex equal if it minimizes the sex equality across all stable matchings. Md (≻) = arg min µd (M) M∈Π≻

Irving [1985] utilize the concept of rotations and propose an O(n4 ) algorithm that finds the egalitarian stable matching Me (≻). We refer to their algorithm as Egalitarian-Alg (more details on this in Section 3.1). Gusfield [1987] provides an algorithm to find Mr (≻). However, finding Md (≻) is NP-Hard [Kato, 1993]. Section A in the Appendix summarizes all the notation used in the paper. 1

Gale and Shapley termed it as the “deferred-acceptance” algorithm. But in honor of their ground-breaking work, contemporary literature refers to it as the Gale-Shapley algorithm.

3

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

Need for an improved approach. Consider the preference instance ≻ in Table 1. The egalitarian stable matching Me = {(1, 4), (2, 1), (3, 3), (4, 5), (5, 2)} performs poorly on µr = 4. On the other hand, the minimum-regret stable matching Mr = {(1, 4), (2, 2), (3, 1), (4, 5), (5, 3)} performs poorly on µe = 11 = 3 + 8. Table 1: Example Me dominate Mr on µe and Mr dominate Me on µr

M 1: 2: 3: 4: 5:

4 5 5 5 3

3 4 1 2 2

W 2 2 3 1 4

1 3 4 4 5

W 1: 2: 3: 4: 5:

5 1 2 3 1

2 5 3 5 4

M 3 2 5 1 3

1 1 1 4 1

4 3 4 2 2

5 4 2 3 5

These gaps point to various limitations that we address in this paper. Our empirical analysis also shows that such examples shown above are not rare. Statistically, each of the three fairness measures above performs poorly on the others; we need a better measure that performs better overall. Towards this, we make use of the well-known measure of Nash social welfare (NSW) [Nash et al., 1950] to address these limitations. Nash social welfare. Nash social welfare (NSW) may be seen as fair in multiple ways in many other domains [Nash et al., 1950, Kaneko and Nakamura, 1979, Moulin, 2004, Caragiannis et al., 2019]. Moulin [2004] shows that NSW is the only fair measure that satisfies many reasonable fairness axioms under general technical conditions. While the Nash bargaining solution maximizes the product of gains over a disagreement point, the NSW maximizes the product of utilities, which is equivalent to Nash bargaining with a disagreement point equal to zero. Accordingly, our formulation is as follows: Nash social welfare (NSW) is the geometric mean of the utilities of men and women. 1  Y  2n Y nsw µ (M) = ur(mi , Mmi ) × ur(wj , Mwj ) mi ∈M

(1)

wj ∈W

In two-sided market literature. For instance, Jain and Vaish [2024] work with agents’ utilities for the matching and maximize Nash social welfare. We refer to such matching as NSW matching. Definition 4. A matching Mnsw (≻) is Nash welfare optimal if it maximizes the Nash social welfare of all agents. Mnsw (≻) = arg max µnsw (M) M∈Σ

The matching Mnsw (≻) can be computed in O(n3 ) time using maximum-weight matching algorithms in bipartite graphs. The algorithm indeed outputs a matching that could be considered fair according to the aforementioned measures (µe , µr , µd ), owing to the larger search space. Anyhow, the matching it computes need not be stable. Hence, we propose to maximize NSW amongst all possible stable matchings. Consider ≻2 given in Table 2. The Table 2: ≻2 : Nash social welfare performs well on all measures

M 1: 2: 3: 4: 5:

3 1 4 2 2

2 5 3 3 3

W 5 2 1 4 5

1 4 2 1 1

W 1: 2: 3: 4: 5:

4 3 5 5 4

3 1 4 4 3

1 3 1 1 4

M 5 4 2 2 1

2 2 5 5 2

4 5 3 3 5

stable matching Me (≻) = {(1, 2), (2, 1), (3, 4), (4, 3), (5, 5)} has µe = 15, but it performs poorly on µd = 7. The stable matching Md (≻) = {(1, 3), (2, 5), (3, 1), (4, 2), (5, 4)} has µd = 2, but its µe = 16. The stable matching M = {(1, 2), (2, 5), (3, 4), (4, 3), (5, 1)} performs well on both measures: µe = 15 and µd = 3. This particular stable matching maximizes the Nash social welfare across all stable matchings.

3

Our Approach

3.1

SNSW-Alg

First, we define an NSW optimal stable matching. 4

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

Definition 5. A stable matching Msnsw (≻) is Nash welfare optimal if it maximizes the Nash social welfare of all agents. Msnsw (≻) = arg max µnsw (M) M∈Π≻

Note the difference in definitions of Mnsw (≻) and Msnsw (≻); the former is over all possible matching Σ and the latter is over Π≻ . Finding a matching Mnsw (≻) is the same as maximum weight matching in a bipartite graph [Jain and Vaish, 2024]. However, because it does not need to be stable, we cannot leverage existing max-flow or matching algorithms to design an algorithm - SNSW-Alg that finds Msnsw . On the other hand, Egalitarian-Alg in Irving et al. [1987] determines a stable matching that minimizes µe , that is, outputs Me (≻). We build upon Egalitarian-Alg. To this end, we present a short description of Egalitarian-Alg in the following paragraph. Egalitarian-Alg. Egalitarian-Alg begins with a stable matching (typically obtained via the Gale-Shapley algorithm) and identifies rotations, following the framework of [Irving, 1985]. Definition 6. A rotation ρ, ρ = (m0 , w0 ), . . . , (mr−1 , wr−1 ), is a cyclic sequence of matched pairs, such that ∀i ∈ [0, r − 1], wi ≻mi wi+1 and mi−1 ≻wi mi , where (i + 1), (i − 1) is taken (mod r). Rotation (say ρ) is said to be exposed with respect to a reduced preference list (say S ) if wi = f irstS (mi ) = secondS (mi−1 ). Successive elimination of rotations produces “reduced preference lists” S . A rotation ρ is said to be eliminated if, ∀i ∈ [0, r − 1], ∀j : mj ≻wi mi−1 , mj ̸∈ Swi , wi ̸∈ Smj . If a rotation ρ cannot be exposed before another rotation π is eliminated, then π is said to precede ρ. The resulting precedence structure defines the rotation poset P , whose vertices (V (P )) correspond to rotations and whose directed edges (E(P )) represent precedence relations [Irving, 1985]. We define predP (ρ) as all predecessors of rotation ρ in P . A sparse subgraph P ′ of P is constructed using the following rules: R1 If (mi∗ , wj ∗ ) belongs to rotation π, and wj ′ is the first woman below wj ∗ in mi∗ ’s preference list such that (mi∗ , wj ′ ) belongs to rotation ρ, then add edge (π, ρ). R2 If (mi∗ , wj ′ ) does not belong to any rotation but is eliminated by rotation π, and wj ∗ is the first woman above wj ′ such that (mi∗ , wj ∗ ) belongs to rotation ρ, then add edge (π, ρ). The transitive closure of P ′ equals P ; consequently, P ′ preserves all closed subsets and therefore all stable matchings [Irving and Leather, 1986]. Specifically, eliminating the rotations of a closed subset yields a reduced preference structure S , and the stable matching (m, f irstS (m)) corresponds uniquely to that subset. Given P ′ , a capacitated s-t network P ′ (s, t) is constructed. A source s is connected to each negative-weight rotation ρ with capacity |w(ρ)|, while each positive-weight rotation is connected to sink t with capacity w(ρ). All original edges of P ′ are assigned infinite capacity. The following result links minimum cuts and maximum-weight closed subsets. Theorem 1 ([Irving et al., 1987]). Let X be a minimum s-t cut in P ′ (s, t). The positive rotations whose edges to t remain uncut, together with all their predecessors in P ′ , form a maximum-weight closed subset of P ′ . Since the number of rotations and edges in P ′ are each bounded by O(n2 ), both the network size and maximum flow value are O(n2 ). Therefore, applying Ford-Fulkerson yields the maximum-weight closed subset—and hence the egalitarian-optimal stable matching—in O(|K||E|) = O(n4 ) time. Adapting Egalitarian-Alg to build SNSW-Alg. Note that Egalitarian-Alg assigns a weight w(ρ) (Eqn. 2) to a rotation ρ = {(m0 , w0 ), (m1 , w1 ), . . . , (mr−1 , wr−1 )} in poset P . With this, the algorithm actually generates a new graph P ′ . The goal in the algorithm is to minimize µe (M ).

w(ρ) =

r−1 X

ur(mi , ρmi+1 ) − ur(mi , ρmi ) +

i=0

r−1 X

ur(wi , ρwi−1 ) − ur(wi , ρwi )

(2)

i=0

Our goal is to maximize Nash social welfare, which is the product of utilities. Using logarithmic transformations, we can reduce the problem to maximizing the sum of the logarithms of utilities. Hence, we propose to use weights of rotations as defined in Definition 7. 5

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

Definition 7. Given a rotation ρ = {(m0 , w0 ), (m1 , w1 ), . . . , (mr−1 , wr−1 )} in a stable marriage instance, we define the weight w′ (ρ) of that rotation by

′

w (ρ) =

r−1 X

log ur(mi , ρmi+1 ) − log ur(mi , ρmi ) +

i=0

r−1 X

log ur(wi , ρwi−1 ) − log ur(wi , ρwi )

(3)

i=0

Determining Msnsw (≻) reduces to determining Me (≻) by plugging the weights in Equation 3 in Egalitarian-Alg. In Egalitarian-Alg, the edge weights of P ′ (s, t) were integers. Hence, they could apply the Ford-Fulkerson algorithm to find the max-flow in O(C · E) time. In SNSW-Alg, edge weights need not be integers. Therefore, we employ Dinic’s maximum flow algorithm [Dinitz, 2006] with dynamic trees improvement by Sleator and Tarjan [1981] to find the max-flow in O(|V | · |E| · log |V |) time. Thus, Egalitarian-Alg adapted to our settings is described as follows.

Algorithm 1 SNSW-Alg 1: Input: ≻= ((≻a )a∈N ) 2: Output: Msnsw (≻) 3: Procedure: 4: Mo (≻m , ≻w ) = Gale-Shapley(≻) 5: Determine the vertex set V (P ) 6: Initialize w(ρ), ∀ρ ∈ V (P ) using Equation 3 7: Construct subgraph P ′ via rules in Section 3.1 8: ∀e ∈ E(P ′ ), w(e) ← ∞, Construct P ′ (s, t) as follows: 9: ∀ρ ∈ V (P ′ ) : (i)w(ρ) < 0, e : s → ρ, w(e) := |w(ρ)|, (ii)w(ρ) > 0, e : ρ → t, w(e) := w(ρ) 10: X = min − cut(P ′ (s, t)) (Dinic’s algorithm [Dinitz, 2006] with dynamic trees improvement by Sleator and Tarjan

[1981])

11: X + := {ρ ∈ P ′ (s, t) : e(ρ, t) uncut by X}, S := X + ∪ predP (X + ) 12: for all ρ ∈ S do 13: Eliminate ρ, and Update S as explained in Section 3.1 14: end for 15: return MSNSW-Alg (≻) = {(mi , f irstS (mi ))}mi ∈M

Now we prove the correctness and the time complexity of SNSW-Alg.

3.2

Theoretical Analysis of SNSW-Alg

We prove the correctness of SNSW-Alg as follows. Proposition 1. Let M′ be the stable matching obtained on eliminating rotations ρ1 , ρ2 , . . . , ρt from the man-oriented shortlist, then

µnsw (M′ ) = µnsw (Mo ) ∗

t Y

w′ (ρi ) exp 2n i=1

!

Proof. Consider a stable matching Ms , with rotation ρ exposed in its preference lists, and let M be the stable matching obtained upon eliminating ρ from the reduced preference lists associated with Ms . Thus, the following follows 6

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

naturally. w′ (ρ) =

r−1 X

log ur(mi , ρmi+1 ) − log ur(mi , ρmi ) +

i=0

exp w′ (ρ) =

r−1 X

log ur(wi , ρwi−1 ) − log ur(wi , ρwi )

Using 3

i=0 r−1 Y

ur(mi , ρmi+1 ) · ur(wi , ρwi−1 ) ur(mi , ρmi ) · ur(wi , ρwi ) i=0

Multiply numerator and denominator by the utility of all man-woman pairs who remain matched after elimination of ρ   Q Q  nsw 2n ur(m , M ) × ur(w , M ) i mi j wj mi ∈M wj ∈W µ (M) ′ = exp w (ρ) =  Q Q µnsw (Ms ) s )× s ) ur(m , M ur(w , M i j mi wj mi ∈M wj ∈W Since M′ is obtained upon the successive elimination of ρ1 , . . . , ρt from shortlists associated with Mo , the equation associated with each rotation may be multiplied together to prove the proposition. Theorem 2. For every preference profile ≻, SNSW-Alg outputs the stable matching that maximizes the Nash social welfare, i.e., SNSW-Alg returns Msnsw (≻). Proof. SNSW-Alg outputs the maximum-weight closed subset S in the weighted rotation poset P using w(ρ) from Def. 7.   ′ Y w (ρ ) i  µnsw (MSNSW-Alg ) = µnsw (Mo ) ∗  exp 2n ρi ∈S

snsw

With this, we need that M (≻) is obtained on eliminating the rotations in S starting from the man-oriented shortlists to complete the proof. It follows from the Theorem 1 and Definition 5 that MSNSW-Alg (≻) = Msnsw (≻). We will now present the proof of the running time complexity of SNSW-Alg. Theorem 3. The running time complexity of SNSW-Alg is O(n4 log n). Proof. Note that P ′ is a subgraph of the rotation poset P . Thus, V (P ′ ) ⊆ V (P ). Since there exist at most O(n2 ) man-woman pairs, and each pair is part of at most one rotation, we have |V (P ′ )| ≤ |V (P )| = O(n2 ). Observation 1. |V | in P ′ (s, t) is bounded by O(n2 ). Next, we observe that the rules R1 and R2 used to create a subgraph P ′ of P associate each edge with a man-woman pair. Furthermore, each pair is associated with the creation of an edge at most once. Therefore, |E(P ′ )| ≤ n ∗ n = O(n2 ). We formalize this in the next observation. Observation 2. |E| in P ′ (s, t) is bounded by O(n2 ). Finally, we observe that the graph P ′ (s, t) as adopted in SNSW-Alg has positive edge weights, and the time complexity of its construction is O. This observation directly follows from the construction of P ′ (s, t) from P ′ . All edges from the source s to the negative weight rotation nodes (ρ) have capacities |w(ρ)|. All edges from positive weight rotation nodes (π) to the sink node t have capacities w(π). All other edges in P ′ (s, t) borrowed from P ′ have capacities set to infinity. Therefore, all edges have positive edge weights. Moreover, since the number of vertices in P ′ is upper-bounded by O(n2 ) from Observation 1. Observation 3. The graph P ′ (s, t) as adopted in SNSW-Alg has positive edge weights, and its construction is O(n2 ) time complexity. Everything put together: Finding the max-flow using Dinic’s algorithm [Dinitz, 2006] with dynamic trees improvement by Sleator and Tarjan [1981] requires O(|V | · |E| · log |V |) time. Based on Observations 1, 2, and 3, this time complexity reduces to O(n4 log n), or Õ(n4 ). 7

Fair Stable Matching: A Nash Social Welfare Approach

4

A P REPRINT

Empirical Evaluation

We empirically evaluate the fairness of our proposed algorithm, SNSW-Alg, on randomly generated data. The goal of our experiments is to demonstrate the fairness of our approach relative to existing baselines across multiple dimensions. We begin by describing the experimental setup, followed by how we generate our data, the baseline algorithms we compare SNSW-Alg against, and the fairness metrics used to evaluate the matching. Finally, we describe the experiments performed and the observations. 4.1

Setup

Preference Generation. We study four distributions over the space of preference profiles ≻, each capturing different structural assumptions about the input. We may categorize them into two groups: i Uniform Distribution D1 : ≻m ∼ U[n] and ≻w ∼ U[n], that is, preference is any permutation drawn uniformly at random. ii Popularity-based Distributions [Zou et al., 2010]. Here, we initialize a popularity profile pa of all a ∈ N according to a PU , where pa ∼ U[0, 1] b PT , where pa ∼ T [0, 1] is triangular with peak at 0.5. c PN , where pa ∼ N (µ = 0, σ = 1) is half-normal.  ) Next, we sample the first preference of mi (wj ) from W (M ) as Pwx = P p(wxp(w P(mk ) = z) wz ∈W  P p(mk ) p(ml ) . Once the sampled woman (man) appends to ≻m (≻w ), we remove it from W (M ) and ml ∈M

resample the next preference. This is performed iteratively till ≻a is completed for agent a. Benchmarks.

We consider the following baselines to compare with SNSW-Alg.

i B1 : Egalitarian-Alg [Irving et al., 1987] ii B2 : Min-Regret-Alg [Gusfield, 1987] iii B3 : Sex-equal-Alg iterates over all possible stable matchings and determines the stable matching with optimal sex equality measure since the sex equal stable matching problem is NP-Hard [Kato, 1993]. The distributions we considered, on average, did not yield an exponential number of stable matchings (|Π|). Thus, we were able to complete all experiments within 6.5 hours, using a 13th Gen Intel i7-1355U (2.3 GHz) with 16GB of RAM. Evaluation Metrics. We observe that while Baselines B1 , B2 , and B3 achieve strong performance on their respective objectives, their performance deteriorates considerably on the other fairness metrics. By comparison, SNSW-Alg achieves a more balanced performance profile across all four metrics. There exist instances of ≻ such that SNSW-Alg outputs Msnsw that performs relatively well across all four measures µe , µr , µd , µnsw . For example, for ≻2 given in Table 2, Msnsw (≻) performs particularly well. While such examples are of theoretical importance, it is a worst-case example. Hence, instead of evaluating algorithms on worst-case performance, we employ statistical versions 4. We compute the empirical mean measures of all baselines across 100K instances.

µ̃e,ALG = d,ALG

µ̃

PK

e ALG ) i=1 µ (Mi

K d µ (MALG ) i i=1 K

PK =

µ̃r,ALG = nsw,ALG

µ̃

PK

r ALG ) i=1 µ (Mi

K nsw (MALG ) i i=1 µ K

PK =

(4)

Setup We use K = 100, 000 instances for n = 25 using all four distributions U, PU , PT , PN and compare µ̃e,ALG , µ̃r,ALG , µ̃d,ALG , µ̃nsw,ALG . To compare these statistical versions uniformly, we normalize them to [0, 1], 0 being the best. Consider the stable matching produced by algorithm ALG. Let the statistical regret measured be µ̃r,ALG . Let the maximum and minimum values of µ̃r measured across all baselines be rmax , rmin . Then we normalize µ̃r,ALG to µ̃r,ALG −rmin −µ̃nsw,ALG nsw,ALG to rmax . Each baseline would achieve 0 on the measure it optimizes. rmax −rmin . We normalize µ̃ rmax −rmin The smaller the triangle’s area, the fairer the algorithm’s matching is. 8

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

Figure 1: Circular Plots for n = 25 Radar Chart (Order: r

→ d → e → nsw)

Radar Chart (Order: r

1 (Area: 0.37972) 2 (Area: 0.86320) 3 (Area: 0.99017)

μd̃

→ e → nsw → d)

1 (Area: 0.34843) 2 (Area: 1.00000) 3 (Area: 0.38609)

μẽ

SNSW-Alg (Area: 0.15169)

0.2

μ̃

0.6

0.4

0.8

SNSW-Alg (Area: 0.11889)

1.0

μ̃

e

r

0.2

μ̃

μd̃

(a) U

(b) PU

nsw

d

e)

Radar Chart (Order: r

1 (Area: 0.14566) 2 (Area: 1.00000) 3 (Area: 0.71354)

nsw

e

0.2

d

0.4

0.6

nsw

d)

1 (Area: 0.38971) 2 (Area: 1.00000) 3 (Area: 0.45197)

SNSW-Alg (Area: 0.13517)

1.0 r

1.0

μr̃

e

SNSW-Alg (Area: 0.04751)

0.8

0.4

0.8

nsw

̃ μnsw Radar Chart (Order: r

0.6

0.2

nsw

e

d

(c) PT

(d) PN

9

0.4

0.6

0.8

1.0 r

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

Table 3: CoV across different Measures

Agents

Metric

Regret

Egalitarian

Disparity

SNSW

r

25

µ µe µd µnsw

0.060 0.094 0.518 0.062

0.055 0.113 0.521 0.061

0.055 0.095 0.597 0.061

0.058 0.113 0.523 0.062

50

µr µe µd µnsw

0.035 0.082 0.587 0.045

0.032 0.093 0.597 0.045

0.032 0.082 0.696 0.044

0.034 0.092 0.600 0.045

Figure 2: Pareto Undominance of SNSW-Alg against other baselines

e vs r

4.8 4.7 r

17.5

18.0

16.5

d vs e

17.0

0

r

17.5

20.7

18.0

4.8 e

4.9

17.0

20.8 20.7

r

17.5

18.0

nsw vs d

20.9

20.6 4.7

16.5

nsw vs e

20.9 nsw

20

4.2

20.8 20.6

17.0

SNSW-Alg

d

0

nsw

1 2 16.5 3

nsw vs r

20.9 nsw

20 d

e

4.9

d vs r

20.8 20.7 20.6

4.7

4.8 e

4.9

10

0

d

10

20

Observations

We first consider SNSW-Alg against baselines for all 6 possible combinations of two fairness measures at a time. We observe in Figure 2 that SNSW-Alg is Pareto-undominated in such pairwise measure comparison for n = 25. We measure the value of Vargha-Delaney A12 measure comparing SNSW-Alg’s output with the baseline algorithms on all measures other than those it optimizes over. We observe that the measure is strictly greater than 0.5 for all such combinations. We also compare all four measures simultaneously. We plot µ̃’s of all the algorithms on a circle (Figure 1). We observe that SNSW-Alg has the least area: at least 93.5% smaller than all benchmarks, demonstrating the statistical significance of SNSW-Alg in achieving fairness across multiple criteria.

5

Related Work

Matching Theory. Gale and Shapley [1962] proposed an algorithm for assigning students to colleges (or residents to hospitals) along with preserving the stability of the matching. Roth et al. [2004] proposed a design to build upon kidney exchange practices, taking into account properties of efficiency and incentive compatibility. Delacrétaz et al. [2016] proposed several refugee resettlement mechanisms that improve match efficiency as well as incentivize refugees to report their choices, and respect the priorities of local areas. More recently, Aziz et al. [2022] authored a survey on many-to-one matching under various market constraints, such as lower quotas, regional constraints, diversity constraints, multidimensional capacity constraints, and hereditary constraints. Kamiyama [2020] studied the problem of popular matching under matroidal constraints, and proposed a polynomial-time algorithm to find the largest size popular matching under the given constraints. 10

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

Fairness in Stable Marriage Problem. Irving et al. [1987] established a fairness criterion to measure how equitable any given stable matching is in the context of the stable marriage problem, and proposed an O(n4 ) algorithm to find such an optimal (egalitarian) stable matching. Gusfield [1987] proposed another fairness metric for the stable marriage problem called regret and proposed an O(n2 ) algorithm to find the minimum-regret stable matching. Gusfield and Irving [1989] studied the parametric stable marriage problem and analyzed the nature of the parametrized measure and time complexity of finding the optimal solution to the parametric stable marriage problem. Kato [1993] studied the complexity of another problem - sex equal stable marriage, which aimed to minimize the net disparity between the assigned matches to the two sides, concluding that this problem is NP-Hard. More recently, Alkan and Yildiz [2022] introduced “modular stable matching rules” as a framework for equity in stable matchings, establishing an equivalence between modular optimization and an ordinal condition called convexity. They also propose a new equity criterion called “equity undominance” and characterize the modular rules that satisfy it. Nash social welfare. Brânzei et al. [2017] study the question of (approximately) implementing the objective of Nash social welfare for fair allocation of resources in the presence of strategic agents in relation to one-sided markets. Barman et al. [2019] propose algorithms for fair allocation of indivisible goods to strategic agents in single-parameter environments along with theoretical Nash welfare guarantees. Barman et al. [2022] utilizes the Nash social welfare function to study fairness and efficiency in coverage problems. Jain and Vaish [2024] studied the complexity of problems in many-to-one matching (not necessarily stable) that aim to maximize Nash social welfare in two-sided markets. Garg et al. [2025] study the interplay between competitive equilibrium and Nash welfare maximizing allocations in the context of the divisible items allocation problem. To summarize, Nash social welfare has been studied extensively in one-sided markets. As per our knowledge, the work of Jain and Vaish [2024] is the sole work on the application of Nash social welfare in two-sided markets.

6

Conclusion

In this paper, we studied the problem of obtaining a fair and stable matching in two-sided markets. Matching produced to optimize any of the existing measures performs poorly on other measures. To this end, we proposed optimizing Nash social welfare under rank-induced utilities while ensuring stability. We then designed SNSW-Alg to output the NSW optimal stable matching. We then proved the correctness of SNSW-Alg and showed its running time complexity is Õ(n4 ). We then empirically study the fairness of matching with different approaches. Empirically, we demonstrate on 100K randomly generated instances per setting, across uniform and popularity-based preference distributions, that, overall, the NSW-optimal stable matching statistically outperforms egalitarian, regret, or sex-equality. Our study shows that the proposed measure µnsw , coupled with stability, yields a fair outcome. We leave further theoretical investigations into its guarantees relative to other measures as future work.

References Ahmet Alkan and Kemal Yildiz. Equitable stable matchings under modular assessment. Available at SSRN 4030050, 2022. Haris Aziz, Péter Biró, and Makoto Yokoo. Matching market design with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 12308–12316, 2022. Siddharth Barman, Ganesh Ghalme, Shweta Jain, Pooja Kulkarni, and Shivika Narang. Fair division of indivisible goods among strategic agents. arXiv preprint arXiv:1901.09427, 2019. Siddharth Barman, Anand Krishna, Y Narahari, and Soumyarup Sadhukhan. Nash welfare guarantees for fair and efficient coverage. In International Conference on Web and Internet Economics, pages 256–272. Springer, 2022. Simina Brânzei, Vasilis Gkatzelis, and Ruta Mehta. Nash social welfare approximation for strategic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 611–628, 2017. Eric Budish and Estelle Cantillon. Strategic behavior in multi-unit assignment problems: Lessons for market design. Technical report, Working Paper, 2009. Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3): 1–32, 2019. David Delacrétaz, Scott Duke Kominers, and Alexander Teytelboym. Refugee resettlement. University of Oxford Department of Economics Working Paper, 2016. Yefim Dinitz. Dinitz’algorithm: The original version and even’s version. In Theoretical Computer Science: Essays in Memory of Shimon Even, pages 218–240. Springer, 2006. 11

Fair Stable Matching: A Nash Social Welfare Approach

A P REPRINT

David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American mathematical monthly, 69(1):9–15, 1962. Jugal Garg, Yixin Tao, and László A Végh. Approximating competitive equilibrium by nash welfare. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2538–2559. SIAM, 2025. Dan Gusfield. Three fast algorithms for four problems in stable marriage. SIAM Journal on Computing, 16(1):111–128, 1987. Dan Gusfield and Robert W Irving. Parametric stable marriage and minimum cuts. Information Processing Letters, 30 (5):255–259, 1989. Robert W Irving. An efficient algorithm for the “stable roommates” problem. Journal of Algorithms, 6(4):577–595, 1985. Robert W Irving and Paul Leather. The complexity of counting stable marriages. SIAM Journal on Computing, 15(3): 655–667, 1986. Robert W Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the “optimal” stable marriage. Journal of the ACM (JACM), 34(3):532–543, 1987. Pallavi Jain and Rohit Vaish. Maximizing nash social welfare under two-sided preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9798–9806, 2024. Naoyuki Kamiyama. Popular matchings with two-sided preference lists and matroid constraints. Theoretical Computer Science, 809:265–276, 2020. Mamoru Kaneko and Kenjiro Nakamura. The nash social welfare function. Econometrica: Journal of the Econometric Society, pages 423–435, 1979. Akiko Kato. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, 10:1–19, 1993. Donald E. Knuth. Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms, volume 10. American Mathematical Society, Providence, RI, 1997. Hervé Moulin. Fair division and collective welfare. MIT press, 2004. John F Nash et al. The bargaining problem. Econometrica, 18(2):155–162, 1950. Pablo Revilla. Many-to-one matching when colleagues matter. SSRN, 2007. Alvin E Roth, Tayfun Sönmez, and M Utku Ünver. Kidney exchange. The Quarterly journal of economics, 119(2): 457–488, 2004. Daniel D Sleator and Robert Endre Tarjan. A data structure for dynamic trees. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, pages 114–122, 1981. James Zou, Sujit Gujar, and David Parkes. Tolerable manipulability in dynamic assignment without money. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 947–952, 2010.

A

Notation M W n N r(a, b) ur(mi , wj ) ur(wk , ml ) M Mo Mz Mr Me Md Mnsw Msnsw

Men side of market: {m1 , m2 , . . . , mn } Women side of market: {w1 , w2 , . . . , wn } Number of men and women | M |=| W |= n Set of all men and women: M ∪ W Rank of agent b in ≻a Utility of man mi on match with woman wj Utility of woman wk on match with man ml Any stable matching between M and W Man-optimal stable matching Woman-optimal stable matching Min-Regret stable matching Egalitarian stable matching Sex-equal stable matching Nash optimal matching Nash stable matching 12

Fair Stable Matching: A Nash Social Welfare Approach

B

A P REPRINT

Experimental Evaluations 1 2 3

μẽ

1 2 3

μẽ

SNSW-Alg

Area: 0.04235 0.2

μd̃

Area: 1.00000

0.4

0.6

0.8

SNSW-Alg

1.0 Area: 0.04289 0.2

μr̃

Area: 0.45172

μd̃

Area: 1.00000 Area: 0.10704

̃ μnsw

̃ μnsw

1 2 3

0.6

Area: 0.04350 0.2

μd̃

Area: 1.00000

0.4

0.6

Area: 0.46083

μr̃

1 2 3

μẽ

SNSW-Alg

0.8

1.0

Area: 0.45875

Area: 0.10858

μẽ

0.4

0.8

SNSW-Alg

1.0 Area: 0.04370 0.2

μr̃

μd̃

Area: 1.00000 Area: 0.10797

̃ μnsw

̃ μnsw

13

0.6

Area: 0.45573

Area: 0.10766

Figure 3: Circular Plot for Uniform Distribution

0.4

0.8

1.0

μr̃

Fair Stable Matching: A Nash Social Welfare Approach

e

1 2 3

A P REPRINT

e

SNSW-Alg 0.8

d

Area: 1.00000

SNSW-Alg

1.0

Area: 0.04820 0.4 0.6 0.2 Area: 0.70387

0.8

r

d

Area: 1.00000

Area: 0.14472

nsw

nsw

1 2 3

e

SNSW-Alg 0.8

d

Area: 1.00000

Area: 0.04799 0.4 0.6 0.2 Area: 0.71126

1.0

Area: 0.04743 0.4 0.6 0.2 Area: 0.71201

Area: 0.14763

e

1 2 3

r

1 2 3

SNSW-Alg

1.0

0.8

r

d

Area: 1.00000

Area: 0.04833 0.4 0.6 0.2 Area: 0.70433

Area: 0.14631

Area: 0.14424

nsw

nsw

Figure 4: Circular Plot for Triangular Distribution

14

1.0

r

Fair Stable Matching: A Nash Social Welfare Approach

e

1 2 3

A P REPRINT

e

SNSW-Alg 0.8

d

Area: 1.00000

SNSW-Alg

1.0

Area: 0.05298 0.4 0.6 0.2 Area: 0.49759

0.8

r

d

Area: 1.00000

Area: 0.12665

nsw

nsw

1 2 3

e

SNSW-Alg 0.8

d

Area: 1.00000

Area: 0.05271 0.4 0.6 0.2 Area: 0.49272

1.0

Area: 0.05204 0.4 0.6 0.2 Area: 0.50696

Area: 0.12643

e

1 2 3

r

1 2 3

SNSW-Alg

1.0

0.8

r

d

Area: 1.00000

Area: 0.05400 0.4 0.6 0.2 Area: 0.51166

Area: 0.12696

Area: 0.12900

nsw

nsw

Figure 5: Circular Plot for Normal Distribution

15

1.0

r

Fair Stable Matching: A Nash Social Welfare Approach

1 2 3

e

A P REPRINT

1 2 3

e

SNSW-Alg 0.8

d

Area: 0.86587

SNSW-Alg

1.0

Area: 0.05373 0.4 0.6 0.2 Area: 0.98970

0.8

r

d

Area: 0.86376

Area: 0.05473 0.4 0.6 0.2 Area: 0.99011

Area: 0.13027

Area: 0.13226

nsw

nsw

1 2 3

μẽ

Area: 0.05373 0.2

μd̃

Area: 0.86320

0.4

0.6

Area: 0.99017

r

1 2 3

μẽ

SNSW-Alg

0.8

1.0

SNSW-Alg

1.0 Area: 0.05404 0.2

μr̃

μd̃

Area: 0.86190

0.6

Area: 0.99185

Area: 0.12950

Area: 0.13072

̃ μnsw

̃ μnsw

Figure 6: Circular Plot for Uniform Default Distribution

16

0.4

0.8

1.0

μr̃

Related documents

• Constrained Fair Allocations via Partition Matroid Reductions#819141
• Constrained Fair Allocations via Partition Matroid Reductions#809149
• Reconfiguration in Fair Division Revisited#1109380
• Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores#997365
• When Maximum Nash Welfare Becomes Strongly Fair: Bi-valued Goods#1154745