Why Prices Need Algorithms

Abstract

Computational complexity has already had plenty to say about the computation of economic equilibria [Fischer et al., 2006; Chen et al., 2009b; 2009a; Daskalakis et al., 2009; Papadimitriou and Wilkens, 2011]. However, understanding when equilibria are guaranteed to exist is a central theme in economic theory, seemingly unrelated to computation. In this note we survey our main results from [Roughgarden and Talgam-Cohen, 2015], which show that the existence of equilibria in markets is inextricably connected to the computational complexity of related optimization problems, such as revenue or welfare maximization. We demonstrate how 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. PDF