# Zero-Error Communication over Adversarial MACs

Yihan Zhang12
1Faculty of Computer Science, Technion Israel Institute of Technology
2Institute of Theoretical Computer Science and Communications, The Chinese
University of Hong Kong
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We consider zero-error communication over a two-transmitter deterministic
adversarial multiple access channel (MAC) governed by an adversary who has
access to the transmissions of both senders (hence called _omniscient_) and
aims to maliciously corrupt the communication. None of the encoders, jammer
and decoder is allowed to randomize using private or public randomness. This
enforces a combinatorial nature of the problem. Our model covers a large
family of channels studied in the literature, including all deterministic
discrete memoryless noisy or noiseless MACs. In this work, given an arbitrary
two-transmitter deterministic omniscient adversarial MAC, we characterize when
the capacity region

  1. 1.

has nonempty interior (in particular, is two-dimensional);

  2. 2.

consists of two line segments (in particular, has empty interior);

  3. 3.

consists of one line segment (in particular, is one-dimensional);

  4. 4.

or only contains $(0,0)$ (in particular, is zero-dimensional).

This extends a recent result by Wang, Budkuley, Bogdanov and Jaggi (2019) from
the point-to-point setting to the multiple access setting. Indeed, our
converse arguments build upon their generalized Plotkin bound and involve
delicate case analysis. One of the technical challenges is to take care of
both “joint confusability” and “marginal confusability”. In particular, the
treatment of marginal confusability does _not_ follow from the point-to-point
results by Wang et al. Our achievability results follow from random coding
with expurgation.

##  I Introduction

The multiple access channel (MAC) model was first (implicitly) considered by
Shannon [Sha61]. This model is arguably one of the simplest communication
models beyond the point-to-point setting. The problem concerns information
transmission over a three-node network. Two111In this paper, we only consider
MACs with two transmitters. Generalizations to more transmitters are left as
an open question (see Item 3 in Section XVI). independent senders
simultaneously send signals to the channel; a single receiver aims to recover
both senders’ transmitted messages given the channel-distorted signal. The
goal for the parties in such a communication scenario is to reliably deliver
as much information from the senders to the receiver. The fundamental limits
(i.e., _capacity region_ , see Definition 7) of discrete memoryless MACs under
the average error criterion was derived independently by Ahlswede [Ahl73,
Ahl74] and Liao [Lia72]222The capacity region given by Ahlswede [Ahl73, Ahl74]
and Liao [Lia72] is written in terms of the convex hull of the union of
multiple regions. An alternative form involving an auxiliary time-sharing
variable was given by Slepian and Wolf [SW73]. A cardinality bound on the
alphabet of the auxiliary variable was given in [CK11].. The Gaussian
counterpart333This paper only concerns MACs with finite-sized alphabets and
will not deal with the Euclidean case. was solved by Cover [Cov75] and Wyner
[Wyn74]. MACs are so far the essentially only multiuser channel whose
fundamental limits are well-understood in full generality.

In the classical Shannon’s setup of the MAC problem, it is assumed that the
channel is given by a _fixed_ (i.e., time-invariant) law444We use lowercase
boldface letters to denote (scalar) random variables.
$W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2}}$ that maps a given pair of
input symbols555Throughout this paper, we use superscripts to denote the
indices of the transmitter. E.g., $x^{1}$ (resp. $x^{2}$) denotes a symbol
transmitted by the first (resp. second) transmitter.
$(x^{1},x^{2})\in{\mathcal{X}}_{1}\times{\mathcal{X}}_{2}$ to an output symbol
$y\in{\mathcal{Y}}$ with probability
$W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2}}\left(y|x^{1},x^{2}\right)$.
Such a channel well models white noise between the senders and the receiver,
while it fails to model _adversarial_ noise that is potentially injected by a
malicious adversary. In this paper, we take a coding-theoretic perspective on
multiple access. A general _omniscient adversarial MAC_ model is introduced
and studied. We assume that the channel is governed by an adversary who has
full access to the transmitted signals from both senders (hence called
_omniscient_). The adversary aims to prevent communication from happening by
transmitting a carefully designed noise sequence to the channel. We therefore
at times also call the adversary the _jammer_. None of the encoders, the
jammer and the decoder is allowed to randomize. To enforce a combinatorial
nature of the problem, it is further assumed that the channel obeys a zero-one
law, i.e., the distribution
$W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}$ (where
${\mathbf{s}}$ denotes the symbol sent by the jammer) only takes values in
$\\{0,1\\}$ and can be realized by a deterministic function
$y=W(x^{1},x^{2},s)$ (with a slight abuse of notation). The main contribution
of this paper is a _zero-th_ order (see the next paragraph) characterization
of the capacity region of an arbitrary omniscient adversarial MAC with
_maximum_ error probability. In fact, since nothing in the system is
stochastic, it is not hard to see that maximum error criterion is equivalent
to zero error criterion. Our results can be appreciated through different
lenses, e.g., arbitrarily varying channels, zero-error information theory,
coding theory, etc. Elaboration on various connections is deferred to Section
II.

Classical Shannon theory and combinatorial coding theory provide systematic
ways of studying the _first-order_ asymptotics, i.e., capacity, of (stochastic
and adversarial respectively) communication channels. By first-order we mean
the number of bits that can be reliably transmitted through the channel. The
first-order asymptotics of discrete memoryless channels (DMCs) are well-
established in the seminal paper by Shannon [Sha48] which laid the foundation
of information theory. The first-order asymptotics of most multiuser channels
remain open, except for MAC as mentioned before and a handful of other special
cases. On the other hand, in the theory of error-correcting codes which deals
with worst-case errors, essentially no capacity is characterized for any
nontrivial channel. Indeed, even the capacity of adversarial bitflip channels
– one of the simplest nontrivial channels remains a holy grail problem in
coding theory. This problem is well known to be equivalent to the sphere
packing problem in binary Hamming space. Our work can be viewed as a first
step towards pushing the existing wisdom of classical coding theory to the
general multiuser setting. For one thing, we consider very general channel
models, not just the bitflip channel which is the most studied one in coding
theory. For another thing, we go beyond the point-to-point setting and
consider MACs. Due to the lack of techniques for characterizing the capacity,
this work only aims to characterize the “shape” of the capacity region of any
given adversarial MAC. More specifically, we determine the dimension of the
capacity region – when it has nonempty interior; when it only consists of (one
or two) line segment(s); and when it only contains ${(0,0)}$. We call such
positivity conditions a characterization of the _zero-th_ order asymptotics of
the channel. See Section XI for the formal statements of our results. Finally,
we remark that there has been a stream of work on high-order
(second-/third-/fourth-order) asymptotics of channels [PPV10, TT13, TT15,
SMiF14, YKE20, Kos20].

######  Remark 1.

The capacity region of a (non-adversarial) MAC under average error criterion
can be achieved using deterministic encoding and the region is invariant even
if stochastic encoding is allowed. However, unlike the point-to-point case,
under _maximum_ error criterion and _deterministic_ encoding, the capacity
region of a MAC is strictly smaller than that under average error criterion
[Due78]. To the best of our knowledge, the exact capacity region in this case
is still open. Furthermore, under maximum error criterion, stochastic encoding
can achieve the capacity region with average probability of error. This shows
that randomization at the encoders can boost the capacity under maximum error
criterion – a phenomenon absent in the point-to-point setting.

##  II Related work

Our model and results are connected to various facets of information theory
and adjacent fields. We list non-exhaustively several connections below and
compare, when proper, our results with existing ones.

###  II-A Arbitrarily varying channels

Our model of general omniscient adversarial MAC is intimately related to a
classical model studied in the literature known as the _arbitrarily varying
channel (AVC)_. An AVC is a channel with a state ${\mathbf{s}}$ that does not
follow any fixed distribution, i.e., is arbitrarily varying. A noticeable
difference between the classical AVC model and our model is that the bulk of
the literature on AVC deals with channels with an _oblivious_ adversary who
does not know anything about the transmitted sequence. Under average error
criterion, this problem is significantly easier (though not trivial) than the
omniscient counterpart. Indeed, the fundamental limits of point-to-point AVCs
[CN88b, CN91] and arbitrarily varying MACs (AVMACs) [AC99, PS19] (and several
other channels which we do not spell out here) are well-understood.

In fact, an oblivious AVMAC with maximum probability of error is equivalent to
our model of omniscient adversarial MAC. However, the maximum error criterion
is much less studied in the AVC literature. Obtaining a tight first-order
characterization of the capacity remains an formidable challenge even for very
simple channels. The main focus of this work is a zero-th order
characterization of the capacity region of general omniscient adversarial
MACs. Though we do present nontrivial inner and outer bounds, there is no
reason to expect any of them to be optimal. Item 1 in Section XVI contains
more discussions and open problems regarding error criterion. See also Section
XI-B for an in-depth comparison between our work and [PS19] on AVMACs.

###  II-B Zero-error information theory

Since randomization in the encoding/jamming/decoding strategies are ruled out
from our model and only deterministic channels are considered, there is no
probability anywhere in the system and maximum error criterion is equivalent
to zero error criterion. For this reason, it is worth mentioning the
connections between our work and zero-error information theory – a
combinatorial facet of information theory. The basic deviation of zero-error
information theory from ordinary Shannon theory is to insist on _zero error_
criterion which changes the nature of the problem in a fundamental way.
Despite of years of research, there is essentially no capacity result for any
general channel model except for sporadic special channels [Lov79]. Usually
channels studied in zero-error information theory do not consist of an
adversarial noise (a.k.a. an arbitrarily varying state in AVC jargon). It
turns out that if the adversarial noise in our model is _unconstrained_ (i.e.,
the state vector666We use underlines to denote vectors of length $n$ – the
number of channel uses. See Section V for notational conventions of this
paper. ${\underline{s}}$ can take any value in ${\mathcal{S}}^{n}$), then the
channel is equivalent to a non-adversarial channel under zero error criterion.
On the other hand, the presence of state constraints brings significant effect
on the behaviour of the channel. Such a phenomenon already shows up in the
point-to-point setting [CN88b]. Classical zero-error information theory
approaches the problem of zero-error communication via the notion of _Shannon
capacity_ of graphs [Sha56] – getting rid of channel
probabilities.777Unfortunately, Shannon capacity is not computable since it is
defined as a limit as $n$, the blocklength, goes to infinity. See Section II-D
and Item 5 in Section XVI for remarks on $n$-letter capacity expressions.
Recently, the positivity of zero-error capacity of MACs (and several other
multiuser channels) was characterized by Devroye [Dev16]. However, she only
dealt with non-adversarial channels, or equivalently, adversarial channels
without state constraints. Several other general multiuser channels with zero
error such as two-way channels [GS19] and relay channels [CSD14, CD15, CD17,
APBD18] were also studied in the literature. Many other works on zero-error
multiuser channels concentrate around specific channels such as binary adder
MAC [AKKN17], $\mathsf{AND}\text{-}\mathsf{OR}$ interference channel [NY20],
etc. See Section II-F for more related work on special MACs.

###  II-C Kolmogorov complexity

Besides Shannon’s notion of graph capacity, Kolmogorov [Kol56, Tik93]
introduced the $\varepsilon$-entropy and $\varepsilon$-capacity (which are the
normalized covering and packing number (using balls of radius $\varepsilon$)
of a space) as another non-stochastic approach to zero-error source and
channel coding, respectively. However, there was no coding theorems companying
these notions. The results in [WBBJ19] which we build upon can be cast as
packing _general_ shapes (not necessarily balls) without overlap in a general
space. For MACs, the geometric interpretation of packing and covering does not
seem to be as obvious/clean as in the point-to-point case.

###  II-D Non-stochastic information theory

Recently, Nair [Nai11, Nai13] proposed yet another alternative framework
towards understanding zero-error communication known as _non-stochastic
information theory_. He introduced non-stochastic analogs of information
measures and proved coding theorems for worst-case error models. Extensions to
MACs (see [ZNE19] for the two-transmitter case and [ZN20] for the multi-
transmitter case), channels with feedback [Nai12, SFN18, SFN20b], channels
with memory [SFN20a, SFN19] and function evaluation [FN20] are presented in
followup works by Nair and his coauthors. In most cases, Nair’s framework only
gives $n$-letter expressions for capacity, similar to the graph-theoretic
approach mentioned in Section II-B. More recently, Lim–Franceschetti [LF17]
and Rangi–Franceschetti [RF19] refined Nair’s framework by introducing new
non-stochastic information measures to incorporate decoding errors while
retaining the worst-case nature of the error model. The latter work [RF19]
also studied the possibility of obtaining single-letter expressions for the
capacity of a certain family of channels.

As a comparison, our approach does not even yield $n$-letter capacity
expressions. However, we can handle general adversarial channels with
potentially constrained adversarial noise. In [RF19], following Nair’s
framework, such channels are treated as _nonstationary_ channels with _memory_
for which no $n$-letter capacity expression was obtained. More words on
$n$-letter expressions can be found in Item 5 of Section XVI.

###  II-E Coding theory and generalized Plotkin bound

Since our problem inherently exhibits a combinatorial nature, one can view our
contributions as Shannon-theoretic results for a coding-theoretic model. We
borrow insights and techniques from both information theory and coding theory
and try to build a bridge between them in the particular MAC setting. At a
technical level, the principal tool that we use is inspired by a recent
Plotkin-type bound for general point-to-point omniscient adversarial channels
[WBBJ19]. Our contribution is to generalize it to the MAC setting and use it,
along with delicate case analysis, to characterize the “dimension” of the
capacity region. The results in both [WBBJ19] and this paper are in turn
generalizations of the Plotkin bound in classical coding theory. This bound
(together with a standard probabilistic construction) pins down the exact
threshold of the noise level of a bitflip channel888A bitflip channel takes a
binary sequence as input and arbitrarily flips a fixed fraction of bits. such
that positive rates are achievable (see Definition 7 for the formal definition
of achievable rates).

###  II-F Specific channels

Our model covers a large family of channels studied in the literature,
including the $\operatorname{\mathsf{OR}}$ MAC, the collision MAC, the adder
MAC [Gu18, AKKN17], the disjunctive MAC [DPSV19], the multiple access
hyperchannel [Shc16], etc. Indeed, our model incorporates all deterministic
channel models. Interested readers are encouraged to refer to the lecture
notes [GGLR] and [PW14, Chapter 29, 30].

##  III Overview of our results

