混合策略纳什均衡
Mixed Strategy Nash Equilibrium
理学院 顾聪 gucong@
01.04.2020
1
4.1 严格竞争博弈和混合策略
1. 混合策略的提出——猜硬币博弈
两个参与人各拿一枚硬币，并选择出正面向上还是反面向上。若两枚硬币 是一致的(即全部正面或全部反面)，则参与人2赢走参与人1的硬币；若两 枚硬币不一致(一正一反)，参与人1赢得参与人2的硬币。支付矩阵如下：
– 如果流浪汉寻找工作的概率小于0.2，政府的最优选择是不救济； 如果流浪汉寻找工作的概率大于0.2，政府的最优选择是救济 。
• 对 θ*= 0.5 的解释：
– 如果政府救济的概率大于0.5，流浪汉的最优选择是流浪；如果 政府救济的概率小于0.5，流浪汉的最优选择是寻找工作。
• 混合策略纳什均衡的含义：
和反面)。
参与人2
r 正面
1-r 反面
q 正面 -1， 1
参与人1 1-q 反面
1，-1
1，-1 -1， 1
01.04.2020
14
q 正面 参与人1
1-q 反面
参与人2
r 正面
1-r 反面
-1， 1
1，-1
1，-1
-1， 1
当给定参与人2选择混合策略σ1=(r, 1-r)时， 参与人1的选取正面的期望效用为
4.2 混合策略纳什均衡的求解
➢ 支付最大化法 ➢ 支付等值法 ➢ 最优反应函数法
01.04.2020
13
1. 支付最大化法求纳什均衡——猜硬币博弈
参与人1的混合策略为σ1=(q, 1-q)(分别以概率q和1-q选择正面 和反面) ，
参与人2的混合策略为σ2=(r, 1-r) (分别以概率r和1-r选择正面
• 纯策略：
– 如果一个策略规定参与人在每一个给定的信息情况下只选择一种 特定的行动，称为纯策略，简称“策略” ，即参与人在其策略空 间中选取唯一确定的策略。
• 混合策略：
– 如果一个策略规定参与人在给定的信息情况下以某种概率分布随 机地选择不同的行动，称为混合策略。参与人采取的不是明确唯 一的策略，而是其策略空间上的一种概率分布。
求出参与人的每个纯策略的期望效用，令其相等即可得到混 合策略纳什均衡。
01.04.2020
19
猜硬币博弈
参与人1的选取正面的期望效用为 E1(正面)=(-1)× r + 1 ×(1-r) = 1-2 r
参与人1的选取反面的期望效用为 E1(反面)=1× r + (-1)×(1-r) = 2 r-1
令纯策略期望效用相等： 1 2 r2 r 1 得r 1 2
类似地，令参与人2的纯战略期望效用相等得：q 1 2
01.04.2020
20
社会福利博弈
假定最优混合策略存在，给定流浪汉选择混合策略
(,1)
政府选择纯策略救济的期望效用为：
3 ( 1 )1 () 4 1
流浪汉
寻找工作 流浪
选择纯策略不救济的效用为：
✓ 每个参与人都想猜透对方的策略，而每个 参与人又不愿意让对方猜透自己的策略。
这种博弈的类型是什么？如何找到均衡？
01.04.2020
3
2. 混合策略、混合策略博弈和混合策略纳什均衡
• 策略：
– 参与人在给定信息集的情况下选择行动的规则，它规定参与人在 什么情况下选择什么行动，是参与人的“相机行动方案”。
• 在两人博弈里，混合策略纳什均衡是两个参与人 的最优混合策略的组合。
01.04.2020
8
4. 一个例子——社会福利博弈
流浪汉 寻找工作 流浪
救济 政府
不救济
2 3，
1 -1，
3 -1，
0 0，
虽这模型没有PNE，却有下述的MNE：参与人以一定的概率选择某种 策略，然后计算相应于不同概率的期望效用。
参与人2
正面
反面
参与人1
正面 反面
-1， 1 1，-1
1，-1 -1， 1
由划线法可知，该博弈不存在纳什均衡。 所以采取纯策略不存在稳定的纳什均衡解。
01.04.2020
2
上述均衡。
✓ 参与人的支付取决于其他参与人的策略； 以某种概率分布随机地选择不同的行动。
E i(p ) L p 1 j1p 2 j2Lp n jn u i(s 1 j1,s 2 j2L ,s n jn) j1 1j2 1 jn 1
01.04.2020
7
• 由于混合策略伴随的是支付的不确定性，因此参 与人关心的是其期望效用。
• 最优混合策略：是指在给定对方的混合策略的情 况下，使期望效用函数最大的混合策略。
成立，且 pi1Lpik1
– 纯策略可以理解为混合策略的特例，即在诸多策略中，选择该纯 策略的概率为1，选其他纯策略的概率为0.
– 为何参与人可能会选择带不确定性的混合策略而放弃确定性的纯 策略？
• 参与人主观因素造成的犹豫不决 • 外在客观因素的不确定性带来应对策略的不确定性 • 迷惑对手：为了让其它参与人不能清楚了解自己的选择
16
社会福利博弈
流浪汉
工作γ 流浪1- γ
救济θ
2
政
3，
府 不救济
1
1- θ -1，
3 -1，
0 0，
假 定 政 府 的 混 合 策 略 是 G ( ,1 )； 流 浪 汉 的 混 合 策 略 是 L ( ，1 )。 政府的期望效用函数为： v ( G , L ) (3 ( 1)(1 )
海萨尼(Harsanyi,1973)对混合战略的解释是，混合策略均衡等价于不完 全信息下的纯策略均衡：如社会福利博弈中，假定有两类特征的流浪汉， 一类选择寻找工作，另一类选择游荡；每个流浪汉都知道自己的特征， 但政府并不知道流浪汉的准确特征，只知道流浪汉20%概率属第一类， 80%概率属第二类。在这种情况下，政府在选择自己的策略时似乎面临 的是一位选择混合策略的流浪汉。
01.04.2020
4
• 混合策略 vs.纯策略 (不确定性 vs.确定性)
– 在博弈G { S 1 , S n ;u 1 , u n } 中，博弈方i的策略空间Si{si1,sik }， 则博弈方i以概率分布p i(p i1,L,pik)随机在其 k个可选策略中选
择的“策略”，称为一个“混合策略”，0其中pij 1对 j1,,k都
01.04.2020
9
设：政府救济的概率θ=1/2 ； 不救济的概率1-θ=1/2。 流浪汉寻找工作的期望效用： 1/2×2+1/2 ×1=1.5 流浪的期望效用： 1/2×3+1/2 ×0=1.5
寻找工作γ
救济θ 3 , 2 不救济1-θ -1 , 1
游荡1-γ
-1 , 3
0, 0
• 此时，流浪汉选择任何混合策略的期望效用都是1.5，则流浪汉的任 何一种策略(纯的γ=1或γ=0或混合的0<γ<1)都是政府所选择的混合策
ui(i*, *i)ui(i, *i)， i Si
其 中 ， ui表 示 参 与 人 i的 期 望 效 用 。
01.04.2020
6
3. 期望效用(Expected Payoff)
• 对于任意混合策略组合：
p ( p 1 , p 2 , L , p n ) , p i ( p i 1 , L , p i m i ) P i
01.04.2020
5
• 混合策略扩展博弈：
博弈方在混合策略的策略空间(概率分布空间)的选择看作一个博弈，就 是原博弈的“混合策略扩展博弈”。
• 混合策略纳什均衡(MNE)：
由最优的混合策略构成的混合策略组合：
*( *, *,, *)
12
n
即 ， 如 果 对 于 所 有 的 i1 ， 2， L， n， 有
– 纳什均衡要求每个参与人的混合战略是给定对方的混合战略下的 最优选择。因此在社会福利博弈中，γ*= 0.2 ，θ*= 0.5 是唯一的 混合策略纳什均衡。
01.04.2020
18
2. 支付等值法求纳什均衡
由上面的例子可以看出，参与人选择的混合策略均使对方选 择纯策略的期望效用相等，促使各方均采取严格策合策略。 所以求解混合策略纳什均衡也可以采取如下方法：
E1(正面)=(-1)×r+1×(1-r)=1-2r 参与人1选取反面的期望效用为
E1(反面)=1×r+(-1)×(1-r)=2r-1
01.04.2020
15
参与人1的期望效用为
E1= E1(正面)×q + E1(反面)×(1- q ) =(1-2r)(2q-1)
类似地，得到参与人2的期望效用为
E2= E2(正面)×r + E2(反面)×(1- r ) =(1-2q)(2r-1)
• 这样，我们得到一个混合策略组合，每一个参与人的混合策略都是给 定对方混合策略是的最优选择，从而构成混合策略纳什均衡。
策略 期望收益 政府 (0.5, 0.5) -0.2 流浪汉 (0.2, 0.8) 1.5
01.04.2020
11
既然参与人在构成混合策略时选择不同纯策略之间是无差异的，他 为什么不选择一个特定的纯策略而要以特定的概率随机地选择不同的纯 策略呢？一个参与人选择混合策略目的是给其他参与人造成不确定性。
• 现在我们可以使用反应对应的概念来描述一个参与人对应 于其他参与人混合策略的最优选择。
• 两个概念的区别仅仅在于： – 反应函数表示的是一个参与人只有一个特定的策略是 其他人给定策略的最优选择； – 反应对应允许一个参与人有多个(甚至无穷多个)策略是 其他人给定策略的最优选择。
01.04.2020
24
混合策略反应函数
1 0 (1 )