Problem Set 7
[Revision 0.1: 23 October 7:57pm]
Collaboration Policy - Read Carefully
The collaboration policy is identical to that for PS6: you should work in groups of one to four students of your choice with no restrictions, and follow the rest of the collaboration policy from PS3.
Preparation
This problem set focuses on Stable Matching — Section 6.4 of the MCS book, and Class 15.
Directions
Solve as many of the 7 problems as you can. Questions 1 and 2 check your understanding of stable matching, and the remaining questions build up to completing the proof that the Gale-Shapley Algorithm always finds a stable matching. For maximum credit, your answers should be correct, clear, well-written, and convincing.
Stable Matching
Traumatized by his failure to reach Eve in Problem Set 6, Wall-E has decided to join RoboMatch.com, the Stable Macthing Service for Loney Robots. Robots do not have limitations on their potential matches, but RoboMatch is concerned that it may not be possible to find a stable matching if the robots are allowed to prefer any other robot, RoboMatch divides robots into two sets based on whether or not they are in Disney/Pixar movies, and requires every member to provide a full preference ranking of all the robots in the other set.
The rankings are (from most preferred to least preferred):
\begin{center} \begin{tabular}{lcl} \multicolumn{1}{c}{{\bf Set A:} Disney/Pixar Robots} & $\qquad\qquad$ & \multicolumn{1}{c}{{\bf Set B:} Real Robots} \ \hline Luxo: AIBO, Big Dog, Junior & & AIBO: Wall-E, Luxo, R2-D2 \
R2-D2: AIBO, Junior, Big Dog & & Big Dog: R2-D2, Luxo, Wall-E \
Wall-E: Big Dog, Junior, AIBO & &
Junior: Wall-E, R2-D2, Luxo
\end{tabular}
\end{center}
Show that there are stable matchings where Wall-E is paired with Junior and where Wall-E is paired with Big Dog. (Note: feel free to use the provided Gale-Shapley program code.
Show that there cannot be any stable matching where Wall-E is paired with AIBO.
Gale-Shapley Algorithm
\vspace{-1ex}
In Class 15, we developed a
state machine model for the Gale-Shapley stable matching algorithm:
\vspace{-2ex}
\begin{equation}
\begin{split}
S = {(pa&irings, \text{\em proposals}) \, | \
& \text{\em pairings} = { (a, b) \, | \, a \in A, b \in B, \text{no duplicate occurences of}\ a\ \text{or}\ b\ \text{in}\ \text{\em pairings} },
& \text{\em proposals} = (r_1, r_2, \cdots, r_n), 0 \le r_i \le n }
G = {(\text{\em pa}&\text{\em irings}, \text{\em proposals} = (r_1, r_2, \cdots, r_n)) \rightarrow (\text{\em pairings}‘, \text{\em proposals}‘) \, |
& i \in { 1, \cdots, n }, r_i < n
& \forall b \in B \ldotp (a_i, b) \notin \text{\em pairings} \
& b_x ::= \text{the}\ r_i\text{-ranked choice for }a_i
& \text{\em proposals}’ = (r_1, \cdots, r_i + 1, \cdots, r_n)
& \text{\em pairings}’ = \begin{cases}
\text{\em pairings} \cup { (a_i, b_x)} & \forall a_z \in A \ldotp (a_z, b_x) \notin \text{\em pairings}\ \text{(Case 1)}
\text{\em pairings} \cup { (a_i, b_x)} - { (a_z, b_x) } & \exists a_z \in A \ldotp (a_z, b_x) \in \text{\em pairings} \wedge az \prec{b_x} a_i\ \text{(Case 2)}
\text{\em pairings} & \text{otherwise (Case 3)}
\end{cases} \
& }
q_0 = (\text{\em pa}&\text{\em irings} = { }, \text{\em proposals} = (0, 0, \ldots, 0))
\end{split}
\end{equation}
Explain (in simple English) when (Case 3) in the definition of $G$ occurs.
Prove that the state machine always terminates (we did this in Class 15, but didn’t write out a full proof). (Hint: Explain why we need the $r_i < n$ constraint for $G$.)
Prove that the state machine always terminates in a state where $\text{\em pairings}$ includes a match for each element of $B$. (Hint: prove by contradiction by showing that if the machine is in a reachable state where some element of $B$ is unmatched, it must have a transition.)
Define, $\text{\em Prefs}x(n)$ as the set of the top ranked $n$ preferences of $x$. So, $\text{\em Prefs}{ai}(0) = { }$, and $\text{\em Prefs}{a_i}(1) = { b_x }$ where $b_x$ is $ai$’s top choice, $\text{\em Prefs}{a_i}(2) = { b_x, b_y }$ where $b_y$ is $ai$’s second choice, and $\text{\em Prefs}{a_i}(n) = B$.
($\star$) Prove that the property $P$ defined below is a preserved invariant for the state machine. The value of $\text{\em proposals}[i]$ is the count in the sequences $\text{\em proposals}$ that corresponds to the number of \text{\em proposals} made by $a_i$. \begin{equation} \begin{split} P(q = (\text{\em pai}&\text{\em rings}, \text{\em proposals})) ::=
& (a_i, b_j) \in \text{\em pairings} \implies \ & \qquad \qquad \forall bx \in \text{\em Prefs}{a_i}(\text{\em proposals}[i]) \wedge bj \prec{a_i} b_x \, \ldotp \, \exists a_y \in A - { a_i } \ldotp (ai \prec{b_x} a_y)
\end{split} % \wedge bx \in \text{\em Prefs}{a_y}(\text{\em proposals}[y])
\end{equation}That is, if $(a_i, b_j)$ is in $\text{\em pairings}$, then every match $a_i$ prefers to $b_j$ prefers someone else over $a_i$.
($\star\star$) Prove the $\text{\em pairings}$ for the terminating state are a stable matching (as defined in Class 15). (You may assume all of the properties in questions 4–6 in your proof, even if you were not able to prove them.) (Note: you may first want to state the definition of a stable matching in a different way, and may also find it helpful to strengthen the preserved invariant property from question 6.)