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.
On the Complexity of Equilibrium Computation in First-Price Auctions / Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Hollender, Alexandros; Lazos, Filippos; Pocas, Diogo. - (2021), pp. 454-476. (Intervento presentato al convegno ACM Conference on Economics and Computation tenutosi a Virtual Conference) [10.1145/3465456.3467627].
On the Complexity of Equilibrium Computation in First-Price Auctions
Filippos Lazos
;
2021
Abstract
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
Filos-Ratsikas_On-the-Complexity_2021.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.55 MB
Formato
Adobe PDF
|
1.55 MB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
