Cooperation via Codes in Restricted Hat Guessing Games

摘要

Hat guessing games have drawn a lot of attention among mathematicians, computer scientists, coding theorists and even the mass press, due to their relations to graph theory, circuit complexity, network coding, and auctions. In this paper, we investigate a new variant where there is exactly one hat of each color and where each player may receive multiple hats. Assume there are n players and T hats with different colors. A dealer randomly places k hats to each player and holds T - nk hats in hand. After observing the (colors of) hats of other players but not those of themselves, the players shall guess their colors simultaneously by a pre-coordinated strategy. We present methods to compute the best strategy under two common winning rules: all guesses are right or at least one guess is right, and derive exact value of the maximum winning probability for several cases. Especially, we introduce a novel notion called Latin matching between ((~([2n-1])_(n-1)) and (~([2n-1])_n) and establish its connection to the solution of some restricted cases. Here, ((([2n-1])_(n-1)) (respectively, ((~([2n-1)~n)) denotes the set of (n - l)-element (respectively, n-element) subsets of {1,..., 2n - 1}. Moreover, we show that some well-known combinatorial results (e.g. the antipodal matching between two symmetric layers of the subset lattice and the ordered design OD(t,k,v) given in modern design theory) can be applied to design explicit strategies in other cases. From our results we observe an interesting phenomenon that a leader is necessary for consensus but unnecessary for decentralization.