Sugarscape

Resources

The simplest version has a single resource, called sugar, that is unequally distributed across the terrain. The terrain and its initial sugar distribution is often called the sugarscape. The distribution of sugar is not simply random but instead has areas of greater concentration.

Patches

A terrain is a collection of patches. Each location on the terrain is a single patch (also called a cell). This location is designated by ordinary Cartesian coordinates, and these coordinates may be considered to be an immutable attribute of a patch. Patches are associated with the renewable resource in the following ways. An immutable characteristic of a patch is its sugar capacity (maxsugar). Since sugar capacity differs between patches, they are fundamentally heterogeneous. In addition, a patch’s actual amount of sugar (sugar) may differ from its capacity. This is another source of heterogeneity.

Patch Behavior

There is one patch behavior: regenerating the renewable resource whenver it is below capacity. In the Sugarscape model, this behavior is captured by a single growback rule that governs the entire terrain. This chapter focuses on the discrete growback rule of [Epstein.Axtell-1996-MIT]. This characterizes growback as follows.

Here \(\alpha\) is the maximum amount of sugar that a patch might be able to grow back in one period. This is a model parameter that applies to the entire terrain. The parameter \(s_\max\) receives the patch-specific carrying capacity (maxsugar), and the parameter \(s\) receives the current resource level of the patch (sugar). So a patch can regrow sugar at a terrain-specific rate, but only up to its maximum capacity. (In the canonical Sugarscape model, the capacity of each patch—its maxsugar—lies in the integer interval \([0\,..\,4]\).)

immutable attributes:

• location

• maxsugar (sugar capacity)

mutable attributes:

• sugar

Terrain Specifics

The terrain is a two-dimensional rectangular array of patches, which are assigned adjacent integer coordinates.

immutable attributes:

• dimensions (number of rows and columns)

• \(\alpha\) (growback rate)

Canonical Terrain

The canonical Sugarscape terrain is a \(50 \times 50\) grid of patches. Each patch has a sugar capacity (maxsugar) that lies in the integer interval \([0\,..\,4]\). Correspondingly, the actual sugar (sugar) of any patch must fall in this interval.

Sugar capacity is clustered. Unfortunately, the original [Epstein.Axtell-1996-MIT] presentation describes the terrain verbally rather than algorithmically. There are two peaks (with sugar capacity 4), separated by a valley, and surrounded by a “desert” of sugarless patches. An image accompanies this description, and various replication efforts have attempted to extract data from this image. This |chapter| works with the sugar data provided in the NetLogo Models Library, which is very similar but not identical to the original terrain. [1]

Initialization of the Terrain

Intialization of the terrain first sets the value of maxsugar and then sugar for each patch. Take the values of maxsugar, sequentially from the sugar-map.txt file, which has the same \(50 \times 50\) layout as the terrain. Note that the value of maxsugar is in integer interval \([0\,..\,4]\). Each cell receives an initial value of sugar equal to its capacity.

[Epstein.Axtell-1996-MIT] were not explicit about the initialization of the sugar attribute of agents, saying only that every agent is initialized with “some initial endowment”. The value of the patch’s sugar is then set to its value of maxsugar.

Visualization of the Terrain

White = no sugar, darker gray = more sugar, possible levels (0, 1, 2, 3, 4)

Environment visuals

the value of psugar is indicated by its color: darker gray implies more sugar.

Autonomous and Heterogeneous Agents

• agents are “autonomous” in the following sense: they are not centrally governed

• agents are heterogeneous in

  • initial location

  • immutable attributes (vision, metabolism, sex, maximum age)

  • mutable attributes (wealth, location)

Agents also have the capacity to accumulate sugar wealth w. An agent's sugar wealth is incremented at the end of each time-step by the sugar collected and decremented by the agent's metabolic rate. Two agents are not allowed to occupy the same patch in the grid. (Unique location constraint.)

Initialization of the Terrain

Visualization of the Terrain

Movement (Environment Topology)

• There is at most one agent at each location of the terrain.

• torus topology: location coordinates wrap around the edges

Model 1: Setup

• 400 agents, each placed on random unoccupied patch (no dual occupancy)

• each agent can only see a certain distance (vision, in [1,6]) horizontally and vertically

• each agent has a certain sugar need (metabolism, in [1,4])

Schedule

At each tick, each agent will

• move to the nearest unoccupied location within their vision range with the most sugar (their own patch is a candidate when moving)

• collect all the available sugar there. If its current location has as much or more sugar than any unoccupied location it can see, it will stay put.

• use (and thus lose) a certain amount (metabolism) of sugar each tick.

• if an agent runs out of sugar, it dies and (in the first model) is simply removed from the simulation

Setup

agents

age 0

randomly chosen unoccupied initial location,

random attributes (vision, metabolism, max-age, initial wealth w0)

random attribute values are drawn from uniform distributions with ranges specified below

Model Rules

patch growback rule Gα:

each patch grows α units of sugar per time-step, up to the patch's capacity

agent movement rule M:

move to nearest best unoccupied, visible patch (resolving ties randomly)

best = most sugar visible = with vision patches to the N, E, S, W (vNM neighborhood)

collect all sugar at new location, decrement sugar wealth by metabolism

if sugar wealth <= 0, die

agent replacement rule R:

if an agent dies, it is replaced by a new agent

new agents get the same initializations as initial agents

Scheduling of events

Scheduling is determined by the order in which the different rules G, M and R are fired in the model. Environmental rule G comes first, followed by agent rule M (which is executed by all agents in random order) and finally agent rule R is executed (again, by all agents in random order).

Parameterisation

Epstein & Axtell (1996, pg. 33)

