Research map / Learning theory and algorithms / Submodular and game algorithms
Tight Inapproximability for Graphical 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 |
|---|---|---|---|
| Fix players with an ε-dominant action, then let remaining players mix uniformly | Two-action graphical games with maximum in-degree d · Two-action graphical games, maximum in-degree d | WSNE approximation guarantee: 1 - \frac{2}{2^d + 1} | Helped |
| Reduce PCircuit to two-action graphical games | Two-action graphical games with maximum in-degree d · Two-action graphical games, maximum in-degree d | WSNE computational complexity: \varepsilon < 1 - \frac{2}{2^d + 1} | Hurt |
| Set the PURE-gate payoff parameter to 1, yielding win-lose payoffs | Two-action graphical games with maximum in-degree d · Two-action win-lose graphical games, maximum in-degree d | WSNE computational complexity: \varepsilon < 1 - \frac{1}{2^{d-1}} | Hurt |
| Let every player mix uniformly over the two actions | Two-action graphical games · Two-action graphical games | NE approximation guarantee: 0.5 | Helped |
| Reduce PCircuit using groups of k players to represent each circuit node | Two-action graphical games · Two-action graphical games | NE computational complexity: (0.5 - \ensuremath{\varepsilon}\xspace) | Hurt |
| Use only 0-or-1 payoff entries in the NE hardness construction | Two-action graphical games · Two-action win-lose graphical games | NE computational complexity: (0.5 - \ensuremath{\varepsilon}\xspace) | Hurt |
Closest papers by meaning
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
- Polynomial-Time Computation of Exact $\Phi$-Equilibria in Polyhedral Games (NeurIPS 2024 · similarity 0.87)
- Anytime-Constrained Equilibria in Polynomial Time (ICML 2025 · similarity 0.87)
- Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization (ICLR 2024 · similarity 0.87)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · 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.