Stable Marriage with Multi-Modal Preferences∗

arXiv:1801.02693v1 [cs.MA] 8 Jan 2018

Jiehua Chen†
Ben-Gurion University of the Negev
Beer-Sheva, Israel

Rolf Niedermeier
TU Berlin
Berlin, Germany

Piotr Skowron‡
TU Berlin
Berlin, Germany

Abstract
We introduce a generalized version of the famous S TABLE M ARRIAGE problem, now based on multimodal preference lists. The central twist herein is to allow each agent to rank its potentially matching
counterparts based on more than one “evaluation mode” (e.g., more than one criterion); thus, each agent
is equipped with multiple preference lists, each ranking the counterparts in a possibly different way. We
introduce and study three natural concepts of stability, investigate their mutual relations and focus on
computational complexity aspects with respect to computing stable matchings in these new scenarios.
Mostly encountering computational hardness (NP-hardness), we can also spot few islands of tractability
and make a surprising connection to the G RAPH I SOMORPHISM problem.
Keywords: Stable matching, concepts of stability, multi-layer (graph) models, NP-hardness, parameterized complexity analysis, exact algorithms.

1 Introduction
Information about the same “phenomenon” can come from different, possibly “contradicting”, sources. For
instance, when evaluating candidates for an open position, data concerning experience and so far achieved
successes of the candidates may give different candidate rankings than data concerning their formal qualifications and degrees. In other words, one has to deal with a multi-modal data scenario. Clearly, in maximally
objective and rationality-driven decision making, it makes sense to take into account several information
resources in order to achieve best possible results. In this work we systematically apply this point of view
to the S TABLE M ARRIAGE problem [25]; a key observation here is that several natural and well-motivated
“multi-modal variants” of S TABLE M ARRIAGE need to be studied. We investigate the complexity of computing matchings that are stable according to the considered definitions.
In the classic (conservative) S TABLE M ARRIAGE problem [25], we are given two disjoint sets U and W
of n agents each, where each of the agents has a strict preference list that ranks every member of the other
set. The goal is to find a bijection (which we call a matching) between U and W without any blocking pair
which can endanger the stability of the matching. A pair of agents is blocking a matching if they are not
matched to each other but rank each other higher than their respective partners in the matching.
∗

Work started when all authors were with TU Berlin.
Supported by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme
(FP7/2007-2013) under REA grant agreement number 631163.11, and by the Israel Science Foundation (grant number 551145/14).
‡
Supported by a postdoctoral fellowship of the Alexander von Humboldt Foundation, Bonn, Germany.
†

1

Gale and Shapley [25] introduced the S TABLE M ARRIAGE problem in the fields of Economics and
Computer Science in the 1960s. One of their central results was that every S TABLE M ARRIAGE instance
with 2n agents admits a stable matching, which can be found by their algorithm in O(n2 ) time. Since
then S TABLE M ARRIAGE has been intensively studied in Economics, Computer Science, and Social and
Political Science [1, 27, 29, 30, 35, 37, 39]. Practical applications of S TABLE M ARRIAGE (and its variants)
include partnership issues in various real-world scenarios, matching graduating medical students (so-called
residents) with hospitals, students with schools, and organ donors with patients [27, 35, 39], and the design
of content delivery systems [36] and other distributed markets [45].
The original model of S TABLE M ARRIAGE assumes, roughly speaking, that there is a (subjective) criterion and that each agent has a single preference list depending on this criterion. In typically complex
real-world scenarios, however, there are usually multiple aspects one takes into account when making a decision. For instance, if we consider the classical partnership scenario, then there could be different criteria
such as working hours, family background, physical appearance, health, hobbies, etc. In other words, we
face a much more complex multi-modal scenario. Accordingly, the agents may have multiple preference
lists, each defined by a different criterion; we call each of these criteria a layer. For an illustration, let us
consider the following stable marriage example with two sets of two agents each, denoted as u1 , u2 , w1 ,
and w2 , and three layers of preferences, denoted as P1 , P2 , and P3 .
w1 w1
w2 w2
w1 w2
w2 w2
w1 w1
w2 w1
u1
u2
u1
u2
u1
u2

P1 :

w1
u1
u2

w2
u1
u2

P2 :

w1
u1
u2

w2
u1
u2

P3 :

w1
u2
u1

w2
u1
u2

In the above diagram the preferences are depicted right above (respectively, right below) the corresponding
agents; preferences are represented through vertical lists where more preferred agents are put above the less
preferred ones. For example, in the first layer, all agents from the same set have the same preference list,
i.e. both u1 and u2 rank w1 higher than w2 while both w1 and w2 rank u1 higher than u2 . Similarly, in
the second layer, both u1 and u2 rank w2 higher than w1 while both w1 and w2 rank u1 higher than u2 . In
the last layer, the preference lists of two agents from the same set are reverse to each other. For instance,
u1 ranks w1 higher than w2 , which is opposite to u2 . In terms of the classic stable marriage problem, we
will have three independent instances, one for each layer. The corresponding stable matching(s) for each
instance are depicted through the edges between the agents. For instance, the first layer admits exactly one
stable matching, which matches u1 with w1 , and u2 with w2 . Yet, if we want to take all these layers jointly
into account, then we need to extend the traditional concept of stability.
With multiple preference lists for each agent, there are many natural ways to extend the original stability
concept. We propose three naturally emerging concepts of stability. Assume each agent has ℓ (possibly
different) preferences lists. All three concepts are defined for a certain threshold α with 1 ≤ α ≤ ℓ, which
quantifies “the strength” of stability. In the following, we briefly describe our three concepts and defer the
formal definitions to Section 2.
- The first one, called α-layer global stability, extends the original stability concept in a straightforward
way. It assumes that the matched pairs agree on a set S of α layers where no unmatched pair is blocking
the matching in any layer from S.
In our introductory example, the matching M1 = {{u1 , w1 }, {u2 , w2 }} is stable in the first and the last
layer, and thus it is a 2-layer globally stable matching.

2

- The second one, called α-layer pair stability, changes the “blocking ability” of the unmatched pairs. It
forbids an unmatched pair to block more than ℓ − α layers. In other words, each pair of matched agents
needs to be stable in some α layers, but the choice of these layers can be different for different pairs.
Considering again our running example, we can verify that the 2-layer globally stable matching M1 is also
2-layer pair stable as each unmatched pair is blocking at most one layer. Indeed, we will see that α-layer
pair stability is strictly weaker than α-layer global stability (Proposition 3.1 and Example 3.1).
- The last one, called α-layer individual stability, focuses on the “willingness” of an agent to stay with its
partner. It requires that for each unmatched pair, at least one of the agents prefers to stay with its partner
in at least α layers.
In our introductory example, the matching M1 is also 2-layer individually stable. Thus, it is tempting
to assume that α-layer individual stability also generalizes α-layer global stability. This is, however,
not true as the following matching M2 = {{u1 , w2 }, {u2 , w1 }} is 2-layer globally stable but not 2layer individually stable. Neither does the latter implies the former. We refer to Example 3.2 for more
explanations.

1.1 Related work
While we are not aware of research on an arbitrary number ℓ of layers, there is some work on ℓ = 2 layers.
Weems [48] considered the case where each agent has two preference lists that are the reverse of each other.
He provided a polynomial-time algorithm to find a bistable matching, i.e. a matching that is stable in both
layers. Thus, while his concept falls into our α-layer global stability concept for α = ℓ = 2, it is a special
case since the preference lists in the two layers are the reverse of each other. In fact, for α = ℓ = 2, we
show that the complexity of determining α-layer global stability is NP-hard.
Aggregating the preference lists of multiple layers into one (by comparing each pair of agents) and
then searching for a “stable” matching for the agents with aggregated preferences is a plausible approach
to multi-modal stable marriages. As already noted by Farczadi et al. [23], the aggregated preferences may
be intransitive or even cyclic. Addressing this situation, they consider a generalized variant of S TABLE
M ARRIAGE, where each agent u of one side, say U , has a strict preference list ≻u (as in the original
S TABLE M ARRIAGE) while each agent w of the other side, say W , may order each possible pair of partners
separately, expressed by a subset Bw ⊆ U × U of ordered pairs. They defined a matching M to be stable
if no unmatched pair {u, w} satisfies “w ≻u M (u) and (u, M (u)) ∈ Bw ”. It turns out that our concept of
individual stability and their concept for a more generalized case where both sides of the agents may have
intransitive preferences are related, and we can use one of their results as a subroutine. In a way, our analysis
provides a more fine-grained view, since we consider a richer model and thus are able to discuss how certain
assumptions on elements of this model (e.g., the number of layers, the threshold value α, etc.) affect the
computational complexity of the problem.
Aziz et al. [2] considered a variant of S TABLE M ARRIAGE, where each agent has a probability for each
ordered pair of potential partners. Assigning a probability of 1 to either (x, y) or (y, x) for each x and y,
their variant is closely related to the one of Farczadi et al. [23] and is shown to be NP-hard.
We refer to several expositions [35, 27, 31, 39, 33, 7] for a broader overview on S TABLE M ARRIAGE
and related problems.

1.2 Our contributions
We introduce three main concepts of stability for S TABLE M ARRIAGE with multi-modal preferences. In
Section 2 we formally define these concepts, global stability, pair stability, and individual stability, and
provide motivating and illustrating examples. In Section 3, we study the relations between the three concepts

3

Table 1: The computational complexity of finding matchings stable according to the three consideerd
definitions—α-layer global stability, α-layer pair stability, and α-layer individual stability—for instances
with 2n agents and ℓ layers. All results hold for each value of α specified in the first column. Results
marked with ∗ hold even if we assume that each agent of one side has the same preference list in all layers.
The NP-hardness results hold even for a fixed number of layers.
Parameters

global stability

pair stability

individual stability

Arbitrary
1=α
2≤α=ℓ
⌊ℓ/2⌋ < α < ℓ
2 ≤ α ≤ ⌊ℓ/2⌋

O(n2 ) [25]
NP-h [T. 4.2+P. 4.4]
NP-h [P. 5.1]
NP-h [P. 5.1]

O(n2 ) [25]
NP-h [C. 4.3+P. 4.4]
NP-h [P. 5.4+P. 5.5]
NP-h∗ [C. 5.3]

O(n2 ) [25]
O(ℓ · n2 ) [T. 4.1]
?
NP-h∗ [T. 5.2]

NP-h for unbounded α [T. 6.2]
W[1]-h & in XP for α [T. 6.2]

NP-h∗ when 2 ≤ α ≤ ⌊ℓ/2⌋ [C. 5.3]
O(ℓ · n2 ) when α > ⌊ℓ/2⌋ [P. 6.3]

NP-h∗ when 2 ≤ α ≤ ⌊ℓ/2⌋ [T. 5.2]
O(ℓ · n2 ) when α > ⌊ℓ/2⌋ [P. 6.3]

O(ℓ · n) [P. 6.7]
O(ℓ · n) [P. 6.7]

?
?

nO(log (n)) + O(ℓ · n2 ) [C. 6.6]
G RAPH I SOM .-hard [T. 6.5]

Single-layered

Uniform
α ≥ ℓ/2 + 1
α = ℓ/2

and show that pair stability is the least restrictive form while global and individual stability are in general
incomparable (also see Figure 1 for a much refined picture). In Section 4, we consider the special case
of all-layers stability (α = ℓ) for the three concepts. On the one hand, we provide a polynomial-time
algorithm for checking individual stability for arbitrary large number of preference lists. On the other hand,
through an involved construction, we show NP-hardness for the other two stability concepts, even if there
are only two layers. The hardness results demonstrate a complexity dichotomy for both global and pair
stability since for single-layer preference lists, all three concepts of stability are the same and polynomialtime computable. In Section 5 we investigate the case of finding stable matchings with respect to less than
all layers and only find NP-hardness results. In Section 6, we identify two special scenarios with strong but
natural restrictions on the preference lists. For the fist scenario we assume that one side of the agents has
single-layered preferences, i.e. on one side the preference list of each agent remains the same in all layers.
We find that under such restrictions two out of three studied concepts are equivalent, and can be computed in
polynomial time; for global stability we obtain W[1]-hardness (and also NP-hardness) and XP membership
for the threshold parameter α. In the second scenario, we assume that the preferences of all agents on each
side are uniform in each layer, i.e. when for each fixed layer and side all agents have the same preference
list, and when considering individual stability we find surprising tight connections to the complexity of the
G RAPH I SOMORPHISM problem. Table 1 gives a broad overview on our complexity results.

2 Definitions and Notations
For each natural number t by [t] we denote the set {1, 2, . . . , t}.
Let U = {u1 , . . . , un } and W = {w1 , . . . , wn } be two n-element disjoint sets of agents. There are ℓ lay(i)
ers of preferences, where ℓ is a non-negative integer. For each i ∈ [ℓ] and each u ∈ U , let ≻u be a linear
order on W that represents the ranking of agent u over all agents from W in layer i. Analogously, for each
(i)
i ∈ [ℓ] and each w ∈ W , the symbol ≻w represents a linear order on U that encodes preferences of w
in layer i. We refer to such linear orders as preference lists. A preference profile Pi of layer i ∈ [ℓ] is a
(i)
collection of preference lists of all the agents in layer i, {≻a | a ∈ U ∪ W }.
Let U ⋆ W = {{u, w} | u ∈ U ∧ w ∈ W }. A matching M ⊆ U ⋆ W is a set of pairwisely disjoint
pairs, i.e. for each two pairs p, p′ ∈ M it holds that p ∩ p′ = ∅. If {u, w} ∈ M , then we also use M (u) to
4

refer to w and M (w) to refer to u, and we say that u and w are their respective partners under M ; otherwise
we say that {u, w} is an unmatched pair. Example 2.1 below shows an example matching and introduces a
graphical notation that we will use throughout the paper.
Example 2.1. Consider two sets of agents, U = {u1 , u2 , u3 } and W = {w1 , w2 , w3 }, and two layers of
preference profiles, P1 and P2 . Let us recall that in the following diagram the preferences are represented
through vertical lists where more preferred agents are put above the less preferred ones. For instance, in the
(1)
(1)
diagram the preference list of agent u3 in the first layer (profile P1 ) is w2 ≻u3 w3 ≻u3 w1 .
w3 w1 w2
w2 w3 w1
w2 w2 w3
w3 w1 w2
w1 w3 w1
w1 w2 w3
u1
u2
u3
u1
u2
u3

P1 :

w1
u2
u3
u1

w2
u3
u1
u2

P2 :

w3
u3
u1
u2

w1
u1
u2
u3

w2
u2
u3
u1

w3
u3
u1
u2

In our diagrams we will depict stable matchings in each layer through edges between matched nodes. If a
layer has more than one stable matching, then we will use different types of lines (solid, dashed, dotted)
and different colors to distinguish between them. For instance, in the above example profile P1 has one
stable matching M1 = {{u1 , w3 }, {u2 , w1 }, {u3 , w2 }}, and P2 has three stable matchings: (1) M2 =
⋄
{{u1 , w1 }, {u2 , w2 }, {u3 , w3 }}, (2) M3 = {{u1 , w2 }, {u2 , w3 }, {u3 , w1 }}, and (3) M1 .
Let us now introduce two notions that we will use when defining various concepts of stability.
Definition 2.1 (Dominating pairs and blocking pairs). Let M be a matching over U ∪ W . Consider an
unmatched pair {u, w} ∈ (U ⋆ W ) \ M and a layer i ∈ [ℓ]. We say that {u, w} dominates {u, v} in layer i
(i)
if w ≻u v. We say that {u, w} is blocking matching M in layer i if it holds that
(1) u is unmatched in M or {u, w} dominates {u, M (u)} in layer i, and
(2) w is unmatched in M or {u, w} dominates {w, M (w)} in layer i.
For a single layer i, a matching M is stable in layer i if no unmatched pair is blocking M in layer i. Let us
illustrate the concept of dominating and blocking pairs through Example 2.1. Consider the matching M3 =
{{u1 , w2 }, {u2 , w3 }, {u3 , w1 }} and profile P1 of layer 1. Here, pair {u1 , w3 } dominates both {u1 , w2 }
(since u1 prefers w3 to w2 ) and {u2 , w3 } (since w3 prefers u1 to u2 ). Thus, {u1 , w3 } is a blocking pair and
so it witnesses that M is not stable in profile P1 .
We are interested in matchings which are stable in multiple layers, i.e. we aim at generalizing the classic
S TABLE M ARRIAGE problem [25, 35, 27, 39] which is defined for a single layer to the case of multiple
layers. The idea behind each of the concepts defined below is similar: in order to call a matching stable for
multiple layers we require that it must be stable in at least a certain, given number of layers α (α is a number
indicating the “strength” of the stability). However, for different concepts we require a different level of
agreement with respect to which layers are required for stability. Informally speaking, on the one end of
the spectrum we have a variant of stability where we require a global agreement of the agents regarding the
set of α layers for which the matching must be stable. On the other end of the spectrum we have a variant
where we assume that the agents act independently: an agent a would deviate if it would find another agent,
say b, such that a prefers b to its matched partner in some α layers, and b prefers a to its matched partner
in another, possibly different, set of α layers. In the intermediate case, we require that a deviating pair must
agree on the subset of layers which form the reason for deviation. We formally define the three concepts
below.

5