This work initiates a systematic study of memoryless MACs in the presence of
an omniscient adversary (who may _not_ behave memorylessly) under the maximum
probability of error criterion. In particular, the main attention of this
paper is focused on the capacity threshold. In what follows, we summarize the
contributions of this paper.

  1. 1.

We introduce in Section VII the model of _omniscient adversarial MACs_ which
covers a large family of channels of interests. In particular, all component-
wise deterministic memoryless channels with finite alphabets fall into our
framework. In this work we focus on the maximum probability of error
criterion. For technical reasons, we make additional assumptions that are
listed in Section VII-B.

  2. 2.

We introduce in Section IX the notion of _confusability_ , both the
operational version (12) and the distributional version (Definition 11) which
turn out to be equivalent (14, Remark 5). Specifically, we define the _joint
confusability set_ and the (first and second) _marginal confusability sets_
(for both transmitters separately) to capture the disability to reliably
transmit both (for the joint case) or exactly one (for the marginal cases) of
the sequences. One can think of the confusability sets as the sets of “bad”
distributions that (the types999The type of a (collection of) vector(s) is the
empirical distribution/histogram. See Definition 3 for a formal definition.
of) any good code should avoid. The significance of the notion of
confusability is that it precisely captures all information one needs for
understanding the capacity region of any adversarial MAC. In fact, adversarial
MACs with the same confusability sets share a common capacity region (16),
though they may appear different at the first glance. Various properties of
the confusability sets are presented in Proposition 15.

  3. 3.

Towards understanding capacity thresholds, we find a class of distributions
that we call _good_ (Definition 15). Again, they are separately tailored for
the joint case and two marginal cases. While being of independent interest on
their own, the sets of good distributions are particularly useful in our
context of determining the capacity threshold. One should think of these
classes of distributions as the _only_ types of distributions that one needs
to consider for the purpose of achieving positive rates (though in this way
one may not be able to achieve the capacity which is anyway unknown given the
current techniques). We also define a cone of tensors referred to as _co-good_
tensors (Definition 16) and show that the cones of good and co-good tensors
are dual to each other (Theorem 18), which will be critical to the proofs in
the proceeding sections. Various properties of good distributions and co-good
tensors are presented. We expect these distributions/tensors and the
associated duality to be useful elsewhere.

  4. 4.

We completely characterize, for any given omniscient adversarial MAC, the
“shape” of the capacity region, that is, when the capacity region

    1. (a)

has nonempty interior (in particular, is two-dimensional);

    2. (b)

consists of two line segments (in particular, has empty interior);

    3. (c)

consists of one line segment (in particular, is one-dimensional);

    4. (d)

or only contains $(0,0)$ (in particular, is zero-dimensional).

The proof comprises of the direct part and the converse part. The technically
most challenging case is to handle the (non-)achievability of rate pairs both
components of which are strictly positive. For the marginal cases, we
emphasize that they do _not_ follow from the point-to-point results in
[WBBJ19] in a black-box manner.

We then briefly discuss separately our achievability and converse results and
the techniques for proving them. For a more detailed discussion on the proof
techniques, see Section XII.

  1. 1.

For the achievability part, one could use good non-confusable distributions
(whenever they exist) to sample good codes of positive rates (Lemma 23). This
follows from the standard random coding argument which in turn is proved using
Chernoff-union bounds. We also strengthen the above positivity results by
giving _inner bounds_ on the capacity region (Lemma 24). This follows by
carefully expurgating the codes and analyzing the large deviation exponents of
the error events using the Sanov’s theorem (Lemma 3). The most challenging
case is where both transmitters are able to achieve positive rates.

  2. 2.

On the other hand, for the converse part, if one cannot construct positive
rate good codes using good distributions, then she/he cannot construct them
using any other types of distributions (Theorem 20). This part is much less
obvious and forms the bulk of the technically most challenging portion of this
work. As alluded to above, the crux of the proof is to leverage the duality
between the cone of good distributions and the cone of co-good tensors defined
before and to apply a double counting trick that is reminiscent of the one
used in the classical Plotkin bound in coding theory. Technically, to make the
trick actually work, we have to preprocess the code by applying a standard
constant composition reduction and an equicoupled subcode extraction (using
Ramsey’s theorems Theorems 26 and 35). The hardest case is to show that two
transmitters cannot simultaneously achieve positive rates as long as there
does not exist a distribution that is _simultaneously_ jointly good and (first
and second) marginally good.

##  IV Organization of this paper

The rest of the paper is organized as follows. Notational conventions of this
paper are listed in Section V, followed by preliminaries in Section VI. We
formally introduce the omniscient adversarial MAC model in Section VII. Before
proceeding, we first study the special case of binary noisy
$\operatorname{\mathsf{XOR}}$ MACs in Section VIII with proofs deferred to
Appendix B. Then in Sections IX and X respectively, we introduce two important
notions of (sets of) distributions, viz.: the confusability sets and the sets
of good distributions, and prove properties of them. Building on the machinery
we have developed in the previous sections, the main result (Theorem 19) of
this paper, i.e., a characterization of the “shape” of capacity region, is
formally stated in Section XI. Before presenting the detailed proofs, we
outline a roadmap with underlying ideas of the proofs in Section XII. Section
XIII contains a full proof of the achievability part of our main theorem.
Sections XIV and XV prove the “joint” case and the “marginal” cases of the
converse part, respectively. We conclude the paper with a list of remarks and
open questions in Section XVI. A table of frequently used notation can be
found in Appendix A.

##  V Notation

Sets are denoted by capital letters in calligraphic typeface, e.g.,
${\mathcal{X}},{\mathcal{S}},{\mathcal{Y}}$, etc. All alphabets in this paper
are finite sized. For a positive integer $M$, we use $[M]$ to denote
$\left\\{1,\cdots,M\right\\}$. Let ${\mathcal{X}}$ be a finite set. For an
integer $0\leq k\leq{\left|{\mathcal{X}}\right|}$, we use
$\binom{{\mathcal{X}}}{k}$ to denote
$\left\\{{\mathcal{X}}^{\prime}\subseteq{\mathcal{X}}\colon\left|{\mathcal{X}}^{\prime}\right|=k\right\\}$.

Random variables are denoted by lowercase letters in boldface, e.g.,
${\mathbf{x}},{\mathbf{s}},{\mathbf{y}}$, etc. Their realizations are denoted
by corresponding lowercase letters in plain typeface, e.g., $x,s,y$, etc.
Vectors (random or fixed) of length $n$, where $n$ is the blocklength of the
code without further specification, are denoted by lowercase letters with
underlines, e.g.,
${\underline{\mathbf{x}}},{\underline{\mathbf{s}}},{\underline{\mathbf{y}}},{\underline{x}},{\underline{s}},{\underline{y}}$,
etc. The $i$-th entry of a vector ${\underline{x}}\in{\mathcal{X}}^{n}$ (resp.
${\underline{\mathbf{x}}}\in{\mathcal{X}}^{n}$) is denoted by
${\underline{x}}(i)$ (resp. ${\underline{\mathbf{x}}}(i)$).

For vectors and random variables/vectors, we use superscripts to denote the
indices of the transmitters, e.g.,
${\underline{x}}^{1},{\mathbf{x}}^{1},{\underline{\mathbf{x}}}^{1}$ (resp.
${\underline{x}}^{2},{\mathbf{x}}^{2},{\underline{\mathbf{x}}}^{2}$)
correspond to the first (resp. second) transmitter.

We use the standard Bachmann–Landau (Big-Oh) notation. For two real-valued
functions $f(n),g(n)$ of positive integers, we say that $f(n)$ _asymptotically
equals_ $g(n)$, denoted by $f(n)\asymp g(n)$, if
$\lim_{n\to\infty}{f(n)}/{g(n)}=1$. We write $f(n)\doteq g(n)$ (read $f(n)$
_dot equals_ $g(n)$) if $\lim_{n\to\infty}\left(\log f(n)\right)/\left(\log
g(n)\right)=1$. Note that $f(n)\asymp g(n)$ implies $f(n)\doteq g(n)$, but the
converse is not true. For any ${\mathcal{A}}\subseteq{\mathcal{X}}$, the
indicator function of ${\mathcal{A}}$ is defined as, for any
$x\in{\mathcal{X}}$,

$\mathds{1}_{{\mathcal{A}}}(x)\coloneqq\begin{cases}1,&x\in{\mathcal{A}}\\\
0,&x\notin{\mathcal{A}}\end{cases}.$

At times, we will slightly abuse notation by saying that
$\mathds{1}{\left\\{{\mathsf{A}}\right\\}}$ is $1$ when event ${\mathsf{A}}$
happens and $0$ otherwise. Note that
$\mathds{1}_{{\mathcal{A}}}(\cdot)=\mathds{1}{\left\\{\cdot\in{\mathcal{A}}\right\\}}$.
In this paper, all logarithms are to the base 2.

We use $\Delta({\mathcal{X}})$ to denote the probability simplex on
${\mathcal{X}}$. Related notations such as
$\Delta({\mathcal{X}}\times{\mathcal{Y}})$ and
$\Delta({\mathcal{Y}}|{\mathcal{X}})$ are similarly defined. For a
distribution
$P_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}\times{\mathcal{Y}}|{\mathcal{U}})$,
we use
$\left[P_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}}\right]_{{\mathbf{x}}|{\mathbf{u}}}\in\Delta({\mathcal{X}}|{\mathcal{U}})$
to denote the marginal distribution onto ${\mathbf{x}}$ given ${\mathbf{u}}$,
i.e., for every $x\in{\mathcal{X}},u\in{\mathcal{U}}$,
$\left[P_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}}\right]_{{\mathbf{x}}|{\mathbf{u}}}(x|u)=\sum_{y\in{\mathcal{Y}}}P_{{\mathbf{x}},{\mathbf{y}}|{\mathbf{u}}}(x,y|u)$.
We use $\Delta^{(n)}({\mathcal{X}})$ to denote the set of types (i.e.,
empirical distributions/histograms, see Definition 3 for formal definitions)
of length-$n$ vectors over alphabet ${\mathcal{X}}$. That is,
$\Delta^{(n)}({\mathcal{X}})$ consists of all distributions
$P_{\mathbf{x}}\in\Delta({\mathcal{X}})$ that are induced by
${\mathcal{X}}^{n}$-valued vectors. Other notations such as
$\Delta^{(n)}({\mathcal{X}}\times{\mathcal{Y}})$ and
$\Delta^{(n)}({\mathcal{Y}}|{\mathcal{X}})$ are similarly defined. The
notation ${\mathbf{x}}\sim P_{\mathbf{x}}$ (resp.
${\underline{\mathbf{x}}}\sim P_{{\underline{\mathbf{x}}}}$) means that the
p.m.f. of a random variable (resp. vector) ${\mathbf{x}}$ (resp.
${\underline{\mathbf{x}}}$) is $P_{\mathbf{x}}$ (resp.
$P_{\underline{\mathbf{x}}}$). If ${\mathbf{x}}$ is uniformly distributed in
${\mathcal{X}}$, then we write ${\mathbf{x}}\sim{\mathcal{X}}$. Throughout
this paper, we use $d_{{\infty}}\left(\cdot,\cdot\right)$ and
$d_{{1}}\left(\cdot,\cdot\right)$ to respectively denote the $\ell^{\infty}$
and $\ell^{1}$ distances between two distributions which are defined as
follows

$\displaystyle
d_{{\infty}}\left(P,Q\right)\coloneqq\sum_{x\in{\mathcal{X}}}\left|P(x)-Q(x)\right|,\quad
d_{{1}}\left(P,Q\right)\coloneqq\max_{x\in{\mathcal{X}}}\left|P(x)-Q(x)\right|,$

for any $P,Q\in\Delta({\mathcal{X}})$. For a distribution
$P\in\Delta({\mathcal{X}})$ and a subset
${\mathcal{A}}\subseteq\Delta({\mathcal{X}})$, the distance (w.r.t. some
metric $\operatorname{dist}(\cdot,\cdot)$) between $P$ and ${\mathcal{A}}$ is
defined as
$\operatorname{dist}(P,{\mathcal{A}})\coloneqq\inf_{Q\in{\mathcal{A}}}\operatorname{dist}(P,Q)$.
For ${\mathcal{B}}\subseteq\Delta({\mathcal{X}})$, the distance between
${\mathcal{A}}$ and ${\mathcal{B}}$ is defined as
$\operatorname{dist}({\mathcal{A}},{\mathcal{B}})\coloneqq\inf_{(P,Q)\in{\mathcal{A}}\times{\mathcal{B}}}\operatorname{dist}(P,Q)$.
The inner product between $P$ and $Q$ is defined as $\left\langle
P,Q\right\rangle\coloneqq\sum_{x\in{\mathcal{X}}}P(x)Q(x)$. The
$\ell^{p}$-norm of a vector is denoted by $\left\|\cdot\right\|_{p}$. Note
that
$d_{{\infty}}\left(\cdot,\cdot\right)=\left\|\cdot-\cdot\right\|_{\infty}$ and
$d_{{1}}\left(\cdot,\cdot\right)=\left\|\cdot-\cdot\right\|_{1}$.

##  VI Preliminaries

Let $P_{\mathbf{x}}\in\Delta({\mathcal{X}})$. We always assume
$\operatorname{supp}(P_{\mathbf{x}})={\mathcal{X}}$. Otherwise, we can
properly reduce ${\mathcal{X}}$ to ${\mathcal{X}}^{\prime}$ and again assume
$P_{\mathbf{x}}\in\Delta({\mathcal{X}}^{\prime}),\operatorname{supp}(P_{\mathbf{x}})={\mathcal{X}}^{\prime}$.
Define the polynomial $\nu(P_{\mathbf{x}},n)$ as

$\displaystyle\nu(P_{\mathbf{x}},n)\coloneqq$ $\displaystyle\sqrt{(2\pi
n)^{\left|{\mathcal{X}}\right|}\prod_{x\in{\mathcal{X}}}P_{\mathbf{x}}(x)}.$
(1)

Note that $\nu(P_{\mathbf{x}},n)\neq 0$.

######  Lemma 1.

If ${\underline{\mathbf{x}}}\sim P_{\mathbf{x}}^{\otimes n}$, then for any
${\underline{x}}$ of type $P_{\mathbf{x}}$, we have
$\Pr\left[{\underline{\mathbf{x}}}={\underline{x}}\right]=2^{-H(P_{\mathbf{x}})}$.
Moreover, $\Pr\left[\tau_{\underline{\mathbf{x}}}=P_{\mathbf{x}}\right]\asymp
1/\nu(P_{\mathbf{x}},n)$.

######  Lemma 2 (Chernoff bound).

Let ${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{N}$ be independent
$\left\\{0,1\right\\}$-valued random variables. Let
${\mathbf{x}}\coloneqq\sum_{i=1}^{N}{\mathbf{x}}_{i}$. Then for any
$\sigma\in[0,1]$,

$\displaystyle\Pr\left[{\mathbf{x}}\geq(1+\delta)\mathbb{E}\left[{\mathbf{x}}\right]\right]\leq$
$\displaystyle\exp\left(-\frac{\delta^{2}}{3}\mathbb{E}\left[{\mathbf{x}}\right]\right),$
$\displaystyle\Pr\left[{\mathbf{x}}\leq(1-\delta)\mathbb{E}\left[{\mathbf{x}}\right]\right]\leq$
$\displaystyle\exp\left(-\frac{\delta^{2}}{2}\mathbb{E}\left[{\mathbf{x}}\right]\right),$
$\displaystyle\Pr\left[{\mathbf{x}}\notin(1\pm\delta)\mathbb{E}\left[{\mathbf{x}}\right]\right]\leq$
$\displaystyle
2\exp\left(-\frac{\delta^{2}}{3}\mathbb{E}\left[{\mathbf{x}}\right]\right).$

######  Lemma 3 (Sanov’s theorem).

Let ${\mathcal{Q}}\subseteq\Delta({\mathcal{X}})$ be a subset of distributions
which equals the closure of its interior. Let ${\underline{\mathbf{x}}}\sim
P_{\mathbf{x}}^{\otimes n}$ for some $P_{\mathbf{x}}\in\Delta({\mathcal{X}})$.
Then

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\log\Pr\left[\tau_{\underline{\mathbf{x}}}\in{\mathcal{A}}\right]=$
$\displaystyle-\inf_{Q_{\mathbf{x}}\in{\mathcal{Q}}}D\left(Q_{\mathbf{x}}\middle\|P_{\mathbf{x}}\right),$

where the Kullback–Leibler (KL) divergence $D\left(\cdot\middle\|\cdot\right)$
between two distributions is defined in Definition 2.

######  Fact 4.

Let
${\underline{x}}=({\underline{x}}^{(1)},{\underline{x}}^{(2)})\in{\mathcal{X}}^{n}$
where ${\underline{x}}^{(1)}\in{\mathcal{X}}^{\alpha n}$ and
${\underline{x}}^{(2)}\in{\mathcal{X}}^{(1-\alpha)n}$ for some
$\alpha\in[0,1]$. Then we have
$\tau_{{\underline{x}}}=\alpha\tau_{{\underline{x}}^{(1)}}+(1-\alpha)\tau_{{\underline{x}}^{(2)}}$.

######  Definition 1 (Net).

Let $({\mathcal{X}},\operatorname{dist})$ be a metric space and $\eta>0$ be a
constant. A subset ${\mathcal{N}}\subseteq{\mathcal{X}}$ is an _$\eta$ -net_
if for all $x\in{\mathcal{X}}$, there exists $x^{\prime}\in{\mathcal{N}}$ such
that $\operatorname{dist}(x,x^{\prime})\leq\eta$.

The following lemma can be proved by taking a simple coordinate quantization.
A proof can be found in, e.g., [ZBJ20].

######  Lemma 5 (Bound on size of a net).

Let ${\mathcal{X}}$ be a finite alphabet. For any constant $\eta>0$, there
exists an $\eta$-net of $(\Delta({\mathcal{X}}),d_{\infty})$ of size at most
$\left\lceil\frac{{\left|{\mathcal{X}}\right|}}{2\eta}\right\rceil^{{\left|{\mathcal{X}}\right|}}\leq\left(\frac{{\left|{\mathcal{X}}\right|}}{2\eta}+1\right)^{{\left|{\mathcal{X}}\right|}}$.

######  Fact 6.

For any ${\underline{x}},{\underline{y}}\in{\mathbb{R}}^{k}$, we have
$d_{{\infty}}\left({\underline{x}},{\underline{y}}\right)\leq
d_{{1}}\left({\underline{x}},{\underline{y}}\right)\leq k\cdot
d_{{\infty}}\left({\underline{x}},{\underline{y}}\right)$.

######  Definition 2 (Kullback–Leibler (KL) divergence).

Let ${\mathcal{X}}$ be a finite set and let $P,Q\in\Delta({\mathcal{X}})$.
Assume that $P$ is absolutely continuous w.r.t. $Q$ (i.e.,
$\operatorname{supp}(P)\subseteq\operatorname{supp}(Q)$). The
_Kullback–Leibler (KL) divergence_ between $P$ and $Q$ is defined as
$D\left(P\middle\|Q\right)\coloneqq\sum_{x\in{\mathcal{X}}}P(x)\log\frac{P(x)}{Q(x)}$.

######  Definition 3 (Types).

Let ${\mathcal{X}}$ be a finite set and $n\in{\mathbb{Z}}_{\geq 1}$. The
_type_ of a vector ${\underline{x}}\in{\mathcal{X}}^{n}$, denoted by
$\tau_{\underline{x}}\in\Delta({\mathcal{X}})$, is the empirical
distribution/histogram of ${\underline{x}}$ defined as: for every
$x\in{\mathcal{X}}$,
$\tau_{\underline{x}}(x)=\frac{1}{n}\left|\left\\{i\in[n]\colon{\underline{x}}(i)=x\right\\}\right|$.
The set of all types of ${\mathcal{X}}^{n}$-valued vectors is denoted by
$\Delta^{(n)}({\mathcal{X}})$. Let ${\mathcal{Y}}$ be another finite set and
${\underline{y}}\in{\mathcal{Y}}^{n}$. The _joint type_
$\tau_{{\underline{x}},{\underline{y}}}$ (and
$\Delta^{(n)}({\mathcal{X}}\times{\mathcal{Y}})$ correspondingly) and the
_conditional type_ $\tau_{{\underline{x}}|{\underline{y}}}$ (and
$\Delta^{(n)}({\mathcal{X}}|{\mathcal{Y}})$ correspondingly) are defined in a
similar manner. Furthermore, these definitions can be extended to tuples of
vectors in the canonical way. The set of vectors of the same type is called a
_type class_.

######  Fact 7 (Types are dense in distributions).

Let ${\mathcal{X}}$ be a finite set. The set $\bigcup_{n\in{\mathbb{Z}}_{\geq
1}}\Delta^{(n)}({\mathcal{X}})$ of types induced by vectors of all possible
lengths is dense in the corresponding set $\Delta({\mathcal{X}})$ of
distributions.

The number of types of length-$n$ vectors is polynomial in $n$.

######  Lemma 8 (Number of types [Csi98]).

The number of types corresponding to ${\mathcal{X}}^{n}$-valued vectors equals
$\binom{n-\left|{\mathcal{X}}\right|-1}{\left|{\mathcal{X}}\right|-1}\leq(n+\left|{\mathcal{X}}\right|-1)^{\left|{\mathcal{X}}\right|-1}$.

######  Lemma 9 (Marginalization does not increase distance).

Let
$P_{{\mathbf{a}},{\mathbf{b}}},Q_{{\mathbf{a}},{\mathbf{b}}}\in\Delta({\mathcal{A}}\times{\mathcal{B}})$.
Then
$d_{{1}}\left(\left[P_{{\mathbf{a}},{\mathbf{b}}}\right]_{{\mathbf{a}}},\left[Q_{{\mathbf{a}},{\mathbf{b}}}\right]_{{\mathbf{a}}}\right)\leq
d_{{1}}\left(P_{{\mathbf{a}},{\mathbf{b}}},Q_{{\mathbf{a}},{\mathbf{b}}}\right)$.

###### Proof.

The lemma follows from triangle inequality.

$\displaystyle
d_{{1}}\left(\left[P_{{\mathbf{a}},{\mathbf{b}}}\right]_{{\mathbf{a}}},\left[Q_{{\mathbf{a}},{\mathbf{b}}}\right]_{{\mathbf{a}}}\right)\leq$
$\displaystyle\sum_{a\in{\mathcal{A}}}\left|\sum_{b\in{\mathcal{B}}}P_{{\mathbf{a}},{\mathbf{b}}}(a,b)-\sum_{b\in{\mathcal{B}}}Q_{{\mathbf{a}},{\mathbf{b}}}(a,b)\right|\leq\sum_{(a,b)\in{\mathcal{A}}\times{\mathcal{B}}}\left|P_{{\mathbf{a}},{\mathbf{b}}}(a,b)-Q_{{\mathbf{a}},{\mathbf{b}}}(a,b)\right|=d_{{1}}\left(P_{{\mathbf{a}},{\mathbf{b}}},Q_{{\mathbf{a}},{\mathbf{b}}}\right).\qed$
(2)

##  VII Basic definitions

###  VII-A Channel and coding

######  Definition 4 (Omniscient adversarial MACs).

An _omniscient adversarial two-user multiple access channel (MAC)_
$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$
is comprised of

  1. 1.

three alphabets
${\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}}$ for the
input sequence from the first user, the input sequence from the second user,
the jamming sequence and the output sequence, respectively;

  2. 2.

input constraints $\Gamma_{1}\subseteq\Delta({\mathcal{X}}_{1})$ and
$\Gamma_{2}\subseteq\Delta({\mathcal{X}}_{2})$ for the first and second users,
respectively;

  3. 3.

state constraints $\Lambda\subseteq\Delta({\mathcal{S}})$ for the jammer;

  4. 4.

and the adversarial channel transition law
$W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}$ that is
governed by the adversary.

Suppose that the first (resp. second) transmitter wishes to send a message
$m^{1}\in[M_{1}]$ (resp. $m^{2}\in[M_{2}]$) to the receiver. They are allowed
to encode101010Importantly, the encoding process must be completed locally by
two individual encoders without cooperation.  $(m^{1},m^{2})$ into two
sequences (called _codewords_)
$\operatorname{Enc}_{1}(m^{1})={\underline{x}}^{1}\in{\mathcal{X}}_{1}^{n}$
and
$\operatorname{Enc}_{2}(m^{2})={\underline{x}}^{2}\in{\mathcal{X}}_{2}^{n}$
respectively such that
$\tau_{{\underline{x}}^{1}}\in\Gamma_{1},\tau_{{\underline{x}}^{2}}\in\Gamma_{2}$.
These two codewords are transmitted into the channel. Knowing the transmitted
${\underline{x}}^{1},{\underline{x}}^{2}$ and the codebooks
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\in{\mathcal{X}}_{1}^{M_{1}\times
n}\times{\mathcal{X}}_{2}^{M_{2}\times n}$ (i.e., the collection of codeword
pairs that encode the messages in $[M_{1}]\times[M_{2}]$; see Definition 5),
the adversary injects an adversarial noise (a.k.a. the _state vector_ or
_jamming vector_) ${\underline{s}}\in{\mathcal{S}}^{n}$ such that
$\tau_{{\underline{s}}}\in\Lambda$. The channel acts on the inputs
${\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}}$ and generates an
output ${\underline{\mathbf{y}}}$ memorylessly, i.e., for any
${\underline{y}}\in{\mathcal{Y}}^{n}$,

$\displaystyle
W_{{\underline{\mathbf{y}}}|{\underline{\mathbf{x}}}^{1},{\underline{\mathbf{x}}}^{2},{\underline{\mathbf{s}}}}\left({\underline{y}}|{\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}}\right)=W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}^{\otimes
n}\left({\underline{y}}|{\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}}\right)=\prod_{j=1}^{n}W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left({\underline{y}}(j)|{\underline{x}}^{1}(j),{\underline{x}}^{2}(j),{\underline{s}}(j)\right).$

Receiving ${\underline{\mathbf{y}}}$, the decoder is required to output an
estimate
$\operatorname{Dec}({\underline{\mathbf{y}}})=\left(\widehat{m}^{1},\widehat{m}^{2}\right)$
of the transmitted messages $(m^{1},m^{2})$. See Figure 1 for a system diagram
of $\mathsf{MAC}_{2}$.

Figure 1: A system diagram of a general two-user omniscient adversarial MAC.

######  Remark 2.

Though the channel from the transmitters to the receiver is memoryless, the
state vector ${\underline{\mathbf{s}}}$ is not necessarily generated
memorylessly by the jammer given
${\underline{\mathbf{x}}}^{1},{\underline{\mathbf{x}}}^{2}$. That is,
$P_{{\underline{\mathbf{s}}}|{\underline{\mathbf{x}}}^{1},{\underline{\mathbf{x}}}^{2}}$
may not factor. Indeed, the adversary can put probability mass one on a single
sequence ${\underline{s}}$.

######  Definition 5 (Codes).

A code pair $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ for an omniscient
adversarial MAC
$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$
consists of

  1. 1.

two encoders $\operatorname{Enc}_{1}\colon[M_{1}]\to{\mathcal{X}}_{1}^{n}$ and
$\operatorname{Enc}_{2}\colon[M_{2}]\to{\mathcal{X}}_{2}^{n}$ for the first
and the second users which map $m^{1}\in[M_{1}]$ and $m^{2}\in[M_{2}]$ to
$\operatorname{Enc}_{1}(m^{1})={\underline{x}}^{1}_{m^{1}}$ and
$\operatorname{Enc}_{2}(m^{2})={\underline{x}}^{2}_{m^{2}}$ respectively; and

  2. 2.

a decoder $\operatorname{Dec}\colon{\mathcal{Y}}^{n}\to[M_{1}]\times[M_{2}]$
that maps ${\underline{y}}$ to
$\operatorname{Dec}({\underline{y}})=\left(\widehat{m}^{1},\widehat{m}^{2}\right)$.

We call the images of $\operatorname{Enc}_{1}$ and $\operatorname{Enc}_{2}$ a
_codebook pair_ (or simply a _code pair_ , overloading the terminology),
denoted, with a slight abuse of notation, by
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\in{\mathcal{X}}_{1}^{M_{1}\times
n}\times{\mathcal{X}}_{2}^{M_{2}\times n}$. The length $n$ of each codeword is
called the _blocklength_. The _rate pair_ of
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ is defined as
$R_{1}=R({\mathcal{C}}_{1})\coloneqq\frac{\log
M_{1}}{n\log\left|{\mathcal{X}}_{1}\right|}$ and
$R_{2}=R({\mathcal{C}}_{2})\coloneqq\frac{\log
M_{2}}{n\log\left|{\mathcal{X}}_{2}\right|}$.

