As systems are becoming larger, it is becoming difficult to optimize them in a centralized manner due to insufficient backhaul connectivity and dynamical systems behavior. In this thesis, we tackle the above problem by developing a distributed strategic learning framework for seeking Nash equilibria under statedependent payoff functions. We develop a discrete time stochastic learning using sinus perturbation with the realistic assumption, that each node only has a numerical realization of the payoff at each time. We examine the convergence of our discrete time algorithm to a limiting trajectory defined by an ordinary differential equation (ODE). Finally, we conduct a stability analysis and apply the proposed scheme in a generic wireless networks. We also provide the application of these algorithms to real world resource utilization problems in wireless. Our proposed algorithm is applied to the following distributed optimization problems in wireless domain. Power control, beamforming and Bayesian density tracking in the interference channel.

We also consider resource sharing problems in large scale networks (e.g. cloud networks) with a generalized fair payoff function. We formulate the problem as a strategic decision-making problem (i.e. a game). We examine the resource sharing game with finite and infinite number of players. Exploiting the aggregate structure of the payoff functions, we show that, the Nash equilibrium is not an evolutionarily stable strategy in the finite regime. Then, we introduce a myopic mean-field response where each player implements a mean-field-taking strategy.

We show that such a mean-field-taking strategy is evolutionarily stable in both finite and infinite regime. We provide closed form expression of the optimal pricing that gives an efficient resource sharing policy. As the number of active players grows without bound, we show that the equilibrium strategy converges to a mean-field equilibrium and the optimal prices for resources converge to the optimal price of the mean-field game. Then, we address the demand satisfaction iv v problem for which a necessary and sufficiency condition for satisfactory solutions is provided.

Resumé

Dans ce travail, notre contribution est double. Nous développons un cadre d'apprentissage stochastique distribué pour la recherche des équilibres de Nash dans le cas de fonctions de paiement dépendantes d'un état. La plupart des travaux existants supposent qu'une expression analytique de la récompense est disponible au niveau des noeuds. Nous considérons ici une hypothèse réaliste où les noeuds ont seulement une réalisation quantifiée de la récompense à chaque instant et développons un modèle stochastique d'apprentissage à temps discret utilisant une perturbation en sinus. Nous examinons la convergence de notre algorithme en temps discret pour une trajectoire limite définie par une équation différentielle ordinaire (ODE). Ensuite, nous effectuons une analyse de la stabilité et appliquons le schéma proposé dans un problème de commande de puissance générique dans les réseaux sans fil. Nous avons également élaboré un cadre de partage de ressources distribuées pour les réseaux -cloud-en nuage. Nous étudions la stabilité de l'évolution de l'équilibre de Nash en fonction du nombre d'utilisateurs. Dans ce scénario, nous considérons également le comportement des utilisateurs sociaux. Enfin nous avons également examiné un problème de satisfaction de la demande où chaque utilisateur a une demande propre à lui qui doit être satisfaite.

I would like to express my deepest gratitude to Mohamad Assaad, Hamidou Tembine and Djamal Zeghlache for their guidance, support and constructive feedback throughout my PhD. Under their tutelage, I was well supervised and given the freedom to work on problems of my interest. They were instrumental in motivating me and giving me direction whenever it was required.

I would like to thank the jury members for allocating their precious time to participate in my defense.

I would also like to thank the people who were helpful at different stages of my work.

• A special thanks to Valerie Mateus of RS2M Lab in Telecom SudParis and Catherine Magnet of Telecommunications Department at Supelec for the logistical support regarding various official matters.

• I would like to thank all my friends from Supelec and Telecom SudParis, among them particulary Mereyem, Daniel, Shoaib, Li-Chuan, Jakob, Stefoan, Subhash, Ayaz, Marwen for their company.

Introduction la recherche du Nash

L'optimisation distribuée a bénéficié un intérêt croissant au cours des dernières années en raison de son application dans des domaines tels que les réseaux sans fil, l'estimation distribuée, etc. Le problème principal se compose d'un réseau de n noeuds ou agents en interaction où chacun a une récompense ou une fonction d'utilité à maximiser. La décision de chaque noeud a un impact sur la fonction de récompense des autres noeuds, ce qui rend le problème difficile en général. vi vii Même si le problème d'optimisation distribuée, considéré dans ce travail, et l'approche développée sont généraux et peuvent être utilisés dans de nombreux domaines d'application, nous nous limitons au problème de commande de puissance dans les réseaux sans fil afin de mieux illustrer notre contribution. La généralisation des résultats obtenus à d'autres applications n'est pas difficile en soi.

Recherche d'extremum

Krstic et.al. au cours des dernières années ont énormément contribué au domaine de la recherche d'extremas non-basée sur un modèle. Dans [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF], les auteurs proposent un algorithme cherchant l'équilibre de Nash pour les jeux avec des espaces d'action continus. Ils proposent un algorithme d'apprentissage entièrement distribué qui nécessite seulement une mesure de la valeur numérique de la récompense. Leur algorithme est fondé sur la perturbation en sinus (perturbation dite déterministe au lieu d'une perturbation stochastique) de la fonction de paiement en temps continu. Toutefois, le schéma d'apprentissage à temps discret avec des perturbations en sinus n'est pas examiné dans [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF]. Dans [START_REF] Miloš | Extremum seeking under stochastic noise and applications to mobile sensors[END_REF], l'algorithme de recherche d'extremas avec perturbations sinuso idales pour des systèmes non-basés sur des modèles a été étendu et modifié pour le cas de mesures bruitées i.i.d et de perturbations en sinus évanouissantes, la convergence presque sûre à l'équilibre est prouvée. La recherche d'extremas basée sur la perturbation en sinus pour des mesure de bruit indépendantes de l'état est présentée dans [START_REF] Stankovic | Distributed seeking of nash equilibria with applications to mobile sensor networks[END_REF].

Dans ce travail, nous étendons le travail dans [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] au cas de fonctions de paiement textit dépendantes d'un état stochastique, et utilisons des perturbations déterministes pour recherche de l'équilibre de Nash. On peut facilement voir la différence entre ce travail et les travaux existants [START_REF] Miloš | Extremum seeking under stochastic noise and applications to mobile sensors[END_REF][START_REF] Stankovic | Distributed seeking of nash equilibria with applications to mobile sensor networks[END_REF]. Dans ces travaux, le bruit η j associé à la mesure est additif et i.i.d , ce qui n'est pas nécessairement vrai dans la pratique notamment dans le domaine de l'ingénierie, où le bruit est en général corrélé dans le temps. Dans notre cas, nous considérons une fonction stochastique de gain dépendantz de l'état et notre problème peut être écrit sous une forme de Robbins-Monro avec un bruit Markov (corrélé) donné par η j = r j (S, a) -E S [r j (S, a)] (Cela deviendra plus clair dans les sections suivantes), c'est à dire que le bruit associé est stochastique dépendant de l'état et de l'action , ce qui est différent du cas du bruit i.i.d additif supposé dans viii [START_REF] Miloš | Extremum seeking under stochastic noise and applications to mobile sensors[END_REF][START_REF] Stankovic | Distributed seeking of nash equilibria with applications to mobile sensor networks[END_REF].

Contribution

Dans ce travail, nous proposons un temps discret algorithme d'apprentissage, en utilisantla perturbation en sinus continue pour des jeux d'action où chaque noeud ne dispose que d'une réalisation numérique de leur propre récompense à chaque instant. Nous étendons donc la méthode classique de recherche de l'équilibre de Nash avec perturbation en sinus [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] au cas du temps discret et des fonctions de paiement dépendantes de l'état stochastique. Nous montrons que notre algorithme converge localement à un état d'équilibre de Nash indépendant de l'état dans le théorème 1 dans [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] pour un pas évanouissant et nous bornons l'erreur correspondante dans le théorème 2 dans [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] pour un pas fixe. Notez que puisuqe les fonction de paiement ne sont pas nécessairement concaves, trouver un optimum global en un temps raisonnable peut être difficile en général, même dans le cas déterministe (état fixe) et avec une expression anamytic de la fonction de gain. Nous montrons aussi le temps de convergence pour le cadre de sinus dans le corollaire 1 dans [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF].

Les publications suivantes ont été soumises ou ont été publiées dans des revues et / ou conférences.

1. La principale contribution de la recherche d'extremum et notamment les preuves sont présentés dans [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF].

2. Nous avons appliqué cette chnique de recherche d'extremum pour les systèmes sans fil dans les scénarios suivants.

(a) Apprentissage distribué stochastique pour le contrôle de puissance continue dans les réseaux sans fil a été présenté dans [START_REF] Hanif | Distributed power control in femto cells using bayesian density tracking[END_REF].

(b) Une commande de puissance distribuée dans les cellules femto bas" sur une poursuite de densité bayésienne a été développée dans [START_REF] Hanif | Distributed stochastic learning for continuous power control in wireless networks[END_REF].

(c) Dans [START_REF] Hanif | Distributed transmit beamforming with 1-bit feedback for los-miso channels[END_REF], nous avons développé une stratégie de beamforming d'émission distribuée avec 1 bit de rétroaction pour les canaux LoS-MISO. ix

Définition du problème et algorithme suggéré

Nous considérons le problème du contrôle de puissance dans les réseaux sans fil qui est composé de paires émetteur-récepteur utilisant tous la même fréquence et ainsi générant des interférences les uns sur les autres. Chaque paire émetteur -récepteur possède donc sa propre fonction de récompense / utilité qui dépend nécessairement de l'interférence exercée par les autres paires / noeuds. Comme le gain de canal sans fil et l'interférence varient dans le temps, l'objectif est d'optimiser nécessairement un long terme (par exemple moyenne) des fonctions de récompense de tous les noeuds. La fonction de récompense de l'utilisateur i au temps k est notée r i (S k , a k ) où S k := [h k (i, j)] représente une matrice n × n contenant les coefficients de canal au temps k, h k (i, j) représente le coefficient de canal entre l'émetteur i et le récepteur j (où (i, j) ∈ [1, . . . , n] 2 ) et a k représente le vecteur contenant la puissance de transmission de n noeuds.

La technique la plus couramment utilisée pour obtenir un maximum local des fonctions de récompense des noeuds est la méthode de de gradient croissants / décroissants.Supposons qu'il y ait n noeuds transmetteurs récepteurs chacun avec une fonction de récompense représentée par r i (S k , a k ) qui est utilisée pour formuler les problèmes d'optimisation suivants: max a i ≥0 E S r i (S, a) ∀ i ∈ {1, . . . , n} =: N

(1) où E S désigne l'opérateur espérance par rapport à S.

En supposant que nous avons accès à la récompense à chaque instant k, mais l'expression analytique de r i (S k , a k ) est inconnue pour l'utilisateur i. une solution au problème ci-dessus est un équilibre indépendant de l'Etat dans le sens qu' aucun émetteur n'a intérêt à changer sa puissance d'émission lorsque les autres émetteurs conservent leur choix. Il est bien connu que les équilibres peuvent être différents des optimum global, l'écart entre l'équilibre et le pire maximum global est capturé par le soi-disant prix de l'anarchisme . Ainsi la solution obtenue par notre méthode peut être sous-optimale par rapport à la maximisation de la somme de toutes les récompenses. Nous étudions la stabilité locale de l'algorithme stochastique.

Puisque la structure des fonctions de paiement est inconnue, les gradients ne peuvent pas être calculés. Ainsi, chaque réseau n'a pas besoin d'être au courant de la présence de ces autres réseaux. La seule information dont chaque émetteur x a besoin est la valeur numérique r i,k Les fonctions de paiement sous-jacentes ne sont pas supposées être concaves / convexes. Ce genre de système est aussi appelé système à modèle libre. Nous supposons seulement que les fonctions sont Lipschitz et qu'un point Nash équilibre existe.

Algorithme d'apprentissage

Supposons que chaque utilisateur i est en mesure d'observer une valeur numérique r i,k de la fonction r i (S k , a k ) au temps k , où a i,k est la puissance d'émission de l'émetteur i au temps k. âi,k est une variable intermédiaire. a i , Ω i φ i représentent la fréquence d'amplitude et la phase du signal de perturbation en sinus, r i,k+1 représente la récompense à l'instant k + 1.

A chaque instant k, chaque émetteur met à jour sa puissance a i,k , en ajoutant la perturbation en sinus à la variable intermédiaire âi,k en utilisant l'équation 2.31, et reprend la transmission en utilisant a i,k . Ensuite, chaque émetteur reçoit une réalisation de la récompense r i,k+1 de son récepteur correspondant au temps k + 1 qui est utilisée pour calculer âi,k+1 en utilisant l'équation 3. La puissance a i,k+1 est ensuite mise à jour en utilisant l'équation 2.31. Cette procédure est répétée pour tout au long de la fenêtre de transmission T . L'algorithme est à temps discret et est donnée par

a i,k = âi,k + a i sin(Ω i k + φ i ) (2)
âi,k+1 = âi,k + λ k l i a i sin(Ω i k + φ i )r i,k+1

(3)

où k := k k ′ =1 λ k ′ . Ω i = Ω j , Ω j + Ω i = Ω j ′ et Ω j ∀i

Introduction au partage des ressources dans le Cloud

Les solutions de partage de ressources sont très importantes pour les centres de données comme car il est mis-en oeuvre à différents niveaux du réseau de nuage.

Le problème de partage de ressources peut être formulé comme un problème de décision stratégique entre les clients. Dans une telle situation, mais dans un contexte différent, Tullock (1980, [Tul80]) a proposé un schéma de la théorie des jeux à récompense probabiliste it recherche de rente. Il a remarqué plus tôt que la perte sociale associée à la recherche de rente dépasse un certain seuil.

Du point de vue de la mise en réseau des nuages, ce qui signifie que beaucoup de ressources peuvent être perdues si l'utilisateur nuage envisage une location économique. Dans ce travail, nous étudions un modèle stylisé de partage des ressources de manière distribuée et équitable. Nous allons montrer que l'efficacité peut être considérablement améliorée pour les grands réseaux de cloud computing en utilisant une conception appropriée de prix. Nous examinons à la fois la stabilité et la réaction myope utilisant des stratégies à champ moyen [START_REF] Als | The evolutionary stability of perfectly competitive behavior[END_REF].

Les jeux de champ moyen sont connus pour être bien adaptés pour les systèmes finis (mais grands) et infinis. Contrairement aux autres outils classiques pour les systèmes à grande échelle, l'approche de champ moyen dynamique intègre les dynamiques qui permettent la gestion de la demande en ligne (pay-as-youuse régime). Elle permet l'optimisation, le contrôle et la conception dynamique de mécanisme lorsque le nombre d'utilisateurs actifs varie et étudie la nature interactive des réseaux de nuage, conduisant à des problèmes de prise de décisions stratégiques. Des études récentes dans les réseaux de cloud ont déjà adopté un régime de champ moyen. Par exemple, dans [START_REF] Parikh | Cloud networking: A network approach that meets the requirements of cloud computing[END_REF], les auteurs considèrent cloud public de plus de cent mille serveurs et de nombreux nuages privés en plus de l' échelle du réseau traditionnel.

L'une des questions fondamentales est de connaître l'écart d'erreur ou erreur d'approximation du modèle de champ moyen. En d'autres termes, la précision de l'approximation fournie par le modèle de champ moyen dans un réseau de nuages avec nombre fini (mais grand ) d'utilisateurs.

Nous fournissons une réponse complète à la question ci-dessus dans ce travail.

Contribution

Bien que nous considérons ici les réseaux de cloud computing, notre analyse qui en résulte est plus générale et est applicable à des réseaux similairesde partage xii de ressources. Les contributions de ce travail sont listées ci-dessous.

• On considère des jeux de partage des ressources en nuage avec des espaces d'action continus où chaque utilisateur tente de maximiser son propre gain.

Dans le régime fini (nombre limité d'utilisateurs), nous fournissons les expressions analytiques de trois importants concepts de solution en théorie des jeux: équilibre de Nash (NE), réponse de champ moyen à population finie (F -MFR) et stratégies évolutives stables à population finie (F -ESS).

• Dans le régime fini, nous fournissons alors un algorithme itératif basé sur Ishikawa qui converge vers chacun des trois concepts d'équilibre ci-dessus et discutons ses temps de convergence.

• On considère alors le régime infini, car dans de nombreux réseaux de nuages le nombre d'utilisateurs devrait être très élevé. Nous fournissons une expression analytique de l'équilibre du champ moyen et montrons que l'équilibre du champ moyen est une stratégie évolutivement stable, c'est à dire qu'il ne peut pas être envahi par une petite fraction des déviants.

Nous montrons que l'équilibre du champ moyen est stable évolutif pour toute fraction de déviants strictement inférieure à 100% ce qui rend notre résultat encore plus fort. Nous montrons également que l'équilibre de Nash est stable dans le régime infini.

• Ensuite, nous nous concentrons sur l'algorithme d'apprentissage distribué pour le régime infini. Nous proposons un système d'apprentissage (mais toujours avec moins d'informations) basé sur un modèle pour les jeux avec l'espace de l'action continue et à grand nombre de joueurs. Chaque joueur va mettre à jour sa stratégie d'apprentissage basée sur une durée d'agrégation, qui est la moyenne d'une fonction croissante de l'action des autres joueurs.

• La dernière contribution de ce papier est l'étude de concept de jeu satisfaisant. Chaque utilisateur du nuage a une demande de capacité qui doit être satisfaite n'importe quand n'importe où (au lieu d'essayer de maximiser un profit). Dans le régime fini, nous fournissons une expression analytique de la solution satisfaisante et développons un algorithme distribué qui est capable de l'atteindre.

xiii Pour plus de détails sur les contributions ci-dessus et des résultats numériques veuillez vous référer à [START_REF] Hanif | Mean-field games for resource sharing in cloud based networks[END_REF][START_REF] Hanif | Cloud networking mean field games[END_REF].

System Model

Nous considérons le partage des ressources jeu avec un nombre fini (mais arbitraire) de clients dans un réseau de nuage. On note un tel jeu par G n , où n est le nombre de clients. L'espace d'action de chaque utilisateur est A = R + qui est un ensemble convexe, c'est-à-chaque joueur j choisit une action a j qui appartient à l'ensemble A. l'action peut représenter une certaine demande. Toutes les actions déterminent ensemble un résultat. Soit p n le prix unitaire de l'utilisation des ressources de cloud par les clients.

Ensuite, le gain de joueur j est donné par:

r j (a 1 , . . . , a n ) = c n h(a j ) n i=1 h(a i ) -p n a j , (4)
si n i=1 h(a i ) > 0 et zéro autrement. La structure de la fonction récompense R J (a 1 , . . . , a n ) pour l'utilisateur j montre qu'il s'agit d'un pourcentage de la capacité allouée moins le coût d'utilisation de cette capacité. Ici, c n représente la valeur des ressources disponibles (qui peuvent être considérées comme la capacité du nuage), h est une fonction positive et décroissante avec h(0) = 0. Nous fixons la fonction h être x α where α > 0 dénote un certain indice de rendement.

Conclusion

Introduction

In this chapter we present a general description of problems in future networks.

In particular we identify and focus on the technological challenges behind these problems. Finally we present the main contribution in this thesis. References are given throughout the work, where interested readers may find detailed information if necessary.

Motivation and Challenges

The main motivation for this thesis comes from the challenges that exists in the design and development of future networks. Future networks will support an ever greater number of subscribers and higher data rates per subscriber than existing networks. At the same time these networks will need to utilize the available resources more efficiently, but above all they will have to consume low power.

Future network is a blanket term which includes all types of wired and wireless communications networks, including the concepts of 'cloud networks', 'internet of things' and 'wireless sensor network'. There is a great technological gap that needs to be bridged in-order to satisfy the performance claims hinted above.

Most of the existing network designs are based on a centralized controller which is responsible for all resource management and control requests but such models are non-scalable to higher number of users as it entails a very high signaling on the backhaul link.

Another limitation even at the small scale is when there are several non cooperating users, for example in cognitive radio we have primary and secondary users using the same spectrum at the same time and interfering with one another.

In such cases the system is inherently distributed and hence the problem cannot be solved in a centralized manner.

To overcome these challenges there is a growing consensus among network designers to make future networks decentralized where each node is autonomous and is able to make intelligent decisions about resource utilization. This decision or action has to be updated at each time as the demand of the network is constantly changing i.e. dynamic.

This type of approach has certain design challenges which are listed as follows:

• How to implement a distributed optimization when there is only limited information in feedback?

• How to ensure that the distributed optimization problem converges to a local maxima?

The answer to both of the above question is dependent on the structure of the reward function and the available information for updates. There can be several practical limitation associated with the reward function which are listed below. In some scenarios, the reward function r j (.) associated with each node is not known, or one or more dependent variables of the reward functions are not known. The reward function could be known but non differentiable. The node may not have the computing power necessary to perform the computation required for optimization. The state of the system could be time varying. All these above limitations encourage designers to look at more clever techniques to deal with such challenges. One way to deal with such limitations is by using a 'model free' approach to optimization. We will discuss these approaches later in this chapter.

Wireless Resource Utilization

The wireless resources are an expensive and limited commodity. There are several methods that have been developed over the year to utilize the wireless resources in a much more efficient ways. For example using efficient multiple access techniques such as code division multiple access (CDMA) and orthogonal frequency division multiple access (OFDMA) to divide the spectrum between a greater number of subscribers, installing multiple antennas per subscriber i.e.

