Can Negligible Cooperation Increase Capacity?
The Average-Error Case
Parham Noorzad, Michelle Effros, Michael Langberg

Abstract

arXiv:1801.03655v1 [] 11 Jan 2018

In communication networks, cooperative strategies are coding schemes where network nodes work together to
improve network performance metrics such as sum-rate. This work studies encoder cooperation in the setting of a
discrete multiple access channel with two encoders and a single decoder. A node in the network that is connected to
both encoders via rate-limited links, referred to as the cooperation facilitator (CF), enables the cooperation strategy.
Previously, the authors presented a class of multiple access channels where the average-error sum-capacity has an
infinite derivative in the limit where CF output link capacities approach zero. The authors also demonstrated that for
some channels, the maximal-error sum-capacity is not continuous at the point where the output link capacities of the
CF equal zero. This work shows that the the average-error sum-capacity is continuous when CF output link capacities
converge to zero; that is, the infinite derivative of the average-error sum-capacity is not a result of its discontinuity
as in the maximal-error case.
Index Terms
Continuity, cooperation facilitator, edge removal problem, maximal-error capacity region, multiple access channel.

I. I NTRODUCTION
Interference is an important limiting factor in the capacity performance of communication networks. One way
to reduce interference is for nodes in the network to work together to coordinate their transmissions. Any such
strategy falls under the general definition of cooperation.
While strategies such as time-sharing are one form of cooperation, the model we consider here is closer to
the “conferencing” cooperation model [1]. In conferencing, unlike time-sharing, encoders share information about
the messages they wish to transmit. In contrast to conferencing however, our cooperation model employs indirect
communication; that is, the encoders communicate through another node which we call the cooperation facilitator
(CF) [2], [3]. Figure 1 depicts the CF model in the two-user multiple access channel (MAC) scenario.
The CF enables cooperation between the encoders through its rate-limited input and output links. Prior to the
transmission of its codeword over the channel, each encoder sends a function of its message to the CF. The CF,
This material is based upon work supported by the National Science Foundation under Grant Numbers 1527524 and 1526771.
P. Noorzad was with the California Institute of Technology, Pasadena, CA 91125 USA. He is now with Qualcomm Research, San Diego, CA
92122 USA (email: parham@qti.qualcomm.com).
M. Effros is with the California Institute of Technology, Pasadena, CA 91125 USA (email: effros@caltech.edu).
M. Langberg is with the State University of New York at Buffalo, Buffalo, NY 14260 USA (email: mikel@buffalo.edu).

1

Figure 1. A network consisting of two encoders that initially cooperate via a CF and then, based on the information they receive, transmit their
codewords over the MAC to the decoder.

using the information it receives from both encoders, computes a rate-limited function for each encoder. It then
transmits the computed values over its output links. Each encoder then selects a codeword using its message and
the information it receives from the CF.
To simplify our discussion in this section, suppose the CF input link capacities both equal Cin and the CF output
link capacities both equal Cout . If Cin ≤ Cout , then the optimal strategy for the CF is “forwarding” [3]; that is,
the CF simply forwards the information it receives from one encoder to the other. Using the capacity region of
the MAC with conferencing encoders [1], it follows that the average-error sum-capacity gain of CF cooperation is
bounded from above by 2Cin and does not explicitly depend on Cout . In the situation where Cin > Cout , however,
the situation is more complicated since the CF can no longer forward all its incoming information. While the 2Cin
upper bound is still valid, the dependence of the sum-capacity gain on Cout is less clear. If the CF simply forwards
part of the information it receives, then again by [1], the average-error sum-capacity gain is at most 2Cout . While
the 2Cout bound has an intuitive interpretation, in the sense that it reflects the amount of information the CF shares
with the encoders, a much larger gain is possible. Specifically, in prior work [3], we show that for a class of MACs
which includes the binary adder MAC,1 for fixed Cin > 0, the average-error sum-capacity has a derivative in Cout
that is infinite at Cout = 0; that is, for small Cout , the gain resulting from cooperation exceeds any function with
bounded derivative.
The large sum-capacity gain described above is not limited to the average-error scenario. In fact, in related work
[2], we show that for any MAC for which the average-error sum-capacity is strictly greater than the maximal-error
sum-capacity in the absence of cooperation, adding a CF and measuring the maximal-error sum-capacity for fixed
Cin > 0 gives a curve that is discontinuous at Cout = 0. In this case, we say that “negligible cooperation” results
in a non-negligible benefit.2
Given these earlier results, the following question remains open: For fixed Cin > 0, can the average-error sumcapacity ever be discontinuous in Cout ? In the present work, we show that the answer is negative; that is, the
1 The
2 In

binary adder MAC defined as Y = X1 + X2 , where X1 , X2 ∈ {0, 1}, and Y ∈ {0, 1, 2}.

[4], Langberg and Effros further show that in a certain network, the transmission of even a single bit (over the entire blocklength) can

strictly increase maximal-error capacity.

2

average-error sum-capacity is continuous even at Cout = 0.
A related average-error continuity problem is the case of rate-limited feedback over the MAC. For such a
network, Sarwate and Gastpar [5], using the dependence-balance bounds of Hekstra and Willems [6], show that
as the feedback rate converges to zero, the average-error capacity region converges to the average-error capacity
region of the same MAC in the absence of feedback.
The problem we study here can also be formulated as an “edge removal problem” as introduced by Ho, Effros,
and Jalali [7], [8]. The edge removal problem seeks to quantify the capacity effect of removing a single edge from
a network. Except in the MAC with CF setting and a number of cases described in [7], [8], the problem remains
open. In fact, Effros and Langberg show that this problem is connected to a number of other open problems in
network coding, including the difference between the 0-error and -error capacity regions [9] and the difference
between the lossless source coding regions for independent and dependent sources [10].
The question of whether the capacity region of a network consisting of noiseless links is continuous with respect
to the link capacities is investigated by Gu, Effros, and Bakshi [11] and Chan and Grant [12]. The present work
differs from [11], [12] in the network under consideration; while our network does have noiseless links (the CF
input and output links), it also contains a multiterminal component (the MAC) which may exhibit interference or
noise.
In [13], Kosut and Kliewer present different variations of the edge removal problem in a unified setting. In their
terminology, the present work investigates whether the network consisting of a MAC and a CF satisfies the “weak
edge removal property” with respect to the average-error reliability criterion. In [14, Chapter 1], we discuss the
known results for each variation of the edge removal problem.

