Today’s post is something a little mathier than the linux stuff I wrote about during the past few days. A p-beauty contest is a game (in the real and mathematical sense of the word) in which n players must simultaneously and secretly guess an integer between 0 and m, inclusive. The judge then computes the average x of all the guesses. The winners are those players who guessed the integer closest to p x of the average, where 0 < p < 1.

Let's see an example with real numbers before we go on. Let's say that p=0.5 and we have n=20 players choosing integers between 0 and m=100, inclusive. Suppose all the players choose at random; the average is x=50. Then p x = 0.5 \cdot 50 = 25. The winners are all those players who chose 25 as their guess. If nobody chose 25 exactly, then the winners are those that chose 24 or 26 (and so on).

The reason this is called a "beauty contest" is because it is very closely related to a game called a "Keynesian beauty contest" (after John Maynard Keynes, the famous economist who first described it). In a Keynesian beauty contest, a newspaper publishes pictures of beautiful women. The readers are then told to vote on which one is the most beautiful. The woman who gets the most votes wins a prize, and the readers who voted for that woman also win a small prize.

The implication is obvious; you are not voting for the most beautiful woman, but for the woman whom you think will be voted most beautiful. But if everyone figures this out, then you’re really voting on the woman whom you think everyone else will think will be voted most beautiful. But if everyone figures this out too…

The p-beauty contest is the same idea. Let’s see how it works in our previous example. Bob is playing the game, and the judge says “Go!” and everyone begins writing down their answers. Bob looks around and sees Alice, who appears to be counting the number of polka dots on her shirt as a method for coming up with her guess. “Oh ho, you rube!”, thinks Bob. “If everyone is just like Alice and picks their number randomly, the average will be 50. 0.50 times 50 is 25 and so if I guess 25 I’ll win!” Bob writes down 25 and smirks.

Carol is sitting next to Bob. She sees the smirk on his face and thinks “Hmm, you know, I bet Bob thinks he’s really clever. I bet he figured out that if everyone guesses randomly, the winning guess will be that closest to 25. But I don’t think Bob is all that smart. In fact, I think that everyone is that smart, and they’ll all guess 25.” She bites the eraser on her pencil and thinks a bit more. “If everybody guesses 25 then the average will be, well, 25. So then 0.50 times 25 is 17.5, which rounds to 18. Therefore I will guess 18, and I’ll win!”.

Little does Carol know that Dave is sitting just behind her and sees her chewing on her pencil. Dave applies the same thought process and concludes that if everyone is as smart as Carol, everyone will pick 18. Accordingly, he picks 0.5 \cdot 18 = 9.

You can see where this is going. If everyone playing the game follows this logic forever, the numbers keep dividing by 2 forever. And since \lim_{k \rightarrow \infty} a / (2^k) = 0, the only possible outcome for such a game played by rational players is for all players to choose 0, at which point all players win.

Of course in real life, the players are not rational. If all but one of the players are rational, they will all choose 0, but the remaining player will throw the average off by choosing something else. It may still be close to 0 (making the rational players the winners), but that depends on how many irrational players are in the game and what numbers they choose. It doesn’t take many before the rational players will almost always lose.

But then in real life, the players (even the rational ones) know that their competitors are not necessarily rational. This is a very different game now! Being rational will almost certainly cause you to lose – you must be irrational, but cleverly so.

In the example given, Alice was a “level 0” player: she chose randomly. Bob was a level 1 player: he chose believing that everyone else was a level 0 player. Carol was a level 2 player: she chose believing that everyone else was like Bob, a level 1 player. And Dave was a level 3 player.

Are higher level players better than lower level players? Well, that depends how accurate their estimation is. Dave chose 9 because he assumed that everyone is a level 2 player. And Carol chose 18 because she assumed that everyone is a level 1 player. But what if it was really Bob that was right, and everyone (except for Bob, Carol, and Dave) picked randomly? In this case we have an average of (17 \cdot 50 + 1 \cdot 25 + 1 \cdot 18 + 1 \cdot 9) / 20 = 45.10. The winning guess is that closest to 0.5 \cdot 45.10 = 22.55. Out of the “advanced” players, Bob came closest with his guess of 25!

Carol and Dave overestimated the ability of the majority. Bob underestimated Carol and Dave, but estimated correctly the majority, and so his guess was closest. Note that Bob still might not have won, since a level 0 player could have randomly guessed closer to 23 than Bob, but Bob’s strategy was best in this situation.

The point here is that when the players take into account the strategies of the other players, that itself becomes part of their “meta-strategy”, if you will. And they need to realize that other players may very well be taking that meta-strategy into account in their own. In the perfectly rational game, everyone takes this concept so far that they all end up guessing 0 (and winning). In real life, however, you need to make some estimate of the rationality of the group.

I’ll end this post with a related riddle that I like. There’s probably an “official” name for the this, but I don’t know it so I’ll just tell it.

—

A logician is arrested on a Sunday afternoon by the Spanish Inquisition. The magistrate tells him that he is to be put to death at exactly noon on one of the upcoming 5 weekdays. Furthermore the magistrate tells him that there will be no prior warning of the moment of execution; at noon on the chosen day the executioner will appear outside the logician’s cell. He ensures the poor logician that it will be a shock, saying “you will be completely and utterly surprised when the moment comes.”

The logician is taken away and put in a cell. To further the torment, a large clock is erected just outside the bars. As the rest of that Sunday passes, the logician stares fearfully as the hands of the clock slowly move. At midnight the clock booms; he sits in the corner of the cell and shakes with the fear of being completely and utterly surprised by the moment of execution. “If I only had some idea when it would happen, it would be much easier to bear! But the judge said I would be completely and utterly surprised.”

Monday morning comes and the hands continue to turn. At 10 o’clock he is fearful; at 11 he is terrified; at 11:59 he is shaking, and as the clock strikes noon he darts to the bars… but no-one is there. He lets out a gasp and sinks to the floor. “Well, I wasn’t executed today, so that leaves Tuesday, Wednesday, Thursday, and Friday. If only I weren’t to be completely and utterly surprised!”

That night the logician is thinking to himself. “I wish I could narrow down the day – the fright would not be as much!” As he paces the cell watching the hands climb over midnight, he comes to a realization. “Ah ha! Suppose it was Thursday night. Were I still alive to ponder the question, I would know that Friday must be the day of my execution. And that would mean that as the minutes grow closer to noon on Friday I would know the executioner is coming. And that would mean that I would not be completely and utterly surprised!” He stops pacing and looks at the clock triumphantly. “Therefore, since I must be completely and utterly surprised, my execution cannot be Friday!”

The logician lays back down on the thin prison mattress. The hands of the clock continue to wind around the face into the early morning of Tuesday, but he can’t sleep. As 6 o’clock comes he suddenly sits upright with another revelation: “Oh ho! Suppose it is Wednesday evening. Were my head still upon my shoulders, I would know that Thursday must be the day of my execution, having already ruled out Friday. And that means that as noon on Thursday approaches I would know the executioner is on his way. And that would mean that I would not be completely and utterly surprised!” Now his mind is working at full speed. “Therefore, since I must be completely and utterly surprised, my execution cannot be Thursday!”

Satisfied that he has narrowed down the day of his execution to Tuesday or Wednesday, he lays down. Before long it is 11 o’clock. Again he stands before the bars, trying to get a glimpse down the hallway. The minutes tick by and he begins to sweat. At 11:45 he is gripping the bars so tight his hands whiten. At 11:59 he grits his teeth, closes his eyes, and waits for the sound of the executioner entering the hall. But as the clock strikes 12 he is still alone.

Frowning, the logician lets go of the bars and walks to the back of the cell. He leans against the stone wall and looks at the clock thoughtfully. Slowly a realization comes upon him and he runs forward and shouts at the clock: “Ah ha! I have figured you out! You see, as I was not executed Monday, nor was I executed today, and I have already proven that it cannot happen Friday, nor Thursday, then the day must be Wednesday!” He is surprisingly happy for a man who has named his own execution date, and he continues: “But when noon approaches tomorrow I will know that the executioner is sharpening his blade, and when you point your hands to 12 I will know that I am to be killed. But that means that I will definitely not be completely and utterly surprised! And therefore Wednesday cannot be the day of my execution!”

He is practically jumping up and down at this point, shouting at the clock with glee. “And since I wasn’t executed Monday, and I wasn’t executed today, and I can’t be executed Wednesday, Thursday, or Friday, then I shan’t be executed at all!” Grinning, he returns to the bed and sits down, having proven conclusively that he will not be executed.

The clock continues to tick, apparently ignoring his demonstration. Tuesday concludes and Wednesday begins. The logician, sure of his safety, is soundly asleep as 9 passes on Wednesday morning, then 10, then 11. At 11:59 he is dreaming of lectures to be given and proofs to be written. But our poor logician has sealed his own fate.

The clock booms, signaling noon on Wednesday, and the logician suddenly wakes to the clanking sound of a key in a lock. He sits upright and rubs his eyes, and then makes out the hooded figure of the executioner standing just within the cell door.

With shock our doomed hero exclaims: “But it cannot be today! Why, I proved it could not be today! I proved it could not be at all! This is impossible! How can this be? I am completely and utterly surprised!”

—

Hopefully you enjoyed my version of the riddle. The relation to the p-beauty contest is pretty clear; the magistrate thought one step ahead and estimated the intelligence of the logician. The logician’s own estimation was what doomed him, much like Dave losing the contest because his estimate places him far from the correct answer. It’s unfortunate for our logician that game theory wasn’t developed until the 1940’s!