Nash equilibrium
Polymatrix games always have at least one mixed Nash equilibrium. The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete. Moreover, the problem of finding a constant approximate Nash equilibrium in a polymatrix game is also PPAD-complete. Finding a correlated equilibrium of a polymatrix game can be done in polynomial time. Note that even if pairwise games played between players have pure Nash equilibria, the global interaction does not necessarily admit a pure Nash equilibrium (although a mixed Nash equilibrium must exist).