Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Authors: Jiawei Ge
Yuanhao Wang
Wenzhe Li
Chi Jin
Venue: ICML 2025 poster (2025)
Keywords: Multiplayer symmetric games; Securing Equal Share
Primary area: theory->game_theory

Abstract: This paper examines multiplayer symmetric constant-sum games with more than two players in a competitive setting, such as Mahjong, Poker, and various board and video games. In contrast to two-player zero-sum games, equilibria in multiplayer games are neither unique nor non-exploitable, failing to provide meaningful guarantees when competing against opponents who play different equilibria or non-equilibrium strategies. This gives rise to a series of long-lasting fundamental questions in multiplayer games regarding suitable objectives, solution concepts, and principled algorithms. This paper takes an initial step towards addressing these challenges by focusing on the natural objective of *equal share*—securing an expected payoff of $C/n$ in an $n$-player symmetric game with a total payoff of $C$. We rigorously identify the theoretical conditions under which achieving an equal share is tractable and design a series of efficient algorithms, inspired by no-regret learning, that *provably* attain approximate equal share across various settings. Furthermore, we provide complementary lower bounds that justify the sharpness of our theoretical results. Our experimental results highlight worst-case scenarios where meta-algorithms from prior state-of-the-art systems for multiplayer games fail to secure an equal share, while our algorithm succeeds, demonstrating the effectiveness of our approach.

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Jiawei Ge 1 Yuanhao Wang" 2 Wenzhe Li
Chi Jin
Abstract
1. Introduction
In recent years, Al systems have achieved remarkable suc- in multi-agent decision-making problems, particularly in wide range of strategic games. These include, but are not limited to, Go (Silver et al., 2016), Mahjong (Li et al., 2020), Poker (Moravčík et al., 2017; Brown & Sand- holm, 2018; 2019), Starcraft (Vinyals et al., 2019). DOTA 2 (Berner et al., 2019), League of Legends (Ye et al., 2020), and Diplomacy (Gray al.. 2020; Bakhtin et al., 2022: FAIR). Many of these games are two-player zero-sum games', where Nash equilibria (NEs) always exist and can be computed in polynomial time. NEs in two-player zero- sum games are also non-explottable-an agent employing a NE strategy will not lose even when facing an adversarial opponent who seeks to exploit the agent's weaknesses. Al- though such equilibrium strategies do not necessarily capi- talize on opponents' weaknesses or guarantee large-margin victories, human players often adopt suboptimal strategies that deviate significantly from equilibria in complex games with large state spaces. Consequently, AI agents who adopt equilibrium strategies often outperform humans in practice for two-player zero-sum games.
This paper examines multiplayer symmetric constant-sum games with more than two play- ers in a competitive setting, such as Mahjong, Poker, and various board and video games. In contrast to two-player zero-sum games, equi- libria in multiplayer games are neither unique nor non-exploitable, failing to provide mean- ingful guarantees when competing against op- ponents who play different equilibria or non- equilibrium strategies. This gives rise to a series of long-lasting fundamental questions in multi- player games regarding suitable objectives, solu- tion concepts, and principled algorithms. This paper takes initial step towards addressing these challenges by focusing the natural ob- an expected
jective of equal payoff of C/n in an n-player symmetric game with a total payoff of C. We rigorously identify the theoretical conditions under which achiev- ing an equal share tractable and design a se- ries of efficient algorithms, inspired by no-regret learning, that provably attain approximate equal share across various settings. Furthermore, we provide complementary lower bounds that justify the sharpness of our theoretical results. Our ex- perimental results highlight worst-case scenarios where meta-algorithms from prior state-of-the- art systems for multiplayer games fail to secure equal share, while our algorithm succeeds, demonstrating the effectiveness of our approach.
In contrast, multiplayer games defined here as those with more than two exayers-exhibit fundamentally dif- ferent game structures compared to two-player zero-sum games. This distinction introduces several unique chal- lenges. Firstly, NEs are believed to be no longer com- putable polynomial time (Daskalakis et al., 2009; Chen & Deng, 2005). Moreover, there may exist multiple NEs with distinct values. Such non-uniqueness in equilibria raises a critical concern about the adoption of equilibrium strategies in multiplayer settings: if learning agent adopts equilibrium that is different from other players, collec- tively, they are not playing any single equilibrium, which undermines the equilibrium property that dissuades the agent from changing its strategy as long as others maintain theirs. Finally, in multiplayer games, equilibrium strate- gies are no longer non-exploitable and fail to provide mean- ingful guarantees when competing against opponents who
"gqual contribution 'Department of Operations Research and Financial Engineering, Princeton University 'Dppartment of Computer Science. Princeton University 'Department of Elec- trical and Computer Engineering, Princeton University. Cor- respondence to: Jiawei Ge =jg53300@pinnetonn.ce Chi Jin <chij @ priuccton.cduu>.
Games such as DOTA and League of Legends, despite in- volving two teams, can he mostly considered similar to two-player zero-sum games in terms of their game structures and solutions.
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

