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

Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, Makoto YokooIJCAI 2015

Abstract

Measuring the influence of individual agents within a group is a central challenge in cooperative game theory. In Weighted Voting Games (WVGs), power indices like Shapley-Shubik and Banzhaf quantify an agent's ability to turn a losing coalition into a winning one. However, real-world cooperation is often constrained by social or communication networks, where only connected subgraphs can form valid coalitions. This paper addresses the computational difficulty of these graph-restricted games, proving the problem is #P-complete and introducing the first pseudo-polynomial algorithm to solve it for networks with bounded treewidth.

Introduction

In a standard Weighted Voting Game, agents possess weights, and any subset of agents whose total weight meets or exceeds a predefined quota is considered a "winning" coalition. Power indices provide a mathematical framework for assessing the true influence of these agents, which often deviates from their nominal weights.

While standard models assume universal cooperation, practical scenarios—ranging from parliamentary alliances to corporate boards—are often limited by geography, trust, or formal communication channels. These limitations are modeled as graph-restricted games. Here, a coalition is only functional if the agents involved form a connected component within a underlying communication graph. This added constraint significantly complicates the calculation of power indices, as one must account for both the weight and the connectivity of every possible subset of agents.

The Complexity of Graph Restrictions

Computing power indices in standard WVGs is already known to be #P-complete. The introduction of graph restrictions makes the problem even more daunting. An agent is considered "pivotal" in a graph-restricted game not only if their weight pushes a coalition over the quota, but also if they act as a critical "bridge" that connects previously disjoint components into a single winning entity.

Previous approaches to this problem were purely exponential, as the number of connected subgraphs in a network can grow massively with the number of agents. This paper formally proves that calculating these indices remains #P-complete in the general case, necessitating a more specialized algorithmic approach for practical application.

Methodology: Tree Decomposition and Dynamic Programming

The authors propose a dedicated dynamic programming (DP) algorithm that leverages the structural properties of the communication network. The core of their approach is the use of tree decomposition, a technique that transforms a complex graph into a tree-like structure of node subsets called "bags."

Figure 1: The process of transforming a communication graph into a tree decomposition and subsequently into a 'nice' tree decomposition for dynamic programming.

The algorithm operates on a "nice" tree decomposition (as shown in Figure 1), traversing the tree from the leaves to the root. At each node in the tree, the algorithm performs one of four operations—LEAF, INTRODUCE, FORGET, or JOIN—to update a data structure tracking the weights and connectivity of coalitions formed by the agents encountered so far.

A key innovation in this method is the handling of "neighbors"—agents outside a specific coalition who are nonetheless connected to it. By deriving new closed-form formulas for the Shapley-Shubik and Banzhaf indices, the authors show that these values can be computed if one can efficiently count connected coalitions based on their size, weight, and neighbor count. They utilize a specific mathematical bijection to integrate this neighbor-counting into the DP framework.

Key Results and Performance

The primary contribution of this work is an algorithm with a time complexity of $O(2^{d^2+d} n^5 q^2)$, where $n$ is the number of agents, $d$ is the treewidth of the graph, and $q$ is the voting quota.

This result is significant because it is pseudo-polynomial. While the complexity grows rapidly with the treewidth ($d$), many real-world networks (such as organizational hierarchies or sparse communication webs) have a low, bounded treewidth. For these structures, the algorithm runs in polynomial time relative to the number of agents and the quota, providing a feasible path for computing power indices where previous methods would fail.

Conclusion and Limitations

This research identifies treewidth as the primary "complexity knob" for graph-restricted voting games. By focusing on the structural "messiness" of the network, the authors provide a tool that is highly effective for sparse or hierarchical systems. However, the algorithm remains computationally expensive for dense graphs (like cliques) where the treewidth is high. Future work may explore the application of these DP techniques to other game-theoretic concepts or different types of cooperation constraints beyond simple connectivity.

Summary updated

BibTeX
@inproceedings{skibski2015pseudo,
  author = {Oskar Skibski and Tomasz P. Michalak and Yuko Sakurai and Makoto Yokoo},
  title = {{A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure