Information Technology Reference
In-Depth Information
a specified
quota
is called a
winning coalition
. The weights of agents in a game cor-
respond to resources or skills available to the agents, while the quota is the amount of
resources or skills required for a task to be accomplished. For example, in
search and
rescue
, robotic agents put their resources (i.e., weights) together in large natural disaster
environments to reach the necessary levels (i.e., quota) to save life and property.
The relative power of each agent reflects its significance in the elicitation of a win-
ning coalition. A widely accepted method for measuring such relative power in WVGs
uses
power indices
. Two prominent power indices for measuring power are the
Shapley-
Shubik
[23] and the
Banzhaf
[6] power indices. WVGs can be viewed as a form of com-
petition among agents to share the available
fixed
power whose total value is always
assumed to be
1
. Agents may thus resort to manipulation by annexation or merging to
improve their influence in anticipation of gaining more power. With the possibility of
manipulation, it becomes difficult to establish or maintain trust, and more importantly,
it becomes difficult to assure fairness in such games.
This paper continues the work of [2,13,18,19] on annexation and merging in WVGs.
We first extend the framework of [18] on susceptibility of power indices to manipula-
tion by annexation and merging in WVGs to consider a
much improved
power gain for
manipulators. Then, we propose and evaluate heuristics that manipulating agents may
employ to engage in such manipulations using the two power indices. Consider a WVG
of
n
agents. The simulation of [18] is based on a
random
approach where some agents,
say
k<n
, in the game are randomly selected to be assimilated in annexation or to form
a voluntary bloc of manipulators in merging. This simple random approach shows that,
on average, annexation can be effective for manipulators using the two power indices to
compute agents' power. These results also show that merging only has a minor effect on
the power gained for manipulators using the Shapley-Shubik index, while it is typically
non-beneficial (i.e., no power is gained) for manipulators using the Banzhaf index.
Restricting the number of agents in the blocs of assimilation or merging as employed
in the simple random simulation of [18], we show that manipulators need to do only a
polynomial
amount of work to find a much improved power gain over the random ap-
proach during manipulation. Given that the problem of computing the Shapley-Shubik
and Banzhaf indices of agents is already NP-hard [21,22],
pseudopolynomial
or approx-
imation algorithms [7,9,21] are available to compute agents' power. We then present
two pseudopolynomial-time enumeration algorithms that manipulators may use to find
a much improved power gain. We empirically evaluate our enumeration approach for
manipulation by annexation and merging in WVGs. Our method is shown to achieve
significant improvement in benefits over previous work for manipulating agents in sev-
eral numerical experiments. Thus, unlike the simple random simulation of [18] where
merging has little or no benefits for manipulators using the two power indices, results
from our experiments suggest that manipulation via merging can be
highly
effective.
The remainder of the paper is organized as follows. Section 2 provides some pre-
liminaries. In Section 3, we provide visual illustrations of manipulation in WVGs to
give some insights into why it is difficult to predict how to merge. We present our
pseudopolynomial-time manipulation algorithms for annexation and merging in Section
4. Section 5 presents results of evaluation of the manipulation algorithms. In Sections
