domination-avoiding learning agents cannot collude¶

会议: NeurIPS 2026
arXiv: 2606.01275
领域: 强化学习
关键词: 算法合谋, 占优规避, 重复博弈, 后悔值最小化, 伯特兰寡头竞争

一句话总结¶

本文证明了单纯的外部无后悔学习算法仍可在对数几率需求的伯特兰寡头竞争中合谋维持超竞争高价，并提出了更一般的“规避经验占优”（Domination-Avoiding, DA）学习智能体类别，在博弈论上严格证明了该类智能体无法合谋并必然收敛至竞争性纳什均衡邻域。

研究背景与动机¶

在现代数字经济中，自动化算法已被广泛部署于在线广告竞价、金融高频交易以及电商平台定价等核心场景。然而，多智能体在未知交互环境中的涌现行为往往难以预测。早期实证研究表明，当两个独立的 Q-learning 智能体置于经典的对数几率（Logit）需求伯特兰双头定价博弈中时，两者即使没有任何显式通信、协议或跨期报复机制，也会自发达成“算法合谋”（Algorithmic Collusion），将商品价格推升至垄断高位并瓜分约 70% 的超额利润；近期关于商业大语言模型（LLM）驱动的定价智能体研究也重现了这一自发合谋现象。这引发了学术界与反垄断监管机构的普遍担忧：算法合谋究竟是强化学习与大模型特有的产物，还是多智能体学习中普遍存在的顽疾？我们能否在理论上严格刻画并排除算法合谋的算法边界？

这一问题的核心矛盾在于：直觉上，追求自身效用最大化且具备“无外部后悔”（No-External-Regret）保证的经典学习算法（如乘法权重法 MW、扰动跟随领导者 FTPL）应当由于单步削价套利的诱惑而打破合谋并驱使价格逼近竞争性纳什均衡，甚至在数值仿真中也确实展现出了竞争性收敛；然而，无外部后悔保证在博弈论上仅能确保经验分布收敛至粗相关均衡（Coarse Correlated Equilibrium, CCE），而 CCE 集合本身是否潜藏着能够维持超额高价的合谋状态，此前在复杂的非线性对数几率需求市场中缺乏严格的理论定论。与此同时，此前文献试图通过“基于均值”（Mean-Based）的算法性质来排除合谋，但该性质对历史累积算术平均极其敏感，学习率衰减或引入有限上下文记忆便会破坏该条件，且所有无内部后悔算法均不属于基于均值类。

本文的核心 idea 是形式化定义一类更通用且稳健的“规避占优智能体”（Domination-Avoiding Agents）——仅要求智能体几乎不选择在历史上绝大部分轮次都严格劣于某一替代动作的经验占优动作；并从理论上双向击穿：一方面反例构造证明纯外部无后悔确实允许合谋，另一方面从博弈论严格证明规避占优智能体在多玩家博弈中绝不可能选择严格纯占优策略迭代消除（IESPDS）筛掉的动作，从而在对数几率伯特兰博弈中彻底杜绝合谋并收敛至纳什均衡邻域。

方法详解¶

整体框架¶

本文的方法论由两部分互为对照的严密理论体系构成：首先，针对外部无后悔算法，构造一个支撑在超竞争价格上的双峰粗相关均衡（CCE），形式化证明外部无后悔自身不足以阻止合谋；其次，建立“规避占优智能体”（DA）的行为公理，并建立其与严格纯占优策略迭代消除（IESPDS）的全局对应定理，进而推导其在离散伯特兰对数几率定价博弈中的双向收缩收敛性。

整个判定与收敛逻辑如下图所示：

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["多智能体重复定价交互环境<br/>(伯特兰对数几率需求模型)"] --> B["反例机制：构造合谋粗相关均衡<br/>基准价与极高价混合使得单方偏离不盈利"]
    A --> C["条件放宽：规避经验占优准则<br/>经验劣势动作选择频率渐进趋近于零"]
    C --> D["博弈论动态：IESPDS 级联消除<br/>由局部存活动作不可被占优诱导全局淘汰"]
    D --> E["双向边界消除：上下阈值收缩<br/>高价削价严格占优与低价抬价严格占优"]
    E --> F["纳什均衡竞争性定价收敛<br/>渐进以全概率集中在均衡 2ε 邻域"]

