Information Technology Reference
In-Depth Information
Manipulation of Weighted Voting Games
via Annexation and Merging
Ramoni O. Lasisi and Vicki H. Allan
Department of Computer Science, Utah State University, UT 84322-4205, Logan, U.S.A.
ramoni.lasisi@aggiemail.usu.edu, vicki.allan@usu.edu
Abstract.
We conduct an experimental study of the effects of
manipulations
(i.e., dishonest behaviors) including those of manipulation by
annexation
and
merging
in weighted voting games. These manipulations involve an agent or
agents misrepresenting their identities in anticipation of gaining more power at
the expense of other agents in a game. Using the well-known Shapley-Shubik
and Banzhaf power indices, we first show that manipulators need to do only
a polynomial amount of work to find a much improved power gain, and then
present two enumeration-based pseudopolynomial algorithms that manipulators
can use. Furthermore, we provide a careful investigation of heuristics for annex-
ation which provide huge savings in computational efforts over the enumeration-
based method. The benefits achievable by manipulating agents using these
heuristics also compare with those of the enumeration-based method which serves
as upper bound.
Keywords:
Agents, Weighted voting games, Annexation, Merging, Power in-
dices.
1
Introduction
False-name manipulation
in
weighted voting games
(WVGs), which involves an agent
or some agents misrepresenting their identities in anticipation of power increase, has
been identified as a problem. The menace can take different forms. With manipulation
by
annexation
, an agent, termed, an
annexer
, takes over the voting weights of some
agents in a game. Power is not shared with the annexed agents. Forming an
alliance
or
manipulation by
merging
involves voluntary merging of weights by two or more agents
to form a single bloc [2,13,18]. Merged agents expect to be compensated with their
share of the power gained by the bloc. The agents whose voting weights are taken over
or merged into a bloc are referred to as
assimilated
agents. The only difference between
merging and annexation is that, in merging, the assimilated agents must be compensated
for their participation by sharing of the power, while in annexation, only the annexer is
compensated for the participation of the group. Annexed agents are assumed to either
voluntary forfeit their weight or be compensated on a one-time basis that is not related
to power. Thus, power increase is much easier to achieve with annexation.
WVGs are classic cooperative games which provide compact representation for coali-
tion formation models in human societies and multiagent systems. Each agent in a WVG
has an associated weight. A subset of agents whose total weight is at least the value of
