On Random Quotas and Proportional Representation in Weighted Voting Games

1 Introduction

In weighted voting games (WVGs), there is a group of players N = {1, . . . , n}, each player i ∈ N has a positive weight wi ∈ Z+. A subset of players S ⊆ N is called winning if the total weight of its members is at least some given threshold (often referred to as a quota). Weighted voting games are a simple yet expressive method of representing and studying electoral bodies such as political parties or company shareholders. In particular, they are used to evaluate the a-priori voting power of players. WVGs play an important role in modelling multi-agent systems. For example, player weights can be thought of as resources (computing power, fuel, etc.), and the threshold as the minimum amount of resources required to complete a task. Consider also the following example: a group of agents has committed to spending no more than q resources (say, in an energy market); however, each agent i ∈ N has spent an amount of wi, where total consumption exceeds q. In this setting, voting power could be seen as the share each agent has in the exceeded cost. 1

A power index is a measure of players' influence in a WVG. Briefly, given a set of players N, a weight vector w ∈ Zn+, and some quota q, we write the WVG induced as G = 〈N,w, q〉; a power measure is a function α whose input is a WVG G, and whose output is a vector α(G) ∈ Rn whose i-th coordinate is the power of player i under G according to α. Two popular power measures are the Banzhaf power index [Banzhaf, 1964], and the Shapley-Shubik power index [Shapley and Shubik, 1954] (SSPI); the latter is the focus of this work.

Given a weighted voting game, it is often desirable to ensure that the voting power of a party (as given by some power measure) is proportional to its weight; this is known as proportional representation [Penrose, 1946]. Intuitively, if weights represent state populations (say, in the case of the EU council of members), then a game with good proportional representation is one where each citizen is equally influential, regardless of the state he belongs to. In a multi-agent system, if a game has the proportional representation property, then players' power is approximately proportional to their weights. Players' power is often used in order to divide rewards (say, for completing a task): each agent receives a reward proportional to his power; such payoff divisions have several highlydesirable properties. However, sharing rewards in proportion to agent weights is often simpler and more intuitive. Thus, if proportional representation holds, then proportional reward sharing will have those properties as well. Formally, given a power measure α and a weighted voting game G = 〈N, w, q〉, G has the ε-proportional representation property if for all players i, j ∈ N, | αi(G) αj (G) - wi wj | ≤ ε. ε-proportional representation means that the weighted voting game satisfies the "one person - one vote" rule, up to an error term of ε. An alternative approach to proportional representation is given by Monroe [1995] and by Chamberlin and Courant [1983]; in this setting, we are given a group of voters, each listing his preference over a set of candidates. The objective is to find a set of k candidates that best represent the voters. We stress that we follow the interpretation of proportional representation given by Penrose [1946], and not the one in [Monroe, 1995; Chamberlin and Courant, 1983].

1 see also Chalkiadakis et al. [2011] for a discussion of WVGs in multi-agent systems.

Penrose's square root method ensures ε-proportional representation w.r.t. the Banzhaf power index via changing the actual number of parliament seats each party/state receives. The square root method states that voting bodies whose parties correspond to populations should have their number of seats proportional to the square root of the weight (population size). If weights are w1, . . . ,wn, the actual number of seats for i ∈ N should be √wi; this is because the Banzhaf power index of player i tends to 1 √wi as the number of players grows.

Quota manipulation can be used in order to achieve εproportional representation; that is, given a vector of weights w and ε > 0, find q0 s.t. for some power measure α, the weighted voting game G0 = 〈N,w, q0〉 has ε-proportional representation. Quota manipulation is preferable to weight reassignment in many scenarios. First, in multi-agent systems, weights correspond to agent resources, which cannot be easily changed; second, even when weight changes are feasible, changes to the quota are more subtle: they are more easily made, but their effects not immediately obvious. This means that it is easier for parties to agree upon changes to the quota, rather than to changes to the number seats they receive.

Manipulating the quota is a delicate matter; power indices tend to be highly sensitive to small changes in the underlying voting game, and in particular to changes in the quota [Zick et al., 2011; Zuckerman et al., 2012]. These changes can, however, occur fairly often: the amount of resources required to complete a task may change, or in the voting perspective, the number of votes required to pass a law may be changed.

1.1 Our Contribution

