Computability And The Local Theory Of Variation

The details of any social interaction will always be subject to some variation. Frequently, this stems from change that occurs in the external world, but variation may also be of a more subjective kind, arising due to changes in the players' knowledge of the game. It is often the case that agents have available to them only a local view of the process that governs change. For instance, a player's understanding of a particular situation might draw upon finite, or otherwise limited, experience and observation. This paper is concerned with how these two things, variation and limited observation, are relevant for the study of social phenomena. I start by examining one very concrete model of change that arises quite naturally when we consider the computability of optimal decisions or of equilibrium when consequences or payoffs are described using computable real numbers. It is then shown that basic considerations and results carry over to a number of other forms of variation and suggest general principles for an analysis of change. Some examples are used to develop this point further. A useful way to think about the logic of the results is by assuming that we observe only finite amounts of output from algorithms that describe a real number. There are no space or time constraints so that it is possible to generate as much output as one likes. When two numbers are different we will (eventually) confirm this, but no finite output can allow us to confirm that the numbers are equal. A second analogy is with a physical process of measurement say of some real-valued quantity. There is error in measurement so that we can only ever determine that the value lies in some open interval with rational end-points. The error can be made small, but is never eliminated. Upon taking several measurements it is possible to assert that the value lies in the intersection of the intervals. So long as we are restricted to finite intersections, it is not possible to determine the exact value of the quantity. As a third example, think of payoffs as continuous real-valued functions (varying, for instance, over time or states of knowledge). An assertion about payoffs, at some point t, is deemed true if it is true for every point in some neighborhood of t. Again, if two functions are not equal at some point there will be some neighborhood in which they are not equal for any point. As in the two previous examples, this is not always the case if the functions are equal at a point. The more general point that emerges here is that all of these models of variation share some common features with regard to the assertions that can be made about payoffs. What is more, the results we obtain about equilibrium are also essentially the same. For instance, in the model where payoffs and strategies are continuous real-valued functions the failure of computability of Nash equilibrium shows up as the failure of existence of equilibrium (here a profile of continuous real-valued functions).Finally, the idea that basic considerations and results from the analysis of computability carry over to a number of other forms of variation is developed formally. Each of the three examples presented above leads to a very precise mathematical model, and these are examined. The first two examples find their formalization in the context of frames and locales (Johnstone, 1982 and Vickers, 1989). Vickers develops the idea (due to Abramsky) that open sets are (finitely) observable properties and a topology represents a system of observation. A point (e.g. a real quantity) is what is being observed and is an infinitary sup-preserving lattice homomorphism. The third example, of variable quantities as continuous functions, is developed in the context of sheaves (Fourman and Hyland, 1979, and Mac Lane and Moerdijk, 1992). It is possible here to describe certain sheaves as the Dedekind real numbers and, in fact, these turn out to be the sheaf of continuous real-valued functions. Several examples from economics and game theory are used to illustrate general principles for the analysis of change. I point out where, and why, these diverge from the approach standard in the economics literature.