On the computation of equilibria in discrete first-price auctions
File(s)
Accepted version
Author(s)
Filos-Ratsikas, Aris
Giannakopoulos, Yiannis
Hollender, Alexandros
Kokkalis, Charalampos
Type
Journal Article
Abstract
We study the computational complexity of computing Bayes–Nash equilibria in first-price auctions with discrete value distributions and discrete bidding space under general subjective beliefs. It is known that such auctions do not always have pure equilibria. In this paper, we prove that the problem of deciding their existence is NP-complete, even for approximate equilibria. On the other hand, it can be shown that mixed equilibria are guaranteed to exist; however, their computational complexity has not been studied before. We establish the PPAD-completeness of computing a mixed equilibrium and we complement this by an efficient algorithm for finding symmetric approximate equilibria in the special case of iid priors. En route to these results, we develop a computational equivalence framework between continuous and discrete first-price auctions, which can be of independent interest, and which allows us to transfer existing positive and negative results from one setting to the other. Finally, we show that correlated equilibria of the auction can be computed in polynomial time.
Date Issued
2026-10-01
Date Acceptance
2026-05-18
Citation
SIAM Journal on Computing, 2026, 55 (5), pp.851-902
ISSN
0097-5397
Publisher
Society for Industrial & Applied Mathematics (SIAM)
Start Page
851
End Page
902
Journal / Book Title
SIAM Journal on Computing
Volume
55
Issue
5
Copyright Statement
Copyright © 2026 Society for Industrial and Applied Mathematics. This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
License URL
Publication Status
Published
Date Publish Online
2026-09-10