We assume that the code pair $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ is known
to $\operatorname{Enc}_{1},\operatorname{Enc}_{2},\operatorname{Jam}$ (see
Definition 6 below) and is fixed before communication is instantiated.

######  Remark 3.

When we talk about “a” code (pair), we always mean an infinite sequence of
codes of increasing blocklengths, i.e.,
$\left\\{\left({\mathcal{C}}_{1}^{(i)},{\mathcal{C}}_{2}^{(i)}\right)\right\\}_{i\geq
1}$ each of blocklength $n_{i}$ where $n_{1}<n_{2}<\cdots\in{\mathbb{Z}}_{\geq
1}$.

######  Definition 6 (Maximum probability of error).

A code pair
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\in{\mathcal{X}}_{1}^{M_{1}\times
n}\times{\mathcal{X}}_{2}^{M_{2}\times n}$ (equipped with encoders
$\operatorname{Enc}_{1},\operatorname{Enc}_{2}$ and a decoder
$\operatorname{Dec}$) is said to attain _maximum probability of error
$\varepsilon$_ for an omniscient adversarial MAC

$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$

if

$\displaystyle\max_{(m^{1},m^{2})\in[M_{1}]\times[M_{2}]}\max_{\begin{subarray}{c}\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))\in{\mathcal{S}}^{n}\\\
\tau_{\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))}\in\Lambda\end{subarray}}{\mathop{\Pr}_{{\underline{\mathbf{y}}}\sim
W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}^{\otimes
n}\left(\cdot|\operatorname{Enc}_{1}\left(m^{1}\right),\operatorname{Enc}_{2}\left(m^{2}\right),\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))\right)}\left[\operatorname{Dec}\left({\underline{\mathbf{y}}}\right)\neq\left(m^{1},m^{2}\right)\right]}$
$\displaystyle=$
$\displaystyle\max_{(m^{1},m^{2})\in[M_{1}]\times[M_{2}]}\max_{\begin{subarray}{c}\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))\in{\mathcal{S}}^{n}\\\
\tau_{\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))}\in\Lambda\end{subarray}}\sum_{{\underline{y}}\in{\mathcal{Y}}^{n}:\operatorname{Dec}({\underline{y}})\neq(m^{1},m^{2})}W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}^{\otimes
n}\left({\underline{y}}|\operatorname{Enc}_{1}\left(m^{1}\right),\operatorname{Enc}_{2}\left(m^{2}\right),\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))\right)$
$\displaystyle\leq$ $\displaystyle\varepsilon.$ (3)

The second maximization is over all legitimate jamming functions
$\operatorname{Jam}\colon{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}\to{\mathcal{S}}^{n}$
such that
$\tau_{\operatorname{Jam}(\operatorname{Enc}_{1}(m^{1}),\operatorname{Enc}_{2}(m^{2}))}\in\Lambda$.

######  Remark 4.

We emphasize that this paper is focused on the maximum probability of error as
defined in Definition 6. One can instead place different bounds on the
constituent error probabilities [TK13]

$\displaystyle\max_{(m^{1},m^{2})\in[M_{1}]\times[M_{2}]}\max_{{\underline{s}}:\tau_{\underline{s}}\in\Lambda}\Pr\left[\left\\{\widehat{\mathbf{m}}^{1}\neq
m^{1}\right\\}\cup\left\\{\widehat{\mathbf{m}}^{2}\neq m^{2}\right\\}\right],$
$\displaystyle\max_{(m^{1},m^{2})\in[M_{1}]\times[M_{2}]}\max_{{\underline{s}}:\tau_{\underline{s}}\in\Lambda}\Pr\left[{\widehat{\mathbf{m}}^{1}\neq
m^{1}}\right],$
$\displaystyle\max_{(m^{1},m^{2})\in[M_{1}]\times[M_{2}]}\max_{{\underline{s}}:\tau_{\underline{s}}\in\Lambda}\Pr\left[{\widehat{\mathbf{m}}^{2}\neq
m^{2}}\right].$

This may create wacky behaviours of the capacity region [ZVJ20] and is a more
challenging question.

######  Definition 7 (Achievable rate pairs and capacity region).

A rate pair $(R_{1},R_{2})$ is said to be _achievable_ for an omniscient
adversarial MAC $\mathsf{MAC}_{2}$ under the maximum error criterion if there
exists a code ${({\mathcal{C}}_{1},{\mathcal{C}}_{2})}$ for $\mathsf{MAC}_{2}$
of rates $R({\mathcal{C}}_{1})\geq R_{1}$ and $R({\mathcal{C}}_{2})\geq R_{2}$
with $o(1)$ maximum probability of error. The closure of all achievable rate
pairs is called the _capacity region_ of $\mathsf{MAC}_{2}$.

######  Definition 8 (Constant composition codes).

A code ${\mathcal{C}}\subseteq{\mathcal{X}}^{n}$ is called $P$-constant
composition for some distribution $P\in\Delta({\mathcal{X}})$ if all codewords
in ${\mathcal{C}}$ have type $P$.

A simple application of Markov’s inequality and Lemma 8 yields the following
reduction from general codes to constant composition codes.

######  Lemma 10 (Constant composition reduction).

For any code ${\mathcal{C}}\subseteq{\mathcal{X}}^{n}$, there exists a
constant composition subcode ${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ of
size at least
$|{\mathcal{C}}|/(n+\left|{\mathcal{X}}\right|-1)^{\left|{\mathcal{X}}\right|-1}$.
In particular, $R({\mathcal{C}}^{\prime})$ is the same as $R({\mathcal{C}})$
(asymptotically in $n$).

Lemma 10 shows that for the purpose of understanding the capacity (region), it
suffices to study constant composition codes. Throughout this paper, we focus
on constant composition code pairs by fixing two feasible input distributions
$(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

###  VII-B Additional technical assumptions

For technical reasons, we make further assumptions on the model considered
throughout this paper.

  1. 1.

All alphabets
${\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}}$ are finite.
In particular, our proof will heavily rely on the assumption of the finiteness
of ${\mathcal{X}}_{1}$ and ${\mathcal{X}}_{2}$. It is unclear how to extend
our results to the large alphabet regime, e.g., the case where
$\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|$ are increasing
in $n$. In fact, we believe that the behaviour of adversarial MACs is
considerably different when the alphabet sizes are sufficiently large. See
Item 11 in Section XVI.

  2. 2.

In this work we only focus on _state deterministic_ channels, i.e., channels
for which $W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}$ is
a zero-one law. Alternatively, the channel transition law can be written as a
(deterministic) function
$W\colon{\mathcal{X}}_{1}\times{\mathcal{X}}_{2}\times{\mathcal{S}}\to{\mathcal{Y}}$
such that $y=W(x^{1},x^{2},s)$.

  3. 3.

To avoid peculiar behaviours, we assume that $\Gamma_{1},\Gamma_{2},\Lambda$
are all convex sets.

  4. 4.

We do not assume the availability of common randomness between the encoders
and the decoder (while kept secret from the jammer). In the AVC literature,
the capacity in the presence of shared randomness is known as the _random code
capacity_ [Ahl78, CN88a].

  5. 5.

No party in the system is allowed to use private randomness. That is, the
encoding/jamming/decoding functions are all deterministic. In the case of
point-to-point omniscient adversarial channels [WBBJ19], there are reductions
showing that the capacity remains the same under stochastic/deterministic
encoding/jamming/decoding. Furthermore, average error criterion is equivalent
to maximum error criterion which is further equivalent to zero error criterion
when the channel is deterministic. Therefore, the omniscient point-to-point
channel problem is combinatorial in nature. However, for our model of
omniscient MACs, as alluded to in Remark 1, we expect neither the equivalence
between stochastic and deterministic encoding nor the equivalence between
average/maximum probability of error. For simplicity, we choose to work with
deterministic encoding/jamming/decoding and maximum/zero error criterion in
this paper. The average probability of error counterpart is left for future
study (see Item 1 in Section XVI).

Under the above assumptions of deterministic encoding/jamming/decoding/channel
law and maximum error criterion, the probability in Equation 3 is either zero
or one. Therefore, vanishing maximum probability of error implies zero error.
This enforces a combinatorial nature of the problem in hand. Our results serve
as a first step towards understanding omniscient adversarial MACs.

##  VIII Warmup example: binary noisy $\operatorname{\mathsf{XOR}}$ MAC

In this section, we study a warmup example of binary noisy
$\operatorname{\mathsf{XOR}}$ MAC defined as follows.

######  Definition 9 (Binary noisy $\operatorname{\mathsf{XOR}}$ MAC).

A two-user binary noisy $\operatorname{\mathsf{XOR}}$ MAC
$\mathsf{XOR}\text{-}\mathsf{MAC}_{2}(p)$ takes as input two binary
transmissions
$({\underline{x}}^{1},{\underline{x}}^{2})\in\left(\\{0,1\\}^{n}\right)^{2}$
and a binary noise sequence ${\underline{s}}\in\\{0,1\\}^{n}$ with (relative)
Hamming weight at most $p$ and outputs
${\underline{y}}={\underline{x}}^{1}\oplus{\underline{x}}^{1}\oplus{\underline{s}}$
where the addition is modulo two.

The following theorem generalizes the classical Plotkin bound in coding theory
to the multiuser setting.

######  Theorem 11.

If $p>1/4$, then there exists no rate pairs $(R_{1},R_{2})$ such that
$R_{1}>0,R_{2}>0$.

###### Proof.

See Appendix B. ∎

##  IX Confusability sets and their properties

In this section, we introduce one of the core definitions of this paper: the
_confusability sets_ associated to an adversarial MAC. They are the sets of
_bad_ distributions that any good code should avoid. As the name suggests,
they precisely characterize the “confusability” of a given channel. In fact,
they determine the capacity region of the channel and therefore are arguably
the most important statistics associated to the channel. Some properties of
confusability sets are proved.

We first present an obvious-looking claim which relates the the zero error
criterion with _operational non-confusability_.

######  Claim 12 (Equivalence between zero error and operational non-
confusability).

Let
$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$
be a two-user omniscient adversarial MAC. A code pair
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\in{\mathcal{X}}_{1}^{M_{1}\times
n}\times{\mathcal{X}}_{2}^{M_{2}\times n}$ attains zero error for
$\mathsf{MAC}_{2}$ if and only if all of the following conditions (which we
call _operational non-confusability_ conditions) are satisfied:

  1. 1.

for all $1\leq i_{1}\neq i_{2}\leq M_{1}$ and $1\leq j_{1}\neq j_{2}\leq
M_{2}$, there do not exist
${\underline{s}}^{1},{\underline{s}}^{2}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}^{1}},\tau_{{\underline{s}}^{2}}\in\Lambda$ such that
$W({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{s}}^{1})=W({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}},{\underline{s}}^{2})$;
in this case we say that
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}})$ and
$({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}})$ are _non-
confusable_ ;

  2. 2.

for all $1\leq i_{1}\neq i_{2}\leq M_{1}$ and $1\leq j\leq M_{2}$, there do
not exist ${\underline{s}}^{1},{\underline{s}}^{2}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}^{1}},\tau_{{\underline{s}}^{2}}\in\Lambda$ such that
$W({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j},{\underline{s}}^{1})=W({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j},{\underline{s}}^{2})$;
in this case we say that
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j})$ and
$({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j})$ are _non-confusable_ ;

  3. 3.

for all $1\leq i\leq M_{1}$ and $1\leq j_{1}\neq j_{2}\leq M_{2}$, there do
not exist ${\underline{s}}^{1},{\underline{s}}^{2}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}^{1}},\tau_{{\underline{s}}^{2}}\in\Lambda$ such that
$W({\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{s}}^{1})=W({\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{2}},{\underline{s}}^{2})$;
in this case we say that
$({\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}})$ and
$({\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{2}})$ are _non-confusable_.

###### Proof.

Intuitively, a violation of the zero error criterion must be the case where a
received vector ${\underline{y}}$ can be explained by (at least) two distinct
pairs of codewords via admissible jamming vectors. In this case, the decoder
is confused by (at least) two candidate pairs of codewords and is forced to
make a decoding error with nonzero probability. Formally, the claim follows
from the following simple arguments.

We first prove the contrapositive of the direct part. If
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ has nonzero error, then there must
exist a pair of codewords
$({\underline{x}}^{1},{\underline{x}}^{2})\in({\mathcal{C}}_{1},{\mathcal{C}}_{2})$
which leads to a decoding error. In particular, at least one of
${\underline{x}}^{1}$ and ${\underline{x}}^{2}$ cannot be correctly decoded.
Then at least one of Items 1, 2 and 3 must be satisfied. Indeed,

  1. 1.

Item 1 corresponds to the case where neither ${\underline{x}}^{1}$ nor
${\underline{x}}^{2}$ can be correctly decoded. More specifically, there must
exist another pair of codewords
$\widetilde{\underline{x}}^{1}\neq{\underline{x}}^{1}$ and
$\widetilde{\underline{x}}^{2}\neq{\underline{x}}^{2}$ such that
$W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})=W(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2},\widetilde{\underline{s}})$
for some ${\underline{s}},\widetilde{\underline{s}}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}},\tau_{\widetilde{\underline{s}}}\in\Lambda$. In this
case, the decoder could not decide to output
$({\underline{x}}^{1},{\underline{x}}^{2})$ or
$(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2})$.

  2. 2.

Item 2 corresponds to the case where ${\underline{x}}^{1}$ is confusable with
another codeword. More specifically, there must exist another codeword
$\widetilde{\underline{x}}^{1}\neq{\underline{x}}^{1}$ such that
$W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})=W(\widetilde{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{s}})$
for some ${\underline{s}},\widetilde{\underline{s}}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}},\tau_{\widetilde{\underline{s}}}\in\Lambda$. In this
case, the decoder could not decide to output
$({\underline{x}}^{1},{\underline{x}}^{2})$ or
$(\widetilde{\underline{x}}^{1},{\underline{x}}^{2})$.

  3. 3.

