TY - GEN
T1 - A pseudo-polynomial algorithm for computing power indices in graph-restricted weighted voting games
AU - Skibski, Oskar
AU - Michalak, Tomasz P.
AU - Sakurai, Yuko
AU - Yokoo, Makoto
PY - 2015
Y1 - 2015
N2 - Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices - the Shapley-Shubik index and the Banzhaf index - in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.
AB - Weighted voting games allow for studying the distribution of power between agents in situations of collective decision making. While the conventional version of these games assumes that any agent is always ready to cooperate with all others, recently, more involved models have been proposed, where cooperation is subject to restrictions. Following Myerson [1977], such restrictions are typically represented by a graph that expresses available communication links among agents. In this paper, we study the time complexity of computing two well-known power indices - the Shapley-Shubik index and the Banzhaf index - in the graph-restricted weighted voting games. We show that both are #P-complete and propose a dedicated dynamic-programming algorithm that runs in pseudo-polynomial time for graphs with the bounded treewidth.
UR - http://www.scopus.com/inward/record.url?scp=84947257601&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947257601&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84947257601
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 631
EP - 637
BT - IJCAI 2015 - Proceedings of the 24th International Joint Conference on Artificial Intelligence
A2 - Wooldridge, Michael
A2 - Yang, Qiang
PB - International Joint Conferences on Artificial Intelligence
T2 - 24th International Joint Conference on Artificial Intelligence, IJCAI 2015
Y2 - 25 July 2015 through 31 July 2015
ER -