Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Market Equilibrium:
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