First and foremost, I would like to sincerely thank my thesis director Prof. Samson Lasaulce for his unflinching support and belief in me. From my experience as representative of the PhD students of L2S, I know that such support and encouragement is indeed rare, and I was extremely lucky in this respect.

I would also like to thank project LIMICOS -ANR-12-BS03-0005 for financing the major part of my thesis, as well as Orange Labs, Issy-les-Moullineux

List of Figures

transmitters (Txs), 2 receivers (Rxs), and M ≥ 1 non-overlapping frequency bands. One feature of the retained model is that both power allocation policies and channel gains g m ij are assumed to lie in finite discrete sets. . . . . . . . . . . . . . . . . . . . . . . . . .

Relative gain in terms of expected payoff ("OP/BP -1" in [%])

vs SNR [dB] obtained with the Optimal policy (OP) (with and without communication cost) when the reference policy is to put half of the power on each band (BP). Red curves correspond to the HIR, and blue curve to the LIR. B 1 = B 2 = 10MHz. . . . . .

2.3

Marginal probability distributions q X 1 (•) q X 2 (•) of Transmitter 1 and Transmitter 2 for the optimal policy vs SNR [dB] for the High Interference Regime. B 1 = B 2 = 10MHz. . . . . . . . . . . . . . .

2.4

Marginal probability distributions q X1 (•) q X2 (•) of Transmitter 1 and Transmitter 2 for the optimal policy vs β for the optimal policy for the High Interference Regime, where β = B1 B2 . For this simulation, we chose SNR=10[dB]. . . . . . . . . . . . . . . . . .

Optimal probability distribution of X 1 at different maximum

SNRs. SNR=40 dB is the optimal distribution globally . . . . .

Scenario a;

Plot of Expected payoff vs SNR for both the cases. One sees that the discrete strategy quickly beats the all-gaussian strategy, and achieves a much lower optimal cost . . . . . . . . .

5.1

The figure represents the power control functions f i provided by Algo. 1 for the three performance metrics under consideration for power control problem. In particular, it is seen that for maximizing sum-energy, the obtained power control function exhibits a threshold under which transmission should not occur for a given transmitter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i LIST OF FIGURES 5.2 Relative performance gain (w fw N ash /w N ash in % ) of our algorithm when compared to average payoffs obtained by Nash equilibrium for sum-rate and sum-energy. The curve for sumenergy saturates as at high SNR, P max is not utilized as power emitted is much lower. . . . . . . . . . . . . . . . . . . . . . . . .

5.

3 Evaluation of different information available at transmitters for different levels of interference. Most importantly, one notices that transmitter knowing the interference channel gains g ij ,i ̸ = j does not bring any performance gain. . . . . . . . . . . . . . . . . . .

5.4

Influence of channel estimation noise on the power control functions. We see that as noise increases, the optimal power emitted becomes more uniform. This is intuitive as higher the noise, higher the uncertainty in the observation leading to same power emitted for all channel gains observed in the asymptotic case. .

5.5

Influence of error in estimation of channel statistics on average payoff. We see that negative error in statistics (underestimation of channels) leads to worse payoffs than positive error. . . . . . .

5.6

Power control functions for different positive and negative error in estimation of channel statistics. It provides an explanation for the greater payoff loss due to underestimation of channel statistics (negative z). We see that the threshold λ i due to negative error is smaller. This results in higher power emited P i which causes interference with other users. . . . . . . . . . . . . . . . . . . . .

5.7

As we see from this graph, very few quantization points per channel are required to achieve payoffs comparable to a much finer quantization. When Channel statistics are estimated with an error, we notice a maximum with only few quanitzation points for different noise levels. . . . . . . . . . . . . . . . . . . . . . . . .

5.8

The number of Power levels required to achieve comparable payoffs to many more power levels can be seen. It can be seen that around 20 power levels are enough for providing reasonable payoffs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Our algorithm reveals the shape of good power control functions in the presence of interference. In contrast with related works on energy-efficiency [START_REF] Goodman | Power control for wireless data[END_REF], our work shows that thresholding is required to manage interference efficiently. . . . . . . . . . . . . . . . . . . 5.10 Scalability of the proposed thesholding strategy and comparison with Nash Equilibrium. We see that as number of Tx-Rx pairs increase, thresholding strategy does increasingly better, whereas Nash equilibrium payoff falls to 0 . . . . . . . . . . . . . . . . .

5.11

Average normalised distortion against number of basis vectors chosen. We see that 4 vectors are enough to approximate X 0 for an error tolerance level of 5%. . . . . . . . . . . . . . . . . . . . ii LIST OF FIGURES 5.12 Relative payoff loss (u total /u noEV ) -1 in percent) against penetration percentage. For more discussion on the choice of this metric refer to [START_REF] Beaude | Reducing the Impact of EV Charging Operations on the Distribution Network[END_REF]. This figure illustrates the robustness of our approach as well as increased importance at higher penetration rates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. [START_REF] Khayutin | Communication with unobservable constraints[END_REF] Relative payoff loss ((u total /u noEV ) -1 for different years for both algorithms in comparison. We see that Algorithm 1 does considerably better every year. . . . . . . . . . . . . . . . . . . . 5.14 Schematic diagram of Witsenhausen counterexample . . . . . . . 5.15 Evolution of minimum payoffs achieved by different approaches over the last 20 years. We see that the minimum has not reduced much since 2001, leading us to suspect that, atleast for the benchmark case, we might be close to optimal. . . . . . . . . . . 5. [START_REF] Belmega | Learning to precode in outage minimization games over mimo interference channels[END_REF] Vagaries of average payoff w.r.t. range as well stepsize of the alphabet X 0 . As we see, there is no fixed pattern. If one considers a bigger range for X 0 , conventional wisdom says that we must do better, but it is not necessarily the case. We note also that for all stepsizes, above a certain range, the payoff remains constant .

We conclude that one needs to employ techniques akin to ordinal optimization [START_REF] Ho | Granular optimization: An approach to function optimization[END_REF] to find optimal range and stepsize. . . . . . . . . 5.17 We see that if one chooses the right range and stepsize to begin with, one could obtain much better performances for low number of quantization points L. Unfortunately, we have not been able to go further in the simulations to be able to compare the two implementations at higher L. Nonetheless, searching for a 'good' initial range and stepsize can help reach better performances for lower complexity . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

Introduction

The only thing that will redeem mankind is cooperation.

Bertrand Russell

Background and Motivation

In recent times, our computing and sensing capabilities have grown manyfold thanks to accelerated innovation rhythm worldwide. This has led to a proliferation of digital devices. In addition, most devices are increasingly getting connected and are capable of receiving, and in some cases sending information. While this connectivity is currently exploited mostly for providing added functions to devices, various new opportunities exist to exploit this new-found ubiquity of information generated for helping devices coordinate better amongst themselves for certain common objectives or goals. A few examples of such common objectives, include, but are not limited to: coordination amongst self driving cars, coordination of drones to perform a common task, coordination between shops for logistics etc. These payoffs thus depend on the decision of every individual coordinating agent.

Usually, the decisions need to be coordinated taking into account certain externalities which are random. If this were not the case, there would be no information available w.r.t. which the agents would need to coordinate. Also their strategies would be stationary based solely on the estimated statistics of the externalities. Due to this randomness in the nature state and its effect on the payoff, it is more interesting to evaluate schemes which maximize expected payoff w.r.t. the nature state. Thus the objective of the optimization problem is that of finding coordination schemes for maximizing expected payoffs. While, in general, the realizations of this nature state might be correlated, we shall consider the case where they are independent and identically distributed (iid). The 1 CHAPTER 1. INTRODUCTION performance achieved for the i.i.d. case can only be bettered if there actually were correlations which were taken into account.

While centralized solutions to optimization problems are attractive due to better promised performances, they are highly impractical since functional optimization often suffers with prohibitive complexity. Its impracticality also stems from the extensive backhaul required to relay the relevant information upto the central decision-making entity and then relaying back the decision chosen to the agents. Again, this only delays the time required to make the decision. In rapidly changing environments, this time delay could render the whole exercise futile. Moreover, such solutions are not robust to noise and vulnerable to total network failures due to propagation of errors.

A more practical approach is to consider decentralized decision-making, with the understanding that the agents co-operate amongst themselves (with or without explicitly communicating) and making informed decisions. The co-operation is necessary as otherwise the solutions might suffer from the problem of operating at Nash equilibria which are generally not socially optimal [START_REF] Nash | Equilibrium points in n-person games[END_REF]. Eventhough nash equilibria result from certain desirable assumptions about decisions taken in a non-cooperative scheme; one does not need a Karl Marx to realize that better performance could be achieved through co-operation at the expense of certain agents.

Nature has provided a good example of what decentralized cooperation schemes can achieve in the form of ants. Despite very limited computation and sensing capabilities, their resourcefulness in sourcing food and creating complex structures is well documented. Indeed, many mathematically similar problems in traffic control, routing protocols have been explored using algorithms inspired by ants.

For illustrative purposes, consider the mechanism ants use in sourcing food. Ants manage to find the shortest paths from food source to colony without the ability to either sense the food at a distance or explicitly communicate its location to other ants. Ants lay a pheromone trail behind when they walk, which helps them retrace their path back to the colony once food is found. The pheromones however serve another purpose, that of communication with other ants. When an ant, after having found food, returns to the colony, it reinforces the path taken with more pheromones. Ants simply follow trails with stronger pheromone scent and over time this algorithm converges to solutions close to optimal. Notice however that the communication in this case is not explicit. The communication happens implicitly between ants by an ant stumbling across the pheromone trail of other ants. Also, each ant acts only on locally available information: the strength of the pheromone scent. Shorter paths are chosen in a natural manner as the frequency of an ant doing to-and-fro passing through a point in a shorter path is higher.

The decentralization of decision-making leads to the information available to different decision makers being different. This difference could manifest itself due to a plethora of reasons:

• Availability of only local information -In general, devices are only con-nected to other devices and sensors in a local neighbourhood. Even if they are connected further, rapidly changing nature state could force agents to adapt faster, and thus with more localized information.

• Hierarchy of information -Some connected devices might act as nodes or aggregators for a small group, having more information. Some nodes might even have information about future realizations or forecasts of the nature state with respect to which the devices are coordinating.

• Noisy channels -Even when the information transmitted to different devices is the same, each device will observe a noisy version of the signal which will be different for each device.

In general, these three parameters define the information structure of a given coordination problem. Indeed, the performance that can be achieved by coordination is constrained by what information each agent can use to make his decisions and coordinate. Thus, the payoffs that are achievable are characterized by the information structure. Such optimization problems are known as team-decision problems and have been studied extensively since Marschak published his seminal work [START_REF] Marschak | Elements for a theory of teams[END_REF]. Together with [START_REF] Radner | Team decision problems[END_REF], it formed the basis for teamdecision theory. Since then, team-decision problems have been considered with various information structures, and is still an active field of research.

While the ants have devised a decentralized scheme, it might or might not make optimal use of the information available to each ant. The optimality of the scheme depends on information theoretical limits of implicit communication i.e. communication achieved while acting towards an objective. We use certain information theoretical results proved recently [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF] [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF], [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF] which provide precisely the performance limits of coordination problems for certain information structures. Eventhough these results are fairly new and make some assumptions about the information structure, they provide good frameworks for tackling certain interesting applications in various domains such as Telecommunications, Automatic Control, and Smart Grids to name a few.

We divide this thesis into two parts based on two different information structures considered for applications. In the first part, we consider a non-causal information structure with a hierarchy of information where one agent knows the future realizations of the nature state in a non causal manner. Other agents only observe the actions chosen by the informed agent and make their decisions accordingly. Second part explores a causal information structure, i.e. all agents can only observe past or present, but not the future. Two scenarios are considered for the causal case; where agents observe an image of the nature state, or where agents also observe the actions of other agents in a causal manner. The former is a special case of the latter. Inspired from [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF], we considered 2-Agent coordination problems with non causal information structure. We assume that one agent has complete and noncausal knowledge of the sequence of i.i.d. realizations of the nature state X 0 for the entire time period of optimization. The informed agent can exchange his knowledge with the other agent only through his actions. While the non causal assumption might seem unrealistic, one can find many scenarios where it holds true.

Consider the following example of a truck and a car coordinating with the goal of safe navigation over a non-straight road. In this example, the truck, having superior visual information, needs to communicate information about the path to the car. This can be achieved through many ways. A simple solution is to have a communication channel between the two for this purpose. However, imagine that no such channel exists, and the car is reliant solely on the movements of the truck to predict the path ahead. The dual role of the movements of truck, to stay on course as well as signal the path ahead to the car, is the defining characteristic of implicit communication. For further discussion and interesting examples of implicit communication, the author refers to the introduction of [START_REF] Grover | Actions can speak more clearly than words[END_REF] .

We consider this example for many instructive reasons. Firstly, it is a practical scenario being tested by Volvo for creating road trains as a solution for self-driving traffic [START_REF] Chan | Cooperative control of sartre automated platoon vehicles[END_REF] . Secondly, it naturally has the non-causal information structure considered in [12] [7] as the truck can see the path ahead whereas the car behind has no direct visuals of the path ahead and relies solely on signalling by the truck for path prediction. Thirdly, this example is closely related to the famous Witsenhausen counterexample in control theory. We shall explore the CHAPTER 1. INTRODUCTION last point in detail later.

Indeed, similar information structure has been treated before. Notably,The case of perfect observation by agents is treated in [START_REF] Gossner | Optimal use of communication resources[END_REF] while the generalization to noisy observations by agents is conducted in [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF]. To be precise, both references assume that agent 2 has a strictly causal knowledge of the state but it can be shown that not having any knowledge about the states realizations at all induces no limiting performance loss [START_REF] Khayutin | Communication with unobservable constraints[END_REF]. Reference [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF] also states an optimization problem which essentially amounts to maximizing the long term payoff function under some constraints but this optimization problem is not analyzed. One of the contributions of our work is precisely to study this general problem in detail by applying it to solve a real optimization problem in resource allocation.

We distinguish two cases for the non-causal information structures: 1) Discrete Case -where all the intervening variables, system state X 0 , and the actions chosen by the users X i , i ∈ {1, 2} are from a discrete alphabet, and 2) Continuous case -where those alphabets are continuous.

Discrete Case: Solving the optimization problem

In [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF] , they characterize the performance limit of coordination problems with the aforementioned non causal information structure. In particular, they generalize the result found in [START_REF] Gossner | Optimal use of communication resources[END_REF] which only treated the case where the second agent has a perfect observation of the first agent's actions. However, both the references do not solve the optimization problem found with information theoretic constraints. We consider the optimization problem for the case of perfect observations by agent 2, and show certain properties of the solutions to this optimization problem under some reasonable assumptions about the payoffs.

The results thus obtained are applied to the problem of distributed power allocation in a two-transmitter M-band interference channel, M ≥ 1, in which the transmitters (who are the agents) want to maximize the sum-rate under the single-user decoding assumption at the two receivers. In such a setting, the nature state is given by the global channel state. The informed transmitter uses a sequence of power vectors as a code which conveys information about the channel to the other transmitter.

We consider the discrete case, i.e. discrete power levels, and channel coefficients. While majority of the literature on power allocation optimization over multi-band channels (starting with the pioneering work [START_REF] Yu | Distributed multiuser power control for digital subscriber lines[END_REF]) consider In contrast with the vast majority of related works on distributed power allocation over , the set of power allocation vectors at a transmitter is assumed to be discrete and finite (namely, |X i | < ∞) instead of being continuous. This choice is motivated by many applications (see e.g., [START_REF] Xing | Stochastic learning solution for distributed discrete power control game in wireless data networks[END_REF][16] [17][18]).

Continuous Case: Generalizing the Information Constraint

However, the variables could in general take values in a continuous alphabet.

To this effect, we generalized the information theoretic bounds in [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF] to the case when the alphabets are continuous. This generalization is not so straightforward as one needs to take care in redefining the information theoretical notions of mutual information. We consider 2 scenarios for the continuous case: the second agent causally observing the actions of the informed agent, or it observes the realization of nature state too in a causal manner, in addition to the actions of the informed agent. We provide the Information Constraints for both the scenarios for the continuous case. We also treat the special case of all the variables being distributed normally for both the scenarios considered. Also, we treat the case of perfect observation and explicit the information constraint if the variables follow log-normal distribution and burr's distribution.

Another contribution for the continuous case is to consider the Witsenhausen cost function [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] as a common cost function to be minimized by the 2-agent team under the two mentioned scenarios in terms of information structures; this establishes for the first time a link between [START_REF] Gossner | Optimal use of communication resources[END_REF][20] [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF] and [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF]. Indeed, although the Witsenhausen problem can be seen as a one-shot coordination problem, whereas we consider a long-term coordination problem here, the idea of joint control-communication strategies is present in both formulations. As it will be seen, characterizing the feasible performance of the long-term coordination problems amounts to determining a certain information constraint. Although information constraints normally appear when (large) sequences intervene, it has been noted that one-shot problems closely related to the Witsenhausen problem have been solved by introducing an information constraint; this is the case, for instance, for the Gaussian Test Channel (GTC) [START_REF] Bansal | Stochastic teams with nonclassical information revisited: When is an affine law optimal?[END_REF].

We treat the original Witsenhausen counterexample using the theory developed in part II as the information structure therein is more adapted to it.

Coordination problems with a causal information structure

The non-causal information structure however is not applicable to scenarios where only causal observations might be available. In general however, its reasonable to assume that future realizations of the nature state are not known to any agent, even if their statistics are known. In [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF], they characterize the achievable payoffs for coordination with such causal information structure. In particular, they show that the achievable payoffs are characterized by conditional probability distributions for all agents (representing the decisions made). Each conditional probability distribution is shown to be independent of each other. This independence comes directly due to the information structure as all agents are supposed to have an image of the nature state through independent channels. In other words, they do not observe each others' actions. Note that it is this difference in information structure which makes the information constraints found in the non-causal case irrelevant. We use the independence of decisions to construct a distributed algorithm based on sequential global best response dynamics (BRD) which aims at op-timizing the payoff for the given structure. While we provide no proof for optimality, we show via numerous applications that it indeed provides a good framework for tackling practical coordination problems in various settings.

The benefits of our framework, when compared to existing literature on decentralized decision making for the aforementioned applications, essentially boils down to a simple reason; cooperation. Most of the current decentralized solutions evaluate non-co-operative games, and provide strategies to attain Nash Equilibria. While this approach is robust, by virtue of its assumed selfishness of the agents while making their decisions, it clearly does not aim to provide optimal performances assuming cooperation.

The strategies found using our decentralized algorithm has the following salient features which make it more efficient, as well as robust and implementable.

• Cooperative strategies -Since we solve the optimization problem with the goal of optimizing common objective, typically sum-utilities of the individual agents, we easily beat non-cooperative schemes. Moreover, since we use information bound optimal payoffs, we achieve strategies which achieve close to optimal performance for the considered information structure.

• Decentralized decision making -Each agent makes its decision based on local information available to him taking into account the global network statistics. Thus the decentralization of decision is based on decentralized information structure. In particular, we can evaluate the payoff corresponding to different partial information of the nature state available to the coordinating agents.

• Robustness to noise -Indeed, in practical cases the feedback has a noise associated with it. In the algorithms proposed, we take into account the noise statistics for generating the best responses, creating robust functions w.r.t. feedback noise.

• Offline optimization -Agents can find their decision functions individually provided they have the global network statistics, which are easily received through network backhauls. They use an iterative method to find functions maximising expected utility given the probability distributions of network parameters. Thus they can infer the best response of each agent sequentially and converge to its optimal best response.

We identified and modelled coordination problems in two major technological challenges: 1) Power optimization schemes proposed could help improve technological standards for 5G technologies by making them more power efficient and reducing interference caused by independent terminals. 2) Communication within the electricity distribution network can be used, along with neighbourhood consumption forecasts, to even out the consumption over time, thus reducing neighbourhood transformer ageing and joules losses related to transmission costs. In addition to these applications, we treat the famous Witsenhausen CHAPTER 1. INTRODUCTION Counterexample [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] which has a slightly different information structure, where an agent can also observe the actions of another agent in a causal manner.

Power optimization for Wireless Communications with partial CSI

Most power optimization schemes for Wireless communications consider noncooperative strategies and employ game theory to provide guarantees on performance and convergence. While these schemes are robust, the performance achieved by them are not socially optimal as they converge to Nash Equilibria. We use the characterization explicited in [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF] to create co-ordination schemes which are sub-optimal, but still perform better than the solutions proposed till now. Due to the generality of the theory developed, we provide a framework which can be used to tackle different utilities sum-rate, sum-energy, sumthroughput under different settings like parallel interference channel and multiple access channel. We pay greater attention to sum-energy as it is the major focus of wireless communications in recent times. We show that a combination of thresholding and channel inversion strategies provide good performances by mitigating the interference in case the communication channels are bad.

Power consumption scheduling in Smart Grids with uncertainty

The main aim was to make a step further towards knowing how an electrical appliance should exploit the available information to schedule its power consumption. This information corresponds here to an imperfect forecast of the non-controllable (exogenous) load or electricity price. Reaching this goal led us to three key results which can be used for other settings which involve multiple agents with partial information

• In terms of modeling, we exploit the principal component analysis to approximate the exogenous load and show its full relevance

• Under some reasonable but improvable assumptions, this work provides a full characterization of the set of feasible payoffs which can be reached by a set of appliances having partial information

• A distributed algorithm is provided to compute good power consumption scheduling functions. These results are exploited in the numerical analysis, which provides several new insights into the power consumption scheduling problem.

We provide first results for the standard cost functions, transformer aging in particular, where we compare our method with iterative water filling algorithm (IWFA). We test our proposed algorithm on real data and show that it is more robust with respect to noise in the signals received. We also observe that our CHAPTER 1. INTRODUCTION proposed method becomes even more relevant when the proportion of appliances with smart counters increase.

Witsenhausen Counterexample

The famous Witsenhausen counterexample has been a key toy problem for dual objectives of control and communication. Its difficulty can be gauged by the fact that the search for optimal control functions for the problem has been unresolved since 1968 . We generalize the theorem provided by [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF] to the case where agents can observe the action of others in a causal manner to get some insights into this problem.

We propose an iterative approach to solve the optimization problem since finding global optimum has prohibitive complexity. This simplification leads us to an algorithm similar to [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF], albeit with certain small differences in the modelization of observation and action spaces. The differences in quantization can be justified due to [START_REF] Saldi | Finite model approximations and asymptotic optimality of quantized policies in decentralized stochastic control[END_REF], which shows that finite and uniform quantized alphabets for observations give strategies with are epsilon-optimal. We thus obtain functions which are very close to the best solutions known to date (difference of 0.3%), and have a smaller complexity than [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF].

Thesis Outline

This thesis consists of 2 parts. The first part comprises of chapter 2 and chapter 3 and deals extensively with the proposed non-causal information structure. The second part includes chapter 4 and chapter 5 and treats the causal information structure.

