Gradient learning narrows equilibria in first-price auction games
Simultaneous Gradient Learning in First-Price Auctions
Computer Science and Game Theory
Summary
When people bid in auctions where they keep their bids secret, predicting outcomes can be tricky because many solutions fit the data. The authors studied how computers learning by adjusting bids little by little tend to settle on a smaller, more precise set of outcomes than standard predictions suggest. This happens because the learning rules rule out many unrealistic strategies, zooming in on what the authors call a Bayesian semicoarse correlated equilibrium, which lies between two classic solution ideas. Their work explains why certain algorithms work better in auctions when the possible bids are finely split into choices.
What this means in practice
- •For auction platform engineers: Improve auction design by simulating gradient-based bidding dynamics that converge reliably to focused equilibria, enhancing prediction accuracy for bidder behavior in first-price auctions.
- •For algorithmic trading teams: Use refined equilibrium models from discretized Bayesian games to better tune automated bidding strategies under private information conditions.
Authors
Janik Bürgermeister, Julius Durmann, Martin Bichler, Mete Şeref Ahunbay, Bary Pradelski, Marco Scarsini
Abstract
We study equilibrium learning in discretized Bayesian games, focusing on first-price auctions as a testbed for gradient-based learning dynamics under private information. While the symmetric independent private values model admits a unique Bayesian correlated equilibrium (BCE) in the continuous limit, standard convergence guarantees for gradient-based learners do not apply: classical no-regret theory predicts convergence only to Bayesian coarse correlated equilibria (BCCE), which can remain large and far from the competitive equilibrium even under fine discretizations. To bridge this gap, we introduce the notion of Bayesian semicoarse correlated equilibrium (BSCCE), an equilibrium concept that refines BCCE by restricting deviations to probability-preserving transformations consistent with projected gradient dynamics. We provide a linear programming characterization of BSCCE with polynomially many variables and constraints and establish the inclusion hierarchy $BCE \subseteq BSCCE \subseteq BCCE$. Our main finding is that the BSCCE set contracts in many cases as the discretization of the Bayesian game is refined. Even with priors for which BCCE fails to concentrate, the diameter of the BSCCE polytope shrinks toward zero, indicating convergence to the unique continuous-game Bayes-Nash equilibrium. These results provide a principled explanation for the observed robustness of gradient-based learning in discretized Bayesian games, showing that these dynamics select a smaller equilibrium set than standard no-regret theory predicts.