LASIGE researcher Diogo Poças published joint work with Aris Filos-Ratsikas (University of Edinburgh), Yiannis Giannakopoulos (Friedrich-Alexander-Universität Erlangen Nürnberg), Alexandros Hollender (University of Oxford) and Philip Lazos (Input Output) in the SIAM Journal on Computing (SCIMAGO Q1). The paper, entitled “On the Complexity of Equilibrium Computation in First-Price Auctions”, considers the problem of computing a (pure) Bayes-Nash equilibrium in the first-price auction with continuous value distributions and discrete bidding space. The paper proves that when bidders have independent subjective prior beliefs about the value distributions of the other bidders, computing an epsilon-equilibrium of the auction is PPAD-complete, and computing an exact equilibrium is FIXP-complete.

The research lies in the important research direction of understanding the complexity of computing equilibria. The first price auction is a fundamental auction format and it is widely used in practice. The main result can be interpreted intuitively as justification of why research in economics has only had limited success in providing closed forms or characterizations for the equilibria of the first-price auction. In addition, the paper is a valuable addition to the literature of total search problems, as it concerns the computation of equilibria of one of the most fundamental games in auction theory.

The paper is available here.