Aziz, Haris, Lachish, Oded, Paterson, Mike and Savani, Rahul 
ORCID: 0000-0003-1262-7831
(2009)
Spanning connectivity games.
[Report]
(Unpublished)
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
0906.3643v1.pdf - Submitted version Download (184kB) |
Abstract
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.
| Item Type: | Report |
|---|---|
| Additional Information: | AAIM 2009 |
| Uncontrolled Keywords: | cs.GT, cs.GT, cs.CC |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 16 Oct 2017 10:17 |
| Last Modified: | 19 Jan 2023 06:53 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3009867 |
Share
Share
