Dominance invariant one-to-one matching problems

Solution concepts in social environments use either a direct or indirect dominance relationship, depending on whether it is assumed that agents are myopic or farsighted. Direct dominance implies indirect dominance, but not the reverse. Hence, the predicted outcomes when assuming myopic (direct) or farsighted (indirect) agents could be very different. In this paper, we characterize dominance invariant one-to-one matching problems when preferences are strict. That is, we obtain the conditions on preference profiles such that indirect dominance implies direct dominance in these problems and give them an intuitive interpretation. Whenever some of the conditions are not satisfied, it is important to understand whether the agents are myopic or farsighted in order to use the appropriate stability concept. Furthermore, we characterize dominance invariant one-to-one matching problems having a non-empty core. Finally, we show that, if the core of a dominance invariant one-to-one matching problem is not empty, it contains a unique matching, the dominance invariant stable matching, in which all agents who mutually top rank each other are matched to one another and all other agents remain unmatched.

1. See for instance Greenberg (1990), Chwe (1994) and Xue (1998) about abstract social environments; Diamantoudi and Xue (2003), Mauleon and Vannetelbosch (2004), and Herings et al. (2010) about coalition formation; Dutta et al. (2005), Page et al. (2005), Herings et al. (2009), and Page and Wooders (2009) about network formation; and Mauleon et al. (2011) and Klaus et al. (2011) about matching models.

2. The farsighted core only exists when the core contains a unique matching and no other matching indirectly dominates the matching in the core.

3. Kirchsteiger et al. (2013) have tested whether subjects behave myopically or farsightedly when forming a network. They have shown that behaviors consistent with farsightedness account for 75 percent of the individual observations, while only 6 percent of the individual observations are consistent with myopic behavior.

4. See Bogomolnaia and Jackson (2002) and Jackson and Watts (2002).

5. If we endow people with preferences satisfying dominance invariance in an experiment, we would be able to test the appropriateness of any solution concept based on direct and/or indirect dominance independently of whether people are farsighted or not. If the observed behavior is different from what is expected according to some solution concept then we know that this deviation from the prediction is not due to differences in farsightedness but simply implies that the solution concept is not the correct one.

6. Throughout the paper we use the notation \(\subseteq \) for weak inclusion and \(\varsubsetneq \) for strict inclusion.

7. This enforceability condition has also been used in Mauleon et al. (2011) and in Klaus et al. (2011).

8. Several papers are devoted to analyzing the core as solution for this matching problem. See for instance Tan (1991), Chung (2000), Diamantoudi et al. (2004) and Iñarra et al. (2013).

9. From now on, \(|M|\) denotes the cardinality of the set \(M\).

10. Notice that \(l\) equals \(\omega (i)\).

11. Hereafter we omit subscript modulo \(k\).

12. A ring is odd (even) if its cardinality is odd (even).

13. Although Lemma 1 in Mauleon et al. (2011) is stated requiring \(\mu _1\) to be individually rational, the “\(\Rightarrow \)”-part of the lemma, which is the one used in this proof, holds for any two different matchings (individually rational or not). See proof in Mauleon et al. (2011) (p. 515).

14. Although Proposition 1 in Klaus et al. (2011) is stated requiring \(\mu \) and \(\mu ^{\prime }\) to be individually rational, the “\( \Rightarrow \)”-part of the proposition, which is the one used in this proof, holds for any two different matchings (individually rational or not). See proof in Klaus et al. (2011) (pp. 926–927).

We would like to thank Lars Ehlers and two anonymous referees for helpful comments. Ana Mauleon and Vincent Vannetelbosch are Senior Research Associates of the National Fund for Scientific Research (FNRS), Belgium. Financial support from Spanish Ministry of Economy and Competition under the project ECO2012-35820 is gratefully acknowledged. Elena Molis acknowledges financial support from the Spanish Ministry of Education and Science under the projects ECO2010-17049 and ECO2012-31346, from the Basque Government under the project IT568-13 and from the Andalusian Government under the project P07.SEJ.02547. Wouter Vergote gratefully acknowledges financial support from the FNRS.

Authors and Affiliations

1. CORE, Université catholique de Louvain, 34 voie du Roman Pays, 1348 , Louvain-la-Neuve, Belgium

   Ana Mauleon, Vincent J. Vannetelbosch & Wouter Vergote

2. CEREC, Université Saint-Louis - Bruxelles, Boulevard du Jardin Botanique 43, 1000 , Brussels, Belgium

   Ana Mauleon, Vincent J. Vannetelbosch & Wouter Vergote

3. GLOBE, Universidad de Granada, Campus de Cartuja s/n, 18011 , Granada, Spain

   Elena Molis

Corresponding author

Correspondence to Ana Mauleon.

Appendix 1

