Prof. Tijani Prof Chahed

Hayel Yezekael

First of all, I would like to thank my supervisor Prof

Dedicated to my beloved nonna Gnagna,

who used to repeat to me that "A living donkey is better than a dead scientist", but who, if she was still here, would be deeply proud of me.

iii Résumé Mots clés: Théorie des Jeux Évolutionnaires, Processus de Décision Markovien, Systèmes Dynamiques, Contrôle et Optimisation La théorie des jeux évolutionnaires (EGT) constitue un cadre simple pour étudier le comportement de populations larges dont les membres sont engagés en interactions stratégiques. L'origine de l'EGT est due à Maynard [START_REF] Smith | Game theory and the evolution of fighting[END_REF], qui utilise les concepts de base de la Théorie des Jeux (GT) classique pour étudier l'évolution des espèces en biologie. Tandis que la GT considère des agents rationnels qui choisissent leurs actions pour maximiser leur propre utilité, dans l'EGT, au départ, les joueurs sont censés être les membres d'une espèce, pour lesquels l'hypothèse de rationalité ne peut pas être considérée. Les actions sont interprétées comme des traits héréditaires et l'utilité correspond au fitness darwinien (ou succès reproductif). Après la diffusion de l'EGT en biologie, les économistes comprennent que l'approche évolutionnaire peut être très utile pour l' étude des équilibres de la GT et que ses modèles peuvent représenter des problèmes dans autres contextes que la biologie. De plus, les modèles évolutionnaires ont l'avantage de ne pas nécessiter d' hypothèse de rationalité, étant un concept très difficile à définir et caractériser [START_REF] Weibull | What have we learned from evolutionary games so far? Working paper 487[END_REF]. Déjà Nash, dans sa thèse, avait suggéré que son concept d'équilibre (l'équilibre de Nash) peut avoir deux interprétations, une rationaliste et une autre qu'il appelle «action de masse» [START_REF] Nash | Non-cooperative Games[END_REF]. L'EGT est désormais considérée comme un enrichissement important de la GT et s'applique à un vaste éventail de problèmes dans des contextes différents, comme l'économie, l'informatique, les télécommunications, les sciences sociales. En étant une théorie assez récente, des nombreuses applications restent encore à identifier, ainsi que plusieurs aspects théoriques à approfondir. iv Dans les jeux évolutionnaires standards, les individus d'une grande population sont sélectionnés aléatoirement de façon répétitive pour jouer un jeu symétrique entre deux joueurs. Le fitness d'un joueur est défini comme une fonction de son action ainsi que de la distribution des actions au sein de la population. Les actions donnant un fitness plus élevé, se diffusent dans la population. Le concept d'équilibre est la stratégie évolutionairement stable (SES ou ESS), introduite par Maynard [START_REF] Smith | The logic of animal conflict[END_REF]. Il s'agit d'une stratégie telle que, si elle est adoptée par l'ensemble de la population, ne peut être envahie par une stratégie différente, et est donc stable par rapport à la déviation d'une (petite) fraction de la population à une stratégie différente (mutante). D'un point de vue biologique, l'ESS peut être vue comme une généralisation du concept darwinien de «survie du plus apte», alors que d'un point de vue des jeux, il s'agit d'un raffinement conceptuel de l'équilibre de Nash.

Tandis que l'ESS est un concept statique qui vise à expliquer les processus de mutation, Taylor et Jonker [START_REF] Taylor | Evolutionarily stable strategies and game dynamics[END_REF] définissent des dynamiques qui permettent de comprendre comment une population atteint une situation stable, la dynamique du réplicateur, en mettant l'accent sur le processus de sélection. Ils formalisent ces dynamiques à travers un système d'équations différentielles et montrent le lien entre les points stationnaires de ce système et les équilibres du jeu. Dans les jeux évolutionnaires standards le joueur est l'individu qui choisit ses actions pour maximiser son propre fitness. Dans cette thèse nous proposons une nouvelle approche pour la modélisation de l' évolution, où le joueur est formé par un ensemble d'individus. Nous considérons toujours des interactions entre individus mais nous supposons qu'ils maximisent le fitness du group auquel ils appartiennent.

Une direction importante pour le développement de l' EGT est celle des jeux stochastiques. La notion de hasard est implicite dans la notion d' ESS, en étant une stratégie stable face à des mutations aléatoires. Même la dynamique du réplicateur peut être vue comme l'approximation déterministe d'un processus stochastique, oú le hasard disparaît quand la population est suffisamment large. Dans la deuxième partie de ce manuscrit, nous introduisons une classe particulière de jeux évolutionnaires stochastiques, les Jeux Evolutionnaires Markoviens (MDEG), défini par [START_REF] Altman | Markov decision evolutionary games[END_REF]. Dans ce contexte, chaque joueur est associé à un état individuel qui évolue dans le temps selon un Processus de Décision Markovien (MDP).

I Deterministic Evolutionary Games and Group of Players

Introduction "The word "model" sounds more scientific than "fable" or "fairy tale" although I do not see much difference between them. [. . . ] The author of a fable draws a parallel to a situation in real life. He has some moral he wishes to impart to the reader. The fable is an imaginary situation that is somewhere between fantasy and reality. Any fable can be dismissed as being unrealistic or simplistic, but this is also the fable's advantage. Being something between fantasy and reality, a fable is free of extraneous details and annoying diversions. In this unencumbered state, we can clearly discern what cannot always be seen in the real world. On our return to reality, we are in possession of some sound advice or a relevant argument that can be used in the real world. We do exactly the same thing in economic theory."

Ariel Rubinstein, Dilemmas of an Economic Theorist, 2006 Evolutionary Game Theory (EGT) constitutes a simple framework to study the behavior of large populations whose individuals are repeatedly engaged in pairwise strategic interactions. The birth of EGT is marked by the pioneering work of Maynard Smith [START_REF] Smith | Game theory and the evolution of fighting[END_REF], who uses classical Game Theory (GT) as a tool to explain and to predict quantitative and qualitative aspects of biological evolution of species. While GT considers rational agents choosing their actions in order to maximize their utility function, originally in EGT the players are supposed to be the members of an animal species, for which rationality can't be assumed. Actions are interpreted as inheritable traits and the utility corresponds to the Darwinian fitness (or reproductive success).

After the spread of EGT in biology, economists understand that the evolutionary apxii proach is useful to investigate the foundations of game theoretic solution concept [START_REF] Friedman | Evolutionary games in economics[END_REF] and it can be adopted in social science contexts, to predict human behavior with no need of rationality assumption, which may be complex to define and to interpret [START_REF] Weibull | What have we learned from evolutionary games so far? Working paper 487[END_REF]. It's worth to mention that in his thesis, Nash already notes that his solution concept (the Nash equilibrium) could have two interpretations, one rationalistic and one that he called the "mass action interpretation": "We shall now take the "mass-action" interpretation of equilibrium points. In this interpretation solutions have no great significance. It is unnecessary to assume that the participants have full knowledge of the total structure of the game, or the ability and inclination to go through any complex reasoning processes. But the participants are supposed to cumulate empirical information on the relative advantages of the various pure strategies at their disposal." [START_REF] Nash | Non-cooperative Games[END_REF].

EGT is nowadays considered as an important enrichment of GT and it's applied in a wide variety of fields, spanning from economics to computer science. Evolutionary models allow, for example, to explain and predict different aspects of human behavior, as the evolution of language [START_REF] Nowak | The evolutionary language game[END_REF], the spread of culture [START_REF] Enquist | Evolution of social learning does not explain the origin of human cumulative culture[END_REF] and moral behavior [START_REF] Harmsand | Evolution of Moral Norms[END_REF], as well as to study telecommunication networks dynamic problems, as the evolution of Internet Transport Protocols [START_REF] Altman | The evolution of transport protocols: An evolutionary game perspective[END_REF], the formation of wireless networks [START_REF] Shakkottai | The case for non-cooperative multihoming of users to access points in ieee 802.11 wlans[END_REF], [START_REF] Altman | Evolutionary power control games in wireless networks[END_REF], (Altman and Hayel, 2008) [START_REF] Bonneau | An evolutionary game perspective to ALOHA with power control[END_REF] and congestion control problems [START_REF] Menasche | An evolutionary gametheoretic approach to congestion control[END_REF], [START_REF] Zheng | Evolutionary game theoretic model and end-to-end flow control in the internet[END_REF], (Zheng and Feng, 2001a). Being a relatively young mathematical theory, there still remain many

possible applications yet to be identified, and many interesting theoretical issues to be addressed or deeper explored.

