\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}[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}