Economics and Computation Series
On the Complexity of Equilibrium Computation in First-Price Auctions
24th 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.
Maintained by Nicos Protopapas