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