In Chapter 2, we introduce the non-causal information structure as well as recall the information theoretical results which we attempt to further develop. These results were shown for the discrete case, i.e. all action alphabets as well as alphabets representing the nature state being discrete. We go further and solve an optimization problem stated by the articles providing the theoretical background, and provide first insights into the structure of the possible solutions.

Chapter 3 generalizes the aforementioned results for the continuous case. While traditionally, the generalization from discrete information theoretical results to continuous ones is assumed, the generalization is not so straightforward as certain concepts need to be redefined carefully. As an application, we consider the Witsenhausen cost function, inspired from the Witsenhausen counterexample whose original version we treat in chapter 5.

In the second part of the thesis, we treat the causal information structure. A general framework is developed in Chapter 4 which recalls the information theoretical characterization. We then propose a decentralized algorithm which exploits the characterization to provide good and practical coordination schemes in general.

We apply the schemes developed to various applications in different domains in Chapter 5; namely team-power optimization in wireless networks in 5.1, power consumption scheduling in smart grids in 5.2, and finding decision functions for Witsenhausen Counterexample in ??. The proposed decision functions outperform the current state of the art simply because of the built-in cooperation while determining them. For Witsenhausen Counterexample, the algorithm proposed coincides with an algorithm already proposed in the literature heuristically.

Concluding remarks are provided in Chapter 6.

Publications

Journal articles Coding through Actions -Discrete Alphabets

• A.
The only reality we truly comprehend is that of our own experience ... The laws of the infinite are extrapolations of our experiences with the finite.

Paul Cohen

Introduction

In this part, we shall only concentrate on the non-causal information structure briefly introduced in the previous chapter. This information structure has an information hierarchy, with an agent knowing, in a non-causal manner, the realizations of the nature state for the entire time period of coordination. The other agent merely has causal observations of the actions of the 'informed' agent. We only consider the 2-Agent case in this part as the more general case of many agents is, for now, untreatable. Nonetheless, the 2-Agent case does provide valuable insights into the limits achievable by co-ordination under such an information structure. We distinguish two different cases: discrete or continuous alphabets for the nature state as well as agents' actions. The information theoretical results of [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF] for the discrete case do not generalize to the continuous case in a facile manner. This stems from the difference in interpretation of entropy and mutual information while passing from discrete to continuous alphabets. We prove the corresponding information theoretical bounds for the continuous case in Chapter 3 In this chapter, we discuss the information theoretical bounds for 2-Agent team coordination problems with non-causal information structure due to [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF], [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF].The central contribution of this chapter is the analysis of an optimization CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS problem which allows one to assess the limiting performance of a team of two agents who coordinate their actions. As a first step, we restrict our analysis to the case of perfect observation by the agents. We use the insights gained to solve a toy power allocation problem in the cognitive radio setting.

The information structure considered in this chapter was first treated by [START_REF] Gossner | Optimal use of communication resources[END_REF]. In that, two agents coordinate over a long period of time, composed of many stages, wherein at each stage they coordinate with the nature state x 0 ∈ X 0 , |X 0 | < +∞ which is assumed i.i.d.. At each stage t ∈ T, agent i ∈ {1, 2} chooses an action x i ∈ X i , |X i | < +∞, which results in the common team payoff w(x 0 , x 1 , x 2 ). Additionally, it is assumed that one agent, agent 1, knows beforehand and perfectly all the realizations of the nature state. On the other hand, agent 2 does not know the state at all and can only be informed about it by observing the actions of agent 1. While in [START_REF] Gossner | Optimal use of communication resources[END_REF] the second agent has a perfect observation of the actions of agent 1, [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] generalizes the results to noisy observations. To be precise, both references assume that agent 2 has a strictly causal knowledge of the state but it can be shown that not having any knowledge about the nature state's realizations at all induces no limiting performance loss [START_REF] Khayutin | Communication with unobservable constraints[END_REF].

The performance analysis of this problem leads to deriving an informationtheoretic constraint. Reference [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] also states an optimization problem which essentially amounts to maximizing the long term payoff function under some constraints, with the information-theoretic constraint being one of them. However, the optimization problem is not analyzed, and this is precisely the main aim of this chapter. As an example of the application The application of interest in this chapter corresponds to a scenario which involves two transmitter-receiver pairs whose communications interfere each other. The communication system under consideration is modeled by an M -band interference channel, M ≥ 1, as depicted in Fig. 2.1. We assume the set of power allocation vectors at a transmitter to be discrete and finite (namely, |X i | < +∞) instead of being continuous. This choice is motivated by well-known results in information theory [START_REF] Cover | Elements of Information Theory[END_REF] which show that the continuous case generally follows from the discrete case by calling quantization arguments. We also assume that channel gains, as defined by Fig. 2.1, lie in discrete sets; this is also well motivated by practical applications such as cellular systems in which quantities such as the channel quality indicator are used. Therefore, for the considered case study, x 0 is given by the vector of all channel gains g m ij , (i, j) ∈ {1, 2} 2 , m ∈ {1, 2, ..., M }, and lies in a finite discrete set (denoted by X 0 ). The chapter is organized as follows. We recall the information theoretical results of [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF] in 2.2. In Sec. 2.3, we introduce and solve the general optimization problem of interest. In Sec. 2.4, we apply the general result of Sec. 2.3 to a special case of payoff function and action sets for the agents. This special case corresponds to the problem of power allocation in a cognitive radio scenario.

CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS

Information Theoretical Bounds

Before we state the general optimization problem with the information theoretical constraints due to the information structure, we would like to recall some results from [START_REF] Larrousse | Coordination in statedependent distributed networks: The two-agent case[END_REF]. Firstly, we restrict the strategies possible for both agents at each time stage t by restricting the variables they can depend on. This also fixes the information structure under consideration. Also, as stated before, we only treat the case of perfect observation by the second agent.

{ σ t : X T 0 → X 1 τ t : X t-1 1 → X 2 (2.1)
where σ t is the strategy for Agent 1, which depends on the knowledge of X T 0 which denotes the realizations of Nature state X 0 ∈ X 0 for all the stages T . Similarly, τ t is the strategy of Agent 2 and depends on the actions of agent 1 X 1 ∈ X 1 upto, but not including the stage t. The realization of the nature state at stage t, denoted by x 0,t , as well as the actions chosen by the agents at that stage x 1,t , x 2,t , together result in the payoff at stage t being w t (x 0,t , x 1,t , x 2,t ). The aim of the agents is to maximize the payoff on an average over many stages. The average payoff can be calculated as w = 1 T ∑ T t=1 w t (x 0,t , x 1,t , x 2,t ). Henceforth, we shall analyze the asymptotic case of T → ∞, which is the limiting case corresponding to the maximum achievable payoff under the given information structure. Since we consider the asymptotic case, the empirical distribution of the random variables q(X 0 X 1 X 2 , t) converges in probability to a time averaged distribution q(X 0 , X 1 , X 2 ) which characterizes the expected payoff. This is encapsulated in the following definition: Definition 1 (Implementability). Let 2.1 be the assumed information structure. The probability density function q(x 0 , x 1 , x 2 ) is implementable if there exists a pair of control strategies (σ t , τ t ) such that as T → +∞, we have for all

(x 0 , x 1 , x 2 ) ∈ X 0 × X 1 × X 2 , 1 T T ∑ t=1 q X0X1X2,t (x 0 , x 1 , x 2 , t) → q(x 0 , x 1 , x 2 ) (2.2)
where q X 0 X 1 X 2 ,t = q X 1 ,X 2 |X 0 ,t × q X 0 is the joint distribution induced by (σ t , τ t ) at stage t.

Note that since the expectation value of the payoff is a linear operator with respect to the distribution q, the time averaged expected payoff w is reachable if and only if the corresponding distribution q is implementable. Also, the factorization of the empirical distribution q can be easily understood, as the random variable X 0 is not controlled by agents and is an extraneous variable. Therefore this factorization is natural. Dropping the index for stage t, we get the expected payoff at a particular stage to be :

CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS E[w] = ∑ (x 0 ,x 1 ,x 2 )∈X 0 ×X 1 ×X 2 q(x 0 , x 1 , x 2 )w(x 0 , x 1 , x 2 ) = ∑ (x0,x1,x2)∈X0×X1×X2 q X 0 (x 0 )q(x 1 , x 2 |x 0 )w(x 0 , x 1 , x 2 )
where q ∈ ∆(X 0 × X 1 × X 2 ), ∆(•) standing for the unit simplex over the set under consideration. q X0 is the marginal law of the random state and thus is fixed (referred to as α i later in this chapter). However, given the information structure 2.1, which distibutions are implementable, or equivaently, which payoffs are achievable? This is precisely the result of a theorem from [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] Theorem 1. [START_REF] Gossner | Optimal use of communication resources[END_REF][20] Let q be a ditribution in ∆(X 0 × X 1 × X 2 ) such that ∀x 0 ∈ X 0 , ∑

x 1 ,x 2 q(x 0 , x 1 , x 2 ) = q X 0 (x 0 ). This distribution q is implementable under the information structure 2.1 if and only if it satisfies the following information constraint:

I q (X 0 ; X 2 ) -H q (X 1 |X 0 , X 2 ) ≤ 0 (2.3)
where, for any two random variables (X, Y ) ∈ (X × Y ) with joint law Q(, ):

• H q (X|Y ) is the conditional entropy of X given Y defined by:

H q (X|Y ) = - ∑ x∈X ∑ y∈Y q(x, y) log 2 q(x, y) q Y (y) (2.4)
where q Y (•) is obtained by marginalization of the joint distribution q(•, •); One can note that the entropy of X is simply:

H q (X) = - ∑ x∈X q X (x) log 2 q X (x) (2.5)
• I q (X; Y ) denotes the mutual information between X and Y , defined by:

I q (X; Y ) = - ∑ x∈X ∑ y∈Y q(x, y) log 2 q(x, y) q X (x)q Y (y) (2.6)
Reference [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] provides a clear interpretation of this constraint. Essentially, the first term can be seen as a rate-distortion term while the second term can be seen as a limitation in terms of communication medium capacity.

The Information Constraint (2.3) can be re-written as:

ic(q) ≜I q (X 0 ; X 2 ) -H q (X 1 |X 0 , X 2 ) (2.7) =H q (X 0 ) + H q (X 2 ) -H q (X 0 , X 1 , X 2 ) (2.8)
CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS

Optimization problem analysis

To state the optimization problem which characterizes the limiting performance in terms of expected payoff, a few notations are in order. We denote the cardinality of the set X i , i ∈ {0, 1, 2} as:

|X i | = n i < ∞.
For the sake of simplicity and without loss of generality, we consider X i as a set of indices X i = {1, ..., n i }.

Additionally, we introduce the vector of payoffs w = (w 1 , w 2 , ..., w n ) ∈ R n with n = n 0 n 1 n 2 and assume, without loss of generality, that Pr[X 0 = j] = α j > 0 for all j ∈ X 0 = {1, . . . , n 0 }, with ∑ n0 j=1 α j = 1. The indexation of w and therefore the vector q = (q 1 , q 2 , ..., q n ) is chosen according to a lexicographic order. This is illustrated through Tab. 2.1. This choice simplifies the analysis of the optimization problem which is stated next.

Index (i) X 0 X 1 X 2 1 1 1 1
n 0 n 1 n 2 n 0 n 1 n 2
Table 2.1: Chosen indexation for the payoff vector w and distribution vector q.

Bold lines delineate blocks of size n 1 n 2 and each block corresponds to a given value of the random state X 0 .

Rewriting the information constraint (2.8) using the chosen indexation, we have:

H q (X 0 ) = - n0 ∑ i=1   ( in1n2 ∑ j=1+(i1)n1n2 q j ) log 2 ( in1n2 ∑ j=1+(i1)n1n2 q j )   (2.9) CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS H q (X 2 ) = - n 2 ∑ i=1   ( n 0 n 1 -1 ∑ j=0 q i+jn 2 ) log 2 ( n 0 n 1 -1 ∑ j=0 q i+jn 2 )   (2.10)
and

H q (X 0 , X 1 , X 2 ) = - n0n1n2 ∑ i=1 q i log 2 q i (2.11)
The optimization problem of interest consists in finding the best joint distribution(s) q (i.e., the best correlation between the agent's actions and the random state) and is as follows:

minimize -E q [w] = - n 0 n 1 n 2 ∑ i=1 q i w i s.t. -1 + n0n1n2 ∑ i=1 q i = 0 -α i + in 1 n 2 ∑ j=1+(i-1)n1n2 q j = 0, ∀i ∈ {1, . . . , n 0 } -q i ≤ 0, ∀i ∈ {1, 2, . . . , n 0 n 1 n 2 }    - n 0 ∑ i=1   ( in 1 n 2 ∑ j=1+(i-1)n1n2 q j ) log 2 ( in 1 n 2 ∑ j=1+(i-1)n1n2 q j )   - n2 ∑ i=1   ( n0n1-1 ∑ j=0 q i+jn2 ) log 2 ( n0n1-1 ∑ j=0 q i+jn2 )   + n 0 n 1 n 2 ∑ i=1 q i log 2 q i } ≤ 0 (2.12)
The first and third constraints imposes that q has to be a probability distribution. The second constraint imposes that the marginal of q with respect to x 1 and x 2 has to coincide with the distribution of the random state which is fixed. The fourth constraint is the information-theoretic constraint which corresponds to (2.3) and has been re-written here as H q (X 0 )+H q (X 2 )-H q (X 0 , X 1 , X 2 ) ≤ 0, to simplify the analysis.

To solve the optimization problem (2.12) we will apply the Karush Kuhn Tucker (KKT) necessary conditions for optimality [START_REF] Boyd | Convex optimization[END_REF]. For this purpose, we first verify that strong duality holds. This can be done e.g., by proving that Slater's constraint qualification conditions are met namely, there exists a strictly feasible point for (2.12) and that (2.12) is a convex problem. First, by specializing Lemma 1 in [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] in the case of perfect observation, we know that (2.3) defines a convex set. Since the cost function and the other constraints of the problem are affine, the problem is then convex; as a consequence. KKT conditions are also sufficient for optimality. The existence of a feasible point follows from the next proposition.

CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS

Proposition 1. There exists a strictly feasible distribution q + ∈ ∆(X 0 ×X 1 ×X 2 ) for the optimization problem (2.12).

Proof. First, choose a triplet of random variables (X 0 , X 1 , X 2 ) which are independent. That is, we consider a joint distribution q + which is of the form q + (x 0 , x 1 , x 2 ) = q + X 0 (x 0 )q + X 1 (x 1 )q + X 2 (x 2 ). Second, one can always impose a full support condition to the marginals q + X 1 and q + X 2 (i.e., ∀x i , q Xi (x i ) > 0); q + X 0 ≡ q X0 has a full support by assumption. Therefore, for the distribution q + (x 0 , x 1 , x 2 ) to be strictly feasible, it remains to be checked that the information-theoretic constraint is active. And this is indeed the case since:

I q (X 0 ; X 2 ) -H q (X 1 |X 0 , X 2 ) (a) = 0 -H q (X 1 |X 0 , X 2 ) (b) = -H q (X 1 ) (c) < 0
where: (a) and (b) comes from the independence hypothesis between X 0 , X 1 , and X 2 ; (c) comes from the positiveness of the entropy and the fact that every q + (x 0 , x 1 , x 2 ) (and thus every q + X1 (x 1 )) is strictly positive.

Following the previous considerations, KKT conditions can be applied. The Lagrangian function can be written as:

L(q, µ, µ 0 , λ, λ IC ) = - n 0 n 1 n 2 ∑ i=1 (w i q i + λ i q i ) + µ 0 [ n0n1n2 ∑ i=1 q i -1 ] + n0 ∑ i=1 µ i   in1n2 ∑ j=1+(i-1)n1n2 q j -α i   + λ IC { - n 0 ∑ i=1   ( in 1 n 2 ∑ j=1+(i-1)n1n2 q j ) log 2 ( in 1 n 2 ∑ j=1+(i-1)n1n2 q j )   - n2 ∑ i=1   ( n 0 n 1 -1 ∑ j=0 q i+jn 2 ) log 2 ( n 0 n 1 -1 ∑ j=0 q i+jn 2 )   + n0n1n2 ∑ i=1 q i log 2 q i } where λ = (λ 1 , ..., λ n 0 n 1 n 2 ), µ = (µ 1 , ..., µ n 0 n 1 n 2 )
, and IC stands for information-CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS theoretic constraint. KKT conditions follow:

∂L ∂q i = -w i -λ i + µ 0 +   n0 ∑ j=1 µ j {1+n 1 n 2 (j-1)≤i≤jn 1 n 2 }   + λ IC [ - n0 ∑ k=1 {1+(k-1)n 1 n 2 ≤i≤(k)n 1 n 2 } log 2 ( kn1n2 ∑ j=1+(k-1)n1n2 q j ) - n 2 ∑ k=1 {i∈{k,k+n2,...,k+(n0n1-1)n2}} log 2 ( n 0 n 1 -1 ∑ j=0 q k+jn2 ) + log 2 q i -1 ] = 0 ∀ i ∈ {1, 2, . . . , n 0 n 1 n 2 } (2.13) λ i ≥ 0 ∀ i ∈ {1, 2, . . . , n 0 n 1 n 2 } (2.14) λ IC ≥ 0 (2.15
)

λ i q i = 0 ∀ i ∈ {1, 2, . . . , n 0 n 1 n 2 } (2.16) λ IC i(q) = 0 (2.17)
where . is the indicator function and i(q) = is the inequality constraint function associated with the information-theoretic constraint (2.3). By inspecting the KKT conditions the following proposition can be proved.

Proposition 2. If there exists a permutation such that the payoff vector w can be strictly ordered, then any optimal solution of (2.12) is such that the information-theoretic constraint is active i.e., λ IC > 0.

Proof. We proceed by contradiction. Assume that the payoff vector can be strictly ordered and that the constraint is not active for solutions under consideration, that is, λ IC = 0. First, consider possible solution candidates q which have two or more nonzero components per block of size n 1 n 2 which is associated with a given realization x 0 of the random state (see Tab. 2.1) . Since there exists a pair of distinct indices (j, k) such that q j > 0, q k > 0, we have that λ j = 0, λ k = 0. This implies that, through the gradient conditions of the KKT conditions, w j = w k which contradicts the fact that payoffs are strictly ordered.

Second, consider possible solution candidates q which have only one nonzero component per block associated with x 0 (see Tab. 2.1). This implies that

H q (X 0 , X 1 , X 2 ) = H q (X 0 ) = H(X 0 ), which means that H q (X 0 ) + H q (X 2 ) > H q (X 0 , X 1 , X 2 )
, whenever H q (X 2 ) > 0. This means that the constraint is violated and therefore the considered candidates are not feasible. Now if, H q (X 2 ) = 0, we see that the constraint is active and contradicts again the starting assumption. Proposition 2 is especially useful for wireless communications when the state is given by the overall channel. Due to channel randomness, the most common CHAPTER 2. CODING THROUGH ACTIONS -DISCRETE ALPHABETS scenario is that the payoffs associated with the channel realizations are distinct. For this reason, we will assume such a setting in this chapter and thus that λ IC > 0. If λ IC > 0, we have the following:

• We can not have λ i > 0 for one or more i ∈ {1, 2, . . . , n 0 n 1 n 2 }. Indeed, if for example λ i > 0, then q i = 0, which implies log 2 (q i ) = -∞ and (2.13) can not be satisfied.

• However, if one of the q i 's equals 0, and

q k = 0 for all k such that k[n 2 ] = i[n 2 ]
, then the λ IC component equals lim x→0

x n 0 n 1 x and does not go to -∞. This case cannot be discarded, but it can be said that X 2 is deterministic in such a case. Summarizing our analysis, the only possible cases are:

• λ IC > 0, and exactly one λ i for each block (corresponding to a particular state of nature) are non-zeros, and they have to be associated with the same action of X 2 (X 2 has to be deterministic). In this case there is no communication, and the optimal strategies are trivial. Therefore we shall not be discussing this case henceforth.

• The only interesting case that is relevant is:

λ i = 0 ∀ i ∈ {1, 2, . . . , n 0 n 1 n 2 } λ IC > 0
For the latter case, KKT conditions become:

∂L ∂q i = -w i + µ 0 +   n0 ∑ j=1 µ j {1+n 1 n 2 (j-1)≤i≤jn 1 n 2 }   + λ IC [ - n 0 ∑ k=1 {1+(k-1)n1n2≤i≤(k)n1n2} . log 2 ( (k)n1n2 ∑ j=1+(k-1)n 1 n 2 q j ) - n2 ∑ k=1 {i∈{k,k+n2,...,k+(n0n1-1)n2}} log 2 ( n0n1-1 ∑ j=0 q k+jn 2 ) + log 2 q i -1 ] = 0 ∀ i ∈ {1, 2, . . . , n 0 n 1 n 2 } (2.18) λ i ≥ 0 ∀ i ∈ {1, 2, . . . , n 0 n 1 n 2 } (2.19) λ IC ≥ 0 (2.20) i(q) = 0.
(2.21)

Now that we have proved some useful results about structure of the optimal solutions of (2.12), a natural question is whether the optimal solution is unique, which is the purpose of the next proposition. Proposition 3. If there exists a permutation such that the payoff vector w can be strictly ordered, the optimization problem (2.12) has a unique solution.

Proof. We know, by Proposition 2, that λ IC > 0 for any optimal solution. It turns out that, if λ IC > 0, the Lagrangian of (2.12) is a strictly convex function w.r.t. the vector q. Indeed, as the Lagrangian is the sum of linear functions and a strictly convex function and that the optimization spaces are compact and convex. It remains to show that Φ :

Q → I Q (X 0 ; X 2 ) -H Q (X 1 |X 0 , X 2 ) is strictly con- vex over the set of distributions Q ∈ ∆(X 0 × X 1 × X 2 ) that verify Q X0 := ∑ (x1,x2) Q(x 0 , x 1 , x 2 ) = ρ(x 0 ) with ρ fixed. The first term I Q (X 0 ; X 2 ) is a convex function of Q X2|X0 for fixed Q X0 . For the second term, let λ 1 ∈ [0, 1], λ 2 = 1 -λ 1 , (Q 1 , Q 2 ) ∈ ∆ 2 (X 0 × X 1 × X 2 ) and Q = λ 1 Q 1 + λ 2 Q 2 .
We have that:

H Q (X 1 |X 0 X 2 ) = - ∑ x 0 ,x 1 ,x 2 ( 2 ∑ i=1 λ i Q i (x 0 , x 1 , x 2 )
) .

log

[ ∑ 2 i=1 λ i Q i (x 0 , x 1 , x 2 ) ∑ 2 i=1 λ i Q i X2 (x 2 ) ] > - ∑ x0,x1,x2 2 ∑ i=1 λ i Q i (x 0 , x 1 , x 2 ) log [ λ i Q i (x 0 , x 1 , x 2 ) λ i Q i X 2 (x 2 ) ] = - 2 ∑ i=1 λ i ∑ x 0 ,x 1 ,x 2 Q i (x 0 , x 1 , x 2 ) log [ Q i (x 0 , x 1 , x 2 ) Q i X 2 (x 2 ) ] = λ 1 H Q 1 (X 1 |X 0 X 2 ) + λ 2 H Q 2 (X 1 |X 0 X 2 )
where the inequality comes from the log sum inequality [START_REF] Cover | Elements of Information Theory[END_REF], with:

a i = λ i Q i (x 0 , x 1 , x 2 ) and b i = λ i Q i X 2 (x 2 ) for i = 1, 2 and for all x 0 , x 1 , x 2 such that Q i X 2 (x 2 ) > 0. The inequality is strict because a1 b1 ̸ = a2 b2 , since we have assumed that Q 1 and Q 2 distinct.
The uniqueness property for the optimization problem is particularly useful in practice since it means that any converging numerical procedure to find an optimal solution will lead to the unique global minimum. We now consider the specific problem of power allocation over M -band interference channels with two transmitter-receiver pairs. Transmission are timeslotted and on each time-slot, transmitter i ∈ {1, 2} has to choose a power allocation vector in the following set of actions:

P i = { P max ℓ e ℓ : ℓ ∈ {1, . . . , M }, e ℓ ∈ {0, 1} M , M ∑ i=1 e ℓ (i) = ℓ } (2.22)
where P max is the the power budget available at a transmitter. Each channel channel is assumed to lie a discrete set Γ = {g 1 , ..., g S }, S ≥ 1, g s ≥ 0 for s ∈ {1, ..., S}. Therefore, if one denotes by g m the vector of four channel gains corresponding to the band m ∈ {1, ..., M }, then g m ∈ Γ 4 and the global channel state g = [g 1 , ..., g M ] lies in G = Γ 4M whose cardinality is S 4M . As it is always possible to find a one-to-one mapping between P i , i ∈ {1, 2}, (resp. G) and X i (resp. X 0 ) as defined in Sec. 2.3, the results derived therein can be applied here. At last, for a given time-slot, the instantaneous or the stage payoff function which is common to the transmitters is chosen to be:

w : G × P 1 × P 2 → R + (g, p 1 , p 2 ) → 2 ∑ i=1 M ∑ m=1 B m log 2 ( 1 + g m ii p m i σ 2 + g m -ii p m -i ) (2.23)
where p i is the power allocation chosen by transmitter i on the current time-slot whose channel state is g, σ 2 is the noise variance, B m is the bandwidth of band m, p m i the power transmitter i allocates to band i,-i stands for the transmitter other than i.

Simulation setup

In this section, specific values for the parameters which are defined in the preceding section are chosen, in particular to make the interpretations relatively easy. We assume M = 2 bands and therefore that the transmitters have three actions:

P i = P max { (0, 1), (1, 0), ( 1 2 , 1 2 )
} for i ∈ {1, 2}. As [START_REF] Mochaourab | Resource allocation in protected and shared bands: uniqueness and efficiency of nash equilibria[END_REF] we assume the first band to be protected (g 1 12 = g 1 21 = 0) whereas the second band corresponds to a general single-band interference channel. The other channel gains are chosen as follows:

g 1 ii ∈ {0.1, 1.9}, i ∈ {1, 2} g 2 ij ∈ {0.15, 1.85}, (i, j) ∈ {1, 2}. We suppose that each g k ij , k = 1, 2 is i.i.d. and Bernouilli distributed g k ij ∼ B(π k ij ) with P (g 1 ii = 0.1) = π 1 ii and P (g 2 ij = 0.15) = π 2 ij . We define SNR[dB]= 10 log 10 ( P max σ 2
) , and we consider two regimes for the second band: a high interference regime (HIR), defined by (π 2 11 , π 2 12 , π 2 21 , π 2 22 ) = (0.5, 0.1, 0.1, 0.5) and a low interference regime (LIR) defined by (π 2 11 , π 2 12 , π 2 21 , π 2 22 ) = (0.5, 0.9, 0.9, 0.5). For the first band, we take π 1 11 = π 1 22 = 0.2. One can see that the high interference regime corresponds to the P ((g 2 ij |i ̸ = j) = 1.85) = 1 -0.1 = 0.9, thus creating high interference due to higher probability for a greater value of (g 2 ij |i ̸ = j) which is precisely the interference in the band 2. The similar intuition holds for low interference regime as well. Three power allocation policies will be considered:

• The costless communication case, where both transmitters knows the state beforehand and can reach the maximum payoff at every stage;

• The (information-constrained) optimal policy (OP) corresponding to the optimal solution of the optimization problem 2.12;

• The blind policy (BP), where transmitters don't know anything about channel gains and always choose to put half of their power in each band:

p 1 = p 2 = P max ( 1 2 , 1
2 ) at every stage. Fig. 2.2 represents the gain allowed by asymmetric coordination w.r.t. the case where the transmitters always use the uniform power allocation policy (Blind Policy). This gain can be as high as 40% for the considered range of SNR. It is seen that the gain are particularly significant when the interference is high (red curves) and in the low and high SNR regimes (red and blue curves on the left and right sides). The first observation translates the intuition that the higher the interference level the stronger is the gain brought by coordination. The second can be understood as follows. In the high SNR regime, the transmission rate over the non-protected band is interference limited and bounded and it is better to allocate the power to the protected band which allows an arbitrarily large rate as the SNR grows large. This explains why allocating uniformly the power becomes more and more suboptimal as the SNR increases. In the low SNR regime, essentially the interference becomes negligible and the best power allocation policies roughly correspond to water-filling over the available channels. At low SNR, the best water-filling policy is to use the best band and not to allocate power uniformly, which explains the gap between the coordinated policies and uniform power allocation.

Our explanations are sustained by Fig. 2.3, which shows the probability that a transmitter uses a given power allocation vector. For instance, at low SNR, the dominant actions for both transmitters is to use the protected band. It can be noticed that transmitter 1 has also to convey information to transmitter 2 (i.e., ensuring that the entropy of X 1 is not too small), which is why he cannot use the protected band as often as transmitter 2. One also notices in Fig. 2.3 that the probability of the action (0, 1) (using the shared band) is zero from lower SNR values for DM2 than for DM1. This can be explained by the fact that the higher the power available for both DM, the higher the interference in the non-protected band. However, DM1 still chooses to play this action as it Lastly, Fig. 2.4 shows the influence of the bandwidths on the power allocation policies. Not surprisingly, the higher the bandwidth of the protected band is, the more often it is used, and conversely for the non-protected band. Concerning the uniform policy, it is seen that transmitter uses it more frequently, although channel conditions are similar, which translates again the need for transmitter 1 to convey information.

Conclusions

The analysis clearly illustrates the potential benefit of the proposed approach, by embedding coordination information into the power allocation levels, relative gains as high as 40% can be obtained w.r.t. the uniform power allocation policies. In this work, the embedded information is a distorted version of the channel state but the proposed approach is much more general: information about the state of queue, a battery, etc, could be considered; other types of policies might be considered to encode information e.g., channel selection policies, transmit power levels.

Chapter 3 Continuous Alphabets -Witsenhausen Cost Function

All means (even continuous) sanctify the discrete end.

Doron Zeilberger

In this chapter, we consider a team with two agents who are trying to maximize their common payoff over a long time period, i.e., composed of many time-slots. At every time-slot or stage t ∈ {1, • • • , T }, Agent i, i ∈ {1, 2} chooses its action x k ∈ X k , where X k is a continuous set. The instantaneous payoff function w(x 0 , x 1 , x 2 ) depends on the realization of the random variable X 0 with realizations x 0 ∈ X 0 . The set X 0 is also continuous and realizations of X 0 are assumed to be i.i.d.. The information structure is thus similar to the one considered in 2, albeit with alphabets for nature state X 0 and agents' actions X i being continuous.

A problem with the same information structure was addressed for the first time in [START_REF] Gossner | Optimal use of communication resources[END_REF]. Therein, the assumptions made are as follows: it is assumed that at any time Agent 1 knows the past, current, and future realizations of X 0 perfectly, whereas Agent 2 only observes the actions of Agent 1 in a strictly causal manner. Such a scenario has been extended in a couple of papers cited further.However, all of them treated the case where the action sets as well as the system state set were discrete and finite, i.e.,

∀ k ∈ {0, 1, 2}, |X k | < ∞.
Reference [START_REF] Gossner | Optimal use of communication resources[END_REF] treated the case of an information structure in which Agent 2 has perfect observation and showed that the average performance characterization is equivalent to finding the appropriate information constraint. In [START_REF] Larrousse | Coded power control: Performance analysis[END_REF] this result was generalized to the case where Agent 2 has imperfect observations. While all these contributions assume a strictly causal knowledge of the system state x 0 at Agent 2, the case where this assumption is relaxed was first presented in [START_REF] Larrousse | More about optimal use of communication resources[END_REF] and treated rigorously in [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF].

The main contribution of the work presented in this chapter is to generalize this approach of finding the limiting performance to the case of continuous action sets, which is an important case for control problems as many designs involve continuous controlers. A second contribution is to consider the Witsenhausen cost function [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] as a common cost function to be minimized by the 2-agent team under the two mentioned scenarios in terms of information structures; this establishes for the first time a link between [START_REF] Gossner | Optimal use of communication resources[END_REF][20] [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF] and [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF].

Indeed, although the Witsenhausen problem can be seen as a one-shot coordination problem, whereas we consider a long-term coordination problem here, the idea of joint control-communication strategies is present in both formulations. As it will be seen, characterizing the feasible performance of the long-term coordination problems amounts to determining a certain information constraint. Although information constraints normally appear when (large) sequences intervene, it has to been noted that one-shot problems closely related to the Witsenhausen problem have been solved by introducing an information constraint; this is the case, for instance, for the Gaussian Test Channel (GTC) [START_REF] Bansal | Stochastic teams with nonclassical information revisited: When is an affine law optimal?[END_REF]. The approach we adopt has connections with that of [START_REF] Kulkarni | An optimizer's approach to stochastic control problems with nonclassical information structures[END_REF] where probability distributions which minimize the cost function are used. However, in the latter the authors restrict their attention to what modifications render the (one-shot) Witsenhausen problem simpler to solve, and do not tackle the general framework of long-term implicit communication.

The chapter is structured as follows. Section 3.1 provides the proposed problem formulation. It explains that characterizing the feasible set of expected common payoffs amounts to characterizing implementable joint probability distributions. Section 3.2 provides, for the two information structures considered, the two information constraints which allows one to characterize the implementable distributions. The Gaussian case is provided as a special instance, which establishes a connection with the dirty-paper coding problem [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF]. We also provide the information constraints for other continuous distribution in the case of where the second agent has perfect observation of first agent's actions. In Section 5.3.2, we discuss the Witsenhausen cost function in context to our problem. Section 3.3.1 describes the numerical analysis for the special instance of payoff function (which equals minus the Witsenhausen cost function) and provide numerical results. Section 3.4 concludes the chapter.

Problem statement

Consider two agents, Agent 1 and Agent 2, who want to coordinate through their actions x 1 ∈ X 1 and x 2 ∈ X 2 . The problem is said to be distributed in the sense that each agent can only control one variable of their common payoff function w(x 0 , x 1 , x 2 ). The action set for both agents X 1 , X 2 as well as the set of system states X 0 are continuous sets. The realizations of the system state are assumed to be i.i.d. and generated from a random variable X 0 whose probability density function is denoted by f 0 (x 0 ). We shall use the notation f V (v) or f (v)

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

to refer to the probability density function of the generic continuous random variable V . The control strategies of Agents 1 and 2 are sequences of functions which are respectively defined by:

   σ t : X T 0 → X 1 τ a t : X t-1 0 × Y t-1 → X 2 τ b t : Y t-1 → X 2 (3.1)
where T ≥ 1 is the total number of stages over which the agents are assumed to interact, Y is the observation set of Agent 2 and the superscripts a or b correspond to the two considered scenarios in terms of observation structure.

The control strategy for Agent 1 σ t basically means that it knows the realizations of the system state for all T beforehand, and uses that information to choose its actions; note that the methodology used in this chapter can also be exploited under less restrictive knowledge assumptions at Agent 1. The merit of the assumptions made for Agent 1 is that it allows one to make progress in the direction of quantifying the relationship between agents' observation capabilities and reachable performance, which is not well understood. Additionally, there already exist applications for which it is relevant: coordination between robots when a leader knows the trajectory in advance; distributed power control in wireless networks; robust image watermarking. For Agent 2, we consider two different control strategies τ a t and τ b t . The control strategy of scenario a assumes that Agent 2 observes the past realizations of the system state x 0 (1), ..., x 0 (i -1) as well as y(1), ..., y(i -1). The control strategy of scenario b is only based on the latter sequence and seems to be more in line with a possible information structure of a long-term version of the Witsenhausen problem. In any case, it is less demanding in terms of information assumptions. The observations y(1), ..., y(T ) are assumed to be generated by a memoryless channel whose transition probability is denoted by γ and verifies a Markov condition f Y |X 0 ,X 1 ,X 2 (y|x 0 , x 1 , x 2 ) = γ(y|x 1 ). The additive white Gaussian noise (AWGN) channel Y = X 1 + Z is an intensively used model which verifies this condition.

The instantaneous team payoff function is denoted by w(x 0 , x 1 , x 2 ). Since X 0 is not deterministic we shall be considering the expected payoff

E f [w(X)] = ˆx∈X w(x 0 , x 1 , x 2 )f (x 0 , x 1 , x 2 )dx 0 dx 1 dx 2 (3.2) where X = (X 0 , X 1 , X 2 ), x = (x 0 , x 1 , x 2 ), and X = X 0 × X 1 × X 2 .
In the sequel, we will also denote by W (f ) the above expected payoff i.e.,

W (f ) = E f [w(X)].
What matters for the expected payoff is function f which characterizes the possible correlations among the three random variables X 0 , X 1 , and X 2 . This correlation precisely measures the degree to which the agents can coordinate with each other and the system state. To understand the relationship between the agents strategies (5.8) and the expected payoff (3.2), let us define the notion of implementable distributions. FUNCTION Definition 2 (Implementability). Let s ∈ {a, b} be the assumed information structure. The probability density function f (x 0 , x 1 , x 2 ) is implementable if there exists a pair of control strategies (σ t , τ s t ) such that as T → +∞, we have for all

(x 0 , x 1 , x 2 ) ∈ X 0 × X 1 × X 2 , 1 T T ∑ i=1 ˆy∈Y f X 0 X 1 X 2 Y,i (x 0 , x 1 , x 2 , y) → f (x 0 , x 1 , x 2 ) (3.3)
where f X0X1X2Y,i = γ × f X1,X2|X0,i × f 0 is the joint distribution induced by (σ t , τ s t ) at stage i. Note that since the expectation value of the payoff is a linear operator with respect to the distribution f , the time averaged expected payoff W is reachable if and only if the corresponding distribution f is implementable. In Section 3.2, we shall characterize the set of reachable or feasible average payoffs under the information structure given by (5.8), which is equivalent to characterizing the set of implementable distributions.

Performance analysis: limiting performance characterization 3.2.1 General case

In the case of finite alphabets |X i | < ∞, i ∈ {0, 1, 2}, it has been shown in the cases which have been treated so far [START_REF] Gossner | Optimal use of communication resources[END_REF], [START_REF] Larrousse | Coded power control: Performance analysis[END_REF], [START_REF] Larrousse | More about optimal use of communication resources[END_REF], [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF] that characterizing the set of implementable (mass) probability distributions amounts to determining a certain information constraint. For instance in the previous chapter, i.e. case of discrete sets and perfect observation (Y = X 1 ), the necessary and sufficient condition for a joint probability mass distribution Q(x 0 , x 1 , x 2 ) to be implementable is that

H Q (X 0 ) + H Q (X 2 ) -H Q (X 0 , X 1 , X 2 ) ≤ 0 (3.4)
where H Q is the discrete entropy function under a fixed joint distribution (see Section [START_REF] Cover | Elements of information theory[END_REF] for the different expressions of the entropy used in this section).

A well-known reasoning in information theory [START_REF] Cover | Elements of information theory[END_REF], and intensively used in control when communication problems are involved, is to use the information constraint derived in the discrete case and just replace the discrete entropy function with the differential entropy. It can be proved that this reasoning is perfectly valid if considered continuous variables are Gaussian (see e.g., [START_REF] Gamal | Network information theory[END_REF] for a recent reference). For coordination problems such as the one under investigation, imposing the agents' actions to be Gaussian is generally suboptimal. Elaborating further, if we replace the discrete entropy function with the differential entropy we obtain

h f (X 0 ) + h f (X 2 ) -h f (X 0 , X 1 , X 2 ) ≤ 0 (3.5)
where h f is the differential entropy under the fixed joint distribution f .

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

It turns out that this condition can be shown to be non-necessary in general, indicating that the transition from the discrete case to the continuous case needs some special care in the problem under investigation. To convince the reader, let us recall one of the Cantor's theorems (see e.g., [START_REF] Steen | Counterexamples in Topology[END_REF]). There exists a bijective map from R T to R. Therefore, a possible control strategy for Agent 1 might be as follows. On the first stage, Agent 1 maps or encodes the whole sequence of states (x 0 (1), • • • , x 0 (T )) ∈ R T into a single action x 1 (1) ∈ R. Since Agent 2 observes this action perfectly, it can decode it perfectly and is thus informed of the sequence of states as well. This would mean that from stage i = 2, the two agents can correlate their actions in a arbitrary manner with the system state; in particular they can choose the pair (or one of the pairs) which maximizes w at a given stage i ≥ 2. This means that any probability density function f X0X1X2 can be implemented (asymptotically), contradicting the fact that any implementable distribution has necessarily to verify the continuous counterpart of (3.4) which is (3.5). This apparent contradiction comes from the fact that expressing (3.4) in the continuous case with differential entropies relies on assumptions which need to be specified rigorously for the problem. Indeed, the information constraint can be shown to be necessary and sufficient for implementability within some classes of random variables. One of the broadest classes which is known is provided in [START_REF] Gray | Probability, Random Processes, and Ergodic Properties[END_REF]. It turns out that if one wants to define a probability measure on the Cantor set, one does not fall into this broad class which is specified below. Let's first give the definition of a field in probability theory. Definition 3 (field). Let (Ω, B) be a measurable space. We call field F a collection of subset of Ω such that :

Ω ∈ F if F ∈ F then F c ∈ F

F is stable under f inite union

A set A of a field F is called an atom if and only if the only subsets which are also member of the field are the set itself and the empty set.

Definition 4 (base). A sequence of finite field

F n ; n = 0, 1, ... is called a basis of a field F if F n ↑ F and if G n is a sequence of atoms of F n such that G n ∈ F n and G n+1 ⊂ G n , n = 0, 1, 2, ... then ∩ ∞ n=1 G n ̸ = ∅.
A sequence F n ; n = 0, 1, ... is called a basis of a measurable space (Ω, B) if F n are a basis of a field F which generates B : B = σ(F). A field F is called standard if it has a basis. A measurable space (Ω, B) is called standard if it can be generated by a standard field i.e. B has a basis. We can now define the mutual information in a standard space provided by [START_REF] Wyner | A definition of conditionnal mutual information for arbitrary ensemble[END_REF].

Definition 5 (Mutual Information). Let (Ω, F, P ) be a standard probability space and X ∈ R, Y ∈ R two generic random variables:

X : Ω → A X , Y : Ω → A Y with (A X , B X ), (A Y , B Y ) two measurable spaces. Let F X = X -1 (A X ) and F Y = Y -1 (A Y ) the sub-σ-algebra of F induced by X and Y . Let P X = {A j } N X j=1 ⊂ F X and P Y = {B j } N Y j=1 ⊂ F Y (3.6)
be finite partitions of Ω. With these partitions we associate the following random variables:

X(ω) = j for ω ∈ A j with 1 ≤ j ≤ N X Y (ω) = j for ω ∈ B j with 1 ≤ j ≤ N Y . (3.7)
The mutual information between X ∈ R and Y ∈ R is then defined by: i(X; Y ) = sup

P X ,P Y I( X; Y ) (3.8)
where I is the classical mutual information between two discrete random variables [START_REF] Cover | Elements of Information Theory[END_REF]. Similarly, the conditional mutual information is defined by

i(X; Y |Z) = i(X; Y, Z) -i(X; Z). (3.9)
The above framework is exploited to prove the following two theorems.

Theorem 2 (Scenario a). Assume that all random variables under use are defined on a standard probability space. Consider a joint probability density distribution f (x 0 , x 1 , x 2 ) such that ∀x 0 ∈ X 0 , ´x1,x2 f (x 0 , x 1 , x 2 )dx 1 dx 2 = f 0 (x 0 ). Then, the distribution f is implementable if and only if f (x 0 , x 1 , x 2 , y) verifies the following information constraint:

i f (X 0 ; X 2 ) ≤ i f (X 1 ; Y |X 0 , X 2 ) (3.10)
where the arguments of the mutual information i f (.) are defined from f and f (x 0 , x 1 , x 2 , y) = f (x 0 , x 1 , x 2 )γ(y|x 1 ).

Theorem 3 (Scenario b). Assume that all random variables under use are defined on a standard probability space. Consider a joint probability density dis-

tribution f (x 0 , x 1 , x 2 ) such that ∀x 0 ∈ X 0 , ´x1,x2 f (x 0 , x 1 , x 2 )dx 1 dx 2 = f 0 (x 0 ). Then, the distribution f is implementable if and only if f (x 0 , x 1 , x 2 , y, x ′ 1 )
verifies the following information constraint:

i f (X 0 ; X 2 ) ≤ i f (X ′ 1 ; Y, X 2 ) -i f (X ′ 1 ; X 0 , X 2 ) (3.11) with f (x0,x1,x2,y,x ′ 1 )=f X ′ 1 |X 0 X 1 X 2 (x ′ 1 |x0,x1,x2)γ(y|x1)f (x0,x1,x2). X ′
1 is an auxilary variable which helps us exploit the joint typicality between X ′ 1 and X 1 as well as X ′ 1 and X 2 to create coding and decoding schemes.

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

We see that the first theorem provides a full characterization of implementable densities in scenario a. The second theorem, which relies in part on Gel'fand and Pinsker coding [START_REF] Gel'fand | Coding for channel with random parameters[END_REF], provides a sufficient condition for implementability in scenario b; note that, as originally done in [START_REF] Gel'fand | Coding for channel with random parameters[END_REF], we introduce an auxiliary random variable X ′ 1 to describe the information constraint. These theorems therefore allow one to know to what extent a team can coordinate under the assumed information structure. In general, to determine the ultimate performance in terms of average payoff, an optimization problem for the functional W (f ) has to be solved. The constraints are that: f has to be a density function; its marginal over (x 1 , x 2 ) has to be f 0 ; the density f as defined through the considered theorem has to meet the information constraint. In the next subsection, we apply the derived general result to a special case of probability distributions namely, Gaussian probability density functions. This allows one to exhibit a case where the information constraints can be quite easily expressed and to establish an interesting link with the work by Costa on dirty-paper coding [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF].

Gaussian case

Here, we assume that all variables which intervene in the information constraints are Gaussian. Agent 2 is assumed to observe the actions of Agent 1 through an additive white Gaussian noise channel:

Y = X 1 + Z with Z ∼ N (0, 1). Let σ 2 0 , σ 2
1 , and σ 2 2 respectively denote the variances of X 0 , X 1 , and X 2 . The correlation coefficient between X i and X j , i ̸ = j is denoted by ρ ij . Using these notations and specializing (3.10) and (3.11) in the Gaussian case the following results can be proved; proofs are omitted here for obvious space limitations.

Proposition 4 (Information constraint in scenario a). Fix σ 2 0 . A necessary and sufficient condition for a joint probability density function f X 0 X 1 X 2 to be implementable is that the variances and correlation coefficients verify the following inequality:

-(σ 2 2 ρ 2 01 -2ρ 01 ρ 02 ρ 12 + σ 2 1 ρ 2 02 + σ 2 0 ρ 2 12 -σ 2 0 σ 2 1 σ 2 2 ) × (σ 2 2 ρ 2 01 - 2ρ 01 ρ 02 ρ 12 + σ 2 1 ρ 2 02 + σ 2 0 ρ 2 12 -σ 2 0 σ 2 1 σ 2 2 + ρ 2 02 ) ≤ 0.
Proposition 5 (Information constraint in scenario b). Fix σ 2 0 . Let α 2 ∈ R. A sufficient condition for a joint probability density function f X 0 X 1 X 2 to be implementable is that the variances and correlation coefficients verify the following inequality:

(-ρ 2 01 + σ 2 0 + σ 2 0 σ 2 1 ) × (σ 2 2 ρ 2 01 -2ρ 01 + 2α 2 ρ 12 + σ 2 1 ρ 2 02 + σ 2 0 ρ 2 12 - σ 2 0 σ 2 1 σ 2 2 ) -σ 2 0 σ 2 2 (ρ 2 01 -σ 2 0 σ 2 1 + α 2 2 ρ 2 02 -α 2 2 σ 2 0 σ 2 2 + α 2 2 σ 2 1 ρ 2 02 + α 2 2 σ 2 2 ρ 2 01 + α 2 2 σ 2 0 ρ 2 12 - 2α 2 σ 2 0 ρ 12 + 2α 2 ρ 01 ρ 02 -α 2 2 σ 2 0 σ 2 1 σ 2 2 -2α 2 2 ρ 01 ρ 02 ρ 12 ) ≤ 0.
For finding the information constraint for scenario b, we have assumed that

X ′ 1 = X 1 + α 0 X 0 + α 2 X 2 .
This choice is inspired by the Costa's dirty paper coding scheme [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF]. The parameter α 2 is related to the choice we made for the auxiliary variable in Theorem 3 .

As seen through Proposition 5, the value of the parameter α 0 does not play any role in the constraint, showing that only the correlation level between the FUNCTION agents' actions X 1 and X 2 has to be tuned properly. The inequality constraint function of Proposition 5 can be shown to be strictly convex w.r.t. α 2 and the optimum point α ⋆ 2 is given by:

α ⋆ 2 = σ 2 0 ρ 12 -ρ 01 ρ 02 ρ 2 02 -σ 2 0 (σ 2 2 -ρ 2 12 + σ 2 1 σ 2 2 ) + σ 2 1 ρ 2 02 + σ 2 2 ρ 2 01 -2ρ 01 ρ 02 ρ 12
.

(3.12)

When the communication signal-to-noise ratio SNR =

E(X 2 1 ) E(Z 2 ) = σ 2 1 → ∞, it is seen that α ⋆ 2 → 0 and the choice X ′ 1 = X 1 is optimal. When SNR → 0, we see that α ⋆ 2 → σ 2 0 ρ 12 -ρ 01 ρ 02 (ρ 2 02 -σ 2 0 σ 2 2 )+σ 2 0 ρ 2 12 +σ 2 2 ρ 2
01 -2ρ 01 ρ 02 ρ 12 . As an aside, using the Cauchy-Shwarz Inequality one can show that for any 3 correlated random variables, the bounds for ρ 12 are ρ 01 ρ 02

σ 2 0 - √ (σ 2 0 σ 2 2 -ρ 2 02 )(σ 2 0 σ 2 1 -ρ 2 01 ) σ 2 0 ≤ ρ 12 ≤ ρ01ρ02 σ 2 0 + √ (σ 2 0 σ 2 2 -ρ 2 02 )(σ 2 0 σ 2 1 -ρ 2 01 ) σ 2 0
. Thus, one sees that when ρ 01 = σ 0 σ 1 and ρ 02 = σ 0 σ 2 , we obtain ρ 12 = ρ 01 ρ 02 σ 2 0 . This is true for all SNR. Incidentally this is also the condition for both the numerator and the denominator of α * 2 in (3.12) to be zero.

In the case of perfect monitoring, i.e. Y = X 1 , we can show that the information constraint suitably simplified is in fact convex atleast for the special case of X 0 = X 1 . (Proof in 3.5.1).

Other Distributions

Since Theorems 2, 3 can be applied to the random variables following any distribution, it is worthwhile to explicit the information constraints for distributions other than normal. However, both scenarios involve imperfect observations by the second agent. Since the noise model is AWGN, it is difficult to find closed form expressions of the information constraint for the variables not jointly distributed normally. Therefore, in this section, we consider the noiseless case, i.e. Y = X 1 . We consider some other standard distributions which might be useful in modelling other co-ordination problems.

Another difficulty arises due to the inexistence of closed form expressions for entropy for most joint continuous distributions. Amongst the few distributions which do, we also need the property that marginalization w.r.t. any variable gives back the same joint distribution, failing which we might again have the problem of no closed form expression for entropy. Two common distributions which satisfy these constraints (Sec. 3.5) are Multivariate Burr and Multivariate Exponential.

Proposition 6 (Multivariate Burr). When the distribution f (x 0 , x 1 , x 2 ) is a Multivariate Burr with the following pdf (Sec. 3.5):

f (x 0 , x 1 , x 2 ) = Γ(α + 3) Γ(α) c 0 d 0 c 1 d 1 c 2 d 2 x c0-1 0 x c1-1 1 x c2-1 2 (1 + d 0 x c 0 0 + d 1 x c 1 1 + d 2 x c 2 2 ) α+3 (3.13)

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

where α, c i , d i , x i > 0, i ∈ {0, 1, 2} then the Information constraint in the case of perfect monitoring can be written as:

log (α + 1)(α + 2) α - α 3 + 7α 2 + 10α + 2 α(α + 1)(α + 2) +logc 1 d 1/c 1 1 - c 1 -1 c 1 {ψ(α)-ψ(1)} ≤ 0 (3.14)
where ψ(•) is the standard psi function as defined in mathematics literature.

It is interesting to note that the distribution parameters c 0 , d 0 , c 2 , d 2 do not intervene in the information constraint.

Proposition 7 (Multivariate Exponential). When the distribution f (x 0 , x 1 , x 2 ) is a Multivariate Burr with the following pdf (Sec. 3.5):

f (x 0 , x 1 , x 2 ) = α θ 0 e x 0 -λ 0 θ 0 α+1 θ 1 e x 1 -λ 1 θ 1 α+2 θ 2 e x 2 -λ 2 θ 2 (e x 0 -λ 0 θ 0 + e x 1 -λ 1 θ 1 + e x 2 -λ 2 θ 2 -1) α+3
(3.15)

where x i > λ i , α, θ i > 0, i ∈ {0, 1, 2}
then the information constraint in the case of perfect monitoring can be written as:

log (α + 1)(α + 2) αθ 1 - (α 2 + 7α + 7) (α + 1)(α + 2) ≤ 0 (3.16)
Again, interestingly, like in the case of multivariate Burr, the parameters θ 0 and θ 2 disappear from the information constraint.

Application to the Witsenhausen cost function

An important 2-Agent co-ordination problem with continuous action alphabets is the Witsenhausen counterexample (See ?? for a detailed description). The information structure of the problem is similar to the one considered by us. One agent has perfect observation of the nature state, whereas the second agent has noisy observations of the actions of the first agent. For this reason, we consider the Witsenhausen cost (times minus one) as the payoff function to be minimized over a large number of stages and reducing it to a convex optimization problem. We find the limiting performance in terms of coordination for the two-agent team. However, note that this is significantly different from the original Witsenhausen's counterexample [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] as we optimize over many stages with one agent 'knowing' the future realizations of the nature state X 0 . In the original counterexample, the 'informed' agent only knows the current realization of X 0 . Thus, the problem has only one stage and the aim is to minimze the expected cost CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION for that stage. The problem has been of great interest since it was proposed in 1968, especially because it was one of the first examples where actions played a dual role of communicating as well as optimizing, rendering the solution of the optimization problem non trivial. The specific payoff function function we consider in this section equals minus the Witsenhausen cost function that is,

w(x 0 , x 1 , x 2 ) = - [ k(x 0 -x 1 ) 2 + (x 1 -x 2 ) 2 ] , k ≥ 0. (3.17)
Note that the notations used here differ from those used in [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF].

Although this cost function is inspired by Witsenhausen's Counterexample, there are a few very important differences between the application of our theory to the Witsenhausen's Cost function and the Witsenhausen's counterexample. First, we optimise the average cost over a large time period, unlike in Witsenhausen's Counterexample where the one shot expectation value for the cost is minimised. Second, we assume strictly causal knowledge at Agent 2, whereas this is not the case in the original counterexample. To apply our approach to the original problem, albeit in the repeated case, one will need to consider a new scenario with the causality condition relaxed. We tackle the orginial counterexample in the second part of this thesis after developing the theory for the information structure corresponding to Witsenhausen Counterexample.

Numerical analysis

While the optimization problem is well defined, finding the joint distribution f X 0 X 1 X 2 Y = γ(y|x 1 ) * f X1X2|X0 * f 0 is not a trivial task. Eventhough f 0 is defined by the problem and γ(y|x 1 ) can be generated given the noise model, we still need to find f X1X2|X0 , and since the search space is over all possible distributions, the computational complexity of such a search is very high. Therefore, in this section we restrict ourselves to two cases which are simpler to handle, complexity wise, but might be sub-optimal.

Both the cases use the results proven in previous sections for the continuous variables. However for the first case, we use a quantizer to discretise (X 0 , X 1 , X 2 , Y) and optimise over them. This approach is inspired by the success of quantizers in finding better solutions for the original Witsenhausen Counterexample. To compare with a strategy most resembling a 'linear control' strategy, we choose the case where all variables are supposed to be gaussian, for which we had simplified the information constraint in terms of variances and covariances in section 3.2.2. Clearly, it would be interesting to compare the two strategies, to see whether like for Witsenhausen Counterexample, non linear (discretisation) strategies outperform 'linear' (and thus continuous) strategies. This argument is used to motivate our choices of simulations, but the similarities are not so straightforward.

The following parameters are taken to be given for the problem: k = 1, σ 2 0 = 25, and Ez 2 = 1 and are common for both simulations (unless specified otherwise). Also, the information constraint considered is for scenario a.

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

Discrete case : we quantize all random variables to take nine values: 24 7 σ 0 , -16 7 σ 0 , -8 7 σ 0 , -3 7 σ 0 , 0, 3 7 σ 0 , 8 7 σ 0 , 16 7 σ 0 , 24 7 σ 0 }, with σ 0 = 5. Indeed, as we consider the continuous random variable X0 ∼ N (0, σ 2 ), we partition uniformly the continuous space that X0 is defined over, so that 99.99 % of the probability mass function lies in the chosen interval. It is well known that considering the interval [-4σ, 4σ] achieves this. We then calculate the transition probabilities P (Y |X 1 ) where Ỹ = X 1 + Z, Z is supposed to be a Gaussian random variable: Z ∼ N (0, 1), and Y is the discrete random variable that corresponds to Ỹ . This problem is computationally simpler as it is easy to calculate entropies for discrete random variables. The optimization problem can be solved using convex optimization algorithms. We search for the joint distribution over X 0 × X 1 × X 2 which minimizes the expectation of the Witsenhausen cost function. This approach is similar to the one used in [START_REF] Larrousse | Implicit coordination in 2agent team problems. application to distributed power allocation[END_REF], except for the cost function and the information constraint which takes into account the observation noise for Agent 2. It gives us an approximation to the continuous case and valuable ideas as we will explain now. 10dB), the probability is almost 1 for X 1 = 0. This is logical as σ 2 1 = 0.1 and thus Agent 1 does not have too much of a choice. For medium SNR (10 dB), we see the probabilities diverging slightly and resembling a Gaussian distribution. The same distribution is observed from SNR = 14 dB onwards as this leads to minimum cost. This can be seen from the graph of expected payoff vs SNR, Fig 3 .2. At 40 dB, one sees a distribution with higher variance but whether it can be a gaussian is tough to speculate given the lack of points.

X 0 = X 1 = X 2 = Y = {-
The salient feature of this approach is that it does not suppose any distribution for the variables a priori, and thus finds the optimal distribution, which is not necessarily Gaussian. However, it only searches for finite action alphabets, thus not attaining optimality in the general continuous case.

Gaussian Case : Guessing the optimal distributions to be Gaussian, we find a feasible set of variances and covariances which satisfy the information constraint calculated in Section 3. The feasible set is found by quantizing the search space for all the parameters. The search space are as follows: [START_REF] Larrousse | Coded power control: Performance analysis[END_REF][START_REF] Khayutin | Communication with unobservable constraints[END_REF] dB , and ρ 01 , ρ 12 , ρ 02 ∈ (0, (σ 0 σ 1 , σ 1 σ 2 , σ 2 σ 0 )). The other constraints of the optimization problem are trivially satisfied since we are taking all distributions to be probability distributions from the beginning.

σ 2 1 σ 2 z ∈ (-10, 40) dB , σ 2 2 σ 2 z ∈ (-
For a given set of variance and covariance values which satisfy the information constraint, we find the expected payoff by evaluating the integral ´x∈{X 0 ×X 1 ×X 2 } f (x)w(x)dx. We do so using Monte Carlo simulations by randomly generating x 0 , x 1 and x 2 (100000 draws) which follow the joint distribution f (x) and averaging over the cost for the randomly generated triplets. We search over all the elements of the feasible set exhaustively to find the optimal joint Gaussian distribution which optimizes the Witsenhausen cost function. (which could be looked at as Signal to Noise Ratio (SNR)) increases, the expected cost reduces initially and then becomes constant. This is because on the x-axis, we are considering the maximum SNR available, and in both the cases, one sees that after a certain SNR*, the payoff remains constant as the agents choose strategies with SNR*.

Results

We notice that the discrete strategy does better than the continuous gaussian strategy and while this is not conclusive proof, it leads us to suspect that discretisation does better than continuous alphabets, which would be similar to the original Witsenhausen problem where discrete Non-Linear strategies were shown to outperform the best affine strategies. Although this might just be an artefact of gaussian variables being sub-optimal distributions for our problem.

For the Gaussian case, the optimal (σ * , ρ * ) = (σ * 1 , σ * 2 , ρ * 01 , ρ * 02 , ρ * 12 ) was found to be (4.6, 5.3, 4.8, 5.1, 4.9) and the optimal expected cost E(w) * associated with it to be 18.64. The information constraint is numerically found to be saturated for the optimal point. Note that the optimal correlations ρ * are not at their maximum values, given by σ i σ j ≥ ρ ij . This is precisely the information constraint which prevents the correlations to be at their maximum values, thus penalising future communication by Agent 1 and preventing the agents to coordinate better. One sees that the discrete strategy quickly beats the all-gaussian strategy, and achieves a much lower optimal cost Ideally one should be able to do more extensive simulations for the discrete case, so as to get a better idea of the optimal distribution which could then be tackled using an approach similar to the gaussian case. However, the computational complexity prevents us from doing so currently.

Conclusions

We generalized the information constraint for the scenarios discussed in the chapter from a discrete case to a continuous case, showing equivalence between implementable distributions and reachable payoffs. This result is independent of the cost function, but it depends on the strategies and information structures. Thus we created a general framework for tackling problems with similar information structures, as well as showed a method of generalizing information constraint found for discrete cases to continuous ones. We also found an interesting link between scenario b and [START_REF] Costa | Writing on dirty paper (corresp.)[END_REF] which needs to be further explored. Since Witsenhausen cost function is an important area for research, we applied our framework to optimize this cost function in our scenario. While we could not provide simulations which solved the general optimization problem described in the chapter, we did gain some insights by simplifying the problem and reducing the computational complexity.

Further possibilities of exploration include better simulations with other types of distributions to see if they do better than Gaussian distributions, quantizing the alphabets with more points so as to approach continuity, as well as proving our results for other type of strategies and information structures. To compare a repeated version of Witsenhausen counterexample, one would need performance limit characterization with a different Information structure, similar to ones discussed in [START_REF] Larrousse | Coordination in distributed networks via coded actions with application to power control[END_REF].

Appendix

Proof of Convexity of Information constraint for the Gaussian Case

The information constraint in the case of perfect monitoring can be given by substituting Y = X 1 in the theorem 2:

H f (X 0 ) + H f (X 2 ) -H f (X 0 , X 1 , X 2 ) ≤ 0 (3.18)
where f is the joint distribution f (x 0 , x 1 , x 2 ). Assume f to be a multivariate Normal distribution whose pdf is given by:

f (x) = 1 (2π|Σ|) 1 2 e 1 2 x T Σx (3.19)
Σ is the covariance matrix Σ ij = EX i X j Without loss of generality, we can assume the mean vector to be zero as the entropy does not depend on the mean. The entropy for the distribution f is:

H f (X 0 , X 1 , X 2 ) = 1 2 log(2πe|Σ|) (3.20)
Using (3.18) and (3.20) and simplifying, we get the following conditions for the parameters of the distribution f :

P 0 P 2 + 2πe(P 0 ρ 2 12 + P 1 ρ 2 02 + P 2 ρ 2 01 ) -P 0 P 1 P 2 -2ρ 01 ρ 02 ρ 12 ≤ 0 (3.21)
where ρ ij is the correlation between variables X i , X j , i ̸ = j, {i, j} ∈ {0, 1, 2}. and P i is the variance of the variable X i .

To check the convexity of the Information Constraint, we calculate the Hessian of the function w.r.t. the control variables {P 1 , P 2 , ρ 01 , ρ 02 , ρ 12 } in that order. The symmetric Hessian matrix can be expressed as follows:

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION H(IC) =       0 -2πeP 0 0 4πeρ 02 0 -2πeP 0 0 4πeρ 01 0 0 0 4πeρ 01 4πeP 2 -4πeρ 12 -4πeρ 02 4πeρ 02 0 -4πeρ 12 4πeP 1 -4πeρ 01 0 0 -4πeρ 02 -4πeρ 01 4πeP 0       (3.22)
To prove the convexity of the IC function, it suffises to show that the hessian matrix is positive semi-definite. One of the tests to show this is to find the eigenvalues of the above matrix and see their signs.

To analyse the above matrix, let us consider a simpler case:

Case 1 -X 0 = X 1 : In that case, P 1 = P 0 and ρ 01 = (P 0 P 1 ) (1/2) = P 0 . Thus the IC becomes a function of only 4 parameters, one of which is specified by the problem. The hessian matrix thus reduces to 3 × 3 matrix and can be expressed as follows:

H R (IC) =   0 0 0 0 4πeP 0 -4πeP 0 0 -4πeP 0 4πeP 0   (3.23)
If the above matrix has nonnegative eigenvalues then the matrix is positive semi-definite. For H R (IC), the eigenvalues are {8πeP 0 , 0} which are both nonnegative. Thus the hessian of the function is positive semi-definite and thus the Information constraint is convex in this case.

Marginal of a Multvariate Burr distribution

Consider a bi-variate Burr distribution with the following pdf:

f (x 1 , x 2 ) = Γ(α + 2) Γ(α) c 1 d 1 c 2 d 2 x c1-1 1 x c2-1 2 (1 + d 1 x c 1 1 + d 2 x c 2 2 ) α+2 (3.24)
where α, c i , d i , x i > 0, i ∈ {1, 2}

Let us now consider marginalising w.r.t. x 2 and see what we obtain:

ˆx2 f (x 1 , x 2 )dx 2 = ˆx2 Γ(α + 2) Γ(α) c 1 d 1 c 2 d 2 x c1-1 1 x c2-1 2 (1 + d 1 x c1 1 + d 2 x c2 2 ) α+2 dx 2 (3.25) = Γ(α + 2) Γ(α) c 1 d 1 c 2 d 2 x c1-1 1 ˆx2 x c2-1 2 (1 + d 1 x c 1 1 + d 2 x c 2 2 ) α+2 dx 2 (3.26) CHAPTER 3.

CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

To solve the integral, consider the substitution y 2 = x c2 2 . Thus dy 2 = c 2 x c 2 -1 2 dx 2 . The expression thus simplifies to:

Γ(α + 2) Γ(α) c 1 d 1 c 2 d 2 x c 1 -1 1 ˆ∞ y2=0 x c 2 -1 2 (1 + d 1 x c1 1 + d 2 y 2 ) α+2 1 c 2 x c 2 -1 2 dy 2 (3.27) = Γ(α + 2) Γ(α) c 1 d 1 d 2 x c 1 -1 1 ˆ∞ y2=0 1 (1 + d 1 x c1 1 + d 2 y 2 ) α+2 dy 2 (3.28) = Γ(α + 2) Γ(α) c 1 d 1 x c 1 -1 1 d α+1 2 ˆ∞ y2=0 1 ( 1+d1x c 1 1 d2 + y 2 ) α+2 dy 2 (3.29) = Γ(α + 2) Γ(α) c 1 d 1 x c 1 -1 1 d α+1 2   - 1 α + 1 1 ( 1+d 1 x c 1 1 d 2 + y 2 ) α+1   ∞ 0 (3.30) = Γ(α + 2) Γ(α) c 1 d 1 x c1-1 1 d α+1 2 ( 1 (α + 1)
d α+1 2 1 + d 1 x c 1 1 ) (3.31)
= Γ(α + 1) Γ(α) c 1 d 1 x c 1 -1 1 1 + d 1 x c1 1 = f (x 1 ) (3.32)
Thus we can see that marginalisation of bivariate Burr distribution w.r.t. to one random variable gives back the reduced Burr distribution for 1 variable, with the same parameters as the definition of the bivariate Burr distribution. This can easily be generalised for multivariable Burr distributions.

Proof of Proposition 6

Using the expression for entropy of a multivariate Burr distribution [START_REF] Ahmed | Entropy expressions and their estimators for multivariate distributions[END_REF], we can write the information constraint for the case when f (X 0 , X 1 , X 2 ) follow a joint multivariate burr distribution.

CHAPTER 3. CONTINUOUS ALPHABETS -WITSENHAUSEN COST FUNCTION

H(X 0 ) + H(X 2 ) -H(X 0 , X 1 , X 2 ) = -log(α) + (α + 1){ψ(α + 1) -ψ(α)} -logc 0 d 1/c0 0 + c 0 -1 c 0 {ψ(α) -ψ(1)} -log(α) + (α + 1){ψ(α + 1) -ψ(α)} -logc 2 d 1/c 2 2 + c 2 -1 c 2 {ψ(α) -ψ(1)} - ( - 2 ∑ i=0 (log(α + i)) + (α + 3){ψ(α + 3) -ψ(α)} - 2 ∑ i=0 logc i d 1/ci i + 2 ∑ i=0 c i -1 c i {ψ(α) -ψ(1)} ) =log (α + 1)(α + 2) α + 2(α + 1){ψ(α + 1) -ψ(α)} -(α + 3){ψ(α + 3) -ψ(α)} + logc 1 d 1/c 1 1 - c 1 -1 c 1 {ψ(α) -ψ(1)} =log (α + 1)(α + 2) α + 2(α + 1) 1 α -(α + 3)( 1 α + 1 α + 1 + 1 α + 2 ) + logc 1 d 1/c1 1 - c 1 -1 c 1 {ψ(α) -ψ(1)} =log (α + 1)(α + 2) α - α 3 + 7α 2 + 10α + 2 α(α + 1)(α + 2) + logc 1 d 1/c 1 1 - c 1 -1 c 1 {ψ(α) -ψ(1)}

Marginal of a Multvariate Exponential distribution

Consider a bi-variate Exponential distribution with the following pdf:

f (x 1 , x 2 ) = α θ 1 e x 1 -λ 1 θ 1 α+1 θ 2 e x 2 -λ 2 θ 2 (e x 1 -λ 1 θ 1 + e x 2 -λ 2 θ 2 -1) α+2 (3.33)
where x i > λ i , α, θ i > 0, i ∈ {1, 2} Let us now consider marginalising w.r.t. x 2 and see what we obtain:

ˆx2 f (x 1 , x 2 )dx 2 = α θ 1 e x 1 -λ 1 θ 1 α + 1 θ 2 ˆ∞ λ2 e x 2 -λ 2 θ 2 (e x 1 -λ 1 θ 1 + e x 2 -λ 2 θ 2 -1) α+2 dx 2 (3.34)
To solve the integral, consider the substitution y = e

x 2 -λ 2 θ 2

. Thus dx 2 = θ2 y dy. The integral thus simplifies to: FUNCTION

α θ 1 e x 1 -λ 1 θ 1 α + 1 θ 2 ˆ∞ 1 y (e x 1 -λ 1 θ 1 + y -1) α+2 θ 2 y dy (3.35) = (α)(α + 1) θ 1 e x 1 -λ 1 θ 1 ˆ∞ 1 1 (e x 1 -λ 1 θ 1 + y -1) α+2 dy (3.36) = (α)(α + 1) θ 1 e x 1 -λ 1 θ 1 ˆ∞ 1 1 (e x 1 -λ 1 θ 1 + y -1) α+2 dy (3.37) = (α)(α + 1) θ 1 e x 1 -λ 1 θ 1 -1 α + 1 ( (e x 1 -λ 1 θ 1 + y -1) -(α+1) ) ∞ 1 (3.38) = - (α) θ 1 e x 1 -λ 1 θ 1 ( (e x 1 -λ 1 θ 1 + y -1) -(α+1) ) ∞ 1 (3.39)
Note that lim y→∞ (e

x 1 -λ 1 θ 1
+ y -1) -(α+1) = 0 since α > 0. Thus, we get :

- (α) θ 1 e x 1 -λ 1 θ 1 (-((e x 1 -λ 1 θ 1 + 1 -1) -(α+1) )) (3.40) = (α) θ 1 e x 1 -λ 1 θ 1 (e x 1 -λ 1 θ 1 ) -(α+1) = f (x 1 ) (3.41)

Proof of Proposition 7

Using the expression for entropy of a multivariate exponential distribution [START_REF] Ahmed | Entropy expressions and their estimators for multivariate distributions[END_REF], we can write the information constraint for the case when f (X 0 , X 1 , X 2 ) follow a joint multivariate burr distribution.

H(X 0 ) + H(X 2 ) -H(X 0 , X 1 , X 2 ) = -log( α θ 0 ) + 1 -log( α θ 2 ) + 1 - ( -(log( α θ 0 ) + log( α + 1 θ 1 ) + log( α + 2 θ 2 ) +(α + 3)( 1 α + 1 α + 1 + 1 α + 2 - 3 α ) =log (α + 1)(α + 2) αθ 1 - (α 2 + 7α + 7) (α + 1)(α + 2)
Chapter 4

Information theoretical bounds

To know that we know what we know, and to know that we do not know what we do not know, that is true knowledge.

Nicolaus Copernicus

Introduction

In this part we turn our attention to causal information structure. Compared to the previous part, the essential difference is that in this part, no agent is assumed to have a non-causal knowledge of the nature state. In other words, no agent knows what the future holds in store. This assumption is more applicable to real world scenarios as one would be hard-pressed to find applications where the future realizations of the nature state is known with reasonable accuracy to some agent. Not knowing the future realizations removes the information assymetry inherent in the previous part. This has the following ramnifications :

1. While the previous part dealed entirely with coding through actions, also known as implicit communication in the literature, communication between agents does not figure in this part (apart from the application to Witsenhausen Counterexample). This is simply because no agent has any information about the future realizations of the nature state to communicate. In the case where an agent cannot even observe the present realization of the nature state, communication through actions indeed plays a significant role. We briefly discuss this scenario in the application to Witsenhausen Counterexample.

2. Also, throughtout the previous part, we showed that the performance limits of coordination schemes with non-causal information structures are characterized by information constraints on the implementable distrbutions. In this section, since there is no information transfer between the agents, information constraints do not appear in our analysis.

3. In this part, due to the symmetry in the information structure, we consider co-ordination scenarios involving more than 2-Agent teams. This greatly enhances the applicability of the framework developed in this part.

While in the previous part, we contended ourselves with the performance limits of coordination schemes, without ever expliciting them, in this part, we shall attempt to provide practical coordinaton schemes for certain important technological challenges. To this effect, we exploit a recent theorem derived in [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF] to find power control functions which may exploit the available knowledge optimally (in the long run). We devise a decentralized offline algorithm which requires knowledge of the statistics of the nature state X 0 as well as the noisy channels ℸ(S i |X 0 ) of the feedback for each agent. Based on the feedback available to each agent about the nature state, we are capable of devising coordination schemes for any application following the given information structure. We specifically apply our framework to the case of power control schemes in wireless communications for various objectives, as well as co-ordination schemes in Smart Grids to even out the consumption of electrcity during a day.

The key insight in the proposal is that most decentralized decision schemes proposed in literature hinge on game theoretic frameworks, which does not necessarily attemmt to achieve social optimality. This is because co-operation is not assumed while considering Nash Equilibria, and the schemes proposed, though robust and fair, do not use the information avialable to agents to coordinate optimally. Our attempt is to get as close as possible to using the knowledge available at each agent in determining optimal decision functions maximizing co-ordination and thus sum-performance.

In this chapter, we develop this general framework, together with the proposed algorithm to devise practical schemes. Indeed, one of the salient features of the proposed framework is to provide robust decision functions by accounting for noise by incorporating noise statistics while determining the decision functions. In Sec. 4.2, we recall the theorem from [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF] which characterizes the implementable distributions under the information structure considered. We exploit this theorem to devise a sub-optimal algorithm for finding decision functions in Sec. 4.3.

Performance limits of an N -Agent Coordination problem

Consider a coordination problem where N Agents are trying to coordinate their decision X i ∈ X i , i ∈ N = {1, ..., N }. The coordination is done with respect to a nature state represented by X 0 ∈ X 0 with the goal of optimizing a common payoff function w(x 0 , x 1 , x 2 , ...x n ) over a long time period T . The nature state X 0 for applications to wireless communications, for example, could be channel gain coefficients g ij = |h ij | 2 , with g ij being the channel gain of the link between transmitter i and receiver j. X 0 denotes a random nature state which affects the common payoff function for the system and is not controlled by the coordinating agents. The realizations of the nature state X 0,t at each time instant t are i.i.d. and follow a probability distribution ρ. In wireless communications ρ is typically an exponential distribution for each channel gain g ij . Our aim is to characterize all the achievable expected payoffs under this certain information structure over a long time period T , T → ∞.

Firstly, we need to formally define the information structure under consideration. At every instant t, agent i is assumed to have an image or a partial observation S i,t of the nature state X 0,t with respect to which all agents are coordinating. Again, for wireless communications, this could be the knowledge of local Channel State Information at Transmitter (CSIT), i.e. transmitter i observes a noisy version (in general) of only the direct link channel gain g ii . One could imagine other kinds of information available at the transmitters: for example, transmitter i observes all the links g ji , ∀j. The observations S i,t are assumed to be generated by a memoryless channel whose transition probability is denoted by ℸ i (S i,t |X 0,t ). All agents have to make their decision X i,t based on this information received. Formally, the sequence of decision functions for agent i, f i,t , is defined as:

f i,t : S t i × U -→ X i (4.1) (s i (1), s i (2)...s i (t), u(t)) -→ x i (t) (4.2)
where S t i = S i (1) × S i (2)... × S i (t) is the discrete observation alphabet till the instant t and X i is the action chosen by agent i with |S i |, |X i | < ∞. U is the alphabet of the auxiliary variable U which is discussed in more detail later. s i (t), u(t) and x i (t) are the realizations of the corresponding variables at instant t.

The problem is said to be decentralized as each agent chooses its action independently based on the information received by it. Since the nature state is an external random variable, and thus not controled by agents, the quantity to be optimized is the expected objective function:

E Q [w(X)] = ∑ x ∈ X w(x 0 , x 1 , ..., x N )Q(x 0 , x 1 , ..., x N ) (4.3)
where X = (X 0 , X 1 , ..., X N ), x = (x 0 , x 1 , ..., x N ), and X = X 0 × ∏ N i=1 X i . Q(x 0 , x 1 , ..., x N ) is the joint probability distribution of the variables affecting the payoff. An important point to note is that since expectation is a linear operator, optimizing the expected payoff is equivalent to finding the optimal distribution Q(x 0 , x 1 , ..., x N ). However, the optimization problem is not so trivial as indeed there are certain restrictions on the distributions Q that are implementable given the imposed information structure. We now define the notion of an implementable distribution. Definition 6 (Implementability). Let the information structure be as defined in (4.1). The probability distribution Q(x 0 , x 1 , ..., x N ) is implementable if there exist decision functions σ i,t such that as T → +∞, we have for all x ∈ X ,

1 T T ∑ t=1 Q X 0 ...X N ,t (x 0 , ..., x N ) -→ Q(x 0 , ..., x N ) (4.4)
where

Q X 0 X 1 ...X N ,t = Q X1,...X N |X0,i × ρ is the joint distribution induced by σ i,t at stage t.
As seen before, the expected payoff is characterized by the probability distribution Q over all the variables that intervene in the payoff function. Thus, the time averaged expected payoff w is said to be achievable, if and only if the corresponding distribution Q is implementable. The following theorem characterizes the achievable payoffs that are implementable under the information structure (4.1). Theorem 4. [START_REF]Coordinating partially-informed agents over state-dependent networks[END_REF] Assume the random process X 0,t to be i.i.d. following a probability distribution ρ and the available information to the transmitters S i,t to be the output of a discrete memoryless channel obtained by marginalizing the conditional probability ℸ(s 1 , ..., s N |x 0 ) . An expected payoff w is achievable in the limit T → ∞ if and only if it can be written as:

w = ∑ x 0 ,x 1 ,...x N , u,s 1 ,...s N ρ(x 0 )P u (u)ℸ(s 1 , ...s N |x 0 )× ( ∏ N i=1 P Xi|Si,U (x i |s i , u) ) w(x 0 , x 1 , ...x N ) (4.5)
where U is an auxiliary variable which can be optimized and P Xi|Si,U (x i |s i , u) is the probability that Transmitter i, chooses action x i after observing s i , u.

The auxiliary variable U is an external lottery known to the transmitters beforehand, which can in general, be used to achieve better coordination. However, we do not exploit this auxiliary variable in our analysis, and thus we shall omit it in the following analysis for greater clarity.

While theorem 4 provides us with all the achievable payoffs given the information structure defined in equation (4.1), it does not provide optimal sequences of decision functions f i,t that might help achieve this payoff. One of the main aims of this chapter is precisely to provide a procedure to obtain those decision functions with reasonable complexity. To achieve this, certain simplifications and observations need to be made. Firstly, instead of looking for a sequence of functions f i,t , we shall only search for optimal stationary strategies, i.e. f i = f i,t ∀t. This induces no performance loss as the nature state is considered to be i.i.d. for every timeslot, and thus the optimal strategies are also time-independent.

Another important observation is that theorem 4 characterizes all achievable payoffs in terms of conditional probabilities (P X1|S1 , ..., P X N |S N ). However, if one considers the optimal achievable payoff, the conditional probabilities (P Xi|Si simplify to mere functions f i (s i ) due to proposition 8. by the simplification are typically good and easily outperform solutions which guarantee convergence to Nash Equilibria.

To apply best response dynamics, we rewrite the expected utility isolating the sum w.r.t. s i , the observation of agent i.

w = ∑ x0,s1,...s N ρ(x 0 )ℸ(s 1 , ...s N |x 0 )w(x 0 , f 1 (s 1 ), ..., f N (s N )) = ∑ x 0 ,s i ρ(x 0 )ℸ(s i |x 0 ) ∑ s -i ℸ(s -i |x 0 )w(x 0 , f 1 (s 1 ), ..., f N (s N ))
where s -i represents the vector comprising of observations of the agents other than agent i.

To update the function f i (s i ) for agent i, all we need is an action corresponding to each possible observation s i . Thus, for every fixed s i , we need to find the action x i which maximizes the expected payoff. More formally, we define the following quantity

θ(s i , x i ) = ∑ x 0 ρ(x 0 )ℸ(s i |x 0 ) ∑ s -i ℸ(s -i |x 0 )w(x 0 , x i , f -i (s -i )) (4.7)
In essence, this is the expected common utility w.r.t. the nature state x O , if agent i choses the action x i assuming that it knows the decision functions of all other agents f -i (s -i ). The update of the function f i for the observation s i is then simply arg max xi θ(s i , x i ). Updating the function for each possible observation completes the update for an agent, and this procedure is repeated sequentially for other agents. The algorithm is said to have converged if after an iteration, i.e. one round of function updates for all agents, the difference in the functions from the previous iteration and the updated functions is below the tolerance level.

An important point to note is that the transmitters can run this algorithm offline as all they need to know are the channel statistics ρ, and the channel ℸ. This helps in exploiting the decision functions for the entire timeslot during which the nature state remain constant. Thus we exploit the channels from the very start of a timeslot as opposed to taking some time initially to find the optimal functions online. The latter case is considered in some decentralized solutions such as the algorithms based on water-filling techniques proposed in [START_REF] Gohary | Robust IWFA for open-spectrum communications[END_REF], [START_REF] Anandkumar | Robust rate maximization game under bounded channel uncertainty[END_REF]. It is easy to see that this algorithm necessarily converges for a common payoff, as stated in 9 Proposition 9. Algorithm 1 converges for a common performance criteria w(x 0 , x 1 , ..., x N ).

Proof. The result can be proved by calling for an exact potential game property [START_REF] Monderer | Potential games[END_REF] (the argument may hold in the more general case in which the transmitter have different performance criteria).

Algorithm 1: Proposed decentralized Algorithm for finding decision functions for all agents inputs : X i , ∀i ∈ {0, ..., N }, w(x 0 , x 1 , ...x N ), ∀x,

ρ(x 0 ), ℸ(s|x 0 ), ∀x 0 , f init i , ∀i ∈ {1...N } output: f * i (s i , u i ), ∀i ∈ {1...N } Initialization: f 0 i = f init i , iter = 0, iter max = 100 while ∃i : f iter-1 i -f iter i ≥ ϵ AND iter ≤ iter max OR iter = 0 do iter = iter + 1; foreach i ∈ {1, . . . , N } do foreach s i ∈ S i do f iter i (s i ) = arg max xi θ(s i , x i ) using (4.7);

end end end

With these tools in hand, we are ready to tackle some practical co-ordination problems from various domains. While the simplifications made to reduce the complexity might induce some performance laws, we shall see in the next chapter that it still performs better than the decentralized solutions currently proposed by the literature.

Chapter 5

Application to N-Agent team coordination problems

The hallmark of a good theory is that with hindsight, it is evident.

Anonymous

In this chapter, we shall consider few specific applications of the theory developed in Chap. [START_REF] Nash | Equilibrium points in n-person games[END_REF]. In particular, we shall consider 3 applications: 1) Power Control in parallel interference channel for wireless communications 2) Power consumption scheduling for applications in Smart Grids 3) Finding decision functions for the famous Witsenhausen Counterexample. The applications are mutually independent, even though they all rely on the same underlying framework developed in the previous chapter.

Power Control in Wireless Communications

As an application, we treat the well studied problem of optimal power control in interference channels ( [START_REF] Zander | Performance of optimum transmitter power control in cellular radio systems[END_REF], [START_REF] Yates | A framework for uplink power control in cellular radio systems[END_REF], [START_REF] Stanczak | Fundamentals of resource allocation in wireless networks: theory and algorithms[END_REF]) and show that not only does our framework attain various payoffs better or identical to the state-of-the-art, it also provides the optimal power control functions in diverse scenarios. The scenarios considered resemble those of [START_REF] Gohary | Robust IWFA for open-spectrum communications[END_REF], [START_REF] Anandkumar | Robust rate maximization game under bounded channel uncertainty[END_REF]. These works propose ad-hoc solutions for specific utilities but not a generic framework which directly provides a power control function that aims at exploiting the available and arbitrary information as optimally as possible. Indeed our approach is very general and can be used to treat more complex and interesting scenarios, e.g. by considering different common objectives, robust power control taking the noisy communications into account, vectorial optimization for power allocation schemes etc.

Eventhough the framework developed previously is very general and conducive to optimizing different utilities such as sum-rate, sum-throughput, sum-PROBLEMS energy [START_REF] Agrawal | A framework for optimal decentralized power control with partial csi[END_REF], we develop the utility sum-energy utility in detail. This choice is motivated by the increasing importance of energy efficiency for wireless communications, as well as the difficulty for finding appropriate solutions for it. For example, [START_REF] Gjendemsjø | Binary power control for multi-cell capacity maximization[END_REF] showed that binary power control is almost optimal for maximizing sum-rate. [START_REF] Paul De Kerret | Best-response team power control for the interference channel with local CSI[END_REF] later showed that thresholding strategy is optimal for sum-rate utilities if only binary power control policies are considered. We generalize those results for the case of energy-efficiency by proposing a combination of thresholding strategy and channel inverson policy, and show its full relevance in the problem of optimal power control for energy efficient communications.

Indeed, for the case of power control in wireless interference channels, these assumptions have been paid some attention. The necessity of minimizing the information required at the transmitters for coordination led to approaches proposed in [START_REF] Paul De Kerret | Best-response team power control for the interference channel with local CSI[END_REF], [START_REF] Gjendemsjø | Binary power control for multi-cell capacity maximization[END_REF], [START_REF] Gjendemsj | Binary power control for sum rate maximization over multiple interfering links[END_REF]. They consider only local channel state information at the transmitters (CSIT). This is also important for reducing the complexity of the optimizations to be performed. For sum-rate maximization, the scenario considered here is comparable to a single-carrier version of the iterative water filling algorithm (IWFA) [START_REF] Scutari | Asynchronous iterative waterfilling for gaussian frequency-selective interference channels[END_REF]. In the case of sum-energy utility, channel inversion strategy was proposed by [START_REF] Goodman | Power control for wireless data[END_REF], whereas the multi-carrier version of the problem was considered by [START_REF] Meshkati | A game-theoretic approach to energy-efficient power control in multicarrier CDMA systems[END_REF]. Decentralization of the power control, or for that matter for any wireless network design, is the reason why game theory has been extensively applied to such problems [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF]. We thus compare our results to game theoretic equilibria analysis as most of the decentralized optimization literature only guarantees convergence to Nash equilibria.

We structure this section as follows: In 5.1.1, we describe the system model of the power control problem in a parallel interference channel. We then proceed to provide simulation results in 5.1.2 with detailed analysis about various aspects of the algorithm proposed in the case of sum-energy utility.

System Model

Consider N single-antenna Transmitter-Reciever pairs T x i , Rx i , i ∈ {1, 2..., N } communicating over a single-carrier parallel interference channel with the channel coefficients being g ij ∈ G ij , i, j ∈ {1, 2..., N } being the index for Transmitter i and Receiver j respectively. The channel coefficients could take values in the discrete alphabet G ij . The transmitter i transmits at powers P i ∈ P i . Due to the power constraint at every transmitter, the total power consumed by transmitter i should not exceed P max , i.e. P i ∈ [0, P max ]. The utility u i for the pair

T x i , Rx i , is typically a function of SINR γ i = P i g ii σ 2 + ∑ i̸ =j P j g ji .
Without loss of generality, we shall consider σ 2 = 1 henceforth. The SNR P max /σ 2 will be thus regulated by varying P max A well accepted model of statistics for the channel gains g ij = |h ij | 2 is Rayleigh fading. In this model, due to central limit theorem, the real and the imaginary components of h ij follow a normal distribution, and thus the channel gain g ij follows exponential distribution (|h ij | follows a Rayleigh distribution).

CHAPTER 5. APPLICATION TO N-AGENT TEAM COORDINATION PROBLEMS

We also assume that all channel gain distributions are independent of each other and that their realizations are i.i.d.

We shall consider the following common utilities for our analysis.

• Sum-rate: w R (P , g) = ∑ i∈N log(1 + γ i ) ;

• Sum-goodput: w G (P , g) = ∑

i∈N Ω(γ i ) ;

• Sum-energy: w E (P , g) = ∑

i∈N Ω(γ i ) P i .

Typical functions for Ω are Ω(γ) = e -c γ [START_REF] Belmega | Energy-efficient precoding for multipleantenna terminals[END_REF], where c > 0 or Ω(γ) = (1e -γ ) M where M ≥ 1 is the packet length [START_REF] Goodman | Power control for wireless data[END_REF]. In simulations, we chose the former function and further supposed c = 1 as it only changes the optimal solutions by a multiplicative constant. Note that Proposition ?? holds for the above payoffs as we are considering sums of individual payoffs which trivially satisfy the required condition for convergence.

The following table explicits the relation between the input variables for Algo. 1 and the corresponding quantities for the application to power control defined above.

General model Power Control Application

Nature State -X 0 Channel state -(g 11 , ..., g N N ) Decision of Transmitter i -X i Power emitted P i ∈ P i w(x 0 , x 1 ...x N ) w R (P , g), w G (P , g), w E (P , g) ρ(x 0 ) 5.1: Correspondence between the general framework and its application to power control

∏ N i=1 ∏ N j=1 e -g ij , g ij = E(g ij ) ℸ(s i |x 0 ) s i = g ii or s i = g ii f init i f i (s) = P max , ∀s ∈ S Table

Numerical Results

Simulation Setup

For G ij , since the channel coefficients g ij follow exponential distribution, a uniform discrete set is typically not a good representative due to varying probabilities for every representative. In our simulations, for |G ij | = n, we find the representative points such that the interval corresponding to each point has an equal probability 1/n. However, the size of alphabets |G ij | = n, ∀i, j ∈ {1, ..., K} is kept same for all channel gains. The average value for the direct channel gains µ ii = 1, and the interfering channel gains µ ij = 0.3, i ̸ = j, unless otherwise stated. The power levels P i are quantized uniformly in dB in the interval [-30dB, 10dB]. In particular, it is seen that for maximizing sum-energy, the obtained power control function exhibits a threshold under which transmission should not occur for a given transmitter.

While considering no noise in the feedback received at transmitter i, the observation alphabet is considered to be the same a

Features of the Algorithm for applications in Wireless communications

Here, we shall illustrate the salient features of the proposed algorithm for power control applications. To illustrate the features, we will concentrate on the utility sum-energy as it is the most novel and important result found using the algorithm.

• Power Control for different utilities: In Fig. 5.1, we plot the power control functions f i obtained using Algo. 1 for the case N = 2 against g ii the direct channel gain between the i th Transmitter-Receiver pair. We do not consider noise in the channel estimation for the moment, and thus in this case s i = g ii . Three different utilities are considered, sum-rate, sum-energy, and sum-goodput.

For the case of sum-rate, it is known that binary power control P i ∈ {P min , P max } is optimal for 2 Transmitter-Receiver pairs [START_REF] Gjendemsjø | Binary power control for multi-cell capacity maximization[END_REF]. Moreover, as shown in [START_REF] Paul De Kerret | Best-response team power control for the interference channel with local CSI[END_REF], optimal power control functions with only local CSIT (g ii ) amounts to P i (g ii ) = P min if g ii ≤ g * and P i (g ii ) = P max otherwise.

It is reassuring to find that our results verify this. Thus, in the case of sum-rate with local CSIT, we find exactly the same results as state-of-theart.

In the case of sum-energy, we see that all the available power P max is not used. Indeed, even in the case of only one Transmitter-Receiver pair, the optimal power control function is c/g 11 . We see that there is also a threshold value of g ii below which, P i = P min . Above the threshold value, the function is similar to the optimal solution obtained in the case of only one Transmitter-Receiver pair. The threshold function is also seen as solution in the case of sum-packet rate. This is because the utility function is not monotonous w.r.t. SINR. To the best of our knowledge, the power control functions found for sum-energy are new. Solutions in literature do not propose thresholding of power control functions to help reduce interference in case of bad direct channel gains.

• Performance gain w.r.t. Nash Equilibria: As stated before, since our framework is co-operative, it easily outperforms game theoretical solutions which guarantee convergence to Nash equlibria under certain conditions. In Fig. 5.2, we compare the performance of the power control function with that of Nash equilibrium for different SNRs in the case of sum-energy and sum-rate. Thus, on the yaxis we see the relative performance gain (w fw N ash /w N ash in % ) of our algorithm when compared to average payoffs obtained by Nash equilibrium. Current state-of-the-art proposes solutions which converge to the Nash equilibrium. Thus, the solutions are generally not optimal while maximizing common utilities that are sum of the individual utilities. The evaluations for obtaining average expected payoffs was done for 10 6 channel realizations.

• Different feedback : Another salient feature of our framework is its ability to incorporate different kinds of feedbacks available at transmitters. This helps in analyzing various possible feedbacks which could help improve the performance. However, the possible additional information at transmitter does come at a cost, and we do not analyze the tradeoff involving this communication cost and the performance gain. Also, we see that additional feedback does not bring significant performance gain.

The more informed choice evidently brings some gain in payoff, as seen from Fig. 5.3. However, suprisingly we see that there is very little difference between the feedback being the vector g ji ∀j ∈ {1, ..., N } and just the direct channel gain g ii . This could be explained by the fact that the decision function f j (g 1j , ...g N j ) for user j, j ̸ = i does not depend on g ji . Thus the additional information does not help in better coordination and we obtain similar payoffs.

We also see that distributed decision making knowing the global CSI g ij ∀i, j ∈ {1, ..., N } performs almost at centralized social optimum. Centralized social optimum is found through joint exhaustive search for the PROBLEMS Relative performance gain (w fw N ash /w N ash in % ) of our algorithm when compared to average payoffs obtained by Nash equilibrium for sum-rate and sum-energy. The curve for sum-energy saturates as at high SNR, P max is not utilized as power emitted is much lower. optimal power levels for every realization of channel coefficients. This is again an indication of the 'goodness' of our proposed distributed algorithm.

For a loose lower bound, we consider the case of no feedback to the users. In the absence of channel feedback but knowing the channel statistics, each user naively chooses the power level which maximises their utility on an average assuming no interference. This power level , in the case of energy efficiency u EE , corresponds to 1/µ ii which is the mean of the direct channel coefficient g ii .

• Robustness to Noisy Feedback : One of the advantages of our framework is that it provides optimal power control functions even for noisy channel estimates. We illustrate this in Fig. 5.4 where power control functions for different levels of noise in channel estimation are plotted. This noise simulates the error in estimation due to noise during feedback transmission, or just simply estimation error of the channel state at the receiver. The noise for the simulations is gaussian, i.e. ĝii = g ii + z where Z ∼ N (0, σ 2 z ), with σ z ∈ {0, 1, 3}. Notice that since the alphabet G ii is discrete, whereas the noise is continuous, we requantize the noisy feedback with the same

s i = g ii P i σ z = 0 σ z = 1 σ z = 3 Payoff = w E Figure 5
.4: Influence of channel estimation noise on the power control functions. We see that as noise increases, the optimal power emitted becomes more uniform. This is intuitive as higher the noise, higher the uncertainty in the observation leading to same power emitted for all channel gains observed in the asymptotic case. alphabet i.e. S i = G ii .

As expected, the power control functions become more uniform at higher noise levels, as the information received is less reliable, and thus transmitters emit at a power level which maximizes the utility after averaging over the uncertainty in observation due to the noise.

• Robustness to noisy estimation of channel statistics : So far, we have assumed that the channel statistics µ ij ∀i, j ∈ {1, ..., K} are known perfectly to everyone. In reality, this might not be the case due to many reasons: error in estimation of the channel, added noise during the communication of statistics being a few. To see the influence of this error, we run our algorithm intentionally using erroneous statistics

µ ij = µ ij (1 + Z).
Here Z is akin to percentage error in the estimation of channel statistics, with z = n corresponding to 100n% error in estimation.

We see form the Fig. 5.5, the average payoff drops off only slightly for positive Z, i.e. if one overestimates the channels. However, interestingly, if one underestimates the channels, the average payoffs are considerably less. This might seem strange at first glance, but closer inspection of the power control functions for the different cases clarifies the reason for this phenomenon.

From Fig. 5.6, we see that the threshold value for g ii , above which the

µ ii est =µ ii (1+z), µ ij est =µ ij (1+z) µ ii =1, µ ij =0.3
Figure 5.5: Influence of error in estimation of channel statistics on average payoff. We see that negative error in statistics (underestimation of channels) leads to worse payoffs than positive error.

transmitter emits, is lesser in the case of negative Z (underestimation). Moreover, since the chosen power levels are roughly equal to 1/g ii , transmitter emits at a very high power level creating high interference. On the other hand, in the case of positive Z, while the threshold is higher, the chosen power levels are not much different, and thus there is less loss in performance.This indicates that its better to overestimate the channel statistics than to underestimate it.

Analysis of the algorithm

• Discrete alphabets G ij , P i : Now we shall analyze the influence of discretization of feedback S i , as well as Power levels P i on the average payoff obtained for our algorithm. Indeed, the complexity of the algorithm is sensitive to the size of these alphabets. Here, we show that the restrictions on the alphabets being discrete and small induce virtually no loss in optimality when compared to much finer discretizations. Furthermore, the small alphabet provides greater robustness against uncertainty in the observations and estimations; i.e. noise in feedback, and higher error in estimation of channel statistics.

For the simple case where number of Tx-Rx pairs , N = 2, we did Monte-Carlo simulations for the functions found using the Algo. 1 while changing It provides an explanation for the greater payoff loss due to underestimation of channel statistics (negative z). We see that the threshold λ i due to negative error is smaller. This results in higher power emited P i which causes interference with other users. the cardinality of P and G ij . The cardinality was changed so as to conserve the equal probability quantization, but also have a nested structure. This was done to see the true effects of finer discretization. Without doing so, the difference in the elements of alphabets G ii could blur the general trends.

There are mainly 3 arguments in favour of discrete alphabets chosen by us:

1. Due to the payoff function -As shown in [START_REF] Gjendemsj | Binary power control for sum rate maximization over multiple interfering links[END_REF], for certain utilities, notably sum-rate, only Binary power control is optimal or quasioptimal depending on the number of pairs. For sum-rate, the number of required power levels is just 2, {P min , P max }.

2. Feedback noise -In practical scenarios, the feedback received is noisy. One way to mitigate the noise is to quantize the feedback alphabet set. We see from Fig. 5.4 that the power levels chosen for different feedbacks g ii is more uniform at higher noise levels. This points at both, less quantization points for the feedback, as well as less number of power levels to choose from.

3. Statistical estimation noise -In addition to the feedback noise, the channel statistics might not be perfectly known either. We again see that having a small alphabet set (G i i, P i ) indeed helps in ensuring against the possible error in estimation. We illustrate this in Fig. 5.7, which is interesting for many reasons. Firstly, it illustrates the robustness of our algorithm. Even in the case of z = 1 which corresponds to 100% error in estimation, the achieved payoffs are comparable to the case with no noise in estimation. Secondly, with more error in estimation, one requires a smaller feedback alphabet set to reach optimal performance. From Fig. 5.8, we see that the required card(P i for achieving 'good' payoffs is very less too ≈ 20. This, along with Fig. 5.7, shows that the alphabets G ii , P i can be discrete and small without inducing much performance loss.

While in slightly more complex cases (multi-carrier, multi-user scenarios), the required alphabet sizes may be higher, we argue that due to the multitude of reasons discussed and illustrated, one expects a small enough alphabet suffices for achieving 'good' payoffs.

• Complexity : The distributed nature of the algorithm helps in reducing the complexity of the search for optimal functions. For the noiseless case, the complexity of the algorithm is O(K.card(P i )card(G ii ) K 2 ). We see that it is exponential w.r.t. number of users K. While this is considerably less than the case of centralized optimization, it is still prohibitive when there are many users. To get around this issue, we firstly observe from Fig. 5.9 that the solution found using our algorithm is a combination of two strategies; thresholding and channel inversion from [START_REF] Goodman | Power control for wireless data[END_REF]. We see that unlike PROBLEMS The number of Power levels required to achieve comparable payoffs to many more power levels can be seen. It can be seen that around 20 power levels are enough for providing reasonable payoffs. .9: Our algorithm reveals the shape of good power control functions in the presence of interference. In contrast with related works on energy-efficiency [START_REF] Goodman | Power control for wireless data[END_REF], our work shows that thresholding is required to manage interference efficiently.

µ ii est =µ ii (1+z), µ ij est =µ ij (1+z) µ ii =1, µ ij =0.3
µ ii est =µ ii (1+z), µ ij est =µ ij (1+z) µ ii =1, µ ij =0.3
[1], we find a threshold below which emitting no power is more optimal, and over which the function closely follows the channel inversion suggested by [START_REF] Goodman | Power control for wireless data[END_REF].

Therefore, we use the intuition given by the power control policy found using the algorithm to propose the following simple continuous power control policy.

P λ i i = { 0 if g ii ≤ λ i αi gii if g ii ≥ λ i (5.1)
Using the thresholding policy, we can reduce the complexity for the search much further. In Fig. 5.10 we compare the scalability of thresholding strategy (5.1) and Nash equilibrium. Unsurprisingly, we see that our policy scales much better than Nash Equilibrium as we increase the number of TX-RX pairs. Indeed, one can show that for Nash Equilibirum, as K → ∞, Ew → 0. This proves the merit of thresholding strategy for sumenergy payoff. However, we cheated slightly here by assuming symmetric channel statistics for all TX-RX pairs which makes finding the optimal threshold very simple. In the assymetric case, exhaustive search can have prohibitve complexity beyond 3 TX-RX pairs. We see that as number of Tx-Rx pairs increase, thresholding strategy does increasingly better, whereas Nash equilibrium payoff falls to 0

Concluding Remarks

The proposed framework was shown to be relevant in diverse scenarios of single band interference channel for finding optimal power control functions. Moreover, the power control functions depend only on local CSIT, thus having the merit of being implementable in a completely decentralized manner. Also, the solutions obtained take noise in the estimation of the channel gain into account. All the above features illustrate the generality of our approach in tackling problems of power control for maximizing sum-utility functions.

However, the framework can be exploited further for tackling other problems in wireless communications as well. For example, one could consider the problem of power allocation in a multi-band interference channel. Also, the auxiliary variable U was not exploited, which in general will only make the solution more optimal. Also, the thresholdng strategy could be analyzed better so as to be robust w.r.t. noisy feedback.

Appendix

Calculation of optimal power control function for 1 user for Energy Efficiency Consider a general energy efficiency utility function u i = Ω(γi)

Pi .

At the optimal point:

∂u i ∂P i = 0 =⇒ ∂ ∂P i Ω(γ i ) P i = 0 =⇒ 1 P 1 -Ω(γ i ) P 2 i + ∂Ω(γ i ) ∂γ i ∂γ i ∂P i = 0
Thus, with just one Tx-Rx pair, there exists a γ ⋆ 1 , the solution to the equation γ ⋆

i Ω ′ (γ ⋆ i ) -Ω(γ ⋆ i ) = 0, which maximises its utility. Now, consider a specific throughput function -Ω(γ i ) = e -c γ i . For this case, we find that γ ⋆ i = c. Thus, the optimal power control function is simply P i = cσ 2 gii .

Nash Equilibrium Calculation -k=2

At the equilibrium point, by definition of Nash Equilibrium, Transmitter i does not gain anything by changing his transmitted power P i , assuming the other player plays P 2 . Thus

∂u i ∂P i = 0 =⇒ ∂ ∂P i f (γ i ) P i = 0 =⇒ 1 P 1 -f (γ i ) P 2 i + ∂f (γ i ) ∂γ i ∂γ i ∂P i = 0
To proceed further, we assume the utility function to be of the form f (γ i ) = e -c γ i . The 'best response' P 1 for a given P 2 can thus be derived as follows:

cf (γ i ) -γ i f (γ i ) P 2 i γ i = 0 =⇒ γ i (P eq 1 , P 2 ) = c P eq 1 = c(σ 2 + P 2 g 21 ) g 11 (5.2)
Now, by symmetry, we know that P eq 2 = c(σ 2 +P1g12)

g22

. Substituting P eq 1 in the place of P 1 (because at equilibrium, both would play their equilibrium values), we get: PROBLEMS Clearly, depending on the realisations of g ij and the constant c, one of the players might exceed the maximum powerP max] , in which case the other player will play its best response power to attain its γ * . Same logic applies if P eq i < 0.

P eq 1 = cσ 2 (

Power Consumption Scheduling functions for

Smart-Grids

Introduction

In this section, we shall divert our attention to the problem of power consumption scheduling functions for Smart-grids, which is also essentially a problem of co-ordination among the consumers to achieve certain common goals for the loads on the electricity distribution networks. With the advent of Smart Grids, it has become possible to send information via the network to the appliances and consumers and vice versa. The information thus generated and relayed could be used to schedule the consumption of electrcity (for charging or using appliances) in order to mitigate the effects of uneven consumption on the network. An important problem for modern electrical networks is to design intelligent strategies for use of electrical appliances (Electric Vehicles (EV) being an example) which are able to exploit the knowledge they have about the non local demand or the electricity price to reach a certain objective. The objective can be to reduce the impact of electricity consumption on the distribution network or to minimize the monetary charging cost paid by the consumer. The most standard approach is to design a charging scheme which assumes a perfect knowledge of the non local demand (or price) and evaluate the performance of the corresponding algorithm by feeding the latter with a forecast or noisy version of the non local demand. Illustrative and recent examples of this approach are given e.g., by [START_REF] Mohsenian-Rad | Autonomous Demand Side Management Based on Game-Theoretic Energy Consumption Scheduling for the Future Smart Grid[END_REF] [55], [START_REF] Gan | Optimal decentralized protocol for electric vehicle charging[END_REF], [START_REF] Beaude | Composite charging games in networks of electric vehicles[END_REF]. In the quoted references, the energy need of a given user is computed by assuming perfect knowledge of the electricity price or the exogenous demand namely, the part of the demand which is not controlled by the smart consuming devices. The obtained power scheduling schemes have essentially or exactly the water-filling structure i.e., that holes in terms of price or demand are exploited in the first place. One of the drawbacks of this approach is the potential lack of robustness of the designed algorithm to imperfect forecast.

Among existing works which take uncertainty into account in the design of power scheduling scheme we find in particular [START_REF] Kim | Scheduling power consumption with price uncertainty[END_REF]. Therein the authors propose a threshold-based scheduling policy which accounts for past and current prices and the statistics of future prices; each appliance consumes according to a rectangular profile and starts consuming when the price is below a time-varying threshold ("threshold policy"). In [START_REF] Kim | Scheduling power consumption with price uncertainty[END_REF] the price values are assumed independent from the load level in each time slot while this assumption is relaxed in [START_REF] Samadi | Tackling the Load Uncertainty Challenges for Energy Consumption Scheduling in Smart Grid[END_REF].

Additionally, in the latter reference the authors also consider uncertainty in the algorithm design part but the uncertainty concerns load and user energy consumption needs, and not prices as in [START_REF] Kim | Scheduling power consumption with price uncertainty[END_REF]. Another example of relevant work where price uncertainty is considered in real-time demand response model is [START_REF] Conejo | Real-time demand response model[END_REF]; therein robust optimization is exploited. In [START_REF] Deng | Load Scheduling With Price Uncertainty and Temporally-Coupled Constraints in Smart Grids[END_REF], the problem is addressed by stochastic gradient based on the statistical knowledge of future prices.

To our knowledge, there is no contribution in the literature related to the present work which treats the problem of optimality of a power consumption scheduling scheme under given arbitrary imperfect observation or forecast. We use the results developed in Chap. 4 to apply to the model proposed in Sec. 5.2.2. This provides us with suboptimal but typically good power consumption scheduling schemes to be determined numerically. A thorough analysis on very practical scenarios is done in Sec. 5.2.3. In Sec. 5.2.4, the main assets of the proposed approach are summarized and several extensions to address its limitations are provided.

Proposed system model

We consider a set of K ≥ 1 smart electrical appliances. Each appliance aims at scheduling its power consumption to maximize a certain payoff function, which is provided further. To this end, it exploits the available knowledge about a state which affects its payoff. In this application, this state is the exogenous load namely, the part of the load which is not controlled by the smart consuming devices but the proposed model and derived results can be directly used for other types of states such as the electricity price. To define the exogenous load and other key quantities such as the power consumption vectors, we need to specify the timing aspect. Time is assumed to be slotted in stages t ∈ {1, ..., T }. Typically, a stage may represent a day and T may represent the number of days over which the payoff is averaged. At the beginning of stage t, appliance k has to choose a power consumption vector x k = (x k,1 , ..., x k,N ). For example, N = 24 if a stage is a day and comprises 24 time-slots whose duration is one hour. The choice of consumption vector should exploit perfect observations of the past exogenous load vectors x 0 (1), ..., x 0 (t -1) (note that x 0 (t) is a vector of size N ) and a signal which is an image or forecast of the system state and appliances actions at stage t; this signal is denoted by s k ∈ S k . For example, such a signal may be a forecast of the exogenous load or the total load, the total load being equal to the sum x 0 (t) + ∑ K k=1 x k (t). For k ∈ {0, 1, ..., K}, the set in which x k lies is assumed to be discrete and is denoted by X k . This choice is not only motivated by the fact that both power and time can be discrete in real systems, but also to obtain a solution robust against forecasting noise; the latter issue has been addressed recently in [START_REF] Beaude | Reducing the Impact of EV Charging Operations on the Distribution Network[END_REF] where rectangular consumption profiles typically perform better than continuous profiles.

The computational complexity of the algorithm proposed in Sec. 4.3 depends on the cardinality of the set X 0 (the set in which the exogenous load lies). In general, assuming X 0 to be discrete amounts to approximating the exogenous load vectors. To obtain a good approximation, we propose to apply the principal PROBLEMS

General model

Power consumption scheduling Nature State -X 0 PCA analysis of R L Decision of Agent k -X k Starting time to charge w(x 0 , x 1 ...x K )

Joule Losses or Transformer Ageing ρ(x 0 )

Based on empirical data and PCA analysis ℸ(s k |x 0 ) DMC with transition probability to nearest neighbour under L 2 norm Table 5.2: Correspondence between the general framework and its application to power consumption scheduling component analysis (PCA) [START_REF] Mallat | A wavelet tour of signal processing[END_REF] on exogenous load vectors. The exogenous load vector for stage t is approximated as follows:

x 0 (t) = µ L + M ∑ i=1 a i (t)v i (5.4)
where µ L is defined by

µ L = 1 L ∑ t∈L x 0 (t) , (5.5)
L being a set of L samples which is available to estimate µ L ; typically, it may correspond to data measured during the preceding year. The vectors v i are the eigenvectors of the following matrix

R L = 1 L ∑ t∈L [ x 0 (t) -µ L ] [ x 0 (t) -µ L ] ′ (5.6)
where the notation [ . ] ′ stands for transpose. One of the advantages of using such a decomposition is that for a given number of basis vectors M (the basis is then

(v 1 , • • • , v M )
), the quality of approximation is maximized; more specifically, the expected distortion E X 0 -X 0 2 is minimized. To minimize the latter quantity we will exploit the Lloyd-Max algorithm [START_REF] Lloyd | Least squares quantization in pcm[END_REF] in the numerical analysis; it will be applied to the vector a = (a 1 , ..., a M ). We trace the average normalised distortion 1 L ∑ t∈L ∥x 0 (t)x 0 (t)∥ 2 /∥x 0 (t)∥ 2 against the number of basis vectors M that we use in our modeling of X 0 to find a 'good' value for M . x 0 (t) = µ L + ∑ M i=1 a i v i where a is arg min a ∥x 0 (t)µ L -∑ M i=1 a i v i ∥ 2 using convex optimisation algorithms. As we see from Fig. 5.11, the average distortion is more sensible to a few basis vectors v i . Thus, by accepting a distortion of 5%, we can reduce the basis space from 15 to 4 which enables us to model X 0 with fewer coefficients a and reasonable accuracy.

Based on data for year 2013 from Pecan Street database [16]

Figure 5.11: Average normalised distortion against number of basis vectors chosen. We see that 4 vectors are enough to approximate X 0 for an error tolerance level of 5%.

The stage or instantaneous payoff function of appliance k is denoted by u k (x 0 , x 1 , ..., x K ). In the simulations we will assume that u k can be written as

u k (x 0 , x 1 , ..., x K ) = ∑ N n=1 u k,n ( x 0,1 + ∑ K k=1 x k,1 , • • • , x 0,n + ∑ K k=1 x k,n ) (5.7)
where n is the index for the hours of the day and u k,n is the consumption . Note that the cost function is not instantaneous inside a stage, but for a given day as seen from the equation 5.7. The function u k,n can e.g., represent the price charged to the consumer, Joule losses, battery aging, or distribution transformer aging at time-slot n. To define the average payoff of appliance k which is the function to be maximized by appliance k, the key notion of power consumption scheduling strategies needs to be defined. A strategy for appliance k is a sequence of mappings which is defined by:

σ k,t : X t-1 0 × S k → X k (x 0 (1), ..., x 0 (t -1), s k (t)) → x k (t) (5.8) PROBLEMS
The average payoff of appliance k is then defined by

U k (σ 1 , ..., σ K ) = E [ 1 T T ∑ t=1 u k (X 0 (t), X 1 (t), ..., X K (t))
] .

(5.9)

The expectation operator is used since the load is typically considered as a random process. Thus in full mathematical generality, the appliances decisions have also to be considered as random processes. The two main technical problems we address in this paper are the characterization of achievable average payoffs when T grows large and the determination of a practical scheme which provides good performance. Note that we assume a general structure for the knowledge s k . Indeed, we assume that (s 1 , ..., s K ) are the outputs of a general discrete memoryless channel (see e.g., [START_REF] Cover | Elements of Information Theory[END_REF] for more details) whose conditional probability is Γ(s 1 , ..., s K |x 0 , x 1 , ..., x K ). Create X 0 -For good modeling of the given data to create accurate X 0 , we do PCA analysis of R L as explained in section 5.2.2. We thus obtain M 'significant' vectors. We then find the continuous vectors a C (t) which lie in the set R M and minimise the distortion ∥ X 0 (t) -X 0 (t)∥ 2 , for every day t. We discretize the continuous alphabet using vectorial Lloyd max algorithm, with the a C (1), ..., a C (t) and specifying the number of points for quantization. The representatives thus generated is our alphabet X 0 .

Create noise model -Since we evaluate the average payoffs for white Gaussian noise x 0 + z, where Z ∼ N (0, σ 2 I), whereas our algorithm uses a DMC channel Γ, the probability of error due to the noise should be taken into account in the algorithm. To reduce the complexity, it is assumed as a first approximation that only the closest neighbour of X0 in terms of the Euclidean norm ∥.∥ 2 can be gotten by error as the approximation of exogenous profiles which should have been approximated by X0 . To estimate the probability of error, 100 draws of a white gaussian noise are added to the realizations of a training set of the exogenous load over {1, • • • , T } and the number of times when a realization leads to the closest neighbour instead of the right approximation are counted. Then, the probability of error is estimated as the ratio of this number of errors over the number of times when a given element of X 0 should have been chosen.

Numerical Analysis

Simulation setup

The simulation setup assumed here by default corresponds to a Texan district in 2013 in which the smart electrical appliances are electric vehicles. A stage is a period from 8 am a given day to 8 am the day after: there are N = 24 time-slots of 1 hour each. The power consumption of the smart electrical devices will be scheduled only during the "nighttime" corresponding here to the period 5 pm -8 am the next day, i.e. n ∈ {10, • • • , 24}. The whole time period is then {1, • • • , T = 365}. Data corresponding to the exogenous profiles (x 0 (1), • • • , x 0 (365)) are obtained from the Pecan Street database [START_REF]Public data basis. Pecan Street energy data (Texas)[END_REF]. To get a realistic profile at the scale of a district, we sum the hourly consumption data available for Texan households and normalize the aggregated profile as explained a little further. We verified using clustering algorithms of Matlab (function kmeans) that on an average over 3 years, the real consumption of the aggregated profile in summer and winter were considerably different. Winter corresponds to [START_REF] Goodman | Power control for wireless data[END_REF]120] ∪ [301, 365] and summer to [121, 300] Thus we chose to only run the simulations for summer, with some tests for winter to see if the results of summer conform with those of winter.

In the case of EV charging, the strategy sets X k are constrained by the mobility parameters and the charging need. Based on a recent French survey [START_REF]Public data basis[END_REF], the arrival µ a k , departure time µ d k and number of time-slots needed to charge C k are taken to be the closest integers of realizations of Gaussian random variables µ a k ∼ N (2, 0.75), µ d k ∼ N (14.5, 0.375) and C k ∼ N (2.99, 0.57). Motivated by battery aging consideration [START_REF] Gan | Stochastic distributed protocol for electric vehicle charging with discrete charging rate[END_REF], it is furthermore assumed that charging profiles are rectangular: charging is done at a constant rate, here 3kW, and cannot be stopped. Note also that profiles without interruption are even required in some important scenarios encountered with home energy management [67][68]. A strategy is then define only by the time to start charging and the strategy set is reduced to

X k = {µ a k , • • • , µ d k -C k + 1}
, the potential time to start charging. One important assumption in our analysis is the memorylessness of the payoff function. Regarding the instantaneous payoff function, two cases will be distinguished. The first considers a "memoryless" payoff with u k (x 0 , x 1 , ...,

x K ) = - ∑ N n=1 (x 0,n + ∑ K k=1 x k,n ) 2
. This is convenient to express Joule losses or a price charged to the consumer depending on the total load at the scale of the district as in [START_REF] Mohsenian-Rad | Autonomous Demand Side Management Based on Game-Theoretic Energy Consumption Scheduling for the Future Smart Grid[END_REF]. The second corresponds to payoffs "with memory", which means that u k,n depends on the whole past of the total load (x 0,1 + ∑

K k=1 x k,1 , • • • , x 0,n + ∑ K k=1 x k,n
) as opposed to only on the current load x 0,n + ∑ K k=1 x k,n . In the context of a distribution network, such a cost can be transformer aging. To be very brief, the most influential parameter for the transformer aging is known to be the hot-spot (HS) temperature [START_REF]Guide for loading mineral-oil-immersed transformers[END_REF]. Indeed, the transformer isolation damage is directly related to the HS temperature: aging is exponentially accelerated (decelerated) when the HS temperature is above (resp. below) its nominal value [START_REF]Guide for loading mineral-oil-immersed transformers[END_REF]. This is mathematically translated as

u k,n (x 0,1 + K ∑ k=1 x k,1 , • • • , x 0,n + K ∑ k=1 x k,n ) = e 0.12×F HS t (x0,1+ ∑ K k=1 x k,1 ,••• ,x 0,n + ∑ K k=1 x k,n ))-11 , (5.10)
which provides the instantaneous aging relatively to the nominal case. The transformer HS temperature evolution law F HS t , which has a memory, is assumed to follow the ANSI/IEEE linearized Clause 7 top-oil-rise model, which is described in [START_REF] Rivera | Acceptability of four transformer top-oil thermal models: Pt. 1: defining metrics[END_REF]. To make the simulations reproducible we provide the values of the different parameters of F HS t : ∆ t = 0.5 h; T 0 = 2.5h (thermal inertia) for all simulations concerning the transformer, γ = 0.83; R = 5.5; ∆θ O FL = 55 C; ∆θ HS FL = 23 C. The initial parameters for this dynamics with memory are PROBLEMS assumed to be the same from one stage to an other given that the transformer temperature has enough time to converge to the same value at 5 pm for different values of this temperature at the beginning of the day at 8 am. in a given season. These are set to θ HS 0 = 37 C and x 0,9 = 30W (resp. θ HS 0 = 75 C and x 0,9 = 87W) in winter (resp. summer). Defining a larger number of periods than the two (winter and summer) seasons with initial parameters for each period could improve the accuracy of the estimation of the transformer lifetime but would need more data to approximate the exogenous load. With these parameters, the exogenous load is normalized such that without EV the transformer lifetime (inversely proportional to the average aging) is 40 years (standard value for nominal conditions).

The functions found using our algorithm and iterative Water Filling algorithm are applied to a noisy version of data for exogenous load (Summer 2013) and real costs are calculated assuming that the vehicles use the decision functions given by the respective algorithms. Note however, that we suppose that the vehicles already know the statistics for the future. The knowledge of future statistics was also assumed in [START_REF] Kim | Scheduling power consumption with price uncertainty[END_REF]. We use some typical values for Forecasting Signal to Noise Ratio FSNR, namely FSNR = 7dB as used in [START_REF] Kim | Scheduling power consumption with price uncertainty[END_REF] to be coherent with the literature. FSNR is defined as FSNR = 10 log 10

( 1 σ 2 day 1 N T T ∑ t=1 N ∑ n=1 X 0,n (t) 2 )

Simulation Results

In our results, we distinguish 2 kinds of vehicles, informed vehicles and uninformed vehicles. By informed vehicles, we mean vehicles who receive a signal corresponding to the exogenous demand X 0 (t) and take their decisions accordingly, whereas the uninformed vehicles recieve no signal, and thus follow a 'plug and charge' policy, since they have no information. The total number of vehicles for the simulations was kept constant at 10. We chose to plot relative payoff loss (u total /u noEV ) -1, which measures the payoff loss when compared to the case of no EV.

In Fig. 5.12, there are 2 key messages: 1) Algo 1 is much more robust to noise, infact in Fig. 5.12, the curves for 2 different noise levels merge. IWFA however is sensible to noise, which is not surprising. Since we impose rectangular charging profiles on the vehicles, they will not react to noise since it might just be a transient optimal period to charge. 2)We see that as the number of informed players increase the difference between our algorithm and iterative Water filling algorithm (IWFA) increases.

