The Shapley Value as a Function of the Quota in Weighted Voting Games

1 Introduction

Collective decision making is a crucial component of multiagent interaction. Consequently, assessing the power of individual voters in decision-making bodies is an important concern in the analysis of multi-agent systems. This issue is often studied within the framework of weighted voting games, where each player is associated with a weight; to win, a coalition needs to amass a weight that meets or exceeds a given threshold, or quota. Usually, the voter's power in such games is associated with her Shapley value [Shapley, 1953], which in the context of weighted voting games is also known as the Shapley-Shubik power index [Shapley and Shubik, 1954]. This quantity depends on both the players' weights and the quota of the game.

The weight of each voter is determined either by his contribution to the system (money, shares, etc.) or the size of the electorate that he represents. In either case, the voters' weights are usually hard to alter. In contrast, the quota of the game can easily be modified: for instance, a legislative body may raise the quota for decisions on certain issues from 51% of all votes to 66%. A change to the quota can have a profound effect on players' power. This phenomenon has been observed in real-life voting systems [Leech, 2002b; Leech and Machover, 2003; Machover, 2007], and recently [Zuckerman et al., 2008] embarked on a systematic study of this issue from the algorithmic perspective. For instance, [Zuckerman et al., 2008] show that one can determine in polynomial time if a player's power can be reduced to 0 by changing the quota; however, deciding which of the two given values of the quota is preferable for a given player is computationally hard.

In this paper, we continue to study the dependence between the players' power and the quota in weighted voting games. We focus on finding values of the quota that maximize/minimize the power of a given player. This is perhaps

nipulator who cares about the impact of a certain agent in a decision-making body; however, it has not been addressed by the previous work.

First, we show that if arbitrary values of the quota are allowed, a player's power can be maximized by setting the quota to that player's weight. In contrast, the associated decision problem, i.e., determining whether the current value of the quota is already optimal for a given player, is computationally hard. Thus, if the manipulation is costly, it is hard for the manipulator to determine whether it is worth the effort.

If the goal is to minimize the player's power rather than to maximize it, then the respective decision problem remains hard, but the status of the optimization problem (finding a value of the quota that minimizes the player's power) is unclear. However, we identify two values of quota, which are very likely to be good choices. The first of them is q = 1 (assuming integer weights): when the quota is small enough, all players have the same power, which is likely to be a bad deal for larger players. The second candidate is q = w + 1, where w is the target player's weight. This quota is more likely to be harmful for smaller players. We perform empirical analysis, drawing the players' weights from various probability distributions, and show that with high probability one of these values of the quota minimizes the target player's power, with the right choice usually being q = w + 1 for the smaller players and q = 1 for the larger players. We provide a (partial) analytic explanation of these results, by showing that for the bottom half of the voters (with respect to the weight) the quota q = w + 1 is strictly worse than q = 1.

While it is hard to determine whether a given value of the quota is optimal/pessimal for a given player, there are special cases of this problem that admit an efficient algorithm: namely, checking if a given quota maximizes the power of the smallest player or minimizes the power of the largest player. Both questions can be reduced to deciding whether all players are equally powerful, which turns out to be poly-time solvable. Interestingly, the complementary problem-finding a quota that ensures all players have different power-has been shown to be easy as well [Zuckerman et al., 2008].

The rest of the paper is structured as follows. We give a brief overview of related work in Section 1.1. Section 2 introduces the necessary terminology. Section 3 provides several examples that illustrate the behavior of the Shapley value as a function of the quota. Section 4 details the main theoretical results of our work, and Section 5 complements them by empirical analysis. Section 6 presents our conclusions and suggests directions for future research.

1.1 RelatedWork

Several papers are relevant to this research, with [Zuckerman et al., 2008] being the direct precursor of this work.

