Metraipolis › archive › dc_9e181bc5dec1
Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces — arXiv:2609.24593
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.24593
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:58:07.184Z
- SHA-256 of the archived text
357647c9aa5b2ab7b4b8efacc13a8d2c840448d7b12afdb8894f0c870f787f55- Stable URL of this page
https://metraipolis.com/documento/dc_9e181bc5dec1
How to cite
Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces — arXiv:2609.24593 — arXiv (en), https://arxiv.org/abs/2609.24593 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9e181bc5dec1 (Metraipolis archive dc_9e181bc5dec1, sha256 357647c9aa5b2ab7b4b8efacc13a8d2c840448d7b12afdb8894f0c870f787f55)
BibTeX
@misc{dc9e181bc5dec1,
title = {Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces — arXiv:2609.24593},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.24593},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9e181bc5dec1; sha256 357647c9aa5b2ab7b4b8efacc13a8d2c840448d7b12afdb8894f0c870f787f55},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24593. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the computational complexity of fundamental algorithmic problems -- membership testing, separation, valid-inequality testing, and linear optimization -- over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program -- in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-22 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC); Combinatorics (math.CO); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.24593 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T06:52:12.763Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).