Item 3 corresponds to the case where ${\underline{x}}^{2}$ is confusable with
another codeword. More specifically, there must exist another codeword
$\widetilde{\underline{x}}^{2}\neq{\underline{x}}^{2}$ such that
$W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})=W({\underline{x}}^{1},\widetilde{\underline{x}}^{2},\widetilde{\underline{s}})$
for some ${\underline{s}},\widetilde{\underline{s}}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}},\tau_{\widetilde{\underline{s}}}\in\Lambda$. In this
case, the decoder could not decide to output
$({\underline{x}}^{1},{\underline{x}}^{2})$ or
$({\underline{x}}^{1},\widetilde{\underline{x}}^{2})$.

The converse part is straightforward. If a code pair
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ attains zero error, then none of Items
1, 2 and 3 is satisfied. Otherwise, (at least) one of Items 1, 2 and 3 above
holds which results in a decoding error, violating the zero-error assumption.
∎

######  Claim 13 (Permutation invariance of operational (non-)confusability).

If two pairs of codewords $({\underline{x}}^{1},{\underline{x}}^{2})$ and
$(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2})$ (resp.
$(\widetilde{\underline{x}}^{1},{\underline{x}}^{2})$ or
$({\underline{x}}^{1},\widetilde{\underline{x}}^{2})$) are confusable/non-
confusable (in the sense of 12), then any other pairs
$({\underline{x}}^{1}_{*},{\underline{x}}^{2}_{*})$ and
$(\widetilde{\underline{x}}^{1}_{*},\widetilde{\underline{x}}^{2}_{*})$ (resp.
$(\widetilde{\underline{x}}^{1}_{*},{\underline{x}}^{2}_{*})$ or
$({\underline{x}}^{1}_{*},\widetilde{\underline{x}}^{2}_{*})$) of the same
joint type
$\tau_{{\underline{x}}^{1}_{*},\widetilde{\underline{x}}^{1}_{*},{\underline{x}}^{2}_{*},\widetilde{\underline{x}}^{2}_{*}}=\tau_{{\underline{x}}^{1},\widetilde{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{x}}^{2}}$
(resp.
$\tau_{{\underline{x}}^{1}_{*},\widetilde{\underline{x}}^{1}_{*},{\underline{x}}^{2}_{*}}=\tau_{{\underline{x}}^{1},\widetilde{\underline{x}}^{1},{\underline{x}}^{2}}$
or
$\tau_{{\underline{x}}^{1}_{*},{\underline{x}}^{2}_{*},\widetilde{\underline{x}}^{2}_{*}}=\tau_{{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{x}}^{2}}$)
are also confusable/non-confusable.

###### Proof.

Since the channel is component-wise and memoryless, the confusability
conditions (Items 1, 2 and 3 in 12) are invariant under coordinate
permutations. That is, $({\underline{x}}^{1},{\underline{x}}^{2})$ is
confusable with
$(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2})$ (resp.
$(\widetilde{\underline{x}}^{1},{\underline{x}}^{2})$ or
$({\underline{x}}^{1},\widetilde{\underline{x}}^{2})$) if and only if
$(\pi({\underline{x}}^{1}),\pi({\underline{x}}^{2}))$ is confusable with
$(\pi(\widetilde{\underline{x}}^{1}),\pi(\widetilde{\underline{x}}^{2}))$
(resp. $(\pi(\widetilde{\underline{x}}^{1}),\pi({\underline{x}}^{2}))$ or
$(\pi({\underline{x}}^{1}),\pi(\widetilde{\underline{x}}^{2}))$) for any
$\pi\in S_{n}$. Here for a vector
${\underline{v}}=({\underline{v}}(1),\cdots,{\underline{v}}(n))\in{\mathcal{V}}^{n}$,
we use the notation
$\pi({\underline{v}})\coloneqq({\underline{v}}(\pi(1)),\cdots,{\underline{v}}(\pi(n)))$.
Indeed, one simply takes $\pi({\underline{s}}),\pi(\widetilde{\underline{s}})$
of type $\tau_{\pi({\underline{s}})}=\tau_{{\underline{s}}}\in\Lambda$ and
$\tau_{\pi(\widetilde{\underline{s}})}=\tau_{\widetilde{\underline{s}}}\in\Lambda$.
Then for any $j\in[n]$,

$\displaystyle
W(\pi({\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi({\underline{s}}))(j)=$
$\displaystyle
W(\pi({\underline{x}}^{1})(j),\pi({\underline{x}}^{2})(j),\pi({\underline{s}})(j))$
(4) $\displaystyle=$ $\displaystyle
W({\underline{x}}^{1}(\pi(j)),{\underline{x}}^{2}(\pi(j)),{\underline{s}}(\pi(j)))$
$\displaystyle=$ $\displaystyle
W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})(\pi(j))$
$\displaystyle=$
$\displaystyle\pi(W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}}))(j).$

Equation 4 is because the channel acts on the inputs component-wise. That is,
$W(\pi({\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi({\underline{s}}))=\pi(W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}}))$.
Similarly,
$W(\pi(\widetilde{\underline{x}}^{1}),\pi(\widetilde{\underline{x}}^{2}),\pi(\widetilde{\underline{s}}))=\pi(W(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2},\widetilde{\underline{s}}))$
(resp.
$W(\pi(\widetilde{\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi(\widetilde{\underline{s}}))=\pi(W(\widetilde{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{s}}))$
or
$W(\pi({\underline{x}}^{1}),\pi(\widetilde{\underline{x}}^{2}),\pi(\widetilde{\underline{s}}))=\pi(W({\underline{x}}^{1},\widetilde{\underline{x}}^{2},\widetilde{\underline{s}}))$).
Since
$W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})=W(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2},\widetilde{\underline{s}})$
(resp.
$W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})=W(\widetilde{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{s}})$
or
$W({\underline{x}}^{1},{\underline{x}}^{2},{\underline{s}})=W({\underline{x}}^{1},\widetilde{\underline{x}}^{2},\widetilde{\underline{s}})$)
and $\pi$ is bijective, we have
$W(\pi({\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi({\underline{s}}))=W(\pi(\widetilde{\underline{x}}^{1}),\pi(\widetilde{\underline{x}}^{2}),\pi(\widetilde{\underline{s}}))$
(resp.
$W(\pi({\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi({\underline{s}}))=W(\pi(\widetilde{\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi(\widetilde{\underline{s}}))$
or
$W(\pi({\underline{x}}^{1}),\pi({\underline{x}}^{2}),\pi({\underline{s}}))=W(\pi({\underline{x}}^{1}),\pi(\widetilde{\underline{x}}^{2}),\pi(\widetilde{\underline{s}}))$).

Finally, permutation invariance of confusability follows from the observation
that all vectors of the same type can be obtained by properly permuting the
coordinates. Since permutations are bijections, non-confusability is also
invariant under coordinate permutation. ∎

We are ready to give the definition of confusability sets. Before doing so, we
first define _self-couplings_ as distributions with prescribed marginals in
accordance with the use of constant composition code pairs.

######  Definition 10 (Self-couplings).

$\displaystyle{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\Delta({\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2})\colon\begin{array}[]{l}\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1}}=\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{2}}=P_{1},\\\
\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{1}}=\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{2}}=P_{2}\end{array}\right\\},$
(7) $\displaystyle{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2})\colon\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right]_{{\mathbf{x}}^{1}_{1}}=\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right]_{{\mathbf{x}}^{1}_{2}}=P_{1},\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right]_{{\mathbf{x}}^{2}}=P_{2}\right\\},$
$\displaystyle{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\Delta({\mathcal{X}}_{1}\times{\mathcal{X}}_{2}^{2})\colon\left[P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}}=P_{1},\left[P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{1}}=\left[P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{2}}=P_{2}\right\\}.$

The previous two claims (12, 13) motivate us to make the following definition
of _confusability sets_. One should think of the conditions in the definition
below as the distributional version of operational confusability in 12.

######  Definition 11 (Confusability sets).

Let
$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$
be a 2-user adversarial MAC. Let $P_{1}\in\Delta({\mathcal{X}}_{1})$ and
$P_{2}\in\Delta({\mathcal{X}}_{2})$. The _joint confusability set_
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$, the _first marginal
confusability set_ ${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and the
_second marginal confusability set_
${\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$ of $\mathsf{MAC}_{2}$ w.r.t.
input distributions $P_{1}$ and $P_{2}$ are defined as follows:

$\displaystyle{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{\begin{array}[]{rl}&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\colon\\\
\exists&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\in\Delta\left({\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}}\right)\mathrm{\
s.t.}\\\
&\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}};\\\
\forall&\left(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y\right)\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}},\\\
&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\left(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y\right)\\\
=&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2}\right)P_{{\mathbf{s}}_{1},{\mathbf{s}}_{2}|{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(s_{1},s_{2}|x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2}\right)W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left(y|x^{1}_{1},x^{2}_{1},s_{1}\right)\\\
=&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2}\right)P_{{\mathbf{s}}_{1},{\mathbf{s}}_{2}|{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(s_{1},s_{2}|x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2}\right)W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left(y|x^{1}_{2},x^{2}_{2},s_{2}\right)\end{array}\right\\},$
(15) $\displaystyle{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{\begin{array}[]{rl}&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\colon\\\
\exists&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\in\Delta\left({\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}}\right)\mathrm{\
s.t.}\\\
&\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}=P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}};\\\
\forall&\left(x^{1}_{1},x^{1}_{2},x^{2},s_{1},s_{2},y\right)\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}},\\\
&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\left(x^{1}_{1},x^{1}_{2},x^{2},s_{1},s_{2},y\right)\\\
=&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\left(x^{1}_{1},x^{1}_{2},x^{2}\right)P_{{\mathbf{s}}_{1},{\mathbf{s}}_{2}|{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\left(s_{1},s_{2}|x^{1}_{1},x^{1}_{2},x^{2}\right)W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left(y|x^{1}_{1},x^{2},s_{1}\right)\\\
=&P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}(x^{1}_{1},x^{1}_{2},x^{2})P_{{\mathbf{s}}_{1},{\mathbf{s}}_{2}|{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\left(s_{1},s_{2}|x^{1}_{1},x^{1}_{2},x^{2}\right)W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left(y|x^{1}_{2},x^{2},s_{2}\right)\end{array}\right\\},$
(23) $\displaystyle{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{\begin{array}[]{rl}&P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)\colon\\\
\exists&P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\in\Delta\left({\mathcal{X}}_{1}\times{\mathcal{X}}_{2}^{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}}\right)\mathrm{\
s.t.}\\\
&\left[P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\right]_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}};\\\
\forall&\left(x^{1},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y\right)\in{\mathcal{X}}_{1}\times{\mathcal{X}}_{2}^{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}},\\\
&P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{s}}_{1},{\mathbf{s}}_{2},{\mathbf{y}}}\left(x^{1},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y\right)\\\
=&P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(x^{1},x^{2}_{1},x^{2}_{2}\right)P_{{\mathbf{s}}_{1},{\mathbf{s}}_{2}|{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(s_{1},s_{2}|x^{1},x^{2}_{1},x^{2}_{2}\right)W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left(y|x^{1},x^{2}_{1},s_{1}\right)\\\
=&P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(x^{1},x^{2}_{1},x^{2}_{2}\right)P_{{\mathbf{s}}_{1},{\mathbf{s}}_{2}|{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\left(s_{1},s_{2}|x^{1},x^{2}_{1},x^{2}_{2}\right)W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}\left(y|x^{1},x^{2}_{2},s_{2}\right)\end{array}\right\\}.$
(31)

One should think of confusability sets as the sets of _bad_
distributions/types that any (sequence of) good codes should avoid. Indeed,
one has the following claim.

######  Claim 14.

Let
$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$
be a 2-user adversarial MAC and let
$\left(P_{1},P_{2}\right)\in\Gamma_{1}\times\Gamma_{2}$ be a pair of feasible
input distributions. Let
$\left\\{\left({\mathcal{C}}_{1,i},{\mathcal{C}}_{2,i}\right)\right\\}_{i}\subseteq{\mathcal{X}}_{1}^{n_{i}}\times{\mathcal{X}}_{2}^{n_{i}}$
be a sequence of pairs of $P_{1}$\- and $P_{2}$-constant composition codes of
increasing blocklengths $n_{i}$’s. Then
$\left\\{\left({\mathcal{C}}_{1,i},{\mathcal{C}}_{2,i}\right)\right\\}_{i}$
achieves zero error for $\mathsf{MAC}_{2}$ if an only if for every $i$, there
is no
$\left({\underline{x}}^{1}_{1},{\underline{x}}^{2}_{1}\right),\left({\underline{x}}^{1}_{2},{\underline{x}}^{2}_{2}\right)\in{\mathcal{C}}_{1,i}\times{\mathcal{C}}_{2,i}$
and ${\underline{x}}^{1}\in{\mathcal{C}}_{1,i}$,
${\underline{x}}^{2}\in{\mathcal{C}}_{2,i}$, such that at least one of the
following happens:
$\tau_{{\underline{x}}^{1}_{1},{\underline{x}}^{1}_{2},{\underline{x}}^{2}_{1}{\underline{x}}^{2}_{2}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$,
$\tau_{{\underline{x}}^{1}_{1},{\underline{x}}^{1}_{2},{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$,
$\tau_{{\underline{x}}^{1},{\underline{x}}^{2}_{1},{\underline{x}}^{2}_{2}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$.

###### Proof.

13 implies that the non-confusability properties (Items 1, 2 and 3 in 12)
depend only on the _type_ of vectors rather than the order of coordinates. We
can therefore quotient out type classes (Definition 3) and work with types
instead of vectors.111111Formally, let $\sim_{\mathrm{perm}}$ be a relation on
vectors defined as
${\underline{v}}\sim_{\mathrm{perm}}{\underline{v}}^{\prime}$ iff there is
$\pi\in S_{n}$ such that ${\underline{v}}^{\prime}=\pi({\underline{v}})$. It
is easy to check that $\sim_{\mathrm{perm}}$ is an equivalence relation. As 13
suggests, the confusability property is a _class invariant_ under
$\sim_{\mathrm{perm}}$, i.e., it is invariant in each equivalence class by
$\sim_{\mathrm{perm}}$. For the purpose of studying confusability, one can
without loss of generality focus on equivalence classes (i.e., types) rather
than vectors.  The above conditions are equivalent to

  1. 1.

for all $1\leq i_{1}\neq i_{2}\leq|{\mathcal{C}}_{1}|$ and $1\leq j_{1}\neq
j_{2}\leq|{\mathcal{C}}_{2}|$, there do not exist
${\underline{s}}^{1},{\underline{s}}^{2}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}^{1}},\tau_{{\underline{s}}^{2}}\in\Lambda$ and
${\underline{y}}\in{\mathcal{Y}}^{n}$ such that

$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}},{\underline{s}}^{1},{\underline{s}}^{2},{\underline{y}}}(x^{1}_{1},x^{2}_{1},x^{1}_{2},x^{2}_{2},s_{1},s_{2},y)$
$\displaystyle=$
$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}}}(x^{1}_{1},x^{2}_{1},x^{1}_{2},x^{2}_{2})\tau_{{\underline{s}}^{1},{\underline{s}}^{2}|{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}}}(s_{1},s_{2}|x^{1}_{1},x^{2}_{1},x^{1}_{2},x^{2}_{2})W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}(y|x^{1}_{1},x^{2}_{1},s_{1})$
$\displaystyle=$
$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}}}(x^{1}_{1},x^{2}_{1},x^{1}_{2},x^{2}_{2})\tau_{{\underline{s}}^{1},{\underline{s}}^{2}|{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}}}(s_{1},s_{2}|x^{1}_{1},x^{2}_{1},x^{1}_{2},x^{2}_{2})W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}(y|x^{1}_{2},x^{2}_{2},s_{2})$

