Négociation multi-agents

Mes travaux s'intègrent aux recherches menées dans l'équipe SMAC de CRIStAL en Intelligence Artificielle Distribuée. Les Systèmes Multi-Agents (SMA) sont un paradigme de premier ordre pour l'analyse, la conception et l'implémentation de systèmes composés d'entités autonomes en interaction. Dans ce domaine, la problématique de la gestion des conflits a deux finalités applicatives majeures : d'une part la conception de systèmes distribués ; d'autre part l'aide à la résolution des conflits entre humains. Quel que soit l'objectif poursuivi, les conflits constituent une caractéristique intrinsèque des SMA. La thèse de doctorat que j'ai soutenue en 2005 aux Mines de Saint-Étienne s'attelait à la résolution des conflits épistémiques, i.e. sur des croyances. Le mécansime principal étudié dans cette thèse est l'argumentation. Les travaux que j'ai menés depuis s'intéressent à la résolution des conflits pratiques, i.e. sur les actions. À cette intention, les agents négocient.

Ce projet de recherche vise à proposer des processus décentralisés pour la gestion des conflits entre des agents autonomes en interaction, en spécifiant leurs comportements. Par négociation, on désigne le processus grâce auquel plusieurs parties prenantes aboutissent à une décision collective en verbalisant leurs demandes pour converger vers un accord. Je défends la thèse selon laquelle le mécanisme opératoire nécessaire pour résoudre un conflit pratique est la concession. Attendu que les agents ont des objectifs individuels qui ne peuvent pas être pleinement satisfaits simultanément, chacun d'eux doit, au fur et à mesure de la négociation, abandonner une partie de ses objectifs pour satisfaire une partie des objectifs de ses interlocuteurs. Ce mécanisme a été étudié à travers le protocole de concession monotone. Toutefois, celui-ci nécessite que chaque agent connaisse la fonction d'utilité de son interlocuteur. En adoptant une approche comportementale, les travaux que j'ai réalisés font l'hypothèse que les données sont décentralisées et donc que les agents ne connaissent pas a priori les préférences des autres. La difficulté commune abordée par ces travaux réside dans le fait que l'information dont disposent les agents est imparfaite. Ainsi, selon la stratégie de concession, un agent débute la négociation en proposant l'alternative qui le satisfait le mieux. Si cette dernière est refusée, l'agent réduit pas-à-pas ses prétentions jusqu'à ce qu'une proposition soit retenue ou que sa valeur de réserve soit atteinte.

Le verrou scientifique auquel ce projet se confronte consiste à garantir la qualité de l'accord obtenu. Je souhaite non seulement garantir le succès du processus de négociation mais également m'assurer de son optimalité sociale. Ce dernier aspect se concrétise via la dominance au sens de Pareto, voire en réintroduisant et en maximisant le bien-être social utilitaire. Dans certains cadres de négociation étudiés, ces critères s'avèrent insuffisants. En effet, je souhaite m'assurer que les concessions, c'est-à-dire les efforts réalisés par les agents pour atteindre un accord soient équitablement répartis. À cette intention, j'introduis la notion d'accord socialement équitable. On peut remarquer que les deux mécanismes évoqués pour la résolution des conflits, l'argumentation et la concession, ne sont pas mutuellement exclusifs. L'argumentation permet de guider les concessions afin d'atteindre rapidement un accord.

Le point commun à l'ensemble des travaux que j'ai menés réside dans le modèle de préférence adopté par les agents. Contrairement à la majorité des travaux existants, je ne représente pas les penchants d'un agent à l'aide d'une fonction d'utilité mais à l'aide d'un modèle de préférence ordinal et qualitatif. Cette hypothèse permet d'éviter les comparaisons interpersonnelles d'utilité qui peuvent être à l'origine de biais dans l'agrégation des préférences. En évitant ainsi des hypothèses restrictives, la modélisation des préférences est expressive et générique. Toutefois, ce modèle de préférence ne nous permet pas d'adopter les fonctions de concession usuelles. Les modèles de préférence que j'ai utilisés prennent la forme d'une relation de préférence complète (i.e. un ordre strict), d'une relation de préférence incomplète (i.e. un pré-ordre) et d'un langage logique. L'expressivité de ces modèles et donc leur complexité est croissante. De manière orthogonale, les processus de négociation que j'ai proposés sont divers de par leur arité. J'ai considéré tour à tour, des processus de négociation bilatérale, multi-latérale puis multi-bilatérale. La complexité du cadre de négociation croit avec l'arité du processus.