1

Coordination in Distributed Networks via
Coded Actions with Application to Power
Control
arXiv:1501.03685v4 [cs.IT] 14 Aug 2017

Benjamin Larrousse, Samson Lasaulce, and Matthieu R. Bloch
{larrousse, lasaulce}@lss.supelec.fr, matthieu.bloch@ece.gatech.edu

Abstract
This paper investigates the problem of coordinating several agents through their actions, focusing
on an asymmetric observation structure with two agents. Specifically, one agent knows the past, present,
and future realizations of a state that affects a common payoff function, while the other agent either
knows the past realizations of nothing about the state. In both cases, the second agent is assumed to
have strictly causal observations of the first agent’s actions, which enables the two agents to coordinate.
These scenarios are applied to distributed power control; the key idea is that a transmitter may embed
information about the wireless channel state into its transmit power levels so that an observation of
these levels, e.g., the signal-to-interference plus noise ratio, allows the other transmitter to coordinate its
power levels. The main contributions of this paper are twofold. First, we provide a characterization of
the set of feasible average payoffs when the agents repeatedly take long sequences of actions and the
realizations of the system state are i.i.d.. Second, we exploit these results in the context of distributed
power control and introduce the concept of coded power control. We carry out an extensive numerical
analysis of the benefits of coded power control over alternative power control policies, and highlight a
simple yet non-trivial example of a power control code.
Index Terms
This paper was presented in part at the 2013 IEEE International Symposium on Information Theory [1], the 2013 International
Workshop on Stochastic Methods in Game Theory [2], and the 12th IEEE International Symposium on Modeling and Optimization
in Mobile, Ad Hoc, and Wireless Networks in 2014 [3]. The work of B. Larrousse and S. Lasaulce was supported in part by
the French agency ANR through the project LIMICOS - ANR-12-BS03-0005. The work of M. Bloch was supported in part by
NSF under award CCF-1320304.

August 15, 2017

DRAFT

2

Channels with state; coding theorems; coordination; distributed power control; distributed resource
allocation; game theory; information constraints; interference channel; optimization.

I. I NTRODUCTION
The main technical problem studied in this paper is the following. Given an integer N ≥ 1, three

discrete alphabets X0 , X1 , X2 , and a stage payoff function w : X0 × X1 × X2 → R, one wants to
maximize the average payoff

N
N
WN (xN
0 , x1 , x2 ) ,

N
1X
w(x0,n , x1,n , x2,n )
T

(1)

n=1

N
N
N
with respect to (w.r.t.) the sequences xN
1 , (x1,1 , . . . , x1,N ) ∈ X1 and x2 , (x2,1 , . . . , x2,N ) ∈ X2

N
given the knowledge of xN
0 , (x0,1 , . . . , x0,N ) ∈ X0 . Without further restrictions and with instantaneous

knowledge of x0,n , solving this optimization problem consists in finding one of the optimal pairs of
variables (x?1,n , x?2,n ) for every n. The corresponding maximum value1 of WN is then
WN?

N
1 X
max w(x0,n , x1 , x2 ).
=
x1 ,x2
N

(2)

n=1

We assume here that the variable x2 cannot be controlled or optimized directly. As formally described
in Section II, the variable x2 results from imperfect observations of x0 through x1 , which induces an
information constraint in the aforementioned optimization problem. One contribution in Section III is to
precisely characterize this constraint for large N when xN
0 consists of independent identically distributed
(i.i.d.) realizations of a given random variable X0 .
This setting is a special case of distributed optimization, in which K agents2 connected via a given
observation structure have the common objective of maximizing the average payoff WN for large N .
The variable xk with k ∈ {1, . . . , K} is the action of Agent k and represents the only variable under
its control. The variable x0 is outside of the agents’ control and typically represents the realization of a

random system state. The observation structure defines how the agents interact through observations of
the random state and of each other’s actions. The average payoff then measures the degree of coordination
between the agents, under the observation constraints of the actions imposed by the observation structure.
As a concrete example, we apply this framework to power control in Section V, in which x0 represents
the global wireless channel state information and xk the power level of Transmitter k .
1

This ideal situation is referred to as the “costless communication” case. In Section V, the corresponding power control

scenario is called costless communication power control (CCPC).
2

In other disciplines such as computer science, control, or economics, agents are sometimes called nodes, controllers, or

decision-makers.

August 15, 2017

DRAFT

3

A central question is to characterize the possible values of the average payoff WN when the agents
interact many times, i.e., when N is large. Answering this question in its full generality still appears out
of reach, and the present paper settles for a special case with K = 2 agents. Specifically, we assume
that Agent 1 has perfect knowledge of the past, current, and future realizations of the state sequence xN
0 ,
while Agent 2 obtains imperfect and strictly causal observations of Agent 1’s actions and possesses either
strictly causal or no knowledge of the realizations of the state. Despite these restricting assumptions, one
may extract valuable concepts and insights of practical relevance from the present work, which can be
extended to the general case of K ≥ 2 agents and arbitrary observation structures.
A. Related work
In most of the literature on agent coordination, including classical team decision problems [4], agents
coordinate their actions through dedicated channels, which allow them to signal or communicate with
each other without affecting the payoff function. The works most closely related to the present one are [5],
[6], in which the authors introduce the notions of empirical and strong coordination to measure agents’
ability to coordinate their actions in a network with noiseless dedicated channels. Empirical coordination
measures an average coordination over time and requires the joint empirical distribution of the actions to
approach a target distribution asymptotically in variational distance; empirical coordination relates to the
communication of probability distributions [7] and tools from rate-distortion theory. Strong coordination
is more stringent and asks the distribution of sequences of actions to be asymptotically indistinguishable
from sequences of actions drawn according to a target distribution, again in terms of variational distance;
strong coordination relates to the notion of channel resolvability [8]. The goal is then to establish the
coordination capacity [5], which relates the achievable joint distributions of actions to the fixed rate
constraints on the noiseless dedicated channels. The results of [5], [6] have been extended to a variety of
networks with dedicated channels [9], [10], [11], [12], and optimal codes have been designed for specific
settings [13], [14], [15].
Much less is known about the coordination via the actions of agents in the absence of dedicated
channels, which is the main focus of the present work. The most closely related work is [16], in which the
authors characterize the set of possible average payoffs for two agents, assuming that each agent perfectly
monitors the other agent’s actions; the authors establish the set of implementable distributions, which
are the achievable empirical joint distributions of the actions under the assumed observation structure.
In particular, this set is characterized by an information constraint that captures the observation structure
between the agents. While [16] largely relies on combinatorial arguments, [17] provides an informationtheoretic approach of coordination via actions under the name of implicit communication. Coordination

August 15, 2017

DRAFT

4

via actions also relates to earlier works on encoders with cribbing [18], [19], [20]; in such models,
encoders observe the output signals of other encoders, which effectively creates indirect communication
channels to coordinate. Another class of relevant models in which agent actions influence communication
are channels with action-dependent states [21], in which the signals emitted by an agent influence the
state of a communication channel.
To the best of our knowledge, the present work is the first to exploit coordination via actions for
distributed resource allocation in wireless networks, and specifically here for distributed power control
over an interference channel and multiple-access channels. Much of the distributed power control literature
studies the performance of power control schemes using game-theoretic tools. One example is the iterative
water-filling algorithm [22], which is an instance of best-response dynamics (BRD), and is applied over a
time horizon over which the wireless channel state is constant. One of the main drawbacks of the various
implementations of the BRD for power control problems, see e.g., [23], [24], [25], is that they tend to
converge to Nash-equilibrium power control (NPC) policies. The latter are typically Pareto-inefficient,
meaning that there exist some schemes that would allow all the agents to improve their individual utility
w.r.t. the NPC policies. Another drawback is that such iterative schemes do not always converge. Only
restrictive sufficient conditions for convergence are known, see e.g., [26] for the case of multiple input
multiple output (MIMO) interference channels, and are met with probability zero for some special cases
such as the parallel multiple-access channels [27]. In contrast, one of the main benefits of coded power
control developed in Section V is precisely to obtain efficient operating points for the network. This is
made possible by having the transmitters exchange information about the quality of the communication
links through observed quantities, such as the signal-to-interference plus noise ratio (SINR). The SINRs
of the different users effectively act as the outputs of a channel over which transmitters communicate
to coordinate their actions. A transmitter codes several realizations of the wireless channel state into a
sequence of power levels, which then allows other transmitters to exploit their corresponding sequence
of SINRs to select their power levels. No iterative procedure is required and convergence issues are
therefore avoided. We focus our study on efficiency, and NPC is therefore compared to coded power
control in terms of average sum-rate; other aspects such as wireless channel state information availability
and complexity should also be considered but are deferred to future work.
B. Contributions
The contributions of the present work are as follows.
•

The results in Section III extend [16] by relaxing assumptions about the observation structure.
While [16] assumes that Agent 2 perfectly monitors the actions of Agent 1, we consider the case

August 15, 2017

DRAFT

5

of imperfect monitoring and analyze situations in which Agent 2 has a strictly causal knowledge
(Theorem 4 and Corollary 12) or no knowledge (Theorem 5) of the state.
•

We clarify the connections between the game-theoretic formulation of [16] and information-theoretic
considerations from the literature on state-dependent channels [28], [29], [30], [31], [32], separation
theorems, and empirical coordination [5], [33]. We also formulate the determination of the long-run
average payoff as an optimization problem, which we study in detail in Section IV and exploit for
power control in Section V.

•

We establish a bridge between the coordination via actions and power control in wireless networks.
We develop a new perspective on resource allocation and control, in which designing a resource
allocation with high average common payoff amounts to designing a code. Such a code has to strike
a balance between sending information about the upcoming realizations of the state, to obtain high
payoff in the future, and achieving a good value of the current payoff. As an illustration, we provide
a complete description of a power control code for the multiple-access channel in Section V-E.
II. P ROBLEM STATEMENT

For convenience, we provide a summary of the notation used throughout this paper in Table I.
We now formally introduce the problem of interest. We consider K = 2 agents that have to select
their actions repeatedly over N ≥ 1 stages and wish to coordinate via their actions in the presence

of a random state and with an observation structure detailed next. At each stage n ∈ [1 : N ], the
action of Agent k ∈ {1, 2} is xk,n ∈ Xk with |Xk | < ∞, while the realization of the random state is

x0,n ∈ X0 with |X0 | < ∞. The realizations of the state are i.i.d. according to a random variable X0 with

distribution ρ0 ∈ ∆(X0 ). The random state does not depend on the agents’ actions but affects a common
payoff function3 w : X0 × X1 × X2 → R. Coordination is measured in terms of the average payoff

N
N
WN (xN
0 , x1 , x2 ) as defined in (1). At every stage n, Agent 2 only has access to imperfect observations

yn ∈ Y of Agent 1’s actions with |Y| < ∞, which are the output of channel without memory and with

transition probability

P(yn |xn0 , xn1 , xn2 , y n−1 ) = Γ(yn |x0,n , x1,n , x2,n )

(3)

for some fixed conditional probability Γ. We consider two observation structures defined by the strategies
(σn )1≤n≤N and (τn )1≤n≤N of Agents 1 and 2, respectively, which restrict how agents observe the state
3

The function w can be any function such that the asymptotic average payoffs defined in the paper exist.

August 15, 2017

DRAFT

6

and each other’s actions at all stage n ∈ [1 : N ] as follows:

 σI :
X0N
→ X1
n
case I:
 τ I : X n−1 × Y n−1 → X
2
n
0

 σ II : X N → X
1
n
0
case II:
.
 τ II : Y n−1 → X

(4)

(5)

2

n

Note that the strategies differ from conventional block channel coding, since an agent acts at every
stage; they may rather be viewed as joint source-channel codes with online coding and decoding.
These strategies are also asymmetric since Agent 1 does not observe Agent 2’s actions. Symmetric
strategies, in which agents would interact, are much more involved and partial results have been recently
developed in [34]. There exist, however, many scenarios, such as cognitive radio, heterogeneous networks,
interference alignment, and master-slave communications [35] in which asymmetric strategies are relevant.
Our objective is to characterize the set of average payoffs that are asymptotically feasible, i.e., the possible
P
values for limN →∞ N1 N
n=1 w(x0,n , x1,n , x2,n ) under the observation structures defined through (4)

and (5). The definition of the two corresponding feasible sets is as follows.

Definition 1 (Feasible sets of payoffs). The feasible set of payoffs in case I is defined as
N
n
 o
1 X 
I
I
Ω = ω ∈ R : ∃ (σn , τn )1≤n≤N , ω = lim
E w X0,n , σnI (X0N ), τnI (X0n−1 , Y n−1 )
. (6)
N →∞ N
I

n=1

The feasible set of payoffs in case II is defined as

N
n
 o
1 X 
E w X0,n , σnII (X0N ), τnII (Y n−1 )
.
ΩII = ω ∈ R : ∃ (σnII , τnII )1≤n≤N , ω = lim
N →∞ N

(7)

n=1

The feasible sets of payoffs are directly related to the set of empirical coordinations over the alphabet
X , X0 × X1 × X2 , defined as follows.

Definition 2 (Type [36]). Let N ≥ 1. For any sequence of realizations z N of the generic random variable
Z , the type of z N , denoted by Tz N , is the probability distribution on Z defined by
4

Tz N (z) =

N
1 X
1{zn =z} .
N

(8)

n=1

Definition 3 (Empirical coordination [5]). For ` ∈ {I, II}, Q ∈ ∆(X ) is an achievable empirical

coordination if there exists a sequence of strategies (σn` , τn` )1≤n≤N that generates, together with X0N , a
sequence X N ∈ X such that
∀ > 0,

August 15, 2017

lim P(||TX N − Q||1 > ) = 0,

N →∞

(9)

DRAFT

7

i.e., the distance between the histogram of a sequence of actions and Q converges in probability to 0.
Each feasible set of payoffs is the linear image of the corresponding set of empirical distributions
under the expectation operator. A value ω is asymptotically feasible if there exists an achievable emP
pirical coordination Q such that ω = EQ [w] = x0 ,x1 ,x2 Q(x0 , x1 , x2 )w(x0 , x1 , x2 ). We focus on the
characterization of achievable empirical coordinations rather than the direct characterization of the feasible
sets of payoffs.
Remark 1. The notion of empirical coordination relates to the game-theoretic notion of implementability [16]. For ` ∈ {I, II}, Q ∈ ∆(X ) is implementable if there exists a sequence of strategies (σn` , τn` )1≤n≤N ,

` ∈ {I, II}, that induce at each stage n a joint distribution

PX0,n ,X1,n ,X2,n ,Yn (x0 , x1 , x2 , y) , Γ(y|x0 , x1 , x2 )PX1,n ,X2,n |X0,n (x1 , x2 |x0 )ρ0 (x0 ),

(10)

and that generate, together with the sequence X0N , the sequence X N ∈ X such that
lim ||E(TX N ) − Q||1 = 0,

N →∞

(11)

i.e., the average histogram of a sequence of actions is arbitrarily close to Q. As shown in Appendix A,
if Q ∈ ∆(X ) is an achievable empirical coordination, then it is implementable.
We conclude this section by a brief discussion of the model, especially Agent 1’s strategy in (4)
and (5) that exploits non-causal knowledge of an i.i.d. state. This assumption has been often used since
the work of Gel’fand and Pinsker [28], but we provide here additional justifications motivated by the
application to power control in Section V. First, even if Agent 1 only knows future realizations over a
limited time horizon, coordination may be significantly improved compared to conventional approaches,
such as implementing single-stage game Nash equilibrium-type distributed policies [22], [23], [26], [37].
For instance, power control is typically based on a training phase and an action phase, assuming that a
single channel state is known in advance; this corresponds to N = 2 in our model and, as illustrated in
Fig. 1, a simple coordination strategy is for Agent 1 to inform Agent 2 about the upcoming channels state
during odd stages4 and coordinate their actions during even ones. In that context, assuming that Agent 1
knows the state non-causally is a way to establish an upper bound on the performance all strategies with
limited time horizon. Second, predicting the wireless channel state over a long time horizon has recently
become realistic. For instance, the trajectory of a mobile user can be forecast [38], [39], [40], which
4

For example, Transmitter 1 might use a high (resp. low) power level on an odd stages to inform Transmitter 2 that the

channel is good (resp. bad) in the next even stage.

August 15, 2017

DRAFT

8

makes our approach relevant when the wireless channel state is interpreted as the variation of path loss
and shadowing. References [38], [39], [40] also suggest that, by sampling the channel at the appropriate
rate, the state is nearly i.i.d.. Finally, note that the proposed approach also applies if the state is only i.i.d.
from block to block, where a block consists of several stages, and suggests that gains can be obtained

10

by varying the power level from stage to stage, even if the channel is constant over a block.
Stage
index |

1

|

2

|

3

|

4

|

5

|

good for good for good for good for good for
Channel user 1 user 2 user 1 user 1 user 2
|
|
|
|
|
state |
Transmit
High
High
Low
Low
power Low
|
|
|
|
|
|
level 1
Random
Random
Transmit Random
power choice High choice Low choice
|
|
|
|
|
level 2 |

Fig. 1. This figure illustrates a simple coordination scheme between two transmitters (which are the agents) in a simplified
Fig. 1. This figure illustrates a simple coordination scheme between two transmitters (which are the agents) in a simplified
scenario inspired by [16] where the alphabets are binary: X0 = {good for user 1, good for user 2}, X1 = {low, high}, X2 =
scenario inspired by [16] where the alphabets are binary: X0 = {good for user 1, good for user 2}, X1 = {low, high}, X2 ′ =
{low, high}. The informed transmitter (i.e., 1) chooses the lowest (resp. highest) transmit power on the current stage 2t + 1
{low, high}. The informed transmitter (i.e., 1) chooses
the lowest (resp. highest) transmit power on the current stage 2t0 + 1
if the upcoming wireless channel state on stage 2t′ + 2 is good for user 2 (resp. 1). If Transmitter 2 can perfectly retrieve the
if the upcoming wireless channel state on stage 2t0 + 2 is good for user 2 (resp. 1). If Transmitter 2 can perfectly retrieve the
power levels of Transmitter 1, it therefore knows the realization of the wireless channel state on stages whose index is even.
power levels of Transmitter 1, it therefore knows the realization of the wireless channel state on stages whose index is even.
It transmits at low (resp. high) power if the channel is good for user 1 (resp. 2). For stages whose index is odd, it chooses its
It transmits at low (resp. high) power if the channel is good for user 1 (resp. 2). For stages whose index is odd, it chooses its
power at random.
power at random.

for achievability, while Theorem 5 and Theorem 11 in Section III-B provide sufficient conditions for
III. I NFORMATION CONSTRAINTS ON ACHIEVABLE EMPIRICAL COORDINATION
achievability in case I and case II, respectively.
We first characterize the sets of achievable empirical coordinations Q ∈ ∆(X ) for the strategies (4)

and
We show condition
that thesefor
sets
consist of distributions in ∆(X ) subject to an information constraint
A. (5).
A necessary
achievability
!
that
captures4.the
imposedinby
the0 ×X
observation
structure. We provide aQ(x
necessary
condition
Theorem
Letrestrictions
Q be a distribution
∆(X
1 ×X2 ) such that ∀ x0 ∈ X0 ,
0 , x1 , x2 ) = ρ0 (x0 ).
x1 ,x(5)
2
for achievability in Theorem 4 and sufficient conditions for strategies (4) and
in Theorem 5 and
In both case I and case II, a distribution Q is an achievable empirical coordination only if it is the
Corollary 12, respectively.
marginal of a distribution Q ∈ ∆(X0 × X1 × X2 × Y) factorizing as
Q(x0 , x1 , x2 , y) = Γ(y|x0 , x1 , x2 )Q(x0 , x1 , x2 ),

∀(x0 , x1 , x2 , y) ∈ X0 × X1 × X2 × Y

(13)

and satisfying the information constraint
August 15, 2017

IQ (X0 ; X2 ) ≤ IQ (X1 ; Y |X0 , X2 )

DRAFT

(14)

9

A. A necessary condition for achievability
Theorem 4. In both cases I and II, if Q ∈ ∆(X ) is an achievable empirical coordination then it must
be the marginal of Q ∈ ∆(X × Y) factorizing as

Q(x0 , x1 , x2 , y) = Γ(y|x0 , x1 , x2 )Q(x1 , x2 |x0 , )ρ0 (x0 ),

(12)

and satisfying the information constraint
(13)

IQ (X0 ; X2 ) ≤ IQ (X1 ; Y |X0 , X2 ).

Proof: Since the strategies of case II are special cases of strategies for case I, we derive the necessary
conditions by considering strategies for case I, in which Agent 2 has causal knowledge of the state X0 .
Let Q ∈ ∆(X ) be an achievable empirical coordination. Note that
N
1 X
E
E TX0N X1N X2N (x0 , x1 , x2 ) =
N



n=1

1{X

0,n

,X1,n ,X2,n =(x0 ,x1 ,x2 )}



N
1 X
PX0,n ,X1,n ,X2,n (x0 , x1 , x2 ),
=
N
n=1

where PX0,n ,X1,n ,X2,n ,Yn is defined in (10). It follows from Appendix A that for ` ∈ {I, II}, there exists
a pair (σn` , τn` )1≤n≤N such that for all (x0 , x1 , x2 ) ∈ X

N
1 XX
lim
PX0,n ,X1,n ,X2,n ,Yn (x0 , x1 , x2 , y) = Q(x0 , x1 , x2 ).
N →∞ N

(14)

n=1 y∈Y

Because of the specific form of (10), this also implies that

N
1 X
lim
PX0,n ,X1,n ,X2,n ,Yn (x0 , x1 , x2 , y) = Q(x0 , x1 , x2 , y)
N →∞ N

(15)

n=1

with Q as in (12). The core of the proof consists in establishing an information constraint on the generic
N
X
1
joint distribution N
PX0,n ,X1,n ,X2,n ,Yn . We start by expressing the quantity H(X0N ) in two different
n=1

manners. On one hand we have that
H(X0N ) = I(X0N ; X0N , Y N )
=

N
X

n=1

=

N
I(X0,n ; X0N , Y N |X0,n+1
)

N
X

n=1
(a)

=

N
X

n=1

August 15, 2017


N
N
N
I(X0,n ; X0n−1 , Y n−1 |X0,n+1
) + I(X0,n ; X0,n
, YnN |X0,n+1
, X0n−1 , Y n−1 )


N
N
N
I(X0,n ; X0n−1 , Y n−1 , X0,n+1
) + I(X0,n ; X0,n
, YnN |X0,n+1
, X0n−1 , Y n−1 )

(16)
(17)
(18)
(19)

DRAFT

10

where (a) follows from the fact that the sequence X0N is i.i.d.. On the other hand we have that
H(X0N ) = I(X0N ; X0N , Y N )

(20)

N
N
= I(X0,n+1
; X0N , Y N ) + I(X0n ; X0N , Y N |X0,n+1
)

=

N
X

n=1

Since 0 ≤


N
N
I(X0,n+1
; X0,n , Yn |X0n−1 , Y n−1 ) + I(X0n ; X0,n , Yn |X0,n+1
, X0n−1 , Y n−1 ) .

(21)
(22)

N
N
N
N
I(X0,n ; X0,n
, YnN |X0,n+1
, X0n−1 , Y n−1 ) = I(X0n ; X0,n , Yn , Yn+1
|X0,n+1
, X0n−1 , Y n−1 )
N
= I(X0n ; X0,n , Yn |X0,n+1
, X0n−1 , Y n−1 ),

we obtain
N
X

n=1

N
I(X0,n ; X0n−1 , Y n−1 , X0,n+1
)=

N
X

n=1

N
I(X0,n+1
; X0,n , Yn |X0n−1 , Y n−1 ).

(23)

Introducing the uniform random variable Z ∈ {1, · · · , N } independent of all others, we rewrite (23) as
N
N
I(X0,Z ; X0,Z+1
, X0Z−1 , Y Z−1 |Z) = I(X0,Z+1
; X0,Z , YZ |X0Z−1 , Y Z−1 , Z).

(24)

We first lower bound the left hand side of (24). Since X0,Z is independent of Z we have that
N
N
I(X0,Z ; X0,Z+1
, X0Z−1 , Y Z−1 |Z) = I(X0,Z ; X0,Z+1
, X0Z−1 , Y Z−1 , Z),

(25)

which expands as
N
I(X0,Z ; X0,Z+1
, X0Z−1 , Y Z−1 , Z) = I(X0,Z ; X0Z−1 , Y Z−1 , Z)
N
+ I(X0,Z ; X0,Z+1
, |X0Z−1 , Y Z−1 , Z). (26)

By definition, X2,Z is a function of (Z, X0Z−1 , Y Z−1 ). Consequently,
I(X0,Z ; X0Z−1 , Y Z−1 , Z) = I(X0,Z ; X2,Z , X0Z−1 , Y Z−1 , Z) ≥ I(X0,Z ; X2,Z ).

(27)

This gives us the desired lower bound for the left term of (24). We now upper bound for the right hand
side of (24) as follows. Using a chain rule, we have
N
N
I(X0,Z+1
; X0,Z , YZ |X0Z−1 , Y Z−1 , Z) = I(X0,Z+1
; X0,Z |X0Z−1 , Y Z−1 , Z)+
N
I(X0,Z+1
; YZ |X0Z−1 , X0,Z , Y Z−1 , Z). (28)

August 15, 2017

DRAFT

11

The last term of (28) is upper bounded as
N
; YZ |X0Z−1 , X0,Z , Y Z−1 , Z)
I(X0,Z+1
N
= H(YZ |X0Z−1 , X0,Z , Y Z−1 , Z) − H(YZ |X0Z−1 , X0,Z , X0,Z+1
Y Z−1 , Z)
(b)

N
= H(YZ |X2,Z , X0Z−1 , X0,Z , Y Z−1 , Z) − H(YZ |X1,Z , X2,Z , X0Z−1 , X0,Z , X0,Z+1
Y Z−1 , Z)

(29)

≤ H(YZ |X0,Z , X2,Z ) − H(YZ |X0,Z , X1,Z , X2,Z )
= I(X1,Z ; YZ |X0,Z , X2,Z ).

where (b) holds because X2,Z is a function of (Z, X0Z−1 , Y Z−1 ) and X1,Z is a function of (Z, X0N ); the inN
equality follows because conditioning reduces entropy and the Markov chain (Z, X0Z−1 , X0,Z+1
, Y Z−1 )−

(X0,Z , X1,Z , X2,Z ) − YZ deduced from from (3). By combining (24)-(29), we find that
I(X0,Z ; X2,Z ) ≤ I(X1,Z ; YZ |X0,Z X2,Z ).

To conclude the proof, note that the joint distribution of X0,Z , X1,Z , X2,Z , and YQ , is exactly the
N
X
1
PX0,n ,X1,n ,X2,n ,Yn and let us introduce function ΦI
distribution N
n=1

ΦI : ∆(X × Y) →
Q

R

,

7→ IQ (X0 ; X2 ) − IQ (X1 ; Y |X0 , X2 )

which is continuous. Because of (15), ∀ε0 > 0 there exists N 0 such that ∀N ≥ N 0 ,
!
N
1 X
I
I
Φ (Q) ≤ Φ
PX0,n ,X1,n ,X2,n ,Yn + ε0 .
N

(30)

(31)

n=1

Theorem 4 has the following interpretation. Agent 2’s actions are represented by X2 and correspond
to a joint source-channel decoding operation with distortion on the information source represented
by X0 . To be achievable, the distortion rate must not exceed the transmission rate allowed by the
channel, whose input and output are represented by Agent 1’s action X1 and the signal Y observed
by Agent 2. Therefore, the pair S = (X0 , X2 ) plays the same role as the side information in statedependent channels [41]. Although we exploit this interpretation when establishing sufficient conditions
for achievability in Section III-B, the argument seems inappropriate to show that the sufficient conditions
are also necessary. In contrast to classical arguments in converse proofs for state-dependent channels [28],
[42], in which the transmitted “message” is independent of the channel state, here the role of the message
is played by the quantity X0N , which is not independent of S N = (X0N , X2N ).

August 15, 2017

DRAFT

12

B. Sufficient conditions for achievability
We start by addressing the special case of distributions Q ∈ ∆(X ) with marginal ρ0 ∈ ∆(X0 ), for

which the distribution Q(x0 , x1 , x2 , y) = Γ(y|x0 , x1 , x2 )Q(x0 , x1 , x2 ) satisfies IQ (X1 ; Y |X0 X2 ) = 0. By
Theorem 4, such Q is an achievable empirical coordination only if IQ (X0 ; X2 ) = 0, so that Q factorizes

as Q(x1 |x0 , x2 )ρ0 (x0 )Q(x2 ). This distribution is trivially achievable by time-sharing between strategies
in which: i) Agent 2 plays a fixed action x2 ; ii) Agent 1 generates actions according to Q(x1 |x0 , x2 ); iii)

playing each strategy with fixed x2 a fraction Q(x2 ) of the time. Hence, we now focus on distributions

Q for which IQ (X1 ; Y |X0 X2 ) > 0

We now characterize achievable empirical coordination for the observation structure of case II in (5).

Theorem 5. Consider the observation structure in case II. Let U be a random variable whose realizations
lie in the alphabet U , |U| < ∞. Let Q ∈ ∆(X ) be with marginal ρ0 ∈ ∆(X0 ). If Q ∈ ∆(X × Y × U)

defined as

Q(x0 , x1 , x2 , y, u) = P(u|x0 , x1 , x2 )Γ(y|x0 , x1 , x2 )Q(x0 , x1 , x2 )

(32)

verifies the constraint
IQ (X0 ; X2 ) < IQ (U ; Y, X2 ) − IQ (U ; X0 , X2 ),

(33)

then Q is an achievable empirical coordination..
Proof: Consider a distribution QX0 X1 X2 Y U ∈ ∆(X × Y × U) that satisfies (32) and (33). We denote

by QU X0 X2 , QU , QX0 X1 X2 , QX0 X2 , and QX2 the resulting marginal distributions.

The crux of the proof is to design strategies from a block-Markov coding scheme that operates over
B blocks of m ≥ 1 actions each. As illustrated in Table II, in every block b ∈ [1 : B − 1], Agent 1

communicates to Agent 2 the actions that Agent 2 should play in block b+1. This is possible by restricting

the actions played by Agent 2 in each block b to a codebook of actions {x2 (ib ) : ib ∈ [1 : 2mR ]}, so

that Agent 1 only has to communicate the index ib to be played in the next block. The problem then
essentially reduces to a joint source-channel coding problem over a state-dependent channel, for which
in every block b:
•

the state is known non-causally by Agent 1, as per the observation structure in (5);

•

Agent 1 communicates with Agent 2 over a state-dependent discrete channel without memory and
with transition probability Γ(y|x0 , x1 , x2 );

•

(b)

the channel state consists of state sequence x0

and action sequence x2 (bib−1 ), where bib−1 is the

index decoded by Agent 2 at the end of block b − 1. Agent 1 only knows x2 (ib−1 ) but the effect of

using bib−1 in place of ib−1 is later proved to be asymptotically negligible;
August 15, 2017

DRAFT

13

•

the action sequence communicated is x2 (ib ), chosen to be empirically coordinated with the state
(b+1)

sequence x0
•

of block b + 1;
(b)

ib is encoded through Gel’fand-Pinsker coding into an action sequence x1 , chosen to be empirically
(b)

coordinated with (x0 , x2 (ib−1 )).
Intuitively, R must be sufficiently large so that one may find a codeword x2 (ib ) coordinated with any
(b+1)

state sequence x0

; simultaneously, R must be small enough to ensure that the index ib is reliably

decoded by Agent 2 after transmission over the channel Γ(y|x0 , x1 , x2 ). The formal analysis of these
conditions, which we develop next, establishes the result.
Unlike the block-Markov schemes used, for instance, in relay channels, in which all nodes may agree
on a fixed message in the first block at the expense of a small rate loss, the first block must be dealt
with more carefully. In fact, we may have to account for an “uncoordinated” transmission in the first
block, in which Agent 1 may not know the actions x2 of Agent 2 and is forced to communicate at rate
b that differs from the rate R used in subsequent blocks. To characterize R
b, we introduce another joint
R
b that factorizes as
distribution Q

b 0 , x1 , x2 , y, u) = Γ(y|x0 , x1 , x2 )P(u|x0 x1 x2 )Q(x1 |x0 x2 )ρ0 (x0 )1{x =x∗ }
Q(x
2
2

(34)

and differs from Q in that X0 is independent of X2 , which is a constant. Assume that IQb (U ; Y, X2 ) −

IQb (U ; X0 , X2 ) = 0 for all P and x∗2 . In particular, for U = X0 , we obtain IQb (X0 ; Y, X2 )−IQb (X0 ; X0 , X2 ) =
0; this is equivalent to HQb (X0 |Y X2 ) = 0, so that x0 must be a function of y and x∗2 . For U = X1 ,

we also obtain IQb (X1 ; Y, X2 ) − IQb (X1 ; X0 , X2 ) = 0, which using the previously established fact leads
to IQb (X1 ; Y |X0 X2 ) = 0. Then, for all (x0 , x2 ) ∈ X0 × X2 , it must be that IQb (X1 ; Y |X0 = x0 , X2 =
x2 ) = 0 and therefore IQ (X1 ; Y |X0 = x0 , X2 = x2 ) = 0. Consequently, IQ (X1 ; Y |X0 X2 ) = 0,

which we have excluded from the analysis. Hence, we can assume that there exist P and x∗2 such that
IQb (U ; Y, X2 ) − IQb (U ; X0 , X2 ) > 0.

b > 0, R
b 0 > 0,
Now, let  > 0. Let R > 0, R0 > 0, R

to be specified later. Define


2

> 3 > 2 > 1 > 0 be real numbers and m ≥ 1

  
R
α , max
,1
b
R



4
B , 1+α
−1 .


(35)
(36)

b in the
Intuitively, α measures the rate penalty suffered from the uncoordinated transmission at rate R
first block. The choice of B merely ensures that

2α
B−1+α

≤ 2 , as exploited later.

Source codebook generation for b = 1. Choose x∗2 such that IQb (U ; Y, X2 ) − IQb (U ; X0 , X2 ) > 0. The

actions of Agent 2 are x∗2 consisting of m repetitions of x∗2 and revealed to both agents.

August 15, 2017

DRAFT

14

Source codebooks generation for b ∈ [2 : B +1]. Randomly and independently generate 2mR sequences

mR ] and reveal them to both agents.
according to Πm
n=1 QX2 (x2,n ), label them x2 (ib ) with ib ∈ [1 : 2
b0

Channel codebook generation for b = 1. Randomly and independently generate 2αm(R +R) sequences
b

αmR ] and j ∈ [1 : 2αmR ], and reveal
b
according to Πm
1
n=1 QU (un ), label them u(i1 , j1 ) with i1 ∈ [1 : 2
b0

b

them to both agents.

0

Channel codebook generation for b ∈ [2 : B]. Randomly and independently generate 2m(R +R)
0

mR ] and j ∈ [1 : 2mR ],
sequences according to Πm
b
n=1 QU (un ), label them u(ib , jb ) with ib ∈ [1 : 2

and reveal them to both agents.

Source encoding at Agent 1 in block b ∈ [1 : B]. At the beginning of block b, Agent 1 uses its
(b+1)

non-causal knowledge of the state x0
(b+1)

(x0

in the next block b + 1 to look for an index ib such that

, x2 (ib )) ∈ Tm
(QX0 X2 ). If there is more than one such index, it chooses the smallest among
1

them, otherwise it chooses ib = 1.

(1)

Channel encoding at Agent 1 in block b = 1. Agent 1 uses its knowledge of (x0 , x∗2 ) to look for an
index j1 such that



(1)
b U X0 X2 )
(Q
u(i1 , j1 ), x0 , x∗2 ∈ Tm
2

(37)

If there is more than one such index, it chooses the smallest among them, otherwise it chooses j1 = 1.
(1)

Finally, Agent 1 generates a sequence x1

(1)

by passing the sequences u(i1 , j1 ), x0 , and x∗2 through a

b X |U X X , and transmits it.
channel without memory and with transition probability Q
1
0 2

(b)

Channel encoding at Agent in block b ∈ [2 : B]. Agent 1 uses its knowledge of (x0 , x2 (ib−1 )) to

look for an index jb such that




(b)
u(ib , jb ), x0 , x2 (ib−1 ) ∈ Tm
(QU X0 X2 )
2

(38)

If there is more than one such index, it chooses the smallest among them, otherwise it chooses jb = 1.
(b)

(b)

Finally, Agent 1 generates a sequence x1 by passing the sequences u(ib , jb ), x0 , and x2 (ib−1 ) through
a channel without memory and with transition probability QX1 |U X0 X2 , and transmits it.
Decoding at Agent 2 in block b = 1. At the end of block 1, Agent 2 observes the sequence of channel
outputs y (1) and knows its sequence of actions x∗2 in block 1. Agent 2 then looks for a pair of indices
(bi1 , b
j1 ) such that




b U Y X2 ).
u(bi1 , b
j1 ), y (1) , x∗2 ∈ Tm
(Q
3

(39)

If there is none or more than one such index, Agent 2 sets bi1 = b
j1 = 1.
August 15, 2017

DRAFT

15

Channel decoding at Agent 2 in block b ∈ [2 : B]. At the end of block b, Agent 2 observes the sequence

of channel outputs y (b) and knows its sequence of actions x2 (bib−1 ) in block b. Agent 2 then looks for a
pair of indices (bib , b
jb ) such that


u(bib , b
jb ), y (b) , x2 (bib−1 ) ∈ Tm
(QU Y X2 ).
3

(40)

If there is none or more than one such index, Agent 2 sets bib = b
jb = 1.

Source decoding at Agent 2 in block b ∈ [1 : B]. Agent 2 transmits x2 (bib−1 ), where bib−1 is its estimate

of the message transmitted by Agent 1 in the previous block b − 1, with the convention that x2 (bi0 ) = x∗2 .
Analysis. We prove that Q is an achievable empirical coordination. We therefore introduce the event
N
N
E , {(X N
/ TN (Q)}
0 , X1 , X2 ) ∈

(41)

with N = mB and we proceed to show that P(E) can be made arbitrarily small for n and B sufficiently
b, and R
b0 . We start by introducing the following events..
large and a proper choice of the rates R, R0 , R
∀b ∈ [1 : N ]

E0 , {(I1 , J1 ) 6= (Ib1 , Jb1 )}
(b+1)

(b)

E1 , {(X 0

, x2 (i0b )) ∈
/ Tm
(QX0 X2 ) ∀ i0b ∈ [1 : 2mR ]}
1

(b)

(b)

0

E2 , {(u(b) (Ib , jb0 ), X 0 , x2 (Ib−1 )) ∈
/ Tm
(QU X0 X2 ) ∀ jb0 ∈ [1 : 2mR ]}
2
n
o
(b)
(b)
(b) (b)
E3 , (u(Ib , Jb ), X 0 , X1 , x2 (Ibb−1 ), Y (b) ) ∈
/ Tm
(Q
)
U
X
X
X
Y
0
1
2
3
n
o
(b)
0 0
E4 , (u(i0b , jb0 ), x2 (Ibb−1 ), Y (b) ) ∈ Tm
(Q)
for
some
(i
,
j
)
=
6
(I
,
J
)
.
b b
b b
3

We start by developing an upper bound for kTxN0 xN1 xN2 − Qk1 , whose proof can be found in Appendix B.
Lemma 6. We have that
B

kTxN0 xN1 xN2 − Qk1 ≤

2α
1 X
+
kTx(b) x(b) x(b) − Qk1 .
0
1
2
B−1+α B−1
b=2

Recalling the choice of B in (36), we therefore have


P(E) = P kTX N0 X N1 X N2 − Qk1 ≥ 
B

≤P



(42)

1 X

kTX (b) X (b) X (b) − Qk1 ≥
0
1
2
B−1
2
b=2

(43)
!



≤ P kTX (b) X (b) X (b) − Qk1 ≥ for some b ∈ [2 : B]
0
1
2
2


(b) 

[
(1)
(b)
(b)
(b)
(b)
≤ P E0 ∪ E1
E1 ∪ E2 ∪ E3 ∪ E4 

(44)
(45)
(46)

b=2

August 15, 2017

DRAFT

16

≤ P(E0 ) +
+

B
X
b=2

+

B
X
b=2

B
X

(b)
P(E1 )

b=1

+

B
X
b=2

(b)

)

(b−1)c

∩ E3

(b−1)c

∩ E4

(b−1)c

∩ E4

(b−1)c

∩ E0c )

P(E3 ∩ E1

(b)

(b−1)c

∩ E2

(b)

(b−1)c

∩ E3

P(E4 ∩ E2

(b−1)c

P(E2 |E1

(b−1)c

∩ E0c )

(47)

As proved in Appendix B, the following lemmas show that all the averages over the random codebooks
of the terms above vanish as n → ∞.
b > I b (U ; X0 X2 ) + δ(2 ) and R
b+R
b0 < I b (U ; Y X2 ) − δ(3 ), then
Lemma 7. If R
Q
Q
lim E (P(E0 )) = 0.

n→∞

Lemma 8. If R > IQ (X0 ; X2 ) + δ(1 ), then for any b ∈ [1 : B]


(b)
lim E P(E1 ) = 0.
n→∞

Lemma 9. If R0 > IQ (U ; X0 , X2 ) + δ(2 ), then for any b ∈ [2 : B]


(b))
(b−1)
lim E P(E2 |E1
) = 0.
n→∞

Lemma 10. For any b ∈ [2 : B]


(b)
(b)c
(b−1)c
(b−1)c
(b−1)c
lim E P(E3 |E2 ∩ E2
∩ E3
∩ E4
∩ E0c ) = 0.
n→∞

Lemma 11. If R + R0 < IQ (U ; Y, X2 ) − δ(3 ), then for any b ∈ [2 : B]


(b)
(b−1)c
(b−1)c
(b−1)c
lim E P(E4 ∩ E2
∩ E3
∩ E4
∩ E0c ) = 0.
n→∞

(48)

(49)

(50)

(51)

(52)

Hence, we can find 1 , 2 , and 3 small enough such that limn→∞ E(P(E)) = 0. In particular, there

must exists at least one sequence of codes such that limn→∞ P(E) = 0. Since  > 0 can be chosen
arbitrarily small, Q is an achievable empirical coordination.
A few comments are in order regarding the result in Theorem 5. The condition IQ (X0 ; X2 ) <
IQ (U ; Y, X2 ) − IQ (U ; X0 X2 ) ensures bib−1 = ib−1 with high probability as m → ∞, so that the “side

information” x2 (ib−1 ) used by Agent 1 to correlate its actions is identical to the true actions x2 (bib−1 )

of Agent 2; hence, Agent 1 effectively knows the actions of Agent 2 without directly observing them.
(b+1)

Furthermore, the state sequence x0

, which plays the role of the message in block b, is independent

(b)

of the “side information” (x0 , x2 (ib−1 )); this allows us to reuse classical coding schemes for the
transmission of messages over state-dependent channels. However, the proof of Theorem 5 exhibits a

August 15, 2017

DRAFT

17

key difference with the usual Gel’fand-Pinsker coding scheme [28] and its extensions [42]. While using
the channel decoder’s past outputs does not improve the channel capacity, it helps for coordination.
Specifically, a classical Gel’fand-Pinsker coding results would lead to an information constraint
IQ (X0 ; X2 ) < IQ (U ; Y ) − IQ (U ; X0 , X2 )

(53)

which is more restrictive than (33).
Corollary 12. Consider the observation structure in case I. Let Q ∈ ∆(X ) be with marginal ρ0 ∈ ∆(X0 ).
If Q ∈ ∆(X × Y) defined as

Q(x0 , x1 , x2 , y) = Γ(y|x0 , x1 , x2 )Q(x0 , x1 , x2 )

(54)

IQ (X0 ; X2 ) < IQ (X1 ; Y |X0 , X2 ),

(55)

satisfies the constraint

then Q is an achievable empirical coordination.
Proof: Case I differs from Case II by having the state available strictly causally at Agent 2; we
can therefore apply the results of Theorem 5 by providing X0 as a second output to Agent 2. Applying
Theorem 5 with (Y, X0 ) in place of Y , we find that if Q defined as in (32) satisfies IQ (X0 ; X2 ) <
IQ (U ; Y X0 X2 )−IQ (U ; X0 X2 ), then Q is an achievable empirical coordination. Since, IQ (U ; Y X0 X2 )−
IQ (U ; X0 X2 ) = IQ (U ; Y |X0 X2 ), setting U = X1 yields the desired result.

Setting aside the already discussed case of equality in (13), the information constraints of Theorem 4

and Corollary 12 coincide, hence establishing a necessary and sufficient condition for a joint distribution
Q ∈ ∆(X ) to be implementable in case I and a complete characterization of the associated set of

achievable payoffs. This also shows that having Agent 1 select the actions played by Agent 2 and
separating source and channel encoding operations do not incur any loss of optimality. We apply this result

in Section V to an interference network with two transmitters and two receivers, in which Transmitter
1 may represent the most informed agent, such as a primary transmitter [35], [43], Γ may represent an

SINR feedback channel from Receiver 2 to Transmitter 2.
Our results hold under the assumption of perfect monitoring [16] in which Agent 2 perfectly monitors
the actions of Agent 1, i.e., Y = X1 . Equations (13), (55), (33), and (53) then coincide with the
information constraint IQ (X0 ; X2 ) ≤ HQ (X1 |X0 , X2 ) [16], confirming as noted in [16], [17] that
allowing Agent 1 to observe the action of the other agent or providing Agent 2 with the past realizations

of the state X0n−1 does not improve the set of feasible payoffs under perfect monitoring. However, this
observation regarding the set of feasible payoffs may not hold for the set of Nash equilibrium payoffs,

August 15, 2017

DRAFT

18

which are relevant when agents have diverging interests and in which case it matters whether an agent
observes the actions of the others or not. In a power control setting, if the transmitters implement
a cooperation plan that consists in transmitting at low power as long as no transmitter uses a high
power level, see e.g., [44], it matters if the transmitters are able to check whether the others effectively
use a low power level. We focus here on a cooperative setting in which a designer has a precise
objective (maximizing the network throughput, minimizing the total network energy consumption, etc.)
and wants the terminals to implement a power control algorithm with only local knowledge and reasonable
complexity. This setting can be seen as a first step toward analyzing the more general situation in which
agents may have diverging interests; this would happen in power control in the presence of several
operators.
Note that we have not proved whether the information constraint of Theorem 5 is a necessary condition
for implementability in case II. One might be tempted to adopt a side information interpretation of the
problem to derive the converse, since (33) resembles the situation of [45]; however, finding the appropriate
auxiliary variables does not seem straightforward and is left as a refinement of the present analysis.
While Theorem 5 and Corollary 12 have been derived for an i.i.d. random state, the results generalize
to a situation in which the state is constant over L ≥ 1 consecutive stages and i.i.d. from one block of

L stages to the next. For strategies as in case I, the information constraint becomes
1
IQ (X0 ; X2 ) < IQ (X1 ; Y |X0 , X2 ).
L

(56)

In fact, one can reproduce the argument in the proof of Corollary 12 and remark that one can communicate
over the channel at a rate L times larger than the rate required for the covering of the source. Specifically,
to encode m realizations of the random state, the source codebooks must contain 2mR codewords with R >
IQ (X0 ; X2 ); however, the channel codebooks can contain 2mLR codewords with R < IQ (X1 ; Y |X0 X2 ).

The source and channel codes are compatible if mIQ (X0 ; X2 ) < mLIQ (X1 ; Y |X0 X2 ), which is the

desired result in (56). This modified constraint is useful in some wireless communication settings for
which channel states are often block i.i.d.. When L → ∞, which correspond to a single realization of

the random state, the information constraint is always satisfied and any Q ∈ ∆(X ) is implementable.

Finally, we emphasize that the information constraint obtained when coordinating via actions differs

from what would be obtained when coordinating using classical communication [46] with a dedicated
channel. If Agent 1 could communicate with Agent 2 through a channel with capacity C , then all
e ∈ ∆(X ) subject to the information constraint
Q

IQe (X0 ; X2 ) ≤ C

August 15, 2017

(57)

DRAFT

19

would be implementable. In contrast, the constraint IQ (X0 ; X2 ) < IQ (X1 ; Y |X0 X2 ) reflects the following
two distinctive characteristics of communication via actions.

1) The input distribution X1 to the “implicit channel” used for communication between Agent 1 and
Agent 2 cannot be optimized independently of the actions and of the state.
2) The output Y of the implicit channel depends not only on X1 but also on (X0 , X2 ); essentially,
the state X0 and the actions X2 of Agent 2 act as a state for the implicit channel.
Under specific conditions, the coordination via actions may reduce to coordination with a dedicated
channel. For instance, if the payoff function factorizes as w(x0 , x1 , x2 ) , w1 (x1 )w2 (x0 , x2 ) and if the obe 0 , x1 , x2 ) , Q̈(x0 , x2 )Q̇(x1 )
servation structure satisfies (X0 , X2 )−X1 −Y , then any joint distribution Q(x
satisfying the information constraint

IQe (X0 ; X2 ) < IQ̇ (X1 ; Y )

(58)

would be an achievable empirical coordination; in particular, one may optimize Q̇ independently. In
addition, if w1 (x1 ) is independent of x1 , the information constraint further simplifies as
IQe (X0 ; X2 ) < max IQ̇ (X1 ; Y ),

(59)

Q̇

and the implicit communication channel effectively becomes a dedicated channel.
IV. E XPECTED PAYOFF OPTIMIZATION
We now study the problem of determining Q ∈ ∆(X ) that leads to the maximal payoff in case I

and case II. We establish two formulations of the problem: one that involves Q viewed as a function,
and one that explicitly involves the vector of probability masses of Q. Although the latter is seemingly
more complex, it is better suited to numerically determine the maximum expected payoff and turns out
particularly useful in Section V. While we study the general optimization problem in Section IV-A, we
focus on the case of perfect monitoring in Section IV-B, for which we are able to gain more insight into
the structure of the optimal solutions.

August 15, 2017

DRAFT

20

A. General optimization problem
From the results of Section III, the determination of the largest average payoff requires solving the
following optimization problem, with ` ∈ {I, II}:
minimize

−EQ [w(X0 , X1 , X2 )] = −

s.t.

−1 +

∀(x0 , x1 , x2 , y, u) ∈ X × Y × U,

Q(x0 , x1 , x2 , y, u)w(x0 , x1 , x2 )

(x0 ,x1 ,x2 ,y,u)

X

Q(x0 , x1 , x2 , y, u)

(c)

=

0

(x0 ,x1 ,x2 ,y,u)

Q(x0 , x1 , x2 , y, u)
X
− Γ(y|x0 , x1 , x2 )
Q(x0 , x1 , x2 , y, u)

(y,u)

∀x0 ∈ X0 ,

X

−ρ0 (x0 ) +

X

Q(x0 , x1 , x2 , y, u)

(d)

=

(e)

=

0

0

(x1 ,x2 ,y,u)

∀(x0 , x1 , x2 , y, u) ∈ X × Y × U, −Q(x0 , x1 , x2 , y, u)
Φ` (Q)

(f )

≤

0

≤

0

(g)

(60)

where in case I ΦI (·) is defined in (30) while in case II
ΦII (Q) , IQ (X0 ; X2 ) − IQ (U ; Y, X2 ) + IQ (U ; X0 , X2 ).

(61)

We start by addressing the potential convexity of the optimization problem [47]. The objective function
to minimize is linear in Q and the constraints (c), (d), (e), and (f ) restrict the domain to a convex
subset of the unit simplex. Therefore, it suffices to show that the domain resulting from the additional
constraint (g) is convex for the optimization problem to be convex. In case I, for which the set U reduces
to a singleton, the following lemma proves that ΦI is a convex function of Q, which implies that the
additional constraint (g) defines a convex domain.
Lemma 13. The function ΦI is strictly convex over the set of distributions Q ∈ ∆(X × Y) with marginal
ρ0 ∈ ∆(X0 ) that factorize as

Q(x0 , x1 , x2 , y) = Γ(y|x0 , x1 , x2 )ρ0 (x0 )Q(x1 , x2 |x0 ),

(62)

with ρ0 and Γ fixed.
Proof. See Appendix C.
For case II, we have not proved that ΦII is a convex function but, by using a time-sharing argument, it is
always possible to make the domain convex. In the remaining of the paper, we assume this convexification
is always performed, so that the optimization problem is again convex.

August 15, 2017

DRAFT

21

We then investigate whether Slater’s condition holds, so that the Karush-Kuhn-Tucker (KKT) conditions
become necessary conditions for optimality. Since the problem is convex, the KKT conditions would also
be sufficient.
Proposition 14. Slater’s condition holds in cases I and II for irreducible channel transition probabilities
i.e., such that ∀(x0 , x1 , x2 , y) ∈ X0 × X1 × X2 × Y, Γ(y|x0 , x1 , x2 ) > 0.
Proof: We establish the existence of a strictly feasible point in case II, from which the existence for
case I follows as a special case. Consider a distribution Q ∈ ∆(X × Y × U) such that X0 , X1 , and X2

are independent, and U = X1 . We assume without loss of generality that the support of the marginals
QXi , i ∈ {0, 1, 2} is full, i.e., ∀xi ∈ Xi , QXi (xi ) > 0. If the channel transition probability is irreducible,

note that Q(x0 , x1 , x2 , y, u) is then strictly positive, making the constraint (f ) inactive. As for inequality

constraint (g), notice that
IQ (X0 ; X2 ) − IQ (U ; Y, X2 ) + IQ (U ; X0 , X2 ) = 0 − IQ (X1 ; Y ) − I(X1 ; X2 |Y ) + IQ (X1 ; X0 , X2 )

(63)

= −IQ (X1 ; Y ) − IQ (X1 ; X2 |Y )

(64)

= −HQ (X1 ) + HQ (X1 |Y, X2 )

(65)

< 0.

(66)

Hence, the chosen distribution constitutes a strictly feasible point for the domain defined by constraints
(c)-(g), and remains a strictly feasible point after convexification of the domain.

Our objective is now to rewrite the above optimization problem more explicitly in terms of the vector
of probability masses that describes Q. This is useful not only to exploit standard numerical solvers in
Section V, but also to apply the KKT conditions in Section IV-B. We introduce the following notation.
Without loss of generality, the finite sets Xk for k ∈ {0, 1, 2} are written in the present section as set of
indices Xk = [1; nk ]; similarly, we write U = [1 : nu ] and Y = [1 : ny ]. With this convention, we define
a bijective mapping ψ ` : X × Y × U → [1 : n` ] as

