Research map / Learning theory and algorithms / Submodular and game algorithms
Zero-sum game learning dynamics
Analyze complexity and learning dynamics for computing equilibria in two-player zero-sum games.
107 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in Submodular and game algorithms, keyword cluster “game · equilibrium · equilibria”
State History Tried Checklist Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
24 papers in 2023–24 and 35 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic grew, from 11.8% to 14.5%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Graphical Hedonic Games of Bounded Treewidth (AAAI 2016 · 35 citations)
- 2017 · Heuristic Search Value Iteration for One-Sided Partially Observable Stochastic Games (AAAI 2017 · 50 citations)
- 2018 · Solving Large Sequential Games with the Excessive Gap Technique (NeurIPS 2018 · 14 citations)
- 2019 · Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions (NeurIPS 2019 · 13 citations)
- 2020 · A Generalized Training Approach for Multiagent Learning (ICLR 2020 · 22 citations)
- 2021 · From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (ICML 2021 · 16 citations)
- 2022 · Fictitious Play and Best-Response Dynamics in Identical Interest and Zero-Sum Stochastic Games (ICML 2022 · 4 citations)
- 2023 · Tight Inapproximability for Graphical Games (AAAI 2023 · 4 citations)
- 2024 · Learning Discrete-Time Major-Minor Mean Field Games (AAAI 2024 · 4 citations)
- 2025 · Decentralized and Uncoordinated Learning of Stable Matchings: A Game-Theoretic Approach (AAAI 2025 · 2 citations)
- 2026 · Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions (AAAI 2026 · 1 citation)
Earliest papers here
- Graphical Hedonic Games of Bounded Treewidth (AAAI 2016 · 35 citations)
- Learning Tree Structured Potential Games (NeurIPS 2016 · 9 citations)
- Computing Possible and Necessary Equilibrium Actions (and Bipartisan Set Winners) (AAAI 2016 · 6 citations)
What has been tried
61 papers here report 383 measured changes (a component added, removed or swapped, compared with a baseline): helped 63%, no clear effect 11%, hurt 17%, mixed 8%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Increase the restarting interval k beyond the range where performance stabilizes | Kuhn Poker and Leduc Poker · exploitability | No clear effect | Rapid Learning in Constrained Minimax Games with Negative Momentum (AAAI 2025 · 0 citations) | |
| Use weight w_t=1 instead of the other tested common weights | Different games · convergence speed | Helped | Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play (NeurIPS 2024 · 0 citations) | |
| Remove the LookAhead module | Zero-sum games · exploitability | Hurt | A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games (ICML 2025) |
What reviewers will expect
Datasets and baselines named in the 23 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Datasets
- randomly generated normal-form games · 2 of 23 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 59 papers; from OpenAlex and the papers' affiliations).
- Carnegie Mellon University · 7 papers
- Massachusetts Institute of Technology · 5 papers
- Inria · 4 papers
- Meta · 3 papers
- French National Center for Scientific Research · 3 papers
- University of California, Irvine · 3 papers
- Google DeepMind · 2 papers
- National University of Singapore · 2 papers
- Columbia University · 2 papers
- Princeton University · 2 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Opponent modeling and subgame solving (116 papers)
- Correlated equilibria in sequential games (86 papers)
- Equilibrium solvers for adversarial games (25 papers)
Elsewhere in the topic
- Fair division of indivisible goods (130 papers)
- Committee voting rules (120 papers)
- Matching markets and welfare (119 papers)
- Monotone submodular maximization (116 papers)
- Learned auction design (105 papers)
- Streaming submodular algorithms (73 papers)
- Submodular influence maximization (33 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).