# On Tractable Phi-Equilibria in Non-Concave Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2024.

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

- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games](https://mlsanity.com/paper/2511.01852/) (2025)

## Abstract (arXiv)

While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is concave in their own strategy, this is not the case when utilities are non-concave -- a common scenario in machine learning applications involving strategies parameterized by deep neural networks, or when agents' utilities are computed by neural networks, or both. Non-concave games introduce significant game-theoretic and optimization challenges: (i) Nash equilibria may not exist; (ii) local Nash equilibria, though they exist, are intractable; and (iii) mixed Nash, correlated, and coarse correlated equilibria generally have infinite support and are intractable. To sidestep these challenges, we revisit the classical solution concept of Phi-equilibria introduced by Greenwald and Jafari [2003], which is guaranteed to exist for an arbitrary set of strategy modifications Phi even in non-concave games [Stolz and Lugosi, 2007]. However, the tractability of Phi-equilibria in such games remains elusive. In this paper, we initiate the study of tractable Phi-equilibria in non-concave games and examine several natural families of strategy modifications. We show that when Phi is finite, there exists an efficient uncoupled learning algorithm that converges to the corresponding Phi-equilibria. Additionally, we explore cases where Phi is infinite but consists of local modifications. We show that approximating local Phi-equilibria beyond the first-order stationary regime is computationally intractable. In contrast, within this regime, we show Online Gradient Descent efficiently converges to Phi-equilibria for several natural infinite families of modifications, including a new structural family of modifications inspired by the well-studied proximal operator.