© Copyright JASSS

  JASSS logo ----

Andreas Flache and Rainer Hegselmann (2001)

Do Irregular Grids make a Difference? Relaxing the Spatial Regularity Assumption in Cellular Models of Social Dynamics

Journal of Artificial Societies and Social Simulation vol. 4, no. 4

To cite articles published in the Journal of Artificial Societies and Social Simulation, please reference the above information and include paragraph numbers if necessary

Received: 4-July-01      Accepted: 10-Sep-01      Published: 31-Oct-01

* Abstract

Three decades of CA-modelling in the social sciences have shown that the cellular automata framework is a useful tool to explore the relationship between micro assumptions and macro outcomes in social dynamics. However, virtually all CA-applications in the social sciences rely on a potentially highly restrictive assumption, a rectangular grid structure. In this paper, we relax this assumption and introduce irregular grids with variation in the structure and size of neighbourhoods between locations in the grid. We test robustness of two applications from our previous work that are representative for two broad classes of CA models, migration dynamics and influence dynamics. We tentatively conclude that both influence dynamics and migration dynamics have important general properties that are robust to variation in the grid structure. At the same time, we find in both examples substantively interesting implications of the irregular grid that could not be identified with a regular grid structure.
Cellular Automata; Sensitivity Analysis; Social Simulation

* Introduction

In the wake of Schelling's (1971) and Sakoda's (1971) pioneering contributions[1], cellular automata (CA) models are increasingly used to study a variety of social dynamics (for some background cf. Hegselmann 1996, Hegselmann and Flache 1998). The most prominent reason is that CAs can be seen as multi-agent systems based on locality with overlapping interaction structures. In this perspective, CAs are attractive as a modelling framework that may provide a better understanding of micro/macro relations. However, many social scientists reject the CA approach on the grounds that the CA framework is far too simple, or -to put it mildly- far too idealised, to be an appropriate tool for modelling social processes. They argue that standard CA assumptions like discrete time, regular grid structures, finite sets of states etc. may make the approach so overly simplistic that it is questionable whether its results can be generalised beyond the particular framework. While we do not necessarily share this concern, we feel that systematic analysis of the robustness of CA modelling is necessary. In this paper, we will address effects of the standard CA assumption of rectangular grid structures.
Regular grids, or more particularly: rectangular grids, are the standard grid structure that is used in previous CA studies. Broadly, a regular grid assumes that the structure of the cell grid and the number of neighbours are homogenous for every location in the cellular space. This assumption seems highly implausible as an empirical description of the geographical or social space that underlies the processes typically studied in CA modelling, like opinion formation or neighbourhood segregation. However, to our knowledge there are virtually no insights into how regular vs. irregular grid structures affect cellular dynamics.
Our research group began recently to study effects of grid structure and to develop software tools for using irregular grids in CA modelling (Hegselmann et al. 2000, Flache and Hegselmann 2000). In the present paper, we apply these tools to test the robustness of substantive results for two cellular models from our work. These models represent the two classes of dynamics typically used in CA modelling. The first model represents the class of "influence dynamics". In influence dynamics, typically every cell in the cellular world represents an actor, and the states of actors (opinions, behaviour) change in response to the states of their neighbours. Examples are models of opinion formation (Latane and Nowak 1997), or the propagation of co-operation in social dilemma games with a spatial dimension (Axelrod 1984, Nowak and May 1993). The second model in this paper represents "migration dynamics". In migration dynamics, the cellular world typically contains a number of empty cells so that actors can change their location in the cellular world by migration. The location actors choose depends on the present distribution of other individuals in their own neighbourhood and in the neighbourhood of the potential new location. Prominent examples of migration dynamics are Schelling's (1971) model of neighbourhood segregation or Sakoda's (1971) model of group formation.
For both classes of CA models, there are a priori reasons to expect that relevant properties of the dynamics are not necessarily robust to variation in the grid structure. Moreover, certain effects of interest may not be revealed by regular cellular models. A first reason to expect grid effects is that regular grids may impose restrictions on the transitivity of neighbourhood relationships. A second reason is that regular grids preclude variation in the number of neighbour cells between locations. To explain, many rectangular grid models use a von Neumann neighbourhood or a Moore neighbourhood, like those shown in Figure 1.
Figure 1: Neighbourhood definitions in a cellular automaton.
Clearly, with a von Neumann neighbourhood it is impossible that there are transitive relationships between neighbours. If B is neighbour of A and C is neighbour of A then B can never be neighbour of C. The Moore neighbourhood allows for transitivity, but at the same time it precludes variation in it, in the sense that every cell has the same number of transitive relationships with neighbour cells. These restrictions on transitivity may be highly influential for influence dynamics. For example, Heider's balance theory (Heider 1946) suggests that in opinion formation dynamics, actors may strive to maximise consistence in their relations with neighbours, yielding transitive opinion patterns in their neighbourhood. Accordingly, the results of opinion formation on basis of Heiderian principles may be different, when transitivity is precluded or, at least variation in the pattern of transitive relationships between local positions in the grid is not possible.

Both migration and influence processes may be affected by lack of variation in the number of neighbour cells across the grid. In typical migration processes, the attractiveness of a new location depends partly on the number of neighbours one can have. For example, in Schelling's neighbourhood segregation model, actors strive to migrate to locations where they have at least a certain proportion of neighbours of their own category. However, the larger the number of neighbour cells, the smaller is the standard deviation in the proportion of ingroup neighbours in a randomly distributed neighbourhood. Accordingly, stable patterns may be less likely to emerge randomly in a grid location with more neighbour cells. This, in turn, may make it harder for migration dynamics to stabilise in an irregular grid as compared to a regular grid, because it does not only matter what positions actors occupy relative to each other, but also where they occupy these positions. In influence dynamics, variation in the number of neighbour cells may affect the resistance that a certain position can have against outside pressures. For example, the more neighbours I have, the more I may be exposed to neighbour influence relative to self-influence. Again, opinion formation dynamics may generate different results depending on the location in an irregular grid.

In Section 2, we describe how irregular grids are implemented in our CA models. Section 3 describes and analyses the example of a influence dynamic, a model of the propagation of reciprocity in spatial collective action. Section 4 deals with the model of a migration dynamic, which is a model of the backward- looking evolution of a social support network. Section 5 summarises and concludes.

