22 一个信号灯胜过所有谈判

▷ 轮到你

回到第 3 章那个斗鸡：两个人抢一条道，谁让谁吃亏，谁都不让就撞车。收益是：都让各得 6，我不让你让我得 7 你得 2，都不让各得 0。

现在装一个装置：它随机选一种情况，然后分别、悄悄地告诉两个人该怎么做——只告诉他本人那一条，他不知道对方被告知了什么。

问：这样一个既不能强制、也不能惩罚的装置，最多能把每个人的收益提到多少？

A 顶多到 4.5——也就是公开抛硬币，一半时间我先走一半时间你先走 B 顶多到混合均衡的 14/3 ≈ 4.667，因为它没有任何强制力 C 能到 5.25，比任何纳什均衡的任何混合都高 D 能到 6，也就是「都让」那一格

先看没有装置时有多糟

斗鸡有三个纳什均衡（引擎穷举出来的）：

均衡	我得	你得	两人合计	撞车概率
纯：我不让，你让	7	2	9	0
纯：我让，你不让	2	7	9	0
混合：各以 2/3 让	14/3	14/3	28/3	1/9

两个纯均衡都不公平，而且需要事先说好谁让——可这本身就是要解决的问题。

混合均衡公平，但它有代价：两人都以 1/3 的概率不让，所以撞车概率是 1/3 × 1/3 = 1/9，约 11.11%。合计收益 28/3 ≈ 9.33，比两个纯均衡的 9 高一点（因为偶尔两人都让，各得 6）。

有没有办法既公平、又不撞车？

最朴素的想法是公开抛一次硬币：正面我先走，反面你先走。这确实可行——它是两个纯均衡的混合，每人期望收益 (7+2)/2 = 4.5，撞车概率 0。

但 4.5 比混合均衡的 4.667 还低。因为公开抛硬币永远只用那两个不公平的格子，从来不用「都让」那个各得 6 的格子。

把硬币藏起来

关键的改动只有一个字：悄悄地说。

装置按下面的概率随机选一格，然后只告诉每个人他自己那一条建议：

                  你：让          你：不让
  我：让           1/2             1/4
  我：不让         1/4              0

# 三种情况：
#   1/2 的概率：两个人都被告知「让」
#   1/4 的概率：我被告知「不让」，你被告知「让」
#   1/4 的概率：我被告知「让」，你被告知「不让」
#   「都不让」这一格概率是 0 —— 撞车不可能发生

现在检查最关键的一件事：收到建议的人，会不会想违抗？

# 我被告知「不让」（发生概率 1/4）
#   这只可能来自「我不让、你让」那一格 ⇒ 我确定你会让
#   听话：得 7      违抗（改成让）：得 6      ⇒ 听话

# 我被告知「让」（发生概率 1/2 + 1/4 = 3/4）
#   我不知道你收到了什么。条件概率：
#     你也被告知「让」   (1/2) / (3/4) = 2/3
#     你被告知「不让」   (1/4) / (3/4) = 1/3
#   听话（让）  ： 2/3 × 6 + 1/3 × 2 = 4 + 2/3 = 14/3 ≈ 4.667
#   违抗（不让）： 2/3 × 7 + 1/3 × 0 = 14/3 ≈ 4.667
#   ⇒ 恰好一样。听话不吃亏。

★ 两条建议都不值得违抗 ⇒ 这套方案自己就站得住。

算一下每个人的期望收益：

我的期望收益 = 1/2 × 6 + 1/4 × 7 + 1/4 × 2 = 3 + 7/4 + 1/2 = 21/4 = 5.25
你的期望收益 = 同理 = 21/4 = 5.25
两人合计 = 21/2 = 10.5
撞车概率 = 0

这个 5.25 有多值钱

把所有方案排在一起：

方案	每人拿	合计	撞车概率	需要什么
混合纳什均衡	14/3 ≈ 4.667	28/3 ≈ 9.33	1/9	什么都不需要
公开抛硬币选一个纯均衡	4.5	9	0	一枚大家都看得见的硬币
信号灯（相关均衡）	21/4 = 5.25	21/2 = 10.5	0	一个只对本人说话的装置

请注意这不是「在几个纳什均衡之间选一个好的」。5.25 比任何纳什均衡都高，也比它们的任何混合都高。纳什均衡能给出的对称收益最高是 14/3 ≈ 4.667，抛硬币是 4.5，而信号灯是 5.25。

它到达了一个纳什均衡够不到的地方。

秘密在那个「悄悄」上。公开的硬币让两个人知道同一件事，所以他们只能在已有的格子里挑；而私下的建议制造了不对称的信息——我知道我该让，但不确定是因为你也要让、还是因为你要冲。正是这份不确定，让「让」这个动作变得划算。

✎ 术语正名

这个概念叫相关均衡（correlated equilibrium），Robert Aumann 在 1974 年提出。他因为博弈论方面的工作在 2005 年获得诺贝尔经济学奖。

定义很干净：一个关于「大家该做什么」的联合概率分布，如果每个人在收到自己那条建议后，照做都是最优的，它就是相关均衡。

纳什均衡是它的特例——当那个联合分布恰好是各自独立的时候。所以相关均衡的集合包含纳什均衡的集合，而且通常大得多。

它还有一个技术上的好处：好算

这一点在实践中可能比前面那些都重要。

