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 .
 
Search WWH ::




Custom Search