On the Complexity of Equilibrium Computation in First-Price Auctions

Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114, Giannakopoulos, Yiannis, Hollender, Alexandros, Lazos, Philip and Poças, Diogo (2021) On the Complexity of Equilibrium Computation in First-Price Auctions. In: EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary.

Text
First_Price_Arxiv (3).pdf - Submitted version
Download (772kB) | Preview

Official URL: http://dx.doi.org/10.1145/3465456.3467627

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 $\varepsilon$-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	24 Jun 2021 10:28
Last Modified:	18 Jan 2023 21:37
DOI:	10.1145/3465456.3467627
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3127549