We analyze approximate proportional representation under the Shapley-Shubik power index, and propose some conditions under which it is maintained via selecting a proper quota. We provide a general bound on the variance of the Shapley value, and show that an improved bound holds for the player with the smallest weight. While our bounds are not particularly tight for general weights, if one assumes that weights exhibit some clustering, we show that the variance tends to be low, especially for players with small weights. Further, we identify a parameter which to a great extent governs the variance of the Shapley value as a function of the quota. We study expected bounds on that parameter when weights are selected from a binomial distribution. These findings are further corroborated by empirical analysis.

From the multi-agent perspective, our results show that under certain assumptions on agent weights, small changes to the amount of resources required to complete a task will not greatly affect the influence agents have: they will, on average, have influence proportional to their weight. From the majority voting perspective, our results show that quota manipulation is not likely to result in great changes to players' power, especially if the threshold is set at 50% of the votes. For both frameworks, weight clustering is an important factor in making players' power resistent to changes to the quota.

1.2 RelatedWork

Proportional representation is a well-studied problem, initiated by Penrose [1946]. 2 The effects of changes to the quota have been previously studied (see, e.g. [Leech and Machover, 2003; Machover, 2007]).

Recently, Tauman and Jelnov [2012] show that approximate proportional representation is achieved in expectation when weights are chosen at random for a fixed quota. These results hold for both the Shapley-Shubik and the Banzhaf power indices. Rather than choosing weights at random, we fix the set of weights and choose a quota at random. Despite the difference in the probability space, our theoretical results strongly support the empirical observations made in [Tauman and Jelnov, 2012]. Neyman [1982], followed by Lindner [2004] perform asymptotic analysis of certain classes of weighted voting games, showing that approximate proportional representation is achieved as the number of players goes to infinity, assuming the weighted voting game has certain properties. H¨aggstr ¨om et al. [2006] also study the asymptotic behavior of weighted voting games.

Changes to the quota have been extensively studied from a computational perspective. Faliszewski and Hemaspanndra [2009] study computational aspects of comparing a player's power in two weighted voting games. Słomczy´nski and ˙Zyczkowski [2006] use a brute force method in order to find a quota that minimizes the total distance of players' Banzhaf power index from their proportional weight in the EU Council (the quota is approximately 61.5%). However, previous hardness results for computing power indices imply that their algorithm is inefficient (see [Chalkiadakis et al., 2011] for an overview). Zuckerman et al. [2012] and Zick et al. [2011] study computational and non-computational aspects of changes to the quota in WVGs. Finally, while we use probabilistic tools in a more traditional manner, probabilistic analysis is also used in order to approximately compute power indices [Bachrach et al., 2010; Fatima et al., 2008].

2 Preliminaries

Throughout the paper, we refer to vectors as boldface lowercase characters and sets as uppercase letters. Given a set S, |S| refers to the size of S. Given a random variable X, let E[X] denote its expected value, and var[X] denote its variance; the standard deviation of X is √var[X]. A weighted voting game (WVG) G = 〈N, w, q〉 is given by a set of players N = {1, . . . , n}, a vector w = (w1, . . . , wn) ∈ Zn+ and a quota q ∈ Z+. Given a set S ⊆ N, w(S) is the total weight of the members of S, i.e. w(S) = ∑i∈S wi. S is called winning

2 Penrose' proposed power measure is similar to that proposed by Banzhaf [1964]; see also [Felsenthal and Machover, 2005] for an overview of various power indices and their history.

(has value 1) if w(S) ≥ q and is called losing (has value 0) otherwise. We write v(S) = 1 if S is winning, and v(S) = 0 otherwise. We say that a player i is pivotal for a set S if v(S) = 0, but v(S ∪ {i}) = 1. Let Π(N ) denote the space of all permutations (also referred to as orderings) over N. Given some σ ∈ Π(N ), let Pi(σ) be the set of all of i's predecessors in σ; that is, Pi(σ) equals {j ∈ N | σ(j) < σ(i)}. We say that i is pivotal for σ if i is pivotal for Pi(σ), i.e. if w(Pi(σ)) < q, but w(Pi(σ)) + wi ≥ q.

