形式陈述
在有限策略式博弈 理路 有限策略式博弈 Strategic-form game · Normal-form game · 标准式博弈 用玩家、有限策略集和收益函数描述相互影响的选择,并以固定他人策略后的单方偏离定义最佳回应。 中,协调者按联合分布 理路 概率分布 Probability distribution · Law 可测空间上总质量为一的测度;随机变量的律是由样本概率推出的一类分布。 μ 抽取剖面 s ,只向玩家 i 私下建议 s i 。玩家知道收益表和分布,可以看见自己的建议后决定是否服从。相关均衡要求,在每一种建议下,单方改换动作都不能提高期望收益。
对建议 a ∈ S i 和替代动作 b ∈ S i ,定义未归一化偏离增益
D i ( a → b ; μ ) = ∑ s : s i = a μ ( s ) [ u i ( b , s − i ) − u i ( s ) ] . 若对所有 i , a , b 都有 D i ( a → b ; μ ) ≤ 0 ,则称 μ 为相关均衡 (CE)。当 μ i ( a ) = Pr ( s i = a ) > 0 时,除以它可写成条件服从约束
E [ u i ( a , s − i ) ∣ s i = a ] ≥ E [ u i ( b , s − i ) ∣ s i = a ] . 若某个建议概率为零,原线性式自动为零,完全不需要定义零概率事件下的条件分布。有限条线性式因此比逐项写条件概率更适合核验和求解。
本页的 ε -CE 采用每条未归一化约束 D i ( a → b ; μ ) ≤ ε 的约定,ε ≥ 0 。它允许的条件收益改进是 ε / μ i ( a ) ,不是统一的 ε 。对于很少出现的建议,两种近似标准会差很多;精确的零误差定义则没有这一差别。
从条件偏离到遗憾
从单对改换到任意动作映射
一份确定的偏离规则是映射 ϕ : S i → S i :收到 a 时执行 ϕ ( a ) 。它的总期望增益为
∑ a D i ( a → ϕ ( a ) ; μ ) . 若所有单对约束都非正,任何映射的总增益也非正。反过来,选一个只把 a 改成 b 、其余动作保持原样的映射,就能恢复该条单对约束。因此,CE 等价于没有任何有利的动作映射。随机偏离规则仍只是确定映射的混合,不会产生额外约束。
粗相关均衡 理路 粗相关均衡 Coarse correlated equilibrium · CCE 对联合动作分布检验事先固定的单方偏离,并把经验分布的约束违反量精确写成平均外部遗憾。 只检查不看建议的固定偏离。固定改选 b 对应常值映射 ϕ ( a ) = b ,其增益为
D i ( b ; μ ) = ∑ a D i ( a → b ; μ ) . 内部遗憾与交换遗憾
对实际历史 s 1 , … , s T ,其中整数 T ≥ 1 ,单对内部遗憾记录“只重做当初选过 a 的那些轮次”:
I i ( a , b ) = ∑ t : s i t = a [ u i ( b , s − i t ) − u i ( s t ) ] . 将出现次数合并,经验分布满足 D i ( a → b ; μ ^ T ) = I i ( a , b ) / T 。因此所有内部遗憾都不超过 T ε ,恰好等价于本页约定的经验 ε -CE。这里比较的是同一段实际历史,并没有重新运行对手。
允许对每个原动作分别选择替代动作,得到交换遗憾(swap regret):
R i swap ( T ) = max ϕ : S i → S i ∑ t [ u i ( ϕ ( s i t ) , s − i t ) − u i ( s t ) ] = ∑ a ∈ S i max b ∈ S i I i ( a , b ) . 最后一步成立,是因为映射对不同 a 的选择互不约束。又因 I i ( a , a ) = 0 ,每个最大值非负,所以 swap regret 非负,且不小于外部遗憾 理路 遗憾与比较器类 Regret · Comparator class 用累计损失相对预先规定的比较器类最优值来评价在线决策。 。R i swap ≤ T ε 保证每条 CE 约束不超过 ε ;反过来,每条内部遗憾不超过 T ε 只给出 R i swap ≤ | S i | T ε 。零误差时两种条件等价,近似常数不能直接互换。
直觉
CE 的每条条件偏离增益都非正,固定偏离增益又是这些量的和,所以 CE 必然是 CCE。反向不成立,因为固定偏离对建议求和时,允许某些建议下的获利被其他建议下的损失抵消。CCE 页的三轮循环博弈已经给出精确反例:六条固定偏离增益全为零,但 0 → 1 的增益为 1 / 3 。
例子与边界
三轮与四轮历史的内部遗憾
例如 CCE 页三轮对角历史中,两位玩家各自的内部遗憾表相同:
原动作 a /替代 b
0
1
2
0
0
1
− 1
1
− 1
0
1
2
1
− 1
0
每行最大值为 1 ,所以交换遗憾为 3 ,最优映射为 ( 1 , 2 , 0 ) ,平均增益为 1 。每条 CE 线性约束则是表项除以 3 ,最小非负 ε 为 1 / 3 。四轮历史中 0 → 1 的累计增益为 2 、未归一化增益为 1 / 2 ,而条件于建议 0 的收益改进仍为 1 ;这具体展示了近似定义中的概率因子。
协调建议与边际乘积
先核验所有服从约束
考虑下面的非零和协调博弈。
行玩家/列玩家
L
R
U
( 3 , 2 )
( 0 , 0 )
D
( 0 , 0 )
( 2 , 3 )
令协调者以各 1 / 2 概率选择 U L 和 D R ,即
μ = ( 1 / 2 0 0 1 / 2 ) . 双方服从时的平均收益均为 5 / 2 。收到 U 的行玩家知道对方是 L ,改成 D 会从 3 降到 0 ;收到 D 时改成 U 则从 2 降到 0 。列玩家同理。乘上相应建议概率,四条非平凡 CE 约束为
玩家及改换
概率 × 条件收益差
未归一化增益
行:U → D
( 1 / 2 ) ( 0 − 3 )
− 3 / 2
行:D → U
( 1 / 2 ) ( 0 − 2 )
− 1
列:L → R
( 1 / 2 ) ( 0 − 2 )
− 1
列:R → L
( 1 / 2 ) ( 0 − 3 )
− 3 / 2
保持原动作的约束均为零,这就检查完全部八条约束。故 μ 是精确 CE,自然也是精确 CCE。
还能直接检查 CCE:行玩家固定选 U , D 的收益为 3 / 2 , 1 ,减去服从收益 5 / 2 ,增益为 − 1 , − 3 / 2 ;列玩家固定选 L , R 的增益为 − 3 / 2 , − 1 。如果把分布实现为两轮历史 U L , D R ,双方最大累计固定偏离增益均为 − 2 。负外部遗憾与精确均衡并不冲突。
相同边际为何失去稳定性
两人的边际都是 ( 1 / 2 , 1 / 2 ) 。若改成各自独立抽样,混合策略 理路 混合策略 Mixed strategy 将有限纯策略上的概率分布作为选择,独立抽样形成联合结果,并由支持集上的最佳回应刻画最优混合。 所产生的乘积分布为
ν = ( 1 / 4 1 / 4 1 / 4 1 / 4 ) . 两个失配格现在各有 1 / 4 概率,双方平均收益降到 5 / 4 。固定纯动作面对的对方边际没有变化,但服从基线已经下降:
玩家
第一纯动作的固定偏离增益
第二纯动作的固定偏离增益
行:U , D
3 / 2 − 5 / 4 = 1 / 4
1 − 5 / 4 = − 1 / 4
列:L , R
1 − 5 / 4 = − 1 / 4
3 / 2 − 5 / 4 = 1 / 4
所以 ν 不是精确 CCE,也不是 CE 或 Nash 均衡,其最小 CCE 误差为 1 / 4 。相关性原先让双方总能协调;保留个人频率却拆散共同出现的关系,会改变服从的收益。
对于乘积分布,CE 的每条约束进一步分解为
D i ( a → b ; ν ) = p i ( a ) [ U i ( b , p − i ) − U i ( a , p − i ) ] . 若 p 是 Nash 均衡,正支持动作全是最佳回应,上式非正;反过来,乘积 CE 是乘积 CCE,后者恰是 Nash 的纯偏离判据。故在乘积分布这一限定下 ,CE、CCE 与Nash 均衡 理路 Nash 均衡 Nash equilibrium · 纳什均衡 · 混合策略纳什均衡 每位玩家都无法在其他人策略固定时通过单方偏离增加期望收益;有限博弈总存在这样的混合策略剖面。 等价。一般联合分布没有这一限制,不能仅凭边际分布就判断稳定性。
推论与应用
CE 约束加上 μ ( s ) ≥ 0 、∑ s μ ( s ) = 1 ,组成关于联合概率的有限线性系统。给定一个候选分布时,逐项代入即可核验;收益表很大时,联合动作数仍可能随玩家数迅速增长,线性形式本身不等于输入规模总是小。
在重复博弈中,外部无遗憾控制事先固定偏离,得到 CCE;内部或交换无遗憾控制建议相关的改换,得到 CE。交换无遗憾算法 理路 交换无遗憾算法 Swap-regret minimization · Blum–Mansour reduction 以逐源动作的指数权重学习器和平稳分布构造交换无遗憾算法,证明有限轮界,并把平均乘积分布转成近似相关均衡。 为每个源动作维护一个指数权重学习器,通过平稳分布使费用相加,并给出有限轮CE误差及三轮账本。普通指数权重的固定动作界不能直接充当交换遗憾界;该页还明确区分分布反馈输出与实际采样历史。
参考资料