Introduction to Game Theory and Applications, III
Fioravante PATRONE
DIPTEM, University of Genoa
Luxembourg, June 2010
Summary
Preliminaries and the core
Preliminaries: cooperative games with transferable utility The core
The Shapley value and some applications The axioms of Shapley
Other axioms for the Shapley value Cost components
Microarray games
Cost allocation for connection problems Conclusions
Bibliography
Basic definitions
Formal definition:
▶ It is given a finite set N of players.
▶ Each group of players, that is, each coalition S ⊆ N, can obtain some amount v (S ) ∈ ℝ
▶ So, a cooperative game with transferable utility is v : 𝒫(N) → ℝ (con v (∅) = 0)
Interpretation: how do we interpret v (S )?
▶ Sum of the (transferable) utility values that players of S obtain.
▶ “Money” that S is able to obtain.
▶ S could be winning or losing. It is the case in which
v (S ) ∈ {0, 1}
Basic definitions
▶ Superadditivity
v (S ∪ T ) ≥ v (S ) + v (T ) if S and T are disjoint.
▶ Allocation
simply one element x of ℝ N .
▶ Pre-imputation
an allocation x such that ∑
i ∈N x i = v (N) (for a superadditive game it is related with efficiency).
▶ Imputation
besides being a pre-imputation, we require also individual
rationality: x i ≥ v ({i }).
The core
One easily gets the idea of core adding, to conditions for an imputation, conditions of “intermediate rationality”:
∑
i ∈S x i ≥ v (S) for all S.
Example. Simple majority game: N = {1, 2, 3}, v (S ) = 1 if
#(S ) ≥ 2, and 0 otherwise.
Easy to see that the core is empty.
Example. Glove game. N is partitioned into “L” and “R” (left and right glove owners). v (S ) = min{S ∩ L, S ∩ R} (unpaired gloves are worthless, pairs of glove have value 1).
If #R = #L + 1, there is a unique allocation in the core: “left”
owners get 1, “right” owners get 0. This is true for all values of
#L, even if #L = 10 6 .
The 4 classical axioms on 𝒮𝒢(N).
Given N, 𝒮𝒢(N) is the class of all superadditive games whose set of players is N. Or 𝒢(N) if we omit superadditivity.
We would like to have Φ : 𝒮𝒢(N) → ℝ N satisfying:
▶ Efficiency: for all games v , Φ(v ) is a pre-imputation. That is:
∑
i ∈N Φ i (v ) = v (N)
▶ Symmetry: Φ i (v ) = Φ j (v ) if, interchanging i with j , the game v does not change
▶ Null player: Φ i (v ) = 0 if the contribution of i is null.
That is, if:
v (S ∪ {i }) = v (S ) for all S
▶ Additivity: Φ(v + w ) = Φ(v ) + Φ(w )
Comments on the axioms.
Efficiency and symmetry are “obvious” conditions.
The “null player” axiom (a special case of the “dummy player”
axiom) says that Shapley value distributes the “gains” taking somehow into account the contributions of the single players.
Additivity: acceptable? Perplexities expressed by Luce and Raiffa (1957)
Mathematically, it works (the reasong can be adapted for 𝒮𝒢(N)):
▶ Unanimity games are a basis for 𝒢(N).
▶ For the unanimity games the first 3 axioms determine the Shapley value.
▶ Using additivity we extend it to all of 𝒢(N).
▶ So, the 4 axioms determine a unique solution on 𝒢(N).
Formulas for the Shapley value, I
A game v can be expressed as a linear combination of unanimity games:
v = ∑
S⊆N,S∕=∅ 𝜆 S (v )u S
So, thanks to linearity, The Shapley value can be calculated using the unanimity coefficients (𝜆 S (v )), that is:
𝜙 i (v ) = ∑
S⊆N:i ∈S
𝜆 S (v )
s (1)
for each i ∈ N.
Here, s denotes the number of elements of S , i.e., its cardinality.
The number 𝛿 S = 𝜆 s
Sis called Harsanyi dividend, relative to the
coalition S (Harsanyi, 1959).
Formulas for the Shapley value, II
Φ i (v ) = 1 n!
∑
𝜎
m 𝜎 i (v ), (2)
where 𝜎 is a permutation of N, while m 𝜎 i (v ) is the marginal contribution of player i according to the permutation 𝜎, which is defined as:
v ({𝜎(1), 𝜎(2), . . . , 𝜎(j )}) − v ({𝜎(1), 𝜎(2), . . . , 𝜎(j − 1)}), where j is the unique element of N s.t. i = 𝜎(j ).
Here is a condensed version of the formula:
Φ i (v ) = ∑
S⊆N:i ∈S
(s − 1)!(n − s)!
n! (v (S ) − v (S ∖ i )) (3)
Some warnings.
▶ The allocation provided could not be stable (outside of the core: glove game; empty core: simple majority game).
▶ Efficiency without superadditivity is a possibly stupid request.
It depends: is one ”obliged” to stay in the ”big coalition”?
▶ Axioms could not be categorical on subsets of 𝒮𝒢(N).
Example: additivity for simple games, that is: v (S ) ∈ {0, 1}.
Replace with transfer:
Φ i (v ∨ w ) + Φ i (v ∧ w ) = Φ i (v ) + Φ i (w ), ∀i ∈ N.
Other axiom systems
▶ Alvin Roth (1977) has taken seriously the idea of expected value.
▶ Peyton Young (1985) emphasizes the marginalistic roots of the Shapley value.
▶ Sergiu Hart and Andreu Mas Colell (1987) introduced the idea of consistency and of potential.
▶ Also Moretti et al. (2007) justify axiomatically the use of the
Shapley value for the microarray games.
Airport game.
Everyone pays for the components (printers, faxes, copiers, etc.) that he uses.
The costs of each component are divided evenly among its users.
Famous case: airport game.
Different types of planes need a landing strip of a different length.
Each piece of the landing strip is paid equally by all of the planes
(landings...) that use it.
Microarray experiment: results and discretization.
Shapley value for microarray games.
▶ Application of Shapley value to find which are the most relevant genes.
▶ Why Shapley value?
▶ New axiomatic characterization, which takes into account specific characteristics of the situation.
▶ Relevance of GT approach: give due emphasis to the
interactions among genes.
Experimental data.
Selection of microarray data from Alon et al. (1999) on colon cells.
Analyzed 2000 genes, and 62 samples (40 tumoral e 22 normal)
Results on the experimental data.
The five genes with the highest Shapley value:
Name of the gene Shapley value (×10 −3 )
H.sapiens mRNA for GCAP-II/ 3.83
/uroguanylin precursor
Nucleolin 3.56
Gelsolin precursor, Plasma 3.34
DNA-(Apurinic or apirymidinic site) 3.23 Lyase
Human vasoactive intestinal peptide (VIP) 3.21
Genes written in blue: it is known that are involved in cancer
processes.
Minimum cost spanning tree games.
Everyone needs to connect with a source (sink):
- irrigation system - electricity provision - sewage facility
Graph with players as nodes; each arc has a cost.
v (S ) as the cost of the MCST lying inside S.
Best (efficient) solution: minimum cost spanning tree.
An example.
1 q q 3
q 2
t S
2 1
4
12 10
8
v ({1}) = 8
v ({2}) = 12
v ({3}) = 10
v ({1, 2}) = 10
v ({1, 3}) = 12
v ({2, 3}) = 11
v ({1, 2, 3}) = 11
Minimum cost spanning tree games: solutions
Question: how to allocate costs?
- Bird rule → a element in the core (extreme element).
- use Shapley value...
Conclusions
1. Shapley value is pervasive.
2. Often (not always!) it is easy to calculate.
3. It has unanticipated applications. Not strange, given the simple and universal conditions it satisfies.
See Moretti and Patrone: Transversality of the Shapley value, about 1) and 3).
▶ Some modest suggestions
▶
Integrate various disciplines.
▶
