# The Stable Matching Lattice under Changed Preferences,
and Associated Algorithms

Rohith Reddy Gangam  University of California, Irvine  Tung Mai  Adobe
Research  Nitya Raju111This work was done while the author was a student at
the University of California, Irvine. University of Maryland, College Park
Vijay V. Vazirani  University of California, Irvine

###### Abstract

[MV18] introduced a fundamental new algorithmic question on stable matching,
namely finding a matching that is stable under two “nearby” instances, where
“nearby” meant that in going from instance $A$ to $B$, only one agent changes
its preference list. By first establishing a sequence of structural results on
the lattices of $A$ and $B$, [MV18] and [GMRV22] settled all algorithmic
questions related to this case. The current paper essentially settles the
general case.

Assume that instance $B$ is obtained from $A$, both on $n$ workers and $n$
firms, via changes in the preferences of $p$ workers and $q$ firms. If so, we
will denote the change by $(p,q)$. Thus [MV18, GMRV22] settled the case
$(0,1)$, since they adopt the convention that one firm changes its
preferences. Let $\mathcal{M}_{A}$ and $\mathcal{M}_{B}$ be the sets of stable
matchings of instances $A$ and $B$, and let $\mathcal{L}_{A}$ and
$\mathcal{L}_{B}$ be their lattices. Our results are:

  1. 1.

For $(0,n)$, $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a sublattice of
$\mathcal{L}_{A}$ and of $\mathcal{L}_{B}$. We can efficiently obtain the
worker-optimal and firm-optimal stable matchings in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$. We also obtain the associated partial
order, as promised by Birkhoff’s Representation Theorem, and use it to
enumerate these matchings with polynomial delay.

  2. 2.

For $(1,n)$, the only missing results are the partial order and enumeration.

  3. 3.

We give an example with $(2,2)$ for which $\mathcal{M}_{A}\cap\mathcal{M}_{B}$
fails to be a sublattice of $\mathcal{L}_{A}$.

In light of the fact that for $(n,n)$, determining if
$(\mathcal{M}_{A}\cap\mathcal{M}_{B})=\emptyset$ is NP-hard [MO19], a number
of open questions arise; in particular, closing the gap between $(2,2)$ and
$(n,n)$.

##  1 Introduction

The seminal 1962 paper of Gale and Shapley [GS62] on stable matching launched
the field of matching-based market design. Over the decades, the remarkably
deep and elegant structural, algorithmic and game theoretic properties of
stable matchings were explored by numerous researchers and led to far-reaching
applications, e.g., see [EIV23], culminating in the award of the 2012 Nobel
Prize in Economics.

Five years ago, [MV18] identified a fundamental new question on stable
matching, namely finding a matching that is stable under two “nearby”
instances, where “nearby” meant that in going from instance $A$ to $B$, only
one agent changes its preference list. This turned out to be a fairly loaded
question and its answer required two papers, as detailed below. Both papers
first established new structural results on the lattices of nearby instances
and then used them to derive the algorithms. As described in the abstract and
detailed below, the current paper essentially settles the general case.

Let $A$ be an instance of stable matching on $n$ workers and $n$ firms. [MV18]
studied the special case when the change in the preference list of one agent,
say firm $f$, involved an upward shift. Let $f$’s preference list be
$\\{\ldots,w_{1},w_{2},\ldots,w_{k},w,\ldots\\}$. Move up the position of
worker $w$ so $f$’s list becomes
$\\{\ldots,w,w_{1},w_{2},\ldots,w_{k},\ldots\\}$, and let $B$ be the resulting
instance. Let $\mathcal{M}_{A}$ and $\mathcal{M}_{B}$ be the sets of stable
matchings of instances $A$ and $B$, and let $\mathcal{L}_{A}$ and
$\mathcal{L}_{B}$ be their lattices. [MV18] showed that
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a sublattice of $\mathcal{L}_{A}$ and
of $\mathcal{L}_{B}$ and that $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is a
sublattice of $\mathcal{L}_{A}$. Building on these structural results, [MV18]
gave polynomial time algorithms to determine if
$(\mathcal{M}_{A}\cap\mathcal{M}_{B})\neq\emptyset$ and if so to find the
worker-optimal and firm-optimal stable matchings in its lattice. They also
found the associated partial order of this lattice, as promised by Birkhoff’s
Representation Theorem.

[GMRV22] studied the general case of nearby instances, i.e., firm $f$
arbitrarily permutes its preference list. They showed that whereas
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is still a sublattice of
$\mathcal{L}_{A}$ and of $\mathcal{L}_{B}$,
$\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ may not be a sublattice of
$\mathcal{L}_{A}$; however, $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is a
join semi-sublattice of $\mathcal{L}_{A}$, see Section 2.2. By introducing the
notion of compression of the Birkhoff partial order, they gave efficient
algorithms for all the questions considered by [MV18].

Our investigation of the general case started with Question 1, whose positive
resolution would have led to a general fact about the class of finite
distributive lattices, as described below.

######  Question 1.

Let $A$ and $B$ be two arbitrary instances of stable matching on $n$ workers
and $n$ firms. Is $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ a sublattice of
$\mathcal{L}_{A}$, under its meet and join operations, and also of
$\mathcal{L}_{B}$, under its meet and join operations?

It is well known that the stable matching lattice is universal in the class of
finite distributive lattices in the following sense: Given any lattice
$\mathcal{L}$ from this class, there is a stable matching instance, of an
appropriate size, such that its lattice $\mathcal{L}_{A}$ is isomorphic to
$\mathcal{L}$ [Bla84]. If the answer to Question 1 were “yes”, we would get
the following general fact about this class: Let $U$ be a finite set and let
$A$ and $B$ be its subsets each of which supports a partial order which is a
finite distributive lattice, $\mathcal{L}_{A}$ and $\mathcal{L}_{B}$,
respectively. Then $\mathcal{L}_{A}\cap\mathcal{L}_{B}$ is a sublattice of
$\mathcal{L}_{A}$, under its meet and join operations, and also of
$\mathcal{L}_{B}$, under its meet and join operations.

Unfortunately, the answer to Question 1 is “no”, as stated in Theorem 12. The
smallest counter-example we could find has $n=4$, and $B$ is obtained from $A$
by changing the preferences of two firms and two workers.

Assume that instance $B$ is obtained from $A$ via changes in the preferences
of $p$ workers and $q$ firms. If so, we will denote the change by $(p,q)$. As
a result of the negative answer, we need to determine the parameters $(p,q)$
for which the answer is “yes”. Thus [MV18, GMRV22] showed that the answer is
yes for $(0,1)$ and Theorem 12 shows that the answer is no for $(2,2)$.

For a choice of parameters $(p,q)$ we also would like to answer the following
algorithmic questions:

  1. 1.

Determine if $(\mathcal{M}_{A}\cap\mathcal{M}_{B})\neq\emptyset$.

  2. 2.

If the answer to the first question is “yes”, efficiently obtain the worker-
optimal and firm-optimal stable matchings in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$.

  3. 3.

Also obtain the associated partial order, as promised by Birkhoff’s
Representation Theorem.

  4. 4.

Use this partial order to enumerate the matching in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ with polynomial delay.

Our results are:

  1. 1.

For $(0,n)$, $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a sublattice of
$\mathcal{L}_{A}$ and of $\mathcal{L}_{B}$. Furthermore, we can affirmatively
answer all four algorithmic questions stated above. We note that the
algorithms for the second question are generalizations of the Gale-Shapley
deferred acceptance algorithm; however because of the asymmetry between
workers and firms, we need to give specialized algorithms for obtaining the
worker-optimal and firm-optimal stable matchings. All this holds for $(0,k)$,
for any $k\leq n$ as well.

  2. 2.

For $(1,n)$, $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a sublattice of
$\mathcal{L}_{A}$ and of $\mathcal{L}_{B}$, and we can affirmatively answer
the first two algorithmic questions. Once again, because of the asymmetry
between workers and firms, we need to give specialized algorithms for
obtaining the worker-optimal and firm-optimal stable matchings, and once
again, these results hold for $(1,k)$, for any $k\leq n$ as well. Regarding
the third question we prove that the Birkhoff partial order can be obtained
efficiently for $(1,n)$ if and only if it can be obtained efficiently for
$(1,1)$.

  3. 3.

As stated above, for $(2,2)$ we give an example for which
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ fails to be a sublattice of
$\mathcal{L}_{A}$.

For this case $(2,2)$ we do not know the complexity of determining if
$(\mathcal{M}_{A}\cap\mathcal{M}_{B})\neq\emptyset$, though we believe a
polynomial time algorithm is likely. If so, in light of the fact that for
$(n,n)$, determining if $(\mathcal{M}_{A}\cap\mathcal{M}_{B})=\emptyset$ is
NP-hard ([MO19, CNS18]), closing the gap between $(2,2)$ and $(n,n)$ becomes
an important question, i.e., for what choices of parameters in this range is
this question in $\cal P$ and when does NP-hardness set in.

[MV18] had given an application of this problem to robust stable matching. Let
$D$ be the domain from which instance $B$ is picked. For [MV18],
$|D|=O(n^{3})$, i.e., the number of different instances $B$ that can arise
from instance $A$ via upward shifts. Assume there is a probability
distribution over $D$, so that $B$ is picked with this distribution. The
question is to find a matching that is stable for $A$ and maximizes the
probability of being stable for $B$. This problem is efficiently solvable.
With [GMRV22], the domain increased to $2n(n!)$ and our work increases it to
$(n!)^{n+1}$. However, this application is not a significant one.

This problem has yet to find a niche application. Since the problem is a
fundamental one and with ever more diverse and impactful matching markets
being launched into our economy, e.g., see [EIV23, ftToC19], it will not be
surprising if a niche application is eventually found222There are several
prominent examples of problems which were studied because of their fundamental
nature, without any applications in mind, but years later, they were found to
be immensely important in practice, e.g., online bipartite matching [KVV90]..

Building on [MV18], [CSS21] defines another notion of robustness based on
swaps. A swap is a reversal of two consecutive agents in the preference list
of a worker or a firm. Given an instance $A$ and a parameter $d$, they call a
stable matching $M$ to be $d$-robust if it remains stable after $d$ arbitrary
swaps. They use structural properties of the stable matching lattice to
efficiently determine if instance $A$ admits a $d$-robust matching.

##  2 Preliminaries

###  2.1 The stable matching problem and the lattice of stable matchings

A stable matching problem takes as input a set of $n$ workers,
$\mathcal{W}=\\{w_{1},w_{2},\ldots,w_{n}\\}$ and a set of $n$ firms,
$\mathcal{F}=\\{f_{1},f_{2},\ldots,f_{n}\\}$, collectively referred to as
agents; Each agent $a\in\cal W\cup\cal F$ has a preference profile ($>_{a}$)
that is a complete preference ranking (a strict total order) over the agents
of the other type. The notation $w_{i}>_{f}w_{j}$ indicates that firm $f$
strictly prefers $w_{i}$ to $w_{j}$ in its preference list. A similar notation
is used for worker preferences.

A matching $M$ is a one-to-one correspondence between $\mathcal{W}$ and
$\mathcal{F}$. For each pair $(w,f)\in M$, $w$ is called the partner of $f$ in
$M$ (or $M$-partner) and vice versa. For a matching $M$, a pair $(w,f)\not\in
M$ is said to be a _blocking pair_ if they prefer each other to their
partners, that is if $f>_{w}M(w)$ and $w>_{f}M(f)$. A matching $M$ is _stable_
if it has no blocking pairs.

