Algorithmic game theory applied to networks and populations
Théorie algorithmique des jeux appliquée aux réseaux et aux populations
par Simon COLLET sous la direction de Pierre FRAIGNIAUD et de Amos KORMAN
Thèse de doctorat en Informatique
ED 386 Sciences Mathematiques de Paris Centre

Soutenue le lundi 09 décembre 2019 à Université Paris Cité

Sujets
  • Algorithmes évolutionnaires
  • Complexité de calcul (informatique)
  • Equilibre de Nash
  • Modèles mathématiques
  • Population
  • Réseaux d'ordinateurs
  • Théorie des jeux

Les thèses de doctorat soutenues à Université Paris Cité sont déposées au format électronique

Consultation de la thèse sur d’autres sites :

TEL (Version intégrale de la thèse (pdf))

Description en anglais
Description en français
Mots clés
Stratégie évolutivement stable (SES), Jeux en réseau
Resumé
Cette thèse se propose d'étudier sous l'angle de la théorie algorithmique des jeux divers jeux inspirés de situations réelles rencontrées dans les domaines des réseaux informatiques et de la biologie. Ces jeux se caractérisent par un grand nombre de joueurs disposant chacun d'une information incomplète à propos des autres joueurs. Dans la théorie classique, ces jeux rentrent dans la catégorie des jeux extensifs à information imparfaite et sont modélisés à l'aide d'arbres. Ils restent toutefois très difficiles à analyser en détail, à cause de leur inhérente complexité, liée notamment à une profondeur d'arbre potentiellement infinie. Nous avons relevé le défi de cette tâche en diversifiant les méthodes de résolution et en mettant l'accent sur son aspect interdisciplinaire.Cette thèse, outre l'introduction et la conclusion, se divise en trois parties. Dans la première, nous adoptons le point de vue de la théorie des jeux classique. Nous proposons un modèle de jeu qui correspond à une large classe de problèmes rencontrés dans la théorie du calcul distribué. Les principales contributions de cette partie sont, d'une part, de montrer comment passer d'un point de vue purement algorithmique du problème à un point de vue correspondant à la théorie des jeux, et, d'autre part, de prouver l'existence d'équilibres satisfaisants pour la classe de jeux obtenue. Ce deuxième point est essentiel et garantit que la théorie des jeux est adaptée à l'étude de tels jeux distribués, malgré leur complexité.La seconde partie est consacrée à l'étude d'un jeu omniprésent au sein des systèmes biologiques que l'on nomme jeu de la dispersion. Il modélise la situation dans laquelle un groupe d'animaux doit se partager une certaine quantité de ressources répartie entre différents sites géographiques. La difficulté du jeu provient du fait que certains sites contiennent plus de ressources que d'autres, mais risquent également d'attirer plus de joueurs. Le partage est alors difficile. Nous proposons une règle de répartition des ressources qui permet de maximiser les ressources exploitées par l'ensemble du groupe. Cette partie est aussi l'occasion de revisiter les liens étroits entre le concept de distribution libre idéale, très présente dans la théorie du fourrageage, et le concept de stratégie évolutionnairement stable, concept clé de la théorie des jeux évolutionnaires.La troisième partie se concentre sur l'étude du comportement d'une certaine espèce de petites chauve-souris vivant au Mexique, dans le désert de Sonora, et se nourrissant la nuit du nectar des cactus géant de l'espèce protégée Saguaro. Après la présentation des résultats expérimentaux obtenus sur le terrain, nous proposons une simulation informatique de leur comportement. Les résultats de ces simulations permettent de formuler des hypothèses intéressantes à propos du fonctionnement cérébral de ces petits mammifères. Nous étudions ensuite un modèle théorique de jeu inspiré de cette situation réelle. L'étude de ce modèle abstrait nous permet de distinguer les caractéristiques fondamentales du jeu, et de renforcer notre approche de théorisation du comportement de fourrageage. Cette étude ouvre également la voie à l'application de ce type de modèle à d'autres situations, impliquant un comportement animal ou humain.