Multiple Hat Colors


I got this problem from Rustan Leino, who got it from Jim Saxe.

I solved it and wrote up my solution.


A team of $N$ people decide on a strategy for playing the following game. Each player walks into a room. On the way in, a fair coin is tossed for each player, deciding that player's hat color, either red or blue. Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other's hat colors, each player decides on a response, which is an integer treated as a bet on her having a red hat. The responses are recorded, but the responses are not shared until every player has recorded her response. Then, the team's score is calculated as follows: Add the integer responses for those players wearing red hats, and subtract from that the integers of those players wearing blue hats. For example, if $N=3$ and the players respond with 12, -2, -100 while wearing blue, red, blue, respectively, then the team's score is (-2) - (12) - (-100) = 86. The team wins if and only if its score is strictly positive.

What strategy should one use to maximize the team's expected chance of winning?

Solution     Reveal