# why_prices_need_algorithms__2b6f7d86.pdf

Why Prices Need Algorithms

Tim Roughgarden Stanford University, Stanford CA

tim@cs.stanford.edu

Inbal Talgam-Cohen Hebrew University, Jerusalem Israel

inbaltalgam@gmail.com

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 de-

mand , 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

1A 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.

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, wel-

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

fare 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.2To 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

2Such 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.

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

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 co NP.

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.

[Ben-Zwi et al., 2013] Oren Ben-Zwi, Ron Lavi, and Ilan

Newman. Ascending auctions and Walrasian equilibrium. Working paper, 2013.

[Bikhchandani and Ostroy, 2002] Sushil Bikhchandani and

Joseph M. Ostroy. The package assignment model. Journal of Economic Theory, 107(2):377 406, 2002. Following 1998 technical report.

[Candogan and Pekec, 2014] Ozan Candogan and Sasa Pekec. Efficient iterative auctions for multi-featured items: A network flow approach. In submission, 2014.

[Candogan et al., 2014] Ozan Candogan, Asuman Ozdaglar,

and Pablo Parrilo. Iterative auction design for graphical valuations part II: General graphs. In submission, 2014.

[Candogan et al., 2015] Ozan Candogan, Asuman Ozdaglar,

and Pablo Parrilo. Iterative auction design for tree valuations. To appear in Operations Research, 2015.

[Chen et al., 2009a] Xi Chen, Decheng Dai, Ye Du, and

Shang-Hua Teng. Settling the complexity of Arrow Debreu equilibria in markets with additively separable utilities. In 50th, pages 273 282, 2009.

[Chen et al., 2009b] Xi Chen, Xiaotie Deng, and Shang-Hua

Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3), 2009.

[Daskalakis et al., 2009] Constantinos Daskalakis, Paul W.

Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195 259, 2009.

[Fischer et al., 2006] Felix A. Fischer, Markus Holzer, and

Stefan Katzenbeisser. The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria. Information Processing Letters, 99(6):239 245, 2006.

[Garey and Johnson, 1979] M. R. Garey and D. S. Johnson.

Computers and Intractability: A Guide to the Theory of NP-Completeness. 1979.

[Gul and Stacchetti, 1999] Faruk Gul and Ennio Stacchetti.

Walrasian equilibrium with gross substitutes. Journal of Economic Theory, 87:95 124, 1999.

[Kelso and Crawford, 1982] Alexander S. Kelso and Vin-

cent P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50(6):1483 1504, 1982. [Milgrom, 2000] Paul R. Milgrom. Putting auction theory

to work: The simultaneous ascending auction. Journal of Political Economy, 108(2):245 272, 2000. [Nisan and Segal, 2006] Noam Nisan and Ilya Segal. The communication requirements of efficient allocations and supporting prices. 129:192 224, 2006. [Papadimitriou and Wilkens, 2011] Christos H. Papadimitriou and Christopher A. Wilkens. Economies with nonconvex production and complexity equilibria. In 12th, pages 137 146, 2011. [Parkes and Ungar, 2000] David C. Parkes and Lyle H. Un-

gar. Iterative combinatorial auctions: Theory and practice. In 17th, pages 74 81, 2000. [Roughgarden and Talgam-Cohen, 2015] Tim Roughgarden

and Inbal Talgam-Cohen. Why prices need algorithms. In 16th, pages 19 36, 2015. [Sun and Yang, 2006] Ning Sun and Zaifu Yang. Equilibria

and indivisibilities: Gross substitutes and complements. Econometrica, 74(5):1385 1402, 2006. [Sun and Yang, 2014] Ning Sun and Zaifu Yang. An efficient

and incentive compatible dynamic auction for multiple complements. Journal of Political Economy, 122(2):422 488, 2014. [Teytelboym, 2014] Alex Teytelboym. Gross substitutes and

complements: a simple generalization. Economics Letters, 123(2):135 138, 2014. [Walras, 1874] L eon Walras. Elements of Pure Economics.

Allen and Unwin, 1874. Published in 1954.