\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}