The Shapley Value

From Theory

Jump to: navigation, search

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

Scribe: Liam Mac Dermed

Lecturer: Yair Tauman


Preview: The Shapley Value is the center of mass of the core.

[edit]

The Shapley Value

(Shapley 1953)

A value of V is \varphi (V) = (\varphi_1 V, ... \varphi_n V) where \varphi_i V is the value of player i in game V.

Axiom 1: Efficiency - \sum_{i\in N} (\varphi_i V) = V(N)
Axiom 2: Symmetry - Two players i and j are symetric if V(S + i) = V(S + j) for all S\subseteq N_{-\{i,j\}}. Then \varphi_i V = \varphi_j V if i and j are symmetric.
Axiom 3: Null (or Dummy) Player- A player i is a null player if V(S+i) = V(S) \forall S\in N. Then \varphi_i V=0 if i is a null player.
Axiom 4: Consistency - \varphi (V+W) = \varphi V + \varphi W for 2 games V and W played simultaneously.


Theorem: There exists a unique value \varphi that satisfies axioms 1-4.

Let R be an order of the players. There are N! orders of players in N. Let P_i^R be the set of players in N which precede i in the order R.

The marginal contribution of i in R is MC_i^R = V(P_i^R + i) - V(P_i^R).


The Shapely value is the expectation of the marginal value given random order.


Shapley value \varphi_i V = 1/N! \sum_R [V(P_i^R + i) - V(P_i^R)]


[edit]

Example 1

Back to the left and right gloves. N={1,2,3} where players 1 and 2 have left gloves and player 3 has a right glove.

RMC
1,2,3V(1) - V(\emptyset) = 0
1,3,2V(1) - V(\emptyset) = 0-0 = 0
2,1,3V(1,2) − V(2) = 0 − 0 = 0
2,3,1V(1,2,3) − V(2,3) = 1 − 1 = 0
3,1,2V(1,3) − V(3) = 1 − 0 = 1
3,2,1V(1,2,3) − V(2,3) = 1 − 1 = 0

so \varphi_1 V = 1/6 and likewise player 2 gets 1/6 and player 3 gets 2/3.


[edit]

Example 2

N = {1,2,3,4,5} Weighted majority game with player 1 having 1/3 voting power while players 2,3,4,and 5 have only 1/6 voting power.

player: 1 2 3 4 5
W = 1/3 1/6 1/6 1/6 1/6


To find \varphi_1 V we can look at each position that player 1 could end up in R. Calculate the value of the coalition before and after player 1 joins in that position and take a weighted average of those differences (based on the probability of being in that position). Because the order is random player 1 is equally likely to be in any of the 5 positions. The value of being in each position is:

position : 1 2 3 4 5
value = 0 0 1 1 0
prob = 1/5 1/5 1/5 1/5 1/5

so: so \varphi_1 V = 2/5 and players 2,3,4,and 5 must get the same value so they split the remaining 3/5 and each get 3/20.

Also see some nice notes by Eyal Winter.

The production of this material was supported in part by NSF award SES-0734780.

Retrieved from "http://wiki.cc.gatech.edu/theory/index.php/The_Shapley_Value"
Personal tools