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

zglloo

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

swh@home

好复杂啊，我只听过纳什和博弈论，还有NP-完全问题，但两者有什么联系，完全不知道。

kittyjia

以地球目前的科技，也许找不到。但是，电脑的出现不过近七十年，一百年后，二百年后，再回过头来看这些问题，也许迎刃而解。不要低估人类科技的发展速度。太阳周围的UFO的出现，有可能证明存在高于地球科技几十万上百万年的文明，他们应该解决了这些问题。

不听流行

我觉着楼上没明白

zglloo

回复 4# 不听流行


    八卦一下, Knuth 大爷说了, NP 和 P 的问题, 会在 2048 2^11 年或者 4096 2^12 年被解决 :)