Center for Social Complexity
George Mason University
Fairfax, Virginia 22030 U.S.A.
Nicholas M. Gotts
Craigiebuckler, Aberdeen, Scotland
AB15 8QH, U.K.
November 7, 2002
Paper prepared for the “Model-2-Model” Workshop on Comparing Multi-Agent Based Simulation Models, Marseilles, France, March 31st-April 1st, 2003. Copyright © 2002 Claudio Cioffi-Revilla and Macaulay Institute. All Rights Reserved.
this paper we compare models of two different kinds of processes in
multi-agent-based social simulations (MABSS): military conflict within a
states-system (GeoSim), and land use and ownership change (FEARLUS). This is a
kind of model-to-model comparison which is novel within MABSS research,
although well-known within mathematics, physics and biology: comparing objects
(in this case MABSS) drawn from distinct research domains, in order to draw out
their structural similarities and differences. This can facilitate research in
both domains, by allowing the use of findings from each to illuminate the other.
Based on the similarities between FEARLUS and GeoSim, we conclude by
identifying a new class of MABS (multi-agent-based simulation) models based on territorial resource allocation processes
occurring on a 2-dimensional space (which we define as the “TRAP2” class). The existence of
the cross-domain TRAP2 class of models in turn suggests that MABS
researchers should look for other members of the class, sharing some of the
properties or dynamics common to the GeoSim and FEARLUS models compared in this
study: a systematic comparison of a set of related models from a range of
apparently distinct domains should generate insights into both MABS modeling,
and the domains concerned.
This paper compares multi-agent-based social simulations (MABSS) of two different kinds of processes. GeoSim (Cederman 2002; Cederman, and Cioffi-Revilla 2002) models military conflict within a states-system, while FEARLUS (Polhill, Gotts and Law 2001) models land use and land ownership change. The paper arose from the authors’ discovery that the two models, despite their apparently unrelated subject matter, had a surprising number of similarities. The comparison of entities or models drawn from distinct research domains, in order to draw out their structural similarities and hence allow findings from each domain to illuminate the other, is a standard research technique in mathematics and many areas of natural and social science (Bak 1997, Davis and Hersh 1980, Ember and Ember 2001; Landman 2000), but so far as we are aware, is novel within Multi-Agent Based Simulation (MABS) research. The similarities (and differences) between GeoSim and FEARLUS lead us to identify a new class of MABS models based on territorial resource allocation processes occurring on a 2-dimensional space (which we call the “TRAP2” class), and to seek further examples among existing models, and additional domains where the model class might be useful.
Comparisons between MABS models can be made at three main levels, which we will refer to as “structure”, “implementation”, and “context”. Comparisons at the level of implementation are the easiest to explain: they concern the computer software used in performing simulations - primarily the source code written by those presenting the model to the research community. Comparisons at the level of structure concern MABS models considered as abstract structures, defined verbally and/or mathematically: two models implemented in different high-level languages, or using different programming constructs in the same language, may embody the same or similar abstract structure. Conversely, a given piece of software may be conceptualized as the implementation of a range of different abstract structures, as explained below. Comparisons at the level of context refer to the interpretations given to the model’s abstract structure – the real-world entities and relationships its elements are intended to represent – and the uses made of the models in research, or in other types of application such as generating policy advice (Bankes 2002) or facilitating participatory planning (Downing 2002). Our concerns here are primarily in structural and contextual comparison, and within the latter, in the interpretations given to models, and how they are used in research.
There is no uniquely correct way to describe the structure of a MABS model, but there are two related approaches which we find particularly useful here. First, a MABS model (or any other kind of discrete-event computational model) can be regarded as a homogeneous Markov chain (denoted simply as Markov chain hereafter) (Grimmett and Stirzaker1992, pp.194-5), provided it has a countable number of distinct possible states, and fixed (stationary) transition probabilities between pairs of states. A Markov chain can be represented by a directed graph with labeled arcs, in which vertices of the graph represent states of the model, arcs represent possible transitions between states, and the arc-labels indicate the exact probability of each possible transition. The state of a model at time t contains, by definition of a Markov chain, all the information necessary to specify the probabilities of each possible state at time t+1. Second, a MABS model may be thought of in terms of the types of objects (e.g. agents, and parts of the environment) it consists of,
the numbers of each type, their properties and relations, and a schedule of events which can change the inventory of objects, and/or their properties and relations.
We can clarify both these approaches by describing how they are related to each other. When a MABS model is described in the literature, the description will generally mention a number of parameters, different values of which produce variants of the model. For example, both FEARLUS and GeoSim, along with many other spatially explicit simulation models, have parameters specifying how many “cells” (minimal spatial units) they contain, and which of these share boundaries. Suppose all the parameters necessary to run such a model are specified. The resulting fully parameterized model will uniquely specify the probabilities of starting in each possible initial state (the initial state is the state from which the run starts), and the probabilities of all the possible transitions between states. (If the initial state and transition probabilities have not been so specified, then the supposed “fully parameterized model” cannot be described as a Markov chain, and, as terminology is used here, it has not yet been fully parameterized.) A MABS model as described in the literature can therefore be identified with a (possibly infinite) set of Markov chains, one for each permitted set of parameters.
One way to specify such a set is to describe the permitted sets of states and transitions, in terms of the kind of object-level description outlined above. A state of a fully parameterized model is then analyzed into the set of model objects existing in that state, their current properties, and their relations with each other. A transition between states is defined in terms of the objects coming into existence and ceasing to exist, and changes in the properties and relations of objects that survive the transition. (It should be noted that two different object-level descriptions could turn out to define isomorphic sets of Markov chains.)
In the next two sections, we describe FEARLUS and GeoSim in object-level terms. These descriptions are intended to provide a general understanding of the computational processes involved in each simulation model, at a level sufficient to carrying out our comparative analysis. More detailed descriptions, beyond the level of detail required here, are published elsewhere (Cederman 2002; Polhill 2002).
FEARLUS is a Swarm-based simulation (Swarm 2002). The current version (FEARLUS-0.6.2) is an abstract model of land use and land ownership. Land uses, biophysical properties of land parcels, and climatic and economic conditions, are all represented as bitstrings, with simple matching operations used to determine the economic return from a given land use at a particular time and place. The main focus of research using FEARLUS so far has been the relative success of different approaches by the model’s land managing agents to land use selection (e.g. imitative versus non-imitative approaches) in different kinds of environment (Polhill et al 2001, Gotts, Polhill and Law 2002). The conviction underlying this work is that land managers do not (and indeed, cannot) act like the instrumentally rational agents of neoclassical economics: they do not have the unlimited computational capacity this requires, and their decisions are profoundly affected by social and cultural factors, particularly their interactions with other land managers. A secondary research theme has been the precautions necessary to avoid artifacts due to model structure influencing outcomes in agent-based social simulation studies (Polhill, Gotts and Law 2002a).
The objects in a FEARLUS model at the start of a simulation run include:
· A Grid of Land Parcels.
· The Grid may consist of Squares, equilateral Triangles, or equilateral Hexagons. Any Parcel edge is either shared between exactly two Parcels, or (if the Parcel is at a free edge of the Grid – see below) belongs to a single Parcel. The Grid is rectangular in shape, consisting of xy Parcels (x and y integers). Each Parcel can be identified by its X and Y coordinates.
· A Neighbor Relation is defined on the Parcels. This specifies which pairs of Parcels are considered Physical Neighbors. A range of possible Neighbor Relations has been implemented, all but one of them based on the X and Y coordinates. This can be described in terms of three parameters:
· Topology. This may be Toroidal, Cylindrical, or Planar. In the Toroidal Topology, the “North” edge of the Grid is considered joined to the “South” edge, and the “East” edge to the “West”, so that all cells have isomorphic Neighborhoods. In the Cylindrical Topology just one pair of edges is joined, and in the Planar Topology, neither.
· Neighborhood Function. This specifies a Basic Neighborhood for each Parcel. For hexagonal or triangular Grids, this consists of those Parcels which share one of the given Parcel’s edges. For a Grid of Squares, the same may be true (von Neumann Neighborhood Function), or a Parcel’s Basic Neighborhood may be those sharing an edge or corner with it (Moore Neighborhood Function). For the Global Neighborhood Function, the Basic Neighborhood of each Parcel includes all others, making the Topology parameter irrelevant, and producing effectively non-spatial models.
· Neighborhood Radius. For all Neighborhood Functions except the Global, the Neighbor Relation can also be adjusted using the Neighborhood Radius, an integer, r. For the von Neumann Neighborhood Function, the Physical Neighbors of a Parcel are those no more than r squares directly to its North, South, East or West (so the neighborhood forms an orthogonal cross). For all other Neighborhood Functions, r specifies the maximum number of steps that can be taken from a Parcel to one of its Basic Neighbors, without risk of leaving the Physical Neighborhood of the starting point. So for a Moore Neighborhood Function and a Neighborhood Radius of 3, for example, the Physical Neighborhood of a given Parcel is a 7 by 7 square centered on that Parcel.
· Each Land Parcel has a set of Biophysical Properties, encoded as a bitstring and fixed for the duration of a simulation run; the length of these bitstrings is a model parameter, the same for all Land Parcels. They are used in investigating how the type and degree of the Environment’s spatial heterogeneity affects the model’s dynamics.
· The Global Environment. This consists of the following:
· The External Conditions. Another bitstring (the length of which is again a model parameter), representing a combination of climatic and economic conditions. The External Conditions may change from one Year to the next. Thus the Properties of Parcels vary across space but not time, the External Conditions over time but not space.
· Two numerical parameters which do not vary over space or time: the Break Even Threshold (BET), which specifies how much economic return or Yield must be gained from a Land Parcel to break even, and the Land Parcel Price (LPP).
· A set of Land Uses. Each Land Use is defined by a bitstring, the length of which is the sum of the length of the Biophysical Properties and External Conditions bitstrings.
· A set of Land Managers (considered as representing households or firms, not individuals). Each Land Manager has an Account, initially having the value 0, and a Land Use Selection Algorithm, described below. Each Land Manager is assigned an m by n block of Land Parcels (m divides x, n divides y). There are thus xy/mn Land Managers in the initial state of the model.
· One or more Subpopulations. A Subpopulation is a generator of Land Managers, and is considered to represent a type of Land Manager (for example, family farm households, or “agribusiness” companies). When a Land Manager is created, it is assigned at random to a Subpopulation, according to a probability distribution which is a model parameter. Each Subpopulation in turn has an associated probability distribution of Land Use Selection Algorithms, used to assign such an Algorithm to a newly created Land Manager.
Considered at the implementation level, a run of a fully parameterized FEARLUS model begins with a setup phase, Year Zero, in which Land Parcels are assigned to Land Managers, and there is a random allocation of Land Uses to Land Parcels. The Yield from a Land Parcel is calculated as described below, but in Year Zero does not affect its Land Manager’s Account: it is used solely as input to subsequent Land Manager decisions. At the level of abstract model structure, Year Zero can be seen as implementing the stochastic selection of an initial model state.
From this initial state, the run repeats the following main loop, or Annual Cycle, either a preset number of times, or until interrupted:
· Agent decision-making. The Land Use for each Land Parcel is selected by its Land Manager, using the latter's Land Use Selection Algorithm.
· Calculation of outcomes.
· Calculation of External Conditions. Bitstrings for any number of Years may be stored in a file (to allow runs with identical External Conditions to be compared), but otherwise the initial bitstring is determined randomly, and each subsequent bitstring is produced from its predecessor by applying a stochastic process to each bit independently. This process uses a parameter called the Flip Probability, f. This specifies how likely each bit is to change. If f=0 the intial bitstring will be retained throughout; if f=1/2, each Year's bitstring is independent of its predecessors and the External conditions are temporally uncorrelated. If 0 < f < 1/2, the External Conditions change, but are temporally auto-correlated.
· Calculation of Yields. A Land Parcel’s Yield is determined by comparing the concatenated bitstrings for the Parcel's Properties and the current External Conditions, with the bitstring of the current Land Use, and counting the matches
· Harvest. The Account of each Land Manager is adjusted. For each Land Parcel owned, the Yield for that Parcel is added, and the BET subtracted.
· Transfer of territory from less to more successful agents.
· Selection of Land Parcels for sale. Each Land Manager whose Account is in deficit puts up for sale (at the LPP) as many of their worst-performing Land Parcels as necessary to clear the deficit, choosing at random among Parcels performing equally badly.
· Retirement of insolvent Land Managers. A Land Manager unable to clear their debt while retaining at least one Parcel, leaves the simulation.
· Sale of Land Parcels. The selected Land Parcels are sold in random order. One ticket in a lottery is issued for each Physical Neighbor of the Parcel which belongs to a Land Manager with at least the LPP in their Account (so Land Managers owning multiple Physical Neighbors get multiple tickets), and one is left unassigned. A Land Manager must buy the Land Parcel (having the LPP deducted from their Account) if selected. If the unassigned ticket wins the lottery, the Parcel is given to a new Land Manager. This Land Manager starts with an Account of 0 after buying the Land Parcel.
When a Land Manager is created, either in Year Zero or later, its Land Use Selection Algorithm is assigned. This is a collection of three Strategies, along with conditions for their use. The Contentment Strategy is used when the Yield in the previous Year equaled or exceeded the Land Manager’s Aspiration Threshold; if this was not met, the Land Manager decides whether to use its Imitative Strategy or its non-Imitative Strategy according to its Imitation Probability.
The Contentment Strategy is to maintain the same Land Use as before. The non-Imitative Strategy may rely on the Land Parcel’s Biophysical Properties alone, or on some combination of these with the External Conditions of recent Years. The Imitative Strategy makes use of information about recent Land Uses and Yields from the Social Neighborhood: the Land Manager’s own Land Parcels, and those belonging to Land Managers who own at least one Physical Neighbor of any of these Parcels. Each Land Manager has a Memory Length, specifying from how far back in time they can use information. See Polhill (2002) for further details of the parameters that can be assigned to Subpopulations to specify the probability distributions of Land Use Selection Algorithms assigned to their members.
Most of the experiments undertaken with FEARLUS so far have tested the relative success of different Land Use Selection Algorithms in Environments differing in size, shape or Neighborhood Function (Polhill et al 2002a), spatial and/or temporal heterogeneity (Polhill et al 2001, Gotts et al 2002), or Break Even Threshold (Gotts et al 2002). This has been done by assigning Land Managers with equal probability to one of two Subpopulations, with all members of each Subpopulation being given the same Land Use Selection Algorithm.
GeoSim is a RePast-based simulation (RePast 2002), following an earlier tradition of simulation models developed by political scientists investigating international relations and world politics (Bremer & Mihalka 1977; Cusack & Stoll 1990). The current version of GeoSim (Cederman 2002) is a model of an inter-state or world system where sovereign countries (nation-states) are composed of capitals and provinces and interactions determine the rise and fall of territorial agents. Several research questions have been investigated thus far using GeoSim, such as the evolution of nationalism, the effects of technology, and the replication of power laws of war (Cederman 2002; Cederman and Cioffi-Revilla 2002). The basic computational framework of GeoSim is that countries have resources which they then use for defensive and offensive purposes in a system of evolving sovereign states. Over time, some states thrive and expand, while others collapse and fragment or are conquered.
The objects in a GeoSim model at the start of a simulation run include:
· A Grid of Territorial Actors
· The Grid consists of a square array or lattice of Squares or “primitive units”. These initial squares become the building blocks of territorial states.
· As the simulation evolves, each state (initially consisting of a single square cell, similar to a city-state) forms as a set of contiguous squares, or composite actor, one of which represents the capital of the state and the others provinces (no longer a city-state, but a territorial state). Initially there are many states with a single province (primitive actors or city-states) and as the simulation evolves there are fewer states with more provinces (composite actors).
· Actors have three types of relations (graphs): local territorial relations (between von Neumann adjacent units), interstate relations (between states), and hierarchical relations (between capital and provinces). In principle, other relations can also be defined.
· The Neighborhood Radius varies by type of relation. For local territorial relations and for interstate relations the radius is one, since only adjacent units (territorial) or adjacent states (interstate) interact. The radius for hierarchical relations is given by the distance between the capital and the farthest province (usually < 20).
· At any given time each province-unit has an associated amount of resources, and each composite actor (state) taxes each province in relation to distance from the capital.
At the implementation level, the main simulation loop consists of five stages:
· Resource updating
· During the first stage the resource level of each unit is updated by having the capital extract resources from however many provinces it controls. Resources are extracted in logistically inverse proportion to distance from the capital.
· This computation also includes a technological effect, which allows a capital to extract at a greater distance as the simulation evolves, as well as gains or losses produced by the result of frontier wars (see interaction stage below).
· Resource allocation
· At the next stage each country (state) allocates resources to each component province. The allocation is governed by two mechanisms. First, there is an even share of resources distributed to provinces. In addition, another share is allocated to provinces at war (“fronts”), for both defensive and deterrent purposes. Cederman (2002) provides examples of resource allocations.
· Resource allocations are executed in parallel with double-buffering and randomized order of execution.
· Each state then decides what to do next, depending on its state of alert and on the balance of power (resource ratios) at each front. Unprovoked attacks occur only with a low probability (0.01) when the state of alert is low for a given country
· The probability of an agent province attacking a target province belonging to an adversary country is a logistic function of the ratio of resources between the neighboring provinces.
· The decision-making stage is also executed in parallel with double-buffering and randomized order of execution.
· Following the decision-making stage, the model then executes all actions and computes the outcomes probabilistically, based on resource ratios. For example, the probability of victory is computed as logistically proportional to a favorable resource ratio, and approaches 1.0 as the ratio approaches 3:1—a common rule of combat.
· As a result, a country will have provinces with battles either won, lost, or in stalemate (battles continue in the next round). The first two outcomes set the stage for what happens next.
· Structural change
· Finally, as a result of warfare, territorial changes occur: each country may win or lose one or more provinces, or fighting may continue in one or more provinces.
· Note that, unlike earlier models (e.g., Cusack and Stoll 1990), structural change in GeoSim affects only one primitive unit (province) at a time.
After structural change has occurred a new geopolitical landscape obtains and the process cycles back to the stage of resource updating with new and old territories, as determined by the previous cycle.
It should be emphasized that the three sets of relations defined earlier (territorial or province-level, relational or country-level, and hierarchical or intra-actor level) are key to understanding the main simulation loop, the long-term dynamics, and how this system of territorial agents evolves. In particular, decision-making is centralized at the country level (relational interactions), as in the real world of interstate relations, but battles are won or lost at specific unit sites or frontier provinces (territorial relations). Thus, countries grow and decline in non-trivial and complex ways that are entirely unpredictable when judging from the simple computations that take place at each stage.
This section attempts to identify the most important similarities, and differences, between GeoSim and FEARLUS. The section begins at the “context” level: the interpretation given to the objects and events in the models, and the use made of them in research. Here, there are both important similarities, and major differences. When we turn to structural comparisons, we find far-reaching and, we believe, highly significant similarities in the overall structure of the two models. As we progress through more detailed aspects of model structure, we find more of a mixture of similarities and differences; at some points, we note topics for future investigation. The section concludes with a subsection on similarities and differences at the level of implementation.
Similar worlds. Both models concern situations in which agents with unlimited potential lifespan but liable to ‘die’ (be they households or firms in control of farms or estates, or governing regimes in control of independent polities), exercise exclusive control over parts of a two-dimensional space, make decisions about the allocation of resources, and interact with their neighbors in ways which include transfer of territorial control from the less successful to the more successful agents. Such ‘worlds’ are also similarly ‘anarchic’, in the sense that each consists of autonomous and autarkic agents that lack any sort of supra-agent system of government (or ‘leviathan’ in a Hobbesian sense). Of course, households or firms owning farms or estates are in general subject to government authority, but in respect of the actions which are the subject of FEARLUS, their choice of land use, they are in general free to make choices independent of such authorities, and of their peers. Such an initial similarity immediately raises issues regarding social dilemmas and conflict resolution (Gotts, Polhill and Law, in press).
Spatial and Organizational Scale. However, while both models deal with the interaction between collective human agents controlling and using parts of the Earth’s surface, the scale of the phenomena modelled is very different. In FEARLUS, the agents are households or firms; in GeoSim, they are states, or their governing elites. In FEARLUS, the research intent is to gain a better understanding of land use dynamics on a local or regional geographic scale, such as a county, province, or perhaps a small to medium size country, given the total number of parcels; in GeoSim the intent is to examine an entire ‘world system’, not necessarily a particular region, since the number of cells is intentionally aimed to be somewhere in the 100-300 range, similar to the total number of autonomous polities (countries) in the modern international system.
Timescales. FEARLUS has an explicitly calibrated timescale: each cycle of the simulation represents a year; GeoSim is not explicit in this regard, although the approximate range appears to be around 1-3 years, perhaps towards the lower end (tax collection, military planning, seasonal battle factors, and so on). However, further research is necessary in order to calibrate the GeoSim timescale (Cioffi-Revilla 2002).
Military versus Economic Competition. In the GeoSim domain of interpretation, agents wrest territory from their neighbors by force; in the FEARLUS domain, they merely acquire their neighbors’ territories following economic failure. Of course, in the real world this distinction has cloudy edges: a state may collapse due to economic failure, and then be divided among its neighbors, while farmers may, in some times and places, force their neighbors off their land by violence; but these aspects of the world are not modelled in GeoSim and FEARLUS.
Research intent. Research in GeoSim has concentrated on the overall pattern of events occurring, and features of their statistical distributions (e.g., the power laws that appear to govern the “size of wars”, Cederman 2002; Cederman & Cioffi-Revilla 2002); research in FEARLUS, has focused instead on the comparative success of different agent strategies under different sets of parameters, and work on different ways of dividing up space and defining neighborhood (Polhill, Gotts & Law 2001, 2002). As a consequence, FEARLUS allows for heterogeneity of agent strategies, while GeoSim presently does not. Another consequence is the difference in experimental methodology: simulation work in FEARLUS has concentrated on finding statistically significant differences between the results of contests between Subpopulations of agents in different environments; GeoSim has concentrated on the emergent statistical features of distributions of events of different sizes within simulations.
Validation. At present, GeoSim has a closer relation to a coherent body of empirical evidence (Cioffi-Revilla 1998, Cederman 2002; Cederman and Cioffi-Revilla 2002) than FEARLUS. This is at least in part related to pre-existing differences in the quality of data available: international politics and warfare are better documented and studied than regional changes in land use and ownership: for GeoSim, there was a coherent body of data about the size of wars requiring explanation. All the same, numerous other aspects of GeoSim require further validation (Cioffi-Revilla 2002: 1714-1716).
Agents and Territory. In both FEARLUS and GeoSim, agents with unlimited potential lifespan compete for the control of territory, which is divided into a regular grid of indivisible “cells” (FEARLUS “Parcels”, GeoSim initial units or provinces). In both, all agents start off controlling the same amount of territory (although this may be more than a single cell in FEARLUS), and territorial expansion depends on being more successful in decision-making than your neighbors. Again, neither model puts any limit on the amount of territory one agent can acquire.
Main loops. Both models have a “main loop” (see sections 2 and 3 above) that can be parsed into three main computational phases: (1) decision-making by the agents, (2) calculation of outcomes (calculation of Yields in FEARLUS, interaction resulting in victories or defeats in GeoSim), and (3) transfer of territory from the less to the more successful agents. The GeoSim loop was described in five stages, but these can be parsed into three for comparative purposes (the “Resource allocation” phase can be subsumed into an expanded “Decision-making” phase, and the “Resource updating” phase considered a piece of book-keeping after the “Interaction” and “Structural Change” phases). The roughly parallel stages in the two loops are a key element, along with other important grid and landscape features, in the class of models that we discuss below.
Synchronous actions by agents. In both models, all agents act synchronously, in the sense that they all act without knowing the decisions of their peers, although at some points in both models, the interacting effects of different agents’ actions are dealt with by sequentializing those actions, using a randomized order of execution.
Dual neighborhoods. Both models also have a dual conception of neighborhood: physical neighborhood between cells, and social or political neighborhood between agents, derived from the physical neighborhood relations of cells but distinct from it, (i.e., the relations between farms in FEARLUS or polities in GeoSim). This means that both models depart from the general cellular automaton rule of fixed neighborhood, so it is not, even in principle, possible to translate them into standard cellular automaton (CA) models (Gotts, Polhill and Law 2001). The CA-level processes that arguably take place (between Parcels in FEARLUS and between provinces in GeoSim) are completely dominated by the higher-order process between the main agents where decision-making resides (farms and polities, respectively).
Spatio-temporal hierarchies. The preceding feature—dual neighborhoods— produces a three-level spatial hierarchy (parcels/provinces, farms/polities, world) as another fundamental similarity. In turn, the existence of a spatial hierarchy automatically raises questions such as (i) the distribution of cells across farms/polities at any given time; (ii) the distribution of the frequency with which different unit cells change “owners” over time, and (iii) similar diachronic questions regarding the evolution of system composition and distribution over time. There is also a parallel three-level temporal hierarchy: basic time-step, agent lifespan, run-length (although in GeoSim the longest agent lifespan is necessarily equal to the run-length). Both hierarchies provide fundamental organization to the spatio-temporal structure of these models, and also suggest numerous potentially insightful analyses that are yet to be undertaken (e.g., hazard rate models of intensity and duration variables; Cioffi-Revilla 1998).
Competition. In GeoSim the competition between neighbors is direct, and essentially zero-sum, given the territorial nature of competition; in FEARLUS, agents are primarily ‘playing’ against external forces, and merely get the opportunity to extend their territory when their neighbors fail. This micro-level difference reflects the difference between the interpretations given to the models and specifically, the different circumstances in which territories are transferred between states and farms; it may or may not affect some macroscopic patterns, such as power law distributions and other large-scale outcomes (see 4.7).
Regular Two-Dimensional Grids. Both models are based on a two-dimensional territorial space composed of a regular grid of identical cells. GeoSim uses a grid of squares, with a toroidal topology and an initial interaction network governed by a von Neumann neighborhood with radius 1. For FEARLUS, this is one among a range of possibilities: most work has used a grid of squares with a toroidal topology, but with an initial interaction network governed by a Moore neighborhood with radius 1. Clearly, detailed outcome comparisons between FEARLUS and GeoSim could be made using a GeoSim-type grid; conversely, there is nothing to prevent GeoSim running with at least some of the alternative types of grid FEARLUS uses. For example, hexagonal unit cells are arguably more appropriate for representing political units, since the average number of real world frontiers is closer to six than it is to four, and military planners also use hexagonal grids (Cioffi-Revilla 2002: 1714-1716; Richardson 1961). Since so many MABSS use regular two-dimensional grids (often with toroidal topology) we are inclined to omit this feature as uniquely distinctive of the TRAP2 class as such, although it clearly remains a shared feature of FEARLUS and GeoSim.
World economies. In GeoSim, the total resources available for use in acquiring new territory are fixed, and are transferred along with the territory; in FEARLUS, resources are generated (or lost) in each cycle. This difference implies that the “world economy” of the two models differs substantially, since it is stationary in GeoSim (albeit not in distribution!) but fluctuating in FEARLUS. Thus, FEARLUS seems rather more realistic in this regard.
Physical environments. In GeoSim, the physical environment external to the agents is spatio-temporally homogeneous; in FEARLUS, it can (but need not) vary over space and time. Again, clearly FEARLUS is (or can be) less stylized with respect to physical environments, at least in the models that have been implemented thus far. GeoSim and other Repast models may soon implement greater realism in their physical environment (Padgett et al. 2002).
Unidirectional causation. In both FEARLUS and GeoSim, the external environment is immune to influence from the agents: they cannot change any of its properties. In both models, the external environment can change over time, but this change is exogenous: in FEARLUS, the External Conditions, representing climatic and economic factors, can (and generally do) change, while in GeoSim, there is the “technological effect” which allows extraction of revenues at greater distances from the capital as time goes on.
Economic starting point. In FEARLUS, all agents start out with equal wealth, while a subset of GeoSim agents are given extra resources at the start of a run. Conversely, however, the spatial heterogeneity of (most) FEARLUS models means that some cells are more valuable than others, while all GeoSim cells produce equal resources.
Decision-making centrality. In GeoSim one cell of an agent’s territory (set of cellular unit provinces) is where the ‘capital’ of the country is located; FEARLUS has no equivalent. Thus, in political terms, decision-making authority is explicitly centralized in GeoSim (as it occurs with real countries in the international system). Political authority is not decentralised in FEARLUS – the Land Manager makes decisions for all the Land Parcels (cells) owned. However, the lack of a capital means that a farm could, over the Years, wander freely around the map. Functionally, depending on the parameters used, it is possible for there to be cells which an agent cannot lose – but this is another significant difference between the two models. Specifically, this can happen if the Land Manager’s algorithm guarantees a positive net return (Yield minus Break-Even Threshold) on a particular Parcel, and the Land Parcel Price is high enough to ensure that losses made elsewhere can be made up by selling off lower-yielding Parcels, see Gotts et al (2001).
As computational objects, agents in both simulations (be they Land Managers or regimes) posses a similar set of attributes and methods (functionality), such as decision-making capacity, resource inventory, territory, and agent territorial and relational connectivity.
Agent Individuality. In any given fully parameterized model, however, FEARLUS agents may (and generally do) have different decision-making algorithms, while GeoSim agents all use the same algorithm.
Memory: FEARLUS agents can in principle base their decisions on indefinitely distant past events (although this capability has not been used in any published work), while GeoSim agents consider only the present state of the world. For any given FEARLUS agent and any fully parameterized FEARLUS model, however, there is a limit on memory length.
Learning: Neither FEARLUS nor GeoSim agents learn in the sense of changing their decision-making strategies. (Strictly, there is provision for a very minor form of strategy change in FEARLUS, but it is a legacy of earlier versions, never used in published work.)
Imitation. FEARLUS agents can imitate each other, while GeoSim agents do not do so.
Public information about agents. Some of the information about agents (notably, the territory they control and the allocation of resources within that territory i.e. the distribution of forces among frontiers in GeoSim, the Land Uses employed in FEARLUS), is public, that is, available to other agents. This has implications for the implementation of the models in simulation tools such as Swarm and Repast, which are based on the object-oriented programming paradigm. Polhill, Gotts and Law (2002) suggest that this model feature may call for some modification to that paradigm.
Information environment. Both models are also similar in terms of their heterogenous information environment. That is, agents in both models are “surrounded” by information on other agents’ resources, location, costs, and other data that is not homogenously distributed across the landscape. Again, further implications of this similarity remain unexplored and therefore unknown at this time.
Myopia. Another similarity is that agents in both models are “myopic”, in the sense that they worry only about the next move and are unaffected by any “shadow of the future”. Myopic behavior is known to produce cumulative behavior and overall results that can be fundamentally different from non-myopic, strategic behavior guided by backward induction or other heuristic.
Choices and Lotteries. Since each phase of the main loop is arguably an event, based on finite event analysis (Cioffi-Revilla 1998: chs. 5–7), the loop can be modeled as a branching process, where nodes may be either choices (producing decisional acts) or lotteries (producing states of Nature). Generally, therefore, in our three-stage parsed process phase 1 is a choice (producing acts), while phases 2 and 3 are lotteries (producing material results and territorial transfers, respectively, as states of Nature). Clearly, the role of human agency is therefore not uniformly distributed throughout the loop, but rather is intermittent. Finite event analysis can uncover and highlight other features, based on a more elementary decomposition of events (e.g., decision-making). The formalization of the branching process implemented in each model makes it possible to compare the two microscopic loop mechanisms in some detail, with possible insights for understanding the emergent macroscopic dynamics.
(In)finiteness. One considerable difference between the two models considered as Markov chains or state-transition networks is that a fully parameterized FEARLUS model has (in general) an infinite state-transition network, while all GeoSim models have a finite one. This is a consequence of the fact that FEARLUS agents can accumulate unlimited “wealth” in their Accounts, which have no parallel in GeoSim. There are special cases of FEARLUS models with finite state-transition networks: the simplest occurs when all Land Uses on all Land Parcels give a Yield exactly equal to the Break-Even Threshold, so no Land Manager’s Account ever contains a non-zero amount.
Sinks. The GeoSim state-transition network has sinks: proper parts of the state-transition network which can be entered from outside, but from which there is no exit. Specifically, once a single agent has gained control of the entire world, it will never lose it, and could only go through the motions of collecting resources and allocating them to (non-existent) fronts. In general, FEARLUS does not have sinks, although there are special cases in which they exist. For example, if all Land Uses give Yields greater than the Break-Even Threshold in all circumstances, all agents will get richer every Year, and hence the model will enter a new sink, within the one it entered the previous Year. Even if this is not the case, particular Managers can gain permanent control of particular Parcels, as already noted.
Further network properties. We can consider further properties of the state-transition network such as connectedness, centralization, diameter, fractal dimension, entropy, and network uncertainty, It should be noted that, although these are attributes in a computational object sense, they may not all be implemented as such. Nonetheless, these attributes should be investigated further.
Territorial configurations and changes. At a higher structural level, we can characterise the state of a fully parameterized model at the end of each cycle simply in terms of the division of the grid into territories, and (in the case of GeoSim) of the capitals. Considered at this level, both GeoSim and FEARLUS have a finite set of possible territorial configurations, and for grids of the same size, GeoSim’s set may be larger, since for a given division into territories, there are generally multiple distributions of capitals in GeoSim. Offsetting this, however, is the fact that a FEARLUS territory need not be a single connected piece, while a GeoSim territory must be (indeed, it must be “line connected” in the sense of Gotts (2000), that is, not divisible into two parts sharing only isolated boundary points). A cell newly added to a FEARLUS territory will always be a physical neighbor of a cell that is already a member, however.
Another difference at this level is that GeoSim agents can both gain and lose cells in the same cycle, while FEARLUS agents cannot.
Demographics. As a corollary of these life-and-death dynamics over ‘time’ (cycles), both models are capable of generating ‘life tables’ or ‘survival’ data pertaining to the evolution (births and deaths) of agents, be they land managers or regimes. From such raw data it is possible to calculate a set of statistics (e.g., moments) and probability functions (e.g. survival functions, hazard rate functions, and other functions based on classical cumulative density functions and probability density functions) for agent populations. Very little of this work has actually been done, although the methodology is well-known and can be readily applied (Cioffi-Revilla 1998).
Power laws? Power law analysis offers an important and so far underutilized means for assessing issues of validity, universality and calibration in MABSS (Cioffi-Revilla 2002). Visual inspection of both models suggests that perhaps some variables (e.g., size of territorial units; size of changes, etc.) may obey power laws of the form ƒ(x) ~ x–f, where x is the size variable and f is the fractal exponent or dimension. Cederman (2002) and Cederman and Cioffi-Revilla (2002) report some preliminary power law results for the occurrence of warfare in GeoSim. It is reasonable to conjecture that, given the other similarities, FEARLUS may also yield power laws.
Simulation software. FEARLUS and GeoSim are based on similar simulation tools—Swarm and RePast, respectively. RePast was developed as an improvement on Swarm. Indeed, RePast borrows much from the Swarm simulation toolkit and can properly be termed “Swarm-like.” In addition, RePast includes such features as run-time model manipulation via GUI widgets first found in the Ascape simulation toolkit’ (RePast 2002).
Formal social science models can be classified in innumerable ways: the common ground between GeoSim and FEARLUS is sufficient to make it useful to define a class to which they both belong, for which it may be possible to arrive at useful analytical results (say, in terms of a structured set of possible regimes of behaviour the models could show), and define common approaches to areas such as sensitivity analysis, study of simplified cases (such as what happens if transfers of territory are made using simple lotteries instead of strategic interactions), avoidance of artifacts, and searches for parameter settings which give particular outcomes.
We define TRAP2 models as having the following minimal characteristics:
1. An exclusive relationship linking each agent to the territory it controls at any one time (i.e., any piece of territory has just one owner at a time).
2. No agent movement or location within the territory held.
3. A mechanism for the transfer of territory between agents – specifically, from less successful to more successful agents. (Agents may or may not be assigned a core territory with which they have an indissoluble connection: GeoSim distinguishes one cell as the agent’s ‘capital’, while FEARLUS makes no such provision.)
4. A decision-making process in which each agent determines how the territorially-linked resources it currently controls are to be used to advance the agent’s interests.
5. Agents with unlimited potential lifespan but the possibility of ‘death’.
6. Synchronous action by the agents.
7. A fixed configuration of ‘atomic’ two-dimensional regions (cells), the minimal bits of territory transferred between agents. (Of course, the real world doesn’t have such a structure, so this is a significant idealisation.) The cells may, but need not, form a regular lattice. Each cell has a set of boundary edges, ending in vertices: each edge either belongs to a single cell, or is shared between exactly two cells.
8. A symmetric physical neighborhood relation defined on the cells. The cell configuration is connected in terms of this neighborhood: that is, there is a path from any cell to any other, in which each adjacent pair of cells are physical neighbors according to the definition of the physical neighborhood relation.
9. A many-to-one relation linking cells and agents, arising necessarily from points 1, 3, 7 and 8.
10. Arising from this many-to-one relation between cells and agents, two distinct but related levels of neighborhood: between cells (fixed throughout a model run), and between the territories owned or controlled by agents (varying over simulated time).
11. An indefinitely repeated cycle of events, subdivided into a specified sequence of phases which includes phases of strategy choice, calculation of outcomes, and transfer of territory.
12. A fixed set of possible decision-making algorithms for agents, in two senses: individual agents do not alter their decision-making algorithms, and all agents in a given fully parameterized models will draw their strategies from a limited set: there is no mechanism for generating novel strategies in either model.
Within these characteristics, we can attempt to distinguish those which appear to derive from fundamental features of the real-world domains which the two models are intended to represent (1-6 above), and those which are convenient simplifications (adopted in order to make the models simpler to design and understand), or which arise from such simplifications in combination with the fundamental features (7-12 above). It will be seen that several among the second group of common features arise in one way or another from treating the world as discrete in space and time, rather than as continuous. It should be noted that this is not the case for point 6, synchronous action by the agents: in the real world as in these models, agents interacting with each other must frequently act in ignorance of the decisions and current actions of their peers. It is also worth noticing that points 8 through 10 would have close counterparts in continuous models of the same domains: if place A is near place B, then B is near A, whether A and B are discrete, well-defined cells or not, and in the real world, there are neighborhood relationships both between polities or farms, and between locations within these discrete, anthropogenic divisions of the Earth’s surface.
Finally it can be argued that indefinitely repeated cycles of action, interaction and territorial transfer (point 11), and the use of limited and stereotyped sets of alternative actions (point 12), are reasonable first approximations to the way in which human and animal collectives interact with each other.
Thus most of the main similarities between FEARLUS and GeoSim can be traced, at least in part, to the common features of the domains they are intended to illuminate. These features may seem obvious in retrospect, but we are not aware of any previous exploration of parallels between the domains of international power politics and rural land management. This prompts us to ask what other domains have, or could have, models falling within the TRAP2 class. Since the most important common features of the domains are competition for resource-providing territory between agents with unlimited potential lifespan, we suggest the following domains as among the most promising:
· Competition between non-state human social groups which occupy and exploit territory (hunter-gatherers, non-state agriculturalists, criminal gangs in cities).
· Competition between political parties in constituency-based elections.
· Competition between non-human social groups (wolf packs, baboon troops, ant colonies). In most of these cases, however, there is an effective limit to the size of social group that can remain coherent, and thus on the territory that can be controlled.
· Models of ecological competition between clones (i.e. genetically-defined plant, fungal or bacterial individuals which can grow indefinitely, or at least for very long periods, without giving rise to new, genetically distinct individuals by sexual reproduction).
· Competition over evolutionary time between species with ecological requirements that are sufficiently similar to prevent their co-occurrence in a single area.
Many domains in which MABS models are or might be used would not be suitable for TRAP2 models. Clearly this is so if the spatial relationships between the agents are not important. However, it may be most useful to consider a few “near miss” domains, which share some features with those suitable to TRAP2 modelling, but lack at least one key characteristic, for example:
· Domains where the agents concerned have a potential lifespan shorter than the time over which events are to be modelled – for example, competition between members of solitary, territorial species.
· Domains where indefinitely long-lived agents compete, and are located in space, but do not control exclusive territories: for example, firms competing for market share, or species which compete for some type of resources, but have sufficiently different ecological roles to coexist spatially.
· Domains where there is competition, territorial control and neighborhood, but territorial expansion is absent or unimportant. In fact, many abstract MABSS of interaction and competition, such as Kirchkamp (2000), fall into this category, but it is less easy to think of real-life cases.
· Competition between languages, religions, or other cultural forms: potentially immortal entities which do have a degree of location in space but do not, in the general case, entirely exclude each other. However, in special cases – of effectively enforced intolerance – this domain might be suitable for TRAP2 models.
· “Competition” between land uses for limited space, as modelled within the CLUE framework, for example (Verburg, de Koning, Kok, Veldkamp and Priess 2001). In this case, the “competitors”, which might be identified as agents (CLUE does not do so), are in fact choices open to the “real”agents, the land managers.
Our next steps in this research are:
(1) Continued work on the similarities and differences between FEARLUS and GeoSim. Since both models are regarded as work in progress, it may well be possible to design future versions so that FEARLUS scenarios can be run within GeoSim, and vice versa. We will also work on the transfer of ideas and techniques in both directions: some of the possibilities have already been mentioned.
(2) A survey of existing MABSS within our “home domains”of land use and international politics, to identify those which fall within or on the border of the TRAP2 class, and to determine whether those within the class do in fact appear to form a sizeable and coherent group.
(3) A survey, more detailed than the brief outline given here, of other possible TRAP2 domains.
(4) Further consideration of “near miss”domains such as those listed above.
(5) Steps 1-4 will enable us to refine our description of the TRAP2 class of models. At some point in this process, it will be useful to move from the kind of natural language definition given above, to description in some suitable formal language, perhaps similar to PMML, which is being developed to describe statistical and data mining models (Data Mining Group 2002). Development and use of suitable formalisms should assist in the cooperative development of generally useful descriptions and classifications of MABS models; however, if the move from natural to formal language is made too early in refining a modeling concept, the chosen formalism may play too large a role in shaping the outcome.
(6) A search for theoretical insights and modelling techniques which can be transfered between TRAP2 domains.
By using GeoSim and Fearlus to identify and describe this broader class of TRAP2 models, we believe we have advanced our understanding of both model domains, of the model class itself and of MABS models in general; and gained insights on a variety of aspects of modelling generally not considered through single-model analysis. We believe this paper illustrates one way in which MABS models can facilitate interdisciplinary collaboration and exchange of insights – in this case, between the domains of international politics and rural land management. The opportunity to undertake this study for the M2M Workshop has certainly been scientifically rewarding and worth extending.
Bak, Per (1997) How Nature Works: The Science of Self-Organized Criticality. Oxford University Press
Bankes, Steven C. (2002) Tools and techniques for developing policies for complex and uncertain systems. Proceedings of the National Academy of Sciences vol.99, Suppl.3, May 14, 2002, pp. 7263-7266, http://www.pnas.org/cgi/doi/10.1073/pnas.092081399.
Bremer, Stuart A., and Michael Mihalka. (1977) “Machiavelli in machina: Or politics among hexagons.” In Problems of World Modeling , Karl W. Deutsch, ed. Boston: Balllinger.
Cederman, Lars-Erik. (1997) Emergent Actors in World Politics. Princeton University Press.
Cederman, Lars-Erik (2002) “Modeling the Size of Wars: From Billiard Balls to Sandpiles,” American Political Science Review, forthcoming.
Cederman, Lars-Erik, and Claudio Cioffi-Revilla (2002) “Replicating the Size of Wars: New Empirical Extensions and Computational Reconstructions of Power Laws.” Paper presented at the Annual Meeting of the International Studies Association, New Orleans, LA, 2002; Arrowhead Conference on Agent-Based Model Simulations, UCLA, Lake Arrowhead, CA, May 2002.
Cioffi-Revilla, Claudio (1998) Politics and Uncertainty: Theory, Models, and Applications. Cambridge University Press.
Cioffi-Revilla, Claudio “Invariance and Universality in Social Agent-Based Simulations” (2002) Proceedings of the National Academy of Sciences of the U.S.A., Vol.99, Suppl. 3, no. 14, May 14, 2002, pp. 7314–7316. http://www.pnas.org/cgi/content/full/99/suppl_3/7314
Cusack, Thomas R., and Richard J. Stoll. (1990) Exploring Realpolitik: Probing International Relations Theory With Computer Simulation. Boulder, CO: Lynne Rienner.
Davis, Philip J. and Reuben Hersh (1980) The Mathematical Experience. Birkhäuser. Ch.4, final section: “Unity within Diversity” (pp.198-200 in 1983 Penguin edn.)
Downing, Thomas E., Scott Moss and Claudia Pahl-Wostl (2001) Understanding climate policy using participatory agent-based social simulation. In Moss, Scott and Paul Davidsson (eds) Multi-agent Based Simulation: Second International Workshop, MABS 2000, Springer.
Ember, Carol R. and Melvin Ember (2002) Cross-Cultural Research Methods. New York and London: AltaMira Press.
Gotts, Nicholas M. (2000) “Describing the Topology of Spherical Regions using the ‘RCC’ Formalism”, pp.83-104 in Ó Nualláin, Séan (ed) Spatial Cognition: Foundations and Applications. Selected Papers from Mind III, Annual Conference of the Cognitive Science Society of Ireland, 1998. Volume 26 in the Advances in Consciousness Research series. John Benjamins.
Gotts, Nicholas M., J. Gary Polhill, and Alistair N. R. Law (2001) “Modelling land use change using standard and modified cellular automata.” Working paper available from authors.
Gotts, Nicholas M., J. Gary Polhill, and Alistair N. R. Law (2002) “Aspiration Levels in a Land Use Simulation”. Submitted to Cybernetics and Systems. Draft version available from http://www.macaulay.ac.uk/fearlus/FEARLUS-publications.html.
Gotts, Nicholas M., J. Gary Polhill, and Alistair N. R. Law (in press) “Agent-based simulation in the study of social dilemmas.” Artificial Intelligence Review.
Grimmett, G.R. and D.R. Stirzaker (1992) Probability and Random Processes. Oxford University Press.
Kirchkamp, O. (2000) “Evolution of Learning Rules in Space”. In Suleiman, R., K.G. Troitzsch and G.N. Gilbert (eds) Tools and Techniques for Social Science Simulation. Berlin, Physica-Verlag, Ch. 10, pp.179-195.
Landman, Todd (2000) Issues and Methods in Comparative Politics: An Introduction. London and New York: Routledge.
Padgett, John, Lars-Erik Cederman, Claudio Cioffi-Revilla, David Sallach (2002). NSF-ITR Proposal.
Data Mining Group (2002) “PMML Version 2.0”, http://www.dmg.org/pmml-v2-0.htm/.
Polhill, J. Gary (2002) FEARLUS Model 0-6-2 User Guide. Available online at http://www.macaulay.ac.uk/fearlus/FEARLUS-publications.html.
Polhill, J. Gary, Nicholas M. Gotts, and Alistair N. R. Law (2001) “Imitative versus nonimitative strategies in a land-use simulation.” Cybernetics and Systems 32: 285-307.
Polhill, J. Gary, Nicholas M. Gotts, and Alistair N. R. Law (2002a) “Artefacts in the representation of space in a land use simulation.” Working paper available from authors.
Polhill, J. Gary, Nicholas M. Gotts, and Alistair N. R. Law (2002b) “Combining object-oriented programming and relational databases for multi-scale spatially-integrated agent-based models.” In Rizzoli, Andrea E. and Anthony J. Jakeman (eds) Integrated Assessment and Decision Support: Proceedings of the 1st Biennial Meeting of the International Environmental Modelling and Software Society, Vol. 2, pp. 251-256.
RePast (2002) http://repast.sourceforge.net/ May 30, 2002.
Swarm (2002) http://www.swarm.org/ Swarm Development Group, October 24, 2002.
Verburg, P.H., H.G.J. de Koning, K. Kok, A. Veldkamp and J. Priess (2001), “The CLUE modelling Framework: An Integrated Model for the Analysis of Land Use Change”. In Singh, R.B., Jefferson Fox and Yukio Himiyama (eds) Land Use and Cover Change, Science Publishers, Enfield, NH.
 Authors are listed alphabetically. The present work was completed with partial support from the Complex Systems Network of Excellence (Exystence), FET-IST European Communities grant IST-2001-32802. Cioffi was supported by the Center for Social Complexity at George Mason University. Gotts was supported by the Scottish Executive Environment and Rural Affairs Department. The authors are grateful to the authors of the simulation models compared in this study, but they are solely responsible for any errors of interpretation.
 Note that this does not prevent, for example, agents in a MABS model using stored information about earlier times: the contents of the agents’ memories of times t-1, t-2… themselves form part of the model’s state at time t.
 The description of FEARLUS differs in some respects from that given in Polhill et al (2001); this reflects changes to the model made since that paper was written. Polhill (2002), being a user guide, describes the model at the implementation level. Some features of the implementation that have never been used in experiments, and some which are not regarded as part of the structure of the model for the purposes of this paper, are ignored or described only in outline here.
A number of terms will be used to refer to elements and aspects of FEARLUS models, some of which could also refer to real-world entities. In FEARLUS model terms, each word begins with an upper-case letter (e.g, “Land Manager”). Each such term is italicised when first used.