Papers for

algorithm developers for economic simulations

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Computing mixed equilibria in auctions with linked values is hard

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

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.

Tue 6 OctComputer Science and Game TheoryComputational Complexity
The gist
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.
Open → 2610.07858v1