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

1 Introduction

Weighted voting games allow for studying the distribution of power between individual agents in situations of collective decision making. Various aspects of these games have been extensively studied in the multi-agent and AI literature [Chalkiadakis et al., 2011]. The research has especially focused on power indices and their computational properties [Elkind et al., 2009]. In this respect, two most prominent power indices, i.e., the Banzhaf power index and the Shapley-Shubik index, were shown to be #P-complete [Prasad and Kelly, 1990; Deng and Papadimitriou, 1994; Chalkiadakis et al., 2011].

Most works in the literature consider the conventional version of coalitional games, and weighted voting games in particular, where it is idealistically assumed that any agent is always ready to cooperate with all others. Recently, however, attention has been drawn to more involved models, with restrictions on agents' ability to cooperate [Napel et al., 2012; Fern´andez et al., 2002]. Such restrictions naturally arise in multi-agent systems due to communication costs, distance, distrust, or other factors [Meir et al., 2011].

Restrictions in cooperation can be conveniently expressed in the form of a graph. A canonical model of graph-restricted coalitional games is due to Myerson [1977]. In this formalism, the graph represents communication links between the agents and cooperation between any two agents is possible if and only if there exists a direct or indirect (i.e., through intermediaries) link between them. This rule naturally extends to coalitions - a coalition can cooperate if and only if all the agents involved induce a connected subgraph of a communication graph. The extensions of the Banzhaf and Shapley-Shubik indices to graph-restricted weighted voting games were proposed by Owen [1986] and Myerson [1977], respectively. Building upon Deng and Papadimitriou [1994], we show that, under graph restrictions, computing both indices is also #P-complete.

Our starting point to develop an algorithm for power indices in graph-restricted weighted voting games is the algorithm for standard weighted voting games by Matsui and Matsui [2000]. In particular, the authors showed that the Banzhaf and Shapley-Shubik indices can be computed in pseudo-polynomial time using the dynamic programming approach, where agents are considered one after the other, and their weights are added to the aggregated data on (weights of) previously generated coalitions.

Unfortunately, with graph restrictions the situation becomes much more involved because we have to account for the fact that an agent must be connected to the coalition he cooperates with. In other words, we cannot add the weight of an agent to aggregated data of previously generated coalitions without checking to which of these coalitions the agent is connected to. This is not an easy task. To perform it, we could use Skibski et al.'s [2014] algorithm for general graphrestricted games that enumerates all connected coalition in the graph. However, as the number of connected coalitions can be exponential, this algorithm can take an exponential number of steps.

Interestingly, however, for graphs with the bounded treewidth, we propose in this paper an algorithm that computes both the Banzhaf and Shapley-Shubik indices in pseudo-polynomial time. To this end, using tree decomposition, we develop a technique that allows to gather needed information about all connected coalitions in polynomial time, even if the number of connected coalitions is exponential. Overall, the time complexity of our algorithm is O(2d2+ddn5 q2 ), where n is the number of agents, d is the treewidth, and q is the voting quota.

2 Preliminaries

Let N be the set of agents. In the classic form, a coalitional game is a tuple (N, v), where v is the characteristic function that assigns a payoff to every coalition S ⊆ N with v(∅) = 0.

Weighted voting games: An important class of coalitional games are weighted voting games. Such a game is defined by a sequence of non-negative integers Q = [q; w1, w2, . . . , wn], where wi is the number of votes (or weight) of agent i, and q is a threshold (quota) needed for a coalition to win. All winning coalitions are assigned the value of 1 while all losing coalitions the value of 0. Formally:

We will denote the set of all winning coalitions in Q by WQ. As common in the literature, we assume that the quota is higher than a half of all votes, i.e., 1 2 ∑i∈N wi < q ≤ ∑i∈N wi. This condition implies that the weighted voting game is proper: if S is a winning coalition, then N\S is a losing one, and does not violate supperadditivity (vQ(S ∪ T ) ≥ vQ(S) + vQ(T) for every disjoint S, T ⊆ N). Typically, we will refer to the coalitional game simply by its characteristic function (e.g., v) or by Q to a weighted voting game.

