# Newspaper competition

A newspaper launches a competition. It said that readers should submit one number between 1 and 1000. A £2000 prize would be awarded to the person that got the closest to 2/3 of the mean of all the entries.

What would a smart entry be? What is the underlying principle behind this type of question. I know it involves game theory but I do not fully understand this type of problem yet. Can anyone draw the game theory tables involved / explain the Nash Equilibria?

-
By the way, is this homework? Judging from your other question I'm guessing you're just looking through a book of puzzles or something, but it's nice to be sure. – Qiaochu Yuan Dec 3 '10 at 0:18

The only Nash equilibrium is that everybody submits $1$. To see this, consider any other set of strategies for all the players. Suppose each player $i, 1 \le i \le n$ submits numbers with an expected value of $p_i$ and that at least one of the $p_i$ is greater than $1$. Then the expected value of the mean of the entries is $\frac{p_1 + ... + p_n}{n}$, and there must be at least one player $j$ for which this mean is less than or equal to their number. But then the expected value of $\frac{2}{3}$ of the mean must be strictly less than $p_j$, so player $j$ has an incentive to switch to a lower number.

This is a funny example. Although the Nash equilibrium suggests that playing $1$ should be an optimal strategy, in practice you will always lose when you do this. The issue, I think, is that it only makes sense to adopt the Nash equilibrium strategy if you expect everybody to be playing optimally, but in practice most people will not think this game through enough to actually find the Nash equilibrium strategy. I've played this game a few times, and what seems to be the case in practice is that to most players you can associate a number $n$ such that the number they pick is $\left( \frac{2}{3} \right)^n$ times the maximum. I like to think of $n$ as being a very rough measure of how far the players think ahead, since one can think of $n$ as being the number of times they recurse through the following argument:

• Since the maximum you can play is $1000$, the maximum the average could be is $\frac{2}{3} \cdot 1000$, so I should never guess more than that.
• But since nobody should guess more than $\frac{2}{3} \cdot 1000$, the maximum the average could be is $\left( \frac{2}{3} \right)^2 1000$, so I should never guess more than that.
• But...

and so forth. If the people you're playing with are smart enough, $n$ will actually measure something much more complicated: each player will be trying to guess how far everyone else will think ahead, and then guessing how far everyone else will guess how far everyone else thinks ahead, and then... this phenomenon, in my opinion, is much more interesting than Nash equilibria; I think it is related to the idea of common knowledge.

(The last time I played this game, the possible numbers were $0$ through $100$. I and one other person submitted $100$ just to throw off the results. The actual average ended up being something like $19$. So here $n \approx 9.7$.)

Finally, here's a cute observation. In general the existence of Nash equilibria can be proven using the Brouwer fixed point theorem. The second argument I gave above establishes the existence (and uniqueness) of the Nash equilibrium using essentially the Banach fixed point theorem.

-
 Also, I think there was a dinosaur comics about this. Anyone have the link? – Qiaochu Yuan Dec 3 '10 at 0:23 Hi, yes they are past interview questions – Ian Messiter Dec 3 '10 at 1:12 Nash equilibrium is the weakest sort of equilibrium (IIRC). Its main selling point is that it always exists, but for dynamic sorts of games I don't think things have to converge to a Nash equilibrium. A much stronger notion is that of a "dominant strategy", which is when you have a best choice regardless of what the other players choose. – Aaron Mazel-Gee Dec 3 '10 at 7:54

When solving problems like this the first thing to do is (almost) always to try and reduce the problem to a simpler problem; in this case, for example, pretending the number of allowed numbers is 10, and not 1000, is a good first thing to do.

You may also simplify the problem by allowing everyone to know the current mean value. That way you'll see that everybody has an incentive to submit lower and lower numbers - resulting in Qiaochu's answer.

(as a "by the way", I'll recommend G. Polya's book "How to solve it", which talks about general problem solving techniques.)

EDIT: This problem reminds me of a "paradox" I read about yesterday: "A prisoner is awating death sentence, and is told he will be executed withing this week (it's Monday now), but on a day he's not expecting it. The prisoner reasons that then he can't be executed on Sunday (because if he lives then, that must be the day), and the same reasoning tells us that he will not be executed on Saturday either, and so on. The prisoner concludes that he wont be executed after all. (without expecting it, he is executed on Monday)"

-
 Yes, the unexpected hanging paradox (en.wikipedia.org/wiki/Unexpected_hanging_paradox) has a sort of similar flavor. – Qiaochu Yuan Dec 3 '10 at 0:30