Game theory, meet cellular automaton

The inventor of game theoryWikipedia, probably also one of the greatest mathematicians of the 20th century, was a rather astounding character named John Von NeumannWikipedia. When he wasn’t throwing fabulous parties in Princeton or working on the atomic bomb, Von Neumann was laying some of the groundwork for the science of the late 20th century. Among his many creations was one of the first electronic digital computers, and associated with it the stored-program architecture that still underlies computers today.

A slightly less well known creation of his was the so-called cellular automatonmathworld.wolfram.com. Something of an alter ego to the digital computer, the cellular automaton is a distributed computational device composed of an array of many simple processors instead of one central and powerful processorWikipedia, as in the modern computer. Unlike Neumann’s other ideas, which continued to flourish, cellular automata fell into obscurity until the late 70s, when they experienced something of a renaissance after the workwww.stephenwolfram.com of Stephen Wolfram (who happens to be the CEO where I work).

More recently, a strange blend of these two ideas has arisen in the guise of rather long-winded spatial evolutionary game theoryadsabs.harvard.edu. Various academics have exploredarxiv.org what happens when, instead of the disembodied entities of traditional game theory (who one imagines lurking in imaginary war rooms plotting nuclear destructionwww.imdb.com), the game players are embodied agents situated in physical space on a grid or lattice, interacting with their neighbors.

It turns out that this can make a huge difference to the dynamics of such games. For example, in the traditional game of Prisoner’s DilemmaWikipedia, the only evolutionarily stable strategy (a strategy that a group of agents can play without being undermined by the appearance of mutants in their midst) is for every player to defect — in other words, a lose-lose situation where everyone mistrusts everyone and we are all unhappy. This is nature red in tooth and claw, pre-LeviathanWikipedia.

However, when we consider that these agents can be on a grid, and can, so to speak, huddle together for comfort, we notice that “tribes” of co-operators can form that offset the attacks from defectors on all sides by forming many positive relationships amongst themselves (see pictures below, the top panel is where the co-operators (blue) have successfully fought off invaders, in the bottom not so much). In fact, this point gets to the heart of one of the puzzles of evolutionary biology: why altruism existsplato.stanford.edu and how it evolved.

This last result was discovered only recently with the help of computer experiments, and there are sure to be many such discoveries waiting to be made in the field of evolutionary spatial game theory. To this end (yup, all of this post so far has been background — it links up too beautifully to not mention the history), I’ve been working on a software library to allow experiments in ESGT to be conducted elegantly and efficiently. To leave you with a taste of what such experiments to look like, here is an animation of the game of Rock Paper Scissors being played on grid (at various ’temperatures’, or degrees of randomness):

I’ll post more such videos in the future as I do further experiments, and hopefully delve a little more into the details of the science that is going on. If you’re interested in the code and seeing some more examples, or even playing around with it yourself if you have a copy of Mathematica, you can visit the project on GitHubgithub.com.

Long live spatial game theory!