# Towards convergence to Nash equilibria in two-team zero-sum games

arXiv: https://arxiv.org/abs/2111.04178 · HTML: https://mlsanity.com/paper/2111.04178/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 92 references that are in the map.
- First posted on arXiv 7 Nov 2021.

## Builds on (most cited first, 30 of 30)

- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Human-level performance in first-person multiplayer games with population-based deep reinforcement learning](https://mlsanity.com/paper/1807.01281/) (2018)
- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Multi-agent Reinforcement Learning in Sequential Social Dilemmas](https://mlsanity.com/paper/1702.03037/) (2017)
- [MAD-GAN: Multivariate Anomaly Detection for Time Series Data with Generative Adversarial Networks](https://mlsanity.com/paper/1901.04997/) (2019)
- [Generalization and Equilibrium in Generative Adversarial Nets (GANs)](https://mlsanity.com/paper/1703.00573/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Generative Multi-Adversarial Networks](https://mlsanity.com/paper/1611.01673/) (2016)
- [MD-GAN: Multi-Discriminator Generative Adversarial Networks for Distributed Datasets](https://mlsanity.com/paper/1811.03850/) (2018)
- [Tight last-iterate convergence rates for no-regret learning in multi-player games](https://mlsanity.com/paper/2010.13724/) (2020)
- [Multi-objective training of Generative Adversarial Networks with multiple discriminators](https://mlsanity.com/paper/1901.08680/) (2019)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [The Complexity of Gradient Descent: CLS = PPAD cap PLS](https://mlsanity.com/paper/2011.01929/) (2020)
- [Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games](https://mlsanity.com/paper/1910.13010/) (2019)
- [Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent](https://mlsanity.com/paper/2106.01285/) (2021)
- [Team-maxmin equilibrium: efficiency bounds and algorithms](https://mlsanity.com/paper/1611.06134/) (2016)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Multi-Generator Generative Adversarial Nets](https://mlsanity.com/paper/1708.02556/) (2017)
- [Stackelberg GAN: Towards Provable Minimax Equilibrium via Multi-Generator Architectures](https://mlsanity.com/paper/1811.08010/) (2018)
- [Adversarial Regression with Multiple Learners](https://mlsanity.com/paper/1806.02256/) (2018)
- [Lessons Learned from the Training of GANs on Artificial Datasets](https://mlsanity.com/paper/2007.06418/) (2020)
- [Computing Ex Ante Coordinated Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games](https://mlsanity.com/paper/2009.12629/) (2020)
- [Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics](https://mlsanity.com/paper/1408.6270/) (2014)
- [Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies](https://mlsanity.com/paper/2102.05026/) (2021)

## Built on by (most cited first, 1 of 1)

- [A Value Based Parallel Update MCTS Method for Multi-Agent Cooperative Decision Making of Connected and Automated Vehicles](https://mlsanity.com/paper/2409.13783/) (2024)

## Abstract (arXiv)

Contemporary applications of machine learning in two-team e-sports and the superior expressivity of multi-agent generative adversarial networks raise important and overlooked theoretical questions regarding optimization in two-team games. Formally, two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents, each experiencing a utility identical to that of their teammates and opposite to that of the opposing team. We focus on the solution concept of Nash equilibria (NE). We first show that computing NE for this class of games is textithard for the complexity class CLS. To further examine the capabilities of online learning algorithms in games with full-information feedback, we propose a benchmark of a simple -- yet nontrivial -- family of such games. These games do not enjoy the properties used to prove convergence for relevant algorithms. In particular, we use a dynamical systems perspective to demonstrate that gradient descent-ascent, its optimistic variant, optimistic multiplicative weights update, and extra gradient fail to converge (even locally) to a Nash equilibrium. On a brighter note, we propose a first-order method that leverages control theory techniques and under some conditions enjoys last-iterate local convergence to a Nash equilibrium. We also believe our proposed method is of independent interest for general min-max optimization.