In standard evolutionary games, individuals in a large population are repeatedly and randomly selected to play a symmetric two-person game. The fitness is defined as a function of both the behavior of the individual as well as of the distribution of behaviors among the whole population. Actions with higher fitness are supposed to spread within the population. The main solution concept, first introduced by Maynard Smith and Price (Maynard [START_REF] Smith | The logic of animal conflict[END_REF], is the Evolutionarily Stable Strategy (ESS), which is such that, if a population adopt it, it is uninvadable by any other strategy, which means that it is robust against deviations of a (possibly small) fraction of the population to a different strategy (mutations). From a biological point of view it can be seen as a generalization of Darwin's idea of survival of the fittest, while from a game theoretical perspective it constitutes a refinement of the Nash Equilibrium. Maynard Smith equilibrium concept has been enriched with an explicit dynamic foundation by Taylor and Jonker [START_REF] Taylor | Evolutionarily stable strategies and game dynamics[END_REF]. In order to explain how a population reaches a stable situation, they introduce the replicator dynamics, which highlights the role of sexiii lection. It is formalized by a system of ordinary differential equations and it establishes that an action spreads if its fitness is larger than the averaged fitness in the population.

While in standard EGT, the interacting individual is the player, choosing the actions to play in order to maximize its own fitness, in the first part of this dissertation we propose a new approach to model evolution, where the player is supposed to be a whole group. We still consider pairwise interactions among individuals but we assume that they maximize the fitness of the group they belong to, which is thus the actual player of the game.

An interesting direction for future developments of EGT is towards stochastic games.

The notion of randomness is somehow implicitly carried in the concept of evolutionary stability, as the mutations in the population are random events. The replicator equation can also be derived as the deterministic approximation of a stochastic process, where all randomness is averaged away when the population size is sufficiently large. Sandholm [START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF] defines the notion of revision protocol, which specifies the general rule followed by players updating their actions in time, generating a continuous time Markov process over the finite set of actions' distributions (states of the system). He rigorously proves that, when the population is sufficiently large, the stochastic process converges in a finite-horizon to the deterministic mean dynamics, defined as the expected motion. We present, in the second part of the manuscript, a particular class of stochastic evolutionary games, that of Markov Decision Evolutionary Games (MDEG), introduced by Altman and Hayel [START_REF] Altman | Markov decision evolutionary games[END_REF]. In this framework, each player is associated with an individual state which evolves in time according to a Markov Decision Process (MDP). During his finite life time a player repeatedly meets other users in random pairwise interactions and it may move among different states; the actions played by an individual determines his immediate fitness and the transition probabilities to the next state. Restricting (without loss of generality) to stationary policies, Altman and Hayel prove that, if the distribution over the individual states is assumed to be stationary with respect to the currently used policy, it is possible to transform the MDEG into a standard evolutionary game and to compute its ESSs. Motivated by the importance of understanding the dynamics leading to a stable situation, we present in this dissertation, our new dynamical approach to MDEG. In contrast with the static approach adopted by Altman and Hayel, we study here the local dynamics of individual states and the dynamics intrinsically related to the distribution of policies in the population, describing them by interdependent differential equations.

In the third part of the manuscript we pursue the study of stochastic dynamics in a different context, that of control theory. We define a hybrid stochastic dynamical system jointly controlled by two players involved in a non-zero sum game and we prove that xiv the problem can be approximated by an averaged deterministic differential game.

The manuscript is organized as follows.

Part I: Deterministic Evolutionary Games and Groups of Players

In Part I, we first briefly introduce Evolutionary Game Theory (EGT), pointing out the main notions that will be used and developed in this work. After a hint of the history of EGT, we provide the main equivalent definitions of the ESS. We then illustrate the dynamic aspect of EGT through the replicator dynamics and the relation between the rest points of the replicator equation and the equilibria of the game. We then describe one of the most studied examples in evolutionary games, that of the Hawk-Dove.

In Chapter 2 we present our new approach to evolutionary games, in which the concept of the player as a single individual is replaced by that of a player as a whole group.

Even if we still consider pairwise interactions among individuals, we suppose that individuals maximize the fitness of the group they belong to. In order to provide simple but meaningful results, we analyze the Hawk-Dove game in this framework, considering the case of an infinite and that of a finite population of individuals. We obtain, in both cases, a concave game. This allows us to prove the existence and the uniqueness of a symmetric Nash equilibrium through Rosen's results [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]. We explicitly compute the equilibria as a function of the number of groups. We then define a gradient based dynamics as a counterpart of the replicator equation. We obtain that the fact of teaming together makes individuals less aggressive at equilibrium. We deepen the study of group-players in Chapter 3, where we consider groups with different relative sizes and we introduce a new concept of equilibrium, the Group Fitness Evolutionarily Stable Strategy (GFESS). The stability required by the GFESS is related to a notion of deviation within a group, and thus of a fraction of the player (instead of a fraction of the whole population). We first define the GFESS in a general case and we then characterize it for two-actions games. We illustrate our results through three classical examples, the Hawk-Dove game, the Stag Hunt game and the Prisoner's Dilemma. We then generalize the definition of group fitness in order to study an application in multiple access control in slotted Aloha.

Part II: Individual State and policy Dynamics in Markov Decision Evolutionary Games

We begin the second part of the dissertation presenting MDEG as defined by Altman and Hayel [START_REF] Altman | Markov decision evolutionary games[END_REF], combining MDP and EGT. In Chapter 5 we present our new dynamical approach to MDEG, in which players are associated with xv an individual state evolving according to a continuous time MDP. We first introduce the concept of interdependent dynamics of states and policies in a general case, and we then define the State Policy coupled Dynamics (SPcD) system in a particularly simple scenario, with two states and two actions. We establish the relation between the equilibria of the defined system and the equilibria of the game, and we then find the closedform solutions of the system. The system is solved by assuming that the processes of states and policies move with different velocities, which allows us to apply two different approximation techniques: the singular perturbation method, and a matrix approximation technique. In Chapter 6 we define a dynamic model for the Hawk-Dove game in a MDEG type of framework, in order to study the impact of the aggressive behavior of adults on the evolution of young individuals. As in MDEG models, players are associated with a MDP, but transitions probabilities here do not depend on the player's action but on the action of its opponent. By considering the stationary distribution over the states, we transform the game into an equivalent standard evolutionary game, and we compute the equilibria. We then combine the notion of group-players presented in Chapter 2 and MDEG, studying the dynamic Hawk-Dove game for the case of group players.

Part III: Stochastic Hybrid Dynamics

In the last part of the manuscript, we extend the theory of control for an hybrid stochastic dynamical system to the case of two players non-zero sum games. The system evolves in continuous time and it is subjected to abrupt changes of the parameters, determined by two (discrete time) Markov decision processes, each of which is controlled by a player that aims at minimizing its objective function. As we did in Chapter 5, we assume a two time scales behavior of the system: the lengths of the time intervals between the "jumps" of the parameters are assumed to be small, which means that parameters evolve faster than the state of the system. This allows us to approximate the hybrid game with a deterministic averaged dynamic game. We prove that an asymptotic Nash equilibrium of such hybrid game can be constructed on the basis of a Nash equilibrium of a deterministic averaged dynamic game. We conclude the dissertation with a last chapter resuming our main contributions and providing the possible future developments of our work.

"Maybe needless to say, the discussion is limited by idiosyncratic limitations to my memory, knowledge and understanding. I apologize for omissions and misrepresentations.", [START_REF] Weibull | What have we learned from evolutionary games so far? Working paper 487[END_REF].

xvi

Notations

Lowercase letters are mostly used for real numbers, vectors of real numbers and functions, while capital letters indicate matrices and sets. Bold lowercase letters are usually used for vectors, non-bold one for real numbers. We will use the term "action" and "policy", avoiding the term "strategy" which may be misleading. In fact, in evolutionary game theory literature it is often used to refer to actions (pure or mixed), while in Stochastic Games the same term refers to policy. A: set of pure actions, with |A| = M;

∆(A) = {p ∈ R K | M ∑ i=1 p i = 1}: set of

Deterministic Evolutionary Games and Group of Players

Chapter 1

An Introduction to Evolutionary Game Theory "The relation between species, or among the whole assemblage of an ecology, may be immensely complex; and at Dr. Cavalli's invitation I propose to suggest that one way of making this intricate system intelligible to the human mind is by the analogy of games of skill, or to speak somewhat more pretentiously, of the Theory of Games." R. Fisher, Polimorphism and Natural Selection, 1958

Summary

This chapter gives a brief introduction to evolutionary game theory, pointing out the main notions that will be used and developed in this work. After a hint of the history of EGT, we provide the main equivalent definitions of the equilibrium concept, the ESS. We then study the dynamic aspect of EGT through the replicator dynamics and we establish the relation between the rest points of the replicator equation and the equilibria of the game. We conclude the chapter presenting one of the most studied examples in evolutionary games, that of the Hawk-Dove.

Origins of Evolutionary Game Theory and its Developments

Evolutionary Game Theory (EGT) has originally developed to formally describe and predict quantitative and qualitative aspects of biological evolution by using the mathematical theory of games.

Before the birth of Game Theory (GT), Fisher [START_REF] Fisher | The Genetic Theory of Natural Selection[END_REF] analyzes the dynamics of the sex ratio in a species as a competition between individuals. In order to explain the stable sex ratio observed in most of mammal species, he supposes that each individual maximizes its own fitness, defined as the expected number of grandchildren, depending on the relative frequency of males and females in the population. Even if the formalism he adopts is not the same, Fisher's approach is conceptually very close to game theory.

The first explicit attempt to apply GT formalism in evolutionary biology is by Lewontin [START_REF] Lewontin | Evolution and the theory of games[END_REF], who describes the evolution of the genetic mechanism as a game played between nature and a species, where the latter seek actions that minimize the probability of extinction. The equilibrium is represented by a maxmin action, the species doing the best against the worst of the nature; similar ideas have been developed a few years later by [START_REF] Slobodkin | An optimal strategy of evolution[END_REF].

Hamilton [START_REF] Hamilton | Extraordinary sex ratio[END_REF] While Maynard Smith's notion of ESS captures the mutation mechanism through a static definition, Taylor and Jonker [START_REF] Taylor | Evolutionarily stable strategies and game dynamics[END_REF] focus on the selection mechanism and model the dynamic process by which the distribution of actions in a population evolves to a stable situation as a system of ordinary equations; Schuster and Sigmund [START_REF] Schuster | Replicator dynamics[END_REF]) call this model the replicator dynamics.

Since the late 1980s, there is a growing interest in EGT by economists, who see the value of the evolutionary approach to game theory in contexts other than biology, both as a method of providing foundations for the equilibrium concepts of traditional game theory, and as a tool for selecting among equilibria. Furthermore the evolutionary approach do not need the rationality assumption required by standard games. EGT mod-els start to be applied to study the behavior of populations of active decision makers [START_REF] Friedman | Evolutionary games in economics[END_REF], [START_REF] Mailath | Introduction: Symposium on Evolutionary Game Theory[END_REF], [START_REF] Nachbar | Evolutionary' selection dynamics in games: Convergence and limit properties[END_REF], [START_REF] Selten | Evolution, learning, and economic behavior[END_REF]. Even if the majority of work in EGT has been undertaken by biologists and economists, closely related models have been applied in a wide range of disciplines, including sociology [START_REF] Zhang | A dynamic model of residential segregation[END_REF], [START_REF] Bisin | The economics of cultural transmission and the dynamics of preferences[END_REF], [START_REF] Kuran | Cultural integration and its discontents[END_REF], [START_REF] Sandholm | Negative externalities and evolutionary implementation[END_REF], computer science [START_REF] Shakkottai | The case for non-cooperative multihoming of users to access points in ieee 802.11 wlans[END_REF], (Zheng and Feng, 2001a), [START_REF] Sandholm | Potential games with continuous player sets[END_REF], [START_REF] Sandholm | Negative externalities and evolutionary implementation[END_REF], and transportation science [START_REF] Sandholm | Potential games with continuous player sets[END_REF].

A Static Approach to EGT

Normal Form Games

We briefly introduce here two players normal form symmetric games, which will be considered to model pairwise interactions involved in EGT models. Suppose that each of the two players disposes of a finite set of pure actions, A, with

|A| = M. Let ∆(A) = {p ∈ R M + | ∑ i∈A p i = 1}
be the set of mixed actions, that are probability measures over the action space. Note that a pure action i ∈ A can be represented through the unit vector e i = (0, . . . , 0, 1, 0, . . . , 0) ∈ ∆(A) with all elements equals to zero except for the element in position i, which equals 1. The payoff can be described by a matrix

A = (a ij ) ∈ R M × R M
, where the entry a ij corresponds to the payoff that a player gets using pure action i ∈ A in an interaction with a player using j ∈ A. If mixed actions are considered, the expected payoff of an individual playing p against an opponent using q, with p, q ∈ ∆(A), is given by:

p T Aq = ∑ i∈A ∑ j∈A p i a ij q j (1.1)
An action q * ∈ ∆(A) is a (symmetric) Nash equilibrium of the two players-symmetric normal form game if:

q * T Aq * ≥ p T Aq * ∀p ∈ ∆(A). (1.2)
If (1.2) holds with strict inequality, q * is a strict Nash equilibrium.

Evolutionarily Stable Strategy (ESS)

Consider a large population of players, where individuals are repeatedly matched at random in a two-players normal form game, as described in the previous section. Maynard Smith's ESS is defined as an action that, if adopted by the whole population, is robust against invasions by a small group of individuals playing a different (mutant) action. Suppose that the whole population is programmed to play an (incumbent) action q ∈ ∆(A) , and that a fraction ǫ of mutants deviate to an action p ∈ ∆(A). Definition 1. The mixed action q is an ESS if ∀p = q, there exists some ǫ p > 0 such that:

∀ǫ ∈ (0, ǫ p ) q T A(ǫp + (1 -ǫ)q) > p T A(ǫp + (1 -ǫ)q). (1.3)
Equation 1.3 requires that, if the size of the invading group is sufficiently small, the incumbent's expected payoff from a random match in the post-entry population exceeds that of any mutant.

The stable population is said to be monomorphic if all individuals are assumed to adopt the same action, polymorphic if it individuals are allowed to take different actions (Maynard [START_REF] Smith | Evolution and the theory of Games[END_REF].

It can be easily proved (see e.g. [START_REF] Weibull | Evolutionary Game Theory[END_REF]) that the following conditions are equivalent to Definition 1. Proposition 1. q ∈ ∆(A) is an ESS if and only if it satisfy:

• Nash Condition:

q T Aq ≥ pAq ∀p ∈ ∆(A), (1.4)
• Stability Condition:

q T Aq = pAq ⇒ qAp ≥ pAp ∀p ∈ ∆(A), p = q.
(1.5)

The inequality 1.4 corresponds to the definition of the Nash equilibrium, while the second condition requires that, if the mutant action p is an alternative best reply to the incumbent action q, then the payoff of the incumbent action against the mutant one is higher then the one of the mutant action against itself. This definition can be interpreted from a biologic perspective: q is an ESS if an arbitrary rare mutant p does no better than q in its most frequent contests against q. If it does as well in these, then it does worse than q in its rare contests against another mutant. It immediately follows from (1.4) that a symmetric strict Nash equilibrium is an ESS (while the converse is not true).

Another equivalent definition of the ESS which is often used, is due to Hofbauer and Sigmund. Theorem 1. [Theorem 6.4.1 (Hofbauer and Sigmund, 1998)] The action q ∈ ∆(A) is an ESS if and only if q T Ap > p T Ap for all p = q in some neighbourhood of q in ∆(A).

Other equivalent definitions of ESS can be found in the literature. The evolutionary stability can be characterized, for example, by introducing the concept of invasion barrier, which is useful in the case of a finite population [START_REF] Weibull | Evolutionary Game Theory[END_REF]. An important distinction to be made is that among ESS and evolutionarily stable state (see the next subsection for the definition of the latter): an analysis of the relation between these two notions can be found in [START_REF] Thomas | Evolutionary stability: States and strategies[END_REF]. Some weakening criteria for evolutionary stability are the concept of neutral stability [START_REF] Weibull | Evolutionary Game Theory[END_REF] and that of local stability [START_REF] Pohley | Non-linear ESS-models and frequency dependent selection[END_REF], while an important refinement of the ESS is the regular ESS [START_REF] Taylor | Evolutionarily stable strategies and game dynamics[END_REF]. Maynard [START_REF] Smith | The logic of asymmetric contests[END_REF] extend the study of the ESS to the case of asymmetric games and Selten [START_REF] Selten | A note on evolutionarily stable strategies in asymmetric animal conflicts[END_REF] proves that, for these games, no mixed action can be evolutionarily stable. Taylor [START_REF] Taylor | Evolutionarily stable strategies with two types of player[END_REF] and

Cressman [START_REF] Cressman | The Stability Concept of Evolutionary Game Theory. A Dynamic Approach[END_REF] study the evolutionary stability in the case of two types of players (see Chapter 2). In Chapter 3 we briefly present the different existing definitions of N-species ESS, first introduced by Garay and Varga [START_REF] Garay | Strict ESS for n-species systems[END_REF], and we define our new notion of Group Fitness Evolutionary Stable Strategy. Cressman [START_REF] Cressman | The Stability Concept of Evolutionary Game Theory. A Dynamic Approach[END_REF] devotes a text to the development of static ESS conditions in diverse theoretical models of evolutionary biology, providing a wide overview of the different definitions of the evolutionary stability notion. Evolutionary stability can also be defined adopting a dynamical point of view: see e.g. [START_REF] Hofbauer | Evolutionary game dynamics[END_REF],

where the authors state a necessary and sufficient condition for an action to be evolutionarily stable, which is related to the replicator equation. Also Pholey and Thomas' local stability has been defined in order to find a static concept in better agreement with the dynamical aspects of the process of natural selection. Cressman et al. [START_REF] Cressman | Evolutionary stability concepts for n-species frequency-dependent interactions[END_REF] focused on a dynamical approach to the ESS in the case of N species. An application driven approach leads to a setwise generalization of the ESS, the Evolutionarily Stable Set (ES): see [START_REF] Thomas | On evolutionarily stable set[END_REF], [START_REF] Cressman | The Stability Concept of Evolutionary Game Theory. A Dynamic Approach[END_REF], [START_REF] Weibull | Evolutionary Game Theory[END_REF].

Population Games and Evolutionarily Stable State

Population games study strategic interactions within a large polymorphic populations of individuals playing pure actions [START_REF] Sandholm | Evolutionary Game Theory[END_REF]. In this scenario, the notion of evolutionary stability is associated with the state of the population instead that to a mixed action (see e.g. [START_REF] Taylor | Evolutionarily stable strategies and game dynamics[END_REF], [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF] and [START_REF] Sandholm | Evolutionary Game Theory[END_REF]). More precisely, a population state (also called profile), is defined by

a vector x = (x 1 , . . . , x M ), with M ∑ i=1
x i = 1, where x i is the proportion of individuals in the population playing pure action i ∈ A. Note that x ∈ ∆(A), so it is formally equivalent to a mixed action in ∆(A). A population game is identified by the continuous vector valued payoff function F : ∆(A) → R M , depending on the state of the population. Let F i (x) denote the payoff of pure action i in a population in state x. If mixed actions are considered, the payoff of mixed action q ∈ ∆(A), denoted by F(q, x), can be thought as the average fitness of a group of individuals such that a proportion q i of the group uses pure action i, against a population in state x, i.e:

F(q, x) = M ∑ i=1 q i F i (x).
Definition 2. A population state q is a (symmetric) Nash equilibrium profile if:

F(q, q) ≥ F(x, q), for all population states x ∈ ∆(A). Definition 3. A population state q is evolutionarily stable if:

F(q, x) > F(x, x),
for all x = q in a neighborhood of q. Remark 1. If the payoff function F is linear in the population state, then evolutionarily stable state and ESS coincide.

A Dynamic Approach to EGT

The notion of dynamics has been introduced into evolutionary games by Taylor and

Jonker [START_REF] Taylor | Evolutionarily stable strategies and game dynamics[END_REF], in order to provide a dynamic foundation of Maynard Smith's static concept of evolutionary stability. Through a system of differential equations, the authors describe the evolution of the distribution of actions within a pop-ulation, where the share of individuals playing a certain action is supposed to change according to the actions' success (represented by the fitness function). They then show the relation between the stable points of their dynamics and the ESSs of the game. The model has been named the replicator dynamics by Schuster and Sigmund [START_REF] Schuster | Replicator dynamics[END_REF].

The need for a dynamical approach to games is already felt at the earliest stages of classical game theory, when Neumann and Morgenstern, in the introduction of their treatise [START_REF] Neumann | Theory of Games and Economic Behaviour[END_REF], suggest the idea of completing their static solution concept with some notion of dynamics. The first dynamic models are due to Brown and Von Neumann, who defined the Brown-Von Neumann-Nash dynamics, as a tool for computing the equilibria in zero-sum games [START_REF] Brown | Solutions of Games by Differential Equations[END_REF]. In the last decades, a large number of dynamics has been introduced in GT framework: see e.g. gradient-based dynamics [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF], fictitious play [START_REF] Gilboa | Social stability and equilibrium[END_REF], projection dynamics, best response dynamics [START_REF] Fudenberg | Game theory[END_REF], Boltzman dynamics and logit dynamics [START_REF] Fudenberg | Theory of Learning in Games[END_REF].

When a dynamic approach is adopted, a player is supposed to occasionally reconsider its choice of action, adjusting its action in response to several information, like its own current payoff, the average current payoff, the historical actions of the others, etc. In [START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF], the author introduces, in population games framework, the notion of revision protocols, which specify the general rule followed by players updating their actions in time (see e.g. imitative protocol, natural selection protocol, evaluative protocol). A revision protocol generates a continuous time Markov process over the finite set of states of the system. For large populations of players and finite time games, this stochastic process can be approximated by its expected motion, given by the deterministic mean dynamics. Then, each revision protocol can be viewed as defining a map, called deterministic evolutionary dynamic, from population games to mean dynamics. On the basis of the revision protocols which induce them, it is possible to identify different families of deterministic evolutionary dynamics. Sandholm defines four main classes of deterministic dynamics for population games: imitation (which includes the replicator dynamics), excess payoff, pairwise comparison and perturbed pairwise comparison dynamics.

In the following subsection, we give the formal definition of the standard replicator dynamics in EGT. In Section 2.3.2 we use Rosen's gradient-based dynamics in our new framework of group-players evolutionary games. In Chapter 5 we study the replicator dynamics of policies coupled with the dynamics of individual states in a particular Markov decision evolutionary game (see Chapter 4 for an introduction to MDEG). In Chapter 7 we deal with a different kind of dynamical system, a hybrid stochastic system 1.3. A Dynamic Approach to EGT for a two players non-zero sum game.

Replicator Equation

While the ESS notion is related to the mutation mechanism in a population, the replicator dynamics focuses on the selection mechanism, that favors some behavioral phenotypes over others.Consider a large population of haploid individuals programmed to play the same action during their entire lifetime and suppose that offspring inherit the parent's action. In the standard setup for replicator dynamics, only pure actions are allowed and thus a vector q ∈ ∆(A) is interpreted as a population state and not as a mixed action. This means that q i represents the share of the population adopting pure action i (instead of representing the probability that an individual plays i); in our mathematical treatment, we do not distinguish between the two interpretations.

The replicator dynamics consists in a system of differential equations describing how the frequencies of pure actions evolve in time depending on their success. The evolution of q i , with i ∈ A, is expressed as:

qi (t) = q i (t)(F i (q(t)) -F(q(t))), (1.6)
where F i (q) denotes the immediate fitness of an individual playing pure action i in a population whose state is q and F(q) = M ∑ i=1 p i F i (q) is the average immediate fitness in the population (in state q). The growth rate qi (t)/q i (t) of the fraction of the population using action i is thus equal to the difference between the immediate fitness of that action and the current average fitness in the population.

In a two-action game, with A = {1, 2}, if p indicates the share of the population playing action 1, we have that F(q) = qF 1 (q) + (1 -q)F 2 (q), and thus, by substituting this into (1.6) we obtain: q(t) = q(t)(1 -q(t))(F 1 (q(t)) -F 2 (q(t)).

(1.7)

Convergence and Stability: the Folk Theorem of EGT

It is easy to see that any Nash equilibrium is a rest point of the replicator dynamics, that is an equilibrium of the ODE (1.6). In fact, if an action in ∆(A) is a NE, all pure strategies in its support earn the same maximal payoff against that strategy, and thus they all earn the population average payoff. This implies that the right side of (1.6) is zero for that action.

The folk theorem of evolutionary game theory [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF], [START_REF] Hofbauer | Evolutionary game dynamics[END_REF] establishes the relation between the rest points of the replicator dynamics, and the Nash equilibria of the symmetric game. Before stating the folk theorem, we define the following notions:

• an orbit is interior if it is such that x(t) ∈ int∆ := {x ∈ ∆|x i > 0, ∀i = 1, . . . , M}, ∀t ≥ 0; • a rest point x * is Lyapunov stable if, for every neighborhood U x * of x * there exists a neighborhood V x * of x * such that x(0) ∈ V x * implies x(t) ∈ U x * , ∀t ≥ 0; • a rest point x * is attracting if it has a neighborhood U x * such that x(t) → x * for t → ∞ holds for ∀x ∈ U x * ;
• a rest point x * is asymptotically stable (or an attractor) if it is both stable and attracting. Theorem 2. [Theorem 2.5.3 (Cressman, 2003)] i. any strict Nash equilibrium is asymptotically stable;

ii. if a rest point is the limit of an interior trajectory, then it is a Nash equilibrium;

iii. if a rest point is Lyapunov stable, then it is a Nash equilibrium, Any ESS is asymptotically stable [START_REF] Hofbauer | A note on evolutionary stable strategies and game dynamics[END_REF], but the converse does not hold in general; only in the special case of two-actions games, we have that dynamic stability is equivalent to evolutionary stability. More precisely, the following result holds. Theorem 3. [Theorem 2.5.4 (Cressman, 2003)] Every interior trajectory that is not initially at rest, converges to an ESS. Furthermore, for the replicator dynamics, the following three statements are equivalent: i. q ∈ ∆(A) is stable.

ii. q is asymptotically stable.

iii. q is an ESS.

The Hawk-Dove Game

One of the most studied examples of evolutionary games, is the Hawk-Dove game, first introduced by Maynard Smith to study the level of aggressiveness in a population of animals competing for a natural resource [START_REF] Smith | Game theory and the evolution of fighting[END_REF]. It has been later used 1.4. The Hawk-Dove Game in a wide variety of fields, spanning from biology to economics, where the notion of aggressive behavior can be translated into a short-term oriented maximization of "selfish" individuals (see e.g. [START_REF] Tomassini | Mutual trust and cooperation in the evolutionary hawks-doves game[END_REF], [START_REF] Hanauske | Doves and hawks in economics revisited: An evolutionary quantum game theory based analysis of financial crises[END_REF]). In engineering, for example, it is used in [START_REF] Altman | The evolution of transport protocols: An evolutionary game perspective[END_REF] to study competition of congestion control algorithms in communication networks, while in (Altman et al., 2008a) it serves to study the interactions between mobile phones that can choose which power to use when transmitting packets.

The standard model has been reformulated in many different ways and a large number of revisited versions of the Hawk-Dove game can be found in the literature. [START_REF] Houston | Fighting for food: a dynamic version of the Hawk-Dove game[END_REF], for example, study a repeated version of the Hawk-Dove model, including a state variable representing animal's level of energy resources and they define an ESS which depends on that variable. Cressman [START_REF] Cressman | The Stability Concept of Evolutionary Game Theory. A Dynamic Approach[END_REF] defines a density dependent Hawk-Dove game, where he modifies the payoff matrix including in the individual's fitness a term that is independent of its strategy, to reflect the biological intuition that population growth rates decrease as density increases ("background fitness"). Crowley [START_REF] Crowley | Hawks, doves, and mixed-symmetry games[END_REF] defines a generalized Hawk-Dove game, modeling interactions between individuals that may differ in size, where size represents "resource holding power". He considers three different situations, based on the amount of information that interacting individuals have about their sizes: the symmetric case, in which no information about sizes is used, the asymmetric case, in which the individuals know their relative sizes, and a mixed-symmetry case, in which each individual only knows its own size.

In Chapter 2 we define a Hawk-Dove model in a new framework, where players are supposed to be (symmetric) groups of interacting individuals. In Chapter 3 we define the notion of GFESS and we compute such equilibrium as a function of the size of the groups for the group-players Hawk-Dove game. In Chapter 6 we study a particular example of a dynamic version of the game, where players are characterized by an individual state and transition probabilities between two states depend on the action of player's opponent.

The Standard Hawk-Dove Game

Suppose that two animals contest for a resource (food, territory,. . . ) of value V. They dispose of two possible pure actions, Hawk (H) and Dove (D), where the first correspond to an aggressive behavior, the second to a passive one. The game is played as follows:

• if two Hawks meet, they fight and each of them has equal probability to win the fight and to be injured. The fight has a cost C;

• if two Doves meet, there is no fight and they equally share the resource;

• if an Hawk meets a Dove, the Hawk gets the resource and the Dove retreats without being injured.

The payoff matrix associated with the game is:

H D H (V -C)/2 V D 0 V/2 (1.8)
There are three possible outcomes, depending on the values of V and C.

• If V > C, the game admits a unique pure strict Nash equilibrium, which is also evolutionarily stable (H, H).

• If V = C, the symmetric pure actions pair (H, H) is still the unique Nash equilibrium; in this case it's not strict (as F H (H) = F D (H)) but it is an ESS.

• If C > V, it's an anti-coordination game, which admits three Nash equilibria: the two non-symmetric pure actions pair (H, D), (D, H) and a mixed NE (q * , q * ), with q * = V/C, where q * is the probability of playing H. The only ESS is (q * , q * ): being a random matching game, a non-symmetric Nash equilibrium can't be an ESS.

The replicator equation of the game is:

q = q(1 -q)(F H (q) -F D (q)) = q(1 -q)( 1 2 (V -C)q + V(1 -q) - V 2 (1 -q)) q(1 -q) 2 (V -Cq), q ∈ [0, 1].
It's easy to verify the folk theorem statements and that, for the Hawk-Dove game the interior orbit of the replicator equation converges to the ESS (q * , q * ).

Chapter 2

Group Players "A society of ants, bees, or termites achieves a kind of individuality at a higher level. Food is shared to such an extent that one may speak of a communal stomach. Information is shared so efficiently by chemical signals and by the famous 'dance' of the bees that the community behaves almost as if it were a unit with a nervous system and sense of organs of its own."

Richard Dawkins, The Selfish Gene, 1976

Summary

In this chapter we present a new model for evolutionary games, in which the concept of the player as a single individual is substituted by that of a player as a whole group. We still consider pairwise interactions among these individuals, but we suppose that the fitness they maximize is that of their group. We analyze a Hawk-Dove game with group players and, as it results to be concave, we prove the existence of a symmetric Nash equilibrium through Rosen's conditions. We explicitly compute it and we obtain that the fact of teaming together makes individuals less aggressive at equilibrium. We finally define a gradient based dynamics as a counterpart of the replicator equation, such the equilibrium of the game is asymptotically stable for such dynamics.

Introduction

We introduce in this chapter a new scenario for evolutionary games, where the notion of the player as a single individual is replaced by that of a player as a whole group. We still consider pairwise interactions among individuals but we assume that they maximize the fitness of the group they belong to. We suppose that the number of groups is finite and we consider two different scenarii: the case of an infinite and that of a finite population of individuals. We allow pairwise interactions within members of the same group and between individuals of different groups. Groups are supposed to be monomorphic, that is, all individuals in a group play the same (possibly mixed) action.

As individuals are indistinguishable, the behavior of an individual is fixed and does not depend on the individual it encounters. In order to provide simple but meaningful results, we analyze the Hawk-Dove game in this framework, and we characterize its equilibria. We adopt the Nash equilibrium as solution concept, rather than the ESS. As a matter of facts, in our game, even if the population of individuals may be infinitely large, the number of players is finite, and, as the Nash equilibrium requires stability against the deviation of one player, in our framework this implies stability against the deviation of a whole group of individuals.

In the next chapter we present the GFESS, a new concept of equilibrium for groupplayers games, which considers local deviations within a group. We show here that we obtain a concave game and we thus apply Rosen's results [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF] to prove that the game admits a unique Nash equilibrium. We finally define a gradient-base dynamics, which converges to the considered equilibrium.

Motivations

In standard EGT, each interacting individual is the player of the game and it chooses its actions in order to maximize its own utility. Many example showing the modeling weaknesses of this assumption can be found. Since in evolutionary games the fitness is defined as related to the reproduction rate, the classical evolutionary game paradigm cannot represent those situations in which only one selected member of a group is responsible for reproduction: in a beehive, for example, the fitness is related to the entire swarm and not to a single bee. Furthermore, in many species, we find altruistic behaviors, which may hurt the individual adopting it, favoring instead the group it belongs to. Altruistic behaviors are typical of parents toward their children: they may incubate them, feed them or protect them from predators at a high cost for themselves. Another example can be found in flock of birds: when a bird sees a predator it gives an "alarm call" to warn the rest of the flock, attracting the predator's attention to itself.

Also the stinging behavior of bees is an altruistic one: it serves to protect the hive, but it's lethal for the bees which strives. Other examples can be found also different contexts. Ass already mentioned, in engineering applications to wireless communication, power control games have frequently been studied in the framework of standard EGT (see e.g. (Altman and Hayel, 2008)). Papers that consider these games usually assume that each mobile can control selfishly its power. In practice however the protocols for power control are not determined by the users of the terminal but by the equipment constructors; this implies that the real competition is among a final number of equipment constructors.

State of Art

The notion of group is not new in evolutionary game theory and different models considering the presence of a finite number of sub-populations have been developed. In those cases, however, the group has a different connotation from the one we introduce here, since it mainly serves to distinguish players with different characteristics and thus to represent asymmetric contexts between individuals. The first evolutionary model considering groups has been introduced by Taylor [START_REF] Taylor | Evolutionarily stable strategies with two types of player[END_REF], who describes a population composed of two types of individuals, I and J, with inter-group and intra-groups interactions. The state of the population as a whole is described by the pair of vectors (p, q), which are the distributions over the pure actions of a player of type I and J respectively, with p = (p 1 , . . . , p m ) and q = (q 1 , . . . , q n ). If the population is in state (p, q) and a sub-population is in state (r, s), the average fitness of a player of type I is given by: F(r|p, q) = m ∑ i=1 F(i|p, q) and the average fitness of type J is: G(s|p, q) = n ∑ j=1 G(j|p, q). The ESS for the two populations model is defined as a pair of actions (p * , q * ) which is stable against simultaneous small deviations of p and q, which means that, for all (r, s) with r = p or s = q:

F(r| p, q) + G(s| p, q) < F(p * | p, q) + G(q * | p, q),
where p = ǫr + (1ǫ)p * , and q = ǫs + (1ǫ)q * . If the fitness functions are linear in (p, q), with F(r| p, q) = r(A p + B q), G(s| p, q) = s(C p + D q), then the ESS condition translates into the conditions: r(A p + B q) + s(C p + D q) ≤ p * (A p + B q) + q * (C p + D q), where, if the equality holds, then r(Ar + Bs) + s(Cp + Ds) < p * (Ar + Bs) + q * (Cr + Ds). Cressman studied (Cressman, 1992) the same scenario but he gives a weaker definition of the ESS: while Taylor's ESS performs better in both groups than any other mutant action pair, he requires jut that (p * , q * ) performs better for (at least) one of the two groups, and thus, either:

r(A p + B q) < p * (A p + B q) or s(C p + D q) < q * (C p + D q).
Cressman provides different equivalent definitions of this ESS in the two-species context. Both Taylor's and Cressman's definitions have been later extended to a multipopulation scenario: see the following chapter for an introduction to the N-species ESS.

Our framework is closer to multipopulation games as defined by Sandholm [START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF]. He considers a society composed of p populations, each with mass m i and a set of strategies S i , i = 1, . . . , p. The population state x i of population i is given by a distribution over the set of strategies S i , while a social state x describes the behavior in all p populations. The game is defined by the payoff function F, which assigns to each social state a vector of payoffs, one for each strategy in each population. By Fi (x), Sandholm denotes the average payoff function in population i. He thus also considers the payoff associated with a whole group of interacting individuals, but, while Sandholm focuses on the different dynamics in this kind of games, introducing the notion of revision protocol, we mainly adopt here a static approach and we consider different solution concepts. In 2.2. The General Model particular, we study here the Nash equilibrium for a group-player Hawk-Dove game, while in the following chapter we define and we characterize a new equilibrium, the GFESS, in a general framework.

The chapter is structured as follows: in the next section we describe our framework and we define the fitness of a group-player in two different cases: that of an infinite population of individuals and that of a finite one. In Section 2.3 we study the Hawk-Dove game in both contexts: we first prove, in Subsection 2.3.1 the existence and the uniqueness of the equilibrium and we then explicitly compute it. We finally define a gradient based dynamics in Section 2.3.2.

The General Model

We consider a population of individuals divided into N groups, G 1 , . . . , G N with N ≥ 2; for simplicity of presentation we will consider symmetric groups of the same size. Let A = {a 1 , a 2 . . . a M } be the set of pure actions and ∆(A) be the corresponding set of mixed actions. We suppose that the sub-population in each group is monomorphic, that is all individuals in the same group adopt the same action. Individuals are indistinguishable and their behavior is fixed. We thus associate to each group G i the mixed action (or state vector)

p i = (p i 1 , . . . , p i M ) ∈ ∆(A), with M ∑ l=1 p i l = 1.
We define a multiaction as the vector of all N group's actions, denoted by p = (p i , . . . , p N ) ∈ ∆(A) N . Let π ij be the probability that an individual in group G i meets an individual in group G j .

The expected fitness of a (group) player G i playing p i ∈ ∆(A) in a population whose multiaction is p is defined by:

Γ i (p i , p -i ) = π ii (p i , p i ) + N ∑ j=1,j =i π ij F(p i , p j ), p i , p j ∈ ∆(A), (2.1)
where p -i = (p 1 , . . . , p i-1 , p i+1 , . . . , p N ), and F(p i , p j ) (resp. F(p i , p i )) denotes the immediate fitness of an individual playing mixed action p i against an opponent playing p j (resp.p i ). The function Γ i is linear in p -i . Note that, as the groups are symmetric, the expected fitness only depend on the strategy used by the player and by the population, i.e. Γ i (p i , p -i ) = Γ(p i , p -i ), ∀i = 1, . . . , N. The probabilities π ij depend on the size of the population. In what follows we see the case of an infinite and that of a finite population of individuals.

The Case of an Infinite Population of Individuals

If the population of individuals is infinitely large, we can assume that the probability of an interaction among two individuals of the same group equals the probability of an interaction among actors of different groups. We thus have that:

π ii = π ij = 1/N ∀i, j = 1, . . . , N.
The resulting expected fitness of a (group) player G i playing p i ∈ ∆(A) in a population whose multiaction is p is given by:

Γ(p i , p -i ) = 1 N F(p i , p i ) + 1 N N ∑ j=1,j =i F(p i , p j ), p i , p j ∈ ∆(A).
(2.2)

The Case of a Finite Population of Individuals

In order to study the impact of the size of groups on the equilibrium, we now consider a finite population of individuals, with size NK, which is thus divided into N groups of size K. The probability that an individual in group G i meets an individual in group G j is given by:

π ij =          K -1 NK -1 if i = j K NK -1 if i = j i, j = 1, . . . , N
The expected fitness of a group playing action p i ∈ ∆(A) in a population whose multiaction is p can be rewritten as:

Γ(p i , p -i ) = K -1 NK -1 F(p i , p i ) + K(N -1) NK -1 N ∑ j=1,j =i F(p i p j ), p i , p j ∈ ∆(A) (2.3)

Hawk-Dove Game with Group Players

We study here the Hawk-Dove game in the framework of group players. Let A = {H, D}; the payoff associated with actors' pairwise interactions is given by the follow-ing matrix:

H D H 1/2 -δ 1 D 0 1/2 , (2.4)
which is obtained from (1.8) with V = 1 and C = 2δ. With some abuse of notation, since a mixed action is given by p = (p H , p D ) with p D = 1 -p H , the action of a group i is represented simply by the probability of being aggressive, p i ∈ [0, 1], i = 1, . . . , N.

Existence and Uniqueness of the Equilibrium

As in our model the number of player is finite and each player corresponds to a group, we adopt the Nash equilibrium as solution concept rather than the ESS. This choice is also justified by the fact that, as the Nash equilibrium is stable against the deviation of on player, in our model this implies the stability against the deviation of a whole group of individuals, as the player is the group.

The existence and the uniqueness of the equilibrium for concave games have been proved

by Rosen [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]. He considers N players games where each player disposes of a set of mixed actions ∆ i , i = 1, . . . , N, and where player's i payoff function F i (p) depends on the vector of actions of all the the N players, p = (p 1 , . . . , p N )

∈ ∆ := ∆ 1 × . . . × ∆ N .
The game is said to be concave if the product space of actions ∆ is convex, closed and bounded ∀p ∈ ∆, and F i (p) is continuous in p and concave in p i (for fixed p -i ). Then, every concave game admits a Nash equilibrium. Rosen also introduces the weighted

sum of payoffs σ(p, r) = N ∑ i=1 r i F i (p)
, with r i ∈ R + and its pseudogradient:

g(p, r) =       r 1 ∇ 1 F 1 (p) r 2 ∇ 2 F 2 (p) . . . r 1 ∇ N F N (p)       . (2.5)
The equilibrium point of the game p ∈ ∆ is proved to be unique when σ(p, r) is diagonally strictly concave for a positive r, which means that for a fixed non-negative vector r ≥ 0 and every vector q = p:

(p -q) ′ g(q, r) + (q -p) ′ g(p, r) > 0.

Hofbauer and Sandholm [START_REF] Hofbauer | Stable population games and integrability for evolutionary dynamics[END_REF]) establish the connection be-tween diagonally strictly concave games and stable population games. They define a p-players game and a p unit masses population game, proving that the diagonal concavity of the first one is equivalent to the stability of the latter.

In what follows we prove that the infinite and the finite-population models are concave games and they both satisfy the diagonal concavity condition, which prove the existence and the uniqueness of the equilibrium. In [START_REF] Brunetti | Revisiting evolutionary game theory[END_REF] we present this model also in a third case, where the population of individuals is finite and the number of groups is random, but it does not satisfy the diagonally concavity condition.

Infinite Population

From the definition of ∆(A), it trivially follows that the product space ∆ = ∆(A) N = [0, 1] N is convex, closed and bounded. When considering an infinite population and the Hawk-Dove payoff matrix (2.4), the fitness of a (group) player adopting action

p i ∈ [0, 1] in a population whose multiaction is p = (p 1 , . . . , p N ) ∈ [0, 1] N (2.2) equals Γ(p i , p -i ) = 1 N F(p i , p i ) + 1 N N ∑ j=1,j =i F(p i , p j ) = 1 N (-δ)(p i ) 2 + 1 2 + N ∑ j=1,j =i (-δp j + 1 2 )p i + 1 -p j 2 .
(2.6) Function Γ in (2.6) is continuous in p and it's easy to verify that it's also concave in p i , i.e. (Rosen, 1965), it follows that there exists an equilib- rium point p * for our game. We verify that it is also unique. Let σ(p, r) :

Γ(ǫp

i + (1 -ǫ)q i , p -i ) > ǫΓ(p i , p -i ) + (1 -ǫ)Γ(q i , p -i ), with q i ∈ [0, 1]. From Theorem 1 in
= N ∑ i=1 r i Γ(p),
r i ≥ 0 and its pseudogradient (Rosen, 1965):

g(p, r) :=       r 1 ∇ 1 Γ(p 1 , p -1 ) r 2 ∇ 2 Γ(p 2 , p -2 ) . . . r 1 ∇ N Γ(p N , p -N )       . (2.7)
To prove that σ(p, r) is diagonally strictly concave for a positive r ≥ 0, we need to prove that the inequality (p -q) ′ g(q, r) + (q -p) ′ g(p, r) > 0 holds for all q = (q 1 , . . . , q N ) = p. A sufficient condition for this inequality to hold is given in Theorem 6 in [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]. It states that, if the symmetric matrix:

[G(p, r) + G ′ (p, r)],
is negative definite, where G(p, r) is the Jacobian with respect to p of g(p, r):

G(p, 1) = ∂g(p, r) ∂p =        ∂g(p, r) ∂p . . . ∂g(p, r) ∂p . . . . . . . . . ∂g(p, r) ∂p . . . ∂g(p, r) ∂p       
, then σ(p, r) is diagonally strictly concave. We fix r = (1, . . . , 1); the pseudogradient of our game is:

g(p, 1) =              -2δp 1 N + 1 N ∑ j =1 (-δp j + 1 2 ) -2δp 2 N + 1 N ∑ j =2 (-δp j + 1 2 ) . . . -2δp N N + 1 N ∑ j =N (-δp j + 1 2 )              . (2.8)
We thus obtain that:

G(p, 1) = - δ N ( 1 + I),
where 1 is the N × N matrix with all the elements equal to 1 and I is the identity matrix.

The sum ( 1 + I) has N -1 eigenvectors of the form (1, 0, -1, 0, . . .) ′ with a corresponding eigenvalue 1 and one eigenvector (1, 1, . . . , 1) ′ with eigenvalue N + 1, which means that G(p, 1) has strictly negative eigenvalues and thus it is strictly negative definite.

From theorem 2 in [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF], this proves the uniqueness of the Nash equilibrium of our game. We explicitly compute it and we resume our results in the following proposition.

Proposition 2. The group-players Hawk-Dove game with an infinite population of individuals admits a unique symmetric Nash equilibrium which is given by

p * = N -1 N + 1 1 2δ .
(2.9)

Proof. We have already proved the existence and the uniqueness of the equilbrium through Rosen's conditions. We thus compute the symmetric equilibrium value p * by maximizing the group fitness function. We have that:

∂Γ(p i , p -i ) ∂p i = -2δ N p i + 1 N N ∑ j=1,j =i ( 1 2 -δp j ).
By imposing ∂Γ(p i , p -i ) ∂p i = 0, we get:

p i = 1 2δN N ∑ j=1,j =i (-δp j + 1 2
).

To obtain the symmetric Nash equilibrium of the game, we set p i = p j = p * , which leads to:

p * = N -1 N + 1 1 2δ .
It is interesting to study the two extreme cases N → ∞ and N = 2.

• When the number of groups is infinite, i.e. N → ∞, we obtain:

p * = 1 2δ
which is the value of the equilibrium of the corresponding standard Hawk-Dove game. This is consistent with a similar result in [START_REF] Haurie | On the relationship between Nash-Cournot and Wardrop equilibria[END_REF], that shows the convergence of Nash equilibrium to Wardrop equilibrium as the number of players goes to infinity.

• When we have only two players (formed by an infinity of individuals), i.e. N = 2 , we obtain:

p * = 1 6δ
which means that two groups are less aggressive then two standard players. uals). We can observe that the equilibrium p * is an increasing function of the number of groups. Note that when N increases, the probability of meeting a member of a different group also increases: we thus obtain that the level of aggressiveness is higher when the probability of interactions among individuals of different groups increases. Hence, if an individual is aggressive, it causes less damage to its group. This can explain the fact that the equilibrium probability of being aggressive is increasing in N. As one may expect, we also observe that when the cost δ increases, at the equilibrium, the probability p * of being aggressive decreases.

Finite Population of Individuals

If the population of individuals has finite size NK, with payoff matrix (2.4). The fitness defined in (2.3) becomes:

Γ(p i , p -i ) = K -1 NK -1 (-δ)(p i ) 2 + 1 2 + K NK -1 N ∑ j=1,j =i (-δp j + 1 2 )p i + 1 -p j 2 .
Proposition 3. The Hawk-Dove game with a finite population divided into N groups admits a unique symmetric Nash equilibrium which is given by

p * = K(N -1) K(1 + N) -2 1 2δ
.

(2.10)

Proof. It is easy to verify that, as in the infinite population case, Rosen's conditions for the existence and the uniqueness of the equilibrium introduced in [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF] are satisfied. We thus compute the symmetric equilibrium:

∂Γ(p i , p -i ) ∂p i = -2 K -1 NK -1 δp i + K NK -1 N ∑ j=1,j =i ( 1 2 -δp j )
and, by imposing ∂Γ(p i , p -i ) ∂p i = 0, we obtain:

p i = K 2(K -1) N ∑ j=1,j =i (-p j + 1 2δ
).

If p i = p j = p, then:

p = K(N -1) 2(K -1) ( 1 2δ -p).
The symmetric Nash equilibrium is thus given by:

p * = K(N -1) K(1 + N) -2 1 2δ
.

In Figure 2.3 we plotted the value of the equilibrium p * as a function of N, with 2 ≤ N ≤ 20, for three different values of K and a fixed δ = 2. As in the previous case, we can observe that p * is an increasing function of N. In Figure (2.4) we plotted p * as a function of the size of the groups. We can note that p * rapidly decreases for small K;

when K > 10, p * stabilizes and it is very slowly decreasing. The explanation for this behavior is that when K is small, then the probability of meeting an individual of one's own group is quite sensitive to K, which is not the case when K is large.

Convergence to the Equilibrium

In evolutionary games, instead of interpreting the equilibrium as a static notion, it's preferable to suppose that individual agents can gradually adjust their choices to their current strategic environment, and to study whether the induced distribution of actions converges to a stable situation. To provide a dynamic foundation of the equilibrium of our game, we introduce actions' dynamics in our model, such that the Nash equilibria computed above are asymptotically stable for these dynamics.

We assume that each group-player changes its action in order to increase the payoff of the group. By following Rosen's approach [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF], we can describe the interval

∆(A) = [0, 1] through the mapping h i (p i ) = (p i , 1 -p i ) ′ , so that [0, 1] = {p|h i (p) ≥ 0}. Let h(p) = (p 1 , 1 -p 1 , p 2 , 1 -p 2 , . . . , p N , 1 -p N ) be the function representing all the 2N constraints, such that [0, 1] N = {p|h(p) ≥ 0}.
We suppose that a group changes its action at a rate proportional to the gradient of its payoff function with respect to its action and subject to the 2N constraints. This leads to the action dynamics:

ṗi = r i ∇ i Γ(p i , p -i ) + 2N ∑ j=1 u j ∇ i h j (p), (2.11)
where Γ(p i , p -i ) is the fitness of G i and the vector u lies in a bounded subset U(p) ⊂ R 2N . The sum on the right hand of (2.11) serves to assure that p i remains in [0, 1]. More precisely, define the

N × 2N matrix H = [∇ 1 h(p) ∇ 2 h(p), . . . , ∇h 2N (p)],
which is independent of p:

H =          1 -1 0 0 0 . . . . . . 0 0 1 -1 0 0 . . . 0 0 0 0 1 -1 0 . . . . . . . . . . . . . . . . . . . . . 0 0 . . . . . . . . . 1 -1         
(2.12)

Define the function:

f (p, u, r) = g(p, r) + H(p)u.
From the definition of the pseudogradient, the system of N dynamic equations can be written as:

ṗ = f (p, u, r), u ∈ U(p),
where the set U(p) is given by:

U(p) = {u| f (p, u, r) = min v j ≥ 0, j ∈ J, v j = 0 otherwise f (p, u, r) }
and:

J = J(p) = {j ∈ {1, . . . , 2N}|h j (p) ≤ 0}.
According to Rosen's theorem, the negative definiteness of the Jacobian G(p, r) guarantees the global asymptotic stability of the equilibrium for the system (2.11). We thus use equations (2.11) as a counterpart of replicator dynamics in our groups evolutionary game. The global stability of the equilibrium point permits to determine the equilibrium point for any concave game by appropriate mathematical programming computational methods. In particular, gradient methods for a concave nonlinear programming problem [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF] can be modified to find the equilibrium point for a concave game.

Conclusion

In this chapter we proposed a new approach to evolutionary games, modeling those situations in which the player is not the individual involved in the interactions, as the fitness is associated with a whole group rather than to the single interacting individual.

We studied the Hawk-Dove game, in this group-players framework in two different cases: for an infinite population of individuals and for a finite one. We verified that the obtained Hawk-Dove group-players game is convex, which allowed us to prove the existence and the uniqueness of the Nash equilibrium through Rosen's results [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]. We then explicitly computed it as a function of the number of groups. We finally defined a gradient-based dynamics, such that the equilibrium obtained is asymptotically stable for this dynamics. In the following chapter we define a different concept of equilibrium, related to a notion of local deviation within a group.

Chapter 3

A New Equilibrium Concept: Group Fitness Evolutionarily Stable Strategy "Imagination is more important than knowledge. For knowledge is limited to all we now know and understand, while imagination embraces the entire world, and all there ever will be to know and understand."

Albert Einstein, 1929

Summary

Following the idea of group players presented in the previous chapter, we introduce here a new concept of equilibrium, the Group Fitness Evolutionarily Stable Strategy, based on the group fitness function and related to a notion of deviation within groups. We compare the GFESS to the standard ESS and we characterize it in the case of two pure actions games. We illustrate our results through some classical examples and we show a possible application in multiple access control framework.

Introduction

We pursue here the line of research presented in Chapter 2, studying a large population in which pairwise interactions among randomly selected individuals occur, but where the actual player of the game is the whole group. While in Chapter 2 we restrain to symmetric groups of the same size and we study the symmetric Nash equilibria of the game, we now consider groups with different sizes and we introduce a new concept of equilibrium, the Group Fitness Evolutionarily Stable Strategy (GFESS). The stability required by the GFESS is related to a notion of deviation within a group, and thus of a "fraction" of the player (instead of a fraction of a population). We thus do not attempt to simply extend the standard definitions of EGT to a multipopulation setting, but we provide a new modeling framework, where the player is the group but the interactions occur among individuals.

We explore the relationship between GFESS and standard ESS and, for the particular case of two strategies games, we provide a characterization of the equilibria. We then extend the definition of group's fitness to the case in which the payoff matrix associated with intragroup interactions is different from that associated with intergroups interactions, and we apply this model to study a problem of multiple access control.

State of Art

Garay and Varga [START_REF] Garay | Strict ESS for n-species systems[END_REF] first define the N-populations strict ESS for multipopulation games with symmetric conflicts within the species (populations) and asymmetric conflicts between them. The player is the individual and the fitness is defined through a system of payoff matrices {A ij } where A ij represents the payoff of species i in its conflict with species j. Then p * = (p 1 * , . . . , p N * ) is a N-populations strict ESS if, for all p = p * and for i ∈ {1, . . . , N} with p i = p i * , there exists 0 < ǫ i p < 1 such that, for all 0 < ǫ i < ǫ i p we have:

p i N ∑ i=1 A ij pj < p i * N ∑ i=1 A ij pj ,
where pj = ǫ j p j + (1ǫ j )p j * . The authors prove that this is equivalent to require that

p i N ∑ i=1 A ij p j < p i * N ∑ i=1 A ij p j ,
for all p = p * in some neighborhood of p * .

The static definition of strict N-populations ESS extends Maynard Smith's standard definition of evolutionary stability and that given by Hofbauer and Sigmund for asymmetric matrix games (J. Hofbauer and K.Sigmund, 1988). The authors also introduce a weaker notion of stability, the evolutionary dynamical stability: a state p * is said to be evolutionarily dynamically stable if, ∀p = p * , the vector (1, 1, . . . , 1) ∈ R N is an asymptotically stable rest point of the system

ǫi = ǫ i [p i * -pi ] A ij pj , i = 1, . . . , N.
A evolutionarily dynamically stable state is equivalent to the standard ESS for N = 1 and to the Cressman definition of two-species ESS for N = 2 (Cressman, 1992). In an analogous setting, Cressman et al. [START_REF] Cressman | Evolutionary stability concepts for n-species frequency-dependent interactions[END_REF] focuses on a dynamical approach to the ESS, assuming that selection acts much faster than mutation and thus the incumbent population has enough time between mutations to eliminate the less fit ones. They define a dynamics for the game and they provide a definition of a Npopulations ESS related to a property of local asymptotically stability for the dynamics introduced. Their ESS is equivalent to the dynamically stable state in [START_REF] Garay | Strict ESS for n-species systems[END_REF], and it is such that at least one of the species earns more that any mutant strategy.

While in [START_REF] Garay | Strict ESS for n-species systems[END_REF] and [START_REF] Cressman | Evolutionary stability concepts for n-species frequency-dependent interactions[END_REF] it is assumed that all populations have the same number of individuals and thus the size of the populations is not considered, in our model the GFESS is defined as a function of the groups' (normalized) sizes, which allows us to study the impact of groups sizes on the equilibrium output.

Sandholm [START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF] compares the two rather different ways of extending the standard definition of ESS to multipopulation games. The Taylor's condition (see Chapter 2) for a N-populations state x = (x 1 , . . . , x N ) to be an the ESS requires that, for any multipopulation incumbent state y = (y 1 , . . . , y N ) = x in a neighborhood of x, the aggregate payoff, i.e. the payoff of the society as a whole, of the invading society in state x, exceeds the aggregate payoff of the society in state y, and thus (y -x) ′ F(y) < 0.

For Cressman ESS, it is enough that for one population i in the society composed of N populations, action x i earns a higher average payoff than the corresponding y i and thus (y ix i ) ′ F i (y i ) < 0, where F i (y i ) denotes the average payoff of population i. The more appropriate extension of the evolutionary stability studied by Maynard Smith and Price, with monomorphic populations of mixed strategists, is the ESS concept defined by Cressman, while Taylor ESS is more useful to understand the dynamics of behavior in polymorphic populations of pure strategists.

Group Fitness Evolutionarily Stable Strategy

Note that for N = 1 these N-population games reduces to the standard EGT models whereas in our framework, if there's only one group, there's no game but an optimization problem, since the player is the group.

The chapter is structured as follows. We first introduce in Section 3.2 the definition of the GFESS and we analyze the relationship between GFESS standard ESS. In Section 3.3

we provide the characterization of the GFESS in the case of two actions game. Section 3.4 gives some numerical illustration through three classical examples, the Hawk-Dove game, the Stag Hunt game and the Prisoner's Dilemma. In section 3.5 we study an application in multiple access control in slotted Aloha.

Group Fitness Evolutionarily Stable Strategy

Consider a large population divided into N groups, denoted by G i , i = 1, 2, .., N where the normalized size of G i is α i , with

N ∑ j=1 α j = 1. Suppose that each individual in group G i
interacts with a member of G j with probability α j , i, j = 1, . . . , N. Let A = {a 1 , a 2 , .., a M } be the finite set of pure actions and ∆(A) the corresponding set of mixed actions; as we did in the previous chapter, we suppose that all individuals in the same group adopt the same (mixed) action and thus, we associate to each G i a vector q i = (q i 1 , q i 2 , .., q i M ) ∈ ∆(A), where q i k is the probability that an individual in group G i chooses an action a k ∈ A, M ∑ l=1 q i l = 1. Let q = (q 1 , . . . , q N ) ∈ ∆(A) N denote the multiaction of the population.

The expected fitness of a group-player G i is:

Γ i (q i , q -i ) = N ∑ j=1 α j F(q i , q j ), (3.1)
where q -i = (q 1 , . . . , q i-1 , q i+1 , . . . , q N ) ∈ ∆(A) N-1 and F(q i , q j ) denotes the immediate expected fitness of an individual adopting action q i against an opponent playing q j . F(•, •) is assumed to be bilinear. Γ i is thus a weighted sum of the possible individual fitness, where the weights are given by the normalized sizes of the players.

The definition of the GFESS is related to a robustness property against local deviations in a group. While in Chapter 2 we consider symmetric Nash equilibria among groups, which are stable against the deviation of one group-player, here we consider deviations of a 'fraction of the player', i.e. of a share of individuals in a group, and we define and characterize the equilibria (not necessarily symmetric) which are robust against these deviations. More precisely, an ǫ-deviation in group G i consists in a (possibly) large

G 1 G 2 G 3 G 4 G 6 G 5 G 7
G 8 q 4 q 3 q 6 q 6 q 7 q 7 q 7 q 7 q 7 q 3 q 6 q 1 q 7 q 5 q 5 q 8 q 8 q 8 q 2 q 8 q 3 q 8

Figure 3.1:

The population of individuals is divided into a finite number of groups G i , i = 1, . . . , N. Each individual can interact with a member of its group or of a different one. All individuals in G i adopts the same strategy q i (no matter which individual they encounter).

deviation of a small fraction ǫ of individuals of the group from the incumbent action q i to a different (mutant) action p i . From the definition of the group fitness function 3.1, this is mathematically equivalent to a small deviation in the action by all members of G i to the mixed action pi := ǫp i + (1ǫq i ) ∈ ∆(A). The population's state after the deviation becomes (q 1 , . . . , q i-1 , ǫp i + (1ǫ)q i , q i+1 , . . . q N ) and the average payoff of the mutant group is given by:

Γ i ( pi , q -i ) = N ∑ j=1 α j F( pi , q j ) = Γ i (q i , q -i ) + ǫ(-α i Ω(p i , q i ) + Γ i (p i , q -i ) -Γ i (q i , q -i )) + ǫ 2 α i Ω(p i , q i ) = Γ i (q i , q -i ) + ǫ α i (F(p i , q i ) + F(q i , p i ) -2F(q i , q i )) + ∑ j =i α j (F(p i , q j ) -F(q i , q j ) + ǫ 2 α i Ω(p i , q i ), (3.2)
where Ω(p i , q i ) := F(p i , p i ) -F(p i , q i ) -F(q i , p i )) + F(q i , q i ). Definition 4. A multiaction q = (q 1 , q 2 , .., q N ) is a Group Fitness Evolutionarily Stable Strategy (GFESS) if for all i = 1, . . . , N and for all p i = q i ∈ ∆(A), there exists some ǫ p i ∈ (0, 1), which may depend on p i , such that for all ǫ ∈ (0,

ǫ p i ) Γ i ( pi , q -i ) < Γ i (q i , q -i ), (3.3)
where pi

= ǫp i + (1 -ǫ)q i .
Note that a GFESS is stable against local deviations in one group, i.e., we suppose that only one mutant group can be present in the population at the same time. We define:

Ψ i (p i , q) := Ω(p i , q i ) -Γ i (p i , q -i ) + Γ i (q i , q -i ), (3.4)
and we provide, in the following proposition, a characterization of the GFESS, which is equivalent to Definition (4). Proposition 4. A multiaction q = (q 1 , q 2 , .., q N ) is a GFESS iff it satisfies the two following conditions:

i. ∀p i ∈ ∆(A) Ψ i (p i , q) ≥ 0, (3.5)
ii. if ∃p i = q i such that:

Ψ i (p i , q) = 0 ⇒ Ω(p i , q i ) < 0 (3.6)
Proof. It follows from the definition that multiaction q is a GFESS iff ∀ǫ ∈ (0,

ǫ p i ) the difference Γ i ( pi , q -i ) -Γ i (q i , q -i
) is strictly negative; if we explicit this difference we get:

ǫ 2 α i Ω + ǫ[α i (F(p i , q i ) + F(q i , p i ) -2F(q i , q i )) + ∑ j =i α j (F(p i , q j ) -F(q i , q j ))] < 0 ⇔ -ǫ[α i (F(p i , q i ) + F(q i , p i ) -2F(q i , q i )) + ∑ j =i α j (F(p i , q j ) -F(q i , q j ))] -ǫ 2 α i Ω > 0.
As ǫ is small, this is true if either the coefficient of ǫ is strictly positive or if it is null and the coefficient of ǫ 2 is strictly positive. As the coefficient of ǫ is:

-

[α i (F(p i , q i ) + F(q i , p i ) -2F(q i , q i )) + ∑ j =i α j (F(p i , q j ) -F(q i , q j ))] = α i (Ω(p i , q i ) -F(q i , q i ) + F(p i , p i )) + ∑ j =i α j (F(p i , q j ) -F(q i , q j )) = α i Ω(p i , q i ) -Γ i (p i , q -i ) + Γ i (q i , q -i ) = Ψ(p i , q),
conditions (i) and (ii) straightforwardly follow.

Nash Equilibrium and Group-Players

Definition 5. The multiaction q = (q 1 , q 2 , .., q N ) is a Nash Equilibrium of the N groups game if ∀i ∈ {1, . . . , N}

Γ i (q i , q -i ) ≥ Γ i (p i , q -i ), p i = q i . (3.7)
If it holds with strict inequality, then q is a strict Nash equilibrium.

It trivially follows that any strict Nash (multiaction) equilibrium is a GFESS. Note that, if multiaction q satisfies condition (3.6), it implies that there exists an action p i = q i ∈ ∆(A) such that:

α i Ω(p i , q i ) = Γ i (q i , q -i ) -Γ i (p i , q -i ) Ω(p i , q i ) < 0 ,
and thus:

Γ i (q i , q -i ) > Γ i (p i , q -i ). It follows that, if ∀i = 1, . . . , N, condition (3.6) is satisfied ∀p i = q i ∈ ∆(A)
, then multiaction q is a strict Nash equilibrium. The GFESS we defined can be interpreted as a local strict Nash equilibium in the groups game.

GFESS and Standard ESS

Since we consider pairwise interactions among individuals and the fitness of a group is defined as a weighted sum of individual fitness, we study here the relationship between the ESS in a standard game (with individual players) and GFESS in a group-players game.

Proposition 5. Suppose that the fitness function F related to pairwise interactions among individuals is symmetric, i.e. F(p, q) = F(q, p). Then, if q * ∈ ∆(A) is an ESS in the standard game, multiaction q = (q * , . . . , q * ) ∈ ∆(A) N is a GFESS in the N group-players game.

Proof. Let q * ∈ ∆(A) be an ESS in a standard evolutionary game and let q = (q * , .., q * ) ∈ ∆(A) N be a multiaction for the N group-players game. From the symmetry of the fit-ness function:

Ψ i (p i , q * ) = -α i (F(p i , q * ) + F(q * , p i ) -2F(q * , q * ) + ∑ j =i α j (F(p i , q * ) -F(q * , q * ) = -2α i (F(p i , q * ) -F(q * , q * )) -(1 -α i )(F(p i , q * ) -F(q * , q * )) = -(1 + α i )(F(p i , q * ) -F(q * , q * )). *
From the definition of ESS, we obtain that Ψ i (p i , q * ) ≥ 0, which means that multiaction q satisfies the first condition (3.5). If there exists a p i = q * such that Ψ i (p i , q * ) = 0, then F(p i , q * ) = F(q * , q * ) and Ω(p i , q) = F(p i , p) -F(p i , p i ). Since q * is an ESS, F(p i , q * ) = F(q * , q * ), implies that F(p i , p i ) < F(q * , p i ), and thus condition (3.5) is satisfied. This completes the proof.

In order to provide a characterization of the GFESSs, for simplicity of presentation, in the next section, we consider the case of two pure actions games.

Analysis of N Groups Games with Two Pure Actions

In this section we study the group-players game when the set of pure actions is given by A = {X, Y}. The payoff matrix associated with pairwise interactions among individuals is:

A = X Y X a b Y c d , (3.8)
where the entries of the matrix A ij , i, j ∈ {X, Y} give the payoff of the first (row) individual if it plays pure action i against the second (column) individual playing action j. The payoffs of the column (individual) player are given by the transposed of A. A mixed strategy q i ∈ ∆(A) is given by q i = (q i X , q i Y ), where q i Y = 1 -q i X . With some abuse of notation, in the following we identify a strategy simply as the probability of playing strategy A, i.e.

q i = q i X ∈ [0, 1].
Conditions (3.5)-(3.6) can be rewritten as follows:

• ∀p i ∈ [0, 1], i = 1, .., N: Ψ i (p i , q) = (q i -p i ) α i (F(q i , 1) -F(q i , 0)) + N ∑ j=1 α j (F(1, q j ) -F(0, q j )) ≥ 0.
(3.9)

• If Ψ i (p i , q) = 0 for some p i = q i , then:

∆ < 0, where ∆ = a -b -c + d. (3.10)
We now give a characterization of the possible GFESS for two pure actions games, depending of the values of the payoff matrix and on the size of the groups. We distinguish between pure, mixed and fully mixed GEES. Without loss of generality, we reorder the groups according to their size, to have

α 1 ≤ α 2 ≤ . . . ≤ α N .

Pure GFESS

We identify a pure multiaction with a number N X ∈ {0, ..., N}, which indicates that the N X first groups use pure action X and the remaining N -N X groups play pure action Y. For example, N X = N (resp. N X = 0) stands for the multiaction (X, . . . , X) (resp.

(Y, . . . , Y)), where all groups choose pure action X (resp. Y). Proposition 6. For the two pure actions game, we have the following characterization of the pure GFESS.

i. If ∀i = 1, . . . , N: a -c > α i (b -a) or a -c ≥ α i (b -a) ∆ < 0 then N X = N is a GFESS; ii. If ∀i = 1, . . . , N: b -d < α i (d -c) or b -d ≤ α i (d -c) ∆ < 0 then N X = 0 is a GFESS; iii. Let 1 ≤ N X ≤ N -1 and define H(N X ) := N X ∑ j=1 α j (a -c) + N ∑ j=N X +1 α j (b -d). If: H(N X ) > α i (b -a) i = 1, . . . , N X H(N X ) < α i (d -c) i = N X + 1, . . . , N or      H(N X ) ≥ α i (b -a) i = 1, . . . , N X H(N X ) ≤ α i (d -c) i = N X + 1, . . . , N ∆ < 0 then N X is a GFESS.
Proof.

i. The pure multiaction N X = N (corresponding to (X, . . . , X)) is a GFESS in the two actions game if, either it satisfies condition (3.9) with strict inequality for all i, or, if the inequality is not strict, if for some i it holds with equality, for these, the condition (3.10) is verified. Note that N X = N means that q i = 1 for all i = 1, . . . , N. We can then rewrite condition (3.9) as:

(1

-p i ) α i (a -b) + N ∑ j=1 α j (a -c) = (1 -p i ) α i (a -b) + a -c) ≥ 0 ∀p i = 1, ∀i = 1, . . . , N. Since (1 -p i ) > 0, the latter inequality is satisfied iff: a -c ≥ α i (b -a)
∀i. We thus have that, either condition (3.9) is satisfied with strict inequality for all i, or, if the equality holds for some i ∈ {1, . . . , N}, then condition (3.10) needs to be satisfied, i.e. ∆ < 0, which completes the proof of (i).

ii. Following the same line of the proof of (i), for the pure multiaction N X = 0 (corresponding to q i = 0 for all i = 1, . . . , N) condition (3.9) can be rewritten as:

-p i α i (c -d) + N ∑ j=1 α j (b -d) = -p i α i (c -d) + b -d) ≥ 0 ∀p i = 0, ∀i = 1, .
. . , N, which leads to:

α i (c -d) + b -d ≤ 0 ∀i = 1, . . . , N,
and thus, either b -

d < α i (c -d) for all i or α i (c -d) + b -d ≤ 0 and ∆ < 0.
iii. We now consider the pure multiaction N X , with N X ∈ {1, . . . , N -1}, (i.e. of the kind (X, . . . , X, Y, . . . , Y)). Following the line of (i) and (ii), for N X , condition (3.9) becomes

           (α i (a -b) + N X ∑ j=1 α j (a -c) + N ∑ j=N X +1 (b -d) ≥ 0 i = 1, . . . , N X (α i (c -d) + N X ∑ j=1 α j (a -c) + N ∑ j=N X +1 (b -d) ≥ 0 i = N X + 1, . . . , N. By defining H(N X ) := N X ∑ j=1 α j (a -c) + N ∑ j=N X +1
α j (b -d), from the considerations in (i) and (ii), we obtain (iii), which completes the proof.

Fully Mixed GFESS

We say that a multiaction q is fully mixed if each group i uses a mixed action q i = (q i 1 , . . . , q i M ) ∈ ∆(A) which assigns positive probability to each pure action, i.e., 0 < q i l < 1 for l = 1, . . . , M, i = 1, . . . , N. Proposition 7. Define, for i = 1, . . . , N :

q i * := d -b + (1 + N)α i -1 (d -c) (N + 1)α i ∆ . (3.11)
If ∆ < 0 and 0 < q i * < 1, ∀i = 1, . . . , N, then the multiaction q * = (q 1 * , . . . , q N * ) is the unique fully mixed GFESS equilibrium of the N group-players two pure actions game.

Proof. From the definition of the GFESS for the two actions game, we can observe that a fully mixed multiaction q = (q 1 , . . . , q N ) ∈]0, 1[ N can satisfy condition (3.9) only with equality, i.e.:

α i (F(q i , 1) -F(q i , 0)) + N ∑ j=1 α j (F(1, q j ) -F(0, q j )) = 0 ∀i = 1, . . . , N,
This leads to

α i ∆q i + b -d + α i (c -d) + ∆ N ∑ j=1 α j q j = 0.
By imposing it for all i = 1, . . . , N, we get:

q i * = d -b + (1 + N)α i -1 (d -c) (N + 1)α i ∆ . q = (q 1 * , . . . , q N * ) is an admissible fully mixed multiaction if q i * ∈]0, 1[ and, if ∆ < 0 it is a GFESS.
Remark 2. Note that every fully mixed GFESS is a strict Nash equilibrium since the condition (3.10) is satisfied for all p i and all i (see Subsection 3.2.1).

Mixed GFESS

We now look for equilibria with both mixed and pure actions. We represent a mixed multiaction by (N X , N Y , q), where group i for i = 1.., N X (resp. i = N X + 1, .., N X + N Y ) uses pure action A (resp. B) and the remaining N -(N X + N Y ) groups adopt a strictly mixed action q i ∈]0, 1[.

Proposition 8. Mixed multiaction in the form (N X , N Y , q) is a GFESS iff:              ∆ < 0 α i ∆ + d -b + α i (c -d) + ∆(α N X + y) ≥ 0, i = 1, .., N X d -b + α i (c -d) + ∆(α N X + y) ≤ 0, i = N X + 1, .., N X + N Y q i = d -b + α i (d -c) -y∆ ∆α i , i = N X + N Y + 1, .., N (3.12
)

where y = (N -N X -N Y )(d -b) + ∆α N X + (d -c) ∑ N j=N X +N Y +1 α j ∆(N -N X -N Y + 1)
.

Proof. Let us consider mixed multiaction (N X , N Y , q). From the condition (3.9), it is a GFESS iff:

     α i ∆ + b -d + α i (c -d) + ∆y > 0, i = 1, .., N X b -d + α i (c -d) + ∆y < 0, i = N X + 1, .., N X + N Y α i ∆q i + b -d + α i (c -d) + ∆y = 0, i = N X + N Y + 1, .., N (3.13)
where y = N ∑ i=1 α j q j . To compute q i , i = N X + N Y + 1, .., N, we add together the N -N X -N Y last equations' left hand sides in (3.13), which gives:

∆y -∆α N X + (N -N X -N Y )(b -d) + (c -d) • N ∑ j=N X +N Y +1 α j + ∆(N -N X -N Y )y = 0, (3.14)
and thus we obtain:

y = (N -N X -N Y )(d -b) + ∆α N X + (d -c) ∑ N j=N X +N Y +1 α j ∆(N -N X -N Y + 1) (3.15)
This agrees with (3.12), completing the proof of the proposition.

Some Examples

In this section we study some examples of games with two group-players and two pure actions. The normalized sizes of the two groups are α 1 = α and α 2 = 1α, with 0 < α ≤ 0.5. We define three different games, where the payoff associated with a pairwise interaction among individuals belongs, respectively, to the anticoordination class, coordination class and pure dominance class of (standard) games. We compute the equilibria as a function of α, in order to understand the impact of the relative size of groups at the equilibrium.

Hawk-Dove Game

We first consider the Hawk-Dove game, defined in (1.8), which belongs to the anticoordination class. We fix the values of the parameters V = 1 and C = 2 and we compute the GFESSs as a function of α ∈ [0, 0.5]. Note that, as ∆ = -1 < 0, the second condition (3.10) is always satisfied, and thus GFESSs and strict NEs coincide. We find that:

• the asymmetric pure multiaction (H, D) is a GFESS for 0 < α < 0.2;

• the asymmetric mixed multiaction (H, q 2 * ) is a GFESS for 0 < α < 0.3;

• the fully mixed (q 1 * (α), q 2 * (α)) is a GFESS for 0.3 < α < 0.5 where, from (3.11):

q 1 * (α) = 2 -3α 6α , q 2 * (α) = 3α -1 6α .
For α ∈ [0, 0.2] the game thus admits two equilibria (H, D) and (H, q 2 * ), whereas, for the other values of α the equilibrium is unique. When α = 0.5, we have q 1 * (α) = q 2 * (α) = 1/6, which corresponds to the symmetric Nash equilibrium obtained in the previous chapter (with δ = 1). The fully mixed equilibrium actions q 1 * (upper line) and q 2 * (lower line), respectively of the first and the second group for 0.3 < α < 0.5 for the two group-players Hawk-Dove game.

Stag Hunt Game

We now consider a well-known example in classical GT, the Stag Hunt game, which belongs to the coordination class. The story behind has been described by Rousseau.

Two individuals go out on a hunt; if they cooperate they can hunt a stag, otherwise, hunting alone, a hunter can only get a hare. The game represents those situations in which collaboration is rewarding for the players and social cooperation is in conflict with safely one. The general payoff matrix of this game is:

S H S a b H c d , with a > c ≥ d > b,
where S and H stand respectively for Stag and Hare. In standard game theory, coordination games admit two strict pure action NEs (which are thus also ESSs), and a non-strict symmetric mixed NE. For the Stag Hunt game theses are, respectively, the risk dominant equilibrium (H, H), the payoff dominant one (S, S)and the mixed NE,

q 1 * = q 2 * = d -b a -b -c + d
, which is not evolutionarily stable.

To study the two group-players game with the above payoff matrix associated with pairwise interactions, we set a = 2, b = 0, c = 1, d = 1. Since ∆ = 2 > 0 the second condition (3.10) for the GFESS is never satisfied, and thus condition (3.9) must be satisfied with strict inequality. This implies that the group-players Stag Hunt game do not admit the fully mixed GFESS. We obtain the following GFESSs:

• the pure symmetric (S, S) and (H, H), for all values of α;

• the pure non-symmetric (S, H) for 0.25 < α < 0.5;

We observe that the ESSs of the standard game are GFESSs of the group-players Stag Hunt game for any value of α, while, in a specific interval of values of α, our game also admits the non symmetric pure GFESS (S, H).

Prisoner's Dilemma

We consider another classical example in game theory, the Prisoner's Dilemma, which belongs to the pure dominance class. The story beyond the game is the following: two criminals are arrested and separately interrogated. They can either accuse the other, either remain silent. If both of them accuse the other (defect), they will be both imprisoned for two years. If only one accuse the other, the accused is imprisoned for three years while the other is free. If both remain silent (cooperate), each of them will serve one year in jail. The general payoff matrix is the following:

C D C a b D c d , with c > a > d > b,
where C and D stand respectively for cooperation and defection. In standard GT, pure dominance class games admit a unique pure, strict and symmetric NE, which is also the unique ESS. For the Prisoner's Dilemma this equilibrium is (D, D). We set a = 2, b = 0, c = 3, d = 1 and we compute the corresponding GFESSs. As in the previous example, condition (3.10) is never satisfied, since ∆ = 0. We obtain that the non-symmetric pure multiaction (D, C) is the only GFESSs for all values of α ∈ [0, 0.5], which means that the smaller group defects and the bigger cooperates.

GFESSs in a Multiple Access Control Game

In this section we introduce a refinement of our model and we apply it to a MAC problem. We modify the group fitness function defined in (3.1) by supposing that the immediate payoff matrix differs if the interacting individuals belong to the same group or to two different ones. The expected fitness function of group G i playing (possibly mixed) action q i ∈ ∆(A) in a population of N groups playing multiaction q = (q 1 , . . . , q N ) ∈ ∆(A) N , is defined as follows:

Γ ′ i (q i , q -i ) := α i J(q i , q i ) + ∑ j =i
α i F(q i , q j ), (3.16) where J(•, •) indicates the immediate expected fitness related to an interaction within a group and F(•, •) is the immediate expected fitness associated with interactions among individuals of different groups. After an ǫ-deviation of group i to action p i the fitness of player G i can be expressed as follows:

Γ ′ i ( pi , q -i ) = Γ ′ i (q i , q j ) + α i ǫ 2 Ω(p i , q i ) + ǫ[α i (J(p i , q i ) + J(q i , p i ) -2K i (q i , q i )) + ∑ j =i α j (J i (p i , q j ) -J i (q i , q j ))],
where pi = ǫp i + (1ǫ)q i and Ω ′ (p i , q i ) := J(p i , p i ) -J(p i , q i ) -J(q i , p i )) + J(q i , q i ).

We define

Ψ ′ i (p i , q) := α i (2J(q i , q i ) -J(p i , q i ) -J(q i , p i )) -∑ j =i α j (F(p i , q j ) -F(q i , q j )) = α i Ω ′ (p i , q i ) -Γ ′ i (p i , q -i ) + Γ ′ i (q i , q -i ), (3.17)
and, as in Proposition 4, we determine the general conditions for a multiaction q = (q 1 , . . . , q N ) to be a GFESS:

• ∀p i ∈ ∆(A): Ψ ′ i (p i , q) ≥ 0,
• If ∃p i = q i ∈ ∆(A) such that:

Ψ ′ i (p i , q) = 0 ⇒ Ω ′ (p i , q i ) < 0

A MAC Game

We now apply this group-players model to a particular MAC problem. We consider a population of mobiles forming a sparse ad-hoc network, where mobiles compete with their neighbors on the access to a radio channel. We suppose that mobiles are randomly placed over a plane, and that they are divided into a finite number N of groups G i , with normalized size α i , i = 1, . . . , N. Mobiles are matched through (both inter-groups and intra-groups) pairwise interactions, where each mobile decides either to transmit (T) or to not transmit (S) a packet to a receiver when they are within transmission range of each other. Interferences occur as in the Aloha protocol: if more than one neighbor of a receiver transmits a packet at the same time then collision occurs and the transmission fails. The channel is ideal for transmission and all errors are due to collisions. Let µ be the probability that a mobile k has its receiver R(k) within its range.

When a mobile k transmits, all mobiles within a circle of radius R centered at node R(k)

cause interference to k for its transmission to R(k), so that more than one transmission within a distance R of the receiver in the same slot causes a collision and the loss of mobile's k packet at R(k). All mobiles in group G i transmits with probability p i ∈ [0, 1], i = 1, . . . , N. If a mobile transmits a packet, it occurs a transmission cost of δ.

R(k) k G 1 G 2 G 3 G 4 p 3 p 4

Figure 3.3:

When a mobile k transmits, all mobiles within a circle of radius R centered at node R(k) cause interference to k for its transmission to R(k), so that more than one transmission within a distance R of the receiver in the same slot causes a collision and the loss of mobile's k packet at R(k). A transmitter in group G i transmits with probability p i ∈ [0, 1], i = 1, . . . , N.

The packet transmission is successful if the other users do not transmit (stay quiet) in that given time slot. If a mobile transmits successfully a packet, it gets a reward of V.

We suppose that the payoff V is greater than the cost of transmission, i.e., δ < V. We denote by γ the probability that a mobile is alone in a given local interaction; the tagged mobile does not know whether there is another transmitting mobile within its range of transmission. Let P 1 (resp. P 2 ) be the matrix representing the immediate fitness of a group when two mobiles belonging to the same group (resp. of two different ones) interact:

P 1 ≡ T S T -2δ 1 -δ S 1 -δ 0 , P 2 ≡ T S T -δ 1 -δ S 0 0 .
The definition of P 1 implies that when two mobiles of the same group G i interact, any successful transmission is equally rewarding for group i. When two of mobiles in group G i interact and play q i ∈ [0, 1], the expected fitness of G i is:

J(q i , q i ) = µ q i [γ(1 -δ) + (1 -γ)((1 -δ)(1 -q i ) -2δq i )] + (1 -γ)(1 -δ)(1 -q i )q i = µq i [(1 -δ)(2 -γ) -2(1 -γ)q i ]. (3.18)
If a mobile in G i interacts with a mobile in a different group G j playing q j ∈ [0, 1], its expected payoff is the following:

F(q i , q j ) = µq i [γ(1 -δ) + (1 -γ)((1 -δ)(1 -q j ) -δq j ] = µq i [1 -δ -(1 -γ)q j ] (3.19)
The total expected payoff of G i is then given by:

Γ ′ i (q i , q -i ) = µq i [1 -δ + (1 -γ)(α i (1 -δ -q i ) - N ∑ j=1 α j q j )] (3.20)
The multiaction q is a GFESS of the group-players MAC game if ∀i = 1, . . . N:

Ψ ′ i (p i , q) ≡ (q i -p i )[1 -δ + (1 -γ)(α i (1 -δ -2q i ) - N ∑ j=1 α j q j )] ≥ 0.
Note that, in this game, the condition Ω ′ (p i , q i ) < 0 reduces to (p iq i ) 2 (1γ)α i > 0. Since the latter inequality is always true, the second condition is always satisfied and thus the first condition is sufficient to guarantee the existence of a GFESS. In the following proposition we give a characterization of the GFESSs of the presented MAC game. Without loss of generality, we reorder the groups so that α 1 ≤ α 2 . . . ≤ α N . Proposition 9. We find that:

i. The pure symmetric multiaction (S, . . . , S) is never a GFESS.

ii. If a fixed group G i adopts pure action T, then if i < N, at the equilibrium all smaller groups transmit. If i = N, i.e. the bigger group G N uses action T at the equilibrium, then (T, . . . , T) is an equilibrium iff γ > γ.

iii. If a fixed group G i adopts pure action S, then at the equilibrium, all smaller groups also use S.

iv. The game admits a unique fully mixed GFESS q * = (q 1 * , . . . , q N * ), given by:

q i * = (1 -δ)(1 + γ + (1 -γ)(2 + N)α i ) 2(N + 2)(1 -γ)α i (3.21)
under the condition: γ < γ.

v. If a fixed group G i adopts a mixed action q i ∈]0, 1[, then if q i > 1δ 2 , at the equilibrium all smaller groups may use pure action T, whereas if q i < 1δ 2 , smaller groups may play S.

The thresholds γ and γ are defined as follows:

γ ≡ min α i α i (N + 2)(1 + δ) -(1 -δ) α i (N + 2)(1 + δ) + (1 + δ) , γ ≡ max α i 1 - 1 -δ α i (δ + 1) + 1 .
Proof. The multiaction q = (q 1 , . . . ,

q N ) ∈ [0, 1] N is a GFESS if ∀i = 1, . . . , N, the condi- tion Ψ ′ i (p i , q) ≥ 0 is verified ∀p i ∈ [0, 1].
i. If, ∀i = 1, . . . , N q i = 0, then

Ψ ′ i (p i , 0) = -p i [1 -δ + (1 -γ)(1 -δ)α i < 0 ∀p i ∈ [0, 1],
which proves that (S, . . . , S) is never a GFESS.

ii. Let q be a GFESS such that q i = 1 for a fixed i. This implies that

1 -δ -(1 -γ)(α i (1 + δ) + Y] ≥ 0, with Y = N ∑ j=1 α j q j ). Then, if α j < α i we have that 1 -δ -(1 -γ)(α j (1 + δ) + Y] ≥ 1 -δ -(1 -γ)(α i (1 + δ) + Y] ≥ 0
and thus q j = 1 satisfy the GFESS condition. If all the groups transmit, then the condition for the GFESS is satisfied iff:

1 -δ -(1 -γ)((1 + δ)α i -1) ≥ 0 ∀i = 1, . . . , N and thus γ ≥ 1 - 1 -δ α i (δ + 1) + 1 , ∀i.
iii. Let q be a GFESS such that q i = 0 for a fixed i. This implies that

1 -δ + (1 -γ)(α i (1 -δ) -Y] ≤ 0. If α j < α i , then: 1 -δ + (1 -γ)(α j (1 -δ) -Y] ≤ 1 -δ + (1 -γ)(α j (1 -δ) -Y] ≤ 0 and thus Ψ ′ j (p i , q) ≥ 0.
iv. Let q be a fully mixed GFESS. Then, ∀i:

1 -δ + (1 -γ)(α i (1 -δ -2q i ) -Y) = 0.
After some algebra we thus obtain that Y = (1

-δ)(N + 1 -γ) (1 -γ)(N + 2)
, and by substituting it in the previous equations we obtain the expressions of q i . By imposing that 0 < q i < 1 ∀i we obtain the condition γ < γ.

v. Let q be a GFESS such that q i ∈]0, 1[ for a fixed i. Then, if for a j < i, q j = 0 (resp.

1), Ψ ′ j (p i , q) ≥ 0 iff q i > 1 -δ 2 (resp. q i > 1 -δ 2 ).
As an example, we consider a two groups MAC game, in which we fix a low value of the cost of transmission, δ = 0.2, and we study the equilibria as a function of the value of the parameter γ, which is the probability that the transmitter is alone. We first set α = 0.5 and we obtain that, for γ < γ = 0.35 the game admits a fully mixed symmetric GFESS (q * , q * ). In figure 3.4 we compare q * to the value of the equilibrium in the corresponding individual-players game: q * std := min(1, 1 1γ -∆), and we observe that q * is lower than q * std . Let p S (q) be the probability of a successful transmissions in a population under profile q. For N = 2, it equals:

p S (q) := µ[γ(αq 1 + (1 -α)q 2 )] + (1 -γ)(2α 2 q 1 (1 -q 1 )+ + α(1 -α)((1 -q 2 )q 1 + (1 -q 1 )q 2 ) + 2(1 -α) 2 q 2 (1 -q 2 ))].
In figure 3.5 we plot the probability p * S = p S (q * ) of a successful transmission in a population under the equilibrium (q * , q * ) as a function of γ for α = 0.5. We note that the probaility to transmit successfully is higher for the two group players game than in the standard case. We then set α = 0.4, to consider an asymmetric case, where the two groups have different sizes. For γ < γ = 0.3 the game admits a fully mixed GFESS (q 1 * , q 2 * ), and for γ = γ > 0.53, the game admits a pure symmetric equilibrium (T, T). These equilibria are plotted in 3.6. In the interval 0 ≤ γ < 0.4 we also have a GFESS in the form (T, q T * ).

In figure 3.7 we plot the equilibrium actions of the second group q T * and q 2 * , and we observe that the latter is lower than q T * , i.e. the probability that the second (bigger) group transmits at the equilibrium is higher if the first group plays pure action T than if it plays mixed action q 1 * . The value of the equilibrium strategy of the second group in the fully mixed equilibrium (q 1 * , q 2 * ) and in the mixed equilibrium (T, q T * ) as a function of γ for α = 0.4.

Conclusion

In this chapter we presented a new concept of evolutionary stability in the groupplayers framework, the GFESS, implying stability against local deviations within each group. While the ESS in standard EGT is a refinement of the Nash equilibrium, the GFESS can be seen as a strict local Nash (in the group context), which is stable against local deviations within a group. For the particular case of two pure actions games, we provided a characterization of the GFESSs, distinguishing between pure, fully mixed and mixed GFESS, and we studied three classical examples considering group players:

the Hawk-Dove game, the Stag Hunt game and the Prisoner's Dilemma. By computing the equilibria as functions of the size of the groups, we saw how the presence of groups impacts the equilibrium output. We then introduced a slightly different situation by redefining the fitness of a group, where the immediate payoff associated with the pairwise interactions among individuals in the same group differs from that of inter-group interactions and we applied this model to a MAC problem.

Chapter 4

Markov Decision Evolutionary Games

"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas. A painter makes patterns with shapes and colours, a poet with words. [. . . ] A mathematician, on the other hand, has no material to work with but ideas, and so his patterns are likely to last longer, since ideas wear less with time than words. The mathematician's patterns, like the painter's or the poet's must be beautiful; the ideas like the colours or the words, must fit together in a harmonious way. Beauty is the first test: there is no permanent place in the world for ugly mathematics."

G.H. Hardy, A Mathematician's Apology, 1940

Summary

In this chapter we briefly introduce Markov Decision Evolutionary Games (MDEG), which combine Markov Decision Processes and Evolutionary Game Theory. These games involve a large population of players characterized by an individual state and randomly matched in pairwise interactions. The fitness of an individual depends on the actions played in the interaction and on the distribution of the individual states in the population. The action taken by a player also determines the transition probabilities to its next individual state. Players aim at maximizing the average sum of their immediate expected fitness during their finite life time. Under certain assumptions, it is possible to transform this game into a standard evolutionary game and find its equilibria.

Introduction

In this chapter we present a particular class of stochastic evolutionary games, Markov Decision Evolutionary Games (MDEG), as defined by Altman and Hayel [START_REF] Altman | Markov decision evolutionary games[END_REF]. In MDEG games, each player belonging to a large population is associated with an individual state. During its finite life time the player meets several times other users through random pairwise interactions and it may move among different states. The actions played by an individual determine not only its immediate fitness but also the transition probabilities to its next state. The objective of a player is the maximization of its expected immediate fitness during its life time, which depends also on the distribution of individual states in the populations. Following a method similar to that used in [START_REF] Filar | A matrix game solution of the single-controller stochastic game[END_REF] for one controller, the authors transform this game into an equivalent standard evolutionary game and they study its ESSs.

State of Art

Stochastic games have been first introduced by Lloyd Shapley [START_REF] Shapley | Stochastic games[END_REF]. He models a play which proceeds by steps from "position" to "position" (state to state), according to transition probabilities jointly controlled by two players. Each state (or position) corresponds to a specific matrix game and the transition probabilities from one position to the other are determined by the current matrix game and by the actions used by the two players. The transition function considered is time homogeneous and players' evaluation of sequences of payoffs have a stationary structure. The author proves the existence of optimal stationary strategies.

Stochastic games belongs to the wider class of sequential games, which are processes generating a sequence of one-shot, non-cooperative games played by the same set of players. The transition probabilities which determine the game to be played at any time t + 1 are functions of t, the game played at t, and the actions chosen at t. A stochastic game is thus a sequential game where these transition functions are stationary and the players' evaluations of the sequences of payoffs have a stationary structure. Jovanovic and Rosenthal [START_REF] Jovanovic | Anonymous sequential games[END_REF] define anonymous sequential games as processes of one-shot, non-cooperative games with a continuum of players, where individuals affect their opponents only when aggregated, ad not at an individual level.

While in stochastic games the notion of state is associated with the system, Jovanovic and Rosental relate it to individuals. Furthermore, they look at equilibria composed of "distributional strategies" (which are sequences of state-action distributions) and therefore they do not restrain to the stationary state of the system. After proving that every anonymous sequential game admits an equilibrium, they also consider the stationary case, where the utility and the transition probabilities do not depend on time.

Flesch et al. [START_REF] Flesch | Evolutionary Stochastic Games[END_REF] unify stochastic games as defined by Lloyd Shapley and EGT into stochastic evolutionary games, which are described as irreducible two-person stochastic games with symmetric payoff matrices and symmetric transition probabilities. At each stage of the game, two players belonging to a large population interact with each other in one of finitely many environments. The transition probabilities between the environments determine the impact of each of these environments on the fitness of the individuals. Under the irreducible transition law assumption, the authors extend the notion of evolutionary stability in terms of stationary strategies and define the replicator dynamics in this multi-state framework. In contrast with [START_REF] Flesch | Evolutionary Stochastic Games[END_REF], the notion of state in MDEG has an individual connotation, as in [START_REF] Jovanovic | Anonymous sequential games[END_REF], but transition probabilities and policies are assumed to be stationary.

Stochastic games and Markov Decision Processes (MDP), are both two suitable mathematical structures for the classes of dynamic, stochastic, decision models. Filar and Vrieze [START_REF] Filar | Competitive Markov Decision Processes[END_REF] present the theories of stochastic games and MDP in a complete unified fashion, and by defining Competitive Markov Decision Processes, they emphasize the importance of the link between these two topics extensively studied by mathematicians, engineers and economists.

The mutations in a population modeled by standard EGT are random deviations, which means that the notion of randomness is somehow implied by the requirement of evolutionary stability. However, since the population considered is large, evolutionary games can be thought as continuous deterministic approximations of discrete stochastic games, where a finite set of players may take random actions.

Tembine et al. [START_REF] Tembine | Mean field asymptotic of Markov Decision Evolutionary Games[END_REF] analyze the connection between stochastic and deterministic evolutionary games, studying the mean-field asymptotic of MDEG. More precisely, they define a finite population game, called mean field interaction, in which, at each stage, each individual interacts with other randomly selected players, and thus interactions may involve more than two individuals. The states and the actions of each player in an interaction determine the instantaneous payoff for all the players involved. Actions also determine the transition probabilities to the next state of the players involved in the interactions. The authors provide a rigorous derivation of the asymptotic behavior of this system when the size of the population grows to infinity and they show that the large population asymptotic of the mean field interaction is equivalent to a MDEG in which a local interaction is described by a single player against a population profile.

In what follows, we first give some basic notions of Markov Decision Process (MDP) and we then introduce MDEG as presented in [START_REF] Altman | Markov decision evolutionary games[END_REF], focusing on the notion of occupation measure and that of equivalence between policies.

Markov Decision Process

A Markov Decision Process (MDP) can be identified by the tuple {S, A, Q}, where:

• S is the finite set of individual states, with |S| = K;

• A is the set of available actions. For each state s ∈ S, A s ⊆ A is the subset of available actions for a player in state s.

• Q is the set of transition probabilities . Given the individual states s, s ′ ∈ S and the actions a, a ′ ∈ A, Q t s ′ (s, a, a ′ ) denotes the probability to move from state s to state s ′ taking action a when interacting with an individual that takes action a ′ at time t.

In what follows we restrain to time homogeneous transition probabilities, which do not depend on t, and we also suppose that they only depend on the player's action (a) and not on that of its opponent (a ′ ). A policy u = {u 0 , u 1 , u 2 , . . .} of a player is a sequence of probability measures on A chosen as functions of the present state of the player and on the history of its previous states and actions. That is, u 0 = u 0 (η), where η is the initial state and u t+1 = u t+1 (h t , s t+1 , ), where s t+1 is the state at time t + 1 and h t is the state-action history of the player until time t: h t := (s l , a l , l = 0, . . . , t) t = 0, 1, 2, . . . (4.1)

Let H be the set of all possible states-actions histories which can be observed, and U the set of all policies. We further define the following particular classes of policies:

• U M is the set of Markov policies of a player such that, at every moment t of decision making, the probability measure u t on A is chosen as a function of the current moment of time and the current state of the player (ad not on the past history);

• U S is the set of stationary policies, which are such that at any moment t, the probability measure u t on A is chosen only as a function of the current state of the player (and not of the current moment of time);

• U D is the set of deterministic policies , (also called pure stationary policies) which 56 4.2. Markov Decision Process assign an action to each state.

Occupation measures

In MDEG each player belonging to a large population is associated with a MDP and the actions played are supposed to determine the fraction of time the player spends in each state. This implies that the share of the population at a given state may depend on the distribution of strategies in the population. In order to model this dependence, we need to define the concept of occupation measure, which describes the expected amount of time that an individual spends in a given state under a given policy.

Denote by f η,u (s, a) the expected number of time units during which a player is in state s and chooses action a under policy u, given the initial distribution η. The occupation measure corresponding to policy u is the quantity:

f η,u := { f η,u (s, a)}.
Let us now define the probability that an individual is in state s using action a under policy u at local time t, given the initial state probability distribution η:

p t (η, u; s, a) := P u η (X t = s, A t = A).
Note that, since the population is supposed to be totally symmetric, this initial distribution, at local time 0, is the same for all individuals. Define: p t (η, u; s) := ∑ a∈A p t (η, u; s, a).

Note that it's a sub-probability measure, as ∑ s p t (η, u; s) may be smaller than one. We have that:

f η,u (s, a) = ∞ ∑ t=0 p t (η, u; s, a), f η,u (s) = ∞ ∑ t=0 p t (η, u; s). (4.
2)

The lifetime of an individual is identified as the time interval before X t leaves S; the expected life-time (corresponding to initial state η and policy u) is thus defined as:

T η,u = ∑ s f η,u (s).
For a given initial state η, sup u∈U T η,u is assumed to be finite. From [START_REF] Kallenberg | Linear Programming and Finite Markovian Control Problems[END_REF],

sup u∈U T η,u = max u∈U D
T η,u , which means that this assumption is equivalent to requesting that the expected lifetime is finite for all deterministic policies.

From the theory of MDP, if all players use an equilibrium stationary policy u s ∈ U S , then no player can benefit by a unilateral deviation to any policy, including non-stationary ones. Hence u s is an equilibrium among all policies and, with no loss of generality, it is possible to restrain to the set U S .

Markov Decision Evolutionary Games

MDEG combine MDP and EGT into a new game theoretic framework. Consider, as in standard EGT, a large population of players, randomly matched in pairwise interactions. Each player is characterized by an individual state, such that the fitness of a player does not depend only on the actions chosen in the interactions, but also on this individual state. The action taken by a player determines the transition probability to its next individual state. Each player is thus associated with a MDP, where the transition probabilities Q are time homogeneous and depend only on the action of the player (and not on the action chosen by its opponent).

Let r(s, a, s ′ , a ′ ) be the immediate fitness that a player receives when it is in state s and uses action a in an interaction with a player who is in state s ′ and uses action a ′ . When the whole population uses a stationary policy u ∈ U S , then at any time t (which is either fixed or is an individual time of an arbitrary player) the state of the system is independent of t. For all (s, a) ∈ S × A S , the fraction of the population in stationary regime in individual state s, that uses action a when all the population uses stationary policy u is given by:

α(u; s, a) = f η,u (s, a) T η,u . (4.3)
Then, the stationary system state is:

α(u) = {α(u; s, a)}. (4.4)
Denote by r(u; s, a) the immediate reward that a player receives when it is in state s and it uses action a while interacting with a player whose policy is u. We have that:

r(u; s, a) = ∑ (s ′ ,a ′ ) α(u; s ′ , a ′ )r(s, a, s ′ , a ′ ).
Consider an arbitrary tagged player and let X t and A t be respectively its state and 4.3. Markov Decision Evolutionary Games action at time t (as measured on its individual clock). Then its expected immediate reward at that time is given by R t (u) = r(u; X t , A t ).

Assume now that a player arrives in the system at time 0. The global expected fitness of a player choosing a policy v in a population whose policy is u is then:

F η (v, u) = ∞ ∑ t=0 E η,v [R t (u)]
When η is concentrated on state s we write with some abuse of notation F η (v, u) = F s (v, u), and when η is fixed, the index is omitted. When the system is in its stationary state, the global expected fitness simplifies to:

F η (v, u) = ∞ ∑ t=0 E η,v [R t (u)] = ∑ (s,a) f η,v (s, a) T η,u ∑ (s ′ ,a ′ ) f η,u (s ′ , a ′ )r(s, a, s ′ , a ′ ) (4.5)
Remark 3. Equation (4.5) would not hold if the policy of a player could depend on the absolute time or on the behavior (i.e. on the actions) of other players. On the other hand, since players are not distinguishable, and since the lifetime distribution of a mobile depends only on its local time, we may expect equation (4.5) to hold.

Two policies v and v ′ are said to be equivalent if the corresponding occupation measures coincide. We shall write v = e v ′ . Note that if v and v ′ are equivalent policies for a given player, then for any policy u used by the rest of the population, the fitness expressed by equation (4.5) under v and under v ′ are the same. Indeed, the fitness depends only of the policy used through the occupation measures.

By considering the expression (4.5) for the fitness, Altman and Hayel [START_REF] Altman | Markov decision evolutionary games[END_REF] define the ESS in a MDEG framework. The authors further define the modified global expected fitness function: In Chapter 6 we study a simple Hawk-Dove game in MDEG framework, where, in contrast to what we presented here, the transition probabilities of a player may depend on the action of the opponent it interacts with and not on its action.

Fη (v, u) = ∑ (s,a) f η,v (s, a) ∑ (s ′ ,a ′ ) f η,u (s ′ , a ′ )r(s, a, s ′ , a ′ ),

Introduction

In the previous chapter we presented MDEG models, introduced by Altman and Hayel [START_REF] Altman | Markov decision evolutionary games[END_REF], where each player is associated with an individual state.

During its finite life time the player meets several times other users through random pairwise interactions and it may move among different states. The actions played by an individual determine its immediate fitness and the transition probabilities to the next state. The evolution of states is thus described by a discrete time MDP. In contrast with

Altman and Hayel, who transform the problem into an equivalent standard evolutionary game and look for its ESS, we study here the dynamics involved in the game. We consider both the local dynamics of individual states and the dynamics intrinsically related to the global evolution of the distribution of policies in the population, which are described by interdependent differential equations. Individuals are thus assumed to control a CT-MDP instead of a discrete time one. We give some general results about the convergence of the coupled dynamical system to an equilibrium of the population game. We deepen the analysis of the convergence of the coupled dynamics in a particular case with two states and two actions, for which we propose two different approaches to the problem.

State of Art

Evolutionary games can be interpreted as a branch of dynamical systems through the replicator equations (see e.g. [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF]), which represents an important foundations for understanding individuals' behaviors in a population. In the last years the relationship between evolutionary dynamics and learning algorithms has been investigated. In [START_REF] Borgers | Learning through reinforcement and replicator dynamics[END_REF], for example, the authors analyze the "Cross' learning process", which is a simple learning model where a player updates its action only on the basis of its own action and on the fitness it gets (and not on the others' actions). They prove that, in a particular case, this dynamics converges to the replicator dynamics. The authors also provide a discussion on the relation between learning and evolution, comparing the interpretation of the stochastic game underlying Cross' learning process model, and the deterministic population game underlying the replicator dynamics. In [START_REF] Beggs | On the convergence of reinforcement learning[END_REF], the author investigates the convergence of fitness and strategies in another similar model of reinforcement learning, the "Erev and Roth's model". The author shows that in a two-person constant-sum game, when both players learn according to Erev and Roth's rule, the long-run behavior of the system is related to a system of equation similar to the 'adjusted replicator dynamic' introduced in (Maynard [START_REF] Smith | Evolution and the theory of Games[END_REF].

In general, a learning procedure describes how each individual adapts its action based on the information it has, like its own fitness, average fitness, historical actions of the others, probabilistic beliefs on the other actions, etc. An analysis of level of information under learning processes in games is given in [START_REF] Fudenberg | Theory of Learning in Games[END_REF]. As already mentioned in Section 1.3, many different learning algorithms/dynamics have been proposed in the game theory literature, like Brown-Nash-Von Neumann, logit dynamics, etc. All these dynamics can be generalized to the notion of revision protocols [START_REF] Sandholm | Population Games and Evolutionary Dynamics[END_REF] which define a general rule ("compare and innovate", "target and innovate", "compare and non-innovate", etc.) followed by individuals (see Section 1.3 for more details).

Motivations and Applications

Our model finds its first motivation in the study of optimal power control policies in wireless networks (Altman and Hayel, 2008) (see the Introduction to the previous chapter). In Information and Communications Technology, it can be used to study social networks applications, crowd sourcing and Internet of Things (IoT). Emerging applications in engineering such as crowd-sourcing and (mis)information propagation, for example, involve a large population in a complex network of heterogeneous users or agents, who strategically make dynamic decisions. These agents interact with each other in a complex environment, in which each individual takes strategic and dynamic decisions in response to the agents it interacts with. In all these applications, the action set of each agent depends on a local state. In social networks, for example, each agent may decide to add/remove friends/news based on its own current status. Its decision impacts its own status dynamics but also the interaction with other agents.

In IoT, a sensor has to determine when to upload its information to the fusion center.

This decision impacts its battery level but also the communication quality as collisions may occur for example. As pointed out in several references cited above, the replicator dynamics equations are related to several learning algorithms that can be implemented in such sensors or actuators in IoT. Then, by studying these equations, we can understand the convergence behavior of decentralized algorithms that can be used in such applications.

This chapter is organized as follows: in Section 5.2 we introduce our evolutionary game model that takes into account an individual state dynamics coupled to the policies ones.

A complete characterization of the coupled dynamical system is performed in Section 5.3, for a particular two states and two pure actions game. By assuming that the two dynamic processes evolve with different velocities, in Subsection 5.3.6 and 5.3.7 we find the equilibria of the game through two different techniques: the singular perturbation method and by rewriting the problem as a matrix game. We then compare the two solutions obtained and we prove that they are equivalent in terms of fitness and average sojourn time. Some applications in network systems are proposed in Section 5.3.9.

General Model

The Individual State Dynamical Model

We consider here a population game in which each individual controls a Continuous Time Markov Decision Process (CT-MDP) (Guo and Hernandez-Lerma, 2009). Let S be the finite individual state space of players, with |S| = K. We suppose that each player disposes of the same finite set of actions, A, with |A| = M. CT-MDP are defined through the set of transition rates R, which describe the rate of the process' transitions from one state to another. More precisely, we denote by R s (s ′ , a) the transition rate from state s ′ to state s given action a, which satisfies R s (s ′ , a) ≥ 0 for all s ′ ∈ S, s ′ = s, and a ∈ A. These quantities are conservative, i.e.

∀s ′ ∈ S, ∀a ∈ A, ∑ s R s (s ′ , a) = 0.
Also the transition rates are stable, i.e.

sup a∈A R s ′ (a) < ∞, ∀s ′ ∈ S with R s ′ (a) := -R s ′ (s ′ , a) ≥ 0.
Since the set of actions is finite, the stability of the transition rates is guaranteed. Note that the transition rates of a player only depend on its actions, and not on the others' ones.

In standard evolutionary games, each individual plays a pure action, whereas in our framework, individuals choose a deterministic policy in the finite set U D = {u 1 , . . . , u D } (see the definition in Section 4.2 for the definition of U D ).

The choice of a policy determines the time spent by each individual in each state. Indeed, for any state s ′ and action a, the sojourn time in state s ′ is a random variable which follows an exponential distribution with parameter R s ′ (a) = ∑ s =s ′ R s (s ′ , a). Then, under a given deterministic policy u j ∈ U D , as there is a unique action a = u j (s ′ ) associated with each state s ′ , such that u j (a|s ′ ) = 1, the time spent in any state s ′ for any individual choosing this policy, follows an exponential distribution with parameter R s ′ (a) = R s ′ (u j (s ′ )). This implies that the fraction of individuals in a given state depends on the distribution of policies over the population. This fraction is important to define the fitness obtained for each individual at each pairwise interaction. Given a deterministic policy u j ∈ U D and a state s ∈ S, we denote by T s (u j ) the average sojourn time that an individual playing policy u j spends in state s, which is given by:

T s (u j ) = 1 R s (u j (s))
.

Note that a general sojourn time distribution could also be considered, but we consider the exponential distribution, in order to obtain closed-form solutions of the equilibrium Markovian policy of the defined game.

Population of Players

Let us consider a fixed population of N players, where each one controls a CT-MDP, with S, A and R respectively the finite set of states, actions, and transition rates. Let ∆(A) be the set of distributions over A. We define the proportion of individuals (decision makers) that are in state s ∈ S at time t as w N s (t

) := 1 N N ∑ l=1 1 {s l (t)=s}
, where 1 is the indicator function, i.e. 1 {s l (t)=s} = 1 if the state of player l at time t is s, and it equals zero otherwise. For each state s, we denote by Y l s (t) the probability that an individual l is in state s at time t under a deterministic policy u ∈ U D , i.e. Y l s (t) = P u s 0 (s l (t) = s), where s 0 is the initial state. Then, from Assumption 1, P u s 0 does not depend on s 0 and, from the law of large numbers, when the size of the population grows to infinity, then Y l s (t) can be approximated by the proportion of individuals in state s at time t, given by w s (t) = lim N→∞ w N s (t). This means that the individual state dynamics, corresponds to the dynamics of the proportion of individuals in state s in the global population. Let S = {s 1 , . . . , s K } and w i = w s i . We further suppose that the individual dynamics also depends on the policies and that, for any state s i ∈ S, there exists a Lipschitz function h i which describes the dynamics of w i as follows:

ẇi (t) = h i (w(t), q(t)), ∀s i ∈ S, (5.1)
where w(t) = (w 1 (t) . . . , w K (t)) is the vector of state probabilities and q(t)=(q 1 (t) . . . , q D (t))

is the vector of distribution over the deterministic policies in the population, such that q j (t) indicates the proportion of individuals playing deterministic policy u j ∈ U D = {u 1 , u 2 , . . . , u D } at time t. Indeed, we have seen previously that the choice of a such policy has an impact on the state dynamics of this individual.

Policies Dynamics

We assume that the proportion of individuals choosing each deterministic policy is evolving over time as a dynamical process. Without specifying any revision protocol, we define the dynamics of policies through a set of Lipschitz continuous functions G := {g 1 , . . . , g D }, such that: qj (t) = g j (w(t), q(t)) ∀u j ∈ U D .

(5.2)

Then, the dynamical evolution of states and policies distributions in the population is represented by a system of K + D equations:

                       ẇ1 = h 1 (w(t), q(t)) . . . ẇK (t) = h K (w(t), w(t)) q1 (t) = g 1 (w(t), q(t)) . . . qD (t) = g D (w(t), q(t)) (5.3)

Two Time-Scales Behavior

We assume that the state and the policy dynamics move with different velocities. By supposing that the individual state dynamics move much faster then the slow updating policies processes, we can consider the singular perturbation model [START_REF] Kokotovic | Singular perturbation methods in control[END_REF], briefly presented in what follows, to find the rest points of the system (5.3). We first introduce Assumption 1, which assures that, under any deterministic policy, there exists a stationary distribution over the individual states which does not depend on the initial state. Assumption 1. Under any deterministic policy, the stochastic process of the individual states forms an ergodic Markov chain.

Singular Perturbation Method

The singular perturbation model of finite dimensional systems has been extensively studied in mathematical literature (see e.g. [START_REF] Levinson | Perturbations of discontinuous solutions of non-linear systems of differential equations[END_REF] [START_REF] Hoppensteadt | Stability in systems with parameters[END_REF][START_REF] O'malley | Boundary layer methods for nonlinear initial value problems[END_REF]) and it was the first method used in control theory as a tool to simplify dynamic models. Following Kokotovic's approach [START_REF] Kokotovic | Singular perturbation methods in control[END_REF], we provide here the basic concepts of singular perturbation asymptotics and time-scale modeling that will be used in the next section. Consider the interdependent dynamics: ẋ = g(x, z, u, ǫ, t), x(t 0 ) = x 0 , x ∈ R n , (5.4) (5.5) where u is the control vector, ǫ is a small scalar and g and h are sufficiently many times continuously differentiable functions of their arguments. To reduce the order of the system (5.4)-(5.5), the parameter ǫ is perturbed: when ǫ equals zero, the order of the system reduces from n + m to n, since equation (5.5) degenerates into the trascendental equation 0 = g( x, z, ū, 0, t).

ǫ ż = h(x, z, u, ǫ, t), z(t 0 ) = z 0 , z ∈ R m ,
(5.6)

The system is said to be in normal or standard form if and only if the following assumption is satisfied: Assumption 2. In a domain of interest, equation (5.6) has k ≥ 1 distinct roots:

z = ϕ i ( x, ū, t), i = 1, 2, . . . , k (5.7)
This assumption assures that a well defined (n-dimensional) model correspond to each root. To obtain the i reduced model, one need to substitute z into (5.4) to get the quasisteady-state model: ẋ = g( x, ϕ i ( x, ū, t), ū, 0, t) = g( x, ū, t).

(5.8)

The velocity of z, given by g/ǫ, is large when ǫ is small and thus z may rapidly converge to a root of (5.6), which is the quasi-steady-state of (5.5). Singular perturbation thus generates a two time-scale behavior of the dynamic system (5.4)-(5.5): the slow process is approximated by the reduced model (5.8), while the discrepancy between the original system and (5.8) is the fast transient. We now investigate the relation between the original variable z and z. Note that the initial value of z may be far from z 0 , as it is given by

z(t 0 ) = ϕ( x(t 0 ), ū(t 0 ), t 0 ) = z 0 .
We can expect that z is well approximated by z in a sub-interval [t 1 , T], where t 1 > t 0 , i.e.:

z = z(t) + O(ǫ), ∀t ∈ [t 1 , T].
(5.9) However, it is possible to constrain the quasi-steady state x to start from x 0 to have:

x = x(t) + O(ǫ), ∀t ∈ [t 0 , T].
(5.10)

We introduce a new time variable to study the behavior of the variable z. Let

ǫ dz dt = dz dτ ⇒ dτ dt = 1 ǫ ,
and τ = 0 when t = t 0 . The new time variable

τ = t -t 0 ǫ , τ = 0 at t = t 0
is stretched, that is, τ goes to infinity when ǫ goes to zero. We define the boundary layer system which describes z as a function of τ: (5.11) where x 0 and t 0 are fixed parameters. We thus obtain that: (5.12) where z(t) is the slow and ẑ(τ) -z(t 0 ) the fast transient of z. Two assumptions are needed to guarantees the validity of the approximations (5.9) and (5.12).

d ẑ dτ = g(x 0 , ẑ(τ), u, 0, t 0 ), ẑ(0) = z 0 ,
z = z(t) + ẑ(τ) -z(t 0 ) + O(ǫ),
Assumption 3. The equilibrium z(t 0 ) of (5.11) is asymptotically stable uniformly in x 0 and t 0 , and z 0 belongs to its domain of attraction, so ẑ(τ) exists for τ ≥ 0.

This implies that lim τ→∞ ẑ(τ) = z(t 0 ) uniformly in x 0 and t 0 and thus z is close to its quasisteady-state z for t 1 > t 0 . The interval [t 0 , t 1 ] can be made arbitrarily short my making ǫ sufficiently small. Assumption 4. The eigenvalues of ∂g/∂z evaluated along x(t), z(t), ū(t) for all t ∈ [t 0 , T] have real parts smaller than a fixed negative number, i.e.:

ℜλ ∂g ∂z ≤ -c < 0.
Note that, if z 0 is assumed to be sufficiently close to z(t 0 ), then Assumption 4 is stronger than Assumption 3. Furthermore, Assumption 4 implies that the root z(t) is distinct as required by Assumptios 2. We can now state the main result, often called Tikhonov theorem. Theorem 4. [Theorem 3.1 (Kokotovic et al., 1986)] If Assumptions 3 and 4 are satisfied, then the approximations (5.10) and (5.12) are valid for all t ∈ [t 0 , T], and there exists a t 1 such that (5.9) is valid for all t ∈ [t 1 , T].

For the proof of this result, see e.g. [START_REF] Levinson | Perturbations of discontinuous solutions of non-linear systems of differential equations[END_REF], [START_REF] Hoppensteadt | Stability in systems with parameters[END_REF].

Fast state and slow policy processes

In order to describe the two time-scales behavior of the system (5.3), we introduce the small positive parameter ǫ > 0:

                       ǫ ẇ1 = h 1 (w(t), q(t)) . . . ǫ ẇK (t) = h K (w(t), q(t)) q1 (t) = g 1 (w(t), q(t)) . . . qD (t) = g D (w(t), q(t))
(5.13)

Then, the velocity of the state process, ẇi = h i (w, q)/ǫ, is fast when ǫ is small, which means that the states dynamics may rapidly converge to its steady-state. From the singular perturbation theory, if the assumptions introduced above are satisfied, one can solve the reduced model and easily find a good approximation of the solution of the original system (5.3). When supposing the two time-scales behavior of the states and policies dynamic system, an alternative technique to find a solution of (5.3) consists in considering the stationary distribution of states and then solve the policies dynamics.

Let r(s, a; s ′ , a ′ ) be the immediate fitness that a player gets when it is in state s and plays action a against an individual in state s ′ using action a ′ . When the distribution of the individual states is stationary, we denote by F(u i , u j ) the immediate expected fitness of a player using deterministic policy u i ∈ U D against a population playing u j ∈ U D . It can be defined as a function of the average sojourn times as follows: [START_REF] Puterman | Markov Decision Processes[END_REF] [START_REF] Ibe | Markov Processes for Stochastic Learning[END_REF]), which makes the total transition rate from a state the same for all states and allows to consider the discrete time MDP embedded at transition epochs of each event. But, since we focus here on the replicator dynamics and not on the equilibria of the game, we study the MDEG in continuous time, where each individuals control their transition rates.

F(u i , u j ) = ∑ s,s ′ ∈S T s (u i ) ∑ s ′ T s ′ (u i ) r(s, u i (s); s ′ , u j (s ′ )) T s ′ (u j ) ∑ s ′ T s ′ (u j ) . ( 5
Once we have defined the expected fitness function, we assume that each individual chooses its deterministic policy in order to maximize its immediate expected fitness and we then define a stationary equilibrium u * policy for our continuous-time MDEG problem. Definition 6. Under the Assumption 1 and assuming that the distribution over the states is time homogeneous, a policy u * ∈ U D is a deterministic equilibrium policy if, ∀ u j ∈ U D :

F(u * , u * ) ≥ F(u j , u * ).
Note that, from Assumption 1, if a deterministic policy u * is optimal, than no player can benefit from unilateral deviations to any policy, including non deterministic ones.

Hence , if all population uses an equilibrium among stationary policy, then no player can benefit by a unilateral deviation to any policy. We have seen in Section 1.3.2 that, in standard evolutionary game theory, there is a relation between equilibria of a game and rest points of the replicator dynamics. We can establish a similar relationship in our setting. Given the vector of policies distributions at time t, q(t) = (q 1 (t), . . . , q D (t)),

we denote by F(u k , q) := ∑ u j ∈U D F(u k , u j )q j (t) the immediate expected fitness of an individual using policy u k ∈ U D against a populations in state q, and by F(q) := ∑ i,j∈U D q i (t)F(u i , u j )q j (t) the average expected fitness of the population.

Based on the expression (5.14), we can define the dynamics of the evolution of q k (t) over time, where u k ∈ U D : qk (t) q k (t) = (F(u k (t), q(t)) -F(q(t))) .

(5.15)

Every interior rest point of the replicator dynamics (5.15) is a stationary equilibrium policy for the game we defined. Note that the dynamics proposed in equation ( 5.15) assumes that the distribution over the individual states is already stationary, as the state dynamics update very quickly compared to the policy dynamics. Getting results about equilibrium policies in the general case may be complicated, as the number of deterministic policies U D explodes and it becomes very difficult to properly write a clear mathematical analysis to obtain closed-form solutions of the equilibrium. In the next section, we present a complete analysis and characterization of the equilibrium policy for a particular game with two states and two strategies, considering the coupled dynamical system.

Complete Characterization of the Game with Two States

and Two Actions

Individual State and Its Dynamics

In this section we study a particular case of the state-policy coupled dynamics model.

We suppose that each player can be in one of two possible states, with S = {1, 0}. Every individual goes through a cycle that starts in state 1 and moves to states 0 after some random time, at a rate that depends on its policy. After some exponentially distributed time it returns to state 1 and so on. At each pairwise interaction, the set of available actions of a player depends on its state: in state 1, A 1 = {x, y}, whereas in state 0 an individual can only use y. We consider the set of deterministic policies U D := {u x , u y }, where u x (resp. u y ) is the deterministic policy which consists in always playing action

x (resp. y) in state 1. Under both policies, in state 0 an individual plays y. Each player chooses one deterministic policy and we denote by q i (t) the proportion of individuals in the population that play the deterministic policy u i at time t. Note that q y (t) = 1 -q x (t).

We suppose that the policy chosen impacts the fitness of the player interacting with another individual and also the time it spends in state 1. We define by µ i the rate of decay from state 1 to state 0 when using policy u i , i ∈ {x, y}, where µ x > µ y , and by µ the rate of change from state 0 to state 1. A player can choose between policy u x and u y . Accordingly with this choice, in state 1 the individual plays, respectively x or y and move to state 0, at a rate µ x or µ y . In state 0, under both policies, the only available action is y and the rate at which the player returns to state 1 is µ.

As stated in Section 5.2.2, since the population considered is large, from the law of large numbers, the individual state dynamics can be approximated by the population state dynamics. Let w 1 (t) denote the share of individuals in state 1, which is equivalent to the probability that an individual in the population is in state 1 at time t. We define the dynamics of w 1 (t) as follows:

ẇ1 (t) = -µ x w 1 (t)q x (t) -µ y w 1 (t)(1 -q x (t)) + µ(1 -w 1 (t)).
(5.16)

The first (resp. the second) term on the right side of the equation indicates that the share of individuals in state 1 which choose policy u x (resp. u y ) at time t, given by µ x w 1 (t) (resp. w 1 (t)(1 -q x (t))), leaves state 1 at a rate µ x (resp.µ y ), whereas the third term indicates that individuals in state 0 move to state 1 at rate µ (independently on the policy chosen).

Individual Fitness

At each pairwise interaction, the immediate fitness obtained by an individual, which depends on its current action and the current action of its opponent, is given by the following fitness bimatrix:

A := x y x (a, a) (b, c) y (c, b) (d, d) ,
(5.17)

where x and y are the available actions and the matrix entry A ij indicates the payoff respectively of the first (row) and the second (column) player. The expected fitness of a player interacting at time t, depends on the population profile at time t, which is now expressed by the couple ξ(t) := (w 1 (t), q x (t)). We denote by r x (ξ(t)) (resp. r y (ξ(t)))

the expected fitness of an individual playing pure action x ∈ A, against a population whose profile is ξ(t). By considering payoff matrix (5.17), we obtain the following expressions:

r x (ξ(t)) := w 1 (t)(q x (t)a + (1 -q x (t))b) + (1 -w 1 (t))b, r y (ξ(t)) := w 1 (t)(q x (t)c + (1 -q x (t))d) + (1 -w 1 (t))d.
We can now define the fitness of an individual choosing deterministic policy u i ∈ U D at time t, denoted by F i (ξ(t)), i = x, y. The fitness F i (ξ(t)) depends on the population profile ξ(t). As we are dealing with a large system, from the law of large numbers, we can assume that the probability that any individual is in state 1 at time t equals w 1 (t) and it is the same for all players, as explained in Section 5.2.2. Then, an individual choosing policy u x will be in state 1 (resp. 0) at time t with probability w 1 (t) (resp. 1 -w 1 (t)), and it will get an immediate fitness r x (ξ(t)) (resp. r y (ξ(t))). The expected immediate fitness of an individual choosing policy u x at time t is thus given by

F x (ξ(t)) = w 1 (t)r x (ξ(t)) + (1 -w 1 (t)))r y (ξ(t)).
If an individual plays policy u y , whatever its state is, it plays pure action y, which leads to:

F y (ξ(t)) = w 1 (t)r y (ξ(t)) + (1 -w 1 (t)))r y (ξ(t)) = r y (ξ(t)).
The average expected fitness of a population whose profile at time

t is ξ(t) = (w 1 (t), q x (t)) is F(ξ(t)) = q x (t)F x (ξ(t)) + (1 -q x (t))F y (ξ(t)).
(5.18)

Equilibrium Profile

We study the properties of stability of the population profile, supposing that individuals play deterministic policies in U D . Let q * = (q * x , q * y ) and define supp(q * ) = {u i ∈ U D |q * i > 0, given ξ * }.

Definition 7.

A population profile ξ * = (w * 1 , q * x ) is an equilibrium profile iff ∀u i ∈ supp(q * ) we have that:

F i (ξ * ) ≥ F j (ξ * ) ∀j = i, i, j ∈ {x, y}
An equilibrium profile is a particular population profile ξ * = (w * 1 , q * x ) which is stable in the sense of robustness against a deviation of the proportion of individuals playing the deterministic policy u x . In other words, this definition says that no individual has an interest in changing its deterministic policy, considering this population profile. Note that an equilibrium policy, if adopted by the whole population, determines a stationary individual state. Remark 5. It can be easily proved that if the population profile ξ * = (p * 1 , q * x ) satisfies the indifference principle, i.e.:

F x (ξ * ) = F y (ξ * ),
then it is an equilibrium profile.

Policy Based Replicator Dynamics

As we consider here policies instead of actions, we introduce a policy based replicator dynamics (PbRD), to study the evolution of the share of individuals using deterministic policy u x at time t, represented by q x (t). The PbRD is given by the following equation: qx (t) := q x (t)(F x (ξ(t)) -F(ξ(t))).

(5.19)

Then, the growth rate of the population share using the deterministic policy u x at time

t is: qx (t) q x (t) = F x (ξ(t)) -F(ξ(t)),
(5.20)

By substituting (5.18) into (5.19):

qx (t) = q x (t)[F x (ξ(t)) -q x (t)F x (ξ(t) -(1 -q x (t))F y (ξ(t))] = q x (t)(1 -q x (t))(F x (ξ(t)) -F y (ξ(t))), = g(w 1 (t), q x (t)).
We can investigate the dynamics of actions in this framework, where the fitness is a function of the population profile depending on policies and states and establish its relation with the dynamics of policies. If we pick one random individual in the population at time t, the probability that it plays pure action x, denoted by q(t), is given by the product q x (t)w 1 (t). From this and from definition (5.19), we obtain:

q(t) = qx (t)w 1 (t) + q x (t) ẇ1 (t) = q x (t)[w 1 (t)(F x (ξ(t)) -F(ξ(t))) + ẇ1 (t)] = q(t) w 1 (t) [w 1 (t)(F x (ξ(t)) -F(ξ(t))) + ẇ1 (t)],
which leads to the following equation for the growth rate of the proportion of individuals playing pure action x in the population at time t:

q(t) q(t) = (F x (ξ(t)) -F(ξ(t))) + ẇ1 (t) w 1 (t) .
(5.21) Equation ( 5.21) shows how the evolution of states impacts the dynamics of actions in our context. The growth rate of action x is increasing in the growth rate of state 1. We observe that a sufficiently high growth rate of state 1 can lead to a growing rate of action

x even if policy u x is non-optimal.

State-Policy Coupled Dynamics

We define the system of State-Policy Coupled Dynamics (SPcD) which combines the dynamics of the individual state and the dynamics of the policies used in the population:

(S) ẇ1 = h(w 1 (t), q x (t)) qx = g(w 1 (t), q x (t))

where ξ(t) = (w 1 (t), q x (t)) is the population profile at time t. Note that, since h and g are continuously differentiable functions of ξ, (i.e. the partial derivatives ∂h/∂w 1 , ∂h/∂q x , ∂g/∂w 1 , ∂g/∂q x are continuous) they are locally Lipschitz continuous functions with respect to ξ in the compact space [0, 1] 2 , which guarantees the existence of a solution of the system (S).

The rest point of the SPcD is ξ * = (w * 1 , q * x ) satisfying:

h(ξ * ) = 0 g(ξ * ) = 0. (5.22)
Lemma 1. Any interior rest point of the SPcD (S) is an equilibrium profile of the state-policy game.

Proof. Trivially, if ξ * is internal, it satisfies the indifference principle F x (ξ * ) = F y (ξ * ), so ξ * is an equilibrium profile.

Remark 6. Note that the converse does not necessarily hold. Any equilibrium profile is a rest point of the PbRD in (5.19), but it's not necessarily a rest point of the individual state dynamics. Lemma 2. Any Lyapunov stable rest point of the SPcD (S) is an equilibrium profile of the state-policy game.

Proof. Suppose that ξ * = (w * 1 , q * x ) is a stable rest point. If supp(q * ) = {u x , u y } then, ξ * is an interior rest point and by Lemma 1, ξ * is an equilibrium profile. Let supp(q * ) = {u x } and let us suppose that ξ * is not an equilibrium. This implies that F y (ξ * ) > F(ξ * ), and, from the continuity of the fitness function, there exists a neighborhood U ξ * of ξ * such that ∀ξ ∈ U ξ * , ξ = ξ * , F y (ξ) > F(ξ). This implies that, for this profile, the component q y increases exponentially, which contradicts the Lyapunov stability of ξ * . The proof is analogous if supp(q * ) = {u y }, which complete the proof of the lemma.

Singular Perturbations Approximation Method

As introduced in Section 5.2, we consider the existence of a small parameter ǫ > 0, such that:

ǫ ẇ1 := h(w 1 , q x ).
We then rewrite the system of the two coupled differential equations as follows:

(S ǫ ) ǫ ẇ1 = h(w 1 , q x ), qx = g(w 1 , q x ).

We can thus approximate the solution of (S ǫ ) using the standard singular Perturbation Model [START_REF] Kokotovic | Singular perturbation methods in control[END_REF] introduced in the previous section. The quasi-steadystate-model is obtained by first solving in w 1 the transcendental equation 0 = h(w 1 , q x ) and then rewriting the differential equation q as a function of the obtained roots. As the transcendental equation has a unique real solution w1 := π 1 (q x ), our system satisfies Assumption 2 and we can thus solve the quasi-steady-state equation: qx = g(π 1 (q x ), q x ).

(5.23)

If the Assumption 4 is satisfied, the reduced model is a good approximation of the original system. In our case, this assumption simplifies to the following condition: ∂h ∂w 1 (w 1 , q x ) < 0. Since ∂h ∂w 1 (w 1 , q x ) = -µ x q xµ y (1 -q x )µ < 0, we can apply the singular perturbation method to solve (S ǫ ).

The two-time-scale behavior of w 1 (t) and q x (t) also has a geometric interpretation, as trajectories in R 2 . If we define the manifold sets M ǫ := {ϕ s.t. w 1 = ϕ(q x , ǫ) & ǫ = h(q x , ϕ(q x , ǫ))}, it is possible to rewrite the problem in terms of invariant manifolds. When the parameter ǫ = 0, then M 0 is an equilibrium manifold which corresponds to the quasi steady state model. As Assumption 4 is satisfied, the equilibrium manifold M 0 is stable (attractive) [START_REF] Kokotovic | Singular perturbation methods in control[END_REF]). An important result states that the existence of a conditionally stable manifold M 0 for ǫ = 0 guarantees the existence of an invariant manifold M ǫ satisfying the following convergence for all ǫ ∈ [0, ǫ * ]:

ϕ(ǫ, q x ) → ϕ(0, q x ), and M ǫ → M 0 as ǫ → 0.

The positive constant ǫ * is determined by imposing the manifold condition:

ǫ ∂ϕ ∂x g(ϕ(q x , ǫ), q x ) = h(ϕ(q x , ǫ), q x ),
for all q x and ǫ ∈ [0, ǫ * ]. We illustrate in Figure 5.2 the attractiveness of the slow mani- fold M 0 for a numerical example.

Let us now compute the solution of the system (S 0 ), i.e. the system obtained with ǫ = 0. We suppose that the distribution of individual states is stationary (expressed by Equation (5.16)). By imposing ẇ1 = 0, we obtain the following slow manifold

M 0 := {ϕ s.t. w 1 = ϕ(q x , 0) & 0 = h(q x , ϕ(q x , 0))}: ϕ(q x , 0) = µ µ + µ x q x + µ y (1 -q x ) := ϕ 1 (q x ).
(5.24)

We can now rewrite the PbRE (5.19) as:

qx (t) = q x (t)(1 -q x (t)) F x (π 1 (q x (t)), q x (t)) -F y (π 1 (q x (t)), q x (t)) .
Proposition 10. For ǫ sufficiently small, the solution of the system (S ǫ ) can be approximated by the solution of S 0 . This is given by the population profile ξ * = (w * 1 , q * x ), such that:

w * 1 = µ -s * (µ x -µ y ) µ + µ y and q * x = s * (µ + µ y ) µ -s * (µ x -µ y ) , (5.25)
where s * is the equilibrium of the replicator dynamics (1.6) for the standard evolutionary game whit payoff matrix given by (5.17):

s * = d -b ∆ with ∆ = a -b -c + d.
Proof. Let us first study the equation qx = 0 before substituting the stationary equation of the state dynamics. To solve this equation is equivalent to find the population profile ξ = (π 1 , q x ) such that:

F x (π 1 , q x ) = F y (π 1 , q x ).
By replacing the expressions of the fitness (5.18) and (5.3.2) in the latter equality we get

π 1 [π 1 (q x a + (1 -q x )b) + (1 -π 1 )b] + (1 -π 1 ) -[π 1 (q x c + (1 -q x )d) + (1 -π 1 )d] = π 1 (q x c + (1 -q x )d) + (1 -π 1 )d.
After some manipulations,

π 1 aπ 1 q x + π 1 b(1 -π 1 q x ) + (1 -π 1 )cπ 1 q x + (1 -π 1 )d(1 -π 1 q x ) = cπ 1 q x + d(1 -π 1 q x ).
This equality corresponds to

π 1 q x [π 1 a -π 1 b + (1 -π 1 )c -(1 -π 1 )d -c + d)] = d -π 1 b -(1 -π 1 )d.
Thus

π 1 q x [π 1 a -π 1 b -π 1 c + π 1 d] = π 1 d -π 1 b.
We finally obtain

π 1 q x = d -b ∆ := s * .
The stationary condition of the first differential equation (5.16) leads to the following relation between w 1 and q x :

w 1 = π 1 (q x ) = µ µ + µ x q x + µ y (1 -q x )
, then we have to solve now: π 1 (q x )q x = s * . The latter equation is equivalent to:

µq x µ + µ x q x + µ y (1 -q x ) = s * .
After some simple manipulations we obtain

q x = s * (µ + µ y ) µ -s * (µ x -µ y ) := q * x .
Finally, as we have π 1 (q x )q x = s * then w *

1 := π 1 (q * x ) = s * q *
x which leads to

w * 1 = µ -s * (µ x -µ y ) µ + µ y .
Note that the rest point q * x of the PbRE (5.19) verifies the following relation:

q * x π 1 (q * x ) = s * .
This result says that the equilibrium probability that any individual picked out randomly in the population is playing action x, is equal to s * . This value is the mixed equilibrium of the standard matrix game given by matrix A. It means that, if we consider a state dependent action game, the equilibrium is obtained under conditional probability over the state.

We have the following necessary and sufficient condition under which the solution obtained is a strict interior point. Lemma 3. The solution q * x obtained in proposition ( 10) is a strict interior point if and only if:

µ > µ x s * 1 -s * .
Proof. The solution obtained in proposition ( 10) is:

q * x = s * (µ + µ y ) µ -s * (µ x -µ y ) .
This solution is a strict interior point if and only if:

0 < q * x < 1.
First, let's look at the positivity condition q * x > 0. This is equivalent to:

0 < q * x ⇐⇒ µ > s * (µ x -µ y ).
After some basic algebras, the second condition is:

q * x < 1 ⇐⇒ µ > µ x s * 1 -s * .
We have clearly that for all s * ∈]0, 1[, µ x and µ y :

s * 1 -s * µ x > s * µ x > s * (µ x -µ y ). Then if µ > µ x
s * 1 -s * the solution is a strict interior point, and the converse is true. This concludes the proof.

Note that this condition does not depend on the rate µ y .

Numerical Illustration

We illustrate the theoretical results obtained in this section through a numerical example. We fix the values of the transition rates, µ = 10, µ x = 1.5 and µ y = 1, and the payoffs of the matrix game: a = -0.3, c = 0, b = 1 and d = 0.5. These values yield to the following equilibrium of the standard evolutionary game: s * = 5 8 = 0.625.

In figure 5.2 we plot the trajectories of the system (S ǫ ) of the coupled differential equations for different initial conditions and for ǫ = 0.01. We simulate a discrete time version of the differential equations. We plot also the invariant manifold M 0 and we observe that it is an attractor of the trajectories.

Proposition [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF] gives the following solution of the system (S 0 ):

q * x = 0.7097, and w * 1 = 0.8807.

This couple corresponds exactly to the attractor of the trajectories on figure 5.2 and then our simulation validates the result of this proposition. In the next section, we present an alternative method based on rewriting our game into a matrix game considering only pure policies.

where r(a, a ′ ) is the immediate fitness of a player using action a against an opponent playing a ′ . From the payoffs matrix (5.17), we obtain:

F(u y , u y ) = d, F(u x , u y ) = T 1 (x)b + T 0 (x)d, F(u y , u x ) = T 1 (x)c + T 0 (x)d, F(u x , u x ) = T 1 (x) [T 1 (x)a + T 0 (x)b] + T 0 (x) [T 1 (x)c + T 0 (x)d] .
(5.27) By considering this matrix game as a representation of a standard evolutionary game, we can write the replicator equation. Let δ x (t) ∈ [0, 1] be the probability that a player plays u x at time t. We have that:

δx (t) = δ x (t)(1 -δ x (t))(F(u x , δ x (t)) -F(u y , δ x (t))) = δ x (t)(1 -δ x (t)) F(u x , u y ) -F(u y , u y ) +δ x (t)(F(u x , u x ) -F(u y , u x ) + F(u y , u y ) -F(u x , u y )) .
(5.28)

We can compute the mixed equilibrium δ *

x by solving the indifference principle equation

F(u y , δ * x ) = F(u x , δ * x ), with F(u i , q) = (1 -q)F(u i , u y ) + qF(u i , u x ) with i ∈ A. We obtain: δ * x = F(u y , u y ) -F(u x , u y ) F(u x , u x ) -F(u y , u x ) + F(u y , u y ) -F(u x , u y ) . If 0 ≤ δ * x ≤ 1,
then it is an admissible equilibrium for the matrix game and it corresponds to a rest point of the replicator dynamics (5.28). We resume our result in the following proposition. Proposition 11. If the distribution of the individual states is stationary, the equilibrium policy of the game can be computed by applying the matrix game approximation technique, which leads to the equilibrium

δ * x = s * T 1 (x)
.

(5.29)

under the condition 0 ≤ s * ≤ T 1 (x).
Proof. As we have mentioned above, the equilibrium can be computed by imposing the indifference principle, which leads to:

δ * x = F(u y , u y ) -F(u x , u y ) F(u x , u x ) -F(u y , u x ) + F(u y , u y ) -F(u x , u y )
.

By substituting the values of the fitnesses (5.27) into the latter equation and by carrying out the values of the time ratios T 1 (x) and T 0 (x), we get:

δ * x = µ(d-b) µ+µ x µ 2 a+µµ x b+µ x µc+µ 2 x d (µ+µ x ) 2 + d -µb+2µ x d+µc (µ+µ x ) = µ(d-b) µ+µ x µ 2 a+µµ x b+µ x µc+µ 2 x d+d(µ+µ x ) 2 -(µ+µ x )(µb+2µ x d+µc) (µ+µ x ) 2 .
After some algebra:

δ * x = µ(d -b) µ + µ x • (µ + µ x ) 2 µ 2 (a + d -b -c) = s * T 1 (x)
.

In order for δ *

x to be an admissible equilibrium, it must satisfy δ *

x ∈ [0, 1], which completes the proof.

In figure 5.3 we illustrate the convergence of the replicator equation (5.28 ) to the equilibrium δ * x = 0.71875, which is obtained by setting, as in the previous numerical example, µ = 10, µ x = 1.5 and µ y = 1, and a = -0.3, c = 0, b = 1 and d = 0.5, starting from q x (0) = 0.2 and q x (0) = 0.9. x = 0.71875, obtained by setting µ = 10, µ x = 1.5 and µ y = 1, and a = -0.3, c = 0, b = 1 and d = 0.5, starting from q x (0) = 0.2 and q x (0) = 0.9.

Relation Between the Equilibria

In section 5.3.6, we suppose that each individual plays a deterministic policy u i ∈ U D , which consists in always choosing action i in state 1 and action y otherwise and, by applying the singular perturbation method, we determine the equilibrium profile ξ * = (w * 1 , q * x ) of such game. In section 5.3.7, we assume that the distribution of individual states is already stationary which allows us to rewrite the game as a standard evolutionary game and to compute its mixed equilibrium δ * . While q *

x represents the share of the population choosing policy u x at the equilibrium, δ * represents the probability of choosing the deterministic policy u x . This means that, in the first case, the population considered is polymorphic (with a fraction q * of the population choosing policy u x and the remaining 1 -q *

x choosing u y ), while in the latter case we have a monomorphic population, where all individuals play the same mixed action (which consists in choosing u x with probability δ *

x ). We can compare the equilibria q * x and δ * x obtained with these two different approaches. Proposition 12. The relation between the equilibrium δ *

x and the equilibrium q * x is the following:

q * x < δ * x .
Proof. We evaluate the difference between the equilibria δ * x , obtained by solving our model as a matrix game in (5.29) with the value of the equilibrium obtained through the singular perturbation method, and q *

x in ( 10):

δ * x -q * x = s * (µ + µ x ) µ - s * (µ + µ y ) µ -s * (µ x -µ y ) = s * (µ x -µ y )(µ -s * (µ + µ x ) µ(µ -s * (µ x -µ y )) .
If we consider the same values of the parameters chosen for the previous numerical example, the matrix game approach gives the following equilibrium:

δ * x = s * (µ + µ x ) µ = 0.71875 > q * x = 0.7097,
which verifies the proposition 12.

We now compare the two equilibria in terms of the average fitness fitness of the population, i.e. F(δ * x ) and F(ξ * ), with ξ * = (w * 1 , q * x ), and we verify that, as expected, the fitnesses are equal. Proposition 13. The average fitness of the population at the equilibria points obtained with the two approaches are equals, i.e. F(ξ * ) = F(δ *

x ).

Proof. Considering the first approach, based on the singular perturbations method, we have:

F(ξ * ) = q * x F x (ξ * ) + (1 -q * x )F y (ξ * ) = F y (ξ * ) + q * x (F x (ξ * ) -F y (ξ * )),
with ξ * = (w * 1 , q * x ). At the equilibrium state, we have

F x (ξ * ) = F y (ξ * ) and thus F(ξ * ) = F y (ξ * ) = r y (ξ * ) = w * 1 (q * x c + (1 -q * x )d) + (1 -w * 1 )d. Knowing that q * x w * 1 = s * , we obtain: F(ξ * ) = s * c + (1 -s * )d.
By rewriting the game into a matrix game, we obtain the following equilibrium profile:

δ * x = s * T 1 (x)
. The average fitness of the population in this case is:

F(δ * x ) = δ * x F(u x , δ * x ) + (1 -δ * x )F(u y , δ * x ) = F(u y , δ * x ) + δ * x (F(u x , δ * x ) -F(u y , δ * x )).
At the equilibrium, we have the following equality F(u x , δ * x ) = F(u y , δ * x ) and then the average fitness of the population becomes simply:

F(δ * x ) = F(u y , δ * x ) = δ * x F(u y , u x ) + (1 -δ * x )F(u y , u y ).
The average fitness of the population is:

F(δ * x ) = δ * x (T 1 (x)c + T 0 (x)d) + (1 -δ * x )d. Since δ * x T 1 (x) = s * , F(δ * x ) = s * c + (1 -s * )d,
which completes the proof.

Finally, we prove that the two equilibria obtained with the two approaches are in the same equivalent class in terms of average sojourn times. Let T 1 (q) be the average sojourn time in state 1 for an individual in a polymorphic population whose profile is ξ * , and let T 1 (δ * x ) be the average sojourn time in state 1 for an individual in a monomophic population playing mixed action δ * . For the monomorphic population case, we obtain:

T 1 (δ * x ) = δ * x T 1 (x) + (1 -δ * x )T 1 (y) = δ * x µ µ + µ x + (1 -δ * x ) µ µ + µ y .
(5.30)

For the case of the polymorphic population: .31) The equivalence between these average sojourn times is proved in the following propo-sition. Proposition 14. The mixed equilibrium δ * x and the equilibrium obtained by the singular perturbation approach yield to the same average sojourn times, i.e.

T 1 (q * x ) = π 1 (q * x ) = µ µ + µ x q * x + µ y (1 -q * x ) . ( 5
T 1 (δ *

x ) = T 1 (q * x ).

Proof. We first rewrite δ * x as a function of the immediate payoffs in matrix (5.17):

δ * x = (µ x + µ)(d -b) µ∆ .
where ∆ := abc + d. We substitute it in (5.30), and we get:

T 1 (δ * x ) = µ∆ + (µ x + µ y ) µ∆(µ + µ y ) .
Analogously, we substitute the expression of s * in q * x in proposition [START_REF] Hofbauer | Evolutionary Games and Population Dynamics[END_REF], and we rewrite it in (5.31), which leads to:

T 1 (q * x ) = µ∆ + (µ x + µ y ) µ∆(µ + µ y ) . which proves that T 1 (q * x ) = T 1 (δ * x ).
The previous results show that we can define two equivalent classes for deterministic policies that yield same average fitness and average sojourn times.

Applications in Network Systems

Energy Control in Wireless Network

The two-states two pure actions model can be applied to describe a particular problem that arises in dynamic power control in mobile networks, which has been presented in (Altman and Hayel, 2008). The underlying idea is based on the fact that battery life is a very critical issue in wireless systems, and then, defining optimal transmission policies based on battery levels is very important. Moreover, this energy management problem is even more important when interactions occurs between the devices, complicating the analysis of such control systems. We then consider a system in which the action of each device impacts the lifetime of its battery or its battery level, and also impacts its transmission rate. A large number of mobiles transmit packets occasionally. Each transmitter can be in Full (F) or Almost empty (A) battery state. When a mobile is in F state it can choose to transmit packets using high (h) or low (l) power, whereas if it is in state A, it can only transmit packets using l power. In general, several mobiles try to join a common receiver at the same time and interferences occur between the received signals. We suppose that transmissions are sparse so that the probability that more than two mobiles transmit simultaneously is negligible. We also assume that a transmission is successful either if the mobile is the only transmitter during a slot or if it transmits at higher power than the other transmitter. The time spent in state F depends on the action chosen by the mobile. Then the state of the mobile changes to the lower battery state A. After an exponentially distributed time, its battery state becomes empty. We assume that the battery is immediately recharged, so that the mobile goes back to state F. When transmitting at high power, the mobile's battery is consumed faster, and thus the transition rate from F to A is faster. Then, in this framework, the state space corresponds to S := {A, F}, the action space is A := {h, l} = A F and the restricted action space for state A is A A := {l}. The set of deterministic policies U D := {u h , u l } is composed of the policy u h such that u h (A) = l and u h (F) = h; the policy u l such that u l (A) = l and u l (F) = l. Then, the system (S) of coupled dynamics describes the time evolution of the proportion of mobiles in each state A and F, and at the same time the proportion of mobiles using policy u h and u l . By assuming that the state dynamic is highly faster than the policy dynamics (the change of policy has to be reimplemented into the mobiles by manufacturer or designers), then our analysis describes the equilibrium situation which corresponds to the long term evolution of this system. , in state F it transmits at high power (h), otherwise, if it chooses policy u l it transmits at low power (l) (right side). In state A, it always transmits at low power. Since high power transmission is costly in terms of energy consumption, when transmitting at high power, the transition rate to state A is faster, and thus the time spent in state F is shorter.

Network Formation Games

Another application of the proposed model can be found in network formation games [START_REF] Jackson | A Survey of Network Formation Models: Stability and Efficiency[END_REF]. We consider a large number of nodes where each node is in one of two possible states: Infected or Susceptible, so that S = {I, S}. Nodes interact through pairwise interactions, during which both nodes exchange contents. If a node is in state S, it determines the type of unidirectional link to the node it is interacting with. The type of link can be charged at a price (p) or for free ( f ); if a node is in the infected state (state I), it can only create free links. Pay connection is safer, so that when a link is not a free one, the probability for a node to be infected is lower, independently of the choice of the other node to pay or not and also independent of the state of the other node. After some random time in I state, a node becomes susceptible again. This application into networks formation games could ask more assumptions on the model, especially if the transition rate depends on the state of the opponent. In this case we should define a more general game framework considering interactive MDPs, like anonymous sequen-tial games [START_REF] Wiecek | Stationary anonymous sequential games with undiscounted rewards[END_REF]. This generalized framework has a highly more complicated internal structure. We thus let its analysis as an extension for future works.

It has to be noted that the singular perturbation approach, proposed in Subsection 5. 3.6 is valid for this application, by considering a more complicated dynamics of individual state, which depends on the action also of the opponent.

Conclusion

In this chapter we considered a particular type of evolutionary game in which the action of the individual not only determines its immediate fitness but it also impacts the transition rates of the Markov process of the individual state. We defined the interdependent dynamics of the individual state and of the policy, where the evolution of policies distribution in the population dynamics is assumed to follow the well-known replicator dynamics. After introducing these combined dynamics in a general framework, we analyzed a particular case for which we proved the correspondence between stable rest points of the dynamics and the equilibrium profiles of the evolutionary game. Under the assumption that the two dynamics evolve with different timescales, we proposed two methods to obtain the rest points. We gave a complete characterization of these equilibrium profiles and we showed that these equilibria are equivalent in terms of average sojourn times and expected fitness. Finally, we illustrated our framework with two application scenarii in network systems.

Introduction

In this chapter we present a simple example of a Hawk-Dove game in a MDEG type of framework, where, in contrast with the theory presented in Chapter 4, we assume that transition probabilities do not depend on the action of the player but may depend on the action taken by those it encounters. The Hawk-Dove game is one of the most studied example to model the level of aggressiveness in a population and it finds many applications in different fields (see Section 1.4). The aim of our MDEG version of the game is to study the impact of the aggressive behavior of adults on the evolution of young individuals.

State of Art

Dynamical models of the Hawk-Dove game can be found in EGT literature. [START_REF] Houston | Fighting for food: a dynamic version of the Hawk-Dove game[END_REF]) [START_REF] Houston | Evolutionary stable strategies in the repeated Hawk-Dove game[END_REF] et al., 1991) give an analytic justification of the computations performed in [START_REF] Houston | Fighting for food: a dynamic version of the Hawk-Dove game[END_REF]) in a simpler setting, where they obtain interesting structural properties of the equilibrium using dynamic programming tools.

