Dear Spiral user, We’re pleased to introduce Helix, https://helix.imperial.ac.uk/ Imperial’s new repository for research datasets. Please use Helix for all future dataset deposits. There is no change to Spiral - continue depositing as usual. For queries, contact the Research Data Management team at rdm-enquiries@imperial.ac.uk. Kind regards, the Spiral Team. The Spiral team
On the complexity of equilibrium computation in first-price auctions
OA Location
Author(s)
Filos-Ratsikas, Aris
Giannakopoulos, Yiannis
Hollender, Alexandros
Lazos, Philip
Poças, Diogo
Type
Journal Article
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 𝜀 -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.
Date Issued
2023-02-28
Date Acceptance
2022-09-14
Citation
SIAM journal on computing (Print), 2023, 52 (1), pp.80-131
URI
URL
DOI
ISSN
0097-5397
Publisher
Society for Industrial and Applied Mathematics
Start Page
80
End Page
131
Journal / Book Title
SIAM journal on computing (Print)
Volume
52
Issue
1
Publication Status
Published
Date Publish Online
2023-02-14