# Fair Stable Matching Meets Correlated Preferences

Angelina Brilliantova
Rochester Institute of Technology
Rochester, NY, USA
<EMAIL_ADDRESS>Hadi Hosseini
Pennsylvania State University
University Park, PA, USA
<EMAIL_ADDRESS>
###### Abstract

The stable matching problem sets the economic foundation of several practical
applications ranging from school choice and medical residency to ridesharing
and refugee placement. It is concerned with finding a matching between two
disjoint sets of agents wherein no pair of agents prefer each other to their
matched partners. The Deferred Acceptance (DA) algorithm is an elegant
procedure that guarantees a stable matching for any input; however, its
outcome may be unfair as it always favors one side by returning a matching
that is optimal for one side (say men) and pessimal for the other side (say
women). A desirable fairness notion is minimizing the sex-equality cost, i.e.
the difference between the total rankings of both sides. Computing such stable
matchings is a strongly NP-hard problem, which raises the question of what
tractable algorithms to adopt in practice. We conduct a series of empirical
evaluations on the properties of sex-equal stable matchings when preferences
of agents on both sides are correlated. Our empirical results suggest that
under correlated preferences, the DA algorithm returns stable matchings with
low sex-equality cost, which further confirms its broad use in many practical
applications.

##  1 Introduction

Matching theory sets the economic foundation for achieving stable allocations
through market design. It has shaped the cornerstone of many practical
applications ranging from school choice [4, 2] and medical residency [62, 64]
to refugee placement [19, 38] and ridesharing [28, 9]. In its essence, the
stable matching problem deals with finding a matching between two disjoint
sets of agents (colloquially men and women) according to their preferences.
The primary objective is to achieve stability, that is, finding a matching
between the two sides wherein no pair of agents prefer each other to their
matched partners.

Over the past few decades, numerous theoretical breakthroughs and developments
were pioneered to study mathematical and axiomatic properties of the stable
matching problem [61, 69, 20, 24] as well as its computational and algorithmic
aspects [72, 30, 40, 45, 67]. However as problems become increasingly more
challenging, there has been a need for moving from theory about simple markets
to more complex settings that account for subtle, but vital, differences in
constraints in preference structures or other factors that may pose
computational or axiomatic challenges. Hence, as Roth and Peranson [64]
suggested “as game theory moves from simple conceptual problems to complex
design problems, we will need to make more general use of this interaction
among theory, computational investigation of market data, and theoretical
computation, and that this in turn will produce new problems and directions
for traditional theory”. This doctrine motivated a large body of work in
taking empirical or statistical approaches in exploring markets through
studying (real or synthetic) data sets or analyzing statistical distributions
[6, 44, 13, 71].

In this vein, we investigate the fairness of stable matchings through
empirical simulations to paint a thorough picture of the structure of fair
stable solutions in matching markets.

#### A motivating insight

The Deferred Acceptance algorithm (DA)—due to Gale and Shapley [23]—provides
an elegant solution to the stable matching problem wherein agents from one
side (say men) make proposals to the agents from the other side (say women).
Each woman tentatively accepts her favorite proposal and rejects the rest.
Despite the popularity and success of the DA algorithm in many real-world
matching markets [64, 61], it always favors the proposing side to the
receiving side, that is, the DA algorithm always returns a stable matching
that is _men-optimal_ [23] but _women-pessimal_ [54]. This unequal treatment
of the sides raises critical questions about the fairness of the DA algorithm,
which may result in (extremely) unequal welfare between both sides.

One of the most prominent and well-studied fairness notions—proposed by
Gusfield and Irving [27]—is _sex-equality_ that aims at finding a matching
that equalizes the welfare of both sides by minimizing the difference between
the total rankings of men and women in a stable matching. While sex-equal
stable matchings always exist, computing one has shown to be strongly NP-hard
[40]. For any instance of the matching problem, there may be an exponential
number of stable solutions [35] and these stable matchings form a distributive
lattice. Thus, one may hope to find a “fair” stable matching that equalizes
the welfare of both sides.

On a closer scrutiny, however, we notice that a sex-equal stable matching is
highly correlated with the structure of preference lists of each side of the
market. This observation suggests that even though the number of stable
matchings grows exponentially in general [35], surprisingly a sex-equal
solution lies at the extreme points of the stable lattice in certain settings.

######  Example 1.1.

Consider the following instance with five men and five women and the following
preference lists.

$m_{1}\colon$ |  $w_{2}^{\dagger}$ |  $w_{4}^{*}$ |  $w_{5}$ |  $w_{1}$ |  $w_{3}$ |  |  $w_{1}\colon$ |  $m_{4}$ |  $m_{2}$ |  $m_{1}$ |  $m_{5}^{*}$ |  $m_{3}^{\dagger}$
---|---|---|---|---|---|---|---|---|---|---|---|---
$m_{2}\colon$ |  $w_{3}^{\dagger}$ |  $w_{2}^{*}$ |  $w_{4}$ |  $w_{1}$ |  $w_{5}$ |  |  $w_{2}\colon$ |  $m_{2}^{*}$ |  $m_{4}$ |  $m_{1}^{\dagger}$ |  $m_{5}$ |  $m_{3}$
$m_{3}\colon$ |  $w_{1}^{\dagger}$ |  $w_{5}^{*}$ |  $w_{4}$ |  $w_{3}$ |  $w_{2}$ |  |  $w_{3}\colon$ |  $m_{4}^{*}$ |  $m_{2}^{\dagger}$ |  $m_{1}$ |  $m_{3}$ |  $m_{5}$
$m_{4}\colon$ |  $w_{4}^{\dagger}$ |  $w_{2}$ |  $w_{3}^{*}$ |  $w_{1}$ |  $w_{5}$ |  |  $w_{4}\colon$ |  $m_{2}$ |  $m_{1}^{*}$ |  $m_{4}^{\dagger}$ |  $m_{5}$ |  $m_{3}$
$m_{5}\colon$ |  $w_{2}$ |  $w_{3}$ |  $w_{5}^{\dagger}$ |  $w_{1}^{*}$ |  $w_{4}$ |  |  $w_{5}\colon$ |  $m_{1}$ |  $m_{4}$ |  $m_{2}$ |  $m_{3}^{*}$ |  $m_{5}^{\dagger}$
$\mu^{M}$$(w_{2},w_{3},w_{1},w_{4},w_{5})$, Men-
optimal$\mu_{1}$$(w_{4},w_{3},w_{1},w_{2},w_{5})$$\mu_{2}$$(w_{2},w_{3},w_{5},w_{4},w_{1})$$\mu_{3}$$(w_{4},w_{2},w_{1},w_{3},w_{5})$$\mu_{4}$$(w_{4},w_{3},w_{5},w_{2},w_{1})$$\mu^{W}$$(w_{4},w_{2},w_{5},w_{3},w_{1})$,
Women-optimal (Sex-
equal)$\rho_{1}$$\rho_{3}$$\rho_{2}$$\rho_{3}$$\rho_{2}$$\rho_{1}$$\rho_{3}$
Figure 1: The stable lattice for the profile described in Example 1.1 with six
stable solutions. Matchings are denoted as lists of women matched to men
according to their indices, rotations are indicated by $\rho_{x}$ on arcs.

The men-optimal and women-optimal matchings are marked by $\dagger$ and $\ast$
respectively. The stable lattice of this preference profile contains five
matchings as illustrated in Figure 1. A sex-equal stable matching assigns a
total ranking of 12 to women and 13 to men, minimizing the welfare difference
between the two sides. Notice that the sex-equal solution for this profile
lies precisely on the extreme point of the stable lattice and is equivalent to
the women-optimal solution.111We refer the readers to Appendix A for details
of lattices and rotations. ∎

Motivated by this observation, we study stable matching problems when both
sides of the market have correlated preference lists. We focus on correlated
random preference lists sampled from _Mallows distribution models_ [50, 51].
The Mallows model is the cornerstone of a variety of ranking problems in
machine learning [75, 8, 49] and social choice [34], and has been shown to
correctly capture the preference rankings of individuals in many practical
applications [15, 68]. Under the Mallows models, preferences are correlated
through a reference ranking, where the probability of a preference list to be
sampled is inversely proportional to its Kendall-tau distance [41, 42] (number
of swaps between the two lists) from the reference ranking. Therefore,
focusing on settings with correlated preference lists on both sides of the
market we ask the following questions:

> _How does the correlation between preference lists of two sides impact the
> fairness of stable matchings? What algorithmic solutions should we adopt in
> practice when preferences are correlated according to Mallows models?_

###  1.1 Our Results

Focusing on markets with correlated preferences on both sides, we empirically
investigate the sex-equality of stable matchings through a series of extensive
experiments on synthetic data:

  * •

Stable lattice: We first focus on the size of the stable lattice when
preferences of both sides are drawn from Mallows distributions. We show that
the size of the stable lattice is heavily dependent on the relationship
between the correlation intensity in preferences of two sides (Section 3). In
particular, we show that when correlations between the two sides of the market
are symmetric, that is, preferences are distributed according to the same
dispersion parameter, the stable lattice grows rapidly–as it was theoretically
proved by Levy [48]. However, when correlations are asymmetric, i.e.
distributed according to different dispersion parameters, the size of the
stable lattice sharply decreases.

  * •

Asymmetric correlations: When preferences of the two sides are sampled from
different Mallows distributions, we show that in overwhelming majority of
cases, a sex-equal stable matching is located at the extreme points of the
stable lattice. In Section 4.1 we discuss how this key observation immediately
results in a polynomial-time algorithm for finding a sex-equal matching by
computing a men-optimal or women-optimal stable matching through the DA
algorithm [23].

  * •

Symmetric correlations: When preferences are sampled from the same Mallows
distribution, even though the size of the stable lattice may be exponential,
the cost of a sex-equal matching is considerably close to the cost of the DA
outcome. As the difference between the welfare of men and women is
sufficiently small, the importance of which group proposes (men or women)
becomes negligible (Section 4.2).

  * •

Comparing the performance of algorithms: In Section 5 we conduct a series of
empirical comparisons between well-studied heuristic and procedurally fair
algorithms. We show that with correlated preferences, the DA algorithm—with a
careful selection of the proposing side—performs as good as the best known
local search algorithm with respect to the sex-equality cost even on large
instances. This result further justifies the use of the DA algorithm which is
more computationally efficient compared to other methods.

###  1.2 Related Work

