Information Technology Reference
In-Depth Information
formation [9,14,12]. In this work, one of the most extensively studied solution concepts
is the
Shapley value
[13]. The Shapley value provides a
unique
solution and is therefore
used to evaluate a player's prospects of playing a game.
Although the Shapley value provides a unique solution, it has two key drawbacks.
First, for the weighted voting game that we consider, the problem of determining the
Shapley value is #
P
-complete [1]. Second, it provides the solution only with a limited
degree of certainty [11]. Thus the uncertainty in the Shapley value provides an addi-
tional dimension for evaluating a player's prospects of playing a game and a measure
of uncertainty would serve as a useful tool to investigate this aspect of a game. Charac-
terizing a game by both its value and uncertainty is like characterising a weapon by its
power and precision, or a financial stock by its expected return and risk [4].
The concept of uncertainty in the outcome of a game is not entirely new. For in-
stance, Roth showed that the Shapley value of a game equals its utility, if and only if the
underlying player preferences are neutral to both
ordinary
1
and
strategic
risk [10,11].
Otherwise, the Shapley value is not the same as utility and is therefore insufficient for
decision-making purposes. Kargin extended this concept further by introducing a mea-
sure for determining the strategic risk [4]. This measure is called the
uncertainty
of the
Shapley value and it provides a yardstick for quantifying the strategic risk. Thus, in or-
der for a player to make more informed decisions, it is important for it to not only know
its Shapley value, but also the relation between this value and its uncertainty. However,
to date, there has been no analysis of this relationship.
Given this, our objective is to analyse the relation between the Shapley value and its
uncertainty for the
voting game
(since it is an important mechanism for multiple agents
to reach consensus). However, uncertainty is defined in terms of the Shapley value (i.e.,
in order to find uncertainty, the Shapley value needs to be determined first). But, as
we pointed out, the problem of determining the Shapley value has been shown to be
#
P
-complete [1]. We therefore present a new
randomised
method (that has polynomial
time complexity) for computing the
approximate
Shapley value. Using this method, we
determine the Shapley value and correlate it with its uncertainty. Our study shows that
each 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.
To our knowledge, the only work that addresses the problem of uncertainty in the
Shapley value is [10,11,4]. While [10,11] introduces the concept of strategic risk in the
context of the Shapley value, [4] defines a measure (called uncertainty) for this risk.
Our paper therefore makes a twofold contribution. First, we present a polynomial time
method along the lines of
Monte Carlo simulation
(see Section 3 for details) for com-
puting the Shapley value for the voting game. Second, using this method we compute
the Shapley value and analyse its relation with uncertainty.
Section 2 defines the Shapley value and its uncertainty. Section 3 describes the
weighted voting game. Section 4 to Section 7 determine the relation between the Shap-
ley value and its uncertainty. Section 8 concludes.
1
Ordinary risk involves the uncertainty that arises from the chance mechanism involved in lot-
teries. On the other hand,
strategic risk
involves the uncertainty that arises as a result of inter-
action in a game of strategic players (i.e., those players that are not dummy).
