Computer Science – Information Theory
Scientific paper
2005-09-15
Computer Science
Information Theory
IEEE International Symposium on Information Theory, Lausanne, Switzerland, July 2002
Scientific paper
We study a game puzzle that has enjoyed recent popularity among mathematicians, computer scientist, coding theorists and even the mass press. In the game, $n$ players are fitted with randomly assigned colored hats. Individual players can see their teammates' hat colors, but not their own. Based on this information, and without any further communication, each player must attempt to guess his hat color, or pass. The team wins if there is at least one correct guess, and no incorrect ones. The goal is to devise guessing strategies that maximize the team winning probability. We show that for the case of two hat colors, and for any value of $n$, playing strategies are equivalent to binary covering codes of radius one. This link, in particular with Hamming codes, had been observed for values of $n$ of the form $2^m-1$. We extend the analysis to games with hats of $q$ colors, $q\geq 2$, where 1-coverings are not sufficient to characterize the best strategies. Instead, we introduce the more appropriate notion of a {\em strong covering}, and show efficient constructions of these coverings, which achieve winning probabilities approaching unity. Finally, we briefly discuss results on variants of the problem, including arbitrary input distributions, randomized playing strategies, and symmetric strategies.
Lenstra Hendrik W.
Seroussi Gadiel
No associations
LandOfFree
On Hats and other Covers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Hats and other Covers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Hats and other Covers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-406886