【笔记】非完全信息下的动态博弈（序贯均衡）

本文主要是介绍【笔记】非完全信息下的动态博弈（序贯均衡），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

来源于mit的Economic Applications of Game Theory这门课的Lecture Notes的第16章。

序贯均衡

考虑如下博弈：

员工有 0.7 0.7 0.7 的概率是勤奋的， 0.3 0.3 0.3 的概率是懒惰的。公司可以选择雇佣或者不雇佣该员工；若雇佣，则员工可以选择工作或偷懒。注意到加粗的线表示了一个贝叶斯纳什均衡（Bayesian Nash equilibrium），这显然不是我们想要的结果。为了解决这个问题，不妨设员工是序贯理性（sequentially rational）的，即对于每一个其所在的信息集（information set）都会选择能使其期望收益最大的策略，那么员工就会选择工作而不是偷懒。而得知员工会选择工作后，公司也会改为雇佣该员工。

注意到第二个均衡是上述博弈中唯一的完美子博弈均衡（subgame-perfect equilibrium），那么使用完美子博弈均衡的方法是不是通用的呢？答案是否定的。考虑如下博弈：

这显然是一个完美子博弈均衡，因为并不存在真子博弈（proper subgame），同时这也是一个纳什均衡。注意到此时玩家 2 2 2 并不是序贯理性的，因此序贯理性的引入是必要的。下面形式化描述序贯理性：

定义1（信念估计）

定义信念估计（belief assessment） b b b 为每个信息集选取一个概率分布构成的列表。给定信息集 I I I，则 b ( ⋅ ∣ I ) b(\cdot|I) b(⋅∣I) 给出了 I I I 上的概率分布。

对于给定的信息集 I I I，在该信息集上做决策的玩家会相信自己以 b ( ⋅ ∣ I ) b(\cdot|I) b(⋅∣I) 的概率分布位于 I I I 上的节点。

定义2（序贯理性）

令 s s s 为策略组合（strategy profile）， b b b 为信念估计。称 ( s , b ) (s,b) (s,b) 是序贯理性的当且仅当对于每个信息集 I I I，在以下条件下，在 I I I 上做决策的玩家最大化了自己的收益：

1. 该玩家相信自己以 b ( ⋅ ∣ I ) b(\cdot|I) b(⋅∣I) 的概率分布位于 I I I 的节点上；
2. 在 I I I 之后的博弈中，每个玩家都会根据 s s s 来决策。

例如在上一个博弈中，若玩家 2 2 2 以 μ \mu μ 的概率位于左边的节点， 1 − μ 1-\mu 1−μ 的概率位于右边的节点。若玩家 2 2 2 是序列理性的，则无论 μ \mu μ 的值是多少，他都会选择决策 R R R。

但这仍然不够。为了获得均衡，我们仍需要 b b b 是与 s s s 一致的。举例来说，仍然考虑上面的博弈

序贯理性的玩家 2 2 2 以 0.1 0.1 0.1 的概率位于左边的节点，他会选择 R R R 作为决策。此时玩家 1 1 1 会选择决策 T T T 作为决策 R R R 的最佳反应（best response）。显然这不是个均衡。问题就在于在均衡中，每个玩家都知道其他玩家的策略。但知道了玩家 1 1 1 的决策后，玩家 2 2 2 的信念估计就会发生改变。因此我们需要引入一致性：

定义3（一致性）

给定策略组合 s s s 和信念估计 b b b，令 I I I 为根据 s s s 进行决策时有可能被到达的信息集。称 b ( ⋅ ∣ I ) b(\cdot|I) b(⋅∣I) 与 s s s 一致当且按照 s s s 进行决策时，到达 I I I 上的概率分布恰好是 b ( ⋅ ∣ I ) b(\cdot|I) b(⋅∣I)。即对于 ∀ n ∈ I \forall n\in I ∀n∈I，
b ( n ∣ I ) = Pr ⁡ ( n ∣ s ) ∑ n ′ ∈ I Pr ⁡ ( n ′ ∣ s ) b(n|I)=\frac{\Pr(n|s)}{\sum_{n'\in I}\Pr(n'|s)} b(n∣I)=∑n′∈I​Pr(n′∣s)Pr(n∣s)​
其中 Pr ⁡ ( n ∣ s ) \Pr(n|s) Pr(n∣s) 表示根据 s s s 进行决策时到达 n n n 的概率。

但对于那些到达的概率为 0 0 0 的节点，上述式子的分母为 0 0 0，那么我们如何定义其一致性呢？一个方法是让每一条边均有一个很小的概率被选取，然后令这些概率趋于 0 0 0，得到的就是对应的概率分布。例如考虑如下博弈：

在策略组合是 ( X , T , L ) (X,T,L) (X,T,L) 时，玩家 3 3 3 的信息集被到达的概率为 0 0 0。不妨令玩家 1 1 1 和 2 2 2 分别有一个很小的概率 ϵ 1 , ϵ 2 \epsilon_1,\epsilon_2 ϵ1​,ϵ2​ 发生“抖动”，即玩家 1 1 1 选择 E E E 的概率是 ϵ 1 \epsilon_1 ϵ1​，选择 X X X 的概率是 1 − ϵ 1 1-\epsilon_1 1−ϵ1​；玩家 2 2 2 选择 B B B 的概率是 ϵ 2 \epsilon_2 ϵ2​。此时再计算到达 T T T 指向的节点 n T n_T nT​ 的概率
Pr ⁡ ( n T ∣ I 3 , ϵ 1 , ϵ 2 ) = ϵ 1 ( 1 − ϵ 2 ) ϵ 1 ( 1 − ϵ 2 ) + ϵ 1 ϵ 2 = 1 − ϵ 2 \Pr(n_T|I_3,\epsilon_1,\epsilon_2)=\frac{\epsilon_1(1-\epsilon_2)}{\epsilon_1(1-\epsilon_2)+\epsilon_1\epsilon_2}=1-\epsilon_2 Pr(nT​∣I3​,ϵ1​,ϵ2​)=ϵ1​(1−ϵ2​)+ϵ1​ϵ2​ϵ1​(1−ϵ2​)​=1−ϵ2​
令 ϵ 2 → 0 \epsilon_2\to 0 ϵ2​→0 就可以得到 b ( n T ∣ I 3 ) = 1 b(n_T|I_3)=1 b(nT​∣I3​)=1 而不是 0.1 0.1 0.1。

定义4（更完备的一致性）

给定 ( s , b ) (s,b) (s,b)，称 b b b 与 s s s 一致当且仅当加入某些趋于 0 0 0 的抖动概率后，根据 s s s 计算出来的所有信息集的概率分布都趋于 b b b 给出的概率分布。即存在序列 ( s m , b m ) (s^m,b^m) (sm,bm) 使得

1. ( s m , b m ) → ( s , b ) (s^m,b^m)\to (s,b) (sm,bm)→(s,b)；
2. 对于任意 m m m， s m s^m sm 满足每一个决策都有可能被选择；
3. b m b^m bm 是通过 s m s^m sm 计算出来的。

通过序贯理性和一致性可以定义出序贯均衡（sequential equilibrium）：

定义5（序贯均衡）

称 ( s , b ) (s,b) (s,b) 是序贯均衡的，如果 ( s , b ) (s,b) (s,b) 是序贯理性的，并且 b b b 与 s s s 一致。

可以验证上面的博弈中，唯一的完美子博弈均衡是 s ∗ = ( E , T , R ) s^*=(E,T,R) s∗=(E,T,R)。令 b ∗ ( n T ∣ I 3 ) = 1 b^*(n_T|I_3)=1 b∗(nT​∣I3​)=1 是信念估计，则可以验证 ( s ∗ , b ∗ ) (s^*,b^*) (s∗,b∗) 是序贯均衡。

非完全信息下的出价博弈

考虑这样一个有意思的博弈：一个卖家要出售一件物品给一个买家。物品对卖家来说价值为 0 0 0，对买家来说价值为 v v v。其中 v v v 在 [ 0 , 1 ] [0,1] [0,1] 上均匀分布，且只有买家自己知道。游戏分两轮：在第一轮中，卖家出价 p 0 p_0 p0​；若买家选择以 p 0 p_0 p0​ 的价格购买，则卖家和买家的收益分别是 p 0 p_0 p0​ 和 v − p 0 v-p_0 v−p0​，游戏结束；若不购买，则进行第二轮。在第二轮中，卖家出价 p 1 p_1 p1​；若买家选择以 p 1 p_1 p1​ 的价格购买，则卖家和买家的收益分别是 δ p 1 \delta p_1 δp1​ 和 δ ( p 1 − v ) \delta(p_1-v) δ(p1​−v)，其中 δ ∈ ( 0 , 1 ) \delta\in (0,1) δ∈(0,1)；若不购买，则双方的收益均为 0 0 0，游戏结束。

买家的策略可以用 a , b a,b a,b 两个函数形式化表示：第一轮中购买当且仅当 v ≥ a ( p 0 ) v\ge a(p_0) v≥a(p0​)；第二轮中购买当且仅当 v ≥ b ( p 1 ) v\ge b(p_1) v≥b(p1​)。现在考虑这个博弈的序贯均衡。

