Efficient Equilibrium Computation in Symmetric First-Price Auctions
This solves a long-standing computational complexity issue for auction theory, with applications in economics and mechanism design.
The paper tackles the problem of computing Bayes-Nash equilibria in symmetric first-price auctions, presenting the first efficient algorithms for bidders with i.i.d. values, achieving polynomial-time solutions in white-box models and query-efficient ones in black-box models.
We study the complexity of computing Bayes-Nash equilibria in single-item first-price auctions. We present the first efficient algorithms for the problem, when the bidders' values for the item are independently drawn from the same continuous distribution, under both established variants of continuous and finite bidding sets. More precisely, we design polynomial-time algorithms for the white-box model, where the distribution is provided directly as part of the input, and query-efficient algorithms for the black-box model, where the distribution is accessed via oracle calls. Our results settle the computational complexity of the problem for bidders with i.i.d. values.