Tutorial | Game dynamics on evolutionary graphs - An introduction
Upcoming: IEEE Congress on Evolutionary Computation 28.06-1.07.2021 Kraków, Poland (VIRTUAL)
Tutor: Hendrik Richter
Affiliation: Faculty of Engineering, HTWK Leipzig University of Applied Sciences Leipzig (Germany)
Studying evolutionary games on graphs can be seen as an attempt to address a long-standing and fundamental problem in Darwinian evolution. How can two seemingly contradictory observations be reconciled? Individuals experience selective pressure which commonly entails competition in order to be successful in survival and reproduction. However, at the same time we find wide-spread cooperative and even altruistic behavior among individuals (and also groups of individuals or even species). In other words, how can selection favor fitter individuals over less fit, while the same individuals regularly cooperate with and support each other, thus ostensibly leveling off differences in fitness?
Evolutionary games may offer answers to these questions as they set up mathematical models to discuss whether, when and under what circumstances cooperation may be more advantageous than competition. Such games define individuals having behavioral choices to be players selecting and executing strategies (for instance cooperation or competition). By linking the relative costs and benefits of strategies to payoff (and subsequently fitness), we obtain a measure of how profitable a given choice is in evolutionary terms. Evolutionary games are highly dependent on the network of interaction, which describes with whom a given player interacts in the game. For describing such networks, element from graph theory have been proposed, which leads to the concept of evolutionary graphs.
The tutorial will give an overview about concepts and research questions as well as addressing recent developments in studying evolutionary games on graphs. Particularly, the concept of game dynamics with changing strategies and interaction networks is addressed.
- Concepts and mathematical models of evolutionary and coevolutionary games
- Players and strategies
- Evolutionary graph theory
- Strategies and configurations
- Games and evolutionary dynamics
- Nash equilibria and evolutionary stable strategies (ESS)
- Parameterization of the payoff matrix and social dilemma games: prisoner's dilemma (PD), snowdrift (SD), stag-hunt (SH), harmony (H) games
- Dilemma strength and universal scaling
- Frequency dependence
- Fixation properties: fixation probabilities and fixation times
- Dynamics on graphs
- Networks of interaction and evolutionary graphs
- Replicator dynamics
- Models of interaction networks: Erdös-Rényi, Barabási-Albert, Watts-Strogatz networks
- Analytical calculation of fixation probabilities
- Amplification and suppression of selection
- Graph measures and fixation
- Open questions and research topics
The tutorial might be interesting for researcher and students looking for an entry point into evolutionary games on graphs. Scientists already working with evolutionary games may find it helpful to obtain an update about recent developments in the field and getting a fresh look at perspectives and potentials. Also practitioners wanting to enhance their knowledge about evolutionary games, evolutionary game theory and graph theory may discover valuable material.
Proposed length and level
120 min, introductory
Bio of the tutor Hendrik Richter
I am Professor at the Faculty of Electrical Engineering & Information Technology of HTWK Leipzig University of Applied Sciences. I am involved in research in the field of evolutionary computation since almost 20 years, regularly attending conference in the field and contributing papers. My main research topics are dynamic optimization, fitness landscapes, coevolution and evolutionary game theory. A tutorial entitled “Recent advances in fitness landscapes” was presented by me at WCCI-CEC 2014, and a tutorial “Concepts and recent results in co-evolutionary games” at WCCI-CEC 2018. At WCCI-CEC 2016 I received the regular best paper award for a paper proposing a landscape approach to coevolutionary games.
My recent publications in the field of coevolution, evolutionary game theory and evolutionary graphs are:
H. Richter, Evolution of cooperation for multiple mutant configurations on all regular graphs with N≤ 14 players. Games 11 (1), 12, 2020.
H. Richter, Properties of network structures, structure coefficients, and benefit–to–cost ratios. BioSystems 180, 88-100, 2019.
H. Richter, Fixation properties of multiple cooperator configurations on regular graphs. Theory in Biosciences 138 (2), 261-275, 2019.
H. Richter, Relationships between dilemma strength and fixation properties in coevolutionary games. Proc. ICNC-FSKD 2019: Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery, (Ed. Y. Liu, et al.), Advances in Intelligent Systems and Computing, Vol. 1074, Springer, 2019, 252-259.
H. Richter, Information content of coevolutionary game landscapes. Proc. IEEE Congress on Evolutionary Computation, IEEE CEC 2018, (Ed.: G. G. Yen), IEEE Press, Piscataway, NJ, 2018, 2051-2058.
H. Richter, Dynamic landscape models of coevolutionary games. BioSystems 153-154: 26-44, 2017.
H. Richter, Analyzing coevolutionary games with dynamic fitness landscapes. In: Ong, Y. S. (Ed.), Proc. IEEE Congress on Evolutionary Computation, IEEE CEC 2016, IEEE Press, Piscataway, NJ, 2016, 609-616.
Hendrik Richter: Coevolutionary intransitivity in games: A landscape analysis. In: Applications of Evolutionary Computation - EvoApplications 2015, (Eds.: A. M. Mora, G. Squillero), Lecture Notes in Computer Science, Vol. 9028, Springer, Berlin, 2015, 869-881.