Some of the features considered in the Hawk-Dove model that we define can be found in (Altman and Hayel, 2008) In what follows, we consider a Hawk-Dove game where players are associated with one of four possible states, representing the age and the strength of the individual, and we suppose that the aggressive behavior is possible only in one of these states. Players aim at maximizing their expected immediate fitness during their lifetime. The system is assumed to be in its stationary state, which means that the distribution over the individ-ual states is stationary, and the game is then transformed into a standard evolutionary game. We identify the stationary equilibrium of the game and we compute its value.

In Section 6.3 we consider the case of group players presented in Chapter 2, for this Hawk-Dove MDEG.

The Model

Let us consider an infinitely large population of players matched in pairwise random interactions. We define a four state model, such that each individual is born 'young'

(Y) and after each interaction with another randomly selected individual can become an adult or remain in young state. Adults can be aggressive (play Hawk) or non-aggressive (play Dove). If a young meets an aggressive adult either it evolves as a 'weak adult' (A W ) or it becomes a 'weak young' (Y W ). A weak young, when evolving, can only become a weak adult, whereas a young who has never been attacked may evolve into a 'strong adult' (A S ). The tuple {S, A, Q} describing our game is defined as follows:

• The set of states is S = {Y, Y W , A S , A W }, where Y, Y W correspond to 'young' and 'weak young', A S to 'strong adult' and A W to 'weak adult'.

