1 Introduction

In the stable matching problem, stated and solved by Gale and Shapley (1962), there are two disjoint sets of agents, and the basic question is to find a matching between these two different sets of agents satisfying the no blocking property; i.e., no pair of opposite agents will prefer each other than the ones to whom they are matched. Gale and Shapley proved the existence of such a matching via a constructive algorithm, which is known as the deferred acceptance algorithm (DAA). For a comprehensive introduction to the subject, we refer to the books Roth and Sotomayor (1992), Knuth (1976), Gusfield and Irving (2003). Note however that the DAA is a centralised algorithm, i.e., the social planner solicits preferences from agents on the two sides of the market, and uses the algorithm to yield a stable match. This leads to a question of whether a decentralized algorithm, as emphasised e.g., in Roth and Vande Vate (1990), Eriksson and Häggström (2008) also yields a stable matching.

In particular, one of the main motivation for our current work is a problem posed in Knuth (1976) (see Knuth 1997 for an English translation). Knuth’s problem can be described as follows: Start with any arbitrary matching, find any blocking pair and then interchange the pairs. Does this procedure eventually lead to a stable matching? Knuth has shown an example in which this procedure may lead to a cycle and has also suggested a way to avoid the cycle in this example.

Roth and Vande Vate (1990), in an influential paper, resolved the question raised by Knuth in the following way: At each stage, new matching is obtained by satisfying a blocking pair. The main difference from the Knuth’s procedure is that in the intermediate steps, some agents may possibly remain single. Roth and Vande Vate (1990) proved, in this framework, that starting from any matching we can obtain a finite sequence of matching leading to a stable matching. Subsequently a counter example is produced to show that the Knuth’s original procedure may not result in a stable matching if we start from an arbitrary matching (see Tamura 1993).

In view of the counter example due to Tamura (1993), one would like to ask if the Knuth’s decentralized algorithm will converge at least in some special cases. As we show later, whenever the Knuth’s decentralized algorithm diverges, the preferences of the agents admit a cycle (see Sect. 2 for precise details). It has been proved in Romero-Medina and Triossi (2013a) that if the preferences have no cycle, then the market admits a unique stable matching. Thus there seems to be some connection between the conditions implying the uniqueness of stable matching and the convergence of Knuth’s decentralized algorithm. Our objective in this paper is to explore this relationship.

In particular, we make the following contributions. We prove that starting from any arbitrary matching, Knuth’s decentralized algorithm always converges to a stable match if the preference ordering of the men and women satisfies the “Sequential Preference Condition” (SPC), or if the marriage market admits no cycle. The notion of SPC has been introduced by Eeckhout (2000), though the terminology is due to Clark (2006). The SPC is an ordering of the men and women such that a man or woman of the same rank prefer each other to anyone else of a lower rank. Eeckhout (2000) has shown that when the preferences of the marriage market satisfies SPC, then there exists a unique stable matching. However, as stated by Clark (2006), the SPC condition does not guarantee the existence of stable matching for subpopulations of a marriage market. To ensure this, a stronger condition called the “No Crossing Condition” (NCC) has been introduced by Clark (2006). Incidentally the NCC is a weaker requirement for subpopulations to have a unique stable match (see Alcalde 1994). Our work is also related to the paper by Romero-Medina and Triossi (2013a), who show that when the market has no simultaneous cycle, then the set of stable matches is unique. In this article, the authors consider marriage markets where agents can prefer to remain single. However, we argue that the SPC is a more general condition because acyclicity implies SPC, when we restrict the classical marriage market where each agent prefers to be matched rather than remaining single. Therefore, the condition given by Romero-Medina and Triossi (2013a) is a stronger than necessary condition for a marriage market to have a unique stable matching. This then leads us to the second question that we address in the paper—under what conditions does Knuth’s decentralized algorithm converge to the unique stable matching?

Apart from the SPC condition, there is another condition (see Drgas-Burchardt 2013) which ensures the uniqueness of a stable matching. This condition includes examples which do not satisfy SPC and thus complements SPC. It should also be noted that, under this condition, the number of agents one each side should be even for uniqueness. Furthermore, the condition does not allow on unemployment.