multiple input multiple output (MIMO) systems to improve capacity or performance, using more efficient coding techniques to better protect against random-ness in the channel. Having faster more robust routing protocols which reduce latency by choosing the shortest path through the network. As the demand for data rate is increasing wireless infrastructure is becoming overloaded with more and more users. This surge in the number of users is putting higher demand on the backhaul to resolve the interference in intelligent ways. This kind of scaling is not practical as the backhaul links has a limited bandwidth.

Motivation for decentralized system: One logical progression is to transition from a centralized to a distributed architecture. In wireless communications there are several scenarios which are inherently distributed i.e. for example an ad-hoc network which does not rely on a pre existing infrastructure. Cognitive radio network is another example where there are primary and secondary users.

The primary users represent the pre-existing infrastructure and operates in a licences frequency spectrum. The secondary users are allowed to use the spectrum only when the primary users are not using it. This type of network is a distributed network as there is no central controller between the primary and the secondary users. Another reason for moving towards a decentralized system is that the delay associated with a centralized system which may cause the information to become outdated by the time it has been shared and used by the central controller. Hence there is greater demand to develop fully distributed techniques which are able to achieve performance similar to a centralized systems. Distributed optimization has been receiving an increasing interest over the past years due to its ability of use in many application fields (wireless networks, distributed estimation, etc.). The main problem consists in a network of n interacting nodes or agents where each one has a reward or utility function to maximize. The decision of each node has an impact of the reward function of the other nodes, which makes the problem challenging in general. Different approaches, mainly based on gradient descent/ascent method, have been developed to achieve a local optimum (or global optimum in some special cases, e.g. concavity of the reward, etc.) of the distributed optimization problem. But in practical systems it may not be possible to implement gradient based method due to lack of knowledge about the reward function.

There are many problem in wireless communication where only a noisy or quantized numerical value of reward is available in feedback at the transmitter.

In such cases implementing a distributed optimization approach becomes much more challenging.

Scenarios that we have considered: Following is a brief description of some of the problems in distributed wireless resource utilization that we have considered.

• Power Control in Interference Channel: In wireless communications, an interference channel arises when there are more than one transmitters trying to use the same frequency. The problem is composed of transmitterreceiver pairs; all of them use the same frequency and thus generate interference onto each other. It is an important scenario, and one ways of managing the interference is by implementing some type of power control scheme. We consider a challenging scenario where the transmitters do not cooperate with one another and only have to do power control based on their local information. Each transmitter-receiver pair has therefore its own reward/utility function that depends necessarily on the interference exerted by the other pairs/nodes. Since the wireless channel is time varying as well as the interference, the objective is necessarily to optimize a long-run (e.g. average) of the reward functions of all the nodes.

The reward function of user i at time k is denoted by r i (H k , p k ) where

H k := [h k (i, j)
] represents an n × n matrix containing channel coefficients at time k, h k (i, j) represents the channel coefficient between transmitter i and receiver j (where (i, j) ∈ [1, . . . , n] 2 ) and p k represents the vector containing transmit powers of n transmit receive nodes.

• Beamforming in Interference Channel: In cases when we have multiple transmitting antennas at each transmitter, it is possible to implement beamforming instead of power control which is a more advanced method of steering the signal power toward your respective receiver. This is a very useful techniques as it helps us in avoiding interfering with the other receivers and improve our performance by directing our signal in the direction of our respective receiver. But in order to implement beamforming we need to have some knowledge about the position of the received with respect to the transmitter. As we assume a case where we only have a limited information i.e. 1-bit in feedback at each time. We attempt to do distributed beamforming using only one bit feedback from the receiver, which is indeed a very limited information for this task. This is what makes it a challenging problem. We consider the case of line of sight (LoS) channel to keep things simple. Each transmitter will adapt its direction of transmission (DoT) using only the 1-bit feedback in such a way that the probability of successful transmission is maximized.

• Bayesian Density Tracking: In wireless communication systems, as the channels are randomly varying, it makes sense to measure the performance of the channel as the probability of 'signal strength' greater than a certain threshold. The mathematical models behind these probability function can be complicated and in most cases the dependent variables may be unknown or randomly varying. We attempt to track the evolution the density of the signal strength and use this information to maximize the success probability using the concepts from Bayesian density tracking. There are scenarios where the probability of success maximization can be a good way to analyze and optimize the performance of a randomly varying system. Here we consider an overlapping femto cell and macro cell operating at the same frequency. We only consider the downlink scenario where the femto cell users will receive interference from the macro access point and vice versa.

We construct the reward functions in such a way that the femto access point take the success probability of the macro cell users and its own users into consideration when implementing its power control strategies. The femto and macro cells are two distributed systems and there is not cooperation on the backhaul. Femto has knowledge about the performance of its own user and the performance of the macro user which the femto is able to overhear in the feedback control channel as they are both using the same standard. This is again a distributed scenario with limited information in feedback.

We mainly concentrated on distributed scenarios with single input single output (SISO) and multiple input single output (MISO) channels. In all of the above mentioned scenarios we use our 'model free' optimization algorithm that we will discuss in the next chapter.

Cloud Networks Resource Sharing

Cloud Networking is a relatively new concept which ensures that computing and storage resources are available to users on demand. Storage Resources: Data storage and backup in the cloud is also an important business. Several companies are providing data storage in the cloud as their primary service, and the demand is to have instant and seamless access to the data over cross platform devices which makes such a service very attractive. As most of our data is now digital it necessary to have secure backup of personalized data. These services are used by individuals and companies. Dropbox, Google

Drive, Microsoft SkyDrive are some of the major storage services for users.

The resource sharing structure used by most cloud service providers uses CPU-hour consumed [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF], which may not be the most efficient, as it doesn't take into account the complex interactions between the users that are happening indirectly thought the shared resource. As different users are sharing the same physical machines, they are interacting with each other through the machines.

The service provider is only interested in maximizing his resource utilization i.e.

all CPU-hour are being utilized, but from the users standpoint this may not result in best performance if CPU-hours are divided among a large number of users. The tasks of a single user may take a very long time to finish. Hence the reward of each user is not fully captured by the CPU-hour resource sharing method, the percentage of resources made available to each user should be part of the reward. We consider such type of reward function where users are interested in increasing their percentage based reward function.

Scenarios that we have considered: Following is a brief description of some of the problems in large scale distributed cloud networks that we have considered.

• One of the problems in sharing resources on a large scale is again with the signaling overhead required to manage a dynamically changing demand by all the users. We address this distributed problem using the concepts from game theory and mean field.

• Demand satisfaction is another resource utilization problem, where each user has a specified demand that needs to be met for the user to be satisfied. This is inherently a different type of resource sharing problem.

Please refer to chapter 3 for detailed information about these cases.

Outline and Contributions

A general system overview which is common to all scenarios considered in this thesis is presented in figure 1.1. Our model assumes a number of nodes interacting with a dynamic environment. The dynamic environment means that the state of the system is changing. The nodes are non-cooperative and they are interacting with each other through the dynamic environment. The action of each node has an impact on the reward of the other nodes and vice versa. This is the basic system mode that we have considered in our thesis.

Extremum Seeking Algorithm

In chapter 2 we develop the concepts associated with extremum seeking for 'model free' scenarios (i.e. where the structure of the reward function is not known) we have developed a stable extremum seeking algorithm that is able to converge to Nash equilibrium when initialized in the neighborhood of the Nash equilibrium point. The algorithm ensures tractability which can is a requirement in certain engineering applications. Note that, our convergence is in the sense of Borkar [Bor08] and will be explained later on in the text.

In this work, we propose a discrete time learning algorithm, using sinus perturbation, for continuous action games where each node has only a numeri-

Rx 1 x 1 a 1,k r 1,k x j . . . . . . x N Rx 3 x 1 x j . . . . . . a j,k r j,k x N Rx 4 x 1 x j . . . . . . x N a N,k r N,k

Dynamic Environment

A j action {r j (.)} payoff function Figure 1.1: Nodes interacting with each other through a dynamic environment cal realization of own-payoff at each time. We therefore extend the classical Nash Seeking with sinus perturbation method [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] to the case of discrete time and stochastic state-dependent payoff functions. We prove that our algorithm converges locally to a state independent Nash equilibrium in Theorem 1 in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] for vanishing step size and provide an error bound in Theorem 2 in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] for fixed step size. Note that since the payoff function may not necessarily be concave, finding a global optimum in reasonable time can be difficult in general even in deterministic case (fixed state) and known closed-form expression of payoff. We also show the convergence time for the sinus framework in Corollary 1 in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF].

Following publications have been submitted or have appeared in peer reviewed journals and/or conferences.

1. The main contribution of extremum seeking framework including proofs is presented in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF]. A Nash seeking algorithm which is able to find the local minima using just the numerical value of the stochastic state dependent payoff function at each discrete time step. We proved the convergence of our algorithm to a limiting ODE. We have provided as well the error bound for the algorithm and the convergence time to be in a close neighborhood of the Nash equilibrium. A numerical example for a generic wireless network is provided for illustration. The convergence bounds achieved by our method are dependent on the step size and the perturbation amplitude. We consider a new class of state dependent payoff functions r j (S, a) which are inspired from wireless systems applications.

But these kind of functions are more general and appear in other application areas. We present an iterative algorithm which is able to perform distributed resource sharing (for same and different prices) for a certain type of reward function. We show the stationary points of our algorithms converge to Nash equilibrium.

2. We have applied this extremum seeking techniques to wireless systems in the following scenarios.

(a) Distributed stochastic learning for continuous power control in wireless networks was presented in [START_REF] Hanif | Distributed power control in femto cells using bayesian density tracking[END_REF].

(b) In [START_REF] Hanif | Distributed transmit beamforming with 1-bit feedback for los-miso channels[END_REF] we developed a distributed transmit beamforming with 1-bit feedback for LoS-MISO channels.

(c) A distributed power control in femto cells using bayesian density tracking was developed in [START_REF] Hanif | Distributed stochastic learning for continuous power control in wireless networks[END_REF].

Distributed Resource Sharing

In chapter 3 we describe distributed resource sharing in cloud networks. We consider a scenarios where the system model is known but the number of users is very large. In such scenario we analyze the structure of the reward function and implement iterative algorithms which are able to the equilibrium point.

Although we consider cloud networks, our resulting analysis is more general and is applicable to similar resources sharing networks.

The contribution of this work is listed below.

• We consider cloud resource sharing games with continuous action spaces where each user tries to maximize its own payoff. In the finite regime (finite number of users), we provide closed-form expressions of three important game-theoretic solution concepts: Nash equilibrium (NE) , finite population mean-field response (F-MFR) and finite population evolutionarily stable strategies (F-ESS). The first surprising result is that the Nash equilibrium is not an evolutionarily stable strategy for finite population.

(see Proposition 2). In fact in cloud networks, the number of users as well as users' demands are constantly changing and in this context evolutionary stable strategy (i.e. it cannot be invaded by small fraction of deviants) is crucial. Based on the work of Possajennikov (2003, [Pos03]) we show that mean-field-taking strategies are evolutionarily stable strategies for a certain range of return index (i.e. α). We provide the explicit optimal pricing as a function of the number of active users. Under the optimal pricing no resource is wasted at the equilibrium. This means that the efficiency loss tends to zero.

• In the finite regime, we then provide an Ishikawa-based iterative algorithm that converges to each of the three aforementioned equilibrium concepts and discuss its convergence time.

• We then consider the infinite regime, because in many cloud networks the number of users is expected to be very high. We provide closed-form expression of the mean-field equilibrium and show that the mean-field equilibrium is an evolutionarily stable strategy, i.e., it cannot be invaded by a small fraction of deviants. We show that the mean-field equilibrium is evolutionary stable for any fraction of deviants strictly less than 100% which makes our result even stronger. We also show that Nash equilibrium is stable in the infinite regime. This is due to the fact that in the limiting case, the influence of one generic player on the total demand is negligible.

• Then, we focus on distributed learning algorithm for infinite regime. We propose a model-based (but still with less information) learning scheme for games with continuous action space and large number of players. Each player will update its learning strategy based on an aggregative term, which is the mean of an increasing function of the action of the other players.

Each player will be influenced by the aggregate, and the mean-field behavior is formed from the action of each player. Each player will try to conjecture the aggregative term consisting of the actions of the other players at each time slot, and will respond to the aggregative term locally. This drastically simplifies the dimensionality of the mean-field response system in the asymptotic case. We also discuss the convergence time of the proposed learning algorithm and show that it is faster than the Ishikawa-based algorithm or standard contraction mapping fixed-point algorithms.

• Finally we study of satisfactory game concept. Each cloud user has a capacity demand that needs to be satisfied anytime anywhere (instead of trying to maximize a payoff). In the finite regime, we provide a closed form expression of the satisfactory solution and develop a distributed algorithm which is able to reach it. Contrary to the aforementioned equilibrium concepts, the extension of the obtained satisfactory solutions to the infinite regime is straightforward.

In chapter 4 we provide a generalized conclusion of the work that has been presented along with implications and applications to future networks.

Publication List

Here we list some of the publications related to this thesis.

HTAZ13Ja A.F. Chapter 2

Model Free Nash Seeking

Introduction

In this work we consider a fully distributed interactive system, which consists of nodes which can be modeled as a strategic decision making problem. Let us consider a distributed interactive system with N nodes or agents which interact with one another and each has a payoff/utility/reward to maximize. The decision or action of each node has an impact on the payoff of the other nodes, which makes the problem challenging in general. In addition, there is a random variable (scalar, vector or matrix) that could influence the payoff of each node.

In distributed interactive systems it might not be possible to have a bird's eye view of the system as it is too complicated or is constantly changing. For practical reason in terms of observation and measurements, we work on discrete time space. We consider interactive systems where each node only has access to a numerical value of its payoff at each time. Let a j,k be the action of node j at time k and the numerical value of the payoff of this node is given by rj,k , which is a realization of some random variable rj,k := r j (S k , a k ) + η j,k where η j,k represents noise, r j :

S × R N + -→ R is the payoff function of node j, S k ∈ S ⊆ C N ×N is the state (which is stochastic), a k = (a 1,k , . . . , a N,k
) is the action profile at time k i.e., the vector containing actions of all nodes at time k. Figure 2.1 shows the system model where we have N interacting nodes.

The payoffs are interdependent as the nodes interact with one another. Each of these nodes j has access to the numerical value of their respective payoff rj,k and it needs to implement a scheme to select an action a j,k such that its payoff is maximized. The above scenario can be interpreted as a strategic decision making problem, i.e. a game. In this work we explore learning in such games which is synonymous with designing distributed iterative algorithms that converge to a solution. One of most known solution concepts in game theory is the socalled Nash equilibrium. For the clarity of the presentation, we restrict ourselves to Nash equilibrium seeking, however, the methodology presented here can be applied to satisfactory solution seeking or correlated equilibrium seeking. Figure 2.1 shows the nodes interacting with one another thought a dynamic environment where state S is stochastic. One of the main assumptions that we can make here is the existence of a local solution. To solve optimization problems there are various approaches, mainly based on gradient ascent or descent method [START_REF] Snyman | Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms[END_REF], have been developed to achieve a local optimum (or global optimum in some special cases, e.g. concavity of the payoff, etc.) of the distributed optimization problem. The stochastic gradient ascent proposes to feedback the numerical value of gradient of payoff function ∇r j of node j (which can be noisy) to itself. This supposes in advance that a noisy gradient can be computed or is available at each node. Note that if the numerical value of the gradients of the payoffs (the entire vector) are not known by the nodes at each step, this scheme cannot be used. In [START_REF] Bianchi | Convergence of a multi-agent projected stochastic gradient algorithm for non convex optimization[END_REF] projected stochastic gradient based algorithm is presented. A distributed asynchronous stochastic gradient optimization algorithms is presented in [START_REF] Tsitsiklis | Distributed asynchronous deterministic and stochastic gradient optimization algorithms[END_REF]. Incremental subgradient Methods for Non-differentiable optimization are discussed in [START_REF] Nedic | Incremental subgradient methods for nondifferentiable optimization[END_REF]. A distributed optimization algorithms for sensor networks is presented in [START_REF] Rabbat | Distributed optimization in sensor networks[END_REF].

Rx 1 x 1 a 1,k r1,k x j . . . . . . x N Rx 3 x 1 x j . . . . . . a j,k rj,k x N Rx 4 x 1 x j . . . . . . x N a N,k rN,k Dynamic Environment A j action S state {r j (.)} payoff function
Interested readers are referred to a survey by Bertsekas [START_REF] Bertsekas | Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey[END_REF] on incremental gradient, sub-gradient, and proximal methods for convex optimization. In [START_REF] Stankovic | Stochastic extremum seeking with applications to mobile sensor networks[END_REF] the authors present stochastic extremum seeking with applications to mobile sensor networks.

Use of the aforementioned gradient based methods requires the knowledge of:

1. the system state.

2. the actions of others and their states.

3. the mathematical structure (closed form expression) of the payoff function.

4. computational capability of the nodes.

As we can see, it will be difficult for node j to compute the gradient if the expression for the payoff function r j (.) is unknown and/or if the states and actions of other nodes are not observed as r j (.) depends on the actions and states of others.

There are several methods for Nash equilibrium seeking where we only have access to the numerical value of the function at each time and not its gradient (e.g. complex functions which cannot be differentiated or unknown functions).

A promising technique for solving the above problem is called extremum seeking.

Extremum Seeking

Krstic et.al. in recent years have contributed greatly to the field of non-model based extremum seeking. In [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF], the authors propose a Nash seeking algorithm for games with continuous action spaces. They proposed a fully distributed learning algorithm which requires only a measurement of the numerical value of the payoff. Their scheme is based on sinus perturbation (i.e. deterministic perturbation instead of stochastic perturbation) of the payoff function in continuous time. However, discrete time learning scheme with sinus perturbations is not examined in [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF]. In [START_REF] Miloš | Extremum seeking under stochastic noise and applications to mobile sensors[END_REF] extremum seeking algorithm with sinusoidal perturbations for non-model based systems has been extended

and modified to the case of i.i.d. noisy measurements and vanishing sinus perturbation, almost sure convergence to equilibrium is proved. Sinus perturbation based extremum seeking for state independent noisy measurement is presented in [START_REF] Stankovic | Distributed seeking of nash equilibria with applications to mobile sensor networks[END_REF].

In [START_REF] Van De Wouw | Extremum-seeking control for periodic steady-state response optimization[END_REF] an extremum-seeking approach for periodic steady-state response optimization is presented. A unifying framework for analysis and design of extremum seeking controllers is presented in [NTM + 12]. In [START_REF] Nesic | On a shubert algorithm-based global extremum seeking scheme[END_REF] a shubert algorithm-based global extremum seeking scheme is presented. A multidimensional global extremum seeking via the DIRECT method is presented in [START_REF] Sei Zhen Khong | Multidimensional global extremum seeking via the direct method[END_REF]. In [START_REF] Liu | Newton-based stochastic extremum seeking[END_REF] a Newton-based stochastic extremum seeking approach is presented. A dynamic bandwidth allocation framework for wireless networks using a Shahshahani gradient based extremum seeking control is presented in [START_REF] Poveda | Dynamic bandwidth allocation in wireless networks using a shahshahani gradient based extremum seeking control[END_REF]. A simplex guided extremum seeking control for real-time optimization is presented in [START_REF] Zhang | Simplex guided extremum seeking control for real-time optimization[END_REF]. A Shahshahani Gradient based extremum seeking scheme is presented in [START_REF] Poveda | A shahshahani gradient based extremum seeking scheme[END_REF]. Extremum seeking under input constraint for systems with a time-varying extremum is presented in [START_REF] Ye | Extremum seeking under input constraint for systems with a time-varying extremum[END_REF]. In [START_REF] Atta | On-line optimization of cone crushers using extremum-seeking control[END_REF] an on-line optimization of cone crushers using Extremum-Seeking Control is considered. In avoid this, sinus perturbation can be used instead of stochastic perturbation in certain applications. Deterministic (sinus) perturbation method is particularly helpful when one node is trying to track the actions of the other nodes in many engineering application, one such application is presented here.

In this work we extend the work in [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] to the case of stochastic state dependent payoff functions, and use deterministic perturbations for Nash seeking. One can see easily the difference between this work and the existing works [START_REF] Miloš | Extremum seeking under stochastic noise and applications to mobile sensors[END_REF][START_REF] Stankovic | Distributed seeking of nash equilibria with applications to mobile sensor networks[END_REF]. In these works, the noise η j associated with the measurement is additive i.i.d. which does not necessarily hold in practice especially in engineering application where the noise is in general time correlated. In our case, we consider a stochastic state dependent payoff function and our problem can be written in Robbins-Monro form with a Markovian (correlated) noise given by η j = r j (S, a) -E S [r j (S, a)] (this will become clearer in the next sections), i.e.

the associated noise is stochastic state-and-action dependent which is different from the case of additive i.i.d. noise assumed in [START_REF] Miloš | Extremum seeking under stochastic noise and applications to mobile sensors[END_REF][START_REF] Stankovic | Distributed seeking of nash equilibria with applications to mobile sensor networks[END_REF].

In this work, we propose a discrete time learning algorithm, using sinus perturbation, for continuous action games where each node has only a numerical realization of own-payoff at each time. We therefore extend the classical Nash

