Chapter 14 Two-sided Matchings: Stable Marriages

Let us now return to the marriage problem discussed in Section 6.4; we again consider a set $X$ of $n$ men, and a set $Y$ of $n$ women, but this time, instead of simply specifying whether a man–woman pair finds a marriage “acceptable,” we consider how desirable each party finds each potential partner: for any pair $x \in X, y \in Y$ , let $v_{x} (y)$ denote how valuable $x$ finds $y$ , and let $v_{y} (x)$ denote how valuable $y$ finds $x$ . We are interested in the question of whether we can find a perfect matching between men and women where everyone is “happy” with the assignment—that is, can we find a set of “stable marriages.”

14.1 Two-sided Matching Problems

To formalize this, let us first define such a matching problem and the notion of an outcome of a two-sided matching problem.

Definition 14.1. We refer to the tuple $Γ = (X, Y, v)$ where $X, Y$ are finite sets such that $| X | = | Y |$ , and $v_{z} : X \cup Y \to ℕ$ for $z \in X \cup Y$ , as a two-sided matching problem. An outcome $M$ of $Γ$ is a perfect matching in the complete bipartite graph over $X \cup Y$ .

Note that a two-sided matching problem can be thought of as a variant of a matching market, but this time not only the nodes on “the left” (i.e., the buyers) have a valuation for the matching, but also the nodes on “the right” (i.e., the items in the matching market) have their own valuations—this is why these types of problems are called two-sided matching problems.

We now turn to defining a notion of stability of an outcome of a matching problem; the notion is similar to the notion of a market equilibrium, and the notion of stability for exchange networks, but this time without any prices. Roughly speaking, an outcome (i.e., a matching $M$ ) is stable if there does not exists a pair $(x, y)$ that prefer each other to their current partners—such a pair is usually called a blocking pair. See Figure 14.1 for examples of stable and unstable matchings.

We turn to the formal definition.

Definition 14.2. An outcome $M$ of a two-sided matching problem $Γ = (X, Y, v)$ is stable if there does not exists $x \in X, y \in Y$ such that $v_{x} (y) > v_{x} (M (x))$ and $v_{y} (x) > v_{y} (M (y))$ .

**Figure 14.1:** An example of a stable (left) and an unstable (right) matching between four men and four women, whose preferences are indicated in the illustration. Notice, in the unstable matching, Charlie and Gloria constitute a “blocking pair”—they both prefer each other to their current partners; this instability is highlighted in red.

14.2 The Stable Marriage Theorem

The following theorem—referred as the stable marriage theorem—shows that every two-sided matching problem has a stable outcome. Furthermore, this stable matching can be efficiently found.

Theorem 14.1. A stable outcome $M$ exists for every two-sided matching problem $Γ = (X, Y, v)$ . Additionally, there exists an efficient procedure that finds this outcome in polynomial time in $| X |$ .

Proof. We present Gale–Shapley’s deferred acceptance algorithm (or simply, the DA algorithm) for finding a stable matching.

Initialize $M$ to the “empty” matching: for all $x \in X, y \in Y$ , $M (x) = ⊥$ , $M (y) = ⊥$ .
While there exists some man x that is unmatched (i.e., M(x) = ⊥) do the following:
- – Pick some unmatched man $x$ . Let $y$ be $x$ ’s preferred (according to $v_{x}$ ) “attainable” woman (breaking ties in some arbitrary way), where $y$ is attainable for $x$ if $y$ is currently unmatched (i.e., $M (y) = ⊥$ ) or $y$ prefers $x$ to her current partner $M (y)$ (i.e., $v_{y} (x) > v_{y} (M (y))$ ). (Such a woman must exist since the number of men and women are equal, and $x$ is unmatched, so there must exist at least one unmatched woman.)
- – If $y$ was matched, break up $y$ ’s earlier “engagement”: if $x^{'} = M (y) \neq ⊥$ , let $M (x^{'}) = ⊥$ .
- – Match $x$ with $y$ ; let $M (x) = y, M (y) = x$ . (Think of this as $x$ and $y$ getting “engaged.”)
Output $M$ (note that by construction $M$ is always one-to-one throughout the execution of the algorithm and thus $M$ is always a matching).