关键设计¶

1. 极端双峰 CCE 构造：证明无外部后悔仍可维持任意高合谋价格

为了打破“无外部后悔即消除合谋”的直觉误区，论文在归一化伯特兰对数几率双头博弈（无外部选项 $\alpha=0$、边际成本 $c=0$、价格敏感度 $\mu=1$，竞争性纳什均衡价格 $p^*=2$）中构建了一个反例。针对任意给定的目标超竞争高价 $V > p^*$，构造支撑在基准高价 $p_L = V$ 和极高奖励价 $p_H \gg p_L$ 上的对称联合分布 $\sigma_{CCE}$： $$ \sigma_{CCE} = \begin{cases} (p_L, p_L) & \text{以概率 } q = \frac{p_H}{p_L + p_H} \ (p_H, p_H) & \text{以概率 } 1-q = \frac{p_L}{p_L + p_H} \end{cases} $$ 由于满足 $q p_L = (1-q) p_H$，均衡预期收益为 $U_{CCE} = q p_L$。通过调大 $p_H$ 使得 $p_H^2 e^{-p_H / p_L} \leq p_L^2 e^{-p_L}$，论文将偏离空间以临界阈值 $\hat{p} = p_H / p_L$ 划分为低偏离与高偏离两段：低偏离因对手维持高价而受到最大获利上界 $u_{max}(p_{-i}) < p_{-i} - 1$ 的限制而无利可图；高偏离则由于对数几率需求的指数衰减使得在对战 $p_L$ 时收益呈指数级衰减，同样无法击败 $U_{CCE}$。这在数学上首次严格坐实了：即便双方算法都在最小化外部后悔，也完全可能陷入合谋高价的 CCE 动态之中。

2. 规避经验占优（Domination-Avoiding）行为准则：极度宽松的防合谋充分条件

为寻找能够彻底排除合谋的最弱必要约束，本文提出了比“基于均值”（Mean-Based）弱得多的“规避经验占优”（DA）定义。如果某个动作 $a$ 在历史截至 $t$ 步中，优于或等于替代动作 $a'$ 的轮次占比不超过 $\delta$（即 $|\{s \le t \mid r^s(a) \ge r^s(a')\}| \le \delta t$），则称 $a$ 是 $\delta$-经验占优的。智能体满足 DA 性质，若对任意对抗环境及任意误差容忍度 $\epsilon > 0$，均存在常数 $\delta > 0$，使得其在均匀采样时间或上时间平均（Upper-Time-Average, UTA）下选择 $\delta$-经验占优动作的概率不超过 $\epsilon$： $$ \operatorname{UTA}({d^t(\delta)}) = \limsup_{T \to \infty} \frac{1}{T} \sum_{t=1}^T \Pr[a^t \text{ 在时间 } t \text{ 是 } \delta\text{-经验占优的}] \le \epsilon $$ 与 Mean-Based 强制要求历史算术平均收益不落后不同，DA 准则只要求智能体最终学会放弃那些“在历史上几乎一直都表现很差”的动作。论文证明了庞大的算法家族均严格满足 DA：包括虚构博弈（Fictitious Play）、有限时域 Mean-Based 配合翻倍技巧（Doubling Trick）、无限时域 Mean-Based、采用递减学习率 $\eta^t \propto t^{-\beta}$（$\beta \in (0,1)$）的无限时域乘法权重法（MW）、无内部后悔/无交换后悔算法（No-Swap-Regret，反证法借助 Lipschitz 连续性与 Jensen 不等式证明违背 DA 必将累积正的交换后悔），以及在有限上下文状态下独立运行 DA 的上下文学习智能体（Contextual DA）。

3. IESPDS 级联消除定理与双侧连续阈值收缩

在多智能体交互机制上，论文证明了任何有限博弈中，相互博弈的 DA 智能体所构成的存活动作集合 $S_i$（定义为选择概率的上时间平均大于 0 的动作）必须能够被对手的存活动作分布所辩护（Justifiable）。一旦某个动作在对手存活集合下被严格纯占优，对手非存活动作出现的频率渐进归零，导致该动作必然在经验上被 $\delta$-占优，迫使其选择频率归零。这一矛盾建立起数学归纳法：所有能够被严格纯占优策略迭代消除（IESPDS）剔除的动作，其被选取的渐进概率均为零。

为将此定理应用到具有连续对数几率需求的离散价格网格 $\mathcal{P}$（网格最大步长为 $\epsilon$），论文定义了两个参数化的连续非递增阈值函数 $\Phi^+(p)$ 与 $\Phi^-(p)$： $$ \Phi^+(p) = c + \frac{\epsilon}{1 - e^{-\mu \epsilon}} \left[1 + \frac{1}{1 + \alpha e^{\mu p}}\right], \quad \Phi^-(p) = c + \frac{\epsilon}{e^{\mu \epsilon} - 1} \left[1 + \frac{1}{1 + \alpha e^{\mu p}}\right] $$ 两者的不动点 $p^+$ 与 $p^-$ 恰好紧密夹逼连续纳什均衡 $p^*$（$p^- < p^* < p^+ \le p^- + 2\epsilon$）。通过微积分与严格占优条件证明： - 自顶向下消除：对于任意价格 $p^{(j)} > p^+$，只要对手出价上限不超过 $p^{(j)}$，单方削价至相邻格点 $p^{(j-1)}$ 均严格占优；最高价格被级联消除，直至上限收缩到 $p \le p^+$； - 自底向上消除：对于任意价格 $p^{(j)} < p^-$，只要对手出价下限不低于 $p^{(j)}$，单方抬价至相邻格点 $p^{(j+1)}$ 均严格占优；最低价格被级联消除，直至下限收缩到 $p \ge p^-$。

最终网格中唯有落在 $[p^* - 2\epsilon, p^* + 2\epsilon]$ 这一 $2\epsilon$ 紧密邻域内的价格能够存活，DA 智能体的出价渐进以全概率集中在竞争价格区间，彻底消除合谋。

为什么 Q-learning 智能体能够合谋而 DA 智能体不能¶

许多学者曾认为 Q-learning 的合谋源自其具有“状态（State/Context）”（例如记录上一轮的价格）。但本文从理论上指出了决定性差异：具有有限上下文状态的 DA 智能体依然受到 DA 性质约束而无法合谋。Q-learning 之所以能够实现合谋，是因为其优化目标并非即时收益，而是即时收益加上后续状态的未来折现预期价值总和（Bellman 方程）。当 Q-learning 智能体交互时，它们学会了“当前若单方面削价套利，会导致系统转移到容易诱发全面价格战的低价状态，从而摧毁长远利益”。这种推迟满足（Delay of Gratification / 棉花糖测试）的远期规划能力使它们甘愿承受短期的次优以维系高额垄断租金；而 DA 智能体由于缺乏跨期远瞻，必然会抓住眼前的严格占优削价套利机会，从而从根本上瓦解任何超竞争价格联盟。

实验关键数据¶

主实验：经典学习动态在对数几率伯特兰博弈中的收敛轨迹¶

论文基于 Calvano 等人（2020）的标准实验基准设定：商品内在效用 $a=2$、外部选项效用 $a_0=0$、边际生产成本 $c=1$、价格敏感度 $\mu=4$，离散定价网格由覆盖连续竞争性均衡至垄断基准的 15 个等间距价格组成。对于无外部后悔算法（乘法权重 MW、跟随扰动领导者 FTPL），学习率固定为 $5 \times 10^{-3}$，总仿真轮次达到 $10^6$ 步。

