# On the Complexity of Equilibrium Computation in First-Price Auctions

arXiv: https://arxiv.org/abs/2103.03238 · HTML: https://mlsanity.com/paper/2103.03238/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2021.

## Built on by (most cited first, 6 of 6)

- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)

## Abstract (arXiv)

We consider the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. We prove that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an varepsilon-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete. We also provide an efficient algorithm for solving a special case of the problem, for a fixed number of bidders and available bids.