Natalie Sandrine Glance
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
glance@xerox.fr
PhD thesis Physics Department Stanford University June 1993
The study of dynamics with expectations is relevant whenever the agents comprising a complex system, be they computational processes or biological entities, take into account possible future states when making decisions in the present. Two systems in particular are the subject of study of this thesis. The first, established under the rubric computational ecosystem by Huberman and Hogg (1988), consists of a loosely coupled collection of agents which compete among themselves for resources according to specialized strategies. Specifically, each agent chooses among different resources according to its perceived payoff for using each resource, which depends on the number of agents already using it. Expectations come into play if agents use past and present global behavior in estimating the expected future payoff for each resource. An extended dynamical formulation of computational ecosystems is necessary to understand the effect of these expectations on the global performance of the system.
A second context in which the effect of agents' expectations becomes important is the question of how spontaneous cooperation in a group can be achieved through individually rational decisions. This problem of collective action arises from the conflict between individual benefit and collective good (Olson 1965). Such dilemmas underlie many ongoing collective action problems, such as the functioning of large organizations (Bendor and Mookherjee 1987) and the mobilization of political movements (Hardin 1972, Oliver 1988). In a general social dilemma, a group attempts to obtain a common good in the absence of a central authority. Each agent has two choices: either to contribute to the common good, or to shirk and free ride on the work of others. The logic behind the decision to cooperate or not changes when the interaction is ongoing since future expected utility gains join present ones in influencing the rational individual's decision. This indicates the importance of including expectations in a dynamical description of ongoing collective action in a group of social agents.
Another aspect which comes to the forefront when studying the dynamics of collective action is the organizational structure of the group. This structure emerges from the pattern of interdependencies among agents. In a fluid structure, the pattern of interactions can vary widely over time, since the sum of small local changes in the structure of a group results in overall broad restructurings. If individual decisions to locally alter the structure depend on the perceived benefit as opposed to the actual benefit, then expectations once again play a role.
A dynamical model of collective action that includes expectations may then help answer the following questions: if agents make decisions on whether or not to cooperate on the basis of imperfect information about the group activity, and incorporate expectations on how their decision will affect other agents, can overall cooperation be sustained for long periods of time? Moreover, how do expectations, group size, and diversity affect cooperation? And lastly, which kinds of organizations are most able to sustain ongoing collective action, and how might such organizations evolve over time? These questions are relevant to both social science and to distributed artificial intelligence (Gasser and Huhns 1989), where instances of negotiation and cooperative problem solving imply the existence of intentional agents (Davis and Smith 1983, Zlotkin and Rosenschein 1991, Osawa and Tokoro 1991). In addition, the emergence of market-like computational systems that have no global controls (Malone et.al.1988, Waldspurger 1992) raises the issue of having computational processes that could free ride on the work of others (Miller and Drexler 1988a,b).
The format of the thesis proceeds as follows. In Chapter 2, I examine the behavior of computational ecosystems in a changing environment. The emphasis is on the dynamics of such a system and on how well agents without learning or predictive capabilities can track the changes in the environment through elementary decision rules. In Chapter 3, the agents' strategies are extended to take into account their expectations of how the system's behavior will evolve into the future. In order to separate the effects of a changing environment and agent expectations, the environment is taken to be fixed.
In the second part of the thesis, I turn to the problem of how ongoing collective action can arise and be sustained in groups of economic or computational agents. In Chapter 3, a dynamical model of collective action is developed and the possibilities for cooperative behavior are elucidated. In Chapter 4, I extend the model to allow for a diversity of beliefs among the agents and find how the dynamical regimes change. In Chapter 5, I examine the effect of ultrametric group structure on the dynamics of cooperation. Specifically, I study how the interplay between evolving group structure and levels of cooperation can yield new regimes of dynamical behavior.
Finally, in the appendix, I elaborate on one particular aspect of how
computer simulations are performed: the choice between synchronous
versus asynchronous updating of agent states. This argument was laid out
by my advisor, Bernardo Huberman, and myself in response to a paper by
May and Nowak (1992) in particular, and to a tendency in the theoretical
biology and artificial life communities to tacitly assume discrete
dynamics by performing synchronous simulations, in general.
postcript (5.3M)