Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
972840 | Mathematical Social Sciences | 2015 | 11 Pages |
Abstract
•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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Stefano Benati, Romeo Rizzi, Craig Tovey,