Research map / Learning theory and algorithms / Submodular and game algorithms
Commitment to Sparse Strategies in Two-Player 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 k-sparse commitments (sparse player restricted to support size at most k) in zero-sum and Stackelberg games, proves structural pathologies, and solves them via MILPs plus single/double-oracle and incremental generation for large action sets.
Problem
Nash equilibria and Stackelberg commitments may have dense support, which is hard to interpret and execute; finding optimal k-sparse commitments is NP-hard and naive greedy or oracle-based methods fail.
Approach
Formulate optimal k-sparse commitments as MILPs (binary support indicators with a cardinality constraint), extend them to Stackelberg games, structured sparsity constraints, and MILP-representable large action spaces, combined with incremental strategy generation for large games; show that k-sparse strategies beat k-uniform ones.
Key results
- In random games with n=m=80, about 90% of the Nash value is attained at around 0.25 k_NE (zero-sum) and 0.45 k_SE (general-sum).
- In the campus patrolling game, the professor achieves more than 90% of the optimal value with k as low as 3.
- With both players having large strategy spaces, the sparse player secures over 95% of the Nash value with k=3 for T=5,6,7, whereas k-uniform yields less than 80%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict Player 1 to an optimally chosen k-sparse commitment | Random zero-sum games, n=m=80 · Random zero-sum games, n=m=80 | relative utility: about 90% at around 0.25 k_NE | Helped |
| Restrict Player 1 to an optimally chosen k-sparse commitment | Random general-sum games, n=m=80 · Random general-sum games, n=m=80 | relative utility: about 90% at around 0.45 k_SE | Helped |
| Restrict the patrol distribution to k paths | Optimal k-sparse commitment · University campus patrolling | relative utility: more than 90% at k as low as 3 | Helped |
| Restrict patrol starting points to k locations | Structured-sparsity commitment · University campus patrolling, 8 starting points | relative utility: almost maximum utility at k=4 | Helped |
| Use an optimally selected sparse support rather than a k-uniform strategy | Patrolling with both players having large action spaces · Patrolling, T in {5,6,7} | relative utility: over 95% vs less than 80% at k=3 | Helped |
| Use an optimal k-sparse strategy instead of a k-uniform strategy | Randomly generated normal-form games · Random zero-sum and general-sum games | relative utility | Helped |
| Use an optimal k-sparse strategy instead of a k-uniform strategy | Patrolling games with large action spaces · Patrolling games | relative utility | Helped |
| Increase path length to T=8 while keeping k=3 | Optimal k-sparse commitment · Patrolling, large sparse-player action space | relative utility: more than 90% for T in {5,6,7} -> 80% at T=8 | Hurt |
| Increase the non-sparse player's graph depth from 6 to 9 | Optimal k-sparse commitment · Patrolling, large non-sparse-player action space | relative utility: around 90% at k=3 for all depths | No clear effect |
| Use the single Stackelberg MILP instead of multiple MILPs | General-sum commitment solver · Random general-sum games | runtime | Hurt |
| Use the single Stackelberg MILP instead of multiple MILPs | General-sum commitment solver · Random general-sum games with alternative payoff correlations | relative utility | No clear effect |
Surprising findings
- Optimal k-sparse supports can be completely disjoint for different k, and the value is not monotone-diminishing or submodular in the support set.
- k-uniform commitments can perform worse than k-uniform-free sparse commitments and their value is not non-decreasing in k.
Limitations
- Finding optimal k-sparse commitments is NP-hard, and runtime exhibits a hard zone for intermediate k.
- Large-action-space settings with both players large can be slow; some runs hit a 12-hour limit and 16k-path games perform poorly at small k.
- Only normal-form and two-player settings are studied; extensions to extensive-form or multiplayer games are left open.
Experimental setup
Datasets: randomly generated normal-form games university campus pursuit-evasion patrolling graph (OSMnx) Hearts of Iron IV maps for air defense placement
Benchmarks: random zero-sum games random general-sum games patrolling pursuit-evasion games air defense battery placement
Metrics: normalized relative utility normalized runtime
Baselines: k-uniform strategies Nash equilibrium value Stackelberg equilibrium value
Builds on: double oracle multiple LPs for Stackelberg equilibrium operationalizable strategies (k-uniform)
Closest papers by meaning
- On the Approximation of Nash Equilibria in Sparse Win-Lose Games (AAAI 2018 · similarity 0.89)
- On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games (AAAI 2021 · similarity 0.87)
- Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure (AAAI 2018 · similarity 0.87)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.87)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.87)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · 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.