Graph-restricted games: An implicit assumption embedded in the above definitions is that all agents can cooperate with each other. This is, however, not always the case as there may exists various physical or procedural restrictions on which coalitions are feasible and which are not. A popular model of such a situation was introduced by Myerson [1977]. Formally, Myerson's graph-restricted game is a triple (N, v, G), where G = 〈N, E〉 is an undirected graph and E ∈ N×N 1 is a set of unordered pairs which denote links between agents. G describes the underlining communication structure between the agents with the interpretation that an agent can cooperate only with nodes connected to him directly (called neighbours and denoted N(i)), or through a path. At the same token, coalition S can cooperate if it is connected in G, i.e., any two agents of S are connected in G by a path contained in S. The set of all connected coalitions in G is denoted CG. If S is not connected, the agents in this coalition cooperate in the connected components of S:

Formally, S′ ⊆ S is a maximal connected subset of S in G, if it is connected and there exists no superset S′′ ⊋ S′ connected in G. Given the above, the graph-restricted game, denoted v/G, is defined as follows:

Note that the definition of restricted game is - though not explicitly - based on the assumption that game is superadditive. Otherwise, we would end up with a paradox: the sum of values of coalitions could be bigger than the value they can get together, i.e., graph-restriction would yield better performance.

1A×B denotes the set of unordered pairs (a, b), a ∈ A, b ∈ B.

Graph-restricted weighted voting games: In this paper, we are interested in graph-restricted weighted voting games which combine features of weighted voting games with graph-restricted games [Napel et al., 2012]. Formally, a graph-restricted weighted voting game is a pair (Q, G), where Q is a weighted voting game of agents N, and G = 〈N, E〉 is an underlining communication structure. In these games:

• the value of coalition S is the sum of the values of its connected components S/G (formula (2)); and
• the value of a connected component T ∈ S/G equals 1 only if the sum of weights of its members exceeds the threshold: ∑i∈T wi ≥ q (formula (1)).

Based on the assumption that threshold exceeds half of the sum of weights of all agents, we have that in every coalition S there exists at most one connected component with nonzero value. Consequently:

Consider a winning coalition from game Q which is connected in G. We will denote the set of all such coalitions, called winning connected coalitions, by WC. Formally:

A set of winning connected coalitions with agent i is denoted WCi. Now, rephrasing the definition of characteristic function vQ/G, the coalition is winning in graph-restricted weighted voting games, if it contains a winning connected coalitions, i.e., vQ/G(S) = 1, iff S/G∩WC ̸= ∅.

Power indices: Let us now consider the issue of measuring power of agents in weighted voting games. Two wellknown power indices are the Shapley-Shubik index [Shapley and Shubik, 1954] and the Banzhaf index [Penrose, 1946]. To formalize them, let us denote by Π(N) the set of all permutations of N and by Sπ i the coalition made of agents which are in a permutation π ∈ Π(N) before i. Now, the ShapleyShubik index and the Banzhaf index can be defined as follows, for all i ∈ N:

respectively (we use a normalized version of Banzhaf index proposed by Dubey and Shapley [1979]). Intuitively, both indices remunerate agents by considering the number of times they are pivotal, i.e., how often a given agent changes a losing coalition to a winning one. While the Banzhaf index is a simple average over all coalitions, the Shapley-Shubik index considers all possible orders in which agents could join the game one after the other. Both indices can be applied to an arbitrary coalitional game (N, v) (not only to weighted voting games). In this case the Shapley-Shubik index is called the Shapley value.

Our aim in this paper is to compute the Shapley-Shubik and the Banzhaf indices in graph-restricted weighted voting games, i.e., to compute SSIi(vQ/G) and BIi(vQ/G) for all i ∈ N. We note that the Shapley-Shubik index applied to the restricted game vQ/G has an alternative name, i.e., the Myerson value [Napel et al., 2012], while the Banzhaf index applied to the restricted game vQ/G is also called the restricted Banzhaf index [Owen, 1986]. However, for clarity, we will refer to them the Shapley-Shubik index and the Banzhaf index, respectively.

