pipette
ESEspañol

On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated Priors

Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell

Preprint

In the authors' words

We show that computing an approximate mixed Bayes-Nash equilibrium in a discrete first-price auction with correlated priors is PPAD-complete. The key intermediate step in our reduction is the PPAD-completeness of computing an approximate Nash equilibrium in a new normal-form game, the hypergraph discrete first-price auction, which may be of independent interest.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.