A combinatorial approach to Ebert's hat game with many colors (Q470962)

Let us first recall the simple version of the well-known Ebert's game. From the introduction: ``Three players walk into a room and each of them is given a hat. Each hat is either red or blue, and the probabilities of the colors of each of the three hats are equally and independently distributed. Each player can see the colors of the other players' hats but cannot see the color of his own hat. No communication of any type is allowed after the players walk into the room. After each player looks at the other players' hats, each of them has to guess the color of his own hat or pass. Each player does not know what the other players' responses are. They win collectively if at least one of the players guesses the color of his own hat correctly and no other player guesses incorrectly. Otherwise (if at least one player guesses incorrectly or everyone passes), they lose. Before the three players walk into the room and receive hats, they may plan a strategy of responses. The question is: What is the best strategy to optimize the chance of winning?''NEWLINENEWLINEIn this paper, the author shows, with a combinatorial optimization proof, the optimal strategy for this game with 3 players and \(k>2\) colors of hats. Then, he constructs a strategy for \(n\) players and \(k\) colors. He also compares his strategy with the one of \textit{H. W. Lenstra jun.} and \textit{G. Seroussi} [``On hats and other covers'', in: Proceedings of the IEEE international symposium on information theory. Lausanne: IEEE (2002; \url{doi:10.1109/ISIT.2002.1023614})]NEWLINENEWLINEFrom the author's abstract: ``In general, for \(n\) players and \(k\) hat colors, we construct a strategy that is asymptotically optimal as \(k\to\infty\). Computer calculation for particular values of \(n\) and \(k\) suggests that, as long as \(n\) is linear with \(k\), the strategy is asymptotically optimal.''