3 Closed-FormFormulas

Let us now derive more compact closed-form formulas for the indices. They show that the key challenge in computing both indices is to count the number of winning connected coalitions of a given size and with a given number of neighbours.

Recall that the basic idea behind both the Shapley-Shubik index and the Banzaf index is to remunerate agents by considering how often they are pivotal in different coalitions. In conventional weighted voting games, all such situations can be found by considering all coalition that almost reach the threshold - for a given agent i, all sets S ̸∋ i such that q > ∑j∈S ωj ≥ q - ωi [Matsui and Matsui, 2000].

Graph-restricted voting games are more involved since we have to account for the communication structure between the agents. In particular, agent i will not turn loosing coalitions to winning ones if it is not connected to them. On the other hand, i may turn out to be pivotal in a coalition with an arbitrary large sum of weights if, without i, this coalition is disconnected. More precisely, agent i is pivotal in S if:

• (a) S \ {i} does not contain a winning connected coalition, and
• (b) S contains a winning connected coalition.

Thus, agent i must produce a winning connected coalition by connecting some (non-winning) components of S \ {i}, joining a single component, or forming a new singleton component (if ωi > q). Thus, the set of all pivotal winning connected coalition of agent i is defined as follows:

In the two following theorems we provide the general formula for the Shapley-Shubik index and the Banzhaf index in graph-restricted weighted voting games. We define N(S) as a set of neighbours of S: N(S) = (⋃i∈S N(i)) \ S.

Theorem 1. Let (Q,G) be a graph-restricted weighted voting game with the set of winning connected coalitions WC. The Shapley-Shubik index satisfies the following formulas:

Proof. Let us consider formula (4) for the Shapley-Shubik index. Since, by definition, (Q,G) is proper, there are no negative marginal contributions. The only case when agent i ∈ N may be pivotal and have the positive marginal contribution of 1 is when T is a winning coalition, but T \ {i} is losing. Let us denote the set of such coalitions with WT i. Formally: WT i = {T ∈ W | i ∈ T, T \ {i} ̸∈ W}.

Now, we can rewrite formula (4) as follows:

Recall that coalitions in WT i do not have to be necessarily connected, but, from the assumption on q, they have to contain exactly one winning connected coalition: S = WT i∩WCi. Since S\{i} cannot belong toWCi (this would imply that T \ {i} ∈ W), we have that S ∈ PWCi, and:

Let us now compute the number of permutations such that S is a connected component of Sπ i . To this end, all other agents from S have to come before agent i, all neighbors of S after i, and all other agents do not play a role. Simple calculations show that there are (|S|-1)!N(S)! (|S|+|N(S)|)! such permutations which concludes the proof of the first part of the formula.

Now, consider the set difference WCi \ PWCi. This set consists of winning connected coalitions C that, without agent i, contain winning connected component S = C\{i}∩WC. Note that i must be a neighbour of S. Analysing the permutations, we see from the set of permutations that contain winning connected coalitions in Sπ i ∪ {i} we have to exclude those that contain winning connected coalitions adjacent to i in Sπ i :

Now, it is enough to calculate permutations as above.

Theorem 2. Let (Q,G) be a graph-restricted weighted voting game with the set of winning connected coalitions WC. The Banzhaf index satisfies the following formulas:

Proof. The proof is analogous to the one of Theorem 1. For the Banzhaf index, the key formula (8) iterates not over permutations, but coalitions of N that contain S. Thus, calculations are easier - the probability that S forms a component in a random coalition equals 1/2|S|+|N(S)|) , as coalition must contain S, but not a neighbour of S. We omit details due to space constraints.

Algorithm 1: General algorithm for power indices in graph-restricted weighted voting games

Input: Weighted voting game Q = [q; w1, . . . , wn], graph G = 〈N, E〉 Output: Shapley-Shubik index SSIi(vQ/G), and Banzhaf index BIi(vQ/G) of game (Q, G) 1 calculate table Ai; 2 for s ← 0 to |N| do 3 for k ← 0 to |N| - s do 4 for w ← q to ∑j∈N ωj do 5 SSIi(vQ/G) ←SSIi(vQ/G)+ WCi[s, k, w] (s-1)(k)! (s+k)! -NWCi[s, k,w] (s)(k-1)! (s+k)! ; 6 BIi(vQ/G) ←BIi(vQ/G)+ WCi[s, k,w] 1 2s+k -NWCi[s, k,w] 1 2s+k ;

