Anytime coalition structure generation in Multi-Agent Systems with positive or negative externalities

• Autorzy: Rahwan T. , Michalak T. , Wooldridge M. , Jennings N. R.

Warianty tytułu

PL

Generowanie struktur koalicyjnych w systemach wieloagentowych z pozytywnymi lub negatywnymi efektami zewnętrznymi

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

multi-agent system; Function Games; Coalition Structure Generation; CSG

PL

system wieloagentowy; gry koalicyjne; Generowanie Optymalnej Struktury Koalicyjnej

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2011
• Tom: nr 6
• Strony: 20--59
• Opis fizyczny: Bibliogr. 32 poz., rys., wykr.

Twórcy

autor

Rahwan T.

• School of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK

autor

Michalak T.

• School of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK

autor

Wooldridge M.

• School of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK

autor

Jennings N. R.

• School of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK

Bibliografia

• 1. T. W. Sandholm, K. Larson, M. Andersson, O. Shehory, F. Tohme, Coalition Structure Generation with Worst Case Guarantees, Artificial Intelligence (AIJ) 111 (1-2) (1999) 209-238.
• 2. V. D. Dang, N. R. Jennings, Generating Coalition Structures with Finite Bound from the Optimal Guarantees, in: Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 564-571, 2004.
• 3. S. Ieong, Y. Shoham, Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games, ACM EC-05 (2006) 170-179.
• 4. O. Shehory, S. Kraus, Methods for Task Allocation Via Agent Coalition Formation, Artificial Intelligence (AIJ) 101 (1-2) (1998) 165-200.
• 5. S. Sen, P. Dutta, Searching for Optimal Coalition Structures, in: Proceedings of the Sixth International Conference on Multi-Agent Systems (ICMAS-00), 286-292, 2000.
• 6. T. Rahwan, S. D. Ramchurn, A. Giovannucci, N. R. Jennings, An Anytime Algorithm for Optimal Coalition Structure Generation, Journal of Artificial Intelligence Research (JAIR) 34 (2009a) 521-567.
• 7. W. Lucas, R. Thrall, n-Person Games in Partition Function Form, Naval Res. Logist. Quart. X (1963) 281- 298.
• 8. E. Catilina, R. Feinberg, Market Power and Incentives to Form Research Consortia, Review of Industrial Organization 28 (2) (2006) 129-144.
• 9. J. Plasmans, J. Engwerda, B. van Aarle, G. D. Bartolomeo, T. Michalak, Dynamic Modelling of Monetary and Fiscal Cooperation Among Nations, Springer, New York USA, 2006.
• 10. S.-S. Yi, Endogenous Formation of Economic Coalitions: A Survey on the Partition Function Approach, in: The Endogenous Formation of Economic Coalitions, Edward Elgar, London, UK, 80-127, 2003.
• 11. M. Finus, New Developments in Coalition Theory: An Application to the Case of Global Pollution Control, in: Environmental Policy in an International Perspective, Kluwer Academic Publishers, Netherlands, 19-49, 2003.
• 12. P. Dunne, Multiagent Resource Allocation in the Presence of Externalities, in: CEEMAS, 408-417, 2005.
• 13. J. Oh, Multiagent Social Learning in Large Repeated Games (Ph.D. thesis), School of Computer Science, Carnegie Mellon University, 2009.
• 14. J. S. Rosenschein, G. Zlotkin, Rules of Encounter: Designing Conventions for Automated Negotiation among Computers, MIT Press, Massachusetts, USA, 1994.
• 15. T. P. Michalak, T. Rahwan, J. Sroka, A. Dowell, M. J. Wooldridge, P. J. McBurney, N. R. Jennings, On Representing Coalitional Games with Externalities, in: J. Chuang, L. Fortnow, P. Pu (Eds.), ACM Conference on Electronic Commerce (ACM-EC), 11-20, 2009.
• 16. R. Cornes, T. Sandler, The Theory of Externalities, Public Goods, and Club Goods, Cambridge University Press, 1996.
• 17. T. Rahwan, S. D. Ramchurn, A. Giovannucci, V. D. Dang, N. R. Jennings, Anytime Optimal Coalition Structure Generation, in: Proceedings of the Twenty Second Conference on Artificial Intelligence (AAAI), 1184-1190, 2007a.
• 18. D. Y. Yeh, A Dynamic Programming Approach to the Complete Set Partitioning Problem, BIT Numerical Mathematics 26 (4) (1986) 467-474.
• 19. M. H. Rothkopf, A. Pekec, R. M. Harstad, Computationally Manageable Combinatorial Auctions, Management Science 44 (8) (1995) 1131-1147.
• 20. T. Rahwan, N. R. Jennings, An Improved Dynamic Programming Algorithm for Coalition Structure Generation, in: Proceedings of the Seventh International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 1417-1420, 2008a.
• 21. T. Rahwan, N. R. Jennings, Coalition Structure Generation: Dynamic Programming Meets Anytime Optimisation, in: Proceedings of the Twenty Third Conference on Artificial Intelligence (AAAI), 156-161, 2008b.
• 22. T. C. Service, J. A. Adams, Approximate Coalition Structure Generation, in: Proceedings of the Twenty Fourth Conference on Artificial Intelligence (AAAI), 2010.
• 23. T. C. Service, J. A. Adams, Constant Factor Approximation Algorithms for Coalition Structure Generation, Autonomous Agents and Multi-Agent Systems 23 (1) (2011) 1-17.
• 24. N. Ohta, V. Conitzer, R. Ichimura, Y. Sakurai, A. Iwasaki, M. Yokoo, Coalition Structure Generation Utilizing Compact Characteristic Function Representations, in: I. P. Gent (Ed.), CP, vol. 5732 of Lecture Notes in Computer Science, Springer, ISBN 978-3-642-04243-0, 623-638, 2009.
• 25. T. Rahwan, T. P. Michalak, E. Elkind, P. Faliszewski, J. Sroka, M. Wooldridge, N. R. Jennings, Constrained Coalition Formation, in: Twenty Fifth AAAI Conference on Artificial Intelligence (AAAI), 719-725, 2011.
• 26. S. Ueda, M. Kitaki, A. Iwasaki, M. Yokoo, Concise Characteristic Function Representations in Coalitional Games Based on Agent Types, in: IJCAI’11: Twenty Second International Joint Conference on Artificial Intelligence, 393-399, 2011.
• 27. T. Rahwan, S. D. Ramchurn, V. D. Dang, N. R. Jennings, Near-Optimal Anytime Coalition Structure Generation, in: Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI), 2365-2371, 2007b.
• 28. S. S. Skiena, The Algorithm Design Manual, Springer-Verlag, New York, USA, 1998.
• 29. W. Riha, K. R. James, Algorithm 29 Efficient Algorithms for Doubly and Multiply Restricted Partitions, Journal of Computing 16 (1974) 163-168.
• 30. K. Larson, T. Sandholm, Anytime Coalition Structure Generation: an Average Case Study, Journal of Experimental and Theoretical Artificial Intelligence 12 (1) (2000) 23-42.
• 31. B. Banerjee, K. Landon, Coalition Structure Generation in Multi-Agent Systems with Mixed Externalities, in: Proceedings of the Ninth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 175-182, 2010.
• 32. T. Rahwan, T. Michalak, N. R. Jennings, M. Wooldridge, P. McBurney, Coalition Structure Generation in Multi-Agent Systems with Positive and Negative Externalities, in: Proceedings of the Twenty First International Joint Conference on Artificial Intelligence (IJCAI), Pasadena, USA, 2009b.

Uwagi

Publikacja opracowana w ramach projektu „Program rozwoju oferty dydaktycznej i podnoszenia kompetencji wykładowców w Warszawskiej Wyższej Szkole Informatyki”.