hat tricks

Among many things the internet has been blamed for, is the phenomenon of people only ever reading stuff that they agree with, and thereby reinforcing their opinions without having them challenged. By analogy, do we spend too much time hanging out with our familiar research communities? At the 23rd British Combinatorial Conference, to which I was invited to give a talk, I now have to struggle to come to terms with research on topics that have obvious computational questions, but where it’s other questions that get considered.

One talk was on a topic that is, at a stretch, vaguely game-theoretic: “Hat problem on a graph” by Marcin Krzywkowski relates to a kind of puzzle described here¹, in particular the 3 hat problem. Three players are fitted with hats, each hat may be either red or blue, the colour chosen uniformly at random. Of course, you can see the other players’ hats but not your own. Each player may (simultaneously) make a guess as to his own hat colour, or else abstain from guessing. They win if at least one player makes a correct guess and no player makes an incorrect guess. For this 3-player case there is a simple guessing scheme whereby their win probability is 3/4. As hinted in this version of the puzzle, if the players can flip coins, there is a randomized scheme that lets them win with probability 3/4 even if the hats are allocated by an adversary — but the adversary should not be able to eavesdrop on their coin-flipping before they get fitted with the hats. (A question: suppose the adversary can eavesdrop on them beforehand but then they can flip coins after the hats have been fitted. The players can win with probability 1/2 by delegating one of them to guess at random. I don’t think they can do better and would guess there should be a nice proof that even works for any number of players, but haven’t figured one out.)

Back to the paper — suppose there are n players and suppose that there are some restrictions on which players can see each others’ hats. It is natural to represent this with a graph on the players, in which a player can see only his neighbours, so that the basic hat problem would assume the complete graph. Then, one can ask how well the players can do for various kinds of graph. If I recall correctly, the players can win with probability 1/2 if the graph is a path; other kinds of graph are also considered.

¹I thank Sophie Huczynska for drawing my attention to this web site.