II. T HE C OOPERATION FACILITATOR M ODEL
In this work, we study cooperation between two encoders that communicate their messages to a decoder over a
discrete, memoryless, and stationary MAC. Such a MAC can be represented by the triple

X1 × X2 , p(y|x1 , x2 ), Y ,
where X1 , X2 , and Y are finite sets and p(y|x1 , x2 ) is a conditional probability mass function. The nth extension
of the channel is given by
p(y n |xn1 , xn2 ) :=

n
Y

p(yt |x1t , x2t ).

t=1

For each positive integer n, called the “blocklength,” and nonnegative real numbers R1 and R2 , called the “rates,”
we next define a

2nR1 , 2nR2 , n -code
1
2
1
2
for communication over a MAC with a (Cin , Cout )-CF. Here Cin = (Cin
, Cin
) and Cout = (Cout
, Cout
) represent

the capacities of the CF input and output links, respectively. (See Figure 1.)

3

For i ∈ {1, 2}, the transmission of encoder i to the CF is represented by a mapping3
i

ϕi : [2nRi ] → [2nCin ].
The CF, based on the information it receives from the encoders, computes a function
1

2

i

ψi : [2nCin ] × [2nCin ] → [2nCout ]
for encoder i, where i ∈ {1, 2}. Encoder i, using its message and what it receives from the CF, selects a codeword
according to
i

fi : [2nRi ] × [2nCout ] → Xin .
The decoder, using the channel output, aims to find the transmitted messages. It is represented by a mapping
g : Y n → [2nR1 ] × [2nR2 ].
The collection of mappings
ϕ1 , ϕ2 , ψ1 , ψ2 , f1 , f2 , g



defines a (2nR1 , 2nR2 , n)-code for the MAC with a (Cin , Cout )-CF.4
For a fixed code, the error probability for a particular message pair (w1 , w2 ) is given by
X
λn (w1 , w2 ) :=
p(y n |f1 (w1 , z1 ), f2 (w2 , z2 )),
y n : g(y n )6=(w1 ,w2 )

where z1 and z2 are the CF outputs. For i ∈ {1, 2}, zi is calculated according to

zi = ψi ϕ1 (w1 ), ϕ2 (w2 ) .
The average probability of error is given by
(n)
:=
Pe,avg

1

X

2n(R1 +R2 )

λn (w1 , w2 ),

w1 ,w2

and the maximal probability of error is given by
(n)
:= max λn (w1 , w2 ).
Pe,max
w1 ,w2

A rate pair (R1 , R2 ) is achievable with respect to the average-error reliability criterion if there exists a sequence
(n)

of (2nR1 , 2nR2 , n)-codes such that Pe,avg → 0 as n → ∞. The average-error capacity region of a MAC with a
(Cin , Cout )-CF, denoted by Cavg (Cin , Cout ), is the closure of the set of all rate pairs that are achievable with
respect to the average-error reliability criterion. The average-error sum-capacity is defined as
Csum,avg (Cin , Cout ) :=
(n)

max

Cavg (Cin ,Cout )

(R1 + R2 )

(n)

By replacing Pe,avg with Pe,max , we can similarly define achievable rates with respect to the maximalerror reliability criterion, the maximal-error capacity region, and the maximal-error sum-capacity. For a MAC
3 Henceforth,

for every x ≥ 1, [x] denotes the set {1, . . . , bxc}.

4 Technically,

the definition we present here is for a single round of cooperation. Similar to [2], it is possible to define cooperation via a CF

over multiple rounds. However, this general scenario does not alter our main proofs.

4

with a (Cin , Cout )-CF, we denote the maximal-error capacity region and sum-capacity by Cmax (Cin , Cout ) and
Cmax (Cin , Cout ), respectively.
III. P RIOR R ESULTS ON THE S UM -C APACITY G AIN OF C OOPERATION
We next describe results from [2], [3] that are relevant to our discussion here. We begin with sum-capacity results
in the average-error case.
Consider a discrete MAC (X1 × X2 , p(y|x1 , x2 ), Y). Let pind (x1 )pind (x2 ) be a distribution that satisfies
Iind (X1 , X2 ; Y ) =

max
p(x1 )p(x2 )

I(X1 , X2 ; Y ).

(1)

In addition, suppose that there exists a distribution pdep (x1 , x2 ) whose support is contained in the support of
pind (x1 )pind (x2 ), and satisfies

Idep (X1 , X2 ; Y ) + D pdep (y)kpind (y) > Iind (X1 , X2 ; Y ).

(2)

Let C ∗ denote the class of all discrete MACs for which input distributions pind and pdep , as described above, exist.
Then the following theorem [3, Theorem 3] holds.
Theorem 1. Let (X1 × X2 , p(y|x1 , x2 ), Y) be a MAC in C ∗ , and suppose (Cin , v) ∈ R2>0 × R2>0 . Then
lim+

h→0

Csum,avg (Cin , hv) − Csum,avg (Cin , 0)
= ∞.
h

Consider a MAC in C ∗ with a CF that has input links with equal capacity Cin and output links with equal
capacity Cout . Then Theorem 1 implies that for fixed Cin > 0, the average-error sum-capacity has a derivative in
Cout that is infinite at Cout = 0.5
We next describe the maximal-error sum-capacity gain. While it is possible in the average-error scenario to
achieve a sum-capacity that has an infinite slope, more is known in the maximal-error case. There exists a class of
MACs for which the maximal-error sum-capacity exhibits a discontinuity in the capacities of the CF output links.
This is stated formally in the next proposition, which is a special case of [2, Proposition 5].
Proposition 2. Consider a discrete MAC for which6
Csum,avg (0, 0) > Csum,max (0, 0);

(3)

that is, the average-error sum-capacity is strictly greater than the maximal-error sum-capacity. Fix Cin ∈ R2>0 .
Then Csum,max (Cin , Cout ) is not continuous at Cout = 0.
The possibility of an infinite derivative in the average-error case (Theorem 1) and a discontinuity in the maximalerror scenario (Proposition 2) leads to the following question: Does there exist any MAC and any Cin for which
5 Note