实验对比了不同算法最终收敛的价格状态、利润捕获率（Profit Gain，定义为相对于纳什均衡利润到垄断利润差距的捕获比例）以及经验占优策略规避特性：

算法类别	算法实例	理论性质归属	渐进出价收敛位置	垄断利润捕获率 (%)	是否自发算法合谋
强化学习 (RL)	Q-Learning (Calvano et al.)	跨期折现长远价值优化 (非 DA)	稳定维持在超竞争垄断高价	$\approx 70.0\%$	是 (自发维持合谋)
大语言模型	Commercial LLMs (Fish et al.)	自回归提示与上下文长远决策	显著高于竞争价格的超额定价	显著正利润增益	是 (自发合谋)
外部无后悔	MW (Constant $\eta=5\times 10^{-3}$)	Mean-Based & Domination-Avoiding	严格收敛于竞争纳什均衡 $p^*$	$0.0\%$	否 (完全竞争)
外部无后悔	FTPL (Perturbation $\epsilon=5\times 10^{-3}$)	Mean-Based & Domination-Avoiding	严格收敛于竞争纳什均衡 $p^*$	$0.0\%$	否 (完全竞争)
构造性反例	Bimodal CCE Agent ($\sigma_{CCE}$)	No-External-Regret (非 DA)	任意指定超高价 $V \gg p^*$	$\to 100\%$ (或更高)	是 (理论允许合谋)

消融实验：不同算法族在 DA 判定准则与抗合谋性上的理论消融¶

论文深入分析了不同算法公理体系在抗合谋性（Convergence to Competitive Price）与规避经验占优（Domination-Avoiding）上的充要关系，消融了不同约束条件对规避合谋的理论有效性：

算法性质约束	包含的经典算法	是否属于 Mean-Based	是否属于 Domination-Avoiding	是否能从理论上排除合谋
No-External-Regret (一般外部无后悔)	任意使 $R(T)/T \to 0$ 的动态	否 (存在反例)	否 (存在反例)	否 (定理 1 构造出超高价合谋 CCE)
No-Swap-Regret (内部/交换无后悔)	Hart-Mas-Colell 算法等	否 (Deng et al. 2019 证明互斥)	是 (定理 4.4 证明)	是 (由定理 2 与推论 3 保证)
Mean-Based (固定学习率 / 有限时域)	固定 $\eta$ 的 MW, FTPL, EXP3	是 (定义符合)	是 (配合 Doubling Trick, 定理 4.2)	是 (由定理 2 保证)
Decaying-Rate MW (递减学习率)	$\eta^t = \lambda t^{-\beta}$, $\beta \in (0,1)$	否 (违反累积均值严格要求)	是 (定理 4.3 积分放缩证明)	是 (由定理 2 保证)
Contextual DA (有限上下文记忆)	基于上一轮历史出价的 S-EXP3	视底层算法而定	是 (定理 4.5 证明有限上下文封闭)	是 (由定理 2 保证)
Q-learning (带折扣跨期优化)	经典表格式 Q-learning	否	否 (甘愿承受短期受占优动作)	否 (能够通过转移状态惩罚维系合谋)

关键发现¶

外部无后悔不足以防范合谋：虽然无外部后悔在数值实验中（如 MW 和 FTPL）往往收敛于竞争均衡，但这完全是因为这些具体算法恰好具备更强的规避经验占优特性。通用外部无后悔本身允许极端双峰 CCE，完全可在理论上支持任意高额的合谋价格。
内部无后悔天然杜绝合谋：尽管内部无后悔（No-Swap-Regret）算法在数学上已被证明不能是 Mean-Based 算法，但它们全集都严格属于 Domination-Avoiding 智能体，因此在任何多玩家博弈中都能自动消除迭代严格纯占优策略。
抗合谋的理论边界在于“短视性”而非“状态记忆”：拥有有限前序博弈历史（Context）并不会带来合谋；合谋的唯一根源在于智能体是否试图优化长远跨期收益（未来回报贴现）。无法通过“延迟满足”的智能体必然因局部削价占优而击碎合谋。

