=Paper=
{{Paper
|id=Vol-2133/cnia-paper1
|storemode=property
|title=Mécanisme de négociation multilatérale pour la prise de décision collective(Multilateral negotiation mechanism for collective decision-making)
|pdfUrl=https://ceur-ws.org/Vol-2133/cnia-paper1.pdf
|volume=Vol-2133
|dblpUrl=https://dblp.org/rec/conf/rjcia/DiagoASS18
}}
==Mécanisme de négociation multilatérale pour la prise de décision collective(Multilateral negotiation mechanism for collective decision-making)==
https://ceur-ws.org/Vol-2133/cnia-paper1.pdf
Mécanisme de négociation multilatérale pour la prise de décision collective
Ndeye Arame DIAGO 1 Samir AKNINE 1 Onn SHEHORY 2 Mbaye SENE 3
1 Université de Lyon 1 2 Bar Ilan University 3 Université de Dakar
aramesdiago@yahoo.fr
Résumé intérêts différents pour la réalisation d’un but
Dans cet article, nous proposons un modèle de commun, de construire ensemble des solutions
négociation multilatérale dans lequel l’interaction collectivement satisfaisantes. Ces participants ont
des agents est totalement décentralisée. Le protocole le plus souvent un comportement égoı̈ste, et ne
proposé s’inspire du principe ”Diviser pour régner”. partagent pas les informations concernant leurs
Les agents sont répartis en plusieurs groupes appelés fonctions d’utilité et leurs préférences. Chacun
anneaux dans lesquels ils négocient. Nous proposons tente de conduire la négociation vers un accord
des politiques d’interaction permettant la communi- qui satisfait ses objectifs. Dans un tel contexte, la
cation entre des agents appartenant à des anneaux négociation devient très complexe lorsque le nombre
différents. Nous cherchons à travers cette approche de participants est important. Dans cet article, nous
distributive à limiter les champs d’interaction des nous intéressons aux négociations multilatérales
agents pour réduire la complexité de raisonnement fondées sur des approches heuristiques[4]. Les
des agents et faciliter la recherche d’accords collec- agents construisent la solution à leur problème à
tifs. Nous avons évalué les performances de notre travers leurs interactions, à la différence des modèles
protocole en le comparant à une approche centra- basés sur la théorie des jeux dont l’espace des solu-
lisée, c’est-à-dire que tous les agents négocient dans tions est supposé connu par tous les agents [1].
un seul groupe. La plupart des travaux effectués sur la négociation
multilatérale ne fournissent pas de protocoles
Mots Clef spécifiques ou s’appuient sur des hypothèses diffici-
Négociation multilatérale, Diviser pour régner, lement applicables dans un contexte réel. Certains
Décision collective étendent les mécanismes proposés pour le cas d’une
négociation bilatérale [1]. Par exemple, [5] propose
Abstract une généralisation du protocole de concession mo-
In this paper, we propose a multilateral negotiation notone [12] pour la négociation multilatérale, il
model in which the agents interact in a fully decen- ne fournit pas un protocole spécifique. [1] propose
tralized way. The proposed protocol draws on ”di- une généralisation du mécanisme de négociation
vide and rule” approach. The agents are divided into bilatérale basé sur les offres alternées pour le cas de
different groups called ”rings” in which negotiations la négociation multilatérale. D’autres mécanismes
take place simultaneously. We propose interaction de négociation multilatérale désignent un médiateur
policies allowing the communication between agents qui se charge, par exemple, de superviser et de
from different rings. We seek through this approach détecter les conflits entre les parties négociatrices,
to limit the agents’ scope of interaction and hence et de suggérer des offres [10, 3]. Le problème de
to reduce agents reasoning complexity to facilitate ces protocoles de négociation avec médiateur réside
agreement research. We have evaluated our protocol dans leur structure centralisée. Ils ne garantissent
by comparing it with a model where all of the agents pas toujours une solution satisfaisante. Notre ob-
negotiate in the same group. jectif est de proposer des protocoles de négociation
applicables dans un contexte réel et qui permettent
Keywords aux agents de construire des solutions collectives de
Multilateral negotiation, Divide and rule, Collective façon totalement décentralisée.
decision. [2] présente deux extensions du protocole des offres
alternées : Stacked Alternating Offers Protocol (SAOP)
1 Introduction et Alternating Multiple Offers Protocol (AMOP).
La négociation multilatérale est un processus Dans ces protocoles, chaque agent ne participe à
d’échange qui permet aux participants ayant des la négociation que quand son tour arrive. Dans
le protocole SAOP, celui-ci démarre toujours la au mieux à leurs objectifs.
négociation en soumettant une offre, et lorsque son
tour arrive, il n’évalue que la dernière offre soumise. 2 Le modèle de négociation
Par conséquent, toutes les offres ne sont pas évaluées
par tous les agents, et certains d’entre eux peuvent Pour illustrer le mécanisme de négociation proposé,
passer à coté des offres qui les auraient intéressées. nous considérons un scénario de négociation basé sur
Dans le protocole AMOP, tous les agents soumettent un projet de mise en place d’une nouvelle ligne de
séquentiellement leurs offres. Ensuite, chacun vote tramway pour une agglomération. Ce projet implique
pour toutes les offres. Dans ce protocole, chaque par exemple, les maires des communes concernées,
agent a une meilleure visibilité sur l’espace des le préfet de la région, les conseillers régionaux et les
solutions, et il peut évaluer toutes les offres des compagnies de transports. Leur but est de déterminer
autres à la différence du protocole SAOP. Cependant, le tracé de la nouvelle ligne de tramway, c’est-à-dire,
ce protocole est très coûteux en nombre de mes- les coordonnées de ses arrêts. Ces participants ayant
sages comparé au protocole SAOP. Le processus de des intérêts différents vont négocier pour s’accorder
raisonnement des agents devient plus complexe car sur une solution. Par exemple, le but des maires
les agents doivent évaluer toutes les offres en même est d’optimiser le coût de financement du projet et
temps, et prennent des décisions pour chacune de la desserte des établissements publics en préférant
ces offres. que la ligne desserve plusieurs communes. Le préfet
Notre modèle s’appuie sur les hypothèses suivantes : s’intéresse à la sécurité des personnes en préférant
(1) les agents négocient sur un seul problème (at- que certains arrêts soient proches des postes de po-
tribut) et doivent trouver une solution collective et lice. Les conseillers régionaux s’intéressent à la des-
acceptable, c’est-à-dire, acceptée par la majorité des serte des établissements publics tels que les lycées.
agents ; (2) les agents sont égoı̈stes et chacun cherche Quant aux compagnies de transport, elles souhaitent
à défendre ses propres intérêts ; (3) la négociation que les arrêts soient proches des stations de métro et
s’effectue sans médiateur, les agents interagissent bus pour faciliter les correspondances.
entre eux de façon totalement décentralisée ; (4) les Le mécanisme de négociation proposé consiste à
agents ne partagent pas leur fonction d’utilité ; (5) la structurer les agents en petits groupes appelés an-
négociation s’effectue sur une durée limitée. De telles neaux dans lesquels les agents s’échangent des pro-
négociations nécessitent des protocoles spécifiques positions. La négociation s’effectue simultanément
pour faciliter la prise de décision et la définition au sein de chaque anneau. Dans chaque anneau, les
de concepts de solution de négociation équitable et agents soumettent leurs propositions. Ils reçoivent
collectivement satisfaisante. celles des autres et prennent des décisions. Un agent
Le mécanisme de négociation que nous propo- peut accepter, refuser, renforcer ou attaquer une pro-
sons, dans cet article, est fondé sur une approche position soumise par un autre agent. La négociation
incrémentale et itérative permettant de distribuer s’effectue de manière décentralisée sans médiation,
la négociation mais aussi, d’appréhender la com- autrement dit les agents décident eux-mêmes de leurs
plexité du raisonnement des agents et ainsi, de propositions et réagissent avec les autres selon leurs
faciliter la convergence de la négociation tout en propres croyances tout en respectant les règles du
limitant le temps. Pour aborder ces problèmes, protocole. Chaque proposition soumise par un agent
nous nous intéressons à l’organisation du système est une suggestion de solution de négociation. Elle
multi-agents. La forme organisationnelle du système devient une solution acceptable si elle est acceptée par
peut significativement affecter la complexité de la la majorité des agents. Le choix de la règle de la ma-
recherche d’accords, la flexibilité, la réactivité et jorité est justifié par le fait que nous considérons les
peut induire des coûts de calcul et de communi- négociations impliquant un grand nombre d’agents
cation [9, 13]. Le modèle de négociation proposé dans lesquelles l’application de la règle de l’unani-
s’inspire de l’approche ”Diviser pour régner”. Il mité rend difficile la recherche d’accords collectifs.
s’agit, d’abord, de diviser l’ensemble des agents en Pour rendre flexible le mécanisme de négociation
groupes dans lesquels les négociations vont prendre proposé, le protocole permet aux agents qui le sou-
place. Nous cherchons à travers cette répartition à haitent de prendre connaissance via l’écoute flottante
limiter les champs d’interaction des agents, à réduire des interactions qui s’effectuent dans les autres an-
la complexité de leur raisonnement et à faciliter la neaux. Cela permet aux agents d’appréhender les
recherche d’accords. Ensuite, nous proposons des négociations menées au-delà de leur anneau. Ainsi,
politiques d’interaction qui s’adaptent aux modèles un agent peut réagir sur les propositions écoutées
d’organisation des agents proposés. Nous proposons tout en restant dans son anneau. Comme il peut
différentes stratégies de négociation qui permettent décider de rejoindre un autre anneau dans lequel ses
aux agents de prendre des décisions qui répondent intérêts seront mieux défendus. Cependant, ils uti-
lisent différentes stratégies pour choisir le meilleur
anneau qu’ils vont rejoindre s’ils en écoutent plus de la négociation, il peut être appelé à faire des
d’un. Lorsqu’un agent se déplace dans un nouvel concessions pour établir un compromis avec les
anneau, il peut soit soumettre de nouvelles pro- autres agents. Ainsi, chaque agent fixe ses aspirations
positions, soit défendre ses propositions ayant déjà représentées ici par l’utilité minimale Umina qu’il
i
obtenu un certain taux d’acceptation en vue d’at- peut espérer, autrement dit son utilité de réserve
teindre la majorité. Les interactions inter-anneaux et en dessous de laquelle aucune proposition n’est
les déplacements des agents d’un anneau à un autre acceptable, et l’utilité maximale Umaxa en dessus de
i
sont régis par les règles du protocole et la politique laquelle toute proposition est acceptable. Lorsque
d’interaction proposée. Une politique d’interaction l’utilité d’une proposition se trouve entre Umina et
i
inter-anneaux spécifie comment et quand les agents
Umaxa , l’acceptation de cette proposition dépend des
appartenant à des anneaux différents interagissent i
stratégies de concession de l’agent. Nous rappelons
entre eux.
que dans le protocole proposé, les agents négocient
La négociation s’effectue sur une durée limitée et en
sur la base d’informations incomplètes. Les fonctions
plusieurs tours séparés par des points de contrôle.
d’utilité sont des informations privées. Chaque agent
Ces derniers permettent d’évaluer à chaque tour de
génère ses propositions, et fixe ses aspirations en se
négociation les échanges effectués et de vérifier si un
basant sur ses propres connaissances qui sont sou-
accord a été trouvé. À l’issue d’un point de contrôle,
vent limitées. Cependant, au cours de ses échanges
une solution peut être trouvée, sinon une autre phase
avec les autres agents, il peut recevoir des proposi-
de négociation est effectuée si le temps imparti à la
tions qui peuvent être au-delà de ses aspirations.
négociation n’a pas expiré. Nous considérons qu’il
Actes de communication : Soit O =
existe une solution de négociation dès lors qu’une
{P ropose, Accepte, Ref use, Renf orce, Attaque} l’en-
proposition est acceptée par la majorité des agents.
semble des actes du langage que les agents utilisent
Les points de contrôle s’effectuent à des périodes
pour interagir.
régulières prédéfinies. En résumé, notre modèle de
Propose(ai , Agk , pαi , argpαi+ ) : l’agent ai ∈ Agk soumet
négociation se déroule en trois phases :
une proposition pαi avec un ensemble d’arguments
Phase 1 : c’est la répartition initiale des agents dans
positifs argpαi+ ⊆ Argpαi+ à tout agent aj ∈ Agk .
les anneaux. Elle consiste à définir le nombre d’an-
Accepte(ai , Agk , pαr ) : l’agent ai ∈ A accepte la propo-
neaux à créer et à affecter les agents dans les anneaux.
sition pαr soumise par ar ∈ Agk et envoie un message
Phase 2 : c’est la négociation proprement dite. Les
à tout agent aj ∈ Agk .
agents formulent et soumettent leurs propositions.
Refuse(ai , Agk , pαr ) : l’agent ai ∈ A refuse la proposi-
Ils reçoivent celles des autres et prennent leurs
tion pαr soumise par ar ∈ Agk et envoie un message à
décisions.
tout aj ∈ Agk .
Phase 3 : c’est le point de contrôle. Il consiste à
Attaque(ai , Agk , pαr , argpαr− ) : l’agent ai ∈ A attaque
vérifier s’il existe, des propositions dont les taux d’ac-
la proposition pαr soumise par ar ∈ Agk et envoie un
ceptations ont atteint le seuil de la majorité fixé par
message à tout aj ∈ Agk avec un ensemble d’argu-
le concepteur du système.
ments négatifs argpαr− ⊆ Argpαr− .
Renforce(ai , Agk , pαr , argpαr+ ) : l’agent ai ∈ A renforce
3 Formalisation la proposition pαr soumise par ar ∈ Agk et envoie un
Soient A = {a1 , ..., an } l’ensemble des agents du message à tout aj ∈ Agk , avec un ensemble d’argu-
système et G = {g1 , ..., gm } l’ensemble des anneaux ments positifs argpαr+ ⊆ Argpαr+ .
dans lesquels les agents sont affectés. Nous désignons pαi signifie que la proposition pα est soumise par
par {r1 , ..., rQ } l’ensemble des tours de négociation, ai . Chaque proposition pα soumise par un agent est
rf
par {Cpt1 , ..., CptQ } l’ensemble des points de contrôle. associée à un tuple (Tpac α
, Tpre
α
, Tpα , Tpat
α
, νpα , ws(pα ), pα )
Chaque tour rq de négociation est suivi d’une phase dont les éléments représentent, respectivement, le
de contrôle Cptq . Soient φmaj le seuil de majorité et dl taux d’acceptation, le taux de renforcement, le taux
le temps imparti à la négociation. de refus, le taux d’attaque, sa valeur de support
Chaque agent ai possède un ensemble de propo- Tpac
α
+Tpre
α
avec νpα = rf , sa valeur de satisfaction sociale
sitions Pai qu’il peut soumettre et une fonction Tpα ,Tpat
α +1
d’utilité uai ∈ [0, 1] lui permettant d’évaluer les détaillée plus loin et l’estampille. Les taux ci-dessus
propositions qu’il reçoit. sont calculés par rapport au nombre d’agents dans
Fonction d’utilité et Aspirations : Soit X = {x1 , ..., xr } le système. Par exemple, Tpac α
est le rapport entre
l’ensemble des critères pour évaluer une proposi- le nombre d’ acceptations et le nombre d’agents n.
tion. Chaque agent ai possède un sous-ensemble Les autres taux tels que le taux de renforcement,
de critères Xi ⊆ X avec lesquels il définit sa fonc- d’attaque, et de refus sont calculés de la même façon.
tion d’utilité. L’objectif de chaque agent est de Les agents formulent des arguments positifs ou
maximiser son utilité mais à un certain moment négatifs pour respectivement renforcer ou attaquer
les propositions. Les renforcements et les attaques n’aurait pas acceptées au tour précédent. Un agent ai
sont pris en compte dans l’évaluation de la valeur de définit une nouvelle zone d’accords possibles, lors-
support d’une proposition. qu’il estime que sa proposition courante notée pc (i)
(acceptée ou soumise), n’a aucune chance d’être ac-
4 Mécanisme de négociation ceptée par au moins la majorité des agents, lorsque le
temps imparti à la négociation sera atteint. La tac-
4.1 Répartition des agents en anneaux tique d’un agent ai dépend de la façon dont il es-
La répartition de A = {a1 , ..., an } en plusieurs groupes time l’évolution du taux d’acceptation d’une propo-
G = {g1 , ..., gm } s’effectue en deux étapes : (1) le choix sition qui peut avoir la chance d’atteindre au moins
du nombre de groupes ; (2) l’affectation des agents le seuil de la majorité φmaj à la date limite dl de la
dans les groupes. Chaque agent doit appartenir à un négociation.
et un seul groupe, chaque groupe doit avoir au moins Nous désignons par α p (t) une fonction d’estimation
deux agents. Ainsi, pour un nombre n d’agents on de l’évolution du taux d’acceptation d’une proposi-
peut former au plus m = bn/2c anneaux ou groupes. tion en fonction du temps t tel que : 0 ≤ α p (t) ≤ 1, 0 ≤
L’affectation T des agents S dans les anneaux s’effectue t ≤ dl . La fonction α p est continue et croissante. Elle
telle que : m k≥1 Ag k = ∅, m
k≥1 Agk = A, |Agk | ≥ 2. peut être définie de différentes façons, représentant
chacune une tactique de négociation [7, 6]. α p per-
4.2 Négociation met de calculer à chaque tour rq de négociation
Les agents négocient sur la base des objectifs qu’ils commençant à la date tq une valeur α p (tq ) que l’agent
souhaitent atteindre à la fin de la négociation, va comparer avec le taux d’acceptation réel Tpac(i) de
c
désignés ici par le terme aspiration. L’aspiration d’un sa proposition courante à cette même date tq . Ainsi,
agent désigne la valeur d’utilité qu’il estime obte- l’agent décidera de réviser à la baisse ou non ses aspi-
nir de la solution finale de négociation. Dans ce rations.
protocole, pour faciliter l’obtention d’une solution La fonction α p guide l’agent dans son processus
de négociation, nous incitons les agents à avoir de concession. Elle permet à l’agent de décider s’il
une certaine flexibilité sur leurs aspirations. Chaque doit continuer à défendre sa proposition courante ou
agent ai définit sa zone d’accord possible, désignée s’il doit diminuer ses aspirations, et donc d’accep-
ici par l’intervalle [Umina , Umaxa ], c’est-à-dire l’in- ter ou de soumettre de nouvelles propositions. Dans
i i
tervalle de valeurs d’utilité acceptables. Au début ce mécanisme de négociation, nous considérons un
de la négociation, chaque agent ai cherche à satis- φ
exemple de définition de α p telle que : α p (t) = dmaj ×t.
l
faire au maximum son objectif en soumettant ou α p est une fonction linéaire, croissante et conti-
en n’acceptant que des propositions dont les uti- nue. Ici nous considérons que les temps des phases
lités sont supérieures ou égales à Umaxa . Au cours de contrôles sont négligeables. Lorsqu’un agent ai
i
de la négociation si l’agent n’atteint pas son pre- décide de réviser à la baisse ses aspirations à la date tq
mier objectif (Umaxa ) au bout d’un certain temps, il à laquelle commence le tour rq de négociation, il doit
i
doit réviser à la baisse son utilité maximum Umaxa . savoir de combien il va les réduire. Le calcul de la
i q
Ainsi, l’agent diminue de manière incrémentale et nouvelle valeur d’utilité Umaxa au tour rq dépend de
i
stratégique ses aspirations selon l’état d’avancement l’écart entre le taux d’acceptation de sa proposition
de ses négociations. La question qui se pose est : à quel courante Tpac(i) , et du taux α p (tq ) qu’il estimait avoir
c
moment, et sous quelles conditions, l’agent va diminuer pour espérer que sa proposition atteigne au moins
sa valeur d’utilité maximale Umaxa espérée et de com- à la fin de la négociation le seuil de majorité φmaj .
i
bien ?. q
L’équation 4.2 ci-dessous montre comment Umaxa est
i
Tactiques de mise-à-jour des aspirations. Nous évaluée.
considérons ici, que la révision à la baisse des aspi- – si α p (tq ) > Tpac(i) alors l’agent met à jour ses aspira-
c
rations d’un agent dépend des facteurs tels que le tions et
temps et le résultat qu’il obtient à cet instant, c’est-à- q q−1
Umaxa = Umina + (Umaxa − Umina ) × (1 − (α p (tq ) −
dire le nombre d’acceptations obtenues par la propo- i i i i
Tpac(i) )).
sition qu’il supporte. Une proposition supportée par c
un agent, peut être celle qu’il a soumise ou celle qu’il – si α p (tq ) < Tpac(i) alors l’agent maintient ses aspira-
c
a acceptée. Nous définissons des tactiques permet- q q−1
tions et Umaxa = Umaxa .
i i
tant à chaque agent ai de calculer à chaque tour rq ,
q q−1
une nouvelle valeur d’utilité Umaxa qu’il espère avoir. Umaxa est la précédente valeur d’utilité que l’agent
i i
q
Cette valeur est telle que Umina ≤ Umaxa ≤ Umaxa . souhaitait avoir pendant le tour rq−1 . Au premier
i i i 1
tour de la négociation r1 , Umax = Umaxa . Au tour
Cela permet à l’agent de faire des concessions, soit en a i i
q
acceptant, soit en soumettant des propositions qu’il rq , Umaxa est recalculée que si α p (tq ) > Tpac(i) . Si-
i c
non l’agent maintient la précédente valeur. Par souci négociation à l’instant δt , si le taux d’acceptation Tpac(i)
c
de simplification, nous considérons dans cet article de sa proposition courante est plus petit que α p (δt )
que les agents utilisent la même fonction d’estima- et si les taux d’acceptation de toutes les propositions
tion (fonction linéaire) mais chaque agent ai définit précédentes qu’il a soumises sont inférieurs à α p (δt ).
ses seuils d’utilité [Umina , Umaxa ] qu’il ne partage
i i Négociation au sein d’un groupe. La négociation
pas avec les autres agents. Il s’agit d’une informa- s’effectue simultanément dans chaque anneau,
tion privée. Dans d’autres variantes de ce protocole, chaque agent soumet ses propositions aux membres
chaque agent peut chacun définir sa propre fonc- de son anneau. Chaque agent ai évalue avec sa
tion d’estimation en se basant par exemple, sur ses fonction d’utilité uai chaque proposition qu’il reçoit.
propres croyances. Il peut ensuite soit l’accepter, soit la refuser, soit la
Dans cet article, nous nous sommes limités à un renforcer, soit l’attaquer. Les agents interagissent
exemple de définition simple de α p où nous n’avons selon les règles du protocole définies comme suit :
considéré que trois paramètres : le seuil de la ma- Ri1 : chaque agent peut soumettre un nombre limité
jorité φmaj fixé, la date limite dl de la négociation de propositions δp et peut faire un nombre limité de
et le temps t. Ces paramètres sont des informations refus δr au cours de la négociation.
publiques et connues par tous les agents. D’autres Ri2 : chaque agent ne peut soumettre ses propositions
définitions de α p peuvent être mises en œuvre dans qu’aux membres de son anneau à tout moment de la
d’autres contextes prenant en compte d’autres pa- négociation.
ramètres relevant de croyances propres à chaque Ri3 : chaque agent peut accepter une proposition
agent. faite par un autre agent à n’importe quel moment de
La prise de décision. Un agent prend des décisions la négociation.
en fonction de ses aspirations [Umina , Umaxa ] qu’il Ri4 : une proposition ne peut être acceptée, refusée,
i i
met à jour à chaque tour rq de la négociation, et attaquée ou renforcée plusieurs fois par le même
aussi en fonction de certaines règles d’interaction agent.
détaillées plus loin. Ces règles permettent de gérer les interactions entre
♦ Accepter une proposition : un agent aj accepte une les agents durant la négociation en les rendant plus
proposition pi d’un autre agent ai au tour rq de la cohérentes. Elles permettent aussi de limiter les taux
négociation si uaj (pi ) > uaj (pc (j)). Ainsi, sa nouvelle de messages et de traitements. Le fait de limiter le
proposition courante devient pc (j) = pi . Nous distin- nombre de refus facilite la recherche d’accords en
guons deux situations avec des niveaux d’acceptation évitant certaines stratégies des agents. Les agents
différents : peuvent aussi faire des concessions en acceptant, par
– Si uaj (pi ) > Umaxa , il s’agit d’une acceptation ac- exemple, une proposition qu’ils auraient refusée.
j
compagnée d’arguments positifs renforçant cette Les politiques d’interaction inter-anneaux. Nous
proposition car sa valeur d’utilité est au-delà des proposons la politique, FIC(Free Inter-rings Com-
attentes de aj . munication), qui permet la communication libre et
q réglementée entre les agents appartenant à des an-
– Si Umaxa ≤ uaj (pi ) ≤ Umaxa il s’agit d’une accepta-
i j neaux différents. FIC autorise dans un premier temps
tion sans argument de renforcement car cette pro- à chaque agent qui le souhaite d’écouter à tout mo-
position est admise par concession. ment de la négociation les propositions soumises en
dehors de son anneau. Il peut réagir sur ces proposi-
Régle 1 : Un agent peut accepter plusieurs propositions tions soit en les renforçant, soit en les attaquant tout
au cours de la négociation. en restant dans son anneau. Cependant, un agent ne
peut soumettre ses propositions que dans son propre
♦ Refuser une proposition : un agent aj refuse une anneau. Dans un deuxième temps, l’agent peut se
proposition pi d’un autre agent ai au tour rq de la déplacer dans un autre anneau pour soumettre à nou-
q
négociation si uaj (pi ) < umaxa . Il refuse et attaque veau ses propositions afin qu’elles atteignent la majo-
j
avec des arguments négatifs toute proposition dont rité. Lorsqu’il rejoint un anneau il est autorisé à ac-
l’utilité est inférieure à Umina à n’importe quel tour cepter, refuser, attaquer, ou renforcer toutes proposi-
j
de négociation. tions soumises dans cet anneau. Les migrations des
agents entre les anneaux sont régies par des règles
Régle 2 : Un agent ne peut pas refuser une proposition de mobilité limitant le nombre de déplacements et le
qu’il a déjà acceptée. nombre de fois qu’un agent peut visiter un anneau.
Rm1 : un agent ai ne peut visiter plus de δv fois le
♦ Soumettre une nouvelle proposition : un agent ai même anneau pendant toute la négociation.
soumet une nouvelle proposition pi avec une valeur Rm2 : un agent ai ne peut effectuer plus de δd
q q−1
d’utilité Umaxa ≤ uai (pi ) ≤ Umaxa au tour rq de la déplacements pendant toute la négociation.
i i
Chaque agent qui décide de changer d’anneau, doit Si |Sr | = ∅ alors il n’y a aucune solution trouvée. Si
identifier l’anneau dans lequel ses intérêts seront r , q alors la négociation continue au tour suivant et
mieux défendus. La politique d’interaction FIC aug- le résultat sera évalué au prochain point de contrôle
mente la flexibilité de communication entre agents Cptr+1 . Si r = q alors la négociation se termine en
dans différents anneaux. Elle permet aux agents de ÉCHEC. Si |Sr | = 1 alors il existe une seule proposi-
négocier progressivement en se déplaçant entre les tion majoritaire qui sera retenue comme la solution
anneaux. Nous précisons que l’interaction des agents finale de la négociation. La négociation se termine
appartenant à des anneaux différents est limitée alors en SUCCÈS. Si |Sr | > 1 alors il y a plusieurs pro-
par les intérêts des agents. Nous supposons que les positions acceptables comme solution. Le processus
surcoûts de communication qu’induit cette politique de décision social présenté dans section 4.3 est uti-
d’interaction, sont négligeables par rapport à la com- lisé pour sélectionner la proposition qui sera retenue
plexité du raisonnement des agents, et au coût de comme solution finale.
traitement d’informations dans le cas où ils sont tous
réunis dans un seul groupe. 4.3 Concept de solution équitable et juste
Migrations des agents. Compte tenu des règles de Le degré de satisfaction des agents. La satisfaction
mobilité présentées ci-dessus, un agent a besoin de d’ un agent ai pour une proposition p est désignée ici
déterminer le moment où il doit changer d’anneau par une valeur de score qu’il attribue à cette propo-
et quel anneau il doit rejoindre. Cela consiste à sition. Cette valeur de score dépend de l’écart entre
identifier d’abord l’anneau dans lequel ses proposi- ses aspirations, c’est-à-dire, les valeurs d’utilité atten-
tions seront mieux défendues, et ensuite de rejoindre dues et la valeur d’utilité de la proposition p. Le score
cet anneau. Les désaccords, dans un anneau, offrent exprime le degré de satisfaction d’un agent ai que
la possibilité à un agent en dehors de cet anneau nous évaluons à trois niveaux : –1 lorsque p est au-
de présenter une proposition qui peut satisfaire au delà de l’objectif fixé, uai (p) ≥ Umaxa ; –2 lorsque p est
i
mieux les objectifs des agents de cet anneau. Nous dans la zone de concessions, uai (p) ∈ [Umina , Umaxa ] ;
i i
considérons ici, qu’un anneau est faible à l’instant –3 lorsque la proposition p sera refusée, c’est-à-
q
δt de la négociation lorsque toutes les propositions dire,uai (p) < Umina ou uai (p) ∈ [Umina , Umaxa ]. Nous
i i i
soumises dans cet anneau ont des taux d’acceptation désignons alors trois valeurs de score notées σ2 , σ1 , σ0
qui sont inférieurs à un certain seuil ϕweak = α p (δt ). représentant, respectivement, les valeurs de score des
Chaque agent évalue les anneaux qu’il écoute selon trois niveaux mentionnés ci-dessus. Ces valeurs sont
les critères suivants : (1) le nombre d’agents dans l’an- telles que σ2 > σ1 > σ0 = 0 et sont des informations
neau, car l’agent vise à convaincre autant d’agents publiques, communes à tous les agents.
que possible ; (2) l’écart entre les taux d’acceptation Notons que chaque agent ai définit sa propre fonction
des propositions soumises dans l’anneau et ceux de d’utilité uai (information privée) et ses seuils d’uti-
l’agent souhaitant se déplacer dans cet anneau. Ces lité Umina , Umaxa (informations privées). Les valeurs
i i
critères permettent à l’agent d’évaluer son degré d’in- d’utilité des agents ne sont pas comparables puisque
fluence dans l’anneau qu’il souhaite rejoindre et les chaque agent définit sa propre fonction d’utilité. Par
chances que ses propositions soient acceptées. Le conséquent, deux agents ayant la même valeur d’uti-
choix de l’anneau à rejoindre est non-trivial lorsque lité pour une proposition peuvent avoir des degrés de
l’agent écoute plusieurs anneaux en même temps. satisfaction différents. Pour évaluer le résultat de la
Chaque agent associe un vecteur d’utilité à chaque négociation, nous définissons une nouvelle méthode
anneau écouté selon les critères ci-dessus. Ainsi, la d’évaluation du bien-être social différente de celles
dominance de Lorenz [8] est utilisée pour comparer les utilisant directement les valeurs d’utilité des agents.
vecteurs d’utilité des anneaux écoutés par un agent. Par exemple, les fonctions de bien-être sociale de
Cela permet à chaque agent d’établir un ordre de Nash ou utilitariste effectuent respectivement le pro-
préférence totale sur l’ensemble des anneaux écoutés. duit et la somme des utilités individuelles des agents.
Les points de contrôle. Soit Cpt = {Cpt1 , ..., Cptq } l’en- La satisfaction sociale d’une proposition. Nous
semble des points de contrôle prévus. Chaque point désignons par ws : P 7→ R+ la fonction d’agrégation
de contrôle Cptr est représenté par un tuple (tr , Sr ), des valeurs de score que nous proposons. Elle at-
tr est la date, Sr est l’ensemble des propositions tribue une valeur réelle positive à chaque proposi-
acceptables.Cpt = {Cpt1 = (t1 , S1 ), ..., Cptq = (tq , Sq )} tion soumise désignant sa valeur de satisfaction so-
avec(t1 <, ..., tq < dl ). ciale. La définition de ws s’inspire du principe de
Lorsqu’un point de contrôle Cptr s’effectue, chaque Rawls (maximim) [11] indiquant que le bien-être so-
agent ai ∈ A communique ses propositions qui ont cial d’une allocation dépend du bien-être de l’indi-
atteint le seuil de la majorité. vidu qui a le niveau de satisfaction le plus bas, c’est-
à-dire la personne avec l’utilité minimale. Dans notre
mécanisme,
P la fonction ws est définie comme suit : la proposition gagnante. S’il existe encore des ex ae-
σai quo leurs estampilles sont utilisées. Il existe toujours
ws (pα ) = n−n . n est le nombre d’agents du système,
apα un écart de temps entre les dates d’obtention de la
napα désigne le nombre d’agents qui ont accepté la majorité pour deux propositions.
proposition pα sans prendre en compte l’agent ayant
soumis la proposition. Nous avons donc napα ≤ n − 1. 5 Résultats empiriques
σai est la valeur de score de chaque agent ai . ws ga- Nous avons implémenté en Java le protocole pro-
rantit le choix de la proposition respectant à la fois la posé. Les simulations sont réalisées en faisant va-
règle de la majorité et celle de l’équité selon Rawls. rier le nombre d’agents et le nombre d’anneaux. Le
Ainsi, maximiser ws consiste à minimiser le nombre scénario de négociation se base sur l’exemple du
d’agents ayant une satisfaction nulle, c’est-à-dire, les projet de tramway. Une liste de propositions et un
agents ayant refusé la proposition. ensemble de critères d’évaluation sont prédéfinis.
Proposition 3 La proposition ayant la plus grande va- Chaque agent sélectionne aléatoirement un sous-
leur de satisfaction sociale a aussi le taux d’acceptation ensemble de propositions et un sous-ensemble de
le plus élevé lorsque σ1 et σ2 prennent certaines valeurs critères. Nous avons effectué plusieurs expériences,
(voir preuve). dans le cas où les agents forment un seul anneau
et dans le cas où les agents forment plusieurs an-
(k+1)σ (k+1)σ neaux. Pour chaque expérience, nous avons mesuré
Preuve Soit f , g, f (k) = n−k 1 , g(k) = n−k 2 deux le taux de convergence. Ce taux de convergence est le
fonctions, k ∈ [1, n − 1] and Pk est l’ensemble des pro- rapport entre le nombre de fois qu’une solution est
positions avec un nombre k acceptations. trouvée et le nombre d’itérations de négociation ef-
∀pα ∈ Pk , ∀σ1 ∈]0, σ2 [, f (k) ≤ ws (pα ) ≤ g(k). ∀pα ∈ fectuées. Nous avons fait varier le nombre d’agents n
Pk , pβ ∈ Pk+1 , ∃σ1 ∈]0, σ2 [ / f (k) ≤ ws (pα ) ≤ g(k) < de 5 à 50 et le nombre d’anneaux m de 1 à 25. Pour
(k+2)
f (k +1) ≤ ws (pβ ) ≤ g(k +1). f (k +1) > g(k) ⇔ n−k−1 σ1 > un nombre n d’agents, on peut créer au plus bn/2c.
(k+1) Chaque anneau doit avoir au moins deux agents.
n−k σ2 .
(k+1) m = 1, correspond au modèle de négociation dans
Soit z(k) = n−k σ2 × n−k−1 k+2 alors ∀σ2 > 0, σ1 ∈ lequel tous les agents négocient dans un seul an-
]M, σ2 [, f (k + 1) > g(k). neau. La figure 1 montre que le nombre d’anneaux
M le maximum de la fonction z(k) avec k ∈ [1, n − 1].
En résumé, la proposition 3 est vraie ∀σ2 > 0 et σ1 ∈
]M, σ2 [.
Nous avons montré que pour toute proposition pα qui
a k acceptations, f (k) ≤ ws (pα ) ≤ g(k). S’il existe, à
l’instant t + 1, une proposition pβ qui a k + 1 accepta-
tions alors quelles que soient les valeurs de satisfac-
tion des agents pour pα , ws (pβ ) > ws (pα ), nous avons
donc f (k) ≤ ws (pα ) ≤ g(k) < f (k+1) ≤ ws (pβ ) ≤ g(k+1).
La fonction de satisfaction sociale ws permet de clas-
ser toutes les propositions dont les taux d’accepta-
tion sont supérieurs ou égaux à φmaj . La proposition
qui a la plus grande valeur de satisfaction sociale de- Figure 1 – Convergence de la négociation selon le
vient la solution. Nous avons montré que si cette pro- nombre d’anneaux formés
position existe, elle a aussi le plus grand taux d’ac-
ceptation. Notons que pour obtenir ce résultat, les formés par les agents a un impact sur le résultat de la
valeurs de σ1 et σ2 doivent respecter une certaine négociation. Par exemple, lorsque le nombre d’agents
contrainte telle que : σ1 ∈]M, σ2 [. Les résultats de ce est supérieur à 20, nous observons que la forma-
travail nous ont permis aussi d’identifier certaines tion de bn/2c anneaux conduit à des taux de conver-
conditions dans lesquelles un système de vote mixte gence plus faibles mais qui sont toujours meilleurs
combinant le vote par approbation et le vote par va- qu’un seul anneau formé. La courbe coloriée en violet
leurs peut garantir un choix collectif respectant à la représente le taux de convergence de la négociation
fois la règle de la majorité et la somme des valeurs de lorsque bn/2c anneaux sont formés. Les taux sont
score. Il peut arriver que plusieurs propositions ob- plus faibles comparés au cas où le nombre d’anneaux
tiennent la même valeur de satisfaction. Ainsi pour est plus petit que bn/2c. Les courbes de la figure 2
garantir l’unicité de la solution de négociation, nous montrent l’évolution du nombre d’acceptations des
utilisons les valeurs de support des propositions dont propositions pour n = 5 agents, n = 10 agents et
les valeurs de satisfaction sont égales pour désigner n = 30 agents. Les courbes en pointillés représentent
lisant un scénario de négociation. Les résultats empi-
riques montrent que ce modèle de négociation fondé
sur une approche distributive permet aux agents
de négocier plus facilement comparé aux modèles
dans lesquels tous les agents sont dans un seul
groupe. Dans nos futurs travaux, nous testerons ce
mécanisme avec d’autres exemples de négociation
pour montrer d’autres propriétés.
Références
[1] B. An, N. Gatti, and V. Lesser. Alternating-offers
bargaining in one-to-many and many-to-many
Figure 2 – Acceptation moyenne des propositions settings. AMAI, 77(1-2) :67–103, 2016.
soumises en fonction du temps.
[2] R. Aydoğan, D. Festen, K. V. Hindriks, and C. M.
Jonker. Alternating offers protocols for mul-
les résultats obtenus lorsque tous les agents forment tilateral negotiation. In Modern Approaches to
un seul groupe et celles en traits pleins représentent ACAN, pages 153–167. Springer, 2017.
les résultats lorsque les agents sont répartis en plu- [3] R. Aydoğan, K. V. Hindriks, and C. M. Jon-
sieurs groupes. Ces courbes montrent que les propo- ker. Multilateral mediated negotiation protocols
sitions sont acceptées plus facilement dans le proto- with feedback. In Novel Insights in ACAN, pages
cole proposé. Cela prouve que notre protocole favo- 43–59. Springer, 2014.
rise la convergence de la négociation.
[4] D. De Jonge and C. Sierra. Nb3 : a multilate-
ral negotiation algorithm for large, non-linear
agreement spaces with limited time. AAMAS,
29(5) :896–942, 2015.
[5] U. Endriss. Monotonic concession protocols for
multilateral negotiation. In AAMAS, pages 392–
399. ACM, 2006.
[6] P. Faratin, C. Sierra, and N. R. Jennings. Negotia-
tion decision functions for autonomous agents.
RAS, 24(3-4) :159–182, 1998.
[7] P. Faratin, C. Sierra, and N. R. Jennings. Using si-
milarity criteria to make negotiation trade-offs.
Figure 3 – Qualité de la solution de négociation In ICMAS, pages 119–126. IEEE, 2000.
La figure 3 montre la comparaison entre notre [8] B. Golden and P. Perny. Infinite order lorenz
modèle de négociation distribuée et le modèle cen- dominance for fair multiagent optimization. In
tralisé (un seul anneau est formé) selon la qualité AAMAS, pages 383–390, 2010.
moyenne de la solution. La qualité de la solution pour [9] B. Horling and V. Lesser. A survey of multi-
chaque agent est l’écart entre l’utilité de la solution agent organizational paradigms. The Knowledge
et son aspiration maximale. La qualité moyenne est engineering review, 19(4) :281–316, 2004.
le rapport entre la somme des qualités individuelles [10] M. Klein, P. Faratin, H. Sayama, and Y. Bar-Yam.
et le nombre total d’agents. Nous observons que les Protocols for negotiating complex contracts.
solutions obtenues lorsque le nombre d’agents aug- IEEE Intelligent Systems, 18(6) :32–38, 2003.
mente sont meilleures dans notre modèle que dans le
modèle centralisé. [11] J. Rawls. Théorie de la justice. 1997.
[12] J. S. Rosenschein and G. Zlotkin. Rules of en-
6 Conclusion counter : designing conventions for automated ne-
Cet article a présenté un modèle de négociation mul- gotiation among computers. MIT press, 1994.
tilatérale dans lequel les agents interagissent de façon [13] A. Schuldt, J. O. Berndt, and O. Herzog. The
incrémentale et itérative. Les agents sont répartis en interaction effort in autonomous logistics pro-
plusieurs groupes (anneaux) dans lesquels ils mènent cesses : potential and limitations for coopera-
leurs négociations. L’objectif de ce travail est de facili- tion. In ACCL, pages 77–90. 2011.
ter la recherche d’accords. Nous avons évalué les per-
formances de notre mécanisme de négociation en uti-