Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR06-031 | 27th February 2006 00:00

On the Approximation and Smoothed Complexity of Leontief Market Equilibria


Authors: Li-Sha Huang, Shang-Hua Teng
Publication: 6th March 2006 16:58
Downloads: 549


We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/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 \epsilon-approximate market equilibrium in time polynomial in m, n, and 1/\epsilon, unless PPAD \subseteq P. We also extend the analysis of our reduction to show, unless PPAD \subseteq RP, that the smoothed complexity of the Scarf's general fixed-point approximation algorithm (when applying to solve the approximate Leontief market exchange problem) or of any algorithm for computing an approximate market equilibrium of Leontief economies is not polynomial in n and 1/\sigma, under Gaussian or uniform perturbations with magnitude \sigma.

ISSN 1433-8092 | Imprint