See Figure 14.2 for an illustration of the execution of the DA algorithm. Note that if the algorithm ends, every man is matched to some (unique) woman, and thus also all the women get a match, since there are as many women as men. Thus, the final matching $M$ is always a perfect matching.

**Figure 14.2:** The process of running the Deferred Acceptance Algorithm on the example from Figure 14.1. New proposals are indicated in green, existing engagements in black, and broken engagements in red.

Let us start by making a simple but useful observation:

Lemma 14.1. If a woman $y$ is unattainable to a man $x$ at some point in the execution of the algorithm, she will always remain so.

This lemma follows from the fact that a woman will only break an earlier engagement by “upgrading” to some man that she prefers over her current match.

We start by showing that the DA algorithm runs in polynomial time.

Claim 14.1. The DA algorithm ends within $| X |^{2}$ iterations.

Proof. First note that by Lemma 14.1, a man $x$ can never be engaged to the same woman $y$ twice—the only reason an engagement is broken off is if $y$ “upgrades” and thus she becomes unattainable to $x$ (and by Lemma 14.1 remains so for the rest of the execution). As a consequence, each man can get engaged at most $| Y | = | X |$ times; since there are $| X |$ men, and one engagement must occur in every iteration, we conclude that the number of iterations is at most $| X |^{2}$ .

■

Since each iteration can be implemented in polynomial time in $| X |$ , it follows that the DA algorithm always terminates within a polynomial (in $| X |$ ) number of steps. We next show that the matching output by the DA algorithm always is a stable matching.

Claim 14.2. The matching $M$ output by the DA algorithm is stable.

Proof. Assume, for contradiction, that $M$ is not stable; that is, there exists a blocking pair $(x, y)$ for $M$ such $v_{x} (y) > v_{x} (M (x))$ and $v_{y} (x) > v_{y} (M (y))$ . That means that $y$ is attainable to $x$ , yet $x$ is matched with some woman $y^{'} = M (x)$ that he likes less than $y$ . By Lemma 14.1, since $y$ is attainable to $x$ at the end of the execution, she must have been so throughout the execution. By construction of the algorithm, $x$ must thus have been engaged to $y$ at some earlier point since he would never have proposed to $y^{'}$ before trying to propose to $y$ first (and $y$ would have accepted since she is attainable to him). But this engagement could never have gotten broken, since the only way it can break is if $y$ no longer is attainable to $x$ , which is a contradiction, and thus $M$ must be stable.

■

This concludes the proof of Theorem 14.1.

■

The above-described DA algorithm is also called the “man-proposing” DA algorithm; we may also consider an alternative variant of it, called the “woman-proposing” DA algorithm, which is identically defined except that instead of having the men propose engagements (and the women accepting or rejecting them), we instead have the women propose (and men accept or reject). Subsequently, whenever we refer to the “DA algorithm,” we refer to the man-proposing DA algorithm.

14.3 Optimality of Stable Outcomes

We turn to analyzing the stable outcome computed by the DA algorithm. To simplify our treatment (and in accordance with much of the literature on matching), we restrict ourselves to the case when men and women have strict preferences over partners. Note that in this case, the DA algorithm only needs to take as input a profile of preferences $\vec{μ}$ over partners. More precisely, given a set of men $X$ and set of women $Y$ , a partner preference profile $\vec{μ}$ (over $X, Y$ ) as a profile of preferences such that $μ_{i}$ is a preference ordering over $Y$ if $i \in X$ and a preference ordering over $X$ if $i \in Y$ . Let $𝒱^{D A}$ denote the DA mechanism taking a partner preference profile as input.

Note that in the case of strict preferences, to determine whether a matching $M$ between $X$ and $Y$ is stable, it suffices to know the preferences of all players $\vec{μ}$ —we can thus refer to $M$ being a stable matching between $X, Y$ with respect to the partner preference profile $\vec{μ}$ .

We start by showing a surprising phenomenon: for the case of strict preferences, there always exists a stable outcome that is “optimal” for the men in the sense that every man $x$ gets matched to his best “achievable” partner $y$ , where a partner is achievable for $x$ if there exists some stable matching where $x$ gets matched to $y$ .

Definition 14.3. Given a partner preference profile $\vec{μ}$ over $X, Y$ , we say that $y \in Y$ is achievable for $x \in X$ (with respect to $\vec{μ}$ ) if there exists some stable matching $M$ with respect to $\vec{μ}$ such that $(x, y) \in M$ .

Definition 14.4. Given a partner preference profile $\vec{μ}$ over $X, Y$ , we say that a stable matching $M$ is man-optimal with respect to $\vec{μ}$ if every man $x \in X$ gets matched (with respect to $M$ ) with his most preferred (with respect to $μ_{x}$ ) achievable woman $y \in Y$ (with respect to $\vec{μ}$ ).

Note that man-optimal outcomes are always unique since when players have strict preferences, for every man there exists only one “most preferred” achievable woman, and this man must be matched to their most preferred achievable choice; that is, we have the following useful fact.

Fact 14.1. Given a partner preference profile $\vec{μ}$ over $X, Y$ , there exists at most one man-optimal stable matching with respect to $\vec{μ}$ .

We now turn to showing that the outcome produced by the (man-proposing) DA algorithm is (the unique) man-optimal matching.

Theorem 14.2. For every partner preference profile $\vec{μ}$ , $𝒱^{D A} (\vec{μ})$ outputs a man-optimal stable matching (with respect to $\vec{μ}$ ).

Proof. Assume not; let $x$ be the first man in the execution of the DA who is “rejected” by an achievable woman $y^{'}$ (i.e., some achievable woman $y^{'}$ is no longer available when it is $x$ ’s turn to get engaged). Since $y^{'}$ rejected $x$ , she must already be engaged to some man $x^{'}$ that she prefers to $x$ ; additionally, since $x$ was the first rejected man, $y^{'}$ must either be $x^{'}$ ’s optimal achievable choice, or preferred to it—in other words, from the point of view of $x^{'}$ , $y^{'}$ dominates every achievable choice that is distinct from $y^{'}$ .

Now, consider the stable matching $M$ where $x$ is matched with $y^{'}$ (such a matching must exist, since $y^{'}$ is achievable for $x$ ). Here, $y^{'}$ clearly prefers to switch to $x^{'}$ , and $x^{'}$ also prefers to switch to $y^{'}$ since $y^{'}$ dominated every achievable choice that is distinct from $y^{'}$ ; this contradicts stability.

■

An interesting corollary of this result is that the order in which the men get to make engagement proposals have no relevance to the outcome—we always get the unique man-optimal outcome.

Obviously, by the same token, the woman-proposing DA would instead give a “woman-optimal” outcome; see Figure 14.3 for an illustration. There is, however, an inherent asymmetry (or “unfairness”) in the outcomes generated by the algorithm. Man-optimal solutions, although stable, are not that great for the women, and vice versa.

Definition 14.5. Given partner preference profile $\vec{μ}$ over $X, Y$ , we say that a stable matching $M$ is woman-pessimal with respect to $\vec{μ}$ if every woman $y \in Y$ gets matched (with respect to $M$ ) with her least preferred achievable man $x \in Y$ .

Theorem 14.3. Given partner preference profile $\vec{μ}$ over $X, Y$ , a stable matching $M$ is man-optimal with respect to $\vec{μ}$ if and only if it is woman-pessimal with respect to $\vec{μ}$ .

Proof. We separately show each direction.

