Characterization of the Shapley-Shubik
and Banzhaf Power Indices on Simple Games
by
Cheng-Jih Chen
Introduction:
	The Shapley-Shubik and Banzhaf power indices are quantitative measures of the influence of a given player in a simple cooperative game.  These indices have been characterized by a collection of ‘reasonable’ axioms that pertain to the indices’ mathematical structure and to notions of how a coalition’s worth is ‘fairly’ distributed among its members.  We present a new characterization with axioms that are weaker than those used by Dubey in 1975.

Background:
	Modern game theory, which dates from the publication of John von Neumann and Oskar Morgenstern’s work, Theory of Games and Economic Behavior in 1944, is the branch of operations research concerned with the formal study of situations of social conflict or cooperation.  A game is a model of such social phenomena.  The theory is concerned with situations in which two or more players with conflicting goals and preferences must interact, and makes use of modern utility theory.   Situations governed purely by chance or of one player against nature are not described by the theory.  
	Games are either cooperative or noncooperative.  A game is cooperative when the players communicate freely with each other, and any agreement they make among themselves is binding.  A noncooperative game places restrictions on these actions.  We are concerned with the former case.
	Binding agreements between players are modelled by coalition formation.  A coalition is then a subset S of the set of players N.  The coalition N is called the grand coalition.  The game v itself is a utility function on all coalitions (i.e., a numerical value, the worth, is assigned to all possible combinations of n players).  The empty coalition always has zero worth (i.e., v(∆) = 0).  The players that ultimately reach an agreement split the worth assigned to their coalition.  The method by which these players divide the worth is called an allocation procedure, and the central problem is to devise a ‘fair’ procedure.
	Before examining two solutions to this problem, we will first introduce simple cooperative games.  Our research is concerned with the meaning of these two solutions, the Shapley-Shubik and the Banzhaf power indices, on such games.
	A simple cooperative game assigns to each coalition either 1 or 0 for that coalition’s worth, with the grand coalition always receiving 1 (i.e., v(S) = 1 or 0, and v(N) = 1).  We say a coalition wins  with worth 1 and loses otherwise.  These games are commonly used to model decision making bodies such as a legislature or a committee.  For example, a coalition of the United Nations Security Council is winning if it contains all five permanent members and three of the rotating members, and losing otherwise.
	We wish to consider certain subclasses of simple games.  The first is the class of monotonic  simple games.  A game belongs to this class if every superset of a winning coalition is also winning (i.e., v(S) ≥ v(S’) whenever S   S’).  In real-world decision making bodies, adding members to a coalition in general does not make that coalition lose.  The next class is that of superadditive  simple games.  For any two disjoint coalitions, their union has greater worth than the sum of the worths of the coalitions taken separately (i.e., v(S » T) ≥ v(S) + v(T) for S « T = ∆).  This requires that two disjoint coalitions cannot both be winning.  Note that superadditive games are are contained in the subclass of monotonic games.
	We are interested in a quantitative determination of a given player’s power, which may then be used as the basis of an allocation procedure.  Such a determination is called a power index, and is a function y that assigns an n-vector to each game v, where n is the cardinality of N (i.e., y(v) = (yi(v))iŒN).  Power is a measure of how much influence a has in the game.  Intuitively, it is related to the number of losing coalitions that become winning when that player joins.  We say a player i is critical  to a coalition S if v(S) = 1 and v(S - i) = 0.  A coalition S to which a player is critical is called a pivot  of that player.  Denote by Pi(v) the set of pivots of player i in game v.  We also define an unanimity game  uT as the simple game in which a coalition S wins if and only if S is a superset of coalition T.  Note that all players contained in T are critical to all winning coalitions in the game uT.