The complexity of computing the Shapley-Shubik power index is well understood: [Deng and Papadimitriou, 1994; Matsui and Matsui, 2001; Prasad and Kelly, 1990] show that deciding whether a player has zero power is hard (and hence computing the exact value of the index is hard, too). We remark that these hardness results do not preclude the existence of efficient algorithms for manipulating the quota: it might be possible to change a player's power in the desired direction even without knowing the exact value of his power before and after the change. Further, there are several heuristics and approximation algorithms for power computation [Mann and Shapley, 1962; Leech, 2002a; Dubey and Shapley, 1979; Bachrach et al., 2010; Fatima et al., 2008; Merrill, 1982].

There are several studies of manipulation in weighted voting games. Apart from [Zuckerman et al., 2008], [Aziz et al., 2011] study a different form of manipulation, namely, players splitting their weight among several identities, or, conversely, merging into a single identity; [Faliszewski and Hemaspaandra, 2009] consider the more general question of comparing the players' power across different weighted voting games.

An alternative approach to measuring a player's power is by means of the Banzhaf power index [Banzhaf, 1965]. The behavior of this index as a function of the quota has been studied in [Dubey and Shapley, 1979; Leech, 2002a; Merrill, 1982]; the results of this analysis have been used in developing approximation algorithms for this index [Fatima et al., 2008].

2 Preliminaries

A weighted voting game G = (w, q) is given by a vector w = (w1, . . . , wn) of positive integer weights and a positive integer quota q ∈ Z+. It is associated with a set of players N = {1, ..., n}, where the i-th player has weight wi. We order the players so that w1 ≤ w2 ≤ . . . ≤ wn. A subset, or coalition, S ⊆ N is called winning if w(S) := ∑j∈S wj ≥ q, and losing otherwise. We write v(S) = 1 if S is winning and v(S) = 0 if S is losing; it is usually stipulated that v(N) = 1, i.e., q ≤ w(N). A player i is called q-pivotal for S ⊆ N \ {i} if q -wi ≤ w(S) < q, or equivalently, if v(S) = 0, but v(S ∪ {i}) = 1. When q is clear from the context, we will simply say that i is pivotal for S. A player i is called a dummy if he is not pivotal for any coalition.

Let Π(N) be the set of permutations over N, and let Pi(σ) ⊆ N denote the set of all predecessors of player i in a permutation σ ∈ Π(N), i.e., Pi(σ) = {j ∈ N | σ(j) < σ(i)}. We say that i is q-pivotal for σ if i is qpivotal for Pi(σ). The set of all permutations for which a player i ∈ N is q-pivotal is denoted by Πi(q). The Shapley value, or Shapley-Shubik power index, [Shapley, 1953; Shapley and Shubik, 1954] of player i in a game with quota q is φi(q) = |Πi(q)| n! . This power index has a number of very attractive properties; it is efficient, i.e., ∑ni=1 φi(q) = 1, symmetric, i.e., if v(A∪{i}) = v(A∪{j}) for all A ⊆ N \{i, j}, then φi(q) = φj(q), and monotone, i.e., wi ≤ wj implies φi(q) ≤ φj (q).

As we vary the quota q, φi(q) becomes a function from Z+ to [0, 1]. Since we would like to ensure that v(N) = 1, we limit our analysis to the values of q in the interval [1, w(N)]∩ N. Note that there is no loss of generality in assuming q ∈ N: while φi(q) is well-defined for any real q ∈ [1,w(N)], all players' weights are integer, so a game (w, q) with q ∈ R is equivalent to (w, ⌊q⌋). We set opt(φi) = {q ∈ N | φi(q) ≥ φi(q′ ) for all q′ ∈ N} and pess(φi) = {q ∈ N | φi(q) ≤ φi(q′ ) for all q′ ∈ N}; these are the sets of quota values that, respectively, maximize and minimize the power of player i.

3 Examples

We start by providing several examples of weighted voting games, and investigate the behavior of a given player's power as a function of the quota in these games.

