Aller au contenu

| | |

Vous êtes ici : UVSQ RechercheDoctorat

«Existence et calcul distribué d'équilibres dans des jeux de congestion généralisés» par Lise Rodier

Présentée par : Lise Rodier Discipline : informatique Laboratoire : DAVID

Résumé :
Cette thèse se focalise sur les jeux de potentiel et une généralisation d'un jeu d'ordonnancement dans un graphe que nous avons appelé jeu de placement. Dans ce jeu, le coût d'un joueur est impacté par son voisinage. Nous pouvons illustrer cela avec un exemple : le placement de joueurs dans un train, pour lesquels la présence de voisins directs influe sur le bien-être. Les résultats de cette thèse se divisent en deux parties. Tout d'abord, nous étudions ces jeux en considérant l'existence et les propriétés de structure des équilibres. Nous nous posons la question fondamentale de savoir s'il existe des équilibres de Nash dans le jeu de placement. Si tel est le cas, nous tachons de déterminer si ces équilibres sont facilement calculables. Dans le cas où il n'existe pas d'équilibre nous prouvons la NP-complétude du problème. Dans un second temps nous nous intéressons à la notion de calcul distribué d'équilibre de Nash dans des jeux de placement. En particulier nous considérons un jeu basé sur le problème de Max-Cut, qui a été plus étudié en théorie des graphes. Cela nous a permis d'étendre nos travaux à une application aux réseaux mobiles pour la gestion d'interférences dans les réseaux sans fils. Nous avons pu, pour les différents jeux, mettre en place des algorithmes distribués de calcul d'équilibres et étudier leur convergence. Parallèlement, nous avons étendu les travaux de Max-Cut à un problème de sélection d'offre de qualité de service parmi divers fournisseurs d'accès. Nous comparons les performances d'algorithmes de calcul distribué d'équilibres et de minimisation de regret.

Abstract :
This thesis focuses on potential games and a generalized load balancing game in a graph we called placement game. In this game, the cost of a player is affected by its neighbors. We can illustrate this with an example: the placement of players on a train, where the presence of direct neighbors affects their well-being. The results of this thesis are divided into two parts. First, we study these games considering the existence and structural properties of equilibria. We ask ourselves the fundamental question of whether there are Nash equilibria in the placement game. If this is the case we aim to determine if they are easily calculable, if there is no such equilibria we prove the NP-completeness of the problem. Secondly we focus on the concept of distributed algorithms to compute Nash equilibria in placement games. In particular we consider a game based on the Max-Cut problem, which has been more frequently studied. This allowed us to expand our work to a mobile network application for managing interference in wireless networks. We were able, for those different games, to implement distributed algorithms to compute equilibria and study their convergence. Meanwhile, we have expanded the Max-Cut works with a selection of QoS offers problem from various network providers. We compare the performance of distributed algorithms and regret minimization.
Informations complémentaires
Evripidis BAMPIS, Professeur des Universités, à l’Université Pierre et Marie Curie/Laboratoire d’Informatique de Paris 6 - UMR 7606 CNRS - Paris - Rapporteur
Jérôme MONNOT, Directeur de Recherche CNRS, à l’Université Paris Dauphine/Laboratoire d’Analyse et Modélisation de Systèmes pour l’Aide à la DEcision - UMR 7243 - Paris - Rapporteur
Johanne COHEN, Chargée de recherche, Habilitée à Diriger des Recherches, à l’Université de Paris-Sud 11 - Laboratoire de Recherche en Informatique (LRI) - UMR 8623 - Orsay - Directrice de thèse
David AUGER, Maître de Conférences, à l’Université Versailles Saint-Quentin-en-Yvelines/Laboratoire Données et Algorithmes pour un Ville Intelligente et Durable (DAVID) - Versailles - Co-Encadrant de thèse
Jean-Michel FOURNEAU, Professeur des Universités, à l’Université Versailles Saint-Quentin-en-Yvelines/Laboratoire Données et Algorithmes pour un Ville Intelligente et Durable (DAVID) - Versailles - Examinateur
Mohamed Lamine LAMALI, Ingénieur de Recherche, à NOKIA Bell Labs - Nozay - Examinateur
Sébastien TIXEUIL, Professeur des Universités, à l’Université Pierre et Marie Curie/Laboratoire d’Informatique de Paris 6 (LIP 6) - UMR 7606 CNRS Paris - Examinateur
Contact :
DREDVal Service FED :