Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Li-Sha Huang:

TR06-031 | 27th February 2006
Li-Sha Huang, Shang-Hua Teng

On the Approximation and Smoothed Complexity of Leontief Market Equilibria

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 ... more >>>

TR05-074 | 8th June 2005
Li-Sha Huang, Xiaotie Deng

On Complexity of Market Equilibria with Maximum Social Welfare

We consider the computational complexity of the market equilibrium
problem by exploring the structural properties of the Leontief
exchange economy. We prove that, for economies guaranteed to have
a market equilibrium, finding one with maximum social welfare or
maximum individual welfare is NP-hard. In addition, we prove that
counting the ... more >>>

ISSN 1433-8092 | Imprint