Before we move on to our main algorithm, we introduce the general scheme for calculating both power indices. Looking at the formulas from Theorems 1 and 2, we see that it involves enumerating two sets: WCi and NWCi = {S ∈ WC | i ∈ N(S)}. Set NWCi is the set of all winning connected coalitions that contain at least one neighbour of agent i, but not i itself. Now, each element of both sets contributes to the power index a value which depends on the size of the set and number of neighbours. Thus, for a given set of connected coalitions A ⊆ C, we will associate a table A[] such that A[s, k, w] is the number of connected coalition of size s with k neighbours and sum of weights w:

Algorithm 1 presents the general scheme for calculating the indices using tables WCi[] and NWCi[]. Our main algorithm presented in the next section will focus on calculating both tables. We end this section with the complexity result.

Proposition 1. Calculating the Shapley-Shubik index and Banzhaf index in graph-restricted weighted voting games is #P -complete. 2

Proof. Deng and Papadimitriou [1994] proved that calculating the Shapley-Shubik index in the standard weighted voting games is #P-complete (similarly, the Banzhaf index). This problem can be reduced to our problem, as it can be modelled using a complete graph as a restriction. Finally, computing n!SSIi(vQ/G) and 2N-1BIi(vQ/G) can be considered as the number of accepting paths of nondeterministic Turing machine, so both problems are in class #P , and - because of the reduction - they are #P -complete.

2#P is the set of counting problems associated with the decision problems in the set NP. A problem is #P-complete if and only if it is in #P and every problem in #P can be reduced to it by a polynomial counting reduction [Valiant, 1979].

4 Traversing Induced Connected Subgraphs

The key challenge in implementing the formulas from the previous section is to count the number of winning connected coalitions of a given size and with a given number of neighbours. In this section, we propose a pseudo-polynomial algorithm that does this task in graphs with bounded treewidth.

We start with some basic definitions. Given a graph G = 〈N, E〉, the tree decomposition is a tree 〈X, T 〉 such that, with each node x ∈ X, a subset of N is associated, denoted Bx, and such that the following three conditions are satisfied:

1. for every node i ∈ N, i ∈ Bx for some x;
2. for every edge (i, j) ∈ E, {i, j} ⊆ Bx for some x;
3. for every node i ∈ N, nodes x such that i ∈ Bx form a subtree of 〈X, T〉.

The width of the tree decomposition is the size of the biggest set of nodes minus one. Now, the treewidth of the graph is the minimum width among all possible tree decompositions. Even though finding the tree decomposition with the minimal treewidth is NP-hard, a heuristic method is able to find one with reasonably small treewidth [Bodlaender, 1996].

A rooted tree decomposition is called nice if every node x is of one of the four types:

• LEAF: no children and |Bx| = {v} for some v;
• INTRODUCE: one child y with Bx=By∪{v} for some v;
• FORGET: one child y with Bx = By \ {v} for some v;
• JOIN: two children, y1, y2, such that Bx = By1 = By2 .

See Figure 1 for an example. Any tree decomposition of width d and n nodes can be turned into a nice tree decomposition of width d and O(dn) nodes in time O(d2n) [Kloks, 1994]. Thus, without the difference for the time complexity of our algorithm, we consider only nice tree decompositions.

In our problem, we aim to find all winning connected coalitions (those containing agent i or adjacent to him). In the graph notation, connected coalitions correspond to induced connected subgraphs - graph 〈S, M〉 is an induced connected subgraph of 〈N, E〉 if S ⊆ N and M = (S × S) ∩ E consist of all edges between nodes from S that appear in E. We will not discuss not-induced subgraphs; hence, we will often skip this word. The goal of our algorithm is to find all (induced) connected subgraphs with given properties.

