Research map / Learning theory and algorithms / Submodular and game algorithms
Are Equivariant Equilibrium Approximators Beneficial?
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 |
|---|---|---|---|
| Enforce OPI/PPE for NE or PE for CE/CCE with orbit averaging | Equilibrium approximator classes · NE, CE, and CCE approximators | covering number: The projected classes have covering numbers no greater than the general classes | Helped |
| Use a smaller-covering-number equivariant class | Equilibrium approximators · Generalization to games drawn from the training payoff distribution | generalization bound and sample complexity: Both decrease with the decrease of covering numbers | Helped |
| Apply PE projection Q | CE/CCE approximator · Permutation-invariant payoff distributions | expected equilibrium approximation (exploitability): \mathbb{E}_{u \sim \mathcal{D}}[\mathcal{E}(\mathcal{Q} \fcCE(u), u)] \le \mathbb{E}_{u \sim \mathcal{D}}[\mathcal{E}(\f | Helped |
| Apply O or P projection | NE approximator · Permutation-invariant payoff distributions for bimatrix constant-sum games | expected sum of exploitabilities: \mathbb{E}_{u \sim \mathcal{D}}[\sum_i \mathcal{E}_i((\mathcal{X} \fNE)(u), u)] \le \mathbb{E}_{u \sim \mathcal{D}}[\sum | Helped |
| Add O projection to a PPE approximator | PPE NE approximator · Permutation-invariant payoff distributions for bimatrix games | expected NE approximation: \mathbb{E}_{u \sim \mathcal{D}}[\mathcal{E}((\mathcal{O} \fNE)(u), u)] \le \mathbb{E}_{u \sim \mathcal{D}}[\mathcal{E}(\ | Helped |
| Add P projection to an OPI approximator | OPI NE approximator · Permutation-invariant payoff distributions | expected NE approximation: \mathbb{E}_{u \sim \mathcal{D}}[\mathcal{E}((\mathcal{P} \fNE)(u), u)] \le \mathbb{E}_{u \sim \mathcal{D}}[\mathcal{E}(\ | Helped |
| Constrain the output to satisfy PE | (C)CE approximator · Games with n ≤ N players and |A_i| ≤ M | worst social welfare ratio: 1 | No clear effect |
| Constrain the output to satisfy OPI | NE approximator · Games with n ≤ N players and |A_i| ≤ M | worst social welfare ratio: \frac{1}{M^{N-1}} | Hurt |
| Constrain the output to satisfy PPE | NE approximator · Games with n ≤ N players and |A_i| ≤ M | worst social welfare ratio: \le \frac{1}{M} | Hurt |
| Constrain the output to satisfy both PPE and OPI | Exact NE oracle · Games with n ≤ N players and |A_i| ≤ M, M ≥ 3 | worst social welfare ratio: 0 | Hurt |
| Require permutation equivariance/invariance | NE, CE, and CCE approximators · Permutation-invariant games with non-fixed pure-equilibrium actions | equilibria the approximator can find | Hurt |
Closest papers by meaning
- Generative Adversarial Equilibrium Solvers (ICLR 2024 · similarity 0.88)
- Paradoxes of Game Theoretic Equilibria and Price of Anarchy (NeurIPS 2026 · similarity 0.87)
- The Complexity of Correlated Equilibria in Generalized Games (NeurIPS 2025 · similarity 0.87)
- Reducing Variance of Stochastic Optimization for Approximating Nash Equilibria in Normal-Form Games (ICML 2025 · similarity 0.86)
- On Tractable $\Phi$-Equilibria in Non-Concave Games (NeurIPS 2024 · similarity 0.86)
- On the Outcome Equivalence of Extensive-Form and Behavioral Correlated Equilibria (AAAI 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.