Jointly stable matchings

Abstract

In the stable marriage problem, we are given a set of men, a set of women, and each person’s preference list. Our task is to find a stable matching, that is, a matching admitting no unmatched (man, woman)-pair each of which improves the situation by being matched together. It is known that any instance admits at least one stable matching. In this paper, we consider a natural extension where $k (\ge 2)$ sets of preference lists $L_{i}$ ($1 \le i \le k$) over the same set of people are given, and the aim is to find a jointly stable matching, a matching that is stable with respect to all $L_{i}$. We show that the decision problem is NP-complete for the following two restricted cases; (1) $k=2$ and each person’s preference list is of length at most four, and (2) $k=4$, each man’s preference list is of length at most three, and each woman’s preference list is of length at most four. On the other hand, we show that it is solvable in linear time for any k if each man’s preference list is of length at most two (women’s lists can be of unbounded length). We also show that if each woman’s preference lists are same in all $L_{i}$, then the problem can be solved in linear time.

1 Introduction

In this paper, we focus on the stable marriage problem (Gale and Shapley 1962) with incomplete preference lists (SMI). An instance I of SMI is a triple $I=(U, W, L)$, where U and W are the sets of men and women, respectively, such that $|U|=|W| (=n)$, and L is the set of 2npreference lists, one for each person. A person p’s preference list in L is denoted by L(p). Each person’s preference list strictly orders a subset of the members of the opposite gender. If a person p is included in L(q), we say that p is acceptable to q. If p is acceptable to q and vice versa, (p, q) is called an acceptable pair.

A matching is a set of acceptable (man, woman)-pairs in which no person appears more than once. For a matching M, a man m, and a woman w, if $(m,w) \in M$ then we write $M(m)=w$ and $M(w)=m$. If there is no w (respectively, m) such that $(m,w) \in M$, we say that m (respectively, w) is single or unmatched in M. For a matching M, if (i) (m, w) is an acceptable pair, (ii) m is single in M or prefers w to M(m), and (iii) w is single in M or prefers m to M(w), then we say that (m, w) is a blocking pair for M in L, or (m, w) blocksM in L. If there is no blocking pair for M in L, then we say that M is stable in L. It is well-known that any SMI instance admits at least one stable matching (Gale and Shapley 1962).

In this paper, we consider an extension of SMI where two or more sets of preference lists are given. An instance I of the Stable Marriage problem with k Incomplete lists (SMkI) is a $(k+2)$-tuple $I=(U, W, L_{1}, L_{2}, \ldots , L_{k})$, where U and W are the same as above, and each $L_{i}$ is a set of preference lists. It asks if there exists a matching M that is stable in every $L_{i}$. We call such a matching M a jointly stable matching. Let a and b be positive integers. The restriction of $\text{ SM }k\text{ I }$ where the lengths of preference lists of men are at most a and those of women are at most b is denoted by $(a,b)\text{-SM }k\text{ I }$. If a (respectively, b) is $\infty$, it means that the lengths of men’s (respectively, women’s) preference lists are unbounded. By symmetry of men and women, we assume without loss of generality that $a \le b$. Note that, since the number of stable matchings grows exponentially in the size of the input (Irving and Leather 1986; Gusfield and Irving 1989; Thurber 2002; Karlin et al 2018), an algorithm of enumerating all the stable matchings for each $L_{i}$ and computing their intersection is not polynomial-time bounded.

Besides its theoretical interest, the problem has several applications: Consider a scenario of assigning medical residents to hospitals, where each resident needs to take training in three fixed clinical departments, e.g., surgery, pediatrics, and internal medicine, at an assigned hospital. A resident r ranks hospitals according to her preference, but her ranking of hospitals may differ depending on clinical departments. As a result, she has three (possibly different) preference lists over hospitals, $L_{1}(r)$ for surgery, $L_{2}(r)$ for pediatrics, and $L_{3}(r)$ for internal medicine. On the other hand, each clinical department may have its own criteria for ranking residents, so each hospital h has three independent preference lists over residents, $L_{1}(h)$ from surgery, $L_{2}(h)$ from pediatrics, and $L_{3}(h)$ from internal medicine. Clearly a blocking pair in some $L_{i}$ may cause dissatisfaction to the corresponding resident and department, so we want to avoid such an assignment. Another example is a match making of Judo team competition. Suppose that there are five different weight classes, and one team consists of five players, one from each class. As a personal preference, a player p of team T who belongs to the weight class C is interested in only the players of the same class C, who are potential candidates for p’s opponent. Therefore, each team has five preference lists corresponding to weight classes, and a matching avoiding blocking pairs in any class is desirable. Precisely speaking, the first and the second examples may be suitable to the Hospitals/Residents and the stable roommates, respectively, but we consider in this paper the stable marriage model as a first step.

1.1 Our results

On the negative side, we show that $(4,4)\text{-SM }k\text{ I }$ for $k \ge 2$ and $(3,4)\text{-SM }k\text{ I }$ for $k \ge 4$ are NP-complete. On the positive side, we show that $(2,\infty )\text{-SM }k\text{ I }$ is solvable in time O(kn) for any k. These results leave the complexities of $(3,3)\text{-SM }k\text{ I }$ for $k \ge 2$ and $(3,\ell )\text{-SM }k\text{ I }$ for $\ell \ge 4$ and $k=2, 3$ open.

We also show that $\text{ SM }k\text{ I }$ (with unbounded-length preference lists) is solvable in polynomial time if $L_{1}(w)=L_{2}(w)= \cdots =L_{k}(w)$ holds for every woman w. This can be thought of as a case where each woman has only one preference list, and one of its interpretations is a modification of the previous example of assigning residents to hospitals, where each resident has three preference lists as above, but each hospital has one preference list determined by e.g., a personnel director of the hospital, rather than three independent lists coming from each clinical department.

1.2 Related work

After publication of the conference version of this paper, we came to be aware of two closely related works. Aziz et al (2016) consider problems of finding a matching with the highest stability probability under uncertain circumstances. Among several problems they consider, the problem “ExistsCertainlyStableMatching”, which asks to determine whether there is a matching with stability probability 1, under the joint probability model is equivalent to our $\text{ SM }k\text{ I }$. They focus on complete preference lists and show that $\text{ SM }k\text{ I }$ is NP-complete for $k \ge 16$. Their reduction implicitly bounds the length of preference lists to be at most four; hence they essentially show the NP-completeness of $(4,4)\text{-SM }k\text{ I }$ for $k \ge 16$. Chen et al (2018) consider similar problems to ours, where multiple preference lists are given as an input. They introduce three stability notions and investigate their time complexities. One of their problems called the globally stable matching problem is equivalent to our $\text{ SM }k\text{ I }$, and they prove NP-completeness of $\text{ SM }k\text{ I }$ (with unbounded-length preference lists) for $k \ge 2$.

Weems (1999) has introduced the bistable matching problem; given an instance I of the stable marriage problem (where preference lists are complete), let ${\hat{I}}$ be the instance obtained by reversing the ordering of each preference list of I. A matching is bistable if it is stable in both I and ${\hat{I}}$. This is a special case of $\text{ SM }2\text{ I }$ where all the preference lists are complete and $L_{1}(p)$ is a reversed order of $L_{2}(p)$ for every person p. Weems showed an $O(n^{2})$-time algorithm to find a bistable matching or to report that none exists. Sethuraman and Teo (2001) showed that the bistable roommates problem can also be solved in polynomial time. See pages 293–296 of Manlove (2013) for a brief survey.

