Power indices in spanning connectivity games
Aziz, Haris, Lachish, Oded, Paterson, Michael S. and Savani, Rahul (2009) Power indices in spanning connectivity games. In: 5th International Conference on Algorithmic Aspects in Information and Management, San Francisco, CA, June 15-17, 2009. Published in: Lecture Notes in Computer Science, Vol.5564 pp. 55-67.Full text not available from this repository.
Official URL: http://www.springerlink.com/content/h5454r468452/#...
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 is #P-complete and computing Shapley-Shubik indices or values is NP-hard 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. This answers (positively) an open question of whether computing Shapley-Shubik indices for a simple game represented by the set of minimal winning coalitions is NP-hard.
|Item Type:||Conference Item (Paper)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Computer Science|
|Series Name:||Lecture Notes in Computer Science|
|Journal or Publication Title:||Lecture Notes in Computer Science|
|Editor:||Goldberg, AV and Zhou, Y|
|Number of Pages:||13|
|Page Range:||pp. 55-67|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Title of Event:||5th International Conference on Algorithmic Aspects in Information and Management|
|Type of Event:||Conference|
|Location of Event:||San Francisco, CA|
|Date(s) of Event:||June 15-17, 2009|
Actions (login required)