Much of the literature on multi-agent coalition formation has focused on Characteristic
Function Games, where the effectiveness of a coalition is not affected by how the other
agents are arranged in the system. 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 optimised. 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), and 0.5% of that
needed by Dang and Jennings (2004). This is despite the fact that the other algorithms take
advantage of the special properties of games with no externalities, while ours does not.
Większość literatury poświęconej formowaniu koalicji w systemach wieloagentowych poświęcona
jest funkcji charakterystycznej w teorii gier, gdzie na skuteczność danej koalicji nie rzutuje
to, w jaki sposób pozostali agenci rozlokowani są w systemie. Niewiele uwagi poświęca się
natomiast bardziej ogólnej grupie gier o sumie statystycznej, gdzie nacisk kładzie się na to, jak
stworzenie jednej koalicji może wpłynąć na wyniki innych, współistniejących koalicji w ramach
danego systemu. Takie międzykoalicyjne zależności, zwane efektami zewnętrznymi przy tworzeniu
koalicji, odgrywają istotną rolę w rzeczywistych, wieloagentowych aplikacjach, i to zarówno
w przypadku, gdy agenci mają nakładające się, jak i sprzeczne ze sobą cele.
Mając powyższe na uwadze, artykuł ten jest pierwszym badaniem obliczeniowym dotyczącym
gier koalicyjnych biorącym pod uwagę efekty zewnętrzne w kontekście systemów wieloagentowych.
Autorzy artykułu skupiają się na Problemie Generowania Optymalnej Struktury
Koalicyjnej, który związany jest ze znalezieniem wyczerpującego i rozłącznego podziału agentów
na koalicje, i który to podział pozwoli na optymalizację wydajności całego systemu. Problem ten
i bez efektów zewnętrznych jest ogromnym wyzwaniem (ze względu na wykładniczy rozmiar przestrzeni
poszukiwań), a branie pod uwagę efektów zewnętrznych jest jeszcze trudniejsze, ponieważ
rozmiar danych wejściowych przy n-agentach rośnie od O(2n) do O(nn). Głównym wkładem autorów
artykułu jest wypracowanie pierwszego algorytmu do Generowania Optymalnej Struktury Koalicyjnej
dla gier koalicyjnych z pozytywnymi lub negatywnymi efektami zewnętrznymi. Autorzy
udowadniają głównie to, że możliwe jest obliczenie górnych i dolnych granic wartości jakiegokolwiek
zbioru koalicji rozłącznych. Opierając się na tym dowodzą, że po to, by ustalić najgorszą gwarancję
jakości rozwiązania konieczne jest poszukiwanie określonego zbioru struktur koalicyjnych
(zdefiniowanego przez badaczy wcześniej). Autorzy artykułu pokazują, w jaki sposób stopniowo
polepszyć tę gwarancję dalszymi poszukiwaniami. W przeszłości nie było żadnych algorytmów do
Generowania Optymalnej Struktury Koalicyjnej dla gier koalicyjnych z efektami zewnętrznymi,
autorzy odnoszą się więc do innych nowoczesnych podejść do gier, gdzie nie ma żadnych efektów
zewnętrznych. Zadziwiające jest to, że w przypadku najgorszych gwarancji, algorytm stworzony
przez autorów wyprzedza inne o rzędy wielkości. Dla przykładu, by osiągnąć związek 3 w przypadku
24 agentów, liczba struktur koalicyjnych, którą należy przeszukać przez algorytm autorów artykułu
wynosi jedynie 0:0007% tego, co poprzez algorytm wypracowany przez Sandholma i innych
(1999) oraz 0:5% tego, co poprzez algorytm Danga and Jenningsa (2004). Dzieje się tak, pomimo że
inne algorytmy korzystają ze szczególnych właściwości gier bez efektów zewnętrznych, a których
algorytm autorów artykułu nie wykorzystuje.
