arXiv:2409.03956cs.GTcs.LG2024-09被引 15

无需威胁机制,算法也能自发形成垄断定价。

Algorithmic Collusion Without Threats

  • 第一方算法用无悔学习,第二方仅优化自身收益
  • 即使不设威胁,仍出现接近垄断的高价
  • 适合关注算法反垄断与市场机制的研究者

近期担忧算法可能自行达成合谋。传统观点认为,超竞争性价格源于威胁策略或一方未优化收益。但本研究发现:即使双方算法均不包含威胁、且仅追求自身利润最大化,仍会形成超竞争性价格。在序列定价博弈中,若第一方采用任意具备无悔保证的算法,第二方即使仅近似优化自身收益,也会导致类似垄断的价格。该结果适用于任何无悔学习算法和任何收益不低于随机定价的策略,包括无法表达威胁的非响应型定价策略。进一步发现,存在一组不显式编码威胁的策略,在算法空间中构成纳什均衡并导致接近垄断的价格。这表明算法合谋的定义需扩展至包含无明确威胁的策略。

原文摘要 · Abstract (English)

There has been substantial recent concern that pricing algorithms might learn to ``collude.'' Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors who refuse to support high prices, and these strategies can be automatically learned. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to optimize their payoff. Is this intuition correct? Would preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can emerge even when both players are using algorithms which do not encode threats, and which optimize for their own revenue. We study sequential pricing games in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would -- and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of ``algorithmic collusion'' may need to be expanded, to include strategies without explicitly encoded threats.

算法合谋定价博弈无悔学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。