• The set of actions is A = {H, D}, with A A S = A, and

A A W = A Y = A Y W = {D}.
Players can choose weather to behave aggressively (H) or not (D) only in A S state, while in all the other states, players can only play D.

• We define the probability of remaining in the young state (either weak or not) for a young individual by y ∈ [0, 1]. Consequently, the probability for a young individual to evolve into an adult one is 1 -y. Analogously, the probability for an adult to stay in adult state (either weak or strong) is denoted by x ∈ [0, 1], while with probability 1 -x an adult dies and is replaced by a young individual. We assume that the transition probabilities Q t s ′ (s, a, a ′ ) (defined in Section 4.2) are time homogeneous and do not depend on the action of the player (a), but they may depend on that of its opponent (a ′ ). We describe the set Q as follows.

-If a young individual meets an adult one, the transition probabilities depend on the action of the player it meets (and not on its action):

Q Y (Y, •, D) = y Q Y (Y, •, H) = 0 Q Y W (Y, •, D) = 0 Q Y W (Y, •, H) = y Q A W (Y, •, D) = 0 Q A W (Y, •, H) = 1 -y Q A S (Y, •, D) = 1 -y Q A S (Y, •, H) = 0 92 6.
2. The Model -If a weak young individual meets an adult one, the transition probabilities only depend on its state (and not on the adult's action):

Q Y (Y W , •, •) = 0 Q Y W (Y W , •, •)y Q A W (Y W , •, •) = 1 -y Q A S (Y W , •, •) = 0
-Analogously, when an adult individual of type i meets another adult, the transition probabilities only depend on the player state:

Q A j (A i , •, •) = x i = j 0 i = j Q Y (A i , •, •) = 0 Q Y W (A i , •, •) = 0
Without loss of generality, we restrict to the set of stationary policies U S . We assume that if the population uses some common (mixed) stationary policy (except for a tagged player) then the global state process before the tagged user is born forms a time-homogeneous Markov chain; when the tagged player is born, it finds the Markov chain in steady state.

Since the choice of an action in A is limited to state A S , we can identify a (mixed) stationary policy u ∈ U S with the rule "play action H with probability q u when in state A S , D otherwise", i.e. u(H|A S ) = q u , u(D|A S ) = 1 -q u and u(D|A W ) = u(D|Y) = u(D|Y W ) = 1. Let u H and u D be the deterministic policies corresponding respectively to q u = 1 and q u = 0. Let v ∈ U S be the common policy adopted by the population . The fraction of adults of type A i ∈ {A W , A S } in such a population is defined as:

α i (v) := P(A i |v)
The total proportion of adults in the population, denoted by P(A), does not depend on the policy v, and it corresponds to the expected lifetime spent in adult state over the total expected lifetime of an individual:

P(A) = 1 1-x 1 1-x + 1 1-y . (6.1)
The probability of being attacked when young is α S (v)q v , which corresponds to the probability of finding a strong adult playing aggressively. Consequently α W (v) = P(A)(α S (v)q v ) and α S (v) = P(A)(1α S (v)q v ). We can then explicit the fraction of strong and weak adults in the population as a function of P(A):

α S (v) = P(A) 1 + P(A)q v , α W (v) = q v P(A) 2 1 + P(A)q v . (6.2)
Since in classical EGT the fitness function is related to the rate of reproduction of an individual, we suppose that only adults reproduce and thus the fitness of a young individual is assumed to be zero. The immediate payoff matrix, describing the fitness of the row player when meeting the column player, is the following:

A S (H) A S (D) A W Y Y W A S (H) 1 2 -δ 1 1 1 1 A S (D) 0 1 2 1 2 1 2 1 2 A W -∆ 1 2 -∆ 1 2 -∆ 1 2 -∆ 1 2 -∆ where δ, ∆ > 1 2
. The parameter δ represents the cost of the fight, whereas ∆ reflects the loss of fitness for individuals who have been attacked when young. We omitted the null rows for Y and Y W .

The expected immediate fitness for an adult of type i ∈ {A S , A W }, choosing policy u ∈ U S against a population playing v ∈ U S is F(i, u, v) := E u,v [r(i, s, s ′ , a ′ )], where r(i, a, s ′ , a ′ ) is the immediate fitness of an adult of type i ∈ {A S , A W } playing a ∈ A i against an individual in state s ′ ∈ S playing a ′ ∈ A s ′ . As each player is born in young state, F(i, u, v) does not depend on the initial state.

Deriving the Expected Fitness and the Equilibria

We suppose that a tagged individual chooses stationary policy u against a population playing stationary policy v. The total expected fitness of the tagged player during its lifetime is given by:

F(u, v) = 1 1 -x (α S (v)F(S, u, v) + α W (v)F(W, u, v)) , (6.3)
where 1 1 -x is the expected lifetime in adult state. F(S, u, v) denotes the immediate expected fitness of an adult strong (A S ) playing u against a population playing v, with: The equilibrium q v * as a function of the value of δ for different values of P(A). The higher line is obtained with P(A) = 0.15, the middle line with P(A) = 0.5, the lower one with P(A) = 0.88. chosen in order to maximize the fitness of the group they belong to. We suppose that the large population of individuals is divided into N symmetric groups of the same size and that all players within a group choose the same policy. We further suppose that the probability of being a strong (or a weak) adult does not depend on the group the player belongs to, but it depends only on the average quantity qu := ∑ N l=1 q u l N , which is the av- involved in pairwise interactions determine not only the immediate fitness but also the transition probabilities of the players' individual state. We found that the described game has a unique symmetric equilibrium, which can be the pure aggressive policy u H or a mixed equilibrium policy v * , depending on the value of the cost of the fight between two aggressive individuals δ. We then further extended our dynamic Hawk-Dove game, by considering group-players as presented in Chapter 2. We fixed the number of groups N = 2, the share of adults P(A) = 0.5 and ∆ = 1, to compute the equilibria as a function of the cost of the fight δ. If the cost is very low, the aggres-sive deterministic policy u H is an equilibrium, otherwise, above certain values of the cost, we have a mixed equilibrium policy u * and the deterministic policy u H . In particular, for δ ∈ [0.8125, 1.05] the game admits the two equilibria u H and u * and, for δ ≥ 1.333 the equilibria u D and u * . The presence of groups in the dynamic Hawk-Dove game thus brings novel features with respect to the individual player game: the fact the non-aggressive policy u D can an equilibrium and the fact of having more than one equilibrium (for some values of δ). We also compared the mixed equilibria obtained respectively for the individual-players and the group-players games and we obtained that the probability of being aggressive in strong adult state is higher for individualplayers. This is coherent with the results obtained in Chapter 2, where we showed that the presence of groups lowers the level of aggressiveness.

Part III

Stochastic Hybrid Dynamics

Introduction

In this chapter, we study a non-zero sum dynamic game whose state is described as a hybrid dynamical system that evolves in continuous time and that is subjected to abrupt changes of the parameters. These changes are determined by two Markov decision processes, each of which is controlled by a player that aims at minimizing its objective function. The lengths of the time intervals between the "jumps" of the parameters are assumed to be equal to a small positive parameter ǫ, which means that parameters change their values frequently (the smaller is the parameter ǫ, the higher is the frequency). The MDPs are thus supposed to move faster than the state of the system. We then define an averaged dynamic game which allows us to approximate the hybrid system. More precisely, the main result of this chapter establishes that an asymptotic Nash equilibrium of the game defined by the solutions of the hybrid system (see Definition 1 in Section 7.2 below) can be constructed on the basis of a Nash equilibrium of the game defined by the solutions of the deterministic averaged system.

The principal difference of our result from those obtained in the aforementioned works is in that the information structures of the hybrid and the averaged games need to be adjusted. In fact, we show that an asymptotic Nash equilibrium of the hybrid game, in which each of the players chooses its actions on the basis of the full information of its states/actions histories can be constructed on the basis of an open loop Nash equilibrium of the averaged game, where players have no information about their previous state/action history (nor about the state of the system).

State of Art

Hybrid dynamics control problems, with stochastic control and two time scales behavior, have been first introduced by Altman and Gaitsgory [START_REF] Altman | Control of a hybrid stochastic system[END_REF], in the case of one controller and linear dynamics and then extended to a two players zero-sum game [START_REF] Altman | A hybrid differential stochastic zero sum game with fast stochastic part[END_REF]. In [START_REF] Altman | Asymptotic optimization of a nonlinear hybrid system controlled by a Markov decision process[END_REF] and [START_REF] Nguyen | On stochastic hybrid zero-sum games with nonlinear slow dynamics[END_REF] these models are generalized to non linear dynamics, respectively for one controller and for the zero-sum game.

The problem of optimization of a nonlinear hybrid system governed by a Markov decision process is close in nature to stochastic singular perturbed control problems intensively studied in the literature (see, for example, [START_REF] Abbad | Perturbation and stability theory for Markov control problems[END_REF], [START_REF] Bensoussan | Singular perturbations in stochastic control. Singular Perturbations and Asymptotic Analysis in Control Systems[END_REF], [START_REF] Bensoussan | Perturbation Methods in Optimal Control Problems[END_REF], [START_REF] Bielecki | Singularly perturbed Markov control problem: Limiting average cost[END_REF], [START_REF] Delebecque | Contribution of stochastic control singular perturbation averaging and team theories to an example of large scale systems: Management and hydropower production[END_REF], [START_REF] Kokotovic | Singular perturbation methods in control[END_REF], [START_REF] Kushner | Weak Convergence and Singularly Perturbed Stochastic Control and Filtering Problems[END_REF], [START_REF] Philips | A singular perturbation approach to modeling and control of Markov chains[END_REF], [START_REF] Pervozvansky | Theory of Suboptimal Decisions[END_REF] and references therein). The main idea in dealing with this category of problems is to optimize slow motions, assuming that the fast ones are approximated by their quasi stationary distributions of states obtained with "frozen" slow variables and controls, (see [START_REF] Kokotovic | Singular perturbation methods in control[END_REF], [START_REF] Bensoussan | Perturbation Methods in Optimal Control Problems[END_REF], [START_REF] O'malley | Introduction to singular perturbations[END_REF], [START_REF] Kokotovic | Applications of singular perturbations techniques to control problems[END_REF]). A common approach is an application of singular perturbations or averaging techniques to the Hamilton-Jacobi-Bellman (HJB) equation for problems in continuous time (as in [START_REF] Bensoussan | Singular perturbations in stochastic control. Singular Perturbations and Asymptotic Analysis in Control Systems[END_REF], [START_REF] Bensoussan | Perturbation Methods in Optimal Control Problems[END_REF]) or to the dynamic programming equation for singularly perturbed discrete time MDPs [START_REF] Abbad | Perturbation and stability theory for Markov control problems[END_REF], [START_REF] Bielecki | Singularly perturbed Markov control problem: Limiting average cost[END_REF], [START_REF] Delebecque | Contribution of stochastic control singular perturbation averaging and team theories to an example of large scale systems: Management and hydropower production[END_REF], [START_REF] Philips | A singular perturbation approach to modeling and control of Markov chains[END_REF], [START_REF] Pervozvansky | Theory of Suboptimal Decisions[END_REF]. In contrast to this approach, here we continue the line of research started in [START_REF] Altman | Asymptotic optimization of a nonlinear hybrid system controlled by a Markov decision process[END_REF] and [START_REF] Nguyen | On stochastic hybrid zero-sum games with nonlinear slow dynamics[END_REF], where an averaging method is applied directly to the "slow" stochastic equation.

Such type of systems arise in modeling admission control in telecommunication networks, in which the dynamics of the state variables (representing information packets transmission times at different nodes) is determined by MDPs describing the changes of the routes, their numbers and the type of sessions that are present in the networks (see e.g. [START_REF] Shi | On asymptotic optimization of a class of nonlinear stochastic hybrid systems[END_REF]).

The chapter is organized as follows. In Sections 7.2 and 7.3, the hybrid and, respectively, averaged deterministic games are introduced. In Section 7.4, the main results are stated (see Propositions 15 and 16), and in Section 7.4.1, these are proved.

Hybrid Game

Let the dynamics of the state vector Z(t) ∈ R N be described by the equation

Ż(t) = f 1 (Z(t), Y 1 (t)) + f 2 (Z(t), Y 2 (t)), Z(0) = z 0 , t ∈ [0, 1], (7.1)
where

f i (•, •) : R N × R N i → R N , i = 1, 2
, are continuous functions satisfying Lipschitz conditions in z (see Assumption 6 below). The functions Y i (t) ∈ R N i , i = 1, 2, are "controls" defined by two players. These controls are not chosen directly by the players.

They are obtained as the result of the players controlling the transition probabilities of two associated stochastic discrete event systems described as follows.

The system i (i = 1, 2) has a finite state space S i and it changes its states at discrete moments of time t j = jǫ, j = 0, 1, . . . , ⌊ǫ -1 ⌋, where ǫ > 0 is a small parameter representing the time unit and ⌊b⌋ stands for the greatest integer which is smaller then or equal to b. The player i has a finite action space A i , and if it chooses an action a ∈ A i , then, such that at any moment t j = jǫ, the probability measure u i j on A i is chosen as a function of the current micro state of the player i.

Note that, as follows from the definitions above, U S ⊂ U M ⊂ U . Assumption 5. Under any stationary policy, the state space of the stochastic processes {S i j , A i j } (i = 1, 2) forms an aperiodic Markov chain such that all states communicate (regular Markov chain).

As mentioned above, we make the following assumption about the functions f 1 and f 2 . Assumption 6. The functions f i (•, •), i = 1, 2 are continuous and satisfy Lipschitz conditions in the first argument. That is, there exist positive constants C 1 , C 2 such that

f i (z, y i ) -f i ( z, y i ) ≤ C i z -z , i = 1, 2 (7.4)
for arbitrary z and z from a sufficiently large subset of R N . Remark 8. According to their definitions, the processes Y 1 (t) and Y 2 (t) take values in some finite subsets D 1 and D

2 of R N 1 and R N 2 , that is, Y i (t) ∈ D i , i = 1, 2 . Due to (7.4), it implies that Z(t) ∈ D ∀t ∈ [0, 1], where D is a compact subset of R N . Note that, since f i (•, •), i = 1, 2 are continuous, there exist positive constants M i , i = 1, 2, such that f i (z, y i ) ≤ M i , ∀(z, y i ) ∈ D × D i , i = 1, 2. (7.5)
Assume that the player i wishes to minimize its cost that only depends on the final value of the macro state, G i (•) : R N → R, i = 1, 2. To simplify the presentation, we assume that the cost functions G i (•) i = 1, 2, satisfy Lipschitz conditions on D (although the continuity of these functions would suffice our purposes). Thus, we make the following assumption. Assumption 7. There exist positive constants C i G , i = 1, 2, such that

|G i (z) -G i ( z)| ≤ C i G z -z ∀ Z, Z ∈ D, i = 1, 2. (7.6) Definition 8. A pair of policies u * ǫ = (u 1 * ǫ , u 2 * ǫ ) ∈ U is an Asymptotic Nash Equilibrium (ANE) of the hybrid game if      lim ǫ→0 E (u 1 * ǫ ,u 2 * ǫ ) ζ [G 1 (Z(1))] ≤ lim ǫ→0 E (u 1 ǫ ,u 2 * ǫ ) ζ {G 1 (Z(1))}, ∀u 1 ǫ ∈ U 1 lim ǫ→0 E (u 1 * ǫ ,u 2 * ǫ ) ζ {G 2 (Z(1))} ≤ lim ǫ→0 E (u 1 * ǫ ,u 2 ǫ ) ζ {G 2 (Z(1))}, ∀u 2 ǫ ∈ U 2 (7.7)
where limits in the left-hand-sides are assumed to exist and the initial micro states ζ = (ζ 1 , ζ 2 ) are fixed (and known to the players).

Averaged Dynamic Game

The fact that the changes of the micro states/actions occur frequently (every moment t j = jǫ) means that the processes Y 1 (t) and Y 2 (t) change their values on a much faster scale than does the macro state Z(t). This allows one to approximate the solutions of the hybrid system (7.1) with the solutions of the deterministic averaged control system introduced in the next section. Our main result is the construction of ANE of the stochastic hybrid game on the basis of the Nash equilibrium of the deterministic dynamic game considered on the trajectories of the averaged system (see Sections 3-5 below).

Averaged Dynamic Game

Let ω i (u i s ) = ω i (u i s ; s, a) be the vector of steady state probabilities of the micro stateaction pair (s, a) of the player i when it uses a stationary policy u i s ∈ U S i . That is,

ω i (u i s ; s, a) := lim j→∞ P u i s ζ (S i j = s, A i j = a), ω i (u i s ) = {ω i (u i s ; s, a)}. (7.8)
Due to the Assumption 5, the limit value ω i (u i s ; s, a) is independent of the initial conditions. Define the sets W i by the equations

W i = u i s ∈U S i {ω i (u i s )}, i = 1, 2. ( 7
.9) Note that the sets W i are polyhedrons (see, e.g., (Derman, 1970), pp. 93-95).

Consider a deterministic system, in which the dynamics of the state vector z(t) is described by the equation

ż(t) = f 1 (z(t), ω 1 (t)) + f 2 (z(t), ω 2 (t)), z(0) = z 0 t ∈ [0, 1], (7.10)
where .11) The functions ω i (•), i = 1, 2, are controls chosen by the players. These are assumed to be measurable functions of t that satisfy the inclusions ω

f i (z, ω i ) := ∑ s,a f i (z, g i (s, a))ω i (s, a) ∀ ω i ∈ W i , i = 1, 2. ( 7
i (t) ∈ W i ∀t ∈ [0, 1], i = 1, 2.
As one can readily see, from Assumption 6 it follows that (7.12) and from Remark 8 it follows that .13) Note that from (7.12) it follows that the solution of (7.10) exists and is unique with any choice of controls ω i (•), i = 1, 2.

f i (z, ω i ) -f i ( z, ω i ) ≤ C i z -z , ∀z, z ∈ D, ∀ω i ∈ W i ,
f i (z, ω i ) ≤ M i , ∀(z, ω i ) ∈ D × W i . ( 7
Assume that the player i wishes to minimize the terminal cost function G i (z(1)), where G i (•) is the same as in the previous section (i = 1, 2). Given a pair of controls (ω 1 (t), ω 2 (t)), let J i (ω 1 , ω 2 ) stand for the cost function of the payer i obtained with the players adopting these controls. That is,

J i (ω 1 , ω 2 ) := G i (z( 1
)), (7.14) where z(t) is the solution of (7.10) obtained applying (ω 1 (t), ω 2 (t)).

Definition 9. A pair of controls (ω 1 * (•), ω 2 * (•)) is a Nash equilibrium of the averaged game if J 1 (ω 1 * , ω 2 * ) ≤ J 1 (ω 1 , ω 2 * ), J 2 (ω 1 * , ω 2 * ) ≤ J 2 (ω 1 * , ω 2 ), (7.15)
for any ω 1 (•) (resp. ω 2 (•)).

Note that the Nash equilibrium of the averaged game is defined in the loop setting, which means that the players have no information about their own past state/action history, nor about the state of the system. In the next section, we will show how ANE policies of the hybrid game can be constructed on the basis of a Nash equilibrium pair of the averaged game.

Construction of ANE Policies -Main Results

Let ω i (•) be a control of the player i in the averaged game. Partition the time interval

[0, 1] by the points .17) On each interval [τ l , τ l+1 ] (l = 0, 1, . . . , ⌊∆(ǫ) -1 ⌋ -1), define the time averages ω i l ,

τ l := l∆(ǫ), l = 0, 1, 2, . . . , ℓ(ǫ), ℓ(ǫ) := ⌊∆(ǫ) -1 ⌋, τ ℓ(ǫ)+1 = 1, (7.16) where ∆(ǫ) > 0 is a function of ǫ such that lim ǫ→∞ ∆(ǫ) = 0, lim ǫ→0 ∆(ǫ) ǫ = ∞. ( 7
ω i l := 1 ∆(ǫ) τ l+1 τ l ω i (t)dt ∈ W i , i = 1, 2, (7.18)
(the validity of the last inclusions follows from the convexity of W i , i = 1, 2). Note that, from the fact that ω i l ∈ W i , it follows that there exists a stationary policy u i s ∈ U S i of the player i such that

ω i l = ω i l (s i l )
(see (7.8) and (7.9)). Let us define a policy of the player i in the hybrid game that consists of:

i. Applying, at each j = ⌊τ l /ǫ⌋, ⌊τ l /ǫ⌋ + 1, . . . , ⌊τ l+1 /ǫ⌋ -1, the policy s i l , for any l = 0, 1, 2, . . . , ℓ(ǫ) -1;

ii. Applying an arbitrary stationary policy for ⌊τ ℓ(ǫ) /ǫ⌋, ⌊τ ℓ(ǫ) /ǫ⌋ + 1, . . . , ⌊ǫ -1 ⌋.

Let us denote this policy as u i ǫ (ω i ). Note that, by construction,

u i ǫ (ω i ) ∈ U M i , i = 1, 2.
The main results of the paper are Propositions 15 and 16 stated below. Proposition 15. Let ω(t) = (ω 1 (t), ω 2 (t)) be a pair of controls and let z(t) be the corresponding solution of (7.10). Let also u ǫ (ω) = (u 1 ǫ (ω 1 ), u 2 ǫ (ω 2 )) be the pair of policies defined above and let Z(t) be the random trajectory of system (7.1) obtained with the players using these policies. Then max .19) where lim ǫ→0 γ(ǫ) = 0. Also,

t∈[0,1] E u ǫ (ω) ζ Z(t) -z(t) ≤ γ(ǫ), ( 7
lim ǫ→ 0 E u ǫ (ω) ζ G i (Z(1)) = J i (ω 1 , ω 2 ), i = 1, 2. ( 7
(ω * ) = (u 1 * ǫ (ω 1 * ), u 2 * ǫ (ω 2 * )) be defined as above (considering ω(t) = ω * (t)). Then u * ǫ (ω *
) is an asymptotic Nash equilibrium of the hybrid game. The proofs of Propositions 15 and 16 are given in the next section.

Proofs of Propositions 15 and 16

Let us first recall some results from the MDP theory that are needed for the proofs of the main results. Let h i stand for the full micro states-actions history of the player i (that is, (7.2)) and let h K,i m be a part of this history corresponding to the interval [t m , t m+K ], h K,i m := {s i m , a i m , . . . , s i m+K , a i m+K }.

h i = h ⌊ǫ -1 ⌋,i 0 ; see
Denote by φ K,i m (h i ; s, a) the frequency of appearance of the micro state-action pair (s, a) ∈ S 7.21) where 1 {s i n =s,a i n =a} is the indicator function. If H i is a random realization of h i , we denote: .22) Lemma 4. The following relationships are valid: (7.23) and also lim

i × A i on the interval [t m , t m+K ], φ K,i m (h i ; s, a) := 1 K + 1 m+K ∑ j=m 1 {s i j =s,a i j =a} , φ K,i m (h i ) = {φ K,i m (h i , s, a)}, (
φ K,i m (s, a) = φ K,i m (H i , s, a), φ K,i m = {φ K,i m (s, a)}. ( 7
lim K→∞ sup ζ sup u i s ∈U S i E u i s ζ φ K,i 0 -ω i (u i s ) = 0,
K→∞ sup ζ sup u i ∈U i E u i ζ d K,i 0 = 0, (7.24)
where

d K,i 0 := dist(φ K,i 0 , W i ) = inf ω i ∈W i φ K,i 0 -ω i .
Proof. For a proof of the lemma, see Theorem 4.1 in [START_REF] Altman | Asymptotic optimization of a nonlinear hybrid system controlled by a Markov decision process[END_REF].

Proof of Proposition 15. Let ω(t) = (ω 1 (t), ω 2 (t)) be as in the statement of Proposition 15 and let z(t) be the corresponding solution of (7.10). Define the sequence of vectors ξ l , l = 0, . . . , ℓ(ǫ), as the solution of the following difference equation

ξ l+1 = ξ l + ∆(ǫ) f 1 (z(τ l ), ω 1 l ) + f 2 (z(τ l ), ω 2 l ) , ξ 0 := z 0 . (7.25) By definition z(τ l+1 ) = z(τ l ) + τ l+1 τ l f 1 (z(t), ω 1 (t))dt + τ l+1 τ l f 2 (z(t), ω 2 (t))dt. (7.26) Hence, z(τ l+1 ) -ξ l+1 ≤ z(τ l ) -ξ l + ∆(ǫ) 2 ∑ i=1 1 ∆(ǫ) τ l+1 τ l f i (z(t), ω i (t))dt -f i (z(τ l ), ω i l )) .
The function f i (z, ω i ) is linear in ω i and Lipschitz continuous in z. Consequently, there exists an appropriately chosen positive constant M such that

z(τ l+1 ) -ξ l+1 ≤ z(τ l ) -ξ l + ∆(ǫ) 2 M,
which implies that, for any l = 1, . . . , ℓ(ǫ), .27) Let Z l , l = 0, 1 . . . , ℓ(ǫ), be the sequence of random vectors defined by the equation

z(τ l ) -ξ l ≤ ℓ(ǫ)∆(ǫ) 2 M ≤ ∆(ǫ) M. ( 7
Z l+1 = Z l + τ l+1 τ l f 1 (Z l , Y 1 (t))dt + τ l+1 τ l f 2 (Z l , Y 2 (t))dt, l = 0, 1, . . . , ℓ(ǫ) -1. (7.28)
By subtracting the latter from (7.25) and taking the expectation over the probability measure corresponding to the policies u ǫ (ω) = (u 1 ǫ (ω 1 ), u 2 ǫ (ω 2 )), we obtain

E u ǫ (ω) ζ ξ l+1 -Z l+1 ≤ E u ǫ (ω) ζ ξ l -Z l + ∆(ǫ) 2 ∑ i=1 E u ǫ (ω) ζ 1 ∆(ǫ) τ l+1 τ l f i (Z l , Y i (t))dt -f i (z(τ l ), ω i l ) ≤ E u ǫ (ω) ζ ξ l -Z l + ∆(ǫ) 2 ∑ i=1 E u ǫ (ω) ζ 1 ∆(ǫ) τ l+1 τ l f i (Z l , Y i (t))dt - 1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt + 1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt -f i (z(τ l ), ω i l )) . (7.29)
Using the Lipschitz continuity of f i (z, ω i ) in z and the estimate (7.27), one can obtain that 1 ∆(ǫ) .30) By substituting the latter inequality in (7.29), one obtains .31) Let K(ǫ) = min l=0,1,...,l(ǫ)-1

