相关均衡

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

最后, 本文介绍了如何从博弈结果分布的角度来思考相关均衡.

会车博弈

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

        让          不让
让      (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)\)

该相关均衡可通过某个信使 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\).

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

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

博弈结果的概率分布可以看成是每个参与人混合策略的联合分布, 而单个参与人的混合策略则是这个联合分布的边缘分布.

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

       Y         G
Y      p1        p3
G      p2        p4

为了使得 (p1, p2, p3, p4) 构成相关均衡, 这四个概率还需要使得每个博弈方在收到信号 y (g) 时的最优策略为 Y (G). 这对应四组不等式约束.

• 比如, 当参与人 1 收到信号 y 时, 他眼中参与人 2 采取行动 Y, G 的概率分别为 p1/(p1+p3), p3/(p1+p3).
  
• 行动 Y 是参与人 1 的最优反应当且仅当:
  • 0 × p1/(p1+p3) + 5 × p3/(p1+p3) ≥ 1 × p1/(p1+p3) + 4 × p3/(p1+p3)

类似可写出其它三个不等式约束. 请读者思考并计算, 所有相关均衡中博弈方收益组合构成的集合.

总结

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

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

2. 给定博弈结果的分布 \(σ\), 博弈方 i 的混合策略为 \(σ_i = ∫_{a_{-i}} σ(a_1, ..., a_n) d a_{-i}\), 即 \(a_i\) 在 \(σ\) 下的边缘分布.

3. 不同于纳什均衡, 相关均衡中每个参与人的策略 \(σ_i\) 可以是互相依赖的. 对 \(σ\) 的一种解读方式是引入信使, 信使可以向每个参与人私下传讯.

4. \(σ\) 是相关均衡, 当且仅当每个参与人 i 在收到 信使的信号 \(m_i\), 并对其他参与人的收到的信号和行动进行推断后, 行动 \(a_i\) 构成参与人 i 的最优反应.

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