2.1 α-layer global stability
Informally speaking, a matching M is α-layer globally stable if there exist α layers in each of which M is
stable.
Definition 2.2 (global stability). A matching M is α-layer globally stable if there exists a set S ⊆ [ℓ] of
α layers, such that for each layer i ∈ S and for each unmatched pair {u, w} ∈ U ⋆ W \ M at least one of
the two following conditions holds:
(1) pair {u, M (u)} dominates {u, w} in layer i, or
(2) pair {w, M (w)} dominates {w, u} in layer i.
The following example describes a scenario where the above concept of multi-layer stability appears to
be useful.
Example 2.2. Assume that the preferences of the agents depend on external circumstances which are not
known a priori. Assume that each layer represents a different possible state of the universe. If we want to
find a matching that is stable in as many states of the universe as possible, then we need to find an α-layer
globally stable matching for the highest possible value of α.
⋄
Already for α-layer global stability we see substantial differences compared to the original concept of
stability for a single layer. It is guaranteed that such a matching always exists for α = 1; indeed this would
be a matching that is stable in an arbitrary layer. However, one can observe that as soon as α > 1 an α-layer
globally stable matching might not exist (see Example 3.1).

2.2 α-layer pair stability
While α-layer global stability requires that the agents globally agree on a certain subset of α layers for
which the matching should be stable, pair stability forbids each unmatched pair to block more than a certain
number of layers. The formal definition, using the domination concept, is as follows:
Definition 2.3 (pair stability). A matching M is α-layer pair stable if for each unmatched pair {u, w} ∈
(U ⋆ W ) \ M , there is a set S ⊆ [ℓ] of α layers such that for each layer i ∈ S at least one of the following
conditions holds:
(1) pair {u, M (u)} dominates {u, w} in layer i, or
(2) pair {w, M (w)} dominates {w, u} in layer i.
Definition 2.3 can be equivalently formulated using a generalization of the concept of blocking pairs.
Let β ∈ [ℓ] be an integer bound. We say that a pair {u, w} ∈ (U ⋆ W ) \ M is β-blocking M if there exists
a subset S ⊆ {1, 2, . . . , ℓ} of β layers such that for each i ∈ S, pair {u, w} is blocking M in layer i.
Proposition 2.1. A matching M is α-layer pair stable if and only if no unmatched pair p is (ℓ − α + 1)blocking M .
Proof. To prove the statement, we show that a matching M is not α-layer pair stable if and only if there
is an unmatched pair p that is (ℓ − α + 1)-blocking M . For the “if” direction, assume that {u, w} is an
unmatched pair and R ⊆ [ℓ] is a subset of ℓ−α+1 layers such that {u, w} is blocking every layer in R. Now
consider an arbitrary subset S ⊆ [ℓ] of size α. By the cardinalities of R and S, it is clear that S ∩ R 6= ∅. Let
i ∈ S ∩ R be such a layer. Then, by assumption, we have that {u, w} is blocking M in layer i. This means
that none of the conditions stated in Definition 2.3 holds. Thus, {u, w} is an unmatched pair witnessing that
M is not α-layer pair stable.
For the “only if” direction, assume that M is not α-layer pair stable and let {u, w} be an unmatched pair
that witnesses the non-α-layer pair stability of M . We claim that {u, w} is (ℓ−α+1)-blocking M . Towards
a contradiction, suppose that {u, w} is not (ℓ − α + 1)-blocking M . Then, there must be a subset S ⊆ [ℓ] of
at least α layers where the pair {u, w} is not blocking M in each layer in S. Equivalently, we can say that
6

for each layer i ∈ S, {u, M (u)} dominates {u, w} in layer i or {w, M (w)} dominates {u, w} in layer i—a
contradiction to {u, w} being a witness.
The following example motivates α-layer pair stability.
Example 2.3. Consider the case when the preferences of the agents depend on a context, yet a context is
pair-specific. For instance, in matchmaking a woman may have different preferences over men depending
on which country they will decide to live in. Thus, a pair of a man and a woman is blocking if they agree
on certain conditions, and if they will find each other more attractive than their current partners according to
the agreed conditions.
⋄
In Section 3, we show that α-layer global stability implies α-layer pair stability (Proposition 3.1). This,
among other things, implies that for α = 1 an α-layer pair stable matching always exists. However, as soon
as α ≥ 2 the existence is no longer guaranteed (see Example 3.1).

2.3 α-layer individual stability
We move to the third and last concept of stability.
Definition 2.4 (individual stability). A matching M is α-layer individually stable if for each unmatched
pair {u, w} ∈ (U ⋆ W ) \ M there is a set S ⊆ [ℓ] of α layers such that at least one of the following
conditions holds:
(1) pair {u, M (u)} dominates {u, w} in each layer of S, or
(2) pair {w, M (w)} dominates {w, u} in each layer of S.
The following example illustrates a potential application in the domain of partnership agencies.
Example 2.4. Assume that each layer describes a single criterion for preferences. The preferences of each
agent may differ depending on the criterion. For instance, the two sets of agents can represent, respectively,
men and women, as in the traditional stable marriage problem. Different criteria may correspond, for instance, to the intelligence, sense of humor, physical appearance etc. Assume that an agent a will have no
incentive to break his or her relationship with b, and to have an affair with c if he or she prefers b to c
according to at least α criteria. In order to match men with women so that they form stable relationships,
one needs to find an α-layer individually stable matching.
⋄
Definition 2.4 can be equivalently formulated using a generalization of the concept of dominating pairs.
Let β ∈ [ℓ] be an integer bound. We say that a pair {u, w} is β-dominating {u, w′ } if there is a subset R ⊆ [ℓ]
of β layers such that for each i ∈ R the pair {u, w} dominates {u, w′ } in layer i.
Proposition 2.2. A matching M is α-layer individually stable if and only if no unmatched pair {u, w} exists
that is both (ℓ − α + 1)-dominating {u, M (u)} and (ℓ − α + 1)-dominating {w, M (w)}.
Proof. To prove the statement, we show that a matching M is not α-layer individually stable if and only
if there is an unmatched pair p that is (ℓ − α + 1)-dominating {u, M (u)} and (ℓ − α + 1)-dominating
{w, M (w)}. For the “if” direction, assume that {u, w} is an unmatched pair and R1 , R2 ⊆ [ℓ] are two
(possibly different) subsets of ℓ − α + 1 layers each, such that {u, w} is dominating {u, M (u)} in each
layer i ∈ R1 and is dominating {w, M (w)} in each layer j ∈ R2 . Now consider an arbitrary subset S ⊆ [ℓ]
of size α. By the cardinalities of R1 , R2 , and S , it is clear that S ∩ R1 6= ∅ and S ∩ R2 6= ∅. Let
i ∈ S ∩ R1 and j ∈ S ∩ R2 be two layers in the intersections. Then, by assumption, we have that {u, w}
is dominating {u, M (u)} in layer i and {u, w} is dominating {w, M (w)} in layer j. This means that none
of the conditions stated in Definition 2.4 holds. Thus, {u, w} is an unmatched pair witnessing that M is not
α-layer individually stable.
For the “only if” direction, assume that M is not α-layer individually stable and let {u, w} be an unmatched pair that witnesses the non-α-layer individual stability of M . We claim that {u, w} is (ℓ − α + 1)dominating {u, M (u)} and is (ℓ − α + 1)-dominating {w, M (w)}. Towards a contradiction, first suppose
7

that {u, w} is not (ℓ − α + 1)-dominating {u, M (u)}, meaning that there are at most ℓ − α layers where
{u, w} dominates {u, M (u)}. This implies that there is a subset S ⊆ [ℓ] of α layers such that for each
i ∈ S, the pair {u, M (u)} is dominating {u, w}, a contradiction to {u, w} being a witness of the non-αlayer individual stability of M . Analogously, if {u, w} was not (ℓ − α + 1)-dominating {w, M (w)}, then
we could obtain the same contradiction.
For α = 1 an α-layer individually stable matching always exists (it will follow from Propositions 3.1
and 3.3); however, this is no longer the case when α ≥ 2 (see Proposition 3.2 and Example 3.1).
Observe that according to α-layer individual stability the preferences of the agents can be represented
as sets of linear orders: it does not matter which preference order comes from which layer. This is not the
case for the other two concepts.

2.4 Central computational problems
In this paper, we study the algorithmic complexity of finding matchings that are stable according to the
above definitions. To this end, we first investigate how the three concepts relate to each other. Next, we
formally define the search problem of finding an α-layer globally stable matching.
G LOBALLY S TABLE M ARRIAGE
Input: Two disjoint sets of n agents each, U and W , ℓ preference profiles, and an integer
bound α ∈ [ℓ].
Output: Return an α-layer globally stable matching if one exists, or claim there is no such.
The other two problems, PAIR S TABLE M ARRIAGE and I NDIVIDUALLY S TABLE M ARRIAGE, are defined
analogously.

3 Relations Between the Multi-Layer Concepts of Stability
Below we establish relations among the three concepts. We start by showing that α-layer pair stability is a
weaker notion than α-layer global stability and α-layer individual stability.
Proposition 3.1. An α-layer globally stable matching is α-layer pair stable.
Proof. Let M be an α-layer globally stable matching and let S ⊆ {1, . . . , ℓ} be such that |S| = α and
that for each i ∈ S, matching M is stable in layer i. For the sake of contradiction let us assume that
M is not α-layer pair stable. By Proposition 2.1, let {u, w} be an (ℓ − α + 1)-blocking pair for M . Let
S ′ ⊆ {1, . . . , ℓ} be such that |S ′ | = ℓ − α + 1 and that for each i ∈ S ′ , pair {u, w} blocks M in layer i.
Since |S ′ | + |S| = ℓ + 1, we get that S ∩ S ′ 6= ∅. Let i ∈ S ∩ S ′ . This gives a contradiction since on the
one hand M is stable in layer i, and on the other hand {u, w} blocks M in layer i.
Proposition 3.2. An α-layer individually stable matching is α-layer pair stable.
Proof. Consider an α-layer individually stable matching M . Towards a contradiction, suppose that M is
not α-layer pair stable. By Proposition 2.1, this means that there exists an unmatched pair {u, w} and a
subset S ′ ⊆ [ℓ] of ℓ − α + 1 layers such that {u, w} is blocking M in each layer from S ′ . This means
that {u, w} is both (ℓ − α + 1)-dominating {u, M (u)} and (ℓ − α + 1)-dominating {w, M (w)}. Then, by
Proposition 2.2, M is not α-layer individually stable, a contradiction.
Example 3.1, below, shows a matching which is α-layer pair stable, but which is not α-layer globally stable. This example, together with Proposition 3.1, also shows that α-layer global stability is strictly stronger
than α-layer pair stability.
8

Example 3.1. Consider an instance with six agents and two layers of preference profiles.
w1 w2 w3
w2 w3 w1
w2 w1 w1
w1 w1 w3
w3 w3 w2
w3 w2 w2
u1
u2
u3
u1
u2
u3

P1 :

w1
u2
u1
u3

w2
u2
u1
u3

P2 :

w3
u3
u1
u2

w1
u3
u1
u2

w2
u1
u2
u3

w3
u2
u1
u3

Observe that matching M = {{u1 , w1 }, {u2 , w3 }, {u3 , w2 }} is 1-layer individually stable and, thus 1-layer
pair stable. However, M is blocked by pair {u2 , w1 } in the first layer and by {u1 , w2 } in the second.
Thus, M is not 1-layer globally stable. Indeed the only 1-layer globally stable matchings are indicated by
the solid lines, which are also 1-layer individually stable (and thus 1-layer pair stable).
As soon as α ≥ 2, α-layer pair stability is not guaranteed to exist, even if ℓ > α. To see this we augment
the instance with one more layer whose preference lists are identical to the first layer given in Example 2.1.
One can verify that for each of all six possible matchings, there is always an unmatched pair that is blocking
at least two layers.
⋄
For α = 1, we observe that 1-layer pair stability is equivalent to 1-layer individual stability.
Proposition 3.3. A matching is 1-layer pair stable if and only if it is 1-layer individually stable.
Proof. By Proposition 3.2, we know that 1-layer individual stability implies 1-layer pair stability. It remains
to show the other direction. Let M be a 1-layer pair stable matching. Suppose, for the sake of contradiction, that M is not 1-layer individually stable. By Proposition 2.2, this means that there is an unmatched
pair {u, w} that is both ℓ − 1 + 1 = ℓ-dominating {u, M (u)} and ℓ − 1 + 1 = ℓ-dominating {w, M (w)}.
This implies that the pair {u, w} is indeed ℓ-blocking M , which by Proposition 2.1, is a contradiction to M
being 1-layer pair stable.
Example 3.2 shows that for α > 1, individual stability and pair stability are not equivalent, neither is
individual stability equivalent to global stability.
Example 3.2. Consider the example given in Section 1. Recall that the first layer admits exactly one stable
matching, namely M1 = {{u1 , w1 }, {u2 , w2 }} (depicted by solid lines). The second layer also admits
exactly one (different) stable matching, namely M2 = {{u1 , w2 }, {u2 , w1 }} (also depicted by solid lines).
The third layer has two stable matchings, M1 and M2 (depicted by solid lines and dashed lines, resp.).
Thus, both M1 and M2 are 2-layer globally stable (and 2-layer pair stable). However, M1 is 2-layer
individually stable while M2 is not. To see why M2 is not 2-layer individually stable, we can verify that the
unmatched pair p = {u1 , w1 } dominates {u1 , w2 } in the first and the third layer and it dominates {u2 , w1 }
in the first two layers. By Proposition 2.2, M2 is not 2-layer individually stable since ℓ − α + 1 = 2.
If we restrict the example to the last two layers only, then matching M2 is also evidence that an ℓ-layer
globally stable (which, by Proposition 3.4, implies ℓ-layer pair stability) is not ℓ-layer individually stable. ⋄
For α = ℓ global stability and pair stability are equivalent.
Proposition 3.4. For α = ℓ, a matching is α-layer globally stable if and only if it is α-layer pair stable.
Proof. By Proposition 3.1, ℓ-layer global stability implies ℓ-layer pair stability. Now, assume that a matching M is ℓ-layer pair stable. For the sake of contradiction, suppose that M is not ℓ-layer globally stable.
This means that there exists a pair, say {u, w}, and a layer, say i, such that {u, w} is blocking in layer i.
Thus, {u, w} is 1-blocking M , and so M cannot satisfy ℓ-layer pair stability. This gives a contradiction.

9

It is somehow counter-intuitive that even an ℓ-layer globally stable matching (i.e. a matching that is
stable in each layer) may not be ℓ-layer individually stable (see Example 3.2). By Proposition 3.5 we can
thus infer that ℓ-layer global stability is strictly weaker than ℓ-layer individual stability.
Proposition 3.5. For α = ℓ, an α-layer individually stable matching is α-layer globally stable.
Proof. Proposition 3.2 and Proposition 3.4 imply the statement since α = ℓ.
By Example 3.2, ℓ-layer global stability does not imply ℓ-layer individual stability. However, it implies
individual stability.

⌈ℓ/2⌉-layer

Proposition 3.6. Every ℓ-layer globally stable matching is ⌈ℓ/2⌉-layer individually stable. There are instances where ℓ-layer globally stable matchings are not (⌈ℓ/2⌉ + 1)-layer individually stable.
Proof. For the first statement, let M be an ℓ-layer globally stable matching. Suppose, for the sake of
contradiction, that M is not ⌈ℓ/2⌉-layer individually stable. Let β = ℓ − ⌈ℓ/2⌉ + 1, which is ⌊ℓ/2⌋ + 1. By
Proposition 2.2, let {u, w} be an unmatched pair that is both β-dominating {u, M (u)} and β-dominating
{w, M (w)}. Since 2 · β > ℓ, there is at least one layer i where {u, w} is dominating both {u, M (u)} and
{w, M (w)}, meaning that {u, w} is blocking layer i, a contradiction to M being ℓ-layer globally stable.
To see why ℓ-layer global stability may not imply (⌈ℓ/2⌉ + 1)-layer individual stability, consider the
following instance with four agents and ℓ = 4 layers.
w1 w1
w1 w2
w2 w2
w2 w2
w2 w2
w2 w1
w1 w1
w1 w1
u1
u2
u1
u2
u1
u2
u1
u2

P1 :

w1
u1
u2

w2
u1
u2

P2 :

w1
u1
u2

P3 :

w2
u1
u2

w1
u2
u1

w2
u2
u1

P4 :

w1
u1
u2

w2
u2
u1

M = {{u1 , w1 }, {u2 , w2 }} is the only 4-layer globally stable matching. However, it is not 3-layer individually stable as the unmatched pair {u1 , w2 } dominates {u1 , w1 } in layers 3 and 4 and dominates {u2 , w2 }
in layers 1 and 2. By Proposition 2.2, M is not 3-layer individually stable since ℓ − α + 1 = 2.
The relations among the different concepts of multi-layer stability are depicted in Figure 1.
A 1-layer globally stable matching always exists. Together with Propositions 3.1 and 3.2, we obtain the
following.
Proposition 3.7. A preference profile with ℓ layers always admits a matching, which is 1-layer globally
stable, 1-layer pair stable, and 1-layer individually stable.

4 All-Layers Stability (α = ℓ)
In this section, we discuss the special case when α = ℓ. It turns out that deciding whether a given instance
admits an ℓ-layer individually stable matching can be solved in polynomial time. For the other two concepts
of stability, however, the problem becomes NP-hard even when ℓ = 2.

