ECCC-Report TR06-031https://eccc.weizmann.ac.il/report/2006/031Comments and Revisions published for TR06-031en-usMon, 06 Mar 2006 16:58:25 +0200
Paper TR06-031
| On the Approximation and Smoothed Complexity of Leontief Market Equilibria |
Li-Sha Huang,
Shang-Hua Teng
https://eccc.weizmann.ac.il/report/2006/031We 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.
Mon, 06 Mar 2006 16:58:25 +0200https://eccc.weizmann.ac.il/report/2006/031