Thesis Defense: Structural Properties of Games on Graphs

The evolution shapes the world around us. Not only in biology, where the fittest individuals spread their genes, but also in physics and social dynamics, the evolutionary forces determine the development of a state of matter or public opinions. Many models describe these dynamics. This thesis examines the role of the structure in the models of selection.
The population structure is represented as a graph or a network, and each vertex is occupied by one individual. Every individual has a type and fitness that represents the reproductive potential and depends on the type, occupied vertex, and the arrangement of the neighbors. The evolution is modeled in discrete steps; in one step, one individual is replaced by a neighbor selected randomly with the influence of fitness.

This thesis examines the role of structure in models of selection from multiple perspectives. It presents the first amplifiers (graphs that help advantageous mutants to spread) for two variants of the Moran process: one with a constant birth rate and the other with a constant death rate. The thesis describes the first structure that promotes cooperation in a setting where the fitness depends on an underlying game, and determines the computational complexity of these game dynamics. Moreover, it explores heterogeneous networks and signed graphs, and the influence of structure on evolutionary processes in these settings.