第8讲博弈论动态策略

博弈论GameTheory蔡树彬[e-mail]13510646162（66162）科技楼14062动态博弈(序贯博弈)的概念Dynamicgame（Sequentialgame）•一类博弈行为通常需要参与人多步决策才能完成，具有明显的阶段性。•博弈的结局、各参与人的支付值由多阶段决策结果确定。•各参与人的决策有一定的顺序。3海盗分赃－逆向归纳案例5个海盗抢来了100枚金币，大家决定分赃的方式是：由海盗一提出一种分配方案，如果同意该方案的人达到半数，则该提议通过并实施；否则，提议人将被扔进大海喂鲨鱼。然后由接下来的海盗继续重复提议过程。假设每个海盗都绝顶聪明，也不相互合作，并且极度自私，那么第一个海盗该如何提议？4博弈树•101个分枝•总共有101的5次方这么多个分支•10#2×5=10#10百亿分支•如何使用逆向归纳法？5海盗分赃－逆向归纳案例使用逆向归纳法可以求解如下：•首先，考虑只剩下最后的海盗五，显然他会分给自己100枚，并赞成自己；•再回溯到只剩下海盗四和海盗五的决策，海盗四可以分给自己100枚并赞成自己；海盗五被分得0枚，即使反对也无用；•画出这里的博弈树和支付分析6海盗分赃－逆向归纳案例•回到海盗三，海盗三可以分给海盗五1枚得到海盗五的同意；分给自己99枚，自己也同意；分给海盗四0枚，海盗四反对但无用；•回到海盗二，海盗二可以分给海盗四1枚得到海盗四同意；分给自己99枚，自己也同意；海盗三、五各分得0枚，他们会反对但反对没有用7海盗分赃－逆向归纳案例•回到海盗一，他可以分给海盗三、五各1枚，获得海盗三、五的同意；分给自己98，自己也同意；分给海盗二、四各0枚，他们会反对但反对不起作用。8海盗分赃－逆向归纳案例•因此，这个海盗分赃问题的答案是（98,0,1,0,1）：海盗一提出分给自己98枚，分给海盗二、四各0枚，分给三、五个1枚；该提议会被通过，因为海盗一、三、五会投赞成票。我们可以把这个逆向决策的过程用如下矩阵表达出来（下图，其中画下划线的数字表示海盗对该方案投了赞成票，未加下划线对应于反对票）9海盗分赃－逆向归纳案例•海盗分赃逆向推理过程(全部海盗半数同意即可通过)•分配者分配给各海盗的金币枚数•海盗一海盗二海盗三海盗四海盗五•海盗五100•海盗四1000•海盗三9901•海盗二99010•海盗一98010110海盗分赃－逆向归纳案例思考：1，如果有100个海盗分，怎么办？2.如果有200个海盗分，怎么办？3.如果有500个海盗分，怎么办4.如果规则改为超过半数通过，怎么提议？5，如果规则改为除了提议人之外的海盗超过半数通过，怎么提议？11扩展型表示（博弈树）阶段：动态博弈中一个博弈方的一次选择行为乙甲（0，4）（2，2）（1，0）不借借分不分开金矿博弈委托-代理模型乙是委托人甲是代理人12委托-代理模型乙甲（0，4）（2，2）（1，0）不借借分不分开金矿博弈本来可以达成（2，2），大家都好，但是最终只能达到（1，0）类似囚徒困境相机选择(ContigentPlay)：不管之前的计划是什么，博弈方在实际的博弈中都可以改变策略，以达到自己的最大收益原因在于甲对于乙的“分”的承诺不可信（Credibility），当甲借到钱后，最好的选择是不分，所以无法达成（借，分）乙甲分不分借(2,2)(0,4)不借(1,0)(1,0)13MoralHazard道德风险•代理倾向于做一些伤害投资人的事情•人的天性（理性）•基金•家族企业的接班人问题•中石化天价酒•…14如何避免损失？•道德约束----职业经理，信托责任•立法------解决有限•对资金的用途进行限制----不灵活（发票报销）•监管资金------相当于让p2先行动（第3方监管，淘宝）•分阶段发放----重复博弈•担保---不是为了使lender觉得资金安全，而是减少借方不还钱时的收益•重新设计payoff–激励设计15可信性不借乙甲乙借不分分（1，0）不打打（0，4）（1，0）（2，2）有法律保障的开金矿博弈乙甲分不分借打(2,2)(1,0)借不打(2,2)(0,4)不借(1,0)(1,0)16乙甲乙打（2，2）不分分不借借（0，4）（-1，0）不打（1，0）法律保障不足的开金矿博弈此时，（借打，分）不是一个均衡乙的打是一个不可信(incredible)的空头威胁(EmptyThreats)乙甲分不分借打(2,2)(-1,0)借不打(2,2)(0,4)不借(1,0)(1,0)173.2.2纳什均衡的问题注意第三种开金矿博弈中有两个纳什均衡：（不借-不打，不分）和（借-打，分）两个都合理吗？•纳什均衡在动态博弈可能缺乏稳定性，也就是说，在完全信息静态博弈中有稳定性的纳什均衡在动态博弈中可能是不稳定的。不能作为预测的基础。•根源在于它不能排除博弈方策略中所包含的不可信的行为设定，不能解决动态博弈的相机选择引起的可信性问题183.3子博弈和子博弈完美纳什均衡3.3.1子博弈•定义：由一个动态博弈第一阶段以外的某阶段开始的后续博弈阶段构成的，有初始信息集和进行博弈所需要的全部信息，能够自成一个博弈的原博弈的一部分，称为原动态博弈的一个“子博弈”乙甲不借借不分分（1，0）（0，4）（2，2）乙（-1，0）19•子博弈1的Nash均衡：乙不打•子博弈2的Nash均衡：（乙打甲分）（甲不分乙不打）–子博弈2的子博弈Nash均衡：（甲不分乙不打）•（借打，分）不是子博弈的Nash均衡，从而也不是整个博弈的子博弈Nash均衡乙甲不借借不分分（1，0）（0，4）（2，2）乙（-1，0）乙甲分不分打(2,2)(-1,0)不打(2,2)(0,4)203.3.2子博弈完美纳什均衡•定义：如果在一个完美信息的动态博弈中，各博弈方的策略构成的一个策略组合满足，在整个动态博弈及它的所有子博弈中都构成纳什均衡，那么这个策略组合称为该动态博弈的一个“子博弈完美纳什均衡”。•子博弈完美纳什均衡能够排除均衡策略中不可信的威胁和承诺，因此是真正稳定的。•逆推归纳法是求完美信息动态博弈子博弈完美纳什均衡最基本的方法。213.2.3逆推归纳法•定义：从动态博弈的最后一个阶段博弈方的行为开始分析，逐步倒推回前一个阶段相应博弈方的行为选择，一直到第一个阶段的分析方法，称为“逆推归纳法”。乙不借借（1，0）甲不分分（0，4）（2，2）22沉船博弈23•有时候过多选择反而带来不好的结果•釜底抽薪，背水一战，置之死地而后生•信息的传递：必须将烧船的信息传递给对方•对另一方来说，有时候过多信息反而不好（无知者无畏）2425•什么情况下原告会接受和解？什么时候原告会一直打官司？26•Rxp原告会起诉(胜诉得到的赔偿大于起诉成本)–哪怕R很小，可以让x很高（比如烟草案中索价3亿，比如苹果败诉要支付上百亿的罚款）–Srx+d被告上法庭（原告狮子大开口，和解费太高，高于法院判决的金额）–Srx+d被告接受和解（原告和解费不太高，被告花钱买平安，息事宁人）•Rxp原告放弃起诉–得不偿失–如果rxp原告该如何做？如何破釜沉舟？•预先支付律师费p，这样原告放弃的支付也为-c-p，原告一定上诉。这时候如果原告s=rx+d，则被告和解2728•美国的诉棍–麦当劳“小心地滑”–万宝路“吸烟有害健康”–Google“linux专利”–Google收购北电专利–桑兰•为什么中国没有诉棍？–R太小，x太少，p太高29303132为什么我们民族越来越没有道德底线？•美国的打假•中国的唐骏•事后惩罚机制•不知惩罚当事人，还有纵容着（不能只罚小偷）33抢10游戏•由两个人玩“抢10”的游戏，游戏规则是这样的：–第一个先说“1”或“1、2”或者“1、2、3”，–第二个人再接着往下说一个或两个数或三个数，–然后轮到第一个人，再接着往下说。这样两人反复轮流，每次每人说一个或两个数或3个数都可以，但是不可以连说4个数，–谁先抢到10，谁就获胜．•谁会获胜？为什么？35红黑树112122121213151623342331441751819451106216217782189213214672158210211572126242534265...1221231011124121191209101201111611710811892131wins2182wins1.博弈树与逆向归纳法:正向搜索，逆向归纳2.列出所有可能的情况，画出博弈树3.确定在每个叶子节点，谁会获胜，向前类推36状态空间爆炸112122121213151623342331441751819451106216217782189213214672158210211572126242534265...1221231011124121191209101201111611710811892131wins2182wins1.图中一共有多少个叶子节点？（多少条路？）估算：最少走四步，最多走10步（3^4m3^10）7，8，9：36：95：9+3+3=154：15+9+3=273：27+15+9=512：51+27+15=931：93+51+27=1710：171+93+51=315斐波纳切数列路径数随着n的增大为指数级增长计算上有难度37如何优化（1）：广度搜索与剪枝112122121213151623342331441751819451106216217782189213214672158210211572126242534265...1221231011124121191209101201111611710811892131wins2182wins实际上不需要走所有的路使用广度优先搜索树标记胜利节点，剪枝人工智能38如何优化（2）：关键点法逆推11062162177821891221231011124121191209101201111611710811892131wins2182wins为了保证数到10，必须数到6“谁先数到10就赢”=》转化为“谁先数到6就赢”以此类推39抢100游戏•由两个人玩“抢100”的游戏，游戏规则是这样的：–每个人可以数1-9，–谁先抢到100，谁就获胜．–谁会获胜？为什么？•抢n游戏，每个人可以数1-k，谁会获胜？40抢100游戏•由两个人玩“抢100”的游戏，游戏规则是这样的：–每个人可以数2-9–每步的数字为乘积，而不是加和–谁先抢到100，谁就获胜．•谁会获胜？为什么？•抢n游戏，每个人可以数1-k，谁会获胜？41•选择某一个点，同时一走该点上方和右方的石子•双方轮流移走石子•移走最后一个石子的人输42拿石子游戏•有一堆石子共25颗，两人轮流从中拿石子。规则是：•（1）掷硬币决定谁先拿；•（2）每人每次可以从中拿1~3颗，不能不拿，也不能多拿；•（3）拿到最后一颗的人输。43•有n堆石子，将这n堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。•比如：三堆石头，16，12，5•应该如何取？谁会获胜？44讨价还价博弈•给你100万，你愿意今天要这个钱还是明天（10年后）要这个钱？Why？•今天的钱并不等于明天的钱：利率•明天的钱并不等于今天的钱：贴现率45贴现率•将未来资产折算成现值(presentvalue)的利率，一般是用当时零风险的利率来当作贴现率，但并不是绝对。•举个例子：贴现率为10%，明年的100块在今年就相当于100/（1+10%）=90.909090...块钱，到了去年就是100/（1+10%）*（1+10%），也就是说，今年用90.909090...块可以买到的东西相当于明年100块可以买到的东西。•今天投资100万元的项目，将来如能收回200万，也不能证明此项投资一定有效。因为如果这回收的200万要等50年之后，今天衡量的价值就远低于100万。这是由于如果利率是3%，100万元存银行，50年内得到的利息也将达338