[foldr]

I don't really get it either, but I think the idea is that you're supposed to somehow optimize on the assumption that your opponent is equally likely to be using any strategy. (To my mind this makes the problem very confusing because it's such an unrealistic assumption.) If you assume that the only possible strategies are "rethrow if my first throw is <= x", then you can define a function f(x,y) giving the EV where x is the threshold for your rethrow and y is the threshold for your opponent's. I guess you then integrate with respect to y (to get the EV for any given x assuming a uniform distribution for the opponent's choice of y) and then differentiate the result with respect to x to find the maximum? If the solution is along those lines that would explain the problem's supposed accessibility to good high school students.

[murbard2]

The reason maximizing EV isn't the answer is that you care about having a larger number than your opponent, not about having the largest number possible.

Imagine we play a die game where whoever rolls the largest number wins. Which die would you rather play with?

1-1-1-1-1-10^250 or 2-2-2-2-2-2

The first die has an EV of about 1.67e249, the second die an EV of 2. Yet, the second die will win 5 out of 6 games against the other one.

To solve the problem, you must find the Nash equilibrium of the game. That is, you must find a strategy which the opponent cannot exploit, no matter what he does.

[murbard2]

And no, you don't assume that every strategy is equally likely. You assume that the opponent plays optimally with full knowledge of your own strategy, which means you're looking for a Nash equilibrium http://en.wikipedia.org/wiki/Nash_equilibrium

[foldr]

That's fine if you already know game theory, but then the problem is not quite as accessible as you made out. You can't expect someone to just invent the concept of a Nash Equilibrium on the spot from the words "best strategy". (Although I understand that you may expect your interviewees to already be familiar with game theory.)

[murbard2]

In this case, the candidate's thesis work explicitly dealt with game theory. In addition, this doesn't require much knowledge of game theory... if you think about the problem for a bit, you can re-derive the concept fairly easily.

Nash's brilliance was in proving that under reasonable conditions, a mixed equilibrium always exists, which is far less obvious.

[foldr]

The issue isn't the difficulty of the concept but the ambiguity of "best strategy".

[murbard2]

Fine, best strategy given a perfectly rational opponent. There, ambiguity removed.

[foldr]

Well not quite, you also need to specify that the opponent assumes that you are perfectly rational, and that he assumes that you assume that he is, and that he assumes that you assume that he assumes that you are, and so on. A perfectly rational opponent would not assume that you are perfectly rational in the absence of any relevant information. Rather, he would assume that his opponent was equally likely to be using any strategy.

[megrimlock]

Makes sense. I didn't realize the problem description was for a game that would be played repeatedly with the same opponent -- i.e. one where you can gather information. If we were doing this in person instead of on a internet forum and async post/response we'd probably iron that out quickly. Thanks for elaborating.