PaperBC.dvi CUBO A Mathematical Journal Vol.12, No¯ 01, (1–6). March 2010 Characterization of the Banzhaf Value Using a Consistency Axiom Joss Erick Sánchez Pérez Facultad de Economı́a, UASLP, Av. Pintores s/n, Col. B. del Estado 78213, San Luis Potośı, México email : joss.sanchez@uaslp.mx ABSTRACT One of the important properties characterizing cooperative game solutions is consistency. This notion establishes connections between the solution vectors of a cooperative game and those of its reduced game. The last one is obtained from the initial game by removing one or more players and by giving them payoffs according to a specific principle. Consistency of a solution means that the restriction of a solution payoff vector of the initial game to any coalition belongs to the solution set of the corresponding reduced game. In this paper, we show that the Banzhaf value is consistent with respect to a suitable reduced game. We also show that consistency together with standardness for two-person games characterize the Banzhaf value. RESUMEN Una de las propiedades importantes caracterizando soluciones de juegos cooperativos es con- sistencia. Esta noción establece conexiones entre los vectores solución de un juego cooperativo y aquellos de su juego reducido. Este último es obtenido a partir del juego inicial al remover uno o más jugadores y asignándoles pagos de acuerdo a un principio espećıfico. Consisten- cia de una solución significa que la restricción de una solución del juego inicial a cualquier coalición, pertenece al conjunto de soluciones del correspondiente juego reducido. En este art́ıculo, mostramos que consistencia junto con estandarización para juegos de dos personas caracterizan el valor de Banzhaf. 2 Joss Erick Sánchez Pérez CUBO 12, 1 (2010) Key words and phrases: Games in characteristic function form, Banzhaf value, consistency. Math. Subj. Class.: 91A12. 1 Introduction The mathematical approach to a proposed solution is to examine a number of its (elementary) properties and, if possible, to provide a minimal number of properties which fully characterize the solution. In their well known paper, Hart and Mas-Colell (1989) characterized the Shapley value for the class of TU cooperative games by means of the following axioms1: i) Consistency. ii) Standardness for two-person games. A cooperative game is always described by a finite player set as well as a real-valued ”char- acteristic function” on the collection of subsets of the player set. A so-called reduced game is deducible from a given cooperative game by removing one or more players on the understanding that the removed players will be paid according to a specific principle (e.g., a proposed payoff vec- tor). The remaining players form the player set of the reduced game: the characteristic function of which is composed of the original characteristic function, the proposed payoff vector, and / or the solution in question. The consistency property for the solution states that if all the players are supposed to be paid according to a payoff vector in the solution set of the original game, then the players of the reduced game can achieve the correspondig payoff vector in the solution set of the reduced game. In other words, there is no inconsistency in what the players of the reduced game can achieve, in either the original game or the reduced game. This paper presents, using a standard notion of consistency, that the Banzhaf value is the unique consistent extension which ”divides the surplus equally” in two-person games. 2 Preliminaries By an n-person game in characteristic function form (or a TU cooperative game), in what follows just a game, we mean a pair (N,v), where N = {1, ...,n} is a finite set of players and v is a function v : 2N → R with the property that v(φ) = 0 (2N denotes the set of subsets of N). We usually refer to subsets S of N as coalitions and to the number v(S) as the worth of S. A game (N,v) is superadditive if v(S∪T ) ≥ v(S)+v(T ) for all S,T ⊂ N, and it is subadditive if the inequality holds in the other direction. There are several interpretations for (N,v), it depends on what people want to model. For instance, if the game is superadditive, v(S) means the maximal amount the players 1The precise definitions will be provided in Section 3. CUBO 12, 1 (2010) Characterization of the Banzhaf Value ... 3 in S can get if they decide to play together. While the game is subadditive, v(S) usually means the joint cost that players in S have to pay to get a service if they hired the service together. Additionally, we will denote the cardinality of a set by its corresponding lower-case letter, for instance n = |N|, s = |S|, t = |T |, and so on. We denote by GN the set of all games with a fixed set of players N, i.e., GN = {v : 2N → R | v(φ) = 0}. A solution ϕ : GN → Rn in GN is a rule to divide the common gain or cost among the players in N. Let ΓN be the set of solutions in GN. Given v,w ∈ GN and λ ∈ R, we define the sum and the product v + w and λv in GN in the usual form, i.e., (v + w)(S) = v(S) + w(S) and (λv)(S) = λv(S) respectively. In a similar manner, for ϕ,ψ ∈ ΓN and λ ∈ R, we define the sum and the product ϕ + ψ and λϕ in GN by (ϕ + ψ)(v + w) = ϕ(v) + ψ(w) and (λϕ)(v) = λϕ(v) It is easy to verify that GN and ΓN are vector spaces with these operations. Next, we define some axioms which are common in game theory. Axiom 1 (Linearity). The solution ϕ is linear if ϕ(v + w) = ϕ(v) + ϕ(w) and ϕ(cv) = cϕ(v), for all v,w ∈ GN and c ∈ R. Let us consider the group Sn = {θ : N → N | θ is bijective}, the group of permutations of the set of players. For every θ ∈ Sn and v ∈ G N we define another game (N,θ · v) as follows θ · v(S) = v(θ−1S) Axiom 2 (Symmetry). The solution ϕ is said to be symmetric if and only if ϕ(θ ·v) = θ ·ϕ(v) for every θ ∈ Sn and v ∈ G N . The player i is said to be a dummy player in the game (N,v) if v(S ∪ {i}) = v(S) for every S ⊆ N. The dummy axiom requests that every dummy player in (N,v) gets a zero payoff. Axiom 3 (Dummy). If the player i is a dummy player in (N,v) then ϕi(v) = 0. For every coalition T ⊆ N we obtain a new game vT where the set of players T is considered as one player; we denote this player by T́ . The space of players for vT is N\T ∪ {T́} and is defined by: vT (S) = v(S) and vT (S ∪ {T́}) = v(S ∪ T ) where S ⊆ N\T . The reduction axiom says that unification of any two players has to be profitable (or at least never harmful). 4 Joss Erick Sánchez Pérez CUBO 12, 1 (2010) Axiom 4 (Reduction). The solution ϕ satisfies the reduction axiom if and only if ϕi(v) + ϕj(v) ≤ ϕT́ (vT ) for every coalition T = {i,j} of two players. Theorem 5 (Lehrer, 1988). There exists a unique solution ϕ that satisfies linearity, symmetry, dummy and reduction axioms. Furthermore it is given by ϕi(v) = 1 2n−1 ∑ S⊆N\{i} [v(S ∪ {i}) − v(S)] 3 Consistency and the Main Result This section is devoted to a characterization of the Banzhaf value by means of an internal consis- tency property. Intuitively speaking, let ϕ be a function that associates a payoff to every player in every game and suppose that one player leaves a game with some payoff. Reduced games describe what games are played between the remaining players, i.e. what is earned by coalitions of the remaining players after one player has left the game. Then ϕ is said to be consistent if, when it is applied to any reduced game, it yields the same payoffs as in the original game. Definition 6. A value ϕ : GN → Rn is consistent with respect to the reduced game (N\{i},v ϕ N\{i} ) if, for N\{i} ⊂ N and all v ∈ GN, one has ϕj(N\{i},v ϕ N\{i} ) = ϕj(N,v) for all j ∈ N\{i} The various consistency requirements differ in the precise definition of the reduced game (i.e., exactly how the players outside are being paid off). It is well known that different solutions are consistent with respect to different reduced games. Next, we will see that the Banzhaf value is consistent according to the following reduced game concept: Definition 7. Given a solution ϕ : GN → Rn in GN, a game (N,v) (with n ≥ 3). The reduced game (N\{k},v ϕ N\{k} ) is defined by v ϕ N\{k} (S) =        1 2 [v(N) + v(N\{k}) − v({k})] if S = N\{k} 1 2 [v(S) − v(N\S)] if φ 6= S ⊂ N\{k} 0 if S = φ (1) The first result is as follows: Proposition 8. The Banzhaf value is a consistent solution function. Proof. We must apply this value to the reduced game (N\{k},v ϕ N\{k} ). We note that player j in (N\{k},v ϕ N\{k} ) gets: ϕj(N\{k},v ϕ N\{k} ) = 1 2n−2 ∑ S⊆N\{j,k} [ v ϕ N\{k} (S ∪ {j}) − v ϕ N\{k} (S) ] CUBO 12, 1 (2010) Characterization of the Banzhaf Value ... 5 Then, using the reduced game concept (1) in the last expression, we obtain: 2n−2 · ϕj(N\{k},v ϕ N\{k} ) = ∑ S⊆N\{j,k} [ v ϕ N\{k} (S ∪ {j}) − v ϕ N\{k} (S) ] = ∑ φ 6=S⊂N\{j,k} [v(S ∪ {j}) − v(N\(S ∪ {j})) − v(S) + v(N\S)] +v({j}) − v(N\{j}) + v(N) + v(N\{k}) − v(N\{j,k}) + v({j,k}) = 1 2 ∑ S⊆N\{j,k} [v(S ∪ {j}) − v(S) + v(N\S) − v(N\(S ∪ {j}))] We observe that in the sum, the worth v(N\S) corresponds to the worths of coalitions con- taining {j,k}; while the worth v(N\S ∪ {j}) corresponds to the worths of coalitions containing {k} but not {j}. Hence, we can apply the change: ϕj(N\{k},v ϕ N\{k} ) = 1 2n−1    ∑ S⊆N\{j,k} [v(S ∪ {j}) − v(S)] + ∑ S⊆N\{j},S∋{k} [v(S ∪ {j}) − v(S)]    = 1 2n−1 ∑ S⊆N\{j} [v(S ∪ {j}) − v(S)] = ϕj(N,v) Next, we will show that the property of consistency almost characterizes the Banzhaf value. ”Almost” refers to the ”initial conditions”, namely, the behavior of the solution for two-person games. The next theorem establishes the main result of this work, we show that consistency together with standardness for two-person games characterize the Banzhaf value. This character- ization is equivalent to that of the Shapley value given by Hart and Mas-Colell (1989) where the only difference rests upon the reduced game concept underlying the notion of consistency. First, we recall that a solution ϕ is standard for two-person games if ϕi({i,j},v) = v({i}) + 1 2 [v({i,j}) − v({i}) − v({j})] for all i 6= j and all v. Thus, the surplus [v({i,j}) − v({i}) − v({j})] is equally divided among the two players. Theorem 9. Let ϕ : GN → Rn in GN be a solution function. Then: (i) ϕ is consistent with respect to the reduced game(1); and (ii) ϕ is standard for two-person games; if and only if ϕ is the Banzhaf value. 6 Joss Erick Sánchez Pérez CUBO 12, 1 (2010) Proof. One direction is immediate, recall Proposition 8 and the fact that: ϕi({i,j},v) = 1 2 ∑ S⊆{j} [v(S ∪ {i}) − v(S)] = v({i}) + 1 2 [v({i,j}) − v({i}) − v({j})] For the other direction, the proof is by induction on the number of players. Assume ϕ,ψ : GN → Rn satisfy (i) and (ii). We claim first that ϕ = ψ for two-person games, since for k ∈ {i,j}: ϕk({i,j},v) = v({k}) + 1 2 [v({i,j}) − v({i}) − v({j})] = 1 2 ∑ S∋k S⊆{i,j} [v(S) − v({i,j}\S)] = ψk({i,j},v) Now, suppose that ϕ and ψ coincide for all the games with n− 1 players. The two-person reduced games: ({i,j},v ϕ {i,j} ) and ({i,j},v ψ {i,j} ) coincide since, v ϕ {i,j} (S) = v ψ {i,j} (S) for any S ⊂ {i,j}. Then ϕi(v ϕ {i,j} ) = ψi(v ψ {i,j} ) by standarness for two-person games, and ϕi(N,v) = ϕi({i,j},v ϕ {i,j} ) = ψi({i,j},v ψ {i,j} ) = ψi(N,v) by consistency. In a similar manner, ϕj(N,v) = ψj(N,v). Applying this to any pair of players, one gets ϕi(N,v) = ψi(N,v) ∀i ∈ N. Received: April, 2008. Revised: September, 2009. References [1] Hart, S. and Mas-Colell, A., Potencial, Value, and Consistency, Econometrica, 57 (1989), 589–614. [2] Lehrer, E., An axiomatization of the Banzhaf value, International Journal of Game Theory, 17 (1988), 89–99. [3] Owen, G., Consistency in values, Sixth Spanish Meeting on Game Theory and Practice, (2003), 15–30.