Tan (1991) establishes a necessary and sufficient condition for the solvability of roommate problems with strict preferences in terms of stable partitions. This notion, which is crucial in the investigation of the core for these problems, can be formally defined as follows.

Let \(A=\{a_{1},...,a_{k}\}\subseteq N\) be an ordered set of agents. The set \( A\) is a ring if \(k\ge 3\) and for all \(i\in \{1,...,k\}\), \( a_{i+1}\succ _{a_{i}}a_{i-1}\succ _{a_{i}}a_{i}\) (subscript modulo \(k\)). The set \(A\) is a pair of mutually acceptable agents if \(k=2\) and for all \(i\in \{1,2\}\), \(a_{i-1}\succ _{a_{i}}a_{i}\) (subscript modulo \(2\)).^{Footnote 11} The set \(A\) is a singleton if \(k=1\).

Definition 5

A stable partition is a partition \(P\) of \(N\) such that:

1. (i)

   for all \(A\in P\), the set \(A\) is a ring, a mutually acceptable pair of agents or a singleton, and

2. (ii)

   for any sets \(A=\{a_{1},...,a_{k}\}\) and \(B=\{b_{1},...,b_{l}\}\) of \(P\) (possibly \(A=B\)), the following condition holds:

   $$\begin{aligned} \text {if } b_{j}\succ _{a_{i}}a_{i-1}\text { then }b_{j-1}\succ _{b_{j}}a_{i}\text {,} \end{aligned}$$

   for all \(i\in \{1,...,k\}\) and \(j\in \{1,...,l\}\) such that \(b_{j}\ne a_{i+1}\).

Condition (i) specifies the sets contained in a stable partition, and condition (ii) contains the notion of stability to be applied between these sets (and also inside each set).

Note that a stable partition is a generalization of a stable matching. To see this, consider a matching \(\mu \) and a partition \(P\) formed by pairs of agents and/or singletons. Let \(A=\{a_{1},a_{2}=\mu (a_{1})\}\) and \( B=\{b_{1},b_{2}=\mu (b_{1})\}\) be sets of \(P\). If \(P\) is a stable partition then Condition (ii) implies that if \( \ b_{1}\succ _{a_{2}}a_{1}\) then \(b_{2}\succ _{b_{1}}a_{2}\), which is the usual notion of stability. Hence \(\mu \) is a stable matching.

Remark 1

(Iñarra et al. 2010) (i) A roommate problem \((N,P)\) has no stable matchings if and only if there exists a stable partition with an odd ring.^{Footnote 12} (ii) Any two stable partitions have exactly the same odd rings. (iii) Every even ring in a stable partition can be broken into pairs of mutually acceptable agents preserving stability.

Appendix 2

Proof

[Proof of Theorem 1] \(\left( \Rightarrow \right) \) By contradiction, we will show that if one of the conditions (i) or (ii) is not satisfied, then \(\mu \gg \mu ^{\prime } \nRightarrow \mu > \mu ^{\prime }\).

• Suppose that condition (i) is not satisfied and there exists a man \( m_i\in M\) such that \(w_k\succ _{m_i}w_j\) for some \(w_k\in A_{m_i}\setminus M_{m_i}\) and some \(w_j\in M_{m_i}\). Let \(\mu _{2}\) be a matching such that \( \mu _{2}(m_i)=w_k\) and \(\mu _{2}(s)=s\) for every \(s\ne m_i,w_k\), and let \( \mu _{1}\) be a matching such that \(\mu _{1}(m_i)=w_j\) and \(\mu _{1}(s)=s\) for every \(s\ne m_i,w_j\). Then \(\mu _{1}\gg \mu _{2}\) (since \(w_k\succ _{w_k}m_i\), woman \(w_k\) enforces the matching in which every agent is alone, and this matching is blocked by \(\{m_i,w_j\}\) enforcing \(\mu _{1}\)). However, \(\mu _{1}\ngtr \mu _{2}\) since \(\mu _{2}\succ _{m_i}\mu _{1}\). A similar argument can be followed to show that there cannot be a woman \( w_i\in W\) such that \(m_k\succ _{w_i}m_j\) for some \(m_k\in A_{w_i}\setminus M_{w_i}\) and some \(m_j\in M_{w_i}\)

