Supermodular Games on Social Networks

Cooperative games offer an elegant framework to model cooperation among self-interested agents. A central question of these games is how to distribute the payoff to each player when all players cooperate and derive some benefits. In this work, we consider cooperative transferable utility games where a subset of players can form a coalition if and only if they are connected in the underlying communication structure. We propose a relaxed notion of supermodularity, called quasi-supermodularity, for such games, and identify a class of networks where many of these problems are polynomial-time solvable for relaxed-supermodular games. We complement these results by showing that without supermodularity, these problems become hard even if the underlying graph is a tree.