Finding Nash equilibria of Tree Polymatrix Games

12^th June 2019, 13:00
Rahul Savani
University of Liverpool

Abstract

Polymatrix games provide a succinct representation of many-player games. In a polymatrix game, a player's payoff is the sum of payoffs from pairwise interactions with other players. The game's interaction graph encodes which players interact with each other.
The problem of finding one Nash equilibrium of a polymatrix games is known to be PPAD-complete (i.e., of high complexity) for:
- degree 3 bipartite interaction graphs with 2 actions per player [Rubinstein 2016];
- degree 3 graphs with constant pathwidth and 2 actions per player [Elkind Goldberg Goldberg 2006].
We show that the problem is PPAD-hard for tree (actually caterpillar) interaction graphs.

Joint work with Argyrios Deligkas and John Fearnley.