Home » Publication » 24820

Dettaglio pubblicazione

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

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.
ISBN: 9781450385541
Gruppo di ricerca: Algorithms and Data Science
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma