Information Technology Reference
In-Depth Information
6, we present heuristics for annexation in WVGs. Section 7 discusses related work and
we conclude in Section 8.
2
Preliminaries
2.1 Weighted Voting Games
Let
I
=
{
1
,
···
,n
}
be a set of
n
agents and the corresponding positive weights of the
agents be
w
=
I
be a non-empty subset of agents. A
WVG
G
with
quota
q
involving agents
I
is represented as
G
=[
w
1
,
{
w
1
,
···
,w
n
}
. Let a coalition
S
⊆
···
,w
n
;
q
]
.We
assume that
w
1
≤
w
2
≤
...
≤
w
n
. Denote by
w
(
S
)
, the weight of a coalition,
S
,
derived as the summation of the weights of agents in
S
,i.e.,
w
(
S
)=
j∈S
w
j
.A
coalition,
S
,winsingame
G
if
w
(
S
)
q
, otherwise it loses. WVGs belong to the class
of
simple voting games
. In simple voting games, each coalition,
S
, has an associated
function
v
:
S
≥
→{
0
,
1
}
.Thevalue
1
implies a win for
S
and
0
implies a loss. So,
v
(
S
)=1
if
w
(
S
)
≥
q
and
0
otherwise.
2.2 Power Indices
We provide brief descriptions of the two power indices we use in computing agents'
power in WVGs. For further discussion, we refer the reader to [12,17].
Shapley-Shubik Power Index
The Shapley-Shubik index quantifies the marginal contribution of an agent to the
grand
coalition
(i.e., a coalition of all the agents). Each permutation (or ordering) of the agents
is considered. We term an agent
pivotal
in a permutation if the agents preceding it
do not form a winning coalition, but by including this agent, a winning coalition is
formed. Shapley-Shubik index assigns power to each agent based on the proportion of
times it is pivotal in all permutations. We specify the computation of the index using no-
tation of [2]. Denote by
π
, a permutation of the agents, so
π
:
,
and by
Π
the set of all possible permutations. Denote by
S
π
(
i
)
the predecessors of agent
i
in
π
, i.e.,
S
π
(
i
)=
{
1
,...,n
}→{
1
,...,n
}
{
j
:
π
(
j
)
<π
(
i
)
}
.
The Shapley-Shubik index,
ϕ
i
(
G
)
, for each
agent
i
in a WVG
G
is
n
!
π
ϕ
i
(
G
)=
1
[
v
(
S
π
(
i
)
∪{
i
}
)
−
v
(
S
π
(
i
))]
.
(1)
∈
Π
Banzhaf Power Index
An agent
i
∈
S
is referred to as being
critical
in a winning coalition,
S
,if
w
(
S
)
≥
q
and
w
(
S
)
<q
. The Banzhaf power index computation for an agent
i
is the proportion
of times
i
is critical compared to the total number of times any agent in the game is
critical. The Banzhaf index,
β
i
(
G
)
, for each agent
i
in a WVG
G
is given by
\{
i
}
η
i
(
G
)
j∈I
η
j
(
G
)
β
i
(
G
)=
(2)
where
η
i
(
G
)
is the number of coalitions for which agent
i
is critical in
G
.
