{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:26:03Z","timestamp":1787325963840,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/130944680","type":"journal-article","created":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T12:07:06Z","timestamp":1429618026000},"page":"823-834","source":"Crossref","is-referenced-by-count":13,"title":["New Constructions and Bounds for Winkler's Hat Game"],"prefix":"10.1137","volume":"29","author":[{"given":"Maximilien","family":"Gadouleau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicholas","family":"Georgiou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,4,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"M. Krzywkowski,\n                      Hat Problem on a Graph,\n                      Ph.D. dissertation, University of Exeter, UK, 2012.","DOI":"10.7494\/OpMath.2012.32.2.285"},{"key":"atypb2","unstructured":"T. Ebert,\n                      Applications of Recursive Operators to Randomness and Complexity,\n                      Ph.D. dissertation, University of California at Santa Barbara, 1998."},{"key":"atypb3","first-page":"121","volume":"50","author":"Krzywkowski M.","year":"2010","journal-title":"Comment. Math."},{"key":"atypb4","unstructured":"G. D. Cohen, I. Honkala, S. Litsyn, and A. C. Lobstein,\n                      Covering Codes\n                      , Elsevier, New York, 1997."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702415317"},{"key":"atypb6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/962","volume":"14","author":"Riis S.","year":"2007","journal-title":"Electron. J. Combin."},{"key":"atypb7","unstructured":"S. Riis,\n                      Graph Entropy, Network Coding and Guessing Games\n                      , ar Xiv: 0711.4175, 2007."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2155618"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"atypb10","first-page":"301","author":"Winkler P.","year":"2002","journal-title":"MA"},{"key":"atypb11","unstructured":"U. Feige,\n                      You Can Leave Your Hat On (If You Guess Its Color)\n                      , Technical report, Computer Science and Applied Mathematics, Weizmann Institute of Science, MA, 2004."},{"key":"atypb12","unstructured":"B. Doerr,\n                      Integral Approximation\n                      , Ph.D. dissertation, Christian-Albrechts-Universita\u0308t zu Kiel, 2005."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2010.07.007"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20512"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/060652774"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.03.027"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"J. Bang-Jensen and G. Gutin,\n                      Digraphs: Theory, Algorithms and Applications\n                      , Springer, New York, 2009.","DOI":"10.1007\/978-1-84800-998-1"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130944680","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:24:54Z","timestamp":1787322294000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130944680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130944680"],"URL":"https:\/\/doi.org\/10.1137\/130944680","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}