Example 3.1. We construct a 20-player game by drawing weights uniformly at random from [1, 40]; the resulting weight vector is w1 = (1, 2, 4, 5, 16, 17, 20, 21, 21, 23, 24, 24, 27, 28, 28, 33, 33, 36, 36, 40). Figure 1 shows the Shapley value of player 10 with weight 23 in games of the form (w1 , q), where q varies from 1 to w(N). We note several interesting properties of this graph. First, φi(q) is centrally symmetric; this is a well-known property of the Shapley value, referred to as self-duality [Felsenthal and Machover, 1998]. Second, the graph has two distinct peaks at w10 = 23 and w(N) - w10 + 1 = 417. This observation is in line with our theoretical results: Section 4.1 shows that φi(q) always peaks at q = wi. Third, φ10(q) has a global minimum at q = 24 = w10 + 1; Section 5 demonstrates that q = wi + 1 is often (though not always) in pess(φi). Finally, the graph plateaus at w10/w(N) ≈ 0.052 as the quota goes to w(N)+1 2 ; this phenomenon has been observed (and explained) in [Leech and Machover, 2003; Machover, 2007].

Example 3.2. We repeat the experiment in Example 3.1, but generate the players' weights according to the Poisson distribution with mean 30, obtaining weight vector w2 = (23, 24, 24, 25, 25, 25, 25, 27, 28, 28, 29, 30, 30, 32, 32, 33, 34, 34,

35, 36); we focus on the second largest player. We observe a high degree of fluctuation in the player's Shapley value.

Example 3.3. Finally, consider a weight vector of the form 1, 2, . . . , 2n . The graphs for n = 7 and players with weights 4, 16 and 64 are given in Figure 3. A remarkable property of this set of weights is the abundance of local minima and maxima; φ1 has a local maximum at any even quota and a minimum at any odd quota, and φ4(q) = 0 for q = 16, 32, 48, . . . . This is true in general for weight vectors of this form.

Quota

Figure 3: The Shapley values of players 3, 5, 7 (weights 4, 16, 64) for weight vector w3 = (1, 2, . . . , 128) (Ex. 3.3)

Proposition 3.1. If q = 2k r for some r ∈ N, then φk(q) = 0. The intuition behind Proposition 3.1 is that for k to be 2k rpivotal for a coalition S, it must be the case that 2k r-2k-1 ≤

w(S) < 2k r. But then the (k-1)-st digit of w(S) is set to 1, i.e., k ∈ S, a contradiction. A similar approach allows us to characterize the local maxima of φk.

Proposition 3.2. φk(q) has a local maximum at q = 2k-1 (2r-1), for all r ∈ N such that 2k-1 (2r-1) ≤ w(N).

Examples 3.2 and 3.3 show that φi(q) may be highly nonmonotone; if we are only allowed to change the quota within a given (small) interval, the best value of the quota is not necessarily at an endpoint of this interval.

4 Theoretical Results

In this section, we provide algorithms and hardness results for a number of problems related to maximizing or minimizing the power of a given player.

4.1 Maximizing the Shapley Value

We will now show that we can maximize the power of player i by setting q = wi. Such a quota may seem unrealistic; in a real-life voting system we typically have q ≥ w(N)/2 and wi < w(N)/2 for all i ∈ N. However, self-duality implies that our results hold for the quota w(N) - wi + 1, and w(N) - wi + 1 > w(N)/2 if wi < w(N)/2; we chose to prove our results for q = wi to improve readability.

Before we formally state our main result, let us prove the following useful lemma. We define Ti(x) = {σ ∈ Π(N) | w(Pi(σ)) < x} for all x > 0.

Proof. Without loss of generality, we assume a ≥ b. Set Ti(a, a + b) = {σ ∈ Π(N) | a ≤ w(Pi(σ)) < a + b}; since Ti(a) ⊆ Ti(a+b), we have |Ti(a+b)|-|Ti(a)| = |Ti(a, a+ b)|. Therefore, to prove that |Ti(b)| ≥ |Ti(a + b)| - |Ti(a)|, it suffices to show that |Ti(b)| ≥ |Ti(a, a + b)|.