Another closely related work, in a more general context, is Banerjee et al. (2001). In this work, the authors discusses non-emptiness and uniqueness of core in coalition formation games. Under top-coalition property and strictness of the preferences, they show that the coalition games have unique core. Note that stable marriage problem is an example of a coalition formation game. In fact, Banerjee et al. (2001) applies their results to Becker’s marriage game (Becker 1974). However, our results are more general than theirs when restricted to the two-sided matching markets.

Note that SPC, as introduced in Eeckhout (2000), applies to a classical situation of matching markets, where each agent prefers to be employed rather than unemployed. To the best of our knowledge, acyclicity (studied in Romero-Medina and Triossi 2013a) seems to be the best result available in the literature for uniqueness for matching markets where agents can remain single rather than being matched with some other agents. Acyclicity is a very strong assumption. SPC, even for the classical setup, does not preclude cycles. In fact, as mentioned above, SPC includes acyclicity for marriage markets in classical framework. Thus a notion for uniqueness, which does not preclude cycles is necessary. To this extent, we introduce a new notion called Generalized Sequential Preference Condition, which allows the agents in the marriage market to remain single over getting matched. We show that when the preferences of the men and women satisfy the Generalized SPC, then the marriage market admits a unique stable matching, and that Knuth’s decentralized algorithm converges to this unique stable match. Furthermore, we prove that the Generalized SPC subsumes the acyclicity condition. We also provide an example to show that a marriage market may have multiple stable matches, yet Knuth’s decentralized algorithm may converge. This is in contrast to the example given by Tamura (1993), leaving a possible improvement of our result for future research.

The subject of uniqueness of stable matching is an important one, at least, in two aspects: designing a stable mechanism and strategic considerations. The presence of multiple stable matchings leads to the natural question of which one of these matchings should a social planner (or market designer) choose? Given that the men-optimal stable match is most preferred by the men, and that the women-optimal stable match is most preferred by the women, how does a planner reconcile these differences to ensure “fairness”? From a strategic point of view, it is proved in (Roth and Sotomayor 1992, Theorem 4.6) that misrepresenting the preferences by a single agent (when all agents are truth-telling) will achieve his/her preferred mate, when there are multiple stable matches. Having a unique stable match precludes (to some extent) these issues. Uniqueness is also important in the area of search with frictions; see e.g., Lauermann and Nöldeke (2014). In Lauermann and Nöldeke (2014), it is proved that the convergence of equilibrium matchings to a stable matching is guaranteed if and only if there is a unique stable matching. Further, uniqueness plays an important role in matching markets with incomplete information (Ehlers and Massó 2007) and also in capacity manipulation (Romero-Medina and Triossi 2013b). For a more detailed discussion on importance of uniqueness and its consequences, we refer to the introductory section in Park (2017).

While strategy proofness is not the main focus of our paper, an interesting insight emerges. From Dubins and Freedman (1981) and Roth (1982), we know that the man proposing DAA is strategy-proof for men while the woman proposing DAA is strategy-proof for women. If the market admits unique stable matching, it follows immediately that DAA is strategy-proof for both the agents. This, in turn, implies the strategy-proofness of DAA mechanism under the SPC condition.

The remainder of the paper is organized as follows: Section 2 details the basic marriage market framework, defines the SPC condition introduced by Eeckhout (2000) and the acyclicity condition. Section 3 begins by summarizing the counterexample given by Tamura (1993) and presents one of our main results on convergence of Knuth’s decentralised algorithm. In addition, this section relates our results to several of the results in the existing literature, and provides two illustrations for the convergence of Knuth’s decentralized algorithm—one, where the market has multiple stable matches, and, two, where the market has a unique stable match. In Sect. 4, we present an extension to Eeckhout’s SPC. Under this extension, we show that the matching market admits a unique core and that the Knuth’s decentralized algorithm converges to this unique stable matching. Further, we show that acyclicity is a special case of this extended notion. Section 5 concludes.

