We analyze the problem of computing the Banzhaf and Shapley power indices for graph restricted voting games, defined in a particular class of graphs, that we called line-clique. A line-clique graph is a model of a uni-dimensional political space in which voters with the same bliss point are the connected vertices of a clique and then other arcs connect nodes of consecutive cliques. The interest to this model comes from its correspondence to the spatial voting game: a model that has been proposed and used by political analysts to understand nations’ behavior and the political outcome of the bargaining process within the EU Council. Broadly speaking, the computation of a power index of a graph restricted game is strongly #P-complete, as it includes the enumeration of all winning coalitions. Nevertheless, we show that in this special class of graph coalitions can be enumerated by dynamic programming, resulting in a pseudo-polynomial algorithm and proving that the problem only weakly #P-complete. After implementing our new algorithms and finding that they are very fast in practice, we analyze the voting behavior in the EU Council, as for this application previous research compiled a large data set concerning nations’ political positions and political outcomes. We will test whether voting power has an effect on the political outcome, more precisely, whether nations that are favored by their weight and position can influence the political outcome to their advantages. Using linear regressions, we will see that unrestricted power indices are not capable of any predictive property, but graph restricted indices are. The statistic evidence shows that the combination of voting weight and network position is a source of power that affects the political outcome to the advantage of a country.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
A voting game is a cooperative game in which a set of voters, or players, having different weights, must make a yes-or-no decision on a proposal. The proposal is accepted if it is supported by a number of votes at least equal to a fixed majority threshold. Voters are endowed with different weights, so their vote can be more or less important to approve the proposal. Player’s voting power is its ability to influence the approval or the rejection of the issue and it depends on its possibility of forming winning coalition. Every time that the voter can join a loosing coalition and let it win, it expresses an influence to the vote results, and the greater is the number of such coalitions, the greater is the player’s power. This is the underlying idea behind most voting power indices proposed in the literature, the most famous being the Shapley-Shubik index (1954), and the Banzhaf index (1965). The calculation of both indices requires the enumeration of all coalitions, e.g. all subsets of voters, but they are an exponential numbers and it has been formally proved that this enumeration is NP-complete and #P-complete, Prasad and Kelly (1990). Still, the indices can be calculated efficiently using dynamic programming, Matsui and Matsui (2001), generating functions, Bilbao et al. (2000), or accurately approximated by the multilinear extension, Leech (2003).
The standard definition of power indices assumes that all coalitions will form with the same probability, defining what are called the a-priori or unrestricted power indices. In these models no assumption is made about voters’ preferences: This is an assumption that has been often criticized, see for example Garrett and Tsebelis (1999), as there are real applications in which voters’ preferences take a strong role in coalition formation. For example in Western Parliaments coalitions between left-wing and right-wing parties excluding the central ones are hardly seen. Therefore, realistic political analysis should consider that some coalitions are more probable than others and the power definition should be modified accordingly.
Anzeige
Researchers have addressed unequal coalitions probability by: (i) Restricting the family of feasible coalitions, Rodriguez-Veiga et al. (2016), for example imposing that some voters always vote in opposite directions, Alonso-Meijide et al. (2015) and Yakuba (2008), or also assuming that voters form a-priori unions before casting their votes, Alonso-Meijide et al. (2009), Amer et al. (2002) and Leech and Leech (2006; ii) Assuming that some coalitions are more probable than others, for example when voters are located in Euclidean political spaces the most likely coalitions are composed of voters that are close to each other, Benati and Vittucci Marzetti (2013), Passarelli and Barr (2007) and Mielcova (2016). One of these models is relevant here: It is the spatial voting game proposed in Pajala and Widgrèn (2004), for which a large set of empirical data has been collected, Thomson et al. (2012; iii) Assuming that voters are embedded in a communication graph, in which the vertices represent voters and the edges represent communication links. In this family of models a coalition is feasible if and only if the coalition induces a connected subgraph. These models have been introduced in Myerson (1977) and applied to voting situations in Alonso-Meijide and Fiestras-Janeiro (2006), Benati et al. (2015), Chessa and Fragnelli (2011), Fernandez et al. (2002), Skibski et al. (2015) and Álvarez Mozos et al. (2013), where they have been called graph restricted games or spectrum games, to emphasize that voters are located on a political spectrum.
In this paper, we consider the computation of Banzhaf and Shapley indices for graph restricted voting games, defined to a particular class of graphs that we call line-clique graphs. In these graphs, voters are located on consecutive cliques posed along a line, as if voters were located in a 0–1 political segment and they could share the same political position. The practical interest to these graphs is that they exactly describe the spatial voting game proposed in Pajala and Widgrèn (2004) to model nations’ positions and the bargaining process of the Council of the European Union. This model has been used for empiric political analysis, Badinger et al. (2014), Leinaweaver and Thomson (2014) and Schneider et al. (2010), as, based on this model, an interesting data set of empirical observations is available, Thomson et al. (2012).
The paper is structured as follows: In the first part of the paper, after defining power indices and graphs, we discuss the application of #P-completeness theory to the calculation of power indices, Matsui and Matsui (2001) and Prasad and Kelly (1990), outlining that the theory excludes the possibility of algorithms calculating power indices in polynomial time. The technical reason is that an index of power must enumerate and count how many coalitions have a given property, that is, in how many coalitions a player i is a swing voter. Excluding polynomiality means that there is no fast way of counting the number of such coalitions. However, the #P-completeness theory separates counting problems that are #P-complete in the weak sense from problems that are #P-complete in the strong sense, Jerrum et al. (1986) and it has important consequences for the algorithm design. Basically, what separates the two classes is the possibility of using dynamic programming for an exact counting. If a problem is #P-complete in the weak sense, then we can apply dynamic programming principles to devise pseudo-polynomial algorithms (algorithms that are linear with respect to the size of the input data, instead of being log-linear as required by being polynomial), that, even though not fully efficient from a theoretical point of view, they are very fast in practice, see Bilbao et al. (2000) and Uno (2012). Conversely, strong #P-complete problems exclude even the possibility of pseudo-polynomial computation and for those cases, calculating the number of coalitions can be done only through simulations, Castro et al. (2009), Castro et al. (2017) and Benati et al. (2019). Unfortunately, it has been proved in Benati et al. (2015) that indices of graph restricted voting games are strong #P-complete problems. However, in that paper it has also been found that counting coalitions can be weak #P-complete if the graph has a peculiar structure. So, at present some pseudo-polynomial algorithms were proposed for same specific cases: For example, when the graph is a tree, Benati et al. (2015), or has bounded tree-width, see Skibski et al. (2015). A further graph class admitting pseudo-polynomial algorithms is introduced here: the line-clique graphs1.
In the second part, after having coded the dynamic programming as Fortran/R subroutines, the power indices are applied to the EU negotiations data set described in Thomson et al. (2012). So, power distributions among European countries can be analyzed and different indices compared. We will see that unrestricted indices, that is, indices not considering spatial location, can be empirically interpreted as an average of those graph restricted, as theoretically advanced in Passarelli and Barr (2007). Then, we will see that, when applied to decision processes, graph restricted indices are better predictors of the outcomes of the negotiation processes, perhaps because restricted indices are measuring in a more realistic way the real political forces underlying the bargaining processes.
Anzeige
2 Voting models and power indices
2.1 Voting models with preferences
In a voting game, or weighted majority game, Peleg and Sudholter (2007), a set of voters \(V = \{1, \ldots , n\}\) must make a yes-or-no decision on a given issue and each voter \(i \in V\) controls \(w_i \in {\mathbb {N}}\) votes. Voters form coalitions \(S \subseteq V\), whose electoral weight is: \(w(S) = \sum _{i \in S} w_i\). Let \(W = w(V)\) be the total weight, let \({\overline{q}}\) be the majority threshold (with \({\overline{q}} > W/2\)), decisions are approved if supported by a majoritarian coalition S for which \(w(S) \ge {\overline{q}}\).
It is well known that voting weights do not correspond to voting power, as the small voters can be as necessary as the big ones to let coalitions win. Voter’s power is assumed to rely on the property of being critical (or pivotal, or swinging): Player i is said to be a critical voter for a coalition \(S \subseteq V - \{i\}\) if and only if \(S \cup \{i\}\) is winning, but S is not (and S is said i-critical).
The game characteristic function\(v:2^V \rightarrow \{0,1\}\) is such that \(v(S) = 1\) if \(w(S) \ge {\overline{q}}\), and \(v(S) = 0\) otherwise. Player i is a critical voter for coalition S if and only if:
The two measures of power rely on different axiomatic assumptions, Shapley (1953) and Dubey and Shapley (1979), whose mathematical content is not discussed here. What is important is that those axioms are based on different political behaviors and this may circumscribe the applied cases in which one index is more appropriate than the other. The Banzhaf index 3 assumes that all coalitions are equally likely: Voters are characterized by the same one-half probability of supporting or rejecting the proposal. Instead, the Shapley index assumes that all sequences of voters are equally likely. That is, it is assumed that all voters will vote “yes”, but they cast their preference in sequence. The first voter begins the sequence and then it is followed suit by another voter, forming a sequence whose size increases progressively. The sequence defines nested coalitions whose weights increase as well, to the point that there will be a specific voter i that let the sequence overcome the majority threshold. In this case, i is critical for the sequence. Then, the Shapley index 5 stands for the probability of forming a i-critical sequence.
Formulas 3 and 5 assumes that all coalitions or all sequences are equally likely, so that they exclude the possibility that voters have preferences over the outcome. This is not always the case, as it may happen that a left-wing party is less willing to vote a right-wing law than the right-wing party itself. There has been a lively debate among political scientists about the possibility of introducing preferences into power measurements, see for example Steunenberg et al. (1999), Braham and Holler (2005) and Napel and Widgrén (2004, 2005, 2006, 2011). When resolved, the proposal is to represent voters’ preferences as bliss points on a political space, and then voters form coalitions (or sequences) constrained by their position, see Passarelli and Barr (2007), Barr and Passarelli (2009), Benati and Vittucci Marzetti (2013), Badinger et al. (2014), Blockmans and Guerry (2015), Peters and Zarzuelo (2016) and Martin et al. (2017). Among the models above, we refer specifically to the spatial voting game presented in Pajala and Widgrèn (2004). There, voters’ bliss points are located on the unit length segment (0–1), with the possibility of more than one voter placed in the same position, see Fig. 2. Then coalitions are feasible or unfeasible depending on their structure, with proximity playing a central role. As will seen, the mathematical structure of this model is equivalent to a voting game restricted to a particular graph and, recognizing this property, the Banzhaf and Shapley index can be formally defined.
The graph restricted voting game, as defined in Benati et al. (2015), in an application to voting situation of a general theory presented in Myerson (1977). A graph \({\mathcal {G}} = (V,E)\) is given, in which every node (or vertex) \(i \in V\) represents a voter and each edge (undirected link) \((i,j) \in E\) represents the communication link between voters \(i,j \in V\). Coalition \(S \subseteq V\) is feasible if and only its induced subgraph \({\mathcal {G}}[S] = (S,E[S])\) is connected, i.e. there is a path between any pair of nodes in \({\mathcal {G}}[S]\). We denote with \({{{\mathcal {F}}}}\) the set of all connected coalitions.
To model the above mentioned spatial voting games, we restrict the analysis to a peculiar class of graphs, which we call line-clique.
Definition 1
(Line-clique graphs) The line-clique is a class of graphs \({\mathcal {G}} = (V,E)\) where nodes can be partitioned into subsets \(V_1 \cup \ldots \cup V_m\) such that:
1.
for every subset \(V_c\), \(c = 1,\ldots ,m\), the induced subgraph \({\mathcal {G}}[V_c] = (V_c,E[V_c])\) is complete, that is, there is an edge \((i,j) \in E[V_c]\) for all \(i,j \in V_c\);
2.
nodes of consecutive subsets are connected, that is:
(a)
there is an edge \((i,j) \in E\) for every pair of nodes \(i \in V_c\), \(j \in V_{c+1}\) for all \(c=1,\ldots , m-1\);
(b)
there is no edge \((k,l) \in E\) for any pair of nodes \(k \in V_i\), \(l \in V_{j}\), for all \(|i-j| \ge 2\).
Figure 1 shows an example of a line-clique graphs.
Fig. 1
Example of line-clique graph: All node pairs of two consecutive cliques are connected
×
To recognize the equivalence of the model in Pajala and Widgrèn (2004) in Fig. 2 and the model 1, it is sufficient to recognize that nations having the same bliss point on the political space are nodes of the same clique \(V_c\) of the graph-restricted game and that the proximity between two voters in the political space is translated as a connection in the line-clique graph. Then, the spatial model assumes that: “..the connected coalition is a coalition formed by members that are adjacent to each other in a unidimensional policy space... ”, (Pajala and Widgrèn 2004, pag. 77). So adjacency in the line is a property that can be interpreted as connectivity in the graph:
Lemma 1
Each feasible coalition of the spatial voting game is a connected coalition of the line-clique graph.
Fig. 2
Position of the political actors in the controversy about the auctioning of carbon credits in the proposed directive on emission allowances in the aviation sector (COD/2006/304). Source: Thomson et al. (2012)
×
2.2 Power on graph-restricted voting games
Some further definitions are needed. From a non connected coalition S we can extract connected components Q’s:
Definition 2
(Component) A voters subset Q, \(Q \subseteq S \subseteq V\), is a component of S if the induced subgraph \({\mathcal {G}}[Q]\) is a maximal connected subgraph of \({\mathcal {G}}[S]\).
In a line-clique graph, connected coalitions are composed of nodes of consecutive cliques: More formally, if a connected coalition Q is such that \(Q \cap V_r \ne \emptyset \) and \(Q \cap V_t \ne \emptyset \), with \(r \le t\), then \(Q \cap V_c \ne \emptyset \) for all c such that \(r \le c \le t\). There is the first and the last clique, that we define as the leftmost and the rightmost.
Definition 3
(Leftmost and rightmost clique) Given a connected coalition Q, its leftmost clique is:
Note that in the summation it is not required that S is connected.
To define the Banzhaf index of the spatial voting game, Pajala and Widgrèn (2004) argued that winning coalition must be connected. So, in the calculation of the marginal contribution of player i, subsets \(S \cup \{i\}\) that are not connected should not be considered and then the non-normalized Banzhaf index of voter i is:
$$\begin{aligned} P_{\mathcal {G}}(i) = \sum _{\begin{array}{c} S \subseteq V - \{i\}\\ S \cup \{i\} \in {{{\mathcal {F}}}} \end{array}} \Big ( v_{\mathcal {G}}(S \cup \{i\}) - v_{\mathcal {G}}(S) \Big ). \end{aligned}$$
(8)
The correspondent (relative, or normalized) Banzhaf index is given by:
Observe that the summation is taken only for coalitions \(S \cup \{i\}\) that are connected and note also that in the summation S can be connected or unconnected.
From definitions (9) and (7), it can be seen that a voter has power for two reasons. The first is its coalitional power: Voter i joins a loosing but connected coalition and makes it win thanks to its weight. But in graph restricted games there is a positional power too: Voter i links two otherwise unconnected loosing coalitions and make them win. It is useful to define formally the two occurrences:
Definition 4
(Coalitional power) The voter i has coalitional power with respect to a coalition S (\(i \notin S\)) if \(S \in {{{\mathcal {F}}}}\), \(w(S \cup \{i\}) \ge {\overline{q}}\) and \(w(S) < {\overline{q}}\).
Definition 5
(Positional power) The voter i has positional power with respect to an unconnected coalition S (\(i \notin S\)) if \(S \notin {{{\mathcal {F}}}}\) and
The #P and #P-complete complexity classes play an important role in cooperative game theory and they have important consequences is in the algorithm design, in a way that is symmetric to the role of the NP (and NP-complete) complexity classes in combinatorial optimization. To define NP-complexity classes, a combinatorial problem is formulated as an existential question, regarding whether there is at least one solution satisfying some properties. The answer to the question must be YES or NO. In voting games, such question is whether there is at least one coalition for which a player i would be critical. However, the binary answer to this question is too weak for a voting game. To calculate an index of power, we must also count how many solutions are satisfying some properties: How many coalitions are there for which i would be critical.
More formally, given a voting game with threshold \(\bar{q}\) and voters’ weights \(w_1,\ldots , w_n\), a coalition S is i-critical if:
PIVOT Prasad and Kelly (1990), Given a voting game with threshold \(\bar{q}\), voters’ weights \(w_1,\ldots , w_n\) and a player i, \(1 \le i \le n\): Is there at least one coalition S that is i-critical?
The problem above is actually a decision problem whose answer is YES or NO. It belongs to the NP-complexity class, as, whenever the answer is YES, the coalition S offers a compact certificate of correctness that can be verified in polynomial time by a deterministic Turing machine. That is, we can code a polynomial algorithm that can check the correctness of the answer YES. Moreover, in Prasad and Kelly (1990) it has been also proved that PIVOT is also NP-complete, as another NP-complete problem, the SUBSET SUM, can be reduced to it.
We remark again that the existence of an i-critical coalition is not enough to calculate an index of power. Rather, we must also know how many i-critical coalitions are admitted by the game structure and therefore we are naturally interested to counting problems. The relevant complexity class of counting problems is #P (pronounced “sharp-pi”), introduced in Valiant (1979).
The correct problem statement that we are interested in is:
COUNTING PIVOT Given a voting game with threshold \(\bar{q}\), voters’ weights \(w_1,\ldots , w_n\) and a player i, \(1 \le i \le n\): how many coalitions S are there that are i-critical?
Here, the answer is an integer number, not a binary decision YES or NO. Clearly, COUNTING PIVOT is at least as difficult as PIVOT, because if the integer number is strictly greater than zero, then the answer to PIVOT is YES.
Having posed that the true question is about counting rather than about existence opens a realm of different complexity classes, namely the ones that are in #P. Technically, #P is defined through another hypothetical device: the counting non- deterministic Turing machine. This is an imaginary machine that, in parallel, is able to explore all solutions satisfying given properties, with the depth of the computation tree (length of each single thread) remaining polynomial. Stated less technically, a given problem is in #P if verifying the correctness of one single solution can be done in polynomial time by a deterministic Turing machine, e.g. by a computer program.
Treating the problem as a counting and then classifying it through its membership to the main #P subclasses has a profound impact in algorithm design. Some #P problems are polynomially solvable, but they are very rare, most of them form the #P-complete class, that is, the counting problems that cannot be solved in polynomial time unless P=NP. In voting games, COUNTING PIVOT is an example of a #P-complete problem, see Prasad and Kelly (1990).
Similarly to the NP-complete, the #P-complete complexity class can be further refined into the #P-complete problems in the strong or in the weak sense. A counting problem is #P-complete problem in the strong sense if it remains #P-complete even when in the input the numbers are encoded in unary rather than in binary. Equivalently, it remains #P-complete even when restricted to instances in which the numbers magnitude is bounded by some polynomial in the input length. This rather technical definition separates the weak #P-complete problems from the strong ones and has deep implications in the algorithm design. It implies that, if a problem is weakly #P-complete, its difficulty lays only in the magnitude of the numbers in the input, but not in its inherent combinatorial structure. Regarding the algorithm design, these problems can be frequently solved by dynamic programming, leading to pseudo-polynomial time algorithms2 that usually perform very well in practice. For example counting i-critical coalitions can be done in pseudo-polynomial time: An analysis of the dynamic programming method of Uno (2012), or the generating function of Bilbao et al. (2000), reveals that the worst case computation time depends polynomially on the term \(W (=\sum _j w_j)\), instead of some function of \(\log W\) as required to an algorithm to be polynomial.
Conversely, when a problem is strongly #P-complete problems, the algorithm design must follow a complete different approach. In cooperative games one possibility is the use of estimation and/or simulation, Leech (2003); Castro et al. (2017); Benati et al. (2019). For example, the Shapley value is an average of marginal gains over sequences, so it can be estimated from a sample of sequences, e.g., simulating the process by which voters cast their vote.
Regarding the complexity of graph-restricted voting games, in Benati et al. (2015) it has been proved this hierarchy of difficulties: (i) if the graph is a tree, the problem is #P-complete in the weak sense and power indices can be calculated by dynamic programming; (ii) if the graph has no structure, the problem is #P-complete in the strong sense and no pseudo-polynomial algorithms can calculate the indices.
In what follows, we show that computing Banzhaf and Shapley indices in line-clique graphs is #P-complete in the weak sense: We prove it describing two dynamic programming algorithms that run in pseudo-polynomial time. Next, we will see how to apply these methods to analyse spatial voting games3.
3 Computation of line-clique Banzhaf and Shapley power indices
3.1 Line-clique Banzhaf index
In what follows, we shall refer to \(\mathtt {bnz}[i] = P_{\mathcal {G}}(i)\) as the data structure necessary to calculate the Banzhaf index. Then, the number of i-critical coalitions \(S \cup \{i\}\) such that \(|S| = k\), that is the data structure necessary to calculate the Shapley index, will be denoted \(\mathtt {shp}[i,k]\).
For \(c \in \{1,\ldots , m\}\) and \(q = 0, 1,\ldots , W\), we define the following data structures:
\(\mathtt {clt}[c,q]\), the number of connected coalitions \(S \subseteq V_c\) and \(w(S) = q\);
\(\mathtt {clt}[i,c,q]\), the number of connected coalitions \(S \subseteq V_c-\{i\}\) and \(w(S) = q\);
\(\mathtt {clt_u}[c,q]\), the number of connected coalitions \(S \subseteq V\) such that \(u(S) = c\) and \(w(S) = q\);
\(\mathtt {clt_l}[c,q]\), the number of connected coalitions \(S \subseteq V\) such that \(l(S) = c\) and \(w(S) = q\).
Since \(V_c\) is a complete subgraph, \(\mathtt {clt}[c,q]\) and \(\mathtt {clt}[i,c,q]\) can be calculated with any algorithm for the Banzhaf index of simple voting games.
For computational convenience (the dynamic programming initialization), we assume \(\mathtt {clt}[c,0] = 0\), \(\mathtt {clt}[i,c,0] = 1\), \(\mathtt {clt_u}[c,0] = 1\) and \(\mathtt {clt_l}[c, 0] = 1\).
\(\mathtt {clt_u}[c,q]\) and \(\mathtt {clt_l}[c,q]\) can be computed through recursion. For \(q \in [1,W]\), \(\mathtt {clt_u}[1, q] = \mathtt {clt}[1,q]\). For \(c > 1\), the recursive formula for \(\mathtt {clt_u}[c,q]\) is:
Formula (11) combines any coalition in \(V_c\) with all connected coalitions whose rightmost voter belongs to \(V_{c-1}\) (including the empty set), forming new coalitions whose rightmost voters is in \(V_c\).
Similarly, for \(q \in [1,W]\), \(\mathtt {clt_l}[m,q]=\mathtt {clt}[m,q]\) and the recursive formula is:
Formula (12) combines any coalition in \(V_c\) with all the connected coalitions whose leftmost voter is in \(V_{c+1}\) (including the empty set), forming new coalitions whose leftmost voters is in \(V_c\).
A voter i in \(V_c\) has positional power when it bridges two loosing connected coalitions, one on the left and one on the right of \(V_c\). Let \(S_1\) and \(S_2\) be these coalitions. We enumerate them in the following data structure.
For \(c \in \{2,\ldots , m-1\}\), let \(\mathtt {clt_p}[c,q]\) be the number of coalitions \(S \subseteq V - V_c\) with \(w(S) = q\) and such that S can be partitioned into two connected coalitions \(S_1\) and \(S_2\) with the properties: \(\max \{w(S_1), w(S_2)\} < {\overline{q}}\), \(u(S_1) = c - 1\) and \(l(S_2) = c + 1\).
The data structure can be worked out by recursion:
Formula (13) combines all the loosing connected coalitions on the right of \(V_c\) with those on the left.
The positional power of voter i can be readily computed from \(\mathtt {clt_p}[c,q]\). Let \(\mathtt {pos}[i]\) be the number of coalitions in which i has positional power. If \(i \in V_1 \cup V_m\), then \(\mathtt {pos}[i] = 0\). If \(i \in V_c\) with \(c \in \{2,\ldots , m-1\}\), then:
Formula (14) sums all the not connected coalitions that turn out connected and winning when joined by i.
Next, we focus on those situations in which i has coalitional power. Given voter \(i \in V_c\) and coalition \(S \subseteq V - \{i\}\) (such that \(S \cup \{i\}\) is connected), we must consider four cases:
1.
\(l(S \cup \{i\}) < c\) and \(u(S \cup \{i\}) = c\), i.e., voters belong to more than one clique and i is a rightmost voter of \(S \cup \{i\}\);
2.
\(l(S \cup \{i\}) = c\) and \(u(S \cup \{i\}) > c\), i.e., voters belong to more than one clique and i is a leftmost voter of \(S \cup \{i\}\);
3.
\(l(S \cup \{i\}) < c\) and \(u(S \cup \{i\}) > c\), i.e., voters belong to more than one clique and i is in a middle position in \(S \cup \{i\}\);
4.
\(l(S \cup \{i\}) = u(S \cup \{i\}) = c\), i.e., all voters belong to \(V_c\).
We consider the four cases:
Rightmost voter: Let \(\mathtt {vot_u}[i, q]\) be the number of coalitions S (not containing i) for which case 1 applies and moreover \(w(S) = q\). Then, for all i and \(q \le W - w_i\), the data structure can be calculated as follows:
Formula (15) combines the subsets of \(V_c\) without i (including the empty set, as \(\mathtt {clt}[i, c, 0] = 1\)) with the subsets on the left of \(V_c\).
Leftmost voter: Let \(\mathtt {vot_l}[i,q]\) be the number of coalitions S (not containing i) for which case 2 applies, and moreover \(w(S) = q\). Then, for all i and \(q \le W - w_i\), the data structure can be calculated as follows:
Formula (16) combines the subsets in \(V_c\) without i (including the empty set) with the subsets on the right of \(V_c\).
Middle voter: Let \(\mathtt {vot_{lu}}[i,q]\) be the number of coalitions S (not containing i) for which case 3 applies and moreover \(w(S) = q\). Then, for all i and \(q \le W - w_i\), we have:
where the subscript conditions on \(j_1\) and \(j_2\) guarantee that \(j_1 \ge 1\), \(j_2 \ge 1\) and \(q-(j_1+j_2) \ge 1\), so that there is at least one voter other than i in \(V_c\) (i must not have positional power).
Formula (16) combines the non empty subsets in \(V_c\) with the subsets that are on the right and on the left of \(V_c\).
One clique: Let \(\mathtt {vot_c}[i,q]\) be the number of coalitions S for which case 4 applies and moreover \(w(S)=q\). Then, for all i and \(q \le W - w_i\), we have:
from which the computation of the Banzhaf index (9) easily follows.
Regarding the complexity of the computation, the calculation of formulas (11), (12), (13), (15), (16) and (17) has worst case complexity O(W), that must be repeated mW or nW times at most. As \(n > m\), the greatest complexity is \(O(nW^2)\), that is quadratic in the input size W. This proves that calculating the line-clique Banzhaf index has pseudo-polynomial complexity, being #P-complete in the weak sense.
3.2 Line-clique Shapley index
To compute the line-clique Shapley index, one has to consider both the coalition weight and the coalition size. Moreover, the Shapley index considers coalitions that are not connected. For unconnected coalitions, we must keep track of their connected component, whose weight is to be stored, and keep track of unconnected voters that are important to define the coalition size. As a consequence, notations are cumbersome, but dynamic programming principles are simple.
Let \(\mathtt {clt}[c,q,k]\) be the number of connected coalitions such that \(S \subseteq V_c\) (\(S \subseteq V_c - \{i\}\)), \(w(S) = q\) and \(|S| = k\), with \(c \in \{1,\ldots , m\}\) and \(q = 0,\ldots , W\).
Similarly, let \(\mathtt {clt}[i,c,q,k]\) be the number of connected coalitions such that \(S \subseteq V_c - \{i\}\), \(w(S) = q\) and \(|S| = k\), with \(c \in \{1,\ldots , m\}\) and \(q = 0,\ldots , W\).
As \(V_c\) is a complete subgraph, all its subsets S are connected coalitions and therefore these values can be calculated using any algorithm for the Shapley index of simple voting games, Uno (2012).
For each c, the following constants, representing the number of voters on the left and the right of \(V_c\), are defined:
Let \(\mathtt {clt_{lu}}[l,u,q,k]\) be the number of connected coalitions S of k voters (\(|S| = k\)) with coalition weight q (\(w(S) = q\)) such that \(l(S) = l\) and \(u(S) = u\).
This number can be computed via recursion. When \(u = l\), \(\mathtt {clt_{lu}}[l,l,q,k] = \mathtt {clt}[l,q,k]\). For \(u > l\), we have:
Using formula (21), we can combine coalitions contained in \(V_u\) with coalitions in which the rightmost voter is in \(V_{u-1}\).
Let \(\mathtt {sqn_l}[l,u,q,k]\) be the number of coalitions \(S \subseteq V\) of k voters (\(|S| = k\)) that can be partitioned into two disjoint sets Q and T, where Q is the component of S with \(l(Q) = l\), \(u(Q) = u\) and \(w(Q) = q\), whereas \(T \subseteq V_1\cup \ldots \cup V_{l(Q)-2}\).
For \(l \in \{1,2\}\), \(\mathtt {sqn_l}[l, u, q, k] = \mathtt {clt_{lu}}[l, u, q, k]\), because \(T = \emptyset \). For \(l > 2\), the data structure can be calculated through the formula:
Formula (22) combines the aforementioned connected coalitions Q with all the subsets of voters T, unconnected to Q and located on the left of it.
Similarly, let \(\mathtt {sqn_u}[l,u,q,k]\) be the number of coalitions \(S \subseteq V\) of k voters (\(|S| = k\)) that can be partitioned into two disjoint sets Q and T, where Q is the component of S with \(l(Q) = l\), \(u(Q) = u\) and \(w(Q) = q\), and \(T \subseteq V_{u(Q) + 2}\cup \cdots \cup V_m\).
If \(u=m\) or \(u=m-1\), \(\mathtt {sqn_u}[l,u,q,k] = \mathtt {clt_{lu}}[l,u,q,k]\), because \(T=\emptyset \). If \(u < m - 1\), the data structure can be calculated through the formula:
Formula (23) combines the connected coalitions Q with all the subsets T, unconnected to Q and located on the right of it.
Formulas (22) and (23) are combined to enumerate all the coalitions with respect to player \(i \in V_c\) has positional power: for \(c \in \{ 2,\ldots ,m-1 \}\)), i will form a link with a coalition \(S_1\) located on the left of \(V_c\) (\(u(S_1)=c-1\)), with a coalition \(S_2\) located on the right (\(l(S_2) = c + 1\)).
Let \(\mathtt {sqn_p}[c,q,k]\) be the number of coalitions S of k voters (\(|S|=k\)) that can be partitioned into two subsets \(S_1\) and \(S_2\) such that:
Note the data structure is useful to determine when i has positional power, as the data structure enumerates those coalitions S for which i is a bridge. Each coalition \(S \cup \{i\}\) has a component \(Q = Q_1 \cup Q_2 \cup \{i\}\) with associated weight \(w(Q) = q+w_i\). If \(q + w_i > {\overline{q}}\) then i has positional power.
The formula to compute \(\mathtt {sqn_p}[c,q,k]\) is:
Formula (24) combines two non-winning subsets: one on the left and one on the right of \(V_c\), keeping track of the weight q and the size k.
Let \(\mathtt {pos}[i,k]\) be the number of i-critical coalitions S of k voters (\(|S| = k\)) where player i has positional power. If \(i \in V_1 \cup V_m\), then \(\mathtt {pos}[i, k] = 0\). If instead \(i \in V_c\) with \(c \in \{ 2, \ldots , m-1 \}\):
Next, we focus on the situations in which i has coalitional power, but no positional power. In particular, we consider a voter \(i \in V_c\) and a coalition \(S \subseteq V - \{i\}\). S is partitioned into two subsets, Q and T, such that Q is connected (Q is the coalition for which we recorded w(Q)) and voters of Q are not connected to voters of T. We have four possible cases:
1.
i is a rightmost voter of \(Q \cup \{i\}\): \(l(Q \cup \{i\}) < c\) and \(u(Q\cup \{i\}) = c\);
2.
i is a leftmost voter of \(Q \cup \{i\}\): \(l(Q \cup \{i\}) = c\) and \(u(Q \cup \{i\}) > c\);
3.
i is a middle voter of \(Q \cup \{i\}\): \(l(Q \cup \{i\}) < c\) and \(u(Q \cup \{i\}) > c\);
4.
all the voters of \(Q \cup \{i\}\) belongs to \(V_c\): \(l(Q \cup \{i\}) = u(Q \cup \{i\}) = c\).
We consider the four cases:
Rightmost voter: In case 1, the enumeration of coalitions is made in two steps. In the first step, we combine the subsets of \(V_c\) with the ones located on the left of \(V_c\), computed in formula (22). In the second step, we combine these coalitions with the unconnected ones on the right of \(V_c\).
In particular, let \(\mathtt {clt_l}[i,q,k]\) be the number of coalitions S of k voters (\(|S| = k\)) that do not include i (\(i \notin S\)) and have a component Q with \(w(Q) = q\). In case 1, \(S \cap V_j = \emptyset \) for all \(j > c\), \(l(Q) < c\) and \(u(Q \cup \{i\}) = c\). Then, by assuming for computational convenience \(\mathtt {clt}[c,i,0,0] = 1\), we can write:
Let \(\mathtt {vot_l}[c,i,q,k]\) be the number of coalitions S of k voters (\(|S| = k\)) having a component Q with \(u(Q \cup \{i\}) = c\) and \(w(Q) = q\). Then we have:
Formula (27) combines all the coalitions enumerated through (26) with all the coalitions on the right of \(V_c\), whose number is accounted for by the binomial coefficient.
Leftmost voter: Also in this case, the enumeration of coalitions can be accomplished in two steps.
In particular, let \(\mathtt {clt_u}[i, q, k]\) be the number of coalitions S of k voters (\(|S| = k\)) that do not include i (\(i \notin S\)) and have a component Q such that \(w(Q) = q\). In case 2, we have \(S \cap V_j = \emptyset \) for all \(j < c\), \(l(Q \cup \{i\}) = c\) and \(u(Q) > c\). Assuming \(\mathtt {clt}[c,i,0,0]=1\), we have:
Let \(\mathtt {vot_u}[c,i,q,k]\) denote the number of coalitions S of k voters having a component Q with \(l(Q \cup \{i\} = c\) and \(w(Q) = q\). Then we have:
Formula (29) combines all the coalitions in (28) with all the unconnected coalitions on the left of \(V_c\), whose number is accounted for by the binomial coefficient.
Middle voter: Let \(\mathtt {vot_{lu}}[i,q,k]\) be the number of coalitions S of k voters (\(|S| = k\)) that do not include i (\(i \notin S\)) and have a component Q such that \(w(Q) = q\). In case 3 we have \(l(Q) < c\) and \(u(Q) > c\). Moreover, since we are considering only the situations where i has coalitional power and excluding the ones in which the player has positional power, it must be that \(Q \cap V_c \ne \emptyset \) and therefore \(|(Q \cup \{i\}) \cap V_c | \ge 2\).
The formula to calculate \(\mathtt {vot_{lu}}[i,q,k]\) is thus:
Formula (30) combines all the coalitions in \(V_c\) with those that are on the left and on the right of \(V_c\). The range of \(j_3\) and \(j_4\) guarantees that there is at least one voter in \(V_c\), at least one on the right of \(V_c\), and at least one on the left of it.
One clique: Let \(\mathtt {vot_c}[i,q,k]\) be the number of coalitions S of k voters (\(|S| = k\)) not including i (\(i \notin S\)) and having a component Q with coalition weight q (\(w(Q) = q\)). In case 4, we have \(S \cap V_{c+1} = S \cap V_{c-1} = \emptyset \).
Assuming for convenience that \(L(c) = 0\) for \(c < 1\) and \(U(c) = 0\) for \(c > m\),
Formula (31) combines all the coalitions in \(V_c\) with all the ones made up of the non critical players located on the left and on the right of \(V_c\).
Formulas (27), (29), (30) and (31) can be summed up to compute the number of coalitions with respect to which player i has coalitional power. Let \(\mathtt {vot}[i,k]\) be the number of such coalitions S of k voters (\(|S| = k\)), then:
Regarding the computational complexity, the calculation of formulas (21), (22), (23), (24), (26), (27), (28), (29), (30) and (31) has at most pseudo-polynomial complexity, depending on polynomial functions of n, m and W. The greatest attained complexity is \(O(m^3W^2n^2)\) for formula (24). This proves that calculating the Shapley index on line-clique graphs is #P-complete in the weak sense.
4 Power indices and negotiation outcomes in the Council of the European Union
In this section, we shall carry out an illustrative application of the analysis of power using the graph restricted versions of Banzhaf and Shapley indices and compare results with the unrestricted versions.
In particular, we shall use the dataset on “Decision-making in the European Union” (DEUII) released by Thomson et al. (2012). The data set serves to analyze the distributions of power across EU member states in the Council of the European Union (or Council of Ministers, CM). Its structure is the spatial voting model from which our line-clique restricted game has been developed. DEUII contains data on 331 controversial issues raised by 125 legislative proposals introduced in the Council between 1996 and 2008. In particular, using information from 349 semi-structured interviews with key informants, the authors identify for each controversial issue: (i) the location of the policy alternative favored most by each of the political actors—European Commission (COM), European Parliament (EP), member states’ representatives in the CM—in a unidimensional policy space (from 0 to 100), i.e. the bliss point of single-peaked preferences; (ii) the spatial location of the decision outcome occurring when the legislative proposal is not adopted, i.e. the disagreement (or reference) point; (iii) the spatial location of the final decision outcome in the same space; (iv) the level of importance that each actor attaches to each of the controversial issues on a 0-100 scale (issue salience).
To give an example, Fig. 2, taken from Thomson et al. (2012), shows the identified spatial location of the political actors (COM, EP and member states’ representatives) in the controversy about the auctioning of carbon credits in the proposed directive on emission allowances in the aviation sector (COD/2006/304).
Since both the EU voting system and the member states have changed much in the last twenty years, we consider two different scenarios: (i) the Pre-Nice scenario, from 1995 up to the Treaty of Nice (February 2003) and before the 2004 enlargement; (ii) the Post-Nice scenario, from January 1st 2007 onward, after the fifth enlargement with the accession of Bulgaria and Romania.
In the former scenario (Pre-Nice), the voting system in the CM was as follows: there were 15 member states; acts were proposed by the European Commission or at least 10 member states. In policy areas not requiring unanimity, there was a qualified majority voting with a threshold of 62 out of 87 votes. The vote allocation was less favorable to big countries. The voting weights were: France, Germany, Italy, UK 10; Spain 8; Belgium, Greece, Netherlands, Portugal 5; Austria, Sweden 4; Finland, Ireland, Denmark 3; Luxembourg 2.
In the latter scenario (Post-Nice), there are 27 EU member countries. In policy areas not requiring unanimity, in the CM the system sets three quotas for passing an act: (i) a qualified weighted majority (74% of the votes, i.e. 255 out of 345 votes); (ii) a (qualified) majority of members (14, for proposals of the European Commission, or 18); (iii) 62% of the total EU population. The voting weights in the qualified weighted majority are: France, Germany, Italy, UK 29; Poland, Spain 27; Romania 14; Netherlands 13; Belgium, Czech Republic, Greece, Hungary, Portugal 12; Austria, Bulgaria, Sweden 10; Denmark, Finland, Ireland, Lithuania, Slovakia 7; Cyprus, Estonia, Latvia, Luxembourg, Slovenia 4; Malta 3. In fact, as showed by Felsenthal and Machover (2001) and Baldwin and Widgrén (2004), conditions (ii) and (iii) have negligible effects for acts proposed by the European Commission and we therefore consider only condition (i).4
In what follows:
We first analyze the numerical difference between graph restricted and unrestricted power indices on a single issue and we will find that country’s position affects its power, being the central positions more strategical than the extreme.
Next, we compute the power indices on all issues and observe their empiric distributions. We will observe that, the average of a country’s graph restricted index corresponds to the value of the unrestricted index. Interestingly, it appears that in the long run no country is taking advantage of any positional power, e.g., countries are sincere when they express a position.
Finally, we run some regression models to test the predictive power of the indices, and we will find that the graph restricted indices are positively correlated with the negotiation outcomes, while the unrestricted indices are not. The result shows that graph restricted indices can be useful for applied political analysis.
4.1 Graph restricted and unrestricted Banzhaf and Shapley indices
To start with, let us analyze the differences between graph restricted and unrestricted Banzhaf indices in one particular controversy. The controversy is about the auctioning of carbon credits in the proposed directive on emission allowances in the aviation sector (COD/2006/304).
Figure 3a reports the unrestricted Banzhaf indices for the 27 member states computed using the Post-Nice voting system (these indices are constant across controversies cause they do not depend on the particular issue at stake), along with the graph restricted Banzhaf indices, using data from the spatial voting game of Fig. 2.
Fig. 3
A-priori and line-clique indices computed for the controversy about the auctioning of carbon credits in the aviation sector (COD/2006/304)
×
Although the two indices are positively correlated (the correlation coefficient is 0.8), for some member countries some differences emerge. For the UK, Denmark, Ireland and Sweden, the unrestricted index is greater than the line-clique version, since these countries are located on the right of the ideological space with no sufficient ability of connecting coalitions. Conversely, for other countries (e.g., Belgium and the Netherlands) the graph restricted Banzhaf index is greater than the unrestricted, since the two nations take advantage their positional power.
Figure 3b shows the unrestricted and restricted versions of the Shapley index for the same spatial voting game. As in the case of the Banzhaf index, the two versions of the Shapley index are highly correlated (the correlation coefficient is 0.92), although for some countries they in fact differs. The greatest differences emerge with respect to the UK, Belgium, Denmark and the Netherlands. For these countries the line-clique version of the Shapley index returns a value significantly greater than the correspondent a-priori version of the index. As remarked previously, this is due to their positional power.
Notably, in the case of the UK, while the a-priori Banzhaf and Shapley indices return fairly similar values (respectively, 0.078 and 0.087), the line-clique versions of the two indices are rather different: the Banzhaf index is small (0.010), while the Shapley index is significantly larger (0.131). This is because the positional power strictly depends on the assumptions on how, given the preferred outcomes of the players, coalitions are formed and these assumptions are different in the two indices (we will expand this remark later).
In general, while the unrestricted versions of Banzhaf and Shapley indices are highly correlated (the correlation coefficient is as high as 0.997), the correlation between the respective graph versions is lower (0.879). Figure 4 shows the scatter plots of unrestricted Banzhaf and Shapley index (Fig. 4a) and the corresponding line-clique versions (Fig. 4b).
Fig. 4
Scatter plots of (line-clique) Banzhaf index vs. (line-clique) Shapley index with least squares fit
×
Finally, Figs. (5) and (6) show the box plots of the distribution of line-clique Banzhaf and Shapley indices computed for each member state over all the different issues in the Pre-Nice and Post-Nice scenario. In this respect, it is interesting to note that, although, as we discussed before, unrestricted and line-clique versions computed for a single issue can be rather different, unrestricted indices (denoted with red circles in the figures) are always very close to the median of the distribution of the corresponding graph indices. This is because, although the relative ideological location of member countries in fact differs across issues (e.g. countries located at the right of the spectrum for some issues are at the left in some other issues), the relative frequency of each country’s location along the ideological space for the different issues tend to be almost the same, and thus the unrestricted version of the indices gives an estimate of the average power of countries across the different issues.
Fig. 5
Boxplots of line-clique Banzhaf and Shapley indices for the 15 EU member states calculated over 119 controversial issues under the Pre-Nice scenario (red circles are a-priori versions of the indices)
Fig. 6
Boxplots of line-clique indices of the 27 EU member states calculated over 46 controversial issues under the Post-Nice scenario (red circles are a-priori indices)
×
×
This notwithstanding, line-clique indices should be better measure of players’ expected level of success in any given negotiation process, since they employ information on the relative ideological location of players. This is something we shall explore in the following section, where we analyze how the different indices are able to forecast the actual outcome of the negotiation processes.
4.2 Power indices and negotiation outcomes
To analyze if and to what extent the different indices can help predicting the outcome of the negotiation process, for each member state in each controversial issue we compute the distance between the member’s ideal outcome (the stated preferred outcome of its representatives) and the actual outcome of the negotiation, and study how this variable correlates with the indices.5
To start with, we run the following simple bivariate OLS regressions:
where the inverse hyperbolic sine of the Euclidean distance between the bliss point of country c and the decision outcome in issue i, \({\text {asinh}}(dist_{ci})\), is regressed on a constant and a power index computed for country c in issue i (0–100 scale), \(power_{ci}\). We run four regressions, one for each of the four indices we considered: Banzhaf, graph restricted Banzhaf, Shapley and graph restricted Shapley.6
We also estimate specifications where we include the salience of the issue for the country, to control somehow for the strength of the interests at stake, as well as country dummies and/or issue dummies, i.e.:
where \(sal_{ci}\) is the salience of issue i for country c—from 0 (no salience) to 100 (max salience)—, \(\mu _c\) are country dummies (one dummy for each country) and \(\iota _i\) issue dummies (one dummy for each issue).
It is worth noting that, since unrestricted Banzhaf and Shapley indices do not depend on the issue at stake, but only on the voting system, they are constant for each country and therefore it is not possible to consistently estimate Eq. (35) including both country and issue dummies. Moreover, with country dummies, for the estimation one exploits the differences in the index for each country across the two voting systems (pre and post Nice), and therefore the only observations that can be actually used are those referring to the 15 member states that are also in the Pre-Nice scenario. These issues do not apply to the graph restricted indices, because they in fact vary across countries and issues, depending also on the stated preferred outcome of member states’ representatives in each controversial issue.7
Table 1
OLS estimation results: Banzhaf index
I
II
III
IV
V
VI
VII
VIII
Banzhaf index
–0.0043
–0.0241\(^{*}\)
0.0107
–0.0050
(0.0122)
(0.0123)
(0.0408)
(0.0099)
Graph restricted Banzhaf index
–0.0312\(^{***}\)
–0.0468\(^{***}\)
–0.0945\(^{***}\)
–0.1272\(^{***}\)
(0.0114)
(0.0114)
(0.0224)
(0.0186)
Salience
0.0115\(^{***}\)
0.0119\(^{***}\)
0.0127\(^{***}\)
0.0092\(^{***}\)
0.0125\(^{***}\)
0.0101\(^{***}\)
(0.0015)
(0.0015)
(0.0016)
(0.0015)
(0.0016)
(0.0015)
Country dummies
No
No
No
No
Yes
No
Yes
Yes
Issue dummies
No
No
No
No
No
Yes
No
Yes
Adjusted \(R^2\)
0.0000
0.0022
0.0177
0.0220
0.0189
0.4995
0.0248
0.5105
Obs
2988
2988
2988
2988
2988
2988
2988
2988
Dependent variable: \({\text {asinh}}(\)distance). Unreported constant included. Standard errors in parentheses.
The regression results are summarized in Tables 1 and 2. In general, the coefficients attached to power indices have the expected signs: an increase in the country’s power is associated on average and ceteris paribus with a smaller distance between ideal and actual outcomes. What is worth discussing are the differences between unrestricted and graph restricted indices.
The coefficients attached to the unrestricted indices (Banzhaf and Shapley) in the regressions are very low and almost always not significant: a larger value of the index for a certain player in any given negotiation is not associated ceteris paribus with actual outcomes significantly closer to the player’s ideal point. This result is not in favor of unrestricted indices: If power, meant as the capacity or ability to direct or influence the course of events, is expected to be (significantly positively) correlated with success, these indices are not particularly good at measuring it. In any case, they turn out to be not very useful in predicting the actual outcome of the negotiation process.
Do graph restricted indices perform better? The answer is yes. The most important results are obtained for the Banzhaf index. Its regression coefficient is always larger, in absolute terms, than the unrestricted one and it is always statistically significant to a large extent: less than 1%. The coefficient negative sign is consistent with the effect of power: It makes shorter the distance between the bliss point and output. For example, according to the point estimate of \(\beta _1\) in the bivariate regression (column II in Table 1), a unit increase in the index (\(\varDelta power_{ci} = 1\)) makes the expected value of the distance decrease by roughly 3%. The coefficient \(\beta _1\) is still significant even when we introduce salience and dummy variables about issue and country. It is interesting to note that salience is significant, but inversely correlated to success. Data suggests that the more an issue is important, the less successful is the negotiation outcome. Here we suggest that it can be interpreted the other way round: nations declare an issue as salient just because they realize that their positional power is little. Finding significant coefficients is an important result about the application of power indices. Unfortunately, this does not mean that the outcome is really predictable: Looking at the R-squared indices we see that they remain quite low (as is generally accepted when regression is applied to political and social data). There is one remarkable exception however, that is in the two cases in which issue dummies are present and in which the R-squared are very high. At the moment, we cannot explain the political reason to this, but it is a result that is worth supplementary analysis.
Regarding the graph restricted Shapley index, we can see in Table 2 that results are less strong. Coefficient estimates have the right sign, but in only one case we found a significant value. Conversely, estimates on salience and dummies remain consistent. We may guess that the graph restricted Banzhaf index is better than Shapley because it relies to more realistic political underpinnings. The Banzhaf index corresponds to the case in which all connected coalitions are equally likely. A coalition with an unconnected voter saying “yes” is not accounted for. Conversely, the Shapley index replaces coalition with sequences. Any sequence is possible, but if a sequence is not connected, it does not express a majority even though its votes are!
5 Future research and conclusions
In this contribution, we have shown how to use dynamic programming to compute the number of connected coalitions in spatial voting games and we have shown that the indices of power calculated in this way are useful to understand the political games, namely, the bargaining process in EU Council. In the past, some authors claimed that cooperative games and power indices can be used only to analyze the a-priori power of legislature, but our results are showing that preferences can be accommodated to better define voters’ power and that the a-posteriori indices calculated in this way can be used to predict the outcome of a bargaining process. This opens up a set of questions in which computational theory and political analysis are strictly intertwined.
We restricted our attention to the Banzhaf and Shapley indices of power, but other definitions of power are available in the literature. Firstly, in our approach, to remain faithful to the original definitions, only connected coalitions define the Banzhaf formula 9, while connected and unconnected coalitions define the Shapley formula 7. But with a manipulation of our dynamic programming, one could test the opposite possibility: Defining a Banzhaf formula based on all coalitions (connected and unconnected), defining a Shapley formula based on connected coalitions only. Formulas would loose their theoretical backgrounds, namely, the axiomatic of Shapley’s and the political empiricism of Banzhaf’s, but they could gain explanatory power in the regression 35. Secondly, other power indexes can be useful here, for example the Deegan-Packel and the Holler indices. Both indexes are based on the concept of minimal winning coalitions, and for Deegan-Packel’s, a dynamic programming algorithm has been proposed in Matsui and Matsui (2000). The recursive function has parameters: the player, the coalition weight, the size, and the coalition minimum weight. It seems elaborate but not insurmountable to include a connectivity constraint in the line followed in Sect. 3. The same consideration holds when considering the possibility of a-priori unions, as suggested in Owen (1977): From a computational point of view, algorithms are more elaborate, but still the same principles can be applied. The final consideration is about to what other kind of graphs dynamic programming can be applied to devise pseudo-polynomial algorithms. Here, the case of line-clique is an instance of graphs that can be defined recursively, according to the definitions available in Borie et al. (2008). In that paper it is also argued that under specific rules and conditions, those graphs are amenable to the application of dynamic programming. However, specific details are to be given to take advantage of the peculiar recursion that defines the graph.
Acknowledgements
The authors gratefully acknowledge the comments by our colleague Romeo Rizzi, regarding the detailed explanation of the technicalities of the #P-complete complexity class. Stefano Benati acknowledges the financial support by Ayudas Fundación BBVA a equipos de investigación científica 2019.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The difference between strong and weak #P-complete problems can be understood as similar to the difference between strong and weak NP-complete problems. The theory of NP-completeness refers to problems expressed in existential form. Is there at least one solution satisfying a given property? Two examples are: Is there at least one Hamiltonian path in a graph?, or: Is there at least one coalition for which i is a swing voter? The former is strongly NP-complete, the latter is weakly NP-complete, as it can reduced to knapsack. The former can be solved by heuristic, the latter can be solved by dynamic programming.
The voting system of the Lisbon Treaty, which came into force in November 2014, is instead a double majority system: (i) majority of countries (72%, or 55% if acting on a proposal of the European Commission); (ii) majority of population (65%).
In fact, the distance between actual and ideal outcomes is a measure of lack of success, and success depends on “power” and “luck” Barry (1980a, 1980b). On the implications of the differences between luck and power in measuring ex-post power see, among the others, Steunenberg et al. (1999) and Napel and Widgrén (2004). Within this context, (ex-post) power is meant as “the ability of a player to make a difference in the outcome” (Steunenberg et al. 1999, p. 362). Napel and Widgrén (2004) suggest to measure it by looking at the sensitivity of the outcome with respect to the player’s ideological location.
Note that for very small values of x, the inverse sine is approximately equal to \(\log (2\, x)\), or \(\log 2 + \log x\), and therefore in Equation (34) \(100\,\beta _1\) can be interpreted as (approximately) the percentage change in the expected value of the distance associated with a unit increase of the power index.
It is worth pointing out that we are assuming that the stated preferred policy alternative in the controversial issue is exogenous and not the result of strategical commitments of players to maximize power.