Irregular Grids in a Cellular Automaton

Practically all social science applications of cellular modelling use a regular grid as the underlying network structure. More in particular, the standard grid structure used is a rectangular regular grid. Other regular grids could be hexagonal or triangular structures. In general, we denote grids as regular where all inner cells (i.e. cells that are not at the border of the grid) have the same number of neighbours, whatever our neighbourhood definition may be - von Neumann neighbourhood or a Moore neighbourhood of a given size. On a regular torus, this definition generalises even to border cells.

To model irregular grid structures, we use a Voronoi-diagram. The basic idea for construction of a Voronoi diagram is the following. A number of points that is corresponding to the number of cells in the grid, are randomly located on a rectangular surface. These points are called generators. The cell of a particular generator i is then defined as the area containing all points of the rectangle that are closer to i than to any other generator in terms of euclidian distance. Figure 2 illustrates the construction method. The crosses in Figure 2 are the generators of the grid. The edges of the resulting polygons are points with equal distance to their neighbouring generators.[2]

Figure 2: A Voronoi diagram.
Figure 3 shows a decisive feature of irregular grids: even the cells inside the grid have different numbers of next neighbours. The figure shows how within the same grid there are locations with 3, 4, 5 and 8 next neighbours. We define a next neighbour cell here as a cell that has a common border (not just a common edge) with the focal cell. Notice that this definition implies a von Neumann neighbourhood on a rectangular grid. More in general, it has been found in simulation analyses that in a Voronoi graph, the number of neighbour cells varies between 3 and 14, where the average number approaches 6 if the number of cells approaches infinity (cf. Upton, Fingleton 1985; Okabe et al. 1992).

Figure 3: Cells with 3, 4, 5, and 8 next neighbours in a Voronoi graph.

The Dynamics of Reciprocity in Irregular Worlds


This section addresses the question whether and to what degree the spatial structure of a cellular worlds matters for the dynamics of individual reciprocity in spatial collective action. Olson (1965) has prominently pointed out how collective goods may suffer from free rider problems in collective action. A group may end up with collective action failure, resulting in severe underprovision with a collective good. This is, because every member benefits from provision of the good, but "free riders" who fail to contribute to its production can not be excluded from consumption. In spatial collective goods, the positive or negative side effects on other members of actors' contributions depend on their location in a geographical space. Environmental problems are a typical example. Here, one actors' pollution may harm only those others within a certain distance, as for example in the diffusion of exhaust or in the spread of noise. This suggests that cellular automata are a useful tool to describe the dynamics that ensue, if individuals follow strategies that link their own contribution to observed effects of contributions by others. Reciprocity strategies in particular, like the well-known "Tit for Tat", have received a great deal of attention in the collective action literature (cf. Friedman 1971, 1986; Axelrod 1984; Taylor 1987) as a possible decentralised mechanism that solves the free rider problem identified by Olson (1965). Accordingly, this section focuses on the dynamics of reciprocity in spatial collective action.

To demonstrate the effects of spatial structures, we concentrate on the propagation of co-operative behaviour starting from small clusters of initial co-operation. We assume that these clusters are at the outset encircled by a "sea of defection". Cellular modelling has demonstrated how then reciprocity strategies in spatial collective action may initially lead to the conversion of defectors in the neighbourhood of the cluster, and then entail self sustaining co-operation, as the initial cluster of co-operation grows bigger (cf. Axelrod 1984, Nowak and May 1993). However, previous analyses have exclusively used rectangular grid structures to study the propagation of co-operation. This imposed strong homogeneity assumptions that may both produce artefacts and obscure possible effects of heterogeneity in the spatial structure. For example, the prospects for co-operation to spread may critically depend on the density of clusters relative to their neighbourhood. If clusters contain relatively more co-operative members per unit square measure, then their relative impact on defecting neighbours may increase, improving prospects for co-operation. Moreover, local properties may make particular areas more prone to be "conquered" by spreading co-operation, while others may be hard to invade, limiting the degree to which co-operation can spread. Clearly, an analysis based on regular grids fails to shed light on these possibilities. Accordingly, we compare in the following reciprocity dynamics for regular and irregular grid structures, both to test robustness and to address possible effects of variation in spatial density. In 3.3 we describe the model of reciprocity in spatial collective action, and 3.7 shows results.

A Model of Reciprocity in Spatial Collective Action

Spatial collective action
We study a spatial collective good with the following simple properties. The larger the number of contributors in the neighbourhood of a focal cell, the higher the benefit that this cell obtains from consumption of the good. Moreover, every neighbour has the same impact on the benefit that accrues to the focal cell. Neighbourhoods are defined by geographical distance to the focal cell. For simplicity, the distance dij between a cell i and a cell j is the euclidian distance between the generator points of the cells, i.e. , where (xi , yi) and (xj , yj) represent the generator coordinates. The neighbourhood of a cell then includes those cells that lie within a maximal distance r from the focal cell. This distance may represent the physical properties of the pollution process. In particular, it implies that the side effects of the pollution of a particular individual can no longer be felt, if the distance to this individual exceeds the maximum range r. Throughout this paper we assume that points in the rectangle in which cells are embedded are described in a two-dimensional euclidian space with coordinates of 0...1000 × 0..1000. Moreover, in all models the cellular world is a torus, i.e. it has no borders. Cells that appear in a 2-dimensional representation of the grid on the left border are neighbours of cells that appear on the right border and cells that appear on the upper border are neighbours of those that appear on the lower border, and vice versa.

Figure 4 below illustrates the shape of neighbourhoods in a rectangular grid, using a range of r = 300 and 20 × 20 = 400 cells. The locations of the two actors in the figure are chosen such that they are just close enough to be within each other's neighbourhood. Figure 4 demonstrates that in the rectangular world, every cell has the same number of neighbours. Clearly, this is different in an irregular grid. Figure 5 shows how the location in space affects the number of neighbours in an irregular grid. The figure uses a range of r = 100 in a grid with 11 × 11 = 121 cells. Figure 5 demonstrates that depending on spatial location, cells may have 2, 5 or 8 neighbours under the same range of r = 100.

