On the complexity of equilibrium computation in first-price auctions∗

Filos-Ratsikas A, Giannakopoulos Y, Hollender A, Lazos P, Pocas D (2023)

Publication Type: Journal article

Publication year: 2023

Journal

SIAM Journal on Computing Society for Industrial and Applied Mathematics

Book Volume: 52

Pages Range: 80-131

Journal Issue: 1

DOI: 10.1137/21M1435823

Abstract

We consider the problem of computing a (pure) Bayes-Nash equilibrium in the firstprice 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.

Authors with CRIS profile

Ioannis Giannakopoulos Juniorprofessur für Algorithmic Game Theory

Involved external institutions

University of Edinburgh GB United Kingdom (GB) University of Oxford GB United Kingdom (GB) IOG Singapore Pte Ltd SG Singapore (SG) University of Lisbon / Universidade de Lisboa (ULisboa) PT Portugal (PT)

How to cite

APA:

Filos-Ratsikas, A., Giannakopoulos, Y., Hollender, A., Lazos, P., & Pocas, D. (2023). On the complexity of equilibrium computation in first-price auctions∗. SIAM Journal on Computing, 52(1), 80-131. https://dx.doi.org/10.1137/21M1435823

MLA:

Filos-Ratsikas, Aris, et al. "On the complexity of equilibrium computation in first-price auctions∗." SIAM Journal on Computing 52.1 (2023): 80-131.

BibTeX: Download