2 NP-completeness

In this section, we show two hardness results.

Theorem 1

For $k \ge 2$, $(4,4)\text{-SM }k\text{ I }$ is NP-complete.

Proof

It is easy to see that $(4,4)\text{-SM }k\text{ I }$ is in NP. In the following, we show that $(4,4)\text{-SM }2\text{ I }$ is NP-hard. To show the NP-hardness for general k, one may simply set $L_{2}=L_{3}= \cdots = L_{k}$ in the reduction.

We give a polynomial-time reduction from the well-known NP-complete problem 3CNF SAT. The definition of 3CNF SAT is as follows. Let x be a binary variable that takes 1(true) or 0(false). A literal is a variable x or its negation ${\overline{x}}$. A clause is a disjunction of literals, and a Conjunctive Normal Form (CNF) formula is a conjunction of clauses. A 3CNF formula is a CNF formula in which each clause contains at most three literals. An instance of 3CNF SAT is a 3CNF formula f and it asks if there exists an assignment to variables that makes f true. We may assume without loss of generality that each clause contains exactly three literals. (If a clause contains less than three literals, then repeat the same literal.)

Let f be an instance of 3CNF SAT, with variables $x_{1}, x_{2}, \ldots , x_{n}$ and clauses $C_{1}, C_{2}, \ldots , C_{m}$. We construct an instance I of $(4,4)\text{-SM }2\text{ I }$. For each i ($1 \le i \le n$), let $s_{i}$ be the number of occurrences of the variable $x_{i}$. For the jth literal of the variable $x_{i}$ ($1 \le j \le s_{i}$), we introduce two men $a_{i,j}$ and $b_{i,j}$ and two women $c_{i,j}$ and $d_{i,j}$. We call them literal men and literal women. For each clause $C_{\ell }$, we introduce nine men $u_{\ell }^{i}$ ($1 \le i \le 9$) and nine women $v_{\ell }^{i}$ ($1 \le i \le 9$). We call them clause men and clause women. Note that there are 15m men and 15m women in total.

The preference lists of literal people and clause people are given in Figs. 1 and 2, respectively. (Here, for example, the notation “$a: b \ \ c \ \ d$” represents person a’s preference list, where b, c, and d are the first, the second, and the third choices of a, respectively.)

Fig. 1

Preference lists of literal people corresponding to the jth occurrence of the variable $x_{i}$ ($1 \le j \le s_{i}$)

Fig. 2

Preference lists of clause people corresponding to the $\ell$th clause

It might be helpful to see a high-level idea of the reduction before getting into the full construction of preference lists. For the four literal people corresponding to the jth literal of $x_{i}$, we have two choices of matchings, namely $M_{i,j}^{1} = \{ (a_{i,j}, c_{i,j}), (b_{i,j}, d_{i,j}) \}$ and $M_{i,j}^{0} = \{ (a_{i,j}, d_{i,j}), (b_{i,j}, c_{i,j}) \}$. Choosing $M_{i,j}^{1}$ ($M_{i,j}^{0}$, respectively) corresponds to setting the jth occurrence of $x_{i}$ to 1 (0, respectively). For the 18 people corresponding to the clause $C_{\ell }$, we have three choices of matchings,

$$\begin{aligned} M_{\ell }^{1}= & {} \{ (u_{\ell }^{1}, v_{\ell }^{3}), (u_{\ell }^{2}, v_{\ell }^{1}), (u_{\ell }^{3}, v_{\ell }^{2}), (u_{\ell }^{4}, v_{\ell }^{4}), (u_{\ell }^{5}, v_{\ell }^{5}), (u_{\ell }^{6}, v_{\ell }^{6}), (u_{\ell }^{7}, v_{\ell }^{8}), \\&\quad (u_{\ell }^{8}, v_{\ell }^{9}), (u_{\ell }^{9}, v_{\ell }^{7}) \}, \\ M_{\ell }^{2}= & {} \{ (u_{\ell }^{1}, v_{\ell }^{2}), (u_{\ell }^{2}, v_{\ell }^{3}), (u_{\ell }^{3}, v_{\ell }^{1}), (u_{\ell }^{4}, v_{\ell }^{6}), (u_{\ell }^{5}, v_{\ell }^{4}), (u_{\ell }^{6}, v_{\ell }^{5}),\\&\quad (u_{\ell }^{7}, v_{\ell }^{7}), (u_{\ell }^{8}, v_{\ell }^{8}), (u_{\ell }^{9}, v_{\ell }^{9}) \}, \end{aligned}$$

and

$$\begin{aligned} M_{\ell }^{3}= & {} \{ (u_{\ell }^{1}, v_{\ell }^{1}), (u_{\ell }^{2}, v_{\ell }^{2}), (u_{\ell }^{3}, v_{\ell }^{3}), (u_{\ell }^{4}, v_{\ell }^{5}), (u_{\ell }^{5},v_{\ell }^{6}),\\&\quad (u_{\ell }^{6}, v_{\ell }^{4}), (u_{\ell }^{7}, v_{\ell }^{9}), (u_{\ell }^{8}, v_{\ell }^{7}), (u_{\ell }^{9}, v_{\ell }^{8}) \}, \end{aligned}$$

depicted in Figs. 5, 6, and 7, respectively, in “Appendix”. Choosing $M_{\ell }^{1}$, $M_{\ell }^{2}$, and $M_{\ell }^{3}$, respectively, corresponds to satisfying $C_{\ell }$ by its first, second, and third literal. Note then that main conditions for CNF SAT are (1) the jth occurrence of $x_{i}$ must have the same value for all j, and (2) each $C_{\ell }$ is satisfied if and only if at least one of its literals is true. To simulate these conditions by $(4,4)\text{-SM }2\text{ I }$, we connect gadgets using some men and women in such a way that if some illegal choices of partial matchings are made, then there arises a blocking pair. The persons at the second position of $L_{2}$ in Fig. 1 exist for condition (1). They come from the literal gadgets corresponding to the $(j-1)$th and the $(j+1)$th occurrences of the same variable $x_{i}$, and play a role of connecting literal gadgets like a chain, so that if $M_{i,j_{1}}^{1}$ and $M_{i,j_{2}}^{0}$ are chosen for some $j_{1}$ and $j_{2}$, then there arises a blocking pair. Two persons $V_{i,j}$ and $U_{i,j}$ in $L_{1}$ of Fig. 1 and six persons $D_{\ell , t}$ and $B_{\ell , t}$ ($t=1, 2, 3$) in $L_{1}$ of Fig. 2 exist for condition (2). They are placed in such a way that if (i) we attempt to satisfy $C_{\ell }$ by its tth literal (i.e., $M_{\ell }^{t}$ is chosen), but (ii) the assignment to this literal is 0 by the choice in the literal gadget side, then there arises a blocking pair.