Assume that 〈X, T〉 is a nice tree decomposition such that node i is in the set Br of the root r ∈ X. In our algorithm, we will traverse the tree decomposition bottom-up and, for every node, construct a data structure cx based on the data structures of the children. However, accounting for all connected subgraphs based only on children is far from trivial. Consider the following example that corresponds to INTRODUCE node with i added to set {j, k}.

Example 1. Let G = 〈N,E〉 be a graph and let X = {i, j, k} ⊆ N. We denote by cx(S) the number of induced connected subgraphs that contain exactly nodes S ⊆ X. Now, assume node i has only two neighbours j and k, not connected directly to each other. Based on the information about connected subgraphs of j and k (without i), we would like to calculate the number of connected subgraphs with i. We can easily see that cx({i}) = 1, cx({i, j}) = cx({j}) and cx({i, k}) = cx({k}). Consider cx({i, j, k}). If j and k are connected only by i (i.e., cx({j, k}) = 0), then the number of induced connected subgraphs that contain all three nodes can be easily calculated: cx({i, j, k}) = cx({j}) · cx({k}). However, if j and k are connected with a path that does not go through i, then this number cannot be determined based on cx({j}), cx({k}) cx({j, k}). To see that, consider two graphs from Figure 2. While the cx({j}) = cx({k}) = 6 and cx({j, k}) = 5 for both graphs, the number cx({i, j, k}) equals 7 for the left graph and 6 for the right one.

To tackle this problem, we provide the following observation. The proposition below states that, to account for all induced connected subgraphs with an additional node, it is enough to consider all induced connected subgraphs of a graph with all possible edges between nodes connected to the new node. While, in general, it is an exponential task, given a bounded treewidth, it will require the exponential number of steps, but only in respect to the treewidth.

Proposition 2. Let G = 〈N, E〉 be a graph, and i ∈ N be a node. Then, there exists a bijection between a set of induced connected subgraphs with i ∪ N(i) in graph G, and induced connected subgraphs with N(i) in graph G′ obtained by removing node i and connecting nodes from X in clique.

Let us describe our algorithm, the pseudocode of which is presented in Algorithm 2. For clarity of presentation, we focus first on the algorithm that calculates set WCi. Later, we discuss a simple modification that allows for computing set NWCi simultaneously. In Algorithm 2, we find first the tree decomposition 〈X, T 〉 and adjust it in such a way that the root

Algorithm 2: DP-algorithm calculating table WCi

Input: Weighted voting game Q = [q; w1, . . . , wn], graph G = 〈N, E〉 with treewidth d, agent i Output: Table WCi[] 1 find a nice tree decomposition 〈X, T〉 of G with width d and root r such that i ∈ Br; 2 add Forget nodes, so that Br = {i} for root r; 3 S ← empty stack; // main stack with nodes from X 4 Q← empty queue; // auxiliary queue to build S 5 Q.add(root r); 6 while Q is not empty do // building S top-down 7 x ←Q.pop(); 8 Q.add(children of x); 9 S.add(x); // we are traversing tree 〈X, T〉 bottom-up 10 while S is not empty do 11 x ←S.pop(); // all children of x are processed 12 switch type of x do 13 case LEAF: (with Bx = {v}) 14 cx(∅, ∅) = ∅; 15 cx({v}, ∅) = {(1, 0, ωv)}; // tuple (s,k,w) 16 case INTRODUCE: (with child y and v = Bx \ By) 17 foreach S ⊆ By, M ⊆ 2By×By , Nv ⊆ By do 18 Mv ← (v ×Nv); 19 if S ∩ Nv ̸= ∅ then 20 foreach (s, k, w) ∈ cy(S, M) do 21 cx(S, M ∪ Mv ).add((s, k + 1, w)); // based on Proposition 2 22 foreach (s, k, w) ∈ cy(S, M ∪ (Nv × Nv)) do 23 cx(S ∪ {v}, M ∪Mv ).add((s + 1, k, w + ωv )); 24 else 25 cx(S, M ∪ Mv) = cy(S, M); 26 if S ̸= ∅ then cx(S ∪ {v}, M ∪ Mv) = ∅; 27 else cx(S ∪ {v}, M ∪ Mv) = {(1, |Mv|, ωv)}; 28 case FORGET: (with child y and v = By \ Bx) 29 Mv ← {(v, j) ∈ E | j ∈ Bx}; // real edges 30 foreach S ⊆ Bx, M ⊆ 2Bx×Bx do 31 cx(S, M) = cy(S, M∪Mv)∪cy(S∪{v},M∪Mv); 32 case JOIN: (with children y1, y2) 33 foreach S ⊆ Bx, M ⊆ 2Bx×Bx do 34 if S ̸= ∅ then 35 foreach (s1, k1, w1) ∈ cy1 (S, M) do 36 foreach (s2, k2, w2) ∈ cy2 (S, M) do 37 s ← s1 + s2 - |S|; 38 k ← k1 + k2 - |{(S × Bx) ∩ M}|; 39 ω ← ω1 + ω2 - ∑i∈S ωi; 40 cx(S, M).add(s, k, ω); 41 else cx(S,M) = cy1 (S,M) ∪ cy2 (S,M); 42 return cx({i}, ∅); // x = root of 〈X, T〉 here

