这里边要用到一个概念： 什么叫“有限时间里用计算机可以计算“。

也就是等价与能求出博弈解的问题。

这个问题比一般看起来的样子要复杂得多。

在复杂性理论里这个可计算的概念是使用一种严格的数学表示来说明的。

就是多项式时间可计算的概念。 就是说一个问题的计算时间的规模可以用多项式来表示的话，那么就定义这个问题是一个可以被有效的计算的问题。

具体的举个例子：

x^2+2x

这是一个多项式。

2^x+ 4^y

这不是一个多项式（是一个指数式）

图灵机的概念。看下边这几个资料吧。有点抽象：（

图灵机的基本概念（因为找不到中文相应合适的网页，这个是英文的）：
http://plato.stanford.edu/entries/turing-machine/

下面的是中文的：
http://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA

http://www.hep.edu.cn/booksintro/qianyan/jisuan.htm

我个人的想法是，“有限时间里用计算机可以计算”与“能求出博弈解”不等价。

按照博弈论求解（这是我们分析的前提），任何一个博弈的三要素都要为求解者已知，如果处理信息结构不确定的问题（特别是信息结构总在变化），博弈论并不能派上用场（尽管博弈论可以继续假设某种信息的不确定性，但仍要借助某种确定的信息结构——比如既定的概率分布）。也就是从这个意义上，我认为计算机实际能处理的问题也比博弈论多得多，深得多。

此外，“有限时间里用计算机可以计算”的问题未必都是博弈论问题吧。而如果一个（给定三要素的）博弈的解“无法在多项式时间内被确定型图灵机解决”，那么我的表述就错了。

我想听听你对这种“等价性”的看法，或者说对“求出博弈解”的看法。

[此贴子已经被作者于2006-5-21 9:18:36编辑过]

我对能“求出博弈解”的这个概念的认识比较的原始和含糊。我得再好好想想。

还有就是你上边提到的“博弈的三要素“能不能稍稍定义一下。刚翻了一下书没找到相应的定义。

你先谈谈你对“求出博弈解”的这个概念的认识吧。 我看能不能接受。 因为你一问我才发现自己并不是很清楚这个概念。

求出“博弈解”就是找出所要求的“纳什均衡”（因为一个博弈完全可能有无数个纳什均衡，有时我们要再限定一些条件求出特定的纳什均衡）：指出每个参与人要采取的策略，并且每个参与人都不愿意改变这种策略（只要任何其他参与人都不改变自己的策略）。

博弈的三要素是参与人、策略、支付（或者叫效用）。

不过，如你所说，如果我们真地构造出一个“无法在多项式时间内被确定型图灵机解决”的博弈，那么这个博弈就是计算机不可解的。能不能构造出，我自己没有能力证明。

我需要独立确认一下这个概念。

但是如果像你说的那样，[求出“博弈解”就是找出所要求的“纳什均衡”] 的话。

那么这个问题不是多项式时间可解的。

这个结论似乎已经被证明过了。

下面是这个证明的论文。 你参考一下。

http://www.cs.berkeley.edu/~christos/papers/pure.ps

[此贴子已经被作者于2006-5-21 17:42:03编辑过]

计算博弈的解，大致的意思是这样吧：只要双方可选择的战略范畴给定，并能估计出不同战略选择所需的支付，通过估计选择各种战略的概率或概率分布，总能计算出如此结果:在某一概率下，将出现的情景会是如何，各方的选择是什么，如此选择下各方的支付为多少。这样可计算出来的结果绝非一个，但可能的结果大概都可以计算出来。

求出博弈的解，则意味着在上述各种可能的结果中，我们是否能确定哪一个才是必定会发生的情况。即使，某一状况的概率非常之小，我们依然不能断言该种状况不会发生。应该是罗素吧，曾经说过，一只小鸡每次看到主人出现都能得到食物，观察了99次之后，它确定主人出现等于食物供给。但第100次时，主人出现，没给它吃的反而把它给吃了。如果一定要求出博弈的解，计算机大概会这样回答吧：你准许我犯1%的估计错误，我给你90%准确度的答案。如果你不准许我犯一点错误，那么我就没有任何确定的答案可以给你了。

