The Complexity of Two-Team Polymatrix Games with Independent Adversaries

A team of researchers from EPFL and ETH Zurich has solved a significant open problem in computational game theory that has implications for multi-agent AI systems. In their paper "The Complexity of Two-Team Polymatrix Games with Independent Adversaries," Alexandros Hollender, Gilbert Maystre, and Sai Ganesh Nagarajan proved that computing Nash equilibria in two-team polymatrix games is CLS-hard, matching the known complexity of three-team versions. This finding closes a gap in our understanding of tractability limits in multiplayer game settings where players can be grouped into teams with identical interests.

Polymatrix games are multiplayer settings where each pair of players engages in either a zero-sum or coordination game, and Nash equilibria were previously known to be efficiently computable in general cases. The researchers specifically examined the scenario where one team consists of multiple independent adversaries, showing this lower bound is tight (CLS-membership). Their analysis revealed that even the simplest non-convex-concave min-max optimization problems with bilinear polynomial objectives are computationally hard.

Beyond the complexity result, the team leveraged their findings to develop a practical algorithm that finds ε-Nash equilibria with only a 1/ε² dependence in its running time. This represents a significant improvement over previous approaches and provides researchers with new tools for analyzing multi-agent systems where computational efficiency matters. The work bridges theoretical computer science with practical AI applications, particularly relevant for understanding cooperation and competition in complex multi-agent environments.