Negative Momentum for Coalition-Proof Equilibria on the Simplex Boundary

A Nash equilibrium only guarantees that no single player gains by changing strategy alone. Groups of players can often do better by changing strategies together. The effect is strongest when the equilibrium is mixed, meaning players randomize independently, because a coordinating group can remove that uncoordinated randomness. One way to find outcomes that resist group deviations is to cast the search as a two-player zero-sum "meta-game". In it, a correlator proposes a distribution over joint actions, and a deviator picks a coalition and a joint action for it that maximizes the coalition's average gain. The correlator wins by making the best available group deviation as unprofitable as possible. Computing Equilibrium beyond Unilateral Deviation solves this with Follow the Perturbed Leader plus dynamic programming over tree decompositions. It recovers full cooperation in the Prisoner's Dilemma, but its cost grows exponentially with the treewidth of the game's interaction graph.

This note makes a simple observation and builds a research program on it. The coalitional meta-game is a large rectangular zero-sum game played over two probability simplices: there are far more coalition deviations than joint profiles. The equilibria of such games generically put zero weight on many actions, so they sit on the boundary of the simplex. That is exactly the regime where our best global convergence theory for first-order game dynamics stops working. On the O(1/T) Convergence of Alternating Gradient Descent–Ascent in Bilinear Games proves a global $O(1/T)$ rate for alternating gradient descent-ascent only when the equilibrium is interior, and only a local result when it is on the boundary. We propose to close that boundary gap for alternating negative-momentum dynamics, and to use the result to get the first last-iterate, first-order solver for coalition-resistant equilibria. Here "negative momentum" means reversing the usual heavy-ball velocity term so that it acts as friction against rotation.

Core Claim

The claim has two parts. The first is theoretical. On simplex-constrained bilinear games whose equilibrium is unique, lies on the boundary, and is strictly complementary, alternating entropic mirror descent with a negative momentum coefficient converges globally in the last iterate at a rate at least $O(1/T)$. Strict complementarity means every action outside the support is strictly worse, the "sharp" condition. Unlike the $\beta = 0$ method, this rate does not require an interior equilibrium.

The second part is empirical. On coalitional meta-games built from standard multi-player games, the boundary-structured equilibrium is the typical case. There, negative momentum should turn slow or stalling last-iterate convergence into fast convergence, while the gain should disappear on controlled meta-games with interior equilibria. That contrast is what would show the mechanism is about the boundary and not a generic speedup.

We are not proposing a new optimizer. The update is the momentum-augmented mirror descent of Rapid Learning in Constrained Minimax Games with Negative Momentum (Fang et al.), applied with alternation. What is new is the global boundary theorem, and bringing momentum dynamics to coalitional solution concepts. Fang et al. show large empirical gains only for two-player zero-sum poker and matrix games, and they never touch coalitions.

The Meta-Game

Let $A$ be the joint action space of an $N$-player game with utilities $u_i$. The correlator chooses $\mu \in \Delta(A)$. The deviator chooses $\nu$, a distribution over pairs $(S, a_S)$, where $S$ is a coalition and $a_S$ a fixed joint action for its members. We use this "coarse" deviation, which ignores the recommendation, to keep the deviator's space polynomial in $|A|$. The payoff to the deviator is the coalition's average gain:

$$ g(\mu,\nu)=\sum_{(S,a_S)}\nu(S,a_S)\,\frac{1}{|S|}\sum_{i\in S}\mathbb{E}_{a\sim\mu}\big[u_i(a_S,a_{-S})-u_i(a)\big]. $$

The value $\min_\mu \max_\nu g$ is a coarse variant of the Minimum Average-Strong Equilibrium (MASE) value from Liu et al. The function $g$ is bilinear in $(\mu,\nu)$, so the game is a plain matrix game. For $N=5$ players with $5$ actions each, it has 3,125 correlator actions against about 7,775 deviator actions. That size is small enough to solve exactly by linear programming for ground truth, and large enough that dynamics matter. The update we study replaces the plain gradient $\nabla$ in entropic mirror descent with $\nabla_t + \beta(\nabla_t - \nabla_{t-1})$, with $\beta<0$, and the players move alternately. This mirrors the $\omega_{t+1}=\omega_t-\eta v(\omega_t)+\beta(\omega_t-\omega_{t-1})$ form of Negative Momentum for Improved Game Dynamics.

Research Program

Theory. Gidel et al. show that alternation combined with $\beta<0$ is what gives linear convergence in unconstrained bilinear games, but their analysis is local. Nan et al. build a global energy function for alternating descent-ascent that tracks boundary collisions, but it only closes when the equilibrium is interior. Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness shows that sharp boundary equilibria attract entropic regularized dynamics geometrically fast, but only once the iterates are nearby. We will try to add a momentum cross-term to Nan et al.'s energy function. The goal is to show that strict complementarity lets the off-support mass decay at a rate the friction term preserves, which would make the energy decrease globally rather than only near the equilibrium.

This is where the program can fail. On the Suboptimality of Negative Momentum for Minimax Optimization shows that negative momentum can be slower than extrapolation methods under some spectra. So we treat a proof that negative momentum enlarges the region of guaranteed convergence as the core result, and a rate improvement over optimistic methods as secondary.

Connection to group-deviation fragility. For Learning in Symmetric Teams, Local Optima are Global Nash Equilibria finds that between 36% and 60% of symmetric local optima in GAMUT random games are mixed, and so exploitable by coordinated deviation. In a pure team game, the grand coalition can always deviate to the team optimum. The meta-game value is therefore zero only at team-optimal profiles, which are pure and so lie at simplex vertices. A meta-game solver started at Emmons et al.'s mixed symmetric optimum must travel from the interior to a vertex. This is precisely the interior-to-boundary transit that the theory targets, and it gives a concrete test of Gap 4 in the file: learning must pass through the interior, where coalition gains are evaluated, without cycling there.

