[OPE-L] Neo-classical Equilibrium shown to be NP-hard

From: Paul Cockshott (wpc@DCS.GLA.AC.UK)
Date: Mon Jul 31 2006 - 04:43:22 EDT

Implications of a new research result


One of the Hayekian objections to the notion of economic planning

Has been to object that the sheer scale of the economic problem is

such that although conceivable in principle, such computations would

be unrealisable in practice {Hayek:1955 p. 43),  and note 37 on pp.
212--213, of of The Counter-Revolution of Science.  In the note, Hayek
appeals to the judgment of Pareto and Cournot, that the solution of a
system of equations representing  the conditions of general equilibrium
would be practically  infeasible.  This is perhaps worth emphasizing in
view of the

tendency of Hayek's modern supporters to play down the computational



However neo-classical economists and the Austrian school have a very
particular concept of equilibrium. One possible concept of equilibrium
would be  Statistical equilibrium: not a point in phase space, but a
region defined by certain macroscopic variables, such that there is a
large set of microscopic conditions that are compatible with it. This is
the concept

advanced by Machover.


The concept of equilibrium with which Hayek was familiar was, in
contrast, that of a mechanical equilibrium, a unique position in at
which all forces

acting on the economy come into balance.

Arrow supposedly established the existence of this sort of equilibria
for competitive economies, but as Velupillai{2003} showed, his proof
rests on theorems that are only valid in non-constructive mathematics. 


Why does it matter whether Arrow used constructive or non-constructive


Because only constructive mathematics has an algorithmic implementation
and is guaranteed to be effectively computable. But even if 

a) a mechanical economic equilibrium can be proven to exist,

b) it can be shown that there is an effective procedure by which this

      be determined : i.e., the equilibrium is in principle computable,


there is still the question of its computation tractability. What

order governs the computation process that arrives at the solution?


 Suppose that an equilibrium exists, but that all algorithms to search
for it are NP-hard, that is, the algorithms may have a running time that
is exponential in the size of the problem.  This is just what has been
shown by Deng and Huang, (Information Processing Letters vol 97, 2006).


Their result might at first seem to support Hayek's contention that the

problem of rational economic planning is computationally intractable. In

Hayek's day, the notion of NP-hardness had not been invented, but he

would seem to have been retrospectively vindicated. Problems with

a computational cost that grows as exp(n) soon become astronomically

difficult to solve. 


I mean astronomical in a literal sense. One can readily specify an

problem that involves searching more possibilities than there are atoms

in the universe before arriving at a definite answer. Such problems,

although in principle finite, are beyond any practical solution.


But this knife cuts with two edges. On the one hand it shows that

no planning computer could solve the neo-classical problem of economic

equilibrium. On the other it shows that no  collection of millions of

individuals interacting via the market could solve it either. In 

neo-classical economics, the number of constraints on the equilibrium

will be proportional, among other things, to the number of economic
actors n.

The computational resource constituted by the  actors 

will be proportional to $n$ but the cost of the computation will grow as
en. Computational

resources grow linearly, computational costs grow exponentially.   This
means that

a market economy could never have sufficient computational resources

to find its own mechanical equilibrium.


It follows that the problem of finding the neo-classical equilibrium is
a mirage.

No planning system could discover it, but nor could the market. The
neo-classical problem of equilibrium misrepresents what capitalist
economies actually do and also sets an impossible goal for socialist


If you dispense with the notion of mechanical equilibrium and replace it
with statistical equilibrium one arrives at a problem that is much more
tractable. The simulations of Ian Wright show that a market economy can
rapidly converge on this sort of equilibrium. But  this is because
regulation by the law of

value is computationally tractable. This same tractability can be
exploited in a socialist planning system. Economic planning does not
have to solve the impossible problem of neo-classical equilibrium, it
merely has to

apply the law of value more efficiently.





This archive was generated by hypermail 2.1.5 : Wed Aug 02 2006 - 00:00:03 EDT