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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We study the discrete Bertrand pricing game with a non-increasing demand function. The game has n≥2n \ge 2 players who simultaneously choose prices from the set {1/k,2/k,…,1}\{1/k, 2/k, \ldots, 1\}, where k∈Nk\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

Figure 1: Numerical experiments for constant demand with c1=0c_{1}=0 .
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=107T=10^{7} rounds, averaged across 100 random seeds.
Appendix figures & tables32 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Numerical experiments for asymmetric CCE and constant demand.
Figure 4: Numerical experiments for symmetric CCE, constant demand and c=0.0c=0.0 .
Figure 5: Numerical experiments for symmetric CCE, constant demand and c=0.5c=0.5 .
Figure 6: Numerical experiments for symmetric CCE, constant demand and c=0.9c=0.9 .
Figure 7: Numerical experiments for asymmetric CCE and linear demand.
Figure 8: Numerical experiments for symmetric CCE, linear demand and c=0.0c=0.0 .
Figure 9: Numerical experiments for symmetric CCE, linear demand and c=0.5c=0.5 .
Figure 10: Numerical experiments for symmetric CCE, linear demand and c=0.9c=0.9 .
Figure 11: Numerical experiments for asymmetric CCE and quadratic demand.
Figure 12: Numerical experiments for symmetric CCE, quadratic demand and c=0.0c=0.0 .
Figure 13: Numerical experiments for symmetric CCE, quadratic demand and c=0.5c=0.5 .
Figure 14: Numerical experiments for symmetric CCE, quadratic demand and c=0.9c=0.9 .
Figure 15: Numerical experiments for asymmetric CCE and exponential demand.
Figure 16: Numerical experiments for symmetric CCE, exponential demand and c=0.0c=0.0 .
Figure 17: Numerical experiments for symmetric CCE, exponential demand and c=0.5c=0.5 .
Figure 18: Numerical experiments for symmetric CCE, quadratic demand and c=0.9c=0.9 .
Figure 19: Experiments using the Hedge-based no-swap-regret learner with c2=1c_{2}=1 and both players have the same learning rates. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 20: Experiments using the Hedge-based no-swap-regret learner with c2=1c_{2}=1 and player 1 having larger learning rate than player 2. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 21: Experiments using the Hedge-based no-swap-regret learner with c2=1c_{2}=1 and player 2 having larger learning rate than player 1. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 22: Experiments using the Hedge-based no-swap-regret learner with c2=0.5c_{2}=0.5 and both players have the same learning rates. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 23: Experiments using the Hedge-based no-swap-regret learner with c2=0.5c_{2}=0.5 and player 1 having larger learning rate than player 2. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 24: Experiments using the Hedge-based no-swap-regret learner with c2=0.5c_{2}=0.5 and player 2 having larger learning rate than player 1. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 25: Actual prices chosen by each player during T=107T=10^{7} rounds for a fixed random seed with c2=1c_{2}=1 . P0 denotes player 11 and P1 denotes player 22 .
Figure 26: Actual prices chosen by each player during T=107T=10^{7} rounds for two different random seeds with c2=1c_{2}=1 and same learning rates. P0 denotes player 11 and P1 denotes player 22 . The Hedge-based no-swap regret learner appears to choose the same set of prices across different seeds.
Figure 27: Experiments using Regret Matching with c2=1c_{2}=1 and both players repeating their prices once. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 28: Experiments using Regret Matching with c2=1c_{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=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 29: Experiments using Regret Matching with c2=1c_{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=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 30: Experiments using Regret Matching with c2=0.5c_{2}=0.5 and both players repeating their prices once. The plots show the frequency of prices over T=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 31: Experiments using Regret Matching with c2=0.5c_{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=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 32: Experiments using Regret Matching with c2=0.5c_{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=107T=10^{7} rounds, averaged across 100 random seeds.
Figure 33: Actual prices chosen by each player during T=107T=10^{7} rounds for a fixed random seed with c2=1c_{2}=1 . P0 denotes player 11 and P1 denotes player 22 .
Figure 34: Actual prices chosen by each player during T=107T=10^{7} rounds for two different random seeds with c2=1c_{2}=1 and both players repeat their prices once. P0 denotes player 11 and P1 denotes player 22 . Regret Matching appears to converge to different prices across different seeds.
More in this topic

Swap Regret

See all 8 papers

Explore similar work

CardsList
Oct 15, 2026

How language model agents reshape price competition

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.

Martin Bichler, Philip Hierhager, Kassian Köck +1

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

Algorithmic CollusionDynamic PricingGame TheoryMulti-Agent LLMs
AskPDF
Sep 28, 2026

Persistent Partners Raise Prices Among Learning Agents

When pricing agents meet repeatedly on a platform, the platform decides who faces whom. We ask whether that choice moves the prices the agents learn, and whether a rise comes with learned punishment. In a pre-registered randomised experiment in the Bertrand duopoly of Calvano et al., each agent's price is set by a tabular Q-learning module, not by the small language model attached to it, and we randomise whether each agent keeps its partner, sees its rival's prices and can send messages. Keeping the same partner raises the level of profits, averaged over training, by 0.27 of the gap between competitive and monopoly profit (95% CI 0.20 to 0.35, all twenty paired runs positive), our registered primary result, and the resting price by 0.17 of the Nash-to-monopoly range (post hoc). A plain tabular learner reproduces the effect in all 25 further blocks, and there one permanent partner raises the level more than about three do (+0.23 against +0.05, exploratory). Where rival prices are hidden, the price-setting module cannot see a cut, so cannot punish it, yet the resting price rises as much and the rise lasts to the end of training, while with visible rivals it shrinks with longer training (post hoc). Where the rival is visible, a static best responder accounts for a third to a half of what a forced-deviation probe reads as punishment, on the starts where the rival can see the cut, and net of it the registered test of learned punishment is inconclusive. A test that looks only for punishment would thus miss the rise where the rival is hidden, while a check for profitable deviations flags most of those prices (post hoc). In an exploratory extension, untrained Qwen2.5 7B and 14B models under one prompt show the effect when the rival's price is left out of the prompt and inconsistently when it is shown, the 7B result replicating on fresh blocks, while two other model families show none.

Paul-Peter Arslan, Yubin Kim, Xiao Xiao

Institute For Future Technologies Devinci Higher Education · Massachusetts Institute of Technology

Algorithmic CollusionMulti-Agent SystemsDynamic PricingMulti-Agent Reinforcement Learning
AskPDF
Jun 3, 2026

Oblivious Learning and Collusive Pricing

On a platform with many sellers, should a pricing algorithm explicitly model competitors' prices when learning demand? Classical arguments suggest that ignoring competitors induces model misspecification and inefficiency, yet findings from algorithmic collusion suggest that ignoring competitor prices may, surprisingly, facilitate collusive outcomes and improve profits. We study this problem in a competitive market with unknown noisy demand, in which sellers repeatedly set prices, either incorporating competitor prices in learning their demand models (informed), or ignoring them (oblivious). We show that, relative to a monopolist, an oblivious seller in a competitive market must conduct more aggressive price exploration to compensate for the loss of dynamic competitor information. When all sellers are oblivious, prices converge to the competitive outcome under persistent exploration, while a continuum of pseudo-equilibria arises when exploration is "insufficient." In markets with a mix of oblivious and informed sellers, the informed strictly out-earn the oblivious. In game-theoretic terms, the unique Nash equilibrium is the all-informed market, in which prices converge to the competitive outcome efficiently, and oblivious modeling does not robustly lead to collusive patterns.

Yuhang Wu, Assaf Zeevi

Columbia Business School

Exploration-Exploitation TradeoffGame TheoryAlgorithmic CollusionDynamic Pricing
AskPDF