# The complexity of evolutionary games on graphs

Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 18p.

Download

IST-2015-323-v2+2_main.pdf
466.16 KB

*Technical Report*|

*Published*|

*English*

Author

Department

Series Title

IST Austria Technical Report

Abstract

Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.

Publishing Year

Date Published

2015-06-16

Page

18

ISSN

IST-REx-ID

### Cite this

Chatterjee K, Ibsen-Jensen R, Nowak M.

*The Complexity of Evolutionary Games on Graphs*. IST Austria; 2015. doi:10.15479/AT:IST-2015-323-v2-2Chatterjee, K., Ibsen-Jensen, R., & Nowak, M. (2015).

*The complexity of evolutionary games on graphs*. IST Austria. https://doi.org/10.15479/AT:IST-2015-323-v2-2Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak.

*The Complexity of Evolutionary Games on Graphs*. IST Austria, 2015. https://doi.org/10.15479/AT:IST-2015-323-v2-2.K. Chatterjee, R. Ibsen-Jensen, and M. Nowak,

*The complexity of evolutionary games on graphs*. IST Austria, 2015.Chatterjee, Krishnendu, et al.

*The Complexity of Evolutionary Games on Graphs*. IST Austria, 2015, doi:10.15479/AT:IST-2015-323-v2-2.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

IST-2015-323-v2+2_main.pdf
466.16 KB

Access Level

Open Access

Date Uploaded

2018-12-12

MD5 Checksum

66aace7d367032af97c15e35c9be9636

**Material in ISTA:**

**Earlier Version**

**Earlier Version**