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 their 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 themselves having a red hat. The responses are recorded, but the responses are not shared until every player has recorded their 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 integer responses 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?

The strategy

Assign the players the numbers 0 through $N-1$. Player $i$ determines if any player numbered $< i$ has a red hat. If so, they bet 0. Otherwise, they bet $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}$.

Why it's optimal

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 they see 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$