Information Technology Reference
In-Depth Information
2.3
Annexation and Merging in Weighted Voting Games
Felsenthal and Machover [13] consider a real life example of annexation where a share-
holder buys the voting shares of some other shareholders in a firm in order to use them
for her own interest. Clearly, this action allows the manipulator to possess more shares
and makes it easier for her to affect the outcomes of decisions in the firm. Yokoo et al.,
[25] have also considered false-name manipulation in open anonymous environments
which they refer to as
collusion
. Like in merging, collusion involves many agents acting
as a single agent. They have shown that the manipulation can be difficult to detect in
such environments. Thus, the increase use of online systems (such as trading systems
and peer-to-peer networks, where WVGs are also applicable) means that annexation
or merging remains an important challenge that calls for attention. We now provide a
formal definition of manipulation by annexation and merging in WVGs.
Let
G
be a WVG. Let
Φ
be either of Shapley-Shubik or Banzhaf power index. We
denote the power of an agent
i
in
G
by
Φ
i
(
G
)
. Also, consider a coalition
C
I
,we
denote by
&
C
a bloc of assimilated voters formed by agents in
C
. We say that a power
index
Φ
is
susceptible
to manipulation whenever a WVG
G
is
altered
by an agent
i
(in the case of annexation or by some agents in the case of merging) and such that
there exists a new game
G
where
Φ
i
(
G
)
>Φ
i
(
G
)
.Inotherwords,
Φ
is susceptible to
manipulation when the power of the agent in the altered game is more than its power in
the original game.
⊆
Definition 1.
Manipulation by Annexation.
Let agent
i
alter game
G
by annexing a coalition
C
(
i/
∈
C
assimilates the agents in
C
to form a bloc
&(
C
)
). We say that
Φ
is susceptible to manipulation via annexation
if there exists a new game
G
such that
Φ
&(
C∪{i}
)
(
G
)
>Φ
i
(
G
)
; the annexation is
termed
advantageous
.The
factor of increment
by which the annexer gains is given by
Φ
&(
C∪{i}
)
(
G
)
∪{
i
}
Φ
i
(
G
)
.If
Φ
&(
C∪{i}
)
(
G
)
<Φ
i
(
G
)
, then the annexation is
disadvantageous
.
We provide an example to illustrate annexation in WVG. The annexer and assimi-
lated agents are all shown in bold.
Example 1.
Annexation in Weighted Voting Game.
Let
G
=[
12
,
16
,
18
,
19
,
23
,
26
,
43
,
46
,
50;195]
be a WVG. The Banzhaf power index
of agent
1
with weight
12
is
β
1
(
G
)=0
.
026
. Suppose the agent annexes agents
3
and
4
with weights
18
and
19
respectively. An assimilated bloc of weight
49
is formed in the
new game
G
=[16
,
23
,
26
,
43
,
46
,
49
,
50;195]
. The new Banzhaf power index of the
annexer
β
6
(
G
)=0
.
177
>β
1
(
G
)
. The agent gains from the annexation and increases
its power index by a factor of
0
.
177
0
.
026
=6
.
81
.
Definition 2.
Manipulation by Merging.
Let a manipulators' coalition,
S
, alter
G
by merging into a bloc
&
S
. We say that
Φ
is susceptible to manipulation via merging if there exists a new game
G
such that
Φ
&
S
(
G
)
>
j∈S
Φ
j
(
G
)
; the merging is termed
advantageous
. The factor of increment
by which the manipulators gain is given by
j∈S
Φ
j
(
G
)
.If
Φ
&
S
(
G
)
<
j∈S
Φ
j
(
G
)
,
Φ
&
S
(
G
)