Now we formally explain how to construct preference lists. In $a_{i,1}$ and $d_{i,1}$’s preference lists of $L_{2}$ in Fig. 1, $c_{i,j-1}$ and $b_{i,j-1}$ are null; hence their preference lists are of length two. Similarly, in $b_{i,s_{i}}$ and $c_{i,s_{i}}$’s preference lists of $L_{2}$, $d_{i,j+1}$ and $a_{i,j+1}$ are null. We then explain $U_{i,j}$ and $V_{i,j}$ in Fig. 1. Suppose that the jth occurrence of $x_{i}$ is the tth literal of the clause $C_{\ell }$. If this literal is positive, then $U_{i,j}$ is null and $V_{i,j}=v_{\ell }^{4}$ if $t=1$, $V_{i,j}=v_{\ell }^{7}$ if $t=2$, and $V_{i,j}=v_{\ell }^{1}$ if $t=3$. If it is negative, then $V_{i,j}$ is null and $U_{i,j}=u_{\ell }^{1}$ if $t=1$, $U_{i,j}=u_{\ell }^{4}$ if $t=2$, and $U_{i,j}=u_{\ell }^{7}$ if $t=3$. Finally, we explain $B_{\ell ,1}, B_{\ell ,2}, B_{\ell ,3}, D_{\ell ,1}, D_{\ell ,2}$, and $D_{\ell ,3}$ in Fig. 2. Suppose that, for $t=1, 2, 3$, the tth literal of the clause $C_{\ell }$ is the jth occurrence of $x_{i}$. If this literal is positive, then $D_{\ell , t}$ is null and $B_{\ell , t}=b_{i,j}$; otherwise, $B_{\ell , t}$ is null and $D_{\ell , t}=d_{i,j}$. Now the reduction is completed. It is not hard to see that the reduction can be performed in polynomial time and each person’s preference list is of length at most four.

We then proceed to the correctness proof. Suppose that f is satisfiable and let T be a satisfying assignment. We will construct a jointly stable matching M for I. For each i, if $T(x_{i})=1$, then we let $M_{i,j}^{1} \subseteq M$ for all j, and if $T(x_{i})=0$, then we let $M_{i,j}^{0} \subseteq M$ for all j. For each $\ell$, suppose that the clause $C_{\ell }$ is satisfied by its tth literal (if there are more than one true literal, choose one arbitrarily). Then we let $M_{\ell }^{t}\subseteq M$. We next show that M is jointly stable.

Lemma 1

The matching M constructed as above is jointly stable.

Proof

Consider literal people corresponding to $x_{i}$, namely $a_{i,j}$, $b_{i,j}$, $c_{i,j}$, and $d_{i,j}$ ($1 \le j \le s_{i}$). If $T(x_{i})=1$, then all the men are matched with their first choices in both $L_{1}$ and $L_{2}$. Similarly, if $T(x_{i})=0$, then all the women are matched with their first choices. Therefore, no blocking pair arises within literal people corresponding to the same variable. Since literal people corresponding to different variables are unacceptable to each other, no blocking pair occurs between them.

As for the 18 people corresponding to the clause $C_{\ell }$, we can easily verify that, in any of $M_{\ell }^{1}$, $M_{\ell }^{2}$, and $M_{\ell }^{3}$, no blocking pair arises among them by investigating Figs. 5, 6 and 7. Also, since clause people corresponding to different clauses are unacceptable to each other, no blocking pair occurs between them.

Finally, we consider a possibility of a blocking pair between a literal person and a clause person. Consider a clause $C_{\ell }$. First, suppose that $M_{\ell }^{1}$ is chosen as a part of M. By construction of M, this means that the clause $C_{\ell }$ is satisfied by its first literal. Suppose that this literal is the jth occurrence of $x_{i}$, and that it is a positive literal. Then by construction of preference lists, $D_{\ell ,1}$ is null and $B_{\ell ,1}=b_{i,j}$, so only the possible blocking pair is $(b_{i,j}, v_{\ell ,4})$ in $L_{1}$. However, since $C_{\ell }$ is satisfied by the first literal, it must be the case that $T(x_{i})=1$. By construction of M, $M_{i,j}^{1} \subseteq M$ and hence $b_{i,j}$ is matched with his first choice woman in $L_{1}$, so he cannot form a blocking pair. Now suppose that the first literal of $C_{\ell }$ is the jth occurrence of $x_{i}$ and it is a negative literal. Then $B_{\ell ,1}$ is null and $D_{\ell ,1}=d_{i,j}$, so only the possible blocking pair is $(u_{\ell ,1}, d_{i,j})$ in $L_{1}$. However, since $C_{\ell }$ is satisfied by the first literal, we have that $T(x_{i})=0$ and hence $d_{i,j}$ is matched with her first choice man in $L_{1}$, so $d_{i,j}$ cannot form a blocking pair. For the other two cases, that is, the case that $M_{\ell }^{2}$ is chosen and that $M_{\ell }^{3}$ is chosen, we can show that there is no blocking pair by a similar argument. $\square$

Conversely, suppose that I admits a jointly stable matching M. We construct a satisfying assignment T of f. First, we see basic properties of M.

Lemma 2

For each i, either $M_{i,j}^{1} \subseteq M$ for all j, or $M_{i,j}^{0} \subseteq M$ for all j.

Proof

We first show that, for each i and j, either $M_{i,j}^{1} \subseteq M$ or $M_{i,j}^{0} \subseteq M$. Suppose not. Since $c_{i,j}$ and $d_{i,j}$ are the only acceptable men to $a_{i,j}$ and $b_{i,j}$ in $L_{1}$ and $L_{2}$ in common, at least one of $a_{i,j}$ and $b_{i,j}$, say $m_{i,j}$, is single in M. For the same reason, at least one of $c_{i,j}$ and $d_{i,j}$, say $w_{i,j}$, is single in M. Then $(m_{i,j}, w_{i,j})$ blocks M (in both $L_{1}$ and $L_{2}$), a contradiction.

Now suppose that the statement of the lemma is false. Then there are i and j ($1 \le j \le s_{i}-1$) such that (i) $M_{i,j}^{1} \subseteq M$ and $M_{i,j+1}^{0} \subseteq M$ or (ii) $M_{i,j}^{0} \subseteq M$ and $M_{i,j+1}^{1} \subseteq M$. In case of (i), $(a_{i,j+1}, c_{i,j})$ blocks M in $L_{2}$, while in case of (ii), $(b_{i,j}, d_{i,j+1})$ blocks M in $L_{2}$, a contradiction. $\square$

Lemma 3

For each $\ell$, either $M_{\ell }^{1}\subseteq M$, $M_{\ell }^{2}\subseteq M$, or $M_{\ell }^{3}\subseteq M$.

Proof

Suppose that there is a man $m_{\ell } \in \{ u_{\ell }^{1}, u_{\ell }^{2}, u_{\ell }^{3} \}$ who is not matched with any of $v_{\ell }^{1}$, $v_{\ell }^{2}$, and $v_{\ell }^{3}$ in M. Note that $D_{\ell ,1}$ is a literal woman (if not null), who is not acceptable to $u_{\ell }^{1}$ in $L_{2}$. Hence it must be the case that $m_{\ell }$ is single in M. By a similar argument, there is a woman $w_{\ell } \in \{ v_{\ell }^{1}, v_{\ell }^{2}, v_{\ell }^{3} \}$ who is single in M. Then $(m_{\ell }, w_{\ell })$ blocks M in $L_{1}$ and $L_{2}$, a contradiction. Therefore, $u_{\ell }^{1}$, $u_{\ell }^{2}$, and $u_{\ell }^{3}$ are matched with $v_{\ell }^{1}$, $v_{\ell }^{2}$, and $v_{\ell }^{3}$ in M. There are six possible ways, namely,