Let $M$ and $M^{\prime}$ be two stable matchings. We say that $M$ _dominates_
$M^{\prime}$, denoted $M\preceq M^{\prime}$, if every worker weakly prefers
its partner in $M$ to $M^{\prime}$. Define the relation predecessor as the
transitive closure of dominates. For two stable matchings, $M_{1}$ and
$M_{2}$, stable matching $M$ is a common predecessor of $M_{1}$ and $M_{2}$ if
it is a predecessor of both $M_{1}$ and $M_{2}$. Furthermore, $M$ is a lowest
common predecessor of $M_{1}$ and $M_{2}$ if it is a common predecessor
$M_{1}$ and $M_{2}$, and there is no other common predecessor $M^{\prime}$
such that $M$ is a predecessor of $M^{\prime}$. Analogously, one can define
the notions of successor and highest common successor. This dominance partial
order has the following property: For any two stable $M_{1}$ and $M_{2}$,
their lowest common predecessor is unique and their highest common successor
is unique, i.e., the partial order is a lattice; the former is called the
meet, denoted $M_{1}\wedge M_{2}$, and the latter is called the join, denoted
$M_{1}\vee M_{2}$.

One can show that $M_{1}\wedge M_{2}$, is the matching that results when each
worker chooses its more preferred partner from $M_{1}$ and $M_{2}$; it is easy
to show that this matching is also stable. Interestingly, $M_{1}\wedge M_{2}$
is also the matching that results when each firm chooses its lesser preferred
partner from $M_{1}$ and $M_{2}$. Similarly, $M_{1}\vee M_{2}$ is the matching
that results when each worker(/firm) chooses its less(/more) preferred partner
from $M_{1}$ and $M_{2}$; this matching is also stable. Because of this
interesting duality of the stable matching lattice, all the above relations
can be equivalently defined in terms of firms, and the lattice properties will
still hold true. Additionally, the lattice operations join and meet
distribute, i.e., given three stable matchings
$M,M^{\prime},M^{\prime\prime}$,

$M\vee(M^{\prime}\wedge M^{\prime\prime})=(M\vee M^{\prime})\wedge(M\vee
M^{\prime\prime})\ \ \mbox{and}\ \ M\wedge(M^{\prime}\vee
M^{\prime\prime})=(M\wedge M^{\prime})\vee(M\wedge M^{\prime\prime}).$

It is easy to see that the lattice must contain a matching, $M_{\top}$, that
dominates all others and a matching $M_{\bot}$ that is dominated by all
others. $M_{\top}$ is called the _worker-optimal stable matching_ , since in
it, each worker is matched to its most preferred firm among all stable
matchings. This is also the firm-pessimal stable matching. Similarly,
$M_{\bot}$ is the worker-pessimal and _firm-optimal stable matching_. And
since the number of matchings stable under any instance is finite, the stable
matching lattice is always a _finite distributive lattice_.

###  2.2 Birkhoff’s Theorem, sublattices and compressions

######  Definition 1.

A closed set of a poset is a set $S$ of elements of the poset such that if an
element is in $S$ then all of its predecessors are also in $S$.

It is easy to see that the family of closed sets (also called lower sets) of a
partial order, say $\Pi$, is closed under union and intersection and forms a
distributive lattice, with join and meet being these two operations,
respectively; let us denote it by $L(\Pi)$. Birkhoff’s theorem [Bir37], which
has also been called the fundamental theorem for finite distributive lattices,
e.g., see [Sta96], states that corresponding to any finite distributed
lattice, $\mathcal{L}$, there is a partial order, say $\Pi$, whose lattice of
closed sets $L(\Pi)$ is isomorphic to $\mathcal{L}$, i.e., $\mathcal{L}\cong
L(\Pi)$. We will say that $\Pi$ generates $\mathcal{L}$.

######  Theorem 2.

(Birkhoff [Bir37]) Every finite distributive lattice $\mathcal{L}$ is
isomorphic to $L(\Pi)$, for some finite poset $\Pi$.

A _join semi-sublattice_ $\mathcal{L}_{j}$ of a distributive lattice
$\mathcal{L}$ is a subset of $\mathcal{L}$ such that for any two elements
$x,y\in\mathcal{L}$, $x\vee y\in\mathcal{L}_{j}$ whenever
$x,y\in\mathcal{L}_{j}$. Similarly, _meet semi-sublattice_ $\mathcal{L}_{m}$
of a distributive lattice $\mathcal{L}$ is subset of $\mathcal{L}$ such that
for any two elements $x,y\in\mathcal{L}$, $x\wedge y\in\mathcal{L}_{m}$
whenever $x,y\in\mathcal{L}_{m}$. A _sublattice_ $\mathcal{L}^{\prime}$ of a
distributive lattice $\mathcal{L}$ is a subset of $L$ that is a join and meet
semi-sublattice of $\mathcal{L}$.

The _Hasse diagram_ of a poset is a directed graph with a vertex for each
element in poset, and an edge from $x$ to $y$ if $x\prec y$ and there is no
$z$ such that $x\prec z\prec y$, i.e., all precedences implied by transitivity
are suppressed.

Let $\mathcal{L}$ be the lattice generated by poset $\Pi$ and let $H(\Pi)$
denote the Hasse diagram of $\Pi$. Consider the following operations to derive
a new poset $\Pi^{\prime}$: Choose a set $E$ of directed edges and add them to
$H(\Pi)$. Let $H_{E}$ be the resulting graph. Let $H^{\prime}$ be the graph
obtained by shrinking the strongly connected components of $H_{E}$; let
$\Pi^{\prime}$ be the partial order defined by the non-shrunk edges of
$H^{\prime}$ on its nodes. Then $\Pi^{\prime}$ is called a _compression_ of
$\Pi$. Then

######  Theorem 3.

([GMRV22] Theorem 1) There is a one-to-one correspondence between the
compressions of $\Pi$ and the sublattices of $L(\Pi)$ such that if sublattice
$\mathcal{L}^{\prime}$ of $L(\Pi)$ corresponds to compression $\Pi^{\prime}$,
then $\mathcal{L}^{\prime}$ is generated by $\Pi^{\prime}$.

Let $\mathcal{L}^{\prime}$ be the sublattice of $\mathcal{L}$ generated by
$\Pi^{\prime}$. We will say that the set of edges $E$ _defines_
$\mathcal{L}^{\prime}$. It can be seen that, while a set of edges, $E$,
uniquely defines a sublattice $L(\Pi^{\prime})$, there may be multiple edge
sets that define the same sublattice.

One way to define partial order for the stable matching lattice is using the
concept of “rotations”. The partial order of rotations can be found
efficiently and has a succinct representation, even if the lattice itself is
exponentially large ([IL86]). [GI89] describes one of the many ways to
efficiently enumerate stable matchings using the rotation poset (algorithm in
Figure 3.8). Compressions defined on the rotation poset characterize
sublattices of the original lattice by grouping rotations into “meta-
rotations” and giving a partial order over them. Using poset of “meta-
rotations” instead of the rotation poset, we can efficiently enumerate
matchings in the _sublattice_. (Details about rotation poset can be found in
Appendix A, though they aren’t necessary for this paper).

###  2.3 Lattices of nearby instances

We will use the notation $\mathcal{M}_{I}$ and $\mathcal{L}_{I}$ to represent
the set of matchings stable with respect to an instance $I$ and its
corresponding lattice. Instances $A_{1},A_{2},\ldots,A_{k}(k\geq 2)$ are said
to be $(p,q)$, if they are all defined on the _same_ set of $n$ workers and
$n$ firms, and the _same_ set of $p$ workers and $q$ firms permute, possibly
back to the same preference, their preferences from any $A_{i}$ to $A_{j}$.
Let us consider two instances $A$ and $B$ that are $(0,1)$ or $(1,0)$.

As the number of matchings stable under an instance can be exponential in $n$,
checking the stability of every matching in $\mathcal{M}_{A}$ with respect to
$B$ can take exponential time. Nonetheless, the following results (statements
modified to suit the notation of this paper) from [GMRV22] reveal the
structure of such matchings and present polynomial time algorithms to find
them.

######  Theorem 4.

([GMRV22] Theorem 29) If a lattice $\mathcal{L}$ can be partitioned into a
sublattice $\mathcal{L}_{1}$ and a semi-sublattice $\mathcal{L}_{2}$, and
there is a polynomial time oracle that answers if any $x\in\mathcal{L}$ is in
$\mathcal{L}_{1}$ or $\mathcal{L}_{2}$, then, an edge set defining
$\mathcal{L}_{1}$ can be found in polynomial time.

######  Lemma 1.

If instances $A$ and $B$ are $(0,1)$(or $(1,0)$) then

  1. 1.

([GMRV22] Proposition 6)
$\mathcal{L}^{\prime}=\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a sublattice of
both $\mathcal{L}_{A}$ and $\mathcal{L}_{B}$.

  2. 2.

([GMRV22] Lemma 31) $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is a join(or
meet) semi-sublattice of $\mathcal{L}_{A}$.

  3. 3.

([GMRV22] Proposition 32) A set of edges defining the sublattice
$\mathcal{L}^{\prime}=\mathcal{M}_{A}\cap\mathcal{M}_{B}$ can be computed in
polynomial time.

These results can be extended to multiple instances in the following way. Let
$A,B_{1},B_{2},\ldots,B_{k}$ are such that each instance $B_{i}$ is formed
from instance $A$ by arbitrarily permuting the preference of one agent
(possibly a different agent for each $B_{i}$), i.e., $\forall
i\in\\{1,2,\ldots,k\\},A$ and $B_{i}$ are $(1,0)$ or $(0,1)$. Lemma 1 tells us
that each $\mathcal{L}_{i}=\mathcal{M}_{A}\cap\mathcal{M}_{B_{i}}$ is a
sublattice of $\mathcal{L}_{A}$. Let the edge set defining each
$\mathcal{L}_{i}$ be $E_{i}$ and let
$\mathcal{L}^{\prime}=\mathcal{M}_{A}\cap\mathcal{M}_{B_{1}}\cap\mathcal{M}_{B_{2}}\cap\ldots\cap\mathcal{M}_{B_{k}}$.
Then

######  Theorem 5.

  1. 1.

([GMRV22] Corollary 7) $\mathcal{L}^{\prime}$ is a sublattice of
$\mathcal{L}_{A}$.

  2. 2.

([GMRV22] Lemma 33) $E=\cup_{i}E_{i}$ defines $\mathcal{L}^{\prime}$.

  3. 3.

([GMRV22] Theorem 2) $E$, and hence the partial order $\Pi^{\prime}$
generating $L^{\prime}$, can be computed efficiently.

  4. 4.

([GI89] Theorem 3.5.1) Matchings in $\mathcal{L}^{\prime}$ can be enumerated
efficiently.

###  2.4 Linear programming formulation

Figure 1: Finding integral stable matching from a fractional solution(Picture
from [EIV23])

A well-known result about the stable matching problem is that it has a linear
programming formulation that has integral optimal vertices, which yields an
efficient algorithm to find the corresponding stable matchings. The
formulation of the LP 1 is given below. The third constraint disallows
blocking pairs, as an equivalent condition for a worker-firm pair $(w,f)$ to
not be a blocking pair of a matching $M$ under instance $A$ is to ensure that
if $w$ is matched to someone worse than $f$, then $f$ is matched to someone
better than $w$. The remaining conditions ensure that $x$ is a fractional
perfect matching.

