纯技术贴 Civ4是个很单纯的小游戏（博弈论分析）[翻译完毕]

RP_MAN

嗯，有一次捉云说要在下用博弈论来分析Civ4。当时答应了（估计捉云自己都忘记了）……
那么，现在就从纯技术角度来分析一下这个游戏好了。
实话说，从来“纯技术的”博弈论文章都是用英语写的，中文真的不会写……
所以就先写着，到时候自己简单翻译一下好了。先全英语，想说的都说清楚了，然后尽量中文翻译。省得有夹杂，又不伦不类……
捉云你不是说要我写的吗，花那么大力气写好了，过来翻译！

Section I


We investigate the nature of Civilisation 4 in this article and show that, despite the popular belief that it involves complicated strategies, the game is in fact, very trivial from a game theorist’s perspective. We prove this by showing that this game must have at least one Nash-Equilibrium and thus cannot be more complicated than other finite (trivial) games such as chess. Section II briefly discusses the underlying existence theorem of Nash Equilibria. Section III proves that Civ4 must have at least one NE. Section IV offers some concluding remarks.

Section II

The concept of Nash Equilibrium was introduced to non-cooperatively game theory by Nash in 1951. Let I denote the finite set of players in the game, Si be each player’s strategy set. We let si be an element of Si for player i. By convention, let –i denote players other than i.
Let Ui be the payoff function for player i. A strategy profile (si*, s-i*) is said to be a Nash Equilibrium strategy profile if the following condition hold:

Ui(si*, s-i*) >= Ui (si,s-i*), for all si not equal to si* and for all player i.

A Nash equilibrium strategy profile constitutes a profile of mutually (or multilaterally) best responses. Given that all other players –i uses their respective strategy s-i*, player i does not gain by unilaterally deviating away from strategy si*.

In his celebrated paper in 1951, Nash proved the following existence theorem:
Theorem 1:

Every game in which the strategy sets Si have a finite number of elements has at least a (mixed) strategy Nash Equilibrium.

The proof of this theorem can be found in any advanced game theory book and is thus omitted here.

Section III

We now use Theorem 1 to derive the central proposition of this paper which shows that Civilisation 4 is, indeed, a trivial game.
Proposition 2:

Civilisation 4 must have at least one NE.
Proof: We prove the above proposition by showing that the condition in Theorem 1 is met.
(1)
Note that there are a finite number of players in the game. The usual upper limit is 18 players (whether human or AI players).
(2)
Note that in each period (turn) of the game, each player has a finite set of actions that can be taken. (Building, moving troops, attacking etc.)
(3)
The game itself has a finite number of periods (turns). It ends either when certain victory conditions are achieved, or when a finite number of turns have been passed. (For example, 1200 turns under Marathon speed.)
Thus it is clear that each player’s strategy set, Si, must contain a finite number of elements. Hence by Theorem 1, Civilisation 4 must have at least one NE.
QED


Proposition 2 shows that no matter how complicated strategies Civ4 might seem to contain, it must have at least one NE once the map, number of players and other settings have been specified. By definition, if each player is playing his/her respective NE strategy, no one can do better by using any other strategies. Thus the game must be trivial as long as one can determine its NE.

Section IV

It has been shown that Civilisation 4 is in fact, a very trivial game in the sense that it must have a NE. However, several cautionary remarks need to be made here. Even though a NE equilibrium exists, it is not necessarily unique. Given civilisation 4 is a sequential game with incomplete information, it is very likely that it will contain a multitude, even infinite amount of NE. Thus one might need to impose refinement concepts such as Subgame Perfect Nash Equilibrium (which is guaranteed to exist Mas-collel et al (1995)) or Perfect Baysian Equilibrium. Second, even though equilibria exist in theory, one might not be able to identify them explicitly as the amount of computation involved is prohibitively high. (As a good example, it is a well known result that chess must have a NE, but its identification is beyond the limit of existing computing power.) Thus one can rest assured that even though a NE exists for Civ 4 in theory, it does not deprive the game of its fascinating powers—precisely because we cannot explicitly solve for it. Each time when a new map is generated, when the sun rises in 4000BC, we are still facing a new, exciting and challenging game on any practical level.


