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

Thank you for your inspiring comments. We address your concerns as follows.

Q1: Novelty and contributions

A1: Please refer to A1 to Reviewer Ada2 for clarification on the novelty and technical contribution of our work.

Q2: Extension to asymmetric games

A2: As mentioned on page 4, L184-186 (left column), we can effectively transform all asymmetric games into symmetric ones by introducing an initial stage where each player’s position is randomly assigned. This randomization process effectively symmetrizes the game, as each player has an equal probability of assuming any role, ensuring that no player has a consistent positional advantage. Therefore, under this transformed setting, our analysis remains applicable.

To further clarify the mathematical transformation, we enlarge the action space to incorporate both the player's position and their actions. Specifically, for each player $i$, we define $(P_i, a_i)$ where $P_i$ represents the player's position or role in the game, and $a_i$ denotes their action. We then define a symmetric utility function $U^{sym}_i$ as follows:

$U^{sym}_i ((P_1, a_1), \ldots, (P_n, a_n))$

$:=U_{\sigma^{-1}(i)}^{asym} (a_{\sigma^{-1}(1)}, \ldots, a_{\sigma^{-1}(n)}),$

where $\sigma$ is a permutation that reorders player positions such that $\sigma(P_1, \ldots, P_n) = (1, \ldots, n)$.
The action space is defined as $\bigcup_{j=1}^n (P_j \times \mathcal{A}_j)$, where $\mathcal{A}_j$ denotes the set of actions available to players when they are in position or role $P_j$.
This transformation aligns the players' positions with a standardized symmetric framework, enabling our analysis to apply to games that are asymmetric by nature but can be symmetrized under random initial positioning.

Thanks a lot for reading our paper and for your insightful comments.

Q1: The theoretical results are not surprising

A1: Novelty. We remark that, compared to developing complex algorithmic techniques, identifying and formulating the right question to solve is equally—if not more—important. This paper precisely addresses the latter: propose novel, practical, and important formulations, study basic properties, and bring the right tools to give principled solutions in a variety of settings.

In multiplayer games, much of the existing research has focused on achieving equilibrium-based outcomes. While extensively studied, equilibrium-based approaches have well-known limitations and are often unsuitable for developing AI agents in multiplayer settings. This concern was explicitly raised in prior work on real-world multiplayer game systems (e.g., Brown & Sandholm, 2019); however, such works do not resolve the issue or propose alternative objectives. Our paper is the first to formulate the problem as achieving equal share, and to clarify that the objective is theoretically well-behaved only under the condition that all opponents deploy identical strategies. While this condition seems strong, we justify its practical relevance and note that it aligns with the settings implicitly enabled in most prior state-of-the-art empirical work. We emphasize that these findings, though not technically challenging, are very fundamental and entirely novel—they have not been previously discovered or formally articulated in the literature.

Technical Contribution on Efficient Algorithms. In addition to our contribution to identifying the correct solution concept, this paper also provides a comprehensive set of algorithmic results for achieving equal share in various settings: (1) fixed opponents; (2) slowly changing opponents; (3) opponents that adapt at intermediate rates; (4) matching lower bounds.

For (1) and (2), we leverage established techniques from the no-regret and no-dynamic-regret learning literature, achieving equal shares with provable guarantees. Our contribution here mostly lies in identifying and bringing the right tools and adapting them to solve the right setup of the multiplayer games, where, to the best of our knowledge, prior state-of-the-art AI systems on multiplayer games (for Poker, etc) have not utilized techniques such as no-dynamic-regret.

For (3), we believe our discovery here is completely new, that simple algorithms like behavior cloning can sometimes even outperform sophisticated no-dynamic regret algorithms. Such a result is only possible by leveraging the symmetric structure of the multiplayer game beyond treating it as one versus an adversarial group of opponents.

For (4), while similar lower bounds have been shown in more general games, they do not apply to our settings as the hard instances constructed in prior lower bounds are not symmetric games. In this paper, we carefully construct new hard instances showing that the algorithmic results we proved in (2) and (3) are near-optimal.

Q2: Two claims made in Section 4

A2: About Condition 1: In Section 4.1, we introduce the concept of population meta-strategy and show that within a large player base, even opponents with different strategies can be viewed as adopting the same population meta-strategy. As mentioned in Section 4.1, various forms of games, such as card games, board games, and online video games, all exemplify the concept of population games via matchmaking in a large population of players.

About Condition 2: Our paper studies both scenarios where the opponents' policy is fixed (see Section 5.1) and where it is slowly adapting (see Section 5.2). While capable of updating their policies, the opponents do not run algorithms specifically targeting our AI agent, as it is merely one player within a vast pool of participants. Moreover, Proposition 4.2 points out that attaining equal shares is impossible if opponents can change their meta-strategy arbitrarily fast across different rounds, supporting Condition 2.

Q3: About experiment

A3: Please refer to A1 to Reviewer Ada2 for details on our experiment design. Our experimental cases are adversarially constructed, based on the common characteristic of many multiplayer games: the existence of multiple NE. This can cause self-play variants to converge to a bad NE, resulting in negative payoffs against carefully chosen opponent policies. Since many real-life games have multiple NEs, the worst-case results of our experiments are relevant to practical games.

While self-play algorithms have achieved impressive results in games like multiplayer poker, these successes are often context-specific and rely on extensive engineering and human input. We agree that understanding why these algorithms succeed and whether they can generalize across different game settings is an important future question, though it is beyond the scope of this paper.

Thanks a lot for reading our paper and for your insightful comments.

Q1: Clarification of the experiment

A1: Our experiment aims to demonstrate that although self-play-based meta-algorithms have been effective in many real-world multiplayer games, they can still fail to secure an equal share in worst-case scenarios. Specifically, we show that the meta-algorithms under consideration — SP_scratch, SP_BC, and SP_BC_reg — which are shown to converge to NE, do not guarantee equal outcomes in our constructed cases.

Consistent with the theoretical analysis in Section 5.1, our experimental setup assumes that all opponents play a fixed, non-adaptive strategy across all rounds. This setup represents a fundamental and arguably the simplest scenario in which a well-designed algorithm should perform reliably, especially given that real-world opponents can be adaptive or even adversarial. For self-play-based algorithms, we first run each method until convergence and then evaluate the learned policy against the fixed opponent strategy. While SP_scratch has no access to the opponent’s strategy, we include SP_BC and SP_BC_reg as baselines for fair comparison. These methods incorporate the opponent’s strategy as either initialization or regularization, following design principles from recent self-play variants that achieve state-of-the-art performance in multi-player games. Finally, as discussed in Section 3, self-play from scratch without any opponent knowledge can fail even in simple settings, such as the majority-vote game.

Q2: The novelty of the results is limited

A2: Novelty. We would like to point out that, compared to developing complex algorithmic techniques, identifying and formulating the right question to solve is equally—if not more—important. This paper precisely addresses the latter: propose novel, practical, and important formulations, study basic properties, and bring the right tools to give principled solutions in a variety of settings.

In multiplayer games, much of the existing research has focused on achieving equilibrium-based outcomes. While extensively studied, equilibrium-based approaches have well-known limitations and are often unsuitable for developing AI agents in multiplayer settings. This concern was explicitly raised in prior work on real-world multiplayer game systems (e.g., Brown & Sandholm, 2019); however, such works do not resolve the issue or propose alternative objectives. Our paper is the first to formulate the problem as achieving equal share, and to clarify that the objective is theoretically well-behaved only under the condition that all opponents deploy identical strategies. While this condition seems strong, we justify its practical relevance and note that it aligns with the settings implicitly enabled in most prior state-of-the-art empirical work. We emphasize that these findings, though not technically challenging, are very fundamental and entirely novel—they have not been previously discovered or formally articulated in the literature.

Technical Contribution on Efficient Algorithms. In addition to our contribution to identifying the correct solution concept, this paper also provides a comprehensive set of algorithmic results for achieving equal share in various settings: (1) fixed opponents; (2) slowly changing opponents; (3) opponents that adapt at intermediate rates; (4) matching lower bounds.

For (1) and (2), we leverage established techniques from the no-regret and no-dynamic-regret learning literature, achieving equal shares with provable guarantees. Our contribution here mostly lies in identifying and bringing the right tools and adapting them to solve the right setup of the multiplayer games, where, to the best of our knowledge, prior state-of-the-art AI systems on multiplayer games (for Poker, etc) have not utilized techniques such as no-dynamic-regret.

For (3), we believe our discovery here is completely new, that simple algorithms like behavior cloning can sometimes even outperform sophisticated no-dynamic regret algorithms. Such a result is only possible by leveraging the symmetric structure of the multiplayer game beyond treating it as one versus an adversarial group of opponents.

For (4), while similar lower bounds have been shown in more general games, they do not apply to our settings as the hard instances constructed in prior lower bounds are not symmetric games. In this paper, we carefully construct new hard instances showing that the algorithmic results we proved in (2) and (3) are near-optimal.

Thank you for your feedback on our submission. Upon reviewing your comments, we believe there may have been a misunderstanding, as the points raised do not seem to be relevant to our paper.

We appreciate the time and effort you have put into your review and are happy to provide further clarification or address any specific questions if needed.