相关均衡

本文以会车博弈和鹰鸽博弈为例, 介绍了两个相关均衡的例子. 前一个例子只涉及到公开信号, 后一个例子引入了私人信号. 这两个例子中, 引入相关均衡的主要动机, 是它的福利性质好于纳什均衡.

除了福利动机外, 很多学者认为“相关均衡”是比“纳什均衡”更自然的解概念.¹ 从数学上来看, 相关均衡确实更自然, 也更简单. 本文最后介绍了如何从博弈结果分布的角度来理解相关均衡.

会车博弈

考虑如下会车博弈. 两车在路口交会, 必须一方退让后, 另一方才能通过. 每位车主的可选策略为”让”和”不让”, 该博弈的矩阵表示如下:

        让          不让
让      (0, 0)     (1,  5) 
不让    (5, 1)     (-1, -1)

会车博弈中存在两个纯策略均衡: (让,不让) 和 (不让,让). 这两个均衡是帕累托有效的.

会车博弈还有一个混合策略均衡: 两位车主按一定概率在”让”和”不让”之间进行随机. 这个混合策略均衡的福利性质不好: 两位车主可能协调失败, 均衡结果中有正概率出现 (让,让) 和 (不让,不让).

纯策略均衡也有弊端: 它不公平. 最理想的均衡结果中, 应该是每位车主的效用均为 3.

相关均衡: 交通信号灯

为了兼顾效率和公平, 现实中使用的方法是在路口安装交通信号灯 🚥. 两车交会时, 可以通过信号灯 🚥 这个公开信号来决定谁停谁走. 信号灯 🚥 可以让参与人在两个纯策略均衡—(让,不让) 和 (不让,让)—之间进行随机.

交通信号灯实现了如下相关均衡. 为简化分析, 假设交通信号灯随机产生了一个公开信号 s $\in$ {红, 绿}.

• 当 “s = 红” 时, 约定车主 1 让而车主 2 通过.

• 当 “s = 绿” 时, 约定车主 2 让而车主 1 通过.

由于(让,不让) 和 (不让,让)都是纳什均衡, 上面这个借由公开信号 s 实现的协议是激励相容的: 当车主1看到红灯时, 他知道车主2不会让, 这时选择让是最优的; 车主2的分析类似.

当信号 s 为红灯或绿灯的概率均为 1/2 时, 博弈的结果是一个概率分布:

• 一半的情况为 (让,不让),

• 一半的情况为 (不让,让).

这个结果中, 两位车主的期望效用均为 3.

鹰鸽博弈

如果允许引入私人信号, 相关均衡可以使得某些不是纳什均衡的结果在均衡中发生. 考虑如下鹰鸽博弈. 博弈方为国家 A 和国家 B, 它们同时决定是选择”战争” (鹰策略, Y) 还是”和平” (鸽策略, G).

       Y        G
Y    (0,0)    (5,1)
G    (1,5)    (4,4)

该博弈包含两个纯策略均衡: (Y,G) 和 (G,Y). 这两个结果中的社会总福利均为 6.

最好的结果是双方和平共处 (G,G), 社会总福利为 8, 但它不是纳什均衡.

仿照前面交通信号灯的处理, 我们可以引入一个公开信号, 使得两个博弈方在 (Y,G) 和 (G,Y) 这两个均衡之间进行随机. 比如, 双方约定如果看到红灯信号就玩 (Y,G), 否则玩 (G,Y). 通过调整红灯信号的概率, 均衡收益向量可以是 (1,5) 和 (5,1) 这两个向量的任意凸组合.

包含私人信号的相关均衡

如果要使均衡中的社会总福利大于 6, 均衡结果中必须出现 (G,G). 我们可以用包含私人信号的相关均衡来实现福利改进.

Claim: 存在相关均衡, 其均衡收益向量为 $(3\frac 13, 3\frac 13)$

该相关均衡可通过如下方式实现: 引入信使 (Messenger, M), 信使分别向博弈方 A 和 B 私下传讯.

信使向每个博弈方同时私下发送信息 $m \in \{ y,g \}$, 当博弈方收到信息 y 时, 鹰策略 Y 会是它的最优反应; 收到信息 g 时的最优反应则为鸽策略 G. 具体构造如下.

当 A 收到信号 y 时, A 认为 B 收到信号 y 的概率记为 $q$:

• 策略Y是参与人A的最优策略, 当且仅当: $$q u_A (Y,Y) + (1-q) u_A (Y,G) \ge q u_A (G,Y) + (1-q )u_A (G,G)$$

• 这个式子等价于 $q × 0 + (1-q) × 5 \ge q × 1 + (1-q) × 4$, 即 $q ≤ 1/2$

• 同理, 当 B 收到信号 y 时, B 认为 A 收到信号 y 的概率也应小于 $1/2$.

当 A 收到信号 g 时, A 认为 B 收到信号 g 的概率记为 $p$:

• 策略G是参与人A的最优策略, 当且仅当: $$(1-p) u_A (G,Y) + p u_A (G,G) \ge (1-p) u_A (Y,Y) + p u_A (Y,G)$$

• 这个式子等价于 $(1-p) × 1 + p × 4 \ge (1-p) × 0 + p × 5$, 即 $p ≤ 1/2$

• 同理, 当 B 收到信号 g 时, B 认为 A 收到信号 g 的概率也应小于 $1/2$.

考虑 $q=0, p=0.5$ 对应的信使策略, 它可以导致如下关于博弈结果的概率分布:

       Y        G
Y      0       1/3
G     1/3      1/3

• 此时, 参与人的均衡收益均为 $3\frac 13$.

另一种视角: 博弈结果的概率分布

上面的讨论中, 我们的分析重点是博弈方和信使的策略. 我们实际上将原本的单期博弈转化成了两期的序贯博弈, 博弈方的策略也从 {Y,G} 上的概率分布变成了从信使传讯到行动的映射.

实际在定义和计算相关均衡时, 直接着眼于博弈结果的概率分布更为方便. Aumann 最早提出相关均衡的定义时, 就是使用的博弈结果的概率分布, 而非参与人的策略组合.

回到前面鹰鸽博弈的例子. 信使通过私下传讯, 在不考虑参与人激励的前提下, 可以实现所有满足 p1+p2+p3+p4=1 的概率分布, 其中每个概率 p 的含义如下:

       Y         G
Y      p1        p3
G      p2        p4

记博弈结果为 σ = (p1, p2, p3, p4). 为了使得 σ 构成相关均衡, 我们还需要考虑参与人的激励, 这通常对应四组线性不等式约束. 这类不等式约束一般被称为服从约束 (OC, obediance constraints). 我们可以通过如下机制来理解 OC:

1. 信使按照分布 σ 决定博弈结果 $(a_1,a_2)$

2. 信使将 $a_1$ ($a_2$) 私下告诉参与人 1 (2).

3. 当参与人 1 收到信号 $a_1 = Y$ 时, 他眼中参与人 2 采取行动 Y, G 的概率分别为 p1/(p1+p3), p3/(p1+p3).

   • 参与人 1 会服从信使 (ie, 行动 Y 是参与人 1 的最优反应) 当且仅当:

$$0 × p_1/(p_1+p_3) + 5 × p_3/(p_1+p_3) ≥ 1 × p_1/(p_1+p_3) + 4 × p_3/(p_1+p_3)$$

上述不等式即为参与人 1 收到信号 $a_1 = Y$ 时的服从约束, 读者可类似写出其它三个不等式约束.

练习: 计算上例中所有相关均衡效用组合.

相关均衡小结

1. 相关均衡可以表示为博弈结果的分布: $σ(a_1, ..., a_n)$.

   • 这里 $a_i$ 表示博弈方 i 的行动.

   • 函数 $σ$ 的输入为某个博弈结果 (i.e., 行动向量) $(a_1, ..., a_n)$, 输出为这个博弈结果发生的概率.

2. 给定相关均衡 $σ$, 博弈方 i 的(混合)策略为 $σ$ 在博弈方 i 行动集 $A_i$ 上的边缘分布: $σ_i = ∫_{a_{-i}} σ(a_1, ..., a_n) \, d a_{-i}$.

   • 不同于纳什均衡, 相关均衡中每个参与人的策略 $σ_i$ 可以是相关的.

3. 分布 $σ$ 是相关均衡, 当且仅当其满足对应的服从约束: 每个参与人 i 在收到信使传讯 $a_i$, 并对其他参与人的收到的信号和行动进行推断后, 行动 $a_i$ 构成参与人 i 的最优反应.

4. 由于期望效用是线性的, 相关均衡可由一组线性不等式刻画. 求解所有相关均衡的难度一般远小于求解所有纳什均衡的难度.

   • 不难证明, 有限博弈中, 所有相关均衡构成紧凸集. 部分数学推导要用到线性规划的知识, 感兴趣的读者可以阅读 Myerson 博弈论教科书 (1991) 的相关章节.

贝叶斯相关均衡

通过海萨尼转化, 纳什均衡这个解概念可以“自然地”推广到不完备信息博弈. 对应的解概念一般称为贝叶斯(纳什)均衡. 只要承认共同先验, 贝叶斯均衡的定义基本没有争议.

相关均衡则不然, 它有多种推广到不完备信息博弈的方式, 并且这些推广不等价. 一种相对流行的推广方式是“贝叶斯相关均衡” (bergemann & morris 2016).