Computing Bayes–Nash Equilibrium Strategies in Auction Games via Simultaneous Online Dual Averaging

Martin Bichler (), Max Fichtl () and Matthias Oberlechner ()
Additional contact information
Martin Bichler: Department of Computer Science, Technical University of Munich, 85748 Garching, Germany
Max Fichtl: Department of Computer Science, Technical University of Munich, 85748 Garching, Germany
Matthias Oberlechner: Department of Computer Science, Technical University of Munich, 85748 Garching, Germany

Operations Research, 2025, vol. 73, issue 2, 1102-1127

Abstract: Auctions are modeled as Bayesian games with continuous type and action spaces. Determining equilibria in auction games is computationally hard in general, and no exact solution theory is known. We introduce an algorithmic framework in which we discretize type and action space and then learn distributional strategies via online optimization algorithms. One advantage of distributional strategies is that we do not have to make any assumptions on the shape of the bid function. Besides, the expected utility of agents is linear in the strategies. It follows that, if our optimization algorithms converge to a pure strategy, then they converge to an approximate equilibrium of the discretized game with high precision. Importantly, we show that the equilibrium of the discretized game approximates an equilibrium in the continuous game. In a wide variety of auction games, we provide empirical evidence that the approach approximates the analytical (pure) Bayes–Nash equilibrium closely. This speed and precision are remarkable because, in many finite games, learning dynamics do not converge or are even chaotic. In standard models in which agents are symmetric, we find equilibrium in seconds. Whereas we focus on dual averaging, we show that the overall approach converges independent of the regularizer, and alternative online convex optimization methods achieve similar results even though the discretized game satisfies neither monotonicity nor variational stability globally. The method allows for interdependent valuations and different types of utility functions, and it can be used to find equilibrium in auction markets and beyond.

Keywords: Optimization; auctions; Bayes–Nash equilibrium; online convex optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0287 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:1102-1127

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().