for all
$(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y)\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}}$;

  2. 2.

for all $1\leq i_{1}\neq i_{2}\leq|{\mathcal{C}}_{1}|$ and $1\leq
j\leq|{\mathcal{C}}_{2}|$, there do not exist
${\underline{s}}^{1},{\underline{s}}^{2}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}^{1}},\tau_{{\underline{s}}^{2}}\in\Lambda$ and
${\underline{y}}\in{\mathcal{Y}}^{n}$ such that

$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j},{\underline{s}}^{1},{\underline{s}}^{2},{\underline{y}}}(x^{1}_{1},x^{1}_{2},x^{2},s_{1},s_{2},y)$
$\displaystyle=$
$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}}(x^{1}_{1},x^{1}_{2},x^{2})\tau_{{\underline{s}}^{1},{\underline{s}}^{2}|{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}}(s_{1},s_{2}|x^{1}_{1},x^{1}_{2},x^{2})W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}(y|x^{1}_{1},x^{2},s_{1})$
$\displaystyle=$
$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}}(x^{1}_{1},x^{1}_{2},x^{2})\tau_{{\underline{s}}^{1},{\underline{s}}^{2}|{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}}(s_{1},s_{2}|x^{1}_{1},x^{1}_{2},x^{2})W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}(y|x^{1}_{2},x^{2},s_{2})$

for all
$(x^{1}_{1},x^{1}_{2},x^{2},s_{1},s_{2},y)\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}}$;

  3. 3.

for all $1\leq i\leq|{\mathcal{C}}_{1}|$ and $1\leq j_{1}\neq
j_{2}\leq|{\mathcal{C}}_{2}|$, there do not exist
${\underline{s}}^{1},{\underline{s}}^{2}\in{\mathcal{S}}^{n}$ with
$\tau_{{\underline{s}}^{1}},\tau_{{\underline{s}}^{2}}\in\Lambda$ and
${\underline{y}}\in{\mathcal{Y}}^{n}$ such that

$\displaystyle\tau_{{\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}},{\underline{s}}^{1},{\underline{s}}^{2},{\underline{y}}}(x^{1},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y)$
$\displaystyle=$
$\displaystyle\tau_{{\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}(x^{1},x^{2}_{1},x^{2}_{2})\tau_{{\underline{s}}^{1},{\underline{s}}^{2}|{\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}(s_{1},s_{2}|x^{1},x^{2}_{1},x^{2}_{2})W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}(y|x^{1},x^{2}_{1},s_{1})$
$\displaystyle=$
$\displaystyle\tau_{{\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}(x^{1},x^{2}_{1},x^{2}_{2})\tau_{{\underline{s}}^{1},{\underline{s}}^{2}|{\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}(s_{1},s_{2}|x^{1},x^{2}_{1},x^{2}_{2})W_{{\mathbf{y}}|{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{s}}}(y|x^{1},x^{2}_{2},s_{2})$

for all
$(x^{1},x^{2}_{1},x^{2}_{2},s_{1},s_{2},y)\in{\mathcal{X}}_{1}\times{\mathcal{X}}_{2}^{2}\times{\mathcal{S}}^{2}\times{\mathcal{Y}}$.

We now get that
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\in{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
attains zero error for $\mathsf{MAC}_{2}$ if and only if the above conditions
hold. Since these conditions should be satisfied for every $n$, by 7, we pass
from types to distributions. According to Definition 11, we finally get that
an infinite sequence of codes
$\left\\{\left({\mathcal{C}}_{1}^{(n)},{\mathcal{C}}_{2}^{(n)}\right)\right\\}_{n\geq
1}$ attains zero error for $\mathsf{MAC}_{2}$ if and only if for every $n$,

  1. 1.

for all $1\leq i_{1}\neq i_{2}\leq|{\mathcal{C}}_{1}^{(n)}|$ and $1\leq
j_{1}\neq j_{2}\leq|{\mathcal{C}}_{2}^{(n)}|$,
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$;

  2. 2.

for all $1\leq i_{1}\neq i_{2}\leq|{\mathcal{C}}_{1}^{(n)}|$ and $1\leq
j\leq|{\mathcal{C}}_{2}^{(n)}|$,
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$;

  3. 3.

for all $1\leq i\leq|{\mathcal{C}}_{1}^{(n)}|$ and $1\leq j_{1}\neq
j_{2}\leq|{\mathcal{C}}_{2}^{(n)}|$,
$\tau_{{\underline{x}}^{1}_{i},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\notin{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$.

This finishes the proof. ∎

######  Remark 5.

12 and 14 actually imply that operational confusability and distributional
confusability are equivalent, both of which are characterizations of zero
error.

######  Remark 6.

Using operational confusability, one can instead define the confusability sets
in terms of types rather than distributions.

$\displaystyle{\mathcal{K}}_{1,2}^{(n)}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{\tau_{{\underline{x}}^{1}_{1},{\underline{x}}^{1}_{2},{\underline{x}}^{2}_{1},{\underline{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right):\begin{array}[]{c}({\underline{x}}^{1}_{1},{\underline{x}}^{1}_{2},{\underline{x}}^{2}_{1},{\underline{x}}^{2}_{2})\in({\mathcal{X}}_{1}^{n})^{2}\times({\mathcal{X}}_{2}^{n})^{2}\\\
({\underline{x}}^{1}_{1},{\underline{x}}^{2}_{1})\text{ and
}({\underline{x}}^{1}_{2},{\underline{x}}^{2}_{2})\text{ satisfy
\lx@cref{creftypecap~refnum}{cond:nonzero-joint} in the proof of
\lx@cref{creftypecap~refnum}{claim:operational-nonconf}}\end{array}\right\\},$
(34) $\displaystyle{\mathcal{K}}_{1}^{(n)}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{\tau_{{\underline{x}}^{1}_{1},{\underline{x}}^{1}_{2},{\underline{x}}^{2}}\in{\mathcal{J}}_{1}\left(P_{1},P_{2}\right):\begin{array}[]{c}({\underline{x}}^{1}_{1},{\underline{x}}^{1}_{2},{\underline{x}}^{2})\in({\mathcal{X}}_{1}^{n})^{2}\times{\mathcal{X}}_{2}^{n}\\\
({\underline{x}}^{1}_{1},{\underline{x}}^{2})\text{ and
}({\underline{x}}^{1}_{2},{\underline{x}}^{2})\text{ satisfy
\lx@cref{creftypecap~refnum}{cond:nonzero-marg1} in the proof of
\lx@cref{creftypecap~refnum}{claim:operational-nonconf}}\end{array}\right\\}$
(37) $\displaystyle{\mathcal{K}}_{2}^{(n)}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{\tau_{{\underline{x}}^{1},{\underline{x}}^{2}_{1},{\underline{x}}^{2}_{2}}\in{\mathcal{J}}_{2}\left(P_{1},P_{2}\right):\begin{array}[]{c}({\underline{x}}^{1},{\underline{x}}^{2}_{1},{\underline{x}}^{2}_{2})\in{\mathcal{X}}_{1}^{n}\times({\mathcal{X}}_{2}^{n})^{2}\\\
({\underline{x}}^{1},{\underline{x}}^{2}_{1})\text{ and
}({\underline{x}}^{1},{\underline{x}}^{2}_{2})\text{ satisfy
\lx@cref{creftypecap~refnum}{cond:nonzero-marg2} in the proof of
\lx@cref{creftypecap~refnum}{claim:operational-nonconf}}\end{array}\right\\}.$
(40)

By 7 and Remark 5, the above definition is (almost) the same as Definition 11.
Indeed,

$\displaystyle{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)=$
$\displaystyle\operatorname{cl}\left(\bigcup_{n=1}^{\infty}{\mathcal{K}}_{1,2}^{(n)}(P_{1},P_{2})\right),$
$\displaystyle{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=$
$\displaystyle\operatorname{cl}\left(\bigcup_{n=1}^{\infty}{\mathcal{K}}_{1}^{(n)}(P_{1},P_{2})\right),$
$\displaystyle{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)=$
$\displaystyle\operatorname{cl}\left(\bigcup_{n=1}^{\infty}{\mathcal{K}}_{2}^{(n)}(P_{1},P_{2})\right),$

where $\operatorname{cl}(\cdot)$ denotes the closure of a set. We stick with
the distribution version of the definition rather than type version.

######  Proposition 15.

Fix any $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$. The confusability sets
enjoy the following properties.

  1. 1.

_Nontriviality._ Any distributions
$P_{{\mathbf{x}}^{1},{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$,
$P_{{\mathbf{x}}^{1},{\mathbf{x}}^{1},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)$
and
$P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)$
are in
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
and ${\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, respectively.

  2. 2.

_Transpositional invariance._ If
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is in ${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$, then
$P_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}$
is also in ${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$; if
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}$ is in
${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$, then
$P_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}}$ is also in
${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$; if
$P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$ is in
${\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, then
$P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}$ is also in
${\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$.

  3. 3.

_Convexity._ All of
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$
are convex.

###### Proof.

By Remark 5, it is convenient to prove the properties via operational
confusability.

To prove the first property, one simply observes that a pair of codewords
$({\underline{x}}^{1},{\underline{x}}^{2})$ is apparently confusable with
itself. In Item 1 (of 12), one takes
${\underline{s}}=\widetilde{\underline{s}}$.

To prove the second property, one notes that if
$({\underline{x}}^{1},{\underline{x}}^{2})$ is confusable with
$(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2})$ (resp.
$(\widetilde{\underline{x}}^{1},{\underline{x}}^{2})$ or
$({\underline{x}}^{1},\widetilde{\underline{x}}^{2})$), then
$(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2})$ (resp.
$(\widetilde{\underline{x}}^{1},{\underline{x}}^{2})$ or
$({\underline{x}}^{1},\widetilde{\underline{x}}^{2})$) is also confusable with
$({\underline{x}}^{1},{\underline{x}}^{2})$. In the conditions of 12, one
interchanges the corresponding ${\underline{s}}$ and
$\widetilde{\underline{s}}$.

To prove the third property, we note that for any $\alpha\in[0,1]$, if
$(\vec{x}^{1}_{1},\vec{x}^{2}_{1})\in{\mathcal{X}}_{1}^{\alpha
n}\times{\mathcal{X}}_{2}^{\alpha n}$ and
$(\vec{x}^{1}_{2},\vec{x}^{2}_{2})\in{\mathcal{X}}_{1}^{\alpha
n}\times{\mathcal{X}}_{2}^{\alpha n}$ are confusable (via
$\vec{s}_{1}\in{\mathcal{S}}^{\alpha n}$ and
$\vec{s}_{2}\in{\mathcal{S}}^{\alpha n}$),
$(\vec{x}^{1}_{3},\vec{x}^{2}_{3})\in{\mathcal{X}}_{1}^{(1-\alpha)n}\times{\mathcal{X}}_{2}^{(1-\alpha)n}$
and
$(\vec{x}^{1}_{4},\vec{x}^{2}_{4})\in{\mathcal{X}}_{1}^{(1-\alpha)n}\times{\mathcal{X}}_{2}^{(1-\alpha)n}$
are also confusable (via $\vec{s}_{3}\in{\mathcal{S}}^{(1-\alpha)n}$ and
$\vec{s}_{4}\in{\mathcal{S}}^{(1-\alpha)n}$), then
$((\vec{x}^{1}_{1},\vec{x}^{1}_{3}),(\vec{x}^{2}_{1},\vec{x}^{2}_{3}))\in{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
and
$((\vec{x}^{1}_{2},\vec{x}^{1}_{4}),(\vec{x}^{2}_{2},\vec{x}^{2}_{4}))\in{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
are confusable (via $(\vec{s}_{1},\vec{s}_{3})\in{\mathcal{S}}^{n}$ and
$(\vec{s}_{2},\vec{s}_{4})\in{\mathcal{S}}^{n}$). Here for two vectors
$\vec{v}_{1}\in{\mathcal{V}}^{n_{1}}$ and
$\vec{v}_{2}\in{\mathcal{V}}^{n_{2}}$, we use the notation
$(\vec{v}_{1},\vec{v}_{2})\in{\mathcal{V}}^{n_{1}+n_{2}}$ to denote the
concatenation of $\vec{v}_{1}$ and $\vec{v}_{2}$. Therefore, by 4, if
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
and
$P_{\widetilde{{\mathbf{x}}^{1}_{1}},\widetilde{{\mathbf{x}}^{1}_{2}},\widetilde{{\mathbf{x}}^{2}_{1}},\widetilde{{\mathbf{x}}^{2}_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
then $\alpha
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}+(1-\alpha)P_{\widetilde{{\mathbf{x}}^{1}_{1}},\widetilde{{\mathbf{x}}^{1}_{2}},\widetilde{{\mathbf{x}}^{2}_{1}},\widetilde{{\mathbf{x}}^{2}_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
for any $\alpha\in[0,1]$. ∎

######  Remark 7.

If we define the relation $\sim_{\mathrm{conf}}$ on the set of feasible input
sequences as
$({\underline{x}}^{1},{\underline{x}}^{2})\sim_{\mathrm{conf}}(\widetilde{\underline{x}}^{1},\widetilde{\underline{x}}^{2})$
(resp.
$({\underline{x}}^{1},{\underline{x}}^{2})\sim_{\mathrm{conf}}(\widetilde{\underline{x}}^{1},{\underline{x}}^{2})$
or
$({\underline{x}}^{1},{\underline{x}}^{2})\sim_{\mathrm{conf}}({\underline{x}}^{1},\widetilde{\underline{x}}^{2})$)
iff
$\tau_{{\underline{x}}^{1},\widetilde{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
(resp.
$\tau_{{\underline{x}}^{1},\widetilde{\underline{x}}^{1},{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
or
$\tau_{{\underline{x}}^{1},{\underline{x}}^{2},\widetilde{\underline{x}}^{2}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$),
then Proposition 15 implies that $\sim_{\mathrm{conf}}$ is reflective and
symmetric. However, $\sim_{\mathrm{conf}}$ is not necessarily transitive.
Therefore, it is not in general an equivalence relation.

######  Claim 16.

Channels with the same confusability sets have the same capacity region.

###### Proof.

Let $\mathsf{MAC}_{2}$ and $\mathsf{MAC}_{2}^{\prime}$ be two adversarial MACs
with the same input constraints $\Gamma_{1},\Gamma_{2}$ and the same
confusability sets
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$
for all $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$. Note that
$\mathsf{MAC}_{2}$ and $\mathsf{MAC}_{2}^{\prime}$ may have different
state/output alphabets and channel laws. By 14, any code
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ that attains zero error for
$\mathsf{MAC}_{2}$ also attains zero error for $\mathsf{MAC}_{2}^{\prime}$.
Therefore, any achievable rate pair $(R_{1},R_{2})$ for $\mathsf{MAC}_{2}$ is
also achievable for $\mathsf{MAC}_{2}^{\prime}$. ∎

##  X The sets of good distributions and their properties

The geometry of various sets of distributions/tensors is depicted in Figure 2.

Figure 2: The geometry of various sets of distributions/tensors. We only draw
sets of joint distributions/tensors. The geometry of the corresponding
marginal distributions/tensors is similar. The ambient space is
$\Delta_{1,2}(P_{1},P_{2})$ which is defined in Definition 12. The set
${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$ of self-couplings is defined in
Definition 10. The set $\mathsf{Sym}_{1,2}(P_{1},P_{2})$ of symmetric tensors
is defined in Definition 13. Inside $\mathsf{Sym}_{1,2}(P_{1},P_{2})$, there
is a pair of dual cones, viz.: ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$
(Definition 15) and
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$ (Definition
16). The blue region denotes the set
${\mathcal{S}}_{1,2}\left(P_{1},P_{2}\right)$ of symmetric distributions
(Definition 14) which is the intersection of $\mathsf{Sym}_{1,2}(P_{1},P_{2})$
and ${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$.

######  Definition 12 (Generalized self-couplings).

$\displaystyle\Delta_{1,2}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathbb{R}}^{\left|{\mathcal{X}}_{1}\right|^{2}\times\left|{\mathcal{X}}_{2}\right|^{2}}:\left\|T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{1}=1,\begin{array}[]{l}\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1}}=\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{2}}=P_{1},\\\
\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{1}}=\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{2}}=P_{2}\end{array}\right\\},$
(43) $\displaystyle\Delta_{1}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathbb{R}}^{\left|{\mathcal{X}}_{1}\right|^{2}\times\left|{\mathcal{X}}_{2}\right|}:\left\|T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right\|_{2}=1,\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right]_{{\mathbf{x}}^{1}_{1}}=\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right]_{{\mathbf{x}}^{1}_{2}}=P_{1},\left[T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right]_{{\mathbf{x}}^{2}}=P_{2}\right\\}$
$\displaystyle\Delta_{2}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathbb{R}}^{\left|{\mathcal{X}}_{1}\right|\times\left|{\mathcal{X}}_{2}\right|^{2}}:\left\|T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{2}=1,\left[T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}}=P_{1},\left[T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{1}}=\left[T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{2}_{2}}=P_{2}\right\\}.$

######  Remark 8.

For a general tensor (not necessarily a distribution)
$T_{{\mathbf{a}},{\mathbf{b}}}\in{\mathbb{R}}^{\left|{\mathcal{A}}\right|\times\left|{\mathcal{B}}\right|}$,
the marginalization of $T_{{\mathbf{a}},{\mathbf{b}}}$ onto the first variable
${\mathbf{a}}$ is defined as
$\left[T_{{\mathbf{a}},{\mathbf{b}}}\right]_{{\mathbf{a}}}(a)\coloneqq\sum_{b\in{\mathcal{B}}}\left|T_{{\mathbf{a}},{\mathbf{b}}}(a,b)\right|$
for any $a\in{\mathcal{A}}$.

######  Remark 9.

For the convenience of discussion, the above sets should be thought of as
generalizations of distributions (Definition 10).

######  Definition 13 (Symmetric tensors).

$\displaystyle\mathsf{Sym}_{1,2}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\Delta_{1,2}(P_{1},P_{2}):T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=T_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}=T_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}\right\\},$
$\displaystyle\mathsf{Sym}_{1}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\Delta_{1}(P_{1},P_{2}):T_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}=T_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}}\right\\},$
$\displaystyle\mathsf{Sym}_{2}(P_{1},P_{2})\coloneqq$
$\displaystyle\left\\{T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\Delta_{2}(P_{1},P_{2}):T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=T_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}\right\\}.$

