CS535 HW5

Problem 1 §

Proof by induction

Problem 2 §

The following case has all $n$ women settle for their last proposer: $m_1$ prefers $w_1$ most, $m_2$ prefers $w_2$ most, etc. s.t. $m_i$ prefers $w_i$ the most. Then every woman settles for their last proposer.

Problem 3 §

Subproblem 1 §

Where $|H|>|S|$, a matching $\pi$ is stable if :

1. there exists no unmatched pair $(s\in S,h\in H)$ such that both would prefer to be with each other than their current match in $\pi$
2. there exists no hospital slot that would prefer an unmatched student $s$ rather than its current match.

Subproblem 2 §

We can extend this problem to create $|h|-|s|$ new dummy hospital slots in set $D$, and add to every student $s$’s preference list:

$$\underset{\text{ preexisting preference }}{\underbrace{\cdots }}{\succ }_s\underset{\in D\text{, in random order}}{\underbrace{h_1{\succ }_s{h}_2\succ \cdots \succ h_{|D|}}}$$

And also for every $h\in D$ construct a randomly ordered preference set of all students as well, and then match students $S$ with $H^{\prime }=H\cup D$. By the same proof that we discussed during class (Gale-Shapely), this algorithm always has a stable matching including the dummy hospitals. When we remove the dummy hospitals, this will not create an unstable matching. This is because in every student’s preference ordering the dummy hospitals are lower than any real hospital in all student’s preferences, therefore no real-matched pair $(s,t\in H\setminus D)$ will be unstable.

Problem 4 §

Subproblem 1 §

We run the Gale-Shapely algorithm on a partition with preferences by breaking ties arbitrarily. In this situation it is trivial to see that a variation on the lemma from class holds: Lemma. If a woman $w$ rejects man $m$, in all future scenarioes, $w$ is engaged to man $m^{\prime }$ who is not less preferred than $m$ (i.e. $w$ may be indifferent between $m,m^{\prime }$). Then, proof by contradiction. Suppose the Gale-Shapely algorithm terminates in a match with a strongly unstable match $(m_1,w_2),(m_2,w_1)$ but $w_1{\succ }_{m_1}{w}_2$ and $m_1{\succ }_{w_1}{m}_2$. Then, since $m_1$ proposes in order of his preferance he must have proposed and gotten rejected by $w_1$ before proposing and being accepted by $w_2$. By the lemma, since $w_1$ rejected $m_1$ she must have the preference $m_2{⪰}_{w_1}{m}_1$, but this is a contradiction. ■

Subproblem 2 §

Counterexample. Suppose matching $m_1,m_2$ and $w_1,w_2$, whose preferences are such that:

• $m_1$: $w_1\succ w_2$
• $m_2$: $w_1\sim w_2$
• $w_1$: $m_2\succ m_1$
• $w_2$: $m_2\succ m_1$ Consider matching $(m_1,w_1),(m_2,w_2)$. This weakly unstable because $(m_2,w_1)$ is a better match since $m_2$ is indifferent and $w_1$ prefers $m_2$. The only other possible matching $(m_1,w_2),(m_2,w_1)$ is also unstable because $w_2$ will prefer $m_2$ and $m_2$ is indifferent about this.

Problem 4 §

Subproblem 1 §

Consider an algorithm which, on timestep $i$, moves distance $(-2{)}^{i-1}$; in other words, moves right 1 step, then left 2 steps, then right 4 steps, then left 8 steps, etc. Suppose also that the car is located at point $k\in \mathbb{R}$. We can then say:

• ${\text{move}}_i:=(-2{)}^{i-1}$, the movement at time $i$
• ${\text{travel}}_i:=2^{i-1}$, the total travel distance after time $i$ And position (=displacement) after time $i$:

\frac{1}{3}(1-2^{i}) & \text{if i is even} \\ \frac{1}{3}(1+2^{i}) & \text{if i is odd} \end{cases}

We consider both cases:

