Communication is one of the most important and expensive resources in a network with different parts who desire to establish coordinated behavior. When the actions of some parts are distributed according to a probability distribution which is given by the nature of the problem, finding the minimum communication requirements to coordinate the actions of some other parts according to an empirical distribution can be posed as a network information theory problem. Two different notions of information theoretic coordination are studied in the literature: empirical and strong.

This thesis deals with empirical coordination. In the standard empirical coordination framework, a mathematical criterion should be satisfied with perfect precision. This requirement can be restrictive in practice. A possible extension of the framework of empirical coordination is proposed in this thesis by introducing in the coordination requirement a fidelity parameter. Within the new framework, some new problems are stated and solved which can be useful in real applications. For example, they can be handled situations where the capacity of the network is not enough for the establishment of standard empirical coordination but is enough for the establishment of a weaker type of coordination; or situations where the quality of the coordination can vary according to the good or bad condition of the network (which is not known at the encoder).

Two different classes of problems of empirical coordination subject to fidelity criteria are studied: empirical coordination of multi-agent systems, and interference coordination over noisy channels.  In the first class, the nodes of a multi-agent system establish coordinated behavior by using the rate-limited communication links that are available between them. In the second class, two nodes control the interference created to an external observer while communicating over a noisy channel. For both classes of problems, the capacity region of two different setups is derived (fully or partially). Furthermore, the mathematical properties that the chosen fidelity metric should satisfy are discussed.

One of the main conclusions of the thesis is that there is a connection between the proposed framework and the framework of empirical coordination. Specifically, it turns out that when we design optimal coding schemes that achieve empirical coordination according to an empirical distribution and subject to the fidelity criteria, it is necessary and sufficient (at least in some simple setups) to consider all coding schemes that achieve standard empirical coordination according to some empirical distribution, from a class of empirical distributions which is close enough to the desired empirical distribution. This observation allows us to separate the proofs of the proposed framework into two discrete steps: first, we derive the capacity region for the standard framework and, then, we apply an appropriate transformation to this capacity region to get the rate-distortion region for the framework of empirical coordination subject to fidelity criteria.

Kommunikation är en av de viktigaste och mest kostsamma resurserna i ett nätverk där olika delar önskar koordinera sitt beteende. När beteendet i vissa delar av nätverket är fördelade enligt en viss sannolikhetsfördelning, som är givet av problemets natur, så är går det att hitta en lösning till det statistiska koordinationsproblemet som minimerar kommunikationskostnaden. Detta problem, vars lösning ska följa en given empirisk sannolikhetsfördelning, kan ställas upp som ett nätverksinformationsteoretiskt problem. I litteraturen studeras två typer av statistisk koordination: empirisk och stark.

Denna avhandling undersöker empirisk statistisk koordinering. I det traditionella empiriska ramverket ska ett matematiskt kriterium uppfyllas med perfekt precision. Detta krav kan i praktiken vara restriktivt. En möjlig utvidgning av ramverket för empirisk statistisk koordinering föreslås i denna avhandling, nämligen en fidelitetsparameter i det statistiska koordinationskravet. Introduktionen av en fidelitetsparameter tillåter både formulering och lösning av nya problem, vilka kan vara användbara i praktiska tillämpningar. Exempel på situationer som kan hanteras av den nya problemformuleringen är dels situationer där nätverkskapaciteten inte räcker till för traditionell empirisk statistisk koordination, men där en lösning kan ges av ett svagare statistiskt koordinationskriterium, dels situationer där kvaliteten på koordineringen kan variera med god eller dålig nätverkskvalitet, vilket inte är känt hos avsändaren.

Två olika klasser av empiriska statistiska koordinationsproblem, båda föremål för fidelitetskriterier, studeras: empirisk statistisk koordination för multiagentsystem, samt kommunikations- och interferenskoordination över brusiga kanaler. I den första klassen koordinerar noder i ett multiagentsystem sitt beteende genom att använda de bandbegränsade kommunikationskanaler som finns tillgängliga. I den andra klassen kontrollerar två noder den interferens som en extern observatör upplever under tiden noderna kommunicerar över en brusig kanal. I båda klasserna härleds kapacitetsregionen för två olika problem, antingen fullt eller delvis. Dessutom diskuteras de matematiska egenskaper som de valda fidelitetskriterierna bör uppfylla. 

En av avhandlingens huvudsakliga slutsatser är att det finns en koppling mellan de föreslagna ramverken och ramverket för empirisk statistisk koordination. Det visar sig att för att designa koder som når empirisk statistisk koordination enligt någon empirisk sannolikhetsfördelning under fidelitetskriterier, är det optimalt, åtminstone i några enkla situationer, att undersöka koder som når traditionell empirisk statistisk koordination givet en godtycklig empirisk sannolikhetsfördelning från en klass av empiriska fördelningar som i någon mening är nära nog den sanna empiriska fördelningen. Denna observation förenklar lösningen till det empiriska statistiska koordinationsproblemet under fidelitetskriterier: lösningen ges genom att tillämpa en lämplig transformation på lösningen till det traditionella ramverket.

We generalize the problem of controlling the interference created to an external observer while communicating over a discrete memoryless channel (DMC) which was studied in [1]. In particular, we consider the scenario where the transmission is established over a compound DMC channel with unknown state at both the encoder and the decoder. Depending on the exact state s of the channel, we ask for a different level of average precision Delta(s) on the establishment of the interference coordination with the external observer. For this setup, we fully characterize the capacity region.

We apply the framework of imperfect empirical coordination to a two-node setup where the action X of the first node is not observed directly but via L agents who observe independently impaired measurements hat X of the action. These L agents, using a rate-limited communication that is available to all of them, help the second node to generate the action Y in order to establish the desiredcoordinated behaviour. When L < ∞, we prove that it suffices RiIleft (hat X hat Y) for at least one agent whereas for L -→ ∞, we show that it suffices RiI(hat X hat Y mid X right) for all agents where hat Y is a random variable such that X - hat X - hat Y and pX, hat Y left( x,y) - p X,Y left(x,y) TV (is the pre-specified fidelity).

We study the problem of empirical coordination subject to a fidelity criterion for a general set-up. We prove a result which indicates a strong connection between our framework and the framework of empirical coordination developed in [1]. It turns out that when we design codes that achieve empirical coordination according to a given distribution and subject to the fidelity criterion, it is sufficient to consider codes that produce actions of the same joint type for a class of types which is close enough to our desired distribution is some sense.

We extend the framework of empirical coordination to a distributed setup where for a given action by nature, multiple descriptions of the action of the decoder are available. We adopt the coding strategy applied by El Gamal and Cover in [1] to get a lower bound of the coordination region. Then, we improve this region by applying the coding scheme applied by Zhang and Berger in [2].