** Next:** A Numeric Example
** Up:** Example: The Recruiting Problem
** Previous:** The Solution

###

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
such that
then
we get
.
That is, if there exists a time
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, ,
does exist.

Let
,
then according to equation
.
Performing backword induction steps, and using equations and we show that for
the inequality remains true:

We now show that for
and
*s*=*MaxSoFar*, it is preferred to
*QuitAndHire*.

Let ,
then according to the first half of the proof,

and,

We conclude this proof by showing that such a
exists, that is, for
there exists
that meets the above requiremints. Let us assume
we get:

which is a circular inequality, and thus leads to cnotradiction.

Note that for
we always get
:

||

and for

.

We therefore choose *Continue* if
and
*QuitAndHire* otherwise.

** Next:** A Numeric Example
** Up:** Example: The Recruiting Problem
** Previous:** The Solution
*Yishay Mansour*

*1999-11-18*