Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability
Authors: Revan MacQueen
James R. Wright
Venue: NeurIPS 2023 poster (2023)
Keywords: Algorithmic Game Theory
Self-Play
Regret-Minimization
Multi-agent RL
Multiplayer Games
General-Sum Games
TL;DR: We identify structural properties of multiplayer games where self-play is guaranteed to perform well against opponents.

Abstract: Self-play is a technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. Self-play is useful for generating large quantities of data for learning, but has the drawback that the agents the learner will face post-training may have dramatically different behavior than the learner came to expect by interacting with itself. For the special case of two-player constant-sum games, self-play that reaches Nash equilibrium is guaranteed to produce strategies that perform well against any post-training opponent; however, no such guarantee exists for multiplayer games. We show that in games that approximately decompose into a set of two-player constant-sum games (called constant-sum polymatrix games) where global $\epsilon$-Nash equilibria are boundedly far from Nash equilibria in each subgame (called subgame stability), any no-external-regret algorithm that learns by self-play will produce a strategy with bounded vulnerability. For the first time, our results identify a structural property of multiplayer games that enable performance guarantees for the strategies produced by a broad class of self-play algorithms. We demonstrate our findings through experiments on Leduc poker.

Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability
Revan MacQueen Department of Computing Science University of Alberta Amii
James R. Wright Department of Computing Science University of Alberta/ Amii
Amii
revanGualberta.co
james wwwght@uallerta.cccmmmmmmm
Abstract
Self-play is technique for machine learning in multi-agent systems where a learning algorithm learns by interacting with copies of itself. Self-play is useful for generating large quantities of data for learning, but has the drawback that the agents the learner will face post-training may have dramatically different behavior than the learner came expect by interacting with itself. For the special case of two-player constant-sun sum games, self-play that reaches Nash equilibrium is guaranteed to produce strategies that perform well against any post-training opponent; however, no such guarantee exists for multiplayer games. We show that in games that approximately decompose into a set of two-player constant-sum games (called constant-sun polymatrix games) where global c-Nash equilibria are boundedly far from Nash equilibria in each subgame (called subgame stability), any no-external-regret algorithm that learns by self-play will produce strategy with bounded vulnerability, For the first time, our results identify a structural property multiplayer games that enable performance guarantees for the strategies produced by a broad class of self- self-play algorithms. We demonstrate our findings through experiments on Ledue poker.
Introduction
Self-play is one of the most commonly used approaches for machine learning in multi-agen systems. In self-play, a learner interacts with copies of itself to produce data that will be used for training. Some of the most noteworthy successes of Al in the past decade have been based self-play; by employing the procedure, algorithms have been able to achieve super-human abilities various games, including Poker (Moraveik al. 2017 Brown & Sandholm 2018 2019), Go and Chess (Silver et af.] 2016 2018), Starcraft (Vinyals et al. 2019), Diplomacy (Paquette et al. 2019). and 2022).
Stratego (Perolat
Self-play has the desirable property that unbounded quantities of training data can be generated (assuming access to simulator). But using self-play necessarily involves choice of agents for the learner to train with: copies of itself. Strategies that perform well during training may perform poorly against new agents, whose behavior may differ dramatically from that of the agents that the learner trained against.
The problem of learning strategies during training that perform well against new agents is a central challenge in algorithmic game theory and multi-agent reinforcement learning (MARL) (Matignon) al. 2012 Lanctot al. 2017). In particular, self-play trained agent interacting with agents from an independent self-play instance deitancc-differing only by random seed-can lead to dramatically worse performance (Lanctot et al. 2017). The self-play-based DORA (Bakhtin et al. 2021) performs well aginst copies of itself in the game of no-press Diplomacy, but poorly against human- like agents
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(Bakhtin et al. 2022). Self-play has also been known to perform poorly against new agents in games with highly specialized conventions (Hu et al. 2020), such as Hanabi (Bard al., 2020). In training, one instance of a self-play algorithm may learn conventions that are incompatible with the conventions of another instance.
There are special classes of games where the strategies learned through self-play generalize well to new agents. In two-player, constant-sum games there exist strong theoretical results guaranteeing the performance of a strategy learned through self-play: Nash equilibrium strategies are maxmin strategies, which will perform equally well against any optimal opponent and can guarantee the value of the game against any opponent.
We lose these guarantees outside of two-player constant- sum games. For example, consider the simple two-player coordination game of Figure [ If both players choose the same action, both receive a utility of 1, otherwise they receive O. Suppose the row player learned in self-play to choose a (which performs well against another a-player), Similarly, column learned play b. If these two players played against each other, both agents would regret their actions. Upon the introduction of a new agent who did not train with learner, despite a and b being optimal strategies during training, they fail to generalize to new agents. As this example demonstrates, equilibrium strategies in general are vulnerable: agents are not guaranteed the equilibrium's 's value against new egents-even if the new agent's 's also play an equilibrium strategy.
b
1,
0,0 0
0.0
1.1
Figure 1: A simple coordination game
In multiplayer, general-sum games, no-regret self-play is no longer guaranteed to produce Nash cquilibra- algorithms converge to a mediated equilibrium, where a mediator recommends actions each player (Von Stengel & Forges 2008 Farina al., 2019 2020; Morrill al. (02 The mediator can represent an external entity that makes explicit recommendations, such as traffic lights mediating traffic flows. More commonly in machine learning, correlation can arise through the shared history of actions of learning agents interacting with each other (Hart & Mas- Colell 2000). If strategy learned in self-play were played against new agents, these new agents may not have access to the actions taken by other agents during training, so agents would no longer be able to correlate their actions. In fact, even if all agents play a decorrelated strategy from the same mediated equilibrium, the result may not be an equilibrium!"
Despite the problems of vulnerability and loss of correlation, self-play has shown promising results outside of two-player constant-sum games. For example, algorithms based on self-play have out- performed professional poker players in multiplayer Texas hold "em, despite the lack of theoretical guarantees (Brown & Sandholm 2019).
We seek to understand what structure in multiplayer games will allow self-play compute good strategy. We show that any multiplayer game can be projected into the set of two-player constant-sum games between each pair of players, called constant- sum polymatrix games. The closer game is to this space, the less the problem of correlation affects the removal of a mediator. We identify a second important property, called subgame stability, where global c-Nash equilibria are boundedly far from Nash equilibria in each two-p two-player subgame. We show that if a multiplayer, general-sun -um game is close to a subgame stable constant-sum polymatrix game, this is sufficient for strategies learned via self-play to generalize to new agents, as they do in two-player constant-sum games.
approach by assuming only that self-play is performed by a regret minimizing algorithm. This is accomplished by analyzing directly the equilibria that no-regret algorithms converge to vo-namely coarse correlated equilibria. As a result, our analysis applics to a broad class of game- teeeettoooccclll-nnsseeeee inspired learning algorithms but also to MARL algorithms that converge to coarse correlated equilibria (Marris al., 2021 Liu et al. 2021 Jin et al. 2021), since any policy can be transformed into a mixed strategy with Kuhn's 's Theorem (Kuhn 1953). For the remainder of this work, when we say "self- play" are referring to self-play using a no-regret algorithm.
Throughout this work, take algorithm-agneet
Decomposition-basel approaches have been used in prior work to show convergence of fictitious play to Nash equilibria two-player games (Chen et al. (022) and evolutionary dynamics (Tuyls ct al. 2018). Cheung & Tao (2020) decompose games into zero-sum and cooperative parts to analyse
Pleasse refer to the Appendix A for example
2

---

the chaotic nature of Multiplicative Weights and sallowtth-Regularizeeedd the convergence of algorithms per se, and focus instead on the generalization of learned strategies to new agents. We are, to the best of our knowledge, the first to do so.
We focus less on
After defining our structural properties and proving our main results, we conclude with experiments on Leduc poker to elucidate why self-play performs well in multiplayer poker. Our results suggest that pegree-miiimizzttion techniques converge to a subset of the game's strategy space that is well- approximated by a subgame stable constant-sum polymatrix game.
2 Background
Normal Form Games A normal form game is 3 tuple G = PN, where N is set of players, P= =XieN P; is a joint pure strategy space and P; is set of pure strategies for player i. Let = [N]. Pure strategies are deterministic choices of actions in the game. We call p E P pure strategy profile. IR. A player i can randomize by playing mixed strategy, a probability distribution s; over i's pure strategies. Let S; = ((P,) be the set of player i's mixed strategies (where (XX denotes the set of probability distributions over a domain X), and let S = XieN St be the set of mixed strategy profiles. We overload the definition of utility function accept mixed strategies as follows: (s)s) EpEp (TLEN 8; (p:)) up()). We p-a and 8_, to denote joint assignment of pure (resp. mixed) strategies to all players except for i, thus s = 5-4). We use P-, and S_, ; to denote the sets of all such assignments.
=uu)EEN is set of utility functions where u,
Hindsight Rationality The hindsight rationality framework (Morrill et al. 2021b) conceptualizes the goal of an agent as finding a strategy that minimizes regret with respect set of deviations c. deviation ø E Φ is a mapping 6 S + S; that transforms a learner's strategy into some other strategy. Regret measures the amount the learner would prefer to deviate to ((x;): ): uy (o(();); s)) - ( 8 8-1). An agent is hindsight rational with respect to a set of deviations & if the agent does not have positive
regret with respect to any deviation in 6, i.e. VÓ $ u,,u, (o(ss)) 8-1) us (s 8-:) S Let (P) be a distribution over pure strategy profiles and (Pi)ee be choice of deviation sets for each player.
2021b)). We say = (n,, (D:)ien) is an e-mediated equilibrium Vi E N, á E 4, we have Epwn [u. (u(o(p)).P-) -2 u.(p)) S e. mediated equilibrium is a O-mediated equilibrium.
Definition 2.1 (e-Mediated Equilibrium (Morrill et al.
Learning takes place in an online learning environment. At each iteration I, learning agent chooses a strategy st while all other agents choose a strategy profile s'.g. No-4-regret learning algorithms ensure that the maximum average positive regret tends O:
T
lim T-
max dE
un(o(s))
u((s)..(.)) + O.
T
If all agents use a no- no-regret learning algorithms w.r.t. a set of deviations P,, the empirical distribution of play converges mediated equilibrium. Formally, let j E A(P) be the empirical distribution of play, where the weight on p E is p(() ='T (Tlex s((().). As + oc, j converges to p of mediated equilibrium (p, (#:)EEN).
Different sets deviations determine the strength of a mediated equilibrium. For normal-form games, the set of swap deviations, &sw, are all possible mappings & P. P.. We may apply swap devi- ation & to a mixed strategy s; by taking its pushforward measure: (o(s:))(p))) = Epteo (p.) (p()), where - (p:) {or e P. Φ(p)) p.). The set of internal deviations 4,, which replace single pure strategy with another, offer the same strategic power as swap deviations (Foster& & Vohra 1999). Formally, & {Ø sw 3p, Pf: (o(p,) = p.] [Vp"" # Pis p(p!)) = P/ The set of external deviations, Øxx, is even more restricted: any 6 E Φxx maps all (mixed) strategies to some particular pure strategy; i.e. TEX = tō E sww 3p, : Vpl. o(p() = p.). The choice of (#e) determines the nature of the mediated equilibrium- provided the learning algorithm for player i is no-gb,-regret (Greenwald et al. (201T). For example, if all players are hindsight rational w.r.t. Fxx, then ji converges to the set of coarse correlated equilibria (CCE) (Moulin & Vial 1978) and if all players are hindsight rational w.r.t. 4 then j converges to the set of correlated equílibria (Aumann) 1974).
3

---

A special case of mediated equilibria are Nash equilibria. If some mediated equilibrium m (n, (#)) is a product distribution (i.e. μ(p) = IIEN s((p) Vp P) )) and $; 2 4Fx Vi N then je is a Nash equilibrium. Similarly, an e-mediated equilibrium is an e-Nash equilibrium if is product distribution and Φ; 2 &xx Vi E N.
In sequential decision making scenarios (often modelled as extensive form games), the set of deviations is even more rich (Morrill al. 2021b). All of these deviation classes-with the exception of action deviations (Selten) 1988) (which are so weak they do not even imply Nash equilibria in two-player constant-sum games, see appendix) are stronger than external deviations. This means that the equilibria of any algorithm that minimizes regret w.r.t. stronger class of deviations than external deviations still inherit all the properties of CCE (for example Hart & Mas-Collell (2000); Zinkevich et al. (2008); [Celli et al. (2020); Steinberger et al. (2020); Morrill et al. (202la)). Thus, we focus on CCE since the analysis generalizes broadly. Moreover, CCE can be computed efficiently, either analytically (Jian & Leyton- Brownn 2011) by a learning algorithm. When we refer to CCE, we use the distribution y to refer the CCE, since + is implicit.
3
Vulnerability
The choice of other agents during learning affects the strategy that is learned. Choosing which agents make good "opponents" during training is an open research question (Lanctot et al.) 2017 Marris al.] 202I). One common approach, self-play, is to have a learning algorithm train with copies of itself as the other agents. If the algorithm is a no-P-regret algorithm, the learned behavior will converge to mediated equilibrium; this gives nice characterization of the convergence behavior of the algorithm.
However, in general the strategies in mediated equilibrium correlated with each other. This means that in order to deploy a strategy learned in self self-play, an agent must first extract it by marginalizing other agent's strategies. This new marginal strategy can then be played against new agents with whom the agent did not train (and thus correlate).
Definition 3.1 (Marginal strategy), Given some mediated equilibrium (p, (4.) let s be the marginal strategy for i, where sy. (pi) E(p.er,, Let sM be marginal strategy profile, where each vi E N plays s/""
Once a strategy has been extracted via marginalization, learning can either continue with the new agents (and potentially re-correlate), or the strategy can remain fixed We focus on the case where the strategy remains fixed. In doing so we can guarantee the performance of this strategy if learning stops, but also the show guarantees about the initial performance of strategy that continues learn; this is especially important in safety-critical domains.
Given marginal strategy sf,, we can bound its underperformance against new agents that behave differently from the (decorrelated) training opponents by a quantity which we call vulnerability.
Definition 3.2 (Vulnerability). The vulnerability of a strategy profile s for player i with respect to 8', S_; is
Vul, (s, = us(s)
min ui(8s, 8L.). "'_ES_
Vulnerability gives a measure of how much worse will perform with new agents compared to training performance under pessimistic assumptions -hat -i play the strategy profile in S" that is worst for i. We assume that -i are not able to correlate their strategies.
its
Thus, if a marginal strategy profile s is learned through self-play and Vul, (s*, (",))" is small, then *!" performs roughly well against new agents -i playing some strategy profile in S' S" is used to encode assumptions about the strategies of opponents. S" S_, means opponents could play any strategy, but we could also set S" to be the set of strategies learable through self-play if we believe that opponents would also be using self-play as a training procedure.
'The strategy learned in self-play prior to online learning has been called blueprint strategy (Brown & Sandholm 2019).

---

Some games have properties that make the vulnerability low. For example, in two- two-player constant- sum games the marginal strategies learned in self- generalize well to new opponents since any Nash equilibrium strategy is also maxmin strategy (von Neumann T928).
4 Guarantees via Polymatrix Decomposability
Multiplayer games are fundamentally more complex than two-player constant-sum games (Daskalakis) & Papadimitriou 2005 Daskalakis et al. 2009). However, certain multiplayer games can be decom- posed into graph of two-player games, where a player's payoffs depend only on their actions and the actions of players who are neighbors in the graph (Bergman & Fokin 1998). In these polymatrix games (a subset of graphical games (Kearns et al. (013)) Nash equilibria can be computed efficiently if player's utilities sum to a constant (Cai & Daskalakis) 2011 Cai et al. 2016).
Definition 4.1 (Polymatrix game). A polymatrix game G (N, E, P. u) consists of set N of players, a set of edges E between players, a set of pure strategy profiles P. and a set of utility functions u- {uig. Uja V(i,j) }} where Uij Ujs P, P, + IR are utility functions associated with the edge (i.j) for players i and j. respectively.
We refer to the normal-form subgame between (f.j) as Gij ((i.j).P x P, (usj. ujs)). We use Ue to denote the global utility function P - I where (p( = EiEEE "iy (Pi, Pÿ) for each
player. We use F S E to denote the set of edges where i is player and [Pg denote the number of such edges.
Definition 4.2 (Constant-sum polymatrix), We say a polymatrix game G is constant-sum for some constant we have that vp P, EiEN up(p) c.
Constant-sum polymatrix (CSP) games have the desirable property that all CCE factor into product distribution; i.e., are Nash equilibria (Cai et al. 2016). We give a relaxed version:
Proposition 4.3. If u is an e-CCE of a CSP game G, sh is an ne-Nash of G.
This means no-externnal-regre learning algorithms will converge to Nash equilibria, and thus do not require a mediator to enable the equilibrium. However, they do not necessarily have the property of two-player constant-sum games that all (marginal) equilibrium strategies are maxmin strategies (Cai
et al. 2016). Thus Nash equilibrium strategies in CSP games have no vulnerability guarantees. Cai
et al. 2016) show that CSP games that are constant sum each subgame are no more or less general than CSP games that are constant sum globally, since there exists a payoff preserving transformation between the two sets, For this reason we focus on CSP games that are constant sum in each subgame without loss of generality. Note that the constant need not be the same in each subgame.
4.1 Vulnerability on a Simple Constant-Sum Polymatrix Game
We next demonstrate why CSP games do not have bounded vulnerability their own without additional properties. Consider the simple 3-player CSP game called Offense-Defense (Figure Dig There are players: 0, and 2. Players 1 and 2 have the option to either attack (ag) attack the other (e.g. a1): player O, on the other hand, may either relax (r) or defend (d). If either 1 or 2 attacks the other while the other is attacking 0, the attacker gets B and the other gets -8 in that subgame. If both 1 and 2 attack O, and 2 get 0 in their subgame and if they attack each other, their attacks cancel out and they both get O. If 0 plays d, they defend and will always get O. If they relax, they get - if they are attacked and ( otherwise. Offense- Defense is a CSP game, so any CCE is a Nash cquilibrium.
Note that م = (r, ag, a1) is a Nash equilibrium. Each E {1,2} are attacking the other j E {1,2) \ {i), so has expected utility of O. Deviating to attacking 0 would leave them open against the other, so an is not a profitable deviation, as it would also give utility O. Additionally, 0 has no incentive to deviate d, since this would also give them utility of O.
However, p is not a Nash equilibrium of the subgames-all all i E (1,2) have profitable deviation in their subgame against 0, which leaves 0 vulnerable in that subgame. If and 2 were to both deviate to ag. and continues to play their Nash equilibrium strategy of r, would lose 2,3 utility from their equilibrium value; in other words, the vulnerability of player 0 is 2B3.
5

---

4.2 Subgame Stability
However, some constant-sum polymatrix games do have have bounded vulnerability; we call these subgame stable games, In subgame stable games, global equilibria imply equilibria at each pairwise subgame.
Definition 4.4 (Subgame stable profile). Let G be polymatrix game with global utility functions (u, NeN. We say a strategy profile is y-subgame stable if (i, E E, we have (ss, 85) is y-Nash of Gay; that Uiy (Ps: 8j) Uiy (8t, 8j) S 7 Vp, E P; and Uz( 8:) Uyi(s), 8:) S Vpj E P,
For example, in lfffense-Defense (r, 02, a1) 3-subgame stable; it is Nash equilibrium but is 9-Nash of the subgame between O and and the subgame between 0 and 2.
Definition 4.5 (Subgame stable game). Let G be polymatrix game. We say G is (c,7))subgam stable if for any e-Nash equilibrium s of G. s is y-subgame stable.
Subgame stability connects the global behavior of play (e-Nash equilibrium in G) to local behavior in subgame (y-Nash in Giy). If polymatrix game is both constant-sum and is (0, 7)-sugmame stable then we can bound the vulnerability of any marginal strategy.
Theorem 4.6. Let G be a CSP game. If is (0, -ussgame stable, then for any player E N and CCE μs of G. we have Vul, (s",S_.) E,
Theorem 4.6/tells us that using self-play to compute a marginal strategy s on constant-sum polymatrix games will have low vulnerability against worst-case opponents if is low. Thus, these are a set of multiplayer games where self-play is an effective training procedure.
Proof idea. Since G is CSP game, s" is Nash equilbrium. Since is (0, (0, suubbgame stable, (sf), 85) is a 7-Nash equilibrium in each subgame, which bounds the vulnerability in each subgame.
This is because
min wi(s s-i) -...__
Σ min (f 8j)
tyES
(i,))EB
since players j * can minimize utility without coordinating, as G is polymatrix game.
We give an algorithm for finding the minimum value of y such that a CSP game is (0, --subamme stable in Appendix D.1
d
Gg
42
2
Og
f
2
2
2
0g
02
Q1
0
0
B
3/2
8
8
9
3/2
8/2
8/2
8/2
8/2
(b)
Figure 2: (a) Offense- -Dfenns,, simple CSP game. We only show payoff's for the row player, column player payoffs are zero minus the row player's payoffs. (b) Bad Card: game that not overall CSP, but the subset of strategies learnable by self-play are. At the terminals, we show the dealers utility first, followed by players 0, and respectively.

---

4.3 Approximate Constant-Sum Polymatrix Games
Most games are not factorizable into CSP games. However, we can take any game G and project into the space of CSP games.
Definition 4.7 (ō-constant sum polymatrix). A game G is 6-constant sum polymatrix (6-CSP) if there exists CSP game G with global utility function such that Vi E N, E P. [1(())() - u,(p)] v Given G. we denote the set of such CSP games as (G). Proposition 4.8. In 5-CSP game G the following hold.
1. Any CCE of G is a 28- CCE of any G E CCPP
2. The marginal strategy profile of any CCE of G is 2nd-Nash equilibrium of any G CSP CSP&(G), s(G).
3. The marginal strategy profile of any CCE of G is 2(n + 1)6-Nash equilibrium of G.
From (3) we have that the removal of the mediator impacts players utilities by a bounded amount in 6-CSP games. We give a linear program in Appendix [D22 that will find the minimum ō such that G is 8-CSP and returns CSP game & E CS),
Combining 8-CSP with (e, -uubbaae stability lets us bound vulnerability in any game. Theorem 4.9. G is 5-CSP and 3/ E CSP that is (2nō, 7-ssugamme stable and μ is CCE of G, then
Vul, (8", S_,) S F 25 S (n 1)y + 25.
Theorem 4.9 shows that games which are close to the space of subgame stable CSP (SS-CSP) games are cases where the marginal strategies learned through self-play have bounded worst-case performance. This makes them suitable for any no-external-regre learning algorithm.
Vulnerability Against Other Self-Taught Agents
Theorem 4.9 bounds vulnerability in worst-case scenarios, where -i play any strategy profile to minimize i's utility. In reality, however, each player j E -i has their own interests and would only play strategy that is reasonable under these own interests. In particular, what if each agent were also determining their own strategy via self-play in a separate training instance. How much utility can guarantee themselves in this setup?
While no-external-regret learning algorithms converge to the set of CCE, other assumptions can be made with additional information about the type of regret being minimized. For example. no-external- regret learning algorithms will play strictly dominated strategies with vanishing probability and CFR will play dominated actions with vanishing probability (Gibson 2014). These refinements can tighten our bounds, since the part of the game that no-regret learning a algorithms converge to might be closer to CSP game than the game overall.
Consider the game shown Figure 2b] called "Bad Card". The game starts with each player except the dealer putting 3/2 into the pot. A dealer player d-whho always receives utility 0 regardless of strategies of the other players- the other two players receive "good card". The player who receives the bad card has option to fold, after which the game ends and all players receive their ante back. Otherwise if this player calls, the other two players cards who call. If one player with a good card calls, they win the pot of 3. If both good card players call then they split the pot. If both players with good cards fold, then the player with the bad card wins the pot.
selects a player from {0, 1, 2} to receive "bad card", while
either fold or call. The pot of 3 is divided among the players with good
As we shall soon show, Bad Card does not have CSP decomposition in fact it does not have any polymatrix decomposition. Since Bad Card an extensive-forn game without chance, each pure strategy profile leads to single terminal history. Let P(z) be the set of pure strategy profiles that play to a terminal z. In order for Bad Card to be polymatrix, we would need to find subgame utility functions such that Vp E P, (p(p) uo.a(po, pa) uo ( P1) + u p2). Equivalently,
7

---

could write 42 E Z, P(z), uo(z) = uo.a(po. Pa) + 10.1 P1) + (00 P2) where Z is the set of terminals. A subset these constraints results in an infeasible system equations.
Consider the terminals in the subtree shown in Figure 2b
z² = (0,c, c). 2² = (0,c,,
23 = (0, c, f. c) and 24 = (0, f. f). Let Pl be any pure strategy that plays in this subtree and p be any strategy that plays
this subtree for player i. In order for Bad Card to decompose into polymatrix game we would need to solve the following infeasible system of linear equations:
uo(2²) = up,a(pi. 0) + 20,1 1 pi) 20 (p): p$) -B
uo(2²) = uo.a(Pi, 0) + ( pi) + u0.2 pi) -B
u=(2²) u 0) + uo, (p p1) + uo 2 pb) -3
uo - "0.a(Po. 0) + un, (P6: 0 + 200 p2)
Thus, Bad Card is not a CSP game, although it a B-CSP game. However, if we prune out dominated actions (namely, those in which a player folds after receiving a good card), the resulting game is indeed O-CSP game.
Let M(A) be the set of mediated equilibria than algorithm A converges to in self-play, For example, if A is no-external-rege
algorithm, ((A) is the set of CCE without strictly dominated strategies in their support. Let S(A) = {s" (μ, (#)) (M(A) be the set of marginal strategy profiles of ((A), and let ((A) {8: E S(A) be the set of i's marginal strategies from ((A).
Now, consider if each player i learns with their own self-play algorithm A, Let AN = (A1,...AA))) be the profile of learning algorithms, then let Sx (An) = XieN Si(A,) and (Ax) SAA)) Summarizing, each player learns with a no- norgee learning algorithm A, they will converge to the set of M(A:) equilibria. The set of marginal strategies from this set of equilibria is (AA,) and the set of marginal strategy profiles is S(Ai). If each player plays (potentially) different learning algorithm, S* (Ax) is the set of possible joint match-ups if each player plays marginal strategy from their own algorithm's 's set of equilibria and S is the set of profiles for -i.
Definition 5.1. We say game G is 8-CSP in the neighborhood of S' C S if there exists a CSP game G such that Vs E 5' we have (u,(s) (s()) < 5. We denote the set of such CSP games as CS,,(G,S))
Definition 5.2. We say polymatrix game G is 7-suugamm stable in the neighborhood of S' if Vs E S", v(i,j) E we have that (s;, 8j) is 7-Nash of Gij.
These definitions allow us to prove the following generalization of Theorem 4.9
Theorem 5.3. For any i E N, if G is 8-CSP in the neighborhood of Sx (An) and 3ة e CSPs S* (Ax)) that is y-subgame stable in the the neighborhood of S(Ai) then for any E S(A.)
Vul, (s, & / + 25 s (n 1)y + 26.
An implication of Theorem 5.3 is that if agents use self-play to compute a marginal strategy from some mediated equilibrium and there is SS-CSP game that is close to the original game for these strategies, then this is sufficient to bound vulnerability against strategies learned in self-play.
Computing an SS-CSP Decomposition in a Neighborhood
How might determine if a game is appr-aappo by SS-CSP game? In addition the algorithms presented in Appendix D we give an algorithm, SGDecompose, that finds an SS-CSP decomposition for game given neighborhood of strategy profiles. Pseudocode given in Algorithm
I SGDecompose could be used to test whether a game is well-approximated by an SS-CSP game before potentially analytically showing this property holds. We will use this algorithm in the following section to decompose Leduc poker.
As input, SGDecompose receives neighborhood of strategies S' and the set of match-ups between strategies in S" given by 8x = XieN S. The idea is to compute CSP game Ö that minimizes
8

---

a loss function with two components: how close G is to G in the neighborhood of S and how subgame stable G is for the neighborhood of S" First, L the error between the utility functions of G and G (u and ú, respectively); is a proxy for 8-CSP. The loss for single strategy profile a is
L (s u)
Σ [. (s)l..
The other component of the overall loss function, L7, measures the subgame stability. First, define L.g. which only applies to a single subgame. Let 8ij = (8i, 85) be profile for subgame and $ (5), is a profile of deviations for that subgame. The 272 loss for this subgame is
C2 (s15, stz; ú) max (ūey(s); 8y) (s1g), 0) + max (ūgr(5;; (5)) ú5c( 0)
Then, given a strategy profile and deviation profile s* for all players N, we have
()) = Σ
(1n)) Sijūū)
(JJEE
SGDecompose repeats over number of epoches T. At the start of an epoch, we compute a best- response (for example, via sequence-form linear programming extensive-form games) to each strategy & in S' in each subgame; the full process is shown in Algorithm 4 in the appendix. After computing these best-responses for the current utility function of G, SGDecompose fits ú to be nearly CSP in the neighborhood of S and subgame stable in the neighborhood of S'. Since S* is exponentially larger than S we partition it into batches, then batch gradient descent
We use the following batch loss function, which computes the average values of L and L over the batch then weights the losses with X. Let S denote batch of strategy profiles from Sx with size B,
(1 (1-A)
S',"
Σ cs; SES*
E (s,s"";;
B
S
SES' E*S"
We this loss function update ú, which is guaranteed to be valid utility function for CSP game via its representation, see Appendix [ for details. In Appendix F we give the procedure in terms of more efficient representation of polymatrix decompositions for extensive-form games, which we call Poly-EFGs; which we describe in Appendix
Algorithm 1 SGDecompose
Input: G, S", hyperparameters v), T. A.
Initialize à to all 0
S* XieN S for 1 E 1...T do
S* + getBRs S¹)
B partition of S into batches of size B
for S < B do
g t VaL(sh S' u) g ù + u Islll (update û using normalized gradient; this helps with stability)
end for end for
(Lastly, output 8 and 7}
+ max (u,(s) ús))
y t max,es: max (BR,((()))) (1.(s,,))) return 7
7 Experiments
Approaches using regret- minimiztiniiiiiioon in self-play have been shown outperform expert human players in some multiplayer games, the most notable example being multiplayer no-limit Texas hold em (Brwnn & Sandholm, 2019), despite no formal guarantees.
One could also partition S' into batches it were too large.

---

Conjecture 7.1. Self-play with regret minimization performs well in multiplayer Texas hold 'em because "good" players (whether professional players or strategies learned by self self-play) play in a part of the games' strategy space that is close to an SS-CSP game (i.e. low values of y, 6).
While multiplayer no-limit Texas hold 'em is too large to directly check the properties developed in this work, we use smaller poker game, called Ledue poker (Southey et al. (012), to suggest why segret-miiimizttion "works" in multiplayer Texas hold em. Ledue poker was originally developed for two players but was extended to 3-player variant by Abou Risk & Szafron (2010); use the 3-player variant here. The game has cards, two rounds of betting, one private and one public card.
We first use self-play algorithm to learn strategies, then use SGDecompose to see if this part of Ledue Poker is close to an SS-CSP game. We give a summary of results here, please refer to Appendix G for full details. We use CFR+ (Tammelin) 2014 Tammelin et al. 2015) as self-play algorithm to compute a set of approximate marginal strategies CFR+ was chosen because of its improved efficiency over CFR. CFR+ is deterministic algorithm, so we use different random initializations of CFR+'s initial strategy in order to generate a set of CCE. We will use 30 runs of CFR+ as input to SGDecompose; and have 30 runs of SGDecompose (i.c. we trained CFR+ 900 times in total in self-play). This will give us a value of 8 and y for each run.
We found that Leduc poker was well -pproxappo by an SS-CSP game in the neighborhood of strategies learned by CFR+. In particular, across runs, Ledue poker was on average (with standard errors) 6 = 0.009 + 0.00046-CSP and y 0.004 + 0.00016-subgame stable in the neighborhood of leareed strategies. How well do these values bound vulnerability with respect to other CFR- learned strategies? For each of the runs, we computed the vulnerability with respect to the strategies of that run, by evaluating each strategy against each other and taking the maximum vulnerability, We compare these values to the upper bounds implies by the values of d and for each and Theorem 5.3 We found the computed values vulnerability. Across the runs, the bounds are at minimum 1.89 times the vulnerability, maximum 3.05 times the vulnerability and on average 2.51 times as large, with a standard error of 0.049.
and y do a good job of upper bounding the
We repeated these experiments with toy hanabi game same-where strategies learned in self-play are highly sainerable--hich we found to have much higher values of 5 and y; details are in Appendix H
It was previously believed that CFR does not compute an e-Nash equilibrium on 3-player Leduc for any reasonable value of Abou Risk & Szafron (2010) found CFR computed 1a1 equilibrium. We found that CFR+ always computed an approximate Nash equilbrium with 6 S 0.013. Appendix G.2 shows that CFR also computes an approximate Nash equilbrium with e < 0.017.
8 Conclusion
Self-play has been incredibly successful in producing strategies that perform well against new opponents in two-player constant-sum games. Despite lack of theoretical guarantees, self-play seems to also produce good strategies in some multiplayer games (Brown & Sandholm, (019). We identify a structural property of multiplayer, general-sum game that allow us to establish guarantees on the performance of strategies learned via self-play against new opponents. We show that any game can be projected into the space of constant-sum polymatrix games, and if there exists a game with this set with high subgame stability (low 7), strategies learned through self- elay have bounded loss of performance against new opponents.
We conjecture that Texas hold 'em is one such game. We investigate this claim on Ledue poker, and find that CFR+ plays strategies from a part of the strategy space Ledue poker that is well- approximated by a subgame stable constant-sum polymatrix game. This work lays the groundwork for guarantees for self-play in multiplayer games. However, there is room for algorithmic improvement and efficiency gains for checking these properties in very large extensive-form games.
'We use the OpenSpiel implementation
Lanctot al.
2019
10

---

Acknowledgements
Computation for this work was provided by the Digital Research Alliance of Canada. Revan MacQueen was supported by Alberta Innovates and NSERC during completion of this work. This work was funded in part by an NSERC Discovery Grant. James R. Wright holds a Canada CIFAR AI Chair through the Alberta Machine Intelligence Institute. Thank you to Dustin Morrill, Michael Bowling and Nathan Sturtevant for helpful conversations and feedback, and the anonymous reviewers for valuable comments.
References
Abou Risk, N. and Szafron, D. Using counterfactual regret minimization to create competitive multiplayer poker agents. International Conference on Autonomous Agents and Multiagent Systems, 2010.
Aumann, R. J. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974.
Bakhtin, A., Wu, D., Lerer, A., and Brown, N. No-press diplomacy from scratch. Advances in Neural Information Processing Systems, 34: 1463331411, 2021.
Bakhtin, A. Wu, D. J., Lerer, A., Gray, J., Jacob, A. P., Farina, G., Miller, A. H., and Brown, N. Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning. arXiv preprint arXiv:2210.05492, 2022.
Bard, N., Foerster, J. N., Chandar, S., Burch, N., Lanctot, M., Song, H. F., Parisotto, E., Dumoulin, V., Moitra, S., Hughes, E., Dumning, Mourad, S., Larochelle, H., Bellemare, M. G., and Bowling, M. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 2020.
Bergman, L. and Fokin, I. On separable non-cooperative zero-sum games. Optimization, 44(1): 69 84, 1998.
Brown, N. and Sandholm. T. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 35966374):418-444, 2018.
Brown, N. and Sandholm, T. Superhuman Al for multiplayer poker. Science, 365(6456)::85--88 2019.
Cai, Y. and Daskalakis, On minmax theorems for multiplayer games. ACM-SIAM Symposium on Discrete algorithms,, 2011.
Cai, Y., Candogan, O., Daskalakis, C., and Papadimitriou, C. Zero-sum polymatrix games: A generalization of minmax. Mathematics of Operations Research, 41 (1(2):648 (60886655571 2016.
Celli, A., Marchesi, A., Farina, G., and Gatti, N. No-regret learning dynamics for extensive-form correlated equilibrium. Neural Information Processing Systems, 2020.
Chen, Y., Deng, X., Li, C., Mguni, D., Wang, J., Yan, X., and Yang, Y. On the convergence of fictitious play: A decomposition approach. International Joint Conferences on Artificial Intelligence, 2022.
Cheung, Y. K. and Tao, Chaos of learning beyond zero-sum and coordination via game decompo- sitions. arXiv preprint arXiv:2008.0055 2020.
Daskalakis, C. and Papadimitriou, C. H. Three-player games are hard. Electron. Colloquium Comput. Complex., 2005.
Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009.
Farina, G., Ling, C. K., Fang, F., and Sandholm, T. Correlation in extensive-form games: Saddle-point formulation and benchmarks. Neural Information Processing Systems, 2019.
Farina, G., Bianchi, T., and Sandholm, T. Coarse correlation in extensive-form games. AAAI conference on Artificial Intelligence, 2020.

---

Foster, D. P. and Vohra, R. Regret in the on-line decision problem. Games and Economic Behavior, 29(1):7-35, 1999.
Gibson, R. G. Regret minimization in games and the development of champion multiplayer computer poker-playing agents. Ph.D. Thesis, 2014.
Greenwald, A., Jafari, A., and Marks, C. No-ø-regret: A connection between computational learning theory and game theory. Games, Norms and Reasons: Logic at the Crossroads, 2011.
Hart, S. and Mas-Colell, A. A simple adaptive procedure leading to correlated equilibrium. Econo- metrica, 68(5):1127-1150) 2000.
Hu, H., Lerer, A., Peysakhovich, A., and Foerster, J. "'other-pla"" for zero-shot coordination. International Conference on Machine Learning, 2020.
Jiang, A. X. and Leyton-Brown, K. A general framework for computing optimal correlated equilibria in compact games. Internet and Network Economics: 7th International Workshop, WINE 2011, 2011.
Jin, C., Liu, Q., Wang, Y., and Yu, T. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110. 14555, 2021.
Kearns, M., Littman, M. L., and Singh, S. Graphical models for game theory, 2013.
Kuhn, H. W. Extensive games and the problem of information. Contributions to the Theory of Games, 193-219,,, 1953.
Lanctot, M.. Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Perolat, J.. Silver, D., and Graepel, T. unified game-theoretic approach multiagent reinforcement learning. Neural Information Processing Systems, 2017.
Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafici, S., et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint 19X8v:1908.00 09453, 2019.
Liu, Q., Yu, T., Bai, Y., and Jin, C. A sharp analysis of model-based reinforcement learning with self-play. International Conference Machine Learning. 2021.
Marris, L., Muller, P., Lanctot, M., Tuyls, K., and Graepel. T. Multi-agent training beyond zero-sum with correlated equilibrium mola-solvers. International Conference on Machine Learning, 2021.
Matignon, L.., Laurent, G. J., and Le Fort-Piat, N. Independent reinforcement learners cooperative markov games: survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 2012.
Moravcik, M., Schmid, M., Burch, N., Lisy, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelligence heads-up no-limit poker. Science, 356(6337):508--
2017.
Morrill, D., D'Orazio, R., Lanctot, M., Wright, J. R., Bowling, M., and Greenwald, A. R. Efficient deviation types and learning for hindsight rationality in extensive-form games. International Conference on Machine Learning, 2021a.
Morrill, D., D'Orazio, R., Sarfati, R., Lanctot, M., Wright, J. R., Greenwald, A. R., and Bowling, M. Hindsight and sequential rationality of correlated play. AAAI Conference Artificial Intelligence, 2021b.
Moulin, H. and Vial, J. Strategically zero-sum games: The class of games whose completely mixed cquilibria cannot be improved upon. International Journal of Game Theory. 7(3):001-221, 1978.
Paquette, P., Lu, Y., Bocco, S. S., Smith, M., O-G, S., Kummerfeld, J. K., Pineau, J., Singh, S., and Courville, A. No-press diplomacy: Modeling multi-agent gameplay. Neural Information Processing Systems, 2019.
12

---

Perolat, J.. Vylder, B. D., Hennes, D.. Tarassov, E., Strub, F., de Boer, V., Muller, P., Connor, J. T., Burch, N., Anthony, T., McAleer, S., Elie, R., Cen, S. H., Wang, Z., Gruslys, A., Malysheva. A., Khan, M., Ozair, S., Timbers, F., Pohlen, T., Fecles, T., Rowland, M., Lanctot, M.. Lespiau, J.-B., Piot, B., Omidshafiei, S., Lockhart, E., Sifre, I.., Beauguerlange, N., Munos, R., Silver, D., Singh, S., Hassabis, D., and Tuyls, K. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 378(6623):990) 999-69999 2022.
Selten, R. Reexamination of the perfectness concept for equilibrium points in extensive games. In Models of Strategic Rationality, pp. 1-31. Springer, 1988.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 2016.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap. T., Simonyan, K., and Hassabis, D. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419): 1140-1144, 2018.
Southey, F., Bowling, M. P., Larson, B., Piccione, C., Burch, N., Billings, D., and Rayner, C. Bayes' bluff: Opponent modelling in poker. arXiv preprint 1207, 2012.
Steinberger, E., Lerer, A., and Brown, N. Dream: Deep regret minimization with advantage baselines and model-free learning. arXiv preprint arXiv:2006. 10410, 2020.
Tammelin, O. Solving large imperfect information games using cfr+, arXiv preprint wxXiv:147755042 2014.
Tammelin, O., Burch, N., Johanson, M., and Bowling, M. Solving heads-up limit texas hold'en em. In Tounty-fourth international joint conference on artificial intelligence, 2015.
Tuyls, K., Pérolat, J., Lanctot, M., Ostrovski, G., Savani, R., Leibo, J. Z., Ord, T., Graepel, T., and Legg. S. Symmetric decomposition of asymmetric games. Scientific reports, 8(1):1-20, 2018.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung. J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, L., Cai, T., Agapiou, J. P., Jaderberg, M., Vezhnevets, A. S., Leblond, R., Pohlen, T., Dalibard, V., Budden, D., Sulsky, Y., Molloy, J., Paine, T. L.. Gülçehre, Ç.. Wang. Z., Pfaff, T., Wu, Y., Ring, R., Yogatama, D., Wünsch, D., McKinney, K., Smith, O., Schaul, T., Lillicrap, T. P., Kavukcuoglu, K., Hassabis, D., Apps, C., and Silver, D. Grandmaster level in Starcraft II using multi-agent reinforcement learning. Nature, 575(7782):350-335) 2019.
von Neumann, Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-32) 1928.
Von Stengel, B. and Forges, F. Extensive-form correlated equilibrium: Definition and computational complexity. Mathematics of Operations Research, 33(4): 2008.
Zinkevich, M., Johanson, M., Bowling, M.. and Piccione, C. Regret minimization in games with incomplete information. Neural Information Processing Systems, 2008.
13

---

A Marginals of a CCE May Not Be a CCE
b
a 1.0 1, -1
a
0,1
Figure 3: The marginal strategies of CCE do not generally form CCE themselves.
Here we give an example showing the marginal strategies of a CCE may form a CCE. Consider μe s.t. pla, a) 0.5 and p(b, b) 0.5. is a CCE. Exzn [p)] = 0.5 for each player. If row (r) were player and column continues play according μ., row's utility is O; if plays instead, their utility is now -0.5. Thus r has no profitable deviations from the CCE recommendations. Column does not either, this can be shown with symmetric argument.
Row's 's marginal strategy s plays a with probability 0.5 and with probability 0.5, s does likewise. (s,; s()) ue(st *0) 0.25.. However, is profitable deviation for now since -0.25, thus the decorrelated strategies from the same CCE are also not a CCE.
B Hindsight Rationality With Respect to Action Deviations Does Not Imply Nash
Here we show that hindsight rationality with respect to action deviations does not imply Nash cquilibrium in 2 player constant-sum games. We show this with player game, Consider the agents strategy, shown in blue, which receives utility of 1. Deviating to [/1 b, /2 a] will increase the player's utility to 2, so the blue strategy is not Nash equilibrium. However, this would require two simultaneous action deviations, one 1 to b and one at I2 to a. Neither of these deviations increases the player's 's utility on their own, so the player is hindsight rational w.r.. action deviations.
I
2
0
Figure 4: Action deviations in a simple game.
C Omitted Proofs
Proposition C.1 (Cai et al. 2016)). In CSP games, for any CCE μs if i deviates to 8,, then their expected utility if other players continue play μ is equal to their utility if other player where to play the marginal strategy profile ,"
Epeny (nr = u,(Si, 8" Vs E S,
C.1
Proof of Proposition
4.3
Proposition
4.3
is an e-CCE of CSP game G, se is an ne-Nash of G.
Proof. Since μ is an e-CCE, Vi we have
max E Exrn (Ms P-:) - Epnn [u)(0)] S MEP,
14

---

which implies (by Proposition
C.1 that Vi E N,
max u; M:(p), s - E pmn [us(p)] Sc A(P.
max u; 5 S c B [u:(p)) EEP;
Summing over N, we get
Σ max Us u. - Σ
(e
Epruy (p)(
(1)
MEP
iEN
ΣE+ E
1 Epon [ui(p]]
(2)
iEN
Σ E c Epru
Σ vi(p)
(3)
iN
LEN
ne +e
(4)
Σ (1(())).
no +
(5)
iEN
Where and (5) use the fact that Vp E P.EiEN uz(p) for some constant. The above inequalities give us
Σ max ui(p), S n Σ Su(s) IEN PEE,,
Rearranging, we get
Σ max u.(p), uu(s") S ne. EN MEP:
All terms in the sum are are non-negative because p best-response s",, Then any particular term in the summation is upper bounded by ne.
C.2 Proof of Theorem 4.6
Proposition C.3. In two-player constant-sun sum gamess for any e-Nash equilibrium s and player i, we have
u (+(+)
s" ES_: ue(si, 8'1) Se.
min
The proof of Proposition C is immediate from the fact that no player can gain more than utility by deviating and the game is constant-sum.
Theorem 4.6 Let G be CSP game. I is (0, subbgame stable, then for any player N and CCE μ of G. we have Vul, (s" S_1) < EEly
Proof. First we show 1. Any marginal strategy s# of CCE μ is Nash equilibrium of G Cai et al. (0016). Then,
Vul, = us((t)- - min :ES
1 s_s)
= Σ
uin(s (9)) - min
Σ (ig(s)18g) (KJEE,
(
Σ uin(st,
Σ
min uig ( 85)- SyE;
(i,j)E,
(ii)e,,
15

---

Where the last line uses the fact that -ė minimize i's utility, so can do so without coordinating since G is polymatrix. Continuing,
Σ
(
min un ui( 15) e,
(.)ER
Σ
(L)))
|
where by (0, -uubgame stability of each Gıj. (f/, is 7-Nash Gty. By Proposition have Wij 6 8j) mill,,es, us(s 83) S 7.
C.3
we
C.3 Proof of Proposition 4.8
Proposition
4.8 In 8- 3-CSP game G the following hold
1. Any CCE of G is 28- -CC of any & CSP&(G).
2. The marginalized strategy profile of any CCE of G is a 2nô-Nash equilibrium of any G & CSPs(G).
3. The marginalized strategy profile of any CCE is a 2(n + 1)ō-Nash equilibrium of G
Proof. First prove claim 1. Let in denote the utility function of in G. Note that V/p E P we have (ū:(p) uz(p)) S Vi E N. Let be any CCE of G. The definition of CCE states
Epzn [u p-1) uz < O Vi N, N. P..
It is sufficient consider only player i. We can preserve the inequality by substituting ü. (p p-i) place of u.(cs. P-;) and (p) in place of u; (p).. This gives us
E E (.. - 5 (7x(p) - 5) 00 Vp
= Epp P-i) - a.() $ 25 Vp.
Thus claim 1 is shown. Claim 2 is an immediate corollary of claim I and Proposition 4.3 Lastly, we
show claim 3. By claim 2, we have the marginalized strategy of p. s", is a 2nô-Nash equilibrium of G E cS), That is for any E N.
d (p s ú, (3 st,) s 2nd Vp Pt.
However, since G is 5-CSP, we may substitute u, (p/. s",) - 5 in place of ū (r slt,)) and u. us("", s",)) 5 in place of (s s" as preserve the inequality.
(u, - 6) - (ui(s,, s - 5)) s 2nd Ap E P..
Rearranging, this gives
Vp EP. ue meldb un (oll 8 S 2nd 28 2(n 1)6
C.4 Proof of Theorem 4.9
Theorem 4.9 IfG 8-CSP and 36 CSPs(G) that (2nő, 7) subbame stable and μ is CCE of G, then
Vul, (s" (_,) < [Ehh 26 < (n 1)7 + 26.
The proof is largely the same as Theorem 4.6 with added approximation since G is no longer CSP.
16

---

Proof. Let be a polymatrix game that is (2mó, >)-subam stable such that & CSPa(G). Let d; denote the utility function of in G. By Proposition 4.8 is a 2nô-Nash equilibrium of G. Then,
Vul; (s") = w;(
min <_,88
o s'4.)
S (s(
min 6_,88-
(5 s'-2) 26,
since G is 8-CSP. Then expanding ū; across i's subgames we have
Σ
min EESL
( 28 (i.)E.,
Σ
(i,)),,
Σ
E
min ( 84) + 28.
efES;
(
(UEE
Where, in Theorem 4.6 the last line uses the fact that C is polymatrix, Gig is constant-sum and -i minimize i's utility and can do so by without coordinating. Continuing, we have
Σ (L.)EE.
min u,(s + 28 Σ
KgE,
(L,)),
E
Usy(s +55)
min uz (z(s + 28 sfES,
(i.)E
Σ
28
(1,))E
E + 28
(n 1)7 + 26.
Where by (2n6, 7) subgame stability of each Gıy, . is 7-Nash of Gsj. By Proposition C.3 s can lose at most y worst case opponent s/ each subgame, since Giy is two-player constant- sum.
C.5 Proof of Theorem
5.3 IJG is 8-CSP in the neighborhood of Sx (An) and 30 E CSP (Ax)) that 7-subgame stable in the the neighborhood of S(A.), then for any E S(A,)
Theorem
Vul; (s. (AAn)) < Exlr + 28 (n 1)7 + 25.
Proof.
The proof is very similar to Theorem 4.9
Writing the definition of vulnerability have
Vul, (s, S(4)) = (s))
min v.
(6)
ES,,
since G is 8-CSP the neighborhood of 8x (An). Swapping out the utility of us for ú, we have
6
ūs(s)
min
in(s,, 25
Since G is polymatrix game,
min
ú, s'-;) 28
(7)
EES ((N))
Σ
un (Si, 85)
min
Σ
(iz(si, +8
(8)
s (A,) (KJ)ER,
(IJ)ER
Σ (n)(31,8))
min (sg(s))()) (AA,)A,))
+ 28.
(9)
17

---

Where, as in Theorem 4.6 and Theorem 4.9 the last line uses the fact that G is polymatrix, Gig is constant-sum and -i minimize i's utility and can do so by without coordinating.
Since Õ is 7-subgame stable in the neighborhood of S(A.) and S(A.). then means (5), 83) is y--ash for each subgame Gij. so has bounded vulnerability within that subgame.
9
Σ
+ 26
(iJ)E,,
< + 28
<n 1)7 + 28
D Normal-Form Algorithms
D.1 Computing Subgame Stability
Let y be the minimum y such that CSP game G' (0, >)-sbgae stable. How do we compute 2? Does involve computing all equilibria of G and checking their subgame stability? The answer is no, it can be done in polynomial time in the number of pure strategies. We next provide an algorithm for computing 2- The algorithm involves solving linear program for each edge in the graph and each pure strategy of those players. This linear program takes pure strategy pt, and finds a Nash equilibrium of G that maximizes i's incentive to deviate to & when only considering their utility in
Giy; call this quantity 7/j
there no such Nash equilibria the solver returns "infeasible". If the solver does not return "infeasible", we update 2 = ().(E))) maxpePP, Tij
Algorithm 2 Compute
Input: G = E,, u), polymatrix game
y < DC
for (i E E do
for p. P, do
if LPI not infeasible then
3 - (P)
7 mmx Tij)
end if end for
for p¹ E P, do LP i,,) not infeasible then
6 - L
? max(7, 151
end if end for end for return 7
Let aglpl n) be the advantage of deviating & from a joint distribution over pure strategies:
app...10 =
Σ
Ugg (.
Eprips
Σ
(.))E
(..))E.
(0)
(b)
18

---

Note that (a) is linear function of since of is a marginal strategy. (b) is also linear function of and so 0z (P): ()) is a linear function of μs. Likewise, let
asyld4 11) = uiyld 19) Eppp (uig P;)]:
be the advantage of p in the subgame between and j. LP1 (1,5,0]) is given below. The decision variables are the weights of for each E P and 1éj.
LP 1
PP/
max
lij
s.t.
as 1) 50 V.EN,
a; %i
Σ ((P) = PEP
m(p) [0,1]
Ap
We get away with computing CCE rather than targeting Nash equilibria because the marginals of any CCE are Nash equilibria in CSP games Cai et al. (2016).
The whole procedure runs in polynomial time in the size of the game. We need solve LP, which takes polynomial time, at most 2 maxeN [P times.
D.2 Finding Constant-Sum Polymatrix Decomposition
Projecting a game into the space of CSP games with minimum can be done with a linear program. Let be the minimum 5 such that G is 6-CSP. We give a linear program that finds 5 and returns CSP game G e CSP (G)) The decision variables are the values of (p)(p) for all i + E N, P. ò and constants for each subgame Ciy, for all + j.
LP 2
min ś
s.t. wp(p)
Σ
ung(es Pi) SE WEE
jE-i
ux(p) E Cus(Pss -5 ViEN
SE-1
+ Uzi(Pis -.j Vi Eij
E
Extensive-Form Games
Section Doction[4develgee devellped notions of approximately CSP and subgame stable in the context of normal-form games. Here, we apply these concepts to extensive-form games. While any extensive-fore game has an equivalent induced normal-form game, analysing properties of an EFG through its induced normal is intractable for moderately-sizer EFGs, since the size the normal-fort representation is exponentially larger.
After background on extensive-for games, we introduce novel "extensive-fome version" of normal- form polymatrix games, which we call Poly-EFGs. The major benefit poly-EFGs over normal-fomm form polymatrix games is their efficiently: Poly-EFGs are exponentially more compact than an equivalent normal-form polymatrix game. The results of this section extend the theory of Sections 4 and using this more efficient representation. We also give proof-of-concept showing that poly-EFGs can be used efficiently decompose extensive-fone games by giving an algorithm for decomposing perfect information EFG into poly-EFG.
19

---

E.1 Background on Extensive-Foree Games
We use the imperfect information extensive-form game (EFG) as a model for sequential multi-agent strategic situations. An imperfect information extensive-fone game is 10-tuple (N, H, Z, A, P. I. me) where N set of players; A is a set of actions; H is a set of sequences of actions, called histories; Z C H is a set of terminal histories; A H - A is function that maps history to available actions; P: - N is the player function, which assigns a player to choose an action at each non-terminal history;
(Mahee is set of utility functions where My : Z + is the utility function for player i; = (Ii)en where I is a partition of the set {h E HI P(h) i} such that if h, h' E I I₁ then A(h) A(h'). We call an element / E I; an information set. The chance player has a function To h) vh : P(h) = c which returns the probability of random nature events a E A. Let Ne N U {c} be the set of players including chance.
For some history h, the jth action in h is written hy. A sub-history of h from the jth kth actions is denoted f and we use h. as shodt-hand for ho:k- If a history h' is a prefix of history h. we write I E and if / is proper prefix of h, we write h' t h.
A pure strategy in an EFG is a deterministic choice of actions for the player at every decision point. We use p; I A to denote pure strategy of player i, and the set of all pure strategies as P.. Likewise, 9, E ((P)) = S; is a mixed strategy, where A(X) denotes the set of probability distributions over domain X.
There are an exponential number of pure strategies in the number of information sets. A behavior strategy is compact representation of the behavior of agent that assigns probability distribution over actions to each information set. We use म; E II, = (A()))) Iez, to denote a behavior strategy of player i and i (a, I) as the probability of playing action a at I. Let I (h) be the unique information set such that h E T. We overload म., (a. h) = ne (a, (h)).. We use E P. 8 E S and π E IT to denote pure, mixed and behavior strategy profiles, respectively. Note that P is subset of both IT and S.
Given a behavior strategy profile, let
pr(ha, m2)
II
Ti(a, h)
hn P(ho)) p pi(12, h2 TT)
p(h1 1)) = II
sEN.
p- (h, h2 --:)
II JEN.V6)
be the probability of transitioning from history h1 to h2 according to m. v and T- respectively. Let (1),,,,),_=(,,,,, ny)) and p(2, be short-hands for (2, z, m.) (-, and p(80, 2, m)) respectively, where Ø is the empty history.
We detine the utility of behavior strategy as:
(II =EZ ViEN
(T(T)) Exnr [ux(2]] = -p(Zz = Σ II pil() ui(z).
=EZ
Perfect recall is common assumption made the structure of information sets in EFGs that prevents players from forgetting information they once possessed. Formally, for any h E / let Xx(h) denote the set of (T,a) a) s.t. 7 I, and 3/' E / and H/a [ h. Let (h, be defined analogously for -i and X X(h) for all players.
Definition E.1 (Perfect recall). V E I, Vr, E I, (h)) = X:())) then i has perfect recall. all players possess perfect recall in some EFG G, we call G game of perfect recall.
In games of perfect recall, the set of behavior strategies and mixed strategies are equivalent: any behavior strategy can be converted into a mixed strategy which is outcome equivalent over the set of terminal histories (i.e. has the same distribution over 7) and vice-versa.
Theorem E.2 (Kuhn (1953)). In games of perfect recall, any behavior strategy n. has an equivalent mixed strategy s; (and vice versa), such that
P((z. = Epires (p((2,p))]
20

---

Theorem E.2 establishes a connection between equilibria in behavior and mixed strategies: a Nash equilibrium behavior strategy profile implies the equivalent mixed strategy profile is also a Nash equilibrium in mixed strategies and vice-versa.
We may also reduce any extensive-form game into equivalent normal-form game.
Definition E.3 (Induced normal-form), The induced normal-form of an extensive-form game G (with utility functions uz) is normal-form game G' -N, u') such that up(p) uz(p)
The induced normal-form of an EFG has players making all decisions up-front. It is not always practical to construct an induced normal-form, but the concept useful for proving things about EFGs.
E.2 Poly-EFGs
What is the appropriate extension of polymatrix games to EFGs? Given some r-player EFG G, what should the subgame between and j be in the graph? Unlike in normal form games, players act sequentially, and and j may either observe actions or have their utility impacted by other players. There is additional structure present in EFGs beyond the players' pure strategies.
The approach take is to have EFG for each pair of players and For simplicity, assume that each subgame G' shares the same structure as some n-player game G, but information sets where P(I) & {i.j} now belong to the chance player c.
Definition E.4 (Subgame). Let G (N.A A, P.u. Re) be some EFG. We define subgame G = (fi,). H, A, P (Myy I,,,), structurally identical game to G between and j with player function P' and utility functions (u'g- u(ja). then
(Phh)
P(h) (i,j) O.W.
P'(h)
and let n' be the strategy of the chance player in Gyy- We put no restrictions on T'
Note that u u/j are not necessarily defined in the above definition. They may take any values. We merely want the subgame G'y to share the structure of G. In Gly= i and j's utility only depends on their strategies n., Ty and chance's 's actions T/::
Uh (Tz, R.) = 1. (mim))))))) [ulg(z)]
= Σ p,(2, (p)p T ((),
ZEZ
What should n". be defined as? This turns out to not matter very much. Given any subgame G with chance strategy Th and utility functions w/ys 2/j for any G7/ with chance strategy T" we can find u/y ufe so that the utility of players between the two games will always equal for any strategy profile (TT, )
Definition F.S. We say me is filly mixed if T'(a,, h)) > 4Ah ( (()) = A(h)
Proposition E.6. Let G be an EFG and Gig subgame between and j with utility functions Wiy u/y and fully mixed chance strategy de Given G a subgame between and with fully mixed chance strutegy nhd we may find uhyg vl/a such that Vn,, Fy we have uly (T))))) = wl/g(1s,, TT) and d'ylTT, Tz)= (T, Tg).
T;)
21