Growth rate α

1

Number of agents N

250

Agents' initial wealth w0

distribution U[5,25]

Agents' metabolic rate m distribution

U[1,4]

Agents' vision v distribution

U[1,6]

Agents' maximum age max-age

distribution U[60,100]

Initialization

• set sugar level of each patch to its sugar capacity

• create n-agents agents at a random unoccupied initial locations

• initialize agents

Sugarscape as a Time-Homogeneous Markov Chain

Sugarscape “induces” a THMC:

• state of the system as a 50×50 array

• each array element corresponds to one patch

• patch state now becomes

  • the patch's sugar level

  • whether the patch is occupied

  • occupying agent's state (e.g., vision, metabolic rate, wealth and life expectancy)

• the number of possible states is finite since all the state variables can only take a finite set of values.

• the state implies a probability distribution over the state space for the following time-step

Analysis

irreducible THMC:

it is possible to go from any state i to any other state j in finite time

Izquierdo, Izquierdo, Galán and Santos (2009)

“the state space of the induced THMC described in the previous section is irreducible and aperiodic (also called ergodic)”

• IIGS (2009)

Regenerating States

regenerating states:

states where agents stay stationary and no sugar is collected.

Example:

• every agent has vision v = 1

• all agents are placed on interior desert patch

Agents do not move because the only unoccupied patches they can see have no sugar, and no sugar is collected for the same reason.

A regenerating state can produce a regenerating state: place any newborn in one of dessert patches.

Pristine State

If a regenerating state is produced four times in a row (AE's maximum sugar capacity is 4), the environment returns to its initial state: each patch's sugar level is equal to its capacity

IIGS define any such state to be a “pristine state” each patch's sugar level is equal to its capacity.

define exterminating pristine states: pristine states where

• every agent dies (because every agent's sugar wealth w is no greater than its metabolic rate m).

Possible States

A state is possible if we can indentify a sequence of events that can lead to it, each with strictly positive probability.

THMC is irreducible

i.e. it is possible to go from any state i to any state j in a finite number of time-steps.

THMC is irreducible (proof)

The proof rests on the following facts:

Let us call initial states those states that can be generated at the begginning of the simulation.

Given our definition of the state space, any state j can be reached by running the model from some initial state j0.

Any initial state j0 is reachable from any exterminating pristine state in one time-step.

To achieve this (departing from the exterminating pristine state) one only has to create the population of newborns as in state j0.

Any state i can lead to an exterminating pristine state, i.e. for every state i there exists an exterminating state ext-prist-st such that p(ni)i,ext-prist-st > 0 for some ni.

Note that one can reach a regenerating state from any state i by giving every newborn vision v = 1 and placing it in any of the patches coloured in red in figure 2.

(Note that sooner or later every agent must die because the maximum age max-age is 100.)

Reaching an exterminating pristine state from a regenerating state is straightforward: one only has to organise a synchronised genocide by "growing" agents with the desired life span –something that can be done by appropriately setting the newborns' metabolic rate m and initial wealth w0 (and vision v = 1).

A newborn with vision v = 1, metabolic rate m and initial wealth w0 placed on one of the patches painted in red in figure 2 will live Ceiling[w0/m] time-steps.

Since this procedure allows us to "grow" agents with life spans whose greatest common divisor is 1, it is possible (Bézout's identity) to organise a synchronised genocide from any regenerating state.

Having proved that the THMC is irreducible, it only remains to prove that it is also aperiodic.

To prove this it suffices to find an aperiodic state –as indicated in section 8 of our paper, after definition 7–.

Note that any exterminating pristine state ext-prist-st is clearly aperiodic, since the greatest common divisor of the set of integers n such that p(n)ext-prist-st,ext-prist-st > 0 is 1, as explained in the third bullet point of the previous list.

This concludes the proof that the induced THMC is irreducible and aperiodic, i.e. ergodic.

Ergodic THMC

In ergodic THMCs, the LR probability of finding the system in each of its states in the long run is

• strictly positive

• independent of the initial conditions

• and the limiting distribution π coincides with the occupancy distribution π* (the long-run fraction of time that the system spends in each state).

Hence, the limiting distribution of any statistic (e.g. the sugar wealth distribution) coincides with its occupancy distribution too, and does not depend on the initial conditions.

Thus, we could approximate the limiting distribution of emergent wealth distributions in Sugarscape as much as we like by running just one simulation (with any initial conditions) for long enough.

Further Reading

References

Buzing, P. and A. Eiben and M. Schut (2005) Emerging Communication and Cooperation in Evolving Agent Societies. Journal of Artificial Societies and Social Simulation 8(1)2. http://jasss.soc.surrey.ac.uk/8/1/2.html.

Epstein, J.M. (1999) Agent-Based Computational Models And Generative Social Science. Complexity 4(5), pp. 41-60.

Epstein, J. M. and Robert L. Axtell (1996) Growing Artificial Societies: Social Science from the Bottom Up. The MIT Press.

Flentge, F. and D. Polani and T. Uthmann (2001) Modelling the Emergence of Possession Norms Using Memes Journal of Artificial Societies and Social Simulation 4(4)3. http://jasss.soc.surrey.ac.uk/4/4/3.html.

Izquierdo, Luis R. and Segismundo S. Izquierdo, José Manuel Galán and José Ignacio Santos (2009) Techniques to Understand Computer Simulations: Markov Chain Analysis Journal of Artificial Societies and Social Simulation 12(1)6. http://jasss.soc.surrey.ac.uk/12/1/6.html and especially the appendix http://jasss.soc.surrey.ac.uk/12/1/6/appendixB/EpsteinAxtell1996.html#epstein1996