不依赖对手信息的算法竟会自发形成串通行为,机制是行动同步性。
The Illusion of Collusion
- 用无模型的多臂赌博机算法模拟竞争,仅靠自身随机探索产生串通
- 同步行动越频繁,串通现象越明显;确定性算法几乎必然导致串通
- 适合关注算法监管、平台定价策略的学者与政策制定者
在一系列竞争性决策场景中,如在线零售和租房定价,算法代理被广泛应用。本文研究当竞争代理采用多臂赌博机算法时,在重复囚徒困境模型下算法串通的出现机制。值得注意的是,这些代理进行在线学习,缺乏对博弈结构的先验知识,也无法获知对手状态或行为,因而无法学习依赖于这些因素的策略。尽管如此,它们仍经常表现出看似串通的行为,我们称之为‘天真串通’。结果表明,这种串通是否出现强烈依赖于赌博机学习者所采用的行为策略。其背后机制是代理行动的同步性,即双方采取相同动作的频率。长期来看,当双方使用广泛的一类持续随机算法(如无ε衰减的ε-贪婪算法)时,串通永不发生;当使用极限贪婪算法(探索期有随机性,但渐近确定)时,串通可能偶尔出现;而当双方使用确定性算法(如经典的上置信界UCB系列)时,串通必然发生。我们强调了市场与算法条件下可预判或不可预判串通出现的情形。研究具有多重政策启示:禁止算法依据对手价格调整行为,并不能防止串通;算法对称性会增加串通风险;串通的出现具有路径依赖性。
原文摘要 · Abstract (English)
Algorithmic agents are used in a variety of competitive decision-making settings, including pricing contexts that range from online retail to residential home rental. We study the emergence of algorithmic collusion when competing agents employ multi-armed bandit algorithms and competition is modeled as a repeated Prisoner's Dilemma game. Notably, agents in our setting perform online learning with no prior model of game structure and have no direct knowledge of competitor states or actions, thus they cannot learn strategies that depend on these factors. These context-free bandits nonetheless frequently learn seemingly collusive behavior, a phenomenon we term naive collusion. Our results reveal that whether naive collusion emerges depends starkly on the choice of behavior policy employed by bandit learners. The mechanism underpinning the emergence of collusive outcomes is synchronicity in agent action plays, where synchronicity captures how often agents play the same action. We show that in the long-run, naive algorithmic collusion never emerges when both agents use a broad class of persistently random algorithms, including the epsilon-greedy algorithm without epsilon decay, sometimes emerges when both agents use greedy-in-the-limit algorithms which feature randomness during exploration but are asymptotically deterministic, and always emerges when both agents use deterministic bandit learning algorithms like those in the well-known upper confidence bound (UCB) family. We highlight market and algorithmic conditions under which one can and cannot predict a priori whether collusion will occur. Our findings have several policy implications: preventing pricing algorithms from conditioning their actions on competitor prices may not preclude algorithmic collusion, symmetry in algorithms may increase collusion potential, and the emergence of algorithmic collusion is path dependent.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。