Hat Problems

I'm currently looking at the infamous Hat Problem devised (or at least reported in his PhD thesis) by Todd Ebert. Or, more specifically, I'm looking into the problem of autoreductions to random sets, but the whole process begins with the hat problem.

The hat problem goes like this: A group of N players are each assigned independently at random either black hat or a white hat. They can see the hats of all the other players, but they do not see their own hat. Nor can they communicate once they receive their hats (though they can devise a strategy before the game begins). Each person then either ventures a guess to what his hat color is, or passes, but has no idea how anyone else guesses. The goal is for at least one person to guess correctly the color of his hat, while none else incorrectly guess the color of theirs. (A pass does not count as an incorrect guess.) If there is at least one incorrect guess, the whole party loses.

Depending on how malicious one is feeling, one can add "There's $N million prize if the team wins, but everyone is executed if they lose" conditions, but that's besides the point.

Obviously, there's at least a 50-50 chance of winning. The strategy that easily attains that is simply: one person guesses white, while everyone else passes. But can one do better?

Part of the problem is that the hats are chosen randomly and independently from each other. So, a majority or minority of black hats does not mean anything about one's own hat. Thus it would seem that anyone's guess is at best a 50-50 shot, for the information of others' hats does not tell him anything about his own.

Now, in the completely unrestricted sense, there's no guaranteed winning strategy. The independent randomness guarantees that. However, if there is assurance of at least one black hat and one white hat (at at least two players), then there is always a winning strategy. But we won't worry about that now.

If we suppose there are three players, we can actually form a strategy that wins about 75% of the time. With three players, we have eight possible combinations of hats, two in which all hats are either black or white, but six in the case where two are one color, and one the other. Thus we can devise a strategy that makes use of that fact. Suppose, in that case, you are wearing the off-color hat. You'll see two hats of the same color, and it is fairly safe to surmise that yours is different. If you don't have the off-color hat, you'll see one hat of each color, and thus you really don't have any clue. In the first case, you'll announce the off-color, and in the second, you'll keep silent. A quick analysis shows that you only lose in the case of everyone's hat being the same color, or only 25% of the time. In effect, we've bumped up the winning percentage from 50% to 75%. (This is provably optimal, so that's about as good as it gets.)

How does this work for more players, though? It certainly gets more complicated. If we just move it up to four players, we can try to keep the same kind of strategy. If every hat you see is the same color, you declare that your hat is the opposite color. So, here again you lose if all hats are the same color, but you win if there's a 3-1 split. But about a 2-2 split? In that case, no one sees all the same color, so we have to add in some more analysis.

This would be easy if we could know how others guessed and figured in some kind of time delay. For example, if a person sees all one color, then within 10 seconds he would make his guess. Then, if no one has guessed after ten seconds, everyone would then correctly guess his hat color by guessing the color that would make a 2-2 split. However, that's not part of the rules. What else can we do?

It turns out that any strategy we assign to deal with the 2-2 split is going to overlap with our 3-1 split strategy. So we'll try to be a little creative. We're going to "designate" a few possible combinations that we'll automatically put off limits. For example, in our 3 man scenario, we designated WWW and BBB as off-limits--i.e, we act as those won't happen and go from there.

How do we choose these "designated" strings? We'll, there's a complicated way to describe these using the Hamming distances and error-correcting codes, but we won't delve into that just yet. But for starters, suppose (in our 4 man case), that the actual arrangement is BWWB. Player 3 then sees two blacks and a white, and so he know there are only two possible combinations the hat arrangement could be: either BWWB or BWBB. Notice these two combinations only differ in one place. Now, suppose we had previously "designated" BWBB as off limits. Then Player 3 has only one choice: he'll state that his hat is white.

In reality, we only have good means of "designating" combinations if the total number of players is N=2^k-1 for some k. Why? When you have this many players, you can "designate" small fraction of combinations such that every other combination only differs from exactly one of the "designates" in one position.

When we had 3 players (3=2^2-1), when we "designated" WWW and BBB, notice that three of the remaining combinations (WWB, WBW, BWW) fall only one place different from WWW, and the remaining three (BBW, BWB, WBB) fall only place different from BBB. (This is what is called having a Hamming distance of 1. The Hamming distance between two strings is simply the number of positions where they differ.) Thus every non-designated string has a Hamming distance of 1 to exactly one designated combination.

We reach N=2^k-1 by the following reason. The number of strings with Hamming distance of 1 to a particular string is N, where N is the length of the strings involved. If we form a ball of these, we have N+1 strings per ball (out of a total of 2^N strings). Now, we want to partition all strings into such balls such that every string is contained in exactly one ball. The number of balls we form is 2^N/(N+1), which is an integer if and only if N+1 is a power of 2: N+1=2^k for some k.

Now, there are methods in cryptology for determining how to properly form these balls, but we won't delve into that here. Needless to say, the centers of these balls will be our "designated" combinations, and our strategy will follow this line: when you observe your teammates, if one of the two possible combinations is "designated", choose the other one. If neither are designated, then pass. Our success probability becomes 1-1/(n+1) overall.

But how do we handle the 4 player case? Well, it should seem like we could designate 3 three strings (3 balls with 5 strings per ball is 15, one less than the total 16 strings), and go from there. However, it's not actually possible to form 3 disjoint balls. Consider this. Let the center of the first ball be WWWW (it doesn't matter what we pick, as the answer will be the same, but this is easier to work with). Now, the strings in the ball around it are every string with one B: BWWW, WBWW, WWBW, and WWWB. Strings with two or more B's will be outside the ball. Now, the center of the next ball has to have Hamming distance of 3 from WWWW. Why? If it has a Hamming distance of 2 (say it is WBBW), then the balls will over lap (in this case, the ball around WBBW will contain WWBW and WBWW, which are in the ball around WWWW). Well, we can find a string with Hamming distance 3 from WWWW, such as BBBW. But in order to find the center of third disjoint ball, we have to find a string with Hamming distance 3 from both of the previous centers. However, any string with a Hamming distance 3 from WWWW will have Hamming distance 2 from our second center! (Just compare BBBW, BBWB, BWBB, WBBB, and you'll see that's true.)

Well, this just means we won't be playing as optimally as we'd prefer. We could pick 4 designates, which would then cover the space with some amount of overlap, and then additionally specify that if our choices are two designates, that we pass, and we would then succeed in our strategy with probability 1-4/16=.75, which is 75% of the time (which is down from 1-1/5=.8, or 80% we would have hoped). That's still good odds, though.