- Tytuł:
-
Anytime coalition structure generation in Multi-Agent Systems with positive or negative externalities
Generowanie struktur koalicyjnych w systemach wieloagentowych z pozytywnymi lub negatywnymi efektami zewnętrznymi - Autorzy:
-
Rahwan, T.
Michalak, T.
Wooldridge, M.
Jennings, N. R. - Powiązania:
- https://bibliotekanauki.pl/articles/91495.pdf
- Data publikacji:
- 2011
- Wydawca:
- Warszawska Wyższa Szkoła Informatyki
- Tematy:
-
multi-agent system
Function Games
Coalition Structure Generation
CSG
system wieloagentowy
gry koalicyjne
Generowanie Optymalnej Struktury Koalicyjnej - Opis:
-
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. - Źródło:
-
Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki; 2011, 5, 6; 20-59
1896-396X
2082-8349 - Pojawia się w:
- Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
- Dostawca treści:
- Biblioteka Nauki
Artykuł