# Characterisation of Super-stable Matchings

Changyong Hu Department of Electrical and Computer Engineering, University of
Texas at Austin, Austin, Texas 78705, USA. E-mail<EMAIL_ADDRESS>Vijay
K. Garg Department of Electrical and Computer Engineering, University of Texas
at Austin, Austin, Texas 78705, USA. E-mail<EMAIL_ADDRESS>
###### Abstract

An instance of the super-stable matching problem with incomplete lists and
ties is an undirected bipartite graph $G=(A\cup B,E)$, with an adjacency list
being a linearly ordered list of ties. Ties are subsets of vertices equally
good for a given vertex. An edge $(x,y)\in E\backslash M$ is a blocking edge
for a matching $M$ if by getting matched to each other neither of the vertices
$x$ and $y$ would become worse off. Thus, there is no disadvantage if the two
vertices would like to match up. A matching $M$ is super-stable if there is no
blocking edge with respect to $M$. It has previously been shown that super-
stable matchings form a distributive lattice [1, 2] and the number of super-
stable matchings can be exponential in the number of vertices. We give two
compact representations of size $O(m)$ that can be used to construct all
super-stable matchings, where $m$ denotes the number of edges in the graph.
The construction of the second representation takes $O(mn)$ time, where $n$
denotes the number of vertices in the graph, and gives an explicit rotation
poset similar to the rotation poset in the classical stable marriage problem.
We also give a polyhedral characterisation of the set of all super-stable
matchings and prove that the super-stable matching polytope is integral, thus
solving an open problem stated in the book by Gusfield and Irving [3].

##  1 Introduction

An instance of the super-stable matching problem with incomplete lists and
ties is an undirected bipartite graph $G=(A\cup B,E)$, with an adjacency list
being a linearly ordered list of ties. Ties are disjoint and may contain just
one vertex. If vertices $b_{1}$ and $b_{2}$ are neighbors of vertex $a$ in the
graph $G$, then either $(1)$ $a$ strictly prefers $b_{1}$ to $b_{2}$, which we
denote as $b_{1}\succ_{a}b_{2}$; or $(2)$ $a$ is indifferent between $b_{1}$
and $b_{2}$, which means $b_{1}$ and $b_{2}$ are in a tie in $a$’s adjacency
list, and denote as $b_{1}=_{a}b_{2}$; or $(3)$ $a$ strictly prefers $b_{2}$
to $b_{1}$. We say $a$ weakly prefers $b_{1}$ to $b_{2}$ if either $a$
strictly prefers $b_{1}$ to $b_{2}$ or $a$ is indifferent between $b_{1}$ and
$b_{2}$, which we denote as $b_{1}\succeq_{a}b_{2}$. A matching $M$ is a set
of disjoint edges in the graph $G$. Let $e=(u,v)$ be an edge contained in the
matching $M$. Then, we say that vertices $u$ and $v$ are matched in $M$ and
write $u=M(v)$ to denote that $u$ is matched to $v$ in $M$. An edge $(x,y)\in
E\backslash M$ is a blocking edge for a matching $M$ if by getting matched to
each other neither of the vertices $x$ and $y$ would become worse off, i.e.
$x$ is either unmatched or $x$ weakly prefers $y$ to $M(x)$, and $y$ is either
unmatched or $y$ weakly prefers $x$ to $M(y)$. We abuse the notation
$y\succeq_{x}M(x)$ for the case that $x$ is unmatched in $M$. A matching is
super-stable if there is no blocking edge with respect to it.

Super-stable matchings were first investigated by Irving [4], who gave three
classes of stable matchings in the case of preference lists with ties,
depending on the way of defining a blocking edge for a matching $M$. In the
weakly stable matching problem an edge $e=(x,y)$ is blocking if by getting
matched to each other, both $x$ and $y$ would become better off. In the
strongly stable matching problem, an edge $e=(x,y)$ is blocking if one of $x$
and $y$ becomes better off and the other would not be worse off.

In this paper we study the problem of characterising the set of all super-
stable matchings. The problem was stated in the book by Gusfield and Irving
[3] as one of the 12 open problems. The structure of the set of all stable
matchings in the stable marriage problem without ties is well understood in
Gusfield and Irving’s book [3]. Recently, Kunysz et al. [5] gave compact
representations for the set of all strongly stable matchings and showed that
the construction can be done in $O(mn)$ time, where $n$ and $m$ denote the
number of vertices and edges in the graph. Scott [6] investigated the
structure of all super-stable matchings by defining an object that he called
meta-rotation, which corresponds to one collection of rotations in some
arbitrary tie-breaking instance of the original instance and the time
complexity of the construction is $O(m^{2})$.

We give two compact representations of the set of all super-stable matchings
that can be constructed in, respectively, $O(nm^{2})$ and $O(mn)$ time.

The first representation of the set of all super-stable matchings consists of
$O(m)$ matchings, each of which is a man-optimal stable matching among all
super-stable matchings that contains a given edge. We show that computing such
matching for each edge can be reduced to computing a man-optimal super-stable
matching in a reduced graph by deleting an appropriate subset of edges in
graph $G$. The algorithm is described in Section 3.

Our second representation explicitly constructs rotations, which are
differences between consecutive super-stable matchings in a maximal sequence
of super-stable matchings starting with a man-optimal super-stable matching
and ending with a woman-optimal super-stable matching. Unlike Scott’s [6]
meta-rotation, our rotation is the symmetric difference of two super-stable
matchings, which could be a cycle or multiple cycles.

Our construction takes $O(mn)$ time, while Scott’s [6] algorithm takes
$O(m^{2})$ time. We also show how to efficiently construct a partial order
among rotations. This poset can be used to solve other problems connected to
super-stable matchings such as the enumeration of all super-stable matchings
and the maximum weight super-stable matching problem. Fleiner et al. [7] solve
the weight super-stable matching by reducing it to the 2-SAT problem and the
time complexity is $O(mn\log(W))$, where $W$ is the maximum weight among all
edges in $G$. By using the rotation poset constructed in this paper, the
weighted problem can also be solved in $O(mn\log(W))$ time.

In this paper we also give a polyhedral characterisation for the set of all
super-stable matchings and prove that the super-stable matching polytope is
integral. This result implies that the maximum weight super-stable matching
problem can be solved in polynomial time. Though the complexity of solving LP
is usually higher than combinatorial methods, like in [7], this gives an
alternative direction to solve the weighted super-stable matching problem.
Previously, it has been shown that the stable matching polytope and the
strongly stable matching polytope are integral [8, 9, 5], we complete all
three cases by proving that the super-stable matching polytope is integral as
well.

We also proved a property called self-duality for the super-stable matching
polytope, which also holds for the classical stable matching polytope [10] and
the strongly stable matching polytope [5].

###  1.1 Related Works

Irving [4] gave an $O(m)$ algorithm to find a super-stable matching if it
exists. Spieker [1] showed that super-stable matchings form a distributive
lattice. Further properties of super-stable matchings were proved by Manlove
in [2]. Scott [6] introduced the concept called meta-rotation poset for super-
stable matchings and showed the one-to-one correspondence between super-stable
matchings and closed subsets of the poset.

Irving [4] and Manlove [2] gave an $O(m^{2})$ algorithm to find a strongly
stable matching if it exists. Kavitha et al. [11] gave an $O(nm)$ algorithm
for the strongly stable matching problem. Manlove [2] showed that strongly
stable matchings form a distributive lattice. Kunysz et al. [12] gave a
characterisation of all strongly stable matchings and later Kunysz [5] gave a
polyhedral description for the set of all strongly stable matchings and proved
that the strongly stable matching polytope is integral.

For weakly stable matchings, it is not true that all weakly stable matchings
of a given instance always have the same size. Weakly stable matching can be
easily found by running the deferred-acceptance algorithm while breaking ties
in an arbitrary manner. The problem of computing a maximum-size weakly stable
matching is NP-hard, which has been proved by Iwama et al. [13]. Thus finding
good approximations of the problem becomes very interesting. For the version
when ties are allowed on both sides, the currently best approximation factor
is $3/2$ [14, 15, 16]. For the case when ties only occur on one side, there
are a sequence of works pushing the approximation factor lower. Iwama et al.
[17] gave an $25/17$ approximation algorithm. Huang and Kavitha [18] improved
it to $22/15$. Later Radnai [19] improved the approximation factor to $41/28$,
then Dean et al. [20] pushed the approximation factor to $19/13$. Most recent
result by Lam and Plaxton [21] gave the currently best approximation factor of
$1+1/e$.

##  2 Preliminaries

In this section we give some definitions and theorems that are useful in the
following sections.

