Computing Equilibrium beyond Unilateral Deviation
Authors: Mingyang Liu
Gabriele Farina
Asuman E. Ozdaglar
Venue: ICLR 2026 Poster (2026)
Keywords: Strong Equilibrium
Complexity
No-regret Learning
Primary area: learning theory
TL;DR: Fixed parameter lower bounds of strong equilibrium and algorithm that matches the lower bound

Abstract: Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating unilaterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes notions to address multilateral deviations (\emph{e.g.}, strong Nash and coalition-proof equilibrium), these generally fail to exist. In this paper, we study a solution concept that accommodates multi-player deviations and is guaranteed to exist. We prove a fixed-parameter lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound.

Published as a conference paper at ICLR 2026
COMPUTING EQUILIBRIUM BEYOND UNILATERAL DEVIATION
Mingyang Liu, Gabriele Farina & Asuman Ozdaglar LIDS, EECS Massachusetts Institute of Technology Cambridge, MA 02139, USA (1 (1iumy19, gfarin Parriin, asuman @0mit.edu
ABSTRACT
Most familiar equilibrium concepts, such as Nash and correlated equilibrium, guarantee only that no single player can improve their utility by deviating uni- laterally. They offer no guarantees against profitable coordinated deviations by coalitions. Although the literature proposes notions address multilateral devi- ations (e.g., strong Nash and coalition-proot equilibrium), these generally fail to exist. this paper, we study solution concept that accommodates multi-player deviations and is guaranteed to exist. We prove a fixed-pan parameeer lower bound on the complexity of computing such an equilibrium and present an algorithm that matches this bound.
INTRODUCTION
Most equilibrium concepts studied so far, such as Nash equilibrium (NE) Nash 1950). correlated cquilibrium (CE) (Aumann 1974), coarse correlated equilibrium (CCE) Moulin & Vial 1978),
and Stackelherg equilibrium (Von Stackelberg, 2010), guarantee only that no individual player can gain by deviating unilaterally. However, they offer no guarantees when multiple players deviate simultaneously by forming a coalition. In this paper, we address the following question:
What is appropriate notion for capturing multilateral deviations, and how it be computed?
Previous notions that address coalition deviations, such as strong NE (Aumann, 1959 and coalition-proof equilibrium (Bernheim et al. 1987), mostly fail exist in general games (unlike NE). Therefore, instead of searching for a joint strategy immune to all coalition deviations, we focus on computing a joint strategy that minimizes the maximum average gain achievable by any coalition, which is the average of improvements over all its members. In other words, we can compute the most stable strategy profile, even if perfectly stable one does not exist. We refer to this notion as the Minimum Average-Stree
Equilibrium (MASE).
The difficulty of this optimization problem naturally depends on the complcxity of the interactions between players. To formalize this, introduce the Utility Dependency Graph| G(V.E) E), where each player is a vertex. An edge connects two players, and j. if and only if there some player k whose utility is affected by the actions of both and j. Intuitively, the actions of and j are linked, as they jointly influence the payoff of some player k. This graph provides clear map of the game's interaction structure, and its properties can help us understand the computational complexity of finding the MASE. For games with simple interaction structures (e.g.. sparse Utility Dependency Graph). one might expect to compute the MASE efficiently.
edge (i, signifies that
However, computing the MASE is computationally challenging in the general case. We establish two key hardness results that delineate the problem's 's complexity.
First, the problem is fundamentally harder than finding equilibria like NE or CE. In those cases, we are solving feasibility problem: finding a strategy where the maximum gain from deviating is at
In this paper, we use the term strong equilibrium to broadly refer to any equilibrium concept that considers multilateral deviations.

---

Published as a conference paper at ICLR 2026
most zero. For MASE, we must solve optimization problem: minimizing this maximum gain. This distinction is crucial, and we show that even for the simplest case of single-player deviations (i.e., coalitions of size one), approximating the MASE value to within factor that is inverse poly- nomial the number of players is NP-hard. This indicates that even without considering complex coalitions, the problem is intractable without additional assumptions the game's structure.
Second, we show that this complexity is intrinsically tied to the structure of the Utility Dependency Graph] Building on the strong exponential time hypothesis (SETH) (Impagliazzo & Paturi] 2001) (see Theorem 4.3 for details), we prove that solving MASE requires time that is at least exponential in the treewidth of Utility Dependency Graph This holds even when we only consider coalitions of a constant size. This result demonstrates that the treewidth is fundamental barrier, and an exponential dependence on it is unavoidable.
Finally, we present a positive result that matches the lower-bound time complexity, up exponential factors. We develop an algorithm that computes the MASE with time complexity that exponen- tial in the treewidth of the Utility Dependency Graph] This demonstrates that our hardness result tight and establishes the treewidth as the definitive parameter characterizing the complexity of computing the MASE. While the problem is hard in general, it becomes tractable for games where the underlying interaction structure not too complex.
To summarize, contributions are follows:
1. Complexity characterization: We establish lower bounds on the computational complexity of computing the minimally deviated equilibrium, showing that the problem is inherently tied to the treewidth of the Utility Dependency Graph]
2. Algorithmic contribution: We design an algorithm that efficiently computes the minimally deviated equilibrium, achieving a running time that matches the established lower bound up exponential dependence treewidth.
2 PRELIMINARIES
For any vector T we use x; denote its 7th element and ||0||| denote its p-norm. By default, ||>|| refers to the 2-norm. For positive integer N, let :N]==1] 1,2, ... (n - 1) -ddddmensional probability simplex by A" == {a E [0, 1]": E z; 1}. More generally, for any discrete set S, let |.S] denote its cardinality and write A for the probability simplex over S, whose coordinates are indexed by elements of S' (e.g., A = Al")). Similarly, H denotes the |S|- dimensional real vector space with coordinates indexed by S. For any set S, S2. S1 x S2 denotes the Cartesian product of sets S and Sz. Finally, we let 11 (argumennt) denote the indicator function, which equals the argument is true and 0 otherwise.
.., N. We denote the
2. GAMES
A game is represented tuple (N, + where
is the number players.
A; is the action set of player i. For convenience, let A == X A, denote the joint action set.
U4 A [0, 1] is the utility function of player i [N].
S is the set of coalitions, which is a set of subsets of players. For example, if only unilateral deviations are allowed (as in Nash equilibrium or coarse correlated equilibrium), then S =
{(1}, (2).... (N}).
For notational simplicity, for any subset of players S C [N]. we write As = Xies Ar. Throughout the paper, let A m |Ag] denote the size of the largest action set.
For any joint action a E A, let denote the action of player i, and let a_; (a), ....... . di+l....... ... aN) be the joint action of all players except i. More generally, for any subset S S [N]. we write a s for the joint action of players outside S.
Treewidth can be thought of formal measure of how sparse and "tree-like" graph is.
2

---

Published as a conference paper at ICLR 2026
Confess (C)
Defect (D)
Confess (C)
(0.6, 0.6)
(0.
Defect (D)
(1,0)
(0.2, 0.2)
Table I: Utility matrix of the Prisoner's Dilemma. Each entry (a, b) denotes the payoff of the row
player (a) and the column player (b).
2.2 SUCCINCT REPRESENTATION
This paper focuses on multi-player games with a succinct representation. Specifically, each utility function Ui be encoded using a number of bits polynomial in the number of players N, rather than requiring O (N II= IAi)) bits as in the general case. Examples of succinctly represented
games include polymatrix games (Howson Jr 1972 Laves 1973) and congestion games (Rosenthal 1973]. Throughout the paper, call an algorithm efficient if its rumning time is polynomial in N, as opposed to polynomial in II [Ag]. We focus on succinct games because MASE can otherwise be solved by linear program whose size grows exponentially with N (see Section B). Moreover, the study of strong equilibrium is particularly compelling in large games, where exponential dependence on N is computationally prohibitive.
3 MINIMUM AVERAGE -SRRON EQUILIBRIUM (MASE)
Several notions of strong equilibrium have been proposed, including the strong Nash equilibrium (NE) (Aumann 1959), the sum-strong NE (Hoeter 2013) (no improvement on the total gain of any coalition), and coalition-proof equilibrium (Bernheim et al. 1987). However, none these exist in general games. To build intuition, first illustrate why strong NE does not exist in the Prisoner's Dilemma. We further show that the problem persists even when correlated strategies are allowed.
Lemma 3.1. In the Prisoner's Dilemma, no strong Nash nor strong correlated equilibrium exists when ((1) (2), (1,2)} is the set of all non-empty subsets of players.
Since correlated equilibria include all Nash equilibria, it suffices to examine strong correlated equi- libria. A strong correlated equilibrium is correlated joint strategy where subset of players (a coalition) can jointly deviate in a way that strictly improves the utility of all its members.
As shown in Table any strategy with positive weight (C, C), (C, D), (D, C) yields profitable deviation for at least one singleton coalition, {1} or (2). Conversely, placing all weight on (D, D) creates a deviation (C, C') that benefits the coalition {1,2] 23. Thus, no strong NE exists.
The failure of strong equilibria arises because coalition objectives may conflict, making it impossible find strategy that simultaneously satisfies all coalitions. Motivated by this, rather than requiring exact immunity to deviations, we instead seek to minimize the incentive to deviate since minimizer always exists by Weierstrass theorem. This leads the following definition of Minimum Average- Strong Equilibrium (MASE):
E argmin max max TEAA SeS agEAs
Σ Ba-x x [4, (ās, a as u4 (a)).
(MASE)
JS]
Intuitively, (MASE) selects the correlated strategy π E A that minimizes the maximum average gain attainable by any coalition across all possible coalitions. If this value is less than or equal to zero, then no coalition can simultaneously deviate in way that yields a strictly positive total gain. Note that the algorithm presented in this paper can also be extended to handle any weighted average over the coalition.
correlated strategy π E A is called an e-MASE
Eawa Mi (ās, a) -U; (a))
SES a.AAA
S
sES
< max max SES ageAs
Bart [2 (ās, a a-s) U1 (a)) +c.
iES
3

---

Published as a conference paper at ICLR 2026
A Strong Nash equilibrium requires that for any deviating coalition, least member does not strictly improve their utility. In contrast, c-MASE aims to minimize the average improvement over all players within any given coalition. From another perspective, e-MASE minimizes the incentive to deviate, even when coalition members can freely reallocate utility within the coalition.
4 HARDNESS OF SOLVING MASE
Recall that we call an algorithm efficient runs in time polynomial in N. In this section, we first establish the computational hardness of computing e-MASE.
Theorem 4.1. Computing e-MASE is NP NP-hard, even when S only contains singletons (coalitions of size one) and 1/e is polynomial in the number of players.
The proof is deferred to Section C Importantly, Theorem 4. highlights a fundamental distinction from the case of CCE, which can be computed efficiently (Papadimitriou & Roughgarden 2008 The reason is that for CCE it suffices to find a correlated strategy E A such that the deviation gap, g maxa, Ea-w [24, (ā,, a-i) 24 (a)]. is less or equal to zero, whereas here we must find a strategy that minimizes the gap. Together with the linear programming characterization in Section B this implies that computing c-MASE is actually NP- NP-comp ete. In fact, Anagnostides et al.] (2025) recently showed that even minimizing the average deviation gap of CCE across all players (instead of the maximum gap considered here) is also NP-comples
4.1 FIXED PARAMETER LOWER BOUND
Next, we present a more refined hardness result: a fixed- -aeddparrameter lower bound for computing MASE. To do so, we first formalize the notion of dependencies among players' utilities.
For each player i E [N], define the relevant set (ii) S [N] consisting of all players E [N] (including j i) such that the action of can affect the utility of i. Formally, j E [N] is in (i)) and only if there exist a-j E A_, and aj, a'j E Aj such that Ui(aj, + Uilay a amj). This leads to the following graph representation.
Definition 4.2 (Utility Dependency Graph). The utility dependence graph g = (V,E) is an undirected graph with vertex V [N] representing the players, and edge set E UNE[N] {(i,)) J E i(k))
i
Since Us depends only the actions of players in Mi).. we may equivalently write U:(ac)
Ui(ac; a'c)) for arbitrary a'c E A_c. where C 2 Mi).. It is worth noting that this definition differs from the graph of graphical game (Kakade et al. 2003 Kearns al., (200)) Here, players and are connected if both influence the utility of some other player k. even if à and j do not directly affect each other. Whereas in graphical games, two players and j are connected if and only if at least one can influence the other's utility.
With this graph structure in place, we can connect the hardness of computing MASE to the treewidth of G. Intuitively, treewidth measures how close graph is to being a tree: the treewidth of g is one when G is tree, and it is N when a complete graph. Throughout this section, let O" denote asymptotic complexity with factors polynomial in N suppressed.
Theorem 4.3 (Treewidth). Suppose a tree decomposition of the Utility Dependency Graph is given. Under the Strong Exponential Time Hypothesis (SETH) (Impagliazzo & Paturi 2001 (MASE) cannot be computed in O* ((A () (G) for any Ç 0. Moreover, under the additional assumption that BPP=P
9N approximate MASE cannot be computed in O* ((A ())w(()) for any Ç >>> 0.
The proof is deferred to Section C.2 For approximate MASES we assume BPP-P, which is standard
in the literature (Arora & Barak 2009). because the reduction involves sampling joint actions from
SETH assumes that SAT cannot he solved in O' ((2 - ")" for any Ç > where the number of variables the SAT instance.
"This assumption implies that any problem with polynomial-time randomized algorithm also has polynomial-time deterministic algorithm.
4

---

Published as a conference paper at ICLR 2026
the approximate MASE. Since enumerating all E A is computationally infeasible, we rely randomized sampling. This yields only a randomized algorithm for the original NP Ne-hard problem, and the assumption ВPP=P ensures that such a randomized algorithm can be derandomized into deterministic one, completing the reduction.
Theorem 4.3 shows that the computational complexity of solving MASE is inherently tied to the treewidth of the [Tiiiity Dependency Graph] Intuitively, when the treewidth is large, each player's utility depends on many others, making even the evaluation of coalition deviations computationally demanding (enumerating over all äş E As). In contrast, when the treewidth is small, such as zero (each player's utility depends only on their own action), computing MASE becomes trivial, since each player's utility can be maximized independently. In polymatrix games (Eaves) 1973), the treewidth of the Utility Dependency Graph can be bounded by that of its corresponding graph. Further details are provided in Section
5 EFFICIENT COMPUTATION OF MASE
Although an MASH lives in an exponentially large space (of size |A),, it can still be computed efficiently. This because the equilibrium always admits a compact representation.
Theorem 5.1 (Efficient Representation). For any 2 0, at least one of the e-MASE can be repre- sented as linear combination of Eses [S]-A + pure strategies, where tw(g) is the treewidth of Utility Dependency Graph
The proof is deferred to Section D Intuitively, Theorem 5.1 shows that there must be e-MASE that always has a sparse representation. Since a pure strategy can be encoded by the index of its unique action with nonzero probability, this compactness makes computation tractable.
5.1 META-GAME BETWEEN THE CORRELATOR AND DEVIATOR
reformulate the problem as mela-game between two players: the To compute an (AASE
correlator and the deviator (Hart & Schmeidler 1989). The correlator chooses the correlated strat- egy x A while the deviator selects deviations. The game is zero-sum: the correlator aims to minimize the coalition's 's gain from deviation, and the deviator aims to maximize it. Formally:
min TEAM
F(T,)),
(5.1)
HsAeses** As
where
((S,as) |S|
F(T,H)
Σ Σ
Eanz Ui (ās, a-s) U4 (a))
(5.2)
SES E
Here, extend the deviator's decision space from discrete to continuous set. This relaxation does not strengthen the deviator, since the objective is linear in J., and the maximum is always attained extreme point. Therefore, (5.1) is equivalent the original definition in (MASE).
natural idea is to apply no-regret learning algorithms simultaneously for the correlator and devi- ator. However, directly updating the full distributions æ and μ infeasible, because the underlying spaces are exponentially large.
implies that maintaining the full distributions unnecessary: it suffices keep track of a polynomial number of pure strategies, and use their convex combination as the ap- proximate equilibrium. This motivates our use of Follow the Perturbed Leader (FTPL) (Hazan al.) 2016), where each decision at timestep is pure strategy, which can be represented compactly.
Fortunately, Theorem (.T
Let π E A and (t) E A As denote the decision variables at timestep t 2 for the correlator and the deviator, respectively. The interaction between these two players can be described
5

---

Published as a conference paper at ICLR 2026
Udiiiy Dependence Graph
Tree Decomposition
# (1,3,4)
(1.2,4)
(3.5)
Figure 1: An illustration of a tree decomposition of the Utility Dependency Graph
by the update rule
(1+1) E argmin TEA
(T.)((t) - .T) TT)
(5.3)
((+1) argmax
Σ (1) + (m
(
e As
where ((++)) and (++1) are noise vectors sampled independently each timestep from some distribution, which will specify later. These noise terms play the role of regularizers in on- line mirror descent (OMD) (Hazan et al. 2016), ensuring stability in the updates by controlling [[++1 - [0]]]] and E
Since F(z, (1) is bilinear in (T) both the minimization and maximization problems admit solu- tions at vertices of their respective decision spaces. In other words, the argmin for the correlator and the argmax for the deviator always contain least one pure strategy.
In what follows, we will explain detail how to update efficiently under this framework. The update of y is deferred to Section
5.2 EFFICIENT UPDATE OF
The key step in updating (++1) is to select pure strategy, i.e., joint action (+++)) E A with (+++1) (a((1) = 1, that minimizes the objective. To gain insight into this update rule, we first examine how compute argmin F(z, (1) for fixed μt.
Suppose we want to find a joint action E A such that the pure strategy से with 7(@) minimizes F(T,p). p). Expanding the definition, we obtain
p(S, ās)
F(
Σ
Σ
(l, (ās a) - U4 (a)
SS]
SES: iES agEAs
M(S, ās)
Σ
Σ
Σ
(U; (āsnvva) aw(ns) U, (āv())
[S]
SES:iES asEAs
Therefore, for each candidate E A, only the local actions äN(s matter for the expression above. If we can evaluate this expression efficientlyftheen for each player E [N] may search for ( that minimizes it. However, a difficulty arises because (i)) and N((j may overlap across different players. Hence, we must ensure that the local assignments remain globally consistent.
To address this, we now introduce the concept of tree decomposition and show how it enables us optimize F efficiently. Throughout the paper, we assume that a tree decomposition is given, and analyze the complexity only with respect to this decomposition.
Tree decomposition. A tree decomposition Graph G (V,E) is tree with K nodes (bags), each B C V where V [N], satisfying the following properties (Diestel 2025):
B¹ B² ..... BK of the Utility Dependency
Thiis possible since y linear combination of pure strategies when updated according 5.3

---

Published as a conference paper at ICLR 2026
1. U B== [N].
2. For every edge (i,j) E, there exists l with {i,}} S B
3. For any player E [N], if i appears in two bags B, B' E TT, then every bag on the path from B to B' also contains
As illustrated in Figure I the tree decomposition separates the game into overlapping bags. For example, since B and B only overlap B', then B and B can be optimized independently, with consistency later enforced at B
Since any clique in G is contained in some bag (Diestel 2025), for every player i [M] there exists a bag with (i) C B. We arbitrarily assign each player i to such a bag.
Dynamic programming on the tree. We begin by choosing an arbitrary bag as the root of the tree decomposition and denote it by B". For each bag B E T, let C(B) denote the set of its children. With this setup, we maintain a vector d(t-1) E RRreer Ae, defined as
(B, aB) = Σ
Σ
Σ agEAs
n (S, as) (4: ((asn,, Ui (a(a))
S
SES
SES:
ussigned to B
Σ
min By Egg
(B',)) -n (t41) (tt)
B'EC(B)
ageg a Bna
(5.4)
where n (2,1) an) ~ Exp (17 sampled from an exponential distribution. Therefore, in 5.3 n((+) (a) = BET (1(+1) B, aB). Since each assigned to B satisfies (ii)) S B, the utility Ui(a)) can be written in terms of ag alone. Moreover, the summation EāgeAs can be computed efficiently, since nr(*) is updated via 5.3) and is therefore pure strategy.
Reconstructing the strategy. The optimal joint action (++1) A is then reconstructed recur- sively from the root B" to the leaves:
((+1)
argmin dB++ .B))
a
ag EA
(5.5)
VB E C(B), a BBB"
a (t+1) argmin ( (B. (a ((BB))
any EAn
By Property of Tree Decomposition every player's action will be included. Since argminl an gr EA is taken over AB,Br, no contradictions arise by Property of Tree Decom- position We then set 7 ((++1)(a =1
The regret bound of this procedure is summarized below.
Theorem 5.2. Consider (5.3). For any 8 O, with probability at least 6, the following holds:
T Σ (1(0 F n1()) S 21 1+ (tw(g) log + 2n [T| 27 log 8 REA-
1
mAx
The proof is given in Section Importantly, Theorem 5.2 shows that by setting 7 = 1/VT, we obtain ((VT) regret. Since the update rule for μ mirrors that of æ, the detailed analysis is deferred to Section G We now formally state the regret bound for y in the following theorem.
Theorem 5.3. Consider the updates in (.3)
For any
O, with probability at least - 8, the
following holds:
max
ΣF Fm(( F (1) (1)))
$2 + (tw(g) + 1) A
+ T 2T
Kses As
17
The complete proof is provided in Section G
'Pr(x w) exp(-nw) when Exp (n).

---

Published as a conference paper at ICLR 2026
5.3 COMPUTATION OF EQUILIBRIUM
For any 8' > O, by setting 8 & in Theorem 5.2 and Theorem 5.3 and applying the union bound, we obtain that with probability at least 8', the following holds:
Σ F (1) 1=1
F n (1
max K
min REAM
I=1
(5.6)
< <117] 1 (LW(g) + 1) log A + 4n [T| T + 2 log 8
We now connect this bound the convergence of the average strategy profile. Let x . be the solution to 5.1). and define the average strategies ग = + Ei= T(t) and ş = 7 Σi= 1(9) The
left-hand side of (5.6) corresponds to the duality gap: max, م max Since TT, 1 are optimal solutions to (5.6). they satisfy
Kses Ay F(T, -mnneEA ()),
min F(R, S F( p²)
max F(T, P))
REAM
DEA Gse Ag
Combining these pieces, we arrive the following finite-time convergence guarantee:
Theorem 5.4. Let x², 14" be the solution of (5.1 and define = ΣT= 7(1), p= E Then, for any > 0, with probability at least 5, we have
F( (), S F("", + 4|7 + (tw(9) 1) log
log
max iEλ As
+ 4n [T| + 21
n/
T
the average strategy constitutes an O (w))) log A+ log
With 1 VT
-MASE. The overall
vT
running time (T [S] [T] (ww())))) Hence, the exponential dependence aligns with the lower bound in Theorem 4.3
EXPERIMENTS
In this section, compare our algorithm against several baselines: Follow the Regularized Leader with a Euclidean regularizer (FTRL), Hedge, Follow the Perturbed Leader with an exponential noise distribution (FTPL; all players run FTPL independently), and Online Mirror Descent with Eu- clidean regularizer (OMD) (Hazan et al. 2016). We also plot the ground-truth MASE computed via linear programming (LP) in Section
We evaluate the algorithms on three criteria:
Exploitability, (max4e(N) maxa, EA, Eg (ā, a_;) U, -4
the maximum gain single player can obtain by deviating unilaterally. Exploitability S indicate a Nash equi- librium (or correlated equilibrium if is correlated).
Coalition exploitability. (max WEAxSES= As F(T,P)) the maximum average gain when coalition deviates simultancously. We take S to be the of all non-empty player subsets. Social welfare. (2i)) Ea-a [2, (a)):: the sum of all players' utilities.
Utility definitions and additional details are provided in Section H In the Prisoner's Dilemma (Luce Raiffa 1957). ) the MASE corresponds to players choosing (C, and (D, (D,C) with probability 0.5 each. yielding social welfare of 1.0. In contrast, because the unique NE/CCE in this game (D, D), the basclines converge to that outcome, with a lower social welfare of 0.4. Thus, in the Prisoner's Dilemma, MASE promotes cooperation and achieves higher utility.
In the Stag Hunt, there are two Nash equilibria, one of which attains higher utility. As shown in Figure 2 all baselines converge the worse equilibrium, whereas MASE converges to the better one. Finally, in terms of exploitability (unilateral deviations). MASE remains close to the baselines, while the baselines substantially more fragile multilateral deviations.
8

---

Published as a conference paper at ICLR 2026
Prisoner's Dilemma
Exploitability
0.3
Coalition Expl.
Social Welfare
1:2
1.0
0.2
0.3
0.
6.1
02
0.6
0.0
01
5000
10000
5000
10000
5000
10000
Timestep (t)
Timestep (t)
Timestep (t)
Stag Hunt
Coalition Expl.
Social Welfare
0.6
Exploitabilty
0.3
0.2
0.1
0.
10
0.0
47
5000
10000
5000
10000
5000
10000
Timestep (t)
Timestep (t)
Timestep (t)
MASE
FTRL OMD
Hedge
Maximum
FTPL
LP
Figure 2: LP denotes the linear programming solution from Section B and Maximum denotes the maximum achievable social welfare. The baselines are comparatively fragile to multilateral devia- tions, while MASE more robust and achieves higher social welfare. At the same time, MASE's exploitability is close to that of the baselines.
6.1 TRADE-OFF BETWEEN EXPLOPTABBILIT AND SOCIAL WELFARE
In Figure see that by allowing exploitability increase from 0.0 to 0.1, the social welfare of MASE increases from 0.4 to 1.0. This raises a natural question:
Given tolerance 2 O, what the maximum social welfare achievable by an equilibrium with exploitability at most c?
In other words, if we are willing to sacrifice equilibrium robustness, how much can we improve social welfare? Interestingly, this trade-off can be computed efficiently using variant of our MASE framework. Specifically, we solve the following weighted objective:
argmin max max TEAM SES agEAs
Wt S
Easx (4, (ās; as 44 (a)),
(6.1)
where w E S is vector of non-negative weights. We have the following lemma.
Lemma 6.1. For any e > 0, computing the CCE with exploitability no more than that maximizes social welfare is equivalent to (6.1) by setting S [[i))e U [[N] and using the weights:
if S = if S [N]
for E [0, 1). Conversely, solving 6.1 with these parameters corresponds finding point on the Pareto frontier of social welfare and exploitability
we can compute the Pareto frontier by solving (6.1) for different values of w. The results shown in Figure 3 In the Stag Hunt, since one the Nash equilibria already maximizes social welfare, the social welfare remains fixed at its optimal value for all [0, 1).
The proof is postponed to Section H.4 With Lemma 6.1

---

Published as a conference paper at ICLR 2026
Tradc-off between Exploitability and Social Welfare
0:1
Exploitabiiit
Social Welfare
Exploitability
Welfare
0.2
0.00
2.0
0.5
0.0
Weight Individual Rationality (1))
Weight Individual Rationality (1))
Prisoner's Dilemma
Stag Hunt
Figure 3: The trade-off between exploitability and social welfare in the Prisoner's Dilemma and the Stag Hunt.
Coalition Exploitability
Coulition Expl.
0.4
0.4
022
0.0
100
2
3
Players (N)
Size (A)
Expected Interactions per Player
FTRI.
Hedge
FTPL
Figure 4: The coalition exploitability of random polymatrix games of different sizes when coalitions with no more than two players are considered. larger expected number interactions per player (c) generally corresponds to a larger treewidth of the UUility Dependency Graph
6.2 COALITION EXPLOITABILITY IN LARGER GAMES
As shown in Figure the coalition exploitability of the average strategy generated by classical no- regret learning algorithms increases as the game size grows. Note that we only consider coalitions of size no more than two. This trend underscores the importance of minimizing coalition exploitability. As games become larger, the equilibria to which these algorithms converge become increasingly fragile to coalition deviations, necessitating approaches that explicitly account for such multilateral deviations. Further details are provided in Section
CONCLUSION
In this work, we introduced the Minimum Seerage-Strong Equilibrium (MASE), a tractable solution concept that accounts for multilateral deviations by minimizing each coalition's is average incentive deviate. We established that computing an approximate MASE is NP-hard even with singleton coalitions and proved fixed-paine parameter lower bound showing unavoidable exponential dependence on the treewidth of the Utility Dependency Graph] We then designed an cefoorthm-combiinn correlator-deviate meta-game with FTPL updates and dynamic programming over tree decompo- sition, whose running time matches this lower bound up to the treewidth factor. Empirically, MASE is substantially more robust to coalition deviations than standard basclines while improving social welfare in canonical games, all without materially worsening unilateral exploitability.
In the future, it is natural to move beyond uniform averaging within coalitions. A compelling open direction is to characterize lower and upper bounds for objectives that minimize the minimal incen- tive within each coalition. More broadly, extending these ideas to richer coalition objectives would mature the strong equiliiquui framework and yield more solution concepts that go beyond unilateral deviations.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENT
The authors are grateful to the anonymous reviewers and the area chair for their constructive feed- back. M.L. was supported by the MathWorks Fellowship. A.O. and G.F. were supported in part by the ONR grant N000142512296. G.F. was additionally supported by CCF-2443068 and an A12050 Early Career Fellowship.
ETHICS STATEMENT
This paper presents work that aims to advance the field of game theory. There are many potential societal consequences of our work, of which feel must be specifically highlighted here.
REPRODUCIBILITY STATEMENT
The proof and assumptions are stated Sections C
D and G.2
10 USE OF LARGE LANGUAGE MODELS
In this paper, we use large language models (LLMs). For example, by correcting grammatical error. identifying related work reduce the risk of overlooking relevant papers, helping create illustrative figures (Figure and assisting with coding.
REFERENCES
Naman Agarwal, Alon Gonen, and Elad Hazan. Learning in non-convex games with an optimization oracle. In Conference on Learning Theory (COLT), 2019.
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, and Brian Hu Zhang. time algorithm for variational incqualities under the Minty condition. arXiv preprint 0:XYv:2500400342,, 2025.
A polynomial-
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge Uni- versity Press, 2009.
Robert Aumann. Acceptable points in General Cooperative n-person Games, pp. 287-324. Prince- ton University Press, 01 1959. doi: 10.1099//ic/023/01.
Robert Aumann. Subjectivity and correlation in randomized strategies. Journal of mathematical Economics, 1(1):67-96, 1974.
Carl T Bergstrom and Peter Godfrey-Smiin On the evolution of behavioral heterogeneity in indi- viduals and populations. Biology and Philosophy, 13(2):205-231, 1998.
Douglas Bernheim, Bezalel Peleg. and Michael Whinston. Coalition-pree Nash equilibria concepts. Journal of economic theory, 42(1):1-12, 1987.
Marie Louisa Tølbøll Berthelsen and Kristoffer Arnsfelt Hansen. On the computational complexity of decision problems about multi-player Nash equilibria. Theory of Computing Systems, 66(3): 519-545, 2022.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In Symposium Foundations of Computer Science (FOCS), 2006.
Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621-641, 2008.

---

Published as a conference paper at ICLR 2026
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. Communications of the ACM, 52(2):89 2009.
Reinhard Diestel. Graph theory, volume 173. Springer Nature, 2025.
B Curtis Eaves. Polymatrix games with joint constraints. SIAM Journal on Applied Mathematics, 2483)418-423, 1973.
Barış Can Esmer, Jacob Focke, Dániel Marx, and Pawel Rzažewski. Fundamental problems on bounded-treewidth graphs: The real source of hardness. In International Colloquium on Au- tomata, Languages and Programming (ICALP), 2024.
Nicola Gatti, Marco Rocco, and Tuomas Sandholm. On the verification and computation of strong Nash equilibrium. In International Conference Autonomous Agents and MultiAgen Systems (AAMAS), 2013.
Sergiu Hart and David Schmeidler. Existence of correlated equilibria. Mathematics of Operations Research, 14(1):18-25 1989.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
Martin Hoefer. Strategic cooperation in cost sharing games. International Journal of Game Theory, 42(1):29-555 2013.
Ron Holzman and Nissan Law-Yor Yone. Strong equilibrium in congestion games. Games and economic behavior, 1101-2):85-101, 1997.
Joseph T Howson Equilibria polymatrix games. Manugement Science, ((5-part-1):312--11 1972.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001.
Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz. Correlated equilibria in graphical games. In ACM Conference on Electronic Commerce, 2003.
Yasushi Kawase and Hanna Sumita. On the max-min fair stochastic allocation indivisible goods. In AAAI Conference on Artificial Intelligence (AAAI), 2020.
Michael J. Kearn,, Michael L. Littman, and Satinder Singh. Graphical models for game theory. In Conference on Uncertainty in Artificial Intelligence (UAI), 2001.
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth probably optimal. In ACM-SIAM Symposium Discrete Algorithms (SODA), 2011.
Duncan R.. Luce and Howard Raiffa. Games and Decisions. wiley, 1957.
Hervé Moulin and J-P Vial. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4):201- 221, 1978.
John F Nash. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48 49, 1950.
Rabia Nessah and Guoqiang Tian. On the existence of strong Nash equilibria. Journal of Mathe- matical Analysis and Applications, 414(2):871-885, 2014.
Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3):1 2008.
Arthur Pigou. The economics of welfare. Routledge, 2017.
Mona Rahn and Guido Schäfer. Efficient equilibria in polymatrix coordination games. Interna-
fional Symposium on Mathematical Foundations of Computer Science (MFCS), 2015.
12

---

Published as a conference paper at ICLR 2026
Robert W Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2(1):65 1973.
Ola Rozenfeld and Moshe Tennenholtz. Strong and correlated strong equilibria in monotone conges- tion games. In International Workshop on Internet and Network Economics, pp. 74-86. Springer, 2006.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader optimal. In Algorithmic Learning Theory (ALT), 2020.
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
13

---

Published as a conference paper at ICLR 2026
A RELATED WORK
In this section, we review the literature on strong equilibrium from three perspectives: existence, time complexity, and computation.
Existence of Strong Equilibrium. Aumann (1959) introduced the strong NE, where no coalition (a nonempty subset of players) can deviate in way that strictly improves the utility of all its mem- bers. However, even in simple two-player games such as the Prisoner's Dilemma (Luce & Raiffa 1957 strong NE does not exist when players can coordinate. To address this, Bernheim et al. 1987 proposed the coalition-prool equilibrium, which restricts the set of deviations. Yet, this con- cept also fails guarantee existence, already in three-player games (Bernheim et al.) 1987). More recently, Rahn & Schäfer (2015) studied the notion of a-approximate k-equilibrium, where no coali- tion of size at most & can deviate improve each member's utility by at least a factor of a 2 1. They further showed that such equilibria exist in graph coordination games only under specific con- ditions, for instance, when a 2 Motivated by these non-existence results, we instead focus on minimizing the maximum average gain from coalition deviations (MASE) a quantity that is always well defined.
Complexity of Strong Equilibrium. Since a strong NE degenerates to an NE when only sin- gleton coalitions considered, computing strong NE is PPAD-hard in general (Daskalakis et al.] (2009) Chen Deng 2006). Beyond computation, Conitzer Sandholm (2008) showed that deciding whether strong NE exists is NP-comp lete in two-player symmetric games, and Berthelsen & Hansen (2022) further established that the problem BIR cem-comp-.. 1 ete for three-player games. Similarly, Rahn Schäfer (2155) proved that determining the existence of strong NE is NP-complete et in graph coordination games, even when restricting attention to coalitions of con- stant size. To the best of our knowledge, however, no hardness results are known for computing strong equilibria when correlation on the joint strategy is allowed, i.e., a correlated strategy immune coalition deviations. In this paper, we show that computing a correlated strategy that minimizes the average gain from coalition deviations is NP-hard. Moreover, we establish fixed seed-parameter lower bound based on the treewidth of the Utility Dependency Graph] demonstrating an inherent computational barrier in solving the MASE considered here.
Computation of Strong Equilibrium. Holzman & Law- Yone 1997) and Rozenfeld & Tennen- holtz (2006) developed algorithms to compute strong NE and correlated strong equilibria in con- gestion games under certain conditions in polynomial time. Rahn & Schäfer (2015) showed that strong NE can also be computed in polynomial time when the graph coordination game is defined on tree. In contrast, Gatti al. (203) proposed a spatial branch-and-bound algorithm for comput- ing strong NE more generally, but its runtime is exponential. Along the same lines, Nessah & Tian (2014) also provided computationally intractable algorithm. Of independent interest, Papadim- itriou& & Roughgarden (2008) introduced an efficient algorithm for computing optimal CE e.g. CE that maximizes the social welfare in graphical games (Kearns et al., 2001] [akadd al.aa2120000 2003) with bounded treewidth, using linear programming. In this paper, we develop new algorithm for computing MASE based on no-regret learning, with a time complexity that matches the lower bound dictated by the treewidth of the Utility Dependency Graph
B LINEAR PROGRAMMING FOR SOLVING MASE
MASE can be solved by the following linear programming
min W
77,00
1
E Baxx (as,a a-) - U4 (a)] VS E S As
S iES
77( (a)
0
Ya A
Σ (a) 1.
aEA
14

---

Published as a conference paper at ICLR 2026
Since
Eawr Ui (ās, a-s)] = Σ
a(a))i(as, a-s)
asA
E Eavn 24 [a)] = Σ {(a)(((a)
aEA
are linear in n, the linear programming above valid. Note that the linear program contains expo- nentially many variables (IT E A), so complexity is necessarily exponential in N.
C OMITTED PROOFS IN SECTION
This section presents the omitted proofs in Section
C.I PROOF OF THEOREM
Theorem 4.1. Computing c-MASE NP NP-hard, even when S only contains singletons (coalitions of size one) and 1/e is polynomial in the number of players.
Proof. We will introduce the allocation problem (NP (ie-hard) and show that it can be reduced to computing the correlated strong equilibrium.
Definition C.1 (Allocation Problem). There are agents and m goods. An assignment X [m] [n] is a mapping from each good to an agent. Agent i's utility is (x(X) for an assignment X. A
stochastic allocation p A [m|!") is distribution over all possible assignments. The egalitarian social welfare (ESW) maximization is defined as
max min pEA[m] vE(n) X X((m]]m)
Σ p(X)u,(X).
(C.1)
For any allocation problem, we can create game with = n m players. The action set of player i i n is A; {0, 1), while the action set of player j > is A, in). For any joint action E A, Ui(a) = u, (a_[))))) for S n when a1 = 02 = = On. otherwise Uj(a) = - us (a(aa)))) For
j > n, Uy = 0. Moreover, let = {{1}. (2) . {n}]. We further define
Σ
(a)u, (a-mx))
ag ay=dy="=aa
Σ aeA:
n (a)u; (a-
02=03= 00=dg=..=0..
Σ
z(a)u; (a-ma))
aEA::
Then, the gap of player 1 is lower bounded by
max (0.1)
Ea-z [24 aa), - U4 (a)] 2 max (a, + (a+ min (a, b)
The equation holds when a is always equal to when 02 = = .... an- Therefore, the optimal strategy should satisfy (mx ((O.... (......)) = Tha 1)) 1.
Then, MASE is equivalent to
MAX
(Taa)u((a
max [ E (mm]n)) xE(m)
min
Σ
[n| (a
(a- (m)) (a-jn));
X|m] EA (m RE(M)
a-(s) [(m]ln]
which equivalent NP-hard to approximate C.1 up 1
C.I.
Finally, according to Kawase & Sumita 2020
Corollary 1), it is
The hard instance constructed Kawase Sumita 2020) satisfies that max; maxxe u(() Poly(n, m) and the solution to (C.1 is Therefore, Poly {) algorithm does not exist unless
P=NP for solving c-MASE.
15

---

Published as a conference paper at ICLR 2026
C.2 PROOF OF THEOREM 4.3
Proof. According to Lokshtanov al. (001)), ) under SETH, g-coloring cannot be solved in O(g - ()tv Poly(I])) for arbitrary graph G, when a tree decomposition of width tw given In the sequel, we construct game such that computing + -approxximate (MASE) is equivalent to determining the g-coloring.
For any g-coloring problem G EV, we will construct game with N [V] + [E] players. For each player i S [V], the action set A, = {1, .......... .2) and the utility function U4 = 0 is constant function equal to zero. For each player j [V], the action set is {1} and the utility function is (a) = (dez-1v1,1 * dez- via) where (C)-IV),1, (--VV1.2 is the (j [V]) edge in E and 1 is the indicator function (cquals one when the argument is true and otherwise zero). this game. S {i 82, [V] lej i2)).
Firstly, for any proper coloring [g]lV the associated pure strategy is T², where TT(a)) 1 if and only if a; = c; and otherwise. satisfies (MASE). Because for any S S (ú, i2 j+ IVD), the maximum of [ST Eies (i(z)) is 3. which is attained when the colors of node i1, different. Therefore, TO obtains the maximum for every coalition E S, which implies the satisfaction of MASE)
Secondly, for any joint strategy A satisfying MASE
we have
(1(T)
1
Eiss
(((T)
Σ (())
1
EiesU(())
min SES
S
|S|
S
S
SES
aEAA
SES
x(a) ll (atvn is not proper coloring)
3
E
GEA
Because there must exist at least one edge with both of its nodes in the same color for any improper coloring. On the other hand, let â x= for some proper coloring Then, for any S E S, we have
Eies (
SS]
Therefore, the approximation error of (MASE) at least
1
Σ T()
(anvv is not proper coloring)
E
for any joint strategy x. When we get डर approximation, since E S N2, we have
Σ (a)) Il (aiv) is not a proper coloring) < aEA
3
Therefore, when sampling n, we will get proper coloring with probability at least 2. which complexity class RP. As result, when P=RP, the time complexity of computing (MASE) is at least O" (Atw(()) where G is the trust graph and is the size of the maximal action set.
D PROOF OF THEOREM 5.1
Theorem 5.1 (Efficient Representation). For any é 2 0, at least one of the e-MASE can be repre- sented as linear combination of Eses [5|. (gw()) + pure strategies, where tw(g) is the treewidth
Utiliy Dependency Graph
7 As summarized in Esmer et al. 2024), the proof of the g-coloring complexity implicitly implies that the complexity is lower bounded by Olg" Poly([/()), even though a tree decomposition of width tw is given. In other words, aside from computing tree decomposition, the g-coloring itself has intrinsic computational barrier.
16

---

Published as a conference paper at ICLR 2026
Proof. Let D Eses Eies (Aswii))- For any joint strategy 8d E ERD, where
A consider the vector
0" (S, (s, Eawa (( a (srW()) [a)a
for any S and (s) Asrwiin By definition of o", it is linear я. Therefore, the vertex set of ( π E A4 should correspond to a subset of A A vertex set, which is the set of all pure strategies.
By Carathéodory's 's theorem, for any n² E A vt be represented the linear combination of
D + 1 vertices, which further implies it can be written as a linear combination of D + 1 vectors in {u² I is pure strategy]. Then, when vx >EET A with X A and x n are pure strategies, due the linearity of v", we have
D+1
D+1
N = =wEks xt*
17
k=1
Finally,
Eant Ub (ās, Lu (a)
SES EsEA
Bava [t ((sn)e)) uu (a)
SES EsAAs
S
iES
max max
(S, (S,
SES asEAs
S
iES
D+1 x* @s,i,)sn)())
max max
SES EgEAg
S
iES
there exists linear combination of D pure strategies also satisfying (MASE). Given N(i) S tw(G), we have D < Eses [S] (G)(
Hence, n² satisfies (AASE
E THE OPTIMALITY OF DYNAMIC PROGRAMMING ON TREE DECOMPOSITION
This section shows that the dynamic programming (e.g., (5.4) will compute the optimality. Let u; (aN() be the contribution of player i's utility to the final objective. Recall A == ns. Then, in (5.4)
u, (aN()) =
Σ Σ
u (s.an?)) (u (āx;, U4 (((a())) axSEAxy
S
SES
iES
at timestep t. We consider the following update rule in this section, which generalizes 5.4 and G.I (see the proof of Lemma F.3 and Lemma G.I.
N(BaBB)
u((a())+ B'EC(B)
max EAgrt aana
h(B', d'gr).
(E.1)
SE[N]
assigned to B
In the following, we will show that
E..
optimal.
Lemma E.1. For any bag B E T. let st(B) = {it, assigned to B U UBBEC(B) st(B') be the set of
players assigned to B and bags in its subtree. Then, for any bag B E T and ag E An, we have
h(B, aB)
max
Σ u((a(())
(E.2)
(EM(B)
17

---

Published as a conference paper at ICLR 2026
The proof is postponed to the end of this section. Note that for the root bag B", since st(B") [M],
Lemma E.1 implies that E h(B", agr) m Ei=1 (aw())) Therefore, we find the maximum of Ei=1 u:(aN(()) and the optimal joint action E A can be extracted recursively. Specifically, let
a
argmax h(B,, aBr)
EAg
(E.3)
BB E C(B),, B\B"
argmax @B
(B. (aB,
(1+1) (BnB-)
We will do this recursively until we find the whole a' A. The tie- tie-breaking rule can be arbitrary, and we use the lexicographic order of joint actions for simplicity. Hence, we prove the optimality of the update rule (..Tp
L
Lemma E.1. For any bag B E T. let st(B) = {i}, assigned U U st(B") be the set of players assigned to B and bags in its subtree. Then, for any bag B T and ag AB, we have
h(B,an) a BEAA (E
Σ us(ax()).
(E.2)
Proof. For leaf bags B (C(B) = 0), for any joint action ag E AB, we have
aB)aa)) = Σ M
u((an)))=
Σ
u,(an())
(
max B
Σ un w.(ax()). (Est(B)
iEst(B)
aasigned
(i) is because (ii) S for any assigned to by definition. Additionally, since B is leaf bag. st(B) = {i E B: i assigned to B}.
Then, for any bag with of its children B' E C(B) satisfying F.2 we have
h(B,aB) = Σ u.(aN()) +
Σ
max
h(B',
Eg
B'EC(B)
assigned
Bandr=a'ane Bne
Σ
v,(an()) Σ
Σ
u:(a'rro)
max
max g EAA
a Eggr
N i assigned to B
()EC(R)
(Es(("))
Bgnar ene
u.(aN())+
Σ
max a' O'EA;
Σ
u((a'rr))
N i Fasssgged to B
BEEC()) anner = Bow
(ES((")
(i) uses the induction hypothesis. By Property of Tree Decomposition for any B' E C(B) and i st(BB), (ii n (B B3) 0. Because for any st( there must be a bag D in the subtree of B' such that N(1) B". and Property 3 of Tree Decomposition will be violated if A(I) n B \ B' + 0. Then, modifying the constraint a a to ag d's will not change the value of u((a'(()) for any i E st(B). Hence,
h(B.an)
Σ
u((aN()+
Σ max
Σ
u.(awio))
B'EC(B) a d'EA: an (Es(BB)
SE[N] assigned to B
Furthermore, by Property 3 of Tree Decomposition for any B', B'B B" C(B) and 1' E st(B',, 1" st B,", we have (( C. Finally,
h(B,8))
Σ
u:(ax()) + max a'EA: an=aj
Σ
Σ
u((av1o)
V i assigned to B
BIEC(B) (E
Σ
u((an()) Σ
Σ
max a BEA
NE|N: assigned B
B'EC(B)
max
u.(av()))
a- A-A-AAA-
1Est
18

---

Published as a conference paper at ICLR 2026
This completes the induction.
F PROOF OF THEOREM 5.2
Theorem 5.2. Consider (5.3) For any 8 >> O, with probability at least 8, the following holds:
T F (1 u0)) F (1) s 2 1 (tw(g)
+ log A + 2n T
27 log
8
REA
"
t=1
Proof. The proof of Theorem 5.2 can be decomposed into three steps.
Firstly, we show that without loss of generality, if FTPL with fixed noise ñ for all timesteps t == ....... attains sublinear regret when the adversary is oblivious then FTPL with independent noise vectors (t) also attains the same regret confronting an adaptive adversary. The reduction to the oblivious setting is common in the literature (Agarwal al. 2019; Suggala & Netrapalli 2020). and we include it here for completeness.
Secondly, we will show that the regret of a fictitious E(E F (()) + (7((+)) x) is sublinear.
algorithm
x (++1)
E
argminges4 Finally, we will show that the regret of (5.3) and that the fictitious algorithm are close.
F.1 FIXED NOISE VECTOR
In this section, for completeness, we will show reduction from an adaptive adversary obliv- ious adversary. For ease of representation, we will take correlator (π) as the no-regret learner, and the deviator (μ) the adversary.
An adaptive adversary determines the utility function at timestep t, which is p(() in this section, according to our past strategies, ((1), z(!)...., ((t-1), In contrast, an oblivious adversary determines all utility functions, i.e., "!!")..... (()), at the beginning (timestep 0), such that μ(() is irrelevant (1)), ((--1), In the following, we will show that a sublinear regret against an oblivious adversary implies sublinear regret against adaptive adversary.
ū()) are independent, n only depends on (1) (((t1), which is known to both the oblivious and adaptive adversary, due to the update rule 5.3 Hence, an additional observation on =(1) .(1),...,,7*. ((-1) does not make adversary more powerful. Formally, we have the following lemma (Cesa-Bianchi & Lugosi 2006 Lemma 4.1).
Intuitively, when the random noise (2)),
Lemma F.1 (Reformulation of Lemma 4.1 in Cesa-Bianchi & Lugosi (0066). Consider any ran- domized no-regret learner and the distribution of the decision variable (7( fully determined by ( j (f-1),, Assume the no no-regret learner's regret against any sequence of p()). ( (T) gen- erated by oblivious adversary satisfies that
T
E E (
max REA t=1
F
(1))
(1
(()))
(7,
S R.
Expocted Regret
Then, for any sequence of ()),.... probability least 1 - ò, we have
..... (T) generated by adaptive adversary and å > 0, with
T
max REAA
F
(R, S R+
2T log 8'
$ "An oblivious adversary will choose all the utility functions at timestep 0, while an adaptive adversary will choose the utility functions timestep according to = (2) x (1-1).
19

---

Published as a conference paper at ICLR 2026
It is easy that the distribution of (+() generated by 5.3). whose randomness is induced by (t()) is fully determined by (1(),, ((t),..,/((t11)) given ( is generated by fixed distribution independently at each timestep.
Then, we will show that the expected regret of FTPL using independent noise vectors and FTPL with a fixed noise vector is the same, while facing an oblivious adversary.
F (1) ml0)
E R ((r) (F((0)
B
F (TT(),1100))
E (
(i) uses the fact that both (1) and ( are independent of ū! ..... (1-11)
when the adversary
controlling f is oblivious. Finally, the expectation Bg(1) [F (T((1) [1()))]]
of
π (1+1) arggin Σ F (TT. (1
#EAM
is equal to Eay [F (T111, (()) when n1 and (1) are sampled from an identical distribution. In summary,
fixed noise and an oblivious adversary (Expectation)
inddependent noise and an oblivious adversary (Expectation)
inddependent noise and an adaptive adversary (High Probability Bound). Hence, the problem reduces to proving sublinear regret against an oblivious adversary with fixed noise vector for all timesteps.
F.2 Low REGRET WITH ACCURATE PREDICTION
The discussion above suggests that we only need show the sublinear regret against an oblivious adversary, when all timesteps share the same noise vector. In other words, we consider the following update rule,
π
(++1) E arggiin
Σ F -
(72, TT
(F.I)
TEAA
where n2 ,..)).......
(T) are identically distributed.
Next, we will show that if the regret minimizer can make the decision x ((+1) with an accurate prediction of ((++1), then we can achieve sublinear regret. In particular, the decision variable at timestep & + 1 is chosen according to (F2).
H+1
x (1+1) E arggiin
Σ F (T. (T. ().
(F2)
TEAA
Actually, we can see that F22 is exactly the original update rule (1+2), Therefore, we will prove the following lemma in the sequel.
Lemma F.2. Consider have
F.2 For any timestep 1 1,2,.... 11)) ,u(2) ,..., and any क A4,
F
- at, (f, n2, +)
(F33
Proof. We will prove the lemma by induction. When t have
F (2) ((())
(T, (2))
- (r F (2) (1 - (F (T(F,1("))
-(7,, ((. -(7,))) + -(ū (() - 7
(ū,
(1)
< n, (2) - 7)
20

---

Published as a conference paper at ICLR 2026
(i) is because xt argmin F (T. (ft, m..
Next, we will show that when F3 holds for t = to. then it also holds for = to + 1. For any f AA, we have
F (1x(+t1),
F (7))l()))
ta+1
1a+1
F
( ,
17
Σ F (
(7, (7, ./) -
(i,, R)
( 1++1
19+1
Σ
F
(T(
Σ π (1++2) (2(7)) - (ni, 72, π x(lttz))
(n, 7)
=
=
F
T (7+1)
ul())
F (T((ot2)) , + nz, x (110+)) - 5)
(i) is because (fo++2) E argmin the induction hypothesis, we have
Dlotl F' ((T)) - (n,, T). Next, by setting ã = xfo0+2) in
to
(T(+1)
,1(t)) F. (x!(0-2), (1, + ( (n, ( (l0022) 7t)
π
n, (2) -1((0+))
(1, -+) x)
n, (2) 7t
F.3 SUBLINEAR VARIATION
In this section, we will show that the regret of FTPL with/without a prediction of n(t+1) is close. Formally, for any AA, we have
F (0 (000))))) - FF (F)
T
Σ F (,((+1),, (2(0)) F (2))
Σ t=1
F (1(0) (20)) - F (x((tt)),
(2, -
Σ F (1) ((())
F (((tt),,((1)
(i) uses Lemma F22
Moreover, since (a)aa [0, 1] for any i [N] and A. we have
max
IF (T, < 1.
REAT
REAXSESAS
Then,
E F (7 (1
F (T((+1)) 11()),1())) (100 S Pr (7 + n1((11))
Hence, we only need to lower bound Pra (T(1) = ((++))) in the sequel. Recall that π. (1) is a pure
strategy with (+)) (a(t) = 1 for some joint action (19) E A. For any bag B E T, let f fa(B) denote its father (fa( B)) = if B is the root). Then,
Pr (t) = x((+2)
Pr (a =a (((11)
(8) Pr (t) (B)Fa(n)) = =a fa(B) fa())
(E)
(t+1)
BET
21

---

Published as a conference paper at ICLR 2026
According to (5.5) each bag B T only determines a Bafaa Since (B,-) is sampled inde- pendently for every bag B, it follows that BBBB. B"AB are independent for B', B" E C(B) with B' + B", by Property 3 of Tree Decomposition Hence, (i) holds.
(6)
For any B E T, to lower bound Pra its lower bound while further conditioning on a "BUfa(B) 's value and n R, J's value.
(t+1) a (a(BB) - BBJB(B (a((B) fa(B)) we will first get
(++1))
(8)
Then, Prü (a
(e) (a(BB a fa
(++1) (e) fa(B) fa(B)) is equal to this conditioned probability in-
((+1)
tegrating over all possible values of a BU)a(B) and nBB,.) .). Formally, we want to lower bound
PB (a (dBufa()) and VaBya((B) AB \ a d'Br)a(B))
(1)
a
(t+1) ( (( a B(FB( a fa(B) [a(B) Busa(B) Bufo(BB
(++1)
(t) a(+1)
n(B, (d' a (B) = a( a (B(B))
for any a' d'ufa(n) ABUSa(B) and a E RAS Then,
Pr (t) (B)aa( = (++1)
inf B))(( fa(m; = =aa(()) an EAnufain): EE
(t+1)
Pg (d)
since Pra (1) (1)
(Bi/a(B) = (++1)
(++1) (e(BB) (a(B) (a((B)
is equal to PB (a (dBBua((B) a) integrating
over d'Busa(B) and æ.
(1) Since B\)(B) = a' (a(B)> for any (By/a(B) E ABra((B)
( {alasFacEs) we have
d (B, ) (B,
d(0) ( aBra(())) (
This can be equivalently written as n (B,a')) (d (B, + +n (B, d(9) (B, (BB (B,(a
Then, a (6+1)
B\(BB = dBB))a(B) is equivalent to
n (B,a')) 2 (d(t+1) (B, + (B, d(+1) (B, (dannaat))
(F4)
(n = (B + d'9) (B. (B,(ammaam)) (B
- d((+1) (d ((o
d (B),
for any (B))a((B) E AB\ In Lemma F.3 we show that the variation of d is bounded by 1. Therefore,
n (BB 2 (B.a') +n
- (d()) )
implies F4
Lemma F.3. Consider the update rule 15.3) For any timestep t. = 1,2,..,, T, bag B E T, joint
action ag Ag, and noise n E RX AB we have
(U++)(B,an) e00) (B, an) 11.
(B,
22

---

Published as a conference paper at ICLR 2026
The proof is postponed to the end of this section. Let
(d (B, d'z) + +n (B, - d01) (d (Byfa(B))).
max
aBy EBB (d'
Note that w only depends on n!)) (.l,,.,,(((.) and æ. Then,
(t) PB
(a Bufa(B). x) 2 (n d/p) 2 w 2 a/a) 2 w)
Pr(n (B, d'z) 2 2
Pr (n (B, d'3) 2 w)
exp (-n) (w + 2))
exp (-npt)
eex (-2n).
(i) is because (B, a'x) ~ Exp(1). Finally, by union bound,
Pr P
(1)) = T x((11)
21 - Σ (1 (1-P% 2 (d'usa(m))
BET
21 Σ
(1 - e (-2n))
BET
21 Σ 2m
BET
=1 - 2n/ (71.
Therefore,
F 12 (2)))()))) - F ( ( (l())
E
1=1
<I
n, (2)
x) Σ E F (2()),(()) F (z((tt)))210))
<I n,
#) 2n IT
Since exp(x) 2 + x for any x E R, (1 exp (-2 (T)) S 2n [T|. Additionally,
E ( ū, (2) }]
(8)
s E 77
|r(
ল ||] <E M 1ol
max n n(B, an) an anEAB
BET
+ log An
2
"
BET
(i) is by Hölder's Inequality. (ii) is because the expectation of the maximum of n i.i.d. random variable sampled from Exp(n) is upper bounded by 1+log a (Agarwal et al. 2019). Furthermore, < B log A < (tw(g) + 1) log A. Hence,
log A
E F (1(0)) 1100) (R. $21T| 1 (tw(g) + log A + 2n [T| T.
T
7
F.4 PROOF OF AUXILIARY LEMMAS
Lemma E3. Consider the update rule (53). For any timestep 1,,,..., T. bag B T, joint
action a E AB, and noise n E RRxee AB we have
(1+1)) (B.an) d (B.an) 1
23

---

Published as a conference paper at ICLR 2026
Proof. Recall Lemma E.1 We can add [T] players the noise player, each assigned to bag in T, with (g(a)) = B,B, aB) so that Nii) B. Recall that u, is the contribution player to the
objective function F. Then, by Lemma E. for any B E T and a E AB. we have
d (B,
min Σ SES(B)
10 m
(aNG))
a- a-nEA_n
where
u; (0) (av(s)
Σ
Σ al (s.axx))) (u (āx;s U((aNo))) for [N]
SeS:
A EAp
(av(a) n(B, aN(a) for the noise player assigned to bag B.
For any noise player, we can see that 1t) (ax()) "; (++1) (ax(s) = O. For any i E [N]. (9) (aN(r) us (++1) (an())
11t+1) (5) (M (āxp, awcons) u((an(o))
S
SES iES
GNSEENN
Σ
((++1) (s.āx²) Uu amoos) u((aww))
|||
SES: IES
ANS EANY
Σ
m(++l) (s.ā
S
EAx
ii) is because Ui (()())) E [0, for any aN(() AN(A)
Recall that by definition, a ( argmax a BEA Eieu(B) u4 (ax()) Then,
d8) (B,aB)
ΣE w (IaNtonn,
())(B)
Σ
ui
(lavion,, (e+1)
a
iEs(B)
Σ (ES(B)
u
(1+1)
(awionn (e+1)
((t)))) + uu
((+1))
(lavtonn. (t+1) / (1011 -u(") (ioionmaa/ot..
wl(t2) (s.
(1+1)
(++1) (aaNonnn a NGABB
Σ
u
(Es(B)
SES:
aNs EAp
((,+))(,
Σ
Σ
((++1) (S, (S.ays))
|S|
SES
(ESns(B)
aws EA
(d(+1) (B,aB)
Similarly, we can get the upper bound that d(') (B, S (B, 1. Hence, the proof is completed.
G EFFICIENT UPDATE OF μ
This section provides the omitted details regarding the update procedure for and presents the complete proof of Theorem 5.3
24

---

Published as a conference paper at ICLR 2026
G.1 EFFICIENT UPDATE OF
The procedure for updating μ closely parallels that of æ. Specifically, we iterate over all coalitions E and, for each S, determine the optimal action as As. To achieve this, we maintain dynamic programming vector Is E BeT An for each S E S, which is updated according to
(1+1) (B (B,ān) 9s
E
Σ aEA
(a) (U1 (B))), Ui (an))
S
iES:
Lassigned to
(B++)) a'y.) + +m (B.
max E.g Ag!
B'EC(B)
ane B Br
At first sight, the ΣaEA appears computationally prohibitive, since A is exponentially large. For- tunately, the update becomes tractable Denote by (T) the joint action selected by T(1), Then G.O simplifies to
recall that x(7) is always pure strategy for 1.
[+11) B, (BBBB) 9s
Σ
(u (aans, - U4 (8 (a))))
:ES: aassigned to
(G.1)
(B', a'g.) ms (t-1) (B, āB).
max EAg
B'EC(B)
agne/= BnB
After completing the dynamic programming updates, we focus on the root bag B" of the tree de- composition. The selected coalition is then S(++1) argmaxses gaxa E 95 (++1) (B", agr). Next, we apply the reconstruction procedure in 5.5 on ggtt+ to extract a joint action ā (++1) E A. Finally, update ((t++1) (s(++1) (((++1)) =
This procedure ensures that can be updated efficiently while maintaining consistency with the tree decomposition structure. Analogous to the update of the regret of this process can be bounded.
G.2 PROOF OF THEOREM 5.3
Theorem 5.3. Consider the updates in following holds:
5.3 For any > 0, with probability at least - 6, the
T Σ
F (TTT1117 - ( ul)) (p(T)),00)) 1=1
1 (tw(g) + lo
max
<2
+ 2n T + 2T log 5
peaXscs As
"
Proof. The proof of Theorem 5.3 is similar to that of Theorem 5.2 By using similar argument as the proof of Theorem 5.2 for any jü E Asses As we have
F ( (1)
F (11), (n))
m 4 21)
Σ
F (1((0) (())))))
(x00),())))
Next, by introducing the counterpart of Lemma
F.3 in the following, the rest of the proof follows
that of Theorem 5.2
Lemma G.1. Consider the update rule 5.3 For any timestep f. = 1,2, T, bag B E T. joint action āg AB, coalition S E S, and noise mn E [Rt As we have
(++1) 9s
(B,ān)
gs (B, an) 1.
25

---

Published as a conference paper at ICLR 2026
The proof is postponed to the end of this section. Let S a denote the coalition and action the deviator picks at timestep I, i.e., (1()) (stO) a(0) = 1. Then,
P (0, (1(tt1))=
(1(1)) =
S (1(t+1) + u1)))
Pr
(((t) =((+1))
II BET
Pr (0) ((++1) ()ja(B) BB)aa()) fa(R)
| |
a ((++) Ja(B)) 8 s((+1)
m
(1)
S - exp (2n(7)).
is because choosing (tt) is equivalent adding a new player in the root bag B", whose action is to select the coalition. Finally, for any 8 > O, with probability at least - 6,
F (1)) , F (m()),((t)
T (tw(g) + 1) log
+ 2n [
2T log g
"
G.3 PROOF OF AUXILIARY LEMMAS
Lemma G.1. Consider the update rule 5.3). For any timestep t = 1, bag E T, joint action nB E Ap, coalition S E S, and noise mi E Rx An we have
(B.āB) 99 (B, 1
9s
Proof. For any e S, the upper bound of
(t+1) 9s
(B, āB) - 95 (t) (B, āB)
can be obtained similarly
the proof of Lemma F.3 by choosing
n u (aN())
Σ
Σ
(a) (U: (āøns, Ui (aB)) for [N]
|S|
iES:
assigged B
4 (aN()) =
for i as the noise player assigned to bag B.
Then,
|u (ax(s) - -
(1+1)
(av())
Σ
Σ
(++1)(aa) (a) (Ui (āBns; aBsS) - U4 (AB))
|S|
iES:
aEA
assigned
Σ
Σ (1+1) (a).
S
TES:
assigned
(i) is by the fact that 24 Bas aBss) _u, (ax) E [0,1]. The rest of the proof follows that of Lemma F3 and thus we complete the proof.
H ADDITIONAL EXPERIMENTAL RESULTS
In this section, we detail our experimental setup and report additional results for two further games: the Chicken game (Bergstrom
Soddfrey-Smine 1998) and Pigou's 's network (Pigou) 2017). All experiments are conducted on 13th Gen Intel(R) Core(TM) 17-13700K @ 3.40 GHz. Error bars for MASE and FTPL indicate lo over 100 random seeds (0, 1..., 99). Across all experiments, set the learning rate n 0.01 and run for T 10, 000 timesteps.
26

---

Published as a conference paper at ICLR 2026
H.1 EXPERIMENTAL DETAILS
For all baselines, we run each algorithm independently for each player, thus the average strategy converges CCE (Hazan al., 2016). For FTRL, Hedge, and OMD, each player E [M] is initialized with uniform distribution over all actions. MASE and FTPL are initialized with pure strategy chosen uniformly random from all pure strategies.
H.2
UTILITY FUNCTIONS
This subsection specifies the utility functions for four games.
Prisoner's Dilemma. The utility matrix shown Table both prisoners confess, they receive reduced sentences. If one confesses while the other defects, the confessor is imprisoned and the defector is released immediately. both defect, both are imprisoned for longer than mutual- confession case to penalize dishonesty.
Confess (C)
Defect (D)
Confess (C)
(0.6, 0.6)
(0,
Defect (D)
(1,0)
(0.2, 0.2)
Table 2:
Utility matrix of the Prisoner's Dilemma. Each entry (a, b) denotes the payoffs to the row player (a) and the column player (b).
Stag Hunt.
The utility matrix is shown in Table 3 A stag yields a higher reward, but it can only be hunted successfully both players choose Stag: solo stag attempt yields nothing. A hare provides smaller payoff but can be secured by single player.
Stag (S)
Hare (H)
Stag (S)
(1,1)
(0.1, 0.8)
Hare (H)
(0.8, 0.1)
(0.5, 0.5)
Table 3: Utility matrix of the Stag Hunt. Each entry (a, b) denotes the payoff of the row player (a) and the column player (b).
Chicken Game Two drivers head toward each other and can either swerve or go straight. If one goes straight while the other swerves, the swerving player "loses." If both go straight, they crash.
Swerve (Sw)
Straight (St)
Swerve (Sw)
(5/6, 5/6)
(2/3, 1)
Straight (St)
(1,2/3)
(0.0)
Table 4: Utility matrix of the Chicken game. Each entry (a, b) denotes the payoff of the row player (a) and the column player (b).
Pigou Network. We use a three-player variant of Pigou's network. Each player chooses fast or slow route. The slow route yields constant utility 0.25. The fast route yields utility 1.5 0.5 (number of players choosing the fast route), reflecting congestion.
H.3 ADDITIONAL EXPERIMENTAL RESULTS
Figure reports additional experiments on the Chicken game and Pigou's network. MASE con- sistently outperforms the baselines in both coalition exploitability and social welfare. In Pigou's 's network, purely self-interested players overuse the fast route, which in equilibrium becomes slow. By contrast, when players form coalitions and consider average utility within a coalition, they share the routes that everyone is better off.
27

---

Published as a conference paper at ICLR 2026
Chicken Game
Coalition Expl.
Social Welfare
Exploitability
0.4
2.4
1.5
6.2
1.
0.0
8.0
5000
10000
5000
10000
5000 Timestep (t)
10000
Timestep (t)
Timestep (t)
Pigou's Network
Exploitability
0.4
Coalition Expl.
Social Welfare
0.2
02
5000
10000
5000 Timestep (t)
10000
5000
10000
Timestep (t)
Timestep (t)
MASE
FTRL OMD
Hedge
Maximum
FTPL
LP
Figure 5: LP refers the linear program in Section Maximum marks the maximum social wel- fare. MASE outperforms the baselines in both games terms of coalition exploitability and social welfare.
Trade-off between Exploitability and Social Welfare
Exploitability
Social Welfare
Exploitabilitt
Social Welfare
1.7
0.1
0.1
1.4
1.6
0.0
0.0
0.0
1.0
0.0
0.5
Weight on Individual Rationality (10)
Weight on Individual Rationality (w)
Chicken Game
Pigou's 's Network
Figure 6: Pigou's network.
The trade-off between exploitability and social welfare in the Chicken game and the
Figure 6 shows the trade-off between exploitability and social welfare in the Chicken game and Pigou's network.
Figure 7 reports the runtime of the algorithm for polymatrix games with varying numbers of players, action set sizes, and interaction densities.
H.4 PROOF OF LEMMA 6.1
Lemma 6.1. For any 0, computing the CCE with exploitability more than that maximizes social welfare is equivalent to 66.1 by setting S = {(i))e[N) U [[N] and using the weights:
W
if S =
WS
1 W
if S = [N]
28

---

Published as a conference paper at ICLR 2026
Runtime (seconds).
Rumtime (sccomds)
500
900
100
100
Number Players (N)
Action (A)
Expected Interactions per Player
Hedge
FTPL
Figure 7: The runtime of the algorithm in different polymatrix games.
for some w E [0, 1). Conversely, solving 6.1) with these parameters corresponds finding a point on the Pareto frontier of social welfare and exploitability.
Proof. For any e > 0, let the strategy that maximizes social welfare subject to its exploitability
being at most c. Let g" = maxaeA N E Basn- [44 (@) 24 (a)) be the maximum gain for the
g grand coalition [N]. Let
Then, by construction, the objective value for nt under 66.1 I is:
c+g"
max max SES agEAs
US
Ba [...]= max (w (exploitability). (1- 11)-ww)-0
S
iES
kg*
I max (we, (1 - -))"") 6 + g
Any strategy with exploitability > would have an objective value > we e4g" which is worse than the value x² achieves. Therefore, any optimal solution to (6.1) must have exploitability at most Since x² by definition maximizes social welfare (i.e., minimizes the coalition gain g²) among all strategies in this set, it must also be an optimal solution to (6.1).
<0"
Conversely, for any w E [0, 1), let T² the corresponding strategy that optimizes Let its exploitability be
max Max Easx' [6 (ō,; a_s) U4 (a)) kE[N]a;E A;EA;
We will show by contradiction that strategy N' exists such that exploitabilityxx) < and SW (r') > SW (T*)) (which implies g' < g", where g' the gain for the grand coalition under r').
Suppose such a exists. We analyze two cases:
Case 1: exploitability(rr)
Since x' has both strictly lower exploitability than x² and g" (higher social welfare), its objective value is max(w exploitability(ar) (1 (1- -w)g'). This strictly less than max(we, (1 w)g"), which is the objective value of π²" This contradicts the optimality of n..
Case 2: exploitability(")) = If > O. choose small 8 > and consider the mixed strategy Tnew = (1 8)T + òz"" where T" is an arbitrary CCE, which is guaranteed to exist (Nash 1950
For any E [N] and à E As, we have:
E Ea-snen [ (ā;, a):) - Us (a)]
Ba [2 (ār, a.:) U4 (a)] d' [1 (āi, a-i) - U4 (a))
( 5)aan [ (ā;, a.:) - 24; (a)
S
(1 8)c.
29

---

Published as a conference paper at ICLR 2026
Step (2) holds because n" is CCE, so its exploitability E."[...] O. Since > 0, the new strategy knew has exploitabilty < e. By contimuity, for sufficiently small 6, SW (Tnew) remains strictly higher than SW (T*) (since SW("') > SW(+*)). This puts us in Case 1, which leads to a contradiction.
If S O, then exploitability(""" 1 0. The objective value for n² is max(wc, (1 w)g") 11-w (1-w)g" (since we I and (1 wwg" 2 0 by definition). The hypothetical strategy has exploitability(z))
0 and g' < g" Its objective value max(we, Since o' < 9" and wo < 1, the objective value of x is strictly less than that of ग which contradicts the optimality of π²
w)g') - (1 w)g'
In all cases, the existence of such x leads to a contradiction. Thus, x² must be solution that maximizes social welfare for given exploitability
I POLYMATRIX GAMES
In this section, we present experimental details for MASE on games with a larger number of players. We select polymatrix games the benchmark for these large-scale experiments. This choice is motivated by their inherent graphical structure, which allows for the efficient generation of instances with low treewidth of their Utiilit Dependency Graph]
We begin with the formal definition. polymatrix game has a corresponding undirected graph g = (VO EU), with yo =[]]. For any joint action E A, the utility of any player is defined as:
ui(a) = E (a,
(L.1)
(i.))EE
where Mi.; A; x A, - 10 represents the interaction between players and j. In other words, only players who are connected in G interact, and a player's total utility the summation of these pairwise interactions.
we construct the Utlity Dependency Graph directly, then the tree decomposition may explode unwillingly, e.g., Figure (). We can that the treewidth of Go is one while the treewidth of the Utility Dependency Graph is three.
Constructing the [Uiility Dependency Graph] directly from the polymatrix game can cause its treewidth to explode. For example. in Figure (a), the original graph G has treewidth of one, while the resulting Utility Dependency Graph has a treewidth of three.
To prevent this, we construct strategically equivalent game (note that this new game is not a polymatrix game). This construction explicitly models the pairwise interactions as new players:
For any original edge (i,j) E EV, we introduce two edge players, ety and ej,i.
Each edge player etg has singleton action set, | 1, meaning it has only a single strategy.
The utility function of an edge player ei is defined the original interaction utility:
Üe., = -.
The utility function of an original vertex player i (one of the original N players) now constant zero: Ut
This transformation is illustrated in Figure (b). The Utility Dependency Graph for this new game, shown on the right of Figure (b), now has a treewidth of max (tw(g"), 2). This method effectively bounds the treewidth and avoids the undesirable explosion.
Next, we show that the new game and the original polymatrix game are strategically equivalent. In other words, for any joint strategy л E A the maximum average deviation gain, maxses maxaseAs [ST Eies Ba-z [4 (ās, a) - 24 (a)), does not change. Recall that since the edge players have only a single action, π E A (a distribution over the original players') joint actions) is sufficient specify the joint strategy in both games.
30

---

Published as a conference paper at ICLR 2026
Figure 8: (a) The original graph G corresponding to the polymatrix game (left) and the Utility Dependency Graph (b) The strategically equivalent game and its Utility Dependency Graph
Lemma L1. The new game described above equivalent to the original polymatrix game, when 3 { s feahessnLeJEe Formally, for any joint strategy ı E AA, we have
Ses
max max
Ban [4 (ās; a s) - 24 (a)) a_s)
SES asEAs
[S]
iES
Easz id (" - il (a)
max max SES agEAs
IS [N]
iE
The proof is postponed to the end of this section. This equivalence allows us to solve the new game instead of the original one. Our algorithm minimize more general objective, maxses maxaş Ws Eies Ea~z [14; (ās, a-s) - U, (a)), for any weight vector w E R We can therefore apply our algorithm this new, strategically equivalent game.
1.1 EXPERIMENTAL DETAILS
We generate random polymatrix games using the following procedure:
Each pair of players (t,j) is connected independently with probability -- where N is the total number of players. This results in an expected degree of for each player in GV.
For each connected pair (i,j), the interaction utilities (i, az) are sampled indepen- dently and uniformly from [0, 1] for all action pairs a; A,, aj E Aj- These pairwise utilities are then normalized according to the formula:
Ui a,) minse[M],acA U4 (a)
maxKEN aE.A Un a ainKK[NI,aE Un
This process ensures that the final total utility (4) for any player E [N] and joint action a E A falls within the within the range [0. 1].
Consistent with the experiments on small games, we average the results over 100 runs for each hyper-parameter setting (using seeds 0-99). All algorithms use learning rate of 7 0.01, and error bars represent a. For these larger games, we set the number of timesteps to T = 100, 000 and uniform action set size |A,| = A for all players E [N].
The hyper- parameters for the ablation studies are as follows:
Ablation on N: A = and c = 1.
Ablation on A: N 30 and e 1.
Both the implementation and the proof only use the linearity of the objective. Hence, any weighted-sum fit into the framework.
31

---

Published as a conference paper at ICLR 2026
Ablation N 30 and A 2.
Furthermore, to accelerate the algorithm, without loss of generality, only need to consider = ((+)))))))))))) jein U ((45) j E [N], E g8) to minimize the coalition exploitability for any coalitions with no more than two players. other words, for coalitions of two players, we only need consider the case when they connected in G As shown in the following lemma.
Lemma 1.2. For any joint strategy x E
AA, by letting S = (fthee U
((,)) j E [N] (i,5) E G"), we have
1
Σ iES
Eawn Ui (ās, a) - -2; (a)]
agE
|5|
max SEffHheM U((J) [[JE[N]AA
max agEAy
Banz (u (ās, a-s) - U: (a)]
|S|
iES
The proof is postponed to the end of this section.
1.2 PROOF OF THE AUXILIARY LEMMA
Lemma L.1. The new game described above equivalent to the original polymatrix game, when
$ { = SU (EssiisENSSEEE JSES Formally, for any joint strategy A we have
max max
Bazz [u (ās, a) - Uu (a)
asEAs
|S|
iES
Eart [ a-((tn)) -i (a)
max max
SEB agE
S n [
VE
Proof. For any S E S, let $ be its correspondence S. Then,
max AgEA
TF. Eann
-ū -i. (a) Ui -1
IS
[N]
iE
max
E Eavn
Ū, (ās, a_s) - (a)
agEAs
SS|
iE3
(it)
Σ
Earn Utes (ās, a-s) Utes (a)
max
Ag
|
iES j: (KJ)EE"
(sax)
Earn U4 (ās, a-s) 24 (a))
agEAg
S
iES
(i) uses the fact that [Ae,,, 1 and 5n [M] = S. (ii) is because U, = 0 for any i E [N]. (iii) is by the definition of Uee and S.
Lemma 1.2. For any joint strategy K E 14, by letting S = ((iHee())
(0,5) | E A E gu}, have
max max SES agEAg
Σ iES
Eanz U4 (ās, a) - U1 (a))
S
max SE(())eMM u((()) [+jj][
max a
Ea-s x 24 (ās, as)) - U4 (a)).
|
iEs
32

---

Published as a conference paper at ICLR 2026
Proof. For any disconnected players j, and S {i.j}. see that
max A
Ba- Me (ass ams) Uu (a))
|S|
RES
< max max a kES
Baxxaa>n Bavn [4 (ās, a- U4 (a)
max max Baa ME (ās, ass) Uk (a))
kES agEAg
max Eavt kES agEAg
E
Uk (ās, a_s,a_s) -Kk, (a)
WE[N]: (RAA)EGO
max max EaNT asEAs
Σ
Uk (āsz a-k) - UR xy' (a)
WEINT: (E. M1 (āss a- - Uu (a)].
max max Eawn KES ag
(i) is because k' & since & E = {i.j} and i, are not connected. Therefore, since the coalition exploitability of $ is upper bounded by the maximum of that of coalitions {i) and (j), do not need to consider {i
Actually, the argument be generalized to coalitions of any size M. If want to consider the coalition exploitability for coalitions no more than size M, then we only need to consider all
connected coalitions of size more than size M by induction similar the proof above. O
33


Reviews:
[{"review_id": "dCGVFvtM72", "reviewer": "Reviewer_D58R", "summary": "The paper proposes Minimal Average-Strong Equilibrium (MASE), an always well-defined correlated strategy that minimizes the average incentive to deviate among all coalitions. The idea is to find a correlated distribution over joint actions that minimizes the coalitions' average gain from deviating (differently from CE and CCE, which only prevent unilateral deviations).\nThe paper proves that computing an approximate MASE is NP-hard even when 1-player coalitions only. It then proposes treewidth-based lower bound via the Utility Dependency Graph (UDG), showing an exponential dependancy on treewidth under the Strong Exponential Time Hypothesis (SETH).\nFor the approximation result, the reduction assumes BPP = P to derandomize sampling. The method computes MASE by recasting it as a two-player zero-sum meta-game between a correlator and a deviator, then running Follow-The-Perturbed-Leader (FTPL) for both sides while implementing each best-response step with dynamic programming (DP) over a tree decomposition of the UDG. The running time scales polynomially in the horizon and number of coalitions, and exponentially in one plus the treewidth of the UDG (as expected, which matches the lower bound up to constants).\nExperiments on standard games such as Prisoner’s Dilemma, Stag Hunt, Chicken, and a Pigou network show lower coalition exploitability and higher social welfare than standard online-learning baselines and a linear-programming oracle designed to compute a MASE for small-sized games, while keeping unilateral exploitability comparable.", "questions": "Why average across coalition members? Can you comnpare average versus minimum or weighted objectives on at least a small examples?\n  \nWhat happens if the coalitions are restricted by size? Can the algorithm and bounds be parameterized by a size bound?\n\nDid you compute the tree decomposition or assume it to be already there? I'd like to see how compute-intensive it is.\n   \nPlease add polymatrix and larger congestion games, and show the runtime as the number of players and, more importantly, treewidth grows.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of MASE is quite nice and it avoids non-existence issues of strong or coalition-proof equilibria. The link to the treewidth decomposition of the UDG is also rather nice. The analysis is sound and the negative dependancy on the UDG's treewidth is quite interesting. The writing is good and the paper's more technical parts are quite understandable. The whole contribution should be relevant to the game-thereotical/multi-agent literature.", "weaknesses": "Experiments are rather limited and consider rather small games. Only matrix and toy congestion games are shown. No larger and more general families such as polymatrix or congestion game instances are considered. Also, no scaling versus the treewidth of the UDG is shown, which is a pity.\nRe: the choice of using an average gain: this is reasonable but also possibly arbitrary and not too strongly motivated in my view.\nSome reductions rely on the assumption that BPP = P which is rather strong. Its practical implications could be better discussed.\nThe appendices need a little polish -- they contain some draft notes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ioO2IDqt3R", "reviewer": "Reviewer_RC8s", "summary": "The paper introduces Minimal Average Strong Equilibrium (MASE), a concept extending classical equilibria to account for coalition deviations by minimizing each coalition’s average incentive to deviate. Computing even an approximate MASE (ϵ-MASE) is NP-hard. \n\nUsing a Utility Dependency Graph to capture players’ interdependencies, the authors establish a fixed-parameter lower bound: under SETH, computing MASE requires time exponential in the graph’s treewidth. \n\nThey propose a Follow-the-Perturbed-Leader (FTPL) learning algorithm via a correlator–deviator meta-game, achieving $O(\\sqrt{T})$ regret for both players, with runtime matching the treewidth lower bound. \n\nExperiments are conducted on bimatrix games.", "questions": "How dose the learning algorithm perform in more general games?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. A novel solution concept, Minimal Average-Strong Equilibrium (MASE), is proposed to addresses coalition deviations.\n2. Clear theoretical results of computation complexity.\n3. A no-regret learning algorithm is proposed.", "weaknesses": "1. The paper appears to overstate its contributions. In the abstract, the authors claim to propose a tractable equilibrium; however, the theoretical results indicate that computing this equilibrium is NP-hard.\n2. Although the theoretical results and learning algorithm are designed for multi-player games, the experiments are limited to simple $2\\times 2$ bimatrix games.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qfkADUSIEY", "reviewer": "Reviewer_SFni", "summary": "The paper introduces Minimal Average-Strong Equilibrium (MASE), a solution concept designed to handle coalitional (multilateral) deviations in games. Instead of requiring immunity to every coalition (which often fails to exist), MASE minimizes the maximum average gain any allowed coalition can obtain by deviating from a correlated strategy.\n\nOn the theory side, the authors prove NP-hardness even when only single-player deviations are allowed and establish a fixed-parameter lower bound: under SETH, computing (even approximating) MASE must be exponential in the treewidth of a newly defined Utility Dependency Graph.\n\nOn the algorithmic side, they show a sparse representation exists for ε-MASE and design a algorithm (up to polynomial factors) that reformulates the problem as a correlator-deviator zero-sum game, solved via no-regret learning (FTPL) combined with dynamic programming over a tree decomposition of the dependency graph. Experiments on classic games (e.g., Prisoner’s Dilemma, Stag Hunt) indicate MASE yields higher robustness to coalition deviations and often better social welfare than standard baselines.\n\nIn short, the paper delivers a new coalitional stability notion, a tight complexity characterization tied to treewidth, and a practical algorithm whose complexity matches the theoretical lower bound in its dependence on treewidth.", "questions": "First, what is the relationship between your Utility Dependency Graph and the original game? Note that I am not asking how to construct the graph from the game; rather, I want to understand the underlying relationship between the constructed graph and the original game.\nSecond, why do you rely on a tree decomposition of the Utility Dependency Graph as the core algorithmic vehicle? How do bags correspond to interaction structures or utility terms in the original game?\nIn a word, I find the description of the tree decomposition and the dynamic programming on the tree insufficiently intuitive, and I would like the authors to clarify it.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper introduces a clear and well-motivated solution concept for coalitional deviations, MASE, which fills the gap left by nonexistence of strong equilibria. It gives tight complexity lower bounds linked to treewidth and then matches them with an algorithm using FTPL plus tree decomposition. The sparse representation result is elegant and enables practical computation. The Utility Dependency Graph provides a clean structural lens that connects theory and algorithms. Experiments show improved coalition robustness and often better social welfare compared to standard baselines.", "weaknesses": "About model: using the average gain of coalition members as the metric can mask heterogeneity within the coalition. Large gains for some members can offset small losses for others, which may understate the true threat of coordinated deviations. If one instead imposed per-member constraints or a weighted minimization, both the conclusions and the algorithmic complexity could change. The paper lacks a systematic comparison and robustness analysis along these dimensions.\nAbout result: Although the results regarding complexity in the paper are mathematically solid, they are not surprising.\nAbout writing: in this paper, the authors mention that one can construct a Utility Dependency Graph from the game G. What implicit relationship exists between the two, and what aspects of that relationship should be clarified in the main text?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MADPFkEeGq", "reviewer": "Reviewer_9CSD", "summary": "This paper studies an equilibrium concept describing resistance to multilateral deviations, similar to strong NE and coalition-proof equilibrium. This \"Minimal Average-Strong Equilibrium\" (MASE) is the strategy $\\pi$ which minimizes the utility gain any coalition can gain by any deviation, averaged across the coalition's members. Computing this notion is hard (Theorem 5.1), so a fixed parameter lower bound is provided in terms of strategy space size and the tree width of a tree decomposition of the game's Utility Dependency Graph (Theorem 5.3). The paper then goes on to propose and empirically evaluate an algorithm achieving an $\\epsilon$-MASE whose running time matches their lower bound (line 416). The main concepts for this algorithm include a correlator–deviator meta-game with FTPL updates and dynamic programming over a tree decomposition.", "questions": "The following points reflect areas where additional clarification could help readers better understand the technical contributions and experimental comparisons:\n\n- (Line 145) How does the complexity of LP (Appendix A) compare to your solution (lines 413--417)? On Line 145 when you say, for non-succinct games, MASE can be computed by LP in $O(\\star^N)$, this doesn't clarify the case for succinct games.\n- Relatedly, it appears in Figure 2 that MASE converges to LP. For my own understanding, does LP correspond with $\\pi^\\star$ and $\\mu^\\star$ in Theorem 6.4? Can you please clarify this connection?\n- Is the deviation gap (line 189) for CCE equivalent to $E_{a \\sim \\pi}[U_i(hat~a_{S}, a_{-S}) - U_i(a)]$ in the definition of MASE (line 167)? For the reader's understanding, it may be worth an additional sentence drawing this connection, somewhere on lines 187--194.\n- (Line 191) How does your work differ from Anagnostides et al. (2025)? How does Theorem 5.1 differ from their conclusion about minimizing the average gap of CCE across players?\n- Relatedly, how does Anagnostides et al.'s solution compare to your experiments in Figure 2?\n- Is your technique for identifying the tree decomposition of the utility dependency graph novel? Or is it inspired by other work?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper makes a meaningful contribution to the learning-in-games literature by providing an algorithm that achieves the tight attainable bound for $\\epsilon$-MASE, established in Theorem 5.3. The work is original in its framing of MASE as a zero-sum meta-game between correlator and deviator strategies, and in its use of the tree decomposition of the utility dependency graph to express $\\sum_{S \\in \\mathcal{S}}$. This appears to be a novel and potentially generalizable technique. The theoretical analysis is rigorous, and the experimental results effectively support the claims, demonstrating the algorithm's efficacy in computing the LP-based solution. The paper is generally clear and well-organized, though some technical sections could benefit from additional explanation to improve accessibility.", "weaknesses": "While the paper's theoretical contributions are strong, several aspects of the exposition could be clarified to improve readability and accessibility. In particular, certain definitions and intuitions are introduced later than they are used, and some algorithmic details are not fully explained. For instance:\n- After the definition of MASE (line 165), it would be helpful to explicitly mention that minimizing the deviation gap guarantees the existence of MASE, as this may not be immediately obvious to some readers.\nTheorem 5.3 (line 216) invokes tree decomposition before defining it (line 316); moving the definition earlier and expanding the discussion of SETH and BPP = P beyond brief footnotes, perhaps in an appendix, would improve clarity.\n- The intuition behind the tree decomposition procedure in Figure 1 (line 334) could be expanded, particularly regarding how property 3 ensures no contradictions arise in Equation (6.5).\n- The discussion of local assignments of agents to bags (lines 310–312) could be elaborated.\n- The FTPL update process (lines 272, 292, 406) could be clarified—are updates alternating, or is there a more complex schedule? Including a concise description of the full procedure for attaining the convergence bound in Theorem 6.4 would be useful.\n- In Section 6.2 (lines 301–307), it would be helpful to explain how Equations (6.4) and (6.5) contribute to minimizing $F(\\tilde{\\pi}, \\mu)$\nOverall, these issues primarily concern clarity and presentation rather than the soundness of the work, and addressing them would make the paper significantly easier to follow for a broader audience.\n\n\nMinor:\n- Line 230: doesn't this paper only consider deviations of singleton coalitions? (following line 129 and Thm 5.1)\n- Line 237: should size be $|A|^n$?\n- Line 292: it might be worth saying up front that Section 6.2 is for $\\pi$, while the update for $\\mu$ is in Appendix F\n- Typo line 421 \"Social welfare.:\"\n- Author comments accidentally revealed on lines 712, 760, \n- Accidental red text on lines 900, 971, 987", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)