Computing Nash Equilibria of Tree Polymatrix Games

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. I will sketch the construction for this hardness result, and finish by discussing the open case of tree interaction graphs with 2 actions per player.

Joint work with Argyrios Deligkas and John Fearnley.