Information Technology Reference
In-Depth Information
2
The Shapley Value and Its Uncertainty
We begin by introducing coalition games and then define the weighted voting game.
Coalition games are of two types ([7]): those with
transferable payoff
and those with
non-transferable payoff
. A coalition game with transferable payoff,
N, v
, consists of
a finite set (
N
=
) of players and a function (
v
) that associates with every
non-empty subset
S
of
N
(i.e., a
coalition
) a real number
v
(
S
) (the worth of
S
).
For each coalition
S
, the number
v
(
S
) is the total payoff that is available for division
among the members of
S
(i.e., the set of joint actions that coalition
S
can take consists
of all possible divisions of
v
(
S
) among the members of
S
). Coalition games with non-
transferable payoffs differ from ones with transferable payoffs in the following way.
For the former, each coalition is associated with a
set
of payoff vectors that is not
necessarily the set of all possible divisions of some fixed amount. In this paper, we
focus on the Shapley value for a game with transferable payoffs.
Let
{
1
,
2
,...,n
}
2
N−{i}
be a random variable that takes its
S
denote the set
N
−{
i
}
and
f
i
:
S→
values in the set of all subsets of
N
−{
i
}
, and has the probability distribution function
(
g
)definedas:
=
|
S
|
!(
n
−|
S
|−
1)!
g
{
f
i
(
S
)=
S
}
n
!
The random variable
f
i
is interpreted as the random choice of a coalition that player
i
joins. A player's Shapley value [13] is defined in terms of its
marginal contribution
.
The marginal contribution of player
i
to coalition
S
with
i/
∈
S
is a function
Δ
i
v
that
acts in the following way:
Δ
i
v
(
S
)=
v
(
S
∪{
i
}
)
−
v
(
S
)
Definition 1.
The Shapley value (
ϕ
i
) of the game
for player
i
is the expectation
(
E
) of its marginal contribution to a coalition that is chosen randomly, i.e.,
ϕ
i
(
N, v
)=
E
N, v
f
i
}
The Shapley value is interpreted as follows. Suppose that all the players are arranged in
some order, all orderings being equally likely. Then
ϕ
i
(
N, v
) is the
expected marginal
contribution
, over all orderings, of player
i
to the set of players who precede him. The
uncertainty
of the Shapley value, is defined as follows [4]:
Definition 2.
The uncertainty (
β
i
) for player
i
is the variance (
Var
) of its marginal
contribution. Thus
β
i
(
N, v
)=
Var
{
Δ
i
v
◦
f
i
}
Thus, while a player's Shapley value is the expectation (i.e., the mean), its uncertainty
is the variance (i.e., the square of the standard deviation) of its marginal contribution.
In other words, the uncertainty is the expectation of the squared difference between the
actual and expected marginal contributions.
The utility of a player that is not neutral to strategic risk depends on both its Shapley
value and the associated uncertainty. Furthermore, such a player's utility function is
subjective and different players may have different functions for the same game. But
for a given game, the relation between the Shapley value and its uncertainty is not
subjective to player preferences and is the same for all players. We therefore analyse
this relation for the voting game described in Section 3.
{
Δ
i
v
◦
