**From:** Paul Cockshott (*wpc@DCS.GLA.AC.UK*)

**Date:** Mon Jul 31 2006 - 16:54:34 EDT

**Previous message:**Michael Perelman: "Re: [OPE-L] Neo-classical Equilibrium shown to be NP-hard"**In reply to:**Michael Perelman: "Re: [OPE-L] Neo-classical Equilibrium shown to be NP-hard"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

@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

**Previous message:**Michael Perelman: "Re: [OPE-L] Neo-classical Equilibrium shown to be NP-hard"**In reply to:**Michael Perelman: "Re: [OPE-L] Neo-classical Equilibrium shown to be NP-hard"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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