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. ISBN 978-3-642-02157-2. doi:10.1007/978-3-642-02158-9_7 ISSN 0302-9743.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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, Engineering and Medicine > 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
Official Date:	2009
Dates:	Date Event 2009 Published
Volume:	Vol.5564
Number of Pages:	13
Page Range:	pp. 55-67
DOI:	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

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item