Quasi-magical thinking and the public good

Cooperation is a puzzle because it is not obvious why cooperation, which is good for the group, is so common, despite the fact that defection is often best for the individual. Though we tend to view this issue through the lens of the prisoner’s dilemma, Artem recently pointed me to a paper by Joanna Masel, a mathematical biologist at Stanford, focusing on the public goods game [1]. In this game, each player is given 20 tokens and chooses how many of these they wish to contribute to the common pool. Once players have made their decisions, the pool is multiplied by some factor m (where mn > 1) and the pool is distributed equally back to all players. To optimize the group’s payoff, players should take advantage of the pool’s multiplicative effects by contributing all of their tokens. However, because a player’s share does not depend on the size of their contribution, it is easy to see that this is not the best individual strategy (Nash equilibrium). By contributing nothing to the common pool, a player gets a share of the pool in addition to keeping all of the tokens they initially received. This conflict captures the puzzle of cooperation, which in this case is: Why do human participants routinely contribute about half of their funds, if never contributing is individually optimal?
Read more of this post

Habitual selfish agents and rationality

Many game theoretical studies of cooperation have focused on the trade-off between selfish behavior that optimizes the individual, versus cooperative behavior that optimizes the whole. Because this trade-off is inherent to prisoner’s dilemma, this game has been a preferred method for studying mechanisms that encourage cooperation among selfish agents. Davies et al. [1] adopt a different framework, however: that of a coordination/anti-coordination game. Note that (anti-)coordination games do not differ from the general class of cooperate-defect games that Artem discussed previously, and would fall into the X and Y games he covered at the end of the post.

To get a flavor of Davies et al.’s game, imagine that there is a social network of scientists, each of which is either (symmetrically) compatible or incompatible with each of their peers. Compatibility results in good collaborations, while incompatibility leads to shoddy research that benefits no one. Collaborations occur every night in one of two bars. Initially, scientists pick a bar randomly. Every night after that, each scientist decides in random order whether to stick with the bar they visited the previous night, or whether to switch bars to meet a greater number of compatible researchers. Because payoffs are symmetric, a stable configuration is quickly reached where no one wants to switch bars. While this arrangement represents a local maximum, in that each scientist makes the selfishly rational choice to stay, it generally fails to maximize the group’s total productivity. Thus, much as in the prisoner’s dilemma, rational agents have no motivation to unilaterally switch bars in the hopes that others follow suit, even though such selfishness ultimately results in lower payoffs for the whole group.

Davies et al. investigate how to tweak each agent’s local strategy (i.e., no knowledge of/concern for the global utility) such that agents remain selfishly rational in some sense, yet still optimize the global utility function. Their answer comes in the form of habituation: agents develop a preference for whichever agents they are currently paired with. Agents, rather than basing their behavior on true utility (a function of the number of agents they are coordinated with), instead base their behavior on perceived utility (a sum of their true utility and their preference for the agents they are interacting with). Because this enables agents to occasionally sacrifice some of their true utility in order to pursue a higher perceived utility (i.e., to switch to a bar with an initially lower payoff), the population is ultimately able to reliably converge to the global maximum. In brief, habituation acts by reinforcing local maxima which, in cases where the global function is a superposition of numerous pairwise interactions, tend to overlap with the global maximum, making it a strong and reliably reachable attractor. (See slides by Peter Helfer, who presented this paper at the EGT Reading Group 38, for a nice overview.)

The model’s workings and results aside, there are interesting questions to ask as to what habituation represents in this context. Artem has previously posted about our interest in the dissociation between objective and subjective rationality. At the heart of this issue is the question of whether we can explain certain examples of seemingly irrational behavior within the framework of selfish rationality. To do so, we can appeal to the notion of bounded rationality: agents are not omniscient and must rely on imperfect information to make their decisions. If the imperfection lies in what payoffs the agents think they are getting (i.e., what game they think they are playing), then we may have a straightforward way of accounting for deviations from objective rationality: the behavior is a result of rationality being applied subjectively, by a deluded agent.

For a loose analogy, consider the case of the missionary. From the point of view of an atheist, a Christian travelling to Africa and doing volunteer work there seems highly altruistic, as he is incurring a high cost and deriving few tangible benefits. At first blush, such behavior seems difficult to explain on the basis of selfish rationality. But consider things from the missionary’s point of view. If the reward for selflessness is an eternity in paradise and the alternative is an eternity of damnation, then becoming a missionary yields the best possible payoff. In short, if the world (or game) is what the missionary believes it to be, then the behavior is selfishly rational after all, rather than purely altruistic.

Davies et al. make a similar point. They observe that, though habituation constitutes a deviation from objective rationality, these agents are still playing rationally—they just happen to be playing a different game from the real one. In other words, behaviors are still selected to maximize utility; it’s just that their perceived utility (as defined by the agent) deviates from their true utility (as defined by the game). To return to the notion of bounded rationality, agent “irrationality” here is explainable as a deficiency in the agent’s knowledge of the game, rather than in its decision-making capacities.

