A verification viewpoint on network congestion games

Les jeux de congestion dans les réseaux sous l’angle de la vérification Les jeux de congestion sont un domaine de recherche bien étudié ; dans ce domaine, les jeux de congestion dans les réseaux permettent de représenter la congestion des réseaux de distribution, et d’étudier à quel point un modèle de réseau est bon ou mauvais en termes de coût total lorsque chaque joueur joue de façon égoïste, cherchant uniquement à optimiser son propre coût ; Nous considérons ces jeux de congestion du point de vue des méthodes formelles, cherchant à vérifier par exemple que, dans un réseaux fixé, il existe un profil de stratégies optimal qui satisfasse une propriété donnée. Nous définissons un modèle de jeux de congestion avec deux particularités : d’une part, le calcul du coût d’une transition dépend du nombre de joueurs utilisant simultanément une arête ; d’autre part, les joueurs choisissent leur chemin de façon dynamique en fonction des choix des autres joueurs. Nous montrons que dans ce modèle les équilibres de Nash existent toujours en montrant la convergence de la dynamique de meilleure réponse. Nous étudions ensuite le problème de vérification mentionné ci-dessus, résolvant le problème de l’existence d’un équilibre social, d’un équilibre de Nash ou d’un équilibre parfait en sous-jeux ayant un côut borné. Dans une deuxième partie, nous étudions les jeux de congestion paramétrés, dans lesquels le nombre de joueurs est un paramètre. Nous nous intéressons à l’évolution des équilibres de Nash en fonction du nombre de joueurs : notre objectif est de calculer efficacement l’ensemble des équilibres de Nash pour un nombre arbitrairement grand de joueurs, à partir des équilibres de Nash pour de petits nombres de joueurs. Nos premiers résultats portent sur les réseaux série-parall‘ele, sans les particularités ci-dessus. Nous conjecturons que ces résultats s’étendent à l’ensemble des graphes, ce qui donnerait lieu à un calcul efficace de tous les équilibres de Nash, quel que soit le nombre de joueurs.