Stability is a key condition for the success and longevity of two-sided
markets [63]. The seminal work by Gale and Shapley showed that a stable
matching always exists and can be found in polynomial time using the Deferred
Acceptance algorithm (DA) [23]. The important property of DA is inherent
asymmetry: favouring one side at the cost of another [27]. The inherent bias
of DA should be taken into account as many central clearinghouses use it as
the basis for their matching procedures, including the National Resident
Matching Program (NRMP) [64] and the New York City school assignment [3].

Several papers investigate the difference between the expected rank of
partners in an optimal and a pessimal stable matching (aka the welfare gap)
[6, 7, 59, 58]. In one-to-one balanced markets (i.e. with an equal number of
men and women) and when preferences drawn uniformly at random, the expected
total rank of agents asymptotically approaches $n\log n$ in their optimal
matching and $n^{2}/\log n$ in their pessimal matching [58]. The same order of
scores is preserved in markets with constant tier-based preferences, in which
agents rank partners proportionally to their real-numbered popularity scores
[7].

Large real-world markets usually admit an exceedingly small number of stable
matchings. For example, for the NRMP hospital-resident matching and for Boston
Public School student admission there were only a couple of stable matchings
each year [64, 57]. It was shown theoretically, that a lattice becomes
essentially a singleton in large one-to-one markets, in which one side draws
shorter fixed-sized preference lists from an arbitrary distribution [32].
Similar results were demonstrated for many-to-one settings: balanced [46] and
unbalanced [6]. At the same time, large stable lattices were theoretically
proven in markets with correlated preferences induced by the Watts–Strogatz
“small world” model (even when unbalanced) [59], and the Mallows model [48].
Empirically, large lattices are found in settings of matching-with-contracts
[29].

#### Fairness and stability.

The potential exponential size of stable solutions [35] alongside the inherent
bias of DA, has motivated the discussion of fairness in stable matching
markets. Various algorithms were proposed to ensure fairness towards
individuals [22, 21], socio-economic groups [1, 31, 56], regions [39], and
sides (e.g. hospitals vs. residents) [70, 53, 60]. Below, we will briefly
discuss a variety of fairness notions that have received attention in the
literature of stable matchings.

The egalitarian stable matching, is a stable matching that minimizes the sum
of rankings of all partners for men and women, hence maximizes the total
welfare of all agents [36]. The minimum regret stable matching minimizes the
highest rank of agents, therefore minimizing the rank of a partner for the
most unsatisfied agent. Egalitarian and minimum regret stable matchings can be
found in polynominal time [36, 21], but do no ensure cross-sided fairness:
they both can substantially favor one of the sides, by optimizing the welfare
on the level of the whole system (egalitarian), and individual agents (minimum
regret). In the median stable matching, each agent is matched to its middle
favorite partner across all partners from stable matchings; the resulting
matching is a median element of a stable lattice. Finding a median stable
matching is NP-hard in general, but it could be done in polynomial time in
some restricted families of the rotation poset [17]. The median stable
matching might not satisfy cross-sided fairness if one side prefers their
middle stable partners substantially more than the other side. A procedurally
fair algorithm aims to provide agents an equal probability to affect the
resultant stable matching by issuing proposals [71], reducing the set of
stable matchings [5], or satisfying blocking pairs [65]. Procedural fairness
does not necessarily result in cross-sided fair matchings, and thus, one side
may receive much higher welfare compare to the other side [43].

A sex-equal stable matching minimizes the gap between the sum of partners’
ranks of men and women. The sex-equal stable matching problem is an NP-hard
problem and fixed parameter tractable with respect to the treewidth of the
Hasse diagram of the rotation poset [25] and $k$ parameter in the $k$-range
model [18]. To tackle the sex-equal stable matching problem various heuristics
have been proposed: for example, performing local search series on a stable
lattice (iBILS) [74], and transforming a stable matching using genetic
algorithm [55]. While some of these approximate algorithms (e.g. iBILS)
perform well in experiments, they bear no theoretical bounds on the quality of
an outcome.

#### Correlated and random preferences.

Several recent works in stable matching have focused on investigating a
variety of natural structures of profiles, from profiles generated uniformly
at random [6, 58] to random profiles with soft and hard constraints on
rankings [44, 71, 7]. The Mallows distribution model drew the attention of
researchers as it was shown to realistically capture the preference of agents
in several applications involving individual decision-makers [68]. In the
Mallows model, preferences are correlated through a reference ranking,
representing the objective order of agents’ attractiveness. In contrast to the
tiered and random utility models, the Mallows model generates a variety of
correlated preferences using only a few parameters: two dispersion parameters
and two reference rankings; one of each for each side of the market.

##  2 Preliminaries

We start by providing a formal representation of the model and define the
necessary properties.

##### Problem setup.

An instance of the _stable matching problem_ is specified by the tuple
$I=\langle M,W,\succ\rangle$, where $M$ is a set of $n$ men, $W$ is a set of
$n$ women, and $\succ$ is a preference profile which consists of the
preference lists of all men and women. The preference list of any man $m\in
M$, denoted by $\succ_{m}$, is a strict total order over all women in $W$ (for
any woman $w\in W$, the list $\succ_{w}$ is defined analogously). The rank of
woman $w$ in man $m$’s preference list, $\succ_{m}$, is denoted by $r(w,m)$.
For instance, given $\succ_{m}=(w_{2},w_{1},w_{3})$, we say $w_{2}$ is ranked
first in $m$’s preference list, i.e., $r(w_{2},m)=1$. Similarly, $r(m,w)$
denotes the rank of $m$ in $\succ_{w}$.

##### Stable matchings.

A perfect _matching_ is a mapping $\mu:M\cup W\rightarrow M\cup W$ such that
$\mu(m)\in W$ for all $m\in M$, $\mu(w)\in M$ for all $w\in W$, and $\mu(m)=w$
if and only if $\mu(w)=m$. Given a matching $\mu$, a man-woman pair $(m,w)$ is
called a blocking pair, with respect to the preference profile $\succ$, if
they prefer each other to their assigned partners under $\mu$, i.e.,
$w\succ_{m}\mu(m)$ and $m\succ_{w}\mu(w)$. A matching is stable if it contains
no blocking pairs.

Given a preference profile $\succ$, the set of all corresponding stable
matchings, $S_{\succ}$, forms a _distributive lattice_.222See Appendix A for a
detailed explanation of the distributive lattice and an example. The maximum
and minimum points of a stable lattice correspond to the men-optimal
($\mu^{M})$ and the women-optimal ($\mu^{W}$) matchings respectively [27],
i.e. a matching where all men (respectively women) receive their best stable
partners. A men-optimal matching is simultaneously women-pessimal: it matches
all woman to their worst stable partners [54]. Figure 1 illustrates a lattice
consisting of six stable matchings. The expected size of a stable lattice
(correspondingly the size of $S_{\succ}$) is asymptotic to $e^{-1}\ln n$ when
preferences are drawn uniformly at random [58] and may grow exponentially with
the number of agents [35].

##### Welfare measure.

Let $S_{M}(\mu)$ denote the sum of ranks of men’s partners in matching $\mu$,
that is, $S_{M}(\mu)=\sum_{m\in M}r(\mu(m),m)$. Similarly for women, we let
$S_{W}(\mu)$ be the sum of ranks of women’s partners given matching $\mu$,
i.e. $S_{W}(\mu)=\sum_{w\in W}r(\mu(w),w)$. Note that the smaller values
indicate higher social welfare. Thus, a men-optimal matching $\mu^{M}$ is the
one that minimizes the sum of rankings for men, that is,
$\mu^{M}=\arg\min_{\mu\in S_{\succ}}S_{M}(\mu)$. And similarly, for the women-
optimal matching we have $\mu^{W}=\arg\min_{\mu\in S_{\succ}}S_{W}(\mu)$. For
simplicity, we will refer to the scores of a men-optimal matching
$S_{M}(\mu^{M})$, $S_{W}(\mu^{M})$ as $S_{M}$-optimal and $S_{W}$-pessimal
scores. Similarly, for a women-optimal matching we write $S_{M}$-pessimal and
$S_{W}$-optimal to indicate $S_{M}(\mu^{W})$ and $S_{W}(\mu^{W})$.

##### The Deferred Acceptance algorithm.

Given a preference profile $\succ$, the Deferred Acceptance (DA) algorithm,
proposed by Gale and Shapley [23], consists of rounds of _proposal_ and
_rejection_ phases and proceeds as follows: In each round every man who is
currently unmatched proposes to his favorite woman from among those who have
not rejected him yet. Each woman tentatively accepts her favorite proposal and
rejects the rest. The algorithm terminates in $\mathcal{O}(n^{2})$ when no
further proposals can be made.

Given any profile $\succ$ as input, the DA algorithm is guaranteed to return a
stable matching [23]. Moreover, the DA algorithm is simultaneously _men-
optimal_ [23] and _women-pessimal_ [54], i.e. men receive their favorite
stable partners among all matchings available to them in $S_{\succ}$, and
women receive their least favorite stable partners. The DA algorithm returns
the stable matchings at the extreme points of the stable lattice depending on
which set (men or women) are proposers. Thus, the DA algorithm with women
proposing is respectively women-optimal and men-pessimal.

###  2.1 Fair Stable Matchings

Given a matching $\mu$, the sex-equality cost of $\mu$ is the absolute
difference between the total welfare of men and women, i.e. $S_{M}$ and
$S_{W}$ scores. Formally, the sex-equality cost of a matching $\mu$ is defined
as

$c(\mu)=|S_{M}(\mu)-S_{W}(\mu))|.$ (1)

Given preference profile $\succ$, a _sex-equal stable matching_ is a matching
in $S_{\succ}$ that minimizes the sex-equality cost across the stable lattice,
that is,

$\mu^{*}\leftarrow\arg\min_{\mu\in S_{\succ}}(c(\mu)).$ (2)

Intuitively, in a sex-equal stable matching the total rank of men’s partners
is as close as possible to that of women (subject to the stability condition).
Kato [40] showed that for an arbitrary preference profile the problem of
finding a sex-equal stable matching is strongly NP-hard. However, it is fixed
parameter tractable with respect to the range of the profile – a metric
showing the maximum discrepancy between an agent’s worst and best rank in the
preference profile [18]. Also, it can be found efficiently when agents have a
specific two-dimensional single-peaked model [66] or if preferences are
identical on one side [37].

###  2.2 Correlated Preferences