2 Preliminaries

We follow the standard matching framework presented in Roth and Sotomayor (1992). There are two finite and disjoint sets, \(M = \{m_1, m_2,\ldots , m_n\}\) and \(W = \{w_1, w_2,\ldots ,w_n\}\); where, M denotes the set of men and W denotes the set of women. The total population is denoted by \(M \cup W\). Every man has preferences over the women, and every woman has preferences over the men. We assume that the preferences are strict (to rule out indifferences), and that they are complete, reflexive, and transitive. The preferences of man \(m_i\) over the women are denoted by \(P(m_i)\) and the preferences of woman \(w_j\) over the men are denoted by \(P(w_j)\). Let \(\varvec{P} = \{P(m_1), P(m_2),\ldots ,P(m_n), P(w_1), P(w_2),\ldots ,P(w_n)\}\) denote the set of preference lists, one for each individual. A marriage market is then denoted by the triplet \((M, W; \varvec{P})\). In the sequel, we also use the alternate notations \(\succ _{m_i}\) or \(\prec _{m_i}\) for \(P(m_i)\) and \(\succ _{w_j}\) or \(\prec _{w_j}\) for \(P(w_j)\).

An outcome of a marriage market is a set of matchings. Formally, a matching \(\mu \) is a one-to-one correspondence from the set \(M \cup W\) onto itself such that, (i) \(m = \mu (w)\) iff \(w = \mu (m)\), and, (ii) \(\mu (m) \in W\) and \(\mu (w) \in M\). A matching \(\mu \) is stable if it cannot be blocked by any pair of men and women; i.e. there is no pair (m, w) such that \(m \succ _{w} \mu (w)\) and \(w \succ _{m} \mu (m)\).

We now introduce some notions that are pertinent to our work.

Definition 2.1

A marriage market is said to satisfy the Sequential Preference Condition (SPC) if the set of men and women can be ordered so that

  • for every i and \(j > i\), we have \(w_i \succ _{m_i} w_j \) and

  • for every i and \(j > i\), we have \(m_i \succ _{w_i }m_j \).

Thus, a marriage market satisfies the SPC condition if the men and women can be ordered such that man i prefers woman i to woman \(i+1, i+2,\ldots ,n\) and woman i prefers man i to man \(i+1, i+2,\ldots ,n\). The SPC is introduced in Eeckhout (2000) and the nomenclature is due to Clark (2006). Note that the preferences of woman i on \(m_1, m_2,\ldots , m_{i-1}\) can be anything. Similarly the preferences of man i on \(w_1, w_2,\ldots , w_{i-1}\) can be anything. Since our proof also involves notions of cycles, we recall the idea here. Note that in Eeckhout (2000), simultaneous cycle is denoted by ring.

Definition 2.2

A k-cycle of men’s preferences is a sequence of distinct men \(m_1, m_2,\ldots , m_k\) and distinct women \(w_1, w_2,\ldots , w_k\) such that \(w_{k} \prec _{m_1} w_1\), \( w_i \prec _{m_{i+1}} w_{i+1}\) for \(i = 1,2,\ldots , k\).

A k-cycle of women’s preferences is a sequence of distinct men \(m_1, m_2,\ldots , m_k\) and distinct women \(w_1, w_2,\ldots , w_k\) such that \(m_i \prec _{w_i} m_{i+1}\) for \(i=1,2,\ldots , k-1\) and \(m_k \prec _{w_k} m_1 \).

A simultaneous k-cycle is a sequence of men and women which is both k-cycle of men’s preferences as well as women’s preferences.

A marriage market is said to be acyclic, if there is no simultaneous cycle of any length k.

3 Knuth’s decentralized algorithm, SPC and uniqueness

