Cooperative games with overlapping coalitions: charting the tractability frontier (Q2321289)

Cooperative games with overlapping coalitions (OCF games) capture situations in which individuals may belong simultaneously to different coalitions, dividing their efforts among those of which they are members. A first step in the analysis of any OCF game involves the specification of all its coalitions. The size of this description determine the computational complexity of the problems that may ensue in the game. A part of this description is the fraction of resources devoted by a player \(i\) to a coalition \(C\), \(x_i^C \in [0,1]\). Since most relevant problems amount to finding these fractions, they become computationally intractable. The authors restrict their attention to two classes of OCF games. On one hand, \textit{discrete} ones (replacing \([0,1]\) by some discretization) and \textit{bottleneck games} (where the payoff of a coalition depend on the contribution of the least contributing player). In both cases the paper studies a series of problems ranging from finding the optimal coalition structure to finding a stable outcome. In the case of a discrete OCF game, only a few assumptions ensure polynomial time solutions for the optimal coalitional structure problem. For the stability problem, instead, it is shown that efficient algorithms exist if the reaction of non-deviators to deviations is limited in scope. In the case of bottleneck games, the authors present a linear programming-based algorithms that finds stable outcomes in polynomial time.