######  Theorem 1.

[4, 2] There is an $O(m)$ algorithm to determine a man-optimal super-stable
matching of the given instance or report that no such matching exists.

######  Theorem 2.

[2] In a given instance of the super-stable matching problem, the same set of
vertices are matched in all super-stable matchings.

######  Lemma 3.

[2] Let $M,N$ be two super-stable matchings in a given super-stable matching
instance. Suppose that, for any agent $p$, $(p,q)\in M$ and $(p,q^{\prime})\in
N$, where $p$ is indifferent between $q$ and $q^{\prime}$, then
$q=q^{\prime}$.

We recall some standard notations and definitions from the theory of matchings
under preferences. For a given edge $(m,w)$, any matching containing $(m,w)$
is called an $(m,w)$-matching. Let us denote the set of all super-stable
matchings of $G$ by $\mathcal{M}_{G}$. Let $\mathcal{M}_{G}(m,w)$ be the set
of all super-stable $(m,w)$-matchings in $G$.

For two super-stable matchings $M$ and $N$, we say that $M$ dominates $N$ and
write $M\succeq N$ if each man $m$ weakly prefers $M(m)$ to $N(m)$. If $M$
dominates $N$ and there exists a man $m$ who prefers $M(m)$ to $N(m)$, then we
say $M$ strictly dominates $N$, write $M\succ N$ and we call $N$ a successor
of $M$. Note that by Lemma 3, $M\succeq N$ implies $M\succ N$, assuming $M$ is
not equal to $N$.

##  3 Irreducible Super-stable Matchings

In this section, we give our first representation via irreducible matchings.
Birkhoff’s representation theorem [22] for distributive lattices states that
the elements of any finite distributive lattice can be represented as finite
sets in such a way that the lattice operations correspond to unions and
intersections of sets. The theorem gives a one-to-one correspondence between
distributive lattices and partial orders. Our goal is to find the partial
order that represents the set of all super-stable matchings.

Distributive lattice is closely related to rings of sets, which is a family of
sets that is closed under set unions and set intersections. If the sets in a
ring of sets are ordered by set inclusion, they form a distributive lattice.
Theory regarding rings of sets and its application to representations of the
set of stable matchings in the classical stable marriage problem is well
studied by Irving and Gusfield [3]. Below we give a brief summary of this
theory that serves as a preliminary for our algorithm.

Given a finite set $B$, the base set, a family
$\mathcal{F}=\\{F_{0},F_{1},\cdots,F_{k}\\}$ of subsets of $B$ is called a
ring of sets over $B$ if $\mathcal{F}$ is closed under set union and
intersection. A ring of sets contains a unique minimal element and a unique
maximal element.

For any element $a\in B$, we denote $\mathcal{F}(a)$ the set of all elements
of $\mathcal{F}$ that contains $a$. It is obvious that $\mathcal{F}(a)$ is
also a ring of sets over $B$. We define $F(a)$ to be the unique minimal
element of $\mathcal{F}(a)$. An element $F\in\mathcal{F}$ that is $F(a)$ for
some $a\in B$ is called irreducible. We denote $I(\mathcal{F})$ the set of all
irreducible elements of $\mathcal{F}$. We view $(I(\mathcal{F}),\leq)$ as a
partial order under the relation $\leq$ of set containment. We give the
Birkhoff’s representation theorem in the language of rings of sets below.

######  Theorem 4.

[3] i) There is a one-to-one correspondence between the closed subsets of
$I(\mathcal{F})$ and the elements of $\mathcal{F}$.
ii) If $S$ and $S^{\prime}$ are closed subsets of $I(\mathcal{F})$ that
generate $F=\bigcup S$ and $F^{\prime}=\bigcup S^{\prime}$ respectively, then
$F\subseteq F^{\prime}$ if and only if $S\subseteq S^{\prime}$.

In the context of super-stable matchings, the base set $B$ corresponds to the
set of all acceptable pairs $(m,w)\in E$. We define the $P$-set of a super-
stable matching $M$ to be the set of all pairs $(m,w)$, where $w$ is either
$M(m)$ or a woman whom $m$ weakly prefers to $M(m)$, which corresponds to an
element in $\mathcal{F}$. It is obvious that the unique minimal (man-optimal)
super-stable matching in $\mathcal{M}_{G}(m,w)$, if nonempty, is irreducible.

We describe an $O(|E|)$ algorithm for computing a man-optimal super-stable
$(m,w)$-matching in $G$. Algorithm 1 essentially constructs a reduced graph
$G^{\prime}\subseteq G$ by removing some edges from $G$ (line 1 to line 1 in
Algorithm 1). After that, the algorithm computes a man-optimal super-stable
matching $M^{\prime}$ in the reduced graph $G^{\prime}$. By adding back the
edge $(m,w)$, the new matching $M\cup(m,w)$ is super-stable in $G$.

1Input: the graph $G=(A\cup B,E)$ and preference lists of $G$ and an edge
$(m,w)\in E$.

2 Output: man-optimal super-stable $(m,w)$-matching or deciding that no such
matching exists.

3 $G^{\prime}\leftarrow G\backslash\\{m,w\\}$ $//$ remove $m$ and $w$ and all
edges that are incident to them

4 for $m^{\prime}$ s.t. $(m^{\prime},w)\in E$ and $m\preceq_{w}m^{\prime}$ do

5 for $w^{\prime}$ s.t. $(m^{\prime},w^{\prime})\in E$ and
$w\succeq_{m^{\prime}}w^{\prime}$ do

6 $G^{\prime}\leftarrow G^{\prime}\backslash(m^{\prime},w^{\prime})$

7 end for

8 end for

9 for $w^{\prime}$ s.t. $(m,w^{\prime})\in E$ and $w\preceq_{m}w^{\prime}$ do

10 for $m^{\prime}$ s.t. $(m^{\prime},w^{\prime})\in E$ and
$m\succeq_{w^{\prime}}m^{\prime}$ do

11 $G^{\prime}\leftarrow G^{\prime}\backslash(m^{\prime},w^{\prime})$

12 end for

13 end for

14 compute man-optimal super-stable matching in $G^{\prime}$.

15 if exists man-optimal super-stable matching $M$ in $G^{\prime}$ and
$M\cup(m,w)$ is super-stable in $G$

16 return $M\cup(m,w)$

17 else

18 return no super-stable $(m,w)$-matching exists.

end if

Algorithm 1 Computing man-optimal super-stable $(m,w)$-matching

######  Lemma 5.

Let $M$ be a super-stable $(m,w)$-matching. Then
$M^{\prime}=M\backslash\\{(m,w)\\}$ is a super-stable matching in the reduced
graph $G^{\prime}$.

###### Proof.

We need to prove $M^{\prime}\subseteq G^{\prime}$ or equivalently none of
edges removed from $G$ is matched in $M^{\prime}$. Suppose not, an edge
$(m^{\prime},w^{\prime})$ was removed from $G$ and is matched in $M^{\prime}$.
Note that $m^{\prime}\neq m$ and $w^{\prime}\neq w$. Hence, it follows that
there is an edge $(m,w^{\prime})$ or $(m^{\prime},w)$ which caused the removal
of $(m^{\prime},w^{\prime})$. W.l.o.g, let’s assume it is $(m,w^{\prime})$
which caused the removal of $(m^{\prime},w^{\prime})$. Then we have
$w\preceq_{m}w^{\prime}$ and $m\succeq_{w^{\prime}}m^{\prime}$. Obviously,
$(m,w^{\prime})$ is a blocking pair, which leads to a contradiction of $M$
being super-stable.

To prove super-stability of $M^{\prime}$ is easy. If there were an edge $e$
blocking $M^{\prime}$, it would also block $M$. ∎

######  Lemma 6.

Let $M^{\prime}$ be some super-stable matching in the reduced graph
$G^{\prime}$ if exists. If $M^{\prime}\cup(m,w)$ is a super-stable matching in
$G$, then for each super-stable matching $N^{\prime}$ in $G^{\prime}$,
$N^{\prime}\cup(m,w)$ is a super-stable matching in $G$. If $G^{\prime}$ does
not have any super-stable matching, then there is no super-stable
$(m,w)$-matching.

###### Proof.

