Cooperative games, solutions and applications

Cooperative games, solutions and applications Anna Borisovna Khmelnitskaya e-mail: a.b.khmelnitskaya@utwente.nl, a.khmelnitskaya@spbu.ru Saint-Petersburg State University March 19, 2020 Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Let Π(N) be a set of all n! permutations π : N → N of N. Denote by π i = {j ∈ N | π(j) ≤ π(i)} the set of players with rank number not greater than the rank number of i, i.e., the set of predecessors of i in ordering π together with i. The marginal contribution vector mπ (v ) ∈ IRN of a game v and a permutation π is given by for all i ∈ N. miπ (v ) = v (π i ) − v (π i \{i}), Consider the following probabilistic distribution model : Assume that the players have as their goal the formation of N and they see it as a sequential process when players enter the room in an arbitrary order, let π = (i1 , ..., in ). The first player i1 gets v ({i1 }) = miπ (v ), 1 The second player i2 gets v ({i1 , i2 }) − v ({i1 }) = miπ (v ), etc. 2 The last player in gets v (N) − v (N\{in }) = miπn (v ). There are n! possible orderings and assume that all orderings are equally possible. Shi (v ) = ψi (v ) = 1 X π 1 X m (v ) = [v (π i ) − v (π i \{i})]. n! π∈Π i n! π∈Π Anna Borisovna Khmelnitskaya Cooperative Game Theory (1) Shapley value Let Π(N) be a set of all n! permutations π : N → N of N. Denote by π i = {j ∈ N | π(j) ≤ π(i)} the set of players with rank number not greater than the rank number of i, i.e., the set of predecessors of i in ordering π together with i. The marginal contribution vector mπ (v ) ∈ IRN of a game v and a permutation π is given by for all i ∈ N. miπ (v ) = v (π i ) − v (π i \{i}), Consider the following probabilistic distribution model : Assume that the players have as their goal the formation of N and they see it as a sequential process when players enter the room in an arbitrary order, let π = (i1 , ..., in ). The first player i1 gets v ({i1 }) = miπ (v ), 1 The second player i2 gets v ({i1 , i2 }) − v ({i1 }) = miπ (v ), etc. 2 The last player in gets v (N) − v (N\{in }) = miπn (v ). There are n! possible orderings and assume that all orderings are equally possible. Shi (v ) = ψi (v ) = 1 X π 1 X m (v ) = [v (π i ) − v (π i \{i})]. n! π∈Π i n! π∈Π Anna Borisovna Khmelnitskaya Cooperative Game Theory (1) Shapley value Let Π(N) be a set of all n! permutations π : N → N of N. Denote by π i = {j ∈ N | π(j) ≤ π(i)} the set of players with rank number not greater than the rank number of i, i.e., the set of predecessors of i in ordering π together with i. The marginal contribution vector mπ (v ) ∈ IRN of a game v and a permutation π is given by for all i ∈ N. miπ (v ) = v (π i ) − v (π i \{i}), Consider the following probabilistic distribution model : Assume that the players have as their goal the formation of N and they see it as a sequential process when players enter the room in an arbitrary order, let π = (i1 , ..., in ). The first player i1 gets v ({i1 }) = miπ (v ), 1 The second player i2 gets v ({i1 , i2 }) − v ({i1 }) = miπ (v ), etc. 2 The last player in gets v (N) − v (N\{in }) = miπn (v ). There are n! possible orderings and assume that all orderings are equally possible. Shi (v ) = ψi (v ) = 1 X π 1 X m (v ) = [v (π i ) − v (π i \{i})]. n! π∈Π i n! π∈Π Anna Borisovna Khmelnitskaya Cooperative Game Theory (1) Shapley value The most reasonable approach to the choice of a right solution concept is the axiomatic approach which allows to choose a solution that satisfies a number of a priori chosen properties stated as axioms reflecting suitable under the circumstances criteria, such as social efficiency, fairness, marginality, simplification of computational complexity, etc. A value ξ is efficient if for all v ∈ G, P i∈N ξi (v ) = v (N). A player i ∈ N is a null-player in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) = v (S). Players i, j ∈ N, i 6= j, are symmetric or substitutes in game v ∈ G if for every S ⊆ N\{i, j}, v (S ∪ {i}) = v (S ∪ {j}). A value ξ possesses the null-player property if for all v ∈ G, for every null-player i ∈ N in game v , ξi (v ) = 0. A value ξ possesses the equal treatment property if for all v ∈ G, for every substitutes i, j ∈ N in game v , ξi (v ) = ξj (v ). A value ξ is additive if for any two v , w ∈ G, ξ(v + w) = ξ(v ) + ξ(w), where (v + w)(S) = v (S) + w(S), for all S ⊆ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value The most reasonable approach to the choice of a right solution concept is the axiomatic approach which allows to choose a solution that satisfies a number of a priori chosen properties stated as axioms reflecting suitable under the circumstances criteria, such as social efficiency, fairness, marginality, simplification of computational complexity, etc. A value ξ is efficient if for all v ∈ G, P i∈N ξi (v ) = v (N). A player i ∈ N is a null-player in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) = v (S). Players i, j ∈ N, i 6= j, are symmetric or substitutes in game v ∈ G if for every S ⊆ N\{i, j}, v (S ∪ {i}) = v (S ∪ {j}). A value ξ possesses the null-player property if for all v ∈ G, for every null-player i ∈ N in game v , ξi (v ) = 0. A value ξ possesses the equal treatment property if for all v ∈ G, for every substitutes i, j ∈ N in game v , ξi (v ) = ξj (v ). A value ξ is additive if for any two v , w ∈ G, ξ(v + w) = ξ(v ) + ξ(w), where (v + w)(S) = v (S) + w(S), for all S ⊆ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value The most reasonable approach to the choice of a right solution concept is the axiomatic approach which allows to choose a solution that satisfies a number of a priori chosen properties stated as axioms reflecting suitable under the circumstances criteria, such as social efficiency, fairness, marginality, simplification of computational complexity, etc. A value ξ is efficient if for all v ∈ G, P i∈N ξi (v ) = v (N). A player i ∈ N is a null-player in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) = v (S). Players i, j ∈ N, i 6= j, are symmetric or substitutes in game v ∈ G if for every S ⊆ N\{i, j}, v (S ∪ {i}) = v (S ∪ {j}). A value ξ possesses the null-player property if for all v ∈ G, for every null-player i ∈ N in game v , ξi (v ) = 0. A value ξ possesses the equal treatment property if for all v ∈ G, for every substitutes i, j ∈ N in game v , ξi (v ) = ξj (v ). A value ξ is additive if for any two v , w ∈ G, ξ(v + w) = ξ(v ) + ξ(w), where (v + w)(S) = v (S) + w(S), for all S ⊆ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value The most reasonable approach to the choice of a right solution concept is the axiomatic approach which allows to choose a solution that satisfies a number of a priori chosen properties stated as axioms reflecting suitable under the circumstances criteria, such as social efficiency, fairness, marginality, simplification of computational complexity, etc. A value ξ is efficient if for all v ∈ G, P i∈N ξi (v ) = v (N). A player i ∈ N is a null-player in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) = v (S). Players i, j ∈ N, i 6= j, are symmetric or substitutes in game v ∈ G if for every S ⊆ N\{i, j}, v (S ∪ {i}) = v (S ∪ {j}). A value ξ possesses the null-player property if for all v ∈ G, for every null-player i ∈ N in game v , ξi (v ) = 0. A value ξ possesses the equal treatment property if for all v ∈ G, for every substitutes i, j ∈ N in game v , ξi (v ) = ξj (v ). A value ξ is additive if for any two v , w ∈ G, ξ(v + w) = ξ(v ) + ξ(w), where (v + w)(S) = v (S) + w(S), for all S ⊆ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value The most reasonable approach to the choice of a right solution concept is the axiomatic approach which allows to choose a solution that satisfies a number of a priori chosen properties stated as axioms reflecting suitable under the circumstances criteria, such as social efficiency, fairness, marginality, simplification of computational complexity, etc. A value ξ is efficient if for all v ∈ G, P i∈N ξi (v ) = v (N). A player i ∈ N is a null-player in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) = v (S). Players i, j ∈ N, i 6= j, are symmetric or substitutes in game v ∈ G if for every S ⊆ N\{i, j}, v (S ∪ {i}) = v (S ∪ {j}). A value ξ possesses the null-player property if for all v ∈ G, for every null-player i ∈ N in game v , ξi (v ) = 0. A value ξ possesses the equal treatment property if for all v ∈ G, for every substitutes i, j ∈ N in game v , ξi (v ) = ξj (v ). A value ξ is additive if for any two v , w ∈ G, ξ(v + w) = ξ(v ) + ξ(w), where (v + w)(S) = v (S) + w(S), for all S ⊆ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value The most reasonable approach to the choice of a right solution concept is the axiomatic approach which allows to choose a solution that satisfies a number of a priori chosen properties stated as axioms reflecting suitable under the circumstances criteria, such as social efficiency, fairness, marginality, simplification of computational complexity, etc. A value ξ is efficient if for all v ∈ G, P i∈N ξi (v ) = v (N). A player i ∈ N is a null-player in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) = v (S). Players i, j ∈ N, i 6= j, are symmetric or substitutes in game v ∈ G if for every S ⊆ N\{i, j}, v (S ∪ {i}) = v (S ∪ {j}). A value ξ possesses the null-player property if for all v ∈ G, for every null-player i ∈ N in game v , ξi (v ) = 0. A value ξ possesses the equal treatment property if for all v ∈ G, for every substitutes i, j ∈ N in game v , ξi (v ) = ξj (v ). A value ξ is additive if for any two v , w ∈ G, ξ(v + w) = ξ(v ) + ξ(w), where (v + w)(S) = v (S) + w(S), for all S ⊆ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Theorem (Shapley, 1953) There is a unique value defined on the class GN that satisfies efficiency, equal treatment property, null-player property, and additivity, and for all v ∈ GN , for every i ∈ N, it is given by Shi (v ) = X S⊆N\{i}
s!(n − s − 1)! v (S ∪ {i}) − v (S) . n! Anna Borisovna Khmelnitskaya Cooperative Game Theory (2) Shapley value Proof. 1. Existence We show that value ψ defined by (1) satisfies efficiency, symmetry, null-player property, and additivity. n P Efficiency : ψi (v ) = i=1 n 1 1 XX π mi (v ) = n! v (N) = v (N). n! π∈Π n! i=1 Null-player property : follows straightforwardly. Additivity : is obvious since everything is linear. Equal treatment property : First show that (1) can be transformed into the form (2). Fix a coalition S and check how many times S = π i \{i}. S =⇒ ψi (v ) = i N\(S ∪ {i}) 1 X π m (v ) = n! π∈Π i X S⊆N\{i} Anna Borisovna Khmelnitskaya
s!(n − s − 1)! v (S ∪ {i}) − v (S) . n! Cooperative Game Theory Shapley value Proof. 1. Existence We show that value ψ defined by (1) satisfies efficiency, symmetry, null-player property, and additivity. n P Efficiency : ψi (v ) = i=1 n 1 XX π 1 mi (v ) = n! v (N) = v (N). n! π∈Π n! i=1 Null-player property : follows straightforwardly. Additivity : is obvious since everything is linear. Equal treatment property : First show that (1) can be transformed into the form (2). Fix a coalition S and check how many times S = π i \{i}. S =⇒ ψi (v ) = i N\(S ∪ {i}) 1 X π m (v ) = n! π∈Π i X S⊆N\{i} Anna Borisovna Khmelnitskaya
s!(n − s − 1)! v (S ∪ {i}) − v (S) . n! Cooperative Game Theory Shapley value Proof. 1. Existence We show that value ψ defined by (1) satisfies efficiency, symmetry, null-player property, and additivity. n P Efficiency : ψi (v ) = i=1 n 1 XX π 1 mi (v ) = n! v (N) = v (N). n! π∈Π n! i=1 Null-player property : follows straightforwardly. Additivity : is obvious since everything is linear. Equal treatment property : First show that (1) can be transformed into the form (2). Fix a coalition S and check how many times S = π i \{i}. S =⇒ ψi (v ) = i N\(S ∪ {i}) 1 X π m (v ) = n! π∈Π i X S⊆N\{i} Anna Borisovna Khmelnitskaya
s!(n − s − 1)! v (S ∪ {i}) − v (S) . n! Cooperative Game Theory Shapley value Proof. 1. Existence We show that value ψ defined by (1) satisfies efficiency, symmetry, null-player property, and additivity. n P Efficiency : ψi (v ) = i=1 n 1 XX π 1 mi (v ) = n! v (N) = v (N). n! π∈Π n! i=1 Null-player property : follows straightforwardly. Additivity : is obvious since everything is linear. Equal treatment property : First show that (1) can be transformed into the form (2). Fix a coalition S and check how many times S = π i \{i}. S =⇒ ψi (v ) = i N\(S ∪ {i}) 1 X π m (v ) = n! π∈Π i X S⊆N\{i} Anna Borisovna Khmelnitskaya
s!(n − s − 1)! v (S ∪ {i}) − v (S) . n! Cooperative Game Theory Shapley value Proof. 1. Existence We show that value ψ defined by (1) satisfies efficiency, symmetry, null-player property, and additivity. n P Efficiency : ψi (v ) = i=1 n 1 XX π 1 mi (v ) = n! v (N) = v (N). n! π∈Π n! i=1 Null-player property : follows straightforwardly. Additivity : is obvious since everything is linear. Equal treatment property : First show that (1) can be transformed into the form (2). Fix a coalition S and check how many times S = π i \{i}. S =⇒ ψi (v ) = i N\(S ∪ {i}) 1 X π m (v ) = n! π∈Π i X S⊆N\{i} Anna Borisovna Khmelnitskaya
s!(n − s − 1)! v (S ∪ {i}) − v (S) . n! Cooperative Game Theory Shapley value Let players i, j ∈ N be substitutes in game v ∈ G, i.e., v (S ∪ {i}) = v (S ∪ {j}) for every S ⊆ N\{i, j}. We show that ψi (v ) = ψj (v ). ψi (v ) = X S⊆N\{i} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) = n! X s!(n − s − 1)!