$$\begin{aligned} X_{\ell }^{1} = \{ (u_{\ell }^{1}, v_{\ell }^{1}), (u_{\ell }^{2}, v_{\ell }^{2}), (u_{\ell }^{3}, v_{\ell }^{3}) \}\mathrm{,} \ X_{\ell }^{2} = \{ (u_{\ell }^{1}, v_{\ell }^{2}), (u_{\ell }^{2}, v_{\ell }^{3}), (u_{\ell }^{3}, v_{\ell }^{1}) \}\mathrm{,} \\ \nonumber X_{\ell }^{3} = \{ (u_{\ell }^{1}, v_{\ell }^{3}), (u_{\ell }^{2}, v_{\ell }^{1}), (u_{\ell }^{3}, v_{\ell }^{2}) \}\mathrm{,} X_{\ell }^{4} = \{ (u_{\ell }^{1}, v_{\ell }^{1}), (u_{\ell }^{2}, v_{\ell }^{3}), (u_{\ell }^{3}, v_{\ell }^{2}) \}\mathrm{,} \\ \nonumber X_{\ell }^{5} = \{ (u_{\ell }^{1}, v_{\ell }^{2}), (u_{\ell }^{2}, v_{\ell }^{1}), (u_{\ell }^{3}, v_{\ell }^{3}) \}\mathrm{,} \ \mathrm{and} \ X_{\ell }^{6} = \{ (u_{\ell }^{1}, v_{\ell }^{3}), (u_{\ell }^{2}, v_{\ell }^{2}), (u_{\ell }^{3}, v_{\ell }^{1}) \}\mathrm{.} \end{aligned}$$

It is easy to see that $X_{\ell }^{4}$ is blocked by $(u_{\ell }^{3}, v_{\ell }^{1})$, $X_{\ell }^{5}$ is blocked by $(u_{\ell }^{2}, v_{\ell }^{3})$, and $X_{\ell }^{6}$ is blocked by $(u_{\ell }^{1}, v_{\ell }^{2})$ in $L_{1}$. Therefore, only $X_{\ell }^{1}$, $X_{\ell }^{2}$, and $X_{\ell }^{3}$ can be a part of M. The same argument applies to $u_{\ell }^{4}$, $u_{\ell }^{5}$, $u_{\ell }^{6}$, $v_{\ell }^{4}$, $v_{\ell }^{5}$, $v_{\ell }^{6}$ and $u_{\ell }^{7}$, $u_{\ell }^{8}$, $u_{\ell }^{9}$, $v_{\ell }^{7}$, $v_{\ell }^{8}$, $v_{\ell }^{9}$, implying that only

$$\begin{aligned} Y_{\ell }^{1} = \{ (u_{\ell }^{4}, v_{\ell }^{4}), (u_{\ell }^{5}, v_{\ell }^{5}), (u_{\ell }^{6}, v_{\ell }^{6}) \}\mathrm{,} \ Y_{\ell }^{2} = \{ (u_{\ell }^{4}, v_{\ell }^{5}), (u_{\ell }^{5}, v_{\ell }^{6}), (u_{\ell }^{6}, v_{\ell }^{4}) \}\mathrm{,} \\ \nonumber Y_{\ell }^{3} = \{ (u_{\ell }^{4}, v_{\ell }^{6}), (u_{\ell }^{5}, v_{\ell }^{4}), (u_{\ell }^{6}, v_{\ell }^{5}) \}\mathrm{,} \ Z_{\ell }^{1} = \{ (u_{\ell }^{7}, v_{\ell }^{7}), (u_{\ell }^{8}, v_{\ell }^{8}), (u_{\ell }^{9}, v_{\ell }^{9}) \}\mathrm{,} \\ \nonumber Z_{\ell }^{2} = \{ (u_{\ell }^{7}, v_{\ell }^{8}), (u_{\ell }^{8}, v_{\ell }^{9}), (u_{\ell }^{9}, v_{\ell }^{7}) \}\mathrm{,} \ \mathrm{and} \ Z_{\ell }^{3} = \{ (u_{\ell }^{7}, v_{\ell }^{9}), (u_{\ell }^{8}, v_{\ell }^{7}), (u_{\ell }^{9}, v_{\ell }^{8}) \} \end{aligned}$$

are valid.

Table 1 27 matchings and corresponding blocking pairs in $L_{2}$

Therefore, there are 27 possible combinations. Note that $M_{\ell }^{1} = X_{\ell }^{3} \cup Y_{\ell }^{1} \cup Z_{\ell }^{2}$, $M_{\ell }^{2} = X_{\ell }^{2} \cup Y_{\ell }^{3} \cup Z_{\ell }^{1}$, and $M_{\ell }^{3} = X_{\ell }^{1} \cup Y_{\ell }^{2} \cup Z_{\ell }^{3}$. We show that the remaining 24 matchings are unstable in $L_{2}$. Table 1 shows 27 matchings in “Matching” columns and corresponding blocking pairs of 24 matchings in “BP” columns. This completes the proof. $\square$

By Lemma 2, either $M_{i,j}^{1} \subseteq M$ for all j or $M_{i,j}^{0} \subseteq M$ for all j holds. In the former case, we set $T(x_{i})=1$, otherwise, we set $T(x_{i})=0$. We show that T satisfies f. Suppose not, and let $C_{\ell }$ be an unsatisfied clause. For $t=1, 2, 3$, let the tth literal of $C_{\ell }$ be the $j_{t}$th occurrence of the variable $x_{i_{t}}$. We will show three claims:

Claim 1

$M_{\ell }^{1} \not \subseteq M$. Consider the first literal of $C_{\ell }$. Suppose that it appears positively in $C_{\ell }$. Then by construction of the preference lists, the lists of $b_{i_{1},j_{1}}$ and $v_{\ell }^{4}$ in $L_{1}$ are as follows:

$$\begin{aligned} b_{i_{1},j_{1}}: \ d_{i_{1},j_{1}} \ v_{\ell }^{4} \ c_{i_{1},j_{1}} \quad v_{\ell }^{4}: \ u_{\ell }^{5} \ u_{\ell }^{6} \ b_{i_{1},j_{1}} \ u_{\ell }^{4} \end{aligned}$$

Since $C_{\ell }$ is unsatisfied, $T(x_{i_{1}})=0$ and so by construction of T, $M_{i_{1},j_{1}}^{0} \subseteq M$, i.e., $M(b_{i_{1},j_{1}})=c_{i_{1},j_{1}}$. If $M_{\ell }^{1} \subseteq M$, then $M(v_{\ell }^{4})=u_{\ell }^{4}$ and hence $(b_{i_{1},j_{1}}, v_{\ell }^{4})$ blocks M in $L_{1}$, a contradiction.

Next, suppose that the first literal of $C_{\ell }$ is negative, i.e., $\overline{x_{i_{1}}}$. Then by construction, the preference lists of $d_{i_{1},j_{1}}$ and $u_{\ell }^{1}$ in $L_{1}$ are as follows:

$$\begin{aligned} u_{\ell }^{1}: \ v_{\ell }^{1} \ v_{\ell }^{2} \ d_{i_{1},j_{1}} \ v_{\ell }^{3} \quad d_{i_{1},j_{1}}: \ a_{i_{1},j_{1}} \ u_{\ell }^{1} \ b_{i_{1},j_{1}} \end{aligned}$$

Since $C_{\ell }$ is unsatisfied, $T(x_{i_{1}})=1$ and so by construction of T, $M_{i_{1},j_{1}}^{1} \subseteq M$, i.e., $M(d_{i_{1},j_{1}})=b_{i_{1},j_{1}}$. If $M_{\ell }^{1} \subseteq M$, then $M(u_{\ell }^{1})=v_{\ell }^{3}$ and hence $(u_{\ell }^{1}, d_{i_{1},j_{1}})$ blocks M in $L_{1}$, a contradiction. Therefore, we can conclude that $M_{\ell }^{1} \not \subseteq M$.

Claim 2

$M_{\ell }^{2} \not \subseteq M$. Consider the second literal of $C_{\ell }$, and first suppose that it is a positive literal, i.e., $x_{i_{2}}$. Then by construction, the preference lists of $b_{i_{2},j_{2}}$ and $v_{\ell }^{7}$ in $L_{1}$ are as follows:

$$\begin{aligned} b_{i_{2},j_{2}}: \ d_{i_{2},j_{2}} \ v_{\ell }^{7} \ c_{i_{2},j_{2}} \quad v_{\ell }^{7}: \ u_{\ell }^{8} \ u_{\ell }^{9} \ b_{i_{2},j_{2}} \ u_{\ell }^{7} \end{aligned}$$

Since $C_{\ell }$ is unsatisfied, $T(x_{i_{2}})=0$ and hence by construction of T, $M_{i_{2},j_{2}}^{0} \subseteq M$, i.e., $M(b_{i_{2},j_{2}})=c_{i_{2},j_{2}}$. If $M_{\ell }^{2} \subseteq M$, then $M(v_{\ell }^{7})=u_{\ell }^{7}$ and hence $(b_{i_{2},j_{2}}, v_{\ell }^{7})$ blocks M in $L_{1}$, a contradiction.

Next, suppose that the second literal of $C_{\ell }$ is $\overline{x_{i_{2}}}$. Then by construction, the preference lists of $d_{i_{2},j_{2}}$ and $u_{\ell }^{4}$ in $L_{1}$ are as follows:

$$\begin{aligned} u_{\ell }^{4}: \ v_{\ell }^{4} \ v_{\ell }^{5} \ d_{i_{2},j_{2}} \ v_{\ell }^{6} \quad d_{i_{2},j_{2}}: \ a_{i_{2},j_{2}} \ u_{\ell }^{4} \ b_{i_{2},j_{2}} \end{aligned}$$

Since $C_{\ell }$ is unsatisfied, $T(x_{i_{2}})=1$ and by construction of T, $M_{i_{2},j_{2}}^{1} \subseteq M$, i.e., $M(d_{i_{2},j_{2}})=b_{i_{2},j_{2}}$. If $M_{\ell }^{2} \subseteq M$, then $M(u_{\ell }^{4})=v_{\ell }^{6}$ and hence $(u_{\ell }^{4}, d_{i_{2},j_{2}})$ blocks M in $L_{1}$, a contradiction. Therefore, we can conclude that $M_{\ell }^{2} \not \subseteq M$.

Claim 3

$M_{\ell }^{3} \not \subseteq M$. Consider the third literal of $C_{\ell }$. First, suppose that it is a positive literal $x_{i_{3}}$. Then by construction, the preference lists of $b_{i_{3},j_{3}}$ and $v_{\ell }^{1}$ in $L_{1}$ are as follows:

$$\begin{aligned} b_{i_{3},j_{3}}: \ d_{i_{3},j_{3}} \ v_{\ell }^{1} \ c_{i_{3},j_{3}} \quad v_{\ell }^{1}: \ u_{\ell }^{2} \ u_{\ell }^{3} \ b_{i_{3},j_{3}} \ u_{\ell }^{1} \end{aligned}$$

Since $C_{\ell }$ is unsatisfied, $T(x_{i_{3}})=0$ and thus by construction of T, $M_{i_{3},j_{3}}^{0} \subseteq M$, i.e., $M(b_{i_{3},j_{3}})=c_{i_{3},j_{3}}$. If $M_{\ell }^{3} \subseteq M$, then $M(v_{\ell }^{1})=u_{\ell }^{1}$ and hence $(b_{i_{3},j_{3}}, v_{\ell }^{1})$ blocks M in $L_{1}$, a contradiction.

Next, suppose that the third literal of $C_{\ell }$ is negative, i.e., $\overline{x_{i_{3}}}$. Then by construction, the preference lists of $d_{i_{3},j_{3}}$ and $u_{\ell }^{7}$ in $L_{1}$ are as follows:

$$\begin{aligned} u_{\ell }^{7}: \ v_{\ell }^{7} \ v_{\ell }^{8} \ d_{i_{3},j_{3}} \ v_{\ell }^{9} \quad d_{i_{3},j_{3}}: \ a_{i_{3},j_{3}} \ u_{\ell }^{7} \ b_{i_{3},j_{3}} \end{aligned}$$

Since $C_{\ell }$ is unsatisfied, $T(x_{i_{3}})=1$ and by construction of T, $M_{i_{3},j_{3}}^{1} \subseteq M$, i.e., $M(d_{i_{3},j_{3}})=b_{i_{3},j_{3}}$. If $M_{\ell }^{3} \subseteq M$, then $M(u_{\ell }^{7})=v_{\ell }^{9}$ and hence $(u_{\ell }^{7}, d_{i_{3},j_{3}})$ blocks M in $L_{1}$, a contradiction. Therefore, we can conclude that $M_{\ell }^{3} \not \subseteq M$.

From Claims 1, 2, and 3, none of $M_{\ell }^{1}$, $M_{\ell }^{2}$, and $M_{\ell }^{3}$ can be a part of M, but this contradicts Lemma 3. Hence we conclude that T satisfies f, which completes the proof of Theorem 1. $\square$

By modifying the reduction in the proof of Theorem 1, we can show the NP-completeness of another restricted case.

Theorem 2

For $k \ge 4$, $(3,4)\text{-SM }k\text{ I }$ is NP-complete.

Proof

We assume that the readers have read the proof of Theorem 1, and give only a proof sketch. It is easy to see that $(3,4)\text{-SM }k\text{ I }$ is in NP. It suffices to show the NP-hardness of $(3,4)\text{-SM }4\text{ I }$, and to achieve this, we give a polynomial-time reduction from 3CNF SAT.

Let f be an instance of 3CNF SAT, consisting of variables $x_{1}, x_{2}, \ldots , x_{n}$ and clauses $C_{1}, C_{2}, \ldots , C_{m}$. We construct an instance I of $(3,4)\text{-SM }4\text{ I }$. For each i ($1 \le i \le n$), let $s_{i}$ be the number of occurrences of the variable $x_{i}$. For the jth literal of the variable $x_{i}$ ($1 \le j \le s_{i}$), we introduce two literal men$a_{i,j}$ and $b_{i,j}$ and two literal women$c_{i,j}$ and $d_{i,j}$. For each clause $C_{\ell }$, we introduce three clause men$u_{\ell }^{i}$ ($1 \le i \le 3$) and three clause women$v_{\ell }^{i}$ ($1 \le i \le 3$). Note that there are 9m men and 9m women in total.

