Dealing with the Complexity of Economic Calculations

This essay is a response to a growing negative literature that suggests that most modern economic theories - including general equilibrium theory - are of limited practical relevance because they require an infeasibly large number of calculations. Many of the results are translations of abstract complexity bounds from the computer science literature. I argue that these bounds do not constitute proofs that difficult economic calculations are ?impossible? for several reasons. First, the complexity bounds are generally based on a worst case analysis, but it is not clear that worst case scenarios are relevant in practical situations. I argue that for many economic problems an average case analysis is more appropriate, and provide examples of problems where the average case complexity is far lower than worst case complexity. Second, complexity bounds only tell us the rate at which computational demands grow with the size or dimension of a problem: they generally cannot tell us whether or not a specific problem can be solved to a specified degree of accuracy with a given amount of computational resources. The economy may be solving a very difficult computational problem, but its collective computational resources are also very large: it can be viewed as a massively parallel processor whose individual processing elements are the millions of individual economic agents. Third, I conjecture that the economy has evolved very sophisticated ?software? for dealing with the complexity of economic calculations including decentralization, shared memory, and the ability to exploit special additive structure of the economy. I provide examples where a decentralized approach to the solving the problem of finding an efficient allocation of resources is computationally efficient relative to centralized approaches. Specifically, I show that the worst case computational complexity of the decentralized approach is bounded above by a function that increases linearly with the number of agents K in the economy whereas the worst case complexity of the centralized approach rises exponentially fast in K. I argue that decentralization also allows the economy to automatically exploit additive structure present in the economy so a similar ?computational constant returns to scale? property also holds for the total number of goods and services in the economy, d. This result suggests that the reason why large scale computable general equilibrium problems are difficult for economists to solve is that they are using the wrong hardware and software. Economists should design their computations to mimic the real economy, using massively parallel computers and decentralized algorithms that allow competitive equilibria to arise as ?emergent computations.? I conclude that the most promising way for economists to avoid the computational burdens associated with solving realistic large scale general equilibrium models is to adopt an ?agent-based? modeling strategy where equilibrium prices and quantities emerge endogenously from the decentralized interactions of agents