1. If $k>0$, the worst case is when on timestep $i$ we have searched until point $k-1$ and then turn left on timestep $i+1$, then meet $k-1$ before timestep $i+2$. In this case:
   • Since we move right on the first step, and $k$ is set as one step to the right of ${\text{pos}}_i$ $i$ must be odd
   • $k={\text{pos}}_i+1$, which means $i={\log }_2(3(k-1)-1)$
2. If $k<0$, the worst case is symmetric:
   • $i$ must be even
   • $k={\text{pos}}_i-1$, which means $i={\log }_2(1-3(k+1))$ In both cases the total travel distance is

$$\begin{array}{rl}& ={\text{travel}}_{i+1}+|{\text{pos}}_{i+1}|+|k|\\ & =\{\begin{array}{ll}-10+8k& \text{if }k>0,i\text{ is even}\\ -\frac{16}{3}-8k& \text{if }k<0,i\text{ is odd}\end{array}\end{array}$$

Since the optimal algorithm which knows $k$ will always have a cost $|k|$:

$$\begin{array}{rlr}\frac{-10+8k}{k}& <8& k>0\\ \frac{-16/8-8k}{-k}& <8& k<0\end{array}$$

This is a $9$-competitive algorithm. Computation:

Subproblem 2 §

Consider an algorithm which with $\frac{1}{2}$ chance chooses the first step to be positive, and with $\frac{1}{2}$ to be negative. After the decision the algorithm deterministically behaves like in subproblem 1. We consider the case when $k>0$ (the analysis when $k<0$ is symmetric): When $|{\text{pos}}_i|<k<|{\text{pos}}_{i+1}|$, we have two cases for right-first or left-first:

1. Moved right on the $i$-th step: the total travel distance is: ${\text{travel}}_{i+1}+|{\text{pos}}_{i+1}|+|k|$
2. Moved left on the $i$-th step: the total travel distance is ${\text{travel}}_i+|{\text{pos}}_i|+|k|$ Since each case have $\frac{1}{2}$ chance, the expected travel distance is:

$$\begin{array}{rl}\mathbb{E}[\text{total travel}]& =\frac{1}{2}({\text{travel}}_{i+1}+|{\text{pos}}_{i+1}|+|k|)+\frac{1}{2}({\text{travel}}_i+|{\text{pos}}_i|+|k|)\end{array}$$

To bound this competitiveness we recall $|{\text{pos}}_i|<k<|{\text{pos}}_{i+1}|$. We try to find $k$ which maximizes the competitive ratio. Since $i\ge 1$:

\frac{d}{dk}\frac{\mathbb{E}[\text{total travel}]}{|k|}=\begin{cases} \frac{8-11\cdot 2^i}{6 k^2} \text{if $i$ is even} \\ \frac{4-11\cdot 2^i}{6 k^2} \text{if $i$ is odd} \end{cases} <0 $$(computation below) Thus regardless of if $k$ is positive or negative, the worst case scenario is when $k$ is smaller, or $k=|\text{pos}_{i}|$. Then: $$\begin{align} \frac{\mathbb{E}[\text{total travel}]}{|k|}&=\frac{\mathbb{E}[\text{total travel}]}{|\text{pos}_{i}|} \\ &=\frac{1}{2|\text{pos}_{i}|}(\text{travel}_{i+1}+|\text{pos}_{i+1}|+|\text{pos}_{i}|)+\frac{1}{2|\text{pos}_{i}|}(\text{travel}_{i}+2|\text{pos}_{i}|) \\ &= \begin{cases} \frac{13\cdot 2^i-10}{2 \left(2^i-1\right)}& \text{if $i$ is even}\\ \frac{13\cdot 2^i-2}{2 \left(2^i+1\right)} & \text{if $i$ is odd} \end{cases}\\ \lim_{ i \to \infty } \frac{\mathbb{E}[\text{total travel}]}{|k|}&\leq 6.5<7 \end{align}

Therefore, the algorithm is 7-competitive. ■

Computation of derivative (divided between $i$ even or odd): Computation of competitive ratio (divided between $i$ even or odd)