Monday, July 17, 2017

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 Kn or Ln.  There have been some papers on cycles (see herehere),  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 hereherehere). 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!



5 comments:

  1. I remember reading my first hat problems in Raymond Smullyan's books as a child, but he told them with colored stamps on the forehead of the players (so that each could see the others' stamps but not his).

    In one of these puzzles, two stamps were put on each player's head (you can also to that with hats, but you'd have to stack two hats). I couldn't find the exact problem on the net, but it was something along the lines of :
    3 perfect logicians A, B and C are shown 4 red stamps and 4 blue stamps. Two of these stamps are put on the head of each logician and the remaining two are hidden away. Each can see the stamps on the others' heads but not his.
    They are asked one after the other if they can deduce the colors of their stamps. A, B, C all say they can't. Then A is asked again and he still says no. Finally B is asked again and says he knows the color of his stamps.
    What are the colors of B's stamps ?

    I might have gotten it wrong, and should think about it more thoroughly to make sure this presentation is the right one, but the point here is that some hat problems variations put more than one hat on players' heads (and it cannot simply be converted into a problem with one hat and n * n colors).

    ReplyDelete
  2. Thanks Bill for sharing. can u please tell us which of these toy problems has real time applications or is used in some way in industry or theory ... be it either crypto or some other field.

    ReplyDelete
    Replies
    1. Good question.
      But actually I've never seen a hat problem that even claimed some application--- I invite my readers to leave comments about

      a) Has any paper even claimed an application (and not to some other branch of math)?

      b) Has any paper or result really been applied?

      I'm skeptical, but I've been skeptical before and found out something had an application!

      Delete
    2. Hamming Codes?

      Delete
    3. AH- you bring up an interesting point.

      One of the solutions of Winklers Problem (with randomly assigned hats, maximizing the expected number of people who get it right) does indeed USE Hamming codes.

      Hence a real world thing (Hamming codes) is applied to get a solution to a Hat puzzle.

      I thing you are looking for a hat puzzle solution be used for a real world problem.

      Alas, if Hat puzzles came first then math developed for Hat Puzzles would THEN be used for a real world application.

      This is almost a cliche: mathematics developed for real applied reasons without thinking of some pure math application, later used for pure math. We need to Fund and study more applied math to help us with our pure math problems!

      Delete