Abstract
Finding stable utility divisions in cooperative games under uncertainty is a fundamental challenge in algorithmic game theory. While determining the "preference core" for multi-scenario games is generally NP-hard, this paper identifies a significant class of tractable problems. We prove that for supermodular (convex) two-scenario games, stable divisions can be computed in polynomial time. This is achieved by reframing the problem as a submodular intersection task and, for specific game types, reducing it to efficient minimum-cut problems on graphs and hypergraphs.
Introduction
In cooperative game theory, the "core" represents a set of utility distributions where no subset of players has an incentive to deviate from the grand coalition. However, real-world cooperation often occurs under uncertainty, where multiple potential scenarios (e.g., different cost structures or demand patterns) must be considered simultaneously. Multi-scenario cooperative games model this by requiring a distribution to be stable across all possible outcomes.
The "preference core" is the solution concept for these games, but its computation is typically intractable. This paper focuses on two-scenario games with the supermodular property—where the marginal benefit of joining a coalition increases with its size. This property, common in infrastructure and network sharing, allows for the development of efficient, polynomial-time algorithms.
Theoretical Framework: Submodular Intersection
The authors establish a deep link between game-theoretic stability and combinatorial optimization. They demonstrate that finding a value division in the $(\epsilon_1, \epsilon_2)$-preference core—where $\epsilon$ denotes the allowable "slack" or deviation in each scenario—is equivalent to solving the submodular intersection problem.
Because submodular intersection is solvable in polynomial time, this result immediately classifies the preference core of any supermodular two-scenario game as computationally tractable. A key insight is that the non-emptiness of the core depends solely on the sum of the slack parameters ($\epsilon_1 + \epsilon_2$), allowing for linear interpolation between different stable states.
Graph Reductions and Efficient Algorithms
Beyond general solvers, the paper provides highly efficient algorithms for specific game models by reducing them to classic network flow problems.
Induced Subgraph Games
In these games, utility is derived from the edges between players in a network. The authors show that the preference core value (the minimum total slack required for stability) can be determined by solving a minimum cut problem on a specially constructed graph or hypergraph.
Multicast Tree Games
Multicast tree games model the cost of distributing information from a source to multiple nodes. The stability problem here reduces to a minimum $s-t$ cut on a directed graph.
Key Results and Case Studies
The research highlights several key findings:
- General Tractability: Any supermodular two-scenario game's preference core is computable in polynomial time.
- Airport Games: For these cost-sharing models, the authors derive a closed-form expression for the core value. They show that under standard player ordering, a perfectly stable division ($\epsilon=0$) often exists.
- Algorithmic Speedups: By leveraging min-cut formulations, the computational overhead for large-scale network games is significantly reduced compared to general submodular optimization.
Conclusion and Future Work
While the two-scenario case is tractable for supermodular games, the authors note that extending these results to three or more scenarios likely leads back to NP-completeness. This is due to the inherent difficulty of finding the intersection of three or more submodular polyhedra. Future research may explore approximation algorithms for these higher-uncertainty environments or investigate hybrid games that combine multiple supermodular structures.
Summary updated