Spatial structure

In evolutionary game theory, the spatial structure of a game can be as important in determining the evolutionary success of a given strategy as is the strategy itself [1]. This is intuitive if we consider that strategies do not work in a vacuum: An agent’s payoff is a function of both its strategy and the context in which that strategy was executed. In light of this, a brief discussion concerning the role of spatial structure in simulations is warranted. Additionally, several common network types (random graphs, small-world and scale-free networks), as well as network properties (degree, clustering and path length) are considered. Readers are also encouraged to consult Albert and Barabási’s review, as it forms the basis for the latter summary [2].

To understand what is meant by spatial structure, something should first be said about what it means to lack one. It is interesting to note that the earliest applications of evolutionary game theory often favored a non-spatial approach [3], and that many continue to do so to this day. In such settings, populations are treated as inviscid (free-mixing), meaning that any agent can potentially pair with any other agent in an interaction; agents are, in other words, inherently unconstrained in their pairings. This extends to reproduction as well: Because new agents are not “placed” anywhere in particular (e.g., next to their parents), reproducing successfully has a more quantitative rather than qualitative effect on the population (e.g., there are more agents of your type, but you are not helping to generate a homogeneous neighborhood).

Reasons for preferring a non-spatial approach may be numerous, but one of the most apparent is the relative simplicity of analysis. Often, only the strategy proportions and the payoff matrix, which describes how fitness changes when these strategies interact, need be considered in order to predict population trends [4]. Nevertheless, spatial structure remains interesting both due to its potentially strong effect, as well as for theoretical reasons. Psychological research, for instance, has shown evidence for adaptive biases that lead to the formation of particular social networks, and it is often argued that such biases are a product of evolution [5]. Therefore, if we wish to use evolutionary game theory to reason about behavior, understanding spatial structure may, in certain cases, be a necessary first step.

At its simplest, spatial structure is a set of constraints on how agents interact. These constraints are typically described in terms of a graph, where agents form the vertices (i.e., nodes) of the graph, and potential interactions are represented by the edges connecting them. The lack of an edge indicates that the given agents cannot pair up for an interaction, and thus a simulation which does not impose a spatial structure may be described as a complete (i.e., fully-connected) graph. When spatial position matters, reproduction is also affected: The researcher must decide where an offspring is placed (e.g., next to the parent, far from the parent, at random?) – and even this decision may have a significant effect. Typically, the same spatial structure is applied to both interactions and reproduction.

To describe how graphs vary, several key terms must be defined. The first of these is degree, represented by k. The degree of a vertex is the number of connections it forms, and as such represents an agent’s connectivity. The higher the degree, the more potential partners the agent has for interaction, and the more spaces it has to potentially place an offspring. In most cases, it is not the degree of a given vertex, but the average degree or the degree distribution of the whole graph that is of interest. Next, clustering, as captured by a clustering coefficient, reflects the extent to which local, highly interconnected groups form. Another way to characterize this is as a measure of agent “cliquishness”. Finally, path length is the number of edges that must be traversed to move from one particular vertex to another. A low average path length suggests that long distance connections are common, whereas a high average path length implies that connections tend to be strongly localized.

Unfortunately, real-world networks often have sophisticated topologies that lack clear design principles. As a result, it is commonly thought that the simplest way to represent such networks is to treat them as random graphs. The most straightforward approach is described by the Erdõs-Rényi model: Here, we start with an empty graph, then consider every pair of points, connecting each with some probability p. The result is a graph of n vertices, degree k and approximately pn(n – 1)/2 randomly distributed edges. Though the underlying principle is simple, in practice, such graphs are more complicated than they first appear. For instance, there are threshold phenomena whereby, as p varies, various properties (e.g., every pair of vertices being connected at least indirectly) emerge very suddenly, yet with remarkable consistency. Variations on this approach are abundant and frequently used [2].

Though the random graph paradigm remains common, others have emerged as well, such as a cross between random graphs and highly clustered regular lattices: the small-world network. These networks are defined by a low average path length between any pair of vertices, a concept that was famously captured by Stanley Milgram’s “six degrees of separation” experiment, where he argued that, on average, any two individuals in the United States are only separated by approximately six social relationships. The implications of this property are that, while local, highly connected groupings are possible, long distance connections make it easy to move anywhere on the graph. This is worth noting, since virtually all real-world networks have a higher clustering coefficient than random graphs do, yet small-world properties abound; examples include various social networks and the Internet. Nevertheless, these properties in and of themselves are not sufficient to specify any particular organizational structure, and, in fact, even random graphs may be regarded as a type of small-world network [2].

The third and final paradigm is the scale-free network. Whereas the degree distribution of a random network is a Poisson distribution, scale-free networks are defined by the fact that their degree distribution has a power-law tail. In other words, vertices with very high numbers of edges are uncommon, and such vertices tend to form “hubs” around which less-connected vertices then gather. Unsurprisingly, scale-free networks have small-world properties, since traversing from any vertex to another is often as simple as connecting to the nearest hub and then using this to access a hub near the target vertex. Like small-world networks, scale-free networks are also quite prevalent across a variety of contexts, ranging from the Internet to metabolic networks [2].

One spatial structure that has proven particularly useful from the point of view of evolutionary game theory is a variation on the random graph: the random k-regular graph. Although random, in that the vertices are randomly connected, these are also regular, in that each vertex has the same degree k. This offers several advantages: First, the random nature of the graph means that no deliberate assumptions about properties such as clustering or average path length are made, which makes them easier to justify at a theoretical level (e.g., if we don’t know what a particular network should look like, this is a relatively neutral place to start). Second, the graph’s regularity means that agents always have an equal number of neighbors, and thus an equal number of interactions and consistent structural constraints on reproductive potential. This precludes scenarios where a more highly connected agent receives higher or lower fitness payoffs, or reproduces more or less, simply as a result of its level of connectivity, rather than the effectiveness of its strategy. One final advantage is that Ohtsuki and Nowak have proposed a means by which more traditional ways of reasoning about non-spatial models may be applied to random k-regular graphs [6]. This has the potential to make games on such graphs more mathematically tractable than other models.

Creating a random k-regular graph is theoretically quite straightforward: We simply consider the entire possible set of graphs with n vertices and k degree, and then pick a graph at random. The question of how this is done in practice is more difficult however, since computational constraints almost always necessitate the use of a faster algorithm. The practical considerations of generating such graphs will be discussed in a future entry.

References

1. Killingback, T., & Doebeli, M. (1996). Spatial Evolutionary Game Theory: Hawks and Doves Revisited. Proceedings of the Royal Society of London. Series B: Biological Sciences, 263(1374), 1135–1144.
2. Reka Albert, & Albert-Laszlo Barabasi (2002). Statistical mechanics of complex networks Reviews of Modern Physics, 74 (1), 47-97 arXiv: cond-mat/0106096v1
3. Smith, J. M. (1982). Evolution and the theory of games. Cambridge University Press.
4. Nowak, M. A. (2006). Evolutionary dynamics: exploring the equations of life. Harvard University Press.
5. Henrich, J., & Broesch, J. (2011). On the nature of cultural transmission networks: evidence from Fijian villages for adaptive learning biases. Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences, 366(1567), 1139–1148.
6. Ohtsuki, H., & Nowak, M. A. (2006). The replicator equation on graphs. Journal of Theoretical Biology, 243(1), 86–97.