max 0 (1) $\displaystyle\text{s.t.}\qquad\sum_{w}x_{wf}=1$ $\displaystyle\
\forall w\in W,$ $\displaystyle\sum_{f}x_{wf}=1$ $\displaystyle\ \forall f\in
F,$
$\displaystyle\sum_{f>^{A}_{w}f^{\prime}}x_{wf^{\prime}}-\sum_{w^{\prime}>^{A}_{f}w}x_{w^{\prime}f}\leq
0$ $\displaystyle\ \forall w\in W,\ \forall f\in F,$ $\displaystyle x_{wf}\geq
0,$ $\displaystyle\ \forall w\in W,\ \forall f\in F.$

A solution $x$ to the LP 1 can be converted into an integral perfect matching
in the following way. Construct $2n$ unit intervals, each corresponding to an
agent. For each worker, $w$, break its interval $I_{w}$ into $n$ subintervals,
each of length $x_{wf}$ (note that $\Sigma_{f}x_{wf}=1$) ordered from $w$’s
most preferred firm to the least. Repeat the same process with each firm $f$’s
interval $I_{f}$, but reverse the ordering of the subintervals from their
least to the most preferred worker. Choose $\theta$ uniformly at random from
the interval $[0,1]$, and determine which subinterval $\theta$ belongs to, in
each agent’s interval. The probability that any of these subintervals is of
zero length is zero, so we assume this case doesn’t happen. Given this, let
$\mu_{\theta}:\mathcal{W}\rightarrow\mathcal{F}$ represents the firm
corresponding to the subinterval containing $\theta$ for each worker and
$\mu^{\prime}_{\theta}:\mathcal{F}\rightarrow\mathcal{W}$ represents the
worker corresponding to the subinterval containing $\theta$ for each firm.
Then, these functions can be shown to be bijections (or perfect matchings). In
fact, they are inverses of each other and are stable for any $\theta\in[0,1]$.

######  Lemma 2.

[TS98] If $\mu_{\theta}(w)=f$ then $\mu^{\prime}_{\theta}(f)=w$.

######  Lemma 3.

[TS98] For each $\theta\in[0,1]$, $\mu_{\theta}$ is stable.

######  Theorem 6.

[Van89] The stable matching polytope given by LP 1 has integral optimal
vertices, i.e., it is a convex hull of stable matchings.

##  3 Setting I

In this setting, we look at instances with the same preferences on the
workers’ side and differing preferences on the firms’ side, i.e., instances
that are $(0,n)$. The case of $(n,0)$ is equivalent. We start by recalling the
following proposition from [GMRV22]. (All omitted proofs and examples can be
found in Appendix B, C and D).

######  Proposition 7.

([GMRV22] Proposition 6) If $A$ and $B$ are $(0,n)$ then the matchings in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ form a sublattice in each of the two
lattices.

The proposition shows that the join and meet of stable matchings in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ under the ordering of $\mathcal{L}_{A}$
are the same as in $\mathcal{L}_{B}$, which means that workers agree about
which stable matchings in the intersection they prefer. The main driver in
this setting is the fact that workers have the _same preferences_ across the
different instances, which allows us to use many arguments that apply to the
stable matching lattices of single instances. Additionally, the set
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ forms the same sublattice in
$\mathcal{L}_{A}$ as well as $\mathcal{L}_{B}$ in that the partial orders are
the same, that is
$(\mathcal{M}_{A}\cap\mathcal{M}_{B},\preceq_{A})=(\mathcal{M}_{A}\cap\mathcal{M}_{B},\preceq_{B})$.
This implies the existence of worker-optimal and firm-optimal stable matchings
in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ and indicates that we could expect a
version of the Deferred Acceptance algorithm to work in the setting.

This motivates the notion of a “compound” instance that captures agent
preferences from all individual instances, and we present a variant of the
Deferred Acceptance (DA) algorithm on this new instance that finds these
matchings. See Algorithm 8 that generates a compound instance.

######  Definition 2.

Let $A$ and $B$ be $(0,n)$. Define compound instance $X$ as follows:

  1. 1.

For worker $w\in\mathcal{W}$, their preference list in $X$ is the same as
their list in $A$ and $B$.

  2. 2.

For firm $f\in\mathcal{F}$, they prefer worker $w_{i}$ to worker $w_{j}$ in
$X$, if and only if they prefer $w_{i}$ to worker $w_{j}$ in $A$ as well as in
$B$, i.e.,

$\forall f\in\mathcal{F},\forall
w_{i},w_{j}\in\mathcal{W},w_{i}>^{X}_{f}w_{j}\Leftrightarrow(w_{i}>^{A}_{f}w_{j}\text{
and }w_{i}>^{B}_{f}w_{j})$

In the compound instance, workers have totally ordered preference lists while
firms have partially ordered preference lists. If a firm $f$ does not have a
strict preference between two workers $w_{i}$ and $w_{j}$ under $X$, we say
$f$ is indifferent between them and denote this $w_{i}\sim^{X}_{f}w_{j}$.

For matching $M$, the worker-firm pair $(w,f)\not\in M$, is said to be
_strongly blocking_ with respect to $M$ if $w$ prefers $f$ to its $M$-partner
and $f$ either prefers $w$ or is indifferent between $w$ and its $M$-partner.
A matching $M$ with no strong blocking pairs is said to be strongly stable
under $X$. Let $\mathcal{M}_{X}$ represent the set of matchings strongly
stable under preference profile $X$. The notion of compound instances is made
important in our context by the following lemma.

######  Lemma 4.

If $X$ is the compound instance of $A$ and $B$ then a matching $M$ is strongly
stable under $X$ if and only if it is stable under both $A$ and $B$, i.e.,
$\mathcal{M}_{X}=\mathcal{M}_{A}\cap\mathcal{M}_{B}$.

###  3.1 Worker and firm optimal matchings

WorkerOptimalForCompoundInstance($X$): Input: Compound stable matching
instance $X$ Output: Perfect matching $M$ or $\boxtimes$ Each worker has a
list of all firms in decreasing order of priority. 1. Until all workers
receive an acceptance or some worker is rejected by all firms, do: (a)
$\forall w\in W:w$ proposes to their best uncrossed firm. (b) $\forall f\in
F:f$ tentatively accepts their best-ever proposal, i.e., the proposal that
they strictly prefer to every other proposal ever received, and rejects the
rest. (c) $\forall w\in W:$ if $w$ is rejected by a firm $f$, they cross $f$
off their list. 2. If all workers got an acceptance, output the perfect
matching($M$); Else output $\boxtimes$. Figure 2: Algorithm to find the
worker-optimal stable matching using compound instance $X$
FirmOptimalForCompoundInstance($X$): Input: Compound stable matching instance
$X$. Output: Perfect matching $M$ or $\boxtimes$. Each firm has a DAG of all
workers in representing its partial order preferences. 1. Until all firms
receive an acceptance or some firm is rejected by all workers, do (a) $\forall
f\in F:f$ proposes to the “best” uncrossed workers, i.e., to every uncrossed
worker with no other strictly better uncrossed worker that they prefer. (b)
$\forall w\in W:w$ tentatively accepts the best proposal and rejects the rest.
(c) $\forall f\in F:$ if $f$ is rejected by a worker $w$, they cross $w$ off
their DAG. 2. If all firms received an acceptance, output the perfect
matching($M$); Else output $\boxtimes$ Figure 3: Algorithm to find the firm-
optimal stable matching using compound instance $X$

The original Deferred Acceptance Algorithm 7 works in iterations. In each
iteration, three steps happen. $(a)$ The proposing side, say workers, propose
to their best firm that hasn’t yet rejected them; $(b)$ Each firm tentatively
accepts their best proposal of the round and rejects all others;$(c)$ All
workers cross off the firms that rejected them; And the loop continues. If at
any point a perfect matching is found, that matching is outputted as stable.
The core reasoning of the algorithm is that whenever a rejection occurs, that
worker-firm pair can never be matched in any stable matching. We modify this
algorithm to find the worker and firm optimal stable matchings in the
intersection for the $(0,n)$ setting, aiming to prevent strong blocking pairs.

######  Theorem 8.

Algorithms 2 and 3 find the worker and firm optimal matchings respectively if
they exist.

The worker-optimal Algorithm 2 (equivalent to algorithms presented in [MO19,
FKJ16, GMRV22]) differs from the DA algorithm as follows. Every firm receives
a set of proposals from the workers and accepts a single proposal only if it
is strictly better than _every_ proposal it has _ever_ received, including
proposals in previous iterations. This prevents strong blocking pairs where
the firm is indifferent between its match and another worker. Observe that a
firm may end up rejecting all proposals in a round if they are indifferent
between the potential matches, and this is necessary to avoid strong blocking
pairs.

In firm optimal Algorithm 3 the firms propose, but they have a directed
acyclic graph (DAG) representing partial order preferences. Each firm proposes
to _all_ of the best uncrossed workers $w$ in their preference DAG, that is
all workers $w$ for whom there is no $w^{\prime}$ that $f$ strictly prefers,
i.e. $w^{\prime}>_{f}^{X}w$. As in the DA algorithm, workers accept their best
option and reject the rest. Since workers have completely ordered lists, when
a worker rejects a firm for a better match, they cannot form a blocking pair
with the rejected firm. The other possibility is when a firm proposes to
multiple workers who all tentatively accept their proposal. It must be the
case that one of these workers eventually rejects the firm for a better match,
or the algorithm terminates and returns no perfect matching. Note that when
instances $A$ and $B$ are the same, instance $X$ has total order preferences
on both sides and the algorithms revert to the original DA algorithm.

###  3.2 Birkhoff’s partial order

Note that when instances $A$ and $B$ are $(0,n)$, as Lemma 5 states and Figure
9 shows $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is not necessarily a semi-
sublattice of $\mathcal{L}_{A}$.

######  Lemma 5.

If $A$ and $B$ are $(0,n)$, then $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is
not always a semi-sublattice of $\mathcal{L}_{A}$.

This shows that Theorem 4 cannot be used directly to find Birkhoff’s partial
order. To get around this, we define $n$ hybrid instances,
$B_{1},\dots,B_{n}$, so that $A$ and $B_{i}$ are $(0,1)$,$\forall
i\in\\{1,2,\ldots,n\\}$. Specifically, the preference profile of agent $x$ in
instance $B_{i}$ is given by

$>_{x}^{B_{i}}=\left\\{\begin{array}[]{lr}>_{x}^{B},&\text{if }x={f_{i}}\\\
>_{x}^{A},&\text{if }x\neq{f_{i}}\end{array}\right\\}$

i.e., instance $B_{i}$ is exactly the same as instance $A$ except for the
preferences of firm $f_{i}$ where it is like instance $B$. Defined this way,
Theorem 9 states that matchings that are stable under both $A$ and $B$ are
exactly those that are stable under $A$, $B_{1},B_{2},\dots$ and $B_{n}$.

######  Theorem 9.

$\mathcal{M}_{A}\cap\mathcal{M}_{B}=\mathcal{M}_{A}\cap\mathcal{M}_{B_{1}}\cap\mathcal{M}_{B_{2}}\cap\ldots\cap\mathcal{M}_{B_{n}}$

######  Theorem 10.

