pith. sign in

arxiv: 2605.17607 · v1 · pith:RBLHGNEWnew · submitted 2026-05-17 · 💻 cs.GT

Convergence of Stochastic First-Order Algorithms in Bertrand Competition Under Incomplete Information

Martin Bichler , Jan-Sebastian Hoehener This is my paper

Pith reviewed 2026-05-19 22:14 UTC · model grok-4.3

classification 💻 cs.GT
keywords Bertrand competitionBayes-Nash equilibriumstochastic first-order algorithmsLyapunov functionalgorithmic pricingincomplete informationconvergence guarantees
0
0 comments X

The pith

Euclidean RRM algorithms converge almost surely to the unique efficient Bayes-Nash equilibrium in finite-dimensional approximations of Bayesian Bertrand competition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that Regularized Robbins-Monro algorithms converge to the efficient equilibrium in Bertrand competition where sellers have private cost information. Standard conditions for convergence like monotonicity are violated, yet the authors prove almost sure convergence anyway. They do this by restricting to symmetric piecewise-linear pricing functions that approximate the full strategy space and building an explicit Lyapunov function that proves the equilibrium is globally asymptotically stable. This matters for understanding whether autonomous pricing software in markets will lead to collusion or competitive pricing. Sympathetic readers care because it gives mathematical backing to convergence in a realistic incomplete-information setting where experiments often show different outcomes.

Core claim

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.

What carries the argument

The global Lyapunov function for the projected primal dynamics constructed explicitly from symmetric piecewise-linear pricing functions in the finite-dimensional strategy space approximation.

If this is right

  • The algorithms converge almost surely despite violations of monotonicity and the Minty variational inequality.
  • The limit point is the unique efficient Bayes-Nash equilibrium.
  • Global asymptotic stability holds for the projected primal dynamics under the constructed Lyapunov function.
  • The result supplies rigorous convergence guarantees for stochastic first-order learning in this Bayesian setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Lyapunov construction via piecewise-linear approximations may extend to other Bayesian market games with private information.
  • Real-world deployment of RRM-style pricing agents would be predicted to reach competitive rather than collusive outcomes under the paper's conditions.
  • Higher-dimensional or asymmetric approximations of the strategy space could test the robustness of the convergence result.

Load-bearing premise

The strategy space admits a finite-dimensional approximation by symmetric piecewise-linear pricing functions for which a global Lyapunov function can be explicitly constructed.

What would settle it

A simulation or theoretical counterexample in the symmetric piecewise-linear pricing space showing that the Euclidean RRM dynamics fail to approach the Bayes-Nash equilibrium or diverge from it.

Figures

Figures reproduced from arXiv: 2605.17607 by Jan-Sebastian Hoehener, Martin Bichler.

