Research map / Learning theory and algorithms / Submodular and game algorithms
Small Nash Equilibrium Certificates in Very Large Games
Brian Zhang, Tuomas Sandholm
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| remove unnecessary nodes from certificate (ablation) | 0-certificate · search game | certificate nodes % of game: 5.8 -> 2.4 | Improved |
| remove unnecessary nodes from certificate (ablation) | 0-certificate · 6-rank PI Goofspiel | certificate nodes % of game: 1.1 -> 0.2 | Improved |
| remove unnecessary nodes from certificate (ablation) | 0-certificate · 13-rank limit Leduc | certificate nodes % of game: 9.4 -> 3.0 | Improved |
| remove unnecessary nodes from certificate (ablation) | 0-certificate · 5-rank random Goofspiel | certificate nodes % of game: 21.7 -> 16.3 | Improved |
| increase rank of perfect-information Goofspiel | 0-certificate · PI Goofspiel | certificate nodes % of game: 12.3 -> 4.7 -> 1.1 | Improved |
| increase rank of Goofspiel | 0-certificate · Goofspiel | certificate nodes % of game: 27.5 -> 20.5 -> 13.3 | Improved |
| increase rank of limit Leduc | 0-certificate · limit Leduc | certificate nodes % of game: 13.3 -> 11.7 -> 9.4 | Improved |
| increase rank of random Goofspiel | 0-certificate · random Goofspiel | certificate nodes % of game: 29.0 -> 24.1 -> 21.7 | Improved |
| randomize prize order in Goofspiel | 0-certificate · 5-rank Goofspiel vs random | certificate nodes % of game: 20.5 -> 21.7 | Hurt |
| perfect-information variant of Goofspiel | 0-certificate · 4-rank Goofspiel | certificate nodes % of game: 27.5 -> 12.3 | Improved |
Closest papers by meaning
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.87)
- Commitment to Sparse Strategies in Two-Player Games (AAAI 2025 · similarity 0.87)
- Protocols for Verifying Smooth Strategies in Bandits and Games (NeurIPS 2025 · similarity 0.86)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.85)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.85)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.85)
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.
