The Complexity of Non-Monotone Markets

DOI10.1145/3064810MaRDI QIDQ4640292zbMATH OpenOpenAlexFDO

Authors Xi Chen, Mihalis Yannakakis, D. Paparas

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.4918, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.758.3575

zbMATH Keywords

Arrow-Debreu marketCES utilitiesFIXPmarket equilibrianon-monotone utilitiesPPAD

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Microeconomic theory (price theory and economic markets) (91B24) Special types of economic equilibria (91B52)

Abstract: 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 utilities. Building on this result, we settle the long-standing open problem regarding the computation of an approximate Arrow-Debreu market equilibrium in markets with CES utility functions, by proving that it is PPAD-complete when the Constant Elasticity of Substitution parameter ho is any constant less than -1.

Recommendations

• The complexity of non-monotone markets
• On the complexity of price equilibria
• scientific article; zbMATH DE number 2084631
• Complex dynamics and multistability with increasing rationality in market games
• On the complexity of market equilibria with maximum social welfare
• Bargaining and markets: Complexity and the competitive outcome
• Complex market dynamics under Box--Cox monopoly
• Nonlinearity, Bounded Rationality, and Heterogeneity
• Market coordination under non-equilibrium dynamics
• The complexity of resource allocation and price mechanisms under bounded rationality

Cited in

(18)

• Nonlinearity, Bounded Rationality, and Heterogeneity
• scientific article; zbMATH DE number 791076 (Why is no real title available?)
• Ascending-price algorithms for unknown markets
• Amortized Analysis of Asynchronous Price Dynamics
• The complexity of non-monotone markets
• On the Complexity of Equilibrium Computation in First-Price Auctions
• Consensus-Halving: Does It Ever Get Easier?
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• Computational complexity of the -Ham-Sandwich problem
• Intersection classes in TFNP and proof complexity
• Pure-circuit: tight inapproximability for PPAD
• Separations in proof complexity and TFNP
• Computational complexity of the Hylland-Zeckhauser mechanism for one-sided matching markets
• Computational complexity of the Hylland-Zeckhauser scheme for one-sided matching markets
• Settling the complexity of Nash equilibrium in congestion games
• The computation of approximate competitive equilibrium is PPAD-hard
• Coase theorem, complexity and transaction costs

This page was built for publication: The Complexity of Non-Monotone Markets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640292)