τ l+1 τ l f i (Z l , Y i (t))dt - 1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt ≤ 1 ∆(ǫ) τ l+1 τ l C i Z l -z(τ l ) dt ≤ C i ( Z l -ξ l + ξ l -z(τ l )) ≤ C i ( Z l -ξ l + M∆(ǫ)). ( 7
E u ǫ (ω) ζ ξ l+1 -Z l+1 ≤ E u ǫ (ω) ζ ξ l -Z l + (C 1 + C 2 ) M∆(ǫ) 2 + ∆(ǫ)E u ǫ (ω) ζ 2 ∑ i=1 C i Z l -ξ l + 1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt -f i (z(τ l ), ω i l )) . ( 7
(⌊τ l+1/ǫ⌋ -⌊τ l/ǫ⌋ ). Note that the following estimates are valid (see [START_REF] Shi | On asymptotic optimization of a class of nonlinear stochastic hybrid systems[END_REF]) .32) From ( 7.32) it follows that there exist positive constants L i 1 , L i 2 such that, for i = 1, 2, and l = 1, . . . , ℓ(ǫ), .34) Let (as above) φ K,i m = {φ K,i m (s, a)} stand for the state-action frequencies of the controller i that corresponds to a random realization of the history H i (see (7.22). Then

2 ≥ ⌊τ l+1/ǫ ⌋ -⌊τ l/ǫ ⌋ -K(ǫ), K(ǫ) - ∆(ǫ) ǫ ≤ 1 ⇒ K(ǫ) -1 - ǫ ∆(ǫ) ≤ ǫ 2 ∆(ǫ) 2 1 1 -ǫ/∆(ǫ) . ( 7
1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt - ǫ ∆(ǫ) ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n )) ≤ L i 1 ǫ ∆(ǫ) , (7.33) ǫ ∆(ǫ) ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n )) - 1 K(ǫ) + 1 ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n ) ≤ L i 2 ǫ ∆(ǫ) . ( 7
1 K(ǫ) + 1 ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n )) = ∑ (s,a)∈S i ×A i φ K(ǫ),i
⌊τ l/ǫ ⌋ (s, a) f i (z(τ l ), g i (s, a)).