If $A$ and $B$ are $(0,n)$, Birkhoff’s partial order generating
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ can be computed efficiently and the
matchings can be enumerated efficiently.

###### Proof.

Since each $B_{i}$ differs from instance $A$ at only exactly agent, we first
use Lemma 1 to find the edge sets $E_{i}$ representing
$\mathcal{M}_{A}\cap\mathcal{M}_{B_{i}}$. From Theorem 5, the union of these
edge sets define the sublattice $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ and can
be used to enumerate the matchings efficiently. ∎

###  3.3 Extension to Multiple Instances

The results extend to multiple instances. Let $A_{1},A_{2},\ldots,A_{k}$ all
be $(0,n)$. Then

######  Theorem 11.

$\mathcal{L}^{\prime}=\mathcal{M}_{A_{1}}\cap\mathcal{M}_{A_{2}}\cap\ldots\cap\mathcal{M}_{A_{k}}$
is a sublattice of each of $\mathcal{L}_{A_{i}}$. The worker and firm optimal
matchings of $\mathcal{L}^{\prime}$ and Birkhoff’s partial order can be found
in polynomial time and its matchings can be enumerated with polynomial delay.

######  Corollary 1.

Strongly stable matchings of an instance $Y$ with partial order preferences on
one-side form a lattice. Each partial order has a finite number of linear
extensions and it follows that for any instance $Y$, $\mathcal{M}_{Y}$, can be
written as an intersection of finitely many lattices. But since the number of
linear extensions can be exponential in $n$, this does not give an efficient
way to derive its Birkhoff’s partial order.

##  4 Setting II

In the setting , both workers and firms are allowed to have different
preferences going from instance $A$ to $B$. This is the most general setting
possible as $A$ and $B$ do not need to have any similarity apart from being
defined over the same universe of agents.

We will demonstrate examples that show that the _join_ and _meet_ operations
are no longer equivalent in $\mathcal{L}_{A}$ and $\mathcal{L}_{B}$. As a
result the argument used in the previous setting in Proposition 7 does not
extend. In fact for stable matchings
$M,M^{\prime}\in\mathcal{M}_{A}\cap\mathcal{M}_{B}$, it may be the case that
some workers prefer $M$ to $M^{\prime}$ in $A$ but prefer $M^{\prime}$ to $M$
in $B$, which is not possible in Setting I. Specifically even if the
intersection is a sublattice, the base set is
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$, but the partial orders
$\leq_{A}\neq\leq_{B}$ may be different.

A trial-and-error approach shows that the intersection may be a sublattice for
many instances. The structure of the sublattice may be more general as the
_join_ and _meet_ operators may not be equivalent in $\mathcal{L}_{A}$ and
$\mathcal{L}_{B}$ (i.e., $(\vee_{A},\wedge_{A})\neq(\vee_{B},\wedge_{B})$).
The example in Figure 10 demonstrates this where the intersection is a
sublattice, but the partial ordering of the stable matchings in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ differs.

Instance $B$ is obtained from instance $A$ by permuting the preferences of
workers $1$ and $2$, and firms $a$ and $b$. It can be seen that taking the
join (or meet) of any two matchings in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$
yields another matching in the intersection regardless of which instance you
consider, however workers $1$ and $2$ prefer $M_{2}$ to $M_{1}$ in $A$ while
they prefer $M_{1}$ to $M_{2}$ in $B$. Figure 4 illustrates this change in the
partial ordering of matchings in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$
depending on the underlying instance.

$M_{1}=\\{1b,2a,3d,4c,5e,6f\\}$ and $M_{2}=\\{1a,2b,3c,4d,5f,6e\\}$ are both
stable under $A$ and $B$.
$X_{1}=M_{1}\wedge_{A}M_{2}=\\{1a,2b,3c,4d,5e,6f\\}$ and
$X_{2}=M_{1}\vee_{A}M_{2}=\\{1b,2a,3d,4c,5f,6e\\}$.
$Y_{1}=M_{1}\wedge_{B}M_{2}=\\{1b,2a,3c,4d,5e,6f\\}$ and
$Y_{2}=M_{1}\vee_{B}M_{2}=\\{1a,2b,3d,4c,5f,6e\\}$.

pt$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y_{1}$pt$X_{1}$pt$M_{2}$ptpt$M_{1}$ptpt$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y_{2}$pt$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}X_{2}$

pt$M_{1}$pt$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y_{1}$pt$X_{1}$ptpt$X_{2}$ptpt$M_{2}$pt$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Y_{2}$

Figure 4: Lattices $\mathcal{L}_{A}$ and $\mathcal{L}_{B}$ from Example 10

######  Theorem 12.

If $A$ and $B$ are $(p,q)$ with $p,q\geq 2$, then
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ may not be a sublattice of
$\mathcal{L}_{A}$.

But, as theorem 12 states, it is not always the case that the intersection is
a sublattice. So, we have seen that for $(0,n)$, the intersection is a
sublattice, but for $(2,2)$, it is not. The following question arises - what
is the boundary where the property of “the intersection is a sublattice”
breaks? We will show that for $(1,n)$ the intersection is still a sublattice.
Let $\mathcal{W}=\\{w_{1},w_{2},\ldots,w_{n}\\}$ and
$\mathcal{F}=\\{f_{1},f_{2},\ldots,f_{n}\\}$. Let $A$ and $B$ be stable
matching instances on $\mathcal{W}$ and $\mathcal{F}$ with $w_{1}$ and an
arbitrary number of firms might permute their preferences from $A$ to $B$ \-
$A$ and $B$ are $(1,n)$.

######  Theorem 13.

If $A$ and $B$ are $(1,n)$, then $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a
sublattice of both $\mathcal{L}_{A}$ and $\mathcal{L}_{B}$.

###### Proof.

Without loss of generality, assume $|\mathcal{M}_{A}\cap\mathcal{M}_{B}|>1$
and let $M_{1}$ and $M_{2}$ be two different matchings in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$. Let $\vee_{A}$ and $\vee_{B}$ be the
join operations under $A$ and $B$ respectively. Likewise, let $\wedge_{A}$ and
$\wedge_{B}$ be the meet operations under $A$ and $B$.

$M_{1}\vee_{A}M_{2}$ is the matching obtained by assigning each worker to its
less preferred partner from $M_{1}$ and $M_{2}$ according to instance $A$.
Since the preferences of workers $w_{2},w_{3},\ldots,w_{n}$ are identical in
$A$ and $B$, each of their less preferred partner from $M_{1}$ and $M_{2}$ are
also the same in $A$ and $B$ so $\forall w\neq
w_{1},(M_{1}\vee_{A}M_{2})(w)=(M_{1}\vee_{B}M_{2})(w)$. $M_{1}\vee_{A}M_{2}$
and $M_{1}\vee_{B}M_{2}$ are stable matchings under their respective instances
and so, are also perfect. Since each of the above $n-1$ workers is assigned
the same partner in both the perfect matchings, the $n^{th}$ worker, $w_{1}$
should also be assigned the same remaining firm as its partner in both
matchings.

Therefore, $M_{1}\vee_{A}M_{2}=M_{1}\vee_{B}M_{2}$. A similar argument can be
applied to show that $M_{1}\wedge_{A}M_{2}=M_{1}\wedge_{B}M_{2}$. Hence, the
operators _join_ and _meet_ under instances $A$ and $B$ are equivalent and
$M_{1}\vee_{A}M_{2}$ and $M_{1}\wedge_{A}M_{2}$ are both in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$. The theorem follows. ∎

###  4.1 Worker and Firm Optimal Algorithms

Theorem 13 indicates that if instances $A$ and $B$ have different preference
profiles for $n$ firms and one worker, the notion of worker and form-optimal
stable matchings is valid. However, constructing a compound instance does not
work as the characterization used in Lemma 4 does not extend when there are
partially ordered preferences on both sides. Instead, we exploit the fact that
the partial order of stable matchings in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$
is the same in $\mathcal{L}_{A}$ as in $\mathcal{L}_{B}$. Specifically, the
matching $M\in\mathcal{M}_{A}\cap\mathcal{M}_{B}$ that is optimal for workers
according to their preferences in $A$, is optimal for workers according to
their preferences in $B$ as well.

######  Theorem 14.

Algorithms 5 and 6 find the worker and firm optimal matchings respectively if
they exist.

The worker optimal algorithm runs the DA algorithm simultaneously in multiple
rooms, where the preference lists for each room correspond to individual
instances. Agents consider the preferences based on the rooms and in each
room, workers propose and firms tentatively accept their best proposals and
reject the rest - however, the rejections apply across all rooms. For example,
if a worker is rejected by a firm in room $R_{A}$, they cross that firm off
their list in _all_ rooms. This ensures that if a perfect matching is found,
it is stable with respect to all instances. The main issue that needs to be
dealt with is the possibility of the algorithm terminating with distinct
perfect matchings in different rooms. Lemma 20 shows that this outcome is not
possible, and this is largely a consequence of the fact that the intersection
has the same partial order in both lattices.

The firm optimal algorithm operates similarly with the firms proposing and the
workers tentatively accepting. The key modification here is that when workers
reject firms, they _preemptively_ reject _all_ other firms that are worse
according to their list in _all_ rooms, including firms that haven’t proposed
to them yet. This step ensures the same perfect matching is found in all the
rooms.

WorkerOptimal($A,B$): Input: Stable matching instances $A$ and $B$ Output:
Perfect matching $M$ or $\boxtimes$ or “No Idea” Assume there are two rooms,
$\mathcal{R}_{A}$ and $\mathcal{R}_{B}$ corresponding to instances $A$ and $B$
respectively. Each worker has a list, initialized to all firms, that they look
at while proposing. 1. Until there is no rejection in any room or some worker
is rejected by all firms, do: (a) $\forall I\in\\{A,B\\},\forall w\in W:w$
proposes to their best-in-$I$ uncrossed firm in $\mathcal{R}_{I}$. (b)
$\forall I\in\\{A,B\\},\forall f\in F:f$ tentatively accepts their best-in-$I$
proposal in room $\mathcal{R}_{I}$ and rejects the rest. (c) $\forall w\in W:$
if $w$ is rejected by a firm $f$ in any room, they cross $f$ off their list.
2. (a) If some worker is rejected by all firms, output $\boxtimes$. (b) Else,
the acceptances define perfect matchings in each room. If they are the same in
all rooms, output the perfect matching($M$). If not, output “No Idea”. Figure
5: Algorithm to find the worker-optimal stable matching. Note that
proposers(workers) have a single list(/set) across rooms. They might propose
to different firms in different rooms but they look at all the rejections and
synchronize their lists in step 2(c). FirmOptimal($A,B$): Input: Stable
matching instances $A$ and $B$ Output: Perfect matching $M$ or $\boxtimes$ or
“No Idea” Assume there are two rooms, $\mathcal{R}_{A}$ and $\mathcal{R}_{B}$
corresponding to instances $A$ and $B$ respectively. Each firm has a list,
initialized to all workers, that they look at while proposing. 1. Until there
is no rejection in any room or some firm is rejected by all firms, do: (a)
$\forall I\in\\{A,B\\},\forall f\in F:f$ proposes to their best-in-$I$
uncrossed worker in $\mathcal{R}_{I}$. (b) $\forall I\in\\{A,B\\},\forall w\in
W:w$ tentatively accepts their best-in-$I$ proposal (call it $f^{I}_{w}$) in
room $\mathcal{R}_{I}$ and rejects the rest. (c) $\forall
I\in\\{A,B\\},\forall w\in W:w$ sends preemptive rejections to all
$f^{\prime}$ that they haven’t rejected already, who are worse than their
current option in $\mathcal{R}_{I}$, i.e., $f^{I}_{w}\geq^{I}_{w}f^{\prime}$.
(d) $\forall f\in F:$ if $f$ is rejected by a worker $w$ in some room, they
cross $w$ off their list. 2. (a) If some firm is rejected by all workers,
output $\boxtimes$. (b) Else, the acceptances define perfect matchings in each
room. If they are the same in all rooms, output the perfect matching($M$). If
not, output “No Idea”. Figure 6: Algorithm to find the firm-optimal stable
matching. Note that, in step 2(c), workers may send rejections to firms that
haven’t yet proposed to them.

