You are playing a game where there are 9 boxes laid out in a row, numbered 1 through 9 from left to right. Randomly placed in one of the boxes is a slip of paper that says "GAME OVER". The other eight boxes each contain $1000.
You are to pick the boxes one at a time. If you pick a box with $1000, you keep the money and you must pick another box. If at any point you select the box that says "GAME OVER", the game ends and you leave with the prize money you've accumulated to that point. The only catch is, the host of the game show will tell you which direction the "GAME OVER" box is in, and you must guess your next box in that direction (it's like a guessing game where you have to guess a number from 1 to 9, and after each guess the host tells you "higher" or "lower" until you finally guess the number he is thinking of). However, the goal of this game is not to land on the "GAME OVER" box (since you eventually will), but to maximize the number of guesses you take (and thus your profit) before you land on it.
Question 1: Is there an optimal strategy for this game? If so, what is it and what is your expected profit? If not, why not?
Question 2: What if you were the host, and instead of randomly placing the "GAME OVER" box, you could choose where it went - is there a strategy that would minimize the expected profit of the contestant?
Always placing the note in box 1 or 9 (with 50% probability) is
certainly not a bad strategy. Even if the contestant knows the
host is doing this, he cannot come up with a strategy that is expected
to win more than $4000. So this is a better host strategy than
randomly placing the note in the boxes with a probability of 1/9 per
box, since my counter-strategy for that expects to win $4,888.89.
By contrast, I can win the full $8,000 if I know the host always picks
box 2 or 8. Just start in box 5. If the host says high,
pick 9,1,2,3,4,6,7. If the host says low, pick
1,9,8,7,6,4,3,2. I like this game.
Similarly, I can always win the full $8,000 if I know the host always picks box 3 or 7.
Similarly, I can always win the full $8,000 if I know the host always picks box 4 or 6.
And I can always win the full $8000 if I know the host always picks box
5. There are many ways to do this, such as 1,2,3,4,9,8,7,6.
Or 1,9,2,8,3,7,4,6.
To my way of thinking, these are the hosts' 5 "pure" strategies, and always picking 1 or 9 is clearly the best of them.
There may very well be a mixed strategy which is better. I would
start by identifying the contestant strategies that do best against
each of the host's 5 "pure" strategies, plus the contestant strategy
that does best against a pure random strategy (see my previous two
posts). I would then figure out the game-theoretic optimal host
strategy as if that were the only contestant strategies
available. This seems manageable, but I'm not going to do it.
I suspect the optimal host strategy is a random strategy that
weights 1 and 9 more heavily than other boxes. But I wouldn't be
too surprised if the best host strategy was always picking box 1 or 9.
Edited on May 23, 2006, 3:03 pm
Observation re Question 2