4.1 Algorithm for ℓ-layer individual stability
The algorithm for deciding ℓ-layer individual stability is based on the following simple lemma.
Lemma 4.1. Let u ∈ U and w ∈ W be two agents such that w is the first ranked agent of u in some
layer i ∈ [ℓ], and let u′ ∈ U \ {u} be another agent such that w prefers u over u′ in some layer j ∈ [ℓ].
Then, no ℓ-layer individually stable matching contains {u′ , w}.
10

ℓ-global

ℓ-individual

Prop 3.5, Ex 3.2

Prop 3.6 fo
r α ≤ ⌈ℓ/2
⌉

α-global

α-individual

Pr
3.4
op

x

3.
1

1-pair
P

α-pair

p
ro

2,
3.

Ex

2
3.

3.2

.3
p3
o
r
P

Ex

3.
1,
E

1-individual

an
d3
.5 ,

op

P ro
p3
.1 ,
Ex
3.1

op
s3
.4

Pr

Props 3.1 and 3.3, Ex 3.1

Pr

1-global

ℓ-pair
Figure 1: Relations among the different multi-layer concepts of stability for different values of α. Herein,
an arc is to be read like an implication: one property implies the other.
Proof. Let u, w, u′ be the three agents and let i, j be the two (possibly equal) layers as described by the
assumption. Suppose towards a contradiction that there is an ℓ-layer individually stable matching with
{u′ , w} ∈ M . This implies that {u, w} is an unmatched pair under M . However, w prefers u over u′ =
M (w) in layer j and u prefers w over M (u) in layer i—a contradiction to M being ℓ-layer individually
stable.
Lemma 4.1 leads to Algorithm 1 which looks quite similar to the so-called extended Gale-Shapley algorithm by Irving [28]. The crucial difference is that we loop into different layers and we cannot delete a
pair p of agents that does not belong to any stable matching, as it may still serve to block certain matchings.
Instead of deleting such pair, we will mark it. Herein, marking a pair {u, w} means marking the agent u
(resp. w) in the preference list of w (resp. u) in every layer.
The correctness of Algorithm 1 follows from Lemmas 4.2 to 4.4.
Lemma 4.2. If a pair {u′ , w} is marked during the execution of Algorithm 1, then no ℓ-layer individually
stable matching contains this pair.
Proof. Each pair is marked within two “foreach” loops in Line 2 and Line 3, respectively (we will refer to
them as the “outer” loop and the “inner” loop). Let us fix an arbitrary u ∈ U and i ∈ [ℓ] and consider the
pairs which was marked when the outer and the inner loops were run for u and i, respectively. We show
the statement via induction on the sequence of pairs which were marked when u and i was considered for
the two loops. For the induction to begin, let {u′ , w} with u′ ∈ U and w ∈ W be the first pair that is
marked during the execution. This implies that agent u ranks w in the first position in layer i and that w
prefers u to u′ in some (possibly different) layer. By Lemma 4.1, no ℓ-layer individually stable matching
contains {u′ , w}.
For the induction assumption, let {u′ , w} be the mth pair (for given u and i) that is marked during
the execution and no ℓ-layer individually stable matching contains a pair that is marked prior to {u′ , w}.
Suppose for the sake of contradiction that there is an ℓ-layer individually stable matching M which contains
the marked pair {u′ , w}. The fact that {u′ , w} has been marked implies that
11

Algorithm 1: Algorithm for finding an ℓ-layer individually stable matching.
1
2
3
4
5
6
7
8
9
10
11
12

13

14

Input: A set of agents U ∪ W and ℓ layers of preferences.
repeat
foreach agent u ∈ U do
foreach layer i = 1, 2, . . . , ℓ do
w ← the first ranked agent in u’s preference list in layer i
r←1
repeat
(j)
foreach u′ with w : u ≻w u′ for some layer j do
′
mark {u , w}
r ←r+1
w ← the rth ranked agent in u’s preference list in layer i
until {u, w} is not marked
until (some agent’s preference list consists of only marked agents) or (no new pair was marked in the last
iteration)
if some agent’s preference list consists of only marked agents then no ℓ-layer individually stable matching
exists
else return M = {{u, w} | w ← the first unmarked agent in u’s preference list in any layer} as an ℓ-layer
individually stable matching

1. u ranks w in the pth position in layer i for some p, and
2. w prefers u over u′ in some layer j.
However, by the description of the algorithm in layer i (Lines 4–11) for each agent w′ that u prefers to w in
(i)
layer i, i.e. w′ ≻u w, we have that {u, w′ } is marked (see the “until” condition in Line 11). The induction
(i)
assumption implies that M does not contain any {u, w′ } with w′ ≻u w. Thus, it follows that u prefers w
(i)
to M (u) in layer i, i.e. w ≻u M (u). This is a contradiction to M being ℓ-layer individually stable on the
(j)
unmatched pair {u, w} since there is a layer j ∈ [ℓ] such that u ≻w u′ = M (w).
The following lemma ensures that in Line 14 if w is matched to an agent u, then it is the most preferred
unmarked agent of u in all layers.
Lemma 4.3. If no agent’s preference list consists of only marked agents and there is an agent u and two
different layers i, j ∈ [ℓ], i 6= j such that the first unmarked agent in the preference list of u in layer i differs
from the one in layer j, then Algorithm 1 will mark at least one more pair.
Proof. Suppose towards a contradiction that no new pair is marked, but there is an agent u ∈ U such that
the first agent unmarked by u is different in different layers, say w and w′ in layers i and j, with w 6= w′
and i 6= j. Since no new pair will be marked, u is the last unmarked agent in the preference lists of w
and w′ in all layers (see Line 8 of Algorithm 1). Since |U | = |W | there is a different agent u′ ∈ U \ {u}
such that for each agent w ∈ W we have that u′ is not the last unmarked agent in the preference list of w
in any layer. Since no agent’s preference list consists of only marked agents, the preference list of u′ (in
some layer) contains an agent which is unmarked. Denote this agent as w′ . Again, since no new pair will be
marked, in the preference list of w′′ , agent u′ is the last unmarked agent—a contradiction.
When Algorithm 1 terminates and no agent contains a preference list that consists of only marked agents,
then we can construct an ℓ-layer individually stable matching by assigning to each agent u its first unmarked
agent in any preference list (note that Lemma 4.3 ensures on termination that for each agent it holds that in
all layers is first unmarked agent is the same).
Lemma 4.4. If upon termination no agent’s preference list consists of only marked agents, then the matching M computed by Algorithm 1 is ℓ-layer individually stable.
12

Proof. Towards a contradiction suppose that M returned by Algorithm 1 is not ℓ-layer individually stable.
That is, there is an unmatched pair {u, w} ∈ (U ⋆ W ) \ M with u ∈ U and w ∈ W and two layers i, j ∈ [ℓ]
(i)
(j)
such that u : w ≻u M (u) and w : u ≻w M (w). Observe that agent u is matched with the first agent,
denoted as x, in the preference list of u such that the pair {u, x} is not marked, and so we infer that {u, w}
is marked. Thus, the innermost loop of the algorithm has been run for the pair {u, w} (see Line 11). By
(j)
Line 8 of Algorithm 1 for all agents u′ where w : u ≻w u′ for some layer j ′ ∈ [ℓ], the pair {u′ , w} is
(j)
marked. This includes the pair {M (w), w} since w : u ≻w M (w)—a contradiction to Lemma 4.2.
Finally, we obtain that Algorithm 1 computes an ℓ-layer individually stable matching if one exists.
Theorem 4.1. For α = ℓ, Algorithm 1 solves I NDIVIDUALLY S TABLE M ARRIAGE in O(ℓ · n2 ) time.
Proof. Let I = (U, W, P1 , P2 , . . . , Pℓ ) with 2 · n agents be the input of Algorithm 1. By Lemma 4.2, no ℓlayer individually stable matching contains a marked pair. If there is an agent whose preference list consists
of only marked agents, then we can immediately conclude that the given instance is a no-instance.
Otherwise, Lemma 4.4 proves that the algorithm returns an ℓ-layer individually stable matching.
It remains to show that the algorithm terminates and has running time O(ℓ · n2 ). Since there are in total
O(n2 ) pairs, the algorithm will eventually terminate, either because some agent’s preference list consists of
only marked agents or because no new new pair will be marked.
By using a list that points to the first unmarked agent of each agent u in each layer, and by using a table
that stores pairs which are already marked and reconsidered by Line 8, the algorithm needs to “touch” each
pair at most twice, once when it is not yet marked and a second time when it is already marked.

4.2 NP-hardness for ℓ-layer global stability and ℓ-layer pair stability
In contrast to ℓ-layer individual stability, in this section we show that deciding G LOBALLY S TABLE M AR RIAGE is NP-hard as soon as ℓ = 2. We establish this by reducing the NP-complete 3-SAT problem [26] to
the decision variant of G LOBALLY S TABLE M ARRIAGE. The idea behind this reduction is to introduce for
each variable four agents that admit exactly two possible globally stable matchings, one for each truth value.
Then, we construct a satisfaction gadget for each clause by introducing six agents. These agents will have
three possible globally stable matchings. We use a layer for each literal contained in the clause to enforce
that setting the literal to false will exclude exactly one of the three globally stable matchings. Therefore,
unless one of the literals in the clause is set to true, no globally stable matching remains.
Using the above idea, we can already show hardness of deciding ℓ-layer global stability for ℓ = 3. With
some tweaks and using a restricted variant of 3-SAT [26] (see Lemma 4.5), we can strengthen our hardness
result to hold even for ℓ = 2. From here on, we call a clause monotone if the contained literals are either all
positive or all negative.
Lemma 4.5. 3-SAT is NP-hard even if each clause has either two or three literals, and no size-three clause
is monotone while all size-two clauses are monotone
Proof. We start with a 3-SAT instance and do the following. For each variable xi introduce a helper variable zi , and make sure that the helper variable zi is set to false if and only if the original variable xi is set
to true. To achieve this, we add to the instance two new clauses (xi ∨ zi ) and (xi ∨ zi ). Finally, for each
original clause (note that it has size three) that contains only positive literals (resp. only negative literals),
say xi ∨xj ∨xk (resp. xi ∨xj ∨xk ), we replace an arbitrary literal, say xi (resp. xi ), with z i (resp. zi ). Observe
that in the new instance, each original clause has size three and contains at least one negative and at least one
positive literal, and that the newly introduced clauses have size two and are monotone. It is straightforward
to see that the original instance is a yes-instance if and only if the new instance is a yes-instance.
Now, we are ready to present one of our main results.
13

Theorem 4.2. G LOBALLY S TABLE M ARRIAGE is NP-hard even if α = ℓ = 2.
Proof. We provide a polynomial-time reduction from an NP-complete restricted variant of 3-SAT as given
by Lemma 4.5 to the decision version of G LOBALLY S TABLE M ARRIAGE. Further, without loss of generality we assume that no clause contains two literals of the form x and x as it will be satisfied anyway and
can be ignored from the input instance.
Let (X, C) be an instance of the aforementioned 3-SAT variant with X = {x1 , x2 , . . . , xn } being the
set of variables and C = {C1 , C2 , . . . , Cm } being the set of clauses of size at most three each. To unify the
expression, for each size-three clause Cj = ℓ1j ∨ ℓ2j ∨ ℓ3j we order the literals so that the first literal is positive
and the second one is negative. For each size-two clause Cj = ℓ1j ∨ ℓ2j (note that it is monotone), we order
the literals arbitrarily, and we call it a positive clause if it contains only positive literals, otherwise we call it
a negative clause.
For each variable xi ∈ X, we create four variable agents xi , xi , yi , y i (we will make it clear when using
xi and xi whether we are referring to the literals or the variable agents). We will construct the preference lists
of the variable agents so that each globally stable matching contains either Mitrue := {{xi , yi }, {xi , y i }} or
Mifalse := {{xi , y i }, {xi , yi }}. Briefly put, using Mitrue and Mifalse will correspond to setting the variable xi
to true or false, respectively.
For each clause Cj ∈ C, we create six clause agents aj , bj , cj , dj , ej , fj . We will construct preference
lists for these clause agents so that for each size-three-clause, there are exactly three different ways in which
these agents are matched in a globally stable matching, and for each size-two-clause, there are exactly two
such ways. We use two layers to enforce that setting a different literal contained in the clause Cj to false
excludes exactly one of these ways.
In total, we have 4n + 6m agents and we divide them into two groups U and W with U = {xi , xi | i ∈
[n]}} ∪ {ai , bi , cj | j ∈ [m]} and W = {yi , y i | i ∈ [n]} ∪ {dj , ej , fj | j ∈ [m]}.
Preference lists of the variable agents. The preference lists of the variable agents restricted to the variable
agents have the same pattern. We use the symbol “· · · ” to denote some arbitrary order of the remaining
agents (that is, agents which were not yet explicitly mentioned in the preference list).
Layer (1) : ∀i ∈ [n]:
Layer (2) : ∀i ∈ [n]:

xi : yi ≻ Di ≻ yi ≻ · · · ,

yi : xi ≻ Ai ≻ xi ≻ · · · ,

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · .

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · ,

xi : yi ≻ Di′ ≻ yi ≻ · · · ,

y i : xi ≻ A′i ≻ xi ≻ · · · .

It remains to specify the meaning of symbols Ai , Di , A′i , and Di′ .
Ai denotes a list (in an arbitrary order) of all clause agents aj that satisfy either of the following conditions:
(a) aj corresponds to a size-three-clause Cj such that the second literal of clause Cj (which is a
negative literal) is xi , or
(b) it corresponds to a negative size-two-clause Cj such that the first literal of clause Cj is xi .
Di denotes a list (in an arbitrary order) of all clause agents dj such that the first literal of clause Cj is xi
(note that in this case Cj has either three literals or exactly two positive literals).
A′i denotes a list (in an arbitrary order) of all clause agents aj such that the last literal of Cj is xi (note that
in this case Cj has either three literals or exactly two positive literals).
Di′ denotes a list (in an arbitrary order) of all clause agents dj such that the last literal of Cj is xi (note that
in this case Cj has either three literals or exactly two negative literals).
14

To illustrate the above notation, suppose that variable xi appears in four size-three-clauses, call them
C1 , C2 , C3 , and C5 , and in two size-two-clauses: C4 and C6 . The positive literal xi is the first literal in
clauses C1 , C3 , and C4 . The negative literal xi is the second literal in C2 , and the last literal in C5 and C6 .
In this case, Ai = a2 , Di could be Di = d1 ≻ d3 ≻ d4 , A′i is empty, and Di′ could be Di′ = d5 ≻ d6 .
Preference lists of the clause agents. The preference lists for the clause agents in the first layer are “fixed”
when restricted to the clause agents; they only differ in the positions of variable agents. For a clause Cj and
(t)
(3)
an integer t ∈ {1, 2, 3} let Cj denote the t-th literal in Cj (there will be no Cj if Cj has two literals). For
a literal ℓi which is xi or xi , by X(ℓi ), Y (ℓi ), X(ℓi ), and Y (ℓi ), we denote the variable agents xi , yi , xi ,
and yi , respectively, all corresponding to variable xi . For instance, for a clause Cj = x2 ∨ x4 ∨ x5 , we have
(1)
(2)
that Y (Cj ) = y 2 , and Y (Cj ) = y 4 .
Layer (1), ∀j ∈ [m]:
(2)

|Cj | = 3:

(1)

aj : dj ≻ ej ≻ Y (Cj ) ≻ fj ≻ · · · , dj : bj ≻ cj ≻ X(Cj ) ≻ aj ≻ · · · ,
bj : ej ≻ fj ≻ dj ≻ · · · ,

ej : cj ≻ aj ≻ bj ≻ · · · ,

cj : fj ≻ dj ≻ ej ≻ · · · ,

fj : aj ≻ bj ≻ cj ≻ · · · ,
(1)

|Cj | = 2 and Cj is positive: aj : dj ≻ ej ≻ · · · ,

dj : bj ≻ X(Cj ) ≻ aj ≻ · · · ,

bj : ej ≻ dj ≻ · · · ,

ej : aj ≻ bj ≻ · · · ,

cj : fj ≻ · · · ,

fj : cj ≻ · · · ,

|Cj | = 2 and Cj is negative: aj : dj ≻ Y

(1)
(Cj )

≻ ej ≻ · · · ,

dj : bj ≻ aj ≻ · · · ,

bj : ej ≻ dj ≻ · · · ,

ej : aj ≻ bj ≻ · · · ,

cj : fj ≻ · · · ,

fj : cj ≻ · · · .

The preference lists for the second layer depends on the “positiveness” of the last literal. There are two
variants:
Layer (2), ∀j ∈ [m] with |Cj | = 3:
(3)

Variant 1 (Cj

Variant 2

(3)
(Cj

(3)

is positive) : aj : fj ≻ dj ≻ Y (Cj ) ≻ ej ≻ · · · , dj : cj ≻ aj ≻ bj ≻ · · · ,
bj : dj ≻ ej ≻ fj ≻ · · · ,

ej : aj ≻ bj ≻ cj ≻ · · · ,

cj : ej ≻ fj ≻ dj ≻ · · · ,

fj : bj ≻ cj ≻ aj ≻ · · · ,

is negative) : aj : ej ≻ fj ≻ dj ≻ · · · ,