node r consists of only agent i: Br = {i} (lines 1-2). Then, we prepare stack S with all nodes in a bottom-up order, i.e., in such a way that children are processed before their parent (lines 3-8). Technically, we do it by going through the tree in a top-down order, and by adding children at the top of the parent in the stack. Then, our main loop starts.

In each step of the main loop, we calculate data structure cx for node x ∈ X based on the data gathered in children nodes. Let us denote by B∗ x the set of nodes that appear in a subtree rooted at x. For a given subset of (potential) edges 3 M ⊆ (Bx × Bx), consider a graph G restricted to nodes B∗ x and with the edges between Bx replaced by M. Now, for each subset of nodes S ⊆ Bx, in variable cx(S,M), we store (parameters of) all connected coalitions of this graph that intersect with Bx on S. Let us define the following set:

Then, cx(S,M) is a multiset

Before we proceed, note that only the FORGET case involves real edges of graph G. This is because, until we remove a node, we have to consider all possible edges between it and other nodes in order to apply the technique from Proposition 2. When we remove the node, because of the tree decomposition structure, we know it will not occur again.

Let us now briefly describe all four cases of nodes. The LEAF case (lines 12-14) is trivial. In the INTRODUCE case (lines 15-26), in order to extend structure to another node for every pair (S,M), we consider also any Nv ⊆ By so that we account for all possible edges that v can have. Now, if - in given scenario with M∪(v×Nv) edges - v is connected to S, then every subgraph with S gains a new neighbour (lines 1920). To count subgraphs that contain S ∪ {i}, we use the technique from Proposition 2. On the other hand, if v is not connected to S, then coalitions with S are just copied, and S ∪ {v} exists only if S is empty.

The FORGET case (lines 27-30), as discussed above, is the only one that uses real edges of graph G. When forgetting node v, for each subset of nodes S, we join connected subgraphs that, in the child node, were assigned to S and to S ∪ {v}.

In the JOIN case (lines 31-40), node x has two children. Consider two subgraphs - one from each child - that contain exactly S (S is connected according to some set of edges M). The important observation is that the intersection of both these subgraphs is also set S. In other words, subgraphs cannot intersect outside of S. This is because, from the tree decomposition definition, if some element would appear in both children's subtrees, then it must appear in their parent node. The same applies to joined neighbours - they are limited to set Bx. Thus, every pair yields a new connected subgraph with sum of values decreased by the intersection - S. However, if intersection S is an empty set, then subgraphs cannot be merged, and sets of subgraphs are simply added. Finally, variable cx({i}, ∅) consists parameters of all connected subgraphs with i, and cx(∅, ∅) - without i (line 41). Note, however, that we cannot easily distinguish those that contain neighbours of agent i, i.e., set NWCi. Let us describe below a simple modification that allows for finding this set simultaneously.

3 We note that we could only consider sets of edges M that include the real set of edges between Bx × Bx. For the clarity of presentation we consider all possible sets.

