Anytime coalition structure generation in multi-agent systems with positive or negative externalities
OA Location
Author(s)
Rahwan, T
Michalak, T
Wooldridge, M
Jennings, NR
Type
Journal Article
Abstract
In contrast, very little attention has been given to the more general class of Partition Function Games, where the emphasis is on how the formation of one coalition could influence the performance of other co-existing coalitions in the system. However, these inter-coalitional dependencies, called externalities from coalition formation, play a crucial role in many real-world multi-agent applications where agents have either conflicting or overlapping goals. Against this background, this paper is the first computational study of coalitional games with externalities in the multi-agent system context. We focus on the Coalition Structure Generation (CSG) problem which involves finding an exhaustive and disjoint division of the agents into coalitions such that the performance of the entire system is optimized. While this problem is already very challenging in the absence of externalities, due to the exponential size of the search space, taking externalities into consideration makes it even more challenging as the size of the input, given n agents, grows from O(2n) to O(nn). Our main contribution is the development of the first CSG algorithm for coalitional games with either positive or negative externalities. Specifically, we prove that it is possible to compute upper and lower bounds on the values of any set of disjoint coalitions. Building upon this, we prove that in order to establish a worst-case guarantee on solution quality it is necessary to search a certain set of coalition structures (which we define). We also show how to progressively improve this guarantee with further search. Since there are no previous CSG algorithms for games with externalities, we benchmark our algorithm against other state-of-the-art approaches in games where no externalities are present. Surprisingly, we find that, as far as worst-case guarantees are concerned, our algorithm outperforms the others by orders of magnitude. For instance, to reach a bound of 3 given 24 agents, the number of coalition structures that need to be searched by our algorithm is only 0.0007% of that needed by Sandholm et al. (1999) [1], and 0.5% of that needed by Dang and Jennings (2004) [2]. This is despite the fact that the other algorithms take advantage of the special properties of games with no externalities, while ours does not.
Date Issued
2012-03-28
Date Acceptance
2012-03-17
Citation
Artificial Intelligence, 2012, 186, pp.95-122
ISSN
1872-7921
Publisher
Elsevier
Start Page
95
End Page
122
Journal / Book Title
Artificial Intelligence
Volume
186
Copyright Statement
© 2012 Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/
Identifier
http://eprints.soton.ac.uk/337180/
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science
COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
Mechanism design
Classification
Game theory
Approximation
Artificial Intelligence & Image Processing
0801 Artificial Intelligence And Image Processing
1702 Cognitive Science
Publication Status
Published