Gradient Dynamics in First-Price Auctions: Iterative Strategy Elimination via Cubic Potentials
For auction designers and researchers in online learning, this provides theoretical justification that gradient-based learning can yield efficient outcomes in first-price auctions, bridging the gap between first- and second-price auction theory.
The paper shows that in discretised first-price auctions with complete information, online gradient ascent learning leads to the efficient outcome of second-price auctions in time-average. It introduces two novel analysis tools: a potential-function-based argument for iterative strategy elimination and a class of cubic potential functions for regret analysis.
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.