博弈论与决策论

博弈论(GameTheory)与决策论（Decisiontheory）主讲人：邓光耀1、几个定义•定义1.1博弈论（GameTheory），亦名“对策论”、“赛局理论”，属应用数学的一个分支,目前在生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。博弈论主要研究公式化了的激励结构间的相互作用。是研究具有斗争或竞争性质现象的数学理论和方法。也是运筹学的一个重要学科。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。•定义1.2序贯博弈是指参与者选择策略有时间先后的博弈形式。因此，某些对局者可能率先采取行动，它是一种较为典型的动态博弈，而重复博弈则可视为一种特殊的动态博弈形式。•在序贯博弈中，先行者可能占据一定的有利地位，我们把它叫做先行者优势。•定义1.3决策论（Decisiontheory）决策论是根据信息和评价准则，用数量方法寻找或选取最优决策方案的科学，是运筹学的一个分支和决策分析的理论基础。在实际生活与生产中对同一个问题所面临的几种自然情况或状态，又有几种可选方案，就构成一个决策，而决策者为对付这些情况所取的对策方案就组成决策方案或策略。2、序贯博弈之例•例1：桌上有25枚硬币，每次可以取1枚、2枚或者3枚。你与对手交替选择，谁先选到第25枚硬币谁就胜利。假设你首先选择，你这样才能保证自己胜利？•解答：你应当这样选择：每次选择的最后一个数依次为1、5、9、13、17、21、25，这样无论对方如何选择，你均可以保证自己胜利。也就是说你要保证每次最后选择的是4n+1型的数。而这种保证是可以做到的，读者可以思考一下原因。•推广1：此类游戏可以推广到选择4k+1枚硬币的情形，优胜策略也是保证每次最后选择的是4n+1型的数。•推广2：设步长为a，（例1中步长为3），则形如（a+1)k+1枚硬币的情形，优胜策略也是保证每次最后选择的是（a+1)n+1型的数。3、囚徒困境•3.1警方逮捕甲、乙两名嫌疑犯，但没有足够证据指控二人入罪。于是警方分开囚禁嫌疑犯，分别和二人见面，并向双方提供以下相同的选择：若一人认罪并作证检控对方（相关术语称“背叛”对方），而对方保持沉默，此人将即时获释，沉默者将判监10年。若二人都保持沉默（相关术语称互相“合作”），则二人同样判监1年。若二人都互相检举（相关术语称互相“背叛”），则二人同样判监8年。•写成以下收益矩阵的情况：乙沉默乙认罪甲沉默-1,-1-10,0甲认罪0,-10-8,-8•3.2由收益矩阵可以看出双方沉默是最好的选择，这与实际中“抗拒从严，坦白从宽”的原则恰好相反。但是分析个人的选择则这个原则是正确的，对于个人来说坦白是最好的选择，当分开审理时得到的结果是双方认罪。假如罪犯懂得博弈论和互相相信对方，肯定会保持沉默。•3.3本例说明的是个人理性选择与集体理性选择的矛盾。•3.4注：（-8,-8）这一点实际上就是纳什均衡点，（-1,-1）这一点就是实现帕累托效率的那一点，但是它不是纳什均衡点。纳什均衡：（通俗定义）给定A的选择，B选择对自己最有利的策略；即给定B的选择，A选择对自己最有利的策略。这样选择得到的均衡点就是纳什均衡。帕累托效率：在没有使任何人境况变坏的前提下，也不可能再使某些人的处境变好。（即损人才能利己）4、田忌赛马•4.1齐国的大将田忌和齐威王约定，进行赛马。他们把各自的马分成上、中、下三等，每一等级的马齐威王都比田忌的强，但是田忌的上等马比齐王的中等马强，田忌的中等马比齐王下等马强，我们分析这个博弈。•4.2写成以下收益矩阵：上等马（齐王）中等马（齐王）下等马（齐王）上等马（田忌）（-1，1）（1，-1）（1，-1）中等马（田忌）（-1,1）（-1，1）（1，-1）下等马（田忌）（-1,1）（-1,1）（-1，-1）•4.3我们可以看到针对一场比赛田忌的上等马对齐王的中等马或者下等马会胜利，田忌的中等马对齐王的下等马会胜利，但是按照三局两胜制就只能按照孙膑的方法才能取得胜利了。即田忌的下等马对齐王的上等马，上等马对中等马，中等马对下等马就可以三局两胜了。•4.4本例田忌只有在齐王先选择的时候做此回应才可能取胜。•4.5此博弈为零和博弈（每次决策的和为零），无纯策略博弈纳什均衡，但是有混合策略（以概率0p1选择策略）博弈纳什均衡。5、军备竞赛•5.1美国与苏联进行军备竞赛，相互竞争生产核导弹。假设双方的收益关系可以写成以下的收益矩阵形式：苏联不生产苏联生产美国不生产4,41,3美国生产3,12,2•5.2此博弈有两个纳什均衡点（4,4）与（2,2）；但是双方不生产带来的效益比双方生产带来的效益大。如何才能达到（4,4）这一点？•5.3如果一方宣布它已经停止部署核导弹，并给予另一方充分的证据来证明它的选择，那么，另一方也会停止部署核导弹。（因为43，实际上，博弈通常情况下会自动趋向于纳什均衡点。•5.4纳什定理：每个有限策略式博弈至少拥有一种纳什均衡。（纯策略或者混合策略纳什均衡）•注：此定理的严格证明比较复杂。纳什本人因为此定理获得1994年的诺贝尔经济学奖。6、绑架博弈•6.1假设绑匪挟持人质，但是人质家里拿不出钱来赎人。如果绑匪弃放人质，但是他担心人质会泄露身份。我们思考有什么办法让绑匪放心地弃放人质。假设收益情况可以写成以下博弈树的形式：（第一项为绑匪的收益，第二项为人质的收益）绑匪选择释放杀掉（-3，-10）人质选择揭露（-5,5）人质选择不揭露（5,3）博弈树•6.2一种办法是绑匪拍写人质不雅的照片（艳照门），如果人质泄露绑匪的身份，那么绑匪可以通过发布这些照片使人质带来名誉的损失。7、敲竹杠•7.1假设你请承包商建设一个仓库，但是快建成时发现颜色不好看，这时承包商说要更改颜色可以，交1500元，可能实际成本只要200元。另外好看的颜色对于客户值1500元。如果你考虑到另请一个油漆工需要交200元，另外时间成本为1400元。那么恭喜你，你肯定愿意被敲竹杠了。具体收益可以写成以下博弈树的形式：博弈树承包商选择敲竹杠按实际要价（0,1300）客户选择让步（1300,0）另找油漆工（0，-100）•7.2解决被敲竹杠的办法：有经验的客户会通过提前在合同中注明的办法来解决。另外如果你知道某位承包商有敲竹杠的爱好，你也不会请他来承包此工程。8、圣彼得堡悖论•8.1假设你花20元去做以下游戏：设定掷出硬币的正面或者反面为成功，游戏者如果第一次投掷成功，得奖金２元，游戏结束；第一次若不成功，继续投掷，第二次成功得奖金４元，游戏结束；这样，游戏者如果投掷不成功就反复继续投掷，直到成功，游戏结束。如果第ｎ次投掷成功，得奖金元，游戏结束。这样做值得吗？•8.2照数学期望的计算方法，将每一个可能结果的得奖值乘以该结果发生的概率即可得到该结果奖值的期望值。游戏的期望值即为所有可能结果的期望值之和。随着ｎ的增大，以后的结果虽然概率很小，但是其奖值越来越大，每一个结果的期望值均为1，所有可能结果的得奖期望值之和，即游戏的期望值，将为“无穷大”。按照概率的理论，多次试验的结果将会接近于其数学期望。但是实际的投掷结果和计算都表明，多次投掷的结果，其平均值最多也就是几十元。n2•8.3利用电脑进行模拟试验的结果说明，实际试验的平均值—样本均值是随着实验次数的增加而变化的。在大量实验以后，其实验均值X可以近似表示为X≈logn/log2，可见当实验次数趋向无穷大的时候，样本均值也趋向无穷大。比如100万即次实验的平均值约等于6/0.301=19.9，即20元左右。•8.4虽然这个游戏在原理上是公平的，但是几乎没有人有时间去做100万次以上的这种抛硬币游戏，故花20元去做此游戏是不值得的。当然，你有足够的精力去做这件事，还是可以赚钱的。610•8.5丹尼尔·伯努利对这个悖论的解答在１７３８年的论文里，提出了效用的概念以挑战以金额期望值为决策标准，论文主要包括两条原理：•１、边际效用递减原理：一个人对于财富的占有多多益善，即效用函数一阶导数大于零；随着财富的增加，满足程度的增加速度不断下降，效用函数二阶导数小于零。•２、最大效用原理：在风险和不确定条件下，个人的决策行为准则是为了获得最大期望效用值而非最大期望金额值。•Thankyouverymuch!