that Theorem 1 does not lead to any conclusions regarding continuity; a function f (x) with infinite derivative at x = 0 can be
√
continuous (e.g., f (x) = x) or discontinuous (e.g., f (x) = dxe).
6 Dueck

in [2].

[15] gives the first proof of the existence of a discrete MAC which satisfies (3). We investigate further properties of Dueck’s MAC

5

Csum,avg (Cin , Cout ) is not continuous at Cout = 0? This problem is posed in [2, Section IV]. We address this
question in the next section, where we describe our results.
IV. C ONTINUITY OF AVERAGE - AND M AXIMAL -E RROR S UM -C APACITIES
In the prior section, for a fixed Cin , we discuss previous results regarding the continuity of Csum,avg (Cin , Cout )
and Csum,max (Cin , Cout ) as a function of Cout at Cout = 0. In this section, we do not limit ourselves to the point
Cout = 0; rather, we study the continuity of Csum,avg (Cin , Cout ) over its entire domain.
We begin by considering the case where the CF has full access to the messages. Formally, for a given discrete
∗1
∗2
MAC (X1 × X2 , p(y|x1 , x2 ), Y), let the components of C∗in = (Cin
, Cin
) be sufficiently large so that any CF with
∗1
∗2
input link capacities Cin
and Cin
has full knowledge of the encoders’ messages. For example, we can choose C∗in

such that
∗1
∗2
min{Cin
, Cin
} > max I(X1 , X2 ; Y ).
p(x1 ,x2 )

Our first result addresses the continuity of Csum,avg (C∗in , Cout ) as a function of Cout over R2≥0 .
Theorem 3. For any discrete MAC, the mapping
Cout 7→ Csum,avg (C∗in , Cout ),

(4)

defined on R2≥0 is continuous.
We provide an overview of the proof in Section V and present the details in Section VII.
While Theorem 3 focuses on the scenario where Cin = C∗in , its result is sufficiently strong to address the
continuity problem for a fixed, arbitrary Cin at Cout = 0. To see this, note that for all Cin ∈ R2≥0 ,
Csum,avg (Cin , 0) ≤ Csum,avg (Cin , Cout ) ≤ Csum,avg (C∗in , Cout ).

(5)

Corollary 4, below, now follows from Theorem 3 by letting Cout approach zero in (5) and noting that for all
Cin ∈ R2≥0 ,
Csum,avg (C∗in , 0) = Csum,avg (Cin , 0) = Csum,avg (0, 0).
Corollary 4. For any discrete MAC and any Cin ∈ R2≥0 , the mapping
Cout 7→ Csum,avg (Cin , Cout ),
is continuous at Cout = 0.
Recall that Proposition 2 gives a sufficient condition under which Csum,max (Cin , Cout ) is not continuous at
Cout = 0 for a fixed Cin ∈ R2>0 . From Corollary 4, it follows that the sufficient condition is necessary as well.
This is stated in the next corollary. The proof appears in Section VII.
Corollary 5. Fix a discrete MAC and Cin ∈ R2>0 . Then Csum,max (Cin , Cout ) is not continuous at Cout = 0 if
and only if
Csum,avg (0, 0) > Csum,max (0, 0).

(6)

6

We next describe the second main result of this paper. Our first main result, Theorem 3, shows the continuity
of Csum,avg (C∗in , Cout ) over R2≥0 . The next result shows that proving the continuity of Csum,avg (Cin , Cout ) over
R2≥0 × R2≥0 is equivalent to demonstrating its continuity on certain axes. Specifically, it suffices to check the
1
2
continuity of Csum,avg when one of Cout
and Cout
is approaching zero, while the other arguments of Csum,avg are

fixed positive numbers.
Theorem 6. For any discrete MAC, the mapping
(Cin , Cout ) 7→ Csum,avg (Cin , Cout ),

(7)

defined on R2≥0 × R2≥0 is continuous if and only if for all (Cin , Cout ) ∈ R2>0 × R2>0 , we have
lim
1 →0+
C̃out

lim
2 →0+
C̃out



1
2
2
Csum,avg Cin , (C̃out
, Cout
) = Csum,avg Cin , (0, Cout
)


1
2
1
Csum,avg Cin , (Cout
, C̃out
) = Csum,avg Cin , (Cout
, 0) .

We remark that using a time-sharing code, it is possible to show that Csum,avg is concave on R2≥0 × R2≥0 , and
thus continuous on its interior. Thus it suffices to study the continuity of Csum,avg on the boundary of R2≥0 × R2≥0 .
Sections V and VI provide proof overviews of Theorem 3 and Theorem 6, respectively. Detailed proofs of the
lemmas presented in these sections appear in Section VII.
V. C ONTINUITY OF S UM -C APACITY: T HE Cin = C∗in C ASE
We start our study of the continuity of Csum (C∗in , Cout )7 by presenting lower and upper bounds in terms of
an auxiliary function σ(δ) defined for δ ≥ 0 (Lemma 8). A similar function appears in Dueck [16]; our function
differs with [16] in a time-sharing random variable. This random variable, denoted by U below, plays two roles.
First it ensures σ is concave, which immediately proves the continuity of σ over R>0 . Second, together with a
lemma from [16] (Lemma 11 below), it helps us find a single-letter upper bound for σ (Corollary 12). We then use
the single-letter upper bound to prove continuity at δ = 0.
The following definitions are useful for the description of our lower and upper bounds for Csum (C∗in , Cout ). For
every finite alphabet U and all δ ≥ 0, define
n
o
(n)
PU (δ) := p(u, xn1 , xn2 ) I(X1n ; X2n |U ) ≤ nδ .
For every n, define the function σn : R≥0 → R≥0 as8
σn (δ) := sup
U

max
(n)
p∈PU (δ)

1
I(X1n , X2n ; Y n |U ),
n

(8)

where the supremum is over all finite sets U. As we see in Lemma 10, the conditioning on the random variable U
in (8) ensures that σn is convex.
7 Henceforth,

we write the average-error sum-capacity as Csum (C∗in , Cout ), since we are no longer concerned with the maximal-error

sum-capacity.
8 For

n = 1, this function also appears in the study of the MAC with negligible feedback [5].

7

For every δ ≥ 0, (σn (δ))∞
n=1 satisfies a superadditivity property which appears in Lemma 7, below. Intuitively,
this property says that the sum-rate of the best code of blocklength m + n is bounded from below by the sum-rate
of the concatenation of the best codes of blocklengths m and n.
Lemma 7. For all m, n ≥ 1 and all δ ≥ 0,
(m + n)σm+n (δ) ≥ mσm (δ) + nσn (δ).
Given Lemma 7, [17, Appendix 4A, Lemma 2] now implies that the sequence (σn (δ))∞
n=1 converges for every
δ ≥ 0, and
lim σn (δ) = sup σn (δ).

n→∞

n

Therefore, we can define the function σ : R≥0 → R≥0 as
σ(δ) := lim σn (δ).
n→∞

(9)

We next present our lower and upper bounds for Csum (C∗in , Cout ) in terms of σ. The lower bound follows directly
from [3, Corollary 8].
Lemma 8. For any discrete MAC and any Cout ∈ R2≥0 , we have
1
2
1
2
1
2
σ(Cout
+ Cout
) − min{Cout
, Cout
} ≤ Csum (C∗in , Cout ) ≤ σ(Cout
+ Cout
).

From the remark following Theorem 6, we only need to prove that Csum (C∗in , Cout ) is continuous on the
1
2
boundary of R2≥0 . Note that on the boundary of R2≥0 , however, min{Cout
, Cout
} = 0. Thus it suffices to show that

σ is continuous on R≥0 , which is stated in the next lemma.
Lemma 9. For any finite alphabet MAC, the function σ, defined by (9), is continuous on R≥0 .
To prove Lemma 9, we first consider the continuity of σ on R>0 and then deal with the point δ = 0. Note
that σ is the pointwise limit of the sequence of functions (σn )∞
n=1 . Using a time-sharing argument as in [18], it is
possible to show that each σn is concave (Lemma 10). Therefore, σ is concave as well, and since R>0 is open, σ
is continuous on R>0 .
Lemma 10 (Concavity of σn ). For all n ≥ 1, σn is concave on R≥0 .
To prove the continuity of σ(δ) at δ = 0, we find an upper bound for σ in terms of σ1 . For some finite set U
(n)

and δ > 0, consider a distribution p ∈ PU (δ). With respect to p,
I(X1n ; X2n |U ) ≤ nδ.

(10)

To find a bound for σ in terms of σ1 , we need a single-letter version of (10). In [16], Dueck presents such a bound.
We present Dueck’s result in the next lemma and include its proof for completeness.

8

(n)

Lemma 11 (Dueck’s Lemma [16]). Fix , δ > 0, positive integer n, and finite alphabet U. If p ∈ PU (δ), then
there exists a set T ⊆ [n] satisfying
|T | ≤

nδ
,


such that
∀t∈
/ T : I(X1t ; X2t |U, X1T , X2T ) ≤ ,
where for i ∈ {1, 2}, XiT := (Xit )t∈T .
Using Lemma 11, it is possible to find an upper bound for σ in terms of σ1 , which we present in the next
corollary. The proof of this corollary combines ideas from [16] with results derived here.
Corollary 12. For all , δ > 0, we have
 δ
σ δ ≤ log |X1 ||X2 | + σ1 ().

By Corollary 12, we have
σ(0) ≤ lim+ σ(δ) ≤ σ1 ().
δ→0

If we calculate the limit  → 0+ , we get
σ(0) ≤ lim+ σ(δ) ≤ lim+ σ1 ().
δ→0

→0

Since σ(0) = σ1 (0), it suffices to show that σ1 is continuous at δ = 0. Recall that σ1 is defined as
σ1 (δ) := sup max I(X1 , X2 ; Y |U ).
U

(1)

(11)

p∈PU (δ)

Since in (11), the supremum is over all finite sets U, it is difficult to find an upper bound for σ1 (δ) near δ = 0
directly. Instead we first show that it is possible to assume that U has at most two elements.
Lemma 13 (Cardinality of U). In the definition of σ1 (δ), it suffices to calculate the supremum over all sets U with
|U| ≤ 2.
From Lemma 13, using standard tools, such as Pinsker’s inequality [19, Lemma 17.3.3] and the L1 bound on
entropy [19, Lemma 11.6.1], the continuity of σ1 at δ = 0 follows.9
Lemma 14 (Continuity of σ1 ). The function σ1 is continuous on R≥0 .

VI. C ONTINUITY OF S UM -C APACITY: A RBITRARY Cin
In this section, we study the continuity of Csum (Cin , Cout ) over R2≥0 × R2≥0 with the aim of proving Theorem
6.
9 By

Lemma 10, σ1 is concave on R≥0 ; thus, it is continuous on R>0 .

9

Fix (Cin , Cout ). For arbitrary (C̃in , C̃out ), the triangle inequality implies
Csum (C̃in , C̃out ) − Csum (Cin , Cout )
≤ Csum (C̃in , C̃out ) − Csum (Cin , C̃out ) + Csum (Cin , C̃out ) − Csum (Cin , Cout )

(12)

We study this bound in the limit (C̃in , C̃out ) → (Cin , Cout ). We begin by considering the first term in (12).
Lemma 15 (Continuity of Sum-Capacity in Cin ). There exists a function
∆ : R2≥0 × R2≥0 → R≥0
that satisfies
lim

∆(Cin , C̃in ) = 0,

C̃in →Cin

and for any finite alphabet MAC and (Cin , C̃in , Cout ) ∈ R2≥0 × R2≥0 × R2≥0 , we have
Csum (Cin , Cout ) − Csum (C̃in , Cout ) ≤ ∆(Cin , C̃in ).
Applying Lemma 15 to (12), we get
Csum (C̃in , C̃out ) − Csum (Cin , Cout ) ≤ ∆(Cin , C̃in ) + Csum (Cin , C̃out ) − Csum (Cin , Cout ) .
Thus to calculate the limit (C̃in , C̃out ) → (Cin , Cout ), it suffices to consider
lim

Csum (Cin , C̃out ) − Csum (Cin , Cout ) .

C̃out →Cout

This is done in the next lemma.
Lemma 16 (Continuity of Sum-Capacity in Cout ). For any finite alphabet MAC and (Cin , Cout ) ∈ R2≥0 × R2≥0 ,
proving that
lim

