Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners

Arnab Maiti; Junyan Liu; Kevin Jamieson; Lillian J. Ratliff

cs.GTFeb 25, 2026

Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners

Authors: Arnab Maiti, Junyan Liu, Kevin Jamieson, Lillian J. Ratliff

Organizations: University of Washington

Abstract

We study the discrete Bertrand pricing game with a non-increasing demand function. The game has $n \ge 2$ players who simultaneously choose prices from the set $\{1/k, 2/k, \ldots, 1\}$ , where $k\in\mathbb{N}$ . The player who sets the lowest price captures the entire demand; if multiple players tie for the lowest price, they split the demand equally. We study the Bertrand paradox, where classical theory predicts low prices, yet real markets often sustain high prices. To understand this gap, we analyze a repeated-game model in which firms set prices using no-regret learners. Our goal is to characterize the equilibrium outcomes that can arise under different no-regret learning guarantees. We are particularly interested in questions such as whether no-external-regret learners can converge to undesirable high-price outcomes, and how stronger guarantees such as no-swap regret shape the emergence of competitive low-price behavior. We address these and related questions through a theoretical analysis, complemented by experiments that support the theory and reveal surprising phenomena for no-swap regret learners.

Figures & tables

Panel of Figure 1 — Figure 1: Numerical experiments for constant demand with $c_{1}=0$ .

Panel of Figure 2 — Figure 2: Experiments using the Hedge-based no-swap-regret learner with different combinations of costs and learning rates. The plots show the frequency of transaction prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Appendix figures & tables32 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Numerical experiments for asymmetric CCE and constant demand.

Panel of Figure 4 — Figure 4: Numerical experiments for symmetric CCE, constant demand and $c=0.0$ .

Panel of Figure 5 — Figure 5: Numerical experiments for symmetric CCE, constant demand and $c=0.5$ .

Panel of Figure 6 — Figure 6: Numerical experiments for symmetric CCE, constant demand and $c=0.9$ .

Panel of Figure 7 — Figure 7: Numerical experiments for asymmetric CCE and linear demand.

Panel of Figure 8 — Figure 8: Numerical experiments for symmetric CCE, linear demand and $c=0.0$ .

Panel of Figure 9 — Figure 9: Numerical experiments for symmetric CCE, linear demand and $c=0.5$ .

Panel of Figure 10 — Figure 10: Numerical experiments for symmetric CCE, linear demand and $c=0.9$ .

Panel of Figure 11 — Figure 11: Numerical experiments for asymmetric CCE and quadratic demand.

Panel of Figure 12 — Figure 12: Numerical experiments for symmetric CCE, quadratic demand and $c=0.0$ .

Panel of Figure 13 — Figure 13: Numerical experiments for symmetric CCE, quadratic demand and $c=0.5$ .

Panel of Figure 14 — Figure 14: Numerical experiments for symmetric CCE, quadratic demand and $c=0.9$ .

Panel of Figure 15 — Figure 15: Numerical experiments for asymmetric CCE and exponential demand.

Panel of Figure 16 — Figure 16: Numerical experiments for symmetric CCE, exponential demand and $c=0.0$ .

Panel of Figure 17 — Figure 17: Numerical experiments for symmetric CCE, exponential demand and $c=0.5$ .

Panel of Figure 18 — Figure 18: Numerical experiments for symmetric CCE, quadratic demand and $c=0.9$ .

Panel of Figure 19 — Figure 19: Experiments using the Hedge-based no-swap-regret learner with $c_{2}=1$ and both players have the same learning rates. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 20 — Figure 20: Experiments using the Hedge-based no-swap-regret learner with $c_{2}=1$ and player 1 having larger learning rate than player 2. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 21 — Figure 21: Experiments using the Hedge-based no-swap-regret learner with $c_{2}=1$ and player 2 having larger learning rate than player 1. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 22 — Figure 22: Experiments using the Hedge-based no-swap-regret learner with $c_{2}=0.5$ and both players have the same learning rates. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 23 — Figure 23: Experiments using the Hedge-based no-swap-regret learner with $c_{2}=0.5$ and player 1 having larger learning rate than player 2. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 24 — Figure 24: Experiments using the Hedge-based no-swap-regret learner with $c_{2}=0.5$ and player 2 having larger learning rate than player 1. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 25 — Figure 25: Actual prices chosen by each player during $T=10^{7}$ rounds for a fixed random seed with $c_{2}=1$ . P0 denotes player $1$ and P1 denotes player $2$ .

