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.

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 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
Publisher:	Springer
ISBN:	978-3-642-02157-2
ISSN:	0302-9743
Editor:	Goldberg, AV and Zhou, Y
Date:	2009
Volume:	Vol.5564
Number of Pages:	13
Page Range:	pp. 55-67
Identification Number:	10.1007/978-3-642-02158-9_7
Status:	Peer Reviewed
Publication Status:	Published
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
URI:	http://wrap.warwick.ac.uk/id/eprint/27629

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item