The Shapley-Shubik and Banzhaf Power Indices:
	The first power index was proposed by Shapley/Shubik in 1954, and defines power as the average marginal contribution of a player i taken over all orderings, where an ordering is the sequence in which players join to form the grand coalition, assuming that they join one at a time.  In the case of simple games, a marginal contribution of 1 is assigned to a player when that player is critical to the coalition that includes himself and the players that have joined before him. Consider the 3-player game in which v(123) = 1, v(12) = 1, v(23) = 1, and v(S) = 0 for all other S Õ N (by an abuse of notation, we will write v({i,j,k}) as v(ijk)).  The table below shows the marginal contribution of a player i to a given ordering.  The column on the far right is the sum of the marginal contributions.

i	123	132	213	231	312	321	S	
1	0	0	1	0	0	0	1	
2	1	1	0	0	1	1	4	
3	0	0	0	1	0	0	1	

	For example, player 2 contributes a marginal worth of 1 to the ordering 132, as the coalition {1,3} is losing before player 2 joins.
	There are six possible orderings, so j(v) = (1/6, 4/6, 1/6), where j is the Shapley-Shubik power index.  We may also interpret this result as the probability that a given player is critical given that all permutations are equally likely.
	The formula for j is then:
		ji(v) = ISU(,,F((|S| - 1)!(|N| - |S|)!,|N|!))
