Skip to Main content Skip to Navigation
Theses

Algorithmic Game Theory Applied to Networks and Populations

Simon Collet 1, 2
2 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Résumé : 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.
Complete list of metadatas

Cited literature [101 references]  Display  Hide  Download

https://hal.inria.fr/tel-02433566
Contributor : Pierre Fraigniaud <>
Submitted on : Thursday, January 9, 2020 - 11:26:34 AM
Last modification on : Friday, April 10, 2020 - 5:29:25 PM
Document(s) archivé(s) le : Saturday, April 11, 2020 - 10:22:02 AM

File

Simon_Collet_PhD_thesis.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02433566, version 1

Collections

Citation

Simon Collet. Algorithmic Game Theory Applied to Networks and Populations. Data Structures and Algorithms [cs.DS]. Université Paris 7 - Diderot, 2019. English. ⟨tel-02433566⟩

Share

Metrics

Record views

58

Files downloads

182