当前位置:首页 >> 高中教育 >>

混合策略纳什均衡


混合策略纳什均衡
Mixed Strategy Nash Equilibrium
理学院 顾聪 gucong@yeah.net

4.1 严格竞争博弈和混合策略
1. 混合策略的提出——猜硬币博弈
两个参与人各拿一枚硬币,并选择出正面向上还是反面向上。若两枚硬币 是一致的(即全部正面或全部反面),则参与人2赢走参与人1

的硬币;若两 枚硬币不一致(一正一反),参与人1赢得参与人2的硬币。支付矩阵如下:

参与人2
正面 参与人1 正面 反面 反面

-1, 1

1,-1

1,-1

-1, 1

由划线法可知,该博弈不存在纳什均衡。 所以采取纯策略不存在稳定的纳什均衡解。
2013-8-9 2

上述博弈的特征是:

? 在这类博弈中,不存在纯策略纳什均衡。
? 参与人的支付取决于其他参与人的策略; 以某种概率分布随机地选择不同的行动。 ? 每个参与人都想猜透对方的策略,而每个 参与人又不愿意让对方猜透自己的策略。

这种博弈的类型是什么?如何找到均衡?

2013-8-9

3

2. 混合策略、混合策略博弈和混合策略纳什均衡
?


策略:
参与人在给定信息集的情况下选择行动的规则,它规定参与人在 什么情况下选择什么行动,是参与人的“相机行动方案”。

?


纯策略:
如果一个策略规定参与人在每一个给定的信息情况下只选择一种 特定的行动,称为纯策略,简称“策略” ,即参与人在其策略空 间中选取唯一确定的策略。

?


混合策略:
如果一个策略规定参与人在给定的信息情况下以某种概率分布随 机地选择不同的行动,称为混合策略。参与人采取的不是明确唯 一的策略,而是其策略空间上的一种概率分布。

2013-8-9

4

? 混合策略 vs.纯策略 (不确定性 vs.确定性) – 在博弈 G ? {S1,?Sn ; u1,?un }中,博弈方i 的策略空间Si ? {si1 ,?sik } , 则博弈方i 以概率分布pi ? ( pi1 ,?, p ik )随机在其 k个可选策略中选
择的“策略”,称为一个“混合策略”,其中 ? 1 对 j ? 1,?, k 都 0 ? pij 成立,且 pi1 ? ? ? pik ? 1 – 纯策略可以理解为混合策略的特例,即在诸多策略中,选择该纯 策略的概率为1,选其他纯策略的概率为0. – 为何参与人可能会选择带不确定性的混合策略而放弃确定性的纯 策略? ? 参与人主观因素造成的犹豫不决 ? 外在客观因素的不确定性带来应对策略的不确定性 ? 迷惑对手:为了让其它参与人不能清楚了解自己的选择

2013-8-9

5

? 混合策略扩展博弈:
博弈方在混合策略的策略空间(概率分布空间)的选择看作一个博弈,就 是原博弈的“混合策略扩展博弈”。

? 混合策略纳什均衡(MNE):
由最优的混合策略构成的混合策略组合:
? * ? (? * , ? * , ? , ? * ) 1 2 n

即,如果对于所有的 i ? 1,, ,n,有 2 ?
* * ui(? i* ,? ? i ) ? ui(? i ,? ? i ),?? i ? Si

其中,ui 表示参与人i的期望效用。

2013-8-9

6

3. 期望效用(Expected Payoff)
? 对于任意混合策略组合:
p ? ( p1, p2 ,?, pn ), ?pi ? ( pi1,?, p imi ) ? P i
–若各参与人最终确定的组合(纯策略组合)为

(s1 j1 , s2 j2 ?, snjn ) ? Si ? {si1,?, simi )
–参与人的支付为

ui (s1 j1 , s2 j2 ?, snjn )

–发生此情况的概率为 p1 j p2 j ? pnj 1 2 n

? 参与人的期望效用:

Ei ( p) ? ???? p1 j1 p2 j2 ? pnjn ui (s1 j1 , s2 j2 ?, snjn )
j1 ?1 j2 ?1 jn ?1
2013-8-9 7

m1

m2

mn

? 由于混合策略伴随的是支付的不确定性,因此参
与人关心的是其期望效用。 ? 最优混合策略:是指在给定对方的混合策略的情 况下,使期望效用函数最大的混合策略。 ? 在两人博弈里,混合策略纳什均衡是两个参与人

的最优混合策略的组合。

2013-8-9

8

4. 一个例子——社会福利博弈
流浪汉 寻找工作 流浪

救济
政府 不救济

2
3, 1 -1,

3 -1, 0 0,

虽这模型没有PNE,却有下述的MNE:参与人以一定的概率选择某种 策略,然后计算相应于不同概率的期望效用。
2013-8-9 9

设:政府救济的概率θ=1/2 ; 不救济的概率1-θ=1/2。 流浪汉寻找工作的期望效用: 1/2×2+1/2 ×1=1.5 流浪的期望效用: 1/2×3+1/2 ×0=1.5

寻找工作γ 救济θ 不救济1-θ

游荡1-γ

3 , -1 ,

2 1

-1 , 0 ,

3 0

? 此时,流浪汉选择任何混合策略的期望效用都是1.5,则流浪汉的任 何一种策略(纯的γ=1或γ=0或混合的0<γ<1)都是政府所选择的混合策

略的最优反应。

2013-8-9

10

而当

γ=0.2 游荡

1-γ=0.8 寻找工作 救济θ

寻找工作γ

游荡1-γ

3 , -1 ,

2 1

-1 , 0 ,

3 0

救济:

3 ? 0.2 ? 1? 0.8 ? ?0.2

不救济1-θ

不救济: ? 1? 0.2 ? 0 ? 0.8 ? ?0.2

? 如果流浪汉选择这个混合策略,政府的任何策略(混合的或纯的)带给 政府的期望效用为-0.2。特别的,以1/2的概率分别选择救济和不救济 当然也是政府对于流浪汉所选择的混合策略的最有反应。 ? 这样,我们得到一个混合策略组合,每一个参与人的混合策略都是给 定对方混合策略是的最优选择,从而构成混合策略纳什均衡。 策略 期望收益 政府 (0.5, 0.5) -0.2 流浪汉 (0.2, 0.8) 1.5
2013-8-9 11

既然参与人在构成混合策略时选择不同纯策略之间是无差异的,他 为什么不选择一个特定的纯策略而要以特定的概率随机地选择不同的纯 策略呢?一个参与人选择混合策略目的是给其他参与人造成不确定性。 海萨尼(Harsanyi,1973)对混合战略的解释是,混合策略均衡等价于不完 全信息下的纯策略均衡:如社会福利博弈中,假定有两类特征的流浪汉, 一类选择寻找工作,另一类选择游荡;每个流浪汉都知道自己的特征, 但政府并不知道流浪汉的准确特征,只知道流浪汉20%概率属第一类, 80%概率属第二类。在这种情况下,政府在选择自己的策略时似乎面临 的是一位选择混合策略的流浪汉。

4.2 混合策略纳什均衡的求解
? 支付最大化法 ? 支付等值法 ? 最优反应函数法

2013-8-9

13

1. 支付最大化法求纳什均衡——猜硬币博弈
参与人1的混合策略为σ1=(q, 1-q)(分别以概率q和1-q选择正面 和反面) , 参与人2的混合策略为σ2=(r, 1-r) (分别以概率r和1-r选择正面 和反面)。 参与人2 r 正面 1-r 反面

参与人1

q 正面 1-q 反面

-1, 1 1,-1

1,-1 -1, 1

2013-8-9

14

参与人2 r 正面 1-r 反面 参与人1

q 正面
1-q 反面

-1, 1 1,-1

1,-1 -1, 1

当给定参与人2选择混合策略σ1=(r, 1-r)时,
参与人1的选取正面的期望效用为

E1(正面)=(-1)×r+1×(1-r)=1-2r
参与人1选取反面的期望效用为 E1(反面)=1×r+(-1)×(1-r)=2r-1
2013-8-9 15

参与人1的期望效用为 E1= E1(正面)×q + E1(反面)×(1- q ) =(1-2r)(2q-1) 类似地,得到参与人2的期望效用为 E2= E2(正面)×r + E2(反面)×(1- r ) =(1-2q)(2r-1)

?E ?E2 由一阶条件: 1 ? 2(1 ? 2r ) ? 0, ? 2(1 ? 2q) ? 0 ?q ?r 1 1 r? , q? 2 2 1 1 1 1 ? 1* ? ( , )和? 2 * ? ( , )分别是参与人1和参与人2的
2013-8-9

2 2 2 2 * 混合纳什均衡策略, (? 1* , ? 2 )为猜币博弈的纳什均衡。
16

社会福利博弈
假定政府的混合策略是? G ? (? ,1 ? ? );
流浪汉
工作γ 流浪1- γ