Given an arbitrary matching \(\mu \), can we find a sequence of matchings \(\mu _1, \mu _2,\ldots , \mu _k\) such that \(\mu _1 = \mu \), \(\mu _k\) is a stable matching and for each i, \(\mu _{i+1}\) is obtained by satisfying a blocking pair in \(\mu _i\) by interchanging the partners of the blocking pair in \(\mu _i\). In Knuth (1976), Knuth asked the following question: Does this iterative process always lead to a stable matching? In fact, Knuth, himself, provided a counter example. Then, he modified his question and asked if we can choose the blocking pair intelligently so that we will have the convergence. This problem is resolved in Roth and Vande Vate (1990) by slightly modifying the procedure. The procedure adapted in Roth and Vande Vate (1990) is as follows: At each stage, find the blocking pair and match them and leave their original partners unmatched. With this modification, they have proved the convergence to a stable matching with probability one. Later, Tamura (1993) has provided a counterexample to show that Knuth’s decentralized algorithm may not converge to a stable matching starting from arbitrary matching. For the sake of exposition, we provide the example below.

Example 3.1

(Tamura 1993) Let the marriage market be given by the following preference ordering of the men and women:

$$\begin{aligned}&P(m_1) = w_1, w_3, w_2, w_4; \quad P(w_1) = m_2, m_4, m_1, m_3 \\&P(m_2) = w_2, w_4, w_3, w_1; \quad P(w_2) = m_3, m_1, m_2, m_4 \\&P(m_3) = w_3, w_1, w_4, w_2 ; \quad P(w_3) = m_4, m_2, m_3, m_1 \\&P(m_4) = w_4, w_2, w_1, w_3 ; \quad P(w_4) = m_1, m_3, m_4, m_2. \end{aligned}$$

This market has five stable matches. If we start with the matching

$$\begin{aligned} \mu = (m_1 \leftrightarrow w_1, m_2 \leftrightarrow w_2, m_3 \leftrightarrow w_4, m_4 \leftrightarrow w_3) \end{aligned}$$

the algorithm will not converge to a stable matching. Moreover, if we draw the directed graph of all the matchings, where an edge from a matching \(\mu \) to another matching \(\nu \) means that \(\nu \) can be obtained from \(\mu \) by interchanging the partners in a blocking pair, then the directed graph has six connected components. One of the components consists of only unstable matchings.

In fact, a general result is established in Tamura (1993). If the number of members in each side of the market is \(n \ge 4\), there always exists a matching market such that there is a matching which cannot be transformed into a stable matching by following Knuth’s decentralized algorithm.

We start with the following simple observation where Knuth’s decentralized algorithm always converges to a stable matching.

Proposition 3.1

If the preferences are acyclic,  then the Knuth’s decentralized algorithm converges to a stable matching.

Proof

Let us start with a matching \(\mu _1\) and assume that after k rounds, we return to \(\mu _1\) i.e., \(\mu _{k+1} = \mu _1\).

Let \((m_2, w_1)\) be a blocking pair in the match \(\mu _1\), where \(w_1\) is matched with \(m_1\). Thus we have \(m_1 \prec _{w_1} m_2\). By the hypothesis, \(m_2\) must have been part of the blocking pair at some stage. So, there must be a women \(w_2\) at some stage such that \(w_1 \prec _{m_2} w_2\). Since the set of men and women are finite and the procedure can take only k rounds, we must end up with men \(m_1, m_2,\ldots , m_l\) and women \(w_1, w_2,\ldots , w_l\) such that \(m_i \prec _{w_i} m_{i+1}\), \( w_i \prec _{m_{i+1}} w_{i+1}\) for \(i=1,2,\ldots , l-1\), \(m_l \prec _{w_l} m_1 \) and \(w_{l} \prec _{m_1} w_1\). This gives a cycle of men and women, contradicting the fact that the market is acyclic. Therefore, Knuth’s decentralized algorithm converges to a stable matching in finitely many steps. \(\square \)

A close inspection of the above proof reveals that the conclusion of the above theorem holds true even if there are no cycles of men (or women) alone. This is the content of the theorem below. We omit the proof as it is a direct adaptation of the above proof.

Proposition 3.2

