An Empirical Study on Computing Equilibria in Polymatrix Games

The Nash equilibrium is an important benchmark for behaviour in systems of strategic autonomous agents. Polymatrix games are a succinct and expressive representation of multiplayer games that model pairwise interactions between players. The empirical performance of algorithms to solve these games has received little attention, despite their wide-ranging applications. In this paper we carry out a comprehensive empirical study of two prominent algorithms for computing a sample equilibrium in these games, Lemke's algorithm that computes an exact equilibrium, and a gradient descent method that computes an approximate equilibrium. Our study covers games arising from a number of interesting applications. We find that Lemke's algorithm can compute exact equilibria in relatively large games in a reasonable amount of time. If we are willing to accept (high-quality) approximate equilibria, then we can deal with much larger games using the descent method. We also report on which games are most challenging for each of the algorithms.