Seeking with sinus perturbation method [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] to the case of discrete time and stochastic state-dependent payoff functions. We prove that our algorithm converges locally in the close neighborhood of a state independent Nash equilibrium in Theorem 1 for vanishing step size and provide an error bound in Theorem 2 for fixed step size. Note that since the payoff function may not necessarily be concave, finding a global optimum in reasonable time can be difficult in general even in deterministic case (fixed state) and known closed-form expression of payoff. Also note that, our convergence is in the sense of Borkar [START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] and will be explained later on in the text.We also show the convergence time for the sinus framework in Corollary 1.

The proof of the theorems are given in Appendix A.

The remainder of this work is organized as follows. Section 2.2 provides the proposed distributed stochastic learning algorithm. The performance analysis of the proposed algorithm (convergence to ODE, error bounds) is presented in Section 2.3. A numerical example with convergence plots is provided in Section 2.4. Appendix A contains the proofs.

We summarize some of the notations in Table 2.1.

r j payoff of node j a j,k decision of j at time k a -j,k (a j ′ ,k ) j ′ =j S k state at time k E expectation operator ∇ gradient operator

Problem Formulation and Proposed Algorithm

Let there be N distributed nodes, each with a payoff function represented by r j (S k , a j,k , a -j,k ) at time k which is used to formulate the following robust problems: sup

a j ≥0 E S r j (S, a j , a -j ) j ∈ N (2.1)
where N := {1, . . . , N } is the set of nodes, A j ⊆ R is the action space of node j, S is the state space of the whole system, where S ⊆ C N ×N and r j : A solution to 2.1 is a state-independent equilibrium in the sense that no node has an incentive to change its action when the other nodes keep their choice and the equilibrium strategy does not depend on the state. It may depend on the entire distribution of states.

S × j ′ ∈N A j ′ -→ R
Definition 1 (Nash Equilibrium (state-independent)). The action profile

a * = (a * j , a * -j ) ∈ j ′ A j ′ is a (state-independent) Nash equilibrium point if E S r j (S, a * j , a * -j ) ≥ E S r j (S, a ′ j , a * -j ), (2.2)
where ∀a ′ j ∈ A j , a ′ j = a * j , E S denotes the mathematical expectation over the state.

It is well-known that equilibria can be different than global optima, the gap between the worse equilibrium and the global optimum is captured by the so-called price of anarchy. Thus, solution obtained by our method can be suboptimal with respect to maximizing the sum of all the payoffs. We study the local stability of the stochastic algorithm. Here we denote a := (a j , a -j ), assuming that node j has access to it's realized payoff at each time k but the closed-form expression of r j (S k , a j,k , a -j,k ) is unknown to node j.

Definition 2 (Nash Equilibrium (state-dependent)). We define a statedependent strategy ǎj of node j as a mapping from S to the action space Ǎj . The set of state-dependent strategy is PG j :

{ǎ j : S -→ Ǎj , S -→ ǎj (S) ∈ Ǎj }. ǎ * = (ǎ * j , ǎ * -j ) ∈ i PG i is a (state-dependent) Nash equilibrium point if E S r j (S, ǎ * j (S), ǎ * -j (S)) ≥ E S r j (S, ǎ′ j (S), ǎ * -j (S)), (2.3) ∀ǎ ′ j ∈ PG j .
Here we will focus on the analysis of the so-called expected robust game i.e., (N , A j , E S r j (S, .)). A (state-independent) Nash equilibrium point [Jr.50] of the above robust game is a strategy profile such that no node can improve its payoff by unilateral deviation, see Definition 1 and Definition 2.

Since the current state is not observed by the nodes, it will be difficult to implement state-dependent strategy. Our goal is to design a learning algorithm for a state-independent equilibrium given in Definition 1. In what follows we assume that we are in a setting where the above problem has at least one isolated state-independent equilibrium solution. More details on existence of equilibria can be found in Theorem 3 in [START_REF] Michael R Baye | Characterizations of the existence of equilibria in games with discontinuous and non-quasiconcave payoffs[END_REF].

Distributed learning algorithm

Suppose that each node j is able to observe a numerical value rj,k of the function

r j (S k , a k ) at time k, where a k = (a j,k , a -j,k
) is the action of nodes at time k. âj,k is an intermediary variable. The real numbers b j Ω j φ j respectively represent the amplitude, frequency and phase of the sinus perturbation signal given by b j sin(Ω j t k + φ j ), The learning algorithm is presented in Algorithm 2 and is explained below. At each time instant k, each node updates its action a j,k , by adding the sinus perturbation i.e. b j sin(Ω j t k + φ j ) to the intermediary variable âj,k using equation (2.4), and makes the action using a j,k . Then, each node gets a realization of the payoff rj,k+1 from the dynamic environment at time k + 1 which is used to compute âj,k+1 using equation (2.5). The action a j,k+1 is then updated using equation (2.4). This procedure is repeated for the window T .

The algorithm is in discrete time and is given by

a j,k = âj,k + b j sin(Ω j t k + φ j ) (2.4) âj,k+1 = âj,k + λ k z j b j sin(Ω j t k + φ j )r j,k+1 (2.5)
where

t k := k ḱ=1 λ ḱ, Ω j = Ω j ′ , Ω j ′ + Ω j = Ω j ′′ ∀j, j ′ , j ′′ .
For almost sure (a.s.) convergence, it is usual to consider vanishing step-size or learning rate such as λ k = 1 k+1 . However, constant learning rate λ k = λ could be more appropriate in some regime. The parameter φ j belongs to [0, 2π]∀ j, k ∈ Z + 1: Each node j, initialize âj,0 Remark 1 (Learning Scheme in Discrete Time). As we will prove in subsection 2.3, the difference equation (2.5) can be seen as a discretized version of the learning scheme presented in [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF]. But it is for games with statedependent payoff functions i.e., robust games.

It should be mentioned here for clarity that the action a j,k of each node j is scalar.

Interpretation of the proposed algorithm

In some sense our algorithm is trying to estimate the gradient of the function r j (.), note that we don't have access to the function but just its numerical value.

The following equation clearly illustrated the significance of each variable and constant in the algorithm.

âj,k+1

New Value

= âj,k

Old Value

+ Learning Rate λ k z j Growth Rate b j Perturbation Amplitude sin( Perturbation Frequency Ω j t k + φ j ) New Reward rj,k+1 (2.6)
The learning rate λ k can be constant or variable depending on the requirements of the algorithm and system limitations. Perturbation amplitude b j > 0 is a small number. z j > 0 is also a small value which can be varied for fine tuning.

Rewriting the above equation we get âj,k+1âj,k

λ k = z j b j sin(Ω j t k + φ j )r j,k+1 (2.7)
For vanishing step size as k -→ ∞ λ k -→ 0 and the trajectory of the above algorithm coincides with the trajectory of an ODE.

For a survey on the above sinus perturbation method see [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF].

Main results

In this section we present the convergence results as introduced in the contribution section.

We introduce the following assumptions that will be used step by step 1 .

Assumption 1 (A1: Vanishing learning rate).

λ k > 0, k λ k = ∞, k |λ k | 2 < ∞.
There exists C 0 > 0 such that P (sup k a k < C 0 ) = 1. λ k represents the step size of the algorithm, The reason for first assumption: k λ k = ∞, is that we need to traverse over all discrete time. The condition k |λ k | 2 < ∞ ensures bound for the cumulative noise error. This last assumption is for a local stability analysis.

Assumption 2 (A2: Constant learning rate).

λ t = λ > 0, sup t [E a t 2 ]
1 2 < +∞ and a t 2 is uniformly integrable.

For Lipschitz functions the following two conditions must hold for the existence of a Nash equilibrium.

1 A1 and A2 are not used simultaneously.

Assumption 3 (A3: Existence of a local best response). E S ∂r j (S,a * ) ∂a j = 0, E S ∂ 2 r j (S,a * ) ∂a 2 j < 0. These two conditions tell us that a * j is a local maximizer of a j -→ E S r j (S, a j , a * -j ) where a * -j = (a * 1 , . . . , a * j-1 , a * j+1 , . . . , a * N ).

Assumption 4 (A4: Diagonal Dominance). the expected payoff has a Hessian that is diagonally dominant at a * , i.e., E S

∂ 2 rj (S,a * ) ∂a 2 j -j ′ =j E S ∂ 2 rj (S,a * ) ∂aj ∂a j ′ > 0.
Note that A4 implies that the Hessian of the expected payoff is invertible at a * .

This assumption is weaker compared to the classical extremum seeking algorithm because the Hessian of r j (S, a * ) does not need to be invertible for each S.

We assume S -→ r j (S, a) is integrable with respect to S so that the expectation E S r j (S, a) is finite.

Assumption 5 (A5). We assume S -→ r j (S, a) is integrable with respect to S so that the expectation E S r j (S, a) is finite.

Assumption 6 (A6). For any given state S, we assume that r j (S, a) is a smooth function with respect to a.

Convergence to ODE

First we need to show that our proposed algorithm converges to the respective ordinary differential equation (ODE) almost surely. We will use a dynamical system viewpoint and a stochastic approximation method to analyze our learning algorithm. The idea consists of finding the asymptotic pseudo-trajectory of the algorithm via ODE. To do so, we use the framework initiated by Robbins-Monro [START_REF] Robbins | A stochastic approximation method[END_REF] or [START_REF] Kiefer | Stochastic estimation of the maximum of a regression function[END_REF]. See [START_REF] Benam | Dynamics of stochastic approximation algorithms[END_REF][START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] for recent developments. The works in [START_REF] Benam | Dynamics of stochastic approximation algorithms[END_REF][START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] allows us to find the limiting trajectory of the learning algorithm.

The scheme can be written as âj,k+1 = âj,k + λ k z j b j sin(Ω j t k + φ j )r j,k+1 . Now we rewrite the above equation in Robbins-Monro [START_REF] Robbins | A stochastic approximation method[END_REF] form as:

âj,k+1 = âj,k + λ k [f j (k, âk ) + M k+1 ] ,
where

f j (k, a k ) := z j b j sin(Ω j t k + φ j )E S rj (S, a k ) rj (S, âk ) := r j (S, (â j,k + b j sin(Ω j t k + φ j )) j∈N ) M k+1 := z j b j sin(Ω j t k + φ j ) [r j,k+1 -E S r j (S, a k )] f (.) := (f j (.)) j∈N
Since the payoff r j is Lebesgue integrable with respect to S, the expectation of the payoff function E S r j (S, a) is finite. M k+1 is a Martingale difference sequence.

The following equations (2.8) (2.9) represent the non-autonomous system of ODEs for Lipschitz functions.

d dt âj,t = z j b j sin(Ω j t + φ j )E S [r j (S, a t )] (2.8) a j,t = âj,t + b j sin(Ω j t + φ j ) (2.9)
Theorem 1 (Variable Learning Rate). Under Assumptions A1, A5 and A6 the interpolated trajectory of our learning algorithm converges almost surely to the trajectory of a non-autonomous system given by equation (2.8) and (2.9) in the following sense,

lim t k -→∞ sup t∈[t k ,t k +T ] āt -a t k t = 0 a.s.
Almost sure (a.s.) convergence in our case simply means that the interpolated trajectory of our proposed algorithm converges to the solution of the ODE almost surely i.e. convergence with probability 1. Please refer to [START_REF] Yin | Stochastic Approximation and Recursive Algorithms and Applications[END_REF] for more details on almost sure convergence.

The gap between the interpolated version āt of algorithm and the trajectory of the ODE given by a t k is bounded as

sup t∈[t k ,t k +T ] āt -a t k t ≤ K T,k e LT + C T sup ḱ≥0 λ k+ ḱ (2.10)
which vanishes, where āt :

= a k + (a k+1 -a k ) (t-t k ) (t k+1 -t k )
is the interpolated version of the algorithm and a t k t is the solution of the ODE at time t starting from t k := k ḱ=1 λ ḱ, where L is the Lipschitz constant for the ODE and T is the time window. K T,k and C T are specified below.

In order to calculate the bound in equation (2.10) we need to define a few terms which are helpful in obtaining a compact form of the bound.

K T,k := C T L ḱ≥0 λ 2 k+ ḱ + sup ḱ≥0 δ k,k+ ḱ (2.11) δ k,k+ ḱ := ξ k+ ḱ -ξ k (2.12) ξ k := k-1 ḱ=0 λ ḱM ḱ+1
(2.13)

C T := r 0 + L(C 0 + r 0 T )e LT < ∞ (2.14) L := max j∈N E S [L j,S ]
(2.15)

r k := [r 1,k , . . . , r N,k ] (2.16)
To prove that the learning algorithm (the learning algorithm (discrete ODE))

converges to the ODE we need to verify conditions from Borkar [START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] Chapter 2 Lemma 1 for non-autonomous case.

This is an important result as it gives us an approximation on the error between our algorithm and the corresponding ODE. The proof of theorem 1 is available in the Appendix A.1.

Theorem 2 (Fixed Learning Rate). Under Assumption A2, A5 and A6 the interpolated trajectory of the learning algorithm converges in distribution when λ -→ 0, to the solution of a non-autonomous system given by equation (2.8) and

(2.9). Moreover the error gap is in order of λ.

The advantage of Theorem 2 compared to Theorem 1 is the convergence time.

The number of iterations required to reach a fixed time T is less with constant learning rate than the vanishing learning rate. However, the convergence notion under constant step size is weaker (it is in distribution) compared to the almost surely convergence with vanishing learning rate. So there is a sort of tradeoff between almost sure convergence and convergence time. Please refer to [START_REF] Yin | Stochastic Approximation and Recursive Algorithms and Applications[END_REF] for more information on convergence in distribution.

Let ∆ t := a ta * be the gap between the trajectory of the ODE at time t and the isolated equilibrium.

Theorem 3 (Local Exponential Stability). Assume A3-A6. Then, there exist Ḿ , T > 0 and ǭ, bj such that, for all ǫ ∈ (0, ǭ) and b j ∈ (0, bj ), if the initial gap is ∆ 0 := a *a 0 (which is small) then for all time t,

∆ t ≤ y 1,t (2.17)
where

y 1,t := Ḿ e -T t ∆ 0 + O(ǫ + max j b 3 j ) (2.18)
The proof of this theorem is presented in the appendix A.3.

According to Theorem 3 we have convergence to within a small range of the equilibrium point i.e. we do not converge to the equilibrium point.

From the above equation it is clear that as time goes to infinity the first term in y 1,t bound vanishes exponentially and the error is bounded by the amplitude of the sinus perturbation i.e. O(ǫ + max j b 3 j ). This means that the solution of ODE converges locally exponentially to the neighborhood of the state-independent equilibrium action a * provided the initial solution is relatively close. The initial error ∆ 0 influences the choice of ǭ in Theorem 3.

Definition 3 (ǫ-Nash equilibrium payoff point). An ǫ-Nash equilibrium payoff point in state-independent strategy is a strategy profile such that no node can improve its payoff more than ǫ by unilateral deviation.

Definition 4 (ǫ-close strategy Nash equilibrium point). An ǫ-close strategy Nash equilibrium point in a state-independent strategy is a strategy profile such that the Euclidean distance to a Nash equilibrium is less than ǫ.

A ǫ-close strategy Nash equilibrium point is an approximate Nash point with a precision at most ǫ.

It is not difficult to see that for Lipschitz continuous payoff functions, an ǫ-close Nash equilibrium is an Lǫ-Nash equilibrium point where L is the Lipschitz constant.

Next corollary shows that one can get an ǫ-close strategy Nash equilibrium in finite time.

Corollary 1 (Convergence Time). Assume A3-A4 and Remark 6,7 holds.

Then, the ODE reaches a (2ǫ + max j b 3 j )-close to a Nash equilibrium in at most T time units where

T = 1 T log( ∆ 0 Ḿ ǫ ) Sketch of Proof

Numerical Example A: Wireless Interference

Even though the distributed optimization problem, considered here, and the developed approach are general and can be used in many application domains. As an application of the above framework, we will consider the problem of power control in wireless networks in order to better illustrate our contribution. Consider an interference channel composed of N transmit receiver pairs as shown in Figure 2.2. Each transmitter communicates with its corresponding receiver and incurs an interference on the other receivers. Each receiver feeds back a numerical value of the payoff γ j (H, p) to its corresponding transmitter.

The problem is composed of transmitter-receiver pairs; all of them use the same frequency and thus generate interference onto each other. Each transmitterreceiver pair has therefore its own payoff/reward/utility function that depends necessarily on the interference exerted by the other pairs/nodes. Since the wireless channel is time varying as well as the interference, the objective is necessarily to optimize in the long-run (e.g. average) the payoff functions of all the nodes. The payoff function of node j at time k is denoted by r j (H k , p k ) where