Note that from (7.23) (see Lemma 4) it follows that there exists a function µ i : N → R, with lim

K→∞ µ i (K) = 0 (implying lim ǫ→0 µ i (K(ǫ)) = 0 ) such that E u i s S i ⌊τ l /ǫ⌋ max (s,a) |φ K(ǫ),i ⌊τ l/ǫ ⌋ (s, a) -ω i l (s, a)| ≤ µ i (K(ǫ)). (7.35) Since 2 ∑ i=1 E u ǫ (ω) ζ 1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt -f i (z(τ l ), ω i l )) ≤ 2 ∑ i=1 E u ǫ (ω) ζ    1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt - ǫ ∆(ǫ) ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n )) + ǫ ∆(ǫ) ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n )) - 1 K(ǫ) + 1 ⌊τ l+1/ǫ ⌋+K(ǫ) ∑ n=⌊τ l/ǫ ⌋ f i (z(τ l ), g i (S i n , A i n )) + ∑ s,a φ K(ǫ) ⌊τ l/ǫ ⌋,i (H i ; s, a) f i (z(τ l ), g i (s, a)) -f i (z(τ l ), ω i l )
and since, by definition, f i (z(τ l ), ω i l ) := ∑ s,a ω i l (s, a) f i (z(τ l ), g i (s, a)), one can obtain, using (7.35), (7.33), (7.34)

