幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

驿易
5 years ago
Views:

1 第四讲 : 博弈的基本分析方法 ( 上 ) 吴建设

2 基本分析思路和方法 1 上策均衡 2 严格下策反复消去法 3 划线法 4 箭头法

3 1 上策均衡上策 : 不管其它博弈方选择什么策略, 一博弈方的某个策略给他带来的得益始终高于他的其它的策略, 至少不低于其他策略的策略大猪待对任意的智猪博弈中的小猪等待 ; 囚徒的困境中的坦白 ; 双寡头削价中低价按等待 u s s ' i( i, i) ui ( si, s i ), 小猪按等 5, 1 4, 4 9, -1 0, 0 s D ' i C S i, s ' i s, i D C

4 1 上策均衡上策均衡 : 一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策, 必然是该博弈比较稳定的结果上策均衡不是普遍存在的上策均衡肯定是纳什均衡, 但纳什均衡不一定是上策均衡按小猪等待 D C 大猪按等待 5, 1 4, 4 9, -1 0, 0 D C

5 2 严格下策反复消去法严格下策 : 不管其它博弈方采用哪一个策略, 某一给一个博弈方带来的收益总是比另一种策略给他带来的收益小的策略 u s s ' i( i, i) ui ( si, s i ), 严格下策反复消去 : 对任意的 s i, s ' i S i, s ' i s, i 左中右左中左中上 1,0 1,3 0,1 1,0 1,3 1,0 1,3 下 0,4 0,2 2,0 0,4 0,2

6 纳什均衡与严格下策反复消去法命题 1: 在 n 个博弈方的博弈 G 策反复消去法排除了除命题 2: 在 n 个博弈方的博弈中 G * ( s, * ( s, * i s n * i s n ) 是 ) G { S, Sn; u1, u * ( s, * i s n 1 n 一定是该博弈的唯一的纳什均衡 } 中, 如果严格下 ) 之外的所有策略组合, 那么 { S, Sn; u1, u 1 n 中, 如果的一个纳什均衡, 那么严格下策反复消去法一定不会将它消去上述两个命题保证在进行纳什均衡分析之前先通过严格下策反复消去法简化博弈是可行的 }

7 纳什均衡与严格下策反复消去法弱下策 : 不管其它博弈方采用哪一个策略, 某一策略给一个博弈方带来的收益总是比另一种策略给他带来的收益小, 至多相等的策略 u s s ' i( i, i) ui ( si, s i ), ' 对任意的 s i, si 弱下策能不能消去 : 俾斯麦海战 1943 年, 日本海军上将木村受命将日本陆军运抵新几内亚, 期间要穿越俾斯麦海而美国海军上将肯尼欲对日本船队进行轰炸穿越俾斯麦海到新几内亚有两条线路 : 较短的北线和较长的南线木村必须选择一条线路, 而肯尼也必须选择一条 S i, s ' i s, i

8 纳什均衡与严格下策反复消去法弱下策能不能消去 : 俾斯麦海战 ( 续 ) 线路去搜索日军如果肯尼将飞机派往错误的线路, 召回需要时间, 轰炸时间会少几天对木村来说, 南线是弱下策对肯尼来说, 他知道南线是木村的弱下策, 因此他也选择北线, 当年就是这么发生的但是, 如果木村知道肯尼要选择北线, 肯尼北线南线木村北线南线 2,-2 2,-2 1,-1 3,-3 他也可能选南线,( 北线, 南线 ) 也可能为最后结果

9 3 划线法给定其它参与人的策略, 对当事参与人在每一种策略进行比较, 在最好的策略下划线最后, 所有策略均划线的策略组合是纳什均衡例子左中右上下 1, 0 1, 3 0, 1 0, 4 0, 2 2, 0 1, 0 1, 3 0, 1 0, 4 0, 2 2, 0

10 3 划线法夫妻之争是一个经典博弈问题一对夫妻得到了两张时装表演票和同一时间的两张足球比赛票妻子更想去看时装表演而丈夫更想去看足球比赛, 但又不愿或不能分头行动, 争执不下就决定双方投票一次决定若同选时装则去看时装表演, 同选足球则去看足球比赛, 如选择不一致则哪儿都不去再假设若丈夫与妻子同去看时装表演, 妻子得益 2 单位, 丈夫得益 1 单位 ; 若丈夫与妻子同去看足球比赛则丈夫得益 3 单位, 妻子得益 1 单位 ; 若因为双方选择不同而没有出门则双方得益都为 0 单位, 夫妻之争妻子时装足球时装 2, 1 0, 0 丈夫足球 0, 0 1, 3 2, 1 0, 0 0, 0 1, 3

