Several different "hat games" have recently received a fair amount of attention. Typically, in a hat game, one or more players are required to correctly guess their hat colour when given some information about other players' hat colours. Some versions of these games have been motivated by research in complexity theory and have ties to well-known research problems in coding theory, and some variations have led to interesting new research. In this paper, we review Ebert's Hat Game, which garnered a considerable amount of publicity in the late 90's and early 00's, and the Hats-on-a-line Game. Then we introduce a new hat game which is a "hybrid" of these two games and provide an optimal strategy for playing the new game. The optimal strategy is quite simple, but the proof involves an interesting combinatorial argument.
A few years prior to the introduction of Ebert's Hat Game, in 1994, a similar game was described by Aspnes, Beigel, Furst and Rudich @cite_7 . In their version of the game, players are not allowed to pass, and the objective is for a majority of the players to guess correctly. For the three-player game, it is easy to describe a strategy that will succeed with probability @math , just as in Ebert's game: Alice votes the opposite of Bob's hat colour; Bob votes the opposite of Charlie's hat colour; and Charlie votes the opposite of Alice's hat colour.
@cite_7
1596450573
In the generalized Russian cards problem, we have a card deck @math of @math cards and three participants, Alice, Bob, and Cathy, dealt @math , @math , and @math cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathy's ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak @math -security) to not gaining any probabilistic advantage in guessing the fate of some set of @math cards (perfect @math -security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly @math -secure strategies and @math -designs on @math points with block size @math , when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect @math -security against Cathy when @math . We leverage a known combinatorial design to construct a strategy with @math , @math , and @math that is perfectly @math -secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak @math -security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of @math cards. Alternatively, the construction yields solutions for arbitrary @math , @math and any @math .