Mitigating Retaliatory Algorithmic Collusion in Repeated Games¶
会议: NeurIPS 2026
arXiv: 2609.20548
OpenReview: https://openreview.net/forum?id=qqcl0vdJhL
领域: 强化学习
关键词: 算法合谋、重复博弈、简单惩罚码、总变差距离、奖励重塑
一句话总结¶
本文形式化证明了重复博弈中基于报复惩罚维持的算法合谋必然在智能体策略间诱导可检测的总变差距离下界，并据此提出 CURB 框架，通过在 Q-learning 中惩罚该 TV 信号并辅以单方面偏离未受惩罚的合成信念注入，理论上消除了非平凡惩罚码不动点，在 Bertrand 与 Cournot 博弈中将合谋指数降至近乎零。
研究背景与动机¶
在重复交互的多智能体强化学习中，即使各智能体完全去中心化且不进行任何显式通信或协议签署，追求自身长期收益的 Q-learning 智能体仍能自发收敛到损害第三方福利的超竞争合谋状态。例如在租赁定价和电子商务中，算法定价系统自发形成了维持高价、惩罚单方面降价的隐性卡特尔。以往针对算法合谋的干预多局限于特定经济场景（如特定拍卖机制设计）或依赖具备集中仲裁权的平台规则，亦或是事后审计与调整探索率等启发式超参数，缺乏在一般重复博弈博弈论根基上瓦解合谋生成机理的普适干预框架。
已有实证研究揭示，自发收敛至合谋状态的 Q-learning 智能体在行为模式上高度契合博弈论经典 Simple Penal Codes（简单惩罚码，SPC）结构：各方在合作路径上获取超额利润，一旦有智能体单方面背叛（如降价抢占市场），其余对手会立即转移至报复性惩罚路径压低整体收益，直至合谋秩序重建。然而，Abreu 的 SPC 理论与 Q 学习算法动态之间的形式化数学桥梁此前从未被建立，使得监管与算法设计者无法从均衡结构上证明何种干预能够彻底根除依赖报复威胁维持的合谋均衡。
本文的切入角度是：惩罚路径的存在必然要求智能体的未来动作分布对对手历史是否发生背叛产生强条件依赖，只要在学习动力学中精准剥离这种报复威胁的经济激励，合谋基础便不复存在。核心 idea：将算法合谋与简单惩罚码（SPC）建立精确映射，证明非平凡报复惩罚必然诱发策略在合作与背叛历史间的总变差（TV）距离存在严格正下界，并提出通过 TV 距离奖励重塑消除报复不动点、结合合成未报复经验信念注入诱导竞争偏离的 CURB 框架。
方法详解¶
整体框架¶
CURB（Collusion Unwinding via Reward shaping and Belief injection）的设计目标是在不改变底层博弈规则和环境收益函数、不依赖中心化平台干预的前提下，作为智能体独立的学习算法插件运行。整个方法由“背叛判定与历史动作跟踪”、“基于滞后条件总变差（TV）距离的奖励重塑惩罚”以及“周期性合成非报复经验的信念注入”三个协同部分构成。
在每个博弈阶段，各智能体观察当前状态并根据其 Q 策略选择动作并获得环境收益，所有智能体的联合动作被推入长度为 \(W\) 的滑动历史窗口 \(\mathcal{H}\) 中。各智能体利用在线偏离准则判定对手动作是否属于背叛，并据此统计对手在“合作”与“背叛”两类历史条件下自身对应动作分布的总变差距离。当该 TV 距离非零时，奖励重塑机制在 Q 学习更新目标中扣除正比于最大对手 TV 距离的惩罚项；同时，系统以固定周期向回放缓存注入假设自身背叛而对手未实施报复的合成转移样本，打破智能体对“偏离必遭报复”的悲观预期。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["环境交互与联合动作历史"] --> B["背叛判定准则划分历史"]
B --> C["滞后条件分布总变差距离检测"]
C --> D["TV距离惩罚重塑奖励"]
D --> E["无报复合成经验信念注入"]
E --> F["竞争性非合谋策略收敛"]关键设计¶
1. 简单惩罚码与总变差距离检测下界：将博弈论报复机制转化为可检测的统计信号
为了从数学上捕捉智能体策略是否正在执行报复性惩罚码，论文在两阶段重复博弈与非平凡 SPC \(\sigma(Q^0, Q^1, \dots, Q^n)\) 假设下分析了智能体的策略依赖性。在 Abreu 的 SPC 理论中，合谋得以维持的充要条件是单期偏离收益被后续惩罚造成的延续价值损失所抵消，即 \(\Delta_j(q_j^*, q_{-j}^i(t)) \le v_j(Q^i; t+1) - v_j(Q^j)\)。如果一个 SPC 是非平凡的（即惩罚路径不同于合作路径），延续价值的严格差距必然要求对手智能体在观察到偏离后的动作分布与合作状态下的动作分布产生实质性偏离。
论文严格证明了 Proposition 2：对于任意贴现因子 \(\delta \in (0, 1)\)，非平凡 SPC 必然导致智能体策略在背叛分区 \(\mathcal{D}_i\) 与合作分区 \(\mathcal{C}_i\) 下的条件动作分布满足总变差距离下界： $$ |\pi_j(\cdot \mid a_i^{t-1} \in \mathcal{D}i) - \pi_j(\cdot \mid a_i^{t-1} \in \mathcal{C}i)| \ge \varepsilon^(\delta) = \frac{(1-\delta)\Delta^}{r > 0 $$ 即使背叛判定准则存在分类噪声（精度为 } - r_{\min}\(1-\alpha\) 且 \(\alpha < \varepsilon^*(\delta)/2\)），可观测的经验 TV 距离依然保持严格正下界 \(\varepsilon^*(\delta) - 2\alpha > 0\)。反之，平凡 SPC（如重复进行单阶段纳什均衡）不依赖历史进行相依惩罚，其 TV 距离恒等于零。这表明 TV 距离是对报复性合谋策略充分且必要的敏感检测算子。
2. TV 距离惩罚重塑奖励：消除非平凡惩罚码不动点的理论保证
基于检测下界，CURB 在智能体 \(j\) 的 Q-learning 收益函数中显式加入针对报复行为的负向重塑惩罚。智能体 \(j\) 在时间步 \(t\) 接收到的重塑奖励为： $$ r_j^{shaped}(s_t, a_t) = r_j(s_t, a_t) - \lambda \cdot \max_{i \ne j} |\hat{\pi}_j(\cdot \mid a_i^{t-1} \in \mathcal{D}_i) - \hat{\pi}_j(\cdot \mid a_i^{t-1} \in \mathcal{C}i)| $$ 其中滑动窗口 \(W=500\) 统计滞后 1 期的条件动作频率。论文证明了核心理论 Theorem 1：当惩罚系数 \(\lambda\) 超过临界阈值 \(\lambda^* = \frac{r_{\max} - r_{\min}}{\varepsilon^*(\delta) - 2\alpha}\) 时，任何非平凡 SPC 都不再是重塑后 Q 学习动力学的贪心策略不动点。
其核心证明逻辑在于：若智能体维持非平凡报复，每一步都会恒定承担至少 \(\lambda(\varepsilon^*(\delta) - 2\alpha)\) 的 TV 惩罚，折现后在 Q 函数中累积损失 \(\frac{\lambda(\varepsilon^*(\delta) - 2\alpha)}{1-\delta}\)；而若智能体切换到无论对手是否背叛均执行原合作行为的条件不变量策略，虽然会损失未惩罚对手带来的环境收益差额（上界为 \(\frac{r_{\max}-r_{\min}}{1-\delta}\)），但罚项节省完全压过了收益损失。因此，贪心策略必将偏向不实施惩罚的不变量策略，强行迫使所有合谋惩罚码退化为平凡惩罚码 \(\sigma(Q, Q, Q)\)。
3. 无报复合成经验信念注入：打破单方面偏离引发的悲观合谋预期
尽管 TV 奖励重塑能够消除通过报复威胁维持的非平凡合谋，但博弈论上可能存在双方均无条件选择垄断高价的平凡弱均衡状态（即双方缺乏偏离动力，固守高价）。合谋之所以在探索中难以自发瓦解，是因为智能体 \(i\) 的 Q 表记住了“一旦单方面降价/增产就会招致价格战惩罚，导致长期收益下降”的历史经验。
为了打破这种错误的报复预期，CURB 设计了信念注入机制：每隔 \(k=100\) 个环境交互步，算法向各智能体注入 \(m=5\) 条合成转移经验 \((s, a_i \in \mathcal{D}_i, \text{no retaliation by } j)\)，在该合成状态中智能体单方面执行背叛动作获得解析上的最高暴利，而对手依旧保持合作不实施报复。在表格 Q 学习中该经验直接触发单步 Q 表更新，在 DQN 中则写入经验回放缓存。这种反事实体验将背叛动作的期望 Q 值迅速拉升，从动力学上激发智能体单方面偏离垄断高价的积极性，促使系统朝竞争性纳什均衡轨道收敛。
实验关键数据¶
主实验¶
实验涵盖 Bertrand 价格竞争（离散动作网格 \(K=15\)，Logit 需求模型）与 Cournot 产量竞争两种经典重复博弈，基准对比包括无干预自发合谋基线、Calvano 等人提出的非完美监控（Imperfect Monitoring）、以及 Johnson 等人依赖中心化平台分发权的 PDP 与 DPDP 规则。合谋程度采用合谋指数 \(\mathrm{CI} = (\bar{\pi} - \pi^{\text{Nash}}) / (\pi^{\text{Mono}} - \pi^{\text{Nash}})\) 衡量，\(\mathrm{CI}=0\) 代表完全处于竞争性单阶段纳什水平，\(\mathrm{CI}=1\) 代表实现完全垄断合谋。
表 1 展示了 Bertrand 双寡头竞争下不同干预机制的最终收敛价格与合谋指数对比（20 个随机种子均值与标准差）：
| 干预机制 | 智能体 0 均价 (\(p_0\)) | 智能体 1 均价 (\(p_1\)) | 合谋指数 (CI) | 竞争对称性与特征 |
|---|---|---|---|---|
| 无干预基线 (No intervention) | \(1.8142 \pm 0.0618\) | \(1.8239 \pm 0.0669\) | \(0.8824 \pm 0.1067\) | 自发收敛至高垄断价合谋 |
| 平台机制 PDP (Johnson et al.) | \(1.4464 \pm 0.0213\) | \(1.7198 \pm 0.1266\) | \(0.0706 \pm 0.0786\) | 定价高度不对称，偏向特定卖家 |
| 平台机制 DPDP (Johnson et al.) | \(1.5164 \pm 0.1171\) | \(1.5671 \pm 0.1317\) | \(0.0426 \pm 0.0408\) | 依赖中心化平台算法控制展现 |
| CURB (\(\lambda=0.2\)) | \(1.4729 \pm 0.0000\) | \(1.4748 \pm 0.0082\) | \(0.0029 \pm 0.0124\) | 完全对称收敛至纳什价格 |
| CURB (\(\lambda=0.5\)) | \(1.4729 \pm 0.0000\) | \(1.4748 \pm 0.0082\) | \(0.0020 \pm 0.0086\) | 近乎消除合谋 (\(\text{CI} \to 0\)) |
消融实验¶
表 2 总结了 Bertrand 与 Cournot 环境下 CURB 各组件消融、散度度量形式以及智能体规模扩展的对比结果：
| 配置 / 实验环境 | 核心设置 | 合谋指数 (CI) | 说明 |
|---|---|---|---|
| Bertrand 完整 CURB | \(\lambda=0.2\), TV 重塑 + 信念注入 | \(0.0029 \pm 0.0124\) | 完整模型，合谋基本完全被瓦解 |
| Bertrand 仅 TV 重塑 (TV-only) | \(\lambda=0.2\), 无信念注入 | \(\approx 0.38 \sim 0.45\) | 报复削弱但仍停留于部分弱合谋 |
| Bertrand 仅信念注入 (Belief-only) | \(\lambda=0.0\), 仅周期性注入合成样本 | \(\approx 0.85\) | 仍形成报复机制，合谋指数接近基线 |
| Bertrand 惩罚强度不足 | \(\lambda=0.05\) (低于理论临界值) | \(\approx 0.86\) | 惩罚额度无法抵消报复获得的贴现价值 |
| Bertrand 替代散度 JSD-norm | \(\lambda=0.2\), 归一化 Jensen-Shannon | \(\approx 0.32\) | 弱于 TV 距离的抑制强度 |
| Bertrand 替代散度 JSD-raw | \(\lambda=0.2\), 原始 Jensen-Shannon | \(\approx 0.55\) | 尺度较小导致惩罚力度不足 |
| Bertrand 扩展三智能体 (\(n=3\)) | \(\lambda=0.5, 2\times 10^7\) 步 | \(\approx 0.01\) | 成功推广至多智能体寡头博弈 |
| Cournot 产量博弈基线 | 无干预，确定性线性逆需求 | \(\approx 0.82\) | 自发削减产量形成高额合谋利润 |
| Cournot 非完美监控 (Calvano et al.) | 需求截距均匀扰动，仅观测市场价 | \(\approx 0.40\) | 无法根除合谋 |
| Cournot 完整 CURB | \(\lambda=0.5\), 产量中位数判定 | \(\approx 0.00\) | 产量恢复至纳什水平 (\(q^{\text{Nash}}\)) |
| 深度强化学习 DQN-Bertrand | 3层MLP，回放缓存 \(10^4\)，\(\lambda=0.5\) | \(\approx 0.03\) | 成功推广至神经网络函数拟合智能体 |
关键发现¶
- 组件协同不可或缺：单独使用 TV 距离奖励重塑仅能部分削弱合谋（CI 从 0.88 降至约 0.4），单独使用信念注入则基本无效（CI 接近 0.85），唯有两者结合才能将 CI 彻底打穿至零。这印证了理论判断：TV 惩罚消除报复威胁，信念注入主动打破僵局。
- 惩罚阈值效应显著：实验观察到与理论公式相吻合的相变阈值现象。当 \(\lambda \le 0.05\) 时，算法行为与无干预基线几无二致；一旦 \(\lambda \ge 0.2\)，惩罚强度跨过临界值 \(\lambda^*\)，合谋指数发生断崖式下跌并稳定收敛在纳什均衡点。
- 强制背叛诊断验证机制保真度：在收敛模型的测试阶段人为注入强制单方面偏离时，无干预基线下的对手会立即降价报复形成数轮价格战；而在 CURB 干预下，对手价格轨迹平稳无波澜，完全验证了报复响应已被精准消除。
亮点与洞察¶
- 首次将 Abreu 惩罚码理论转化为端到端强化学习约束：论文没有停留在合谋现象的经验性描述，而是通过数学定理将博弈论中维持合谋所必需的报复惩罚码，精确映射为动作条件概率分布的 TV 距离正下界，提供了坚实的理论立足点。
- 去中心化且不侵入环境规则的抗合谋设计：以往方案往往依赖第三方平台对买家流量进行干预（如 PDP 会导致卖家间定价严重不对称），CURB 仅作用于智能体自身的学习更新规则，不仅完全保留了对称定价的公平性与消费者选择多样性，更无需任何外部协调机构。
- 跨博弈形式与跨算法架构的强迁移性：同一套基于滞后条件分布统计与反事实注入的思路，在 Bertrand 价格博弈、Cournot 产量博弈以及表格 Q 学习和深度 DQN 网络中均展现出极其稳健的合谋瓦解能力，为算法合谋的治理提供了通用范式。
局限与展望¶
- 多智能体理论保证尚存空白：当前 Theorem 1 的严格形式化证明仅针对 \(n=2\) 的双寡头博弈环境，尽管多智能体实验表明基于最大 TV 距离的扩展在 \(n=3\) 时经验有效，但 \(n > 2\) 时惩罚分摊与背叛认定的形式化理论尚待补全。
- 依赖领域知识指定偏离判定方向：背叛准则 \(\phi_i\) 目前基于滑动历史中位数（如价格低于中位数或产量高于中位数），对于更加复杂的高维动作空间或非线性博弈结构，如何无监督自适应提取偏离信号仍具挑战。
- 信念注入机制尚缺收敛性理论证明：信念注入在实验中对推动收敛至纳什均衡至关重要，但目前作为一种强化学习探索启发式手段，尚未具备收敛速率与稳态分布的形式化证明。
相关工作与启发¶
- vs Calvano et al. (AER 2020 / IJIO 2021): Calvano 等人首次在实证上指出 Q-learning 智能体自发形成的报复策略类似于简单惩罚码（SPC），并尝试使用非完美监控来抑制合谋；本文在此基础上推进了一大步，首次给出了二者之间的严格数学证明并推导出 TV 距离下界，提出了完全消除惩罚码不动点的 CURB 算法，抑制定价合谋效果显著优于非完美监控。
- vs Johnson et al. (Econometrica 2023 - PDP / DPDP): Johnson 等人通过平台设计算法调控产品曝光来对抗合谋，但其实质是将价格竞争转嫁为不对称展现；CURB 则是首个纯智能体端、去中心化且保证价格对称竞争的内生干预方法。
- vs Hartline et al. (CSLAW 2024 / 2025): Hartline 等人的方案侧重于基于校准悔标的事后法律与监管审计；CURB 则侧重于在训练学习算法底层进行事前防御，防止具有报复威胁的有害平衡在系统演化中形成。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次形式化连接 Abreu 惩罚码理论与 Q-learning 算法合谋，推导出 TV 距离下界定理并设计出 TV 重塑+信念注入架构。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖 Bertrand/Cournot 两种经典博弈模型、表格与深度 DQN 架构、\(n=2\) 与 \(n=3\)、细致的组件消融与强制背叛诊断。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严密自洽，从博弈论引理到强化学习算法推导逻辑一气呵成，结构清晰明了。
- 价值: ⭐⭐⭐⭐⭐ 为解决反垄断领域日益严峻的现实算法隐性合谋问题提供了普适且坚实的理论工具与工程解法。