17 April 2009, Computational Social Choice Seminar, Vangelis Markakis

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 study a model for cooperative games with overlapping coalitions. We then focus on concepts of stability in this setting. In particular, 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 then introduce a concept of balancedness for overlapping coalitional games, and use it to characterize coalition structures that can be extended to elements of the core. Furthermore, we generalize the notion of convexity to our setting, and show that 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.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle at illc.uva.nl).