Un protocole de concessions monotones pour la formation distribuée de coalitions
Josselin Guéneron1 ; Grégory Bonnet1
1 Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France
Revue Ouverte d'Intelligence Artificielle, Volume 5 (2024) no. 1, pp. 9-34.

Nous nous intéressons dans cet article à la conception d’un protocole de formation de coalitions distribué et générique. Pour ce faire, nous étudions une adaptation au cadre de la formation de coalitions d’un protocole de négociation multilatérale initialement proposé par Ulle Endriss. Ce protocole utilise un mécanisme de concession monotone et nous proposons, d’une part, une adaptation directe au problème de formation de coalitions et, d’autre part, deux nouvelles stratégies de concession qui prennent explicitement en compte la notion de coalition. Nous étudions par la suite comment différents critères influencent les performances du protocole, y compris en termes de types de concession décrivant des contraintes sur les propositions que les agents peuvent formuler. Nous montrons expérimentalement que nos deux stratégies tenant compte explicitement des coalitions sont efficaces lorsqu’elles sont associées aux trois types de concession qui minimisent les pertes, à savoir les types fort, égalitaire et Pareto.

In this article, we are interested to design a distributed and generic coalition formation protocol. To this end, we study an adaptation of a multilateral negotiation protocol originally proposed by Ulle Endriss. This protocol uses a monotonic concession mechanism and we propose, on the one hand, a direct adaptation to the coalition formation problem and, on the other hand, two new concession strategies that explicitly take into account the notion of coalition. We then study how different criteria influence the performance of the protocol, including concession types describing constraints on the proposals agents can make. We show experimentally that our two strategies that explicitly take coalitions into account are efficient when they are associated with the three loss-minimizing concession types, namely the strong, egalitarian and Pareto types.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/roia.63
Mot clés : Formation distribuée de coalitions, théorie des jeux, négociation.
Keywords: Distributed coalition formation, Game theory, Negotiation.

Josselin Guéneron 1 ; Grégory Bonnet 1

1 Normandie University, UNICAEN, ENSICAEN, CNRS, GREYC, Caen, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ROIA_2024__5_1_9_0,
     author = {Josselin Gu\'eneron and Gr\'egory Bonnet},
     title = {Un protocole de concessions monotones pour la formation distribu\'ee de coalitions},
     journal = {Revue Ouverte d'Intelligence Artificielle},
     pages = {9--34},
     publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
     volume = {5},
     number = {1},
     year = {2024},
     doi = {10.5802/roia.63},
     language = {fr},
     url = {https://roia.centre-mersenne.org/articles/10.5802/roia.63/}
}
TY  - JOUR
AU  - Josselin Guéneron
AU  - Grégory Bonnet
TI  - Un protocole de concessions monotones pour la formation distribuée de coalitions
JO  - Revue Ouverte d'Intelligence Artificielle
PY  - 2024
SP  - 9
EP  - 34
VL  - 5
IS  - 1
PB  - Association pour la diffusion de la recherche francophone en intelligence artificielle
UR  - https://roia.centre-mersenne.org/articles/10.5802/roia.63/
DO  - 10.5802/roia.63
LA  - fr
ID  - ROIA_2024__5_1_9_0
ER  - 
%0 Journal Article
%A Josselin Guéneron
%A Grégory Bonnet
%T Un protocole de concessions monotones pour la formation distribuée de coalitions
%J Revue Ouverte d'Intelligence Artificielle
%D 2024
%P 9-34
%V 5
%N 1
%I Association pour la diffusion de la recherche francophone en intelligence artificielle
%U https://roia.centre-mersenne.org/articles/10.5802/roia.63/
%R 10.5802/roia.63
%G fr
%F ROIA_2024__5_1_9_0
Josselin Guéneron; Grégory Bonnet. Un protocole de concessions monotones pour la formation distribuée de coalitions. Revue Ouverte d'Intelligence Artificielle, Volume 5 (2024) no. 1, pp. 9-34. doi : 10.5802/roia.63. https://roia.centre-mersenne.org/articles/10.5802/roia.63/

[1] E. Anshelevich; A. Dasgupta; J. Kleinberg; É. Tardos; T. Wexler; T. Roughgarden The price of stability for network design with fair cost allocation, SIAM Journal on Computing, Volume 38 (2008) no. 4, pp. 1602-1623 | DOI | Zbl

[2] R. J. Aumann; J. H. Dreze Cooperative games with coalition structures, International Journal of Game Theory, Volume 3 (1974), pp. 217-237 | DOI | Zbl

[3] E. T. Bell The iterated exponential integers, Ann. of Math. (2), Volume 39 (1938) no. 3, pp. 539-557 | DOI | MR | Zbl

[4] F. Bistaffa; A. Farinelli; J. Cerquides; J. Rodríguez-Aguilar; S. D. Ramchurn Algorithms for graph-constrained coalition formation in the real world, ACM Transactions on Intelligent Systems and Technology, Volume 8 (2017) no. 4, pp. 1-24 | DOI

[5] J. Castro; D. Gómez; J. Tejada Polynomial calculation of the Shapley value based on sampling, Computers & Operations Research, Volume 36 (2009) no. 5, pp. 1726-1730 | DOI | Zbl

[6] G. Chalkiadakis; E. Elkind; M. Wooldridge Computational aspects of cooperative game theory, Synthesis Lectures on Artificial Intelligence and Machine Learning, 5, Springer Cham, 2011 no. 6, 168 pages | DOI

[7] U. Endriss Monotonic concession protocols for multilateral negotiation, 5th International Joint Conference on Autonomous Agents and MultiAgent Systems (2006), pp. 392-399 | DOI

[8] G. Greco; E. Malizia; L. Palopoli; F. Scarcello On the complexity of the core over coalition structures, 22nd International Joint Conference on Artificial Intelligence (2011), pp. 216-221

[9] J Guéneron; G. Bonnet Un protocole de concessions monotones pour la formation distribuée de coalitions, 30es Journées Francophones sur les Systèmes Multi-Agents (2022), pp. 31-40

[10] L. Khalouzadeh; N. Nematbakhsh; K. Zamanifar A Decentralized Coalition Formation Algorithm among Homogeneous Agents, Journal of Theoretical & Applied Information Technology, Volume 22 (2010) no. 1, pp. 35-42

[11] R. Mochaourab; E. A. Jorswieck Coalitional games in MISO interference channels : Epsilon-core and coalition structure stable set, IEEE Transactions on Signal Processing, Volume 62 (2014) no. 24, pp. 6507-6520 | DOI | Zbl

[12] M. Nagarajan; G. Sošić Game-theoretic analysis of cooperation among supply chain agents : Review and extensions, European Journal of Operational Research, Volume 187 (2008) no. 3, pp. 719-745 | DOI | Zbl

[13] A. Navon; G. Ben Yosef; R. Machlev; S. Shapira; N. R. Chowdhury; J. Belikov; A. Orda; Y. Levron Applications of game theory to design and operation of modern power systems : a comprehensive review, Energies, Volume 13 (2020), 3982 | DOI

[14] T. Rahwan; N. R. Jennings An improved dynamic programming algorithm for coalition structure generation, 7th International Joint Conference on Autonomous Agents and MultiAgent Systems (2008), pp. 1417-1420

[15] T. Rahwan; T. Michalak; M. Wooldridge; N. R. Jennings Coalition structure generation : A survey, Artificial Intelligence, Volume 229 (2015), pp. 139-174 | DOI | Zbl

[16] T. Rahwan; S. D. Ramchurn; N. R. Jennings; A. Giovannucci An anytime algorithm for optimal coalition structure generation, Journal of Artificial Intelligence Research, Volume 34 (2009), pp. 521-567 | DOI | Zbl

[17] Gian-Carlo Rota The number of partitions of a set, Amer. Math. Monthly, Volume 71 (1964), pp. 498-504 | DOI | MR | Zbl

[18] L. S. Shapley A value for n-person games, Contribution to the Theory of Games (H. Kuhn; A. Tucker, eds.), Volume 2, Princeton University Press, 1953, pp. 303-317 | DOI | Zbl

[19] L. S. Shapley; M. Shubik Quasi-cores in a monetary economy with nonconvex preferences, Econometrica : Journal of the Econometric Society, Volume 34 (1966), pp. 805-827 | DOI | Zbl

[20] O. Shehory; S. Kraus Methods for task allocation via agent coalition formation, Artificial Intelligence, Volume 101 (1998) no. 1-2, pp. 165-200 | DOI | Zbl

[21] M. Sims; C. V. Goldman; V. Lesser Self-organization through bottom-up coalition formation, 2nd International Joint Conference on Autonomous Agents and MultiAgent Systems (2003), pp. 867-874 | DOI

[22] P. Tošić; C. Ordonez Distributed protocols for multi-agent coalition formation : a negotiation perspective, 8th International Conference on Active Media Technology (2012), pp. 93-102 | DOI

Cité par Sources :