Panel of Figure 26 — Figure 26: Actual prices chosen by each player during $T=10^{7}$ rounds for two different random seeds with $c_{2}=1$ and same learning rates. P0 denotes player $1$ and P1 denotes player $2$ . The Hedge-based no-swap regret learner appears to choose the same set of prices across different seeds.

Panel of Figure 27 — Figure 27: Experiments using Regret Matching with $c_{2}=1$ and both players repeating their prices once. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 28 — Figure 28: Experiments using Regret Matching with $c_{2}=1$ where player 1 repeats its price 20 times and player 2 repeats its price once. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 29 — Figure 29: Experiments using Regret Matching with $c_{2}=1$ where player 2 repeats its price 20 times and player 1 repeats its price once. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 30 — Figure 30: Experiments using Regret Matching with $c_{2}=0.5$ and both players repeating their prices once. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 31 — Figure 31: Experiments using Regret Matching with $c_{2}=0.5$ where player 1 repeats its price 20 times and player 2 repeats its price once. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 32 — Figure 32: Experiments using Regret Matching with $c_{2}=0.5$ where player 2 repeats its price 20 times and player 1 repeats its price once. The plots show the frequency of prices over $T=10^{7}$ rounds, averaged across 100 random seeds.

Panel of Figure 33 — Figure 33: Actual prices chosen by each player during $T=10^{7}$ rounds for a fixed random seed with $c_{2}=1$ . P0 denotes player $1$ and P1 denotes player $2$ .

Panel of Figure 34 — Figure 34: Actual prices chosen by each player during $T=10^{7}$ rounds for two different random seeds with $c_{2}=1$ and both players repeat their prices once. P0 denotes player $1$ and P1 denotes player $2$ . Regret Matching appears to converge to different prices across different seeds.

Swap Regret

See all 8 papers

How language model agents reshape price competition
Oct 15, 2026Martin Bichler, Philip Hierhager, Kassian Köck +1Algorithmic Collusion Dynamic Pricing
School of Computation, Information and Technology, Technical University of Munich, Germany.
Persistent Partners Raise Prices Among Learning Agents
Sep 28, 2026Paul-Peter Arslan, Yubin Kim, Xiao XiaoAlgorithmic Collusion Multi-Agent Systems
Institute For Future Technologies Devinci Higher Education · Massachusetts Institute of Technology
Oblivious Learning and Collusive Pricing
Jun 3, 2026Yuhang Wu, Assaf ZeeviExploration-Exploitation Tradeoff Game Theory
Columbia Business School

Oct 15, 2026J/K move · Enter open · S save

How language model agents reshape price competition

Martin Bichler, Philip Hierhager, Kassian Köck, Fabian Pieroth

School of Computation, Information and Technology, Technical University of Munich, Germany.

Algorithmic Collusion Dynamic Pricing Game Theory Multi-Agent LLMs

Open paper AskPDF arXiv

Repeated Bertrand competition is a stringent benchmark for algorithmic pricing: in homogeneous-goods markets, standard learning procedures typically select the stage-game Nash outcome with prices near marginal cost. We show that LLM pricing agents can escape this benchmark, depending on deployment decisions. LLMs outperform standard online learners through faster adaptation, but this advantage largely disappears against full-information learners. An extracted surrogate algorithm illustrates how LLMs in specific deployments profit from regularly undercutting slower learners. Agents that post one price every period from raw market histories that include rival prices can sustain supracompetitive regimes in self-play. Agents that periodically emit probability distributions from summarized histories of their own profits instead move toward the competitive region in self-play. Markets mixing these interfaces can generate dynamic regimes in which LLMs establish a high-price anchor and regularly undercut it to capture demand. These regimes can keep both competitors' prices above marginal cost. Deployment choices shape these outcomes, shifting the focus from stationary equilibria to dynamic pricing regimes.

Abstract

Swap Regret

Explore similar work

How language model agents reshape price competition

Persistent Partners Raise Prices Among Learning Agents

Oblivious Learning and Collusive Pricing