Information Technology Reference
In-Depth Information
q=100
q=150
q=200
0.25
0.2
0.15
0.1
0.05
200
0
100
1
0.8
0.6
0.4
0.2
0
0
Shapley value
Weight
Fig. 9.
Shapley value and uncertainty for a game of 50 players and a varying weight
q=300
q=350
q=400
0.25
0.2
0.15
0.1
0.05
400
0
200
Weight
1
0.8
0.6
0.4
0.2
0
0
Shapley value
Fig. 10.
Shapley value and uncertainty for a game of 100 players and a varying weight
To sum up, our study provides a basis for agents to compare games on the basis of
both their Shapley values and the associated uncertainties. We showed that a player's
uncertainty first increases with its Shapley value and then decreases. This implies that
the uncertainty is at its minimum when the value is at its maximum, and that agents do
not always have to compromise value in order to reduce uncertainty. This is because, if
the Shapley value lies in the range [0
.
5
..
1], then an increase in value is associated with
a decrease in uncertainty.
8
Conclusions and Future Work
Although the Shapley value provides a unique solution that gives an indication of an
agent's power relative to that of others, it also has an element of uncertainty associated
with it. Given this, the uncertainty is an additional dimension that an agent should take
into account for evaluating its prospects of playing a game. Against this background,
this paper has analysed the relation between the Shapley value and its uncertainty for
the weighted voting game. Since the problem of determining the Shapley value is #
P
-
complete, we first presented a randomised method with polynomial time complexity.
Using this method, we computed the Shapley value and correlated it with its uncer-
tainty. Our study shows that a player's uncertainty first increases with its Shapley value
and then decreases. Although our present work provides an analysis for the case where
different players have different weights, the distribution of weights was assumed to be