11 3 划线法 ( 自己练习 ) 囚徒困境 D C D C -5, -5 0, -8-8, 0-1, -1 囚徒困境 D C D C -5, -5 0, -8-8, 0-1, -1 猜硬币 -1, 1 1, -1 1, -1-1, 1 猜硬币 -1, 1 1, -1 1, -1-1, 1 夫妻之争 2, 1 0, 0 0, 0 1, 3 夫妻之争 2, 1 0, 0 0, 0 1, 3

12 4 箭头法方法描述 : 对每一种策略组合, 用箭头标出其转移的方向, 没有箭头指向外面的策略组合即为纳什均衡例 1 1, 0 1, 3 0, 1 0, 4 0, 2 2, 0 1, 0 1, 3 0, 1 0, 4 0, 2 2, 0

13 4 箭头法其它例子囚徒困境 -5, -5 0, -8-8, 0-1, -1 夫妻之争 2, 1 0, 0 0, 0 1, 3 猜硬币 -1, 1 1, -1 1, -1-1, 1

14 混合策略博弈的纳什均衡 1 混合策略的引进 2 多重均衡博弈和混合策略 3 混合策略和严格下策反复消去法 4 混合策略反应函数

15 一猜硬币博弈 1 混合策略的引进猜硬币方盖硬币方正面反面正面反面 -1, 1 1, -1 1, -1-1, 1 (1) 不存在前面定义的纳什均衡策略组合 (2) 关键是不能让对方猜到自己策略这类博弈很多, 引出混合策略纳什均衡概念

16 二混合策略混合策略博弈和混合策略纳什均衡混合策略 : 在博弈 G { S1, Sn; u1, un} 中, 博弈方 i 的策略空间为 S i { s i1, s ik }, 则博弈方 i 以概率分布 pi ( pi 1, pik) 随机在其 k 个可选策略中选择的策略, 称为一个混合策略, 其中 0 p ij 1 对 j 1,, k 都成立, 且 pi 1 pik 1 混合策略扩展博弈 : 博弈方在混合策略的策略空间 ( 概率分布空间 ) 的选择看作一个博弈, 就是原博弈的混合策略扩展博弈 ) 混合策略纳什均衡 : 包含混合策略的策略组合, 构成的纳什均衡

17 三一个例子 : 警察与小偷某个小镇上只有一名警察, 他负责整个镇的治安现在我们假定, 小镇的一头有一家酒馆, 另一头有一家银行再假定该地只有一个小偷因为分身乏术, 警察一次只能在一个地方巡逻 ; 而小偷也只能去一个地方若警察选择了小偷偷盗的地方巡逻, 就能把小偷抓住 ; 而如果小偷选择了没有警察巡逻的地方偷盗, 就能够偷窃成功假定银行需要保护的财产价格为 2 万元, 酒馆的财产价格为 1 万元警察怎么巡逻才能使效果最好? 一种最容易被警察采用而且确实也更为常见的做法是, 警察对银行进行巡逻这样, 警察可以保住 2 万元的财产不被偷窃但是假如小偷去了酒馆, 偷窃一定成功这种做法是警察的最好做法吗?

18 三一个例子 : 警察与小偷收益均等化方法 : 在纳什均衡状态, 每个参与人使用某一种策略得到的收益必须与他使用另一种策略得到的收益相同以警察与小偷为例, 如果小偷使用混合策略, 他去银行的收益高于他去酒馆的收益, 那他就会增加去银行的概率, 直到去银行和去酒馆收益相等警察酒馆银行小偷酒馆银行 0, 3 1, 2 2, 1 0, 3

19 三例 1: 警察与小偷警察的混合策略计算 : 使小偷在两种策略下收益相等小偷 p ( J) 0 p ( Y) 1 p ( J) 2 p ( Y) 0 J J J J 小偷在酒馆的收益 = 小偷在银行的收益酒馆银行酒馆警察银行 0, 3 1, 2 2, 1 0, 3 p ( Y) 2 / 3 p ( J) 1/ 3 J J 小偷的混合策略计算 : 使警察在两种策略下收益相等 p ( J) 3 p ( Y) 1 p ( J) 2 p ( Y) 3 X X X X p ( Y) 1/ 3 p ( J) 2 / 3 X X 警察在酒馆的收益 = 警察在银行的收益