(3)

dj : aj ≻ bj ≻ X(Cj ) ≻ cj ≻ · · · ,

bj : fj ≻ dj ≻ ej ≻ · · · ,

ej : bj ≻ cj ≻ aj ≻ · · · ,

cj : dj ≻ ej ≻ fj ≻ · · · ,

fj : cj ≻ aj ≻ bj ≻ · · · ,

Layer (2), ∀j ∈ [m] with |Cj | = 2:
Variant 1 (Cj is positive) :

Variant 2 (Cj is negative)

(2)

aj : dj ≻ Y (Cj ) ≻ ej ≻ · · · ,

dj : bj ≻ aj ≻ · · · ,

bj : ej ≻ dj · · · ,

ej : aj ≻ bj · · · ,

cj : fj ≻ · · · ,

fj : cj ≻ · · · ,

aj : dj ≻ ej ≻ · · · ,

dj : bj ≻ X(Cj ) ≻ aj ≻ · · · ,

(2)

15

bj : ej ≻ dj · · · ,

ej : aj ≻ bj · · · ,

cj : fj ≻ · · · ,

fj : cj ≻ · · · .

This completes the construction which can be done in polynomial time.
Before we show the correctness of our construction, we first discuss some properties that each 2-layer
globally stable matching M must satisfy.
Claim 1. Let M be a 2-layer globally stable matching for our two-layer preference profiles. For each
variable xi ∈ X, it holds that either Mitrue ⊆ M or Mifalse ⊆ M .
Proof. To see this, we distinguish between two cases, depending on whether the partner of xi , M (xi ), is y i
or not. If M (xi ) 6= y i , then by the stability of M for the first layer, it follows that y i prefers its partner M (y i )
to xi in the first layer as otherwise xi and y i are forming a blocking pair for the first layer. Since xi is the
only agent that y i prefers to xi in this layer, we have that M (y i ) = xi . Then, it must hold that M (xi ) = yi
as otherwise xi and yi would block M in the first layer. Thus, Mifalse ⊆ M .
Similarly, if M (xi ) = y i , then by the stability of M and by construction of the preference lists of xi and
yi in the second layer we must have that M (xi ) = yi . This leads to Mitrue ⊆ M .
(of Claim 1) ⋄
We obtain a similar result for the clause agents. For each clause Cj ∈ C with |Cj | = 3, let Nj1 =
{{aj , dj }, {bj , ej }, {cj , fj }}, Nj2 = {{aj , fj }, {bj , dj }, {cj , ej }}, Nj3 = {{aj , ej }, {bj , fj }, {cj , dj }}.
Claim 2. Let Cj ∈ C be a size-three-clause, and let xi be a variable that appears (as either a positive or a
negative literal) in Cj . For a 2-layer globally stable matching M the following conditions hold:
(i) If xi is the first literal in Cj and if Mifalse ⊆ M , then either Nj2 ⊆ M or Nj3 ⊆ M .
(ii) If xi is the second literal in Cj and if Mitrue ⊆ M , then either Nj1 ⊆ M or Nj3 ⊆ M .
(iii) If xi is the third literal in Cj and if Mifalse ⊆ M , then either Nj1 ⊆ M or Nj2 ⊆ M .
(iv) If xi is the third literal in Cj and if Mitrue ⊆ M , then either Nj1 ⊆ M or Nj2 ⊆ M .
Proof. We consider the four cases separately:
(i) Assume that xi is the first literal in Cj and Mifalse ⊆ M . This implies that {xi , y i } ∈ M . Consider
the preference list of xi in the first layer, and observe that dj appears in Di . Since xi prefers dj to its
partner y i in the first layer, it follows that dj must obtain a partner that it prefers to xj in the first layer.
By the preference list of dj in the first layer, we have that M (dj ) ∈ {bj , cj }. If M (dj ) = bj , then by
the preference list of bj in the first layer it follows that both ej and fj must obtain partners that they
find better than bj in the first layer. This means that M (fj ) = aj and M (ej ) ∈ {aj , cj }, implying
that M (ej ) = cj . Analogously, if M (dj ) = cj , then {aj , ej } ∈ M as otherwise they will block the
first layer since the most preferred agents of both aj and ej are already assigned to someone else, and
aj and ej are each other’s second most preferred agents. Then, bj must obtain a partner that it prefers
to dj . Since fj is the only agent left that bj prefers to dj , we get that M (bj ) = fj , and so Nj3 ⊆ M .
(ii) Assume that xi is the second literal in Cj and Mitrue ⊆ M (thus, in particular, {xi , yi } ∈ M ). Since
aj appears in Ai in the preference list of yi in the first layer, we infer that yi prefers aj to its partner xi
in the first layer. Thus, it follows that aj must obtain a partner that it prefers to yi in the first layer, i.e.
that M (aj ) ∈ {dj , ej }. If M (aj ) = dj , then by considering the preference list of dj in the first layer
we infer that both bj and cj obtain partners that they find better than dj in the first layer. This means
that M (cj ) = fj , and M (bj ) ∈ {ej , fj }. Since fj is taken by cj , we get that M (bj ) = ej . Together,
we have that Nj1 ⊆ M .
Analogously, if M (aj ) = ej , then {bj , fj } ∈ M as otherwise they would block the first layer since the
most preferred agents of both bj and fj are already assigned to someone else, and bj and fj are each
other’s second most preferred agent. Moreover, cj must obtain a partner that it prefers to ej . Since dj
is the only agent left that cj prefers to ej , we obtain that M (cj ) = dj . This leads to Nj3 ⊆ M .
16

(iii) Assume that xi is the third literal in Cj and Mifalse ⊆ M . Observe that in this case aj appears in A′i in
the preference list of y i in the second layer, and since {xi , y i } ∈ M , that y i prefers aj to its partner xi
in the second layer. It follows that aj must obtain a partner that it prefers to y j in the second layer. By
investigating the preference list of aj in the second layer (note that we are in Variant 1), we have that
M (aj ) ∈ {fj , dj }. If M (aj ) = fj , then by looking at the preference list of fj in the second layer we
infer that both bj and cj must obtain partners that they find better than fj in the second layer. Thus
M (cj ) = ej , and consequently, M (bj ) = dj . Summarizing, in this case we have that Nj2 ⊆ M .
Analogously, if M (aj ) = dj , then {bj , ej } ∈ M as otherwise they would block the second layer.
Moreover, fj must obtain a partner that it prefers to aj . Since cj is the only agent left that fj prefers
to aj , we obtain that M (cj ) = fj . This leads to Nj1 ⊆ M .
(iv) Finally, assume that xi is the third literal in Cj and Mitrue ⊆ M . In this case, we have that dj appears
in Di′ in the preference list of xi in the second layer, and that {xi , y i } ∈ M . This means that xi
prefers dj to its partner y i in the second layer, and so it must be the case that dj obtains a partner that
it prefers to xj in the second layer. As a result, we have that M (dj ) ∈ {aj , bj }. If M (dj ) = aj , then
the preference list of aj indicates that both ej and fj must obtain partners that they find better than
aj in the second layer. Thus, M (fj ) = cj , and M (ej ) ∈ {bj , cj }. Consequently, M (ej ) = bj , and
we get that Nj1 ⊆ M . Finally, if M (dj ) = bj , then {cj , ej } ∈ M as otherwise they would block the
second layer. Further, aj must obtain a partner that it prefers to dj , thus M (aj ) = fj . Consequently,
Nj2 ⊆ M .
(of Claim 2) ⋄
For each clause Cj ∈ C with |Cj | = 2, let Nj1 = {{aj , dj }, {bj , ej }}, Nj2 = {{aj , ej }, {bj , dj }}.
Claim 3. Let Cj ∈ C be a size-two-clause, and let xi be a variable that appears (as either a positive or a
negative literal) in Cj . Assume that M is a 2-layer globally stable matching. The following holds:
(i) If xi is the first literal in Cj and if Mifalse ⊆ M , then Nj2 ⊆ M .
(ii) If xi is the last literal in Cj and if Mitrue ⊆ M , then Nj2 ⊆ M .
(iii) If xi is the last literal in Cj and if Mifalse ⊆ M , then Nj1 ⊆ M .
(iv) If xi is the first literal in Cj and if Mitrue ⊆ M , then Nj1 ⊆ M .
Proof. We show the first two statements together and the last two statements together. Assume that one of
the conditions in the first two statements holds, that is,
1. xi is the first literal in Cj and Mifalse ⊆ M , or
2. xi is the last literal in Cj and Mitrue ⊆ M .
This implies that
1. either {xi , y i } ∈ M , and in the first layer the list Di contains dj , or
2. {xi , y i } ∈ M , and in the second layer the list Di′ contains dj and we are in Variant 2.
Since xi prefers all agents from Di to y i in the first layer and xi prefers all agents from Di′ to y i in the second
layer, we must have that dj obtains a partner that it prefers to xi in the first layer or to xi in Variant 2 of the
second layer. In either case, bj is the only agent that fulfills the requirement, implying that {bj , dj } ∈ M . By
looking at the preference lists of bj and ej in the first layer, we derive that {aj , ej } ∈ M . Thus, Nj2 ⊆ M .
Analogously, assume that one of the conditions in the last two statements holds, that is,
1. xi is the last literal in Cj and Mifalse ⊆ M , or
2. xi is the first literal in Cj and Mitrue ⊆ M .
This implies that
1. {xi , y i } ∈ M , and in the second layer we have Variant 1 such that the list A′i contains aj , or
2. {xi , yi } ∈ M , and in the first layer the list Ai contains aj .
Since y i prefers all agents from A′i to xi in the second layer and yi prefers all agents from Ai to xi in
the first layer, we must have that aj obtains a partner that it prefers to y i in the second layer (Variant 1)
17

or to yi in the first layer. In either case, dj is the only agent that fulfills the requirement, implying that
{aj , dj } ∈ M . By the preference lists of dj and bj in the first layer, we further derive that {bj , ej } ∈ M .
Thus, Nj1 ⊆ M .
(of Claim 3) ⋄
Now, we are ready to show that (X, C) admits a satisfying truth assignment if and only if there exists a
2-layer globally stable matching for the so-constructed instance.
(⇒) For the “only if” direction, assume that σ : X → {T, F } is a satisfying truth assignment for
(X, C). We claim that the matching M constructed as follows is all-layer globally stable.
(1) For each variable xi ∈ X with σ(xi ) = T , let Mitrue ⊆ M ; otherwise let Mifalse ⊆ M .
(2) For each size-three-clause Cj , identify a literal ℓj such that σ(ℓj ) makes Cj satisfied. If ℓj is Cj ’s first
literal, then let Nj1 ⊆ M . If ℓj is the second literal, then let Nj2 ⊆ M . Otherwise let Nj3 ⊆ M .
(3) For each size-two-clause Cj , let {cj , fj } ∈ M . Identify a literal ℓj such that σ(ℓj ) makes Cj satisfied.
If ℓj is the first literal in Cj , then let Nj1 ⊆ M ; otherwise let Nj2 ⊆ M .
Towards a contradiction suppose that M is not 2-layer globally stable, and let p = {u, w} be a possible
blocking pair with u ∈ U and w ∈ W . First, we observe that p involves neither two variable agents
that correspond to different variables nor two clause agents that correspond to different clauses. Second,
p does not involve two variable agents that belong to the same variable since for each layer and for each
two variable agents that correspond to the same variable, exactly one of both is already matched to its most
preferred agent. Third, p also does not involve two clause agents that belong to the same size-two-clause as
either of such clause agents is already matched with its most preferred agent.
Next, consider the case that u and w are two clause agents that belong to the same size-three-clause,
say Cj . If {u, w} is blocking M in the first layer, then we know that Nj3 ⊆ M as otherwise either u or w
already obtains its most preferred agent. But then {u, w} cannot be blocking M in the first layer as for each
agent w′ that is preferred to M (u) by u in the first layer, we have that w′ prefers M (w′ ) to u in the first
layer. Similarly, if {u, w} is blocking M in the second layer with Variant 1 (resp. Variant 2), then we know
that Nj1 ⊆ M (resp. Nj2 ⊆ M ) as otherwise either u or w already obtains its most preferred agent. Since
for each agent w′ such that u prefers w′ to M (u) in the second layer we have that w′ prefers M (w′ ) to u, it
follows that {u, w} cannot be blocking the second layer.
Now, suppose that p involves a variable agent and a clause agent. By the construction of the preference
lists, we can assume that the clause agent involved in the blocking pair p is either an aj or a dj for some
j ∈ [m]. We distinguish between two cases, depending on the size of Cj .
Case 1: |Cj | = 3. If aj ∈ p and p is blocking the first layer, then by the preference list of aj in the first
layer, we have that Nj2 ⊆ M . By the construction of the matching M , we have that the truth assignment of
the second literal, say xi , in Cj makes Cj satisfied; note that by our convention, the second literal is always
negative. This implies that Mifalse ⊆ M . Since p involves aj and is blocking the first layer, it follows that the
agent yi that corresponds to variable xi prefers ai to M (yi ) in the first layer. This means that Mitrue ⊆ M , a
contradiction.
Analogously, if aj ∈ p and p is blocking the second layer, then by the preference list of aj in the second
layer, we have that the preference list of aj comes from Variant 1 and Nj3 ⊆ M . By the construction of
the matching M , we have that the truth assignment of the third literal which is positive in Cj (recall that
Variant 1 was used) makes Cj satisfied. Let this literal be xi . Then, it must hold that Mitrue ⊆ M . Since p
involves aj and is blocking the second layer (due to Variant 1), it follows that the agent y i that corresponds
to variable xi prefers aj to M (y i ) in the second layer. This means that Mifalse ⊆ M , which results in a
contradiction.
If dj ∈ p and p is blocking the first layer, then by the preference list of dj in the first layer, we have
that Nj1 ⊆ M . By the construction of the matching M , we have that the truth assignment of the first literal,
say xi , in Cj makes Cj satisfied; note that by convention, the first literal is always positive. This implies that
Mitrue ⊆ M . Since p involves dj and is blocking the first layer, it follows that the agent xi that corresponds
18

to variable xi prefers dj to M (xi ) in the first layer. By the preference list of xi in the first layer, it follows
that Mifalse ⊆ M , which also yields a contradiction.
Finally, if dj ∈ p and p is blocking the second layer, then by the preference list of dj in the second
layer, we have that the preference list of dj comes from Variant 2 and Nj3 ⊆ M . By the construction of
the matching M , we have that the truth assignment of the third literal which is negative in Cj makes Cj
satisfied. Denote this literal by xi . Then, it follows that Mifalse ⊆ M . Since p involves dj and is blocking the
second layer (due to Variant 2), it follows that the agent xi that corresponds to variable xi in Cj prefers dj
to M (xi ) in the second layer. By the preference list of xi in the first layer, this means that Mitrue ⊆ M ,
which is a contradiction.
Case 2: |Cj | = 2. If aj ∈ p, then by the preference lists of aj in any of the two layers, we have that
Nj2 ⊆ M . Hence, the second literal in Cj makes it satisfied. We distinguish between two cases. If the
second literal in Cj is positive, say xi , then Mitrue ⊆ M and the other involved agent in p must be either
yi or y i . Since y i prefers its partner xi to aj in both layers, it follows that yi is the other involved agent.
However, by the preference list of yi in the first layer, Ai does not contain aj , meaning that yi also prefers
its partner xi to aj in both layers, which is a contradiction to p being a blocking pair.
If the second literal in Cj is negative, say xi , then Mifalse ⊆ M and our reasoning is very similar. First
we infer that the other involved agent in p must be either yi or y i . Since yi prefers its partner xi to aj in both
layers, it follows that the other agent in p is y i . However, by the preference list of yi in the second layer,
A′i does not contain aj , which means that y i prefers its partner to aj in both layers. Thus, in this case we
also get a contradiction.
If dj ∈ p, then our reasoning is very similar. First, by looking at the preference lists of dj in any of
the two layers, we infer that Nj1 ⊆ M . By the construction of the matching M , we get that the first literal
in Cj makes it satisfied. We consider two cases. If this literal is positive, say xi , then Mitrue ⊆ M and the
other involved agent in p must be either xi or xi . Agent xi prefers its partner yi to dj in both layers and so
it cannot be involved in the blocking pair. Thus, xi is the other involved agent. However, by the preference
list of xi in the first layer, Di′ does not contain dj , meaning that xi also prefers its partner yi to dj in both
layers, a contradiction to p being a blocking pair.
If the first literal in Cj is negative, say xi , then Mifalse ⊆ M and the other involved agent in p must be
either xi or xi . Since xi prefers its partner yi to dj in both layers, it follows that xi is the other involved
agent. However, by the preference list of xi in the last layer, Di does not contain dj , meaning that xi prefers
its partner y i to dj in both layers, which is again a contradiction.
(⇐) For the “if” direction, let M be a 2-layer globally stable matching. We construct a truth assignment σ as follows. For each variable agent xi , if Mitrue ⊆ M , then let σ(xi ) = T ; otherwise by Claim 1
we have that Mifalse ⊆ M , and let σ(xi ) = F . Suppose, towards a contradiction, that σ is not a satisfying
assignment and let Cj be a clause where none of the literals is evaluated to true. We distinguish between
two cases.
Case 1: |Cj | = 3. Let xr , xs , and ℓt be the first, second, and the third literal in Cj . Since none of these
literals is evaluated to true, it follows that Mrfalse , Mstrue ⊆ M . By statements (i) and (ii) in Claim 2, we
must have that Nj3 ⊆ M . However, by the statements (iii) and (iv) in Claim 2, applied for ℓt , we must have
that either Nj1 ⊆ M or Nj2 ⊆ M , a contradiction.
Case 2: |Cj | = 2. Let the first and the second literals in Cj correspond to variables xi and xk , respectively.
If Cj is positive, then since Cj is not satisfied, we have that Mifalse , Mkfalse ⊆ M . By Claim 3, we have that
both Nj1 and Nj2 must belong to M , which leads to a contradiction.
Analogously, if Cj is negative, then since Cj is not satisfied, we have that Mitrue , Mktrue ⊆ M . By
Claim 3, we have that both Nj1 and Nj2 must belong to M , a contradiction.
Altogether, we showed that the constructed matching is globally stable for two layers. This concludes
the proof of Theorem 4.2.
19