The Shapley-Shubik power index [Shapley and Shubik, 1954; Shapley, 1953] is a function ϕ whose input is a WVG G, and whose output is a list of values ϕ1(G), . . . , ϕn(G). The value ϕi(G) is the probability that i is pivotal for a permutation σ selected uniformly at random from Π(N ). Formally:

In what follows, we fix the weights w1, . . . ,wn, and assume that they are positive, whereas q is a random variable. Specifically, we let q be a random variable according to the uniform distribution over {1, . . . , w(N )}, denoted U (1, w(N )).

We are interested in the random variable ϕi(q), which is the Shapley value of player i when the quota is q. That is, fixing the weights of all players, we randomly pick a quota from 1, . . . , w(N ) and measure the Shapley value of player i.

3 The Variance of ϕi(q)

Let us set

Pivi,σ(q) = {1 if i is pivotal for σ when the quota is q 0 otherwise. .

We observe that ϕi(q) =

1

n!

∑σ∈Π(N

)

It is a well-known fact that Eq∼U[1,w(N )] [ϕi(q)] = wi w(N ) [Mann and Shapley, 1960]. While proportional representation is achievable (in expectation) by taking a random quota, ϕi(q) may exhibit a high degree of fluctuation. We are thus interested in bounding the margin of error between ϕi(q) and wi w(N ) .

Experimental results in [Zick et al., 2011] indicate that ϕi(q) generally exhibits low variance, assuming that one takes a quota not too far from 50% of the total weight. That is, approximate proportional representation is achieved for a randomly chosen quota, if one selects a quota close to 0.5w(N ). These results are in line with the observations made by Jelnov and Tauman [2012]. We now identify conditions that ensure that this is indeed the case.

Given two permutations σ, τ ∈ Π(N ), let us observe the random variable Pivi,σ(q) · Pivi,τ(q); it takes a value of 1 whenever player i is pivotal for both σ and τ, and is 0 otherwise. Intuitively, player i can be pivotal for two permutations only if the weight of the predecessors of i is not too different in σ and τ. If the weights of the predecessors are too far apart, then whenever a quota q allows i to be pivotal for one permutation, it prohibits him from being pivotal for the other. We formalize this notion in the following lemma.

Pivi,σ(q).

Lemma 3.1. Given a player i ∈ N and two permutations σ, τ ∈ Π(N ), Pr(Pivi,σ(q)Pivi,τ (q) = 1) equals

Proof. Player i is pivotal for σ only when w(Pi(σ)) < q ≤ w(Pi(σ)) + wi; similarly, player i is pivotal for τ only when w(Pi(τ)) < q ≤ w(Pi(τ)) + wi. He is pivotal for both permutations only when q is strictly greater than max{w(Pi(σ)),w(Pi(τ))}, and is at most min{w(Pi(σ)),w(Pi(τ))} + wi. Note that max{a, b} - min{a, b} = |a - b|; therefore, if wi ≤ |w(Pi(σ)) - w(Pi(τ))| then i is never pivotal for both σ and τ. Otherwise, player i is pivotal for both σ and τ when q = max{w(Pi(σ)),w(Pi(τ))} + 1, . . . ,min{w(Pi(σ)),w(Pi(τ))} + wi. This is a total of wi - |w(Pi(σ)) -w(Pi(τ))| quotas.

Recall that var[X] = E[X2 ] - E[X]2 . Thus, in order to compute var[ϕi(q)] we must first derive an explicit formula for E[ϕi(q)2 ]. Let us first analyze the expression ϕi(q)2 . Given some w ∈ Z, we set

Πi,σ(w) is the set of all permutations such that the weight of i's predecessors is a distance of exactly w from the weight of i's predecessors in σ. We observe that

Thus, by linearity of expectation, we get that E[ϕi(q)2 ] equals

which, by Lemma 3.1, equals

Using (2), we now proceed to provide some upper bounds on the variance of ϕi(q). We recall the following lemma from Zick et al. [2011] (Lemma 4.1).

Lemma 3.2. Let Φi(w) be the set of permutations such that the weight of i's predecessors is at strictly less than w; then for all a, b ∈ Z+, |Φi(a)| + |Φi(b)| ≥ |Φi(a + b)|.

Let Πi(w) be the set of all permutations such that the weight of i's predecessors is exactly w; Lemma 3.2 implies the following corollary.

Corollary 3.3. |Πi(w)| ≤ (n - 1)!; moreover, if wi = minj∈N wj , then the set of all permutations such that i's predecessors have a weight between w and w+wi - 1 has a size of at most (n1)!.

Proof. We observe that Πi(w) = Φi(w + 1) \ Φi(w); since Φi(w) ⊆ Φi(w + 1), we have that |Πi(w)| = |Φi(w + 1)| - |Φi(w)|. By Lemma 3.2, |Φi(w + 1)| - |Φi(w)| ≤ |Φi(1)|; however, Φi(1) is the set of all permutations where the weight of i's predecessors is exactly 0. Since all weights are positive, Φi(1) is the set of all permutations where i is first, thus has a size of (n1)!, which concludes the proof.

Similarly, The size of the set Φi(w+wi)\Φi(w) is at most |Φi(wi)|. If wi = minj∈N wj , Φi(wi) consists only of the permutations where i is first, which proves the second part of the claim.

Using Corollary 3.3, we are able to prove the following result.

Lemma 3.4. For all i ∈ N and all σ ∈ Π(N ), |Πi,σ(w)| ≤ 2(n - 1)!. Moreover, if wi = minj∈N wj, then | ⋃wi-1 w=0 Πi,σ(w)| ≤ 2(n - 1)!.

Proof. Both claims follow immediately from the observation that

and then invoking the upper bounds set in Corollary 3.3.

Lemma 3.4 provides an upper bound on the size of Πi,σ(w), which proves to be instrumental in showing the following result:

Theorem 3.5. For all i ∈ N:

Moreover, if wi ≤ wj for all j in N, then

Proof. Using Lemma 3.4, we obtain the following upper bound on E[ϕi(q)2 ]:

Finally, we deduct E[ϕi(q)]2 = w2 i w(N )2 from the final term to obtain the desired upper bound on var[ϕi(q)]. For the player with the smallest weight, we can obtain a better bound on E[ϕi(q)2 ] via Corollary 3.3.

Theorem 3.5 implies the following corollary

Corollary 3.6. Suppose that all weights are drawn from an interval [a, b], where both a and b are constants independent of n; then var[ϕi(q)] is in O( 1 n2 )

Proof. According to Theorem 3.5,

var[ϕi(q)] ≤ wi(wi + 1) nw(N ) ≤ b(b + 1) n2a where the last expression is in O( 1 n2 )

Note that if we assume that weights are bounded by a constant, wi w(N ) is in O( 1n ); therefore, Corollary 3.6 simply implies that the standard deviation and the mean of ϕi(q) decrease in the same rate, i.e. are within a multiplicative constant of each other. We observe that the bounds derived in Theorem 3.5 can be rewritten as

this implies that the constant term in the ratio between the standard deviation and the mean (also known as the coefficient of variation) is given by √ wi+1 wi w(N ) n - 1. The constant term is dominated by the value w(N ) n , or the average weight of the players. In general, the bound derived in Theorem 3.5 does not strongly depend on wi, as wi+1 wi is at most 2, and tends to 1 as wi grows. In general, the standard deviation tends to 0 as w(N ) n tends to 1. That is, var[ϕi(q)] grows smaller as weights grow smaller.

For the player with the smallest weight, the variation coefficient is √ 1n w(N ) wi - 1. This means that if the smallest weight is close to the average weight, then the variation coefficient tends to 0. For example, in a setting where weights are clustered, there will be many quotas for which the Shapley value of the players with a small weight is close to wi w(N ) .

4 Bounds on |Πi(w)|

Recall that Πi(w) is the set of permutations such that the weight of i's predecessors is exactly w.

Consider the following setting: we sample n weights independently at random from a binomial distribution, and then randomly choose a quota. Formally, let W1, . . . ,Wn ∼

B(Q, 12 ), i.e. Pr[Wi = w] = (Qw) 1 2Q . In order to set the weight of player i, we simply sample a value 0, . . . ,Q from a binomial distribution. In this setting, we provide bounds on the expected size of Πi(w). As shown in Theorem 3.5, general bounds on the size of Πi(w) would be useful in bounding var[ϕi(q)].

Fixing i, let Pi,q be a random variable corresponding to the number of permutations for which Pi(σ) has a weight of q. Let Pi,q,k be the number of permutations such that Pi(σ) has a weight of q and size k. Observe that Pi,q = ∑n-1 k=0 Pi,q,k. Let Si,q,k be the number of subsets of N \ {i} such that w(S) = q and |S| = k. We write Ni,k to be {S ⊆ N \ {i} | |S| = k}. Let IS,q be a random variable that equals 1 if w(S) = q and 0 otherwise. We note that if |S| = k, E[IS,q = 1] = (kQ q )2-kQ. Assuming that k ≤ q,

We conclude that

where we assume that if m < k, then (mk ) = 0. Note that ∑n-1 k=0 (kQ q )2-kQ is upper bounded by ∑(n-1)Q j=q (jq)2-j . Let us denote ξm,k = ∑mj=k (jk)2-j . Since some of the realized values of W1, . . . ,Wn may be 0, we cannot rely on Lemma 3.4 to upper-bound E[Pi,q]. However, as the following lemma shows, a similar bound holds in expectation.

Lemma 4.1. Given m, k ∈ Z+ such that k ≤ m, ξm,k ≤ 2; moreover, for any k > 0, limm→∞ ξm,k = 2.

Proof. Let us observe the function f(x) = xk (1-x)k+1 , for k ≥ 1; whenever x < 1 we have

The righthand expression simply equals ∑∞j=k (jk)xj . Now, on one hand, f( 12 ) = 2; on the other hand, f( 12 ) = ∑∞j=k (jk)2-j . Since ξm,k is a partial sum of f( 12 ), and all summands are positive, we have ξm,k ≤ f( 12 ) = 2; moreover we have limm→∞ ξm,k = f( 12 ) = 2, so this upper bound is tight.

Lemma 4.1 implies that E[Pi,q] ≤ 2(n - 1)! for all i and all q. The upper bound shown in Lemma 4.1 can be further improved for many values of q; we now provide an improved bound of O( q 2q ) on all ξnQ,q such that q is far from nQ .

2

Theorem 4.2. For all q such that q ≥ ρ-1 ρ nQ or 1 ≤ q ≤ 1ρ nQ, ξnQ,q is in O( q 2q ), where ρ is a constant between 3 and 3.055.

Proof. We observe that for all m, k ∈ Z+ such that m > k ≥ 1, we have

where log is the base-2 logarithm and e is Euler's constant. Let us now look at the function f(x) = x - log ex. The function f has two real roots, one of them, denoted by ρ, is slightly greater than 3 (3 < ρ < 3.055). Setting x = m m-k we get that f( m m-k ) > 0 if m m-k > ρ, or if m < ρ ρ-1 k. Now, suppose that q > ρ-1 ρ nQ; for all j > q, there is some εj ∈ (0, 1) such that

Setting ε = maxj>q εj , we take c = 2ε 2 . We obtain that

We observe that we make no assumptions on Q itself; that is, unlike the general O( 1 n2 ) bound shown in Corollary 3.6, the result shown in Theorem 4.2 holds for any value of Q. In fact, the bound on E[Pi,q] decreases exponentially as Q goes to infinity. Intuitively, by selecting weights from a binomial distribution, we are very likely to select weights that are close to one another. By employing Chernoff bounds, it can be shown that as Q grows, weights are likely to be very close to Q2 , and in particular to one another; thus the resulting weighted voting game is likely to have smaller perturbations when varying the quota.

5 Empirical Analysis

Our results do not show a general bound on |Πi(w)| when weights are drawn from a binomial distribution; however, simulations show that in general, |Πi(w)| tends to be quite low. In fact, our results show that when one samples w from a region not too far from a quota of 12 w(N ), the values of |Πi(w)| tend to cluster around the mean.

Experimental Setup We have drawn 30 weights from a binomial distribution B(50, 12 ), and sorted them so that w1 ≤ · · · ≤ w30; this was repeated 100 times. For each player in the resulting weighted voting game, we have computed |Πi(w)|; this was done using dynamic programming, a method similar to that used to compute the Shapley value in weighted voting games (see [Chalkiadakis et al., 2011] for further details). We then compute the ratio of the standard deviation to the mean (the variation coefficient) of the values

|Πi(1)|, . . . , |Πi(w(N ) - 1)|; a low correlation coefficient indicates that the values |Πi(1)|, . . . , |Πi(w(N ) - 1)| tend to be clustered together, i.e. they are not too far from the mean, and in particular from each other. The correlation coefficient is a measure which does not depend on the actual value of the mean, hence allowing us to effectively compare different samples with different means.

Experimental Results The results in Section 3, as well as the results in [Zick et al., 2011], indicate that different players will display different behavior. Our results show that this is indeed the case. As seen in Figure 1, we have measured the average clustering of the values of |Πi(w)| when taking values of w at different distances from 0.5w(N ). The data series labeled 1 shows the average variation coefficient for the players as a function of their rank, when w ranged from 1 to w(N ). As is observed in Theorem 3.5, the average variation coefficient is slightly over 1 for all players. However, taking the variation coefficient over the weights ranged from 51 to w(N ) - 50 results in a significantly lower average variation coefficient. Further limiting the values of w to those closer to 0.5w(N ) results in further decreasing the variation coefficient. To conclude, when limited to a small interval around 0.5w(N ), the values of |Πi(w)| are, on average, very close to one another.

6 Conclusions and FutureWork

The main implication of our research is that manipulating the quota is not likely to dramatically change player influence, under some assumptions on the underlying WVG. First, as our empirical analysis shows, the Shapley value changes little if quotas are close to 50% of the total weight; second, weights must be not too far apart, as is shown in our theoretical results. As our analysis shows, the Shapley value exhibits higher fluctuation in the range of very large (or very small)

quotas; while this is mitigated in expectation for binomially distributed weights, this effect is not yet fully understood for the general case. However, our results provide theoretical justification to choosing quotas close to 50% in voting bodies: in addition to mitigating fluctuations in the Shapley values of players, they are likelier to ensure proportional representation.

Our work also identifies a parameter that strongly governs the behavior of var[ϕi(q)], |Πi(w)|. Providing upper bounds on |Πi(w)| is thus an important part of the analysis of var[ϕi(q)]. We show that this quantity is small in expectation when one samples weights from a binomial distribution. This fact is further corroborated by empirical analysis; we show that for WVGs whose weights are sampled from a binomial distribution, permutations tend to be evenly distributed in the sense that |Πi(w)| is close to |Πi(w′ )| for most values of w and w′ , and are almost always orders of magnitude smaller than the general upper bound of (n - 1)!. These results imply better (expected) bounds for weights sampled from binomial distributions. Other distributions of weights are likely to provide more insight into the problem, as they will result in different clustering behavior (in expectation).

Our theoretical results indicate that the fluctuation of ϕi(q) is low, and our empirical analysis indicates a range where low fluctuation occurs. However, it remains to be proven that indeed, under some assumptions on weight distribution, ϕi(q) has low fluctuation when quotas are close to 50%. Weaker results would also shed light on the behavior of ϕi(q). For example, Zick et al. [2011] show that maxϕi(q) = ϕi(wi) for all i ∈ N; however, not much is known about minϕi(q). Showing that the global minimum of ϕi(q) is never close to 50% for some classes of weights would be an important step in the understanding of the behavior of the Shapley value as a function of the quota.

In general, uncertainty in weighted voting games would be interesting to analyze: one can analyze uncertainty in WVGs when players' weights are randomized as is the case in Tauman and Jelnov [2012], or assume a different distribution of quotas e.g. a quota is sampled from a binomial distribution. Alternatively, one can study uncertainty in a natural generalization of WVGs, threshold task games. In a threshold task game, there is a list of tasks, each with a weight and a value; like a WVG, players have weights, and the value of a coalition is the largest value of a task that it complete using the total weight of its constituent players (see Chalkiadakis et al. [2010] for a detailed description of threshold task games). In this setting, one can analyze both threshold uncertainty, i.e. uncertainty w.r.t. the amount of resources that tasks require, or value uncertainty, i.e. uncertainty w.r.t. the value of tasks. Applying our analysis and methods to this more general setting would be an important step in understanding uncertainty and its effect on payoff divisions in multi-agent systems.

Acknowledgements The author was supported by the SINGA (A*STAR) scholarship, Singapore. The author thanks Edith Elkind for several useful discussions. Some of the bounds in Section 4 were obtained as part of a discussion on math.stackexchange [math.stackexchange, 2012].