• Suppose that condition (ii) is not satisfied and there exists a woman \( w\in M_{m_i}\setminus \{\omega (m_i)\}\) such that \(m_j\succ _{w}m_i\) for some \(m_j\in M_{w}\). Let \(\mu _{2}\) be a matching such that \(\mu _{2}(m_i)=w\) and \(\mu _{2}(s)=s\) for every \(s\ne m_i,w\), and let \(\mu _{1}\) be a matching such that \(\mu _{1}(w)=m_j\), \(\mu _{1}(m_i)=\omega (m_i)\) and where \( \mu _{1}(s)=s\) for every \(s\ne m_i,m_j,w,\omega (m_i)\). Then \(\mu _{1}\gg \mu _{2}\) (since \(\{m_j,w\}\) block \(\mu _{2}\) enforcing a matching in which \( m_i\) and \(\omega (m_i)\) are alone, and this matching is blocked by \( \{m_i,\omega (m_i)\}\) enforcing \(\mu _{1}\)). However, \(\mu _{1}\ngtr \mu _{2}\) since \(\mu _{2}\succ _{m_i}\mu _{1}\). In a similar way, we can show that there cannot be a man \(m\in M_{w_i}\setminus \{\omega (w_i)\}\) such that \( w_j\succ _{m}w_i\) for some \(w_j\in M_{m}\)

\(\left( \Leftarrow \right) \) Now we will prove that if \(\mu _1\gg \mu _2\) and conditions (i) and (ii) are satisfied, then \(\mu _1>\mu _2\).

Let \(D=\{i\in M\cup W:\mu _{1}\succ _i \mu _{2}\}\). First, we prove that for any man \(m_i\in M\) (\(w_i\in W\), respectively) such that \(\mu _{1}(m_i)\ne \mu _{2}(m_i)\) and \(\mu _{1}(m_i)\ne m_i \), we have that \(m_i\in D\) . By contradiction, let \(\mu _{1}(m_i)=w_j\) and let \(\mu _{2}(m_i)=w_k\) and assume that \(w_k\succ _{m_i}w_j\) (which implies that \(w_k\ne w_j\)). Notice that this implies that man \(m_i\) must have been left alone first and then matched to \(w_j\), so \(w_j\in M_{m_i}\) because otherwise \(\{m_i,w_j\}\) would never be formed contradicting \(\mu _{1}\gg \mu _{2}\). Then, by condition (i), \(w_k\in M_{m_i}\). Since \(\mu _{1}\gg \mu _{2}\) and \(m_i\) prefers \(\mu _{2}\) to \(\mu _{1}\), \(w_k\) must prefer \(\mu _{1}\) to \(\mu _{2}\) because, otherwise, \(\{m_i,w_k\}\) would be a blocking pair of \(\mu _{1}\) contradicting that \(\mu _{1}\gg \mu _{2}\) [see Lemma 1 in Mauleon et al. (2011)].^{Footnote 13} Then, the partner of \(w_k\) at \(\mu _{1}\), say for instance \(\mu _{1}(w_k)=m_l\), by condition (i), also belongs to the set \(M_{w_k}\) given that \(m_l\succ _{w_k}m_i\), that is \(m_l\in M_{w_k}\). But this contradicts condition (ii), which says if \(w_k\in M_{m_i}\setminus \omega (m_i)\), there is no man \(m_l\in M_{w_k}\) such that \(m_l\succ _{w_k} m_i\). Hence, man \(m_i\) should prefer \(\mu _{1}\) to \(\mu _{2}\), and, by the same reasoning, \(\mu _1\succ _{w_j} \mu _2\). Therefore \(\{m_i,\mu _1(m_i)\}\subseteq D\).

Consider now any man \(m_i\in M\) such that \(\mu _{1}(m_i)=m_i\ne \mu _2(m_i)=w_k\). Since \(\mu _{1}\gg \mu _{2}\), then either \(\mu _{1}(w_k)\succ _{w_k}m_i \) and \(w_k\) deviates leaving agent \(m_i\) unmatched (with \(\mu _{1}(w_k)\) also preferring \(\mu _{1}\) to \(\mu _{2}\)) and then \( \{w_k,\mu _1(w_k)\}\subseteq D\), or \(m_i\succ _{m_i}w_k\) (and man \(m_i\) individually deviates) and therefore \(m_i\in D\).

Then the coalition \(D\) deviates from \(\mu _{2}\) enforcing \(\mu _{1}\) and \( \mu _{1}>\mu _{2}\) as we wanted to prove. \(\square \)

Proof

[Proof of Proposition 1]

Proof

\(\left( \Leftarrow \right) \) It is easy to see that if properties ( a.) and (b.) are satisfied for every \(m\in M\) and every \( w\in W\), then condition (ii) of Theorem 1 is also satisfied and the problem \( (N,P)\) is dominance invariant. If condition (a.) holds for man \( m_i\in M\), there is no woman \(w_j\in M_{m_i}\setminus \{\omega (m_i)\}\) such that \(m_j\succ _{w_j} m_i\) for any \(m_j\in M_{w_j}\). If \(|M_{\omega (m_i)}| \ge 2\) and condition (b.) holds, condition (ii) of Theorem 1 is satisfied by \(\omega (m_i)\). Otherwise, \(M_{\omega (m_i)}=\{m_i\}\) and condition (ii) of Theorem 1 is satisfied by default.

