# Structural and algorithmic results for stable cycles
and partitions in the Roommates problem††thanks: Frederik Glitzner is
supported by a Minerva Scholarship from the School of Computing Science,
University of Glasgow. David Manlove is supported by the Engineering and
Physical Sciences Research Council, grant number EP/X013618/1.

Frederik Glitzner and David Manlove  0009-0002-2815-6368 0000-0001-6754-7308

###### Abstract

An instance $I$ of the Stable Roommates problem involves a set of agents, each
with ordinal preferences over the others. We seek a _stable matching_ , in
which no two agents have an incentive to deviate from their assignment. It is
well known that a stable matching is unlikely to exist when the number of
agents becomes large. A _stable partition_ provides a succinct certificate for
the unsolvability of $I$, although its significance extends beyond this. Apart
from being a useful structural tool to study the problem, every stable
partition corresponds to a _stable half-matching_ , in which agents are
assigned either one full unit or two half-units, and agents are in a stable
equilibrium in the sense that no two agents would prefer to be assigned more
units to each other. A stable partition always exists and has applications,
for example, in sports tournament scheduling and time-sharing applications.

In this paper, we investigate the stable partition structure further and show
how to efficiently enumerate all stable partitions and the cycles included in
such structures. Furthermore, we adapt known fairness and optimality criteria
from stable matchings to stable partitions. As there can be an exponential
number of stable partitions, we investigate the complexity of computing
different “fair” and “optimal” stable partitions. While a minimum-regret
stable partition always exists and can be computed in linear time, we prove
the NP-hardness of finding five other kinds of stable partitions that are
“optimal” with regards to their profile (measuring number of first, second,
third, etc., choices assigned). Furthermore, we give 2-approximation
algorithms for two of the optimal stable partition problems and show the
inapproximability within any constant factor for another.

Through this research, we contribute to a deeper understanding of stable
partitions from a combinatorial point of view, as well as the computational
complexity of computing “fair” or “optimal” stable half-matchings in practice,
closing the gap between integral and fractional stable matchings and paving
the way for further applications of stable partitions to unsolvable instances
and computationally hard stable matching problems.

##  1 Introduction

###  1.1 Background

The Stable Roommates problem (sr) is a classical combinatorial problem with
applications to computational social choice. Consider a group of friends that
want to play one hour of tennis, where everyone has preferences over who to
play with. Can we match them into pairs such that no two friends prefer to
play with each other rather than their assigned partners? If the problem
instance $I$ admits such a _stable matching_ $M$ which does not admit a
_blocking pair_ of agents which would rather be matched to each other than
their partners in $M$, then we call $I$ _solvable_. Otherwise, we call $I$
_unsolvable_. Even an instance with as few as 6 agents may be unsolvable,
which is illustrated in Example 2. In Example 2, $a_{1}$ ranks the agents
$a_{2}$, $a_{5}$, $a_{3}$, etc., in linear order. The problem instance admits
the matching $M=\\{\\{a_{1},a_{2}\\},\\{a_{3},a_{4}\\},\\{a_{5},a_{6}\\}\\}$
indicated in circles, the stability of which can be easily verified by hand by
looking at all agents that are not matched to their first choice and seeing
that no agent preferred to their partner would rather be matched to them than
their partner. On the other hand, Example 2 shows an example instance with six
agents that does not admit any stable matching (for which we will see a
certificate later).

$a_{1}$ | $a_{2}$ | $a_{5}$ | $a_{3}$ | $a_{4}$ | $a_{6}$
---|---|---|---|---|---
$a_{2}$ | $a_{5}$ | $a_{3}$ | $a_{1}$ | $a_{6}$ | $a_{4}$
$a_{3}$ | $a_{4}$ | $a_{2}$ | $a_{6}$ | $a_{1}$ | $a_{5}$
$a_{4}$ | $a_{1}$ | $a_{2}$ | $a_{5}$ | $a_{3}$ | $a_{6}$
$a_{5}$ | $a_{6}$ | $a_{2}$ | $a_{1}$ | $a_{4}$ | $a_{3}$
$a_{6}$ | $a_{5}$ | $a_{3}$ | $a_{2}$ | $a_{4}$ | $a_{1}$
Table 1: A solvable sr instance

$a_{1}$ | $a_{2}$ | $a_{5}$ | $a_{3}$ | $a_{4}$ | $a_{6}$
---|---|---|---|---|---
$a_{2}$ | $a_{4}$ | $a_{3}$ | $a_{1}$ | $a_{6}$ | $a_{5}$
$a_{3}$ | $a_{5}$ | $a_{4}$ | $a_{1}$ | $a_{2}$ | $a_{6}$
$a_{4}$ | $a_{1}$ | $a_{5}$ | $a_{6}$ | $a_{2}$ | $a_{3}$
$a_{5}$ | $a_{6}$ | $a_{2}$ | $a_{4}$ | $a_{1}$ | $a_{3}$
$a_{6}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | $a_{5}$
Table 2: An unsolvable sr instance

There are many practical applications of the sr model. As the name suggests,
it can model campus housing allocation where two students either share a room
or a flat [39]. Furthermore, sr can model pairwise kidney exchange markets
[34], with centralised matching schemes existing, for example, in the US [1],
Netherlands [31], and UK [2]. sr can also model peer-to-peer networks, such as
file-sharing networks [20], and pair formation in chess tournaments [32].

First proposed by [21], the problem is, historically, a non-bipartite
extension of the Stable Marriage problem (sm), where the set of agents can be
partitioned into two sets such that every agent from one set has complete
preferences over all agents from the other set, but does not accept to be
matched with anyone from their own set. The authors showed that any sm problem
instance admits at least one stable matching, and that such a matching can be
found in linear time.

In sr, a problem instance $I$ and a matching $M$ can be represented in the
form of preference lists and a set of pairs or as a complete graph and a set
of edges, respectively. These representations are equivalent. The sr problem
is well-studied [25, 35], and [27] presented an algorithm to find a stable
matching or decide that none exists in linear time, which is referred to as
_Irving’s algorithm_. Furthermore, sr now has a wide range of algorithms and
structural results relating to special kinds of stable matchings, including
algorithms for finding stable matchings that satisfy further optimality
constraints on the structure of the matching. For example, the _profile_ is
often used in fairness measures of a matching, which is a vector $(p_{1}\dots
p_{n})$ where $p_{i}$ captures the number of agents that are matched to their
$i$th choice, and $n$ is the number of agents. However, naturally, these
optimality properties cannot be realised if the instance is unsolvable.

[42] presented some empirical evidence relating to solvability probability,
denoted $P_{n}$, which is the probability that a uniformly random sr instance
admits at least one stable matching. Their results suggest that for instances
with 100 to 2000 agents, $P_{n}$ appears to decline from around 64% down to
around 33%. [36, 38] extended the results through extensive simulations and
conjectured that with an even number of agents $n$, $P_{n}\simeq
e\sqrt{2\pi^{-1}}n^{-\frac{1}{4}}$.

Thus, it is clear that as $n$ grows large, stable matchings are unlikely to be
a good solution concept in practice as they are unlikely to exist. In the
past, many alternative solution concepts have been proposed, such as _stable
partitions_ , _maximum stable matchings_ , _almost-stable matchings_ ,
_popular matchings_ , and more, some of which leave many agents unassigned or
are NP-hard to compute.

One of the fundamental sr-related questions posed by [25] asked about the
existence of a succinct certificate for the unsolvability of an instance. The
question was answered positively by [48], who generalised the notion of a
stable matching to a new structure called a _stable partition_. A stable
partition is a cyclic permutation $\Pi$ of the agents, where every agent
prefers their successor in $\Pi$ over their predecessor in $\Pi$, and no two
agents strictly prefer each other over their predecessors (for example,
$\Pi=(a_{1}\;a_{2}\;a_{3})(a_{4}\;a_{5}\;a_{6})$ is the unique stable
partition of Example 2, indicated in dotted and unbroken circles). Tan proved
that cycles of odd length are invariant for all stable partitions of an
instance and that an instance is unsolvable if and only if any stable
partition contains a cycle of odd length. Over 20 years after their initial
publication, [35] called the work on stable partitions in the 1990s a key
landmark in the progress made on the sr problem after 1989.

Although proposed and studied as a succinct certificate for the unsolvability
of an sr instance, the notion of a stable partition was adopted as a solution
concept in itself. Remaining in the tennis analogy, a stable partition can be
interpreted as an assignment of the friends into half-hour sessions, or a
weekly-alternating schedule. The stability definition leads to a guaranteed
solution in which every friend plays either for exactly one hour with some
other friend or two half-hour sessions with two different friends, at most one
agent does not play at all, and no two friends who would like to play more
time with each other (in Example 2, agents $a_{1},a_{2},a_{3}$ would all play
half-hour matches with each other and $a_{4},a_{5},a_{6}$ would do too). Note
that for any solvable instance, any stable partition can be transformed into a
stable matching in linear time, and for unsolvable instances, some agents are
guaranteed to be in half-time partnerships.

Some have highlighted the advantages of considering truly fractional stable
matchings, whereas stable matchings are inherently integral, and stable
partitions can be interpreted as stable half-integral matchings [12]. While
stable fractional matchings might be advantageous in applications such as
time-sharing [44], it is unlikely to be a suitable solution concept for other
applications. For example, a tennis schedule for a set of friends where
everyone plays many times for varying durations, which could be very short, is
unlikely to be satisfactory.

Overall, stable partitions are an important structure and tool in the study of
sr and in the field of stable matchings. They can be used to show properties
about instances, algorithms, and structures and pose an efficient solution
concept to solvable and unsolvable instances at the intersection of stable
integral and fractional matchings. Surprisingly, though, stable partitions
themselves have not received nearly as much attention as stable matchings.
This motivates our study of stable partition structures in more detail,
specifically the investigation of different cycle types, the algorithmics of
stable cycle and partition enumeration, how profile-optimality in the case of
stable matching and maximum utility in the case of stable fractional matching
adapts to stable partitions, and which of these variants are efficiently
solvable or approximable.

###  1.2 Our Contributions

In this paper, we prove new structural results for stable partitions, allowing
us to construct algorithms to enumerate stable partitions and to compute or
approximate various types of optimal stable partitions.

Specifically, we characterise the structure of _reduced stable partitions_
(i.e., stable partitions with no cycles of even length larger than 2) in a
given sr instance $I$ by proving a bijective correspondence between the set of
reduced stable partitions and the set of stable matchings of a solvable sub-
instance of $I$. With this, we show how the set of all reduced stable
partitions can be enumerated efficiently.

We build on these results by considering all stable partitions, not
necessarily reduced. We show that any non-reduced stable partition can be
constructed from two reduced stable partitions and leverage our previous
result to enumerate all stable partitions. However, a deeper structural
investigation yields the non-trivial result that any predecessor-successor
pair can be part of at most one cycle of length larger than 2. This proves
that the union of all stable partitions of any instance with $n$ agents
contains at most $O(n^{2})$ cycles, and we show how these can be enumerated in
$O(n^{4})$ time. We then use these structural insights to improve on the
previous enumeration algorithm for all stable partitions, denoted $P(I)$, and
present a more efficient algorithm that runs in $O(|P(I)|n^{3}+n^{4})$ time.

Finally, we adapt six natural fairness measures and optimality criteria from
stable matchings to stable partitions. We prove that finding a stable
partition that minimises the maximum predecessor rank (called _minimum-regret
stable partition_) is the only tractable problem variant of these, while the
remaining five are NP-hard to compute. Furthermore, although two of the NP-
hard optimisation problem variants are polynomial-time approximable within a
factor of 2, one of them is not approximable within any constant factor.

All of these results are consistent with those previously known about stable
matchings, strengthening the tight correspondence between stable matchings and
stable partitions observed from the beginning of this work. Overall, our
results shed more light on the complexity-theoretic and structural properties
of stable partitions.

###  1.3 Related Work

#### Stable Matchings

[26, 23] published an extensive collection of early structural results,
leading to a book discussing the structure and algorithms of the sm and sr
problems by [25]. They proved, for example, that the stable matchings of a
given instance form a semi-lattice structure, that the same set of agents are
unassigned in every stable matching of the same instance and that, of a given
sr instance $I$ with $n$ agents, all stable pairs (union of all pairs part of
some stable matching) and all stable matchings, denoted $S(I)$, can be found
in $O(n^{3}\log n)$ and $O(|S(I)|n^{2}+n^{3}\log n)$ time, respectively.
Later, [18] used a 2-sat reduction to obtain improved time complexities for
the last two problems, solving them in $O(n^{3})$ and $O(|S(I)|n+n^{2})$ time,
respectively.

With regards to the complexity of profile-optimal stable matching problems,
_minimum-regret_ is one of few efficiently solvable ones, with a linear-time
algorithm presented by [25]. On the other hand, [17] proved that finding an
egalitarian (minimum sum of ranks of agents assigned) stable matching for sr
is NP-hard. Later, [18], and [24] gave 2-approximation algorithms for the
problem using a reduction to 2-sat. The hardness result is refined by [15] who
established NP-hardness even when preference lists are of length at most 3. On
the other hand, [11] showed that the problem is fixed-parameter tractable with
respect to egalitarian cost. [13] showed that for an instance with regret $r$,
the problems of finding _rank-maximal_ (lexicographically maximal profile),
_generous_ (lexicographically minimal inverse profile), _first-choice maximal_
(maximum number of first choices achieved), and _regret-minimal_ (minimum
number of agents assigned to $r$) stable matchings, if they exist, are all NP-
hard. [47] extended these results to short preference lists and presented some
approximability results.

As a natural way to deal with unsolvable instances, [3] introduced the problem
of finding _almost-stable_ matchings, which are matchings with a minimum
number of blocking pairs. They proved that the problem is NP-hard and not
approximable within $n^{\frac{1}{2}-\varepsilon}$ for any $\varepsilon>0$,
unless P$=$NP. Later, [7] extended the study of this problem to bounded
preference lists, showing that the problem remains inapproximable within any
constant factor even for preference lists of lengths at most 3.

#### Stable Partitions

In his original paper, [48] provided a linear-time algorithm similar to
Irving’s algorithm to compute a stable partition, referred to as _Tan’s
algorithm_ , and showed that every sr instance admits at least one stable
partition. [50] considered the online version of the problem of finding a
stable partition, in which a new agent arrives and the preference lists are
updated, and constructed an exact algorithm known as the _Tan-Hsueh algorithm_
that runs in linear time.

[40] derived a range of probabilistic results about the original algorithm by
Tan. Specifically, he showed, for example, that every stable partition is
likely to be almost a stable matching, in the sense that at most
$O(\sqrt{(n\log n)})$ members are likely to be involved in the cycles of odd
length three or more. He also showed that the expected number of stable
partitions is $O(\sqrt{n})$. This work was extended by [41], who showed that
the expected total number of reduced stable partitions grows proportionally to
$O(n^{\frac{1}{4}})$. Pittel also showed that the expected total number of
cycles of odd length grows proportionally to $O(n^{\frac{1}{4}}\log n)$ and
that, with high probability, the total length of all its cycles of odd length,
denoted $n_{odd}$, is below $\sqrt{n}\log n$.

With regards to experimental results related to components of stable
partitions, [36] analysed $n_{odd}$ for unsolvable instances sampled from
complete uniform random graphs and conjectured that the expected total number
is $\Theta(\sqrt{n(\log n)^{-1}})$. Furthermore, [37] presented the exact
probabilities for specific component types for small instances.

Stable partitions are also used to show various other results with regards to
the sr problem. For example, [5] studied economic aspects of the algorithm by
[50]. A core result is that in the algorithm, the agent that arrives last gets
their best-possible partner in any stable matching. Similarly, in their study
of almost-stable matchings, [3] used stable partitions to prove bounds on the
number of blocking pairs. Finally, stable partitions are also used in exact
and approximation algorithms for finding almost-stable matchings by [7].

#### Similar Problems and Extensions

Over time, many variations of sr have been studied, such as srt (where ties
are allowed in the preferences) [28, 43, 46, 33], sri (where incomplete
preferences are permitted) [15], or both, denoted srti [28].

Another extension of sr is the problem of finding stable fractional matchings.
One advantage of fractional matchings is the natural integration of cardinal
utilities rather than purely ordinal preferences, as highlighted by [4]. [9]
were the first to study a combined model of stable fractional matchings with
cardinal preferences in the sm context from a computational complexity point
of view. The authors established the NP-hardness of computing an optimal
solution in terms of a stable fractional matching with highest overall utility
achieved. As a special case of sr, these hardness results carry over to the
sri problem. Recently, [12] expanded on these results and completed the
complexity classification of optimising for overall utility or the number of
fully matched agents in both the sm and sr settings with and without ties.
They established that a stable fractional matching always exists, but that
both optimisation problems are NP-hard when considering cardinal utilities.
Furthermore, they showed that stable partitions are a 2-approximation of the
optimisation problem of finding stable fractional matchings with the maximum
number of agents fully matched in the presence of ties.

Building on theory for bipartite problem restrictions by [14, 30], [19] showed
how, under some assumptions, the strict linearly-ordered preference lists can
be replaced with choice functions, which are a generalisation of ordinal
rankings and can capture more complex preference behaviours, while keeping the
problem polynomial-time solvable. [29] introduced a many-to-many extension of
sr called Stable Fixtures and ave a linear-time algorithm to find a stable
matching or report that none exists. This was later extended by [6] to include
payments. A similar extension many-to-many extensions where parallel edges are
allowed, i.e., agents can be matched to each other multiple times, was studied
by [10] and extended by [8].

