Computation and Complexity in Economic Behavior and Organization

by Kenneth R. Mount , Stanley Reiter

• ISBN13: 9780521800563
• ISBN10: 0521800560
• Format: Hardcover
• Copyright: 2002-06-24
• Publisher: Cambridge University Press

Summary

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.

Table of Contents

Acknowledgments	ix
Introduction	1	(17)
The Modeling of Computing and Economic Agents	1	(6)
Complexity, Mathematics, and Human Capacities	7	(2)
Complexity and Computability	8	(1)
Computing and Economic Organization	9	(6)
Chapter Summaries	15	(3)
F Networks	18	(28)
Graphs and Trees	18	(28)
The Network Model	25	(16)
Conditional Branching	41	(1)
Symmetrical Computation	42	(4)
Networks of Real-Valued Functions	46	(27)
The Leontief Theorem	46	(11)
Necessary Conditions	48	(2)
An Example	50	(3)
Sufficient Conditions	53	(4)
Local Conditions	57	(8)
Computability in Excess Time	65	(8)
Applications to Economics	73	(22)
Computation with Human Agents	73	(6)
Example 1: Reading Handwriting	74	(3)
Example 2: Chernoff Faces	77	(2)
Decentralized Mechanisms	79	(4)
The Edgeworth Box Economy	83	(8)
Linear Coordinate Changes in the Message Space	89	(1)
Linear Coordinate Changes in Parameter Spaces	90	(1)
The Efficient Frontier	91	(4)
Applications to Games	95	(16)
Bargaining Games	95	(10)
Bargaining Games with Quadratic Boundaries	95	(2)
The Kalai-Smorodinsky Solution for Quadratic Boundaries	97	(2)
The Nash Solution for Quadratic Boundaries	99	(4)
Bargaining Games with Cubic Boundaries	103	(2)
Computational Power and Strategic Advantage	105	(6)
Lower Bounds and Approximations	111	(26)
Revelation Mechanisms	111	(17)
Constructions	117	(11)
Finite Approximations	128	(9)
Lattice Decomposition of Hn	128	(2)
A Limit Theorem	130	(7)
Organizations	137	(42)
Coordination Problems	137	(8)
Costs of Information Processing and Efficient Assignments	140	(5)
Two Examples	145	(17)
Example 1	145	(12)
Example 2	157	(5)
A Formal Model	162	(8)
Technology and Production	162	(2)
Efficient Production	164	(1)
Information, Communication, and Coordination	164	(6)
Structure of Organizations	170	(9)
Larger Organizations	170	(1)
Revised Cost Model	170	(1)
Example 3	171	(8)
A Appendix to Chapter 2: Graph Theory	179	(17)
B Appendix to Chapter 3: Real-Valued Functions	196	(29)
B.1 Uniqueness Results	197	(10)
B.1.1. An Example	202	(5)
B.2 Leontief's Theorem	207	(18)
B.2.1. An Example	209	(5)
B.2.2. Example of the General Leontief Theorem in a Low-Dimensional Case	214	(11)
C Appendix to Chapter 5: Application to Games	225	(4)
Bibliography	229	(6)
Index	235