Mardi 16 février 2010 à 14h dans la salle A006, Octave Boussaton soutiendra sa thèse intitulée :

Résumé :
Il existe de nombreuses méthodes d'optimisation du routage réseau en général.
Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation au sens de Nash, des flux réseau.
Nous rappelons tout d'abord le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présenterons un jeu de tarification simple a deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présenterons  un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présenterons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibre du système.