H k := [h k (i,
sj 1 T x N s N 1 . . . T x 1 s 1 j . . . s jj rj T x N s N j Rx N T x 1 s 1 N . . . s j N T x N s N N rN Figure 2.2: Interference Channel Model
In Section 2.3, we proved that our proposed algorithm converges to p * for any type of payoff functions which satisfies the assumptions in Section 2.3. In order to show numerically that our algorithm converges to p * , we run our algorithm for a simple payoff function. In parallel, we obtain analytically the Nash equilibrium p * and compare the convergence point of our algorithm to p * . We therefore choose a simple payoff function for which p * can be obtained analytically.

The payoff function of node j at time k has then the following form:

γ j (H k , p k ) = ω bandwidth log(1 + SIN R j p j,k g jj,k σ 2 + j ′ =j p j ′ ,k g j ′ j,k ) Rate - κp j,k constraint on powers (2.20)
where ω represents the bandwidth available for transmission. The above payoff function γ j (H k , p k ) consists of log of (1 + SIN R j ) of user j and the unit cost of transmission is κ. It is assumed that a user doesn't know the structure function γ j (.) or the law of the channel state. For the above payoff function to ensure the assumption A3-A4 and Remark 6,7 we need to satisfy the condition

E|h jj | 2 ≥ E j ′ =j |h j ′ j | 2 . Please see appendix A for more details.
The problem here is to maximize the payoff function γ j (H, p) which is stated as follows: find p * such that for each user j ∈ N , satisfies p * j ∈ arg max p j ≥0 Eγ j (H, p * 1 , . . . , p * j-1 , p j , p * j+1 , . . . , p * N ). Note that when g jj = 0 then the payoff of user j is negative and the minimum power p * j = 0 is a solution to the above problem. For the remaining, we assume that |h jj | 2 = g jj > 0.

The channel h jj ′ is time varying and is generated using an independent and identically distributed complex Gaussian channel model with variance σ 2 jj ′ such that σ jj = 1 σ jj ′ = 0.1, ∀j ′ = j. The thermal noise is assumed to be a zero mean Gaussian with variance σ 2 such that σ 2 = 1.

We consider the following simulation settings with N = 2 for the above wireless model: k 1 = 0.9, k 2 = 0.9, φ 1 = 0, φ 2 = 0,Ω 1 = 0.9, Ω 2 = 1, b 1 = 0.9, b 2 = 0.9. The numerical setting could be tuned in order to make the convergence slower or faster with some other tradeoff. Due to space limitations further discussion on how to select these parameters has been omitted. p 1,0 and p 2,0 represent the starting points of the algorithm which are initialized as p 1,0 = p * 1 + 10 and p 2,0 = p * 2 + 10. κ = 2 is the penalty for interference, ω = 10 is the bandwidth and the variance of noise is normalized. The example we discussed is only one of the possible types of applications where our proposed algorithm can be implemented.

Consider for example the following payoffs: q 1 (.) = goodput(.) and q 2 (.) = P(goodput(.) < η) where η is a small value and P(.) stands for probability. Goodput represents the ratio of correctly received information bits vs the number of transmitter bits. In wireless communications the channel is constantly changing due to various physical phenomenon and interference from other sources and changes in the environment. It is hard to have a closed form expression for q 1 (.) due to complexity of the transmitter, receiver and unknown parameters. In practice, at each time k, the receiver has therefore a numerical value of goodput(.) but no closed form expression for rate/goodput is available especially for advanced coding scheme (e.g. turbo code, etc.). q 2 (.) represents an outage probability for which also depends on the goodput, the gradient for q 2 (.) is notoriously hard to compute without channel and interference statistics knowledge (probability distribution function) and closed form expression of goodput(.). Our scheme can be particularly helpful in such scenarios.

The price/design parameter κ inside the reward function can be tuned such that the solution of the distributed robust extremum coincides with a global optimizer of the system designer. The κ can be same for all nodes or each node can have its own κ j . Let a * g represent the optimal action or set of actions to be performed by each node to maximize their respective utilities. It is possible to set κ such that the following equation is satisfied.a(κ) = a * g . κ could represent a scalar or a vector depending on the system size and the application. To be able to effectively make a(κ) equal to a * we need to have enough degrees of freedom in the system. However this type of tuning is not true in general.

Numerical Example B: Distributed Beamforming

We consider a system model with M transmitter-receiver pairs as shown in Fig 2 .6 (where M = 2 for simplicity), where each access point AP j is equipped with N t transmitting antennas and each user U j has one receiving antenna. Furthermore, we assume that the transmitters and receivers are not mobile. Let a ij ∈ C 1×Nt represent the complex channel between transmitter AP j and user U i ∀i, j ∈ M 2 , where M := {1, . . . , M }.

The channel between all transmitter and receivers is assumed to be line of sight (LoS) and frequency flat. From [START_REF] Karipidis | Far-field multicast beamforming for uniform linear antenna arrays[END_REF] we know that Vandermonde a ij := 1, e -iϕ ij , . . . , e -iϕ ij (Nt-1) ∀i, j ∈ M

(2.21)

Let ϕ ij be defined as

ϕ ij := 2πd sin(θ ij ) λ
, and i = √ -1. Where d is the antenna separation and λ is the wavelength of the carrier frequency f and

θ ii = θ ij ∀i = j ∈ M.
The signal received by each receiver U j is given as y j ,

y j = Useful Signal a jj w j s j + i =j a ij w i s i Interference Signal + Noise n j (2.22) w0 w1 w... wNt-1 d AP 1 U 1 a( θ11 ) θ 11 1l {Γ 1 ≥γ 1 } U 2 a ( θ 2 1 ) θ 21 w0 w1 w... wNt-1 d AP 2 U 1 a ( θ 1 2 ) θ 12 U 2 a( θ22 ) θ 22 1l {Γ 2 ≥γ 2 } Figure 2.6: System Model with M = 2
where w j is the pre-coder associated with the transmitter j, a jj w j s j is the useful signal for receiver j, i =j a ij w i s i is the interference coming from the transmitters i = j, and n j represents the additive white noise with zero mean and σ 2 j variance associated with the receiver j. s j represent the symbol intended for user j with a symbol power of |s j | 2 = 1. The symbols are assumed to be mutually uncorrelated. Based on the above description it is clear that the transmitter AP j is operating in diversity mode i.e. only one symbol is transmitter per time slot.

Based on the above knowledge we can write the signal to interference and noise ratio (SINR) Γ j of U j as

Γ j := |a jj w j | 2 σ 2 j + i =j |a ij w i | 2 ∀i, j ∈ M 2 (2.23)
We consider a case with M = 2 transmit-receiver pairs where each transmitter is equipped with N t = 4 transmit antennas. It is worth noting that this simple case of M = 2 is considered only for illustration clarity (in fact for this simple case we can find analytically a closed form expression of the Nash equilibrium and therefore we can compare the direction of transmission (DoT) obtained by our algorithm to this equilibrium), but obviously our scheme and the analysis done so far in the thesis hold for larger but finite M. The values of the sinus perturbation parameters associated with equations (2.4) and (2.5) are given below. We summarize the system and simulation parameters in Table 2.3 and 2.4 respectively. Interested readers are referred to [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] for more details on how to select the parameters in Table 2.4.

φ j 0 0
For the above setting, we can show that Nash equilibrium is achieved if each AP j transmits in a direction close to U j i.e. to say It is worth mentioning that using fixed step size has the advantage of faster convergence rate as compared to vanishing step size at the expense of converging to a neighborhood of Nash (instead of converging to Nash). Comparison between fixed and vanishing step sizes is omitted due to space limitation.

ψ j ≈ θ jj ∀j ∈ [1, 2].

Numerical Example C: Nash Bayesian Estimation

As the demand for wireless capacity is increasing, the cell sizes are shrinking to accommodate greater capacity and higher frequency reuse. Femtocells (FCs) are used to provide coverage and capacity to more users in a concentrated area using the shared wireless resources. Typically one or more FCs are deployed in an Typically FCs use the same frequency as the macro cell which leads to several power control problems at the cell edge of the FC which is contained in the MC.

FCs are user deployed and could be located randomly throughout a MC. Open access FCs allow MC users to access the network through them and closed access FCs don't allow macro users to have access to the network [START_REF] Xia | Open vs. closed access femtocells in the uplink[END_REF]. In this thesis we will deal with closed access FCs. When a macro user located in the neighborhood of a FC is operating at the same frequency, it will receive strong interference from the FC users and femto access point (FAP) which results in significant degradation in performance. In such cases it is important to implement distributed power control that achieves a tradeoff between the quality of service (QoS) (or success probability) of femto users and that of macro users. We attempt to study such scenarios in this thesis. Some of the recent works dealing with femto-macro power control and interference management are described hereinafter. In [START_REF] Chandrasekhar | Uplink capacity and interference avoidance for two-tier femtocell networks[END_REF], the uplink capacity and interference avoidance for twotier FC networks are discussed. In However, in a realistic scenario where the users mobility cannot be modeled by a poisson point process and where the environment is dynamic, an accurate closed form expression of the SINR density is hard to obtain. In addition, the interference depends on the decision of the other transmitters which makes the density characterization of the interference and therefore the SINR very challenging. Besides, in the standard power control framework [START_REF] Yates | A framework for uplink power control in cellular radio systems. Selected Areas in Communications[END_REF], the iterative power control (the power at time step k is updated using the SINR at time step k -1) can achieve a target SINR under the assumption that the channel stays constant until the algorithm converges. In the current work, we assume that the wireless channel changes from one time step to another.

Figure 2.9 shows our system model. It is worth noting that although one user per femto (respectively per macro) is shown/used, our analysis holds for any number of macro and femto users and our analysis extension to this case is straightforward. It should be mentioned here for clarity that we are only considering the downlink scenario for femto and macro users. Let the macro access point (MAP) and the macro user (MU) be represented by subscript M , m respectively and the femto access point (FAP) and its femto user be represented by the subscript F , f respectively. Let h M m represents the channel between the MAP and the macro user, h F j f i represents the channel between the FAP j and the femto user i, and h F j m represents the interference channel between the FAP j and the macro user. This channel h F j m is typically unknown. h M f i represents the channel between the MAP and the femto user i. Let g M m |h M m | 2 be the channel gain between the MAP and the macro user. Similarly, we define

M m f 1 f 2 F 1 F 2 h F 1 f 1 h F 2 f 2 h M m h F 1 m h F 2 m h M f 1 h M f2 h F 1 f 2 h F 2 f 1 Figure 2.9: Macrocell containing two FCs g F j f i |h F j f i | 2 , g F j f i |h F j f i | 2 , g F j m |h F j m | 2 and g M f i |h M f i | 2 .
Here we consider a situation where both FAPs and MAP are using the same frequency in the downlink and generating interference to each other's users.

The downlink SINR of macro user Γ m is defined as

Γ m p M g M m σ 2 m + 2 i=1 p F i g F i m
(2.24)

Where p M is the MAP power allocated to the macro user m. p F i is the power of the FAP i, σ 2 m is the noise variance and 2 i=1 p F i g F i m represents the interference caused by the FAPs 1 and 2 on the macro user.

The downlink SINR of femto user i Γ f i is defined as

Γ f i p F i g F i f i σ 2 f i + j =i p F j g F j f i + p M g M f i (2.25)
Where σ 2 f i is the noise variance, j =i p F j g F j f i is the inter femto interference and p M g M f i represents the interference coming from the MAP. In addition, we assume that the MAP and FAPs have imperfect knowledge of their own users' SINRs. The observed SINR, respectively for macro and femto users, is therefore given as,

Γ k m = Γ k m + v k m (2.26) Γ k f i = Γ k f i + v k f i (2.27)
where v m and v f i represent the respective errors due to feedback delays, channel estimation errors or quantization errors. To ensure that macro user is given priority while maintaining a reasonable quality of service (QoS) for the femto users we formulate the following problem. Let the objective be to maximize the rewards R m and R f i of macro and femto respectively (given respectively by equations (2.28) and (2.29)) where the rewards are constructed from the probabilities of success of femto and macro users. This type of rewards is more robust and ensures better QoS as compared to some existing works that maximize the expected SINR of each user.

R m = αE γm [P(Γ m ≥ γ m )]
(2.28)

R f i = βE γ f i [P(Γ f i ≥ γ f i )] -α (1 -E γm [P(Γ m ≥ γ m )]) (2.29)
γ m and γ f i are the target SINRs for respectively macro and femto users. α > 0 and β > 0 are design parameters which can be adjusted to find the desired balance in performance between the femto and the macros. In the aforementioned formulation, the MAP tries to maximize the success probability of its own users without considering the presence of the FC users. It is the responsibility of the FAP to operate in such a way that it minimizes the interference to nearby macro users while trying to maintain a reasonable success probability for its own users. Notice also that the technique/analysis provided in the sequel still holds when the MAP tries also to obtain a tradeoff between the success probabilities of the macro and femto users, i.e. when

R m = αE γm [P(Γ m ≥ γ m )] -β 1 -E γ f i [P(Γ f i ≥ γ f i )]
. Obviously, our analysis/framework holds as well when the FAP attempts to maximize the success probability of its own users without considering the macro users (i.e.

R f i = βE γ f i [P(Γ f i ≥ γ f i )]
). Furthermore, in the presence of multiple macro users, each user will have a reward function defined as in (2.28) and the objective of the macro cell in this case will be to maximize the sum of the rewards of all users (similar extension can be done in the case of multiple femto users). For clarity of presentation and ease of notation, we will limit ourselves to one user per femto (two FCs) and one macro user.

Furthermore, the targets γ m and γ f i are determined by the network (e.g FAP, MAP) such that the signals are decoded with small Block Error Rate (BLER) and a minimum QoS is therefore ensured for users. It is worth noting that the target SINRs γ m and γ f i may not be constant over time since the environment type is dynamic (e.g. the wireless channel type may change during the connection from an Outdoor Channel to an Indoor Channel and the target SINR must be updated in this case). This dynamic adaptation of the target SINR explains the presence of E γ [.] in the rewards in equations (2.28) and (2.29) which represents the expectation over the values of target γ m and γ f j attributed by the macro and femto access points (FAPs). In addition, it is evident that our framework holds when the target SINR is constant. We assume that the target γ m is available to the FAP through a backhaul between MAP and FAP. In the absence of a backhaul between FAP and MAP, the FAP can listen to the downlink control channel of the MAP (since both are using the same technology/standard) where such information is usually sent. One can also assume that γ m is broadcasted by the MAP and that the FAP can listen to the broadcast channel. It should be mentioned here that these targets γ m and γ f j change slowly because they depend on the type of environment, as for example transition from outdoor to indoor or vice versa happens slowly. Notice that in cellular networks, the base station/AP updates the target SINR using the outer loop power control (called also slow loop power control as the update of the target SINR happens slowly) and informs the users of the updated target SINR using the downlink control channel. The update algorithm of target SINRs falls out of the scope of this work. Notice that in the case when the FAP tries to maximize the success probability of its own users without considering the macro users (i.e.

R f i = βE γ f i [P(Γ f i ≥ γ f i )]
), there is no need to exchange the target γ m between the MAP and the FAP.

Using the reward functions defined in equations (2.28) and (2.29), the distributed stochastic power control problem can be formulated as follows.

max

p M ,p F 1 ,p F 2 R x ∀x ∈ {m, f 1 , f 2 } (2.30)
The success probabilities P(Γ m ≥ γ m ) and P(Γ f i ≥ γ f i ) are given as,

P(Γ f i ≥ γ f i ) ∞ γ f i Φ(Γ f i )dΓ f i P(Γ m ≥ γ m ) ∞ γm Φ(Γ m )dΓ m
where Φ(Γ m ) and Φ(Γ f i ) are respectively macro and femto SINR densities. It is well known that Gaussian assumption of SINRs densities is not accurate since the SINR depends on various random parameters such as users' mobility, dynamic environment, wireless channel conditions as well as dynamic interference (that depends itself on the decision of other transmitters/users). Therefore the SINR density does not have an accurate closed form expression which makes the distributed stochastic optimization problem in (2.30) very hard. The above problem cannot be solved using standard optimization techniques because of the complexity and randomness associated with such rewards. In order to solve the above problem, we first present a stochastic learning technique based on our recently developed theory in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] that uses sinus perturbation and the instantaneous numerical value of the reward of to approach the problems defined in (2.30). As this techniques required the numerical value of the reward which is based on the density of SINR, we need to track the density Φ(Γ m ) and Φ(Γ f i ) using the imperfect instantaneous estimated SINR. Since the expression is too complicated, only numerical values of the rewards in (2.28) and (2.29) can be obtained/estimated at each time (due to some complicated integral expressions).

Notice that, in order to obtain numerical values of the reward in (2.29), we exploit the fact that MC and FCs users are using the same standard and the FAP can listen to the uplink control channel of the macro user. For example, when the macro user who is at the cell edge of the FC transmits its SINR Γ m to its MAP, the FAP can listen to this Γ m . However, we stress that this is necessary only because of the definition of the reward in (2.29). If instead of maximizing the reward in (2.29), the FAP tries to maximize the success probabilities of its own users (i.e. if R

f i = βE γ f i [P(Γ f i ≥ γ f i )]
), the aforementioned assumption is not needed (i.e. the FAP does not have to listen to Γ m ).

The problem in (2.30) can be solved using our Nash Seeking theory developed in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] as follows. At each time instant k, each transmitter updates its power p k X (recall that X could be either M or F i ), by adding the sinus perturbation to the intermediary variable pk X using equation (2.31), and transmits using p k X . Then, each transmitter (AP) computes a realization of the reward R k+1 x at time k + 1 which is used to compute the intermediary variable pk+1 X using equation (2.32). The power p k+1 X is then updated using equation (2.31). This procedure is repeated for the whole transmission window (connection duration) T > 0.

The update is done in discrete time and is given by,

p k X = pk X + a X sin(Ω X k + φ X ) (2.31) pk+1 X = pk X + λ k l X a X sin(Ω X k + φ X )R k+1 x (2.32)
where the grow rate l X > 0 has a small value and the step size λ k (also known as the learning rate) has also a small value 0 < λ k < 1 (e.g.

λ k = 1 k+1 ). In addition, k := k k ′ =1 λ k ′ , and φ X ∈ [0, 2π] ∀ X ∈ { M , F 1 , F 2 }. The condition Ω X = Ω X ′′ , Ω X ′′ + Ω X = Ω X ′ need
to be satisfied such that the perturbations are orthogonal to ensure convergence of the algorithm. The above framework is only applicable to functions which are Lipschitz continuous and the existence of the equilibrium is assumed. One can refer to [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF][START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] for more details.

Bayesian Density Tracking

In order to use the extremum seeking framework provided in section 2.2.1 we need to estimate a numerical value of the reward which is based on the density of the SINR. In this section we use Bayesian Theory for SINR density tracking, we first model the SINR evolution as a dynamic state equation (not necessarily linear) as follows.

The transmit powers of the MAP and FAPs evolve according to the following equations.

p k+1 M = p k M + η k M , p k+1 F i = p k F i + η k F i .
Where k represents the discrete time index and η k M and η k F i are the power deviation between times k and k + 1.

We can write the SINR of macro user at time k + 1 as

Γ k+1 m = (p k M + η k M )g k+1 M m σ 2 m + 2 i=1 (p k F i + η k F i )g k+1 F i m
For simplification we define the variable ǫk

m ǫk m η k M g k+1 M m σ 2 m + 2 i=1 (p k F i + η k F i )g k+1 F i m
The channel gain g k M m evolves according to the following dynamic equation,

g k+1 M m = g k M m + ̺ k M m
where ̺ k M m is an ergodic stochastic process. Putting the value of ǫk m in the above equation we get.

Γ k+1 m = p k M g k+1 M m σ 2 m + 2 i=1 (p k F i + η k F i )g k+1 F i m + ǫk m Γ k+1 m = p k M g k+1 M m σ 2 m + 2 i=1 p k F i g k F i m (1 + ǫ k m ) + ǫk m (2.33)
where

ǫ k m 2 i=1 p k+1 F i ̺ k F i m + 2 i=1 η k F i g k+1 F i m σ 2 m + 2 i=1 p k F i g k F i m
In addition, we define ǫk m as follows,

ǫk m p k M ̺ k M m σ 2 m + 2 i=1 p k F i g k F i m (1 + ǫ k m ) + ǫk m
Using the above fact, equation (2.33) can be written as

Γ k+1 m = Γ k m 1 + ǫ k m + ǫk m that implies, Γ k+1 m = Γ k m ∞ l=0 (-ǫ k m ) l + ǫk m (2.34)
It is worth noting that in all iterative power control strategies (also in learning techniques) the state difference or power deviation between two consecutive iterations has to be small in order to ensure the convergence. Therefore, ǫ k m is small ∀ k. Similarly it can be shown that the SINR Γ f i can be written as

Γ k+1 f i = Γ k f i ∞ l=0 (-ǫ k f i ) l + ǫk f i (2.35)
where ǫ k f i is small ∀ k. Note that ǫk m and ǫk f i can be considered as random variables.

The SINRs of macro and femto users evolve according to equations (2.34) and (2.35), hence dynamic state equations and Bayesian theory can be used for density tracking.

For ease of notation and to conserve space we introduce the following SINR notation Γ k

x , (where index x could be either m or f i and X could be either M or

F i ). We also use the notation Γ k+1 x = f k x (Γ k x , ǫk x ) to represent equation (2.

34) or (2.35).

We stress that only an imperfect measurement Γ k x of Γ k x is available at time k. We use the notation Γ k x = h k x (Γ k x , v k x ) to represent equation (2.26) or (2.27). We thus define D k

x as the set of previous imperfect SINR measurements till time k, i.e. D k x = { Γ i x : i = 1, . . . , k}. We also denote by Φ(Γ k x |D k-1 x ) the SINR density estimation assuming that the set of measurements D k-1 x is available.

Using recursive Bayesian estimation from [GSS93], we can track the SINR density Φ(Γ k

x |D k x ) as follows. First, we find the density Φ(Γ k x |D k-1 x ) and then we estimate the required density Φ(Γ k

x |D k x ). Φ(Γ k

x |D k-1 x ) can be obtained using the following equation (2.36) from [START_REF] Gordon | Novel approach to nonlinear/non-gaussian bayesian state estimation[END_REF],

Φ(Γ k x |D k-1 x ) = Φ(Γ k x |Γ k-1 x )Φ(Γ k-1 x |D k-1 x )dΓ k-1 x (2.36)
where

Φ(Γ k x |Γ k-1 x ) = Φ(Γ k x |Γ k-1 x , ǫk-1 x )Φ(ǫ k-1 x |Γ k-1 x )dǫ k-1 x using the fact that Φ(ǫ k-1 x |Γ k-1 x ) = Φ(ǫ k-1 x ) we have Φ(Γ k x |Γ k-1 x ) = δ(Γ k x -f k-1 x (Γ k-1 x , ǫk-1 x ))Φ(ǫ k-1 x )dǫ k-1 x (2.37)
Where δ(.) is a dirac function. The dirac function arises because when Γ k-1

x and ǫk-1

x are known, Γ k x is obtained from equation (2.34) or (2.35); i.e. Γ k x = f k-1 x (Γ k-1
x , ǫk-1 x ) . Now we are able to estimate the density Φ(Γ k x |D k-1 x ) by putting the value of Φ(Γ k

x |Γ k-1 x ) from equation (2.37) into equation (2.36). At time step k, the set of measurements D k x becomes available. Using the Bayes' rule, we can update the SINR density Φ(Γ k

x |D k x ) using the following equation,

Φ(Γ k x |D k x ) = Φ( Γ k x |Γ k x )Φ(Γ k x |D k-1 x ) Φ( Γ k x |D k-1 x ) (2.38) where Φ( Γ k x |D k-1 x ) = Φ( Γ k x |Γ k x )Φ(Γ k x |D k-1 x )dΓ k x Φ( Γ k x |Γ k x ) = δ( Γ k x -h k x (Γ k x , v k x ))Φ(v k x )dv k x Φ(Γ 1 x |D 0 x ) ≡ Φ(Γ 1 x )

Joint Density Tracking and Power Control Algorithm

By combining the techniques described in section 2.2.1 and 2.6 we get the following density tracking and power control algorithm (see Algorithm 3 below).

First each users initializes Φ(Γ 1 x |D 0 x ) with a distribution Φ(Γ 1 x ), then each access point (AP) X initializes its power and transmits. After this the loop begins. At time k each AP observes Γ k m and Γ k f i which are the noisy versions of the SINRs and updates their previous density according to equation (2.38). Then each AP estimates its reward R k

x from equation (2.28) or (2.29), then this reward is used to calculate the power according to (2.31). This power is used for making the transmission. This process is repeated until horizon T (which is the connection duration). In the next section we present the numerical results which show that our algorithm performs better than existing methods. We used the following settings for simulating the above framework. The macro cell radius is equal to 500m whereas the radius of each femto is 25m. We consider a frequency selective Rayleigh fading channel with exponential delay profile. The power spectral density of noise is -174 dBm/Hz. The path losses are calculated according to Cost-Hata Model. In addition, we used the following sinus framework parameters in the simulations. l f 1 = 2.5; l f 2 = 3.5; l m = 4.5;

1: At k = 1 initialize Φ(Γ 1 x |D 0 x ) ≡ Φ(Γ 1 x ) 2: Each AP X,
φ f 1 = 0; φ f 2 = 0; φ m = 0; Ω f 1 = 1.4; Ω f 2 = 1.2; Ω m = 1; b f 1 = 0.6; b f 2 = 0.3; b m = 0.1; α m = 1; β f i = 3.
Interested readers are referred to [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] for more details on how to select the above parameters. In addition, our results were generated using λ k = 1 k+1 (since we proved in [START_REF] Hanif | On the convergence of a nash seeking algorithm with stochastic state dependent payoffs[END_REF] the convergence to Nash equilibrium for λ k = 1 k+1 ). The results for success probability are presented in Figure 2.10 where we compare our scheme to the widely used standard power control scheme from [START_REF] Yates | A framework for uplink power control in cellular radio systems. Selected Areas in Communications[END_REF].

