Search

We consider an optimization problem in which a (single) bat aims to exploit the nectar in a set of $n$ cacti with the objective of maximizing the expected total amount of nectar it drinks. Each cactus $i \in [n]$ is characterized by a parameter $r_{i} > 0$ that determines the rate in which nectar accumulates in $i$. In every round, the bat can visit one cactus and drink all the nectar accumulated there since its previous visit. Furthermore, competition with other bats, that may also visit some cacti and drink their nectar, is modeled by means of a stochastic process in which cactus $i$ is emptied in each round (independently) with probability $0 < s_i < 1$. Our attention is restricted to purely-stochastic strategies that are characterized by a probability vector $(p_1, \ldots, p_n)$ determining the probability $p_i$ that the bat visits cactus $i$ in each round. We prove that for every $\epsilon > 0$, there exists a purely-stochastic strategy that approximates the optimal purely-stochastic strategy to within a multiplicative factor of $1 + \epsilon$, while exploiting only a small core of cacti. Specifically, we show that it suffices to include at most $\frac{2 (1 - \sigma)}{\epsilon \cdot \sigma}$ cacti in the core, where $\sigma = \min_{i \in [n]} s_{i}$. We also show that this upper bound on core size is asymptotically optimal as a core of a significantly smaller size cannot provide a $(1 + \epsilon)$-approximation of the optimal purely-stochastic strategy. This means that when the competition is more intense (i.e., $\sigma$ is larger), a strategy based on exploiting smaller cores will be favorable.

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.; 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.

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., 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.

Distributed tasks such as constructing a maximal independent set (MIS) in a network, or properly coloring the nodes or the edges of a network with reasonably few colors, are known to admit efficient distributed randomized algorithms. Those algorithms essentially proceed according to some simple generic rules, by letting each node choosing a temptative value at random, and checking whether this choice is consistent with the choices of the nodes in its vicinity. If this is the case, then the node outputs the chosen value, else it repeats the same process. Although such algorithms are, with high probability, running in a polylogarithmic number of rounds, they are not robust against actions performed by rational but selfish nodes. Indeed, such nodes may prefer specific individual outputs over others, e.g., because the formers suit better with some individual constraints. For instance, a node may prefer not being placed in a MIS as it is not willing to serve as a relay node. Similarly, a node may prefer not being assigned some radio frequencies (i.e., colors) as these frequencies would interfere with other devices running at that node. In this paper, we show that the probability distribution governing the choices of the output values in the generic algorithm can be tuned such that no nodes will rationally deviate from this distribution. More formally, and more generally, we prove that the large class of so-called LCL tasks, including MIS and coloring, admit simple "Luby's style" algorithms where the probability distribution governing the individual choices of the output values forms a Nash equilibrium. In fact, we establish the existence of a stronger form of equilibria, called symmetric trembling-hand perfect equilibria for those games., Leibniz International Proceedings in Informatics (LIPIcs), 125, ISSN:1868-8969, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), ISBN:978-3-95977-098-9

In the classical framework of local distributed network computing, it is generally assumed that the entities executing distributed algorithms are altruistic. However, in various scenarios, the value of the output produced by an entity may have a tremendous impact on its future. This is for instance the case of tasks such as computing maximal independent sets (MIS) in networks. Indeed, a node belonging to the MIS may be later asked more than to a node not in the MIS, e.g., because MIS in networks are often used as backbones to collect, transfer, and broadcast information, which is costly. In this paper, we revisit typical local distributed network computing tasks in the framework of algorithmic game theory. Specifically, we focus on the construction of solutions for locally checkable labeling (LCL) tasks, which form a large class of distributed tasks, including MIS, coloring, maximal matching, etc., and which have been studied for more than 20 years in distributed computing. Given an LCL task, the nodes are collectively aiming at computing a solution, but, at the individual level, every node plays rationally and selfishly with the objective of optimizing its own profit. Surprisingly, the classical frameworks for game theory are not fully appropriate for the purpose of our study. Moreover, we show that classical notions like Nash equilibria may yield algorithms requiring an arbitrarily large number of rounds to converge. Nevertheless, by extending and generalizing core results from game theory, we establish the existence of a so-called trembling-hand perfect equilibria, a subset of Nash equilibria that is well suited to LCL construction tasks. The main outcome of the paper is therefore that, for essentially all distributed tasks whose solutions are locally checkable, there exist construction algorithms which are robust to selfishness.