Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games

## Abstract

Abstract This paper examines multiplayer symmetric constant-sum games with more than two players in a competitive setting, including examples like 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 𝐶 𝑛 C/n italic_C / italic_n in an n 𝑛 n italic_n -player symmetric game with a total payoff of C 𝐶 C italic_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.

## 1 Introduction

In recent years, AI systems have achieved remarkable success in multi-agent decision-making problems, particularly in a wide range of strategic games. These include, but are not limited to, Go (Silver et al., ), Mahjong (Li et al., ), Poker (Moravčík et al., ; Brown & Sandholm, , ), Starcraft 2 (Vinyals et al., ), DOTA 2 (Berner et al., ), League of Legends (Ye et al., ), and Diplomacy (Gray et al., ; Bakhtin et al., ; † et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al., ). Many of these games are two-player zero-sum games(^1^11Games such as DOTA and League of Legends, despite involving two teams, can be mostly considered similar to two-player zero-sum games in terms of their game structures and solutions.), where Nash equilibria always exist and can be computed in polynomial time.
Nash equilibria in two-player zero-sum games are also non-exploitable—an agent employing a Nash equilibrium strategy will not lose even when facing an adversarial opponent who seeks to exploit the agent’s weaknesses. Although such equilibrium strategies do not necessarily capitalize 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.

In contrast, multiplayer games—defined here as those with *more than two players*—exhibit fundamentally different game structures compared to two-player zero-sum games. This distinction introduces several unique challenges. Firstly, Nash equilibria are believed to be no longer computable in polynomial time (Daskalakis et al., ; Chen & Deng, ). Moreover, there may exist multiple Nash equilibria with distinct values. Such non-uniqueness in equilibria raises a critical concern about the adoption of equilibrium strategies in multiplayer settings: if a learning agent adopts an equilibrium that is different from other players, collectively, 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 strategies are no longer non-exploitable and fail to provide meaningful guarantees when competing against opponents who are not playing equilibria. Although the introduction of alternative equilibrium notions such as (coarse) correlated equilibria alleviates computational hardness, issues of non-uniqueness and the lack of guarantees in the general settings remain. This leads to the first critical question:

What is the *suitable solution concept* for learning in multiplayer games?

Due to the presence of such fundamental challenge, even state-of-the-art expert-level or superhuman AI systems for popular multiplayer games, including Diplomacy (Bakhtin et al., ; † et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al., ) (7 players), Poker (Brown & Sandholm, ) (6 players), and Mahjong (Li et al., ) (4 players), are designed with limited theoretical supports.
These works focus on developing algorithmic frameworks capable of learning effective strategies that excel in ladders, online gaming platforms, or tournaments against opponents. Generally, most of these systems rely on a basic self-play framework, starting from scratch or from opponents’ 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 applications they were designed for, often coupled with human expertise and extensive engineering efforts. It remains unclear whether these algorithms are general-purpose solutions that can be readily applied to multiplayer games beyond Mahjong, Poker, or Diplomacy. This leads to the second important question:

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., ), Mafia, and Catan.(^2^22All these examples are symmetric games up to randomization of the seating.) *Symmetry brings fairness among players, providing a natural baseline* where a learning agent should at least *secure an equal share* — achieving an expected payoff of $C/n$ in an $n$-player symmetric game with a total payoff of $C$. This paper takes an initial step toward addressing the two fundamental questions highlighted above by focusing on securing an equal share in multiplayer symmetric normal-form games(^3^33Extensive-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 a strategy in EFGs or MGs, although such representations may not always be efficient.). The main contributions are summarized as follows:

1. Regarding the question of solution concepts, we first demonstrate the insufficiency of classical equilibrium concepts 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 adaptivity, 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 multiplayer AI agents.

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 communities to achieve equal share with provable guarantees. Concretely, this paper considers several opponent settings: fixed, slowly adapting, and opponents that adapt at intermediate rates. For all cases, we design algorithms that approximately achieve equal share, with an error tolerance of $1/\text{poly}(T)$, where $T$ is the total number of games played. Additionally, we provide matching lower bounds, demonstrating that these guarantees cannot be significantly improved in the worst-case scenario.

3. We further complement our theory by experiments on two basic multiplayer symmetric games. Our experimental 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 settings, while our principled algorithm always succeeds; (2) prior meta-algorithm has no clear advantage over our algorithm 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.

### 1.1 Related work

##### AI gaming agents in practice

Building superhuman AI has long been a 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., ), Go (Silver et al., ), Heads-Up Texas Hold’em (Moravčík et al., ; Brown & Sandholm, ), Starcraft 2 (Vinyals et al., ), DOTA 2 (Berner et al., ) and League of Legends (Ye et al., ). Most of them are based on finding equilibria via self-play, fictitious play, league training, etc. There is comparatively much less amount of work on games with more than two players, whose game structures are fundamentally different from two-player zero-sum games. Several remarkable multiplayer successes include Poker (Brown & Sandholm, ), Mahjong (Li et al., ), Doudizhu (Zha et al., ) and Diplomacy (Bakhtin et al., ; † et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al., ). 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 enhancing it through self-play, and finally applying adaptations based on the game’s specific structure or human expertise. It remains elusive whether such a recipe is generally effective for a wide range of multiplayer games.

##### Existing results for symmetric games

Von Neumann & Morgenstern () gave the first definition of symmetric games and used the three-player majority-vote example to showcase the stark difference between symmetric three-player zero-sum games and symmetric two-player zero-sum games. In his seminal paper that introduced Nash equilibrium, Nash proved that a symmetric finite multi-player game must have a symmetric Nash equilibrium  (Nash, ). However, this existence result holds little significance from an individual standpoint, as there is no reason *a priori* to assume that other players are indeed playing according to this symmetric equilibrium. Papadimitriou & Roughgarden () studied the computational complexity of finding the Nash equilibrium 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 () proposed *anonymous games*, a generalization of symmetric games.

##### No-regret learning in games

There is a rich literature on applying no-regret learning algorithms to learning equilibria in games. It is well-known that if all agents have no regret, the resulting empirical average would be an approximate Coarse Correlated Equilibrium (CCE) (Young, ), while if all agents have no swap-regret, the resulting empirical average would be an $\epsilon$-Correlated Equilibrium (CE) (Hart & Mas-Colell, ; Cesa-Bianchi & Lugosi, ). Later work continuing this line of research includes those with faster convergence rates (Syrgkanis et al., ; Chen & Peng, ; Daskalakis et al., ), last-iterate convergence guarantees (Daskalakis & Panageas, ; Wei et al., ), and extension to extensive-form games (Celli et al., ; Bai et al., , ; Song et al., ) and Markov games (Song et al., ; Jin et al., ).

## 2 Preliminaries

##### Notation.

For any set $\mathcal{A}$, its cardinality is represented by $|\mathcal{A}|$, and $\Delta(\mathcal{A})$ denotes a probability distribution over $\mathcal{A}$. We employ $\mathcal{A}^{\otimes n}$ to denote the Cartesian product of $n$ instances of $\mathcal{A}$. Given a distribution $x$ over $\mathcal{A}$, $x^{\otimes n}$ represents the joint distribution of $n$ independent copies of $x$, forming a distribution over $\mathcal{A}^{\otimes n}$. For a function $f:\mathcal{A}\rightarrow\mathbb{R}$, we denote $\|f\|_{\infty}:=\max_{a\in\mathcal{A}}|f(a)|$. We use $[n]$ to denote the set $\{1,\ldots,n\}$. 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 consists of a finite set of $n$ players, where each player has an action space $\mathcal{A}_{i}$ and a corresponding payoff function $U_{i}:\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n}\to[-1,1]$ with $U_{i}(a_{1},\ldots,a_{n})$ denotes the payoff received by the $i$-th player if $n$ players are taking joint actions $(a_{1},\ldots,a_{n})$. We define a game as constant-sum if there exists constant $C$ such that $\sum_{i=1}^{n}U_{i}(a_{1},\ldots,a_{n})=C$ for all joint actions. We further denote a game as zero-sum if it is a constant-sum game with a total payoff of $C=0$. Normal-form games can represent a wide range of games as their special cases, including sequential games such as extensive-form or Markov games.

##### Strategy

A (mixed) strategy of a player is a probability distribution over the player’s actions.
For $i\in[n]$, we use $a_{i}\in\mathcal{A}$ and $x_{i}\in\Delta(\mathcal{A})$ to denote an action and a mixed strategy of the $i$-th player respectively. We use $a_{-i}\in\mathcal{A}^{\otimes n-1}$ and $x_{-i}\in\Delta(\mathcal{A}^{\otimes n-1})$ to denote the actions and the mixed strategies of the other players.
We denote
$U_{i}(x_{i},x_{-i}):=\mathbb{E}_{a_{i}\sim x_{i},a_{-i}\sim x_{-i}}\left[U_{i}
(a_{i},a_{-i})\right].$

##### Learning protocol

We assume that the learner knows the game rule, and thus her own payoff function $U_{1}$. At every round $t$, all players take action simultaneously, and the learner only observes the opponents’ noisy actions $(a_{2}^{t},a_{3}^{t},\ldots,a_{n}^{t})$ that are sampled from their strategies.

##### Best response

Given a mixed strategy $x_{-i}$ of the other $n-1$ players, the *best response set* ${\rm BR}_{i}(x_{-i})$ of the $i$-th player is defined as ${\rm BR}_{i}(x_{-i}):={\arg\max}_{a_{i}\in\mathcal{A}_{i}}U_{i}(a_{i},x_{-i})$.

##### Equilibrium

Nash Equilibrium (NE) is the most commonly-used solution concept for games: a mixed strategy $x\in\Delta(\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{n})$ of all players is said to be NE if $x$ is a product distribution (^4^44The randomness in different players’ strategies are independent.), and no player could gain by deviating from her own strategy while holding all other players’ strategies fixed. That is,
for all $i\in[n]$ and $a^{\prime}_{i}\in\mathcal{A}_{i}$, $\mathbb{E}_{a\sim x}[U_{i}(a_{i},a_{-i})]\geq\mathbb{E}_{a\sim x}[U_{i}(a^{
\prime}_{i},a_{-i})]$.

There are also two equilibrium notions relaxing the notion of NE by no longer requiring $x$ to be a product distribution. It allows general joint distribution $x$ which describes correlated strategies among players. In particular, (1) $x$ is a Correlated Equilibrium (CE) if for all $i\in[n]$ and $a^{\prime}_{i}\in\mathcal{A}_{i}$, $\mathbb{E}_{a\sim x}[U_{i}(a_{i},a_{-i})\mid a_{i}]\geq\mathbb{E}_{a\sim x}[U_
{i}(a^{\prime}_{i},a_{-i})\mid a_{i}]$, and (2) $x$ is Coarse Correlated Equilibrium (CCE) if for all $i\in[n]$ and $a^{\prime}_{i}\in\mathcal{A}_{i}$:
$\mathbb{E}_{a\sim x}[U_{i}(a_{i},a_{-i})]\geq\mathbb{E}_{a\sim x}[U_{i}(a^{
\prime}_{i},a_{-i})]$. 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 relationship among various equilibrium concepts is encapsulated by ${\rm NE}\subset{\rm CE}\subset{\rm CCE}$.

##### Two-player zero-sum games

It is well-known that in two-player zero-sum games, all Nash equilibria share the *unique* payoff value 0 0. Furthermore, a Nash equilibrium is *non-exploitable* against any strategy that is not necessarily an equilibrium. In math, if $(\mu^{\star},\nu^{\star})$ is the Nash equilibrium, we have $\min_{\nu}U_{1}(\mu^{\star},\nu)=\max_{\mu}\min_{\nu}U_{1}(\mu,\nu)=0$.