Since ℓ-layer global stability equals ℓ-layer pair stability (Proposition 3.4), by Theorem 4.2 we obtain
the following corollary for the pair stability.
Corollary 4.3. PAIR S TABLE M ARRIAGE is NP-hard even if α = ℓ = 2.
By adding to the profile constructed in the proof of Theorem 4.2 an arbitrary number of layers with
preferences that are stable anyway, we can deduce hardness for arbitrary α = ℓ ≥ 2.
Proposition 4.4. For each α = ℓ ≥ 2, both G LOBALLY S TABLE M ARRIAGE and PAIR S TABLE M AR RIAGE are NP-hard.
Proof. We add to the profile constructed in the proof of Theorem 4.2 ℓ − 2 layers with preferences of the
following form:
Layers (3)–(ℓ),∀i ∈ [n] :
∀j ∈ [m] :

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · ,

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · .

aj : dj ≻ ej ≻ fj ≻ · · · ,

dj : bj ≻ cj ≻ aj ≻ · · · ,

bj : ej ≻ fj ≻ dj ≻ · · · ,

ej : cj ≻ aj ≻ bj ≻ · · · ,

cj : fj ≻ dj ≻ ej ≻ · · · ,

fj : aj ≻ bj ≻ cj ≻ · · · .

It is straightforward that a matching is ℓ-layer globally stable if and only if it is 2-layer globally stable for
the first two layers.

5 Multi-Layer Stable Marriage with α < ℓ
In this section we show that for each of the three concepts that we introduced in Section 2 the problem of
computing a multi-layer stable matching is computationally hard as soon as 2 ≤ α < ℓ.

5.1 NP-hardness for α-layer global stability
To find a matching M that is α-layer globally stable, even if α < ℓ, the main difficulty is not just to determine
α layers where M should be stable. In fact, we sometimes need to find a matching that is stable in some
specific layers. This requirement allows us to adapt the construction in the proof of Theorem 4.2 to show
hardness for deciding α-layer global stability for the case when 2 ≤ α < ℓ.
Proposition 5.1. For each fixed number α with α ≥ 2, G LOBALLY S TABLE M ARRIAGE is NP-hard.
Proof. To prove the NP-hardness, we adapt the reduction in the proof of Theorem 4.2 which shows that
deciding α-layer global stability for α = ℓ = 2 is NP-hard. Let P be the constructed two-layer instance in
the proof of Theorem 4.2. Besides the original agents from P, we introduce two sets U and W of dummy
agents with |U | = |W | = 2·(ℓ−α+1), where U = {u1 , u2 , . . . , uℓ−α+1 } and W = {w1 , w2 , . . . , wℓ−α+1 }.
The idea of introducing such dummy agents is to make sure that each α-layer globally stable matching must
include all pairs {uj , wj }, j ∈ [ℓ − α + 1]. However, this is the case only when such matching is stable in the
two layers constructed in the NP-hardness proof of Theorem 4.2; we denote these two layers as layers (1)
and (2). In the following, we use “· · · ” to denote an arbitrary order of the unmentioned agents.
Preferences of the original agents. The preferences of the original agents in the first two layers are the
same as in P in the proof of Theorem 4.2. For each other layer, the preferences of the original agents are as
follows.
Layers (3)–(ℓ),∀i ∈ [n] :

xi : y i ≻ y i ≻ · · · ,
20

y i : xi ≻ xi ≻ · · · ,

∀j ∈ [m] :

Preferences of the dummy agents.

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · .

aj : dj ≻ ej ≻ fj ≻ · · · ,

dj : bj ≻ cj ≻ aj ≻ · · · ,

bj : ej ≻ fj ≻ dj ≻ · · · ,

ej : cj ≻ aj ≻ bj ≻ · · · ,

cj : fj ≻ dj ≻ ej ≻ · · · ,

fj : aj ≻ bj ≻ cj ≻ · · · .

The preferences of the dummy agents are as follows; let ℓ̂ = ℓ−α+1:

Layers (1)–(α), ∀j ∈ [ℓ̂] :
Layer (i + α), 1 ≤ i ≤ ℓ̂ − 1, ∀j ∈ [ℓ̂] :

uj : wj ≻ · · · ,

wj : uj ≻ · · · ,

uj : w(j mod ℓ̂)+i ≻ · · · ,

wj : u(j−1 mod ℓ̂)+i ≻ · · · .

Observe that each dummy agent obtains a different partner in different layers with indices higher than α.
More precisely, for each layer (i + α) with 1 ≤ α ≤ ℓ̂ − 1, the only stable matching in this layer must
include Mi = {{uj , w(j mod ℓ̂)+1 } | 1 ≤ j ≤ ℓ̂}} since uj and w(j mod ℓ̂)+1 are each other’s most preferred
agent. Moreover, by the same reasoning, each layer with index at most α admits exactly the same stable
matching regarding the dummy agents which is different from any layer with index higher than α, namely
M0 = {{uj , wj } | 1 ≤ j ≤ ℓ̂}. For each two distinct values i, j ∈ {0, 1, . . . , ℓ̂ − 1}, however, we have that
Mi ∩ Mj = ∅. This means that each α-layer globally stable matching must include M0 and must be stable
in the first α layers, including the first two layers.
Now, it is straightforward to see that a matching M is 2-layer globally stable for P if and only if M ∪M0
is α-layer globally stable for our new instance.
We remark that our proof for Proposition 5.1 also implies hardness for α = ℓ for arbitrary ℓ ≥ 2.

5.2 NP-hardness for α-layer individual stability
For α-layer individual stability, we also obtain a hardness result by reducing from the NP-hard P ERFECT
SMTI problem, the problem of finding a perfect SMTI-stable matching with (possibly) incomplete preference lists and ties [32, 38] which is defined as follows. A preference list is incomplete if not all agents from
one side are considered acceptable to an agent from the other side. A preference list has a tie if there are
two agents in the list which are considered to be equally good. As a result, a preference list of an agent u
from one side can be considered as a weak (i.e. transitive and complete) order u on a subset of the agents
on the other side. We use ≻u and ∼u to denote the asymmetric and symmetric part of the preference list,
respectively. Equivalently, two agents x and y are said to be tied by u if x u y and y u x, denoted as
x ∼u y. Formally, we say that a matching M for a P ERFECT SMTI with two disjoints sets U and W of
agents is SMTI-stable if there are no SMTI-blocking pairs for M . A pair {u, w} is SMTI-blocking M if
all of the following three conditions are satisfied: (i) u and w appear in the preference lists of each other,
(ii) w ≻u M (u) or u is not matched to any agent from W , and (iii) u ≻w M (w) or w is not matched to any
agent from U .
The reduction is based on the following ideas: In a P ERFECT SMTI instance I the preference list of an
agent z may have ties. To encode ties, we first “linearize” the preference list of z in I to obtain two linear
preference lists such that the resulting lists restricted to the tied agents are reverse to each other. Then, we
let half of the ℓ layers have one of the preference lists and let the remaining half to have the other list. Since
α < ℓ/2, it is always possible to find half layers which fulfill our α-layer individual stability constraint.
In I, two agents, say x and y, may not be acceptable to each other. To encode this, we introduce to
the source instance ℓ pairs of dummy agents with ℓ layers of preferences that preclude x and y from being
matched together. However, to make sure that an agent x is not matched to any dummy agent, we have to
require that ℓ ≥ 4.

21

Theorem 5.2. For each fixed number ℓ of layers with ℓ ≥ 4 and for each fixed value α with 2 ≤ α ≤ ⌊ℓ/2⌋,
I NDIVIDUALLY S TABLE M ARRIAGE is NP-hard, even if on one side, the preference list of each agent is the
same in all layers.
Proof. Assume that ℓ ≥ 4 and that 2 ≤ α ≤ ⌊ℓ/2⌋. We give a polynomial-time reduction from the NP-hard
P ERFECT SMTI problem [32, 38].
Let I be an instance of P ERFECT SMTI. In I we are given two disjoint sets of agents, U and W , with
|U | = |W | = n; each agent u ∈ U is endowed with a weak order u on a subset of W . By the SMTIstability, an agent u prefers not to be assigned to any agent rather than to be assigned to an agent outside of
its preference list.
We assume that ties occur in the preferences of the agents from the side U only, that there is at most one
tie per list, and each tie is of length two as this variant remains NP-hard [38, Theorem 2.2].
From I we construct an instance I ′ of the problem of finding an α-layer individually stable matching in
the following way. We copy the sets of agents U and W ; further, we introduce a set of 2ℓ · n dummy agents
P ∪ R with |P | = |R| = ℓ · n. We denote the elements in these sets as: P = {pi,j | 1 ≤ i ≤ n ∧ 1 ≤ j ≤ ℓ}
and R = {ri,j | 1 ≤ i ≤ n ∧ 1 ≤ j ≤ ℓ}. One side of the bipartite “acceptability graph” will consist of the
agents from U ∪ P , and the other side of the agents from W ∪ R. We construct the preference orders of the
agents as follows:
Agents from U . Consider an agent u ∈ U , and let Lu denote its preference list in I. In I ′ we construct
the preference list of u from Lu as follows. We iterate over Lu starting from the top position. If
agent u prefers x over y, then we assume that u also prefers x over y in all layers in I ′ . If x and y
are tied in Lu , then we assume that u prefers x over y in the first ⌈ℓ/2⌉ layers and y over x in the
remaining ⌊ℓ/2⌋ layers (or the other way around). The remaining parts of the preference orders of u
are constructed as follows: first, let us assume that u = ui ∈ U . Right after all agents from Lu , agent u
puts in all layers ri,1 , ri,2 , . . . , ri,ℓ , respectively in the following orders: (1) ri,1 ≻ ri,2 ≻ . . . ≻ ri,ℓ ,
(2) ri,2 ≻ ri,3 ≻ . . . ≻ ri,ℓ ≻ ri,1 , and so on, until (ℓ) ri,ℓ ≻ ri,1 ≻ ri,2 ≻ . . . ≻ ri,ℓ−1 . Next,
u puts all the remaining agents in an arbitrary order. For example, if ℓ = 5 and Lu is equal to
w1 ≻ w4 ≻ w3 ∼ w5 , then the preference lists of u in the five layers will be as follows, where “· · · ”
denotes some arbitrary but fixed order of the remaining agents.
Layer (1) :
Layer (2) :
Layer (3) :
Layer (4) :
Layer (5) :

agent ui :
agent ui :
agent ui :
agent ui :
agent ui :

w1
w1
w1
w1
w1

≻ w4
≻ w4
≻ w4
≻ w4
≻ w4

≻ w3
≻ w3
≻ w3
≻ w5
≻ w5

≻ w5
≻ w5
≻ w5
≻ w3
≻ w3

≻ ri,1 ≻ ri,2 ≻ ri,3 ≻ ri,4 ≻ ri,5 ≻ · · · ,
≻ ri,2 ≻ ri,3 ≻ ri,4 ≻ ri,5 ≻ ri,1 ≻ · · · ,
≻ ri,3 ≻ ri,4 ≻ ri,5 ≻ ri,1 ≻ ri,2 ≻ · · · ,
≻ ri,4 ≻ rr,5 ≻ ri,1 ≻ ri,2 ≻ ri,3 ≻ · · · ,
≻ rr,5 ≻ ri,1 ≻ ri,2 ≻ ri,3 ≻ ri,4 ≻ · · · .

Observe that in the first three layers w3 is preferred to w5 and in the remaining layers w5 is preferred
to w3 .
Agents from W . For each agent wi from W , we recall that the preferences of wi in I do not have ties (that
was one of the assumptions in the problem we reduce from). Let Lwi denote the preference list of wi .
The preferences of wi in I ′ are the same in all layers, where the second “· · · ” denotes some arbitrary
but fixed order of the remaining agents.
Layers (1)-(ℓ) : agent wi : Lwi ≻ pi,1 ≻ pi,2 ≻ · · · ≻ pi,ℓ ≻ · · · .
Agents from P ∪ R. Consider pi,j ∈ P : this agent ranks wi first, next ri,j , and next all the remaining
agents in some arbitrary order:
Layers (1)-(ℓ) : agent pi,j : wi ≻ ri,j ≻ · · · .
22

The preferences of an agent from ri,j ∈ R are constructed analogously:
Layers (1)-(ℓ) : agent ri,j : ui ≻ pi,j ≻ · · · .
This completes the description of the construction of instance I ′ . Obviously, the preferences of each
agent from W ∪ R are the same in all layers. Now, we will show that there exists a perfect SMTI-stable
matching in I if and only if there exists an α-layer individually stable matching in I ′ .
For the “onlyif” direction, assume that the instance I has a perfect SMTI-stable matching M . We claim
that M ′ = M ∪ {ri,j , pi,j } | 1 ≤ i ≤ n ∧ 1 ≤ j ≤ ℓ is α-layer individually stable for I ′ . First, M ′ is a
perfect matching for I ′ as M is a perfect matching for I. Second, observe that no two agents from R ∪ P
are blocking M ′ as for each agent a in R ∪ P it prefers its partner M ′ (a) to every other agent in R ∪ P in all
layers. Third, no agent from U ∪ W can form a blocking pair with an agent from R ∪ P for the matching M ′
as each agent a from U ∪ W prefers its partner M ′ (a) = M (a) ∈ La to every other agent in R ∪ P in all
layers. Now, consider two arbitrary agents u and w with u ∈ U and w ∈ W such that {u, w} is unmatched.
We show that we can always find a set S of ⌊ℓ⌋ ≥ α layers such that M ′ (u) ≻u w in each layer from S
or M ′ (w) ≻w u in each layer from S. We can assume that u and w are acceptable to each other in I as
otherwise both u and w prefer to be with their respective partner M ′ (u) and M ′ (w) rather than with each
other in all layers. Let us consider the following cases; note that the preference list of w does not have ties
and remains the same in all layers.
Case 1: u ≻w M ′ (w) = M (w). By the stability of M we have that M ′ (u) = M (u) u w in instance I. For the case that M ′ (u) and w tied by u we can identify ⌊ℓ/2⌋ layers, either the first ⌊ℓ/2⌋
layers or the last ⌊ℓ/2⌋ layers where u prefers M ′ (u) to w. For the case that M ′ (u) ≻u w we have that
u prefers M ′ (u) to w in all layers.
Case 2: M ′ (w) ≻w u. In this case we know that w prefers M ′ (w) to u in all layers.
For the “if” direction, assume that M ′ is an α-layer individually stable matching for I ′ . First, observe
that no agent ui ∈ U can be matched with an agent that it ranks lower than any agent from {ri,j | 1 ≤ j ≤ ℓ}
in any layer. Indeed, for such matching each pair {ui , ri,j }, with j ∈ [ℓ], would be blocking M ′ in all layers.
Similarly, ui cannot be matched with ri,j for j ∈ [ℓ] as the pair {ui , ri,(j+ℓ−2 mod ℓ)+1 } would be blocking
M ′ in exactly ℓ−1 layers, namely those layers other than the j th layer, which are more than ℓ−α layers. For
instance, if ui was matched with ri,1 , then {ui , ri,ℓ } would be blocking the 2nd , 3rd , . . . , ℓth layers; if ui was
matched with ri,2 , then (ui , ri,1 ) would be blocking the 1st , 3rd , 4th , . . . , ℓth layers, etc. Thus, each agent u
from U must be matched with someone from Lu , where Lu is the preference list of u in I. Consequently,
no agent in W is matched with an agent in P as otherwise, by the pigeonhole principle, some agent in
U must be matched with an agent in R which is not possible by our reasoning above. Also, by a similar
reasoning we deduce that each agent w from W must be matched with someone from Lw , where Lw is the
preference list of w in I. Now, we show that M = {{u, w} ∈ M ′ | u, w ∈ U ∪ W } is a perfect SMTI-stable
matching for I. Since M ′ is a perfect matching in I ′ , by the reasoning above, it follows that M is a perfect
matching in I. Suppose, for the sake of contradiction, that there is an unmatched pair {x, y} ∈
/ M that is
SMTI-blocking M . This means that x and y are acceptable to each other, and that y ≻x M (x) = M ′ (x)
and x ≻y M (y) = M ′ (y) in I. By the preference lists of x and y in I ′ and by the definition of M , it follows
that in each layer x prefers y to M ′ (x) and y prefers x to M ′ (y)—a contradiction to M ′ being α-layer
individually stable since α > 2.