######  Definition 14 (Symmetric distributions).

$\displaystyle{\mathcal{S}}_{1,2}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\cap\mathsf{Sym}_{1,2}(P_{1},P_{2}),$
$\displaystyle{\mathcal{S}}_{1}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\cap\mathsf{Sym}_{1}(P_{1},P_{2}),$
$\displaystyle{\mathcal{S}}_{2}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)\cap\mathsf{Sym}_{2}(P_{1},P_{2}).$

######  Definition 15 (Good distributions).

Let $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$. The set of _jointly good
distributions_ ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$, the set of
_first marginally good distributions_
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and the set of _second
marginally good distributions_ ${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$
w.r.t. $P_{1}$ and $P_{2}$ are defined as follows:

$\displaystyle{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\colon\begin{array}[]{l}\exists
k\in{\mathbb{Z}}_{\geq
1},\left\\{\lambda_{i}\right\\}_{i=1}^{k}\subseteq[0,1],\left\\{P_{1,i}\right\\}_{i=1}^{k}\subseteq\Delta({\mathcal{X}}_{1}),\left\\{P_{2,i}\right\\}_{i=1}^{k}\subseteq\Delta({\mathcal{X}}_{2}),\mathrm{\
s.t.}\\\
\displaystyle\sum_{i=1}^{k}\lambda_{i}=1,P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes
2}\otimes P_{2,i}^{\otimes 2}\end{array}\right\\},$ (46)
$\displaystyle{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\colon\begin{array}[]{l}\exists
k\in{\mathbb{Z}}_{\geq
1},\left\\{\lambda_{i}\right\\}_{i=1}^{k}\subseteq[0,1],\left\\{P_{1,i}\right\\}_{i=1}^{k}\subseteq\Delta({\mathcal{X}}_{1}),\left\\{P_{2,i}\right\\}_{i=1}^{k}\subseteq\Delta({\mathcal{X}}_{2}),\mathrm{\
s.t.}\\\
\displaystyle\sum_{i=1}^{k}\lambda_{i}=1,P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}=\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes
2}\otimes P_{2,i}\end{array}\right\\},$ (49)
$\displaystyle{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)\colon\begin{array}[]{l}\exists
k\in{\mathbb{Z}}_{\geq
1},\left\\{\lambda_{i}\right\\}_{i=1}^{k}\subseteq[0,1],\left\\{P_{1,i}\right\\}_{i=1}^{k}\subseteq\Delta({\mathcal{X}}_{1}),\left\\{P_{2,i}\right\\}_{i=1}^{k}\subseteq\Delta({\mathcal{X}}_{2}),\mathrm{\
s.t.}\\\
\displaystyle\sum_{i=1}^{k}\lambda_{i}=1,P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=\sum_{i=1}^{k}\lambda_{i}P_{1,i}\otimes
P_{2,i}^{\otimes 2}\end{array}\right\\}.$ (52)

In addition, we define the set of _simultaneously good_ distributions
${\mathcal{G}}\left(P_{1},P_{2}\right)$ w.r.t. $P_{1}$ and $P_{2}$ as

$\displaystyle{\mathcal{G}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{\begin{array}[]{rl}P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right):&\\\
\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}=&\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\\\
\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=&\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\end{array}\right\\}.$
(56)

######  Proposition 17 (Properties of good distributions).

The sets
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$
and ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ enjoy the following
properties.

  1. 1.

Good distributions are symmetric.

$\displaystyle{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\subset{\mathcal{S}}_{1,2}\left(P_{1},P_{2}\right),\quad{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\subset{\mathcal{S}}_{1}\left(P_{1},P_{2}\right),\quad{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\subset{\mathcal{S}}_{2}\left(P_{1},P_{2}\right).$

  2. 2.

For any
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$,

$\displaystyle\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}=$
$\displaystyle\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2}},\quad\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}.$

  3. 3.

The sets ${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$ are projections of the set
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$.

$\displaystyle{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)=$
$\displaystyle\left\\{\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}:P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right\\},$
$\displaystyle{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)=$
$\displaystyle\left\\{\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}:P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right\\}.$

######  Remark 10.

Though the good sets
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$
are _consistent under projections_ (the third property of Proposition 17), the
confusability sets
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$
are not. Operationally, this is because
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{j_{1}})$ (or
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{2}})$) and
$({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}})$ (or
$({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}})$) are not
necessarily confusable even if
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}})$ and
$({\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}})$ are (for
$i_{1}\neq i_{2}$ and $j_{1}\neq j_{2}$). Therefore, even the second property
of Proposition 17 is guaranteed to hold for
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$,
let alone the third one.

######  Definition 16 (Co-good tensors).

$\displaystyle\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathsf{Sym}_{1,2}(P_{1},P_{2})\colon\forall
P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1}),\forall
P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2}),\left\langle
P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes P_{{\mathbf{x}}^{2}}^{\otimes
2},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\geq
0\right\\},$
$\displaystyle\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\mathsf{Sym}_{1}(P_{1},P_{2})\colon\forall
P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1}),\forall
P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2}),\left\langle
P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes
P_{{\mathbf{x}}^{2}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right\rangle\geq
0\right\\},$
$\displaystyle\mathrm{co}\text{-}{\mathcal{G}}_{2}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathsf{Sym}_{2}(P_{1},P_{2})\colon\forall
P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1}),\forall
P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2}),\left\langle
P_{{\mathbf{x}}^{1}}\otimes P_{{\mathbf{x}}^{2}}^{\otimes
2},P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\geq
0\right\\}.$

######  Remark 11.

Note that co-good tensors are not necessarily distributions. They may have
negative entries.

######  Remark 12.

It follows from definition that the sets of good distributions are subsets of
the corresponding co-good distributions, i.e.,

$\displaystyle{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\subset\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right),\quad{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\subset\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right),\quad{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\subset\mathrm{co}\text{-}{\mathcal{G}}_{2}\left(P_{1},P_{2}\right).$

######  Definition 17 (Dual cone).

The _dual cone_ ${\mathcal{B}}^{*}$ of a cone ${\mathcal{B}}$ in a Hilbert
space ${\mathcal{H}}$ is defined as
${\mathcal{B}}^{*}\coloneqq\left\\{b^{\prime}\in{\mathcal{H}}:\forall
b\in{\mathcal{B}},\;\left\langle b,b^{\prime}\right\rangle\geq 0\right\\}$.

######  Theorem 18 (Duality).

The sets ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$,
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$ are all closed convex pointed
cones with non-empty interior. Furthermore, the following duality relations
hold. In $\mathsf{Sym}_{1,2}(P_{1},P_{2})$,
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ and
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$ are dual
cones of each other. In $\mathsf{Sym}_{1}(P_{1},P_{2})$,
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and
$\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)$ are dual cones
of each other. In $\mathsf{Sym}_{2}(P_{1},P_{2})$,
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$ and
$\mathrm{co}\text{-}{\mathcal{G}}_{2}\left(P_{1},P_{2}\right)$ are dual cones
of each other.

###### Proof.

We first prove the duality relations. Intuitively, the duality follows since
the extremal rays of ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ (or
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$,
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$ respectively) are distributions
of the form $P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes
P_{{\mathbf{x}}^{2}}^{\otimes 2}$ (or $P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes
P_{{\mathbf{x}}^{2}}$, $P_{{\mathbf{x}}^{1}}\otimes
P_{{\mathbf{x}}^{2}}^{\otimes 2}$ respectively). Indeed, it follows from
Definition 15 that

$\displaystyle{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)=$
$\displaystyle\operatorname{conv}\left\\{P_{{\mathbf{x}}^{1}}^{\otimes
2}\otimes P_{{\mathbf{x}}^{2}}^{\otimes
2}:P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1}),P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2})\right\\}\cap{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right),$
$\displaystyle{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)=$
$\displaystyle\operatorname{conv}\left\\{P_{{\mathbf{x}}^{1}}^{\otimes
2}\otimes
P_{{\mathbf{x}}^{2}}:P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1}),P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2})\right\\}\cap{\mathcal{J}}_{1}\left(P_{1},P_{2}\right),$
$\displaystyle{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)=$
$\displaystyle\operatorname{conv}\left\\{P_{{\mathbf{x}}^{1}}\otimes
P_{{\mathbf{x}}^{2}}^{\otimes
2}:P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1}),P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2})\right\\}\cap{\mathcal{J}}_{2}\left(P_{1},P_{2}\right),$

where $\operatorname{conv}\left\\{\cdot\right\\}$ denotes the convex hull of a
set. Therefore, one can replace
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$
(or $P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}$,
$P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$ respectively)
in the definition of ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}$ (or
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}$,
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)^{*}$ respectively) below with
$P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes P_{{\mathbf{x}}^{2}}^{\otimes 2}$ (or
$P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes P_{{\mathbf{x}}^{2}}$,
$P_{{\mathbf{x}}^{1}}\otimes P_{{\mathbf{x}}^{2}}^{\otimes 2}$ respectively).

