📈 economics

Auditing Algorithmic Collusion from Strategy Graphs

本文提出了一种新颖的审计框架，通过分析源自企业冻结定价策略的策略图拓扑特征来检测算法共谋，证明了诸如最大介数和吸引子入度等指标是稳健且高效的数据指标，能够识别共谋行为，且无需获取敏感的市场数据或价格历史。

原作者： Nicolas Eschenbaum, Janusz M. Meylahn

发布于 2026-08-10

📖 1 分钟阅读☕ 轻松阅读

原作者： Nicolas Eschenbaum, Janusz M. Meylahn

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在观看一场高水平的国际象棋比赛，但参赛者并非人类，而是通过试错法学习如何下棋的超高速计算机程序。这就是算法定价的世界，在这里，公司让人工智能来决定从汽油到公寓租金的一切价格。有时，这些程序会无意中学会一种“秘密握手”：它们发现，如果大家都维持高价，即使彼此从未交流，大家也能赚得更多。这被称为算法合谋。这对监管机构来说是一场噩梦，因为这很难被抓获。通常，要证明两个人正在进行反竞争行为，你需要看到他们在角落里窃窃私语，或者找到一张纸条。但在计算机的世界里，没有窃窃私语，而那些“纸条”则埋藏在数百万行代码中，公司将这些代码视为顶级机密配方。

那么，如果你无法阅读他们的日记或监听他们的电话，该如何抓住作弊者呢？你必须观察他们决策的地图。不要把定价算法看作一个大脑，而要把它看作一个迷宫。每当计算机看到特定情况（例如“昨天的价格很高”）时，它都会有一个下一步的规则。如果你从每种情况连线到计算机选择的下一个情况，你就会得到一个巨大的、纠缠不清的网络路径。在公平的竞争游戏中，这个网络通常是一条通往最低价格的混乱而直接的路径。但如果计算机在合谋，这个网络看起来就会不同。它会有特定的“瓶颈”和长长的、蜿蜒的循环，旨在惩罚任何试图破坏规则的人。这篇论文探讨的是：我们能否仅仅通过观察这个迷宫的形状，在不知道价格、利润甚至不知道代码的情况下，就识破一场秘密的阴谋？

这篇论文的作者尼古拉斯·埃申鲍姆（Nicolas Eschenbaum）和雅努什·M·梅拉恩（Janusz M. Meylahn）说：可以。他们提出了一种新的审计算法的方法，这种方法不需要窥探内部构造。他们建议，监管机构不需要索要秘密代码或训练数据，而是只需询问算法：“如果你处于这种特定情况下，你会怎么做？”通过针对每种可能的情景进行提问，他们就可以构建出“策略图”——即迷宫的地图。

研究人员发现，合谋算法会在这种地图上留下非常独特的指纹。他们发现，当算法协同工作以维持高价时，它们的决策迷宫会产生强烈的瓶颈。想象一座城市，要从任何地方回家，你必须经过一座单一且狭窄的桥梁。如果你试图走捷径，你会在通过那座桥之前陷入交通拥堵（惩罚阶段）。在竞争激烈的市场中，会有许多桥梁和捷径；你可以从任何地方快速回家。但在合谋的市场中，地图被设计成了这样：几乎所有的路径都会在返回高价区之前，被迫汇聚到一个特定的“惩罚状态”。

为了证明这一点，团队进行了数千次模拟。他们创建了一个简单的世界，其中两个计算机程序学习如何设定价格。他们测试了两种不同的学习方法：一种是程序共同学习的方法（类似于著名的“Calvano”方法），另一种是分散式Q学习（Decentralized Q-learning）。他们还测试了一个场景，即将两个分别训练的程序强制放在一起对抗，从而打破了它们的合谋。

结果令人震惊。研究人员测量了迷宫的三个主要特征：

最大介数（Maximum Betweenness）：这衡量了有多少路径经过单个“瓶颈”。在模拟中，算法越倾向于合谋，被迫通过单一惩罚状态的流量就越大。这种相关性很强，在主要测试中的得分达到了 0.67。
吸引子入度（Attractor In-degree）：这计算了有多少路径能直接通向“快乐之地”（高价循环）。在合谋迷宫中，很少有路径能直接到达那里；大多数路径必须通过惩罚阶段绕远路。这一指标显示出强烈的负相关性 -0.67（这意味着随着合谋程度上升，直接路径减少）。
平均路径长度（Average Path Length）：这衡量了在犯错后回到高价循环需要多少步。合谋迷宫的路径更长（在理论模型中平均为 1.96 步），因为算法在给予宽恕之前会强制执行一个“惩罚阶段”。

作者谨慎地指出，这并不是一个能瞬间证明犯罪的“万灵药”。他们发现，当算法学会如何在惩罚之后重新恢复合作，而不是直接放弃（即“严厉触发”策略）时，这些“图指标”效果最好。他们也承认，在现实世界中，算法可能会更加复杂，使用随机选择或连续更新，这可能会使地图变得模糊。然而，他们的模拟表明，决策过程的形状是一个稳健的信号。

这种方法的精妙之处在于它需要的信息极少。监管机构不需要看到公司的秘密代码、销售数据或利润率。他们只需要能够查询当前的“冻结策略”——即算法目前遵循的一套规则——并追踪迷宫的线条。如果地图显示出一条每个人都必须经过才能回到高价区的单一、狭窄的桥梁，那就是一个巨大的红旗，预示着算法可能正在合谋。这就像是在城堡里发现了一条秘密通道；你不需要知道是谁建造了它或为什么要建造它，但这条通道的存在本身就说明了一些可疑的情况正在发生。

