# Gale–Shapley algorithm is man-optimal

I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page https://sites.google.com/site/stablemarriageproblem/intro and here http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf relies crucially on the fact that the disagreement happens for the 1st time when a man M approaches a woman W and we are trying to prove that in no matching matching M can be paired up with W.

If possible could you also give alternative proofs.

• Have you tried looking at other resources? There are many resources on the Gale–Shapley algorithm, including a few books, and many of them will prove that the resulting matching is male– or female–optimal (depending on how you set up the algorithm). – Yuval Filmus Feb 4 '15 at 3:18

We use the following notation:

1. $M$ is the set of men, $W$ the set of women.
2. For a man $m$ and a set $W'$ of women, $\max_m W'$ is the woman which $m$ prefers the most among those in $W'$, or $\bot$ if $W'$ is empty. We similarly define $\max_w M'$ for a woman $w$ and a set $M'$ of men.

One way to view the Gale–Shapley algorithm is as maintaining a graph $G$ of possible matches. Here is pseudo-code for the Gale–Shapley algorithm from this point of view:

1. Create a complete bipartite graph $G$ with the men on one side and the women on the other side. The initial set of edges is thus $\{(m,w) : m \in M, w \in W\}$.
2. For each man $m \in M$, let $\operatorname{top}(m) = \max \{w : (m,w) \in G\}$ be the woman $m$ most prefers among his possible matches at this point; $m$ proposes to $\operatorname{top}(m)$.
3. For each woman $w \in W$, let $\operatorname{best}(w) = \max \{m : \operatorname{top}(m) = w\}$ be the man $w$ most prefers among those who propose to her; $w$ chooses $\operatorname{best}(w)$ (if different from $\bot$).
4. Remove $(m,\operatorname{top}(m))$ from $G$ whenever $\operatorname{best}(\operatorname{top}(m)) \neq m$, that is, remove $m$'s top choice as a possibility if she rejects him.
5. If any edge was removed from $G$ in Step 4, go back to Step 2.
6. Return the matching in which each man $m \in M$ is married to $\operatorname{top}(m)$, and each woman $w \in W$ is married to $\operatorname{best}(w)$.

The idea of the algorithm is that at each point, in every stable marriage, every match $(m,w)$ is an edge in $G$. The reason is as follows. Suppose that in Step 4, $\operatorname{best}(\operatorname{top}(m)) \neq m$ for some man $m \in M$, and consider any marriage in which $m$ is married to $w = \mathrm{top}(m)$. Let $m' = \mathrm{best}(w)$, so that $w = \mathrm{top}(m')$. Obviously $w$ by definition prefers $m'$ to $m$. Since $w$ was $m'$'s top possible choice, $m'$ must be married to someone he prefers $w$ over. Therefore $(m',w)$ is an unstable pair. This shows that no stable marriage can contain $(m,w)$, and so we can safely remove it from $G$ in Step 4.

Throughout the algorithm, no man $m \in M$ is ever left alone, i.e. there is always some $w \in W$ such that $(m,w) \in G$; this is important, since otherwise the algorithm isn't well-defined. This property holds due to the following list of observations:

1. Once $\operatorname{best}(w) = m \neq \bot$ at some stage for some woman $w \in W$, $\operatorname{best}(w) \neq \bot$ from that point on, and never becomes less desirable than $m$ from the point of view of $w$. This is because at the next iteration, $\operatorname{top}(m) = w$, so $\operatorname{best}(w)$ is at least as good as $m$.
2. If $\operatorname{best}(w_1),\operatorname{best}(w_2) \neq \bot$ at some iteration for $w_1 \neq w_2 \in W$, then $\operatorname{best}(w_1) \neq \operatorname{best}(w_2)$ at that iteration. This is since $\operatorname{top}(\operatorname{best}(w_1)) = w_1 \neq w_2$.
3. Every time an edge $(m,w)$ is removed, $\operatorname{best}(w) \neq \bot$. This is because $w = \operatorname{top}(m)$.

Suppose now that all edges adjacent to some man $m \in M$ are removed, and consider the iteration in which the last edge adjacent to $m$ is removed. At this point, all edges $(m,w)$ were removed, so by (3) and (1), $\operatorname{best}(w) \neq \bot$ for all women $w \in W$. By (2), the mapping $\operatorname{best}\colon W\to M$ is one-to-one and so in bijection. In particular, $m = \operatorname{best}(w)$ for some woman $w \in W$. But this means that $w = \operatorname{top}(m)$ and so $(m,w)$ would not be removed in Step 4. We conclude that no man $m \in M$ is ever left isolated.

Since we only remove edges, eventually Step 6 will be reached. At this point, $\operatorname{best}(\operatorname{top}(m)) = m$ for all men $m \in M$, and so $\operatorname{top}$ and $\operatorname{best}$ are inverses. This shows that the output is well-defined and a matching.

Moreover, the matching is stable. Indeed, suppose that $(m,w)$ was an unstable pair, $m$ preferring $w$ over $\operatorname{top}(m)$, and $w$ preferring $m$ over $\operatorname{best}(w)$. Since $m$ prefers $w$ over $\operatorname{top}(m)$, necessarily $(m,w) \notin G$. When this edge was removed, $w$ preferred $\operatorname{best}(w)$ over $m$, and by (1), at the end $w$ still prefers $\operatorname{best}(w)$ over $m$, leading to a contradiction.

Finally, the matching is man-optimal. This is because in any stable marriage, a man $m \in M$ is matched to one of its neighbors in the final graph $G$. The marriage output by the algorithm matches $m$ to his top choice $\operatorname{top}(m)$, so it is optimal from the point of view of $m$.

Moreover, the matching is woman-pessimal. For suppose there were some stable matching in which some woman $w \in W$ is matched to a man which she prefers less than her match $m = \operatorname{best}(w)$ returned by the algorithm. Since $G$ represents the only possible matches in stable marriages, $m$ must be matched to some woman he prefers less than $w = \operatorname{top}(m)$. Thus $(m,w)$ is an unstable pair, and we reach a contradiction.

This exposition is taken from Section 6.3 of this paper, where other algorithms are described and analyzed, culminating in Subramanian's fixed point algorithm.

Let $E$ be an execution of the algorithm. Let $H$ be a stable marriage and $H_E$ the output of $E$. For every $(m,w)$ in $H$ so that $m$ prefers his wife in $H$ over his wife in $H_E$, record the time that $w$ refused or broke-up with $m$ during $E$.

Assume that the set of such pairs is non-empty (towards a contradiction).

Let $(m_0,w_0)$ be such a pair with minimum time.

Let $w'$ be the wife of $m_0$ in $H_E$.

Since $m_0$ asked $w_0$ before $w'$ during $E$, but ended up marrying $w'$, we know that $w_0$ is not married to $m_0$ due to some specific $m_1$. And that $w_0$ prefers $m_1$ over $m_0$. ($m_1$ is not necessarily married to $m_0$; they were just engaged.)

Let $w_1$ be the wife of $m_1$ in $H$.

There are two cases:

1. If $m_1$ prefers $w_1$ over $w_0$: This means that prior to the engagement of $m_1$ and $w_0$, man $m_1$ asked $w_1$. This happened before $m_0$ was rejected by $w_0$, by the choice of $m_1$. Since $m_1,w_1$ are not married in $H_E$, this means that $w_1$ rejected $m_1$ before $w_0$ rejected $m_0$. A contradiction to the minimality.

2. If $m_1$ prefers $w_0$ over $w_1$: This is a contradiction to the stability of $H$, since $w_0$ also prefers $m_1$ over $m_0$.