Let $M=M^{\prime}\cup(m,w)$. Since $M^{\prime}$ is super-stable in
$G^{\prime}$. It follows that only the removed edges in $E\backslash
E^{\prime}$ can potentially block $M$. We have two cases.
Case 1. Any edge that is incident to $m$ or $w$ cannot block $M$. W.l.o.g,
Suppose that for some $w^{\prime}$ that is incident to $m$, and
$(m,w^{\prime})$ blocks $M$. Then we have $w^{\prime}\succeq_{m}w$. By the
construction of $G^{\prime}$, any edge $(m^{\prime},w^{\prime})$ such that
$m\succeq_{w^{\prime}}m^{\prime}$ was removed. Hence $w^{\prime}$ must be
unmatched in $M$. From Theorem 2, $w^{\prime}$ is unmatched in any super-
stable matching of $G$. Let us assume there exists some super-stable
$(m,w)$-matching $N$. Then $N^{\prime}=N\backslash(m,w)$ is super-stable in
$G^{\prime}$. Since $w^{\prime}$ is unmatched in $N$, $(m,w^{\prime})$ blocks
$N$, contradiction.
Case 2. Any edge $(m^{\prime},w^{\prime})$ such that $m^{\prime}\neq m$ and
$w^{\prime}\neq w$ cannot block $M$. By the construction of the reduced graph
$G^{\prime}$, the removal of $(m^{\prime},w^{\prime})$ was caused by some edge
$(m,w^{\prime})$ or $(m^{\prime},w)$. W.l.o.g, some edge $(m,w^{\prime})$
caused the removal of $(m^{\prime},w^{\prime})$. Hence, if $w^{\prime}$ is
matched in $M$, then $M(w^{\prime})\succeq_{w^{\prime}}m^{\prime}$.
$(m^{\prime},w^{\prime})$ does not block $M$. In the case that $w^{\prime}$ is
unmatched in $M$, $w^{\prime}$ is unmatched in any super-stable matching in
$G$. Similar to Case 1, if there exists some super-stable $(m,w)$-matching
$N$, then $(m,w^{\prime})$ blocks N, contradiction. By the same argument, if
$M$ is super-stable in $G$, for any other super-stable matching $N^{\prime}$
in $G^{\prime}$, $M^{\prime}$ and $N^{\prime}$ match the same set of vertices.
No edges in $E\backslash E^{\prime}$ can block $N^{\prime}\cup(m,w)$. ∎

######  Theorem 7.

Let $(m,w)$ be an edge in $G$. There is an $O(m)$ algorithm for computing a
man-optimal super-stable $(m,w)$-matching or deciding that no super-stable
$(m,w)$-matching exists.

###### Proof.

Lemma 6 makes sure if Algorithm 1 outputs a matching $M$, then $M$ is super-
stable in $G$. Lemma 5 guarantees that if there exists any super-stable
matching in $G$, then Algorithm 1 would never miss it. ∎

######  Theorem 8.

$(I(\mathcal{M}_{G}),\leq)$ can be constructed in $O(nm^{2})$ time.

###### Proof.

$I(\mathcal{M}_{G})$ can be computed in $O(m^{2})$ time by running Algorithm 1
for each edge $(m,w)\in E$. The set $I(\mathcal{M}_{G})$ has at most $m$
elements. By checking each pair of $I(\mathcal{M}_{G})$, we can construct the
partial order. Each check takes $O(n)$ time. Thus, the total time is
$O(nm^{2})$. ∎

##  4 A Maximal Sequence of Super-stable Matchings

Representation via irreducible matchings is intuitive, but the time complexity
is high. In this section, we give another representation via rotation poset
and the time complexity to construct this rotation poset is only $O(mn)$.

Rotation poset derives from the concept of minimal differences of a ring of
sets. A chain $C=\\{C_{1},\cdots,C_{q}\\}$ in $\mathcal{F}$ is an ordered set
of elements of $\mathcal{F}$ such that $C_{i}$ is an immediate predecessor of
$C_{i+1}$ for each $i\in[q]$. The maximal chain is a chain that begins at the
minimal element of $\mathcal{F}$, $F_{0}$ and ends at the maximal element of
$\mathcal{F}$, $F_{z}$. Let $F_{i}$ and $F_{i+1}$ be two elements of
$\mathcal{F}$ such that $F_{i}$ is an immediate predecessor of $F_{i+1}$. The
difference $D=F_{i+1}\backslash F_{i}$ is called a minimal difference of
$\mathcal{F}$. Note that for each two consecutive elements of a chain $C$,
there is a minimal difference $D$, we say that $C$ contains $D$. The following
two theorems give another version of Birkhoff’s representation theorem in the
language of minimal differences. The reader can find more details in Irving
and Gusfield’s book [3].

######  Theorem 9.

[3] If $F$ and $F^{\prime}$ are two elements in $\mathcal{F}$ such that
$F\subset F^{\prime}$, then every chain from $F$ to $F^{\prime}$ in
$\mathcal{F}$ contains exactly the same set of minimal differences (in a
different order).

######  Theorem 10.

[3] Let $D(\mathcal{F})$ denote the set of all minimal differences in
$\mathcal{F}$. For two minimal differences $D$ and $D^{\prime}$, $D\prec
D^{\prime}$ if and only if $D$ appears before $D^{\prime}$ on every maximal
chain in $\mathcal{F}$. There is a one-to-one correspondence between the
elements of $\mathcal{F}$ and the closed subsets of $D(\mathcal{F})$.

In the context of super-stable matchings, we want to compute a maximal
sequence of super-stable matchings in $\mathcal{M}(G)$, i.e. a sequence
$M_{0}\succ M_{1}\succ\cdots\succ M_{z}$ where $M_{0}$ is the man-optimal
super-stable matching and $M_{z}$ is the woman-optimal super-stable matching
and for each $1\leq i\leq z$, there is no super-stable matching $M^{\prime}$
such that $M_{i-1}\succ M^{\prime}\succ M_{i}$. We call a matching
$M^{\prime}$ a strict successor of a matching $M$ if $M^{\prime}$ is a
successor of $M$, i.e. $M\succ M^{\prime}$ and there exists no super-stable
matching $M^{\prime\prime}$ such that $M\succ M^{\prime\prime}\succ
M^{\prime}$. We can solve this problem by computing a strict successor of any
super-stable matching $M$.

Let $M$ be a super-stable matching in $G$ and $m$ a vertex in $A$. Suppose
that there exists a super-stable matching $M^{\prime}$ such that $m$ gets a
worse partner in $M^{\prime}$ than in $M$, i.e. $M(m)\succ_{m}M^{\prime}(m)$.
Let $w=M^{\prime}(m)$, by Lemma 3, $w$ must be matched in $M$ and
$m\succ_{w}M(w)$. Hence we are essentially searching for some vertex $w$ such
that $M(m)\succ_{m}w$ and $m\succ_{w}M(w)$. In Algorithm 2, the set $E_{c}$
contains for each man $m$ highest ranked edges incident to him that satisfies
the condition above. For each man $m$, the candidate edge $(m,w)$ is not
unique, there might be other edge $(m,w^{\prime})$ that forms a tie with
$(m,w)$. While in the case of strict preference list, the candidate edge is
unique.

A strongly connected component $S$ of a directed graph $G$ is a subgraph $S$
that is strongly connected, i.e. there is a path in $S$ in each direction
between each pair of vertices of $S$, and is maximal with this property: no
additional edges or vertices from $G$ can be included in the subgraph without
breaking its property of being strongly connected. We say that $e=(m,w)$ is an
outgoing edge of $S$ if $m\in S$ and $w\notin S$.

In Algorithm 2 given below we maintain a directed graph $G_{d}=(V,E_{d})$,
whose every edge $(m,w)\in E_{d}\cap M$ is directed from $w$ to $m$ and every
other edge $(m,w)$ is directed from $m$ to $w$. $G_{d}$ is a subgraph of $G$
that contains the edges the algorithm traverses so far. The basic idea of this
algorithm is that for each man $m$ such that $M(m)\neq M_{z}(m)$, we traverse
the preference list of $m$ until we find some candidate edges defined above.
We add the edges traversed into $G_{d}$ and the candidate edges into $G_{c}$.
For each strongly connected component $S$ of $G_{d}$ without outgoing edges,
we try to find a perfect matching on $S$ in $G_{c}=(V,E_{c})$. If we are
successful, we find a strict successor of $M$. Otherwise, we modify $G_{c}$
and $G_{d}$ by allowing edges of lower ranks.

1 let $M_{0}$ be the (unique) man-optimal super-stable matching of $G$.

2 let $M_{z}$ be the (unique) woman-optimal super-stable matching of $G$.

3 $M\leftarrow M_{0}$

4 let $M^{\prime}$ contain edge $(m,M(m))$ for each man $m$ such that
$M(m)=_{m}M_{z}(m)$

5 let $E_{d}$ contain all edges of $M$

