On the Approximation and Smoothed Complexity of

Li-Sha Huang, Shang‐Hua Teng2006

TL;DR

This paper establishes that finding approximate market equilibria in Leontief economies is computationally hard, specifically PPAD-hard. This implies that no efficient algorithm (a Fully Polynomial-Time Approximation Scheme) likely exists for this problem, even for approximate solutions. Furthermore, the paper shows that even with random "noise" (smoothed analysis), finding these equilibria remains computationally challenging.

What Problem Does This Paper Address?

The paper tackles the computational complexity of finding market equilibria, a fundamental concept in economics. Specifically, it focuses on "Leontief economies," a model where consumers have fixed proportions of goods they consume (like a recipe). The core question is whether we can efficiently find approximate market equilibria, meaning prices that lead to near-optimal outcomes for traders, even if not perfectly optimal. This is crucial because finding exact equilibria is known to be hard. The paper also investigates the "smoothed complexity" of this problem, which considers how algorithms perform when faced with slightly noisy or perturbed input data, a more realistic scenario.

Methods

The paper's main contribution comes from a clever reduction: they show how to transform a problem of finding an approximate Nash equilibrium in a two-person game into the problem of finding an approximate market equilibrium in a Leontief economy. This reduction is "polynomial," meaning the size of the Leontief problem grows manageably with the size of the game problem. By leveraging existing results that show finding Nash equilibria is hard (PPAD-complete), this reduction implies that Leontief market equilibria are also hard to find.

They also extend this analysis to the realm of "smoothed complexity." This involves introducing random perturbations to the input matrices (endowments and demand) and analyzing the expected running time of algorithms. They demonstrate that even under these perturbations, the problem remains computationally difficult.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Leontief Economies are Fundamentally Hard: The paper strongly suggests that Leontief economies, despite their seemingly simple structure, pose significant computational challenges for finding equilibria, even approximate ones. This is a key differentiator from economies with simpler utility functions (like linear ones).
  • Nash Equilibrium Hardness Translates: The reduction from Nash equilibrium problems to Leontief economies is a powerful technique. It shows that the inherent difficulty of finding stable outcomes in strategic interactions (Nash equilibrium) is mirrored in the difficulty of finding stable prices in a market with fixed consumption ratios.
  • Smoothed Complexity Matters: The analysis of smoothed complexity highlights that even when inputs are "almost" structured, finding market equilibria is not necessarily easy. This is important for understanding the practical performance of algorithms in real-world scenarios where data is rarely perfect.
  • No Free Lunch for Approximations: The paper effectively argues that approximating market equilibria in Leontief economies doesn't offer a computational shortcut. The hardness of the exact problem carries over to approximate versions, suggesting that significant algorithmic breakthroughs are unlikely without advancements in the underlying complexity classes.

Key Results

  • The problem of finding an $\epsilon$-approximate Nash equilibrium of an $n \times n$ two-person game can be reduced to computing an $(\epsilon/n)^2$-approximate market equilibrium of a Leontief economy.
  • This reduction implies that the Leontief market exchange problem does not have a Fully Polynomial-Time Approximation Scheme (FPTAS), unless PPAD $\subseteq$ P. This means no algorithm is likely to exist that can find an $\epsilon$-approximate equilibrium in time polynomial in $n$ and $1/\epsilon$.
  • The paper shows that, unless PPAD $\subseteq$ RP, computing an equilibrium (or approximate equilibrium) of a Leontief economy is not in smoothed polynomial time, even under uniform or Gaussian perturbations.

Limitations and Future Work

  • Constant $\epsilon$ Approximation: The paper's hardness results for approximate equilibria are for cases where $\epsilon$ can be arbitrarily small (e.g., $1/n^c$). The authors pose conjectures about whether a polynomial-time approximation scheme might exist for a fixed constant $\epsilon$ (Conjecture 4) or for smoothed complexity with constant perturbations (Conjecture 5). These remain open questions.
  • Specific Perturbation Models: While the paper discusses uniform and Gaussian perturbations, other perturbation models might yield different results.
  • Generalizations: The paper focuses on Leontief economies. Extending these hardness results to other types of economies with more complex utility functions could be a future direction.

Summary updated

Abstract

We show that the problem of finding an �-approximate Nash equilibrium of an n× n two-person games can be reduced to the computation of an (�/n) 2 -approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, that is, there is no algorithm that can compute an �-approximate market equilibrium in time polynomial �
BibTeX
@misc{huang2006approximation,
  author = {Li-Sha Huang and Shang‐Hua Teng},
  title = {{On the Approximation and Smoothed Complexity of}},
  year = {2006},
}
Figure