As an alternative to stability, a matching $M$ is _popular_ if there does not
exist some matching $M^{\prime}$ which is preferred by more agents than those
that prefer $M$. [22, 16] simultaneously proved that the problem of deciding
whether a matching is popular is NP-complete. [45] extended this result to
maximize the utility of a matching that is popular but admits only a few
blocking pairs, proving that finding a popular matching with at most one
blocking pair is already NP-hard.

###  1.4 Structure of the Paper

In Section 2, we present a mixture of existing and new formal definitions and
known results relevant to this paper. In Section 3, we characterise and
exploit the structure of reduced stable partitions, longer cycles, and all
stable partitions. Finally, in Section 4, we adapt common profile-based
optimality criteria from stable matchings to stable partitions and investigate
the complexity and approximability of these problems. We finish with a
discussion of the results and some related open problems in Section 5.

##  2 Formal Definitions and Preliminary Results

In Section 2.1, we will outline some crucial concepts and their notation with
regards to stable matchings, stable partitions, and their different
components. Following, Section 2.2 will introduce some natural fairness and
optimality measures previously studied in the literature for stable matchings
and adapt them for our study of stable partitions.

###  2.1 Stable Matchings, Partitions, and Cycles

######  Definition 2.1 (sr Instance).

Let $I=(A,\succ)$ be an sr _instance_ where $A=\\{a_{1},a_{2},\dots,a_{n}\\}$,
also denoted $A(I)$, is a set of $n\in 2\mathbb{N}$ agents and every agent
$a_{i}\in A$ has a strict preference ranking or _preference relation_
$\succ_{i}$ over all other agents $a_{j}\in A\setminus\\{a_{i}\\}$.

######  Definition 2.2 (Stable Matchings).

Let $I=(A,\succ)$ be an sr instance. $M$ is a _matching_ of $I$ if it is an
assignment of some agents in $A$ into pairs such that no agent is contained in
more than one pair of $M$. A _blocking pair_ of a matching $M$ is a pair of
two agents $a_{i},a_{j}\in A$ such that either $a_{j}$ is unassigned in $M$ or
$a_{i}\succ_{j}M(a_{j})$, and either $a_{i}$ is unassigned or
$a_{j}\succ_{i}M(a_{i})$, where $M(a_{i})$ is the partner of $a_{i}$ in $M$.
If $M$ does not admit any blocking pair, then it is called _stable_.

######  Definition 2.3 (Solvability and Sub-Instances).

Let $I=(A,\succ)$ be an sr instance. $I$ is _solvable_ if it admits at least
one stable matching, otherwise it is _unsolvable_.
$I^{\prime}=(A^{\prime},\succ^{\prime})$ is a _sub-instance_ or a
_restriction_ of $I$ if $A^{\prime}\subseteq A$ and
$a_{i}\succ^{\prime}_{k}a_{j}$ for all agents $a_{i},a_{j},a_{k}\in
A^{\prime}$ where $a_{i}\succ_{k}a_{j}$.

Note that in this work, we assume an even number of agents. However, it has
been shown [25] that most concepts and results transfer over to the case where
the number of agents is odd and we accept an unmatched (but non-blocking)
agent.

As previously mentioned, stable partitions $\Pi$ are permutations on the
subset of agents. Therefore, they can be written in cyclic notation where
every agent is part of exactly one cycle. We assume that any agent ranks
themselves last, thereby allowing fixed points (unmatched agents) in the
partition. A formal definition follows.

######  Definition 2.4 (Stable Partition).

Let $I=(A,\succ)$ be an sr instance. Then a partition $\Pi$ is _stable_ if it
is a permutation of $A$ and

  1. (T1)

$\forall a_{i}\in A$ we have $\Pi(a_{i})\succeq_{i}\Pi^{-1}(a_{i})$, and

  2. (T2)

$\nexists.a_{i},a_{j}\in A,\;a_{i}\neq a_{j},$ such that
$a_{j}\succ_{i}\Pi^{-1}(a_{i})$ and $a_{i}\succ_{j}\Pi^{-1}(a_{j})$,

where $\Pi(a_{i})\succeq_{i}\Pi^{-1}(a_{i})$ means that either $a_{i}$’s
successor in $\Pi$ is equal to its predecessor, or the successor has a better
rank than the predecessor in the preference list of $a_{i}$.

In the study of stable partitions, it is important to differentiate between
different kinds of cycles that may or may not be part of a stable partition.

######  Definition 2.5 (Cycles).

Let $I$ be an sr instance and let $C=(a_{i_{1}}\;a_{i_{2}}\;\dots\;a_{i_{k}})$
be an ordered collection of agents in $I$. Then $C$ is a _cycle_ and we can
_apply_ cycle $C$ to some agent $a_{i_{j}}\in C$ to get its successor in $C$,
denoted by $C(a_{i_{j}})$. Similarly, we can apply the inverse
$C^{-1}=(a_{i_{1}}\;a_{i_{k}}\;\dots\;a_{i_{2}})$ to $a_{i_{j}}$ to get its
predecessor in $C$, denoted by $C^{-1}(a_{i_{j}})$. The same holds for sets of
disjoint cycles.

These cycle definitions can be applied to stable partitions directly.

######  Definition 2.6 (Stable Cycles).

Let $I$ be an sr instance and let $C$ be a cycle. If there exists some stable
partition $\Pi$ of $I$ such that $C\in\Pi$, then $C$ is a _stable cycle_ of
$I$. A stable cycle of odd length is called an _odd cycle_ , of length 2 a
_transposition_ , and of even length larger than 2 an _even cycle_ of $I$.
Clearly, for every stable partition $\Pi$ of $I$,
$\Pi=\mathcal{T}\cup\mathcal{E}\cup\mathcal{O}_{I}$, where $\cup$ refers to
concatenation of the disjoint cycles, $\mathcal{T}$ denote the transpositions,
$\mathcal{E}$ the even cycles, and $\mathcal{O}_{I}$ the odd cycles of $\Pi$.
Let $A(C)$ denote the set of agents contained in a single cycle or a
collection of cycles $C$. Unless specified otherwise, let
$n_{1}=|A(\mathcal{T}\cup\mathcal{E})|$ and $n_{2}=|A(\mathcal{O}_{I})|$.

######  Definition 2.7 (Reduced Stable Partition).

A cycle is called _reduced_ if its length is either 2 or odd, otherwise it is
called _non-reduced_. Similarly, a stable partition $\Pi$ is reduced if it
consists only of reduced cycles, and non-reduced if not.

We will also need a definition for sub-sequences of cycles.

######  Definition 2.8 (Partial Cycles).

Let $I$ be an sr instance and let $C=(a_{i_{1}}\;a_{i_{2}}\dots
a_{i_{k}}\dots)$ be a cycle where only some agents $a_{i_{1}}\dots a_{i_{k}}$
and their position in the cycle are known. Then we call $C$ a _partial cycle_
and if there exist agents $a_{i_{k+1}}\dots a_{i_{r}}$ such that
$(a_{i_{1}}\;a_{i_{2}}\dots a_{i_{k}}\;a_{i_{k+1}}\dots a_{i_{r}})$ is a
stable cycles, then $C$ is a _partial stable cycle_ and the sequence of agents
$a_{i_{k+1}}\dots a_{i_{r}}$ is a _completion_ of $C$.

Now we can introduce the notion of blocking agents and pairs for stable
partitions. Note that the definition is very close to that of blocking pairs
of stable matchings, and it should be clear from the context which definition
applies.

######  Definition 2.9 (Blocking Pairs and Agents).

Let $I=(A,\succ)$ be an sr instance and let $\Pi$ be a partition of $A$. Then
an agent $a_{i}\in A$ _blocks_ $\Pi$ (is a _blocking agent_) if
$\Pi^{-1}(a_{i})\succ_{i}\Pi(a_{i})$. Two agents $a_{i},a_{j}$ _block_ (form a
_blocking pair) of_ $\Pi$ if $a_{j}\succ_{i}\Pi^{-1}(a_{i})$ and
$a_{i}\succ_{j}\Pi^{-1}(a_{j})$. In the second case, we can also say that
(wlog) $a_{i}$ _blocks_ $\Pi$ _with_ $a_{j}$.

The following has been shown and will also be assumed throughout this work.

######  Theorem 2.10 ([48, 49]).

The following properties hold for any sr instance $I$.

  * •

Any two stable partitions $\Pi_{a},\Pi_{b}$ of $I$ contain exactly the same
odd cycles, not only having the same agents involved but also in the same
order within the cycles.

  * •

$I$ admits a complete stable matching if and only if no stable partition of
$I$ contains an odd cycle.

  * •

If $I$ has a stable partition containing an odd cycle, then there does not
exist a complete stable matching.

Note that if an sr instance $I$ admits a stable matching
$M=\\{\\{a_{i_{1}},a_{i_{2}}\\},\dots,\\{a_{i_{2k-1}},a_{i_{2k}}\\}\\}$
consisting of $k$ pairs, then it can be denoted interchangeably with its
induced collection of transpositions $\Pi=(a_{i_{1}}$
$a_{i_{2}})\dots(a_{i_{2k-1}}$ $a_{i_{2k}})$, which is a stable partition of
$I$.

###  2.2 Optimality and Fairness of Matchings and Partitions

As previously noted, there are different measures of fairness and optimality
for stable matchings considered in the literature. The main measure is the
_profile_ $p(M)$ of a matching $M$, a vector $(p_{1}\dots p_{n-1})$, where
$p_{i}$ counts the number of agents assigned to their $i$th choice in $M$. We
define a similar measure for stable partitions, accounting for all half-
assignments in the associated half-matching.

######  Definition 2.11.

Let $I$ be an sr instance with $n$ agents and $\Pi$ a stable partition of $I$.
Then the _successor profile_ , denoted
$p^{s}(\Pi)=(p_{1}^{s}\;\dots\;p_{n}^{s})$, captures the number of agents
$p_{i}^{s}$ whose successor in $\Pi$ has rank $i$ in their preference list.
Analogously, let $p^{p}(\Pi)$ denote the _predecessor profile_ of $\Pi$.
Finally, let $p(\Pi)=(p_{1}\;\dots\;p_{n})$ denote the combined _profile_ of
$\Pi$, where $p_{i}=p_{i}^{s}+p_{i}^{p}$. Similarly, for a stable cycle $C$,
let $p^{s}(C),p^{p}(C),$ and $p(C)$ denote the profiles containing the number
and positions of predecessors, successors, or both achieved in $C$.

For some stable partition $\Pi$ of $n$ agents, the sum of all entries in
$p^{s}(\Pi)$ and $p^{p}(\Pi)$ add up to $n$ each, such that those in $p(\Pi)$
add up to $2n$, one for each half-assignment and counting a full assignment as
two half-assignments.

One simple measure of optimality for a stable matching $M$ of a solvable
instance $I$ is its _regret_ , which is the rank of the worst assigned agent
in $M$. Similarly, the regret of $I$ is the minimum regret over all its stable
matchings. We will consider the same for stable partitions.

######  Definition 2.12.

Let $\Pi$ be a stable partition and let $p(\Pi)$ be its profile. Then the
_regret_ of $\Pi$, denoted $r(\Pi)$, is the rank of the worst-ranked agent
assigned in $\Pi$, which is the index of the last positive entry in $p(\Pi)$.
Similarly, for $C$ some cycle of agents, let $r(C)$ be the rank of the worst-
ranked agent assigned in $C$.

Finally, another important optimality measure of a stable matching $M$ is its
_cost_ , which is a weighted sum of its profile. Again, the same can be
defined for stable partitions.

######  Definition 2.13.

Let $\Pi$ be a stable partition and let $p(\Pi)$ be its profile. Then the
_cost_ of $\Pi$, denoted $c(\Pi)$, is the sum of ranks achieved in $\Pi$,
averaged over the predecessor and successor assignments. Specifically, we
define $c(\Pi)=\frac{1}{2}\sum_{1\leq i<n}p_{i}(\Pi)*i$.

We include the factor of half for consistency with stable matchings, as the
profile entries sum up to $2n$. This constant factor does not affect our
optimisation problems. For the same reason, we also do not sum up to $n$, as
an agent assigned to someone of rank $n$ is assigned to itself, which can
never happen in stable matchings. As in any stable partition, there can be at
most one self-assigned agent, and this is an odd cycle and thus invariant,
this again does not affect our optimisation problems.

Some associated problem variants for stable matchings are the following.

######  Definition 2.14.

Let $I$ be a solvable sr instance. A _minimum-regret_ stable matching is a
stable matching of $I$ with regret $r$ such that no other stable matching has
lower regret. A _regret-minimal_ stable matching is a minimum-regret stable
matching such that no other minimum-regret stable matching satisfies fewer
choices of rank $r$. A _first-choice maximal_ stable matching is a stable
matching of $I$ such that no other stable matching satisfies more first
choices. Finally, a (egalitarian) _cost-optimal_ stable matching of $I$ is a
stable matching such that no other stable matching has a lower cost.

With our definitions of profile, regret, and cost for stable partitions, we
can define analogous optimality measures for stable partitions (and thus
stable half-matchings). For some, we need an order on profiles as defined
below.

######  Definition 2.15.

Let $p=(p_{1}\dots p_{n}),p^{\prime}=(p_{1}^{\prime}\dots p_{n}^{\prime})$ be
two profile vectors. Then $p=p^{\prime}$ if $p_{i}=p_{i}^{\prime}$ for all
$1\leq i\leq n$. If $p\neq p^{\prime}$, let $k$ be the first position in which
they differ. We define $p\succ p^{\prime}$ if $p_{k}>p_{k}^{\prime}$.
Furthermore, we define $p\succeq p^{\prime}$ if either $p\succ p^{\prime}$ or
$p=p^{\prime}$. Finally, we will call $p^{rev}=(p_{n}\dots p_{1})$ the
_reverse profile_ of $p$.

The optimality criteria are defined as follows.

######  Definition 2.16.

Let $\Pi$ be a stable partition of some sr instance $I$ with $n$ agents and
regret $r$ and let $p(\Pi)$ be its profile. Then $\Pi$ is a

  * •

_minimum-regret_ stable partition of $I$ if, for all stable partitions
$\Pi^{\prime}$ of $I$, we have $r(\Pi)\leq r(\Pi^{\prime})$,

  * •

_first-choice maximal_ stable partition of $I$ if, for all stable partitions
$\Pi^{\prime}$ of $I$ with profile $p(\Pi^{\prime})$, we have $p_{1}(\Pi)\geq
p_{1}(\Pi^{\prime})$,

  * •

_rank-maximal_ stable partition of $I$ if, for all stable partitions
$\Pi^{\prime}$ of $I$ with profile $p(\Pi^{\prime})$, we have $p(\Pi)\succeq
p(\Pi^{\prime})$,

  * •

_regret-minimal_ stable partition of $I$ if $\Pi$ is a minimum-regret stable
partition and, for all minimum regret stable partitions $\Pi^{\prime}$ of $I$
with profile $p(\Pi^{\prime})$, we have $p_{r}(\Pi)\leq p_{r}(\Pi^{\prime})$,

  * •

_generous_ stable partition of $I$ if, for all stable partitions
$\Pi^{\prime}$ of $I$ with profile $p(\Pi^{\prime})$, we have
$p^{rev}(\Pi^{\prime})\succeq p^{rev}(\Pi)$, and

  * •

_egalitarian_ stable partition of $I$ if, for all stable partitions
$\Pi^{\prime}$ of $I$, we have $c(\Pi)\leq c(\Pi^{\prime})$.

##  3 Structure of Stable Cycles, Transpositions, and Partitions

First, we will formalise and characterise the structure of reduced stable
partitions in Section 3.1. Then, naturally, we will extend the study to all
stable partitions. This requires the study of stable cycles. After showing
various results about the structure of even cycles in Section 3.2, we focus on
algorithmic questions related to the enumeration of all reduced and non-
reduced stable cycles in Section 3.3, finishing this section with an
enumeration algorithm for all stable partitions in Section 3.4 which ties
together most of our results.

###  3.1 Structure of Reduced Stable Partitions

Let $I=(A,\succ)$ be an instance of sr and let $\Pi_{i}$ be any reduced stable
partition of $I$. We know that its odd cycles $\mathcal{O}_{I}$ are invariant
under all stable partitions of $I$, while the transpositions might not be. Let
$I_{E}=(A^{\prime},\succ^{\prime})$, where $A^{\prime}=A\setminus
A(\mathcal{O}_{I})$ and $\succ^{\prime}$ is the restriction of $\succ$ to the
agents in $A^{\prime}$, be the instance $I$ restricted to agents in
transpositions.

######  Lemma 3.1.

Let $\Pi_{i}$ be any reduced stable partition of an sr instance $I$. Then
$\Pi_{i}$ is the union $M_{i}\mathcal{O}_{I}$ of its odd cycles
$\mathcal{O}_{I}$ and a perfect stable matching $M_{i}$ of the sub-instance
$I_{E}$ of $I$ constructed above as a cyclic permutation of transpositions.

###### Proof.

By definition of reduced stable partitions, $\Pi_{i}$ is the union
$M_{i}\mathcal{O}_{I}$ of transpositions $M_{i}$ and its invariant odd cycles
$\mathcal{O}_{I}$. Note first that if $M_{i}=\varnothing$, then
$A(\mathcal{O}_{I})=A$, so $A^{\prime}=\varnothing$ and $I_{E}=\varnothing$.
Therefore, $M_{i}$ is trivially perfect and stable in $I_{E}$.

Otherwise, suppose that $M_{i}\neq\varnothing$ with $|A^{\prime}|\in
2\mathbb{N}$, where $M_{i}$ is not a stable matching in $I_{E}$. Note first
that $M_{i}$ is a matching in $I_{E}$ as the transpositions are disjoint due
to $\Pi_{i}$ being a partition, and only include agents in $A^{\prime}$ by
construction. Then either some partners $a_{r},a_{s}$ in $M_{i}$ would not
find each other acceptable anymore in $\succ^{\prime}$, or there would be at
least one blocking pair consisting of two agents $a_{r},a_{s}$ in $A^{\prime}$
that prefer each other over their partners in $M_{i}$ in the preference
relation $\succ^{\prime}$.

Consider first the case where some $\\{a_{r},a_{s}\\}\in M_{i}$ would not find
each other acceptable anymore in $\succ^{\prime}$. This cannot happen, as
$A(M_{i})\cap A(\mathcal{O}_{I})=\varnothing$, so the pair would not be
removed in the construction of $\succ^{\prime}$, where $\succ^{\prime}$ is
restricted to agents not in $\mathcal{O}_{I}$.

Furthermore, $M_{i}$ cannot admit a blocking pair in $I_{E}$. Suppose that
$\\{a_{r},a_{s}\\}\subseteq A^{\prime}$ was a blocking pair in $I_{E}$, then
$a_{r}\succ^{\prime}_{s}M_{i}(a_{s})$ and
$a_{s}\succ^{\prime}_{r}M_{i}(a_{r})$. However, because all agents in
$A^{\prime}$ are contained in transpositions in $\Pi_{i}$, we know that
$M_{i}(a_{r})=\Pi_{i}(a_{r})=\Pi_{i}^{-1}(a_{r})$ and
$M_{i}(a_{s})=\Pi_{i}(a_{s})=\Pi_{i}^{-1}(a_{s})$. Because $\succ^{\prime}$ is
contained in $\succ$, this would let us conclude that
$a_{r}\succ_{s}\Pi_{i}^{-1}(a_{s})$ and $a_{s}\succ_{r}\Pi_{i}^{-1}(a_{r})$, a
contradiction of stability condition T2 of $\Pi_{i}$.

Finally, every agent has complete preference lists in $I_{E}$, so if $M_{i}$
is stable, it must be a perfect matching. Otherwise, there would be two
unmatched agents in $A^{\prime}$ that would rather be matched to each other
than to be unmatched, contradicting the stability of $M_{i}$. ∎

On the other hand, we are not guaranteed that there is a bijection between the
set $P(I)$ of all reduced stable partitions of $I$ and the set $S(I_{E})$ of
all stable matchings of $I_{E}$. Consider the instance $I$ in Example 3. It
admits the reduced stable partition $\Pi_{0}=(a_{1}$ $a_{2})(a_{3}$
$a_{4})(a_{5}$ $a_{6}$ $a_{7})(a_{8}$ $a_{9}$ $a_{10})$. Now clearly
$\mathcal{O}_{I}=(a_{5}$ $a_{6}$ $a_{7})(a_{8}$ $a_{9}$ $a_{10})$ and
$I_{E}=(\\{a_{1},a_{2},a_{3},a_{4}\\},\succ^{\prime})$. However, $I_{E}$
admits the stable matchings $S(I_{E})=\\{M_{1},M_{2}\\}$ where
$M_{1}=\\{\\{a_{1},a_{2}\\},\\{a_{3},a_{4}\\}\\}$ and
$M_{2}=\\{\\{a_{1},a_{3}\\},\\{a_{2},a_{4}\\}\\}$. While
$M_{1}\mathcal{O}_{I}$ is the original stable partition $\Pi_{0}$,
$M_{2}\mathcal{O}_{I}$ does not correspond to a stable partition of $I$ as
agents $\\{a_{1},a_{5}\\}$ would violate condition T2. Specifically,
$a_{5}\succ_{1}a_{3}$ and $a_{1}\succ_{5}a_{7}$. In Example 3, this is
indicated by $M_{2}$ in dotted circles and the violating pair in unbroken
circles.

$a_{1}$ | $\mathbf{a_{2}}$ | $a_{5}$ | $a_{3}$ | …
---|---|---|---|---
$a_{2}$ | $a_{4}$ | $\mathbf{a_{1}}$ | … |
$a_{3}$ | $a_{1}$ | $\mathbf{a_{4}}$ | … |
$a_{4}$ | $\mathbf{a_{3}}$ | $a_{2}$ | … |
$a_{5}$ | $a_{1}$ | $\mathbf{a_{6}}$ | $a_{7}$ | …
$a_{6}$ | $\mathbf{a_{7}}$ | $a_{5}$ | … |
$a_{7}$ | $\mathbf{a_{5}}$ | $a_{6}$ | … |
$a_{8}$ | $\mathbf{a_{9}}$ | $a_{10}$ | … |
$a_{9}$ | $\mathbf{a_{10}}$ | $a_{8}$ | … |
$a_{10}$ | $\mathbf{a_{8}}$ | $a_{9}$ | … |
Table 3: sr instance with stable $\Pi_{0}$ as successors and predecessors

To deal with the case where enumerating the stable matchings of $I_{E}$ is not
enough, we can reduce $I_{E}$ further. Specifically, all pairs of agents
$\\{a_{i},a_{j}\\}\subseteq A^{\prime}$ need to be deleted (made mutually
unacceptable) from the preference relation $\succ^{\prime}$ whenever there
exists an agent $a_{r}\in A(\mathcal{O}_{I})$ such that
$a_{i}\succ_{r}\mathcal{O}_{I}^{-1}(a_{r})$ and $a_{r}\succ_{i}a_{j}$. This is
equivalent to truncating the preference list of $a_{i}$ at the first agent
$a_{s}\in A^{\prime}$ such that $a_{s}\succ_{i}a_{r}$, for the best-ranked
such $a_{r}\in A(\mathcal{O}_{I})$ of $a_{i}$, and removing $a_{i}$ from the
preference list of every agent in $A^{\prime}$ that is less preferred by
$a_{i}$. The deletion operations do not reduce the set of agents, just the
preference relation, so we let the resulting sub-instance of $I_{E}$ be
denoted by $I_{T}=(A^{\prime},\succ^{\prime\prime})$ (Algorithm 1 captures all
steps to compute $I_{T}$ from $I$). We assume that preference comparison and
partner lookup can be done in constant time, such that the procedure takes at
most linear time overall.

1:$I$ : an sr instance

2:$I_{T}$ : a solvable sub-instance of $I$

3:$I_{T}\leftarrow I$

4:$M_{0}\mathcal{O}_{I}\leftarrow$ ReducedStablePartition$(I)$

5:for $a_{r}$ in $A(\mathcal{O_{I}})$ do

6: remove $a_{r}$ from $I_{T}$

7:end for

8:for $a_{i}$ in $A(M_{0})$ do

9: delete $\leftarrow$ False

10: for $a_{j}$ in preference list of $a_{i}$ in $I$ (in order or preference)
do

11: if $a_{j}$ in $A(\mathcal{O}_{I})$ and
$a_{i}\succ_{j}\mathcal{O}^{-1}(a_{j})$ then

12: delete $\leftarrow$ True

13: end if

14: if delete and $\\{a_{i},a_{j}\\}$ acceptable in $I_{T}$ then

15: make $\\{a_{i},a_{j}\\}$ mutually unacceptable in $I_{T}$

16: end if

17: end for

18:end for

19:return $I_{T}$

Algorithm 1 ConstructI${}_{T}(I)$, constructs $I_{T}$ from sr instance $I$

Although these deletions might destroy some stable matchings admitted by
$I_{E}$, we must ensure that $I_{T}$ still admits at least one.

######  Lemma 3.2.

Let $\Pi_{i}=M_{i}\mathcal{O}_{I}$ be any reduced stable partition of an sr
instance $I$ and let $I_{T}$ be its sub-instance as constructed above. Then
$M_{i}$ is a perfect stable matching of $I_{T}$.

###### Proof.

By Lemma 3.1, $M_{i}$ is a perfect stable matching of $I_{E}$. As
$\succ^{\prime\prime}$ is contained in $\succ^{\prime}$, $M_{i}$ cannot admit
more blocking pairs in $I_{T}$ than in $I_{E}$. Thus, if $M_{i}$ were not a
stable matching in $I_{T}$, then this would have to be because $M_{i}$ is not
a valid matching. This would only occur if two agents in $M_{i}$ were made
mutually unacceptable in the construction of $I_{T}$ from $I_{E}$.

Suppose that $\\{a_{i},a_{j}\\}\in M_{i}$ find each other acceptable in
$\succ^{\prime}$, but do not find each other acceptable anymore in
$\succ^{\prime\prime}$. Then their respective preference list entries would
have been removed in the deletion operations. Without loss of generality
(wlog), suppose this was because there exists some agent
$a_{r}\in\mathcal{O}_{I}$ such that
$a_{i}\succ_{r}\mathcal{O}_{I}^{-1}(a_{r})$ and $a_{r}\succ_{i}a_{j}$. Then
$\\{a_{i},a_{j}\\}$ could not belong to $M_{i}$ as $a_{i}$ and $a_{r}$ would
contradict stability condition T2 with respect to $\Pi_{i}$. Therefore,
matched agents in $M_{i}$ still consider each other mutually acceptable in
$\succ^{\prime\prime}$.

Thus, $M_{i}$ is also a perfect stable matching of $I_{T}$. ∎

We can now show the correspondence between the stable matchings of $I_{T}$ and
the reduced stable partitions of $I$.

######  Theorem 3.3.

$M_{i}$ is a perfect stable matching of $I_{T}$ if and only if
$M_{i}\mathcal{O}_{I}$ is a reduced stable partition of $I$, where $I_{T}$ is
constructed as above and $\mathcal{O}_{I}$ are the invariant odd cycles of
$I$.

###### Proof.

First, suppose that $M_{i}$ is a perfect stable matching of $I_{T}$. We want
to show that $M_{i}\mathcal{O}_{I}$ is a reduced stable partition of $I$.
Suppose not, then either $M_{i}\mathcal{O}_{I}$ is not a partition, not
reduced, or it violates one of the stability conditions T1 or T2.

$M_{i}\mathcal{O}_{I}$ would not be a partition of $I$ if either there was an
agent $a_{r}\in A$ such that $a_{r}\notin A(M_{i}\mathcal{O}_{I})$ or if there
was an agent $a_{r}\in A(M_{i}\mathcal{O}_{I})$ that is in multiple different
cycles. The first case cannot happen because $A=A^{\prime}\uplus
A(\mathcal{O}_{I})$ and by Lemma 3.2, $I_{T}$ admits a perfect stable
matching. All stable matchings admitted by an sr instance have the same size,
so every agent in $A^{\prime}$ is matched in $M_{i}$. Thus, every agent
$a_{r}\in A$ is either in $M_{i}$ or in $\mathcal{O}_{I}$ and so $a_{r}\in
A(M_{i}\mathcal{O}_{I})$. The second case cannot happen by construction. If
$a_{r}\in\mathcal{O}_{I}$, then by construction of $\mathcal{O}_{I}$ and
$I_{E}$, $a_{r}$ only appears once in $\mathcal{O}_{I}$ and $a_{r}\notin
A^{\prime}$, so $a_{r}\notin M_{i}$. If $a_{r}\in A^{\prime}$, then it was not
deleted during the construction of $I_{E}$ and so
$a_{r}\notin\mathcal{O}_{I}$. Because $M_{i}$ is a matching, $a_{r}$ will only
be matched to one other agent and thus appear only once in the induced
collection of transpositions. This also confirms that the partition is reduced
because all cycles are either of odd length or of length two.

Condition T1 cannot be violated by $M_{i}\mathcal{O}_{I}$ as $\mathcal{O}_{I}$
was found in such a way that T1 holds and because $M_{i}$ is a collection of
transpositions which means that for all agents $a_{r}\in A^{\prime}$,
$a_{r}$’s predecessor is also their successor.

Finally, suppose that $M_{i}\mathcal{O}_{I}$ violates T2 with a pair of agents
$a_{r},a_{s}\in A=A^{\prime}\uplus A(\mathcal{O}_{I})$, then there are three
cases. First, suppose that $a_{r},a_{s}\in A^{\prime}$. This means that the
agents are not partners in $M_{i}$ but would rather be matched to each other.
This cannot happen due to stability of $M_{i}$ in $I_{T}$. Now suppose that
$a_{r},a_{s}\in A(\mathcal{O}_{I})$. This cannot happen, as $\mathcal{O}_{I}$
was chosen in such a way that it satisfies T2. Lastly, suppose that, wlog,
$a_{r}\in A^{\prime}$ and $a_{s}\in A(\mathcal{O}_{I})$. Then
$a_{s}\succ_{r}(M_{i}\mathcal{O}_{I})^{-1}(a_{r})=M_{i}(a_{r})$ and
$a_{r}\succ_{s}(M_{i}\mathcal{O}_{I})^{-1}(a_{s})=\mathcal{O}_{I}^{-1}(a_{s})$.
However, in this case, the pair $\\{a_{r},M_{i}(a_{r})\\}$ would have been
deleted from $\succ^{\prime}$ during the construction of $I_{T}$ from $I_{E}$
and thus $\\{a_{r},M_{i}(a_{r})\\}$ could not be matched in $M_{i}$, a
contradiction.

Now for the reverse implication, suppose that $M_{i}\mathcal{O}_{I}$ is a
reduced stable partition of $I$, where $M_{i}$ is the collection of
transpositions, if any, and $\mathcal{O}_{I}$ is the collection of odd cycles.
By Lemma 3.2, $M_{i}$ is a perfect stable matching of $I_{T}$. ∎

######  Corollary 3.4.

The number of reduced stable partitions that an sr instance $I$ with $n\in
2\mathbb{N}$ agents admits is equal to the number of stable matchings that its
sub-instance $I_{T}$ with $n-|A(\mathcal{O}_{I})|$ agents admits.

With these results, we now have a procedure to enumerate all reduced stable
permutations.

######  Theorem 3.5.

We can enumerate all reduced stable partitions of an sr instance $I=(A,\succ)$
in $O(|S(I_{T})|n+n^{2})$ time, where $I_{T}$ is the sub-instance of $I$ as
constructed above, $S(I_{T})$ is the set of all stable matchings of $I_{T}$,
and $n=|A|$.

###### Proof.

The procedure is given as follows (steps 1-3 can be performed together using
Algorithm 1):

  1. 1.

Compute any reduced stable permutation $\Pi=M_{0}\mathcal{O}_{I}$ of $I$, for
example using the algorithm presented by [48].

  2. 2.

Construct the instance $I_{E}=(A^{\prime},\succ^{\prime})$ from $I$ by
restricting $A$ and $\succ$ to all agents $a_{i}\notin A(\mathcal{O}_{I})$.

  3. 3.

Construct the instance $I_{T}=(A^{\prime},\succ^{\prime\prime})$ from $I_{E}$
by removing all agent pairs $\\{a_{i},a_{j}\\}\subseteq A^{\prime}$ from
$\succ^{\prime}$ whenever there exists an agent $a_{r}\in A(\mathcal{O}_{I})$
such that $a_{i}\succ_{r}\mathcal{O}_{I}^{-1}(a_{r})$ and
$a_{r}\succ_{i}a_{j}$.

  4. 4.

Enumerate all stable matchings $S(I_{T})$ of instance $I_{T}$, for example
using the algorithm by [18].

  5. 5.

For every matching $M_{i}\in S(I_{T})$, construct and output the corresponding
reduced stable partition $M_{i}\mathcal{O}_{I}$.

Steps 1-3 can be carried out in $O(n^{2})$ steps using Algorithm 1 as a stable
partition can be found in linear time using the algorithm by [48] and
converted into a reduced stable partition in linear time by breaking down even
length cycles into transpositions. Furthermore, the first loop takes $O(n)$
time and the second one takes $O(n^{2})$ time by the number of agents,
assuming constant time lookup for preference comparisons and partners in
$\mathcal{O}_{I}$. Step 4 can be carried out in $O(|S(I_{T})|n_{1}+n_{1}^{2})$
steps using the algorithm presented in [18]. Depending on the presentation of
the output, step 5 can be carried out in $O(|S(I_{T})|n)$ steps under the
assumption that we want to print all cycles for every reduced stable
partition. As all steps can be carried out sequentially, we arrive at the
stated worst-case complexity. ∎

###  3.2 Structure of Longer Even Cycles

Reduced stable partitions are canonical in the sense that they cannot be
broken down into smaller cycles. However, while [49] shows that any stable
cycle of even length greater than two can be decomposed into a stable
collection of transpositions, it may be of theoretical interest to look at how
longer cycles can be constructed from a collection of transpositions. Naively,
we could try any combination of transpositions to construct longer even
cycles. However, this would quickly lead to a combinatorial explosion due to
the potential number of transpositions involved.

First, we look at the different ways to decompose an even cycle into
transpositions.

######  Lemma 3.6.

Any even cycle $C=(a_{i_{1}}\;a_{i_{2}}\;\dots\;a_{i_{2k}})$ of some stable
partition $\Pi$ where $k\geq 2$ can be broken into two distinct collections of
transpositions
$C_{1}=(a_{i_{1}}\;a_{i_{2}})(a_{i_{3}}\;a_{i_{4}})\dots(a_{i_{2k-1}}\;a_{i_{2k}})$
and
$C_{2}=(a_{i_{1}}\;a_{i_{2k}})(a_{i_{2}}\;a_{i_{3}})\dots(a_{i_{2k-2}}\;a_{i_{2k-1}})$
such that both partitions $\Pi_{1}=(\Pi\setminus C)\cup C_{1}$ and
$\Pi_{2}=(\Pi\setminus C)\cup C_{2}$ are stable.

###### Proof.

By definition of even cycles, we know that
$C=(a_{i_{1}}\;a_{i_{2}}\;\dots\;a_{i_{2k}})$ is of length $2k\geq 4$. Suppose
that $\Pi_{1}$ or $\Pi_{2}$ are not stable. Then either condition T1 or T2
must be violated. However, if $\Pi$ satisfies T1, then both $\Pi_{1}$ and
$\Pi_{2}$ must satisfy T1 because the repartitioned agents are now in
transpositions, such that their predecessors equal their successors, trivially
satisfying the condition. Thus, suppose (wlog) that although $\Pi$ satisfies
T2, $\Pi_{1}$ does not. Then there exist agents $a_{i_{p}}$, $a_{i_{q}}\in C$
such that we have $a_{i_{p}}\neq a_{i_{q}}$,
$a_{i_{q}}\succ_{i_{p}}\Pi_{1}^{-1}(a_{i_{p}})=C_{1}(a_{i_{p}})$, and
$a_{i_{p}}\succ_{i_{q}}\Pi_{1}^{-1}(a_{i_{q}})=C_{1}(a_{i_{q}})$. However, we
know that for all agents $a_{i_{r}}\in C$, we have
$C_{1}(a_{i_{r}})\succeq_{i_{r}}C^{-1}(a_{i_{r}})=\Pi^{-1}(a_{i_{r}})$,
contradicting stability of $C$. Thus, both $\Pi_{1}$ and $\Pi_{2}$ are stable
partitions satisfying T1 and T2. ∎

However, there might be more ways to rearrange the agents of an even cycle
into a stable collection of disjoint transpositions. Consider the instance $I$
shown in Example 4 which admits the stable partition (indicated in the figure
with successors in bold and predecessors underlined)
$\Pi=(a_{1}\;a_{2}\;a_{3}\;a_{4}\;a_{5}\;a_{6})$. $I$ also admits the reduced
stable partitions $\Pi_{1}=(a_{1}\;a_{2})(a_{3}\;a_{4})(a_{5}\;a_{6})$,
$\Pi_{2}=(a_{1}\;a_{6})(a_{2}\;a_{3})(a_{4}\;a_{5})$, and
$\Pi_{3}=(a_{1}\;a_{4})(a_{2}\;a_{5})(a_{3}\;a_{6})$, corresponding to three
stable matchings of $I$, where $\Pi_{3}$ is indicated in the figure through
circles.

$a_{1}$ | $a_{4}$ | $\mathbf{a_{2}}$ | $a_{6}$ | …
---|---|---|---|---
$a_{2}$ | $\mathbf{a_{3}}$ | $a_{1}$ | $a_{5}$ | …
$a_{3}$ | $a_{6}$ | $\mathbf{a_{4}}$ | $a_{2}$ | …
$a_{4}$ | $\mathbf{a_{5}}$ | $a_{3}$ | $a_{1}$ | …
$a_{5}$ | $a_{2}$ | $\mathbf{a_{6}}$ | $a_{4}$ | …
$a_{6}$ | $\mathbf{a_{1}}$ | $a_{5}$ | $a_{3}$ | …
Table 4: sr instance with at least five stable partitions

While $\Pi_{1}$ and $\Pi_{2}$ can be derived from $\Pi$ by Lemma 3.6,
$\Pi_{3}$ is different in the way that it does not preserve the structure of
$\Pi$. Note, though, that $I$ also admits the stable partition
$\Pi_{4}=(a_{1}\;a_{4}\;a_{3}\;a_{6}\;a_{5}\;a_{2})$, which can be broken into
$\Pi_{1}$ and $\Pi_{3}$ in a similar manner. In fact, when combining two such
collections of transpositions $\Pi_{a}$ and $\Pi_{b}$ with empty intersection
into one large cycle $C$, there are just two options, only one of which can be
correct. Start with an arbitrary agent, say $a_{1}$, and note that either
$C(a_{1})=\Pi_{a}(a_{1})$ and $C^{-1}(a_{1})=\Pi_{b}(a_{1})$, or
$C(a_{1})=\Pi_{b}(a_{1})$ and $C^{-1}(a_{1})=\Pi_{a}(a_{1})$. From there, just
alternate between the stable partitions $\Pi_{a}$ and $\Pi_{b}$ and continue
until the cycle is complete. Note though that although one of the
constructions must satisfy stability condition T1, condition T2 might not be
satisfied. Consider, for example, the cycle
$(a_{1}\;a_{4}\;a_{5}\;a_{2}\;a_{3}\;a_{6})$ produced by joining $\Pi_{3}$ and
$\Pi_{2}$, which satisfies T1 but not T2, as, for example agents
$\\{a_{1},a_{2}\\}$ prefer each other over their predecessors.

######  Theorem 3.7.

Any non-reduced stable partition $\Pi$ can be constructed from two reduced
stable partitions $\Pi_{a}$, $\Pi_{b}$.

###### Proof.

Consider an arbitrary stable partition
$\Pi=\mathcal{T}\cup\mathcal{E}\cup\mathcal{O}_{I}$, where $\mathcal{T}$ are
the stable transpositions, $\mathcal{E}$ are the even cycles of length larger
than 2, and $\mathcal{O}_{I}$ are the odd cycles. Then we have shown in Lemma
3.6 that we can break down each cycle $c\in\mathcal{E}$ into two different
collections of transpositions. Now we can consider the reduced stable
partitions $\Pi_{a}$ and $\Pi_{b}$ where in $\Pi_{a}$ every even cycle in
$\mathcal{E}$ is broken down in one way and in $\Pi_{b}$ the other way. Then
precisely, $\Pi_{a}\cap\Pi_{b}=T\cup\mathcal{O}_{I}$, so the symmetric
difference $D=\Pi_{a}\triangle\Pi_{b}$ contains precisely the transpositions
formed by breaking down each cycle $c\in\mathcal{E}$ in two different ways.

Now in combination with Lemma 3.6, we know that the symmetric difference is
precisely the set
$D=\\{(a_{i_{j}}\;a_{i_{j+1}})\;|\;(a_{i_{0}}\;a_{i_{1}}\;a_{i_{2}}\;\dots\;a_{i_{2k-1}})\in\mathcal{E}\;\wedge\;0\leq
j\leq 2k-1\\}$, where addition is taken modulo $2k$ to account for the cyclic
structure. Thus, knowing $D$, we have overlapping transpositions such that
every agent $a_{i_{j}}$ is contained in exactly two transpositions
$(a_{i_{j}}\;a_{i_{j+1}})$ and $(a_{i_{j-1}}\;a_{i_{j}})$. We can now
reconstruct $\mathcal{E}$ cycle by cycle by simply aligning the transpositions
as informally shown below Example 4, where $a_{i_{j}}$’s preferences will
uniquely determine the alignment by determining whether $a_{i_{j-1}}$ or
$a_{i_{j+1}}$ must be the successor to satisfy stability condition T1.

The result follows as $\Pi=(\Pi_{a}\cap\Pi_{b})\cup\mathcal{E}$, where
$\mathcal{E}$ is constructed from $\Pi_{a}\triangle\Pi_{b}$. ∎

This gives a naive way to construct all stable partitions from the set of
reduced stable partitions.

######  Corollary 3.8.

We can construct all stable partitions, $P(I)$, of an sr instance $I$ from its
set of reduced stable partitions, $RP(I)$, in $O(|RP(I)|^{2}n^{2})$ time
without repetitions.

###### Proof.

Knowing that any stable partition can be constructed from two reduced stable
partitions due to Theorem 3.7, we can conclude that in addition to all reduced
stable partitions $RP(I)$, we can find all other stable partitions admitted by
$I$ by considering every one of the $\binom{|RP(I)|}{2}=O(|RP(I)|^{2})$ pairs
of reduced stable partitions, constructing each candidate partition and
verifying in $O(n^{2})$ time that it satisfies T1 and T2.

This process will not generate repetitions, as two distinct pairs of reduced
stable partitions will never generate the same non-reduced stable partition
candidate. To see this, let $\\{\Pi_{a},\Pi_{b}\\},\\{\Pi_{c},\Pi_{d}\\}$ be
two distinct pairs of reduced stable partitions where agent $a_{i_{1}}$ is in
a different transposition in each of them. Then, when merging $\Pi_{a}$ and
$\Pi_{b}$ to a non-reduced stable partition candidate $\Pi$ using the method
above, we have that either $\Pi(a_{i_{1}})=\Pi_{a}(a_{i_{1}})$ or
$\Pi(a_{i_{1}})=\Pi_{b}(a_{i_{1}})$ and similar when merging $\Pi_{c}$ and
$\Pi_{d}$ to candidate $\Pi^{\prime}$. However,
$\\{\Pi_{a}(a_{i_{1}}),\Pi_{b}(a_{i_{1}})\\}\cap\\{\Pi_{c}(a_{i_{1}}),\Pi_{d}(a_{i_{1}})\\}=\varnothing$,
so clearly $\Pi\neq\Pi^{\prime}$. ∎

However, as $|RP(I)|$ may be exponential in $n$ and we have seen that many
combinations of reduced stable partitions do not to lead to a non-reduced
stable partition, we focus the study on stable cycles themselves and how they
could be useful in enumerating all stable partitions directly.

First, to refine the search for longer even cycles, we can show restrictions
on the combinatorics of agents. We want to show that it suffices to know a
predecessor-successor pair of agents in a partial even cycle
$C=(a_{i_{1}}\;a_{i_{2}}\;\dots)$ to find a completion if one exists, and that
we can find such a completion in polynomial time. For this, we show that the
correspondence between $C$ and $C\setminus\\{a_{i_{2}}\\}$, where the latter
is a potential odd cycle of some related instance. Specifically, we propose
the method outlined in Algorithm 2 to transform the instance $I$ appropriately
to an instance $I_{S}$ such that it admits the desired invariant odd cycle if
it exists. Specifically, the procedure takes as input the instance and a
predecessor-successor pair $a_{i_{1}},a_{i_{2}}$ of the partial (not
necessarily stable) cycle in question and creates an instance $I_{S}$ related
to $I$ without agent $a_{i_{2}}$ in which the preference lists of all agents
preferred by $a_{i_{2}}$ over $a_{i_{1}}$ in $I$ are modified in $I_{S}$ such
that $a_{i_{1}}$ takes the spot of $a_{i_{2}}$ and its previous entry is
deleted, and these agents, if not preferred by $a_{i_{1}}$ over $a_{i_{2}}$,
are promoted in the preference list of $a_{i_{1}}$ in $I_{S}$ to before the
rank position of $a_{i_{2}}$ in $a_{i_{1}}$’s preference list in $I$ while
maintaining the relative preference order given by $a_{i_{2}}$ in $I$.

1:$I$: an sr instance; $a_{i_{1}}$: an agent of some partial (not-necessarily
stable) cycle of $I$; $a_{i_{2}}$: the successor of $a_{i_{1}}$ in the partial
cycle in question

2:$I_{S}$ : an instance in which $a_{i_{1}},a_{i_{2}}$ are in an odd cycle if
the partial cycle is stable

3:$I_{S}\leftarrow I$ (make a copy)

4:for agent $a_{r}$ preferred by $a_{i_{2}}$ over $a_{i_{1}}$ do

5: delete $a_{i_{1}}$ from preference list of $a_{r}$ in $I_{S}$

6: replace $a_{i_{2}}$ by $a_{i_{1}}$ in preference list of $a_{r}$ in $I_{S}$

7:end for

8:$k\leftarrow$ rank${}_{i_{1}}(a_{i_{2}})$

9:for agent $a_{r}$ preferred by $a_{i_{2}}$ (in order) over $a_{i_{1}}$ but
not by $a_{i_{1}}$ over $a_{i_{2}}$ do

10: move $a_{r}$ up in the preference list of $a_{i_{1}}$ to rank-position $k$
in $I_{S}$

11: $k\leftarrow k+1$

12:end for

13:delete $a_{i_{2}}$ from $I_{S}$ altogether

14:return $I_{S}$

Algorithm 2 ConstructI${}_{S}(I$, $a_{i_{1}}$, $a_{i_{2}})$, constructs
$I_{S}$ from sr instance $I$

######  Theorem 3.9.

Let $I$ be an sr instance, let $(a_{i_{1}}\;a_{i_{2}}\dots)$ be a partial
cycle of $I$, and let $I_{S}$ be the instance constructed from $I$ using
Algorithm 2. If $(a_{i_{1}}\;a_{i_{2}}\dots)$ has a completion to an even
stable cycle in $I$, then $a_{i_{1}}$ belongs to an odd stable cycle in
$I_{S}$.

###### Proof.

Suppose that $C=(a_{i_{1}}\;a_{i_{2}}\;a_{i_{3}}\dots\;a_{i_{2k}})$ is an even
cycle in a stable partition $\Pi$ of $I$ for some agents
$a_{i_{3}}\dots\;a_{i_{2k}}$. We claim that
$C^{\prime}=(a_{i_{1}}\;a_{i_{3}}\dots\;a_{i_{2k}})$ is an odd cycle of any
stable partition $\Pi^{\prime}$ in $I_{S}$. For this, we need to prove that
stability conditions T1 and T2 are satisfied.

For T1, by stability of $\Pi$, in $I$, we have that $a_{i_{1}}$ prefers
$a_{i_{2}}$ to $a_{i_{2k}}$ and $a_{i_{2}}$ prefers $a_{i_{3}}$ to
$a_{i_{1}}$. Hence, by construction, $a_{i_{1}}$ prefers $a_{i_{3}}$ to
$a_{i_{2k}}$ in $I_{S}$. Also, $a_{i_{3}}$ prefers $a_{i_{4}}$ to $a_{i_{2}}$
in $I$ by stability of $\Pi$, so $a_{i_{3}}$ prefers $a_{i_{4}}$ to
$a_{i_{1}}$ in $I_{S}$ since $a_{i_{2}}$ prefers $a_{i_{3}}$ to $a_{i_{1}}$ in
$I$.

For T2, suppose that $\\{a_{r},a_{s}\\}$ block $\Pi^{\prime}$ in $I_{S}$.
First, suppose that $a_{r}=a_{i_{1}}$. Then $a_{s}\neq a_{i_{3}}$ as
$(\Pi^{\prime})^{-1}(a_{i_{3}})=a_{i_{1}}$ and $a_{i_{1}}$ prefers $a_{s}$ to
$a_{i_{2k}}$ in $I_{S}$. Suppose that $a_{i_{2}}$ prefers $a_{s}$ to
$a_{i_{1}}$ in $I$. Then $a_{s}$ replaced $a_{i_{2}}$ with $a_{i_{1}}$ in
$I_{S}$. This means that $\\{a_{i_{2}},a_{i_{s}}\\}$ blocks $\Pi$ in $I$, a
contradiction. Therefore, $a_{i_{2}}$ does not prefer $a_{s}$ to $a_{i_{1}}$
in $I$, so $a_{s}$ remains in the same position in the preference list of
$a_{i_{1}}$ in $I_{S}$ as it was in $I$, so $\\{a_{i_{1}},a_{s}\\}$ blocks
$\Pi$ in $I$, a contradiction.

Now suppose that $a_{r}=a_{i_{3}}$. Then $a_{i_{3}}$ prefers $a_{s}$ to
$a_{i_{1}}$ in $I_{S}$. We know that $a_{i_{2}}$ prefers $a_{i_{3}}$ to
$a_{i_{1}}$ in $I$. Hence, by construction of $I_{S}$, $a_{i_{3}}$ prefers
$a_{s}$ to $a_{i_{2}}$. Also since $a_{s}\neq a_{i_{1}}$ and $a_{s}\neq
a_{i_{3}}$, it must be the case that
$(\Pi^{\prime})^{-1}(a_{s})=\Pi^{-1}(a_{s})$, so $\\{a_{i_{3}},a_{s}\\}$ block
$\Pi$ in $I$, a contradiction.

Lastly, if $\\{a_{r},a_{s}\\}\cap\\{a_{i_{1}},a_{i_{3}}\\}=\varnothing$, then
clearly $\\{a_{r},a_{s}\\}$ block $\Pi$ in $I$ as
$(\Pi^{\prime})^{-1}(a_{r})=\Pi^{-1}(a_{r})$,
$(\Pi^{\prime})^{-1}(a_{s})=\Pi^{-1}(a_{s})$, $a_{r}$ prefers $a_{s}$ to
$\Pi^{-1}(a_{r})$ and $a_{s}$ prefers $a_{r}$ to $\Pi^{-1}(a_{s})$. ∎

Due to odd cycles being invariant, we can use the statement above to reason
about the structural restrictions of longer even cycles implied by a
predecessor-successor pair.

######  Corollary 3.10.