\(\left( \Rightarrow \right) \) Now we show that if the problem is dominance invariant, that is, it satisfies conditions (i) and (ii) of Theorem 1, then properties (a.), and ( b.) hold.

Suppose that condition (a.) is not satisfied. Then there is a woman \(w_j\in M_{m_i}\setminus \{\omega (m_i)\}\) such that \(t(w_j)\ne m_i\). Let \( t(w_j)= m_j\). By condition (i) of Theorem 1 since \(m_i\in M_{w_j}\) and \( m_j\succ _{w_j} m_i\), we have that \(m_j\in M_{w_j}\). However, this contradicts condition (ii) of Theorem 1.

Now we prove that property (b.) is also satisfied. Suppose first that \(\omega (m_i)\notin T\), that is \(t(t(\omega (m_i)))\ne \omega (m_i)\). If \( t(\omega (m_i))=m_i\) we are done, so assume that \(t(\omega (m_i))=m_j\) and \( t(m_j)=w_k\). Then there is a man \(m_j\in M_{\omega (m_i)}\setminus \{\omega (\omega (m_i))\}\) who prefers \(w_k\) to \(\omega (m_i)\), contradicting that \(\omega (m_i)\) satisfies condition (ii) of Theorem 1. Hence, if \(\omega (m_i)\notin T\), the most prefer man for \(\omega (m_i)\) is \(m_i\). Suppose now that \( t(\omega (m_i))\ne m_i\), say \(t(\omega (m_i))= m_j\). By condition (i) of Theorem 1, since \(m_i\in M_{\omega (m_i)}\) and \(m_j\succ _{\omega (m_i)} m_i\), we have that \(m_j\in M_{\omega (m_i)}\). By condition (ii) of Theorem 1 there cannot be any woman \(w_k\) such that \(w_k\succ _{m_j} \omega (m_i)\) and therefore \(t(m_j)=\omega (m_i)\) and \( \omega (m_i)\in T\) as we wanted to prove. \(\square \)

Proof

[Proof of Theorem 2]

\(\left( \Rightarrow \right) \) By contradiction, we will show that if one of the conditions (i) or (ii) is not satisfied, then \(\mu \gg \mu ^{\prime } \nRightarrow \mu > \mu ^{\prime }\).

• Suppose that condition (i) is not satisfied. Then there exists an agent \(i\in N\) such that \(k\succ _{i}j\) for some \(k\in A_{i}\setminus M_i\) and some \(j\in M_{i}\). Let \(\mu _{2}\) be a matching such that \(\mu _{2}(i)=k\) and \(\mu _{2}(s)=s\) for every \(s\ne i,k\), and let \(\mu _{1}\) be a matching such that \(\mu _{1}(i)=j\) and \(\mu _{1}(s)=s\) for every \(s\ne i,j\). Then \( \mu _{1}\gg \mu _{2}\) (since \(k\succ _{k}i\), agent \(k\) enforces the matching in which every agent is alone, and this matching is blocked by \(\{i,j\}\) enforcing \(\mu _{1}\)). However, \(\mu _{1}\ngtr \mu _{2}\) since \(\mu _{2}\succ _{i}\mu _{1}\).

• Suppose that condition (ii) is not satisfied. Then there exists an agent \(k\in M_{i}\setminus \{\omega (i)\}\) and an agent \(l\in M_{k}\) such that \(l\succ _{k}i\) and \(\{l\}\ne M^k_{i}\). Then it must exist an agent \( j\ne l\) such that \(j\in M^k_{i}\). Let \(\mu _{2}\) be a matching such that \( \mu _{2}(i)=k\) and \(\mu _{2}(s)=s\) for every \(s\ne i,k\), and let \(\mu _{1}\) be a matching such that \(\mu _{1}(k)=l\), \(\mu _{1}(i)=j\) and where \(\mu _{1}(s)=s\) for every \(s\ne i,k,l,j\). Then \(\mu _{1}\gg \mu _{2}\) (since \( \{k,l\}\) block \(\mu _{2}\) enforcing a matching in which \(i\) and \(j\) are alone, and this matching is blocked by \(\{i,j\}\) enforcing \(\mu _{1}\)). However, \(\mu _{1}\ngtr \mu _{2}\) since \(\mu _{2}\succ _{i}\mu _{1}\).

\(\left( \Leftarrow \right) \) Now we will prove that if \(\mu _1\gg \mu _2\) and conditions (i) and (ii) are satisfied, then \(\mu _1>\mu _2\).

