Download File - Game Theory Polimi - Home

Power indices on cooperative games:
semivalues.
Giulia Bernardi
Politecnico di Milano
3 dicembre 2014
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
1 / 25
Cooperative game
Cooperative game
N set of players.
v : 2N → R utility function, such that v (0)
/ = 0.
Vector space given by all games on the nite set N : GN ' R2
n −1
Simple games
v is monotonic:
v (S) ≤ v (T ) if S ⊆ T
v : 2N → { 0, 1}
v (N) = 1
Giulia Bernardi
Unanimity games
For any coalition S
(
1 if S ⊆ T
uS (T ) =
0 otherwise
Indices on cooperative games
3 dicembre 2014
2 / 25
Examples
Buyers and sellers (1)
A person wants to sell his car and evaluates it a value a. There are two
potential buyers, that evaluates the car b and c , respectively. (suppose
b ≤ c and to avoid trivial game a < b ).
v (0)
/ =0
v (1) = a
v (2) = v (3) = v ({2, 3}) = 0
v ({1, 2}) = b
v ({1, 3}) = v (N) = c
Buyers and sellers (2)
There are two people selling their own cars and only one potential buyer.
v (0)
/ = v (1) = v (2) = v (3) = 0
v ({1, 3}) = v ({2, 3}) = v (N) = 1 v ({1, 2}) = 0
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
3 / 25
Examples
Bankruptcy Problem
N = {1, . . . , n} is the set of players (i.e. of creditors), c = (c1 , . . . , cn ) such
that ci is the money claimed by player i and E is the available capital; the
bankruptcy condition is E < ∑i∈N ci .
v (S) = max{0, E −
∑
ci } for every S ⊆ N.
i∈NrS
Talmud Bankruptcy Problem.
A man, who was married to three wives,
died and the kethubah (the money the groom should give to his bride) of
the rst wife was one-hundred zuz, the one of the second wife was
two-hundred zuz while the third one deserved three-hundred zuz; but the
estate was three-hundred zuz.
v (0)
/ =0
v (N) = 300
v (1) = 0
v (2) = 0
v (3) = 0
.
v ({1, 2}) = 0 v ({1, 3}) = 100 v ({2, 3}) = 200
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
4 / 25
Examples
Weighted Majority Game
Given a positive number q and non negative integers w1 , . . . , wn the game
v = [q; w1 , w2 , . . . , wn ] is dened by
(
1 if w (T ) = ∑i∈T wi ≥ q
v (T ) =
.
0 otherwise
UN Security Council 5 permanent members and 10 non permanent
members. A motion is accepted if it gets at least 9 votes, including all the
votes of the permanent members.
v = [39; 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
5 / 25
Solution
Solution
ϕ : GN → Rn s.t. ϕi (v ) is the amount given to player i in game v .
Properties:
linearity: ϕ(v + w ) = ϕ(v ) + ϕ(w ) e ϕ(λ v ) = λ ϕ(v );
positivity: if v is monotonic then ϕi (v ) ≥ 0 ∀i ;
eciency: ∑i∈N ϕi (v ) = v (N);
symmetry: for any permutation ϑ on N
ϕi (ϑ v ) = ϕϑ (i) (v )
where (ϑ v )(S) = v (ϑ (S));
dummy player: v (S ∪ {i}) = v (S) + v ({i}) for all S , then
ϕi (v ) = v ({i}).
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
6 / 25
Solution concepts
Imputation
ϕ that are ecient and individually rational, i.e.
I (v ) =
∑ ϕi (v ) = v (N) and ϕi (v ) ≥ v ({i})
i∈N
for all i ∈ N .
Core
ϕ that are ecient and coalitionally rational, i.e.
C (v ) = {ϕ :
∑ ϕi (v ) = v (N) and ∑ ϕi (v ) ≥ v (S) for all S ⊆ N}
i∈N
Giulia Bernardi
i∈S
Indices on cooperative games
3 dicembre 2014
7 / 25
Power indices
Shapley
σi (v ) =
s!(n − s − 1)!
[v (S ∪ {i}) − v (S)]
n!
S⊆Nr{i}
∑
It satises linearity, symmetry, dummy player and eciency.
Banzhaf
βi (v ) =
∑
S⊆Nr{i}
1
2n−1
[v (S ∪ {i}) − v (S)]
It satises linearity, symmetry and the dummy player property.
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
8 / 25
Examples
Talmud Bankruptcy Problem
v (0)
/ =0
v (i) = 0
v (N) = 300
.
v ({1, 2}) = 0 v ({1, 3}) = 100 v ({2, 3}) = 200
The Shapley value is
σ1 = 50
σ2 = 100
σ3 = 150
UN Security Council
v = [39; 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].
If i is a permanent member and j is a non permanent member
421
2145
53
βi (v ) =
1024
σi (v ) =
Giulia Bernardi
4
2145
21
βj (v ) =
4096
σj (v ) =
Indices on cooperative games
3 dicembre 2014
9 / 25
Examples
Senato della Repubblica
v = [161; 108, 91, 50, 20, 16, 16, 10, 10]
Party
Partito Democratico
Popolo delle Libertà
5 Stelle
Scelta Civica
Lega Nord
Misto
Grandi Autonomie
Per le Autonomie
Giulia Bernardi
% Seats
33.65
28.35
15.58
6.23
4.98
4.98
3.11
3.11
Shapley
33.8
26.19
21.42
5.24
3.33
3.33
3.33
3.33
Indices on cooperative games
Banzhaf
32.14
25.00
23.21
5.36
3.57
3.57
3.57
3.57
3 dicembre 2014
10 / 25
Probabilistic value
Proabilistic value
ϕ : GN → Rn that satisfies the following properties: linearity, positivity and
dummy player.
Theorem
ϕ is a probabilistic value i for all i ∈ N there are {pSi }S⊆Nr{i} such that
pSi ≥ 0, ∑S⊆Nr{i} pSi = 1
ϕi (v ) =
∑
pSi [v (S ∪ {i}) − v (S)].
S⊆Nr{i}
Probabilistic + eciency =⇒ quasivalue.
Probabilistic + symmetry =⇒ semivalue.
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
11 / 25
Semivalue
Semivalue
ϕ : GN → Rn linear, positive, symmetry and dummy player.
Theorem
ϕ is a semivalue
i there are {ps }s=0,...n−1 such that ps ≥ 0,
1 n−1
p
=
1
∑n−
s
s=0
s
ϕi (v ) =
∑
ps [v (S ∪ {i}) − v (S)].
S⊆Nr{i}
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
12 / 25
Other semivalues
q-binomial
φi (v ) =
q s (1 − q)n−s−1 [v (S ∪ {i}) − v (S)]
∑
S⊆Nr{i}
Regular semivalues
ps > 0 for all s = 0, . . . , n − 1.
Marginal
Dictatorial
p0 = 1
ps = 0
for all s = 1, . . . , n − 1.
Giulia Bernardi
ps = 0
pn−1 = 1
for all s = 0, . . . , n − 2.
Indices on cooperative games
3 dicembre 2014
13 / 25
Other semivalues
Modied Values
m2 is dened by the
If ϕ is a semivalue with coecients ps , the semivalue ϕm
1
coecients

ps

if s ∈ [m1 , m2 ]

2 p (n−1)
 ∑mj=m
1 j j
ps0 =



0
otherwise.
Modied Shapley:
ps0 =
1
(m2 − m1 + 1)
Modied Banzhaf:
ps0 =
Giulia Bernardi
n−1
s
1
m2
n−1
∑j=m
j
1
Indices on cooperative games
3 dicembre 2014
14 / 25
Senato della Repubblica
β = β07
β01 , β11
β02 , β12
β33 , β34 , β44
β24 , β35
β56 , β57
β66 , β67
PD
PdL
5 Stelle
Sc. Civica
Altri
32.14
25
23.21
5.357
3.571
50
50
0
0
0
37.5
25
18.75
6.25
3.125
30.0
25.0
25.0
5.0
3.75
31.05
24.74
24.21
5.263
3.684
37.5
25
18.75
6.25
3.125
50
50
0
0
0
Table: Modied Banzhaf index
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
15 / 25
Semivalues and Biology
Microarray game
Let M = (mij ) be a matrix such that mij ∈ {0, 1}. For every j dene
Sj = {i : mij = 1} and v j
(
1 if Sj ⊆ T
j
v (T ) =
0 otherwise.
The microarray game associated to M is dened as
v=
1 m j
∑v .
m j=
1
The columns represent the patients while the rows represent the genes,
that are the players of this game.
mij = 1 =⇒ the gene i is abnormally expressed in patient j ,
mij = 0 =⇒ the gene i is normally expressed in patient j
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
16 / 25
Microarray Game
Example


1 1 0 0
0 1 1 1
0 0 1 0
Giulia Bernardi
v ({1}) = v ({2}) =
1
4
v ({3}) = 0
v ({1, 2}) =
3
4
v ({1, 3}) =
v ({2, 3}) =
2
4
v (N) = 1
Indices on cooperative games
1
4
3 dicembre 2014
17 / 25
Semivalues and Biology
Shapley and Banzhaf values give dierent rankings of genes, because they
have a dierent behaviour on unanimity games.
σi (uS ) =
1
s
βi (uS ) =
1
2s−1
a-value
(
σia (uS )
=
1
sa
if i ∈ S
0
otherwise
where uS is the simple game such that uS (T ) = 1 i S ⊆ T .
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
18 / 25
Semivalues on
G
G space of all nite games
U universe of players.
v : 2U → R and there is a niteN such that ∀S ⊂ U , v (S) = v (S ∩ N).
A G - Additive games: v (S ∪ T ) = v (S) + v (T )
Semivalues on G
ϕ : G → A G that satises:
linearity;
symmetry: ϕ ◦ ϑ = ϑ ◦ ϕ for all permutation ϑ ;
monotonicity: v monotonic =⇒ ϕ(v ) monotonic;
axis projection: if v ∈ A G then ϕ(v ) = v .
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
19 / 25
Semivalues on
G
Theorem
ϕ is a semivalue on G i there is a probability distributiion ξ over (0, 1)
such that
Z
ϕi (v ) =
∑
S⊆Nr{i}
0
1
n−s−1
t (1 − t)
s
dξ (t) [v (S ∪ {i}) − v (S)]
for each game v with support N .
Unanimity Game
For any coalition S :
Giulia Bernardi
(
1 S ⊆T
uS (T ) =
0 otherwise
Indices on cooperative games
3 dicembre 2014
20 / 25
Generating Semivalues
Theorem
The function ϕ dened on the basis of unanimity games
(
αs
ϕiα (uS ) =
0
if i ∈ S
otherwise
and extended by linearity is a semivalue on G i α1 = 1 and the sequence
αs is completely monotonic.
A sequence {µn }∞
n=0 is completely monotonic if µn ≥ 0 and
k
k
(−1) ∆ µn = (−1) ∑ (−1)
µn+k−j ≥ 0
j
j=0
k
k
k
j
for all k, n = 0, 1, 2, . . . .
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
21 / 25
Proof
psn
n−s−1 =
∑
k=0
n−s −1
(−1)k αs+k+1
k
So we get
n−1 ∑
s=0
n−1 n
ps = 1 ⇐⇒ α1 = 1
s
psn ≥ 0 ⇐⇒ (−1)k ∆k αt ≥ 0
a-values
(
σia (uS )
=
1
sa
if i ∈ S
0
otherwise
Shapley value if a = 1.
Giulia Bernardi
q-binomial values
(
q s−1 if i ∈ S
φi (uS ) =
0
otherwise
Banzhaf value if q = 12 .
Indices on cooperative games
3 dicembre 2014
22 / 25
Not regular semivalues
Proposition
Let {µk }+∞
k=0 be a completely monotonic sequence. Then
(−1)k ∆k µn > 0
for every n, k unless the sequence is constant except at most for the rst
term.
A semivalue ϕ on G is regular i ϕ|N is a regular semivalue on GN for all
N . A semivalue that is not regular is irregular.
Irregular semivalues
The irregular semivalues are generated by α = (1, q, . . . q) for any q ∈ [0, 1]
and their weighting coecients are p n = (1 − q, 0, . . . , 0, q) for all n.
If q = 1 we nd the marginal value.
If q = 0 we nd the dictatorial value.
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
23 / 25
Generating Semivalues
A function f (x) is completely monotonic if (−1)n f (n) (x) ≥ 0, ∀n ≥ 0.
We can use completely monotonic functions to dene completely
monotonic sequences:
Theorem
Let f (x) be a completely monotonic function in [a, +∞) and let δ be any
xed positive number, then
µn = {f (a + nδ )}+∞
n=0
is a completely monotonic sequence.
a
f (x) = e x
Giulia Bernardi
c
f (x) = ln(b + )
x
Indices on cooperative games
f (x) =
1
(d + ex)γ
3 dicembre 2014
24 / 25
Bibliography
Giulia Bernardi and Roberto Lucchetti.
Generating semivalues via unanimity games.
Journal of Optimization Theory and Applications, pages 112, 2014.
Francesc Carreras and Josep Freixas.
Semivalue versatility and applications.
Annals of Operations Research, 109(1-4):343358, 2002.
Pradeep Dubey, Abraham Neyman, and Robert James Weber.
Value theory without eciency.
Mathematics of Operations Research, 6(1):122128, 1981.
Roberto Lucchetti, Paola Radrizzani, and Emanuele Munarini.
A new family of regular semivalues and applications.
International Journal of Game Theory, 40(4):655675, 2011.
Robert James Weber.
Probabilistic values for games.
The Shapley Value. Essays in Honor of Lloyd S. Shapley, 1988.
Giulia Bernardi
Indices on cooperative games
3 dicembre 2014
25 / 25

Download Report