Research map / Multi-agent systems and games / Games and equilibria

Domination-Avoiding Learning Agents Cannot Collude

NeurIPS 2026 · Multi-agent systems and games › Games and equilibria · approach: Cooperation and social dilemmas · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows external-regret minimizers can collude in logit Bertrand duopolies, defines Domination-Avoiding agents that provably avoid collusion, and proves they converge to iteratively undominated (competitive) prices.

Problem

Algorithmic collusion among learning agents in Bertrand price competition with logit demand: which learning-agent properties prevent supra-competitive pricing, given that external-regret minimizers can sustain collusion.

Approach

Defines Domination-Avoiding (DA) agents, which learn to almost never play actions that are empirically dominated (δ-dominated) over time; proves that DA agents playing any finite game eventually almost never play actions removable by iterated elimination of strictly dominated strategies, and that in the logit Bertrand game this yields prices within 2ε of the Nash price. Shows mean-based, internal-

Key results

• Theorem 1: external-regret minimizing agents can reach arbitrarily high collusive prices in a symmetric logit Bertrand duopoly with no outside option (via a collusive CCE).
• Corollary 3: two DA agents on an epsilon-dense price grid play prices within 2 epsilon of the Nash price p* with asymptotic time-fraction 1.
• Empirically, MW and FTPL with learning rate 5e-3 over 1e6 steps converge to the competitive price in the baseline logit game (a=2, a0=0, c=1, mu=4).

Surprising findings

• Multiplicative Weights with a decaying learning rate (non-mean-based) is still domination-avoiding, while no internal-regret learner can be mean-based.
• External-regret minimizers can sustain supra-competitive prices even though the classic MW/FTPL simulations converge to competitive prices.

Limitations

• Domination-avoidance excludes forward-looking agents such as Q-learning, which can collude; the authors call this the main limitation.
• Results are asymptotic and the collusion construction relies on a normalized game (alpha=0, c=0, mu=1) rather than the baseline parameters.

Experimental setup

Metrics: fraction of time at competitive prices UTA of dominated-action probability CCE collusive price existence

Baselines: Q-learning Multiplicative Weights Follow the Perturbed Leader

Builds on: mean-based learning multiplicative weights no-swap-regret learning Q-learning collusion (Calvano et al.) iterated elimination of strictly dominated strategies

Closest papers by meaning

• Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma (ICML 2025 · similarity 0.89)
• Mitigating Retaliatory Algorithmic Collusion in Repeated Games (NeurIPS 2026 · similarity 0.89)
• No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics (NeurIPS 2026 · similarity 0.86)
• No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.86)
• Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents (ICML 2025 · similarity 0.85)
• Do LLM Agents Have Regret? A Case Study in Online Learning and Games (ICLR 2025 · similarity 0.85)