帽子游戏二

zhiqiangJune 25, 2007 科学

这个题目听说是MSRA的面试题。

在这个游戏的开头，我们设想自己要参加一个电视游戏大奖赛。规则呢，是这样。我们有 n 个人，作为一个小组来参加游戏。游戏中，主持人会给我们每人头上戴一顶帽子。帽子有黑白两种颜色，可以认为它们在我们各自头上的分布是临时随机决定的。小组中的每一个人，可以看到其他人的帽子颜色，但不知道自己的帽子颜色。每个游戏成员都被要求回答自己帽子的颜色（且必须回答，而且是独立回答的）。只有当所有人都回答正确（注意这里与帽子游戏一的区别），他们才能获胜，一起获得最后的大奖。

这个游戏还有最关键的一点：在游戏开始前(帽子戴上之前)，有一个“协商时间”，小组成员可以聚在一起，讨论决定小组应采取什么样的策略。但这个交流过程在游戏开始时自然终止。

现在的问题是：小组选择什么样的策略，才有最大的机会获胜呢？

因为任何一个人没有关于自己的帽子的任何信息，所以正确率不可能超过1/2。关键是怎么让所有人要么同时正确，以达到这个1/2的正确率。

所以，正确的策略应该是每个观众回答其余所有观众的帽子的异或（0表示白帽子，1表示黑帽子，则第i个人回答 $\oplus_{j\not=i}^n x_j$ 。

OK，现在这个问题到这里已经完整了。但令人惊奇的是，在两个星期前，来自伦敦大学的Taoyang Wu给了一个非常有趣的讲座，上面这个游戏恰是这个讲座的一个特例。

上面的问题其实是说有一个完全的有向图，每个顶点上有一个随机的变量。每一个点都知道它的邻居（连向它的点）的变量，需要猜测自己的信息。问以怎么样的策略能够使得所有点同时正确的概率最大？

显然，这个概率（记作 $p(G)$ ）与这个图G的结构密切相关，这样， $p(G)$ 某种意义上是这个图的结构的一个度量，称为Guessing Number，等于 $g(G)=n+\log p(G)$ 。根据前面所说，完全图的Guessing Number为n-1。另易知一个单环的Guessing Number等于1。而对一般图Guessing Number问题，无论是从直接求解（猜测是NP-hard），还是其性质分析，都还留下很多未解决的问题。