流浪汉的混合策略是? L ? (? , ? )。 1? 政府的期望效用函数为: v(? G ,? L ) ? ? (3? ? (?1)(1 ? ? ) ?(1 ? ? )(?? ? 0(1 ? ? ) ? ? (5? ? 1) ? ? 求微分,得到政府最优化的一阶条件: ?vG ? 5? ? 1 ? 0 ?? 故? * ? 0.2

政 府

救济θ

2 3, -1, 1 -1, 0,

3 0

不救济 1- θ

即:流浪汉以0.2的概率选择寻找工作,0.8的概率选择流浪。 同理可以根据流浪汉的期望效用函数找到政府的最优混合策略。
2013-8-9 17

? 对γ*= 0.2 的解释:
– 如果流浪汉寻找工作的概率小于0.2,政府的最优选择是不救济; 如果流浪汉寻找工作的概率大于0.2,政府的最优选择是救济 。

? 对 θ*= 0.5 的解释:
– 如果政府救济的概率大于0.5,流浪汉的最优选择是流浪;如果 政府救济的概率小于0.5,流浪汉的最优选择是寻找工作。

? 混合策略纳什均衡的含义:
– 纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的 最优选择。因此在社会福利博弈中,γ*= 0.2 ,θ*= 0.5 是唯一的 混合策略纳什均衡。

2013-8-9

18

2. 支付等值法求纳什均衡
由上面的例子可以看出,参与人选择的混合策略均使对方选 择纯策略的期望效用相等,促使各方均采取严格策合策略。
? ?

所以求解混合策略纳什均衡也可以采取如下方法:
求出参与人的每个纯策略的期望效用,令其相等即可得到混

合策略纳什均衡。

2013-8-9

19

猜硬币博弈
参与人1的选取正面的期望效用为 E1(正面)=(-1)× r + 1 ×(1-r) = 1-2 r 参与人1的选取反面的期望效用为 E1(反面)=1× r + (-1)×(1-r) = 2 r-1 令纯策略期望效用相等: 1 ? 2r ? 2r ? 1 得 r?

1 2

类似地,令参与人2的纯战略期望效用相等得:q ?

1 2
20

2013-8-9

社会福利博弈
假定最优混合策略存在,给定流浪汉选择混合策略

(? ,1 ? ? )
政府选择纯策略救济的期望效用为:

3? ? (?1)(1 ? ? ) ? 4? ?1
政 救济 府 不救济 如果一个混合策略(而不是纯策略)

流浪汉 寻找工作
流浪

选择纯策略不救济的效用为: ? 1? ? 0(1 ? ? ) ? ??

3, 2 -1,1

-1, 3 0, 0

是政府的最优选择,一定意味着政 府在救济与不救济之间是无差异的
4? ? 1 ? ??
2013-8-9

?=0.2
21

3. 最优反应函数法求纳什均衡
? 在讨论连续纯策略均衡时(如古诺模型),我们使用了反应 函数的概念。 ? 现在我们可以使用反应对应的概念来描述一个参与人对应 于其他参与人混合策略的最优选择。 ? 两个概念的区别仅仅在于: – 反应函数表示的是一个参与人只有一个特定的策略是 其他人给定策略的最优选择; – 反应对应允许一个参与人有多个(甚至无穷多个)策略是 其他人给定策略的最优选择。

2013-8-9

22

? 纯策略均衡:反应函数(reaction function) 在纯策略的范畴内,最优反应函数是各博弈方选择的纯策略 对其他博弈方纯策略的反应。纯策略纳什均衡是博弈方反应 函数的交叉点。

? 混合策略均衡:反应对应(reaction correspondence) 在混合策略的范围内,博弈方的决策内容为选择概率分布, 最优反应函数就是一方对另一方的概率分布的反应。由于纯 策略可以理解为混合策略,因此实际上最优反应函数的概念, 也可以在混合策略概率分布之间反应的意义上统一起来。混 合战略纳什均衡也是反应函数的交叉点。

2013-8-9

23

混合策略反应函数
猜硬币博弈
猜硬币方 r 1

r ? R1(q)
q ? R 2( r )

盖 硬 正面 币 反面 方

正 面 -1, 1

反 面 1, -1

1, -1

-1, 1

1/2

1/2
2013-8-9

1

q

(r,1-r):盖硬币方选择正反面 的混合策略概率分布 (q,1-q):猜硬币方选择正反面 的混合策略概率分布

24

混合策略反应函数
夫妻之争博弈
r 电影 丈夫 足球 0, 0 1, 3

1
1/3

q ? R2 (r )

妻 电影 子 足球

2, 1 0, 0

r ? R1 (r )
1/3
2013-8-9

(r,1-r):丈夫的混合策略概率分布 (q,1-q):妻子的混合策略概率分布
1 q

25

例题 监督博弈
θ检查

纳税人 1-γ不逃税 γ逃税 a-c+F, -a-F 0 , 0

税收机关

a-c ,
a,

-a
-a

1-θ不检查

其中,a: 应纳税款,C: 检查成本,F: 罚款, a-c+F: 检查到逃税者, -a-F: 除了要交税款又要交罚款 假定C<a十F,在这个假设下,不存在纯战略纳什均衡。让我们来 求解混合战略纳什均衡。 求MNE两种方法:支付最大化方法(求一阶导数为0); 支付等值法(即选两个纯战略是没差异)
2013-8-9 26

逃税γ 检查θ 不检查(1-θ)
a ? C ? F ,? a ? F
0, 0

不逃税(1-γ) a: 应纳税款,C: 检查成本,
a ? C ,? a

F: 罚款, a-c+F: 检查到逃税者, -a-F:

a ,? a

除了要交税款又要交罚款

假定C<a十F,在这个假设下,不存在纯战略纳什均衡。让我们来 求解混合战略纳什均衡。 用θ表示税收机关检查的概率,γ表示纳税人逃税的概率 给定γ,税收机关选择检查(θ=1)和不检查(θ=0)的期望收益分别为:

?(1 ?) a ? C ? F ) ? ? (a ? C )(1 ? ? ) ? ?F ? a ? C ? ( G , ?(0,?) 0 * ? ? a(1 ? ? ) ? a(1 ? ? ) ? G

2013-8-9

?G (1, ?) ? ?G (0, ?)
27

逃税γ

不逃税(1-γ)
a ? C ,? a



C ? ? a?F
*

检查θ
不检查(1-θ)

a ? C ? F ,? a ? F
0, 0

a ,? a

给定θ,纳税人选择逃税和和不逃税的期望收益分别为:

?(?, ? (a ? F )? ? 0 * (1 ? ?) ? (a ? F )? 1) ? ? p ?(?, ? ?a? ? (?a)(1 ? ?) ? ?a 0) p a * 令 ? p (?,1) ? ?G (?,0) 得 ? ? a?F C a * * ? ? 因此,混合战略纳什均衡是: ? ? a?F a?F
a C 税收机关以 的概率检查,纳税人以 的概率选择逃税。 a?F a?F
2013-8-9 28

结论:

?* ?

a a?F

?* ?

C a?F

当逃税概率? ?

c , 即? G (1 , ? ) ? ? G (0 , ? ) 则税收机关最优选择是不检查 a?F a 检查概率 ? ? 纳税人选逃税。 a?F c , 即? G (1 , ? ) ? ? G (0 , ? ),则税收机关最优选择检查 当逃税概率 ? ? a?F a ,纳税人选纳税。 检查概率 ? ?
a?F

当逃税概率 ? ? 而当 ? ?

c ,则税收机关随机地选择检查或不检查无差异 a?F

a ,则纳税人选择纳税与不纳税无差异 a?F a a ? * ? ? 即税收机关以 的概率选择检查 ? ? a?F a?F MNE: ? c ?? * ? c 即纳税人以 的概率选择逃税 ? a?F a?F ?

c 另一解释是:社会中有许多个纳税人,其中有 比例的纳税人 a?F a c ( )比例的纳税人选择不逃税;税收机关以 选择逃税,1 ? 比例
随机地检查纳税人的纳税情况。
a?F
a?F

a , F ?纳税人选逃税概率越小;检查成本C 越高,纳税人逃税的

概率就越大。
为什么应纳税款越多,纳税人逃税的概率反而越小呢?这是因为, 应纳税款越多,税收机关检查的概率越高,逃税被抓住的可能性越大, 因而纳税人反而不敢逃税了。这一点或许可以解释为什么逃税现象在 小企业中比在大企业中更为普遍,在低收入阶层比在高收入阶层更普

遍。

4.3 纳什均衡的存在性定理
1. 纳什定理(Nash,1950):
在一个有n个博弈方的博弈 G ? S1 ,?, S n ; u1, ?, un 中, 如果n是有限的,且Si 都是有限集,则该博弈至少存在一个纳什 均衡(纯策略的或混合策略的)。 即:每一个有限博弈至少存在一个纳什均衡。 现实中的博弈都是可以当作有限博弈来解决。这样纳什均衡 的存在就是普遍的。纳什均衡的普遍存在性是纳什均衡概念最 重要的性质。
2013-8-9 31

?

?

2. 纳什定理的推广
? 纳什均衡的存在性定理2:

当博弈方个数有限,战略集是非空、闭的、有界的,支付函 数是连续且拟凹的,则博弈至少存在一个纯战略纳什均衡。 (Debreu,1952; Clicksberg,1952; Fan,1952)
? 纳什均衡的存在性定理3:

当博弈方有限,战略集是非空、闭的、有界的,支付函数是 连续的,则博弈至少存在一个纳什均衡(纯战略的或混合战略 的)。 (Clicksberg, 1952)

2013-8-9

32

3. 纳什均衡应用的局限性
尽管纳什均衡非常重要,但不是说学到了这种分析方法你就能 预测所有博弈的结果。纳什均衡分析仅仅保证有个体理性的智能 人的博弈结果是唯一纯策略纳什均衡时的预测。实际情况是纳什 均衡分析并不能保证对所有博弈的结果都作出准确的预测。 现实中的博弈可能是下面三种情况之一: 1、有许多博弈不存在纯策略纳什均衡; 2、有些博弈是多重纳什均衡; 3、博弈方可能是集体理性或有限理性。 此时纳什均衡分析就不是绝对有效的。对这些问题有不同程度 的解决,例如,实验经济学和行为经济学的成果为寻找有限理性 时的博弈均衡提供了支持。一些新的均衡概念,例如,帕累托上 策均衡、风险上策均衡、聚点均衡和相关均衡等为多重纳什均衡 时的决策找到了方向。
2013-8-9 33

不同均衡概念的关系

占优均衡
DSE 重复剔除占优均衡

IEDE
纯策略纳什均衡 PNE 混合策略纳什均衡

MNE
2013-8-9 34


相关文章:
博弈论复习题及答案
在本题中不存在混合策略的纳什均衡解,因此,最终的纯策略纳什均衡就是 A、B 两厂商都做广告。 15、求出下面博弈的纳什均衡(含纯策略和混合策略)。乙 L 甲 U...
用非线性规划模型求解有限博弈的混合策略纳什均衡
用非线性规划模型求解有限博弈的混合策略纳什均衡 博弈方2 策略 博弈方1 策略 U L 混合策略 X1 X2 A Y1 3,5 4,3 B Y2 1,4 2,5 C Y3 5,7 0,3...
混合策略
混合策略和混合策略纳什... 4页 1下载券 混合策略纳什均衡 暂无评价 8页 1下载...混合策略(mixed strategy) : 表示采用每个纯策略的概率。 (注: 混合策略可以...
平新乔《微观经济学十八讲》课后习题详解(第10讲 策略性博弈与纳什均衡)
这个博弈有纯策略纳什均衡吗?计算出混合策略纳什均衡。 答: (1)该题的支付矩阵(表 10-4)为: 表 10-4 划拳博弈的支付矩阵 (2)这是一个零和博弈,没有纯...
“博弈论”习题及参考答案
13. 子博弈精炼纳什均衡不是一个纳什均衡。 14. 零和博弈的无限次重复博弈中, 可能发生合作, 局中人不一定会一直重复原博弈的混合 战略纳什均衡。 4 15.原...
博弈论复习题及答案
子博弈完美纳什均衡路径: 两阶段都 采用原博弈同一个纯战略纳什均衡,或者轮流采用不同纯战略纳什均衡,或者两 次都采用混合战略纳什均衡,或者混合战略和纯战略轮流...
博弈论复习题及答案
(2)如果参与者以 1/3 的概率选择每一个数字,证明该混合策略存在一个 纳什均衡,它为多少? 答: (1)此博弈的收益矩阵如下表。该博弈是零和博弈,无纳什均衡。...
博弈论复习题及答案
子博弈完美纳什均衡路径:两阶 段都采用原博弈同一个纯战略纳什均衡,或者轮流采用不同纯战略纳什均衡,或 者两次都采用混合战略纳什均衡,或者混合战略和纯战略轮流...
博弈论判断题
也许在有些博弈中只有惟一的纯策略纳什均衡, 没有严格意义上的混合策略纳什均衡, 这时把纯策略理解成特殊的混合策略, 混合策略纳什 均衡就存在了。 (4)小正确。...
更多相关标签:
混合策略纳什均衡例题 | 混合策略纳什均衡求解 | 纳什均衡 | 混合策略 | 纯策略纳什均衡 | 混合策略均衡 | 混合策略纳什均衡计算 | 零和博弈 |