        \problemdata       % Takes 5 *mandatory* arguments
        {vi-a}             % latex-friendly label for the prob.
        {stable-marriages}  % The topic(s) of the problem content.
        {karger tut5, old problems}               % Source (if known)
        {F01 tut6-3} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
Four people are interested in participating in the VI-A
program where each person ranks his top choices of companies and the
companies rank the students as well.  The people Albert, Jaime, Christos,
and Thien-loc are interested in companies AT\&T, Bellcore, Compaq, and
Draper Labs.  Below are the students' rankings of the companies and
the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Jaime:     & AT\&T, Bellcore, Draper, Compaq \\
Christos:   & Compaq, Draper, AT\&T, Bellcore \\
Thien-loc:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company   & Students \\ \hline
AT\&T:    & Thien-loc, Albert, Christos, Jaime \\
Bellcore: & Christos, Jaime, Albert, Thien-loc \\
Compaq:   & Thien-loc, Christos, Albert, Jaime \\
Draper:   & Jaime, Thien-loc, Christos, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?

\solution{
You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Jaime:     & AT\&T & 1\\
Christos:   & Compaq & 1\\
Thien-loc:    & Draper &1
\end{tabular}
\end{center}
}

\problempart What is a company-optimal stable marriage set for
this problem?

\solution{Similarly, you were guaranteed to get a company-optimal
stable marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  The result
is the following assignment:

\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Jaime & 2\\
Compaq:   & Christos & 2\\
Draper:   & Thien-loc & 2
\end{tabular}
\end{center}
}

% source: Fall 2000 Problem Set 5
% topics: Matching, intuition

\problempart Give an example of a stable match between 3 boys and 3 girls
where no person gets their first choice.

\solution{Call the boys $1, 2, 3$ and the girls $a, b, c$.  Consider
the following preference list:

\begin{center}
\begin{tabular}{llll||llll} \hline
choice& 1st& 2nd& 3rd& choice& 1st& 2nd& 3rd \\ \hline
1& a& b& c& a& 2& 3& 1 \\
2& b& c& a& b& 3& 1& 2 \\
3& c& a& b& c& 1& 2& 3 \\ \hline
\end{tabular}
\end{center}
   
The matching $(1, b), (2, c), (3, a)$ is stable even though no person
gets their first choice.  

To see the intuition behind this solution, notice first that the first
choice of any boy has that boy as her last choice and vice versa.  
Second, notice that everyone ends up with their second choice.  

Since we show a pairing where everyone has their second choice, this 
is stable because the only way to have a rogue pair is for a boy
or girl to want their first choice, but their first choice always 
likes them least so will never want to leave their current partner.  
Therefore, we end up with a stable pairing where no one gets their
first choice.}

%\problempart Can a stable match where no person gets their first choice be
%produced by the matching algorithm described in the lecture notes?  If
%yes, state an example and show why the example works.  If not, prove
%using an invariant.

%\solution{Yes. For $n=4$, for boys $1, 2, 3, 4$ and the girls $a, b,
%c, d$, the following preference list yields such a match (x choices
%don't matter):
%
%\begin{center}
%\begin{tabular}{lllll||lllll} \hline
%choice& 1st& 2nd& 3rd& 4th& choice& 1st& 2nd& 3rd& 4th \\ \hline
%1& a& c& x& x& a& 3& 2& 1& 4 \\
%2& b& a& x& x& b& 1& 4& 3& 2 \\
%3& b& d& x& x& c& x& 1& x& x \\
%4& a& b& x& x& d& x& 3& x& x \\ \hline
%\end{tabular}
%\end{center}

%The matching algorithm executes as follows:%
%
%\begin{description}
%\item[Round 1] $a$ picks $1$. $b$ picks $3$. $2, 4$ are dropped.
%\item[Round 2] $a$ picks $2$. $b$ picks $4$. $1, 3$ are dropped.
%\item[Round 3] $c$ picks $1$. $d$ picks $3$.
%\end{description}
%}

\end{problemparts}

\end{problem}
