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.
|
