TCS: Game Theory & 纳什均衡的计算

作者: , 共 793 字

Game Theory 即博弈论,目前在经济学中运用得最多 ( 纳什更因为他在这上面的工作拿到了诺贝尔经济学奖 )。但在最近几年,理论计算机界对它的研究也很热。

Game Theory 主要是研究在两人甚至多人的系统中,各方如何选择自己的策略使自己的效益最大化。这里每个人的收益不光决定于自己的决策,还决定于其它人的决策。主要有两种不同的游戏,一种是 两人零和游戏 ,只一个人赢的就是另一个人亏损的。一个典型的例子是下面这个,前两天有人在水木社区数学版问的:

某个村庄上只有一名警察,他要负责整个村的治安。小村的两头住着两个全村最富有的村民 A 和 B , A、B 分别需要保护的财产为 2 万元、1 万元。整个小村某一天来了个小偷,要在村中偷盗 A 和 B 的财产,这个消息被警察得知。

因为分身乏术,警察一次只能在一个地方巡逻;而小偷也只能偷盗其中一家。若警察在某家看守财产,而小偷也选择了去该富户家,就会被警察抓住;若警察没有看守财产的富户家而小偷去了,则小偷偷盗成功。

小偷将会去偷哪家?警察又应该守哪家?

还有一种是非零和博弈,经典的 囚徒困境 就是这一类。在这类博弈中,有可能产生合作实现双赢或者互相欺骗最后双输。

但无论哪种游戏(零和博弈可以看作非零和博弈的一种特殊情况,而 n 人非零和游戏又可视为 n+1 人的零和游戏),都存在均衡策略(指各方在知道对方的策略后不会主动改变自己现在的策略)。这就是纳什获得诺贝尔奖的主要结果,后世称此种均衡态为纳什均衡。

理论计算机里的 Game Theory 主要是研究计算纳什均衡的算法和复杂度。对于两人零和游戏,均衡点的计算即为一个线性规划的问题,目前已经有有效的算法。对于两人 ( 和多人 ) 非零和游戏,均衡点的计算已经被证明为 PPAD-complete ,一个在 P 和 NP 之间的复杂类。

Q. E. D.

类似文章:
注 : 这个问题来自 China Theory Week 2008 的 Open Problems Session。
相似度: 0.108
今天上课的时候老师讲的,我觉得很有意思。
相似度: 0.105
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
注:这篇文章是应 You XU 邀请的 guest blog。
更新:证明的关键一步发现错误,作者更新了论文,结论甚至论文标题都改了(废话),新版本 On the graph isomorphism problem
前一篇:
最近常看到官方的报导说今年的物价上涨属于结构性上涨,但一直没太明白这个结构性上涨是什么意思,上网看了一下,没找到什么特别权威的资料,大致有两种说法。
命题:实数集 \( \mathcal{R}\) 上的任何一个可数种颜色染色方案,都存在四个不等的同色点 \( x, y, z, w\) 使得 \( x+y=z+w\)