帽子游戏二

作者:, 发表于

这个题目听说是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),还是其性质分析,都还留下很多未解决的问题。

Q.E.D.


上一篇:帽子游戏一2007年6月19日
在这个游戏的开头,我们设想自己要参加一个电视游戏大奖赛。规则呢,是这样。我们有 n 个人,作为一个小组来参加游戏。游戏中,主持人会给我们

下一篇:策略游戏:医生和病人(I)2007年7月10日
我很早之前就想过这个问题,但一直只知道一个trivial的答案。前两天无意中发现网上已经有高手给出了更好的方案,故记录在此。有兴趣的可以自己想


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。