maximum value

A personnel manager is to interview four can- didates for a job. These are ranked 1, 2, 3, and 4 in order of preference and will be interviewed in random order. However, at the conclusion of each interview, the manager will know only how the current candidate compares to those previously in- terviewed. For example, the interview order 3, 4, 1, 2 generates no information after the rst interview, shows that the second candidate is worse than the rst, and that the third is better than the rst two. However, the order 3, 4, 2, 1 would generate the same information after each of the rst three inter- views. The manager wants to hire the best candidate but must make an irrevocable hire/no hire decision after each interview. Consider the following strat- egy: Automatically reject the rst s candidates and then hire the rst subsequent candidate who is best among those already interviewed (if no such candi- date appears, the last one interviewed is hired).

For example, with s = 2, the order 3, 4, 1, 2 would result in the best being hired, whereas the order 3, 1, 2, 4 would not. Of the four possible s
values (0, 1, 2, and 3), which one maximizes P(best is hired)? (Hint: Write out the 24 equally likely interview orderings: s = 0 means that the rst candidate is automatically hired.)