Figure 4: Neighborhood of two individuals in the rectangular cellular world (r=300, cellsize 50 × 50).
Figure 5: Neighbourhoods of three different cells in an irregular grid. Range r = 100, 11 × 11 cells. Focal cells are blue, neighbour cells are red.
To model reciprocity, we assume that actors are selected in random order to make from time to time a new decision about their contribution to the collective good. At this point, actors contribute if and only if the proportion of co-operative neighbours is sufficiently large. More precisely, we assume that all inhabitants of the cellular world have the same expectation level or contribution threshold E (0 < E < 1).

With this decision heuristic, actors' behaviour is decisively shaped by their expectation level E (0 < E < 1). For example, if a player has a high expectation level, say E = 0.95, small "disturbances" in others' co-operation suffice to make him uncooperative. At the same time, a player with a relatively low expectation level, say E = 0.3, is very "robust" in his willingness to co-operate.


First, we analyse the conditions that affect the growth of co-operative clusters in a rectangular world. Subsequently, we test these results for robustness in an irregular world. Finally, we study in more detail how in the irregular grid the local density of clusters affects the dynamics of reciprocity.

Figure 6 illustrates non-linear effects of the size of the neighbourhood for a particular starting condition. The simulations assume that all actors have an expectation level of E = 0.3. The "world" is a rectangular torus grid with 50 × 50 = 2500 cells and the initial cluster is a rectangle, with 9 × 9 = 81 contributors. To show effects of the neighbourhood size, r varies from a very small radius of r = 20 to r = 80 and r = 160.

Figure 6: Non-linear effects of neighbourhood size r in a rectangular torus world. Expectation level E = 30%, Initial cluster of 9 × 9 = 81 contributors, 50 × 50 torus grid.
Figure 6 demonstrates three qualitatively different scenarios. With a small neighbourhood, the initial cluster can not grow, but it is stable. Under a medium size neighbourhood, with range r = 80, the cluster grows and eventually occupies the entire world. Finally, clusters vanish and the endstate is universal defection, if the neighbourhood is large with r = 160. The underlying mechanism of this non-linear effect of neighbourhood size is straightforward. If r is very small, the neighbourhood is effectively a von Neumann neighbourhood. That is: only the cells in the North, East, South and West of a focal cell are members of the neighbourhood. Clearly, in this case a member of the initially co-operative cluster can maximally have 2 defecting neighbours, a case that occurs only for the 4 corner cells of the cluster. At the same time, defectors have never more than one member of the cluster in their neighbourhood, which is the case for those defectors who are located at the borderline of the cluster. Hence, co-operators find more than the expected 30% co-operation, while defectors maximally find 25% co-operation. Accordingly, the reciprocity rule implies that neither class of actors changes their behaviour. This pattern changes as soon as the neighbourhood size exceeds a critical level. In the case of r = 40, the "circular" neighbourhood of defectors at the outer border of the cluster stretches far enough into the cluster to encompass more than 30% co-operators. At the same time, co-operators at the inner border see less than 70% defection around them. Consequently, defectors start to change into co-operators, but not vice versa[3]. This tips the balance towards growth of the cluster until universal co-operation obtains. Finally, the case of r = 160 represents the situation that occurs when neighbourhoods are so large that even for members inside the cluster a large part of the defecting "outworld" is included in their neighbourhood. Here, all or at least a considerable part of the cluster members experience less than 30% co-operation in their neighbourhood, while the same is true for all defectors. As a consequence, the cluster crumbles and eventually vanishes.

Further simulations show how this pattern occurs under a considerable range of conditions. Figure 7 shows the results of simultaneous variation of the size of the initial cluster h, actors' expectation level E, and the radius of the neighbourhood, r. The size of the initial rectangular cluster is represented in terms of the number of cells for which the cluster stretches in every direction from its central cell, h. Hence, h = 1 represents a 3 × 3 cluster, while the cluster includes 17 × 17 = 289 members for h = 8. The expectation level varies between E = 0.3 to E = 0.4 and the neighbourhood radius r varies at 12 different levels, ranging from r = 20 to r = 320, where we increase the step size from 20 to 40 above r = 140. For reliability, results are based on 10 replications per condition.

Figure 7: Effects of expectation level E, cluster size h and neighbourhood radius r on final state of TFT-dynamics. Rectangular grid.
Figure 7 illustrates how clusters collapse, as soon as the neighbourhood size exceeds a critical level. Broadly, the larger the initial cluster and the lower actors' expectation level, the larger the range of neighbourhood sizes for which clusters can grow or at least be stable. Moreover, the results indicate that the non-linear patterns represented by Figure 6 occur both for E = 0.3 and E = 0.4 for a large range of initial cluster sizes. In this range, clusters are stable if the neighbourhood is small, but they can grow as soon as neighbourhood size exceeds some level. Finally, as neighbourhood size rises further, the critical level is exceeded beyond which clusters collapse and universal defection obtains.

To test robustness, we replicated these analyses on an irregular cellular grid. We used an irregular torus grid with 2500 cells, where generators were equally distributed on the 1000 × 1000 rectangular area. Like in the previous simulation, expectation levels vary between E = 0.3 and E = 0.4. The variation of the neighbourhood size was restricted to four different levels, r = 30, 50, 85 and 160, because computing time is much higher for irregular grids as compared to regular grids. In an irregular grid, it is unclear how to define a rectangular cluster. Accordingly, we use the method applied for the definition of neighbourhoods also to delineate clusters. A cluster is the set of cells whose generators lie within a radius of h around its central point. Cluster size was varied between h = 30 and h = 190 in 8 equidistant steps. Finally, it matters on the irregular grid, where the cluster is located. Accordingly, to test robustness across various locations, we simulated 16 different locations for every parameter combination, distributed on the intersections of a 4 × 4 regular coordinate system. That is, x and y coordinates both vary across 125, 375, 625 and 875. For reliability, 50 simulations per cluster location and parameter combination were used. Figure 8 below shows the results.