If the market admits no cycle of men (or women),  then Knuth’s decentralized algorithm converges to a stable matching.

We will now try to understand the structure of acyclicity. If the men’s preferences have no cycle, then their preferences over women are identical. This can be seen as follows: consider two men \(m_1\) and \(m_2\) and two women \(w_1, w_2\). Suppose \(w_1 \prec _{m_1} w_2\). If \(w_2 \prec _{m_2} w_1\), then we have a cycle. Therefore \(w_1 \prec _{m_2} w_2\), proving the one-sidedness of the preferences. In other words, the preference structure of each man on the women is identical. This is already observed in (Romero-Medina and Triossi 2013a, (Proposition 3), page 238). Moreover, if there are no simultaneous cycles, both men and women are ranked and their preferences are according to this ranking. Consequently acyclicity implies SPC, which is the content of the proposition below.

Proposition 3.3

Suppose the market admits no cycle of men (or women). Then the market satisfies SPC.

Proof

From the comments preceding the statement of the proposition, we know that all men rank the women in same way. Let us assume that the women are rearranged so that the men prefer the women in the order \(w_1, w_2,\ldots , w_n\). Now, arrange the men as per the unique stable matching \(\mu \) i.e., \(m_i = \mu (w_i)\). It is now an easy exercise to see that SPC is satisfied with respect to this ordering of men and women. \(\square \)

Under SPC, the market may admit cycles. To see this, let us consider the market with three men \(\{m_1, m_2, m_3 \}\) and three women \(\{w_1, w_2, w_3 \}\) with preferences as follows:

$$\begin{aligned}&P(m_1) : w_1, w_2, w_3; \quad P(m_2): w_1, w_2, w_3; \quad P(m_3) : w_2, w_3, w_1 \\&P(w_1) : m_1, m_3, m_2; \quad P(w_2): m_2, m_3, m_1;\quad P(w_3) = m_3, m_2, m_1. \end{aligned}$$

It is not hard to see that the market has cycles.

Consequently, the notion of acyclicity is also related to uniqueness. In fact, Romero-Medina and Triossi (2013a) proves that acyclicity implies uniqueness for marriage markets where unemployment is allowed. We provide a direct proof of this result when unemployment is not allowed for the sake of completeness.

Proposition 3.4

Suppose a market has at least two stable matches,  then the market admits a cycle.

Proof

Let \(\mu \) and \(\nu \) be two different stable matches. Now construct a sequence of distinct men and women \(m_1, m_2,\ldots , m_k\) and women \(w_1, w_2,\ldots , w_k\) as follows:

figure a

Such a sequence is possible and exists because \(\mu \ne \nu \) and there are only finitely many men and women. This sequence provides us with a cycle. \(\square \)

We are, now, ready to state and prove our main result of this section which extends Proposition 3.1 (and also Proposition 3.2).

Theorem 3.1

If a matching market satisfies SPC,  then starting from an arbitrary matching \(\mu _{1},\) there exists a sequence \(\mu _{1}, \mu _{2},\ldots , \mu _{k},\) where \(\mu _{k}\) is the unique stable matching,  and \(\mu _{i+1}\) is obtained from \(\mu _{i}\) by interchanging appropriately chosen blocking pair in \(\mu _{i}.\)

Proof

SPC implies that the men and women can be arranged such that \(m_i\) prefers \(w_i\) to \(w_{i+1}, w_{i+2},\ldots , w_n\) and \(w_i\) prefers \(m_i\) to \(m_{i+1}, m_{i+2},\ldots , m_n\).

Let \(\mu _1\) be any matching. Consider the smallest i such that \(m_i\) is not matched to \(w_i\). Clearly this pair will form a blocking pair to the matching \(\mu _1\). We interchange their partners to obtain \(\mu _2\). Repeat this procedure. In at most n steps, we will reach the unique stable matching. \(\square \)