Scaling beyond exact dynamic programming. For larger games, such as polymatrix games of the kind Liu et al. test up to 100 players, we restrict coalitions to size at most $k$ and replace full enumeration of deviations with a sampled best-response oracle for the deviator. For the correlator, we will try a pairwise-marginal (local-polytope) relaxation. This part is exploratory because the relaxation can produce marginals that no joint distribution realizes. We will therefore always report the realized coalitional gain of profiles actually sampled from the recovered distribution, never the relaxed objective.

Baselines

The naive reference is alternating entropic mirror descent with $\beta=0$. This is the method whose global guarantee Nan et al. establish only for interior equilibria, and comparing against it isolates the single ingredient we add. It is run with the same step-size grid and the same number of payoff-matrix evaluations as the proposal.

The exact reference is a linear-programming solve of the meta-game. It gives the true value, so every method's coalitional exploitability (the gap between the deviator's best response and the value) is measured against ground truth. Wall-clock time and memory are recorded so we can locate where first-order methods start to beat it.

The published method for this solution concept is the Follow-the-Perturbed-Leader approach of Liu et al. We reimplement it on the same meta-games. Its reported result is a social welfare of 1.0 in the Prisoner's Dilemma, against 0.4 for Hedge and Optimistic Mirror Descent. A correct implementation of our method must reproduce the 1.0. No reported result found on Lacuna for MASE on GAMUT random or team games, so we produce that number ourselves.

The strongest existing dynamics for simplex-constrained zero-sum games are MoRM+ and MoMD from Fang et al., who report exploitability "up to $10^9$ times lower than standard RM+ or CFR+" on poker and dice games. We run MoRM+ as-is on the meta-games. Alternating RM+ with linear averaging (the CFR+ recipe) and optimistic multiplicative weights are included as the strongest non-momentum competitors. All methods get the same iteration budget and a tuning budget of the same size, in grid points, over step size and, where relevant, $\beta$.

Beating the baselines means specific outcomes. On boundary-equilibrium meta-games, the last iterate should reach coalitional exploitability below $10^{-6}$ in fewer matrix evaluations than both the $\beta=0$ ablation and the averaged iterate of RM+ and Hedge. It should match or beat MoRM+. Beyond some game size, it should also finish faster than the linear program.

Why not just…?

Why not just solve the linear program? For the small games above, that is the right tool, and we use it as ground truth. The claim is about the regime where an exact solve is not possible: dense interaction graphs where tree-decomposition dynamic programming blows up, and decentralized settings where only sampled gradients exist. The scaling experiments either show a crossover point where first-order methods win or they do not. If they do not, the practical part of the proposal shrinks to the theory.

Why not just use averaged no-regret dynamics like Hedge or RM+? Averaging is legitimate here because the correlator's feasible set is convex, so the average of recommendations is a valid correlated distribution. This is the most serious alternative. The known advantages of momentum and last-iterate methods are rate advantages: $O(1/T)$ against $O(1/\sqrt{T})$ in Nan et al., and Fang et al.'s gains over averaged RM+/CFR+. We will report averaged and last iterates side by side at equal compute. If averaged alternating RM+ matches our last iterate on boundary meta-games, the empirical claim fails and we will say so.

Why not just use optimistic or extragradient methods? They also damp rotation. However, Fang et al. observe that predictive methods like optimistic descent-ascent degrade as game size grows. The file also records that optimistic multiplicative weights diverges on games mixing cooperative and cyclic structure, which is the kind of structure coalitional meta-games inherit from team components of the base game. Optimistic multiplicative weights and optimistic descent-ascent are therefore run as full baselines rather than dismissed.

Why not just restrict players to pure strategies, or restart a local solver many times? Restricting to pure strategies removes the mixed-strategy trap, but pure equilibria may not exist, and Mixed Strategies in Combinatorial Agency shows that purity can cost payoff. Restarts work at small scale: Emmons et al. find the symmetric optimum 87% of the time with ten restarts, and Algorithms for Strong Nash Equilibrium with More than Two Agents reports 95% success with 50 restarts. But restarted solvers optimize unilateral or symmetric objectives, so they still return mixed profiles that coalitions can exploit. We include best-of-10 SLSQP as a reference on team games and measure the coalitional gain of what it returns.

Decisive Experiments

The first check is a controlled contrast. We generate meta-games with a planted unique equilibrium in two conditions: interior (square, full support) and boundary (rectangular, strictly complementary, using the uniform, integer, binary, normal, and lognormal matrix distributions from Nan et al.). The prediction is that $\beta<0$ beats $\beta=0$ substantially in the boundary condition and little in the interior condition. If the advantage is the same in both conditions, the mechanism we propose is wrong.

The second check uses GAMUT random, coordination, collaboration, and polymatrix games with 2 to 5 players and 2 to 5 actions, 100 games per configuration as in Emmons et al. We build the coarse meta-game for each and plot last-iterate coalitional exploitability against matrix evaluations for every baseline.

The third check starts dynamics at Emmons et al.'s mixed symmetric optima in team games. We record whether and how quickly each method reaches a zero-value vertex, and whether the $\beta=0$ method cycles in the interior on the way.

The fourth check reproduces the Prisoner's Dilemma result (welfare 1.0) as a correctness test. It then scales polymatrix games to treewidths where Liu et al.'s dynamic program becomes infeasible, and reports the realized coalitional gain of sampled profiles.

Alongside all of these, we sweep $\beta$ to map how sensitive the method is to the coefficient. That sensitivity is a known weakness of negative momentum, and the sweep shows how much tuning the result actually needs.