Source

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

I solved it and wrote up my solution.

Problem

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

Assign the players the numbers 0 through $N-1$. Player $i$ determines if any player numbered $< i$ has a red hat. If so, she bets 0. Otherwise, she bets $2^i$.

This strategy wins if and only if at least one player has a red hat, by the following reasoning. If all players have blue hats, then each player $i$ bets $2^i$ and they lose. Otherwise, let $j$ be the lowest-numbered player with a red hat. Each player $i$ such that $0 \leq i < j$ will bet $2^i$ which will pay out negatively. Player $j$ will bet $2^j$ which will pay out positively. Players $i$ such that $j < i$ will bet 0. Thus, the sum of the payouts will be $2^j - \sum_{i=0}^{j-1} 2^i = 2^j - (2^j - 1) = 1$. This is positive, so they win.

The probability that no players have red hats is $2^{-N}$, so the strategy wins with probability $1 - 2^{-N}$.

Define a *configuration* as a list of hat colors corresponding to the
players' hat colors in order from $0$ to $N-1$. A *subconfiguration*
for a player is an assignment of hat colors to all but that player.

One way to view a strategy is in terms of *mini-strategies*. A
mini-strategy is for a certain player to make a certain bet if he sees a
certain subconfiguration. For instance, one mini-strategy for $N=5$ might
be "Player 3 will bet 7 if player 1's hat is red, player 2's hat is blue,
player 4's hat is blue, and player 5's hat is red." Each strategy is
equivalent to a list of $N \cdot 2^{N-1}$ mini-strategies, one for each
player and each subconfiguration for that player.

For each mini-strategy, there are exactly two configurations in which it comes into play. In one configuration, its bet will pay off positively and in the other configuration it will pay off negatively. So, if you add up the score due to that mini-strategy across all configurations, you get zero. Since any strategy is just a combination of a bunch of mini-strategies, if you add up the score due to any strategy across all configurations, you also get zero.

For this reason, it's impossible for a strategy to win in all configurations. If it did, it would have a positive score for every configuration, and its sum across all configurations would be positive, not zero. Thus, a strategy that wins in all but one configuration must be optimal. Our strategy loses in only one configuration, that in which all hats are blue. Thus, it's optimal. $\Box$