##### Multiplayer or general-sum games

When the number of players is greater than two, or the games are no longer constant-sum games, Nash equilibria become PPAD-hard to compute  (Daskalakis et al., ) while CEs and CCEs can be still computed in polynomial time. All of these three concepts admit multiple equilibria with distinct payoffs. Furthermore, they no longer own strong guarantees, such as non-exploitness, when competing against non-equilibrium players.

### 2.2 Symmetric games and equal share

##### Symmetric games

For an $n$-player normal-form game with an action space $\{\mathcal{A}_{i}\}_{i=1}^{n}$ and a payoff $\{U_{i}\}_{i=1}^{n}$, we say the game is symmetric if (1) $\mathcal{A}_{i}=\mathcal{A}$, for all $i\in[n]$; (2) for any permutation $\sigma:[n]\rightarrow[n]$, we have $U_{i}(a_{1},\cdots,a_{n})=U_{\sigma^{-1}(i)}(a_{\sigma(1)},\cdots,a_{\sigma(n)})$.

In short, the payoffs of a 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_{1}$, is sufficient to encapsulate the entire game.

Symmetric games are popular in practice as they bring fairness 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 an agent attains an equal share, if the agent’s average payoff of the games is at least $C/n$ for a $n$-player symmetric constant-sum game with a total payoff of $C$.

It is not hard to see that shifting the total payoff of a game by any absolute constant will not alter the strategic aspects of the game. Therefore, without loss of generality, this paper sets a total payoff of $C=0$ and focuses on achieving an equal share in multiplayer symmetric zero-sum games.

## 3 Insufficiency of Equilibria and Self-play for Equal Share

In this section, we demonstrate that existing equilibria notions and the self-play from scratch algorithm are not sufficient to secure an equal share in multiplayer symmetric zero-sum games even under very basic settings. To illustrate this, we consider the following $3$-player *majority vote* game:

###### Example 1 (Three-player majority vote game) .

Every player chooses either 0 0 or $1$. If all players take the same action, then they receive a payoff of 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$.

###### Example 1 (Three-player majority vote game) .

##### Insufficiency of equilibria

In this setup, both pure strategies $(0,0,0)$ and $(1,1,1)$ constitute NE. However, the existence of multiple NEs creates a predicament for the learning agent. It must choose which equilibrium to 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 exist.
Since ${\rm NE}\subset{\rm CE}\subset{\rm CCE}$, we know the same limitation also holds for CE and CCE.

##### Insufficiency of self-play from scratch

Self-play is a 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 $\{x_{t}\}_{t=1}^{T}$. At the $t^{\text{th}}$ iteration, the learner first pretends that all opponents are employing its current strategy $x_{t}$, and samples actions from them. Then the learner updates its own strategy to $x_{t+1}$ using the gradient information from the gameplay. The updates can be made using any optimizer such as gradient descent or Hedge.

Figure: Algorithm 1 Self-play meta-algorithm

Here, we argue that self-play from scratch (the algorithm adopted in Brown & Sandholm ()) again fails to secure an equal share in the same three-player majority vote game: Consider two opponents play the same fixed strategy 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 algorithm is agnostic to the strategies of the opponents, it is doomed to fail. We note that while recent systems (Li et al., ; Jacob et al., ) combine self-play with behavior cloning which is no longer agnostic to opponents’ strategies, our experiment shows that their meta-algorithms remain insufficient to secure an equal share in the worst-case scenario (See Section 6).

## 4 Sufficient Conditions for Securing Equal Share

In this section, we identify the structural conditions of the games where equal share is achievable. We will show that the following two conditions are needed to achieve equal share:

- Condition 1.
All opponents need to deploy the same strategy, i.e., $x_{2}=\ldots=x_{n}$;
- Condition 2.
All opponents must have limited adaptivity and the player has to model the opponents, i.e., $\{x_{j}\}_{j=2}^{n}$ can not adversarially change across different rounds of the game.

We justify these two conditions by proving that without either condition,
an equal share can not be attained in multiplayer symmetric games in the worst case. We remark that both conditions restrict the strategies of opponents rather than the type of games.

##### Non-adaptive opponents that deploy different strategies

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,

$$ $\max_{x_{1}}\min_{x_{2},\cdots,x_{n}}U_{1}(x_{1},\cdots,x_{n})\leq\min_{x_{2}, \cdots,x_{n}}\max_{x_{1}}U_{1}(x_{1},\cdots,x_{n})\leq 0$ (1) $$

where both inequalities can be made strict in certain games.

Here, we can further strengthen the proposition to require opponents to deploy strategies without “collusion”. That is, the hard instance holds even when the strategies employed by opponents are statistically independent without any shared randomness. Proposition 4.1 highlights the challenge when opponents are free to adopt different strategies.

###### Proposition 4.1 .

##### Adaptive opponents that deploy identical strategy

We next examine the case where Condition 1 holds but Condition 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 that they adhere to identical strategy at each round. In math,

$$ $\max_{x_{1}}\min_{x}U_{1}(x_{1},x^{\otimes n-1})\leq\min_{x}\max_{x_{1}}U_{1}( x_{1},x^{\otimes n-1})=0,$ (2) $$

where the inequality can be made strict in certain games.

Proposition 4.2 implies a 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 an equal share.

###### Proposition 4.2 .

##### 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. We conclude from (1) and (2) that, out of the four related minimax concepts, only $\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1})=0$ across all multiplayer symmetric zero-sum games, which guarantees an equal share. This remaining minimax concept precisely corresponds to the two identified conditions where opponents employ identical strategies, and the learner must be adaptive to the opponents. Therefore, we will use $\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1})$ as our target solution concept for this paper to achieve equal share. We remark that *this solution concept does not necessarily correspond to any equilibrium in most multiplayer games*. We conclude with this solution concept from a principled manner with equal share as our primary objective. For conciseness, from now on, we will also refer to the common strategy employed by all opponents as the meta-strategy.

### 4.1 Connections between identified conditions and practice

While the two identified conditions may seem restrictive, here we argue that they in fact apply to practical multiplayer gaming platforms with a large player base. Condition 1 is further implicitly adopted by most prior state-of-the-art AI agents for multiplayer games.

##### Connection to multiplayer games with a large player base

We argue that both identified conditions are
well-justified in modern multiplayer gaming platforms with a large player base.
Imagine a casino hosting $N$ players who randomly join poker tables or an online Mahjong match-making platform with $N$ users.
Let $\{x_{i}\}^{N}_{i=1}$ be the strategy set for these $N$ players.
We can then define the *population meta-strategy* as $\bar{x}=(1/N)\sum_{i=1}^{N}x_{i}$. 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-1$ players who all adopt the same population meta-strategy $\bar{x}$, as long as $N\gg(n-2)^{2}$.

###### Proposition 4.3 .

Let $\mathbb{E}_{x_{-1}}$ be the expectation over the randomness on sampling $n-1$ strategies uniformly from the set $\{x_{i}\}^{N}_{i=1}$ without replacement. Then for any strategy $z\in\Delta(\mathcal{A})$, we have
$|\mathbb{E}_{x_{-1}}[U_{1}(z,x_{-1})]-U_{1}(z,\bar{x}^{\otimes n-1})|\leq 2(n-
2)^{2}/N$.

Furthermore, it is often safe to assume that the population meta-strategy $\bar{x}$ — the average strategy of all players within the player pool — will not quickly adapt to one particular player’s strategy.

###### Proposition 4.3 .

##### Connection to practical AI systems

We remark that a majority of practical AI systems for multiplayer games (Li et al., ; Brown & Sandholm, ; Bakhtin et al., ; † et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al., ) leverage self-play meta-algorithms (Algorithm 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.

## 5 Provably Efficient Algorithms

In this section, we explore efficient algorithms that provably secure an equal share under the two conditions identified in Section 4. Particularly, we consider several opponent settings with various adaptivity: fixed, slowly adapting, and opponents that adapt at intermediate rates.

We use the following notations throughout this section: at round $t$, let $x^{t}$ denote the learner’s strategy, and $y^{t}$ the meta-strategy employed by all opponents. We denote $u^{t}(\cdot)$ as the expected payoff function of the learner at round $t$, where $u^{t}(\cdot):=U_{1}(\cdot,(y^{t})^{\otimes n-1})$. Then the average payoff of the learner is:

$$ $\textstyle{u_{\text{avg}}(T)}:=\textstyle(1/T)\sum^{T}_{t=1}u^{t}(x^{t}).$ $$

### 5.1 Fixed opponents

We begin by exploring the simple stationary scenario, where the meta-strategy used by the opponents remains constant over time, denoted as $y^{t}=y$ for all $t\in[T]$.

Notably, in this particular scenario, the payoff function $u^{t}(\cdot)$ remains constant over time. Additionally, by symmetry, it is not hard to observe that at least one action will consistently yield an expected payoff of 0 in all rounds. This implies $\max_{a\in\mathcal{A}}\sum_{t=1}^{T}u^{t}(a)\geq 0$, which makes the no-regret learning tool well-poised to achieve equal share in this setting. Standard *(static) regret*, defined as follows, compares the learner’s total payoff to the total payoff achieved by the best action in hindsight:

$$ $\textstyle{\text{Reg}(T)}:=\max_{a\in\mathcal{A}}\sum_{t=1}^{T}u^{t}(a)-\sum^{ T}_{t=1}u^{t}(x^{t}),$ $$

An algorithm has *no-regret* if ${\text{Reg}(T)}\leq o(T)$ for all large $T$.
We deploy a standard no-regret learning algorithm — Hedge (Freund & Schapire, ), which provides the following guarantees:

###### Theorem 5.1 (Stationary opponents) .

Let $\{x^{t}\}^{T}_{t=1}$ be the strategy sequence implemented by the Hedge algorithm against stationary opponents. Then, with probability at least $1-\delta$, we have

$$ $\textstyle{u_{\text{avg}}(T)}\geq u^{\star}-C\sqrt{\log(A/\delta)/T},$ $$

for some absolute constant $C$, where $u^{\star}:=\max_{a\in\mathcal{A}}U_{1}(a,y^{\otimes n-1})\geq 0$.

The probability is taken over the random actions by opponents sampled from the meta-strategy(^5^55Recall that our learning protocol in Section 2 assumes the learner only observes the noisy actions of the other players at each round.). Theorem 5.1 claims that with stationary opponents, the Hedge algorithm approximately achieves an equal share up to a $\tilde{O}(1/\sqrt{T})$ error, which demonstrates its effectiveness in the long run.

###### Theorem 5.1 (Stationary opponents) .

### 5.2 Adaptive opponents

In practical scenarios, encountering a fixed opponent strategy 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 scenario, where the meta-strategy $y^{t}$ adopted by the opponents *varies* over time.

According to Proposition 4.2, it is clear that attaining an equal share is impossible if opponents can change their meta-strategy $y^{t}$ arbitrarily fast across different rounds.
Thus we introduce a constraint on the adaptive power of the opponents by positing a variation budget $V_{T}$, which bounds the total variation of the payoff function across the time horizon. Specifically, we assume the payoff function belongs to $\mathcal{U}$, which is defined as

$$ $\textstyle\mathcal{U}:=\left\{\{u^{t}\}^{T}_{t=1}\,\left|\,\sum_{t=1}^{T-1} \left\|u^{t+1}-u^{t}\right\|_{\infty}\leq V_{T}\right.\right\}.$ (3) $$

Furthermore, we denote $\mathcal{G}(n,A,V_{T})$ as the set of tuples, which consists of a $n$-player symmetric zero-sum game with $A$ actions and a corresponding meta-strategy sequence $\{y^{t}\}_{t=1}^{T}$, such that the payoff function $\{u^{t}\}^{T}_{t=1}\in\mathcal{U}$. This constraint effectively moderates the adaptivity of the opponents compared to a fully adversarial setup.

##### Slowly adapting opponents

In non-stationary environments, the total payoff achieved by the best action in hindsight $\max_{a\in\mathcal{A}}\sum_{t=1}^{T}u^{t}(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:

$$ $\textstyle{\text{D-Reg}(T)}:=\sum_{t=1}^{T}\max_{a\in\mathcal{A}}u^{t}(a)-\sum ^{T}_{t=1}u^{t}(x^{t}).$ $$

This measures a strategy’s performance against the best action at each time step (dynamic oracle), providing a more relevant benchmark in changing environments.

In the setting of symmetric games, the dynamic oracle is always assured to secure an equal share, i.e., $\sum_{t=1}^{T}\max_{a\in\mathcal{A}}u^{t}(a)\geq 0$. 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 algorithm—Strongly Adaptive Online Learner with Hedge $\mathcal{H}$ as a black box algorithm ($\mathrm{SAOL}^{\mathcal{H}}$) (See Appendix C.1.2), as proposed by Daniely et al. () to our setting and achieve following guarantees:

###### Theorem 5.2 .

Suppose that $n\geq 3$, $A\geq 2$, and $V_{T}\in[1,T]$, then for any game and any meta-strategy sequence in $\mathcal{G}(n,A,V_{T})$, with probability at least $1-\delta$, $\mathrm{SAOL}^{\mathcal{H}}$ satisfies

$$ $\textstyle{u_{\text{avg}}(T)}\geq u^{\dagger}-CV^{1/3}_{T}T^{-1/3}\left(\sqrt{ \log(A/\delta)}+\log T\right)$ $$

for some absolute constant $C$, where $u^{\dagger}:=(1/T)\sum_{t=1}^{T}\max_{a\in\mathcal{A}}u^{t}(a)\geq 0$.

Theorem 5.2 implies that $\mathrm{SAOL}^{\mathcal{H}}$ achieves a non-negative average payoff, up to an error term that scales with $\tilde{O}(V_{T}^{1/3}T^{-1/3})$.
Therefore, if $V_{T}$ is sublinear in $T$, $\mathrm{SAOL}^{\mathcal{H}}$ is capable of approximately achieving equal share over an extended duration.

###### Theorem 5.2 .

##### Opponents that adapt at intermediate rates

Interestingly, there is an intermediate regime where opponents’ strategies $\{y^{t}\}_{t=1}^{T}$ are changing neither too fast nor too slow where the favorable algorithm for the learner might be simply behavior cloning—simply mimic opponents’ strategies.

Formally, we define the behavior cloning algorithm for the learner 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 $n\geq 3$, $A\geq 2$, and $V_{T}\in[1,T]$, for any game and any meta-strategy sequence in $\mathcal{G}(n,A,V_{T})$,
behavior cloning guarantees that

$$ $\mathbb{E}[{u_{\text{avg}}(T)}]\geq-(V_{T}+1)/T.$ $$

We remark that while the error term $O(V_{T}/T)$ in Theorem 5.3 is always smaller than the error term $\tilde{O}((V_{T}/T)^{1/3})$ in Theorem 5.2, the latter is comparing to the baseline of dynamic oracle $u^{\dagger}$, which has a greater value than the baseline in behavior cloning — 0 0. It is not hard to see that in the intermediate regime $\tilde{\Theta}(u^{\dagger})\leq V_{T}/T\leq\Theta(1)$, the meta-strategy is changing too fast so that it is better for the learner to simply copy the meta-strategy instead of running sophisticated no-dynamic-regret algorithm to learn the game and to counter the meta-strategy by herself.

###### Theorem 5.3 .

##### Matching lower bounds

Finally, we also complement our upper bounds by matching lower bounds showing that $\mathrm{SAOL}^{\mathcal{H}}$ 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 on adapting existing hard instances for a more general setup to the symmetric zero-sum game setting. Please see more discussion in Appendix C.2.

###### Theorem 5.4 .

There exists some absolute constant $C>0$ such that for any $n\geq 3$, $A\geq 2$, and $V_{T}\in[1,T]$, and any learning algorithm, there exists a game and a meta-strategy sequence in $\mathcal{G}(n,A,V_{T})$, such that $\mathbb{E}[{u_{\text{avg}}(T)}]\leq u^{\dagger}-CV^{1/3}_{T}T^{-1/3}$.

###### Theorem 5.5 .

There exists some absolute constant $C>0$ such that for any $n\geq 3$, $A\geq 2$, and $V_{T}\in[1,T]$, and any learning algorithm, there exists a game and a meta-strategy sequence in $\mathcal{G}(n,A,V_{T})$ such that $\mathbb{E}\left[{u_{\text{avg}}(T)}\right]\leq-CV_{T}/T$.

The expectation in both theorems are taking over the random actions by the opponents as well as the possible intrinsic randomness in a stochastic algorithm. Theorem 5.4 and 5.5 match Theorem 5.2 and 5.3 respectively, up to additional logarithmic factors.

###### Theorem 5.4 .

###### Theorem 5.5 .

## 6 Experiments

In this section, we focus on the scenario where one learning agent competes against $n-1$ opponents who play the identical 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 AI 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 opponents?
We design the following two games to compare our algorithm with prior self-play-based algorithms.

##### Majority Vote (MV).

We first consider the standard 3-player majority vote game (Example 1). It is not hard to see that $[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 $p$ and the second action with probability $1-p$. We fix the opponents’ meta-strategy $y_{\text{meta}}=[0.49,0.51]$ for all rounds.

##### Switch Dominance Game (SDG).

In each round, players simultaneously choose an action from the set $\{A,B,C\}$.
Let $n$ be the total number of players and $n_{A}$ be the number of agents choosing action $A$,
We define the game rule as:

$$ $\textstyle\begin{cases}B\succ A\succ C&\text{if }n_{A}>0.2n,\\ C\succ B\succ A&\text{otherwise },\end{cases}$ $$

where the rule $i\succ j\succ k$ intuitively means that action $i$ dominates both $j$ and $k$, and action $j$ dominates $k$. SDG is designed so that $C$ is a *dominated* action when there is a reasonable number of players taking action $A$, but a *dominating* action otherwise. Concretely,
for $i\succ j\succ k$, we assign the following payoff $(r_{i},r_{j},r_{k})$ to players taking actions $(i,j,k)$ respectively, where:

$$ $\displaystyle\textstyle r_{i}$ $\displaystyle=\mathbb{I}[n_{j}+n_{k}>0],\quad r_{j}=\mathbb{I}[n_{k}>0]- \mathbb{I}[n_{j}+n_{k}>0]\cdot n_{i}/(n_{j}+n_{k}),$ $\displaystyle r_{k}$ $\displaystyle=-\mathbb{I}[n_{j}+n_{k}>0]\cdot n_{i}/(n_{j}+n_{k})-\mathbb{I}[n _{k}>0]\cdot n_{j}/n_{k}.$ $$

This payoff design guarantees that SDG is a symmetric zero-sum game. Throughout our experiments, we choose $n=30$ and pick the fixed meta-strategy of the opponents $y_{\text{meta}}=[0.399,0.6,0.001]$ (in the order of action $A,B,C$) for all rounds. Note that while this game has an NE strategy [0, 0, 1], its utility is negative against our chosen meta-strategy $y_{\text{meta}}$.

### 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.e., has direct access to) the meta-strategy $y_{\text{meta}}$ by the opponents.
In this setting, according to Theorem 5.1, our theoretical framework suggests to directly run the Hedge algorithm (Hedge) against opponents who play the meta-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, ); (2) self-play initialized from behavior cloning (SP_BC) (Li et al., ), and (3) self-play initialized from behavior cloning with regularization towards the meta-strategy (SP_BC_reg) (Jacob et al., ).
While these AI systems further implement multi-step lookahead with a few additional techniques, many of them only apply to sequential games, not the basic normal-form games. Here, we focus on the comparison of the high-level game-theoretic meta-algorithms.

##### 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 regularization parameter according to Jacob et al. (). We refer readers to Appendix D for more details.

### 6.2 Results

To answer Q1 and Q2, we evaluate the utility of the learned strategy $\hat{x}$ against the pre-specified meta-strategy $y_{\text{meta}}$, i.e., $U_{1}(\hat{x},y_{\text{meta}}^{\otimes(n-1)})$, as well as the exploitability of the learner $\hat{x}$, i.e., $\min_{y}U_{1}(\hat{x},y^{\otimes(n-1)})$.
To measure the utility, we evaluate the payoff of the agent’s converged strategy by Monte Carlo methods with $3\times 10^{5}$ games and report the mean and standard deviation of 10 runs. As for the exploitability, 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: We report the limiting solution each algorithm converges to within 100 runs, as summarized in Table 1. Our algorithm (Hedge) consistently converges to the good strategy $[0,1]$. All self-play variants have significant probability converge to the bad strategy $[1,0]$, which has a negative utility against the chosen meta-strategy $y_{\text{meta}}=[0.49,0.51]$.

SDG:
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]$.

**Table 1: The distribution of mixed strategies to which different self-play algorithms converge in MV. We use SP_BC_$\lambda$ as the short name of SP_BC_reg with regularization coefficients $\lambda$.**
| Strategy | SP_scratch | SP_BC | SP_BC_$10^{-5}$ | SP_BC_$10^{-4}$ | SP_BC_$10^{-3}$ | SP_BC_$10^{-2}$ | 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 each 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 performance in the worst case.**
| MV | SP_scratch / SP_BC / SP_BC_reg | Hedge |  |
| --- | --- | --- | --- |
| Utility ($\times 10^{-2}$) | -1.00 $\pm$ 0.09 | 1.03 $\pm$ 0.10 |  |
| Exploitability | -1.00 $\pm$ 0.00 | -1.00 $\pm$ 0.00 |  |

##### Utility and Exploitability.

We summarize the results in Table 2, which show that even in these two simple symmetric zero-sum games, none of the self-play algorithms can consistently secure a non-negative payoff, i.e., an equal share, in the worst case. This undesirable behavior persists even without opponents making any adaptations!
Moreover, based on these two games, we further conclude two potential failure modes of self-play algorithms:
(1) For games with multiple NEs, such as MV, self-play methods may converge to different NEs based on different initialization. When the opponents’ meta-strategy (i.e., the initial strategy for SP_BC) lies close to the boundary of the convergence 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 is undesirable against the meta-strategy $y_{\text{meta}}$.
(2) For games with a single NE, self-play algorithms are still very likely to be attracted to this equilibrium. A carefully designed game structure can result in this NE yielding a negative utility against the chosen meta-strategy, and hence jailbreak all self-play variants.
The aforementioned failure modes highlight a significant limitation of self-play variants when being applied to diverse and complex multiplayer games.
In contrast, the principled algorithm according to our theory consistently beats the meta-strategy of the opponents, receives a much higher payoff, and secures an equal share.
Regarding exploitability,
all learned strategies can be easily exploited by adversarial opponents.

## 7 Conclusion

Unlike in the two-player zero-sum games, standard equilibria are no longer always the suitable solution concept for multiplayer games. They are non-unique and lack meaningful guarantees in general scenarios. This paper establishes a new theoretical framework that provides the solution 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.

## Acknowledgement

The authors would like to thank Haifeng Xu for the helpful discussions. This work is supported by Office of Naval Research N00014-22-1-2253.

## Appendix A Extended Preliminaries

### A.1 No-regret learning

No-regret learning is a commonly adopted strategy in game theory to find equilibrium solutions.
We consider a $T$-step learning procedure, where for each round $t\in[T]$: (1) the agent picks a mixed strategy $\mu^{t}$ over $\mathcal{A}$, (2) the environment picks an adversarial loss $\ell_{t}\in[0,1]^{|\mathcal{A}|}$. The expected utility for $t$-th round is defined as $-\langle\mu^{t},\ell_{t}\rangle$. To measure the performance of a particular algorithm, a common approach is to consider regret, where the algorithm’s performance is compared against the single best action in hindsight. Specifically, for policy sequence $(\mu^{1},\ldots,\mu^{T})$ taken by an algorithm, the static regret is given, by

$$ ${\text{Reg}(T)}=\sum_{t=1}^{T}\langle\mu^{t},\ell_{t}\rangle-\min_{a\in \mathcal{A}}\sum^{T}_{t=1}\ell_{t}(a).$ $$

We say that the algorithm is a no-regret algorithm if ${\text{Reg}(T)}=o(T)$. One of such no-regret learning algorithms is Hedge algorithm, which performs the following exponential weight updates:

$$ $\mu^{t+1}(a)\propto\mu^{t}(a)e^{-\eta_{t}\ell_{t}(a)},\quad\text{for}\quad \forall a\in\mathcal{A}.$ $$

where $\eta_{t}$ is the learning rate.
See Algorithm 5 for the Hedge algorithm as applied to our problem setup.

### A.2 3 3 3 3 -player majority and minority game

In this section, we give a 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 $\mathcal{A}:=\{0,1\}$ and the payoff function given by:

$$ $\displaystyle U_{1}(0,0,0)=U_{1}(1,1,1)=0$ $\displaystyle U_{1}(0,1,0)=U_{1}(0,0,1)=U_{1}(1,1,0)=U_{1}(1,0,1)=1/2$ $\displaystyle U_{1}(0,1,1)=U_{1}(1,0,0)=-1.$ $$

In other words, players receive a positive payoff if they are part of the majority and a negative payoff if they are in the minority.
Correspondingly, we define the 3-player *minority game* as a symmetric zero-sum game with action space $\mathcal{A}:=\{0,1\}$ and the payoff function given by:

$$ $\displaystyle U_{1}(0,0,0)=U_{1}(1,1,1)=0$ $\displaystyle U_{1}(0,1,0)=U_{1}(0,0,1)=U_{1}(1,1,0)=U_{1}(1,0,1)=-1/2$ $\displaystyle U_{1}(0,1,1)=U_{1}(1,0,0)=1.$ $$

In other words, players receive a positive payoff if they are part of the minority and a negative payoff if they are in the majority.

## Appendix B Proofs for Section 4

In the sequel, we will prove Proposition 4.1 in Section B.1, Proposition 4.2 in Section B.2 and Propostion 4.3 in Section B.3.

### B.1 Proof of Proposition 4.1

In this section, we will prove (1), where both inequalities can be made strict in certain games.

###### Proof of Proposition 4.1 .

For the first inequality, note that for any $(x_{1},\ldots,x_{n})$:

$$ $\displaystyle U_{1}(x_{1},\cdots,x_{n})\leq\max_{x_{1}}U_{1}(x_{1},\cdots,x_{n }),$ $$

which implies

$$ $\displaystyle\min_{x_{2},\cdots,x_{n}}U_{1}(x_{1},\cdots,x_{n})\leq\min_{x_{2} ,\cdots,x_{n}}\max_{x_{1}}U_{1}(x_{1},\cdots,x_{n}).$ $$

By further taking maximum over $x_{1}\in\Delta(\mathcal{A})$, we prove that

$$ $\displaystyle\max_{x_{1}}\min_{x_{2},\cdots,x_{n}}U_{1}(x_{1},\cdots,x_{n}) \leq\min_{x_{2},\cdots,x_{n}}\max_{x_{1}}U_{1}(x_{1},\cdots,x_{n}).$ $$

To show the first inequality can be strict, we consider the $3$-player majority vote. Suppose $3$ players adopt the mixed strategies $(\alpha_{1},1-\alpha_{1})$, $(\alpha_{2},1-\alpha_{2})$ and $(\alpha_{3},1-\alpha_{3})$, respectively. It then holds that

$$ $\displaystyle U_{1}(x_{1},x_{2},x_{3})$ $\displaystyle=U_{1}(\alpha_{1},\alpha_{2},\alpha_{3})$ $\displaystyle=\alpha_{1}\left(-(1-\alpha_{2})(1-\alpha_{3})+\frac{1}{2}\alpha_ {2}(1-\alpha_{3})+\frac{1}{2}\alpha_{3}(1-\alpha_{2})\right)$ $\displaystyle\quad+(1-\alpha_{1})\left(-\alpha_{2}\alpha_{3}+\frac{1}{2}\alpha _{2}(1-\alpha_{3})+\frac{1}{2}\alpha_{3}(1-\alpha_{2})\right).$ $$

By choosing $\alpha_{2}=\alpha_{3}=0$ when $\alpha_{1}>1/2$ and $\alpha_{2}=\alpha_{3}=1$ when $\alpha_{1}\leq 1/2$, it can be seen that

$$ $\displaystyle\max_{\alpha_{1}}\min_{\alpha_{2},\alpha_{3}}U_{1}(\alpha_{1}, \alpha_{2},\alpha_{3})\leq\max_{\alpha_{1}}\min\{-\alpha_{1},-(1-\alpha_{1})\} =-\frac{1}{2}.$ $$

Note that

$$ $\displaystyle\min_{\alpha_{2},\alpha_{3}}\max_{\alpha_{1}}U_{1}(\alpha_{1}, \alpha_{2},\alpha_{3})$ $\displaystyle=\frac{1}{2}\min_{\alpha_{2},\alpha_{3}}\max\{-2(1-\alpha_{2})(1- \alpha_{3})+\alpha_{2}(1-\alpha_{3})+\alpha_{3}(1-\alpha_{2}),$ $\displaystyle\qquad\qquad\qquad\quad-2\alpha_{2}\alpha_{3}+\alpha_{2}(1-\alpha _{3})+\alpha_{3}(1-\alpha_{2})\}$ $\displaystyle=\frac{1}{2}\min_{\alpha_{2},\alpha_{3}}\max\{3(\alpha_{2}+\alpha _{3})-4\alpha_{2}\alpha_{3}-2,\alpha_{2}+\alpha_{3}-4\alpha_{2}\alpha_{3}\}$ $\displaystyle=0.$ $$

Thus, we show that $\max_{\alpha_{1}}\min_{\alpha_{2},\alpha_{3}}U_{1}(\alpha_{1},\alpha_{2},
\alpha_{3})<\min_{\alpha_{2},\alpha_{3}}\max_{\alpha_{1}}U_{1}(\alpha_{1},
\alpha_{2},\alpha_{3})$, which implies the first inequality can be strict.

For the second inequality, due to a restriction on the minimization constraints, it is straightforward that

$$ $\displaystyle\min_{x_{2},\cdots,x_{n}}\max_{x_{1}}U_{1}(x_{1},\cdots,x_{n}) \leq\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1}).$ $$

In the sequel, we prove $\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1})=0$ via contradiction. Note that by choosing $x_{1}=x$, we can show that

$$ $\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1})\geq 0.$ $$

Suppose for some game inequality holds, then by definition

$$ $\displaystyle\forall x\in\Delta({\mathcal{A}}),\exists x^{\prime}\in\Delta({ \mathcal{A}}),s.t.\ U_{1}(x^{\prime},x,\cdots,x)>0.$ $$

Define the set-valued argmax function $\phi:\Delta({\mathcal{A}})\to 2^{\Delta({\mathcal{A}})}$:

$$ $\displaystyle\phi(x):=\{x^{\prime}\in\Delta({\mathcal{A}})\mid U_{1}(x^{\prime },x,\cdots,x)=\max_{x^{\prime\prime}}U_{1}(x^{\prime\prime},x,\cdots,x)\}.$ $$

We claim that argmax function $\phi(x)$ is:

- •
Always non-empty and convex;
- •
Has a closed graph.

The first property is obvious, so we focus on the second one. Suppose that sequences $\{x_{i}\}$, $\{y_{i}\}$ satisfy $x_{i}\to x$, $y_{i}\to y$ and $y_{i}\in\phi(x_{i})$. Since the payoff function is (Lipschitz) continuous, $\max_{x^{\prime\prime}}U_{1}(x^{\prime\prime},\cdot)$ is continuous by Berge’s maximum theorem. Thus $\max_{x^{\prime\prime}}U_{1}(x^{\prime\prime},x_{i},\cdots,x_{i})$ converges to $\max_{x^{\prime\prime}}U_{1}(x^{\prime\prime},x,\cdots,x)$. Meanwhile $U_{1}(y_{i},x_{i},\cdots,x_{i})$ converges to $U_{1}(y,x,\cdots,x)$. Thus

$$ $\displaystyle U_{1}(y,x\cdots,x)=\lim_{i\to\infty}U_{1}(y_{i},x_{i},\cdots,x_{ i})=\lim_{i\to\infty}\max_{x^{\prime\prime}}U_{1}(x^{\prime\prime},x_{i}, \cdots,x_{i})=\max_{x^{\prime\prime}}U_{1}(x^{\prime\prime},x,\cdots,x).$ $$

This implies $y\in\phi(x)$, and that $\phi$ has a closed graph. Thus by Kakutani’s fixed point theorem, $\exists x^{*}:x^{*}\in\phi(x^{*})$. Now we have

$$ $\displaystyle U_{1}(x^{*},\cdots,x^{*})=\max_{x^{\prime\prime}}U_{1}(x^{\prime \prime},x^{*},\cdots,x^{*})>0,$ $$

which contradicts with the assumption that the game is zero-sum and symmetric. Consequently, we prove the equation. As a result, we have

$$ $\displaystyle\min_{x_{2},\cdots,x_{n}}\max_{x_{1}}U_{1}(x_{1},\cdots,x_{n}) \leq\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1})=0.$ $$

To show the second inequality can be strict, we consider a $3$-player minority game. If the other two players act 0 0 and $1$, respectively, then the learner always receive $-1/2$ payoff, which is strictly less than 0 0. We then finish the proofs.
∎

###### Proof of Proposition 4.1 .

### 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 shown that $\min_{x}\max_{x_{1}}U_{1}(x_{1},x^{\otimes n-1})=0$. Thus, it remains to prove the inequality in (2).

Note that for any $x_{1},x\in\Delta(\mathcal{A})$, we have

$$ $\displaystyle U_{1}(x_{1},x^{\otimes n-1})\leq\max_{x_{1}\in\Delta(\mathcal{A} )}U_{1}(x_{1},x^{\otimes n-1}),$ $$

which implies for any $x_{1}\in\Delta(\mathcal{A})$

$$ $\displaystyle\min_{x\in\Delta(\mathcal{A})}U_{1}(x_{1},x^{\otimes n-1})\leq \min_{x\in\Delta(\mathcal{A})}\max_{x_{1}\in\Delta(\mathcal{A})}U_{1}(x_{1},x^ {\otimes n-1}).$ $$

By further taking maximum over $x_{1}\in\Delta(\mathcal{A})$, we show that

$$ $\displaystyle\max_{x_{1}\in\Delta(\mathcal{A})}\min_{x\in\Delta(\mathcal{A})}U _{1}(x_{1},x^{\otimes n-1})\leq\min_{x\in\Delta(\mathcal{A})}\max_{x_{1}\in \Delta(\mathcal{A})}U_{1}(x_{1},x^{\otimes n-1}).$ $$

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 a mixed strategy $(\beta,1-\beta)$ (i.e. play 0 0 w.p. $\beta$; play $1$ w.p. $1-\beta$). And the two opponents adopt an identical mixed strategy $(p,1-p)$ (i.e. play 0 0 w.p. $p$; play $1$ w.p. $1-p$).
Then, we can calculate the payoff of the learner as $U_{1}(\beta,p,p)=\beta(-(1-p)^{2}+p(1-p))+(1-\beta)(-p^{2}+p(1-p))$.
It then follows that $\max_{\beta\in[0,1]}\min_{p\in[0,1]}U_{1}(\beta,p,p)\leq\max_{\beta\in[0,1]}
\min_{p\in\{0,1\}}U_{1}(\beta,p,p)=-1/2,$
which is strictly less than 0 0. Thus, we finish the proofs.
∎

###### Proof of Proposition 4.2 .

### B.3 Proof of Proposition 4.3

###### Proof of Proposition 4.3 .

Let $\mathbb{P}^{w/o}(i_{1},\ldots,i_{n-1})$ denote the probability of observing $(i_{1},\ldots,i_{n-1})$ when sampling $n-1$ points from $N$ without replacement, and let $\mathbb{P}^{w}(i_{1},\ldots,i_{n-1})$ denote the probability of observing $(i_{1},\ldots,i_{n-1})$ when sampling $n-1$ points from $N$ with replacement. For any $a$, we then have

$$ $\displaystyle\mathbb{E}_{x_{-1}}\left[U_{1}(a,x_{-1})\right]=\sum_{(i_{1}, \ldots,i_{n-1})}\mathbb{P}^{w/o}(i_{1},\ldots,i_{n-1})U_{1}(a,x_{i_{1}},\ldots ,x_{i_{n-1}})$ $\displaystyle U_{1}(a,\bar{x}^{\otimes n-1})=\sum_{(i_{1},\ldots,i_{n-1})} \mathbb{P}^{w}(i_{1},\ldots,i_{n-1})U_{1}(a,x_{i_{1}},\ldots,x_{i_{n-1}}).$ $$

Note that $\|U_{1}\|_{\infty}\leq 1$. Thus, we have

$$ $\displaystyle\left|\mathbb{E}_{x_{-1}}\left[U_{1}(a,x_{-1})\right]-U_{1}(a, \bar{x}^{\otimes n-1})\right|$ $\displaystyle\leq\sum_{(i_{1},\ldots,i_{n-1})}\left|\mathbb{P}^{w/o}(i_{1}, \ldots,i_{n-1})-\mathbb{P}^{w}(i_{1},\ldots,i_{n-1})\right|$ $\displaystyle=\sum_{(i_{1},\ldots,i_{n-1})\text{ has repeated value}}\mathbb{P }^{w}(i_{1},\ldots,i_{n-1})-\mathbb{P}^{w/o}(i_{1},\ldots,i_{n-1})$ $\displaystyle\quad+\sum_{(i_{1},\ldots,i_{n-1})\text{ no repeated value}} \mathbb{P}^{w/o}(i_{1},\ldots,i_{n-1})-\mathbb{P}^{w}(i_{1},\ldots,i_{n-1})$ $\displaystyle=2\sum_{(i_{1},\ldots,i_{n-1})\text{ has repeated value}}\mathbb{ P}^{w}(i_{1},\ldots,i_{n-1})-\mathbb{P}^{w/o}(i_{1},\ldots,i_{n-1})$ $\displaystyle=2\left(1-\frac{N(N-1)\ldots(N-n+2)}{N^{n-1}}\right)$ $\displaystyle=2\left(1-\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right) \ldots\left(1-\frac{n-2}{N}\right)\right)$ $\displaystyle\leq 2\left(1-\left(1-\frac{n-2}{N}\right)^{n-2}\right)$ $\displaystyle\leq\frac{2(n-2)^{2}}{N}.$ $$

∎

###### Proof of Proposition 4.3 .

## Appendix C Proofs for Section 5

In Section C.1, we establish guarantees for the Hedge algorithm, $\mathrm{SAOL}^{\mathcal{H}}$, 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 $\mathrm{SAOL}^{\mathcal{H}}$ by proving Theorem 5.2 in Section C.1.2, and for behavior cloning by proving Theorem 5.3 in 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 $a^{\star}\in{\arg\max}_{a\in\mathcal{A}}U_{1}(\cdot,y^{\otimes n-1})$. We then have

$$ $\displaystyle u^{\star}-\frac{1}{T}\sum^{T}_{t=1}u^{t}(x^{t})$ $\displaystyle=U_{1}(a^{\star},y^{\otimes n-1})-\frac{1}{T}\sum^{T}_{t=1}u^{t}( x^{t})$ $\displaystyle=\underbrace{U_{1}(a^{\star},y^{\otimes n-1})-\frac{1}{T}\sum^{T} _{t=1}U_{1}(a^{\star},a^{t}_{-1})}_{\rm(i)}+\underbrace{\frac{1}{T}\sum^{T}_{t =1}U_{1}(a^{\star},a^{t}_{-1})-\frac{1}{T}\sum^{T}_{t=1}U_{1}(x^{t},a^{t}_{-1} )}_{\rm(ii)}$ $\displaystyle\quad+\underbrace{\frac{1}{T}\sum^{T}_{t=1}U_{1}(x^{t},a^{t}_{-1} )-\frac{1}{T}\sum^{T}_{t=1}u^{t}(x^{t})}_{\rm(iii)}$ $$

For (i), by Hoeffding’s inequality and union bound, we have with probability at least $1-\delta$ that

$$ $\displaystyle{\rm(i)}\leq O(\sqrt{\frac{\log(A/\delta)}{T}})$ $$

For (ii), by Hedge algorithm, we have

$$ $\displaystyle{\rm(ii)}\leq O(\sqrt{\frac{\log(A)}{T}})$ $$

For (iii), note that $\{U_{1}(x^{t},a^{t}_{-1})-u^{t}(x^{t})\}^{T}_{t=1}$ is a martingale difference sequence, thus by Azuma–Hoeffding inequality, we have with probability at least $1-\delta$ that

$$ $\displaystyle{\rm(iii)}\leq O(\sqrt{\frac{\log(1/\delta)}{T}}).$ $$

Combining the above results, we have

$$ $\displaystyle u^{\star}-\frac{1}{T}\sum^{T}_{t=1}u^{t}(x^{t})\leq C\sqrt{\frac {\log(A/\delta)}{T}}$ $$

for some absolute constant $C>0$. Thus we finish the proofs.
∎

###### Proof of Theorem 5.1 .

#### C.1.2 Proof of Theorem 5.2

In this section, we establish guarantees for $\mathrm{SAOL}^{\mathcal{H}}$ when facing adaptive opponents.

The basic idea behind $\mathrm{SAOL}^{\mathcal{H}}$ is to execute $\mathcal{H}$ in parallel over each interval within a carefully selected set. This algorithm dynamically adjusts the weight of each interval based on the previously observed regret. In each round, $\mathrm{SAOL}^{\mathcal{H}}$ selects an interval in proportion to its assigned weight, applies $\mathcal{H}$ to each time slot within this interval, and follows its advice.
Through this mechanism, $\mathrm{SAOL}^{\mathcal{H}}$ achieves a near-optimal performance on every time interval.
We will leverage the strong adaptivity of $\mathrm{SAOL}^{\mathcal{H}}$ in our proofs.

###### Proof of Theorem 5.2 .

Let $\mathcal{I}$ be any fixed interval in $[0,T]$, $a_{0}\in{\arg\max}_{a\in\mathcal{A}}\left\{\sum_{t\in\mathcal{I}}u^{t}(a)\right\}$ and $u^{t,\star}:=\max_{a\in\mathcal{A}}u^{t}(a)$. It holds that

$$ $\displaystyle\sum_{t\in\mathcal{I}}\left(u^{t,\star}-u^{t}(x^{t})\right)$ $\displaystyle=\underbrace{\sum_{t\in\mathcal{I}}\left(u^{t,\star}-u^{t}(a_{0}) \right)}_{\rm(i)}+\sum_{t\in\mathcal{I}}\left(u^{t}(a_{0})-U_{1}(a_{0},a^{t}_{ -1})\right)$ $\displaystyle\quad+\underbrace{\sum_{t\in\mathcal{I}}\left(U_{1}(a_{0},a^{t}_{ -1})-U_{1}(x^{t},a^{t}_{-1})\right)}_{\rm(ii)}+\sum_{t\in\mathcal{I}}\left(U_{ 1}(x^{t},a^{t}_{-1})-u^{t}(x^{t})\right).$ $$

For (i), it can be seen that

$$ $\displaystyle{\rm(i)}=\sum_{t\in\mathcal{I}}\left(u^{t,\star}-u^{t}(a_{0}) \right)\leq|\mathcal{I}|\max_{t\in\mathcal{I}}\left\{u^{t,\star}-u^{t}(a_{0}) \right\}\leq 2V_{\mathcal{I}}|\mathcal{I}|.$ $$

Here the last inequality follows from the following argument:
otherwise there exists $t_{0}\in\mathcal{I}$ such that $u^{t_{0},\star}-u^{t_{0}}(a_{0})>2V_{\mathcal{I}}$. Let $a_{1}\in{\arg\max}_{a\in\mathcal{A}}u^{t_{0}}(a)$. For all $t\in\mathcal{I}$, it then holds that $u^{t}(a_{1})\geq u^{t_{0}}(a_{1})-V_{\mathcal{I}}=u^{t_{0},\star}-V_{\mathcal{
I}}>u^{t_{0}}(a_{0})+V_{\mathcal{I}}\geq u^{t}(a_{0})$. Contradict to the definition of $a_{0}$!

For (ii), we have

$$ $\displaystyle{\rm(ii)}\leq\max_{a\in\mathcal{A}}\sum_{t\in\mathcal{I}}\left(U_ {1}(a,a^{t}_{-1})-U_{1}(x^{t},a^{t}_{-1})\right)\leq C(\sqrt{\log A}+\log T) \sqrt{|\mathcal{I}|},$ $$

where the last inequality follows from Theorem 1 in Daniely et al. ().

Combining the upper bound of (i) and (ii), we have for any fixed interval $\mathcal{I}\subset[0,T]$,

$$ $\displaystyle\sum_{t\in\mathcal{I}}\left(u^{t,\star}-u^{t}(x^{t})\right)$ $\displaystyle\leq 2V_{\mathcal{I}}|\mathcal{I}|+\sum_{t\in\mathcal{I}}\left(u^ {t}(a_{0})-U_{1}(a_{0},a^{t}_{-1})\right)+C(\sqrt{\log A}+\log T)\sqrt{| \mathcal{I}|}$ $\displaystyle\quad+\sum_{t\in\mathcal{I}}\left(U_{1}(x^{t},a^{t}_{-1})-u^{t}(x ^{t})\right).$ $$

We segment the time horizon $T$ into $T/|\mathcal{I}|$ batches $\{\mathcal{I}_{j}\}$ with each length $|\mathcal{I}|$. It then holds for all $j$ that

$$ $\displaystyle\sum_{t\in\mathcal{I}_{j}}\left(u^{t,\star}-u^{t}(x^{t})\right)$ $\displaystyle\leq 2V_{\mathcal{I}_{j}}|\mathcal{I}|+\sum_{t\in\mathcal{I}_{j}} \left(u^{t}(a_{0})-U_{1}(a_{0},a^{t}_{-1})\right)+C(\sqrt{\log A}+\log T)\sqrt {|\mathcal{I}|}$ $\displaystyle\quad+\sum_{t\in\mathcal{I}_{j}}\left(U_{1}(x^{t},a^{t}_{-1})-u^{ t}(x^{t})\right).$ $$

Sum over $j$ gives

$$ $\displaystyle{\text{D-Reg}(T)}$ $\displaystyle\leq 2V_{T}|\mathcal{I}|+\underbrace{\sum^{T}_{t=1}\left(u^{t}(a_ {0})-U_{1}(a_{0},a^{t}_{-1})\right)}_{\rm(iii)}+C(T/\sqrt{|\mathcal{I}|})\cdot (\sqrt{\log A}+\log T)$ $\displaystyle\quad+\underbrace{\sum^{T}_{t=1}\left(U_{1}(x^{t},a^{t}_{-1})-u^{ t}(x^{t})\right)}_{\rm(iv)}.$ $$

For (iii), note that $\{u^{t}(a)-U_{1}(a,a^{t}_{-1})\}^{T}_{t=1}$ is a martingale difference sequence, we have with probability at least $1-\delta$ that

$$ $\displaystyle{\rm(iii)}\leq\max_{a\in\mathcal{A}}\sum^{T}_{t=1}\left(u^{t}(a)- U_{1}(a,a^{t}_{-1})\right)\leq O\left(\sqrt{T\log(A/\delta)}\right),$ $$

where the last inequality follows from Azuma–Hoeffding inequality and union bound.

For (iv), note that $\{U_{1}(x^{t},a^{t}_{-1})-u^{t}(x^{t})\}^{T}_{t=1}$ is a martingale difference sequence, thus by Azuma–Hoeffding inequality, we have with probability at least $1-\delta$ that

$$ $\displaystyle{\rm(iv)}\leq O\left(\sqrt{T\log(1/\delta)}\right).$ $$

Consequently we have with probability at least $1-\delta$ that

$$ $\displaystyle{\text{D-Reg}(T)}\leq 2V_{T}|\mathcal{I}|+C(T/\sqrt{|\mathcal{I}| })\cdot(\sqrt{\log A}+\log T)+O\left(\sqrt{T\log(A/\delta)}\right).$ $$

Choosing $|\mathcal{I}|=(T/V_{T})^{2/3}$, we have with probability at least $1-\delta$ that

$$ $\displaystyle{\text{D-Reg}(T)}\leq O\left(V^{1/3}_{T}T^{2/3}(\sqrt{\log(A/ \delta)}+\log T)\right).$ $$

Finally, by the definition of ${u_{\text{avg}}(T)}$ and $u^{\dagger}$, we show that

$$ $\textstyle{u_{\text{avg}}(T)}\geq u^{\dagger}-CV^{1/3}_{T}T^{-1/3}\left(\sqrt{ \log(A/\delta)}+\log T\right)$ $$

for some absolute constant $C$.

∎

###### Proof of Theorem 5.2 .

#### C.1.3 Proof of Theorem 5.3

In this section, we establish guarantees for behavior cloning when facing adaptive opponents.

Figure: Algorithm 2 Behavior Cloning

###### Proof of Theorem 5.3 .

Note that

$$ $\displaystyle\mathbb{E}\left[\sum^{T}_{t=1}u^{t}(x^{t})\right]$ $\displaystyle\geq-1+\mathbb{E}\left[\sum^{T}_{t=2}u^{t}(x^{t})\right]$ $\displaystyle=-1+\mathbb{E}\left[\sum^{T}_{t=2}U_{1}(a^{t-1}_{2},(y^{t})^{ \otimes n-1})\right]$ $\displaystyle\geq-1-V_{T}-\mathbb{E}\left[\sum^{T}_{t=2}U_{1}(a^{t-1}_{2},(y^{ t-1})^{\otimes n-1})\right]$ (by the defition of $V_{T}$ ) $\displaystyle=-1-V_{T}-\mathbb{E}\left[\sum^{T}_{t=2}U_{1}(y^{t-1},(y^{t-1})^{ \otimes n-1})\right]$ (since $a^{t-1}_{2}\sim y^{t-1}$ ) $\displaystyle=-1-V_{T}$ (since the game is symmetric and zero-sum) $$

Finally, by the definition of ${u_{\text{avg}}(T)}$, we finish the proofs.
∎

###### Proof of Theorem 5.3 .

### C.2 Matching lower bounds

Upon examining Theorem 5.2 alongside Theorem 5.3, it becomes apparent that Theorem 5.2 benchmarks against a more stringent standard (i.e., the dynamic oracle) and incurs a larger error of $V^{1/3}_{T}T^{-1/3}$, while Theorem 5.3 sets its comparison against a baseline metric (i.e., the average payoff) and attains a smaller error of $V_{T}/T$.
Regarding this observation, one might aspire to devise an algorithm whose payoff satisfies: ${u_{\text{avg}}(T)}\geq u^{\dagger}-\tilde{O}(V_{T}/T).$
However, Theorem 5.4 and Theorem 5.5 demonstrate that such a goal is 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 a dynamic regret at least order of $V^{1/3}_{T}T^{2/3}$, closing off the possibility of attaining a better $V_{T}$ rate.
It’s noteworthy that a similar lower bound for dynamic regret has already been established under broader conditions Besbes et al. (). 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 $\mathrm{SAOL}^{\mathcal{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 0. The guarantees achieved by Theorem 5.3 can not be improved in 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

$$ $\displaystyle U^{(3)}_{1}(a,b,c):=\begin{cases}\text{payoff for $3$-player majority game}&\text{if }a,b,c\in\{0,1\}\\ -1&\text{if }a\notin\{0,1\},b,c\in\{0,1\}\\ \text{defined by symmetric}&\text{o.w.}\end{cases}$ $$

which is basically the payoff function for $3$-player majority game with extra dummy actions.
We then define

$$ $\displaystyle U^{(n)}_{1}(a,a_{2},\ldots,a_{n}):=\frac{1}{(n-1)(n-2)}\sum_{2 \leq i\neq j\leq n}U_{1}^{(3)}(a,a_{i},a_{j}).$ $$

We consider a game that evolves stochastically, with $n$ players, action space $\mathcal{A}=\{0,1,\ldots,A-1\}$, and the payoff function of the first player given by $U_{1}^{(n)}$.
We segment the decision horizon $T$ into $T/\Delta_{T}$ batches $\{\mathcal{T}_{j}\}$, with each batch comprising $\Delta_{T}$ episodes.
We consider two distinct scenarios:

- •
Case1: All the other players employ a mixture strategy $(1/2-\epsilon,1/2+\epsilon)$ (i.e., playing 0 with probability $1/2-\epsilon$, playing 1 with probability $1/2+\epsilon$);
- •
Case 2: All the other players employ a mixture strategy $(1/2+\epsilon,1/2-\epsilon)$ (i.e., playing 0 with probability $1/2+\epsilon$, playing 1 with probability $1/2-\epsilon$);

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/\Delta_{T}$ represent total number of batches.
We fix some algorithm and a batch $j\in\{1,\ldots,m\}$.
Let $\delta_{j}\in\{1,2\}$ indicate batch $j$ belongs to Case1 or Case2. We denote by $\mathbb{P}^{j}_{\delta_{j}}$ the probability distribution conditioned on batch $j$ belongs to Case $\delta_{j}$, and by $\mathbb{P}_{0}$ the probability distribution when all the other players employ a mixture strategy $(1/2,1/2)$. We further denote by $\mathbb{E}^{j}_{\delta_{j}}[\cdot]$ and $\mathbb{E}_{0}[\cdot]$ the corresponding expectations.
We denote by $N^{j}_{a}$ the number of times action $a$ was played in batch $j$. If the batch $j$ belongs to Case $\delta_{j}$, then the optimal action in the batch is $-\delta_{j}+2$.
We first present a useful lemma.

###### Lemma C.1 .

Let $f:\{-1,0,1/2\}^{|\mathcal{T}_{j}|\times A}\rightarrow[0,M]$ be any bounded real function defined on the payoff matrices $R$. Then, for any $\delta_{j}\in\{1,2\}$, ${\epsilon}\leq 1/4$:

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}[f(R)]-\mathbb{E}_{0}[f(R)]\leq\frac{M }{2}\sqrt{-2|\mathcal{T}_{j}|\ln\left(1-4{\epsilon}^{2}\right)}\leq 2M{ \epsilon}\sqrt{\Delta_{T}}.$ $$

By Lemma C.1 with $f=N^{j}_{-\delta_{j}+2}$, we have

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}[N^{j}_{-\delta_{j}+2}]-\mathbb{E}_{0} [N^{j}_{-\delta_{j}+2}]\leq 2{\epsilon}|\mathcal{T}_{j}|\sqrt{\Delta_{T}}.$ (4) $$

Note that

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}[u^{t}(x^{t})]$ $\displaystyle=-\mathbb{P}^{j}_{\delta_{j}}(x^{t}\notin\{0,1\})+(-{\epsilon}-2{ \epsilon}^{2})\mathbb{P}^{j}_{\delta_{j}}(x^{t}=\delta_{j}-1)+({\epsilon}-2{ \epsilon}^{2})\mathbb{P}^{j}_{\delta_{j}}(x^{t}=-\delta_{j}+2)$ $\displaystyle\leq(-{\epsilon}-2{\epsilon}^{2})\mathbb{P}^{j}_{\delta_{j}}(x^{t }\neq-\delta_{j}+2)+({\epsilon}-2{\epsilon}^{2})\mathbb{P}^{j}_{\delta_{j}}(x^ {t}=-\delta_{j}+2)$ $\displaystyle=-{\epsilon}-2{\epsilon}^{2}+2{\epsilon}\cdot\mathbb{P}^{j}_{ \delta_{j}}(x^{t}=-\delta_{j}+2),$ $$

therefore,

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}\left[\sum_{t\in\mathcal{T}_{j}}u^{t}( x^{t})\right]$ $\displaystyle\leq(-{\epsilon}-2{\epsilon}^{2})|\mathcal{T}_{j}|+2{\epsilon} \cdot\mathbb{E}^{j}_{\delta_{j}}[N^{j}_{-\delta_{j}+2}]$ $\displaystyle\leq(-{\epsilon}-2{\epsilon}^{2})|\mathcal{T}_{j}|+2{\epsilon} \cdot\mathbb{E}^{j}_{0}[N^{j}_{-\delta_{j}+2}]+4{\epsilon}^{2}|\mathcal{T}_{j} |\sqrt{\Delta_{T}}.$ (by ( 4 )) $$

Consequently, we have

$$ $\displaystyle\frac{1}{2}\mathbb{E}^{j}_{1}\left[\sum_{t\in\mathcal{T}_{j}}u^{t }(x^{t})\right]+\frac{1}{2}\mathbb{E}^{j}_{2}\left[\sum_{t\in\mathcal{T}_{j}}u ^{t}(x^{t})\right]\leq(-{\epsilon}-2{\epsilon}^{2})|\mathcal{T}_{j}|+{\epsilon }|\mathcal{T}_{j}|+4{\epsilon}^{2}|\mathcal{T}_{j}|\sqrt{\Delta_{T}}.$ (5) $$

It then holds that