Note that when there is no cycle, there is no need to choose the blocking pair intelligently in order to arrive at the stable matching (follows from Proposition 3.1). However, under SPC, we need to choose the blocking pair suitably. Theorem 3.1 leads us to the following question—Can we drop the SPC condition and still guarantee convergence? At this point, we do not have answer to this question, even though we believe the answer to be affirmative. It is also worth mentioning that not every stable match can be obtained via the Roth and Vande Vate’s algorithm (see Ma 1996; Klaus and Klijn 2007 for details). This also leaves open the following question: which stable matches can be obtained via the Knuth’s decentralized algorithm or the Roth and Vande Vate’s algorithm? In particular, will the convergence happen always if the market admits a unique stable matching?

We conclude this section with a couple of examples. Example 3.2 considers a market with multiple stable matches which exhibits the convergence of Knuth’s decentralized algorithm (in contrast to Tamura 1993). Example 3.3 considers a market with singleton core, which does not satisfy SPC. Nevertheless, the Knuth’s decentralized algorithm converges.

Table 1 Example 3.2
Full size table

Example 3.2

Consider the market with four men and four women and with the preferences given by

$$\begin{aligned}&P(m_1) = w_2, w_1, w_4, w_3;\quad P(w_1) = m_4, m_2, m_1, m_3 \\&P(m_2) = w_3, w_2, w_1, w_4;\quad P(w_2) = m_3, m_2, m_4, m_1 \\&P(m_3) = w_4, w_1, w_3, w_2;\quad P(w_3) = m_1, m_3, m_2, m_4 \\&P(m_4) = w_3, w_2, w_4, w_1;\quad P(w_4) = m_1, m_4, m_3, m_2. \end{aligned}$$

By using DAA and inspection, we see that the market has three stable matches and they are given by

$$\begin{aligned} \mu _M= & {} ( m_1 \leftrightarrow w_1, m_2 \leftrightarrow w_3, m_3 \leftrightarrow w_4, m_4 \leftrightarrow w_2), \\ \mu _W= & {} ( m_1 \leftrightarrow w_4, m_2 \leftrightarrow w_2, m_3 \leftrightarrow w_3, m_4 \leftrightarrow w_1 ), \\ \mu= & {} ( m_1 \leftrightarrow w_1, m_2 \leftrightarrow w_2, m_3 \leftrightarrow w_3, m_4 \leftrightarrow w_4). \end{aligned}$$

There are 24 matches possible in the market. In the Table 1, we list all the possible outcomes of Knuth’s Algorithm. It is evident from the Table 1 that Knuth’s decentralized algorithm always results in a stable matching.

Example 3.3

Consider the market with four men and four women and with the preferences given by

$$\begin{aligned}&P(m_1) = w_1, w_2, w_3, w_4;\quad P(w_1) = m_4, m_3, m_1, m_2 \\&P(m_2) = w_1, w_4, w_3, w_2;\quad P(w_2) = m_2, m_4, m_1, m_3 \\&P(m_3) = w_2, w_1, w_3, w_4;\quad P(w_3) = m_4, m_1, m_2, m_3 \\&P(m_4) = w_4, w_2, w_3, w_1;\quad P(w_4) = m_3, m_2, m_1, m_4. \end{aligned}$$

We can see that, by applying both men-optimal and women-optimal DAA, the market has unique stable matching. The unique stable match is given by

$$\begin{aligned} \mu = ( m_1 \leftrightarrow w_3, m_2 \leftrightarrow w_4, m_3 \leftrightarrow w_1, m_4 \leftrightarrow w_2). \end{aligned}$$

We can easily see that the market does not satisfy SPC, nevertheless, it has unique stable matching. Furthermore, Knuth’s decentralized algorithm converges to a stable matching. The Table 2 lists all the possibilities for the 24 matchings.

Table 2 Example 3.3
Full size table

4 An extension of Eeckhout’s SPC

Until now, we assumed that each agent prefers to be matched rather than being single. In this section, we allow the agents to remain single. This means that, the preferences P(m) of man m is, now, a strict ordering on \(W \cup \{m\}\) and the preferences P(w) of woman w is a strict ordering on \(M \cup \{w \}\). The rest of the concepts and notations are same as in Sect. 2.

