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
Abstract : The aim of this thesis is to use algorithmic game theory tools to study various games inspired from real world problems in the fields of information networks and biology. These games are characterized by a large number of players, each with incomplete information about other players. In classical game theory, these games fall into the category of extensive games with imperfect information, which are modeled using trees. However, these games remain very difficult to analyze in details, because of their intrinsic complexity, which is linked with their possibly infinite tree depth. Nevertheless, we have taken up the challenge of this task, while diversifying the methods of resolution, and emphasizing its interdisciplinary aspect. Besides the introduction and the conclusion, the thesis is divided into three parts. In the first part, we adopt the point of view of classical game theory. We propose a game that corresponds to a wide class of problems encountered in the theory of distributed computing. The main contributions of this part are, on the one hand, to show how to transform a purely algorithmic problem into a game, and, on the other hand, to prove the existence of satisfactory equilibria for the resulting class of games. This second point is essential, as it guarantees that game theory is adapted to the study of distributed games, despite their complexity. The second part is dedicated to the study of a game omnipresent within biological systems, that we call dispersion game. This game models the situation in which a group of animals must share a certain amount of resources scattered among different geographical sites. The difficulty of the game comes from the fact that some sites contain more resources than others, but may also attract more players. We propose a rule for the distribution of resources which makes it possible to maximize the resources exploited by the whole group. This part of the thesis is also an opportunity to revisit the close links between the concept of ideal free distribution, very present in the theory of foraging, and the concept of evolutionarily stable strategy, a key concept of evolutionary game theory. The third part focuses on the study of the behavior of a specific species of small bats living in Mexico, in the Sonoran Desert, and feeding at night from the nectar of the giant Saguaro cacti, a protected species. After the presentation of the experimental results obtained in the field, we propose a computer simulation of their behavior. The results of these simulations make it possible to formulate interesting hypotheses about the cerebral activities of these small mammals. We then study a theoretical model of game inspired by this real situation. The study of this abstract model allows us to distinguish the fundamental characteristics of the game, and to reinforce our approach of theorizing foraging behavior. This study also opens the way to applying this type of model to other situations, involving animal or human behavior.
Complete list of metadata

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
Long-term archiving on: : 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

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

110

Files downloads

234