  The Banzhaf index, Shapley-Shubik index and other voting power indices
measure the importance of a player in a coalitional game. We consider a simple
coalitional game called the spanning connectivity game (SCG) based on an
undirected, unweighted multigraph, where edges are players. We examine the
computational complexity of computing the voting power indices of edges in the
SCG. It is shown that computing Banzhaf values and Shapley-Shubik indices is
#P-complete for SCGs. Interestingly, Holler indices and Deegan-Packel indices
can be computed in polynomial time. Among other results, it is proved that
Banzhaf indices can be computed in polynomial time for graphs with bounded
treewidth. It is also shown that for any reasonable representation of a simple
game, a polynomial time algorithm to compute the Shapley-Shubik indices implies
a polynomial time algorithm to compute the Banzhaf indices. As a corollary,
computing the Shapley value is #P-complete for simple games represented by the
set of minimal winning coalitions, Threshold Network Flow Games, Vertex
Connectivity Games and Coalitional Skill Games.