, 2 ∑ i=1 E u ǫ (ω) ζ 1 ∆(ǫ) τ l+1 τ l f i (z(τ l ), Y i (t))dt -f i (z(τ l ), ω i l ) ≤ ( L1 + L2 ) ǫ ∆(ǫ) + 2 ∑ i=1 E u ǫ (ω) ζ ∑ s,a φ K(ǫ) ⌊τ l/ǫ ⌋,i (H i ; s, a) -ω i l (s, a) f i (z(τ l ), g i (s, a)) ≤ ( L1 + L2 ) ǫ ∆(ǫ) + 2 ∑ i=1 M i E u i ǫ (ω) ζ ∑ s,a φ K(ǫ) ⌊τ l/ǫ ⌋,i (H i ; s, a) -ω i l (s, a) ≤ ( L1 + L2 ) ǫ ∆(ǫ) + 2 ∑ i=1 M i E u i ǫ (ω) ζ E s i l S i ⌊τ l /ǫ⌋ ∑ s,a φ K(ǫ) ⌊τ l/ǫ ⌋,i (H i ; s, a) -ω i l (s, a) ≤ ( L1 + L2 ) ǫ ∆(ǫ) + 2 ∑ i=1 M i µ i (K(ǫ)) (7.36)
where Li = L i 1 + L i 2 (L i j , j = 1, 2, being the constants from (7.33) and ( 7.34)) and M i , i = 1, 2, are the constants from (7.5). The substitution of the latter into (7.31) leads to

E u ǫ (ω) ζ [ ξ l+1 -Z l+1 ] ≤ E u ǫ (ω) ζ [ ξ l -Z l ] + M∆(ǫ)E u ǫ (ω) ζ [ ξ l -Z l ] + ∆(ǫ)κ(ǫ), (7.37)
where lim ǫ→0 κ(ǫ) = 0 and M is an appropriately chosen constant. This implies (see Proposition 5.1 in [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF]) that .38) with lim ǫ→0 ν(ǫ) = 0. By definition, for l = 1, . . . , ℓ(ǫ) -1:

E u ǫ (ω) ζ [ ξ l -Z l ] ≤ ν(ǫ), l = 1, . . . , ℓ(ǫ), ( 7
Z(τ l+1 ) = Z(τ l ) + τ l+1 τ l f 1 (Z(t), Y 1 (t))dt + τ l+1 τ l f 2 (Z(t), Y 2 (t))dt (7.39)
By subtracting (7.28) from ( 7.39), one obtains .40) Note that, due to (7.5),

E u ǫ (ω) ζ Z(τ l+1 ) -Z l+1 ≤ E u ǫ (ω) ζ Z(τ l ) -Z l + (C 1 + C 2 ) τ l+1 τ l Z(t) -Z l dt . ( 7
Z(t) -Z(τ l ) ≤ (M 1 + M 2 )∆(ǫ) ∀t ∈ [τ l , τ l+1 ], (7.41)
Hence, .42) Due to Proposition 5.1 from [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF], the latter implies that there exists an appropriately chosen positive constant M such that .43) By combining (7.27), (7.38), ( 7.43), we may conclude that .44) This and the fact that z(t) -z(τ l ) ≤ M∆(ǫ) ∀t ∈ [τ l , τ l+1 ] imply the validity of (7.19) with some γ(ǫ) such that lim ǫ→0 γ(ǫ) = 0. The validity of (7.20) follows from (7.19) since (see (7.6))

E u ǫ (ω) ζ Z(τ l+1 ) -Z l+1 ≤ E u ǫ (ω) ζ [ Z(τ l ) -Z l + C∆(ǫ) Z(τ l ) -Z l ] + C(M 1 + M 2 )∆(ǫ) 2 . ( 7
E u ǫ (ω) ζ Z(τ l ) -Z l ≤ M∆(ǫ), l = 0, 1, . . . , ℓ(ǫ). ( 7
E u ǫ (ω) ζ z(τ l ) -Z(τ l ) ≤ E u ǫ (ω) ζ { z(τ l ) -ξ l + ξ l -Z l + Z l -Z(τ l ) } ≤ ν(ǫ) + ∆(ǫ) M, l = 0, 1, . . . , ℓ(ǫ). ( 7
|E u ǫ (ω) ζ G i (Z(1)) -G i (z(1))| ≤ C i G E u ǫ (ω) ζ Z(1) -z(1) ≤ C i G γ(ǫ).
Thus, the proof of the proposition is completed.

Proof of Proposition 16. Let h 1 = h ⌊ǫ -1 ⌋,1 0 = (s 1 0 , a 1 0 , . . . , s 1 ⌊ǫ -1 ⌋ , a 1 ⌊ǫ -1 ⌋ ) be a realization of a state-action trajectory of player 1 and let y 1 (t, h 1 ) := g 1 (s 1 ⌊t/ǫ⌋ , a 1 ⌊t/ǫ⌋ ). (7.45) Define the projection of the vector of the state action frequencies φ K(ǫ),1 ⌊τ l /ǫ⌋ (h 1 ) (see (7.21)) onto W 1 by the equation: .46) where K(ǫ) is as in the proof of Proposition 15. Define the function

ω 1 l (h 1 ) := arg min ω 1 ∈W 1 φ K(ǫ),1 ⌊τ l/ǫ ⌋ (h 1 ) -ω 1 . ( 7
ω 1 (t, h 1 ) := {ω 1 l (h 1 ) for t ∈ [τ l , τ l+1 ], l = 1, . . . , ℓ(ǫ)},
and denote by z(t, h 1 ) the solution of the differential equation ż(t, h 1 ) = f1 (z(t, h 1 ), ω 1 (t, h 1 )) + f2 (z(t, h 1 ), ω 2 * (t)). (7.47) continuous in z and linear in ω i , one can obtain .54) By subtracting (7.54) from ( 7.39), one obtains

z(τ l+1 , H 1 ) = z(τ l , H 1 ) + τ l+1 τ l f 1 ( z(t, H 1 ), ω 1 (t, H 1 ))dt + τ l+1 τ l f 2 ( z(t, H 1 ), ω * 2 (t))dt = z(τ l , H 1 ) + ∆(ǫ) f 1 ( z(τ l , H 1 ), ω 1 l (H 1 )) + ∆(ǫ) f 2 ( z(τ l , H 1 ), ω 2 * l )) + O(∆(ǫ) 2 ). ( 7
Z(τ l+1 ) -z(τ l+1 , H 1 ) ≤ Z(τ l ) -z(τ l , H 1 ) + ∆(ǫ) 1 ∆(ǫ) τ l+1 τ l f 1 (Z(t), Y 1 (t)dt -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 )) + ∆(ǫ) 1 ∆(ǫ) τ l+1 τ l f 2 (Z(t), Y 2 (t)dt -f 2 ( z(τ l , H 1 ), ω 2 * l ) + O(∆(ǫ) 2 ) (7.55) By (7.4), 1 ∆(ǫ) τ l+1 τ l f 1 (Z(t), Y 1 (t))dt -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 )) ≤ 1 ∆(ǫ) τ l+1 τ l f 1 (Z(t), Y 1 (t))dt - 1 ∆(ǫ) τ l+1 τ l f 1 ( z(τ l , H 1 ), Y 1 (t)) + 1 ∆(ǫ) τ l+1
τ l f 1 ( z(τ l , H 1 ), Y 1 (t)) -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 ))

≤ 1 ∆(ǫ) τ l+1
τ l f 1 ( z(τ l , H 1 ), Y 1 (t))dt -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 ))

+ C 1 ∆(ǫ) Z(τ l ) -z(τ l , H 1 ) + O(∆(ǫ) 2 ) (7.56) Analogously, 1 ∆(ǫ)

τ l+1 τ l f 2 (Z(t), Y 2 (t))dt -f 2 ( z(τ l , H 1 ), ω 2 * l ) ≤ 1 ∆(ǫ) τ l+1 τ l f 2 (Z(t), Y 2 (t))dt - 1 ∆(ǫ) τ l+1 τ l f 2 ( z(τ l , H 1 ), Y 2 (t))dt + 1 ∆(ǫ) τ l+1 τ l f 2 ( z(τ l , H 1 ), Y 2 (t))dt -f 2 ( z(τ l , H 1 ), ω 2 * l ) ≤ 1 ∆(ǫ) τ l+1 τ l f 2 ( z(τ l , H 1 ), Y 2 (t)) -f 2 ( z(τ l , H 1 ), ω 2 * l )
+ C 2 ∆(ǫ) Z(τ l ) -z(τ l , H 1 ) + O(∆(ǫ) 2 ).

(7.57)

For brevity, let us re-denote u i * ǫ (ω i * ) as u i * ǫ (i = 1, 2). From (7.55), (7.56) and (7.57) it follows that, for any u 1 ǫ ∈ U 1 ,

E u 1 ǫ ,u 2 * ǫ ζ Z(τ l+1 ) -z(τ l+1 , H 1 ) ≤ E u 1 ǫ ,u 2 * ǫ ζ Z(τ l ) -z(τ l , H 1 ) (1 + (C 1 + C 2 )∆(ǫ)) + ∆(ǫ)E u 1 ǫ ,u 2 * ǫ ζ 1 ∆(ǫ) τ l+1 τ l f 1 ( z(τ l , H 1 ), Y 1 (t))dt -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 )) + 1 ∆(ǫ) τ l+1
τ l f 2 ( z(τ l , H 1 ), Y 2 (t))dt -f 2 ( z(τ l , H 1 ), ω 2 * l ) + O(∆(ǫ) 2 ).

(7.58)

Similarly to (7.36), one can obtain

E u 1 ǫ ,u 2 * ǫ ζ 1 ∆(ǫ) τ l+1 τ l f 2 ( z(τ l , H 1 ), Y 2 (t))dt -f 2 ( z(τ l , H 1 ), ω 2 * l ) ≤ L2 ǫ ∆(ǫ) + M 2 E u 2 * ǫ ζ ∑ s,a φ K(ǫ)
⌊τ l/ǫ ⌋,2 (H 2 ; s, a)ω 2 * l (s, a))

≤ L2 ǫ ∆(ǫ) + M 2 E u 2 * ǫ ζ E s 2 l S 2 ⌊τ l /ǫ⌋ ∑ s,a φ K(ǫ)
⌊τ l/ǫ ⌋,2 (H 2 ; s, a)ω 2 * l (s, a))

≤ L2 ǫ ∆(ǫ)
+ M 2 µ 2 (K(ǫ)), (7.59) where L2 and M 2 are the same constants as in (7.36). In an analogous way,

E u 1 ǫ ,u 2 * ǫ ζ 1 ∆(ǫ) τ l+1
τ l f 1 ( z(τ l , H 1 ), Y 1 (t))dt -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 ))

≤ L1 ǫ ∆(ǫ) + M 1 E u 1 ǫ ζ ∑ s,a φ K(ǫ)
⌊τ l/ǫ ⌋,1 (H 1 ; s, a)ω 1 l (s, a; H 1 ) (7.60) where M 1 is the constant from (7.5). From the definition of ω 1 l (H 1 ) = {ω 1 l (s, a; H 1 )} as argmin in (7.46) and from (7.24) (see Lemma 4) it follows that there exists a function μ1 : N → R, with lim K→∞ μ1 (K) = 0 (implying lim ǫ→0 μ1 (K(ǫ)) = 0) such that

E u 1 ǫ ζ ∑ s,a φ K(ǫ)
⌊τ l/ǫ ⌋,1 (H 1 ; s, a)ω 1 l (s, a; H 1 )) ≤ μ1 (K(ǫ)). (7.61) Hence, by (7.60),

E u 1 ǫ ,u 2 * ǫ ζ 1 ∆(ǫ) τ l+1 τ l f 1 ( z(τ l , H 1 ), Y 1 (t))dt -f 1 ( z(τ l , H 1 ), ω 1 l (H 1 )) ≤ L1 ǫ ∆(ǫ)
+ M 1 μ1 (K(ǫ)). [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF], the latter implies that there exists a function η(ǫ), with η(ǫ) → 0, such that ∀l = 1, . . . , ℓ(ǫ),

E u 1 ǫ ,u 2 * ǫ ζ
Z(τ l ) -z(τ l , H 1 ) ≤ η(ǫ). (7.64) Thus, Since, by Proposition (15),