taken over all coalitions S to which i is critical.
	The Banzhaf power index b is a similar measure of the probability that a player is critical, but assumes instead that all coalitions are equally likely to form.  The order in which the players join is not important.  A player’s power is interpreted as the fraction of the total number of pivots that are his.  The Banzhaf power index is then given by
		bi(v) = F(|Pi(v)|, isu(iŒN,, |Pi(v)|).).
	It is sometimes more convenient to consider the absolute Banzhaf index o(b,`), which is the probability that the player i is critical to the coalition that actually forms.  Power is then the fraction of the total number of coalitions that are player i’s pivots.  Thus,
		o(b,`)i(v) = F(|Pi(v)|, 2n-1).
	The regular Banzhaf index is a normalization of the absolute index so that isu(iŒN,, bi(v)) = 1.
	For the above 3-player game, b(v) = (1/5, 3/5, 1/5) and o(b,`)(v) = (1/4, 3/4, 1/4).

Characterizations:
	A characterization is a set of ‘reasonable’ axioms that uniquely determine a power index, and is useful in examining the index’s structure and in comparing it with other indices.  Dubey in 1975 and 1979 proved that the following axioms characterize both indices.

Dummy (Du):  y(v) fulfills the dummy axiom if " i Œ N, if
v(S » i) - v(S) = 0 for all S Õ N - {i}, then yi(v) = 0.
	If a player is not critical for any coalition, and so contributes nothing to the game, then that player should receive nothing when the worth is allocated.

	Let p: N Æ N be a permutation of N.  We define a new game pv(S) as v(p(S)) for all S Õ N.
Symmetry (Sym):  A value y(v) is symmetric if " i Œ N and for all permutations p of N, yp(i)(v) = yi(pv).
	Symmetry requires that the labels of the players do not matter.  What a player receives is determined by the role he has in the game, and only that.

Dubey Transfer Axiom (DTr):  A power index y(v) satisfies the Dubey transfer axiom if y(v Ÿ w) + y(v ⁄ w) = y(v) + y(w), where v Ÿ w and v ⁄ w denote the games given by

	ACO2HS5((v Ÿ w)(S) = ,BLC{(ACO2HS5VS5(1,if v(S) = 1 and w(S) = 1,0,otherwise)))

	ACO2HS5((v ⁄ w)(S) = ,BLC{(ACO2HS5VS5(1,if v(S) = 1 or w(S) = 1,0,otherwise)))

	This transfer axiom pertains to the structure of the index.  It describes how the index can be determined with respect to other games that are related to the game in question.  In particular, it states that if the pivots for a player in two games are ‘shifted around’ in a specified way, the total powe of that player is not changed.
	DTr replaces an additivity axiom proposed by Shapley in 1953 to characterize the Shapley value, the extension of the Shapley-Shubik index to the space of general games.  In general games, additivity can be used to describe the value in terms of more basic games, much as a vector space is described by its basis.  Additivity, however, is not a restriction on simple games.

Efficiency (Eff):  A value y(v) is efficient if Isu(iŒN,, yi(v) = v(N)).
	This is a requirement that the worth of the grand coalition is completely split among the players.  There is then no ‘waste,’ nor can players obtain more worth than is available.  For simple games, each player receives a fraction of the fixed worth v(N) = 1. 

Modified Efficiency (Eff’):  y(v) satisfies Eff’ if 
Isu(iŒN,, yi(v)) = isu(iŒN,, |Pi(v)|).
	The total number of pivots is divided among the players.  The axiom characterizes the absolute Banzhaf index when it replaces Eff.

Theorem (Dubey 1975, 1979): The Shapley-Shubik power index (resp. Banzhaf) is the unique index satisfying Du, Sym, DTr and Eff (resp. Eff’).
	The axiomatic difference between the Shapley-Shubik and Banzhaf indices is thus very slight.  The former requires a constant worth to be split among the players.  The latter depends on a prior assessment of the game.

	In fact, a weaker axiom than Sym is sufficient for these characterizations:
Equal Treatment (ET):  If v(S » i) = v(S » j) for all S Õ N - {i,j}, then
yi(v) = yj(v).
	If two player contribute equally in a given game, then they are treated equally, having the same power.  This axiom is weaker than Symmetry as it cannot compare players in different games.

Transfer Axioms:
	We now propose new axioms that characterize the power indices.  The first set is the transfer axioms, which includes Dubey’s transfer axiom in conjunction with the Dummy axiom.  These pertain to the structure of the index.

Unanimity game Transfer (UTr): For all T Õ N such that T ≠ ∆,
yi(v) = yi(v Ÿ uT) + yi(v ⁄ uT), " i œ T.
	UTr is formulated with respect to a unanimity game applied in conjunction with DTr & Du.
	This axiom is analogous to the Coalitional Strategic Equivalence axiom proposed by Chun in his characterization of the Shapley value.  It specifies the effect of an unanimity game uT on a player’s power if that player does not belong to coalition T.
	By interpreting v Ÿ uT and v ⁄ uT as games in which, respectively, coalition T has acquired the power to veto motions and the power to pass motions, we can see that UTr states that the sum of the power lost by a player i œ T is equal to his total power in the original game v.

Split Pivot Transfer (STr):  yi(w) = yi(v) + yi(u) when the games u and v split player i's pivots in the game w, i.e. Pi(w) = Pi(v) » Pi(u) and Pi(v) « Pi(u) = ∆.
	STr requires that if the pivots of player i are completely divided between two other games, then the power of i in the original game is equal to the sum of the power in the other games.  The power of player i does not change if there is no change in set of pivots of player i.  The power index of one game as the sum of the indices for two other games is in a sense similar to Shapley's original Additivity axiom.

TransferSum Axiom:   $ f : 2N ¥ {1,2, . . . ,n} Æ ¬, where 2N is the space of subsets of N, such that  yi(v) = isu(SŒPi(v),,   f(S,i)).
	We now state explicitly that the power of a player depends only on the set of pivots in the game.  This axiom has antecedents in the work of Weber (1978), who proposed a summation over a probability distribution, and Bolger, who proposed characterizations in a summation form of various common power indices, including the two in question.

	Our first result shows that the following transfer axioms  are equivalent on monotonic simple games.
	1) TransferSum Axiom
	2) Split Pivot Transfer Axiom
	3) Dubey's Transfer Axiom and Dummy
	4) Unanimity Transfer Axiom.

	This, however, is not true when an index satisfying these axioms is restricted to simple superadditive games.  Axioms 1, 2, and 3 are equivalent, but UTr is necessarily weaker than these.  We show this by examining all such 3-player games, which are listed below.

S	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	
123	1*	1	1*	1*	1	1	1*	1	1	1	1*	
  23	0	1	0	0	1	1	0	1	1	1	0	
1  3	0	0	1*	0	1*	0	1*	1*	1	0	1*	
12	0	0	0	1*	0	1*	1*	1*	0	1	1*	
    3	0	0	0	0	0	0	0	0	1	0	0	
  2	0	0	0	0	0	0	0	0	0	1	0	
1	0	0	0	0	0	0	0	0	0	0	1*	
												
y1(vi)	a	0	a+b	a+c	b	c	?	?	0	0	a+b +c+d	

a = f({1,2,3},1), b = f({1,3},1), c = f({1,2},1), d = f({1},1)
	1 and 0 in a matrix entry designate winning and losing coalitions, respectively.  Coalitions with asterisks next to them are pivots for player 1 in that particular game.  The values a, b, c, and d represent the function from the TransferSum axiom on a given pivot of player 1.  The bottom row contains the values that can be obtained with UTr only.
	Clearly, by assuming the TransferSum axiom we can obtain values for games v7 and v8.  In general, using UTr we can determine y(vk) for a given k by considering previously determined values for vk ⁄ uT and vk Ÿ uT.  However, UTr alone cannot determine a value for v8.  To do so would require us to construct a non-superadditive game.  We also cannot obtain a value for v7, as the only superadditive game we are allowed to construct is v8.
	Thus, on superadditive games, STr, Du and DTr, and the TransferSum axiom are equivalent notions.  All of these are stronger notions than UTr, since UTr is a necessary condition of Du and DT.

Fairness Axioms:
	Fairness conditions are formalizations of a notion of ‘fair play.’  Players that contribute equally should receive equal value.  Symmetry and Equal Treatment are two such axioms.  We introduce two others:
Equal Treatment on Unanimity Games (ETUG):  An index fulfills ETUG if yi(vT) = yj(vS) for all i Œ T, j Œ S whenever |T| = |S| for the coalitions T and S.
	ETUG requires that the members of the minimal winning coalition (MWC) of an unanimity game are treated equally, and that any two unanimity games with MWCs of the same cardinality are equivalent (i.e., the players have simply been renamed).

FairSum Axiom: $ f : {1,2, . . . ,n} Æ ¬  '  yi(v) = isu(SŒPi(v),,  f(|S|)).
	FairSum is the TransferSum axiom when the function f does not depend upon labels (i.e., does not differentiate between any particular player i or coalition S).  The function depends only on the cardinality of S.

	Our next result shows that, with an index y(v) that fulfills the TransferSum axiom, the following fairness conditions  are equivalent.
	1) FairSum
	2) Symmetry
	3) Equal Treatment on Unanimity Games
	Equal treatment is a necessary condition of Symmetry, but at present we have no results that further clarify this relationship.

New Characterization:
	Clearly, the Transfer axioms and the Fairness conditions characterize both Shapley-Shubik and Banzhaf indices, as both sets of axioms contain those previously shown to do so.  We can, however, characterize both indices on simple superadditive games with strictly weaker axioms.  Our last result shows that UTr, ET and Eff (resp. Eff’) uniquely determine the Shapley-Shubik (resp. Banzhaf) index in this class of games.  The proof shows inductively that UTr is sufficient to obtain values for players that are not critical to every winning coalition.  For players that are critical to all winning coalitions, we may apply ET, as such players contribute equally, and Eff, as they divide equally the worth not accounted for by the other players.

Bibliography:

Bolger, E.M.  "A Class of Power Indices for Voting Games."  Int. Journal of Game Theory 9 (1980): 217-232.

Chun, Y.  "A New Axiomatization of the Shapley Value."  Games and Economic Behavior 1 (1989): 119-130.

Dubey, P.  "On the Uniqueness of the Shapley Value."  Int. Journal of Game Theory 4 (1975): 131-139.

Dubey, P. and Shapley, L.S.  "Mathematical Properties of the Banzhaf Power Index."  Mathematics of Operations Research 4 (1979): 99-131.

Weber, R.J.  "Probabilistic Values for Games."  The Shapley Value: Essays in Honor of Lloyd S. Shapley.  Ed. by Alvin Roth.  New York: Cambridge University Press, 1988.