Information Technology Reference
In-Depth Information
Note that for each player, uncertainty (in Equations 4, 5, 8, and 9) has the same
relation with Shapley value as that for Equation 1. Therefore, the plot in Figure 1 ap-
plies to Equations 4, 5, 8, and 9 as well. Thus, for the voting game with a single
large player, each player's uncertainty first increases as its Shapley value increases. A
player's uncertainty is at a maximum when its Shapley value is 1
/
2.AstheShapley
value increases further, uncertainty decreases.
6
Multiple Large and Multiple Small Parties
Consider a parliament in which there are
m
parties. The set of parties consists of
km
large parties and (1
1. As before, each large party
has
j
seats and each small one has one seat. The total seats in a coalition of size
m
is
mkj
+(1
−
k
)
m
small parties where 0
≤
k
≤
k
)
m
. Thus, in a given population of players, the proportion of large players
is
k
. Here, the quota (
q
) satisfies the constraint (
j
+1)
−
≤
q
≤
(
kmj
+(1
−
k
)
m
−
1).
As before, the lower and upper limits for
j
are 2 and (
q
1) respectively. Finally, the
value of a coalition is one if it has
q
or more seats, otherwise it is zero.
−
A Randomised Method for the Shapley Value.
In order to determine a player's Shap-
ley value, we consider a sample from the above defined population of players. Let this
sample be a large random coalition of size
X
.Let
k
denote the proportion of large play-
ers in this sample. Irrespective of how the population is distributed, the proportion of
large players in a sample of size
X
is distributed approximately
normally
, with mean
μ
=
k
and variance
ν
=
k
(1
−
k
)
/X
(see [2] p435), i.e., we have:
(
k,
k
(1
−
k
)
k
∼N
)
(10)
X
On the basis of Equation 10, we obtain the Shapley value as follows. Consider a large
party. The marginal contribution of this party to the random sample is one if the weight
of the sample is less than the quota (
q
) but is greater than or equal to (
q
j
).Otherwise,
its marginal contribution is zero. We know that the mean weight of the sample is
kXj
+
(1
−
k
)
X
.Let
a
denote the proportion of large players that is required for the random
sample to have mean weight (
q
−
1))). Also, let
b
denote the proportion of large players that is required for the random sample to have
mean weight (
q
−
j
) (i.e.,
a
=(
q
−
j
−
X
)
/
(
X
(
j
−
−
) (where
is an infinitesimally small positive number) (i.e.,
b
=
(
q
−
X
−
)
/
(
X
(
j
−
1))). The expected marginal contribution of a large player to
the random sample is the area under the curve defined by the normal distribution of
Equation 10 between the limits
a
and
b
, i.e.,
b
1
(2
πν
)
(
x−μ
)
2
2
ν
Δ
l
=
e
−
dx
(11)
a
Therefore, a large player's Shapley value is:
m
1
m
Δ
l
ϕ
l
=
(12)
X
=1
and its uncertainty is:
