89944 Hat Problems

I've blogged about different hat problems a few times (see here). The question arises: How many hat problems are there? The answer is really infinite (literally) but I will list some parameters and bound them reasonably to get an upper bound.  Some of the combinations don't make sense, but we'll live with that. (I am also working on a website of hat problem papers. Its nowhere near finished yet and maybe never will be, but its here for your benefit. And for mine-- if there are some obvious papers I've omitted then comment or email me.)

First off, what is a hat problem? Ignoring many parameters: There are n people and c different colors of  hats and they are put on people's heads and the people have to guess what color hat they have on. They can see some or all of the other people. I'll mention one that has someone's name on it:

Winkler's Hat Problem (Peter Winkler proposed it here along with some other hat problems and some non-hat problems that are also fun)

There are n people and 2 color hats. An adversary will put the hats no peoples heads. The people must guess simultaneously their hat color. Maximize how many get it right in the worst case.

(ADDED LATER: While I have seen the above referred to as Winkler's Hat Problem, Winkler
himself told me that hs problem has the hats put on RANDOMLY, not by an adversary.)

Peter Winkler and later a paper by Ebert  et al. (Not Ebert of Siskel and Ebert--- to bad, that would be awesome!) that I mention below seem to have popularized hat games somewhat.  But this post is not about their history its about

how many hat games are there?

Here are some parameters I've seen for hat games. If you know of any others please comment!


1) Is the number of hats finite, infinite (and assume AC), infinite (but don't assume AC). I could say that since there are infinitely many infinities this is an infinite number of parameters, but we'll stick to countable and say this is a 3-valued parameter.  A paper on infinite number of hats is here.

2) The two most common puzzles are to have the people either all see each other, or in a line where person i sees person j iff i ≤ j. This can be viewed as the people are on K_n or L_n.  There have been some papers on cycles (see here, here),  triangle-free graphs (see here), some directed graphs (see here), a PhD that studies the problem on cycles (see here), and a paper with several graphs (see here). Formally this would be an infinite-valued parameter, but we'll take the number of classes of graphs that actually have been studied to be 4.

3) Do the people all guess their hat at the same time OR is there some ordering OR in rounds  3-valued.

4) Are people allowed to pass or not? (if they are then usually we demand that at least one does not pass). 2-valued. The paper by Ebert-Merkle-Vollmer which allowed passing got a lot of attention and brought hat problems to the general public. Its here. A generalization of Ebert's version is here. Ebert's game but on a line is studied here

5) Are the hats put on by an adversary who can hear your strategy (I've never seen a paper about an adversary who can't hear your strategy) or uniformly randomly or random with some known probability. The last case has been studied in several papers by Theo van Uem (see here, here, here). 3 valued

6) The players strategy can be deterministic or randomized. 2-valued. Butler et. al's paper about deterministic strategies covers a lot of material: here. 2 valued.

7) What is the goal? To get as many right as possible all the time? To get the expected number right as large as possible (prob may be based on either the random placement of hats or the random strategy of the players). There are even more variations here such as you want for each color there is a guaranteed fraction that get it right (see here) 3-valued

8) Is there some other information available. Examples I've seen: (a) at least one hat is RED, (b) for each color there is a bound on how many hats there are of that color, (c) the hats are natural numbes x,y, and x+y. (see here) (d) there are n+1 colors, n people, and each perosn has a different color (see here). Many values depending on the information given, but we'll just say 4-valued, the info above and no info.

9) Can some other information be revealed first? I've seen a paper where first everyone who sees a RED hat raises their hand. 2-valued.

10) Is a delay allowed? There are some puzzles where the people do reasoning about what others might deduce, so there is a delay in answers. 2-valued

11) I've never seen this- but how about trying to make sure that everyone gets it WRONG. 2-valued

12) I don't count this as a hat problem but some do: they want to find collectively information about all of the hats. Aspnes et al has 0-1 valued hats and wants to simul vote on the parity, see here. 2-valued.

This puts an upper bound on the number of possible hat puzzles at

3 x 4 x 3 x 2 x 3 x 2 x 3 x 4 x 2 x 2 x 2 x 2 = 89944.

This figure is wrong for reasons for reasons that both argue higher and lower.

a) Lower: MANY of  these combinations do not work together. For example, if you have an adversary and a deterministic strategy you can't talk about doing well in the average case.

b) Higher: For many of the above categories my number-of-values is low. For example you could look at hat games on many different graphs.

c) Higher: there are other variants I have not listed. That's where YOU come in! If you know of a version I have not discussed then please comment or email it to me!