5. Négociation dans les systèmes multi-agents
5.2 Critères d'évaluation des protocoles de négociation

5.2.2 Critères d'évaluation

On revient maintenant aux critères d'évaluation des protocoles de négociation. On peut identifier les critères qui suivent. Il faut noter que, bien que ces critères s'appuient sur la théorie des jeux, on peut essayer d'évaluer n'importe quel autre protocole en les utilisant, comme on va voir dans les sections qui suivent.

Rationalité individuelle

Un protocole est rationnel pour un agent si le gain de l'agent qui participe à une négociation avec ce protocole n'est pas inférieur (d'habitude il est supérieur) au gain que l'agent obtiendrait s'il ne participait pas à la négociation. Si un protocole n'est pas rationnel pour un agent alors l'agent (autonome) n'a aucune raison de participer à la négociation. Un protocole est rationnel au niveau individuel s'il est rationnel pour chaque agent participant à la négociation.

Bien-être social

Le bien-être social est la somme de toutes les utilités (ou gains) des agents pour une certaine solution de la négociation. Le bien-être social peut être utilisé pour comparer deux protocoles en faisant la comparaison des résultats auxquels les deux protocoles ont conduit. Le problème qui pose ce critère est qu'il faut comparer les utilités de plusieurs agents et cela n'est pas toujours possible. Dans ce cas, on peut utiliser un autre critère, notamment celui qui suit.

Efficacité Pareto

Une solution (résultat) x à un problème de négociation est efficace Pareto (Pareto optimale), s'il n'y a pas une autre solution x' telle qu'au moins un agent ait une meilleure situation avec x' qu'avec x et aucun agent n'ait une plus mauvaise situation avec x' qu'avec x.. Autrement dit, le résultat (solution) d'une négociation est Pareto optimal s'il n'y a pas un autre résultat qui fasse gagner plus à un agent aux dépens d'un autre agent qui, lui, gagnera moins dans cette solution. L'efficacité Pareto mesure le bien global et ne demande pas la comparaison d'utilités.

Dans le dilemme du prisonnier, le résultat efficace Pareto correspond au cas où les deux prisonniers se tairaient, notamment coopération (CC). Puisque dans ce problème les valeurs d'utilité sont comparables, le bien-être social peut être aussi utilisé et il correspond toujours au cas (CC).

Stabilité

Pour pouvoir définir le critère de stabilité, il faut d'abord comprendre ce que c'est une stratégie dominante. Si on désigne par r = f(ActA, ActB) le résultat (état) des actions ActA de l'agent A et ActB de l'agent B, on peut considérer que, pour différentes combinaisons d'actions possibles de l'agent on obtient différents résultas. Par exemple, dans le dilemme du prisonnier on a quatre résultats possibles, correspondant aux paires d'actions CC, CD, DC et DD. La stratégie de négociation de l'agent lui dit quelles actions il doit faire et correspond à un ensemble de résultats (états) obtenus en suivant cette stratégie. On dit qu'une stratégie S1 = {r11, r12, , r1n} domine une autre stratégie S2 = {r21, r22, , r2m} si n'importe quel résultat r dans S1 est préféré à n'importe quel résultat r' dans S2.

Equilibre Nash

Deux stratégies, S1 de l'agent A et S2 de l'agent B, sont dans un équilibre Nash si:

  • dans le cas où l'agent A adopterait S1 l'agent B ne peut pas faire mieux que d'utiliser S2 et
  • dans le cas où l'agent B adopterait S2 l'agent A ne peut pas faire mieux que de d'utiliser S1.
La définition peut être généralisée pour plusieurs agent qui suivent les stratégies S1, S2, , Sk. L'ensemble de stratégies {S1, S2, , Sk} suivies par les agents A1, A2, , Ak est dans un équilibre Nash si, pour chaque agent Ai, la stratégie Si est la meilleure stratégie à suivre par Ai pourvu que les autres agents suivent les stratégies { S1, S2, , Si-1, Si+1,, Sk.}.

Cette forme d'équilibre mutuel est très importante car, si on a un équilibre Nash aucun agent n'aura de raison de suivre une autre stratégie que celle qui assure l'équilibre.
Revenons au problème des prisonniers. Dans ce cas, l'équilibre Nash est assuré par le cas où les deux prisonniers dénoncent (DD). En fait, on a vu quand on a présenté le problème que DD était le comportement rationnel pour les deux agents. Il faut noter que dans le cas du dilemme de prisonnier l'équilibre Nash est assuré par les actions DD alors que le bien-être social est garanti par les actions (CC).

Question: Expliquez pourquoi l'équilibre Nash du dilemme du prisonnier est le cas (DD).

 

 

Cliquer ici pour voir la réponse.

Il y a un problème lié à l'application de l'équilibre Nash comme critère d'évaluation des protocoles de négociation: il existe des problèmes qui n'ont pas d'équilibre Nash et d'autres qui en possèdent plusieurs . De plus, si le jeu est joué avec plusieurs tours (en tournoi), l'équilibre Nash garantit la stabilité uniquement au début du tournoi.

Dans le cas du dilemme du prisonnier, si on joue le jeu d'une manière répétitive, et si on suppose que chaque prisonnier peut connaître l'action choisie par l'autre au tour précédent, le problème de la stratégie à suivre devient plus compliqué. Robert Axelrod a organisé une compétition entre plusieurs équipes (logiciels conçus par différents ingénieurs) où chaque équipe avait une certaine stratégie, par exemple: TIT-FOR-TAT = au premier tour, coopérer, aux tours suivants, choisir l'action que l'autre joueur a effectué au tour précédent; ALL-D = dénoncer toujours sans prendre en compte ce que l'autre a fait aux tours précédents, JOSS = TIT-FOR-TAT mais dans 10% des cas, au lieu de coopérer le joueur dénonce. A la fin de la compétition la stratégie gagnante a été TIT-FOR-TAT mais on considère que cette stratégie a gagné parce que la plupart des équipes avait tendance à coopérer. De nombreuses recherches essaient de trouver la meilleure stratégie à suivre dans les jeux de type dilemme du prisonnier en tournoi, y compris les stratégies obtenues par apprentissage artificiel (par exemple les algorithmes génétiques).

Simplicité et efficacité de calcul

Un protocole est "simple" si les participants peuvent se rendre compte aisément quelle est la meilleure stratégie à suivre. En plus, un protocole doit être efficace du point de vue des calculs impliqués pour déterminer quelle est la stratégie optimale.

Les négociations modélisées par la théorie des jeux, même si elles offrent un modèle mathématique rigoureux, posent des problèmes si on essaie de les appliquer à des situations du monde réel parce que (Chaib-Draa, Jarras et Moulin, 2001):

  • les négociations impliquent des critères beaucoup plus complexes qu'une utilité une seule dimension;
  • les négociations se déroulent parfois dans une certaine incertitude;
  • les utilités des agents sont parfois secrètes;
  • les agents ne peuvent pas avoir une puissance de calcul infinie, notamment ils ne peuvent pas disposer de tout leur temps pour déterminer la stratégie optimale; dans la théorie des jeux on considère que l'agent est capable de trouver la meilleure stratégie instantanément ce qui n'est pas le cas dans le monde réel.

<< Section précédente Table de matières Section suivante >>

Politechnica University of Bucharest - 2002