Information Technology Reference
In-Depth Information
3
The Weighted Voting Game
We adopt the definition of voting game given in [7]. There is a set of
n
players that
may, for example, represent shareholders in a company or members in a parliament.
The weighted voting game is a game
G
=
in which
v
(
S
)=
1 if
w
(
S
)
N, v
≥
q
0 otherwise
IR
+
,where
w
(
S
)=
i∈S
w
i
for any coalition
S
. Thus
w
i
is the number of votes that player
i
has and
q
is the number of votes needed to win
thegame(i.e.,the
quota
). For this game (denoted
for some
q
∈
IR
+
and
w
i
∈
q
;
w
1
,...,w
n
), a player's marginal
contribution is either zero or one.
The problem of determining the Shapley value for the weighted voting game is #
P
-
complete [1]. A problem is #
P
-hard if solving that problem is as hard as counting sat-
isfying assignments of propositional logic formulae [8, p442]. Since #
P
-completeness
thus subsumes
NP
-completeness, this implies that computing the Shapley value for the
weighted voting game will be intractable in general. To overcome this problem, two
methods have been proposed:
Monte Carlo simulation
[5] and the method of
generat-
ing functions
[6]. The former method treats the number of
swings
2
for each player as
a random variable over a given distribution and defines the Shapley value in terms of
these random variables. While this method gives the approximate Shapley value, the
generating functions method is an exact procedure. Although it is an exact procedure,
it requires very large arrays (i.e., it requires substantial storage space) and can only be
applied to games with integer weights and quotas.
The method we present is similar to that of [5] in the sense that it is an approxima-
tion method. But the difference is that while [5] defines the Shapley value by treating a
player's number of swings as a random variable, we treat the players' weights as ran-
dom variables. Since the voting game is defined in terms of the players' weights and
the number of swings are obtained from these weights, our method corresponds more
closely to the definition of the voting game. Furthermore, it does not require large ar-
rays and is therefore economical in terms of storage space. The proposed method has
polynomial time complexity. We first consider a simple voting game in which all play-
ers have equal weight. We then extend our analysis to a game with two types of players:
large
and
small
, and finally generalise it to more than two player types.
4
All Players Have Equal Weight
Consider the game
j
,then
there would be no need for players to form a coalition. On the other hand, if
q
=
mj
(
m
=
q
;
j,...,j
with
m
parties. Each party has
j
seats. If
q
≤
is the number of players), only the grand coalition is possible. Thus, the
quota (
q
) satisfies the constraint: (
j
+1)
|
N
|
1). A majority is decisive. The
value of a coalition is one if the weight of the coalition is greater than or equal to
q
,
otherwise it is zero.
2
≤
q
≤
j
(
m
−
A swing for a player
i
is a pair of coalitions (
x
,
x ∪ i
) such that
x
is losing but
x ∪ i
is winning.