s!(n − s − 1)! v (S∪{i})−v (S) + v (S∪{i})−v (S) = n! n! S⊆N\{i} S3j X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) + n! X T ⊆N\{i,j} X S⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪ {i, j}) − v (T ∪ {j}) = n!
s!(n − s − 1)! v (S ∪ {j}) − v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{i, j})−v (T ∪{i}) = ψj (v ). n! Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Let players i, j ∈ N be substitutes in game v ∈ G, i.e., v (S ∪ {i}) = v (S ∪ {j}) for every S ⊆ N\{i, j}. We show that ψi (v ) = ψj (v ). ψi (v ) = X S⊆N\{i} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) = n! X s!(n − s − 1)!

s!(n − s − 1)! v (S∪{i})−v (S) + v (S∪{i})−v (S) = n! n! S⊆N\{i} S3j X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) + n! X T ⊆N\{i,j} X S⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪ {i, j}) − v (T ∪ {j}) = n!
s!(n − s − 1)! v (S ∪ {j}) − v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{i, j})−v (T ∪{i}) = ψj (v ). n! Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Let players i, j ∈ N be substitutes in game v ∈ G, i.e., v (S ∪ {i}) = v (S ∪ {j}) for every S ⊆ N\{i, j}. We show that ψi (v ) = ψj (v ). ψi (v ) = X S⊆N\{i} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) = n! X s!(n − s − 1)!