To this end, we add the fourth element a to the tuple of parameters stored in cx(S,M). Now, a = 1 if connected subgraph contains a neighbour of i, and 0 otherwise. Updating this information is easy - whenever we add a new tuple (lines 14, 26), we set it to 0. When we join two coalitions (lines 36-39), we take a maximum of both values. Now, when forgetting a node v, if v is a neighbour of i, then, in all sets that contained v (cx(S ∪ {v},M ∪ Mv) in line 30), we update the value of a to 1. At the end, NWCi consists of all tuples from cx(∅, ∅) with a = 1 (line 41). This modification does not change the complexity of the algorithm.

Time and Space Complexity: Let n = |N|. Crucial for the time and space complexity is the data structure used for multiset cx(S,M). Here, we assume that cx(S,M) is a threedimension table [0..n+1][0..n+1][0..2q], where q is a threshold and the dimensions corresponds to the size of the coalition, number of neighbours and sum of weights. Thus, for every possible tuple (s, k,w) we store the number of occurrences. That way, we are achieving pseudo-polynomial time and space complexity. Note that for special cases - for example, when the number of connected subgraphs is polynomial in n - different data structure may be better and lead to real polynomial time.

Let us consider the time complexity of our algorithm. The initialization (lines 1-9) has complexity O(d2n) (for n = |N|) and produces a tree decomposition with at most O(dn) nodes. Thus, the main loop has O(dn) iterations. In the LEAF case, we performO(1) steps. In the JOIN case, for every subset of Bx (O(2d )) and subset of possible edges between Bx (O(2d2 )), we have to multiply two cx structures (O(n4 q2 )), which overall gives time O(2d2+dn4 q2 ). Analogous analysis leads to O(2d2+2dn2 q) and O(2d2+dn2 q) for the INTRODUCE and FORGET cases, respectively. Thus, each iteration have complexity O(2d2+dn4 q2 ). Overall, the time complexity of our algorithm is O(2d2+ddn5 q2 ) which yields pseudopolynomial time if d is bounded.

As for the space complexity, note that in every node of tree decomposition we store 2d2+d arrays of size O(n2 q). As there are at most O(dn) nodes, the space complexity is O(2d2+dn2 q).

5 Related work

One of the main motivations behind the graph-restricted weighted voting games is modelling the political alliances - a topic that raised considerable attention in the literature. The first computational analysis is due to Fern´andez et al. [2002] who proposed polynomial time algorithms for Banzhaf and Shapley-Shubik indices for trees based on generating functions. Palestini [2005] proved, that under some strong condition on the set of winning coalitions, Shapley-Shubik index can be calculated in graph-restricted weighted voting games in the polynomial time. Recently, Napel et al. [2012] performed the (non-computational) monotonicity analysis of power indices graph-restricted weighted voting games.

In a related work, See et al. [2014] introduced compatibility weighted voting games, where all winning coalitions have to be cliques. Aziz et al. [2009] considered computational complexity of the power indices in the spanning connectivity game. Here, however, agents are represented by edges, not nodes.

Game-theoretic solution concepts, such as the Banzhaf index and the Shapley-Shubik index have been used as an advanced centrality measures [Gomez et al., 2003; Michalak et al., 2013; 2015]. Thus, our paper directly contributes to this growing body of literature (see Tarkowski et al., [2015] for an overview).

6 Conclusions

In this paper, we studied the problem of computing the Shapley-Shubik index and the Banzhaf index in graphrestricted weighted voting games. For graph with a bounded treewidth, we introduced a general technique for traversing all induced connected subgraphs in polynomial time. We used it to design a pseudo-polynomial algorithm for both indices. In our future work, we would like to study computational properties of other power indices under graph restrictions.

Acknowledgements

Oskar Skibski and Makoto Yokoo were supported by JSPS KAKENHI Grant (24220003) and Yuko Sakurai was supported by JSPS KAKENHI Grant (15K12101). Tomasz Michalak was supported by the European Research Council under Advanced Grant 291528 ("RACE") and the Polish National Science grant DEC-2013/09/D/ST6/03920.