计算机科学家给经济学家的教诲——纳什均衡是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 (百度百科有向伪基发展的潜力)

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

FOCS 06 best paper...

> 删除
2009-11-12 00:14:26 foo (百度百科有向伪基发展的潜力)

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 (Is set of CLI groups complete)

是Pspace-hard吗？

> 删除
2009-11-12 16:46:45 foo (百度百科有向伪基发展的潜力)

PSPACE-hard吧

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

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

> 删除
2009-11-12 19:06:49 foo (百度百科有向伪基发展的潜力)

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

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

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

> 删除
2009-11-12 22:18:25 icefire (好想静下心来啊)

好好研究一下

> 删除