Our main task in this section is to extend the notion of SPC to the markets with the possibility of unemployment and establish the extension of results in Sect. 3. We start with the extended notion of SPC.

Definition 4.1

(Generalized SPC) The matching market is said to satisfy generalized SPC if there exists \(1 \le l \le n\) such that the men and women can be arranged such that

  • \(w_i \succ _{m_i} w \) for each \( w \not \in \{w_1, w_2,\ldots , w_{i} \} \) and for each \(i = 1,2,\ldots , l\), whenever w is in the preference list of man \(m_i\),

  • \(m_i \succ _{w_i} m\) for each \( m \not \in \{m_1, m_2,\ldots , m_{i} \}\) and for each \(i = 1,2,\ldots , l\), whenever m is in the preference list of woman \(w_i\),

  • for \(i > l\), there exists \(i^\prime \le l \) such that \(m_i \succ _{m_i} w\) for \(w \not \in \{w_1, w_2,\ldots , w_{i^\prime } \}\), whenever w is in the preference list of man \(m_i\),

  • for \(i > l\), there exists \(\hat{i} \le l \) such that \(w_i \succ _{w_i} m\) for \(m \not \in \{m_1, m_2,\ldots , m_{\hat{i}} \}\), whenever m is in the preference list of woman \(w_i\).

Interestingly, generalized SPC extends the notion of SPC to include markets where some agents can be unemployed. Note that if each man or woman has preferences over everyone on the opposite side, then this definition reduces to the SPC introduced in Eeckhout (2000). Next we show that this class of matching markets is not void by proving that acyclic markets satisfy generalized SPC.

Proposition 4.1

Acyclic markets satisfy generalized SPC.

Proof

Recall from the discussion following Proposition 3.2 (which will apply in this case also) that if both \(m_1\) and \(m_2\) have preferences over two women \(w_1\) and \(w_2\), then they will rank them same.

Since the market is acyclic, there is a unique stable matching (see Romero-Medina and Triossi 2013a and also Proposition 3.4, which can be extended to the markets with unemployment). Let the number of single men (and single women) be \(n-l\). We choose \(\{m_{l+1},\ldots , m_n \} \) to be the set of all single men and \(\{w_{l+1},\ldots , w_n \}\) to be the set of all single women. For ordering the single agents exactly, we follow the procedure indicated below, where the ranking of other agents is discussed.

We claim that there is at least one pair of man and woman who are matched and they are best for each other; i.e. they prefer each other over others. Suppose not. We will construct a cycle following the idea of Proposition 3.4. Pick a man m and assume that he is matched with w under \(\mu \). Without loss of generality, suppose that w’s most preferred man is not m. Instead let this be \(m^\prime \). Similarly, let \(w^\prime \) be the best preference of \(m^\prime \), and continue with this process. Since there are only finitely many men and women, we will end up with a cycle. This contradicts the acyclicity assumption. Therefore, there is a matched pair who are best for each other.

Let \(P_1\) be the set of all pairs of men and women matched and who are the best for each other. If we remove this set of men and women from the market, then the new market will, still, satisfy the acyclicity condition. Also, the unique stable matching will be same as the original stable matching, except for the pairs already removed. Following the above procedure, we obtain another set of pairs of men and women, let us call this \(P_2\). Continuing this way, we end up with the sets \(P_1, P_2, \ldots \) Owing to the finiteness of the market, this process will exhaust all the men and women, and will end in finitely many steps giving rise to \(P_1, P_2,\ldots , P_k\). Now we order the men and women according to these sets, which will give us the required ordering satisfying the generalized SPC. Also, note that these sets may include men and women who are single. The order for these people also will follow the order of these sets starting from \(l+1\). \(\square \)

From the discussion in Sect. 3, we see that SPC is much weaker than the notion of acyclicity i.e., acyclicity implies SPC, but not the converse. Obviously this extends to generalized SPC since SPC implies generalized SPC. Nevertheless, we provide an example of a market where agents may not prefer to be matched with every agent on the other side.

