Int J Game Theory DOI 10.1007/s00182-013-0400-z

Voting power and proportional representation of voters Artyom Jelnov · Yair Tauman

Accepted: 19 November 2013 © Springer-Verlag Berlin Heidelberg 2013

Abstract We prove that for the proportional representative election system if parties’ sizes are uniformly distributed on the simplex, the expected ratio of a party size to its political power, measured by the Shapley–Shubik index, converges to 1, as the number n of parties increases indefinitely. The rate of convergence is high and it is of the magnitude of n1 . Empirical evidence from the Netherlands elections supports our result. A comparison with the Banzhaf index is provided. Keywords Shapley-Shubik index · Banzhaf index · Voting power · Voting systems · Proportional representation 1 Introduction In many democracies parliaments are elected by proportional representative system (hereafter-PR). The PR system allocates seats in parliament to parties in proportion to their supporters. But does it represent the bargaining power of the parties? The answer in general is negative. As an example, let A, B and C be the only three parties represented in a parliament with 100 seats. Suppose that A, B and C have 45, 45 and 10 seats, respectively. A coalition of parties that have a simple majority (more than 50 seats) has the entire power. Any coalition of at least two parties has a majority and no party has a majority by itself. In this sense C has the same bargaining power as A or B A. Jelnov (B) The Faculty of Management, Tel Aviv University, Tel Aviv, Israel e-mail: [email protected]; [email protected] Y. Tauman Department of Economics, Stony Brook University, Stony Brook, NY, USA e-mail: [email protected] Y. Tauman The Interdisciplinary Center, Herzliya, Israel

123

A. Jelnov, Y. Tauman

even though C is much smaller in size. A similar argument applies to a large number of parties.1 Suppose there are n = 2m + 1 parties in the parliament, m is an arbitrary integer. Assume there are 2m parties with k > 1 seats each, and one party, A, with 1 seat only. A majority consists of at least mk +1 seats. Any coalition with m +1 or more parties has a majority, and any coalition of less than m + 1 parties has no majority. Clearly, the smaller party A has the same bargaining power as any other party. Many argue that “voting power” of parties should be closely related to their size. Nurmi (1981) advocates that the idea of proportional representation rests on the identity of distribution of parties’ support and the distribution of parties’ power. Nozick (1968, Note 4) refers to district systems and states that a system of proportional representation reflects legislators’ power. The example above however demonstrates that the PR system does not satisfy this property, at least not for every distribution of parties’ size. Yet, proportionality of a priori voting power to weight sounds a proper principle for a fair representative parliament. The literature offers several tools to measure voting power of a party. The most wellknown tools are the Shapley value (Shapley 1953) and the Banzhaf index (Banzhaf 1964, 1968). Both measures are based on the probability of party to be a pivot. Namely, the voting power of a party is the probability that it turns a random coalition of parties from one with no majority into a winning coalition. While for the Banzhaf index all coalitions have the same probability to form, the Shapley value uses different probability distribution: coalitions of the same size are equally likely to be formed and all sizes have the same probability. In this paper we show that irrespective of the quota required for majority, if parties’ size is uniformly distributed (reflecting no prior information about their size), the expected ratio of a party size to its voting power, measured by the Shapley value, approaches 1, as the number of parties increases. This result fails to hold for the Banzhaf index, but holds for the normalized Banzhaf index only when the quota is 0.5 [see Chang et al. (2006)]. Furthermore, the rate of convergence is high and the error term is of the magnitude of 1/n where n is the number of parties. Numerical analysis shows that the variance of this ratio converges to 0, as the number of parties increases. Let us mention that using Neyman (1982) it is shown (see Proposition 2, below) that the ratio of the Shapley value of a party to its size converges in probability to 1. Nevertheless, this result does not imply our convergence result above since this ratio is not bounded above and for some realizations it converges to infinity. Also, the proof of Proposition 2 does not provide a hint on the rate of convergence. Even though the number of parties in most parliaments is relatively small our result may still be applicable. A relatively small number of parties in parliaments is often caused by a “threshold of participation” [see Rae et al. (1971)]. A large number of parties often participate in the election, but in some cases only small number of them have seats in the parliament. For instance, the 2009 German federal election resulted with 6 parties in the parliament out of 29 competing parties. The 2006 Netherlands election resulted with 10 parties out of 23 competing parties. In addition, an electoral threshold induces some parties not to participate in elections as a distinct party.

1 The following example is from Lindner and Owen (2007).

123

Voting power and proportional representation of voters

Our analysis is also relevant to voting power of shareholders in a business company with relatively large number of shareholders. Since typically the number of shareholders is large our result asserts that profit sharing proportional to the number of shares reflects on average the voting power of shareholders. The notion of voting power is well discussed in the literature. As mentioned above we focus here on the Shapley–Shubik index (Shapley and Shubik 1954), which relies on the Shapley value for cooperative games (Shapley 1953). This notion is uniquely derived by a set of four axioms and it assigns to every party in a given game a share in the total “cake”. An axiomatization of the Shapley value for just voting games is given in Dubey (1975). Young (1985) provides an alternative axiomatization of the Shapley value for the class of all n−person games in coalitional form which can also be used to characterize the Shapley value on the class of voting games.2 The Shapley value of a party is considered to measure its “real contribution” to the total cake, reflecting on its bargaining power in the cake division game. In the context of voting games, the Shapley–Shubik index measures voting power as an expected prize of a party [“the P-power”, using terminology of Felsenthal and Machover (1998) 3 ]. Our main result can therefore be stated as follows: if parties’ size are random and has uniform distribution the expected value of the ratio of the Shapley value of a party to its size approaches 1, when the number of parties increases. The parliamentary elections in the Netherlands provide an empirical evidence for our result. For each election in the Netherlands we calculated the average and the variance of the ratio of the Shapley value of a party to its size. The average is above 0.9, and the variance is impressively low. Chang et al. (2006) confirmed our result through Monte-Carlo simulations for any majority quota, provided that it is not close to 1, as well as for the normalized Banzhaf index4 if the majority quota is 0.5 [for quota other than 0.5 Chang et al. (2006) have no convergence results]. These simulations confirm the Penrose (1952) conjecture stating that asymptotically the ratio of voting power to size is the same across parties. Penrose used informal language to describe the notion of voting power, one that was defined formally later in Banzhaf (1964). The conjecture fails to hold for instance for the example above, but found to be analytically correct for some special cases [see Lindner and Machover (2004)]. It is worth mentioning a very simple and related result by Shapley (1961). Namely, for any number of players and any system of weights if the quota for a majority is random and has a uniform distribution then the expected Shapley value of every party coincides with its size. Finally, in many parliaments around the world at least one party is relatively large. Nevertheless, this observation does not contradict the assumption that parties’ size 2 Young replaces the controversial additivity axiom by a more intuitive monotonicity axiom. For the axiomatization of the Banzhaf index and its relationship to the Shapley value see Lehrer (1988). Another axiomatization of the Banzhaf index is by Dubey et al. (2005). 3 Although Felsenthal and Machover (1998) expressed reservation regarding the Shapley–Shubik index, in

Felsenthal and Machover (2005) they state that “for a priori P-power, the Shapley–Shubik index still seems to be the most reasonable candidate for measuring it ”. 4 The sum of Banzhaf indices of parties is normalized to 1.

123

A. Jelnov, Y. Tauman

