Computational Aspects of the Preference Cores of Supermodular Two-Scenario Cooperative Games

Daisuke Hatano, Yuichi Yoshida

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.

Figure 2: Reduction of the preference core problem for induced subgraph games to a minimum cut problem on a constructed graph G'.

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.

Figure 4: Construction of a directed graph G' to solve the preference core value for multicast tree games via a minimum s-t cut.

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

Abstract

In a cooperative game, the utility of a coalition of players is given by the characteristic function, and the goal is to find a stable value division of the total utility to the players. In real-world applications, however, multiple scenarios could exist, each of which determines a characteristic function, and which scenario is more important is unknown. To handle such situations, the notion of multi-scenario cooperative games and several solution concepts have been proposed. However, computing the value divisions in those solution concepts is intractable in general. To resolve this issue, we focus on supermodular two-scenario cooperative games in which the number of scenarios is two and the characteristic functions are supermodular and study the computational aspects of a major solution concept called the preference core. First, we show that we can compute the value division in the preference core of a supermodular two-scenario game in polynomial time. Then, we reveal the relations among preference cores with different parameters. Finally, we provide more efficient algorithms for deciding the non-emptiness of the preference core for several specific supermodular two-scenario cooperative games such as the airport game, multicast tree game, and a special case of the generalized induced subgraph game.
BibTeX
@inproceedings{hatano2018computational,
  author = {Daisuke Hatano and Yuichi Yoshida},
  title = {{Computational Aspects of the Preference Cores of Supermodular Two-Scenario Cooperative Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/43},
}

Loading related content...

Figure