Figure 8: Effects of expectation level E, Cluster size h and neighbourhood radius r on final state of TFT-dynamics. Rectangular grid with varying location of cluster.
Comparison of Figure 8 with Figure 7shows that by and large the qualitative results obtained for the rectangular grid are robust. Increasing neighbourhood size tends to shift the qualitative endresult from cluster stability or cluster growth towards collapse of the cluster. Moreover, if initial clusters are sufficiently large, then clusters are stable under small neighbourhoods, clusters grow with intermediate neighbourhood size and clusters collapse if neighbourhoods are too large. At the same time, the areas in the figure that are white, light orange or light purple indicate how at least two or even three qualitatively different end results may obtain under the same combination of conditions. This is different from the rectangular grid, where the combination of cluster size, neighbourhood size and expectation level fully determined the endstate of the reciprocity dynamics. This variation in the irregular grid is caused by two factors. The first factor is that in an irregular grid, the course of dynamics may be highly path dependent, depending on the particular order in which cells update their "behaviour". The second factor is that all other things being equal, dynamics vary between cluster locations. We discuss both factors in turn.

To demonstrate path dependence, we choose a scenario where one and the same cluster either may stabilise, grow moderately or grow strongly depending on the sequence of cell updates. For this simulation, the same irregular grid was used that underlies the analysis of Figure 8. The midpoint of the circle that defines the cluster is located at the grid coordinate (166.66, 500), actors' expectation level is E = 0.3, the neighbourhood is small with a radius of r = 30, and the initial cluster radius is h = 190. Figure 9 below represents the frequency with which a particular cell was co-operative in the endstate of this simulation, based on 100 replications.

Figure 9: Path dependence in the growth of a cluster in an irregular grid. Colours indicate relative frequency of co-operation in this cell in the endstate, based on 100 replications. Dark blue = 100%, Blue = 83%, Red = 0%). Initial cluster size h = 190, expectation level E = 0.3, neighbourhood size r = 30.
Figure 9 shows that the cluster grows into a large cluster in all replications of the dynamics. However, there are a number of additional cells that turn into co-operators only in about 83% of the replications. Moreover, the figure demonstrates that there are certain regions in the irregular grid that never become co-operative, even if they are completely encircled by co-operative cells. This suggests that these regions may have local properties that make them particularly resistant against outside influences. This result also indicates that such regions might be particularly suitable as strongholds or seedbeds of co-operative behaviour. In the following, we analyse more closely the local properties of an initial cluster location that facilitate the propagation of co-operation.

The density of cells within a cluster seems to be an important factor for cluster growth. More precisely, the denser cells are within the cluster, and the sparser the distribution of cells around the cluster, the higher will be the proportion of co-operation that neighbours of the cluster find around themselves. This in turn favours cluster growth. To measure how this relative cluster density varies across locations, we compute the density difference D between a cluster and the surrounding area that is close to the cluster. Equation [1] below formalises the definition of the density difference D.

The symbol a in [1] is the average surface of a cell in the grid, i.e. 1000 × 1000 divided by the number of cells. The ratios in [1] compare this average surface to indicators for the average surface of cells in the cluster, aC, and the average surface of cells within a ring between distance of r and 2r around the centerpoint of the cluster, aR. To be precise, for calculation of aC and aR the number of cells are counted whose generators are located within the circle of the cluster and within the ring around it, respectively. Then, the respective cell numbers are divided by the corresponding surfaces of cell and ring. Accordingly, if the density of cells within the cluster is high, the average surface of a cell in it is small, resulting in a high ratio of a/aC. Hence, a negative density difference D indicates that the distribution of cells is less dense within the cluster than around it, while a positive density difference represents the opposite case.

To test the expected positive effect of relative density on cluster growth, we simulated 2500 different cluster locations for a selected condition. The cluster locations were randomly chosen with equal distribution over the world. For every location, per condition the average fraction of co-operators was measured in the whole world in the endstate of the simulation, based on 50 replications. Figure 10 below shows the results for this analysis. The figure is based on the parameter combination of an expectation level E = 0.3, neighbourhood size r = 50 and cluster size h = 30. The figure charts the effect of the density difference D on the average fraction of co-operators in the endstate, where each dot in the figure represents one of the 2500 cluster locations.

Figure 10: Fraction of co-operators in the endstate as a function of the relative density of the initial cluster. E = 0.3, r = 50 and h = 30. Results are based on 2500 different cluster locations and 50 replications per condition.
Figure 10 confirms the expected positive effect of relative cluster density on cluster growth. An increase of the relative cluster density from -0.5 to +0.5 shifts the endresult from universal defection in almost every simulation towards convergence on universal co-operation in the majority of runs. At the same time, there remains considerable variation between cluster positions in the level of co-operation attained that is not explained by differences in relative density.

To conclude, this analysis of the dynamics of reciprocity suggests that global characteristics of influence dynamics may be robust against variation in the grid structure. Broadly, the conditions of initial cluster size, neighbourhood size and actors' expectation level have the same qualitative effects in a rectangular cellular world than they have in an irregular grid. Such information may for instance be relevant for a "social planner", who is interested in fostering environmental co-operation and who has the means to "implant" in a defecting world clusters of initial co-operation. At the same time, such a social planner can learn more from an analysis based on an irregular grid. The analysis of the irregular grid highlights potentially important insights into the characteristics of locations that are particularly suitable as seedbeds for the propagation of co-operation. In particular, the prospects for co-operation to spread from an initially small cluster may improve, if a cluster location is chosen where the density of cells in the cluster is large relative to the density of cells around it. Clearly, these conclusions may change if influence dynamics with other characteristics are considered. However, it seems plausible that the main conclusion that irregular grids matter generalises to a broader class of influence dynamics.

Backward-looking Social Support in Irregular Worlds


In this section, we address the effects of grid structure on a migration dynamic. As substantive application, a model is used of the evolution of social support networks in which individuals face a co-operation problem in bilateral support relationships. The model assumes that actors are free to change support partners by migration to new locations in the cellular world. It draws on a somewhat adapted version of Hegselmann, (1998), (cf. Flache and Hegselmann 1999). In this paper, we will focus in particular on the backward-looking version of the model that has been developed by Flache and Hegselmann (1998, 1999). In this backward-looking model, actors may learn through a simple trial and error mechanism to form mutually co-operative relationships with their neighbours. At the same time, they use their experience with neighbours to evaluate whether they might gain from migration to new locations in the cellular world. Clearly, in the context of support relationships, it makes sense to assume that the attractiveness of a new location is not only affected by the expectation of co-operation with neighbours at this location. It also depends on the number of neighbours one can have in the present cell and in the new cell. Broadly, if actors have made the experience that mutual support is beneficial, they may expect to gain from maximising the number of neighbours with whom they exchange support. Conversely, if actors have negative experience with support relations, they might not care about the number of neighbours or even try to avoid locations with many possible relationships. This suggests that the grid structure may have profound effects on migration dynamics. To analyse these effects, we compare in the following the backward-looking migration dynamics on three types of grid structures, rectangular grids, hexagonal grids and irregular grids. In 4.2, we describe in more detail the backward-looking model of the evolution of social support networks and 4.13 presents results of the comparison of grid structures.