ψ ` (i0 , j 0 , k 0 , l0 , m0 ) , m0 + nu (l0 − 1) + nu ny (k 0 − 1) + nu ny n2 (j 0 − 1) + nu ny n2 n1 (i0 − 1),

(67)

which maps a realization (i0 , j 0 , k 0 , l0 , m0 ) ∈ X × Y × U to a unique index ψ ` (i0 , j 0 , k 0 , l0 , m0 ) ∈ [1 : n` ].

We also set nI , n0 n1 n2 ny and nII , n0 n1 n2 ny nu . This allows us to introduce the vector of probability
`

masses q n = (q1 , q2 , . . . , qn` ) for ` ∈ {I, II}, in which each component qi , i ∈ [1 : n` ], is equal to
`

`

Q((ψ ` )−1 (i)), and the vector of payoff values wn = (w1 , w2 , . . . , wn` ) ∈ Rn , in which each component

August 15, 2017

DRAFT

22

`

wi is the payoff of (ψ ` )−1 (i). The relation between the mapping Q (resp. w) and the vector q n (resp.
`

wn ) is summarized in Table III.

Using the proposed indexing scheme, the optimization problem is written in standard form as follows.
n
X̀
−EQ [w(X0 , X1 , X2 )] = − qi wi

minimize

i=1

∀i ∈

n
X̀

s.t.

−1 +

[1; n` ],

qi
− Γi
Θi

(h)

= 0

qi

i=1

∀i ∈ [1 : n0 ], −ρ0 (i) +

(i)

=0

in1 n2 ny nu

X

(j)

=0

qj

j=1+(i−1)n1 n2 ny nu
(k)

∀i ∈ [1 : n` ], −qi

≤ 0

(`)

`

φ` (q n )

where

X

M

Θi =

j∈{1,...,ny nu }
k∈{1,...,n0 n1 n2 }

(68)

≤0

q(k−1)ny nu +j .1{(k−1)ny nu ≤i≤kny nu −1}

(69)

and ∀i ∈ [1 : n0 ], ρ0 (i) = P(X0 = i) and ∀i ∈ [1 : n` ], Γi corresponds to the value of Γ(y|x0 , x1 , x2 ),

according to Table III. As for the function associated with inequality constraint (`), it writes in case II
(case I follows by specialization with |U| = 1) as follows:
II

φII (q n ) = IqnII (X0 ; X2 ) − IqnII (U ; Y, X2 ) + IqnII (U ; X0 , X2 )
= HqnII (X0 ) − HqnII (U, X0 |X2 ) + HqnII (U |Y, X2 )
= HqnII (X0 ) + HqnII (X2 ) − HqnII (X0 , X2 , U ) + HqnII (X2 , Y, U ) − HqnII (X2 , Y )

with


n0
X

HqnII (X0 ) = −
i=1

in1 n2 ny nu

X

j=1+(i−1)n1 n2 ny nu


qj log

in1 n2 ny nu

X

j=1+(i−1)n1 n2 ny nu




qj  ,

(70)

(71)



n2
n
n
y nu
y nu
0 n1 n
0 n1 n
X
X
X
X
X



HqnII (X2 ) = −
q(i−1)nu ny +(j−1)n2 ny nu +k log
q(i−1)nu ny +(j−1)n2 ny nu +k  ,
i=1

j=1 k=1

j=1 k=1

(72)

n2 ny nu

HqnII (X2 , Y, U ) = −

August 15, 2017

X
i=1




n
0 n1
X
j=1


q(j−1)n2 ny nu +i log

n
0 n1
X
j=1




q(j−1)n2 ny nu +i  ,

(73)

DRAFT

23

" n n ny
n0 X
n2 X
nu
0 1X
X
X

q(i−1)n1 n2 ny nu +(j−1)ny nu +k+(l−1)n2 ny nu +(m−1)nu
HqnII (X0 , X2 , U ) = −
l=1 m=1

i=1 j=1 k=1
ny

log

n
0 n1 X
X

q(i−1)n1 n2 ny nu +(j−1)ny nu +k+(l−1)n2 ny nu +(m−1)nu

l=1 m=1

and
n2 ny

HqnII (X2 , Y ) = −

X
i=1



(



#

(74)

,



nu
n
0 n1 X
X

nu
n
0 n1 X
X

q(j−1)n2 ny nu +(i−1)nu +k ) log(

j=1 k=1

j=1 k=1

q(j−1)n2 ny nu +(i−1)nu +k ) . (75)

This formulation is directly exploited in Section IV-B and in Section V.
B. Optimization problem for perfect monitoring

In the case of perfect monitoring, for which Agent 2 perfectly monitors Agent 1’s actions and Y = X1 ,
the information constraints (55) and (33) coincide and
M

I

II

φ(q n ) = φI (q n ) = φII (q n ) = Hqn (X2 ) − Hqn (X2 |X0 ) − Hqn (X1 |X0 , X2 )

(76)

with q n = (q1 , . . . , qn ), n = n0 n1 n2 . To further analyze the relationship between the vector of payoff
values wn and an optimal joint distribution q n , we explicitly express the KKT conditions. The Lagrangian
is
L(q n , λn , µ0 , µn0 , λIC ) = −

n
X
i=1

"

wi qi + λi qi + µ0 −1 +

n
X
i=1

#

qi +

n0
X
j=1



µj −ρ0i +

jn
1 n2
X

i=1+(j−1)n1 n2



qi 

+ λIC φ(q n ) (77)

where λn = (λ1 , . . . , λn ), µn0 = (µ1 , . . . , µn0 ), and the subscript IC stands for information constraint.
A necessary and sufficient condition for a distribution q n to be an optimum point is that it is a solution
of the following system:
n

∀ i ∈ [1 : n],

0
X
∂L
∂φ n
= −wi − λi + µ0 +
(q ) = 0
µj 1{1+n1 n2 (j−1)≤i≤jn1 n2 } + λIC
∂qi
∂qi

(78)

j=1

q n verifies (h), (i), (j)

(79)

∀ i ∈ [1 : n], λi ≥ 0

(80)

λIC ≥ 0

(81)

∀ i ∈ [1 : n], λi qi = 0

(82)

λIC φ(q n ) = 0

(83)

August 15, 2017

DRAFT

24

where
∂φ n
(q ) =
∀i ∈ [1 : n],
∂qi

"

−

n0 
X
k=1

−

1{1+(k−1)n n ≤i≤kn n } log

n2
X
k=1

1

2

1

2

kn
1 n2
X

j=1+(k−1)n1 n2

1{i∈{k,k+n ,...,k+(n n −1)n }} log
2

0

1

2

qj

n0X
n1 −1
j=0



#

qk+jn2 − 1 + log qi . (84)

In the following, we assume that there exists a permutation of [1 : n] such that the vector of payoff
values wn after permutation of the components is strictly ordered. A couple of observations can then
be made by inspecting the KKT conditions above. First, if the expected payoff were only maximized
under the constraints (h) and (k), the best joint distribution would be to only assign probability to the
greatest element of the vector wn ; in other words the best q n would correspond to a vertex of the unit
simplex ∆(X ). However, as the distribution of the random state fixed by constraint (j), at least n0
components of q n have to be positive. It is readily verified that under constraints (h), (j), and (k), the
optimal solution is that for each x0 the optimal pair (x1 , x2 ) is chosen; therefore, q n possesses exactly n0
positive components. This corresponds to the costless communication scenario. Now, in the presence of
the additional information constraint (`), the optimal solutions contain in general more than n0 positive
components because optimal communication between the two agents requires several symbols of X1 to
be associated with a given realization of the state. In fact, as shown in the following proposition, there
is a unique optimal solution under mild assumptions.
Proposition 15. If there exists a permutation such that the payoff vector wn is strictly ordered, then the
optimization problem (68) has a unique solution.
Proof: Assume λIC = 0 in the Lagrangian. Further assume that a candidate solution of the optimization problem q n has two or more positive components in a block of size n1 n2 associated with a
given realization x0 (see Table III). Then, there exist two indices (i1 , i2 ) such that λi1 = 0 and λi2 = 0.
Consequently, the conditions on the gradient

∂L
∂qi

= 0 for i ∈ {i1 , i2 } imply that wi1 = wi2 , which

contradicts the assumption of wn being strictly ordered under permutation. Therefore, a candidate solution
only possesses a single positive component per block associated with a given realization x0 , which means
that X1 and X2 are deterministic functions of X0 . Hence, Hqn (X2 |X0 ) = Hqn (X1 |X0 X2 ) = 0 and the
information constraint reads Hqn (X2 ) < 0, which is impossible. Hence, λIC > 0.

From Lemma 13, we know that φ(q n ) is strictly convex. Since λIC > 0, the Lagrangian is the sum of
linear functions and a strictly convex function. Since it is also continuous and optimized over a compact
and convex set, there exists a maximum point and it is unique.

August 15, 2017

DRAFT

25

Apart from assuming that wn can be strictly ordered, Proposition 15 does not assume anything on the
values of the components of wn . In practice, for a specific problem it will be relevant to exploit the special
features of the problem of interest to better characterize the relationship between the payoff function
(which is represented by wn ) and the optimal joint probability distributions (which are represented by
the vector q n ). This is one of the purposes of the next section.
V. C ODED POWER CONTROL
We now exploit the framework previously developed to study power control in interference networks. In
this context, the agents are the transmitters and the random state corresponds to the global wireless channel
state, i.e., all the channel gains associated with the different links between transmitters and receivers.
Coded power control (CPC) consists in embedding information about the global wireless channel state
into transmit power levels themselves rather than using a dedicated signaling channel. Provided that the
power levels of a given transmitter can be observed by the other transmitters, the sequence of power
levels can be used to coordinate with the other transmitters. Typical mechanisms through which agents
may observe power levels include sensing, as in cognitive radio settings, or feedback, as often assumed in
interference networks. One of the salient features of coded power control is that interference is directly
managed in the radio-frequency domain and does not require baseband detection or decoding, which
is useful in systems such as heterogeneous networks. The main goal of this section is to assess the
limiting performance of coded power control and its potential performance gains over other approaches,
such as the Nash equilibrium power control policies of a given single-stage non-cooperative game. This
comparison is relevant since conventional distributed power control algorithms, such as the iterative waterfilling algorithm, do not exploit the opportunity to exchange information through power levels or vectors
to implement a better solution, e.g., that would Pareto-dominate the Nash equilibrium power control
policies.
A. Coded power control over interference channels
We first consider an interference channel with two transmitters and two receivers, which we then
specialize to the multiple-access channel in Section V-E to develop and analyze an explicit non-trivial
power control code.
By denoting gij the channel gain between Transmitter i and Receiver j , each realization of the global
wireless channel state is given by
x0 = (g11 , g12 , g21 , g22 ),

August 15, 2017

(85)

DRAFT

26

where gij ∈ G , |G| < ∞; it is further assumed that the channel gains gij are independent and we

set X0 = G 4 . Each alphabet Xi , |Xi | < ∞, i ∈ {1, 2}, represents the set of possible power levels

for Transmitter i. Assuming that the sets are discrete is of practical interest, as there exist wireless
communication standards in which the power can only be decreased or increased by step and in which
quantized wireless channel state information is used. In addition, the use of discrete power levels may
not induce any loss of optimality [48] w.r.t. the continuous case, as further discussed in Section V-B.
We consider three stage payoff functions wrate , wSINR , and wenergy , which respectively represent the

sum-rate, the sum-SINR, and the sum-energy efficiency. Specifically,
wrate :

X

→

(x0 , x1 , x2 ) 7→

wSINR :

2
X

log2

i=1

X

X

→

→

(x0 , x1 , x2 ) 7→

R+
gii xi
1+ 2
σ + g−ii x−i
|
{z
}



,

(86)

SINRi

(x0 , x1 , x2 ) 7→
wenergy :



R+

2
X
i=1



R+

2 F 1+
X
i=1

(87)

,
gii xi
σ 2 + g−ii x−i
gii xi
σ +g−ii x−i
2

xi



.

(88)

The notation −i stands for the transmitter other than i; σ 2 corresponds to the reception noise level;
F : R+ → [0, 1] is a sigmoidal and increasing function that typically represents the block success rate,

see e.g., [49], [50]. The function F is chosen so that wenergy is continuous and has a limit when xi → 0.

The motivation for choosing these three payoff functions is as follows.
•

The sum-rate is a common measure of performance for distributed power control in wireless networks.

•

The sum-SINR is not only a linear approximation of the sum-rate but also an instance of sum-payoff
function that is more sensitive to coordination, since the dependency with respect to the SINR is
linear and not logarithmic.

•

The sum-energy efficiency has recently gathered more attention as a way to study a tradeoff between
the transmission benefit (namely, the net data rate which is represented by the numerator of the
individual payoff) and the transmission cost (namely, the transmit power which is represented by the
denominator of the individual payoff). As pointed out in [51], energy-efficiency can even represent
the energy consumed in a context with packet re-transmissions, indicating its relevance for green

August 15, 2017

DRAFT

27

communications. Finally, as simulations reveal next, total energy-efficiency may be very sensitive
to coordination.
Finally, we consider the following three possible observation structures.
•

Perfect monitoring, in which Agent 2 directly observes the actions of Agent 1, i.e., Y = X1 ;

•

BSC monitoring, in which Agent 2 observes the actions of Agent 1 through a binary symmetric
channel (BSC). The channel is given by the alphabets X1 = {Pmin , Pmax }, Y = {Pmin , Pmax }, and
the transition probability: P(Y = y|X1 = x1 ) = 1 − p if y = x1 and P(Y = y|X1 = x1 ) = p if

y 6= x1 , 0 ≤ p ≤ 1;
•

Noisy SINR feedback monitoring, in which Agent 2 observes a noisy version of the SINR of

Agent 1 as illustrated in Fig. 2; this corresponds to a scenario in which a feedback channel exists
between Receiver 2 and Transmitter 2. The channel is given by the alphabets X0 = G 4 , X1 =

{0, Pmax }, X2 = {0, Pmax }, Y = {SINR(1) , ..., SINR(N ) }, and the transition probability P(Y =
SINR(n) |(X0 , X1 , X2 ) = (x0 , x1 , x2 )) = P(Y = SINR(n) |Y0 = SINR(m) )δSINR(m) −γ(x0 ,x1 ,x2 ) ,

where γ is the function given by the SINR definition (86) and



1 − e if m = n,


P(Y = SINR(n) |Y0 = SINR(m) ) =
e if m = 1 and n = 2, or m = N and n = N − 1,



 e else.
2

The performance of coded power control will be assessed against that of the following three benchmark
power control policies.
•

Nash-equilibrium power control (NPC) policy. In such a policy, each transmitter aims at maximizing
an individual stage payoff function ui (x0 , x1 , x2 ). In the sum-rate, sum-SINR, and sum-energy
efficiency cases, these individual stage payoff-functions are respectively given by ui (x0 , x1 , x2 ) =
log2 (1 + SINRi ), ui (x0 , x1 , x2 ) = SINRi , and ui (x0 , x1 , x2 ) =

F (SINRi )
.
xi

In the sum-rate and sum-

NE
SINR cases, the unique Nash equilibrium is (xNE
1 , x2 ) = (Pmax , Pmax ), irrespectively of the value

of x0 , Pmax being the maximal power level for the transmitters. In the sum-energy efficiency case,
the unique non-trivial Nash equilibrium may be determined numerically and generally requires some
knowledge of x0 , depending on how it is implemented (see e.g., [23]).
•

Semi-coordinated power control (SPC) policy. This policy corresponds to a basic coordination
scheme in which Transmitter 1 optimizes its power knowing that Transmitter 2 transmits at full
power; SPC requires the knowledge of the current wireless channel state realization at Transmitter
1. Specifically, x2 = Pmax , x†1 ∈ arg max wr (x0 , x1 , Pmax ), r ∈ {rate, SINR, energy}. SPC is a
x1

rather intuitive scheme, which also corresponds to the situation in which Transmitter 1 only knows

August 15, 2017

DRAFT

33

1−e

SINR(1)

28

y1 = SINR(1)
e
2

e
1−e

SINR(2)

y2 = SINR(2)
e
2

e
2

SINR(3)

1−e

SINR(N −1)

1−e
e
2

y3 = SINR(3)

e

SINR(N )

1−e

yN −1 = SINR(N −1)

yN = SINR(N )

Fig. 4.Fig.
The
observed
by Transmitter
2 lies 2inlies
an in
N −symbol
alphabet
i.e., |Y|
N .=The
correspond
to possible
2. signal
The signal
observed
by Transmitter
an N −symbol
alphabet
i.e.,=|Y|
N .symbols
The symbols
correspond
to possible
valuesvalues
for theforSINR
at
the
receiver
which
is
associated
with
Transmitter
2.
Transmitter
2
observes
the
actual
value
of
its
SINR
the SINR at the receiver which is associated with Transmitter 2. Transmitter 2 observes the actual value of its SINR
with probability
1 − e1while
there there
is probability
e ≥ 0ethat
neighboring
SINRSINR
is observed.
In theInsimulations,
e = 0.1.
with probability
− e while
is probability
≥ 0athat
a neighboring
is observed.
the simulations,
e = 0.1.

i)
log2 (1
SINR
ui (x0 , realizations
x1 , x2 ) = SINR
and uithis
(x0 ,scheme
x1 , x2 ) can
= Fin(SINR
. In
the sum-rate
sumthe+past
and
of the
fact
be
optimal
if Agentand
1 and
Agent
i ),current
i , state;
x
i

NE , xNE ) = (P
SINR2 cases,
the unique
Nash
equilibrium
is (xwith
irrespectively
of the Therefore,
value
only know
X0n and
Y n−1
, respectively,
Agent
2 choosing
the),best
constant action.
max , Pmax
1
2

of x0comparisons
, Pmax beingwith
the SPC
maximal
forthe
thepotential
transmitters.
In an
theadvanced
sum-energy
efficiency
allowpower
us tolevel
assess
gain of
coding
schemecase,
and the
the unique
non-trivial
equilibrium may be determined numerically and generally requires some
value of
knowingNash
the future.
knowledge
of x0 , depending on
howcontrol
it is implemented
(see e.g.,
• Costless-communication
power
(CCPC) policy.
This [23]).
policy corresponds to the situation in
•

Semi-coordinated
powermay
control
(SPC) policy.
policy
to aoptimize
basic coordination
which transmitters
communicate
at not This
cost, so
that corresponds
they may jointly
their powers to
scheme
in which
Transmitter
1 optimizes
its power
thatInTransmitter
transmits
at full
achieve
the maximum
of the
payoff function
wr at knowing
every stage.
such a case 2there
is no information
power;
SPC requires
theperformance
knowledge of CCPC
the current
wireless
channel
stateforrealization
at Transmitter
constraint,
and the
provides
an upper
bound
the performance
of all other
†
1. Specifically,
wr (x0 , x1 , Pmax ), r ∈ {rate, SINR, energy}. SPC is a
policies. x2 = Pmax , x1 ∈ arg max
x
1

rather
schemesignal-to-noise
an engineer might
fact, SPC
The intuitive
communication
ratio think
(SNR)of.
is In
defined
as also corresponds to the situation

where Transmitter 1 only knows the past and current realizations
Pmax of the state; this scheme can in
(89)
SNR(dB) , 10 log10 2 .
σ ). Optimality is obtained when Agent
fact be optimal if Agent 1 (resp. 2) only knows X0t (resp. Y t−1
2 chooses
constant
action. Therefore, the comparisons we made allow one both to assess
B.
Influencetheofbest
the payoff
function
the potential gain an advanced coding scheme might bring over a quite simple and natural scheme
The objective of this subsection is to numerically assess the relative performance gain of CPC over SPC
and to assess the value of knowing the future.
in the case of perfect monitoring. We assume that the channel gains gij ∈ {gmin , gmax } are Bernoulli
August
July 28,
2017 15, 2017

DRAFT
DRAFT

29

distributed gij ∼ B(pij ) with pij , P(gij = gmin ); with our definition of X0 in (85), this implies

that |X0 | = 16. All numerical results in this subsection are obtained for gmin = 0.1, gmax = 2 and
(p11 , p12 , p21 , p22 ) = (0.5, 0.1, 0.1, 0.5). The sets of transmit powers X1 , X2 are both assumed to be the

same alphabet of size four {P1 , P2 , P3 , P4 }, with P1 = 0, P2 =

Pmax
3 , P3

=

2Pmax
3 , P4

= Pmax . The

quantity Pmax is given by the operating SNR and σ 2 = 1. The function F is chosen as a typical instance
of the efficiency function used in [50], i.e.,


20.9 − 1
F (x) = exp −
x



(90)

.

For all r ∈ {rate, SINR, energy}, the relative performance gain with respect to the SPC policy is


r
?
EQ (w )
Relative gain (%) = 
− 1 × 100
(91)
Eρ0 (max w(x0 , x1 , Pmax ))
x1

?

where Q is obtained by solving optimization problem (68) under perfect monitoring. This optimization
is numerically performed using the Matlab function fmincon. Fig. 3 illustrates the relative performance
gain in % w.r.t. the SPC policy for the sum-energy efficiency, while Fig. 4 illustrates it for the sum-SINR
and sum-rate.
As shown in Fig. 3, our simulation results suggest that CPC provides significant performance gains
for the sum-energy efficiency. This may not be surprising, as the payoff function (88) is particularly
sensitive to the lack of coordination; in fact, as the transmit power becomes high,

F (SINRi )
xi

→

1
xi ,

which

means that energy efficiency decreases rapidly. As shown in Fig. 4, the performance gains of CPC for
the sum-SINR and the sum-rate are more moderate, with gains as high as 43% for the sum-SINR and
25% for the sum-rate; nevertheless, such gains are still significant, and would be larger if we used NPC
instead of SPC as the reference case, as often done in the literature of distributed power control. The
shape of the sum-rate curve in Fig. 4 can be explained intuitively. At low SNR, interference is negligible
and the sum-rate is maximized when both transmitters use full power, which is also what SPC does in
this regime. At high SNR, SPC is not optimal but still provides a large sum-rate, which is comparable
to that provided by the best CPC scheme. Between these regimes, advanced coordination schemes are
particularly useful, which explains the peak at intermediate SNR.

X ?
?
?
Q (x0 , x1 , x2 ), QX2 (x2 ) =
We conclude this subsection by providing the marginals QX1 (x1 ) =
x0 ,x2
X ?
X ?
?
Q (x0 , x1 , x2 ), and joint distribution QX1 X2 (x1 , x2 ) =
Q (x0 , x1 , x2 ) of the optimal joint distri-

x0 ,x1

x0

bution for CPC and CCPC in Table IV and Table V, respectively. In both cases, the results correspond
to the maximization of the sum-rate payoff function wrate and SNR = 10 dB. Table IV shows that,

without information constraint, the sum-rate is maximized when the transmitters correlate their power

August 15, 2017

DRAFT

30

800

Expected sum energy-efficiency

Relative gain (%)

700

600

500

400

300

200
−10

0

10

20

30

40

Signal-to-Noise Ratio (dB)

Fig. 3. Relative sum-energy gain of coded power control (CPC) with perfect monitoring over semi-coordinated power control
(SPC).

Relative gain (%)

40

30

Expected sum-SINR
Expected sum-rate

20

10

0
−10

0

10

20

30

40

Signal-to-Noise Ratio (dB)

Fig. 4. Relative sum-SINR gain and sum-rate gain of coded power control (CPC) with perfect monitoring over semi-coordinated
power control (SPC).

August 15, 2017

DRAFT

31

levels so that only three pairs of transmit power levels are used out of 16. This result is consistent
with [48], which proves that, for interference channels with two transmitter-receiver pairs, there is no
loss of optimality in terms of wrate by operating over a binary set {0, Pmax } instead of a continuous

interval [0, Pmax ]. Interestingly, as seen in Table V, the three best configurations of the CCPC policy are
exploited 44.3+42.9+2.1 = 89.3% of the time in the CPC policy, despite the presence of communication
constraints between the two transmitters.
C. Influence of the observation structure
In this subsection, we focus on the observation structure defined by case I in (4) and we restrict
our attention to the sum-rate payoff function wrate . The set of powers is restricted to a binary set

X1 = X2 = {0, Pmax }, but unlike the study in Section V-B, we do not limit ourselves to perfect

monitoring. Fig. 5 shows the relative performance gain w.r.t. the SPC policy as a function of SNR for
three different observation structures. The performance of CPC for BSC monitoring is obtained assuming
a probability of error of 5%, i.e., Z1 ∼ B(0.05), P(Z1 = 1) = 0.05. The performance of CPC for noisy

SINR feedback monitoring is obtained assuming e = 0.1; in this case, it can be checked that the SINR
can take one of N = 7 distinct values.

Fig. 5 suggests that CPC provides a significant performance gain over SPC over a wide range of
operating SNRs irrespective of the observation structure. Interestingly, for SNR = 10 dB, the relative
gain of CPC only drops from 22% with perfect monitoring to 18% with BSC monitoring, which suggest
that for observation structures with typical noise levels the benefits of CPC are somewhat robust to
observation noise. Similar observations can be made for SINR feedback monitoring. Note again that one
would obtain higher performance gains by considering NPC as the reference policy or by considering
scenarios with stronger interference.
D. Influence of the wireless channel state knowledge
In this subsection, we restrict our attention to CPC with BSC monitoring with the same parameters as
in Section V-C, but we consider both Case I and Case II defined in (4) and (5), respectively. The results
for Case II are obtained assuming that |U| = 10. While we already know that the performance of CPC
is the same in Case I and Case II with perfect monitoring, the results in Fig. 6 suggest that, for typical
values of the observation noise, not knowing the past realizations of the global wireless channel state at
Transmitter 2 only induces a small performance loss.

August 15, 2017

DRAFT

32

CCPC
CPC w/ perfect monitoring
CPC w/ SINR feedback monitoring
CPC w/ BSC monitoring

30

Relative gain (%)

25
20
15
10
5
0
−10

0

10

20

30

40

Signal-to-Noise Ratio (dB)

Fig. 5. Relative sum-rate gain of costless communication power control (CCPC) and coded power control (CPC) over semicoordinated power control (SPC) under various monitoring assumptions in the observation structure of Case I.

CCPC
CPC in Case I
CPC in Case II

30

Relative gain (%)

25
20
15
10
5
0
−10

0

10

20

30

40

Signal-to-Noise Ratio (dB)

Fig. 6. Relative sum-rate gain of coded power control (CPC) and costless communication power control (CCPC) over semicoordinated power control (SPC) for the binary symmetric channel (BSC) monitoring in the observation structure of Case I and
Case II.

August 15, 2017

DRAFT

CPC in Case II

Relative gain (%)

25
20

33

15

E. Influence of the coordination scheme
10

In this last subsection, we assess the benefits of CPC for an explicit code that operates over blocks
5

of length n = 3. To simplify the analysis and clarify the interpretation, several assumptions are made.
0
First, we consider a multiple-access
channel, which is a special case of the interference channel studied
−10

0

10

20

30

40

earlier with two transmitters and a single receiver,
so that the
global
Signal-to-Noise
Ratio
(dB)wireless channel state comprises only
two components (g1 , g2 ). Second, we assume that the global wireless channel state X0 takes values in
Fig. 8. Relative sum-rate gain of coded power control (CPC) and costless communication power control (CCPC) over semi-

the binary alphabet X0 ∈ {(gmin , gmax ), (gmax , gmin )}, and is distributed according to Bernoulli random

coordinated power control (SPC) for the binary symmetric channel (BSC) monitoring in the observation structure of Case I and

variable
Case
II.

B(p) with p = P X0 = (gmin , gmax ) . In the remaining of this subsection, we identify the

realization (gmin , gmax ) with “0” and (gmax , gmin ) wth “1,” so that we may write X0 = {0, 1}. Third, we

assume that the transmitters may only choose power values in {Pmin , Pmax }, and we identify power Pmin
assume that the transmitters may only choose power values in {Pmin , Pmax }, and we identify power Pmin
with “0” and power Pmax with “1”, so that we may also write X1 = X2 = {0, 1}. Finally, we consider
with “0” and power Pmax with “1”, so that we may also write X1 = X2 = {0, 1}. Finally, we consider
the case of perfect monitoring and we restrict our attention to the sum-SINR payoff function wSINR .
the case of perfect monitoring and we restrict our attention to the sum-SINR payoff function wSINR .
The values of the payoff function used in numerical simulations are provided in Fig. 7 as the entries in
The values of the payoff function used in numerical simulations are provided in Fig. 9 as the entries in
a matrix. Each matrix corresponds to a different choice of the wireless channel state x0 ; in each matrix,
a matrix. Each matrix corresponds to a different choice of the wireless channel state x0 ; in each matrix,
the choice of the row corresponds to the action x1 of Transmitter 1, which the choice of the column
the choice of the row corresponds to the action x1 of Transmitter 1, which the choice of the column
corresponds to the action x2 of Transmitter 2.
corresponds to the action x2 of Transmitter 2.
Pmin Pmax
Pmin

0

20

Pmax

1

≃ 10

Pmin Pmax
Pmin

0

Pmax 20

x0 = (gmin , gmax )

1
≃ 10

x0 = (gmax , gmin )

Fig. 9. Payoff matrix of wSINR for power control over multiple-access channel. Numerical values of the payoff correspond
Fig. 7. Payoff matrix of wSINR for power control over multiple-access channel. Numerical values of the payoff correspond
to gmin = 0.1, gmax = 2, σ 2 = 1, Pmin = 0, Pmax = 10. For example, for the left matrix, when the power profile is
to gmin = 0.1, gmax = 2, σ 2 = 1, Pmin = 0, Pmax = 10. For example, for! the
leftgmin
matrix,Pmax
when
the" power profile is
Pmax
gmax
.
(p1 , p2 ) = (Pmax , Pmax ) the individual SINRs are given by: (SINR1 , SINR2 ) = 1+P
, 1+Pmax
g
g
max
max
min
Pmax gmin
Pmax gmax
(p1 , p2 ) = (Pmax , Pmax ) the individual SINRs are given by: (SINR1 , SINR2 ) = 1+P
,
.
g
1+P
g
max max
max min

The coordination code of length 3 that we develop next can be seen as a separate source channel code,
The coordination code of length 3 that we develop next can be seen as a separate source channel code,
which consists of a source code with distortion and a channel code with side information. The source
July 28, 2017

DRAFT

encoder and decoder are defined by the mappings
fS : X03 → {m0 , m1 }
x0

August 15, 2017

7→

,

(92)

i

DRAFT

34

gS : {m0 , m1 } → X23
7→

i

(93)

.
x2

Note that the chosen source code only uses 2 messages {m0 , m1 } to represent the 8 possible sequences
x0 . One of the benefits of this restriction is that it becomes computationally feasible to find the best two-

message code by brute force enumeration. Finding a more systematic low-compelxity design approach
to coordinatinon codes goes beyond the scope of the present work. The exact choice of fS and gS is
provided after we describe the channel code.
In each block b, Transmitter 1’s channel encoder implements the mapping
(b)

(b)

(b)

(94)

x1 = fC (x0 , x2 , ib+1 )
(b+1)

where ib+1 = fS (x0

(b+1)

) is the index associated with the sequence x2

. The idea behind the design

of the channel encoder fC is the following. If Transmitter 1 did not have to transmit the index ib+1 ,
its optimal encoding would be to exploit its knowledge of (x30 (b), x32 (b)) to choose the sequence x31 (b)
resulting in the highest average payoff in block b. However, to communicate the index ib+1 , Transmitter
1 will instead choose to transmit the sequence x31 (b) with the highest average payoff in block b if
(b)

ib+1 = m0 , or the sequence x1 with the second highest average payoff in block b if ib+1 = m1 . Note
(b)

(b)

(b)

that Transmitter 2 is able to perfectly decode this encoding given its knowledge of x0 , x2 , and x1 at
the end of block b. Formally, fC is defined as follows. The sequence x1 is chosen as
x1 = x01 ⊕ d

(95)

where the modulo-two addition is performed component-wise,
x01 ∈ arg max3
x1 ∈X1

3
X

wSINR (x0,n , x1,n , x2,n ),

n=1

d = (0, 0, 0) if ib+1 = m0 ,
3

d ∈ arg max

(96)

3
X

d s.t. Ω(d)=1 n=1

wSINR (x0,n , x01,n ⊕ dn , x2,n ) if ib+1 = m1

(97)
(98)

where Ω is the Hamming weight function that is, the number of ones in the sequence d ∈ {0, 1}3 . If the
argmax set is not a singleton set, we choose the sequence with the smallest Hamming weight.

To complete the construction, we must specify how the source code is designed. Here, we choose the
mappings fS and gS that maximize the expected payoff E(wSINR ) knowing the operation of the channel
code. The source code resulting from an exhaustive search is given in Table VI, and the corresponding
channel code is given in Table VII. The detailed expression of the expected payoff required for the search
is provided in Appendix D.

August 15, 2017

DRAFT

35

The proposed codes admit to an intuitive interpretation. For instance, the first line of Table VII indicates
that if the channel is bad for Transmitter 1 for the three stages of block b, then Transmitter 1 remains
silent over the three stages of the block while Transmitter 2 transmits at all three stages. In contrast,
the last line of Table VII shows that if the channel is good for Transmitter 1 for the three stages of
block b, then Transmitter 1 transmit at all stages while Transmitter 2 remains silent two thirds of the
time. While this is suboptimal for this specific global wireless channel state realization, this is required
to allow coordination and average optimality of the code.
To conclude this section, we compare the performance of this short code with the best possible
performance that would be obtained with infinitely long codes. As illustrated in Fig. 8, while the
performance of the short code suffers from a small penalty compared to that of ideal codes with infinite
block length, it still offers a significant gain w.r.t. the SPC policy and it outperforms the NPC policy.
100

CCPC
CPC length n → ∞
CPC length n = 3
SPC
NPC

Expected payoff (a.u.)

80

60

40

20

0
0

10

20

30

40

50

Signal-to-Noise Ratio (dB)
Fig. 8. Expected payoff versus SNR for different power control policies.

VI. C ONCLUSION
In this paper, we adopted the view that distributed control policies or resource allocation policies in
a network are joint source-channel codes. Essentially, an agent of a distributed network may convey its
knowledge of the network state by encoding it into a sequence of actions, which can then be decoded by
the agents observing that sequence. As explicitly shown in Section V-E, the purpose of such “coordination
codes” is neither to convey information reliably nor to meet a requirement in terms of maximal distortion
level, but to provide a high expected payoff. Consequently, coordination codes must implement a trade-off

August 15, 2017

DRAFT

36

between sending information about the future realizations of the network state, which plays the role of
an information source and is required to coordinate future actions, and achieving an acceptable payoff for
the current state of the network. Considering the large variety of payoff functions in control and resource
allocation problems, an interesting issue is whether universal codes performing well within classes of
payoff functions can be designed.
Remarkably, since a distributed control policy or resource allocation policy is interpreted as a code,
Shannon theory naturally appears to measure the efficiency of such policies. While the focus of this paper
was limited to a small network of two agents, the proposed methodology to derive the best coordination
performance in a distributed network is much more general. The assumptions made in this paper are
likely to be unsuited to some application scenarios, but provide encouraging preliminary results to further
research in this direction. For example, as mentioned in Section I, a detailed comparison between coded
power control and iterative water-filling like algorithms would lead to consider a symmetric observation
structure while only an asymmetric structure is studied in this paper. The methodology to assess the
performance of good coded policies consists in deriving the right information constraint(s) by building the
proof on Shannon theory for the problem of multi-source coding with distortion over multi-user channels
wide side information and then to use this constraint to find an information-constrained maximum of
the payoff (common payoff case) or the set of Nash equilibrium points which are compatible with the
constraint (non-cooperative game case). As a key observation of this paper, the observation structure of
a multi-person decision-making problem corresponds in fact to a multiuser channel. Therefore, multiterminal Shannon theory is not only relevant for pure communication problems but also for any multiperson decision-making problem. The above observation also opens new challenges for Shannon-theorists
since decision-making problems define new communication scenarios.
A PPENDIX A
ACHIEVABLE EMPIRICAL COORDINATION AND IMPLEMENTABILITY
Assume Q is an achievable empirical coordination. Then, for any  > 0,
||E(TX N ) − Q||1 ≤ E(||TX N − Q||1 )

(99)

= E(||TX N − Q||1 | ||TX N − Q||1 ≥ )P(||TX N − Q||1 ≥ )
+ E(||TX N − Q||1 | ||TX N − Q||1 < )P(||TX N − Q||1 < )
≤ 2P(||TX N − Q||1 ≥ ) + .

Hence, ∀ > 0

August 15, 2017

(100)
(101)

limN →∞ ||E(TX N ) − Q||1 ≤ , which means that Q is implementable.

DRAFT

37

A PPENDIX B
L EMMAS USED IN PROOF OF T HEOREM 5
A. Proof of Lemma 6
Recall that N = αm + (B − 1)m with our coding scheme. Note that
kTxN0 xN1 xN2 − Qk1
=

N
X
1
1
− Q(x0 , x1 , x2 )
N {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )}

X

(102)

x0 ,x1 ,x2 n=1

=

B X
m
αm
X
X
1
1
1 (1) (1) (1)
+
1 (b) (b) (b)
− Q(x0 , x1 , x2 )
N {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )}
N {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )}

X

x0 ,x1 ,x2 n=1

≤

b=2 n=1

(103)

αm
X
αm
1
1 (1) (1) (1)
−
Q(x0 , x1 , x2 )
N {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )}
N

X

x0 ,x1 ,x2 n=1

+

B
X
X

m
X
1
N − αm
Q(x0 , x1 , x2 )
1 (b) (b) (b)
−
N {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )} N (B − 1)

(104)

b=2 x0 ,x1 ,x2 n=1

=

αm
αm X X 1
1 (1) (1) (1)
− Q(x0 , x1 , x2 )
N x ,x ,x
αm {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )}
0

1

2

n=1

B
m
mX X X 1
+
1 (b) (b) (b)
− Q(x0 , x1 , x2 )
N
m {(x0,n ,x1,n ,x2,n )=(x0 ,x1 ,x2 )}
x ,x ,x
b=2

0

1

2

(105)

n=1

B

2α
1 X
≤
+
kTx(b) x(b) x(b) − Qk1 ,
0
1
2
B−1+α B−1

(106)

b=2

where (104) follows from the triangle inequality and (106) follows from
for (P, Q) ∈ ∆2 (X ).

m
N

≤

1
B−1

and kP − Qk1 ≤ 2

B. Proof of Lemma 7
The proof of this result is similar to that of the following Lemmas, using the “uncoordinated” distrib instead of Q. For brevity, we omit the proof.
bution Q
C. Proof of Lemma 8
Note that




(b+1)
(b)
, X 2 (i0b )) ∈
/ Tn1 (QX0 X2 ) for all i0b ∈ [1 : 2nR ]
E P(E1 ) = P (X 0

August 15, 2017

(107)

DRAFT

38

Q
(b)
with X 0 distributed according to nn=1 QX0 , and X 2 (ib ) independent of each other distributed according
Q
to m
n=1 QX2 . Hence, the result directly follows from the covering lemma [41, Lemma 3.3], with the
following choice of parameters.

(b+1)

X̂ n (m) with m ∈ A ← X 2 (i0b ) with i0b ∈ [1 : 2nR ].

Xn ← X0

U ←∅

D. Proof of Lemma 9
Note that




0
(b)
(b−1)c
(b)
/ Tn2 (QU X0 X2 ) for all jb0 ∈ [1 : 2nR ] , (108)
E P(E2 |E1
) = P (U (Ib , jb0 ), X 0 , X 2 (Ib−1 )) ∈
(b)

where (X 0 , X 2 (Ib−1 )) ∈ Tn1 (QX0 X2 ), and U (Ib , j) are generated independently of each other according
Q
to nn=1 QU . Hence, the result follows directly from the covering lemma [41, Lemma 3.3] with the
following choice of parameters.
(b)

X n ← X 0 , X 2 (Ib−1 )

U ←∅

0

X̂ n (m) with m ∈ A ← U (Ib , jb0 ) with jb0 ∈ [1 : 2nR ].

E. Proof of Lemma 10
The result follows from a careful application of the conditional typicality lemma. Note that condition(b)c

ing on E2
(b−1)c

(b)

(b−1)c

ensures that (u(Ib , Jb ), X 0 , x2 (Ib−1 )) ∈ Tn2 (QU X0 X2 ), while conditioning on E2

∩



(109)

(b−1)c

∩ E0c guarantees that Ibb−1 = Ib−1 . Consequently,


(b)
(b)c
(b−1)c
(b−1)c
(b−1)c
P E3 ∩ E2 ∩ E2
∩ E3
∩ E4
∩ E0c

(b)
(b)
/ Tn3 (QX0 X2 X1 Y )
≤ P (u(Ib , Jb ), X 0 , X 1 , x2 (Ibb−1 ), Y (b) ) ∈

E3

=

∩ E4

X

(b)
|(u(Ib , Jb ), X 0 , x2 (Ib−1 )) ∈ Tn2 (QU X0 X2 ) ∩ Ibb−1 = Ib−1
XX
(b) (b)
pIbb−1 ,Ib ,Jb ,X (b) (ib−1 , ib , jb , x0 )
Γ(y|x0 , x1 , x2 (ib−1 ))
0

(b)

ib−1 ,ib ,jb ,x0

y

(b)

x1

Q(x1 |u(ib , jb ), x0 , x2 (ib−1 ))1{(u(ib ,jb ),x(b) ,x(b) ,x(b) (ib−1 ),y)∈T
/ n (QU X
(b)

(b)

0

1

2

3

0 X1 X2 Y

)} ,

(110)

(b)
(b)
where pIbb−1 ,Ib ,Jb ,X (b) denotes the joint distribution of Ibb−1 , Ib , Jb , X 0 given (u(Ib , Jb ), X 0 , x2 (Ib−1 )) ∈
0

Tn2 (QU X0 X2 )

and Ibb−1 = Ib−1 . Upon taking the average over the random codebooks, we obtain

 

(b)
(b−1)c
(b−1)c
(b−1)c
(b−1)c
E P E3 |E1
∩ E2
∩ E3
∩ E4
∩ E0c


XX
X
(b)
(b) (b)
=
E pIbb−1 ,Ib ,Jb ,X (b) (ib−1 , ib , jb , x0 )E 
Γ(y|x0 , x1 , X 2 (ib−1 ))
0

y

(b)

ib−1 ,ib ,jb ,x0

(b)

x1


U
(i
,
j
),
X
(i
))
.
b b
2 b−1
0 X1 X2 Y }

Q(x1 |U (ib , jb ), x0 , X 2 (ib−1 ))1{(u(ib ,jb ),x(b) ,x(b) ,X (b) (ib−1 ),y)∈T
/ n (QU X
(b)

(b)

0

August 15, 2017

1

2

3

(111)

DRAFT

39

The inner expectation is therefore

P (u, x0 , X 1 , x2 , Y ) ∈
/ Tn3 (QU X0 X1 X2 Y ) ,

where (X 1 , Y ) is distributed according to

Qm

n=1 QX1 |U X0 X2 (x1,n |u1,n , x2,n x0,n )Γ(yn |x0,n x1,n x2,n )

(112)
given

(u, x0 , x2 ) ∈ Tn2 (QX0 X2 ). The conditional typicality lemma [41, p. 27] guarantees that (112) vanishes

as n → ∞.

F. Proof of Lemma 11
The result is a consequence of the packing lemma. Note that
 

(b)
(b−1)c
(b−1)c
(b−1)c
E P E4 ∩ E2
∩ E3
∩ E4
∩ E0c
 

(b)
≤ E P E4 |Ibb−1 = Ib−1


= P (U (i0b , jb0 ), X 2 (Ibb−1 ), Y (b) ) ∈ Tn2 (Q) for some (i0b , jb0 ) with i0b 6= Ib |Ibb−1 = Ib−1
(b−1)c

(113)
(114)

(b−1)c
∩ E4
∩ E0c guarantees that Ibb−1 = Ib−1 . Since every U (i0b , jb0 )
Q
with i0b =
6 Ib is generated according to m
i=1 pU (ui ) independently of (Y , X 2 (Ib−1 )), byt the packing

since conditioning on E2

(b−1)c

∩ E3

lemma [41, Lemma 3.1] we know that if R + R0 < IQ (U ; Y, X2 ) − δ(3 ) then


P (U (i0b , jb0 ), X 2 (Ibb−1 ), Y (b) ) ∈ Tn2 (Q) for some (i0b , jb0 ) with i0b 6= Ib |Ibb−1 = Ib−1

vanishes as n → ∞.

A PPENDIX C
P ROOF OF L EMMA 13
The function Φ = ΦI can be rewritten as Φ(Q) = HQ (X0 ) − HQ (Y, X0 |X2 ) + HQ (Y |X0 , X2 , X1 ).
P
The first term HQ (X0 ) = − x0 ρ0 (x0 ) log ρ0 (x0 ) is a constant w.r.t. Q. The third term is linear w.r.t.
Q since, with Γ fixed,

HQ (Y |X0 , X2 , X1 ) = −

X

Q(x0 , x1 , x2 , y) log Γ(y|x0 , x1 , x2 ).

(115)

x0 ,x1 ,x2 ,y

It is therefore sufficient to prove that HQ (Y, X0 |X2 ) is concave. Let λ1 ∈ [0, 1], λ2 = 1 − λ1 , (Q1 , Q2 ) ∈
∆2 (X0 × X1 × X2 × Y) and Q = λ1 Q1 + λ2 Q2 . We have that:


P
X X
x1 ,i λi Qi (x0 , x1 , x2 , y)
P
HQ (Y, X0 |X2 ) = −
λi Qi (x0 , x1 , x2 , y) log
i λi Qi (x2 )
x0 ,x2 ,y
x1 ,i
P

P

X X X
i λi
x1 Qi (x0 , x1 , x2 , y)
P
=−
λi
Qi (x0 , x1 , x2 , y) log
i λi Qi (x2 )
x ,x ,y
x
0

August 15, 2017

2

i

(116)
(117)

1

DRAFT

40

X X

X





P

Qi (x0 , x1 , x2 , y)
>−
λi
Qi (x0 , x1 , x2 , y) log
λi Qi (x2 )
x0 ,x2 ,y
x1
i
P




X
X
X
x1 Qi (x0 , x1 , x2 , y)
=−
λi
Qi (x0 , x1 , x2 , y) log
Qi (x2 )
x ,x ,y
x
i

0

2

λi

x1



(118)
(119)

1

(120)

= λ1 HQ1 (Y, X0 |X2 ) + λ2 HQ2 (Y, X0 |X2 )

where the strict inequality comes from the log-sum inequality [36], with:
ai = λi Qi (x0 , x1 , x2 )

(121)

bi = λi Qi (x2 )

(122)

and

for i ∈ {1, 2} and for all (x0 , x1 , x2 ) such that Qi (x2 ) > 0.
A PPENDIX D
E XPRESSION OF THE EXPECTED PAYOFF W3

WHICH ALLOWS THE BEST MAPPINGS fS AND gS TO BE
SELECTED

We introduce the composite mapping χS = gS ◦ fS . For the channel code defined in Section V-E,

the expected payoff only depends on the mappings fS and χS , and we denote it by W3 (fS , χS ). The
following notation is used below: χS (x30 ) = (χ1 (x30 ), χ2 (x30 ), χ3 (x30 )) to stand for the three components
of χS .
It can be checked that

X

W3 (fS , χS ) =

(123)

Wijk (fS , χS )

(i,j,k)∈{0,1}3

where:
3

W000 (fS , χS ) =
3
0

p
|{z}

P[x [b]=(0,0,0)]



P0 (fS ) ×
| {z }

P[ib+1 =m0 ]

+ (1 − P0 (fS )) ×

max

|

x31 ∈{0,1}3 \X1000

X1000 = arg 3 max {
x1 ∈{0,1}3

August 15, 2017

|

max {

x31 ∈{0,1}3

{

3
X

n=1

3
X

w(0, x1,n , χn ((0, 0, 0)))}

n=1

{z

Best payoff

w(0, x1,n , χn ((0, 0, 0)))}

{z

Second best payoff

3
X

w(0, x1,n , χn ((0, 0, 0)))},

!

,

!
}

(124)

}

(125)

n=1

DRAFT

41


W001 (fS , χS ) = p (1 − p) P0 (fS ) ×
2

+ (1 − P0 (fS )) ×



max
3

x1 ∈{0,1}3

n
w(0, x1,1 , χ1 ((0, 0, 1))) + w(0, x1,2 , χ2 ((0, 0, 1)))

!
o
+ w(1, x1,3 , χ3 ((0, 0, 1)))

n
w(0, x1,1 , χ1 ((0, 0, 1))) + w(0, x1,2 , χ2 ((0, 0, 1)))
x31 ∈{0,1}3 \X1001
o
,
(126)
+ w(1, x1,3 , χ3 ((0, 0, 1)))
max

X1001 = arg 3 max {w(0, x1,1 , χ1 ((0, 0, 1))) + w(0, x1,2 , χ2 ((0, 0, 1))) + w(1, x1,3 , χ3 ((0, 0, 1)))},
x1 ∈{0,1}3

(127)


W010 (fS , χS ) = p (1 − p) P0 (fS ) ×
2

max
3

x1 ∈{0,1}3

n
w(0, x1,1 , χ1 (0, 1, 0)) + w(1, x1,2 , χ2 (0, 1, 0))

!
o
+ w(0, x1,3 , χ3 (0, 1, 0))

n
w(0, x1,1 , χ1 (0, 1, 0)) + w(1, x1,2 , χ2 (0, 1, 0))+
x31 ∈{0,1}3 \X1010
o
w(0, x1,3 , χ3 (0, 1, 0))
,
(128)

+ (1 − P0 (fS )) ×



max

X1010 = arg 3 max {w(0, x1,1 , χ1 (0, 1, 0)) + w(1, x1,2 , χ2 (0, 1, 0)) + w(0, x1,3 , χ3 (0, 1, 0))},
x1 ∈{0,1}3


W100 (fS , χS ) = p (1 − p) P0 (fS ) ×
2

max
3

x1 ∈{0,1}3

(129)

n
w(1, x1,1 , χ1 ((1, 0, 0))) + w(0, x1,2 , χ2 ((1, 0, 0)))
!

+ w(0, x1,3 , χ3 ((1, 0, 0)))}
+ (1 − P0 (fS )) ×



{w(1, x1,1 , χ1 ((1, 0, 0))) + w(0, x1,2 , χ2 ((1, 0, 0)))

+ w(0, x1,3 , χ3 ((1, 0, 0)))} ,
(130)
max

x31 ∈{0,1}3 \X1100

X1100 = arg 3 max {w(1, x1,1 , χ1 ((1, 0, 0))) + w(0, x1,2 , χ2 ((1, 0, 0))) + w(0, x1,3 , χ3 ((1, 0, 0)))},
x1 ∈{0,1}3

(131)


3
W111 (fS , χS ) = (1 − p) P0 (fS ) ×
+ (1 − P0 (fS )) ×

August 15, 2017

max

x31 ∈{0,1}3

max

3
nX

x31 ∈{0,1}3 \X1111

w(1, x1,n , χn ((1, 1, 1)))

n=1

3
nX

n=1

!

!
o 
w(1, x1,n , χn ((1, 1, 1)))
,

(132)

DRAFT

42

X1111

W011 (fS χS ) = p(1 − p)

2

"

= arg 3 max {
x1 ∈{0,1}3

P0 (fS ) ×



3
X

w(1, x1,n , χn ((1, 1, 1)))},

(133)

n=1

max
3

x1 ∈{0,1}3

n
w(0, x1,1 , χ1 ((0, 1, 1))) + w(1, x1,2 , χ2 ((0, 1, 1)))

o
+ w(1, x1,3 , χ3 ((0, 1, 1)))

n
+ (1 − P0 ((fS ))) ×
max
w(0, x1,1 , χ1 ((0, 1, 1))) + w(1, x1,2 , χ2 ((0, 1, 1)))+
x31 ∈{0,1}3 \X1011
#
o
,
(134)
w(1, x1,3 , χ3 ((0, 1, 1)))
X1011 = arg 3 max {w(0, x1,1 , χ1 ((0, 1, 1))) + w(1, x1,2 , χ2 ((0, 1, 1))) + w(1, x1,3 , χ3 ((0, 1, 1)))},
x1 ∈{0,1}3

W101 (fS , χS ) = p(1 − p)

(135)
2

"

P0 (fS ) ×



max
3

x1 ∈{0,1}3

n
w(1, x1,1 , χ1 ((1, 0, 1))) + w(0, x1,2 , χ2 ((1, 0, 1)))

o
+ w(1, x1,3 , χ3 ((1, 0, 1)))

n
w(1, x1,1 , χ1 ((1, 0, 1))) + w(0, x1,2 , χ2 ((1, 0, 1)))+
+ (1 − P0 (fS )) ×
max
x31 ∈{0,1}3 \X1101
#
o
w(1, x1,3 , χ3 ((1, 0, 1)))
,
(136)
X1101 = arg 3 max

x1 ∈{0,1}3

n
o
w(1, x1,1 , χ1 ((1, 0, 1))) + w(0, x1,2 , χ2 ((1, 0, 1))) + w(1, x1,3 , χ3 ((1, 0, 1))) ,

W110 (fS , χS ) = p(1 − p)

(137)

2

"

P0 (fS ) ×

+ (1 − P0 (fS )) ×





max
3

x1 ∈{0,1}3

n
w(1, x1,1 , χ1 ((1, 1, 0))) + w(1, x1,2 , χ2 ((1, 1, 0)))

o
+ w(0, x1,3 , χ3 ((1, 1, 0)))

n
w(1, x1,1 , χ1 ((1, 1, 0))) + w(1, x1,2 , χ2 ((1, 1, 0)))
x31 ∈{0,1}3 \X1110
#
o
+ w(0, x1,3 , χ3 ((1, 1, 0)))
,
(138)
max

X1110 = arg 3 max {w(1, x1,1 , χ1 ((1, 1, 0))) + w(1, x1,2 , χ2 ((1, 1, 0))) + w(0, x1,3 , χ3 ((1, 1, 0)))}.
x1 ∈{0,1}3

August 15, 2017

(139)

DRAFT

43

In the case of Table VI, P0 (fS ) is given by








P0 (fS ) = P x30 = (0, 0, 0) + P x30 = (0, 0, 1) + P x30 = (0, 1, 0) + P x30 = (0, 1, 1)




+ P x30 = (1, 0, 0) + P x30 = (1, 0, 1)

(140)

= p(2 − p)

(141)

3
.
4

(142)

p= 21

=

R EFERENCES
[1] B. Larrousse and S. Lasaulce, “Coded power control: Performance analysis,” in Proc. of IEEE International Symposium
on Information Theory, Istanbul, Turkey, July 2013.
[2] S. Lasaulce and B. Larrousse, “More about optimal use of communication resources,” in Proc. of International Workshop
on Stochastic Methods in Game Theory, International School of Mathematics G. Stampacchia, Erice, Italy, September
2013.
[3] B. Larrousse, A. Agrawal, and S. Lasaulce, “Implicit coordination in two-agent team problems; application to distributed
power allocation,” in Proc. of 12th IEEE International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and
Wireless Networks, 2014, pp. 579–584.
[4] T. Başar and S. Yüksel, Stochastic Networked Control Systems, Birhäuser, Ed.

Springer, 2013, vol. XVIII.

[5] P. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity.” IEEE Transactions on Information Theory, vol. 56,
no. 9, pp. 4181–4206, 2010.
[6] P. Cuff, “Distributed channel synthesis,” IEEE Transactions on Information Theory, vol. 59, no. 11, pp. 7071–7096, 2013.
[7] G. Kramer and S. A. Savari, “Communicating probability distributions,” IEEE Transactions on Information Theory, vol. 53,
no. 2, pp. 518–525, February 2007.
[8] T. Han and S. Verdú, “Approximation theory of output statistics,” IEEE Transactions on Information Theory, vol. 39, no. 3,
pp. 752–772, May 1993.
[9] A. Bereyhi, M. Bahrami, M. Mirmohseni, and M. Aref, “Empirical coordination in a triangular multiterminal network,” in
Proc. of IEEE International Symposium on Information Theory, Istanbul, Turkey, July 2013, pp. 2149–2153.
[10] F. Haddadpour, M. H. Yassaee, A. Gohari, and M. R. Aref, “Coordination via a relay,” in Proc of IEEE International
Symposium on Information Theory, Boston, MA, July 2012, pp. 3048–3052.
[11] M. R. Bloch and J. Kliewer, “Strong coordination over a line network,” in Proc. IEEE International Symposium on
Information Theory, Istanbul, Turkey, July 2013, pp. 2319–2323.
[12] ——, “Strong coordination over a three-terminal relay network,” in Proc. of IEEE Information Theory Workshop, Hobart,
Tasmania, November 2014, pp. 646–650.
[13] R. Blasco-Serrano, R. Thobaben, and M. Skoglund, “Polar codes for coordination in cascade networks,” in Proc. of
International Zurich Seminar on Communications, Zurich, Switzerland, March 2012, pp. 55–58.
[14] M. R. Bloch, L. Luzzi, and J. Kliewer, “Strong coordination with polar codes,” in Proc. of 50th Allerton Conference on
Communication, Control, and Computing, Monticello, IL, 2012, pp. 565–571.
[15] R. A. Chou, M. R. Bloch, and J. Kliewer, “Polar coding for empirical and strong coordination via distribution
approximation,” in Proc. of IEEE International Symposium on Information Theory, Hong Kong, June 2015, pp. 1512–
1516.

August 15, 2017

DRAFT

44

[16] O. Gossner, P. Hernandez, and A. Neyman, “Optimal use of communication resources,” Econometrica, vol. 74, no. 6, pp.
1603–1636, 2006.
[17] P. Cuff and L. Zhao, “Coordination using implicit communication,” in Proc. of IEEE Information Theory Workshop, Paraty,
Brazil, 2011, pp. 467–471.
[18] E. van der Meulen, “A survey of multi-way channels in information theory: 1961-1976,” IEEE Transactions on Information
Theory, vol. 23, no. 1, pp. 1–37, Jan 1977.
[19] F. Willems and E. van der Meulen, “The discrete memoryless multiple-access channel with cribbing encoders,” IEEE
Transactions on Information Theory, vol. 31, no. 3, pp. 313–327, May 1985.
[20] H. Asnani and H. Permuter, “Multiple-access channel with partial and controlled cribbing encoders,” IEEE Transactions
on Information Theory, vol. 59, no. 4, pp. 2252–2266, April 2013.
[21] T. Weissman, “Capacity of channels with action-dependent states,” IEEE Transactions on Information Theory, vol. 56,
no. 11, pp. 5396–5411, Nov 2010.
[22] W. Yu, G. Ginis, and J. M. Cioffi, “Distributed multiuser power control for digital subscriber lines,” IEEE Journal on
Selected Areas in Communications, vol. 20, no. 5, pp. 1105–1115, Jun. 2002.
[23] S. Lasaulce and H. Tembine, Game Theory and Learning for Wireless Networks : Fundamentals and Applications.
Academic Press, 2011.
[24] A. Zappone, S. Buzzi, and E. Jorswieck, “Energy-efficient power control and receiver design in relay-assisted DS/CDMA
wireless networks via game theory,” IEEE Communications Letters, vol. 15, no. 7, pp. 701–703, July 2011.
[25] G. Bacci, L. Sanguinetti, M. Luise, and H. Poor, “A game-theoretic approach for energy-efficient contention-based
synchronization in OFDMA systems,” IEEE Transactions on Signal Processing, vol. 61, no. 5, pp. 1258–1271, 2013.
[26] G. Scutari, D. Palomar, and S. Barbarossa, “The MIMO iterative waterfilling algorithm,” IEEE Transactions on Signal
Processing, vol. 57, no. 5, pp. 1917–1935, May 2009.
[27] P. Mertikopoulos, E. V. Belmega, A. L. Moustakas, and S. Lasaulce, “Distributed learning policies for power allocation in
multiple access channels,” IEEE Journal on Selected Areas in Communications, vol. 30, no. 1, pp. 96–106, January 2012.
[28] S. Gel’Fand and M. S. Pinsker, “Coding for channel with random parameters,” Probl. Contr. Inform. Theory, vol. 9, no. 1,
pp. 19–31, 1980.
[29] Y.-H. Kim, A. Sutivong, and T. Cover, “State amplification,” IEEE Transactions on Information Theory, vol. 54, no. 5,
pp. 1850–1859, 2008.
[30] C. Choudhuri, Y.-H. Kim, and U. Mitra, “Capacity-distortion trade-off in channels with state,” in Proc. of 48th Annual
Allerton Conference on Communication, Control, and Computing, 2010, pp. 1311–1318.
[31] ——, “Causal state amplification,” in Proc. of IEEE International Symposium on Information Theory Proceedings, Saint
Petersburg, Russia, August 2011, pp. 2110–2114.
[32] C. Choudhuri and U. Mitra, “Action dependent strictly causal state communication,” in Proc. of IEEE International
Symposium on Information Theory, 2012, pp. 3058–3062.
[33] P. Cuff and C. Schieler, “Hybrid codes needed for coordination over the point-to-point channel,” in Proc. of 49th Annual
Allerton Conference on Communication, Control, and Computing, Monticello, IL, 2011, pp. 235–239.
[34] B. Larrousse, S. Lasaulce, and M. Wigger, “Coordinating partially-informed agents over state-dependent networks,” in
Proc. of Information Theory Workshop, Jerusalem, Israel, April 2015, pp. 1–5.
[35] Q. Li, D. Gesbert, and N. Gresset, “Joint precoding over a master-slave coordination link,” in Proc. of the IEEE International
Conference on Acoustics Speech and Signal Processing (ICASSP), Florence, Italy, May 2014.
[36] T. M. Cover and J. A. Thomas, Elements of Information Theory.

August 15, 2017

Wiley-Interscience, 2006.

DRAFT

45

[37] D. Goodman and N. Mandayam, “Power control for wireless data,” IEEE Personal Communications, vol. 7, no. 2, pp.
45–54, April 2000.
[38] B. Fourestié, “Communication switching method, access point, network controller and associated computer programs,”
France Telecom, Patent WO 2008/081137, Dec. 2007.
[39] M. Olama, S. Djouadi, and C. Charalambous, “Stochastic power control for time-varying long-term fading wireless
networks,” EURASIP Journal on Applied Signal Processing, 2006.
[40] M. Malmirchgini and Y. Mostofi, “On the spatial predictability of commucation channels,” IEEE Transactions on Vehicular
Technology, 2012.
[41] A. El Gamal and Y. Kim, Network Information Theory.

Cambridge University Press, 2011.

[42] N. Merhav and S. Shamai, “On joint source-channel coding for the Wyner-Ziv source and the Gel’fand-Pinsker channel,”
IEEE Transactions on Information Theory, vol. 49, no. 11, pp. 2844–2855, 2003.
[43] S. Haykin, “Cognitive radio: brain-empowered wireless communications,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 2, pp. 201–220, 2005.
[44] M. L. Treust and S. Lasaulce, “A repeated game formulation of energy-efficient decentralized power control,” IEEE
Transactions on Wireless Communications, vol. 9, no. 9, pp. 2860–2869, September 2010.
[45] T. M. Cover and M. Chiang, “Duality between channel capacity and rate distortion with two-sided state information,” IEEE
Transactions on Information Theory, vol. 48, no. 6, pp. 1629–1638, 2002.
[46] C. E. Shannon, “A mathematical theory of communication,” Bell System Technical Journal, vol. 27, pp. 379–423, 1948.
[47] S. P. Boyd and L. Vandenberghe, Convex optimization.

Cambridge University Press, 2004.

[48] A. Gjendemsj, D. Gesbert, G. E. Oien, and S. G. Kiani, “Binary power control for sum rate maximization over multiple
interfering links,” IEEE Transactions on Wireless Communications, vol. 7, no. 8, pp. 3164–3173, 2008.
[49] F. Meshkati, H. Poor, and S. Schwartz, “Energy-efficient resource allocation in wireless networks: An overview of game
theoretic approaches,” IEEE Signal Processing Magazine, vol. 58, pp. 58–68, May 2007.
[50] E. V. Belmega and S. Lasaulce, “Energy-efficient precoding for multiple-antenna terminals,” IEEE Transactions on Signal
Processing, vol. 59, no. 1, pp. 329–340, January 2011.
[51] V. S. Varma, S. Lasaulce, Y. Hayel, and S. E. Elayoubi, “A cross-layer approach for distributed energy-efficient power
control in interference networks,” IEEE Transactions on Vehicular Technology, vol. 75, no. 7, pp. 3218 – 3232, 2015.

August 15, 2017

DRAFT

46

TABLE I
S UMMARY OF NOTATION USED THROUGHOUT THE PAPER .

Symbol

Meaning

Z

A generic random variable

Zij

Sequence of random variables (Zi , . . . , Zj ), j ≥ i

Z n or Z
Z
|Z|
∆(Z)
z
z n or z

EP
H(Z)

Zij when i = 1 and j = n

Alphabet of Z
Cardinality of Z

Unit simplex over Z
Realization of Z

Sequence or vector (z1 , . . . , zn )
Expectation operator under the probability P
Entropy of Z

I(Y ; Z)

Mutual information between Y and Z

Z1 − Z2 − Z3

Markov chain P(z1 |z2 , z3 ) = P(z1 |z2 )

1{.}

Indicator function

⊕

Modulo−2 addition

R+

[0, +∞)

Tn (Q)

{z n ∈ Z n : kTz n − Qk1 < }

δ()

A function of  such that lim→0 δ() = 0

Tz n

Type of the sequence z n

TABLE II
E NCODING AND DECODING USED IN THE PROOF OF T HEOREM 5

August 15, 2017

Block

1

2

b

···

B

Message

···

i1

i2

State

···

iB

(2)
x0

···

ib

(1)
x0

Agent 2 action

x∗2

Agent 1 codeword

u1 (i1 , j1 )

u(i2 , j2 )

Agent 1 action

(1)
x1

x2 (bi1 )
(2)
x1

Agent 2 decoding

bi1

bi2

···
···
···
···
···

(b)
x0

x2 (bib−1 )
u(ib , jb )
(b)
x1

bib

···
···
···
···
···

(B)

x0

x2 (biB−1 )
u(iB jB )
(B)

x1

biB
DRAFT

47

TABLE III
C HOSEN INDEXATION FOR THE PAYOFF VECTOR w
BLOCKS OF SIZE

n1 n2 ny nu

AND PROBABILITY DISTRIBUTION VECTOR

q. B OLD LINES DELINEATE

AND EACH BLOCK CORRESPONDS TO A GIVEN VALUE OF THE RANDOM STATE

X0 . T HE

5−UPLETS ARE SORTED ACCORDING TO A LEXICOGRAPHIC ORDER .
Index of qi

X0

X1

X2

Y

U

1

1

1

1

1

1

2
..
.

1
..
.

1
..
.

1
..
.

1
..
.

2

nu

1

1

1

1

nu

nu + 1
..
.

1
..
.

1
..
.

1
..
.

2
..
.

1
..
.

2nu
..
.

1
..
.

1
..
.

1
..
.

2
..
.

nu
..
.

n1 n2 ny nu − nu + 1
..
.

1
..
.

n1
..
.

n2
..
.

ny
..
.

1
..
.

n1 n2 ny nu

1

n1

n2

ny

nu

..
.
..
.

..
.
..
.

..
.
..
.

..
.
..
.

..
.
..
.

..
.
..
.

(n0 − 1)n1 n2 ny nu + 1
..
.

n0
..
.

1
..
.

1
..
.

1
..
.

1
..
.

n0 n1 n2 ny nu

n0

n1

n2

ny

nu

TABLE IV
O PTIMAL MARGINAL AND JOINT DISTRIBUTIONS ( EXPRESSED IN %) FOR THE SUM - RATE PAYOFF FUNCTION OF THE CCPC
 10 20
POLICY, WITH SNR = 10 D B AND WITH FOUR POSSIBLE TRANSMIT POWER LEVELS 0, 3 , 3 , 10 .

?

?

?

(QX1 (x1 ), QX2 (x2 ), QX1 X2 (x1 , x2 ))

x1 = 0

x1 =

10
3

x1 =

20
3

x1 = 10

in %

August 15, 2017

x2 = 00

(47.5,47.5,00.0)

(00.0,47.5,00.0)

(00.0,47.5,00.0)

(52.5,47.5,47.5)

x2 =

10
3

(47.5,00.0,00.0)

(00.0,00.0,00.0)

(00.0,00.0,00.0)

(52.5,00.0,00.0)

x2 =

20
3

(47.5,00.0,00.0)

(00.0,00.0,00.0)

(00.0,00.0,00.0)

(52.5,00.0,00.0)

x2 = 10

(47.5,52.5,47.5)

(00.0,52.5,00.0)

(00.0,52.5,00.0)

(52.5,52.5,05.5)

DRAFT

48

TABLE V
O PTIMAL MARGINAL AND JOINT DISTRIBUTIONS ( EXPRESSED IN %) FOR THE SUM - RATE PAYOFF FUNCTION OF THE CPC
 10 20
POLICY, WITH SNR = 10 D B AND WITH FOUR POSSIBLE TRANSMIT POWER LEVELS 0, 3 , 3 , 10 .

?

?

?

(QX1 (x1 ), QX2 (x2 ), QX1 X2 (x1 , x2 ))

x1 = 0

x1 =

10
3

x1 =

20
3

x1 = 10

in %
x2 = 00

(44.4,50.4,00.1)

(02.6,50.4,00.9)

(08.0,50.4,06.5)

(45.0,50.4,42.9)

x2 =

10
3

(44.4,00.0,00.0)

(02.6,00.0,00.0)

(08.0,00.0,00.0)

(45.0,00.0,00.0)

x2 =

20
3

(44.4,00.0,00.0)

(02.6,00.0,00.0)

(08.0,00.0,00.0)

(45.0,00.0,00.0)

x2 = 10

(44.4,49.6,44.3)

(02.6,49.6,01.7)

(08.0,49.6,01.5)

(45.0,49.6,02.1)

TABLE VI
P ROPOSED SOURCE CODING AND DECODING FOR p = 21 .

x30
Index i =

fS (x30 )

gS (i)

000

001

010

011

100

101

110

111

m0

m0

m0

m0

m0

m0

m1

m1

111

111

111

111

111

111

001

001

TABLE VII
P ROPOSED CHANNEL CODING FOR p = 12 .

x30 (b)

000

001

010

011

100

101

110

111

x32 (b)

111

111

111

111

111

111

001

001

ib+1

m0

m1

m0

m1

m0

m1

m0

m1

m0

m1

m0

m1

m0

m1

m0

m1

x31 (b)

000

001

001

000

010

000

011

001

100

000

101

001

110

111

111

110

August 15, 2017

DRAFT