In Fig. 5.13 we see that the general trend discussed for Fig. 5.12 is true irrespective of the year. Moreover all the 3 years show similar patterns, thus showing that the good performance at higher penetration is not by chance. We could not test for more years as that information is not available in a similar format.

We see in Table 5.3 that the ratio between the average costs of Algo 1 Figure 5.12: Relative payoff loss (u total /u noEV ) -1 in percent) against penetration percentage. For more discussion on the choice of this metric refer to [START_REF] Beaude | Reducing the Impact of EV Charging Operations on the Distribution Network[END_REF]. This figure illustrates the robustness of our approach as well as increased importance at higher penetration rates. and IWFA decreases as the number of vehicles increases. This implies that as the number of vehicles increases, Algo 1 does increasingly better than IWFA. Moreover, the same pattern is observed for the cost function taken to be Energy losses. This vindicates our claim that the algorithm proposed by us is generic and could be applied to any cost function to provide 'good' strategies.

Since the cost also depends on the need d which represents the needs of the electric vehicles, we generated d using the general statistics for demand observed. We generated 3 d vectors independently with the same distribution, and found that all the results discussed above hold. Same is true for the winter periods as defined in the simulation setup. All the following tests of robustness show the general nature of our approach.

Concluding remarks

Numerical results show the full relevance of the proposed PCA-based model. Remarkably, an accurate approximation can be obtained by using only a few eigenvectors and applying the Lloyd-Max algorithm on the weights to be applied to these eigenvectors. The proposed framework to characterize the best performance of power consumption scheduling exploits a very recent result in information theory and also allows to derive robust scheduling functions. Simulations show that in the presence of uncertainty on the exogenous load forecast, the obtained functions outperform iterative Water-Filling based schemes. Most importantly, we provide a general framework which can be applied to various scenarios, and guarantees electric vehicle using functions achieving good performance for every scenario.

