Problem 1

Proof by induction

Problem 2

The following case has all women settle for their last proposer: prefers most, prefers most, etc. s.t. prefers the most. Then every woman settles for their last proposer.

Problem 3

Subproblem 1

Where , a matching is stable if :

  1. there exists no unmatched pair such that both would prefer to be with each other than their current match in
  2. there exists no hospital slot that would prefer an unmatched student rather than its current match.

Subproblem 2

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

And also for every construct a randomly ordered preference set of all students as well, and then match students with . 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 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 rejects man , in all future scenarioes, is engaged to man who is not less preferred than (i.e. may be indifferent between ). Then, proof by contradiction. Suppose the Gale-Shapely algorithm terminates in a match with a strongly unstable match but and . Then, since proposes in order of his preferance he must have proposed and gotten rejected by before proposing and being accepted by . By the lemma, since rejected she must have the preference , but this is a contradiction.

Subproblem 2

Counterexample. Suppose matching and , whose preferences are such that:

  • :
  • :
  • :
  • : Consider matching . This weakly unstable because is a better match since is indifferent and prefers . The only other possible matching is also unstable because will prefer and is indifferent about this.

Problem 4

Subproblem 1

Consider an algorithm which, on timestep , moves distance ; 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 . We can then say:

  • , the movement at time
  • , the total travel distance after time And position (=displacement) after time :
\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 , the worst case is when on timestep we have searched until point and then turn left on timestep , then meet before timestep . In this case:
    • Since we move right on the first step, and is set as one step to the right of must be odd
    • , which means
  2. If , the worst case is symmetric:
    • must be even
    • , which means In both cases the total travel distance is

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

This is a -competitive algorithm. Computation:

Subproblem 2

Consider an algorithm which with chance chooses the first step to be positive, and with to be negative. After the decision the algorithm deterministically behaves like in subproblem 1. We consider the case when (the analysis when is symmetric): When , we have two cases for right-first or left-first:

  1. Moved right on the -th step: the total travel distance is:
  2. Moved left on the -th step: the total travel distance is Since each case have chance, the expected travel distance is:

To bound this competitiveness we recall . We try to find which maximizes the competitive ratio. Since :

\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 even or odd): Computation of competitive ratio (divided between even or odd)