are uniformly distributed. For instance for n = 10, when parties’ sizes are uniformly distributed on the simplex, the probability that at least one party is larger than 0.2 is 0.92, and the probability that at least one party is larger than 0.3 is 0.4 [see Holst (1980, Theorem 2.1]. 2 The model Let N = {1, 2, . . . , n} be the set of parties. Suppose that X 1 , . . . , X n are n random variables that measure the size of the n parties. That is n X i=1 i = 1,X i ≥ 0 and i = 1, . . . , n. Let An =



n     x1 , . . . , xn  xi = 1, xi ≥ 0, i = 1, . . . , n i=1

be the n − 1 dimensional simplex in Rn . We assume that the realization (x1 , . . . , xn ) has a uniform distribution on An with respect to the volume of An . Let vn be the volume of An and let pn = v1n be the (fixed) density function of X = (X 1 , . . . , X n ) on An . Let 21 ≤ q < 1 be a quota and let Vn be the voting game on N defined for every realization x ∈ An and all S ⊆ N by Vn (S, x) =



i∈S x i > q otherwise.

1, 0,

 We say that a subset S of N is a winning coalition if i∈S xi > q and it is a minimal winning coalition if it is a winning coalition and for all i ∈ S, S\{i} is not a winning   coalition j∈S\{i} x j ≤ q . Let x ∈ An and let i (x) be the set of all coalitions S, S ⊆ N \{i}, such that S is not a winning coalition and S ∪ {i} is a winning coalition. In this case we say that i is a pivot player to S. That is, i (x) is the set of all coalitions S, S ⊆ N \{i} such that i is pivot to S. To derive the Shapley value of a player consider the n! permutations of the players in N . For every i ∈ N and every permutation  let Pi be the subset of players in N that precede i in the order . For example, suppose that N = {1, 2, 3, 4} and  = {2, 3, 1, 4}. Then P1 = {2, 3}. The number of permutations of N where i is a pivot is φ(x, i) =



|S|!(n − |S| − 1)!

S∈i (x)

Given the set N and the weights x = (x1 , . . . , xn ) ∈ An , the Shapley value of Vn is Sh i (x) =

123

φ(x, i) n!

Voting power and proportional representation of voters

That is, the Shapley value of a party i is the probability that i is a pivot in a random order where all orders are equally likely. An equivalent way to derive the Shapley value of i ∈ N is through the following probability distribution over coalitions S ⊆ N \{i}. All coalitions of the same size are equally likely to be formed and all sizes 0, 1, . . . , n − 1 have the same probability, n1 . That is the probability of S ⊆ N \{i} 1 occurring is n−1 = |S|!(n−|S|−1)! . n! ( |S| )n Given (N , x) the Banzhaf index, Bz, of i ∈ N is: Bz i (x) =

|i (x)| 2n−1

That is, every coalition S ⊆ N \{i} have the same probability to form irrespective of its size. Both the Shapley value and the Banzhaf index of a party i measure the probability of i to be a pivot to a random coalition. The two measures differ in the probability distribution over coalitions. Let E x p be the expected value operator and denote

E x p(Sh i (X ), n) =

pn Sh i (X ) d X An

and  Exp



Sh i (X ) Sh i (X ) ,n = pn d X. Xi Xi An

Similarly,  Exp



Bz i (X ) Bz i (X ) ,n = pn d X. Xi Xi An

The following result is shown analytically. Theorem Let i ∈ N , and

1 2

≤ q < 1. Then

(1) lim E x p

n→∞

 (2) E x p

Sh i (X ) Xi , n



=1+O

 Sh (X )  i ,n = 1 Xi

  1 n

That is, the expected ratio between the Shapley value and the size of a party approaches 1 as n increases indefinitely. The rate of convergence is n1 and it can

123

A. Jelnov, Y. Tauman

 Fig. 1 E x p



Sh i (X ) X i , n for q = 0.5

be shown that the error term converges to zero exponentially. Figure 1 illustrates the  Sh i (X ) rate of convergence for q = 1/2. In this case, E x p X i , n ≥ 0.9 for n ≥ 10.5 Examples 1. Suppose that n = 2 (two parties only). Then X i ∼ U [0, 1], i = 1, 2. Clearly Sh i (x) =

1, 0,

xi > q xi ≤ q

implying that  Exp

1 Sh i (X ) 1 ,2 = d xi = − log q. Xi xi q



Sh i (X ) Xi , 2



= log 2 < 1   ) , 3 is more complicated. We 2. Suppose that n = 3. The computation of E x p ShXi (X i In particular for q =

1 2

Exp

show later on [see (6) below] that for q = Exp and log 2 < 2 log 2 −

2 3

1 2

 Sh (X )  2 i , 3 = 2 log 2 − Xi 3

< 1.6

5 Simulations in Chang et al. (2006) give a close result for the Shapley–Shubik index for any quota except quotas close to 1. Our analytical result holds for any quota smaller than 1. The difference can be explained by the rate of convergence. For quota close to 1 the rate of convergence is relatively small, and the number of parties needed in this case is larger than isused in the simulations of Chang et al. (2006). 6 We provide an explicit expression of E x p Sh i (X ) , n for all q, 1 ≤ q < 1 and all n. 2 Xi

123

Voting power and proportional representation of voters

To prove the Theorem we first state and prove the following proposition. Let c ∈ (0, 1) and let Cn (c) be the set of all elements in An such that x1 = c. Cn (c) =

n      c, x2 , . . . , xn  xi = 1 − c, xi ≥ 0, i = 2, . . . , n . i=2

Proposition 1 Suppose that the elements of Cn (c) are uniformly distributed. Then for n≥3

Cn (c)

⎧ c(n−2) , ⎪ ⎪ ⎨ (1−c)n  pn Sh 1 (X ) d X = n1 + (n−2)(1−q) n(1−c) , ⎪ ⎪ ⎩ 1,

0


where pn is the (fixed) density function of X = (X 2 , . . . , X n ) on Cn (c). Note, that Proposition 1 is consistent with the well-known “oceanic games” result (Shapiro and Shapley 1978), which states, that if there is a sequence of weighted majority games with one party of constant size c, c < q < 1 − c (a major party), and the size of any other (minor) party converges to zero, then the Shapley value of c . It was shown in Dubey and Shapley (1979) that the the major party converges to 1−c convergence of the Banzhaf index is different. The proof of the Proposition relies on the following two well-known lemmas. Lemma  1 Let Y1 , . . . , Yn be  i.i.d. with exponential distribution. Then (X 1 , . . . , X n ) Yn Y1   and , . . . , n Y has the same distribution. n Y j=1

j

j=1

j

For a proof see, for instance, Feller (1971). Lemma 2 Let Y1 , . . . , Yn be i.i.d. random variables, each has an exponential distrik k Yi . Then  for 1 ≤ k < n has the Beta bution. For 1 ≤ k ≤ n, let k = i=1 n distribution with parameters (k, n − k). For a proof see Jambunathan (1954, Theorem 3). Notice that the Beta distribution function is defined by 

k
=

n−1   n−1 j=k

j

z j (1 − z)n−1− j

The next lemma is a consequence of the above two lemmas. Lemma 3 Suppose that X = (X 1 , . . . , X m ) is uniformly distributed on Am , where m ≥ 2. Then m−1  k=1

 Pr ob

k 

 Xi ≤ z

= (m − 1)z

i=1

123

A. Jelnov, Y. Tauman

Proof From Lemmas 1 and 2, k). Hence, m−1 

 Pr ob