If $C=(a_{i_{1}}\;a_{i_{2}}\;a_{i_{3}}\;\dots\;a_{i_{2k}})$ and
$C^{\prime}=(a_{i_{1}}\;a_{i_{2}}\;a_{i_{3}}^{\prime}\;\dots\;a_{i_{2l}}^{\prime})$
are both even cycles of $I$, then $k=l$ and $a_{i_{j}}=a_{i_{j}}^{\prime}$ for
$3\leq j\leq 2k$.

###### Proof.

Consider even cycles $C$, $C^{\prime}$ of $I$. Then by Theorem 3.9, we must
have stable odd cycles $(a_{i_{1}}\;a_{i_{3}}\;\dots\;a_{i_{2k}})$ and
$(a_{i_{1}}\;a_{i_{3}}^{\prime}\;\dots\;a_{i_{2l}}^{\prime})$ in the instance
$I_{S}$ using the transformation from $I$ in Algorithm 2. However, because
$a_{1}$ is in both cycles and odd cycles are invariant, they are the same
cycles and the result follows. ∎

Now note that this also implies that no instance can admit, for example, the
following two stable partitions:
$\Pi=(a_{1}\;a_{2}\;a_{3}\;a_{4}\;a_{5}\;a_{6})$,
$\Pi^{\prime}=(a_{1}\;a_{2}\;a_{3}\;a_{4})(a_{5}\;a_{6})$.

######  Corollary 3.11.

If some stable partition $\Pi$ of sr instance $I$ contains an even cycle
$C=(a_{i_{1}}\;\dots\;a_{i_{k}})$, then $C$ cannot be contained in a longer
even cycle
$C^{\prime}=(a_{i_{1}}\;\dots\;a_{i_{k}}\;a_{j_{1}}\;\dots\;a_{j_{l}})$ of
some other stable partition $\Pi^{\prime}$ of $I$.

###### Proof.

We can consider any predecessor-successor pair in $C$ to see that Corollary
3.10 implies that there cannot exist such a $C^{\prime}$. ∎

The results also greatly restrict the number of even cycles that an instance
can admit.

######  Corollary 3.12.

Any sr instance with $n$ agents admits at most $O(n_{1}^{2}+n_{2})=O(n^{2})$
cycles of length not equal to two, where $n_{2}=|A(\mathcal{O}_{I})|$ and
$n_{1}=n-n_{2}$.

###### Proof.

As odd cycles are invariant and any agent can be in at most one odd cycle,
there are at most $n_{2}$ odd cycles.

Due to Corollary 3.10, any candidate predecessor-successor pair is part of at
most one even stable cycle, and hence any pair of agents can be consecutively
ordered in at most two even stable cycles. Thus, we have at most
$O(n_{1}^{2})$ even stable cycles of length not equal to two. ∎

It also establishes the following powerful result.

######  Corollary 3.13.

Let $(a_{i_{1}}\;a_{i_{2}}\dots)$ be a partial cycle in some sr instance $I$.
In linear time, we can determine whether this partial cycle has a completion
$C=(a_{i_{1}}\;a_{i_{2}}\;a_{i_{3}}\dots a_{i_{2k}})$ to an even cycle of some
stable partition of $I$, or report that no such completion exists. If a
completion $C$ to a stable even cycle does exist, then $C$ must be unique.

###### Proof.

We can construct $I_{S}$ from $I$ using the Algorithm 2 and find some stable
partition $\Pi^{\prime}$ of $I_{S}$, all in linear time. Now, if $a_{i_{1}}$
does not belong to an odd stable cycle $C^{\prime}$ of $\Pi^{\prime}$, then by
Theorem 3.9, $(a_{i_{1}}\;a_{i_{2}}\dots)$ has no completion to a stable even
cycle of $I$.

Otherwise, suppose that $C^{\prime}=(a_{i_{1}}\;a_{i_{3}}\dots a_{i_{2k}})$ is
an odd stable cycle of $\Pi^{\prime}$. Then the cycle
$C=(a_{i_{1}}\;a_{i_{2}}\;a_{i_{3}}\;\dots\;a_{i_{2k}})$ is an even stable
cycle of $I$ unless $\\{a_{i_{1}},a_{i_{3}}\\}$ block in
$(\Pi^{\prime}\setminus C^{\prime})\cup C$.

Thus, we can either output $C$, which is unique by Corollary 3.10, or it must
be the case that “no” is the correct answer, as by the same Corollary, if
$(a_{i_{1}}\;a_{i_{2}}\dots)$ has a completion to an even stable cycle in $I$,
then $C=(a_{i_{1}}\;a_{i_{2}}\;a_{i_{3}}\dots a_{i_{2k}})$ is the only
candidate. ∎

We have shown above that if $C$ is a partial even stable cycle of the
considered instance $I$, then we must have a corresponding invariant odd cycle
$C^{\prime}$ of some related instance of $I$, and that therefore, $C$ has a
unique completion. Furthermore, Corollary 3.13 establishes that we only need
to consider a potential successor-predecessor pair to see whether that pair is
indeed part of some longer unique stable even cycle, and we can do so in
linear time.

Furthermore, given an instance $I$ and a (non-partial) candidate cycle $C$, we
can also efficiently verify whether it is in some stable partition as it is,
by Corollary 3.13, sufficient to consider any successor-precessor pair in it.
If so, we can also explicitly construct a stable partition $\Pi$ containing
$C$ using the method described in the proof, where $\Pi=(\Pi^{\prime}\setminus
C^{\prime})\cup C$.

######  Corollary 3.14.

Given an sr instance $I$ and a candidate (not necessarily stable) cycle $C$ of
even length, we can verify whether $C$ is stable and, if so, construct a
stable partition $\Pi$ containing $C$, all in linear time.

###  3.3 All Stable Cycles

With stable matchings, we can consider the problem of finding all stable
pairs, which is defined as the union of all pairs contained in some stable
matching of an sr instance $I$,

$SP(I)=\\{\\{a_{i},a_{j}\\}\in M\;|\;M\in S(I)\\}$

where $S(I)$ is the set of all stable matchings admitted by $I$. Similarly,
one can ask about the fixed pairs, which are the pairs contained in all stable
matchings of $I$. Analogously, we introduce the corresponding questions for
stable partitions: given an sr instance $I$, what are all the stable cycles,
denoted $SC(I)$, admitted by some stable partition of the instance? Similarly,
what are the (fixed) stable cycles, denoted $FC(I)$, admitted by all its
stable partitions?

We have seen how to enumerate all reduced stable partitions of an instance and
also how to reconstruct longer even cycles from transpositions, allowing us to
enumerate all stable partitions, not necessarily reduced. However, the
enumeration of reduced stable partitions might naturally run in time
exponential in the number of agents, similar to the enumeration of all stable
matchings of a solvable instance. In contrast, when only looking at stable
pairs rather than matchings, [18] presented an $O(n^{3})$ algorithm to find
them in a sr instance with $n$ agents. Therefore, it is natural to ask whether
we can construct a similar efficient algorithm for finding all stable cycles
of a stable partition.

Given an sr instance $I$, we are looking to find stable cycles

$SC(I)=\\{C\in\Pi\;|\;\Pi\in P(I)\\}$

where $P(I)$ are all stable partitions admitted by $I$. Now note that the odd
cycles $\mathcal{O}_{I}$ are invariant and can be computed efficiently, so we
require to find the union of all stable cycles of even length. Observe that

$\mathcal{O}_{I}\subseteq FC(I)\subseteq RSC(I)\subseteq SC(I),$

where $RSC(I)$ are the reduced stable cycles (i.e. stable transpositions and
odd cycles) of $I$. This is because for any stable cycle $C$ of even length
larger than 2, we can break it into two collections of stable transpositions
by Lemma 3.6, such that $C$ cannot be fixed. Note that if $|P(I)|=1$, then the
second and third inclusions hold with equality and if, furthermore,
$|A(\mathcal{O}_{I})|=n$, then the first inequality also holds with equality.
Thus, we can find all reduced fixed cycles directly in $O(n^{2})$ time by
constructing the odd cycles $\mathcal{O}_{I}$, which are fixed, and the sub-
instance $I_{T}$ (computed using Algorithm 1). Then, we can compute the
reduced phase-1 table of $I_{T}$, from which we can directly derive the fixed
pairs (i.e. fixed stable transpositions) as proven by [25].

######  Theorem 3.15.

Given an sr instance $I$ with $n$ agents, we can find all its fixed cycles in
linear time.

Theorem 3.3 states that any reduced stable partition $\Pi_{i}$ is the union of
some stable matching $M_{i}$ of the sub-instance $I_{T}$ of $I$ (constructed
by Algorithm 1), and $\mathcal{O}_{I}$. Therefore, in order to find all stable
transpositions, we can apply the known all stable pairs algorithm to $I_{T}$.

######  Lemma 3.16.

Given an sr instance $I$ with $n$ agents, we can find all reduced stable
cycles, $RSC(I)$, i.e. odd cycles and stable transpositions, in
$O(n^{2}+n_{1}^{3})$ time, where $n_{1}=n-|A(\mathcal{O}_{I})|$.

###### Proof.

We know that we can find all stable pairs of a solvable sr instance with
$n_{1}$ agents in $O(n_{1}^{3})$ time using the algorithm by [18].

Consider any pair $p$ produced by the algorithm. Then $p$ is a stable pair of
some stable matching $M$ of $I_{T}$, so by Theorem 3.3, $M\mathcal{O}_{I}$ is
a reduced stable partition of $I$ and thus $p$ a stable transposition.
Similarly, if $t$ is some stable transposition of $I$, then there exists some
reduced stable partition $\Pi_{i}$ containing $t$. By Theorem 3.3, there
exists some stable matching $M_{i}$ of $I_{T}$ such that
$\Pi_{i}=M_{i}\mathcal{O}_{I}$. As $t$ is a transposition, we must have that
$t\in M_{i}$, so the stable pairs algorithm must detect and output $t$.

The complexity follows directly from the size of $I_{T}$ and the justification
by [18]. ∎

This lets us extend Corollary 3.12 to include transpositions.

######  Theorem 3.17.

Any sr instance with $n$ agents admits at most $O(n_{1}^{2}+n_{2})=O(n^{2})$
stable cycles, where $n_{2}=|A(\mathcal{O}_{I})|$ and $n_{1}=n-n_{2}$.

###### Proof.

By [25] we know that any solvable instance with $k$ agents admits at most
$O(k^{2})$ stable pairs, so we will have at most $O(n_{1}^{2})$ stable
transpositions. Due to Corollary 3.12, there are also at most
$O(n_{1}^{2}+n_{2})$ stable cycles that are not transpositions, so the result
follows. ∎

Now to compute all stable cycles, not necessarily reduced or fixed, we can use
our previous work on reconstructing stable cycles of even length larger than 2
to show the following.

######  Theorem 3.18.

Given an sr instance $I$ with $n$ agents, we can find all its stable cycles,
$SC(I)$, in quadratic time, or more specifically, in
$O(n_{1}^{2}(n^{2}+n_{1}))$ time, where $n_{2}=|A(\mathcal{O}_{I})|$ and
$n_{1}=n-n_{2}$.

###### Proof.

Due to Lemma 3.16, we can find all reduced stable cycles, i.e. all stable
transpositions and odd cycles, in $O(n^{2}+n_{1}^{3})$ time.

Now with regards to the stable cycles of even length larger than 2, we can
consider all pairs of agents that could be part of a longer even stable cycle.
There are $\binom{n}{2}=O(n^{2})$ such subsets in general, but we can limit
ourselves to the stable transpositions we found in the previous step due to
Theorem 3.7, in which we showed that any even cycle can be broken into at
least two collections of stable transpositions, therefore no agent pair that
is not a stable transposition will lead to an even stable cycle.

For each pair $\\{a_{i},a_{j}\\}$, we need to consider each of the two
orderings $(a_{i}\;a_{j}\;\dots)$ and $(a_{j}\;a_{i}\;\dots)$. Clearly, there
are $O(n_{1}^{2})$ such pairs. Then, for each ordering, we can try to find its
unique completion in $O(n^{2})$ time due to Corollary 3.13 and finally verify
that it is a stable cycle, also in $O(n^{2})$ time due to Corollary 3.14.
Altogether, we consider $O(n_{1}^{2})$ candidates and need $O(n^{2})$ time for
each, therefore requiring $O(n_{1}^{2}n^{2})$ time. As any consecutively
ordered pair of agents will only be part of at most one stable cycle of length
larger than 2 by Corollary 3.13, we can eliminate all such pairs from the
candidate set once detected. This will ensure that the even cycles are
enumerated exactly once.

Altogether, the steps take $O(n_{1}^{2}(n^{2}+n_{1}))$, or $O(n^{4})$ time. ∎

###  3.4 Enumerating Stable Partitions

Now that we know how to find all stable cycles of our sr instance $I$
efficiently, we show that this leads to an alternative approach to enumerating
all stable partitions, $P(I)$, compared to the naive method from Corollary
3.8. In this procedure, we will recursively build up all stable partitions,
starting with the invariant odd cycles and adding one additional cycle with
each recursive call. Simultaneously, at each recursive step, we fix an
arbitrary agent not yet in any cycle of the partial partition and branch on
all its cycles (as given by $SC(I)$) that, together with the current partial
partition, lead to at least one stable partition. This way, the recursive tree
consists of paths leading from the origin (a partial stable partition
containing only the odd cycles) to all leaf nodes (all stable partitions).

The procedure EnumPI implements the logic described in the previous paragraph
to enumerate all stable partitions. The parameter “cycles” contains a partial
stable partition and grows with each recursive call until it is a full stable
partition. The parameter “agents” contains all agents in $I$ not yet in any
cycle of “cycles” and is naturally decreasing in size as “cycles” grows.
Finally, the parameter $SC$ contains all cycles of some stable partition of
$I$ containing some agent in “agents”, not necessarily compatible with
“cycles” (in the sense that not every cycle in $SC$ belongs to a stable
partition with “cycles”). Note that by this behaviour, if “agents” is empty,
then “cycles” is a stable partition and we print it. If not, then the
algorithm proceeds to return and remove an arbitrary agent $a_{i}$ from
“agents”. Then, the algorithm checks whether there is a unique cycle $c$
containing $a_{i}$ such that “cycles”$\cup c$ is part of some stable partition
of $I$ using the procedure FC from Algorithm 3. If there is a unique such $c$,
then we reduce the set of stable cycles $SC$ to $SC_{red}$ which does not
contain any cycles with agents in $c$ and recurse with the increased partial
stable partition “cycles”$\cup c$, the reduced set of stable cycles to choose
from $SC_{red}$, and the reduced set of remaining agents “agents”$\setminus
A(c)$.

If there is no unique choice $c$, then the procedure loops through all
candidate cycles $c^{\prime}\in SC$ that contain $a_{i}$, at least two of
which must correspond to a partial stable partition “cycles”$\cup c^{\prime}$
by construction. Whether “cycles”$\cup c^{\prime}$ does correspond to a
partial stable partition or only a collection of cycles that is not a subset
of any stable partition can be determined with the procedure verify which is
omitted but uses the result from Corollary 3.14 to check whether the
collection of cycles completes to a stable partition. If so, we, again, create
the appropriate $SC_{red}$ and recurse as above.

The helper function FC which will speed up the execution of calls where the
partial partition (in the sense that the cycles contained in the parameter are
part of some stable partition, but may be missing some cycles) only allows one
fixed cycle from all candidate cycles that contain the set agent. This must
always be a transposition. To see this, consider an sr instance $I$. If we
have a collection of cycles $C$ including all odd cycles that are part of some
stable partition of $I$ and a single agent $a_{i}\in A(I)$ not in $A(C)$, then
by the existence of stable partitions, there must exist a cycle $c\notin C$
such that $C\cup c$ is part of some stable partition of $I$. Now if $c$ is
unique, then $c$ must be a transposition. Suppose not, then $c$ must be of
even length at least 4 (by $C$ containing all odd cycles), but then we can
break it into two collections of stable transpositions $c_{1},c_{2}$ such that
also $C\cup c_{1}$ and $C\cup c_{2}$ are part of some stable partition. Thus,
unique choices must be transpositions.

Now, the procedure FC described in Algorithm 3 takes such a collection of
cycles $C$ as input “cycles”, as well as a single agent $a_{i}\in
A(I)\setminus A(C)$ and generates a sub-instance $I^{\prime}$ of $I$
consisting only of the agents not in $C$ with their preference lists truncated
such that any stable partition $\Pi$ of $I^{\prime}$ corresponds to a stable
partition $\Pi\cup C$ of $I$. In fact, $I^{\prime}$ must be solvable as there
must exist some such stable partition by construction and if any would contain
an odd cycle, “cycles” would not contain all odd cycles. Thus, by the argument
in the previous paragraph, to check whether the agent $a_{i}$ is in a unique
cycle $c$ such that $C\cup c$ is a stable partition of $I$, it suffices to
apply the fixed pairs algorithm for stable matchings, for example using the
linear time procedure (denoted by getFixedPairs) by [25], and returning
(through an $O(n)$ search) the fixed pair containing $a_{i}$, if it exists,
otherwise returning null to report that no such fixed pair exists (to indicate
that the choice is not unique).

1:cycles: a collection of cycles which is a subset of some stable partition of
$I$ and includes all odd cycles of $I$; $a_{i}$ : a single agent in
$A(I)\setminus A($cycles$)$

2:pair : a pair of two agents in $A(I)\setminus A($cycles$)$, potentially null

