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 $arepsilon$-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.
2021, EC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation, Pages 454-476
On the Complexity of Equilibrium Computation in First-Price Auctions (04b Atto di convegno in volume)
Filos-Ratsikas Aris, Giannakopoulos Yiannis, Hollender Alexandros, Lazos Filippos, Pocas Diogo
Gruppo di ricerca: Algorithms and Data Science