亮点与洞察¶

颠覆性理论反例：在具有广泛现实意义的对数几率弹性需求双头市场中，构造了纯外部无后悔算法可以合谋支撑任意高价的严格 CCE，弥补了此前仅在低价全赢等简化拍卖模型中存在反例的理论空白。
精准提炼最弱行为公理：跳出了过于严苛、脆弱且与内部无后悔互斥的 Mean-Based 框架，提出了概念更自然、鲁棒性更强且对有限上下文封闭的 Domination-Avoiding 定义，为算法反垄断提供了极其坚实的博弈论抓手。
双向边界收缩的微积分精妙证明：在离散网格上将对数几率需求的非线性导数巧妙化解为上界削价与下界抬价的统一严格占优条件，通过几何极限证明了当网格精细化（$\epsilon \to 0$）时出价窗口精确收缩至纳什均衡本身。

局限与展望¶

反向合作机制的缺失：在经济反垄断语境下合谋是有害的，但在自动驾驶车队调度、去中心化算力分配或多机器人协作等社会有益场景中，无中心协调的自发合作是极度渴望的特性。DA 智能体因为无法通过“棉花糖测试”而天然无法达成有益合作，如何精准设计兼顾防范恶性定价合谋同时保留良性跨期协同的机制仍待解决。
纯策略占优与混合策略占优的鸿沟：本文理论建立在严格纯策略占优迭代消除（IESPDS）之上；然而在某些非超模博弈或更复杂的混合策略均衡博弈中，纯策略消除可能无法收缩至单一均衡点，拓展到混合占优消除将是重要的理论挑战。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次形式化定义 Domination-Avoiding 概念并证明了多智能体 IESPDS 收敛与反合谋等价性。
实验充分度: ⭐⭐⭐⭐ 理论推导完备严密，附带数值仿真与对数几率伯特兰博弈的基准校验。
写作质量: ⭐⭐⭐⭐⭐ 概念动机阐述极为透彻，数学推导层层递进，对“棉花糖测试”与跨期价值的经济学直觉把握深刻。
价值: ⭐⭐⭐⭐⭐ 为解决数字经济中的算法合谋与反垄断监管提供了强有力的博弈论与多智能体强化学习理论基石。

算法性质约束	包含的经典算法	是否属于 Mean-Based	是否属于 Domination-Avoiding	是否能从理论上排除合谋
No-External-Regret (一般外部无后悔)	任意使 \(R(T)/T \to 0\) 的动态	否 (存在反例)	否 (存在反例)	否 (定理 1 构造出超高价合谋 CCE)
No-Swap-Regret (内部/交换无后悔)	Hart-Mas-Colell 算法等	否 (Deng et al. 2019 证明互斥)	是 (定理 4.4 证明)	是 (由定理 2 与推论 3 保证)
Mean-Based (固定学习率 / 有限时域)	固定 \(\eta\) 的 MW, FTPL, EXP3	是 (定义符合)	是 (配合 Doubling Trick, 定理 4.2)	是 (由定理 2 保证)
Decaying-Rate MW (递减学习率)	\(\eta^t = \lambda t^{-\beta}\), \(\beta \in (0,1)\)	否 (违反累积均值严格要求)	是 (定理 4.3 积分放缩证明)	是 (由定理 2 保证)
Contextual DA (有限上下文记忆)	基于上一轮历史出价的 S-EXP3	视底层算法而定	是 (定理 4.5 证明有限上下文封闭)	是 (由定理 2 保证)
Q-learning (带折扣跨期优化)	经典表格式 Q-learning	否	否 (甘愿承受短期受占优动作)	否 (能够通过转移状态惩罚维系合谋)