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

2021/12/30 23:12:44

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

来源于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​



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


扫一扫关注最新编程教程