Abstract
This paper resolves a long-standing open question in computational economics by establishing the complexity of finding an equilibrium in Arrow-Debreu exchange markets. The authors demonstrate that computing an equilibrium is PPAD-complete for markets where traders possess additively separable, piecewise-linear, and concave (PLC) utility functions. This result identifies a sharp complexity transition between linear and non-linear utility models and effectively rules out the existence of a fully polynomial-time approximation scheme (FPTAS) for this class of markets.
Introduction
The Arrow-Debreu model is a foundational pillar of mathematical economics, providing a rigorous framework for how prices in an exchange economy reach an equilibrium where supply equals demand. While the existence of such an equilibrium was proven in the 1950s using fixed-point theorems, its computational tractability has remained a central challenge in algorithmic game theory.
Prior research established that if utility functions are purely linear, an equilibrium can be found in polynomial time. However, the complexity for more realistic utility functions—specifically additively separable PLC utilities, where a trader's total utility is the sum of concave, piecewise-linear functions of individual goods—remained unknown. This paper "settles" the question, proving that even this modest extension of linear utilities pushes the problem into the realm of PPAD-completeness.
The Computational Gap: From P to PPAD-Complete
The paper reveals a sharp complexity threshold. In a "1-linear" market (purely linear utilities), the problem is in P. However, the authors show that "2-linear" markets—where utility functions consist of just two segments—are already PPAD-complete. This finding is significant because it identifies the exact point at which the market equilibrium problem becomes computationally intractable.
Furthermore, the proof demonstrates that finding even an approximate equilibrium is hard. This implies that the problem does not admit an FPTAS unless PPAD is solvable in polynomial time, a result that has profound implications for the predictive power of equilibrium theory in large-scale economies.
Methodology: The Price-Regulating Market
The core technical contribution is a sophisticated reduction from SPARSE BIMATRIX, a known PPAD-complete problem involving finding an approximate Nash equilibrium in a two-player game with sparse payoff matrices.
To bridge the gap between game theory and market dynamics, the authors introduce the Price-Regulating Market ($M_n$). This specially designed linear market with $n$ goods ensures that any approximate equilibrium price vector $\mathbf{p}$ has entries $p_k$ constrained within a tight range $[1, 2]$. By setting $x_k = p_k - 1$, the authors encode free variables between 0 and 1 directly into the market prices.
This price-regulation property is remarkably stable. The authors demonstrate that they can introduce additional traders—representing the constraints of a Nash equilibrium—without disrupting the price bounds. These "perturbations" allow the payoffs of a game to be mapped directly into the utility functions and endowments of traders in the market.
Key Insights and Implications
- Prices as Variables: A primary innovation is the realization that market prices can serve as a stable medium to encode probability distributions from a Nash equilibrium.
- Robustness of Market Structures: The authors show that markets can be constructed to maintain structural properties even when perturbed by new participants, allowing for modular constructions of complex market instances.
- Sparsity and Hardness: The hardness result persists even in "sparse" markets where each trader only owns or cares about a small, constant number of goods, suggesting that complexity is not driven by the number of interactions but by the underlying utility structure.
Conclusion
By proving that computing Arrow-Debreu equilibria for additively separable PLC utilities is PPAD-complete, this paper provides a definitive answer to a premier open question in the field. While the result highlights the computational limits of general equilibrium theory, the reduction techniques—specifically the use of price-regulating markets—provide a new toolkit for analyzing other market models. Future work may extend these techniques to resolve the complexity of markets with non-separable utilities, such as Constant Elasticity of Substitution (CES) or hybrid linear-Leontief models.
Summary updated