$$ $\displaystyle\mathbb{E}_{{\text{Alg}}}\left[\sum^{m}_{j=1}\sum_{t\in\mathcal{T }_{j}}u^{t}(x^{t})\right]$ $\displaystyle=\sum^{m}_{j=1}\mathbb{E}_{{\text{Alg}}}\left[\sum_{t\in\mathcal{ T}_{j}}u^{t}(x^{t})\right]$ $\displaystyle=\sum^{m}_{j=1}\mathbb{E}_{{\text{Alg}}}\left[\frac{1}{2}\mathbb{ E}^{j}_{1}\left[\sum_{t\in\mathcal{T}_{j}}u^{t}(x^{t})\right]+\frac{1}{2} \mathbb{E}^{j}_{2}\left[\sum_{t\in\mathcal{T}_{j}}u^{t}(x^{t})\right]\right]$ $\displaystyle\leq\sum^{m}_{j=1}((-{\epsilon}-2{\epsilon}^{2})|\mathcal{T}_{j}| +{\epsilon}|\mathcal{T}_{j}|+4{\epsilon}^{2}|\mathcal{T}_{j}|\sqrt{\Delta_{T}})$ $\displaystyle=-2{\epsilon}^{2}T+4{\epsilon}^{2}T\sqrt{\Delta_{T}}.$ $$

Set ${\epsilon}=\min\{1/(8\sqrt{\Delta_{T}}),V_{T}\Delta_{T}/T\}$. We then have

$$ $\displaystyle\mathbb{E}_{{\text{Alg}}}[{\text{D-Reg}(T)}]$ $\displaystyle=({\epsilon}-2{\epsilon}^{2})T-\mathbb{E}_{{\text{Alg}}}\left[ \sum^{T}_{t=1}u^{t}(x^{t})\right]$ $\displaystyle\geq({\epsilon}-2{\epsilon}^{2})T-(-2{\epsilon}^{2}T+4{\epsilon}^ {2}T\sqrt{\Delta_{T}})$ $\displaystyle={\epsilon}T-4{\epsilon}^{2}T\sqrt{\Delta_{T}}$ $\displaystyle={\epsilon}T(1-4{\epsilon}\sqrt{\Delta_{T}})$ $\displaystyle\geq\frac{1}{2}{\epsilon}T$ $\displaystyle=\frac{1}{2}\min\left\{\frac{1}{8\sqrt{\Delta_{T}}},\frac{V_{T} \Delta_{T}}{T}\right\}T.$ $$

Choosing $\Delta_{T}=(T/V_{T})^{2/3}$, we then have

$$ $\displaystyle\mathbb{E}_{{\text{Alg}}}[{\text{D-Reg}(T)}]\geq CV_{T}^{1/3}T^{2 /3}.$ $$

Recall the definition of ${u_{\text{avg}}(T)}$ and $u^{\dagger}$, we then finish the proofs.
∎

We prove Lemma C.1 in the following.

###### Proof of Lemma C.1 .

We have that

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}[f(R)]-\mathbb{E}_{0}[f(R)]$ $\displaystyle=\sum_{R}f(R)\left(\mathbb{P}^{j}_{\delta_{j}}(R)-\mathbb{P}_{0}( R)\right)$ $\displaystyle\leq\sum_{R:\mathbb{P}^{j}_{\delta_{j}}(R)\geq\mathbb{P}_{0}(R)}f (R)\left(\mathbb{P}^{j}_{\delta_{j}}(R)-\mathbb{P}_{0}(R)\right)$ $\displaystyle\leq M\sum_{R:\mathbb{P}^{j}_{\delta_{j}}(R)\geq\mathbb{P}_{0}(R) }\left(\mathbb{P}^{j}_{\delta_{j}}(R)-\mathbb{P}_{0}(R)\right)$ $\displaystyle=\frac{M}{2}\|\mathbb{P}^{j}_{\delta_{j}}-\mathbb{P}_{0}\|_{\rm TV}$ $\displaystyle\leq\frac{M}{2}\sqrt{2{\sf KL}(\mathbb{P}_{0}\ \|\ \mathbb{P}^{j} _{\delta_{j}})},$ (6) $$

where the last ineqaulity follows from Pinsker’s inequality.
Let $R_{t}\in\mathbb{R}^{A}$ be a random vector denoting the payoff for each action at time $t$, and let $R^{t}\in\mathbb{R}^{t\times A}$ denote the payoff matrix received upon time $t$: $R^{t}=[R_{1},\ldots,R_{t}]^{T}$.
By the chain rule for the relative entropy, we have

$$ $\displaystyle{\sf KL}(\mathbb{P}_{0}\ \|\ \mathbb{P}^{j}_{\delta_{j}})=\sum^{| \mathcal{T}_{j}|}_{t=1}\mathbb{E}_{R^{t-1}}\left[{\sf KL}\left(\mathbb{P}_{0}( R_{t}\mid R^{t-1})\ \|\ \mathbb{P}^{j}_{\delta_{j}}(R_{t}\mid R^{t-1})\right) \right].$ (7) $$

Note that

$$ $\displaystyle\mathbb{P}_{0}(R_{t}=[-1,0,-1,\ldots,-1]\mid R^{t-1})=\mathbb{P}_ {0}(R_{t}=[0,-1,-1,\ldots,-1]\mid R^{t-1})=1/4$ $\displaystyle\mathbb{P}_{0}(R_{t}=[1/2,1/2,-1,\ldots,-1]\mid R^{t-1})=1/2.$ $$

In the case $\delta_{j}=1$, we have

$$ $\displaystyle\mathbb{P}^{j}_{\delta_{j}}(R_{t}=[-1,0,-1,\ldots,-1]\mid R^{t-1} )=(1/2+{\epsilon})^{2}$ $\displaystyle\mathbb{P}^{j}_{\delta_{j}}(R_{t}=[0,-1,-1,\ldots,-1]\mid R^{t-1} )=(1/2-{\epsilon})^{2}$ $\displaystyle\mathbb{P}^{j}_{\delta_{j}}(R_{t}=[1/2,1/2,-1,\ldots,-1]\mid R^{t -1})=2(1/2+{\epsilon})(1/2-{\epsilon}).$ $$

In the case $\delta_{j}=2$, we have

$$ $\displaystyle\mathbb{P}^{j}_{\delta_{j}}(R_{t}=[-1,0,-1,\ldots,-1]\mid R^{t-1} )=(1/2-{\epsilon})^{2}$ $\displaystyle\mathbb{P}^{j}_{\delta_{j}}(R_{t}=[0,-1,-1,\ldots,-1]\mid R^{t-1} )=(1/2+{\epsilon})^{2}$ $\displaystyle\mathbb{P}^{j}_{\delta_{j}}(R_{t}=[1/2,1/2,-1,\ldots,-1]\mid R^{t -1})=2(1/2+{\epsilon})(1/2-{\epsilon}).$ $$

Thus, we have

$$ $\displaystyle{\sf KL}\left(\mathbb{P}_{0}(R_{t}\mid R^{t-1})\ \|\ \mathbb{P}^{ j}_{\delta_{j}}(R_{t}\mid R^{t-1})\right)$ (8) $\displaystyle=$ $\displaystyle\frac{1}{4}\ln\frac{1/4}{(1/2+{\epsilon})^{2}}+\frac{1}{4}\ln \frac{1/4}{(1/2-{\epsilon})^{2}}+\frac{1}{2}\ln\frac{1/2}{2(1/2+{\epsilon})(1/ 2-{\epsilon})}$ $\displaystyle=$ $\displaystyle-\ln\left(1-4{\epsilon}^{2}\right).$ (9) $$

Combining (C.2.1), (7) and (8), we have

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}[f(R)]-\mathbb{E}_{0}[f(R)]\leq\frac{M }{2}\sqrt{-2|\mathcal{T}_{j}|\ln\left(1-4{\epsilon}^{2}\right)}.$ $$

If we further have ${\epsilon}\leq 1/4$, it then holds that $-\ln\left(1-4{\epsilon}^{2}\right)\leq 16\ln(4/3){\epsilon}^{2}$ and consequently

$$ $\displaystyle\mathbb{E}^{j}_{\delta_{j}}[f(R)]-\mathbb{E}_{0}[f(R)]\leq\frac{M }{2}\sqrt{-2|\mathcal{T}_{j}|\ln\left(1-4{\epsilon}^{2}\right)}\leq 2M{ \epsilon}\sqrt{|\mathcal{T}_{j}|}\leq 2M{\epsilon}\sqrt{\Delta_{T}}.$ $$

∎

###### Proof of Theorem 5.4 .

###### Lemma C.1 .

###### Proof of Lemma C.1 .

#### C.2.2 Proof of Theorem 5.5

###### Proof of Theorem 5.5 .

We consider a game that evolves stochastically, with $n$ players, action space $\mathcal{A}=\{0,1,\ldots,A-1\}$, and the same payoff function $U^{(n)}_{1}$ as outlined in Theorem 5.4.
We segment the decision horizon $T$ into $T/\Delta_{T}$ batches $\{\mathcal{T}_{j}\}$, with each batch comprising $\Delta_{T}$ episodes.
We consider two distinct scenarios:

- •
Case1: All the other players play 0;
- •
Case 2: All the other players play 1.

In Case 1, we have $u^{t}(0)=0$ and $u^{t}(a)=-1$ for all $a\neq 0$. In Case 2, we have $u^{t}(1)=0$ and $u^{t}(a)=-1$ for all $a\neq 1$.
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/\Delta_{T}$ represent total number of batches.
We fix some algorithm.
Let $\delta_{j}\in\{1,2\}$ indicate batch $j$ belongs to Case1 or Case2. We denote by $\mathbb{P}^{j}_{\delta_{j}}$ the probability distribution conditioned on batch $j$ belongs to Case $\delta_{j}$, and by $\mathbb{E}^{j}_{\delta_{j}}[\cdot]$ the corresponding expectation.
It then holds that

$$ $\displaystyle\mathbb{E}_{{\text{Alg}}}\left[\sum^{m}_{j=1}\sum_{t\in\mathcal{T }_{j}}u^{t}(x^{t})\right]$ $\displaystyle=\sum^{m}_{j=1}\mathbb{E}_{{\text{Alg}}}\left[\sum_{t\in\mathcal{ T}_{j}}u^{t}(x^{t})\right]$ $\displaystyle=\sum^{m}_{j=1}\mathbb{E}_{{\text{Alg}}}\left[\frac{1}{2}\mathbb{ E}^{j}_{1}\left[\sum_{t\in\mathcal{T}_{j}}u^{t}(x^{t})\right]+\frac{1}{2} \mathbb{E}^{j}_{2}\left[\sum_{t\in\mathcal{T}_{j}}u^{t}(x^{t})\right]\right]$ $\displaystyle\leq\sum^{m}_{j=1}\mathbb{E}_{{\text{Alg}}}\left[\frac{1}{2} \mathbb{E}^{j}_{1}\left[u^{t^{j,1}}(x^{t^{j,1}})\right]+\frac{1}{2}\mathbb{E}^ {j}_{2}\left[u^{t^{j,1}}(x^{t^{j,1}})\right]\right],$ $$

where $t^{j,1}$ represents the first episode of batch $j$ and the inequality follows from the fact that $u^{t}\leq 0$. Note that

$$ $\displaystyle\frac{1}{2}\mathbb{E}^{j}_{1}\left[u^{t^{j,1}}(x^{t^{j,1}})\right ]+\frac{1}{2}\mathbb{E}^{j}_{2}\left[u^{t^{j,1}}(x^{t^{j,1}})\right]$ $\displaystyle=-\frac{1}{2}\left(\mathbb{P}^{j}_{1}(x^{t^{j,1}}\neq 0)+\mathbb{ P}^{j}_{2}(x^{t^{j,1}}\neq 1)\right)$ $\displaystyle=-\frac{1}{2}\left(\mathbb{P}(x^{t^{j,1}}\neq 0)+\mathbb{P}(x^{t^ {j,1}}\neq 1)\right)\leq-\frac{1}{2},$ $$