Let \(D=\{i\in N:\mu _{1}\succ _{i}\mu _{2}\}\). First, we prove that for any agent \(i\in N\) such that \(\mu _{1}(i)\ne \mu _{2}(i)\) and \(\mu _{1}(i)\ne i \), we have that \(i\in D\) . By contradiction, let \(\mu _{1}(i)=j\) and let \( \mu _{2}(i)=k\) and assume that \(k\succ _{i}j\) (which implies that \(k\ne j\) ). Notice that this implies that agent \(i\) must have been left alone first and then matched to \(j\), so \(j\in M_{i}\) because otherwise \(\{i,j\}\) would never be formed contradicting \(\mu _{1}\gg \mu _{2}\). Then, by condition (i), \(k\in M_{i}\). Since \(\mu _{1}\gg \mu _{2}\) and \(i\) prefers \(\mu _{2}\) to \(\mu _{1}\), \(k\) must prefer \(\mu _{1}\) to \(\mu _{2}\) because, otherwise, \( \{i,k\}\) would be a blocking pair of \(\mu _{1}\) contradicting that \(\mu _{1}\gg \mu _{2}\) [see Proposition 1 in Klaus et al. (2011)].^{Footnote 14} Then, the partner of \(k\) at \(\mu _{1}\), say for instance \(\mu _{1}(k)=l\) (with \(l\ne k,j\)), by condition (i), also belongs to the set of mutually acceptable agents of agent \(k\) given that \(l\succ _{k}i\), that is \(l\in M_{k}\). But then, according to (ii), it must be that \(M_{i}^{k}=\{l\}\). But this is a contradiction, since \(j\in M_{i}^{k}\). Hence, agent \(i\) should prefer \(\mu _{1}(i)\) to \(\mu _{2}(i)\), and, by the same reasoning, \(\mu _{1}\succ _{j}\mu _{2}\). Therefore \(\{i,\mu _{1}(i)\}\subseteq D\).

Consider now any agent \(i\in N\) such that \(\mu _{1}(i)=i\ne \mu _2(i)=k\). Since \(\mu _{1}\gg \mu _{2}\), then either \(\mu _{1}(k)\succ _{k}i \) and \(k\) deviates leaving agent \(i\) unmatched (with \(\mu _{1}(k)\) also preferring \( \mu _{1}\) to \(\mu _{2}\)) and then \(\{k,\mu _1(k)\}\subseteq D\), or \(i\succ _{i}k\) and agent \(i\) individually deviates and therefore \(i\in D\).

Then the coalition \(D\) deviates from \(\mu _{2}\) enforcing \(\mu _{1}\) and \( \mu _{1}>\mu _{2}\) as we wanted to prove. \(\square \)

Proof

[Proof of Proposition 2]

Proof

\(\left( \Leftarrow \right) \) It is easy to see that if properties [ P1.], [P2.] are satisfied, then condition (ii) of Theorem 2 is also satisfied and the problem \( (N,P)\) is dominance invariant.

P1. :

If (a) and (b.1) are satisfied then there is no agent \(k\in M_i\setminus \{\omega (i)\}\) such that \(l\succ _k i\) for any \(l\in M_k\). If (b.2) is satisfied then \(j_k\in M_i\setminus \{\omega (i)\}\), \(\omega (i)\succ _{j_k} i\), and \(M^{j_k}_i=\{\omega (i)\}\). Hence, when agent \(i\) holds property [P1.] in her preferences, condition (ii) of Theorem 2 is satisfied.

P2. :

If \(M_i=\{j\}\), then \(M_i\setminus \{\omega (i)\}=\emptyset \) and condition (ii) of Theorem 2 is satisfied by agent \(i\) by default. Let \(M_i=\{j,\omega (i)\}\). If \(t(t(i))=i\) there is no agent \(k\in M_i\setminus \{\omega (i)\}\) such that \(l\succ _k i\) for any \(l\in M_k\). If \( t(t(i))=\omega (i)\), then \(t(i)\in M_i\setminus \{\omega (i)\}\), \( \omega (i)\succ _{t(i)} i\), and \(M^{t(i)}_i=\{\omega (i)\}\). In both cases, condition (ii) of Theorem 2 is satisfied by agent \(i\). If \(i\in S\) where \(S\) is a ring in \(P\) such that \( |S|=3\) and for all \(s_i\in S\), \(s_{i+1}\succ _{s_i}s_{i-1}\succ _{s_i} j\) for any \(j\in N\setminus \{s_{i+1},s_{i-1}\}\), then it is easy to see that condition (ii) of Theorem 2 is also satisfied by agent \(i\). (Notice that if \(t(t(i))\notin \{i, \omega (i)\}\), condition (ii) is not satisfied and the problem is not dominance invariant)

\(\left( \Rightarrow \right) \) We will show that if the problem is dominance invariant and satisfies conditions (i) and (ii) of Theorem 2, then properties [P1.], [ P2.] hold.