Csum (Cin , C̃out ) = Csum (Cin , Cout ).

C̃out →Cout

is equivalent to showing that for all (Cin , Cout ) ∈ R2>0 × R2>0 , we have
lim
1 →0+
C̃out

lim
2 →0+
C̃out



1
2
2
Csum Cin , (C̃out
, Cout
) = Csum Cin , (0, Cout
)


1
2
1
Csum Cin , (Cout
, C̃out
) = Csum Cin , (Cout
, 0) .

VII. P ROOFS
In this section, we begin with the proof of Corollary 5. We then provide detailed proofs of the lemmas appearing
in Sections V and VI.

10

A. Proof of Corollary 5 (Necessary and Sufficient Condition for Discontinuity of Maximal-Error Sum-Capacity)
If (6) holds, then by Proposition 2, Csum,max (Cin , Cout ) is not continuous at Cout = 0. Here we prove the
reverse direction. To this end, we show that if
Csum,avg (0, 0) = Csum,max (0, 0),

(13)

then Csum,max (Cin , Cout ) is continuous at Cout = 0.
We begin by defining the function f : R≥0 → R≥0 as
f (Cout ) := Csum,max (C∗in , (Cout , Cout ))
Then by [2, Theorem 1] and (13), for all Cout ≥ 0, we have
f (Cout ) = Csum,avg (C∗in , (Cout , Cout )).
∗ :=
1
2
For each Cout ∈ R2≥0 , let Cout
max{Cout
, Cout
}. Then for any Cin ∈ R2≥0 ,
∗
f (0) ≤ Csum,max (Cin , Cout ) ≤ f (Cout
).

If we now let Cout → 0 and apply Theorem 3, the continuity of Csum,max (Cin , Cout ) at Cout = 0 follows.

B. Proof of Lemma 7
(n)

By the definition of σn (δ), for all  > 0, there exist finite alphabets U0 and U1 and distributions pn ∈ PU0 (δ)
(m)

and pm ∈ PU1 (δ) such that
In (X1n , X2n ; Y n |U0 ) ≥ nσn (δ) − n
Im (X1m , X2m ; Y m |U1 ) ≥ mσm (δ) − m.
Consider the distribution
pn+m (u0 , u1 , xn+m
, xn+m
) = pn (u0 , xn1 , xn2 )pm (u1 , xn+1:n+m
, xn+1:n+m
).
1
2
1
2
(n+m)
Let U := U0 × U1 . Then it is straightforward to show that that pn+m ∈ PU
(δ), and

In+m (X1n+m , X2n+m ; Y n+m |U0 , U1 ) ≥ nσn (δ) + mσm (δ) − (n + m),
which implies the desired result.

C. Proof of Lemma 8
We first prove the lower bound. For i ∈ {1, 2}, choose Cid such that
i
0 ≤ Cid ≤ Cout
.

Let p(u, x1 , x2 ) be any distribution satisfying
I(X1 ; X2 |U ) = C1d + C2d .

11

Then [3, Corollary 8] implies that
Csum (C∗in , Cout ) ≥ I(X1 , X2 ; Y |U ) − min{C1d , C2d }.
Applying the same corollary to the MAC
p(y n |xn1 , xn2 ) =

Y

p(yt |x1t , x2t ),

t∈[n]

proves our lower bound.
For the upper bound, consider a sequence of (2nR1 , 2nR2 , n)-codes for the MAC with a (C∗in , Cout )-CF. By the
data processing inequality,
1
2
I(X1n ; X2n ) ≤ n(Cout
+ Cout
).

In addition, from Fano’s inequality it follows that there exists a sequence (n )∞
n=1 such that
H(W1 , W2 |Y n ) ≤ nn ,
and n → 0 as n → ∞. We have
n(R1 + R2 ) = H(W1 , W2 )
= I(W1 , W2 ; Y n ) + H(W1 , W2 |Y n )
= I(X1n , X2n ; Y n ) + nn
1
2
≤ nσ(Cout
+ Cout
) + nn .

Dividing by n and taking the limit n → ∞ completes the proof.

D. Proof of Lemma 10 (Concavity of σn )
It suffices to prove the result for n = 1. We apply the technique from [18]. Note that
σ1 (δ) = sup max I(X1 , X2 ; Y |U ).
U

(1)

p∈PU (δ)
(1)

Fix a, b ≥ 0, λ ∈ (0, 1), and  > 0. Then there exist finite sets U0 and U1 and distributions p0 ∈ PU0 (a) and
(1)

p1 ∈ PU1 (b) satisfying
I0 (X1 , X2 ; Y |U0 ) ≥ σ1 (a) − 
I1 (X1 , X2 ; Y |U1 ) ≥ σ1 (b) − ,
respectively. Define the alphabet V as
V := {0} × U0 ∪ {1} × U1 .
We denote an element of V by v = (v1 , v2 ). Define the distribution pλ (v, x1 , x2 ) as
pλ (v, x1 , x2 ) = pλ (v1 )pv1 (v2 , x1 , x2 ),

12

where
pλ (v1 ) =



1 − λ

if v1 = 0


λ

if v1 = 1.

Then
Iλ (X1 ; X2 |V ) = Iλ (X1 , X2 |V1 , V2 )
= (1 − λ)I(X1 ; X2 |V1 = 0, V2 ) + λI(X1 ; X2 |V1 = 1, V2 )
= (1 − λ)I0 (X1 ; X2 |U0 ) + λI1 (X1 ; X2 |U1 )
≤ (1 − λ)a + λb,
(1)

which implies pλ ∈ PV ((1 − λ)a + λb). Similarly,
Iλ (X1 , X2 ; Y |V ) = Iλ (X1 , X2 ; Y |V1 , V2 )
= (1 − λ)I(X1 , X2 ; Y |V1 = 0, V2 ) + λI(X1 , X2 ; Y |V1 = 1, V2 )
= (1 − λ)I0 (X1 , X2 ; Y |U0 ) + λI1 (X1 , X2 ; Y |U1 )
≥ (1 − λ)σ1 (a) + λσ1 (b) − .
Therefore,

σ1 (1 − λ)a + λb ≥ (1 − λ)σ1 (a) + λσ1 (b) − .
The result now follows from the fact that the above equation holds for all  > 0.
E. Proof of Lemma 13
(1)

Let U be some finite set and let p∗ ∈ PU (δ) be a distribution that achieves
max I(X1 , X2 ; Y |U ).
(1)

p∈PU (δ)

Let Q ⊆ R|U | denote the set of all vectors (q(u))u∈U that satisfy
q(u) ≥ 0 for all u ∈ U
X
q(u) = 1
u∈U

X

q(u)I ∗ (X1 ; X2 |U = u) = I ∗ (X1 ; X2 |U ),

(14)

u∈U

where in (14), I ∗ (X1 ; X2 |U = u) and I ∗ (X1 ; X2 |U ) are calculated according to p∗ (x1 , x2 |u) and p∗ (u, x1 , x2 ),
respectively. Consider the mapping F : Q → R≥0 defined by
X
F [q] :=
q(u)I ∗ (X1 , X2 ; Y |U = u),

(15)

u∈U

where I ∗ (X1 , X2 ; Y |U = u) is calculated with respect to p∗ (x1 , x2 |u)p(y|x1 , x2 ). Note that since p∗ (u) ∈ Q, we
have
max F [q] =
q∈Q

max I(X1 , X2 ; Y |U ).
(1)

p∈PU (δ)

13

Thus it suffices to find q ∗ ∈ Q which has at most two non-zero components and at which F obtains its maximal
value.
Since F is linear in q, it is convex on Q, which is a bounded convex polyhedron in R|U | . Thus there exists an
extreme point of Q, say q ∗ ∈ Q, at which F obtains its maximum. Since q ∗ is an extreme point, if we apply [20,
p. 50, Theorem 2.3] to the definition of Q, we see that we must have q ∗ (u) = 0 for at least
|U| − 2
values of u. This completes the proof.

F. Proof of Lemma 14 (Continuity of σ1 )
By Lemma 13, without loss of generality, we can set U := {a, b}. For all δ ≥ 0, we have
max I(X1 , X2 ; Y |U ).

σ1 (δ) =

(1)

p∈PU (δ)
(1)

Fix δ > 0. Let p∗ (u, x1 , x2 ) be a distribution in PU (δ) achieving the maximum above, and define
p∗ind (x1 , x2 |u) := p∗ (x1 |u)p∗ (x2 |u).
Since
X


p∗ (u)D p∗ (x1 , x2 |u)kp∗ind (x1 , x2 |u) = I ∗ (X1 ; X2 |U ) ≤ δ,

u∈U

by [19, Lemma 11.6.1],
X

p∗ (u) p∗ (x1 , x2 |u) − p∗ind (x1 , x2 |u)

2
L1

≤ 2δ ln 2.

(16)

u∈U

In addition,
X

p∗ (u) p∗ (y|u) − p∗ind (y|u)

L1

u∈U

≤

X

p∗ (u)

≤

p(y|x1 , x2 ) p∗ (x1 , x2 |u) − p∗ind (x1 , x2 |u)

x1 ,x2

u∈U

X

X

p∗ (u) p∗ (x1 , x2 |u) − p∗ind (x1 , x2 |u)

L1

u∈U

≤

√
2δ ln 2,

(17)

where (17) follows from (16) and the Cauchy-Schwarz inequality. Define the subset U0 ⊆ U as
n
U0 = u ∈ U : p∗ (y|u) − p∗ind (y|u)

L1

o
≤ 1/2 .

Clearly, by (17),
X
u∈U
/ 0

√
p∗ (u) ≤ 2 2δ ln 2.

(18)

14

Thus
∗
H ∗ (Y |U ) − Hind
(Y |U )
X
∗
(Y |U = u)
≤
p∗ (u) H ∗ (Y |U = u) − Hind
u∈U

√
≤ 2 2δ ln 2 log |Y|

(a)

−

X

p∗ (u) p∗ (y|u) − p∗ind (y|u)

L1

log

u∈U0

p∗ (y|u) − p∗ind (y|u)
|Y|

L1

 1 √

√
√
2δ ln 2
≤ 2 2δ ln 2 log |Y| − 2δ ln 2 log
|Y|
3
√
|Y|
= 2δ ln 2 log √
,
2δ ln 2
(b)

(19)

where (a) follows from (18) and [19, Theorem 17.3.3], and (b) follows from (17) and the fact that the mapping
t 7→ −t log(t/|Y|) is concave on its domain and increasing for sufficiently small t.10 In addition, by (17),
∗
H ∗ (Y |U, X1 , X2 ) − Hind
(Y |U, X1 , X2 )
X
≤
p∗ (u, x1 , x2 ) − p∗ind (u, x1 , x2 ) H(Y |X1 = x1 , X2 = x2 )
u,x1 ,x2

≤ max H(Y |X1 = x1 , X2 = x2 ) ·
x1 ,x2

≤



X

p∗ (u) p∗ (x1 , x2 |u) − p∗ind (x1 , x2 |u)

L1

u∈U0

log |Y|

√

2δ ln 2.

(20)

Thus by (19) and (20),
σ1 (δ) = I ∗ (X1 , X2 ; Y |U ) = H ∗ (Y |U ) − H ∗ (Y |U, X1 , X2 )
∗
∗
(Y |U, X1 , X2 )
(Y |U ) + H ∗ (Y |U, X1 , X2 ) − Hind
≤ H ∗ (Y |U ) − Hind
∗
+ Iind
(X1 , X2 ; Y |U )

≤

√

2δ ln 2 log √


√
|Y|3
+ log |Y| 2δ ln 2 + σ1 (0).
2δ ln 2

Since σ1 (0) ≤ σ1 (δ) for all δ ≥ 0, the continuity of σ1 at δ = 0+ follows.

G. Proof of Lemma 11 (Dueck’s Lemma)
If for all t ∈ [n], we have
I(X1t ; X2t |U ) ≤ ,
then we define T := ∅. Otherwise, there exists t1 ∈ [n] such that
I(X1t1 ; X2t1 |U ) > .
10 Precisely,

the mapping t 7→ −t log(t/|Y|) is increasing on (0, |Y|/e).

(21)

15

