Paper deep dive
Fair Stable Matching: A Nash Social Welfare Approach
Parth Desai, Rasheed M, Ganesh Ghalme, Sujit Gujar
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/3/2026, 4:28:12 AM
Summary
This paper introduces SNSW-Alg, a polynomial-time algorithm that solves the stable marriage problem by maximizing Nash Social Welfare (NSW) while preserving stability. Unlike traditional algorithms like Gale-Shapley which prioritize stability at the cost of fairness, or existing fairness-focused algorithms (egalitarian, minimum-regret, sex-equal) that optimize specific metrics, SNSW-Alg uses a rotation poset framework with logarithmic utility weights to balance equity and efficiency. Empirical results show that matchings produced by SNSW-Alg are statistically Pareto-undominated by those from other fairness measures.
Entities (8)
Relation Signals (8)
SNSW-Alg → hastimecomplexity → Õ(n^4)
confidence 100% · SNSW-Alg that finds a stable matching ... in Õ(n^4) time
SNSW-Alg → optimizes → Nash Social Welfare
confidence 100% · We develop SNSW-Alg that finds a stable matching that maximizes Nash social welfare
Gale-Shapley algorithm → prioritizes → Stability
confidence 100% · While traditional stable matching algorithms, such as the Gale-Shapley algorithm, prioritize stability
SNSW-Alg → buildsupon → Egalitarian-Alg
confidence 90% · We build upon Egalitarian-Alg... Adapting Egalitarian-Alg to build SNSW-Alg.
SNSW-Alg → usesalgorithm → Dinic’s algorithm
confidence 90% · We then propose using Dinic’s algorithm ... rather than Ford-Fulkerson
SNSW-Alg → usesdatastructure → Rotation Poset
confidence 90% · By building upon the rotation poset framework... we can design an efficient algorithm
SNSW-Alg → outperforms → Minimum-Regret Stable Matching
confidence 85% · 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.
SNSW-Alg → outperforms → Sex-Equal Stable Matching
confidence 85% · Our findings suggest that the stable matching produced by SNSW-Alg is statistically Pareto-undominated by stable matchings based on other fairness measures ... sex equality.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2609.02354v1
- Canonical: https://arxiv.org/abs/2609.02354v1
Trouble viewing inline? Open PDF directly →
Full Text
47,694 characters extracted from source content.
Expand or collapse full text
Fair Stable Matching: A Nash Social Welfare Approach Rasheed Affiliation: Machine Learning Lab Affiliation: IIIT Hyderabad Affiliation: Hyderabad, India Email: mohammad.ahmed@research.iiit.ac.in Parth Desai Affiliation: Machine Learning Lab Affiliation: IIIT Hyderabad Affiliation: Hyderabad, India Email: parth.desai@research.iiit.ac.in Ganesh Ghalme Affiliation: Department of AI Affiliation: IIT Hyderabad Affiliation: Hyderabad, India Email: ganeshghalme@ai.iith.ac.in Sujt Gujar Affiliation: Machine Learning Lab Affiliation: IIIT Hyderabad Affiliation: Hyderabad, India Email: sujit.gujar@iiit.ac.in Abstract 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) O(n^4) 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. A Preprint 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 (i) 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. 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) O(n^4). 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), (i) one that minimizes the worst rank (minimum regret), and (i) 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. (i) Toward this, we propose a polynomial-time algorithm SNSW-Alg. (i) 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 _a for an agent a∈Na∈ N. We assume (i) both sides have an equal number of agents, n, (i) no agent prefers to be unmatched over any possible match from the other side, and (i) the preferences are strict. We refer to ≻=((≻a)a∈N) =(( _a)_a∈ N) as the original preference list. A matching ℳ(≻)M( ) outputs a match for each agent. Let r(mi,wj)r(m_i,w_j) (or, r(wk,ml)r(w_k,m_l)) represent the rank of agent wjw_j (or, mlm_l) in ≻mi _m_i (or, ≻wk _w_k). We assumed a 00-indexed ranking, that is, the best possible match has rank 00. Motivated by Budish and Cantillon (2009), we consider ur(mi,wj)=n−r(mi,wj)ur(m_i,w_j)=n-r(m_i,w_j) (or, ur(wk,ml)=n−r(wk,ml)ur(w_k,m_l)=n-r(w_k,m_l)) to be the utility of man mim_i (or, woman wkw_k) on being matched to woman wjw_j (or, man mlm_l). Let Σ denote the set of all possible matchings. 2.2 Preliminaries We denote match of an agent a∈Na∈ N under matching ℳM as ℳaM_a. In a matching ℳM, if r(mi,wj)<r(mi,ℳmi)r(m_i,w_j)<r(m_i,M_m_i) and r(wj,mi)r(w_j,m_i) <r(wj,ℳwj)<r(w_j,M_w_j) , then (mi,wj)(m_i,w_j) 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 algorithm11 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. (Gale and Shapley, 1962) outputs one such stable matching ℳo(≻)M^o( ) (assuming men propose to women). Similarly, it would output ℳz(≻)M^z( ) if women proposed to men. The stable matching ℳo(≻)M^o( ) 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,ℳomi)=minℳ∈Π≻r(mi,ℳmi)∀ m_i∈ M,r(m_i,M^o_m_i)= _M∈ _ r(m_i,M_m_i). The stable matching ℳoM^o is not only “man-optimal” but also “women-pessimal”, i.e., ∀wj∈W,r(wj,ℳowj)=maxℳ∈Π≻r(wj,ℳwj)∀ w_j∈ W,r(w_j,M^o_w_j)= _M∈ _ r(w_j,M_w_j). Similarly, ℳzM^z is “woman-optimal” and “men-pessimal”. Though ℳoM^o (or, ℳzM^z) 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. μe(ℳ)=∑mi∈Mr(mi,ℳmi)+∑wj∈Wr(wj,ℳwj)μ^e(M)= _m_i∈ Mr(m_i,M_m_i)+ _w_j∈ Wr(w_j,M_w_j) Regret is defined as the worst individual dissatisfaction across men and women. μr(ℳ)=max(maxmi∈Mr(mi,ℳmi),maxwj∈Wr(wj,ℳwj))μ^r(M)= ( _m_i∈ Mr(m_i,M_m_i), _w_j∈ Wr(w_j,M_w_j) ) Sex-equality is defined as the absolute difference between the total satisfaction of men and women. μd(ℳ)=|∑mi∈Mr(mi,ℳmi)−∑wj∈Wr(wj,ℳwj)|μ^d(M)= _m_i∈ Mr(m_i,M_m_i)- _w_j∈ Wr(w_j,M_w_j) Definition 1 (Egalitarian Stable Matching). (Irving et al., 1987) A stable matching ℳe(≻)M^e( ) is egalitarian if it minimizes the egalitarian criterion across all stable matchings. ℳe(≻)=argminℳ∈Π≻μe(ℳ)M^e( )= _M∈ _ μ^e(M) Definition 2 (Minimum-Regret Stable Matching). (Gusfield, 1987) A stable matching ℳr(≻)M^r( ) is minimum-regret if it minimizes the regret across all stable matchings. ℳr(≻)=argminℳ∈Π≻μr(ℳ)M^r( )= _M∈ _ μ^r(M) Definition 3 (Sex-Equal Stable Matching). (Kato, 1993) A stable matching ℳd(≻)M^d( ) is sex equal if it minimizes the sex equality across all stable matchings. ℳd(≻)=argminℳ∈Π≻μd(ℳ)M^d( )= _M∈ _ μ^d(M) Irving (1985) utilize the concept of rotations and propose an (n4)O(n^4) algorithm that finds the egalitarian stable matching ℳe(≻)M^e( ). We refer to their algorithm as Egalitarian-Alg (more details on this in Section 3.1). Gusfield (1987) provides an algorithm to find ℳr(≻)M^r( ). However, finding ℳd(≻)M^d( ) is NP-Hard (Kato, 1993). Section A in the Appendix summarizes all the notation used in the paper. Need for an improved approach. Consider the preference instance ≻ in Table 1. The egalitarian stable matching ℳe=(1,4),(2,1),(3,3),(4,5),(5,2)M^e=\(1,4),(2,1),(3,3),(4,5),(5,2)\ performs poorly on μr=4μ^r=4. On the other hand, the minimum-regret stable matching ℳr=(1,4),(2,2),(3,1),(4,5),(5,3)M^r=\(1,4),(2,2),(3,1),(4,5),(5,3)\ performs poorly on μe=11=3+8μ^e=11=3+8. Table 1: Example ℳeM^e dominate ℳrM^r on μeμ^e and ℳrM^r dominate ℳeM^e on μrμ^r M W 1: 4 3 2 1 5 2: 5 4 2 3 1 3: 5 1 3 4 2 4: 5 2 1 4 3 5: 3 2 4 5 1 W M 1: 2 1 3 4 5 2: 5 1 2 3 4 3: 3 1 5 4 2 4: 5 4 1 2 3 5: 4 1 3 2 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 and others, 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 and others, 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. μnsw(ℳ)=(∏mi∈Mur(mi,ℳmi)×∏wj∈Wur(wj,ℳwj))12nμ^nsw(M)= ( _m_i∈ Mur(m_i,M_m_i)× _w_j∈ Wur(w_j,M_w_j) ) 12n (1) 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 ℳnsw(≻)M^nsw( ) is Nash welfare optimal if it maximizes the Nash social welfare of all agents. ℳnsw(≻)=argmaxℳ∈Σμnsw(ℳ)M^nsw( )= _M∈ μ^nsw(M) The matching ℳnsw(≻)M^nsw( ) can be computed in (n3)O(n^3) 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μ^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. Table 2: ≻2 _2: Nash social welfare performs well on all measures M W 1: 3 2 5 1 4 2: 1 5 2 4 3 3: 4 3 1 2 5 4: 2 3 4 1 5 5: 2 3 5 1 4 W M 1: 3 1 5 2 4 2: 1 3 4 2 5 3: 4 1 2 5 3 4: 4 1 2 5 3 5: 3 4 1 2 5 Consider ≻2 _2 given in Table 2. The stable matching ℳe(≻)=(1,2),(2,1),(3,M^e( )=\(1,2),(2,1),(3, 4),(4,3),(5,5)4),(4,3),(5,5)\ has μe=15μ^e=15, but it performs poorly on μd=7μ^d=7. The stable matching ℳd(≻)=(1,3),(2,5),(3,1),(4,2),(5,4)M^d( )=\(1,3),(2,5),(3,1),(4,2),(5,4)\ has μd=2μ^d=2, but its μe=16μ^e=16. The stable matching ℳ=(1,2),(2,5),(3,4),(4,3),(5,1)M=\(1,2),(2,5),(3,4),(4,3),(5,1)\ performs well on both measures: μe=15μ^e=15 and μd=3μ^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. Definition 5. A stable matching ℳsnsw(≻)M^snsw( ) is Nash welfare optimal if it maximizes the Nash social welfare of all agents. ℳsnsw(≻)=argmaxℳ∈Π≻μnsw(ℳ)M^snsw( )= _M∈ _ μ^nsw(M) Note the difference in definitions of ℳnsw(≻)M^nsw( ) and ℳsnsw(≻)M^snsw( ); the former is over all possible matching Σ and the latter is over Π≻ _ . Finding a matching ℳnsw(≻)M^nsw( ) 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 ℳsnswM^snsw. On the other hand, Egalitarian-Alg in Irving et al. (1987) determines a stable matching that minimizes μeμ^e, that is, outputs ℳe(≻)M^e( ). 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),ρ=(m_0,w_0),…,(m_r-1,w_r-1), is a cyclic sequence of matched pairs, such that ∀i∈[0,r−1],wi≻miwi+1∀ i∈[0,r-1],w_i _m_iw_i+1 and mi−1≻wimim_i-1 _w_im_i, where (i+1),(i−1)(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=first(mi)=second(mi−1)w_i=first_ S(m_i)=second_ S(m_i-1). Successive elimination of rotations produces “reduced preference lists” S. A rotation ρ is said to be eliminated if, ∀i∈[0,r−1],∀j:mj≻wimi−1,mj∉wi,wi∉mj∀ i∈[0,r-1],∀ j:m_j _w_im_i-1,m_j ∈ S_w_i,w_i ∈ S_m_j. 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)V(P)) correspond to rotations and whose directed edges (E(P)E(P)) represent precedence relations (Irving, 1985). We define predP(ρ)pred_P(ρ) as all predecessors of rotation ρ in P. A sparse subgraph P′P of P is constructed using the following rules: R1 If (mi∗,wj∗)(m_i^*,w_j^*) belongs to rotation π, and wj′w_j is the first woman below wj∗w_j^* in mi∗m_i^*’s preference list such that (mi∗,wj′)(m_i^*,w_j ) belongs to rotation ρ, then add edge (π,ρ)(π,ρ). R2 If (mi∗,wj′)(m_i^*,w_j ) does not belong to any rotation but is eliminated by rotation π, and wj∗w_j^* is the first woman above wj′w_j such that (mi∗,wj∗)(m_i^*,w_j^*) belongs to rotation ρ, then add edge (π,ρ)(π,ρ). The transitive closure of P′P equals P; consequently, P′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,first(m))(m,first_ S(m)) corresponds uniquely to that subset. Given P′P , a capacitated s-t network P′(s,t)P (s,t) is constructed. A source s is connected to each negative-weight rotation ρ with capacity |w(ρ)||w(ρ)|, while each positive-weight rotation is connected to sink t with capacity w(ρ)w(ρ). All original edges of P′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)P (s,t). The positive rotations whose edges to t remain uncut, together with all their predecessors in P′P , form a maximum-weight closed subset of P′P . Since the number of rotations and edges in P′P are each bounded by (n2)O(n^2), both the network size and maximum flow value are (n2)O(n^2). Therefore, applying Ford-Fulkerson yields the maximum-weight closed subset—and hence the egalitarian-optimal stable matching—in (|K||E|)=(n4)O(|K||E|)=O(n^4) time. Adapting Egalitarian-Alg to build SNSW-Alg. Note that Egalitarian-Alg assigns a weight w(ρ)w(ρ) (Eqn. 2) to a rotation ρ=(m0,w0),(m1,w1),…,(mr−1,wr−1)ρ=\(m_0,w_0),(m_1,w_1),…,(m_r-1,w_r-1)\ in poset P. With this, the algorithm actually generates a new graph P′P . The goal in the algorithm is to minimize μe(M)μ^e(M). w(ρ)=∑i=0r−1ur(mi,ρmi+1)−ur(mi,ρmi)+∑i=0r−1ur(wi,ρwi−1)−ur(wi,ρwi)w(ρ)= _i=0^r-1ur(m_i, _m_i+1)-ur(m_i, _m_i)+ _i=0^r-1ur(w_i, _w_i-1)-ur(w_i, _w_i) (2) 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. Definition 7. Given a rotation ρ=(m0,w0),(m1,w1),…,(mr−1,wr−1)ρ=\(m_0,w_0),(m_1,w_1),…,(m_r-1,w_r-1)\ in a stable marriage instance, we define the weight w′(ρ)w (ρ) of that rotation by w′(ρ)=∑i=0r−1logur(mi,ρmi+1)−logur(mi,ρmi)+∑i=0r−1logur(wi,ρwi−1)−logur(wi,ρwi)w (ρ)= _i=0^r-1 ur(m_i, _m_i+1)- ur(m_i, _m_i)+ _i=0^r-1 ur(w_i, _w_i-1)- ur(w_i, _w_i) (3) Determining ℳsnsw(≻)M^snsw( ) reduces to determining ℳe(≻)M^e( ) by plugging the weights in Equation 3 in Egalitarian-Alg. In Egalitarian-Alg, the edge weights of P′(s,t)P (s,t) were integers. Hence, they could apply the Ford-Fulkerson algorithm to find the max-flow in (C⋅E)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 (|V|⋅|E|⋅log|V|)O(|V|·|E|· |V|) time. Thus, Egalitarian-Alg adapted to our settings is described as follows. Algorithm 1 SNSW-Alg 1: Input: ≻=((≻a)a∈N) =(( _a)_a∈ N) 2: Output: ℳsnsw(≻)M^snsw( ) 3: Procedure: 4: ℳo(≻m,≻w)M^o( _m, _w) = Gale-Shapley(≻ ) 5: Determine the vertex set V(P)V(P) 6: Initialize w(ρ),∀ρ∈V(P)w(ρ),\>∀ρ∈ V(P) using Equation 3 7: Construct subgraph P′P via rules in Section 3.1 8: ∀e∈E(P′),w(e)←∞∀ e∈ E(P ),w(e)←∞, Construct P′(s,t)P (s,t) as follows: 9: ∀ρ∈V(P′):(i)w(ρ)<0,e:s→ρ,w(e):=|w(ρ)|,(ii)w(ρ)>0,e:ρ→t,w(e):=w(ρ)∀ρ∈ V(P ):(i)w(ρ)<0,e:s→ρ,w(e):=|w(ρ)|,(i)w(ρ)>0,e:ρ→ t,w(e):=w(ρ) 10: X=min−cut(P′(s,t))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,:=X+∪predP(X+)X^+:=\ρ∈ P (s,t):e(ρ,t) uncut by X\, S:=X^+∪ pred_P(X^+) 12: for all ρ∈ρ∈ S do 13: Eliminate ρ, and Update S as explained in Section 3.1 14: end for 15: return ℳSNSW-Alg(≻)=(mi,first(mi))mi∈MM SNSW-Alg( )=\(m_i,first_ S(m_i))\_m_i∈ 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 _1, _2,…, _t from the man-oriented shortlist, then μnsw(ℳ′)=μnsw(ℳo)∗(∏i=1texpw′(ρi)2n)μ^nsw(M )=μ^nsw(M^o)* ( _i=1^t w ( _i)2n ) Proof. Consider a stable matching ℳsM^s, with rotation ρ exposed in its preference lists, and let ℳM be the stable matching obtained upon eliminating ρ from the reduced preference lists associated with ℳsM^s. Thus, the following follows naturally. w′(ρ)=∑i=0r−1logur(mi,ρmi+1)−logur(mi,ρmi)+∑i=0r−1logur(wi,ρwi−1)−logur(wi,ρwi)Using3 w (ρ)= _i=0^r-1 ur(m_i, _m_i+1)- ur(m_i, _m_i)+ _i=0^r-1 ur(w_i, _w_i-1)- ur(w_i, _w_i) ~ eq:wt-rot expw′(ρ)=∏i=0r−1ur(mi,ρmi+1)⋅ur(wi,ρwi−1)ur(mi,ρmi)⋅ur(wi,ρwi) w (ρ)= _i=0^r-1 ur(m_i, _m_i+1)· ur(w_i, _w_i-1)ur(m_i, _m_i)· ur(w_i, _w_i) Multiply numerator and denominator by the utility of all man-woman pairs who remain matched after elimination of ρ expw′(ρ)=(∏mi∈Mur(mi,ℳmi)×∏wj∈Wur(wj,ℳwj))(∏mi∈Mur(mi,ℳmis)×∏wj∈Wur(wj,ℳwjs))=(μnsw(ℳ)μnsw(ℳs))2n w (ρ)= ( _m_i∈ Mur(m_i,M_m_i)× _w_j∈ Wur(w_j,M_w_j) ) ( _m_i∈ Mur(m_i,M^s_m_i)× _w_j∈ Wur(w_j,M^s_w_j) )= ( μ^nsw(M)μ^nsw(M^s) )^2n Since ℳ′M is obtained upon the successive elimination of ρ1,…,ρt _1,…, _t from shortlists associated with ℳoM^o, 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 ℳsnsw(≻)M^snsw( ). Proof. SNSW-Alg outputs the maximum-weight closed subset S in the weighted rotation poset P using w(ρ)w(ρ) from Def. 7. μnsw(ℳSNSW-Alg)=μnsw(ℳo)∗(∏ρi∈expw′(ρi)2n)μ^nsw(M SNSW-Alg)=μ^nsw(M^o)* ( _ _i∈ S w ( _i)2n ) With this, we need that ℳsnsw(≻)M^snsw( ) 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 ℳSNSW-Alg(≻)=ℳsnsw(≻)M SNSW-Alg( )=M^snsw( ). ∎ We will now present the proof of the running time complexity of SNSW-Alg. Theorem 3. The running time complexity of SNSW-Alg is (n4logn)O(n^4 n). Proof. Note that P′P is a subgraph of the rotation poset P. Thus, V(P′)⊆V(P)V(P ) V(P). Since there exist at most (n2)O(n^2) man-woman pairs, and each pair is part of at most one rotation, we have |V(P′)|≤|V(P)|=(n2)|V(P )|≤|V(P)|=O(n^2). Observation 1. |V||V| in P′(s,t)P (s,t) is bounded by (n2)O(n^2). Next, we observe that the rules R1 and R2 used to create a subgraph P′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=(n2)|E(P )|≤ n*n=O(n^2). We formalize this in the next observation. Observation 2. |E||E| in P′(s,t)P (s,t) is bounded by (n2)O(n^2). Finally, we observe that the graph P′(s,t)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)P (s,t) from P′P . All edges from the source s to the negative weight rotation nodes (ρ) have capacities |w(ρ)||w(ρ)|. All edges from positive weight rotation nodes (π) to the sink node t have capacities w(π)w(π). All other edges in P′(s,t)P (s,t) borrowed from P′P have capacities set to infinity. Therefore, all edges have positive edge weights. Moreover, since the number of vertices in P′P is upper-bounded by (n2)O(n^2) from Observation 1. Observation 3. The graph P′(s,t)P (s,t) as adopted in SNSW-Alg has positive edge weights, and its construction is (n2)O(n^2) 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 (|V|⋅|E|⋅log|V|)O(|V|·|E|· |V|) time. Based on Observations 1, 2, and 3, this time complexity reduces to (n4logn)O(n^4 n), or ~(n4) O(n^4). ∎ 4 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 D1D_1: ≻m∼[n] _m [n] and ≻w∼[n] _w [n], that is, preference is any permutation drawn uniformly at random. i Popularity-based Distributions (Zou et al., 2010). Here, we initialize a popularity profile pap_a of all a∈Na∈ N according to a PP_U, where pa∼[0,1]p_a [0,1] b PP_T, where pa∼[0,1]p_a [0,1] is triangular with peak at 0.50.5. c PP_N, where pa∼(μ=0,σ=1)p_a (μ=0,σ=1) is half-normal. Next, we sample the first preference of mim_i (wjw_j) from W (M) as ℙwx=p(wx)∑wz∈Wp(wz)P_w_x= p(w_x) _w_z∈ Wp(w_z) (ℙ(mk)=p(mk)∑ml∈Mp(ml)P(m_k)= p(m_k) _m_l∈ Mp(m_l)). Once the sampled woman (man) appends to ≻m _m (≻w _w), we remove it from W (M) and resample the next preference. This is performed iteratively till ≻a _a is completed for agent a. Figure 1: Circular Plots for n=25n=25 (a) U (b) PP_U (c) PP_T (d) PP_N Benchmarks. We consider the following baselines to compare with SNSW-Alg. i ℬ1B_1: Egalitarian-Alg (Irving et al., 1987) i ℬ2B_2: Min-Regret-Alg (Gusfield, 1987) i ℬ3B_3: 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.56.5 hours, using a 13th Gen Intel i7-1355U (2.3 GHz) with 16GB of RAM. Evaluation Metrics. We observe that while Baselines ℬ1B_1, ℬ2B_2, and ℬ3B_3 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 ℳsnswM^snsw that performs relatively well across all four measures μe,μr,μd,μnswμ^e,μ^r,μ^d,μ^nsw. For example, for ≻2 _2 given in Table 2, ℳsnsw(≻)M^snsw( ) 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=∑i=1Kμe(ℳiALG)Kμ~r,ALG=∑i=1Kμr(ℳiALG)Kμ~d,ALG=∑i=1Kμd(ℳiALG)Kμ~nsw,ALG=∑i=1Kμnsw(ℳiALG)K split μ^e,ALG&= _i=1^Kμ^e(M^ALG_i)K μ^r,ALG= _i=1^Kμ^r(M^ALG_i)K\\ μ^d,ALG&= _i=1^Kμ^d(M^ALG_i)K μ^nsw,ALG= _i=1^Kμ^nsw(M^ALG_i)K\\ split (4) Setup We use K=100,000K=100,000 instances for n=25n=25 using all four distributions ,P,P,PU,P_U,P_T,P_N and compare μ~e,ALG,μ~r,ALG,μ~d,ALG,μ~nsw,ALG μ^e,ALG, μ^r,ALG, μ^d,ALG, μ^nsw,ALG. To compare these statistical versions uniformly, we normalize them to [0,1][0,1], 00 being the best. Consider the stable matching produced by algorithm ALGALG. Let the statistical regret measured be μ~r,ALG μ^r,ALG. Let the maximum and minimum values of μ~r μ^r measured across all baselines be rmax,rminr_max,r_min. Then we normalize μ~r,ALG μ^r,ALG to μ~r,ALG−rminrmax−rmin μ^r,ALG-r_minr_max-r_min. We normalize μ~nsw,ALG μ^nsw,ALG to rmax−μ~nsw,ALGrmax−rmin r_max- μ^nsw,ALGr_max-r_min. Each baseline would achieve 00 on the measure it optimizes. The smaller the triangle’s area, the fairer the algorithm’s matching is. Table 3: CoV across different Measures Agents Metric Regret Egalitarian Disparity SNSW 25 μrμ^r 0.060 0.055 0.055 0.058 μeμ^e 0.094 0.113 0.095 0.113 μdμ^d 0.518 0.521 0.597 0.523 μnswμ^nsw 0.062 0.061 0.061 0.062 50 μrμ^r 0.035 0.032 0.032 0.034 μeμ^e 0.082 0.093 0.082 0.092 μdμ^d 0.587 0.597 0.696 0.600 μnswμ^nsw 0.045 0.045 0.044 0.045 4.2 Observations We first consider SNSW-Alg against baselines for all 6 possible combinations of two fairness measures at a time. We observe in Figure 3 that SNSW-Alg is Pareto-undominated in such pairwise measure comparison for n=25n=25. We measure the value of Vargha-Delaney A12A^12 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.50.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. Figure 3: Pareto Undominance of SNSW-Alg against other baselines 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. 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 (n4)O(n^4) 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 (n2)O(n^2) 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) O(n^4). 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μ^nsw, coupled with stability, yields a fair outcome. We leave further theoretical investigations into its guarantees relative to other measures as future work. References Alkan and Yildiz (2022) A. Alkan and K. Yildiz Equitable stable matchings under modular assessment. Available at SSRN 4030050. Cited by: §5. Aziz et al. (2022) H. Aziz, P. Biró, and M. Yokoo Matching market design with constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 12308–12316. Cited by: §5. Barman et al. (2019) S. Barman, G. Ghalme, S. Jain, P. Kulkarni, and S. Narang Fair division of indivisible goods among strategic agents. arXiv preprint arXiv:1901.09427. Cited by: §5. Barman et al. (2022) S. Barman, A. Krishna, Y. Narahari, and S. Sadhukhan Nash welfare guarantees for fair and efficient coverage. In International Conference on Web and Internet Economics, p. 256–272. Cited by: §5. Brânzei et al. (2017) S. Brânzei, V. Gkatzelis, and R. Mehta Nash social welfare approximation for strategic agents. In Proceedings of the 2017 ACM Conference on Economics and Computation, p. 611–628. Cited by: §5. Budish and Cantillon (2009) E. Budish and E. Cantillon Strategic behavior in multi-unit assignment problems: lessons for market design. Technical report Working Paper. Cited by: §2.1. Caragiannis et al. (2019) I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation (TEAC) 7 (3), p. 1–32. Cited by: §2.2. Delacrétaz et al. (2016) D. Delacrétaz, S. D. Kominers, and A. Teytelboym Refugee resettlement. University of Oxford Department of Economics Working Paper. Cited by: §5. Dinitz (2006) Y. Dinitz Dinitz’algorithm: the original version and even’s version. In Theoretical Computer Science: Essays in Memory of Shimon Even, p. 218–240. Cited by: §1, §3.1, §3.2, 10. Gale and Shapley (1962) D. Gale and L. S. Shapley College admissions and the stability of marriage. The American mathematical monthly 69 (1), p. 9–15. Cited by: §1, §1, §2.2, §2.2, §5. Garg et al. (2025) J. Garg, Y. Tao, and L. A. Végh Approximating competitive equilibrium by nash welfare. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 2538–2559. Cited by: §5. Gusfield and Irving (1989) D. Gusfield and R. W. Irving Parametric stable marriage and minimum cuts. Information Processing Letters 30 (5), p. 255–259. Cited by: §5. Gusfield (1987) D. Gusfield Three fast algorithms for four problems in stable marriage. SIAM Journal on Computing 16 (1), p. 111–128. Cited by: §1, §2.2, §2.2, item i, §5, Definition 2. Irving et al. (1987) R. W. Irving, P. Leather, and D. Gusfield An efficient algorithm for the “optimal” stable marriage. Journal of the ACM (JACM) 34 (3), p. 532–543. Cited by: §1, §1, §2.2, §3.1, item i, §5, Definition 1, Theorem 1. Irving and Leather (1986) R. W. Irving and P. Leather The complexity of counting stable marriages. SIAM Journal on Computing 15 (3), p. 655–667. Cited by: §3.1. Irving (1985) R. W. Irving An efficient algorithm for the “stable roommates” problem. Journal of Algorithms 6 (4), p. 577–595. Cited by: §2.2, §3.1, §3.1. Jain and Vaish (2024) P. Jain and R. Vaish Maximizing nash social welfare under two-sided preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 9798–9806. Cited by: §1, §2.2, §3.1, §5. Kamiyama (2020) N. Kamiyama Popular matchings with two-sided preference lists and matroid constraints. Theoretical Computer Science 809, p. 265–276. Cited by: §5. Kaneko and Nakamura (1979) M. Kaneko and K. Nakamura The nash social welfare function. Econometrica: Journal of the Econometric Society, p. 423–435. Cited by: §2.2. Kato (1993) A. Kato Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics 10, p. 1–19. Cited by: §1, §2.2, §2.2, item i, §5, Definition 3. Knuth (1997) D. E. Knuth Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. Vol. 10, American Mathematical Society, Providence, RI. Cited by: §2.2, §2.2. Moulin (2004) H. Moulin Fair division and collective welfare. MIT press. Cited by: §2.2. Nash et al. (1950) J. F. Nash et al. The bargaining problem. Econometrica 18 (2), p. 155–162. Cited by: §2.2. Revilla (2007) P. Revilla Many-to-one matching when colleagues matter. SSRN. Cited by: §1. Roth et al. (2004) A. E. Roth, T. Sönmez, and M. U. Ünver Kidney exchange. The Quarterly journal of economics 119 (2), p. 457–488. Cited by: §1, §5. Sleator and Tarjan (1981) D. D. Sleator and R. E. Tarjan A data structure for dynamic trees. In Proceedings of the thirteenth annual ACM symposium on Theory of computing, p. 114–122. Cited by: §1, §3.1, §3.2, 10. Zou et al. (2010) J. Zou, S. Gujar, and D. Parkes Tolerable manipulability in dynamic assignment without money. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 24, p. 947–952. Cited by: item i. Appendix A Notation M Men side of market: m1,m2,…,mn\m_1,m_2,…,m_n\ W Women side of market: w1,w2,…,wn\w_1,w_2,…,w_n\ n Number of men and women ∣M∣=∣W∣=n M = W =n N Set of all men and women: M∪WM∪ W r(a,b)r(a,b) Rank of agent b in ≻a _a ur(mi,wj)ur(m_i,w_j) Utility of man mim_i on match with woman wjw_j ur(wk,ml)ur(w_k,m_l) Utility of woman wkw_k on match with man mlm_l ℳM Any stable matching between M and W ℳoM^o Man-optimal stable matching ℳzM^z Woman-optimal stable matching ℳrM^r Min-Regret stable matching ℳeM^e Egalitarian stable matching ℳdM^d Sex-equal stable matching ℳnswM^nsw Nash optimal matching ℳsnswM^snsw Nash stable matching Appendix B Experimental Evaluations Figure 4: Circular Plot for Uniform Distribution Figure 5: Circular Plot for Triangular Distribution Figure 6: Circular Plot for Normal Distribution Figure 7: Circular Plot for Uniform Default Distribution