6 let $G_{d}$ be the directed graph $(V,E_{d})$ such that each edge $(m,w)\in
E_{d}\cap M$ is directed from $w$ to $m$ and every other edge $(m,w)$ is
directed from $m$ to $w$

7 $E^{\prime}\leftarrow E\backslash E_{d}$

8 let $E_{c}=M^{\prime}$ and $G_{c}=(V,E_{c})$

9 for each $(m,w)\in M$ remove from $E^{\prime}$ each edge $(m^{\prime},w)$
such that $m^{\prime}\prec_{w}m$ and each edge $(m,w^{\prime})$ such that
$w^{\prime}\succeq_{m}w$

10 repeat

11 while $(\exists m\in A)$ $deg_{G_{c}}(m)=0$ and $outdeg(S(m))=0$ do

12 add the set $E_{m}$ of top choices of $m$ from $E^{\prime}$ to $E_{d}$

13 if $outdeg(S(m))=0$ then

14 add every edge $(m,w)\in E_{m}$ such that $m\succ_{w}M(w)$ and
$M(m)\succ_{m}w$ to $E_{c}$

15 for each edge $(m,w)$ of $E_{c}$ that becomes strictly dominated by some
added

16 edge $(m^{\prime},w)$ remove it from $G_{c}$

17 remove $E_{m}$ from $E^{\prime}$

18 end if

19 end while

20

21 for each $m\in A$ such that $outdeg(S(m))=0$ do

22 delete all lowest ranked edge in $E_{c}\cup E^{\prime}$ incident to any
$w\in S$ such that $w$ is

23 multiple engaged

24 end for

25

26 while $(\exists S)$ $outdeg(S)=0$ and $E_{c}$ is a perfect matching on $S$
do

27 $M\leftarrow(E_{c}\cap S)\cup(M\backslash S)$

28 $M_{i}\leftarrow M$

29 output $M_{i}$

30 $i\leftarrow i+1$

31 update $G_{c}$ and $G_{d}$: $E_{c}\cap S$ contains only edges $(m,M(m))$
such that

32 $M(m)=_{m}M_{z}(m)$; an edge $(m,w)\in S$ stays in $G_{d}$ only if $w=M(m)$

33 and $rank_{w}(m)\leq rank_{M}(w)$

34 end while

until $(\forall m\in A)$ $rank_{M}(m)=rank_{M_{z}}(m)$

Algorithm 2 Computing a maximal sequence of super-stable matchings

###  4.1 Correctness of Algorithm 2

Lemma 11 proves that any edge removed from $G_{d}$ (line 2 and line 2) never
block any super-stable matching that the algorithm will output.

######  Lemma 11.

Let $M$ be a super-stable matching in $G$. For any successor $N$ of $M$ such
that $N$ is also a super-stable matching in $G$ and each $(m,w)\in M$, any
edge $(m,w^{\prime})$ such that $w^{\prime}\succeq_{m}w$ or $(m^{\prime},w)$
such that $m\succ_{w}m^{\prime}$ cannot block $N$.

###### Proof.

For any edge $(m,w^{\prime})$ such that $w^{\prime}\succeq_{m}w$, this edge
$(m,w^{\prime})$ cannot block $M$ since $M$ is super-stable. Thus we must have
$m\prec_{w^{\prime}}M(w^{\prime})$. The matching $N$ is a successor of $M$
from the man’s point of view, hence from the woman’s point of view, $M$ is a
successor of $N$. Then we have $m\prec_{w^{\prime}}N(w^{\prime})$ since
$M(w^{\prime})\preceq_{w^{\prime}}N(w^{\prime})$, which implies that the edge
$(m,w^{\prime})$ would not block $N$. Similarly, for any edge $(m^{\prime},w)$
such that $m\succ_{w}m^{\prime}$, we have $N(w)\succ_{w}m^{\prime}$ since
$N(w)\succeq_{w}M(w)$, which implies that the edge $(m^{\prime},w)$ would not
block $N$. ∎

######  Lemma 12.

No edge deleted in line 2 can belong to any super-stable matching $N$
dominated by $M$.

###### Proof.

Suppose that the algorithm deletes an edge $(m,w)$ from $E_{c}$ because it is
dominated by some edge $(m^{\prime},w)$, i.e. $w$ strictly prefer $m^{\prime}$
to $m$. We want to show that $(m,w)$ cannot belong to any super-stable
matching dominated by $M$. Suppose, for a contradiction, that the edge $(m,w)$
belongs to a super-stable matching $N$ dominated by $M$. $m^{\prime}$ must
match to another woman $w^{\prime}$ in $N$ and $m^{\prime}$ strictly prefers
$w^{\prime}$ to $w$, otherwise the edge $(m^{\prime},w)$ would block $N$. Thus
we have that $rank_{M}(m^{\prime})\leq
rank_{m^{\prime}}(w^{\prime})<rank_{m^{\prime}}(w)$, where the first
inequality comes from the fact that $N$ is dominated by $M$. Hence, we have
two cases shown as below:
Case $1$:
$rank_{M}(m^{\prime})<rank_{m^{\prime}}(w^{\prime})<rank_{m^{\prime}}(w)$. In
this case, $w^{\prime}$ must match to a different man $M(w^{\prime})$ other
than $m^{\prime}$ in $M$. Again because $M$ dominates $N$,
$m^{\prime}\succeq_{w^{\prime}}M(w^{\prime})$. If
$m^{\prime}\succ_{w^{\prime}}M(w^{\prime})$, by our algorithm, in order to let
$(m^{\prime},w^{\prime})$ belong to $E_{d}$, $(m^{\prime},w^{\prime})$ must
also belong to $E_{c}$ and this requires that
$rank_{m^{\prime}}(w)=rank_{m^{\prime}}(w^{\prime})$, which contradicts with
the fact that is $rank_{m^{\prime}}(w^{\prime})<rank_{m^{\prime}}(w)$.
Case $2$:
$rank_{M}(m^{\prime})=rank_{m^{\prime}}(w^{\prime})<rank_{m^{\prime}}(w)$.
First, we rule out the case that $m^{\prime}$ is indifferent between
$M(m^{\prime})$ and $w^{\prime}=N(m^{\prime})$ by Lemma 3. Thus we must have
$w^{\prime}=M(m^{\prime})=N(m^{\prime})$. In order to prove a contradiction,
we need the property of strongly connected component. $m^{\prime}$ and $w$ are
in the same strongly connected component, hence there must be a directed path
$P$ from $w$ to $m^{\prime}$. Arc $(w^{\prime},m^{\prime})$ is the unique arc
that points to $m^{\prime}$ since $(m^{\prime},w^{\prime})\in M$. Hence, there
must be an arc $(m^{\prime\prime},w^{\prime})$ in $P$. If
$rank_{M}(m^{\prime\prime})<rank_{N}(m^{\prime\prime})$, then
$rank_{m^{\prime\prime}}(w^{\prime})\leq rank_{N}(m^{\prime\prime})$ , thus
$(m^{\prime\prime},w^{\prime})$ would block $N$. So
$M(m^{\prime\prime})=N(m^{\prime\prime})$. Let
$w^{\prime\prime}=M(m^{\prime\prime})$. $(m^{\prime\prime},w^{\prime\prime})$
is also in path $P$, Let us continue this process until it reaches to $w$ and
we will have $M(w)=N(w)$, which is a contradiction. ∎

######  Lemma 13.

No edge deleted in line 2 can belong to any super-stable matching $N$
dominated by $M$.

###### Proof.

Suppose that an edge $(m,w)$ is deleted in line 2, there must be an edge
$(m^{\prime},w)\in E_{c}$ such that $m=_{w}m^{\prime}$. Let $N$ be a super-
stable matching dominated by $M$ that includes the edge $(m,w)$. $m^{\prime}$
must match to a woman $w^{\prime}$ in $N$ and $m^{\prime}$ strictly prefer
$w^{\prime}$ to $w$, otherwise the edge $(m^{\prime},w)$ would block $N$.
$m^{\prime}$ and $w$ are in the same strongly connected component. By the same
argument as in Lemma 12, we will have a contradiction. We omit the proof here.
∎

######  Lemma 14.

The output matching $M_{i}$ is super-stable and a strict successor of
$M_{i-1}$.

###### Proof.