博弈论是一种对事件发生之后的后验和分析解释工具吧，不是不可以用来预期，只是不可以用来进行精确预期。如果将其运用到战略研究，大概只能是：如果对方处于何种天时、地利、军情，我方采取何种战略，获胜的概率较大，牺牲的军力较小。而无论提出何种战略，都需要遵守这一兵法原则吧：战略计划可以在将出征之前给出，但出征之后，则只能是将在外军令有所不受了。

帖子看到今天，sungmoo和turingmachine的讨论蛮精彩的。不过，我对数学一直有些郁闷不已，lz似乎也有些郁闷了(也有可能估计错误) ，妄言几句，以助继续讨论之雅兴。好的帖子总是不希望沉下去，或太快的沉下去。呵呵。

虽然我还不能完全看懂该文，不过我相信“不是多项式时间可解”。

现在我们可以继续讨论一下，人脑如何得到博弈解？证明解的存在性与求出具体解还是两个问题。如果我们只知解存在，但不知究竟是何解，是否也无法谈到“应用”？

“计算机可求解”与“博弈论可应用”应该是什么关系呢？如果连计算机都不能实现“多项式时间可解”，面对这样的博弈论问题，我们是否也无法“应用”博弈论了？或者说，谈“博弈论应用”时要排除一大类博弈问题。

人脑除了设计计算机，还有没有别的求解法？如果排除了别的救解法，你的判断“有限时间里用计算机可以计算等价于能求出博弈解”就是对的。不过，我又有一种担心，真地在操作中面对了这样的博弈，人脑可能会不自觉地“偷懒”（未经人预先设计的计算机是否没有这种能力？）——把博弈修改成可计算的（改变了博弈的信息结构）。

仅供探讨。

[此贴子已经被作者于2006-5-21 21:37:29编辑过]

我特别找书来确认了一下，纳什均衡的存在性定理是这样说的：

“每一个有限博弈至少存在一个纳什均衡（纯战略的或混合战略的）”

张维迎：博弈论与信息经济学。 p113

问题来了，有限博弈的解从上边的定理来看，应该是等价与找到这个博弈的纳什均衡点。

那么对于一个无限博弈情况是怎样的？

就是说一个求解一个无限博弈，是不是不一定等于找到其纳什均衡点？

A game is finite if the set of players and all the strategy sets are finite.

对于infinite games，由于数学困难（太过于一般），我们无法说明其解存在的一般性（只能说明一类特殊的infinite games，比如strategy sets是紧的度量空间。另外，这里可能还要引入新的解概念，比如epsilon解）

其实这里的问题是，对于无限博弈，首先要确定的是，“解”（从而“求解”）该如何定义（基于这个解的定义，我们得以说明解的存在性，而这个解背后也有着经济意义）。解的定义与“存在性”命题的讨论是联系在一起的（当然也不能没有经济意义）。

[此贴子已经被作者于2006-5-22 10:40:32编辑过]

找另外一本书确认了一下。

Drew Fudenberg,Jean Tirole: game theory, MIT ,1991 (中文版，博弈论，人大出版社，2002)

1。3。3节“具有连续收益的无限博弈的纳什均衡的存在性” P.27

这里说到的一个结论就是： 纯策略均衡在收益不连续时不一定存在。

存在很多例子显示，在这种情况下，混合策略也可能不存在。

证明存在性与找到博弈解还是两个问题吧。

很简单的博弈“纯策略纳什均衡”也可能不存在，于是人们推广解的概念——混合策略纳什均衡。如果还有一些很简单的博弈连“混合策略纳什均衡”也可能不存在，人们需不需要再推广一下解的概念呢？

个人以为，理论上“解”的定义要与其存在性证明相关，而实际中“解”的定义还要有经济意义。如果在很大的“范围”里，一种理论的“解”常常不存在，我们就得要么抛弃这种理论，要么修改解的定义了。不同的解的定义可能有不同的存在性命题，这也是我们评价“解”定义的一种原则。