容易发现在第二轮中，买家收益非负当且仅当 v ≥ p 1 v\ge p_1 v≥p1​，因此 b ( p 1 ) = p 1 b(p_1)=p_1 b(p1​)=p1​。在第一轮中，当买家拒绝以 p 0 p_0 p0​ 的价格购买时，卖家可以得知 v ≤ a ( p 0 ) v\le a(p_0) v≤a(p0​)，即对于卖家来说 v v v 在 [ 0 , a ( p 0 ) ] [0,a(p_0)] [0,a(p0​)] 中均匀分布。若在第二轮中出价 p 1 p_1 p1​，则卖家的期望收益为
U S ( p 1 ∣ p 0 ) = p 1 Pr ⁡ ( p 1 < v ∣ v ≤ a ( p 0 ) ) = p 1 ( a ( p 0 ) − p 1 ) / a ( p 0 ) U_S(p_1|p_0)=p_1\Pr(p_1<v|v\le a(p_0))=p_1(a(p_0)-p_1)/a(p_0) US​(p1​∣p0​)=p1​Pr(p1​<v∣v≤a(p0​))=p1​(a(p0​)−p1​)/a(p0​)
由于卖家想要最大化自己的收益，得到
p 1 ( p 0 ) = a ( p 0 ) / 2 p_1(p_0)=a(p_0)/2 p1​(p0​)=a(p0​)/2
下面考虑第一轮。给定 p 0 p_0 p0​ 后，当 v ≥ a ( p 0 ) v\ge a(p_0) v≥a(p0​) 时，买家会在第一轮以 p 0 p_0 p0​ 的价值购买；当 v ∈ [ a ( p 0 ) / 2 , a ( p 0 ) ) v\in [a(p_0)/2,a(p_0)) v∈[a(p0​)/2,a(p0​)) 时，买家会在第二轮以 a ( p 0 ) / 2 a(p_0)/2 a(p0​)/2 的价值购买；否则不买。根据序贯理性，我们有
v − p 0 ≥ δ ( v − p 1 ( p 0 ) )  for  v ≥ a ( p 0 ) v-p_0\ge \delta(v-p_1(p_0))\text{ for }v\ge a(p_0) v−p0​≥δ(v−p1​(p0​)) for v≥a(p0​)

v − p 0 ≤ δ ( v − p 1 ( p 0 ) )  for  v ∈ [ a ( p 0 ) / 2 , a ( p 0 ) ) v-p_0\le \delta(v-p_1(p_0))\text{ for }v\in [a(p_0)/2,a(p_0)) v−p0​≤δ(v−p1​(p0​)) for v∈[a(p0​)/2,a(p0​))

根据连续性，当 v = a ( p 0 ) v=a(p_0) v=a(p0​) 时上述不等式取等号，即
a ( p 0 ) − p 0 = δ ( a ( p 0 ) − p 1 ( p 0 ) ) a(p_0)-p_0=\delta(a(p_0)-p_1(p_0)) a(p0​)−p0​=δ(a(p0​)−p1​(p0​))
代入 p 1 ( p 0 ) = a ( p 0 ) / 2 p_1(p_0)=a(p_0)/2 p1​(p0​)=a(p0​)/2 得到
a ( p 0 ) = p 0 1 − δ / 2 a(p_0)=\frac{p_0}{1-\delta/2} a(p0​)=1−δ/2p0​​
最后考虑如何设置 p 0 p_0 p0​：当 v ≥ a ( p 0 ) v\ge a(p_0) v≥a(p0​) 时卖家收益为 p 0 p_0 p0​；当 v ∈ [ a ( p 0 ) / 2 , a ( p 0 ) ) v\in [a(p_0)/2,a(p_0)) v∈[a(p0​)/2,a(p0​)) 时收益为 δ p 1 ( p 0 ) = δ a ( p 0 ) / 2 \delta p_1(p_0)=\delta a(p_0)/2 δp1​(p0​)=δa(p0​)/2；其余情况收益为 0 0 0。因此期望收益为
U S ( p 0 ) = p 0 ⋅ ( 1 − a ( p 0 ) ) + δ ( a ( p 0 ) / 2 ) ⋅ ( a ( p 0 ) − a ( p 0 ) / 2 ) = p 0 ( 1 − p 0 1 − δ / 2 ) + δ ( p 0 2 − δ ) 2 \begin{aligned} U_S(p_0)&=p_0\cdot(1-a(p_0))+\delta(a(p_0)/2)\cdot(a(p_0)-a(p_0)/2)\\ &=p_0\left(1-\frac{p_0}{1-\delta/2}\right)+\delta\left(\frac{p_0}{2-\delta}\right)^2 \end{aligned} US​(p0​)​=p0​⋅(1−a(p0​))+δ(a(p0​)/2)⋅(a(p0​)−a(p0​)/2)=p0​(1−1−δ/2p0​​)+δ(2−δp0​​)2​
计算 U S ( p 0 ) U_S(p_0) US​(p0​) 的最大值得到
p 0 = ( 1 − δ / 2 ) 2 2 ( 1 − 3 δ / 4 ) p_0=\frac{(1-\delta/2)^2}{2(1-3\delta/4)} p0​=2(1−3δ/4)(1−δ/2)2​

这篇关于【笔记】非完全信息下的动态博弈（序贯均衡）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！