“Only-if” direction Assume for contradiction that $M$ is man-optimal, but not woman-pessimal; that is, there exists some woman $y$ that is matched with some man $x$ , but there exists some achievable man $x^{'}$ that $y$ likes less than $x$ . Consider the stable matching $M^{'}$ in which $y$ is matched with the (less desirable) $x^{'}$ (such a matching must exists since $x^{'}$ is achievable for $y$ ). Let $y^{'}$ denote the woman that $x$ (i.e., $y$ ’s original partner) is matched with in $M^{'}$ . Since $M$ was man-optimal, $x$ must strictly prefer $y$ to $y^{'}$ (by the assumption of strict preferences); and $y$ strictly prefers $x$ to $x^{'}$ , thus $M^{'}$ cannot be stable, which is a contradiction.

“If” direction The backward direction follows using a similar argument, except we now show that the original matching $M$ cannot be stable. Assume for contradiction that $M$ is woman-pessimal, but not man-optimal; that is, there exists some man $x$ that is matched with some woman $y$ , but there exists some achievable woman $y^{'}$ that $x$ likes more than $y$ . Let $x^{'}$ denote the man that $y^{'}$ is matched with in $M$ . Since $M$ is woman-pessimal, $y^{'}$ strictly prefers $x$ to $x^{'}$ (by the assumption of strict preferences); however, $x$ strictly prefers $y^{'}$ to $y$ , and so $M$ cannot be stable, which is a contradiction.

■

Thus, we see an interesting phenomenon: the order in which either the men or the women make proposals makes no difference in the final outcome, but whether the men or the women are proposers makes a big difference—the proposers get their optimal outcome, and the accepters get their pessimal outcome—it pays to be “pushy”!

14.4 Strategy-proofness of Two-sided Matching Rules

We turn to considering whether the DA algorithm is strategy-proof. Following our treatment of voting and one-sided matchings, we can define a two-sided matching context analogously to matching context except that now (a) both the left nodes and the right nodes are associated with a valuation function, and (b) the players’ types are preferences over partners: We say that $Γ = (2 n, Ω, T, v)$ is a two-sided matching market context if

$n \in ℕ$ (the number of men and women);
$Ω$ (the set of states) is the set of matchings between $X = {1, \dots, n}$ and $Y = {n + 1, \dots, 2 n}$ ;
for each player $i \in [2 n]$ , $T_{i}$ is a set of preference orderings $μ$ over $Y$ if $i \in [n]$ , and over $X$ if $i \in [n + 1, \dots, 2 n]$ ;

for every player

i

μ \in T_{i}

v_{i} (μ, M) \geq v_{i} (μ, M^{'})

M (i) >_{μ} M^{'} (i)

(that is, player

i

is happier if they get allocated a partner they prefer).

If it always holds that $v_{i} (μ, M) > v_{i} (μ, M^{'})$ (i.e., we have strict inequality) when $i$ prefers their partner in $M^{'}$ , we refer to the context as a two-sided matching context with strict preferences. Furthermore, if for each player $i$ , $T_{i}$ is the full set of preferences (i.e., all orderings are possible), we refer to the context as a complete two-sided matching context.

We refer to a payment-free mechanism $𝒱$ for a two-sided matching-market context as a two-sided matching rule $𝒱$ ; as usual, we say that $𝒱$ is strategy-proof if $𝒱$ is DST. In the context of two-sided matching, we will also consider two weaker notions of strategy-proofness where DST only holds for either the men or the women:

Definition 14.6. We say that a two-sided matching rule $𝒱$ is strategy-proof for the men for the two-sided matching market context $Γ = (2 n, Ω, T, v)$ if for every $\vec{μ} \in T$ , $μ_{i}$ is a dominant strategy for every $i \in [n]$ in $G^{Γ, \vec{t}, 𝒱}$ . If instead the above holds for every $i \in [n + 1, \dots, 2 n]$ , we say that $𝒱$ is strategy-proof for the women.

Clearly, a matching rule $𝒱$ is strategy-proof if and only if $𝒱$ is strategy-proof for both the men and the women. As we shall now see, the (man-proposing) DA algorithm is strategy-proof for the men in every complete two-sided matching context with strict preferences (and, symmetrically, the woman-proposing DA algorithm is strategy-proof for the women).

Theorem 14.4. $𝒱^{D A}$ is strategy-proof for the men for every complete two-sided matching context with strict preferences.

The theorem follows directly from Theorem 14.2 and the next proposition that shows that any voting rule that always (no matter what the preferences are) outputs man-optimal outcomes is strategy-proof for the men.

Proposition 14.1. Consider some complete two-sided matching context $Γ = (2 n, Ω, T, v)$ with strict preferences and a two-sided matching rule $𝒱$ . Assume that for every $\vec{μ} \in T$ , $𝒱 (\vec{μ})$ is a man-optimal stable matching with respect to $\vec{μ}$ . Then $𝒱$ is strategy-proof for the men for $Γ$ .

Proof [Advanced]. We refer to a matching rule that always outputs man-optimal stable matchings as being simply man-optimal. We start by showing that man-optimal two-sided matching rules satisfy a notion of monotonicity: the voting rule continues to output exactly the same matching if we modify some men’s preferences to rank the woman they previously got matched with the highest.

Lemma 14.2. Let $𝒱$ be a man-optimal two-sided matching rule. Let $\vec{μ} \in T$ be a preference profile, let $M = 𝒱 (\vec{μ})$ , and let ${\vec{μ}}^{'}$ be a preference profile where some of the men $s \in S$ rank $M (x)$ the highest (but have otherwise arbitrary preferences), and the remaining players $i \notin S$ have exactly the same preferences as in $\vec{μ}$ . Then, $𝒱 (\vec{μ}) = M$ .

Proof. Consider preference profiles $\vec{μ}, {\vec{μ}}^{'}$ as in the statement of the lemma, let $M = 𝒱 (\vec{μ})$ and $M^{'} = 𝒱 ({\vec{μ}}^{'})$ . We first show that all the men are at least as well off in $M^{'}$ as in $M$ with respect to the original preferences $\vec{μ}$ :

First, note that $M$ is stable with respect to the preferences ${\vec{μ}}^{'}$ as players $i \in S$ clearly do not want to change as they get their most preferred match, and thus none of the other players will want to change either, as their preferences are unchanged. Thus, by man-optimality of $M^{'}$ , all men $x \in S$ must still be matched with $M (x)$ . Additionally, by man-optimality of $M^{'}$ , all the other men must be at least as well off in $M^{'}$ as in $M$ with respect to ${\vec{μ}}^{'}$ , and thus also with respect to $\vec{μ}$ (as their preferences have not changed).

We now conversely show that all the men are also least as well off in $M$ as in $M^{'}$ (with respect to $\vec{μ}$ ) and from this can conclude that $M^{'} = M$ .

By the fact (which we showed above) that all men $x \in S$ are still matched with $M (x)$ in $M^{'}$ , it follows that $M^{'}$ is stable with respect to $\vec{μ}$ —no men in $S$ want to change, and thus, none of the others will either (since their preferences are the same). By man-optimality of $M$ , it thus follows that all the men are at least as well off (with respect to $\vec{μ}$ ) in $M$ as in $M^{'}$ .

We conclude that $M = M^{'}$ , which proves the lemma.

■

Armed with the above lemma, we turn to prove the proposition. Consider a man-optimal two-sided matching rule $𝒱$ , and assume for contradiction that $𝒱$ is not strategy-proof for the men. That is, there exists some preference profile $\vec{μ}$ , some man $i$ and some preference ordering $μ_{i}^{'}$ such that $i$ strictly prefers his match $y^{'}$ in $M^{'} = 𝒱 (μ_{i}^{'}, μ_{- i})$ to his match $y$ in $M = 𝒱 (\vec{μ})$ . We consider a set of “hybrid preferences”:

Let

μ_{i}^{1}

the preference ordering where

y^{'}

has been shifted up to the top in the (“original”) preferences

μ_{i}

, and let

M^{1} = 𝒱 (μ_{i}^{1}, μ_{- i})

. By Lemma 14.2, we have that

M^{1} = M^{'}

(as we only changed player

i

’s preferences from

μ_{i}^{'}

μ_{i}^{1}

, but made sure that

i

’s match in

M^{'}

was ranked first in

μ_{i}^{i}

, as required by the lemma).

Note that

M = 𝒱 (\vec{μ})

is stable with respect to

(μ_{i}^{1}, μ_{- i})

since the only difference between

μ_{i}^{1}

and

μ_{i}

is that we have “shifted-up”

y^{'}

μ_{i}^{1}

, but this shift does not affect the set of women that

i

prefers to

y

(as

y^{'}

must dominate

y

μ_{i}

), so

i

will not want to change in the shifted preferences, and consequently none of the others will either. By man-optimality of

𝒱

, it follows that no man is worse off in

M^{1}

than in

M

with respect to the preferences

(μ_{i}^{1}, μ_{- i})

, and consequently (since player

1

gets a better outcome in

M^{1}

with respect to

μ_{i}

), also with respect to the actual preferences

\vec{μ}

Let

B

be the set of men that are (strictly) better off in

M^{1}

compared to

M

(with respect to the actual preferences

\vec{μ}

); all the others,

Q = X - B

are as well off—that is, all men in

Q

have the same match in

M

and

M^{1}

. Note that

| B | \geq 1

, since at the very least

i \in B

. Let

\vec{μ^{2}}

denote the partner preference profile where for every man

x \in Q

, we have shifted up

M (x)

to the top position in

x

’s preferences starting from the original

\vec{μ}

, and let

M^{2} = 𝒱 (\vec{μ^{2}})

. By Lemma 14.2, we get that

M^{2} = M

Thus, we have that all the men in $B$ are strictly better off in $M^{1}$ than in $M^{2}$ with respect to $\vec{μ}$ , and all the remaining men (in $Q$ ) have exactly the same match. By uniqueness of man-optimal outcomes (i.e., by Fact 14.1), we can obtain $M^{2}$ by running the DA on $\vec{μ^{2}}$ in any man-proposing order. In particular, let us start by having the players in $Q$ get their top choice, and then pick any arbitrary order. Note that the players in $Q$ directly get their top choice, and then never change (since they need to end up with their top pick), so we can simply disregard those players and the women they get matched to.

Additionally, note that all the

| B | \geq 1

remaining women (not matched to men in

Q

) must at some point in the execution of the DA algorithm reject some man (in particular, they must reject their match in

M^{1}

, since all the men in

B

are better off in

M^{1}

with respect to

\vec{μ}

and thus also with respect to

\vec{μ^{2}})

. But in the DA algorithm, the last woman who gets proposed to will never reject. Thus, we have reached a contradiction.

This concludes the proof of the proposition.

■

14.5 Strategy-proofness vs. Stability

So, if we use the man-proposing DA algorithm, none of the men will ever want to deviate, and if we use the woman-proposing DA algorithm, none of the women will want to deviate. We would obviously like to have a mechanism that is strategy-proof for both the men and the women. Unfortunately, as the next theorem shows, no mechanism that outputs stable outcomes can be strategy-proof (for both men and women):

Consider a complete two-sided matching context $Γ = (2 n, Ω, T, v)$ with strict preferences. We say that $𝒱$ is stable for $Γ$ if $𝒱 (\vec{μ})$ is stable with respect to $\vec{μ}$ for every $\vec{μ} \in T$ .

Theorem 14.5. Consider a complete two-sided matching context $Γ = (2 n, Ω, T, v)$ with strict preferences such that $n \geq 3$ . There does not exists a two-sided matching rule $𝒱$ that is both stable and strategy-proof for $Γ$ .

Proof. Consider some complete context $Γ$ with strict preferences and assume for contradiction that there exists some two-sided matching $𝒱$ that is both stable and strategy-proof for $Γ$ .

We start by considering the case that $n = 3$ ; that is, consider three men ${M 1, M 2, M 3}$ and three women ${W 1, W 2, W 3}$ (we may without loss of generality assume that those are their “names”), and consider the partner preference profile $\vec{μ}$ specified as follows:

$M 1$ prefers $W 1 > W 2 > W 3$ , $M 2$ prefers $W 2 > W 1 > W 3$ , and $M 3$ prefers $W 1 > W 2 > W 3$ .
$W 1$ prefers $M 2 > M 1 > M 3$ , $W 2$ prefers $M 1 > M 2 > M 3$ , and $W 3$ prefers $M 1 > M 2 > M 3$ .

That is, $M 1, M 2$ ’s preferences are aligned—according to them the matches $(M 1, W 1)$ , $(M 2, W 2)$ are optimal; likewise, $W 1, W 2$ ’s preferences are aligned but orthogonally to the men’s preferences—according to them the matches $(M 1, W 2)$ , $(M 2, W 1)$ are optimal. The third man and woman ( $M 3, W 3$ ) are just “dummy” players that all the others place last. Thus, there are exactly two stable matchings with respect to $\vec{μ}$ :

$(M 1, W 1)$ , $(M 2, W 2)$ , $(M 3, W 3)$
$(M 1, W 2)$ , $(M 2, W 1)$ , $(M 3, W 3)$

Assume the $𝒱 (\vec{μ})$ picks the first of these matchings (it must pick one of them since $𝒱$ is stable). If so, the men are happy with the outcome, but both the women are not. In particular, if $W 1$ instead had reported $M 2 > M 3 > M 1$ , then the only stable outcome is $(M 1, W 2)$ , $(M 2, W 1)$ , $(M 3, W 3)$ . This follows by simply inspecting the six possible matchings:

$(M 1, W 1)$ can never be part of a stable matching, since then $W 1$ prefers to switch to $M 3$ (who prefers her).
$(M 1, W 3)$ can never be part of a stable matching, since $M 1$ prefers $W 2$ to $W 3$ (and $M 1$ is $W 2$ ’s top preference, so she would switch).
$(M 2, W 3)$ can never be part of a stable matching, since $M 2$ prefers $W 1$ to $W 3$ (and $M 2$ is $W 1$ ’s top preference, so she would switch).

Thus, we conclude that $(M 1, W 2), (M 2, W 1), (M 3, W 3)$ is the only stable matching under these new preferences. It follows that $𝒱$ must output it (under $W 1$ ’s deviation), and thus $W 1$ strictly gains by misreporting her preferences.

An analogous argument can be applied if the mechanism instead outputs the second matching. Finally, we remark that if $n > 3$ , then for every $i > 3$ , we can simply have man $i$ rank woman $i$ first, and woman $i$ rank man $i$ first. It follows that in any stable matching, for $i > 3$ , man $i$ must be matched to woman $i$ , and we can simply disregard these extra players and repeat the argument above.

■

We end this section by noting that Theorem 14.5 has intriguing social consequences: as we cannot hope to get a mechanism that is strategy-proof for “both sides,” when running a two-sided matching mechanism, we need to decide toward what side we want robustness to manipulation. Indeed, the DA algorithm is commonly used in practice: perhaps the most famous application is for matching residents to hospitals; in this application, the residents are acting as proposers and the hospitals as accepters (which means that the mechanism is strategy-proof for the residents, but also means that the outcome is “resident-optimal”).

Notes

The two-sided matching problem and the Deferred Acceptance algorithm were introduced by Gale and Shapley [GS62]; Gale and Shapley also proved the stable marriage theorem. Dubins and Freedman [DF81] and Roth [Rot82] showed the the DA algorithm is strategy-proof of the men; the proof we present here, however, is new (although it takes some inspiration from the proof in [GS85]). Roth [Rot82] showed the impossibility of mechanisms that are both strategy-proof and stable. See [RS92] for a more extensive survey of two-sided matchings. Alvin E. Roth and Lloyd S. Shapley received the Nobel Prize in Economic Sciences (for the “theory of stable allocations”) in 2012.