Fig. 3

Preference lists of literal people corresponding to the jth occurrence of the variable $x_{i}$ ($1 \le j \le s_{i}$)

The preference lists of literal people are given in Fig. 3. As in the previous proof, their lists restrict a part of stable matchings to $M_{i,j}^{1} = \{ (a_{i,j}, c_{i,j}), (b_{i,j}, d_{i,j}) \}$ and $M_{i,j}^{0} = \{ (a_{i,j}, d_{i,j}), (b_{i,j}, c_{i,j}) \}$. The structures of $L_{1}$ through $L_{3}$ depend on whether the corresponding literal (i.e., the jth occurrence of $x_{i}$) is positive or negative. If it is positive, then selecting $M_{i,j}^{0}$ matches the man $b_{i,j}$ to the worse partner, which yields the risk of $b_{i,j}$ forming a blocking pair with $V_{i,j}^{k}$, while if it is negative, then selecting $M_{i,j}^{1}$ does so. Suppose that the jth occurrence of $x_{i}$ is the tth literal of the clause $C_{\ell }$. Then $V_{i,j}^{k}$ is defined as $v_{\ell }^{1}$ if $k=t$ and it is null if $k \ne t$. $L_{4}$ is the same as $L_{2}$ in Fig. 1, whose role is to ensure that for each i, either $M_{i,j}^{1} \subseteq M$ for all j, or $M_{i,j}^{0} \subseteq M$ for all j, as was shown in Lemma 2.

The preference lists of clause people are given in Fig. 4. The role of $L_{4}$ is to restrict a part of stable matchings to $M_{\ell }^{1} = \{ (u_{\ell }^{1}, v_{\ell }^{1}), (u_{\ell }^{2}, v_{\ell }^{2}), (u_{\ell }^{3}, v_{\ell }^{3}) \}$, $M_{\ell }^{2} = \{ (u_{\ell }^{1}, v_{\ell }^{2}), (u_{\ell }^{2}, v_{\ell }^{3}), (u_{\ell }^{3}, v_{\ell }^{1}) \}$, and $M_{\ell }^{3} = \{ (u_{\ell }^{1}, v_{\ell }^{3}), (u_{\ell }^{2}, v_{\ell }^{1}), (u_{\ell }^{3}, v_{\ell }^{2})\}$. Suppose that, for $t=1, 2, 3$, the tth literal of the clause $C_{\ell }$ is the jth occurrence of $x_{i}$. Then $B_{\ell , t}$ is defined as $b_{i,j}$. Now the reduction is completed. It is not hard to see that the reduction can be performed in polynomial time and each man’s (woman’s) preference list is of length at most three (at most four, respectively).

Fig. 4

Preference lists of clause people corresponding to the $\ell$th clause

Finally, we briefly explain the correctness of the reduction. Suppose that f is satisfiable and let T be a satisfying assignment. We will construct a jointly stable matching M for I as follows: For each i, if $T(x_{i})=1$, then we let $M_{i,j}^{1} \subseteq M$ for all j, and if $T(x_{i})=0$, then we let $M_{i,j}^{0} \subseteq M$ for all j. For each $\ell$, if the clause $C_{\ell }$ is satisfied by its tth literal, then we let $M_{\ell }^{t}\subseteq M$. It is not hard to see that M is jointly stable.

Conversely, suppose that I admits a jointly stable matching M. We construct a satisfying assignment T of f in a straightforward manner. That is, we know that for each i, $M_{i,j}^{1} \subseteq M$ for all j, or $M_{i,j}^{0} \subseteq M$ for all j. In the former case, we set $T(x_{i})=1$, whereas in the latter case, we set $T(x_{i})=0$. In a similar way as the proof of Theorem 1, we can observe that T satisfies f. $\square$

In the above reductions, we have exploited existence of pairs that are acceptable in some $L_{i}$ but not in $L_{j}$ ($j \ne i$). Then one may be curious about whether $\text{ SM }k\text{ I }$ is solvable in polynomial time if the set of acceptable pairs is the same in all $L_{i}$. However, this is unlikely, as shown in the following corollary. Let $\text{ SM }k$ denote the special case of $\text{ SM }k\text{ I }$ where all the preference lists are complete. Clearly $\text{ SM }k$ satisfies the above mentioned condition.

Corollary 1

For $k \ge 2$, $\text{ SM }k$ is NP-complete.

Proof

Apparently $\text{ SM }k \in$ NP. For the NP-hardness, in the reduction given in the proof of Theorem 1, make every preference list complete by appending missing persons to the tail of the list in an arbitrary order. It is not hard to see that the same correctness proof (with slight modifications) applies. $\square$

3 Tractable cases

3.1 Length-two preferences lists of one side

Our first positive result is for instances in which the length of preference lists of one side, say men’s side, is bounded by two. In this subsection, we assume without loss of generality that acceptability is mutual, i.e., m is acceptable to w in $L_{i}$ if and only if w is acceptable to m in $L_{i}$. This is because, if for example m is acceptable to w while w is not acceptable to m, then (m, w) can neither be a part of a matching nor a blocking pair. Hence we may remove m from w’s list safely, without changing the set of jointly stable matchings. This preprocessing can be done in time linear in the total length of the input preference lists.

However, even if (m, w) is an acceptable pair in $L_{i}$ but is an unacceptable pair in $L_{j}$ ($j \ne i$), we must not remove m and w from each other’s list in $L_{i}$. This is because, although (m, w) cannot be a pair in a jointly stable matching, it may block some matching in $L_{i}$ and removing it may change the set of jointly stable matchings.

The proof of Theorem 3 exploits a partially-ordered set (poset) of rotations and its relation to the whole set of stable matchings. These structural properties were originally studied for complete preference lists, but they can be extended easily and naturally to incomplete preference lists. Here we give brief explanations about them. See (Gusfield and Irving 1989) for more detail. Readers who are familiar with these notions may skip the following two paragraphs.

Let I be an instance of SMI and M be a stable matching for I. For a man m matched in M, $s_{M}(m)$ denotes the first woman w in m’s list such that w is matched in M and w prefers m to M(w). Note that m prefers M(m) to $s_{M}(m)$; otherwise, $(m, s_{M}(m))$ blocks M. Also, $next_{M}(m)$ denotes the partner of $s_{M}(m)$ in M, that is, $next_{M}(m) = M(s_{M}(m))$. Let $\rho = (m_{0}, w_{0}), (m_{1}, w_{1}), \ldots , (m_{r-1}, w_{r-1}) (r \ge 2)$ be a sequence of pairs such that each pair in $\rho$ is contained in M and $m_{i+1} = next_{M}(m_{i})$ for each i, where $i+1$ is taken modulo r. Then we call $\rho$ a rotation exposed inM. By eliminating a rotation $\rho$ from M, we mean to replace pairs $(m_{0}, w_{0}), (m_{1}, w_{1}), \ldots , (m_{r-1}, w_{r-1})$ by $(m_{0}, w_{1}), (m_{1}, w_{2}), \ldots , (m_{r-1}, w_{0})$ in M. The resulting matching, denoted by $M / \rho$, is also stable in I. Note that each man included in $\rho$ has a worse partner in $M / \rho$ than in M.