Example 4.1

Consider the marriage market with men \(\{m_1, m_2, m_3 \}\) and women \(\{w_1, w_2, w_3 \}\) with preferences as follows:

$$\begin{aligned} \begin{aligned} P(m_1) : w_1, w_2&\qquad P(w_1) = m_1, m_3, m_2 \\ P(m_2) : w_1, w_2&\qquad P(w_2) = m_2, m_3 \\ P(m_3) : w_2, w_3, w_1&\qquad P(w_3) = m_3. \end{aligned} \end{aligned}$$

It is not hard to see that the market has cycles and satisfies generalized SPC.

We will now prove that the matching market under generalized SPC has singleton core, which extends the uniqueness result in Romero-Medina and Triossi (2013a).

Theorem 4.1

Under the generalized SPC,  the matching market admits a unique stable matching and is given by \(\mu (m_i) = w_i\) for each \(i=1, 2,\ldots , l,\) \(\mu (m) = m\) and \(\mu (w) = w\) for all \(m \ne m_i\) and \(w \ne w_i,\) \(i=1,2,\ldots , l.\)

Proof

We will only prove the uniqueness, since the proof that \(\mu \) is stable is obvious. Let \(\nu \) be any matching different from \(\mu \). Let i be the smallest number such that \(\nu (m_i) \ne w_i\). Without loss of generality let us assume a man m is matched to \(w_i\) and \(m \ne m_i\). It is easy to see that \((m_i, w_i)\) will form a blocking pair for the matching \(\nu \).

It is possible that for every \(i \in \{1, 2,\ldots , l \}\), \(\nu (m_i) = w_i\). In that case some man \(m \ne m_i\), \(i=1,2,\ldots , l\), \(\nu (m) = w\) for some \(w \ne w_i\), \(i=1,2,\ldots , l\). Obviously both m and w prefers to be single than matched to these by the hypothesis. Thus any matching other than \(\mu \) is not stable. This completes the proof. \(\square \)

Naturally, generalized SPC implies the convergence of Knuth’s decentralized algorithm.

Theorem 4.2

Under the generalized SPC,  Knuth’s decentralized algorithm converges.

Proof

The proof is analogous to the proof of Theorem 3.1, and is hence not repeated. \(\square \)

It is also possible to see our results using serial dictatorship mechanism as in (Romero-Medina and Triossi 2013a, Proposition 4). The agents, according to their order in SPC (or generalized SPC), are given the opportunity to select their partner. It is not difficult to notice that the outcome of this mechanism is exactly the unique stable matching.

5 Conclusions

The DAA is a centralized algorithm, whereas the algorithm proposed by Knuth is a decentralized algorithm. In this article, we provide conditions under which Knuth’s decentralized algorithm converges. Specifically, we prove that if the preferences of the men and women satisfy either the SPC condition or the acyclicity condition, then the algorithm converges to a stable matching. We also extended SPC to markets where agents may remain unmatched. Under the extended notion of SPC, we showed that the market will admit a singleton core. Further, we demonstrate the convergence of the Knuth’s decentralized algorithm under the notion of generalized SPC. In addition, the generalized SPC subsumes the acyclicity condition available in the literature. To the best of our knowledge, the generalized SPC seems to be the most general condition available in the literature for uniqueness, where the agents have an option of remaining single.

Theorem 3.1 (also Theorem 4.2) conveys an important insight regarding the convergence of a decentralized matching market to a stable matching. We offer a solution to the long standing question posed by Knuth—starting from any arbitrary matching, is there a convergence to a stable matching? Our result is also particularly relevant given the counterexample given in Tamura (1993) who shows that Knuth’s decentralized algorithm may cycle and therefore, not converge to a stable matching.

Our work can be extended in several directions. One interesting extension of our analysis is to consider marriage markets with indifferences. We also believe that our analysis can be useful to study one-sided markets. Moreover, completely characterising the matching markets with singleton core is still an open question.