Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces

Abstract

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ⁿ values, so the input size is 2ⁿ 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 ≤ 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ⁿ. 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.

Induced Representations in Cooperative Games with Homogeneous Groups of Players
Windsor Kiang
arXiv25 Sep 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Cooperative Integer Programming Games: Core Stability and Optimal Coalition Structures
Hyunwoo Lee, Robert Hildebrand, I. Esra Buyuktahtakin
arXiv10 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Loss of memory in the periodic Ehrenfest model with small polyhedral scatterers
Christopher Lutsko, Jens Marklof
arXiv3 Sep 2026PreprintarXiv licenceFull textDynamical systems Mathematical physicsarXiv
String-averaging bargaining in solidarity cooperative games
Yair Censor, Soumitra Dey
arXiv29 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
W^1,p error estimates of an IPDG and a class of HDG methods for the Poisson problem on convex polyhedral domains
Haitao Leng, Weifeng Qiu
arXiv30 Oct 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv

Cite

BibTeX RIS

BibTeX

@misc{tiwary2026polyhedral,
  title = {{Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces}},
  author = {Hans Raj Tiwary and Michel Grabisch},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.24593},
  eprint = {2609.24593},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.24593},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces
AU  - Hans Raj Tiwary
AU  - Michel Grabisch
PY  - 2026
DA  - 2026/09/21
PB  - arXiv
DO  - 10.48550/arxiv.2609.24593
UR  - https://arxiv.org/abs/2609.24593
AB  - 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 ≤ 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.
ER  -

Abstract

Related

Cite