s!(n − s − 1)! v (S∪{i})−v (S) + v (S∪{i})−v (S) = n! n! S⊆N\{i} S3j X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) + n! X T ⊆N\{i,j} X S⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪ {i, j}) − v (T ∪ {j}) = n!
s!(n − s − 1)! v (S ∪ {j}) − v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{i, j})−v (T ∪{i}) = ψj (v ). n! Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Let players i, j ∈ N be substitutes in game v ∈ G, i.e., v (S ∪ {i}) = v (S ∪ {j}) for every S ⊆ N\{i, j}. We show that ψi (v ) = ψj (v ). ψi (v ) = X S⊆N\{i} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) = n! X s!(n − s − 1)!

s!(n − s − 1)! v (S∪{i})−v (S) + v (S∪{i})−v (S) = n! n! S⊆N\{i} S3j X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) + n! X T ⊆N\{i,j} X S⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪ {i, j}) − v (T ∪ {j}) = n!
s!(n − s − 1)! v (S ∪ {j}) − v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{i, j})−v (T ∪{i}) = ψj (v ). n! Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Let players i, j ∈ N be substitutes in game v ∈ G, i.e., v (S ∪ {i}) = v (S ∪ {j}) for every S ⊆ N\{i, j}. We show that ψi (v ) = ψj (v ). ψi (v ) = X S⊆N\{i} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) = n! X s!(n − s − 1)!

