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:

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