Research map / Learning theory and algorithms / Submodular and game algorithms
Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies equal-share payoff (C/n) in multiplayer symmetric constant-sum games, identifies conditions for tractability, and gives Hedge, SAOL-Hedge, and behavior-cloning algorithms with matching lower bounds, validated on two toy games.
Problem
Multiplayer symmetric constant-sum games lack a suitable solution concept: equilibria are non-unique and non-exploitable guarantees fail, so learning agents cannot reliably secure a fair share of payoff against opponents.
Approach
Adopts equal share (expected payoff C/n) as the objective and shows it is achievable only when opponents use an identical meta-strategy and have bounded adaptivity; then applies no-regret (Hedge), no-dynamic-regret (SAOL), and behavior cloning, with matching lower bounds.
Key results
- On Majority Vote, Hedge achieves utility 1.03e-2 ± 0.10e-2 against the opponent meta-strategy while self-play variants get about -1.00e-2, with self-play converging to the bad NE half the time.
- On Switch Dominance Game (n=30), Hedge achieves utility 1.00 ± 0.00 while all self-play variants reach -12.67 ± 0.01.
- Theory gives Hedge error O~(1/sqrt(T)) against stationary opponents, SAOL-Hedge error O~(V_T^{1/3} T^{-1/3}) and behavior cloning error O((V_T+1)/T) under bounded variation, with matching lower bounds up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Hedge instead of the self-play meta-algorithms | MV · MV | Utility (×10^-2): -1.00 $\pm$ 0.09 -> 1.03 $\pm$ 0.10 | Helped |
| Use Hedge instead of the self-play meta-algorithms | SDG · SDG | Utility: -12.67 $\pm$ 0.01 -> 1.00 $\pm$ 0.00 | Helped |
| Use Hedge instead of the self-play meta-algorithms | MV · MV | Exploitability: -1.00 $\pm$ 0.00 -> -1.00 $\pm$ 0.00 | No clear effect |
| Use Hedge instead of the self-play meta-algorithms | SDG · SDG | Exploitability: -29.00 $\pm$ 0.00 -> -29.00 $\pm$ 0.00 | No clear effect |
| Add behavior-cloning initialization to self-play | MV self-play · MV | Convergence frequency to [1,0]: 52% -> 48% | No clear effect |
| Vary the behavior-cloning regularization coefficient | MV self-play · MV | Convergence frequency to [1,0]: 50%, 46%, 42%, 42% | Mixed |
Surprising findings
- Equal share is not achievable by any learner in worst case when opponents play different strategies, and even identical-strategy opponents make any fixed strategy exploitable.
- Simple behavior cloning is near-optimal in the intermediate regime where opponents adapt at moderate rates, outperforming sophisticated no-dynamic-regret methods there.
Limitations
- Results are for normal-form symmetric constant-sum games with opponents sharing one meta-strategy; the condition of identical opponent strategies may be restrictive.
- Experiments are limited to two toy games with fixed opponents and idealized imitation learning.
- The learned strategies are exploitable by adversarial opponents.
Experimental setup
Benchmarks: Majority Vote game Switch Dominance Game
Metrics: utility against meta-strategy exploitability
Baselines: self-play from scratch self-play with behavior cloning initialization self-play with behavior cloning regularization
Builds on: Hedge strongly adaptive online learning self-play behavior cloning
Closest papers by meaning
- Guarantees for Self-Play in Multiplayer Games via Polymatrix Decomposability (NeurIPS 2023 · similarity 0.90)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.88)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.88)
- Can Reinforcement Learning Solve Asymmetric Combinatorial-Continuous Zero-Sum Games? (ICLR 2025 · similarity 0.87)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.