Computing Walrasian Equilibria: Fast Algorithms and Economic Insights

Renato Paes Leme, Sam Chiu-wai WongarXiv 2015 · OpenReview

TL;DR

This paper introduces the first polynomial-time algorithms for computing Walrasian equilibria, a fundamental concept in economics, using only aggregate demand information. For a special class of goods (gross substitutes), they achieve remarkable efficiency, even in a more restrictive "value oracle" model, and provide conditions for markets to be perfectly coordinated by prices alone.

What Problem Does This Paper Address?

The paper tackles the computationally challenging problem of finding a Walrasian equilibrium, which represents a state where supply meets demand for all goods in an economy. Traditionally, this requires detailed information about each individual buyer's preferences (microscopic view). However, in real-world markets, such granular data is often unavailable or impractical to collect. The authors aim to bridge this gap by developing algorithms that can compute equilibria using only aggregated market data (macroscopic view), specifically an "aggregate demand oracle" that reports the total quantity of each good demanded at given prices. They also explore the problem in the "value oracle" model, where individual buyer values for bundles are accessible, but still seek to improve efficiency. A key economic question they address is when prices alone can perfectly coordinate a market, ensuring each agent has a unique demand and the market clears.

Methods

The core of the paper lies in novel algorithmic approaches to convex optimization and its application to economic equilibrium problems.

  • Aggregate Demand Oracle: For general valuations, they transform the problem into minimizing a convex function that cannot be directly evaluated but whose subgradients can be computed. They adapt cutting-plane methods (like the Ellipsoid method) to work with subgradients only, overcoming the challenge of not knowing the function's exact value. This involves a clever perturbation and rounding technique to achieve exact solutions.
  • Gross Substitutes (Aggregate Demand): For the important "gross substitute" class of valuations, they leverage structural properties to simplify the convex optimization problem, leading to faster algorithms.
  • Gross Substitutes (Value Oracle): In the value oracle model, they develop an algorithm with a running time of $\widetilde{O}((mn + n^3) T_V)$, where $T_V$ is the cost of a value oracle query. This is achieved by regularizing the objective function to prevent overly aggressive steps and by reusing computations.
  • Robust Walrasian Prices: They provide necessary and sufficient conditions for the existence of "robust Walrasian prices" – prices that uniquely coordinate the market. This involves analyzing the structure of the Walrasian price polytope and its interior.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Macroscopic Equilibrium Computation: The most significant insight is demonstrating that Walrasian equilibria can be computed efficiently using only aggregate demand information, challenging the notion that detailed individual preferences are always necessary. This suggests markets can be viewed as emergent systems driven by collective behavior.
  • Subgradient-Based Optimization: The paper showcases the power of subgradient methods for optimizing convex functions that are not directly evaluable, a crucial technique for problems where only oracle access is available.
  • Structural Properties of Gross Substitutes: The authors exploit the specific mathematical structure of gross substitute valuations to derive more efficient algorithms and uncover important economic insights about market coordination.
  • Market Coordination by Prices: They establish that for gross substitute markets, robust Walrasian prices (which uniquely coordinate the market) exist if and only if there's a unique optimal allocation. This provides a clear condition for when prices alone can perfectly manage a market.

Key Results

  • First Polynomial-Time Algorithm (Aggregate Demand): They present the first polynomial-time algorithm for computing Walrasian equilibria using only an aggregate demand oracle for general buyer valuations.
  • Fastest Algorithm (Gross Substitutes, Aggregate Demand): For gross substitute valuations, their algorithm queries the aggregate demand oracle $\widetilde{O}(n)$ times and runs in $\widetilde{O}(n^3)$ time.
  • Fastest Algorithm (Gross Substitutes, Value Oracle): They achieve the fastest known algorithm for Walrasian equilibrium in the value oracle model with a running time of $\widetilde{O}((mn + n^3) T_V)$.
  • Conditions for Robust Walrasian Prices: They provide necessary and sufficient conditions for the existence of robust Walrasian prices and an algorithm to compute them in $\widetilde{O}(mn + n^3)$ time.

Limitations and Future Work

  • General Valuations vs. Gross Substitutes: While they provide an algorithm for general valuations, the most efficient results are for the specific case of gross substitutes. Extending these efficiencies to broader classes of valuations remains an open area.
  • Computational Complexity: Although polynomial, the exponents in the running times (e.g., $n^3$, $mn^3$) can still be significant for large problem instances. Further improvements in algorithmic techniques could be explored.
  • Practical Implementation: The paper focuses on theoretical computability. Investigating the practical performance and scalability of these algorithms on real-world market data would be a valuable next step.
  • Robust Walrasian Prices: The conditions for robust Walrasian prices are established, but further exploration into how to find such prices when they exist and their implications for market design could be beneficial.

Summary updated

Abstract

We present the first polynomial time algorithm for computing Walrasian equilibrium in an economy with indivisible goods and \emph{general} buyer valuations having only access to an \emph{aggregate demand oracle}, i.e., an oracle that given prices on all goods, returns the aggregated demand over the entire population of buyers. For the important special case of gross substitute valuations, our algorithm queries the aggregate demand oracle $\widetilde{O}(n)$ times and takes $\widetilde{O}(n^3)$ time, where $n$ is the number of goods. At the heart of our solution is a method for exactly minimizing certain convex functions which cannot be evaluated but for which the subgradients can be computed. We also give the fastest known algorithm for computing Walrasian equilibrium for gross substitute valuations in the \emph{value oracle model}. Our algorithm has running time $\widetilde{O}((mn + n^3) T_V)$ where $T_V$ is the cost of querying the value oracle. A key technical ingredient is to regularize a convex programming formulation of the problem in a way that subgradients are cheap to compute. En route, we give necessary and sufficient conditions for the existence of \emph{robust Walrasian prices}, i.e., prices for which each agent has a unique demanded bundle and the demanded bundles clear the market. When such prices exist, the market can be perfectly coordinated by solely using prices.
BibTeX
@misc{leme2015computing,
  author = {Renato Paes Leme and Sam Chiu-wai Wong},
  title = {{Computing Walrasian Equilibria: Fast Algorithms and Economic Insights}},
  year = {2015},
  eprint = {1511.04032},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1511.04032},
}
Figure