Figure 1
Figure 1. Figure 1: Projected gradient dynamics with m = 2 and δ = 1/10. This Proposition allows to determine explicitly the game gradient for any profit kernel and m ∈ N. In case of the all-or-nothing demand Π(p, c) = p − c and m = 2, this yields v(x) =   − 7 48 − 3x2 48x1 + 5 48x1 − 1 3 − x2 8x1 + 3 16x1 + 1 24x2   . Let us recall a relevant proposition from the literature which properly defines a Lyapunov function … view at source ↗
Figure 2
Figure 2. Figure 2: Stochastic Gradient Ascent plus offset for [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript studies stochastic first-order learning in a Bayesian Bertrand duopoly with private costs. It shows that the game violates monotonicity and the Minty variational inequality, so classical convergence theorems do not apply. Nevertheless, the authors prove that Euclidean Regularized Robbins-Monro (RRM) algorithms converge almost surely to the unique efficient Bayes-Nash equilibrium when the strategy space is restricted to a finite-dimensional subspace of symmetric piecewise-linear pricing functions. The proof proceeds by explicitly constructing a global Lyapunov function for the projected primal dynamics, establishing global asymptotic stability of the equilibrium, and then invoking standard stochastic-approximation arguments.

Significance. If the central claims hold, the work supplies the first rigorous almost-sure convergence guarantees for stochastic gradient-based pricing algorithms in an incomplete-information setting where standard stability conditions fail. The explicit Lyapunov construction in a non-monotone game is a technical contribution that may be useful beyond pricing applications. The result also supplies a principled theoretical counterpoint to experimental reports of collusion under Q-learning.

major comments (2)
  1. [§4] §4 (Duopoly analysis): The central claim rests on the assertion that the finite-dimensional restriction to symmetric piecewise-linear functions admits an explicitly constructible global Lyapunov function whose derivative is strictly negative away from the equilibrium. The manuscript provides only a high-level sketch of this derivative; the explicit functional form and the algebraic verification that the derivative is negative semi-definite (or negative definite after projection) are not supplied. Without these steps the global asymptotic stability result cannot be checked.
  2. [§5] §5 (Stochastic convergence): The passage from deterministic global stability to almost-sure convergence of the stochastic recursion invokes standard results on stochastic approximation with projection. The paper does not verify the required conditions on the noise process (martingale-difference property, uniform integrability, or boundedness of the iterates under the projection) nor cite the precise theorem being applied. These omissions are load-bearing because the setting already violates monotonicity, so the usual Lyapunov-drift arguments must be checked with extra care.
minor comments (3)
  1. [Introduction] The abstract states that the algorithms converge 'within a finite-dimensional approximation'; the introduction should clarify whether the target equilibrium is exactly the Bayes-Nash equilibrium of the original infinite-dimensional game or only of the restricted game.
  2. Notation for the projection operator and the regularization parameter is introduced without a dedicated table or list of symbols; this makes the later equations harder to follow.
  3. [Figure 1] Figure 1 (phase portrait of the deterministic dynamics) would benefit from an overlay of the level sets of the claimed Lyapunov function to illustrate the global decrease.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the major comments point by point below and will revise the manuscript to incorporate additional details where needed.

read point-by-point responses

  1. Referee: [§4] §4 (Duopoly analysis): The central claim rests on the assertion that the finite-dimensional restriction to symmetric piecewise-linear functions admits an explicitly constructible global Lyapunov function whose derivative is strictly negative away from the equilibrium. The manuscript provides only a high-level sketch of this derivative; the explicit functional form and the algebraic verification that the derivative is negative semi-definite (or negative definite after projection) are not supplied. Without these steps the global asymptotic stability result cannot be checked.

    Authors: We thank the referee for this observation. While the manuscript states that an explicit global Lyapunov function is constructed for the projected primal dynamics in the finite-dimensional symmetric piecewise-linear strategy space, we agree that the algebraic verification of its derivative was presented only at a high level. In the revised version we will supply the explicit functional form of the Lyapunov function together with the complete step-by-step algebraic computation showing that its derivative along the dynamics is strictly negative away from the equilibrium (after accounting for the projection). revision: yes

  2. Referee: [§5] §5 (Stochastic convergence): The passage from deterministic global stability to almost-sure convergence of the stochastic recursion invokes standard results on stochastic approximation with projection. The paper does not verify the required conditions on the noise process (martingale-difference property, uniform integrability, or boundedness of the iterates under the projection) nor cite the precise theorem being applied. These omissions are load-bearing because the setting already violates monotonicity, so the usual Lyapunov-drift arguments must be checked with extra care.

    Authors: We agree that the required conditions on the noise process and the precise invocation of the stochastic-approximation theorem should be stated explicitly, especially given the absence of monotonicity. In the revision we will add a dedicated paragraph (or subsection) that verifies the martingale-difference property, uniform integrability of the noise, and boundedness of the projected iterates, and we will cite the exact theorem applied (e.g., the relevant result on projected stochastic approximation from Kushner and Yin or Borkar). revision: yes

Circularity Check

0 steps flagged

Central convergence proof is an explicit Lyapunov construction in a restricted strategy space; independent of fitted inputs or self-citation chains

full rationale

The derivation proceeds by restricting to symmetric piecewise-linear pricing functions in duopoly, explicitly constructing a global Lyapunov function for the projected primal dynamics, establishing global asymptotic stability, and then invoking standard stochastic-approximation results for almost-sure convergence. This chain is self-contained and does not reduce any claimed prediction or equilibrium to a fitted parameter, self-defined quantity, or load-bearing self-citation. Minor background self-citations may exist but are not invoked to justify the uniqueness or stability result itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof relies on standard convex analysis and stochastic approximation theory plus the modeling choice of a finite-dimensional piecewise-linear strategy space; no new invented entities are introduced.

axioms (1)
  • domain assumption Existence of a global Lyapunov function for the projected primal dynamics on symmetric piecewise-linear strategies
    Invoked to establish global asymptotic stability in the duopoly case

pith-pipeline@v0.9.0 · 5706 in / 1157 out tokens · 21158 ms · 2026-05-19T22:14:16.199865+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    The art of retail pricing: Developing a taxonomy for describing pricing algorithms.European Conference on Information Systems, 2024

    Clemens Brackmann, Tobias Wulfert, Jan Busch, and Reinhard Sch ¨utte. The art of retail pricing: Developing a taxonomy for describing pricing algorithms.European Conference on Information Systems, 2024

    work page 2024

  2. [2]

    Online Learning and Online Convex Optimization.Foundations and Trends® in Machine Learning, 4(2):107–194, 2011

    Shai Shalev-Shwartz. Online Learning and Online Convex Optimization.Foundations and Trends® in Machine Learning, 4(2):107–194, 2011

    work page 2011

  3. [3]

    Book review of theorie mathematique de la richesse social and of recherches sur les principes mathematiques de la theorie des richesses.Journal des Savants, 1883

    Joseph Bertrand. Book review of theorie mathematique de la richesse social and of recherches sur les principes mathematiques de la theorie des richesses.Journal des Savants, 1883

    work page

  4. [4]

    Algorithmic Pricing What Implications for Competition Policy?Review of Industrial Organization, 55(1):155–171, aug 2019

    Emilio Calvano, Giacomo Calzolari, Vincenzo Denicol`o, and Sergio Pastorello. Algorithmic Pricing What Implications for Competition Policy?Review of Industrial Organization, 55(1):155–171, aug 2019

    work page 2019

  5. [5]

    Autonomous algorithmic collusion: Q-learning under sequential pricing.The RAND Journal of Economics, 52(3):538–558, 2021

    Timo Klein. Autonomous algorithmic collusion: Q-learning under sequential pricing.The RAND Journal of Economics, 52(3):538–558, 2021

    work page 2021

  6. [6]

    Artificial Intelligence: Can Seemingly Collusive Outcomes Be Avoided?Management Science, 69(9):5042–5065, September 2023

    Ibrahim Abada and Xavier Lambin. Artificial Intelligence: Can Seemingly Collusive Outcomes Be Avoided?Management Science, 69(9):5042–5065, September 2023

    work page 2023

  7. [7]

    A unified stochastic approximation framework for learning in games.Mathematical Programming, 203(1):559–609, 2024

    Panayotis Mertikopoulos, Ya-Ping Hsieh, and V olkan Cevher. A unified stochastic approximation framework for learning in games.Mathematical Programming, 203(1):559–609, 2024

    work page 2024

  8. [8]

    Th ´eorie math´ematique de la richesse sociale.Journal des Savants, pages 499–508,

    Joseph Bertrand. Th ´eorie math´ematique de la richesse sociale.Journal des Savants, pages 499–508,

    work page

  9. [9]

    URLhttps://cruel.org/econthought/texts/marginal/bertrand83.pdf

    work page

  10. [10]

    Academic Press, Amsterdam and Boston, 2nd edition, 2010

    Vijay Krishna.Auction Theory. Academic Press, Amsterdam and Boston, 2nd edition, 2010. ISBN 978-0-12-374507-1

    work page 2010

  11. [11]

    Hartline

    Shuchi Chawla and Jason D. Hartline. Auctions with unique equilibria. InProceedings of the Fourteenth ACM Conference on Electronic Commerce, pages 181–196, New York, NY , USA, 2013. ACM. doi: 10.1145/2482540.2482558

    work page doi:10.1145/2482540.2482558 2013

  12. [12]

    Springer, 2003

    Francisco Facchinei and Jong-Shi Pang.Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

    work page 2003

  13. [13]

    Cavazzuti, M

    E. Cavazzuti, M. Pappalardo, and M. Passacantando. Nash equilibria, variational inequalities, and dynamical systems.Journal of Optimization Theory and Applications, 114(3):491–506, September 2002

    work page 2002

  14. [14]

    Beyond monotonicity: On the convergence of learning algorithms in standard auction games

    Martin Bichler, Stephan B Lunowa, Matthias Oberlechner, Fabian R Pieroth, and Barbara Wohlmuth. Beyond monotonicity: On the convergence of learning algorithms in standard auction games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 13649–13657, 2025

    work page 2025

  15. [15]

    Adaptive dynamics and evolutionary stability.Applied Mathematics Letters, 3:75–79, 1990

    Josef Hofbauer and Karl Sigmund. Adaptive dynamics and evolutionary stability.Applied Mathematics Letters, 3:75–79, 1990. doi: 10.1016/0893-9659(90)90018-H. MSC: 91h:92018

    work page doi:10.1016/0893-9659(90)90018-h 1990

  16. [16]

    Riemannian game dynamics.Journal of Economic Theory, 177:315–364, 2018

    Panayotis Mertikopoulos and William H Sandholm. Riemannian game dynamics.Journal of Economic Theory, 177:315–364, 2018

    work page 2018

  17. [17]

    Evolutionary game dynamics

    Josef Hofbauer and Karl Sigmund. Evolutionary game dynamics. Technical Report No. 76, Interim Report IR-03-078, International Institute for Applied Systems Analysis (IIASA), December 2003. URL https://pure.iiasa.ac.at/id/eprint/7010/1/IR-03-078.pdf. Approved by Ulf Dieckmann

    work page 2003

  18. [18]

    Stochastic approximations and differential inclusions

    Michel Bena¨ım, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328–348, 2005

    work page 2005

  19. [19]

    Computation of Lyapunov Functions under State Constraints using Semidefinite Programming Hierarchies.IFAC-PapersOnLine, 53(2):6281–6286, January 2020

    Marianne Souaiby, Aneel Tanwani, and Didier Henrion. Computation of Lyapunov Functions under State Constraints using Semidefinite Programming Hierarchies.IFAC-PapersOnLine, 53(2):6281–6286, January 2020

    work page 2020

  20. [20]

    A dynamical system approach to stochastic approximations.Siam Journal on Control and Optimization - SIAM J CONTR OPTIMIZAT, 34, 03 1996

    Michel Bena¨ım. A dynamical system approach to stochastic approximations.Siam Journal on Control and Optimization - SIAM J CONTR OPTIMIZAT, 34, 03 1996. doi: 10.1137/S0363012993253534

    work page doi:10.1137/s0363012993253534 1996

  21. [21]

    Asymptotic pseudotrajectories and chain recurrent flows, with applications.Journal of Dynamics and Differential Equations, 8:141–176, 12 1996

    Michel Bena¨ım and Morris Hirsch. Asymptotic pseudotrajectories and chain recurrent flows, with applications.Journal of Dynamics and Differential Equations, 8:141–176, 12 1996. doi: 10.1007/ BF02218617. 12 Convergence in Bertrand Competition Appendix 8 Proofs 8.1 Proof of Lemma 3.1 Proof.By definition, we have DU(β, ˜β−1)[d] = lim ε→0 ε−1 U1(β+εd, ˜β−1)−U...

    work page 1996