Gradient Dynamics in First-Price Auctions: Iterative Strategy Elimination via Cubic Potentials
2026-06-03 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors studied how bidders learn to bid in first-price auctions when bids can only take certain discrete values. They showed that if bidders use a method called online gradient ascent to update their bids over time, the average outcome ends up close to what would happen in a second-price auction, which is known to be efficient. To prove this, the authors created new mathematical tools involving potential functions to better understand how strategies evolve, ensuring some bad strategies get dropped over time. These tools may also help analyze other game situations beyond auctions.
first-price auctionssecond-price auctionsonline gradient ascentnormal-form gamespotential functionsiterative eliminationregret minimizationdiscrete biddingstrategy convergencegame theory
Authors
Mete Şeref Ahunbay, Weiqiang Zheng, Tao Lin
Abstract
We show that in discretised first-price auctions with complete information, if the buyers learn to bid with online gradient ascent, in time-average the outcome is (almost) the efficient outcome of the second-price auction. Our proof rests on two novel innovations in the analysis of online gradient ascent in normal-form games, which may be useful in a wider range of applications. First, we develop a potential-function-based argument for the analysis of gradient ascent in normal-form games, allowing us to deduce that certain strategies will not be played in time-average. We provide sufficient conditions which ensure this argument can be applied iteratively, resulting in a procedure reminiscent of iterative elimination of dominated strategies. Second, we develop a novel class of cubic "candidate potential functions", classifying a family of quadratic strategy modifications on the probability simplex against which online gradient ascent incurs no regret.