P1. :

Assume that (a) is not satisfied. That is, there exists an agent \(j\in M_{i}\setminus \{j_{k},\omega (i)\}\) such that \( t(j)\ne i\). This implies that \(\exists k\in N\) such that \(t(j)=k\) and \( k\succ _{j}i\). By condition (i) of Theorem 2, \(k\in M_{j}\) and then by condition (ii) of Theorem 2, \(M^j_{i}=\{k\}\). However, this contradicts that \(\{j_{k},\omega (i)\}\subseteq M^j_{i}\). Now we will show that (b) must be satisfied as well. The fact that \( t(j_{k})\in \{i,\omega (i)\}\) is straightforward from condition (ii) of Theorem 2. In order to prove (b.1), let \(t(j_{k})=i\). First, we will show that if \(\omega (i)\notin T\) then either \(t(\omega (i))=i\) or \(t(\omega (i))=t(i)\) . Let \(\omega (i)\notin T\). Then, there exists an agent \(k\) such that \( t(\omega (i))=k\). If \(k=i\) we are done, so assume that \(k\ne i\). Since \( k\succ _{\omega (i)}i\) and \(i\in M_{\omega (i)}\), by condition (i) of Theorem 2, \(k\in M_{\omega (i)}\). Moreover, \(t(k)=l\ne \omega (i)\) so \(l\succ _{k}\omega (i)\) and by condition (i) of Theorem 2, \(l\in M_{k}\). Thus, \(\exists \,k\in M_{\omega (i)}\setminus \{\omega (\omega (i))\} \) and \(\exists \,l\in M_{k}\) such that \(l\succ _{k}\omega (i)\). Then, by condition (ii) of Theorem 2, it holds that \(\{l\}=M^k_{\omega (i)}\). Since \(i\in M^{k}_{\omega (i)}\), we have that \(l=i\). Given that \(l\in M_{k}\) and \(l=i\), it holds that \(k\in M_{i} \). Let \(k\ne t(i)\), otherwise we are done. Then since \(i\in M_{k}\setminus \{\omega (k)\}\) and there exists an agent \(k^{\prime }\in M_{i}\) such that \(k^{\prime }\succ _{i}k\) (remember that \(k\ne t(i)\)), by condition (ii) of Theorem 2, \(\{k^{\prime }\}=M^{i}_k\). But this implies that \(k^{\prime }=\omega (i)\) and this is a contradiction since \( \omega (i)\nsucc _{i}k\). So we have proved that when \(\omega (i)\notin T\) either \(t(\omega (i))=i\) or \(t(\omega (i))=t(i)\).Now we will show that if \(t(\omega (i))\notin \{i,t(i)\}\), then \(\omega (i)\in T\). Let \(t(\omega (i))=k\) with \(k\ne i,t(i)\). If \(t(k)=\omega (i) \) we are done, so assume that \(t(k)=l\ne \omega (i)\). Thus, there exists an agent \(l\in M_{k}\) such that \(l\succ _{k}\omega (i)\) and by condition (ii) of Theorem 2 \(\{l\}=M^k_{\omega (i)}\) , which implies that \(l=i\). Notice that we are in the same situation as in the previous paragraph. Then, following the same reasoning, we achieve the same contradiction (\( \omega (i)\nsucc _{i}k\)) and this proves that \(\omega (i)\in T\) as desired. Next, we proceed to prove (b.2). Let \(t(j_{k})=\omega (i)\). We will prove that in this case \(t(\omega (i))=j_{k}\). Since \(i\in M_{j_{k}}\), we have that \(\omega (i)\in M_{j_{k}}\setminus \{\omega (j_{k})\}\). If \( t(\omega (i))=j_{k}\) we are done, so assume that \(t(\omega (i))=k\). By condition (i) of Theorem 2 \(k\in M_{\omega (i)}\), and by condition (ii) of Theorem 2, since \(k\succ _{\omega (i)}j_{k}\), \( \{k\}=M^{\omega (i)}_{j_k}\). Then, \(k=i\), with \(i\in M_{\omega (i)}\setminus \{\omega (\omega (i))\}\). Hence, by condition (ii) of Theorem 2 again, we have that for any \(j\in M_{i}\setminus \{\omega (i)\}\), \(j\succ _{i}\omega (i)\), then \( \{j\}=M^i_{\omega (i)}\). But \(|M_{i}\setminus \{\omega (i)\}|>1\), and then \( j\in M^i_{\omega (i)}\) for all \(j\in M_{i}\setminus \{\omega (i)\}\), contradicting the uniqueness of \(M^i_{\omega (i)}\).

P2. :

