幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

窗秋
5 years ago
Views:

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

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

3 上策均衡上策 : 不管其它博弈方选择什么策略, 一博弈方的某个策略给他带来的得益始终高于其它的策略, 至少不低于其他策略的策略智猪博弈中的小猪等待 ; 囚徒的困境中的坦白 ; 双寡头削价中低价上策均衡 : 一个博弈的某个策略组合中的所有策略都是各个博弈方各自的上策, 必然是该博弈比较稳定的结果上策均衡不是普遍存在的上策均衡肯定是纳什均衡, 但纳什均衡不一定是上策均衡

4 2 严格下策反复消去法严格下策 : 不管其它博弈方的策略如何变化, 某一给一个博弈方带来的收益总是比另一种策略给他带来的收益小的策略严格下策反复消去 : 左中右左中左中上,0,3 0,,0,3,0,3 下 0,4 0,2 2,0 0,4 0,2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25 3 混合策略的严格下策反复消去法无论博弈方 2 采用 L 或 R, 对博弈方来说, 策略 D 都是严格下策 L 博弈方 2 R 博弈方 2 采用纯策略 L 时, 博弈方采用混合策略 (/2,/2,0) 的得益博弈方 U M D 3, 0, 2 0, 2 3,, 3, u e 博弈方 2 采用纯策略 R 时, 博弈方采用混合策略 (/2,/2,0) 的得益 3 2 u e

26 4 混合策略反应函数猜硬币方 r 盖硬币方反应函数 : r R( q) 盖硬币方正面反面正面反面 -,, -, - -, 猜硬币博弈 /2 r : 盖硬币方选择正反面的概率 q : 猜硬币方选择正反面的概率 /2 (r, -r): 盖硬币方选择正反面的混合策略概率分布 (q, -q): 猜硬币方选择正反面的混合策略概率分布 q

27 4 混合策略反应函数猜硬币方反应函数 : 猜硬币方 r q R2( r) 盖硬币方正面反面正面 -,, - 反面, - -, /2 猜硬币博弈 r : 盖硬币方选择正反面的概率 q : 猜硬币方选择正反面的概率 /2 (r, -r): 盖硬币方选择正反面的混合策略概率分布 (q, -q): 猜硬币方选择正反面的混合策略概率分布 q

28 4 混合策略反应函数两个函数合在一张图猜硬币方 r r R( q) 盖硬币方正面反面正面 -,, - 反面, - -, /2 q R2( r) 猜硬币博弈 r : 盖硬币方选择正反面的概率 q : 猜硬币方选择正反面的概率 /2 (r, -r): 盖硬币方选择正反面的混合策略概率分布 (q, -q): 猜硬币方选择正反面的混合策略概率分布 q

29 夫妻之争博弈丈夫 r 时装足球 3/4 q R 2 ( r) 妻时装子足球 2, 0, 0 0, 0, 3 夫妻之争 /3 r R ( r) (r,-r): 丈夫的混合策略概率分布 (q,-q): 妻子的混合策略概率分布 q r 为丈夫选择足球的概率 q 为妻子选择足球的概率

30 5 纳什均衡的存在性纳什定理 : 在一个由 n 个博弈方的博弈 S G { S, Sn; u, un} 中, 如果 n 是有限的, 且都是有限集时 ( i, n i ), 则该博弈至少存在一个纳什均衡, 但可能包含混合策略主要根据是布鲁威尔和角谷的不动点定理纳什均衡的普遍存在性正是纳什均衡成为非合作博弈分析核心概念的根本原因之一

31 6 纳什均衡的选择和分析方法扩展一多重纳什均衡博弈的分析二共谋和防共谋均衡

32 一多重纳什均衡博弈的分析帕累托上策均衡风险上策均衡聚点均衡相关均衡

33 帕累托上策均衡这个博弈中有两个纯策略纳什均衡,( 战争, 战争 ) 和 ( 和平, 和平 ), 显然后者帕累托优于前者, 所以,( 和平, 和平 ) 是本博弈的一个帕累托上策均衡国家战争和平国家 2 战争和平 -5, -5 8, -0-0, 8 0, 0 战争与和平

34 风险上策均衡考虑顾忌博弈方其他博弈方可能发生错误等时, 帕累托上策均衡并不一定是最优选择, 需要考虑 : 风险上策均衡下面就是两个例子博弈方 2 猎人 2 博弈方 U D L R 9, 9 0, 8 8, 0 7, 7 风险上策均衡 (D,R) 猎人鹿兔子鹿 5, 5 3, 0 兔子 0, 3 3, 3 猎鹿博弈风险上策均衡 ( 兔子, 兔子 )

