\documentclass{homework}
\insolution{\author{Carl Eastlund (\url{cce@ccs.neu.edu})}}
\subject{CS 4800: Algorithms and Data}
\insolution{\date{\today}}
\inassignment{\date{Due \textbf{Thursday, September 13, 2012} in class.}}
\title{Homework 1}
\insolution{\subtitle{Sample Solution}}
\begin{document}
\maketitle
\exercise[(2 points)]
\begin{problem}
Decide whether you think the following statement is true or false.
If it is true, give a short explanation. If it is false, give a
counterexample.
\begin{quotation} \noindent
\emph{True or false? In every instance of the Stable Matching
Problem, there is a stable matching containing a pair \((m,w)\) such that
\(m\) is ranked first on the preference list of \(w\) and \(w\) is ranked
first on the preference list of \(m\).}
\end{quotation}
\end{problem}
\insolution{
\begin{solution}
The above statement is false. Consider the following example, which also
appears on page 5 of section 1.1 in Kleinberg and Tardos:
\begin{list}{}{}
\item \(m\) prefers \(w\) to \(w'\).
\item \(m'\) prefers \(w'\) to \(w\).
\item \(w\) prefers \(m'\) to \(m\).
\item \(w'\) prefers \(m\) to \(m'\).
\end{list}
By straightforward inspection, none of the pairs in this
example---\((m,w)\), \((m,w')\), \((m',w)\), and \((m',w')\)---have two
partners ranked first on each other's preference list. Thus no matching,
stable or otherwise, can contain such a pair.
\end{solution}
}
\exercise[(2 points)]
\begin{problem}
Decide whether you think the following statement is true or false.
If it is true, give a short explanation. If it is false, give a
counterexample.
\begin{quotation} \noindent
\emph{True or false? Consider an instance of the Stable Matching
Problem in which there exists a man \(m\) and a woman \(w\) such that
\(m\) is ranked first on the preference list of \(w\) and \(w\) is ranked
first on the preference list of \(m\). Then in every stable matching \(S\)
for this instance, the pair \((m,w)\) belongs to \(S\).}
\end{quotation}
\end{problem}
\insolution{
\begin{solution}
The above statement is true. Consider any stable matching \(S'\) which does
not contain \((m,w)\). There must then be pairs \((m,w')\) and \((m',w)\)
in \(S'\). However, because \(w\) ranks first on the preference list of
\(m\), \(m\) prefers \(w\) to \(w'\). Symmetrically, \(w\) prefers \(m\) to
\(m'\). The pair \((m,w)\) therefore constitutes an instability in \(S'\).
This contradicts our assumption that \(S'\) is stable. We conclude that
every stable matching \(S\) must contain \((m,w)\).
\end{solution}
}
\exercise[(5 points)]
\begin{problem}
Gale and Shapley published their paper on the Stable Matching
Problem in 1962, but a version of their algorithm had already been in use for
ten years by the National Resident Matching Program for the problem of
assigning medical residents to hospitals.
Basically, the situation was the following. There were \(m\) hospitals, each
with a certain number of available positions for hiring residents. There were
\(n\) medical students graduating in a given year, each interested in joining
one of the hospitals. Each hospital had a ranking of the students in order of
preference, and each student had a ranking of the hospitals in order of
preference. We will assume that there were more students graduating than
there were slots available in the \(m\) hospitals.
The interest, naturally, was in finding a way of assigning each student to at
most one hospital, in such a way that all available positions in all hospitals
were filled. (Since we are assuming a surplus of students, there would be
some students who do not get assigned to any hospital.)
We say that an assignment of students to hospitals is \emph{stable} if neither
of the following situations arises.
\begin{itemize}
\item First type of instability: there are students \(s\) and \(s'\), and a
hospital \(h\), so that
\begin{itemize}
\item \(s\) is assigned to \(h\), and
\item \(s'\) is assigned to no hospital, and
\item \(h\) prefers \(s'\) to \(s\).
\end{itemize}
\item Second type of instability: there are students \(s\) and \(s'\), and
hospitals \(h\) and \(h'\), so that
\begin{itemize}
\item \(s\) is assigned to \(h\), and
\item \(s'\) is assigned to \(h'\), and
\item \(h\) prefers \(s'\) to \(s\), and
\item \(s'\) prefers \(h\) to \(h'\).
\end{itemize}
\end{itemize}
So we basically have the Stable Matching Problem, except that (i) hospitals
generally want more than one resident, and (ii) there is a surplus of medical
students.
Show that there is always a stable assignment of students to hospitals, and
give an algorithm to find one.
\end{problem}
\insolution{
\begin{solution}
We demonstrate constructively that there is always a stable assignment of
students to hospitals by modifying the Gale-Shapley algorithm. The set of
students \(s\) looking for residencies is \(R\) and the set of hospitals
\(h\) looking to fill resident positions is \(H\). We use \(H\) in the role
of \(M\) and \(R\) in the role of \(W\). Our algorithm follows.
\begin{list}{}{}
\item Initially all \(s \in R\) are unassigned and all positions at all
hospitals \(h \in H\) are open.
\item While there is a hospital \(h\) with at least one open position and
which has not offered a position to every student:
\begin{list}{}{}
\item Choose such a hospital \(h\).
\item Let \(s\) be the highest-ranked student in \(h\)'s preference list
to whom \(h\) has not yet offered a position.
\item If \(s\) is unassigned, then:
\begin{list}{}{}
\item \((h,s)\) become assigned and a position closes at \(h\).
\end{list}
\item Otherwise, if \(s\) is currently assigned to \(h'\):
\begin{list}{}{}
\item If \(s\) prefers \(h'\) to \(h\), then:
\begin{list}{}{}
\item \(h\)'s position remains open.
\end{list}
\item Otherwise, if \(s\) prefers \(h\) to \(h'\):
\begin{list}{}{}
\item \((h,s)\) become assigned and a position closes at \(h\).
\item \((h',s)\) becomes unassigned and another position opens at
\(h'\).
\end{list}
\end{list}
\end{list}
\item Return the set \(S\) of assigned pairs.
\end{list}
The proof that this algorithm produces a stable assignment follows the same
form as the proof that the Gale-Shapley algorithm produces a stable matching
in Kleinberg and Tardos. We start by establishing several intermediate
facts. Where the facts and their justification follow similar reasoning as
in the original Gale-Shapley algorithm, we omit an explanation.
\begin{fact}
\label{fact:student-employed}
A student \(s\) remains assigned from the time of receiving the first
offer, and the sequence of assigned positions improves in terms of \(s\)'s
preference ranking.
\end{fact}
\begin{fact}
\label{fact:hospital-progress}
The sequence of students to whom a hospital \(h\) makes offers gets worse
and worse in terms of \(h\)'s preference list.
\end{fact}
\begin{fact}
The algorithm terminates after at most \(|H|\cdot|R|\) iterations of the
``while'' loop.
\end{fact}
\begin{fact}
If \(h\) has open positions at some point in the execution of the
algorithm, then there is a student to whom the hospital has not yet made
an offer.
\end{fact}
\begin{just}
By fact~\ref{fact:student-employed}, if \(h\) had made every student an
offer, then every student would be employed. Since we assign only one
student to each position, and there are fewer positions than students,
this is a contradiction. Therefore no hospital can \emph{ever} make an
offer to every student in this algorithm.
\end{just}
\begin{fact}
The set \(S\) returned at termination assigns every position at every
hospital.
\end{fact}
\begin{fact}
The set \(S\) returned at termination is a stable assignment.
\end{fact}
\begin{just}
We must consider both kinds of instability. In both cases, we assume that
an instability exists and derive a contradiction.
\begin{itemize}
\item Assume that there are students \(s\) and \(s'\) and a hospital \(h\)
such that \(s\) is assigned to \(h\), \(s'\) is unassigned, and \(h\)
prefers \(s'\) to \(s\). If \(h\) had ever made an offer to \(s'\),
then by fact~\ref{fact:student-employed} \(s'\) would still be assigned.
If \(h\) never made an offer to \(s'\), that would imply it prefers
\(s\) to \(s'\). Either way presents a contradiction.
\item Assume that there are students \(s\) and \(s'\) and hospitals \(h\)
and \(h'\) such that \(s\) is assigned to \(h\), \(s'\) is assigned to
\(h'\), \(h\) prefers \(s'\) to \(s\), and \(s'\) prefers \(h\) to
\(h'\). If \(h\) had ever made an offer to \(s'\), then \(s'\) would
have an assignment to a hospital ranked at least as high as \(h\) in the
preference list of \(s'\). If \(h\) never made an offer to \(s'\), that
would imply it prefers \(s\) to \(s'\). Either way presents a
contradiction.
\end{itemize}
It follows that \(S\) is a stable assignment.
\end{just}
\end{solution}
}
\exercise[(5 points)]
\begin{problem}
Peripatetic Shipping Lines, Inc., is a shipping company that owns \(n\) ships
and provides service to \(n\) ports. Each of its ships has a \emph{schedule}
that says, for each day of the month, which of the ports it's currently
visiting or whether it's out at sea. (You can assume the ``month'' here has
\(m\) days, for some \(m>n\).) Each ship visits each port for exactly one day
during the month. For safety reasons, PSL Inc. has the following strict
requirement:
\smallskip
\emph{($\dagger$) ~ No two ships can be in the same port on the same day.}
\smallskip
The company wants to perform maintenance on all the ships this month, via the
following scheme. They want to \emph{truncate} each ship's schedule: for each
ship \(S_i\), there will be some day when it arrives in its scheduled port and
simply remains there for the rest of the month (for maintenance). This means
that \(S_i\) will not visit the remaining ports on its schedule (if any) that
month, but this is okay. So the \emph{truncation} of \(S_i\)'s schedule will
simply consist of its original schedule up to a certain specified day on which
it is in a port \(P\); the remainder of the truncated schedule simply has it
remain in port \(P\).
Now the company's question to you is the following: Given the schedule for
each ship, find a truncation of each so that condition ($\dagger$) continues
to hold: no two ships are ever in the same port on the same day.
Show that such a set of truncations can always be found, and give an algorithm
to find them.
\paragraph{Example:}
Suppose we have two ships and two ports, and the ``month'' has four days.
Suppose the first ship's schedule is
\begin{quotation}\noindent
\emph{port \(P_1\); at sea; port \(P_2\); at sea}
\end{quotation}
and the second ship's schedule is
\begin{quotation}\noindent
\emph{at sea; port \(P_1\); at sea; port \(P_2\)}
\end{quotation}
Then the (only) way to choose truncations would be to have the first ship
remain in port \(P_2\) starting on day 3, and have the second ship remain in
port \(P_1\) starting on day 2.
\end{problem}
\insolution{
\begin{solution}
We can solve this problem by applying the Gale-Shapley algorithm unmodified,
and simply map each element of the Stable Matching Problem to an element of
PSL, Inc.'s problem. We map the men to ports and the women to ships. Each
man/woman partnership represents a choice of port where a ship stops for
repairs. The men's preferences correspond to the order each ship visits the
corresponding port; \emph{later} visits are ranked higher. Women's
preferences correspond to the order that the corresponding ship visits each
port; \emph{earlier} ports are ranked higher.
Translating from the Stable Matching Problem to PSL, Inc.'s problem, we
arrive at the following definition of \emph{instability}.
\begin{quotation}\noindent
An instability occurs when there are two pairs \((P,S)\) and \((P',S')\)
in the truncated schedule with the property that \(S'\) arrives
\emph{after} \(S\) at \(P\) in the original schedule, and \(S'\) stops at
\(P\) \emph{before} \(P'\).
\end{quotation}
We now establish the following fact about truncated schedules.
\begin{fact}
Any time we violate condition ($\dagger$), there must be an instability in
the truncated schedule.
\end{fact}
\begin{just}
Let us assume that we violate condition ($\dagger$): ships \(S\) and
\(S'\) visit \(P\) at the same day in the truncated schedule. One of the
two ships must arrive first; without loss of generality\footnotemark{} we
consider \(S\) to arrive first. Since \(S\) does not stay until \(S'\)
arrives in the original schedule, it must have stopped at \(P\).
Therefore \((S,P)\) is in the truncated schedule. And, since \(S'\)
reaches \(P\), its truncation must come at some port \(P'\) that it
reaches later. Thus, \((P,S)\) and \((P',S')\) are in the truncated
schedule, \(S'\) arrives after \(S\) at \(P\), and \(S'\) stops at \(P\)
before \(P'\). We have established precisely the conditions of an
instability.
\footnotetext{The phrase ``without loss of generality'', often abbreviated
WLOG, means that although we are not stating all cases, every other case
follows the same reasoning symmetrically. For instance, given two
people \(A\) and \(B\), one of each gender, we may consider without loss
of generality that \(A\) is male and \(B\) is female. Of course it
might be the other way around; in that case we would use the same
reasoning but swap the names \(A\) and \(B\).}
\end{just}
Because the Gale-Shapley algorithm never produces instabilities in its
result, our use of it to solve PSL, Inc.'s problem can never violate
condition ($\dagger$).
\end{solution}
}
\end{document}