Figure 2.10 shows that, with our proposed scheme, both femtos and macro cells are able to maintain a success probability of 65 -75% which is much better in comparison to the Yates method [START_REF] Yates | A framework for uplink power control in cellular radio systems. Selected Areas in Communications[END_REF]. It should be noted here that achieving a success probability of 65 -75% for macro and femto users is quite significant considering that we are dealing with fully distributed stochastic system with interacting player/APs, using only imperfect SINR. Please also refer to Figure 2.11 which shows the Pareto boundary for our conditions. A Pareto plot is generated by using all possible transmit power scenarios by all the APs, and it is desirable to be as close to the boundary as possible as that gives the best performance for all users. The white circle in Figure 2.11 represents our operating region which is quite close to the boundary. It is evident that achieving higher success probability for macro and femto users simultaneously is quite difficult in a stochastic environment. involves outsourcing the equipment used to support operations, including storage, hardware, servers and networking components. The increasing selection of services delivered over the Internet is sometimes referred to as XaaS, where XaaS refers to anything as a service." [START_REF] Rouse | Spi model (saas, paas, iaas)[END_REF]. In IaaS cloud computing paradigm a virtual machine (VM) is offered to paying clients as a service. A virtual machine as the name implies is a virtual computing terminal hosted over physical servers.

Virtual machines are created on demand and are able to satisfy client demand for a remotely accessible machine with a give set of hardware specifications.

The VM has certain hardware specifications such as a CPU clock rate RAM and available storage space, which defines a certain minimum performance criterion. Chip Microprocessor (CMP) architecture is a scalable and cost effective architecture where a could comprises of a large number of commodity hardware which is relatively cheap as compared to having specialized hardware. The VM reside on top of chip microprocessor architecture (CMP) which enables them to be scalable by using shared resources. There is contention between the VMs as they are using these shared physical resources like storage space, CPU processing power and last level cache (LLC). As all these machines have their respective services level agreement (SLA) i.e. minimum performance criterion that needs to be ensured. The resource contention could cause violation of the SLA of individual VMs as more virtual machines are hosted by a given number of physical machines. An example of resource contention at the cache level is the following.

For example a Sun microprocessor with a 3MB Level 2 cache can share this cache among 32 different threads of execution. These different threads could belong to instances of 32 different VMs, in which case the resource management needs to be done in an efficient manner such that the SLA for each individual user is satisfied. There can be similar examples in the context of storage space and available CPU processing time for each VM.

So it is very important to manage these various resources in an efficient manner. This concept of contention in cloud based resources can be modeled using the concept of game theory. Following are some related works where game theory has been used in the context of cloud computing. In such a situation, but in a different context, Tullock (1980, [Tul80]) proposed a game-theoretic setting with probabilistic reward in rent-seeking. He has noticed earlier that the social loss associated to rent-seeking behavior exceeds a certain threshold.

From a cloud networking perspective, this means that lot of resources may be wasted if the VM consider an economic renting. In this chapter, we study a stylized model of resource sharing in a distributed and fair manner. We will show that efficiency can be significantly improved for large cloud networks using a suitable price design. We examine both stability and myopic reaction using mean-field-taking strategies [START_REF] Als | The evolutionary stability of perfectly competitive behavior[END_REF]. Mean field games are known to be welladapted for both finite (but large) and infinite systems Please refer to [START_REF] Gueant | Paris-Princeton Lectures on Mathematical Finance[END_REF] for an introductory reference on mean field games. In contrast to the other classical tools for large-scale systems, the mean-field approach incorporates the dynamics which allows online demand management (pay-as-you-use scheme). It allows optimization, control and dynamic mechanism design when the number of active users varies and studies the interactive nature of cloud networking, leading to strategic decision-making problems. Recent studies on cloud networking have already adopted a mean-field regime.

Overview

Game-theoretic approaches to cloud networking

The concept of cloud networking is very old but it has recently become a reality. There are several aspects of cloud networking that still need to be discussed. Game-theoretic tools for cloud networking have been recently proposed in [START_REF] Gupta | Cloud resource allocation games[END_REF]. The authors in [START_REF] Gupta | Cloud resource allocation games[END_REF] studied cloud resource allocation games. The work in [START_REF] Wei | A game-theoretic method of fair resource allocation for cloud computing services[END_REF] presents a game-theoretic method of fair resource allocation for cloud services. They proved the existence of a Nash equilibrium under feasibility condition of the resource allocation problem. [MCL + 10] examines a resource allocation for VMs using Kelly's approach. The authors in [KDF + 11] has studied optimal service pricing for cloud cache services. [START_REF] Orna Agmon Ben-Yehuda | The resource-as-a-service (RaaS) cloud[END_REF] studied the framework of Resource-as-a-Service (RaaS). In [START_REF] Khan | Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation[END_REF] a non-cooperative, semicooperative, and cooperative games-based grid resource allocation are examined.

[RY12] proposed a game-theoretic approach for the provisioning and operation of the infrastructure under uniform cost models. The authors in [START_REF] Künsemöller | A game-theoretical approach to the benefits of cloud computing[END_REF] tried to answer the question whether or not to utilize the cloud for processing, by identifying characteristics of potential cloud beneficiaries and advisable actions to actually gain financial benefits. They proposed a game-theoretic model of an Infrastructure-as-a-Service (IaaS) cloud market, covering dynamics of pricing and usage. The work in [APP11] modeled a service provisioning problem in cloud as an action-coupling constrained game, and proposed an efficient algorithm for the run time management and allocation of IaaS resources to competing SaaS (Software as a Service). The authors in [START_REF] Teng | A new game theoretical resource allocation algorithm for cloud computing[END_REF] proposed a Bayesian Nash Equilibrium Allocation algorithm to solve resource management problem in cloud networking under heterogeneous distribution of resources and incomplete information. The concept of heavy traffic approximation of equilibria in resource sharing games is studied in [START_REF] Wu | Heavy traffic approximation of equilibria in resource sharing games. Selected Areas in Communications[END_REF].

Our work differs from the above references in three ways. First, the above reference do not examine the stability of the solution concepts. Second, their approaches seem not to be adapted to large-scale systems. Third, the references [RY12, KK12, APP11, TM10, WVZX10, KA06] do not propose simple, memoryless and easy-to-implement learning algorithms. In this chapter we will address these three issues.

Large-scale clouds

Large data and large number of users are frequently met in the context of cloud networking, such as in Amazon's Elastic Compute Cloud (Amazon EC2) which is a web service that provides resizable computing capacity in the cloud. As systems become large traditional game theoretic analysis result in computationally inefficient frameworks as they take into account effect of each unique action by every player. Recently, there has been renewed interest in developing largescale strategic learning also called mean-field learning. These frameworks are very efficient at simplifying the system structure giving us few parameters such as the mean instead of tracking the unique action of each user. This not only helps in computationally when simulating or analyzing these systems, but it also drastically simplifies the mathematical analysis giving us the averaged effect of the interaction of a large number of particles instead of tracking each particle.

[AJ10, AAJW07, Hua12] Thus, mean-field learning is an important framework for large-scale cloud networks. Such a problem is tackled in [START_REF] Parikh | Block splitting for large-scale distributed learning[END_REF] using block splitting for large-scale distributed learning. We refer the reader to Chapter 1 of [START_REF] Tembine | Distributed strategic learning for wireless engineers[END_REF] for a recent survey book on distributed strategic learning.

Contribution

Although here we consider cloud networks, our resulting analysis is more general and is applicable to similar resources sharing networks. The contribution of this chapter can be divided into two main parts: i) Equilibrium analysis of two different resource sharing problems for finite and infinite number of clients and ii) development of low complexity distributed learning algorithms that can achieve the equilibrium solutions. The equilibria analysis shows the interest of using mean field theory in the cloud as on one hand it simplifies hugely the analysis of the game and allows thus developing low complexity iterative learning solutions that converge to the equilibrium (see section 3.4.2). Our contributions is this chapter are listed below:

• We first consider a cloud resource sharing problem with continuous action spaces where each user tries to maximize its own payoff. The payoff depends on the fraction of resources (e.g. LLC memory, CPU power, etc.) allocated to the user. This problem can be applied to the cases where each user tries to get VMs with resources as much high as possible in order to reduce for example the computation time of his own tasks. This can be applied to the case where the cloud does not have enough physical resources to satisfy all the current clients' demands (especially for very high number of users). In the finite regime (finite number of users), we provide closed-form expressions of three important game-theoretic solution concepts: Nash equilibrium (NE), finite myopic mean-field response (F-MFR) and finite evolutionary stable strategy (F-ESS). The first surprising result is that the Nash equilibrium is not an evolutionary stable strategy for finite population (see Proposition 2). In fact in cloud networks, the number of users as well as users' demands are constantly changing and in this context evolutionary stable strategy (i.e. it cannot be invaded by small fraction of deviants) is crucial. Based on the work of Possajennikov (2003, [Pos03]) we show that mean-field-taking strategies are evolutionary stable strategies for a certain range of return index (i.e. α). We provide the explicit optimal pricing as a function of the number of active users. Under the optimal pricing no resource is wasted at the equilibrium. This means that the efficiency loss tends to zero.

• We then consider the infinite regime, because in many cloud networks the number of users is expected to be very high. We provide closed-form expression of the mean-field equilibrium and show how the mean field theory simplifies the analysis in this regime. Furthermore, we show that the mean-field equilibrium is an evolutionary stable strategy, i.e., it cannot be invaded by a small fraction of deviants. We show that the mean-field equilibrium is evolutionary stable for any fraction of deviants strictly less than 100% which makes our result even stronger. We also show that Nash equilibrium is stable in the infinite regime. This is due to the fact that in the limiting case, the influence of one generic player on the total demand is negligible.

• We then consider another resource sharing problem in the cloud where each user tries to satisfy anytime anywhere its own request (for example when enough physical resources are available for all users). The problem is formulated as a satisfactory game. In the finite regime, we provide a closed form expression of the satisfactory solution and develop a distributed algorithm which is able to reach it. Contrary to the aforementioned equilibrium concepts, the extension of the obtained satisfactory solutions to the infinite regime is straightforward.

• We then provide distributed iterative learning algorithms that converges to the equilibrium solutions of the first resource sharing problem discussed above. for the finite regime, we provide an Ishikawa-based distributed iterative learning algorithm that converges to each of the three aforementioned equilibrium concepts and discuss its convergence time. It is worth mentioning that developing learning algorithms with less information and having faster convergence time is of high interest. We therefore propose a model-based (but still with less information) learning scheme for games with continuous action space and large number of players. Each player will update its learning strategy based on an aggregative term, which is the mean of an increasing function of the action of the other players. Each player will be influenced by the aggregate, and the mean-field behavior is formed from the action of each player. Each player will try to conjecture the aggregative term consisting of the actions of the other players at each time slot, and will respond to the aggregative term locally. This drastically simplifies the dimensionality of the mean-field response system in the asymptotic case. We also discuss the convergence time of the proposed learning algorithm and show that it is faster than the Ishikawa-based algorithm or standard contraction mapping fixed-point algorithms.

Structure

The remainder of the paper is organized as follows. In section 3.2 we present the resource sharing and the demand satisfaction framework. In Section 3.3 we examine both equilibrium and stability properties of the game with finite number of VMs and asymptotic game with infinite number of VMs. In section 3.4 the algorithms used to approach the equilibria are presented. In section 3.5 numerical results are presented.

Model

We consider resource (i.e. last level cache (LLC)) sharing between n virtual machine (VM) instances. These VMs, maximize their performance by increasing their access to the shared LLC. These VMs are trying to share the total available cache capacity given by c n among themselves in a fair fashion. It is interesting to analyze this type of problem in the context of game theory. As there in contention between various instances of the VM, each of these VM can be considered a player in a game competing for the same resources. Notice also that the physical resources in the cloud are not centralized (i.e. in one machine) which justify the need for a game framework.

There are several types of problems or scenarios that arise in this context.

We focus here on two resource sharing problems. The first problem corresponds for example to the case where there are not enough resources of cache available to satisfy all clients or players. In such scenario we define a reward function which is based on a resource sharing strategy where each client demands a percentage of the total available cache capacity c n and pays a price for this access. This ensures that there is fair sharing of the resources among the clients. The remaining demand of each client is met by secondary sources which are relatively more expensive. This first problem can arise also when there are enough resources for all clients and the clients try to get as much resources as possible in order to increase the performance of their VMs (e.g. in order to minimize the computation time of the required tasks). In the next two sections (3.2.1 and 3.2.2) we shall describe the resource sharing game for the finite and the infinite number of clients for such a scenario. The second scenario described in section 3.2.3 represents the case when the total available cache capacity is higher than the total demand and each client wants to use a given percentage of the total capacity/resources (satisfaction game).

Resource sharing game G n with finite number of clients

We consider resource sharing game with finite (but arbitrary) number of clients in a cloud network. We denote such a game by G n , where n is the number of clients. The action space of every client is A = R + which is a convex set, i.e., each player j chooses an action a j that belongs to the set A. An action may represent a certain demand for a resource. In case of cloud computing the demand could be the CPU access duration or the share of a percentage of total LLC memory. For example in case of a computation intensive task where several VMs are running simulation related computation tasks and want to complete their computation tasks as soon as possible by demanding for as much resources as possible. All the actions together determine an outcome as the resources are shared. Let p n be the unit price of cloud resource usage by the clients. Then, the payoff of player j is given by

r j (a 1 , . . . , a n ) = c n h(a j ) n i=1 h(a i ) -p n a j , (3.1)
if n i=1 h(a i ) > 0 and zero otherwise. The structure of the reward function r j (a 1 , . . . , a n ) for client j shows that it is a percentage of allocated capacity minus the cost for using that capacity. Here, c n represents the value of the available resources (which can be seen as the capacity of the cloud), h is a positive and nondecreasing function with h(0) = 0. We fix the function h to be x α where α > 0 denotes a certain return index. The function h represents hence the efficiency of the demand in the access probability to the resource. This introduction of efficiency can be interpreted by the fact that the clients and the physical resources are distributed and are connected through internet or virtual private networks. This class of games have been studied by Tullock in the 1980s under the name of rent-seeking game. See Tullock (1980, [Tul80]). However [START_REF] Tullock | Efficient Rent Seeking[END_REF] does not examine stability, price design and algorithmic issues. The cloud game G n is given by the collection (N , A, (r j ) j∈N ) where N = {1, . . . , n}, n ≥ 2, is the number of potential players. We say that player j is active if its action a j > 0. We will see that what is important in our analysis is not the number of potential players N but the set of active players (those with non-zero demand). Therefore, we define the following variable:

m n 1 n n i=1 a α i 1 α
as a weighted α-norm of all the actions. m n will play the role of the meanfield term in the resource sharing game and will be useful in the development of iterative algorithm but also in the study of mean-field games. The payoff function can be rewritten as rn (a j , m n,-j ) r j (a) = cn n a j mn α p n a j , where the ratio cn n is the theoretical capacity per client in the cloud and

m α n,-j 1 n -1 i =j a α i = n n -1 m α n - a α j n
m n,-j represents the mean when the action of user j is not taken into account.

rn (a j , m n,-j ) = c n a α j m n,-j (n -1) + a α j -p n a j ,
The payoff function of a generic player j depends only on own-action a j and the mean m n . Note that m α n,-j does not depend on a j .

Remark 3. The payoff is discontinuous for i h(a i ) = 0. As we will see in the next sections the discontinuity of the payoff function (at the origin) can be handled in the equilibrium analysis.

As mentioned in [MCL + 10], the above payoff function has interesting connections with the seminal works of Kelly on capacity sharing problems. However, the approach presented here has additional features: (i) our approach is distributed and autonomous decision approach.

(ii) the evolutionary stability of the resulting system depends on the interactive and strategic behavior of each client, (iii) Our payoff is well adapted even if there is no coordination between the clients for joint decision-making, (iv) The mean-field approach and the evolutionary stable strategies of the finite game presented here complement the previous works.

Resource sharing game G ∞ with infinite number of clients

In current cloud network, the number of clients for clusters grows without bound and it is becoming increasingly important to dynamically share resources between these large population of clients. When the number of active clients is very large, we analyze the asymptotic game, denoted by, G ∞ = (A, r) where the payoff denoted by r can be obtained easily as follows (using the expressions of m n and r(a j , m n,-j ) defined above in the finite regime and then taking the limit when n tends to infinity) r :

A 2 -→ R, r(a j , m) =    ca α j m α -pa j , m > 0 0, m = 0, a j = 0
The numbers c > 0 and p > 0 are scaled asymptotic version of cn n and p n i.e. c = lim n-→+∞ cn n and p = lim n-→+∞ p n . The term m can be interpreted as a limit value of m n i.e. m = lim n-→+∞ m n . Therefore, we can write r(a j , m) = p ( c p a α j m αa j ). As we will see, one of the important terms in the equilibrium structure will be the ratio c p which can be interpreted as the inverse of the cost (price) per capacity.

We will show in the next section that the error gap between the mean-field game model and the finite game model is the error at which cn n 1 pn goes to c p together with a convergence rate of O( 1 n ). This result is interesting because when the system is large, one can approximate it by a very simple mean-field game model for any number of active clients that exceeds n ǫ in order to get an error that is at most ǫ. In addition the mean-field game system has additional features: it provides • A stable equilibrium that is resilient to small perturbations.

• The mean-field equilibrium is robust to perturbation by new entrants/exits in the sense that it remains within ǫ-equilibrium.

• The payoff at mean-field equilibrium is close to the payoff of all the finite games for any active number of clients above a certain threshold. This means that mean-field game model is also useful in finite regime (even at small scale).

Demand satisfaction game G s

In this subsection we analyze a different type of game where each client is interested in satisfying a given demand instead of trying to maximize a given reward function. First we provide the characterization of an equilibrium for finite clients and then we present a fully distributed algorithm which is able to reach this equilibrium. It is straight forward to extend the equilibrium characterization to the infinite case as it is shown at the end of this section. We restrict the set A to the interval [0, c n ].

We now examine learning satisfactory solutions in cloud resource sharing games with continuous action space. Our motivations for satisfactory solution seeking are the following: First, we observe that in dynamic interactive system, most clients constantly make decisions which are simply "good enough" rather than best response or optimal. Simon (1956, [Sim56]) has adopted the word "satisficing" for this type of decision. As mentioned by Simon himself in his paper in page 129, "Evidently, organisms adapt well enough to 'satisfice'; they do not, in general, 'optimize'. Therefore satisfactory solution offers an alternative approach and is closely model the way VMs make decisions [Sti03, GSF98, SG99].

Here, a satisfactory strategy is a decision-making strategy that attempts to meet an acceptability threshold. This is contrasted with optimal decision-making or best response strategy, an approach that specifically attempts to find the best option available given the choice of the other clients. Following that idea we define a satisfaction solution as a situation where every client is satisfied, i.e., its payoff is above its satisfactory level.

For each client j, we introduce a satisfaction level s * j . The collection G s (N , (A, s j , s * j ) j∈N ) constitutes a one-shot game in satisfaction form.

Definition 5 (Demand Profile). The demand profile (a j ) j∈N is a pure satisfactory solution of the cloud resource sharing game if all the clients are satisfied:

s j (a) = cna α j n i=1 a α i ≥ s * j , ∀j ∈ N .
The above inequality implies that the satisfaction s j (a) represents a fraction of the total capacity allocated to client j which should be greater or equal to s * j .

Equilibrium Analysis

In order to study the cloud in a dynamic and constantly changing setting, we examine the stability concept in a finite game G n . We first start by characterizing the Nash equilibrium and then we compare their equilibrium/strategy to the finite evolutionary stable strategy (F-ESS). We will see that Nash and F-ESS have two different equilibria (see proposition 2). Which means that Nash equilibrium is not stable.

We then consider another strategy called finite myopic mean-field response (F-MFR) and show that this strategy is stable under the system model considered in this chapter. In the last part of this section, we develop a distributed iterative algorithm that can converge to each of these three equilibria studied in this section.

Equilibrium for G s finite number of clients

Before defining Nash equilibrium, we introduce the so-called reaction set or best response correspondence. The best response problem (BR j ) of player j is

(BR j ) : Given a -j (a 1 , . . . , a j-1 , a j+1 , . . . , a n ), Find a j ∈ arg max a ′ j r j (a ′ j , a -j )
Which is the best response of client j given the demand of the others.

An interior solution to the problem (BR j ) (whenever it exists) is obtained by setting the first order condition (FOC) to zero and the second order derivative to be negative.

Note that the payoff is differentiable outside the origin and the first derivative with respect to a j yields

∂ a j r(a j , m n ) = c n n αa α-1 j m α n -a α j ( α n a α-1 j ) m 2α n -p n = c n αa α-1 j n m α n - a α j n m 2α n -p n .
and using the fact that m α n -

a α j n = i =j a α i n is independent of a j we get the second derivative ∂ 2 a 2 j r(a j , m n ) as c n α n (m α n - a α j n ) (α -1)a α-2 j m 2α n -a α-1 j 2α n a α-1 j m α n m 4α n = c n α n (m α n - a α j n ) a α-2 j m 3α n (α -1)m α n - 2α n a α j . (3.2)
Definition 6 (Symmetric Game). A game is symmetric if the action spaces are identical and the payoff functions are invariant by permutation of clients action and index.

The next Proposition provides closed-form expression of the Nash equilibrium for some range of parameter α. It also provides the optimal price p * n such that no resource is wasted in equilibrium.

Proposition 1. By direct computation, we have the following results:

(i) The resource sharing game is a symmetric game. All the clients have symmetric strategies in equilibrium whenever it exists.

(ii) For 0 ≤ α ≤ 1, the payoff r j is concave (outside the origin) with respect to own-action a j . The best response BR j (a -j ) is strictly positive and is given by the root of

