\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Stable Marriage (13)}
\author{Michael L. Littman}
\date{October 22nd, 1998}

\maketitle 

\section{RESIDENCY MATCHING}

\subsection{The Medical Track}

\ni Timetable for physicians:

\ul

\li Childhood (13 years).
\li High School (4 years).
\li College (4 years).
\li Medical School (4 years).
\li Residency (3-8 years).
\li Fellowship (optional 2-8 years).
\el

\ni Each phase change has entry requirements and an application
procedure.  The medical school to residency transition is the one
we're focussing on.


\subsection{Residency is Special}

\ni In college and grad school, programs are typically large enough
that it is possible to accept more students than are actually expected
to attend and it is satisfactory if slightly fewer or slightly more
than the expected number accept.

\ni Residency programs can have as few as one or two slots per year
and rarely more than 20.

\ni Can't leave things to chance!

\ni Hospitals wise to recruit students early (perhaps even years
before they graduate), to ensure a strong and full program.


\subsection{The Match}

\ni About 40 years ago, ``The Match'' was developed to rationally
assign prospective residents (students) to residency programs
(hospitals).

\ni Students submit a rank-order list (ROL) to the
\href{http://www.aamc.org/about/progemph/nrmp/start.htm}{National
Residency Match Program} (NRMP).  Hospitals rank-order the students,
too.

\ni NRMP finds a match and publishes its results in mid March.

\ni Legally binding!

\ni Used since 1952 based on a 1962 (!) Gale and Shapley paper.


\section{THE STABLE MARRIAGE PROBLEM}

\subsection{Simplified Problem}

\ni It turns out that there are some special complications in the
Match (couples match, program parity restrictions) that make it
difficult to analyze.  We'll look at an idealization of this problem.

\ni We've got $n$ boys and $n$ girls.  Each boy submits a ROL of all
$n$ girls.  Ditto for the girls.  (How much data do we have?)

\ni A {\em marriage\/} (or {\em matching\/}) is a bijection between
girls and boys.


\subsection{Example}

\ni Boys preferences:

\ni
\begin{tabular}{|l|llll|}
\hline
Albert & Laura & Nancy & Kira & Marcy \\
Brad   & Marcy & Kira & Nancy & Laura \\
Chuck  & Laura & Marcy & Kira & Nancy \\
Daniel & Nancy & Kira & Marcy & Laura \\
\hline
\end{tabular}

\ni .

\ni Girls preferences:

\ni
\begin{tabular}{|l|llll|}
\hline
Kira  & Brad & Albert & Daniel & Chuck \\
Laura & Daniel & Chuck & Albert & Brad \\
Marcy & Albert & Daniel & Chuck & Brad \\
Nancy & Brad & Albert & Daniel & Chuck \\
\hline
\end{tabular}

\ni .

\ni A marriage: (A, L), (B, K), (C, M), (D, N).

\subsection{Stability}

\ni Not a great coupling.  Why?

\ni A {\em stable marriage\/} is a marriage in which no boy-girl pair
would want to swap spouses.

\ni Such a pair is unstable because they'd rather dump their partners
and marry each other than stay with who they've got.

\ni {\bf Theorem 1}: If there is no unstable pair, then there is also no
unstable coalition.  Why?  A coalition is really just a set of pairs.

\ni Can you find a stable marriage for this group?

\subsection{Stability Checking}

\ni Here's an obvious algorithm for checking if a given marriage is
stable.

\begin{algorithm}{Check-Marriage}{R,M}
 \begin{FOR}{\EACH b \in \{1,n\}}
   \begin{FOR}{\EACH g \in \{1,n\}}
     bm \= \mbox{\sc Rank}(R_B[b], M_B[b]) \\
     bg \= \mbox{\sc Rank}(R_B[b], g) \\
     gm \= \mbox{\sc Rank}(R_G[g], M_G[g]) \\
     gb \= \mbox{\sc Rank}(R_G[g], b) \\
     \begin{IF}{(bg < bm)\mbox{ and }(gb < gm)}
       \RETURN (b,g)
     \end{IF}
   \end{FOR}
  \end{FOR} \\
 \RETURN {\tt True}
\end{algorithm}

\ni Here, $R_B[b]$ is the ROL for boy $b$, $R_G[g]$ is the ROL for
girl $g$, $M_B[b]$ is the mate of boy $b$ in matching $M$, and
$M_G[g]$ is the mate of girl $g$ in matching $M$.