The backward-looking model

The basic building block of the support network is the dyadic exchange relationship between two actors, say ego and alter. We first describe the model of this exchange dyad and actors' decision making with respect to behaviour in a particular dyad. Subsequently, we turn to the model of partner selection that drives the migration process.

Backward-looking dyadic exchange in support relations
Flache and Hegselmann's original backward- looking model assumes that actors differ in their attractiveness as potential exchange partners. To concentrate on effects of the grid structure, we strongly simplified the model for the purposes of the present paper and assume that the population is homogeneous in the potential costs and benefits associated with the exchange of support.

The ongoing exchange between ego and alter is modelled as a repeated support game that consists of consecutive iterations of a constituent game. For simplicity, both actors have only two decision options in the constituent game, to provide help (Co-operate), and to not provide help (Defect). To further simplify, the model assumes that participants make these decisions simultaneously and independently[4]. The payoff of mutual defection, DD, provides the baseline outcome that yields a payoff of zero to both participants. In DD, actors neither receive help nor provide support. Actors gain one util from being supported in one iteration of the game, as compared to the baseline. At the same time, actors incur some costs if they provide help themselves. However, we assume that mutual support is collectively desirable, i.e. the costs of providing a unit of help are smaller than the benefits from receiving a unit of help. In particular, the costs are only 25% of the benefits in our simulations. With these assumptions, the constituent game of the repeated support game generates a 2 × 2 Prisoner's dilemma structure with the payoffs shown in Table 1.

Table 1: Payoffs of the constituent support game.
To model actors' backward-looking decision making in the repeated support game, we use the Bush-Mosteller (1955) stochastic learning algorithm that Macy (1991); (cf Flache and Macy 1996) has prominently applied for the analysis of co-operation in social dilemmas. Broadly, the algorithm implements two simple principles found in psychological research on learning behaviour. These are Thorndikes (1898) "law of effect" and Blackburn's (1936) "power law of practice". The law of effect posits that choices associated with good outcomes in the past are more likely to be repeated, while choices related to poor outcomes are more likely to be avoided. The power law of practice adds the assumption that the modification of action propensities tends to flatten out, the longer the learning process continues. More technically, the probability that actor i co-operates in a given period t of the dyadic support game is given by his propensity for co-operation, qi,C(t). Accordingly, i defects with probability qi,D(t) = 1 - qi,C(t). After the outcome of round t occurred, both players receive a reinforcement for the action they took. This reinforcement, r (xt) results from the difference between the payoff experienced in t, xt , and the aspiration level or reference point that actors hold, ρ. Reinforcements are scaled to values between -1 and +1, where the payoff that has the largest distance from the aspiration level generates the corresponding extreme value of this interval. If the payoff is exactly equal to the aspiration level, then the reinforcement is zero, while it is negative if the payoffs falls below the aspiration, and it is positive otherwise. For simplicity, we fix the aspiration level of actors at the midpoint of the payoff interval [-0.25,1.0] of Table 1, i.e.ρ = 0.375. Equation 2 formalises the corresponding calculation of the reinforcement that actors experience for a payoff xt.

The reinforcement affects choice propensities such that positive reinforcement increases the propensity for the action taken and decreases the propensity for the action that was not taken. Conversely, negative reinforcement decreases the propensity for the action taken, while it increases the propensity for the alternative. Formally, after an action X was taken and a payoff xt experienced in t, the new propensity for action X is


where l is the learning rate (0 <= l <= 1). The change in propensity for the alternative action Y that was not taken obtains from the constraint that propensities add up to one, i.e. qi,C(t+1)+qi,D(t+1)=1. With l close to zero, learning is very slow, while the model approaches a fast learning "win stay, lose shift" strategy with l = 1. Moreover, the terms q and (1 -q) ensure the power law of practice[5], i.e. propensity adjustments flatten out as propensities approach the extremes of the interval [0,1].
For the purpose of this paper, we are interested in a scenario where actors' can learn mutual co-operation in repeated interaction. Macy (1991) has demonstrated how the Bush Mosteller learning algorithm can generate mutual co-operation in a repeated Prisoner's dilemma game through "stochastic collusion". The crucial conditions for this are an aspiration that exceeds the payoff of mutual defection, and a high learning rate. Accordingly, we will use throughout the following a maximal learning rate of l = 1 and the aspiration level of qi,C(t) = 0.375. Figure 11 shows how these conditions allow stochastic collusion in a repeated dyadic support game with the payoffs of Table 1.

Figure 11: Change in propensities for co-operation in dyadic support game simulated with the Bush Mosteller stochastic learning algorithm and high learning rate l = 1.
Figure 11 shows how the learning process eventually leads actors to stabilise mutual co-operation after an initial period of instability. To explain, with an aspiration level of qi,C(t) = 0.375, CC is the only outcome that satisfies both players simultaneously. Moreover, CC reinforces both players' co-operation, because the associated payoff exceeds their aspiration level. However, Figure 11 assumes that initially both players randomise, that is: their propensities for co-operation are q = 0.5. Accordingly, at the outset of the simulation, the outcome CC occurs only with probability 0.25. As a consequence, frequent CD or DC outcomes lead initially at least one of the two players to reduce at some point her propensity for co-operation. Then, in about round 120, a series of mutual co-operation outcomes occurs that is long enough to eventually increase both players' propensities up to a level where defection is practically excluded.

For the analysis of effects of migration, the central property of the model of backward-looking dyadic co-operation is its sensitivity to timing. The longer two players interact, the higher are the chances that they eventually enter a phase of mutually reinforcing co-operation, leading to lock-in on CC. Clearly, migration may then exacerbate co-operation, because actors may leave their partners before lock-in occurs. In the following, we describe the model of the migration process.