x (α-1)/2 ( αc n np n G) 1/2 - x α n -G = 0, G 1 n i =j a α i
where x a j and there is a unique equilibrium (hence a symmetric one)

given by x α-1 αcn npn n-1

n x α 1 2 -x α n -n-1 n x α = 0, i.e., a * N E = α (n -1)c n n 2 p n .
It follows that the total demand na * N E at equilibrium is less than cn pn which means that some resources are wasted.

The equilibrium payoff is rn (a * N E ) = a j p n G+ a α j n
αG -1 which is positive for α ≤ 1.

(iii) For α > 1, the activity (participation) of player j depends mainly of the aggregate of the others. a * j > 0 only if G ≤ G * and the number of active clients should be less than α α-1 . If n > α α-1 then BR j = 0.

(iv) With a participation constraint, the payoff at equilibrium (whenever it exists) is at least 0.

(v) The game is a symmetric aggregative game in the sense of Dubey et al.

1980, [START_REF] Dubey | Efficiency properties of strategies market games: An axiomatic approach[END_REF].

(vi) By choosing the price p * n = α (n-1) n < α one gets that the total demand at equilibrium is exactly the available capacity of the cloud. Thus, pricing design can improve resource sharing efficiency in the cloud. Interestingly, as n goes to infinity, the optimal pricing converges to α.

(vii) The game is a submodular game with respect to own-action and the meanfield, i.e., it satisfies a decreasing-difference property: if a j > a ′ j , then the difference rn (a j , m n,-j )rn (a ′ j , m n,-j ) is decreasing with m n whenever nm α n > a α j .

We say that the cloud renting game is efficient if no resource is wasted, i.e., the equilibrium demand is exactly c n . Hence, the efficiency ratio is na * NE cn . As we can see from (ii) of Proposition 1, the efficiency ratio goes to 1 by setting the price to p * n . This type of efficiency loss is due to selfishness and have been widely used in the literature of mechanism design and auction theory. We refer the reader to [START_REF] Nisan | Algorithmic Game Theory[END_REF] for more recent applications.

Note that the equilibrium demand increases with α, decreases with the charged price and increases with the capacity per client.

The equilibrium payoff is positive and if α ≤ 1 each player will participate in an equilibrium.

Note that in case of Nash equilibrium the optimal pricing p * n depends on the number of active clients in the cloud and value of α. When the active number of clients varies (for example, due to new entry or exit in the cloud), a new price needs to be setup which is not convenient.

Finite evolutionary stable strategy (F-ESS)

The notion of evolutionary stable strategies (ESS) have been studied in the context of evolutionary games, starting from Volterra 1926 [Vol], Fisher 1931 [FB99], Hamilton 1967 [Ham67] and Maynard Smith & Price in 1973 [START_REF] Smith | The logic of animal conflict[END_REF].

The original definition was for infinite population in pairwise interaction model. However, the idea can be used for finite population as well. However, the notion of ESS in finite population is slightly different than the ESS notion for infinite population. The reason is that for finite population regime, each generic player has an influence in the mean-field which may result in a non-negligible effect on the relative payoff. We start with a simple (and weaker) notion of Finite evolutionary stable strategy (F-ESS) with one deviant.

Definition 7 (F-ESS). The pure strategy a * i ∀ i ∈ N is an F-ESS in the cloud game with finite number of players if r j (. . . , a * j , . . . , a k , . . . , ) ≥ r j (. . . , a j , . . . , a * k , . . . , ) for all a i ∈ A, and for all k = j.

This definition of F-ESS is based on the definition in [START_REF] Hamilton | Extraordinary sex ratios[END_REF]. This means that if one player k = j is adopting a different strategy than the F-ESS i.e.

a k = a * k , the best strategy for user j is to choose the F-ESS a j = a * j . The user j does not have interest to deviate from a * j . In other words, in a population of n -1 F-ESS players and 1 mutant player, we do not expect the mutant to do better than a typical F-ESS player [START_REF] Hamilton | Extraordinary sex ratios[END_REF]. Note that this definition of F-ESS does not necessarily imply (Nash) equilibrium condition. For a more detailed description of F-ESS strategies please refer to [START_REF] Schaffer | Evolutionarily stable strategies for a finite population and a variable contest size[END_REF].

Proposition 2. For α ≤ 1, the game G n has a F-ESS given by a * f -ess = α cn npn .

Remark 4. The F-ESS equilibrium a * f -ess from Proposition 2 is different from the a * N E from Proposition 1 (ii) which implies that a * N E is unstable.

Finite myopic mean-field response (F-MFR)

Here we will provide another strategy which coincides with F-ESS for our reward.

Note that this result is not general and is true only for our system model.

Since the cloud game G n has an aggregative structure m n , it is interesting to evaluate the performance of aggregate-taking clients. Each client sees the aggregate m n as signal (by ignoring its effect on the signal). A response to the aggregate of such game is called mean-field response. Since the reaction ignores the influence of own-action a j in m n , such reaction is called myopic. This leads to an equilibrium concept, which we call, finite myopic mean-field response (F-MFR). It corresponds to a mean-field-taking strategy.

Definition 8 (F-MFR). Formally, a pure F-MFR is a strategy a * such that a * j ∈ arg max

a j ∈A c n n a j m * n α -p n a j , where m * n 1 n n i=1 (a * i ) α 1 α .
This is a fixed-point equation since m * n contains the action a * j .

Proposition 3. For α ≤ 1, the game G n has a F-MFR given by

a * f -mf r = αc n np n .
For α > 1 the game has no F-MFR due to inconsistency. Note that a F-MFR is not a Nash equilibrium of G n . In the asymptotic regime, a * f -mf r converges to a mean-field equilibrium.

Remark 5. The a * f -mf r and a * f -ess coincides for α ≤ 1. However, for α > 1 the two notions do not coincide.

Equilibrium for G ∞ infinite number of clients

In cloud networks as the number of nodes is very large it is useful to analyze the asymptotic case as it is able to provide simplification and structure to a game which would otherwise be difficult to find. In this section, we characterize the Nash equilibrium for the infinite client which is also referred to as the Wardrop equilibrium [START_REF] Wardrop | Wardrop of Some Theoretical Aspects of Road Traffic Research-Road Paper[END_REF], and show that it is a submodular Mean Field (MF) Game.

Then we also define an evoloutionary stable strategy (ESS) and show that our Nash equilibrium is ESS i.e. it is a stable equilibrium point even for small perturbations in client demand.

In this infinite game, the notion of F-ESS becomes the classical ESS in the sense of Maynard Smith & Price (1973, [START_REF] Smith | The logic of animal conflict[END_REF]) and the notion of F-MFR becomes a mean-field Nash equilibrium (see Definition 9). Definition 9 (Mean-field (Nash) equilibrium). m * is a pure mean-field (Nash) equilibrium if m * ∈ A, and m * is consistent and is a best response to itself: m * ∈ arg max a j r(a j , m * ) From the above analysis, we get Proposition 4. (i) The resource sharing game G ∞ is a symmetric game.

(ii) the game G ∞ is a submodular mean-field game, i.e., ∂ 2 a j m r ≤ 0 (at the interior). This means that the incentive to decrease the demand decreases with the level of the m of the mean-field.

(iii) For α < 1, m > 0 the best response to mean-field is br(m) = αc pm α 1 1-α and for α > 1 the best response is 0.

(iv) For α ≤ 1, there is a unique mean-field equilibrium (i.e. global solution) which is given by

m * = α c p ,
and the optimal pricing is p * = α.

(v) Thus, the Nash equilibrium a * N E from proposition 1 (ii) can be scaled to converge to the mean-field equilibrium m * as n grows.

We are now interested in the stability of the mean-field equilibrium. We adapt the notion of evolutionary stable strategy (ESS) introduced by Maynard Smith and Price (1973, [MP73]). The original definition of ESS was for pairwise interaction and bilinear payoffs, here we have a non-linear payoff function (nonlinear in x and non-linear in m).

Definition 10 (ESS). For α ∈ [0, 1], m * is an evolutionary stable strategy (ESS), if it cannot be invaded by a fraction of deviants i.e., for any m = m * there exists 1 > ǭm > 0 (which may depend on m) such that for any ǫ ∈ (0, ǭm )

one has r(m * , ǫm + (1 -ǫ)m * ) > r(m, ǫm + (1 -ǫ)m * ), m = m *
The parameter ǭm is called invasion barrier. Next, we show that the mean-field equilibrium is an ESS for α ∈ (0, 1). This means that in the asymptotic regime, the mean-field equilibrium cannot be invaded by a perturbation of deviant VM demands. Moreover, our proof shows that the fraction of deviant(s) can be arbitrary high (i.e. ǫ < 1), which gives a stronger ESS.

Proposition 5. Let α ∈ (0, 1). Then, the mean-field equilibrium m * = α c p is an evolutionary stable strategy when ǫ = 1. This is a useful result as it states that as long as the number of deviants is not 100% it is possible for the system to return to the m * .

Equilibrium for G s Demand Satisfaction

Before going for pure satisfactory solution seeking, we first need to ask if the problem is well-posed, i.e; the existence of a pure satisfactory solution i.e. the equilibrium. The feasibility of the satisfaction problem for a given s * j , j ∈ N , is the non-emptiness of the set {a = (a 1 , . . . , a n ) ∈ A n | s j (a) ≥ s * j , ∀j}. The non-emptiness is equivalent to say that there exists a vector (ǫ 1 , . . . , ǫ n ), ǫ j ≥ 0 such that there is a demand profile a that satisfies ∀j, s j (a) = s * j + ǫ j . Thus, a necessary condition for existence of a satisfactory solution is that such a vector s * + ǫ belongs to the set s (A n ) , i.e., the range of the vectorial function s(a) (s 1 (a), . . . , s n (a)). It is not difficult to see that this is also a sufficient condition. Proposition 6. Suppose that the satisfaction levels are such that n i=1 s * i < c n . Then, the game has a satisfactory solution and the allocation given by

a i = (s * i ) 1 α , satisfies s j (a) = c n s * i n j=1 s * j > s * i
The proof is obvious and has been omitted for brevity.

The condition n i=1 s * i < c n translates the fact that the total demand should not exceed the available capacity.

We have proposed a selection algorithm in Section 3.4. The goal of the fully distributed learning algorithm for satisfactory solutions detailed in Subsection 3.4.3, is to select the most efficient satisfactory solution. By most efficient we mean that each user gets exactly the required performance without any waste. Thus, our analysis covers not only the satisfactory solution algorithm but also the problem of selecting the most efficient satisfactory point.

Algorithms

In the above sections we were able to analyze the equilibria associated with various types of games. As these systems are inherently distributed it is not possible to solve the problem in a centralized fashion. So in this section we provide the iterative distributed algorithms to approach the equilibria described in the above section. These algorithms require limited information in feedback in order to converge to their respective equilibria.

Iterative Learning Algorithm in the Finite Regime

In this subsection we present an iterative learning algorithm which is able to converge to the respective equilibria of the above subsections. The reason for using such an algorithm is that in general, the best response function has a complicated structure (as one can see in section 3.3.1, the equilibrium is a solution of a system of non linear equations.) Therefore, the use of an iterative algorithm allows us to achieve the equilibrium with less computational complexity. In addition the purposed iterative algorithm in this chapter is distributed in the sense that each client updates its own action and sends it to the cloud.

We propose to use an Ishikawa algorithm (see [START_REF] Ishikawa | Fixed points by a new iteration method[END_REF] for details) which is represented by the equation as follows

a t+1 = f (a t )λ + a t (1 -λ) (3.3)
where λ > 0 is a step size λ ∈ [0, 1],

where f (.) is the best response br(.) of the Nash equilibrium. br(.) which is given below:

br(a j,t-1 , m n,t-1 ) = ( αc n np n (m n,t-1 - a j,t-1 n )) 1/2 -(m n,t-1 - a j,t-1 n ) + (3.4)
Note that if a * is a fixed-point of br i.e, br(a * ) = a * then br(a t )λ+a t (1-λ) = (3.5)

a * λ + a * (1 -λ) = a * .
To prove this we can follow the standard ODE technique described in [START_REF] Tembine | Distributed strategic learning for wireless engineers[END_REF].

(2) Stable point of the ODE: Second we prove that a * is a stable point of the ODE. To prove this we just need to verify that the Jacobian J of the R.H.S of the equation (3.5) evaluated at a * be negative semidefinite i.e. its eigen values have negative real parts. We can show that the diagonal of J is -1 and the non diagonal elements are β = 2-n 2n(n-1) . Hence ∀ y ∈ R, y T Jy = -(1 + β)( j y j ) 2β( j y) 2 j ≤ 0, for n > 2, (where n is the number of players) which implies that J is negative semidefinite which concludes the proof.

For more details please refer to [START_REF] Hanif | Cloud networking mean field games[END_REF] where we have presented a similar analysis for in more detail for a similar reward function.

Notice that for a fixed step size (sufficiently small), the Ishikawa algorithm (Equation(3.3)) converges in general for a pseudo contraction mapping [START_REF] Tembine | Distributed strategic learning for wireless engineers[END_REF].

We define the convergence time for a fixed step size (sufficiently small) within a certain η-neighborhood of a * as the first time the trajectory of the algorithm a t enters a range within a distance less than η from a * : T η = inf{t > 0 | a ta * ∞ ≤ η}. The convergence time for η sufficiently small enough, is in order log( 1 η ) [START_REF] Tembine | Distributed strategic learning for wireless engineers[END_REF].

An important requirement for the implementation of the Newton method is the availability of the derivative of the best response which might not be available for some non differentiable functions. Therefore derivative free techniques are used in general.

An example of the derivative free techniques is the so-called secant method given by (1.6 * ) m t+1 = m t -g(mt)(mt-m t-1 ) g(mt)-g(m t-1 ) , m 0 fixed. which has the form m t = F (m t-1 , m t-2 ), i.e., a two-step memory scheme. The secant method is known to have a convergence order of o = 1.6 (hence, the name of the system (1.6*)). The drawback here is that although this method is derivative free, it is slower than the Newton method in terms of convergence order.

A faster method than the secant method is called the Steffensen method in (2 * ) which has a second order convergence with only two evaluations per time slot. Interested readers are referred to [START_REF] Dahlquist | Numerical Methods[END_REF] for more details.

(2 * )

m t+1 = m t - g 2 (mt)
g(mt+g(mt))-g(mt) , m 0 fixed.

In this chapter we go one step further and construct a faster convergence order of o = 4. For that we introduce the following notation: ∆g[a, a ′ ] g(a)-g(a ′ ) a-a ′ , a = a ′ and b t m t + g(m t ). The function g(.) will be evaluated at points: m t , ȳt and b t , where ȳt is the analogue of the secant point given above. Let ν(s) = α 0 + α 1 (sm t ) + α 2 (sm t ) 2 be a polynomial of degree 2 with coefficients α 0 , α 1 , α 2 . We want that ν(s) approximates the Taylor expansion of function g(.) till order 2. To achieve that, it is sufficient to determine the coefficients α 0 , α 1 , α 2 using the following requirement: ν(m t ) g(m t ), ν(ȳ t ) = g(ȳ t ) and ν(b t ) = g(b t ) (for more details one can refer to [START_REF] Dahlquist | Numerical Methods[END_REF]). From these relations, we deduce the coefficients

• α 0 = g(m t )
• α 1 = ȳt∆g[bt,mt]+mt∆g[ȳt,mt]-mt∆g[bt,mt]-bt∆g [ȳt,mt] ȳt-bt

• α 2 = ∆g[bt,mt]-∆g [ȳt,mt] bt-ȳt

Note that the derivative of ν at the point m t is exactly the coefficient α 1 . In other words, α 1 approximates the derivative of g(.) at point m t (since ν is a

Taylor approximation of g(.)). Now, if we consider the Newton update method and replace the derivative of g(.) by coefficient α 1 (α 1 can be seen as a plausible derivative-free term of g(.)), we obtain our derivative-free update algorithm given as follows, (4 * )

                 m t+1 = ȳt - (1+wt)(ȳt-bt)g(ȳt) ((ȳt-mt)∆g[bt,mt]-(bt-mt)∆g[ȳt,mt])
where ȳt is the secant point ȳt m t -g (mt) ∆g[bt,mt]) , w t 2 g(ȳt) g(bt)

Properties 1. The proposed speedup scheme (4*)

• is a derivative-free scheme,

• has three evaluations of the function g(.) per time-slot.

• is memoryless

• is faster than the secant speedup method (superlinear order),

• is faster than Steffensen's speedup learning method (quadratic order).

Proposition 8. Assume that g(.) has a simple zero in A. Locally, the scheme (4*) has a convergence order equal to four.

Definition 13 (Convergence time). The convergence time to be within an η-neighborhood of m * is the first time the trajectory enters into this neighborhood, i.e.,

T η,ǫ 0 inf{t > 0 | |m t -m * | ≤ η, |m 0 -m * | = ǫ 0 } Proposition 9. The convergence time is T η,ǫ 0 = 1 + ⌊max(0, T )⌋ where T = 1 ln(4) ln       ln 1 ηc 1 3 1 ln 1 ǫ 0 c 1 3 1       which is in order of O log(log( 1 η )) .
Where c 1 is a positive constant as represented in definition 12 and whose value is given in the proof of Proposition 8. The result of Proposition 9 is very important since strictly contraction mapping fixed-point algorithm exhibits a convergence time in order of O(log( 1 η )). Notice that the convergence time of Ishikawa algorithm in finite case is log( 1 η ) [START_REF] Tembine | Distributed strategic learning for wireless engineers[END_REF]. Here we have a bound in order of log(log( 1 η )) which is a great improvement.

Iterative Learning Algorithm for satisfactory solution

We propose a fully distributed learning algorithm for satisfactory solutions. The only information assumption required to each client is the numerical realized value of its satisfaction s j,t and its own-satisfaction level s * j . We propose to use the following fixed-point iteration given by

a j,t+1 = proj A a j,t s * j s j,t , (3.7)
where proj A (x) = min(c n , max(0, x)). proj A is the projection operator over the nonempty and convex set A. The above is Banach Picard algorithm and (see [START_REF] Willard | General topology[END_REF] for details) and it converges to the equilibrium characterized in Proposition 6.

sketch of proof for convergence: . The algorithm (3.7) is fully distributed in the sense that a client does not need to observe the actions of the others in order to update its strategy iteratively. The righthand side of (3.7) is denoted by f j . The function f j is well-defined whenever the ratio a j s j s * j = s * j cn a 1-α j ( n i=1 a α i ) has a limit when a j -→ 0 if α ≤ 1. Due to space limit, we omit the proof that the function in (3.7) is a fixed point equation (for more details see [START_REF] Dahlquist | Numerical Methods[END_REF]). The set of fixedpoint of f is denoted by f ix(f ) is contained in the set of satisfactory solution.

It is clear that if the algorithm converges to some interior point a * then a * is a satisfactory solution. To prove this statement, consider a converging sequence to a * . Combining the continuity of the projection map and the continuity of the payoff function, one gets the continuity of proj A a j s * j s j . Taking the limit as t goes to infinity yields a j = proj A a j s * j s j , i.e., the payoff of client j is s j = s j (a * ) = s * j which means that every satisfied client j is in interior steady state.

For the infinite case as n → +∞ with satisfactory level s * , the algorithm simplifies to m t+1 = s * c m t + s * c ǫm 1-α t where ǫ > 0 is very small, which converges to an interior fixed-point.

Numerical Investigation

For the numerical investigation we fix α = 1.

Finite user scenario

In the finite case we numerically show that Nash equilibrium in unstable in the sense that it is different from the ESS equilibrium. For that, we compare the performance of the Nash equilibrium and the ESS equilibrium. to their horizontal red lines, which shows that Nash equilibrium is different from ESS and hence Nash equilibrium is not a stable point in the finite case.

We then examine the case when different clients are using different strategies.

Figure 3.2 shows the scenario where 1 client is using the ESS strategy and n -1 clients are using the Nash strategy (where the number of clients n = 10). This figure shows that ESS dominates Nash in the sense that ESS client represented by the solid green line gets a higher reward than the other n -1 clients and also has a higher demand, while the case when all clients are implementing Nash strategy are represented by the solid blue lines for reference. It is clear from the plots that the performance of users in interactive Nash equilibrium strategy which is represented by dotted blue line as indicated in the legend is even lower than the solid blue line which represents the pure nash when all users are using the same Nash strategy. It should be noted that as we have the same price for all users we only see 3 lines as all the other users have the same demand and the same reward which would result in the same equilibrium.

Infinite user scenario

Next we numerically illustrate that in the infinite case i.e. for large number of clients Nash and ESS equilibria converge to the same point. Here we extend the case of from Figure 3.2 to n = 1000 and present in Figure 3.3 the evolution of the client demand a j (top) and client reward r j (bottom). Note that the capacity c n = 100000 and the price is p n = 11 for all clients. It can be clearly seen that the trajectories of Nash and ESS equilibria converge to the same point which means that Nash equilibrium is stable for large number of users i.e. the mean field case. It should be noted that as we have the same price we only plot one user of each type for clarity.

Heterogeneous pricing scenario

In this section we numerically extend the analysis to the case of different pricing (i.e. heterogeneous pricing scenario) and show that our framework works with different price scenarios. We have included some numerical results to corroborate our claim. Notice that these results are obtained by considering a modified reward function where a different price per user is used, then we find the bestresponse function for this case and we feed these new best responses in the Ishikawa based algorithm.

In Figure 3.5 we presents the plot for the evolution of the demand a j (top)

and the reward r j (bottom) for different prices in the finite case with n = 4.

Conclusion and Future Work

Future networks will have to handle higher data rate, offer lower latency and efficient spectrum and bandwidth utilization in an energy efficient manner. This will required a paradigm shift in the fundamental architecture of the network, which will make individual nodes more independent, intelligent, and able to make decisions about how, when and where to communicate. This distributed network architecture poses several design challenges. In this thesis we have tried to address a subset of those challenges such that it could be possible to make intelligent decisions based on the limited information and still able to converge to a local maximum equilibrium point.

Extremum Seeking

In this section we summarize our extremum seeking framework with contributions and their implications. We consider a distributed systems scenario with stochastic state dependent reward function, which needs to satisfy Lipschitz continuity condition. Each node has a numerical value of the reward available in feedback at each time slot. We have extended the classical Nash Seeking with sinus perturbation method [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF] to the case of discrete time and stochastic state-dependent payoff functions. Our contribution is the development of a deterministic perturbation algorithm which is able to converge locally to a state independent Nash equilibrium according to Theorem 1 in Chapter 2 for vanishing step size and provide an error bound according to Theorem 2 in Chapter 2 for fixed step size. We also provide the convergence time for the extremum seeking algorithm according to Corollary 1 in Chapter 2. The error bound for the algorithm and the convergence time to be in a close neighborhood of the Nash equilibrium.. Algorithm: For 'model free' scenarios (i.e. when the model of the reward function is not known by all the nodes) we have developed a stable extremum seeking algorithm that is able to converge to the Nash equilibrium when initialized in the neighborhood of the Nash equilibrium point. Our proposed discrete time learning algorithm uses sinus perturbation, for continuous action games where each node has only a numerical realization of own-payoff at each time.

This extremum seeking algorithm is able to find the local minima using just the numerical value of the stochastic state dependent payoff function at each discrete time sample. Note that since the payoff function may not necessarily be concave, finding a global optimum in reasonable time can be difficult in general even in deterministic case (fixed state) and known closed-form expression of payoff. The algorithm ensures tractability which can be a requirement in certain engineering applications.

Following is a list of the three distributed wireless system scenarios that we have considered. Numerical results for each of these cases was also provided for illustration.

• Distributed power control in femto cells using bayesian density tracking.

• Distributed transmit beamforming with 1-bit feedback for LoS-MISO channels.

• Distributed stochastic learning for continuous power control in wireless networks.

For certain applications where the reward function may not satisfy the Lipschitz continuity condition, we may still be able to use our extremum seeking algorithm, but may not mathematically be able to proved or ensure the convergence or stability. This may not be acceptable in some mission critical applications, and may be acceptable in others.

Resource Sharing Games in Cloud Networks

In this section we summarize our Resource Sharing Framework with contributions and their implications.

Resource Sharing Problem: For resource sharing in cloud networks with finite number of user, each users has a specific reward which needs to be maximized.

For our specific type of resource sharing reward function, we have proved that Nash equilibrium point is unstable for our reward function and have identified two stable strategies namely finite evolutionary stable strategy (F-ESS) and finite myopic mean field response (F-MFR). We extend this to the asymptotic case, i.e. when the number of users approaches infinity, then the Nash equilibrium point becomes evolutionary stable, which means that it cannot be dominated or invaded by another competing strategy.

Satisfaction Problem: We consider another type of resource utilization problem where each users has a minimum demand which need to be satisfied. These type of models, more accurately capture the requirements of the users, where the maximum requirement of the users is known. We provide necessary and sufficient conditions for the existence of satisfactory solution where each user is satisfied anywhere anytime.

Algorithms and Numerical Results:

We provide an algorithms which are able to respectively converge to the equilibria mention above. We develop a faster iterative distributed algorithm that converges to the mean-field equilibrium with a convergence order of four. We also develop a distributed iterative algorithm for large scale systems using Mean Field theory and apply them to finite scale systems. In large scale systems for the same price we were able to show that the reward for a social users in better than reward for a selfish user.

The resource sharing problem is a general problem that arises in various application domains. We are able to derive fundamental results which scale to large scale systems. We have studied resource sharing games in cloud networks, however our analysis is applicable to other resources sharing scenarios as well.

The reward function considered here has a very specific structure which is based on the percentage of resources available to each node. There may be scenarios where the percentage of resources can be re-interpreted as the access probability for random access scenarios.

Future Work

The future work could focus on

• the extension of the extremum seeking framework to non-Lipschitz continu-ous reward functions, as Lipschitz continuity is not a very easy condition to satisfy in most engineering applications. This extension if possible would enable our framework to be applicable to a wider range of engineering problems.

• Additionally the extremum seeking framework could be extended to the case of vectors of action, where each users is able to perform multiple actions based on multiple rewards. This type of extension could be very useful in systems where there are multiple inputs to a system.

• So far all of the results achieved are for the local stability, it would be interesting to extend the analysis to global stability condition for Nash equilibrium for both deterministic and stochastic payoff functions.

• the resource sharing framework in cloud networks could be extended to dynamic pricing where the pricing function depends on the user's demand. This type of dynamic pricing reward would be more flexible in dealing with dynamic demand of the users and will be able to incentivise the uniform distribution of the demand thus discouraging peak load outages.

• r j (S, a), ∇ a r j (S, a) are absolutely integrable in S and E S r j (S, a) is continuous in a. where γ is the measure of S state space. For more details on the above conditions please refer to [START_REF] Schwartz | Functional analysis[END_REF].

Since f j (.) is a function of time and the actions of nodes, we need a uniform Lipschitz condition on f j (.).

We have

|f j (t, a) -f j (t, a ′ )| ≤ b j z j | sin(Ω j t + φ)| E S r j (S, a) -E S r j (S, a ′ ) But one has | sin(.)| ≤ 1. Hence, |f j (t, a) -f j (t, a ′ )| ≤ b j z j E S r j (S, a) -E S r j (S, a ′ )
by using Lemma 1 we get,

|f j (t, a) -f j (t, a ′ )| ≤ b j z j L j a -a ′
This implies that the Lipschitz constant of f j is less than the one of r j times the factor b j z j .

Finally, we check the noise conditions. The recursion equation is given by

a j,k+1 = a j,k + λ k [f j (k, a k ) + M j,k+1 ]
where M j,k+1 is a martingale difference sequence. By definition the martingale sequence for the algorithm is given as

M j,k+1 := z j b j sin(Ω j t k + φ j )[r j,k+1 -E S [r j,k+1 (S, a k+1 )]] which satisfied the condition E[M k+1 |F k ] = 0 for k ≥ 0 almost surely (a.s.) Lemma 2. If a k ∈ A then the martingale is square-integrable with E[ M k+1 2 |F k ] ≤ ć(1 + a k 2 ) ∀k
Taking E S over the above inequalities we get:

E S M j,k+1 2 ≤ 4z 2 b 2 (E S β 2 1,S + β 2 2 + (E S L 2 j,S + L 2 j ) a k 2 ) ≤ 4z 2 b 2 (β + Ĺj a k 2 ) ≤ ć(1 + a k 2 ) Where Ĺj := E S L 2 j,S + L 2 j , β := E S β 2 1,S + β 2 2 and 4z 2 b 2 (β + Ĺj ) ≤ ć
This completes the proof.

We now combine the above three steps to derive almost sure convergence to an ODE. To do so, we interpolate the stochastic process a k (an affine interpolation) in order to get a continuous time process following the lines of Borkar [START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF] Chapter 2 Lemma 1 for the case of non-autonomous system. The solution of the non-autonomous differential equation

d dt a t = f (t, a t ) is a * t .
The gap between the a * t and interpolated process is given by lim

t k -→∞ sup t∈[t k ,t k +T ]
āta * t = 0 a.s.

i.e. it vanishes almost surely (a.s.) for asymptotic interval of length T > 0 In order to calculate the bound we need to define a few terms which are helpful in obtaining a compact form of the bound.

sup

t∈[t k ,t k +T ] āt -a t k t ≤ K T,k e LT + C T sup ḱ≥0 λ k+ ḱ = C T (λ k+ ḱ + L ḱ≥0 λ 2 k+ ḱ) + sup ḱ≥0 δ k,k+ ḱ where K T,k := C T L ḱ≥0 λ 2 k+ ḱ + sup ḱ≥0 δ k,k+ ḱ δ k,k+ ḱ := ξ k+ ḱ -ξ k ξ k := k-1 ḱ=0 λ ḱM ḱ+1 C T := r 0 + L(C 0 + r 0 T )e LT < ∞ L := max j∈N E S [L j,S ] r k := [r 1,k , . . . , r N,k ] P sup ḱ a ḱ < C 0 = 1
The above bound is derived following the steps of the proof of Lemma 1 in chapter 2 of [START_REF] Borkar | Stochastic Approximation: A Dynamical Systems Viewpoint[END_REF]. From the above bound we can conclude that lim

t k -→∞ sup t∈[t k ,t k +T ]
āta * t = 0 a.s.

A.2 Fixed

Step Size: Proof of Theorem 2

Theorem 2 states that under Assumption A2, the learning algorithm converges in distribution to the trajectory of a non-autonomous system given by d dt âj,t = z j b j sin(Ω j t + φ j )E S (r j (S, a t )) a j,t = âj,t + b j sin(Ω j t + φ j )

Proposition 1. Let āt be the interpolated version the trajectory of our algorithm at time t and ât is the trajectory of the the ODE at time t. Under assumption A2 āt converges to ât as step size λ vanishes i.e. λ -→ 0.

E sup t∈[0,T ] [ āt -ât 2 ] 1 2 = CT √ λ
Proposition 1 implies Theorem 2.

Proof of Proposition 1. To prove the above proposition we start with a fixed step size λ > 0.

• Time Scale. tk := k ḱ=1 λ = kλ, for k ≥ 0

• The cumulative noise at iteration k is ξ k = k-1 ḱ=0 λM ḱ+1 = λ k-1 ḱ=0 M ḱ+1

• Define the (affine) interpolated process from {â ḱ} ḱ≥0 rewritten as âj,k+1 = âj,k + λ(f j (k, âk ) + M k+1 ).

The advantage of the interpolated process is that it is defined for any continuous time by concatenation. The affine interpolation writes āt := âk + ( t-tk λ )(â k+1âk ) if t ∈ [kλ, (k + 1)λ[ which is now in continuous time.

Note that constant learning rate or constant step size λ k = λ is suitable for many practical scenarios. It is used for example in numerical analysis: Euler's Scheme (1st Order), Runge Kutta's scheme (4th Order), etc. Our algorithm writes ( * * ) âj,k+1 = âj,k + λb j z j sin( tk Ω j + φ j )r j,k+1 a j,k = âj,k + b j sin( tk Ω j + φ j )

where λ is a constant learning rate, our aim is to analyze ( * * ) asymptotically when λ is very small. In order to prove an asymptotic pseudo-trajectory result for constant learning rate, we need additional assumptions for the sequence generated by the powers. The key additional assumption is the uniform integrability of that process. We need the conditions C 1 C 2 , which translate into Now we use Burkholder's inequality which states the following: For an α > 0 there exists two constants c 1 > 0 and c 2 > 0 such that

-
c 1 E[ k ḱ=1 âḱ -âḱ -1 2 ] α/2 ≤ E[sup ḱ≤k âḱ ] α ≤ c 2 E[ k ḱ=1 âḱ -âḱ -1 2 ] α/2
A direct application to the process η k := λ ḱ≤k M ḱ 2 gives

c 1 E[ k ḱ=1 η ḱ -η ḱ-1 2 ] α/2 ≤ E[sup ḱ≤k η ḱ ] α ≤ c 2 E[ k ḱ=1 η ḱ -η ḱ-1 2 ] α/2
We consider the inequality of η k and we use discrete Gronwall inequality which states that if This completes the proof.

ǫ k+1 ≤ C + L

A.3 Stability analysis, Proof of Theorem 3

The proof of theorem 3 follows the steps in [START_REF] Frihauf | Nash equilibrium seeking in noncooperative games. Automatic Control[END_REF]. The main steps are provided here.

We denote the error relative to the Nash equilibrium as ãj,t = âj,tµ j (t)a * From general averaging theory (Khalil [2002], Fink [1947]) the system (A.5) retains the stability properties of the average system.

This completes the proof.

A.4 Conditions for Example A

Following are some details about how to obtain a * for our application.

g ij := |h ij | 2 ḡij := E g g ij = E g |h ij | 2
From remark 7 we can write E G ∂γ j (G,a * ) ∂a j = ∂ ∂a j E G γ j (G, a * ) = 0. Solving N equations we have the following matrix form. Ḡ should be invertible and all the elements in the vector ā should be strictly positive as they are a linear combination of power and gains which are positive.

We can also write ωḡ jj > λσ 2 . For this example we can write

E G [g jj ] > j ′ =j E G [g jj ′ ] ∀j, j ′ = j
If this condition is satisfied then Ḡ is invertible.

As G is a matrix of random channel gains it is almost surely invertible. To

show the invertibility of this matrix we just need to show that the det( Ḡ) = 0.

The set of invertible matrices G where G ∈ G.

Appendix B

Proofs in Mean Field Resource

Sharing

Proof of Proposition 1:. The proof is in several steps:

(i) The payoff function r j of the cloud game (given in Equation (3.1)) is obtained by permutation of index of the players and the actions. Moreover, the action space is common. Hence, the game is symmetric.

There is no asymmetric interior equilibrium. Since the game is reduced to a subgame between the active players only, all the players will use symmetric strategies in equilibrium.

(ii) A direct computation of the first order and second order derivatives of r j

shows that α ∈ [0, 1] is a sufficient condition for the concavity of the payoff with respect to own-action, i.e., x j -→ r j (x j , x -j ) is concave. With the participation constraint, we need to examine only the possible interior equilibria. Since it is an open set, the derivative should vanish. This means that

x (α-1)/2 ( αc n np n G) 1/2 - x α n -G = 0, G 1 n i =j a α i
and the unique symmetric interior equilibrium candidate is a * N E = α n-1 n cn n pn . Note that the equilibrium demand increases with α, decreases with the charged price and increases with the capacity per user. The equilibrium payoff is positive and if α ≤ 1 each player will participate in equilibrium.

(iii) Using the equilibrium payoff at the equilibrium candidate from (ii), one gets that G + a α j n > αG which means that the aggregative term from the other players should not exceed a certain quantity G * and α < 1 + 1 n-1 , It trivially limits the number of users to be n < α α-1 .

(iv) Nonparticipation into the game will result to zero-payoff. Thus, the equilibrium payoff is positive or zero by dominance.

(v) The game is an aggregative game. A simple of aggregative games is the one in which the payoff function can be written into the following form : rj (a j , φ(a)), where φ is the aggregative term. Our game belongs to that class with the aggregative term being m n .

(vi) The total demand in equilibrium is α (n-1)cn npn . Thus, by designing the price p n to be p * n = α n-1 n the equilibrium demand is to total available resource c n , i.e., no resource is wasted in equilibrium. The optimal price p * n -→ α as n grows.

(vii) A direct differentiation at the interior of the domain shows that ∂ 2 a j Gr j ≤ 0 whenever G > a α j where G = i a α i . This completes the proof of Proposition 1.

Proof of Proposition 2:. The relative payoff is Proof of Proposition 4:. (i) The first item statement can be proved following similar lines as above.

(ii) the cross derivative ∂ 2 a j m r is given by -α 2 ca α-1 j m -α-1 ≤ 0. Hence the game is submodular.

(iii) the best response to mean-field is obtained by direct computation. where d (j) is a jth order differential operator.

We claim that ǫ t+1 can be expressed as

ǫ t+1 = c 2 ǫ 4 t + O(ǫ 5 t )
where c 2 (1+q 1 )q 2 [(5+3q 1 )q 2 2 -q 1 (1+q 1 )q 3 ] q 3 1 This means that locally, the scheme (4*) has fourth-order convergence rate (see Definition 12). Note that using the notation from Definition 12, we have and ∆g[ȳ t , m t ] = g(ȳt)-g(mt)

g(mt)

.

We use the relation g(m t ) = 4 l=1 q l ǫ l t + O(ǫ 5 t ) (i.e. a Taylor expansion of g(m t ) around m * till order 4). Using Taylor expansion of g(b t ) and g(ȳ t ) and after several algebraic manipulations we get g(b t ) = g(m t + g(m t )) = 0 + (ǫ t + g(m t ))q 1 + q 2 (ǫ t + g(m t )) 2 +q 3 (ǫ t + g(m t )) 3 + c 4 (ǫ t + g(m t )) 4 + O(.) (B.10) g(ȳ t ) = q 2 (1 + q 1 )ǫ 2 t + 1 q 1 [q 1 (1 + q 1 )(2 + q 1 )q 3 -q 2 1 q 2 2 -2q 1 q 2 2 -2q 2 2 ǫ 3 t + ǫ 4 t q 2 1 (q 3 1 + 4q 2 1 + 7q 1 + 5)q 3 2 -q 1 q 2 q 3 (2q 3 1 + 7q 2 1 + 10q 1 + 7) +q 2 1 q 4 (1 + q 1 )(q 2 1 + 3q 1 + 3) + O(ǫ 5 t ) (B.11) Finally, plugging in the values of g(ȳ t ), g(m t ) and g(b t ) back in equation (B.7)

and after doing simplification we get ǫ t+1 = (1 + q 1 )q 2 [(5 + 3q 1 )q 2 2q 1 (1 + q 1 )q 3 ] q 3 1 ǫ 4 t + O(ǫ 5 t ).

The above equation proves the claim and implies order four convergence.

This completes the proof. We remember that for q = 1, 1 + q + . . . + q t-1 = q t -1 q-1 . Thus,

η t ≤ c 4 t -1 3 1 η 4 t 0 .
This means that the convergence time to be within an η-neighborhood of the mean-field equilibrium is at most for t satisfying c Proof of Proposition 6:. By assumption, the satisfaction levels s * i are such that the condition i=1 s * i < c n is met. then we compute s i (a).

Finally

  , I would like to thank my family, especially my beloved wife Kiran, for her continued support during my PhD. Ahmed Farhan Hanif, May 2014.

  devraient être choisis assez faibles. Par exemple, λ k = 1 k+1 . φ i ∈ [0, 2π]∀ i, k ∈ Z Chaque utilisateur i, initialiser âi,0 et transmettre Répétez Calcul puissance selon l'équation (2.31) Observer r i,k mise à jour âi,k+1 en utilisant l'équation 3 jusqu'à horizon T Algorithm 1: algorithme d'apprentissage distribué

FAP

  Nous avons étudié les jeux de partage des ressources dans les réseaux de cloud computing, mais notre analyse est applicable à d'autres scénarios de partage des ressources. Pour le cas fini, nous avons prouvé que le point d'équilibre Nash est instable pour notre fonction de paiement et avons identifié deux stratégies stables à savoir F -ESS et F -MFR. Nous avons aussi développé des algorithmes qui sont capables de converger respectivement aux stratégies mentionnées dans la section précédente. Pour les systèmes à grande échelle, nous avons développé un schéma de jeu de champ moyen et montré que l'équilibre du champ moyen est stable. Nous développons ensuite un algorithme itératif distribué qui converge vers l'équilibre du champ moyen avec un ordre de convergence de quatre. En outre, nous avons donné des conditions nécessaires et suffisantes pour l'existence de solution satisfaisante où chaque utilisateur est satisfait n'importe xiv où n'importe quand. Pour plus de détails sur les contributions ci-dessus et les résultats numériques veuillez vous référer à[START_REF] Hanif | Mean-field games for resource sharing in cloud based networks[END_REF][START_REF] Hanif | Cloud networking mean field games[END_REF]. Contents 1 Introduction 1.1 Motivation and Challenges . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Wireless Resource Utilization . . . . . . . . . . . . . . . . 1.1.2 Cloud Networks Resource Sharing . . . . . . . . . . . . . 1.2 Outline and Contributions . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Extremum Seeking Algorithm . . . . . . . . . . . . . . . . 1.2.2 Distributed Resource Sharing . . . . . . . . . . . . . . . . 1.2.3 Publication List . . . . . . . . . . . . . . . . . . . . . . . 2 Model Free Nash Seeking 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Problem Formulation and Proposed Algorithm . . . . . . . . . . 2.2.1 Distributed learning algorithm . . . . . . . . . . . . . . . 2.2.2 Interpretation of the proposed algorithm . . . . . . . . . . 2.3 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Numerical Example A: Wireless Interference . . . . . . . . . . . . 2.5 Numerical Example B: Distributed Beamforming . . . . . . . . . 2.6 Numerical Example C: Nash Bayesian Estimation . . . . . . . . 3 Resource Sharing in Cloud Networks 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Resource sharing game G n with finite number of clients . 3.2.2 Resource sharing game G ∞ with infinite number of clients xv CONTENTS xvi 3.2.3 Demand satisfaction game G s . . . . . . . . . . . . . . . . 3.3 Equilibrium Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Equilibrium for G s finite number of clients . . . . . . . . . 3.3.2 Equilibrium for G ∞ infinite number of clients . . . . . . . . 3.3.3 Equilibrium for G s Demand Satisfaction . . . . . . . . . . 3.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Iterative Learning Algorithm in the Finite Regime . . . . 3.4.2 Iterative Learning Algorithm in the Infinite Regime . . . 3.4.3 Iterative Learning Algorithm for satisfactory solution . . 3.5 Numerical Investigation . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Finite user scenario . . . . . . . . . . . . . . . . . . . . . 3.5.2 Infinite user scenario . . . . . . . . . . . . . . . . . . . . . 3.5.3 Heterogeneous pricing scenario . . . . . . . . . . . . . . . 4 Conclusion and Future Work 4.1 Extremum Seeking . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Resource Sharing Games in Cloud Networks . . . . . . . . . . . . 4.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Proof of convergence in Extremum Seeking A.1 Variable Step Size: Proof of Theorem 1 . . . . . . . . . . . . . . A.2 Fixed Step Size: Proof of Theorem 2 . . . . . . . . . . . . . . . . A.3 Stability analysis, Proof of Theorem 3 . . . . . . . . . . . . . . . A.4 Conditions for Example A . . . . . . . . . . . . . . . . . . . . . . B Proofs in Mean Field Resource Sharing Acronyms a.s. almost sure CDMA code division multiple access CMP Chip Microprocessor discrete ODE the learning algorithm DoT direction of transmission F -ESS stratégies évolutives stables à population finie F -MFR réponse de champ moyen à population finie F-ESS finite evolutionary stable strategy F-MFR last level cache equation OFDMA orthogonal frequency division multiple access PaaS Platform as a Service QoS quality of service RaaS Resource-as-a-Service SaaS Software as a Service SINR signal to interference and noise ratio SISO single input single output SLA services level agreement ULA uniform linear array VM virtual machine XaaS anything as a service CONTENTS xix Definition 1 Nash Equilibrium (state-independent) . . . . . . . . . . . Definition 2 Nash Equilibrium (state-dependent) . . . . . . . . . . . . Definition 3 ǫ-Nash equilibrium payoff point . . . . . . . . . . . . . . Definition 4 ǫ-close strategy Nash equilibrium point . . . . . . . . . . Definition 5 Demand Profile . . . . . . . . . . . . . . . . . . . . . . . . Definition 6 Symmetric Game . . . . . . . . . . . . . . . . . . . . . . . Definition 7 F-ESS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Definition 8 F-MFR . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1

Figure 2 . 1 :

 21 Figure 2.1: Nodes interacting with each other through a dynamic environment

[

  NMM13] a framework for extremum seeking control of systems with parameter uncertainties is considered. A time-varying extremum-seeking control approach is presented in[START_REF] Guay | A time-varying extremumseeking control approach[END_REF]. Examples of distance-based synchronization: An extremum seeking approach is presented in[START_REF] Durr | Examples of distance-based synchronization: An extremum seeking approach[END_REF]. In[START_REF] Poveda | Distributed extremum seeking for realtime resource allocation[END_REF] a distributed extremum seeking for real-time resource allocation is presented. An extremumseeking control of ABS braking in road vehicles with lateral force improvement is presented in[START_REF] Dincmen | Extremum-seeking control of abs braking in road vehicles with lateral force improvement[END_REF].In[START_REF] Liu | Stochastic averaging in continuous time and its applications to extremum seeking[END_REF] Krstic et al. have recently extended Nash seeking scheme to stochastic non-sinusoidal perturbations and convergence in probability is proved.Interested readers can also refer to the references therein[START_REF] Liu | Stochastic averaging in continuous time and its applications to extremum seeking[END_REF] for other perturbation method. In[START_REF] Liu | Stochastic averaging in continuous time and its applications to extremum seeking[END_REF] stochastic averaging theory is developed for extremum seeking problems and several conditions on the payoff functions like global Lipschitz condition has been relaxed. Notions of weakly stable, weakly asymptotically stable and weakly exponentially stable are defined for extremum seeking. In[START_REF] Liu | Stochastic nash equilibrium seeking for games with general nonlinear payoffs[END_REF], building on the theoretical foundations in[START_REF] Liu | Stochastic averaging in continuous time and its applications to extremum seeking[END_REF], Krstic et al. present stochastic perturbations based Nash equilibrium seeking for games with non linear payoffs and they analyze necessary convergence conditions. Although these stochastic perturbation techniques do estimate the gradient but they introduce a level of uncertainty because of the stochastic perturbations. To

  Calculate action a j,k according to Equation (2.4) 4: Perform action a j,k 5: Observe rj,k 6: Update âj,k+1 using Equation (2.5) 7: until horizon T Algorithm 2: Distributed learning algorithm

  j)] represents an N × N matrix containing channel coefficients at time k, h k (i, j) represents the channel coefficient between transmitter i and receiver j (where (i, j) ∈ N 2 ) and p k represents the vector containing transmit powers of N transmit-receive nodes. The most common technique used to obtain a local maximum of the nodes' payoff functions is the gradient based descent or ascent method.

  Figure 2.3 represents the average transmit power trajectories of the algorithm for two nodes. The dotted line represents p * . As can be seen from the plots in Fig 2.3 that the system converges to p * where p * j = 3.9604, j ∈ {1, 2}. Fig 2.4 shows that the reward also approaches the optimal value.

Figure 2

 2 Figure 2.3: Power evolution (discrete time)

Figure 2

 2 Figure 2.4: Payoff evolution (discrete time)

Figure 2

 2 Figure 2.5: Stochastic Perturbation method

  We run our algorithm by taking the initial values of ψ 0 1 = -60 o , ψ 0 2 = 60 o which is the worst direction as it incurs strong interference on the receiver of the other network, and can cause outage. In Fig 2.7 we present the evolution of ψ j and show that the transmitters direct their beams away from each other's receives and towards their own receiver which means that ψ j -→ θ jj ∀j ∈ [1, 2] which is the Nash equilibrium point. Fig 2.7 shows that ψ j convergences to a neighborhood of Nash since the step size ǫ k used in the simulation is fixed (see Theorem 2).

Figure 2

 2 Figure 2.7: Evolution of ψ for AP 1 and AP 2

Figure 2

 2 Figure 2.8: Beam pattern for U 1 and U 2

  [XCA10], Ping et al. compare open and closed access FCs in the uplink. In [IDME12], Ibrahim et al. present an Adaptive interference mitigation techniques for femto cells. Various approaches for enhancing autonomous power control at Femto under co-channel deployment of Macrocell and Femtocell are presented in [YZ11]. In [HAT13] a robust distributed H ∞ based power control in a dynamic wireless network environment is presented by Hasssan. A location based autonomous power control for LTE-A heterogeneous network is presented in [YW11]. Hong et al. in [HYC09] present a decentralized power control scheme in FC networks based on game theory. A game theoretic approach for an interference control problem with sub band scheduling is presented in [Ran10]. In [BHN11], Bendlin et al. develop probabilistic power control for heterogeneous cellular networks with closed-access FCs. In [WCLP12], Wu et al. provide a downlink outage probability analysis for co-channel femtocells in hierarchical 3-sector macrocells. In most of the existing works, the SINR distribution function is obtained (and therefore the outage) using some assumptions such as infinite number of interferers, poisson point process mobility model, etc.

  Figure 2.10: Evolution of Probability of Macro and Femto Users

  For a symmetric game, the reward function r(m * , ǫm + (1ǫ)m * ) represents the reward of a user employing the ESS strategy m * while an ǫ fraction of players are adopting the strategy of m where m = m * and 1ǫ fraction of users are adopting the strategy m * which makes the effective mean field response to be ǫm + (1ǫ)m * i.e. a convex combination of m and m * where m = m * . Hence the meanfield term in this case is ǫm + (1ǫ)m * . The inequality between r(m * , ǫm + (1ǫ)m * ) and r(m, ǫm + (1ǫ)m * ) indicates that the reward of a player implementing m * is higher as long as ǫ is less than the invasion barrier ǭm . Definition 11 (Invasion barrier ǭm ). Invasion barrier ǭm is the maximum percentage of the clients which can deviate from m * such that the system still remains stable i.e. it is able to return to m * .

( 1 )

 1 Convergence to an ODE: First we show that for vanishing step size, our Ishikawa algorithm (Equation(3.3)) converges to the limiting Ordinary differential equation (ODE) give by ȧt = br(a t )a t .

  Figure 3.1 compares the evolution of the demand a j (top) and the reward r j (bottom) for c n = 1000, n = 10 clients with the same price p n = 11. The horizontal dotted red line shows the Nash equilibrium and the horizontal solid red line represents the ESS equilibrium. The dotted and solid blue lines correspondingly converge

FigureFigure 3

 3 Figure 3.2: ESS vs Nash n = 10 Interactive

  then E[∇ a r j (S, a)] = ∇ a E[r j (S, a)] which can be written as S ∇ a r j (S, a)γ(dS) = ∇ a S r j (S, a)γ(dS)

MλM

  From Remark 7: gradient of the expectation of payoff is bounded -From Lemma 2: Square of the martingale is bounded -Uniform Integrability of r j (S, a) and ât is the solution of ȧt = f (t, ât ) starting from â⌊ t λ ⌋ k+ ḱ+1 ) one gets āt k+T = T ḱ=1 ( tk+ ḱ -tk+ ḱ-1 )f (⌊ tk+ ḱ-1 k+ ḱ+1 + āt k , (A.3) By rewriting ( tk+ ḱ -tk+ ḱ-1 ) = tk+ ḱ k+Tξ k ) + āt k

  L, ǫ k > 0 ∀k ≥ 0 then one getsǫ k+1 ≤ Ce Lλk Taking ǫ k := E[sup ḱ≤k āt ḱât ḱ 2 ] 1/2in the above inequality and settingC := λT K 1 1 + C 2 0 + λK 2 (1 + C 2 0 ), L := max j∈N E S [L j,S ]for some K 1 , K 2 = c 2 withK 1 := max(c 1 , c 2 1 + C 2 0 ), C 0 = E[sup shows that E[sup ḱ≤k āt ḱât ḱ 2] 1/2 is bounded and implies Proposition 1. When λ -→ 0 we have a weak convergence of the interpolated process to a solution of the ODE. The error gap is √ λ CT which vanishes as λ -→ 0.

j

  and formulate the error system in the time scale τ = Ωt. d dτ ãj,τ = z j µ j (τ ) fj (ã j,τ + µ(τ ) + a * ) (A.4) 0 µ T µ t µ j dτ = we have noted assumption A3, put in the value of (A.7) and computed the average of each term.Substituting (A.6) in (A.26) and matching the first order powers of b j gives α j m = 0 for all j, m such since Λ is nonsingular by Assumption 4. Similarly matching the second order terms of b j and substituting α j m mm , . . . , β T -1 mm , β T mm , β m+1 mm , . . . , β N mm ] T = -Λ -1 π m (A.27) mn = 0 for all j, m, n when m = n and β j mm is given by (A.27). The equilibrium of the average system is ãe Taylor series expansion one can show that the Jacobian Ψ ave = [ψ j,m ] N ×N of (A.5) at ãe j has elements given by ψ j,m = ǫZ j lim by assumption A3 and A4 for sufficiently small b j , which means that the equation (A.29) of the average system (A.5) is locally exponentially stable, i.e. there exist M, m > 0 such that |ã ave (τ )ãe | < M e -tm |ã ave (0)ãe |.

  The above equation can be written in the compact form asa * = Ḡ-1 b

  n -1)(a * ) α p n (a ja * )By differentiating with the respect to a j , a first order condition equivalent a * f -ess = α cn npn . The second order condition is satisfied for α ≤ 1.Proof of Proposition 3:. Simple differentiation of the payoff function (first and second order) yields to αcn npn a α-1 1 m α n -1 = 0 and the second derivative is negative for α ≤ 1. If α > 1 the mean-field taking strategy leads to unboundedness or non-participation.

