Why is a raven like a writing-desk? Final Part
I think that I’m going to give up trying to solve the Hat Problem, though I’ve come pretty far (for background, see my original description and its follow-up post). I’ve now solved the N=5 version (with surprising results!), and gotten a pretty good framework around the problem:
- With a deterministic strategy, every time a person guesses their hat colour correctly there is a corresponding configuration when the person guesses incorrectly, namely the same hat configuration with that individual person’s hat colour flipped. I will not consider nondeterministic strategies, so we will have this 1-to-1 correspondance between correct guesses and incorrect guesses.
- Define a “complete” strategy to be a strategy which does not contain a hat configuration in which everyone passes. If your strategy had a configuration in which everyone passed, you would lose nothing by having someone guess wrong in that situation instead. Consequently, the best complete strategy will be no worse than the best incomplete one.
- If there is a hat configuration in your strategy in which the group loses because someone guessed wrong, it can’t hurt to modify your strategy so that everyone guesses wrong in that configuration. Having more people guess wrong in a losing configuration may make other, passed configurations winners, but it can never turn a winning configuration into a losing one.
- Consequently, for a given losing configuration, we can have everyone guess wrong there, and turn every configuration that is a single colour-flip away into a winning configuration (and then have people pass when they know they’re not in one of these predetermined losing configurations). In these configurations that are 1 colour-flip away from losing configurations, everyone will pass except the people who think it might be alosing configuration, who will all guess correctly.
One way to visualize this is to construct an unweighted, undirected graph with 2^N vertices, one for each hat configuration. Two vertices will be connected by an edge iff they are a single colour-flip apart. Now, if you label a vertex/configuration as a losing state, you can label every adjacent state a winner (except if it’s already a losing state, in which case it’s still a loser). So, to get the best odds of winning, what we really need to do is find a minimum dominating set for the graph (thanks to Steamboat Steven for showing me this problem in an unrelated conversation weeks ago!). To summarize this new problem, a dominating set is a subset of vertices such that every vertex in the graph is either itself in the set or adjacent to a vertex in the set. We’re now looking for the smallest dominating set. Remember that at least one optimal solution will always be a minimum dominating set because dominating sets correspond to complete strategies, and the optimal complete strategy is at least as good as the optimal incomplete one.
The bad news is that this problem is NP-Complete for arbitrary unweighted, undirected graphs. The good news is that our graph does not have arbitrary structure: each vertex has degree N, and they are connected in a regular pattern. The tricky news is that I have no idea how to benefit from this structure (which is probably why this is still an unsolved problem). I’ve written a Java program to search over all possible dominating sets, and I am releasing the source code under the Creative Commons Attribution-Share Alike license. Its running time is better than the previous program: if you want at most M dominating vertices, it’s “only” O(2^(MN)). However, this still means that I can’t use it to solve the N=6 problem in my lifetime.
But I verified the N=3 solution, verified that the best you can do for N=4 is the N=3 solution and have the fourth person do nothing useful (with the dominating set solution, the fourth person only guesses when the other three people guess wrong). However, I’ve also found the solution for N=5, and it really surprised me. Last time, I showed that of the 32 possible hat configurations, the optimal solution will win between 24 and 26 times. It turns out it wins 25 times: one set of dominating vertices are the bit representations of 0, 1, 2, 15, 23, 27, and 28. All other numbers between 0 and 31 inclusive are 1 bit-flip away from at least one of these, so we would have 7 losing configurations and 25 winning ones. I know this is the optimal solution because this was the best solution the program found with at most 7 dominators (it also considered cases with fewer dominators; note that with 6 dominators the best you can do is 24 winners), and with 8 dominators, there are only 24 other vertices which could be winners. How strange! I have no idea why these numbers have the properties they do, and I’m not going to look through the other 3839 equivalent dominating sets to see if any of them have a recognizable pattern. At this point, I’m just going to give up and admit it’s a pretty tough problem.
It’s not clear to me that you can do things like “have someone guess if everyone passes”. What if there’s exactly one configuration where everyone passes. Then flipping any hat implies someone would guess, and therefore no one can tell that we’re in a configuration where everyone passes.
Suppose that we have a strategy containing a hat configuration where everyone passes, and suppose without loss of generality that in this configuration, person X has a blue hat. If person X observes everyone else’s hats to be consistent with this all-pass configuration, the group loses nothing when person X guesses his hat is red. If his hat was blue, they were going to lose anyway. If his hat is red, he guessed right and cannot hurt the team’s performance. In this latter case, it is possible that someone else will also guess correctly and that our correct guesses are bunching up on top of each other. But person X will never hurt the team by guessing that they’re not in a losing configuration.