5.3 NP-hardness of α-layer pair stability
We note that in the instance constructed in the proof of Theorem 5.2 every agent from the side W ∪R has the
same preference list in all layers. Later on, in Proposition 6.1 we will show that in such a case the concepts
23

of α-layer individual stability and α-layer pair stability are equivalent, Thus, we obtain the same hardness
result for pair stability when α ≤ ⌊ℓ/2⌋.
Corollary 5.3. For each fixed number ℓ of layers with ℓ ≥ 4 and for each fixed value α with 2 ≤ α ≤ ⌊ℓ/2⌋,
PAIR S TABLE M ARRIAGE is NP-hard even if on one side the preference list of each agent is the same in all
layers.
For α > ⌈ℓ/2⌉, we use an idea similar to the one used for showing Proposition 5.1.
Proposition 5.4. For each fixed number α with ⌈ℓ/2⌉ + 1 ≤ α ≤ ℓ, PAIR S TABLE M ARRIAGE is NP-hard.
Proof. Assume that α ≥ ⌈ℓ/2⌉ + 1. To prove the NP-hardness, we slightly adapt the reduction in the proof
of Theorem 4.2 which shows that deciding α-layer global stability is NP-hard for α = ℓ = 2. Let P be
the two-layer instance constructed in the proof of Theorem 4.2. The idea is to copy ℓ/2 times profile P and
make sure that an α-layer pair stable matching must be stable in the two layers of the original profile.
For the preference lists in the ℓ layers, we do the following; let k = ⌊ℓ/2⌋.
1. We make k copies of the profile P.
2. If ℓ is odd, then we add an ℓth layer with the following preference lists:
Layer (ℓ),∀i ∈ [n] :
∀j ∈ [m] :

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · ,

xi : y i ≻ y i ≻ · · · ,

y i : xi ≻ xi ≻ · · · .

aj : dj ≻ ej ≻ fj ≻ · · · ,

dj : bj ≻ cj ≻ aj ≻ · · · ,

bj : ej ≻ fj ≻ dj ≻ · · · ,

ej : cj ≻ aj ≻ bj ≻ · · · ,

cj : fj ≻ dj ≻ ej ≻ · · · ,

fj : aj ≻ bj ≻ cj ≻ · · · .

This completes the construction, which can clearly be done in polynomial time. We claim that profile P with
two layers has a 2-layer globally stable matching if and only if the new profile with ℓ layers has an α-layer
pair stable matching. For the “only if” direction, it is straightforward to see that each 2-layer globally stable
matching for P is ℓ-layer globally stable for the new profile. By Proposition 3.1, M is also ℓ-layer pair
stable for the new instance.
For the “if” direction, assume that M is an α-layer pair stable matching for the new instance
with ℓ layers. We claim that M is 2-layer globally stable for instance P. First, for each unmatched
pair {u, w} ∈
/ M , let S unblock ({u, v}) be the set that consists of all layers that are not blocked by {u, w}:
(i)
(i)
S unblock ({u, v}) := {i ∈ [ℓ] | M (u) ≻u w or M (w) ≻w u}. Since M is α-layer pair stable it follows
unblock
that |S
({u, v})| ≥ α ≥ ⌈ℓ/2⌉ + 1; the last inequality holds by our assumption on the value of α.
We claim that S unblock ({u, v}) contains at least k + 1 layers from the first 2 · k layers. If ℓ is odd, then
⌈ℓ/2⌉ + 1 = k + 2, and the claim follows; otherwise ℓ = 2k and ⌈ℓ/2⌉ + 1 = k + 1, implying our claim.
Since the first 2k layers are k copies of the two layers from P, we can assume without
that
T loss of generality
unblock ({u, v})
S unblock ({u, v}) contains at least the first k + 1 layers. Now, it is obvious that {u,v}∈M
S
/
contains at least the first two layers. This implies that no unmatched pair is blocking the first two layers, and
hence that M is 2-layer globally stable for the instance P.
Corollary 5.3 and Proposition 5.4 cover the whole range of the potential values of α except for
α = ⌊ℓ/2⌋ + 1 when ℓ is odd. As we will see in the next section Theorem 5.2 cannot be strengthened to
cover the value α = ⌊ℓ/2⌋ + 1 (see Proposition 6.3), and so, also Corollary 5.3 cannot be directly strengthened. However, we can tweak the construction from Theorem 5.2, breaking the restriction that on one side
the preference list of each agent is the same in all layers, and obtain hardness for α-layer pair stability for
α = ⌊ℓ/2⌋ + 1.
Proposition 5.5. For each fixed odd number ℓ of layers with ℓ ≥ 5 and for the case when α = ⌊ℓ/2⌋ + 1,
PAIR S TABLE M ARRIAGE is NP-hard.
24

Proof. We provide a reduction from an instance I of the NP-hard P ERFECT SMTI problem which is very
similar to the reduction given in the proof of Theorem 5.2. Consequently, instead of describing the new
reduction from scratch, we will only explain how it differs from the one from the proof of Theorem 5.2. For
each agent wi ∈ W in the proof of Theorem 5.2, the preference list of wi was the same in all layers. Now, in
the last ℓ − 1 layers this list is constructed in exactly the same way as in the proof of Theorem 5.2. However,
in the first layer we set the first part of the list to be reversed in comparison to the remaining (ℓ − 1) layers;
←−−
let Lwi be the reverse of the strict preference list of w in the input instance of P ERFECT SMTI and let the
second “· · · ” denote some arbitrary but fixed order of the remaining agents:
←−−
Layer (1) : agent wi : Lwi ≻ pi,1 ≻ pi,2 ≻ · · · ≻ pi,ℓ ≻ · · · .
The preference lists of all other agents are constructed in exactly the same way as in the proof of
Theorem 5.2. We prove that I admits a perfect SMTI-stable matching if and only if the constructed instance I ′ with ℓ layers admits an α-layer pair stable matching with α = ⌊ℓ/2⌋ + 1.
For the “only if” direction, assume that M is a perfect SMTI-stable matching for I and consider matching M ′ = M ∪ {ri,j , pi,j } | 1 ≤ i ≤ n ∧ 1 ≤ j ≤ ℓ . We will show that M ′ is α-layer pair stable for I ′ .
First of all, just as in the proof of Theorem 5.2 we deduce that no agent from P ∪ R and no agent from
U ∪ W will form a blocking pair. Neither will any two agents that are not acceptable to each other in I form
a blocking pair. Now, consider two arbitrary agents u and w with u ∈ U and w ∈ W that are acceptable
to each other in I. We need to find a subset of ⌊ℓ/2⌋ + 1 layers, where in each layer in the subset u prefers
M ′ (u) to w or w prefers M ′ (w) to u . We distinguish between two cases concerning the preference list of w
in I; note that it does not have ties:
Case 1: u ≻w M ′ (w) = M (w) in I. This implies that w prefers M ′ (w) to u in the first layer in I ′ .
Thus, it suffices if we can find ⌊ℓ/2⌋ layers in the last ℓ − 1 layers, where u prefers M ′ (u) to w. By
the stability of M we have that M ′ (u) = M (u) u w in instance I. For the case that M ′ (u) ≻u w
in I we have that u prefers M ′ (u) to w in all layers. For the case that M ′ (u) and w are tied by u we
can identify ⌊ℓ/2⌋ layers, either the layers from 2 to ⌊ℓ/2⌋ + 1 or the layers from ⌊ℓ/2⌋ + 2 to ℓ, where
u prefers M ′ (u) to w. Additionally, in the first layer w prefers M (w) to u, which gives in total the
subset of ⌊ℓ/2⌋ + 1 layers.
Case 2: M ′ (w) ≻w u. In this case we know that w prefers M ′ (w) to u in the last ℓ − 1 layers.
For the “if” direction, assume that M ′ is an α-layer pair stable matching for I ′ . By the same reasoning
as in the proof of Theorem 5.2 we deduce that each agent u ∈ U must be matched with someone that
it prefers to each agent from R in each layer, and that w ∈ W must be matched with an agent that it
prefers to each agent from P in all layers. Thus, u and M ′ (u) (resp. w and M ′ (w)) must be acceptable
to each other in I, meaning that M = {{u, w} ∈ M ′ | u ∈ U, w ∈ W } is a perfect matching for I.
We show that M is SMTI-stable. For the sake of contradiction, suppose that an unmatched pair {u, w} is
SMTI-blocking M . This means that w prefers u to M (w) = M ′ (w) in the last ℓ − 1 layers in I ′ , and that u
prefers w to M (u) = M ′ (u) in all ℓ layers, a contradiction to M ′ being α-layer pair stable, since α ≥ 2.

6 Two Special Cases of Preferences
In this section we consider two well-motivated special cases of our general multi-layer framework for stable matchings. We will discuss how the corresponding simplifying assumptions affect the computational
complexity of finding multi-layer stable matchings. Interestingly, even under seemingly strong assumptions
some variants of our problem remain computationally hard.

25

6.1 Single-layered preferences on one side
Consider the special case where the preferences of the agents from U can be expressed through a single
layer. Formally, we model this by assuming that for each agent from U , its preference list is the same in all
layers. In this case we say that the agents from U have single-layered preferences.
Single-layered preferences on one side can arise in many real-life scenarios. For instance, consider the
standard example of matching residents with hospitals and, similarly as in Example 2.4, assume that each
layer corresponds to a certain criterion. It is reasonable to assume that the hospitals evaluate their potential
employees with respect to the level of their qualifications only (thus, having a single layer of preferences),
while the residents take into account a number of factors such as how far is a given hospital from the place
they live, the level of compensation, the reputation of the hospital, etc.
First, we observe that in such a case two out of our three solution concepts from Section 2 are equivalent.
Proposition 6.1. If each agent from U has single-layered preferences, then α-layer pair stability and αlayer individual stability are equivalent for each α.
Proof. The fact that α-layer individual stability implies α-layer pair stability follows from Proposition 3.2.
Let us prove the other direction. Let M be an α-layer pair stable matching. Towards a contradiction,
suppose that M is not α-layer individually stable. By Proposition 2.2, let p = {u, w} be an unmatched pair
of agents such that there is a subset S1 of ℓ − α + 1 layers where p is dominating {u, M (u)}, and that there
is a subset S2 of (ℓ − α + 1) layers where p is dominating {w, M (w)}. By our assumption of single-layered
preferences for each agent in U , we have that p is dominating {u, M (u)} in every layer. Thus, the pair p is
blocking M in each layer in S2 —a contradiction to Proposition 2.1.
For profiles with single-layered preferences of the agents on one side, α-layer global stability is strictly
stronger than the other two concepts:
Example 6.1. Consider four agents with the following three layers of preference profiles:
w1 w2
w1 w2
w1 w2
w2 w1
w2 w1
w2 w1
u1
u2
u1
u2
u1
u2

P1 :

w1
u2
u1

w2
u1
u2

P2 :

w1
u2
u1

w2
u2
u1

P3 :

w1
u1
u2

w2
u1
u2

Let M = {{u1 , w2 }, {u2 , w1 }}. We show that M is 2-layer pair stable but not 2-layer globally stable.
Indeed, M is stable only in the first layer, so it cannot be 2-layer globally stable. To see why M is 2-layer
pair stable, consider the unmatched pairs {u1 , w1 } and {u2 , w2 }. The first one only blocks the third layer,
and the latter one only blocks the second layer.
⋄
6.1.1

Global stability

By Propositions 3.4 and 6.1, we can find out whether an instance with single-layered preferences on one
side admits an α-layer globally stable matching in time O(ℓα · α · n2 ) by guessing a subset of α layers
and using Algorithm 1. However, the following result shows that fixed-parameter tractability (FPT) for the
parameter α, i.e., the existence of an algorithm running in f (α) · (ℓ · n)O(1) time for some computable
function f , is unlikely (for details on parameterized complexity we refer to the books of Cygan et al. [17],
Downey and Fellows [19], Flum and Grohe [24], and Niedermeier [42]).
Theorem 6.2. Even if the preferences of the agents from U are single-layered G LOBALLY S TABLE M AR RIAGE is NP-hard and is W[1]-hard for the threshold parameter α. It can be solved in O(ℓα · α · n2 ) time.
26

Proof. For the running time statement, let I be an instance of G LOBALLY S TABLE M ARRIAGE with ℓ
layers. We guess a subset S ⊆ [ℓ] of α layers and check whether a matching M exists that is stable in
all layers of S. Now consider the instance I ′ restricted to the α layers in S. By Proposition 3.4, M is
α-layer globally stable in I ′ if and only if M is α-layer pair stable in I ′ . Since each agent on one side has
the same preference list in all layers, by Proposition 6.1, M is α-layer pair stable in I ′ if and only if M is
α-layer individually stable in I ′ . By Theorem 4.1, we can use Algorithm 1 to decide whether M is α-layer
individually stable in I ′ in O(α · n2 ) time. The total running time is thus O(ℓα · α · n2 ).
For the last statement, we provide a parameterized reduction1 from the W[1]-complete I NDEPENDENT
S ET problem parameterized by the size k of the solution. We will see that the reduction is also a polynomialtime reduction, showing the first statement since I NDEPENDENT S ET is also NP-hard.
In the I NDEPENDENT S ET problem we are given an undirected graph G = (V, E) with vertex set V and
edge set E, and a non-negative integer k, and we ask whether G admits a k-vertex independent set, i.e. a
vertex subset V ′ ⊆ V with k pairwisely non-adjacent vertices.
Given an I NDEPENDENT S ET instance (G = (V, E), k), we construct an instance with |V | layers with
the set of agents U ⊎ W as follows. Assume that V = {v1 , v2 , . . . , vn }. For each vertex vi ∈ V we construct
six agents, three for each side, denoted by ui , ui , wi , w i , ai and bi . Let U = {ui , ui , ai | 1 ≤ i ≤ n} and
W = {wi , w i , bi | 1 ≤ i ≤ n}. We create a layer for each vertex so that if a matching is stable for a layer,
then an independent set solution has to include the corresponding vertex and exclude any of its adjacent
vertices. Again, the notation “· · · ” denotes an arbitrary order of the unmentioned agents.
Agents from U .

The preference list of each agent in U is the same for all layers.
∀i ∈ [n] : agent ui : w i ≻ wi ≻ · · · ,
agent ui : wi ≻ wi ≻ · · · ,
agent ai : wi ≻ bi ≻ · · · .

Agents from W . For each layer i, 1 ≤ i ≤ n, the preference list of agents wi and w i and of agents wj
and w j for vj 6= vi are constructed in such a way that they encode the adjacency structure of graph G.
agent wi : ui ≻ ai ≻ · · · ,
agent wi : ui ≻ · · · ,
∀j with {vi , vj } ∈ E : agent wj : uj ≻ · · · ,
agent wj : uj ≻ · · · ,
∀k with {vi , vk } ∈
/ E : agent wk : uk ≻ uk ≻ · · · ,
agent wk : uk ≻ uk ≻ · · · .
The preference list of each bj with j ∈ [n] remains the same in all layers and is as follows.
agent bj : aj ≻ · · · .
Observe that for each layer i ∈ [n], wi is the most preferred agent of ai . Thus, a matching M is stable in
layer i only if M (wi ) ∈ {ui , ai }. From this we infer that for M to be stable in layer i it must also hold that
M (ui ) = w i . This implies that M (wi ) = ui as otherwise {ui , wi } would be blocking layer i. Further, if M
is stable in layer i, then for each vertex vj that is adjacent to vi , it must hold that M (wj ) = uj and M (w j ) =
1

A parameterized reduction from a parameterized problem Π1 to a parameterized problem Π2 is an algorithm mapping an
instance (x, k) to an instance (x′ , k′ ) in f (k) · |x|O(1) time such that k′ ≤ g(k), and that (x, k) ∈ Π1 if and only if (x′ , k′ ) ∈ Π2 ,
where f and g are some computable functions.

27

uj . In the following, for each i ∈ [n], let Mivc = {{ui , wi }, {ui , w i }} and Miind = {{ui , w i }, {ui , wi }}.
Then, we have the following observation for the case that a matching M is stable in layer i:
Mivc ⊆ M and for each vertex vj incident with {vi , vj } ∈ E it holds that Mjind ⊆ M .

(1)