Simultaneous support relations and partner selection in the cellular world
The model assumes that actors have independent support relations with every next neighbour in the cellular world[6]. Examples of next neighbour relationships in the rectangular and the irregular worlds are shown by Figure 2 above. To model simultaneous support relations with more than one neighbour, we assume that actors hold a generalised propensity to co-operate that they update after every new play they experienced. More precisely, actors are selected in every iteration of the simulation in random sequence to play one round of the support game with every next neighbour, again in random sequence. After every play, actors update their propensities for co-operation according to the outcome they just experienced.

Backward-looking partner selection is modelled with the assumption that in each period of the simulation, a random generator allocates migration options, such that every individual gets a migration option with an exogenously set probability m. We denote this probability the migration probability. Migration options can be used, but it is not obligatory. Migration is possible within a certain migration window, but only to vacant destination cells. The options are evaluated and/or used in a sequential order according to the results of a lottery. After that, a new period of the simulation starts. To define the boundaries of a migration window, we assume that it includes all cells within a certain network distance from the focal cell. Other than in the model of the previous section, network distance rather than euclidian distance is used here, because the size of a migration window reflects social distance rather than geographical distance from the present location to a new one. To be precise, network distance between two cells in the grid is defined as the smallest number of steps from one next neighbour to another that are needed to get from the focal cell to a target cell. For illustration, Figure 12 shows migration windows of different size in three different grid structures.

Figure 12: Migration windows with radius 3 (red) and 5 (yellow) around focal cell (black) in 3 different grid structures.
An actor who gets an option to migrate, evaluates all free social positions in his migration window relative to the present social position. He estimates the attractiveness of a new position on basis of his present assessment of the payoff that he attains in one interaction with one other player. This assessment is based on experience. Whenever i interacted with another player, he computes a weighted mean of the payoff he attained in this most recent interaction and of his previous assessment of the payoffs of an interaction with other players.[7] In this, actors have a decaying memory function. That is, the most recent payoff affects their assessment twice as much as the average of the payoffs attained in previous interactions.[8] Actors then use this assessment to evaluate every feasible new position. More precisely, they multiply the number of neighbours at the potential new location with the payoff they presently expect to attain in a single interaction. The basic evaluation rule is then simply that actors compute their location payoff, i.e. the sum of the payoffs attained in the most recent interactions with all present neighbours, and compare this payoff to their evaluation of every feasible new location. Subsequently, actors move to the best new location if at least one of two conditions is satisfied. The first condition is that the best location is better than their present one. The second condition is that actors are dissatisfied with their present location, i.e. the present location payoff falls below an aspiration level that actors hold with respect to the payoff at their location. To distinguish this aspiration from the one used in the co-operation decision, we denote it the location aspiration. The assumption of a location aspiration introduces the notion of risk seeking behaviour for actors who are in a dissatisfactory location. Actors' location aspiration corresponds to a situation, where they experience mutual co-operation with half the average number of neighbours they could have in the given grid structure. In other words, in a rectangular grid actors expect a location payoff of at least 2*0.75 = 1.5, while it is exactly 3*0.75 = 2.25 in a hexagonal grid structure, and approximately that number in an irregular grid.


To study effects of the grid structure on the migration dynamics, a very simple scenario is used with a single homogenous population of 16 actors. Table 2 summarises the main assumptions of the simulation.

Table 2: Main assumptions of simulation of migration dynamics.
The simulations show how grid structure affects the interplay of co-operation decision and migration decisions. For every grid structure, we ran 10 simulations with 10000 iterations per simulation. Figure 13 charts the average dynamics of four outcome variables of the process. The migration rate is the fraction of migration options that are used per iteration of the simulation. The satisfaction rate represents the fraction of actors who are satisfied with the payoff at their present location. The level of clustering measures the degree to which actors "flock together" with other members of the population, i.e. the average fraction of non-empty neighbour cells across the population. A clustering rate of 0 indicates that actors have only empty neighbour cells, whereas all members have only occupied neighbour cells with a clustering rate of 1.

Figure 13: Dynamics of co-operation and migration in three different grid structures.
Figure 13 demonstrates that the basic pattern is the same in all three grid structures. In the course of the simulation, all individuals gradually develop a high propensity to co-operate. As a consequence, actors begin to experience that an empty neighbour cell is less attractive than an occupied one. Accordingly, with rising co-operation propensity, actors increasingly strive to occupy cells with a maximal number of neighbours, exemplified by the increasing level of clustering in the population. At the same time, the migration rate declines and satisfaction soars, because more and more actors find locations at which they attain a payoff that exceeds their aspiration and from which no better positions can be reached.

Figure 13 also highlights remarkable differences between the grids, despite the structural similarity of the dynamics.

A comparison of possible cluster structures between the grids explains the differences. For illustration, Figure 14 shows 3 × 3 clusters in all three grid structures. The figure shows why migration rates are highest in the hexagonal grid. Broadly, the reason is that the chances for random emergence of a stable cluster are lowest in the hexagonal grid and are highest in the rectangular grid. A cluster can be stable, when every member of it is satisfied with his present location. In the hexagonal grid, at least 7 actors are needed to generate a stable cluster, i.e. a cluster in which every member has at least three neighbours. The cluster in Figure 14 contains 9 actors of which 2 are dissatisfied, assuming full co-operation (q = 1). To attain a larger cluster than 7 with universal satisfaction, a tenth actor needs to be added in the position at the top of the 9-cluster. Further stable clusters can occur in the hexagonal grid with 13, 16 etc. members. In the rectangular grid, only 4 actors need to co-ordinate positions in order to form a minimal stable cluster, because here only 2 neighbours are needed to satisfy every member. Moreover, in the rectangular grid stable clusters can also form with 6, 8, 10 etc. members. Clearly, this suggests that random migration can generate stable clusters much quicker in the rectangular grid than in the hexagonal grid. Accordingly, migration stabilises later and at a higher level in the hexagonal grid. Finally, this also explains why it takes much longer in the hexagonal grid before co-operation propensities converge on q = 1. The reason is that actors spend less time in repeated interaction with their neighbours, due to continuing migration. Accordingly, dyadic relations are often disrupted before the interactants could lock into mutual co-operation.

