Information Technology Reference
In-Depth Information
Fig. 3.
Manipulation by annexation where Agent
1
assimilates Agent
3
(from Figure 1). The new
power indices of Agent
1
as computed by Shapley-Shubik index after the annexation for various
values of the quota is also shown.
programming [7,9,21]. Given that the problem of computing the two indices is already
NP-hard, and only pseudopolynomial or approximation algorithms are available to com-
pute agents' power, it is reasonable that the manipulation algorithms we propose are also
pseudopolynomial since we necessarily need to use these indices in computing agents'
benefits during manipulation.
4.2
Manipulation Algorithm for Merging
The brute force approach to determine a coalition that yields the most improved benefit
in merging in a WVG is to simply enumerate all the possible coalitions of agents in
the game and then compute the benefit for each of these coalitions. We can then output
the coalition with the highest value. Unfortunately, enumerating all the possible coali-
tions is exponential in the number of agents. Also, computing the power indices naively
from their definitions means that we have two exponential time problems to solve. We
provide an alternative approach.
Let procedure
PowerIndex
(
G, i
)
be a pseudopolynomial algorithm for computing the
power index of an agent
i
in a WVG
G
of
n
agents for Shapley-Shubik or Banzhaf index
according to any of [7,9,21]. We first use
PowerIndex
(
G, i
)
as a subroutine in the con-
struction of a procedure,
GetMergeBenefit
(
G, S
)
. Procedure
GetMergeBenefit
(
G, S
)
accepts a WVG
G
and a would-be manipulators' coalition,
S
. It first computes the sum
of the individual power index of the assimilated agents in
S
using
PowerIndex
(
G, i
)
.
Then, it alters
G
by replacing the sum of the weights of the assimilated agents in
G
with a single weight in a new game
G
before computing the power of the bloc
&
S
in
G
. Finally,
GetMergeBenefit
(
G, S
)
returns the factor of increment of the merged bloc
&
S
.Let
A
(
G
)
be the pseudopolynomial running time of
PowerIndex
(
G, i
)
.Now,since
|
S
|≤|
I
|
=
n
, procedure
GetMergeBenefit
(
G, S
)
takes at most
O
(
n
·
A
(
G
))
time which
is pseudopolynomial.
We n ow u s e
GetMergeBenefit
(
G, S
)
to construct an algorithm that manipulators can
use to determine a coalition that yields a good benefit in merging. We first argue that
manipulators tend to prefer coalitions which are small in size because they are easier to
form and less likely to be detected. Also, intra-coalition coordination, communication,
and other overheads increase with coalition size. Thus, we suggest a limit on the size
