Game Theory & Math Economics: Rasmus Ibsen-Jensen (IST Austria) - "Computational Complexity of Evolutionary Games on Graphs"

The talk will consider evolutionary games on graphs, which is a generalization of matrix games to graphs, using the solution concept of evolutionary stable strategies. In evolutionary games on graphs, there is a graph and a 2x2 matrix. Each node of the graph has a strategy of the matrix game - r or b - and initially all nodes are r. Then, a uniformly random node is made to follow b and the following is repeated until the graph is all one strategy again:1. Find the average payoff of each node when playing against their neighbors in the graph (depending on their current strategies).2. Translate this into a probability distribution and pick a node.3. That node makes a random neighbor follow its strategy.The question of interest is to find an approximation of the probability that the graph eventually becomes all b.We consider two special cases, depending on the matrix: the matrix is constant in each row (called constant selection or generalized Moran process) or is an instance of the prisoners' dilemma.We show that the former can be solved in polynomial time and the latter is PSPACE-hard and even for general matrices can be done in polynomial space.  

Date: 

Sun, 26/11/2017 - 16:00 to 17:00

Location: 

Elath Hall, 2nd floor, Feldman Building, Edmond J. Safra Campus