MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo
Cédric L.R. Buron1 ; Zahia Guessoum2, 3 ; Sylvain Ductor4 ; Olivier Roussel5
1 KLaIM team, L@bisen, Yncrea Ouest, 33 Q. Chemin du Champ de Manœuvres, Carquefou, France
2 CReSTIC EA 3804, Université de Reims Champagne Ardennes, France
3 Lip6 UMR 7606, Sorbonne Université, Paris, France
4 Greentea.Cloud
5 Kyriba Corp, San Diego, USA
Revue Ouverte d'Intelligence Artificielle, Volume 3 (2022) no. 5-6, pp. 645-669.

La négociation automatique suscite un intérêt croissant dans la recherche en intelligence artificielle. Bien que de nombreuses hypothèses aient été explorées, les résultats proposés ne sont pas satisfaisants vis-à-vis de certaines applications. C’est notamment le cas de l’affacturage, qui propose un intéressant défi de par ses spécificités, notamment l’impossibilité de borner la négociation en termes de temps, mais aussi la taille des domaines de négociation, potentiellement infinis. Les méthodes de Monte-Carlo constituent un outil intéressant pour aborder cette application en raison de leur efficacité face à ce type d’hypothèses.

Dans cet article, nous décrivons un agent de négociation automatique, le Monte-Carlo Negotiating Agent (MoCaNA) dont la stratégie d’offre s’appuie sur la recherche arborescente de Monte-Carlo. MoCaNA est doté de méthodes de modélisation du comportement de l’opposant. Il est capable de négocier sur des domaines de négociation incluant des attributs discrets et continus, linéaires ou non, dans un contexte où aucune date butoir n’est spécifiée. Nous confrontons MoCaNA aux agents de l’ANAC 2014 et à d’autres agents capables de négocier sans date butoir, sur des domaines de négociation différents. Il se montre capable de surpasser ou égaler tous les agents dans un domaine sans date butoir et la majorité des finalistes de l’ANAC dans un domaine avec date butoir.

Automated negotiation is of growing interest in artificial intelligence research. While research has focused numerous contexts, some applications have not benefited from these advances. This is particularly the case for factoring, which offers an interesting challenge due to its specificities, notably the impossibility to limit the negotiation in terms of time, and negotiation on vast, even infinite domains. Monte-Carlo methods are an interesting tool for solving this problem because of their effectiveness with such hypotheses.

In this paper, we introduce a Monte Carlo Negotiating Agent (MoCaNA) whose bidding strategy relies on Monte Carlo Tree Search. We endow MoCaNA with opponent modeling techniques for bidding strategy and utility. MoCaNA can negotiate on continuous domains and in a context where no bound is specified. We confront MoCaNA with both the finalists of ANAC 2014 and to agents that are able to negotiate without bounds on different negotiation domains. MoCaNA outperforms or ties all the agents in a domain without bound and the majority of the ANAC finalists in a domain with a bound.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/roia.46
Mot clés : Monte-Carlo, Négociation Automatique, Agent
Keywords: Monte Carlo, Automated Negotiation, Agent

Cédric L.R. Buron 1 ; Zahia Guessoum 2, 3 ; Sylvain Ductor 4 ; Olivier Roussel 5

1 KLaIM team, L@bisen, Yncrea Ouest, 33 Q. Chemin du Champ de Manœuvres, Carquefou, France
2 CReSTIC EA 3804, Université de Reims Champagne Ardennes, France
3 Lip6 UMR 7606, Sorbonne Université, Paris, France
4 Greentea.Cloud
5 Kyriba Corp, San Diego, USA
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{ROIA_2022__3_5-6_645_0,
     author = {C\'edric L.R. Buron and Zahia Guessoum and Sylvain Ductor and Olivier Roussel},
     title = {MoCaNA, un agent de n\'egociation automatique utilisant la recherche arborescente de {Monte-Carlo}},
     journal = {Revue Ouverte d'Intelligence Artificielle},
     pages = {645--669},
     publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
     volume = {3},
     number = {5-6},
     year = {2022},
     doi = {10.5802/roia.46},
     language = {fr},
     url = {https://roia.centre-mersenne.org/articles/10.5802/roia.46/}
}
TY  - JOUR
AU  - Cédric L.R. Buron
AU  - Zahia Guessoum
AU  - Sylvain Ductor
AU  - Olivier Roussel
TI  - MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo
JO  - Revue Ouverte d'Intelligence Artificielle
PY  - 2022
SP  - 645
EP  - 669
VL  - 3
IS  - 5-6
PB  - Association pour la diffusion de la recherche francophone en intelligence artificielle
UR  - https://roia.centre-mersenne.org/articles/10.5802/roia.46/
DO  - 10.5802/roia.46
LA  - fr
ID  - ROIA_2022__3_5-6_645_0
ER  - 
%0 Journal Article
%A Cédric L.R. Buron
%A Zahia Guessoum
%A Sylvain Ductor
%A Olivier Roussel
%T MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo
%J Revue Ouverte d'Intelligence Artificielle
%D 2022
%P 645-669
%V 3
%N 5-6
%I Association pour la diffusion de la recherche francophone en intelligence artificielle
%U https://roia.centre-mersenne.org/articles/10.5802/roia.46/
%R 10.5802/roia.46
%G fr
%F ROIA_2022__3_5-6_645_0
Cédric L.R. Buron; Zahia Guessoum; Sylvain Ductor; Olivier Roussel. MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo. Revue Ouverte d'Intelligence Artificielle, Volume 3 (2022) no. 5-6, pp. 645-669. doi : 10.5802/roia.46. https://roia.centre-mersenne.org/articles/10.5802/roia.46/

[1] Tim Baarslag Exploring the Strategy Space of Negotiating Agents : A Framework for Bidding, Learning and Accepting in Automated Negotiation, Ph. D. Thesis, Delft University of Technology (2016) | DOI

[2] Tim Baarslag; Reyhan Aydoğan; Koen V. Hindriks; Katsuhide Fujita; Takayuki Ito; Catholijn M. Jonker The automated negotiating agents competition, 2010–2015, AI Magazine, Volume 36 (2015) no. 4, pp. 115-118 | DOI

[3] Tim Baarslag; Mark J. C. Hendrikx; Koen V. Hindriks; Catholijn M. Jonker Learning about the opponent in automated bilateral negotiation : a comprehensive survey of opponent modeling techniques, Autonomous Agents and Multi-Agent Systems, Volume 20 (2015) no. 1, pp. 1-50 | DOI

[4] Tim Baarslag; Koen V. Hindriks, AAMAS ’13 (2013), pp. 715-722 http://dl.acm.org/citation.cfm?id=2484920.2485033

[5] Tim Baarslag; Koen V. Hindriks; Catholijn Jonker A Tit for Tat Negotiation Strategy for Real-Time Bilateral Negotiation, Complex Automated Negotiations : Theories, Models, and Software Competitions, Volume 435, Springer Berlin Heidelberg, 2013, pp. 229-233 | DOI

[6] Cameron C. Browne; Edward Powley; Daniel Whitehouse; Simon M. Lucas; Peter I. Cowling; Philipp Rohlfshagen; Stephen Taverner; Diego Perez; Spyridon Samothrakis; Simon Colton A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in games, Volume 4 (2012) no. 1, pp. 1-43 | DOI

[7] Siqi Chen; Gerhard Weiss, Multiagent System Technologies : 10th German Conference Proceedings (2012), pp. 68-82 | DOI

[8] Rémi Coulom, International conference on computers and games (2006), pp. 72-83 | DOI

[9] Dariusz T. Dziuba Crowdfunding Platforms in Invoice Trading as Alternative Financial Markets, Roczniki Kolegium Analiz Ekonomicznych/Szkoła Główna Handlowa, Volume 49 (2018), pp. 455-464

[10] Fang Fang; Ye Xin; Yun Xia; Xu Haitao, 2008 International Symposium on Electronic Commerce and Security (2008) | DOI

[11] Peyman Faratin; Nicholas R. Jennings; Carles Sierra Negotiation decision functions for autonomous agents, Robotics and Autonomous Systems, Volume 24 (1998) no. 3-4, pp. 159-182 | DOI

[12] Katsuhide Fujita; Reyhan Aydoğan; Tim Baarslag; Takayuki Ito; Catholijn Jonker The Fifth Automated Negotiating Agents Competition (ANAC 2014), Recent Advances in Agent-based Complex Automated Negotiation (Naoki Fukuta; Takayuki Ito; Minjie Zhang; Katsuhide Fujita; Valentin Robu, eds.), Springer International Publishing, Cham, 2016, pp. 211-224 | DOI

[13] Recent Advances in Agent-based Complex Automated Negotiation (Naoki Fukuta; Takayuki Ito; Minjie Zhang; Katsuhide Fujita; Valentin Robu, eds.), Studies in Computational Intelligence, 638, Springer International Publishing, 2016 | DOI

[14] Niels van Galen Last Agent Smith : Opponent Model Estimation in Bilateral Multi-issue Negotiation, New Trends in Agent-Based Complex Automated Negotiations (Takayuki Ito; Minjie Zhang; Valentin Robu; Shaheen Fatima; Tokuro Matsuo, eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, 2012, pp. 167-174 | DOI

[15] Sylvain Gelly; David Silver Monte-Carlo tree search and rapid action value estimation in computer Go, Artificial Intelligence, Volume 175 (2011) no. 11, pp. 1856-1875 | DOI | MR

[16] David P. Helmbold; Aleatha Parker-Wood, IC-AI (2009), pp. 605-610

[17] Joe Hicklin; Cleve Moler; Peter Webb; Ronald F. Boisvert; Bruce Miller; Roldan Pozo; Karin Remington Jama : A Java matrix package, 2000 (http://math. nist. gov/javanumerics/jama)

[18] Koen Hindriks; Dmytro Tykhonov, Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Volume 1 (2008), pp. 331-338 http://dl.acm.org/citation.cfm?id=1402383.1402433

[19] Anna Jaśkiewicz; Andrzej S. Nowak Non-Zero-Sum Stochastic Games, Handbook of Dynamic Game Theory (Tamer Basar; Georges Zaccour, eds.), Springer International Publishing, Cham, 2016, pp. 1-64 | DOI

[20] Dave de Jonge; Dongmo Zhang, AAMAS ’17 (2017), pp. 371-379 http://dl.acm.org/citation.cfm?id=3091125.3091183

[21] Levente Kocsis; Csaba Szepesvári, Machine Learning : ECML 2006 (2006), pp. 282-293 | DOI

[22] Raz Lin; Sarit Kraus; Tim Baarslag; Dmytro Tykhonov; Koen Hindriks; Catholijn M. Jonker Genius : an integrated environment for supporting the design of generic automated negotiators, Computational Intelligence, Volume 30 (2014) no. 1, pp. 48-70 | DOI | MR

[23] Maxime Morge, Vingt-sixièmes journées francophones sur les systèmes multi-agents (2018), pp. 75-84

[24] John F. Nash Jr The bargaining problem, Econometrica : Journal of the econometric society (1950), pp. 155-162 | DOI | MR | Zbl

[25] Martin J. Osborne; Ariel Rubinstein A course in game theory, MIT press, 1994

[26] Jeanne-Marie Prost; Jean-Pierre Villetelle Rapport annuel des délais de paiement en 2019 (2020) (Technical report)

[27] Dean G. Pruitt Negotiation Behavior, Academic Press, 1981

[28] Carl E. Rasmussen; Christopher K. I. Williams Gaussian processes for machine learning, MIT Press, 2006

[29] Hsin Rau; Mou-Hsing Tsai; Chao-Wen Chen; Wei-Jung Shiang Learning-based automated negotiation between shipper and forwarder, Computers & Industrial Engineering, Volume 51 (2006) no. 3, pp. 464 -481 http://www.sciencedirect.com/science/article/pii/S0360835206001070 Special Issue on Selected Papers from the 34th. International Conference on Computers and Industrial Engineering (ICC&IE) | DOI

[30] Daniel M Reeves; Michael P Wellman, Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI ’04) (2004), pp. 470-478 http://dl.acm.org/citation.cfm?id=1036843.1036900

[31] Tuomas W. Sandholm Distributed rational decision making, Multiagent systems : a modern approach to distributed artificial intelligence (1999), pp. 201-258

[32] David Silver; Aja Huang; Chris J. Maddison; Arthur Guez; Laurent Sifre; George Van Den Driessche; Julian Schrittwieser et al. Mastering the game of Go with deep neural networks and tree search, Nature, Volume 529 (2016) no. 7587, pp. 484-489 | DOI

[33] The apache commons mathematics library, online, 2016 (see https://commons.apache.org/proper/commons-math/)

[34] Colin R. Williams; Valentin Robu; Enrico H. Gerding; Nicholas R. Jennings, IJCAI’11 (2011), pp. 432-438 | DOI

Cité par Sources :