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.
Citation:
@inproceedings{
huang2025learning,
title={Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response},
author={Kexin Huang and Ziqian Chen and Xue Wang and Chongming Gao and Jinyang Gao and Bolin Ding and Xiang Wang},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
}
Kexin Huang
黄科鑫
Chongming Gao
高崇铭 博士后