---

Proof. Note that Pe(2, (o(2, # 0. Then Vz Z, define ul((2)
Pe(em))) Uly(2) and
pe(s,
()((z) = pe(a,a)) Pa(a,)))
(22(()) Then
(Ta, TT) Ep((z, p (1)p """"")
267
Polz, m²) polz, uly(2)
Σ pp((z.m.)p)))
Σ (1tem sEZ
uh (T;, nT).
For the remainder of this work, when defining a subgame between i and given an EFG G, we define the subgame chance player's strategy to be equal The in G information sets where P(I) in G and uniform randomly otherwise.
Having defined subgames, we may now define our representation of extensive-form polymatrix games.
Definition E.7 (Poly-EFG), A poly-EFG (N, E, g) is defined by graph with nodes N, one for each player, a set of edges E and a set of games 9 = (Giz ((i,j) E E) where Gig E 9 is a two player EFG between and j and all Giy G are subgame between and j and all subgames are defined with respect to some EFG G.
Let Giy 9 denote the subgame between i and j. We use subseript ij (e.g. Ziy) refer parts of Giy.
Since each subgame of the poly-EFG is the subgame of the same G, the space of pure, mixed and behavior strategies is the same each subgame for any player. A player chooses a strategy (whether pure, mixed or behavior) and plays this strategy in each subgame. A player's global utility is the sum of their utility in each their subgames. We have
(T)
Σ (G)EE
Uiy Ty).
where E; S is the of edges connected in the graph and usj is the utility function of in subgame Gig.
E.3
Constant-Sum and Subgame Stable Poly-EFCI
Here, we give definitions of constant-sum and subgame stability for poly-EFGs. These definitions largely identical to their normal-fome foom counterparts, we merely provide them here for completeness.
Poly-EFGs are constant-sum if, for each subgame, the utilities at the terminals add up to constant. Definition E.8 (Constant-sum). We say a poly-EFG is constant-sum if vGay E G, e Zzy. (z + (2) Cij where Zij is the set of terminal histories of VG.j and eij is constant.
We may also define approximate poly-EFGs in the same way as normal-form games. Definition E.9 (8-constant poly-EFG). An EFG G is 8-constant
Poly-EFG (6-CSP) if there exists constant-sum Poly-EFG & with global utility function ă such that Vi N, II. (m) ú, (=) < 6. We denote the set such CSP games as CSP (S)&
Finally, define subgame stability for poly-EFGs. Our definitions are near-identical from the normal-form definitions.
Definition E.10 (Subgame stable profile). Let G be a PFIy-EFG. We say strategy profile и is 7-subgame stable if v(i.)) E E, we have (T, π,) is a 7-Nash of Gij- Definition F. (Subgame stable game). Let G be Poly-EFG. We say G (e, -uubgame stable for any Nasa equilibrium x of G, is y-subgame stable.
22

---

E.4 Theoretical Results For Poly-EFGs
Our theoretical results from Sections 4 and 5 continue to hold in poly-EPGs. The idea is to use the induced normal-ford form of a poly-EFG. We assume perfect recall.
First, we will characterize what self-play will produce in EFGs. These called marginal behavior strategies.
Definition E.12 (Marginal behavior strategy), Given some mediated equilibrium (1,, (9,) ) let T. be the marginal behavior strategy for i where n. (a, I) is defined arbitrarily if EptEP.(T) 8, (1() and otherwise
Ea (p.) EnEPIn (D))
m&t (a, 1)
I A(T),
where (pi) Ep ((pi.p-)).
Definition E.13 (Marginal behavior strategy profile). Given some mediated equilibrium (μ, ( (0)) let Th be a marginal behavior strategy profile, where x. is marginal behavior strategy Vi E N.
Definition E.14 (Induced normal-form polymatrix game). Given Poly-EFG G
N,,.)). the induced normal-form polymatrix game is a polymatrix game G = (N, E, P. such that P; is equal to i's set of pure strategies each Gij and u (Pis P5) = Uiz Pj) =
Evez Pi(z, p()pp Pt) po,,,, (=)));;z) where Wij the utility function of Gij-
In games of perfect recall, every behavior strategy n, has an equivalent mixed strategy 8 (by Kuhn's Theorem), which means for any perfect recall EFG G, we can use the poly-EFG representation instead of turning G into a normal-form game then using a normal-form polymatrix game to get the same vulnerability bounds on G. Given let s be profile of equivalent mixed strategies.
From Kuhn's 's Theorem and an assumption that each Gij G has perfect recall, derive two immediate corollaries.
Corollary E.15. T is y subgame stable for a Poly-EFG t where each subgame has perfect recall, then S is y subgame stable in the induced normal formal-formm// polymatrix game of G.
Corollary E.16. For EFG of perfect recall G, if G is 6-CSP-EFG then the induced normal form of G is 8-CSP.
An extension of Theorem 4.9 holds for poly-EFGs. Let I be the set of marginal behavior strategy profiles for any CCE of G and II be the set of marginal behavior strategies for i.
Proposition E.17. If an EFG G is 8-CSP and 36 E cSPs(G) that is (2nd, -ussugamee stable and is a CCE of G. then
Vul, (xx :I I |E,17 + 25 S (n 1)y + 25,
Proof. Transform & into its induced normal-form polymatrix game G² By Corollaries E. and the induced normal form of G is 5-CSP and (2no, r)-subgame stable. By perfect recall, can convert nọ to an equivalent mixed strategy profile s and do likewise with any π E II Then apply Theorem 4.9 using s", S_, and the induced normal-fome polymatrix game of G to bound vulnerability on G's induced normal form, and hence G.
E.5 Vulnerability Against Self-Taught Agents in EFGs
Next we show an analogue of Theorem 5.3 for extensive- games. In Section 5 we defined S(.A) as the set of marginal strategy profiles for no-regret learning algorithm A. Many algorithms for EFGs will compute behavior strategies, so we use II(AA) = {nl (4, (L.)ee) E M(A) as the set of marginal behavior strategy profiles of M(A) (recall that M(A) is the set of mediated equilibria reachable by learning algorithm A. Then let IT; = {T; π E IT{A)} be the set of i's marginal
strategies from IT(AA. For example, if A is CFR, (MA) is the set of observably sequentially rational CFCCE Morrill et al. (2021b) and (TA) is the set of behavior strategy profiles computable by CFR.
NNte that "CCE" refers normal-form CCE (NFCCE) in the language of Farina et al. 2020
23

---

Next, suppose each player learns with their own self-play algorithm A,. Let Av (A.....AA,) be the profile of learning algorithms: II (An) = XiEN (A.) be the set of all possible match-ups between strategies learned in self-play by those learning algorithms and II (An) = -
be the profiles of -i amongst these match-ups.
Definition E.18. We say game G is 8-CSP in the neighborhood of C if there exists a constant sum poly-EFG G such that Var IT' we have [u((=) uz(TT] S 8. We denote the set of such CSP games as CSPs(G,1)
Definition E.19. We say poly-EFG game G is 7-subgame stable in the neighborkood of TV' VI E II', J)i,j) & E we have that (ma, Ry) is a Y-Nash of Gig-
Proposition E.20. G 5-CSP in the neighborkood TI* (An) and 36 CT that is y-subgame stable in the the neighborhood of As) then for any E IT(AA))
Vul, (Tt, II, (AN))
I |E 26 _ (n 1)y 26.
The proof goes the same way in Corollary E.17 Use the induced normal-form polymatrix game of
G' and Theorem 5.3 to derive bounds for the induced normal form of G, which then apply to G.
E.6 Leveraging the Poly-EFG Representation for Computing CSP Decompositions
The poly-EFG representation gives rise more efficient algorithms for computing poly-EFG decomposition. As a proof of concept, we show that in perfect information EFGs, we can write linear program compute the optimal polymatrix decomposition for EFG that is exponentially smaller than LP 2 from Section D.2] Recall that d is the minimum value of such that game 6-CSP. In perfect information EFG, can compute with the following LP. The decision variables are the values of (2) A2 E Z, (i,j) E E and Cij vii.j) E E.
LP 3
min
uz(z)
Σ (z)(2) WEN,
jE-i
u2(2) Σ (z)()) 2 -
viE N, E
jE-i
ū.y( (=) + 0g(=)= = N,
The trick is that in perfect information EFGs, each pure strategy profile leads to a single terminal. Hence, rather than having constraint for each pure strategy profile, a constraint for each terminal will suffice. This leads to an exponential reduction in the number of constraints over LP 2.
F Details of SGDecompose
Next, we give the full details of SGDecompose. We give details here using our poly-EFG representa- tion, since this is the representation we use in our experiments.
For each subgame G.j we store a single vector üij where the entry ūey(z) (z) gives the value of utility for corresponding terminal We additionally store constant ě;j for each subgame. Player i will use ūiy when computing üig (Te, n;)::
üig (TT RJ) = pi(Zz,T)pe m))po(s Te)
=EZ
Whereas we compute (T,, nT) as follows.
( mT) = Σ Dp m2) (Gi - ūzz(2))
=EZ
For simplicity, let denote the stacked vector of all Miy and &gj. We additionally initialize G as fully connected graph.
24

---

The overall loss function which we minimize has two components: first, L is the error between the urility functions of and G; it is proxy for 6-CSP.
L
u)) =
Σ iEN
(x) us(#+)
Wey (sg( m7)) ui(a)
Σ
Σ (i.JEE
The other component of the overall loss function, L" measures the subgame stability. First, we define Cij, which only applies single subgame.
(Tag. Tigi ú) = max (ū)((T) mT) ū. (TT))
+ max (ūgj((T, 73) ( ).0)
Where Taj = (Ti, TT) is profile and m.z = ( ) is profile of deviations. Then
L (T, ; = Σ
(JJE
Algorithm BrrrtthmmBshor ssoows how compute subgame stable constant-sum polymatrix decomposition via SGD. As input, the algorithm receives game G, a finite set of strategy profiles II', learning rate number of training epochs T. hyperparameter À [0, 1] and batch size B. First, initialize ITx as the set of all match-ups amongst strategies in IT'.
We then repeat the following steps for each epoch. First, compute best-response (for example, via sequence-form linear programming) to each strategy πę in I1' each subgame; the full process is shown in Algorithm After computing these best-responses for the current utility function G we try to fit ů to be nearly CSP in the neighborhood of II and subgame stable in the neighborhood of II'. Since II is exponentially larger than II', we partition into batches, then use batch gradient descent. We use the following batch loss function, which computes the average values of L and L over the batches, then weights the losses with A. Let IT denote a batch of strategy profiles from 1Tx with size B, the overall loss function is
c(11, II;, ú. u)
Σ (,;ūū,
(1-1)
Σ Σ (T,)));)
IT'
TEIL
TEIl' x'lll
We take this loss and find its gradient with respect to ú, then update
à ύtūー VaC(II, II', II': ū. u).
We found that in practise the gradient can be quite large relative to û, which has the potential to destabilize optimization. This alleviated by normalizing the gradient by its 12 norm.
g - V&L(II II', II"; ú,
g
à 17
[9g]]
G
Experiment Details
The codebase for our experiments is available at Self Self-Play-Polymarrix
G.1 Ledue Poker
We ran SGDecompose 30 times, each time with its own set of strategy profiles. These 900 strategy profiles are generated with CFR+ in self-play for 1000 iterations with random initializations. We
25

---

Algorithm 3 SGDecompose with behavior strategies
Input: G, II' ?). T, X, B
Initialize ú to
ITx XieN TI;
for t E 1...T do
II" - get IT')
8 4 partition of IIx into batches of size B
for 11 do
9 < V C(T II' ū.,
g ù - ū T
end for end for
(Lastly, output 8 and 7)
+ max [x) (T()
< max IJX (is ((R((BR - (T) m,))
return ú, 7,7
Algorithm 4 getBRs
Input: G, II'
I < Ø Vi E N
for i # E N x do
for n E I1 do
compute Fly E arggmax, mTy(
II; < II (ml))
end for end for return XIEN I
randomly initialize CFR+ with regrets between 0 and 0.001 chosen uniformly at random, which are the default values in OpenSpiel.
Interestingly, we found that CFR+ converges to approximate Nash equilibria in Leduc poker, with a maximum value of equal to 0.013 after 1000 iterations. As will show in Appendix G.2 CFR also empirically produces approximate Nash equilibria in Leduc poker.
Let I(CFR+); denote the set of CFR+-leamed strategy profiles for run j: and (CFR++)
denote the set of all match-ups between these 30 strategy profiles. Figure 5 shows diversity of II(CFR+) for each of the 30 runs. We measure the diversity of each 11(CFR), by taking each pair of strategy profiles т, n' E II(CFR), and computing the total variation between these two probability distributions induced over the terminal histories of Ledue poker. We denote the maximum total variation for run j as TV,, where
TV,
max (((RR) 2 #EZ
(p(e,)) p(2,
TV, is constrained to be between and 1, where means the two distributions are the same and 1 means they maximally different. Figure shows the maximum total variation between any two of the strategy profiles used each run.
We used the same parameters for each run of SGDecompose: À = 0.5, B = 30, T = 200. We used a learning rate schedule where the learning rate 7) begins at 2- then halves every epochs until reaching 2-17 to encourage convergence. Our results are shown in Figure 6 We see that across the 30 runs of SGDecompose, Ledue poker at most 0.021 HPP1 in the neighborhood of TI (CFR+)) and 0.009-subgame stable in the neighborhood of IT(CFR+); Figure 7 shows the maximum vulnerability with respect to the strategics in each of the runs compared to the bounds on vulnerability given by Proposition E.20 We compute the maximum vulnerability as
Vul = max max IEN (EI(CFR))
Vul, (T, 11 (CFR),
(10)
26

---

0.28
0.26
0.24
TV,
0.22
0.20
0.18
Figure 5: The maximum total variation for each II(FFR), used in different runs of SGDecompose in Ledue Poker. Different runs are shown on the x-axis, and the corresponding TV, for run is shown with the bars. value of 0 indicates minimal diversity and means maximal diversity. The minimum, mean, maximum and standard error across runs are 0.21, 0.22, 0.26 and 0.0016, respectively.
see that the bounds are between 1.89 and 3.05 times the actual vulnerability, and are on average 2.51 times larger with standard error of 0.049.
0.0200
0.008
0.0175
0.007
6
0.0150
0.006
0.0125
0.005
0.0100
0.004
0.0075
0.003
(a)
(b)
Figure 6: Boxplots showing the values of 8, and 7i for each of the 30 runs of SGDecompose in Ledue Poker. Figure 6a shows the values of ój. with the minimum, mean, maximum and standard error being 0.006, 0.009, 0.021 and 0.00046, respectively. Figure 6b shows the values of ?y, with the minimum, mean, maximum and standard error being 0.003, 0.004, 0.009 and 0.00016, respectively.
G.2 CFR Finds Approximate Nash in Ledue Poker
was previously believed that CFR does not compute an c-Nash equilibrium on 3-player Leduc for any reasonable value of Previous work found that CFR computed 0.130-Nash equilibrium after 10s iterations Abou Risk & Szafroo (2010). We saw in the previous section that CFR+ computes approximate Nash equilibria in Ledue poker-dock this hold for CFR well?
We ran runs of CFR in self-play 10,000 iterations and found that all of our strategies converged to approximate Nash equilibrium with the maximum 0.017 after only 10a iterations. Figure 8b
27

---

0.08
Vulj
2(6 + y)
0.07
0.06
Expected Utility
0.05
0.04
0.03
0.02
0.01
0.00
Figure 7: Bounds vulnerability compared to true vulnerability in Leduc Poker for each run. Each of the 30 runs are shown on the x-axis. For each run j. we compute the bounds determined by Proposition E.20 which (n - (>y, 26j 2(n; 6,). These value shown in orange. The blue bars are the maximum vulnerability in each run, computed using (10). The ordering of
bars in this plot matches the ordering of bars in Figure The rightmost had both the highest vulnerability and highest diversity.
shows the shows the maximum deviation incentive
max (1 T-:) (x(
for each of the CFR strategies и computed by CFR in Ledue Poker. Each column is for one of the players and each point is one of the random seeds. We see the maximum value of after 10,000 iterations 0.017. Figure Bal shows the maximum deviation incentive over 10,000 iterations. We average learning curves over 30 random seeds.
H
Toy Hanabi
In games with low values of ê and self-play will perform well against new opponents; however the converse also true? Do games where self-play performs poorly against new opponents have high values of 8 and y As mentioned earlier, self-play struggles to generalize to new agents in some games with specialized conventions (Hu et al., 2020). Hanabi is one such game (Bard al. 2020). Hanabi is a cooperative game where players cannot see their own hands, but can see all other players hands; therefore players must give each other hints on how to act.
We show that a small version of the game of Hanabi is not close to the space of CSP games and self-play is quite vulnerable. We use Tiny Hanabi in the Openspiel framework (Lanctot al. 2019) with our own payoffs, shown in Figure g Chance deals one of two hands, or B with equal probability. Only player may observe this hand and must signal other players through their actions, and d2, which hand chance has dealt. If both players 2 and 3 then correctly choose their actions to match chance's deal ((a, a) for A (b, b) for B) then all players get payoff equal otherwise all players get O.
01 and d2 may learn either of these conventions. However, a player trained self-play encounters a set of players trained in an independent instance of self-play, they may not have compatible conventions.
to mean different things, could signal 2 and play a, or b. Self-play
This is indeed what happens when we train CFR on Tiny Hanabi in Figure 9. We trained 30 runs in self-play with different random initializations for 10,000 iterations. Some of these runs converged to
28

---

Player 1
Player 2
Player 3
10
100
100
10-1
10-1
10
10-2
10-2
10
5000
10000
5000 Iteration
10000
5000 Iteration
10000
Iteration
(a)
0.016
0.014
0.012
0.010
0.008
2
3
Player
(b)
Figure 8: CFR empirically computes Nash Equilibria in Ledue Poker. (a) shows learning curves over iterations for each the players. We measure e by finding a best-response with sequence-form linear programming every 1000 iterations. We show each of the individual instances of CFR with different random initializations light-coloured lines and the average across seeds in bold. (b) shows the distribution of at iteration 10,000.
each convention and when played against each other miscoordinated. We found
max max Vul, (T,11"((FFR) 1, KE (CIR)
as expected.
We decomposed Tiny Hanabi and found = 0.5 and Rs 0, meaning the true vulnerability matched what our bounds predicted since (n 1)> + 28 Why y 0? We found that this was because our algorithm was setting the payoff's to equal to 0.50 for all terminal histories, which is trivially polymatrix.
29

---

A
B
2
2
0
b
a
b
a
b
b
0
a
a
1
Figure 9: Tiny Hanabi. We omit payoffs of 0 at terminals.
30


Reviews:
[{"review_id": "1PagSi0w8v", "reviewer": "Reviewer_hBPZ", "summary": "This paper explores the intriguing problem of why no-regret algorithms seem to approximate well in multiplayer games, a phenomenon that has been empirically demonstrated in multiagent poker. The authors identify a structural property in multi-player games that allows performance guarantees for strategies derived through self-play algorithms. They propose that multi-player games can be projected into a series of two-player constant-sum games, known as polymatrix games. The proximity of a game to this structure is hypothesized to diminish the effect of correlation issues on the removal of a mediator. The researchers take an algorithm-agnostic approach, which broadens the applicability of their analysis to a variety of game-theoretically inspired learning algorithms and MARL algorithms that converge to coarse correlated equilibria.\n", "questions": "How can the theory be applied practically? Can it be used to predict whether a no-regret algorithm will converge to a low-exploitability strategy in a new game?\nCould the use of the term 'vulnerability' over 'exploitability' be explained or justified in this context?\nWhat are the detailed parameters and specifics of the experiments conducted, such as the number of seeds and the range of no-regret algorithms tested?\n", "limitations": "There are certain limitations in the terminology used in the paper. The authors use 'vulnerability' instead of 'exploitability', although 'exploitability' is the term most widely used and recognized in this field. In addition, the term 'self-play' can lead to confusion, as it can generally refer to methods where RL agents play against themselves, which are not no-regret. The term 'no-regret' would be clearer. Lastly, at the end of page 9: “and if there exists a game with this set with high subgame stability” do you mean “and if there exists a game in this set with high subgame stability”?\n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's strength lies in its novel approach to an important problem. The authors introduce theory that all multiplayer games can be projected onto the space of polymatrix games, offering a promising direction for further research. If a high subgame stability game exists within this space, no-regret learning algorithms are predicted to converge to low-exploitability strategies. Additionally, the authors' algorithm-agnostic approach ensures that the analysis remains broadly applicable to a variety of game-theoretically inspired learning and MARL algorithms.\n", "weaknesses": "The paper's main weaknesses lie in its experimental section, which comes across as somewhat unclear. The section seems intended to demonstrate that CFR will always converge to a low-exploitable strategy due to the subgame stability of the game, but this is not clearly stated. If the goal is to show that no-regret algorithms will always converge, the experiment design should include many seeds with different hyperparameters and many different no-regret algorithms. Secondly, it's unclear how this theory can be practically applied. For instance, if a new game is introduced, can it be predicted ahead of time whether CFR or another no-regret algorithm will converge to a low-exploitability strategy? This potential application isn't clear and should be further highlighted if it is indeed feasible.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review.\n\n### Response to Questions\n**Practical applications.** This work can be used practically to show in which multiplayer games pre-computing a strategy via self-play is desirable. It absolutely can be used to predict whether the strategy of a no-regret algorithm will have low vulnerability. We know that for any two-player constant-sum games, strategies learned via no-regret self-play have performance guarantees. We see the practical use of our theory in much the same way: showing a particular game/application is subgame stable CSP will give similar theoretical guarantees. \n\nShowing a game has these properties can be done analytically by reasoning about the structure of a game. One could also sample strategies and empirically test whether a game is subgame stable CSP in the neighborhood of these strategies using our algorithm. This approach could quickly build intuition about a game before formally proving it is subgame stable CSP. \n\nWe also think our work could be applied in mechanism design for multiplayer settings. A mechanism designer could be sure to design a game to be subgame stable CSP. Behavior of agents would likely be more predictable and stable. \n\n**Vulnerability vs Exploitability.** We chose to use the term “vulnerability” over “exploitability” in our work since “exploitability” already has a different meaning in the literature for n-player games. For example in this paper (https://www.ijcai.org/proceedings/2022/0484.pdf) exploitability is defined as the average incentive to deviate across players. This is a different quantity than vulnerability, which we define as the difference in utility between a strategy profile and the worst-case joint deviation by $-i$. \n\n**Experiment Details.** We tested a single no regret algorithm: vanilla CFR (the code is here: https://github.com/deepmind/open_spiel/blob/master/open_spiel/python/algorithms/cfr.py). We used CFR with simultaneous updates. The only modification we made was to allow random initialization of CFR’s initial strategy, which is uniformly random by default. We used 30 random seeds. We chose CFR since it is a widely used algorithm and efficient for large games. \n\n### Response to Limitations\nWe will clarify the distinction between the usual RL self-play and no-regret self-play. \n\nWe do mean the latter sentence. Thank you for catching that. \n"}, {"review_id": "MOfSfsvwd7", "reviewer": "Reviewer_Wd36", "summary": "In multiplayer games, the authors derive bounds for the vulnerability of marginal strategies trained via no-regret self-play against other, uncorrelated agents independently trained via no-regret self-play. This is done by projecting games onto the space of constant-sum polymatrix (CSP) games, which can be decomposed into a set of 2-player constant-sum games between individual players. The closer this projection is, the tighter the bound on self-play's vulnerability to other self-play-trained agents is. This claim is validated by demonstrating that 3-payer Leduc can indeed be closely approximated as a CSP game and that the calculated vulnerability bounds are relatively close to the empirically measured vulnerability among marginal CFR strategies from many seeds.", "questions": "Are there any heuristics one may be able to look for in larger games that might indicate when a game has a high chance of being approximately decomposable as a CSP game? If there is intuition on this to be gained from explicitly analyzing smaller games, it would be a great thing to discuss.", "limitations": "All limitations have been adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A bound on the vulnerability of marginal no-regret strategies to other uncorrelated no-regret strategies is novel and highly useful to the game theory/AI community.\n- The paper is well written and concepts are clearly explained.", "weaknesses": "- I would have preferred to see a range of common tractable games examined to get an intuition on when and how often a game can be closely approximated as a CSP game (and thus provide a useful bound on vulnerability). Currently, experiments only include Leduc Poker.\n- The analysis method is not immediately transferable to large games, and this is clearly stated as a limitation.\n\n\n- Minor note: It's not explicitly stated until the very end of section 6 that the 3-player variant of Leduc Poker is used for experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and interesting questions.\n\n### Response to Weaknesses\n1. We agree that it would be interesting to validate our approach on a larger suite of games. Since submission, we have conducted experiments on a toy Hanabi game and found that self-play performs poorly against new opponents and the toy Hanabi game is not well-approximated by a CSP game.\n\n2. We think better algorithms for decomposing large games is a great direction for future research. Our analysis still applies if you can analytically show that a large game is subgame stable CSP. Since submission, we have also improved our algorithm which allows us to more efficiently decompose Leduc poker, which already has about 25,000 information sets. \n\n3. We will add this clarification. \n\n### Response to Questions\nWe think that poker might be well-approximated by a CSP game because for most hands, all but two players fold relatively quickly, which means the game really looks like a set of two-player games. Bad Card shows this intuition by having the dominated strategy reduced game being CSP, but the overall game isn’t. One could also look for independence between the interactions between agents. For example, if an agent were to simultaneously play two games of chess, this overall “game” would be CSP. \n"}, {"review_id": "0qrzm3ENb3", "reviewer": "Reviewer_wuxJ", "summary": "This paper asks and answers the question: \"In what games does self-play (with regret-minimizing algorithms) in multiplayer imperfect-information games perform well?\"\n\nThe motivation behind the question is that such algorithms, such as multiplayer versions of CFR (which has theoretic guarantees in 2-player zero-sum games), have empirically performed well in some multiplayer games, despite no previous theory guaranteeing that they will do so. (The salient example is no-limit Texas Hold'em, in the work \"Superhuman AI for multiplayer poker\", Brown & Sandholm 2019.)\n\nThis paper answers the question primarily by looking at the concept of the coarse correlated equilibrium (CCE), since that is what the policies of the regret-minimizing players will converge to. The authors show that if games can be decomposed into a bunch of 2-player constant-sum games, called a constant-sum polymatrix (CSP) game, and the CSP game fulfills some additional properties, then we can bound the worst-case performance of a player's CCE strategy. They also show that even in games which can't be factored into polymatrix games (which is most games), we can project them into the space of CSP games, and still bound the worst-case performance of each player's CCE strategy.\n\nThey also refine the analysis further by examining worst-case performance only against other self-play strategies. Finally, they perform experiments on multiplayer Leduc poker, and show that the empirical worst-case performances are within the bounds predicted by their theory.", "questions": "It's not clear to me how important the caveat in Footnote 3 on page 8 (section 6) is. So CFR does not necessarily converge to a CCE. The experiments in Section 6 use CFR. Is my interpretation correct that you take the marginal strategies of the CFR iterates, and hand-wavingly say that we can assume they are marginal strategies of (a distribution converging to) \na CCE, even though they're not?", "limitations": "The authors adequately addressed the limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- I think this is an excellent paper. The question it asks and answers is fascinating, and one that I think was begging to be examined for several years now. Therefore, I judge this paper to be a significant contribution to science.\n- The results of the paper are novel and nontrivial. \n- The paper is well-written. The writing is clear and understandable. The introduction explains the background and motivates the problem well.\n", "weaknesses": "The paper mentions no-limit Texas hold'em as a motivating real-world positive example of self-play working in multiplayer games. I also suggest that the authors mention some real-world negative examples -- for example, FAIR's line of work on Diplomacy, particularly the self-play agents performing poorly against humans in \"No-Press Diplomacy from Scratch\", Bakhtin et al 2021 https://arxiv.org/pdf/2110.02924.pdf (the problem is the motivation of \"Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning\" Bakhtin et al 2022: \"the resulting agent DORA does very well when playing with other copies of itself. However, DORA performs poorly in games with 6 human human-like agents.\")\n\ntypo on line 336: \"with ... be the set\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. \n\n### Response to Weaknesses\nWe think this is an excellent suggestion for our work, and we will definitely mention this. Since submission, we conducted additional experiments on a toy version of Hanabi (another game where self-play is known to perform well in training but poorly against new agents) and found that this game was not well-approximated by a CSP game. \n\n### Response to Questions\nThe footnote was in order to clarify a detail about the implementation of CFR. The OpenSpiel CFR is indeed guaranteed to produce the marginal strategies of a CCE, since the average of the marginal strategies is equal to the marginal of the average strategy profile. However, if one wanted to extract the actual joint distribution across pure strategies, one would need to use a method like CFR-JR. We will clarify this detail. \n\n"}, {"review_id": "Y7SwlTQh7t", "reviewer": "Reviewer_WEmp", "summary": "The paper studies theoretical performance guarantees for agents learned using self-play in multiplayer games. Self-play is a common approach of machine learning in multi-agent systems for generating unbounded quantities of training data, but agents trained using self-play may perform poorly against new agents whose behavior differ dramatically from those seen during training. Despite guarantees previously established for self-play agents in 2 player constant-sum games, these guarantees do not extend outside of two-player constant-sum games. To solve this problem, the authors identify a structural property of multiplayer, general-sum game and use it to establish guarantees on the performance of strategies learned via self-play against new opponents. They show that any game can be projected into the space of constant-sum polymatrix games, which enables performance guarantees for the strategies produced by a broad class of self-play algorithms. The findings are empirically demonstrated on Leduc poker.", "questions": "- Can the authors pleaes explicitly list the assumptions/conditions needed for the theoretical results?\n- Can the structural property identified in this paper extends to other application domains (outside of multi-agent self-play)?", "limitations": "I don't see negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- I find the studied topic which extends the theoretical guarantees of self-play beyond two-player (constant-sum) games to be important to the multi-agent learning community.\n- The proposed method, by projecting a general game into the space of constant-sum polymatrix games, is novel and interesting.\n- The theoretical results are verified on 3-player Leduc poker", "weaknesses": "The technical sections of the paper is slightly hard to follow for a non-expert in this field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. \n\n### Response to Questions\n**Assumptions.** The main assumption we make is that self-play is performed by a no-regret learning algorithm. This means the average regret (the difference in utility between the chosen strategy and some hypothetical deviation) will get driven to 0 as the number of iterations increases. The set of deviations makes a difference on the type of resulting equilibrium, so we assume that the no-regret learning algorithms minimize external regret. This is a weak form of regret and almost every no-regret algorithm minimizes a stronger type of regret. We also assume that an agent learning via no-regret self-play will extract their strategy via marginalization in order to play it against new agents. \n\n**Extensions.** One of the fundamental problems in game theory is the equilibrium selection problem. Equilibria are fixed points where agents do not want to change their strategies; however if two agents found different equilibrium strategies (say, in self-play), then we do not generally know if the resulting joint selection of strategies is itself an equilibrium. This problem makes choosing a good strategy against new agents very hard. \n\nIn two-player constant-sum games, all equilibria are exchangeable, which means that a joint selection of equilibrium strategies is also an equilibrium. This solves the equilibrium selection problem for this class of games. Subgame stable CSP games also solve the equilibrium selection problem in n-player games, since equilibria of the whole game also are equilibria of the subgames, which are two-player constant-sum and hence exchangeable. This means equilibria of the whole game are also exchangeable. "}]

Author rebuttal:

Meta-review: The paper studies the structural properties of multiplayer games where self-play is guaranteed to perform well against opponents. The paper contains new ideas, is well-motivated, and well-written. It reaches a consensus that this is a good paper that should be accepted. Please make sure all the comments are addressed in preparing the final version.
Decision: Accept (poster)