Research map / Learning theory and algorithms / Submodular and game algorithms

The Complexity of Two-Team Polymatrix Games with Independent Adversaries

ICLR 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that computing an approximate Nash equilibrium in two-team zero-sum polymatrix games is CLS-hard (even with no internal edges in one team), proves CLS-membership when the second team consists of independent adversaries, and gives a projected gradient descent algorithm with 1/ε² running time.

Problem

The complexity of computing Nash equilibria in two-team polymatrix zero-sum games, where each pair of players plays a zero-sum or coordination game; open for two teams after PPAD-hardness for three teams.

Approach

Reduces MinQuadKKT to a multilinear min-max KKT problem with no y_i y_j terms (independence property), then embeds it into a two-team polymatrix game with independent adversaries using two-action players; for independent adversaries, the LP dual yields a minimization formulation whose KKT points give Nash equilibria, enabling CLS membership and projected gradient descent.

Key results

• Two-team zero-sum polymatrix games with independent adversaries (even with two actions per player) are CLS-hard to find an approximate Nash equilibrium when epsilon is inverse exponential in the game description.
• For independent adversaries the problem lies in CLS, making the hardness tight.
• Projected gradient descent yields an epsilon-Nash equilibrium in time O(poly(|Γ|)/ε²) for payoffs in [-1,1].

Surprising findings

• Hardness holds already for bilinear polynomial min-max objectives that are concave in the max variable, which are the simplest non-convex-concave case.

Limitations

• CLS membership only holds for independent adversaries; with internal adversary edges the problem is only known to be in PPAD.
• Hardness requires inverse-exponential epsilon; does not rule out polynomial algorithms for constant epsilon-type regimes beyond stated bounds.

Experimental setup

Baselines: Anagnostides et al. algorithm for two-team games

Builds on: Cai and Daskalakis three-team PPAD-hardness Anagnostides et al. single-adversary CLS membership Daskalakis and Papadimitriou polymatrix zero-sum games

Closest papers by meaning

• The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.91)
• On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games (AAAI 2021 · similarity 0.91)
• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.89)
• Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics (NeurIPS 2025 · similarity 0.88)
• Efficient Learning in Polyhedral Games via Best-Response Oracles (AAAI 2024 · similarity 0.87)
• Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.87)