Hat problem
|
|
The hat problem, attributed to Todd Ebert, in his 1998 Ph.D. thesis at the University of California, Santa Barbara, is a strategy question about a cooperative game, which has been shown to have connections to algebraic coding theory. A team of N players, where N is at least three, are randomly assigned hats that are equally likely to be red or blue, under conditions such that:
- each team player can see the hats of the other team members, but cannot see their own hat;
- team members cannot communicate in any way.
For example, separately in a series of television studios, they are shown video clips of the hats being placed on the heads of the others, on television monitors, but everyone is blindfolded while being filmed.
Then they are kept apart, and are independently interviewed. They are allowed to make a guess at their own hat colour, or to decline to guess.
The hat problem is this: is there a pre-agreed team strategy for guessing, which will improve on an expected value of 0.5, for the score of the team, when it is awarded as 1 if there is at least one correct hat colour guess and no incorrect guess, and 0 otherwise?
The answer has been shown to be 'yes' for N = 3, and some higher values of N.
One such strategy for solving the hat problem employs Hamming codes, which are commonly used to detect and correct errors in data transmission. This strategy can be applied to team sizes of <math>N = 2^k-1<math> (e.g. 3, 7, 15) and achieves an expected value of <math>\frac{2^k-1}{2^k}<math>. Notably, the Hamming code strategy yields greater expected values for larger values of <math>N<math>.