Let \(i\) be an agent such that \(|M_{i}|\le 2\). We will prove that either \(t(i)\in T\) with \(t(t(i))\in \{i,\omega (i)\}\) or agent \( i \) belongs to a ring \(S\) such that \(|S|=3\) and \(\forall s_{i}\in S\), \( s_{i+1}\succ _{s_{i}}s_{i-1}\succ _{s_{i}}r\) for any \(r\in N\setminus \{s_{i+1},s_{i-1}\}\). Consider first that \(M_{i}=\emptyset \), then we have \(i\succsim _{i}j\) for all \(j\in N\), and so \(t(i)\in T\) with \(t(t(i))=\{i\}\). Consider now that \(M_{i}=\{j\}\). If \(t(j)=i\) we are done, so assume that \( t(j)=k\) with \(k\ne i\). By the reasoning in [P1.], if \(|M_{j}|>2\), then \(t(k)=j\) and we are done. So let \(|M_{j}|\le 2\). Since \(k\in M_{j}\setminus \{\omega (j)\}\), by condition (ii) of Theorem 2, either \(t(k)=j\) or there exists an agent \(l\in M_{k}\) such that \(l\succ _{k}j\) and \(\{l\}=M_{j}^{k}\). However, this implies \(l=i\) (since \(i\in M_{j}^{k})\), which contradicts condition (i) of Theorem 2 since this implies that \( i\succ _{k}j\) when by the initial assumption \(k\notin M_{i}\). Hence, if \( M_{i}=\{j\}\), then either \(t(j)=i\) or \(t(j)=k\) with \(t(k)=j\). Consider now the case that \(M_{i}\) has two elements. Without loss of generality, let \(M_{i}=\{j,k\}\) with \(j\succ _{i}k\). Since \(j\in M_{i}\setminus \{\omega (i)\}\) from condition (ii) of Theorem 2, we deduce that either \(t(j)=i\) or \( t(j)=k\). Let assume that \(t(j)=k\), otherwise we are done. We will show that either \(t(k)=j\) or there exists a ring \(S=\{i,j,k\}\) such that \(\forall s_{i}\in S\), \(s_{i+1}\succ _{s_{i}}s_{i-1}\succ _{s_{i}}r\) for all \(r\in N\setminus \{s_{i+1},s_{i-1}\}\) . (Until now, we have assumed that \(j\succ _i k\) and \(k\succ _j i\).) Assume that there exists an agent \(s\in M_{j}\setminus \{i,k\}\) such that \(s\succ _{j}i\) . Since \(j\in M_{i}\setminus \omega (i)\), by condition (ii) of Theorem 2, \(\{s\}=M^j_{i}\), which implies \(s=k\). Therefore, there cannot be any agent different from \(k\) more preferred than \( i\) in agent \(j\)’s preferences. Consider now that there exists an agent \(s\in M_{j}\setminus \{i,k\}\) such that \(i\succ _{j}s\). Then \(|M_{j}|>2\) and by the reasoning of [P1. ], \(t(j)=k\) implies \(t(k)=j\) as desired. Finally, suppose that there is no \(s\in M_{j}\setminus \{i,k\}\). (That is, \( M_{j}=\{k,i\}\) with \(k\succ _{j}i\).) If \(t(k)=j\) we are done, so assume that \(t(k)=l\ne j\). Since \(k\in M_j\setminus \{\omega (j)\}\) and there exists \( l\in M_k\) such that \(l\succ _k j\), by condition (ii) of Theorem 2 \(\{l\}=M_j^k\), which implies that \(l=i\) and then \(i\succ _k j\). Now we prove that there cannot be any agent between \( i \) and \(j\) in agent \(k\)’s preferences. Suppose there is an agent \(s\in M_k\setminus \{i,j\}\) such that \(s\succ _k j\). Since \(k\in M_j\setminus \{\omega (j)\}\) and \(s\succ _k j\), then by condition (ii) of Theorem 2 \(M_j^k=\{s\}\) and then \(s=i\). Therefore, we have that \(S=\{i,j,k\}\) form a ring in \(P\) such that \(\forall s_{i}\in S\), \(s_{i+1}\succ _{s_{i}}s_{i-1}\succ _{s_{i}}r\) for any \(r\in N\setminus \{s_{i+1},s_{i-1}\}\) as we wanted to prove. \(\square \)

Proof

[Proof of Corollary 1]

According to Proposition 2, by properties [P1.] and [P2.], if \(i\notin T\), then \(|M_i|\le 2\). If \(M_i=\{j\}\), by property [P2.] \(j\in T\). If \(M_i=\{j, k\}\) and \(i\notin S\), then by property [P2.] \(j,k\in T\). \(\square \)

Proof

[Proof of Proposition 3]

