西塔图上的帽子猜测游戏

Hat Guessing Games on Theta Graphs

摘要: 帽子猜测游戏是一类基于图结构的组合信息游戏。给定无向图G = (V, E)，其每个顶点v代表一位参与游戏的智者，每位智者会被分配一顶从给定颜色集中选出的帽子，可用颜色数量由函数h(v)决定。在游戏规则下，智者仅能观察到其所有相邻顶点上同伴的帽子颜色，但无法得知自己的颜色。随后，智者们需依据预先约定的全局策略，对其自身帽子的颜色做出猜测。如果存在一种策略，使得在任意一种可能的整体帽子颜色分配状态下，都至少有一位智者的猜测是正确的，那么我们称该图上的帽子猜测游戏为获胜游戏。图G的帽子猜测数HG(G)被定义为：在每位智者仅允许猜测一次的情况下，使得游戏能够保持获胜状态的最大全局可能颜色数q (即对于所有顶点v，满足h(v) = q)。确定各类特殊图的帽子猜测数是该领域的核心问题之一。本文主要研究西塔图(Theta graph)上的帽子猜测游戏。我们通过引入子游戏属性以及失败游戏的构造推导机制，详细分析了帽子猜测策略在高维状态空间中的覆盖冗余与约束矛盾。研究证明，当赋予所有顶点的帽子颜色数恒为4时，西塔图上的帽子猜测游戏必然是一个失败游戏。综合已知基本图类的相关结论，本文最终完全确定了任意西塔图G的帽子猜测数为HG(G) = 3。

Abstract: Hat guessing games are a class of combinatorial information games based on graph structures. Given an undirected graph G = (V, E), each vertex represents a sage participating in the game. Each sage is assigned a hat chosen from a given set of colors, where the number of available colors is determined by a function h(v). Under the rules of the game, a sage can only observe the hat colors of all their neighboring peers but cannot see their own. Subsequently, the sages must make a guess about their own hat color based on a predetermined global strategy.If there exists a strategy such that under any possible global hat color assignment, at least one sage guesses correctly, the hat guessing game on the graph is called a winning game. The hat guessing number HG(G) of a graph G is defined as the maximum global possible number of colors q (i.e., h(v) = q for all vertices v) that allows the game to remain winning, given that each sage is allowed only one guess. Determining the hat guessing numbers for various specific graphs is one of the core problems in this field. In this paper, we focus on the hat guessing games on Theta graphs. By introducing the properties of subgames and the constructor mechanisms for losing games, we analyze in detail the covering redundancy and constraint contradictions of guessing strategies in high-dimensional state spaces. Our research proves that when the number of hat colors assigned to all vertices is constantly 4, the hat guessing game on a Theta graph is necessarily a losing game. Combining related conclusions from known basic graph classes, this paper finally determines that the hat guessing number for any Theta graph G is HG(G) = 3.