Let $\varPi$ be the set of rotations that are exposed in one or more stable matchings for I. We can define a partial order $\preceq$ on $\varPi$, and $(\varPi , \preceq )$ is called the rotation poset of I. A subset $P \subseteq \varPi$ is called a closed subset of $\varPi$ if for any $\rho \in P$ and any $\rho ' \preceq \rho$, $\rho ' \in P$ holds. There is a one-to-one correspondence between the stable matchings for I and the closed subsets of $\varPi$ by the mapping defined as follows. Let $M_{0}$ be the man-optimal stable matching of I (which is guaranteed to exist and can be found by the men-oriented Gale-Shapley algorithm in time linear in the total length of preference lists). Let P be a closed subset of $\varPi$. If we eliminate rotations in P one by one according to the order $\preceq$, we obtain a stable matching for I. Conversely, any stable matching for I is obtained by this procedure for some closed subset of $\varPi$. In particular, the empty set corresponds to the man-optimal stable matching and the whole set $\varPi$ corresponds to the woman-optimal stable matching (which is the opposite extreme to the man-optimal stable matching). The rotation poset can be constructed in time linear in the total length of preference lists (Sect. 3.3 of Gusfield and Irving 1989).

Theorem 3

$(2,\infty )\text{-SM }k\text{ I }$ is solvable in time O(kn).

Proof

We first compute the man-optimal stable matchings $M_{i}$ for $L_{i}$ ($i=1, 2, \ldots , k$) using the men-oriented version of the Gale-Shapley algorithm. For each $L_{i}$, any stable matching leaves the same set of men and women unmatched (Gale and Sotomayor 1985). Thus if there are i and j ($i \ne j$) such that the set of matched people in $M_{i}$ and that in $M_{j}$ are different, then we can immediately answer “no”. In the following, we assume that the sets of matched people are the same in all $M_{i}$.

For each i, we compute all the rotations $\rho _{1}^{i}, \rho _{2}^{i}, \ldots , \rho _{n_{i}}^{i}$ with respect to $L_{i}$. Since the length of each man’s preference list is at most two, each man is contained in at most one rotation. This means that all the rotations are mutually incomparable in the rotation poset. Hence there is a one-to-one correspondence between the set of stable matchings for $L_{i}$ and the power set of $\{ \rho _{1}^{i}, \rho _{2}^{i}, \ldots , \rho _{n_{i}}^{i} \}$: the subset $S \subseteq \{ \rho _{1}^{i}, \rho _{2}^{i}, \ldots , \rho _{n_{i}}^{i} \}$ corresponds to the stable matching $M_{i,S}$ obtained by eliminating all the rotations in S from $M_{i}$. Consider a man m who is matched in $M_{i}$. If m is not included in a rotation, his partner is the same in all the stable matchings of $L_{i}$. If he is included in a rotation $\rho _{j}^{i}$, then he is matched in $M_{i,S}$ with his first choice if $\rho _{j}^{i} \not \in S$ and with his second choice if $\rho _{j}^{i} \in S$.

The remaining task is to check if there are k subsets $S_{i} \subseteq \{ \rho _{1}^{i}, \rho _{2}^{i}, \ldots , \rho _{n_{i}}^{i} \}$ ($1 \le i \le k$) such that $M_{1,S_{1}}=M_{2,S_{2}}= \cdots =M_{k,S_{k}}$. For this purpose, we introduce a binary variable $x_{j}^{i}$ for $\rho _{j}^{i}$ ($1 \le i \le k$, $1 \le j \le n_{i}$), where $x_{j}^{i}=1$ means to put $\rho _{j}^{i}$ in $S_{i}$. We then construct a 2CNF SAT instance as follows.

For each man m who is matched in $M_{1}$ (and equivalently in all $M_{i}$), we fix the value of variables or construct 2CNF clauses to ensure that m’s partners coincide in all $M_{1,S_{1}}, M_{2,S_{2}}, \ldots , M_{k,S_{k}}$. If (m, w) is a pair in some stable matching of L, w is called m’s stable partner in L. Also, if w is m’s stable partner in all $L_{i}$, w is called m’s jointly stable partner. If m has no jointly stable partner, we immediately output “no”. If m has one jointly stable partner w, then for each i, we enforce the variable (if any) to match m with w in $M_{i,S_{i}}$. Namely, if m is not included in a rotation, then there is no variable and we do nothing. If m is included in a rotation $\rho _{j}^{i}$ and w is his first (second) choice in $L_{i}$, then we set $x_{j}^{i}=0$ ($x_{j}^{i}=1$). During this course, if some variable is fixed differently, then we immediately output “no”. Finally, suppose that m has two jointly stable partners $w'$ and $w''$. This means that for each i, $L_{i}(m)$ contains both $w'$ and $w''$ and m is included in a rotation of $L_{i}$. Let $\rho _{j_{i}}^{i}$ be the rotation that includes m. For each $i=2, \ldots , k$, we construct two clauses as follows: If the orders of $w'$ and $w''$ are same in $L_{1}(m)$ and $L_{i}(m)$, then we construct $(x_{j_{1}}^{1} \vee \overline{x_{j_{i}}^{i}})$ and $(\overline{x_{j_{1}}^{1}} \vee x_{j_{i}}^{i})$; these two clauses force $x_{j_{1}}^{1} = x_{j_{i}}^{i}$, meaning that inclusion of $\rho _{j_{1}}^{1}$ and $\rho _{j_{i}}^{i}$ to the respective posets should be the same. Otherwise, i.e. if the orders of $w'$ and $w''$ are different in $L_{1}(m)$ and $L_{i}(m)$, we construct $(x_{j_{1}}^{1} \vee x_{j_{i}}^{i})$ and $(\overline{x_{j_{1}}^{1}} \vee \overline{x_{j_{i}}^{i}})$. The construction of 2CNF formula is completed by doing this for all the men m who are matched in $M_{1}$. It is not hard to see that a satisfying assignment corresponds to subsets $S_{i}$ such that $M_{1,S_{1}}=M_{2,S_{2}}= \cdots =M_{k,S_{k}}$.

Recall that men’s preference lists are of length at most two and acceptability is mutual by assumption, so the total lengths of $L_{i}$ is O(n). Therefore, for each i, finding $M_{i}$ and computing the set of rotations of $L_{i}$ can be done in O(n) time, and hence in O(kn) time in total. Constructing 2CNF clauses for each man can be done in time O(k), and therefore O(kn) for at most n men. The resulting 2CNF formula has size O(kn). Finally, solving 2CNF satisfiability problem can be done in linear time (Even et al 1976; Aspvall et al 1979). Thus the overall time-complexity is O(kn). $\square$

3.2 Identical preference lists of one side

The next polynomial-time solvable case is that each woman’s preference lists are identical in all $L_{i}$. It should be noted that this condition is different from the so-called master lists where, in each $L_{i}$, all the women have the same preference order derived from a fixed master list. (See, e.g., page 30 of Manlove 2013 for a formal definition of master lists.) In our case, w and $w'$ may have different preference lists.

In this subsection, we restrict inputs so that acceptability is mutual in each preference list set $L_{i}$. Note that this assumption was made without loss of generality in Sect. 3.1, but we cannot do so here because preprocessing described in Sect. 3.1 (in particular, deleting some men from women’s lists) would make some woman’s list differ in $L_{i}$ and $L_{j}$.

