博弈树与逆向归纳法1

1动态博弈与逆向归纳法假如欺负他人可以获得快乐，那你会欺负他人吗？大多数人的回答是不会，原因正如他们所指出的，欺负他人会担心他人的报复，这抵消了从欺负他人的行为中所能得到的快乐。这个答案至少表明，你之所以现在没有欺负他人，并不因为不想欺负他人，而是因为你知道欺负他人会在将来给自己造成麻烦。同样，当我们面临一些博弈对局的时候，我们应如何采取现在的行动，常常取决于每个行动在将来会产生什么后果，或者说在将来别人将如何反应。在前面各章内容中，博弈是静态的——或者说是同时行动的。而现实中的博弈常常是动态的、依序行动的，这就要求我们必须考虑人们在将来对我们的行动反应。分析序贯行动博弈的一个重要思路就是：向前展望，向后推理(lookingforwardandreasoningbackward)，即面向未来，思考现在，站在未来的立场来确定现在的最优行动。本章我们将通过一些例子来说明这一分析思路，其中有些例子很有趣，也很有挑战性。§5-1逆向归纳法1、美中军事政治博弈我们通过一个简单的例子来说明序贯博弈的（离散策略的）扩展式表达和逆向归纳法求解方法。这个例子可以称做美中军事政治博弈，或者叫“毛泽东的对外军事政治战略”。故事模型在我国解放初期，美国一直试图对我国实施打击。此时，我国必须对美国采取应对之策。就我国对美国可以采取的行动而言，无非是回击或不回击。用更符合毛泽东的话来说，美国可以“犯我”或“不犯我”，而我们可以“犯人”或“不犯人”。由此我们可以刻画出一个动态博弈：●博弈方：美国、中国；●行动空间：美国可选择的行动是“犯我”或“不犯我”；中国的选择是“犯人”或“不犯人”；●行动顺序：美国先行动；中国观察到美国的行动后再选择自己的行动；●赢利：我们这样假设赢利状况（数字是虚拟的）；●如果美国“犯我”，中国“犯人”，恶战再所难免，则美国亏损2，中国2美国亏损2；●如果美国“犯我”，中国“不犯人”，那么中国沦为美国的附庸，丧失国家主权，则美国获得2，中国亏损4；●如果美国“不犯我”，中国“犯人”，那么就是中国挑起战事，美国正好有借口纠合国际力量打击中国，则美国得3，中国亏损5；●如果美国“不犯我”，中国“不犯人”，各自和平地发展经济，则美国得1，中国得1。2、博弈树对于上述动态博弈，我们可以用博弈树(gametree)表达如下（图5-1）：犯我不犯我中国中国犯人不犯人犯人不犯人（－2，－2）（2,-4）（3,-5）（1,1）图5-1美中军事政治博弈图5-1的博弈树是这样解读的：美国先选择“犯我”或“不犯我”，然后中国观察美国的选择后选择“犯人”或“不犯人”；最右边的括号内数字是各种情况下双方的赢利状况，前一个数字代表第一个行动人（美国）的赢利，第二个数字代表第二个行动人（中国）的赢利。依此类推，如果有更多的参与人序贯行动，则赢利的排列顺序与行动顺序一致。3、逆向归纳法究竟什么是图5-1博弈的均衡呢？在完美信息动态博弈中，我们要找的均衡实际上是一条路径，即从第一个行动人决策结点出发，一直到某一个终点之间的路径。所谓均衡路径就是在每一个决策阶段，没有人会偏离这条路径。这条路径所代表的策略均衡被称做子博弈完美均衡。下面我们介绍如何用逆向归纳法来求解博弈的均衡。逆向归纳的步骤是这样的：●首先，从最后阶段行动的参与人决策开始考虑。在图5-1的博弈中，最后行动的是中国，因此我们先考虑中国怎么决策。在考虑中国的决策时，我们假3定美国已经选了“犯我”或“不犯我”；◆如果美国选择了“犯我”，在图5-1中可发现，中国选择“犯人”会得到-2，选择“不犯人”会得到-4；因此中国必然选择“犯人”——我们就在中国“犯人”的分枝上画上一个短短的横线标记；◆如果美国选择了“不犯我”，从图5-1中可发现，中国选择“犯人”会得到-5，选择“不犯人”会得到1，因此中国必然选择“不犯人”——我们就在中国“不犯人”的分枝上画上一个短短的横线标记。●然后，考虑次后阶段行动的人（例子中只有两个阶段，因此实际上就是第一阶段行动的人）——美国。美国决策时会考虑中国的反应，而现在它已预见到中国将选择的行动就是两条划了双横线的分枝。所以，它很容易推出自己面临的情况是：◆若选择“犯我。，则必然导致中国“犯人”，则美国得到-2；◆若选择“不犯我”，则中国必选择“不犯人”，则美国得到1；◆结果美国宁愿选择“不犯我”。照规矩，我们在美国“不犯我”的一个分枝上画上横线。●如果存在一个路径，其每个分枝都画上了横线，那么这条路径就是均衡路径。可发现，在图5-1的例子中，均衡路径将是美国选择“不犯我”，而中国选择“不犯人”。因此，美中博弈的子博弈完美均衡结果是：美国不侵犯中国，而中国也不侵犯美国。逆向归纳法对于求解子博弈完美均衡之所以适用，其原因就在于它的解过程很好地体现了子博弈完美均衡的定义：一个策略组合只有在其路．既满足是整个博弈的均衡又满足该路径上每一个子博弈的均衡时候，‘才是子博弈完美均衡。§5-2逆向归纳法的应用掌握了逆向归纳方法，现在我们就可以来看一些序贯行动博弈的例子。这些例子既充满趣味，也是对大家使用逆向归纳技术的一种训练，同时也可能是一种智力上的测试。1、私奔博弈故事模型在我国汉代，有个青年作家叫司马相如，有个年轻的寡妇叫卓文君。卓文君的父亲喜欢附庸风雅，经常请一些所谓的才子到家里吟诗作赋，其中就包括司马相如。日情，并打算结婚。但是，这门亲事遭到文君父亲的反对。父亲对文君4说，你若跟司马结婚，那么就将脱离父女关系。现在，卓文君应该怎样选择？是屈从父亲，还是跟心上人结婚？我们可用如下一个博弈（图5-3）来表示卓文君与她父亲的博弈。跟司马结婚默认文君父亲（2,－1）与司马断绝父女断绝关系关系（－1,1）（0,-2）图5-3私奔博弈图5-3的博弈中，卓文君先选择“与司马断绝关系”或者“结婚”。若与司马断绝关系，则她失去一个心爱的人，得到-1的赢利（她父亲则得到赢利1，因为他终于如愿以偿让女儿没能跟司马结婚）；若选择结婚，则由文君的父亲做出反应。他可以选择真的断绝父女关系——这种情况下，文君得到0（因为她虽然跟爱人结婚得到1，但是却因此失去了父亲得到-1，总计得到0），父亲得到是-2（因为看到文君与司马结婚心中不快得到-1，又失去了一个女儿其所得再增加-1）；当然，既然生米煮成了熟饭，父亲可以默认——此时文君既得到爱人又没有失去父亲故获得赢利2，而父亲心中不快得到-1，但毕竟没有失去女儿。使用逆向归纳法不难得到，第二阶段父亲将选择默认（因为默认的赢利为-1，而断绝父女关系的赢利为-2）；给定第二阶段父亲会默认，第一阶段文君将选择结婚（结婚赢利为2，与司马断绝关系赢利为—1）。所以，私奔博弈的均衡结果是，文君选择结婚，而文君的父亲选择默认。历史上的故事正是如此。卓文君不顾父亲的反对和司马相如私奔。两个人在成都靠开酒吧为生。文君的父亲不忍女儿受苦，最后还是接纳了他们的婚姻。私奔博弈刻画了一个很重要的道理，那就是有些时候威胁并不可怕，因为那些威胁仅仅是威胁而已。就像父母亲反对儿女婚姻时常常摆出一副要断绝父子（女）关系的样子，但一旦木已成舟，他们也只好默认，并不会真的跟儿女断绝关系。学习了博弈论的人，更容易看出这些威胁是不可置信的。52、海盗分赃再来看一个逆向归纳法的经典例子，其原型来自I．Stewart在《科学美国人》杂志上的一篇文章《凶残海盗的逻辑》。这个例子曾经被作为微软公司招募员工的面试题目，你也可以尝试着可以在几分钟之内求解出正确答案。故事模型话说有5个海盗ABCDE抢来了100枚金币，大家决定分赃的方式是：依次由海盗ABCD提出一种分配方案，如果同意这种方案的人达到半数，那么该提议就通过并付诸实施；若同意这种方案的人未达半数，则提议不能通过且提议人将被扔进大海喂鲨鱼，然后由接下来的海盗继续重复提议过程。假设每个海盗都绝顶聪明，也不相互合作，并且每个海盗都想尽可能多得到金币，那么，第一个提议的海盗将怎样提议既可以使得提议被通过又可以最大限度得到金币呢？我曾好几次在学生中做过调查，如果他们就是第一个海盗会提出怎么分？答案五花八门，但是大多数是表示平均分（每人20颗）——这可能是现实中的情况，公平观念在博弈中发挥着作用。但是标准博弈论是研究人们完全理性的情况下极端复杂的策略互动后果，这里的平均分配并不符合标准博弈论的逻辑。那么答案究竟是什么呢？使用边向归纳法可以求解如下：★首先，考虑只剩下最后的海盗E，显然他会分给自己100枚并赞成自己。★再回溯到只剩下海盗D和海盗E的决策，海盗D可以分给自己100枚并赞成自己；海盗E被分得0枚，即使反对也无用。★回到海盗C。海盗C可以分给海盗E1枚金币得到海盗E的同意；分给自己99枚，自己也同意；分给海盗D0枚，海盗D反对但无用。★回到海盗B。海盗B可以分给海盗D1枚得到海盗D同意；分给自己99枚，自己也同意；海盗C、E各分得0枚，他们会反对但反对没有用。★回到海盗A。他可以分给海盗C、E各1枚，获得海盗C、E的同意；分给自己98，自己也同意；分给海盗B、D各0枚，他们会反对但反对不起作用。因此，这个海盗分赃问题的答案是(98，0，1，0，1)：海盗A提出分给自己98枚，分给海盗B、D各O，分给C、E各1枚，该提议会被通过。因为海盗A、C、E会投赞成票。我们可以把这个逆向决策的过程用如下矩阵表达出来（如图5-4，其中画下划线的数字表示海盗对该方案投了赞成票，未加下划线对应于反对票）。如果你是海盗A，你会这样提方案吗？对于上述海盗分赃问题，我们还可以演化出不同的版本。比如说：(1)如果要求包括提议海盗在内的所有海盗过半数（超过1/2）同意才能使提议通过，那么海盗A应该怎么提方案？(2)如果要求提议海盗之外的海盗过半数同意才能6通过，那么海盗A又该怎么提方案？(3)或者海盗的数目增加到10个、100个，海盗A又怎么提方案？大家可以把这个当做练习题来做一做。分配给各位海盗的金币数目分配者海盗ABCDE海盗E100D1000C9901B99010A980101图5-4海盗分赃逆向推理过程（全部海盗半数同意即可通过）答案：变种问题(1)中，海盗A提出的分配方案是(97，0，1，2，O)或(97，0，1，0，2)；变种问题(2)中，海盗A提出的分配方案应是(97，0，1，1，1)；变种问题(3)中，大家可尝试逐渐增加海盗的数量，将会发现答案是有规律可循的。§5-3理性的局限与非理性行为逆向归纳方法是一个非常美妙的思想，但是它对人们的理性要求可能会太高。然而，也可能正因为人们的理性程度是不一样的，才有了博弈的高下之分。关于参与人理性不对称下的博弈理论研究，至今仍是博弈论研究的一个努力方向。按照博弈论大家鲁宾斯坦(A.Rubinstein)的说法：“对不同参与人的能力及形势洞察力的不对称性建模在将来的研究中将是一个吸引人的挑战。”1、序贯理性所谓序贯理性，通俗地说就是每个参与人在其每一个行动时点上都将重新优化自己的选择，并且会把自己将来会重新优化其选择这一点也纳入当前的优化决策当中。换句话说，一个具备序贯理性的参与人很清楚自己在每一个需要做出决定的时刻都需要重新对已有的决策进行优化，而且在做这种优化的时候必须把未来需要重新优化的这一事实考虑在现有的优化决策当中。显然，序贯理性下将不会有“后悔出现”——因为满足序贯理性所形成的路径，无论从后向前看，还是从前向后看，都将是一条最优的道路。那么，只凭我们在日常生活的决策中有那么多的“悔不该当初”，我们就知道其实人们常常难以达到序贯理性的要求。7为什么人们常常难以达到序贯理性的要求呢？至少有两个原因：一是人们的算计能力是有限的；二是人们的理性本身也是有限的（比如感情用事、冲动行事、冒险倾向等）。2、算计能力与策略技巧从臥理论上来说，有限的离散策略，只要其可能的结果状态是有限的，我们就可以通过逆向归纳方法，来求解出均衡路径上的策略。按照这样的一个想法，我们在下下象棋、围棋等时可能就分不出高下。因为，每个人都通过逆向归纳法已经知道如何应对每一步棋，最后大家可能永远只会下成平手。但现实中，下棋的胜负是很常见的结果。而且，我们明显发现更