《第8讲博弈论动态策略》由会员分享，可在线阅读，更多相关《第8讲博弈论动态策略（71页珍藏版）》请在金锄头文库上搜索。
1、蔡树彬（66162）科技楼14062动态博弈(序贯博弈)的概念Dynamicgame（Sequentialgame）一类博弈行为通常需要参与人多步决策才能完成，具有明显的阶段性。博弈的结局、各参与人的支付值由多阶段决策结果确定。各参与人的决策有一定的顺序。3海盗分赃逆向归纳案例5个海盗抢来了100枚金币，大家决定分赃的方式是：由海盗一提出一种分配方案，如果同意该方案的人达到半数，则该提议通过并实施；否则，提议人将被扔进大海喂鲨鱼。然后由接下来的海盗继续重复提议过程。假设每个海盗都绝顶聪明，也不相互合作，并且极度自私，那么第一个海盗该如何提议？4博弈树101个分枝总共有101的5次方这么多个分支
2、10#25=10#10百亿分支如何使用逆向归纳法？5海盗分赃逆向归纳案例使用逆向归纳法可以求解如下：首先，考虑只剩下最后的海盗五，显然他会分给自己100枚，并赞成自己；再回溯到只剩下海盗四和海盗五的决策，海盗四可以分给自己100枚并赞成自己；海盗五被分得0枚，即使反对也无用；画出这里的博弈树和支付分析6海盗分赃逆向归纳案例回到海盗三，海盗三可以分给海盗五1枚得到海盗五的同意；分给自己99枚，自己也同意；分给海盗四0枚，海盗四反对但无用；回到海盗二，海盗二可以分给海盗四1枚得到海盗四同意；分给自己99枚，自己也同意；海盗三、五各分得0枚，他们会反对但反对没有用7海盗分赃逆向归纳案例回到海盗一，他
3、可以分给海盗三、五各1枚，获得海盗三、五的同意；分给自己98，自己也同意；分给海盗二、四各0枚，他们会反对但反对不起作用。8海盗分赃逆向归纳案例因此，这个海盗分赃问题的答案是（98,0,1,0,1）：海盗一提出分给自己98枚，分给海盗二、四各0枚，分给三、五个1枚；该提议会被通过，因为海盗一、三、五会投赞成票。我们可以把这个逆向决策的过程用如下矩阵表达出来（下图，其中画下划线的数字表示海盗对该方案投了赞成票，未加下划线对应于反对票）9海盗分赃逆向归纳案例海盗分海盗分赃逆向推理逆向推理过程程(全部海盗半数同意即可通全部海盗半数同意即可通过)分配者分配给各海盗的金币枚数海盗一海盗二海盗三海盗四海盗
4、五海盗五100海盗四100 0海盗三99 01海盗二99 01 0海盗一98 01 0110海盗分赃逆向归纳案例思考：1，如果有100个海盗分，怎么办？2.如果有200个海盗分，怎么办？3.如果有500个海盗分，怎么办4.如果规则改为超过半数通过，怎么提议？5，如果规则改为除了提议人之外的海盗超过半数通过，怎么提议？11扩展型表示（博弈树）阶段：动态博弈中一个博弈方的一次选择行为乙甲（0，4）（2，2）（1，0）不借借分不分开金矿博弈委托委托-代理模型代理模型乙是委托人乙是委托人甲是代理人甲是代理人12委托-代理模型乙甲（0，4）（2，2）（1，0）不借借分不分开金矿博弈q本来可以达成（2，2
5、），大家都好，但是最终只能达到（1，0）类似囚徒困境q相机选择(Contigent Play)：不管之前的计划是什么，博弈方在实际的博弈中都可以改变策略，以达到自己的最大收益q原因在于甲对于乙的“分”的承诺不可信（Credibility），当甲借到钱后，最好的选择是不分，所以无法达成（借，分）乙甲分不分借(2,2)(0,4)不借(1,0)(1,0)13MoralHazard道德风险代理倾向于做一些伤害投资人的事情人的天性（理性）基金家族企业的接班人问题中石化天价酒14如何避免损失？道德约束-职业经理，信托责任立法-解决有限对资金的用途进行限制-不灵活（发票报销）监管资金-相当于让p2先行动（第
6、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
7、)173.2.2纳什均衡的问题注意第三种开金矿博弈中有两个纳什均衡：（不借-不打，不分）和（借-打，分）两个都合理吗？纳什均衡在动态博弈可能缺乏稳定性，也就是说，在完全信息静静态博弈中有博弈中有稳定性定性的纳什均衡在动态博弈中可能可能是不稳定的。不能作为预测的基础。根源在于它不能排除博弈方策略中所包含的不可信的行为设定，不能解决动态博弈的相机选择引起的可信性问题183.3子博弈和子博弈完美纳什均衡3.3.1子博弈定义：由一个动态博弈第一阶段以外的某阶段开始的后续博弈阶段构成的，有初始信息集和进行博弈所需要的全部信息，能够自成一个博弈的原博弈的一部分，称为原动态博弈的一个“子博弈”乙甲不借借不分
8、分（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子博弈完美纳什均衡定义：如果在一个完美信息的动态博弈中，各博弈方的策略构成的一个策略组合满足，在整个动态博弈及它的所有子博弈中都构成纳什均衡，那么这个策略组合称为该动态博弈的一个“子博弈完美子博弈完美纳什均衡什均衡
9、”。子博弈完美纳什均衡能够排除均衡策略中不可信的威胁和承诺，因此是真正稳定的。逆推归纳法是求完美信息动态博弈子博弈完美纳什均衡最基本的方法。213.2.3逆推归纳法定义：从动态博弈的最后一个阶段博弈方的行为开始分析，逐步倒推回前一个阶段相应博弈方的行为选择，一直到第一个阶段的分析方法，称为“逆推归纳法”。乙不借借（1，0）甲不分分（0，4）（2，2）22沉船博弈23有时候过多选择反而带来不好的结果釜底抽薪，背水一战，置之死地而后生信息的传递：必须将烧船的信息传递给对方对另一方来说，有时候过多信息反而不好（无知者无畏）2425什么情况下原告会接受和解？什么时候原告会一直打官司？26Rxp原告会起
10、诉(胜诉得到的赔偿大于起诉成本)哪怕R很小，可以让x很高（比如烟草案中索价3亿，比如苹果败诉要支付上百亿的罚款）Srx+d被告上法庭（原告狮子大开口，和解费太高，高于法院判决的金额）Srx+d被告接受和解（原告和解费不太高，被告花钱买平安，息事宁人）Rxp原告放弃起诉得不偿失如果rxp原告该如何做？如何破釜沉舟？预先支付律师费p，这样原告放弃的支付也为-c-p，原告一定上诉。这时候如果原告s=rx+d，则被告和解2728美国的诉棍麦当劳“小心地滑”万宝路“吸烟有害健康”Google“linux专利”Google收购北电专利桑兰为什么中国没有诉棍？R太小，x太少，p太高29303132为什么我们
11、民族越来越没有道德底线？美国的打假中国的唐骏事后惩罚机制不知惩罚当事人，还有纵容着（不能只罚小偷）33抢10游戏由两个人玩“抢10”的游戏，游戏规则是这样的：第一个先说“1”或“1、2”或者“1、2、3”，第二个人再接着往下说一个或两个数或三个数，然后轮到第一个人，再接着往下说。这样两人反复轮流，每次每人说一个或两个数或3个数都可以，但是不可以连说4个数，谁先抢到10，谁就获胜谁会获胜？为什么？35红黑树1.博弈树与逆向归纳法:正向搜索，逆向归纳2.列出所有可能的情况，画出博弈树3.确定在每个叶子节点，谁会获胜，向前类推36状态空间爆炸1.图中一共有多少个叶子节点？（多少条路？）估算：最少走四
12、步，最多走10步（34m310）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）：广度搜索与剪枝实际上不需要走所有的路使用广度优先搜索树标记胜利节点，剪枝人工智能38如何优化（2）：关键点法逆推为了保证数到10，必须数到6“谁先数到10就赢”=转化为“谁先数到6就赢”以此类推39抢100游戏由两个人玩“抢100”的游戏，游戏规则是这样的：每个人可以数1-9，谁先抢到100，谁就获胜谁会获胜？为什么？抢n
13、游戏，每个人可以数1-k，谁会获胜？40抢100游戏由两个人玩“抢100”的游戏，游戏规则是这样的：每个人可以数2-9每步的数字为乘积，而不是加和谁先抢到100，谁就获胜谁会获胜？为什么？抢n游戏，每个人可以数1-k，谁会获胜？41选择某一个点，同时一走该点上方和右方的石子双方轮流移走石子移走最后一个石子的人输42拿石子游戏有一堆石子共25颗，两人轮流从中拿石子。规则是：（1）掷硬币决定谁先拿；（2）每人每次可以从中拿13颗，不能不拿，也不能多拿；（3）拿到最后一颗的人输。43有n堆石子，将这n堆石子摆成一排。游戏由两个人进行，两人轮流操作，每次操作者都可以从一堆中取出若干颗石子，可以将那一堆
14、全部取掉，但不能不取，不能操作的人就输了。比如：三堆石头，16，12，5应该如何取？谁会获胜？44讨价还价博弈给你100万，你愿意今天要这个钱还是明天（10年后）要这个钱？Why？今天的钱并不等于明天的钱：利率明天的钱并不等于今天的钱：贴现率45贴现率将未来资产折算成现值(presentvalue)的利率，一般是用当时零风险的利率来当作贴现率，但并不是绝对。举个例子：贴现率为10%，明年的100块在今年就相当于100/（1+10%）=90.909090.块钱，到了去年就是100/（1+10%）*（1+10%），也就是说，今年用90.909090.块可以买到的东西相当于明年100块可以买到的东西
15、。今天投资100万元的项目，将来如能收回200万，也不能证明此项投资一定有效。因为如果这回收的200万要等50年之后，今天衡量的价值就远低于100万。这是由于如果利率是3%，100万元存银行，50年内得到的利息也将达338万元（利率为2%的话，50年的利息为169万元）。所以50年后回收200万的投资与存银行得利息相比不值得去做。贴现率：将来的钱现在花，把将来的钱借给现在利率：现在的钱存起来将来花，把现在的钱借给将来46二人讨价还价博弈三回合讨价还价112不接受，出S接受不接受，出S2接受出S1本博弈的本博弈的现实根根据和据和现实意意义合作博弈重复博弈47对结果的讨论48二人无限重复讨价还价博
16、弈斯塔克博格寡头博弈市场中有两个厂商。厂商1先行动，选择自身产量。厂商2观察到厂商1选择的产量后，再决策自己的产量。厂商1通常被称为领先者，厂商2通常被称为跟随者。价格P=8-Q，Q=q1+q2，成本c1=c2=2现在的博弈情况如何？蜈蚣博弈的定义假设有两名博弈参与者：参与者1和参与者2。两名参与者轮流进行决策：首先由参与者1进行决策，然后是参与者2，再次是博弈参与者1，然后是博弈参与者2，依次类推。在博弈的初始节点处，参与者1有两个策略可以选择：T和C。策略T表示结束博弈，策略C表示继续博弈。当参与者1选择策略T时，博弈结束。参与者1得到收益1，参与者2得到收益1。当参与者1选择策略C时，轮
17、到博弈参与者2进行决策。参与者2同样面临两个策略选择：策略T和策略C。当参与者2选择策略T时，博弈结束。参与者1得到收益0，参与者2得到收益3。当参与者2选择策略C时，轮到博弈参与者1进行决策。参与者1同样面临两个策略选择：策略T和策略C。如果参与者1选择策略T，那么博弈结束。参与者1得到收益2，参与者2得到收益2。如果参与者1选择策略C，那么轮到参与者2进行决策，依次类推。在蜈蚣博弈中，包含初始节点在内，共有198个博弈节点。蜈蚣博弈的支付矩蜈蚣博弈的支付矩阵v参与者1和参与者2轮流决策。v参与者1对应98个节点，参与者2也对应98个节点。v即：在奇数节点上，都是参与者1进行决策。v在偶数节
18、点上，都是参与者2进行决策。53三人罢工博弈的定义三人三人罢工博弈的博弈工博弈的博弈树三人罢工博弈的策略选择与信息员工工 2 只有一个信息集的博弈只有一个信息集的博弈树员工工 3 不能不能观察到察到员工工 2 的决策策略的决策策略员工工 3 不知道不知道员工工 1 的决策策略的决策策略员工工 3 不知道不知道员工工 1 和和员工工 2 的决策策略的决策策略三名三名员工都只有一个信息集的博弈工都只有一个信息集的博弈博弈树与静态博弈博弈树的方法不仅能表示动态博弈，还能表示静态博弈。所谓的“博弈先后顺序”，它主要是一个信息的概念，而不是一个纯时间先后的概念。用博弈用博弈树表示囚徒困境表示囚徒困境嫌疑
19、人乙嫌疑人乙坦白坦白不坦白不坦白嫌疑人甲嫌疑人甲坦白坦白（5，5）（1，10）不坦白不坦白（10，1）（2，2）无不确定性的委托代理人理论62123委托不委托接受拒绝努力偷懒R(0),0R(0),0R(E)-w(E),w(E)-ER(S)-w(S),w(S)-S无不确定性的委托代理人理论63123委托不委托接受拒绝努力偷懒0,00,012，27，1成果不确定但可监督的委托代理人理论64123委托不委托接受拒绝努力偷懒0,00,020-w(E),w(E)-E20-w(S),w(S)-S00高产0.9低产0.110-w(E),w(E)-E高产0.1低产0.910-w(S),w(S)-S成果不确定且不可监督的委托代理人理论65123委托不委托接受拒绝努力偷懒0,00,020-w(20),w(20)-E20-w(20),w(20)-S高产0.9低产0.110-w(10),w(10)-E高产0.1低产0.910-w(10),w(10)-S0选择报酬和连续努力水平的委托代理人模型解读P139-142的例子66制造商与销售商的博弈67制造商与销售商的博弈分别得到2个人的收益函数68制造商与销售商的博弈制造商的应如何定价？69制造商与销售商的博弈制作商的定价70制造商与销售商的博弈71
