博弈论 第一讲 博弈现象与基本概念
博 弈 论 the Theory of Games
正 大 光 明 公 正 无 私
主要内容
一、博弈现象及基本概念
二、完全信息静态博弈
三、完全信息动态博弈
四、不完全信息静态博弈
五、不完全信息动态博弈
六、不完全信息专题
正 大 光 明 公 正 无 私
主要参考书
姚国庆:《博弈论》,高等教育出版社,2007. 罗云峰:《博弈论教程》,清华大学出版社、北京交通大学出版社。 张维迎:《博弈论与信息经济学》,上海三联书店,上海人民出版社,2004。
施锡铨,《博弈论》,上海财经大学出版社,2002。 正 大 光 明 公 正 无 私
张守一,《现代经济对策论》,高等教育出版社,1998。 钱颂迪,《运筹学》,清华大学出版社,1996。
[美]艾里克.拉斯缪森:《博弈与信息》,北京大学出版社,2003。
[美]弗登博格:《博弈论》,中国人民大学出版社,2002。
正 大 光 明 公 正 无 私 第一讲 博弈现象与基本概念 1(博弈现象
2. 博弈概念
3. 博弈描述
4. 博弈练习
5. 关于博弈论
正 大 光 明 公 正 无 私 1(博弈现象
田忌赛马:正确的策略可以反败为胜。
囚徒困境:
(-1,-1)
(-10,0)
不认罪
(0,-10)
(-5,-5)
认罪
不认罪
认罪
甲
乙
理性的人是自私自利的; 理性选择不是全局最优。 正 大 光 明 公 正 无 私 经济合作:
(0,0)
(4,-2)
欺骗
(-2,4)
(2,2)
合作
欺骗
合作
甲
乙
诚信的价值;
一报还一报策略;
人类生存环境启示。
正 大 光 明 公 正 无 私 长街上的超市 (海滩占位模型)
,,,,,,,,,,,,,,,,,,,,,
0
1/2
3/4
1
1/4
A’
O’
资源浪费还是理性的必然,
其它相似情形:旅行社的热门路线;黄金时间的电视节目;总统竞选。
正 大 光 明 公 正 无 私
狩猎与投资
狩猎:
两个猎人围住一头鹿,各卡住两个关口中的一个,齐心协力即可成功获得并平分猎物。此时有一群兔子跑过,任何一人去抓兔子必可成功,但鹿会跑掉。
他们会坚持猎鹿还是去抓兔子,
正 大 光 明 公 正 无 私
共同投资:
双方共同投资一个大项目,可期望有较大收益。此时如某方抽出资金去进行小项目投资,必可成功获小利,但会使共同项目陷入困境,使对方蒙受损失。
投资者会如何选择,
正 大 光 明 公 正 无 私
旅行者困境
两个旅行者花瓶被摔坏,向航空公司索赔。航空公司知道价格约为八九
十元,但不知道确切价格。于是请两位旅客在100元以内自己写下花瓶的价格。
如两人写的一样,就认为他们讲真话,并按所写数额赔偿;如果两人写
的不一样,就认定低者讲真话,并照此价格赔偿。同时,对讲真话的旅客奖励2
元钱,对讲假话的旅客罚款2元。
理性原则下,他们会写多少价格呢,
正 大 光 明 公 正 无 私
2. 博弈概念
什么是博弈:
个人或团体间在依存和对抗、合作和冲突中的决策问题。
博弈论研究博弈过程中的理性行为。
正 大 光 明 公 正 无 私
如何理解理性行为:
自身利益最大;
持续地有意图的行动;
不对动机妄加猜测;
不考虑道德问题;
只研究合法问题;
盈利函数有多重
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
。
正 大 光 明 公 正 无 私
博弈三要素
局中人(参与人)players:
决策主体;
自然人、团体或“虚拟局中人”;
有可供选择的策略和明确定义的利益函数;
分为两人和多人
正 大 光 明 公 正 无 私
策略(战略)strategies:
采取行动的规则;
可以是一次行动也可以是一个行动序列;
可以是纯策略也可以是混合策略;
分为有限和无限。
支付(盈利函数)payoff:
对应于某策略组合的局中人利益或损失;
确定的或是期望的;
分为零和和非零和。
正 大 光 明 公 正 无 私
扩展术语:
信息:信息集;
完全信息(complete);
完美信息(perfect)。
共同知识:双方可能获取的相同信息;
彼此都能算清楚。
博弈结果:均衡策略组合;均衡行动组合。 均衡:所有局中人最优策略的组合。 正 大 光 明 公 正 无 私
3. 博弈描述
博弈的策略型(标准型、正则型)表述: 指定n个局中人,以及他们各自的纯策略空间
和这些局中人各自的支付(盈利)函数
我们将该博弈表示为:
正 大 光 明 公 正 无 私
例:寡头竞争问题
策略型表述多适用于静态博弈。
另一种表述方式是扩展式表述,两种表述形式几乎是完全等价的,但是扩展
式表述更适合于讨论动态博弈。
正 大 光 明 公 正 无 私
房地产开发实例
双方:A,B
策略:开发投资1亿元;不开发,投资0
售价:高需:1.4亿元(两栋),1.8亿元(一栋);
低需:0.7亿元(两栋),1.1亿元(一栋)。 正 大 光 明 公 正 无 私
结果:高需,(开,不开), (0.8,0)
高需,(不开,开), (0,0.8)
高需,(开,开), (0.4,0.4)
高需,(不开,不开),(0,0)
低需,(开,不开), (0.1,0)
低需,(不开,开), (0,0.1)
低需,(开,开), (-0.3,-0.3)
低需,(不开,不开),(0,0) 正 大 光 明 公 正 无 私
策略型表述: (两人有限博弈;矩阵形式) (0,0)
(0,0.8)
不开发
(0.8,0)
(0.4,0.4)
开发
不开发
开发
A
B
高需求情况
低需求情况,
正 大 光 明 公 正 无 私
房地产博弈分析
假设:同时决策;市场需求双方已知
若市场需求大,双方开发,各得0.4万元。
若市场需求小,依赖于对方行动。
若市场不确定,依赖对市场的判断及对方行动。
例:P,0.5,最坏情况期望盈利500万元,开发。
P,0.3,对方开发概率,31/40时,开发;否则,不开发。(,)
正 大 光 明 公 正 无 私
关键问题:
对自然状态的概率估计;
不同时间决策(决策顺序);
对对方先验信息的估计(即估计对方对信息的掌握程度)。
现实困难:
对市场了解程度不同;
对对方了解程度不同;
如何向对方暗示自己的行动。
正 大 光 明 公 正 无 私
4.博弈练习
游戏一:心灵感应
两个人一组,独立写出1至10之间的任意5个数。如果不重复则得奖;否则受罚。
获胜的秘诀是什么,
正 大 光 明 公 正 无 私
游戏二:海盗逃生
有5个海盗,即将被处死刑。法官愿意给他们一个机会。从100个黄豆中随意抓取,最多可以全抓,最少可以不抓,可以和别人抓的一样多。抓得最多的和最少的要被处死。
如果你第一个抓,你抓几个,
正 大 光 明 公 正 无 私
游戏三:100元怎么分,
你看见两个小孩在玩耍,出于好奇,你给他们100元,让他们猜拳。
猜赢者决定怎么分这100元,而输者如果同意赢者的分配比例,那么他们将各有所得,如果不同意,那么这100元,你将收回。
请你替赢者考虑一下,怎样分配,赢者既得到最大利益,又能让输者也同意呢,
正 大 光 明 公 正 无 私
游戏四:一元钱竞拍
给一元钱钞票开出你的价钱,使自己获益最大或损失最少;每次叫价以5分钱为单位;开价最高者得到这一元钱;出价最高和次高者一并按所开的价钱支付。
斜坡上的均衡;
“骑虎难下”的博弈;
“协和谬误”
正 大 光 明 公 正 无 私
游戏五:强盗分赃
有五个强盗抢得100枚金币,在如何分赃问题上争吵不休。于是他们决定:
(1)抽签决定自己的号码(1,2,3,4,5);
(2)由1号提出分配
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
,然后5人表决,如果方案超过半数同意就通过,否则他将被仍进大海喂鲨鱼;
正 大 光 明 公 正 无 私
(3)1号死后,由2号提方案,4人表决,当且仅当超过半数同意方案
通过,否则2号同样被仍进大;
(4)依次类推,直到找到一个每个人都接受的方案(当然,如果只剩下
5号,他当然接受一个人独吞的结果)。
如果你是第一个强盗,你该如何提出分配方案才能使自己的收益最大化
呢,
正 大 光 明 公 正 无 私
5. 关于博弈论
博弈分类:
合作、非合作:
是否存在一个具有约束力的
协议
离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载
(binding agreement) 前者强调团体理性(效率、公正、公平)
后者强调个人理性(最优决策,不保证效率) 正 大 光 明 公 正 无 私
完全信息与不完全信息:
每一个局中人对自己及其它局中人是否有完全的了解;
包括局中人特征、策略空间、盈利函数等知识。
动态与静态:
行动的先后顺序;
是否同时(或不同时但对方不知)。
正 大 光 明 公 正 无 私
发展历史:
1944 Von Neumann & Morgenstern “The theory of games and
economic behavior”
1950 Nash & 1953 Shapley “讨价还价”模型
1950、1951 Nash 非合作博弈
1950 Tucker Prisoners’ dilemma
1953 Gillies & Shapley 合作博弈
1965 Selton 动态分析;“精炼纳什均衡”
1967、1968 Harsanyi “不完全信息”
1994 Nash 、Selton、 Harsanyi 诺贝尔经济学奖 正 大 光 明 公 正 无 私
纳什的传奇人生
1928年出生于一个电子工程师家庭。
17岁进入今卡耐基梅隆大学,专攻数学。 20岁时进入普林斯顿大学攻读博士学位。
1949年,21岁的纳什写下论文《多人博弈的均衡点》。
1950年以论文《非合作型博弈》获得数学博士学位。 正 大 光 明 公 正 无 私
正 大 光 明 公 正 无 私
毕业后先后在兰德研究所、普林斯顿大学、MIT工作。
1957年他与MIT学生爱莉西娅结婚。
在而立之年患上了妄想型精神分裂症,九十年代逐渐恢复了正常。
1994年纳什博士获诺贝尔经济学奖。
2002年来北京参加 “国际数学家大会”
正 大 光 明 公 正 无 私 正 大 光 明 公 正 无 私 电影 “美丽心灵”
正 大 光 明 公 正 无 私 不完全信息动态博弈
精炼贝叶斯纳什均衡
泽尔滕(1975)
不完全信息静态博弈
贝叶斯纳什均衡
海萨尼(1967,1968) 不完全信息
完全信息动态博弈
子博弈精炼纳什均衡
泽尔滕(1965)
完全信息静态博弈
纳什均衡
纳什(1950,1951)
完全
信息
动态
静态
博弈论体系
正 大 光 明 公 正 无 私 第二讲 完全信息静态博弈 1.矩阵博弈
2.累次严优均衡
3.纳什均衡
4.混合策略纳什均衡
5.纳什均衡的存在性与多重性 正 大 光 明 公 正 无 私 1. 矩阵博弈
什么是矩阵博弈:
两人零和有限策略博弈;
可用矩阵形式表述。
矩阵元素为局中人A的赢得,亦即B的损失。
例:用矩阵形式表述田忌赛马博弈(,)
正 大 光 明 公 正 无 私 有鞍点情形:存在最优纯策略
例:表中数据为I的赢得
2
6
2
9
max ,3
6
0
,3
α4 ,10 ,10 ,1
9
α3
2
4
2
3
α2
,8
,8
1
,6
α1
min
β3
β2
β1
II
I 博弈哲学:从最坏处考虑,争取最好结果
正 大 光 明 公 正 无 私
无鞍点情形:最优混合策略
例:
?
9
11
max
7
9
7
α2
5
5
11
α1
min
β2
β1
II
I
设最优混合策略:
大 光 明 公 正 无 私 正
对局中人I:
正 大 光 明 公 正 无 私 ?I的最优混合策略为
同理,II的最优混合策略为
G,8
同理可求局中人II的最优混合策略(,)
正 大 光 明 公 正 无 私
2.累次严优均衡
占优策略均衡
严格)劣策略:无论对方如何选择都更差。 (
占优策略:无论对方如何选择存在唯一最优。 占优策略均衡:所有局中人占优策略的组合。 特点:只要求每个人理性,并不要求知道其它人是不是理性。
正 大 光 明 公 正 无 私
例:裁军问题
(0,0)
(,? , 10000)
裁军
( 10000 ,,? )
(,3000,,3000)
武装
裁军
武装
以巴
例:囚徒困境中的(认罪,认罪)
例:房地产投资市场大情况下(开发,开发) 正 大 光 明 公 正 无 私
重复剔除的占优均衡 (iterated elimination)
也称为累次严优均衡。
通过重复剔除劣战略剩下唯一的战略组合。
如果存在则称为重复剔除占优可解的。
(dominance solvable)
特点:不仅要求每个人理性,还要求知道其它人理性。理性是共同知识。
正 大 光 明 公 正 无 私
例:智猪博弈
按钮喂食:一次供应量为8,代价为2。
大猪先到 7:1;同时到 5:3;小猪先到 4:4 (0,0)
(7,,1)
等
(2,4)
(3,1)
按
等
按
小猪
大猪
正 大 光 明 公 正 无 私
分析:小猪有占优策略,大猪没有,所以不存在占优均衡;
在“理性”为共同知识的情况下,存在重复剔除的占优均衡,即(大猪
按,小猪等)。
应用:
此为“多劳不多得,少劳不少得”的奇怪情形,是一种有趣的社会现象。
经济学中称为“搭便车现象” 正 大 光 明 公 正 无 私 例:
(2,8)
(9,6)
(3,0)
D
(3,6)
(8,4)
(2,1)
M
(6,2)
(5,1)
(4,3)
U
R
M
L
II
I
无论局中人I怎样决策,局中人II与其选取策略M还不如选取策略R。对
于局中人II来说,M是个劣策略。 可以去掉II的“M”列。 正 大 光 明 公 正 无 私 假定II不选M,对于I来说M和D是劣策略。
(2,8)
(3,0)
D
(3,6)
(2,1)
M
(6,2)
(4,3)
U
R
L
II
I
正 大 光 明 公 正 无 私 故I选择U。这时,II选择L而不选R。
可以预测博弈的合理结局可能是(U,L)即(4,3)。
(6,2)
(4,3)
U
R
L
II
I
(4,3)
U
L
II
I
正 大 光 明 公 正 无 私 严优均衡的局限
有时无法开始累次严优的剔除;
例:房地产投资中市场小的情况
反常现象:盈利函数取极端值时;
如果双方都存在严劣策略,从不同人开始的结果一致;
与混合策略的优劣比较。
正 大 光 明 公 正 无 私 例:
(5, 4.5)
(6, 5)
D
(,1000, 8.5)
(7, 9)
U
R
L
II
I
分析:
累次严优过程产生了唯一解(U,L)。
然而,不管局中人I如何行动,局中人II取R仅比取L在盈利上差0.5。
I选策略U要冒极大的风险,策略D比U更加稳健。
所以,局中人I不会选U,而是选择D。稳健性。 正 大 光 明 公 正 无 私
3. 纳什均衡
定义:
有n个局中人的策略式表述博弈
G={S1,„,Sn;u1,„,un},
策略组合s* = (s1*,„,si*,„,sn*)是一个纳什均衡,如果对于每一个
i,si*是给定其它局中人选择
s-i*=(s1*,„,si-1*,si+1*,„,sn*)
的情况下第i个局中人的最优策略,即
ui(si*,s-i*)??ui(si,s-i*) , ??si??Si,?? i
正 大 光 明 公 正 无 私
或者用另一种表述方式:
si*是下述最大化问题的解:
si* ?? argmax ui(s1*,„,si-1*,si,si+1*,„,sn*),
i=1,2,„n。si??Si 结论:
最优对任一参与者的任一策略成立;
是一种可以自动实施的协议(self-enforcing)
正 大 光 明 公 正 无 私
两人有限博弈纳什均衡的确定
例:用表上作业法寻找nash均衡 (6,6)
(3,5)
(3,5)
D
(5,3)
(0,4)
(4,0)
M
(5,3)
(4,0)
(0,4)
U
R
C
L
B
A
大 光 明 公 正 无 私 正
对纳什均衡的理解
“一致性”特征:
局中人预测到均衡;局中人也预测到其它人预测到均衡;
没有局中人有兴趣作不同的选择。
是局中人的一致性预测;但不一定最好。 正 大 光 明 公 正 无 私
与严优均衡的关系:
(1)每个占优均衡、重复剔除的占优均衡一定是纳什均衡,反之则不然。
(2)纳什均衡一定是在重复剔除严劣策略过程中没有剔除的策略组合,反
之则不然。
(3)纳什均衡有强弱之分。强纳什均衡,;弱纳什均衡?。允许弱劣策略
存在。
大 光 明 公 正 无 私 正
例:市场进入博弈
参与人:在位者;进入者
策略:在位者:默许、斗争;
进入者:进入、不进入。
假定:进入之前的垄断利润为300,
进入之后寡头利润为100,
进入成本为10。
正 大 光 明 公 正 无 私 (0,300)
(0,300)
不进入
(,10,0)
(40,50)
进入
斗争
默许
在位者
进入者
纳什均衡分析:
(进入,默许)是强纳什均衡,
(不进入,斗争)是弱纳什均衡。
正 大 光 明 公 正 无 私
重复剔除弱劣策略方法:
“斗争”是在位者的弱劣战略被剔除,(进入,默许)是唯一重复剔除的占优均衡;
纳什均衡(不进入,斗争)将被剔除掉。
说明(弱)纳什均衡允许弱劣战略存在。
正 大 光 明 公 正 无 私
4.纳什均衡应用举例
(1) 消耗战(鹰鸽博弈)
两只老虎为争夺猎物对峙。都坚持则猎物腐烂;一方放弃则归另一方;都放弃则都得不到猎物。猎物价值9><>f,僵持成本为c。
(对称博弈与对称均衡)
正 大 光 明 公 正 无 私
(2)性别战(协调博弈)
一对情侣周末安排,女方喜欢音乐会,男方喜欢足球赛。情侣陪伴看喜欢的为最好,陪情侣看自己不喜欢的为次之,各自看自己喜欢的又次之,各自看不喜欢的最糟糕。
正 大 光 明 公 正 无 私
(3)协同作业1
两人合作,报酬相同为v。两人同时用力,代价为cl;只有一人用力,
代价为ch。
cl < V < ch 正 大 光 明 公 正 无 私
(4)协同作业2
两人合作,给定一人的努力水平,另一人的收益随自己努力水平先增后
减。收益函数:
ui(ai)=ai(c+aj-ai), c>0,ai>=0(图,) 最优反应函数:ai*(aj)=(c+aj)/2 联立求Nash均衡得:a1=a2=c
正 大 光 明 公 正 无 私
(5)Cournot寡头竞争模型
Cournot,1838,完全信息静态博弈。
参与人:企业1和企业2;
企业策略:选择产量;
支付:利润,是两个企业产量的函数。
正 大 光 明 公 正 无 私
第i个企业的产量:
成本函数:
价格函数:
第i个企业的利润函数:
正 大 光 明 公 正 无 私
对每个企业的利润函数求导并令其等于零:
分别定义了两个反应函数:
结论:每个企业的最优战略(产量)是另一个企业产量的函数。
正 大 光 明 公 正 无 私
两个反应函数的交叉点就是纳什均衡: 正 大 光 明 公 正 无 私
考虑上述模型的简单情况:
设 , 价格函数取线性形式:
最优化的一阶条件分别为:
正 大 光 明 公 正 无 私
反应函数为:
解两个反应函数,得纳什均衡为:
每个企业的纳什均衡利润分别为:
正 大 光 明 公 正 无 私
与垄断情况作比较:
垄断企业的问题:
垄断企业的最优产量:
垄断利润:
正 大 光 明 公 正 无 私
结论:
(1)寡头竞争的总产量大于垄断产量的原因,在于每个企业在选择自己的
最优产量时,只考虑对本企业利润的影响,而忽视对另一个企业的外部负效应。 (2)易证明,双方串谋成立卡特尔是不稳定的,双方都有欺骗的动机。(,) 正 大 光 明 公 正 无 私
(6)自学
伯川德模型
多党竞选;事故赔偿法;
公共地悲剧;争议仲裁;
合作性谈判;报案;专家诊断; 正 大 光 明 公 正 无 私 5. 混合策略纳什均衡
例:社会福利博弈(父母与懒惰儿子)
参与人:政府;一个流浪汉
政府策略:救济、不救济;
流浪汉策略:找工作、流浪 正 大 光 明 公 正 无 私 支付矩阵:
(0,0)
(,1,1)
不救济
(,1,3)
(3,2)
救济
游荡
找工作
流浪汉
政府
正 大 光 明 公 正 无 私
假定:政府的混合策略
流浪汉的混合策略
则政府的期望效用函数为:
正 大 光 明 公 正 无 私
对上述效用函数求微分,得到政府最优化的一阶条件为:
即,流浪汉以0.2的概率选择寻找工作,0.8的概率选择流浪。 所以,如果 ,政府将选择不救济;如果 ,政府将选择
救济;只有当
时,政府才会选择混合策略( )或任何纯策略。 正 大 光 明 公 正 无 私
同理,求解流浪汉的最优化问题,即可找出政府的均衡混合战略。 易知 (,)
纳什均衡要求,每个参与人的混合策略是给定对方的混合策略下的最优选
择。因此,在社会福利博弈中, 是唯一的纳什均衡。 正 大 光 明 公 正 无 私
例:监督博弈
参与人:税收机关;纳税人
税收机关策略:检查、不检查;
纳税人策略:逃税、不逃税
正 大 光 明 公 正 无 私
支付矩阵:a是应纳税款,C是检查成本,
<>F是罚款; C<a+<>F 。 (a,-a)
(0,0)
不检查
a-C,-a) (
(a-C+<>F,-a-<>F)
检查
不逃税
逃税
纳税人
税收机关
正 大 光 明 公 正 无 私
用θ代表税收机关检查的概率,γ代表纳税人逃税的概率。
给定γ,税收机关检查(θ=1)和不检查(θ=0)的期望收益分别为:
练习:本例与前例解法互换(,) 正 大 光 明 公 正 无 私
令 ,
,即最优的逃税概率。 得:
同理得 。
因此混合策略纳什均衡是:
正 大 光 明 公 正 无 私
讨论:
应纳税款越多逃税概率越小;
与逃税技术及检查成本有关;
贿赂的积极性;
提高逃税惩罚可降低逃税积极性,减少检查必要性。
练习:
解析法求前面图解法例子的最优混合策略(,) 正 大 光 明 公 正 无 私
6.纳什均衡的存在性与多重性
纳什均衡的存在性定理(纳什1950)
每一个有限博弈至少存在一个纳什均衡(纯的或混合的)。
各均衡间的关系(下图)
正 大 光 明 公 正 无 私 正 大 光 明 公 正 无 私
纳什均衡的多重性:
导致局中人一致预测困难;例:分蛋糕
利用其它信息达到聚点均衡;例:性别战;赌徒分钱
廉价磋商cheap talk;
协调博弈coordination game; 局中人学习,重复博弈中“平均”表现。
正 大 光 明 公 正 无 私 (1,1)
(0,0)
D
(0,0)
(9,9)
U
R
L
II
I
(7,7)
(8,0)
D
(0,8)
(9,9)
U
R
L
II
I
正 大 光 明 公 正 无 私 第三讲 完全信息动态博弈 1.博弈的扩展型表述
2.扩展型博弈的纳什均衡 3.子博弈精炼纳什均衡(完美均衡) 4.寡头竞争模型
5.工会与雇主间的博弈 6.讨价还价模型
7.重复博弈
正 大 光 明 公 正 无 私 1.博弈的扩展型表述
extensive form representation
要素:
局中人:谁参加
行动顺序:什么时候行动
行动空间:有什么选择
信息集:知道些什么
支付函数:能得到什么
自然选择概率:外生事件如何
正 大 光 明 公 正 无 私
博弈树:
n人有限博弈的扩展型表述可用博弈树表示。
例:房地产开发
正 大 光 明 公 正 无 私
博弈树一般构造:
结,决策结、终点结;
枝,局中人的行动选择。
信息集,决策时面临的可能信息状态;
由单个或多个决策结组成的集合;
用虚线连接同一信息集的结。
注:应用信息集概念,可将博弈树用来表示静态博弈(囚徒困境,)
正 大 光 明 公 正 无 私
正 大 光 明 公 正 无 私
正 大 光 明 公 正 无 私
正 大 光 明 公 正 无 私
信息类型
完美perfect:每个信息集都是单结的。
确定certain:自然不在任何一个参与人行动之后行动。 对称symmetric:没有人在行动时或终点结处拥有与其它人不同的信息。 完全complete:自然不首先行动或它的最初行动被所有人观察到。 博弈论
正 大 光 明 公 正 无 私
例:扑克牌游戏下注前行为规则。
(1)所有牌洗成面朝上; (完美,确定)
(2)所有牌洗成面朝下且不能看自己的牌;
(不完全,对称,确定)
(3)所有牌洗成面朝下且参与人只能看自己的牌; (不完全,不
对称,确定)
(4)所有牌洗成面朝上,但每个参与人随后都可以用手护住并悄悄丢掉一
张牌;
(完全,不对称,确定)
博弈论
正 大 光 明 公 正 无 私
(5)所有牌洗成面朝上,然后参与人下注,然后每个人再得到一张面朝上
的牌。
(完美,不确定) (6)所有牌洗成面朝下,然后参与人抓起自己的牌但不看牌,然后把牌举
过头顶让其它人看清他的牌。
(不完全,不对称,确定) 博弈论
正 大 光 明 公 正 无 私
完美信息博弈特征:
没有同时行动;
所有后行动者确切知道前行动者的行动;
所有人观测到自然的行动。
博弈的完美回忆要求 perfect recall
所有人都不忘记以前知道的事情;
所有人都不会忘记自己的选择。
例:扑克游戏忘记前面所出牌的情形 正 大 光 明 公 正 无 私
2. 扩展型博弈的纳什均衡
纯策略纳什均衡
例:市场小情况下的房地产开发
正 大 光 明 公 正 无 私 (0,1)
(1,0)
不开,开
(0,0)
(0,0)
(0,1)
不开
(1,0)
(-3,-3)
(-3,-3)
开
不开,不开
开,不开
开,开
A\B 囚徒困境动态情况下的策略型, 正 大 光 明 公 正 无 私 分析:
A的纯策略:开发、不开发;2个 B的纯策略:共4个
所有局中人的一个纯策略组合决定了博弈树的一个路径。
(开发,,不开发,开发,):
A,开发,B,不开发,(1,0)
(不开发,,开发,开发,):
A,不开发,B,开发,(0,1) 正 大 光 明 公 正 无 私
存在三个纯策略纳什均衡:
(开发,,不开发,开发,)
(开发,,不开发,不开发,)
(不开发,,开发,开发,)
定理:一个有限完美信息博弈有一个纯策略纳什均衡。 正 大 光 明 公 正 无 私
混合策略纳什均衡**:
行为策略:信息集上行动集合的概率分布
例:
正 大 光 明 公 正 无 私
参与人2纯策略:
,L,L,,,L,R,,,R,L,,,R,R, 行为策略:
b2=,(1/2,1/2),(1/2,1/2), (在信息集每一个结点,局中人2以1/2的概率选择一种行动)
混合策略:
ζ2,(ζ21,ζ22,ζ23,ζ24) 正 大 光 明 公 正 无 私
在信息集h:
选择L,,L,L,,,L,R,
选择R,,R,L,,,R,R,
在信息集h〃:
选择L,,L,L,,,R,L,
选择R,,L,R,,,R,R,
所以有
正 大 光 明 公 正 无 私
解之得:
ζ2,(1/4,1/4,1/4,1/4)
ζ2,(1/2,0,0,1/2)
ζ2,(0,1/2,1/2,0)
结论:一个行为策略可能对应多个混合策略;
但一个混合策略只对应一个行为策略。
可证明:在完美信息博弈中,两者是等价的。 正 大 光 明 公 正 无 私
3.子博弈精炼纳什均衡(完美均衡)
基本思想:
静态中假设其它人策略是给定的
动态中前行动者要考虑对后行动者的影响
区分纳什均衡的合理性
精炼refining
不可置信威胁
大 光 明 公 正 无 私 正
莱茵哈德?泽尔腾
Reinhard Selten 1930年出生于德国
1961年获得法兰克福大学数学博士学位 1984年后任教于波恩大学
子博弈精炼纳什均衡创立者
1994年因在“非合作博弈理论中开创性的均衡分析” 获诺贝尔经济学奖
正 大 光 明 公 正 无 私
例 : (U,R)与(D,L)的区别, (0,0)
(3,1)
D
(2,2)
(2,2)
U
R
L
1\2
正 大 光 明 公 正 无 私
例:房地产开发,唯一合理均衡: A:开发,B:,不开发,开发, 正 大 光 明 公 正 无 私
子博弈:
从一个单结信息集开始;
信息集和支付向量都直接继承自原博弈;
(不可分割原博弈的信息集)
任何博弈本身称为自身的一个子博弈。 正 大 光 明 公 正 无 私
前例:包括原博弈,共有三个子博弈。 正 大 光 明 公 正 无 私
无法再分割,子博弈只有本身一个。 正 大 光 明 公 正 无 私
在第2局中人处不可分割(会切割原来的信息集),故此图只有两个子
博弈。
正 大 光 明 公 正 无 私
子博弈精炼纳什均衡
扩展型博弈的策略组合 s*=
(s1*,...,si*,...,sn*) 是一个子博弈精炼纳什均衡,如果:
(1)它是原博弈的纳什均衡;
(2)它在每一个子博弈上给出纳什均衡。 正 大 光 明 公 正 无 私
说明:
每一个子博弈(包括原博弈)都构成一个纳什均衡;
如果有唯一子博弈,则等同于纳什均衡;
如果存在其它子博弈,则有些纳什均衡将不是。 前例:两个子博弈;
(D,L)是精炼均衡,(U,R)不是。 前例:房地产投资
正 大 光 明 公 正 无 私
与纳什均衡的本质区别:
纳什均衡只要求均衡策略在均衡路径(历史)上的决策结上是最优的;
子博弈精炼纳什均衡要求在非均衡路径的决策结上也是最优的。
正 大 光 明 公 正 无 私
4.逆向归纳法
基本思想
重复剔除劣策略方法的推广。
在均衡路径,每一个局中人在每一个信息集上的选择都是占优选择。
适用于有限完美信息博弈
不适用于无限博弈和不完美信息博弈。 正 大 光 明 公 正 无 私
例:(,U,U’,,L)
正 大 光 明 公 正 无 私
逆向归纳法的缺陷
在阶段多时失去可靠性。例如:传口令游戏
对意外事件的预测。Rosenthal 1981
1 A1 2 A2 1 A3 2 A4 1 A5
D1
D2
D3
D4
D5
(1,0) (0,1) (3,0) (2,4) (6,3)
(5,5)
正 大 光 明 公 正 无 私
分析:
逆向归纳法Di为最优选择;
如果1非理性地选择A1,则2如何选择,
大家均非理性会有双赢结果,是否应该冒险,
正 大 光 明 公 正 无 私
5.承诺行动 commitment
通过减少自己的选择机会使自己受益。
完全承诺与不完全承诺。
例:破釜沉舟
例:房地产
案例
全员育人导师制案例信息技术应用案例心得信息技术教学案例综合实践活动案例我余额宝案例
若B与某客户已签合同,如不能履约赔偿3500万,则B的,开发,开发,
成为可置信的威胁。子博弈精炼纳什均衡为(不开发,,开发,开发,) 正 大 光 明 公 正 无 私
例:要胁诉讼: 原告P,被告D
(1) 原告决定是否对被告提出控告,成本为c>0; (2) 如果决定控告,原告要求被告支付s>0私了; (3) 被告决定是否接受原告的要求;
(4) 如果被告拒绝,原告决定放弃或是向法庭起诉,原告的起诉成本为p,
被告的辩护成本为d;
(5) 如果案子到了法庭,原告以??概率赢得x单位的支付.
正 大 光 明 公 正 无 私
提出s
正 大 光 明 公 正 无 私
分析:
原告指控条件: ??x-p<0,即 ??x<p
原告选择: {不指控,要求,放弃} 被告选择:{拒绝}
均衡:原告不指控
正 大 光 明 公 正 无 私
原告承诺行动:
指控前支付律师费,则??x,c,p,,c,p。 最后选择:起诉。
私了赔偿:
私了赔偿区域为s?[??x, ??x+d]。 若讨价还价能力相同,则赔偿为s= ??x+d/2。 正 大 光 明 公 正 无 私
原告指控条件:
原告总成本为c+p,
指控条件为??x+d/2,c+p。
被告越大,d越大,被指控可能性就越大。
?
被告承诺行动:
指控前支付律师费y。
被告节省成本??x+d/2,y,律师费y,??x+d/2
“积淀成本”:
局中人为承诺行动支付的成本。
正 大 光 明 公 正 无 私
6.应用实例
(1)Stackelberg产量竞争模型
Stackelberg ,1934, 完美信息动态博弈。
Leader:q1?0,
follower:观测到q1,选择q2?0 正 大 光 明 公 正 无 私
给定q1,企业2的问题是:
最优化:
企业1预测到S2(q1),企业1的问题是:
解:
均衡: ;均衡结果: 正 大 光 明 公 正 无 私
比较分析:
总产量:
各企业产量及利润:
正 大 光 明 公 正 无 私
结论:
— 拥有信息优势使人处于劣势(可以证明:价格竞争有后动优势) 先动优势
原因:q1先生产 积淀成本
若q1只是宣布,未真正实现,则不构成威胁,即是cournot 模型。
正 大 光 明 公 正 无 私
(2)工会与雇主间的博弈*
列昂惕夫模型 Leontief 1946
博弈的顺序:
工会首先选择工资w;
企业观测到w后选择就业水平L。
(工会决定工资,企业决定就业水平。)
因此,这是个完美信息动态博弈。
正 大 光 明 公 正 无 私
设工会的效用函数为:U(w,L),
w,工资水平,L,就业水平,
Uw,0,UL,0
设企业的利润函数为:
假定R(L)是严格递增的上凸函数,即R’,0,R”,0 正 大 光 明 公 正 无 私
首先求解给定w的情况下,企业的就业需求 。 企业问题:
最优化的一阶条件是: 即边际收益等于边际成本。
?边际收益 是递减的,?上述一阶条件意味着企业对劳动的需
求 是工资的递减函数(w?,L?)。
正 大 光 明 公 正 无 私
工会预测到上述结果,工会在第一阶段的问题是:
最优化的一阶条件是:
其中, 是工会的边际替代率;
是企业劳动需求曲线的斜率。
正 大 光 明 公 正 无 私
合同曲线
工会的无差异曲线
企业的等利润曲线
正 大 光 明 公 正 无 私
均衡:
工会选择工资水平 使得自己的无差异曲线与企业的劳动需求曲线相切。 子博弈精炼纳什均衡结果是
非帕累托最优。
帕累托最优合同曲线:
即企业等利润曲线的斜率等于工会无差异曲线的斜率(相切)。 正 大 光 明 公 正 无 私
模型改进:纳什讨价还价模型
假定工会和企业之间就工资和就业水平同时进行磋商,如果双方不能达
成协议,工会的效用水平和企业的利润水平都为零;如果双方达成协议,工会的
效用水平为U(w,L),企业的利润为π(w,L)。
纳什讨价还价问题:
正 大 光 明 公 正 无 私
最优解的一阶条件是:
整理得:
显然,这个解是一个帕累托最优合同。 正 大 光 明 公 正 无 私
(3) 讨价还价模型
不存在耐心问题
例:两人为买卖一物谈判一个价格。
买者B最高出价300元,
卖者S不接受低于200元的开价。
不存在耐心问题:
轮次少,时间短,不存在时间价值。 正 大 光 明 公 正 无 私
B
正 大 光 明 公 正 无 私
特点:“后动优势”;
“几乎吃掉整个蛋糕”
另:若由B开价,只进行一次,
则(200,ε)元成交。
决定因素:谁最后开价;开价轮次数。
正 大 光 明 公 正 无 私 不耐心的情形
5.82
2.91
3
0
B盈余
88.53
94.18
94
100
S盈余
S 6%,B 3%
S,B均3%
11.47
94.18
B
97
5.82 97.09 S
98
6
97
B
99
0
100
S
100
B盈余
S盈余
开价者
轮次
例:100轮次。每轮要支付成本。
正 大 光 明 公 正 无 私
48.35 46.75 48.20 B盈余
32.65 34.73 32.71 34.80 32.78 ...
S盈余
S 6%,B 3%
S,B均3% 67.35 51.65 B
1
65.27 53.25 S
2
67.29 51.80 B
3
65.20
S
4
67.22
B
5
...
...
...
B盈余
S盈余
开价者
轮次
耐心相同:50,50;耐心之比:利益之比 正 大 光 明 公 正 无 私
一般模型
Rubinstein-Stahl讨价还价模型 定理:给定S、B双方,B第一次开价,次数无限,贴现因子0,δB,1,0
,δS,1,当拒绝与接受无所谓,认为接受,则存在唯一子博弈完美均衡。(贴
现因子,1,耐心成本因子)
B首轮开价
正 大 光 明 公 正 无 私 注:若 ,则
例:若δB=0.97,δS=0.94,
x*=(1-0.94)/(1-0.94??0.97)=0.674;
若δB=δS=0.97
x*=1/(1+0.97)=0.508 结论:取决于两个因素
?折扣因子(耐心程度):耐心回报
?谁先行动:先动优势
正 大 光 明 公 正 无 私
问题:
独裁者dictator博弈:
当政者与平头百姓金钱分配。有限次,最后一次为当政者。
当政者不会利用后动优势。
存在其它支付标准(价值)。
正 大 光 明 公 正 无 私
最后通牒ultimatum博弈:
双方金钱分配,第一人提出,第二人接受或拒绝。
第二人不完全理性:宁可(0,0),拒绝+ε
厌恶盈利差距。
合理结局:五五开,
正 大 光 明 公 正 无 私
(4)自学
Stackelberg产量竞争模型
收买选票;赛跑;
开放式基金;国际贸易与关税;
工作竞赛;退出衰落行业
正 大 光 明 公 正 无 私
7. 重复博弈repeated games
基本概念
相同的博弈长期中不断重复。
阶段博弈之间没有“物质”上的联系,即不改变下一阶段结构。
所有局中人都观测到过去的历史。
局中人总支付是所有阶段支付贴现值之和或加权平均值。 正 大 光 明 公 正 无 私
连锁店悖论
chain-store paradox,Selton,1978
有限次重复博弈。
市场进入问题:有20个同样市场
猜想:为阻止进入者进入其它19个市场,在位者选择“斗争”,
子博弈完美均衡:每一个市场都选择“默许” 正 大 光 明 公 正 无 私
定理:
令G是阶段博弈,G(T)是G重复T次的重复博弈(T,??)。那么,
如果G有唯一的纳什均衡,G(T)的唯一子博弈精炼纳什均衡结果是G的纳什均
衡重复T次。
正 大 光 明 公 正 无 私
无限次重复
例:囚徒困境问题(P6)
冷酷grim策略(触发策略):
)开始选择不认罪; (1
(2)选择不认罪直到有一方选择认罪,然后永远选择认罪。 正 大 光 明 公 正 无 私
设:δ为贴现因子(两人相同)
给定j坚持冷酷策略没有首先选择认罪,
则i不认罪的条件为:
0 + δ(-5) + δ2(-5) +...
?? -1 + δ(-1) + δ2(-1) 或 -5δ/(1-δ) ?? -1/(1-δ),
解之得: δ* ?? 1/5
正 大 光 明 公 正 无 私
不难看出:即使j首选选择了认罪,i将坚持冷酷策略以惩罚j的不合作行为。
所以:冷酷战略为纳什均衡。
子博弈:
类型A:没有任何局中人曾经认罪,冷酷战略为纳什均衡;
类型B:至少有一人曾经认罪,冷酷战略重复单阶段纳什均衡,也是整个子博弈的纳什均衡。
正 大 光 明 公 正 无 私
结论:
若δ* ?? 1/5(局中人足够耐心),则冷酷策略为无限次囚徒困境问题的子博弈精炼纳什均衡。
此时帕累托最优(不认罪,不认罪)成为每一个阶段的均衡结果。
困境解决~
其它策略:有限惩罚策略,一报还一报策略
正 大 光 明 公 正 无 私
无名氏定理(Friedman 1971):
令G为一个n人阶段博弈,G(??,δ)为以G为阶段博弈的无限次重复博弈,a*是G的一个纳什均衡(纯策略或混合策略),e=(e1,e2,...,en)是a*决定的支付向量,v=(v1,v2,...,vn)是一个任意可行的支付向量,V是可行支付向量集合。那么,对于任何满足vi>ei的v??V(??i),存在一个贴现因子δ*<1,使得对于所有δ,δ*, v=(v1,v2,...,vn)是一个特定的子博弈精炼纳什均衡结
果。
正 大 光 明 公 正 无 私
说明:
a*为v的惩罚点,或纳什威胁点Nash threat point。
由于害怕触发阶段纳什均衡,局中人有积极性保持合作并乐于惩罚机会主义行为。
正 大 光 明 公 正 无 私