\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Thursday, August 21, 2008 14:03:59}
%TCIDATA{LastRevised=Monday, November 03, 2014 12:39:17}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}
\title{Math 443/543 Graph Theory Notes: Stable Marriage}
\author{David Glickenstein}
\maketitle
\section{Stable Marriage problem}
Suppose there are a bunch of boys and and an equal number of girls and we want
to marry each of the girls off. Thus we want to create a perfect matching.
However, in addition, each boy has his preferences and each girl has her
preferences, each a complete ranking with no ties. The preferences do not need
to be symmetric, though, unlike in the dancing problem, we assume that each
couple is compatible (no infinite rankings). Now, there could be a problem.
Consider the graph on M-p.12. In this case, every boy likes Angelina best and
every girl likes Brad best. If Brad is married to Jen and BillyBob is married
to Angelina, then we find that Brad and Angelina like each other more than
their spouses. This is called a \emph{rogue couple}. We want to avoid this
situation, as it would strain marriages.
\begin{definition}
A \emph{rogue couple} is a pair of a boy $B$ and a girl $G$ such that $B$
likes $G$ more than his spouse and $G$ likes $B$ more than her husband. A
matching is \emph{stable} if it contains no rogue couples.
\end{definition}
We will study stable marriage, and show that it is always possible to create
stable marriages. This is in contrast to the buddy problem, where we do not
specify boys and girls and just see if their are stable pairs of buddies. In
fact, this is not true, as we see in the graph on M-p. 13. We can check the
possibilites on by one, but see that there is always a rogue couple.
\section{Solution of the Stable Marriage problem: The Mating Ritual}
We propose a method to solve this problems using a mating ritual (I think this
is due to Gale-Shapley). Each day, we do the following:
Morning: Each girl stands on her balcony. EAch boy stands under the balcony of
his favorite girl on his list and serenades her. If there is no girl on his
list, he stays home.
Afternoon: Each girl who has one or more suitors serenading her says to her
favorite suiters to come back tomorrow and maybe we'll get married. She tells
the others to get lost.
Evening: Each shunned boy crosses the girl off his list.
We continue like this until every girl has at most one suitor, and then every
girl with a suitor marries that suitor.
It turns out that (1) this procedure ends, (2) everyone gets married, and (3)
the resulting marriages are stable.
\begin{proposition}
There is a marriage day, when people finally get married.
\end{proposition}
\begin{proof}
Every day on which the ritual has not terminated, at least one boy crosses one
girl off his list, since there must be one girl who is serenaded by at least
two boys, one of whom she must refuse. Since there are $n$ boys with $n$
entries on their list, there are at most $n^{2}$ girls names on all lists.
Since at least one name is crossed off one list every day, it can only last
for $n^{2}$ days at most.
\end{proof}
Is this a good upper bound for the number of days?
\begin{corollary}
Every girl who is visited once gets married. Moreover, if she is visited by a
boy $B,$ she will like her eventual husband at least as much as she likes $B.$
\end{corollary}
\begin{proof}
Every girl who is visited once continues to have her first choice among
serenaders return, so since there is a marriage day, each of these girls must
get married. Furthermore, if she doesn't like anyone more than boy $B$ that
visits her, she will continue to choose $B.$
\end{proof}
\begin{proposition}
\label{married prop}Everyone gets married.
\end{proposition}
\begin{lemma}
For each girl $G$ and boy $B,$ if $G$ is crossed off of $B$'s list, then $G$
likes another boy $B^{\prime}$ more than she likes $B.$
\end{lemma}
\begin{proof}
By the mating ritual, if $G$ is crossed off $B$'s list, then $G$ has said no
to him, and thus has been serenaded by a boy she likes better.
\end{proof}
\begin{proof}
[Proof of Proposition \ref{married prop}]Suppose some boy $B$ has only one
name $G$ left on his list. Since his list had included all girls, that means
that he today, he will have visited all of the girls. That means that all of
the girls will eventually get married.
\end{proof}
\begin{proposition}
The resulting marriages are stable.
\end{proposition}
\begin{proof}
Let $B$ be an arbitrary boy and let $G$ be a girl who is not his wife. We will
show that $B$ and $G$ do not form a rogue couple. Suppose first that $G$ is
not on $B$'s list. That means that $G$ already turned $B$ down and hence likes
her husband more than she likes $B,$ so they do not form a rogue couple. Now
suppose $G$ is on $B$'s list. That means that $B$ likes his wife more than he
likes $G,$ and again they are not a rogue couple.
\end{proof}
It is now interesting to consider who comes out better in this process, the
girls or the boys. It looks like the girls have their choice, telling boys no
when they don't like them, but they do not. In fact, the opposite is true. The
boys are starting off with their favorite and working down the list, while the
girls are settling for the best among those who see them.
Note that although we found one stable marriage group, there may be others.
However, sometimes certain pairings must be in any assignment of stable marriages.
\begin{definition}
Given any marriage problem, one person is in another person's \emph{realm of
possible spouses} if there is a stable matching in which the two people are
married. A person's \emph{optimal spouse} is their most preferred person
withing the realm of possibility. A person's \emph{pessimal spouse} is their
least preferred person in their realm of possibility.
\end{definition}
Since there is at least one stable marriage, everyone has an optimal and
pessimal spouse. Note that with regard to the mating ritual:
\begin{theorem}
The mating ritual marries every boy to his optimal spouse.
\end{theorem}
\begin{proof}
Suppose that some boy does not get his optimal girl. There must be a day when
he crosses off his optimal girl. Moreover, there must be a first day when a
boy Dick crosses out his optimal girl Jane. This must be because Jane got
serenaded by a preferred boy, Butch. Since this is the first time a boy
crosses off his optimal spouse, Butch must not have crossed off his optimal
spouse yet. But this means that Butch must have ranked Jane at least as high
as his optimal spouse. If there is a marriage between Jane and Dick, but then
we have argued that Butch and Jane form a rogue couple, and thus this is not a
stable marriage.
\end{proof}
\begin{theorem}
The mating ritual marries every girl to her pessimal spouse.
\end{theorem}
\begin{proof}
Suppose Dick and Jane marry as a result of the ritual. We already know that
Jane is Dick's optimal spouse. So in any stable set of marriages, Dick ranks
Jane at least as high as his spouse. Now suppose there were a marriage set
where Jane marries Zed, and prefers Dick to Zed. Then we see that Jane and
Dick are a rogue couple, and this marriage set is not stable.
\end{proof}
Some applications of this problem:
\begin{itemize}
\item Matching residents to hospitals.
\item Matching web traffic to servers.
\end{itemize}
\section{Example}
Four students have applied for graduate school at University of Arizona, UC
Berkeley, Cornell, and UC Davis. Both the students and schools have ranked
them, and here are their preferences:
\bigskip%
\begin{tabular}
[c]{l|l}%
Student & Schools\\\hline
Wanda & UA, UC Davis, Cornell, UC Berkeley\\
Xander & Cornell, UC Davis, UC Berkeley, UA\\
Yvonne & UA, UC Berkeley, Cornell, UC Davis\\
Zack & UC Berkeley, Cornell, UC Davis, UA
\end{tabular}
\qquad
\bigskip%
\begin{tabular}
[c]{l|l}%
School & Students\\\hline
U Arizona & Zack, Yvonne, Wanda, Xander\\
UC Berkeley & Xander, Zack, Yvonne, Wanda\\
Cornell & Zack, Wanda, Yvonne, Xander\\
UC Davis & Yvonne, Xander, Wanda, Zack
\end{tabular}
\bigskip
We can use the mating ritual to find two stable assignments of students to schools.
\end{document}