Coalition Structures in Weighted Voting Games
Authors: Edith Elkind, Georgios Chalkiadakis, Nicholas R. Jennings
Abstract:
Weighted voting games are a popular model of collaboration
in multiagent systems. In such games, each agent has
a weight (intuitively corresponding to resources he can contribute),
and a coalition of agents wins if its total
weight meets or exceeds a given threshold.
Even though coalitional stability in such games is
important, existing research %in this area
has nonetheless only considered the stability of the grand coalition.
In this paper, we introduce a model for weighted voting games
with coalition structures. This is a natural extension in
the context of multiagent systems, as
several groups of agents may be simultaneously at work, each serving a
different task.
We then proceed to study stability in this context.
First, we define the CS-core, a notion of the core for such settings,
discuss its non-emptiness, and
relate it to the traditional notion of the core in weighted voting games.
We then investigate its computational properties.
We show that, in contrast with the traditional setting, it
is computationally hard to decide whether a game has a non-empty CS-core,
or whether a given outcome is in the CS-core.
However, we then provide an efficient algorithm that
verifies whether an outcome is in the CS-core if all weights
are small (polynomially bounded).
Finally, we also suggest heuristic algorithms for checking
the non-emptiness of the CS-core.