The Complexity of Non-Monotone Markets

2012/11/21 by Xi Chen, Dimitris Paparas, Chen, Xi +3
Economics, Econometrics and Finance · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Economic Theory and Institutions #Economic Theory and Policy #Economic theories and models #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1211.4918

openalex publication_date 2012/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ρis any constant less than -1.

Citations

• The Complexity of Computing a Nash Equilibrium
• Settling the complexity of computing two-player Nash equilibria
• A Contribution to the Theory of Economic Growth
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

Related

• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
• Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R
• On Computability of Equilibria in Markets with Production
• Non-Separable, Quasiconcave Utilities are Easy -- in a Perfect Price Discrimination Market Model