In this paper, we propose a multilateral negotiation model in which the agents interact in a fully decentralized way. The proposed protocol draws on ”divide and rule” approach. The agents are divided into different groups called ”rings” in which negotiations take place simultaneously. We propose interaction policies allowing the communication between agents from different rings. We seek through this approach to limit the agents’ scope of interaction and hence to reduce agents reasoning complexity to facilitate agreement research. We have evaluated our protocol by comparing it with a model where all of the agents negotiate in the same group.
La ne´gociation multilate´rale est un processus
d’e´change qui permet aux participants ayant des
inte´reˆts diffe´rents pour la re´alisation d’un but
commun, de construire ensemble des solutions
collectivement satisfaisantes. Ces participants ont
le plus souvent un comportement e´go¨ıste, et ne
partagent pas les informations concernant leurs
fonctions d’utilite´ et leurs pre´fe´rences. Chacun
tente de conduire la ne´gociation vers un accord
qui satisfait ses objectifs. Dans un tel contexte, la
ne´gociation devient tre`s complexe lorsque le nombre
de participants est important. Dans cet article, nous
nous inte´ressons aux ne´gociations multilate´rales
fonde´es sur des approches heuristiques[
Notre mode`le s’appuie sur les hypothe`ses suivantes : (1) les agents ne´gocient sur un seul proble`me (attribut) et doivent trouver une solution collective et acceptable, c’est-a`-dire, accepte´e par la majorite´ des agents ; (2) les agents sont e´go¨ıstes et chacun cherche a` de´fendre ses propres inte´reˆts ; (3) la ne´gociation s’effectue sans me´diateur, les agents interagissent entre eux de fac¸on totalement de´centralise´e ; (4) les agents ne partagent pas leur fonction d’utilite´ ; (5) la ne´gociation s’effectue sur une dure´e limite´e. De telles ne´gociations ne´cessitent des protocoles spe´cifiques pour faciliter la prise de de´cision et la de´finition de concepts de solution de ne´gociation e´quitable et collectivement satisfaisante.
Le me´canisme de ne´gociation que nous
proposons, dans cet article, est fonde´ sur une approche
incre´mentale et ite´rative permettant de distribuer
la ne´gociation mais aussi, d’appre´hender la
complexite´ du raisonnement des agents et ainsi, de
faciliter la convergence de la ne´gociation tout en
limitant le temps. Pour aborder ces proble`mes,
nous nous inte´ressons a` l’organisation du syste`me
multi-agents. La forme organisationnelle du syste`me
peut significativement affecter la complexite´ de la
recherche d’accords, la flexibilite´, la re´activite´ et
peut induire des co uˆts de calcul et de
communication [
Pour illustrer le me´canisme de ne´gociation propose´, nous conside´rons un sce´nario de ne´gociation base´ sur un projet de mise en place d’une nouvelle ligne de tramway pour une agglome´ration. Ce projet implique par exemple, les maires des communes concerne´es, le pre´fet de la re´gion, les conseillers re´gionaux et les compagnies de transports. Leur but est de de´terminer le trace´ de la nouvelle ligne de tramway, c’est-a`-dire, les coordonne´es de ses arreˆts. Ces participants ayant des inte´reˆts diffe´rents vont ne´gocier pour s’accorder sur une solution. Par exemple, le but des maires est d’optimiser le couˆ t de financement du projet et la desserte des e´tablissements publics en pre´fe´rant que la ligne desserve plusieurs communes. Le pre´fet s’inte´resse a` la se´curite´ des personnes en pre´fe´rant que certains arreˆts soient proches des postes de police. Les conseillers re´gionaux s’inte´ressent a` la desserte des e´tablissements publics tels que les lyce´es. Quant aux compagnies de transport, elles souhaitent que les arreˆts soient proches des stations de me´tro et bus pour faciliter les correspondances.
Le me´canisme de ne´gociation propose´ consiste a` structurer les agents en petits groupes appele´s anneaux dans lesquels les agents s’e´changent des propositions. La ne´gociation s’effectue simultane´ment au sein de chaque anneau. Dans chaque anneau, les agents soumettent leurs propositions. Ils rec¸oivent celles des autres et prennent des de´cisions. Un agent peut accepter, refuser, renforcer ou attaquer une proposition soumise par un autre agent. La ne´gociation s’effectue de manie`re de´centralise´e sans me´diation, autrement dit les agents de´cident eux-meˆmes de leurs propositions et re´agissent avec les autres selon leurs propres croyances tout en respectant les re`gles du protocole. Chaque proposition soumise par un agent est une suggestion de solution de ne´gociation. Elle devient une solution acceptable si elle est accepte´e par la majorite´ des agents. Le choix de la re`gle de la majorite´ est justifie´ par le fait que nous conside´rons les ne´gociations impliquant un grand nombre d’agents dans lesquelles l’application de la re`gle de l’unanimite´ rend difficile la recherche d’accords collectifs. Pour rendre flexible le me´canisme de ne´gociation propose´, le protocole permet aux agents qui le souhaitent de prendre connaissance via l’e´coute flottante des interactions qui s’effectuent dans les autres anneaux. Cela permet aux agents d’appre´hender les ne´gociations mene´es au-dela` de leur anneau. Ainsi, un agent peut re´agir sur les propositions e´coute´es tout en restant dans son anneau. Comme il peut de´cider de rejoindre un autre anneau dans lequel ses inte´reˆts seront mieux de´fendus. Cependant, ils utilisent diffe´rentes strate´gies pour choisir le meilleur anneau qu’ils vont rejoindre s’ils en e´coutent plus d’un. Lorsqu’un agent se de´place dans un nouvel anneau, il peut soit soumettre de nouvelles propositions, soit de´fendre ses propositions ayant de´ja` obtenu un certain taux d’acceptation en vue d’atteindre la majorite´. Les interactions inter-anneaux et les de´placements des agents d’un anneau a` un autre sont re´gis par les re`gles du protocole et la politique d’interaction propose´e. Une politique d’interaction inter-anneaux spe´cifie comment et quand les agents appartenant a` des anneaux diffe´rents interagissent entre eux.
La ne´gociation s’effectue sur une dure´e limite´e et en plusieurs tours se´pare´s par des points de controˆle. Ces derniers permettent d’e´valuer a` chaque tour de ne´gociation les e´changes effectue´s et de ve´rifier si un accord a e´te´ trouve´. A` l’issue d’un point de controˆle, une solution peut eˆtre trouve´e, sinon une autre phase de ne´gociation est effectue´e si le temps imparti a` la ne´gociation n’a pas expire´. Nous conside´rons qu’il existe une solution de ne´gociation de`s lors qu’une proposition est accepte´e par la majorite´ des agents. Les points de controˆle s’effectuent a` des pe´riodes re´gulie`res pre´de´finies. En re´sume´, notre mode`le de ne´gociation se de´roule en trois phases : Phase 1 : c’est la re´partition initiale des agents dans les anneaux. Elle consiste a` de´finir le nombre d’anneaux a` cre´er et a` affecter les agents dans les anneaux. Phase 2 : c’est la ne´gociation proprement dite. Les agents formulent et soumettent leurs propositions. Ils rec¸oivent celles des autres et prennent leurs de´cisions.
Phase 3 : c’est le point de controˆle. Il consiste a` ve´rifier s’il existe, des propositions dont les taux d’acceptations ont atteint le seuil de la majorite´ fixe´ par le concepteur du syste`me.
Soient A = fa1; :::; ang l’ensemble des agents du syste`me et G = fg1; :::; gmg l’ensemble des anneaux dans lesquels les agents sont affecte´s. Nous de´signons par fr1; :::; rQg l’ensemble des tours de ne´gociation, par fCpt1 ; :::; CptQ g l’ensemble des points de controˆle. Chaque tour rq de ne´gociation est suivi d’une phase de controˆle Cptq . Soient maj le seuil de majorite´ et dl le temps imparti a` la ne´gociation.
Chaque agent ai posse`de un ensemble de propositions Pai qu’il peut soumettre et une fonction d’utilite´ uai 2 [0; 1] lui permettant d’e´valuer les propositions qu’il rec¸oit.
Fonction d’utilite´ et Aspirations : Soit X = fx1; :::; xr g l’ensemble des crite`res pour e´valuer une proposition. Chaque agent ai posse`de un sous-ensemble de crite`res Xi X avec lesquels il de´finit sa fonction d’utilite´. L’objectif de chaque agent est de maximiser son utilite´ mais a` un certain moment de la ne´gociation, il peut eˆtre appele´ a` faire des concessions pour e´tablir un compromis avec les autres agents. Ainsi, chaque agent fixe ses aspirations repre´sente´es ici par l’utilite´ minimale Uminai qu’il peut espe´rer, autrement dit son utilite´ de re´serve en dessous de laquelle aucune proposition n’est acceptable, et l’utilite´ maximale Umaxai en dessus de laquelle toute proposition est acceptable. Lorsque l’utilite´ d’une proposition se trouve entre Uminai et Umaxai , l’acceptation de cette proposition de´pend des strate´gies de concession de l’agent. Nous rappelons que dans le protocole propose´, les agents ne´gocient sur la base d’informations incomple`tes. Les fonctions d’utilite´ sont des informations prive´es. Chaque agent ge´ne`re ses propositions, et fixe ses aspirations en se basant sur ses propres connaissances qui sont souvent limite´es. Cependant, au cours de ses e´changes avec les autres agents, il peut recevoir des propositions qui peuvent eˆtre au-dela` de ses aspirations. Actes de communication : Soit O = fP ropose; Accepte; Ref use; Renf orce; Attaqueg l’ensemble des actes du langage que les agents utilisent pour interagir.
Propose(ai ; Agk; pi ; argpi+) : l’agent ai 2 Agk soumet une proposition pi avec un ensemble d’arguments positifs argpi+ Argpi+ a` tout agent aj 2 Agk. Accepte(ai ; Agk; pr ) : l’agent ai 2 A accepte la proposition pr soumise par ar 2 Agk et envoie un message a` tout agent aj 2 Agk.
Refuse(ai ; Agk; pr ) : l’agent ai 2 A refuse la proposition pr soumise par ar 2 Agk et envoie un message a` tout aj 2 Agk.
Attaque(ai ; Agk; pr ; argpr ) : l’agent ai 2 A attaque la proposition pr soumise par ar 2 Agk et envoie un message a` tout aj 2 Agk avec un ensemble d’arguments ne´gatifs argpr Argpr .
Renforce(ai ; Agk; pr ; argpr+) : l’agent ai 2 A renforce la proposition pr soumise par ar 2 Agk et envoie un message a` tout aj 2 Agk, avec un ensemble d’arguments positifs argpr+ Argpr+: pi signifie que la proposition p est soumise par ai . Chaque proposition p soumise par un agent est associe´e a` un tuple (Tpac; Tpre; Tprf ; Tpat; p ; ws(p ); p ) dont les e´le´ments repre´sentent, respectivement, le taux d’acceptation, le taux de renforcement, le taux de refus, le taux d’attaque, sa valeur de support avec p = TTprpfac;T+pTatpr+e1 , sa valeur de satisfaction sociale de´taille´e plus loin et l’estampille. Les taux ci-dessus sont calcule´s par rapport au nombre d’agents dans le syste`me. Par exemple, Tpac est le rapport entre le nombre d’ acceptations et le nombre d’agents n. Les autres taux tels que le taux de renforcement, d’attaque, et de refus sont calcule´s de la meˆme fac¸on. Les agents formulent des arguments positifs ou ne´gatifs pour respectivement renforcer ou attaquer les propositions. Les renforcements et les attaques sont pris en compte dans l’e´valuation de la valeur de support d’une proposition.
La re´partition de A = fa1; :::; ang en plusieurs groupes G = fg1; :::; gmg s’effectue en deux e´tapes : (1) le choix du nombre de groupes ; (2) l’affectation des agents dans les groupes. Chaque agent doit appartenir a` un et un seul groupe, chaque groupe doit avoir au moins deux agents. Ainsi, pour un nombre n d’agents on peut former au plus m = bn=2c anneaux ou groupes. L’affectation des agents dans les anneaux s’effectue telle que : Tm
k 1 Agk = ;; Skm 1 Agk = A; jAgkj 2: 4.2
Les agents ne´gocient sur la base des objectifs qu’ils souhaitent atteindre a` la fin de la ne´gociation, de´signe´s ici par le terme aspiration. L’aspiration d’un agent de´signe la valeur d’utilite´ qu’il estime obtenir de la solution finale de ne´gociation. Dans ce protocole, pour faciliter l’obtention d’une solution de ne´gociation, nous incitons les agents a` avoir une certaine flexibilite´ sur leurs aspirations. Chaque agent ai de´finit sa zone d’accord possible, de´signe´e ici par l’intervalle [Uminai ; Umaxai ], c’est-a`-dire l’intervalle de valeurs d’utilite´ acceptables. Au de´but de la ne´gociation, chaque agent ai cherche a` satisfaire au maximum son objectif en soumettant ou en n’acceptant que des propositions dont les utilite´s sont supe´rieures ou e´gales a` Umaxai . Au cours de la ne´gociation si l’agent n’atteint pas son premier objectif (Umaxai ) au bout d’un certain temps, il doit re´viser a` la baisse son utilite´ maximum Umaxai . Ainsi, l’agent diminue de manie`re incre´mentale et strate´gique ses aspirations selon l’e´tat d’avancement de ses ne´gociations. La question qui se pose est : a` quel moment, et sous quelles conditions, l’agent va diminuer sa valeur d’utilite´ maximale Umaxai espe´re´e et de combien ?.
Tactiques de mise- a`-jour des aspirations. Nous conside´rons ici, que la re´vision a` la baisse des aspirations d’un agent de´pend des facteurs tels que le temps et le re´sultat qu’il obtient a` cet instant, c’est-a`dire le nombre d’acceptations obtenues par la proposition qu’il supporte. Une proposition supporte´e par un agent, peut eˆtre celle qu’il a soumise ou celle qu’il a accepte´e. Nous de´finissons des tactiques permettant a` chaque agent ai de calculer a` chaque tour rq, q une nouvelle valeur d’utilite´ Umaxai qu’il espe`re avoir. Cette valeur est telle que Uminai U mqaxai Umaxai . Cela permet a` l’agent de faire des concessions, soit en acceptant, soit en soumettant des propositions qu’il n’aurait pas accepte´es au tour pre´ce´dent. Un agent ai de´finit une nouvelle zone d’accords possibles, lorsqu’il estime que sa proposition courante note´e pc(i) (accepte´e ou soumise), n’a aucune chance d’eˆtre accepte´e par au moins la majorite´ des agents, lorsque le temps imparti a` la ne´gociation sera atteint. La tactique d’un agent ai de´pend de la fac¸on dont il estime l’e´volution du taux d’acceptation d’une proposition qui peut avoir la chance d’atteindre au moins le seuil de la majorite´ maj a` la date limite dl de la ne´gociation.
Nous de´signons par p(t) une fonction d’estimation
de l’e´volution du taux d’acceptation d’une
proposition en fonction du temps t tel que : 0 p(t) 1, 0
t dl . La fonction p est continue et croissante. Elle
peut eˆtre de´finie de diffe´rentes fac¸ons, repre´sentant
chacune une tactique de ne´gociation [
La fonction p guide l’agent dans son processus de concession. Elle permet a` l’agent de de´cider s’il doit continuer a` de´fendre sa proposition courante ou s’il doit diminuer ses aspirations, et donc d’accepter ou de soumettre de nouvelles propositions. Dans ce me´canisme de ne´gociation, nous conside´rons un exemple de de´finition de p telle que : p(t) = dmaj t. l p est une fonction line´aire, croissante et continue. Ici nous conside´rons que les temps des phases de controˆles sont ne´gligeables. Lorsqu’un agent ai de´cide de re´viser a` la baisse ses aspirations a` la date tq a` laquelle commence le tour rq de ne´gociation, il doit savoir de combien il va les re´duire. Le calcul de la q nouvelle valeur d’utilite´ Umaxai au tour rq de´pend de l’e´cart entre le taux d’acceptation de sa proposition courante Tpacc(i), et du taux p(tq) qu’il estimait avoir pour espe´rer que sa proposition atteigne au moins a` la fin de la ne´gociation le seuil de majorite´ maj . q L’e´quation 4.2 ci-dessous montre comment Umaxai est e´value´e.
ac – si p(tq) > Tpc(i) alors l’agent met a` jour ses aspirations et Umacaxai = Uminai + (U mqa1xai Uminai ) (1 ( p(tq) q
Tpc(i))): – si p(tq) < Tpacc(i) alors l’agent maintient ses aspirations et Umaxai = U mqa1xai :
q q 1 Umaxa est la pre´ce´dente valeur d’utilite´ que l’agent i souhaitait avoir pendant le tour rq 1. Au premier tour de la ne´gociation r1, Um1axai = Umaxai . Au tour rq, U mqaxai est recalcule´e que si p(tq) > Tpacc(i). Sinon l’agent maintient la pre´ce´dente valeur. Par souci de simplification, nous conside´rons dans cet article que les agents utilisent la meˆme fonction d’estimation (fonction line´aire) mais chaque agent ai de´finit ses seuils d’utilite´ [Uminai ; Umaxai ] qu’il ne partage pas avec les autres agents. Il s’agit d’une information prive´e. Dans d’autres variantes de ce protocole, chaque agent peut chacun de´finir sa propre fonction d’estimation en se basant par exemple, sur ses propres croyances.
Dans cet article, nous nous sommes limite´s a` un exemple de de´finition simple de p ou` nous n’avons conside´re´ que trois parame`tres : le seuil de la majorite´ maj fixe´, la date limite dl de la ne´gociation et le temps t. Ces parame`tres sont des informations publiques et connues par tous les agents. D’autres de´finitions de p peuvent eˆtre mises en oeuvre dans d’autres contextes prenant en compte d’autres parame`tres relevant de croyances propres a` chaque agent.
La prise de de´cision. Un agent prend des de´cisions en fonction de ses aspirations [Uminai ; Umaxai ] qu’il met a` jour a` chaque tour rq de la ne´gociation, et aussi en fonction de certaines re`gles d’interaction de´taille´es plus loin.
Accepter une proposition : un agent aj accepte une proposition pi d’un autre agent ai au tour rq de la ne´gociation si uaj (pi) > uaj (pc(j)). Ainsi, sa nouvelle proposition courante devient pc(j) = pi. Nous distinguons deux situations avec des niveaux d’acceptation diffe´rents : – Si uaj (pi) > Umaxaj , il s’agit d’une acceptation accompagne´e d’arguments positifs renforc¸ant cette proposition car sa valeur d’utilite´ est au-dela` des attentes de aj . – Si U mqaxai uaj (pi) Umaxaj il s’agit d’une acceptation sans argument de renforcement car cette proposition est admise par concession.
Re´gle 1 : Un agent peut accepter plusieurs propositions au cours de la ne´gociation.
Refuser une proposition : un agent aj refuse une proposition pi d’un autre agent ai au tour rq de la q ne´gociation si uaj (pi ) < umaxaj . Il refuse et attaque avec des arguments ne´gatifs toute proposition dont l’utilite´ est infe´rieure a` Uminaj a` n’importe quel tour de ne´gociation.
Re´gle 2 : Un agent ne peut pas refuser une proposition qu’il a de´ja` accepte´e.
Soumettre une nouvelle proposition : un agent ai soumet une nouvelle proposition pi avec une valeur q q 1 d’utilite´ Umaxai uai (pi) Umaxai au tour rq de la ac ne´gociation a` l’instant t, si le taux d’acceptation Tpc(i) de sa proposition courante est plus petit que p( t) et si les taux d’acceptation de toutes les propositions pre´ce´dentes qu’il a soumises sont infe´rieurs a` p( t). Ne´gociation au sein d’un groupe. La ne´gociation s’effectue simultane´ment dans chaque anneau, chaque agent soumet ses propositions aux membres de son anneau. Chaque agent ai e´value avec sa fonction d’utilite´ uai chaque proposition qu’il rec¸oit. Il peut ensuite soit l’accepter, soit la refuser, soit la renforcer, soit l’attaquer. Les agents interagissent selon les re`gles du protocole de´finies comme suit : Ri1 : chaque agent peut soumettre un nombre limite´ de propositions p et peut faire un nombre limite´ de refus r au cours de la ne´gociation.
Ri2 : chaque agent ne peut soumettre ses propositions qu’aux membres de son anneau a` tout moment de la ne´gociation.
Ri3 : chaque agent peut accepter une proposition faite par un autre agent a` n’importe quel moment de la ne´gociation.
Ri4 : une proposition ne peut eˆtre accepte´e, refuse´e, attaque´e ou renforce´e plusieurs fois par le meˆme agent.
Ces re`gles permettent de ge´rer les interactions entre les agents durant la ne´gociation en les rendant plus cohe´rentes. Elles permettent aussi de limiter les taux de messages et de traitements. Le fait de limiter le nombre de refus facilite la recherche d’accords en e´vitant certaines strate´gies des agents. Les agents peuvent aussi faire des concessions en acceptant, par exemple, une proposition qu’ils auraient refuse´e. Les politiques d’interaction inter-anneaux. Nous proposons la politique, FIC(Free Inter-rings Communication), qui permet la communication libre et re´glemente´e entre les agents appartenant a` des anneaux diffe´rents. FIC autorise dans un premier temps a` chaque agent qui le souhaite d’e´couter a` tout moment de la ne´gociation les propositions soumises en dehors de son anneau. Il peut re´agir sur ces propositions soit en les renforc¸ant, soit en les attaquant tout en restant dans son anneau. Cependant, un agent ne peut soumettre ses propositions que dans son propre anneau. Dans un deuxie`me temps, l’agent peut se de´placer dans un autre anneau pour soumettre a` nouveau ses propositions afin qu’elles atteignent la majorite´. Lorsqu’il rejoint un anneau il est autorise´ a` accepter, refuser, attaquer, ou renforcer toutes propositions soumises dans cet anneau. Les migrations des agents entre les anneaux sont re´gies par des re`gles de mobilite´ limitant le nombre de de´placements et le nombre de fois qu’un agent peut visiter un anneau. Rm1 : un agent ai ne peut visiter plus de v fois le meˆme anneau pendant toute la ne´gociation. Rm2 : un agent ai ne peut effectuer plus de d de´placements pendant toute la ne´gociation. Chaque agent qui de´cide de changer d’anneau, doit identifier l’anneau dans lequel ses inte´reˆts seront mieux de´fendus. La politique d’interaction FIC augmente la flexibilite´ de communication entre agents dans diffe´rents anneaux. Elle permet aux agents de ne´gocier progressivement en se de´plac¸ant entre les anneaux. Nous pre´cisons que l’interaction des agents appartenant a` des anneaux diffe´rents est limite´e par les inte´reˆts des agents. Nous supposons que les surcouˆ ts de communication qu’induit cette politique d’interaction, sont ne´gligeables par rapport a` la complexite´ du raisonnement des agents, et au co uˆt de traitement d’informations dans le cas o u` ils sont tous re´unis dans un seul groupe.
Migrations des agents. Compte tenu des re`gles de
mobilite´ pre´sente´es ci-dessus, un agent a besoin de
de´terminer le moment ou` il doit changer d’anneau
et quel anneau il doit rejoindre. Cela consiste a`
identifier d’abord l’anneau dans lequel ses
propositions seront mieux de´fendues, et ensuite de rejoindre
cet anneau. Les de´saccords, dans un anneau, offrent
la possibilite´ a` un agent en dehors de cet anneau
de pre´senter une proposition qui peut satisfaire au
mieux les objectifs des agents de cet anneau. Nous
conside´rons ici, qu’un anneau est faible a` l’instant
t de la ne´gociation lorsque toutes les propositions
soumises dans cet anneau ont des taux d’acceptation
qui sont infe´rieurs a` un certain seuil 'weak = p( t).
Chaque agent e´value les anneaux qu’il e´coute selon
les crite`res suivants : (1) le nombre d’agents dans
l’anneau, car l’agent vise a` convaincre autant d’agents
que possible ; (2) l’e´cart entre les taux d’acceptation
des propositions soumises dans l’anneau et ceux de
l’agent souhaitant se de´placer dans cet anneau. Ces
crite`res permettent a` l’agent d’e´valuer son degre´
d’influence dans l’anneau qu’il souhaite rejoindre et les
chances que ses propositions soient accepte´es. Le
choix de l’anneau a` rejoindre est non-trivial lorsque
l’agent e´coute plusieurs anneaux en meˆme temps.
Chaque agent associe un vecteur d’utilite´ a` chaque
anneau e´coute´ selon les crite`res ci-dessus. Ainsi, la
dominance de Lorenz [
Lorsqu’un point de controˆle Cptr s’effectue, chaque agent ai 2 A communique ses propositions qui ont atteint le seuil de la majorite´.
Si jSr j = ; alors il n’y a aucune solution trouve´e. Si r , q alors la ne´gociation continue au tour suivant et le re´sultat sera e´value´ au prochain point de controˆle Cptr+1 . Si r = q alors la ne´gociation se termine en E´ CHEC. Si jSr j = 1 alors il existe une seule proposition majoritaire qui sera retenue comme la solution finale de la ne´gociation. La ne´gociation se termine alors en SUCCE` S. Si jSr j > 1 alors il y a plusieurs propositions acceptables comme solution. Le processus de de´cision social pre´sente´ dans section 4.3 est utilise´ pour se´lectionner la proposition qui sera retenue comme solution finale. 4.3
Le degre´ de satisfaction des agents. La satisfaction d’ un agent ai pour une proposition p est de´signe´e ici par une valeur de score qu’il attribue a` cette proposition. Cette valeur de score de´pend de l’e´cart entre ses aspirations, c’est-a`-dire, les valeurs d’utilite´ attendues et la valeur d’utilite´ de la proposition p. Le score exprime le degre´ de satisfaction d’un agent ai que nous e´valuons a` trois niveaux : –1 lorsque p est audela` de l’objectif fixe´, uai (p) Umaxai ; –2 lorsque p est dans la zone de concessions, uai (p) 2 [Uminai ; Umaxai ] ; –3 lorsque la proposition p sera refuse´e, c’est-a`q dire,uai (p) < Uminai ou uai (p) 2 [Uminai ; Umaxai ]. Nous de´signons alors trois valeurs de score note´es 2; 1; 0 repre´sentant, respectivement, les valeurs de score des trois niveaux mentionne´s ci-dessus. Ces valeurs sont telles que 2 > 1 > 0 = 0 et sont des informations publiques, communes a` tous les agents.
Notons que chaque agent ai de´finit sa propre fonction
d’utilite´ uai (information prive´e) et ses seuils
d’utilite´ Uminai ; Umaxai (informations prive´es). Les valeurs
d’utilite´ des agents ne sont pas comparables puisque
chaque agent de´finit sa propre fonction d’utilite´. Par
conse´quent, deux agents ayant la meˆme valeur
d’utilite´ pour une proposition peuvent avoir des degre´s de
satisfaction diffe´rents. Pour e´valuer le re´sultat de la
ne´gociation, nous de´finissons une nouvelle me´thode
d’e´valuation du bien-eˆtre social diffe´rente de celles
utilisant directement les valeurs d’utilite´ des agents.
Par exemple, les fonctions de bien-eˆtre sociale de
Nash ou utilitariste effectuent respectivement le
produit et la somme des utilite´s individuelles des agents.
La satisfaction sociale d’une proposition. Nous
de´signons par ws : P 7! R+ la fonction d’agre´gation
des valeurs de score que nous proposons. Elle
attribue une valeur re´elle positive a` chaque
proposition soumise de´signant sa valeur de satisfaction
sociale. La de´finition de ws s’inspire du principe de
Rawls (maximim) [
ai est la valeur de score de chaque agent ai . ws garantit le choix de la proposition respectant a` la fois la re`gle de la majorite´ et celle de l’e´quite´ selon Rawls. Ainsi, maximiser ws consiste a` minimiser le nombre d’agents ayant une satisfaction nulle, c’est-a`-dire, les agents ayant refuse´ la proposition.
Proposition 3 La proposition ayant la plus grande valeur de satisfaction sociale a aussi le taux d’acceptation le plus e´leve´ lorsque 1 et 2 prennent certaines valeurs (voir preuve).
Preuve Soit f ; g; f (k) = (kn+1k) 1 , g(k) = (k+1) 2 deux n k fonctions, k 2 [1; n 1] and Pk est l’ensemble des propositions avec un nombre k acceptations. 8p 2 Pk; 8 1 2]0; 2[; f (k) ws(p ) Pk; p 2 Pk+1; 9 1 2]0; 2[ = f (k) g(k): 8p 2 ws(p ) g(k) < (k+2) ws(p ) g(k +1). f (k +1) > g(k) , n k 1 1 > f (k +1) (k+1) . n k 2 Soit z(k) = (nk+1k) 2 nk+k21 alors 8 2 > 0; 1 2 ]M; 2[; f (k + 1) > g(k):
En re´sume´, la proposition 3 est vraie 8 2 > 0 et 1 2 ]M; 2[.
Nous avons montre´ que pour toute proposition p qui a k acceptations, f (k) ws(p ) g(k). S’il existe, a` l’instant t + 1, une proposition p qui a k + 1 acceptations alors quelles que soient les valeurs de satisfaction 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 classer toutes les propositions dont les taux d’acceptation sont supe´rieurs ou e´gaux a` maj . La proposition qui a la plus grande valeur de satisfaction sociale devient la solution. Nous avons montre´ que si cette proposition existe, elle a aussi le plus grand taux d’acceptation. Notons que pour obtenir ce re´sultat, les valeurs de 1 et 2 doivent respecter une certaine contrainte telle que : 1 2]M; 2[. Les re´sultats de ce travail nous ont permis aussi d’identifier certaines conditions dans lesquelles un syste`me de vote mixte combinant le vote par approbation et le vote par valeurs peut garantir un choix collectif respectant a` la fois la re`gle de la majorite´ et la somme des valeurs de score. Il peut arriver que plusieurs propositions obtiennent la meˆme valeur de satisfaction. Ainsi pour garantir l’unicite´ de la solution de ne´gociation, nous utilisons les valeurs de support des propositions dont les valeurs de satisfaction sont e´gales pour de´signer la proposition gagnante. S’il existe encore des ex aequo leurs estampilles sont utilise´es. Il existe toujours un e´cart de temps entre les dates d’obtention de la majorite´ pour deux propositions. 5
Nous avons imple´mente´ en Java le protocole propose´. Les simulations sont re´alise´es en faisant varier le nombre d’agents et le nombre d’anneaux. Le sce´nario de ne´gociation se base sur l’exemple du projet de tramway. Une liste de propositions et un ensemble de crite`res d’e´valuation sont pre´de´finis. Chaque agent se´lectionne ale´atoirement un sousensemble de propositions et un sous-ensemble de crite`res. Nous avons effectue´ plusieurs expe´riences, dans le cas ou` les agents forment un seul anneau et dans le cas ou` les agents forment plusieurs anneaux. Pour chaque expe´rience, nous avons mesure´ le taux de convergence. Ce taux de convergence est le rapport entre le nombre de fois qu’une solution est trouve´e et le nombre d’ite´rations de ne´gociation effectue´es. Nous avons fait varier le nombre d’agents n de 5 a` 50 et le nombre d’anneaux m de 1 a` 25. Pour un nombre n d’agents, on peut cre´er au plus bn=2c. Chaque anneau doit avoir au moins deux agents. m = 1, correspond au mode`le de ne´gociation dans lequel tous les agents ne´gocient dans un seul anneau. La figure 1 montre que le nombre d’anneaux Figure 1 – Convergence de la ne´gociation selon le nombre d’anneaux forme´s forme´s par les agents a un impact sur le re´sultat de la ne´gociation. Par exemple, lorsque le nombre d’agents est supe´rieur a` 20, nous observons que la formation de bn=2c anneaux conduit a` des taux de convergence plus faibles mais qui sont toujours meilleurs qu’un seul anneau forme´. La courbe colorie´e en violet repre´sente le taux de convergence de la ne´gociation lorsque bn=2c anneaux sont forme´s. Les taux sont plus faibles compare´s au cas ou` le nombre d’anneaux est plus petit que bn=2c. Les courbes de la figure 2 montrent l’e´volution du nombre d’acceptations des propositions pour n = 5 agents, n = 10 agents et n = 30 agents. Les courbes en pointille´s repre´sentent Figure 2 – Acceptation moyenne des propositions soumises en fonction du temps. les re´sultats obtenus lorsque tous les agents forment un seul groupe et celles en traits pleins repre´sentent les re´sultats lorsque les agents sont re´partis en plusieurs groupes. Ces courbes montrent que les propositions sont accepte´es plus facilement dans le protocole propose´. Cela prouve que notre protocole favorise la convergence de la ne´gociation. La figure 3 montre la comparaison entre notre mode`le de ne´gociation distribue´e et le mode`le centralise´ (un seul anneau est forme´) selon la qualite´ moyenne de la solution. La qualite´ de la solution pour chaque agent est l’e´cart entre l’utilite´ de la solution et son aspiration maximale. La qualite´ moyenne est le rapport entre la somme des qualite´s individuelles et le nombre total d’agents. Nous observons que les solutions obtenues lorsque le nombre d’agents augmente sont meilleures dans notre mode`le que dans le mode`le centralise´.
Cet article a pre´sente´ un mode`le de ne´gociation multilate´rale dans lequel les agents interagissent de fac¸on incre´mentale et ite´rative. Les agents sont re´partis en plusieurs groupes (anneaux) dans lesquels ils me`nent leurs ne´gociations. L’objectif de ce travail est de faciliter la recherche d’accords. Nous avons e´value´ les performances de notre me´canisme de ne´gociation en utilisant un sce´nario de ne´gociation. Les re´sultats empiriques montrent que ce mode`le de ne´gociation fonde´ sur une approche distributive permet aux agents de ne´gocier plus facilement compare´ aux mode`les dans lesquels tous les agents sont dans un seul groupe. Dans nos futurs travaux, nous testerons ce me´canisme avec d’autres exemples de ne´gociation pour montrer d’autres proprie´te´s.