Remark

The case of the master list setting can be solved easily. In this case, each preference list set $L_{i}$ admits only one stable matching. Hence it suffices to compute the unique stable matching for each $L_{i}$ and see if the obtained k matchings are identical or not.

Theorem 4

If each woman’s preference lists are identical in all $L_{i}$ ($1 \le i \le k$) and if in each $L_{i}$ acceptability is mutual, then $\text{ SM }k\text{ I }$ is solvable in time O(N), where N is the total length of preference lists in an input.

Proof

Let $I=(U, W, L_{1}, L_{2}, \ldots , L_{k})$ be an instance of $\text{ SM }k\text{ I }$. We first note that, since $L_{1}(w) =L_{2}(w) = \cdots =L_{k}(w)$ for every woman w, for each man m the sets of women included in $L_{i}(m)$ are the same for all i, due to the mutual-acceptability assumption made at the beginning of this subsection. Now we construct a set L of preference lists from $L_{1}, L_{2}, \ldots , L_{k}$ as follows: For each woman w, let $L(w) := L_{1}(w)$. For each man m, the set of women included in L(m) is the same as in $L_{i}(m)$, and their order is defined as follows. Let $w'$ and $w''$ be women in L(m). If m prefers $w'$ to $w''$ in all $L_{i}(m)$, then m prefers $w'$ to $w''$ in L(m). If m prefers $w'$ to $w''$ in some $L_{i}(m)$ and $w''$ to $w'$ in some $L_{j}(m)$, then m is indifferent between $w'$ and $w''$ in L(m). It is not hard to see that L(m) is a partially-ordered list and hence $I'=(U, W, L)$ can be regarded as an instance of the Stable Marriage problem with Partially-ordered and Incomplete lists (SMPI).

We now recall the super-stability (Gusfield and Irving 1989; Irving 1994) in the case that preference lists are not necessarily in a total order. For a matching M, (m, w) is a blocking pair in super-stability if (1) $(m,w) \not \in M$ but (m, w) is an acceptable pair, (2) m is single in M, or prefers w to M(m), or is indifferent between w and M(m), and (3) w is single in M, or prefers m to M(w), or is indifferent between m and M(w). We say that a matching is super-stable if it admits no blocking pair in super-stability. Irving (1994) developed an $O(n^{2})$-time algorithm to find a super-stable matching or to report that no super-stable matching exists when preference lists are complete and may include ties. Manlove (1999) extended this algorithm for incomplete preference lists, and showed that it runs in time O(N) where N is the total length of preference lists in an input. Also, Manlove showed that the same algorithm is applicable for partially-ordered preference lists, i.e., SMPI (page 169 of Manlove 2013). Therefore, to complete the proof, it suffices to show that a matching M is jointly stable in I if and only if M is super-stable in $I'$.

First suppose that M is super-stable in $I'$. Due to Lemma 3.24 in page 160 and observations in page 169 of Manlove (2013), M is stable in any SMI instance derived by linear extension of the partial orders in $I'$. Since each $L_{i}$ is a linear extension of L, M is stable in each $L_{i}$, that is, M is jointly stable in I.

Conversely, suppose that M is not super-stable in $I'$. Then, there is a blocking pair (m, w) in super-stability. Since L(w) is a total order, w is unmatched in M or prefers m to M(w) in L(w). In the latter case, w prefers m to M(w) in all $L_{i}(w)$. Note that m either (i) is unmatched in M, or (ii) prefers w to M(m) in L(m), or (iii) is indifferent between w and M(m) in L(m). In the case of (i), (m, w) is a blocking pair for M in all $L_{i}$. In the case of (ii), m prefers w to M(m) in all $L_{i}(m)$, so again (m, w) is a blocking pair for M in all $L_{i}$. In the case of (iii), m prefers w to M(m) in $L_{i}(m)$ for some i, so that (m, w) is a blocking pair for M in $L_{i}$. In any case, M in not jointly stable in I.

Constructing $I'$ from I and solving $I'$ can both be done in O(N) time, hence the theorem follows. $\square$

As a byproduct of the above proof, we can show the existence of the man-optimal and woman-optimal stable matchings. Let us call a jointly stable matching Mman-optimal if for any man m and any jointly stable matching $M'$, either $M(m)=M'(m)$ or m prefers M(m) to $M'(m)$ in all $L_{i}$. The woman-optimal jointly stable matching is defined similarly.

Let $I=(U, W, L_{1}, L_{2}, \ldots , L_{k})$ be an $\text{ SM }k\text{ I }$ instance and $I'=(U, W, L)$ be the SMPI instance constructed as in the above proof. It is known that the set of super-stable matchings for an SMPI instance form a distributive lattice (Spieker 1995; Manlove 2002; and page 169 of Manlove 2013), so there are the man-optimal and the woman-optimal stable matchings for $I'$, denoted $M_{U}$ and $M_{W}$, respectively. Since women’s preference lists are the same in L and all $L_{i}$, $M_{W}$ is the woman-optimal jointly stable matching for I. Consider a man m and suppose that m is indifferent between $w_{1}$ and $w_{2}$ in L(m). It is known that it cannot be the case that m is matched with $w_{1}$ in one super-stable matching and with $w_{2}$ in another super-stable matching. Thus by the man-optimality of $M_{U}$, for every man m, either $M_{U}(m)=M(m)$ or m prefers $M_{U}(m)$ to M(m) in L(m) for any super-stable matching M. This implies that by construction of L, either $M_{U}(m)=M(m)$ or m prefers $M_{U}(m)$ to M(m) in $L_{i}(m)$ for all i, leading to the existence of the man-optimal jointly stable matching.

4 Conclusion

In this paper, we considered a variant of the stable marriage problem in which we are given k sets of preference lists $L_{1}, L_{2}, \ldots , L_{k}$, and are asked to determine the existence of a matching that is stable with respect to all $L_{i}$ ($1 \le i \le k$). We have shown two NP-complete cases and one polynomially solvable case with respect to the lengths of preference lists. We also showed that the problem is solvable in linear time if every woman has an identical preference list in all $L_{i}$.

An important future work is to determine the complexity of $(3,3)\text{-SM }k\text{ I }$ for $k \ge 2$ and $(3,\ell )\text{-SM }k\text{ I }$ for $\ell \ge 4$ and $k=2, 3$. Another direction is approximability of $\text{ SM }k\text{ I }$; given an instance, find a matching that is stable in as many $L_{i}$ as possible. Finding a stable matching in any one list is a trivial k-approximation algorithm. On the other hand, using Theorem 1 we can easily deduce an approximation hardness of $2-\epsilon$ for even k and $2-\frac{2}{k+1}-\epsilon$ for odd k, for any positive constant $\epsilon$ under P$\ne$NP. Narrowing this gap is an interesting future work. Considering an alternative optimization criteria, e.g., minimizing the total number of blocking pairs over all $L_{i}$, would also be attractive.

Appendix: Partial matchings \(M_{\ell }^{1}\), \(M_{\ell }^{2}\), and \(M_{\ell }^{3}\)

See Figs. 5, 6 and 7.

Fig. 5

Partial matching $M_{\ell }^{1}$

Fig. 6

Partial matching $M_{\ell }^{2}$

Fig. 7

Partial matching $M_{\ell }^{3}$