Intuitively, the matching Miind means that vertex vj does not belong to an independent set while the matching Mivc means that vertex vi belongs to an independent set.
To complete the construction we let α = k. Clearly, the construction can be done in polynomial time.
Now, we claim that the given graph G has an independent set of size k if and only if the constructed instance
has an α-layer globally stable matching.
′ ⊆ V is a size-k independent set for G. We show that the
For the “only
S that V ind
S if” part,vcassume
matching M = vi ∈V ′ Mi ∪ vj ∈V \V ′ Mj ∪ {{ai , bi } | i ∈ [n]} is stable in each layer i with vi ∈ V ′ .
Suppose, for the sake of contradiction, that there is a layer i with vi ∈ V ′ and there is an unmatched
pair p = {x, y} with x ∈ U and y ∈ W that is blocking layer i, i.e. the following holds.
In layer i, agent x prefers y to M (x) and agent y prefers x to M (y).
First, y ∈
/ {bj | j ∈ [n]} since M (bj ) = aj is the most preferred agent of bj . Second, y ∈
/ {wj , wj |
{vi , vj } ∈ E} as both wj and w j already obtain their most preferred agents, namely uj and uj in layer i.
Third, y ∈
/ {wj , w j | vj ∈ V ′ }, as in this way wj and w j obtain uj and uj as their partners, and since V ′ is
an independent set, we have that {vi , vj } ∈
/ E, and so uj and uj are the most preferred partners of wj and
wj .
Now, the only possible choice for y would be agent wj or wj such that {vi , vj } ∈
/ E and vj ∈
/ V ′ . By
our construction of M we have that M (wj ) = uj and M (w j ) = uj . First, consider the case when y = wj .
By the preference list of wj in layer i, if {x, y} is a blocking pair, then x = uj . However, uj already obtains
its most preferred agent, namely, w j ; a contradiction. Analogously, the case when y = w j also results in a
contradiction. Summarizing, matching M is stable in each layer i with vi ∈ V ′ .
For the “if” part, assume that our constructed instance admits an α-layer globally stable matching M .
We show that the vertex subset V ′ := {vi ∈ V | M is stable in layer i} is an independent set of size k.
Clearly, |V ′ | = α = k. Suppose, for the sake of contradiction, that V ′ contains two adjacent vertices vi and
vj with {vi , vj } ∈ E. Since M is stable in layer i and {vi , vj } ∈ E, by our observation (1) we deduce that
Mivc ⊆ M and Mjind ⊆ M . However, this is a contradiction to M being stable in layer j.
6.1.2

Individual stability and pair stability

Observe that, by Theorem 5.2, we know that finding an α-layer individually stable matching with preferences single-layered on one side is NP-hard if ℓ ≥ 4 and α ≤ ⌊ℓ/2⌋.
Next, we establish a relation between the individual (and thus pair) stability for preferences singlelayered on one side, and the stability concept in the traditional single-layer setting, but with general (incomplete and possibly intransitive) preferences as studied by Farczadi et al. [23]. This relation allows us
to construct a polynomial-time algorithm for finding an α-layer individually stable (and hence α-layer pair
stable) matching with single-layer preferences on one side when α ≥ ⌊ℓ/2⌋ + 1.
Proposition 6.3. If the preferences of the agents on one side are single-layered and α ≥ ⌊ℓ/2⌋ + 1, then
PAIR S TABLE M ARRIAGE and I NDIVIDUALLY S TABLE M ARRIAGE can be solved in O(ℓ · n2 ) time.
Proof. We will reduce our problem to the S TABLE M ARRIAGE WITH G ENERAL P REFERENCES (SMG)
problem [23]. Let I be an instance of our problem, let U ∪ W denote the set of agents in I, and let ℓ be the
number of layers. We construct an instance I ′ of SMG as follows. In I ′ we have the same set of agents as
in I. For each agent u ∈ U we copy the preferences from I to I ′ (such an agent has the same preference
28

list in all layers). The preferences of the agents from W can be arbitrary binary relations on the set V .
Thus, we use an ordered pair (u, u′ ) of two agents to denote that u is regarded as good as u′ . Formally,
for each agent w ∈ W we define the general preferences of w, denoted as Rw , as follows: For each two
agents u, u′ ∈ U we let (u, u′ ) ∈ Rw if and only if w prefers u to u′ in at least α layers. First, by our
assumption on the value of α, we observe that the preferences of the agents from W are asymmetric as, i.e.,
for each pair of agents u, u′ ∈ U we have that |{(u, u′ ), (u′ , u)} ∩ Rw | ≤ 1.
Now, we will prove that a matching M is α-layer pair stable in I if and only if it is stable in I ′ according
to the definition of stability by Farczadi et al. [23]. Indeed, according to Farczadi et al. [23] a pair {u, w} is
SMG-blocking if and only if the following two conditions hold: (1) w ≻u M (u) and (2) (M (w), u) ∈
/ Rw .
The first condition is equivalent to saying that u prefers w to M (u) in each layer in I. The second condition
holds if and only if w prefers M (w) to u in less than α layers. This is equivalent to saying that w prefers
u to M (w) in at least ℓ − α + 1 layers, and so the two conditions are equivalent to saying that {u, w} is
(ℓ − α + 1)-blocking M in I.
For asymmetric preferences SMG can be solved in O(n2 ) time [23, Theorem 2], where the number of
agents is 2n. The reduction to an SMG instance takes O(ℓ · n2 ) time. The number of agents in I equals the
number of agents in I ′ . Thus, the problem (deciding α-layer pair stability) can be solved in O(ℓ · n2 ) time.
By Proposition 6.1, we obtain the same result for α-layer individual stability.

6.2 Uniform preferences in each layer
In this section we consider the case when for each layer the preferences of all agents from U (resp. all agents
from W ) are the same—we call such preferences uniform in each layer. This special case is motivated with
the following observation pertaining to Example 2.4: preferences uniform in a layer can arise if the criterion
corresponding to the layer is not subjective. For instance, if a layer corresponds to the preferences regarding
the wealth of potential partners, it is natural to assume that everyone prefers to be matched with a wealthier
partner (and so the preferences of all agents for this criterion are the same); similarly it is natural to assume
that the preferences of all hospitals are the same: candidates with higher grades will be preferred by each
hospital.
First, we observe that for uniform preferences no two among the three concepts are equivalent.
Example 6.2. Consider four agents with the following four layers of uniform preferences:
w1 w1
w1 w1
w2 w2
w2
w2 w2
w2 w2
w1 w1
w1
u1
u2
u1
u2
u1
u2
u1

P1 :

w1
u1
u2

w2
u1
u2

P2 :

w1
u2
u1

P3 :

w2
u2
u1

w1
u1
u2

w2
u1
u2

P4 :

w1
u2
u1

w2
w1
u2
w2
u2
u1

Let M1 = {{u1 , w1 }, {u2 , w2 }} and M2 = {{u1 , w2 }, {u2 , w1 }}. We observe that M1 is stable only in
layers (1) and (4) whereas M2 is stable only in layers 2 and 3. Thus, neither is 3-layer globally stable.
One can check that neither is 3-layer individually stable. However, both M1 and M2 are 3-layer pair stable.
To see why this is the case we observe that for M1 , both unmatched pairs {u1 , w2 } and {u2 , w1 } are each
blocking only one layer, namely layers 2 and 3, respectively. Moreover, if we restrict the instance to only
the first three layers, then we have the following results:
1. M1 is not even 2-layer globally stable but it is 2-layer individually stable as for each unmatched pair p
with respect to M1 , at least one agent in p obtains a partner which is its most preferred agent in at
least two layers.
2. M2 is 2-layer globally stable (it is stable in layers 2 and 3) but it is not 2-layer individually stable.
To see why it is not 2-layer individually stable, we consider the unmatched pair {u1 , w1 }. There are
29

3 − 2 + 1 = 2 layers where u1 prefers w1 to its partner M2 (u1 ) = w2 and there are two layers where
w1 prefers u1 to its partner M2 (w1 ).
⋄
6.2.1

Individual stability

For preferences that are uniform in each layer, we find that there is a close relation between I NDIVIDUALLY
S TABLE M ARRIAGE and G RAPH I SOMORPHISM, the problem of finding an isomorphism between graphs
or deciding that there exists none. Herein, an instance of G RAPH I SOMORPHISM consists of two undirected
graphs G and H with the same number of vertices and the same number of edges. We want to decide
whether there is an edge-preserving bijection f : V (G) → V (H) between the vertices, i.e. for each two
vertices u, v ∈ V (G) it holds that {u, v} ∈ E(G) if and only if {f (u), f (v)} ∈ E(H). We call such
bijection an isomorphism between G and H.
We explore this relation through the following construction. For an instance I of I NDIVIDUALLY S TA BLE M ARRIAGE we construct two directed graphs GI and HI as follows. The agents from U and W will
correspond to the vertices in GI and HI , respectively. For each two vertices u, u′ ∈ U we add to GI an
arc (u, u′ ) if the agents from W prefer u to u′ in at least (ℓ − α + 1) layers. Analogously, for each two
agents w and w′ , we add to HI an arc (w, w′ ) if the agents from U prefer w to w′ in at least (ℓ − α + 1)
layers. Let E(GI ) and E(HI ) denote the arc sets of GI and HI , respectively.
We first explain how the so constructed graphs can be used to find an α-layer individually stable matching in the initial instance I, or to claim there is no such a matching.
Proposition 6.4. A matching M for instance I is α-layer individually stable if and only if the following two
properties hold.
1. For each two vertices u, u′ ∈ U , it holds that: (u, u′ ) ∈ E(GI ) implies (M (u′ ), M (u)) ∈
/ E(HI ).
2. For each two vertices w, w′ ∈ W , it holds that: (w, w′ ) ∈ E(HI ) implies (M (w′ ), M (w)) ∈
/ E(GI ).
Proof. For the “only if” direction, assume that M is α-layer individually stable. Towards a contradiction,
suppose that one of both properties stated above does not hold. That is, there exist two vertices u, u′ ∈ U
such that (u, u′ ) ∈ E(GI ) and (M (u′ ), M (u)) ∈ E(HI ) or there exist two vertices w, w′ ∈ W such that
(w, w′ ) ∈ E(HI ) and (M (w′ ), M (w)) ∈ E(GI ). For the first case, it follows that there is a subset S of
at least ℓ − α + 1 layers such that all agents (including M (u′ )) in W prefer u to u′ in each layer of S, and
there is a (possibly different) subset R of at least ℓ − α + 1 layers such that all agents (including u) in U
prefer M (u′ ) to M (u) in each layer of R. This means that the pair {u, M (u′ )} is (ℓ − α + 1)-dominating
{u′ , M (u′ )} and is (ℓ − α + 1)-dominating {u, M (u)}—a contradiction to Proposition 2.2. Analogously,
the second case also leads to a contradiction to Proposition 2.2 regarding the unmatched pair {M (w′ ), w}.
For the “if” direction, assume that both properties hold. Towards a contradiction and by Proposition 2.2,
suppose that there is an unmatched pair, call it {u, w} with u ∈ U and w ∈ W , which is (ℓ − α + 1)dominating {u, M (u)} and is (ℓ − α + 1)-dominating {w, M (w)}. By our construction of GI and HI , it
follows that (w, M (u)) ∈ E(HI ) and (u, M (w)) ∈ E(GI )—a contradiction to the second property.
Using a construction by McGarvey [40], given an arbitrary directed graph, we can indeed construct
multi-layer preferences that induce this graph.
Lemma 6.1. For each two directed graphs GI and HI with m arcs each there exists an instance with
ℓ = 2m layers of preferences that induces GI and HI via McGarvey’s construction, where m denotes the
number of arcs in GI (and thus in HI ).
Proof. Our profile uses the vertex sets of GI and HI as the two disjoint subsets of agents, denoted as U
and W , respectively. For each arc in the graphs GI (resp. HI ) we construct two layers of preference lists
30

Arcs to all other vertices
except for the deputy.
primeG

deputyG

connectorG
{v,v ′ }

v

sinkG
{v,v ′ }

connectorG
∗

...

v′

Figure 2: Construction of the graphs GI and HI in the proof of Theorem 6.5. The diagram shows the case
{v, v ′ } ∈ G.
for the agents from W (resp. U ) to “encode” it. We describe how to construct the preference lists for an
arc in GI , say (u, u′ ). The construction for the arcs in HI works analogously. To encode the arc (u, u′ ),
→
−
we construct two layers where the preference lists for the agents in W are as follows; denote by X some
←
−
→
−
arbitrary but fixed order of the agents other than u and u′ and let X be the reverse of X .
→
−
One layer : u ≻ u′ ≻ X .
←
−
The other layer : X ≻ u ≻ u′ .
Finally, we set α = ℓ/2 = m. Note that for each two agents u and u′ in GI all agents from W prefer u to u′
in either exactly m − 2 layers, or exactly m layers, or exactly m + 2 layers. It is straightforward to see that
our constructed instance induces the two input graphs GI and HI .
Using Proposition 6.4 and Lemma 6.1 as tools, we can show that for the preferences of the agents being
uniform in all layers, the problem of finding an α-layer individually stable matching is at least as hard as the
graph isomorphism problem.
Theorem 6.5. G RAPH I SOMORPHISM is polynomial-time reducible to I NDIVIDUALLY S TABLE M AR RIAGE, where the preferences of the agents are uniform in all ℓ layers, ℓ is even, and α = ℓ/2.
Proof. Let G, H be two undirected graphs that form an instance of G RAPH I SOMORPHISM. Without loss
of generality, assume that n ≥ 4 (number of vertices) and m ≥ 3 (number of edges). From G and H
we construct an instance I of the problem of deciding whether there exists an α-layer individually stable
matching for preferences being uniform in all ℓ layers, where α = ℓ/2. By Lemma 6.1 we can describe this
instance by providing the corresponding directed graphs GI and HI . We show how to construct GI from G.
The graph HI is constructed from H analogously.
Let V and E denote the sets of vertices and edges in G. We copy all vertices from G to GI (we will refer
to these vertices as non-special) and we additionally introduce five types of “special” vertices, which we call
31



primeG , deputyG , n2 + 1 connectors, m sinks, and n2 − m sources. We specify the connectors, the sinks,

and the sources formally: With each pair of vertices p = {v, v ′ } ∈ V2 we associate one connector, denoted
G
as connector G
p . One remaining connector is distinguished and denoted as connector ∗ . Further, for each
G
edge e ∈ E we have one sink, denoted as sinke , and for each non-edge e = {v, v ′ } ∈
/ E we have a source,
V
G
.
The
arcs
in
G
are
constructed
as
follows.
Let
SOURCE
=
{source
denoted as sourceG
I
e | e ∈ 2 \ E},
e

V
SINKG = {sinke | e ∈ E}, and CONNECTORG = {connector G
e | e ∈ 2 } denote the set of all sources,
the set of all sinks, and the set of non-special connectors, respectively:
• For each pair e = {v, v ′ } ⊆ V of vertices, we do the following:
G
′
G
1. If {v, v ′ } ∈ E, then we add to GI the following five arcs: (v, sinkG
e ), (v , sinke ), (v, connector e ),
G
′
G
G
(v , connector e ), and (sinke , connector e ). Otherwise, we add to GI the following five arcs:
G
G
′
G
G
G ′
(sourceG
e , v), (sourcee , v ), (v, connector e ), (v , connector e ), and (sourcee , connector e ).
′
G
2. For each other non-special vertex u ∈ V \ {v, v }, we add to GI the arc (connector e , u).
G
3. For each other source or sink x ∈ SOURCEG ∪ SINKG \ {sinkG
e , sourcee }, we add to GI the
arc (connector G
e , x).
• For each source and each sink x ∈ SOURCEG ∪ SINKG we add to GI an arc (x, connector G
∗ ). For each
G
non-special vertex v ∈ V , we additionally add to G the arc (connector ∗ , v).
• For each vertex x ∈ V ∪ SOURCEG ∪ SINKG ∪ CONNECTORG ∪ {connector G
∗ } except for the deputy,
we add to GI an arc (primeG , x).
• For each vertex x ∈ SOURCEG ∪ SINKG ∪ {primeG } we add to GI the arc (deputyG , x). For each
G
connector y ∈ CONNECTORG ∪ {connector G
∗ } we add to GI the arc (y, deputy ).
This completes the construction of GI (crucial elements of this construction are illustrated in Figure 2).
Observe a useful property: Each vertex in GI except primeG has at least two incoming arcs; primeG has
exactly one incoming arc, namely from deputyG . Indeed, since GI has at least three edges (and so at
least three connectors), deputyG has at least three incoming arcs from the connectors. Each connector
′
G
connector G
{v,v′ } has incoming arcs from v and v ; The special connector connector ∗ has arcs from all sources
and sinks (there are at least six of them). For each sink, source, and each non-special vertex there are at least
two incoming arcs, one from the prime and the other from the deputy.
The arcs in HI are constructed analogously. We claim that there is an α-layer individually stable matching in the instance (GI , HI ) with α = ℓ/2 if and only if there is an isomorphism between G and H.
(⇐) For the “if” direction, assume that there is an isomorphism f : V (G) → V (H) between G to H. We
show that the following matching M is m-layer individually stable. For each vertex v ∈ V (G)let M (v)
 =
G
G
G
G
f (v) ∈ V (H). Further, for each source or sink s{v,v′ } ∈ SOURCE ∪ SINK we let M s{v,v′ } =
G
′
sH
{f (v),f (v′ )} . Why should such a matching exist? If s{v,v′ } is a sink, then {v, v } ∈ E(G); since f is
an isomorphism, we have that {f (v), f (v ′ )} ∈ E(H) and so the sink sH
{f (v),f (v′ )} exists. Analogously, if
G
H
s{v,v′ } is a source, then s{v,v′ } is also a source and exists in H. Similarly, we match the corresponding


H
connectors: for each pair of vertices {v, v ′ } we let M connector G
{v,v′ } = connector {f (v),f (v′ ))} , and we
G
H
G
H
H
let M (connector G
∗ ) = connector ∗ . Finally, we let M (deputy ) = deputy and M (prime ) = prime .
Since f is an isomorphism between G and H, by the construction of GI and HI , an arc (x, y) in GI
(resp. HI ) implies no arc (M (x), M (y)) in HI (resp. GI ). By Proposition 6.4, M is m-layer individually
stable.

