\problemdata
{S00 ps4.5}
{Stable marriage}

\begin{problem}
%[[[New problem.  Comes from lecture notes from fall98---I believe
%Eric Lehmann wrote up a supplementary handout on this.  But
%beware---the old statement of this that I used in fall98 had the boys
%and girls reversed.]]]
It turns out that the stable marriage algorithm described in lecture
(Installment 2 of notes) is very unfair, in the sense that, in any
(live) execution of the algorithm:
\begin{itemize}
\item The boys end up paired up with the most preferred girl that they
possibly could get.
\item The girls end up paired up with the least preferred boy that they
possibly could get.
\end{itemize}
(So, being aggressive pays.)

More precisely, define $\ms{PP}$ (``possible pairs'') to be the set of
all (boy,girl) pairs that occur in any stable pairings.
Then, in the final state of the algorithm:
\begin{itemize}
\item If a boy $b$ likes a girl $g$ more than the partner he has received, then
$(b,g) \notin \ms{PP}$, that is, $g$ isn't even possible for him.
\item If a girl $g$ likes a boy $b$ less than the partner she has
received, then $(b,g) \notin \ms{PP}$. 
\end{itemize}

Prove these results.

\solution{
\begin{solution}

\begin{description}
\item[(a) ]

You can prove as an invariant, the claim that:
``If $b$ has crossed $g$ off his list, then $(b,g) \notin \ms{PP}$.''
This statement immediately implies the claim in (a).

%[[[Shishir: 
The key step is where g rejects b, and he crosses her off
his list. 
She rejects him in favor of some other boy b'.

Now, suppose for the sake of contradiction that P is a stable pairing
containing $(b,g)$.
We can show that $(b',g)$ form an unstable pair in P:
We know that $g$ prefers $b'$ to $b$, because in this step of the
algorithm, she rejects $b$ in favor of $b'$.
We have to argue that, also, $b'$ prefers $g$ to whomever he is matched up
with in P---call her $g'$.

This is a tricky argument.
Can argue it by contradiction, using the fact that the invariant is
true before the step.
Suppose for the sake of contradiction that $b'$ prefers $g'$ to $g$.
In the pre-state, $b'$ is pursing $g$, so he must have crossed off
his higher preference $g'$.
But by the invariant in the pre-state, this means that $(b',g') \notin
\ms{PP}$, that is, $(b',g')$ do not form a possible pair.
That's a contradiction, because we've assumed that they are paired in
the stable pairing $\ms{PP}$.
%]]]

\item[(b) ]

You can prove the invariant:

``If $g$ likes $b$ less than her most-preferred boy that is currently
pursuing her, then $(b,g) \notin \ms{PP}$.''
This statement implies the claim in (b).

This can be proved without using an inductive argument (or the
Invariant Theorem), but simply by contradiction using the invariant
used for part (a). 

%[[[Shishir:  It's not so simple to keep straight.

Suppose for the sake of contradiction, that there is some reachable
state in which
$g$ likes $b$ less than her most-preferred boy that is currently
pursuing her, call him $b'$, 
but $(b,g) \in \ms{PP}$.
Fix P, some stable pairing having $(b,g) \in P$.
We can show that $(b',g)$ form an unstable pair in P:
We know that $g$ prefers $b'$ to $b$, by the assumption above.
We have to argue that also $b'$ prefers $g$ to whomever he is matched
with in $P$, call her $g'$.

Suppose he doesn't (this is going to be a contradiction within a
contradiction!), that is $b'$ prefers $g'$ to $g$.
That is, $b'$ prefers $g'$ to the girl he is currently pursuing.
This means that $b'$ has crossed $g'$ off his list in the current state.
By the previous invariant, proved for part (a), it follows that
$(b',g') \notin \ms{PP}$.  
So surely we can't have $(b',g') \in P$.
This is a contradiction, which means that $b'$ does prefer $g$ to
$g'$.
That's what we needed to show above.

So, this all says that $(b',g)$ form an unstable pair in P.
That's a contradiction to the assumption that P is a stable matching.


%Shishir:
%You might find it helpful to write this in a structured way.  This is
%exactly the sort of proof where the logic gets confusing.
%Shishir: I have a handwritten structured version at home, but it has
%the boys and girls interchanged.  I think Eric probably type-set this
%and put it into the supplementary lecture notes for fall98.]]]
\end{description}


}
\end{problem}