\ni $M_G[M_B[b]] = $?.


\subsection{Rank Computation}

\ni $\mbox{\sc Rank}(L, p)$ is the rank position of person $p$ in ROL
$L$.

\begin{algorithm}{Rank}{L,p}
 \begin{FOR}{\EACH j \in \{1,n\}}
   \begin{IF}{L[j] = p}
       \RETURN j
   \end{IF}
 \end{FOR} \\
 \RETURN {\tt Bug!}
\end{algorithm}


\ni What's the total algorithm running time?

\ans{$\Theta(n^3)$.}

\ni Not hard to do better than this (HW).

\section{THE MATCHING ALGORITHM}

\subsection{Fundamental Result}

\ni {\bf Theorem 2}: There is always a stable marriage, for any well-formed
set of ROLs.

\ni To prove this, we describe an algorithm for finding such a
marriage.

\subsection{Matching Algorithm}

\begin{algorithm}{Match}{R}
 \begin{FOR}{\EACH i \in \{1,n\}}
   M_B[i] \= \mbox{free} \\
   \mbox{rejected}[i] \= 0 \\
   M_G[i] \= \mbox{free}
 \end{FOR} \\
 \begin{WHILE}{b \mbox{ is a free man}}
   g \= R_B[b][\mbox{rejected}[b]+1] \\
   \begin{IF}{M_G[g] = \mbox{free}}
      M_B[b] \= g \\
      M_G[g] \= b
   \ELSE
     b' \= M_G[g] \\
     \begin{IF}{\mbox{\sc Rank}(R_G[g], b) < \mbox{\sc Rank}(R_G[g], b')}
         \mbox{rejected}[b'] \= \mbox{rejected}[b'] + 1 \\
         M_B[b'] \= \mbox{free}\\
         M_B[b] \= g \\
         M_G[g] \= b
     \ELSE
         \mbox{rejected}[b] \= \mbox{rejected}[b] + 1
     \end{IF}
   \end{IF}
  \end{WHILE} \\
 \RETURN M
\end{algorithm}

\subsection{In Words}

\ni The boys {\em propose\/} (to their top-ranked girl that hasn't yet
rejected them) and the girls tentatively accept.  This is an {\em
engagement\/}.

\ni If a girl ever gets an offer from a boy that she likes better than
her current fiance, she breaks her old engagement for him.

\ni Stop when all boys are engaged.

\ni $M$ holds the tentative matching. $\mbox{rejected}[b]$ records the
rank position of $b$'s most recent rejection (ouch).

\ni Once $b$ is rejected by $g$, $b$ never needs to propose to $g$
again.  Why? 

\ans{She is already holding a proposal from someone better.}

\ni (It is possible to also have the girls do the proposing... we will
return to this later.)

\ni Example!

\subsection{More Theorems}

\ni We will soon prove a number of important facts about this
algorithm.

\ul

\li {\bf Theorem 3}: For every girl $g$, $\mbox{\sc Rank}(R_G[g], M_G[g])$
improves (decreases) throughout the execution of $\mbox{\sc Match}$.

\li {\bf Theorem 4}: The order in which the boys are chosen to propose
doesn't matter (you get the same marriage no matter what).

\li {\bf Theorem 5}: The algorithm will terminate before the ROL of any boy
is exhausted.

\li {\bf Theorem 6}: The returned matching is stable.

\li {\bf Theorem 7}: The boys get to marry the best girl that they could
possibly get in any stable marriage.  The matching is simultaneously
optimal for {\em all\/} of them!

\el


\subsection{Time Analysis}

\ni But first, how long does it take for $\mbox{\sc Match}$ to run?

\ni What happens in the while loop?  Either a free girl accepts her
first proposal or a boy gets rejected.  What's an upper bound for each
of these?

\ni So, that tells us how many times the loop is executed.  How much
work do we do per iteration?  We need to find a free man and we
execute {\sc Rank} several times.  These can both be done in $O(n)$.

\ni This gives us a running time of $O(n^3)$.

\subsection{Improving the Running Time}

\ni An easy change to the algorithm improves the running time to
$O(n^2)$.  

\ul

\li How can we make the search for a free man (boy) take constant
time?

\li How can we implement {\sc Rank} to run in constant time?  It needs
to, for example, take a boy $b$ and a girl $g$ and tell us where $b$
is on $g$'s ROL.  With some preprocessing, can do this with a single
array lookup.

\el

\ni Therefore, each iteration of the while loop takes constant time.
Total $O(n^2)$ time.


\section{UNDERSTANDING THE ALGORITHM}

\subsection{Termination}

\ni As simple as the algorithm is, its behavior is not immediately
obvious.

\ni Let's show that no boy can be rejected by {\em all\/} girls.

\ul

\li A boy $b$ is only rejected by a girl who is already engaged (not
to him).

\li So, the last rejection for $b$ can only come if all $n$ girls are
already engaged to someone better.

\li But there can only be $n-1$ boys better than $b$, so this can't
happen.

\el

\ni This proves Theorem~5: the algorithm terminates before the ROL of
any boy is exhausted.  We get a marriage!

\subsection{Correctness}

\ni Furthermore, the final marriage is stable (Theorem 6).  Proof by
contradiction.

\ul

\li Assume that there is some pair $(b,g)$ that prefer each other to
whomever they are matched to.

\li Since $b$ proposes strictly in order of his ROL, this means that
he must have proposed to $g$ at some point.

\li Since $b$ isn't engaged to $g$, that means $g$ must have rejected
$b$.

\li But, $g$ would only reject $b$ for someone she ranks more highly.

\li Therefore, by Theorem 3, $g$'s final fiance is ranked more highly
than $b$.

\li Therefore $g$ {\em doesn't\/} prefer $b$ to her mate.
Contradiction!

\el

\ni Since the algorithm always terminates (Theorem 5), and the
returned matching is stable (Theorem 6), then there is always a stable
marriage, for any well-formed set of ROLs (Theorem 2).  Note that this
is a proof by algorithmic correctness!

\subsection{Boy Optimality}

\ni We say that $(b,g)$ is a {\em stable pair\/} if there is some
stable marriage in which $b$ and $g$ are matched.  We say that $g$ is
a {\em stable partner\/} of $b$ and vice versa.

\ni The marriage returned by {\sc Match} assigns {\em every\/} boy to
his {\em favorite\/} stable partner!  We, therefore, call this the
boy-optimal match.

\ul

\li {\bf Claim:} At no point in the execution of {\sc Match} does a girl
reject a stable partner.  This means that the first time a boy
proposes to one of his stable partners, he gets to stay with her (and
consequently marries his favorite stable partner).

\li Let's assume that a stable pair is rejected.  Let $(b_1,g_1)$ be
the first such stable pair.  Let $b_2$ be the boy that causes the
breakup of $b_1$ and $g_1$.

\li Since $(b_1,g_1)$ is a stable pair, there is some stable marriage
that includes it.  In one such stable marriage, let $g_2$ be $b_2$'s
mate.  

\li But, a marriage that includes $(b_1,g_1)$ and $(b_2,g_2)$ can't be
stable!  Because $g_1$ rejected $b_1$ for $b_2$, we know $g_1$ would
rather be with $b_2$.  Because the $(b_1,g_1)$ breakup was the first,
we know that $b_2$ prefers $g_1$ to any other stable partner (such as
the hypothetical $g_2$).

\li So, $(b_1,g_1)$ isn't a stable pair---a contradiction---and,
therefore, no stable pair can be rejected.

\el

\ni This proves Theorem 7 (boy optimality), but it also implies
Theorem 4: you get the same marriage independent of the order in which
free boys propose.



\subsection{Girl Pessimality}

\ni Consider the pairing obtained by taking each girl and assigning
her to her {\em least favorite\/} stable partner.

\ni {\bf Claim:} The girl-pessimal pairing is a stable marriage, and it is
the same as the marriage returned by {\sc Match}.

\ni This can be shown by the same type of argument as above or by
appealing to the boy-optimality property of {\sc Match} in the right
way.

\ni Now, if we reverse the roles of boys and girls (girls propose and
boys tentatively accept), then we get a girl-optimal and boy-pessimal
marriage.


\section{BACK TO THE HOSPITAL}

\subsection{Matching Students to Hospitals}

\ni The problem of matching medical students to hospitals is a bit
different from what we've discussed.

\ni A single hospital usually takes on more than one student.

\ni This can be handled by actually treating a hospital as a group of
people (one per fillable slot).

\ni The same basic mathematical results hold in this variation (the
{\sc Match} algorithm always gives a unique, stable, boy-optimal
marriage).

\subsection{Matching Algorithm}

\ni So, who gets to ``play the boy'' in this setting?

\ul

\li Hospital-proposing algorithm: Hospital optimal, student pessimal.
No incentive for the hospitals to cheat.

\li Student-proposing algorithm: Student optimal.

\el

\ni From 1952 to 1997, a hospital-proposing (and therefore student
pessimal) algorithm has been used.


\subsection{Controversy!}

\ni The written information concerning the Match has confused some of
the medical students over the years:

\ul 

\li ``...each applicant is matched to the hospital program highest on
the applicant's rank order list that has offered the applicant a
position...''  (1995 NRMP Handbook)

\el

\ni Is this correct?

\ans{Yes, this is not the same as saying that the applicant gets the
highest possible hospital.}

\ni Someone, at some point, decided that this wasn't fair (both the
description and the process).  Some quotes from AMSA, October 1995.

\ul

\li ``Don't let the NRMP alone plan your future.  The American Medical
Student Association, as your advocate and voice, is demanding that the
scales be tipped in {\bf YOUR} favor to give the power of choice back
to the {\bf MEDICAL STUDENT}.'' (October, 1995).
% \href{http://pubweb.acns.nwu.edu/\%7ealan/nrmp1.htm}{Full page.}

\li ``The NRMP and its algorithm can be thought of as the rules to a
game with the hospital and the students acting as players (a game with
important consequences, as the outcome greatly affects careers and
lives).''
% \href{http://pubweb.acns.nwu.edu/\%7ealan/nrmp2.htm}{Full page.}

\el

\subsection{The Study}

\ni The students got enough people worked up that NRMP had to respond.

\ul

\li NRMP had economist Alan Roth do
\href{http://www.pitt.edu/\%7ealroth/nrmp.html}{a study} examining the
effect of changing the algorithm from basically hospital-optimal to
basically student-optimal.  (Why is it not absolutely optimal?)

\ans{Because of complications like couples matches.}

\li He used 5 years of actual ROLs and tested a large number of
variations of the matching algorithm.

\li He found that 91 out of 111,026 students would be affected by a
shift from roughly hospital-optimal to student-optimal (and only 65 of
them actually improved!).  That's about $.06$\%.

\el

\subsection{The Decision}

\ni From a \href{http://www.aamc.org/events/pressrel/970508.htm}{NRMP
Press Release}:


\ul

\li Washington, D.C., May 8, 1997--Beginning January 1, 1998, the
National Resident Matching Program (NRMP) will change the algorithm
used to match students and physicians with residency programs.
Although the new mathematical formula will effect less than 15 of the
over 22,000 individuals who participate in the Match annually, the
change refines a highly respected process that has served residency
training for over 45 years.

\li ...

\li Now, following 15 months of intense study, the NRMP has decided to
change the algorithm so that in a very small number of instances, a
few applicants will be matched to a more preferred position than they
would have received under the present process. ``Essentially, the new
algorithm improves the chances of one applicant in a thousand,'' said
NRMP Executive Director Robert L. Beran, Ph.D.  ``After careful
examination, the NRMP board supported this change in recognition of
the major impact the Match can have on the career plans of every
applicant.''

\li ...

\el



\section{OTHER NEAT FACTS}

\ul

\li Can be more students than hospital slots, or vice versa.  Theory
carries over (smaller set gets completely matched).

\li The same students are matched and the same hospital positions are
filled at every stable matching. (That is, any student who is
unmatched at one stable matching is unmatched at every stable
matching, and the hospital positions that are unfilled are the same at
every stable matching.)  Only the specific assignment of which matched
students are in which filled hospital positions differs between
different stable matchings.

\li When the student-proposing algorithm is used, but not when the
hospital-proposing algorithm is used, no student can possibly improve
his or her match by submitting an ROL that is different from his or
her true preferences.

\li There is a polynomial-time egalitarian algorithm (neither student
nor hospital optimal).

\li The student-optimal algorithm is, in fact, hospital pessimal (even
though hospitals don't directly give a ranking over groups of
students).

\li Couples match: The basic algorithm can be extended to permit
constraints on where pairs of people end up.  However, the nice
mathematics is trashed.

\el

\end{document}

