Research map / Multi-agent systems and games / Games and equilibria
On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player 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 each payoff-matrix row and column to at most two ones | Sparse win-lose polymatrix games · (2, 2)-SWLP games | computational complexity of finding a 1/n4-well-supported Nash equilibrium | Hurt |
| Restrict the game to at most one one per row or per column | Sparse win-lose polymatrix games · (1, n)-SWLP and (n, 1)-SWLP games | exact Nash equilibrium computation | Helped |
Closest papers by meaning
- On the Approximation of Nash Equilibria in Sparse Win-Lose Games (AAAI 2018 · similarity 0.92)
- Constrained Pure Nash Equilibria in Polymatrix Games (AAAI 2017 · similarity 0.92)
- Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria (NeurIPS 2023 · similarity 0.91)
- Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure (AAAI 2017 · similarity 0.91)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.91)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.88)
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.