###  4.2 Birkhoff’s partial order

Let $w_{1}\in W,f_{1},\dots,f_{n}\in F$ be the workers and firms who have
different preferences in $A$ and $B$. We use an idea similar to that in
Section 3.2. Let $B_{X}$ denote the stable matching instance where the
preference lists of all agents in $X$ are the same as in $B$, and for the
remaining agents are the same as in $A$. Then,

######  Theorem 15.

$\mathcal{M}_{A}\cap\mathcal{M}_{B}=\mathcal{M}_{A}\cap\mathcal{M}_{B_{\\{w_{1},f_{1}\\}}}\cap\mathcal{M}_{B_{\\{w_{1},f_{2}\\}}}\cap\dots\cap\mathcal{M}_{B_{\\{w_{1},f_{n}\\}}}$.

######  Corollary 2.

Finding Birkhoff’s partial order for $(1,n)$ is in $\cal P$ if and only if
finding Birkhoff’s partial order for $(1,1)$ is in $\cal P$.

The characterization requires that the smaller instances include changes from
a worker and a firm. Certain blocking pairs are introduced in instance $B$
only when a worker _and_ a firm involved have modified lists, and this cannot
be captured when the changes are restricted to one side.

######  Lemma 6.

If $A$ and $B$ are $(1,1)$, then $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is
not always a semi-sublattice of $\mathcal{L}_{A}$.

However unlike in (0,1), $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is not
always a semi-sublattice in $(1,1)$; see example in Figure 12. As a result,
Theorem 4 cannot be used here and the problem of finding Birkhoff’s partial
order for (1,1), and hence $(n,1)$, remains open along with finding a way to
enumerate the matchings in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ with
polynomial delay.

###  4.3 LP-Approach

For a single stable matching instance, there is a linear programming
formulation where the vertices of the polyhedron are _integral_ (see Section
2.4), yielding an efficient way to find stable matchings. We will similarly
define a linear program whose integral optimal vertices correspond to stable
matchings under instances $A$ and $B$.

The linear program is given below - the first two and last constraints ensure
that any solution $x$ is a fractional perfect matching, and the remaining two
constraints prevent blocking pairs with respect to either instance.

max 0 (2) $\displaystyle\text{s.t.}\qquad\sum_{w}x_{wf}=1$ $\displaystyle\
\forall w\in W,$ $\displaystyle\sum_{f}x_{wf}=1$ $\displaystyle\ \forall f\in
F,$
$\displaystyle\sum_{f>^{A}_{w}f^{\prime}}x_{wf^{\prime}}-\sum_{w^{\prime}>^{A}_{f}w}x_{w^{\prime}f}\leq
0$ $\displaystyle\ \forall w\in W,\ \forall f\in F,$
$\displaystyle\sum_{f>^{B}_{w}f^{\prime}}x_{wf^{\prime}}-\sum_{w^{\prime}>^{B}_{f}w}x_{w^{\prime}f}\leq
0$ $\displaystyle\ \forall w\in W,\ \forall f\in F,$ $\displaystyle x_{wf}\geq
0,$ $\displaystyle\ \forall w\in W,\ \forall f\in F.$

A solution to Equation 2 is clearly a fractional stable matching under both
$A$ and $B$. Choose $\theta\in[0,1]$ with uniform probability and construct
two integral perfect matchings $\mu^{A}_{\theta}$ and $\mu^{B}_{\theta}$ as
explained in Section 2.4.

######  Lemma 7.

The two integral perfect matchings are identical, i.e.,
$\mu^{A}_{\theta}=\mu^{B}_{\theta}$.

######  Corollary 3.

$\mu^{A}_{\theta}$ $(=\mu^{B}_{\theta})$ is stable under both $A$ and $B$ and
the polyhedron described by LP 2 has integer optimal vertices.

This means the LP can be used to find a stable matching in the setting
$(1,n)$(and so, also for $(0,n)$). Note that the method no longer works for
$(2,2)$\- the proof of Lemma 7 does not hold anymore. For this reason, we
believe that the polyhedron here might not have integral vertices.

###  4.4 Extension to Multiple instances

The results from this section extend from two instances to multiple instances.
Let $A_{1},A_{2},\ldots,A_{k}$ be $k$ stable matching instances which are all
$(1,n)$, i.e., $n-1$ of the $n$ workers have the same preference profiles in
all of them. Then

######  Theorem 16.

$\mathcal{L}^{\prime}=\mathcal{M}_{A_{1}}\cap\mathcal{M}_{A_{2}}\cap\ldots\cap\mathcal{M}_{A_{k}}$
is a sublattice of each of $\mathcal{L}_{A_{i}}$. The LP formulation can be
used to find stable matchings in $\mathcal{L}^{\prime}$ and the worker and
firm optimal matchings can be found in polynomial time.

## References

  * [Bir37] Garrett Birkhoff.  Rings of sets.  Duke Mathematical Journal, 3(3):443–454, 1937.
  * [Bla84] Charles Blair.  Every finite distributive lattice is a set of stable matchings.  Journal of Combinatorial Theory, Series A, 37(3):353–356, 1984\.
  * [CNS18] Jiehua Chen, Rolf Niedermeier, and Piotr Skowron.  Stable marriage with multi-modal preferences.  In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, page 269–286, New York, NY, USA, 2018. Association for Computing Machinery.
  * [CSS21] Jiehua Chen, Piotr Skowron, and Manuel Sorge.  Matchings under preferences: Strength of stability and tradeoffs.  ACM Trans. Econ. Comput., 9(4), oct 2021.
  * [EIV23] Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani, editors.  Online and Matching-Based Market Design.  Cambridge University Press, 2023.
  * [FKJ16] Linda Farczadi, Georgiou Konstantinos, and Könemann Jochen.  Stable marriage with general preferences.  Theory of Computing Systems, 59(4):683–699, 2016.
  * [ftToC19] Simons Institute for the Theory of Computing.  Online and matching-based market design, 2019.  https://simons.berkeley.edu/programs/market2019.
  * [GI89] Dan Gusfield and Robert W Irving.  The stable marriage problem: structure and algorithms.  MIT press, 1989.
  * [GMRV22] Rohith Reddy Gangam, Tung Mai, Nitya Raju, and Vijay V. Vazirani.  A Structural and Algorithmic Study of Stable Matching Lattices of ”Nearby” Instances, with Applications.  In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), 2022.
  * [GS62] David Gale and Lloyd S Shapley.  College admissions and the stability of marriage.  The American Mathematical Monthly, 69(1):9–15, 1962.
  * [IL86] Robert W Irving and Paul Leather.  The complexity of counting stable marriages.  SIAM Journal on Computing, 15(3):655–667, 1986.
  * [KVV90] Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358. ACM, 1990.
  * [MO19] Shuichi Miyazaki and Kazuya Okamoto.  Jointly stable matchings.  J. Comb. Optim., 38(2):646–665, 2019.
  * [MV18] Tung Mai and Vijay V. Vazirani.  Finding stable matchings that are robust to errors in the input.  In European Symposium on Algorithms, 2018.
  * [Sta96] Richard Stanley.  Enumerative combinatorics, vol. 1, Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986; second printing, 1996.
  * [TS98] Chung-Piaw Teo and Jay Sethuraman.  The geometry of fractional stable matchings and its applications.  Mathematics of Operations Research, 23(4):874–891, 1998.
  * [Van89] John H. Vande Vate.  Linear programming brings marital bliss.  Operations Research Letters, 8(3):147–153, 1989.

##  Appendix A The Partial Order of Rotations

DeferredAcceptanceAlgorithm($A$): Input: Stable matching instance $A$ Output:
Perfect matching $M$ Each worker has a list of all firms in decreasing order
of priority. 1. Until all firms receive a proposal, do: (a) $\forall w\in W,w$
proposes to their best uncrossed firm. (b) $\forall f\in F,f$ tentatively
accepts their best proposal and rejects the rest. (c) $\forall w\in W,$ if $w$
is rejected by a firm $f$, they cross $f$ off their list. 2. Output the
perfect matching($M$). Figure 7: Deferred Acceptance Algorithm with workers
proposing, taken from [EIV23] CompoundInstance($A,B$): Input: Stable matching
instances $A$ and $B$ with same preferences on the workers’ side. Output:
Instance $X$. 1. $\forall w\in W,w$’s preferences in $X$ are the same as in
$A$ and $B$. 2. $\forall f\in F,\forall w_{i},w_{j}\in W,w_{i}>_{f}^{X}w_{j}$
if and only if $w_{i}>_{f}^{A}w_{j}$ and $B\in S,w_{i}>_{f}^{B}w_{j}$ 3.
Return $X$. Figure 8: Subroutine for constructing a compound instance.

For the lattice of stable matchings, the partial order $\Pi$ defined in
Birkhoff’s Theorem has additional useful structural properties. First, its
elements are rotations. A rotation takes $r$ matched worker-firm pairs in a
fixed order, say $\\{w_{0}f_{0},w_{1}f_{1},\ldots,w_{r-1}f_{r-1}\\}$, and
“cyclically” changes the matches of these $2r$ agents. The number $r$, the $r$
pairs, and the order among the pairs are so chosen that when a rotation is
applied to a stable matching containing all $r$ pairs, the resulting matching
is also stable; moreover, there is no valid rotation on any subset of these
$r$ pairs, under any ordering. Hence, a rotation can be viewed as a minimal
change to the current matching that results in a stable matching.

Any worker–firm pair, $(w,f)$, belongs to at most one rotation. Consequently,
the set $R$ of rotations underlying $\Pi$ satisfies $|R|$ is $O(n^{2})$, and
hence, $\Pi$ is a succinct representation of $\mathcal{L}$; the latter can be
exponentially large. $\Pi$ will be called the rotation poset for
$\mathcal{L}$.

Second, the rotation poset helps traverse the lattice as follows. For any
closed set $S$ of $\Pi$, the corresponding stable matching $M(S)$ can be
obtained as follows: start from the worker-optimal matching in the lattice and
apply the rotations in set $S$, in any topological order consistent with
$\Pi$. The resulting matching will be $M(S)$. In particular, applying all
rotations in $R$, starting from the worker-optimal matching, leads to the
firm-optimal matching.

