Room 327

Polymatrix coordination games

Sunil Simon

IIT, Kanpur

We consider an extension of coordination games to the network setting where the neighbourhood relation is specified using a graph and
common strategies are not guaranteed to exist. When the payoffs are symmetric, pure Nash equilibria always exist where as strong equilibria may not always exist. We identify certain classes of graphs where strong equilibria are guaranteed to exist.

When payoffs are not ecessarily symmetric, we show that the problem of determining the existence of a pure Nash equilibrium becomes NP-complete.
We identify several natural classes of graphs for which a finite improvement path of polynomial length always exists. As a consequence, a pure Nash equilibrium can be computed in polynomial time. We also argue that these results are optimal in the sense that in natural generalisations of these classes of graphs, a pure Nash
equilibrium may not even exist.