3:$I^{\prime}\leftarrow I$ (make a copy of $I$)

4:for cycle in cycles do

5: for $a_{j}$ in cycle do

6: for $a_{p}$ preferred by $a_{j}$ over cycle${}^{-1}(a_{j})$ in $I$ do

7: delete $a_{j}$ and all successors of $a_{j}$ from $a_{p}$’s preference list
in $I^{\prime}$ (if exists)

8: end for

9: delete $a_{j}$ from the set of agents of $I^{\prime}$ altogether

10: end for

11:end for

12:fixed $\leftarrow$ getFixedPairs($I^{\prime}$)

13:if $\\{a_{i},a_{k}\\}$ in fixed for some $a_{k}\in A(I^{\prime})$ then

14: return ($a_{i}$, $a_{k}$)

15:end if

16:return null

Algorithm 3 FC(cycles, $a_{i}$), Fixed Cycle Helper Function for Algorithm 4

Overall, our method to enumerate $P(I)$ first finds all $O(n_{1}^{2}+n_{2})$
stable cycles, $SC(I)$, in $O(n_{1}^{2}(n^{2}+n_{1}))$ time as previously
shown, and then calling the procedure EnumPI described in Algorithm 4 with
stable cycles $SC(I)\setminus\mathcal{O}_{I}$ as parameter $SC$, the invariant
odd cycles $\mathcal{O}_{I}$ as parameter “cycles”, and agents $A(I)\setminus
A(\mathcal{O}_{I})$ as parameter “agents”.

1:$SC$: all cycles of some stable partition of $I$ containing some agent in
“agents” and no agent in $A($cycles$)$; cycles: a collection of cycles which
is a subset of some stable partition of $I$ and includes all odd cycles of
$I$; agents: all agents in $A(I)\setminus A($cycles$)$

2:if agents $=\varnothing$ then

3: print(cycles)

4: return

5:end if

6:$a_{i}\leftarrow$ agents.pop()

7:fixed $\leftarrow$ FC($I$, cycles, $a_{i})$

8:if fixed $\neq$ null then

9: $SC_{red}\leftarrow\\{(a_{j_{1}}\;\dots\;a_{j_{k}})\in
SC\;|\;\forall\;1\leq s\leq k,\;a_{j_{s}}$ not in fixed$\\}$

10: EnumPI($SC_{red}$, cycles $\cup$ fixed, agents$\setminus A$(fixed))

11:else

12: for cycle in $SC$ containing $a_{i}$ do

13: if verify(cycles $\cup$ cycle) then

14: $SC_{red}\leftarrow\\{(a_{j_{1}}\;\dots\;a_{j_{k}})\in
SC\;|\;\forall\;1\leq s\leq k,\;a_{j_{s}}$ not in cycle$\\}$

15: EnumPI($SC_{red}$, cycles $\cup$ cycle, agents$\setminus A$(cycle))

16: end if

17: end for

18:end if

Algorithm 4 EnumPI($SC$, cycles, agents), recursively enumerates all stable
partitions $P(I)$

######  Theorem 3.19.

Let $I$ be an instance of sr with $n$ agents. Then Algorithm 4 enumerates all
stable partitions $P(I)$ of $I$ without repetition in $O(|P(I)|n^{3}+n^{4})$
time, or more specifically, $O((|P(I)|+n_{1})n_{1}n^{2}+n_{1}^{3})$ time,
where $n_{2}=|A(\mathcal{O}_{I})|$ and $n_{1}=n-n_{2}$, when called as
described above.

###### Proof.

To establish correctness, note that by definition of stable cycles, each
stable cycle is contained in at least one stable partition and all stable
partitions are made up only of (some, not necessarily all) stable cycles. At
every node in the recursive tree, if all previous cycles on the recursive path
are compatible, i.e., belong to some stable partition together, then if
$a_{i}$ is null, all agents are part of some cycle and thus the path
represents a stable partition and we can stop. Otherwise, if $a_{i}$ is not
null, there must be some cycle or cycles $C$ in their $SC$ parameter that
cycles$\cup c$ is compatible for all $c\in C$. If $|C|=1$, then we will detect
it using the procedure FC and can immediately filter out all cycles in $SC$
from further consideration that contain any agent in $c$. Similarly, if
$|C|>1$, then we will need to consider all cycles in $SC$ that contain
$a_{i}$, check whether it is compatible with cycles and, if so, recurse with a
subset of $SC$ not containing any cycles with overlapping agents. This
procedure detects every stable partition exactly once, as by construction,
every path contains distinct sets of cycles such that every agent is contained
exactly once. As the first call passes only the odd cycles to the procedure,
it is trivially compatible as the odd cycles are invariant, and correctness
follows by induction.

Now with regards to the computational complexity, note that in the recursive
tree, there will be exactly $|P(I)|$ leaf nodes, $O(|P(I)|n_{1})$ internal
nodes with one child because each stable partition will contain $O(n)$ cycles
and the odd cycles are given, and $O(|P(I)|)$ internal nodes with at least two
children by properties of binary trees. Every leaf and internal node with one
child takes $O(n^{2})$ time due to Algorithm 3 and building $SCred$, and every
internal node with more children takes $O(n_{1}n^{2})$ time because we
consider at most $O(n_{1})$ different stable cycles. This is because each
agent can be contained in $O(n_{1})$ transpositions and can have at most
$O(n_{1})$ successors in even cycles, and by Corollary 3.10 in at most one
even cycle per predecessor-successor pair. We noted in the description of
Algorithm 3 that testing whether a candidate set of cycles is part of a stable
partition takes $O(n^{2})$ time, and building $SC_{red}$ also takes
$O(n_{1}^{2})$ time. Thus, the recursive procedure takes, overall,
$O(|P(I)|n_{1}n^{2})$ time, with an additional $O(n_{1}^{2}(n^{2}+n_{1}))$
overhead to compute all stable cycles once. ∎

##  4 Complexity of Profile-Optimal Stable Partitions

We have shown how to efficiently enumerate all reduced stable partitions
admitted by an sr instance $I$. However, as the size of the set $S(I_{T})$ of
all stable matchings of the sub-instance $I_{T}$ of $I$ (constructed using
Algorithm 1) can, in general, be exponential in the number of agents $n$, this
might not be a good solution to finding a reduced stable partition with some
special property. Therefore, we might be interested in computing some “fair”
or “optimal” stable partitions directly. As the odd cycles of sr instances are
invariant, there is no point in seeking odd cycles with special properties for
a given instance. However, we can consider the set of stable partitions of a
given instance and seek, for example, a reduced stable partition with minimum
regret. In this case, it is not enough to simply leverage the result from
Theorem 3.3, as we are deleting entries in the preference lists during the
construction of $I_{T}$, which makes the resulting profile entries in the
larger instance inconsistent. For this, we use a _padding argument_ by
replacing deleted agents in the preference lists by dummy agents which are
guaranteed to be matched to each other by construction. Therefore, a solvable
instance similar to $I_{T}$ is created in which the ranks are maintained and
known algorithms can be applied. This method and its correctness is outlined
in Section 4.1. Section 4.2 establishes the computational complexity of
computing various types of stable partitions directly, and 4.3 gives some
details about the approximability of the problems that we show to be NP-hard
in general.

###  4.1 Padding Method

Whenever, during the construction of $I_{E}$ and $I_{T}$, an agent is supposed
to be deleted from some preference list, we can instead replace the
corresponding preference list entry to be deleted with a dummy agent entry
that is guaranteed to be matched to another dummy agent in any stable matching
or partition by making them rank each other as their respective first choices.
Agents in odd cycles are automatically replaced in all preference lists of
agents that are not in odd cycles and can be deleted altogether at the end of
the transformation. Clearly, for an instance with $n$ agents, we need at most
$n$ dummy agents in the transformation as they can be reused across but not
within preference lists. If the number of required dummy agents is odd, we can
simply add one more dummy agent to guarantee that all dummy agents are in
fixed pairs of any stable matching of the transformed instance. As we are
replacing all agents in odd cycles with dummy agents in fixed pairs, we
transform the instance $I$ to a solvable instance $I_{P}$ with at most $2n$
agents, allowing us to apply any of the known algorithms now to find stable
matchings satisfying additional optimality criteria with no asymptotic
increase in complexity. We denote these $k$ fixed pairs by
$D=(d_{1}\;d_{2})\dots(d_{k-1}\;d_{k})$ and can map the solution $M$ in
$I_{P}$ back to a solution $\Pi$ for the original instance $I$ by excluding
the dummy agents and including the original odd cycles, i.e., $\Pi=(M\setminus
D)\cup\mathcal{O}_{I}$.

The transformation from $I$ to $I_{P}$ is illustrated in Example 5 on the
instance previously shown in Example 3. Two dummy agents, $d_{1}$ and $d_{2}$,
are introduced, replacing the preference list entries that would otherwise be
deleted in the construction of $I_{T}$. The changes due to the transformation
are indicated using dotted circles and the stable matching corresponding to
the one in Example 3 is indicated using unbroken circles.

$a_{1}$ | $a_{2}$ | $d_{1}$ | $d_{2}$ | …
---|---|---|---|---
$a_{2}$ | $a_{4}$ | $a_{1}$ | … |
$a_{3}$ | $d_{1}$ | $a_{4}$ | … |
$a_{4}$ | $a_{3}$ | $a_{2}$ | … |
$d_{1}$ | $d_{2}$ | … |  |
$d_{2}$ | $d_{1}$ | … |  |
Table 5: An instance $I_{P}$ transformed from $I$ of Example 3

The correctness of the correspondence is established by the following Lemma.

######  Lemma 4.1.

Let $I=(A,\succ)$ be any sr instance and let $I_{P}$ be constructed from $I$
as described above. Then $M$ is a stable matching of $I_{P}$ if and only if
$\Pi=(M\setminus D)\cup\mathcal{O}_{I}$ is a reduced stable partition of $I$,
where $D$ is the collection of dummy agent fixed pairs and $\mathcal{O}_{I}$
are the invariant odd cycles of $I$.

###### Proof.

If suffices to show that $M$ is a stable matching of $I_{P}$ if and only if
$M\setminus D$ is a stable matching of $I_{T}$ constructed from $I$ using
Algorithm 1. Then, by Theorem 3.3, $M\setminus D$ is a stable matching of
$I_{T}$ if and only if $\Pi=(M\setminus D)\cup\mathcal{O}_{I}$ is a reduced
stable partition of $I$ and the result follows.

Indeed, if $M$ is a stable matching of $I_{P}$, then $M\setminus D$ is a
matching of $I_{T}$. Suppose $M\setminus D$ is not stable in $I_{T}$, then, by
the construction of $I_{P}$, there exist two agents $a_{i},a_{j}\in A\setminus
A(\mathcal{O}_{I})$ that prefer each other over their partners in $M\setminus
D$. However the preference relations of all agents in $A\setminus
A(\mathcal{O}_{I})$ are the same for $I_{P}$ and $I_{T}$, so this would
contradict the stability of $M$ in $I_{P}$.

On the other hand, if $M^{\prime}$ is a stable matching of $I_{T}$, then
$M^{\prime}\cup D$ is a matching in $I_{P}$ as we have $A(D)\cap
A(M^{\prime})=\varnothing$. Suppose that $M^{\prime}\cup D$ is not stable in
$I_{P}$. As the preference relations in $I_{T}$ for all agents matched in
$M^{\prime}$ remain the same in $I_{P}$, no two agents matched in $M^{\prime}$
can block $M^{\prime}\cup D$ in $I_{P}$. Also, no dummy agent can block with
another dummy agent or an agent matched in $M^{\prime}$, because all dummy
agents are matched to their first choice. ∎

###  4.2 Complexity of Problems

The padding method allows us to establish further results on the
correspondence between stable partitions and stable matchings. Specifically,
we show that the profile-based optimality criteria for stable matchings carry
over naturally to stable partitions and we can show that the computational
complexity results are consistent.

First, we look at stable partitions with minimum regret. Using the padding
argument, we can show that the problem of finding a minimum-regret stable
partition is tractable.

######  Lemma 4.2.

Let $I$ be an sr instance, let $\Pi=M_{0}\mathcal{O}_{I}$ be a reduced stable
partition of $I$, where $M_{0}$ is a collection of transpositions and
$\mathcal{O}_{I}$ are the odd cycles in $\Pi$, and $I_{P}$ be the transformed
instance using the padding method. If $M_{0}$ is a stable matching of $I_{P}$
with minimum regret, then $\Pi$ is a reduced stable partition with minimum
regret.

###### Proof.

Lemma 4.1 states that if $M_{0}$ is a minimum-regret stable matching of
$I_{P}$, then $\Pi=(M_{0}\setminus D)\cup\mathcal{O}_{I}$ is a reduced stable
partition of $I$, where $D$ are the fixed pairs of dummy agents.

Now suppose that there exists a reduced stable partition $\Pi^{\prime}\neq\Pi$
such that $r(\Pi^{\prime})<r(\Pi)$. Then again, by Lemma 4.1, we must have
$\Pi^{\prime}=M_{1}\mathcal{O}_{I}$, where $M_{1}\neq M_{0}$ is some stable
matching of $I_{P}$. Note that the dummy agents do not affect the regret of
the partition, as all of them are matched to their first choice by
construction. Now, if $r(\Pi^{\prime})<r(\Pi)$, then we must have that
$r(M_{1})<r(M_{0})$ by invariance of $r(\mathcal{O}_{I})$. This contradicts
that $M_{0}$ is a minimum-regret stable matching of $I_{P}$, proving the
statement. ∎

Note that the converse does not necessarily hold, because a reduced stable
partition $\Pi=M_{0}\mathcal{O}_{I}$ as above could have
$r(M_{0})<r(\Pi)=r(\mathcal{O}_{I})$.

We can furthermore show that there is no gap in minimum regret between the set
of reduced stable partitions and the set of stable partitions.

######  Lemma 4.3.

Let $\Pi$ be a minimum-regret reduced stable partition of some sr instance $I$
and let $r(\Pi)$ be its regret. Then for any stable partition $\Pi^{\prime}$
of $I$, we have $r(\Pi)\leq r(\Pi^{\prime})$.

###### Proof.

Suppose not, then there exists some non-reduced minimum regret stable
partition $\Pi^{\prime}$ of instance $I$ which has smaller regret
$r_{1}=r(\Pi^{\prime})$ than the reduced stable partition $\Pi$ with minimum
regret $r_{2}=r(\Pi)$ over all reduced stable partitions.

The odd cycles are invariant for all stable partitions, so $r_{2}>r_{1}$ must
come from choosing transpositions over longer even cycles. However, we can
show that breaking down an even cycle
$C=(a_{i_{1}}\;a_{i_{2}}\;\dots\;a_{i_{2k}})$ preserves its regret, i.e. that
$r(C)=r(C^{\prime})$, where
$C^{\prime}=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{2k-1}}\;a_{i_{2k}}))$. This
holds because any agent’s predecessor in $C^{\prime}$ is at least as good as
their predecessor in $C$ due to stability condition T1. As this transformation
does not impact stability due to Lemma 3.6 and because we can break down every
even cycle larger than 2 like this, some reduced stable partition can achieve
the same regret as any non-reduced stable partition, therefore proving the
statement. ∎

######  Theorem 4.4.

A stable partition with minimum regret always exists and can be computed in
linear time.

###### Proof.

[25] already showed that we can compute a stable matching with minimum regret
in linear time for solvable instances. Thus, we can compute any reduced stable
partition, derive the solvable instance $I_{P}$ from any sr instance $I$, find
a stable matching with minimum regret, and map it back to the instance $I$,
which produces the correct result due to Lemma 4.2. Lemma 4.3 states that the
minimum regret reduced stable partition is also a minimum regret stable
partition. Existence follows from the existence of stable partitions and all
computation and transformation steps can be performed in linear time. ∎

Consistent with stable matchings, minimum regret remains an exception
concerning the tractability of profile-based optimal stable partitions. We now
also consider the following decision problems.

######  Definition 4.5.

Given an sr instance $I$ with $n$ agents and regret $r$, an integer $k$, and a
vector $\sigma\in\\{0,1,\dots,n\\}^{n}$, let

  * •

FC-Dec-SR-SP denote the problem of deciding whether $I$ admits a stable
partition $\Pi$ where $p_{1}(\Pi)\geq k$,

  * •

Rank-Dec-SR-SP denote the problem of deciding whether $I$ admits a stable
partition $\Pi$ where $p(\Pi)\succeq\sigma$,

  * •

RM-Dec-SR-SP denote the problem of deciding whether $I$ admits a minimum
regret stable partition with at most $k$ $r$th choices,

  * •

Gen-Dec-SR-SP denote the problem of deciding whether $I$ admits a stable
partition $\Pi$ where $\sigma^{rev}\succeq p^{rev}(\Pi)$, and

  * •

Egal-Dec-SR-SP denote the problem of deciding whether $I$ admits a stable
partition with cost at most $k$.

For all of these problems, we show that no non-reduced stable partition is
“better” with regards to our optimality criteria than the best reduced stable
partition, which allows us to only consider reduced stable partitions. Knowing
the NP-completeness of the associated problems above for stable matchings, we
can show that all of these problems are NP-complete for stable partitions,
even if the instance is solvable. One might ask whether the same result holds
for unsolvable instances, which have some different structural properties.
Using a reduction from solvable instances, we can show that this is indeed the
case.