简而言之，这篇论文表明，虽然我们并不总是能读懂这些算法的思想，但我们可以读懂它们的地图。如果地图看起来像是一个旨在把你困在惩罚循环中、然后再让你回到高价俱乐部的迷宫，那么监管机构是时候进行密切调查了。

技术摘要：基于策略图的算法共谋审计

问题陈述
检测算法共谋非常困难，因为监管机构通常无法获取企业的专有算法、训练数据和完整的市场历史。虽然存在极端的信息体制——要么拥有完整的源代码访问权，要么仅能获得有限的价格轨迹——但本文研究的是一种中间信息体制。在这种体制下，审计员可以查询“冻结”的定价策略（即在每个市场状态下选择的贪婪动作），但缺乏对需求函数、数值价格基准、竞争性/垄断性利润水平或具体训练方法的了解。核心问题在于：这些冻结策略的结构拓扑结构是否包含稳健的共谋信号，且无需重建底层的经济环境。

方法论
作者提出了一种基于图论的审计方法。他们将 $n$ 个智能体在重复定价博弈中的交互建模，其中每个智能体的决策都以截断的历史价格剖面为条件。一个联合确定性策略会诱导出一个策略图 $G(\pi)$ ，这是一个函数关系，其中节点代表联合市场状态，有向边代表当所有智能体执行其贪婪动作时向下一个状态的转移。

核心方法包括：

基准真相推导： 作者首先分析了一个具有对数需求的三价格双寡头博弈中一个完全已知的、包含 101 个纳什均衡的解析集合。他们通过“共谋指数”（ $\Delta$ ）对这些均衡进行分类，该指数是一个基于利润的指标，范围从 0（竞争性）到 1（垄断性）。
指标定义： 基于奖励与惩罚策略（即偏差发生后在恢复合作前先受到惩罚）的结构逻辑，他们从策略图的最大弱连通分量（WCC）中导出了五个图论指标：
- 最大介数 ( $B_{max}$ )：经过单个非吸引子节点（瓶颈）的最大返回路径数量。
- 吸引子入度 ( $D_A$ )：直接转移至吸引子（代表长期结果的循环）的状态平均数量。
- 平均路径长度 ( $L_A$ )：任何状态到达吸引子所需的平均步数。
- 盆地比例 ( $\beta$ )：属于最大 WCC 的总状态空间的比例。
- 吸引子数量 ( $K$ )：图中不同循环的数量。
实证验证： 这些指标在两种不同的算法学习的策略上进行了测试：
- Calvano 等人 (2020) 的 Q-learning：在 15 个价格环境下进行训练，折扣因子 $\gamma \in [0.1, 0.95]$ 变化，生成了 1,800 对策略。
- 去中心化 Q-learning (Arslan 和 Yükel, 2017)：在 5 个价格环境下进行训练。
- 重匹配测试 (Rematching Test)：将独立训练的策略相互重新匹配以打破共谋，从而创建一个具有高折扣因子的竞争性结果数据集。

关键结果
研究发现，策略图的特定拓扑特征与基于利润的共谋指数具有强相关性，即使在缺乏价格标签或需求估计的情况下也是如此：

最大介数：显示出与共谋指数强正相关（在合并后的 Calvano 运行中 $\rho \approx +0.67$ ；在解析均衡集中 $\rho \approx +0.94$ ）。共谋图表现出“瓶颈”，即惩罚状态位于大多数瞬态状态的返回路径上。
吸引子入度：显示出强负相关 ( $\rho \approx -0.67$ )。在共谋均衡中，较少有状态直接转移到高价格吸引子，因为偏差必须先经过惩罚阶段。
平均路径长度：显示出正相关 ( $\rho \approx +0.57$ )，反映了在惩罚阶段后返回合作所需的额外步骤。
盆地比例和吸引子数量：在标准的 Calvano 设置中（其中竞争性策略通常形成单盆地图），这些指标的信息量较少；但在去中心化 Q-learning 设置或重匹配实验中，当状态空间发生碎片化时，它们变得显著。

这些结果在不同的学习算法和实验设计中均保持一致。值得注意的是，这些指标仅依赖于图的无标签拓扑结构；它们不需要知道具体的价格、利润或折扣因子的量级。

意义与主张
本文声称提供了一个“在有限信息条件下审计算法定价系统的有前景的基础”。其主要贡献在于证明了冻结定价策略的结构包含了稳定的共谋信号。

审计可行性：所提出的指标表明，监管机构无需重建训练过程或访问专有代码即可识别潜在的共谋。相反，通过查询策略对所有可行状态的响应来构建策略图，足以生成一个结构性筛查。
无基准检测：不同于基于利润的指标，这些图论指标不需要竞争性或垄断性的基准，而这些基准通常是监管机构无法获得的。
范围与局限性：作者明确指出，这是一种结构性筛查，而非对共谋的最终判定。这些指标检测的是“奖励与惩罚”机制（即在偏差后返回合作），但可能无法识别“严厉触发”（Grim Trigger）均衡，因为在后者中，系统在偏差后会永久回归到竞争状态（这会将共谋分支隐藏在一个次要分量中）。此外，目前的验证仅限于在程式化对数环境下有限、确定性和冻结策略上的应用；这些指标对于随机、自适应或高维策略的适用性仍是一个开放性问题。

总之，本文认为策略图的拓扑结构——特别是返回路径向惩罚状态的集中程度——构成了算法共谋的拓扑特征，为处于信息受限环境下的监管机构提供了一个实用的工具。

类似论文