Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities

DOI10.1109/FOCS.2009.29zbMath1292.91113MaRDI QIDQ5171211

Xi Chen, Ye Du, Decheng Dai, Shang-Hua Teng

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

91B50: General equilibrium theory

Related Items

Inapproximability of Nash Equilibrium, Constant Rank Two-Player Games are PPAD-hard, Ascending-Price Algorithms for Unknown Markets, Computing Large Market Equilibria Using Abstractions, Amortized Analysis of Asynchronous Price Dynamics, Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm, Unnamed Item, Unnamed Item, The classes PPA-\(k\): existence from arguments modulo \(k\), The classes PPA-\(k\): existence from arguments modulo \(k\), The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, Public goods games in directed networks, A smooth path-following algorithm for market equilibrium under a class of piecewise-smooth concave utilities, Market equilibrium under piecewise Leontief concave utilities, An alternating algorithm for finding linear Arrow-Debreu market equilibria, Discrete versions of the KKM lemma and their PPAD-completeness, Computing equilibria for markets with constant returns production technologies, A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for It, A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities