Optimality Proof

We will now show that the described policy agrees with the optimality equations.
We start by showing that if there is a time $\tau$ such that $\frac{\tau}{N}<U_\tau^*(MaxSoFar)$ then $\forall t, t<\tau$ we get $\frac{t}{N}<U_t^*(MaxSoFar)$. That is, if there exists a time $t=\tau$ in which it is preferred to Continue, then for each earlier time it is also preferred to continue. Later on, we will show that such a time, $\tau$, does exist.
Let $\frac{t}{N}<U_t^*(MaxSoFar)$, then according to equation $U_\tau^*(MaxSoFar)=U_\tau^*(Other)$. Performing backword induction steps, and using equations and we show that for $t<\tau$ the inequality remains true:
$U_{\tau-1}^*(Other)=\frac{1}{\tau}U_\tau^*(MaxSoFar)+\frac{\tau-1}{\tau}U_\tau^*(Other)=U_\tau^*(Other)>\frac{\tau}{N}$
$U_{\tau-1}^*(MaxSoFar)=\max\{\frac{\tau-1}{N}, U_{\tau-1}^*(Other)\}>\frac{\tau}{N}>\frac{\tau-1}{N}$
We now show that for $t>\tau$ and s=MaxSoFar, it is preferred to QuitAndHire.
Let $t>\tau$, then according to the first half of the proof,
$U_t^*(MaxSoFar)=\frac{t}{N}$
and,

$$\begin{eqnarray*}U_t^*(Other) & = & \frac{1}{t+1}U_{t+1}^*(MaxSoFar)+\frac{t}{t+... ...frac{1}{N}\sum_{ i=0}^{ N-t}\frac{t}{t+i}\sim\ln(\frac{N}{t})\\ \end{eqnarray*}$$

We conclude this proof by showing that such a $\tau$ exists, that is, for $N\geq2$ there exists $\tau\geq1$ that meets the above requiremints. Let us assume $\tau=0$ we get:
$U_1^*(Other)=\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N}>\frac{1}{2} \geq \frac{1}{N}=U_1^*(MaxSoFar)\geq U_1^*(Other)$
which is a circular inequality, and thus leads to cnotradiction.
Note that for $N\geq2$ we always get $\tau\geq1$:
$U_1^*(Other) = ... = U_{\tau}^*(Other)$
||
$U_1^*(MaxSoFar) = ... = U_{\tau}^*(MaxSoFar)$
and for $t>\tau$
$U_t^*(MaxSoFar)=\frac{t}{N}$
$U_t^*(Other)=\frac{t}{N}(\frac{1}{t}+\frac{1}{t+1}+...+\frac{1}{N-1})$.
We therefore choose Continue if $\frac{1}{t}+...+\frac{1}{N-1}>1$ and QuitAndHire otherwise.