We will show that \((N,P)\) satisfies conditions (i) and (ii) of Theorem 2. Condition (i) is trivially satisfied since all agents of \(N\) are mutually acceptable between them, that is \( \forall i\in N,A_{i}\setminus M_{i}=\emptyset \). Now let \(N=\{i,k,l\}\) and assume w.l.o.g. that \(k\in M_{i}\setminus \{\omega (i)\}\). If \(i\succ _{k}l\) , for agent \(i\) condition (ii) is satisfied by default. So let \(l\succ _{k}i\) . Since \(l=\{\omega (i)\}=M_{i}^{k}\), condition (ii) is thus also satisfied. \(\square \)

Proof

[Proof of Proposition 4]

\(\left( \Rightarrow \right) \) The existence of a ring \(S\) in the preferences with \(|S|=3\) and \(\forall s_{i}\in S\), \(s_{i+1}\succ _{s_{i}}s_{i-1}\succ _{s_{i}}j\), for any \(j\in N\setminus \{s_{i+1},s_{i-1}\}\) is a sufficient condition for non-existence of stable matchings in any one-to-one matching problem (dominance invariant or not). Let \(\mu \) be a matching such that \( \mu (s_{i})=j\) for some \(s_{i}\in S\) and some \(j\notin S\). This matching is blocked by the pair \(\{s_{i},s_{i-1}\}\). Therefore any matching containing a pair formed by an agent in the ring and an agent outside the ring is not stable. Consider then a matching \(\mu ^{\prime }\) satisfying that \(\mu ^{\prime }(s_{i})=s_{i+1}\) and \(\mu ^{\prime }(s_{i-1})=s_{i-1}\)

This matching is blocked by the pair \(\{s_{i-1},s_{i+1}\}\). Therefore any matching in which agents in \(S\) are matched among themselves is not stable. Hence, there is no matching stable as we wanted to prove.

\(\left( \Leftarrow \right) \) We will show that if a one-to-one matching problem is dominance invariant and unsolvable then there exists a ring \(S\) in \(P\) satisfying that \(|S|=3\) and \(\forall s_i \in S\), \(s_{i+1}\succ _{s_i} s_{i-1}\succ _{s_i} j\) for any \(j\in N\setminus \{s_{i+1},s_{i-1}\}\).

First, we show that if a problem \((N,P)\) is dominance invariant, there cannot be a ring \(S\) in \(P\) with \(|S|>3\). By contradiction, suppose there is a ring \(S\) with \(|S|>3\) and take agent \(s_i\in S\). By definition of ring, \( s_{i+1}\succ _{s_i} s_{i-1}\succ _{s_i} s_i\) and \(s_{i+2}\succ _{s_{i+1}} s_{i}\succ _{s_{i+1}} s_{i+1}\). Then \(s_{i+1}\in M_{s_i}\setminus \{\omega (s_{i})\}\) and \(s_{i+2}\succ _{s_{i+1}}s_i\). By condition (ii) of Theorem 2 \(M^{s_{i+1}}_{s_i}=s_{i+2}\) . That implies that \(s_{i+2}=s_{i-1}\), which is only possible if \(|S|=3\).

Now we show that for any agent \(s_i\in S\) there cannot be an agent \(j\notin S \) such that \(j\succ _{s_i} s_{i-1}\). By contradiction, suppose there exists an agent \(j\notin S\) and \(j\succ _{s_i} s_{i-1}\). By condition (i) of Theorem 2, \(j\in M_{s_i}\). By definition of ring, \(s_i\succ _{s_{i-1}} s_{i+1}\) and then \(s_i\in M_{s_{i-1}}\setminus \{\omega (s_{i-1})\}\). By condition (ii) of Theorem 2, \(M^{s_i}_{s_{i-1}}=j\), which implies that \(j=s_{i+1}\). But this contradicts that \(j\notin S\). \(\square \)

Proof

[Proof of Proposition 5]

For all \(i\in T\), it is easy to see that \(\mu _C(i)=t(i)\). Otherwise \(\mu _C\) is blocked by the pair \(\{i, t(i)\}\) and it is not stable. (This holds for all one-to-one matching problems dominant invariant or not.) Consider now an agent \(j\notin T\) such that \(\mu _C(j)\ne j\). Then either \(t(\mu _C(j))\ne j\) or \(t(j)\ne \mu _C(j)\). W.l.o.g. assume that \(t(j)\ne \mu _C(j)\). By condition (i) of Theorem 2, \(t(j)\in M_j\). Let \(\mu _C(t(j))=l\). Since matching \(\mu _C\) is stable, then \( l\succ _{t(j)} j\). By condition (ii) of Theorem 2, \(M^{t(j)}_j=l\), which implies \( \mu _C(j)=l\). But this is not possible, given that agent \(l\) cannot be matched in matching \(\mu _C\) to agent \(j\) and agent \(t(j)\) at the same time. \(\square \)

Reprints and permissions