Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-074 | 8th June 2005 00:00

On Complexity of Market Equilibria with Maximum Social Welfare

RSS-Feed




TR05-074
Authors: Li-Sha Huang, Xiaotie Deng
Publication: 14th July 2005 23:00
Downloads: 4698
Keywords: 


Abstract:

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 number of equilibrium prices is #P-hard.



ISSN 1433-8092 | Imprint