  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 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
$\epsilon$-approximate stationary strategy for the team can be extended in
polynomial time to an $O(\epsilon)$-approximate Nash equilibrium, where the
$O(\cdot)$ notation suppresses polynomial factors in the description of the
game. As a consequence, we show that the Moreau envelop of a suitable best
response function acts as a potential under certain natural gradient-based
dynamics.
