Information Technology Reference
In-Depth Information
method of construction of the algorithm is the same as that of the manipulation algo-
rithm for merging with the exception that we add the weight of an annexer
i
to the
weight of each coalition
S
and compare the power index
Φ
&(
S∪{i}
)
(
G
)
of the assim-
ilated bloc in a new game
G
to the power index
Φ
i
(
G
)
of the annexer in the original
game
G
. The annexer examines a polynomial number of coalitions of the agents assum-
ing a limit
k<n
on the size of each coalition. Since the annexer belongs to a coalition
it annexes, the total number of coalitions examined by the annexer is:
n
+
+
n
=
n
.
k−
1
−
1
−
1
−
1
···
(4)
1
k
−
1
j
j
=1
Bounding this equation using similar approach as in Equation 3 shows that Equation
4is
O
(
n
k
)
. Thus, as before, the manipulation algorithm for annexation also runs in
pseudopolynomial time, with a total running time of
O
(
n
k
·
A
(
G
))
.
5
Evaluation of the Manipulation Algorithms
We first argue that the simple random simulation of [18] for manipulation by annexation
and merging is unintelligent. Thus, it is impractical that strategic agents would employ
such method to engage in manipulation [19]. This is because simply guessing a partic-
ular coalition from among all the exponential possible coalitions provides a rare chance
for strategic agents to benefit in both manipulation by annexation and merging. We note
also that this chance of success by the manipulators decreases as the number of agents
in a game becomes large. Now, since it is impractical to exhaustively consider all the
exponential possible coalitions, we have presented two pseudopolynomial manipulation
algorithms where we have restricted the sizes of coalitions to be considered by the ma-
nipulators to a constant
k
which is less than the number
n
of the agents in the game. Our
idea is for the manipulators to sacrifice optimality for good merging or annexation. By
doing so, the manipulation algorithms potentially bypass a lot of search. Although, the
manipulation algorithms are incomplete, nonetheless, they consider more search space
than the simple random approach, and hence, are guaranteed to find a much improved
factor of increment than the simple random simulation of [18].
We perform experiments to confirm the above hypothesis. First, we make a sim-
ple modification to the random simulation of [18] which provides manipulators with
higher average factor of increment. The modification involves the selection of the best
factor of increment from three random choices (which we refer to as the
best-of-three
method). We compare results of our enumeration-based method with those of the best-
of-three method. We randomly generate WVGs. The weights of agents in each game
are chosen such that all weights are integers and drawn from a normal distribution,
N
(
μ, σ
2
)
,where
μ
and
σ
2
are the mean and variance. We have used
μ
=50
and val-
ues of standard deviation
σ
from the set
. When creating a new game,
the quota,
q
, of the game is randomly generated such that
{
5
,
10
,...,
40
}
1
w
(
I
)
,where
w
(
I
)
is the sum of the weights of all agents in the game. The number of agents,
n
,in
each of the original WVGs is chosen uniformly at random from the set
2
w
(
I
)
<q
≤
}
while the number of assimilated agents
k
is uniformly chosen at random from the set
{
{
10
,
11
,...,
20
5
,
6
,...,
10
}
.