The following process yields a rotation for a stable matching $M$. For a
worker $w$ let $s_{M}(w)$ denote the first firm $f$ on $w$’s list such that
$f$ strictly prefers $w$ to its $M$-partner. Let $next_{M}(w)$ denote the
partner in $M$ of firm $s_{M}(f)$. A _rotation_ $\rho$ _exposed_ in $M$ is an
ordered list of pairs $\\{w_{0}f_{0},w_{1}f_{1},\ldots,w_{r-1}f_{r-1}\\}$ such
that for each $i$, $0\leq i\leq r-1$, $w_{i+1}$ is $next_{M}(w_{i})$, where
$i+1$ is taken modulo $r$. In this paper, we assume that the subscript is
taken modulo $r$ whenever we mention a rotation. Notice that a rotation is
cyclic and the sequence of pairs can be rotated. $M/\rho$ is defined to be a
matching in which each worker not in a pair of $\rho$ stays matched to the
same firm and each worker $w_{i}$ in $\rho$ is matched to
$f_{i+1}=s_{M}(w_{i})$. It can be proven that $M/\rho$ is also a stable
matching. The transformation from $M$ to $M/\rho$ is called the _elimination_
of $\rho$ from $M$.

######  Lemma 8 ([GI89], Theorem 2.5.4).

Every rotation appears exactly once in any sequence of elimination from
$M_{0}$ to $M_{z}$.

Let $\rho=\\{w_{0}f_{0},w_{1}f_{1},\ldots,w_{r-1}f_{r-1}\\}$ be a rotation.
For $0\leq i\leq r-1$, we say that $\rho$ _moves $w_{i}$ from $f_{i}$ to
$f_{i+1}$_, and _moves $f_{i}$ from $w_{i}$ to $w_{i-1}$_. If $f$ is either
$f_{i}$ or is strictly between $f_{i}$ and $f_{i+1}$ in $w_{i}$’s list, then
we say that $\rho$ _moves $w_{i}$ below $f$_. Similarly, $\rho$ _moves $f_{i}$
above_ $w$ if $w$ is $w_{i}$ or between $w_{i}$ and $w_{i-1}$ in $f_{i}$’s
list.

###  A.1 The rotation poset

A rotation $\rho^{\prime}$ is said to _precede_ another rotation $\rho$,
denoted by $\rho^{\prime}\prec\rho$, if $\rho^{\prime}$ is eliminated in every
sequence of eliminations from $M_{0}$ to a stable matching in which $\rho$ is
exposed. If $\rho^{\prime}$ precedes $\rho$, we also say that $\rho$
_succeeds_ $\rho^{\prime}$. If neither $\rho^{\prime}\prec\rho$ nor
$\rho^{\prime}\succ\rho$, we say that $\rho^{\prime}$ and $\rho$ are
_incomparable_ Thus, the set of rotations forms a partial order via this
precedence relationship. The partial order on rotations is called _rotation
poset_ and denoted by $\Pi$.

######  Lemma 9 ([GI89], Lemma 3.2.1).

For any worker $w$ and firm $f$, there is at most one rotation that moves $w$
to $f$, $w$ below $f$, or $f$ above $w$. Moreover, if $\rho_{1}$ moves $w$ to
$f$ and $\rho_{2}$ moves $w$ from $f$ then $\rho_{1}\prec\rho_{2}$.

######  Lemma 10 ([GI89], Lemma 3.3.2).

$\Pi$ contains at most $O(n^{2})$ rotations and can be computed in polynomial
time.

Consequently, $\Pi$ is a succinct representation of $\mathcal{L}$; the latter
can be exponentially large. And rotations also help in the efficient
enumeration of stable matchings([GI89], Chapter 3.5). If we know the edge set
defining a sublattice(see 2.3 for definition) $\mathcal{L}^{\prime}$ of a
stable matching lattice, the corresponding compression defines a partial order
on the “meta-rotations”(groups of rotations). This new partial order can be
used to efficiently enumerate the matchings in sublattice
$\mathcal{L}^{\prime}$.

##  Appendix B Examples and Figures

1 a b d c e 2 b a c d e 3 c d b a e 4 b d c a e 5 c e a b c workers’
preferences in $A$ a 4 2 1 3 5 b 3 1 2 4 5 c 2 4 3 1 5 d 1 3 4 2 5 e 5 1 2 3 4
firms’ preferences in $A$ a 4 2 1 3 5 b 1 4 2 3 5 c 4 5 3 1 2 d 1 3 4 2 5 e 5
1 2 3 4 firms’ preferences in $B$ Figure 9:
$\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is not a semi-sublattice of
$\mathcal{L}_{A}$. Preferences are in decreasing order. 1 a b c d e f 2 b a c
d e f 3 c d a b e f 4 d c a b e f 5 e f a b c d 6 f e a b c d workers’
preferences in $A$ a 2 1 3 4 5 6 b 1 2 3 4 5 6 c 4 3 1 2 5 6 d 3 4 1 2 5 6 e 6
5 1 2 3 4 f 5 6 1 2 3 4 firms’ preferences in $A$ 1 b a c d e f 2 a b c d e f
3 c d a b e f 4 d c a b e f 5 e f a b c d 6 f e a b c d workers’ preferences
in $B$ a 1 2 3 4 5 6 b 2 1 3 4 5 6 c 4 3 1 2 5 6 d 3 4 1 2 5 6 e 6 5 1 2 3 4 f
5 6 1 2 3 4 firms’ preferences in $B$ Figure 10: Worker and firm
preferences(from most preferred to least) 1 a b c d 2 b c a d 3 d c a b 4 c d
a b workers’ preferences in $A$ a 2 4 1 3 b 1 2 3 4 c 3 4 2 1 d 4 3 2 1 firms’
preferences in $A$ 1 a b c d 2 b c a d 3 c d a b 4 d a c b workers’
preferences in $B$ a 2 4 1 3 b 1 2 3 4 c 4 2 3 1 d 3 4 1 2 firms’ preferences
in $B$ Figure 11:  $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is not a sublattice of
$\mathcal{L}_{A}$. Preferences are in decreasing order. 1 a b c d e 2 b c a d
e 3 c a b d e 4 d c e a b 5 e d a b c workers’ preferences in $A$ a 2 3 1 4 5
b 3 1 2 4 5 c 1 2 3 4 5 d 5 3 4 1 2 e 4 5 1 2 3 firms’ preferences in $A$ 1 a
b c d e 2 b c a d e 3 c d a b e 4 d c e a b 5 e d a b c workers’ preferences
in $B$ a 2 4 1 3 5 b 1 2 3 4 5 c 1 4 3 2 5 d 5 3 4 1 2 e 4 5 1 2 3 firms’
preferences in $B$ Figure 12:  $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is
not a sublattice of $\mathcal{L}_{A}$ even when the setting is $(1,1)$

##  Appendix C Omitted Proofs

###### Proof of Proposition 7.

If $|\mathcal{M}_{A}\cap\mathcal{M}_{B}|\leq 1$,
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is a trivial sublattice of
$\mathcal{L}_{A}$ and $\mathcal{L}_{B}$. So, assume
$|\mathcal{M}_{A}\cap\mathcal{M}_{B}|>1$ and let $M_{1}$ and $M_{2}$ be
matchings in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$. Let $\vee_{A}$ and
$\vee_{B}$ be the join operations under $A$ and $B$ respectively, and let
$\wedge_{A}$ and $\wedge_{B}$ be the meet operations under $A$ and $B$.

By definition of join operation in Section 2.1, $M_{1}\vee_{A}M_{2}$ is the
matching obtained by assigning each worker to its less preferred partner (or
equivalently, each firm to its more preferred partner) from $M_{1}$ and
$M_{2}$ according to instance $A$. Since the list of each worker is identical
in $A$ and $B$, its less preferred partner from $M_{1}$ and $M_{2}$ is also
the same in $A$ and $B$. Therefore, $M_{1}\vee_{A}M_{2}=M_{1}\vee_{B}M_{2}$. A
similar argument can be applied to show that
$M_{1}\wedge_{A}M_{2}=M_{1}\wedge_{B}M_{2}$. Hence, $M_{1}\vee_{A}M_{2}$ and
$M_{1}\wedge_{A}M_{2}$ are both in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$
proving that $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ forms a sublattice in each
of the two lattices. ∎

###### Proof of Lemma 4.

Let $(w,f)$ be a strong blocking pair for matching $M$ under $X$. As $w$ has
the same preference lists in $A$ and $B$, they must strictly prefer $f$ to
$M(w)$ in both instances. $f$ must either strictly prefer $w$ to its
$M$-partner or is indifferent between them. In both cases, $f$ must prefer $w$
to its $M$-partner in at least one of $A$ and $B$. Hence $(w,f)$ is a blocking
pair for $M$ under that instance. The other direction follows along similar
lines. ∎

###### Proof of Lemma 5.

Consider instances $A$ and $B$ as given in Figure 9. The set of workers is
$\mathcal{W}=\\{1,2,3,4,5\\}$ and the set of firms is
$\mathcal{F}=\\{a,b,c,d,e\\}$. Instance $B$ is obtained from instance $A$ by
permuting firm $b$ and $c$’s lists. Consider matchings
$M_{1}=\\{1b,2a,3c,4d,5e\\}$ and $M_{2}=\\{1a,2b,3d,4c,5e\\}$ that are both
stable matchings with respect to instance $A$. With respect to instance $B$,
$M_{1}$ has blocking pair $(5,c)$ and $M_{2}$ has blocking pair $(4,b)$. Hence
$M_{1}$ and $M_{2}$ are both in $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$.
However, the _join_ with respect to $A$ is
$M_{1}\vee_{A}M_{2}=\\{1b,2a,3d,4c,5e\\}$ which is stable with respect to $A$
and $B$.

Similarly, we see that $M_{3}=\\{1b,2c,3d,4a,5e\\}$ and
$M_{4}=\\{1d,2a,3b,4c,5e\\}$ are stable with respect to $A$ but have blocking
pairs $(1,a)$ and $(4,d)$ respectively, under $B$. However, their _meet_ ,
$M_{3}\vee_{A}M_{4}=\\{1b,2a,3d,4c,5e\\}$ is stable with respect to $A$ and
$B$.

Hence $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is not a semi-sublattice of
$\mathcal{L}_{A}$. ∎

###### Proof of Theorem 9.

We will show that any blocking pair for a perfect matching under the
preference lists of instance $A$ or instance $B$ is a blocking pair under the
preference lists of at least one of the instances $A$ and $B_{1},\dots,B_{n}$,
and vice versa.

Let $M$ be a perfect matching with a blocking pair under the preference lists
in $A$ or in $B$. If it has a blocking pair under $A$, then $M$ is clearly not
in $\mathcal{M}_{A}\cap\mathcal{M}_{B_{1}}\cap\ldots\cap\mathcal{M}_{B_{n}}$.
Suppose $(w,f)$ be a blocking pair for $B$ and $f>_{w}^{B}M(w)$ and so,
$w>_{f}^{B}M(f)$. Workers have identical lists in all instances, so $w$
prefers $f$ to $M(w)$ in every instance $B_{i}$. Firm $f$ has the same
preference list in $B$ and in $B_{k}$ for some $k\in\\{1,\dots,n\\}$. Then
$w>_{f}^{B_{k}}M(f)$ and $(w,f)$ is a blocking pair for instance $B_{k}$, so
$M$ is not a stable matching in
$\mathcal{M}_{A}\cap\mathcal{M}_{B_{1}}\cap\ldots\cap\mathcal{M}_{B_{n}}$

Let $M$ be a perfect matching with blocking pair $(w,f)$ under the preference
lists in one of the instances $A,B_{1},\dots,B_{n}$. As in the previous case,
if $(w,f)$ is a blocking pair under the preference lists of $A$ then $M$ is
not a stable matching in $M_{A}\cap M_{B}$. Otherwise, $(w,f)$ is a blocking
pair for some instance $B_{k}$. We will show that $(w,f)$ must be a blocking
pair for $B$.

