1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Feb 4 '15 at 3:18
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.