求纳什均衡是困难的。即使是两人博弈，找一个纳什均衡的复杂度也被证明是 PPAD-完全的（Daskalakis、Goldberg、Papadimitriou 2006；Chen 与 Deng 2006）——一般认为没有高效算法。这本书前面那台「支撑枚举」求解器在 3×3 上跑得飞快，放到 30×30 就跑不动了。

而相关均衡的条件全是线性不等式：每个人对每一对动作的「照做不比换掉差」，写出来都是关于那个联合分布的线性约束。所以求相关均衡是一个线性规划，可以在多项式时间内解出来。

上面 demo 里那个 (1/2, 1/4, 1/4, 0) 就是这样解出来的——引擎用精确有理数单纯形，最大化两人收益之和，得到的答案是干净的分数。

还有第三个好处，接着上一章：无悔算法自然收敛到相关均衡（准确地说是它的一个近亲，粗相关均衡）。这三件事合起来是一个很强的组合：

它更好——能到达纳什够不到的地方；
它更好算——线性规划；
它更容易自发出现——一群只会最小化后悔的简单个体就会走到那儿。

这三条让一些博弈论学者认为，相关均衡才是比纳什均衡更该被当作默认答案的那个概念。

▸ 在现实里

红绿灯真的就是这个东西。它不能物理阻止你闯红灯，它只是给两个方向分别发指令。而每个司机计算之后都会发现：照做是自己的最优应对。它把一个每人 4.667、11% 撞车的局面，变成了每人 5.25、0% 撞车。

排班表、值班轮换、分布式系统里的 leader 选举。这些都是同一台机器：一个大家都接受的、能打破对称的随机装置。注意「大家都接受」这个条件——它对应的正是那些激励约束。一个没人愿意听的排班表，不是相关均衡。

为什么「随机分配」有时比「协商」更好。协商要花时间、会僵持、会让强势的一方占便宜；而一个事先约定好的随机装置，只要它满足激励约束，就能自己运转，一次都不用谈。这也是抽签、摇号、轮值这些古老制度背后的数学。

算法交易与拥塞控制。在多方共享资源的系统里，引入一个共同的随机信号源（比如带抖动的退避、共享的时间片）常常能显著改善整体表现——原理是同一个：打破对称，避免所有人同时冲。

✗ 这个直觉是错的

「要让大家协调起来，就得把信息公开，让所有人都知道所有人的计划。」

第 7 章确实讲过公开的价值——那是为了建立共同知识，解决协调问题（猎鹿）。但这一章给出了反例：在利益冲突的局里，让每个人知道得少一点，反而能到达更好的地方。

原因在那笔条件概率的账上：我被告知「让」的时候，正是因为我不确定你会不会冲，「让」才不吃亏。如果装置公开宣布结果，那个不确定性消失，我一看你也要让，立刻就想冲了——方案当场散架。

所以关于信息的正确问法不是「该不该公开」，而是：这个局是协调（大家想去同一个地方）还是冲突（大家想去不同的地方）？协调靠公开，冲突靠私下的、相关的建议。

◇ 摊牌

正确答案是 C：能到 21/4 = 5.25，比任何纳什均衡的任何混合都高。

A 「顶多 4.5」——这是公开抛硬币能到的地方，也是绝大多数人的第一反应。它的局限在于「公开」：所有人知道同一件事，就只能在两个不公平的格子之间切换，永远用不上「都让」那个各得 6 的格子。 B 「没有强制力就超不过纳什」——这个直觉很硬，但它把「强制力」和「相关性」搞混了。装置确实没有任何强制力（每个人都可以违抗），可它提供了相关的私人信息，而这本身就是一种资源。相关均衡的定义里恰恰要求「照做是最优的」——它是靠自愿运转的。 D 「能到 6」——「都让各得 6」这一格是全表总收益最高的（12），可它不可能被任何机制稳住：如果我确信你会让，我一定想冲（7 > 6）。任何试图把两人都锁在「让」上的方案都会被违抗。5.25 是在激励约束下能到达的最好位置——这才是机制设计的真实上限。

◆ 换你定规则

两个团队争抢同一个共享环境（测试机、发布窗口）。现在的做法是「谁先抢到谁用」，结果经常撞车，撞了两边都得重来。你不想引入审批。改什么？

各自抢 ⇒ 斗鸡博弈 ⇒ 均衡里必然有一定比例的撞车，而且双方都要一直保持戒备。装一个大家事先都同意的随机分配器：每个窗口随机指定优先方，只通知相关方。关键是让它满足激励约束——被指定为「让」的那一方，此刻确实不值得抢。做法通常是给让的一方一点补偿（下个窗口优先、或者更长的占用时段）。

请注意最难的部分不是随机，是让「听话」变成最优应对。一个没人愿意遵守的排班表，和红绿灯坏了没区别。

这一章的一句话

一个既不能强制也不能惩罚的装置，只要给每个人的建议是「相关的、私下的」，就能带所有人去一个纳什均衡够不到的地方——而它便宜到只是一盏灯。

下一章从纸上走出来，去看三台已经被写进代码、每天在跑的机制：一台在给拥堵标价，一台在拍卖「谁排前面」的权利（它没有被任何人设计过，是自己长出来的），还有一台每天在让全世界的组织朝着错误的方向努力——它叫 KPI。