There are several plausible ways to study preference models generated from
uniform distributions [58, 6] or correlated preferences [7, 10, 71, 59]. The
vast majority of these works focused on profiles wherein the preferences of
one side are correlated while the other side is considered uniform. We focus
on a more general distribution models where both sides of the market have
correlated preferences through the Mallows model.

##### The Mallows model

A Mallows distribution is a distance-based probabilistic model for
permutations correlated with some common reference [50]. It is parameterized
by a reference ranking, $\hat{\pi}$, and a dispersion parameter
$\phi\in(0,1]$. Let $\pi$ be a permutation of a preference list. For any
permutation $\pi$, the Mallows model specifies a probability as follows:

$p(\pi|\hat{\pi},\phi)=\frac{1}{Z}\phi^{\tau(\pi,\hat{\pi})}$

where $\tau(\pi,\hat{\pi})$ is a Kendall-tau distance (the number of pairwise
inversions) between $\pi$ and $\hat{\pi}$ and $Z$ is a normalization constant
with $Z=1(1+\phi)(1+\phi+\phi^{2})\ldots(1+\phi+\ldots+\phi^{n-1})$.

Note that the dispersion parameter $\phi$ indicates the ‘intensity’ of
correlation between the sampled preferences. When $\phi=0$, the correlation is
maximal, that is, the distribution mass is entirely on the reference ranking
and all preference lists are identical. When $\phi=1$, the correlation is
minimal, the probability mass is distributed evenly between all possible
permutations and the Mallows model is equivalent to the Uniform distribution
model (also known as _Impartial Culture_ [12] in the computational social
choice literature).

For each set involved in the stable matching problem, we consider an
independent probabilistic preference model: one Mallows model for the set of
men parameterized by $\hat{\pi}_{m}$ and $\phi_{m}$ and another preference
model for women specified by $\hat{\pi}_{w}$ and $\phi_{w}$. In this way, the
preferences of men (similarly women) are globally correlated with
$\hat{\pi}_{m}$ ($\hat{\pi}_{w}$).333Throughout the paper, we assume
$\hat{\pi}_{m}=\hat{\pi}_{w}$, because one can simply relabel the preferences
on one side to create any arbitrary distance.

##### Symmetric and asymmetric models.

We let $\phi_{\Delta}=|\phi_{m}-\phi_{w}|$ to represent the correlation
disparity in preferences of men and women sampled for this particular
instance. Simply put, correlation disparity reflects how similar the
probabilistic preferences of men are in comparison to the similarity of
women’s preferences. We call stable matching instances simulated from the
Mallows model with zero correlation disparity, $\phi_{\Delta}=0$, symmetric
correlation markets, and asymmetric correlation markets when simulated with
$\phi_{\Delta}\neq 0$.

##  3 Stable Lattice under the Mallows model

In this section, we show empirically that in one-to-one markets with
correlated preferences induced by Mallows models the size of the stable
lattice depends on the correlation disparity. The empirical investigations
give insights on how searching for a sex-equal matching can computationally
vary with the size of a stable lattice in a given market.444The source code is
available at https://github.com/Restel/mallows-smp

###  3.1 Setup and Preference Sampling

We generate $1,000$ instances of a stable matching problem for each
$n\in[10,150]$ and $\phi_{m},\phi_{w}$ in $[0.1,1.0]$. When generating a
preference profile under probabilistic models, we draw a preference list for
each agent i.i.d from the Mallows distribution using the sampler from PrefLib
library [52].

In all sampled stable matching instances we built the stable lattice, and
measured $S_{M}$, $S_{W}$ welfare scores. For each experimental setting, we
estimate a target statistic (the median for numerical variables like size and
mean for binary variables) over $1,000$ instances along with the confidence
intervals. Confidence intervals were obtained using bootstrap sampling with
replacement with sample size $1,000$ with $100$ repeats. We report the results
only for $n=150$, as for the smaller $n$ the results are qualitatively the
same. We occasionally considered larger instances with $n=300$, when comparing
the size of the lattice of the Uniform and the Mallows
($\phi_{m}=\phi_{w}=0.5$) models.555We use the same instance generation and
setup in all remaining sections.

###  3.2 The Size of the Stable Lattice

#### The size of the stable lattice depends on the correlation disparity

Our empirical investigation illustrates an intriguing observation about the
size of the stable lattice: Under the Mallows model the size of the stable
lattice is affected by the correlation intensity in men’s and women’s
preferences (measured by the dispersion parameters $\phi_{m}$, $\phi_{w}$) as
well as the discrepancy between them, i.e. the correlation disparity
$\phi_{\Delta}$. The size of the lattice is maximum when the preferences of
men and women are sampled from a distribution with identical dispersion
parameters, $\phi_{\Delta}=0$, and decreases with the rise of the correlation
disparity. This relationship is confirmed by median values, 25%-75%
percentiles, 95% confidence intervals, maximum values and holds for all
combinations of dispersion parameters (Figure 2). These findings are aligned
with theoretical results indicating that when the preferences are sampled from
the same distribution (parametrized by identical dispersion parameters,
$\phi_{m}=\phi_{w}$), the size of the stable lattice grows exponentially in
the number of agents [48], making the use of an exhaustive search algorithm
impractical in these settings.

More importantly, they reveal that the primary predictor of the lattice size
is the correlation disparity between the two sides, and the intensity of the
correlations (dispersion parameters) have less significant impact on the
lattice size.666Similar results hold for rotation posets as we discuss in
Appendix B.

| n | Type |  Median $\mathcal{L}$ |  CI($\mathcal{L}$) |  max($\mathcal{L}$)
---|---|---|---|---|---
1 | 150 | Mallows | 16.00 | (2;256) | 1024
3 | 150 | Uniform | 82.00 | (32;231) | 626
4 | 300 | Mallows | 144.00 | (8;7008) | 147456
5 | 300 | Uniform | 209.00 | (91;567) | 1262
Table 1: The size of the stable lattice ($\mathcal{L}$) under the Uniform, and
the Mallows distributions with $\phi_{m}=\phi_{w}=0.5$ models.
$CI(\mathcal{L})$ denotes the 95% confidence interval.

#### Mallows preferences induce large lattices

It is thought that introducing correlation in preferences reduces the stable
lattice size compared to the random uncorrelated case [64, 6, 47]. In their
empirical work, Roth and Peranson [64] conjectured that having a common
objective ranking for the agents’ preferences is one of the main reason behind
the observed small lattice sizes. Our empirical results suggest that while in
general the median size of the lattice was indeed smaller in the Mallows
compared to the Uniform distribution, some $\phi$ parameters have much larger
maximum values and confidence intervals.777See Table 4 in Appendix B for
details. For example, in case of asymmetric correlation with $\phi_{m}=0.5$,
$\phi_{w}=0.3$, $n=150$, the maximum size of the lattice was larger than that
of the Uniform model. Similarly, for symmetric case with $\phi_{m}=0.5$,
$\phi_{w}=0.5$, and $n=300$, 95% confidence interval of a stable lattice size
spans from $8$ to $7008$ matchings compared to $91$–$567$ interval under the
Uniform distribution (see Table 1).

Figure 2: The size of the stable lattice with respect to $\phi_{m}-\phi_{w}$
in the Mallows model for $n=150$: median values (left), maximum values
(right). Dotted lines denote the medians, shadowed gray area denotes 1st and
3rd quartiles. Y-axes of left and right figures have different scales.

Our results suggest that symmetrically correlated markets have extraordinarily
large lattices compared to the Uniform case ($147456$ vs. $1262$), aligning
well with the results of Levy [48] on asymptotic exponential lattices in the
Mallow model. Note, that such large instances appeared for such small number
of agents as $300$, while real-world markets often have many more agents [64,
57].

In the past, correlation in preferences of agents was considered a sole factor
contributing to small lattice sizes [64, 6]. Our experiments imply that in
case of the correlation induced by the Mallows model, this effect depends not
on the presence of correlation itself, but rather on its disparity between the
two sides i.e. how strongly the preferences of one set are correlated compared
to the preferences of the other set. Symmetric correlation markets seem to be
the worst case scenario, and the lattice tends to grow smaller when the sets
are having preferences correlated dissimilarly. This raises the question of
whether real-world markets with observed small lattices suffer from such
correlation disparity in preference profiles or it should be attributed to
other factors.

Figure 3: The fraction of instances where a sex-equal solution is an outcome
of DA algorithm for $n=150$: women proposing if $\phi_{m}<\phi_{w}$, men-
proposing if $\phi_{m}>\phi_{w}$, any side proposing if $\phi_{m}=\phi_{w}$.
Confidence intervals are given in parentheses.

Figure 4: The median sex-equality cost of a DA solution with respect to
$\phi_{m}$, $\phi_{w}$, for $n=150$. Confidence intervals are given in
parentheses.

##  4 Sex-Equal Stable Matchings

In this section, we discuss how the position of a sex-equal matching within a
stable lattice is determined by the relationship between men and women welfare
scores, which enables us to find a sex-equal matching using the DA algorithm.

The relationship between $S_{M}$ and $S_{W}$ of men- and women-optimal stable
matchings dictates the location of a sex-equal solution within the lattice. In
particular, it determines whether or not it lies on the extreme points of the
lattice. Based on this relationship, we identify two “easy” cases, in which DA
guarantees to return a sex-equal stable matching, and a “hard” case, in which
it does not.

######  Lemma 1 (Kato [40]).

A sex-equal stable matching is:
1) the men-optimal stable matching, $\mu^{M}$, if $S_{M}(\mu^{M})\geq
S_{W}(\mu^{M})$
2) the women-optimal matching, $\mu^{W}$, if $S_{M}(\mu^{W})\leq
S_{W}(\mu^{W})$
3) the stable matching $\mu_{Z}$ such that $c(\mu_{Z})=\arg\min_{\mu\in
S_{\succ}}(c(\mu))$, otherwise.

######  Corollary 1.

A sex-equal stable matching can be computed in polynomial time when either
$S_{M}(\mu^{M})\geq S_{W}(\mu^{M})$ or $S_{M}(\mu^{W})\leq S_{W}(\mu^{W})$.

###### Proof.

Find a men-optimal matching $\mu^{M}$ by running a men-proposing DA algorithm.
Compute $S_{M}(\mu^{M})$ and $S_{W}(\mu^{M})$ and if $S_{M}(\mu^{M})\geq
S_{W}(\mu^{M})$, than by Lemma 1, Case 1 the men-optimal matching is a sex-
equal stable matching. Analogously, find a women-optimal matching $\mu^{W}$ by
running a women-proposing DA algorithm. Compute $S_{M}(\mu^{W})$ and
$S_{W}(\mu^{W})$ and if $S_{M}(\mu^{W})\leq S_{W}(\mu^{W})$, than by Lemma 1,
Case 2 the women-optimal matching is a sex-equal stable solution. The running
time of DA and calculating $S_{M}$, $S_{W}$ scores is $\mathcal{O}(n^{2})$.
Thus, a sex-equal stable matching can be found in polynomial time when
$S_{M}(\mu^{M})\geq S_{W}(\mu^{M})$ or $S_{M}(\mu^{W})\leq S_{W}(\mu^{W})$. ∎

In the first and the second cases of Lemma 1, the sign of the difference
between the scores $S_{M}(\mu)-S_{W}(\mu)$ is preserved across the lattice, in
other words $S_{M}(\mu)$ is either always greater or equal than $S_{W}(\mu)$
(Case 1), or smaller or equal than $S_{W}(\mu)$ (Case 2). The third case
corresponds to the instances, in which the sign of $S_{M}(\mu)-S_{W}(\mu)$
changes across the lattice, and the location of the sex-equal matching within
the lattice is not known a priori.

###  4.1 Asymmetric Markets ($\phi_{m}\neq\phi_{w}$)

When preferences of men and women have different levels of correlation
intensity with the reference rankings, a sex-equal stable matching is often
found on an extreme point of the stable lattice: men-optimal in case men have
higher correlation and women-optimal otherwise. Empirically, we observe this
behavior in all instances, including the largest stable lattices with up to
$1024$ matchings (Figure 4). We found that agents from the side with a smaller
dispersion parameter $\phi$ of the Mallows model, are less satisfied with
their optimal matching than their partners with their pessimal one (and the
market belongs to Case 1 or Case 2 scenario from Lemma 1). This fact might
imply that, in asymmetric correlation markets, “hard” cases rarely occur and
the DA algorithm can be considered a fair alternative to the exhaustive
search, especially since such markets can induce large lattices as shown in
Section 3.

Experimentally, in every stable matching instance belonging to an asymmetric
correlation market with $\phi_{m}<\phi_{w}$, $S_{M}$-optimal was larger than
$S_{W}$-pessimal, and therefore a men-optimal matching is sex-equal (Lemma 1,
Case 1). Similarly, whenever $\phi_{m}>\phi_{w}$, $S_{W}$-optimal was larger
than $S_{M}$-pessimal, rendering the women-optimal matching sex-equal (Lemma
1, Case 2). This is well illustrated by the distribution of $S_{M}$ and
$S_{W}$ scores of men- and women-optimal matchings for various combinations of
$\phi_{m}$, $\phi_{w}$. Figure 5 illustrates this relationship when men sample
their preferences with $\phi_{m}=0.9$, and women have their dispersion
parameter in range $[0.1,1.0]$ (the graphs for other values of $\phi_{m}$ are
analogous). In the part of the graph, where women’s preferences have a lower
dispersion parameter $\phi_{w}<\phi_{m}$, the distribution of $S_{W}$-scores
of a women-optimal matching lies strictly above the distribution of its
$S_{M}$-scores with no overlap.888A more fine-grained analysis with
$\phi_{w}\in\\{0.9,0.91,0.92,\ldots,0.99\\}$ confirms the same finding (see
Appendix C).

Figure 5: Illustrating $S_{M}$, $S_{W}$ scores under the Mallows model with
$\phi_{m}=0.9$ and varying $\phi_{w}$ based on 1000 samples.

#### Implications on the DA algorithm.

Interestingly, increasing the variability of women’s preferences, results in
1) higher welfare for women in optimal and pessimal matchings and 2) a higher
number of proposals from men. The total number of proposals in the DA
algorithm corresponds to the optimal score of the proposing side [58]. In
Figure 5 we can see a noticeable increase in the $S_{M}$-scores with the
increase of $\phi_{w}$ as well as a decrease in $S_{W}$ scores (same pattern
occurs for other values of $\phi_{m}$). Imagine that the proposing side
samples its preferences from the model with a smaller dispersion parameter,
and hence has less variable preferences and demonstrates a higher competition
for partners (than the opposite side). Intuitively, during the course of DA
those agents would propose to the same set of partners over and over again and
their potential partners get to choose from a diverse set of proposals, which
improves the rank of their matches. This makes the total rank of proposers’
partners greater than that of the agents from the accepting side. This fact
distinguishes the Mallows model from the Uniform model in which the proposing
side gets a substantially smaller score than the accepting side [58].

###  4.2 Symmetric Markets ($\phi_{m}=\phi_{w}$)

When the preferences of men and women have the same intensity of correlation,
reflected in zero correlation disparity, the lattice size can quickly become
very large. The size of the stable lattice is expected to be asymptotically
exponential [48], which is confirmed in our experiments: even for small number
of agents as $n=300$, there were significantly large (compared to the Uniform
model) lattices with up to $147456$ matchings (Table 1). Despite the large
size of the stable lattice, the cost of a sex-equal solution is considerably
close to the cost of DA outcomes (Figure 4). In this case, the DA algorithm
can be considered cost-effective as the exhaustive search takes significantly
more time for large lattices and gives only a moderate gain in the sex-
equality cost.

We discussed in Section 4.1, that under the Mallows model, $S_{M}$-optimal and
$S_{W}$-pessimal scores (similarly $S_{W}$-optimal, $S_{M}$-pessimal) are
close to each other and their distributions overlap significantly. This can
explain the small sex-equality cost of DA outcomes (see Figure 5). It could
indicate, that under this scenario, the expected score of the proposing side
under DA is similar to the expected score of the receivers. This finding
differs sharply from the Uniform model wherein the expected pessimal score is
substantially greater than the optimal one [58, 7]. As the difference between
the welfare of men and women is sufficiently small, the importance of which
group proposes (men or women) in DA becomes negligible. Hence, not only can
the DA algorithm be adopted to ensure sex-equality, but it may also provide a
natural framework for achieving procedural fairness as it has recently been
studied [71, 70].

###  4.3 Implications on manipulation strategies

In our experiments, the Mallows model with symmetric and asymmetric
correlations results in a considerably small difference between the pessimal
and the optimal scores for one side (the welfare gap), for example, between
$S_{W}$ pessimal and $S_{W}$-optimal (Figure 5). This difference represents
how much on average an agent can improve by shifting from her worst stable
partner to her best one, and therefore has implications on manipulation
incentives [6, 59]. Since the welfare gap is small for both men and women, in
symmetric and asymmetric correlation settings, the accepting side has a
limited scope/incentive for manipulations in practice. This observation
suggests that one-to-one markets with Mallows preferences might be less
susceptible to manipulation compared to the Uniform model, for which a larger
welfare gap, and subsequently, higher incentive for manipulation has been
established [58] and shown empirically [69, 30].

Figure 6: Mallows model (symmetric): comparing the sex-equality cost of
various matching algorithms when $\phi_{m}=\phi_{w}=0.5$. Subscript 0
indicates that men start proposing first, and 1 indicates women propose first.
Figure 7: Mallows model (asymmetric): the sex-equality cost of iBILS and a
pre-processed Deferred Acceptance (DA*) for an asymmetric correlation market
with $\phi_{m}=0.5$, $\phi_{w}=0.7$.

##  5 Comparing with Other Algorithms

We compare the DA algorithm with several state-of-the art algorithms (as
implemented in [71]) such as multiple variants of the procedurally fair
algorithms, and the best known heuristic algorithm when preferences are drawn
from the Mallows model.999The comparison of algorithms for the Uniform model
can be found in Appendix E. We use an exhaustive search algorithm as our
baseline to find sex-equal stable matchings [70]. In particular, we test
several procedures allowing both sides to issue and receive proposals such as
Late Discontent Dispension (LDS), Early Discontent Dispension, and
Powerbalance [71]. We also measure the performance of an enhanced
bidirectional local search iBILS, which is one of the best-performing existing
heuristic for finding sex-equal stable matchings.

###  5.1 Experimental Setup

We evaluate the sex-equality cost and the run-time of these algorithms for the
number of agents varying from 20 to 1000. For the symmetric correlation case,
we select $\phi_{m}=\phi_{w}=0.5$ as these parameters results in the largest
lattice size among all combinations of $\phi_{m}$ and $\phi_{w}$ (see Table
4). We sample 1000 instances of the stable matching for each experimental
setting.

The exhaustive search algorithm uses the break-marriage operation of McVitie
and Wilson [54]: breaking a single man’s assignment initiates a chain of
proposals and rejections. It terminates when either all women reject the last
man, or his proposal is accepted by a single woman. The latter case results in
a new stable matching. All the elements of the stable lattice can be found by
applying this operation recursively from the men-optimal solution
[54].101010An example of the break-marriage operation is provided in Appendix
A.

The enhanced bidirectional local search, iBILS, uses rotations to generate the
successors of a stable matching to search over the stable lattice starting
from its extreme points [70, 73].

###  5.2 Fairness and Running Time

Symmetric correlation. For symmetric correlation markets we used a smaller
number of agents (up to 150), to avoid instances with extremely large
lattices, for which exhaustive search would not terminate in a reasonable time
(Section 4.2). Under symmetric correlations, stable lattice can grow
exponentially [48]. In our experiments, all algorithms performed similarly on
average with respect to the sex-equality cost (Figure 6). Among them, the
iBILS algorithm performed better, and in most instances, found the sex-equal
stable matching that was computed by the exhaustive search algorithm. These
results and the good performance of other algorithms are justified by the fact
that under the Mallows model, $S_{M}$ and $S_{W}$ scores of all stable
matchings are close to one another (i.e. the welfare gap between the two sets
is small). Therefore, many stable matchings have costs close to that of the
the sex-equal solution.

While the DA and procedurally fair algorithms give higher sex-equality costs
(on average twice as much as the exhaustive search and the iBILS algorithms),
they have much smaller running times. For larger instances, this discrepancy
between the running times will become even more pronounced. The exhaustive
search has exponential complexity in the worst case. The running time of the
iBILS algorithm depends on the stable lattice size and its configuration: it
is $\mathcal{O}(dkn^{2})$, where $d$ is the maximum search depth and $k$ is
the maximum width of the lattice [74, 70]. The DA algorithm and procedurally
fair algorithms run in polynomial-time.