Assume that $f$ is not the agent whose preference list is identical in $B$ and
$B_{k}$. Then both $w$ and $f$ have identical preference lists in $A$ and in
$B_{k}$, and so, this is a blocking pair for $A$. Otherwise, it must be the
case that $f$ changed its preference list in $B_{k}$ and has the same changed
list in $B$. Then $(w,f)$ is a blocking pair for $B$ as well, as
$f>_{w}^{B}M(w)$ and $w>_{f}^{B}M(f)$. We conclude that the sets are equal. ∎

###### Proof of Theorem 11.

The proof that $\mathcal{L}^{\prime}$ a sublattice is similar to Proposition
7. The Deferred Acceptance algorithms to find worker and firm optimal
matchings work on the new compound instance $X$, where firm $f$ prefers worker
$w_{i}$ to worker $w_{j}$ if and only if they does so in all the instances.
Birkhoff’s partial order for $\mathcal{L}^{\prime}$ can be found by finding
the edge set representing $\mathcal{M}_{A_{1}}\cap\mathcal{M}_{A_{i}}$ for
each instance $A_{i}$ and the union of these edge sets defines
$\mathcal{L}^{\prime}$. This gives us a way to efficiently enumerate the
matchings. ∎

###### Proof of Theorem 12.

The example in Figure 11 shows that the intersection is not necessarily a
sublattice in $(2,2)$. Instance $B$ differs from $A$ in the preferences of
workers $3$ and $4$ and firms $c$ and $d$. Consider matchings
$M_{1}=\\{1a,2b,3c,4d\\}$ and $M_{2}=\\{1b,2a,3d,4c\\}$ that are stable under
$A$ and $B$. However, $M=M_{1}\vee_{A}M_{2}=\\{1a,2b,3d,4c\\}$ is not stable
under $B$ as $a>_{4}c$ and $4>_{a}1$ so $4a$ is a blocking pair of $M$ under
$B$. And so, if there are at least two agents on each side having different
preferences in $A$ and $B$, $\mathcal{M}_{A}\cap\mathcal{M}_{B}$ is not a
sublattice of $\mathcal{L}_{A}$. ∎

###### Proof of Lemma 6.

Consider instances $A$ and $B$ as given in Figure 12. The set of workers is
$\mathcal{W}=\\{1,2,3,4,5\\}$ and the set of firms is
$\mathcal{F}=\\{a,b,c,d,e\\}$. Instance $B$ is obtained from instance $A$ by
permuting the lists of firm $c$ and worker $3$. Consider matchings
$M_{1}=\\{1b,2c,3a,4d,5e\\}$ and $M_{2}=\\{1a,2b,3c,4e,5d\\}$ that are both
stable with respect to $A$. With respect to instance $B$, $M_{1}$ has blocking
pair $(3,d)$ and $M_{2}$ has blocking pair $(4,c)$. Hence $M_{1}$ and $M_{2}$
are both in $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$. However, the _join_
with respect to $A$ is $M_{1}\vee_{A}M_{2}=\\{1a,2b,3c,4d,5e\\}$ which is
stable with respect to $A$ and $B$.

Similarly, we see that $M_{3}=\\{1c,2a,3b,4d,5e\\}$ and
$M_{4}=\\{1b,2c,3a,4e,5d\\}$ are stable with respect to $A$ but have blocking
pairs $(3,d)$ and $(4,c)$ respectively, under $B$. However, their _meet_ ,
$M_{3}\vee_{A}M_{4}=\\{1c,2a,3b,4e,5d\\}$ is stable with respect to $A$ and
$B$.

Hence $\mathcal{M}_{A}\setminus\mathcal{M}_{B}$ is not a semi-sublattice of
$\mathcal{L}_{A}$. ∎

###### Proof of Theorem 15.

$(\supseteq)$ Let $\mu\notin\mathcal{M}_{A}\cap\mathcal{M}_{B}$. Then $\mu$
has a blocking pair with respect to $A$ or $B$. If it is $A$ then it is
trivially not in
$\mathcal{M}_{A}\cap\mathcal{M}_{B_{\\{w_{1},f_{1}\\}}}\cap\mathcal{M}_{B_{\\{w_{1},f_{2}\\}}}\cap\dots\cap\mathcal{M}_{B_{\\{w_{1},f_{n}\\}}}$.
So suppose it has a blocking pair $(w,f)$ with respect to $B$.

Suppose $w=w_{1}$ and $f\in\\{f_{1},\dots,f_{n}\\}$. So $f>_{w}^{B}\mu(w)$ and
$w>_{f}^{B}\mu(f)$. But these are the preferences of $w$ and $f$ in
$B_{\\{w,f\\}}$, so
$\mu\notin\mathcal{M}_{A}\cap\mathcal{M}_{B_{\\{w_{1},f_{1}\\}}}\cap\mathcal{M}_{B_{\\{w_{1},f_{2}\\}}}\cap\dots\cap\mathcal{M}_{B_{\\{w_{1},f_{n}\\}}}$.

Else $w\neq w_{1}$ and $f\in\\{f_{1},\dots,f_{n}\\}$. Then $w$ has the same
preferences in $A$ and $B$, as well as in every $B_{\\{w_{1},f\\}}$, while $f$
has the same preferences in $B$ and $B_{\\{w_{1},f\\}}$. Hence $(w,f)$ is a
blocking pair for instance $B_{w_{1},f}$.

$(\subseteq)$ Similarly, consider
$\mu\notin\mathcal{M}_{A}\cap\mathcal{M}_{B_{w_{1},f_{1}}}\cap\dots\cap\mathcal{M}_{B_{w_{1},f_{n}}}$.
Then $\mu$ has blocking pair $w,f$ and as in the previous case, assume the
blocking pair is not with respect to $A$. Then it is with respect to some
instance $B_{\\{w_{1},f_{i}\\}}$.

There are three cases:

  1. 1.

$w\neq w_{1}$ and $f=f_{i}$: Then $f_{i}$ has the same list in $B$ and
$B_{w_{i},f_{i}}$, $w$ has the same list in $A$ and $B$ and $B_{w_{i},f_{i}}$,
hence it is a blocking pair with respect to $B$.

  2. 2.

$w=w_{1}$ and $f\neq f_{i}$: Then $w_{i}$ has the same list in $A$ and $B$ and
$B_{\\{w_{i},f_{i}\\}}$, $f$ has the same list in $A$ and $B$ and
$B_{\\{w_{i},f_{i}\\}}$, hence it is a blocking pair with respect to $B$.

  3. 3.

$w=w_{1}$ and $f=f_{i}$: Then $w_{1}$ has the same list in $B$ and
$B_{\\{w_{i},f_{i}}\\}$ only, $f$ has the same list in $B$ and
$B_{\\{w_{i},f_{i}\\}}$, hence it is a blocking pair with respect to $B$.

The other case of $w\neq w_{1}$ and $f\neq f_{1}$ does not arise because then,
$(w,f)$ would be a blocking pair of $A$ which cannot be as
$\mu\in\mathcal{M}_{A}$.

Hence $w,f$ is a blocking pair with respect to $B$ and
$\mu\notin\mathcal{M}_{B}$, hence it is not in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$.

We conclude that the sets are the same. ∎

###### Proof of Lemma 7.

$\mu^{A}_{\theta}$ and $\mu^{A}_{\theta}$ are perfect matchings and we know
that the preferences of $n-1$ workers $w_{1},\dots,w_{n-1}$ are the same in
$A$ and $B$. This means that these $n-1$ workers are paired to $n-1$ distinct
firms in both matchings. Since they are perfect matchings, the $n^{th}$ worker
must be paired with the remaining firm. Hence the matchings are identical. ∎

###### Proof of Theorem 16.

$\mathcal{L}^{\prime}$ is a sublattice of each $\mathcal{L}_{A_{i}}$ as a
corollary of Theorem 13. The LP approach can be used to find stable matchings
in the intersection. The new formulation will have $k$ blocking pair
conditions - one for each instance $A_{i}$ to say that no worker-firm pair
$(w,f)$ is a blocking pair for $x$ under that instance. The Algorithms 5 and 6
can be used to find the worker and firm optimal matchings. Define a room for
each instance and run the Deferred Acceptance algorithm in each room according
to the preferences of the corresponding instance. If the same perfect matching
$M$ is obtained in every room, it is outputted by the algorithm and is stable
with respect to all instances. ∎

##  Appendix D Proofs of Algorithms

We prove Theorem 8 in sections D.1 and D.2. And we prove Theorem 14 in
Sections D.3 and D.4.

###  D.1 Proof of Algorithm 2

We have $A$ and $B$ which are $(0,n)$, meaning workers have complete order
preferences and firms have partial order preferences in $X$. In Algorithm 2,
workers propose, and unlike in Algorithm 7, firms (tentatively) accept only
that worker, that it strictly prefers to every other proposal it has received
- in this round and in all previous rounds.

######  Lemma 11.

If firm $f$ rejects worker $w$ in any round of Algorithm 2, $w$ and $f$ can
never be matched in any matching strongly stable under $X$.

###### Proof.

Assume there is a rejection (otherwise, it is trivial). Let a firm $f$ reject
worker $w$. We will show that any matching $M$ such that $(w,f)\in M$ has a
strong blocking pair. We will induct on the round number when the rejection
happens.

Assume the rejection happens in the first round. $f$ only rejects $w$ in the
first round if it received a proposal from another worker $w^{\prime}$ that it
prefers or is indifferent to. And since $w^{\prime}$ proposed to $f$ on the
first round, it must prefer $f$ to $M(w^{\prime})$. Hence, $(w^{\prime},f)$ is
a strong blocking pair to $M$.

Let the rejection happen in some round $k(>1)$. Now, if $f$ rejects $w$, then
there is some worker $w^{\prime}$ that is proposed to $f$ in this or previous
rounds and $w^{\prime}>^{X}_{f}w$ or $w^{\prime}\sim^{X}_{f}w$. If
$w^{\prime}$ got rejected by $f$ in an earlier round, then, by the induction
hypothesis, $w^{\prime}$ cannot be matched to any firm it proposed to before
$f$ and $f$ in any stable matching. And so, $f>_{w}^{\prime}M(w^{\prime})$.
And so, $(w^{\prime},f)$ is a strong blocking pair. ∎

######  Lemma 12.

If $X$ admits a strongly stable matching, then algorithm 2 finds one.

###### Proof.

Suppose there exists a strongly stable matching but the algorithm terminated
outputting $\boxtimes$. This only happens when a worker gets rejected by all
the firms. But, by lemma 11, this means that this worker has no feasible
partner in any of the strongly stable matchings, which is a contradiction. ∎

######  Lemma 13.

If algorithm 2 returns a matching, it must be strongly stable under $X$.

###### Proof.

Assume not. Let $(w,f)$ be a blocking pair to the matching given by the
algorithm. But then, $w$ should have proposed to $f$ in the run of the
algorithm and got rejected. And so, $f$ should get matched to something better
at the end of the algorithm, implying $(w,f)$ is not a strong blocking pair, a
contradiction. ∎

######  Lemma 14.

If algorithm 2 returns a matching, it must be worker-optimal strongly stable
matching.

###### Proof.

If not, some worker $w$ has a better partner in the worker optimal matching.
But then, that worker would have proposed to that partner and got rejected in
the algorithm, giving rise to a contradiction. ∎