(⇒) For the “only if” direction, assume that M is an m-layer individually stable matching for (GI , HI ).
We start by showing M (primeG ) = primeH . For the sake of contradiction, suppose that this is not the
case, and let y = M (primeG ) ∈ V (HI ), with y 6= primeH . Since y 6= primeH , there are at least two
vertices w1 , w2 ∈ V (HI ) with (w1 , y), (w2 , y) ∈ E(HI ). Thus, one of them is not matched to deputyG ,
say M (w1 ) 6= deputyG . Since (w1 , y) ∈ E(HI ), by Proposition 6.4, it must hold that (primeG , M (w1 )) =

32

(M (y), M (w1 )) ∈
/ E(GI ). This is a contradiction with M (w1 ) 6= deputyG since primeG has outgoing arcs
to all vertices but deputyG .
Second, we show that M (deputyG ) = deputyH . The reason for this is that using Proposition 6.4 for the
arc (deputyG , primeG ) implies that (M (primeG ), M (deputy G )) = (primeH , M (deputy G )) cannot exists
in HI . By construction, primeH has an arc to all vertices except deputyH . Thus, M (deputy G ) = deputyH .
By an analogous reasoning focusing on the deputy vertex, we deduce that each connector in GI must be
matched with some connector in HI . Further, for each source or sink sG ∈ SOURCEG ∪ SINKG since
G
G
(sG , connector G
∗ ) ∈ E(GI ), by Proposition 6.4, it follows that (M (connector ∗ ), M (s )) does not exist
in HI ; thus there are at least 6 forbidden arcs from M (connector G
∗ ) to some vertices which are sinks,
sources, or non-special vertices. This means that connector G
can
only
be matched to connector H
∗
∗ because
each other connector in HI has all but three outgoing arcs to such vertices. Thus, we deduce that each
source/sink must be matched with a source/sink only, and consequently, that non-special vertices in GI are
matched with non-special vertices in HI . We show that the bijection f : V (GI ) → V (HI ) derived from M
by setting f (v) = M (v) for each v ∈ V is an isomorphism between G and H.
Consider an arbitrary pair e = {v, v ′ } ⊆ V (G) of non-special vertices and its corresponding connector
H
H
G
G
connector G
e . We know that M (connector e ) ∈ CONNECTOR , say M (connector e ) = connector {w,w ′ } .
We claim that {w, w′ } = {M (v), M (v ′ )}. Towards a contradiction, suppose that M (v) ∈
/ {w, w′ }. Then,
G
(v, connector G
e ) ∈ E(GI ) and (connector {w,w ′ } , M (v)) ∈ E(HI ), a contradiction to Proposition 6.4. Finally, we show that e ∈ E(G) if and only if {f (v), f (v ′ )} = {M (v), M (v ′ )} = {w, w′ } ∈ E(H).
G
G
If e ∈ E(G), then sinkG
e exists and (sinke , connector e ) ∈ E(GI ). By Proposition 6.4, it follows that
H
G
H
G
/ E(HI ). Since M (sinkG
(connector {w,w′ } , M (sinke )) = (M (connector e ), M (sinkG
e )) ∈
e ) ∈ SOURCE ∪
G
H
SINKH , we have that M (sinkG
e ) = s{w,w ′ } , where s is a source or a sink. Further, since (v, sinke ) ∈ E(GI )
we infer that (sH
/ E(GI ), and so s is a sink, and w and w′ are connected in H. Similarly, if
{w,w ′ } , w) ∈
H
′ / E(H).
e∈
/ E(G), then we deduce that sourceG
e and source{w,w ′ } exist, and thus {w, w } ∈

Theorem 6.5 implies that developing a polynomial-time algorithm for our problem is currently out
of scope, since the question of whether G RAPH I SOMORPHISM is solvable in polynomial time is still
open. Besides Theorem 6.5 there are other interesting implications of Proposition 6.4 and Lemma 6.1. For
α ≥ ℓ/2 + 1 our problem can be reduced to the T OURNAMENT I SOMORPHISM problem, which, given two
tournament graphs, asks whether there is an arc-preserving bijection between the vertices of the two tournaments [3, 46, 47]. T OURNAMENT I SOMORPHISM has been studied extensively in the literature (for a
more detailed discussion see, e.g., [3, 47, 46]), but to the best of our knowledge it is still open whether it is
solvable in polynomial time [3]. The best known algorithm solving T OURNAMENT I SOMORPHISM runs in
nO(log n) time, where n denotes the number of vertices.
Corollary 6.6. If the preferences of the agents are uniform in all ℓ layers and α ≥ ℓ/2 + 1, then I NDIVID UALLY S TABLE M ARRIAGE can be solved in nO(log n) + O(ℓ · n2 ) time, where n denotes the number of
agents.
Proof. Assume that α ≥ ℓ/2 + 1 and construct the two directed graphs as we did for Proposition 6.4. Since
ℓ − α + 1 ≤ ℓ/2, for each pair of vertices x and y in GI (resp. HI ) at least one arc from (x, y) and
(y, x) exists. Note that such graphs are not necessarily tournaments, where for each two vertices x and y
exactly one of (x, y) and (y, x) exists. But we can deal with the case when one of the graphs is not a
tournament. If both (x, y) and (y, x) exist in GI or in HI , then by Proposition 6.4 no α-layer individually
stable matchings exists. Thus, the only non-trivial case is when the graphs GI and HI are tournaments.
Moreover, in such a case, the condition from Proposition 6.4 can be reformulated as (x, y) ∈ GI if and
only if (M (x), M (y)) ∈ HI and this is the condition that M is a tournament isomorphism between GI
and HI . Consequently, for α ≥ ℓ/2 + 1 the problem of finding an α-layer individually stable matching can
be reduced to T OURNAMENT I SOMORPHISM. Note that the number of vertices in the constructed graphs
33

equals the number of agents in our problem. By the result of Babai and Luks [3], we obtain an algorithm for
our problem with the desired running time.
6.2.2

Global stability

There exists a fairly straightforward polynomial-time algorithm for finding α-layer globally stable matchings.
Proposition 6.7. If the preferences of the agents are uniform in all ℓ layers, then G LOBALLY S TABLE
M ARRIAGE can be solved in O(ℓ · n) time, where n denotes the number of agents.
Proof. It is apparent that for uniform preferences of the agents, each layer admits a unique stable matching:
for each i ∈ [n] the i-th most preferred agent from U is matched with the i-th most preferred agent from W .
Further, such a matching can be computed in O(n) time. Thus, our algorithm proceeds as follows. For each
layer we compute a unique stable matching, and we pick the matching which is stable in the largest number
of layers. Our algorithm returns this matching if it is stable in at least α layers; otherwise, the algorithm
outputs that there exists no α-layer globally stable matchings for the given instance.

7 Open Problems and Conclusions
We have considered a new multi-layer model of preferences in the context of the S TABLE M ARRIAGE
problem. We identified three natural concepts of stability and discussed their relations with each other.
Our results show that the algorithmic problem of finding stable matchings according to each of the three
concepts is, in general, computationally hard. On the positive side, we also managed to identify a number of
natural special cases which are tractable (Table 1 summarizes our results). Interestingly, while in the world
of multi-layer stable matchings the case of two layers already leads to most computational hardness results,
in the world of maximum-cardinality matching in two-layer graphs one obtains polynomial-time solvability,
while in the case of three layers one encounters NP-hardness [14].
Our work provides a rich structure for analyzing computational properties of the problems we considered, and we view our work as only initiating this line of research. Indeed, it directly leads to the following
open questions:
(1) How hard is it to find an α-layer individually stable matching for ⌈ℓ/2⌉ < α < ℓ?
(2) When the preferences of the agents are uniform in each layer and α ≥ ℓ/2 + 1, we have shown
that the decision variant of I NDIVIDUALLY S TABLE M ARRIAGE is solvable in quasi-polynomial time
nO(log n) + O(ℓ · n2 )) which implies that the problem is in the complexity class LOGSNP [43]. It would
be interesting to know whether it is also complete for LOGSNP.2 However, LOGSNP-hardness for our
problem would also imply LOGSNP-hardness for G RAPH I SOMORPHISM (see Theorem 6.5).
(3) When the preferences of the agents are uniform in each layer, how hard is it to search for an α-layer
pair stable matching for arbitrary α > 1 or an α-layer individually stable matching when α < ℓ/2, or in
general when the number of layers is constant.
We also believe that a number of other parameters and special cases can be motivated naturally in the
context of our model, in particular parameters quantifying the degree to which the preferences of the agents
differ. Analogous parameterizations have been studied in computational social choice, for instance for the
NP-hard K EMENY S CORE problem [6, 5].
2

LOGSNP-hardness has been encountered and discussed for natural problems in Computational Social Choice [10, 11].

34

Continuing our research on special cases of input preferences (Section 6), it might be interesting to study
stable matching with multi-layer structured preferences, such as single-peaked [8], single-crossing [44, 41],
and 1-Euclidean [16, 34, 15] preferences. We note that it can be detected in polynomial time whether a preference profile has any of these structure [4, 18, 22, 18, 20, 9, 34] and we refer the reader to Bredereck et al.
[12] and Elkind et al. [21] for an overview of the literature on single-peakedness and single-crossingness.
We also note that Bartholdi III and Trick [4] worked on stable roommates for narcissistic and single-peaked
preferences, while Bredereck et al. [13] extended this line by also studying other structured preferences and
including preferences with ties and incompleteness.
Finally, our multi-modal view on the bipartite variant (S TABLE M ARRIAGE) can be generalized to the
non-bipartite variant (S TABLE ROOMMATES) and the case with incomplete preferences with ties. It would
be interesting to see whether our computational tractability results can transfer to these cases.

References
[1] D. J. Abraham, P. Biró, and D. Manlove. “Almost stable” matchings in the roommates problem. In Proceedings of the Third International Workshop on Approximation and Online Algorithms (WAOA ’05),
pages 1–14, 2005. 2
[2] H. Aziz, P. Biró, T. Fleiner, S. Gaspers, R. de Haan, N. Mattei, and B. Rastegari. Stable matching with
uncertain pairwise preferences. In Proceedings of the 16th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS ’17), pages 344–352. AAAI Press, 2017. 3
[3] L. Babai and E. Luks. Canonical labeling of graphs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC ’83), pages 171–183. ACM Press, 1983. 33, 34
[4] J. J. Bartholdi III and M. Trick. Stable matching with preferences derived from a psychological model.
Operations Research Letters, 5(4):165–169, 1986. 35
[5] N. Betzler, J. Guo, C. Komusiewicz, and R. Niedermeier. Average parameterization and partial kernelization for computing medians. Journal of Computer and System Sciences, 77(4):774–789, 2011.
34
[6] N. Betzler, R. Bredereck, and R. Niedermeier. Theoretical and empirical evaluation of data reduction
for exact kemeny rank aggregation. Autonomous Agents and Multi-Agent Systems, 28(5):721–748,
2014. 34
[7] P. Biró. Applications of matching under preferences. In Trends in Computational Social Choice, pages
345–373. AI Access, 2017. 3
[8] D. Black. The Theory of Committees and Elections. Cambridge University Press, 1958. 35
[9] R. Bredereck, J. Chen, and G. J. Woeginger. A characterization of the single-crossing domain. Social
Choice and Welfare, 41(4):989–998, 2013. 35
[10] R. Bredereck, J. Chen, P. Faliszewski, J. Guo, R. Niedermeier, and G. J. Woeginger. Parameterized
algorithmics for computational social choice: Nine research challenges. Tsinghua Science and Technology, 19(4):358–373, 2014. 34
[11] R. Bredereck, J. Chen, S. Hartung, S. Kratsch, R. Niedermeier, O. Suchý, and G. J. Woeginger. A
multivariate complexity analysis of lobbying in multiple referenda. Journal of Artificial Intellgence
Research, 50:409–446, 2014. 34
35

[12] R. Bredereck, J. Chen, and G. J. Woeginger. Are there any nicely structured preference profiles nearby?
Math. Soc. Sci., 79:61–73, 2016. 35
[13] R. Bredereck, J. Chen, U. P. Finnendahl, and R. Niedermeier. Stable roommate with narcissistic,
single-peaked, and single-crossing preferences. In Proceedings of the 5th International Conference on
Algorithmic Decision Theory (ADT ’17), pages 315–330. Springer, 2017. 35
[14] R. Bredereck, C. Komusiewicz, S. Kratsch, H. Molter, R. Niedermeier, and M. Sorge. Assessing the
computational complexity of multi-layer subgraph detection. In Proceedings of the 10th International
Conference on Algorithms and Complexity (CIAC ’17), pages 128–139. Springer, 2017. 34
[15] J. Chen, K. Pruhs, and G. J. Woeginger. The one-dimensional Euclidean domain: Finitely many
obstructions are not enough. Social Choice and Welfare, 48(2):409–432, 2017. 35
[16] C. H. Coombs. A Theory of Data. John Wiley and Sons, 1964. 35
[17] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and
S. Saurabh. Parameterized Algorithms. Springer, 2015. 26
[18] J. Doignon and J. Falmagne. A polynomial time algorithm for unidimensional unfolding representations. Journal of Algorithms, 16(2):218–233, 1994. 35
[19] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. 26
[20] E. Elkind, P. Faliszewski, and A. Slinko. Clone structures in voters’ preferences. In Proceedings of the
13th ACM Conference on Electronic Commerce (EC ’12), pages 496–513. ACM Press, 2012. 35
[21] E. Elkind, M. Lackner, and D. Peters. Structured preferences. In Trends in Computational Social
Choice, pages 187–207. AI Access, 2017. 35
[22] B. Escoffier, J. Lang, and M. Öztürk. Single-peaked consistency and its complexity. In Proceedings of
the 18th European Conference on Artificial Intelligence (ECAI ’08), pages 366–370. IOS Press, 2008.
35
[23] L. Farczadi, K. Georgiou, and J. Könemann. Stable marriage with general preferences. Theory of
Computing Systems, 59(4):683–699, 2016. 3, 28, 29
[24] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. 26
[25] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 120(5):386–391, 1962. 1, 2, 4, 5
[26] M. R. Garey and D. S. Johnson. Computers and Intractability—A Guide to the Theory of NPCompleteness. W. H. Freeman and Company, 1979. 13
[27] D. Gusfield and R. W. Irving. The Stable Marriage Problem–Structure and Algorithms. Foundations
of Computing Series. MIT Press, 1989. 2, 3, 5
[28] R. W. Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261–272, 1994.
11
[29] R. W. Irving. Optimal stable marriage. In M. Kao, editor, Encyclopedia of Algorithms, pages 1470–
1473. Springer, 2016. 2

36

[30] R. W. Irving. Stable marriage. In M. Kao, editor, Encyclopedia of Algorithms, pages 2060–2064.
Springer, 2016. 2
[31] K. Iwama and S. Miyazaki. A survey of the stable marriage problem and its variants. In International
Conference on Infomatics Education and Research for Knowledge-Circulating Society, pages 131–136,
2008. 3
[32] K. Iwama, S. Miyazaki, Y. Morita, and D. Manlove. Stable marriage with incomplete lists and ties.
In Proceedings of the 26th International Colloquium on Automata, Languages, and Programming
(ICALP ’99), pages 443–452, 1999. 21, 22
[33] B. Klaus, D. F. Manlove, and F. Rossi. Matching under preferences. In Handbook of Computational
Social Choice. Cambridge University Press, 2016. 3
[34] V. Knoblauch. Recognizing one-dimensional Euclidean preference profiles. Journal of Mathematical
Economics, 46(1):1–5, 2010. 35
[35] D. Knuth. Mariages Stables. Les Presses de L’Université de Montréal, 1976. 2, 3, 5
[36] B. Maggs and R. Sitaraman. Algorithmic nuggets in content delivery. SIGCOMM Computer Communication Review, 45(3):52–66, 2015. 2
[37] D. Manlove. Hospitals/residents problem. In M. Kao, editor, Encyclopedia of Algorithms. Springer,
2016. 2
[38] D. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage.
Theoretical Computer Science, 276(1-2):261–279, 2002. 21, 22
[39] D. F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical
Computer Science. WorldScientific, 2013. 2, 3, 5
[40] D. C. McGarvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608–610,
1953. 30
[41] J. A. Mirrlees. An exploration in the theory of optimal income taxation. Review of Economic Studies,
38:175–208, 1971. 35
[42] R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. 26
[43] C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C
dimension. Journal of Computer and System Sciences, 53(2):161–170, 1996. 34
[44] K. W. Roberts. Voting over income tax schedules. Journal of Public Economics, 8(3):329–340, 1977.
35
[45] A. E. Roth and M. A. O. Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and
Analysis. Cambridge University Press, 1992. Part of Econometric Society Monographs. 2
[46] P. Schweitzer. A polynomial-time randomized reduction from tournament isomorphism to tournament
asymmetry. Technical report, arXiv:1704.08529, 2017. 33
[47] F. Wagner. Hardness results for tournament isomorphism and automorphism. In Proceedings of the
32nd International Symposium on Mathematical Foundations of Computer Science (MFCS ’07), pages
572–583. Springer, 2007. 33
[48] B. P. Weems. Bistable versions of the marriages and roommates problems. Journal of Computer and
System Sciences, 59(3):504–520, 1999. 3
37