“解不存在”，自然计算机计算不了；“解存在”，计算机也未必计算得了。

我还想探讨前面那个问题，如果计算机不能计算而解又存在，人脑该怎么计算呢？

我觉得这确实是两个问题。

等我想想他们之间的关系。。应该是怎样的。

这个问题比较好回答，因为是一个经典问题，答案是现成的。就是叙述起来有点长。等我来整理一下。

今天看来不行了。明天吧。

[此贴子已经被作者于2006-5-22 14:01:12编辑过]

你们的谈话令我受益非浅，如果有时间可以帮你们整理成册~~

来整理一下这个问题我个人的看法。

先来定义一下两类问题：

1。 计算机可以在多项式时间里计算出解的问题，这类问题被定义为“多项式时间可解问题”（简称为P-problem）

2。 计算机不能在多项式时间里计算出解，但解的正确性的证据可以在多项式时间以内得到判定的问题，这类问题被定义为“非多项式时间可解问题”（简称为NP-problem）

关于这两类问题是不是等价的问题，是一个著名的open problem (P?=NP问题)

P-NP问题，可以参看一下下面这两个网页。

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

我觉得，[“解存在”，计算机计算不了] 这类问题应该就对应着NP-problem

[“解存在”，计算机也计算得了] 这类问题对应着P-problem

[此贴子已经被作者于2006-5-22 21:58:42编辑过]

问题越来越难，我也有点发晕了：）

先灌两瓢水。   再看看哪个问题能找出个眉目来。

[此贴子已经被作者于2006-5-24 19:28:24编辑过]

我倒！楼上两位的精彩发言真的很深奥，我一点都看不懂。

插个嘴，请教几个小问题：

1、根据测不准原理，1m到底有多长？

2、如何精确显示一个无理数？

3、用人类语言能否精确描述一个名词的“概念”？

1.你要“1m”的长度是想做什么用的呢？（不知你是否学过相关概念，“不确定度”与动量有关，动量很大的物体不确定度完全可以忽略不计——做任何事情都要有所“忽略”，“忽略”的原则就是“你想干什么”）

2.你要精确显示无理数的目的又是什么？（最精确的是用一个代数符号，比如“pi”；写成“3.1415…”也可以，而这是用有理数近似无理数的方法——“近似”的原则也是“你想干什么”）

3.这个判断可能是个悖论，在你“精确”地定义“精确”这个概念之前，没有人能做任何回答。

对于此问题，再插一句，长度单位“米”与“物体的长度”是两个概念，两个问题，不能混淆在一起。

“米”的定义，你可以在任何有关“国际单位制”的介绍中了解到。

“不确定原理”（也有人称“测不准原理”）不是针对“长度单位”的表述，并且不确定的“程度”的表示也离不开各种单位。比如普朗克常数仍有自己的量纲。

如果说博弈，我国早在数千年前就开始运用了，著名的莫过于《孙子兵法》。

如果说现代意义上的真正研究，那么早在一战期间也开始了大规模的研究，二战尤甚！

可以看看那个著名的机构：兰德。

大名鼎鼎的冯．诺依曼就在那期间专门研究这个问题，而且是实战！

我只知道这个问题。

对应的大约应该是维特根斯坦的语言哲学。这个方向是一个当前研究的大热门。 具体的就不知道了。

记得目前的结论好像是：描述起来非常困难，要满足一堆条件。。。。我说的是具体意思的准确理解。。。。

诺伊曼研究了“实战”问题？可否举一二个例子？

他“在那期间”好像更多地是研究武器技术吧？

根据我的印象，应该是武器技术，或者组织管理。典型的例子是，有一次需要解决军队排队洗碗的速度问题，这是后勤保障问题啊。

类似中国人观念中的“谋略”，几乎很少。觉得谋略还是初级问题，经验丰富的指挥员在实践中拼直觉就可以解决，作用没有想象中的大。

http://www.moulue.org/

中国谋略科学网

58楼说得很有道理

排队洗碗问题 和 银行排队取钱问题 都应该属于运筹学范畴吧