Abstract Why Prices Need Tim Roughgarden Stanford University, Stanford CA tim@cs.stanford.edu 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 complexitytheoretic 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. Model and Walrasian Equilibrium. Consider a standard market model with n consumers and m indivisible items. Each consumer i has a valuation function vi , which maps bundles of items to their value for the consumer in R 0 .1 Consumers are assumed to have quasi-linear utilities, i.e., their utility from a bundle is their value for it minus the bundle’s price. The leading notion of market equilibrium in our context is that of Walrasian equilibrium, which dates back to the workof [Walras, 1874]. Formally it consists of (i) an allocation ofthe items to the consumers, and (ii) a price for each item, sucthat the following conditions hold: 1. Every consumer is allocated a bundle that is in his “demand”, i.e., maximizes his utility given the prices; 2. The revenue is maximized given the prices, i.e., all items with non-zero prices are allocated. Intuitively, in Walrasian equilibrium the consumers are happy with their bundles and the seller cannot sell more items, so thmarket is stable. Moreover, the First Welfare Theorem states that the allocation in every Walrasian equilibrium is welfaremaximizing (where social welfare is measured as usual by the sum of consumer values). The properties of stability and 1 A valuation requires 2m numbers in general to represent; natural to assume that consumers either have succinctly represevaluations or oracle access to them.