Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response

Kexin Huang, Ziqian Chen, Xue Wang, Chongming Gao, Jinyang Gao, Bolin Ding, Xiang Wang
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:25159-25184, 2025.

Abstract

Auction plays a crucial role in many modern trading environments, including online advertising and public resource allocation. As the number of competing bidders increases, learning Bayesian Nash Equilibrium (BNE) in auctions faces significant scalability challenges. Existing methods often experience slow convergence in large-scale auctions. For example, in a classic symmetric auction setting, the convergence rate depends on the number of bidders quadratically. To address this issue, we propose the Approximate Best Response Gradient method, a new approach for learning BNE efficiently in auction games. We leverage an analytic solution for gradient estimation to enable efficient gradient computation during optimization. Moreover, we introduce the Best Response Distance objective, which serves as an upper bound of approximation quality to BNE. By optimizing the new objective, our method is proven to achieve a local convergence rate independent of bidder numbers and circumvent the traditional quadratic complexity in the classic symmetric setting. Extensive experiments across various auction formats demonstrate that our approach accelerates convergence and enhances learning efficiency in complex auction settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-huang25f, title = {Learning {B}ayesian {N}ash Equilibrium in Auction Games via Approximate Best Response}, author = {Huang, Kexin and Chen, Ziqian and Wang, Xue and Gao, Chongming and Gao, Jinyang and Ding, Bolin and Wang, Xiang}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {25159--25184}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/huang25f/huang25f.pdf}, url = {https://proceedings.mlr.press/v267/huang25f.html}, abstract = {Auction plays a crucial role in many modern trading environments, including online advertising and public resource allocation. As the number of competing bidders increases, learning Bayesian Nash Equilibrium (BNE) in auctions faces significant scalability challenges. Existing methods often experience slow convergence in large-scale auctions. For example, in a classic symmetric auction setting, the convergence rate depends on the number of bidders quadratically. To address this issue, we propose the Approximate Best Response Gradient method, a new approach for learning BNE efficiently in auction games. We leverage an analytic solution for gradient estimation to enable efficient gradient computation during optimization. Moreover, we introduce the Best Response Distance objective, which serves as an upper bound of approximation quality to BNE. By optimizing the new objective, our method is proven to achieve a local convergence rate independent of bidder numbers and circumvent the traditional quadratic complexity in the classic symmetric setting. Extensive experiments across various auction formats demonstrate that our approach accelerates convergence and enhances learning efficiency in complex auction settings.} }
Endnote
%0 Conference Paper %T Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response %A Kexin Huang %A Ziqian Chen %A Xue Wang %A Chongming Gao %A Jinyang Gao %A Bolin Ding %A Xiang Wang %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-huang25f %I PMLR %P 25159--25184 %U https://proceedings.mlr.press/v267/huang25f.html %V 267 %X Auction plays a crucial role in many modern trading environments, including online advertising and public resource allocation. As the number of competing bidders increases, learning Bayesian Nash Equilibrium (BNE) in auctions faces significant scalability challenges. Existing methods often experience slow convergence in large-scale auctions. For example, in a classic symmetric auction setting, the convergence rate depends on the number of bidders quadratically. To address this issue, we propose the Approximate Best Response Gradient method, a new approach for learning BNE efficiently in auction games. We leverage an analytic solution for gradient estimation to enable efficient gradient computation during optimization. Moreover, we introduce the Best Response Distance objective, which serves as an upper bound of approximation quality to BNE. By optimizing the new objective, our method is proven to achieve a local convergence rate independent of bidder numbers and circumvent the traditional quadratic complexity in the classic symmetric setting. Extensive experiments across various auction formats demonstrate that our approach accelerates convergence and enhances learning efficiency in complex auction settings.
APA
Huang, K., Chen, Z., Wang, X., Gao, C., Gao, J., Ding, B. & Wang, X.. (2025). Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:25159-25184 Available from https://proceedings.mlr.press/v267/huang25f.html.

Related Material