第二讲纳什均衡
1,0 1,3
下 0,4 0,2 2,0
0,4 0,2
左
中
1,0 1,3
严格下策反复消去法
• 智猪博弈
小猪
按 等待
大
按
5,1 4,4
猪
等待 9,-1 0,0
严格下策反复消去法
• 适用面:
– 严格下策反复消去法的适用面比上策均衡要更大些 – 但也有很多博弈问题没有严格下策:田忌赛马、猜硬币、情
侣博弈、交通博弈、石头剪刀布、、、--此时,该方法失 效。 – 最大的用处:简化博弈
严格竞争博弈和混合策略的引进
一、猜硬币博弈
盖 正面 硬 币 反面 方
猜硬币方
正面
反面
-1, 1
1, -1
1, -1
-1, 1
(1)不存在前面定义的纳什均衡策略组合 (2)关键是不能让对方猜到自己策略--保持随机性
这类博弈很多,引出混合策略纳什均衡概念
混合策略、混合策略博弈 和混合策略纳什均衡
• 混合策略:在博弈 G {S1, Sn;u1, un} 中,博弈方i 的策略 空间为 Si {si1, s,ik }则博弈方i 以概率分布
• 画出智猪博弈的得益矩阵
“智猪博弈”(boxed pigs)
•
小猪
按 等待
大
按
5,1 4,4
猪
等待 9,-1 0,0
经典博弈之四--猎人博弈
• 设想在古代的一个地方,有两个猎人。那时候,狩猎是人们的 主要生计。为了简单起见,假设主要的猎物只有两种: 鹿,兔子。 在古代,人类的狩猎手段还比较落后,弓箭威力也有限。在这样的 条件下,我们可以进一步假设,两个猎人一起去猎鹿,才能猎获一 只鹿,如果一个猎人单兵作战,他只能打到4只兔子。如果他打兔 子,你去猎鹿,他可以打到4只兔子,而你一无所获,得0。
得五体投地,她怎么肯放过正宗俄罗斯的芭蕾舞剧《胡桃夹子》?这么说,一
个在家里看电视直播的足球,一个去剧院看芭蕾舞演出不就得了?问题在于他
们是热恋中的情侣,分开各自度过这难得的周末时光,才是最不乐意的事情。
这样一来,他们就面临一场温情笼罩下的“博弈”
• 在情侣博弈中, 我们不妨这样给大海和小丽的“满意程度”赋值:如果大 海看球让小丽一个人去看芭蕾,双方的满意程度都为0;两人一起去看足球, 大海的满意程度为2,小丽的满意程度为1;两人一起去看芭蕾,大海的满意程 度为1,小丽的满意程度为2。应该不会有小丽独自看球而大海独自去看芭蕾的 可能,不过人们还是把它写出来,设想因此双方的满意程度都是-1。
弈
猜
-1, 1
硬
币
1, -1
1, -1 -1, 1
2, 1 0, 0
0, 0 1, 3
课堂习题
• 用划线法求出均衡解
C1
C2
C3
R1
0,4 4,0 5,3
R2 4,0 0,4 5,3
R3 3,5 3,5 6,6
箭头法
• 思路:
– 对博弈中的每一个策略组合进行分析,考察在每个策略组合 处各个博弈方能否通过单独改变自己的策略而增加得益
• 也有时:情侣博弈中,用划线法有两个策略组合同时下面划线,这意味着 两个策略组合中的双方策略都是对对方策略的最佳对策--都具有内在的 稳定性--但具体那一个会出现,无法确定。
划线法
1, 0 0, 4
1, 3 0, 2
0, 1 2, 0
囚 徒
-5, -5
0, -8
情 侣
困
-8, 0
境
-1, -1
博
齐威王田忌赛马
Pa 上中下
齐 Pb 上下中 威 Pc 中上下 王 Pd 中下上
Pe 下上中 Pf 下中上
Pg
上 中 下
3,-3 1,-1 1,-1 -1,1 1,-1 1,-1
– 与划线法一样都是基于策略之间的相对优劣关系进行分析的, 所得到的结果也是一致的。
– 如果能,则从所分析的策略组合对应的得益数组引一箭头, 到改变策略后策略组合对应的得益数组
– 最后,只有指向,没有离开的策略组合为均衡解--稳定- -没有人愿意单独改变
箭头法
1, 0 0, 4
1, 3 0, 2
0, 1 2, 0
• 假设打到一只鹿,两家平分,每家管10天;打到4只兔子,只能供 一家吃4天。
• 画出得益矩阵
猎人博弈得益矩阵
乙
猎鹿
打兔
10
4
甲 猎鹿 10
0
0
4
打兔 4
4
博弈论故事之五--高薪养廉
• “高薪养廉”是公务员制度方面的一种理论,我们分 析一下“高薪”为什么能养廉?
• 假设甲乙为一家单位的主任和书记关系密切的国家公 务员,7代表现在政府给他们的高薪。如果两人受贿, 因为串谋而一时不被人发现,他们可以达到9的位置; 而一旦“东窗事发”,他就要被撤职查办, 不受贿一 方得8
pi ( pi1, pik ) 随机在其 k个可选策略中选择的“策略”,
称为一个“混合策略”,0其 中pij 1 j 1对, ,k
都成立,且
pi1 pik 1
• 混合策略扩展博弈:博弈方在混合策略的策略空间(概率
分布空间)的选择看作一个博弈,就是原博弈的“混合策略扩
展博弈)
• 假设行走顺利,每人获益为1,相撞,则获益为-1, • 画出得益矩阵
交通博弈
乙
靠左行
靠右行
靠左行
甲
靠右行
1,1 -1,-1
-1,-1 1,1
经典博弈故事之三--智猪博弈
• 笼子里面有两只猪,一只比较大,一只比较小。笼子很长,一头 有一个按钮,另一头是饲料的出口和食槽。按一下按钮,将有相当 于10个单位的猪食进槽,但是按按钮以后跑到食槽所需要付出“劳 动”,加起来要消耗相当于2个单位的猪食。问题是按钮和食槽分 置笼子的两端,按按钮的猪付出劳动跑到食槽的时候,坐享其成的 另一头猪早已吃了不少。如果大猪先到,大猪呼啦啦吃到9个单位, 小猪只能吃到1个单位;如果同时到达,大猪吃到7个单位;小猪吃 到3个单位;如果小猪先到,小猪可以吃到4个单位,而大猪吃到6 个单位。
• 静态:博弈方是同时决策的,或者虽然各博弈方决策的 时间不一定真正一致,但他们在做决策时互相不知道其 他博弈方的策略。
• 完全信息静态博弈:各博弈方同时决策,且所有博弈方 对各方得益都了解的博弈。
• 如何求这一类博弈的解呢?--博弈的结果如何?-- 博弈各方最终的策略组合?
上策均衡法
• 上策均衡:一个博弈的某个策略组合中的所有策略都是 各个博弈方各自的上策
•博弈方i 的得益:ui
•博弈:G {S1, Sn;u1, un} •纳什均衡:在博弈G {S1, Sn;u1, un} 中,如果由各个博弈 方的各一个策略组成的某个策略组合(si*, sn* ) 中,任一博弈
方i 的策略,都是对其余博弈方策略的组合 (si*, si*1, si*1,...sn* )
博弈方1的混合策略
pA 3 pB 1 pA 2 pB 5
博 弈A 方B 1
博弈方2
C
D
2, 3 5, 2
3, 1 1, 5
博弈方2的混合策略
pC 2 pD 5 pC 3 pD 1
pA+pB=1;
pC+pD=1
策略
得益
博弈方1 (0.8,0.2) 2.6
博弈方2 (0.8,0.2) 2.6
的最佳对策,也即 ui (si*, si*1, si*, si*1,...sn*) ui (si*, si*1, sij , si*1,...sn*)
对任意 si j Si 都成立,则称 (si*, sn* ) 为 G 的一个纳什
均衡
纳什均衡的一致预测性质
•一致预测:
– 如果所有博弈方都预测一个特定博弈结果会出现,所有博弈方都不会 利用该预测或者这种预测能力,选择与预测结果不一致的策略,即没 有哪个博弈方有偏离这个预测结果的愿望,因此预测结果会成为博弈 的最终结果
经典博弈故事之二--情侣博弈
•
大海和小丽正在热恋。难得的周末又到了,安排什么节目呢?周末晚上,
中国足球队要在世界杯外围赛中和伊朗队做生死之战。大海是个超级球迷,国
内的甲级联赛都不肯放过,何况是不争气的国家队的生死大战?也正好是这个
周末的晚上,俄罗斯一个著名芭蕾舞团莅临该市演出芭蕾舞剧《胡桃夹子》。
丽娟最崇尚钢琴、芭蕾这样的高雅艺术,对斯拉夫民族的歌唱和芭蕾更是崇拜
• 试着用一个得益矩阵来描述大海和丽娟的情侣博弈
情侣博弈的得益矩阵Leabharlann 小丽足球芭蕾
足球
1
2 大
海
芭蕾
-1
-1
0 0
2 1
靠左走还是靠右走
• 在一个没有交通规范的农村小路骑自行车,你应该走 在道路的哪一边?
• 假如别人靠右(左)走,你也 靠右(左)走,则不会 相撞;反之,假如别人靠右(左)走,而你却反其道 而行之,偏要靠左(右)走,则必然相撞。
• 只有,两方均被划线的策略组合,才是稳定的策略--表明给定一方采用 该策略组合中的策略,则另一方也愿意采用该策略组合中的策略,该策略 组合具有稳定性。
• 但是,许多博弈根本不不存在确定性的结果,划线法失效,比如猜硬币- -没有一个策略组合是双方同时愿意接受的,这样的博弈根本不可能有可 以预言的博弈结果
• 做法: – 首先找出某博弈人的严格下策,把这个严格下策剔除后,剩下的是一 个不包含已剔除劣策略的新的博弈;然后再剔除这个新的博弈中的严 格下策;继续这个过程,直到没有劣策略存在。如果剩下的策略组合 是唯一的,这个唯一的策略组合就是严格下策反复消去法的均衡
严格下策反复消去法