More Web Proxy on the site http://driver.im/

research-article

Market equilibrium under separable, piecewise-linear, concave utilities

Authors:

Vijay V. Vazirani,

Mihalis YannakakisAuthors Info & Claims

Journal of the ACM (JACM), Volume 58, Issue 3

Article No.: 10, Pages 1 - 25

https://doi.org/10.1145/1970392.1970394

Published: 09 June 2011 Publication History

Abstract

We consider Fisher and Arrow--Debreu markets under additively separable, piecewise-linear, concave utility functions and obtain the following results. For both market models, if an equilibrium exists, there is one that is rational and can be written using polynomially many bits. There is no simple necessary and sufficient condition for the existence of an equilibrium: The problem of checking for existence of an equilibrium is NP-complete for both market models; the same holds for existence of an ε-approximate equilibrium, for ε = O(n⁻⁵). Under standard (mild) sufficient conditions, the problem of finding an exact equilibrium is in PPAD for both market models. Finally, building on the techniques of Chen et al. [2009a] we prove that under these sufficient conditions, finding an equilibrium for Fisher markets is PPAD-hard.

References

[1]

Arrow, K., and Debreu, G. 1954. Existence of an equilibrium for a competitive economy. Econometrica 22, 265--290.

[2]

Brainard, W. C., and Scarf, H. E. 2000. How to compute equilibrium prices in 1891. Cowles Foundation discussion paper. 1270.

[3]

Chen, X., Dai, D., Du, Y., and Teng, S.-H. 2009a. Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS).

Digital Library

[4]

Chen, X., Deng, X., and Teng, S.-H. 2009b. Settling the complexity of computing two-player Nash equilibria. J. ACM 56, 3.

Digital Library

[5]

Chen, X., and Teng, S.-H. 2009. Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC). 647--656.

Digital Library

[6]

Codenotti, B., Saberi, A., Varadarajan, K., and Ye, Y. 2006. Leontief economies encode two-player zero-sum games. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Digital Library

[7]

Codenotti, B., and Varadarajan, K. 2004. Efficient computation of equilibrium prices for markets with Leontief utilities. In Proceedings of the Conference on Automation Languages and Programming (ICALP).

[8]

Daskalakis, C., Goldberg, P., and Papadimitriou, C. 2009. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1, 195--259.

Digital Library

[9]

Deng, X., and Du, Y. 2008. The computation of approximate competitive equilibrium is PPAD-hard. Inform. Proc. Lett. 108, 369--373.

Digital Library

[10]

Devanur, N., and Kannan, R. 2008. Market equilibria in polynomial time for fixed number of goods or agents. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS). 45--53.

Digital Library

[11]

Devanur, N., Papadimitriou, C. H., Saberi, A., and Vazirani, V. V. 2008. Market equilibrium via a primal-dual-type algorithm. J. ACM 55, 5.

Digital Library

[12]

Eaves, B. C. 1976. A finite algorithm for the linear exchange model. J. Math. Econ. 3, 197--203.

[13]

Etessami, K., and Yannakakis, M. 2010. On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39, 6, 2531--2597.

Digital Library

[14]

Gale, D. 1960. Theory of Linear Economic Models. McGraw-Hill, New York.

[15]

Gale, D. 1976. The linear exchange model. J. Math. Econ. 3, 205--209.

[16]

Garey, M. R., and Johnson, D. S. 1979. Computer and Intractability: A Guide to the Theory of NP-Completeness. Freeman.

Digital Library

[17]

Goel, G., and Vazirani, V. V. 2010. A perfect price discrimination market model with production and a (rational) convex program for it. In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT). 186--197.

Digital Library

[18]

Huang, L.-S., and Teng, S.-H. 2007. On the approximation and smoothed complexity of leontief market equilibria. In Proceedings of the 1st Annual International Workshop in Frontiers in Algorithmics (FAW). Lecture Notes in Computer Science, vol. 4613, Springer, 96--107.

Digital Library

[19]

Jain, K. 2007. A polynomial time algorithm for computing the Arrow-Debreu market equilibrium for linear utilities. SICOMP 37, 1, 303--318.

Digital Library

[20]

Lemke, C., and Howson, J. 1964. Equilibrium points of bimatrix games. J. SIAM, 413--423.

[21]

Maxfield, R. R. 1997. General equilibrium and the theory of directed graphs. J. Math. Econ. 27, 1, 23--51.

[22]

Megiddo, N. 1988. A note on the complexity of P-matrix LCP and computing an equilibrium. IBM Res. rep. 6439. http://theory.stanford.edu/~megiddo/pdf/plcp.pdf.

[23]

Megiddo, N., and Papadimitriou, C. 1991. On total functions, existence theorems, and computational complexity. Theoret. Comput. Sci. 81, 317--324.

Digital Library

[24]

Papadimitriou, C. 1994. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48, 3, 498--532.

Digital Library

[25]

Scarf, H. 1967. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15, 1328--1343.

Digital Library

[26]

Scarf, H. 1973. The Computation of Economic Equilibria. Yale University Press.

[27]

Uzawa, H. 1962. Walras' existence theorem and Brower's fixpoint theorem. Econ. Stud. Quart. 13, 59--62.

[28]

Ye, Y. 2007. Exchange market equilibria with Leontief's utility: Freedom of pricing leads to rationality. Theoret. Comput. Sci. 378, 134--142.

Digital Library

Cited By

Chekuri CKulkarni PKulkarni RMehta RWooldridge MDy JNatarajan S(2024)1/2 - approximate MMS allocation for separable piecewise linear concave valuationsProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i9.28815(9590-9597)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i9.28815
Chen XKroer CKumar R(2024)The Complexity of Pacing for Second-Price AuctionsMathematics of Operations Research10.1287/moor.2022.000949:4(2109-2135)Online publication date: Dec-2024
https://doi.org/10.1287/moor.2022.0009
Deligkas AFearnley JHollender AMelissourgos T(2024)Pure-Circuit: Tight Inapproximability for PPADJournal of the ACM10.1145/367816671:5(1-48)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1145/3678166
Show More Cited By

Index Terms

Market equilibrium under separable, piecewise-linear, concave utilities
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

Our first result shows membership in PPAD for the problem of computing approximate equilibria for an Arrow-Debreu exchange market for piecewise-linear concave (PLC) utility functions. As a corollary we also obtain membership in PPAD for Leontief ...
The Complexity of Non-Monotone Markets

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and non-monotone ...
Nonseparable, Concave Utilities Are Easy---in a Perfect Price Discrimination Market Model

Recent results establishing evidence of intractability for such restrictive utility functions as additively separable, piecewise-linear and concave, under both Fisher and Arrow--Debreu market models, have prompted the question of whether we have failed to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 58, Issue 3

May 2011

122 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1970392

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2011

Accepted: 01 February 2011

Revised: 01 January 2011

Received: 01 December 2009

Published in JACM Volume 58, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

75
Total Citations
View Citations
831
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)7

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chekuri CKulkarni PKulkarni RMehta RWooldridge MDy JNatarajan S(2024)1/2 - approximate MMS allocation for separable piecewise linear concave valuationsProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i9.28815(9590-9597)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i9.28815
Chen XKroer CKumar R(2024)The Complexity of Pacing for Second-Price AuctionsMathematics of Operations Research10.1287/moor.2022.000949:4(2109-2135)Online publication date: Dec-2024
https://doi.org/10.1287/moor.2022.0009
Deligkas AFearnley JHollender AMelissourgos T(2024)Pure-Circuit: Tight Inapproximability for PPADJournal of the ACM10.1145/367816671:5(1-48)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1145/3678166
Deligkas AFearnley JHollender AMelissourgos TKleinberg RSaban DBergemann D(2024)Constant Inapproximability for Fisher MarketsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673533(13-39)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673533
Filos-Ratsikas AHansen KHøgh KHollender AMohar BShinkar IO'Donnell R(2024)PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex OptimizationProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649645(1204-1215)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649645
Gao RRoghani MRubinstein ASaberi A(2024)Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00085(1294-1331)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00085
Nan TGao YKroer CWilliams BChen YNeville J(2023)Fast and interpretable dynamics for fisher markets via block-coordinate updatesProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25723(5832-5840)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25723
Kell NSun KWilliams BChen YNeville J(2023)Approximations for indivisible concave allocations with applications to nash welfare maximizationProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i5.25708(5705-5713)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i5.25708
Chaudhury BGarg JMcGlaughlin PMehta R(2023)A Complementary Pivot Algorithm for Competitive Allocation of a Mixed MannaMathematics of Operations Research10.1287/moor.2022.131548:3(1630-1656)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1287/moor.2022.1315
Garg JHusić EVégh L(2023)An Auction Algorithm for Market Equilibrium with Weak Gross Substitute DemandsACM Transactions on Economics and Computation10.1145/362455811:3-4(1-24)Online publication date: 14-Sep-2023
https://dl.acm.org/doi/10.1145/3624558
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents