AXIOMATIC AND PROBABILISTIC CHARACTERIZATIONS OF MINIMAL WINNING COALITION BASED POWER INDICES John R. Birge Technical Report 82-10 Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109

AXIOMATIC AND PROBABILISTIC CHARACTERIZATIONS OF MINIMAL WINNING COALITION BASED POWER INDICES John R. Birge Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Abstract Power in voting situations has been described as the probability of a player to cast the deciding vote. The Banzhaf-Coleman and ShapleyShubik indices have been shown to have this characterization. In this paper, a general probabilistic characterization is shown to lead to a minimal winning coalition based power index similar to the DeeganPackel index. An axiomatization is also given for a family of indices including this index.

1. Introduction. An individual's power in a voting game can be characterized by his or her probability of being decisive in the outcome. Straffin [1976] has shown that the Shapley-Shubik (Shapley [1953]) and Banzhaf-Coleman (Baazhaf [1965], Coleman [1971]) indices fit this characterization according to different assumptions about the behavior of players in joining coalitions,. The Deegan-Packel index (Deegan and Packel [1978]) differs from these indices in the assumption that only minimal winning coalitions form. In this paper, we present a general probabilistic characterization of power indices that may be viewed as a member of Bolger's [1980] class of power indices. We show that this class includes the Shapley-Shubik and Banzhof indices and a variant of the Deegan-Packel index that does not include the "equal division of spoils" present in the Deegan-Packel characterization. We also present a set of axioms which characterizes the family of indices including this minimal winning coalition based power index. We first define some terms that will be used throughout the discussion. Definition: A game (N, v) is a simple game if v(S) = 0 or 1 for all S CN = {1, 2,..., n}. Definition: S is a winning coalition in a simple game (N, v) if v(S) = 1. The collection of winning coalitions is U. v Definition: S is a minimal winning coalition in a simple game (N, v) if v(S) = 1 and v(S - {i})= 0 for all i e S. The collection of minimal winning coalitions is M. v

-2 - Definition: A player i is a dummy player in a simple game (N, v) if S V {i} E W if and only if S e W for all S C N. Definition: A power index for a simple game (N, v) is a function Pv that assigns a real number, v(i) > 0, to each player i e N. Definition: A player i is critical in a simple game (N, v) to a set S if v(S ) {i}) - v(S) = 1. Definition: A permutation, Pv, of the game (N, v) defines a game such that, for a permutation P of the players i ~ N, P (P(T)) = v(T) for all Tc N. The number of sets for which i is critical is written 6 (i) = Z [v(S {i}) - v(S)]. (1) SON Sji The Banzhaf index B is a normalized measure of the critical sets for v a player i, where 6 (i) v (2) v( = Z 6 (j) v jaN A non-normalized version, which we call Banzhaf-Coleman index yvy, measures the fraction of all subsets not containing i for which i is critical, where 5(i) Yv(i) - 2nl3) The Shapley-Shubik index k includes all permutations of subsets S CN for which i may be critical. In this case, Vi = s! (ns-l)! [v(S U{i}) - v(S)] (4) Sei where s = ISI.

-3 - The Deegan-Packel index, p, is defined for i as v 1 1 Pv Mi= 1-i- E 1 (5) V iM7 SCM (i) s where M (i) = {S c M: i C S}..V V 2. Probabilistic Characterizations. Straffin [1976] characterized power in terms of the probability that a player will be critical in a voting game according to the"homogeneity" of the player set N. The player set is homogeneous if each player has the same probability p,(r) of a joining a coalition for a given proposal r or the rth play of the game. The players are independent if every player i has an independent probability Pi(r) of joining a coalition for any proposal. The set of proposals including r is R. We can generalize this characterization by partitioning N into Z homogeneous groups where N = N1L N2... UJ Ng and N. N. + ~ for all JL 2 Xk 1 J i $ j. We let I N. = n. and assume that each player j e N. has the same 1 1 probability Pi(r) of joining a coalition S in (N, v). We also assume that pi(r) is independent of Pk(r) for all i 4 k. For a given proposal r, the probability T (i) that i is critical is V 9 k n.-kj nl-kl-l T (i) ) ).(r) T P (r) p(r) }, (6) v sC.C (i) j=l j=2 i 1 where C (i) = {S CN | v(S U {i} - v(S) = 1} and we assume that S C C (i) V V includes k. players from N. for all j and that i C N1 without loss of g i generality.

-4 - r The expected value of Tr (i) over all possible proposals r is v Wv (i) = Er [rr(i)], (7) r1 r1 g kj n -kj nl-kl-1 S~C (i) ''' f(P'i P i S= ZC I *(i i PP) P o * TlbP. P1. dp...dp s, ScC. (i) C M 1 2 ~ j=lj j=2] ~ where f(p1, P2,..., P.) is the probability density function imputed on P1~ p2,.'*., pi from R. P1'> P ' from R. Various distributions can be used in evaluating (7) based perhaps on prior data for outcomes of the game. A simple assumption is that each probability is uniformly distributed, i.e., f(P1, P2,""*, Pn) = 1. In this case, k k!. k!(nl-k -l)!(n2-k)!...(n-k)! -u..... 2 2.... (i) = Z "....... (8) v SCC(i) nl! (n2 + 1)!... (n + 1)! This value can be used to obtain both the Shapley-Shubik and BanzhafColeman indices. Proposition 1. If N = N, then -U Tr(i) = )(i) for a simple game (N, v). Proof: This follows immediately from (8) and (4). Proposition 2. If N.i = 1 for all i = 1, 2,...,Z, then -U Wv(i) = Yv(i). Proof: This follows from (8) and (3).

-5 - If we assume that only minimal winning coalitions are possible, then the density function f(p1, P2,..'., p) in (7) also depends on the coalition S. In this case f(pl, P2,..., pd) = 0, if S is not a minimal winning coalition. If we additionally assume that the minimal winning coalitions are equally likely, we obtain -m j A. n.-k. n -k -1 7Vi) sc i ~ jt f(P, P2,""P,. ) rlp * i T (1-p) pi dp l.dP1p V SC t (i) j=l j=2 (9) If we further assume uniformity in forming these coalitions, we obtain mu k! k!...k!(nl-k -l1)(n2 -k2)!...(n-k)! T (i) = l 2 9 2 (10) v ScM(i)!(n2 + 1)!..(n + )!n (10) We can again obtain indices similar to the Shapley-Shubik of BanzhafColeman indices by assuming N1 = N or |N.i = 1 for all i. In the latter case, we obtain m,u I l(i) l nV(i) - v (i)= 2n- * (11) The index fn is similar to the Deegan-Packel index in its counting over minimal winning coalitions, but it does not depend on the size of these coalitions. This aspect may be interpreted as saying that a player receives equal amounts of power from groups for which he is critical regardless of the size of that group. r is also not normalized in terms of dividing one unit of power among all players as the Deegan-Packel index does. This may be an advantage in characterizing power among different games. A normalized version would!M (i)l n(i)v... (12) v Sz [ N (i) iN v

-6 - We note that n is actually a member of the family of indices in V Packel and Deegan [1980] and, therefore, fits their set of axioms. This family consists of indices Pv such that f P (S) f( 1 v () (13) vZ P(S) SEM (i) -v S EI. ' v where f i fo if S M PF(S) = f. (14) a f (S) if S ~ M v and ci = Z f(S). (15) SzN f f If we assume f(S) = s, v (i) and the axioms for p with this definition of f(S) lead to v (i). In the next section, we develop a set of axioms for TIV V 3. Axiomatization For simple games, (N, v) and (N, w), we define the compositions, vN/w and v /, w by v 1 if v(S) = 1 or w(S) = 1, v X/w(S) = 0, otherwise, an d ( 1 if v(S) = 1 and w(S) - 1, v Aw(S) = 0, otherwise.

We also introduce the elementary game, (N, Ei) as in Owen [1978], where E.(S) = 1 0, otherwise, and the game (N, v ) such that s v(T) = 0, otherwise. The index n (i) will be shown to be a member of the family of indices satisfying a set of axioms based on the compositions v \ w and v /w. f This family n is defined in the following theorem. Theorem. There exists a one parameter family of power indices v that satisfy the following axioms: a) If i is a dummy in (N, v), then (v(i) = 0. V b) If is a permutation of (N, v), then 4 (P(i)) = M (i). v c) If SL T and T S for all S C Mv and T c {w for simple games (N, v) and (N, w), then vV\w(i)= (i = (i) (16) d) If R C M if and only if R = S UT for S e M and f v/\w v T E A{ for simple games (N, v) and (N, w), then w yAw(i) = v(i) wvtI1 + c (i) IJ (17) - v (i)- Vw(i) q, where q is a nonnegative parameter.

-8 - Proof. We will find a set of power indices that are functionsof the parameter q in (17). The proof follows as in Deegan and Packel [1978] and Owen [1978]. We can write any game as v = \ v. and v can be written as v A/ s S itS sb M ~ ~ v by (a), we have E.. In the game E., 1 1 a E > (j) = for some Now a. using (b) and if j = i, if j 4 i, (d), we find if i e S, otherwise, a v (i) = s, and from (c), v (i) = Z a. seAM (i) v (18) Hence, if ~v satisfies (a) - (d), then it has the form in (18). Next, for any game z = v \w satisfying the conditions in (d), we have: MZ(i) = (Mv(i)U Mw) (Mu(i) V and IM(i)l = l v(i)l.~ IM + IM ~ M (i)l - IM(i)l II (i). So, from (d),

-9 - <z(i) = a(I M(i) ~ M I + I Mv ~ IM (i)| - IMv(i) I ~ IM{(i)|) = 4v(i) IMw1 + w (i)v I - 4v(i) 4w(i)q = a(IM (i)j IM I + IMvl IM (i)l) - a2q (1 4(i) I w(i)) 2 1 so we must have a = a q if IM (i)i 4 0 and ji A(i)l + 0. Therefore, a= IM (i)l q or O. The nonzero one-parameter family is 4 (i) = q. This index clearly satisfies (a) and (b) and the above shows that it satisfies (d). To show that (c) is satisfied we note that if the conditions for (c) are satisfied then IM A (i)| = IM (i)| + I| (i)l. nv is the unique nonzero index satisfying the axioms when q = 2nl These axioms are similar to those given by S4apley, [1953], Dubey [1975], Owen [1978], and Deegan and Packel [1978] for other power indices in their giving dummy players zero value, being symmetric, and describing relationships in composition games. We can see how nv may differ from the other indices in the following weighted voting game, [q; wl, w2, w3, w4] = [7, 5, 3, 2, 1] where v(S) = 1 if Z w. > q. We also look at its complementary game (N, v) where v(S) = v(N-S). icS For these games, we obtain the values in Table 1. We note that the Shapley-Shubik, Banzhaf and Banzhaf-Coleman indices have the same value in complementary games but that pv, rv and nv may differ. In this example, P = p- but nv + nv' v v v v

-10 - 4. Summary A general probabilistic characterization of power indices was given which led to a variant of the Deegan-Packel index. In this characterization, power was defined as the expected probability of making a critical decision when only minimal winning coalitions are allowed to form and a uniform distribution is assumed for the probability of joining a coalition in a given play of the game. This index was also shown to be characterized by a set of axioms similar to the axioms for other power indices. Table 1. Comparative Index Values. Y P P~ p- fn- lT T1 -Player v y v ~v v v v v nv v 1 1 1 1 1 2/3 3/5 3/4 1/2 1/2 1 4 8 2 3 2 1/6 1/5 1/4 1 /4 1/4 1 3 1/6 1/5 1/4 1/4 1/4 1 1 3 3 1/6 1/5 1/4 1/4 1/4 8 8 4 3 4 0 0 0 0 0 0 0 0 0

-11 - References Banzhaf, J. R.: Weighted Voting Doesn't Work: A Mathematical Analysis. Rutgers Law Review 19. 1965, 317-343. Bolger, E. M.: A Class of Power Indices for Voting Games. International Journal of Game Theory 9. 1980, 217-232. Coleman, J. S.: Control of Collectivities and the Power of a Coalition to Act. Social Choice. Ed. by Lieberman. New York, 1971. Deegan, J. and E. Packel: A New Index of Power for Simple n-Person Games. International Journal of Game Theory 7. 1978, 113-123. Dubey, P.: Some Results on Finite and Infinite Games. Ph.D. Thesis, Center for Applied Mathematics, Cornell University, Ithaca, New York, 1975. Owen, G.: Characterization of the Banzhof-Coleman Index. SIAM Journal Applied Math. 35. 1978, 315-327. Packel, E. W. and J. Deegan: An Axiomated Family of Power Indices for Simple n-Person Games. Public Choice 35. 1980, 229-239. Shapley, L. S. A Value for n-Person Games, Annals of Mathematics Study 28. Ed. by H. W. Kuhn and A. W. Tucker, Princeton, New Jersey, 1953, 307-317. Straffin, P.: Power Indices in Politics, MAA Modules in Applied Mathematics, Upson Hall, Cornell University, Ithaca, New York, 1976.

UNIVERSITY OF MICHIGAN 3 9015 03994 839611111 11 I 3 9015 03994 8396