k=1

k 

k

X i has Beta distribution with parameters (k, m −

i=1

 Xi ≤ z

m−1  m−1 

=

i=1

k=1 j=k

(m − 1)! z j (1 − z)m−1− j j!(m − 1 − j)!

By rearranging terms we have: m−1 

Pr ob

k=1

k 

 m−1  Xi ≤ z = k

i=1

k=1

(m − 1)! z k (1 − z)m−1−k k!(m − 1 − k)!

= (m − 1)z = (m − 1)z

m−1 

m − 2 k−1 z (1 − z)m−1−k k−1

k=1 m−2  k  =0

m−2 k





z k (1 − z)m−2−k



= z(m − 1)(z + 1 − z)m−2 = z(m − 1)

Corollary 1 Suppose that X is uniformly distributed on Cm (c), m ≥ 3. Then m−1 

Pr ob

k 

k=2

 X i ≤ z = (m − 2)

i=2

z 1−c

We are ready now to prove Proposition 1. Proof  of Proposition 1 For every permutation  of N party 1 is pivot  if q − c < x ≤ q. Denote by  = {(c, x , . . . , x ) ∈ C (c)|q − c <  1  2 n n i∈P1 i∈P1 x 1 ≤ q} the subset of Cn (c), in which party 1 is pivot in . Let Rk be the set of all orders  of N such that there are exactly k parties that precede 1 in the order . Note that Cn (c) is a symmetric subset of Rn and so is  for every order . Hence, if  ∈ Rk and  ∈ Rk Pr ob(X ∈  |X ∈ Cn (c)) = Pr ob(X ∈  |X ∈ Cn (c)) ≡ (c, k) Since the orders of N are uniformly distributed, Pr ob( ∈ Rk ) = n1 . Thus



pn Sh 1 (X ) d X = Cn (c)

Notice that

n−1 1 (c, k) n

k+1    (c, k) = Pr ob q − c < Xi ≤ q i=2

123

(1)

k=0

(2)

Voting power and proportional representation of voters

We distinguish two cases. Case 1 0 < c < 1 − q In this case (c, 0) = (c, n − 1) = 0 and by (2) n−2 n−2 k+1    1 1 (c, k) = Pr ob q − c < Xi ≤ q n n k=1

k=1

=

n−2 1

n

i=2

Pr ob

k=1

k+1 

n−2 k+1     Xi ≤ q − Pr ob Xi ≤ q − c

i=2

k=1

i=2

By Corollary 1 n−2 n−2 c 1 n−2 [q − (q − c)] = (c, k) = n n(1 − c) n 1−c k=1

This together with (1) imply



pn Sh 1 (X ) d X = Cn (c)

n−2 c n 1−c

as claimed. Case 2 1 − q ≤ c ≤ q In this case party 1 is a veto player meaning that every winning coalition must  k+1 X ≤ q = 1 for every k = 1, . . . , n − 1, and in include 1. In this case Pr ob i=2 i particular (c, n − 1) = 1. Applying (2) we have n−1 n−2 1 1 1 1 n−2 (c, k) = + (c, k) = + n n n n n k=1

k=1

n−2 k+1   1 Pr ob X i ≤ q −c . − n k=1

i=2

By Corollary 1 n−1 1 (n − 2)(1 − q) 1 1 n − 2 (n − 2)(q − c) − = + (c, k) = + n n n n(1 − c) n n(1 − c)

(3)

k=1

By (1) and (3)



pn Sh 1 (X ) d X = Cn (c)

1 (n − 2)(1 − q) + n n(1 − c)

123

A. Jelnov, Y. Tauman

Note that if c > q then 1 is a dictator and is a pivot in every order . In this case its Shapley value is 1.

We are now ready to prove the theorem. Proof of the Theorem Without loss of generality we prove the theorem for i = 1. Let f X i (xi ) be the density distribution function of X i (derived from the fact that X = (X 1 , . . . , X n ) has a uniform distribution on An . Lemma 4 f X i (x) = (n − 1)(1 − x)n−2 Proof By Lemmas 1 and 2 Yi X i ∼ n

j=1 Y j

FX i (x) = Pr ob(X i ≤ x) =

∼ β(1, n − 1)

n−1   n−1 j=1

=

n−1   j=0

n−1 j

j

x j (1 − x)n−1− j

x j (1 − x)n−1− j − (1 − x)n−1 = 1 − (1 − x)n−1

Consequently f X i (x) = (n − 1)(1 − x)n−2



as claimed. Next define for every x1 , 0 ≤ x1 ≤ 1, the set Bn−1 (x1 ) ⊆ Bn−1 (x1 ) =



Rn−1

by

n     x2 , . . . , xn  x j = 1 − x1 , x j ≥ 0 j=2

Also denote by f X −1 (x2 , . . . , xn |X 1 = x1 ) the conditional density function of (X 2 , . . . , X n ) on Bn−1 (x1 ). Then 

Exp



Sh 1 (X ) ,n = X1

pn

x∈An

1 =

Sh 1 (x) d x1 , . . . , d xn x1 ⎡

⎢ f X 1 (x1 ) ⎣

⎤



Bn−1 (x1 )

0

Sh 1 (x) ⎥ f X −1 (x2 , . . . , xn |x1 ) d x2 , . . . , d xn ⎦ d x1 x1

By Lemma 4

1 =

⎡ ⎢ (n − 1)(1 − x1 )n−2 ⎣

0

⎤



Bn−1 (x1 )

f X −1 (x2 , . . . , xn |x1 )

Sh 1 (x) ⎥ d x2 , . . . , d xn ⎦ d x1 x1 (4)

123

Voting power and proportional representation of voters

Note that Sh 1 (x) = 1 whenever x1 > q (1 is a dictator in this case). Also, by Proposition 1 if x1 ≤ q then



 f X −1 (x2 , . . . , xn |x1 )Sh 1 (x) d x2 , . . . , d xn = pn Sh 1 (x) d x (5) Bn−1 (x1 )

Cn (x1 )

 n−2

=

x1 n 1−x1 , (n−2) 1 n + n(1−x1 ) (1 − q),

x1 ≤ 1 − q 1 − q < x1 ≤ q

By (4) and (5) Sh 1 (X ) E x p( , n) = X1

1−q

(n − 1)(n − 2) (1 − x1 )n−3 d x1 n

0

q  + 1−q

(n − 1) (1 − x1 )n−2 n x1

 (n − 1)(n − 2) (1 − x1 )n−3 (1 − q) d x1 + n x1

1 + q

(n − 1)(1 − x1 )n−2 d x1 x1

(6)

But 1−q

0

(n − 1)(n − 2) (1 − x1 )n−3 d x1 n

1−q  n−1 n − 1 n − 1 n−2 n−2  (1 − x1 )  − q =− = n n n 0

(7)

and

q  0≤ 1−q

 (n − 1) (1 − x1 )n−2 (n − 1)(n − 2) (1 − x1 )n−3 (1 − q) d x1 + n x1 n x1

n−1 ≤ n(1 − q)



q  (1 − x1 )n−2 + (n − 2)(1 − x1 )n−3 (1 − q) d x1 1−q

q   (1 − x1 )n−1 n−1 n−2  − − (1 − q)(1 − x1 ) =  n(1 − q) n−1 1−q =

(n − 1)q n−2 (1 − q)n−2 (1 − q)n−2 (n − 1) q n−1 + − − n(1 − q) n n n

(8)

123

A. Jelnov, Y. Tauman

and

1 0≤ q

(n − 1)(1 − x1 )n−2 n−1 d x1 ≤ x1 q

1  1 (1 − q)n−1 n−1  = − (1 − x1 )  = q q

1 (1 − x1 )n−2 d x1 q

(9)

q

Consequently by (6), (7), (8) and (9) n−1 (1 − q n−2 ) ≤ E x p n +



q n−1 Sh 1 (X ) n−1 + − (1 − q)n−2 ,n ≤ X1 n n(1 − q)

(1 − q)n−1 q

Equivalently −

q n−1 1 n − 1 n−2 Sh 1 (X ) 1 − q − (1 − q)n−2 ≤ E x p( , n) − 1 ≤ + n n X1 n n(1 − q) (1 − q)n−1 . + q

Since 0 < q < 1  Exp

 Sh 1 (X ) 1 , ,n − 1 = O X1 n

and the proof of the theorem is complete.



Remarks 1 The assumption that An has uniform distribution is essential. As a trivial counter example, suppose that the distribution on An is such that Pr ob(q < X 1 ≤ 1 − ) = 1, 0 <  < 1 − q. In this case Sh 1 (X ) = 1 and X 1 < 1 with probability 1. In addition, by Proposition 1, for q = 0.5 if the size of Party 1 is c with probability1, and the size of the other parties are distributed uniformly, then ) 1 , n converges to 1−c > 1, as n → ∞. E x p ShX1 (X 1

) 2 The variance of the random ratio ShXi (X can be calculated numerically using i Monte-Carlo simulation and the approximation method of Owen (1975). The sim) is small and converges to 0 ulation shows, that for q = 0.5 the variance of ShXi (X i when n increases (see Fig. 2).

The next proposition following Neyman (1982) states that if X is uniformly dis) converges to 1 in probability, as n increases. tributed on An , then the ratio ShXi (X i

123

Voting power and proportional representation of voters

 Fig. 2 V ar



Sh 1 (X ) X 1 , n , q = 0.5

Proposition 2 Let q ≥ 0.5. Suppose X is uniformly distributedon An . Then   ) for any  > 0, there exists n  s.t. whenever n > n  Pr ob  ShX1 (X − 1 1  >  < .  ) Note that Proposition 2 does not imply that E x p ShX1 (X converges to 1, as n → 1 ∞, since the random variable converges to infinity.

Sh 1 (X ) X1

has no upper bound and for some realizations

First, we prove the following lemma.

n Lemma 5 limn→∞ E x p( i=1 |Sh i (X ) − X i |) = 0, when X is uniformly distributed on An . n n Proof Since i=1 Sh i (x) = i=1 xi = 1,

Proof

7

n 

|Sh i (x) − xi | ≤ 2

(10)

i=1

for any realization X = x ∈ An . Applying Neyman (1982, Main Theorem) we have that for every  > 0, there exists δ() > 0 s.t. for every n and for every x ∈ An max xi ≤ δ() ⇒

1≤i≤n

n  i=1

|Sh i (x) − xi | <

 . 3

(11)

7 This proof was contributed by Abraham Neyman.

123

A. Jelnov, Y. Tauman

Next we compute for every η, 0 < η < 1, the probability that X i ≤ η. To that end denote Bni (η) = {x ∈ An |η ≤ xi ≤ 1} n  xi = 1 − η} An (1 − η) = {x ∈ Rn+ | i=1

It could be verified that V ol(Bni (η)) = V ol(An (1 − η)) = (1 − η)n−1 V ol(An ) and Pr ob(X i > η) =

V ol(Bni (η)) = (1 − η)n−1 . V ol(An )

(12)

Hence for every i, 1 ≤ i ≤ n, Pr ob(X i > δ()) = (1 − δ())n−1 . Since δ() does not depend on n and 0 < δ() < 1, for n sufficiently large Pr ob(X i > δ()) <

 . 3n

This implies that

   Pr ob ∃i ∈ N s.t. X i > δ() ≤ . 3 Since X has uniform distribution over An Exp

n 



|Sh i (X ) − X i |



i=1

=

Pn En

n 

(13)

|Sh i (x) − xi | d x +

Pn An  E n

i=1

n 

|Sh i (x) − xi | d x

i=1

n where E n = {x ∈ An | max xi ≤ δ(∈)}. By (11) i=1 |Sh i (x) − xi | < ∈3 for every 1≤i≤4  n x ∈ E n and every n. By (10) i=1 |Sh i (x) − xi | ≤ 2 for every x ∈ An . Hence EXP

 n 

 |Sh i (x) − xi | <

i=1

∈ Prob(E n ) + 2Prob(An E n ) 3

By (13), for n sufficiently large Exp

 n  i=1

123

 |Sh i (x) − xi | <

∈ 2∈ + =∈ . 3 3

Voting power and proportional representation of voters



as claimed.

We proceed to prove Proposition 2. Let 1 > 0. By Lemma 5, for n sufficiently large n  E x p|Sh i (X ) − X i | < 1 i=1

Since the distribution of X on An is symmetric n E x p|Sh 1 (X ) − X 1 | ≤ 1 .

(14)

Clearly,      Sh (X )    1   Pr ob  − 1 >  = Pr ob Sh 1 (X ) − X 1  >  X 1 . X1 For any 1 > c > 0,           Pr ob  Sh 1 (X ) − X 1  >  X 1 = Pr ob  Sh 1 (X ) − X 1  >  X 1 and X 1 > c      +Pr ob Sh 1 (X ) − X 1  >  X 1 and X 1 ≤ c      ≤ Pr ob Sh 1 (X ) − X 1  > c and X 1 > c +Pr ob(X 1 ≤ c)

(15)

By the Markov inequality and (14),    E x p(|Sh (X ) − X |) 1 1   Pr ob Sh 1 (X ) − X 1  > c and X 1 > c ≤ ≤ . c cn

(16)

By (12) Pr ob(X 1 ≤ c) = 1 − (1 − c)n−1 . From (15), (16) and (17) we have    1   + 1 − (1 − c)n−1 . Pr ob Sh 1 (X ) − X 1  >  X 1 ≤ cn Let c =

δ n.

(17)

(18)

From (18),     1 δ  n−1   Pr ob Sh 1 (X ) − X 1  >  X 1 ≤  + 1 − 1 − δ n 



Since (1 − δn )n−1 → e−δ , as n → ∞, there exists n(δ  ) s.t. if n > n(δ  ), then   (1 − δn )n−1 > e−δ − 3 . Hence,    1     Pr ob  Sh 1 (X ) − X 1  >  X 1 ≤  + 1 − e−δ + . δ 3

123

A. Jelnov, Y. Tauman 

Let δ  be sufficiently small s.t. 1 − e−δ < 3 . Let n > n(δ  ). Then    1 2   Pr ob Sh 1 (X ) − X 1  >  X 1 ≤  + . δ 3 Let 1 be sufficiently small, such that

1 δ 

< 3 . Then for n sufficiently large

     Pr ob Sh 1 (X ) − X 1  >  X 1 < 

3 The Banzhaf index In this section we show numerically that our result fails to hold if we replace the Shapley–Shubik index by the Banzhaf index even for q = 0.5. We use the next lemma for our numerical calculations. Lemma 6 Let q = 0.5. Then  Bz (X )  1 ,n X1  n−2 

0.5 n−2  n−1  n−2 1 = n−1 (1 − n)(1 − x1 )n−2 k j 2

Exp

 ×

0

0.5 1 − x1

k=1

j 1−

0.5 1 − x1

j=k

n−2− j 

j n−2− j    0.5 − x1 1 0.5 − x1 1− − dx 1 − x1 1 − x1 x1

1 +

(1 − n)(1 − x1 )n−2 d x1 x1

(19)

0.5

Proof The proof is similar to the proof of the Theorem.



  ) Figure 3 below describes the numerical calculation of E x p BzX1 (X , n using 1   ) Lemma 6 above. It illustrates that E x p Bz(X , n does not converge. X1 As for the normalized Banzhaf index, Chang et al. (2006) found that for q = 0.5 the normalized Banzhaf index of a party converges to its size. When q differs from 0.5 there is no convergence. Finally, a recent paper by Houy and Zwicker (2013) uses a version of the Banzhaf index (which is 2n−1 times the Banzhaf index) measuring the number of times a party (a player) is pivot, given weights and quota. They provide geometrical characterization

123

Voting power and proportional representation of voters

 Fig. 3 E x p



Bz i (X ) X i , n for q = 0.5

of the class of simple games for which the Banzhaf index of parties serve as voting weights and hence perfectly reflect the proportional representation. Analogous results for the Shapley–Shubik index are not known. Another related paper is Peleg (1968) who showed that the nucleolus (Schmeidler 1969) of a constant-sum weighted majority game G is a system of weights  for G. If G is in additional homogeneous for a system of weights (w1 , . . . , wn ) ( i∈S wi = q for all minimal winning coalitions S), then the nucleolus is the unique normalized homogeneous representation of G which assigns a zero weight to each dummy player of G. 4 Empirical evidence We analyzed all 26 elections of the Second Chamber (“Tweede Kamer”) of the Netherlands’ parliament since 1918 (the first time the PR system was introduced in the Netherlands). The data was taken from Mackie and Rose (1991), Eijk (1989), Lucardie and Voerman (1995), Irwin (1999), Lucardie (2003), Lucardie and Voerman (2004), Lucardie (2007) and Lucardie and Voerman (2011). In these elections we only consider parties that entered the parliament.8 For each party we calculated the ratio of its Shapley value to its size (the size is defined as the fraction of popular vote it received).9 Since parties in parliaments change over time we could not average this ratio over elections. Instead for every election we took the average of this ratio over the elected parties. For parliaments of 10 or more parties the average ratio is close to 1 and the variance is close to 0. Figure 4 summarizes our findings. 8 We also ignored parties classified as “others” in the data sources we used. In most cases those parties did not obtain sufficient votes to pass the electoral threshold. 9 For parliaments of at least 10 parties we use for the Shapley value the approximation method of Owen

(1975)

123

A. Jelnov, Y. Tauman

Fig. 4 The data analysis for the elections in the Netherlands, 1918–2010

Fig. 5 The data analysis for the elections in the Netherlands, 1918–2010: the Banzhaf index

123

Voting power and proportional representation of voters

Fig. 6 The data analysis for the elections in the Netherlands, 1918–2010: the normalized Banzhaf index

Remark We made similar calculations for the Banzhaf index. In most cases the expected value of the ratio of the party’s Banzhaf index to its size is close to be a constant significantly larger than 1, and the variance is relatively high (see Fig. 5). However, for the normalized Banzhaf index, the results (Fig. 6) are close to those for the Shapley value. Acknowledgments The authors thank Abraham Diskin, Pradeep Dubey, David Gilat, Dennis Leech, Abraham Neyman, Ronny Razin and Dov Samet for useful discussion and remarks. Special thanks go to Abraham Neyman for contributing Proposition 2.

References Banzhaf JF (1964) Weighted voting doesn’t work: a mathematical analysis. Rutgers Law Rev 19:317–343 Banzhaf JF (1968) One man, 3.312 votes: a mathematical analysis of the Electoral College. Villanova Law Rev 13:304–332 Chang PL, Chua VCH, Machover M (2006) LS Penrose’s limit theorem: tests by simulation. Math Soc Sci 51(1):90–106 Dubey P (1975) On the uniqueness of the Shapley value. Int J Game Theory 4(3):131–139 Dubey P, Einy E, Haimanko O (2005) Compound voting and the Banzhaf index. Games Econ Behav 51(1):20–30 Dubey P, Shapley LS (1979) Mathematical properties of the Banzhaf power index. Math Oper Res 4:99–131 Feller W (1971) An introduction to probability theory and its applications, vol II. Wiley, New York Felsenthal DS, Machover M (1998) The measurement of voting power: theory and practice, problems and paradoxes. Edward Elgar, Cheltenham Felsenthal DS, Machover M (2005) Voting power measurement: a story of misreinvention. Soc Choice Welfare 25(2):485–506

123

A. Jelnov, Y. Tauman Holst L (1980) On the lengths of the pieces of a stick broken at random. J Appl Probab 17:623–634 Houy N, Zwicker WS (2013) The geometry of voting power: weighted voting and hyper-ellipsoids. Games Econ Behav 79:75 Irwin GA (1999) The Dutch parliamentary election of 1998. Elect Stud 18(2):271–276 Jambunathan MV (1954) Some properties of beta and gamma distributions. Annals Math Stat 25(2):401–405 Lehrer E (1988) An axiomatization of the Banzhaf value. Int J Game Theory 17:89–99 Lindner I, Machover M (2004) LS Penrose’s limit theorem: proof of some special cases. Math Soc Sci 47(1):37–49 Lindner I, Owen G (2007) Cases where the penrose limit theorem does not hold. Math Soc Sci 53:232 Lucardie P (2003) The Netherlands. Eur J Polit Res 42(7–8):1029–1036 Lucardie P (2007) The Netherlands. Eur J Polit Res 46(7–8):1041–1048 Lucardie P, Voerman G (1995) The Netherlands. Eur J Polit Res 28(3–4):427–436 Lucardie P, Voerman G (2004) The Netherlands. Eur J Polit Res 43(7–8):1084–1092 Lucardie P, Voerman G (2011) The Netherlands. Eur J Polit Res 50(7–8):1070–1076 Mackie TT, Rose R (1991) The international almanac of electoral history, 3rd edn. Macmillan Press Ltd., Basingstoke Neyman A (1982) Renewal theory for sampling without replacement. Ann Probab 10:464–481 Nozick R (1968) Weighted voting and ’one-man, one-vote’. In: Pennock, Chapman (eds) Representation. Atherton Press, New York, pp 217–225 Nurmi H (1981) The problem of the right distribution of voting power. In: Holler (ed) Power, voting and voting power. Physica, Heidelberg, pp 203–212 Owen G (1975) Evaluation of a presidential election game. Am Polit Sci Rev 69(3):947–953 Peleg B (1968) On weights of constant-sum majority games. SIAM J Appl Math 16(3):527–532 Penrose LS (1952) On the objective study of crowd behaviour. HK Lewis, London Rae D, Hanby V, Loosemore J (1971) Thresholds of representation and thresholds of exclusion. Comp Polit Stud 3(4):479–488 Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17(6):1163–1170 Shapiro NZ, Shapley LS (1978) Values of large games, i: a limit theorem. Math Oper Res 3:1–9 Shapley LS (1953) A value for n-person games. In: Kuhn, Tucker (eds) Contributions to the theory of games, vol 2. Princeton University Press, Princeton, pp 31–40 Shapley LS (1961) Values of games with infinitely many players. RAND Corporation, Santa Monica Shapley LS, Shubik M (1954) A method for evaluating the distribution of power in a committee system. Am Polit Sci Rev 48(3):787–792 Van Der Eijk C (1989) The Netherlands. Elect Stud 8(3):305–312 Young HP (1985) Monotonic solutions of cooperative games. Int J Game Theory 14(2):65–72

123