The proposed framework can be extended. While the discrete alphabet assumption seems like a good assumption to obtain robust scheduling schemes, the i.i.d assumption on the exogenous load would need to be relaxed e.g., into a milder assumption such as a Markovian process, the i.i.d. assumption being made for the performance characterization theorem. Another direction to further improve performance is to maximize the expected payoff jointly and not by using a distributed algorithm. A more accurate study with mobility data from Texas could constitute an interesting extension of this work but as a first step, we assumed that the French ones could be applied also in the context described here.

Witsenhausen Counterexample

The story will not be complete without applying theorem 4 to the Witsenhausen Counterexample (WC) which is of great interest due to the complex interplay between communication and control. Before exploring the WC, we would like to restate theorem 4 in a form more adapted to its information structure which involves agents observing each others' actions. This particularity leads to a combination of the two parts of this thesis since witsenhausen counterexample is a fundamental signalling problem involving implicit communication amongst the agents, while at the same time the information structure of the problem is causal, in the sense that no agent is aware of the future realizations of the nature state with respect to which they co-ordinate.

Performance limits with agents observing each other

While it may seem counterintuitive that the agents can observe each others' actions while trying to co-ordinate with only causal information at every instant t, this could happen if every t itself is composed of many stages j, j ∈ {1, ..., J}. For all stages j, the nature state remains constant and the payoff is decided at last stage J once all agents have made their decision. In such a scenario, an agent who needs to take a decision at stage j can, in general, observe the actions chosen by some agents during the previous stages j ∈ {1, ..., (j -1)} without violating causality. By Y i , we denote the set of images of actions taken by all the agents that agent i can observe without violating causality before taking its decision. More formally, a more general information structure for the sequence of decision functions f i,t of player i for instant t could be stated as follows:

f i,t : S t i × U × Y i -→ X i (5.11) (s i (1), s i (2)...s i (t), u(t), y i (t)) -→ x i (t)
where S t i = S i (1) × S i (2)... × S i (t) is the discrete observation alphabet of system state x 0 upto and including the instant t, X i is the decision alphabet for agent i for all instants t , with both |S i |, |X i | < ∞. The main difference between 4.1 and 5.11 is that agent i can also observe an image of the actions of other agents Y i if permitted by the information structure. As before, U is the alphabet of the auxiliary variable U which could in general serve as a co-ordination key for the agents. s i (t), u(t) and y i (t) are the realizations of the corresponding variables at instant t.

This leads to the generalization of Theorem 4, where we now simply add the fact that agent i can observe the actions chosen by other agents Y i as long as the actions were chosen at a stage before agent i chooses it's decision. Theorem 5. Assume the random process X 0,t to be i.i.d. following a probability distribution ρ. X 0,t is known to agent i via its image S i,t which is the output of a discrete memoryless channel (DMC) obtained by marginalizing the conditional probability ℸ x 0 (s 1 , ..., s N |x 0 ). Agent i also observes the actions of other agents PROBLEMS ing agents. Witsenhausen showed that affine controls, even for control problems even with linear system, quadratic costs and gaussian noise -the LQG problem, may not be optimal in some cases as was previously believed. This is an artifact of the hierarchy of the information structure as explained by [START_REF] Ho | Team decision theory and information structures in optimal control problems-part i[END_REF] [START_REF] Chu | Team decision theory and information structures in optimal control problems-part ii[END_REF].

The counterexample is a deceptively simple 2-Agent coordination problem which captures the essence of tradeoff between optimising control costs and communication costs at the same time. Reference [START_REF] Sahai | Demystifying the witsenhausen counterexample [ask the experts[END_REF] provides a very lucid description of the problem along with its importance due to the established links with computer science. However, the illustrative scenario constructed therein, of stabilizing an inverted pendulum, is too contrived in my experience of presenting the problem. For a more natural illustration, reconsider the scenario of a truck and a car coordinating to follow a path introduced in Sec. 1.2. Also, imagine that the visibility is very low, i.e. the truck can only see the immediate path ahead. The truck has two main objectives, follow the path, as well as signal the path to the car behind given that the car too has a blurry observation of the movement of truck. The communication-control trade-off comes in because manipulating a big and heavy truck is costly.

The trade-off can be better understood by considering extreme cases. Imagine the truck is really heavy. In that case, the truck will simply follow the path and let the car behind guess the path ahead based on its blurry observation of the truck's movements. On the other hand, if the truck is ultra-light and easily manipulable, it will not be too costly for it to move more than required taking into account how blurry the vision of the car behind is. Thus, based on how heavy the truck is, and how blurry the vision of the car is, they have to choose the right strategy for coordination. It turns out that finding optimal strategies for coordination problems with such information structure is fiendishly difficult, if not impossible.

The problem can be formally stated in the following manner (See Fig. 5.14).

• Uncontrolled signals -x 0 , z where x 0 represents the initial system state and z represents the noise in the observation for the second agent. System state x 0 ∼ N (0, σ 2 0 ) whereas the noise is normalized z ∼ N (0, 1). • Decision functions -First agent observes the system state perfectly and chooses its action x 1 = u(x 0 ). The second agent has a noisy observation y = x 1 + z of the first agent's action and chooses its action x 2 = v(y).

• Common Objective -Choose control functions u, v to minimize the expected cost : min

u,v w = E[k(x 1 -x 0 ) 2 + (x 2 -x 1 ) 2 ], k ≥ 0
In the case of classical information structure, i.e. Agent 2 is privy to the information available at Agent 1, the optimal strategy is trivial. Agent 1 would, in that case, choose to take no action, resulting in x 1 = x 0 and zero first stage cost. Since Agent 2 knows x 0 , and by extension x 1 , it would simply choose x 2 = x 0 , which would result in the second stage cost to be zero too. Thus these solutions are trivially linear. This is sometimes also referred to as centralized optimization in the literature. A natural conjecture was that linear controllers Witsenhausen debunked this conjecture by firstly finding the optimal linear controllers and their corresponding costs in this scenario, and then showing that for certain values of parameterk, a simple non-linear controller can achieve lower costs for certain values of the parameters k, σ 2 0 . The non linear control strategy proposed by Witsenhausen was a 1-bit quantizer of the state x 0 into either σ 0 or -σ 0 . Eventhough Witsenhausen in [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] proved the existence of an optimal solution, it has, until now, not been found.

Instead, the difficulty in finding optimal control functions was further highlighted by [START_REF] Papadimitriou | Intractable problems in control theory[END_REF] which showed that the discrete version of the problem is NPcomplete. NP-complete problems is a class of problems for which no efficient solutions have yet been found. Due to their proven equivalence, if an efficient solution is found for any NP-complete problem, it would immediately resolve the other NP-complete problems.

Nonetheless various heuristic based approaches have been suggested over the years . The convergence of the costs of these sub-optimal approaches for the benchmark case k = 0.2, σ 0 = 5 (Fig. 5.15) leads us to believe that they are very close to optimal controllers. However, most approaches give no guarantee of their optimality. Most works use the following observations made in the original Witsenhausen's article [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] to simplify the problem.

• For an optimal strategy u, E[u(x 0 )] = 0 and E[u(x 0 ) 2 ] ≤ 4σ 2 0 .

• Given a decision function u respecting the above criterion, the optimal decision for second agent v(•) is simply the MMSE:

v ⋆ u = E[u(x 0 )|y] = E x0 [u(x 0 )ϕ(y -u(x 0 )] E x0 [ϕ(y -u(x 0 )] (5.13)
where ϕ(•) is the normalized gaussian density function.

The optimal expected cost, taking into account these observations thus reduces to a function of just the decision of Agent 1. where I(D u ) is the Fischer Information of the variable y agent is the encoder trying to transmit a gaussian source over a gaussian channel. An important step in their approach is the use of information-theoretic data-processing inequality to convexify the problem, making it tractable. [START_REF] Kulkarni | An optimizer's approach to stochastic control problems with nonclassical information structures[END_REF] argue that one could use a more general optimization approach for solving problems with non-classical information structure. They suggest transforming the problem into another equivalent optimization problem with linear objective but necessarily non-convex constraints. Thereafter, one could use the technique of convex relaxation to 'convexify' the constraints and find a solution for the new optimization problem. If then, one can find a solution which is also feasible for the original non-convex constraints, then one has found the solution. They show that the data processing inequality used in [START_REF] Bansal | Stochastic teams with nonclassical information revisited: When is an affine law optimal?[END_REF] does precisely this.

Various studies have shed more light on the properties of the optimal control functions. In particular, from the vantage of optimal transport theory, [START_REF] Wu | Witsenhausen's counterexample: A view from optimal transport theory[END_REF] shows that the optimal function u(•) is monotonically increasing and has a real analytic left-inverse. This disproved the conjecture in [START_REF] Grover | The finite-dimensional witsenhausen counterexample[END_REF] that optimal solution is a multi-step piecewise constant function.

Notwithstanding the intractability of the problem, attempts have been to find best possible solutions from various viewpoints. [START_REF] Ho | An ordinal optimization approach to optimal control problems[END_REF] supposes the decision function u(•) to be a multi-step function, and uses ordinal optimization to narrow down the search for optimal number of steps and break-points. Ordinal optimization is a numerical method which uses quick and rough estimates using monte-carlo simulations over the parameter space to narrow down regions of interest. They assume that u(•) is an odd function and consider only the positive domain of the problem. They find that 2-step functions (4 steps over the whole domain) have a higher probability of 'good' payoffs and go on to finetune the search assuming 2-step functions. [START_REF] Ho | Granular optimization: An approach to function optimization[END_REF] takes this approach a step further using 2 new ideas. Firstly, they use integration with the appropriate step size to evaluate the cost of a given function, thus speeding up the search allowing them to analyze more cases of step-functions. Also, they analyze each constant section of the step function to find more 'sub-steps' thus reducing the cost further. The best solution proposed by them is a 3.5 step solution. [START_REF] Baglietto | Numerical solutions to the witsenhausen counterexample by approximating networks[END_REF] use approximating networks to find similar performances as [START_REF] Ho | Granular optimization: An approach to function optimization[END_REF] , albeit their method is much more general. They also apply their method to [START_REF] Bansal | Stochastic teams with nonclassical information revisited: When is an affine law optimal?[END_REF] as a verification test of their method.

More recently, [START_REF] Li | Learning approaches to the witsenhausen counterexample from a view of potential games[END_REF] modeled the problem in terms of potential games considering the intervals where the step function remains constant as players trying to optimize a common utility. They then applied the procedure of joint fictitious state play (JFSP) to converge to best known solutions then. However, due to the large size of 'players', it required many more iterations to converge, although the cost dropped considerably after the first 100 iterations. A similar approach, albeit not directly inspired, was taken in [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF] where they consider each controller as a player co-ordinating with the other trying to maximize a common utility. Their approach bears a close resemblance to ours, although we arrive at similar conclusions from different roots. We shall elaborate the connections in greater detail after having developed our approach in the next section. We develop a general framework of finding good coordination between N-agents, given a par-PROBLEMS ticular order of decision making and information available to the agents. We apply this framework to the special case of Witsenhausen counterexample.

Algorithm for searching optimal Witsenhausen control functions

We can now use theorem 5 to devise an algorithm for the Witsenhausen counterexample on similar lines as Chapter 4. As it would probably be clear by now, witsenhausen counterexample consists of 2 stages, i.e. J = 2. Also, the first controller perfectly observes the nature state S 1 = X 0 , whereas the second controller only observes a noisy image of the action chosen by the first controller, i.e. Y 2 = X 1 + Z, where Z ∼ N(0, σ 2 Z ). While it was difficult to write a general algorithm like we did in Chapter 4, in the specific case of witsenhausen counterexample, this task is considerably simpler. The algorithm proposed is essentially the same as [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF]. However, we implement the same idea in a slightly different way. The major differences are

• Expectation over X 0 -In [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF], they take the expectation by generating 10 6 monte carlo samples of X 0 . We argue that, as shown in [START_REF] Saldi | Finite model approximations and asymptotic optimality of quantized policies in decentralized stochastic control[END_REF], one could just create a finite model of X 0 by uniform quantization over a finite range. We argue that doing this, we can achieve good enough performances for a much smaller complexity.

• Range of X 0 -In [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF], the range of X 0 is taken to be [-25, 25], without any justification. We ran our algorithm for different ranges and found that the range has a role to play in the performance of the algorithm. [START_REF] Ho | Granular optimization: An approach to function optimization[END_REF] also performs ordinal optimization to ascertain the range as well as stepsize of X 0 although they use a different procedure for finding the functions.

• Parameter Relaxation -In [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF], due to potentially bad initialization points, they adopt the technique of parameter relaxation. Essentially, the parameter k, i.e. the weight of the cost associated at first stage, is initially taken to be high and slowly decreased to the desired value 0.04, in approximately 10 steps. We argue that such an arbitrary step is not required, and one can simply initialize with identity linear controllers i.e. u(x 0 ) = x 0 . We see that this converges to equally good solutions as [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF].

• Assumption of symmetry -In [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF], they assume that u is an odd function, i.e. u(x 0 ) = -u(-x 0 ). Since the solutions obtained are not necessarily optimal, this restriction could, in general, lead to worse solutions.

We impose no such restriction, and indeed our solutions do not verify this assumption close to x 0 = 0.

Numerical analysis

As mentioned in the preceding discussion, the implementation of Algo 4.3 differs in our case. To make a just comparison, we define certain quantities pertaining to the range and stepsize of the alphabets X i . The range for the nature alphabet X 0 is taken between [-M, M ], with the stepsize δ X0 . The range for X 1 , X 2 is taken to be the same. However, their stepsize is decreased after Algo 4.3 converges and the algo is ran again. This is done by preserving the decision functions found beforehand and merely extending their domains to include the mid-points between the earlier domain points. Firstly, we would like to point out the variability of average payoff on the range M as well as the stepsize δ X 0 . As seen in Fig. 5.16, the average payoff obtained are highly variable based on the chosen range and stepsize. At first glance, the result might seem paradoxical, but considering a bigger range for X 0 is not necessarily helpful as it might increase the chances of extra cost due to noise in observation of the second agent. Thus, there is a sort of Braess Paradox in choosing the range.

While we did not carry out a thorough analysis to find good range and stepsize, by preliminary simulations, we identified a case (M = 16.47,δ X0 = 0.27) which gives a good payoff 0.1745 when X 0 = X 1 = X 2 . Then, we increase the alphabets X 1 , X 2 by reducing the corresponding stepsize by half. Let us denote the number of total points of

|X i | = 2M δ X i = L.
With the notations in order, we can compare our results with that of [START_REF] Karlsson | Iterative source-channel coding approach to witsenhausen's counterexample[END_REF] for different alphabet sizes L. As we see from 5.17, for lower L, we provide better results, simply by searching for 'good' range and stepsize to begin with. While it is not clear if this trend holds true at higher L, we assert that it is still Figure 5.16: Vagaries of average payoff w.r.t. range as well stepsize of the alphabet X 0 . As we see, there is no fixed pattern. If one considers a bigger range for X 0 , conventional wisdom says that we must do better, but it is not necessarily the case. We note also that for all stepsizes, above a certain range, the payoff remains constant . We conclude that one needs to employ techniques akin to ordinal optimization [START_REF] Ho | Granular optimization: An approach to function optimization[END_REF] to find optimal range and stepsize. Figure 5.17: We see that if one chooses the right range and stepsize to begin with, one could obtain much better performances for low number of quantization points L. Unfortunately, we have not been able to go further in the simulations to be able to compare the two implementations at higher L. Nonetheless, searching for a 'good' initial range and stepsize can help reach better performances for lower complexity worthwhile to perform an initial search for range and stepsize, especially if one is looking for solutions which have low complexity.

Concluding Remarks

While the algorithm developed in this section had already been found independently before, we provide a rationale behind why it is a good algorithm. However, due to the sub-optimality of the approach, we could not attack the more important and open problem of finding the optimal decision functions as well as lowest achievable costs. Nonetheless, the approach outlined in this section is in all probability ϵ-optimal due to the result in [START_REF] Saldi | Finite model approximations and asymptotic optimality of quantized policies in decentralized stochastic control[END_REF]. Also, slight differences in the application of the algorithm provides hope of beating the lowest known solution till date if one manages to find the right range to search over, and given enough time to run extensive simulations. Given the really marginal improvements in the cost for the benchmark case however, it is not clear if such an effort is worthwhile, even though it would easily merit a publication in a reputed conference.

Chapter 6

Conclusions

This thesis has merely scratched the surface of the possibilities opened up by the Information theoretical tools for evaluating performances of coordination schemes. One hopes that it has nonetheless demonstrated the potential of those tools by exploring applications in various, otherwise unrelated, domains. Eventhough we tried being clever in modeling the problems to exploit the tools developed herein, in all applications further advancements were restricted due to complexity issues.

Even otherwise, there is a need to develop the theory further than the current status as coordination problems do not always assume the information structures discussed in this thesis. For example, the non-causal information structure considered in the first part currently only applies to 2-Agent team problems, which is evidently too restrictive. There is a need to consider a more general information structure. One possibility could be to consider one agent having non-causal information about the future realizations of the nature state, while others observe its action to coordinate with it. This problem is much more complicated than the 2-agent case, as the 'informed' agent, in addition to performing implicit communication, also has to choose the importance it attaches to communication with each follower. Also, the follower needs to guess if the action chosen by the informed agent was meant for him. All this to say that while the extension to this case is non trivial, if one wants to apply the developed theory to realistic coordination problems with non-causal information structure, it is necessary to go beyond 2-Agents.

Another possibility, probably a simpler case to analyze, would be to consider a chain of agents observing each other, with the leading agent having non-casual information. Even then, the performance limit of such a system is not easily obtainable from the current theory, as one cannot simply write the information constraints for each implicit communication in the chain. Moreover, even though this might be a simpler case to consider, for application purposes, the assumed information structure is too restrictive. In this thesis, we willingly did not develop the applications for the non-causal information structure in great detail as theoretically, there is still work to be done.

1. 1

 1 Truck and car co-ordinating to stay on course . . . . . . . . . . . 2.1 Case study considered in Sec. 2.4: an interference channel with 2

Figure 1 . 1 :

 11 Figure 1.1: Truck and car co-ordinating to stay on course

CHAPTER 2 .Figure 2 . 1 :

 221 Figure 2.1: Case study considered in Sec. 2.4: an interference channel with 2 transmitters (Txs), 2 receivers (Rxs), and M ≥ 1 non-overlapping frequency bands. One feature of the retained model is that both power allocation policies and channel gains g m ij are assumed to lie in finite discrete sets.

CHAPTER 2 .Figure 2 . 2 :Figure 2 . 3 :

 22223 Figure 2.2: Relative gain in terms of expected payoff ("OP/BP -1" in [%]) vs SNR[dB] obtained with the Optimal policy (OP) (with and without communication cost) when the reference policy is to put half of the power on each band (BP). Red curves correspond to the HIR, and blue curve to the LIR. B 1 = B 2 = 10MHz.

CHAPTER 2 .Figure 2 . 4 :

 224 Figure 2.4: Marginal probability distributions q X1 (•) q X2 (•) of Transmitter 1 and Transmitter 2 for the optimal policy vs β for the optimal policy for the High Interference Regime, where β = B1 B2 . For this simulation, we chose SNR=10[dB].

Figure 3 . 1 :

 31 Figure 3.1: Optimal probability distribution of X 1 at different maximum SNRs. SNR=40 dB is the optimal distribution globally

  : In Fig 3.2, we see that as E

1 Figure 3 . 2 :

 132 Figure 3.2: Scenario a; Plot of Expected payoff vs SNR for both the cases. One sees that the discrete strategy quickly beats the all-gaussian strategy, and achieves a much lower optimal cost

Figure 5 . 1 :

 51 Figure5.1: The figure represents the power control functions f i provided by Algo. 1 for the three performance metrics under consideration for power control problem. In particular, it is seen that for maximizing sum-energy, the obtained power control function exhibits a threshold under which transmission should not occur for a given transmitter.

Figure 5 . 2 :

 52 Figure 5.2: Relative performance gain (w fw N ash /w N ash in % ) of our algorithm when compared to average payoffs obtained by Nash equilibrium for sum-rate and sum-energy. The curve for sum-energy saturates as at high SNR, P max is not utilized as power emitted is much lower.

Figure 5 . 3 :

 53 Figure 5.3: Evaluation of different information available at transmitters for different levels of interference. Most importantly, one notices that transmitter knowing the interference channel gains g ij ,i ̸ = j does not bring any performance gain.

CHAPTER 5 .

 5 APPLICATION TO N-AGENT TEAM COORDINATION PROBLEMS

Figure 5 . 6 :

 56 Figure 5.6: Power control functions for different positive and negative error in estimation of channel statistics. It provides an explanation for the greater payoff loss due to underestimation of channel statistics (negative z). We see that the threshold λ i due to negative error is smaller. This results in higher power emited P i which causes interference with other users.

  Channel Statistics -Nested Quantization Number of equiprobable Quantised points for g ii Expected payoff

Figure 5 . 7 :

 57 Figure 5.7: As we see from this graph, very few quantization points per channel are required to achieve payoffs comparable to a much finer quantization. When Channel statistics are estimated with an error, we notice a maximum with only few quanitzation points for different noise levels.

Figure 5 . 8 :

 58 Figure 5.8: The number of Power levels required to achieve comparable payoffs to many more power levels can be seen. It can be seen that around 20 power levels are enough for providing reasonable payoffs.

Figure 5

 5 Figure 5.9: Our algorithm reveals the shape of good power control functions in the presence of interference. In contrast with related works on energy-efficiency[START_REF] Goodman | Power control for wireless data[END_REF], our work shows that thresholding is required to manage interference efficiently.

Figure 5 . 10 :

 510 Figure5.10: Scalability of the proposed thesholding strategy and comparison with Nash Equilibrium. We see that as number of Tx-Rx pairs increase, thresholding strategy does increasingly better, whereas Nash equilibrium payoff falls to 0

  PROBLEMS

CHAPTER 5 .

 5 APPLICATION TO N-AGENT TEAM COORDINATION PROBLEMS

CHAPTER 5 . 2 Figure 5 . 14 :

 52514 Figure 5.14: Schematic diagram of Witsenhausen counterexample

w

  ⋆ (u) := w ⋆ (u, v ⋆ u ) = kE[(x 0u(x 0 )) 2 ] + 1 -I(D u ) (5.14)

Algorithm 2 : 2 Initialization: f 0 1 (s 1 ) 2 (y 2 )) ; end foreach y 2 ∈ X 0 do f iter 2 (y 2 )

 22112222 Proposed decentralized Algorithm for finding decision functions for Witsenhausen Counterexampleinputs : X 0 , f init i , ∀i ∈ {1, 2}, output: f * 1 , f * = s 1 , f 0 2 (y 2 ) = (y 2 ), iter = 0, iter max = 100 while ∃i : f iter-1 i f iter i ≥ ϵ AND iter ≤ iter max OR iter = 0 do iter = iter + 1; foreach x 0 ∈ X 0 do f iter 1 (x 0 ) = arg min x1∈X0 ∑ y2 P (y 2 |x 1 )w(x 0 , x 1 , f iter = E X 0 (x 1 |y 2 ) ; end end

  g 22 + cg 21 ) g 11 g 22c 2 g 12 g 21 , P eq 2 = cσ 2 (g 11 + cg 12 ) g 11 g 22c 2 g 12 g 21 (5.3)

Penetration of informed EVs (%) Relative payoff loss (%)

										Without EV
	50									Algo 1, 2012
										Algo 1, 2013
										Algo 1, 2014
										IWFA, 2012
	40									IWFA, 2013
										IWFA, 2014
	30
	20
	10
	0	0	10	20	30	40	50	60	70	80	90	100

Based on data for summer 2012-2014 from Pecan Street database [16]

  Figure 5.13: Relative payoff loss ((u total /u noEV ) -1 for different years for both algorithms in comparison. We see that Algorithm 1 does considerably better every year.

	CHAPTER 5. APPLICATION TO N-AGENT TEAM COORDINATION
	PROBLEMS
	Number of Vehicles 1	2	3	4	5	6	7	8
	Transformer Aging 0.99 0.98 0.96 0.96 0.94 0.93 0.91 0.89
	Energy Loss	0.99 0.98 0.96 0.96 0.94 0.94 0.92 0.90

Table 5 .

 5 3: Ratio of u Algo1 /u IW F A for different number of vehicles, supposing that all the vehicles are informed (in posession of a signal)

for financing the remainder of my thesis.

Part II

Proof. Assume that at the optimal point, there exists one agent (agent i) with actions, labelled X 1 i , X 2 i , with non zero probabilities. If it were the case, the agent could always increase the common team payoff by choosing the action which gives better performance with probability 1; thus leading to the conditional probability P Xi|Si being a deterministic function f i (s i ). This is a classical argument to show that the solution of a multilinear program lies at the vertices. [START_REF] Nahapetyan | Bilinear programming bilinear programming[END_REF] where the decision functions of interest, f i , are formally defined as follows:

With these simplifications, we can now restate the theorem 4 for optimal achievable payoff w ⋆ in terms of the optimal decision functions f ⋆ i .

Note that in terms of optimality, all the simplifications made till now induce no performance loss. However, jointly finding the optimal functions f ⋆ i (s i ) still entails high complexity. Indeed the complexity of joint optimization could be prohibitive if the number of agents N or alphabet size |X i |, i ∈ 0, ..., N is too high. In the following section, we endeavour to devise a distributed algorithm, which although sub-optimal, is tractable complexity-wise.

Algorithm for finding sub-optimal decision functions

To reduce the complexity of the optimization problem further, we use the suboptimal approach of sequential best response dynamics [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF], with each user sequentially updating their decision function to maximize the common payoff. This approach consists of each transmitter choosing the best decision function, keeping the other decision functions constant, and each transmitter doing so sequentially within an iteration. This procedure is is repeated till convergence is achieved, typically in a few iterations. The number of iterations required for convergence of course depends on the number of agents coordinating, but it scales up very slowly as algorithms based on best-response dynamics normally converges very fast [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF]. Furthermore, since we are considering a common 'team' payoff w(x 0 , x 1 , ..., x N ), the convergence of best-response dynamics is guaranteed (See 9). Note however that BRD procedures do not necessarily converge to globally optimum solutions. Nonetheless, the decision functions obtained CHAPTER 5. APPLICATION TO N-AGENT TEAM COORDINATION PROBLEMS within the instant t denoted by Y i . Assume the observation Y i to also be an output of a DMC denoted by

, where I denotes the set of all agents whose actions are observable by agent i, and X I denotes the set of actions chosen by the agents belonging to the set I. An expected payoff w is achievable in the limit T → ∞ if and only if it can be written as:

where U is an auxiliary variable which can be optimized and P Xi|Si,U,Yi (x i |s i , u, y i ) is the probability that Transmitter i, chooses action x i after observing s i , u, y i . Now, we can develop an algorithm on similar lines as Algo 1, but with the added structure of the agents observing each others' actions in a perfectly causal and ordinated manner. This induces the function updates to be carried out stage wise within the instant t. Note that this does not affect the complexity of the algorithm much as all players still sequentially update their functions. After stating the algorithm for the general case of N agents and J stages per timeslot, we shall treat the special case of Witsenhausen counterexample (N, J = 2).

From Theorem 5, we see that the average common payoff for the agents is characterized by the conditional probabilities of an action being chosen for each agent P X i |S i ,U,Y i (x i |s i , u, y i ). However, an important point to note, as has been previously explained in proposition 8, is that at optimal payoff the strategies cannot be non-deterministic. If it were the case for any agent, it could always choose to give probability 1 to the action optimising the objective to reduce the payoff. This is due to the multilinear nature of the optmization. Thus without loss in optimality, we shall restrict the search to deterministic decision functions f i defined in 5.11. In [START_REF] Wu | Witsenhausen's counterexample: A view from optimal transport theory[END_REF] they start the optimization assuming non deterministic controllers and slowly impose determinism to obtain the optimal transport functions. While this approach is different from what we propose, the arguments used therein for imposing determinism is the same.

Writing a general algorithm for the discussed information structure in this section is pretty complex in general. Therefore, we first turn our attention to Witsenhausen counterexample which is a special case of the scenario described in Theorem 5. For this special case, an algorithm is much less convoluted and understandable. The agents are 2-controlers (N = 2) co-ordinating with each realization of nature state x 0 (t) being i.i.d. and each instant t composed of 2 stages (J = 2). In the following section, we describe the problem as well as the progress made until now in understanding the open problem.

Background -Witsenhausen Counterexample

The Witsenhausen Counterexample [START_REF] Witsenhausen | A counterexample in stochastic optimum control[END_REF] provides a well studied and important coordination problem which has a hierarchy of information amongst coordinat-PROBLEMS 1 9 9 9 2 0 0 1 2 0 0 9 2 0 1 2 0.17 where ϕ(x; 0, σ 2 0 ) is the gaussian density function with mean 0 and variance σ 2 0 . Most heuristics thus search only for the optimal function u(•), as the optimal v ⋆ u (•) is fixed given optimal u(•). Some of the important early works analyze the reasons for the difficulty of the optimization problem given the non-classical information structure. In [START_REF] Bansal | Stochastic teams with nonclassical information revisited: When is an affine law optimal?[END_REF], the authors consider a slightly modified version of the Gaussian test channel (GTC), which has the same information structure as Witsenhausen counterexample, but admits optimal linear solutions. More precisely, if we consider the following payoff with the same information structure, the optimal controlers are linear:

(5.17)

The authors then consider a more general decentralized control problem with the GTC and WC being special cases. They show that linear strategies are optimal in the case when there is no product-term of the decision variables in the cost function. They argue that the presence of such a product term is the reason for non-linear strategies outperforming linear strategies. To prove their result, they consider the problem as a communication problem where first CHAPTER 6. CONCLUSIONS For the second part pertaining to causal information structure, the challenges lie more on the application side. The developed theory is pretty general and easily adaptable to various applications as evidenced from chapter 5. However, there seems to be a trade-off between optimality and complexity which is difficult to know a priori and is highly dependent on the application in question. This requires careful analysis and modelling of the problems, and good knowledge of the state of the art to be able to choose the right mix of optimality and complexity to provide solutions better than the existing ones.

Theoretically too, there is some progress to be made, especially concerning the information structure discussed for the Witsenhausen Counterexample, where each timeslot could be divided into various stages, and agents could observe each others', causality permitting. This should be a slightly easier endeavour, although any practical application based on this theory will necessarily suffer from complexity issues, as evidenced from the treatment of the relatively simple (complexity wise) 2-agent Witsenhausen counterexample.

Most importantly, there are many new domains to be explored which could use the framework developed to provide practical coordination schemes. An application, which I find interesting, and which undoubtedly is going to be useful in the future is that of coordination for controlling the flow of traffic. A simple toy problem could be to consider traffic signals co-operating with each other with the common objective of maximizing traffic flow. One can imagine with the development in sensor technology that it would be possible for signals to locally measure the traffic in each direction, and with very little back-haul, relay the information to neighbouring signals. The signals could then make informed and smart decisions about how many vehicles to let go in which direction. This is but one such example of hopefully many more to come. Titre : Développement et application des bornes issues de la théorie de l'information à certains types de problèmes de coordination.

Mots clés : Theorie de l'information, Réseaux Sans Fil, Smart Grids, Contre-exemple de Witsenhausen Résumé : Avec la montée de la connectivité entre les appareils (internet des objets), nouvelles possibilités de coordination entre les différentes entités ont ouvert. En même temps, des résultats récents, issus de la théorie de l'information, ont fourni des limites pour la performance que tout système de coordination pourrait atteindre sous certaines structures d'information. Dans cette thèse, nous développons ces résultats théoriques dans le but de les rendre plus facilement applicable aux problèmes pratiques. À cet égard, la contribution de cette thèse est double: 1) En outre développer les résultats théoriques pour fournir un aperçu de la structure des solutions au problème d'optimisation posés dans les travaux anterieurs , ainsi que la généralisation des résultats . 2) Développer des algorithmes qui exploitent le cadre théorique fourni par les travaux antérieurs pour concevoir des mécanismes de coordination pratiques, décentralisées et robustes. La généralité de l'approche se prête à diverses applications, dont les éléments suivants ont été traités : optimisation de puissance dans les réseaux sans fil, planification de la consommation d'énergie dans les applications de réseau intelligent, ainsi que Witsenhausen contre-exemple, un problème important issu de la théorie du contrôle. Diverses possibilités sont encore à venir pour exploiter le cadre et les outils développés ici. En effet, ils pourraient être utiles même dans des domaines qui ne sont pas abordés dans cette thèse, mais qui nécessitent une coordination entre les agents avec des informations différentes à la disposition de chacun.

Title : Development and Application of Information Theoretical Bounds to Certain Class of Coordination Problems

Keywords : Information Theory, Wireless Networks, Smart Grids, Witsenhausen Counterexample Abstract : With the rise in connectivity between appliances (Internet of Things), new avenues for coordination between various entities have opened up. At the same time, recent information theoretical results have provided bounds for the performance that any coordination scheme could achieve under certain information structures. In this thesis, we further develop those information theoretical results with the aim of making them applicable more easily to practical problems. In this regard, the contribution of this thesis is twofold:

1) Further developing the aforementioned information theoretical results to provide insights into the structure of the solutions to optimization problem posed in them, as well as generalizing some results.

2) Developing algorithms which exploit the theoretical framework provided by Information theory to devise practical, decentralized and robust coordination schemes. The generality of the approach lends itself to various applications, of which the following were treated: power optimization in wireless networks, power consumption scheduling in smart grid applications, as well as Witsenhausen counterexample, an important toy problem in control theory. Various opportunities still lie ahead to exploit the framework and tools developed herein. Indeed, they could be useful even in domains which have not been explored in this thesis but which require coordination between agents with different information available to each.