s!(n − s − 1)! v (S∪{i})−v (S) + v (S∪{i})−v (S) = n! n! S⊆N\{i} S3j X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {i}) − v (S) + n! X T ⊆N\{i,j} X S⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪ {i, j}) − v (T ∪ {j}) = n!
s!(n − s − 1)! v (S ∪ {j}) − v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{i, j})−v (T ∪{i}) = ψj (v ). n! Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value 2. Uniqueness Assume that a value ψ on GN meets all four axioms. For every T ⊆ N, T 6= ∅, define the unanimity game as  1, T ⊆ S, for all S ⊆ N. uT (S) = 0, T 6⊆ S, Let λ be arbitrary real number. First we find ψ(λ uT ). Every i ∈ / T is a null-player and therefore gets nothing. Any i, j ∈ T are substitutes and by equal treatment property they get equal payoffs.   λ, ψi (λ uT ) = t  0, =⇒ i ∈ T, i∈ / T. It turns out that unanimity games {uT } T ⊆N create a basis in GN . T 6=∅ To prove that it is enough to show that all uT , T ⊆ N, T 6= ∅, are linear independent. X Let αT uT = 0, and let not all αT = 0. ∅6=T ⊆N =⇒ there is a coalition T0 = 6 ∅ such that αT0 = 6 0 and for all T ⊂ T0 , αT = 0. X X αT αT uT =⇒ uT0 (T0 ) = − uT (T0 ). =⇒ uT0 = − αT 0 αT0 T *T0 T *T0 =⇒ uT0 (T0 ) = 0, contradiction. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value 2. Uniqueness Assume that a value ψ on GN meets all four axioms. For every T ⊆ N, T 6= ∅, define the unanimity game as  1, T ⊆ S, for all S ⊆ N. uT (S) = 0, T 6⊆ S, Let λ be arbitrary real number. First we find ψ(λ uT ). Every i ∈ / T is a null-player and therefore gets nothing. Any i, j ∈ T are substitutes and by equal treatment property they get equal payoffs.   λ, ψi (λ uT ) = t  0, =⇒ i ∈ T, i∈ / T. It turns out that unanimity games {uT } T ⊆N create a basis in GN . T 6=∅ To prove that it is enough to show that all uT , T ⊆ N, T 6= ∅, are linear independent. X Let αT uT = 0, and let not all αT = 0. ∅6=T ⊆N =⇒ there is a coalition T0 = 6 ∅ such that αT0 = 6 0 and for all T ⊂ T0 , αT = 0. X X αT αT =⇒ uT0 = − uT =⇒ uT0 (T0 ) = − uT (T0 ). αT 0 αT0 T *T0 =⇒ T *T0 uT0 (T0 ) = 0, contradiction. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value 2. Uniqueness Assume that a value ψ on GN meets all four axioms. For every T ⊆ N, T 6= ∅, define the unanimity game as  1, T ⊆ S, for all S ⊆ N. uT (S) = 0, T 6⊆ S, Let λ be arbitrary real number. First we find ψ(λ uT ). Every i ∈ / T is a null-player and therefore gets nothing. Any i, j ∈ T are substitutes and by equal treatment property they get equal payoffs.   λ, ψi (λ uT ) = t  0, =⇒ i ∈ T, i∈ / T. It turns out that unanimity games {uT } T ⊆N create a basis in GN . T 6=∅ To prove that it is enough to show that all uT , T ⊆ N, T 6= ∅, are linear independent. X Let αT uT = 0, and let not all αT = 0. ∅6=T ⊆N =⇒ there is a coalition T0 = 6 ∅ such that αT0 = 6 0 and for all T ⊂ T0 , αT = 0. X X αT αT =⇒ uT0 = − uT =⇒ uT0 (T0 ) = − uT (T0 ). αT 0 αT0 T *T0 =⇒ T *T0 uT0 (T0 ) = 0, contradiction. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value 2. Uniqueness Assume that a value ψ on GN meets all four axioms. For every T ⊆ N, T 6= ∅, define the unanimity game as  1, T ⊆ S, for all S ⊆ N. uT (S) = 0, T 6⊆ S, Let λ be arbitrary real number. First we find ψ(λ uT ). Every i ∈ / T is a null-player and therefore gets nothing. Any i, j ∈ T are substitutes and by equal treatment property they get equal payoffs.   λ, ψi (λ uT ) = t  0, =⇒ i ∈ T, i∈ / T. It turns out that unanimity games {uT } T ⊆N create a basis in GN . T 6=∅ To prove that it is enough to show that all uT , T ⊆ N, T 6= ∅, are linear independent. X Let αT uT = 0, and let not all αT = 0. ∅6=T ⊆N =⇒ there is a coalition T0 = 6 ∅ such that αT0 = 6 0 and for all T ⊂ T0 , αT = 0. X X αT αT =⇒ uT0 = − uT =⇒ uT0 (T0 ) = − uT (T0 ). αT 0 αT0 T *T0 =⇒ T *T0 uT0 (T0 ) = 0, contradiction. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, Harsanyi dividends Corollary. Any game v ∈ GN can be presented via unanimity basis {uT } T ⊆N , T 6=∅ X v= λvT uT , (3) ∅6=T ⊆N Following Harsanyi (1959) λvT is called the dividend of the coalition T in the game v . X v (S) = λvT , for all S ⊆ N, S 6= ∅. ∅6=T ⊆S λvS has a natural interpretation as the extra revenue from cooperation among players in S that they could not realize staying in proper subcoalitions. Moreover, we obtain another formula representation for the Shapley value: Shi (v ) = X λv T T ⊆N T 3i t for all i ∈ N. Proposition λvT = X (−1)t−s v (S), for all T ⊆ N, T 6= ∅. S⊆T Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, Harsanyi dividends Corollary. Any game v ∈ GN can be presented via unanimity basis {uT } T ⊆N , T 6=∅ X v= λvT uT , (3) ∅6=T ⊆N Following Harsanyi (1959) λvT is called the dividend of the coalition T in the game v . X v (S) = λvT , for all S ⊆ N, S 6= ∅. ∅6=T ⊆S λvS has a natural interpretation as the extra revenue from cooperation among players in S that they could not realize staying in proper subcoalitions. Moreover, we obtain another formula representation for the Shapley value: Shi (v ) = X λv T T ⊆N T 3i t for all i ∈ N. Proposition λvT = X (−1)t−s v (S), for all T ⊆ N, T 6= ∅. S⊆T Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, Harsanyi dividends Corollary. Any game v ∈ GN can be presented via unanimity basis {uT } T ⊆N , T 6=∅ X v= λvT uT , (3) ∅6=T ⊆N Following Harsanyi (1959) λvT is called the dividend of the coalition T in the game v . X v (S) = λvT , for all S ⊆ N, S 6= ∅. ∅6=T ⊆S λvS has a natural interpretation as the extra revenue from cooperation among players in S that they could not realize staying in proper subcoalitions. Moreover, we obtain another formula representation for the Shapley value: Shi (v ) = X λv T T ⊆N T 3i t for all i ∈ N. Proposition λvT = X (−1)t−s v (S), for all T ⊆ N, T 6= ∅. S⊆T Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, Harsanyi dividends Proposition λvT = X (−1)t−s v (S), for all T ⊆ N, T 6= ∅. S⊆T Proof. P v= ∅6=T ⊆N X λvT uT , and consider arbitrary Q ⊆ N. λvT uT (Q) = ∅6=T ⊆N X S⊆Q X X  (−1)t−s v (S) uT (Q) = ∅6=T ⊆N S⊆T X X (−1)t−s v (S) = ∅6=T ⊆Q S⊆T q  X  X X q − s
 v (S) (−1)t−s = v (Q)+ v (S) (−1)t−s = t −s t=s S⊆T ⊆Q S$Q v (Q) + X (1 − 1)q−s v (S) = v (Q). S$Q Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, simple games Let v ∈ GN be a simple game. The Shapley value of a simple game v is given by X Shi (v ) = S⊆N\{i} S ∈W / (v ) S∪{i}∈W (v ) s!(n − s − 1)! , n! for all i ∈ N, and is called the Shapley-Shubik power index of v . λvT = X (−1)t−s v (S), for all T ⊆ N, T 6= ∅. S⊆T If T ∈ / W (v ) then λvT = 0; c(v ) then λv = 1. if T ∈ W T Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, simple games Let v ∈ GN be a simple game. The Shapley value of a simple game v is given by X Shi (v ) = S⊆N\{i} S ∈W / (v ) S∪{i}∈W (v ) s!(n − s − 1)! , n! for all i ∈ N, and is called the Shapley-Shubik power index of v . λvT = X (−1)t−s v (S), for all T ⊆ N, T 6= ∅. S⊆T If T ∈ / W (v ) then λvT = 0; c(v ) then λv = 1. if T ∈ W T Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, null-player out property A value ξ possesses the null-player out property if for all v ∈ GN for any null-player i ∈ N in game v it holds that for all j ∈ N, j 6= i, ξj (v ) = ξj (v |N\{i} ). Proposition The Shapley value meets the null-player out property. Proof. Let i ∈ N be a null-player in v and consider j ∈ N, j 6= i. Shj (v ) = X S⊆N\{j} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {j}) − v (S) = n!
