New Constructions and Bounds for Winkler's Hat Game
New Constructions and Bounds for Winkler's Hat Game
复制标题
温克勒帽子游戏的新结构和界限
DOI：
10.1137/130944680
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
Gadouleau M
中科院分区：
文献类型：
--
作者：
Gadouleau M
帽子问题最近已成为组合数学和离散数学中的热门话题。这些已被证明与编码理论、网络编码和拍卖密切相关。我们考虑以下版本的帽子游戏，由 Winkler 引入并由 Butler 等人研究。一支队伍由多名队员组成；每个玩家都会被分配一顶给定颜色的帽子；根据有向图，他们看不到自己的颜色，但可以看到其他一些帽子。如果团队有这样的策略，即对于任何可能的帽子颜色分配，至少有一名玩家正确猜测自己的帽子颜色，则该团队获胜。在本文中，我们发现了一些新的图表类别，它们允许获胜策略，从而回答了 Butler 等人的一些开放性问题。我们还得出了可能的帽子颜色的最大数量的上限，这些上限允许给定图表的获胜策略。
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.