Computability and Algorithmic Complexity in Economics
Rabin’s effectivization of the Gale-Stewart Game (43) remains the model methodological contribution to the field for which Velupillai coined the name Computable Economics more than 20 years ago. Alain Lewis was the first to link Rabin’s work with Simon’s fertile concept of bounded rationality and interpret them in terms of Alan Turing’s work. Solomonoff (1964), one of the three – the other two being Kolmogorov and Chaitin – acknowledged pioneers of algorithmic complexity theory, had his starting point in one aspect of what73 came to call the Modern Theory of Induction, an aspect which had its origins in.24 Kolmogorov’s resurrection of von Mises (81) and the genesis of Kolmogorov complexity via computability theoretic foundations for a frequency theory of probability has given a new lease of life to finance theory (50). Rabin’s classic of computable economics stands in the long and distinguished tradition of game theory that goes back to Zermelo (85, Banach & Mazur (,6 Steinhaus (63) and Euwe (15).
This is an outline of the origins and development of the way computability theory and algorithmic complexity theory were incorporated into economic and finance theories. We try to place, in the context of the development of computable economics, some of the classics of the subject as well as those that have, from time to time, been credited with having contributed to the advancement of the field. Speculative thoughts on where the frontiers of computable economics are, and how to move towards them, conclude the paper. In a precise sense — both historically and analytically — it would not be an exaggeration to claim that both the origins of computable economics and its frontiers are defined by two classics, both by Banach and Mazur: that one page masterpiece by Banach and Mazur (6), built on the foundations of Turing’s own classic, and the unpublished Mazur conjecture of 1928, and its unpublished proof by Banach (39, ch. 6 &69, ch. 1, §.6). For the undisputed original classic of computable economics is Rabin’s effectivization of the Gale-Stewart game (43;17); the frontiers, as I see them, are defined by recursive analysis and constructive mathematics, underpinning computability over the computable and constructive reals and providing computable foundations for the economist’s Marshallian penchant for curve-sketching (10;20; and, in general, the contents of Theoretical Computer Science, Vol. 219, Issue 1-2). The former work has its roots in the Banach-Mazur game (cf.39, especially p. 30), at least in one reading of it; the latter in (6), as well as other, earlier, contributions, not least by Brouwer.
