Research map / Learning theory and algorithms / Submodular and game algorithms
Constrained Pure Nash Equilibria in Polymatrix 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 |
|---|---|---|---|
| Restrict the query to be monochromatic rather than polychromatic | 2-colour coordination games on arbitrary graphs; existence of constrained pure NE · 2 colours, monochromatic query | complexity: NP-comp. -> \mathcal{O}(|G|) | Helped |
| Restrict the query to be monochromatic rather than polychromatic | 2-colour coordination games on arbitrary graphs; universality of constrained pure NE · 2 colours, polychromatic query | runtime: \mathcal{O}(|G|) -> \mathcal{O}(|G|) | No clear effect |
| Restrict the graph to a DAG with out-degree at most 1 | Constrained pure NE existence and universality · DAGs with out-degree \leq 1 | complexity: NP-comp. / coNP-comp. -> \mathcal{O}(|G|^{2.5}) | Helped |
| Allow DAGs with out-degree up to two instead of at most one | Constrained pure NE existence and universality · Unweighted DAGs, no bonuses | complexity: \mathcal{O}(|G|^{2.5}) -> NP-complete / coNP-complete | Hurt |
| Use three colours and singleton queries on DAGs | Constrained pure NE existence and universality · Unweighted DAGs, no bonuses | complexity: NP-complete / coNP-complete | Hurt |
| Restrict the underlying graph to a simple cycle | Constrained pure NE existence and universality · Simple cycles | runtime: \mathcal{O}(|G|) / \mathcal{O}(m\cdot|G|) | Helped |
| Require the graph to be unweighted and colour complete, with no bonuses and a fixed number of colours | Constrained pure NE existence and universality · Colour complete graphs | runtime: \mathcal{O}(nm\cdot m!) | Helped |
Closest papers by meaning
- On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games (AAAI 2021 · similarity 0.92)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.89)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.88)
- The Complexity of Computing Robust Mediated Equilibria in Ordinal Games (AAAI 2024 · similarity 0.88)
- Computing Game Symmetries and Equilibria That Respect Them (AAAI 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.