2015/06/12 by Tim Roughgarden, Inbal Talgam-Cohen · 1 citation
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Economic theories and models #Game Theory and Applications
paper · doi:10.1145/2764468.2764515
openalex publication_date 2015/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Understanding when equilibria are guaranteed to exist is a central theme in economic theory, seemingly unrelated to computation. This paper shows that the existence of pricing equilibria is inextricably connected to the computational complexity of related optimization problems: demand oracles, revenue-maximization, and welfare-maximization. This relationship implies, under suitable complexity assumptions, a host of impossibility results. We also suggest a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept: such extensions seem to require the invention of novel polynomial-time algorithms for welfare-maximization.