有没有人把博弈论研究在作战理论中？？？

以下是引用sungmoo在2006-5-19 21:39:00的发言：

这里首先要对“计算所有博弈问题”与“求出博弈的解”做一下区分。

如果只是谈“计算所有博弈问题”，我同意“可以计算”，即该命题真。

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

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

以下是引用turingmachine在2006-5-20 23:36:00的发言：

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

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

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

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

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

具体的举个例子：

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

以下是引用turingmachine在2006-5-20 23:36:00的发言：

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

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

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

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

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

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

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

以下是引用sungmoo在2006-5-21 8:34:00的发言：

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

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

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

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

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

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

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

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

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

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

以下是引用sungmoo在2006-5-21 16:42:00的发言：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以下是引用turingmachine在2006-5-21 17:41:00的发言：…但是如果像你说的那样，[求出“博弈解”就是找出所要求的“纳什均衡”]的话。

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

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

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

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

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

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

仅供探讨。

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

以下是引用sungmoo在2006-5-21 16:42:00的发言：

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

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

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

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

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

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

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

以下是引用turingmachine在2006-5-21 22:17:00的发言：…那么对于一个无限博弈情况是怎样的？就是说一个求解一个无限博弈，是不是不一定等于找到其纳什均衡点？

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编辑过]