How to win a game like this?

My teacher started a game like this "everyone hands in a number in [0,99] in the next class, and the winner is the one with the number that is closest to half of the average of all submitted numbers".

If all my classmates are idiots picking number uniform randomly, then my winning number is 25. If they all think in this way, then my winning number is 13. Clearly not all of them are idiots, so what number I should pick to win the game?

-
Have you read this? –  mrf Mar 9 '13 at 22:41
The statement: "If all my classmates are idiots..." sounds you are smart. LOL (It's just a joke, no hurt feeling) –  Tunk-Fey May 20 '14 at 6:31

If all classmates are not idiots, then by repeating the same logic, they would all reason to pick 13, and hence pick 6. But then they would all reason to pick 6, and hence pick 3... and so on, leaving 0 as the winning choice.

But probably, some of your classmates are idiots, and will attempt this line of reasoning to their maximal capabilities, give up, and pick a number like 9, so depending on the percentage of idiots and the size of the class, the actual optimal number might be something like 2 or 3.

However, some members of your class might be exceptional idiots and will pick a number like 85. These people will skew the average upward, meaning that the idiot that picked 9 will win.

-
+1 for exceptional idiots! –  Brian M. Scott Mar 9 '13 at 22:57
That the classmates are not idiots is not the same thing as this being common knowledge. –  Michael Greinecker Mar 10 '13 at 11:50
And some will be non-idiots, but consider that the prize is not worth the mental effort of trying to win it, and deliberately play 85 for the lulz. (That is perfectly rational, provided that you consider the lulz to have nonzero utility for you). –  Henning Makholm Mar 10 '13 at 14:09

Assuming that all of your classmates are perfect logicians: since the maximal number that can be chosen is 99, make it 100, then half the average is at most 50, thus nobody would choose more than 50. But this means that the average can be at most 25, so nobody would choose more than 25. And so on. So the only logical choice is to choose 0. Furthermore notice that with this technique you can get everybody to win with perfect score (if everybody chooses 0).

-
It is not enough that they are all perfect logicians. This has to be common knowledge. –  Michael Greinecker Mar 10 '13 at 11:49
@MichaelGreinecker: Do you mean the fact that everybody is perfectly rational? Yes, of course. But if the teacher is a maths teacher it could be a good idea to choose 0 to kinda impress him ;) –  Daniel Robert-Nicoud Mar 10 '13 at 22:52
You need everyne to be perfectly, rational, everyone to know that everyone is perfectly rational, everyone to know that everyone knows... Perfect rationality alone oes not imply that all players will play $0$. –  Michael Greinecker Mar 11 '13 at 7:37

It's a classic example of basic game theory in which the best strategy is 0... But they made studies in which, by average, you should go to the third "iteration" of that conclusion chain, so, if you have to pick in [0,99], then the first is 50, then 25, then 13... the average result was that in the first play, you should pick 13, and with the same people after three rounds the winning number was already 0. I'm sorry I can't reference those studies, I just remember seeing them, doing with college classes. But basically, the correct answer is that the best strategy is 0.

-
There is no best strategy. –  Michael Greinecker Mar 10 '13 at 11:48
@MichaelGreinecker I honestly haven't studied game theory very formally... Then the 0 is the Nash equilibrium of the game, isn't it? The state in which no player will want to change strategy? –  MyUserIsThis Mar 10 '13 at 12:23
Yes, the unique Nash equilibrium has everyone playing 0. But a Nash equilibrium is defined so that nobody has an incentive to deviate when knowing wat the others play- it doesn't tell you much on what happens when you do not know how others play. In this game, one can use rationalizability, the outcome of everyone being rational, everyone knowing that everyone is rational, everyone knowing that everyone knows everyone is rational, and so on. This is compatible only with everyone playing 0 here, but the assumption is of course extremely strong. –  Michael Greinecker Mar 10 '13 at 12:29
@Michael: I'm not sure everyone playing 0 is an equilibrium. If everyone is already playing 0, I could collude with my neighbor: He plays $1$, I play $1/2n$ and win, then I split the prize with my accomplice. That's better than splitting the prize with the entire class (or drawing lots), which I suppose would be the result if everyone plays 0. –  Henning Makholm Mar 10 '13 at 14:06
@HenningMakholm If there is the possibility to make side arrangements, it should be included in the structure of the game. –  Michael Greinecker Mar 10 '13 at 14:37

The standard notion of rationality used in game theory is maximizing expected payoff given some subjective belief (a probability distribution) over what the other players do. Let's also assume everyone cares only about winning.

So what is the largest number a rational player could play in this game? If everyone else plays $99$, one could win by playing $98$. If you think they play something smaller, you would want to play an even smaller number. So a rational player will never play $99$. Now, if you are sure everyone else is rational, you know that nobody else will play $99$ and for the same reason as before, $98$ is not a best response to any behavior compatible with the assumption that everyone is rational. Now if you think that everyone thinks that everyone is rational, you can rule out $97$. Continuing this way, you can rule out everyone playing anything but $0$ and this is the only outcome compatible with common knowledge of rationality.

Note that the assumption that everyone knows that everyone knows that... everyone is rational is more and more demanding and probably unrealistic, the longer the chain of reasoning goes. So there is very little one can actually say about how to play the game.

Something that does help a bit is weak dominance. Even though playing $98$ is compatible with rationality, note that whenever $98$ wins, $97$ would win too and there are imaginable cases (with many players) where $97$ wins but $98$ does not. by a similar argument, you might not want to play anything larger than $66$.

-
Nice exposition. –  Metta World Peace Mar 18 '13 at 9:53