Research map / Learning theory and algorithms / Submodular and game algorithms
Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games
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 |
|---|---|---|---|
| Leverage poker's Kronecker-product structure to construct Technique A or Technique B sparsifications instead of using the general sparsification heuristic | Poker river-endgame payoff matrices · Eight River endgames | sparsification size (nonzeros): Technique A: 100 and 200; Technique B: 200 and 400 (sparsity increase factors, as reported) | Helped |
| Use Technique B rather than Technique A | Poker river-endgame payoff matrices · Eight River endgames | sparsification size (nonzeros): Technique B ... roughly twice as small as Technique A | Helped |
| Use Kronecker-structure techniques rather than Zhang & Sandholm's general technique | Poker river-endgame payoff matrices · River 7, River 6, River 8, River 2, River 4 | sparsification computation time: 300 milliseconds and 1 second; general method: hours | Helped |
| Use the proposed sparsification techniques to prepare the Nash-equilibrium LP | Gurobi · Eight River endgames | ability to compute an optimal Nash-equilibrium basis | Helped |
| Use Technique B rather than Technique A for Nash LP solving | Gurobi · Larger River endgames | Nash LP solve time: 1x--3x | Helped |
| Use Technique A rather than Technique B for GPU Discounted CFR | GPU implementation of DCFR · River endgames | time to reach a given exploitability | Helped |
| Use Technique A sparsification in GPU Discounted CFR | GPU implementation of DCFR · River endgames | time to obtain playable approximate Nash strategies: 5-6 seconds | Helped |
| Compute least-exploitable deterministic strategies using Technique B-sparsified formulations | Gurobi integer program · Eight River endgames | value retained relative to game value: 98.26%; < 1.16%; < 1.18%; < 1.10%; < 1.74%; < 1.42%; < 1.00%; < 0.94%; < 1.60% | Helped |
Closest papers by meaning
- Sparsified Linear Programming for Zero-Sum Equilibrium Finding (ICML 2020 · similarity 0.91)
- Solving Large Sequential Games with the Excessive Gap Technique (NeurIPS 2018 · similarity 0.89)
- Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions (NeurIPS 2019 · similarity 0.89)
- Faster Game Solving via Hyperparameter Schedules (AAAI 2026 · similarity 0.88)
- Commitment to Sparse Strategies in Two-Player Games (AAAI 2025 · similarity 0.86)
- Accelerated Regularized Learning in Finite N-Person Games (NeurIPS 2024 · similarity 0.86)
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.