Figure 14: Structures of 3 × 3 clusters in three different grids.
The irregular grid can be seen as a mixture of the features of rectangular and hexagonal grid. Like in the hexagonal grid, three neighbours are needed to satisfy every member of a cluster, because the average number of neighbour cells in the grid is 6. Accordingly, it is harder for stable clusters to emerge in the irregular grid as compared to the rectangular one. At the same time, local variation in the grid structure facilitates stabilisation in certain areas of the world. This is illustrated by the comparison of a "centralised" and a "decentralised" cluster in the irregular grid in Figure 14. The decentralised cluster is stable, while the centralised cluster has some positions with only two occupied neighbour cells. Inspection of the dynamics of Figure 10 suggests that eventually, the migration process "finds" regions like the decentralised cluster. Accordingly, there is less migration in the irregular grid than in the hexagonal grid, but it takes about the same time before migration rates stabilise.

To summarise, the migration dynamics analysed in this section suggest that qualitative features of the dynamics may be robust against variation of the grid structure. At the same time, it turns out that migration dynamics are sensitive both to the number of neighbour cells in a grid and local variation in the number of neighbour cells. Clearly, this conclusion generalises to other migration dynamics, like Schelling's analysis of neighbourhood segregation or Sakoda's model of group formation. In both models, actors strive to find positions in the grid, where a certain population distribution in the neighbourhood can be realised. Clearly, with a larger number of neighbour cells, it may be harder to attain this distribution by chance. At the same time, variation in local structure may allow that dynamics eventually "find" stable configurations in irregular grids, where they might fail to converge in hexagonal grids.


Three decades of CA-modelling in the social sciences have shown that the cellular framework is a useful tool to explore the relationship between micro assumptions and macro outcomes in social dynamics. At the same time, there is virtually no knowledge about the robustness of the results of CA-modelling against variation in the standard assumption of a rectangular grid structure. This led us to develop tools that allow to use both rectangular, other regular and even irregular grids within one and the same CA-modelling framework. In this paper, we applied these tools to two applications from our own work that are typical for the two broad classes of dynamics investigated in CA research, migration dynamics and influence dynamics. Our results support the following conclusions.

This suggests the general conclusion that the qualitative results that have been found in three decades of CA modelling in social sciences may be widely robust against changes of the underlying standard assumption of rectangular grids.

Of course, we are aware that the regularity of the grid structure is but one of a number of idealisations used in CA-modelling. For example, it has been discussed controversially whether and under what conditions a simple influence dynamics similar to our model of spatial collective action can be robust with respect to variation in simultaneous vs. sequential updating of strategy choices (Huberman and Glance 1993, Nowak et. al. 1994). In our own work, we have found effects of a discrete vs. a continuous opinion space and discrete vs. continuous time on the outcomes of opinion formation in a cellular world (Hegselmann et. al 2000). Finally, recent models of the dynamics of social networks (Doreian and Stokman 1996, Zeggelink 1994, 1996) raise the issue what consequences may arise if the structure of a CA grid is not static, as always assumed in CA-modelling, but neighbourhood relationships change as a consequence of individual behavior. These possibilities indicate that researchers should be aware of various potential sensitivities of the substantive conclusions drawn from CA-models. Our results raise confidence that substantive insights may often not hinge critically on the idealisation of rectangular grids that dominates the visual appearance of CA- applications in the social sciences since Schelling (1971) and Sakoda (1971) introduced "checkerboard" models.

We also found that irregular grids open up possibilities for new interesting hypotheses and we showed that at least certain relevant features of CA dynamics may be sensitive to local variation in the number of neighbours within a grid. Of course, we are aware that our study relies on only two specific applications. However, we also began to extend these robustness analyses to more CA models, in particular to classical applications, like Schelling's neighbourhood segregation model, or Sakoda's analysis of group formation (Flache and Hegselmann 2000). These results also support our general conclusion. At the same time, we feel that more robustness tests are necessary to obtain better insight in the characteristics of dynamics that shape robustness to variation in the grid structure. We encourage other researchers to join into this effort and to make use of the tools we provide on our website.

* Acknowledgements

This research has mostly been conducted within a project on modelling the dynamics of social dilemma situations, financed by the German Science foundation DFG, grant no. HE-1412/4-1. Further elaboration of the material and compilation of the manuscript has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences (KNAW) granted to the first author.

* Notes

1Both the model of Schelling and the model of Sakoda are examples of what we call "migration dynamics". These models assume that "actors" can change their location ("cell") in a CA. In physics applications, this class of models is referred to as a "lattice dynamics" and is distinguished from cellular automata. For consistence with the social simulation literature, we follow the established terminology in our field and classify models of migration dynamics as cellular automata.

2For the mathematical details see Okabe et al. (1992). Details of our implementation of Voronoi-diagrams and some sample data sets can be found on our website.

3With exception of the four corner members of the cluster, who change into defectors, because they see only 25% co-operation around them, less than their expectation level E. However, the conversion of these four cells is more than outweighed by the changes from defection to co-operation.

4With this assumption, the support game used here is different from the support game used in Hegselmann and Flache (1998). The main difference is that bilateral help is always possible in the game we use here, though the degree varies for different neediness class combinations. By contrast, the support game of Hegselmann and Flache (1998) allows in each period only unilateral help. As a consequence, that game imposes imperfect information which greatly complicates the game theoretical analysis. Obviously, there are different plausible approaches to model what in the daily life is simply called mutual help.

5This implementation of the learning dynamics is different from an alternative formalization of the "power law of practice" that was proposed by Erev et al (1999). Flache and Macy (2001) showed that for parameter values corresponding to those used in the present paper, both models generate very similar behaviour. However, the authors also reveal subtle but important differences that occur in other regions of the parameter space, in particular when actors’ aspiration levels are high or their learning rates are low.

6To recall, we define a next neighbour as a cell that has a common border with the focal cell. For the rectangular world, this imposes a von Neumann neighborhood structure.

7Simultaneously, the opponent adapts her corresponding attractiveness assessment. The sequence in which dyads are selected is randomly chosen.

8More precisely, we assume that a particular player i assesses the attractiveness payoff attained in interactions with others after the t'th encounter as: . The symbol uit indicates the payoff attained at the t'th encounter and ai,t-1 is the estimate of others' attractiveness before the t'th encounter occurred. The parameter d in this function indicates the rate of decay . Only the most recent payoff is taken into account, when d = 0, while d = 1 indicates that the attractiveness assessment is a weighted mean of the payoffs i attained in all previous encounters. In the simulations reported here, we assumed d = 0.5. Note that this function guarantees that ait is always within the range of valid payoffs [-0.25,1].

