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

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.

Economic theory predicts that when firms sell the same product, competition should push prices down: any firm can slightly undercut its rivals and win the market. Yet in many real markets, prices remain well above cost, a tension known as the Bertrand paradox. We study whether this gap can be explained by the way firms learn prices over repeated interactions, where firms use learning algorithms designed to do almost as well as the best strategy they could have chosen in hindsight. Our results show that the type of learning guarantee matters sharply. When two firms use a weaker form of learning that only compares against one fixed alternative price, high prices can persist for any non-increasing demand curve. But when both firms use a stronger form of learning that can compare against richer price-switching rules, competition drives prices down. Surprisingly, having just one stronger learner in the market is not always enough to restore competitive pricing. However, two stronger learners are sufficient to drive prices down. We also run experiments that support our theory and illustrate how different learning rules behave in practice.