Note that the algorithm outputs $M_{i}$ when the edge set $E_{c}$ is a perfect
matching in a strongly connected component $S$ with no outgoing edges and
$M_{i}=(M_{i-1}\backslash S)\cup(E_{c}\cap S)$. Suppose, for a contradiction,
that $M_{i}$ is blocked by some edge $(m,w)\in E_{d}$. There are four cases.
Case 1: $m\notin S$ and $w\notin S$, it is obvious that $(m,w)$ cannot block
$M_{i}$, since it would block $M_{i-1}$ as well.
Case 2: $m\in S$ and $w\notin S$, this is not possible, because this will
imply $S$ has an outgoing edge in $E_{d}$.
Case 3: $m\notin S$ and $w\in S$, then $M_{i}(m)(=M_{i-1}(m))\succ_{m}w$,
hence $(m,w)$ would not block $M_{i}$.
Case 4: $m\in S$ and $w\in S$, if $(m,w)$ never belong to $E_{c}$, then
$M_{i}(w)\succ_{w}M_{i-1}(w)=_{w}m$, $(m,w)$ can not block $M_{i}$; if $(m,w)$
once belongs to $E_{c}$ and got deleted later, then $w$ always get a strictly
better partner than $m$. We prove that no edge from $E_{d}$ can block $M_{i}$.
There might be some other edges $e\not\in E_{d}$ that can potentially block
$M_{i}$. These edges are deleted during the updating of $E_{d}$. Lemma 11
gives a proof that these set of edges cannot block any matching $N$ that is
dominated by $M_{i-1}$. Hence $M_{i}$ is super-stable.

Next we prove that $M_{i}$ is a strict successor of $M_{i-1}$. Suppose not and
let $m$ be any man in $S$ and $N$ a successor of $M_{i-1}$ such that
$M_{i-1}(m)\succ N(m)\succ M_{i}(m)$. If $(m,N(m))\in E_{c}$ and is not
deleted during the algorithm, then $(m,M_{i}(m))$ would not be in $E_{c}$,
which is not true. Since $N$ is a successor of $M$ and is super-stable, by
Lemma 12 and Lemma 13, the edge $(m,N(m))$ can never once belong to $E_{c}$.
Let $w=N(m)$, by our updating rule of $E_{d}$, we have $N(w)\succeq_{w}M(w)$.
While if $N(w)\succ_{w}M(w)$, then the edge $(m,w)$ must once belong to
$E_{c}$. Thus we have $N(w)=_{w}M(w)$, which violates Lemma 3. ∎

######  Lemma 15.

If $M_{i}\neq M_{z}$, the algorithm always outputs a matching.

###### Proof.

The algorithm will end without outputting any matching if and only if in line
2 the while loop, it cannot find any strongly connected component with no
outgoing edges. Note that every directed graph can be expressed as a directed
acyclic graph of its strongly connected components. Hence, we can always find
a strongly connected component without outgoing edges. ∎

######  Theorem 16.

Algorithm 2 computes a maximal sequence of super-stable matchings.

###### Proof.

By Lemma 14 and Lemma 15, it is obvious that Algorithm 2 outputs a maximal
sequence of super-stable matchings. ∎

###  4.2 Running Time of Algorithm 2

######  Theorem 17.

The running time of Algorithm 2 is $O(mn)$.

###### Proof.

Each time we add new edges into $E_{d}$, we need to compute strongly connected
components of $G_{d}$. Computing strongly connected component of any directed
graph $G^{\prime}=(V^{\prime},E^{\prime})$ can be done in $O(E)$ time. Each
edge $e$ of $G$ is added to $G_{d}$ at most once, and $G_{d}$ is always a
subgraph of $G$. Hence, a naive implementation takes $O(m^{2})$ on computing
strongly connected components of $G_{d}$. As mentioned in [12], Pearce [23]
and Pearce and Kelly [24] sketch how to extend their algorithm and that of
Marchetti-Spaccamela et al. [25] to compute strongly connected component
dynamically. Their algorithm runs in $O(mn)$ if edges can only be added to the
graph and not deleted. The edges in $G_{d}$ can be deleted during the
algorithm, but they are deleted only when $E_{c}$ is perfect on a strongly
connected component without outgoing edges. Thus, other strongly connected
components are unchanged. Also as mentioned in [12], the edges remaining in
the selected strongly connected component can be treated as they were added
anew to the graph. Since the ranks of men increase as we output subsequent
super-stable matchings, each edge can be added anew to $G_{d}$ constant number
of times. Thus, the amortized cost of edge insertion remains unchanged. The
reader can easily check the other part of the algorithm takes at most $O(m)$
time. Hence, the total time is $O(mn)$. ∎

###  4.3 Rotation Poset

We have shown all rotations $D(\mathcal{M}_{G})$ can be found in time $O(mn)$
by Algorithm 2. It remains to show how to efficiently construct the precedence
ration $\prec$ on $D(\mathcal{M}_{G})$. Our construction is essentially the
same as the construction given in [3] for the classical stable marriage
problem. The only difference here is that one rotation for super-stable
matchings can be one or multiple cycles, while one rotation for stable
matchings in the classical stable marriage problem is always a cycle. For the
completeness, we briefly sketch it. The reader can find more details in [3].

Let $\rho=\\{(m_{1},w_{1}),\cdots,(m_{k-1},w_{k-1})\\}$ be a rotation. Each
rotation corresponds to the symmetric difference of two consecutive super-
stable matchings in a maximal chain of $\mathcal{M}_{G}$. We say $\rho$ is
exposed to a super-stable matching $M$ if $\rho\in M$ and we can eliminate it
to obtain another super-stable matching $M^{\prime}=M\oplus\rho$.

We say that $\rho$ moves $m_{i}$ down to $w_{i+1}$ and moves $w_{i}$ up to
$m_{i-1}$ for each $i\in[k]$. We also say $\rho$ moves $m_{i}$ below $w$ if
$w_{i-1}\prec_{m_{i}}w\preceq_{m_{i}}w_{i}$ and moves $w_{i}$ above $m$ if
$m_{i}\preceq_{w_{i}}m\prec_{w_{i}}m_{i-1}$.

Let us consider a directed graph $(D(\mathcal{M}_{G}),E)$, $E$ contains two
types of edges:

  * •

Type 1: For each pair $(m,w)\in\rho$, if $\rho^{\prime}$ is the unique
rotation that moves $m$ down to $w$, then $(\rho^{\prime},\rho)\in E$.

  * •

Type 2: If $\rho$ moves $m$ below $w$ and $\rho^{\prime}\neq\rho$ is the
unique rotation that moves $w$ above $m$, then $(\rho^{\prime},\rho)\in E$.

The algorithm to construct the set $E$ is simple. For each rotation $\rho$ and
each pair $(m_{i},w_{i})\in\rho$, label $w_{i}$ in $m_{i}$’s preference list
with a type 1 label of $\rho$, and for each $m$ strictly between $m_{i}$ and
$m_{i-1}$ on $w_{i}$’s list, label $w_{i}$ in $m$’s preference list with a
type 2 label of $\rho$. Then, traverse each woman $w$ on $m$’s preference
list, set $\rho^{*}=\emptyset$. If $w$ has a type 1 label of $\rho$, add
$(\rho^{*},\rho)$ into $E$ and set $\rho^{*}=\rho$. If $w$ has a type 2 label
of $\rho$, add $(\rho,\rho^{*})$ into $E$. The algorithm takes $O(m)$ time
since it only traverse the preference lists once.

It turns out that the transitive closure of $(D(\mathcal{M}_{G}),E)$ is
exactly $(D(\mathcal{M}_{G}),\prec)$. The reader can find the proof in Irving
and Gusfield’s book [3].

We summarize Section 4 with the following theorem.

######  Theorem 18.

The partial order $(D(\mathcal{M}_{G}),\prec)$ can be constructed in $O(mn)$.

###### Proof.

The construction of $D(\mathcal{M}_{G})$ takes $O(mn)$ time by running
Algorithm 2. The precedence relation can be constructed in $O(m)$ time. Hence,
the time complexity is $O(mn)$. ∎

##  5 The Super-stable Matching Polytope

In this section, we give a polyhedral characterisation of the set of all
super-stable matchings and prove that the super-stable matching polytope is
integral. The main result is the following theorem.

######  Theorem 19.

Let $G=(V,E)$ be a stable matching problem with ties where the graph $G$ is
bipartite, then the super-stable matching polytope $SUSM(G)$ is described by
the following linear system:

$\displaystyle\sum_{u\in N(v)}x_{u,v}\leq 1,$ $\displaystyle\forall v\in V,$
(1a) $\displaystyle\sum_{i>_{u}v}x_{u,i}+\sum_{j>_{v}u}x_{j,v}+x_{u,v}\geq 1,$
$\displaystyle\forall(u,v)\in E,$ (1b) $\displaystyle x_{u,v}\geq 0,$
$\displaystyle\forall(u,v)\in E$ (1c)

