Polyhedral methods clarify complexity of cooperative game problems
Polyhedral Methods for Cooperative Games: Small Lifts and Hard Faces
Computer Science and Game TheoryComputational Complexity
Summary
Cooperative games involve many players working together and require a huge amount of information, making computations very hard. The authors study special cases where the input size is smaller, called k-additive games, and find efficient ways to solve key problems in these cases. They also prove that for certain games, these problems remain very hard to solve, explaining why some game properties are difficult to understand. Their work builds bridges between geometry and game theory to better understand when cooperative game computations are feasible.
What this means in practice
- •For game theorists: Use explicit polynomial-size linear programs to solve core-related problems in k-additive k-monotone cooperative games efficiently.
- •For combinatorial optimization teams: Avoid computational intractability by recognizing hardness in membership testing for certain cooperative game cones, guiding problem modeling choices.
A theory result. No direct application yet.
Authors
Hans Raj Tiwary, Michel Grabisch
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^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.