Recherche de flots stables dans des réseaux de transport multi-agents

Nous considérons dans ce travail, des problèmes d’optimisation dans des graphes de flot multi-agent. Trois types d’agents sont considérés : les agents producteurs, transporteurs et usagers et différentes variétés de topologies de réseaux sont abordées. Chaque agent transporteur contrôle la capacité d’un ensemble de routes élémentaires (arcs), ayant chacun une capacité qui peut être augmenté jusqu’à une valeur maximale moyennant un coût fixe. Les autres agents (i.e., usagers/producteurs) sont intéressés par la maximisation du flot qu’ils reçoivent. Dans ce but, ces derniers offrent une récompense aux agents transporteurs, cette récompense est proportionnelle à la valeur du flot reçu. Ce contexte multi-agent particulier est appelé jeu expansion de réseau multi-agent. La stratégie d’un agent transporteur consiste à décider de la capacité de ses arcs sachant qu’un coût supplémentaire est encouru pour toute expansion unitaire de capacité. Il reçoit en contrepartie une part de la récompense. Il est intéressé par la maximisation de son profit et se comporte en conséquence. En outre, la stratégie d’un agent producteur/usager consiste à décider de la politique de partage de sa récompense afin de maximiser le flot qu’il reçoit. Le flot total réalisé dépend finalement des stratégies de tous les agents. Dans ces jeux d’expansion de réseau multi-agent, nous nous intéressons à caractériser des stratégies stables (i.e., Equilibre de Nash) selon diverses hypothèses. En se basant sur cette caractérisation, différents cas sont définis et étudiés. L’analyse de la complexité de quelques problèmes de décision est présentée dans ce manuscrit. Nous nous intéressons particulièrement au problème de recherche d’un équilibre de Nash qui maximise la valeur du flot total circulant dans le réseau. Nous montrons que ce problème est NP-difficile au sens fort et nous montrons comment une telle stratégie peut être caractérisée par des chemins spécifiques dans des graphes résiduels. Nous proposons également un programme linéaire à variables mixtes (PLM) qui résout le problème dans le cas d’un seul agent producteur/usager et un ensemble d’agents transporteurs. Des résultats expérimentaux sont fournis pour prouver l’efficacité de notre approche.