First, to show the next statements, the following Lemma establishes that no
non-reduced stable partition satisfies more first-choices than the maximum
number of first-choices satisfied by any reduced stable partition.

######  Lemma 4.6.

Let $C=(a_{i_{1}}\;a_{i_{2}}\;\dots\;a_{i_{k}})$ be an even cycle with $k\geq
4$ and profile $p(C)$. Then both collections of transpositions
$C_{1}=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{k-1}}\;a_{i_{k}})$ and
$C_{2}=(a_{i_{1}}\;a_{i_{k}})\dots(a_{i_{k-2}}\;a_{i_{k-1}})$ are stable and
either $p_{1}(C_{1})\geq p_{1}(C)$ or $p_{1}(C_{2})\geq p_{1}(C)$.

###### Proof.

By Lemma 3.6, both $C_{1}$ and $C_{2}$ are stable. Now for $a_{i_{j}}\in C$,
we know that $C(a_{i_{j}})\succ_{i_{j}}C^{-1}(a_{i_{j}})$ by stability
condition T1 and the fact that $C$ is longer than a transposition, therefore
proving strict inequality. Thus, any agent $a_{i_{j}}$ that contributes a
first choice in $C$ must rank their successor as a first choice and no agent
in $C$ can have their predecessor ranked as a first choice. Therefore, any
such agent $a_{i_{j}}$ adds exactly 1 to $p_{1}(C)$. Now if we break $C$ into
transpositions, an agent $a_{i_{j}}$ who is paired with their first choice
successor now has their first choice as successor and predecessor
simultaneously, thus adding 2 either to $p_{1}(C_{1})$ or to $p_{1}(C_{2})$.
Now for any two agents $a_{i_{r}},a_{i_{s}}$ that get their first choice in
$C$ and have an even number of agents between them, one will get their first
choice assigned in $C_{1}$ and one in $C_{2}$. Any two such agents that have
an odd number of agents between them will both get their first choice assigned
in $C_{1}$ or $C_{2}$. Hence, at least one of $C_{1}$ and $C_{2}$ will achieve
at least as many first choices as in $C$. ∎

This lets us limit the search for first-choice maximal stable partitions on
reduced stable partitions, as we can always break down longer even cycles into
transpositions efficiently without loss of first-choice maximality.

######  Lemma 4.7.

FC-Dec-SR-SP is NP-complete, even if the given instance is solvable.

###### Proof.

Note that FC-Dec-SR-SP is in NP, as given instance $I$, integer $k$, and
partition $\Pi$, we can check whether $\Pi$ is a stable partition of $I$ and
verify that it has at least $k$ first-choices, all in linear time.

[13] proved that FC-Dec-SR-SM, the problem of deciding whether a solvable sr
instance $I$ with complete preference lists admits a stable matching with at
least $k$ ﬁrst choices, is NP-complete. To establish our result, we will show
that for a solvable instance $I$ with complete preference lists, $I$ admits a
stable matching $M$ where $p_{1}(M)\geq k$ if and only if $I$ admits a stable
partition $\Pi$ where $p_{1}(\Pi)\geq 2k$.

Suppose that $I$ admits a stable matching
$M=\\{\\{a_{i_{1}},a_{i_{2}}\\}\dots\\{a_{i_{n-1}},a_{i_{n}}\\}\\}$ with at
least $k$ ﬁrst choices, i.e. at least $k$ agents are assigned a partner that
is ranked first in their preference list. Then, immediately, $M$ has an
associated stable partition
$\Pi=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{n-1}}\;a_{i_{n}})$, in which at least
$k$ agents have a successor that is their first-choice. As all cycles are
transpositions, their predecessors are also their successors, so in the
associated profile $p(\Pi)$, we will have $p_{1}(\Pi)\geq 2k$ as desired.

For the other direction, suppose that $I$ admits a stable partition $\Pi$ with
at least $2k$ first choices in $p(\Pi)$. By Lemma 4.6 we can break down $\Pi$
into a reduced stable partition $\Pi^{\prime}$ if $\Pi$ is not reduced, such
that $p_{1}(\Pi^{\prime})\geq p_{1}(\Pi)\geq 2k$. Because we assume that $I$
is solvable, by Theorem 3.3, $\Pi^{\prime}$ corresponds to a stable matching
$M$ of $I$ and so $p_{1}(M)=\frac{p_{1}(\Pi^{\prime})}{2}\geq k$ as desired. ∎

######  Theorem 4.8.

Let $I$ be an sr instance and $k$ an integer. FC-Dec-SR-SP, the problem of
deciding whether $I$ admits a stable partition with at least $k$ first
choices, is NP-complete, even if $I$ is solvable and even if $I$ is
unsolvable.

###### Proof.

If $I$ is solvable, the result follows immediately from Lemma 4.7.

Now suppose that we can, in polynomial time, decide FC-Dec-SR-SP for an
unsolvable instance $I$. Then we could also solve the problem for solvable
instances, contradicting the above. Specifically, take any solvable instance
$I_{1}$ with $n$ agents and transform it to an unsolvable instance $I_{2}$ by
adding six agents $a_{n+1},\dots,a_{n+6}$ with preferences given in Example 6,
where $a_{n+i}=b_{i}$, such that they form two invariant three-cycles in any
stable partition without satisfying any first-choices. One can easily verify
the construction by checking that each agent prefers their successor over
their predecessor and no two agents prefer each other over their predecessors.
As the three-cycles are of odd length, they must be invariant. Finally,
$I_{2}$ is clearly unsolvable due to the new odd cycles, but any stable
partition $\Pi_{2}$ of $I_{2}$ corresponds to a stable partition
$\Pi_{1}=\Pi_{2}\setminus\\{(a_{n+1}\;a_{n+2}\;a_{n+3})(a_{n+4}\;a_{n+5}\;a_{n+6})\\}$
of $I_{1}$ and vice versa. Furthermore, $p_{1}(\Pi_{1})=p_{1}(\Pi_{2})$, so
some stable partition of $I_{1}$ satisfies at least $k$ first-choices if and
only if some stable partition of $I_{2}$ satisfies at least $k$ first-choices.
∎

$b_{1}$ | $b_{4}$ | $b_{2}$ | $b_{3}$ | …
---|---|---|---|---
$b_{2}$ | $b_{4}$ | $b_{3}$ | $b_{1}$ | …
$b_{3}$ | $b_{5}$ | $b_{1}$ | $b_{2}$ | …
$b_{4}$ | $b_{3}$ | $b_{5}$ | $b_{6}$ | …
$b_{5}$ | $b_{1}$ | $b_{6}$ | $b_{4}$ | …
$b_{6}$ | $b_{1}$ | $b_{4}$ | $b_{5}$ | …
Table 6: Added 3-cycles for first-choice maximal reduction

The hardness of finding rank-maximal stable partitions follows directly from
the previous result.

######  Theorem 4.9.

Rank-Dec-SR-SP is NP-complete, even if the given instance is solvable and even
if it is unsolvable.

###### Proof.

Note that Rank-Dec-SR-SP is in NP, as given an instance $I$, vector $\sigma$,
and partition $\Pi$, we can check whether $\Pi$ is a stable partition of $I$
and check whether $p(\Pi)\succeq\sigma$, all in linear time.

We showed above in Theorem 4.8 that FC-Dec-SR-SP is NP-complete for solvable
and for unsolvable instances. Now given a problem instance $(I,k)$ to FC-Dec-
SR-SP, $(I,k)$ is a yes-instance if and only if $(I,(k\;0\dots 0))$ is a yes-
instance to Rank-Dec-SR-SP. ∎

A similar result holds for regret-minimal stable partitions.

First, the following Lemma establishes that no non-reduced minimum-regret
stable partition with regret $r$ satisfies less $r$th choices than any reduced
minimum-regret stable partition with minimal $r$th choices satisfied.

######  Lemma 4.10.

Let $C=(a_{i_{1}}\;a_{i_{2}}\dots a_{i_{k}})$ be an even cycle with profile
$p$ and regret $r$ of some instance $I$ with $n$ agents. Then both
$C_{1}=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{k-1}}\;a_{i_{k}})$ and
$C_{2}=(a_{i_{1}}\;a_{i_{k}})\dots(a_{i_{k-2}}\;a_{i_{k-1}})$ are stable and
either $p_{r}(C_{1})\leq p_{r}(C)$ and $p_{j}(C_{1})=0$ for all $r<j\leq n$ or
$p_{r}(C_{2})\leq p_{r}(C)$ and $p_{j}(C_{2})=0$ for all $r<j\leq n$.

###### Proof.

By Lemma 3.6, both $C_{1}$ and $C_{2}$ are stable. Now for any $a_{i_{j}}\in
C$, we know $C(a_{i_{j}})\succ_{i_{j}}C^{-1}(a_{i_{j}})$ by stability
condition T1 and the fact that $C$ is longer than a transposition, therefore
proving strict inequality. Thus, any agent $a_{i_{j}}$ that gets their $r$th
choice in $C$ must rank their successor better than $r$. Therefore, any such
agent $a_{i_{j}}$ contributes exactly 1 to $p_{r}(C)$. Now if we break $C$
into transpositions, an agent $a_{i_{j}}$ who is paired with their $r$th
choice predecessor now has them also as their successor, thus adding 2 to
either $p_{r}(C_{1})$ or $p_{r}(C_{2})$. Clearly,
$p_{j}(C_{1})=p_{j}(C_{2})=0$ for all $r<j\leq n$ is true, as everyone gets a
partner in $C_{1},C_{2}$ no worse than their predecessor in $C$. Now for any
two agents $a_{i_{l}},a_{i_{m}}$ that get their $r$th choice predecessor in
$C$ and have an even number of agents between them, one will get their $r$th
choice assigned in $C_{1}$ and one in $C_{2}$. For any two such agents that
have an odd number of agents between them will both get their $r$th choice
assigned in either $C_{1}$ or $C_{2}$. Hence, the result follows. ∎

This, again, lets us consider reduced partitions and use existing complexity
results.

######  Lemma 4.11.

RM-Dec-SR-SP is NP-complete, even if the given instance is solvable.

###### Proof.

Note that RM-Dec-SR-SP is in NP, as given instance $I$ with minimum regret
$r$, integer $k$, and partition $\Pi$, we can check whether $\Pi$ is a minimum
regret stable partition of $I$ and verify that it assigns at most $k$ $r$th
choices, all in linear time.

[13] proved that RM-Dec-SR-SM, the problem of deciding whether a solvable sr
instance $I$ admits a stable matching with at most $k$ $r$th-choices and 0
choices higher than $r$, is NP-complete. Note that this is equivalent to
saying that the problem of deciding whether $I$ admits a minimum-regret stable
matching with at most $k$ $r$th choices is NP-complete. To establish our
result, we will show that for an instance $I$ with complete preference lists,
$I$ admits a minimum-regret stable matching $M$ with at most $k$ $r$th choices
in $p(M)$ if and only if $I$ admits a minimum-regret stable partition $\Pi$
with at most $2k$ $r$th choices in $p(\Pi)$.

Suppose that $I$ admits a minimum-regret stable matching
$M=\\{\\{a_{i_{1}},a_{i_{2}}\\}\dots\\{a_{i_{n-1}},a_{i_{n}}\\}\\}$ with at
most $k$ $r$th choices, i.e. at most $k$ agents are assigned a partner that is
ranked in the $r$th position of their preference list. Then, immediately, $M$
has an associated minimum-regret stable partition
$\Pi=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{n-1}}\;a_{i_{n}})$, in which at most
$k$ agents have a predecessor that is ranked in their $r$th position. As all
cycles are transpositions, their predecessors are also their successors, so in
the associated profile we will have $p_{r}(\Pi)\leq 2k$ as desired.

For the other direction, suppose $I$ admits a minimum-regret stable partition
$\Pi$ with $p_{r}(\Pi)\leq 2k$. By Lemma 4.10 we can furthermore suppose that
$\Pi$ is reduced, because if $\Pi$ is not reduced, then we can break its even
cycles into a stable collection of transpositions in a way that does not
increase the number or index of worst-choice assignments. Because we assume
that $I$ is solvable, by Lemma 4.2, $\Pi$ corresponds to a minimum regret
stable matching $M$ of $I$, and because all cycles in $\Pi$ are
transpositions, we know that $p_{r}(\Pi)=2p_{r}(M)$, as desired. ∎

######  Theorem 4.12.

Let $I$ be an sr instance with regret $r$ and let $k$ be an integer. RM-Dec-
SR-SP, the problem of deciding whether $I$ admits a minimum-regret stable
partition with at most $k$ $r$th cohices, is NP-complete, even if $I$ is
solvable and even if $I$ is unsolvable.

###### Proof.

If $I$ is solvable, the result follows immediately from Lemma 4.11.

If $I$ is unsolvable, we can use the same construction as in Theorem 4.8 to
show that NP-completeness follows from the solvable case. ∎

This immediately lets us establish hardness results for generous stable
partitions.

######  Theorem 4.13.

Gen-Dec-SR-SP is NP-complete, even if the given instance is solvable and even
if it is unsolvable.

###### Proof.

Note that Gen-Dec-SR-SP is in NP, as given an instance $I$, vector $\sigma$,
and partition $\Pi$, we can check that $\Pi$ is a stable partition of $I$ and
check that $\sigma^{rev}\succeq p^{rev}(\Pi)$, all in linear time.

We showed above in Theorem 4.12 that RM-Dec-SR-SP is NP-complete for solvable
and for unsolvable instances. Now given a problem instance $(I,k)$ to RM-Dec-
SR-SP, $(I,k)$ is a yes-instance if and only if $(I,\sigma)$ is a yes-instance
to Gen-Dec-SR-SP, where $r$ is the minimum regret of any stable partition of
$I$, $\sigma_{r}=k$, $\sigma_{i}=n$ for $i<r$ and $\sigma_{i}=0$ for $i>r$.

In this construction, both problems ask whether there exists a stable
partition $\Pi$ of $I$ where at most $k$ agents are assigned their $r$th
choice and no agent is assigned to anyone worse than their $r$th choice, as
any stable partition satisfies $p_{i}(\Pi)<\sigma_{i}$ for $i<r$, so the
result follows. ∎

Finally, we consider minimising the profile-based (egalitarian) cost of a
stable partition.

Again, the following lemma lets us reduce the search to reduced stable
partitions.

######  Lemma 4.14.

Let $C=(a_{i_{1}}\;a_{i_{2}}\dots a_{i_{k}})$ be an even cycle with cost
$c(C)$. Then both collections of transpositions
$C_{1}=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{k-1}}\;a_{i_{k}})$ and
$C_{2}=(a_{i_{1}}\;a_{i_{k}})\dots(a_{i_{k-2}}\;a_{i_{k-1}})$ are stable and
either $c(C_{1})\leq c(C)$ or $c(C_{2})\leq c(C)$.

###### Proof.

By Lemma 3.6, both $C_{1}$ and $C_{2}$ are stable. Now let $c_{1},c_{2}$ be
the costs of $C_{1},C_{2}$, respectively. Let
rank${}_{s}(C)=(sr_{1}\;sr_{2}\dots sr_{k})$ be the vector of successor ranks
for agents $i_{1}\dots i_{k}$, i.e., $sr_{j}$ is the rank of $C(a_{i_{j}})$ on
$a_{i_{j}}$’s preference list and define rank${}_{p}(C)$ the same for
predecessors. Then $c(C)=$ sum(rank${}_{s}(C)$ \+ rank${}_{p}(C)$), and
similarly for $C_{1},C_{2}$, by definition. However, by construction, we have
that rank${}_{s}(C_{1})=(sr_{1}\;pr_{2}\;sr_{3}\dots pr_{k})=$
rank${}_{p}(C_{1})$ and rank${}_{s}(C_{2})=(pr_{1}\;sr_{2}\;pr_{3}\dots
sr_{k})=$ rank${}_{p}(C_{2})$. Then $c_{1}+c_{2}=2c(C)$, so the result
follows. ∎

This helps us in establishing the intractability of the problem.

######  Lemma 4.15.

Egal-Dec-SR-SP is NP-complete, even if the given instance is solvable.

###### Proof.

Note that Egal-Dec-SR-SP is in NP, as given instance $I$, integer $k$, and
partition $\Pi$, we can check whether $\Pi$ is a stable partition of $I$ and
verify that it has cost at most $k$, all in linear time.

[17] proved that Egal-Dec-SR-SM, the problem of deciding whether $I$ admits a
stable matching with cost at most $k$, is NP-complete, even if $I$ is
solvable. To establish our result, we will show that for an instance $I$ with
complete preference lists, $I$ admits a stable matching $M$ with cost at most
$k$ if and only if $I$ admits a stable partition $\Pi$ with cost at most $k$.

By solvability of $I$ and Theorem 3.3, any stable matching
$M=\\{\\{a_{i_{1}},a_{i_{2}}\\}\dots\\{a_{i_{n-1}},a_{i_{n}}\\}\\}$
corresponds to a reduced stable partition
$\Pi=(a_{i_{1}}\;a_{i_{2}})\dots(a_{i_{n-1}}\;a_{i_{n}})$ and vice versa.
Furthermore, by definition of cost, $c(\Pi)=c(M)$. Also, by Lemma 4.14, there
is no gap in minimum cost between reduced stable partitions and non-reduced
stable partitions, and we know that we can turn any non-reduced stable
partition into a reduced stable partition without an increase in cost. Thus,
the result follows. ∎