Let S1 := [n] \ {t1 }. Then
I(X1n ; X2n |U ) = I(X1n ; X2t1 |U ) + I(X1n ; X2S1 |U, X2t1 )
= I(X1t1 ; X2t1 |U ) + I(X1S1 ; X2t1 |U, X1t1 )
+ I(X1t1 ; X2S1 |U, X2t1 ) + I(X1S1 ; X2S1 |U, X1t1 , X2t1 )
≥ I(X1t1 ; X2t1 |U ) + I(X1S1 ; X2S1 |U, X1t1 , X2t1 ).
Since I(X1n ; X2n |U ) ≤ nδ, using (21), we get
I(X1S1 ; X2S1 |U, X1t1 , X2t1 ) ≤ nδ − .
Now if for all t ∈ S1 ,
I(X1t ; X2t |U, X1t1 , X2t1 ) ≤ ,
then we define T := {t1 }. Otherwise, there exists t2 ∈ [n] such that
I(X1t2 ; X2t2 |U, X1t1 , X2t1 ) > .
Similar to the above argument, if we define S2 := [n] \ {t1 , t2 }, then
I(X1S2 ; X2S2 |U, X1t1 , X1t2 , X2t1 , X2t2 ) ≤ nδ − 2.
If we continue this process, we eventually get a set T := {t1 , . . . , tk } such that
c

c

I(X1T ; X2T |U, X1T , X2T ) ≤ nδ − |T |,

(22)

and for all t ∈ Sk := T c ,
I(X1t ; X2t |U, X1T , X2T ) ≤ .
In addition, from (22) it follows that
|T | ≤

nδ
.


(23)

H. Proof of Corollary 12
Fix a positive integer n. By Lemma 13, we can set U := {a, b}. From Lemma 11, it follows that there exists a
set T ⊆ [n] such that
0 ≤ |T | ≤

nδ
,


(24)

and
∀t∈
/ T : I(X1t ; X2t |U, X1T , X2T ) ≤ .
Thus
c

c

I(X1n , X2n ; Y n |U ) = I(X1T , X2T ; Y n |U ) + I(X1T , X2T ; Y n |U, X1T , X2T )
c

c

≤ |T | log |X1 ||X2 | + I(X1T , X2T ; Y n |U, X1T , X2T ).

(25)

16

We further bound the second term on the right hand side by
c

c

I(X1T , X2T ; Y n |U, X1T , X2T )
c

c

c

c

c

c

= I(X1T , X2T ; Y T |U, X1T , X2T ) + I(X1T , X2T ; Y T |U, X1T , X2T , Y T )
X
≤
I(X1t , X2t ; Yt |U, X1T , X2T )
t∈T
/

≤ n max I(X1 , X2 ; Y |V ) ≤ nσ1 (),
(1)

(26)

p∈PV ()

where
|T |
|T |
V := U × X1 × X2 .

Therefore, by (24), (25), and (26),
δ
1
I(X1n , X2n ; Y n |U ) ≤ log |X1 ||X2 | + σ1 (),
n

which completes the proof.

I. Proof of Lemma 15 (Continuity of Sum-Capacity in Cin )
Fix Cout ∈ R2≥0 . Define the functions f, g : R2≥0 → R as
f (Cin ) := Csum (Cin , Cout ) − Csum (Cin , 0) = Csum (Cin , Cout ) − Csum (0, 0)
1
2
g(Cin ) := Cin
+ Cin
− g(Cin ).

Note that since f is concave, g is convex. Thus for all λ ∈ [0, 1] and all (Cin , C̃in ),
g(λCin + (1 − λ)C̃in ) ≤ λg(Cin ) + (1 − λ)g(C̃in ).
Since g(0) = 0, setting C̃in = 0 gives
g(λCin ) ≤ λg(Cin )
Note that by [3, Proposition 6], g is nonnegative. Thus
g(λCin ) ≤ g(Cin ),
which when written in terms of f , is equivalent to
1
2
f (Cin ) − f (λCin ) ≤ (1 − λ)(Cin
+ Cin
).

Consider Cin , C̃in ∈ R2≥0 . Define the pairs Cin , C̄in ∈ R2≥0 as
¯
i
i
i
:= min{Cin
∀ i ∈ {1, 2} : Cin
, C̃in
}
¯
i
i
i
:= max{Cin
∀ i ∈ {1, 2} : C̄in
, C̃in
}

(27)

17

Next define λ∗ (Cin , C̃in ) ∈ [0, 1] as11
i
i
/C̄in
.
λ∗ := min Cin
i∈{1,2} ¯

Then
f (Cin ) − f (C̃in ) ≤ f (Cin ) − f (Cin ) + f (Cin ) − f (C̃in )
¯
¯

(28)

= f (Cin ) − f (Cin ) + f (C̃in ) − f (Cin )
¯
¯

(29)

≤ f (Cin ) − f (λ∗ Cin ) + f (C̃in ) − f (λ∗ C̃in )

(30)

1
2
1
2
≤ (1 − λ∗ )(Cin
+ Cin
) + (1 − λ∗ )(C̃in
+ C̃in
),

(31)

where (28) follows from the triangle inequality, (29) follows from the definition of Cin , (30) follows from the
¯
definition of λ∗ , and (31) follows from (27). Finally, if we let C̃in → Cin in (30), we see that f (C̃in ) → f (Cin ),
since
lim

λ∗ (Cin , C̃in ) = 1.

C̃in →Cin

J. Proof of Lemma 16 (Continuity of Sum-Capacity in Cout )
Recall that we only need to verify continuity on the boundary of R2≥0 × R2≥0 ; namely, the set of all points
1
2
1
2
(Cin , Cout ) where at least one of Cin
, Cin
, Cout
, or Cout
is zero.

We first show that
lim

Csum (Cin , C̃out ) = Csum (Cin , Cout ).

C̃out →Cout
1
2
holds if Cout = 0, or if either Cin
= 0 or Cin
= 0. For the case Cout = 0, note that

Csum (Cin , C̃out ) − Csum (Cin , 0) = Csum (Cin , C̃out ) − Csum (0, 0)
≤ Csum (C∗in , C̃out ) − Csum (0, 0),
which goes to zero as C̃out → 0 by Theorem 3.
2
Next suppose Cin
= 0. In this case, we have



