Tech Reports

ULCS-10-005

Tackling the Computational Complexity of Understanding Coalition Formation in Multi-Agent Systems (PhD Thesis)

Andrew Dowell

Abstract

In its simplest metaphor, agent based computation is that undertaken via the interactions of autonomous computational entities (from [39]). Often, these interactions are cooperative and, in this context, a coalition describes any group of agents who may cooperate together. In any multi-agent system, to understand which coalitions will be formed by the agents, the system can be represented as a cooperative game and solution concepts from game theory can be employed. In particular, a coalition is core stable if no agent that belongs to this coalition can gain from forming another coalition instead. On the other hand, an optimal coalition structure consists of an exhaustive and disjoint collection of coalitions of agents that maximizes the welfare of the system. Given any coalition formation protocol, it is assumed that self-interested agents will always form core stable coalitions whereas fully cooperative agents will always partition themselves into an optimal coalition structure.

In a cooperative game representation, when the value obtained from forming every coalition is explicitly stated, existing research has shown that no algorithm is guaranteed to solve decision problems concerning the core and optimal coalition structure concepts with time complexity that is polynomial in the number of agents. Given this background, the research presented in this thesis aims to tackle this complexity by presenting:

• (a) Algorithms that can compute these problems as efficiently as possible; and,
• (b) Representations of cooperative games that can permit efficient computation of these problems.

With regard to point (a), the computational difficulties with generating an optimal coalition structure arise, in part, from the fact that the number of coalition structures grows exponentially in the number of agents. To this end, in this thesis, two optimal coalition structure generation algorithms are presented - each with the aim of efficiently generating an optimal coalition structure through analyzing only a fraction of all possible coalition structures. These algorithms develop upon the contributions of previous algorithms by considering both externalities from coalition formation and coalition value calculation processes.

In addition, with regard to point (b), existing research has shown that the complexity of computing if a given coalition belongs to the core of a game is polynomial in the size of the game itself. However, because the number of coalitions grows exponentially in the number of agents, the general representation will have size that is exponential in the number of agents. Thus, from a computational perspective, this is not positive. Given this insight, this thesis also contributes to the state-of-the-art understanding of multi-agent systems through developing a concise representation of coalition formation between self-interested agents. For certain, natural instances of this representation, a system user is able to solve problems concerning core stability with time complexity that is polynomial in the number of agents.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.