E u 1 ǫ ,u 2 * ǫ ζ {G 1 (Z(1))} -E u 1 ǫ ,u 2 * ǫ ζ {G 1 ( z(1, H 1 ))} ≤ C 1 G η(ǫ) ∀u 1 ǫ ∈ U 1 . ( 7
G * i = lim ǫ→0 E u 1 * ǫ ,u 2 * ǫ s {G i (Z(1))}, i = 1, 2,
the proposition is proved.

Conclusion

In this chapter we presented a non-zero sum dynamic game whose state is described by a hybrid dynamical system that evolves in continuous time and that is subjected to abrupt changes of the parameters. By supposing that the MDPs associated to the jumps of the parameters and the macro state of the system evolve with different velocities, we proved that the state trajectory of the hybrid system can be approximated by the solutions of a certain deterministic averaged control system. We showed how to construct an asymptotic Nash equilibrium Markov policy of the game obtained solving the hybrid system, on the basis of a Nash equilibrium of the game obtained solving the deterministic averaged system.

Chapter 8

Conclusions and Future Perspectives

Summary of Contributions

In this dissertation we investigated different theoretical aspects of EGT, with a particular focus on the notion and the characterization of the player. We followed two major directions: we first revisited the classical idea of individual-selfish players, defining a model for group-players, and we then focused on games combining standard EGT and MDP, which allows one to characterize players through an individual state evolving in time, beside the action used. We also suggested various scenarii which provide useful applications for our models, particularly in telecommunication networks.

More precisely, in Part I we proposed our new approach to evolutionary games to represent those situations in which individuals interact, maximizing the fitness of the group they belong to. Therefore, the actual players of a game are not the interacting individuals but the groups. We studied a simple but meaningful example with two pure actions, the Hawk-Dove game, in two cases, respectively a finite and an infinite population of individuals, divided into a finite number N of symmetric groups of the same size. As the number of players is finite, we considered the Nash equilibrium as solution concept (rather than the ESS). Moreover, since the Nash equilibrium is a multiaction such that no player can profit by deviating, in our group-players context, it is stable against deviations of a share of individuals, since the player consists in a whole group of individuals. We verified that the Hawk-Dove group-players game (in both the finite and the infinite population case) is convex, which allowed us to prove the existence and the uniqueness of the equilibrium through Rosen's conditions [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave n-person games[END_REF]. We then explicitly computed the symmetric mixed Nash equilibra, showing how the presence of groups plays an important role for the equilibrium structure. In particular, we showed that, for the two group-players game, the level of aggressiveness at the equilibrium is lower than in the standard Hawk-Dove game. We finally defined a gradient-based dynamics, such that the equilibria obtained are asymptotically stable for this dynamics.

We then extended the group players model to a more general framework, where the N groups have different sizes and dispose of a finite set of pure actions. We presented a new solution concept, the GFESS, implying stability against local deviations within each group. For the particular case of two pure actions games, we provided a detailed characterization of the GFESSs and we illustrated our results studying three classical examples considering group-players, the Hawk-Dove game, the Stag Hunt game and the Prisoner's Dilemma, through which we showed that the presence of groups impacts the equilibrium output. We then further generalized our model by redefining the fitness of a group, assuming that the immediate payoff associated with the pairwise interactions among individuals in the same group differs from that of inter-group interactions. We applied this model to a MAC problem, where we studied the impact of groups on mobiles behavior.

In the second part of the dissertation, we considered a particular class of evolutionary games, the MDEG, where each (individual) player is characterized by a state. The action played by an individual not only determines its immediate fitness but it also impacts the transition probabilities to the individual's next state. Furthermore, the fitness of a player does not only depend on its action and on the distribution of actions in the population, but also on the distribution of individual states. We proposed a new dynamical approach to this type of games, focusing on the dynamics involved. We defined the interdependent dynamics of the policies distribution and of the individual states, where the first is assumed to follow the well-known replicator dynamics.

For a particular game with two states and two pure actions, we proved the correspondence between stable rest points of the dynamics and the equilibrium profiles of the evolutionary game. Under the assumption that the two dynamics evolve with different timescales, we proposed two methods to obtain the rest points. We gave a complete characterization of these equilibrium profiles and we showed that these equilibria are equivalent in terms of average sojourn times and expected fitnesses. Finally, we illustrated our model through two application scenarii in network systems.

We then defined a particular Hawk-Dove game in a MDEG type of framework, where an individual may be in one of four possible states, representing its age and its strength.

In contrast with standard MDEG, in this particular example, we supposed that the transition probabilities of a player do not depend on its action but on the action chosen by 126 8.2. Perspectives its opponent. By considering stationary policies and supposing that the distribution of the individual states is stationary, we transformed the dynamic Hawk-Dove into a standard evolutionary game and we computed its Nash equilibria. We then further extended our dynamic Hawk-Dove game, by considering group-players as presented in Chapter 2. We showed that, for a two groups game with fixed values of the parameters, the presence of groups in the dynamic Hawk-Dove game brings important novel features with respect to the individual-player game, as the fact that the non-aggressive pure policy can be an equilibrium. We also compared the mixed equilibria obtained respectively for the individual-players and group-players games and we obtained that, also in this case, the probability of being aggressive in strong adult state is lower for group-players.

Finally, we presented a different problem which is not directly related to evolutionary games but which is connected to the dynamic approach adopted for MDEG problems.

In particular, we studied a non-zero sum dynamic game whose state is described by a hybrid dynamical system that evolves in continuous time and that is subjected to abrupt changes of the parameters. By supposing that the MDPs associated with the jumps of the parameters and the macro state of the system evolve with different velocities, we proved that the state trajectory of the hybrid system can be approximated by the solutions of a certain deterministic averaged control system. in particular, we show that an asymptotic Nash equilibrium of such hybrid game can be constructed on the basis of a Nash equilibrium of the deterministic averaged dynamic game.

Perspectives

Group-players evolutionary games leave many issues open for future studies. We have introduced a gradient based dynamics for the Hawk-Dove group-players game. We may define a dynamics in the general group-players framework, comparing different possible dynamics (gradient based, replicator, etc.). Following the folk theorem approach for standard evolutionary games, we could then establish the relation between rest points and equilibria. We may also unify the two lines of research presented here by considering group-players in a MDEG framework, as we did in Chapter 6 for a particular Hawk-Dove dynamic game. The notion of the player can be further investigated.

We may consider the case of a population of individuals divided into groups, where the interacting individuals maximize a fitness function which considers both an individual and a group component. It would be interesting also to consider a population which is composed, at the same time, by group-players and individual players, i.e. where some individuals maximize the fitness of the group they belong to, while others maximize their own fitness, and then to define a suitable notion of equilibrium in this context.

Also the SPcD and, more generally, MDEG problems offer various possible direction for forthcoming developments. In standard MDEG and in our dynamical model we supposed that, respectively, transition probabilities and transition rates only depend on the action of the player. In future works we propose to relax this assumption, letting these functions depend on the actions of both individuals involved in an interaction.

Moreover, we may extend our results concerning SPcD to a more general framework, characterizing the states and policies interdependent dynamics for games with more than two states and two pure actions. A major effort should be done in unifying the different classes of stochastic games into a comprehensive theory. As a matter of fact, as we have already mentioned, different classes of games dealing with stochastic processes have been defined in the literature, as stochastic (evolutionary) games (Shapley, 1953) [START_REF] Flesch | Evolutionary Stochastic Games[END_REF], anonymous sequential games [START_REF] Jovanovic | Anonymous sequential games[END_REF] , mean-field stochastic games [START_REF] Weintraub | Oblivious equilibrium: A mean field approximation for large-scale dynamic games[END_REF] [START_REF] Tembine | Mean field stochastic games: Convergence, q/h-learning and optimality[END_REF], mean-field stochastic differential games [START_REF] Lasry | Mean field games[END_REF] [START_REF] Guéant | Mean field games and applications[END_REF]. It would be interesting and useful to deeper explore the relation between these types of games and see whether they can all be thought as different subclasses of a more general class of games.

As regards the hybrid stochastic system, in this dissertation we analyzed the open loop information structure case, which means that the player has no information about the state of the system, but only on its state and (eventually) its history. We are currently working to extend this model to the feedback information structure case, where, at each instant of time both players know exactly to which (macro) state the game has evolved and policies are determined as functions of this information. In order to generalize our results to the closed-loop case, we need to prove that the results in Lemma 4 still hold.

Another direction that we would like to investigate in future works is the study of a hybrid stochastic system where the parameters evolve according to CT-MDPs, instead of discrete time processes. This would lead to a framework very close in nature to the one presented in Chapter 5, where we study the interdependent dynamics of individual states and policies distributions and we assume a two timescale behavior of the system.

We may thus be able to combine hybrid stochastic dynamical system and EGT.

3.1

The population of individuals is divided into a finite number of groups G i , i = 1, . . . , N. Each individual can interact with a member of its group or of a different one. All individuals in G i adopts the same strategy q i (no matter which individual they encounter). . . . . . . . . . . . . . . . . . .

3.2

The fully mixed equilibrium actions q 1 * (upper line) and q 2 * (lower line), respectively of the first and the second group for 0.3 < α < 0.5 for the two group-players Hawk-Dove game. . . . . . . . . . . . . . . . . . . . .

3.3

When a mobile k transmits, all mobiles within a circle of radius R centered at node R(k) cause interference to k for its transmission to R(k), so that more than one transmission within a distance R of the receiver in the same slot causes a collision and the loss of mobile's k packet at R(k). A transmitter in group G i transmits with probability p i ∈ [0, 1], i = 1, . . . , N.

3.4

The value of the equilibrium strategy q * in a two symmetric groups MAC game as a function of γ for α = 0.4, compared to the ESS q * std of the standard game. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 The value of the equilibrium strategy of the second group in the fully mixed equilibrium (q 1 * , q 2 * ) and in the mixed equilibrium (T, q T * ) as a function of γ for α = 0. x = 0.71875, obtained by setting µ = 10, µ x = 1.5 and µ y = 1, and a = -0.3, c = 0, b = 1 and d = 0.5, starting from q x (0) = 0.2 and q x (0) = 0.9. . . . . . . . 5.4 Energy control in wireless networks. Each mobile continuously moves from full battery state (F) to almost empty battery state (A) and then back to F. If the mobile chooses policy u h (left side), in state F it transmits at high power (h), otherwise, if it chooses policy u l it transmits at low power (l) (right side). In state A, it always transmits at low power. Since high power transmission is costly in terms of energy consumption, when transmitting at high power, the transition rate to state A is faster, and thus the time spent in state F is shorter. . . . . . . . . . . . . . . . . . . .

  Un joueur interagit à répétition avec d'autres joueurs, et il change d' états. L'action choisie détermine son fitness et aussi la probabilité de transition à l'état suivant. En considérant des politiques stationnaires, Altman et Hayel montrent que, si la distribution sur les états est stationnaire par rapport à la politique choisie, il est possible de transformer le jeu MDEG dans un jeu évolutionnaire standard et calculer ses ESSs. v Motivés par l'importance de comprendre les dynamiques qui amènent à une situation stable, nous présentons ici une nouvelle approche dynamique des MDEG. À différence de l'approche statique adopté par Altman et Hayel, en ce travail nous considérons les dynamiques des états individuels et couplée avec les politiques et nous les décrivons à travers des équations différentielles interdépendantes. Dans la troisième partie du manuscrit, nous poursuivons l'étude des jeux stochastiques dynamiques dans un contexte différent, la théorie du contrôle. Nous définissions un système stochastique dynamique contrôlé simultanément par deux joueurs engagés dans un jeu à somme non nulle (et non constante) et nous montrons que le problème stochastique peut être approximé à travers un jeu dynamique déterministe. vi Introduction xii

  uses game theory terminology to study the sex ratio of species, in situations where certain underlying assumptions of Fisher's argument do not hold. He models the choice of the sexes of offspring of an individual as the choice of an action in a game and defines the concept of unbeatable strategy, which is very close to the notion of evolutionarily stable strategy, the key equilibrium concept introduced by Maynard Smith and Price, (Maynard Smith and Price, 1973) which marks the official birth of EGT. The authors study animals' conflicts as games, where actions are behavioral phenotypes and the payoff represents the fitness, i.e. the number of offspring of an individual. With his treatise Evolution and the Theory of Games (Maynard Smith, 1982), Maynard Smith brings EGT into widespread circulation.

Figure 2 . 1 :

 21 Figure 2.1: Individuals are divided into a finite number of symmetric groups. Each individual can interact with a member of its own group or of a different one.

Figure 2 .

 2 Figure 2.2 shows the probability of being aggressive p * at the equilibrium, as a function of the number of players N in an infinite population of individuals, plotted for three different values of the cost δ (involved in an encounter between two aggressive individ-

Figure 2 . 2 :

 22 Figure 2.2: The value of p * as a function of the number of groups 2 ≤ N ≤ 20 for three different values of δ. The upper dashed curve is obtained with δ = 0.6, the middle curve with δ = 1 and the lower dotted one with δ = 4.

Figure 2 . 3 :Figure 2 . 4 :

 2324 Figure 2.3: The value of p * as a function of the number of groups 0 ≤ N ≤ 20 for three different values of K and δ = 2. Upper dashed line is obtained with K = 2, middle line with K = 10 and lower dotted line with K = 70.

  Figure 3.2:The fully mixed equilibrium actions q 1 * (upper line) and q 2 * (lower line), respectively of the first and the second group for 0.3 < α < 0.5 for the two group-players Hawk-Dove game.

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4:The value of the equilibrium strategy q * in a two symmetric groups MAC game as a function of γ for α = 0.4, compared to the ESS q * std of the standard game.

Figure 3 . 6 :

 36 Figure 3.6: The value of the equilibria of the two groups in a two groups MAC game as a function of γ for α = 0.4

  which is bilinear in the occupation measures. They then define the weak ESS, related to the notion of equivalent class in terms of occupation measure. They show how to transform a MDEG into a standard evolutionary game and to compute the equilibria.While Altman and Hayel focus on a static definition of the ESS in MDEG framework, in the next chapter we consider MDEG from a dynamical point of view. We associate each player to continuous time MDP and we model the interdependent dynamics of individual states and policies.

  Figure 5.1:A player can choose between policy u x and u y . Accordingly with this choice, in state 1 the individual plays, respectively x or y and move to state 0, at a rate µ x or µ y . In state 0, under both policies, the only available action is y and the rate at which the player returns to state 1 is µ.

Figure 5 . 2 :

 52 Figure 5.2: Trajectories of the system (S ǫ ) from different starting points and the slow manifold M 0 for ǫ = 0.01.

Figure 5 . 3 :

 53 Figure 5.3: Convergence of the replicator dynamics to the equilibrium δ *x = 0.71875, obtained by setting µ = 10, µ x = 1.5 and µ y = 1, and a = -0.3, c = 0, b = 1 and d = 0.5, starting from q x (0) = 0.2 and q x (0) = 0.9.

Figure 5 . 4 :

 54 Figure 5.4: Energy control in wireless networks. Each mobile continuously moves from full battery state (F) to almost empty battery state (A) and then back to F. If the mobile chooses policy u h (left side), in state F it transmits at high power (h), otherwise, if it chooses policy u l it transmits at low power (l) (right side). In state A, it always transmits at low power. Since high power transmission is costly in terms of energy consumption, when transmitting at high power, the transition rate to state A is faster, and thus the time spent in state F is shorter.

  study a repeated version of the Hawk-Dove game, where each bird is associated with a state variable representing animal's level of energy evolving in time as a Markov Process. The action played by an animal depends on its reserve of energy and the fitness function depends on the average level of aggressiveness in the population. Birds are supposed to choose their policy in order to minimize the probability of dying during a period of time, and the ESS is in the form: "play Hawk if and only if reserves are below a critical level of the energy resources c * (t)". McNamara et al. (McNamara

  (see the Introduction to the previous chapter), where the authors present a simple application of MDEG to mobile communications. As in our case, individuals can choose among an aggressive and a non-aggressive action only in one of the possible individual states, while in the others, only non-aggressive one is allowed.

Figure 6 . 1 :

 61 Figure 6.1: The equilibrium q v * plotted as a function of the proportion P(A) of adults in the population for different values of δ. The higher line is obtained with δ = 4, the middle line with δ = 6, the lower one with δ = 10.

Figure 6

 6 Figure 6.2:The equilibrium q v * as a function of the value of δ for different values of P(A). The higher line is obtained with P(A) = 0.15, the middle line with P(A) = 0.5, the lower one with P(A) = 0.88.

Figure 6 . 3 :Figure 6 . 4 :

 6364 Figure 6.3:The probability of being aggressive in state A S at the equilibria, obtained with N = 2, P(A) = 0.5 and ∆ = 1, as a function of the cost δ.

  l+1 ) -z(τ l+1 , H 1 ) ≤ (1 + C∆(ǫ) = 0. By virtue of Proposition 5.1 in

  z(1, H 1 )) ≥ G 1 * + O(∆(ǫ)),

Information

  are divided into a finite number of symmetric groups. Each individual can interact with a member of its own group or of a different one. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The value of p * as a function of the number of groups 2 ≤ N ≤ 20 for three different values of δ. The upper dashed curve is obtained with δ = 0.6, the middle curve with δ = 1 and the lower dotted one with δ = 4. 2.3 The value of p * as a function of the number of groups 0 ≤ N ≤ 20 for three different values of K and δ = 2. Upper dashed line is obtained with K = 2, middle line with K = 10 and lower dotted line with K = 70. . . . 2.4 The value of p * as a function of the size of groups 1 ≤ K ≤ 50 for three different values of N. Upper dashed line is obtained with N = 2, middle line with N = 10, lower dotted line with N = 70. . . . . . . . . . . . . . .

3. 5

 5 The probability p S (q * ) of a successful transmission at the equilibrium for the fully mixed GFESS in a two symmetric groups MAC game and in the standard game, as a function of γ. . . . . . . . . . . . . . . . . . . . . . . 3.6 The value of the equilibria of the two groups in a two groups MAC game as a function of γ for α = 0.4 . . . . . . . . . . . . . . . . . . . . . . . . .

  4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Each mobile can be in full or in almost empty battery state. In state full, it can choose to transmit ah high power or at at low power, while, if the battery is almost empty, it can only transmit at low power. If a destination receives simultaneously a transmission from two terminal, packets collide, but one of the packets can still be received correctly if transmitted at a higher power. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 A player can choose between policy u x and u y . Accordingly with this choice, in state 1 the individual plays, respectively x or y and move to state 0, at a rate µ x or µ y . In state 0, under both policies, the only available action is y and the rate at which the player returns to state 1 is µ. . . . . . 5.2 Trajectories of the system (S ǫ ) from different starting points and the slow manifold M 0 for ǫ = 0.01. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Convergence of the replicator dynamics to the equilibrium δ *

  mixed actions;

	ANE: Asymptotic Nash Equilibrium
	CT-MDP: Continuous Time Markov Decision Process
	EGT: Evolutionary Game Theory
	ESS: Evolutionarily Stable Strategy
	GFESS: Group Fitness Evolutionarily Stable Strategy
	GT: Game Theory
	MAC: Multiple Access Control
	MDP: Markov Decision Process
	NE: Nash Equilibrium
	SPcD: State Policy couple Dynamics

S: set of individual states, with |S| = K; U : set of general policies; U M : set of Markov policies; U S : set of stationary policies; U D : set of deterministic (stationary) policies; F(•, •): fitness function of an individual; F(•): average fitness in the population;

Γ i (•, •): fitness function of a group player G i ; α i : normalized size of a group i; Q: set of transition probabilities; Q s (s ′ , a) (homogeneous time) transition probability from state s ′ ∈ S to state s ∈ S given action a ∈ A; R set of transition rates; R s (s ′ , a) transition rate from state s ′ ∈ S to state s ∈ S given action a ∈ A; T s (u): average time that an individual playing deterministic policy u ∈ U D spends in state s ∈ S; H: set of all observable state-action histories h t = {s l , a l , l = 0, . . . , t}, t = 0, 1, 2, . . .; W = u s ∈U S ω(u s ): set of all vectors of steady state probabilities of state action pairs. xvii Part I

Acknowledgements

Part II

Individual State and Policy Dynamics in Evolutionary Games

Applications MDEG can find a wide range of applications in different fields. Altman and Hayel present a simple application of MDEG to mobile communications in (Altman and Hayel, 2008), where mobile terminals transmit packets occasionally and their destination may occasionally receive simultaneously a transmission from another terminal which results in a collision. When packets collide, one of the packets can still be received correctly if transmitted at a higher power. Successful transmissions is rewarded, but energy consumption is penalizing. The action corresponds to the choice of power transmission level, and the set of available actions depend on the individual state of the player, which consists in the level of the battery. The state can be either full, in which case there are two transmitting power levels available, or almost empty in which only the weak power level is available. Transmission at high power is costly in terms of energy consumption and thus it results in a higher probability of moving to the lower energy level.

The authors define the fitness of a terminal as the total number of packets successfully transmitted during its lifetime and characterize the ESS in this context. In state full, it can choose to transmit ah high power or at at low power, while, if the battery is almost empty, it can only transmit at low power. If a destination receives simultaneously a transmission from two terminal, packets collide, but one of the packets can still be received correctly if transmitted at a higher power.

In Chapter 5 we'll develop the dynamical aspect related to MDEG theory, studying the interdependent dynamics of individual states and policies, where players are supposed to control a continuous time MDP and we illustrate other possible application fields. In Chapter 6 we'll see a particular dynamic version of the Hawk-Dove game in a MDEG kind of framework.

Chapter 5

State Policy Couple Dynamics "We repeat most emphatically that our theory is thoroughly static. A dynamic theory would unquestionably be more complete and preferable." Von Neumann and Morgenstern, Theory of Games and Economic Behavior, 1953

Summary

In this chapter, we present a new dynamical approach to MDEG, where individual states are supposed to evolve in time according to a continuous time MDP. We introduce the concept of interdependent dynamics of states and policies in a general framework, and we then define the State Policy coupled Dynamics (SPcD) in a simple case, in order to find closed-form solutions and to establish the relation between the equilibria of the defined system of differential equations and the equilibria of the game. These solutions are obtained by assuming that the processes of states and policies move with different velocities, which allows us to apply two different approximation techniques: the singular perturbation method, and a matrix approach.

Matrix Game Approximation Technique

In alternative to the singular perturbation method, when assuming the two time-scales behavior of the SPcD system, one can consider the distribution over individual states to be stationary and then solve the obtained standard normal form game. In particular, by following the approach used in [START_REF] Altman | Markov decision evolutionary games[END_REF], we can rewrite the two states and two actions model as a matrix game, where individuals play deterministic policies instead of actions. We get the following payoff bimatrix:

where F(u i , u j ) is the expected fitness of an individual playing pure policy u i against an individual using u j , with i, j ∈ {x, y}. Note that, as showed in (Altman and Hayel, 2010), it is possible to apply this matrix game approach to the general model with M actions and K states but, in this case, the size of the matrix would be of dimension D × D, where D is the number of deterministic policies. We restrict here our analysis to the two actions/states case in order to compare the equilibrium obtained with the two approaches.

The stationary distributions in states 1 and 0 are given respectively by the following average sojourn times:

where i ∈ A denotes the choice of policy u i . The expected fitness F(u i , u j ) can be expressed as a function of these average sojourn times as follows: (6.4) and F(W, u, v) is the immediate expected fitness of a weak adult (A W ):

Note that the fitness of a weak adult F(W, v) does not depend on the policy u, as a weak adult always plays D. By substituting the expressions (6.4) and (6.5) in ( 6.3) we obtain:

where α S (v) = P(A)

. By definition we have that

, which leads to:

In the following theorem we present the symmetric equilibrium of the game, which depends on the value of the cost of the fight δ. We obtain that, if the the cost of the fight is below a certain threshold δ * the deterministic symmetric equilibrium policy is u H . If the cost is strictly higher than δ * , the symmetric equilibrium is given by a mixed policy v * . Theorem 5. Given the game described in Section 6.2 we have that:

i. if δ ≤ δ * the unique symmetric equilibrium is the deterministic policy u H ;

ii. if δ > δ * the unique symmetric equilibrium is the stationary policy v * such that

, (6.8) where:

Proof. We first look for the equilibrium in pure actions. If the population's policy is v = u D (i.e. all individuals in the population plays pure action D in state A S ), we obtain that:

By substituting these values and q v = 0 in equation ( 6.7) we get:

. ( 6.9)

Note that F(u, u D ) is increasing in q u , and thus u D (corresponding to q u = 0) is never an equilibrium.

We consider the case v = u H . We have that:

.

By substituting these values, q v = 1 and, respectively q u = 0 and q u = 1 in 6.7 we get:

The aggressive deterministic policy u H is an equilibrium only if the inequality F(u H , u H ) ≥ F(u D , u H ) holds. We have that:

The latter inequality is satisfied if and only if

We thus obtain that the aggressive behavior u H is an equilibrium in deterministic policies if and only if δ ≤ 1 + P(A) 2P(A) , which proofs the first statement of the theorem.

We now apply the indifference principle to find the equilibrium in mixed policies. By substituting q u = 0 in (6.7) we obtain:

For policy u H , equation (6.7) becomes:

We impose the indifference among the two possible pure policies of the first player, i.e.

and we find the following value:

By imposing these constraints on (6.8), we get δ > 1 + P(A) 2P(A) , which completes the proof.

In figure 6.1 we plot the equilibrium probability q v * , i.e. the probability of being aggressive in state A S at the equilibrium defined in (6.8), as a function of the proportion P(A) of adults in the population, for three different values of δ. The continuous higher line is obtained with δ = 4, the dotted line with δ = 6, the continuous lower one with δ = 10.

As expected we can observe that q v * is a decreasing function of P(A): this means that the higher the proportion of adults in the population is, the lower is the probability of being aggressive. As a matter of fact, the aggressive behavior of strong adults is rewarding only when adopted against a non-aggressive individual, while it is costly if adopted against another aggressive adult. In figure 6.2, q v * is plotted as a function of the threshold δ * . The continuous higher line is obtained with P(A) = 0.15, the dotted line with P(A) = 0.5, the continuous lower one with P(A) = 0.88. As the value of δ * represents the cost of the fight between two aggressive adults, as expected, we can see that q v * is decreasing in δ * . Remark 7. We observe that the equilibrium value q v * , corresponding to the probability of playing aggressively in state A S , does not coincide with the mixed Nash equilibrium q * = 1 2δ of the standard Hawk-Dove game, even when x → 1, so that P(A) ≃ 1. As a matter of fact, even if there are almost only adult individuals in the population, the fraction of weak adults may not be negligible, and thus we still may have a populations with two types of adults.

The Dynamic Hawk-Dove Game and Group Players

We now reformulate this Hawk-Dove game, considering groups players, as presented in Chapter 2. States are associated with individuals within a group, which are randomly matched in pairwise interactions, but the rules that determine their policy are erage probability of being aggressive in state A S in the population. These probabilities are given, respectively by:

where ū is the mixed policy such that u(H|A S ) = qu . These quantities can be rewritten as: .11) We suppose that the entire population chooses the same stationary policy u ∈ U S , except for a fixed group i playing u i ∈ U S . We have that: qu = q u i + (N -1)q u N .

Group Fitness and Equilibria

We associate to pairwise interactions among individuals the payoff matrix defined in Section 6.2. The expected fitness during the lifetime of a group-player i choosing policy u i ∈ U S , in a population adopting policy u ∈ U S is given by:

where:

is the expected immediate fitness of a strong adult in group i, playing policy u i against a population playing u and

is the expected immediate fitness of a weak adult in a population whose policy is u.

Quantities α S ( ū) and α S ( ū) are defined in (6.10) and (6.11) with qu = q u i + (N -1)q u N , while 1/N and N -1/N are, respectively, the probability for a player of meeting an opponent in the same group and in a different group.

In order to obtain insight on the impact of the groups on the equilibrium, we shall focus on some particular values of the parameters. We consider the case of two groups (N = 2) and we further fix ∆ = 1 and P(A) = 0.5, which means that there's an equal share of young and adult individuals in the population. We first look at symmetric equilibria in deterministic policies and we obtain that, if the cost of the fight is higher than a certain threshold, the deterministic policy u D is an equilibrium, while, if the cost is low enough, the deterministic equilibrium policy is u H . This result is presented in the following theorem. Theorem 6. Given the group-players dynamic Hawk-Dove model, with N = 2, P(A) = 0.5 and ∆ = 1, the equilibrium in deterministic policy is:

• u H for δ < 1.05;

• u D for δ > 1.333.

Proof. Let us first consider a non aggressive population, i.e. u = u D . We substitute q u = 0 in (6.12) and we compare the results obtained for the two possible response of the tagged group i, u i = u D and u i = u H .

We compute the difference:

If the population is aggressive, i.e. if u = 1, we have that:

In this case:

By substituting ∆ = 1 and P(A) = 0.5in (6.13) and in (6.14), we obtain respectively:

We now consider also symmetric mixed policies. We obtain that, if the cost is higher that a certain value, the group-players Hawk-Dove dynamic game admits a symmetric mixed (stationary) policy equilibrium u * . We resume our results in the following theorem.

Theorem 7. The group-players dynamic Hawk-Dove model, for the fixed values of the parameters N = 2, P(A) = 0.5, ∆ = 1, admits the following equilibria:

i. the deterministic policy u H for 0.5 < δ < 1.05 ;

ii. the stationary policy u * for δ ≥ 0.8125, with:

iii. the deterministic equilibrium policy u D for δ ≥ 1.333.

Proof. By substituting the values of N = 2, P(A) = 0.5 and ∆ = 1 in 6.12, we obtain:

We compute the derivative:

and, by imposing ∂Γ(u i , u) ∂u i = 0, we find:

We now impose the symmetry q u i = q u and we obtain the two solutions:

The second solution q u 2 is always negative and thus it is not acceptable, while the first solution satisfies 0 < q u 1 < 1 iff δ > 0.8125. We set q u * = q u 1 and we define by u * the policy corresponding to play H with probability q u * in state A S . This completes the proof.

From Theorem 7, we can observe that it is possible to determine two intervals of the values of the cost δ (involved in a fight between two aggressive strong adults), in which we have two equilibria. More precisely, we can observe that:

• for 0.5 < δ ≤ 0.8125 the game admits one deterministic equilibrium policy u H ;

• for 0.8125 < δ ≤ 1.05 the game admits two equilibria, the deterministic u H and the mixed u * ;

• for 1.05 < δ < 1.333 the game admits one mixed equilibrium u * ;

• for δ ≥ 1.333 the game admits one deterministic equilibrium policy u D .

In figure 6.3 we plot the probability of being aggressive in state A S at the equilibrium, as a function of the cost δ. In figure 6.4 we compare the mixed equilibrium policies obtained for the dynamic Hawk-Dove game, respectively for group-players and for individual-players. We can observe that the probability of being aggressive (in state

A S ) at the equilibrium is lower for group-players. This is coherent with what we found in chapter 2.

Conclusion

We revisited in this chapter the Hawk-Dove game in a MDEG framework. In this context an individual may be in one of several states, and the actions played by individuals

Summary

In this chapter we extend the theory of control of an hybrid stochastic dynamical system to the case of a two players non-zero sum game. The system evolves in continuous time and it is subjected to abrupt changes of the parameters, determined by two (discrete time) Markov decision processes, each of which is controlled by a player that aims at minimizing its objective function. As we did in Chapter 5, we assume a two time scale behavior of the system: the lengths of the time intervals between the "jumps" of the parameters are assumed to be small, which means that parameters evolve faster than the state of the system. This allows us to approximate the hybrid game with a deterministic averaged dynamic game. We prove that an asymptotic Nash equilibrium of such hybrid game can be constructed on the basis of a Nash equilibrium of a deterministic averaged dynamic game.

provided that the current state of system i is s ∈ S i , its next state will be s ′ ∈ S i with the probability

A policy u i = {u i 0 , u i 1 , . . . , u i j , . . . , u i ⌊ǫ -1 ⌋ } of the player i is a sequence of probability measures on A i chosen as functions of the present state of the player and of its states/actions history. That is, u i 0 = u i 0 (s i 0 ) and u i j+1 = u i j+1 (h j,i 0 , s i j+1 ), where h j,i 0 is the states/actions history of the i th system/player from time 0 to time t: h j,i 0 := (s i l , a i l , l = 0, ..., j), j = 1, ..., ⌊ǫ -1 ⌋, i = 1, 2. (7.2)

Let U i stand for the set of all such policies and let F i be the discrete σ-algebra of all subsets of H i , which is the set of all possible states-actions histories of player i that can be observed until time ǫ -1 . Each initial distribution β of the initial states (s 1 0 , s 2 0 ) and a policies pair (u 1 , u 2 ) ∈ U 1 × U 2 uniquely define a probability measure P (u 1 ,u 2 ) β over the space of samples H := H 1 × H 2 equipped with the discrete σ-algebra

Denote by E (u 1 ,u 2 ) β the corresponding expectation operator. When the distribution of the initial states is concentrated on a single states pair ζ = (ζ 1 , ζ 2 ), we shall denote the corresponding probability measure and the mathematical expectation operator as

Let g i : S i × A i → R N i be a given vector function and let S i j and A i j , j = 0, 1, . . . , ⌊ǫ -1 ⌋, be the state-action processes of the system/player i. Then Y i (t) in (7.1) are defined by the equations Y i (t) = g i (S i ⌊t/ǫ⌋ , A i ⌊t/ǫ⌋ ), i = 1, 2. (7.3) Note that the dynamics of the state vector Z(t) is fully determined by the states/actions realizations {S i j , A i j }, i = 1, 2. For convenience, Z(t) will be referred to as a "macro state" vector of the system and {S i j } will be referred to as "micro states" of the players i = 1, 2.

Along with the class of policies U := U 1 × U 2 described above, we will be dealing with two other classes of policies U M := U M 1 × U M 2 and U S := U S 1 × U S 2 , where U M i and U S i (i = 1, 2) are defined as follows:

• U M i is the set of Markov policies of the player i such that, at every moment t j = jǫ of decision making, the probability measure u i j on A i is chosen as a function of two arguments, one being the current moment of time and the other being the current micro state of the player i.

• U S i is the set of stationary policies of the player i. That is, it is the set of policies Define the piecewise constant function ω2 * (t) = {ω 2 * l for t ∈ [τ l , τ l+1 ], l = 1, . . . , ℓ(ǫ)},

where ω 2 * l := 1 ∆(ǫ) τ l+1 τ l ω 2 * (t)dt. Let z(t, h 1 ) be the solution of the following differential equation ż(t, h 1 ) = f1 ( z(t, h 1 ), ω 1 (t, h 1 )) + f2 ( z(t, h 1 ), ω2 * (t)). (7.48) By subtracting (7.47) from (7.48) (and having in mind linearity of f 2 (z, ω 2 ) in ω 2 )), one obtains

where M is an appropriate positive constant. Due to Proposition 5.1 in [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF], the latter implies that z(τ l , h 1 ) -z(τ l , h 1 ) ≤ M∆(ǫ) ∀l = 1 . . . , ℓ(ǫ), (7.49) which, in turn, implies that max t∈[0,1] z(t, h 1 ) -z(t, h 1 ) ≤ M∆(ǫ), (7.50) and, by (7.6), .51) Due to the Definition 9 of the Nash equilibrium ,

.53)

Let H 1 be a random realization of h 1 . Using the fact that f i (z, ω i ) (i = 1, 2) are Lipschitz

Conclusions

List of Publications

Journal Papers The equilibrium q v * plotted as a function of the proportion P(A) of adults in the population for different values of δ. The higher line is obtained with δ = 4, the middle line with δ = 6, the lower one with δ = 10. . . . . 98 6.2 The equilibrium q v * as a function of the value of δ for different values of P(A). The higher line is obtained with P(A) = 0.15, the middle line with P(A) = 0.5, the lower one with P(A) = 0.88. . . . . . . . . . . . . . . . . 98 6.3 The probability of being aggressive in state A S at the equilibria, obtained with N = 2, P(A) = 0.5 and ∆ = 1, as a function of the cost δ. . . . . . . 103 6.4 The equilibrium value q u * as a function of the value of δ . . . .