where $N(v)$ denotes the set of neighbors of $v$ in $G$, and $w>_{u}v$ means
$u$ prefers $w$ to $v$.

###### Proof.

Let $x$ be a feasible solution. Define $E^{+}$ to be the set of edges $(u,v)$
with $x_{u,v}>0$, and $V^{+}$ the set of vertices covered by $E^{+}$. For each
$u\in V^{+}$, let $N^{*}(u)$ be the maximal elements in $\\{i:x_{u,i}>0\\}$.
Note that there might be multiple maximal elements that form a tie.

We first show the following lemma.

######  Lemma 20.

For each vertex $u$ and each vertex $v\in N^{*}(u)$, then $u$ is the unique
minimal element in $\\{j:x_{j,v}>0\\}$ and that $\sum_{j\in N(v)}x_{j,v}=1$.

###### Proof.

Indeed, (1b) implies

$1\leq\sum_{j>_{v}u}x_{j,v}+x_{u,v}=\sum_{j\in
N(v)}x_{j,v}-\sum_{j<_{v}u}x_{j,v}-\sum_{\begin{subarray}{c}j=_{v}u;\\\ j\neq
u\end{subarray}}x_{j,v}\leq
1-\sum_{j<_{v}u}x_{j,v}-\sum_{\begin{subarray}{c}j=_{v}u;\\\ j\neq
u\end{subarray}}x_{j,v}\leq 1$ (2)

Hence we have equality throughout in (2). This implies that $x_{j,v}=0$ for
each $\\{j:j<_{v}u\\}$ and each $\\{j:j=_{v}u;j\neq u\\}$ and that $\sum_{j\in
N(v)}x_{j,v}=1$. Since $x_{j,v}=0$ for each $\\{j:j=_{v}u;j\neq u\\}$, $v$
strictly prefers any other vertices in $\\{j:x_{j,v}>0\\}$ over $u$, making
$u$ the unique minimal element in $\\{j:x_{j,v}>0\\}$. ∎

We then prove that for any $v$ such that $v\in N^{*}(u)$ for some $u$, then
$u$ is unique. Suppose not, there is a vertex $u^{\prime}\neq u$ and $v\in
N^{*}(u^{\prime})$. By Lemma 20, $u$ is the unique minimal element in
$\\{j:x_{j,v}>0\\}$, and $u^{\prime}$ is the unique minimal element in
$\\{j:x_{j,v}>0\\}$, contradiction.

Now let $U$ and $W$ be the color classes of $G$. For any $u\in U\cap V^{+}$,
there is at least one unique vertex $w\in N^{*}(u)$, such that $\sum_{j\in
N(w)}x_{j,w}=1$. Let $F_{W}(x)$ be the set of these vertices. Formally,
$F_{W}(x)=\\{w:w\in N^{*}(u),u\in U\cap V^{+}\\}$. Then we have
$|F_{W}(x)|\geq|U\cap V^{+}|$. We also have that

$|F_{W}(x)|=\sum_{w\in F_{W}(x)}\sum_{j\in N(w)}x_{j,w}=\sum_{j\in U\cap
V^{+}}\sum_{w\in F_{W}(x)}x_{j,w}\leq\sum_{j\in U\cap V^{+}}1=|U\cap V^{+}|$
(3)

implying that $|F_{W}(x)|=|U\cap V^{+}|$. Hence, we conclude that for each
$u\in U\cap V^{+}$, $|N^{*}(u)|=1$, which implies that $u$ has an unique
maximal element in $\\{i:x_{u,i}>0\\}$. Since $|N^{*}(u)|=1$, we denote this
unique vertex as $x^{*}(u)$. We then have the following corollary.

######  Corollary 21.

There is a bijection between $U\cap V^{+}$ and $F_{W}(x)$, and for each $u\in
U\cap V^{+}$, $\sum_{i\in N(u)}x_{u,i}=1$.

Similarly, we may define $F_{U}(x)=\\{u:u\in N^{*}(w),w\in W\cap V^{+}\\}$ and
we have

######  Corollary 22.

There is a bijection between $W\cap V^{+}$ and $F_{U}(x)$, and for each $w\in
W\cap V^{+}$, $\sum_{j\in N(w)}x_{j,w}=1$.

Then we have $|U\cap V^{+}|=|F_{W}(x)|\leq|W\cap V^{+}|$ and $|W\cap
V^{+}|=|F_{U}(x)|\leq|U\cap V^{+}|$, implying $|U\cap V^{+}|=|W\cap
V^{+}|=|F_{W}(x)|=|F_{U}(x)|$. Then any $u\in U\cap V^{+}$ is also in
$F_{U}(x)$, hence, $u$ has an unique minimal element, denoted by $x_{*}(u)$.

The bijection between $U\cap V^{+}$ and $F_{W}(x)$ forms a perfect matching
$M$ in $(V^{+},E^{+})$, i.e. the set of edges $\\{(u,x^{*}(u)):u\in U\cap
V^{+}\\}$. Similarly, the bijection between $W\cap V^{+}$ and $F_{U}(x)$ forms
another perfect matching $N$, i.e. the set of edges $\\{(x^{*}(w),w):w\in
W\cap V^{+}\\}$.

Consider the vector $x^{\prime}=x+\varepsilon\chi^{M}-\varepsilon\chi^{N}$,
with $\varepsilon$ close enough to $0$ (positive or negative). we will show
that $x^{\prime}$ is also feasible solution of (1a)-(1c). It is easy to see
that $x^{\prime}$ satisfies (1a) and (1c). For each vertex $u\in U\cap V^{+}$,
there is an unique maximal element $x^{*}(u)$ and $(u,x^{*}(u))\in M$ and an
unique minimal element $x_{*}(u)$ and $(u,x_{*}(u))\in N$, implying
$\sum_{i\in N(u)}x^{\prime}_{u,i}=\sum_{i\in N(u)}x_{u,i}\leq 1$. To see that
$x^{\prime}$ satisfies (1b), let $(u,v)$ be an edge in $E^{+}$ attaining
equality in (1b). The case that $(u,v)\in M$ or $(u,v)\in N$ is trivial. So
assume that $(u,v)\notin M$ and $(u,v)\notin N$. The edge $(u,x^{*}(u))\in M$
and $x^{*}(u)>_{u}v$. There is no other edge in $\\{(u,i):i\in N(u)\\}$
belongs to $M$. We prove that there is no edge $(j,v)$ in $M$ and $j>_{v}u$
since if $(j,v)\in M$, $j$ is the minimal element of $v$. Similarly, we can
prove that there is exact one edge $(j,v)\in N$ and $j>_{v}u$. Concluding,
$\sum_{i>_{u}v}x^{\prime}_{u,i}+\sum_{j>_{v}u}x^{\prime}_{j,v}+x^{\prime}_{u,v}=\sum_{i>_{u}v}x_{u,i}+\sum_{j>_{v}u}x_{j,v}+x_{u,v}=1$.
Let $x$ be an extreme point. The feasibility of $x^{\prime}$ implies that
$\chi^{M}=\chi^{N}$, that is, $M=N$. So $E^{+}=M$ since the maximal element is
the same as the minimal element for each vertex, hence, $x=\chi^{M}$. ∎

###  5.1 Self-Duality

Let’s consider the linear program: ∑_(u,v) ∈E x_u,v(LP) x ∈FSUSM(G,P).

The dual problem with variables $(\alpha,\beta)\in R^{V}\times R^{E}$, is
given by

∑_v ∈V α_v - ∑_(u,v) ∈E β_u,v(DLP) α_u + α_v - ∑_i ¡_u v β_u,i - ∑_j ¡_v u
β_v,j - β_u,v≥1, ∀(u,v) ∈E, α_v ≥0, ∀v ∈V, β_u,v ≥0, ∀(u,v) ∈E.

######  Lemma 23 (Self-Duality).

Each $x\in FSUSM(G,P)$ is an optimal solution of $(\bf{LP})$ and $(\alpha,x)$
is an optimal solution of $(\bf{DLP})$, where

$\alpha_{v}=\sum_{i\in N(v)}x_{v,i}\hskip 14.45377pt\forall v\in V.$ (4)

###### Proof.

Let $x\in FSUSM(G,P)$ and let $\alpha$ be defined by (4). Let $(u,v)\in E$, we
have that

