The computation of approximate competitive equilibrium is PPAD-hard
Arrow and Debreu showed in 1954 that, under mild conditions, a competitive economy always has an equilibrium. In this paper, we show that, given a competitive economy that fully respects all the conditions of Arrow-Debreu's existence theorem, for any positive constant h > 0, it is PPAD-hard to compute a 1/n(h)-approximate competitive equilibrium (C) 2008 Elsevier B.V. All rights reserved.
competitive equilibrium leontief economy ppad computational complexity