Thèse de Redha Taguelmimt

Thesis of Redha Taguelmimt

Subject:

Optimal Coalition Structure Generation Algorithms for Multiagent Systems

Defense date: 12/01/2024

Advisor: Samir Aknine

Summary:

Coalition formation is an important mode of interaction in multiagent systems that involves grouping several agents together within different coalitions in order to efficiently achieve their individual or collective goals. Forming certain coalitions can be more valuable than others and deciding which coalitions to form typically involves evaluating multiple coalition structures. The choice of coalitions to form is of crucial importance, as it can have a major impact on the overall success of the endeavor. This is a major problem in artificial intelligence and game theory that is central to many practical applications, such as transportation, disaster response, and distributed sensor networks. A crucial challenge in coalition formation is \textit{coalition structure generation}, where agents are bundled into a coalition structure---that is, disjoint coalitions in which each agent belongs to only one coalition---in a way that maximizes social welfare.

However, this problem of generating an optimal coalition structure is exceptionally complex due to the exponential growth in the number of potential solutions as the number of involved agents increases. In this thesis, we address this problem by introducing a set of algorithms designed to provide optimal or approximate solutions.

First, we introduce new concepts and methods for the coalition structure generation problem, including offline phases that improve the efficiency of the search process. Specifically, we divide the coalition structure generation into two phases: an offline phase and an online phase, allowing automated configuration of algorithms for this problem. This is based on non-trivial results of the search space analysis that revealed that exact algorithms for this problem can be improved by automatically tuning them.

Second, we develop an algorithm that uses a new representation of the search space, which partitions the space of possible solutions into subspaces and gathers the solutions in a new way. This representation not only enables to optimize the evaluation of coalition structures but also enables to eliminate the redundant processing of common coalition structures, resulting in a significant reduction in computational time.

Furthermore, we develop several methods to tackle large-scale instances of this problem. Specifically, we develop two heuristic algorithms based on a new representation of the search space that depicts the space of coalition structures using integers. These algorithms generate the coalition structures by performing index permutations on specific initialization vectors and can handle problems with hundreds or thousands of agents. Last but not least, we develop a multiagent path finding algorithm designed for the coalition structure generation problem. This algorithm significantly outperforms other scalable algorithms in terms of solution quality.

References.

[1] Narayan Changder, Samir Aknine, and Animesh Dutta. “An Effective Dynamic Programming Algorithm for Optimal Coalition Structure Generation (Accepted)”. In: ICTAI 2019: The 31st International Conference on Tools with Artificial Intelligence. 2019.

[2] Talal Rahwan, Sarvapali D Ramchurn, Viet Dung Dang, Andrea Giovannucci, and Nicholas R Jennings. “Anytime optimal coalition structure generation”. In: AAAI. Vol. 7. 2007, pp. 1184–1190.

[3] Narayan Changder, Samir Aknine, and Animesh Dutta. “An Imperfect Algorithm for Coalition Structure Generation”. In: The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pp. 9923–9924.

[4] Tomasz Michalak, Talal Rahwan, Edith Elkind, Michael Wooldridge, and Nicholas R Jennings. “A hybrid exact algorithm for complete set partitioning”. In: Artificial Intelligence 230 (2016), pp. 14–50.

[5] Narayan Changder, Samir Aknine, Sarvapali Ramchurn, and Animesh Dutta. “ODSS: Efficient Hybridization for Optimal Coalition Structure Generation. (Accepted)”. In: Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-2020). 2020.

[6] Narayan Changder, Samir Aknine, and Animesh Dutta. “An Improved Algorithm for Optimal Coalition Structure Generation”. In: Proceedings of the Twelfth International Symposium on Combinatorial Search, SOCS, Napa, California, 16-17 July. 2019, pp. 166–167.

[7] Donald E Knuth. “Dancing links”. In: arXiv preprint cs/0011047 (2000).

Jury:

M. Ramchurn Sarvapali	Professeur(e)	Université de Southampton - Royaume-Uni	Rapporteur(e)
M. Maudet Nicolas	Professeur(e) associé(e)	Sorbonne Université	Rapporteur(e)
Mme Merghem-Boulahia Leila	Professeur(e)	Université de Technologie de Troyes	Examinateur(trice)
M. Farinelli Alessandro	Professeur(e)	Université de Vérone - Italie	Examinateur(trice)
Mme Bonifati Angela	Professeur(e)	LIRIS - Université Claude Bernard Lyon 1	Examinateur(trice)
M. Aknine Samir	Professeur(e)	LIRIS - Université Claude Bernard Lyon 1	Directeur(trice) de thèse
Mme Boukredera Djamila	Maître de conférence	Université de Bejaia - Algérie	Co-encadrant(e)