Learning in Möbius pricing games
Global last-iterate convergence of payoff-gradient learning in Bayesian bidding and pricing games under symmetric self-play.
The problem
When players repeatedly improve their bids or prices, will their strategies converge? This project studies Möbius pricing games, a class spanning first-price auctions, unit-demand pay-as-bid auctions, rank-based generalized first-price auctions, and homogeneous-good price competition with inelastic demand.
The class shares two structural properties: a direct payoff effect that is independent of the action, and a payoff difference at the allocation threshold that is affine in the action. The resulting payoff gradient depends on the strategy slope through a fractional-linear, or Möbius, expression.
The analysis concerns symmetric self-play: all players use a common strategy and apply the same payoff-gradient update at each type. Initial strategies may include pooling, where different types choose the same action.
-
Shared payoff structure
Bidding and pricing models satisfy the same structural conditions.
-
Transport and damping
A singular equation describes strategy error; comparison barriers control its decay.
-
Convergence and approximation
The current strategy reaches a unique rest point, with a constructive projected grid scheme.
What this work shows
- Global convergence, including pooling. Under the paper’s coefficient and metric assumptions, every continuous, weakly increasing feasible initial strategy generates a unique viscosity solution converging to the unique rest point.
- Explicit rates without monotonicity. Comparison barriers make the uniform strategy error a strict Lyapunov functional and yield rates with optimal algebraic exponents, without relying on monotonicity or Minty conditions.
- Equilibrium guarantees. In allocation games, the rest point is the unique weakly increasing symmetric equilibrium under the stated tie-breaking conditions. A positive lower slope bound turns strategy-error bounds into approximate-equilibrium guarantees.
- Constructive grid learning. A projected scheme with a slope floor provides error bounds under deterministic perturbations and almost-sure convergence on a fixed grid under martingale gradient noise.
Last-iterate convergence concerns the current strategy itself. Independent, asymmetric learning remains open. The draft includes a Lean 4 formalization of every numbered result.
Upcoming presentation
I will present a poster on this work at the Optimization in AI workshop at RICAM in Linz, Austria, from November 23–27, 2026.
Publications
-
Soon on arXiv
Bichler, M., Hierhager, P., & Hoehener, J. (2026). Last-Iterate Convergence of Payoff-Gradient Learning in Möbius Pricing Games.Abstract
We prove global last-iterate convergence of payoff-gradient learning, with explicit rates, in a class of Bayesian bidding and pricing games that includes first-price auctions, unit-demand pay-as-bid auctions, rank-based generalized first-price auctions, and homogeneous-good price competition with inelastic demand. The result holds for symmetric self-play: all players use a common strategy and apply the same payoff-gradient update at each type. Convergence is from every continuous weakly increasing feasible initial strategy, including pooling, and does not rely on the monotonicity or Minty conditions that underlie existing guarantees in other games. Instead, the class is characterized by two structural properties: a direct payoff effect that is independent of the action, and a payoff difference at the allocation threshold that is affine in the action. These properties reduce the learning dynamics to a singular transport–damping equation for the common strategy, which, under the stated coefficient and metric assumptions, admits a unique viscosity solution. Comparison barriers make the uniform distance to the unique rest point a strict Lyapunov functional and yield convergence rates with optimal algebraic exponents. In allocation games, the rest point is the unique weakly increasing symmetric equilibrium under the stated tie-breaking conditions, and a positive lower slope bound converts strategy-error bounds into explicit approximate-equilibrium guarantees. A projected grid scheme with a slope floor makes the approximation constructive, with error bounds under deterministic perturbations and almost-sure convergence on a fixed grid under martingale gradient noise.
BibTeX citation
@unpublished{bichler2026lastiterate, title = {Last-Iterate Convergence of Payoff-Gradient Learning in Möbius Pricing Games}, author = {Bichler, Martin and Hierhager, Philip and Hoehener, Jan}, year = {2026}, note = {Soon on arXiv}, }