$\displaystyle{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}=$
$\displaystyle\left\\{Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathsf{Sym}_{1,2}(P_{1},P_{2}):\forall
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right),\;\left\langle
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\geq
0\right\\},$ $\displaystyle{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}=$
$\displaystyle\left\\{Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\mathsf{Sym}_{1}(P_{1},P_{2}):\forall
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right),\;\left\langle
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right\rangle\geq
0\right\\},$ $\displaystyle{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)^{*}=$
$\displaystyle\left\\{Q_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathsf{Sym}_{2}(P_{1},P_{2}):\forall
P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right),\;\left\langle
P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\geq
0\right\\}.$

After the replacement, we get exactly
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ (or
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$,
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$, respectively).

To formalize this intuition, we prove two-sided set inclusions for
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$ and
$\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)$. The proof for
$\mathrm{co}\text{-}{\mathcal{G}}_{2}\left(P_{1},P_{2}\right)$ is the same as
that for $\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)$ up to
change of notation.

We first prove
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)={\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}$.

  1. $\subseteq$.

Let
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$.
Let
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes
2}\otimes P_{2,i}^{\otimes
2}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$. By Definition 16, we have
$\left\langle
Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},P_{1,i}^{\otimes
2}\otimes P_{2,i}^{\otimes 2}\right\rangle\geq 0$ for all $i\in[k]$.
Therefore, $\left\langle
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\geq
0$, which means
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}$.
This proves
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)\subseteq{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}$.

  2. $\supseteq$.

Let
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}$.
By Definition 17, for any $P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1})$
and $P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2})$, we have $\left\langle
Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},P_{{\mathbf{x}}^{1}}^{\otimes
2}\otimes P_{{\mathbf{x}}^{2}}^{\otimes 2}\right\rangle\geq 0$ since
$P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes P_{{\mathbf{x}}^{2}}^{\otimes
2}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$. Therefore,
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$
and
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)^{*}\subseteq\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$.

We then prove
$\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)={\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}$
in the same way.

  1. $\subseteq$.

Let
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$.
Let
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}=\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes
2}\otimes P_{2,i}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$. By
Definition 16, for each $i\in[k]$, we have $\left\langle
Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},P_{1,i}^{\otimes
2}\otimes P_{2,i}\right\rangle\geq 0$. Therefore, $\left\langle
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right\rangle\geq
0$, which means
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}$.
This proves
$\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)\subseteq{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}$.

  2. $\supseteq$.

Let
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}$.
By Definition 17, for any $P_{{\mathbf{x}}^{1}}\in\Delta({\mathcal{X}}_{1})$
and $P_{{\mathbf{x}}^{2}}\in\Delta({\mathcal{X}}_{2})$, we have $\left\langle
Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},P_{{\mathbf{x}}^{1}}^{\otimes
2}\otimes P_{{\mathbf{x}}^{2}}\right\rangle\geq 0$ since
$P_{{\mathbf{x}}^{1}}^{\otimes 2}\otimes
P_{{\mathbf{x}}^{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$.
Therefore,
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)$
and
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)^{*}\subseteq\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$.

This finishes the proof for duality.

The claimed convexity and conic property of
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$,
$\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)$ and
$\mathrm{co}\text{-}{\mathcal{G}}_{2}\left(P_{1},P_{2}\right)$ follow directly
from Definition 16. The closedness of
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$,
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$ follows from the fact that the
dual cone of any convex cone is closed. One can easily find distributions that
are in the interior of the cones under consideration. The pointedness of
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$,
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$ follows from nonnegativity of
the entries of their elements. Finally, the pointedness of
$\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$,
$\mathrm{co}\text{-}{\mathcal{G}}_{1}\left(P_{1},P_{2}\right)$ and
$\mathrm{co}\text{-}{\mathcal{G}}_{2}\left(P_{1},P_{2}\right)$ follows from
the fact that the dual cone of any convex cone with nonempty interior is
pointed. ∎

##  XI A characterization of the shape of capacity region

######  Theorem 19.

Fix a pair of input distributions
$(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

  1. 1.

If ${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$, then the capacity
region contains rate pairs $(R_{1},R_{2})$ such that $R_{1}>0,R_{2}>0$ or
$R_{1}>0,R_{2}=0$ or $R_{1}=0,R_{2}>0$ or $R_{1}=0,R_{2}=0$.

  2. 2.

If ${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$,
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$
and
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$,
then the capacity region only contains rate pairs $(R_{1},R_{2})$ such that
$R_{1}>0,R_{2}=0$ or $R_{1}=0,R_{2}>0$ or $R_{1}=0,R_{2}=0$.

  3. 3.

If
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$
and
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)=\emptyset$,
then the capacity region only contains rate pairs $(R_{1},R_{2})$ such that
$R_{1}>0,R_{2}=0$ or $R_{1}=0,R_{2}=0$.

  4. 4.

If
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=\emptyset$
and
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$,
then the capacity region only contains rate pairs $(R_{1},R_{2})$ such that
$R_{1}=0,R_{2}>0$ or $R_{1}=0,R_{2}=0$.

  5. 5.

If
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=\emptyset$
and
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)=\emptyset$,
then the capacity region only contains $(0,0)$.

Cases | ${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$ | ${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$ | ${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$ | Capacity region
---|---|---|---|---
Case (1) | $\checkmark$ | $\checkmark$ | $\checkmark$ | $(+,+),(+,0),(0,+),(0,0)$
Case (2) | $\times$ | $\checkmark$ | $\checkmark$ | $(+,0),(0,+),(0,0)$
Case (3) | $\times$ | $\checkmark$ | $\times$ | $(+,0),(0,0)$
Case (4) | $\times$ | $\times$ | $\checkmark$ | $(0,+),(0,0)$
Case (5) | $\times$ | $\times$ | $\times$ | $(0,0)$
TABLE I: A characterization of the _shape_ of the capacity region of any
omniscient adversarial two-user MAC. Note that the condition
${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$ implies both
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$
and
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$.
Indeed, the former condition is strictly stronger. In each case, we highlight
the conditions in colors in such a way that red conditions imply blue
conditions. Note that the table above covers all possible cases.

The proof of the above characterization is comprised of two parts:
achievability (Lemma 23) and converse (Theorem 20).

######  Theorem (Achievability, restatement of Lemma 23).

Fix input distributions $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

  1. 1.

If ${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$, then there exist
achievable rate pairs $(R_{1},R_{2})$ such that $R_{1}>0,R_{2}>0$.

  2. 2.

If
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$,
then there exist achievable rate pairs $(R_{1},0)$ such that $R_{1}>0$.

  3. 3.

If
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$,
then there exist achievable rate pairs $(0,R_{2})$ such that $R_{2}>0$.

Various achievability results are proved in Section XIII. Firstly, in Lemma
22, we prove the existence of positive rates using _product_ distributions.
Next, in Lemma 23, we refine this result using _mixtures_ of product
distributions, i.e., good distributions (Definition 15). Finally, in Lemma 24
we present _inner bounds_ on the capacity region using product distributions.

######  Theorem 20 (Converse).

Fix a pair of input distributions
$(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

  1. 1.

If ${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$, then there does not
exist achievable rate pair $(R_{1},R_{2})$ such that $R_{1}>0,R_{2}>0$.

  2. 2.

If
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=\emptyset$,
then there does not exist achievable rate pair $(R_{1},R_{2})$ such that
$R_{1}>0$.

  3. 3.

If
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)=\emptyset$,
then there does not exist achievable rate pair $(R_{1},R_{2})$ such that
$R_{2}>0$.

###### Proof.

Item 1 is proved in Section XIV. Items 2 and 3 are proved in Section XV. ∎

######  Observation 13.

For an omniscient two-user adversarial MAC, for $i=1,2$, if a rate $R_{i}>0$
is achievable for transmitter $i$, then any rate $0\leq R_{i}^{\prime}\leq
R_{i}$ is also achievable for transmitter $i$.

By 13, if the capacity region contains a rate pair $(R_{1},R_{2})$ where
$R_{1}>0,R_{2}>0$, then the rate pairs $(R_{1},0)$ and $(0,R_{2})$ are also in
the capacity region.

###  XI-A A remark on nonconvexity of capacity region

As suggested by Theorem 19, the capacity region of an adversarial MAC can be
_nonconvex_. E.g., if a MAC satisfies the conditions in Item 2 of Theorem 19,
then the capacity region only consists of two perpendicular line segments and
is therefore nonconvex. However, the capacity region cannot be an arbitrary
nonconvex region. Indeed, 13 implies that if a rate pair $(R_{1},R_{2})$ with
$R_{1}>0,R_{2}>0$ is achievable, then all rate pairs in the (closed) rectangle
with vertices $(0,0),(R_{1},0),(0,R_{2}),(R_{1},R_{2})$ are also achievable.

For AVMACs (i.e., the _oblivious_ adversarial MACs), the nonconvexity of the
capacity region was noted by Gubner–Hughes [GH95] and Pereg–Steinberg [PS19]
via the example of an (oblivious) erasure MAC. As a side note, for AVMACs
equipped with common randomness, the capacity region may or may not be convex,
depending on how the common randomness is instantiated. If each encoder shares
an _independent_ secret key with the decoder, then the corresponding capacity
region, known as the _divided-randomness_ capacity region, is not necessarily
convex [GH95]. On the other hand, if all of two encoders and the decoder share
the _same_ key, then the corresponding capacity region, known as the _random
code_ capacity region, is always convex [PS19]. In our work, we do not equip
any party with shared randomness. See [PS19] for a more detailed discussion on
the nonconvexity of the capacity region of AVMACs.

###  XI-B Comparison of our results with [PS19] on (oblivious) AVMACs

We compare below our results with the parallel results by Pereg and Steinberg
on _oblivious_ AVMACs. For simplicity, we only compare the characterizations
of _positivity_ of capacities. Specifically, an oblivious AVMAC is a general
adversarial MAC with input and state constraints and an oblivious adversary
who does _not_ know the transmitted sequences from any of the encoders. As
many other results in the AVC literature, their characterization involves the
oblivious analog of confusability known as _symmetrizability_. Proper notions
of _first marginal symmetrizability_ , _second marginal symmetrizability_ and
_joint symmetrizability_ (denoted in their notation by _symmetrizability-
${\mathcal{X}}_{1}|{\mathcal{X}}_{2}$_, _symmetrizability-
${\mathcal{X}}_{2}|{\mathcal{X}}_{1}$_ and _symmetrizability-
${\mathcal{X}}_{1}\times{\mathcal{X}}_{2}$_ respectively) were introduced and
were shown to characterize the capacity positivity. See Table II below.

Cases | non-joint symmetrizability | non-first marginal symmetrizability | non-second marginal symmetrizability | Capacity region
---|---|---|---|---
Case (1) | $\checkmark$ | $\checkmark$ | $\checkmark$ | $(+,+),(+,0),(0,+),(0,0)$
Case (2) | $\checkmark$ | $\checkmark$ | $\times$ | $(+,0),(0,0)$
Case (3) | $\checkmark$ | $\times$ | $\checkmark$ | $(0,+),(0,0)$
Case (4) | $\times$ | $?$ | $?$ | $(0,0)$
Case (5) | $\checkmark$ | $\times$ | $\times$ | $(0,0)$
TABLE II: Results in [PS19] on capacity positivity of oblivious AVMACs. In the
table, “$\checkmark$” (resp. “$\times$”) means the corresponding non-
symmetrizability condition is satisfied (resp. unsatisfied). Question marks
“$?$” mean either satisfied or unsatisfied, regardlessly. As noted, non-joint
symmetrizability is a necessary condition for any positive achievable rate.

Intuitively, one should think of symmetrizability as the oblivious analog of
confusability defined in Section IX. However, in the AVMAC setting, due to the
“independence” between the jammer and the encoders, the formal definition of
symmetrizability does not appear to be a straightforward adjustment of
Definition 11. As a result, the characterization of positivity in [PS19] does
not exactly parallel ours. An informal analogy between the symmetrizability of
Pereg and Steinberg’s and the confusability of ours is as follows. Non-first
(resp. -second) marginal symmetrizability corresponds to
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$
(resp.
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$).
Non-joint symmetrizability corresponds to
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\neq\emptyset$.
However, one gets _wrong_ results (for Items 1 and 2 in particular) if she/he
verbatim translates the oblivious results to the omniscient setting using the
aforementioned informal correspondence.

In the AVMAC setting, non-joint symmetrizability is a necessary condition for
the existence of $R_{1}>0$ or $R_{2}>0$. As a consequence, there does not
exist situation where $R_{1}>0$ or $R_{2}>0$ can be achieved separately yet
not simultaneously (Item 2 in Theorem 19).

In the omniscient setting, the condition that determines the possibility of
$(R_{1},R_{2})$ with $R_{1}>0,R_{2}>0$ is in terms of
${\mathcal{G}}\left(P_{1},P_{2}\right)$ rather than
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$.
Communication at positive rates for both encoders simultaneously may not be
possible even if
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\neq\emptyset$.
It is possible only if there is a _single_ good distribution (as per
Definition 15) that is simultaneously non-jointly symmetrizable and non-
marginally symmetrizable (for both transmitters).

##  XII Overview of proof techniques

In this section we overview the proof techniques for establishing Theorem 19.
Since there are cases where both/exactly one/none of the transmitters can
achieve positive rates, we have to divide the analysis into several cases.
Nevertheless, the proofs for different cases share roughly the same structure.
In what follows, we briefly introduce the ideas behind the achievability part
and the converse part separately.

###  XII-A Proof techniques for achievability

To show positive achievable rates under the conditions of Lemma 23, we use the
standard method of random coding with expurgation. The conditions in Lemma 23
can be intuitively interpreted as the existence of _good_ distributions
(according to Definition 15) that are not _bad_ (according to Definition 11).

If one is able to find a _product_ distribution (which is always good by
definition) that is outside the confusability sets, then one can simply sample
positive rate codes whose entries are i.i.d. according to the distribution. By
concentration of measure, the joint type of any codeword tuple is tightly
concentrated around the product distribution. In particular, any joint type is
outside the confusability sets with high probability. Now by large deviation
principle, if the code rates are sufficiently small, a union bound over all
codeword tuples allows us to conclude that no joint type is confusable and
hence the whole code pair attains zero error with high probability. This gives
Lemma 22.

Lemma 22 can be strengthened in the following two ways.

Firstly, even if product distributions are confusable, if one can find
_mixtures_ of product distributions that are outside the confusability sets,
then positive rates are still achievable. Here the additional idea is _time-
sharing_. Recall that a good distribution is a convex combination of product
distributions.121212Note that importantly, the components of such a convex
combination do not have to satisfy the input constraints. This is why it is
possible to find mixtures of product distributions that are non-confusable