Computer Science – Computer Science and Game Theory
Scientific paper
2006-02-26
Computer Science
Computer Science and Game Theory
Scientific paper
We show that the problem of finding an \epsilon-approximate Nash equilibrium of an n by n two-person games 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 is not in P, We also extend the analysis of our reduction to show, unless PPAD is not in 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.
Huang Li-Sha
Teng Shang-Hua
No associations
LandOfFree
On the Approximation and Smoothed Complexity of Leontief Market Equilibria does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Approximation and Smoothed Complexity of Leontief Market Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Approximation and Smoothed Complexity of Leontief Market Equilibria will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-6351