\documentclass[11pt,fleqn]{article}
\usepackage{latexsym,epsf,epsfig}
\usepackage{amsmath,amsthm}
\begin{document}
\newcommand{\mbf}[1]{\mbox{{\bfseries #1}}}
\newcommand{\N}{\mbf{N}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\section*{CS 70 homework 5 solutions}
Your full name: PUT YOUR NAME HERE
\newline
Your login name: PUT YOUR LOGIN NAME HERE
\newline
Homework 5
\newline
Your section number: PUT YOUR SECTION NUMBER HERE
\newline
Your list of partners: LIST YOUR PARTNERS HERE
\newline
\begin{enumerate}
\item
Consider the problem of admitting $n$ students to $k$ colleges.
The $j$th college can admit up to $n_j$ students.
Each student has an order of preference for the colleges,
and each college has an order of preference for the students.
A {\it stable admission} is an assignment of the students to the colleges
where there is no ``rogue couple'', that is, no situation where
there is a student $A$ who is not admitted to college $a$,
but who prefers $a$ to his/her college and is preferred by $a$
to at least one of $a$'s students.
\begin{enumerate}
\item Describe how to use the Traditional Matching Algorithm as a subroutine to
produce a stable admission. (That is, you shouldn't change the TMA code.)
YOUR ANSWER GOES HERE.
\item Also justify why your procedure produces
a stable admission.
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
We know that there can be no more than $n^2$ stages of the TMA
algorithm, because at least one girl is deleted from at least one list at
each stage. Construct an instance with $n$ boys and $n$ girls
so that {\it at least} $c\cdot n^2$ stages are required for some
constant $c > 0$, and justify your runtime bound.
We are looking for a {\em general pattern} here, one that
results in $c\cdot n^2$ stages for all $n$. $c$ might be less than 1,
say 1/10 or 1/100.
YOUR ANSWER GOES HERE.
\item
A person $x$ is said to {\it prefer} a matching $M$ to a matching $M'$
if $x$ strictly prefers her/his partner in $M$ to her/his partner in $M'$.
Given two stable matchings $M$ and $M'$, a person may prefer one to the other
or be indifferent if she/he is matched with the same person in both.
Suppose now that $M$ and $M'$ are stable matchings,
and suppose that $m$ and $w$ are partners in $M$ but not in $M'$.
Prove that one of $m$ and $w$ prefers $M$ to $M'$,
and the other prefers $M'$ to $M$.
YOUR ANSWER GOES HERE.
\item
Consider the following variation on the stable marriage problem:
In Hawkinsville this year, we have $n$ eligible boys and girls.
Everyone knows the preferences of all the boys, but the girls
have managed to keep their preferences totally secret.
Tomorrow night, the girls will throw a secret meeting (no boys allowed!),
privately share their (true) preferences, and collude to come up with a set of
fake preferences that they will announce to the village elders.
As a twist, each girl may declare some boys to be unacceptable (she'd
rather be single than marry any of them).
Next week, the village elders will run the traditional marriage algorithm on
the boys' (true) preferences along with the girls' announced (and
totally fake) preferences.
The output of the traditional marriage algorithm will be used
to marry off all the eligible youngsters in Hawkinsville.
Show that the girls can conspire to choose fake preferences
so that when the wedding bells ring next week,
we'll end up with a girl-optimal pairing.
(By ``optimal,'' we mean optimal with respect to everyone's true preferences.)
YOUR ANSWER GOES HERE.
\item
Consider this protocol for three-party cake cutting:
\begin{tabbing}
\quad\=1. \=Alice cuts the cake into three equal chunks (equal by her measure).\\
\>2. \>Bob cuts each of these three chunks in half (so that both
halves of each chunk are equal by his measure).\\
\>3. \>Among these 6 pieces, Carol chooses the two best pieces (by her measure).\\
\>4. \>Among the 4 remaining pieces, Alice chooses the best two (by her measure).\\
\>5. \>Bob gets the last 2 pieces.
\end{tabbing}
Justify each of your answers below briefly.
\begin{enumerate}
\item Is this protocol fair for Alice? for Bob? for Carol?
YOUR ANSWER GOES HERE.
\item Is this protocol envy-free for Alice? for Bob? for Carol?
Recall that a protocol is envy-free for X if it has the following property:
if X follows the protocol, then X gets at least as much (by her measure)
as anyone else gets, no matter how the other parties behave.
YOUR ANSWER GOES HERE.
\end{enumerate}
\end{enumerate}
\end{document}