Summary
Figuring out how bidders behave in complex auctions where their values are connected is very challenging. The authors show that even approximately predicting such behaviors is as hard as the toughest equilibrium problems known in computer science. They introduce a new type of game involving hypergraphs to prove this. This means that designing algorithms to find solutions in these auction settings is unlikely to be simple.
What this means in practice
- •For auction platform designers: Know the fundamental limits on efficiently computing equilibria in auctions where bidders’ values are correlated, guiding practical mechanism designs.
- •For algorithm developers for economic simulations: Focus on heuristic or approximate methods since exact equilibrium computations in correlated-value first-price auctions are computationally infeasible.
A theory result. No direct application yet.
Authors
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
Abstract
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.