Asymmetric correlation. In asymmetric correlation markets, we focused on
comparing the performance of iBILS and DA with additional pre-processing step
(aka DA*). Given the findings in Section 4.1, we modify the DA algorithm by
deciding which side should propose according to the dispersion parameters: the
side with smaller dispersion parameter proposes, i.e. when $\phi_{m}<\phi_{w}$
men propose, otherwise women propose. In real-world markets, dispersion
parameters can be inferred from preference profiles in polynomial time when
the reference ranking is known [33].

Figure 7 presents the sex-equality cost of DA* compared to the iBILS algorithm
for large markets with 300 and 1000 agents. In almost all instances, DA* finds
the same stable matching as iBILS. More importantly, as shown in Figure 8, the
run-time of the DA* remains in $\mathcal{O}(n^{2})$ while iBILS requires more
steps to estimate a sex-equal solution. Given the performance of iBILS in most
cases, our results suggest that DA* is a reasonable cost-effective fair
algorithm for matching markets with asymmetric correlations.

Figure 8: Mallows model (asymmetric): the running time of iBILS and a pre-
processed Deferred Acceptance (DA*) for an asymmetric correlation market with
$\phi_{m}=0.5$, $\phi_{w}=0.7$ (other combinations of parameters give
analogous results).

##  6 Concluding Remarks

For decades, market design has played a crucial role in setting the
foundations of decision-making through mechanism design. While the theoretical
guarantees sometimes fall short due to incompatibilities between axiomatic
requirements or challenges imposed by computational complexity, empirical
evaluations can still shed light on practical implications and guide the
design of new mechanisms. This in turn could help produce new problems and
directions for traditional theory.

In this spirit, our extensive empirical investigations revealed an intriguing
relation between the disparity of preferences of both sides and the fairness
of stable matchings. We showed that surprisingly, the primary factor affecting
the sex-equality cost of the DA algorithm is the difference between dispersion
parameters of both sides. These observations suggest that the DA algorithm
could still be a prime candidate both in symmetric and asymmetric markets,
further justifying its wide use in practice.

From the theoretical perspective, investigating the bounds of fairness in
stable matchings under correlated preferences is certainly an interesting
future direction. From the practical perspective, a noteworthy, and perhaps
more important, direction is to investigate the structure of preferences in
various matching settings (e.g. refugee matching, residency matching, and
school choice) and develop domain-specific models that can correctly capture
the correlations between the preferences with high accuracy. We believe that
these models, alongside with theoretical studies, should shape governmental
and societal policies—prescribed by social planners—in the adoption of
suitable mechanisms in each specific domain.

## Acknowledgments

Hadi Hosseini acknowledges support from NSF IIS grants #2052488 and #2107173.
We are grateful to the anonymous referees for their valuable comments and
suggestions.

## References

  * Abdulkadiroğlu and Sönmez [2003] Atila Abdulkadiroğlu and Tayfun Sönmez.  School choice: A mechanism design approach.  _American economic review_ , 93(3):729–747, 2003\.
  * Abdulkadiroğlu et al. [2005a] Atila Abdulkadiroğlu, Parag A Pathak, and Alvin E Roth.  The New York City High School Match.  _American Economic Review_ , 95(2):364–367, 2005a.
  * Abdulkadiroğlu et al. [2005b] Atila Abdulkadiroğlu, Parag A Pathak, and Alvin E Roth.  The new york city high school match.  _American Economic Review_ , 95(2):364–367, 2005b.
  * Abdulkadiroğlu et al. [2005c] Atila Abdulkadiroğlu, Parag A Pathak, Alvin E Roth, and Tayfun Sönmez.  The Boston Public School Match.  _American Economic Review_ , 95(2):368–371, 2005c.
  * Aldershof et al. [1999] Brian Aldershof, Olivia M Carducci, and David C Lorenc.  Refined inequalities for stable marriage.  _Constraints_ , 4(3):281–292, 1999.
  * Ashlagi et al. [2017] Itai Ashlagi, Yash Kanoria, and Jacob D Leshno.  Unbalanced random matching markets: The stark effect of competition.  _Journal of Political Economy_ , 125(1):69–98, 2017.
  * Ashlagi et al. [2020] Itai Ashlagi, Mark Braverman, Clayton Thomas, and Geng Zhao.  Tiered random matching markets: Rank is proportional to popularity.  _arXiv preprint arXiv:2009.05124_ , 2020.
  * Awasthi et al. [2014] Pranjal Awasthi, Avrim Blum, Or Sheffet, and Aravindan Vijayaraghavan.  Learning mixtures of ranking models.  In _Advances in Neural Information Processing Systems_ , pages 2609–2617, 2014.
  * Banerjee and Johari [2019] Siddhartha Banerjee and Ramesh Johari.  Ride sharing.  In _Sharing economy_ , pages 73–97. Springer, 2019.
  * Beyhaghi et al. [2017] Hedyeh Beyhaghi, Daniela Saban, and Eva Tardos.  Effect of selfish choices in deferred acceptance with short lists.  _arXiv preprint arXiv:1701.00849_ , 2017.
  * Bhatnagar et al. [2008] Nayantara Bhatnagar, Sam Greenberg, and Dana Randall.  Sampling stable marriages: why spouse-swapping won’t work.  In _Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1223–1232. Society for Industrial and Applied Mathematics, 2008.
  * Black et al. [1958] Duncan Black et al.  The theory of committees and elections.  1958\.
  * Boudreau and Knoblauch [2010] James W Boudreau and Vicki Knoblauch.  Marriage matching and intercorrelation of preferences.  _Journal of Public Economic Theory_ , 12(3):587–602, 2010.
  * Campo and Erné [2018] Frank A Campo and Marcel Erné.  Exponential functions of finite posets and the number of extensions with a fixed set of minimal points.  _arXiv preprint arXiv:1802.01419_ , 2018.
  * Caragiannis et al. [2013] Ioannis Caragiannis, Ariel D Procaccia, and Nisarg Shah.  When do noisy votes reveal the truth?  In _Proceedings of the Fourteenth ACM Conference on Electronic Commerce_ , pages 143–160, 2013.
  * Celik and Knoblauch [2007] Onur B Celik and Vicki Knoblauch.  Marriage matching with correlated preferences.  2007\.
  * Cheng [2010] Christine T Cheng.  Understanding the generalized median stable matchings.  _Algorithmica_ , 58(1):34–51, 2010.
  * Cheng and Rosenbaum [2021] Christine T Cheng and Will Rosenbaum.  Stable matchings with restricted preferences: Structure and complexity.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , pages 319–339, 2021.
  * Delacretaz et al. [2019] David Delacretaz, Scott Kominers, and Alexander Teytelboym.  Matching mechanisms for refugee resettlement.  Technical report, Human Capital and Economic Opportunity Working Group, 2019.
  * Demange et al. [1987] Gabrielle Demange, David Gale, and Marilda Sotomayor.  A further note on the stable matching problem.  _Discrete Applied Mathematics_ , 16(3):217–222, 1987.
  * Feder [1992] Tomás Feder.  A new fixed point approach for stable networks and stable marriages.  _Journal of Computer and System Sciences_ , 45(2):233–284, 1992.
  * [22] Rupert Freeman, Evi Micha, and Nisarg Shah.  Two-sided matching meets fair division.
  * Gale and Shapley [1962] David Gale and Lloyd S Shapley.  College admissions and the stability of marriage.  _The American Mathematical Monthly_ , 69(1):9–15, 1962.
  * Gale and Sotomayor [1985] David Gale and Marilda Sotomayor.  Some Remarks on the Stable Matching Problem.  _Discrete Applied Mathematics_ , 11(3):223–232, 1985.
  * Gupta et al. [2017] Sushmita Gupta, Saket Saurabh, and Meirav Zehavi.  On treewidth and stable marriage.  _arXiv preprint arXiv:1707.05404_ , 2017.
  * Gusfield [1987] Dan Gusfield.  Three fast algorithms for four problems in stable marriage.  _SIAM Journal on Computing_ , 16(1):111–128, 1987\.
  * Gusfield and Irving [1989] Dan Gusfield and Robert W Irving.  _The stable marriage problem: structure and algorithms_.  MIT press, 1989.
  * Hall et al. [2017] Jonathan V Hall, John J Horton, and Daniel T Knoepfle.  Labor market equilibration: Evidence from uber.  2017\.  Working paper. Revision requested from American Economic Review.
  * Hassidim et al. [2018] Avinatan Hassidim, Assaf Romm, and Ran I Shorrer.  Need vs. merit: The large core of college admissions markets.  _Merit: The Large Core of College Admissions Markets (June 28, 2018)_ , 2018.
  * Hosseini et al. [2021] Hadi Hosseini, Fatima Umar, and Rohit Vaish.  Accomplice Manipulation of the Deferred Acceptance Algorithm.  In _Proceedings of the 30th International Joint Conference on Artificial Intelligence_ , pages 231–237, 2021.
  * Huang [2010] Chien-Chung Huang.  Classified stable matching.  In _Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms_ , pages 1235–1253. SIAM, 2010.
  * Immorlica and Mahdian [2015] Nicole Immorlica and Mohammad Mahdian.  Incentives in large random two-sided markets.  _ACM Transactions on Economics and Computation (TEAC)_ , 3(3):1–25, 2015.
  * Irurozki [2014] Ekhine Irurozki.  _Sampling and learning distance-based probability models for permutation spaces_.  PhD thesis, 2014.
  * Irurozki et al. [2019] Ekhine Irurozki, Borja Calvo, Jose A Lozano, et al.  Mallows and generalized mallows model for matchings.  _Bernoulli_ , 25(2):1160–1188, 2019.
  * Irving and Leather [1986] Robert W Irving and Paul Leather.  The complexity of counting stable marriages.  _SIAM Journal on Computing_ , 15(3):655–667, 1986\.
  * Irving et al. [1987] 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\.
  * Irving et al. [2008] Robert W Irving, David F Manlove, and Sandy Scott.  The stable marriage problem with master preference lists.  _Discrete Applied Mathematics_ , 156(15):2959–2977, 2008.
  * Jones and Teytelboym [2017] Will Jones and Alexander Teytelboym.  Matching systems for refugees.  _Journal on Migration and Human Security_ , 5(3):667–681, 2017.  doi: 10.1177/233150241700500306.  URL https://doi.org/10.1177/233150241700500306.
  * Kamada and Kojima [2015] Yuichiro Kamada and Fuhito Kojima.  Efficient matching under distributional constraints: Theory and applications.  _American Economic Review_ , 105(1):67–99, 2015\.
  * Kato [1993] Akiko Kato.  Complexity of the sex-equal stable marriage problem.  _Japan Journal of Industrial and Applied Mathematics_ , 10(1):1–19, 1993.
  * Kendall [1938] Maurice G Kendall.  A new measure of rank correlation.  _Biometrika_ , 30(1/2):81–93, 1938.
  * Kendall et al. [1948] MG Kendall et al.  Rank correlation methods.  _Rank correlation methods._ , 1948.
  * Klaus and Klijn [2006] Bettina Klaus and Flip Klijn.  Procedurally fair and stable matching.  _Economic Theory_ , 27(2):431–447, 2006.
  * Knoblauch [2009] Vicki Knoblauch.  Marriage matching and gender satisfaction.  _Social Choice and Welfare_ , 32(1):15–27, 2009\.
  * Knuth et al. [1990] Donald E Knuth, Rajeev Motwani, and Boris Pittel.  Stable husbands.  _Random Structures & Algorithms_, 1(1):1–14, 1990.
  * Kojima and Pathak [2009] Fuhito Kojima and Parag A Pathak.  Incentives and stability in large two-sided matching markets.  _American Economic Review_ , 99(3):608–27, 2009\.
  * Lee [2016] SangMok Lee.  Incentive compatibility of large centralized matching markets.  _The Review of Economic Studies_ , 84(1):444–463, 2016.
  * Levy [2017] Avi William Levy.  _Novel uses of the Mallows model in coloring and matching_.  PhD thesis, Dept. of Mathematics, University of Washington, Seattle, 2017\.
  * Lu and Boutilier [2014] Tyler Lu and Craig Boutilier.  Effective sampling and learning for mallows models with pairwise-preference data.  _The Journal of Machine Learning Research_ , 15(1):3783–3829, 2014.
  * Mallows [1957] Colin L Mallows.  Non-null ranking models. i.  _Biometrika_ , 44(1/2):114–130, 1957.
  * Marden [1995] John I Marden.  Analyzing and modeling rank data.  1995\.
  * Mattei and Walsh [2013] Nicholas Mattei and Toby Walsh.  Preflib: A library of preference data http://preflib.org.  In _Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013)_ , Lecture Notes in Artificial Intelligence. Springer, 2013.
  * McDermid and Irving [2014] Eric McDermid and Robert W Irving.  Sex-equal stable matchings: Complexity and exact algorithms.  _Algorithmica_ , 68(3):545–570, 2014.
  * McVitie and Wilson [1971] David G McVitie and Leslie B Wilson.  The stable marriage problem.  _Communications of the ACM_ , 14(7):486–490, 1971\.
  * Nakamura et al. [1995] Morikazu Nakamura, Kenji Onaga, Seiki Kyan, and Manuel Silva.  Genetic algorithm for sex-fair stable marriage problem.  In _Proceedings of ISCAS’95-International Symposium on Circuits and Systems_ , volume 1, pages 509–512. IEEE, 1995.
  * Nguyen and Vohra [2019] Thành Nguyen and Rakesh Vohra.  Stable matching with proportionality constraints.  _Operations Research_ , 67(6):1503–1519, 2019\.
  * Pathak and Sönmez [2007] Parag Pathak and Tayfun Sönmez.  c.  2007\.
  * Pittel [1989] Boris Pittel.  The average number of stable matchings.  _SIAM Journal on Discrete Mathematics_ , 2(4):530–549, 1989.
  * Rheingans-Yoo and Street [2020] Ross Rheingans-Yoo and Jane Street.  Large random matching markets with localized preference structures can exhibit large cores.  Technical report, Mimeo, 2020.
  * Romero-Medina [2005] Antonio Romero-Medina.  Equitable selection in bilateral matching markets.  _Theory and Decision_ , 58(3):305–324, 2005.
  * Roth [1982] Alvin E Roth.  The economics of matching: Stability and incentives.  _Mathematics of operations research_ , 7(4):617–628, 1982.
  * Roth [1984] Alvin E Roth.  The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory.  _Journal of Political Economy_ , 92(6):991–1016, 1984.
  * Roth [2002] Alvin E Roth.  The economist as engineer: Game theory, experimentation, and computation as tools for design economics.  _Econometrica_ , 70(4):1341–1378, 2002.
  * Roth and Peranson [1999] Alvin E Roth and Elliott Peranson.  The redesign of the matching market for american physicians: Some engineering aspects of economic design.  _American economic review_ , 89(4):748–780, 1999\.
  * Roth and Vate [1990] Alvin E Roth and John H Vande Vate.  Random paths to stability in two-sided matching.  _Econometrica: Journal of the Econometric Society_ , pages 1475–1480, 1990.
  * Salonen and Salonen [2018] Hannu Salonen and Mikko AA Salonen.  Mutually best matches.  _Mathematical Social Sciences_ , 91:42–50, 2018.
  * Shen et al. [2018] Weiran Shen, Pingzhong Tang, and Yuan Deng.  Coalition manipulation of gale-shapley algorithm.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Steyvers et al. [2009] Mark Steyvers, Brent Miller, Pernille Hemmer, and Michael D Lee.  The wisdom of crowds in the recollection of order information.  In _Advances in Neural Information Processing Systems_ , pages 1785–1793, 2009.
  * Teo et al. [2001] Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan.  Gale-shapley stable marriage problem revisited: Strategic issues and applications.  _Management Science_ , 47(9):1252–1267, 2001\.
  * Tziavelis et al. [2019] Nikolaos Tziavelis, Ioannis Giannakopoulos, Katerina Doka, Nectarios Koziris, and Panagiotis Karras.  Equitable stable matchings in quadratic time.  In _Advances in Neural Information Processing Systems_ , pages 455–465, 2019.
  * Tziavelis et al. [2020] Nikolaos Tziavelis, Ioannis Giannakopoulos, Rune Quist Johansen, Katerina Doka, Nectarios Koziris, and Panagiotis Karras.  Fair procedures for fair stable marriage outcomes.  In _Thirty-Fourth AAAI Conference on Artificial Intelligence_ , 2020\.
  * Vaish and Garg [2017] Rohit Vaish and Dinesh Garg.  Manipulating gale-shapley algorithm: Preserving stability and remaining inconspicuous.  In _IJCAI_ , pages 437–443, 2017.
  * Viet et al. [2016] Hoang Huu Viet, SeungGwan Lee, TaeChoong Chung, et al.  A bidirectional local search for the stable marriage problem.  In _2016 International Conference on Advanced Computing and Applications (ACOMP)_ , pages 18–24. IEEE, 2016.
  * Viet et al. [2020] Hoang Huu Viet, Le Hong Trang, Le Pham Tuyen, and Taechoong Chung.  A shortlist-based bidirectional local search for the stable marriage problem.  _Journal of Experimental & Theoretical Artificial Intelligence_, 32(1):147–163, 2020.
  * Vitelli et al. [2017] Valeria Vitelli, Øystein Sørensen, Marta Crispino, Arnoldo Frigessi, and Elja Arjas.  Probabilistic preference learning with the mallows rank model.  _The Journal of Machine Learning Research_ , 18(1):5796–5844, 2017.

