Why Prices Need Algorithms

Why Prices Need Algorithms

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 work of [Walras, 1874]. Formally it consists of (i) an allocation of the items to the consumers, and (ii) a price for each item, such that 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 the market 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; it is natural to assume that consumers either have succinctly represented valuations or oracle access to them.

Inbal Talgam-Cohen

Hebrew University, Jerusalem Israel inbaltalgam@gmail.com

social efficiency lead to the question: for which classes of markets is a Walrasian equilibrium guaranteed to exist?

Main Result for Walrasian Equilibrium. [Kelso and Crawford, 1982] introduced the class of "gross substitutes" valuations for which existence is guaranteed. [Gul and Stacchetti, 1999; Milgrom, 2000] showed a partial converse: any class of valuations which includes at least one non-grosssubstitutes valuation, as well as all "unit-demand" valuations (a subclass of gross substitutes), cannot have guaranteed existence of a Walrasian equilibrium. Since many natural valuation classes do not subsume unit-demand valuations, research proceeded to study additional classes in a relatively ad hoc fashion [Parkes and Ungar, 2000; Sun and Yang, 2006; Ben-Zwi et al., 2013; Candogan et al., 2014; Candogan and Pekec, 2014; Sun and Yang, 2014; Teytelboym, 2014; Candogan et al., 2015].

We introduce an approach to equilibrium non-existence results that is arguably more systematic. Here is our main theorem for Walrasian equilibrium:

Theorem (Proposition 2.1 in [Roughgarden and Talgam-Cohen, 2015]). A necessary condition for the guaranteed existence of a Walrasian equilibrium in markets with valuations from class V is that utility maximization for V given item prices is as hard computationally as welfare maximization for V.

Theorem establishes a link between a purely economic question - existence of equilibrium - and a purely algorithmic one. Welfare maximization and utility maximization are two algorithmic problems associated with the valuation class V: In the former, a social planner gets as input consumer valuations and outputs a welfare-maximizing allocation. In the latter, also known as answering demand queries, a consumer gets as input a vector of item prices, and outputs a bundle of items that maximizes his utility given these prices. By "as hard as computationally" we refer to the existence of a polynomial-time Turing reduction from welfare maximization to utility maximization. The proof leans on the wellknown "configuration" linear program, and its solution via the ellipsoid method [Nisan and Segal, 2006].

Sample Application. We restate Theorem in contrapositive form, and demonstrate its usefulness for proving nonexistence results.

Corollary. If, under standard complexity assumptions, welfare maximization in markets with valuations from class V cannot be reduced to utility maximization for V given item prices, then the existence of a Walrasian equilibrium is not guaranteed.

Impossibility results following from this corollary make use of the mature understanding of computational complexity to explain non-existence, and have an added dependence on complexity assumptions. As a concrete example, imagine a consumer contemplating what to have for dessert. He has different values for different desserts, and an aggregate value for a bundle of desserts up to a capacity b on the total value he can extract from dessert. 2 To maximize his utility such a consumer must maximize the total value that fits within his capacity while minimizing the total price, and this reduces to the well-known knapsack problem. In comparison, the welfare maximization problem involves n different capacities for the n consumers, and is thus as hard as the bin packing problem. While knapsack and bin packing are both NP-hard, the former is only weakly so while the latter is strongly so [Garey and Johnson, 1979]. 3 Applying Corollary we conclude that if P 6= NP, there exists a market with capacitated valuations and no Walrasian equilibrium.

Beyond Walrasian Equilibrium. Pricing can be much more general then one price per item. Mathematically speaking, a pricing function is as general as a valuation - a function from bundles to R≥0, which can be different for different consumers. Just as there are many classes of valuations, we can consider many classes of pricings for stabilizing a market. The generalization of the Walrasian equilibrium notion to allow for such classes is called a pricing equilibrium [Nisan and Segal, 2006] (see also [Bikhchandani and Ostroy, 2002]).

We would like to study pricing equilibria that maintain some of the nice properties of Walrasian equilibria, which have "simple" prices in three respects: they are anonymous (different consumers face the same prices); they are succinct in comparison to the class of valuations they stabilize (prices are m-dimensional, whereas the dimension of the gross substitutes valuation class is exponential in m); and they make the verification of the equilibrium tractable. The main question is then, what other simple and meaningful pricing equilibria exist? Or more accurately, why are no such equilibria known to date?

It turns out that the methodology we introduced for Walrasian equilibria can be adapted to deduce similar results to Theorem and Corollary for pricing equilibria, and we can use these to show the non-existence of interesting pricing equilibria for many markets that seem like natural candidates for positive results. For example, recall that unit-demand valuations guarantee an equilibrium with anonymous item prices; wouldn't "pair-demand" valuations guarantee an equilibrium with anonymous prices on pairs of items? A consequence of our results is that they would not, at least not unless NP ✓ coNP.

2 Such valuations are also known as "budget-additive". It is not hard to show that consumers with unit-demand valuations, that is, consumers who want no more than one dessert and therefore attribute to a bundle their highest value for any individual dessert in the bundle, are not in general budget-additive. Thus the non-existence result of [Gul and Stacchetti, 1999; Milgrom, 2000] does not apply.

3 This means that when values and capacities are polynomiallybounded integers, there is no reduction from welfare to utility maximization.

Our methodology also provides a general explanation to the dearth of useful extensions of the Walrasian equilibrium concept, by linking the existence of such extensions to algorithmic progress on the welfare maximization problem. In particular, designing a novel polynomial-time algorithm for the welfare-maximization problem, which does not rely on solving the configuration linear program, seems like a necessary step on the way to finding meaningful pricing equilibria. Designing such an algorithm is one of the main open questions arising from this work.