Computation and Complexity in Economic Behavior and Organization

Computation and Complexity in Economic Behavior and Organization

Computation and Complexity in Economic Behavior and Organization

Computation and Complexity in Economic Behavior and Organization

Synopsis

This book presents a model of computing and a measure of computational complexity which are intended to facilitate analysis of computations performed by people, machines, or a mixed system of people and machines. The model is designed to apply directly to models of economic theory, which typically involve continuous variables and smooth functions, without requiring analysis of approximations. The model permits analysis of the feasibility and complexity of the calculations required of economic agents in order for them to arrive at their decisions. The treatment contains applications of the model to game theory and economics, including comparison of the complexities of different solution concepts in certain bargaining games, and the trade-off between communication and computation in an example of an Edgeworth Box economy.

Excerpt

This book presents a model of computing, called the modular network model, and a measure of complexity, intended to apply to computations performed by a mixed system of people and machines. Applications of the model to problems in game theory and economics are also presented.

The model has two primitives: a set, usually denoted F of elementary functions or elementary operations, and a set of directed graphs. the modeler can choose the set of elementary operations to fit the problem at hand. It is assumed that an elementary operation is carried out in one unit of time. Every computation is described as a superposition of elementary operations. Choice of the set of elementary operations permits limitations on computing capabilities to be expressed formally. It also gives the modeler control over the level of reduction of analysis. the topology of the directed graph can also be restricted by the modeler, though in this book we do not do so; instead we assume that any directed graph is available.

These features facilitate the application of the model to human agents and to economic models. Parallel and distributed computing and the dispersion of information among agents are naturally expressed in this model. in each application the modeler can choose the set of elementary functions to suit the problem. the class of elementary operations may include functions of real variables, as well as functions whose domains are discrete sets, as, for instance, functions defined on strings from a finite alphabet. When the alphabet is finite and the elementary functions are Boolean, the model is equivalent to the finitestate automaton model.

Computing with real numbers offers some important advantages in the context of scientific computing (see Blum et al., 1998). It is also relevant to applications in economic theory. Economic models typically use real variables and functions of them. a model of computing in which the elementary operations are functions of real variables allows that model to be directly applied to . . .

Search by... Author
Show... All Results Primary Sources Peer-reviewed

Oops!

An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.