Supplementary Material

##  Appendix A Additional Preliminaries

In this section, we give additional preliminaries, definitions, and examples
to provide a complete view to the readers.

#### Dominance

Stable matching $\mu^{\prime}$ dominates stable matching $\mu$ if it assigns
all men a partner at least as good as in $\mu$ and a better partner to at
least one man [27]. Formally, $\mu^{\prime}$ dominates $\mu$ if $\forall m\in
M$ $r(\mu^{\prime}(m),m)\leq r(\mu(m),m)$ and $\exists m^{*}\in M$ such that
$r(\mu^{\prime}(m^{*}),m^{*})<r(\mu(m^{*}),m^{*})$.

#### Stable lattice

Given a preference profile $\succ$, the set of all corresponding stable
matchings, $S_{\succ}$, forms a _distributive lattice_ under a dominance
relation (referred to as a stable lattice hereinafter). Any pair of stable
matchings in a stable lattice has a unique least upper bound (also called a
join) and a unique greatest lower bound (a meet) within the lattice. In a join
of two stable matchings, $\mu_{1}$, $\mu_{2}$, every man from $M$ is given its
best partner among $\mu_{1}$, $\mu_{2}$. Similarly, in a meet all men are
given their worse partners from $\mu_{1}$, $\mu_{2}$.

In a stable lattice supremum, the men-optimal matching $\mu^{M}$, all men are
matched to their favorite partners among all potential stable partners. It
dominates every other matching in $S_{\succ}$, formally $\forall m\in M$,
$r(\mu^{M}(m),m)\leq r(\mu^{\prime}(m),m)$ for all $\mu^{\prime}\in
S_{\succ}$. Similarly, in a stable lattice infimum, the men-pessimal matching
$\mu^{W}$, all men are given their worse stable partners. Men-pessimal
matching is dominated by every other stable matching. Interestingly, a stable
lattice infimum is simultaneously women-optimal matching: each woman is
matched to her best stable partner in $S_{\succ}$, i.e., $\forall w\in W$,
$r(\mu^{W}(w),w)\leq r(\mu^{\prime}(w),w)$ for all $\mu^{\prime}\in
S_{\succ}$. Figure 1 illustrates a lattice consisting of six stable matchings.

#### Rotation poset.

For any stable lattice $S_{\succ}$ there exists an associated partially
ordered set (a rotation poset, $\mathcal{R}(S_{\succ})$), whose downsets are
in one-to-one correspondence with the matchings of the lattice [27]. The
elements of the rotation poset—aka rotations—are specific sequences of pairs
matched in some stable matching. For each man $m$ in a rotation the following
holds: 1) the woman in his pair is his current partner $\mu(m)$; 2) the woman
to the right of $m$ (or the first woman if $m$ is the last man),
$w_{next}(m)$, would be the first to accept his proposal if he is disallowed
to propose to $\mu(m)$ within the course of DA. Formally, a rotation
$\rho=(m_{1},w_{1}),(m_{2},w_{2}),...,(m_{k},w_{k})$ is a sequence of pairs in
a matching such that $m_{i}$ is matched to $w_{i}$, and $w_{(i+1)\ mod\ k}$ is
the first woman in $m_{i}$’s preference list who prefers him to her current
partner. For specific $\mu$ and $\rho$, if for every man $m_{i}\in\rho$ the
above conditions holds, the rotation $\rho$ is said to be exposed in $\mu$.
One rotation can be exposed in multiple stable matchings of the same problem
instance; a stable matching can have multiple exposed rotations [27] .

