5. Négociation dans les systèmes multi-agents
5.4 Négociation pour l'allocation des tâches
5.4.2 Allocation des tâches par redistribution
Le problème de l'allocation des tâches entre agents a été
étudié par Rosenschein et Zlotkin (1994) dans ce qu'ils
appellent domaines orientés tâches ("task-oriented domains"
en anglais). Un domaine orienté tâche est un triple
<T, Ag, c>
où
- T est un ensemble de tâches;
- Ag = {1, . . . ,n}est un ensemble d'agents qui participent
à la négociation;
- c:P(T)->R+ est une fonction coût qui définie
les coûts nécessaires pour exécuter chaque sous-ensemble
de tâches.
La fonction coût doit satisfaire deux contraintes: elle doit être
monotone et le coût de ne pas exécuter une tâche doit
être zéro, c'est à dire c(F)
= 0. La première contrainte dit que, si on ajoute une tâche
à un ensemble de tâches, le coût de l'ensemble résultant
doit être toujours supérieur au coût de l'ensemble
initial.
Une rencontre dans un domaine orienté
tâche est l'attribution d'une collection d'ensembles de tâches
R = {E1, . . ., En}, Ei T, i Ag, aux agents Ag.
Dans une telle rencontre, on se pose le problème de savoir si
chaque agent ne serait pas en meilleure situation (avec des coûts
moins élevés) par un réallocation des tâches
à exécuter. Par exemple, si on a trois agents a1, a2 et
a3 (Ag = {a1, a2, a3}) et les tâches T = {t1, t2, t3, t4, t5} on
peut définir la rencontre
R = {E1, E2, E3} avec E1 = {t1, t3}, E2 = {t2}, E3 = {t4, t5}
Cette rencontre indique que l'allocation initiale des tâches est
t1 et t3 pour l'agent a1, t2 pour l'agent a2, et t4 et t5 pour l'agent
a3. Les agents peuvent négocier entre eux pour arriver à
une autre distribution de tâches, c'est à dire à une
réallocation, par exemple a1 fera t1 et t5, a2 fera t2 et t3, et
a3 fera t4. Quelle sera la motivation des agents pour essayer une réallocation
des tâches? On va l'expliquer maintenant.
Supposons qu'on a seulement deux agents Ag = {a1, a2} et une rencontre
R = {E1, E2}. Dans une telle rencontre, une affaire
A = {D1, D2} est une allocation de tâches E1 E2 dans
deux autres ensembles de tâches D1 et D2 tel que D1 U D2 = E1 U
E2.
Le coût d'une affaire pour l'agent a1 est défini comme c(D1)
alors que le coût pour l'agent a2 est c(D2). L'utilité d'une
affaire représente combien l'agent doit gagner grâce à
l'affaire et peut être définie comme:
utilitéi(A ) = ci(Ei) - ci(Di), pour i = 1, 2
correspondant aux agents a1 et a2
Si l'utilité est négative, alors la situation de l'agent
est pire que s'il avait exécuté simplement les tâches
qui lui ont été allouées au début dans la
rencontre. Qu'arrive-t-il si les agents n'atteignent pas l'accord? Dans
ce cas, ils doivent exécuter les tâches qui leur ont été
allouées au début.
La notion de dominance (voir stratégie dominante dans la section
5.2.2) peut être aussi définie pour les affaires. Une
affaire 1 est dite dominer une autre affaire 2 si et seulement
si:
- l'affaire A1 est au moins aussi bonne que A2 pour chaque agent
pour chacune i dans {1,2} utilitéi(A1)>=utilitéi(A2)
- l'affaire A1 est meilleure que A2 pour au moins un agent
pour chacune i dans {1,2} utilitéi(A1) >utilitéi(A2)
Si une affaire A1 domine une autre affaire A2, alors il doit être
clair pour tous les participants que A1 est meilleure que A2 et tous les
agents rationnels doivent préférer A1 à A2.Une affaire
qui n'est dominée par aucune autre affaire est dite Pareto
optimale.
Pour réaliser une meilleure allocation des tâches les agents
utilisent un protocole appelé le protocole
de concession monotone. Les règles du protocole sont
comme suit.
- La négociation se déroule en une suite de tours.
- Au premier tour, les deux agents proposent simultanément une
affaire de la série de négociation.
- Un accord est atteint si les deux agents proposent des affaires A1
et A2 telles que soit utilité1(A2)>=utilité1(A1)
soit utilité2(A1)>=utilité2(A2). Autrement
dit, un des agents trouve l'affaire proposée par l'autre au moins
aussi convenable ou meilleure que la proposition qu'il a faite.
- Si un accord est alors atteint la règle pour déterminer
l'affaire sur laquelle les agents sont d'accord est la suivante. Si
les deux offres des agents égalent ou dépassent ceux de
l'autre agent, alors une des propositions est choisie au hasard. Si
seulement une proposition dépasse ou égale l'autre proposition,
alors c'est elle qui est l'affaire sur laquelle les agents sont d'accord.
- Si aucun accord n'est atteint, alors la négociation continue
pour un autre tour de propositions simultanées. Au tour u + 1,
aucun agent n'a le droit de faire une proposition qui est moins préférée
par l'autre agent que l'affaire qu'il a proposée au tour u.
- Si aucun agent ne fait de concession à un tour donné,
alors la négociation est terminée et il y a conflit.
Le protocole de concession monotone garantit que la négociation
se terminera avec ou sans accord, après un nombre fini de tours.
Cependant le protocole ne certifie pas qu'un accord sera rapidement atteint.
Il est concevable que la négociation continue pour un nombre de
tours qui croît d'une manière exponentielle par rapport au
nombre de tâches à allouer.
 Question:
Dans une telle rencontre, y-a-t-il des raisons pour qu'un agent mente
et quel sera le mensonge qui peut lui apporter un bénéfice?
Cliquer ici pour voir
la réponse.
|