We construct a injective mapping ψ : Ti(a, a+b) → Ti(b) as follows. If σ ∈ Ti(a, a + b) is a permutation of the form σ = (x1, ..., xk, y1, ..., yℓ, i, z1, ..., zr), where k is the first index for which ∑kj=1 w(xj) ≥ a, then we set ψ(σ) = (y1, . . . , yℓ, i, x1, . . . , xk, z1, . . . , zr). Note that since i and a are given, ψ is invertible and hence injective. We denote X = {x1, . . . , xk} and Y = {y1, . . . , yℓ}; it is possible that Y = ∅, but this does not affect our analysis. Since σ ∈ Ti(a, a + b), we have w(X ∪ Y ) < a + b. However, w(X) ≥ a, so w(Y ) < b. This means that ψ(σ) ∈ Ti(b). Thus, there exists an injective mapping from Ti(a, a + b) to Ti(b), and hence |Ti(b)| ≥ |Ti(a, a + b)|.

Theorem 4.2. For any w ∈ (Z+)n we have wi ∈ opt(φi).

Proof. We differentiate between the following two cases: q ≤wi: For any σ ∈ Πi(q), w(Pi(σ)) < q ≤ wi and w(Pi(σ)) + wi ≥ wi, hence σ ∈ Πi(wi). Therefore, for all q ≤ wi it holds that Πi(q) ⊆ Πi(wi), and hence φi(q) ≤ φi(wi).

q > wi: Note that Πi(q) = Ti(q) \ Ti(q -wi) and Πi(wi) = Ti(wi). By Lemma 4.1 we have |Ti(wi)| + |Ti(q - wi)| ≥ |Ti(q)|. Thus, we obtain

and hence φi(wi) ≥ φi(q).

Theorem 4.2 provides a simple recipe for the manipulator who favors player i: he should set the quota to wi (or to w(N)-wi +1). However, changing the quota may be costly, and therefore the manipulator may want to know whether the current quota is already optimal. As wi ∈ opt(φi), this is equivalent to asking whether φi(q) = φi(wi); we call this decision problem MAXSV. MAXSV can be viewed as a special case of the QUOTA problem considered in [Zuckerman et al., 2008], where we are given w, i, q, and q′ , and the goal is to check whether φi(q) > φi(q′ ). [Zuckerman et al., 2008] prove that QUOTA is computationally hard; however, this does not imply that MAXSV is hard, since in MAXSV one of the candidate quotas is fixed to be wi, which potentially could make MAXSV an easier problem.

Nevertheless, we can show that MAXSV is hard, too; the proof proceeds by a reduction from SUBSETSUM [Garey and Johnson, 1979], and is omitted due to space constraints.

Theorem 4.3. MAXSV is coNP-hard.

4.2 Minimizing the Shapley Value

So far we focused on maximizing an agent's Shapley value. However, the manipulator may wish to minimize the power of a player by changing the quota. We first establish that, just as in the case of maximization, the corresponding decision problem is hard. Specifically, we define the problem MINSV as follows: given a weighted voting game G = (w, q), and a player i ∈ N, is it the case that q ∈ pess(φi)? We have the following result (proof omitted).

Theorem 4.4. MINSV is coNP-hard.

For the rest of this section, we focus on finding a quota in pess(φi). This task appears to be more challenging than finding a maximizing quota. Indeed, the graphs in Section 3 suggest that a suitable value of the quota may be q = wi + 1. However, the experiments in Section 5 show that wi + 1 is not always in pess(φi), especially for relatively large players. For such players it is often a good solution to set q = 1; this ensures that these players are no more powerful than smaller players. Indeed, for the largest player, q = 1 is clearly the worst possible quota, since φn(q) ≥ 1n for any q. However, this approach only works for above-median players; we can prove that for below-median players q = wi + 1 is a strictly better choice for the manipulator than q = 1.

