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

From: Paul Cockshott (wpc@DCS.GLA.AC.UK)
Date: Mon Jul 31 2006 - 16:54:34 EDT


@book{hayek:1955,
        author={F. A. Hayek},
        title={{The Counter-Revolution of Science}},
        publisher={The Free Press},
        year={1955},
        address={New York}
}

-----Original Message-----
From: OPE-L [mailto:OPE-L@SUS.CSUCHICO.EDU] On Behalf Of Michael
Perelman
Sent: 31 July 2006 17:37
To: OPE-L@SUS.CSUCHICO.EDU
Subject: Re: [OPE-L] Neo-classical Equilibrium shown to be NP-hard

I am having trouble getting a handle on the references.  What is
Hayek:1955 p. 43?
My copy of The Counter-Revolution of Science has no note 37 on those
pages, one of
which is blank and the next one is the first page of chapter 12.


On Mon, Jul 31, 2006 at 09:43:22AM +0100, Paul Cockshott wrote:
> 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
> issue.
>
>
>
>
>
> 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
> mathematics?
>
>
>
> 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
> can
>
>       be determined : i.e., the equilibrium is in principle
computable,
>
>
>
> there is still the question of its computation tractability. What
> complexity
>
> 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
> NP-hard
>
> 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
> planning.
>
>
>
> 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.
>
>
>
>
>
>
>
>
>

--
Michael Perelman
Economics Department
California State University
Chico, CA 95929

Tel. 530-898-5321
E-Mail michael at ecst.csuchico.edu


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