MoCaNA, un agent de négociation automatique utilisant la recherche arborescente de Monte-Carlo

Cédric L R Buron (1) , Zahia Guessoum (2) , Sylvain Ductor (3) , Olivier Roussel

1 Thales Research and Technology [Palaiseau]
2 CRESTIC - Centre de Recherche en Sciences et Technologies de l'Information et de la Communication - EA 3804
3 DC/UFC - Departamento de Computaçãos [Ceará]

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.

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.

Mots clés: négociation; agent; MCTS

Domaines: Système multi-agents [cs.MA]; Intelligence artificielle [cs.AI]; Apprentissage [cs.LG]

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, 2022, Post-actes des Journées Francophones sur les Systèmes Multi-Agents, 3 (5-6), pp.645-669. ⟨hal-03873577⟩