s!(n − s − 1)! v (S∪{j})−v (S) + n! X S⊆N\{j},S3i
s!(n − s − 1)! v (S∪{j})−v (S) = n! i is a null-player =⇒ v (S) = v (S\{i}) and v (S∪{j}) = v ((S∪{j})\{i}) = v ((S\{i})∪{j}). Let in the second sum T = S\{i}. X S⊆N\{i,j}
s!(n − s − 1)! v (S∪{j})−v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{j})−v (T ) = n! Change notation T → S and t → s in the second sum. X s!(n − s − 2)!
v (S ∪ {j}) − v (S) = Shj (v |N\{i} ). (n − 1)! S⊆N\{i,j} Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, null-player out property A value ξ possesses the null-player out property if for all v ∈ GN for any null-player i ∈ N in game v it holds that for all j ∈ N, j 6= i, ξj (v ) = ξj (v |N\{i} ). Proposition The Shapley value meets the null-player out property. Proof. Let i ∈ N be a null-player in v and consider j ∈ N, j 6= i. Shj (v ) = X S⊆N\{j} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {j}) − v (S) = n!
s!(n − s − 1)! v (S∪{j})−v (S) + n! X S⊆N\{j},S3i
s!(n − s − 1)! v (S∪{j})−v (S) = n! i is a null-player =⇒ v (S) = v (S\{i}) and v (S∪{j}) = v ((S∪{j})\{i}) = v ((S\{i})∪{j}). Let in the second sum T = S\{i}. X S⊆N\{i,j}
s!(n − s − 1)! v (S∪{j})−v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{j})−v (T ) = n! Change notation T → S and t → s in the second sum. X s!(n − s − 2)!
v (S ∪ {j}) − v (S) = Shj (v |N\{i} ). (n − 1)! S⊆N\{i,j} Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, null-player out property A value ξ possesses the null-player out property if for all v ∈ GN for any null-player i ∈ N in game v it holds that for all j ∈ N, j 6= i, ξj (v ) = ξj (v |N\{i} ). Proposition The Shapley value meets the null-player out property. Proof. Let i ∈ N be a null-player in v and consider j ∈ N, j 6= i. Shj (v ) = X S⊆N\{j} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {j}) − v (S) = n!
s!(n − s − 1)! v (S∪{j})−v (S) + n! X S⊆N\{j},S3i
s!(n − s − 1)! v (S∪{j})−v (S) = n! i is a null-player =⇒ v (S) = v (S\{i}) and v (S∪{j}) = v ((S∪{j})\{i}) = v ((S\{i})∪{j}). Let in the second sum T = S\{i}. X S⊆N\{i,j}
s!(n − s − 1)! v (S∪{j})−v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{j})−v (T ) = n! Change notation T → S and t → s in the second sum. X s!(n − s − 2)!
v (S ∪ {j}) − v (S) = Shj (v |N\{i} ). (n − 1)! S⊆N\{i,j} Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, null-player out property A value ξ possesses the null-player out property if for all v ∈ GN for any null-player i ∈ N in game v it holds that for all j ∈ N, j 6= i, ξj (v ) = ξj (v |N\{i} ). Proposition The Shapley value meets the null-player out property. Proof. Let i ∈ N be a null-player in v and consider j ∈ N, j 6= i. Shj (v ) = X S⊆N\{j} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {j}) − v (S) = n!
s!(n − s − 1)! v (S∪{j})−v (S) + n! X S⊆N\{j},S3i
s!(n − s − 1)! v (S∪{j})−v (S) = n! i is a null-player =⇒ v (S) = v (S\{i}) and v (S∪{j}) = v ((S∪{j})\{i}) = v ((S\{i})∪{j}). Let in the second sum T = S\{i}. X S⊆N\{i,j}
s!(n − s − 1)! v (S∪{j})−v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{j})−v (T ) = n! Change notation T → S and t → s in the second sum. X s!(n − s − 2)!
v (S ∪ {j}) − v (S) = Shj (v |N\{i} ). (n − 1)! S⊆N\{i,j} Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, null-player out property A value ξ possesses the null-player out property if for all v ∈ GN for any null-player i ∈ N in game v it holds that for all j ∈ N, j 6= i, ξj (v ) = ξj (v |N\{i} ). Proposition The Shapley value meets the null-player out property. Proof. Let i ∈ N be a null-player in v and consider j ∈ N, j 6= i. Shj (v ) = X S⊆N\{j} X S⊆N\{i,j}
s!(n − s − 1)! v (S ∪ {j}) − v (S) = n!
s!(n − s − 1)! v (S∪{j})−v (S) + n! X S⊆N\{j},S3i
s!(n − s − 1)! v (S∪{j})−v (S) = n! i is a null-player =⇒ v (S) = v (S\{i}) and v (S∪{j}) = v ((S∪{j})\{i}) = v ((S\{i})∪{j}). Let in the second sum T = S\{i}. X S⊆N\{i,j}
s!(n − s − 1)! v (S∪{j})−v (S) + n! X T ⊆N\{i,j}
(t + 1)!(n − t − 2)! v (T ∪{j})−v (T ) = n! Change notation T → S and t → s in the second sum. X s!(n − s − 2)!
v (S ∪ {j}) − v (S) = Shj (v |N\{i} ). (n − 1)! S⊆N\{i,j} Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, some other properties • Covariance A value ξ is covariant under strategicPequivalence if for any v ∈ GN , k > 0, a ∈ IRN and ai for all S ⊆ N, w ∈ GN such that w(S) = kv (S) + i∈S ξ(w) = k ξ(v ) + a. Both the core and the nucleolus are covariant. • Linearity A value ξ is linear if for any liner combination v = m P αk vk of games v1 , ..., vm ∈ GN , k =1 αk ∈ IR, it holds that ξ(v ) = m P αk ξ(vk ), k =1 where v (S) = m P αk vk (S) for all S ⊆ N. k =1 Under covariance linearity is equivalent to additivity. The core is linear, but the nucleolus is not. • Dummy player property A player i ∈ N is a dummy in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) − v (S) = v ({i}). A value ξ possesses the dummy player property if for all v ∈ GN , for every dummy i ∈ N in game v , ξi (v ) = v ({i}). Anna Borisovna Khmelnitskaya Cooperative Game Theory Under covariance the null-player property is equivalent to the dummy player property. Shapley value, some other properties • Covariance A value ξ is covariant under strategicPequivalence if for any v ∈ GN , k > 0, a ∈ IRN and ai for all S ⊆ N, w ∈ GN such that w(S) = kv (S) + i∈S ξ(w) = k ξ(v ) + a. Both the core and the nucleolus are covariant. • Linearity A value ξ is linear if for any liner combination v = m P αk vk of games v1 , ..., vm ∈ GN , k =1 αk ∈ IR, it holds that ξ(v ) = m P αk ξ(vk ), k =1 where v (S) = m P αk vk (S) for all S ⊆ N. k =1 Under covariance linearity is equivalent to additivity. The core is linear, but the nucleolus is not. • Dummy player property A player i ∈ N is a dummy in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) − v (S) = v ({i}). A value ξ possesses the dummy player property if for all v ∈ GN , for every dummy i ∈ N in game v , ξi (v ) = v ({i}). Anna Borisovna Khmelnitskaya Cooperative Game Theory Under covariance the null-player property is equivalent to the dummy player property. Shapley value, some other properties • Covariance A value ξ is covariant under strategicPequivalence if for any v ∈ GN , k > 0, a ∈ IRN and ai for all S ⊆ N, w ∈ GN such that w(S) = kv (S) + i∈S ξ(w) = k ξ(v ) + a. Both the core and the nucleolus are covariant. • Linearity A value ξ is linear if for any liner combination v = m P αk vk of games v1 , ..., vm ∈ GN , k =1 αk ∈ IR, it holds that ξ(v ) = m P αk ξ(vk ), k =1 where v (S) = m P αk vk (S) for all S ⊆ N. k =1 Under covariance linearity is equivalent to additivity. The core is linear, but the nucleolus is not. • Dummy player property A player i ∈ N is a dummy in game v ∈ G if for every S ⊆ N\{i}, v (S ∪ {i}) − v (S) = v ({i}). A value ξ possesses the dummy player property if for all v ∈ GN , for every dummy i ∈ N in game v , ξi (v ) = v ({i}). Anna Borisovna Khmelnitskaya Cooperative Game Theory Under covariance the null-player property is equivalent to the dummy player property. Shapley value, some other properties • Anonymity A value ξ is anonymous if for all v ∈ G, for any permutation of players π ∈ Π it holds that ξ(πv ) = πξ(v ), where game πv is defined by πv (S) = v (π(S)) for all S ⊆ N. Remark: For single-valued solutions from anonymity follows equal treatment property but for set-valued this is not true. For example, the imputation set meets anonymity but not equal treatment property • Individual rationality A value ξ is individually rational in the game v ∈ GN if ξi (v ) ≥ v ({i}) for all i ∈ N. In a superadditive game the Shapley value is individually rational. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, some other properties • Anonymity A value ξ is anonymous if for all v ∈ G, for any permutation of players π ∈ Π it holds that ξ(πv ) = πξ(v ), where game πv is defined by πv (S) = v (π(S)) for all S ⊆ N. Remark: For single-valued solutions from anonymity follows equal treatment property but for set-valued this is not true. For example, the imputation set meets anonymity but not equal treatment property • Individual rationality A value ξ is individually rational in the game v ∈ GN if ξi (v ) ≥ v ({i}) for all i ∈ N. In a superadditive game the Shapley value is individually rational. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, some other properties • Monotonicity (positivity) A game v is monotonic if v (S) ≤ v (T ) for all S ⊆ T ⊆ N. A value ξ is monotonic if ξi (v ) ≥ 0, i ∈ N, for any monotonic game v ∈ GN . • Aggregate monotonicity A value ξ is aggregate monotonic if for any v , w ∈ GN such that v (N) ≥ w(N) and v (S) = w(S) for all S $ N, it holds that ξi (v ) ≥ ξi (w) for all i ∈ N. • Coalitional monotonicity A value ξ is coalitionally monotonic if for any v , w ∈ GN such that for some T ⊆ N v (T ) ≥ w(T ) and v (S) = w(S) for all S ⊆ N, S 6= T , it holds that ξi (v ) ≥ ξi (w) for all i ∈ T . Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, some other properties • Monotonicity (positivity) A game v is monotonic if v (S) ≤ v (T ) for all S ⊆ T ⊆ N. A value ξ is monotonic if ξi (v ) ≥ 0, i ∈ N, for any monotonic game v ∈ GN . • Aggregate monotonicity A value ξ is aggregate monotonic if for any v , w ∈ GN such that v (N) ≥ w(N) and v (S) = w(S) for all S $ N, it holds that ξi (v ) ≥ ξi (w) for all i ∈ N. • Coalitional monotonicity A value ξ is coalitionally monotonic if for any v , w ∈ GN such that for some T ⊆ N v (T ) ≥ w(T ) and v (S) = w(S) for all S ⊆ N, S 6= T , it holds that ξi (v ) ≥ ξi (w) for all i ∈ T . Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, some other properties • Monotonicity (positivity) A game v is monotonic if v (S) ≤ v (T ) for all S ⊆ T ⊆ N. A value ξ is monotonic if ξi (v ) ≥ 0, i ∈ N, for any monotonic game v ∈ GN . • Aggregate monotonicity A value ξ is aggregate monotonic if for any v , w ∈ GN such that v (N) ≥ w(N) and v (S) = w(S) for all S $ N, it holds that ξi (v ) ≥ ξi (w) for all i ∈ N. • Coalitional monotonicity A value ξ is coalitionally monotonic if for any v , w ∈ GN such that for some T ⊆ N v (T ) ≥ w(T ) and v (S) = w(S) for all S ⊆ N, S 6= T , it holds that ξi (v ) ≥ ξi (w) for all i ∈ T . Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Let G denote the set of all TU games. Given a function P : G → IR, the marginal contribution of a player i in a game hN, v i is D i P(N, v ) = P(N, v ) − P(N\{i}, v ), (4) where game hN\{i}, v i is the subgame of hN, v i on N\{i}. A function P : G → IR with P(∅, v ) = 0 is called a potential function if for all games hN, v i ∈ G it satisfies the condition X D i P(N, v ) = v (N). (5) i∈N Marginals of a potential function are always efficient. Theorem (Hart and Mas-Colell, 1988) There exists a unique potential function P. For every game hN, v i ∈ G " # X 1 P(N, v ) = v (N) + P(N\{i}, v ) , n (6) i∈N and D i P(N, v ) = Shi (N, v ), Anna Borisovna Khmelnitskaya for all i ∈ N. Cooperative Game Theory (7) Shapley value, potential Let G denote the set of all TU games. Given a function P : G → IR, the marginal contribution of a player i in a game hN, v i is D i P(N, v ) = P(N, v ) − P(N\{i}, v ), (4) where game hN\{i}, v i is the subgame of hN, v i on N\{i}. A function P : G → IR with P(∅, v ) = 0 is called a potential function if for all games hN, v i ∈ G it satisfies the condition X D i P(N, v ) = v (N). (5) i∈N Marginals of a potential function are always efficient. Theorem (Hart and Mas-Colell, 1988) There exists a unique potential function P. For every game hN, v i ∈ G " # X 1 P(N, v ) = v (N) + P(N\{i}, v ) , n (6) i∈N and D i P(N, v ) = Shi (N, v ), Anna Borisovna Khmelnitskaya for all i ∈ N. Cooperative Game Theory (7) Shapley value, potential Let G denote the set of all TU games. Given a function P : G → IR, the marginal contribution of a player i in a game hN, v i is D i P(N, v ) = P(N, v ) − P(N\{i}, v ), (4) where game hN\{i}, v i is the subgame of hN, v i on N\{i}. A function P : G → IR with P(∅, v ) = 0 is called a potential function if for all games hN, v i ∈ G it satisfies the condition X D i P(N, v ) = v (N). (5) i∈N Marginals of a potential function are always efficient. Theorem (Hart and Mas-Colell, 1988) There exists a unique potential function P. For every game hN, v i ∈ G " # X 1 P(N, v ) = v (N) + P(N\{i}, v ) , n (6) i∈N and D i P(N, v ) = Shi (N, v ), Anna Borisovna Khmelnitskaya for all i ∈ N. Cooperative Game Theory (7) Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proof. (6) follows straightforwardly from (4) and (5). Starting with P(∅, v ) = 0, (6) determines P(N, v ) recursively. This proves the existence and uniqueness of the potential function P. To prove that D i P(N, v ) = Shi (N, v ) for all hN, v i ∈ G and i ∈ N it suffices to show that the payoff vector (D i P(N, v ))i∈N meets all four Shapley axioms. Efficiency : this is just (5). The other three axioms we prove by induction using the recursive formula (6). Null-player property : Let i be a null-player in hN, v i. We show P(N, v ) = P(N\{i}, v ). If n = 1, then P({i}, v ) = v ({i}) = 0 = P(∅, v ). Assume that the assertion holds for all games with less than n players, in particular, P(N\{j}, v ) = P(N\{j, i}, v ) for all j ∈ N, j 6= i. Subtract (6) for N\{i} from (6) for N: X n[P(N, v )−P(N\{i}, v )] = [v (N)−v (N\{i})]+ [P(N\{j}, v )−P(N\{j, i}, v )] = 0. j∈N\{i} Equal treatment property : Let i and j be substitutes in hN, v i. =⇒ v (S ∪ {i}) = v (S ∪ {j}) for all S ⊆ N\{i, j}, and together with (6) =⇒ P(N\{i}, v ) = P(N\{j}, v ) =⇒ D i P(N, v ) = D j P(N, v ). Additivity : another induction argument on (6) shows that P(N, v + w) = P(N, v ) + P(N, w) which implies additivity. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X λv T T ⊆N t . Proof. Denote X λv T T ⊆N t by Q(N, v ). Q(∅, v ) = 0 and Q(N, v ) − Q(N\{i}, v ) = X T ⊆N,T 3i λvT t = Shi (N, v ). =⇒ Q(N, v ) meets (5) =⇒ by Theorem of Hart and Mas-Colell Q(N, v ) = P(N, v ). Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X λv T T ⊆N t . Proof. Denote X λv T T ⊆N t by Q(N, v ). Q(∅, v ) = 0 and Q(N, v ) − Q(N\{i}, v ) = X T ⊆N,T 3i λvT t = Shi (N, v ). =⇒ Q(N, v ) meets (5) =⇒ by Theorem of Hart and Mas-Colell Q(N, v ) = P(N, v ). Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X λv T T ⊆N t . Proof. Denote X λv T T ⊆N t by Q(N, v ). Q(∅, v ) = 0 and Q(N, v ) − Q(N\{i}, v ) = X T ⊆N,T 3i λvT t = Shi (N, v ). =⇒ Q(N, v ) meets (5) =⇒ by Theorem of Hart and Mas-Colell Q(N, v ) = P(N, v ). Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X (s − 1)!(n − s)! v (S). n! S⊆N Proof. X (s − 1)!(n − s)! v (S) by Q(N, v ). Q(∅, v ) = 0. n! Denote S⊆N Q(N, v )−Q(N\{i}, v ) = X (s − 1)!(n − s)! X v (S)− n! S⊆N X S⊆N,S3i S⊆N\{i} X (s−1)!(n−s)! v (S)+ n! S⊆N\{i} (s − 1)!(n − s − 1)! v (S) = (n − 1)! X (s−1)!(n−s)! v (S)− n! S⊆N\{i} (s−1)!(n−s−1)! v (S) = (n−1)! In the first sum denote S\{i} by T , so, t = s − 1, and then change T → S and t → s. X T ⊆N\{i} X t!(n − t − 1)! v (T ∪{i})− n! S⊆N\{i} Anna Borisovna Khmelnitskaya s!(n − s − 1)! v (S) = Shi (v ). n! Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X (s − 1)!(n − s)! v (S). n! S⊆N Proof. X (s − 1)!(n − s)! v (S) by Q(N, v ). Q(∅, v ) = 0. n! Denote S⊆N Q(N, v )−Q(N\{i}, v ) = X (s − 1)!(n − s)! X v (S)− n! S⊆N X S⊆N,S3i S⊆N\{i} X (s−1)!(n−s)! v (S)+ n! S⊆N\{i} (s − 1)!(n − s − 1)! v (S) = (n − 1)! X (s−1)!(n−s)! v (S)− n! S⊆N\{i} (s−1)!(n−s−1)! v (S) = (n−1)! In the first sum denote S\{i} by T , so, t = s − 1, and then change T → S and t → s. X T ⊆N\{i} X t!(n − t − 1)! v (T ∪{i})− n! S⊆N\{i} Anna Borisovna Khmelnitskaya s!(n − s − 1)! v (S) = Shi (v ). n! Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X (s − 1)!(n − s)! v (S). n! S⊆N Proof. X (s − 1)!(n − s)! v (S) by Q(N, v ). Q(∅, v ) = 0. n! Denote S⊆N Q(N, v )−Q(N\{i}, v ) = X (s − 1)!(n − s)! X v (S)− n! S⊆N X S⊆N,S3i S⊆N\{i} X (s−1)!(n−s)! v (S)+ n! S⊆N\{i} (s − 1)!(n − s − 1)! v (S) = (n − 1)! X (s−1)!(n−s)! v (S)− n! S⊆N\{i} (s−1)!(n−s−1)! v (S) = (n−1)! In the first sum denote S\{i} by T , so, t = s − 1, and then change T → S and t → s. X T ⊆N\{i} X t!(n − t − 1)! v (T ∪{i})− n! S⊆N\{i} Anna Borisovna Khmelnitskaya s!(n − s − 1)! v (S) = Shi (v ). n! Cooperative Game Theory Shapley value, potential Proposition For every game hN, v i ∈ G, P(N, v ) = X (s − 1)!(n − s)! v (S). n! S⊆N Proof. X (s − 1)!(n − s)! v (S) by Q(N, v ). Q(∅, v ) = 0. n! Denote S⊆N Q(N, v )−Q(N\{i}, v ) = X (s − 1)!(n − s)! X v (S)− n! S⊆N X S⊆N,S3i S⊆N\{i} X (s−1)!(n−s)! v (S)+ n! S⊆N\{i} (s − 1)!(n − s − 1)! v (S) = (n − 1)! X (s−1)!(n−s)! v (S)− n! S⊆N\{i} (s−1)!(n−s−1)! v (S) = (n−1)! In the first sum denote S\{i} by T , so, t = s − 1, and then change T → S and t → s. X T ⊆N\{i} X t!(n − t − 1)! v (T ∪{i})− n! S⊆N\{i} Anna Borisovna Khmelnitskaya s!(n − s − 1)! v (S) = Shi (v ). n! Cooperative Game Theory Shapley value A value ξ is marginalist if for all v ∈ GN for every i ∈ N, ξi (v ) = φi ({v (S ∪ {i}) − v (S)}S⊆N\{i} ), where φi : IR2 N−1 → IR1 . Theorem (Young, 1985) The only efficient, marginalist, and satisfying equal treatment property value defined on the class GN is the Shapley value. Remark. Efficiency + marginality + equal treatment property Anna Borisovna Khmelnitskaya =⇒ Cooperative Game Theory null-player property. Shapley value A value ξ is marginalist if for all v ∈ GN for every i ∈ N, ξi (v ) = φi ({v (S ∪ {i}) − v (S)}S⊆N\{i} ), where φi : IR2 N−1 → IR1 . Theorem (Young, 1985) The only efficient, marginalist, and satisfying equal treatment property value defined on the class GN is the Shapley value. Remark. Efficiency + marginality + equal treatment property Anna Borisovna Khmelnitskaya =⇒ Cooperative Game Theory null-player property. Shapley value A value ξ is marginalist if for all v ∈ GN for every i ∈ N, ξi (v ) = φi ({v (S ∪ {i}) − v (S)}S⊆N\{i} ), where φi : IR2 N−1 → IR1 . Theorem (Young, 1985) The only efficient, marginalist, and satisfying equal treatment property value defined on the class GN is the Shapley value. Remark. Efficiency + marginality + equal treatment property Anna Borisovna Khmelnitskaya =⇒ Cooperative Game Theory null-player property. Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (N) = v ({1, 2}) = v ({1, 3}) = 1 and v (S) = 0 for all other coalitions S ⊆ N = {1, 2, 3}. To compute the Shapley value we start with the payoff Sh1 (v ) to player 1. The coalitions S ⊆ N : S 63 1 are ∅, {2}, {3}, and {2, 3}. Then applying formula (2) we obtain Sh1 (v ) = 1 2(v ({1}) − v (∅)) + (v ({1, 2}) − v ({2})) + (v ({1, 3}) − v ({3}))+ 6  1 1 1 2 2(v ({1, 2, 3}) − v ({2, 3})) = + + 2 = . 6 6 6 3 Players 2 and 3 are substitutes =⇒ from equal treatment property, Sh2 (v ) = Sh3 (v ). From efficiency, Sh1 (v ) + Sh2 (v ) + Sh3 (v ) = v (N) =⇒ Sh2 (v ) = Sh3 (v ) = 2 1 1 =⇒ Sh(v ) = ( , , ). 3 6 6 The core C(v ) is a singleton and C(v ) = {(1, 0, 0)}. Anna Borisovna Khmelnitskaya Cooperative Game Theory 1 . 6 Shapley value Example Consider 3-person game v defined as v (∅) = 0, v (N) = 9, and for all i = 1, 2, 3, v ({i}) = i and v (N\{i}) = 4 − i. Find a strategically equivalent game w, w(S) = k v (S) + X ai , for all S ⊆ N, i∈S such that w({i}) = 0 for all i = 1, 2, 3. Let k = 1, then a1 = −1, a2 = −2, a3 = −3, and the game w is determined as w(∅) = w({i}) = 0, w(N\{i}) = −2, w(N) = 3. w is symmetric game =⇒ Shi (w) = 1, i = 1, 2, 3. Whence because of covariance of the Shapley value it follows that Sh1 (v ) = 2, Sh2 (v ) = 3, Sh3 (v ) = 4. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Example Consider 3-person game v defined as v (∅) = 0, v (N) = 9, and for all i = 1, 2, 3, v ({i}) = i and v (N\{i}) = 4 − i. Find a strategically equivalent game w, w(S) = k v (S) + X ai , for all S ⊆ N, i∈S such that w({i}) = 0 for all i = 1, 2, 3. Let k = 1, then a1 = −1, a2 = −2, a3 = −3, and the game w is determined as w(∅) = w({i}) = 0, w(N\{i}) = −2, w(N) = 3. w is symmetric game =⇒ Shi (w) = 1, i = 1, 2, 3. Whence because of covariance of the Shapley value it follows that Sh1 (v ) = 2, Sh2 (v ) = 3, Sh3 (v ) = 4. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Example Consider 3-person game v defined as v (∅) = 0, v (N) = 9, and for all i = 1, 2, 3, v ({i}) = i and v (N\{i}) = 4 − i. Find a strategically equivalent game w, w(S) = k v (S) + X ai , for all S ⊆ N, i∈S such that w({i}) = 0 for all i = 1, 2, 3. Let k = 1, then a1 = −1, a2 = −2, a3 = −3, and the game w is determined as w(∅) = w({i}) = 0, w(N\{i}) = −2, w(N) = 3. w is symmetric game =⇒ Shi (w) = 1, i = 1, 2, 3. Whence because of covariance of the Shapley value it follows that Sh1 (v ) = 2, Sh2 (v ) = 3, Sh3 (v ) = 4. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Example Consider 3-person game v defined as v (∅) = 0, v (N) = 9, and for all i = 1, 2, 3, v ({i}) = i and v (N\{i}) = 4 − i. Find a strategically equivalent game w, w(S) = k v (S) + X ai , for all S ⊆ N, i∈S such that w({i}) = 0 for all i = 1, 2, 3. Let k = 1, then a1 = −1, a2 = −2, a3 = −3, and the game w is determined as w(∅) = w({i}) = 0, w(N\{i}) = −2, w(N) = 3. w is symmetric game =⇒ Shi (w) = 1, i = 1, 2, 3. Whence because of covariance of the Shapley value it follows that Sh1 (v ) = 2, Sh2 (v ) = 3, Sh3 (v ) = 4. Anna Borisovna Khmelnitskaya Cooperative Game Theory Shapley value Example Consider 3-person game v defined as v (∅) = 0, v (N) = 9, and for all i = 1, 2, 3, v ({i}) = i and v (N\{i}) = 4 − i. Find a strategically equivalent game w, w(S) = k v (S) + X ai , for all S ⊆ N, i∈S such that w({i}) = 0 for all i = 1, 2, 3. Let k = 1, then a1 = −1, a2 = −2, a3 = −3, and the game w is determined as w(∅) = w({i}) = 0, w(N\{i}) = −2, w(N) = 3. w is symmetric game =⇒ Shi (w) = 1, i = 1, 2, 3. Whence because of covariance of the Shapley value it follows that Sh1 (v ) = 2, Sh2 (v ) = 3, Sh3 (v ) = 4. Anna Borisovna Khmelnitskaya Cooperative Game Theory A land corn production economy Consider a corn production economy with n + 1 agents: one landowner, agent 0, and several landless identical peasants, agents 1, 2, ..., n, i.e., N = {0, 1, ..., n} and |N| = n + 1. The landowner cannot produce anything by himself. The monetary value of the crop of the land depends on the number of hired peasants. Let nondecreasing function f : {0, 1, ..., n} → IR with f (0) = 0 denote the total revenue function, i.e., f (k ) represents the monetary value of the production level achieved by hiring k peasants. The corresponding TU game is given by  0, v (S) = f (s − 1), S3 6 0, S 3 0, for all S ⊆ N, in particular, v (N) = f (n) and v ({i}) = 0 for all i ∈ N. Anna Borisovna Khmelnitskaya Cooperative Game Theory A land corn production economy Shapley value All orderings of players 0, 1, ..., n are uniformly distributed. =⇒ in any random ordering of players the landowner 0 is at k th position, 1 and his marginal contribution is equal to f (k −1) k = 1, ..., n + 1, with probability n+1 because (k −1) peasants are before him. =⇒ Sh0 (v ) = n+1 n 1 X 1 X f (k − 1) = f (k ). n+1 n+1 k =1 k =1 All peasants i = 1, ..., n are identical =⇒ Shi (v ) = n 1 1 X f (k )), (f (n) − n n+1 for all i = 1, ..., n. k =1 Anna Borisovna Khmelnitskaya Cooperative Game Theory A land corn production economy Shapley value All orderings of players 0, 1, ..., n are uniformly distributed. =⇒ in any random ordering of players the landowner 0 is at k th position, 1 and his marginal contribution is equal to f (k −1) k = 1, ..., n + 1, with probability n+1 because (k −1) peasants are before him. =⇒ Sh0 (v ) = n+1 n 1 X 1 X f (k − 1) = f (k ). n+1 n+1 k =1 k =1 All peasants i = 1, ..., n are identical =⇒ Shi (v ) = n 1 X 1 f (k )), (f (n) − n n+1 for all i = 1, ..., n. k =1 Anna Borisovna Khmelnitskaya Cooperative Game Theory