Overlapping Coalition Formation
Authors: Georgios Chalkiadakis, Edith Elkind, Vangelis Markakis, Nicholas R. Jennings
Abstract:
In multiagent domains, agents form coalitions to perform tasks.
The usual models of cooperative game theory assume that the desired outcome is either the grand
coalition
or a coalition structure that consists of disjoint coalitions (i.e., a partition of the set of
agents).
However, in practice an agent may be involved in executing more than one task, and distributing his
resources between several (not necessarily disjoint) coalitions.
To tackle such scenarios, we introduce a model for cooperative games with overlapping coalitions.
We focus on the concept of stability in this setting. We define and study a notion of the core,
which is a
generalization of the corresponding notion in the traditional models of cooperative game theory.
Under some quite general conditions, we provide a characterization for pairs of the form
(coalition structure, imputation) to be in the core.
We also show that any element of the core maximizes the social welfare.
We then introduce balancedness for overlapping coalitional games, and use this to
characterize coalition structures that can be extended to elements in the core.
Furthermore, we extend the notion of convexity to our setting, and show that under some natural
assumptions convex
games have a non-empty core.
Finally, we explore alternative definitions of allowable deviations by a set of agents, and the
corresponding notions
of stability.
This is the first paper to provide a generic model for overlapping coalition formation, along with
a theoretical
treatment of stability in this setting.