where the second equation follows from the fact that $x^{t^{j,1}}$ is independent of $\delta_{j}$. Thus, we have

$$ $\displaystyle\mathbb{E}_{{\text{Alg}}}\left[\sum^{m}_{j=1}\sum_{t\in\mathcal{T }_{j}}u^{t}(x^{t})\right]\leq-\frac{m}{2}=-\frac{T}{2\Delta_{T}}.$ $$

Choosing $\Delta_{T}=T/V_{T}$, we have

$$ $\displaystyle\mathbb{E}_{{\text{Alg}}}\left[\sum^{m}_{j=1}\sum_{t\in\mathcal{T }_{j}}u^{t}(x^{t})\right]\leq-V_{T}/2.$ $$

Recall the definition of ${u_{\text{avg}}(T)}$, we then finish the proofs.
∎

###### Proof of Theorem 5.5 .

## Appendix D Experiments Details

In this section, we provide additional details for our experiments.

### D.1 Algorithms

We refer readers to Algorithm 3-6 for detailed implementation of algorithms in the experiment. For MV, we choose $\eta=1$. For SDG, we choose $\eta=2$.

Figure: Algorithm 3 Self-Play

Figure: Algorithm 4 Self-Play with Regularization

Figure: Algorithm 5 Hedge

Figure: Algorithm 6 Exploiter for strategy $x$

### D.2 Computation Resources

The experiments are conducted on a server with 256 CPUs. Each experiment can be completed in a few minutes.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: No.
soundness: 3
strengths: The mult-player constant sum game is of great interests to practice, and the strength of this paper paper lies in its conceptual contribution.
summary: The paper considers multiplayer symmetric constant-sum games, focusing on achieving equal share - where a player secures an expected payoff of $C/n$ in an n-player game with total payoff $C$. This work is particularly relevant for games like Mahjong, Poker, and Diplomacy, where traditional two-player zero-sum game theory falls short.

The paper makes serveral theoretical contributions. First, they identify two conditions for achieving equal share (over the worst case): all opponents must deploy the same strategy, and they must have limited adaptivity while being modeled by the learning agent. 

For fixed opponents, they employ the Hedge algorithm; for slowly adapting opponents, they introduce the SAOL_H algorithm; and for intermediately adapting opponents, they utilize behavior cloning. Importantly, they provide matching lower bounds that demonstrate their algorithms are near optimal.

---------
Post rebuttal: I have read the author's rebuttal. My concerns on the technical novelty remains (this is also observed by other reviewers). I still think the paper studies an interesting topic.
weaknesses: 1. The technique is not strong, seems to be a natural modificaiton to the existing (adaptive) online learning algorithm.


Minor issue: Some of the the most up to date (and the state-of-art) literature on hardness of NE and no-regret learning in games:

[1] Inapproximability of Nash equilibrium, Aviad Rubinstein. STOC'15.
(This paper gave the best hardness result for NE)

[2] Fast swap regret minimization and applications to approximate correlated equilibria. Binghui Peng, Aviad Rubinstein. STOC'24

[3] From External to Swap Regret 2.0: An Efficient Reduction for Large Action Spaces. Yual Dagan, Constantinos Daskalakis, Max Fishelson, Noah Golowich. STOC 2024

These two papers gave the best algorithm for learning in normal-form/extensive-form games.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: My questions are related to the weaknesses highlighted above --

1. To what extent are the ideas in the result about dynamic regret different from prior work in this area. Is there something specific to symmetric games (such as faster convergence) that is explored in the paper? Is there a reason that results about dynamic regret do not directly imply Theorem 5.2.

2. Does it make sense to compare self-play to no-regret (and variants) given that the two frameworks (as set up in the paper) get to see different levels of information? For example, if the experiments adversarially pick the opponent strategy based on the result of self-play, then the comparison is trivial since we would then be comparing playing first (self-play) versus best-responding while playing second (no-regret).
soundness: 4
strengths: The main strength of the paper is coming up with a simple and compelling framework to study learning in n-player symmetric games. The paper has some clean results showing that the minimax theorem and variants do not hold in multiplayer symmetric games and uses this to place some reasonable restrictions on opponent behavior. In particular, the paper introduces some exemplar multiplayer symmetric games, such as the majority/ minority vote game, which demonstrate useful properties that provide insight into the nature of equilibria and best-responses in multiplayer symmetric games. The results related to these parts

Another strength of the paper is in coming up with a natural setting (where opponents are drawn from a large population) to justify working with the condition that all opponents behave identically.

The paper establishes matching upper and lower bounds for payoffs in the online learning setting -- for different regimes based on how swiftly the opponent's strategy and the resulting environment is changing. In particular, the lower bounds extend previous results about general multiplayer games to the special case of symmetric games.
summary: The paper studies n-player symmetric constant-sum games, specifically how an agent can guarantee themselves a 1/n- fraction, i.e. "equal share" of the total payoff.  They identify conditions under which a learner can guarantee themselves this equal share against (n-1) opponents. The paper also studies various no-regret algorithms that can guarantee equal share under these conditions and compares their performance to self-play based meta-learners.

They identify two conditions necessary for a single player, called the learner, to learn a strategy that gives them their equal share in a repeated interaction - 
1. All the other (n-1) players, called the opponents, must deploy the same strategy
2. The opponents must have limited adaptivity over the rounds of play

The first condition is shown via analyzing the one-shot version of the game and showing that the minimax theorem does not hold in symmetric n-player constant sum games. This condition is justified by studying the game against opponents drawn from a large random population. The second condition is additionally required to show that strongly adaptive no-regret algorithms achieve small dynamic regret against opponents with limited adaptivity. For intermediate rates of adaptivity, the paper also studies the payoff obtained by mimicking the identical opponents. The final theoretical result is to show matching lower bounds for dynamic regret.

The paper also experimentally compares the performance of these algorithms against that of existing self-play based frameworks.
weaknesses: There are two main weaknesses in my view:

1. One of the main technical results in the paper is about dynamic regret bounds against opponents with limited adaptivity in changing their strategies (and consequently the online optimization environment they induce). To what extent are the ideas in this result different from prior work in this area - is there something specific to symmetric games (such as faster convergence) that is explored in the paper? More broadly, this raises a concern about the technical depth and significance of the results.
 
2. I do not understand the comparison to self-play. If I understand correctly, self-play is used to come up with a static strategy (via playing copies of the learner) that is then tested against a particular benchmark strategy for the (n-1) opponents. Importantly, the self-play process does not get to see the opponents' strategy while learning. On the other hand, the no-regret algorithms get to see the opponents' strategy, either fixed or slowly changing, and are allowed to adapt to this strategy. I'm not sure how meaningful this comparison is, since it does not appear to compare the same shape of object.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: I have no further questions.
soundness: 3
strengths: Identifying reasonable solution concepts beyond two-player zero-sum games has been a major challenge in game theory. Common solution concepts, such as Nash equilibria and correlated equilibria, have many deficiencies, and so attempting to explore different concepts that overcome those issues is certainly a fruitful research direction. The paper contributes to this line of work by proposing a natural objective, described above, which appears to be novel in its current form. Further, the authors provide necessary and sufficient conditions under which that solution concept can be attained. The conditions are very interpretable and natural, and provide a theoretical framework to design principled algorithms in practice. It is plausible that the approach of the paper can guide the performance of systems in practice. The paper is generally well-written, and all claims appear to be sound. The scope of the paper would also make it a good fit for a conference such as ICLR.
summary: The paper considers multi-player symmetric zero-sum games, a class which captures many games from realistic applications. In light of the deficiencies of existing solution concepts in such games, the paper proposes a new solution concept, namely equal share---a player must secure a utility or 0. They proceed by identifying sufficient and necessary conditions under which equal share is attainable. Experiments are also conducted to highlight some of the theoretical results.
weaknesses: On the negative side, my main concern is about the novelty of the results. First, all the observations made in the paper (Section 3 and in part Section 6) about the other solution concepts and the self-play framework are well-known and immediate. It is clear that one can devise simple examples where common solution concepts fail in terms of the objective put forward by the paper. The more interesting question, in my opinion, is why the self-play framework performs that well in games such as multi-player poker despite those obvious deficiencies. In terms of the conditions identified in the paper in order to achieve equal share, it is again fairly immediate to see that there are necessary and sufficient. In particular, when the opponents are not fully adaptive, most of the positive results obtained in Section 5 follow readily from existing results in the literature on dynamic regret. As to whether equal share is a reasonable objective, I don't believe there is a definite answer. The fact that it does not correspond to an equilibrium is an obvious concern, but I understand that going beyond equilibrium will be necessary to make progress in this line of work. Overall, I believe that the technical contributions of the paper do not go far enough compared to existing results to merit acceptance.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: no.
soundness: 3
strengths: They rigorously identify the theoretical conditions under which achieving an equal share is tractable.
summary: This paper examines multiplayer symmetric constant-sum games with more than two players in a competitive setting. 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 addresses these challenges by focusing on the minmax strategy and  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. They 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.
weaknesses: The significance of the contribution is limited. 

1) The so-called suitable solution concept for learning in multiplayer games is a minimax strategy, which is not new.

2) This paper mentioned that symmetric games are popular in practice, however, the large games mentioned in this paper are not symmetric. Please give more detailed real-world cases.

3) This paper mentioned that all asymmetric games can be converted to symmetric games. More details should be given, especially how the results in this paper can be used in all asymmetric games.

4) This paper shows that the equal share can be secured under two conditions, making a multiplayer game equivalent to a two-player zero-sum game with the opponent fixed.  This case is trivial for securing an equal share. As two-player zero-sum games have been studied well, then the following algorithm is trivial. 

These results may not help solve general multiplayer games.

Meta-review: The paper proposes a framework for multiplayer symmetric constant-sum games by introducing the concept of equal share, where a player secures an expected payoff of C/n in an n-player game with total payoff C. The reviewers generally found the problem well-motivated and welcomed work in this space. However, there was a consistent sentiment that the technical contributions and experimental comparisons lacked sufficient novelty and depth to merit acceptance at this stage.

All reviewers appreciated the effort to move beyond equilibrium-based methods, which have limitations in multiplayer games. Reviewer 5Z1z noted that the paper “contributes to this line of work by proposing a natural objective,” while reviewer sdNv described the conceptual contribution as a “strength of the paper.” However, multiple reviewers, including 5Z1z and sS4W, expressed concerns about the novelty of the technical results. Reviewer sS4W questioned, “To what extent are the ideas in the result about dynamic regret different from prior work in this area?” Similarly, reviewer sdNv remarked that the techniques seem “a natural modification to the existing (adaptive) online learning algorithms.” The authors included in their general answer, a rebuttal of the novelty concerns, but the reviewers did not change their mind.

The experimental results also drew mixed reactions. Reviewer sS4W appreciated the worst-case analysis highlighting the limitations of self-play but critiqued the fairness of the comparison, stating, “I’m not sure how meaningful this comparison is, since it does not appear to compare the same shape of object.” Reviewer Yqqg raised concerns about the broader applicability of the results, remarking that “these results may not help solve general multiplayer games.” The authors provided a response, but the reviewer maintained a negative opinion. 

Ultimately, while reviewers recognized the potential of the proposed framework, the paper’s current scope and contributions were deemed insufficient for acceptance. Reviewer 5Z1z summarized this sentiment by stating, “the technical contributions of this paper do not go far enough.”

Decision: Reject