1
1
2
Csum (Cin
, 0), C̃out = Csum (Cin
, 0), (0, C̃out
) .
Let f : R≥0 → R≥0 denote the function

2
1
2
f (Cout
) := Csum (Cin
, 0), (0, Cout
) .
2
Note that f is continuous on R>0 since it is concave. To prove the continuity of f at Cout
= 0, observe that
2
f (Cout
) equals the sum-capacity of a MAC with a (C12 , 0)-conference [1], where
1
2
C12 := min{Cin
, Cout
}.

i = 0, set λ∗ := min{1, C 2 /C̄ 2 }. If C̄ 1 = C̄ 2 = 0, set λ∗ = 1. These definitions ensure the
for some i ∈ {1, 2}, say i = 1, C̄in
in
in
¯ in in
∗
continuity of λ in (Cin , C̃in ).
11 If

18

From the capacity region given in [1], we have
2
1
2
f (Cout
) ≤ f (0) + min{Cin
, Cout
},
2
1
from which implies that f is continuous at Cout
= 0. The case where Cin
= 0 follows similarly.
2
1
Finally, consider the case where Cout
= 0, but Cout
> 0. In this case, we apply the next lemma for concave

functions that are nondecreasing as well.
Lemma 17. Let f : R≥0 → R≥0 be concave and nondecreasing. Then if |x − y| ≤ min{x, y},
f (x) − f (y) ≤ f (|x − y|) − f (0).
We have
1
2
1
Csum (Cin , (C̃out
, C̃out
)) − Csum (Cin , (Cout
, 0))
(a)

1
2
1
1
2
1
2
, C̃out
)) − Csum (Cin , (Cout
, 0))
, C̃out
)) − Csum (Cin , (Cout
, C̃out
)) + Csum (Cin , (Cout
≤ Csum (Cin , (C̃out

(b)

1
1
2
2
− Cout
|, C̃out
)) − Csum (Cin , (0, C̃out
))
≤ Csum (Cin , (|C̃out
1
2
1
, C̃out
)) − Csum (Cin , (Cout
, 0)) ,
+ Csum (Cin , (Cout

1
, 0),
where (a) follows from the triangle inequality, and (b) follows from Lemma 17. If we now let C̃out → (Cout

Corollary 4 implies
lim
1 ,0)
C̃out →(Cout

1
2
1
Csum (Cin , (C̃out
, C̃out
)) − Csum (Cin , (Cout
, 0))

≤ lim
2 →0
C̃out

1
2
1
Csum (Cin , (Cout
, C̃out
)) − Csum (Cin , (Cout
, 0)) ,

2
1
> 0.
= 0, but Cout
from which our result follows. An analogous proof applies in the case where Cout

VIII. S UMMARY
Consider a network consisting of a discrete MAC and a CF that has full knowledge of the messages. In this work,
we show that the average-error sum-capacity of such a network is always a continuous function of the CF output
link capacities; this is in contrast to our previous results on maximal-error sum-capacity [2]. Our proof method
relies on finding lower and upper bounds on the average-error sum-capacity and then using a modified version of
a technique developed by Dueck [16] to demonstrate continuity.
R EFERENCES
[1] F. M. J. Willems, “The discrete memoryless multiple access channel with partially cooperating encoders,” IEEE Trans. Inf. Theory, vol.
IT-29, no. 3, pp. 441–445, 1983.
[2] P. Noorzad, M. Effros, and M. Langberg, “Can negligible rate increase network reliability?” IEEE Trans. Inf. Theory, to be published.
[Online]. Available: http://ieeexplore.ieee.org/document/7944667/
[3] ——, “The unbounded benefit of encoder cooperation for the k-user MAC,” IEEE Trans. Inf. Theory, to be published. [Online].
Available: http://ieeexplore.ieee.org/document/8125167/
[4] M. Langberg and M. Effros, “On the capacity advantage of a single bit,” in IEEE Globecom Workshops, 2016.

19

[5] A. D. Sarwate and M. Gastpar, “Some observations on limited feedback for multiaccess channels,” in IEEE Int. Symp. Information Theory
(ISIT), 2009.
[6] A. P. Hekstra and F. M. J. Willems, “Dependence balance bounds for single-output two-way channels,” IEEE Trans. Inf. Theory, vol. 35,
no. 1, pp. 44–53, 1989.
[7] T. Ho, M. Effros, and S. Jalali, “On equivalence between network topologies,” in Allerton Conf. Communication, Control, and Computing,
2010.
[8] S. Jalali, M. Effros, and T. Ho, “On the impact of a single edge on the network coding capacity,” in Information Theory and Applications
Workshop, 2011.
[9] M. Langberg and M. Effros, “Network coding: Is zero error always possible?” in Allerton Conf. Communication, Control, and Computing,
2011.
[10] ——, “Source coding for dependent sources,” in IEEE Information Theory Workshop, 2012.
[11] W. Gu, M. Effros, and M. Bakshi, “A continuity theory for lossless source coding over networks,” in Proc. Allerton Conf. Communication,
Control, and Computing, 2008.
[12] T. Chan and A. Grant, “On capacity regions of non-multicast networks,” in Proc. IEEE Int. Symp. Information Theory, 2010.
[13] O. Kosut and J. Kliewer, “Strong converses are just edge removal properties,” Jun. 2017. [Online]. Available: http://arxiv.org/abs/1706.08172
[14] P. Noorzad, “Network effects in small networks: A study of cooperation,” Ph.D. dissertation, California Institute of Technology, June 2017.
[15] G. Dueck, “Maximal error capacity regions are smaller than average error capacity regions for multi-user channels,” Probl. Contr. Inform.
Theory, vol. 7, no. 1, pp. 11–19, 1978.
[16] ——, “The strong converse of the coding theorem for the multiple-access channel,” Journal of Combinatorics, Information, and System
Sciences, vol. 6, pp. 187–196, 1981.
[17] R. G. Gallager, Information Theory and Reliable Communication, 1st ed.

Wiley, 1968.

[18] T. M. Cover, A. El Gamal, and M. Salehi, “Multiple access channels with arbitrary correlated sources,” IEEE Trans. Inf. Theory, vol.
IT-26, no. 6, pp. 648–657, 1980.
[19] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed.
[20] D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization.

Wiley, 2006.

Athena Scientific, 1997.

