A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games

Skibski, Oskar; Michalak, Tomasz P.; Sakurai, Yuko; Yokoo, Makoto

A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games

Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, Makoto Yokoo

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 631-636.

Abstract

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.

Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, and Makoto Yokoo. 2015. A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 631–636. https://ijcai.org/proceedings/2015/95

@inproceedings{ijcai2015p95,
  title     = {A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games},
  author    = {Skibski, Oskar and Michalak, Tomasz P. and Sakurai, Yuko and Yokoo, Makoto},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {631--636},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/95},
}

TY  - CPAPER
TI  - 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
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 631
EP  - 636
UR  - https://ijcai.org/proceedings/2015/95
ER  -