Advancing Learning and Evolutionary Game Theory with an Application to Social Dilemmas

PhD Thesis

Written by Luis R. Izquierdo. Supervised by Nick Gotts and Bruce Edmonds.

Download the whole thesis.

Abstract

This thesis advances game theory by formally analysing the implications of replacing some of its most stringent assumptions with alternatives that –at least in certain contexts– have received greater empirical support. Specifically, this thesis makes two distinct contributions in the field of learning game theory and one in the field of evolutionary game theory. The method employed has been a symbiotic combination of computer simulation and mathematical analysis. Computer simulation has been used extensively to enhance our understanding of various formal systems beyond the current limits of mathematical tractability, and also to illustrate, complement and extend various analytical derivations.

The two extensions to learning game theory presented here abandon the orthodox assumption that players are fully rational, and assume instead that players follow one of two alternative decision-making processes –case-based reasoning or reinforcement learning– that have received strong support from cognitive science research. The formal results derived in this part of the thesis add to the growing body of work in learning game theory that supports the general principle that the stability of outcomes in games depends not only on how unilateral deviations affect the deviator but also, and crucially, on how they affect the non-deviators. Outcomes where unilateral deviations hurt the deviator (strict Nash) but not the non-deviators (protected) tend to be the most stable.

The contribution of this thesis to evolutionary game theory is a systematic study of the extent to which the assumptions made in mainstream evolutionary game theory for the sake of tractability are affecting its conclusions. Our results show that the type of strategies that are likely to emerge and be sustained in evolutionary contexts is strongly dependent on assumptions that traditionally have been thought to be unimportant or secondary (e.g. number of players, continuity of the strategy space, mutation rate, population structure...). This latter contribution is focused on the evolutionary emergence of cooperation.

Following the presentation of the main results and the discussion of their implications, this thesis provides some guidance on how the models analysed here could be parameterised and validated.

Contents

Front page, acknowledgements, abstract and table of contents. [Download]

1. Introduction

This chapter outlines the motivation of this thesis, its overall aim, the approach and the methodology we followed. It also highlights the main distinguishing features of this work, and briefly summarises the key contributions of this thesis to the advancement of human knowledge. [Download]

2. Main Assumptions in Game Theory

This chapter is a critical dissection of the main assumptions embedded in each of the most advanced branches of deductive non-cooperative game theory. We distinguish between game theory as a framework (which makes no assumptions about individuals' behaviour or beliefs), classical game theory, evolutionary game theory, and learning game theory. [Download]

3. Scope and method

The first section of this chapter explains what social dilemmas are and how they can be formalised as 2×2 games; it also gives a brief account of some of the most relevant results obtained within each of the main branches of deductive game theory on the most famous 2×2 social dilemma, i.e. the Prisoner's Dilemma. The second section of this chapter outlines the range of formal methods that have been used to analyse the models developed in this thesis. It is argued that both mathematical analysis and simulation studies are extremely useful tools to analyse the dynamics of formal models, particularly when used together. [Download]

4. Dynamics of the Bush-Mosteller Reinforcement Learning Algorithm in 2×2 Games

This chapter is an in-depth analysis of the transient and asymptotic dynamics of the Bush-Mosteller reinforcement learning algorithm for 2-player 2-strategy games. [Download]

5. The Implications of Case-Based Reasoning in Strategic Contexts

Case-Based Reasoning is a form of reasoning by analogy within a particular domain. This chapter is an exploration of cased-based reasoning as decision-making algorithm in strategic contexts. [Download]

6. Structural Robustness of Evolutionary Models in Game Theory

This chapter describes EVO-2×2, the modelling framework developed in this thesis to assess the impact of various assumptions made in mainstream evolutionary game theory for the sake of mathematical tractability. The use of EVO-2×2 is illustrated by conducting an investigation on the structural robustness of evolutionary models of cooperation. [Download]

7. Discussion

Chapter 7 is a general discussion of the results obtained in chapters 4, 5 and 6. This chapter outlines five ways in which the research conducted in this thesis can be usefully applied to contribute to the advancement of human knowledge. [Download]

8. Conclusions

The structure of this final chapter is particularly simple. Section 8.1 summarises the main contributions of this thesis to the advancement of game theory. The methodological conclusions derived from the symbiotic use of computer simulation and mathematical analysis are then summarised in section 8.2. Finally, the last section of this chapter (8.3) identifies areas for future research. [Download]

Remaining sections

Supporting Material

All the software, parameter files, and documentation required to easily replicate every experiment presented in this thesis are included in this (~50 MB) file. This document outlines the structure of the supporting material.