Given $\rho$ exposed in $\mu$, if every man $m_{i}$ from the rotation is
matched to the woman to the right of him, $w_{i+1}$ (where $(i+1)$ is taken
modulo size of $\rho$), and every man not in the rotation is assigned his
current partner, then the resulting matching is also stable [35]. Rotations
can be thought of as the transition operations between the adjacent elements
of the lattice. The rotation poset is a useful structure for studying the
stable matching problem [11, 26, 17] as it contains $\mathcal{O}(n^{2})$
elements (in contrast to the exponential size of the stable lattice in the
worst case) and yet encodes all stable matchings. We refer the reader to [27]
for a more detailed discussion on the subject of rotations.

#### Example from Figure 1: Stable Lattice and Rotations

In this section, we illustrate the concept of stable lattice, rotation poset
and break-marriage operation using the preference profile given in Example
1.1.

$\mu^{M}$$(w_{2},w_{3},w_{1},w_{4},w_{5})$, Men-
optimal$\mu_{1}$$(w_{4},w_{3},w_{1},w_{2},w_{5})$$\mu_{2}$$(w_{2},w_{3},w_{5},w_{4},w_{1})$$\mu_{3}$$(w_{4},w_{2},w_{1},w_{3},w_{5})$$\mu_{4}$$(w_{4},w_{3},w_{5},w_{2},w_{1})$$\mu^{W}$$(w_{4},w_{2},w_{5},w_{3},w_{1})$,
Women-optimal (Sex-
equal)$\rho_{1}$$\rho_{3}$$\rho_{2}$$\rho_{3}$$\rho_{2}$$\rho_{1}$$\rho_{3}$
Figure 9: The stable lattice for the profile described in Example 1.1 with six
stable solutions. Matchings are denoted as lists of women matched to men
according to their indices, rotations are indicated by $\rho_{x}$ on arcs.

We run a men-proposing DA to obtain the men-optimal matching, $\mu^{M}$ =
($w_{2}$, $w_{3}$, $w_{1}$, $w_{4}$, $w_{5}$), where women are matched to men
according to their position in the matching, e.g. $w_{2}$ is matched to
$m_{1}$, $w_{3}$ to $m_{2}$ and so on.

To identify a rotation exposed in $\mu^{M}$ we will use the concept of
shortlists [36]. Given a stable matching $\mu$, let each woman $w\in W$ remove
from her list all men, that she does not prefer over her current partner, i.e.
every $m^{\prime}$ s.t. $\mu(m)\succ_{w}m^{\prime}$. Removed men delete woman
$w$ from their preferences as well. In the resulting male-oriented shortlist,
the following holds for every $m\in M$ : 1) $m$’s current partner is the first
entry in his list $\succ_{m}$; 2) the first woman who prefers $m$ to her
partner, $w_{next}(m)$, is the second entry in $\succ_{m}$. Also, for every
woman $w\in W$ her current partner is the last entry in her preference list
$\succ_{w}$ [36].

$m_{1}\colon$ |  $w_{2}^{\dagger}$ |  $w_{4}$ |  $w_{5}$ |  $w_{1}$ |  |  |  $w_{1}\colon$ |  $m_{4}$ |  $m_{2}$ |  $m_{1}$ |  $m_{5}$ |  $m_{3}^{\dagger}$
---|---|---|---|---|---|---|---|---|---|---|---|---
$m_{2}\colon$ |  $w_{3}^{\dagger}$ |  $w_{2}$ |  $w_{4}$ |  $w_{1}$ |  $w_{5}$ |  |  $w_{2}\colon$ |  $m_{2}$ |  $m_{4}$ |  $m_{1}^{\dagger}$ |  |
$m_{3}\colon$ |  $w_{1}^{\dagger}$ |  $w_{5}$ |  |  |  |  |  $w_{3}\colon$ |  $m_{4}$ |  $m_{2}^{\dagger}$ |  |  |
$m_{4}\colon$ |  $w_{4}^{\dagger}$ |  $w_{2}$ |  $w_{3}$ |  $w_{1}$ |  $w_{5}$ |  |  $w_{4}\colon$ |  $m_{2}$ |  $m_{1}$ |  $m_{4}^{\dagger}$ |  |
$m_{5}\colon$ |  |  |  $w_{5}^{\dagger}$ |  $w_{1}$ |  |  |  $w_{5}\colon$ |  $m_{1}$ |  $m_{4}$ |  $m_{2}$ |  $m_{3}$ |  $m_{5}^{\dagger}$
Table 2: The shortlist of men-optimal matching of Example 1.1 instance

To identify an exposed rotation, we will take the first man $m_{1}$ and put it
in front of a candidate rotation along with his current partner
$\rho_{1}=(m_{1},\mu(m_{1}))$. The next pair in the sequence must contain
$w_{next}(m_{1})$ and her partner $\mu(w_{next}(m_{1}))$, i.e.
$\rho_{1}=(m_{1},\mu(m_{1})),(\mu(w_{next}(m_{1})),w_{next}(m_{1}))$. We will
repeat building the candidate rotation in this fashion. The rotation becomes
valid as soon as one of the men appears twice in the same candidate rotation.
After this happens, we will discard all pairs outside of the cycle: the
remaining ordered sequence of pairs constitutes a rotation exposed in $\mu$.
In order to identify all rotations exposed in the same matching, the same
procedure must be repeated for all men that did not appear in a valid rotation
and were not discarded in the course of building one.

We will identify all rotations exposed in $\mu^{M}$ to obtain several stable
matchings adjacent to it. We start a candidate rotation with putting $m_{1}$
and his partner $w_{2}$ to the beginning: $\rho_{1}=(m_{1},w_{2})$. The first
woman who prefers $m_{1}$ over her current partner is $w_{4}$, and we append
her and her partner as the next pair in the sequence:
$\rho_{1}=(m_{1},w_{2})(m_{4},w_{4})$. The next pair in the sequence will be
($m_{1}$, $w_{2}$) as $w_{next}(m_{4})=w_{2}$. As it is the second appearance
of $m_{1}$ in the sequence we found a rotation exposed in $\mu^{M}$. We
continue in this fashion with the next man $m_{3}$ as a founder of a new
candidate rotation, that leads to $\rho_{3}=(m_{3},w_{1}),(m_{5},w_{5})$.
Using $m_{2}$ as the first man of a rotation leads to already found
$\rho_{1}$.

When rotation $\rho_{1}$ is applied to $\mu^{M}$, $m_{1}$ is matched to
$w_{4}$, $m_{4}$ to $w_{2}$, giving stable matching
$\mu_{1}=(w_{4},w_{3},w_{1},w_{2},w_{5})$. Similarly, the application of
$\rho_{3}$ gives $\mu_{2}=(w_{2},w_{3},w_{5},w_{4},w_{1})$. By finding and
applying rotations exposed in $\mu_{1}$, $\mu_{2}$ one can recreate the
lattice from Example 1.1 with 6 elements.

One can also use a break-marriage algorithm to find all the elements of the
lattice: it is a recursive procedure that starts with breaking assignments of
the fist man in the men-optimal matching, and letting him propose to the next
woman who has not rejected him yet. This initial change in the matching
initiates a chain of proposals and rejections between the agents and
terminates when either all women reject some man (the last one to propose), or
his proposal is accepted by a single woman. The latter case results in a new
stable matching. By applying this operation recursively to all new stable
matchings one can find all the elements of the stable lattice [54]

Let apply break-marriage to the fist man in the men-optimal matching
$\mu^{M}$: $m_{1}$ is assigned free and propose to his next favorite woman in
the list $w_{4}$. She prefers his proposal to her current partner and is
matched to $m_{1}$ tentatively. Man $m_{4}$ proposes to $w_{2}$, who accepts
the proposal since she is currently single. The new matching is $\mu_{1}$ and
the current breakmarriage round will now assign $m_{2}$ in $\mu^{M}$ free and
tries to identify a new stable matching. If breakmarriage is applied to all
men in the matching, it will result in repetitive stable matchings, so a more
efficient modification of the algorithm exists [54].

##  Appendix B Summary Statistics for Stable Lattice and Rotation Poset

