Convergence of Stochastic First-Order Algorithms in Bertrand Competition Under Incomplete Information
Martin Bichler, Jan-Sebastian Höhener · 2026
Read Convergence of Stochastic First-Order Algorithms in Bertrand Competition Under Incomplete Information by Martin Bichler, Jan-Sebastian Höhener (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17607.txt.
Introduction
Martin Bichler and Jan-Sebastian Hoehener study Bayesian Bertrand competition with private costs and piecewise-linear pricing. They prove Minty stability fails near equilibrium in the continuous game, and in fine piecewise-linear approximations with flat segments. A sum-of-squares frame builds global Lyapunov maps for the projected flow, and feasible positive-rate checks imply global stability. A proximal Lyapunov proof gives last-iterate settling under persistent noise and shrinking steps. The search covers 243 systems, returning feasible results throughout, including 111 with verified Minty failure.
Catalog record
| CREATOR | Martin Bichler, Jan-Sebastian Höhener |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55323 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17607
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convergence of Stochastic First-Order Algorithms in Bertrand Competition Under Incomplete Information Martin Bichler, Jan-Sebastian Höhener Abstract Autonomous pricing agents are widely deployed in online marketplaces, making algorithmic pricing a prominent application of multi-agent learning. Experimental studies often report collusive outcomes, but these findings typically rely on Q-learning in complete-information environments and lack rigorous convergence guarantees. In this paper, we study the stochastic learning dynamics of Regularized Robbins–Monro (RRM) algorithms in a Bayesian Bertrand competition with private costs. We show that this setting violates standard stability conditions, including monotonicity and the Minty variational inequality, rendering classical convergence results for gradient-based learning inapplicable. Despite this, we prove that Euclidean RRM algorithms converge almost surely to the unique, efficient Bayes–Nash equilibrium within a finite-dimensional approximation of the strategy space. By analyzing symmetric piecewise-linear pricing strategies in a duopoly, we explicitly construct a global Lyapunov function for the projected primal dynamics and establish global asymptotic stability of the equilibrium. Our analysis yields rigorous convergence guarantees for stochastic first-order learning algorithms in Bayesian Bertrand competition and provides a principled counterpoint to widespread claims of algorithmic collusion. Keywords Machine Learning \cdot Algorithmic Pricing \cdot Game Theory \cdot Stochastic Approximation 1 Introduction Online retail is one of the largest-scale deployments of automated decision-making, with sellers increasingly relying on learning algorithms to adjust prices dynamically [ 8 ] . From the perspective of an individual seller, pricing is an online learning problem [ 19 ] : at each round, the agent selects a price to maximize cumulative profit in an uncertain and adaptive environment shaped by competitors. Classical economic theory, by contrast, models price competition using static equilibrium concepts such as the Bertrand model [ 5 ] , which assumes complete information and simultaneous play. Real-world pricing agents face a different strategic environment, usually having no or incomplete information about competitors’ costs, which requires them to learn revenue-maximizing pricing strategies over time. This gap between static equilibrium analysis and adaptive learning raises a central question for multi-agent learning: what is the long-run behavior of markets populated by learning agents? Recent experimental evidence suggests a troubling answer. In a range of pricing environments, learning agents often fail to converge to the competitive Nash equilibrium and instead sustain prices above it, a phenomenon commonly referred to as algorithmic collusion [ 9 , 15 , 1 ] . However, much of this evidence relies on tabular Q-learning in complete-information settings and on specific hyperparameter choices. Q-learning scales poorly, does not satisfy vanishing regret guarantees, and is therefore a questionable benchmark for rational pricing behavior in competitive environments. In this paper, we study learning dynamics based on the class of Euclidean Regularized Robbins–Monro (RRM) algorithms, which encompass a broad family of scalable, theoretically grounded no-regret methods, including stochastic gradient ascent (SGA), as well as their optimistic, and extra-gradient versions [ 17 ] . Unlike tabular Q-learning, RRM algorithms are well suited for continuous action spaces and satisfy minimal rationality requirements of vanishing regret, which makes them a natural choice for algorithmic pricing agents. We analyze RRM learning in a Bayesian Bertrand competition , where firms’ costs are privately known and drawn from a common distribution. This formulation captures key features of online pricing environments, while retaining a clear equilibrium benchmark: the Bayes–Nash equilibrium (BNE). While competitors’ costs are drawn from a prior distribution, learning agents do not even know this distribution ex-ante. Establishing convergence of learning RRM agents in this setting is challenging, as standard sufficient conditions used in learning analysis, most notably monotonicity and the Minty variational inequality, fail to hold, as we show in this paper. Our main contribution is to establish that learning converges to the efficient equilibrium within a projected dynamical system framework. We approximate the infinite-dimensional strategy space using symmetric piecewise-linear pricing functions and analyze the projected primal dynamics induced by Euclidean RRM algorithms. For the foundational case of a symmetric duopoly with all-or-nothing demand and two linear pieces, we provide a rigorous proof of convergence by explicitly constructing a global Lyapunov function for the projected dynamics and prove that the competitive BNE is a globally asymptotically stable equilibrium. Using stochastic approximation theory for projected dynamical systems, we lift this stability result to discrete-time learning and establish almost sure convergence of the class of Euclidean RRM algorithms. Beyond providing a rigorous convergence guarantee, these results offer a positive counterpoint to the prevailing narrative of algorithmic collusion. They show that widely used no-regret learning algorithms converge to competitive outcomes even under incomplete information and stochastic updates, and they provide a practical method for computing approximate BNEs in Bayesian games where analytical solutions are intractable. Our contributions are summarized as follows: • We show that Bayesian Bertrand competition violates standard sufficient conditions for convergence, including monotonicity and the Minty variational inequality. • We prove global asymptotic stability of the competitive equilibrium within the projected space of symmetric piecewise-linear strategies ( m=2 ) by constructing an explicit global Lyapunov function for the projected primal mean dynamics. • We apply stochastic approximation theory to establish almost sure convergence of a broad family of Euclidean RRM algorithms, including projected gradient, optimistic, and extra-gradient methods. While our explicit derivation focuses on the two-piece case, the underlying Lyapunov-based approach extends to strategies with more linear pieces, albeit requiring more sophisticated constructions beyond the scope of this paper. 2 Bertrand Competition Let us first introduce the Bertrand competition as a complete-information game, before we expand this to the Bayesian version of the game. 2.1 Complete Information Let n\in\mathbb{N} be the number of firms. We consider a strategic game in which each firm i\in\mathcal{N}:=\{1,\dots,n\} competes by choosing a price p_{i}\in\mathbb{R}_{\geq 0} to maximize its utility (or profit). Setting fixed costs to zero for simplicity, the utility is given by: u_{i}(p_{i},\mathbf{p_{-i}})=q_{i}(\mathbf{p})\,(p_{i}-c_{i}), where c_{i} denotes the marginal cost and q_{i}(\mathbf{p}) is the firm’s sales quantity determined by the demand function. We analyze the game under the standard all-or-nothing demand model, where consumers purchase from the firm offering the lowest price: q_{i}(\mathbf{p})=\begin{cases}1&\text{if}\quad p_{i}<\min_{j\neq i}p_{j},\\ 0&\text{else.}\end{cases} Under complete information, where each firm knows its rival’s cost and strategy, the unique Nash equilibrium for the homogeneous case is characterized by marginal cost pricing: p_{i}^{*}=c_{i}\quad\forall i. This result, known as the Bertrand Paradox [ 6 ] , implies zero profits even in oligopolies and serves as the competitive baseline equilibrium against which learning dynamics are evaluated. 2.2 Incomplete Information In the Bayesian formulation, we assume incomplete information regarding firms’ costs. Each firm i\in\mathcal{N} has a private cost (type) c_{i}\in C_{i}\subset\mathbb{R} , which is independently distributed according to an atomless cumulative distribution function F_{i} . We assume (without loss of generality) that costs are normalized to the unit interval, C_{i}=[0,1] , and F_{i} admits a strictly positive probability density function f_{i} . A pure strategy for firm i is a function \beta_{i}:C_{i}\to P_{i} that maps its private cost to a price p_{i}\in P_{i}\subset\mathbb{R}_{\geq 0} . The vector of strategies for all firms is denoted by \boldsymbol{\beta}=(\beta_{1},\dots,\beta_{n}) . We define the space of admissible strategies \mathcal{B}_{i} as a subset of the Banach space V_{i}=W^{1,1}(0,1;F_{i}) , which consists of F_{i} -integrable functions with F_{i} -integrable weak derivatives. Denote \boldsymbol{\mathcal{B}}:=\prod_{i}\mathcal{B}_{i} . The goal of each firm is to maximize its expected utility (or profit), denoted by