Research map / Learning theory and algorithms / Submodular and game algorithms
Sparsified Linear Programming for Zero-Sum Equilibrium Finding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Factor the payoff matrix sparsely before solving the equilibrium LP | LP equilibrium solving · Explicitly specified games | wall-clock time to target Nash gap | Helped |
| Factor the payoff matrix sparsely before solving with simplex | No-limit poker endgames · River 1–7 | time (s) | Helped |
| Factor the payoff matrix before simplex rather than leave it unfactored (ablation) | Gurobi simplex · No-limit poker endgames | memory (MB): 5569 -> 259 | Helped |
| Factor the payoff matrix before simplex rather than leave it unfactored (ablation) | Gurobi simplex · River 2 | time (s): 830 -> 113 | Helped |
| Allow inner iterations to grow linearly with outer iterations instead of using an exponentially increasing limit (ablation) | LPsparse · Game solving | runtime | Helped |
| Initialize the factorization search with a random basis vector rather than a random vector (ablation) | Sparse matrix factorization · Sparse extensive-form game payoff matrices | factorization effectiveness | Helped |
| Use the 1-norm instead of the 0-norm in the factorization objective (ablation) | Sparse matrix factorization · Experiments | factorization performance | No clear effect |
| Use sparse factorization rather than SVD-based factorization | Payoff matrix compression · Poker endgames | matrix sparsity: 58{,}707{,}847 -> 740{,}218 | Helped |
Closest papers by meaning
- Solving Large Sequential Games with the Excessive Gap Technique (NeurIPS 2018 · similarity 0.91)
- Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games (AAAI 2022 · similarity 0.91)
- Faster Game Solving via Hyperparameter Schedules (AAAI 2026 · similarity 0.90)
- Accelerating Nash Equilibrium Convergence in Monte Carlo Settings Through Counterfactual Value Based Fictitious Play (NeurIPS 2024 · similarity 0.88)
- Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis (NeurIPS 2024 · similarity 0.87)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 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.