35 聚点均衡来自谢林的冲突的策略, 这本博弈论的经典之作没有方程, 也没有数学符号你和其他参与人均从下面一组数中选择一个数, 并画上圈 :7,00,3,26,99,666 如果你们选择相同则赢利越多你会选择哪个数呢? 谢林发现选 7 是最常见的策略, 但在一群比较贪婪的人群中,666 也有可能成为聚点如果博弈重复多次, 则过去的历史常常就规定了聚点之所在有个老师所在的学院每到周一下午就会开会, 大家在会议室的座位本来是不固定的, 但是每学期第一次会议大家所坐的位置, 基本上会在这个学期都是他坐的位置, 因为每次开会时大家就会习惯性地坐到上次坐过的位置, 这种座位配置也如同产生了聚点一样新婚夫妻的家务分担博弈也是如此, 在婚姻初期谁做家务做得多, 那就意味着可能这一辈子他 / 她都会做更多的家务, 这也是一个聚点

36 聚点均衡利用博弈设定以外的信息和依据选择的均衡文化习惯或者其他各种特征都可能是聚点均衡的依据城市博弈 ( 城市分组相同 ) 时间博弈 ( 报出相同的时间 ) 是聚点均衡的典型例子

37 相关均衡 (A,A) 和 (B,B) 为该博弈的两个纳什均衡, 但是两人的收益不同若双方采用混合策略, 就有 /2 的概率遇到 (A,B) 和 (B,A) 的情形, 双方的收益将低于任何一个纯策略纳什均衡博弈方 A B A a, b 0, 0 博弈方 2 B 0, 0 c, d a>b>0, d>c>0 时装 C 丈夫足球 F 妻子时装 C 足球 F 2, 0, 0 0, 0, 3 夫妻之争博弈的混合策略纳什均衡策略得益妻子 (0.75,0.25) 0.67 丈夫 (/3,2/3) 0.75 夫妻之争

38 相关均衡怎么办呢? 可以设立一套装置 : () 该装置以 (a-b)/(a-b+d-c) 的概率发出 A 信号, 以概率 (d-c)/(ab+d-c) 的概率发出 B 信号 (2) 博弈方只能看到 A 信号, 博弈方 2 只能看到 B 信号 (3) 当博弈方看到 A 时, 采用 A 策略, 否则采用 B 策略 ; 当博弈方 2 看到 B 时, 采用 B 策略, 否则采用 A 策略分析可知, 在 a+b=d+c 条件下, 虽然博弈双方的总收益没有提高, 但由于实现了双方收益一致, 为双方妥协提供了可能博弈方 A B A a, b 0, 0 博弈方 2 B 0, 0 c, d a>b>0, d>c>0

39 相关均衡博弈方 U D L 5, 4, 4 三个纳什均衡 : (U,L) (D,R) 博弈方 2 R 0, 0, 5 相关均衡例子和混合策略均衡 [(/2,/2), (/2,/2)] 结果都不理想, 不如 (D,L) 可利用聚点均衡 ( 天气, 抛硬币 ), 但仍不理想相关装置 : 各 /3 概率 A B C 2 博弈方看到是否 A, 博弈方 2 看到是否 C 3 博弈方见 A 采用 U, 否则 D; 博弈方 2 见 C 采用 R, 否则 L 相关均衡要点 : 构成纳什均衡 2 有人忽略不造成问题

40 二共谋和防共谋均衡多人博弈中的共谋问题博弈方 U D L 博弈方 2 R 0,0,0-5,-5,0-5,-5,0,,-5 博弈方 3 A 博弈方 U D L 博弈方 2 R -2,-2,0-5,-5,0-5,-5,0 -,-,5 博弈方 3 B 本博弈的纯策略纳什均衡 :(U,L,A) (D,R,B) 前者帕累托优于后者博弈的结果会是什么呢? (U,L,A) 有共谋 (Coalition) 问题 : 博弈方和 2 同时偏离

41 防共谋均衡如果一个博弈的某个策略组合满足下列要求 : () 没有任何单个博弈方的会主动改变策略, 即单独改变策略无利可图 ; (2) 没有任何两个博弈方的串通会改变博弈的结果 ; (3) 依此类推, 直到所有博弈方都参加的串通也不会改变博弈的结果称为防共谋均衡前面例子中 :(D,R,B) 是防共谋均衡 (U,L,A) 不是防共谋均衡

幻灯片 1

幻灯片 1 第四讲 : 博弈的基本分析方法 ( 上 ) 吴建设基本分析思路和方法 1 上策均衡 2 严格下策反复消去法 3 划线法 4 箭头法 1 上策均衡上策 : 不管其它博弈方选择什么策略, 一博弈方的某个策略给他带来的得益始终高于他的其它的策略, 至少不低于其他策略的策略大猪待对任意的智猪博弈中的小猪等待 ; 囚徒的困境中的坦白 ; 双寡头削价中低价按等待 u s s ' i( i,