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

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

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}$. We analyze a repeated-game model in which firms set prices using no-regret learners to understand the "Bertrand Paradox"—the gap between classical theory (predicting low prices) and real-world high prices. Our results characterize the equilibrium outcomes under different no-regret learning guarantees, showing that no-external-regret learners can converge to high-price outcomes, while no-swap-regret guarantees are typically required to drive prices down.

Introduction

In classical economics, the Bertrand Paradox describes a situation where competition between even two firms should drive prices down to marginal cost ($P=MC$). However, real-world markets frequently sustain high markups. This paper investigates this discrepancy by modeling firms as agents in a repeated game using no-regret learning algorithms. We ask what transaction prices can be sustained when firms learn from past interactions, specifically examining how "algorithmic sophistication"—measured by external regret versus swap regret—influences whether a market stays "collusive" (high prices) or becomes "competitive" (low prices).

Methodology

The researchers analyze a discrete Bertrand pricing game where $n$ players choose prices from a grid. They utilize the fundamental link between learning and equilibrium:

  • No-External-Regret Learning: Converges to a Coarse Correlated Equilibrium (CCE).
  • No-Swap-Regret Learning: Converges to a Correlated Equilibrium (CE).

The study evaluates its theoretical findings against several standard synthetic demand functions: constant ($f(x) = 1$), linear ($f(x) = 1 - x$), quadratic ($f(x) = 1 - x^2$), and exponential ($f(x) = \exp(-x)$). The paper combines formal mathematical proofs with numerical experiments using standard algorithms like Hedge and Regret Matching.

Key Insights and Results

The theoretical analysis reveals that simple no-external-regret learning is insufficient to guarantee competitive pricing.

The Persistence of High Prices

Theorem 2.1 confirms that high transaction prices can always be sustained under no-external-regret learning, regardless of the demand function. Essentially, simple learners can "accidentally" collude. Numerical experiments show a striking $1/e$ Rule: in symmetric settings, the maximum utility achievable in a symmetric CCE converges to approximately 36.8% of the maximum monopoly profit as the price grid becomes finer (see Figure 1a).

The Impact of Competition and Sophistication

As the number of firms ($n$) increases, the maximum utility that no-external-regret learners can sustain decays exponentially (see Figure 1b). High-price outcomes become nearly impossible with more than five firms.

Furthermore, the authors identify a "Two-Learner" Threshold: it takes at least two no-swap-regret learners to drive prices down to marginal cost. A single sophisticated learner is not enough to break a high-price CCE if the other players are only minimizing external regret.

Numerical experiments for constant demand. (a) Ratio of duopoly utility under the best symmetric CCE vs grid size $k$, showing convergence to $1/e$. (b) Exponential decay of utility as the number of players $n$ increases. (Bottom) Price distributions showing sensitivity to learning rates and costs.

Asymmetric Costs and Algorithmic Sensitivity

In duopoly settings where firms have asymmetric costs, no-swap-regret learning leads to a competitive outcome where the higher-cost firm's utility is driven to zero, effectively pushing them out of the market.

Even when theory suggests a low-price equilibrium is possible, the actual outcome depends heavily on algorithmic choices. For instance, higher learning rates for one player can push transaction prices higher by making that player more responsive to the other's price hikes. Experiments show that the specific price settled on is highly sensitive to the "aggressiveness" of the learning algorithms.

Conclusion

This work provides a robust framework for understanding the Bertrand Paradox through the lens of algorithmic game theory. It demonstrates that while simple learning dynamics can sustain collusive-like high prices, the transition to competitive markets requires a critical mass of sophisticated (no-swap-regret) learners. Future work remains to address the "selection problem"—predicting which specific equilibrium a given set of algorithms will favor in practice, as well as extending these findings to continuous pricing models.

Summary updated

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.
BibTeX
@inproceedings{maiti2026revisiting,
  author = {Arnab Maiti and Junyan Liu and Kevin Jamieson and Lillian J. Ratliff},
  title = {{Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=ZEP68RaUeR},
}
Figure