Information Technology Reference
In-Depth Information
of the manipulators' coalitions since it is unrealistic and impractical that
all
agents in a
WVG will belong to the manipulators' coalition. This reasoning is consistent with the
assumptions of the previous work on annexation and merging [2,18] as well as coali-
tion formation [24]. We note, however, that limiting the manipulators coalitions' size
this way does not change the complexity class of the problem as finding the coalition
that yields the most improved benefit remains NP-hard.
Consider a WVG of
n
agents. Suppose the manipulators' coalitions,
S
, have a limit,
k<n
, on the size of the members of the coalitions, i.e.,
S
, are bounded as
2
|≤
k
. In this case, the number of coalitions that the manipulators need to examine is at most
O
(
n
k
)
which is polynomial in
n
. Specifically, the total number of these coalitions is:
≤|
S
n
2
+
n
3
+
+
n
k
=
n
j
.
k
···
(3)
j
=2
So, we have
n
j
=
k
k
n
(
n
−
1)
···
(
n
−
j
+1)
j
!
j
=2
j
=2
k
n
j
j
!
≤
j
=2
k
n
j
2
j−
1
≤
j
=2
=
n
2
2
1
+
n
3
n
k
2
k−
1
=
O
(
n
k
)
.
2
2
+
···
+
Running
GetMergeBenefit
(
G, S
)
while updating the most
1
improved benefit found so
far from each of these coalitions requires a total running time of
O
(
n
k
·
A
(
G
))
which
is pseudopolynomial, and thus becomes reasonable to compute.
4.3
Manipulation Algorithm for Annexation
Our pseudopolynomial manipulation algorithm for annexation provides a modification
of the merging algorithm. We first replace
GetMergeBenefit
(
G, S
)
with another pro-
cedure,
GetAnnexationBenefit
(
G, i, S
)
.
GetAnnexationBenefit
(
G, i, S
)
accepts a WVG
G
, an annexer,
i
, and a coalition
S
to be assimilated by
i
. The procedure then returns
the factor of increment of the assimilated bloc
&(
S
)
.
We u s e
GetAnnexationBenefit
(
G, i, S
)
to construct an algorithm that the annexer can
use to determine the coalition that yields the most improved benefit in annexation. The
∪{
i
}
1
We refer to the most improved benefit among the
O
(
n
k
)
polynomial coalitions and not from
n
coalitions since we have restricted each manipulators' coalition size to a con-
the original
2
stant
k<n
.