The Hat Puzzle (A Consulting or Engineering Interview Brain Teaser)

The Hat Puzzle is one of my favorites. This is one of those brain teasers people might ask in an interview for a consulting or engineering job.

Here is the problem, as worded by Sara Robinson (this is a good article to read):

Three players enter a room and a red or blue hat is placed on each person’s head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players’ hats but not his own.

No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly.

…

The general problem is to find a strategy for the group that maximizes its chances of winning the prize.

(In the language of game theory, this is a simultaneous coordination game of incomplete information.)

If the players could talk after they had hats on, the game would be trivial. Since the players have incentive to cooperate, they would honestly reveal what they see. In a matter of seconds, they could all figure out their hat colors and guess correctly.

But the rules only allow for an initial strategy session. How well can the players fare? Amazingly, they can do pretty well.

The Basic Strategy (50 percent winning)

The rules heavily penalize incorrect guesses. A single incorrect guess makes the group lose—even if the other two players guess correctly. A single incorrect guess is the apple that spoils the bunch.

So it’s important the rules allow for players to pass. If a player doesn’t have a good guess, it would be a good idea to pass.

A basic strategy would be to minimize the risk of bad guesses. Force two players to pass in every game and make one person the official guesser. The group wins exactly when this person guesses correctly.

How often will the group succeed? Since the hat color is chosen by a coin flip, there is a 50 percent chance of guessing the correct color.

This is not too shabby when there’s a $3 million dollar reward at stake. I will take that gamble any day.

If I were conducting an interview, I would be satisfied if an applicant, never having heard the puzzle, came this far. The answer demonstrates basic risk management and an understanding of probability.

But can the team do better than random chance?

If you’ve been reading my game theory articles, then you would guess that they can. Players can do often do better than random chance if they consider the distribution of outcomes—a tactic I described in my article about finding true love.

The trick is figuring out the players do have a way of coordinating as a group. Doing this, they can make winning an amazing 75 percent chance. Let’s investigate why.

One Optimal Strategy (75 percent winning)

Motivating question: does observing the other two hat colors tell you anything about your own hat color? In other words, if you see two red hats, does that make your hat more likely to be blue?

The answer is no, and that’s a potential roadblock. Regardless of what you see, your hat color is determined by a coin flip. Fair coins are never “due” for a particular outcome—each toss is independent.

But don’t get caught up in probability—the fact is that seeing the other hat colors does convey information. The problem is the figuring out how to transmit that information to the other players.

To get around that, players need to coordinate guesses based on what they see. If possible, they still want to minimize bad guesses by having two people pass and one person guess. What’s needed now is a group strategy.

How can they do that? It starts by taking a step back and considering the possible distributions of hat outcomes. With three players and two hat colors, there are a total of eight equally likely outcomes:

Is there anything special about the distribution?

One feature is that most outcomes—six of them—include at least one hat of both colors. Only two extreme outcomes don’t—the ones with all red hats or all blue hats.

We can analyze further. Among outcomes with both hat colors, there logically has to be two hats of one color (the “majority” color) and one hat of another color (the “minority” color).

Here’s the kicker: by looking at the other hats, players can identify whether they are wearing a majority color or a minority color.

For instance, if a player sees both a red and blue hat, then the player must be wearing the majority color (which could be red or blue).

If a player sees two blue or two red hats, then the player must be wearing the minority color, which will be the opposite color of what the player sees.

Here is what players can reason among the six choices:

Now the idea is to get the player with the minority hat color to guess and force the other people to pass.

So here is the strategy:

• if you see both a red and a blue hat, then “pass”
• if you see two red hats, then guess “blue”
• if you see two blue hats, then guess “red”

This strategy wins in all six cases with at least one hat of each color. It only loses in the two cases of all-red or all-blue, in which all players guess incorrectly.

Here is how players would guess:

All told, the group wins in six of eight possible outcomes—a whopping 75 percent chance.

Optional Extra Credit: The Host can Learn

If you’re playing rock-paper-scissors against a computer that mixes randomly, you could win 1/3 of the time simply by picking one strategy, say rock. But if the computer could learn and analyze your pattern, it might respond by countering with paper and start winning a lot. To maintain your 1/3 winning chance, you need to randomize your choices among rock, paper, and scissors.

In the hat game, the players have a 75 percent chance of winning, but the strategy has a pattern. It loses every time the hat colors are all the same. A responsive host, like the computer in rock-paper-scissors, would see the pattern and respond by assigning hats to be the all one color more frequently. To keep the host honest, the players need to randomize.

Is there some a way the players can win, without creating a pattern of outcomes in which they all lose?

Amazingly, yes there is! Even more surprising, the winning percentage stays at 75 percent.

In researching this article, I learned about the claim and a proposed winning strategy from a presentation on Michel Waldschmit’s website called “Coding Theory, Card Tricks and Hat Problems.”

Unfortunately the slides didn’t contain the proof, or an example, so I felt a little bit like I was staring at the margin of a textbook from Fermat.

I took out my own pencil and paper and worked on the answer. I am happy to say I came up with the following analysis myself.

The Random Optimal Strategy (75 percent winning)

The random strategy is a refinement on the static one given above. The key to the above strategy is that players essentially bet against the outcome being all-red or all-blue. Knowing that, it was possible to coordinate guesses so only one person guessed and gave a correct answer.

There’s nothing special about picking all-red or all-blue.

The players can randomly pick any color combination and its “opposite” configuration (red-blue-red and blue-red-blue are opposites) as outcomes to bet against. The remaining six outcomes can be coded based on the hat colors that each player sees.

Why would this work, and why does it have to be “opposite” combinations?

The eight outcomes of the hat game can be visualized as vertices of a cube. Adjacent vertices differ by changing only a single “coordinate,” that is, the color of one player’s hat.

The graphical interpretation is as follows: can the players identify which vertex they belong to? The information they are given is the other two hat colors they see—that is, they are effectively placed at midway points along the adjacent edges.

Each player can see the coordinates of the other two players, but is unsure about the own coordinate—that is, the player is unsure which of the two possible endpoints the group belongs to.

We want a situation where exactly two players will not be able to tell the vertex (they will “pass”) and the remaining player will know the location (and guess correctly).

Such a unique coding occurs when players bet against a random vertex and the “opposite” one—a limitation that gives maximal location information.

In any of these cases, players only lose if in fact the outcome is one of the two they bet against, meaning they have a 75 percent chance of winning.

The 75 percent chance of winning applies to every time the game is played but the losing outcomes are randomized. Hence, the host won’t be able to exploit any particular color combination.

Appendix: The coding for betting against red-blue-red and blue-red-blue outcomes (others can be found similarly)

Strategies:

Player 1:
If see blue-red, then pick red.
If see red-blue, then pick blue.
Else pass.

Player 2:
If see red-red, then pick blue.
If see blue-blue, then pick red.
Else pass.

Player 3:
If see red-blue, then pick red.
If see blue-red, then pick blue
Else pass.