20 三例 2 该博弈无纯策略纳什均衡, 可用混合策略纳什均衡分析博弈方 1 的混合策略 : 使博弈方 2 在两种策略下收益相等 p ( A) 3 p ( B) 1 p ( A) 2 p ( B) 可得 p 1 (A) 与 p 1 (B) 的比例, 再由 p 1(A)+ p 1(B) =1, 得 (p 1(A), p 1(B) )=(0.8, 0.2) 博弈方 2 的混合策略 : 使博弈方 1 在两种策略下收益相等 p C 2 p 5 p 3 p 1 D C D 博弈方 1 A B C 博弈方 2 D 2, 3 5, 2 3, 1 1, 5 策略得益博弈方 1 (0.8,0.2) 2.6 博弈方 2 (0.8,0.2) 2.6 如果在某时刻, 博弈方 2 在取策略 C 时的收益大于 D, 那他一定会增加取 C 的概率, 直至取两种策略的收益相等, 或变成纯策略 ( 只取 C)

21 2 多重均衡博弈和混合策略一夫妻之争的混合策略纳什均衡妻子时装 C 足球 F 丈夫时装 C 足球 F 2, 1 0, 0 0, 0 1, 3 妻子的混合策略 p w ( C) 1 p ( F) 0 p ( C) 0 p ( F) 3 w 丈夫的混合策略 p h ( C) 2 p ( F) 0 p ( C) 0 p ( F) 1 h w h w h 夫妻之争夫妻之争博弈的混合策略纳什均衡策略得益妻子 (0.75,0.25) 0.67 丈夫 (1/3,2/3) 0.75

22 2 多重均衡博弈和混合策略混合策略可以优于纯策略, 或不劣于纯策略妻子时装 C 足球 F 丈夫时装 C 足球 F 2, 1 0, 0 0, 0 1, 3 夫妻之争夫妻之争博弈的混合策略纳什均衡策略得益妻子 (0.75,0.25) 0.67 丈夫 (1/3,2/3) 0.75

23 二制式问题 A 厂商 2 B 厂商 1 A B 1, 3 0, 0 0, 0 2, 2 制式问题制式问题混合策略纳什均衡 A B 得益厂商 1: 厂商 2:

24 课堂练习借钱的例子 : 策略 A 表示只向别人借, 策略 B 表示只借给别人混合策略纳什均衡是什么? 博弈方 2 B A 博弈方 1 A B

25 三小偷和守卫的博弈守卫 ( 睡觉 ) 的收益 ) 守卫 S 小偷偷不偷睡不睡 V,-D -P,0 0,S 0, D Pt 小偷偷的概率 - D 加重对守卫的处罚 : 短期中的效果是使守卫真正尽职在长期中并不能使守卫更尽职, 但会降低盗窃发生的概略

26 小偷 ( 偷 ) 的得益守卫 V 睡不睡小偷偷不偷 V,-D -P,0 0,S 0,0 0 - P 1 Pg 守卫睡的概率 - P 加重对小偷的处罚 : 短期内能抑制盗窃发生率长期并不能降低盗窃发生率, 但会使得守卫更多的偷懒

27 四市场机会博弈进厂商 2 不进厂商 1 进不进 -50, ,0 0,100 0,0 市场机会进不进得益厂商 1: 2/3 1/3 0 厂商 2: 2/3 1/3 0

28 作业 1. 严格劣势策略与弱劣势策略 : 严格劣势策略的定义是什么? 弱劣势策略的定义是什么? 请用一个包含两个参与人的博弈矩阵来举例说明, 要求其中一个参与人有三个策略且三者之一为严格劣势策略 ; 另一个参与人有三个策略但三者之一为弱劣势策略请指出你所举例子中的劣势策略

29 作业 2. 迭代剔除 ( 弱 ) 劣势策略 : 请看下面的博弈 (a). 这个博弈中是否存在严格劣势策略和弱劣势策略? 如果存在, 请指出并说明 (b). 剔除掉严格劣势策略和弱劣势策略之后, 在简化的博弈中是否还有劣势策略呢? 如果是, 请指出并说明最后哪些策略不会被剔除呢? (c). 回顾你第一次剔除劣势策略时哪些策略是劣势策略并给出解释把它与第二次剔除的劣势策略作比较从中你能得出关于迭代剔除劣势策略的何种结论?

幻灯片 1

幻灯片 1 第四讲 : 博弈的基本分析方法吴建设基本分析思路和方法上策均衡 2 严格下策反复消去法 3 划线法 4 箭头法上策均衡上策 : 不管其它博弈方选择什么策略, 一博弈方的某个策略给他带来的得益始终高于其它的策略, 至少不低于其他策略的策略智猪博弈中的小猪等待 ; 囚徒的困境中的坦白 ; 双寡头削价中低价上策均衡 : 一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策, 必然是该博弈比较稳定的结果