So how do we make sense of habituation? While Davies et al. justify it as a simple biasing mechanism worthy of investigation in adaptive networks, it is not altogether clear what this implies for psychology. On one hand, if such cognitive biases are broadly effective at optimizing cooperative behavior, then it is plausible that they evolved, or are commonly adopted through learning. On the other hand, it is difficult to judge whether such a bias is useful in cooperative behavior beyond the present context. Here, it solves the specific problem of the population’s search for an optimal arrangement stalling in local maxima. This is a crucial point, as the goal here (optimizing global payoffs in this coordination/anti-coordination game) is more a problem of constraint satisfaction than of replacing selfish behavior with cooperation. To sum up, we should not approach habituation and its consequences as if it solves the same problem that we face in the prisoner’s dilemma.

References

  1. Davies, A., Watson, R., Mills, R., Buckley, C., & Noble, J. (2011). “If You Can’t Be With the One You Love, Love the One You’re With”: How Individual Habituation of Agent Interactions Improves Global Utility Artificial Life, 17 (3), 167-181 DOI: 10.1162/artl_a_00030

Generating random k-regular graphs

In a previous post, I gave a brief overview of the role of spatial structure in evolutionary game theory. Along with an explanation of what it means for an agent-based simulation to have such structure, several notable types of networks were introduced, including small-world and scale-free networks, as well as random graphs. At the time, random k-regular graphs were singled out as being of particular practical interest to modelers. Consequently, I would now like to touch on some of the practical considerations involved in generating such graphs. Recall that, in our particular case, a graph’s vertices may be thought to represent agents, whereas the graph’s edges characterize the social or reproductive connections between them.

A random k-regular graph is a set of n vertices randomly connected with k edges incident on each vertex. This specification is rather straightforward, as is the naive approach to generating such a graph: In theory, we must simply consider all possible graphs with n vertices and k degree, and then select one of them at random. Unfortunately, the space of possible k-regular graphs is so large that this approach could never work in practice. As years of research have now shown [1], generating a random k-regular graph by other means is also no trivial task. A variety of algorithms have emerged as a result.

The most popular method to date was first proposed by Bollobás [2], and is called the pairing model (though it is also sometimes referred to as the configuration model). The algorithm itself is simple:

  1. Begin with a set of n vertices.
  2. Create a new set of nk points, distributing them across n buckets, such that each bucket contains points.
  3. Take each point and pair it randomly with another one, until ½nk pairs are obtained (i.e., a perfect matching).
  4. Collapse the points, so that each bucket (and thus the points it contains) maps onto a single vertex of the original graph. Retain all edges between points as the edges of the corresponding vertices.
  5. Check if the resulting graph is simple. That is to say, make sure that none of the vertices have loops (i.e., self-connections) or multiple edges (i.e., more than one connection to the same vertex). If the graph is not simple, restart.

There are several limitations to this algorithm. The first of these is that nk must be an even number, a requirement that is easily satisfied. The second and more interesting limitation is the need to retain only simple graphs. This is because, if we allow loops or multiple edges, graphs are no longer generated uniformly at random [1], and the randomization process becomes biased . Luckily, in evolutionary game theory, we are typically quite happy with this constraint and, in fact, often deliberately exclude the possibility of self-connections or parallel connections to the same agent. The final drawback is brought about by the occasional need for a restart. Specifically, asgrows, the probability of obtaining a non-simple graph rises as well, eventually making applying this algorithm impractical. Luckily, it has been shown that so long as is a smaller constant, this limitation is of no great concern [1]. Other algorithms that bypass this third limitation have been proposed [3], though they come with a notable drawback: Rather than generating a uniform random regular graph, they typically only generate an asymptotically uniform one. In light of this, there are good reasons for preferring the pairing model, so long as exceptionally large and highly-connected graph structures are not required.

Though the pairing model algorithm is easy to implement, a brief search of the Matlab Central File Exchange reveals that a ready-made implementation is already available for Matlab users. Using it is as simple as loading createRandRegGraph.m, then calling the createRandRegGraph function, using and k as parameters, respectively. The output of this function is an adjacency matrix, using a sparse matrix representation, though this is readily converted to a standard adjacency matrix by applying the full function. For example, entering full(createRandRegGraph(4, 2)); into the command window yields an adjacency matrix that describes a 4 vertex graph of degree 2, such as this one:

\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}

Using a random k-regular graph as the basis for your simulation’s spatial structure, therefore, is as simple as incorporating the output of this function into your work.

References

  1. N. Wormald, Models of random regular graphs. Surveys in combinatorics, 1999 (Canterbury), 239-298, London Math. Soc. Lecture Note Ser., 267, Cambridge Univ. Press, Cambridge, 1999.
  2. B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 (1980), no. 4, 311-316.
  3. Kim, J. H., & Vu, V. H. (2003). Generating random regular graphs. Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, STOC  ’03 (pp. 213–222). New York, NY, USA: ACM.

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 Sciences263(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 Sciences366(1567), 1139–1148.
  6. Ohtsuki, H., & Nowak, M. A. (2006). The replicator equation on graphs. Journal of Theoretical Biology243(1), 86–97.
Follow

Get every new post delivered to your Inbox.

Join 2,268 other followers