计算机科学家给经济学家的教诲——纳什均衡是NP问题

2009-11-11 20:51:00 来自: zglloo(成器)

以1994年诺贝尔经济学奖得主约翰·纳什命名的纳什均衡是博弈论中的重要概念。纳什证明每个博弈必定存在一个纳什均衡点，其他经济学则推测纳什均衡点极难找到，但如果找到的话，它将能精确描述市场的行为。那么找到纳什均衡点的难度究竟有多大呢？一位计算机科学博士生的博士论文(PDF)——获得2008年度美国计算机协会学位论文奖——认为经济学家的推测是错误的，找到纳什均衡点是几乎不可能的事。
目前担任MIT电机工程和计算机科学系助理教授的Constantinos Daskalakis与UC伯克利的Christos Papadimitriou、英国利物浦大学的Paul Goldberg合作，证明对某些博弈来说，穷全世界所有计算机之力，在整个宇宙寿命的时间内也计算不出纳什均衡点。Daskalakis相信，计算机找不到，人类也不可能找到。纳什均衡属于NP问题，Daskalakis证明它属于NP问题的一个子集，不是通常认为的NP-完全问题，而是PPAD-完全问题。这项研究成果被一些计算机科学家认为是十年来博弈论领域的最大进展。
http://science.solidot.org/article.pl?sid=09/11/10/0957225

2009-11-12 00:07:44 foo ([;\mathbf{P}=\mathbf{BPP};])

这里当然要提一下Xi Chen, Xiaotie Deng证明两人博弈纳什均衡是PPAD-complete的文章

FOCS 06 best paper...

回应删除举报广告
2009-11-12 00:14:26 foo ([;\mathbf{P}=\mathbf{BPP};])

Lance Fortnow: What is PPAD?
http://blog.computationalcomplexity.org/2005/12/what-is-ppad.html

回应删除举报广告
2009-11-12 15:45:04 [已註銷]

其實類似的研究成果早就有了，就是以博弈論來計算圍棋任意盤面上給定規則後的最佳應手。令某些頑固的希望數學對圍棋無能為力的人極其失望的是，相應的算法是存在的，該問題是遞歸可判定的。但是，另一方面，論及圍棋問題的計算量，已經是比NP更難的DSPACE-hard問題了。這是一個對於博弈論的計算問題之難的構造性證明，但可能是因為東西方文化的隔閡而名氣並不是很大，本人由於對圍棋有愛才去查閱相關文獻。雖然沒讀過LZ給出的文，但個人相信，尋找納什均衡點的難度問題，早已在圍棋問題上得到解決。
若只說一句話，就是：I told u。

回应删除举报广告
2009-11-12 15:53:35 [已註銷]

我想到的是，某氣象學家重複了一下數學家做了好幾十年的微分方程解的穩定性的問題，做出來的結果最多只及得上Poincare在19世紀末的開山之作，與20世紀數學家的深入研究相比只能算幼稚園水平，但此人卻用電腦畫出一些很上去很酷的圖，還從希臘神話裡找來一個聽上去很酷的名字：chaos，於是此人就被捧為chaos之父。
Poincare若在世，不知作何想？

回应删除举报广告
2009-11-12 15:57:42 withinbeyond (Legend In Newyork！)

是Pspace-hard吗？

回应删除举报广告
2009-11-12 16:46:45 foo ([;\mathbf{P}=\mathbf{BPP};])

PSPACE-hard吧

一般我们说DSPACE(f(n))这样的，然后PSPACE=Big Union_{c} DSPACE(n^c)

另外尽管对复杂性理论还算有点了解，我还是要承认自己看不明白“尋找納什均衡點的難度問題，早已在圍棋問題上得到解決”是啥米意思

回应删除举报广告
2009-11-12 19:06:49 foo ([;\mathbf{P}=\mathbf{BPP};])

另外楼顶文章不准确。。。纳什均衡的难解性体现于它是PPAD-complete的。。。而不是在NP里。。。后者说明的实际上是易验证性。。。

另外不能说真正证明了“在整个宇宙寿命的时间内也计算不出纳什均衡点”。因为这个难解性还是依赖于类似P!=NP的假设的，这里我想大概是FP!=PPAD吧

计算复杂性领域研究者的行为模式通常是这样的：他们试图证明x确实不可能有简单的方法求解，但是这个任务目前看起来不大有希望。所以他们换了个方法：定义一个包含x的复杂性类Y，然后说：瞧，我能证明x是Y里面最难的。而Y显然不是一个容易求解的复杂性类（因为至今没能证明它的反面），所以。。。

回应删除举报广告
2009-11-12 22:18:25 icefire (好想静下心来啊)

好好研究一下

回应删除举报广告
2009-12-17 10:48:15 无向无间 (也许活着的信仰是“有信仰”)

学习的目的不是知道，而是拥有独立探索和发现的能力。

回应删除举报广告