On the Complexity of Equilibrium Computation in First-Price Auctions

24^th February 2021, 13:00
Aris Filos-Ratsikas
University of Liverpool

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 agents have independent subjective prior beliefs about the value distributions of the other agents, computing an epsilon-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.

Joint work with Yiannis Giannakopoulos, Alexandros Hollender, Philip Lazos, and Diogo Pocas.