5. Négociation dans les systèmes multi-agents
5.5 Autres modèles de négociation

5.5.1 Négociation heuristique

Dans cette section et la suivante on présentera d'autres mécanismes de négociation, en retournant au modèle des agents egocentrés. Dans les protocoles de négociation qu'on a déjà discutés, les agents pouvaient accepter ou repousser une proposition (offre).

Si les agents peuvent uniquement accepter ou rejeter les propositions d'autres agents, alors la négociation peut être très longue et inefficace puisque l'auteur d'une proposition n'a pas le moyen de vérifier pourquoi la proposition est inacceptable, ni si les agents sont proches d'un accord, ni dans quelle direction une proposition peut être changée pour convenir à l'autre agent.

Pour améliorer l'efficacité de la négociation, les agents doivent fournir des réactions plus utiles aux propositions qu'ils reçoivent. Ces réactions peuvent prendre la forme d'une critique ou d'une contre-proposition (proposition refusée ou modifiée). Une critique est un commentaire sur la partie de la proposition que l'agent accepte ou refuse. Une contre-proposition est une proposition alternative engendrée en réponse à une proposition. À partir de telles réactions, l'auteur doit être capable d'engendrer une proposition qui est probablement plus apte à mener à un accord.

Considérons d'abord le concept de critique. Une critique fournit deux formes de réactions: elle suggère des contraintes sur les questions de négociation particulières et elle indique l'acceptation ou le rejet des caractéristiques particulières de la proposition ou de la proposition entière.

Pour illustrer ces points, considérons les dialogues suivants qui sont des exemples de propositions suivies par des critiques. Nous utilisons le langage naturel dans les exemples mais la négociation sera, normalement, exprimée dans un langage formel de négociation.

Dans le premier cas, la critique mentionne les aspects de la proposition qui sont acceptables et ceux qui ont besoin d'être modifiés. Dans le deuxième cas, la critique indique le rejet d'une partie de la proposition.

Les contre-propositions sont le deuxième mécanisme de réaction à une proposition. Une contre-proposition est une proposition qui est plus favorable à l'expéditeur et elle est faite en réponse à une proposition précédente. Les exemples qui suivent montrent des propositions suivies par des contre-propositions.

Dans le dialogue 3, la contre-proposition étend la proposition initiale alors que dans le dialogue 4, l'agent B amende une partie de la proposition initiale. Les contre-propositions diffèrent des critiques en ce que les réactions sont plus détaillées. Le schéma pour décrire un tel mécanisme de négociation est montré dans la figure 6.

Figure 6. Négociation heuristique

Ce type de négociation est appelé négociation heuristique; expliquons pourquoi. Il y a une différence importante entre les mécanismes de négociation que nous avons discutés précédemment, par exemple les enchères, et la négociation heuristique. Cette différence consiste dans le modèle de décision de l'agent.

Le modèle de décision de l'agent est le dispositif de décision que les participants emploient en conformité avec le protocole de négociation pour atteindre leurs objectifs. Dans certaines circonstances, comme celles que nous avons discutées dans les sections précédentes, le protocole de négociation est dominant -voir le cas d'enchères. Le protocole contraint les types d'opérations qui peuvent être exécutées sur l'objet de négociation et prescrit le comportement du modèle de décision de l'agent. Par exemple, dans la plupart des protocoles d'enchères que nous avons présentés, il y a une stratégie optimale (dominante) que l'agent peut utiliser.

Dans les méthodes heuristiques de négociation, le problème central est de modéliser la décision de l'agent au cours de la négociation. Généralement, le protocole choisi ne prescrit pas un cours optimal d'action, notamment une stratégie optimale pour l'agent. Dans ce cas, le succès relatif de deux agents est déterminé par l'efficacité de leur modèle de raisonnement. Les agents doivent découvrir d'une manière heuristique quelle est la meilleure proposition ou contre-proposition qu'ils doivent faire. Ils doivent découvrir cela en partant du modèle de décision qu'ils emploient. Meilleur sera le modèle, et plus grande sera la récompense de l'agent.

Dans les méthodes heuristiques de négociation, l'objet de négociation est très important parce qu'il décrit les caractéristiques que les agents négocient. On présente un exemple d'un objet de négociation et une série de primitives de négociation dans un langage de négociation possible (Florea, 2002).

L'objet de négociation (ON) est l'intervalle des questions sur lesquelles un accord doit être trouvé. L'objet de la négociation peut être une action que l'agent négociateur A demande à un autre agent B d'effectuer, un service que l'agent A demande à B ou l'offre d'un service que A veut effectuer pour B si B accepte les conditions de A. L'objet de négociation est défini par plusieurs attributs, chaque attribut pouvant être négocié (Modifiable = Oui) ou non (Modifiable = Non). Cela correspond à la possibilité de modifier ou pas la valeur de l'attribut dans une contre-proposition.

Objet de négociation
ON03: ON
Nom: Peindre_maison
Coût: Valeur:100, Type: integer, Modifiable = Oui;
Date_limite: Valeur: 12_mai, Type: date, Modifiable = Non;
Qualité: Valeur: grande, Type: un de (basse, moyenne, grande), Modifiable = Oui

Primitives de négociation

• (Request ON) - demande d'un objet de négociation
• (Accept nom(ON)) - accepte la demande de ON
• (Reject nom(ON)) - refuse la demande de ON
• (ModReq nom(ON) valeur(ON, X, V1)) - modifie la demande en modifiant la valeur de l'attribut X du ON à une autre valeur V1

Le protocole est montré dans la figure 7. Dans ce protocole plusieurs propositions et contre-propositions peuvent être échangées dans des tours suivants. L'agent A, avec la proposition pA, est l'initiateur de la négociation, alors que l'agent B peut répondre avec les réponses p1B, p2B, p3B. Même si on ne l'indique pas d'une manière explicite dans le protocole, le nombre des contre-propositions qu'on peut faire est limité. Une fois que cette limite est atteinte, on arrive à un rejet.

Figure 7. Protocole de négociation heuristique

Il faut remarquer qu'un tel protocole donne seulement les règles acceptables pour une négociation heuristique mais n'indique pas les critères que l'agent doit utiliser pour prendre une décision. C'est le mécanisme de raisonnement de l'agent qui indiquera si et quand il faut accepter la proposition ou faire une contre-proposition, quelle contre-proposition faire et comment cette contre-proposition devrait être faite (comment modifier la proposition initiale).

Question: Donner un exemple d'objet de négociation qui correspond à l'offre d'un service que A veut effectuer pour B si B accepte les conditions de A

Cliquer ici pour voir la réponse.