Adversarial team games model multiplayer strategic interactions in which a team of identically-interested players is competing against an adversarial player in a zero-sum game. Such games capture many well-studied settings in game theory, such as congestion games, but go well-beyond to environments wherein the cooperation of one team---in the absence of explicit communication---is obstructed by competing entities; the latter setting remains poorly understood despite its numerous applications. Since the seminal work of Von Stengel and Koller (GEB `97), different solution concepts have received attention from an algorithmic standpoint. Yet, the complexity of the standard Nash equilibrium has remained open.
In this paper, we settle this question by showing that computing a Nash equilibrium in adversarial team games belongs to the class \emph{continuous local search} (CLS, thereby establishing CLS-completeness by virtue of the recent CLS-hardness result of Rubinstein and Babichenko (STOC 21) in potential games. To do so, we leverage linear programming duality to prove that any
Based on joint work with Ioannis Anagnostides, Ioannis Panageas, Manolis Vlatakis, Stephen McAleer