Jugal Garg
ABSTRACT
The classic Arrow-Debreu market model captures both production and consumption, two equally important blocks of an economy, however most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. In this paper we show two new results on markets with production. Our first result gives a polynomial time algorithm for Arrow-Debreu markets under piecewise linear concave (PLC) utilities and polyhedral production sets provided the number of goods is constant. This is the first polynomial time result for the most general case of Arrow-Debreu markets.
Our second result gives a novel reduction from an Arrow-Debreu market M (with production firms) to an equivalent exchange market M' such that the equilibria of M are in one-to-one correspondence with the equilibria of M'. Unlike the previous reduction by Rader where M' is artificially constructed, our reduction gives an explicit market M' and we also get: (i) when M has concave utilities and convex production sets (standard assumption in Arrow-Debreu markets), then M' has concave utilities, (ii) when M has PLC utilities and polyhedral production sets, then M' has PLC utilities, and (iii) when M has nested CES-Leontief utilities and nested CES-Leontief production, then M' has nested CES-Leontief utilities.
- K. Arrow and G. Debreu. 1954. Existence of an Equilibrium for a Competitive Economy. Econometrica 22 (1954), 265--290.Google Scholar
Cross Ref
- S. Basu, R. Pollack, and M.-F. Roy. 1996. On the combinatorial and algebraic complexity of quantifier elimination. JACM 43(6) (1996), 1002--1045. Google ScholarDigital Library
- S. Basu, R. Pollack, and M.-F. Roy. 2004. Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer.Google Scholar
- W. C. Brainard and H. E. Scarf. 2000. How to Compute Equilibrium Prices in 1891. Cowles Foundation Discussion Paper 1270 (2000).Google Scholar
- X. Chen, D. Dai, Y. Du, and S.-H. Teng. 2009. Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. In FOCS. 273--282. Google ScholarDigital Library
- X. Chen and S.-H. Teng. 2009. Spending is not easier than trading: on the computational equivalence of Fisher and Arrow-Debreu equilibria. In ISAAC. 647--656. Google ScholarDigital Library
- Bruno Codenotti, Sriram Pemmaraju, and Kasturi Varadarajan. 2005. On the polynomial time computation of equilibria for certain exchange economies. In SODA. 72--81. Google ScholarDigital Library
- O. de La Grandville. 2009. Economic growth: A unified approach. Cambridge University Press.Google Scholar
- N. Devanur and R. Kannan. 2008. Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. In FOCS. 45--53. Google ScholarDigital Library
- N. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani. 2008. Market Equilibrium via a Primal-Dual Algorithm for a Convex Program. JACM 55, 5 (2008). Google ScholarDigital Library
- Ran Duan and Kurt Mehlhorn. 2013. A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market. In ICALP. 425--436. Google ScholarDigital Library
- Jugal Garg, Ruta Mehta, and Vijay V. Vazirani. 2014a. Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Functions. In STOC. 525--534. Google ScholarDigital Library
- Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod. 2014b. Leontief Exchange Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness. In arXiv:1411.5060.Google Scholar
- Jugal Garg and Vijay V. Vazirani. 2014. On computability of Equilibria in Markets with Production. In SODA. 1329--1340. Google ScholarDigital Library
- K. Jain. 2007. A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. SIAM J. Comput. 37, 1 (2007), 306--318. Google ScholarDigital Library
- K. Jain and K. Varadarajan. 2006. Equilibria for economies with production: Constant-returns technologies and production planning constraints. In SODA. 688--697. Google ScholarDigital Library
- A. Mas-Colell. 1991. On the Uniqueness of Equilibrium Once Again. (1991).Google Scholar
- J. B. Orlin. 2010. Improved algorithms for computing Fisher's market clearing prices. In STOC. 291--300. Google ScholarDigital Library
- T. Rader. 1964. Edgeworth Exchange and General Economic Equilibrium. Yale Economic Essays 4 (1964), 133--181.Google Scholar
- T. Rutherford. 1999. Applied general equilibrium modeling with MPSGE as a GAMS subsystem: An overview of the modeling framework and syntax. Computational Economics 14 (1999), 1--46. Google ScholarDigital Library
- H. Scarf. 1967. The approximation of fixed points of a continuous mapping. SIAM Journal of Applied Mathematics 15, 1 (1967), 1328--1343.Google ScholarCross Ref
- J. B. Shoven and J. Whalley. 1992. Applying general equilibrium. Cambridge University Press.Google Scholar
- S. Smale. 1976. A convergent process of price adjustment and global newton methods. Journal of Mathematical Economics 3(2) (1976), 107--120.Google Scholar
- H. Sonnenschein. 1973. Do Walras' identity and continuity characterize the class of community excess-demand functions? Journal of Economic Theory 6 (1973), 345--354".Google ScholarCross Ref
- Vijay V. Vazirani and Mihalis Yannakakis. 2011. Market equilibrium under separable, piecewise-linear, concave utilities. Journal of ACM 58, 3 (2011), 10:1--10:25. Google ScholarDigital Library
- Laszlo A. Vegh. 2012. Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. In STOC. Google ScholarDigital Library
- Yinyu Ye. 2008. A path to the Arrow-Debreu competitive market equilibrium. Math. Program. 111(1--2) (2008), 315--348. Google ScholarDigital Library
Index Terms
- Markets with Production: A Polynomial Time Algorithm and a Reduction to Pure Exchange
Recommendations
Earning and Utility Limits in Fisher Markets
Earning limits and utility limits are novel aspects in the classic Fisher market model. Sellers with earning limits have bounds on their income and lower the supply they bring to the market if income exceeds the limit. Buyers with utility limits have an ...
On competitiveness in uniform utility allocation markets
We call a market competitive if increasing the endowment of one buyer does not increase the equilibrium utility of another. We show that every competitive uniform utility allocation market is a submodular utility allocation market, answering a question ...
Multiplicative Pacing Equilibria in Auction Markets
Budgets play a significant role in ad markets that implement sequential auctions such as those hosted by internet companies. In “Multiplicative Pacing Equilibria in Auction Markets,” the authors look at pacing in an ad marketplace using the lens of game ...
Budgets play a significant role in real-world sequential auction markets such as those implemented by internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best ...
Comments