Research map / Learning theory and algorithms / Sample complexity
On Covering Codes and Upper Bounds for the Dimension of Simple Games
Martin Olsen
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| Cover the maximal losing coalitions with a radius-1 binary covering code and represent each covered group by a weighted game | Simple games with n players · Simple games with n players | dimension upper bound: d_n ≤ K_n | Improved |
| Pair maximal losing coalitions at distance at most 3, handling unpaired coalitions as singletons | Simple games · Simple games with maximal losing coalitions | dimension upper bound: \frac{1}{2}(|L^M|+|C|) | Improved |
| Use a covering code to bound dimension rather than the Taylor-Zwicker maximal-losing-coalition bound | Maximum dimension d_n · Simple games with n players | dimension upper bound: d_n ≤ K_n | Improved |
Closest papers by meaning
- Commitment to Sparse Strategies in Two-Player Games (AAAI 2025 · similarity 0.84)
- Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size (AAAI 2025 · similarity 0.84)
- Certifying Concavity and Monotonicity in Games via Sum-of-Squares Hierarchies (NeurIPS 2025 · similarity 0.84)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.84)
- Thresholds for sensitive optimality and Blackwell optimality in stochastic games (NeurIPS 2025 · similarity 0.84)
- Securing Equal Share: A Principled Approach for Learning Multiplayer Symmetric Games (ICML 2025 · similarity 0.84)
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.
