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.
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