The complexity of power indexes with graph restricted coalitions

• We prove that both problems are #P-complete in the strong sense for graphs.
• We prove that both problems are #P-complete in the weak sense for trees.
• We give pseudo-polynomial algorithms for both problems on trees.

Coalitions of weighted voting games can be restricted to be connected components of a graph. As a consequence, coalition formation, and therefore a player’s power, depends on the topology of the graph. We analyze the problems of computing the Banzhaf and the Shapley–Shubik power indexes for this class of voting games and prove that calculating them is #P-complete in the strong sense for general graphs. For trees, we provide pseudo-polynomial time algorithms and prove #P-completeness in the weak sense for both indexes.