博弈的相关均衡（Correlated equilibrium）

微观经济理论与博弈论 · 知乎专栏 · · 2015-05-03 13:46

正文

（以下以性别博弈为例介绍相关均衡的概念。内容主要基于刚给出的一个答案的扩展，添加了例子和理论基础。）

性别博弈（Battle of the sexes）:

$% \begin{tabular} [c]{lll} & $F$ & $B$\\\cline{2-3}% $F$ & \multicolumn{1}{|l}{$2,1$} & \multicolumn{1}{|l|}{$0,0$}\\\cline{2-3}% $B$ & \multicolumn{1}{|l}{$0,0$} & \multicolumn{1}{|l|}{$1,2$}\\\cline{2-3}% \end{tabular}$

这个博弈有三个纳什均衡： $(F,F), (B,B), (\frac{2}{3}F+\frac{1}{3}B, \frac{1}{3}F+\frac{2}{3}B)$ 。相关均衡是比纳什均衡更一般的概念。

首先，每个相关均衡都是一个在策略组合的集合 $\{F,B\}\times \{F,B\}$ 上的概率分布（correlated distribution） $p$ ， $p$ 可以用下面的表格刻画

$% \begin{tabular} [c]{lll} & $F$ & $B$\\\cline{2-3}% $F$ & \multicolumn{1}{|l}{$a$} & \multicolumn{1}{|l|}{$b$}\\\cline{2-3}% $B$ & \multicolumn{1}{|l}{$c$} & \multicolumn{1}{|l|}{$d$}\\\cline{2-3}% \end{tabular}$ $% \begin{tabular} [c]{lll} & $F$ & $B$\\\cline{2-3}% $F$ & \multicolumn{1}{|l}{$1/2$} & \multicolumn{1}{|l|}{$0$}\\\cline{2-3}% $B$ & \multicolumn{1}{|l}{$0$} & \multicolumn{1}{|l|}{$1/2$}\\\cline{2-3}% \end{tabular}$

例如，这个概率分布会以概率 $b$ 抽取行动组合 $(F,B)$ ，并将 $F$ 推荐给第一个参与人， $B$ 推荐给第二个参与人。当第一个人收到推荐 $F$ 的时候，他并不知道对方收到的推荐是什么，但由于他知道概率分布如上，他的条件概率估计是对方以概率 $\frac{a}{a+b}$ 收到了推荐 $F$ ，以概率 $\frac{b}{a+b}$ 收到了推荐 $B$ 。（如果 $p$ 可以表示成两个参与人混合策略的乘积，那么 $p$ 本质上就是不包含任何correlation 的。而右上表给出的概率分布 $\frac{1}{2}FF+\frac{1}{2}BB$ 则不能由任何乘积表示，也容易看出在该分布下，双方的策略是高度相关的。）

$p$ 构成相关均衡的条件是，在按照 $p$ 随机抽取行动组合推荐给参与人时，每个参与人在接收到行动推荐后，给定根据 $p$ 计算出的对方收到的行动推荐的条件概率并假定对方会服从，那么他的最优选择就是服从推荐。

相关均衡是基于推荐的均衡，可以通过交通调度来理解。调度员只需要分别告诉每个司机他该走哪条路，司机收到调度指令后，根据调度分布算出调度员给其他人的指令的概率分布是什么（从而计算拥堵程度），如果该分布是均衡，在给定其他司机都会服从调度的情况下，每个司机都会发现服从调度是最优的。

从直观上，我们已经可以看出相关均衡和纳什均衡思路上的一致性：只要其他人服从均衡指定的推荐，那么自己服从推荐就是最优的。相关均衡更一般的地方在于，每个参与人自己得到的推荐和其他人的推荐可以是相关的，而在纳什均衡里，无论你选择什么，对方的（混合）策略都是独立于你的从而是给定的。

=====================================================

对于性别博弈，概率分布 $p$ 构成相关均衡的条件是：

1. 参与人1 在收到行动推荐 $F$ 时，选择 $F$ 是最优（即好过选择 $B$ ）。给定条件概率，我们可以计算出 $F$ 和 $B$ 分别带来的收益，得到不等式
$1F: \frac{a}{a+b}2+\frac{b}{a+b}0\geq\frac{a}{a+b}0+\frac{b}{a+b}1$

2. 同理，在1 收到推荐 $B$ 和 2 分布收到两个行动推荐时，服从推荐都需要是最优选择，于是如下三个不等式需要满足
$1,B & :0c+1d\geq2c+0d,\\ 2,F & :1a+0c\geq0a+2c,\\ 2,B & :0b+2d\geq1b+0d.$

整理后，得到
$a+b+c+d & =1,\\ a,b,c,d\geq 0\\ a,d & \geq2c\\ a,d & \geq b/2$

所有满足以上不等式组的 $a,b,c,d$ 所定义的概率分布 $p$ 都是性别博弈的相关均衡。由于以上不等式的解的集合是一个多面体（准确地说，是有五个顶点的六面体）和它的内部，相关均衡的集合自然就是一个凸集。并且该凸集包含纳什均衡的凸包。

相关均衡 $(a,b,c,d)=(1/2,0,0,1/2)$ 以一半概率选择 $(F,F)$ 一半概率选择 $(B,B)$ ，带来的期望支付是 $(3/2, 3/2)$ 是三个纳什均衡都达不到的。而相关均衡 $(a,b,c,d)=(1/4,1/2,0,1/4), (2/5, 0, 1/5, 2/5)$ 则不在三个纳什均衡构成的凸包中。

===========================================================

再举一个例子：

$% \begin{tabular} [c]{lll} & $F$ & $B$\\\cline{2-3}% $F$ & \multicolumn{1}{|l}{$6,6$} & \multicolumn{1}{|l|}{$2,7$}\\\cline{2-3}% $B$ & \multicolumn{1}{|l}{$7,2$} & \multicolumn{1}{|l|}{$0,0$}\\\cline{2-3}% \end{tabular}$

这个博弈有三个纳什均衡，带来的支付分别为： $(2,7), (7,2),(14/3, 14/3)$

可以检验 $1/3FF+1/3FB+1/3BF$ 构成相关均衡，并且带来的期望支付为 $(5,5)$ 高于纳什均衡支付的任意凸组合。

=============================================================

理论基础

给定一个博弈和它的一个相关均衡 $p$ ，由于 $p$ 本质上是一个correlating device， $p$ 给每个参与人推荐行动的过程可以理解成一个不完全信息的生成过程：每个参与人接收到自己的信息（行动推荐），同时产生了对他人信息（行动推荐）的概率估计。

在该博弈由相关均衡 $p$ 生成的不完全信息博弈中，每个参与人在每个信息状态下选择推荐的行动构成贝叶斯纳什均衡。

也就是说，如果我们在model 一个博弈的时候，有一部分与博弈支付无关而在参与人之间又相关的信息没有考虑到，从而把参与人事实上面临的不完全信息博弈理解成了完全信息博弈（想象你坐着直升机在天空观察并试图理解司机之间的博弈，却没有意识到司机们背后调度的存在），那么参与人之间博弈的贝叶斯纳什均衡事实上是我们考虑的完全信息博弈的相关均衡。（这部分抽象理论主要指向博弈的epstemic foundation，推荐阅读Aumann [1987]。）

References:

Aumann, R. (1974), Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics, 1, 67-96.

Aumann, R. (1987), Correlated equilibrium as an expression of Bayesian rationality, Econometrica, 55, 1-18.

Nau, R., Canovas, S.G., Hansen, P. (2004), On the geometry of Nash equilibria and Correlated equilibria, 32, International Journal of Game Theory, 443-453.