References
Mas-colell, A, Whinston, M and Green, J. 1995. Microeconomic theory. Oxford University Press.

Nash, J. F. 1951. non-cooperative games. Annals of Mathematics 54: 289-95.

RP_MAN

自己保留，用来翻译。翻多少是多少。从来没有看过中文文章的格式，还有些东西可能会翻得不伦不类……大家谅解……

第一章

本文将对文明4这个游戏进行探讨。我们将在文中证明，尽管很多人都认为这个游戏牵涉到很复杂的策略，但从博弈论的角度而言，文明4其实是一个很简单的小游戏而已。我们将证明，这个游戏必然有一个纳什均衡，所以，其复杂程度不会超过别的（有限策略）游戏如国际象棋。第二章将简单的阐述纳什均衡以及纳什的定理。第三章将证明文明4至少肯定有一个纳什均衡。第四章包含一些讨论。

第二章

非合作博弈中的纳什均衡最先由纳什在1951年提出。我们让 I 代表游戏中所有玩家的集合； Si 代表每个玩家 i 的策略集合； si 代表玩家 i 的某一个策略。按照学术习惯，-i 将用来代表所有不是 i 的玩家。让 Ui 代表玩家i 的效用函数。一组策略(si*, s-i*) 在满足了以下条件后，被称为纳什均衡策略 (Nash equilibrium strategy profile 中文到底叫什么……）：
Ui(si*, s-i*) >= Ui (si,s-i*), for all si not equal to si* and for all player i.
在纳什均衡中，所有玩家的策略构成相互的best response。也就是说，对所有玩家 i 而言，在纳什均衡中，他的对手都选择他们各自的策略s-i*, 玩家i 无法通过单方面的采用不是si* 的策略来获益。
在其著名的1951年的文章中，纳什证明了以下定理：
定理1
如果一个游戏中，每个玩家的策略集合都包括有限的元素的话，这个游戏至少有一个纳什均衡。
此定理的证明可以在很多博弈论的教科书中找到，这里省略。

第三章
引用定理1，我们可以得出本文的中心理论。这个理论将证明，文明4是个很简单的小游戏。
理论2
每局文明4必然会有至少一个纳什均衡。
证明：要证明理论2，我们只需证明定理1中的条件在文明4种是满足的。
（1）每一局的玩家数量是有限的。一般来说上限是18个，无论是人类还是电脑玩家。
（2）每一回合中，每个玩家所能采取的行动是有限的。（建造，移动单位，进攻，等等）
（3）每一局的回合数是有限的。当某个胜利条件达成，或者当一定数目的回合达到后，游戏结束。（比如马拉松速度最多1200回合。）
所以，每个玩家的策略集必然包含有限的策略。所以，引用定理1，文明4 必然有至少一个纳什均衡。

上述理论证明了无论这个游戏看起来有多复杂，在每一局，在地图，玩家数量以及其他设置都定下以后，这个游戏必然有至少一个纳什均衡。只要每个玩家都遵循其纳什均衡中的策略来游戏，没有人可以通过单独地选择别的策略而获益。所以这个游戏是个很简单的小游戏——只要我们能找到其理论上必然存在的纳什均衡。

第四章

本文证明了文明这个游戏其实是一个很简单的小游戏，因为从博弈论的角度而言，它每一局必定有一个纳什均衡。但是，我们在这里要做一些注释。第一，尽管，纳什均衡必然存在，它未必单一。文明4是一个动态的，包含不完全信息的游戏。它很有可能有很多，甚至无限个纳什均衡。所以，我们很有可能要进一步的寻找更加精炼的均衡。比如说子博弈精炼均衡（这个是必然存在的Mas-collel et al (1995)，或者贝叶斯精炼均衡等等。 第二，尽管理论上来说，这个游戏必然有一个纳什均衡存在，我们未必可以将其计算出来——其牵涉的计算量可能非常巨大。（一个很好的例子：博弈论中早就证明了国际象棋必然有至少一个纳什均衡，但以现在的计算机计算能力，我们还远远不能将这个均衡算出来。）所以，玩家们可以放心，尽管纳什均衡在理论上存在，这个游戏的魅力仍然不会减少——因为我们算不出这个纳什均衡。所以，当每次一个新地图生成的时候，当每次太阳在公元前4000年升起的时候，我们实际上面对的，仍然是一个崭新的，刺激的好游戏

[ 本帖最后由 RP_MAN 于 2008-6-21 16:37 编辑 ]

水滴子

你没有认为你不翻译会有人看吧 ……

RP_MAN

最讨厌作翻译了……哪怕是自己的文章……
再过一会朋友的导师要请吃饭……
捉云，你叫我写的！过来翻译！！

玉米派

来拜读了……

zdfsilence

有意思，学到新东西了，查了下啥叫纳什均衡，顺便贴一下

纳什均衡名称来源及简介：
纳什均衡，Nash equilibrium ,又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。约翰·纳什1948年作为年轻数学博士生进入普林斯顿大学。其研究成果见于题为《非合作博弈》（1950）的博士论文。该博士论文导致了《n人博弈中的均衡点》（1950）和题为《非合作博弈》（1951）两篇论文的发表。纳什在上述论文中，介绍了合作博弈与非合作博弈的区别。他对非合作博弈的最重要贡献是阐明了包含任意人数局中人和任意偏好的一种通用解概念，也就是不限于两人零和博弈。该解概念后来被称为纳什均衡。


纳什均衡定义：
假设有n个局中人参与博弈，给定其他人策略的条件下，每个局中人选择自己的最优策略（个人最优策略可能依赖于也可能不依赖于他人的战略），从而使自己效用最大化。所有局中人策略构成一个策略组合（Strategy Profile）。纳什均衡指的是这样一种战略组合，这种策略组合由所有参与人最优策略组成。即在给定别人策略的情况下，没有人有足够理由打破这种均衡。


纳什均衡经典案例：囚徒困境
（1950年，数学家塔克任斯坦福大学客座教授，在给一些心理学家作讲演时，讲到两个囚犯的故事。）
假设有两个小偷A和B联合犯事、私入民宅被警察抓住。警方将两人分别置于不同的两个房间内进行审讯，对每一个犯罪嫌疑人，警方给出的政策是：如果一个犯罪嫌疑人坦白了罪行，交出了赃物，于是证据确凿，两人都被判有罪。如果另一个犯罪嫌疑人也作了坦白，则两人各被判刑8年；如果另一个犯罪嫌人没有坦白而是抵赖，则以妨碍公务罪（因已有证据表明其有罪）再加刑2年，而坦白者有功被减刑8年，立即释放。如果两人都抵赖，则警方因证据不足不能判两人的偷窃罪，但可以私入民宅的罪名将两人各判入狱1年。表2.2给出了这个博弈的支付矩阵。
表2.2  囚徒困境博弈
——————————————————————————
　　　　　　　　┃　　　　 B　　  ┃　　　　 B　　   ┃
————————┃————————┃————————┃
　　　　　　　　┃　　　　坦白　   ┃　　　　抵赖　    ┃
————————┃————————┃————————┃
A　　   坦白　　 ┃　　 –8, –8　   ┃　　　0, –10　 ┃
————————┃————————┃————————┃
A　　   抵赖　　  ┃　　–10, 0　　 ┃　　　 –1, –1　┃
————————┃————————┃————————┃

关于案例，显然最好的策略是双方都抵赖，结果是大家都只被判1年。但是由于两人处于隔离的情况，首先应该是从心理学的角度来看，当事双方都会怀疑对方会出卖自己以求自保、其次才是亚当·斯密的理论，假设每个人都是“理性的经济人”，都会从利己的目的出发进行选择。这两个人都会有这样一个盘算过程：假如他坦白，我抵赖，得坐10年监狱，坦白最多才8年；他要是抵赖，我就可以被释放，而他会坐10年牢。综合以上几种情况考虑，不管他坦白与否，对我而言都是坦白了划算。两个人都会动这样的脑筋，最终，两个人都选择了坦白，结果都被判8年刑期。

基于经济学中Rational agent的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被释放就不会出现。这样两人都选择坦白的策略以及因此被判8年的结局，纳什均衡”首先对亚当·斯密的“看不见的手”的原理提出挑战：按照斯密的理论，在市场经济中，每一个人都从利己的目的出发，而最终全社会达到利他的效果。但是我们可以从“纳什均衡”中引出“看不见的手”原理的一个悖论:从利己目的出发,结果损人不利己,既不利己也不利他。

西艾薇.C.丫头

好文章，水滴把帖子移到创意学园吧

水滴子

可是，存在一个那什么均衡和文明是小游戏有什么关系？

水滴子

沉了就转

zdfsilence

感觉就是 因为有一个纳什均衡的游戏就是小游戏，又因为文明有一个纳什均衡，所以文明是小游戏

西艾薇.E.捉云

没错 是翻译做 纳什均衡.

西艾薇.E.捉云

没有意见的话 我受精给人品男了?

西艾薇.E.捉云

还有 这个一点实用性能都么有..完成了么?

不过我觉得如果你做一个小型分析战报,会好的多,例如玩一个10分钟能结束的图, 1v1的. 然后用Game Theory去分析下一步应该如何发展,毕竟这个Gametheory那么难,人不可能看一下你的文章就明白吧?更何谈在文明里应用呢?

炸鸡宝宝

电脑本身的运算能力不够，玩家更不够，均衡不能啊
就像如果电脑的运算能力足够，象棋AI的先手一定不会输的，玩家最好的结果就是和棋

Jean.Brown

與人鬥其樂無窮~~~~~~~~~~~~~~~~~
這個是亙古不變的真理阿~~~~~~~~~~~~~~~

RP_MAN

原帖由 塞爱维.E.捉云 于 2008-6-21 18:42 发表
还有 这个一点实用性能都么有..完成了么?

不过我觉得如果你做一个小型分析战报,会好的多,例如玩一个10分钟能结束的图, 1v1的. 然后用Game Theory去分析下一步应该如何发展,毕竟这个Gametheory那么难,人不可 ...

所以说是纯技术贴。很多时候纯理论的东西就是如此的。
分析一个实际的文明4游戏，找出其中的纳什均衡是在实际操作中是几乎不可能的。就像文中说的国际象棋大家都知道有纳什均衡，但是无法计算出来。为什么呢？ 如果说黑棋先走，那么有8个卒可以动，每个卒可以走一步或者两步。或者，黑棋可以动任意一个马，那么每个马还有两个走法。也就是说，黑棋第一步就有20个可以选择的行动。白棋也是如此。那么前两步可能牵涉到的行动就是20*20=400。你可以想象一下接下来的计算量……
那么文明的话，也是如此，8个玩家，不用15个回合的话，这个计算量已经是天文数字了……

RP_MAN

原帖由 zdfsilence 于 2008-6-21 17:57 发表
有意思，学到新东西了，查了下啥叫纳什均衡，顺便贴一下

纳什均衡名称来源及简介：
纳什均衡，Nash equilibrium ,又称为非合作博弈均衡，是博弈论的一个重要术语，以约翰·纳什命名。约翰·纳什1948年作为年 ...

其实，我一直很恼火初级教材喜欢用囚徒困境来作为纳什均衡的例子……很多新学博弈论的都被这个例子误导而以为博弈论很简单，或者博弈结果必然让双方都不利。这是错误的认识。
是的，从定义而言，囚徒困境中的均衡的确是一个纳什均衡，但是它是一个很特别的纳什均衡，这个其实叫(strictly) dominant strategy nash equilibrium.
在囚徒困境博弈中，每个囚徒无论对方作什么，都有一个dominant strategy，就是confess--Against any strategy of your opponent, confessing always gives a higher payoff。而更广义的纳什均衡所要求的仅仅是:Given that everyone else is using a particular strategy, I do not gain by deviating away from my own strategy。
不是每个博弈都存在Dominant strategy euqlibrium (事实上，很多没有)。即使存在，dominant strategy equilibria的集合也只是纳什均衡的一个子集而已。

????

  RP男举个你认为典型的那时均衡的例子吧

zdfsilence

博弈论的前提是不是每个参与者对各自的行动会造成的结果都完全了解，从而选择对自己最有利的行动？
如果是的话，在实际的游戏过程中，似乎不可能做到这点啊？

????

每个参与者对各自的行动会造成的结果都完全了解，从而选择对自己最有利的行动？

这个无论是游戏还是现实都不可能做到吧