Proof. If player i is pivotal for a set S ⊆ N \ {i}, and the quota is wi + 1, then S ⊆ {1, . . . , i - 1}. Denote by Ak the collection of sets of size k for which player i is pivotal. For any 1 ≤ k ≤ i - 1, we have |Ak| ≤ (i-1 k ). Note also that the contribution of a set in Ak to the Shapley value of player i equals to

Therefore, the total contribution fromAk is at most 1n · (i-1 k ) (n-1 k ) . This means that

Theorems 4.4 and 4.3 show that deciding whether a given quota is in opt(φi) or pess(φi) is coNP-hard. However, there are certain values of i for which these problems become easy. Specifically, consider the problem of checking if q ∈ opt(φ1). By monotonicity, we have φ1(q) ≤ · · · ≤ φn(q); thus φ1(q) ≤ 1n and, moreover, φ1(q) = 1n if and only if φ1(q) = . . . = φn(q). Thus, q ∈ opt(φ1) if and only if φ1(q) = . . . = φn(q). Similarly, q ∈ pess(φn) if and only if φ1(q) = . . . = φn(q). It turns out that deciding whether all players have the same Shapley value (or, equivalently, whether φn(q) = φ1(q)) is easy.

Theorem 4.6. There exists a poly-time algorithm that checks whether φn(q) = φ1(q).

Algorithm 1: FIND-SET(w, q)

for k = 1 to n - 2 do A ← {2, . . . , k + 1}; B ← {2, . . . , n - 1} \ A; while B ̸= ∅ do if q - wn ≤ w(A) < q - w1 then return A; i ←min(A) ; j ←min(B) ; A ← A \ {i} ∪ {j} ; B ← B \ {j} ; return "no";

Proof. Observe that φn(q) > φ1(q) if and only if there is a set A ⊆ {2, . . . , n - 1} for which player n is pivotal but player 1 is not, i.e., q - wn ≤ w(A) < q - w1. Algorithm 1 iteratively tries to find such a set of size k, 1 ≤ k ≤ n-2, by starting with a set that contains the k smallest elements and repeatedly (i) removing the smallest element and (ii) adding the smallest yet unused element. This process stops if either a set with the desired weight is found or if there are no elements left to swap in; in the latter case the last set to be considered contains the k largest elements.

Each swap increases w(A) by at most wn-1 -w2 ≤ wn - w1. Therefore, if a set A with q - wn ≤ w(A) < q - w1 exists, our algorithm is guaranteed find it. Since we remove one element of B at each swap, there are at most n-2 swaps in each of the n - 2 iterations, which ensures polynomial running time.

Algorithm 1 can be simplified by observing that a set A with |A| = k and q - wn ≤ w(A) < q - w1 exists if and only if the first k weights in W = {w2, . . . , wn-1} are small enough and the last k weights in W are large enough.

Corollary 4.7. φn(q) > φ1(q) if and only there exist a k ∈ [1, n-2] with ∑k+1 i=2 wi < q-w1 and ∑n-1 i=n-k wi ≥ q-wn. Corollary 4.8. There exist poly-time algorithms for checking whether q ∈ opt(φ1) and whether q ∈ pess(φn).

5 Empirical Results

We have conjectured that two values of the quota that are likely to minimize the Shapley value of player i are the quotas 1 and wi + 1. In this section, we will verify this empirically.

We considered three different distributions of weights: uniform on [1, 40], normal with μ = 30, σ2 = 15 and Poisson distribution with mean 20. For each distribution, we conducted 100 tests. In each test, we generated 30 weights and checked whether the Shapley value of player i ∈ [1, 30] is minimized at q ∈ {1,wi + 1}. The results are graphed in Figure 4.

Our experiments show that for the uniform distribution, the likelihood of wi + 1 being the global minimum is relatively low. However, under the normal or Poisson distributions, the likelihood of this event increases dramatically. Similarly, for the uniform distribution, it is often the case that 1, wi+1 ̸∈ pess(φi), especially for small values of i, whereas in all 100 experiments for the Poisson distribution the minimum occurred at wi + 1 or 1, i.e., pess(φi) ⊆ {1, wi}. Furthermore, for all distributions, even if there exists a quota q such that φi(q) < φi(wi + 1), φi(1), the average difference between min(φi(wi + 1), φi(1)) and φi(q) is small.

We conclude that when the players' weights are tightly clustered (as it typically happens for normal and Poisson distribution) either q = wi + 1 or q = 1 is likely to minimize player i's power. When choosing between these two options, the rule of thumb is to set q = wi +1 for the bottom 70-80% of all voters, and q = 1 for all other voters.

Another interesting question that merits empirical investigation is whether the manipulator can incur significant changes of the players' Shapley values if the quota is required to be reasonably close to 50% of the total weight, since such constraints on the quota are very common in practice. Now, in Example 3.1 any choice of quota between-roughly-25% and 75% of the total weight results in the player's power being very close to his relative weight, i.e., w10/w(N), whereas in Example 3.2 this is not the case. Our next experiment aims to establish which of these scenarios is more frequent.

Given a vector of weights w and a player i, let r be the maximum radius such that |φi(q) - wi w(N) | < ε for all q ∈ [ w(N) 2 - r, w(N) 2 + r] ∩ N. In this notation, the quantity we are interested in is 2r w(N) .

Our experiment was conducted as follows: for each player i ∈ {1 . . . 30}, we have drawn 30 weights from the uniform distribution on the interval [1, 40]. We then computed the proportion 2r w(N) . The results were averaged over 50 trials. The same was done for weights drawn from the Poisson distribution with mean 20. The results are presented in Figure 5a (uniform) and Figure 5b (Poisson). In both figures, the X axis represents the rank of the player (between 1 and 30), while the Y axis represents the average value of 2r w(N) for ε = 0.0001, 0.00025, 0.001. We observe that, under both distributions, for most players their power is very close to their relative weight for a significant proportion of the quotas. However, for very large players this is less likely to be the case, as illustrated by Example 3.2. Interestingly, for different values of ε the graphs are shaped differently; in particular, for very small values of ε the graphs peak around player 20, with the position of the peak being different for the two distributions.

6 Conclusions and FutureWork

We explored the behavior of the Shapley value as a function of the quota in weighted voting games. We viewed this problem from the position of a manipulator who aims to maximize/minimize a given player's power. We have shown that,

(a) Uniform distribution on {1, . . . , 40}.

Figure 5: The average proportion 2r

(b) Poisson distribution with mean 20.

w(N) for ε = 0.0001, 0.00025, 0.001

despite a number of hardness results for related problems, maximizing a player's power is easy. While we do not have a polynomial-time algorithm for the minimization problem, our heuristic approach works extremely well, especially for large players. However, in a more realistic scenario where the quota is not allowed to stray too far from 50%, the manipulator cannot do much, especially for smaller players: for a large, centrally symmetric range of quotas the small players' power is fairly close to their (normalized) weight. In summary, it appears that it is the large players who are most vulnerable to quota manipulation: small changes of the quota may be sufficient to change their power significantly. However, to change the power of small players in a measurable way, one may need the ability to choose very high/low quota values.

Perhaps the most interesting open question inspired by this work is whether one can find a power-minimizing quota efficiently. A related question is whether there exists a polynomial-time algorithm for maximizing the total power of a set of players: indeed, φi(q) is minimal if and only if ∑j∈N\{i} φj(q) is maximal.

Acknowledgments This research was supported by the National Research Foundation (Singapore) under grant 200908, by NTU SUG, and by SINGA graduate fellowship.