$\displaystyle\alpha_{u}+\alpha_{v}-\sum_{i<_{u}v}x_{u,i}-\sum_{j<_{v}u}x_{v,j}-x_{u,v}$
$\displaystyle=$ $\displaystyle\sum_{i\in N(u)}x_{u,i}+\sum_{j\in
N(v)}x_{v,j}-\sum_{i<_{u}v}x_{u,i}-\sum_{j<_{v}u}x_{v,j}-x_{u,v}$
$\displaystyle=$
$\displaystyle\sum_{i>_{u}v}x_{u,i}+\sum_{\begin{subarray}{c}i=_{u}v;\\\ i\neq
v\end{subarray}}x_{u,i}+\sum_{j>_{v}u}x_{v,j}+\sum_{\begin{subarray}{c}j=_{v}u;\\\
j\neq u\end{subarray}}x_{v,j}+x_{u,v}$ $\displaystyle\geq$
$\displaystyle\sum_{i>_{u}v}x_{u,i}+\sum_{j>_{v}u}x_{v,j}+x_{u,v}$
$\displaystyle\geq$ $\displaystyle 1,$

where the last two inequalities hold since $x$ satisfies (1c) and (1b). Hence
$(\alpha,x)$ is feasible for $(DLP)$. To see that $x$ and $(\alpha,x)$ are
optimal solutions of $(LP)$ and $(DLP)$, respectively. Note that

$\sum_{v\in V}\alpha_{v}-\sum_{(u,v)\in E}x_{u,v}=2\sum_{(u,v)\in
E}x_{u,v}-\sum_{(u,v)\in E}x_{u,v}=\sum_{(u,v)\in E}x_{u,v},$

so the objective function in $(LP)$ and that in $(DLP)$ are equal. Thus, the
weak duality theorem of linear programming implies that $x$ is optimal for
$(LP)$ and $(\alpha,x)$ is optimal for $(DLP)$. ∎

###  5.2 Partial Order Preference Lists

Partial order preference lists are generalisation of preference lists with
ties in such a way that the preference list of each man or woman is an
arbitrary partial order. It turns out that the linear system (1a)-(1c) can
also describe the set of all super-stable matchings with partial order
preference list.

###### Proof.

Let $x$ be a feasible solution. Define $E^{+}$ to be the set of edges $(u,v)$
with $x_{u,v}>0$, and $V^{+}$ the set of vertices covered by $E^{+}$. For each
$u\in V^{+}$, let $N^{*}(u)$ be the maximal elements in $\\{i:x_{u,i}>0\\}$.
Note that there might be multiple maximal elements that are incomparable to
each other.

The following lemma is an analogue to Lemma 20.

######  Lemma 24.

For each vertex $u$ and each vertex $v\in N^{*}(u)$, then $u$ is the unique
minimal element in $\\{j:x_{j,v}>0\\}$ and that $\sum_{j\in N(v)}x_{j,v}=1$.

###### Proof.

Indeed, (1b) implies

$1\leq\sum_{j>_{v}u}x_{j,v}+x_{u,v}=\sum_{j\in
N(v)}x_{j,v}-\sum_{j<_{v}u}x_{j,v}-\sum_{j\parallel_{v}u}x_{j,v}\leq
1-\sum_{j<_{v}u}x_{j,v}-\sum_{j\parallel_{v}u}x_{j,v}\leq 1$ (5)

, where $w\parallel_{u}v$ means $w$ is incomparable with $v$ in $u$’s
preference list. Hence we have equality throughout in (2). This implies that
$x_{j,v}=0$ for each $\\{j:j<_{v}u\\}$ and each $\\{j:j\parallel_{v}u\\}$ and
that $\sum_{j\in N(v)}x_{j,v}=1$. Since $x_{j,v}=0$ for each
$\\{j:j\parallel_{v}u\\}$, $v$ strictly prefers any other vertices in
$\\{j:x_{j,v}>0\\}$ over $u$, making $u$ the unique minimal element in
$\\{j:x_{j,v}>0\\}$. ∎

The rest of the proof is essentially the same as in Theorem 19. ∎

###  5.3 The Strongly Stable Matching Polytope

Kunysz [5] gives a linear system that characterizes the set of all strongly
stable matchings and proves this linear system is integral using the duality
theory of linear programming. Here, we give an alternate and simpler proof
that does not rely on the duality theory and uses only Hall’s theorem.

######  Theorem 25 (Kunysz, [5]).

Let $G=(V,E)$ be a stable matching problem with ties where the graph $G$ is
bipartite, then the strongly stable matching polytope $SSM(G)$ is described by
the following linear system:

$\displaystyle\sum_{u\in N(v)}x_{u,v}\leq 1,$ $\displaystyle\forall v\in V,$
(6a)
$\displaystyle\sum_{i>_{u}v}x_{u,i}+\sum_{j>_{v}u}x_{j,v}+\sum_{k=_{u}v}x_{u,k}\geq
1,$ $\displaystyle\forall(u,v)\in E,$ (6b)
$\displaystyle\sum_{i>_{u}v}x_{u,i}+\sum_{j>_{v}u}x_{j,v}+\sum_{k=_{v}u}x_{k,v}\geq
1,$ $\displaystyle\forall(u,v)\in E,$ (6c) $\displaystyle x_{u,v}\geq 0,$
$\displaystyle\forall(u,v)\in E$ (6d)

where $N(v)$ denotes the set of neighbors of $v$ in $G$, and $w>_{u}v$ means
$u$ prefers $w$ to $v$.

We give an alternative proof that does not rely on the duality theory of
linear programming.

###### Proof.

It is easy to verify that the incidence vector of any strongly stable matching
satisfies constraints (6a)-(6d). We need to prove each extreme point of the
polytope defined by (6a)-(6d) is integral.

Let $x$ be a feasible solution. Define $E^{+}$ to be the set of edges $(u,v)$
with $x_{u,v}>0$, and $V^{+}$ the set of vertices covered by $E^{+}$. For each
$u\in V^{+}$, let $N^{*}(u)$ be the set of maximal elements in
$\\{i:x_{u,i}>0\\}$. Note that there might be multiple maximal elements that
form a tie. Similarly, for each $u\in V^{+}$, let $N_{*}(u)$ be the set of
minimal elements in $\\{i:x_{u,i}>0\\}$.

We first show the following lemma.

######  Lemma 26.

For each vertex $u$ and each vertex $v\in N^{*}(u)$, then $u\in N_{*}(v)$ and
that $\sum_{j\in N(v)}x_{j,v}=1$, and
$\sum_{k=_{u}v}x_{u,k}\geq\sum_{k=_{v}u}x_{k,v}$.

###### Proof.

Indeed, (6c) implies

$1\leq\sum_{j>_{v}u}x_{j,v}+\sum_{k=_{v}u}x_{k,v}\leq\sum_{j\in
N(v)}x_{j,v}-\sum_{j<_{v}u}x_{j,v}\leq 1-\sum_{j<_{v}u}x_{j,v}\leq 1$ (7)

Hence we have equality throughout in (7). This implies that $x_{j,v}=0$ for
each $\\{j:j<_{v}u\\}$ and that $\sum_{j\in N(v)}x_{j,v}=1$. Hence, $u\in
N_{*}(v)$. (6b) implies

$1\leq\sum_{j>_{v}u}x_{j,v}+\sum_{k=_{u}v}x_{u,k}\leq
1-\sum_{k=_{v}u}x_{k,v}+\sum_{k=_{u}v}x_{u,k}$

Hence, $\sum_{k=_{u}v}x_{u,k}\geq\sum_{k=_{v}u}x_{k,v}$. ∎

Now let $U$ and $W$ be the color classes of $G$. Let $E^{*}(x)$ be the set of
edges $\\{(u,v):u\in U\cap V^{+},v\in N^{*}(u)\\}$ and $F_{W}(x)$ be the set
of vertices in $W$ and covered by $E^{*}(x)$. We will show that the subgraph
induced by $E^{*}(x)$ contains a perfect matching $M$.

Suppose not, by Hall’s theorem, let $S$ be the unique critical subset of
$U\cap V^{+}$. A subset of $X$ is critical if it is maximally deficient and
contains no maximally deficient proper subset. Hence, we have $|N(S)|<|S|$ and
there is a matching $M^{\prime}$ saturating for $N(S)$ in the subgraph induced
by $S\cup N(S)$. Fixing the matching $M^{\prime}$, let $S^{\prime}$ be the set
of vertices in $S$ that is matched in $M^{\prime}$, so $S^{\prime}\subsetneq
S$. By Lemma 26, we have

$\displaystyle\sum_{u\in S^{\prime}}\sum_{k\in N^{*}(u)}x_{u,k}$
$\displaystyle\geq\sum_{v\in N(S)}\sum_{k=_{v}M^{\prime}(v)}x_{k,v}$ (8)
$\displaystyle\geq\sum_{v\in N(S)}\sum_{k\in S}x_{k,v}$ (9)
$\displaystyle=\sum_{u\in S}\sum_{k\in N^{*}(u)}x_{u,k}$ (10)

The first equality follows from Lemma 26. The second inequality follows from
that each vertex $v\in N(S)$ is indifferent with all neighbors. The third
equality follows by double counting. Hence, the vertices in $S\backslash
S^{\prime}$ are isolated, contradiction. So we also have $|U\cap
V^{+}|=|F_{W}(x)|$. Again by Lemma 26, we have

$\sum_{u\in U\cap V^{+}}\sum_{k=_{u}M(u)}x_{u,k}\geq\sum_{v\in
F_{W}(x)}\sum_{k=_{v}M(v)}x_{k,v}\geq\sum_{u\in U\cap
V^{+}}\sum_{k=_{u}M(u)}x_{u,k}$ (11)

Hence, we have equality throughout (11). So for each $v\in F_{W}(x)$ and each
$k\in N_{*}(v)$, $v=N^{*}(k)$.

Similarly, let $E_{*}$ be the set of edges $\\{(u,v):v\in W\cap V^{+},u\in
N^{*}(v)\\}$ and $F_{U}(x)$ be the set of vertices in $U$ and covered by
$E^{+}$. The subgraph induced by $E_{*}$ contains a perfect matching $N$.
Hence, $|W\cap V^{+}|=|F_{U}(x)|$. So $|U\cap V^{+}|=|W\cap
V^{+}|=|F_{U}(x)|=|F_{W}(x)|$. It follows that $E_{*}$ is exactly the set of
edges $\\{(u,v):u\in U\cap V^{+},v\in N_{*}(u)\\}$.

Consider the vector $x^{\prime}=x+\varepsilon\chi^{M}-\varepsilon\chi^{N}$,
with $\varepsilon$ close enough to $0$ (positive or negative). we will show
that $x^{\prime}$ is also feasible solution of (6a)-(6d). It is easy to see
that $x^{\prime}$ satisfies (6a) and (6d). For each vertex $u\in U\cap V^{+}$,
there is one edge in $M$ and one edge in $N$ incident to it, implying
$\sum_{i\in N(u)}x^{\prime}_{u,i}=\sum_{i\in N(u)}x_{u,i}\leq 1$. To see that
$x^{\prime}$ satisfies (6b), let $(u,v)$ be an edge in $E^{+}$ attaining
equality in (6b). First we know that there is one edge in $M$ incident to $u$
such that $M(u)\geq_{u}v$. Also there is no $M$ edge incident to $v$ and
$M(v)>_{v}u$ since $M(v)\in N_{*}(v)$. Similarly, there is one edge in $N$
incident to $v$ such that $M(v)\geq_{v}u$. Then we have two cases. If there is
one edge in $N$ incident to $v$ such that $N(v)>_{v}u$, then there is no edge
in $N$ incident to $u$ such that $M(u)\geq_{u}v$, because otherwise, $u\in
N^{*}(v)$, which contradicts with $N(v)>_{v}u$. The other case is that there
is one edge in $N$ incident to $v$ such that $N(v)=_{v}u$, then there must be
an edge in $N$ incident to $u$ such that $N(u)=_{u}v$. Hence,
$\sum_{i>_{u}v}x^{\prime}_{u,i}+\sum_{j>_{v}u}x^{\prime}_{j,v}+\sum_{k=_{u}v}x^{\prime}_{u,k}=\sum_{i>_{u}v}x_{u,i}+\sum_{j>_{v}u}x_{j,v}+\sum_{k=_{u}v}x_{u,k}=1$.
Similarly, we can prove $x^{\prime}$ satisfies (6c). Let $x$ be an extreme
point. The feasibility of $x^{\prime}$ implies that $\chi^{M}=\chi^{N}$, that
is, $M=N$. So for each $v\in V^{+}$, we have $N^{*}(v)=N_{*}(v)$ and
$\sum_{k\in N^{*}(v)}x_{k,v}=1$. Then $x$ is an extreme point of the perfect
matching polytope of $(V^{+},E^{+})$. $x$ must be a perfect matching in
$(V^{+},E^{+})$. ∎

## References

  * [1] B. Spieker, “The set of super-stable marriages forms a distributive lattice,” _Discrete applied mathematics_ , vol. 58, no. 1, pp. 79–84, 1995.
  * [2] D. F. Manlove, “The structure of stable marriage with indifference,” _Discrete Applied Mathematics_ , vol. 122, no. 1-3, pp. 167–181, 2002.
  * [3] D. Gusfield and R. W. Irving, _The Stable marriage problem - structure and algorithms_ , ser. Foundations of computing series. MIT Press, 1989.
  * [4] R. W. Irving, “Stable marriage and indifference,” _Discrete Applied Mathematics_ , vol. 48, no. 3, pp. 261–272, 1994.
  * [5] A. Kunysz, “An algorithm for the maximum weight strongly stable matching problem,” in _29th International Symposium on Algorithms and Computation (ISAAC 2018)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [6] S. Scott, “A study of stable marriage problems with ties,” Ph.D. dissertation, University of Glasgow, 2005.
  * [7] T. Fleiner, R. W. Irving, and D. F. Manlove, “Efficient algorithms for generalized stable marriage and roommates problems,” _Theoretical computer science_ , vol. 381, no. 1-3, pp. 162–176, 2007.
  * [8] J. H. V. Vate, “Linear programming brings marital bliss,” _Operations Research Letters_ , vol. 8, no. 3, pp. 147–153, 1989.
  * [9] U. G. Rothblum, “Characterization of stable matchings as extreme points of a polytope,” _Mathematical Programming_ , vol. 54, no. 1-3, pp. 57–67, 1992\.
  * [10] C.-P. Teo and J. Sethuraman, “The geometry of fractional stable matchings and its applications,” _Mathematics of Operations Research_ , vol. 23, no. 4, pp. 874–891, 1998.
  * [11] T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch, “Strongly stable matchings in time o (nm) and extension to the hospitals-residents problem,” _ACM Transactions on Algorithms (TALG)_ , vol. 3, no. 2, pp. 15–es, 2007\.
  * [12] A. Kunysz, K. Paluch, and P. Ghosal, “Characterisation of strongly stable matchings,” in _Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms_. SIAM, 2016, pp. 107–119.
  * [13] K. Iwama, S. Miyazaki, Y. Morita, and D. Manlove, “Stable marriage with incomplete lists and ties,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 1999, pp. 443–452.
  * [14] E. McDermid, “A 3/2-approximation algorithm for general stable marriage,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2009, pp. 689–700.
  * [15] K. Paluch, “Faster and simpler approximation of stable matchings,” _Algorithms_ , vol. 7, no. 2, pp. 189–202, 2014.
  * [16] Z. Király, “Linear time local approximation algorithm for maximum stable marriage,” _Algorithms_ , vol. 6, no. 3, pp. 471–484, 2013.
  * [17] K. Iwama, S. Miyazaki, and H. Yanagisawa, “A 25/17-approximation algorithm for the stable marriage problem with one-sided ties,” _Algorithmica_ , vol. 68, no. 3, pp. 758–775, 2014.
  * [18] C.-C. Huang and T. Kavitha, “An improved approximation algorithm for the stable marriage problem with one-sided ties,” in _International Conference on Integer Programming and Combinatorial Optimization_. Springer, 2014, pp. 297–308.
  * [19] A. Radnai, “Approximation algorithms for the stable matching problem,” _Eötvös Lorand University_ , 2014.
  * [20] B. Dean and R. Jalasutram, “Factor revealing lps and stable matching with ties and incomplete lists,” in _Proceedings of the 3rd International Workshop on Matching Under Preferences_ , 2015, pp. 42–53.
  * [21] C.-K. Lam and C. G. Plaxton, “A (1+ 1/e)-approximation algorithm for maximum stable matching with one-sided ties and incomplete lists,” in _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 2019, pp. 2823–2840.
  * [22] G. Birkhoff _et al._ , “Rings of sets,” _Duke Mathematical Journal_ , vol. 3, no. 3, pp. 443–454, 1937.
  * [23] D. J. Pearce, “Some directed graph algorithms and their application to pointer analysis,” Ph.D. dissertation, University of London, 2005.
  * [24] D. J. Pearce and P. H. Kelly, “Online algorithms for topological order and strongly connected components,” Citeseer, Tech. Rep., 2003.
  * [25] A. Marchetti-Spaccamela, U. Nanni, and H. Rohnert, “Maintaining a topological order under edge insertions,” _Information Processing Letters_ , vol. 59, no. 1, pp. 53–58, 1996.