Slides for Szabo & Fath’s Evolutionary Games on Graphs

On April 5th and 12th, 2012 we discussed Szabo & Fath (2007) Evolutionary Games on Graphs. This is a very long review paper (133 pages) but is an amazing introduction to evolutionary game theory (EGT) and games on graphs, in particular. We are not finished talking about all parts of the paper but have discussed the following sections:

  • Peter Helfer presented Section 2: Rational game theory.
  • Marcel Montrey presented Section 5: The structure of social graphs.
  • Thomas Shultz presented Section 6: Prisoner’s dilemma.

I still want to take closer look at section 3 (Evolutionary games: population dynamics), 4 (Evolutionary games: agent-based dynamics), and C (Generalized mean-field approximations).

In the introduction, Szabo & Fath stress the importance of evolutionary game theory as a unifying approach to question in various fields (biology, cognitive science, economics, and social sciences). The defend EGT as a way to climb up the rationality ladder: start from the simplest possible agents and work your way up. This approach to bounded rationality seems very natural to me, and I am surprised it has not made a bigger impact. What is the influence of evolutionary game theory on the cognitive sciences?

For Szabo & Fath, EGT has 3 main goals: (1) study bounded rationality, (2) explore dynamics, and (3) provide an equilibrium selection method in both static and dynamic settings. In other words, the goal is to fix the hard problems of rational game theory. The survey focuses on graph games with identical agents with heterogeneous neighbourhoods.

In his slides, Peter followed section 2 and introduces the basics of rational game theory. He talked about normal form games, focusing on some special cases like symmetric and zero-sum games. Previously, I have given a detailed treatment of two strategy cooperate-defect games. Peter presented the more drastic single variable parametrization of two strategy games that lets us view them on the unit circle. Unfortunately, this transformation preserves only Nash equlibria and not Pareto dominance. It cannot be used for evolution of cooperation studies because it cannot distinguish between games with Pareto inefficient Nash-eq (what defines social dilemmas) and simple Pareto efficient equilibria.

Marcel’s review of section 5 recalled and then expanded past his previous discussion of spatial structure. Of particular interest to me was his slide on diluted lattices which are formed by removing some nodes or edges from a regular lattice. I wonder how free space would interact with dilute lattices in the Hammond & Axelrod model. Marcel finished with a slide on evolving graphs.

Tom looked at the bread-and-butter of evolution of cooperating: the Prisoner’s dilemma. For iterated games, he focused on stochastic reactive strategies as a probabilistic generalization of Tit-for-Tat and finite populations. For spatial games Tom discussed the classic Nowak & May paper and variants with stochastic updating. To set the stage for small world networks, Tom showed results on the simplest kind of heterogeneous networks: the dumbbell. He finished with a discussion of early tag-based simulations.

I recommend taking a look at the slides, and if something piques your interest reading the relevant section of the survey. Some more detailed summaries will come in future posts.

ResearchBlogging.orgSzabo, G., & Fath, G. (2007). Evolutionary games on graphs Physics Reports, 446 (4-6), 97-216 DOI: 10.1016/j.physrep.2007.04.004

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

8 Responses to Slides for Szabo & Fath’s Evolutionary Games on Graphs

  1. Victoria says:

    This is an interesting post. I was looking at this last week and considered reading it although the length does seem a bit daunting. I hope you could provide the slides or perhaps write future posts to expand on the sections that have been discussed. It would certainly be helpful.

    • Victoria says:

      Oops I failed to realize the slides are already linked! Please ignore my comment above and thanks.

  2. Pingback: EGT Reading Group 21 – 30 « Theory, Evolution, and Games Group

  3. Pingback: Start of ethnocentric cooperation « Theory, Evolution, and Games Group

  4. Pingback: Slides for Roca, Cuesta & Sanchez’s EGT: Temporal and spatial effects beyond replicator dynamics « Theory, Evolution, and Games Group

  5. Pingback: Introduction to evolving cooperation « Theory, Evolution, and Games Group

  6. Pingback: Asking Amanda Palmer about cooperation in the public goods game | Theory, Evolution, and Games Group

  7. Pingback: Space and stochasticity in evolutionary games | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s