1. Regarding the question of solution concepts, we first Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
are not playing equilibria. Although the introduction of alternative equilibrium notions such (coarse) correlated equilibria alleviates computational hardness, issues of non- uniqueness and the lack of guarantees in the general set- tings remain. This leads to the first critical question:
demonstrate the insufficiency of classical equilibrium con- cepts and general self-play frameworks (learning from scratch) in achieving an equal share in symmetric games. We then proceed to identify the structural conditions where equal share is achievable. In contrast to two-player zero- sum games, we prove that in order to achieve an equal share in multiplayer games: (1) all opponents need to deploy the same strategy: (2) all opponents must have limited adap- tivity, and the learning agent has to model the opponents (See Section 4). We show that without either condition, an equal share can not be attained in the worst case. We prove that our identified conditions apply to practical multiplayer gaming platforms with a large player base. They are also tightly connected to the design of many prior modern mul- tiplayer AI agents.
What is the suitable solution concept for learning in multiplayer games?
Due to the presence of such fundamental challenge, even state-of-ther aar expert-level or superhuman AI systems for popular multiplayer games, including Mahjong (Li et al., 2020) (4 players), Poker (Brown & Sandholm, 2019) (6 players), and Diplomacy (Bakhtin et al., 2022; FAIR) (7 players), are designed with limited theoretical supports. These works focus on developing algorithmic frameworks capable of learning effective strategies that excel in lad- ders, online gaming platforms, tournaments against op- ponents. Generally, most of these systems rely on a basic self-play framework, starting from scratch or from oppo- nents' strategies acquired through behavior cloning, with or without regularization. While the success of these self-play algorithms is remarkable, their performance has been demonstrated primarily within the specific applica- tions they were designed for, often coupled with human expertise and extensive engineering efforts. It remains un- solu-
2. Regarding the question of principled algorithms, this paper illustrates how we can leverage existing tools from no-regret learning and no-dynamic-regret learning com- munities to achieve equal share with provable guarantees. Concretely, this paper considers several opponent settings: fixed, slowly adapting, and opponents that adapt at inter- mediate rates. For all cases, we design algorithms that ap- proximately achieve equal share, with an error tolerance of 1 L/poly(T), where T is the total number of games played. Additionally, we provide matching lower bounds, demon- strating that these guarantees cannot be significantly im- proved in the worst-case scenario.
clear whether these algorithms are general- tions that can be readily applied to multiplayer games be- yond Mahjong, Poker, or Diplomacy. This leads to the sec- ond important question:
3. We further complement our theory by experiments on two basic multiplayer symmetric games. Our experimen- tal results illustrate that (1) the self-play meta-algorithms from prior state-of-the-art systems for multiplayer games can fail to secure an equal share even under favorable set- tings, while our principled algorithm always succeeds; (2) prior meta-algorithm has no clear advantage over our al- gorithm on exploitability in the worst case. This indicates that prior self-play algorithms are not general-purpose and highlights the effectiveness of our theoretical framework.
What is the principled algorithm that provable learns a rich class of multiplayer games?
In this paper, we consider multiplayer symmetric constant- sum games, which are prevalent in games involving more than two players. Examples include previously discussed multiplayer games like Mahjong, Poker, and Diplomacy, as well as a variety of board games such as Avalon (Light et al., 2023), Mafia, and Catan.2 Symmetry brings fairness among players, providing a natural baseline where a learn- ing agent should at least secure an equal share - achiev- ing an expected payoff of C/n in an n-player symmetric game with a total payoff of C. This paper takes an ini- tial step toward addressing the two fundamental questions highlighted above by focusing on securing an equal share in multiplayer symmetric normal-form games?. The main contributions are summarized as follows:
1.1. Related work
AI gaming agents in practice. Building superhuman AI has long been goal in various games. A large body of works in this line focus on two-player or two-team zero- sum games like Chess (Campbell et al., 2002), Go (Silver et al., 2016). Heads-Up Texas Hold' em (Moravčík et al., 2017; Brown & Sandholm, 2018), Starcraft 2 (Vinyals et al., 2019), DOTA 2 (Berner et al., 2019) and League of Legends (Ye et al., 2020). Most of them are based on finding equilibria via self-play, fictitious play, league train- ing, etc. There is comparatively much less amount of work games with more than two players, whose game struc- tures are fundamentally different from two-player zero- sum games. Several remarkable multiplayer successes in-
All these examples are symmetric games up randomization of the seating.
"Extensive-Fone Form Games (EFGs) or Markov Games (MGs) can be viewed as special cases of normal-form games, where each action in normal-form games corresponds to strategy in EFGs or MGs, although such representations may not always he efficient.
2

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
clude Poker (Brown & Sandholm, 2019), Mahjong (Li al., 2020), Doudizhu (Zha et al., 2021) and Diplo- macy (Bakhtin et al., 2022: FAIR). Despite lacking a clearly formulated learning objective, these works typically design meta-algorithms, which include initially training the model using behavior cloning from opponents, then en- hancing it through self-play, and finally applying adapta- tions based on the game's specific structure or human ex- pertise. It remains elusive whether such recipe is gener- ally effective for wide range of multiplayer games.
distribution over A For a function f A R, we denote II = A [f(a].. We use [n] to denote the set m2,. In this paper, we use C' to denote universal constants, which may vary from line to line.
2.1. Normal-form games and equilibrium
Normal-form game. An n-player normal-form game con- sists of finite set of players, where each player has an action space A, and a corresponding payoff function U, : A1 X ... x An + [-1, 1] with Us(ai...... an) denotes the payoff received by the i-th player a play- ers are taking joint actions (aI....,,n) game as constant-sum if there exists constant C such that _i Li-l Ui ................................ an)) = C' for all joint actions. We further denote a game as zero-sume surr--sumii if it is a constant-sum game with total payoff of C = O. Normal-form games can represent a wide range of games as their special cases, including se- quential games such as extensive
Existing results for symmetric games. Von Neumann & Morgenstern (1947) gave the first definition of sym- metric games and used the three-player majority-vote ex- ample to showcase the stark difference between symmer- ric three-player zero-sum games and symmetric two-player zero-sum games. In his seminal paper that introduced Nash equilibrium (NE), Nash proved that a symmetric fi- nite multi-player game must have symmetric NE (Nash, 1951). However, this existence result holds little signifi- cance from an individual standpoint, as there is no reason a priori to assume that other players are indeed playing ac- cording to this symmetric equilibrium. Papadimitriou & Roughgarden (2005) studied the computational complexity of finding the NE in symmetric multi-player games when the number of actions available is much smaller than the number of players and gave a polynomial-time algorithm for the problem. In this case, symmetry greatly reduced the computational complexity (as computing Nash in general is PPAD-hard). Daskalakis (2009) proposed anonymous games, a generalization of symmetric games.
We define a
n
or Markov games. Due to space limit, we refer readers to Appendix A for more details of basic concepts in normal-form games, in- cluding formal definitions of strategy, learning protocol, and best response.
Equilibrium. Nash Equilibrium (NE) is the most commonly used solution concept for games: a mixed strat- egy x E A(A1 x ..... x A,,) of all players is said to be NE if is a product distribution 4, and no player could gain by deviating from her own strategy while holding all other players' strategies fixed. That is, for all i E [n|] and of E A., Eu, (a; a-;)] 2 Eu a-;)]
There are also two equilibrium notions relaxing the notion of NE by no longer requiring æ to be a product distribution. It allows general joint distribution x which describes corre- lated strategies among players. In particular, (1) is Cor- related Equilibrium (CE) if for all E [m]] and a' E Ai, Egs [U, a-:) a;] > "U,=((U((a; ami) a.]. and (2)
No-regret learning. There is rich literature on applying no-regret learning algorithms to learning equilibria. It is well-known that if all agents have no regret, the resulting empirical average would be an approximate Coarse Corre- lated Equilibrium (CCE) (Young, 2004), while if all agents have no swap-regret, the resulting empirical average would be an c-Correlated Equilibrium (CH) (Hart& & Mas-Colell, 2000; Basa-Bianchi&& & Lugosi, 2006). Later work continu- ing this line of research includes those with faster conver- gence rates (Syrgkanis et al., 2015; Chen & Peng, 2020; Daskalakis et al., 2021), last-iterate convergence guaran- tees (Daskalakis & Panageas, 2018; Wei et al., 2020), and extension to extensive-form games (Celli et al., 2020; Bai al., 2022b;a; Song et al., 2022) and Markov games (Song et al., 2021; Jin et al., 2021).
is Coarse Correlated Equilibrium (CCE) if for all i E [n] and of E A;: Ea-z The major difference between those two notions is in the cases when the agent deviates from her current strategy, whether she is still allowed to observe the randomness in drawing actions from the correlated strategy. The relation- ship among various equilibrium concepts is encapsulated by NE C CE C CCE.
> Ea-z UU a)))
Two-player zero-sum games. In two-player zero-sum games, all Nash equilibria share the unique payoff value 0. Furthermore, a Nash equilibrium is non-exploitable against any strategy that is not necessarily an equilibrium. In math, if (n² (²* is the Nash equilibrium, we have min, Ui("", max, min, (i v) = 0.
2. Preliminaries
Notation. For any set A, its cardinality is represented by [A]. and (AA) denotes a probability distribution over AA We employ A to denote the Cartesian product of in- stances of A. Given a distribution x over A, r0"n represents the joint distribution of independent copies of x, forming
Multiplayer/generalssuu games. When there are more
*Randomness in different players' strategics are independent.
3

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
than two players, or games are no longer constant-sum games, NEs become PPAD-hard compute (Daskalakis et al., 2009) while CEs and CCEs can be still computed in polynomial time. All of these three concepts admit mul- tiple equilibria with distinct payoffs. Furthermore, they no longer own strong guarantees, such as non-exploitness, when competing against non non-equilibrium players.
istence of multiple NEs creates a predicament for the learn- ing agent. It must choose which equilibrium follow, yet there is always the risk that the two opponents are both playing the other NE, leading to a negative payoff for the learner. In other words, adhering to a single NE does not reliably ensure an equal share when multiple equilibria ex- ist. Since NE c CE C CCE, we know the same limitation also holds for CE and CCE.
2.2. Symmetric games and equal share
Insufficiency of self-play from scratch. Self-play is training method in which the learning agent improves its performance by repeatedly playing against copies of itself without human supervision. See pseudo-code in Algorithm 1. The learner maintains its own strategy {2e) At the h iteration, the learner first pretends that all opponents are employing its current strategy 3t, and samples actions from them. Then the leamer updates its own strategy 2++1 ing the gradient information from the gameplay. The up- dates can be made using any optimizer such as gradient descent or Hedge.
Symmetric games. For an n-player normal-form game with an action space {A: and a payoff {U-)=z we say the game is symmetrie if (1) A, = A, for all i [n]; (2) for any permutation a: [m] - [n]] we have Ui(",,"" an) = Uo
In short, the payoff's of symmetric game for employing a specific action are determined solely by the actions used by others, agnostic of the identities of the players using them. Thus, the payoff function of the first player denoted as U,, sufficient encapsulate the entire game.
Here, we argue that self-play from scratch (the algorithm adopted in (Brown & Sandholm, 2019)) again fails to se- cure an equal share in the same three-player majority vote game: Consider two opponents play the same fixed strat- egy that is one of the NEs. In this case, the learner has no choice but to play the exact same NE as the opponents to secure an equal share. That is, if the learner's 's algorithm is agnostic to the strategies of the opponents, it is doomed to fail. We note that while recent systems (Li et al., 2020; Ja- cob et al., 2022) combine self-play with behavior cloning which is no longer agnostic to opponents' strategies, our experiment shows that their meta-algorithms remain insuf- ficient to secure an equal share in the worst-case scenario (See Section 6).
Symmetric games are popular in practice as they bring fair- ness among players. Technically, all asymmetric can be converted to symmetric games by randomizing the roles of the players at the beginning of the game. Nevertheless, casting the games in the symmetric form gives a natural and minimal baseline - the learning agent should attain an equal share in the long run.
Equal share. We say agent attains equal share, if its average payoff of the games is at least C/n for n-player symmetric constant-sum game with a total payoff of C.
is not hard to see that shifting the total payoff of game by any absolute constant will not alter the strategic aspects of the game. Therefore, without loss of generality, this pa- per sets total payoff of C 0 and focuses on achieving equal share in multiplayer symmetric zero-sum games.
4. Sufficient Conditions for Securing Equal Share
3. Insufficiency of Equilibria and Self-play for Equal Share
Here we further identify structural conditions of the games where equal share is achievable. We will show that the following two conditions are needed to achieve equal share:
In this section, we demonstrate that existing equilibria no- tions and the self-play from scratch algorithm are insuffi- cient to secure equal shares in multiplayer symmetric zero- sum games even under very basic settings. To show this, we consider the following 3-player majority vote game:
Condition 1. egy, i.c., I2 = .... Zn
All opponents need to deploy the same strat-
Condition 2.
All opponents must have limited adaptivity and the player has to model the opponents, i.e., { can not adversarially change across different rounds of the game.
Example 1 (Three-player majority vote game). Every player chooses either 0 1. If all players take the same action, then they receive payoff 0. Otherwise, being in the majority yields a positive payoff of 1/2. while being in the minority results in a negative payoff of -1.
We justify these two conditions by proving that without ei- ther condition, an equal share can not be attained in multi- player symmetric games in the worst case. We remark that both conditions restrict the strategies of opponents rather
Insufficiency of equilibria. In this setup, both pure strate- gies 00,0,0) and (1, 1, constitute NE. However, the ex-
4

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
than the type of games.
remark that this solution concept does not necessarily cor- respond to any equilibrium in most multipaaeer games. We conclude with this solution concept from principled man- ner with equal share as our primary objective. For con- ciseness, from now on, we will also refer to the common strategy employed by all opponents as the meta-strategy.
Non-adaptive opponents that deploy different strate- gies. We start by considering the case where Condition 2 holds but Condition 1 does not hold.
Proposition 4.1. There exist symmetric zero-sum games with opponents using fixed but differing strategies, such that no learner's strategy secures an equal share. In math,
4.1. Connections between identified conditions and practice
max min U1(11,... ,In)
While the two identified conditions may seem restrictive, here we argue that they in fact apply to practical multi- player gaming platforms with a large player base. Con- dition 1 is further implicitly adopted by most prior state-of- the-art AI agents for multiplayer games.
min max U1 1 In) 0O 21
(1)
where both inequalities can be strict in certain games.
Here, further strengthen the proposition to require opponents to deploy strategies without "collusion". That is, the hard instance holds even when the strategies em- ployed by opponents are statistically independent without any shared randomness. Proposition 4.1 highlights the challenge when opponents can adopt different strategies.
Connection to multiplayer games with large player base We argue that both identified conditions are well- justified in modern multiplayer gaming platforms with a large player base. Imagine casino hosting N players who randomly join poker tables or an online Mahjong match- making platform with N users. Let { be the strategy set for these N players. We can then define the popula- rion meta-strategy as I = (1/N) Σ 2;. The following proposition claims that, for n-player symmetric zero-sum games, in terms of the expected payoff, playing against n 1 random players is almost the same as playing against n players who all adopt the same population meta- strategy 5. as long N (n 2)
Adaptive opponents that deploy identical strategy. We next examine the case where Condition 1 holds but Condi- tion 2 does not hold.
Proposition 4.2. There exist symmetric zero-sum games such that no learner's strategy secures an equal share against adversarial opponents, even under the constraint they adhere to identical strategy at each round. In math,
>
max min U1 (x1, sn-1 21 S Smn U1 x xn-1))- = 0, (I1,
Proposition 4.3. Let E.,,, be the expectation over the ran- domness on sampling n 1 strategies uniformly from the J.N without replacement. Then for any strategy set {2, Ji=1
E (AA), we have [B._, (11,, U1 (2, (mm-))
where the inequality can be strict certain games.
2(n - 2)²
Proposition 4.2 implics property that makes multiplayer games significantly different from two-player zero-sum games: even under the favorable scenario of all opponents employing identical strategies, one can no longer find a fixed "non-exploitable" strategy agnostic to the strategies of opponents. All strategies are exploitable. Opponent modeling is necessary to secure equal share.
Furthermore, it is often safe to assume that the population meta-strategy I - the average strategy of all players within the player pool - will not quickly adapt to one particular player's 's strategy.
Connection to practical AI systems. We remark that a majority of practical AI systems for multiplayer games (Li et al., 2020; Brown & Sandholm, 2019; Bakhtin et al., 2022; FAIR) leverage self-play meta-alge aeta-algorithms (Algo- rithm 1), which equate the strategies of all opponents with those of the learner. This implicitly assumes all opponents employ an identical strategy at every round.
Solution concepts beyond equilibrium. Combining Proposition 4.1 and Proposition 4.2, we observe that both conditions mentioned at the beginning of Section 4 are needed to make equal share achievable. In math, we con- clude from (1) and (2) that, out of the four related minimax concepts, only ming max,, 211,1,00=1) 00 = 0 across all multiplayer symmetric zero-sum games, which guarantees an equal share. This remaining minimax con- cept precisely corresponds to the two identified condi- tions where opponents employ identical strategies, and the leamner must be adaptive to the opponents. Therefore, we will use min, max,, U1 (I1, 2"=1) as our target solu- tion concept for this paper to achieve equal share. We
5. Provably Efficient Algorithms
In this section, we explore efficient algorithms that prov- ably secure an cqual share under the two conditions iden- tified in Section 4. Particularly, we consider several oppo- nent settings with various adaptivity: fixed, slowly adapt- ing, and opponents that adapt at intermediate rates.
5

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
We use the following notations throughout this section: at round i, let denote the learner's ' strategy, and y' the meta- strategy employed by all opponents, We denote w' as the expected payoff function of the learner at round t, where (.))) == (1, (g')@n=1). Then the average payoff of the learner is: Mavg (T) = S/ w' (x').
equal share is impossible if opponents can change their meta-strategy s arbitrarily fast across different rounds. Thus we introduce constraint on the adaptive power of the opponents by positing a variation budget Vr, which bounds the total variation of the payoff function across the time horizon. Specifically, we assume the payoff function belongs to U, which is defined as
5.1. Fixed opponents
U = {(u') EL |utt1 1--t--ull u'll I VrJ.
(3)
We begin by exploring the simple stationary scenario, where the meta-strategy used by the opponents remains constant over time, denoted as y" = y for all t E [7].
Furthermore, we denote ((n, A, VT) as the set of tuples, which consists of n-player symmetric zero-sum game with A actions and a corresponding meta-strategy sequence { such that the payoff function {u')/= E U. This constraint effectively moderates the adaptivity of the oppo- nents compared to a fully adversarial setup.
Notably, in this particular scenario, the payoff function (')) remains constant over time. Additionally, by sym- metry, is not hard to observe that at least one action will consistently yield an expected payoff of 0 in all rounds. This implies max Ei= (a) 2 0, which makes the no-regret learning tool well-poised to achieve equal share in this setting. Standard (static) regret, defined as fol- lows, compares the learner's total payoff to the total payoff achieved by the best action in hindsight:
Slowly adapting opponents. In non-stationary environ- ments, the total payoff' achieved by the best action in hindsight max Σi= u (a) is no longer non-negative Therefore, minimizing standard regret in this setting is no longer effective in securing an equal share. This motivates us to turn our attention to a stronger notion of regret- dynamic regret, defined as:
Reg(T)= == a Et (()a (TT EIz u'(x',,
An algorithm has no-regret if Reg(T)= S o(T) for all large T. We deploy a standard no-regret learning algorithm Hedge (Freund & Schapire, 1997), which provides the fol- lowing guarantees:
D- D-Reg(T)= = EI= max - -t= (xt).
This measures a strategy's performance against the best ac- tion at each time step (dynamic oracle), providing a more relevant benchmark in changing environments.
Theorem 5.1 (Stationary opponents). Let {2r)T= be the strategy sequence implemented by the Hedge algo- rithm against stationary opponents. Then, with prob- ability at least 8, have Mave(T) 2 u² C. (Voo((A/5)/ for some absolute constant C, where u* A (a.yaan.)))
In the setting of symmetric games, the dynamic ora- cle is always assured to secure an equal share, i.e., Σ max.g (a)) 2 O. Thus, any algorithm achieving no-dynamic-regret is guaranteed to achieve an equal share up to a small error. To this ends, we adapt a no-dynamic- regret Aggorthm--Strongee Adaptive Online Learner with Hedge H as black box algorithm (SAOL (See Ap- pendix C.1.2), proposed by (Daniely et al., 2015) to setting and achieve following guarantees:
The probability is taken over the random actions by op- ponents sampled from the meta-strategy". Theorem 5.1 claims that with stationary opponents, the Hedge algorithm approximately achieves an equal share up to a ((1/VT) error, which demonstrates its effectiveness in the long run.
Theorem 5.2. Suppose that 2 3. A 2 2, and Vr
[1 T. then for any game and any meta-strategy sequence in (mn A, Vr), with probability at least 1 - 8, SAOL H satisfies
5.2. Adaptive opponents
In practical scenarios, encountering a fixed opponent strat- egy is relatively uncommon. More often, opponents adapt and modify their strategies over time, responding to the game's dynamics and the actions of other players. Thus, in this section, we shift our focus to the non-stationary sce- nario, where the meta-strategy y² adopted by the opponents varies over time.
- -CVV//3T-13 (VIog(A/0) + +log log?)
Mave 2
for some absolute constant C. where u! (1/T) Et max.5A u u'(a) 2 O.
Theorem 5.2 implies that SAOL* H achieves nen-negative average payoff, up to an error term that scales with Therefore, if V/ is sublinear in T. SAOL* H is capable of approximately achieving equal share over an extended duration.
According to Proposition 4.2, it is clear that attaining an
Ö(v//31-1/3
RRcall that our learning protocol in Section 2 assumes the learner only observes the noisy actions of the other players at each round.
6

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Opponents that adapt at intermediate rates. Interest- ingly, there is an intermediate regime where opponents" strategies {v' J are changing neither too fast nor too slow where the favorable algorithm for the leamer might be behavior cloning-simply mimic opponents' strategies.
6. Experiments
In this section, we focus on the scenario where one learning agent competes against n- opponents who play the iden- tical meta-strategy. For simplicity, we restrict ourselves to the setting of fixed opponents. We aim to answer: (Q1) Can existing algorithmic frameworks in previous superhuman Al systems consistently secure an equal share under this favorable setting? If not, what are the failure cases? (Q2) Are these trained agents exploitable by adversarial oppo- nents? We design the following two games to compare our algorithm with prior self-play-basee algorithms.
Formally, we define the behavior cloning algorithm for the leamer by making her action in t-th round the same as the action taken by the 2nd player in (t 1)-th round (See Algorithm 2). Behavior cloning achieves the following:
Theorem 5.3. Suppose that 2 3. A 2 2, and VT E [1, for any game and any meta-strategy se- quence in (n, A, Vr), behavior cloning guarantees thut B [T)) 2 - -VV + 1)/T.
Majority Vote (MV). We first consider the standard 3- player majority vote game (Example 1). Here [1.0]. [0, 1]. and [1/2, 1/2] are all NEs, where [p, 1 p] denotes the mixture strategy that takes the first action with probability and the second action with probability 1 1- p. We fix the opponent meta-strategy Ymeta [0.49, 0.51] for all rounds.
We remark that while the error term (V in Theorem 5.3 is always smaller than the error term ((VVT (/3) in Theorem 5.2, the latter is comparing to the baseline of dy- namic oracle w!, which has a greater value than the base- line in behavior cloning - 0. It is not hard to see that in the intermediate regime @(ut) S Vr I @(),, the meta-strategy is changing too fast so that it is better for the learner to simply copy the meta-strategy instead of run- ning sophisticated no-dynamic-regret algorithm to learn the game and to counter the meta- stratey by herself.
Switch Dominance Game (SDG). In each round, players simultancously choose an action from set {A, B, CJ. Let n be the total number of players and n' be the number of agents choosing action A, We define the game rule as:
B> A> if > 0.2n, C otherwise,
Matching lower bounds. Finally, we also complement our upper bounds by matching lower bounds showing that SAOL Ht and behavior cloning are already the near-optimal algorithms in terms of error rates when compared with the corresponding baselines - the dynamic oracle and zero payoff respectively. The techniques used here are based adapting existing hard instances for more general setup to the symmetric zero-sum game setting. Please see more discussion in Appendix C.2.
where the rule j k intuitively means that action i dominates both j and k, and action dominates k. SDG is designed so that C' is dominated action when there is a reasonable number of players taking action A, but a dominating action otherwise. Concretely, for > j > k, we assign the following payoff (ra, rj, rk) to players taking actions ji. k) respectively, where:
r. In, n > 0].
r3 = 1| > 0] 1|n, - n > 0] na/(nn + +nk),
Theorem 5,4. There exists some absolute constant C > O such that for any n 2 3, A 2 2, and VT E [1, T), and any learning algorithm, there exists a game and a meta- strategy sequence in A(n, A, VT), such that Er (T)] <
F = L[n, + nu > 0] 1l..:///, + n4)) 1[ > 0] - n2 ny/nk..
This payoff design guarantees that SDG is a symmetric zero-sum game. Here we set n = 30 and pick the fixed meta-strategy of the opponents ymmeta = [0.399, 0.6, 0.001] (in the order of action A, B3, C.) for all rounds. Note that while this game has an NE strategy [0, 1J, its utility is negative against our chosen meta-strategy Ymeta-
ut - -CV//3T
Theorem 5.5. There exists some absolute constant C > O such that for any n 2 3, A 2 2, and Vr E [I,T], and any learning algorithm, there exists a game and a meta- strategy sequence in G(n, Vr) such that E (Mave(T) < -CVr/T.
6.1. Learning algorithms
To better focus on the key game-theoretic property of the algorithms, we idealize the process of imitation learning by assuming that the learning agent has already learned (i.c., has direct access to) the meta-strategy Fmeta by the opponents. In this setting, according to Theorem 5.1, our thcoretical framework suggests to directly run the Hedge algorithm (Hedge) against opponents who play the meta-
The expectation in both theorems are taking over the ran- dom actions by the opponents as well as the possible in- trinsic randomness in a stochastic algorithm. Theorem 5.4 and 5.5 match Theorem 5.2 and 5.3 respectively, up to ad- ditional logarithmic factors.
7

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Table 1. The distribution of mixed strategies to which different self-play algorithms converge in MV. We use SP_BC P.B.C.A as the short name of PP_CCrre with regularization coefficients X.
Strategy
SP.scratch
SP_BC
SP SP.BC.10'*
SP_BC.10"
SP.BC.10
SP_BC.10
Hedge
[1.0]
52%
48%
50%
46%
42%
42%
0%
[0.1
48%
52%
50%
54%
58%
58%
100%
Table 2. The utility and exploitability of cach algorithm. Particularly, for MV, as self-play algorithms converge to two different solutions with roughly equal probability, we evaluate the utility of the worse converged solution of the two to reflect the worst-case performance.
MV
SP scratch / SP BC / SP rC.reg
Hedge
SDG
SP SP_scratch / SPLBC/ SP SP_BC.reg
Hedge
Utility (x10-3)
-1.00 0.09
1.03 0.10
Utility
-12.67 1 0.01
1.00 1 0.00
Exploitability
-1.00 0.00
-1.00 + 0.00
Exploitability
-29.00 + 0.00
-29.00 + 0.00
strategy. We compare our algorithm against three meta- algorithms adopted by prior state-of-the-art AI systems in practice: (1) self-play from scratch (SP scratch) (Brown & Sandholm, 2019); (2) self-play initialized from behav- ior cloning (SP BC) (Li al., 2020), and (3) self-play ini- tialized from behavior cloning with regularization towards the meta-strategy (SP.BCA reg) (Jacob et al., 2022). While these Al systems further implement multi-step lookahead with a few additional techniques, many of them only ap- ply to sequential games, not the basic normal-form games. Here, we focus on the comparison of the high-level game- theoretic meta-algorithms.
We report that while our Hedge algorithm converges to the strategy [0, 1,0 all self-play variants consistently converge to the strategy [0, 0, 1].
SDG:
Utility and Exploitability. We summarize the results in Table 2, which show that even in these two simple sym- metric zero-sum games, none of the self-play algorithms can consistently secure non-negative payoff, i.e. an equal share, in the worst case. This undesirable behavior persists even without opponents making any adaptations! More- over, based on these two games, we further conclude two potential failure modes of self-play algorithmss (1) For games with multiple NEs, such as MV, self-play methods may converge different NEs based on different initial- ization. When the opponents' meta-strategy (i.e., the initial strategy for SP_BC PPBC) lies close to the boundary of the con- vergence basins of two different NEs, self-play algorithms will have a non-zero probability of converging to both of them due to the statistical randomness in the game. It is likely one of the two NEs undesirable against the meta- strategy ymmeta (2) For games with single NE, self-play algorithms are still very likely to be attracted to this equi- librium. A carefully designed game structure can result in this NE yielding negative utility against the chosen meta- strategy, and hence jailbreak all self-play variants. The aforemmnnioned failure modes highlight a significant lim- itation of self-play variants when being applied to diverse and complex multiplayer games. In contrast, the princi- pled algorithm according to our theory consistently beats the meta-strategy of the opponents, receives much higher payoff, and secures an equal share. Regarding exploitabil- ity, all learned strategies can be easily exploited by adver- sarial opponents.
Algorithm details. We also use the Hedge algorithm as the optimizer for the self-play algorithm to update its strategy. We choose the learning rate for the Hedge algorithm based on theoretically optimal value and choose the regulariza- tion parameter according to (Jacob et al., 2022). We refer readers to Appendix for more details.
6.2. Results
To answer Q1 and Q2, we evaluate the utility of the learned strategy å against the pre-specified meta-strategy ymetu i.c., U1 (ft, (iin-1)) as well as the exploitability of the learner 4. i.e., miny U () To measure the utility, we evaluate the payoff of the agent's converged strategy by Monte Carlo methods with 3 x 10y games and report the mean and standard deviation of 10 runs. As for the ex- ploitability, pick the best exploiter strategy within 100 runs, and report the payoff of the learner against that exploiter.
Convergence analysis. We first check the convergence for each algorithm in both games:
MV: Table I reports the limiting solution each algorithm converges to within 100 runs. Our algorithm (Hedge) con- sistently converges to the good strategy [o, 1]. All self-play variants have significant probability converge the bad strategy [1, OJ. which has a negative utility against the cho- sen meta-strategy Vmera= = [0.49, 0.51].
7. Conclusion
Unlike in the two-player zero-sum games, standard equi- libria are no longer always the suitable solution concept for multiplayer games. They are non-unique and lack mean- ingful guarantees in general scenarios. This paper estab-
8

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
lishes new theoretical framework that provides the solu- tion concepts and the principled algorithms for multiplayer games from the unique angle of achieving equal share. We hope our results serve as the first step toward further research on principled methodologies and algorithms for multiplayer games.
Celli, A., Marchesi, A., Farina, G., and Gatti, N. No-regret learning dynamics for extensive-form correlated equilib- rium. Advances in Neural Information Processing Sys- tems, 33:7722-7732. 2020.
N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Acknowledgement
Chen, X. and Deng, X. 3-nash is ppad-complete. In Elec- tronic Colloquium on Computational Complexity, vol- ume 134, pp. 2-29. Citeseer, 2005.
The authors would like to thank Haifeng Xu for the help- ful discussions. This work is supported by Office of Naval Research N00014-22-1-2253.
Chen, X. and Peng, B. Hedging in games: Faster conver- gence of external and swap regrets. Advances in Neu- ral Information Processing Systems, 33:18990-18999, 2020.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Daniely, A., Gonen, A., and Shalev-Shwartz, S. Strongly adaptive online learning. In International Conference on Machine Learning, pp. 1405-1411. PMLR, 2015.
References
Daskalakis, C. Nash equilibria: Complexity, symmetries, and approximation. Computer Science Review, 3(2)877- 100, 2009.
Bai, Y. Jin, C.. Mei, S., Song, Z., and Yu, T. Efficient Ø-regret minimization in extensive-form games via on- line mirror descent. arXiv preprint arXiv:2205.15294. 2022a.
Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. arXiv preprint arXiv: 04252, 2018
Bai, Jin, C., Mei, S., and Yu, T. Near-optimal learning of extensive-form games with imperfect information. arXiv preprint ar Xihv:2202.0/752. 2022b.
Daskalakis, C., Goldberg, W., and Papadimitriou, C. H.
The complexity computing a nash equilibrium. SIAM Journal on Computing, 39(1):195-255 2009.
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.05499, 2022.
Daskalakis, C., Fishelson, M., and Golowich, N. Near- optimal no-regret learning general games. Advances in Neural Information Processing Systems, 34:27604- 27616, 2021.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q.. Hashme, S., Hesse, C., et al. Dota with large scale deep reinforce- ment learning, arXiv preprint arXiv:1912.06668 2019.
(FAIR)+. M. R. Bakhtin, A., Brown, N., Dinan, E., Farina, G., Flaherty, C., Fried, D., Goff, A., Gray, J., Hu, H., et al. Human-level play in the game of diplomacy by combining language models with strategic reasoning. Science, 378(6624); 1067-10044 2022.
Besbes, O., Gur, Y., and Zeevi, A. Stochastic multi-armed- bandit problem with non-stationary rewards. Advances in neural information processing systems, 27, 2014.
Freund, Y. and Schapire, R. E. A decision-theoretic gener- alization of on-line learning and an application to boost- ing. Journal of computer and syslem sciences, 55(1): 119-139, 1997.
Brown, N. and Sandholm, T. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Sci- ence, 359(6374):418 424, 2018.
Gray, J., Lerer, A.. Bakhtin, A., and Brown, N. Human- level performance in no-press diplomacy via equilibrium search. arXiv preprint arXiv:2010.0225 02923, 2020.
Brown, N. and Sandholm, T. Superhuman ai for multi- player poker. Science, 365(6456):885-89)) 2019.
Hart, S. and MoleC,,ell, A. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5): 1127-1150, 2000.
Campbell, M., Hoane Jr, A. J., and Hsu, F.hh. Deep blue. Artificial intelligence, 134(1-2))57-83, 2002.

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Jacob, A. P., Wu, D. J., Farina, G., Lerer, A., Hu, H., Bakhtin, A., Andreas, J., and Brown, N. Modeling strong and human-like gameplay with kl-regularized search. In International Conference on Machine Learning, pp. 9695-9728. PMLR, 2022.
Von Neumann, and Morgenstern, O. Theory of games and economic behavior, 2nd rev. 1947.
Wei, C.-Y., Lee, C.-W., Zhang, M., and Luo, H. Linear last-iterate convergence in constrained saddle-point op- timization. arXiv preprint arXiv:2006.0955: 2020.
Jin, C., Liu, Q.. Wang, Y., and Yu, T. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2) 10. 14.555,, 2021.
Ye, D., Chen, G., Zhang, W., Chen, S., Yuan, B., Liu, B., Chen, J., Liu, Z., Qiu, F., Yu, H., et al. Towards play- ing full moba games with deep reinforcement learning. Advances in Neural Information Processing Systems, 33: 621-6322 2020.
Li, J., Koyamada, S., Ye, Q., Liu, G., Wang. C., Yang, R., Zhao, L.,, Qin, T., Liu, T.-Y., and Hon, H.-W. Suphx: Mastering mahjong with deep reinforcement learning. arXiv preprint arXiv:2003. 13590, 2020.
Young, H. P. Strategic Learning and its Limits. Oxford University Press, 2004. ISBN 9780199269181.
Light, J., Cai, M., Shen, S., and Hu, Z. Avalonbench: Eval- uating Ilms playing the game of avalon. In NeurIPS 2023 Foundation Models for Decision Making Work- shop, 2023.
Zha, D., Xie, J., Ma, W., Zhang, S., Lian, X., Hu, X., and
Liu, J. Douzero: Mastering doudizhu with self-play deep reinforcement learning. In international conference on machine learning, pp. 12333-12344 PMLR, 2021.
Moravčík, M., Schmid, M., Burch, N., Lisy, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M. Deepstack: Expert-level artificial intelli- gence in heads-up no-limit poker. Science, 356(6337): 508-5 513, 2017.
Nash, J. Non-cooperative games, Annals of mathematics, pp. 286-295, 1951.
Papadimitriou, C. H. and Roughgarden, T. Computing equilibria multi-player games. SODA, volume 5, pp. 82-91. Citeseer, 2005.
Silver, D., Huang, A., Maddison, 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 search. nature, (29()587):488) 489, 2016.
Song. Z., Mei, S., and Bai, Y. When can we learn general- sum markov games with a large number of players sample-efficiently? arXiv preprint 18.444110.0 2021.
Song. Z., Mei, S., and Bai, Y. Sample-efficient learning of correlated equilibria in extensive- games. arXiv preprint XxX::22005007223 2022.
Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. Ad- vances in Neural Information Processing Systems, 28, 2015.
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R. Ewalds, T., Georgiev, P., et al. Grandmaster level star- craft ii using multi-agent reinforcement learning. Nature, 575(7782)3350-33 354, 2019.
10

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
A. Extended Preliminaries
A.1. Basic concepts
Strategy (mixed) strategy of a player is a probability distribution over the player's actions. For E [n], we use a, A and I; E ((A) denote an action and mixed strategy of the i-th player respectively. We use a-i A and x-1 A(A3n-1) denote the actions and the mixed strategies of the other players. We denote U1(29,
Bap=zaa---r.. (Ui(as,a-:))
Learning protocol We assume that the learner knows the game rule, and thus her own payoff function U1. At every round t, all players take action simultaneously. and the learner only observes the opponents' noisy actions (a ag. ................. an) that are sampled from their strategies.
Best response Given a mixed strategy -- of the other n - players, the best response set (R.(x-;) of the i-th player defined as (x-+) == arg max,,eA, U,(,,
A.2. No-regret learning
No-regret learning is commonly adopted strategy in game theory to find equilibrium solutions. We consider a T-step learning procedure, where for each round E [T]: (1) the agent picks a mixed strategy μ² over A. (2) the environment picks an adversarial loss l E [0, 1]l-I. The expected utility for 1-th round is defined as - (2). To measure the performance of particular algorithm, common approach is consider regret, where the algorithm's 's performance compared against the single best action in hindsight, Specifically, for policy sequence (n²,...,,/t taken by an algorithm, the static regret is given, by
T Reg (T) E(ut e)) 1=1
T
min Σ l(a).
aEA
1=1
We say that the algorithm is a no-regret algorithm if (T) o(T). One of such no-regret learning algorithms is Hedge algorithm, which performs the following exponential weight updates:
p (a) pa(ae (aaa)-mnii)) ud((a) for Va A.
where 7) is the learning rate. See Algorithm 5 for the Hedge algorithm as applied to our problem setup.
A.3. 3-player majority and minority game
In this section, we give formal definition of the 3-player majority and minority game.
We define the 3-player majority game as a symmetric zero-sum game with action space A = {0, 1} and the payoff function given by:
U1(0,0,0) (1(1,,,
(, = 1), = U1 ((. 1/2
(0, 1, = U,(1,0,0) = -1
In other words, players receive a positive payoff if they are part of the majority and negative payoff if they are in the minority. Correspondingly, we define the 3-player minority game as symmetric zero-sum game with action space A = (0, 1) and the payoff function given by:
(1,0,0,0) = (1,
(,,0,1,0) -1000000000000011000000010010000 =
(0, = (,) =.
In other words, players receive a positive payoff if they are part of the minority and a negative payoff they are in the majority.

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
B. Proofs for Section 4
In the sequel, we will prove Proposition 4.1 Section B.I, Proposition 4.2 Section B.2 and Propostion 4.3 Section B.3.
B.1. Proof Proposition 4.1
In this section, we will prove (1), where both inequalities can made strict in certain games.
Proof of Proposition 4.1. For the first incquality, note that for any (21,...,Ix))
U1 (11, ,nd s max U1(11 (01, ;n))
21
which implics
min (1(21, ... ,n) S min max (1(11 In).
ag. an 21
By further taking maximum over xı E A(A), we prove that
max min (1 ... ,,) < min max U1 (21, ... (..)
To show the first inequality can be strict, consider the 3-player majority vote. Suppose 3 players adopt the mixed strategies (a1,1 - an), (02, 1 - a2) and (az, - 03), respectively. It then holds that
(1, = U1(a1, 022 az)
=0 -(1 - (1) ax3) + zaz(1 0z) + 2 200(1 - 02)
1
2
+ (1- (-0203 + 20 -az) + 2 _as(1 - (12))
1
By choosing 02 = 03 = 0 when on > 1/2 and 02 = 03 = when 0 S 1/2, it can be seen that
1
max min U1(01, 03) < max (11 a1) - an 02,0g
an
Note that
min max 02, 02.0g on
= min max 2((1 - a2) - az) + 02 az) + as((1 az),
02.0g
-20203 + a2(1 a3) + a3(1 - a2))
min max maxx33(22 a3) - 40203 2, 02 + a3 44223) 02.03 = 0.
Thus, we show that max,, min (1(1,,02 023) < milngag max,, can be strict.
which implies the first inequality
For the second inequality, due to restriction the minimization constraints, it is straightforward that
min (1 .xn) S min max U1 (21, 22
21
In the sequel, we prove miny max,, Un (1 x 1n1 = 0 via contradiction. Note that by choosing #1 = x, we can show that
min max U, (x) xn 0.
21
12

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Suppose for some game inequality holds, then by definition
Vo E A(A), 1s's E A(A), s.1. Ui 2., 0. Define the set-valued argmax function Φ (.A)) + 2A(A):
(xx) = { (AAA) Ui(1', ,t, ". ,,) max Ui Ui("", , .., ..,,
2"
We claim that argmax function ((x) is:
Always non non-empty and convex;
Has closed graph.
The first property is obvious, so we focus on the second one. Suppose that sequences {r;}. {yi} satisfy z; + I. I, + and y; E ((z,). Since the payoff function (Lipschitz) continuous, max," (z", :) is continuous by Berge's 's maximum theorem. Thus maxy" U1 (x", "4,-"" ,z)) converges max," U1(1" (x", 2, x). Meanwhile (1 Zy.-. .z, converges to U1 (v. .. ..). Thus
U1(y, aily,,..,a ,x) = lim (36, "., ,x)) = lim max U (x", Iy .. , = max U1 U1(x", ,4, pr, ",,,",))) +0000 x²
1000
2"
This implies y E (xxx) and that Φ has a closed graph. Thus by Kakutani's fixed point theorem, Er xx d(x*). Now have
_,,,,,"))) xx)) U1(x", ....
= max max U1(x", x² x²) > O,
x²
which contradicts with the assumption that the game is zero-sum and symmetric. Consequently, prove the equation. As result, we have
min max U1 (x (" 2n) S min max (z 00)1) = 0. #2. Pn #1
21
To show the second inequality can be strict, consider a 3 3-player minority game. If the other two players act 0 and 1, respectively, then the learner always receive 11/ payoff, which is strictly less than O. We then finish the proofs.
B.2. Proof of Proposition 4.2
In this section, we will prove (2), where the inequality can be made strict in certain games.
Proof of Proposition 4.2. In the proof of Proposition 4.1, we have already shown that min, max,, U1 01(11,08-11 0. Thus, it remains to prove the inequality in (2).
Note that for any 1 x E (AA), we have
00121
E)(((A)
which implies for any æ1 E ((A)
min U1 (11,, sn-1) xEA(A)
min max U x11,1 =EA(A)
By further taking maximum over 2ı E A(A), we show that
min U1(11, 6n < min max U1 U1(21, U1(21,20111 @n-11) xIE((A) (EA(A)
max
aEA(A) eiE((A)
To show that the inequality can be strict, we consider the scenario where the learner is involved in a 3-player majority game and plays mixed strategy (3, 1 - 3) (i.e. play 0 w.p. 3: play 1 w.p. 1 1 3). And the two opponents adopt an identical mixed strategy (p. 1 --pp)) p) (i.e. play 0 w.p. p: play w.p. 1 - p). Then, we can calculate the payoff of the learner as (1 p. = -p (1-11)1-1111110 (=p2==pppppp11------- p)). then follows that max min (1 p.P) s maxge(o.1] min (1 = 1/2, which strictly less than Thus, we finish the proofs.
13

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
B.3. Proof of Proposition 4.3
Proof of Proposition 4.3. Let (,,, denote the probability of observing Uu,....,nn-... when sampling n points from N without replacement, and let IP ( in-1) denote the probability of observing (f....., (n-1) when sampling n 1 points from N with replacement. For any a, then have
Ex [Ui(a,
Σ (f1..ntn Σ
(i in Fig............................. Tin 1)
U1 Ui(a, x0n)))
(
(11....h-11
Note that | 1 1. Thus, we have
Ez_, (Ui(a,x-1)) - U1(a,
51(11800n11) _00-1)||
Σ
(pu/o in-1) -P (1 2n-1))
(11mm1-1)
(" (i - po (i1,...,
(fimndn-1 has repeated value
Σ
pw/o (w/o (n- P 2n-1)
(on 1) na repeated value
=2
Σ
p (i (iI,..., in-1)
in-
(1pprtt 1) has repeated value
N(N 1)..............) (N 12 +2
2
Na-1
2
n 2
2
1
1
1
N
N
N
n 2
n-
2
N
2(n
2)
N
C. Proofs for Section 5
In Section C.I, we establish guarantees for the Hedge algorithm, SAOL* and behavior cloning. In Section C.2, we provide a detailed discussion of the matching lower bounds and prove Theorem 5.4 and Theorem 5.5.
C.1. Guarantees for efficient algorithms
In the sequel, we establish guarantees for the Hedge algorithm by proving Theorem 5.1 in Section C.1.1, for SAOL by proving Theorem 5.2 Section C.1.2, and for behavior cloning by proving Theorem 5.3 Section C.1.3.
C.1.1. PROOF OF THEOREM 5.1
In this section, we establish guarantees for the Hedge algorithm when facing fixed opponents.
Proof of Theorem 5.1. Let arg mix,eaUilsyy 0n-1) We then have
1 T
u² u' (x)"
14

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
T
=Ui(a", , y
u' u²(x)
T 1=1
T
Ui(a", ,y yon-1)
Ui(a" -1++++++++++
Ui a d-1))
T E
d')))
T
(i)
T
1
Un(r ai_1) T (x')
Σ
T
(ii)
For (i), by Hoeffding's inequality and union bound, have with probability least å that
logí A/00)
(i) S Ov
For (ii), by Hedge algorithm, we have
log( log(A), A) (ii) - O(V
T
For (iii), note that (Ui("', d²-;) - (2'))) is martingale difference sequence, thus by Azuma Hoeffdingg inequality, we have with probability at least 1 that
log(1 (1/)
(iii) - O(y
T
Combining the above results, have
1 T
Σ u'(a') s C
log(A/6)
T
for some absolute constant C 0. Thus we finish the proofs.
C.1.2. PROOF OF THEOREM 5.2
In this section, we establish guarantees for SAOL, when facing adaptive opponents.
The basic idea behind SAOL, H is to execute H in parallel over each interval within carefully selected set. This algorithm dynamically adjusts the weight of each interval based on the previously observed regret. In each round, SAOL* H selects an interval in proportion to its assigned weight, applies H to each time slot within this interval, and follows its advice. Through this mechanism, SAOL" HH" achieves near-optimal performance on every time interval. We will leverage the strong adaptivity of SAOT." H our proofs.
Proof of Theorem 5.2. Let I be any fixed interval in [0,T], ag arg {EtEz ('(a) and ut = max.6. 2' (a).
It holds that
Σ (n - (2(()))
Σ (w'it n² (ao)) + Σ (ao) Ua aa))
(8)
15

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
+
(Ui(an, a'11) U1 Ui a (r(x,,a"1) u' u'('))
1EZ
(11)
For (i), it can be seen that
(1)
(u [( (ao)) - IZ] max { {u'r u'(ao)} - 2V FEZ
tEI
Here the last incquality follows from the following argument: otherwise there exists to E such that ufo -00==) > 2V Let an E arg ma (a). For all E I, it then holds that u' ua1) 2 u Vi ufoi Vz > u (a) + V/2 2 u' (ao). Contradict the definition of ag!
For (ii), we have
(ii)
max
Σ (Ui(a,aL1)- U1(x', dii)) C(Vlog A log T) VII, aEA
where the last inequality follows from Theorem in (Daniely et al., 2015).
Combining the upper bound of (i) and (ii), we have for any fixed interval I C [0,
Σ ( - -u'="((zz))
EE
2 + Σ (1' - U1(a0, a' + C(V A + log T) [
REI
(Ui(2', a- - -''('')
YET
We segment the time horizon T into T/ batches (I₃} with each length [Z]. then holds for all j that
Σ
(u - u'(x))
IEI
< 2V2, [ + Σ (u'(a)) - U1(a, + C(Vlog A+ + lo
IEI
Σ
("((',a""1) - -u' -'(x'))
E2
Sum over gives
D-Reg(T))
2 +
(as) U1 (iga +C(T//III)
(Vlog A + log
(ii1)
T
(U((=",a'z)- - -d
(iv)
For (iii,, note that (a) U1 (a aa ,)TT is martingale difference sequence, have with probability at least 1 8 that
T (a((a)UU(aads so (o (VTTlog(A/))
(iii) < max
Σ
16

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
where the last inequality follows from Azuma-Hoeffding inequality and union bound.
For (iv), note that we have with probability at least 1 that
u² (x')) is martingale difference sequence, thus by Azuma-Hoeflding inequality,
(iv) s 0 1osoovTTiii (VTlog(1/))
Consequently we have with probability at least - 8 that
(-Reg(T) & 2V + C(T/VIT) (Vlog A + log 7) + 0 (VTlog(A/))
Choosing [Z] = (2/V))2/5, we have with probability at least 1 - that
(T) s So (V+ (Vog((A)))))))))-))))))) log log
Finally, by the definition of Uavg (T) and ut, we show that
Unvg (T) 2 ul CV2//3--133 (Vlog(A/b) (A/5) + log T)
for some absolute constant C.
C. I.3. PROOF OF THEOREM 5.3
In this section, we establish guarantees for behavior cloning (Algorithm 2) when facing adaptive opponents.
Proof of Theorem 5.3. Note that
T
T
E
u' (x*)
2 2-1+B
Σ u' (at)
T
=-1+ E
Ui 1-1 (w1))n-1)
2 2-1 VT E
Σ Ui(ap 1-1 (1--))
(by the defition of Vr))
T
1 VT E
Σ Ui(y' (
(since at a yf y11
VT
(since the game is symmetric and zero-sum)
Finally, by the definition of uavg (T), we finish the proofs.
C.2. Matching lower bounds
Upon examining Theorem 5.2 alongside Theorem 5.3, it becomes apparent that Theorem 5.2 benchmarks against more stringent standard (i.e., the dynamic oracle) and incurs larger error of v 1/1///-11/3 while Theorem 5.3 sets its comparison against a baseline metric (i.e., the average payoff) and attains a smaller error of Vr/TT. Regarding this observation, one might aspire to devise an algorithm whose payoff satisfies: Unvg (T') 2 u uL-ŌŌ(V/T)) However, Theorem 5,4 and Theorem 5.5 demonstrate that such goal unattainable, by exploring the fundamental limits faced when competing against non- stationary opponents.
Theorem 5.4 shows, when contending with non-stationary opponent, the optimal algorithm must incur dynamic regret at least order of / closing off the possibility of attaining better Vy rate, It's noteworthy that a similar lower bound
17

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
for dynamic regret has already been established under broader conditions (Besbes al., 2014). The distinction of Theorem 5.4 lies in further restricting the hard problems to be symmetric games, implying that the structure of symmetric game does not offer an advantage in improving dynamic regret in the worst case. By comparing this lower bound with Theorem 5.2, it is evident that SAOL H is demonstrated to be minimax optimal, albeit with the inclusion of some logarithmic factors.
Theorem 5.5 establishes the fundamental limit when comparing to average payoff 0. The guarantees achieved by Theorem 5.3 can not be improved the worst case, showing behavior cloning is demonstrated to be optimal upto some constant.
C.2.1. PROOF OF THEOREM 5.4
Proof of Theorem 5.4. We define
payoff for 3-player majority game
if b, E (0, 1) if & [0,1],b,ce {0, 13 o.w.
(a, (a,b,))
defined by symmetric
which is basically the payoff function for 3-player majority game with extra dummy actions. We then define
U\ (a, a2,...,,a,)) an) = (n 1)(n 2)
Σ 2gitisn
(a, ag az)-
We consider game that evolves stochastically, with players, action space A f0, .......,4 A of the first player given by T/(h) We segment the decision horizon T into T/ Ar batches (Tj}, with each batch comprising Ar episodes. We consider two distinct scenarios:
A-11- 13, and the payoff function
Casel: All the other players employ mixture strategy (1/2- + <) (i.e., playing 0 with probability 1/2 playing I with probability 1/2 + e);
Case 2: All the other players employ a mixture strategy (1/2+c,1/ - <) (i.e., playing 0 with probability 1/2 + e, playing with probability 1/2 - <);
At the beginning of each batch, one of these scenarios is randomly selected (with equal probability) and remains constant throughout that batch.
Let m = T/Ar represent total number of batches. We fix some algorithm and a batch j E {1....,,} Let 6, E {1,2] indicate batch j belongs to Casel or Case2. We denote by PV the probability distribution conditioned on batch j belongs to Case oj. and by Po the probability distribution when all the other players employ mixture strategy (1/2,1/2) We further denote by E3, [-] and [F[[]] the corresponding expectations. We denote by N the number of times action a was played in batch j. If the batch j belongs to Case öy. then the optimal action in the batch is -ō, 2. We first present useful lemma.
Lemma C.I. Let ʃ (-1,0, + [0, M) be any bounded real function defined on the payolf matrices R. Then, for any رj E (1,2), < 1/4:
M
E - [o][(R]] <
-2 In [n (1-16)) < 22M AT.
2
By Lemma C.I with f f= Noj - +2 we have
+2.
E Eo 621 s 2 VT.
(4)
Note that
EY, [u (xx = -P%, (a' $ (0, (- (x² =6, -1)+ + (e- 222) --6 + +2)
2:3)
S (- P2 (a' # -5 + 2) + (E 2c 2T2), (n² (x'==Ap =6 -5,+ + 2)
18

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
2222 2e PPj 1Pg,(0 (x'= = -6; + 2),
therefore,
B
Σ n' (x') LETg
S ((Ee- 2 BB, [N -6,+2l
< - + B -2, 55, + 462
Ar.
(by (4))
Consequently, we have
1
E
Σ
u'
(xt)
+ 1 12
< {- - + 16 77IVVrr Σ 2z')
(5)
2
TETs
LET
It then holds that
m
m Σ Exig
EAl
(x())
Σ
n (at)
/=
1ET,
1
Σ EaIE
Ey
Σ
(x(")
+
E2
Σ TET
rt (z)))
2
2
TETs
< > ((-E - 26 2T5)|TTl + T + +46217, AA)
1=1
= 2 + Le2TVAr
Set min=//nn1///AAr) /T). We then have
T Σ 1=1
EaIg (-Rgg(()))) = (e - 222 EAIE
(xx))
n
2 (c 2c²)T (-2eTT + 46 ADr)
= ET -1--4e27 4e2T /TT
= ET(1 - 4e Ar)
ET
Vi T.
= 2
min
BVAT T
Choosing A7 (2/V then have
EAIg DD-Re(TT) 2 CV2//312/3
Recall the definition of davy (T) and ut, we then finish the proofs.
We prove Lemma C.I in the following.
Proof of Lemma C.I. We have that
EY, [f)] - [olf(R)) = Σ ((R)
(P] (R) Po(())
R
19

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Σ
f(R) [P (R) - Po((t)
RiF, (R)2Po(R)
M
E
(P), ( (o(
R.F,, (B)2Fo(1))
M
IP/
-PolTV
M V /2KL(Po || Pb,)) )
(6)
where the last ineqaulity follows from Pinsker's inequality. Let R2 E R be a random vector denoting the payoff for each action at time t, and let Rs RxxA denote the payoff matrix received upon time t: R [R....., Re]" " By the chain rule for the relative entropy, we have
ITil
KL(Po
|| 12
Σ t=1
E
KL (Po(Re R² || Po, (Rs R ].
Note that
Po R4 1-1,00 1, ,,,,, -1] R² Po Rb = 0, 1, -1, ..... -1] 1| R² 1/4
Po R 1//2.1/2 -1, -..... -1] R 1/2.
In the case 6, = 1, we have
P/ (Re [-1,0, -1 -1 =
P/ (R, -0,-1.-1, )
(1/2 c)
p (R,
-1, -
e).
In the case 8j- 2, we have
Pd = -1,,,, ) (1/2 c)²
(R, ) o1/
8, (R₂ (R, =
= + c)(1/2 c).
Thus, we have
KL (ReeRe (Re RT
RR R R²-1)
(8)
In 1/4
1/4
1/2
+
+ In
4 (1/2 c)2
4
(1/2-c)2
+ (//2+c)(1/2 -
In (1 - 4c?).
(9)
Combining (6), (7) and (8), we have
M.
E - < V -22 In (1 4c2).
2
If we further have e < 1/4, it then holds that - In (1 - 462) < 16133433) and consequently
Ey [f()) Eolf(R)) < M V
- In (1 422) s 2Mc / S. 2M A.M
20

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
C.2.2. PROOF OF THEOREM 5.5
Proof of Theorem 5.5. We consider game that evolves stochastically, with players, action space A {0, 1, ,...,, A0 and the same payoff function -\nh as outlined in Theorem 5.4. We segment the decision horizon '' into T/Ar batches { with each batch comprising Âr episodes. We consider two distinct scenarios:
Casel: All the other players play O;
Case 2: All the other players play 1.
In Case I, we have u' (0) = 0 and u' (a) = -1 for all a a 0. In Case 2, we have (1(1) = 0 and u'(a) -1
1 for a + 1. At the beginning each batch, one of these scenarios randomly selected (with equal probability) and remains constant throughout that batch.
Let T/Ar represent total number of batches. We fix some algorithm. Let 63 {1,2} indicate batch j belongs to Casel or Case2. We denote by pl oy the probability distribution conditioned on batch j belongs to Case 6j. and by R3,, []] the corresponding expectation. It then holds that
EAIS
u'
(x')
=
EAIg
Σ u' (x¹)
f=1
TE
/=1
TET;
m
EAlg
2 Ey
Σ (xt)
+ +
Σ ut (xt)
j=l
AET3
IETS
EalR
B
thi
+
B2 2
}]]
where f1d represents the first episode of batch and the inequality follows from the fact that us O. Note that
E u p.
2
}]
+
1
E2
(zotii)
}]=
- P P( * + I (2 # #1))
2
(Z 0) + P(
+ +1))
S 2
2
where the second equation follows from the fact that 5r is independent of 8z. Thus, we have
EAIg
a' (x+)
m
T
2
2AT
IET
Choosing AT T/VT, we have
m Σ
Eagg
u'(x))
S
-1
j=1
Recall the definition of Havg (T), we then finish the proofs.
D. Experiments Details
In this section, we provide additional details for experiments.
D.I. Algorithms
We refer readers Algorithm 3-6 for detailed implementation of algorithms in the experiment. For MV, we choose 1) = For SDG, we choose 7) 2.
D.2. Computation Resources
The experiments are conducted on server with 256 CPUs. Each experiment can be completed in few minutes.
21

---

Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Algorithm Self-play meta-algorithm
1: Initialize learner's mixed strategy 21-
2: for = .,.... T do
3: Sample action af 2t for all player [n].
4: Update strategy F++1 using the gradient information U1(: d',))"))).
Algorithm Behavior Cloning
1: In the first round, play Uniform(AA).
2: for t = 2, ., I do
3: Play di2 1-1 i.e. the action played by Player 2 in the last round.
Algorithm Self-Play
Require: Number of iterations T, action space A, learning rate mh ny
log A
number of players and initialize
strategy Z0.
1: for = 1 to T do
2: Sample actions a:- ~ It-1 for i = 2, ,, Denote a'-' = (a2 1-- at. n. (a) x ax- (a)xpp Va E E.A
3: Update
Algorithm 4 Self-Play with Regularization
Require: Number of iterations action space A, learning rate 1)t m7 log |A| number of players n, initialize strategy
Zo. meta-strategy Umeta: and regularization parameter X.
1: for = I to do
2: Sample actions a. It-1 for .,....n. Denote a'='' := (a2 ,..., ....,ar, a)
3: Update
log log + Erer Tri a²11) ) + + EEst 4r log Ummes(a) Va E A.
(a) exp
1+ E+
Algorithm 5 Hedge
Require: Number of iterations T, action space A, learning rate 7h T
log A
number of players n, and initialize
strategy Zg-
1: for t= I to T do
2: Sample actions a. ~ Umeea for i = 2...., Denote a'-²' = (a² 1-1 ..... (111
3: Update
(a)a) x (aapp A
Algorithm Exploiter for strategy
Require: Number of iterations T, action space A, learning rate 7) = n7
log
number of players n, and initialize
strategy Zi--
1: for 1 T do
2: Sample actions a
3: Sample actions a; It-1 for i = 2,..., Denote a'- (a 1-1 ...., a -
4: Update
a
(x)a) x 2=-1(a)exx)
Nt
Σ
U1 (a
; 11. a1. li Va A.
11
t=2
22


Reviews:
[{"review_id": "ofQaJFgwJe", "reviewer": "Reviewer_SUo1", "summary": "This paper proposes a novel Monte Carlo Tree Search–inspired algorithm for multi-agent, simultaneous-move games under imperfect information.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback on our submission. Upon reviewing your comments, we believe there may have been a misunderstanding, as the points raised do not seem to be relevant to our paper.\n\nWe appreciate the time and effort you have put into your review and are happy to provide further clarification or address any specific questions if needed.", "claims_and_evidence": "The proposed NN-CCE algorithm achieves performance that is superior or competitive with some multi-agent reinforcement learning algorithms (e.g., MAPPO, MADDPG) across cooperative, competitive, and mixed tasks.", "methods_and_evaluation_criteria": "The authors benchmark performance mainly via win rate in competitive scenarios or average reward/success rate in cooperative tasks.", "theoretical_claims": "The key theoretical claim is that following a no-regret learning procedure (like EXP-IX) in repeated states leads to approximate CCE in the time-averaged strategy profile. This is a standard result from the game theory literature on no-regret dynamics.", "experimental_designs_or_analyses": "The authors evaluate their algorithm on 17 tasks, spanning different complexities and team-based structures (2-player zero-sum, 2-team with multiple agents, purely cooperative).\n\nThey compare to diverse baselines: MAPPO, MADDPG, s-MCTS, DORA, plus references to prior results for variants of PSRO or CFR on smaller tasks.", "relation_to_broader_scientific_literature": "The paper is well positioned within the literature on multi-agent reinforcement learning (MADDPG, MAPPO) and game-theoretic equilibrium approximation (PSRO, CFR, DORA).", "essential_references_not_discussed": "No glaringly missing citations.", "other_strengths_and_weaknesses": "Strengths:\nThe authors introduce a method that abandons deeper search in favor of single-step lookahead, using an online no-regret learner (EXP-IX) at each state to approximate a CCE distribution over actions.\n\nThey decouple the “data collection” (policy rollout) from the “equilibrium approximation” (no-regret workers) and from the “value/policy network training\"\n\n\nWeaknesses:\nBy restricting the MCTS procedure to depth 1, the algorithm might miss deeper strategic foresight. While the neural value function can somewhat compensate, there may be domains where deeper lookahead is crucial.", "other_comments_or_suggestions": "A brief discussion contrasting Coarse Correlated Equilibria with Correlated Equilibria and (in zero-sum) Nash Equilibria would be beneficial for readers less familiar with these solution concepts. The paper touches on it, but a succinct subsection might be useful.", "questions_for_authors": "How does your method adapt if the game includes partial observability of the environment state itself (not just hidden opponent actions)? Do you foresee major changes to the design of the no-regret worker or the neural network architecture in more general imperfect-information settings?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "cBi5mC6n1f", "reviewer": "Reviewer_Ada2", "summary": "The authors present an algorithms for learning in symmetric constant-sum multiplayer games, where the solution concept is equal allocation of social welfare among the players. They show that standard no-regret learning algorithms in a self-play setup cannot achieve \"equal share\". They demonstrate necessary conditions for a game and algorithmic assumptions necessary to allow an equal share strategy to be computable, and then adapt algorithms from the online learning literature to compute equal share strategy under different assumptions on the opponent.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for reading our paper and for your insightful comments.\n\n**Q1:  Clarification of the experiment**\n\n**A1:** Our experiment aims to demonstrate that although self-play-based meta-algorithms have been effective in many real-world multiplayer games, they can still fail to secure an equal share in worst-case scenarios. Specifically, we show that the meta-algorithms under consideration — **SP_scratch**, **SP_BC**, and **SP_BC_reg** — which are shown to converge to NE, do not guarantee equal outcomes in our constructed cases.\n\nConsistent with the theoretical analysis in Section 5.1, our experimental setup assumes that all opponents play a fixed, non-adaptive strategy across all rounds. This setup represents a fundamental and arguably the simplest scenario in which a well-designed algorithm should perform reliably, especially given that real-world opponents can be adaptive or even adversarial.\nFor self-play-based algorithms, we first run each method until convergence and then evaluate the learned policy against the fixed opponent strategy. While SP_scratch has no access to the opponent’s strategy, we include SP_BC and SP_BC_reg as baselines for fair comparison. These methods incorporate the opponent’s strategy as either initialization or regularization, following design principles from recent self-play variants that achieve state-of-the-art performance in multi-player games. Finally, as discussed in Section 3, self-play from scratch without any opponent knowledge can fail even in simple settings, such as the majority-vote game.\n\n**Q2: The novelty of the results is limited**\n\n**A2: Novelty.** We would like to point out that, **compared to developing complex algorithmic techniques, identifying and formulating the right question to solve is equally—if not more—important.** This paper precisely addresses the latter: propose novel, practical, and important formulations, study basic properties, and bring the right tools to give principled solutions in a variety of settings. \n\nIn multiplayer games, much of the existing research has focused on achieving equilibrium-based outcomes. While extensively studied, equilibrium-based approaches have well-known limitations and are often unsuitable for developing AI agents in multiplayer settings. This concern was explicitly raised in prior work on real-world multiplayer game systems (e.g., Brown & Sandholm, 2019); however, such works do not resolve the issue or propose alternative objectives. Our paper is the first to formulate the problem as achieving equal share, and to clarify that the objective is theoretically well-behaved only under the condition that all opponents deploy identical strategies. While this condition seems strong, we justify its practical relevance and note that it aligns with the settings implicitly enabled in most prior state-of-the-art empirical work. **We emphasize that these findings, though not technically challenging, are very fundamental and entirely novel—they have not been previously discovered or formally articulated in the literature.**\n\n**Technical Contribution on Efficient Algorithms.**\nIn addition to our contribution to identifying the correct solution concept, this paper also provides a comprehensive set of algorithmic results for achieving equal share in various settings: (1) fixed opponents; (2) slowly changing opponents; (3) opponents that adapt at intermediate rates; (4) matching lower bounds. \n\nFor (1) and (2), we leverage established techniques from the no-regret and no-dynamic-regret learning literature, achieving equal shares with provable guarantees. Our contribution here mostly lies in identifying and bringing the right tools and adapting them to solve the right setup of the multiplayer games, where, to the best of our knowledge, prior state-of-the-art AI systems on multiplayer games (for Poker, etc) have not utilized techniques such as no-dynamic-regret.\n\nFor (3), we believe our discovery here is completely new, that simple algorithms like behavior cloning can sometimes even outperform sophisticated no-dynamic regret algorithms. Such a result is only possible by leveraging the symmetric structure of the multiplayer game beyond treating it as one versus an adversarial group of opponents.\n\nFor (4), while similar lower bounds have been shown in more general games, they do not apply to our settings as the hard instances constructed in prior lower bounds are not symmetric games. In this paper, we carefully construct new hard instances showing that the algorithmic results we proved in (2) and (3) are near-optimal.", "claims_and_evidence": "Yes, the claims are supported, and theoretical and empirical evidence are presented to support the claims.", "methods_and_evaluation_criteria": "Yes. they do.", "theoretical_claims": "Yes, I checked the correctness of all proofs.", "experimental_designs_or_analyses": "The experimental analysis is a bit confusing. The comparison is done against a set of fixed meta-strategies, but then the self-play algorithm is run, trying to compute optimal strategies for each player in a no-regret fashion. It is not clear to me what the experiments aim to illustrate.", "relation_to_broader_scientific_literature": "The authors do a good job of contextualizing their work in the broader line of work on this topic. In general, computing NE in general multiplayer games is hard. The authors choose to focus on the case of zero-sum symmetric multiplayer games and come up with a tractable solution concept for this reason.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "While the authors propose an interesting theoretical framework, the novelty of the results is limited. The sufficient conditions are immediate observations that can be made. The extension of no-static-regret algorithms and dynamic regret algorithms to the equal share setting while interesting, is a fairly straightforward extension.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Can you explain the experiments in more detail? What are they aiming to illustrate?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mFtdfYCJX6", "reviewer": "Reviewer_sKsB", "summary": "The paper proposes a new solution concept for constant-sum, multi-player, symmetric games, which is referred to as equal share. What this means is that each player secures the same utility. The paper observes that usual equilibrium concepts do not necessarily satisfy equal share, and it then proceeds by identifying necessary and sufficient conditions under which equal shares can be attained--namely, players adopting symmetric dynamics and limited opponent adaptivity. Under those two conditions, they provide algorithms that indeed attain equal share. Finally, experimental results are provided to support some of the theoretical claims.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for reading our paper and for your insightful comments.\n\n**Q1: The theoretical results are not surprising**\n\n**A1: Novelty.** We remark that, **compared to developing complex algorithmic techniques, identifying and formulating the right question to solve is equally—if not more—important.** This paper precisely addresses the latter: propose novel, practical, and important formulations, study basic properties, and bring the right tools to give principled solutions in a variety of settings. \n\nIn multiplayer games, much of the existing research has focused on achieving equilibrium-based outcomes. While extensively studied, equilibrium-based approaches have well-known limitations and are often unsuitable for developing AI agents in multiplayer settings. This concern was explicitly raised in prior work on real-world multiplayer game systems (e.g., Brown & Sandholm, 2019); however, such works do not resolve the issue or propose alternative objectives. Our paper is the first to formulate the problem as achieving equal share, and to clarify that the objective is theoretically well-behaved only under the condition that all opponents deploy identical strategies. While this condition seems strong, we justify its practical relevance and note that it aligns with the settings implicitly enabled in most prior state-of-the-art empirical work. **We emphasize that these findings, though not technically challenging, are very fundamental and entirely novel—they have not been previously discovered or formally articulated in the literature.**\n\n**Technical Contribution on Efficient Algorithms.**\nIn addition to our contribution to identifying the correct solution concept, this paper also provides a comprehensive set of algorithmic results for achieving equal share in various settings: (1) fixed opponents; (2) slowly changing opponents; (3) opponents that adapt at intermediate rates; (4) matching lower bounds. \n\nFor (1) and (2), we leverage established techniques from the no-regret and no-dynamic-regret learning literature, achieving equal shares with provable guarantees. Our contribution here mostly lies in identifying and bringing the right tools and adapting them to solve the right setup of the multiplayer games, where, to the best of our knowledge, prior state-of-the-art AI systems on multiplayer games (for Poker, etc) have not utilized techniques such as no-dynamic-regret.\n\nFor (3), we believe our discovery here is completely new, that simple algorithms like behavior cloning can sometimes even outperform sophisticated no-dynamic regret algorithms. Such a result is only possible by leveraging the symmetric structure of the multiplayer game beyond treating it as one versus an adversarial group of opponents.\n\nFor (4), while similar lower bounds have been shown in more general games, they do not apply to our settings as the hard instances constructed in prior lower bounds are not symmetric games. In this paper, we carefully construct new hard instances showing that the algorithmic results we proved in (2) and (3) are near-optimal.\n\n**Q2: Two claims made in Section 4**\n\n**A2:**\n**About Condition 1**: In Section 4.1, we introduce the concept of population meta-strategy and show that within a large player base, even opponents with different strategies can be viewed as adopting the same population meta-strategy. As mentioned in Section 4.1, various forms of games, such as card games, board games, and online video games, all exemplify the concept of population games via matchmaking in a large population of players. \n\n**About Condition 2**: Our paper studies both scenarios where the opponents' policy is fixed (see Section 5.1) and where it is slowly adapting (see Section 5.2). While capable of updating their policies, the opponents do not run algorithms specifically targeting our AI agent, as it is merely one player within a vast pool of participants. Moreover, Proposition 4.2 points out that attaining equal shares is impossible if opponents can change their meta-strategy arbitrarily fast across different rounds, supporting Condition 2.\n\n**Q3: About experiment**\n\n**A3:**\nPlease refer to **A1** to **Reviewer Ada2** for details on our experiment design. Our experimental cases are adversarially constructed, based on the common characteristic of many multiplayer games: the existence of multiple NE. This can cause self-play variants to converge to a bad NE, resulting in negative payoffs against carefully chosen opponent policies. Since many real-life games have multiple NEs, the worst-case results of our experiments are relevant to practical games.\n\nWhile self-play algorithms have achieved impressive results in games like multiplayer poker, these successes are often context-specific and rely on extensive engineering and human input. We agree that understanding why these algorithms succeed and whether they can generalize across different game settings is an important future question, though it is beyond the scope of this paper.", "claims_and_evidence": "Overall, the claims made in the paper are well-grounded, although there are certain points that are very much debatable. In particular, I want to mention two claims made in Section 4.1, which serve to justify the main assumptions of the paper. The first one is that \"Condition 1 is further implicitly adopted by most prior state-of the-art AI agents for multiplayer games.\" It is true that self-play algorithms satisfy the symmetry condition postulated in the paper, but I see no reason whatsoever why this is a reasonable assumption when interacting with opponents in a realistic game (in the self-play setting, one, of course, controls the algorithms employed by all players, but this is not so in practice). \n\nThe second claim is that \"it is often safe to assume that the population meta-strategy will not quickly adapt to one particular player’s strategy.\" As far as I can see, no evidence is given to justify this claim. In many ways, limited opponent adaptivity trivializes the problem and goes against basic game-theoretic principles.", "methods_and_evaluation_criteria": "The evaluation in Section 6 supports some of the claims of the paper, but it does not go far enough. The benchmarks tested have been cherry-picked to serve the narrative of the paper, and they are not comprehensive enough. The paper would benefit from providing a more complete evaluation based on more benchmarks. The main question is why existing self-play algorithms perform so well in practice despite such clear deficiencies. Is it the case that the games tested by the authors do not reflect practical examples? It would be interesting if the authors could provide a more general characterization of games with practical relevance where similar phenomena are present.", "theoretical_claims": "All theoretical claims appear to be sound; I did not find any notable issue.", "experimental_designs_or_analyses": "The experimental evaluation is sound in the methodology of the games tested, but, as I pointed out above, it is not comprehensive enough.  It's hard to draw concrete conclusions from a very limited benchmark evaluation.", "relation_to_broader_scientific_literature": "The paper tries to address a thorny issue in multi-agent learning concerning the deficiencies of traditional equilibrium concepts. These issues are well understood, and so the observations made in Section 3 are fairly immediate from existing results. The paper departs from most of the line of work in game theory by going beyond equilibrium, and is mostly related to opponent modeling.", "essential_references_not_discussed": "One paper that could be discussed is \"Game Theory-Based Opponent Modeling in Large Imperfect-Information Games,\" and more broadly I believe that the authors could elaborate more on how their results relate to opponent modeling.", "other_strengths_and_weaknesses": "On the positive side, the paper attempts to address an important problem in multiagent learning. The proposed solution concept is fairly natural, and as far as I know has not been analyzed before. The paper fully characterizes conditions under which guaranteeing equal share is possible. I believe that there are certain settings in which the results provided by the paper will be relevant.\n\nOn the negative side, the theoretical results are not surprising, and mostly follow directly from existing results, although there is value in stating and formalizing such results. Furthermore, as I said above, the assumption that opponents are not fully adaptive is a very strong assumption, which really goes against basic game-theoretic principles. I understand that making progress on this problem necessitates departing from the existing normative assumptions, but the paper hasn't made an entirely convincing case.", "other_comments_or_suggestions": "As I pointed out earlier, I believe that the paper would benefit considerably by a more comprehensive experimental evaluation.", "questions_for_authors": "I have no further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nqNrRSzBXQ", "reviewer": "Reviewer_fi33", "summary": "This submission studies multiplayer (n-player where n >= 3) symmetric zero-sum games (such as Mahjong and Poker). Unlike two-player zero-sum games, equilibria in multiplayer games are neither unique nor non-exploitable, which poses a challenge when competing against opponents who play strategies from different equilibria or non-equilibria strategies. Motivated by these observations, the authors propose a new learning objective: ensuring that each player secures at least C/n utility in a n-player symmetric game with total payoff C. \n\nThe authors derive conditions under which obtaining this equal share is tractable, and design learning algorithms to approximate this objective which are inspired by no-regret learning. The authors also derive complementary lower bounds which largely match their upper bounds. \n\nThey empirically evaluate their algorithms in two symmetric zero-sum games: majority vote and switch dominance game. They find that self play-based methods often fail to guarantee an equal share, and are often out-performed by the authors’ algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your inspiring comments. We address your concerns as follows.\n\n**Q1: Novelty and contributions**\n\n**A1:** \nPlease refer to **A1** to **Reviewer Ada2** for clarification on the novelty and technical contribution of our work.\n\n**Q2: Extension to asymmetric games**\n\n**A2:** As mentioned on page 4, L184-186 (left column), we can effectively transform all asymmetric games into symmetric ones by introducing an initial stage where each player’s position is randomly assigned. This randomization process effectively symmetrizes the game, as each player has an equal probability of assuming any role, ensuring that no player has a consistent positional advantage. Therefore, under this transformed setting, our analysis remains applicable.\n\nTo further clarify the mathematical transformation, we enlarge the action space to incorporate both the player's position and their actions. Specifically, for each player $i$, we define $(P_i, a_i)$ where $P_i$ represents the player's position or role in the game, and $a_i$ denotes their action. We then define a symmetric utility function $U^{sym}_i$ as follows:\n\n$U^{sym}_i ((P_1, a_1), \\ldots, (P_n, a_n))$\n\n$:=U_{\\sigma^{-1}(i)}^{asym} (a_{\\sigma^{-1}(1)}, \\ldots, a_{\\sigma^{-1}(n)}),$\n\nwhere $\\sigma$ is a permutation that reorders player positions such that $\\sigma(P_1, \\ldots, P_n) = (1, \\ldots, n)$.  \nThe action space is defined as $\\bigcup_{j=1}^n (P_j \\times \\mathcal{A}_j)$, where $\\mathcal{A}_j$ denotes the set of actions available to players when they are in position or role $P_j$.  \nThis transformation aligns the players' positions with a standardized symmetric framework, enabling our analysis to apply to games that are asymmetric by nature but can be symmetrized under random initial positioning.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This work falls under the category of learning in games. Specifically, they propose novel objectives for learning in multiplayer symmetric games.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths: \nThe downsides pointed out by the authors about multiplayer equilibria are well-known “pain points” in algorithmic game theory, and I appreciate the authors’ attempt to propose a new objective. This new objective is very natural in symmetric games. The authors provide nearly-matching upper- and lower-bounds on learning algorithms for accomplishing this objective, which, when combined, give a clean solution to this problem. \n\nWeaknesses: \nOne weakness of this submission is that the proposed algorithms are not terribly novel. When playing against stationary opponents, the authors use the well-known Hedge algorithm to obtain an approximately equal share. Against adapting opponents, they adapt the Sttrongly Adaptive Online Learning algorithm of Daniely et al., 2015 to achieve an approximately equal share.  With that being said, there is still value in showing that existing techniques can accomplish this new objective and so I do not view this as a major weakness.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Do you think any of your ideas could generalize to multiplayer games which are not symmetric? Or are completely new solution concepts needed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: [Note: Review SUo1 was excluded from my evaluation of the paper given that the review appears to not be about the paper at hand and the reviewer has not responded to queries.]

Overall, the reviewers feel the reasons to accept are more than the reasons to reject.  The reviewers feel the problem domain is unique and challenging.  However, they feel the evaluations are somewhat trivial -- more extensive evaluations with more sophisticated opponents would improve the paper substantially.  However, as one reviewer noted, you have to start somewhere.  As such, I am marking this paper as "weak accept" (if there is room in the program).

I encourage the authors to take into account the reviewer feedback as they iterate on the paper.
Decision: Accept (poster)