\documentclass{article}%
\usepackage{amsmath}%
\setcounter{MaxMatrixCols}{30}%
\usepackage{amsfonts}%
\usepackage{amssymb}%
\usepackage{graphicx}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Sunday, November 02, 2014 23:05:56}
%TCIDATA{LastRevised=Sunday, November 02, 2014 23:14:35}
%TCIDATA{}
%TCIDATA{}
%TCIDATA{}
\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{More on Stable Marriage and the Mating Ritual}
\maketitle
Note that although we found one stable marriage group through the mating
ritual, 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.
First we will show the following:
\begin{theorem}
The mating ritual marries every boy to his optimal spouse.
\end{theorem}
BO1) Suppose that some boy does not get his optimal girl. Show their must be a
first day that some boy, say Dick, crosses off his optimal girl, Jane.
BO2) Show this must be because Jane got serenaded by a preferred boy, say
Butch.
BO3) Show that Butch must not have crossed off his optimal spouse yet.
BO4) Show that Butch must have ranked Jane at least as high as his optimal
spouse.
BO5) Show that if there is a marriage between Jane and Dick, then Butch and
Jane form a rogue couple, and thus this is not a stable marriage.
\begin{theorem}
The mating ritual marries every girl to her pessimal spouse.
\end{theorem}
GP1) Suppose Dick and Jane marry as a result of the ritual. Show that in any
stable set of marriages, Dick ranks Jane at least as high as his spouse.
(Hint: we know that Dick gets his optimal spouse.)
GP2) Now suppose there were a marriage set where Jane marries Zed, and prefers
Dick to Zed. Show that Jane and Dick are a rogue couple, and this marriage set
is not stable.
\end{document}