D´ecider si une strat´egie est un ´equilibre de Nash pour le jeu 0=m=1 65Table des mati`eres 

Télécharger le fichier pdf d’un mémoire de fin d’études

Gestion de la cha^ne logistique

Dans di erents problemes issus de situations reelles, tel que la gestion de cha^nes logis-tiques, du fait de la necessit de faire cooperer des acteurs appartenant a des entites juridique et nanciere di erentes, voire m^eme concurrentes, une approche de resolu-tion centrale peut s’averer totalement irrealiste [89]. Plusieurs chercheurs ont abordes ces problemes en distinguant un ensemble de centres de decision, qui se coordonnent pour elaborer : des decisions strategiques (telle que la politique budgetaire), tactiques (par exemple l’elaboration d’un plan de production a moyen terme) ou operationnelles (comme l’ordonnancement de la production).
Dans un contexte centralise, Fink [48] propose un cadre de negociation, supposant l’exis-tence d’un mediateur independant, entre deux entreprises voulant coordonner leurs pro-ductions. Le probleme consider est un probleme d’ordonnancement ou le produit d’une entreprise constitue la matiere premiere necessaire pour la production de l’autre. Chaque entreprise souhaite ameliorer ses performances, le mediateur essaie de trouver un com-promis sous forme d’une sequence de t^aches pour les deux entreprises. Le mediateur a ici une vision partielle des objectifs de chaque entreprise, il propose alors des solutions qui vont ^etre acceptees ou refusees. A n d’assurer que les entreprises cooperent, la fonc-tion d’acceptation est probabiliste et force les entreprises a accepter un pourcentage de deterioration de leur pro t.
L’analyse de l’autonomie decisionnelle des acteurs d’une cha^ne logistique a et au centre de travaux s’appuyant sur des approches distribuees pour tenir compte de leurs speci – cites [15, 76]. Par exemple, dans [97], les acteurs d’une cha^ne logistique sont assimiles a des centres de decision autonomes devant realiser des actions. Ils peuvent accepter ou refuser les requ^etes des autres entites et agir en consequence. D’autres chercheurs se sont interesses a des approches davantage hierarchisees. Ils s’interessent aux mecanismes d’agregations et de desagregations des decisions au sein d’une m^eme entit decisionnelle. Dans [4] et [18], les auteurs presentent par exemple une caracterisation formelle de ces relations dans le cadre de relations cooperatives et hierarchiques. L’approche se base sur un modele de decision generique duplique au niveau de chaque centre decisionnel. Dans [68], les auteurs proposent une vision globale du reseau decisionnel et proposent trois types de modelisations : hierarchique, coordonne et heterarchique. Le premier possede un systeme central qui coordonne et assure la consistance des decisions, le second possede des centres de decisions qui se coordonnent en utilisant des informations partielles et le dernier modelise des relations intra-unites de decision. Cette derniere approche garantit une reactivit des unites de decision sans passer par une unite centrale mais ne peut pas assurer la coordination des decisions.

Jeux dans les reseaux sociaux

Dans le domaine des reseaux sociaux, la prediction du comportement des agents a in-teress de nombreux chercheurs. Plusieurs travaux ont mis l’accent sur les jeux associes a diverses formes de reseaux sociaux (voir [95] pour un apercu). D’autres ont etudi les comportements sociaux des domaines applicatifs speci ques.
Dans une etude recente, Apt et Markakis (2011) [11] ont etudi la complexit de trouver un equilibre de Nash pour un reseau social dans lequel on s’interesse a la di usion de produits multiples. S’inspirant du principe des reseaux sociaux (tels que Facebook ou Twitter), les auteurs considerent qu’un agent est in uenc par les preferences et choix de ses amis sur le reseau social. Les agents, representes par des n uds d’un graphe, sont in uences par leurs voisins et peuvent choisir une alternative de produits parmi plusieurs possibles. Dans ce graphe, la liaison entre deux agents est representee par un arc ponder qui represente le sens et le poids de cette in uence. L’utilite d’un agent depend uniquement du choix de ses voisins. Dans le jeu etudie, le gain de chaque agent augmente legerement avec le nombre d’agents qui choisissent la m^eme strategie que lui, ce qui est exactement le contraire de l’e et de congestion. Ils montrent que decider si le jeu admet un equilibre de Nash est NP-complet.
Ulterieurement, dans [91] et [12] des variantes de ce probleme ont et etudiees. En par-ticulier, ces travaux caracterisent un reseau social dans lequel tous les agents choisissent les produits etant donnee une fonction de pro t unique. Cette caracterisation permet de trouver un algorithme polynomial qui resout le probleme. Ils montrent egalement que determiner s’il existe un reseau social pour lequel tous les n uds adoptent un m^eme produit, est NP-complet. Ces problemes deviennent faciles quand le jeu est compose uniquement de deux produits.

Ordonnancement multi-agent

D’autres chercheurs ont porte une attention particuliere au probleme d’ordonnancement multi-agent. En e et, en particulier dans le domaine de l’ordonnancement de production, les environnements sont souvent multi-agents par essence, soit parce que les travaux a ordonnancer sont partages entre plusieurs agents qui sont en competition pour l’utilisa-tion de ressources, soit parce que, plusieurs decideurs ayant des objectifs contradictoires sont concernes par l’ordonnancement d’un m^eme ensemble travaux, soit encore parce que les activites a ordonnancer sont realisees par des agents di erents. Pour considerer ces problemes, deux types d’approches sont distinguees ici : le premier aborde le probleme sous l’angle de l’optimisation multi-objectif ; le second, davantage lie a ce travail, s’inte-resse a l’ordonnancement de projet, appel Multi-Agent Project Scheduling problem ou MAPS, aborde sous l’angle de la theorie des jeux.
Dans les recherches apparentees a l’ordonnancement multi-agent et multi-objectif, on distingue plusieurs classes de problemes selon les relations ensemblistes existant entre les travaux associes aux agents [2]. Lorsque tous les agents considerent le m^eme ensemble de travaux, l’ordonnancement multi-agent s’apparente a un probleme multi-objectif clas-sique ou chaque agent considere son propre objectif (di erent de celui des autres). Si chaque agent possede ses travaux propres, on dit que les agents sont en competition pour l’utilisation des machines. Si par contre, les ensembles de travaux ne sont pas disjoints mais qu’il existe une relation d’inclusion entre les ensembles pris deux a deux, on dit que les agents sont interferants. Le cas quelconque est design sous le nom de la classe des problemes non-disjoints. Ces problemes ont et tres etudies dans la litterature. Nous renvoyons le lecteur vers l’ouvrage collectif [2] pour un etat de l’art tres complet sur ces problemes.
Dans le domaine de l’ordonnancement de projet, les ressources participant a l’execu-tion du projet n’etant pas considerees explicitement, plusieurs chercheurs se sont inte-resses a un environnement ou les activites du projet sont distribuees entre un ensemble d’agents [45]. C’est l’hypothese utilisee dans les travaux de Estevez et Ferenandez (2012) [44] qui s’interessent au partage des penalites/recompenses entre les agents a posteriori, une fois le projet execute, selon si un agent a et source d’avance ou de retard pour le projet. D’autre travaux se sont interesses au cas ou la duree des activites est contr^olable comme dans [37], la reduction d’une duree operatoire induisant des co^uts supplemen-taires. Par exemple, Briand et al. [20] considerent un jeu non cooperatif represent par un graphe ou les activites sont sur les n uds. Ce jeu implique un ensemble d’agents, chacun d’eux est responsable de l’execution d’une partie du projet et contr^ole les du-rees d’execution de ses activites. Un agent client est pr^et a recompenser les agents s’ils parviennent a minimiser la duree totale du projet. Ce prix est partage entre les agents qui participent dans le projet. Pour ce contexte particulier, il est montre, dans [3], que trouver un equilibre de Nash minimisant la duree totale du projet est NP-di cile au sens fort. Par ailleurs, en utilisant les concepts de coupes augmentante et decroissante, comme de nies dans [60], et la dualite entre les problemes de ot maximum et de coupe mini-male, les auteurs proposent une formulation a variables entieres e cace pour resoudre le probleme [21].
D’autres approches de resolution de l’ordonnancement multi-agent releve plut^ot de l’In-telligence Arti cielle. Dans [108], les auteurs modelisent un jeu d’ordonnancement de t^aches dans un reseau de ot multi-agent en considerant des fonctions d’utilites. Chaque agent possede un ensemble de ressources necessaires pour executer di erentes t^aches et doit decider de la repartition de ses ressources entre les t^aches a n de maximiser son utilite. Dans [66] et [67], les auteurs considerent un ordonnancement de projet distribue impliquant des agents autonomes et proposent une approche basee sur la negociation entre les agents a n de montrer l’inter^et du partage d’information entre les agents. Dans [101], les auteurs considerent un probleme d’ordonnancement de projet decentralis et proposent un cadre general de resolution qui se focalise sur le respect des contraintes de ressources. Di erentes possibilites d’organisation (bottom-up, to-down, equivalent) et de prise de decision sont considerees ou chaque projet est contr^ole par un gestionnaire de projet. Une decision est associee a une activite, a une ressource ou a un coordinateur.

Jeux de conception ou d’expansion de reseaux

Conception de reseau

Dans cette section, nous presentons certains jeux de conception de reseaux, qui se fo-calisent sur l’analyse de la perte d’e cience due au fait que les agents rationnels se comportent d’une maniere egoiste. D’une maniere generale, dans un jeu de conception de reseau, le co^ut d’utilisation d’un arc est partage entre les agents qui l’utilisent.
Dans ce domaine, les travaux developpes s’interessent essentiellement aux problemes de conception de reseaux partages ou chaque agent veut a la fois, minimiser son co^ut pour creer/utiliser le reseau, et augmenter la qualite de service dans le reseau. L’inter^et est focalise sur la prevision du comportement des agents. Plusieurs etudes se sont concentrees sur les jeux associes a di erentes formes de reseaux. Nous regroupons ici une revue de quelques travaux.
Ce probleme a et initialement introduit par [10] et [9] pour construire des reseaux partages. Dans ces jeux de conception de reseaux partages, un agent detient son ensemble propre de n uds dans le reseau. Son objectif est d’augmenter la connectivit globale de ses n uds a co^ut minimum. Il participe ainsi nancierement a creer un ensemble d’arcs dans le reseau, la connectivit du reseau etant la principale mesure de qualite. Les co^ut sont de nis par arc, et les agents qui utilisent un arc partagent son co^ut selon une politique de partage equitable. Un autre e ort quantitatif d’analyse de la perte d’e cience dans des reseaux stables a et realis par Fabrikant et al. (2003) [46]. Ici, les auteurs considerent un jeu de conception locale de reseau. Chaque agent, represent par un n ud, mesure la qualite du reseau comme la somme des distances vers tous les autres n uds. L’objectif d’un agent est de minimiser une fonction combinant a la fois la qualite du reseau et le co^ut de construction. Cette fonction exprime le compromis entre la minimisation de la somme des co^uts de construction et de la distance vers tous les autres agents. Dans [95], les auteurs considerent un jeu d’implantation d’installations (Facility Location Game) ou les agents payent un co^ut par arc et de nissent un prix d’usage pour les agents usagers. Dans ce jeu, les acteurs placent des installations pour servir des clients contre un prix d’usage. Le pro t des agents est la di erence entre le prix d’usage et le co^ut supporte. Ils montrent qu’un reseau e cient socialement est stable. Leur objectif est de borner la perte d’e cience resultante du comportement rationnel des agents (i.e., Prix de l’Anarchie (POA) et Prix de la Stabilite (POS)).

Jeux d’expansion de reseau

Une question naturelle dans plusieurs applications de probleme de reseau concerne la determination d’une augmentation de capacite a co^ut minimum. On parle alors de pro-blemes d’expansion de reseau. Plusieurs applications de ce probleme ont eu lieu dans di erents domaines, tels que la production de biens [107], les services publics d’electri-cite [71], les telecommunications [65], la gestion des stocks [58] et le transport [69], [52] et [84]. La plupart des approches considere un environnement mono-agent. Notre travail etant centr sur ces problemes d’expansion, nous les passons rapidement en revue avant de nous focaliser sur la version multi-agent de ce probleme. Fulkerson [52] a et un des premiers a considerer le probleme d’allocation de budget de ressources dans un reseau a n d’augmenter sa capacite de circulation de ot par rapport a une source et un puits donnes. L’auteur propose un algorithme d’etiquetage pour cal-culer l’allocation optimale etant donne un co^ut d’augmentation lineaire de la capacite sur les arcs.
Ordonez et Zhao (2007) [84] considerent le probleme d’expansion des capacites dans un reseau soumis a une demande et a des temps de trajet incertains. Ils proposent une approche d’optimisation robuste pour trouver une solution d’expansion de reseau de transport minimisant les co^uts. Dans [39], les auteurs considerent un probleme d’expan-sion de capacite d’un reseau en supposant que le co^ut d’augmentation de la capacite d’un arc depend de ses caracteristiques physiques, notamment sa longueur. Ce travail est etendu dans [40] et [41], ou les auteurs a nent l’algorithme deja propose pour tenir compte d’une structure de reseau plus complexe, a savoir avec plusieurs origines et desti-nations. Dans [41], les auteurs presentent un algorithme pour minimiser l’investissement consacre a augmenter la capacite d’un reseau de transport a plusieurs origines et desti-nations. L’algorithme prend en compte les demandes des destinations et les restrictions economiques ou techniques dans l’expansion de capacite. A chaque etape, l’algorithme choisit l’arc le moins co^uteux, ce qui assure que la solution entiere est a co^ut minimum. L’inconvenient de cet algorithme est qu’il utilise des appels repetitifs a l’algorithme de Ford-Fulkerson, ce qui a ecte l’e cacit de l’algorithme pour les reseaux de grandes tailles. Dans [13], les auteurs considerent le probleme de plani cation de capacite dans des reseaux de telecommunication modelises comme des problemes de ot multimodaux avec un co^ut de capacite et une demande incertaine. Ils presentent une methode d’opti-misation robuste pour trouver un compromis entre la qualite de service exigee et le co^ut d’investissement.
Dans [7], une application concrete de ce travail est propose dans le domaine de l’exploi-tation agricole. Une methode basee sur la programmation dynamique est proposee pour optimiser le niveau d’investissement pour plusieurs investisseurs.
Nous nous interessons a present au contexte multi-agent. Dans [88], les auteurs consi-derent un jeu cooperatif de ni dans des reseaux de ot, ou les agents forment des coa-litions pour faire circuler du ot. Les auteurs focalisent leur analyse sur le c ur du jeu cooperatif, qui contient toutes les distributions stables de la coalition. Dans un contexte de jeu cooperatif, une coalition est stable si elle veri e a la fois la stabilite interne et externe selon D’Aspremont et al. (1983). La stabilite interne signi e qu’aucun agent cooperant n’a inter^et a quitter la coalition pour ameliorer son propre pro t. La stabilite externe signi e que toute repartition en dehors de l’ensemble est dominee par au moins un membre de l’ensemble [36]. Si le c ur du jeu est vide, c’est-a-dire s’il n’existe aucune coalition stable, alors les auteurs supposent qu’un organisme externe peut allouer un paiement supplementaire a la coalition, ce qui peut stabiliser le jeu si le paiement est su samment eleve. Les auteurs etudient dans ce cadre le Prix de la stabilite (PoS) pour les jeux de reseaux de ot avec seuil (Threshold Network Flow Game ou TNFG). Un jeu de reseau de ot avec seuil (TNFG) est un jeu cooperatif ou chaque agent contr^ole un arc du reseau et forme des coalitions pour faire circuler du ot d’un n ud source vers un n ud puits, la coalition etant stable si le ot resultant est superieur a un seuil donne. Dans ce cadre, il est prouve que determiner si une distribution donnee est stable est CoNP-complet.
Le TNFG a ete aussi etudi par [59] et [14]. Les auteurs s’interessent a calculer des indices de pouvoir pour chaque agent. Ces indices re etent le poids reel d’un agent et sont estimes par un systeme de vote ponder . Pour garantir que le reseau soit capable d’assurer le ot desire, des ressources sont allouees en fonction de leur impact sur la valeur du ot (i.e., les ressources doivent ^etre allouees sur des arcs dont la defaillance est davantage susceptible d’entra^ner une baisse du ot). Ils montrent que le calcul de ces indices dans ce type de reseau est NP-di cile mais que le calcul du c ur du jeu peut ^etre fait en temps polynomial.

Positionnement de notre travail

Notre travail s’interesse a revisiter un probleme particulier de reseau, le probleme d’ex-pansion de reseaux, dans un contexte multi-agent. La nature et la complexit des pro-blemes d’optimisation de reseaux varient considerablement quand on considere un contexte multi-agents.
Dans ce travail, nous considerons un reseau de transport modelis par un graphe de ot, impliquant plusieurs agents, chacun d’eux etant en charge d’une partie des arcs du reseau. Chaque agent transporteur contr^ole les capacites de ses arcs, le co^ut supporte par l’agent etant suppose proportionnel a l’augmentation de capacite.
Nous etudions principalement le probleme de recherche de strategie stable, i.e., equilibre de Nash, qui maximise le ot transporte dans le reseau que nous comparons au ot maximum accessible. Dans ce travail, nous nous situons dans un contexte de jeu non-cooperatif et nous assimilons une strategie stable a un equilibre de Nash. Comme pour le probleme d’Ordonnancement de Projet multi-agent etudi dans [3, 20], nous supposons qu’il existe un agent client recompensant les agents en fonction du ot qu’il recoit : le gain d’un agent de transport depend donc de sa strategie et de la satisfaction de l’agent client, qui est liee au ot circulant dans le reseau. La politique de partage sera tour a tour consideree xe ou, au contraire, libre. Nous presentons dans la partie experimentale (cf. chapitre 8) une comparaison entre les deux approches.
Une application importante a ce probleme est l’expansion de la capacite d’un reseau de transport (ferroviaire, routier, pipelines, etc.) pour couvrir des pics de demandes ou pour absorber des augmentations futures en presence de plusieurs operateurs de transport, eventuellement concurrents. Nous supposons que les usagers du systeme de transport re-munerent les operateurs de transport librement, cela proportionnellement au ot o ert. Dans un tel systeme, le bien-^etre social peut ^etre assimile au ot total vehicul au sein du reseau.
Notre travail presente donc de fortes similitudes avec le probleme MAPS decrit dans [3], bien que le probleme etudie soit di erent de celui de l’ordonnancement de projet. Nous nous situons egalement dans la mouvance des travaux developpes par [59, 88] et [14] qui s’interesse a des jeux cooperatifs d’expansion de reseau. Cependant, nous faisons l’hypothese ici d’un environnement non-cooperatif, ou les acteurs ne forment pas de coalition et ne partagent pas les co^uts d’expansion. Les jeux de construction de reseau sont eux aussi relativement proches bien que, dans notre cas, les agents contr^olent la capacite des arcs.

Problemes consideres

Enonce du probleme

Dans le cadre de cette these, nous considerons un jeu d’expansion de reseau multi-agent. D’une maniere generale, nous considerons des jeux impliquant trois types d’agents ra-tionnels : des agents producteurs, des agents transporteurs et des agents usagers. Les agents producteurs sont responsables de la mise a disposition de produits a acheminer a travers le reseau de transport. Leur objectif est de maximiser la quantite de leurs produits circulant dans le reseau. Chaque agent transporteur detient son propre ensemble d’arcs dans le reseau et est capable d’augmenter la capacite de ses arcs a co^ut xe moyennant des ressources supplementaires. La capacite d’un arc de transport a une valeur normale (minimale) et peut ^etre augmentee jusqu’a une valeur maximale. La valeur normale de la capacite est la valeur que l’on peut utiliser pour faire circuler des produits dans le reseau a co^ut nul. Les agents usagers, comme leur nom l’indique, sont des utilisateurs du reseau, ils veulent maximiser la quantite de produits recus, pour satisfaire leur demande en produits. Nous supposons que les agents ne cooperent pas et ne forment donc pas de coalition.
Selon le nombre d’agents de chaque type en interaction, nous considererons di erents scenarios possibles entre les agents comme le resume la Figure 2.1 dans laquelle T re-presente les agents de transport, U les agents usagers, P les agents producteurs et ou F et indiquent l’existence d’un ux de produits et d’un ux nancier (une recompense), respectivement. Dans les di erents scenarios du jeu, les agents transporteurs du reseau T jouent un r^ole central du fait qu’ils recoivent des recompenses pour faire circuler du ot. Contrairement a [25], ou les auteurs supposent que la recompense est partagee entre les agents selon des ratios collectivement convenus durant la phase de conception du re-seau, on suppose ici que la politique de partage peut ^etre partie integrante de la prise de decision des producteurs et usagers.
La Figure 2.1(a) illustre le cas d’un jeu entre des agents usagers et des agents trans-porteurs exclusivement. Ce jeu se deroule comme suit : les agents usagers donnent une recompense aux agents transporteurs proportionnelle a leur quantite de produits circu-lant dans le reseau. Cette recompense a pour but de motiver ces derniers a augmenter leurs capacites (cf. [3, 44]), les gains des agents transporteurs etant egaux a la recom-pense recue moins les co^uts d’expansion de leurs arcs. La strategie d’un agent usager consiste a decider la politique de partage de sa recompense entre les agents transporteurs a n de maximiser la quantite de produits recus. Le jeu decrit dans la Figure 2.1(b) est symetrique a celui consider dans (a) : les agents producteurs donnent une recompense aux agents transporteurs pour les inciter a augmenter la capacite de leurs arcs et aug-menter ainsi la quantite de marchandises circulant dans le reseau.
capacites de leurs arcs et recoivent une recompense de la part des agents usagers et/ou producteurs. Quant a eux, les agents usagers et producteurs decident du partage des recompenses entre les transporteurs, toujours a n de maximiser la quantite de produits qui circule dans le reseau.

Topologie du reseau

Nous considerons une topologie particuliere du reseau multi-agent, representee sur la Figure 2.2 ou les agents sont a ectes aux arcs du reseau.
Le reseau multi-agent peut ^etre decompos en trois parties separees par deux coupes C1 et C2. La premiere coupe C1 contient tous les arcs des agents producteurs et la deuxieme coupe C2 contient tous les arcs des agents usagers. Les arcs de la coupe C1 appartiennent cha-cun a un agent producteur. Ces arcs representent le reseau des agents producteurs P et relient le n ud super-source S s avec des agents transporteurs. Un arc (i.e., un centre de production) est caracteris par un intervalle d’o re minimale et maximale [oi;j; oi;j] que l’on supposera egale a [0; +1] (la prise en compte d’o re minimale et maximale ne changeant pas fondamentalement la nature du probleme.
La seconde partie est le reseau forme par les agents de transport T compose d’arcs qui assurent l’acheminement des produits des producteurs vers les clients. Chaque arc de transport est caracteris par un intervalle de capacite minimale et maximale [qi;j; qi;j] et par un co^ut d’expansion unitaire ci;j. Le reseau T ainsi de ni permet la circulation d’un ot a travers des chemins dont les arcs sont distribues entre di erents agents transpor-teurs.
De facon symetrique, la deuxieme coupe C2 correspond aux agents usagers U qui relient le reseau de transport avec le super-puits S t. Un arc appartenant a un agent usager est caracteris par un intervalle de demande minimale et maximale [di;j; di;j] que l’on . . . tm p q C1 [ qi , j , [0, +∞[ qi , j ],ci , j u1 u2 . S-t . . up C2 [0, +∞[ supposera aussi egale a [0; +1].
Dans cette topologie, chaque chemin de la super-source vers le super puits commence obligatoirement par un arc appartenant a seul un agent producteur et nit necessaire-ment par un arc appartenant a un seul agent usager. Le modele de graphe associe est un graphe de ot (aussi appel reseau de transport).

De nitions

De nition du jeu d’expansion de reseau

Nous considerons un jeu non-cooperatif d’expansion de reseau se deroulant simultane-ment entre un ensemble de q agents producteurs, de m agents transporteurs et de p agents usagers. Ce jeu consiste a etendre la capacite d’un reseau de transport multi-agent a n de faire circuler des produits depuis leurs centres de production vers les usagers via un reseau de transport central. Ce reseau multi-agent est assimile a un graphe de ot ou les arcs sont distribues entre des agents ayant di erents r^oles. Les agents usagers et/ou producteurs veulent maximiser leur ot circulant dans le reseau et donnent pour cela une recompense xee pour chaque unite de ot supplementaire circulant sur l’un de leurs arcs. Chaque agent transporteur contr^ole la capacite de ses arcs qui varie entre sa valeur normale et maximale. Simultanement , les agents usagers et/ou producteurs decident de leur politique de partage de recompense et les agents transporteurs decident la capacite de leurs arcs respectifs.
Nous considerons que maximiser le ot total circulant dans le reseau est l’objectif global (ou social) poursuivi par tous les agents. Cet objectif global est une consequence directe des objectifs individuels des agents usagers ou producteurs. Les agents transporteurs cooperent pour satisfaire cet objectif global, a condition bien s^ur que leurs pro ts soient ameliores.
Le jeu, appel Jeu d’Expansion de Reseau (NEG) (Network Expansion Game), decrit ci-dessus, se deroule dans un Reseau Multi-Agent (RMA), de ni comme suit : Un RMA est decrit par un tuple < G; A; I; I; C; > ou : | G = (V; E) est un graphe de ot. V est l’ensemble des n uds ou S s; S t 2 V sont les n uds super-source et super-puits du graphe G, respectivement. L’ensemble des arcs E = EP [ ET [ EU est reparti entre les producteurs EP , les transporteurs ET et les usagers EU selon la topologie decrite precedemment (cf. Section 2.2.2). Notons par e = (i; j) un arc e allant du n ud i au n ud j.
| A = AP [ AT [ AU est l’ensemble des agents qui composent le jeu, ou : | AT = faT1 ; : : : ; aTx ; : : : ; aTmg est l’ensemble des m agents transporteurs ; | AU = faU1 ; : : : ; aUy ; : : : ; aUp g est l’ensemble des p agents usagers.
| AP = faP1 ; : : : ; aPz ; : : : ; aPq g est l’ensemble des q agents producteurs ;
| I = (qi;j)(i;j)2ET designe le vecteur de capacite normale entiere pour les arcs de l’ensemble ET . Ce vecteur represente la quantite de produits qu’un agent peut transporter sur ses arcs sans payer de co^ut supplementaire ;
| I = (qi;j)(i;j)2ET designe le vecteur de capacite maximale entiere pour les arcs de l’ensemble ET et represente la quantite maximale de produits qu’un agent peut transporter.
| C = (ci;j)(i;j)2AT designe le vecteur de co^uts unitaires d’expansion pour les trans-porteurs ;
| = ( u)u2AU[AP est le vecteur de recompenses donnees par les agents usagers et/ou producteurs pour chaque unite additionnelle de ot qui circule sur un de leurs arcs.
Les arcs du reseau multi-agent sont de nis comme suit :
| chaque agent transporteur aTx possede un ensemble de mTx arcs, que nous no-tons ExT . Chaque arc (i; j) 2 ET appartient a exactement un et un seul agent | 2 EyU . Le transporteur : ExT \ ExT0 = ;, 8 (aTx ; aTx0) 2 AT AT tel que x 6= x0. Chaque arc (i; j) 2 ET est caracteris par une valeur normale et maximale de la capacite qi;j et qi;j, respectivement. Un agent transporteur peut augmenter la capacite d’un arc (i; j) 2 ET par une unite moyennant un co^ut ci;j.
| chaque agent usager aUy possede un ensemble de mUy arcs, que nous notons EyU . Chaque arc (i; j) 2 EU appartient a exactement un seul agent usager : EyU \EyU0 = ; pour chaque paire d’agents usagers (aUy ; aUy0) 2 AU AU tel que y 6= y0.
| chaque agent producteur aPz possede un ensemble de mPz arcs, que nous notons EzP . Chaque arc (i; j) 2 EP appartient a exactement un seul agent usager : EzU \EzU0 = ; pour chaque paire d’agents usagers (aPz ; aPz0) 2 AP AP tel que z 6= z0.
De nition 2.2. Jeu d’expansion de reseau.
Un jeu d’expansion de reseau est caracteris par un RMA et un vecteur de strategies S = (ST ; SU ; SP ) compose :
| des strategies des agents transporteurs : ST = (S1T ; : : : ; SmT) ou SxT = (qi;j)(i;j)2Ex est la strategie de l’agent transporteur aTx . La capacite qi;j choisie par l’agent aTx est un entier qui veri e qi;j 2 [qi;j; qi;j] pour tout arc (i; j) 2 aTx ;
| des strategies des agents usagers : SU = (S1U ; : : : ; SpU ) ou SyU = wy = (wxy)x=1;:::;m est la strategie de l’agent usager aUy et represente sa politique de partage pour chaque unite de ot additionnelle circulant sur un de ses arcs (i; j) partage de recompense wy choisi par l’agent usager aU est tel que : P wy = 1. y x2AT x | des strategies des agents producteurs : SP = (S1P ; : : : ; SqP ) ou SzP = wz = (wxz)x=1;:::;m est la strategie de l’agent producteur aPz et represente sa politique de partage pour chaque unite de ot additionnelle circulant sur un de ses arcs (i; j) 2 EzP . Le partage de recompense wz choisi par l’agent producteur aPz est tel que : P T wz = 1. x2A x

Le cas mono-producteur ou mono-usager

Dans cette section, nous presentons des proprietes speci ques au cas ou un seul agent, producteur ou usager, distribue une recompense aux agents de transport. Dans ce cas particulier, l’objectif social est donc confondu avec l’objectif de l’unique agent (produc-teur ou usager) fournissant la recompense. Ce cas mono-producteur ou mono-usager sera etudi en details dans les chapitres suivants (chapitres 3, 4 et 5).

Pro t des agents et strategies pauvres

Pour une strategie S, lorsqu’un unique agent, usager aUy (respectivement producteur aPz ), delivre la recompense, son pro t est egal au ot maximum circulant dans le reseau : ZyU (S) = F (S) (respectivement ZzP (S) = F (S)).
Le pro t d’un agent de transport aTx depend alors de la valeur du ot maximal qui (F(S) F) P(i;j)2ET ci;j (qi;j qi;j). x S ) = Pu2AU[AP x u ) circule auquel il faut soustraire ses co^uts d’expansion : ZT ( (wu
Nous de nissons alors la notion de strategie pauvre. Ce concept sera utile pour caracte-riser plus precisement la notion d’equilibre de Nash.
Une strategie S ayant une valeur de ot maximal F (S) > F est dite pauvre s’il existe un agent quelconque au ayant une strategie alternative Su0 produisant une valeur de ot maximale F (Su0; S u) = F (S) tel que Zu(Su0; S u) > Zu(S).
En d’autres termes, puisqu’un agent usager et/ou producteur ne peut pas ameliorer son pro t etant donne que F (S0) = F (S), une strategie est pauvre quand un agent trans-porteur est capable de trouver une strategie ameliorant son pro t a ot constant.
Nous notons l’ensemble des strategies non pauvres par S np
. Evidemment, une strategie
pauvre ne peut pas ^etre un equilibre de Nash, i.e., SN Snp.
Une strategie pauvre S = (Su; S u) peut ^etre transformee en une strategie non pauvre S0 = (Su0; S u) en adaptant la strategie Su de l’agent au tout en maintenant les strategies
S u des autres agents xees. S0 S0 Etant donnee une valeur de ot F ( ) une strategie non pauvre peut ^etre la solution du programme non lineaire suivant : max T Z ( ) s:c:q: Pax 2AT x S0 (i) Zx(S0) Zx(S); 8axT 2 AT (ii) F(S) = F(S0) (iii) fi;j0 qi;j0 ; 8(i; j) 2 E 8 0 8i 6= s; t (2.1) (vi) (i;j)2E f i;j0 (j;i)2E f j;i0 = > F ; i = s > P P < F ; i = t (v) q q ; (i; j) 2 E T > i;j q i;j0 i;j : > fi;j0 0; 8(i; j) 2 ET
Le programme mathematique 2.1 peut ^etre utilise a la fois pour veri er si une strategie est pauvre et pour ameliorer la strategie a n de remedier a sa pauvret . Dans le premier cas, si on xe les strategies de tous les agents sauf un seul et qu’il existe une solution au probleme 2.1 alors S est pauvre. Dans le deuxieme cas, le programme mathematique 2.1 donne une solution non pauvre S0 si on l’applique pour tous les agents au 2 A.
Demonstration. Soit S 0 une solution optimale du programme mathematique 2.1. Si un agent au etait capable d’augmenter son pro t en adoptant une nouvelle strategie Su, cela sans modi er la valeur du ot, alors la strategie (Su; S0 u) serait meilleure que S0 , d’ou une contradiction.

Jeu d’expansion de reseau 0=1=1

Cette section traite du jeu d’expansion particulier 0=1=1 qui se deroule de maniere simul-tanee entre un agent usager et un agent transporteur. L’agent transporteur, qui possede tous les arcs du reseau de transport, decide d’etendre ou pas la capacite de ses arcs dans l’intervalle prede ni de valeurs normale et maximale. Comme l’agent transporteur est unique, il recoit la totalite de la recompense donnee par l’agent usager. Notons que, pour ce modele avec un seul agent usager, l’objectif social correspond a l’objectif individuel de l’agent usager, a savoir maximiser le ot global. Par ailleurs, la notion de stabilite n’a pas de sens dans ce contexte car l’agent transpor-teur est unique (cf corollaire 2.14). Par consequent, nous nous interessons a maximiser le ot de produits transportes dans le reseau de sorte que cela demeure pro table pour l’agent transporteur, i.e., que son pro t ne soit pas negatif. Ce probleme est donc proche des problemes d’expansion de reseau evoques au chapitre 1. La speci cit de notre travail reside dans le fait que, pour realiser l’expansion d’un reseau, il existe un agent client (usager/producteur) fournissant une recompense proportionnelle a l’augmentation de ot dans le reseau. De ce fait, nous nous interessons a la maximisation du ot dans le reseau de maniere pro table pour l’unique agent de transport.

Jeu d’expansion de reseau 0=m=1

De nition formelle du jeu 0=m=1

Pour le jeu 0=m=1, le RMA se compose uniquement du reseau de transport T et le ot resultant dans le reseau sera egal au ot recu par l’unique agent usager. De nouveau, l’objectif social se confond avec l’objectif individuel de cet agent. Le jeu d’expansion de reseau caracteris dans la partie 2.3.1 se simpli e donc de la maniere suivante :
De nition 4.1. Reseau Multi-Agent 0=m=1.
Un RMA 0=m=1 decrit par le tuple < G; A; I; I; C; > tels que :
| G = (V; E) est un reseau de transport dans lequel l’agent usager est a ect au sommet puits. Les arcs se repartissent entre les di erents agents transporteurs : E=ET;
| A = fAT [faUm+1gg est compose d’un ensemble de m transporteurs faT1 ; : : : ; aTu ; : : : ; aTmg et d’un unique agent usager aUm+1 ;
| I (resp. I) est le vecteur des capacites minimales (resp. maximales) pour le reseau des agents transporteurs T ; | (i;j)2ExT ci;j
| C = (ci;j)(i;j)2AT designe le vecteur de co^uts unitaires d’expansion pour les agents transporteurs ;
| est la recompense totale donnee par l’agent usager pour chaque unite addition-nelle de ot qui circule dans le reseau.
De nition 4.2. Strategies et pro ts des agents.
Dans le jeu 0=m=1, la strategie S recouvre les strategies des agents de transport et la strategie de l’agent usager : S = (ST ; SU ).
| les strategies des agents de transport sont : ST = (S1T ; : : : ; SmT) ou SxT = (qi;j)(i;j)2Ex , 8x 2 AT.
| la strategie de l’agent usager est : SmU+1 = (wx)x=1;:::;m.
Les pro ts des agents pour une strategie S associee a un ot maximal F (S), s’ecrivent alors :
| pour chaque agent transporteur aTx : ZxT (S) = wx (F (S) F ) P (qi;j qi;j).
| pour l’agent usager : ZmU+1(S) = F (S).
Rappelons que S represente la strategie particuliere pour laquelle les capacites des trans-porteurs sont a leurs valeurs minimales.
Dans un jeu 0=m=1, chaque agent transporteur aTx est libre d’augmenter (ou de diminuer) unilateralement les capacites de ses arcs a n d’ameliorer son pro t ZxT . La stabilite d’une strategie S n’est donc pas assuree a priori. Le probleme qui nous interesse est alors le probleme MaxNash de ni dans la partie 2.3.2 pour lequel nous allons chercher une strategie equilibre de Nash maximisant le ot total.

Exemple d’une instance du jeu 0=m=1

Dans l’exemple suivant, nous allons introduire un jeu qui se deroule entre deux agents de transport. Le deroulement du jeu va ^etre present en details dans la Section 4.4. Considerons le reseau donne dans la Figure 4.2. Ce reseau est compose de deux agents transporteurs aT1 et aT2 ainsi que d’un agent usager souhaitant transporter la plus grande valeur possible de ot du noeud A vers le noeud D et o rant pour cela une recompense = 120, partagee selon une politique SmU+1 = (w1; w2).
La repartition des arcs entre les agents transporteurs est : E1T = fb = (A; C); c = (B; C); d = (B; D)g et E2T = fa = (A; B); e = (C; D)g, representes par les arcs simples et pointilles, respectivement. Les intervalles de capacites normales et maximales ([qi;j; qi;j]), et les co^uts d’expansion (ci;j) apparaissent sur chaque arc du graphe.
Considerons en particulier, l’arc a allant de A vers B, cet arc a comme intervalle de capacite est [0; 2] et son co^ut d’expansion unitaire est egal a 50.

Table des matières

1 Probl`emes de d´ecision multi-agents 
1.1 Introduction
1.2 Approches issues de la th´eorie des jeux
1.2.1 Th´eorie des jeux non coop´eratifs
1.2.2 Equilibres et stabilit´e ´
1.2.3 Autres jeux
1.3 Approches issues de l’optimisation combinatoire
1.3.1 Optimisation multi-objectif
1.3.2 Optimisation bi-niveaux
1.3.3 Optimisation distribu´ee
1.3.3.1 Probl`emes de satisfaction de contraintes distribu´ees
1.3.3.2 Probl`emes d’optimisation sous contraintes distribu´ees
1.4 Syst`emes multi-agents
1.5 Exemples de probl`emes de d´ecision multi-agents
1.5.1 Planification de r´eunions
1.5.2 Gestion de la cha^ıne logistique
1.5.3 Jeux dans les r´eseaux sociaux
1.5.4 Ordonnancement multi-agent
1.5.5 Jeux de conception ou d’expansion de r´eseaux
1.5.5.1 Conception de r´eseau
1.5.5.2 Jeux d’expansion de r´eseau
1.6 Positionnement de notre travail
2 R´eseaux de transport multi-agents 
2.1 Introduction
2.2 Probl`emes consid´er´es
2.2.1 Enonc´e du probl`eme
2.2.2 Topologie du r´eseau
2.3 D´efinitions
2.3.1 D´efinition du jeu d’expansion de r´eseau
2.3.2 Strat´egies remarquables
2.3.3 Exemple
2.4 Le cas mono-producteur ou mono-usager
2.4.1 Profit des agents et strat´egies pauvres
2.4.2 Propri´et´es basiques
2.5 Synth`ese des jeux
3 Probl`emes 0=1=1 et 1=1=0 
3.1 Introduction
3.2 Jeu d’expansion de r´eseau 0=1=1
3.2.1 D´efinition formelle du jeu 0=1=1
3.2.2 Exemple
3.3 Propri´et´es du jeu
3.3.1 Graphe r´esiduel
3.3.2 Variation du flot dans le r´eseau
3.3.3 Dualit´e
3.3.4 Augmenter le flot
3.3.5 Diminuer le flot
3.4 Jeu d’expansion de r´eseau 1=1=0
3.5 Exemple
3.6 Conclusion
4 Probl`emes 0=m=1 et 1=m=0 
4.1 Introduction
4.2 Jeu d’expansion de r´eseau 0=m=1
4.2.1 D´efinition formelle du jeu 0=m=1
4.2.2 Exemple d’une instance du jeu 0=m=1
4.3 Mod`ele math´ematique
4.4 Exemple illustratif
4.5 Variation de flot
4.5.1 Graphe r´esiduel multi-agent
4.5.2 Augmenter le flot de mani`ere profitable
4.5.3 Diminuer le flot de mani`ere profitable
4.6 Strat´egies stables
4.7 Conclusion
5 Complexit´e 
5.1 Introduction
5.2 Complexit´e de trouver un ´equilibre de Nash
5.2.1 D´ecider si une strat´egie est un ´equilibre de Nash pour le jeu 0=m=1 65Table des mati`eres
5.2.2 Trouver un ´equilibre de Nash dans le cas 0=m=1 pour wx fix´ee
5.3 Trouver un ´equilibre de Nash qui maximise le flot pour 0=m=1
5.3.1 Cas d’une politique de partage ´egalitaire
5.3.2 Cas d’une politique de partage variable
5.4 Trouver une strat´egie profitable pour 0=m=1 pour wx fix´ee
5.5 Cas particulier jExTj = 1; 8aT x
5.6 Conclusion
6 Premier pas vers une g´en´eralisation 
6.1 Introduction
6.2 Jeu d’expansion de r´eseau 0=m=p
6.2.1 Caract´eristiques du jeu 0=m=p
6.2.1.1 Propri´et´es basiques
6.2.2 Variation de flot
6.2.2.1 Graphe r´esiduel multi-agent
6.2.2.2 Augmenter le flot
6.2.2.3 Diminuer le flot
6.2.3 Caract´erisation d’un ´equilibre de Nash
6.3 Jeu d’expansion de r´eseau q=m=0
6.4 Jeu d’expansion de r´eseau q=m=p
6.4.1 Mod`ele math´ematique
6.5 Conclusion
7 Mod`ele lin´eaire `a variables mixtes pour le jeu 0=m=1
7.1 Introduction
7.2 Formulation math´ematique
7.3 Lin´earisation des contraintes
7.3.1 Analyse des couts r´esiduels
7.3.2 Plus court chemin dans le graphe r´esiduel
7.4 Mod`ele lin´eaire obtenu
8 R´esultats exp´erimentaux 
8.1 Introduction
8.2 Contexte exp´erimental
8.2.1 Familles d’instances
8.2.2 Politique de partage de r´ecompense
8.3 Analyse des r´esultats
8.3.1 Analyse du ratio de flot et des temps d’ex´ecution
8.3.2 Politiques de partages
Conclusion 
Bibliographie 

Télécharger le rapport complet