Figure 10: The size of the rotation poset with respect to $\phi_{m}-\phi_{w}$ in the Mallows model for $n=150$: median values (left), maximum values (right). Dotted lines denote the medians, shadowed gray area denotes 1st and 3rd quartiles. Y-axes of left and right figures have different scales | n | Type |  max($\mathcal{R}$) |  Median $\mathcal{R}$ |  CI($\mathcal{R}$)
---|---|---|---|---|---
1 | 150 | Mallows | 11 | 4.00 | (1;8)
3 | 150 | Uniform | 53 | 33.00 | (19;45)
4 | 300 | Mallows | 18 | 8.00 | (3;13)
5 | 300 | Uniform | 85 | 60.00 | (44;76)
Table 3: The size of the rotation poset ($\mathcal{R}$) under the Uniform, and the Mallows with $\phi_{m}=\phi_{w}=0.5$ models.  | $\phi_{w}$ | Q2($\mathcal{L}$) | Q1($\mathcal{L}$) | Q3($\mathcal{L}$) | max($\mathcal{L}$) | max($\mathcal{R}$) | Q2($\mathcal{R}$) | Q1($\mathcal{R}$) | Q3($\mathcal{R}$)
---|---|---|---|---|---|---|---|---|---
|  |  |  |  | $\phi_{m}=0.1$ |  |  |  |
1 | 0.1 | 2.00 | 1.00 | 4.00 | 128 | 7 | 1.00 | 0.00 | 2.00
2 | 0.3 | 4.00 | 2.00 | 8.00 | 128 | 7 | 2.00 | 1.00 | 3.00
3 | 0.5 | 2.00 | 2.00 | 4.00 | 32 | 5 | 1.00 | 1.00 | 2.00
4 | 0.7 | 2.00 | 1.00 | 2.00 | 32 | 5 | 1.00 | 0.00 | 1.00
5 | 0.9 | 1.00 | 1.00 | 1.00 | 8 | 3 | 0.00 | 0.00 | 0.00
6 | 1 | 1.00 | 1.00 | 1.00 | 4 | 2 | 0.00 | 0.00 | 0.00
|  |  |  |  | $\phi_{m}=0.3$ |  |  |  |
7 | 0.1 | 4.00 | 2.00 | 6.50 | 128 | 7 | 2.00 | 1.00 | 3.00
8 | 0.3 | 8.00 | 4.00 | 16.00 | 2048 | 11 | 3.00 | 2.00 | 4.00
9 | 0.5 | 8.00 | 4.00 | 16.00 | 768 | 10 | 3.00 | 2.00 | 4.00
10 | 0.7 | 4.00 | 2.00 | 8.00 | 256 | 8 | 2.00 | 1.00 | 3.00
11 | 0.9 | 1.00 | 1.00 | 2.00 | 16 | 4 | 0.00 | 0.00 | 1.00
12 | 1 | 1.00 | 1.00 | 2.00 | 8 | 3 | 0.00 | 0.00 | 1.00
|  |  |  |  | $\phi_{m}=0.5$ |  |  |  |
13 | 0.1 | 2.00 | 1.00 | 4.00 | 64 | 6 | 1.00 | 0.00 | 2.00
14 | 0.3 | 8.00 | 4.00 | 16.00 | 1024 | 10 | 3.00 | 2.00 | 4.00
15 | 0.5 | 16.00 | 6.00 | 32.00 | 1024 | 11 | 4.00 | 3.00 | 5.00
16 | 0.7 | 8.00 | 4.00 | 16.00 | 512 | 9 | 3.00 | 2.00 | 4.00
17 | 0.9 | 2.00 | 1.00 | 4.00 | 96 | 7 | 1.00 | 0.00 | 2.00
18 | 1 | 1.00 | 1.00 | 2.00 | 12 | 5 | 0.00 | 0.00 | 1.00
|  |  |  |  | $\phi_{m}=0.7$ |  |  |  |
19 | 0.1 | 2.00 | 1.00 | 2.00 | 16 | 4 | 1.00 | 0.00 | 1.00
20 | 0.3 | 4.00 | 2.00 | 8.00 | 192 | 8 | 2.00 | 1.00 | 3.00
21 | 0.5 | 8.00 | 4.00 | 16.00 | 384 | 10 | 3.00 | 2.00 | 4.00
22 | 0.7 | 12.00 | 4.00 | 32.00 | 2304 | 12 | 4.00 | 2.00 | 5.00
23 | 0.9 | 4.00 | 2.00 | 8.00 | 192 | 9 | 2.00 | 1.00 | 3.00
24 | 1 | 2.00 | 1.00 | 4.00 | 14 | 6 | 1.00 | 0.00 | 2.00
|  |  |  |  | $\phi_{m}=0.9$ |  |  |  |
25 | 0.1 | 1.00 | 1.00 | 1.00 | 8 | 3 | 0.00 | 0.00 | 0.00
26 | 0.3 | 1.00 | 1.00 | 2.00 | 16 | 5 | 0.00 | 0.00 | 1.00
27 | 0.5 | 2.00 | 1.00 | 4.00 | 96 | 7 | 1.00 | 0.00 | 2.00
28 | 0.7 | 4.00 | 2.00 | 8.00 | 96 | 8 | 2.00 | 1.00 | 3.00
29 | 0.9 | 8.00 | 4.00 | 16.00 | 280 | 14 | 4.00 | 2.00 | 5.00
30 | 1 | 8.00 | 4.00 | 12.00 | 112 | 15 | 4.00 | 3.00 | 6.00
|  |  |  |  |  $\phi_{m}=1.0$(Uniform) |  |  |  |
31 | 0.1 | 1.00 | 1.00 | 1.00 | 4 | 2 | 0.00 | 0.00 | 0.00
32 | 0.3 | 1.00 | 1.00 | 2.00 | 8 | 3 | 0.00 | 0.00 | 1.00
33 | 0.5 | 1.00 | 1.00 | 2.00 | 9 | 5 | 0.00 | 0.00 | 1.00
34 | 0.7 | 2.00 | 1.00 | 4.00 | 30 | 7 | 1.00 | 0.00 | 2.00
35 | 0.9 | 7.00 | 4.00 | 12.00 | 116 | 15 | 5.00 | 3.00 | 7.00
36 | 1 | 82.00 | 61.00 | 112.00 | 794 | 53 | 33.00 | 29.00 | 37.00
Table 4: Summary statistics for the size of the lattice ($\mathcal{L}$) and
the rotation poset ($\mathcal{R}$) in Mallows model with different dispersion
parameters for men ($\phi_{m}$) and women($\phi_{w}$). Q1, Q2, Q3 indicate
25th, 50th (median), 75th percentiles.

#### Rotation Poset

The rotation poset size follows the same pattern as the lattice size: it has
the maximum size in case of zero correlation disparity and decreases with the
increase in the disparity. The rotation poset is much smaller under the
Mallows model (all cases) compared to the Uniform. For $n=150$, the median
rotation poset size in the Uniform model ($33$) is substantially larger than
in the Mallows model (maximum median equals $4$ rotations) (Table 3). For
$n=300$, the difference is even more pronounced: $60$ rotations vs $8$. For a
general case, if rotation poset $\mathcal{R}$ has $r$ rotations and height
$h$, the maximum number of downsets in a poset, $d(P)$, (corresponding to
maximum stable lattice size) can be counted as $d(P)=2^{r-h}(h+1)$ [14]. We
see an interesting configuration of the rotation posets associated with large
lattices: a decreased height (the size of the maximal chain), and an increased
width (the size of the largest anti-chain) [14]. For example, for $n=150$ the
maximum stable lattice under the Mallows model has $2304$ matchings, only $12$
corresponding rotations and rotation poset height equals $2$ (Table 4). Under
the Uniform model the maximum stable lattice was smaller but had many more
rotations: $626$ matchings and $53$ rotations (the rotation poset height was
equal to $4$).

##  Appendix C Fine-grained asymmetric correlation case

In the part of the graph, where women’s preferences have a lower dispersion
parameter $\phi_{w}<\phi_{m}$, the distribution of $S_{W}$-scores of a women-
optimal matching lies above the distribution of its $S_{M}$-scores: the
distributions have no overlap for $\phi_{w}\leq 0.96$ (Figure 11).

Figure 11: Illustrating $S_{M}$, $S_{W}$ scores under the Mallows model with
$\phi_{m}=0.99$ and varying $\phi_{w}$ based on 1000 samples.

##  Appendix D Egalitarian cost under the Mallows model

To assess the total welfare of DA outcome in the presence of correlation, we
looked into its egalitarian cost. We found that introducing correlation in
preferences of any side translates into a high total dissatisfaction of all
agents by the DA outcome.

Given a preference profile $\succ$, the _egalitarian cost_ of a stable
matching is the total ranking over all men and women [36]. Formally,

$c^{\prime}(\mu)=S_{M}(\mu)+S_{W}(\mu)$ (3)

The smaller the egalitarian cost, the higher the welfare of all involved
agents.

According to our experiments, DA algorithm is a reasonable alternative to the
exhaustive search algorithm for finding a sex-equal stable matching, when the
preferences come from the Mallows model. Its output seems to be either a sex-
equal solution (in asymmetric correlation markets) or a matching close to sex-
equal one in terms of the cost (in symmetric correlation markets). Although DA
achieves such a high level of sex-equality fairness in the Mallows, the
overall satisfaction of agents by its output remains low in experiments
(Figure 12). The egalitarian cost is high for all $\phi$ combinations under
the Mallows distribution: the smallest median score is $16636$ for
$\phi_{m}=\phi_{w}=0.9$, which for $n=150$ corresponds to having a partner
with $55$ rank position on average. In contrast, the DA applied to the uniform
preferences have a relatively high total satisfaction, while having a great
disparity between the welfare of men and women according to our experiments
(Figure 4).

Figure 12: The egalitarian cost of a men-optimal matching under the Mallows
model with various $\phi_{m}$, $\phi_{w}$ and $n=150$. Confidence intervals
are given in parentheses.

##  Appendix E Algorithm performance in the Uniform model

Under the Uniform model, the outcomes of the DA algorithm have high sex-
equality costs, as expected, since men- and women-optimal matchings have high
sex-equality cost [58]. Other algorithms performed better: iBILS and
PowerBalance showed the best performance and in most cases were able to find a
sex-equal stable matching.

Figure 13: Uniform model: comparing the sex-equality cost of various matching
algorithms. Subscripts 0, indicate that men start proposing first, 1 that
women.

##  Appendix F Fairness beyond the Mallows model

###  F.1 Other Correlated Models

We also analyzed the fairness of other correlated preference models known in
the literature. Namely, we analyze the known results for some probabilistic
models with hard-tier sets as well as those that consider correlation
coefficients on preferences. It is unclear whether these models can be thought
of as Mallows models (or Mallows mixture). Yet, similar to the Mallows model
correlation intensity between the preferences of two sides might be a
reasonable indicator in predicting the sex-equality cost of stable matchings.

#### Asymmetric correlation

The Discrete Uniform model from [71] is a probabilistic hard-tier preference
model in which a subset of agents is always ranked higher than the rest of the
set—referred to as hot and cold sets. Within a set, partners are sampled
uniformly. According to experiments of [71] when men have uniform preferences
on women, and women have discrete uniform preferences on men, the women-
proposing DA has one of the lowest sex-equality cost and drastically
outperforms many procedurally fair algorithms. In this case, women’s
preferences are more correlated compared to men, so the women-optimal matching
might become a sex-equal matching (or gives a good approximation of its sex-
equality cost), coinciding with our findings for the Mallows model in
asymmetric correlation markets.

#### Symmetric correlation

Celik and Knoblauch [16] proposes a correlation coefficient of preferences
$\rho$. The coefficient computes the sum of agents’ average ranks in
preferences of men (or women), normalized to take values between 0 (perfectly
uncorrelated preferences) and 1 (identical preferences). The authors used the
correlation coefficients of men $\rho_{m}$ and women $\rho_{w}$ as a predictor
of men’s and women’s satisfaction by DA outcome. To generate instances with
different correlation intensities they sampled from a hard-tier model while
varying the number of tiers. They showed that a higher correlation in
preferences of women sharply reduces their satisfaction by a men-optimal
matching while making the other side slightly better off. These insights are
consistent with our observations (e.g. in Figure 5 $S_{W}$-pessimal rises, and
$S_{M}$-optimal moderately decreases when $\phi_{w}$ decreases).