###  D.2 Proof of Algorithm 3

We have $A$ and $B$ which are $(0,n)$, meaning workers have complete order
preferences and firms have partial order preferences in $X$. In algorithm 3,
firms propose, and unlike in algorithm 7, they can propose to multiple workers
in the same iteration.

######  Lemma 15.

If worker $w$ rejects firm $f$ in any round of algorithm 3, $w$ and $f$ can
never be matched in any matching stable under both instances $A$ and $B$.

###### Proof.

Suppose for contradiction that $w$ is a worker that rejected firm $f$ in some
round but they are matched in stable matching $\mu$.

We proceed by induction on the number of rounds. Suppose $w$ rejects $f$ in
the first round. Then there is another firm $f_{1}$ that $w$ strictly prefers
to $f$. Since the firms propose to “best”-uncrossed workers and it is the
first round, there is no worker $w^{\prime}$ such that $f$ prefers
$w^{\prime}$ to $w$, that is $w>_{f_{1}}w^{\prime}$ or
$w\sim_{f_{1}}w^{\prime}$. Consider stable matching $\mu$ where $w$ is matched
to $f$. Then as ${f_{1}}>_{w}f$ and $w>_{f_{1}}w^{\prime}$ or
$w\sim_{f_{1}}w^{\prime}$, $(w,f_{1})$ is a strong blocking pair for $\mu$.

Suppose $w$ rejects $f$ in the $k$th round. Then there is a firm $f_{k}$ who
$w$ strictly prefers to $f$. One of the following cases must hold:

  1. 1.

$w>_{f_{k}}\mu(f_{k})$ or $w\sim_{f_{k}}\mu(f_{k})$. In this case, $(w,f_{k})$
is a strong blocking pair for $\mu$.

  2. 2.

$\mu(f_{k})>_{f_{k}}w$. Then $f_{k}$ must have proposed to $\mu(f_{k})$ in a
previous round and been rejected by $\mu(f_{k})$. Applying the inductive
hypothesis, there exists a different strong blocking pair
$(w^{\prime},f^{\prime})$ for $\mu$ as $f_{k}$ and $\mu(f_{k})$ are matched,
hence $\mu$ is not stable.

∎

######  Lemma 16.

Algorithm 3 terminates.

###### Proof.

For any given round in the execution of the algorithm, one of the following
cases must hold:

  1. 1.

There are less than $n$ proposals to make in round $k$. Then there is a firm
$f$ that has no uncrossed worker to propose in its list(DAG). Then the
algorithm will terminate before this round and output $\boxtimes$.

  2. 2.

There are exactly $n$ proposals are given to $n$ distinct workers. All workers
get only a single proposal, so there is either a rejection or the algorithm
terminates at the end of the round and outputs a perfect matching.

  3. 3.

There are more than $n$ proposals. Then there is at least one worker $w$ that
receives multiple proposals. $w$ rejects at least one of these proposals and
at least one firm crosses $w$ off its list.

This shows that at the end of every round, there is either a rejection or the
algorithm terminates. Since there are only $O(n^{2})$ rejections possible, the
algorithm terminates in $\operatorname{poly}(n)$ rounds. ∎

######  Lemma 17.

If $X$ admits a strongly stable matching, then algorithm 3 finds one.

###### Proof.

Suppose there exists a strongly stable matching but the algorithm terminated
outputting $\boxtimes$. This only happens when a firm gets rejected by all the
workers. But, by lemma 15, this means that this firm has no feasible partner
in any of the strongly stable matchings, which is a contradiction. ∎

######  Lemma 18.

If algorithm 3 returns a matching, it must be strongly stable under $X$.

###### Proof.

Assume not. Let $(w,f)$ be a blocking pair to the matching given by the
algorithm. But then, $f$ should have proposed to $w$ in the run of the
algorithm and got rejected. And so, $w$ should get matched to something better
at the end of the algorithm, implying $(w,f)$ is not a strong blocking pair, a
contradiction. ∎

######  Lemma 19.

If algorithm 3 returns a matching, it must be firm-optimal strongly stable
matching.

###### Proof.

If not, some firm $f$ has a better partner in the firm optimal matching. But
then, that firm would have proposed to that partner and got rejected in the
algorithm, leading to a contradiction. ∎

Note that both the above proofs work for any compound instance $X$ which has
partial order preferences on one side and complete order on the other side.
So, instead of just two instances, we can have many more as explained in
section 3.3. Also note that both the algorithms work exactly like the original
Deferred acceptance algorithm if $X$ has complete order preferences on both
sides, i.e., instances $A$ and $B$ are the same.

###  D.3 Proof of Algorithm 5

The algorithm involves running the Deferred Acceptance algorithm in different
rooms with workers proposing and returning the worker optimal matching in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$, given $A$ and $B$ are $(1,n)$. Let
$w_{1}$ be the worker with different preferences in $A$ and $B$.

######  Lemma 20.

The algorithm terminates and always returns a perfect matching or $\boxtimes$

###### Proof.

The algorithm always terminates since there is at least one rejection per
iteration before the final iteration.

Suppose the algorithm terminates with two distinct perfect matchings,
$\mu_{A}$ in room $A$ and $\mu_{B}$ in room $B$. So, there must exists a
worker $w\neq w_{1}$ with the same preferences in $A$ and $B$ but different
matches in $\mu_{A}$ and $\mu_{B}$. Such a worker must exist since only
$w_{1}$ changed their preferences, and the matchings are perfect. Suppose
without loss of generality that $\mu_{A}(w)>_{w}^{A,B}\mu_{B}(w)$. As $w$ has
the same lists in $A$ and $B$, $w$ must have proposed to $\mu_{A}(w)$ in room
$B$, been rejected and crossed them off their list. However, per the
algorithm, $w$ should have also crossed off $\mu_{A}(w)$ their list in room
$A$, hence $\mu_{A}$ cannot be a perfect matching achieved in room $A$. ∎

######  Lemma 21.

If firm $f$ rejects $w$ in either room, $w$ and $f$ cannot be matched in any
matching in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$.

###### Proof.

We use the property of the DA algorithm for single instance $A$ that says that
if a firm $f$ rejects worker $w$, then $(w,f)$ are not matched in any stable
matching with respect to $A$([GS62]).

Suppose, without loss of generality, let $f$ reject $w$ in room $A$. Then
$(w,f)$ are not matched in any stable matching in $\mathcal{M}_{A}$. Hence
they cannot be matched in any stable matching in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$. ∎

######  Lemma 22.

If $A$ and $B$ admit a stable matching under both, then algorithm 5 finds one.

###### Proof.

Suppose there exists such a stable matching but the algorithm terminated
outputting $\boxtimes$. This only happens when a worker gets rejected by all
the firms. But, by lemma 21, this means that this worker has no feasible
partner in any of the stable matchings, which is a contradiction. ∎

######  Lemma 23.

If algorithm 5 returns a matching, it must be stable under both $A$ and $B$.

###### Proof.

Suppose $\mu$ is the perfect matching returned and without loss of generality
suppose it has blocking pair $(w,f)$ with respect to $A$. That is,
$f>_{w}^{A}\mu(w)$ and $w>_{f}^{A}\mu(f)$. Then $w$ must have proposed to $f$
during some iteration of the algorithm and been rejected in room $A$ for some
worker $w^{\prime}$ that $f$ preferred to $w$, eventually ending up with
$\mu(f)$. As firms always get better matches as the algorithm progresses, it
must be the case that $\mu(f)>_{f}w$ and $(w,f)$ is not a blocking pair. ∎

######  Lemma 24.

If algorithm 5 returns a matching, it must be worker-optimal matching.

###### Proof.

If not, some worker $w\neq w_{1}$ has a better partner in the worker optimal
matching. But then, that worker would have proposed to that partner every room
and got rejected in one of them, giving rise to a contradiction. ∎

###  D.4 Proof of Algorithm 6

The algorithm involves running the Deferred Acceptance algorithm in different
rooms with firms proposing and returning the firm optimal matching in
$\mathcal{M}_{A}\cap\mathcal{M}_{B}$, given $A$ and $B$ are $(1,n)$. Let
$w_{1}$ be the worker with different preferences in $A$ and $B$.

######  Lemma 25.

The algorithm terminates and always returns a perfect matching or $\boxtimes$.

###### Proof.

The algorithm terminates since there is at least one rejection per iteration.

Suppose the algorithm terminates with distinct perfect matchings $\mu_{A}$ in
room $A$ and $\mu_{B}$ in room $B$. Then there is some worker $w\neq w_{1}$
who has the same lists in $A$ and $B$ who has distinct matches $\mu_{A}(w)$
and $\mu_{B}(w)$. Suppose without loss of generality that
$\mu_{A}(w)>_{w}^{A,B}\mu_{B}(w)$. So $w$ must have received a proposal from
$\mu_{A}(w)$ in some iteration since to be tentatively matched a worker must
have received a proposal from that firm. Workers reject all firms that are
less preferred in all the rooms, so $w$ must have rejected $\mu_{B}(w)$ in
room $R_{A}$ as well in room $R_{B}$, so $\mu_{B}$ cannot be the final perfect
matching in room $R_{B}$, a contradiction. ∎

######  Lemma 26.

If firm $f$ rejects $w$ in either room, $w$ and $f$ cannot be matched in any
strongly stable matching in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$.

###### Proof.

We use the property of the DA algorithm for single instance $A$ that says that
if a firm $f$ is rejected by worker $w$, then $(w,f)$ are not matched in any
stable matching with respect to $A$([GS62]). But we note the additional fact
that workers should only get matched to something better than $f$ from then
on. It is the same as preemptively rejecting all firms down the list than $f$,
the idea that we carry over to this algorithm. Suppose that, without loss of
generality, let $w$ reject $f$ in room $A$. Then $(w,f)$ are not matched in
any stable matching in $\mathcal{M}_{A}$. Hence they cannot be matched in any
stable matching in $\mathcal{M}_{A}\cap\mathcal{M}_{B}$. ∎

######  Lemma 27.

If $A$ and $B$ admit a stable matching under both, then algorithm 6 finds one.

###### Proof.

Suppose there exists such a stable matching but the algorithm terminated
outputting $\boxtimes$. This only happens when a firm gets rejected by all the
workers. But, by lemma 26, this means that this firm has no feasible partner
in any of the stable matchings, which is a contradiction. ∎

######  Lemma 28.

If Algorithm 6 returns a matching, it must be stable under both $A$ and $B$.

###### Proof.

Suppose the algorithm returns perfect matching $\mu$ and assume, without loss
of generality, it has blocking pair $(w,f)$ with respect to $A$. That is
$w>_{f}^{A}\mu(f)$ and $f>_{w}^{A}\mu(w)$. Then $f$ must have proposed to $w$
during some iteration of the algorithm in room $R_{A}$ and been rejected for
some firm $f^{\prime}$ that $w$ preferred(under $A$), and $w$ eventually ends
up with $\mu(w)$ which it prefers the most. Hence $\mu(w)>_{w}^{A}f$ which
contradicts our assumption that $(w,f)$ is a blocking pair. ∎

######  Lemma 29.

If Algorithm 6 returns a matching, it must be firm-optimal matching.

###### Proof.

If not, some firm $f$ has a better partner in the firm optimal matching. But
then, that firm would have proposed to that partner in all the rooms and got
rejected in a room, leading to a contradiction. ∎