problemdata       % Takes 5 *mandatory* arguments
        {computational-processes-5}             % latex-friendly label for the prob.
        {computational-processes}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {S02 PS5} % Usage (list ones you are aware of).
        {Jack Kwok, S02}        % Last revision info (author, date).

\begin{problem}
Four VI-A students would like a position at a company.  There are four
companies, each with one position for a VI-A student.  Below are the
students' rankings of the companies and the companies' rankings of the
students.

\begin{center}
\begin{tabular}{l|c} 
Student & Ranking of Companies \\ \hline
Nikos   & Lotus, IBM, Compaq, Akamai \\
Yu-Han  & Compaq, Lotus, Akamai, IBM \\
Radhika & Compaq, Lotus, IBM, Akamai\\
Tina    & Akamai, Compaq, Lotus, IBM 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l|c}
Company & Ranking of Students \\ \hline
Compaq  & Yu-Han, Tina, Nikos, Radhika \\
Lotus   & Yu-Han, Radhika, Nikos, Tina \\
IBM     & Radhika, Yu-Han, Nikos, Tina \\
Akamai  & Tina, Yu-Han, Radhika, Nikos
\end{tabular}
\end{center}

Based on the rankings, the VI-A office will assign one student to each
company so the assignment forms a stable marriage set.

\bparts

\ppart There are VI-A student, $S$, and a company, $C$, that would form a
rogue pair in \emph{any} assignment in which $S$ was not assigned to $C$.
Give an example of such a pair $(S,C)$, and briefly explain why your
example has this property.

\solution{Tina likes Akamai best and Akamai likes Tina best.  So these
two would be sure to prefer each other over their spouses if they were not
married, \ie they would be a rogue pair if they were not married.  Yu-Han
and Compaq are another such pair.}

\ppart Verify that in this case, the Mating Algorithm yields the same
assignment whether Students are treated as Boys or as Girls.

\solution{Either way, the result is the following assignment:
\begin{center}
\begin{tabular}{l|l|} 
Student & Companies \\ \hline
Nikos  & IBM \\
Yu-Han     & Compaq \\
Radhika   & Lotus\\
Tina    & Akamai
\end{tabular}
\end{center}
}

\ppart Explain why this implies that there is only one possible stable
assignment (even including possible stable assignments that may not be
produced by the Gale/Shapley Mating Algorithm).

\solution{In the student-optimal (pessimal) assignment, a student $S$,
is assigned to their most (least) preferred company, $C$, among all
possible companies they could be assigned to in a stable assignment.  So
in any stable assignment, $S$ would be to be assigned to a company they
like no worse than $C$ nor more than $C$, so they have to be assigned to
$C$ no matter what.}

\eparts
\end{problem}