(

  iv) The fixed-point is m * = αc p . (v) the equilibrium converges to m * = αc p whenever cn n -→ c and p n -→ p as n goes to infinity. This completes the proof of Proposition 4. Proof of Proposition 5:. Let m = m * and m ǫ ǫm+(1-ǫ)m * = m * +ǫ(m-m * ) for ǫ = 1. It follows that m *m = m * -mǫ ǫ . Let A be the quantity r(m * , m ǫ ) -r(m, m ǫ ). Then, ((m * ) αm α )α(m *m)m α ǫ ] (B.2)where we have used that the fact thatc p = (m * ) α . The function x -→ x α is concave in A. Therefore, (m * ) αm α > α(m * ) α-1 (m *m) . By multiplying by m * both sides, one gets m * ((m * ) αm α ) > α(m * ) α (m *m) . Thus, A > p αm α ǫ [α(m * ) α (m *m)α(m *m)m α ǫm) [(m * ) αm α ǫm ǫ ) [(m * ) αm α ǫ ] > 0 (B.6)where the last inequality follows because x α is nondecreasing for α > 0 and m * = m ǫ . We conclude that r(m * , ǫm + (1ǫ)m * ) > r(m, ǫm + (1ǫ)m * ) for any ǫ ∈ (0, 1) and m = m * . In particular, the result is true for the case of interest i.e., for ǫ ∈ (0, ǭm ). This completes the proof.Proof. Proof of Proposition 8: If the function g(.) is sufficiently many times differentiable with simple zero, and m 0 is a initial guess that is close enough to m * , Let us define the error ǫ t+1 m t+1m * and q j = d (j) g(m * ) j!

c 1

 1 |c 2 | and η t+1 = |ǫ t+1 |. Lets now prove the above claim: Using equation (4*) we can write equation (B.7)

Proof.t

  Proof of Proposition 9: Let t ≥ 2. Using Proposition 8 the algorithm has a convergence order of 4. From Definition 12 we have c 1 = lim sup t-→∞ η t+1 η 4 t which implies that η t+1 ≤ c 1 η 4 t which can be re written in terms of η t+1 ≤ c 1 η 4We reiterate the recursive equationη t ≤ c 1 η 4

  0 ≤ η where c 1 = |c 2 | whose value is given in the proof of Proposition 8. Thus,

i

  Thus, every user is satisfied.

Table 2

 2

		.1: Summary of Notations
	Symbol Meaning
	N A j S	set of nodes set of choices of node j, state space

  for Corollary 1. The proof follows from the inequality (2.17) in Proof of Corollary 2. The proof uses the triangle inequality āta * ≤ āta t + a ta * . By Theorem 1, we get āta t ≤ y 2,t and by Theorem 3, we have a ta * ≤ y 1,t Combining together, we arrive at the announced result.

	ḱ≥0	λ 2 k+	ḱ) + sup ḱ≥0	δ k,k+ ḱ	(2.19)
	and t ∈ [t k , t k + T ]
	This completes the proof.
	Theorem 3.

Corollary 2 (Convergence). Under Assumption A1, A3, and A4, the following inequality holds almost surely: āta * ≤ y 1,t + y 2,t where y 2,t := C T (λ k+ ḱ + L The constants in equation (2.18) and (2.19) depends on the number of players and the dimension of the action space.

Table 2

 2

		.2: Equivalent Notations for Wireless
			Remark 2.
	General Application		Description
	rj,k	γ j,k	utility/payoff of transmitter j at time k
	a j,k	p j,k	action/power of transmitter j at time k
	s jj ′ ,k	g jj ′ ,k	state/channel gain between transmitter
			j and receiver j ′ at time k
			r1
		T x 1	s 11	Rx 1
		. . .

Table 2

 2

	.3: Summary of system parameters
		d	λ 4
		N t	4
		M	2
		γ	10
		ǫ k	0.15
		θ 11	0 o
		θ 22	0 o
		θ 12 -60 o θ 21 60 o
	Table 2.4: Summary of sinus perturbation parameters
	user j	1		2
	l j	1.688	1.688
	Ω j	2π4.5185 2π4.5425
	b j	0.5		0.5

  Then a * is a fixed-point of Equation (3.3). Convergence of the Algorithm to Nash Equilibrium: For a vanishing step size i.e. when t λ t = ∞ and t λ 2 t < ∞ the Ishikawa algorithm (Equation(3.3)) converges to the Nash equilibrium a * .

	Proposition 7. Proof. The proof follows in two steps,

  m t )∆g[b t , m t ] -(b tm t )∆g[ȳ t , m t ]) ȳtb t (B.9)Now lets find the expression of ∆g[b t , m t ] = g(bt)-g(mt)

		ǫ t+1 = ǫ t -	g(m t ) A 1	-(1 + w t )	g(ȳ t ) A 2	(B.7)
	where A 1 and A 2 are respectively given by equation (B.8) (B.9)
		A 1 ∆g[b t , m t ]		(B.8)
	A 2	(ȳ t g(mt)

Acknowledgements

We can apply our Ishikawa based algorithm from equation (3.3) to any of the strategies developed in the previous sections by replacing function f (.) with the respective best response function. This has been omitted due to space limitations.

Iterative Learning Algorithm in the Infinite Regime

Let us develop an algorithm that converges to the stable MF equilibrium by following the same steps as in finite case.

The mean-field response is a j,t+1 ∈ arg max a ′ j r(a ′ j , m t ) = br(m t ). In general, this is a multi-valued map (correspondence) as we have seen in the finite number of client case. However, for infinite number of client case (see proposition 5 (iii)), the correspondence is a single-valued map. In this case of a single valued map, equation (3.6) is able to converge to its fixed point. Thus, one can use the following mean-field response learning given by

We denote br(.) by f (.) to simplify the notation where br(.) represents best response. Note that in Equation (3.6) only the starting point m 0 is required if the player knows the structure of f (.). This means that it is not needed to feedback the mean of the mean-field at each step. Finding a fixed-point of the function f (.) is equivalent to finding the root of g(m) f (m)m.

There are several algorithms that may obtain the root of g(m). Each has a different convergence order or time which depends on their construction. We start by defining the convergence order. A classical method that is known to find the root of a single valued map function (e.g. g(.)) is the Newton method and it has a convergence order of o = 2.

Appendix A

Proof of convergence in Extremum Seeking

A.1 Variable Step Size: Proof of Theorem 1

The Theorem 1 states that Under Assumption A1, the learning algorithm converges almost surely to the trajectory of a non-autonomous system given by d dt âj,t = z j b j sin(Ω j t + φ j )E S (r j (S, a t ))

The proof follows in several steps.

• The first step provides conditions for Lipschitz continuity of the expected payoff which is given in Lemma 1. From Lemma 2 we have that ∀j, t, f j (t, a) := b j z j sin(Ω j t + φ j )E S r j (S, a), is Lipschitz over the domain A

• Second step: the learning rates are chosen such that they satisfy assumption A1.

• Third step: we check the noise conditions.

Lemma 1. Let (S, a) -→ r j (S, a) ∀ S ∈ S, ∃ L j,S such that

Proof of Lemma 1. Suppose that a -→ E S r j (S, a) is Lipschitz with Lipschitz constant L j,S , then by Jensen's inequality one has

Then

This completes the proof.

Remark 6.

• Note that under C 1 and C 2 the expected payoff vector r := (r j ) j∈N is Lipschitz continuous with L := max j L j ,

• If S is a compact set and S -→ L j,S is continuous then a -→ E S r j (S, a)

is Lipschitz [In particular, the condition C 2 is not needed]

We shall prove the above remark by Reductio ad absurdum. To prove the second statement of Remark 6 we use compactness and continuity argument. We start from Bolzano-Wierstrass theorem which states that: For any k, any continuous map a -→ f (k, a) over a compact set A has at least one maximum, i.e., sup f (k, a) = max a∈A f (k, a) < ∞. The proof of this statement can be easily done by contradiction. Suppose sup f (k, a) = ∞. Then there exists a sequence (a l ) l such that a l ∈ A but f (k, a l ) -→ ∞ as l goes to infinity. This is impossible because A is compact which implies that f (k, A) = {f (k, a) |a ∈ A} is bounded by continuity.

Since S is compact and S -→ L S is continuous, sup S∈S L S is also finite.

Remark 7. If r j (S, a) is continuously differentiable with the respect to a then it is sufficient to check that the expectation of the gradient of r j (S, a) is bounded (in norm).

if S is in Euclidean Space

• r j (S, a) is differentiable w.r.t a

• r j (S, a), ∇ a r j (S, a) are continuous in S Proof of Lemma 2. Let rj,k+1 be the realization the payoff at time k + 1. The expected value of this random variable can be bounded above the norm of a k .

Let M j,k+1 := z j b j sin(Ω j t k + φ j )(r j,k+1 -E S [r j,k+1 (S, a k+1 )])

≤ zb( rj,k+1 + E S rj,k+1 (S, a k+1 ) )

Where | sin(.)| ≤ 1, z := max |z j |, b := max |b j |, rj,k+1 is bounded because of the Lipschitz condition as mentioned in C 1 , which is shown below.

Where β 1,S := r j (S, 0) . The above equations A.1 show that r j (S, a) is bounded by β 1,S +L j,S a . By taking expectation of the above set of inequalities we get.

Where β 2 := E S r j (S, 0) , L j := E S L j,S . The above set of inequalities A.2 show that E S r j (S, a) is bounded.

Combining the results of inequalities in (A.1) (A.2) we can get

Applying averaging theory to equation (A.4) we can write it as follows, where âavg j,τ represents the average action of node j.

The equilibrium ãe = [ã e 1 , . . . , ãe N ] of (A.5) satisfies

for all j ∈ {1, . . . , N } we postulate that ãe j (which is the equilibrium of the average system) has the form

By expanding fj about a * in (A.6) and substituting (A.7) the unknown coefficients α m j and β mn j can be determined.

The Taylor series expansion of fj about a * in (A.6) for an N-player game is

Where ν j = ãe j + µ j (τ ) substituting (A.8) in (A.6) and computing the average of each term gives

T 0 µ j (τ )(µ 1 (τ ) + ãe 1 ) t 1 , . . . , (µ N (τ ) + ãe N ) t N dτ (A.13)

. . .