New Constructions and Bounds for Winkler's Hat Game

Gadouleau, Maximilien; Georgiou, Nicholas

doi:10.1137/130944680

New Constructions and Bounds for Winkler's Hat Game

Gadouleau, Maximilien; Georgiou, Nicholas

Authors

Dr Maximilien Gadouleau m.r.gadouleau@durham.ac.uk
Associate Professor

Dr Nicholas Georgiou nicholas.georgiou@durham.ac.uk
Associate Professor

Abstract

Hat problems have recently become a popular topic in combinatorics and discrete mathematics. These have been shown to be strongly related to coding theory, network coding, and auctions. We consider the following version of the hat game, introduced by Winkler and studied by Butler et al. A team is composed of several players; each player is assigned a hat of a given color; they do not see their own color but can see some other hats, according to a directed graph. The team wins if they have a strategy such that, for any possible assignment of colors to their hats, at least one player guesses their own hat color correctly. In this paper, we discover some new classes of graphs which allow a winning strategy, thus answering some of the open questions of Butler et al. We also derive upper bounds on the maximal number of possible hat colors that allow for a winning strategy for a given graph.

Citation

Gadouleau, M., & Georgiou, N. (2015). New Constructions and Bounds for Winkler's Hat Game. SIAM Journal on Discrete Mathematics, 29(2), 823-834. https://doi.org/10.1137/130944680

Journal Article Type	Article
Acceptance Date	Jan 26, 2015
Online Publication Date	Apr 21, 2015
Publication Date	Apr 1, 2015
Deposit Date	Apr 28, 2015
Publicly Available Date	Apr 29, 2015
Journal	SIAM Journal on Discrete Mathematics
Print ISSN	0895-4801
Electronic ISSN	1095-7146
Publisher	Society for Industrial and Applied Mathematics
Peer Reviewed	Peer Reviewed
Volume	29
Issue	2
Pages	823-834
DOI	https://doi.org/10.1137/130944680