Abstract
Understanding the conditions under which market equilibria are guaranteed to exist is a cornerstone of economic theory. Traditionally viewed through the lens of preference structures and convexity, this paper demonstrates that the existence of Walrasian equilibria is fundamentally linked to the computational complexity of underlying optimization problems. We show that for equilibrium to be guaranteed, the task of individual utility maximization must be as computationally difficult as global welfare maximization. This relationship provides a unified framework for proving the non-existence of equilibrium in complex markets and suggests that the future of economic mechanism design is inextricably tied to algorithmic innovation.
Introduction
In the study of market dynamics, the Walrasian equilibrium represents a state of perfect stability: a set of prices where every consumer receives their preferred bundle of goods at those prices, and the market clears exactly. While the existence of such equilibria is well-established for specific classes of valuations—most notably "gross substitutes"—economists have long struggled to characterize the boundaries of this existence for more complex valuation models.
This paper addresses this challenge by shifting the perspective from traditional economic analysis to structural complexity theory. We propose that the failure of a market to reach equilibrium is not merely a failure of "convexity" or "preferences," but a manifestation of a computational gap between individual incentives and collective optimization.
The Technical Framework: Utility vs. Welfare
The core of our analysis rests on the relationship between two distinct algorithmic problems:
- Utility Maximization (The Demand Oracle): Given a set of prices, an individual consumer identifies the bundle of goods that maximizes their personal utility.
- Welfare Maximization (The Social Planner's Problem): A central authority allocates all available items among all consumers to maximize the sum of their total utilities.
The technical "bridge" connecting these problems is the Configuration Linear Program (LP). By applying the Ellipsoid Method, we demonstrate a fundamental reduction: if one can efficiently solve the Utility Maximization problem (which corresponds to the dual of the Configuration LP), one can solve the Welfare Maximization problem.
The Complexity Gap Principle
Our main theorem establishes a necessary condition for the guaranteed existence of a Walrasian equilibrium. For any class of valuations $\mathcal{V}$, if a Walrasian equilibrium is guaranteed to exist, then Utility Maximization for $\mathcal{V}$ must be as computationally hard as Welfare Maximization for $\mathcal{V}$ (via a polynomial-time Turing reduction).
This implies that if a "complexity gap" exists—where the global welfare problem is strictly harder than the local utility problem—a Walrasian equilibrium cannot be guaranteed. This provides a systematic "recipe" for proving impossibility results: to show that a market model lacks a guaranteed equilibrium, one simply needs to prove that maximizing collective welfare is harder than satisfying an individual consumer's demand.
Case Study: The Budget-Additive Market
The power of this framework is best illustrated through the example of budget-additive valuations, where consumers have a fixed cap on the total value they can derive from goods.
- The Local Problem: For a single consumer with a budget, finding the best bundle of goods at given prices is equivalent to the Knapsack Problem. While NP-hard, it is only "weakly" NP-hard.
- The Global Problem: For a social planner trying to maximize welfare across multiple such consumers, the task becomes equivalent to the Bin Packing Problem. This problem is "strongly" NP-hard.
Because Bin Packing is strictly harder than the Knapsack Problem (under standard complexity assumptions), our framework formally proves that markets with budget-additive valuations do not have guaranteed Walrasian equilibria. This explains why decades of economic intuition failed to find a stable pricing mechanism for such shoppers.
Implications and Future Directions
This research provides a complexity-theoretic explanation for why the Walrasian equilibrium concept has been so difficult to extend to more general settings. Any meaningful extension of pricing equilibrium to complex valuations—such as those involving "pair-demand" pricing—essentially requires the discovery of new polynomial-time algorithms for welfare maximization that do not rely on standard linear programming relaxations.
The bottleneck for economic theory is no longer just mathematical modeling, but algorithmic progress. The paper suggests that to find new, stable ways of pricing complex goods, researchers must focus on identifying valuation classes where the individual and collective optimization problems align computationally.
Summary updated