---
_id: '5440'
abstract:
- lang: eng
  text: '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.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Rasmus
  full_name: Ibsen-Jensen, Rasmus
  id: 3B699956-F248-11E8-B48F-1D18A9856A87
  last_name: Ibsen-Jensen
  orcid: 0000-0003-4783-0389
- first_name: Martin
  full_name: Nowak, Martin
  last_name: Nowak
citation:
  ama: Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games
    on Graphs</i>. IST Austria; 2015. doi:<a href="https://doi.org/10.15479/AT:IST-2015-323-v2-2">10.15479/AT:IST-2015-323-v2-2</a>
  apa: Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity
    of evolutionary games on graphs</i>. IST Austria. <a href="https://doi.org/10.15479/AT:IST-2015-323-v2-2">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>
  chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity
    of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href="https://doi.org/10.15479/AT:IST-2015-323-v2-2">https://doi.org/10.15479/AT:IST-2015-323-v2-2</a>.
  ieee: K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary
    games on graphs</i>. IST Austria, 2015.
  ista: Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary
    games on graphs, IST Austria, 18p.
  mla: Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>.
    IST Austria, 2015, doi:<a href="https://doi.org/10.15479/AT:IST-2015-323-v2-2">10.15479/AT:IST-2015-323-v2-2</a>.
  short: K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary
    Games on Graphs, IST Austria, 2015.
date_created: 2018-12-12T11:39:21Z
date_published: 2015-06-16T00:00:00Z
date_updated: 2023-02-23T12:26:10Z
day: '16'
ddc:
- '005'
- '576'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2015-323-v2-2
file:
- access_level: open_access
  checksum: 66aace7d367032af97c15e35c9be9636
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T11:53:23Z
  date_updated: 2020-07-14T12:46:56Z
  file_id: '5484'
  file_name: IST-2015-323-v2+2_main.pdf
  file_size: 466161
  relation: main_file
file_date_updated: 2020-07-14T12:46:56Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '18'
publication_identifier:
  issn:
  - 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '338'
related_material:
  record:
  - id: '5421'
    relation: earlier_version
    status: public
  - id: '5432'
    relation: earlier_version
    status: public
status: public
title: The complexity of evolutionary games on graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...