Problèmes d’allocation de ressources et bien-être de Nash Résolution par négociation entre agents Antoine Nongaillard – Philippe Mathieu – Patricia Everaere Laboratoire d’Informatique Fondamentale de Lille Bât. M3, 59655 Villeneuve d’Ascq, France prénom.nom@lifl.fr RÉSUMÉ. Allouer m ressources entre n agents, de façon à optimiser leur bien-être, est un problème qui peut souvent être résolu de manière centralisée. Cependant, pour certaines fonctions de bien-être social, une résolution centralisée n’est pas envisageable. Par exemple, le bien-être de Nash est une fonction qui a d’indéniables qualités mais qui ne peut être optimisée de manière classique. De plus, de nombreuses applications reposent sur des hypothèses qui ne peuvent pas être prises en compte par ces techniques centralisées alors que d’autres méthodes le permettent, comme les approches multi-agents. Après une présentation du problème multi-agents d’allocation de ressources, nous mettons en évidence les difficultés liées aux techniques centralisées et distribuées existantes. Nous proposons une méthode s’appuyant sur la notion de transaction sociale que nous revendiquons être la seule méthode « anytime » capable de résoudre efficacement le problème d’allocation de Nash. ABSTRACT. Solving the allocation of m resources between n agents is a problem which has been mainly studied in a centralized way. However, some welfare functions cannot be addressed by such approaches. The Nash welfare, which has interesting qualities cannot be solved in such a way. Moreover, many real problems rely on aspects that cannot be handled by centralized techniques whereas multiagent methods are efficient. After having presented the multiagent allocation problem, we show the difficulties of centralized and distributed approaches. We propose a solving method based on social transactions and we claim that our anytime solving method is the only one able to effectively address this problem of obvious practical interests. MOTS-CLÉS : allocation de ressources, négociation, simulation, bien-être de Nash. KEYWORDS: multiagent resource allocation, negotiation, simulation, Nash welfare. RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux, pages 681 à 709 682 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux 1. Introduction Les problèmes d’allocation de ressources se retrouvent souvent dans la vie courante au travers de très nombreuses applications, et suscitent donc un intérêt croissant. Leur but est de déterminer la meilleure manière de distribuer un ensemble de ressources aux membres d’une population afin d’optimiser un objectif donné. Cette apparente simplicité cache en réalité un problème très riche et complexe, dont la résolution se heurte à des problèmes de complexité caculatoire exponentielle. De nombreuses études ont été réalisées aussi bien de manière centralisée (Sandholm, 2002; Cramton et al., 2006; Peters et al., 2010) que distribuée (Sandholm, 1998; Chevaleyre et al., 2006a; Endriss et al., 2006; Chevaleyre et al., 2010; Nongaillard et al., 2010) sous des hypothèses et des objectifs très variés. Dans cet article, nous nous intéressons en particulier au bien-être de Nash (Kaneko et al., 1979; Moulin, 1988; Arrow et al., 2002). Cette fonction de bien-être permet de prendre en compte à la fois la satisfaction moyenne de la société, mais aussi les inégalités au sein d’une population. Dans (Moulin, 2003), l’auteur montre que cette notion possède des propriétés intéressantes sur la distribution des ressources comme l’indépendance des agents non impliqués, le principe des transferts de Pigou-Dalton ou encore l’indépendance vis-à-vis des échelles de valeurs. En dépit de ses qualités, cette notion a été rarement étudiée jusqu’à maintenant. Nous montrons dans cet article que les méthodes constructives mènent à l’énumération explicite de toutes les allocations possibles, et qu’elles ne sont donc pas utilisables pour résoudre un problème d’allocation de Nash en un temps raisonnable. En effet, un problème d’allocation de m ressources à n agents mène à nm allocations différentes. Leur énumération explicite n’est donc pas envisageable. Il est nécessaire de concevoir des méthodes alternatives afin de trouver un global-optimum pour les problèmes d’allocation de Nash. Après une description du contexte d’étude en section 2, la section 3 énumère les idées préconçues et les difficultés liées à la résolution des problèmes d’allocation de ressources, aussi bien de manière centralisée que distribuée. Enfin, la section 4 décrit la méthode de résolution que nous proposons pour résoudre efficacement les problèmes d’allocation de Nash de manière distribuée. 2. Définitions et notations Un problème d’allocation de ressources est souvent défini à partir d’une population P de n agents et d’un ensemble R de m ressources. Chaque agent i ∈ P possède un panier Ri contenant les mi ressources qu’il possède. L’objectif est de trouver comment distribuer les ressources de R entre les agents de P afin d’optimiser un objectif donné. De nombreuses notions de bien-être existent dans la littérature, mais dans cet article, nous cherchons à maximiser la valeur du bien-être de Nash. Les problèmes d’allocation sont caractérisés par de nombreux paramètres qui influent sur leurs propriétés intrinsèques. La moindre différence dans les caractéristiques MARA et bien-être de Nash 683 de deux problèmes peut mener à des techniques de résolution efficaces fondamentalement différentes, comme par exemple considérer des ressources divisibles ou non. Les sections suivantes sont donc dédiées à la description de notre contexte de travail. 2.1. Allocations de ressources La nature des ressources est une caractéristique essentielle qui modifie profondément les propriétés du problème. Dans cet article, nous ne nous intéressons qu’à des ressources à la fois uniques et atomiques. Cela signifie qu’un agent ne peut ni diviser ni consommer les ressources de son panier. Dans ce contexte, les allocations de ressources peuvent être définies et caractérisées de la manière suivante : Définition 2.1 (Allocation de ressources). Soient une population de n agents P = {1, . . . , n} et un ensemble de m ressources R = {r1 , . . . , rm }. Une allocation de ressources est une liste ordonnée de n paniers de ressources Ri ⊆ R décrivant les ressources possédées par chaque agent i ∈ P : A = [R1 , . . . , Rn ], 1, . . . , n ∈ P, A ∈ A, oA est l’ensemble des allocations possibles. D’après la nature des ressources que l’on choisit de considérer ici, une allocation vérifie également les propriétés suivantes : \ [ Ri = ∅. Ri = R et i∈P i∈P Cette contrainte, peu restrictive, implique néanmoins que les ressources doivent être discrétisées. La gestion d’une ressource en quantité continue (comme de l’électricité par exemple) n’est ici pas prise en compte. 2.2. Les préférences des agents Un autre paramètre important est la représentation des préférences de chaque agent. Un agent évalue sa satisfaction, aussi appelée son bien-être individuel (Sandholm, 1998), grâce à une fonction d’évaluation souvent basée sur divers éléments comme, par exemple, une fonction d’utilité ou un porte-monnaie. Cependant, au lieu de considérer des porte-monnaie infinis comme dans beaucoup d’études de la littérature (par exemple (Chevaleyre et al., 2005)), nous avons choisi de restreindre la fonction d’évaluation à une fonction d’utilité. Ainsi, puisque l’argent n’est pas considéré, la satisfaction d’un agent dépend uniquement des ressources qu’il possède. Cette hypothèse peut sembler restrictive mais l’utilisation de paiements compensatoires infinis ne peut pas être considérée comme plausible. En effet, si un agent est aussi riche que nécessaire, n’importe quelle condition peut être satisfaite : toute perte d’utilité peut être compensée par de l’argent. Un tel contexte n’est pas réaliste selon nous. 684 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Les préférences des agents peuvent être modélisées selon différentes représentations (Coste-Marquis et al., 2004; Doyle, 2004; Chevaleyre et al., 2006b; Bonzon et al., 2009). Dans cet article, les agents expriment leurs préférences par une fonction d’utilité additive ce qui implique que l’utilité correspondante à la possession de plusieurs ressources est calculée par la somme de l’utilité de chacune. Définition 2.2 (Utility function). Un agent évalue son bien-être individuel grâce à une fonction d’utilité additive ui : 2R → R. Si un agent i ∈ P possède un panier de ressources Ri ⊆ R, son bien-être individuel peut être calculé par : X ui (r), i ∈ P, Ri ⊆ R. ui (Ri ) = r∈Ri Exemple 2.1. Soient une population de 3 agents P = {ag1, ag2, ag3} et un ensemble de 6 ressources R = {r1 , . . . , r6 }. Le tableau 1 décrit les préférences des agents : il contient les valeurs d’utilité associées à chaque ressource par chaque agent. ui (rj ) Population P ag1 ag2 ag3 Ensemble de ressources R r 1 r 2 r3 r 4 r 5 r 6 10 7 10 9 2 1 6 10 3 4 8 6 1 2 1 2 1 3 Tableau 1. Exemple de préférences d’agents Supposons que les ressources soient allouées de la manière suivante : A = [{r4 }{r1 , r2 , r6 }{r3 , r5 }]. L’agent ag1 ne possède que la ressource r4 . L’agent ag2 possède les ressources r1 , r2 et r6 et l’agent ag3 possède alors les ressources r3 et r5 . D’après le tableau 1, le bien-être individuel de chaque agent peut être calculé de la manière suivante : uag1 ({r4 }) = 9 uag2 ({r1 , r2 , r6 }) = 6 + 10 + 6 = 22 uag3 ({r3 , r5 }) = 1 + 1 = 2 2.3. Intérêt du bien-être de Nash La qualité d’une allocation de ressources est souvent évaluée globalement grâce à des notions de la théorie du choix social (Kaneko et al., 1979; Moulin, 1988; Arrow et al., 2002). Ces notions permettent l’évaluation du bien-être d’une population à partir du bien-être individuel des agents de cette population. Différentes notions existent dans la littérature. Le bien-être utilitaire est la notion sociale la plus utilisée. Elle mesure le bien-être moyen d’une population (par la somme des bien-être individuels). Le bien-être égalitaire mesure les inégalités au sein d’une population (en ne considérant que son agent ayant la plus faible satisfaction individuelle). Le bien-être de Nash MARA et bien-être de Nash 685 ou produit de Nash considère ces deux aspects à la fois. Il peut être vu comme un compromis entre les bien-être utilitaire et égalitaire. C’est celui sur lequel nous nous focalisons dans cet article. Définition 2.3 (Le bien-être de Nash). Le bien-être de Nash associé à une allocation de ressources A ∈ A se calcule par le produit des bien-être individuels de tous les agents de la population : Y ui (Ri ), A ∈ A. swn (A) = i∈P Alors que les notions de bien-être utilitaire et égalitaire souffrent d’inconvénients liés à la répartition des ressources, le bien-être de Nash possède des propriétés remarquables. En effet, cette notion est indépendante des échelles de valeurs : modifier les échelles de valeurs des utilités ne modifie pas les comparaisons d’allocations par paire. Aucun agent ne peut être négligé : tous les agents obtiennent au moins une ressource (si n ≤ m) pour éviter un bien-être individuel nul et donc un bien-être social nul. Cette notion a néanmoins ses limites : elle perd par exemple tout son sens dès que des valeurs d’utilité sont négatives. Exemple 2.2. Soient une population P = {ag1, ag2, ag3} et un ensemble ressources R = {r1 , . . . , r6 }. Les préférences des agents sont décrites dans le tableau 1. On peut alors déterminer une allocation de ressources optimale selon trois fonctions de bien-être social différentes, comme décrit dans le tableau 2. Fonction de bien-être social Utilitaire Égalitaire Nash Allocation optimale [{r1 , r3 , r4 }, {r2 , r5 , r6 }, {}] [{r1 }, {r5 }, {r2 , r3 , r4 , r6 }] [{r1 , r3 }, {r2 , r5 }, {r4 , r6 }] Tableau 2. Allocation optimale vs. fonction de bien-être Le tableau 2 fournit les allocations optimales pour différents bien-être à partir des préférences décrites dans le tableau 1. Il met en évidence l’une des propriétés intéressantes du bien-être de Nash : la répartition équitable. Avec les autres notions de bien-être, certains agents peuvent être complètement négligés et n’obtenir aucune ressource comme dans le cas utilitaire. Dans le cas égalitaire, tous les agents obtiennent au moins une ressource mais il arrive qu’un agent récupère la majorité des ressources afin de compenser ses faibles préférences. Dans le cas du bien-être de Nash, aucun agent n’est négligé et les ressources ne sont pas drainées pour autant. Cette notion permet à la fois de maximiser le bien-être individuel moyen et de minimiser les inégalités entre les agents. Le bien-être de Nash est donc une notion sociale évaluant différents aspects d’une allocation de ressources. Il a d’indéniables qualités et évite aussi certains inconvénients rencontrés par d’autres notions. Mais pourquoi cette notion si intéressante estelle rarement utilisée en pratique ? 686 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux 3. Un problème bien complexe En dépit de nombreuses idées reçues, déterminer une allocation de ressources maximisant le bien-être de Nash est un problème très complexe. Cette section présente les différents pièges liés aux techniques de résolution centralisées d’abord, puis aux méthodes distribuées basées sur des négociations entre agents. 3.1. Idées reçues dans les techniques centralisées Les problèmes d’allocation de ressources peuvent évidemment être résolus au moyen de techniques centralisées, mais leurs utilisations nécessitent des conditions particulières qui ne sont pas toujours satisfaites. Par exemple, une entité centrale omnisciente doit exister : elle doit connaître les paniers de ressources et les préférences des agents pour chercher une solution. Les enchères combinatoires (Bachrach et al., 2008; Cramton et al., 2006; Sandholm, 2002) remplissent ces conditions : le commissaire-priseur représente l’entité centrale qui connaît les ressources et les préférences des agents. En revanche, dans le cadre d’applications distribuées comme celles basées sur les réseaux pair-à-pair, ces hypothèses ne sont plus satisfaites. L’entité centrale omnisciente n’existe plus. En effet, un pair n’est même pas conscient de la taille de la population et rassembler les informations nécessaires n’est pas plausible ni même acceptable, en particulier dans le cadre de systèmes dynamiques. Les techniques centralisées, qui visent à identifier une allocation des ressources maximisant le bien-être de Nash, fournissent des solutions optimales que nous appelons optima globaux. Définition 3.1 (Global-Optimum). Une allocation de ressources A ∈ A est un globaloptimum si il n’existe pas d’autre allocation A′ ∈ A(A 6= A′ ) fournissant une plus grande valeur de bien-être social : ∄A′ ∈ A, swn (A′ ) > swn (A) A, A′ ∈ A, A 6= A′ . Les sections suivantes présentent quatre familles de techniques centralisées et leurs limites dans le cadre de la résolution de Nash. 3.1.1. . Algorithme exact Un algorithme exact déterminant une allocation socialement optimale existe toujours. En effet, puisqu’il n’existe qu’un nombre fini d’allocations distinctes, leur énumération explicite est toujours possible. Un tel algorithme peut être écrit de manière très concise en Prolog (Colmerauer et al., 1981) comme décrit dans l’algorithme 1. Cet algorithme permet de trouver l’allocation de ressources maximisant le bien-être de Nash au moyen d’une énumération explicite de toutes les allocations possibles. Le nombre d’allocations différentes augmente exponentiellement en fonction du nombre de ressources et d’agents. Un tel algorithme devient vite inutilisable, même sur des jeux de données de taille modeste. En effet, depuis la naissance du système solaire MARA et bien-être de Nash Algorithme 1. Algorithme d’énumération explicite % détermination d’une allocation alloc(_,[],[]). alloc(Ag,[R|Res],[[A,R]|L]) :- alloc(Ag,Res,L), member(A,Ag). % bien-être individuel pour une allocation donnée value(Ag,Alloc,T) :- util(Ag,U), valueBis(U,Ag,Alloc,T). valueBis(U,Ag,[],0). valueBis(U,Ag,[[Ag,Re]|Aff],T) :- !, valueBis(U,Ag,Aff,T1), member([Re,V],U), T is T1+V. valueBis(U,Ag,[[_,_]|Aff],T) :- valueBis(U,Ag,Aff,T). % Produit de Nash pour une allocation donnée nash([],Affect,1). nash([A|L],Affect,T) :- nash(L,Affect,T1), value(A,Affect,V), T is T1*V. % détermination de la meilleure allocation best(Alloc,R) :- ag(La), res(Lr), bagof(X,alloc(La,Lr,X),L), bestBis(La,L,Alloc,R). bestBis(La,[],[],0). bestBis(La,[X|L],X,V) :- bestBis(La,L,_,V2), nash(La,X,V), V>V2, !. bestBis(La,[_|L],X,V) :- bestBis(La,L,X,V). % exemple de données ag([a,b]). res([r1,r2,r3]). util(a,[[r1,10],[r2,5],[r3,8]]). util(b,[[r1,5],[r2,8],[r3,6]]). % commandes de lancement ag(La),res(Lr),alloc(La,Lr,Aff), nash(La,Aff,R). best(X,R). 687 688 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux (4.6 109 années), à l’aide d’un ordinateur déterminant un million d’allocations par seconde, nous n’aurions résolu qu’un problème de Nash de 10 agents et 23 ressources. Des techniques alternatives sont donc nécessaires pour trouver un global-optimum pour les problèmes d’allocation de Nash. 3.1.2. Limites de la programmation linéaire Les méthodes de résolution basées sur la programmation linéaire décrivent le problème sous la forme d’un modèle mathématique. Puisque les ressources que l’on considère ne sont pas divisibles, notre modèle se base sur des variables booléennes xir décrivant la possession d’une ressource par un agent : xir = 1 si la ressource r appartient à l’agent i, xir = 0 sinon. Le problème de maximisation du bien-être de Nash peut ainsi être formulé de la manière suivante :  Q P  max ui (r)xir    i∈P r∈R  swn⋆ = t.q : P xir = 1 r∈R   i∈P    xir ∈ {0, 1} r ∈ R, i ∈ P. On peut voir que la fonction objectif de ce système n’a pas de propriétés intéressantes. En effet, cette fonction n’est ni concave, ni convexe, ni linéaire. Résoudre des problèmes quadratiques (limité à deux agents) est déjà une tâche complexe et les techniques d’optimisation classiques ne sont pas efficaces au-delà. Afin de contourner ce problème, une idée répandue vise à transformer le produit en somme pour obtenir une expression plus facile à manipuler. L’idée la plus intuitive est d’utiliser une propriété de la fonction logarithme pour transformer la maximisation d’un produit en maximisant d’une somme de logarithme. log(a ∗ b) = log(a) + log(b). Malheureusement, cette transformation ne facilite pas la résolution du problème ! En effet, le logarithme n’est pas une fonction linéaire et il n’est pas plus aisé d’optimiser une somme de fonctions non-linéaires. Les outils d’optimisation les plus répandus comme C PLEX ou M ATLAB ne sont pas efficaces. Cette transformation change donc un problème complexe en un autre tout aussi complexe. 3.1.3. Programmation dynamique Puisque la programmation linéaire n’est pas efficace, certains se tournent vers les approches constructives. Le principe est d’utiliser une solution optimale d’un sousproblème comme base pour trouver une solution optimale au problème complet. Dans le cadre des problèmes d’allocation de ressources, trois types de sousproblèmes sont envisageables. Le premier considère toute la population mais seulement une partie des ressources. Le second considère toutes les ressources mais seulement une partie de la population. Le troisième type de sous-problème considère à la MARA et bien-être de Nash 689 fois une partie des agents et une partie des ressources. Ne considérer qu’une partie de la population est discutable. En effet, si toutes les ressources sont allouées de manière optimale sur une partie de la population, son extension entraînera forcément la redistribution des ressources déjà allouées. Autrement, tout nouvel agent n’aurait aucune ressource et nuirait ainsi au bien-être de la société (un bien-être individuel nul). Pour toutes ces raisons, seul le premier type de sous-problème sera considéré dans la suite de cette section. Un sous-problème d’allocation de ressources ne considère qu’un sous-ensemble de ressources R′ ⊂ R, qui est alloué de manière optimale entre les agents de la population P. Ensuite, un nouvel ensemble de ressources ρ ⊆ R \ R′ est ajouté au sous-problème et il faut alors adapter la solution optimale du sous-problème initial pour déterminer une solution optimale au problème élargi. Par exemple, une technique pourrait consister en l’utilisation de l’algorithme hongrois (Kuhn, 1955) pour allouer une ressource à chaque agent, avant d’allouer les ressources restantes aux agents leur attribuant la plus grande d’utilité. Malheureusement, l’efficacité d’une telle méthode dépendrait fortement des n premières ressources choisies pour être allouées aux agents. Proposition 3.1 (Pas de méthode constructive). Il n’est pas possible de déterminer un global-optimum du problème complet à partir d’une solution optimale d’un sousproblème. Démonstration. Prouvons cette proposition en construisant un contre-exemple générique. Considérons pour cela une population P de n agents, un ensemble R de m ressources et un sous-ensemble de ces ressources R′ = {r1 , . . . rk−1 } ⊂ R tel que n < k ≤ m. Les préférences des agents peuvent être définies en utilisant seulement trois coefficients x, y, z ∈ N tel que x < y < z de la manière suivante :  0 if n < j < k or k < j ≤ m    y if i = j or i = 1, j = n ui (rj ) = z if i = n, j = k    x sinon. Une solution optimale A au sous-problème ne considérant que k − 1 ressources peut être construite de la manière suivante : ( rj ∈ Rj if 1 ≤ j ≤ n A= =⇒ swn (A) = y n . rj ∈ R1 if n < j < k Chaque agent obtient une ressource qu’il associe à une utilité y. Les ressources rn+1 à rk−1 n’influent pas sur le résultat puisqu’elles sont associées à des utilités nulles. Toute ressource rj (1 ≤ j ≤ n) qui n’est pas associée à l’agent j n’apporte que x au bien-être individuel de son possesseur, ce qui mènera à une allocation dont la valeur de Nash sera plus faible. 690 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Étendons maintenant le sous-problème en considérant une ressource supplémentaire à allouer rk ∈ R \ R′ . S Il faut donc trouver comment allouer les ressources de R ˇ = R′ {rk } à partir de la solution optimale A au sous-problème précédent. Notons A′ , A ˇ ∈ A les deux seules allocations possibles : ( rk ∈ Rn =⇒ swn (A′ ) = y n−1 (y + z) rk ∈ Ri , i 6= n =⇒ swn (A ˇ) = y n−1 (x + y). L’allocation A ˇ est associée au plus grand bien-être de Nash (par la relation liant les coefficients x < y < z). Cependant, il existe toujours une meilleure allocation Aopt ∈ A tel que swn (Aopt ) = 2y n−1 z :   rj ∈ R1 , if j = 1 or n ≤ j < k opt A = rj ∈ Rj , if 1 < j < n   rj ∈ Rn if j = k. Les relations entre ces trois coefficients nous amènent à déduire que : swn (Aopt ) > swn (A ˇ) > swn (A′ ) > swn (A). Par conséquent, nous pouvons toujours trouver un contre-exemple montrant qu’il n’est pas possible de trouver une solution socialement optimale à partir d’une allocation optimale d’un sous-problème. Une autre solution serait d’utiliser un algorithme de branch-and-bound. Ces algorithmes peuvent être vus comme des arbres où les nœuds sont des solutions partielles alors que les feuilles sont des allocations complètes. Chaque branche correspond à l’allocation d’une ressource à un agent. À partir de la racine, le processus de résolution consiste à descendre dans l’arbre, en incluant les ressources petit à petit. Dans (Ramezani et al., 2009), les auteurs utilisent une borne supérieure pour couper certaines branches. Cette borne supérieure est égale à la valeur du bien-être de Nash lorsque toutes les ressources restantes sont allouées à tous les agents. Même si cette valeur est effectivement une borne supérieure, sa valeur est si grande qu’elle ne permet pas de couper des branches en pratique. L’algorithme de branch-and-bound entraîne alors l’énumération explicite de toutes les allocations. Exemple 3.1. Considérons 3 agents et 6 ressources. Supposons que tous les agents associent à toutes les ressources une utilité de 2. À la racine de l’arbre, aucune ressource n’a encore été allouée, elles appartiennent donc virtuellement à tous. [{r1 . . . r6 }{r1 . . . r6 }{r1 . . . r6 }] ⇒ swn = 12 × 12 × 12 = 1728 Descendons dans l’arbre des allocations possibles, en allouant une ressource à la fois. Si d’abord r1 est allouée à ag1 , seules les autres ressources r2 à r6 appartiennent virtuellement à tous. On obtient la borne supérieure : r1 ∈ ag1 −→ [{r1 . . . r6 }{r2 . . . r6 }{r2 . . . r6 }] ⇒ swn = 12 × 10 × 10 = 1200 MARA et bien-être de Nash 691 Si r2 et r3 sont respectivement allouée à ag3 et ag1 , nous obtenons les bornes supérieures suivantes : r2 ∈ ag3 −→ [{r1 , r3 . . . r6 }{r3 . . . r6 }{r2 . . . r6 }] ⇒ swn = 10 × 8 × 10 = 800 r3 ∈ ag1 −→ [{r1 , r3 . . . r6 }{r4 . . . r6 }{r2 , r4 . . . r6 }] ⇒ swn = 10 × 6 × 8 = 480 On peut voir que les valeurs des bornes supérieures entre deux niveaux de l’arbre sont si différentes qu’en pratique, elles ne permettent pas de couper des branches. Un tel algorithme mènera donc à l’énumération explicite de toutes les allocations. Notons que plus la valeur d’utilité moyenne est grande (valant ici 2), plus la différence entre les bornes supérieures de niveaux de l’arbre est importante. Puisqu’il n’y a pas de critère de branchement efficace dans ce contexte, ces algorithmes ne représentent pas une approche convaincante pour résoudre des problèmes d’allocation de Nash. La proposition 3.1 a ainsi des conséquences importantes sur la conception d’algorithmes de résolution. Notons que cette proposition est aussi valide dans le contexte de société égalitaire mais pas dans le cadre de société utilitaire. 3.1.4. Efficacité des heuristiques Puisque ni les algorithmes exacts, ni les techniques d’optimisation classiques ne semblent efficaces, des heuristiques doivent être conçues pour estimer le bien-être de Nash optimal. Nous avons utilisé différentes techniques et conçu plusieurs heuristiques que nous avons comparé au sein d’un tournoi pour déterminer celle donnant les meilleurs résultats. Puisque le produit de Nash est un compromis entre l’augmentation du bien-être individuel moyen et la diminution des inégalités, les heuristiques que nous avons conçu accordent plus ou moins d’importance à ces deux aspects. Nous avons conçu 6 heuristiques différentes. La première heuristique se focalise uniquement sur la satisfaction moyenne des agents et alloue chaque ressource à l’agent lui associant la plus grande utilité. La seconde ne considère que les inégalités entre les agents. Ils sont considérés séquentiellement par un mécanisme de round-robin où la meilleure ressource restante leur est allouée. La troisième heuristique prend en compte ces deux aspects par des étapes successives. D’abord, chaque ressource est allouée à l’agent lui associant la plus grande utilité. Ensuite, on vérifie que chaque agent possède au moins une ressource, et si besoin est, on prend la ressource maximisant le produit local des bien-être individuels. Les deux heuristiques suivantes sont basées sur l’algorithme hongrois (Kuhn, 1955) qui peut résoudre un problème d’allocation de x ressources entre x agents de manière optimale. La quatrième heuristique vise à maximiser la satisfaction moyenne alors que la cinquième vise à maximiser la richesse de l’agent le plus pauvre. La sixième et dernière heuristique est basée sur du branch-andbound. Elle est basée sur l’allocation des ressources libres à tous les agents comme décrit dans la section 3.1.3. L’efficacité de ces heuristiques a été comparée dans un tournoi. Chaque duel a été répétée 10 000 fois sur différentes instances. Ce tournoi met en évidence le fait qu’une 692 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux heuristique efficace doit prendre en compte aussi bien la richesse moyenne que les inégalités entre les agents. L’heuristique la plus efficace est la troisième heurisitque décrite dans cette section. Cette heuristique est décrite dans l’algorithme 2. Algorithme 2. Heuristique d’estimation du bien-être de Nash optimal Entrées : Population P, Ressources R Sorties : Estimation de swn⋆ // Première étape centrée sur le bien-être individuel moyen pour tous les r ∈ R faire i ← arg max ui (r) ; // détermine l’agent qui estime le plus r i∈P Ajouter r à A(i) ; // alloue r à l’agent i // Seconde étape centrée sur les inégalités pour i ∈ P s.t. mi = 0 faire val ← 0 ; // cherche où prendre une ressource pour j ∈ P s.t. mj > 1 faire
r′ ← arg max ui (r′ ) × uj (Rj \ {r′ }) ; r ′ ∈Rj si val < ui (r′ )uj (Rj \ {r′ }) alors val ← ui (r′ )uj (Rj \ {r′ }) ; r ← r′ ; Ajouter r à A(i) ; retourner swu (A) ; // ré-alloue r à l’agent i 3.2. Idées reçues dans les méthodes distribuées Puisque les techniques centralisées habituelles ne permettent pas la résolution des problèmes d’allocation de Nash, nous nous penchons dans cette section sur les méthodes distribuées. À notre connaissance, seules des approches basées sur des agents ont été étudiées, et c’est également à ces approches que nous avons choisi de nous intéresser. 3.2.1. Caractéristiques des méthodes « agents » Selon ces méthodes distribuées, des agents autonomes négocient les ressources de leur panier au moyen de transactions qui modifient l’allocation de ressources. En effet, tout au long du processus de négociation, l’allocation de ressources initiale évolue transaction après transaction jusqu’à une allocation optimale. Les méthodes « agents » partent d’une allocation initiale, qui évolue au travers de transactions successives entre agents, alors que les techniques centralisées distribuent directement les ressources. Pour atteindre un optimum grâce à ce type de méthodes distribuées, il faut donc qu’il existe une suite de transactions entre agents qui permette MARA et bien-être de Nash 693 de faire évoluer l’allocation de ressources jusqu’à cet optimum. Selon les transactions autorisées dans la méthode distribuée, un chemin menant de l’allocation initiale à un global-optimum peut ne pas exister. Exemple 3.2. Soient une population de deux agents P = {ag1, ag2} et un ensemble de trois ressources R = {r1 , r2 , r3 }. Les préférences des agents sont décrites dans le tableau 3. ui (rj ) Population P ag1 ag2 Ensemble de ressources R r1 r2 r3 5 5 1 1 1 5 Tableau 3. Caractéristique des méthodes distribuées – Préférences des agents   L’allocation de ressources initiale est A = {r1 }{r2 , r3 } . Autrement dit, l’agent ag1 possède r1 alors que l’agent ag2 possède r2 et r3 . La valeur initiale du bien-être de Nash est swn (A) = 30. Il est relativement facile de déterminer une allocation optimale A′ = {r1 , r2 }{r3 } et la valeur sociale associée : swn (A′ ) = 50. Or, il n’existe pas de chemin d’échange (une ressource contre une autre) permettant d’atteindre la solution optimale alors qu’un chemin de dons (une ressource sans contrepartie) existe. En effet, l’utilisation exclusive d’échanges ne permet pas de modifier le nombre initial de ressources par agent. Ainsi, selon le type de transaction autorisé, le global-optimum peut ne pas être atteignable. Méthodes centralisées et distribuées n’amènent pas aux mêmes types d’optimum. Les méthodes centralisées utilisent une notion d’optimum absolu alors que les méthodes distribuées utilisent une notion d’optimum réaliste basée sur les transactions. Définition 3.2 (∆-optimum). Une allocation de ressources A ∈ A est un ∆-optimum si aucun chemin de transactions, appartenant à l’ensemble des transactions autorisées ∆, ne mène à une allocation associée à un plus grand bien-être de Nash. ∀A′ ∈ A, ∄δ swn (A′ ) > swn (A) δ ∈ ∆, A ∈ A. Un ∆-optimum est la meilleure allocation atteignable selon les transactions autorisées. Cet optimum ne peut donc jamais être associé à un plus grand bien-être de Nash qu’un global-optimum, alors que l’inverse est généralement vrai. Dans l’exemple 3.2, l’allocation A est un ∆-optimum lorsque seules les transactions « échange » (une ressource échangée contre une autre) sont autorisées, mais cette allocation n’est pas un global-optimum. Un ∆-optimum ne peut être déterminé par des techniques centralisées pour des raisons de calculabilité. En effet, à chaque étape du chemin, le nombre de transactions possibles peut être extrêmement grand selon ∆. Par exemple, si seuls les dons sont autorisés, alors n × m transactions sont possibles à chaque étape du chemin menant au global-optimum. 694 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Notons que les méthodes « agents » doivent satisfaire certaines caractéristiques afin d’être utilisables en pratique. En effet, ces méthodes fournissent des chemins de transactions menant jusqu’à une allocation ∆-optimale. Chaque transaction est déterminée par une négociation entre agents et le processus de négociation (c’est-à-dire les négociations successives) doit cesser lorsque la population atteint une allocation ∆-optimale. Or, comme les agents sont autonomes, ils doivent à un moment donné arrêter de négocier, afin de laisser le système dans une allocation de ressources optimale. L’allocation atteinte à la fin du processus de négociation peut être vue comme un phénomène émergent. Les agents doivent ainsi être capables de déterminer localement si une transaction est profitable ou non. Leurs décisions doivent reposer sur un critère d’acceptabilité garantissant la convergence du processus de négociation (choisi de manière appropriée) et surtout l’arrêt de toute modification une fois le ∆-optimum obtenu. 3.2.2. Transactions : complexité et restrictions Différentes classes de transaction existent dans la littérature (Sandholm, 1998), les restreignant plus ou moins. La transaction la plus générique est appelée transaction multilatérale et peut impliquer autant d’agents et de ressources que nécessaire : Définition 3.3 (Transaction). Une transaction est un couple d’allocation δ = (A, A′ ) telle que A, A′ ∈ A et A 6= A′ . Ce couple décrit l’évolution de l’allocation initiale A en une autre A′ . Notons Pδ l’ensemble des nδ agents qui prennent part à la transaction δ. Cette définition est largement utilisée dans la littérature et plus particulièrement dans le cadre d’études théoriques (par exemple (Endriss et al., 2006; Chevaleyre et al., 2010)). Cependant, cette définition est basée sur la notion d’allocation qui est une notion globale. Seules quelques études ont été menées sur les transactions multilatérales. Certains auteurs les ont étudiées d’un point de vue théorique (Endriss et al., 2005) et ont établi des bornes sur la longueur des chemins de transactions selon différents scénarios. Dans (Hemaissia et al., 2007), les auteurs proposent un protocole de négociation pour simuler des transactions multilatérales. En pratique, ces transactions ne sont pas utilisées pour des raisons de calculabilité. En effet, déterminer une transaction multilatérale acceptable est une tâche complexe, due à la taille exponentielle de l’espace des possibilités. Proposition 3.2 (Complexité des transactions multilatérales). Soit δ une transaction multilatérale impliquant nδ agents dans laquelle m′ ressources sont offertes. Le P ′ nombre total de transactions multilatérales est : #δ = (nδ )m avec m′ = mi . i∈Pδ Démonstration. Une transaction multilatérale δ, impliquant nδ participants qui peuvent offrir jusqu’à leur panier complet, peut être vue comme un sous-problème d’allocation de ressources (P ′ , R′ ). La population est restreinte à l’ensemble des par- MARA et bien-être de Nash 695 ticipants P ′ = Pδ et l’ensemble S des ressources à allouer correspond à l’union des paniers des participants R′ = i∈Pδ Ri . Le nombre de transactions multilatérales correspond donc au nombre total d’allocations possibles du sous-problème. Puisqu’il n’existe pas de technique fiable pour identifier efficacement les transactions multilatérales, nous choisissons de ne considérer que les transactions bilatérales dans cet article, comme c’est le cas dans la majorité des études réalisées. Cependant, même si cette restriction diminue la complexité liée à l’identification des transactions acceptables, elle empêche également d’atteindre une allocation optimale. Proposition 3.3 (Limite sur le nombre de participants). Limiter le nombre d’agents pouvant être impliqués dans une même transaction peut empêcher le processus de négociation d’atteindre une allocation optimale. Corollaire 3.4. Une transaction impliquant tous les agents d’une population peut être nécessaire pour qu’un processus de négociation atteigne une allocation socialement optimale. Démonstration. Prouvons cette propriété en concevant un contre-exemple. Soient une population P = {ag1, ag2, ag3} et un ensemble de ressources R = {r1 , r2 , r3 }. Nous supposons que les agents n’acceptent que des transactions augmentant leur bienêtre individuel. Leurs préférences sont décrites dans le tableau 4. ui (rj ) Population P ag1 ag2 ag3 Ensemble de ressources R r1 r2 r3 2 1 5 5 2 1 1 5 2 Tableau 4. Limite sur le nombre de participants – Préférences des agents   Supposons l’allocation initiale A = {r1 }{r2 }{r3 } avec swn (A) = 8. Aucune transaction n’impliquant qu’un sous-ensemble de la population ne mène à une meilleure allocation de ressources. En effet, les dons (une ressource donnée sans contrepartie) laissent toujours un des agents sans ressources (et donc à un bien-être individuel nul), et tous les échanges (une ressource contre une autre) mènent toujours à la diminution du bien-être individuel d’au moins un des participants. Or cette allo cation initiale n’est pas un global-optimum puisqu’il existe A′ = {r3 }{r1 }{r2 } qui est associée à un plus grand bien-être de Nash swn (A′ ) = 125. La seule et unique manière d’atteindre l’optimum correspond à trois dons simultanés. En effet, si les trois agents donnent simultanément leur ressource à un des partenaires, ils augmentent tous les trois leur bien-être individuel. Par conséquent, limiter le nombre d’agents impliqués dans une même transaction peut empêcher le processus de négociation d’atteindre un global-optimum. 696 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Restreindre le nombre de participants à une transaction reste un moyen efficace pour diminuer la complexité. Malheureusement, cela ne suffit pas. La détermination d’une transaction bilatérale acceptable reste une tâche délicate dont la complexité dépend du nombre de ressources que les participants peuvent offrir. Corollaire 3.5 (Complexité des transactions bilatérales). Considérons deux agents i, j ∈ P qui possèdent respectivement mi et mj ressources. Le nombre total de transactions bilatérales possible entre les agents i est j est : #δij = 2mi × 2mj − 1. Démonstration. Cette formule est obtenue par une application directe de la proposition 3.2 avec nδ = 2, Pδ = {i, j}, et m = mi + mj . Limiter la taille des offres faites par les agents (le nombre de ressources que les participants peuvent offrir) est un moyen de simplifier l’identification de transactions bilatérales acceptables. On peut cependant se demander quel est l’effet d’une telle restriction sur l’efficacité des négociations. Proposition 3.6 (Limite sur les offres des participants). Restreindre la taille des offres des participants durant une transaction peut empêcher le processus de négociation d’atteindre un global-optimum. Corollaire 3.7 (Décomposition d’une transaction de Nash). Les transactions ne peuvent pas toujours être décomposées en une séquence de transactions acceptables de moindre cardinalité. Démonstration. Soient P = {ag1, ag2} une population de deux agents et R = {r1 , r2 } un ensemble de ressources. Les préférences des agents sont décrites dans le tableau 5. ui (rj ) Population P ag1 ag2 Ensemble de ressources R r1 r2 1 7 7 1 Tableau 5. Limite sur les offres des participants – Préférences des agents   L’allocation de ressources initiale est A = {r1 }{r2 } et vaut swn (A) = 1. Il existe un échange acceptable pour les deux agents (leurs bien-être individuels res  pectifs augmentent). Cet échange mène à une allocation A′ = {r2 }{r1 } qui vaut swn (A′ ) = 49. Cette transaction acceptable ne peut en revanche pas être décomposée en une séquence de transactions acceptables de moindre cardinalité (impliquant chacune moins de ressources). En effet, la seule décomposition possible est une séquence de deux MARA et bien-être de Nash 697 dons. Or, aucun don n’est acceptable puisqu’il laisserait un agent sans aucune ressource. Par conséquent, une transaction acceptable ne peut pas toujours être décomposée en une séquence de transactions acceptables de moindre cardinalité. La première conséquence de cette proposition est évidente. Les transactions de grande cardinalité ne peuvent être décomposées en une séquence de transactions de moindre cardinalité, et donc en une séquence de dons. Elles sont essentielles pour garantir l’atteinte d’une allocation optimale. Les types de transaction autorisés durant les négociations, noté ∆, définissent la politique de négociation. Les agents peuvent par exemple être autorisés à offrir une ou plusieurs ressources lors d’une même transaction. La politique de négociation basée uniquement sur des « dons » (une ressource sans contrepartie) sera notée « h1, 0i » alors que celle basée uniquement sur des « échanges » (une ressource contre une autre) sera notée « h1, 1i ». Un seul type de transaction est autorisé selon ces politiques de négociation. Une politique de négociation selon laquelle les agents peuvent respectivement offrir jusqu’à n et m ressources sera notée « up to hn, mi ». « up to {hn, mi} » ⇔ ∆ = {hx, yi|x ≤ n, y ≤ m}. Proposition 3.8 (Complexité des politiques de négociation). Si les deux agents i, j ∈ P peuvent offrir respectivement jusqu’à u et v ressources (u ≤ mi , v ≤ mj ), le nombre de transactions bilatérales possible entre eux deux est : ! ! v u X X j x x Cmj . C mi #δi = x=0 x=0 Démonstration. Une politique de négociation est basée sur la taille des offres qu’un agent peut faire. Si un agent peut offrir « jusqu’à trois ressources », il peut offrir n’imk porte quel sous-ensemble de son panier contenant au plus trois ressources. Cm est le i nombre d’offres possibles contenant exactement k ressources que peut faire un agent possédant mi ressources. Une simple somme permet de déterminer le nombre total d’offres qu’un agent peut faire. Une fois ce nombre calculé pour chacun des deux agents, déterminer le nombre de transactions possibles est alors trivial. Exemple 3.3. Considérons deux agents i, j ∈ P impliqués dans une négociation initiée par l’agent i. Ces agents possèdent respectivement 10 et 20 ressources dans leur panier. Déterminons alors le nombre de transactions possibles selon différentes stratégies de négociation. ∆ = {h1, 0i} ⇒ #δij = 10 ∆ = {h1, 1i} ⇒ #δij = 200 ∆ = {hx, yi|x ≤ 2, y ≤ 2} ⇒ #δij = 40500 698 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Lorsque seuls les dons de l’initiateur sont autorisés, 10 dons sont possibles puisque l’initiateur ne possède que 10 ressources. Lorsque seuls les échanges sont autorisés, les deux participants peuvent offrir une unique ressource ce qui rend 200 transactions différentes possibles. Lorsque les participants peuvent offrir jusqu’à deux ressources, le nombre de transactions possibles explose jusqu’à 40 500. Cet exemple met en évidence que, selon le type de transaction autorisé, une négociation peut très vite prendre un temps considérable. Restreindre la cardinalité des transactions est ainsi essentiel pour garantir l’exécution en temps raisonnable de la méthode. 3.2.3. Rationalité individuelle et efficacité Dans les méthodes distribuées, les agents sont souvent autonomes. L’allocation initiale évolue petit à petit grâce à des transactions locales entre les agents. Au lieu d’avoir une entité centrale qui décide comment allouer les ressources, la décision est distribuée entre les agents. Chaque agent doit alors déterminer localement quelles transactions sont profitables. La prise de décision des agents est basée sur un critère d’acceptabilité. Dans la littérature ((Sandholm, 1998) par exemple), le critère le plus utilisé est la rationalité individuelle : ce critère ne considère que le bien-être individuel de l’agent. Définition 3.4 (Agent rationnel). Un agent est dit « rationnel » si et seulement si il n’accepte que les transactions augmentant son bien-être individuel. Un agent rationnel i ∈ P acceptera donc toute transaction δ(A, A′ ) satisfaisant la condition suivante : ui (Ri′ ) > ui (Ri ), i ∈ P, Ri , Ri′ ⊆ R, où Ri et Ri′ sont respectivement les paniers de ressources de l’agent i dans les allocations A et A′ . Ce critère d’acceptabilité n’est basé que sur des informations personnelles et peut donc être calculé de manière locale. Cependant, un critère d’acceptabilité basé uniquement sur le bien-être individuel de l’agent est inefficace pour atteindre une allocation socialement optimale. En effet, seules peu de transactions rationnelles peuvent être appliquées en général, et la population reste dans une situation sous optimale. Exemple 3.4. Soient une population P = {ag1, ag2} et un ensemble de ressources R = {r1 , r2 }. Le tableau 6 décrit les préférences des agents. ui (rj ) Population P ag1 ag2 Ensemble des ressources R r1 r2 1 4 10 5 Tableau 6. Rationalité individuelle – Préférences des agents   L’allocation de ressources initiale est A = {r1 }{r2 } et vaut swn (A) = 5. À partir de cette allocation, aucune transaction rationnelle n’est possible. En effet, au- MARA et bien-être de Nash 699 cun don n’est rationnel puisqu’un agent donnant une ressource diminuera son bienêtre individuel. Pareillement, le seul échange possible diminuerait le bien-être individuel de l’agent ag1 qui passerait de 5 à 4. Or, une meilleure allocation existe : A′ = {r2 }{r1 } valant swn (A′ ) = 40. Ce global-optimum ne peut pas être atteint par des agents individuellement rationnels. Ainsi, les processus de négociation entre agents individuellement rationnels peuvent se terminer prématurément sur des allocations sous-optimales. 3.2.4. Processus de négociation et graphe d’accointances La plupart des études réalisées jusqu’à présent sur les problèmes d’allocation de ressources ne considère pas de restrictions dans les communications entre les agents (par exemple (Chevaleyre et al., 2006a; Endriss et al., 2006)). Un agent peut donc négocier avec tous les autres agents de la population. Cette hypothèse ne nous semble pas très réaliste car ce n’est pas le cas dans bien des applications. Par exemple, dans le cas d’un réseau pair-à-pair, un pair ne connaît pas tous les autres pairs du réseau. Dans un réseau social sur Internet, une personne ne connaît qu’un nombre limité d’autres membres. Dans de tels cas, les agents ne sont même pas conscients de la taille du système complet et ne disposent que d’informations locales. Ces aspects ne sont souvent pas pris en compte lorsqu’on parle de problèmes d’allocation. Dans (Chevaleyre et al., 2007), les auteurs ont étudié l’élimination de l’envie au sein d’une population d’agents. Ils ont établi des résultats sur la convergence et la complexité des problèmes d’allocation sur graphes, sans donner les moyens d’atteindre les solutions optimales. Les problèmes d’allocation de tâches ont été étudiés sans que les capacités de communication des agents ne soient restreintes (de Weerdt et al., 2007). Seul le cas des sociétés utilitaires a été résolu au moyen d’algorithmes exponentiels. D’autres auteurs se sont focalisés sur des questions topologiques, où le comportement des agents et les performances des systèmes complexes ont été étudiés (Dekker, 2007). Puisque peu d’études ont considéré des restrictions sur les communications des agents, certains pourraient remettre en cause l’importance de telles restrictions. Proposition 3.9 (Impact du graphe d’accointances). Indépendamment de la fonction objectif considérée, un graphe d’accointances restreint peut empêcher un processus de négociation d’atteindre un global-optimum. Démonstration. Soient une population P = {ag1, ag2, ag3} et un ensemble de ressources R = {r1 , r2 , r3 }. Les préférences des agents sont décrites dans le tableau 7. Le graphe d’accointances décrivant les capacités de communication des agents est représenté dans la figure 1. Les nœuds représentent les agents et les liens entre les agents représentent les possibilités de communication. Selon la topologie de ce graphe, l’agent ag2 peut communiquer avec les agents ag1 et ag3, tandis que ces 700 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux ui (rj ) Population P ag1 ag2 ag3 Ensemble de ressources R r1 r2 r3 3 1 9 1 4 1 10 2 3 Tableau 7. Impact du graphe d’accointances – Préférences des agents derniers  ne peuvent pas  communiquer entre eux. L’allocation de ressources initiale est A = {r1 }{r2 }{r3 } et vaut swn (A) = 36. Figure 1. Exemple de graphe d’accointances Seulement deux échanges sont possibles. Soit les agents ag1 et ag2 échangent les ressources r1 et r2 , soit les agents ag2 et ag3 échangent les ressources r2 et r3 . Ces deux échanges provoquent une diminution du bien-être individuel d’au moins un des participants. Aucun échange n’est donc acceptable ici. Cette allocation A n’est cependant pas un global-optimum. En effet, l’échange des ressources r1 et r3 entre les agents ag1 et ag3 mènerait à une meilleure allocation   A′ = {r3 }{r2 }{r1 } valant swn (A′ ) = 360. La topologie du graphe d’accointances (décrit figure 1) a suffisamment restreint les communications entre les agents, pour empêcher le processus de négociation d’atteindre un global-optimum. Dès que le graphe d’accointances est restreint, l’ordre dans lequel les agents négocient devient important. Proposition 3.10 (Ordre des négociations). Indépendamment de la fonction objectif considérée, l’ordre selon lequel les agents négocient empêche un processus de négociation d’atteindre un global-optimum. Démonstration. Soient une population P = {ag1, ag2, ag3} et un ensemble de ressources R = {r1 , r2 , r3 }. Les préférences des agents sont décrites dans le tableau 8. Le réseau d’accointances décrivant les capacités de communication  des agents est représenté dans la figure 1. L’allocation de ressources initiale est A = {r1 }{r2 }{r3 } et vaut swn (A) = 6. Supposons maintenant que l’agent ag2 initie une négociation. D’après la topologie du graphe d’accointances, deux partenaires sont possibles. Selon le choix de l’initiateur, le processus de négociation peut terminer sur une allocation MARA et bien-être de Nash 701 sous-optimale. En effet, si l’agent ag2 négocie d’abord avec l’agent ag1, l’allocation atteinte est A′ = {r2 }{r1 }{r3 } et vautswn (A′ ) = 50. En revanche, si l’agent ag3 est choisi, l’allocation atteinte est A ˇ = {r1 }{r3 }{r2 } et vaut swn (A ˇ) = 126. ui (rj ) Population P ag1 ag2 ag3 Ensemble des ressources R r1 r2 r3 2 10 4 5 3 9 2 7 1 Tableau 8. Ordre des négociations – Préférences des agents Par conséquent, l’ordre selon lequel les agents négocient devient un paramètre important à prendre en compte lorsque le graphe d’accointances est restreint. Dans cette section, nous avons montré qu’il était important de prendre en compte la topologie du graphe d’accointances car cela intervient dans de très nombreuses applications. Ces restrictions de communication correspondent sans doute plus au monde réel mais ont des conséquences importantes sur l’efficacité des processus de négociation. Elles peuvent d’ailleurs empêcher les processus de négociation d’atteindre un global-optimum. De plus, nous avons également montré que l’ordre dans lequel les agents négocient peut mener à des solutions sous-optimales. En dépit de leurs impacts respectifs, ces paramètres ont été rarement pris en compte jusqu’à présent. 4. Notre approche distribuée La section précédente était dédiée aux idées préconçues sur les problèmes d’allocations de Nash, sur les techniques centralisées, sur la conception d’heuristiques et sur les négociations distribuées. Cette section décrit la solution distribuée que nous proposons, basée sur des agents autonomes qui négocient et font émerger une solution au problème d’allocation de Nash. Nous décrivons d’abord le paramétrage des négociations, et présentons ensuite une étude expérimentale pour étayer notre proposition. 4.1. Paramétrages des négociations Puisque les transactions bilatérales sont les plus calculables en pratique, nous avons choisi de ne considérer qu’elles. Elles peuvent être modélisées en utilisant le nombre de ressources que chaque agent peut offrir. Définition 4.1 (Transactions bilatérales). Une transaction bilatérale entre deux agents i, j ∈ P, notée δij , est initiée par l’agent i qui choisit un partenaire j. C’est une paire δij hu, vi = (ρi , ρj ) où l’initiateur i offre un ensemble ρi de u ressources (ρi ⊆ Ri ) alors que le partenaire j offre un ensemble ρj de v ressources (ρj ⊆ Rj ). 702 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux 4.1.1. Le critère de sociabilité Comme décrit dans la section 3.2.3, le critère de décision est essentiel afin de garantir la convergence des processus de négociation. Un agent utilise ce critère afin de déterminer quelles sont les transactions profitables. Le critère le plus utilisé, la rationalité individuelle, mène le plus souvent les processus de négociation à des solutions très sous-optimales. Nous proposons ici un nouveau critère plus flexible, qui devrait mener à des solutions socialement meilleures. Définition 4.2 (Transaction sociale). Une transaction sociale δ, changeant l’allocation initiale A en une nouvelle A′ , est une transaction menant à une amélioration du bienêtre de la société : swn (A′ ) > swn (A), A, A′ ∈ A. Le critère social est centré sur la notion de bien-être social, qui est une notion globale. Sa valeur ne peut être déterminée que grâce à la valeur du bien-être individuel de tous les agents. Les agents devraient connaître le panier de ressources et les préférences de tous les agents de la population, afin de calculer la valeur du bien-être social. Ces conditions ne peuvent être satisfaites puisque les agents ne disposent que d’informations locales. La valeur du bien-être social n’est pas essentielle : en effet, connaître son évolution est suffisant pour savoir si une transaction pénalise ou non la société. De tels calculs peuvent alors être réduits à un contexte local, au niveau d’un agent. En effet, si on ne considère que les deux agents impliqués dans une transaction, l’évolution de la valeur sociale peut être calculée de manière locale. swn (A) <swn (A′ ) Y Y uk (Rk′ ) uk (Rk ) < ⇒ k∈P ⇒ ui (Ri )uj (Rj ) Y k∈P uk (Rk ) <ui (Ri′ )uj (Rj′ ) k∈P\{i,j} ⇒ Y uk (Rk′ ) k∈P\{i,j} ui (Ri )uj (Rj ) <ui (Ri′ )uj (Rj′ ) C’est l’un des points forts de notre approche que de pouvoir ramener ce critère global à un calcul local. C’est la condition nécessaire garantissant que les agents n’ont pas à être omniscients. 4.1.2. Réseau d’accointances Notre méthode permet de prendre en compte les notions de voisinage et de réseau d’accointances. Le voisinage Ni d’un agent i ∈ P est un sous-ensemble de la population P avec laquelle il est capable de communiquer. Le graphe d’accointances est le réseau de relations formé par l’agrégation du voisinage de tous les agents. Ce réseau décrit les capacités de communication des agents. Dans un tel graphe, les nœuds représentent les agents et les liens entre les agents symbolisent les possibilités de communication. MARA et bien-être de Nash 703 Différentes topologies peuvent ainsi être considérées : les graphes structurés où tous les agents ont le même nombre de voisins (grilles ou graphes complets) et les graphes aléatoires (classique (Erdős et al., 1959) et petit-monde (Albert et al., 2002)) où la topologie est irrégulière. 4.1.3. Le comportement des agents Le comportement d’un agent le définit d’un point de vue externe, c’est-à-dire qu’il décrit la manière dont l’agent interagit avec les autres. Une transaction bilatérale est une combinaison d’offres venant de différents participants. Lorsqu’un agent initie une négociation, il sélectionne un partenaire dans son voisinage, fait des offres et en reçoit, puis vérifie leur acceptabilité selon son propre critère. Si une transaction est acceptable pour les deux participants, alors elle est appliquée. Sinon, les agents doivent décider qui doit modifier son offre d’après son comportement et la négociation continue. L’ordre dans lequel ces actions sont effectuées (si elles le sont) constitue un comportement. Plusieurs comportements ont été implémentés et testés mais seul le plus efficace est décrit dans cet article (c’est-à-dire celui menant aux meilleures solutions d’un point de vue social). Nos simulations montrent que les agents doivent être capables de modifier leurs offres et de changer de partenaire durant la négociation. Il faut en effet que les agents soient capables de faire des concessions et de proposer différentes offres à différents partenaires si c’est nécessaire. Un tel comportement nécessite plus de temps de calcul que lorsque les agents refusent de modifier leurs offres, mais il permet aux processus de négociation d’atteindre de meilleures solutions. L’ordre dans lequel les différentes actions sont effectuées affecte également l’efficacité des négociations. Trois niveaux de priorité doivent être distingués : sur les partenaires, sur les offres de l’initiateur et sur celles du partenaire. Nos expériences montrent que le comportement décrit par l’algorithme 3 est le plus efficace. Dans cet algorithme, TEST D ’ ACCEP TABILITÉ dénote le test que doit faire l’agent pour déterminer si une transaction est acceptable ou non selon son propre critère. Le test peut être formellement formulé selon la définition 3.4 si l’agent est individuellement rationnel ou selon la définition 4.2 si l’agent est sociable. Selon la politique de négociation (c’est-à-dire le type de transaction autorisé), chaque agent peut offrir jusqu’à un certain nombre de ressources. Il commence par constituer la liste des offres qu’il peut faire. Ensuite, il trie cette liste selon ses préférences afin de toujours proposer ce qui a le moins de valeur pour lui en premier lieu. Un agent agissant suivant le comportement décrit dans l’algorithme 3, peut changer de partenaire et d’offre durant la négociation. Il propose son offre à ses voisins avant de faire des concessions et d’en proposer une autre. 704 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Algorithme 3. Recherche d’une transaction bilatérale acceptable Entrées : Agent initiateur i // génère la liste des offres possibles selon sa politique Li ← génère (∆, Ri ) ; // ordonne la liste d’offres pour offrir d’abord ce qui a le moins de valeur Trie Li selon ui ; // mélange le voisinage pour éviter un biais de sélection Mélange Ni ; // Évolution de l’offre de l’initiateur en dernier recours pour tous les ρi ∈ Li faire // Changement du partenaire impliqué s’il ne peut répondre de manière acceptable à l’offre de l’initiateur pour tous les j ∈ Ni faire // Modification prioritaire de l’offre du partenaire pour tous les ρj ∈ Lj faire // Création d’une transaction δ ← (ρi , ρj ) ; si TEST D ’ ACCEPTABILITÉ alors Application de la transaction δ ; Fin de la négociation ; 4.2. Évaluation de notre méthode basée sur les agents 4.2.1. Le protocole d’évaluation Durant ces expérimentations, différents aspects des processus de négociation ont été évalués principalement grâce à deux paramètres. Le premier paramètre est la cardinalité des transactions. Identifier une transaction bilatérale acceptable peut devenir une tâche coûteuse et complexe selon le nombre de ressources que les agents peuvent offrir en une fois (comme décrit dans la section 3.2.2). Afin de favoriser l’implémentation de notre approche, une limite sur la taille des offres nous paraît essentielle. Le but est de déterminer si l’utilisation de transactions de large cardinalité est inévitable pour atteindre des solutions socialement intéressantes. Le second paramètre utilisé est l’efficacité sociale, qui mesure l’écart entre le global-optimum (fourni par la meilleure heuristique décrite dans la section 3.1.4) et la solution obtenue par négociation entre agents selon différents paramétrages. Le but est de déterminer quel est le meilleur moyen de négocier et d’atteindre une solution socialement optimale en un temps raisonnable. MARA et bien-être de Nash 705 Les simulations ont été menées sur des populations de 50 agents où 250 ressources étaient disponibles (n = 50, m = 250). Deux types de graphes structurés (des réseaux complets et des grilles) et deux types de graphes aléatoires (Erdős-Rényi et petitmondes) ont été utilisés. Un grand nombre de simulations a été effectué : nous avons généré 10 graphes de chaque classe, 10 ensembles de préférences d’agents par graphe, et 100 négociations pour chacun des couples graphe-préférences à partir d’allocations initiales différentes. Deux critères d’acceptabilité ont été évalués durant les simulations : la rationalité individuelle et la sociabilité. Les ressources sont distribuées de manière aléatoire. De même, les utilités des agents ont été générées de manière aléatoire dans l’intervalle de valeurs {1..m}. Durant un processus de négociation, l’agent initiateur est choisi de manière aléatoire et la distribution du tour de parole est uniforme : aucun agent ne peut parler deux fois si les autres agents n’ont pas parlé au moins une fois. Lorsque personne ne peut plus trouver de transaction acceptable, le processus de négociation s’arrête. 4.2.2. La cardinalité des transactions Le premier paramètre à évaluer est la cardinalité des transactions. Une transaction bilatérale δij hu, vi entre deux agents i, j ∈ P est caractérisée par la taille des offres faites u et v. Les figures 2 et 3 montrent l’évolution du bien-être de Nash durant le processus de négociation selon la cardinalité des transactions. Ces courbes sont des moyennes obtenues sur les 100 processus de négociation de même paramétrage, qui ont été menés à partir d’allocations initiales différentes. Bien-Être de Nash (Log(swn )) 375 350 325 300 < 1, 0 > < 1, 1 > jusque < 1, 1 > jusque < 2, 2 > jusque < 3, 3 > 0 250 500 750 Nombre de transactions effectuées 1000 Figure 2. Efficacité des négociations vs. transaction effectuée en fonction de la cardinalité La figure 3 montre que les processus de négociation basés sur des dons (ie transactions h1, 0i) nécessitent moins de temps et de transactions. Plus les transactions autorisées sont larges, plus les processus de négociation prennent de temps. Cependant, selon la figure 2 représentant le nombre de transactions effectuées, les transactions plus larges n’améliorent pas significativement la qualité des solutions. Les négociations reposant sur des échanges (ie transactions h1, 1i) se finissent après un faible nombre de 706 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux Bien-Être de Nash (Log(swn )) 375 350 325 300 < 1, 0 > < 1, 1 > jusque < 1, 1 > jusque < 2, 2 > jusque < 3, 3 > 10 100 1000 Temps de calcul (ms) 10000 Figure 3. Efficacité des négociations vs. temps de calcul en fonction de la cardinalité transactions mais atteignent également des solutions beaucoup moins intéressantes. Les autres processus de négociation se terminent après des séquences de transactions de longueur similaire. L’expérience montre que l’utilisation de larges transactions bilatérales n’améliore pas significativement les solutions, et donc ne justifie pas les importants surcoûts engendrés. 4.2.3. L’efficacité des négociations L’efficacité des négociations doit être évaluée. Nous proposons de le faire ici par comparaison avec les heuristiques centralisées présentées précédemment (section 3.1.4). Le tableau 9 montre l’efficacité des processus de négociation selon le type de graphe d’accointances, le critère d’acceptabilité et la cardinalité des transactions. Ce tableau montre que certaines valeurs de bien-être peuvent être supérieures à 100 %. Puisque les heuristiques ne donnent qu’une estimation du bien-être de Nash, une efficacité supérieure à 100 % signifie que le processus de négociation mène à des allocations plus intéressantes que celles fournies par les heuristiques. Réseaux d’accointances Complet Grille Erdős-Rényi Petit-monde Rationalité individuelle h1, 1i up to h2, 2i 99.9 100.1 97.0 97.5 99.6 99.8 97.2 98.0 h1, 0i 101.6 99.6 101.4 100.2 h1, 1i 100.1 98.2 99.9 98.9 Sociabilité up to h1, 1i 101.7 99.7 101.6 100.4 up to h2, 2i 101.7 99.7 101.6 100.4 Tableau 9. Efficacité des négociations de Nash (%) selon les réseaux d’accointances Les négociations rationnelles aboutissent à des allocations socialement plus faibles que les négociations sociales, ce qui indique une répartition plus inéquitable des ressources dans la population. La variation entre les valeurs sociales atteintes est égale- MARA et bien-être de Nash 707 ment plus importante, montrant le manque de flexibilité des négociations entre agents individuellement rationnels. Par ailleurs, que les négociations soient rationnelles ou sociales, les politiques de négociation basées sur ∆ = {hu, vi|u ≤ 1, v ≤ 1} et sur ∆ = {hu, vi|u ≤ 2, v ≤ 2} mènent aux mêmes résultats. En conséquence, autoriser les dons et les échanges est suffisant pour atteindre des allocations efficaces. En revanche, les négociations basées sur des échanges uniquement (sans autoriser les dons) mènent à des allocations socialement très faibles. En effet, la répartition initiale des ressources est plus difficile à modifier, et les négociations finissent rapidement dans des optima locaux. De plus, dans ce cas, l’écart type est beaucoup plus élevé. Les processus de négociation basés sur des grilles mènent à des allocations plus faibles. La connectivité moyenne des réseaux d’accointances est une caractéristique importante, affectant l’efficacité des négociations. Les capacités de communication des agents sont trop restreintes pour permettre une circulation efficace des ressources, et empêchent l’atteinte de solutions optimales. La comparaison entre les résultats obtenus sur des graphes Erdős-Rényi et sur des petits-mondes indique qu’un grand nombre d’agents ayant un petit voisinage pénalise beaucoup les processus de négociation. En effet, par définition, sur un graphe Erdős-Rényila probabilité de liens entre deux agents est uniforme alors qu’elle dépend de la taille du voisinage dans le cas d’un petitmonde. Il y a alors beaucoup d’agents avec peu de voisins dans un petit-monde qui pénalisent le processus de négociation. Les expérimentations que nous avons menées nous permettent de clarifier les politiques les plus efficaces pour atteindre un bien-être global satisfaisant. Les négociations entre agents sociaux mènent à des allocations plus intéressantes que celles atteintes par des agents rationnels. Autoriser à la fois les dons et les échanges (ie ∆ = {h1, 0i, h1, 1i}) peut être considéré comme la meilleure politique de négociation. Restreindre encore plus la cardinalité des transactions autorisées n’est pas efficace mais l’utilisation de transactions plus larges n’améliore pas significativement le résultat alors que le coût explose. Cependant, l’utilisation des transactions bilatérales n’est pas suffisante pour garantir l’atteinte d’un optimum global, mais mène tout de même à des allocations socialement très proches. 5. Conclusion Parmi les nombreuses possibilités permettant d’évaluer le bien-être d’une société vis-à-vis d’une allocation de ressources en satisfaisant les préférences des agents, nous nous sommes intéressés dans cet article au bien-être de Nash. En effet, cette évaluation représente un bon compromis entre satisfaction individuelle des agents et satisfaction globale de la société. Malgré ses bonnes propriétés, le bien-être de Nash est rarement utilisé en pratique pour des raisons de calculabilité. Nous avons présenté dans cet article les idées reçues les plus répandues sur le problème d’allocation de Nash. Nous avons montré l’inefficacité des techniques d’optimisation classiques et l’impossibilité de décomposer le problème en sous-problèmes solubles. La seule solution pratique pour tenter d’approcher l’optimal est donc une approche centrée individus de type 708 RSTI - RIA – 25/2011. Systèmes multi-agents: défis sociétaux multi-agent. La seconde partie décrit la méthode que nous proposons afin de résoudre efficacement le problème d’allocation de Nash, en utilisant des négociations entre agents. Nous avons spécifié les paramètres à utiliser afin d’obtenir une séquence de transactions menant à des solutions proches de l’optimum. N’importe quel type de réseau d’accointances peut être considéré, et le critère de décision des agents n’est basé que sur des informations locales. De telles hypothèses correspondent à un contexte bien plus réaliste que celui utilisé habituellement. Nous fournissons également le comportement, le critère d’acceptabilité, et le type de transaction à utiliser pour atteindre des allocations ∆-optimales. Une des limites de ces travaux vient du fait qu’il n’est pour l’instant pas possible de garantir qu’un processus de négociation converge vers un optimum global, et ce même si le réseau d’accointances est complet. Il pourrait alors être intéressant d’identifier les restrictions à imposer sur l’expression des préférences des agents afin de garantir l’atteinte d’une allocation optimale, au moins sur un réseau d’accointances complet. Au lieu d’avoir des agents infiniment riches, nous avons choisi de ne pas considérer d’argent dans notre système. Il nous semble intéressant de lever cette limitation, sans pour autant tomber dans les travers des études que nous critiquons. Chaque agent devra donc avoir un porte-monnaie fini et pourra utiliser de l’argent pour compenser une transaction qui ne lui semblerait pas satisfaisante. 6. Bibliographie Albert R., Barabási A., « Statistical Mechanics of Complex Networks », Reviews of Modern Physics, vol. 74, n° 1, p. 47-97, 2002. Arrow K., Sen A., Suzumura K., Handbook of social choice and welfare, vol. 1, Elsevier, 2002. Bachrach Y., Rosenschein J., « Sequential auctions for the allocation of resources with complementarities », Proceedings of the international joint conference on autonomous agents and multiagent systems, p. 1103-1110, 2008. Bonzon E., Lagasquie-Schiex M., Lang J., Zanuttini B., « Compact Preference Representation and Boolean Games », Autonomous Agents and Multi-Agent Systems, vol. 18, n° 1, p. 1-35, 2009. Chevaleyre Y., Endriss U., Lang J., Maudet N., « Negotiating over Small Bundles of Resources », AAMAS’05 - Autonomous Agents and multiagent systems, ACM Press, EU, The Netherlands, Utrecht, p. 296-302, July, 2005. Chevaleyre Y., Dunne P., Endriss U., Lang J., Lemaitre M., Maudet N., Padget J., Phelps S., Rodriguez-Aguilar J., Sousa P., « Issues in Multiagent Resource Allocation », Informatica, vol. 30, n° 1, p. 3, 2006a. Chevaleyre Y., Endriss U., Lang J., « Expressive Power of Weighted Propositional Formulas for Cardinal Preference Modelling », Proceedings of Principles of Knowledge Representation and Reasoning, p. 145-152, 2006b. Chevaleyre Y., Endriss U., Maudet N., « Allocating goods on a graph to eliminate envy », Proceedings of the national conference on artificial intelligence, vol. 22(1), p. 700-705, 2007. MARA et bien-être de Nash 709 Chevaleyre Y., Endriss U., Maudet N., « Simple negotiation schemes for agents with simple preferences : Sufficiency, necessity and maximality », Autonomous Agents and Multi-Agent Systems, vol. 20, n° 2, p. 234-259, 2010. Colmerauer A., Kanoui H., Van Caneghem M., « Last Steps Towards an Ultimate PROLOG », IJCAI, p. 947-948, 1981. Coste-Marquis S., Lang J., Liberatore P., Marquis P., « Expressive Power and Succinctness of Propositional Languages for Preference Representation », Proceedings of Principles of Knowledge Representation and Reasoning, p. 203-212, 2004. Cramton P., Shoham Y., Steinberg R., Combinatorial auctions, MIT Press, 2006. de Weerdt M., Zhang Y., Klos T., « Distributed task allocation in social networks », Proceedings of the international joint conference on Autonomous agents and multiagent systems), p. 1-8, 2007. Dekker A., « Studying Organisational Topology with Simple Computational Models », Journal of Artificial Societies and Social Simulation, vol. 10, n° 4, p. 6, 2007. Doyle J., « Prospects for preferences », Computational Intelligence, vol. 20, n° 2, p. 111-136, 2004. Endriss U., Maudet N., « On the Communication Complexity of Multilateral Trading : Extended Report », Autonomous Agents and Multi-Agent Systems, vol. 11, p. 01-107, 2005. Endriss U., Maudet N., Sadri F., Toni F., « Negotiating Socially Optimal Allocations of Resources », Journal of Artificial Intelligence Research, vol. 25, p. 315-348, 2006. Erdős P., Rényi A., « On Random Graphs », Publicationes Mathematicae, vol. 6, p. 290-297, 1959. Hemaissia M., El Fallah Seghrouchni A., Labreuche C., Mattioli J., « A Multilateral Multi-Issue Negotiation Protocol », Proceedings of the international joint conference on autonomous agents and multiagent systems, p. 1-8, 2007. Kaneko M., Nakamura K., « The Nash social welfare function », Econometrica : Journal of the Econometric Society, vol. 47, n° 2, p. 423-435, 1979. Kuhn H., « The Hungarian method for the assignment problem », Naval research logistics quarterly, vol. 2, n° 1-2, p. 83-97, 1955. Moulin H., Axioms of cooperative decision making, Cambridge University, 1988. Moulin H., Fair division and Collective Welfare, MIT press, 2003. Nongaillard A., Mathieu P., Everaere P., « Nash Welfare Allocation Problems : Concrete Issues », Proceedings of IEEE/WIC/ACM International Conference on Intelligent Agent Technology, IEEE Computer Society, p. 32-39, 2010. Peters H., Vermeulen D., « WPO, COV and IIA bargaining solutions for non-convex bargaining problems », International Journal of Game Theory, vol. 1, p. 1-34, 2010. Ramezani S., Endriss U., « Nash social welfare in multiagent resource allocation », Proceedings of the International Workshop on Agent-Mediated Electronic Commerce, 2009. Sandholm T., « Contract Types for Satisficing Task Allocation : I Theoretical Results », AAAI Spring Symposium : Satisficing Models, vol. 99, p. 68-75, 1998. Sandholm T., « Algorithm for optimal winner determination in combinatorial auctions », Artificial Intelligence, vol. 135, n° 1-2, p. 1-54, 2002.