* References

AXELROD, R. 1984. The Evolution of Cooperation. New York: Basic Books.

BLACKBURN, J.M. 1936. "Acquisition of Skill: An Analysis of Learning Curves". IHRB Report 73. Reference taken from Erev, I. and A.E. Roth. 1998. "Predicting how People play Games: Reinforcement Learning in Experimental Games with Unique, Mixed Strategy Equilibria." American Economic Review 88(4):848-879.

BUSH, R. R., Mosteller, F. 1955. Stochastic models for learning. New York: Wiley.

DOREIAN, P., F. N. Stokman (eds). 1996. The Evolution of Social Networks. Amsterdam: Gordon and Breach.

EREV, I., Y. Bereby-Meyer and A.E. Roth. 1999. "The effect of adding a constant to all payoffs: experimental investigation , and implications for reinforcement learning models." Journal of Economic Behavior and Organization 39: 111-128.

FLACHE, A., Macy, M. W. 1996. "The Weakness of Strong Ties: Collective action failure in a highly cohesive group". Journal of Mathematical Sociology 21, 3-28.

FLACHE, A, Hegselmann, R. 1998. "Rational vs. Adaptive Egoism in Support Networks: How different micro foundations shape different macro hypotheses". Pp. 261-275 in: Leinfellner, W. & Köhler, E. (eds.): Game Theory, Experience, Rationality. Foundations of Social Sciences, Economics and Ethics. In Honor of John C. Harsanyi [Yearbook of the Institute Vienna Circle 5]. Dordrecht: Kluver.

FLACHE, A, Hegselmann, R. 1999. "Rationality vs. Learning in the Evolution of Solidarity Networks: A Theoretical Comparison". Computational and Mathematical Organization Theory 5:2:97-127.

FLACHE, Hegselmann, R. 2000. Abschlußbericht des DFG-Projektes "Dynamik sozialer Dilemma-Situationen". (Final research report of the DFG-Project "Dynamics of social dilemma situations"). University of Bayreuth, Department of Philosophie. URL (German text): <http://www.uni-bayreuth.de/departments/philosophie/deutsch/dfg/index.html>

Flache, A. and M. W. Macy. 2001. "Stochastic Collusion and the Power Law of Learning." ISCORE Working Paper No. 189. Utrecht University: Institute for the Study of Cooperative Relations.

FRIEDMAN, J.W. 1971. "A Non-Co-operative Equilibrium for Supergames". Review of Economic Studies 38:1-12.

FRIEDMAN, J.W (1986) Game Theory with Applications to Economics, 2nd ed. 1991. Oxford UP, Cambridge.

HEIDER, F. 1946. "Attitudes and Cognitive Organization". Journal of Psychology 21:107-112.

HEGSELMANN, R. 1996. "Cellular Automata in the Social Sciences - perspectives, restrictions, and artefacts". Pp. , 209-234 in: Hegselmann, R., K.G. Troitzsch, U. Mueller (eds.): Modelling and Simulation in the Social Sciences from the Philosophy of Science Point of View (Theory and Decision Library). Dordrecht: Kluver.

HEGSELMANN, R. 1998. "Modelling Social Dynamics by Cellular Automata". Pp. 37-64 in: Liebrand, W. B. G., A. Nowak, R. Hegselmann, R. (eds.): Computer Modelling and the Study of Dynamical Social Processes. London: Sage.

HEGSELMANN, R., A. Flache 1998. "Understanding Complex Social Dynamics: A Plea For Cellular Automata Based Modelling". In: Journal of Artificial Societies and Social Simulation 1: <http://jasss.soc.surrey.ac.uk/1/3/1.html>

HEGSELMANN, R., A. FLACHE, V. Möller 2000. "Cellular Automata as a Modelling Tool: Solidarity and Opinion Formation". Pp. 151-178 in: Suleiman, R., K.G. Troitzsch, N. Gilbert (eds.). Tools and Techniques for Social Science Simulation. Heidelberg: Physica.

HUBERMAN, B.A., N.S. Glance, 1993. Proceedings of the National Academy of Sciences U.S.A 90:7716-7718.

LATANéâ, B., A. Nowak. 1997. "Self-Organizing Social Systems: Necessary and sufficient conditions for the emergence of clustering, consolidation and continuing diversity". Pp. 43-74 in: Barnet, G. & Boster, F. (eds.): Progress in communication science: Persuasion, Ablex, Norwood, NJ.

MACY, M. W. 1991. "Learning to Cooperate: Stochastic and tacit collusion in social exchange". American Journal of Sociology 97, 808-843.

NOWAK, M. A., R.M. May, 1993. "The Spatial Dilemmas of Evolution". International Journal of Bifurcation and Chaos 3: 35-78.

NOWAK, M., S. Bonhoeffer, R.M. MAY, 1994. "Spatial Games and the Maintenance of cooperation". Proceedings of the National Academy of Sciences U.S.A. 91:4877-4881.

OLSON, M. Jr. 1965. The Logic of Collective Action. Cambridge, Mass.: Harvard University Press.

OKABE, A., B. Boots, K. Sugihara, 1992. Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. Chichester: Wiley & Sons.

SAKODA, J.M. 1971. "The Checkerboard Model of Social Interaction". Journal of Mathematical Sociology 1: 119-132.

SCHELLING, T. 1971. "Dynamic Models of Segregation". Journal of Mathematical Sociology 1: 143-186.

TAYLOR, M. 1987. The Possibility of Cooperation (revised edition of: Anarchy and Cooperation, 1976). London:Wiley & Sons.

THORNDIKE, E.L. 1898. "Animal Intelligence. An Experimental Study of the Associative Processes in Animals". Psychological Monographs 2.8.

UPTON, G.J.G., B. Fingleton, 1985. Spatial Data Analysis by Example. Vol. 98. New York: Wiley.

ZEGGELINK, E 1996. "Evolving friendship networks: An individual orientied approach implementing similarity". Social Networks 17:83-110.

ZEGGELINK, E 1994. "Dynamics of structure: An individual orientied approach". Social Networks 16:295- 333.


ButtonReturn to Contents of this issue

© Copyright Journal of Artificial Societies and Social Simulation, 2001