######  Theorem 4.16.

Let $I$ be an sr instance and $k$ be an integer. Egal-Dec-SR-SP, the problem
of deciding whether $I$ admits a stable partition with egalitarian cost at
most $k$, is NP-complete, even if $I$ is solvable and even if $I$ is
unsolvable.

###### Proof.

If $I$ is solvable, the result follows immediately from Lemma 4.15.

If $I$ is unsolvable, we can use the same construction as in Theorem 4.8 to
show that NP-completeness follows from the solvable case, as the cost of the
added 3-cycles in the reduction is fixed and can be added onto the parameter
$k$. ∎

Note that all NP-hardness arguments above assume a solvable (sub)instance that
is computationally difficult in the considered context. However, the smaller
the sub-instance, the easier to compute an optimal solution, as there is no
choice involved in the odd cycles. In the extreme case, all agents are part of
odd cycles, which means that there exists a unique stable partition for the
instance which is automatically optimal regardless of the objective.

###  4.3 Approximability of the NP-hard Problems

After seeing how profile optimality transfers from matchings to partitions in
terms of computational complexity, we can similarly consider whether
approximation methods carry over. We have shown the NP-hardness of computing
egalitarian, first-choice maximal, rank-maximal, regret-minimal, and generous
stable partitions. However, there is no known measure of approximability for
rank-maximal or generous profiles even for stable matchings, so it is unclear
what an approximation could look like for stable partitions. We postpone this
for future work and focus on the first-choice maximal, and regret-minimal, and
egalitarian problems.

######  Theorem 4.17.

The problem of finding a first-choice maximal stable partition $\Pi$ of some
sr instance $I$ does not admit a polynomial-time approximation algorithm with
any constant-factor performance guarantee, even if $I$ is solvable and even if
$I$ is unsolvable, unless P$=$NP.

###### Proof.

[47] proved that there does not exist any constant factor approximation
algorithm for the first-choice maximal stable matching problem, unless P$=$NP.
Thus, for this proof, it suffices to show that if there was a polynomial-time
approximation algorithm for regret-minimal stable partitions with any constant
performance guarantee $c$, then we could also solve the respective stable
matching problem.

Indeed, let $I$ be any solvable sr instance and let $opt$ be the maximum
number of first choices achieved in any stable matching of $I$. We have
previously shown in Theorem 4.8 that $2opt$ is the maximum number of first
choices achieved in the profile of any stable partition of $I$ and that it can
be achieved by some reduced stable partition. Thus, if we could approximate a
first-choice maximal stable partition problem within $c$, then we could find a
reduced stable partition $\Pi$ with at least $\frac{2opt}{c}$ first choices in
the profile, corresponding to $\frac{opt}{c}$ first choices in the
corresponding stable matching profile, which is a contradiction to the fact
that there is no constant factor approximation algorithm for the stable
matching version of the problem.

Furthermore, if we had a $c$-approximation algorithm for unsolvable instances,
then we could transform any solvable instance $I$ with $n$ agents into an
unsolvable one by adding two forced odd cycles
$(a_{n+1}\;a_{n+2}\;a_{n+3})(a_{n+4}\;a_{n+5}\;a_{n+6})$ similar to the proof
of Theorem 4.8 using the preference list construction from Example 6, where
$a_{n+i}=b_{i}$. Clearly, the preferences admit the desired 3-cycles as
stability conditions T1 and T2 are satisfied. Furthermore, as the cycles are
of odd length, we can immediately conclude that they are unique, and must thus
be part of any stable partition. The cycles do not satisfy any additional
first choices which could affect the correctness of the reduction to prove the
inapproximability of first-choice maximal stable partitions of unsolvable
instances within any constant factor. ∎

For the other problems, we can use some known results about approximating
special stable matchings.

######  Definition 4.18.

Let $I$ be an instance of sr. Then a matching $M$ is a solution to the Optimal
sr problem if $M$ is a solution to the sr problem and $\sum_{a_{i}\in
A_{M}}c_{i}(M(a_{i}))$ is minimal, where $A_{M}$ is the set of agents matched
in $M$ and $c_{i}(a_{j})$ is the (real-valued) cost of being matched to
$a_{j}$ from $a_{i}$’s point of view.

[51] showed that if the cost function furthermore satisfies that for each
agent $a_{k}$ with complete ordinal preferences
$a_{k_{1}}\succ_{k}\dots\succ_{k}a_{k_{n-1}}$, there exists an agent
$a_{k_{l}}$ such that $c_{k}(a_{k_{m-1}})\geq c_{k}(a_{k_{m}})$ for all
$1<m\leq l$ and $c_{k}(a_{k_{m^{\prime}}})\leq c_{k}(a_{k_{m^{\prime}+1}})$
for all $l\leq m^{\prime}<n-1$, then Optimal sr is approximable within a
factor of 2 using an integer programming approach computable in polynomial
time.

Note that for first-choice maximal stable partitions, it is not possible to
apply this approximation method, as there is no suitable cost function that
satisfies the additional criteria. However, [47] previously showed how the
2-approximation of Optimal sr can be used to approximate regret-minimal stable
matchings, and we showed that this is also true for stable partitions.

######  Theorem 4.19.

The problem of finding a regret-minimal stable partition $\Pi$ of some sr
instance $I$ admits a polynomial-time approximation algorithm with a
performance guarantee of 2.

###### Proof.

Again, we know that because all odd cycles are invariant and can be found in
polynomial time, we show that we can 2-approximate the even cycles, which
actually gives an overall performance guarantee significantly better than 2 if
the number of agents in odd cycles is large compared to the number of agents
in the instance.

Let $\Pi_{p}$ be a minimum regret stable partition of $I$ with profile $p$,
which always exists and we have shown to be computable in linear time, and let
$r$ be the minimum regret. If $r=1$ or $p_{r}=p_{r}|_{\mathcal{O}_{I}}$, i.e.
all profile entries at position $r$ are caused by half-matchings in odd
cycles, there is no variability and we found an optimal solution. Otherwise,
we showed that $\Pi_{p}=M^{\prime}\mathcal{O}_{I}$ for a minimum-regret stable
matching $M$ of $I_{P}$ with dummy agents removed. Some match in $M$ causes an
entry at position $r$ in the profile of $\Pi$, none of which can be with a
dummy agent as they are all matched to each other and rank their match first
in their preference list. We define the cost function

$c_{i}(a_{j})=\begin{cases}1&\text{rank}_{i}(a_{j})\geq r\\\
0&\text{otherwise}.\end{cases}$

Then, $c$ satisfies the condition by [51] as preference lists correspond to a
cost sequence $0,\dots,0,1,\dots,1$ with $r-1$ zeros and $n-r$ ones.
Furthermore, as we know that every agent in $S_{P}$ can be matched to some
other agent of rank at least as good as $r$, we can truncate the preference
lists of every agent at rank $r+1$. Then $\sum_{a_{i}\in
A_{M}}c_{i}(M(a_{i}))$ is exactly the number of agents in $I_{P}$ that are
matched to their $r$th choice. Now, let $\Pi_{opt}$ be an optimal stable
partition, then we can apply the 2-approximation algorithm for Optimal SR with
cost function $c$ to $S_{P}$ to get a matching $M^{\prime\prime}$ with dummy
agents removed such that
$p_{r}(M^{\prime\prime}\mathcal{O}_{I})=p_{r}(M^{\prime\prime})+p_{r}(\mathcal{O}_{I})\leq
2(p_{r}(M_{opt})+p_{r}(\mathcal{O}_{I}))=2p_{r}(\Pi_{opt})$ as desired. ∎

Similarly, we showed that there also exists a suitable cost function to
approximate egalitarian stable partitions using this method.

######  Theorem 4.20.

The problem of finding an egalitarian stable partition $\Pi$ of some sr
instance $I$ admits a polynomial-time approximation algorithm with a
performance guarantee of 2.

###### Proof.

We will show that we can define a suitable cost function $c$ such that when
applying the 2-approximation algorithm to the Optimal SR problem to the
solvable instance $I_{P}$ derived from $I$ by the padding method, we find a
solution to the egalitarian stable partition problem with a performance
guarantee of 2. Even more, we know that because all odd cycles are invariant
and can be found in polynomial time, we show that we can 2-approximate the
even cycles, which actually gives an overall performance guarantee
significantly better than 2 if the number of agents in odd cycles is large
compared to the number of agents in the instance. Indeed, the natural cost
function $c_{i}(a_{j})=$ rank${}_{i}(a_{j})$ works to approximate an
egalitarian stable matching within 2, as $c_{k}(a_{k_{i}})$ is strictly
increasing for $i$ from 1 to $n-1$. Also, the solution $M$ will satisfy
$\sum_{a_{i}\in A_{M}}c_{i}(M(a_{i}))=c(M)$ minimal as desired.

Now we want to show that $\Pi=M\mathcal{O}_{I}$, where $M$ is a
2-approximation of an egalitarian stable matching of $I_{P}$ with dummy agents
removed and $\mathcal{O}_{I}$ are the invariant odd cycles of $I$, is a
2-approximation of an optimal egalitarian stable partition
$\Pi_{opt}=M^{\prime}\mathcal{O}_{I}$ of $I$, where $M^{\prime}$ is an
egalitarian stable matching of $I_{P}$ as previously shown. Recall that
$c(\Pi)=\frac{1}{2}\sum_{1\leq
i<n}p_{i}*i=\frac{1}{2}\sum_{a_{i}}(\text{rank}_{i}(\Pi(a_{i}))+\text{rank}_{i}(\Pi^{-1}(a_{i})))$.
Thus, $c(\Pi)=c(M)+c(\mathcal{O}_{I})$ and similarly for $c(\Pi_{opt})$, such
that $c(\Pi)>2c(\Pi_{opt})$ implies $c(M)>2c(M^{\prime})$, a contradiction.
Therefore, the method gives a 2-approximation for the egalitarian stable
partition problem and can be computed in polynomial time. ∎

These results are consistent with the approximability results of stable
partitions, which fits the theme of compatibility and close correspondence
throughout this research.

##  5 Discussion and Open Problems

In this paper, we have shown various new insights into the structure of stable
partitions. Specifically, that there is a close correspondence between reduced
stable partitions of unsolvable instances and stable matchings of certain
solvable sub-instances, how even cycles can be constructed from transpositions
and partial cycles, with the highlight being a result proving that a
predecessor-successor pair is sufficient to find the unique stable cycle of
even length larger than 2 (if one exists). Using these insights, we also
provided the first algorithms to efficiently enumerate all reduced and non-
reduced stable cycles and partitions of a given problem instance, which could
be useful for a variety of cases. Furthermore, we showed how the stable
matching notions of profile- and cost-optimality carry over to stable
partitions and which of the problems are efficiently computable. Although we
assumed complete preference lists throughout this work, the same results and
algorithms should apply to sri instances (sr instances with incomplete lists).
This bridges the gap between stable matchings, which do not always exist, and
fractional matchings, which always exist but may not be useful in certain
practical applications.

For a comparative overview of the complexity results previously known and
newly established, see Table 7. There, we consider maximum welfare stable
fractional matchings as egalitarian for consistency. With regards to
approximation bounds for the optimisation versions of the NP-complete decision
problem variants above, Table 8 compares the existing results for stable
matchings to the new results for stable partitions presented here.

| M | SP | FM
---|---|---|---
Always Exists | No | Yes | Yes
Find Any (if exists) |  $O(n^{2})$ [27] |  $O(n^{2})$ [48] |  $O(n^{2})$ [9]
Find $SP(I)$/$SC(I)$ |  $O(n^{3})$ [18] |  $O(n_{1}^{2}(n^{2}+n_{1}))$ (Thm 3.18) |
Find $FP(I)$/$FC(I)$ |  $O(n^{2})$ [25] |  $O(n^{2})$ (Thm 3.15) |
Find $S(I)$/$RP(I)$ |  $O(|S(I)|n+n^{2})$ [18] |  $O(|S(I_{T})|n+n^{2})$ (Thm 3.5) |
Find $P(I)$ |  |  $O((|P(I)|+n_{1})n_{1}n^{2}+n_{1}^{3})$ (Thm 3.19) |
Min Regret |  $O(n^{2})$ [25] |  $O(n^{2})$ (Thm 4.4) |
Egalitarian |  NP-hard [17] | NP-hard (Thm 4.16) |  NP-hard [9]
First-Choice Max |  NP-hard [13] | NP-hard (Thm 4.8) |
Rank-Max |  NP-hard [13] | NP-hard (Thm 4.9) |
Regret-Min |  NP-hard [13] | NP-hard (Thm 4.12) |
Generous |  NP-hard [13] | NP-hard (Thm 4.13) |
Table 7: Complexity classification of different sr problems related to Stable Matchings (M), Stable Partitions (SP), and Fractional Matchings (FM) under ordinal stability. Contributions in colour. Not applicable or not a natural problem to study in gray. $n$ is the number of agents in the instance, $n_{1}$ of which are not in invariant odd cycles. | Stable Matching | Stable Partition
---|---|---
Egalitarian |  2-approximable [18] | 2-approximable (Thm 4.20)
Regret-Min |  2-approximable [47] | 2-approximable (Thm 4.19)
First-Choice Max |  Not approx within any $c\in\mathbb{R}$ [47] | Not approx within any $c\in\mathbb{R}$ (Thm 4.17)
Table 8: Approximation Results for Different sr Problems. Contributions in
color.

Overall, we have shown a close correspondence between stable matchings and
stable partitions in every way, from instance and solution structure to the
computational complexity and approximability of problem variants. However,
there are still many open problems related to stable partitions and other
topics of this paper. One direction for future work is to improve on the
complexity results presented here, for example by investigating whether a
technique similar to the 2-sat reduction by [18] in the enumeration of $SP(I)$
and $S(I)$ can speed up the enumeration of $SC(I)$ and $P(I)$. One could also
explore stable fractional matchings more, looking into fast enumeration of
such matchings and partnerships, or adapting optimality criteria similar to
the ones formulated here. Currently, it is not clear what a suitable
definition for an approximation ratio could look like for the rank-maximal-
and generous-profile problems, neither for matchings nor for partitions. There
might also be a closer relationship than currently discovered between stable
partitions and approximate or exact solutions to computationally difficult
problems such as the almost-stable matching problem, where some results
presented here might help. Finally, it could be investigated how stable
partitions can be useful in the presence of ties in the preference lists, for
example in approximating large weakly stable matchings.

## References

  * [1] http://www.paireddonationnetwork.org (Paired Donation Network website)
  * [2] http://www.organdonation.nhs.uk (Organ Donation and Transplantation Directorate, NHS Blood and Transplant website).
  * [3] David J. Abraham, Péter Biro and David Manlove  “”Almost stable” matchings in the roommates problem”  In _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ 3879 LNCS Springer Verlag, pp. 1–14  DOI: 10.1007/11671411˙1/COVER
  * [4] Elliot Anshelevich, Sanmay Das and Yonatan Naamad  “Anarchy, stability, and utopia: Creating better matchings”  In _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ 5814 LNCS Springer, Berlin, Heidelberg, 2009, pp. 159–170  DOI: 10.1007/978-3-642-04645-2˙15/COVER
  * [5] Péter Biró, Katarína Cechlárová and Tamás Fleiner  “The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems”  In _International Journal of Game Theory_ 36 Springer, 2008  DOI: 10.1007/S00182-007-0084-3/METRICS
  * [6] Péter Biró, Walter Kern, Daniël Paulusma and Péter Wojuteczky  “The stable fixtures problem with payments”  In _Games and Economic Behavior_ 108 Academic Press, 2018, pp. 245–268  DOI: 10.1016/J.GEB.2017.02.002
  * [7] Péter Biró, David Manlove and Eric J. McDermid  ““Almost stable” matchings in the Roommates problem with bounded preference lists”  In _Theoretical Computer Science_ 432 Elsevier, 2012, pp. 10–20  DOI: 10.1016/J.TCS.2012.01.022
  * [8] Viera Borbel’ová and Katarína Cechlárová  “Rotations in the stable b-matching problem”  In _Theoretical Computer Science_ 411 Elsevier, 2010, pp. 1750–1762  DOI: 10.1016/J.TCS.2010.01.017
  * [9] Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos and Rohit Vaish  “Stable fractional matchings”  In _ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation_ Association for Computing Machinery, Inc, 2019, pp. 21–39  DOI: 10.1145/3328526.3329637
  * [10] Katarína Cechlárová and Tamás Fleiner  “On a generalization of the stable roommates problem”  In _ACM Transactions on Algorithms (TALG)_ 1 ACM PUB27 New York, NY, USA, 2005, pp. 143–156  DOI: 10.1145/1077464.1077474
  * [11] Jiehua Chen, Danny Hermelin, Manuel Sorge and Harel Yedidsion  “How hard is it to satisfy (almost) all roommates?”  In _Leibniz International Proceedings in Informatics, LIPIcs_ 107 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017  DOI: 10.4230/LIPIcs.ICALP.2018.35
  * [12] Jiehua Chen, Sanjukta Roy and Manuel Sorge  “Fractional Matchings under Preferences: Stability and Optimality”  In _IJCAI International Joint Conference on Artificial Intelligence_ 1 International Joint Conferences on Artificial Intelligence, 2021, pp. 89–95  DOI: 10.24963/IJCAI.2021/13
  * [13] Frances Cooper  “Fair and large stable matchings in the stable marriage and student-project allocation problems”, 2020