Short history of iterated prisoner’s dilemma tournaments

Nineteen Eighty — if I had to pick the year that computational modeling invaded evolutionary game theory then that would be it. In March, 1980 — exactly thirty-five years ago — was when Robert Axelrod, a professor of political science at University of Michigan, published the results of his first tournament for iterated prisoner’s dilemma in the Journal of Conflict Resolution. Game theory experts, especially those specializing in Prisoner’s dilemma, from the disciplines of psychology, political science, economics, sociology, and mathematics submitted 14 FORTRAN programs to compete in a round-robin tournament coded by Axelrod and his research assistant Jeff Pynnonen. If you want to relive these early days of evolutionary game theory but have forgotten FORTRAN and only speak Python then I recommend submitting a strategy to an analogous tournament by Vincent Knight on GitHub. But before I tell you more about submitting, dear reader, I want to celebrate the anniversary of Axelrod’s paper by sharing more about the original tournament.

Maybe it will give you some ideas for strategies.
Read more of this post

Advertisements

Useful delusions, interface theory of perception, and religion

As you can guess from the name, evolutionary game theory (EGT) traces its roots to economics and evolutionary biology. Both of the progenitor fields assume it impossible, or unreasonably difficult, to observe the internal representations, beliefs, and preferences of the agents they model, and thus adopt a largely behaviorist view. My colleagues and I, however, are interested in looking at learning from the cognitive science tradition. In particular, we are interested in the interaction of evolution and learning. This interaction in of itself is not innovative, it has been a concern for biologists since Baldwin (1886, 1902), and Smead & Zollman (2009; Smead 2012) even brought the interaction into an EGT framework and showed that rational learning is not necessarily a ‘fixed-point of Darwinian evolution’. But all the previous work that I’ve encountered at this interface has made a simple implicit assumption, and I wanted to question it.

It is relatively clear that evolution acts objectively and without regard for individual agents’ subjective experience except in so far as that experience determines behavior. On the other hand, learning, from the cognitive sciences perspective at least, acts on the subjective experiences of the agent. There is an inherent tension here between the objective and subjective perspective that becomes most obvious in the social learning setting, but is still present for individual learners. Most previous work has sidestepped this issue by either not delving into the internal mechanism of how agents decide to act — something that is incompatible with the cognitive science perspective — or assuming that subjective representations are true to objective reality — something for which we have no a priori justification.

A couple of years ago, I decided to look at this question directly by developing the objective-subjective rationality model. Marcel and I fleshed out the model by adding a mechanism for simple Bayesian learning; this came with an extra perk of allowing us to adopt Masel’s (2007) approach to looking at quasi-magical thinking as an inferential bias. To round out the team with some cognitive science expertise, we asked Tom to join. A few days ago, after an unhurried pace and over 15 relevant blog posts, we released our first paper on the topic (Kaznatcheev, Montrey & Shultz, 2014) along with its MatLab code.
Read more of this post

Enriching evolutionary games with trust and trustworthiness

Fairly early in my course on Computational Psychology, I like to discuss Box’s (1979) famous aphorism about models: “All models are wrong, but some are useful.” Although Box was referring to statistical models, his comment on truth and utility applies equally well to computational models attempting to simulate complex empirical phenomena. I want my students to appreciate this disclaimer from the start because it avoids endless debate about whether a model is true. Once we agree to focus on utility, we can take a more relaxed and objective view of modeling, with appropriate humility in discussing our own models. Historical consideration of models, and theories as well, should provide a strong clue that replacement by better and more useful models (or theories) is inevitable, and indeed is a standard way for science to progress. In the rapid turnover of computational modeling, this means that the best one could hope for is to have the best (most useful) model for a while, before it is pushed aside or incorporated by a more comprehensive and often more abstract model. In his recent post on three types of mathematical models, Artem characterized such models as heuristic. It is worth adding that the most useful models are often those that best cover (simulate) the empirical phenomena of interest, bringing a model closer to what Artem called insilications.
Read more of this post

Cooperation through useful delusions: quasi-magical thinking and subjective utility

GoBoardEconomists that take bounded rationality seriously treat their research like a chess game and follow the reductive approach: start with all the pieces — a fully rational agent — and kill/capture/remove pieces until the game ends, i.e. see what sort of restrictions can be placed on the agents to deviate from rationality and better reflect human behavior. Sometimes these restrictions can be linked to evolution, but usually the models are independent of evolutionary arguments. In contrast, evolutionary game theory has traditionally played Go and concerned itself with the simplest agents that are only capable of behaving according to a fixed strategy specified by their genes — no learning, no reasoning, no built in rationality. If egtheorists want to approximate human behavior then they have to play new stones and take a constructuve approach: start with genetically predetermined agents and build them up to better reflect the richness and variety of human (or even other animal) behaviors (McNamara, 2013). I’ve always preferred Go over chess, and so I am partial to the constructive approach toward rationality. I like to start with replicator dynamics and work my way up, add agency, perception and deception, ethnocentrism, or emotional profiles and general condition behavior.

Most recently, my colleagues and I have been interested in the relationship between evolution and learning, both individual and social. A key realization has been that evolution takes cues from an external reality, while learning is guided by a subjective utility, and there is no a priori reason for those two incentives to align. As such, we can have agents acting rationally on their genetically specified subjective perception of the objective game. To avoid making assumptions about how agents might deal with risk, we want them to know a probability that others will cooperate with them. However, this depends on the agent’s history and local environment, so each agent should learn these probabilities for itself. In our previous presentation of results we concentrated on the case where the agents were rational Bayesian learners, but we know that this is an assumption not justified by evolutionary models or observations of human behavior. Hence, in this post we will explore the possibility that agents can have learning peculiarities like quasi-magical thinking, and how these peculiarities can co-evolve with subjective utilities.
Read more of this post

John Maynard Smith: games animals play

Although this blog has recently been focused on static fitness landscapes and the algorithmic lens, it’s url and a big chunk of the content focuses of evolutionary game theory (EGT). Heck, I even run a G+ community on the topic. If you are a biologist and asked me to define EGT then I would say it is a general treatment of frequency-dependent selection. If you were a mathematician then I might say that it is classical game theory done backwards: instead of assuming fully rational decision makers, imagine simple agents whose behavior is determined by their genes, and instead of analyzing equilibrium, look at the dynamics. If you are a computer scientists, I might even say to look at chapter 29 of your Algorithmic Game Theory book: it’s just a special case of AGT. However, all of these answers would be historically inaccurate.
Read more of this post

Hunger Games themed semi-iterated prisoner’s dilemma tournament

hungerGamesCodeWith all the talk surrounding it, crowdsourcing science might seem like a new concept and it might be true for citizen science efforts, but it is definitely an old trick to source your research to other researchers. In fact, evolutionary game theory was born (or at least popularized) by one such crowdsourcing exercise; in 1980, Robert Axelrod wanted to find out the best strategy for iterated prisoner’s dilemma and reached out to prominent researchers for strategy submissions to a round-robin tournmanet. Tit-for-tat was the winning strategy, but the real victor was Axelrod. His 1981 paper with Hamilton analyzing the result went on to become a standard reference in applications of game theory to social questions (at least outside of economics), agent-based modeling, and — of course — evolutionary game theory. Of Axelrod’s sizeable 47,222 (at time of writing) citations, almost half (23,370) come from this single paper. The tradition of tournaments continues among researchers, I’ve even discussed an imitation tournament on imitation previously.

The cynical moral of the tale: if you want to be noticed then run a game theory tournament. The folks at Brilliant.org — a website offering weekly olympiad-style challange problems in math and physics — took this message to heart, coupled it to the tried-and-true marketing technique of linking to a popular movie/book franchise, and decided to run a Hunger Games themed semi-iterated Prisoner’s dillema tournament. Submit a quick explanation of your strategy and Python script to play the game, and you could be one of the 5 winners of the $1,000 grand prize. Hooray! The submission deadline is August 18th, 2013 and all you need is a Brilliant account and it seems that these are free. If you are a reader of TheEGG blog then I recommend submitting a strategy, and discussing it in the comments (either before or after the deadline); I am interested to see what you come up with.
Read more of this post

Replicator dynamics of cooperation and deception

In my last post, I mentioned how conditional behavior usually implied a transfer of information from one agent to another, and that conditional cooperation was therefore vulnerable to exploitation through misrepresentation (deception). Little did I know that an analytic treatment of that point had been published a couple of months before.

McNally & Jackson (2013), the same authors who used neural networks to study the social brain hypothesis, present a simple game theoretic model to show that the existence of cooperation creates selection for tactical deception. As other commentators have pointed out, this is a rather intuitive conclusion, but of real interest here are how this relationship is formalized and whether this model maps onto reality in any convincing way. Interestingly, the target model is reminiscent of Artem’s perception and deception models, so it’s worth bringing them up for comparison; I’ll refer to them as Model 1 and Model 2.
Read more of this post

Evolving useful delusions to promote cooperation

This joint work with Marcel Montrey and Thomas Shultz combines — to be consistent with the interdisciplinary theme of this symposium — ideas from biology, economics, a little bit of cognitive science, and the approach is through applied mathematics. This post is a transcript of a presentation I gave on March 27th and covers part of my presentation today at Swarmfest.
Read more of this post

How ethnocentrism evolves: a simulation of evolutionary dynamics

tumblr_lcuael7Jyx1qeodf5Cooperation is a paradox—it just doesn’t make sense. Why should I help you when there’s no direct benefit for me? Artem, Professor Tom Shultz, and I have been working for quite some time on a paper about cooperation, and we’re psyched to announce that it’s finally been published in The Journal of Artificial Societies and Social Simulation (JASSS). JASSS is an open web journal, so you can view the full text of our article for free on their website. Or you could skip the 8000 or so words and check out this summary post. Read more of this post

Conditional cooperation and emotional profiles

I haven’t been delving into evolutionary game theory and agent-based modeling for very long, and yet I find that in that little time something quite eerie happens once I’m immersed in these models and simulations: I find myself oscillating between two diametrically opposed points of view. As I watch all of these little agents play their games using some all-too-simplistic strategy, I feel like a small God*. I watch cooperators cooperate, and defectors defect oblivious to what’s in their best interest at the moment. Of course, in the end, my heart goes out to the cooperators, who unfortunately can’t understand that they are being exploited by the defectors. That is what pushes me at the other end of the spectrum of omniscience, and with a nudge of empathy I find myself trying to be a simpleton agent in my over-simplified world.

In that state of mind, I begin to wonder what information exists in the environment, in particular information about the agents I am going to play against. I suppose I’m able to access it and use it to condition my move. Admittedly, that makes me a bit more complex than my original simpleton, and that complexity is likely to come at a cost, but I leave it to evolution to figure out whether the trade-off is worthwhile.
Read more of this post