## V.2.b Coding Result

In this section, we extend the coordination coding result of (Le Treust, 2017, Theorem 4) to the case where state and channel noise are Gaussian random variables, other random variables are real-valued, and we consider the power and estimation cost functions of the vector-valued Witsenhausen counterexample. We provide a characterization of the achievable pairs of costs (P, S).

**Theorem 26** The pair of Witsenhausen costs (P, S) is achievable if and only if there exists a joint probability distribution that decomposes according to

$$P_{X_0 Q_{U_1 W_1 W_2 | X_0} P_{X_1 Y_1 | X_0 U_1} Q_{U_2 | W_2 Y_1}}, \qquad (V.50)$$

such that

$$I(W_1; Y_1 | W_2) - I(W_1, W_2; X_0) \geq 0, \qquad (V.51)$$

$$P = \mathbb{E}_{Q}[U_1^2], \quad S = \mathbb{E}_{Q}[(X_1 - U_2)^2], \qquad (V.52)$$

where $W_1$ and $W_2$ are discrete or continuous auxiliary random variables.

The achievability proof of Theorem 26 relies on a block-Markov coding scheme and an adequate notion of weak typicality, inspired from the techniques of Vu et al. (2019). The achievability and converse proofs are stated in (Le Treust and Oechtering, 2022, App. A, [W9]). Entropy and mutual information are defined using the Radon-Nikodym derivative, which is briefly recapitulated in the preliminaries.

**Remark 18** The probability distributions in (V.50) satisfy the Markov chains

$$\left\{ \begin{array}{l} (X_1, Y_1) \leftarrow (X_0, U_1) \leftarrow (W_1, W_2), \\ U_2 \leftarrow (Y_1, W_2) \leftarrow (X_0, X_1, U_1, W_1). \end{array} \right. \qquad (V.53)$$

The causality condition prevents the controller $C_2$ to recover $W_1$ which induces the second Markov chain of (V.53). The first and second Markov chains are induced by the network topology.

**Remark 19** The information constraint (V.51) reformulates as

$$I(W_1; Y_1, W_2) - I(W_1; X_0, W_2) \geq I(X_0; W_2). \qquad (V.54)$$

The terms $I(X_0; W_2)$ corresponds to the quantization of the state $X_0$ via the auxiliary random variable $W_2$. The expression $I(W_1; Y_1, W_2) - I(W_1; X_0, W_2)$ stands for the capacity of a two-sided state dependent channel where the encoder observes $(X_0, W_2)$ and the decoder observes $W_2$. Intuitively, $W_1$ is used to tune the state-dependent channel so as to increase its capacity, as in Gel'fand and Pinsker (1980), in order to refine the quantization of the state $X_0$, via the auxiliary random variable $W_2$.

In order to investigate the region of achievable pairs of Witsenhausen costs (P, S), we focus on its boundary. We fix the power cost to some parameter $P \geq 0$, and we investigate the optimal estimation cost at the decoder.

**Definition 33** Given a power cost parameter $P \geq 0$, the optimal estimation cost MMSE(P) is the solution of the optimization problem

$$\text{MMSE}(P) = \inf_{Q \in \mathbb{Q}(P)} \mathbb{E}_{Q}[(X_1 - U_2)^2], \qquad (V.55)$$

$$\mathbb{Q}(P) = \left\{ (Q_{U_1 W_1 W_2 | X_0}, Q_{U_2 | W_2 Y_1}) \text{ s.t. } P = E_{Q}[U_1^2], \right. \\ \left. I(W_1; Y_1 | W_2) - I(W_1, W_2; X_0) \geq 0 \right\}. \qquad (V.56)$$
The notation MMSE(P) in (V.55) recalls that the decoder estimation cost is the Minimum Mean Square Error estimation cost. For such objective, the decoder optimal decision policy is well known and given by the conditional expectation stated in the following lemma.

**Lemma 2** Given a power cost parameter $P \ge 0$, the optimal estimation cost MMSE(P) satisfies

$$ \mathrm{MMSE}(P) = \inf_{Q \in \mathcal{Q}_c(P)} \mathbb{E}_Q \left[ (X_1 - \mathbb{E}[X_1|W_2, Y_1])^2 \middle| W_2, Y_1 \right], \quad (V.57) $$

$$ \mathcal{Q}_c(P) = \left\{ \begin{array}{l} \mathcal{Q}_{U_1 W_1 W_2 | X_0} \quad \text{s.t. } P = E_Q [U_1^2], \\ I(W_1; Y_1|W_2) - I(W_1, W_2; X_0) \ge 0 \end{array} \right\}. \quad (V.58) $$

*Proof.* [Lemma 2] For all probability distribution $Q_{X_1 W_2 Y_1}$, the random variable $U_2 = \mathbb{E}[X_1|W_2, Y_1]$ minimizes $\mathbb{E}_Q[(X_1 - U_2)^2]$. □

Note that the remaining optimization problem (V.57) is difficult to solve since the domain is the set of real-valued distributions. In the next section, we investigate this optimization problem by considering additional assumptions that restrict the set of conditional distributions $Q_{U_1 W_1 W_2 | X_0}$.

### V.2.c Control schemes of particular interest

We restrict our attention to specific choices for the auxiliary random variables $W_1$ and $W_2$. We consider both $W_1$ and $W_2$ are Gaussian in Sec. V.2.c, whereas in Sec. V.2.c, the random variable $W_2$ is discrete and $W_1$ is Gaussian.

#### Gaussian auxiliary random variables $W_1$ and $W_2$

We focus our attention to the class of jointly Gaussian random variables $(X_0, U_1, W_1, W_2, X_1, Y_1, U_2)$.

**Definition 34** Given a power cost parameter $P \ge 0$, we define the optimal estimation cost obtained with Gaussian random variables

$$ \mathrm{MMSE}_G(P) = \inf_{Q \in \mathcal{Q}_G(P)} \mathbb{E}_Q \left[ (X_1 - \mathbb{E}[X_1|W_2, Y_1])^2 \middle| W_2, Y_1 \right], \quad (V.59) $$

$$ \mathcal{Q}_G(P) = \left\{ \begin{array}{l} \mathcal{Q}_{U_1 W_1 W_2 | X_0} \quad \text{is conditionally Gaussian and } P = E_Q [U_1^2], \\ I(W_1; Y_1|W_2) - I(W_1, W_2; X_0) \ge 0 \end{array} \right\}. \quad (V.60) $$

Note that if $(X_0, U_1, W_2)$ are Gaussian, then $\mathbb{E}[X_1|W_2, Y_1]$ is also Gaussian.

**Definition 35** Given a power cost parameter $P \ge 0$, we consider the linear scheme defined by

$$ U_{1,\ell}(P) = \begin{cases} -\sqrt{\frac{P}{Q}}X_0 & \text{if } P \in [0, Q], \\ -X_0 + \sqrt{P-Q} & \text{otherwise.} \end{cases} \quad (V.61) $$

The linear estimation cost function given by

$$ \mathrm{MMSE}_{\ell}(P) = \begin{cases} \frac{(\sqrt{Q}-\sqrt{P})^2 \cdot N}{(\sqrt{Q}-\sqrt{P})^2+N} & \text{if } P \in [0, Q], \\ 0 & \text{otherwise.} \end{cases} \quad (V.62) $$

Note that if $P \ge Q$, the interim state $X_1$ can be canceled and the offset $\sqrt{P-Q}$ is only included to meet the power constraint with equality, as in (V.49). In the linear scheme $U_{1,\ell}(P)$, the channel input is used to cancel the state $X_0$. The next lemma is a reformulation of (Witsenhausen, 1968, Lemma 11), which shows that $\mathrm{MMSE}_{\ell}(P)$ is obtained by using the best linear scheme.
**Lemma 3** We consider the linear strategy

$$U_1 = a \cdot X_0 + b, \qquad (V.63)$$

with parameters $(a, b) \in \mathbb{R}^2$, such that to match the power cost constraint $\mathbb{E}[U_1^2] = a^2Q + b^2 = P$. The optimal estimation cost is given by

$$\inf_{\substack{(a,b) \in \mathbb{R}^2, \\ a^2Q+b^2=P}} \mathbb{E}[(X_1 - \mathbb{E}[X_1|Y_1])^2|Y_1] = \text{MMSE}_\ell(P), \qquad (V.64)$$

which is achieved by the strategy $U_{1,\ell}(P)$ defined in (V.61).

For the sake of clarity, we also provide the proof of Lemma 3, in (Le Treust and Oechtering, 2022, App. B, [W9]).

**Theorem 27** Suppose that $Q > 4N$, we define the parameters

$$P_1 = \frac{1}{2} \left( Q - 2N - \sqrt{Q \cdot (Q - 4N)} \right), \qquad (V.65)$$

$$P_2 = \frac{1}{2} \left( Q - 2N + \sqrt{Q \cdot (Q - 4N)} \right). \qquad (V.66)$$

The optimal estimation cost obtained with Gaussian random variables is given by

$$\text{MMSE}_{\text{G}}(P) = \begin{cases} \frac{N \cdot (Q - N - P)}{Q} & \text{if } Q > 4N \text{ and } P \in [P_1, P_2], \\ \text{MMSE}_{\ell}(P) & \text{otherwise.} \end{cases} \qquad (V.67)$$

The proof of Theorem 27 is stated in (Le Treust and Oechtering, 2022, App. C, [W9]). The estimation cost in (V.67) can be obtained by using, either a time sharing strategy between the two linear schemes $U_{1,\ell}(P_1)$ and $U_{1,\ell}(P_2)$, when $Q > 4N$ and $P \in [P_1, P_2]$, and otherwise with the linear scheme $U_{1,\ell}(P)$. This result shows that, under the Gaussian assumption, memoryless policies are optimal so that these policies are also optimal for the original scalar Witsenhausen counterexample setup restricted to Gaussian random variables. However, as pointed out by Witsenhausen in Witsenhausen (1968), the Gaussian assumption is a strong restriction in the original scalar model which induces control designs that are generally not optimal.

**Gaussian auxiliary random variable $W_1$ and discrete $W_2$**

In this section, we assume that $P \le Q$ and we consider that $W_2$ is a discrete auxiliary random variable, equal to the sign of the interim random variable $X_1$,

$$W_2 = \text{sign}(X_1). \qquad (V.68)$$

We assume that the random variables $(X_0, U_1)$ are centered jointly Gaussian, distributed according to $\mathcal{N}(0, K)$, with covariance matrix

$$K = \begin{pmatrix} Q & \rho \sqrt{PQ} \\ \rho \sqrt{PQ} & P \end{pmatrix}, \qquad (V.69)$$

depending on the correlation parameter $\rho \in [-1, 1]$.

Given a correlation parameter $\rho \in [-1, 1]$, we reformulate the pair of correlated Gaussian random variables $(X_0, U_1)$ into a pair of independent Gaussian random variables $(\tilde{S}, \tilde{X})$ such that the sum is preserved, i.e. $X_0+U_1 = \tilde{S}+\tilde{X}$, and the auxiliary channel input $\tilde{X}$ is independent of the auxiliary channel state $\tilde{S}$. Since $(X_0, U_1) \sim \mathcal{N}(0, K)$, we have $U_1 = \rho \sqrt{\frac{P}{Q}}X_0 + \tilde{X}$ with $\tilde{X} \sim \mathcal{N}(0, P(1 - \rho^2))$ and $\tilde{X} \perp X_0$.
Therefore, we introduce two Gaussian random variables $\tilde{X} \sim \mathcal{N}(0, P(1-\rho^2))$ and $\tilde{S} \sim \mathcal{N}(0, (\sqrt{Q}+\rho\sqrt{P})^2)$ such that

$$ \tilde{S} = \frac{\sqrt{Q} + \rho\sqrt{P}}{\sqrt{Q}} \cdot X_0, \qquad (V.70) $$

$$ \tilde{X} \perp (\tilde{S}, X_0), \qquad (V.71) $$

$$ X_1 = X_0 + U_1 = \tilde{X} + \tilde{S}. \qquad (V.72) $$

Then, the state-dependent channel reformulates

$$ Y_1 = X_0 + U_1 + Z = \tilde{X} + \tilde{S} + Z, \qquad (V.73) $$

for which Costa's auxiliary random variable for Dirty Paper Coding (DPC), see Costa (1983), writes

$$ W_1 = \tilde{X} + \alpha \tilde{S}, \quad \text{with} \quad \alpha = \frac{P(1 - \rho^2)}{P(1 - \rho^2) + N}. \qquad (V.74) $$

By combining (V.70) and (V.74), we reformulate the auxiliary random variable

$$ W_1 = \tilde{X} + \frac{P(1 - \rho^2)(\sqrt{Q} + \rho\sqrt{P})}{(P(1 - \rho^2) + N)\sqrt{Q}} \cdot X_0, \quad \text{where } X_0 \perp \tilde{X} \sim \mathcal{N}(0, P(1 - \rho^2)). \qquad (V.75) $$

Note that the correlation parameter $\rho \in [-1, 1]$ is a free parameter that we use to minimize the decoder estimation cost.

**Definition 36** Given $P \ge 0$, we consider the auxiliary random variables $(W_1, W_2)$ defined by (V.75) and (V.68), the optimal estimation cost is defined by

$$ \text{MMSE}_{\text{coord}}(P) = \min_{\rho \in [-1,1]} \mathbb{E} \left[ \left( X_1 - \mathbb{E}[X_1|W_2, Y_1] \right)^2 \middle| W_2, Y_1 \right], \qquad (V.76) $$

$$ \text{s.t.} \quad I(W_1; Y_1|W_2) - I(W_1; X_0|W_2) \ge I(X_0; W_2). \qquad (V.77) $$

In the information constraint (V.77), the quantization rate $I(X_0; W_2)$ must be smaller than the state dependent channel capacity $I(W_1; Y_1|W_2) - I(W_1; X_0|W_2)$.

**Proposition 7** Given $P \ge 0$, we consider the auxiliary random variables $(W_1, W_2)$ defined by (V.75) and (V.68) and we use the change of variable $T = P + Q + 2\rho\sqrt{PQ}$. We have

$$ \text{MMSE}_{\text{coord}}(P) = \min_{\rho \in [-1,1]} \frac{TN}{T+N} \cdot \left( 1 - \frac{2}{\sqrt{T+N}} \cdot \frac{1}{2\pi} \int \frac{\phi\left(y_1 \cdot \sqrt{\frac{2T+N}{N(T+N)}}\right)}{\Phi\left(y_1 \cdot \sqrt{\frac{T}{N(T+N)}}\right)} dy_1 \right), \qquad (V.78) $$

$$ \text{s.t.} \quad \frac{1}{2} \log_2 \left( 1 + \frac{P(1 - \rho^2)}{N} \right) - \Psi\left(\sqrt{\frac{T}{N}}\right) + \Psi\left(\sqrt{\frac{T(\sqrt{Q} + \rho\sqrt{P})^2N + P(1 - \rho^2)(T + N)^2}{(\sqrt{Q} + \rho\sqrt{P})^2N^2}}\right) \ge 1, \qquad (V.79) $$

where the entropy reduction function $\Psi: \mathbb{R} \to [0, 1]$ is defined by

$$ \Psi(\alpha) = \int 2\Phi(\alpha \cdot x) \cdot \log_2(2\Phi(\alpha \cdot x)) \frac{1}{\sqrt{2\pi}} \exp\left(-\frac{x^2}{2}\right) dx, \qquad (V.80) $$

and $\Phi(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{x} \exp\left(-\frac{t^2}{2}\right) dt$, is the Gaussian cumulative distribution function.

The proof of Prop. 7 is stated in (Le Treust and Oechtering, 2022, App. D, [W9]). The first term of (V.79) corresponds to the capacity of a Gaussian state-dependent channel with channel input power $P(1 - \rho^2)$ and noise variance $N$. The entropy reduction function $\Psi(\alpha)$ corresponds to the entropy penalty term of skew normal distribution with the skewness factor $\alpha \in \mathbb{R}$.
<figure><img src="image_37.png" /><figcaption>Figure V.7 – Entropy reduction function Ψ(α) defined in (V.80).</figcaption></figure>

## V.2.d Numerical Results

We compare the performances of the control schemes of Sec. V.2.c and Sec. V.2.c, to the Witsenhausen two-point strategy (Witsenhausen, 1968, Sec. 5). In Grover and Sahai (2010), Grover and Sahai investigate a vector-version of the Witsenhausen counterexample in which the decoder is non-causal and implements the DPC scheme of Costa (1983), for a specific channel state. We compare the control schemes of Sec. V.2.c and Sec. V.2.c to the DPC based scheme of Grover and Sahai (2010).

### Witsenhausen two-point strategy

**Proposition 8 (Two-point strategy)** For some parameter $a \ge 0$, Witsenhausen two-point strategy is defined by

$$U_1 = a \cdot \mathrm{sign}(X_0) - X_0. \qquad (V.81)$$

The power and estimation costs are given by

$$P_{\text{two}}(a) = Q + a \left( a - 2\sqrt{\frac{2Q}{\pi}} \right), \qquad (V.82)$$

$$\text{MMSE}_{\text{two}}(a) = \sqrt{\frac{2\pi}{N}} a^2 \phi\left(\frac{a}{\sqrt{N}}\right) \int \frac{\phi\left(\frac{ay}{\sqrt{N}}\right)}{\cosh\left(\frac{ay}{N}\right)} dy, \qquad (V.83)$$

where $\phi(x) = \frac{1}{\sqrt{2\pi}} \exp\left(-\frac{x^2}{2}\right)$ and the optimal receiver's strategy is given by $\mathbb{E}[X_1|Y=y] = a \tanh\left(\frac{ay}{N}\right)$.

For the sake of clarity, we also provide the proof of Proposition 8, in (Le Treust and Oechtering, 2022, App. E, [W9]). By letting $N = 1$ and $a = \sqrt{Q}$, we recover the equations in the proof of (Witsenhausen, 1968, Theorem 2). Note that the function $P_{\text{two}}(a)$ decreases over the interval $[0, \sqrt{\frac{2Q}{\pi}}]$, where it reaches the minimal value $Q(1 - \frac{2}{\pi})$, and then increases for $a \ge \sqrt{\frac{2Q}{\pi}}$. Note that this two-point strategy requires a power cost $P \ge Q(1 - \frac{2}{\pi})$ in order to be implemented. This strategy induces a binary interim state $X_1 = a \cdot \mathrm{sign}(X_0) \in \{-a, a\}$ for which the estimation cost outperforms, in some cases, the best estimation cost obtained via the linear scheme, see (Witsenhausen, 1968, Theorem 2).

### Dirty Paper Coding (DPC) based scheme for non-causal decoder

In Grover and Sahai (2010), the authors investigate a vector version of Witsenhausen counterexample in which the decoder is non-causal.

**Definition 37** For $n \in \mathbb{N}^*$, a “control design” with non-causal encoder and non-causal decoder is a tuple of stochastic functions $c = (f, g)$ defined by

$$f: \mathcal{X}_0^n \to \mathcal{U}_1^n, \quad g: \mathcal{Y}_1^n \to \mathcal{U}_2^n. \qquad (V.84)$$

We denote by $\mathcal{C}_{nc}(n)$ the set of control designs with non-causal encoder and non-causal decoder.

In (Grover and Sahai, 2010, App. D.1-D.7), the authors investigate a Dirty Paper Coding (DPC) based scheme by using a Gaussian channel input $U_1 \sim \mathcal{N}(0, P)$, $U_1 \perp X_0$ and the auxiliary random
variable $W = U_1 + \alpha X_0$. The leads to

$$I(W; Y_1) - I(W; X_0) = \frac{1}{2} \log_2 \left( \frac{P(P+Q+N)}{PQ(1-\alpha)^2 + N(P+\alpha^2 Q)} \right), \qquad (V.85)$$

$$H(U_1 + X_0 | W, Y_1) = \frac{1}{2} \log_2 \left( (2\pi e) \cdot \frac{NPQ(1-\alpha)^2}{PQ(1-\alpha)^2 + N(P+\alpha^2 Q)} \right). \qquad (V.86)$$

Since the random variables are jointly Gaussian, the optimization problem writes

$$\mathrm{MMSE}_{\mathrm{dpc}}(P) = \min_{\substack{\alpha \in \mathbb{R} \\ P(P+Q+N) \ge PQ(1-\alpha)^2 + N(P+\alpha^2 Q)}} \frac{NPQ(1-\alpha)^2}{PQ(1-\alpha)^2 + N(P+\alpha^2 Q)}. \qquad (V.87)$$

**Proposition 9** Let $P^* \ge 0$, the unique positive root of equation $P^2(P+Q+N) = QN^2$.

* If $P \le P^*$, the estimation cost for DPC is given by

$$\mathrm{MMSE}_{\mathrm{dpc}}(P) = \frac{N(N\sqrt{Q} - P\sqrt{P+Q+N})^2}{(P+N)^2(P+Q+N)}, \qquad (V.88)$$

which is achieved with $\alpha^* = \frac{P(\sqrt{Q}+\sqrt{P+Q+N})}{\sqrt{Q}(P+N)}$.

* If $P > P^*$, then $\mathrm{MMSE}_{\mathrm{dpc}}(P) = 0$ which is achieved with $\alpha^* = 1$.

This result is proved in (Grover and Sahai, 2010, App. D.1-D.7), we recall the main proof arguments in (Le Treust and Oechtering, 2022, App. F, [W9]). In (Grover and Sahai, 2010, App. D.8), the authors additionally investigate a combination between the linear scheme and the DPC scheme. Given a parameter $-\sqrt{P/Q} \le \beta \le \sqrt{P/Q}$, the transmit power $P$ is divided into a linear part $U_{1,1} = -\beta X_0$ and a part $U_{1,2}$ used to implement DPC against the state $(1-\beta)X_0 \sim \mathcal{N}(0, (1-\beta)^2Q)$ with power constraint $\mathbb{E}[U_{1,2}^2] \le P - \beta^2Q$. By using the change of variable $\beta = -\rho\sqrt{P/Q}$, we obtain the correlation matrix of (V.69) and the auxiliary state-dependent channel $Y_1 = \tilde{X} + \tilde{S} + Z$ where $\tilde{X} + \tilde{S} = X_0 + U_1$, the channel state $\tilde{S}$ is defined in (V.70), and $\tilde{X} \perp (\tilde{S}, X_0)$ with $\mathbb{E}[\tilde{X}^2] \le P(1-\rho^2)$. Therefore, we replace $P$ and $Q$ in (V.88), respectively by $P(1-\rho^2)$ and $(\sqrt{Q} + \rho\sqrt{P})^2$, and we obtain

$$\mathrm{MMSE}_{\mathrm{lin}+\mathrm{dpc}}(P) = \min_{\rho \in [-1,1]} \frac{N(P(1-\rho^2)\sqrt{P+Q+2\rho\sqrt{PQ+N}} - N(\sqrt{Q}+\rho\sqrt{P}))^2}{(P(1-\rho^2)+N)^2(P+Q+2\rho\sqrt{PQ+N})}. \qquad (V.89)$$

In the next section, we will see that this estimation cost $\mathrm{MMSE}_{\mathrm{lin}+\mathrm{dpc}}(P)$ outperforms all other estimation costs.

## V.2.e Discussion

In Figure V.8, we compare the estimation cost proposed in Sec. V.2.c and Sec. V.2.c, with the estimation costs from the literature, for $(Q, N) = (0.1, 0.01)$.

* The blue curve corresponds to the estimation cost of the best linear scheme $\mathrm{MMSE}_\ell(P)$ defined in (V.62), see also (Witsenhausen, 1968, Lemma 11).

* The green curve depicts the estimation cost of Witsenhausen two point strategy $(P_{\mathrm{two}}, \mathrm{MMSE}_{\mathrm{two}})$ defined in (V.82) and (V.83), see also (Witsenhausen, 1968, Sec. 5).

* The red curve presents the estimation cost of the Grover and Sahai's combination of the linear scheme and DPC scheme $\mathrm{MMSE}_{\mathrm{lin}+\mathrm{dpc}}(P)$ defined in (V.89), when the decoder is non-causal, see also (Grover and Sahai, 2010, App. D.1-D.8).

The coordination coding scheme we propose in Sec. V.2.c is restricted to Gaussian random variables. The estimation cost $\mathrm{MMSE}_G(P)$ defined in (V.67) consists of the brown line when $Q > 4N$ and $P \in$
<figure><img src="image_38.png" /><figcaption>Figure V.8 – Blue: optimal linear scheme MMSE<sub>ℓ</sub>(P) in (V.62), Brown: time sharing N·(Q-N-P)/Q in (V.67), Green: two-point strategy (P<sub>w</sub>, MMSE<sub>w</sub>) in (V.82) and (V.83) ; Red: combination DPC and linear scheme MMSE<sub>lin+dpc</sub>(P) in (V.89) ; Orange: MMSE when W<sub>2</sub> = sign(X<sub>1</sub>) and W<sub>1</sub> is Costa’s auxiliary random variable MMSE<sub>coord</sub>(P) in (V.78).</figcaption></figure>

[P<sub>1</sub>, P<sub>2</sub>], and of the estimation cost MMSE<sub>ℓ</sub>(P) represented by the blue line, otherwise. Note that the function P ↦→ MMSE<sub>G</sub>(P) is the convexification of the linear estimation cost function P ↦→ MMSE<sub>ℓ</sub>(P).

We reduce the estimation cost by using the auxiliary random variable W<sub>2</sub> = sign(X<sub>1</sub>) that encapsulates the sign of the interim state, see Sec. V.2.c. This strategy requires a certain power cost level for the first controller to transmit the sign of X<sub>1</sub> to the second controller. The Fig. V.8, shows the existence of some weight parameter κ ∈ [0, 1], such that our coordination coding scheme of Sec. V.2.c, outperforms Witsenhausen two point strategy

$$ \kappa P + (1 - \kappa) \text{MMSE}_{\text{coord}}(P) \leq \kappa P_{\text{two}} + (1 - \kappa) \text{MMSE}_{\text{two}}. \qquad (V.90) $$

Note also that the power cost required to implement our coordination coding scheme of Sec. V.2.c, is strictly less than the minimal power cost Q(1 - 2/π) needed to implement the Witsenhausen two point strategy.

When the decoder is non-causal, the combination between the linear scheme and the DPC scheme MMSE<sub>lin+dpc</sub>(P) proposed in Grover and Sahai (2010), Pareto-dominates all the other solutions.

## V.3 Strong coordination of signals and actions

A general information-theoretic framework to study coordination in networks was put forward in Cuff et al. (2010), related to earlier work on “Shannon’s reverse coding theorem” Bennett et al. (2002) and the compression of probability distribution sources and mixed quantum states Kramer and Savari (2007); Soljanin (2002); Winter (2002). This framework also relates to the game-theoretic perspective on coordination Gossner et al. (2006) with applications, for instance, to power control Larrousse et al. (2018). Recent extensions of the framework have included the possibility of coordination through interactive communication Gülcü and Barg (2016); Haddadpour et al. (2017); Yassaee et al. (2015). Two information-theoretic metrics have been proposed to measure the level of coordination: empirical coordination, introduced in Chap. IV, which requires the joint histogram of the devices’ actions to approach a target distribution, and strong coordination, which requires the joint distribution of sequences of actions to converge to an i.i.d. target distribution, e.g., in ℓ<sub>1</sub> distance Cuff (2013); Cuff et al. (2010). Empirical coordination captures an “average behavior” over multiple repeated actions of the devices, in contrast, strong coordination captures the behavior of sequences. A byproduct of strong coordination is that it enforces some level of “security,” in the sense of guaranteeing that sequence of actions will be unpredictable to an outside observer beyond what is known about the target joint distribution of sequences.
Strong coordination in networks was first studied over error free links in Cuff et al. (2010) and later extended to noisy communication links in Haddadpour et al. (2017). In the latter setting, the signals that are transmitted and received over the physical channel become a part of what can be observed, and one can therefore coordinate the actions of the devices with their communication signals Cuff and Schieler (2011), (Le Treust, 2017, [J6]).

To illustrate the relevance of this joint coordination problem, we can consider the situation in which two stockbrokers who work for two competing companies decide to collude. One stockbroker, Agent 1, has access to a source of information on future market developments: he sees the symbol 0 when it is profitable to buy and the symbol 1 when it is profitable to sell. Agent 1 can accordingly act to buy or sell, which is represented by 0 or 1, respectively. The other stockbroker, Agent 2, takes similar actions but is less informed and only sees the actions of Agent 1. Both agents are assumed to benefit from helping each other but their cooperation would be illegal and any coordination should therefore be kept secret. Secrecy is achieved by keeping the signal distributions to be statistically indistinguishable from i.i.d., so that an outside observer working for a regulating entity would not be able to prove that an exchange of information takes place.

As the stockbrokers example above suggests, the joint strong coordination of signals and actions with a noisy link is particularly interesting if security is required: if for example we require the actions of the agents to appear independent of the communication, a malicious eavesdropper who observes the output of the channel cannot infer anything about the source and the reconstruction without having access to the source of common randomness. This “secure coordination” was investigated for error-free links in Satpathy and Cuff (2016).

In this section, we address the problem of strong coordination in a two-node network comprised of an information source and a noisy channel, in which both nodes have access to a common source of randomness. This scenario presents two conflicting goals: the encoder needs to convey a message to the decoder in order to coordinate the actions, while simultaneously coordinating the signals that encode the message.

Up to now, the coordination problem assumes that the source and the channel follow distributions which are fixed ahead of time and known by the agents. However, this constraint prevents us from modeling situations in which the agent reacts to an external stimulus, and in which the channel statistics depend on the environment. For instance, consider a situation where the actions of an agent might be constrained by obstacles that prevent it from making certain choices. In this case the probability distributions given by nature could change with time and would be partially if not completely unknown to some of the agents. To include such situations in the coordination framework, we introduce a random state capturing the effect of the environment, to model actions and channels that change with external factors, and we consider a general setting in which we have a state-dependent channel and a source with decoder’s side information as in (Le Treust, 2014, [IC12]), (Le Treust, 2015c, [IC13]), Larrousse et al. (2015a).

We derive an inner and an outer bound for the strong coordination region by developing a joint source-channel scheme in which an auxiliary codebook allows us to satisfy both coordination of signals and actions. Since the two bounds do not match, the optimality of our general achievability scheme remains an open question. However, we succeed in characterizing the strong coordination region in some special cases: i) when the channel is noiseless, ii) when the decoder is lossless, and iii) when the random variables of the channel are independent from the random variables of the source. In all these cases, the sets of achievable target distributions are the same as for empirical coordination (Le Treust, 2015c, [IC13]), but we show that a positive rate of common randomness is required for strong coordination.

The remainder of this section is organized as follows. Section V.3.a describes a simple model in which there is no state and no side information and derives an inner and an outer bound for the strong coordination region. The information-theoretic modeling of coordination problems relevant to this work is best illustrated in this simplified scenario. Section V.3.b extends the inner and outer bounds to the general case of a noisy channel with state and side information at the decoder. Section V.3.c characterizes the strong coordination region for three special cases and shows that the separation principle does not hold for strong coordination.
### V.3.a Inner and outer bounds for the strong coordination region

Before we consider the general model with a state and side information, it is helpful to focus on the simpler model depicted in Figure V.9 to understand the nature of the problem. Two agents, the encoder and the decoder, wish to coordinate their behaviors: the stochastic actions of the agents should follow a known and fixed joint distribution.

<figure><img src="image_39.png" /><figcaption>Figure V.9 – Coordination of signals and actions for a two-node network with a noisy channel with non-causal encoder and decoder.</figcaption></figure>

Given a rate parameter $R_0 \ge 0$, we suppose that the encoder and the decoder have access to a shared source of uniform randomness $C \in [1, 2^{nR_0}]$. Let $U^n \in \mathcal{U}^n$ be an i.i.d. source with distribution $\bar{P}_U$. The encoder observes the sequence $U^n \in \mathcal{U}^n$ and selects a signal $X^n = f_n(U^n, C)$, where $f_n: \mathcal{U}^n \times [1, 2^{nR_0}] \to \mathcal{X}^n$ is a stochastic map. The signal $X^n$ is transmitted over a discrete memoryless channel parametrized by the conditional distribution $\bar{P}_{Y|X}$. Upon observing $Y^n$ and common randomness $C$, the decoder selects an action $V^n = g_n(Y^n, C)$, where $g_n: \mathcal{Y}^n \times [1, 2^{nR_0}] \to \mathcal{V}^n$ is a stochastic map. For block length $n$, the pair $(f_n, g_n)$ constitutes a code.

We recall the definitions of empirical and strong coordination Cuff (2009); Cuff et al. (2010).

**Definition 38** A distribution $\bar{P}_{UXYV}$ is achievable for empirical coordination if there exists a sequence $\{(f_n, g_n)\}_{n \ge 1}$ of encoders-decoders such that

$$ \forall \delta > 0, \quad \lim_{n \to +\infty} \min_{(f_n, g_n)_{n \ge 1}} \Pr \left( \left\| Q_{UXVY}^n - \bar{P}_{UXVY} \right\|_1 > \delta \right) = 0, \quad (V.91) $$

where $Q_{UXVY}^n$ is the empirical distribution of the random variables $(U^n, X^n, Y^n, V^n)$ induced by the code. The empirical coordination region $\mathcal{R}_e$ is the set of achievable distributions $\bar{P}_{UXYV}$.

**Definition 39** A pair $(\bar{P}_{UXYV}, R_0)$ is achievable for strong coordination if there exists a sequence $\{(f_n, g_n)\}_{n \ge 1}$ of encoders-decoders with rate of common randomness $R_0$, such that

$$ \lim_{n \to \infty} \left\| \mathcal{P}_{U^n X^n Y^n V^n}^c - \bar{P}_{UXYV}^{\otimes n} \right\|_1 = 0 $$

where $\mathcal{P}_{U^n X^n Y^n V^n}^c \in \Delta(\mathcal{U}^n \times \mathcal{X}^n \times \mathcal{Y}^n \times \mathcal{V}^n)$ is the joint distribution induced by the code, and $\bar{P}_{UXYV}^{\otimes n}$ denotes the i.i.d. probability distribution. The strong coordination region $\mathcal{R}$ is the closure of the set of achievable pairs $(\bar{P}_{UXYV}, R_0)$.

Our first result is an inner and outer bound for the strong coordination region $\mathcal{R}$ (Cervia et al., 2017b, [IC19]).

**Theorem 28** Let $\bar{P}_U$ and $\bar{P}_{Y|X}$ be the given source and channel parameters, then $\mathcal{R}'_{in} \subseteq \mathcal{R} \subseteq \mathcal{R}'_{out}$ where:

$$ \mathcal{R}'_{in} := \left\{ \begin{array}{l} (\bar{P}_{UXYV}, R_0) \text{ such that:} \\ \bar{P}_{UXYV} = \bar{P}_U \bar{P}_{X|U} \bar{P}_{Y|X} \bar{P}_{V|UXY} \\ \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{UXYWV} = \bar{P}_U \bar{P}_{W|U} \bar{P}_{X|UW} \bar{P}_{Y|X} \bar{P}_{V|WY} \\ I(W; U) \le I(W; Y) \\ R_0 \ge I(W; UXV|Y) \end{array} \right\} \quad (V.92) $$
$$
\begin{equation}
\begin{aligned}
\mathcal{R}'_{\text{out}} &:= \left\{
\begin{array}{@{}l@{}}
(\bar{P}_{UXYV}, R_0) \text{ such that:} \\
\bar{P}_{UXYV} = \bar{P}_U \bar{P}_{X|U} \bar{P}_{Y|X} \bar{P}_{V|UXY} \\
\phantom{\bar{P}_{UXYV} = {}} \exists W \text{ taking values in } \mathcal{W} \\
\bar{P}_{UXYWV} = \bar{P}_U \bar{P}_{W|U} \bar{P}_{X|UW} \bar{P}_{Y|X} \bar{P}_{V|WY} \\
\phantom{\bar{P}_{UXYWV} = {}} I(W; U) \le I(X; Y) \\
R_0 \ge I(W; UXV|Y) \\
|\mathcal{W}| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V}| + 4
\end{array}
\right\}.
\end{aligned}
\tag{V.93}
\end{equation}
$$

The proof of Theorem 28 is provided in (Cervia et al., 2020, [J9]).

**Remark 20** Observe that the decomposition of the joint distributions $\bar{P}_{UXYV}$ and $\bar{P}_{UWXYV}$ is equivalently characterized in terms of Markov chains:

$$
Y - X - U, \quad \left\{ \begin{array}{l} Y - X - (U, W) \\ V - (Y, W) - (X, U) \end{array} \right. . \qquad (V.94)
$$

**Remark 21** The empirical coordination region for the setting of Figure V.9 was investigated in Cuff and Schieler (2011), in which the authors derived an inner and outer bound. Note that the information constraint $I(W; U) \le I(W; Y)$ and the decomposition of the joint probability distribution $\bar{P}_U \bar{P}_{W|U} \bar{P}_{X|UW} \bar{P}_{Y|X} \bar{P}_{V|WY}$ are the same for empirical coordination (Cuff and Schieler, 2011, Theorem 1). The main difference is that strong coordination requires a positive rate of common randomness $R_0 > I(W; UXV|Y)$.

V.3.b Strong coordination region with state and side information

<figure><img src="image_40.png" /><figcaption>Figure V.10 – Coordination of signals and actions for a two-node network with a noisy channel with state and side information at the decoder.</figcaption></figure>

The problem of source coding with side information at the receiver was notably considered in Wyner and Ziv (1976), while Gel'fand and Pinsker (1980) studies channel coding with non-causal state information available at the encoder. In practice, it is realistic to assume that the encoder and the decoder have access to some side information, without having full knowledge of it as in Cover and Chiang (2002); Merhav and Shamai (2003).

In this paper, we study a joint source-channel strong coordination system whose encoder has the chan-
nel state information available and whose decoder has access to side information that may be correlated
to the source.

More precisely, in this section we consider the model depicted in Figure V.10, where the noisy channel
depends on a state $S^n$, and the decoder has access to non-causal side information $Z^n$.

The encoder selects a signal $X^n = f_n(U^n, C)$, with $f_n: \mathcal{U}^n \times [1, 2^{nR_0}] \to \mathcal{X}^n$ a stochastic map, and
transmits it over the discrete memoryless channel $\bar{P}_{Y|XS}$ where $S$ represents the state. The decoder then
selects an action $V^n = g_n(Y^n, Z^n, C)$, where $g_n: \mathcal{Y}^n \times \mathcal{Z}^n \times [1, 2^{nR_0}] \to \mathcal{V}^n$ is a stochastic map and $Z^n$
represents the side information available at the decoder.

**Remark 22** The channel state information and side information at the decoder are represented explicitly by the random variables $S^n$ and $Z^n$ respectively, and we make no assumptions on the correlation of $(U^n, S^n, Z^n)$. This includes scenarios where the encoder has access to partial, perfect or noisy channel
state information, since the variables $U^n$ and $S^n$ are possibly correlated. Moreover, the decoder side information $Z^n$ can contain partial, perfect or noisy information on the channel state, on the source, or on both of them.

We recall the notions of empirical and strong coordination in this setting Cuff (2009); Cuff et al. (2010).

**Definition 40** A distribution $\bar{P}_{USZXYV}$ is achievable for empirical coordination if there exists a sequence $\{(f_n, g_n)\}_{n \ge 1}$ of encoders-decoders such that

$$ \forall \delta > 0, \quad \lim_{n \to +\infty} \min_{\{(f_n, g_n)\}_{n \ge 1}} \Pr \left( \left\| Q_{USZXYV}^n - \bar{P}_{USZXYV} \right\|_1 > \delta \right) = 0, \quad (V.95) $$

where $Q_{USZXYV}^n$ is the empirical distribution of the random variables $(U^n, X^n, Y^n, V^n)$ induced by the code. The empirical coordination region $\mathcal{R}_e$ is the closure of the set of achievable distributions $\bar{P}_{USZXYV}$. A pair $(\bar{P}_{USZXYV}, R_0)$ is achievable for strong coordination if there exists a sequence $\{(f_n, g_n)\}_{n \ge 1}$ of encoders-decoders with rate of common randomness $R_0$, such that

$$ \lim_{n \to \infty} \left\| P_{U^n S^n Z^n X^n Y^n V^n} - \bar{P}_{USZXYV}^{\otimes n} \right\|_1 = 0 $$

where $P_{USZXYV}^{\otimes n}$ is the joint distribution induced by the code. The strong coordination region $\mathcal{R}$ is the closure of the set of achievable pairs $(\bar{P}_{USZXYV}, R_0)$.

In the case of non-causal encoder and decoder, the problem of characterizing the strong coordination region for the system model in Figure V.10 is still open, but we establish the following inner and outer bounds.

**Theorem 29** Let $\bar{P}_{USZ}$ and $\bar{P}_{Y|XS}$ be the given source and channel parameters, then $\mathcal{R}_{in} \subseteq \mathcal{R} \subseteq \mathcal{R}_{out}$ where:

$$ \mathcal{R}_{in} := \left\{ \begin{array}{l} (\bar{P}_{USZXYV}, R_0) \text{ such that:} \\ \bar{P}_{USZXYV} = \bar{P}_{USZ} \bar{P}_{X|U} \bar{P}_{Y|XS} \bar{P}_{V|UXYSZ} \\ \quad \exists W \text{ taking values in } W \\ \bar{P}_{USZWXYV} = \bar{P}_{USZ} \bar{P}_{W|U} \bar{P}_{X|UW} \bar{P}_{Y|XS} \bar{P}_{V|WYZ} \\ \quad I(W; U) \le I(W; YZ) \\ \quad R_0 \ge I(W; USXV|YZ) \end{array} \right\}, \quad (V.96) $$

$$ \mathcal{R}_{out} := \left\{ \begin{array}{l} (\bar{P}_{USZXYV}, R_0) \text{ such that:} \\ \bar{P}_{USZXYV} = \bar{P}_{USZ} \bar{P}_{X|U} \bar{P}_{Y|XS} \bar{P}_{V|UXYSZ} \\ \quad \exists W \text{ taking values in } W \\ \bar{P}_{USZWXYV} = \bar{P}_{USZ} \bar{P}_{W|U} \bar{P}_{X|UW} \bar{P}_{Y|XS} \bar{P}_{V|WYZ} \\ \quad I(W; U) \le \min\{I(XUS; YZ), \\ \qquad I(XS; Y) + I(U; Z)\} \\ R_0 \ge I(W; USXV|YZ) \\ |W| \le |U \times S \times Z \times X \times Y \times V| + 5 \end{array} \right\}. \quad (V.97) $$

The proof of Theorem 29 is stated in (Cervia et al., 2020, [J9]).

**Remark 23** As in Theorem 28, even if inner and outer bound do not match, they only differ on the upper bound on $I(W; U)$. Note that we cannot compare $I(XUS; YZ)$ and $I(XS; Y) + I(U; Z)$. Hence, in $\mathcal{R}_{out}$ the upper bound on the mutual information $I(W; U)$ is the minimum of the two.
**Remark 24** Observe that the decomposition of the joint distributions $\bar{P}_{USZXYV}$ and $\bar{P}_{USZWXYV}$ is equivalently characterized in terms of Markov chains:

$$ \left\{ \begin{array}{l} Z - (U, S) - (X, Y) \\ Y - (X, S) - U \end{array} \right. , \quad \left\{ \begin{array}{l} Z - (U, S) - (X, Y, W) \\ Y - (X, S) - (U, W) \\ V - (Y, Z, W) - (X, S, U) \end{array} \right. . \qquad (V.98) $$

### V.3.c Characterization of the strong coordination region for special cases

Although the inner and outer bounds in Theorem 29 do not match in general, we characterize the strong coordination region exactly in three special cases: perfect channel, lossless decoding and separation between the channel and the source.

The empirical coordination region for these three settings was derived in (Le Treust, 2015c, [IC13]), (Le Treust, 2015, [W1]). In this section we recover the same information constraints, but we show that for strong coordination a positive rate of common randomness is also necessary. This reinforces the conjecture, stated in Cuff et al. (2010), that with enough common randomness the strong coordination capacity region is the same as the empirical coordination capacity region for any specific network setting.

#### Perfect channel

<figure><img src="image_41.png" /><figcaption>Figure V.11 – Coordination of signals and actions for a two-node network with a perfect channel.</figcaption></figure>

Suppose we have a perfect channel as in Figure V.11: $\bar{P}_{Y|XS}(y|x,s) = 1_{X=Y}\{x = y\}$. In this case $X^n = Y^n$ and $Z^n$ plays the role of side information at the decoder. We characterize the strong coordination region $\mathcal{R}_{PC}$.

**Theorem 30** In the setting of Theorem 29, suppose that $\bar{P}_{Y|XS}(y|x,s) = 1_{X=Y}\{x = y\}$. Then the strong coordination region is

$$ \mathcal{R}_{PC} := \left\{ \begin{array}{l} (\bar{P}_{UZXV}, R_0) \text{ such that:} \\ \bar{P}_{UZXV} = \bar{P}_{UZ}\bar{P}_{X|U}\bar{P}_{V|UXZ} \\ \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{UZWXV} = \bar{P}_{UZ}\bar{P}_{W|U}\bar{P}_{X|UW}\bar{P}_{V|WXZ} \\ I(WX; U) \le H(X) + I(W; Z|X) \\ R_0 \ge I(W; UV|XZ) \\ |W| \le |\mathcal{U} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{V}| + 4 \end{array} \right\} \qquad (V.99) $$

The proof of Theorem 30 is stated in (Cervia et al., 2020, [J9]).

**Remark 25** Observe that the decomposition of the joint distributions $\bar{P}_{UZXV}$ and $\bar{P}_{UZWXV}$ is equivalently characterized in terms of Markov chains:

$$ Z - U - X, \quad \left\{ \begin{array}{l} Z - U - (X, W) \\ V - (X, Z, W) - U \end{array} \right. . \qquad (V.100) $$
**Case** $H(Y|X) = 0$ Suppose that, instead of assuming that there is a perfect channel between the encoder and the decoder, we consider the more general case $H(Y|X) = 0$. Then, we recover a very similar result to $\mathcal{R}_{PC}$.

**Proposition 10** Consider the setting of Theorem 29 and suppose that $H(Y|X) = 0$. Then the strong coordination region is

$$ \mathcal{R}_{H(Y|X)} := \left\{ \begin{array}{l} (\bar{P}_{USZXYV}, R_0) \text{ such that:} \\ \bar{P}_{USZXYV} = \bar{P}_{USZ}\bar{P}_{X|U}\bar{P}_{Y|XS}\bar{P}_{V|USZXY} \\ \quad \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{USZWXYV} = \bar{P}_{USZ}\bar{P}_{W|U}\bar{P}_{X|UW} \\ \quad \bar{P}_{Y|XS}\bar{P}_{V|WZY} \\ I(WX; U) \le H(X) + I(W; Z|X) \\ R_0 \ge I(W; UV|XZ) \\ |W| \le |\mathcal{U} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{V}| + 4 \end{array} \right\} $$

Lossless decoding

<figure><img src="image_42.png" /><figcaption>Figure V.12 – Coordination of signals and actions for a two-node network with a noisy channel and a lossless decoder.</figcaption></figure>

Suppose that the decoder wants to reconstruct the source losslessly, i.e., $V = U$ as in Figure V.12. Then, we characterize the strong coordination region $\mathcal{R}_{LD}$.

**Theorem 31** Consider the setting of Theorem 29 and suppose that $\bar{P}_{V|USXYZ}(\mathbf{v}|\mathbf{u}, \mathbf{s}, \mathbf{x}, \mathbf{y}, \mathbf{z}) = \mathbb{1}_{V=U}\{\mathbf{u} = \mathbf{v}\}$. Then the strong coordination region is

$$ \mathcal{R}_{LD} := \left\{ \begin{array}{l} (\bar{P}_{USZXY}, R_0) \text{ such that:} \\ \bar{P}_{USZXYV} = \bar{P}_{USZ}\bar{P}_{X|U}\bar{P}_{Y|XS}\mathbb{1}_{V=U} \\ \quad \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{USZWXYV} = \bar{P}_{USZ}\bar{P}_{W|U}\bar{P}_{X|UW}\bar{P}_{Y|XS}\mathbb{1}_{V=U} \\ I(W; U) \le I(W; YZ) \\ R_0 \ge I(W; USX|YZ) \\ |W| \le |\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y}| + 3 \end{array} \right\} \quad (V.101) $$

The proof of Theorem 31 is stated in (Cervia et al., 2020, [J9]).

**Remark 26** Observe that the decomposition of the joint distributions $\bar{P}_{USZXYV}$ and $\bar{P}_{USZWXYV}$ is equivalently characterized in terms of Markov chains:

$$ \left\{ \begin{array}{l} Z - (U, S) - (X, Y) \\ Y - (X, S) - U \end{array} \right. , \quad \left\{ \begin{array}{l} Z - (U, S) - (X, Y, W) \\ Y - (X, S) - (U, W) \end{array} \right. . \quad (V.102) $$
**Remark 27** An equivalent characterization of the region is:

$$ \mathcal{R}_{LD} := \left\{ \begin{array}{l} (\bar{P}_{USZXY}, R_0) \text{ such that:} \\ \bar{P}_{USZXY} = \bar{P}_{USZ}\bar{P}_{X|U}\bar{P}_{Y|XS} \\ \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{USZWXY} = \bar{P}_{USZ}\bar{P}_{W|U}\bar{P}_{X|UW}\bar{P}_{Y|XS} \\ H(U) \le I(WU;YZ) \\ R_0 \ge I(W;USX|YZ) + H(U|WYZ) \\ |W| \le |\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y}| + 1 \end{array} \right\} \qquad (V.103) $$

The region in (V.103) is achievable since with the choice of the auxiliary random variable $W'' = (W, U)$, the constraints in (V.101) become

$$ I(WU;U) = H(U) \le I(WU;YZ) \qquad (V.104) $$

$$ \begin{aligned} R_0 &\ge I(WU; USX|YZ) \\ &= I(W; USX|YZ) + I(U; USX|WYZ) \\ &= I(W; USX|YZ) + H(U|WYZ) - H(U|USXWYZ) \\ &= I(W; USX|YZ) + H(U|WYZ). \end{aligned} \qquad (V.105) $$

Moreover, the converse in the proof of Theorem 31 is still valid with the identification $W = (C, U_{\sim T}, Y_{\sim T}, Z_{\sim T}, T)$.

Note that (Le Treust, 2015c, [IC13], Section IV.B) gives a characterization of the empirical coordination region and the constraint for the mutual information is

$$ 0 \le I(WU;YZ) - H(U) = I(WU;YZ) - H(U) - I(W;S|U) $$

which is the same as in (V.104) because of the Markov chain $SZ - U - W$.

### Independence between source and channel

Suppose that the channel state $P_{S^n}$ is independent of the source and side information $P_{U^n Z^n}$, and that the target joint distribution is of the form $\bar{P}_{UZ}^{\otimes n} \bar{P}_{SXY}^{\otimes n}$. For simplicity, we will suppose that the encoder has perfect state information (see Figure V.13). Then we characterize the strong coordination region $\mathcal{R}_{\text{IND}}$.

Note that in this case the coordination requirements are three-fold: the random variables $(U^n, Z^n, V^n)$ should be coordinated, the random variables $(S^n, X^n, Y^n)$ should be coordinated and finally $(U^n, Z^n, V^n)$ should be independent of $(S^n, X^n, Y^n)$. We introduce two auxiliary random variables $W_1$ and $W_2$, where $W_2$ is used to accomplish the coordination of $(U^n, Z^n, V^n)$, while $W_1$ has the double role of ensuring the independence of source and state as well as coordinating $(S^n, X^n, Y^n)$.

<figure><img src="image_43.png" /><figcaption>Figure V.13 – Coordination of signals and actions for a two-node network with a noisy channel where the source is separated from the channel.</figcaption></figure>
**Theorem 32** Consider the setting of Theorem 29 and suppose that $\bar{P}_{USXYZV} = \bar{P}_{UZV}\bar{P}_{SXY}$. Then, the strong coordination region is

$$ \mathcal{R}_{IND} := \left\{ \begin{array}{l} (\bar{P}_{USZXY}, R_0) \text{ such that:} \\ \bar{P}_{USZXYV} = \bar{P}_{UZ}\bar{P}_{V|UZ}\bar{P}_{S}\bar{P}_{X|S}\bar{P}_{Y|XS} \\ \exists (W_1, W_2) \text{ taking values in } \mathcal{W}_1 \times \mathcal{W}_2 \\ \bar{P}_{USZW_1W_2XYV} = \bar{P}_{UZ}\bar{P}_{W_2|U}\bar{P}_{V|ZW_2} \\ \qquad \bar{P}_{S}\bar{P}_{X|S}\bar{P}_{W_1|SX}\bar{P}_{Y|XS} \\ I(W_1; S) + I(W_2; U) \le I(W_1; Y) + I(W_2; Z) \\ R_0 \ge I(W_1; SX|Y) + I(W_2; UV|Z) \\ (|\mathcal{W}_1|, |\mathcal{W}_2|) \le |\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V}| + 4. \end{array} \right\} \quad (V.106) $$

The proof of Theorem 32 is stated in (Cervia et al., 2020, [J9]).

**Remark 28** Observe that the decomposition of the joint distribution $\bar{P}_{USZW_1W_2XYV}$ is equivalently characterized in terms of Markov chains:

$$ \left\{ \begin{array}{l} Z - U - W_2 \\ Y - (X, S) - W_1 \\ V - (Z, W_2) - U \end{array} \right. . \qquad (V.107) $$

### Coordination under secrecy constraints

In this section we briefly discuss how in the separation setting of Section V.3.c, strong coordination offers additional security guarantees “for free”. In this context, the common randomness is not only useful to coordinate signals and actions of the nodes but plays the role of a secret key shared between the two legitimate users.

To simplify the notation, we do not consider channel state and side information at the decoder. Suppose there is an eavesdropper who observes the signals sent over the channel. We will show that not knowing the common randomness, the eavesdropper cannot infer any information about the actions.

<figure><img src="image_44.png" /><figcaption>Figure V.14 – Wiretap channel: strong coordination implies secrecy.</figcaption></figure>

**Lemma 4** In the setting of Theorem 32, without state and side information at the decoder, suppose that there is an eavesdropper that receives the same sequence $Y^n$ as the decoder but has no knowledge of the common randomness. There exists a sequence $(f_n, g_n)$ of strong coordination codes achieving the pair $(\bar{P}_{UV}\bar{P}_{XY}, R_0) \in \mathcal{R}_{IND}$ such that the induced joint distribution $P_{U^nV^nX^nY^n}^{RC}$ satisfies the strong secrecy condition Bloch and Barros (2011):

$$ \lim_{n \to \infty} \mathbb{D}(P_{U^nV^nY^n}^{RC} \| P_{U^nV^n}^{RC} P_{Y^n}^{RC}) = \lim_{n \to \infty} I(U^nV^n; Y^n) = 0. \qquad (V.108) $$

### V.3.d Is separation optimal?
<figure><img src="image_45.png" /><figcaption>Figure V.15 – Coordination of the actions $U^n$ and $V^n$ for a two-node network with an error-free link of rate $R$.</figcaption></figure>

Strong coordination over error-free channels was investigated in Cuff (2008); Cuff et al. (2010). When extending this analysis to noisy channels, it is natural to ask whether some form of separation theorem holds between coding for coordination and channel coding. In this section, we show that unlike the case of empirical coordination, separation does not hold for strong coordination.

If the separation principle is still valid for strong coordination, by concatenating the strong coordination of the source and its reconstruction with the strong coordination of the input and output of the channel we should retrieve the same mutual information and rate constraints. In order to prove that separation does not hold, first we consider the optimal result for coordination of actions in Cuff (2008); Cuff et al. (2010) and than we compare it with our result on joint coordination of signals and actions. In particular, since we want to compare the result in Cuff (2008); Cuff et al. (2010) with an exact region, we consider the case in which the channel is perfect and the target joint distribution is of the form $\bar{P}_{UV}^{\otimes n} \bar{P}_{X}^{\otimes n}$. The choice of a perfect channel might appear counterintuitive but it is motivated by the fact that we are trying to find a counterexample. As a matter of fact, if the separation principle holds for any noisy link, it should in particular hold for a perfect one.

We start by considering the two-node network with fixed source $\bar{P}_U$ and an error-free link of rate $R$ (Figure V.15). For this setting, Cuff (2008); Cuff et al. (2010) characterize the strong coordination region as

$$ \mathcal{R}_{\text{Cuff}} := \left\{ \begin{array}{l} (\bar{P}_{UWV}, R, R_0)\text{such that} \\ \bar{P}_{UV} = \bar{P}_U \bar{P}_{V|U} \\ \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{UWV} = \bar{P}_U \bar{P}_{W|U} \bar{P}_{V|W} \\ R \ge I(U; W) \\ R + R_0 \ge I(UV; W) \\ |\mathcal{W}| \le |\mathcal{U} \times \mathcal{V}| + 1 \end{array} \right\}. \qquad (\text{V.109}) $$

The result in Cuff (2008); Cuff et al. (2010) characterizes the trade-off between the rate $R_0$ of available common randomness and the required description rate $R$ for simulating a discrete memoryless channel for a fixed input distribution. We compare this region to our results when the requirement to coordinate the signals $X^n$ and $Y^n$ in addition to the actions $U^n$ and $V^n$ is relaxed. We consider, in the simpler scenario with no state and no side information, the intersection $\mathcal{R}_{UV \otimes X} := \mathcal{R}_{PC} \cap \mathcal{R}_{IND}$. The following result characterizes the strong coordination region.

**Proposition 11** Consider the setting of Theorem 28 and suppose that $\bar{P}_{Y|X}(y|x) = 1_{X=Y}\{x = y\}$ and $\bar{P}_{UXV} = \bar{P}_{UV}\bar{P}_X$. Then, the strong coordination region is

$$ \mathcal{R}_{UV \otimes X} := \left\{ \begin{array}{l} (\bar{P}_{UXV}, R_0) \text{ such that:} \\ \bar{P}_{UXV} = \bar{P}_U \bar{P}_{V|U} \bar{P}_X \\ \exists W \text{ taking values in } \mathcal{W} \\ \bar{P}_{UWXV} = \bar{P}_U \bar{P}_{W|U} \bar{P}_{V|W} \bar{P}_X \\ I(W; U) \le H(X) \\ R_0 \ge I(UV; W) \\ |\mathcal{W}| \le |\mathcal{U} \times \mathcal{V}| + 1 \end{array} \right\}. \qquad (\text{V.110}) $$

To compare $\mathcal{R}_{\text{Cuff}}$ and $\mathcal{R}_{UV \otimes X}$, suppose that in the setting of Figure V.15 we use a codebook to send a message to coordinate $U^n$ and $V^n$. In order to do so we introduce an i.i.d. source $X^n$ with distribution
$P_X$ over $\mathcal{X}$ in the model and we use the typical sequences of $X^n$ as a codebook $\mathcal{C}$. Note that the codebook $\mathcal{C}$ can be seen as an optimal channel code for the perfect channel. Hence, asymptotically $R = H(X)$ and we rewrite the information constraints in (V.109) as

$$ 
\begin{aligned}
H(X) &\geq I(U; W), \\
R_0 &\geq I(UV; W) - H(X).
\end{aligned}
$$

This defines a new region:

$$ 
\begin{aligned}
\mathcal{R}_{\text{Cuff},H(X)} &:= \left\{ 
\begin{array}{l}
(\bar{P}_{UXV}, R_0) \text{ such that:} \\
\bar{P}_{UV} = \bar{P}_U \bar{P}_{V|U} \\
X \text{ generated according to } \bar{P}_X \\
\exists W \text{ taking values in } \mathcal{W} \\
\bar{P}_{UWV} = \bar{P}_U \bar{P}_{W|U} \bar{P}_{V|W} \bar{P}_X \\
I(W; U) \leq H(X) \\
R_0 \geq I(UV; W) - H(X) \\
|W| \leq |\mathcal{U} \times \mathcal{V}| + 1
\end{array}
\right\} .
\end{aligned}
\quad (V.111) $$

The distributions $\bar{P}_{UXV}$ in $\mathcal{R}_{\text{Cuff},H(X)}$ coordinate separately $X^n$ and $(U^n, V^n)$. In Cuff (2008) the joint distribution $P_{U^nV^n}$ should be $\varepsilon$-close to the i.i.d. distribution $\bar{P}_{UV}^{\otimes n}$, and we have imposed that $X^n$ is generated according to the uniform distribution.

Observe that, while the information constraint is the same in the two regions (V.110) and (V.111), the rate of common randomness $R_0$ required for the strong coordination region in (V.110) is larger than the rate of common randomness in (V.111). In fact, in the setting of Figure V.15 both $X^n$ and the pair $(U^n, V^n)$ achieve coordination separately (i.e. $P_X^n$ is close to $\bar{P}_X^{\otimes n}$ and $P_{U^nV^n}$ is close to $\bar{P}_{UV}^{\otimes n}$), but there is no extra constraint on the joint distribution $P_{U^nX^nV^n}$. On the other hand, the structure of our setting in (V.110) is different and requires the control of the joint distribution $P_{U^nX^nV^n}$ which has to be $\varepsilon$-close to the i.i.d. distribution $\bar{P}_{UV}^{\otimes n} \bar{P}_X^{\otimes n}$. Since we are imposing a more stringent constraint, it requires more common randomness.

**Remark 29** We found $\mathcal{R}_{UV\otimes X}$ as the intersection of two regions, but we can give it the following interpretation starting from $\mathcal{R}_{\text{Cuff}}$. By identifying $R = H(X)$ in $\mathcal{R}_{\text{Cuff}}$, we find that the rate of common randomness has to be greater than $I(UV; W) - H(X)$. But this is not enough to ensure that $X^n$ is independent of $(U^n, V^n)$. In order to guarantee that, we apply a one-time pad on $X^n$ (which requires an amount of fresh randomness equal to $H(X)$) and we have

$$ R_0 \geq I(UV; W) - H(X) + H(X) = I(UV; W) $$

which is the condition on the rate of common randomness in (V.110).

The following example shows that, unlike the case of empirical coordination (Le Treust, 2017, [J6]), separation does not hold for strong coordination.

**Example 3** The difference in terms of rate of common randomness $R_0$ is better shown in an example: when separately coordinating the two blocks $X^n$ and $(U^n, V^n)$ without imposing a joint behavior $P_{U^nV^nX^n}$, the same bits of common randomness can be reused for both purposes, and the required rate $R_0$ is lower. We consider the case, already analyzed in Cuff (2008, 2013), of a Bernoulli-half source $U$, and $V$ which is an erasure with probability $p_e$ and is equal to $U$ otherwise. In Cuff (2013) the authors prove that the optimal choice for the joint distributed $P_{UWV}$ is the concatenation of two erasure channels $\bar{P}_{W|U}$ and $\bar{P}_{V|W}$ with erasure probability $p_1$ and $p_2$ respectively. Then we have

$$ p_2 \in [0, \min\{1/2; p_e\}], \quad p_1 = 1 - \frac{1 - p_e}{1 - p_2}, $$
<figure><img src="image_46.png" /><figcaption>Figure V.16 – Comparison of the joint coordination region $\mathcal{R}_{UV \otimes X}$ with $\mathcal{R}_{Cuff}$ Cuff (2008, 2013): boundaries of the regions for a binary erasure channel with erasure probability $p_e = 0.75$ and a Bernoulli-half input.</figcaption></figure>

and therefore we obtain

$$ 
\begin{aligned}
I(U; W) &= 1 - p_1, \\
I(UV; W) &= h(p_e) + (1 - p_1)(1 - h(p_2)),
\end{aligned}
$$

where $h$ is the binary entropy function. Figure V.16 shows the boundaries of the regions (V.109) (red) and (V.110) (red) for $p_e = 0.75$ and a Bernoulli-half input. The dotted bound $R \ge I(U; V)$ comes directly from combining $R \ge I(U; W)$ with the Markov chain $U - W - V$. At the other extreme, if $R_0 = 0$ in (V.109), $R + R_0 \ge I(UV; W) \ge C(U; V)$ where $C(U; V) := \min_{U-W-V} I(U, V; W)$ is Wyner's common information Cuff (2008). On the other hand, in our setting (V.110), $R_0 \ge I(UV; W) \ge C(U; V)$ for any value of $R = H(X)$.

Moreover, note that as $R = H(X)$ tends to infinity, there is no constraint on the auxiliary random variable $W$ (aside from the Markov chain $U - W - V$) and similarly to Lapidoth and Wigger (2016) the minimum rate of common randomness $R_0$ needed for strong coordination is Wyner's common information $C(U; V)$. In particular to achieve joint strong coordination of $(U, X, V)$ a positive rate of common randomness is required. The boundaries of the rate regions only coincide on one extreme, and $\mathcal{R}_{UV \otimes X}$ is strictly contained in $\mathcal{R}_{Cuff}$.

## V.4 Chapter summary

In this chapter, we present three research directions that are based on the coordination results of Chap. IV. First, we revisit the problems of state masking of Merhav and Shamai (2007) and state amplification Kim et al. (2008) through the lens of empirical coordination. Second, we extend the coordination result for finite alphabet to the Gaussian case, and we provide fundamental bounds for a long-standing open problem in the control literature, the counterexample of Witsenhausen (1968). Third, we study a finer notion of coordination, namely the strong coordination introduced in Cuff et al. (2010), which builds a bridge with Physical Layer Security problems, see Bloch and Barros (2011).

In the next chapter, we will consider that the encoder and decoder select their coding strategies in a strategic manner, i.e. they optimize their own cost function.
# Chapter VI

## Bayesian persuasion with
restricted communication

<figure><img src="image_47.png" /></figure>

We consider a game of information transmission in which the encoder and the decoder optimize their respective cost functions. As in the Bayesian persuasion model of Kamenica and Gentzkow (2011), we assume that the encoder commits to a strategy and we study the incentive constraints of the decoder. The natural solution concept is the Stackelberg equilibrium in which the encoder is the leader and the decoder is the follower. In the first section, we study the restrictions imposed by the channel on this strategic communication, see also (Le Treust and Tomala, 2019, [J8]), (Le Treust and Tomala, 2016, [IC16]), (Le Treust and Tomala, 2020, [IC26]), (Le Treust and Tomala, 2017, [NC8]). The strategic nature of the problem changes when the decoder privately observes a random variable correlated with the source. This aspect is treated in the second section, that corresponds to (Le Treust and Tomala, 2018b, [IC20]), (Le Treust and Tomala, 2021, [IC28]), (Le Treust and Tomala, 2018a, [W2]), (Le Treust and Tomala, 2019, [W3]). The third section presents Rony Bou Rouphael's PhD contributions on persuasion problems with two decoders via the Gray and Wyner (1974) communication network. These contributions are presented in (Bou Rouphael and Le Treust, 2020, [IC24]), (Bou Rouphael and Le Treust, 2021, [IC28]), (Bou Rouphael and Le Treust, 2022c, [IC31]), (Bou Rouphael and Le Treust, 2022b, [W7]), (Bou Rouphael and Le Treust, 2022a, [NC5]), (Bou Rouphael and Le Treust, 2022d, [W5]).

## Contents

<table><tr><td>VI.1</td><td>Persuasion with limited communication capacity</td><td>83</td></tr><tr><td>VI.1.a</td><td>Bayesian persuasion model</td><td>86</td></tr><tr><td>VI.1.b</td><td>Persuasion model with restricted communication</td><td>87</td></tr><tr><td>VI.1.c</td><td>Results</td><td>90</td></tr><tr><td>VI.1.d</td><td>Convexification with information constraint</td><td>93</td></tr><tr><td>VI.1.e</td><td>Illustrating example</td><td>94</td></tr><tr><td>VI.1.f</td><td>Beyond identical problems</td><td>100</td></tr><tr><td>VI.2</td><td>Persuasion game with side information at the decoder</td><td>101</td></tr><tr><td>VI.2.a</td><td>System model</td><td>102</td></tr><tr><td>VI.2.b</td><td>Convex closure formulation</td><td>104</td></tr><tr><td>VI.2.c</td><td>Doubly symmetric binary source</td><td>106</td></tr><tr><td>VI.3</td><td>Bayesian persuasion with several decoders</td><td>111</td></tr><tr><td>VI.3.a</td><td>System model</td><td>111</td></tr><tr><td>VI.3.b</td><td>Main result</td><td>112</td></tr><tr><td>VI.4</td><td>Chapter summary</td><td>113</td></tr></table>
VI.1 Persuasion with limited communication capacity

In modern internet societies, pieces of information are repeatedly and continuously disclosed to deci-
sion makers by informed agents. Information transmission is affected by at least two sources of friction.
First, the encoder and the decoder of a given signal may have nonaligned incentives, in which case the
encoder might be unwilling to transmit truthful information. Second, communication between agents is
often imperfect. the encoder and the decoder may have time constraints to write or read signals, forcing
the encoder to summarize his arguments and making him unable to convey all the details. Further, there
might be discrepancies between the informational content of a signal that is intended by the encoder
and the one understood by the decoder. For instance, if the mother tongue of the encoder and of the
decoder are different, there are possible translation errors (See Blume et al., 2007). Additionally, signals
travelling in a network of computers might be subject to random shocks, internal errors or protocol fail-
ures. Studying the effect of noise in communication channels is the starting point of Information Theory
(Shannon, 1948).

How does imperfect communication reduce the possibilities of persuasion in a sender-receiver game?
When the encoder communicates many pieces of information, to what extent does tying the pieces together
help in overcoming the communication limitations?

We consider an encoder and a decoder who communicate over an imperfect channel and are engaged in a series of $n \in \mathbb{N}^*$ persuasion problems. the encoder observes $n$ independent and identically distributed pieces of information and sends $k \in \mathbb{N}^*$ signals to the decoder. Messages are sent through a channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{\mathcal{Y}|\mathcal{X}})$ that consists of two finite sets $\mathcal{X}, \mathcal{Y}$ of respectively inputs and outputs signals and of a transition probability $\mathcal{T}_{\mathcal{Y}|\mathcal{X}} \in \Delta(\mathcal{Y})^{|\mathcal{X}|}$ such that when the encoder chooses input symbol $x$, the decoder receives output symbol $y$ with probability $\mathcal{T}_{\mathcal{Y}|\mathcal{X}}(y|x) \in [0, 1]$. Upon receiving $k$ output signals from the channel, the decoder chooses $n$ actions, one for each problem. Cost functions are additively separable across persuasion problems. We assume that the encoder is able to commit to a disclosure strategy that maps sequences of pieces of information to distributions of sequences of input signals.

We study the optimal average cost secured by the encoder by committing to a strategy. We give an upper bound on this optimal cost and show that this bound is achieved asymptotically when the numbers $n$ and $k$ grow large. To prove this latter statement, we borrow techniques from Information Theory, namely, the coding and decoding schemes of Shannon (1948, 1959). This machinery allows to transmit a sequence of signals over a noisy channel with the property that the decoder recovers almost all signals correctly. The information theoretic literature typically considers an obedient decoder who calculates the decoded signals and takes them at face value. In the persuasion game framework, the decoder is strategic and may not follow any prescribed scheme. Rather, the decoder takes into account the strategy of the encoder and the received outputs, calculates its Bayesian belief about the sequence of states, and chooses a sequence of actions that minimizes its cost. Our technical contribution is to construct a strategy of the encoder for which we are able to estimate and to control those Bayesian beliefs in order to ensure that the strategic decoder chooses a desired sequence of actions.

Our upper bound is the value of an *optimal splitting problem with information constraint*, which represents the best cost that the encoder can achieve by sending a signal, subject to the constraint that the mutual information between the state and the signal is no more than the capacity of the channel. We show that this value is given by the convex closure of the cost function of the encoder, subject to a constraint on the entropy of posterior beliefs. This is also given by the convex closure of a modified cost function, where the encoder pays a cost proportional to the mutual information between the state and the signal.

Motivating example.

There are relevant situations where an encoder discloses information about a large number of indepen-
dent state parameters. For instance, one can think of testing product quality: a firm has many items to
sell, which are ex-ante identical, and the authorities (e.g., the FDA for drugs) design quality tests <fnref n="1" />. One
can also think about designing and grading exams to assess the quality of a large number of students<fnref n="2" />.

<footnote n="1">¹See e.g., Perez-Richet and Skreta, 2022.</footnote>

<footnote n="2">²See Boleslavsky and Cotton, 2015 for a model of grading standards through Bayesian persuasion.</footnote>
As an example, consider an innovating firm that has several projects to be financed by investors. The board of investors audits the firm, which is given a limited amount of time to present all the projects. How to best structure arguments in order to get the maximum number of projects approved?

To be specific, let us assume that all projects are ex-ante identical and equally likely to be of good or bad quality. When a project is approved, it yields a cost of −1 to the investors if it is good, and a cost of 7 if it is bad; rejecting a project yields a cost of 0. The objective of the firm is to get a minimum number of projects approved.

Suppose that the firm commits to an information disclosure mechanism, i.e., distributions of signals conditional on states (as in Kamenica and Gentzkow, 2011) and faces no restriction on the number of signals. To invest, the board of investors must be persuaded that the project is good with probability at least 7/8. Thus, for each project, the firm would optimally draw a good signal g or a bad signal b with the following probabilities:

$$ \Pr(g \mid \text{project is good}) = 1, \quad \Pr(g \mid \text{project is bad}) = 1/7. $$

This way, the belief that the project is good upon receiving the good signal is as follows:

$$ \Pr(\text{project is good} \mid g) = 7/8, $$

and the project is accepted with probability 4/7 (see Section VI.1.e).

Now, suppose that the auditing board gives the firm only half the time it would require to talk about all projects. Namely, there is an even number n of projects, but the firm has only n/2 signals available.

A simple strategy the firm can adopt would be to select half of the projects, focus on them, and communicate optimally for each of them. With this strategy, half of the projects are accepted with probability 4/7 each, so in expectation, the average number of accepted projects is 2/7. This is not optimal, and a better strategy would be to pair projects by two and to draw one signal g, b for each pair in the following way:

$$ \Pr(g \mid \text{both projects are good}) = 1, \quad \Pr(g \mid \text{both projects are bad}) = 0, $$

$$ \Pr(g \mid \text{only one project is good}) = 1/6. $$

The total probability of g is 1/3 and upon observing this signal, the beliefs about quality are as follows:

$$ \Pr(\text{both projects are good} \mid g) = 6/8, $$

$$ \Pr(\text{only project 1 is good} \mid g) = \Pr(\text{only project 2 is good} \mid g) = 1/8. $$

Therefore, each project is believed to be good with probability 7/8 and both projects are accepted when g is received. Thus, the expected average number of accepted projects is 1/3 > 2/7.

We thus see that tying projects together improves upon communication about each project separately. Suppose that the number of projects is large. Is it possible to find a more complex strategy that further lowers the cost?

Our main result, Theorem 33, gives an upper bound on the expected average number of accepted projects when the number of signals is half the number of projects. The upper bound is tight: the optimal value approaches it as the number of project increases. In this example, the upper bound is $\lambda^*$ where $(\lambda^*, p^*)$ is the unique solution in $[0, 1] \times [0, \frac{1}{2}]$ of the system of equations:

$$ \frac{1}{2} = \lambda^* \frac{7}{8} + (1 - \lambda^*) p^*, \quad \frac{1}{2} = \lambda^* H\left(\frac{7}{8}\right) + (1 - \lambda^*) H(p^*), $$

where $H(p) = -p \log(p) - (1-p) \log(1-p)$ is the binary entropy function. The first equation is Bayes plausibility (Kamenica and Gentzkow, 2011) coming from Bayes' rule, saying that the expected posterior belief is the prior belief. The second equation requires the expected entropy of the posterior to be $\frac{1}{2}$, which means that the mutual information between the quality of the project and the signal sent to the decoder is equal to the number of signals per project that the firm is able to transmit.

Numerically $\lambda^* \approx 0.519 < \frac{4}{7} \approx 0.571$. Thus, for large n, the expected number of projects is higher than 1/3 but bounded away from the value obtained with unrestricted communication.
Related literature

We now describe the relationships between our contribution and the literature. This work is at the junction of Bayesian persuasion and Information Theory.

The traditional game theoretic approach to strategic information disclosure assumes perfect com-
munication and analyzes in isolation the problem of sending a single signal. These are the well-known
sender-receiver games where an informed player, the encoder, communicates once with a decoder who
takes an action. In the *cheap talk* version of this game, the signal sent by the encoder is costless and
unverifiable; see for instance the seminal paper of Crawford and Sobel (1982). In the *Bayesian persuasion*
game (Kamenica and Gentzkow, 2011), the encoder chooses verifiably an information disclosure device
prior to learning his information. That is, the encoder is an *information designer* (Bergemann and Mor-
ris, 2016, 2017; Taneva, 2019) who chooses, without knowledge of the state, the information or signaling
structure which releases information to the decision maker.

In parallel, Information Theory considers agents with perfectly aligned interests and analyzes the *rate* of information transmission. the encoder observes an information *flow*, which is a stochastic process, and sends signals to the decoder over an imperfect channel represented by a transition probability from input to output signals. Truthful information transmission is the common goal of the encoder and the decoder. The *rate of information transmission* is the average number of correct guesses made by the decoder. Shannon's theory (Shannon, 1948, 1959) determines whether a source of information can be transmitted over the channel with arbitrarily small probability of error and shows that the rate of the source of information has to be smaller than *the capacity of the channel* defined as the maximal *mutual information* between input and output signals.

Our model of persuasion has two essential features. the encoder and the decoder are engaged in a large number of identical copies of the same game and communication is restricted to an imperfect channel. As Kamenica and Gentzkow (2011), we consider the cost obtained by the encoder as a function of the belief of the decoder, when the decoder takes optimal actions. With unrestricted communication, that is on a perfect channel with large set of inputs, the optimal cost for the encoder is given by the convex closure of this function. Then, solving any number of identical games amounts to solving each copy separately. With a single copy, the game of persuasion with a noisy channel is studied by Tsakas and Tsakas (2021) who prove the existence of optimal solutions and show monotonicity of the encoder's cost with respect to the noise of the channel. Considering many copies of the base game and restricted communication, we show that linking independent problems together yields a better cost to the encoder: the optimal strategy correlates all signals with the state parameters of all problems. In this respect, our work bears some similarity with Jackson and Sonnenschein (2007), who showed that a mechanism designer can achieve more outcomes in an incentive compatible manner by linking many identical problems together.

The optimal cost that we characterize is related to models where the cost of information is measured by mutual information. Such information costs have been introduced in the literature on rational inattention by Sims (2003), (See also Martin, 2017; Matejka and McKay, 2015; Steiner et al., 2017). The use of mutual information has been axiomatized in Morris and Strack (2019) and Hebert and Woodford (2018). In the context of persuasion, Gentzkow and Kamenica (2014) consider a model where the encoder gets his cost from the game, minus a cost that is proportional to the mutual information between the state and the signal; see also Matyskova (2018). With Lagrangian methods, we find that the value of our optimal splitting problem with information constraint is the convex closure of the cost function, net of such an information cost, a similar convexification problem is found in Caplin and Dean (2013)

Different from those papers, the mutual information is not a primitive of our model. Our finding is that the noise and limitations in communication induce a *shadow cost* measured by the mutual information. Entropy and mutual information appear endogenously in several papers on repeated games where players have bounded rationality (Neyman and Okada, 1999, 2000), are not able to freely randomize their actions (Gossner and Vieille, 2002), or observe actions imperfectly (Gossner and Tomala, 2006, 2007). A related paper is Gossner et al. (2006), henceforth GHN, who also consider a sender-receiver game. In GHN, the encoder and the decoder play an infinitely repeated game with common interests: both the encoder and the decoder want to choose the action that matches the state. the encoder knows the infinite sequence of states and can communicate with the decoder only through his actions. GHN characterize the best average cost that the encoder (and the decoder) can achieve. Their solution resembles ours: the optimal value is the cost obtained when the encoder can send a direct signal to the decoder, subject to an
information constraint.

VI.1.a Bayesian persuasion model

In this section, we briefly present the Bayesian persuasion model of Kamenica and Gentzkow (2011), depicted on Fig. VI.1. The encoder and the decoder are endowed with distinct costs functions $c_e: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ and $c_d: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$. The main difference with the Information-Theoretic models of Chap. III is that:

1. the perfect channel has a large cardinality $|\mathcal{X}| \ge |\mathcal{U}|$,

2. the sequences of symbols have length $n = 1$.

<figure><img src="image_48.png" /><figcaption>Figure VI.1 – Bayesian persuasion model</figcaption></figure>

The encoding and decoding functions are defined by

$$ \sigma: \mathcal{U} \to \Delta(\mathcal{X}), \quad \tau: \mathcal{X} \to \Delta(\mathcal{V}), \qquad (VI.1) $$

and induce a probability distribution given by

$$ \Pr((U, X, V) = (u, x, v)) = \mathcal{P}_U(u)\sigma(x|u)\tau(v|x), \quad \forall (u, x, v). \qquad (VI.2) $$

Given an encoder strategy $\sigma$, we define the set of decoder best responses by

$$ \mathrm{BR}(\sigma) = \underset{\tau}{\operatorname{argmin}} \mathbb{E}[c_d(U, V)]. \qquad (VI.3) $$

If the set $\mathrm{BR}(\sigma)$ contains several strategies, we assume that the decoder selects the worst one for the encoder cost function. Note that in case of indifference in the model of Kamenica and Gentzkow (2011), the decoder selects the best response strategy $\tau \in \mathrm{BR}(\sigma)$ that also minimizes the encoder cost function.

**Definition 41** The robust Bayesian persuasion problem writes

$$ C_e^* = \inf_{\sigma} \max_{\tau \in \mathrm{BR}(\sigma)} \mathbb{E}[c_e(U, V)]. \qquad (VI.4) $$

In this strategic communication scenario, the encoder commits to implementing the strategy $\sigma$, by anticipating that the decoder selects a best response $\tau \in \mathrm{BR}(\sigma)$.

**Definition 42** Given the source probability distribution $p \in \Delta(\mathcal{U})$, the decoder selects a best response action $v$ in

$$ \mathcal{V}^*(p) = \underset{v \in \mathcal{V}}{\operatorname{argmin}} \mathbb{E}_p[c_d(U, v)]. \qquad (VI.5) $$

Given $p \in \Delta(\mathcal{U})$, we define the robust cost function by

$$ \psi_e(p) = \max_{v \in \mathcal{V}^*(p)} \mathbb{E}_p[c_e(U, v)]. \qquad (VI.6) $$

The next results is a reformulation of (Kamenica and Gentzkow, 2011, Prop. 1), where $\mathrm{vex} f: \Delta(\mathcal{U}) \to \mathbb{R} \cup \{-\infty\}$ denotes the convex closure of a function $f$, i.e. the largest convex function everywhere smaller than $f$ on $\Delta(\mathcal{U})$.
**Proposition 12** If $|\mathcal{X}| \ge |\mathcal{U}|$, we have

$$C_e^* = \mathrm{vex} \psi_e(\mathcal{P}_U). \qquad (\mathrm{VI}.7)$$

*Proof.* [Prop. 12] The main argument comes from the splitting lemma of Aumann and Maschler (1995), also referred to as Bayes plausibility in Kamenica and Gentzkow (2011). We recall the definition of convex closure,

$$\mathrm{vex} \psi_e(\mathcal{P}_U) = \inf \left\{ \sum_{x \in \mathcal{X}} \lambda_x \psi_e(p_x), \quad \sum_{x \in \mathcal{X}} \lambda_x p_x = \mathcal{P}_U \right\}, \qquad (\mathrm{VI}.8)$$

where the infimum is taken over the parameters $(\lambda_x, p_x)_{x \in \mathcal{X}}$ with $|\mathcal{X}| = |\mathcal{U}|$, such that for each $x \in \mathcal{X}$, $p_x \in \Delta(\mathcal{U})$, $\lambda_x \in [0, 1]$, and $\sum_{x \in \mathcal{X}} \lambda_x = 1$.

Given an encoder strategy $\sigma$, we define for all $x \in \mathcal{X}$,

$$\lambda_x = \sum_{u \in \mathcal{U}} \mathcal{P}_U(u) \sigma(x|u), \qquad (\mathrm{VI}.9)$$

$$p_x(u) = \frac{\mathcal{P}_U(u)\sigma(x|u)}{\sum_{u' \in \mathcal{U}} \mathcal{P}_U(u')\sigma(x|u')}, \quad \forall u \in \mathcal{U}. \qquad (\mathrm{VI}.10)$$

This implies that $\lambda_x p_x(u) = \mathcal{P}_U(u)\sigma(x|u)$ for all $(u, x) \in \mathcal{U} \times \mathcal{X}$, and thus

$$\min_{\tau} \mathbb{E}[c_d(U, V)] = \min_{\tau} \sum_{u,x,v} \mathcal{P}_U(u)\sigma(x|u)\tau(v|x)c_e(u, v) \qquad (\mathrm{VI}.11)$$

$$= \min_{\tau} \sum_{u,x,v} \lambda_x p_x(u) \tau(v|x) c_e(u, v) \qquad (\mathrm{VI}.12)$$

$$= \sum_x \lambda_x \min_v \sum_u p_x(u) c_e(u, v) \qquad (\mathrm{VI}.13)$$

$$= \sum_x \lambda_x \min_v \mathbb{E}_{p_x} [c_e(U, v)]. \qquad (\mathrm{VI}.14)$$

BY using similar arguments, we have

$$\max_{\tau \in \mathrm{BR}(\sigma)} \mathbb{E}[c_e(U, V)] = \sum_x \lambda_x \max_{v \in \mathrm{argmin}_{\mathbb{E}_{p_x}[c_d(U, v)]}} \mathbb{E}_{p_x}[c_e(U, v)] = \sum_{x \in \mathcal{X}} \lambda_x \psi_e(p_x), \qquad (\mathrm{VI}.15)$$

and thus $C_e^* \ge \mathrm{vex} \psi_e(\mathcal{P}_U)$.

Given the parameters $(\lambda_x, p_x)_{x \in \mathcal{X}}$, we define the encoder strategy by

$$\sigma(x|u) = \frac{\lambda_x p_x(u)}{\sum_{u'} \lambda_x p_x(u')}, \qquad (\mathrm{VI}.16)$$

for which (VI.15) is also satisfied. Then, we obtain $C_e^* \le \mathrm{vex} \psi_e(\mathcal{P}_U)$. □

## VI.1.b Persuasion model with restricted communication

We consider an encoder and a decoder engaged in a series of identical persuasion problems and where the communication technology is fixed exogenously, depicted in Fig. VI.2. More specifically, we consider a fixed communication channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|\mathcal{X}})$, where $\mathcal{X}, \mathcal{Y}$ are finite sets of signals and $\mathcal{T}_{Y|\mathcal{X}} \in \Delta(\mathcal{Y})^{|\mathcal{X}|}$ is a transition probability from $\mathcal{X}$ to $\mathcal{Y}$.

Given two integers $n, k$, we define a repeated persuasion problem where the uncertainty is about a sequence $u^n = (u_1, \dots, u_n)$ drawn i.i.d. from $\mathcal{P}_U \in \Delta(\mathcal{U})$. The decoder chooses a sequence of actions $v^n = (v_1, \dots, v_n)$ and the cost for player $i = e, d$ is as follows:

$$\bar{c}_i(u^n, v^n) = \frac{1}{n} \sum_{t=1}^{n} c_i(u_t, v_t).$$
<figure><img src="image_49.png" /><figcaption>Figure VI.2 – Repeated persuasion problem via a noisy channel ($\mathcal{X}$, $\mathcal{Y}$, $\mathcal{T}_{Y|X}$).</figcaption></figure>

To disclose information, the encoder can use the channel $k$ times by choosing a sequence of input signals $x^k = (x_1, \dots, x_k)$. The channel then draws a sequence of output signals $y^k$ with probability $\mathcal{T}_{Y|X}^k(y^k|x^k) = \prod_{t=1}^k \mathcal{T}_{Y|X}(y_t|x_t)$ and sends it to the decoder. This defines the following persuasion game $\Gamma(n, k)$:

1. The encoder chooses a strategy $\sigma: \mathcal{U}^n \to \Delta(\mathcal{X}^k)$ which is announced to the decoder.

2. A sequence of states $u^n$ is drawn i.i.d. from the prior $\mathcal{P}_U$, a sequence of input signals $x^k$ is drawn with probability $\sigma(x^k|u^n)$, a sequence of output signals $y^k$ is drawn with probability $\mathcal{T}_{Y|X}^k(y^k|x^k)$ and is observed by the decoder.

3. the decoder chooses a sequence of actions $v^n$.

Then, player $i = e, d$ gets the average cost $\bar{c}_i(u^n, v^n)$.

Notice that for $n = k = 1$, this is the model of Tsakas and Tsakas (2021) of a single persuasion problem with noisy communication. An interesting particular case is given by perfect channels where $\mathcal{X} = \mathcal{Y}$ and $\mathcal{T}_{Y|X}(y|x) = \mathbb{1}_{\{y=x\}}$ for all $(x, y)$. In such a case, the only limitation is given by the number of signals. If we let $n = k = 1$ and choose a perfect channel with sufficiently many signals $|\mathcal{X}| = |\mathcal{Y}| \ge |\mathcal{U}|$, the model encompasses the standard persuasion game of Kamenica and Gentzkow (2011).

## Optimal robust cost

As a solution concept, we study the best cost the encoder can secure, regardless of which best reply is chosen by the decoder. A strategy of the decoder is a mapping $\tau: \mathcal{Y}^k \to \mathcal{V}^n$. Knowing $\sigma$, the decoder chooses a best reply $\tau$, which minimizes the expected cost. That is, for each $y^k$:

$$ \tau(y^k) \in \underset{v^n \in \mathcal{V}^n}{\operatorname{argmin}} \sum_{u^n, x^k} \mathcal{P}_U^n(u^n) \sigma(x^k|u^n) \mathcal{T}_{Y|X}^k(y^k|x^k) \bar{c}_d(u^n, v^n). $$

Denote $BR_d(\sigma)$ the set of best replies of the decoder to the strategy $\sigma$.

**Definition 43** The optimal robust cost of the encoder in this problem is as follows:

$$ C_e^{n,k}(\mathcal{P}_U, \mathcal{T}_{Y|X}) = \inf_{\sigma} \max_{\tau \in BR_d(\sigma)} \sum_{u^n, x^k, y^k} \mathcal{P}_U^n(u^n) \sigma(x^k|u^n) \mathcal{T}_{Y|X}^k(y^k|x^k) \bar{c}_e(u^n, \tau(y^k)). $$

This definition differs from the conventional solution to Bayesian persuasion of Kamenica and Gentzkow (2011) where the decoder takes the best reply which is preferred by the encoder. Our choice is motivated by robustness; we ask the solution to be robust to the way the decoder breaks ties<fnref n="3" />. We stress that this choice does not matter for generic problems. Indeed, with slight perturbations of the cost function of the decoder, we can make sure that indifferences occur only at interior beliefs. When this is the case, the encoder can slightly change his strategy in order to avoid the indifference region.

The goal is to give an upper bound for the optimal robust cost and to characterize its limit when $n$ and $k$ tend to infinity.

<footnote n="3">³A similar approach is followed by Inostroza and Pavan (2021) and Mathevet et al. (2020).</footnote>
Optimal splitting problem with information constraint

To state our main results, we introduce some definitions.

**Definition 44** A splitting of $\mathcal{P}_U \in \Delta(\mathcal{U})$ is a finite family $(\lambda_w, \nu_w)_{w \in \mathcal{W}}$, where for each $w \in \mathcal{W}$, $\nu_w \in \Delta(\mathcal{U})$, $\lambda_w \in [0, 1]$, $\sum_w \lambda_w = 1$ such that:

$$ \mathcal{P}_U = \sum_w \lambda_w \nu_w. \qquad (VI.17) $$

A splitting of $\mathcal{P}_U$ is a distribution of posterior beliefs whose average equals the prior. An “information structure” which draws a signal $w$ with probability $\text{Pr}(w|u)$ in state $u$, induces a splitting $(\lambda_w, \nu_w)_w$ with $\lambda_w = \sum_{u'} \mathcal{P}_U(u')\text{Pr}(w|u')$ and $\nu_w(u) = \frac{\mathcal{P}_U(u)\text{Pr}(w|u)}{\sum_{u'} \mathcal{P}_U(u')\text{Pr}(w|u')}$.

For each posterior belief $\nu \in \Delta(\mathcal{U})$, let the set of optimal actions of the decoder be:

$$ \mathcal{V}^*(\nu) = \underset{v \in \mathcal{V}}{\operatorname{argmin}} \sum_u \nu(u)c_d(u, v). $$

We denote by $c_e^*(\nu) = \min_{v \in \mathcal{V}^*(\nu)} \sum_u \nu(u)c_e(u, v)$ the robust cost of the encoder at the belief $\nu \in \Delta(\mathcal{U})$, i.e., the cost of the encoder when the decoder chooses the optimal action, which is worst for the encoder.

We now introduce tools borrowed from Information Theory; the reader is referred to Cover and Thomas (2006).

**Definition 45** 1. The (Shannon) entropy of a probability distribution $q \in \Delta(S)$ over a finite set $S$ is as follows:

$$ H(q) = - \sum_{s \in S} q(s) \log q(s), $$

where the logarithm has basis 2 and $0 \log 0 = 0$.

2. Given a distribution $p_X \in \Delta(\mathcal{X})$, the mutual information between two random variables $(X, Y)$, drawn from the joint probability distribution $p_X T_{Y|X} \in \Delta(\mathcal{X} \times \mathcal{Y})$ is as follows:

$$ I(X; Y) = H\left(\sum_x p_X(x) T_{Y|X}(\cdot|x)\right) - \sum_x p_X(x) H(T_{Y|X}(\cdot|x)) = H(Y) - H(Y|X). $$

3. The capacity of the channel $(X, Y, T_{Y|X})$ is defined by:

$$ C(T_{Y|X}) = \max_{p_X \in \Delta(\mathcal{X})} I(X; Y). $$

The channel capacity $C(T_{Y|X})$ is the minimal mutual information between two random variables $(X, Y)$, respectively the input and output of the channel, drawn from the joint probability distribution $p_X(x)T_{Y|X}(y|x)$, where the minimum is over the marginal distribution $p_X(x)$. Intuitively, this is the minimal number of bits of information that can be transmitted reliably through the channel (see Cover and Thomas, 2006).

Equipped with these tools, our main definition is the following.

**Definition 46** For any $C \ge 0$, the optimal splitting problem with information constraint is:

$$ \begin{align*} C_e^*(\mathcal{P}_U, C) &= \inf \sum_w \lambda_w c_e^*(\nu_w) \\ \text{s.t.} \quad & \sum_w \lambda_w \nu_w = \mathcal{P}_U, \\ \text{and} \quad & H(U) - \sum_w \lambda_w H(\nu_w) \le C. \end{align*} $$
This is the best cost that the encoder can secure by choosing a splitting of the prior belief (i.e., an information structure) under the constraint that the expected reduction of entropy does not exceed the capacity C of the channel. The entropy reduction $H(U) - \sum_w \lambda_w H(\nu_w) = H(U) - H(U|W)$ is nonnegative. It is equal to the mutual information $I(U; W)$ between a random state U and a random signal W, drawn from the joint distribution $(\lambda_w \nu_w(u))_{(u,w)}$, see Prop. 2. The interpretation is thus that the encoder optimizes over a set of information structures that convey bounded information about the state.

Notice that $C_e^*(P_U, C)$ is greater than or equal to the convex closure (or convexification) of $c_e^*$ at $P_U$ which is the unconstrained infimum $\inf \{ \sum_w \lambda_w c_e^*(\nu_w) : \sum_w \lambda_w \nu_w = P_U \}$.

VI.1.c Results

The main result shows that the value of the optimal splitting problem with information constraint provides an upper bound to the optimal robust cost and that the bound is achieved asymptotically.

**Theorem 33** 1. The optimal robust cost of the encoder is no more than the value of the optimal splitting problem with information constraint. For each pair of integers n, k:

$$C_e^{n,k}(P_U, \mathcal{T}_{Y|X}) \le C_e^*(P_U, \frac{k}{n}\mathcal{C}(\mathcal{T}_{Y|X})).$$

2. The optimal robust cost of the encoder converges to the value of the optimal splitting problem with information constraint in the following sense. For each $r \in [0, +\infty]$, for each pair of sequences of integers $(k_j, n_j)_{j \in \mathbb{N}^*}$ such that $\lim_{j \to \infty} \min(n_j, k_j) = \infty$ and $\lim_{j \to \infty} \frac{k_j}{n_j} = r$, we have:

$$\lim_{j \to \infty} C_e^{n_j, k_j}(P_U, \mathcal{T}_{Y|X}) = C_e^*(P_U, r\mathcal{C}(\mathcal{T}_{Y|X})).$$

The proof of Theorem 33 is stated in (Le Treust and Tomala, 2019, [J8]). On the one hand, this result shows communication restrictions limits the cost that can be achieved through Bayesian persuasion. On the other hand, it quantifies the extent to which repeating the same problem and linking the copies together helps in overcoming those restrictions.

**Sketch of proof**

We give an intuition for the main arguments of the proof; the technical details are in the appendix.

**First point, upper bound.** The argument is that regardless of which strategies are used, the mutual information between the states and the signals to the decoder cannot exceed the capacity of the channel.

For simplicity, consider the case $n = k = 1$ where the result says $C_e^{1,1}(P_U, \mathcal{T}_{Y|X}) \le C_e^*(P_U, C(\mathcal{T}_{Y|X}))$. Take any strategy $\sigma$ of the encoder. This induces the splitting $P_U = \sum_y \Pr_\sigma(y)\nu_y$ where $\Pr_\sigma(y) = \sum_{u,x} P_U(u)\sigma(x|u)\mathcal{T}_{Y|X}(y|x)$ is the probability of the signal y and

$$\nu_y(u) = \Pr_\sigma(u|y) = \frac{\sum_x P_U(u)\sigma(x|u)\mathcal{T}_{Y|X}(y|x)}{\Pr_\sigma(y)}$$

is the posterior belief conditional on y. The mutual information of this splitting is:

$$H(U) - \sum_y \Pr_\sigma(y)H(\nu_y) := I(U; Y)$$

where $(U, X, Y)$ denotes a random triple of state, input and output signals drawn from the joint distribution $P_U(u)\sigma(x|u)\mathcal{T}_{Y|X}(y|x)$. With an abuse of notation, we denote $I(U; Y)$ the mutual information between U and Y without explicit reference to the distribution.

Since X is a sufficient statistic for Y, X is more informative<fnref n="4" /> about Y than U, that is $I(U; Y) \le I(X; Y)$. Then, the mutual information between the input and the output is no more than $C(\mathcal{T}_{Y|X})$ from the definition of the channel capacity.

<footnote n="4">⁴See Cover and Thomas, 2006, Theorem 2.8.1, p. 34.</footnote>
The proof for general $n$ and $k$ is an elaboration of this argument. Since states are i.i.d., we can prove that for any strategy, the average cost is the one induced by some splitting whose mutual information is no more than $\frac{k}{n}C(\mathcal{T}_{Y|X})$. The trick is to introduce an auxiliary random variable $T$ uniformly distributed over $\{1, \dots, n\}$ and known by the decoder. Then, we regard the average cost over stages $1, \dots, n$ as the expected cost for the randomly selected stage.

**Second point, asymptotic construction.** To make the intuition simple, let us consider a sequence of pairs of integers $(k_j, n_j)_{j \in \mathbb{N}^*}$ such that $k_j = n_j$ and let $k = n$ be a large term of this sequence. Take a splitting $(\lambda_w, \nu_w)_w$ of the prior $\mathcal{P}_U$ which satisfies the information constraint. We want to show that for large $n$, there is a strategy $\sigma$ of the encoder such that for any best reply $\tau \in BR_d(\sigma)$ of the decoder, the cost of the encoder is at least about $\sum_w \lambda_w c_e^*(\nu_w)$. Let also $v_w^* \in \mathcal{V}^*(\nu_w)$ such that $c_e^*(\nu_w) = \sum_u \nu_w(u)c_e(u, v_w^*)$.

A first intuition for the construction is as follows. From Shannon's coding Theorem<fnref n="5" />, if $I(U; W) < C(\mathcal{T}_{Y|X})$, then for large $n$, there exists functions $f_1: \mathcal{U}^n \to \mathcal{W}^n$, $f_2: \mathcal{W}^n \to X^n$ and $g: \mathcal{Y}^n \to \mathcal{W}^n$, altogether a coding/decoding scheme, with the following properties. Given a sequence of states $u^n$, the encoder calculates a sequence of signals $w^n = f_1(u^n)$ such that with probability close to one, the empirical frequency of the $(u_t, m_t)$'s is approximately the theoretical one $\lambda_w \nu_w(u)$. The encoder then calculates a sequence of inputs $x^n = f_2(m^n)$ and sends them into the channel. If the decoder calculates $\hat{m}^n = g(y^n)$, then the signals are recovered with probability close to one: $\Pr(m^n = \hat{m}^n) \approx 1$.

This argument is standard in Information Theory but is not sufficient for proving our result. The proof is actually more complicated because the strategic decoder actually calculates the Bayesian posterior $\Pr(u^n|y^n)$ and chooses at stage $t$ an action $v_t \in \mathcal{V}^*(\Pr(u_t|y^n))$. Thus, the main task is to refine the construction in such a way that for any best reply of the decoder, with probability close to one, the optimal action $v_t \in \mathcal{V}^*(\Pr(u_t|y^n))$ is equal to the recommended action $v_{\hat{m}_t}^*$ at most stages, that is, for a set of stages whose proportion is close to one. This implies that the cost is approximately the target one.

The proof consists of three main steps. In the first step, we show that for each $\varepsilon > 0$, we can find a splitting $\varepsilon$-optimal for $C_e^*(\mathcal{P}_U, \mathcal{C})$, which satisfies the information constraint with strict inequality and such that for each posterior $\nu_w$, the action $v_w^*$ which minimizes the encoder cost over $\mathcal{V}^*(\nu_w)$ is unique in a neighborhood of $\nu_w$. This latter property ensures that the decoder plays $v_w^*$ whenever its belief is close to $\nu_w$. We deduce that the difference between the realized cost and the target cost is bounded by the number of times $t$ where the Bayesian posterior $\Pr(u_t|y^n)$ is far away from $\nu_{\hat{m}_t}$. The goal is then to show that this number is small with probability close to one.

The second step consists in defining Shannon's strategy for this splitting. There, we adapt known construction from Information Theory to our setting.

At the third step, we prove that, under our construction, with probability close to one, the Bayesian posteriors $\Pr(u_t|y^n)$ are close enough to the target posteriors $\nu_{\hat{m}_t}$ at most stages. This allows us to conclude that with probability close to one, the decoder plays the recommended actions at most stages and that the expected cost is close to the target one. This step, where we estimate the realized Bayesian beliefs, is new compared to the information theoretic literature, which typically focuses on the average number of mistakes in decoding. Summing up, our construction is similar to the ones found in this literature but is adapted to the context where the decoder is minimizing its cost. $\square$

We now provide some direct implications of the theorem.

**Large capacity.** Reordering the information constraint as $\sum_w \lambda_w H(\nu_w) \ge H(U) - \mathcal{C}$, we see that if $\mathcal{C} \ge H(U)$, the constraint is satisfied by all splittings. The value of the problem is thus the unconstrained convexification of $c_e^*$:

$$ \mathcal{C} \ge H(U) \implies C_e^*(\mathcal{P}_U, \mathcal{C}) = \mathrm{vex} c_e^*(\mathcal{P}_U). $$

As a consequence, if we fix $n$ and $\mathcal{T}_{Y|X}$ and choose $k$ large enough such that $\frac{k}{n}C(\mathcal{T}_{Y|X}) \ge H(U)$, then the encoder can achieve approximately the unconstrained minimum $\mathrm{vex} c_e^*(\mathcal{P}_U)$.

The intuition is simple: for fixed size of the state space $\mathcal{U}$, if the imperfect channel can be used a large number of times, then the encoder is able to convey the state $u \in \mathcal{U}$ with arbitrarily high probability.

<footnote n="5">⁵See Cover and Thomas, 2006, Theorem 10.4.1, p. 318.</footnote>
More precisely, suppose $C(\mathcal{T}_{Y|X}) > 0$ that is to say, $\mathcal{T}_{Y|X}(\cdot|x)$ is not constant with respect to $x$. There exist distributions of inputs $p_X^u \in \Delta(X)$ for $u \in \mathcal{U}$, that statistically identify the state:

$$u \neq u' \implies \sum_x p_X^u(x) \mathcal{T}_{Y|X}(\cdot|x) \neq \sum_x p_X^{u'}(x) \mathcal{T}_{Y|X}(\cdot|x).$$

For each state $u \in \mathcal{U}$, the encoder can draw an i.i.d. sequence of signals $x_1, \dots, x_k$ from $p_X^u$ and sends them through the channel. The posterior belief of the decoder conditional on $y_1, \dots, y_k$ then converges to the truth (the Dirac mass on $u$). Thus, asymptotically, the distributions of actions of the decoder will be close to the one under perfect communication.

**Small capacity.** When $C$ is close to 0, the information constraint $H(U) - \sum_w \lambda_w H(\nu_w) \le C$ implies that the splitting is almost nonrevealing since:$^6$

$$\sum_w \lambda_w \|\nu_w - \mathcal{P}_U\|_1 \le \sqrt{2 \ln 2 (H(U) - \sum_w \lambda_w H(\nu_w))}.$$

It follows that $C_e^*(\mathcal{P}_U, C)$ is approximately $c_e^*(\mathcal{P}_U)$, the cost obtained without any information transmission.

As a consequence, if we fix $\mathcal{T}_{Y|X}$ and $k$, then for large $n$, the encoder cannot get substantially more than $c_e^*(\mathcal{P}_U)$.

**Perfect channels.** Our result applies to communication channels without noise. A communication channel has two sources of imperfection: the noise and the number of available signals, which is given exogenously. One insight of our work is that all that matters for the analysis is the capacity of the channel.

A channel $(X, Y, \mathcal{T}_{Y|X})$ is called perfect if $\mathcal{X} = \mathcal{Y}$ and $\mathcal{T}_{Y|X}(y|x) = \mathbb{1}_{\{x=y\}}$. For each integer $|\mathcal{X}| \ge 2$, we denote $\mathcal{T}_{|\mathcal{X}|}^*$ the perfect communication channel with $|\mathcal{X}|$ signals where $|\mathcal{X}| = |\mathcal{Y}|$. Its capacity is$^7$ $C(\mathcal{T}_{|\mathcal{X}|}^*) = \log |\mathcal{X}|$. We apply our results to the optimal robust cost $C_e^{n,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}|}^*)$ of the game where the persuasion problem is repeated $n$ times and where the encoder can send one signal from a set with cardinality $|\mathcal{X}|$. Our method applies since for large $|\mathcal{X}|$, the channel $\mathcal{T}_{|\mathcal{X}|}^*$ can be seen as having the use of a binary perfect channel $k$ times, with $k = \log_2 |\mathcal{X}|$.

There are two simple extreme cases. First, if $|\mathcal{X}| = 1$, the capacity of the channel is 0 and the encoder cannot convey any information. Thus, $C_e^{n,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}|}^*) = C_e^*(\mathcal{P}_U, 0) = c_e^*(\mathcal{P}_U)$. Second, if $|\mathcal{X}| \ge |\mathcal{U}|^n$, then the encoder can secure the unconstrained persuasion cost $C_e^{n,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}|}^*) = C_e^*(\mathcal{P}_U, \log |\mathcal{U}|) = \text{vex } c_e^*(\mathcal{P}_U)$ by treating each of the $n$ problems separately and getting the cost $\text{vex } c_e^*(\mathcal{P}_U)$ for each instance. The first point of Theorem 33 shows that this is the best possible cost.

More generally, Theorem 33 implies the following.

**Corollary 5** Consider a persuasion problem repeated $n$ times, where the encoder sends one signal from a set of cardinality $|\mathcal{X}|$. Then:

1. $C_e^{n,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}|}^*) \le C_e^*(\mathcal{P}_U, \frac{\log |\mathcal{X}|}{n})$, for all $n \in \mathbb{N}^*$.

2. For any pair of sequences of integers $(|\mathcal{X}_j|, n_j)_{j \in \mathbb{N}^*}$ such that $\lim_{j \to \infty} \min(|\mathcal{X}_j|, n_j) = \infty$ and

$$\lim_{j \to \infty} \frac{\log |\mathcal{X}_j|}{n_j} = C, \text{ we have } \lim_{j \to \infty} C_e^{n_j,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}_j|}^*) = C_e^*(\mathcal{P}_U, C).$$

*Proof.* The first point follows directly from Theorem 33. To see the second point, it is enough to remark that a perfect channel $\mathcal{T}_{|\mathcal{X}|}^*$ is “close” to $k$ copies of a perfect binary channel $\mathcal{T}_2^*$ with $k$ such that $2^k \le |\mathcal{X}| < 2^{k+1}$, that is $k = \lfloor \log |\mathcal{X}| \rfloor$. Having more signals at disposal is beneficial for the encoder and thus $C_e^{n,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}|}^*)$ is weakly increasing with $|\mathcal{X}|$. It follows that:

$$C_e^{n,k}(\mathcal{P}_U, \mathcal{T}_2^*) \le C_e^{n,1}(\mathcal{P}_U, \mathcal{T}_{|\mathcal{X}|}^*) \le C_e^{n,k+1}(\mathcal{P}_U, \mathcal{T}_2^*)).$$

<footnote>$^6$See Cover and Thomas, 2006, Lemma 11.6.1, p. 370.</footnote>

<footnote>$^7$See Cover and Thomas, 2006, p. 184.</footnote>
Take a sequence $(m_j, n_j)_{j \in \mathbb{N}^*}$ such that $\lim_{j \to \infty} \min(m_j, n_j) = \infty$ and $\lim_{j \to \infty} \frac{\log |\mathcal{X}_j|}{n_j} = \mathcal{C}$, and define $k_j = [\log |\mathcal{X}_j|]$. We have $\lim_{j \to \infty} \min(k_j, n_j) = \infty$, $\lim_{j \to \infty} \frac{k_j}{n_j} = \mathcal{C}$ and the conclusion follows from Theorem 33. □

VI.1.d Convexification with information constraint

In this section, we give some properties of the optimal splitting problem under information constraint. The motivation for this part of the results is two-fold. First, it is known than in a convexification problem, the number of posteriors (or of signals) can be chosen less than or equal to the number of states. One might wonder whether this remains true when there is a constraint on the feasible splittings. Second, models with costly information often use the mutual information as information cost (see e.g. Sims, 2003). We will see that in our case, this is derived by writing a Lagrangian for $C_e^*(\mathcal{P}_U, \mathcal{C})$.

Consider the optimal splitting under information constraint:

$$ \inf \left\{ \sum_w \lambda_w c_e^*(\nu_w) : \sum_w \lambda_w \nu_w = \mathcal{P}_U, \sum_w \lambda_w H(\nu_w) \ge H(U) - \mathcal{C} \right\}. $$

This is a special instance of the following optimization problem. Let $f, g: S \to \mathbb{R} \cup \{-\infty\}$ be two functions defined on a convex set $S \subseteq \mathbb{R}^d$, where $S$ represents an abstract set of posteriors, $f$ is a cost function and $g$ is a constraint capturing the feasible splittings. For $s \in S$ and $\gamma \in \mathbb{R}$ consider the problem:

$$ F^g(s, \gamma) := \inf \left\{ \sum_w \lambda_w f(s_w) : \sum_w \lambda_w s_w = s, \sum_w \lambda_w g(s_w) \ge \gamma \right\}. $$

Let $f^g: S \times \mathbb{R} \to \mathbb{R} \cup \{+\infty\}$ defined by:

$$ f^g(s, \gamma) = \begin{cases} f(s) & \text{if } \gamma \le g(s), \\ +\infty & \text{otherwise.} \end{cases} $$

**Theorem 34** Then, for each $(s, \gamma) \in S \times \mathbb{R}$,

$$ 1. F^g(s, \gamma) = \text{vex} f^g(s, \gamma). $$

$$ 2. F^g(s, \gamma) = \sup_{t \ge 0} \left\{ \text{vex}(f + tg)(s) - t\gamma \right\}. $$

The proof of Theorem 34 is stated in (Le Treust and Tomala, 2019, [J8]). Applying this result to the optimal splitting under information constraint, we get:

**Corollary 6** For each $\mathcal{P}_U \in \Delta(\mathcal{U})$ and $C \ge 0$,

1. $C_e^*(\mathcal{P}_U, \mathcal{C})$ is the convexification of the function $c_e^H: \Delta(\mathcal{U}) \times \mathbb{R} \to \mathbb{R}$ defined as:

$$ c_e^H(\nu, \eta) = \begin{cases} c_e^*(\nu) & \text{if } \eta \le H(\nu), \\ +\infty & \text{otherwise,} \end{cases} $$

$$ \text{calculated at } (\nu, \eta) = (\mathcal{P}_U, H(U) - \mathcal{C}). $$

$$ 2. C_e^*(\mathcal{P}_U, \mathcal{C}) = \sup_{t \ge 0} \left\{ \text{vex}(c_e^* + tH)(\mathcal{P}_U) - t(H(U) - \mathcal{C}) \right\}. $$

Since it might be useful in other contexts, Theorem 34 is stated for general functions rather than specifically for the entropy function. This result has recently been generalized by Doval and Skreta (2018) to splitting problems with several constraints. The first point of the theorem states that the convexification with constraint, is the convexification of a bivariate function where an additional variable is added for the constraint (many variables when there are many constraints, see Doval and Skreta, 2018). The second point states that a Lagrangian function can be introduced and that the convexification under constraint is the convexification of the Lagrangian for some multiplier. The proof is in (Le Treust and Tomala, 2019, [J8], Appendix).
A direct implication of the second point of Corollary 6 is that there exists $t^* = t^*(\mathcal{P}_U, \mathcal{C})$ such that:

$$C_e^*(\mathcal{P}_U, \mathcal{C}) = \mathrm{vex}(c_e^* + t^*H)(\mathcal{P}_U) - t^*(H(U) - \mathcal{C}).$$

To see the existence of $t^*$, notice that $\mathrm{vex}(c_e^* + t^*H)(\mathcal{P}_U) - t(H(U) - \mathcal{C}) \ge (c_e^* + t^*H)(\mathcal{P}_U) - t(H(U) - \mathcal{C}) = c_e^*(\mathcal{P}_U) + t\mathcal{C}$, which tends to $+\infty$ as $t \to +\infty$. Therefore, $t \mapsto \mathrm{vex}(c_e^* + t^*H)(\mathcal{P}_U) - t(H(U) - \mathcal{C})$ reaches a minimum at some $t^*$.

If $(\lambda_w^*, \nu_w^*)_w$ is an optimal splitting, let $\mathcal{I}^* = H(U) - \sum_w \lambda_w^* H(\nu_w^*)$ be its mutual information. We have the following:

$$C_e^*(\mathcal{P}_U, \mathcal{C}) = \sum_w \lambda_w^* c_e^*(\nu_w^*) - t^*(\mathcal{I}^* - \mathcal{C}). \qquad (\text{VI.18})$$

We then find the usual Kuhn-Tucker slackness conditions. If $\mathcal{I}^* < \mathcal{C}$, then $t^* = 0$ and the unconstrained optimum is feasible. If $t^* > 0$, the constraint is binding. The Lagrange multiplier $t^*$ can be interpreted as the shadow price of capacity, that is, the marginal value of an extra unit of communication capacity.

This characterization can be related with the cost of information considered in the literature on rational inattention (See Sims, 2003) where the agent pays a cost proportional to the mutual information between the state and the signal he observes. In particular, Caplin and Dean (2013) consider the convexification of a utility function net of such an information cost. For persuasion games, Gentzkow and Kamenica (2014) assume that the encoder pays a cost for choosing a disclosure strategy which is also related to the mutual information and also take the convexification of the net utility function.

Equation (VI.18) can be seen as a microfoundation of the use of mutual information as the information cost: the limit optimal value of persuasion for a large number of copies of problems with communication over an imperfect channel, has the same value as a problem of persuasion with an information cost. There are some differences, however. First, the information cost is not the mutual information, but the difference between the mutual information and the capacity of the channel. That is, a cost reduces the cost only when the encoder would like to send more information bits than the capacity. Second, the unit price of capacity is endogenous and given by the Lagrange multiplier of the information constraint.

A direct implication is an upper bound of the number of posteriors needed to achieve the convexification.

**Corollary 7** In the optimization problem,

$$C_e^*(\mathcal{P}_U, \mathcal{C}) = \inf \left\{ \sum_w \lambda_w c_e^*(\nu_w) : \sum_w \lambda_w \nu_w = \mathcal{P}_U, \sum_w \lambda_w H(\nu_w) \ge H(U) - \mathcal{C} \right\},$$

the number of posteriors can be chosen to be at most $\min\{|\mathcal{V}|, |\mathcal{U}| + 1\}$.

The proof of Corollary 7 is stated in (Le Treust and Tomala, 2019, [J8]). Without the information constraint, the usual bound is $\min\{|\mathcal{V}|, |\mathcal{U}|\}$, i.e. the number of posteriors or of signals can be upper bounded by the number of actions and the number of states. For the number of actions, the argument is that two signals for which the decoder chooses the same action can be merged into one and the corresponding two posteriors replaced by the average. The argument still holds due to the concavity of the entropy function: replacing two posteriors by their average increases the expected entropy and thus helps in satisfying the information constraint.

For the bound given by the number of states, the usual technical argument is that any point in the convex hull of the epigraph of a function on $\Delta(\mathcal{U})$ is a convex combination involving $|\mathcal{U}|$ points. From Corollary 6, we consider the convexification of a function defined on $\Delta(\mathcal{U}) \times \mathbb{R}$ a domain with one extra dimension; thus, an extra posterior might be needed. A similar observation is made in Boleslavsky and Kim (2018), where due to an incentive constraint, an extra posterior is needed. In Section VI.1.e, we provide an example where $|\mathcal{U}| + 1$ posteriors are used at the optimum.

## VI.1.e Illustrating example

### Unrestricted communication

In this example, the encoder is a firm that persuades the decoder to invest in a risky project. If the decoder does not invest (action $v_0$), the cost is 0 for both players. If the decoder invests (action $v_1$), the
project has a cost 7 in the bad state $u_0$ and $-1$ in the good state $u_1$. Both states are equally likely, the encoder obtains the cost $-1$ only if the decoder invests. The cost table is as follows, the entries are pairs of costs for the players $i = e, d$ depending on the state and action.

<table><thead><tr><th></th><th>$v_0$</th><th>$v_1$</th><th>$P_U$</th></tr></thead><tbody><tr><th>$u_0$</th><td>$0, 0$</td><td>$-1, 7$</td><td>$\frac{1}{2}$</td></tr><tr><th>$u_1$</th><td>$0, 0$</td><td>$-1, -1$</td><td>$\frac{1}{2}$</td></tr></tbody></table>

The decoder invests for sure only when he holds a belief $\nu$ such that $\nu(u_1) > 7/8$. If $\nu(u_1) = 7/8$ he is indifferent. Assuming that in case of indifference he does not invest, the robust cost of the encoder $c_e^*(\nu)$ is 0 if $\nu(u_1) > 7/8$ and $-1$ otherwise.

<figure><img src="image_50.png" /><figcaption>Figure VI.3 – Convexification.</figcaption></figure>

The convexification function $\mathrm{vex}\,c_e^*(\nu)$ is continuous and equal to $-\frac{8}{7}\nu(u_1)$ for $\nu(u_1) \le \frac{7}{8}$ and 0 otherwise. It is easy to see that it does not depend on the action chosen by the decoder at $\nu(u_1) = \frac{7}{8}$, see Fig. VI.3. If the decoder were to choose $v_1$ at the point of indifference, then the optimal splitting for the encoder would be as follows:

$$ \left(\frac{1}{2}, \frac{1}{2}\right) = \frac{3}{7}(1,0) + \frac{4}{7}\left(\frac{1}{8}, \frac{7}{8}\right), $$

where a belief is denoted $\nu = (\nu(u_0), \nu(u_1))$. This yields a cost of $\frac{3}{7}$ which is the lowest that the encoder can achieve given the uniform prior. For any small $\varepsilon > 0$, we can perturb the previous splitting and get the following:

$$ \left(\frac{1}{2}, \frac{1}{2}\right) = \frac{3+8\varepsilon}{7+8\varepsilon}(1,0) + \frac{4}{7+8\varepsilon}\left(\frac{1}{8}-\varepsilon, \frac{7}{8}+\varepsilon\right), $$

which achieves the cost $-\frac{4\varepsilon}{7+8\varepsilon}$ irrespective of the tie-breaking rule. Letting $\varepsilon$ tend 0, we see that the encoder achieves a cost arbitrarily close to $-\frac{4}{7}$, which is the optimal robust cost.

## Restricted and noisy communication

We consider binary sets of signals $\mathcal{X} = \{x_0, x_1\}$, $\mathcal{Y} = \{y_0, y_1\}$ and we assume that the channel has a noise level $\varepsilon \in [0, \frac{1}{2}]$, that is $\mathcal{T}_{\mathcal{Y}|\mathcal{X}}(y_j|x_i) = \varepsilon$ for $j \ne i$, see Fig. VI.4. The generic case is $\varepsilon \in ]0, \frac{1}{2}[$ where the label of the signal (0 or 1) is changed with positive probability but observing a label 1 is still more
<figure><img src="image_51.png" /><figcaption>Figure VI.4 – Binary symmetric channel.</figcaption></figure>

likely when the input label is 1. When $\epsilon = \frac{1}{2}$, the distribution of the output signal is independent from the input signal, so the channel completely disrupts the communication.

A special case is the *binary perfect channel* when $\epsilon = 0$: identifying together the sets $\mathcal{X}$ and $\mathcal{Y}$, an input signal $x$ is received with certainty. Communication is then restricted only by the number of available signals, i.e. the cardinality of $\mathcal{X}$.

The capacity of the binary symmetric channel<fnref n="8" /> is $1 - H(\epsilon)$ where the entropy of the binary probability distribution $(\epsilon, 1 - \epsilon)$ is defined by $H(\epsilon) = \epsilon \log_2 \frac{1}{\epsilon} + (1 - \epsilon) \log_2 \frac{1}{1-\epsilon}$ for $\epsilon \in [0, 1[$, and $H(\epsilon) = 0$ for $\epsilon \in \{0, 1\}$.

One-shot scenario $k = n = 1$

Let a strategy $\sigma$ of the encoder be parametrized by $\sigma(x_0|u_0) = 1 - \alpha$ and $\sigma(x_1|u_1) = 1 - \beta$; see Fig. VI.5.

<figure><img src="image_52.png" /><figcaption>Figure VI.5 – Strategy on the binary symmetric channel.</figcaption></figure>

Then, $\text{Pr}_{\sigma}(y_1|u_0) = \alpha(1 - \epsilon) + (1 - \alpha)\epsilon$, $\text{Pr}_{\sigma}(y_0|u_1) = \beta(1 - \epsilon) + (1 - \beta)\epsilon$ and from Bayes' rule,

$$ \text{Pr}_{\sigma}(u_1|y_1) = \frac{\mathcal{P}_{U}(u_1)(1 - \text{Pr}_{\sigma}(y_0|u_1))}{\mathcal{P}_{U}(u_0)\text{Pr}_{\sigma}(y_1|u_0) + \mathcal{P}_{U}(u_1)(1 - \text{Pr}_{\sigma}(y_0|u_1))}, $$

$$ \text{Pr}_{\sigma}(u_1|y_0) = \frac{\mathcal{P}_{U}(u_1)\text{Pr}_{\sigma}(y_0|u_1)}{\mathcal{P}_{U}(u_0)(1 - \text{Pr}_{\sigma}(y_1|u_0)) + \mathcal{P}_{U}(u_1)\text{Pr}_{\sigma}(y_0|u_1)}. $$

It is easy to see that the numbers $\text{Pr}_{\sigma}(y_1|u_0)$, $\text{Pr}_{\sigma}(y_0|u_1)$, $\text{Pr}_{\sigma}(u_1|y_1)$, $\text{Pr}_{\sigma}(u_1|y_0)$ all belong to the interval $[\epsilon, 1 - \epsilon]$.

A pair of posteriors $(\nu_0, \nu_1)$ is said to be *feasible* in the one-shot scenario if there exists a number $\lambda \in [0, 1]$ such that:

$$ (\mathcal{P}_{U}(u_0), \mathcal{P}_{U}(u_1)) = \lambda(\nu_0(u_0), \nu_0(u_1)) + (1 - \lambda)(\nu_1(u_0), \nu_1(u_1)). $$

The feasible splittings can be characterized as follows.

<footnote n="8">⁸Cover and Thomas, 2006, Example 2.1.1, p. 15.</footnote>
<figure><img src="image_53.png" /><figcaption>Figure VI.6 – For a noise parameter $\epsilon = \frac{1}{4}$, the green lenses correspond to the feasible posteriors $(\nu_0, \nu_1)$ characterized in Lemma 5 for the one-shot scenario $k = n = 1$. The blue and green regions correspond to the feasible posteriors $(\nu_0, \nu_1)$ in the asymptotic scenario where $k = n \to \infty$. The red point corresponds to the optimal splitting, also depicted in Fig. VI.7. The hatched areas correspond to the nonfeasible posteriors $(\nu_0, \nu_1)$.</figcaption></figure>

**Lemma 5** We consider the one-shot problem where $n = k = 1$. A pair of posteriors $(\nu_0, \nu_1)$ is feasible if and only if $\nu_1 = \nu_0 = \mathcal{P}_U$ or,

$$ \epsilon \leq \frac{\nu_0(u_1)(\nu_1(u_1) - \mathcal{P}_U(u_1))}{\mathcal{P}_U(u_1)(\nu_1(u_1) - \nu_0(u_1))} \leq 1 - \epsilon $$

and

$$ \epsilon \leq \frac{(1 - \nu_0(u_1))(\mathcal{P}_U(u_1) - \nu_0(u_1))}{(1 - \mathcal{P}_U(u_1))(\nu_1(u_1) - \nu_0(u_1))} \leq 1 - \epsilon. $$

The proof is in (Le Treust and Tomala, 2019, [J8], Appendix). As an illustration, take the uniform prior $(\frac{1}{2}, \frac{1}{2})$ and a level of noise $\epsilon = \frac{1}{4}$. The feasible posteriors are shown by the colored green regions on Fig. VI.6.

From the previous discussion, it is impossible to induce beliefs with $\nu(u_1) > \frac{3}{4}$. Therefore, the decoder will never be confident enough to invest and the cost is 0 for the encoder.

**Asymptotic scenario with $k = n \to \infty$**

We consider the case where $k = n$ tends to infinity with a noise level of $\epsilon = \frac{1}{4}$ and compute the value of the optimal splitting problem with information constraint. The capacity of the channel is $1 - H(\frac{1}{4})$, the entropy of the uniform prior is 1; therefore, the information constraint is $\sum_w \lambda_w H(\nu_w) \geq H(\frac{1}{4})$. Under this constraint the optimal splitting for the encoder satisfies:

$$ \left(\frac{1}{2}, \frac{1}{2}\right) = \lambda\left(\frac{1}{8}, \frac{7}{8}\right) + (1 - \lambda)(\nu_0(u_0), \nu_0(u_1)) $$

and

$$ H\left(\frac{1}{4}\right) = \lambda H\left(\frac{7}{8}\right) + (1 - \lambda)H(\nu_0(u_1)). $$
<figure><img src="image_54.png" /><figcaption>Figure VI.7 – For a noise parameter $\epsilon = \frac{1}{4}$, the optimal splitting is given by $\nu_0(u_1) \approx 0.340$ and $\nu_1(u_1) = \frac{7}{8}$.</figcaption></figure>

To see why it is optimal, first observe that the encoder has to bring on some posterior, denoted by $\nu_1$, with $\nu_1(u_1) > \frac{7}{8}$ in order to get some cost. To get it with the highest probability, he should aim for $\nu_1(u_1) = \frac{7}{8}$. Among the posteriors that induce investment, this is also the one with highest entropy. Second, to minimize expected costs, the remaining posteriors must be as far away as possible from the prior; that is, the information constraint should bind. Additionally, note that only one posterior, denoted by $\nu_0$, will be optimally generated in the region $\nu_0(u_1) < \frac{7}{8}$. Since the entropy is strictly concave, replacing two posteriors on this region by their average does not change the cost and increases the entropy.

Solving these two equations numerically we get, $\nu_0(u_1) \approx 0.340$ and $C_e^*(P_U, C(T_{Y|X})) = -\lambda \approx -0.298$ instead of the cost 0 for the one-shot scenario and about 52.1% of the unconstrained optimum $-\frac{4}{7}$.

This is shown in Fig. VI.7 which plots the cost function and the entropy function. The splitting of $P_U$ into $\nu_0, \nu_1$ is shown by the three points on the horizontal axis. On the vertical line $P_U(u_1) = \frac{1}{2}$, we can read the average cost with the red line and the average entropy with the green line. To see optimality on the picture, if we move $\nu_0(u_1)$ to the right, then the average cost decrease, and if we move it to the left, the average entropy will fall below $H(\frac{1}{4})$ and the information constraint will be violated.

The optimal splitting is also marked on Fig. VI.6 which shows the set of pairs of posteriors for the splittings that satisfy the information constraint (union of green and blue regions).

On Fig. VI.8, we represent the value $C_e^*(P_U, C(T_{Y|X}))$ of the optimal splitting problem as a function of the prior $P_U$, for different values for the noise parameter $\epsilon \in \{\frac{1}{20}, \frac{3}{20}, \frac{1}{4}, \frac{7}{20}, \frac{9}{20}, \frac{99}{200}\}$. It is found by solving the following system for $\nu_0$:

$$ (P_U(u_0), P_U(u_1)) = \lambda \left(\frac{1}{8}, \frac{7}{8}\right) + (1-\lambda)(\nu_0(u_0), \nu_0(u_1)) $$

and

$$ H(P_U(u_1)) - 1 + H(\epsilon) = \lambda H\left(\frac{7}{8}\right) + (1-\lambda)H(\nu_0(u_1)). $$

When $P_U(u_1) = \frac{1}{2}$ and $\epsilon = \frac{1}{4}$, we recover the value $C_e^*(P_U, C(T_{Y|X})) \approx -0.298$ as in Fig. VI.7.

Observe that the function $C_e^*(P_U, C(T_{Y|X}))$ is not concave with respect to the prior $P_U$. From Corollary 6, $C_e^*(P_U, C)$ is the convexification of the function $c_e^H$ calculated at $(P_U, H(U) - C)$, so this composed function need not be concave.
<figure><img src="image_55.png" /><figcaption>Figure VI.8 – Value of the optimal splitting problem as a function of the prior $\mathcal{P}_U$, for different noise parameters $\varepsilon \in \{\frac{1}{20}, \frac{3}{20}, \frac{1}{4}, \frac{7}{20}, \frac{9}{20}, \frac{99}{200}\}$.</figcaption></figure>

**Perfect binary channel with $k = \frac{n}{2} \to \infty$**

We consider the same example as before, repeated $n$ times with the uniform prior $\mathcal{P}_U = (\frac{1}{2}, \frac{1}{2})$. In line with the motivating example from the introduction, we consider a perfect channel and assume that the encoder has at its disposal half as many signals as needed to communicate perfectly, that is $k = \frac{n}{2}$. Since the capacity of the binary perfect channel is one, $\frac{k}{n} = \frac{1}{2}$ and $H(U) = 1$, the information constraint is:

$$H(U) - \sum_{w} \lambda_{w} H(\nu_{w}) \leq \frac{1}{2} \iff \sum_{w} \lambda_{w} H(\nu_{w}) \geq \frac{1}{2}.$$

Observe that this constraint is identical to the one obtained with a binary symmetric channel with noise $\varepsilon$ such that $H(\varepsilon) = \frac{1}{2}$ (i.e., $\varepsilon \approx 0.110$). Therefore, the optimal splitting is given by the following system:

$$(\mathcal{P}_U(u_0), \mathcal{P}_U(u_1)) = \lambda\left(\frac{1}{8}, \frac{7}{8}\right) + (1-\lambda)(\nu_0(u_0), \nu_0(u_1))$$

and

$$\frac{1}{2} = \lambda H\left(\frac{7}{8}\right) + (1 - \lambda)H(\nu_0(u_1)).$$

Solving numerically, we find $C_e^*(\mathcal{P}_U, \frac{1}{2}) \approx -0.519$.

**On the number of posteriors**

We give now an example showing the tightness of the bound $\min\{|V|, |U| + 1\}$ on the number of posteriors, given in Corollary 7. The cost table is as follows:

<table><thead><tr><th></th><th>$v_0$</th><th>$v_1$</th><th>$v_2$</th><th></th></tr></thead><tbody><tr><th>$u_0$</th><td>0, 0</td><td>-1, 7</td><td>-1, -1</td><td>$\frac{1}{2}$</td></tr><tr><th>$u_1$</th><td>0, 0</td><td>-1, -1</td><td>-1, 7</td><td>$\frac{1}{2}$</td></tr></tbody></table>
There are two risky projects ($v_1$ and $v_2$) and the encoder wants to persuade the decoder to invest in any of them. The decoder invests only if $\nu(u_1) > 7/8$ or $\nu(u_1) < 1/8$.

With unrestricted communication, the solution is clear: the encoder fully discloses the state and gets a cost of -1. However, with a binary symmetric channel with noise $\epsilon = 1/4$, the encoder gets 0 in the one-shot scenario. Consider now the case where $k = n \to \infty$.

The “one-sided” solution of Section VI.1.e is feasible. Recall that this is the splitting such that:

$$ \left(\frac{1}{2}, \frac{1}{2}\right) = \lambda \left(\frac{1}{8}, \frac{7}{8}\right) + (1-\lambda)(\nu_0(u_0), \nu(u_1)) $$

and

$$ H\left(\frac{1}{4}\right) = \lambda H\left(\frac{7}{8}\right) + (1-\lambda)H(\nu_0(u_0), \nu_0(u_1)). $$

with $\nu_0(u_1) \approx 0.340$ and $\lambda \approx 0.298$. It is easy to see that this is optimal among the splittings with two posteriors. Indeed, it is not possible that the two posteriors induce investment while satisfying the information constraint.

However, this is not optimal. The optimal splitting has three posteriors and is as follows:

$$ \left(\frac{1}{2}, \frac{1}{2}\right) = (1-\lambda)\left(\frac{1}{2}, \frac{1}{2}\right) + \frac{\lambda}{2}\left(\frac{1}{8}, \frac{7}{8}\right) + \frac{\lambda}{2}\left(\frac{7}{8}, \frac{1}{8}\right) $$

with

$$ H\left(\frac{1}{4}\right) = (1-\lambda)H\left(\frac{1}{2}\right) + \frac{\lambda}{2}H\left(\frac{1}{8}\right) + \frac{\lambda}{2}H\left(\frac{7}{8}\right). $$

This pins down a unique $\lambda$ and solving numerically yields $\lambda \approx 0.413$. Since $\lambda$ is the probability of investment, we get $C_e^*(P_U, T_{Y|X}) \approx -0.413$ which is about 38% better than what is achieved with a splitting with two points.

To see that this is optimal, first since there are two states, we know that three posteriors are sufficient. Second, it is not possible to have all posteriors in the investment region and to satisfy the information constraint. If there is only one posterior in the investment region, then the splitting achieves no more than the “one-sided” solution. Therefore, it is optimal to have two posteriors in the investment region and one outside of it. However, then, it is optimal to choose the point in the middle region to be $(\frac{1}{2}, \frac{1}{2})$, since this is the one with the highest entropy.

### VI.1.f Beyond identical problems

The main result can be extended to series of persuasion problems which are not all identical, but such that each type of problem is repeated many times. Suppose that we have a family of persuasion problems indexed by a type parameter $z$ in a finite set $\mathcal{Z}$. That is, for every $z \in \mathcal{Z}$, there is a prior probability distribution $P_{U|Z}(\cdot|z) \in \Delta(\mathcal{U})$ and cost functions $c_i: \mathcal{U} \times \mathcal{V} \times \mathcal{Z} \to \mathbb{R}$ for each player $i = \mathbf{e}, \mathbf{d}$. The series of persuasion problems is given by a sequence $z^n = (z_1, \dots, z_n)$ which is commonly known by both players. The distribution of states is as follows:

$$ \mathcal{P}_U^n(u^n|z^n) := \prod_{t=1}^n \mathcal{P}_U(u_t|z_t). $$

If the sequence of states and actions are respectively $u^n, v^n$, the cost for player $i$ is $\frac{1}{n} \sum_{t=1}^n c_i(u_t, v_t, z_t)$. The communication technology is still given by a channel $(\mathcal{X}, \mathcal{Y}, T_{Y|X})$ used $k$ times, so that the strategy sets are the same as before for both players. The optimal robust cost of the encoder is defined as before and is denoted by $C_e^{n,k}(P_U, T_{Y|X}, z^n)$.

For each posterior belief $\nu \in \Delta(\mathcal{U})$ and type $z \in \mathcal{Z}$, the set of optimal actions of the decoder is $V^{*z}(\nu) = \text{argmin}_{v \in \mathcal{V}} \sum_u \nu(u)c_d(u, v, z)$ and we denote by $c_e^z(\nu) = \min_{v \in V^{*z}(\nu)} \sum_u \nu(u)c_e(u, v, z)$ the robust cost of the encoder at the belief $\nu$.
**Definition 47** For $\pi \in \Delta(\mathcal{Z})$ and $C \ge 0$, the optimal splitting problem with information constraint is as follows:

$$C_e^Z(\mathcal{P}_{U|Z}, C, \pi) = \inf \sum_z \pi(z) \sum_m \lambda_w^z c_e^z(\nu_w^z) \\ \text{s.t.} \quad \sum_w \lambda_w^z \nu_w^z = \mathcal{P}_{U|Z}(\cdot|z), \quad \forall z \in Z, \\ \text{and} \quad \sum_z \pi(z) \left( H(\mathcal{P}_{U|Z}(\cdot|z)) - \sum_w \lambda_w^z H(\nu_w^z) \right) \le C.$$

The interpretation is as follows. Suppose that $\pi(z)$ represents the probability, or frequency, of occurrence of $z$. Conditional on $z$ which is known by both players, the encoder performs a splitting of $\mathcal{P}_{U|Z}(\cdot|z)$, $\sum_w \lambda_w^z \nu_w^z = \mathcal{P}_{U|Z}(\cdot|z)$, and gets the cost $\sum_m \lambda_m^z c_e^z(\nu_m^z)$. The information constraint imposes the conditional mutual information $I(U; W|Z)$ to be less than or equal to the capacity $C$.

Given a sequence $z^n \in Z^n$, let $\pi_n \in \Delta(\mathcal{Z})$ be the empirical frequency induced by the sequence: for each $z \in \mathcal{Z}$, $\pi_n(z) = \frac{1}{n}|\{t: z_t = z\}|$.

**Theorem 35** 1. The optimal robust cost of the encoder is no more than the value of the optimal splitting problem with information constraint. For each pair of integers $n, k$:

$$C_e^{n,k}(\mathcal{P}_U, \mathcal{T}_{Y|X}, z^n) \le C_e^Z(\mathcal{P}_{U|Z}, \frac{k}{n}C(\mathcal{T}_{Y|X}), \pi_n).$$

2. The optimal robust cost of the encoder converges to the value of the optimal splitting problem with information constraint in the following sense. For each $\pi \in \Delta(\mathcal{Z})$ and $r \in [0, +\infty]$, for each pair of sequences of integers $(k_j, n_j)_{j \in \mathbb{N}^*}$ such that $\lim_{j \to \infty} \min(n_j, k_j) = \infty$, $\lim_{j \to \infty} \frac{k_j}{n_j} = r$ and $\lim_{j \to \infty} \pi_{n_j} = \pi$, we have:

$$\lim_{j \to \infty} C_e^{n_j, k_j}(\mathcal{P}_U, \mathcal{T}_{Y|X}, z^{n_j}) = C_e^Z(\mathcal{P}_{U|Z}, rC(\mathcal{T}_{Y|X}), \pi).$$

Given a sequence $z^n$, $\pi_n$ is the empirical distribution of types of problems. The optimal cost of the encoder is bounded above by the value of optimal splitting under information constraint. Suppose that the distribution of types is held fixed (or converges to) $\pi$, then when $n$ and $k$ grow large, the encoder is able to secure approximately this value.

This extension applies to the case where the proportions of types of problems are fixed. Alternatively, the sequence $z^n$ could be drawn i.i.d. from a prior distribution $\pi \in \Delta(\mathcal{Z})$.

Notice the channel $\mathcal{T}_{Y|X}^k$ is used for transferring information about all problems. Thus, Theorem 35 does more than merely patching up distinct families of problems together. The capacity of the channel bounds the total amount of information, across all problems. Thus, all problems, even of different types, are linked together in the signals.

We have analyzed a persuasion game where the encoder communicates with the decoder through a fixed and imperfect channel. The optimal cost of the encoder is bounded above by the value of the optimal splitting problem with information constraint. When the encoder and the decoder are engaged in many repetitions of identical persuasion games, the optimal cost for the encoder converges to the upper bound as the number of repetitions increases.

## VI.2 Persuasion game with side information at the decoder

In the previous section, it is assumed that the information about the state if fully controlled by the encoder. To model private information of the decoder, we consider that the nature draw pairs $(u_t, z_t)_{t=1,...,n}$ and assume that $u^n$ is the private information of the encoder and $z^n$ is the private information of the decoder, as depicted in Fig. VI.9. Our methods generalize to this case provided that we use the correct information constraint. A random signal $W$ can be transmitted over the channel provided that its mutual
information with the state, conditional on the private information of the decoder $I(U; W|Z) \le C$ is less than or equal to the capacity, where

$$I(U; W|Z) := \sum_z \Pr(z)I(U; W|Z = z)$$

is the expectation over $Z$ of the mutual information conditional on $\{Z = z\}$.

Communication between autonomous devices that have distinct objectives is under study. This problem, referred to as the strategic communication problem, is at the crossroads of different disciplines such as Control Theory Sarıtaş et al. (2017), Sarıtaş et al. (2020), Computer Science Dughmi et al. (2019) and Information Theory (Le Treust and Tomala, 2016, [IC7]), (Le Treust and Tomala, 2018b, [IC20]), (Le Treust and Tomala, 2018a, [W2]), Sarıtaş et al. (2019), Vora and Kulkarni (2020), Vora and Kulkarni (2020), Kazıklı et al. (2021), where it was introduced by Akyol et al. in Akyol et al. (2016), Akyol et al. (2017).

Three different formulations of the strategic communication problem are originally proposed in the Game Theory literature, see (Le Treust and Tomala, 2020, [IC26]). The cheap talk game of Crawford and Sobel Crawford and Sobel (1982) relies on the Nash equilibrium solution. In the mechanism design problem of Jackson and Sonnenschein Jackson and Sonnenschein (2007) the receiver commits to a prescribed decoding strategy, as the leader of a Stackelberg game. The hypothesis of decoder commitment is also related to the mismatched rate-cost problem in Lapidoth (1997), Scarlett et al. (2020). In the persuasion game of Kamenica and Gentzkow (2011), it is the sender who commits to a strategy whereas the decoder computes its Bayesian posterior belief and selects the optimal output symbol. In (Le Treust and Tomala, 2019, [J8]), we characterize the impact of the channel noise in the solution to the persuasion problem.

In this section, we extend these previous results with encoder commitment by considering that the decoder has side information. More specifically, we formulate a joint source-channel coding problem with decoder side information in which the encoder and the decoder are endowed with distinct cost functions. Given an encoder strategy, the decoder selects an optimal strategy for its cost function. The encoder anticipates the mismatch of the cost functions and commits to implementing the encoding strategy that minimizes its cost.

The technical novelty consists in controlling the distance of the posterior beliefs induced by Wyner-Ziv's coding to the target posterior beliefs. This demonstrates that the Wyner-Ziv's encoding reveals nothing but the exact amount of information needed to implement the optimal decoding strategy. Consequently at the optimum the decoder produces a sequence of outputs which is almost the same as the one generated by the coding of Wyner and Ziv (1976), for a specific probability distribution.

<figure><img src="image_56.png" /><figcaption>Figure VI.9 – The source $P_{UZ}$ is i.i.d., the channel $T_{Y|X}$ is memoryless. The encoder and the decoder have arbitrary distinct cost functions $c_e(u, v) \neq c_d(u, v)$.</figcaption></figure>

## VI.2.a System model

We denote by $\mathcal{U}$, $\mathcal{Z}$, $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{V}$, the finite sets of information source, side information, channel inputs, channel outputs and decoder's outputs. We consider the information source $(\mathcal{U} \times \mathcal{Z}, P_{UZ})$ and the channel $(\mathcal{X}, \mathcal{Y}, T_{Y|X})$, as depicted in Fig. VI.9.
**Definition 48** We define the encoding and the decoding strategies by

$$ \sigma: \mathcal{U}^n \to \Delta(\mathcal{X}^n), \qquad (VI.19) $$

$$ \tau: \mathcal{Y}^n \times \mathcal{Z}^n \to \Delta(\mathcal{V}^n). \qquad (VI.20) $$

The strategies $(\sigma, \tau)$ induces the distribution

$$ P_{U^n Z^n X^n Y^n V^n}^{\sigma, \tau} = \left( \prod_{t=1}^{n} P_{U_t Z_t} \right) \sigma_{X^n|U^n} \left( \prod_{t=1}^{n} \tau_{Y_t|X_t} \right) \tau_{V^n|Y^n Z^n}, \qquad (VI.21) $$

where $\sigma_{X^n|U^n}$, $\tau_{V^n|Y^n Z^n}$ denote the distributions of the strategies $\sigma$, $\tau$.

**Definition 49** The encoder and decoder are endowed with distinct cost functions

$$ c_e: \mathcal{U} \times \mathcal{V} \to \mathbb{R}, \qquad c_d: \mathcal{U} \times \mathcal{V} \to \mathbb{R}. \qquad (VI.22) $$

The long-run cost functions $c_e^n(\sigma, \tau)$, $c_d^n(\sigma, \tau)$ are defined by

$$ c_e^n(\sigma, \tau) = \mathbb{E} \left[ \frac{1}{n} \sum_{t=1}^{n} c_e(u_t, v_t) \right], \\ c_d^n(\sigma, \tau) = \sum_{u^n, v^n} P^{\sigma, \tau}(u^n, v^n) \cdot \left( \frac{1}{n} \sum_{t=1}^{n} c_d(u_t, v_t) \right). $$

**Definition 50** Given $n \in \mathbb{N}^*$, we define:

1. the set of decoder best responses to strategy $\sigma$ by

$$ BR_d(\sigma) = \underset{\tau}{\operatorname{argmin}} c_d^n(\sigma, \tau), \qquad (VI.23) $$

2. the long-run encoder cost value by

$$ C_e^n = \inf_{\sigma} \max_{\tau \in BR_d(\sigma)} c_e^n(\sigma, \tau). \qquad (VI.24) $$

In case $BR_d(\sigma)$ is not a singleton, we assume that the decoder selects the worst strategy for the encoder cost $\max_{\tau \in BR_d(\sigma)} c_e^n(\sigma, \tau)$, so that the solution is robust to the exact specification of the decoding strategy. We aim at characterizing the asymptotic behavior of $C_e^n$.

**Definition 51** We consider an auxiliary random variable $W \in \mathcal{W}$ with $|\mathcal{W}| = \min (|\mathcal{U}| + 1, |\mathcal{V}|^{|\mathcal{Z}|})$ and we define

$$ \mathbb{Q} = \left\{ \mathcal{P}_{UZ} \mathcal{Q}_{W|U}, \max_{\mathcal{P}_X} I(X; Y) - I(U; W|Z) \ge 0 \right\}. \qquad (VI.25) $$

Given $\mathcal{Q}_{UZW}$, we define the single-letter best responses

$$ A_d(\mathcal{Q}_{UZW}) = \underset{\mathcal{Q}_{V|ZW}}{\operatorname{argmin}} \mathbb{E}_{\mathcal{Q}_{V|ZW}} [c_d(U, V)]. \qquad (VI.26) $$

The encoder optimal cost $C_e^*$ is given by

$$ C_e^* = \inf_{\mathcal{Q}_{UZW} \in \mathbb{Q}} \max_{\substack{\mathcal{Q}_{V|ZW} \in \\ \lambda_d(\mathcal{Q}_{UZW})}} \mathbb{E}_{\mathcal{Q}_{V|ZW}} [c_e(U, V)]. \qquad (VI.27) $$

If $A_d(\mathcal{Q}_{UZW})$ is not a singleton, the decoder selects the worst distribution $\mathcal{Q}_{V|ZW}$ from the encoder perspective.
**Theorem 36**

$$ \forall n \in \mathbb{N}^*, \quad C_e^n \geq C_e^*, \qquad (VI.28) $$

$$ \forall \varepsilon > 0, \exists \bar{n} \in \mathbb{N}^*, \forall n \geq \bar{n}, \quad C_e^n \leq C_e^* + \varepsilon. \qquad (VI.29) $$

The proof of Theorem 36 is stated in (Le Treust and Tomala, 2019, [W3], App. B and C).

Sketch of proof of (VI.28). For all $n \in \mathbb{N}^*$, the converse result relies on the identification of the auxiliary random variables $W = (Y^n, Z^{T-1}, Z_{T+1}^n, T)$ and $(U, Z, V) = (U_T, Z_T, V_T)$, where $T$ is uniformly distributed over $\{1, \dots, n\}$. We denote by $Q_{UZW}^\sigma$, $Q_{V|ZW}^\tau$ the distributions induced by $(\sigma, \tau)$ over $(U, Z, W, V)$. In Merhav and Shamai (2003), it is proved that the Markov chain $Z \leftarrow U \leftarrow W$ holds and that $I(U; W|Z) \leq \max_{\mathcal{P}_X} I(X; Y)$, hence $Q_{UZW}^\sigma \in \mathbb{Q}$. We show that

$$ c_e^n(\sigma, \tau) = \mathbb{E}_{\substack{Q_{UZW}^\sigma \\ Q_{V|ZW}^\tau}} [c_e(U, V)], \qquad (VI.30) $$

$$ \{\mathcal{P}_{V|ZW}, \exists \tau \in \mathbf{BR}_d(\sigma), Q_{V|ZW}^\tau = \mathcal{P}_{V|ZW}\} = \mathbb{A}_d(Q_{UZW}^\sigma). \qquad (VI.31) $$

Then for any $\tilde{\sigma}$, we have

$$ \max_{\tau \in \mathbf{BR}_d(\tilde{\sigma})} c_e^n(\tilde{\sigma}, \tau) = \max_{\substack{\mathcal{P}_{V|ZW}, \exists \tau \in \mathbf{BR}_d(\tilde{\sigma}) \\ Q_{V|ZW}^\tau = \mathcal{P}_{V|ZW}}} \mathbb{E}_{\substack{Q_{UZW}^\sigma \\ \mathcal{P}_{V|ZW}}} [c_e(U, V)] \qquad (VI.32) $$

$$ = \max_{\substack{Q_{V|ZW} \in \mathcal{P}_{UZW} \\ \mathcal{P}_{d}(Q_{UZW}^\tau)}} \mathbb{E}_{\substack{Q_{UZW} \\ Q_{V|ZW}}} [c_e(U, V)] \qquad (VI.33) $$

$$ \geq \inf_{Q_{UZW} \in \mathbb{Q}} \max_{\substack{Q_{V|ZW} \in \mathcal{P}_{UZW} \\ \mathcal{P}_{d}(Q_{UZW}^\tau)}} \mathbb{E}_{\substack{Q_{V|ZW} \\ Q_{UZW}}} [c_e(U, V)] = C_e^*, \qquad (VI.34) $$

which implies (VI.28).

Note that the sequence $(nC_e^n)_{n \in \mathbb{N}^*}$ is sub-additive. Indeed, when $\sigma$ is the concatenation of several encoding strategies, the optimal $\tau$ in (VI.24) is the concatenation of the optimal decoding strategies. Theorem 36 and Fekete's lemma, show that

$$ C_e^* = \lim_{n \to +\infty} C_e^n = \inf_{n \in \mathbb{N}^*} C_e^n. \qquad (VI.35) $$

## VI.2.b Convex closure formulation

Recall that we denote by $\mathrm{vex} f: \mathcal{X} \to \mathbb{R} \cup \{-\infty\}$ the convex closure of a function $f$, i.e. the largest convex function everywhere smaller than $f$ on $X$. We reformulate $C_e^*$ in terms of a convex closure, similarly to (Kamenica and Gentzkow, 2011, Corollary 1).

**Lemma 6** For all $Q_{W|U} \in \Delta(\mathcal{W})^{|U|}$, for all $(u, z, w) \in \mathrm{supp}(\mathcal{P}_{UZ} Q_{W|U})$ we have

$$ Q_{U|WZ}(u|w, z) = \frac{Q_{U|W}(u|w)\mathcal{P}_{Z|U}(z|u)}{\sum_{u'} Q_{U|W}(u'|w)\mathcal{P}_{Z|U}(z|u')}. \qquad (VI.36) $$

The proof is direct. The conditional distribution $Q_{U|WZ} \in \Delta(\mathcal{U})^{|W \times Z|}$ reformulates in terms of $Q_{U|W} \in \Delta(\mathcal{U})^{|W|}$.

**Definition 52** Given the probability distribution $p \in \Delta(\mathcal{U})$, the decoder selects a best response action $v$ in

$$ \mathcal{V}^*(p) = \underset{v \in \mathcal{V}}{\operatorname{argmin}} \mathbb{E}_p[c_d(U, v)]. \qquad (VI.37) $$

Given $p \in \Delta(\mathcal{U})$, we define the robust cost function by

$$ \psi_e(p) = \max_{v \in \mathcal{V}^*(p)} \mathbb{E}_p[c_e(U, v)]. \qquad (VI.38) $$
**Definition 53** For $p \in \Delta(\mathcal{U})$, the average cost function $\Psi_e(p)$ and the average entropy function $h(p)$ are
defined by

$$ \Psi_e(p) = \sum_{u,z} p(u) \mathcal{P}_{Z|U}(z|u) \cdot \psi_e \left( \frac{p(\cdot) \mathcal{P}_{Z|U}(z|\cdot)}{\sum_{u'} p(u') \mathcal{P}_{Z|U}(z|u')} \right), \quad (\text{VI.39}) $$

$$ h(p) = \sum_{u,z} p(u) \mathcal{P}_{Z|U}(z|u) \log_2 \frac{\sum_{u'} p(u') \mathcal{P}_{Z|U}(z|u')}{p(u) \mathcal{P}_{Z|U}(z|u)}. \quad (\text{VI.40}) $$

The function $h(p)$ is the conditional entropy $H(U|Z)$ evaluated with respect to $p \cdot \mathcal{P}_{Z|U}$ instead of $\mathcal{P}_{UZ}$.

**Lemma 7** The function $h(p)$ is concave in $p \in \Delta(\mathcal{U})$.

*Proof.* [Lemma 7] The entropy $H(U)$ is concave in $p \in \Delta(\mathcal{U})$, the mutual information $I(U; Z)$ is convex in $p \in \Delta(\mathcal{U})$ for fixed $\mathcal{P}_{Z|U}$ and moreover $H(U|Z) = H(U) - I(U; Z)$. ■

**Theorem 37**

$$ C_e^* = \inf \left\{ \sum_{w \in \mathcal{W}} \lambda_w \Psi_e(p_w), \sum_{w \in \mathcal{W}} \lambda_w p_w = \mathcal{P}_U, \sum_{w \in \mathcal{W}} \lambda_w h(p_w) \ge H(U|Z) - \max_{\mathcal{P}_X} I(X; Y) \right\}, \quad (\text{VI.41}) $$

where the infimum is taken over $(\lambda_w, p_w)_{w \in \mathcal{W}}$ with $|\mathcal{W}| = \min(|\mathcal{U}|+1, |\mathcal{V}|^{|\mathcal{Z}|})$, such that for each $w \in \mathcal{W}$, $p_w \in \Delta(\mathcal{U})$, $\lambda_w \in [0, 1]$, and $\sum_{w \in \mathcal{W}} \lambda_w = 1$.

The proof of Theorem 37 is stated in (Le Treust and Tomala, 2019, [W3], App. A). It is a consequence of the Markov chain property $Z \leftarrow U \leftarrow W$. Note that all the channels such that $\max_{\mathcal{P}_X} I(X; Y) \ge H(U|Z)$ lead to the same value for $C_e^*$. The optimal parameters $(\lambda_w^*, p_w^*)_{w \in \mathcal{W}}$ in (VI.41) are referred to as the optimal splitting of the prior distribution $\mathcal{P}_U$, see Aumann and Maschler (1995). When removing the decoder side information, e.g. $|\mathcal{Z}| = 1$, and changing the infimum into a supremum, we recover the value of the optimal splitting problem of (Le Treust and Tomala, 2019, [J8], Definition 2.4).

* Since $\sum_w \lambda_w h(p_w) = H(U|Z, W)$, the information constraint in (VI.41) is a reformulation of $I(U; W|Z) \le \max_{\mathcal{P}_X} I(X; Y)$.

* The dimension of the problem (VI.41) is $|\mathcal{U}|+1$. Caratheodory's Lemma (Rockafellar, 1970, Corollary 17.1.5, pp. 157) induces the cardinality bound $|\mathcal{W}| \le |\mathcal{U}|+1$.

* The cardinality of $\mathcal{W}$ is also restricted by the vector of recommended symbols $|\mathcal{W}| \le |\mathcal{V}|^{|\mathcal{Z}|}$, telling to the decoder which symbol $v \in \mathcal{V}$ to select when the side information is $z \in \mathcal{Z}$.

The encoder optimal cost $C_e^*$ can be reformulated in terms of Lagrangian and in terms of the convex closure of

$$ \tilde{\Psi}_e(p, \nu) = \begin{cases} \Psi_e(p), & \text{if } \nu \le h(p), \\ +\infty, & \text{otherwise.} \end{cases} \quad (\text{VI.42}) $$

**Theorem 38**

$$ C_e^* = \sup_{t \ge 0} \left\{ \mathrm{vex} \left[ \Psi_e + t \cdot h \right] (\mathcal{P}_U) - t \cdot \left( H(U|Z) - \max_{\mathcal{P}_X} I(X; Y) \right) \right\} \quad (\text{VI.43}) $$

$$ = \mathrm{vex} \tilde{\Psi}_e (\mathcal{P}_U, H(U|Z) - \max_{\mathcal{P}_X} I(X; Y)). \quad (\text{VI.44}) $$
Equation (VI.43) is the convex closure of a Lagrangian with the information constraint. Equation (VI.44) corresponds to the convex closure of a bi-variate function where the information constraint requires an additional dimension. The proof follows directly from (Le Treust and Tomala, 2019, [J8], Theorem 3.3, pp. 37) by replacing concave closure by convex closure.

**Remark 30** When $c_e = c_d$, then $\psi_e(p) = \min_v \mathbb{E}_p[c_e(U, v)]$ and we reformulate the solution of Wyner and Ziv (1976) in terms of a splitting problem, whose optimal solution is computed as in Sec. VI.2.c.

$$ C_e^* = \inf_{(\lambda_w, p_w)_{w \in W}, \sum_w \lambda_w = 1} \left\{ \sum_{w \in W} \lambda_w \sum_{u, z} p_w(u) \mathcal{P}_{Z|U}(z|u) \times \min_v \mathbb{E} \frac{p_w(\cdot) \mathcal{P}_{Z|U}(z|\cdot)}{\sum_{u'} p_w(u') \mathcal{P}_{Z|U}(z|u')} [c_e(U, v)], \right. \\ \left. \sum_{w \in W} \lambda_w p_w = \mathcal{P}_U, \quad \sum_{w \in W} \lambda_w h(p_w) \ge H(U|Z) - \max_{\mathcal{P}_X} I(X; Y) \right\}. \quad (VI.45) $$

When $c_e = -c_d$, then $V^*(p) = \underset{v}{\operatorname{argmax}} \mathbb{E}_p[c_e(U, v)]$ and both functions $\psi_e(p)$, $\Psi_e(p)$ are convex in $p \in \Delta(U)$. By Jensen's inequality, the infimum in (VI.41) is achieved by $p_w^* = \mathcal{P}_U$, $\forall w \in W$, i.e. no information is transmitted and $C_e^* = \max_v \mathbb{E}_{\mathcal{P}_U}[c_e(U, v)]$.

## VI.2.c Doubly symmetric binary source

We consider the doubly symmetric binary source (DSBS) example introduced in (Wyner and Ziv, 1976, Sec. II), depicted in Fig. VI.10 with parameters $(p_0, \delta_0, \delta_1) \in [0, 1]^3$. The cardinality bound is $|W| = \min(|U| + 1, |V|^{|Z|}) = 3$, hence the random variable $W$ is drawn according to the conditional probability distribution $Q_{W|U}$ with parameters $(\alpha_k, \beta_k)_{k \in \{1,2,3\}} \in [0, 1]^6$ such that $\sum_k \alpha_k = \sum_k \beta_k = 1$.

<figure><img src="image_57.png" /><figcaption>Figure VI.10 – Joint probability distribution $\mathcal{P}_{UZ}(u, z)Q_{W|U}(w|u)$ with $|W| = 3$ depending on parameters $p_0, \delta_0, \delta_1, (\alpha_k, \beta_k)_{k \in \{1,2,3\}}$ that belong to $[0, 1]$.</figcaption></figure>

<table><caption>Figure VI.11 – Encoder cost $c_e(u, v)$.</caption><thead><tr><th></th><th>$v_0$</th><th>$v_1$</th></tr></thead><tbody><tr><th>$u_0$</th><td>0</td><td>1</td></tr><tr><th>$u_1$</th><td>1</td><td>0</td></tr></tbody></table>

<table><caption>Figure VI.12 – Decoder cost $c_d(u, v)$.</caption><thead><tr><th></th><th>$v_0$</th><th>$v_1$</th></tr></thead><tbody><tr><th>$u_0$</th><td>0</td><td>1 + $\kappa$</td></tr><tr><th>$u_1$</th><td>1</td><td>$\kappa$</td></tr></tbody></table>

The cost functions are given by Fig. VI.11 and VI.12 for which the extra cost $\kappa \in [0, 1]$ in the decoder cost may capture a computing cost, an energy cost, or the fact that an estimation error of the symbol $v_1$ is more harmful than an estimation error of the symbol $v_0$.

The optimal decision for the decoder depends on the posterior belief $Q_{U|WZ}(\cdot|w, z) \in \Delta(U)$ after observing the symbols $(w, z)$. We denote by $\gamma = \frac{1+\kappa}{2} = \frac{7}{8}$ the belief threshold at which the decoder changes from symbol $v_0$ to $v_1$, as in Fig. VI.13. The decoder chooses $v_0^*$ (resp. $v_1^*$) when the posterior belief belongs to $[0, \gamma]$ (resp. $]\gamma, 1]$).

The correlation of $(U, Z)$ is fixed whereas the correlation of $(U, W)$ is selected by the encoder. Lemma 6 formulates the posterior belief $Q_{U|WZ}$ in terms of the iterim belief $Q_{U|W}$. For the symbols $w \in W, z_0 \in Z, z_1 \in Z$ we have

$$ Q(u_1|w, z_0) = \frac{q\delta_1}{(1-q)(1-\delta_0) + q\delta_1} =: p_0(q), \quad (VI.46) $$

$$ Q(u_1|w, z_1) = \frac{q(1-\delta_1)}{(1-q)\delta_0 + q(1-\delta_1)} =: p_1(q). \quad (VI.47) $$
<figure><img src="image_58.png" /><figcaption>Figure VI.13 – Decoder’s expected cost $\mathbb{E}_p[c_d(U, v)] = (1-p) \cdot c_d(u_0, v) + p \cdot c_d(u_1, v)$ for $v \in \{v_0, v_1\}$ depending on the belief $Q(u_1|w, z) \in [0, 1]$.</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>Figure VI.14 – Equations (VI.46) and (VI.47), depending on the interim belief $q \in [0, 1]$, for $p_0 = 0.5$, $\delta_1 = 0.05$, $\delta_2 = 0.5$ and $\gamma = 0.875$.</figcaption></figure>

Equations (VI.46) and (VI.47) are depicted on Fig. VI.14. Given the belief threshold $\gamma = \frac{7}{8}$, we define $\nu_0$ and $\nu_1$ such that

$$ \gamma = p_0(\nu_0) \iff \nu_0 = \frac{\gamma(1 - \delta_0)}{\delta_1(1 - \gamma) + \gamma(1 - \delta_0)}, \qquad (VI.48) $$

$$ \gamma = p_1(\nu_1) \iff \nu_1 = \frac{\gamma \delta_0}{\gamma \delta_0 + (1 - \delta_1)(1 - \gamma)}. \qquad (VI.49) $$

Without loss of generality, we assume that $\delta_0 + \delta_1 < 1 \iff \nu_1 < \nu_0$. The robust and average cost functions writes

$$ \psi_e(p) = p \cdot \mathbb{1}(p \le \gamma) + (1-p) \cdot \mathbb{1}(p > \gamma), \qquad (VI.50) $$

$$ \Psi_e(q) = \mathrm{Pr}_q(z_0) \cdot \psi_e(p_0(q)) + \mathrm{Pr}_q(z_1) \cdot \psi_e(p_1(q)) \qquad (VI.51) $$

$$ = q \cdot \mathbb{1}(q \le \nu_1) + (1-q) \cdot \mathbb{1}(q > \nu_0) + (q\delta_1 + (1-q)\delta_0) \cdot \mathbb{1}(\nu_1 < q \le \nu_0). \qquad (VI.52) $$

The average cost function $\Psi_e(q)$ is depicted by the orange lines in Fig. VI.15 and Fig. VI.16, where the black curve is the average entropy $h(q) = H_b(q) + (1-q) \cdot H_b(\delta_0) + q \cdot H_b(\delta_1) - H_b((1-q)\delta_0 + q(1-\delta_1))$ and $H_b$ denotes the binary entropy.
<figure><img src="image_60.png" /><figcaption>Figure VI.15 – The optimal splitting has three posteriors when $C \in [0, H(U|Z) - h(q^*)]$, with $p_0 = 0.5$, $\delta_0 = \delta_1 = 0.3$, $C = 0.2$, $\kappa = 0$, then $C_e^* = 0.2098$.</figcaption></figure>

<figure><img src="image_61.png" /><figcaption>Figure VI.16 – The optimal splitting has only two posteriors when $C \in [H(U|Z) - h(q^*), H(U|Z)]$, with $p_0 = 0.5$, $\delta_0 = \delta_1 = 0.3$, $C = 0.4$, $\kappa = 0$, then $C_e^* = 0.1212$.</figcaption></figure>

The optimal splitting has posteriors $(q_1, q_2, q_3) \in [0, 1]^3$ with respective weights $(\lambda_1, \lambda_2, \lambda_3) \in [0, 1]^3$ that satisfy

$$1 = \lambda_1 + \lambda_2 + \lambda_3, \qquad (VI.53)$$

$$p_0 = \lambda_1 q_1 + \lambda_2 q_2 + \lambda_3 q_3, \qquad (VI.54)$$

$$H(U|Z) - C = \lambda_1 \cdot h(q_1) + \lambda_2 \cdot h(q_2) + \lambda_3 \cdot h(q_3). \qquad (VI.55)$$

Equation (VI.55) is satisfied when the information constraint is binding, therefore we obtain (Le Treust and Tomala, 2019, [J8], Eq. (58)-(60)). Without loss of generality, we assume that $q_1 \in [0, \nu_1[$, $q_2 \in [\nu_1, \nu_2[$, $q_3 \in [\nu_2, 1]$ and characterize the optimal solution in three different scenarios. According to the Splitting Lemma Aumann and Maschler (1995), we have for $k \in \{1, 2, 3\}$,

$$Q(w_k|u_0) = Q(w_k) \frac{1 - Q(u_1|w_k)}{1 - P(u_1)} = \lambda_k \frac{1 - q_k}{1 - p_0} = \alpha_k, \qquad (VI.56)$$

$$Q(w_k|u_1) = Q(w_k) \frac{Q(u_1|w_k)}{P(u_1)} = \lambda_k \frac{q_k}{p_0} = \beta_k. \qquad (VI.57)$$

## Wyner-Ziv's example with equal cost functions

We consider $p_0 = 0.5$, $\delta_0 = \delta_1 = 0.3$, $\kappa = 0$, hence both encoder and decoder minimize the Hamming cost and hence $\gamma = \frac{1}{2}$. The average cost and average entropy write

$$\Psi_e(q) = q \cdot \mathbb{1}(q \le \delta) + \delta \cdot \mathbb{1}(\delta < q \le 1 - \delta) + (1 - q) \cdot \mathbb{1}(q > 1 - \delta), \qquad (VI.58)$$

$$h(q) = H(U|Z) + H_b(q) - H_b(q \star \delta), \qquad (VI.59)$$
with the notation $q \star \delta = (1 - q)\delta + q(1 - \delta)$.

**Proposition 13** We denote by $q^*$ the unique solution to

$$h'(q) = \frac{H(U|Z) - h(q)}{\delta - q}. \qquad (VI.60)$$

1) If $C \in [0, H(U|Z) - h(q^*)]$ then at the optimum (Fig. VI.15)

$$q_1 = q^* = 1 - q_3, \quad q_2 = \frac{1}{2}, \qquad (VI.61)$$

$$\lambda_1 = \frac{1}{2} \cdot \frac{C}{H(U|Z) - h(q^*)} = \lambda_3 = \frac{1 - \lambda_2}{2}, \qquad (VI.62)$$

which correspond to the distribution parameters $\alpha_1 = (1-q^*) \cdot \frac{C}{H(U|Z)-h(q^*)} = \beta_3$, $\alpha_2 = 1-\frac{C}{H(U|Z)-h(q^*)} = \beta_2$, $\alpha_3 = q^* \cdot \frac{C}{H(U|Z)-h(q^*)} = \beta_1$, and to the optimal cost

$$C_e^* = \delta - C \cdot \frac{\delta - q^*}{H(U|Z) - h(q^*)}. \qquad (VI.63)$$

2) If $C \in [H(U|Z) - h(q^*), H(U|Z)]$ then at the optimum (Fig. VI.16) $q_1 = h^{-1}(H(U|Z) - C) = 1 - q_3$, $q_2 = \frac{1}{2}$, $\lambda_1 = \frac{1}{2} = \lambda_3$, $\lambda_2 = 0$, which correspond to the distribution parameters $\alpha_1 = 1 - h^{-1}(H(U|Z) - C) = 1 - \alpha_3 = \beta_3 = 1 - \beta_1$ and $\alpha_2 = \beta_2 = 0$ and to the optimal cost

$$C_e^* = h^{-1}(H(U|Z) - C), \qquad (VI.64)$$

where the notation $h^{-1}(H(U|Z) - C)$ stands for the unique solution $q \in [0, 1]$ of the equation $h(q) = H(U|Z) - C$.

3) If $C > H(U|Z)$, then the optimal splitting rely on the two extreme posterior beliefs $(0, 1)$ and $C_e^* = 0$.

<figure><img src="image_62.png" /><figcaption>Figure VI.17 – Optimal trade-off between the capacity C and the optimal cost $C_e^*$ for the DSBS with parameters $p_0 = 0.5$, $\delta_0 = \delta_1 = 0.3$, $\kappa = 0$.</figcaption></figure>

The proof of Proposition 13 is provided in (Le Treust and Tomala, 2019, [W3], App. D). When $C \le H(U|Z) - h(q^*)$, the optimal strategy consists of a time-sharing between $(C_e^*, C) = (q^*, H(U|Z) - h(q^*))$ and the zero rate point $(\delta, 0)$, as depicted in Fig. VI.17.

According to Fig. VI.15 and Fig. VI.16, the optimal distribution of the Wyner-Ziv problem for DSBS has two regimes, either with two posteriors or with three posteriors, i.e. with $|W| = 2$ or $|W| = 3$.

## Distinct cost functions without side information

We consider $p_0 = 0.5$, $C = 0.2$, $\kappa = \frac{3}{4}$ and $\delta_0 = \delta_1 = 0.5$ so that Z is independent of U, as in (Le Treust and Tomala, 2019, [J8]). We have $H_b(\delta_0) = H_b(\delta_1) = H_b((1-q)\delta_0 + q(1-\delta_1)) = 1$ and $\nu_1 = \nu_2 = \gamma = \frac{7}{8}$. The average entropy and average cost write

$$h(q) = H_b(q), \qquad (VI.65)$$

$$\Psi_e(q) = \psi_e(q) = p \cdot \mathbb{1}(p \le \gamma) + (1-p) \cdot \mathbb{1}(p > \gamma), \qquad (VI.66)$$
<figure><img src="image_63.png" /><figcaption>Figure VI.18 – For $p_0 = 0.5$, $\delta_0 = \delta_1 = 0.5$, $C = 0.2$, $\kappa = \frac{3}{4}$, $C_e^* = 0.2668$.</figcaption></figure>

and are depicted in Fig. VI.18. Applying (Le Treust and Tomala, 2019, [J8], Corollary 3.5), the optimal splitting has two posteriors, i.e. $|W| = 2$, and satisfy

$$ \frac{p_0 - q_2}{q_1 - q_2} \cdot H_b(q_1) + \frac{q_1 - p_0}{q_1 - q_2} \cdot H_b(q_2) \geq H(U) - C. \qquad (\text{VI.67}) $$

By numerical optimization, the above inequality is satisfied for $p_0 = 0.5$, $\delta_0 = \delta_1 = 0.5$, $C = 0.2$, $\kappa = \frac{3}{4}$, hence the optimal cost is achieved by using $q_2 = \gamma$, as in Fig. VI.18.

<figure><img src="image_64.png" /><figcaption>Figure VI.19 – $p_0 = 0.5$, $\delta_0 = 0.05$, $\delta_1 = 0.5$, $C = 0.2$, $\kappa = \frac{3}{4}$, $C_e^* = 0.1721$.</figcaption></figure>

## Distinct cost functions with side information

We consider $p_0 = 0.5$, $\delta_0 = 0.05$, $\delta_1 = 0.5$, $C = 0.2$, $\kappa = \frac{3}{4}$. By numerical simulation, we determine the optimal triple of posteriors ($q_1, q_2, q_3$) represented by the red dots in Fig. VI.19, corresponding to $C_e^* = 0.1721$. The parameters of the optimal strategy in Fig. VI.10, are given by the following table.

<table><tr><td>$q_1 = 0.0715$</td><td>$q_2 = 0.4118$</td><td>$q_3 = 0.9301$</td></tr><tr><td>$\lambda_1 = 0.1288$</td><td>$\lambda_2 = 0.6165$</td><td>$\lambda_3 = 0.2548$</td></tr><tr><td>$\alpha_1 = 0.2392$</td><td>$\alpha_2 = 0.7252$</td><td>$\alpha_3 = 0.0356$</td></tr><tr><td>$\beta_1 = 0.0184$</td><td>$\beta_2 = 0.5077$</td><td>$\beta_3 = 0.4739$</td></tr></table>
## VI.3 Bayesian persuasion with several decoders

In this section, we investigate the Bayesian persuasion problem with two decoders via a communication network of Gray and Wyner (1974), as in Fig. VI.20. The encoder may use three restricted communication channels. One channel of capacity $R_0$ is public, i.e. both decoder observe its output, and the two other channels of capacity $R_1$ and $R_2$ are private to each decoders. We assume that the encoder commits to an encoding strategy and the actions taken by each decoder do not affect the cost function of the other decoder.

Information design with multiple designers interacting with a set of agents is studied in Koessler et al. (2022). In Sarıtaş et al. (2017), Sarıtaş et al. (2019), the Nash equilibrium solution is investigated for multi-dimensional sources and quadratic cost functions, whereas the Stackelberg solution is studied in Sarıtaş et al. (2020). The strategic communication problem with a noisy channel is investigated in Akyol et al. (2015), Akyol et al. (2017). The case where the decoder privately observes a signal correlated to the state, also referred to as the setting of Wyner and Ziv (1976), is studied in Akyol et al. (2016), Bou Rouphael and Le Treust (2020) and Le Treust and Tomala (2021). Vora and Kulkarni investigate the achievable rates for the strategic communication problem in Vora and Kulkarni (2020), Vora and Kulkarni (2020) where the decoder is the Stackelberg leader.

<figure><img src="image_65.png" /><figcaption>Figure VI.20 – Gray-Wyner Network with Cost-Independent Decoders.</figcaption></figure>

### VI.3.a System model

In this section, we introduce the coding problem depicted in Fig VI.20.

**Definition 54** Let $R_0, R_1, R_2 \in \mathbb{R}_+^3 = [0, +\infty]^3$, and $n \in \mathbb{N}^* = \mathbb{N} \setminus \{0\}$. We denote by $M_0 \in \{1, ..2^{\lfloor nR_0 \rfloor}\}$, $M_1 \in \{1, ..2^{\lfloor nR_1 \rfloor}\}$, $M_2 \in \{1, ..2^{\lfloor nR_2 \rfloor}\}$ the random variables of the public and private messages send by the encoder and perfectly received by the decoders, as in Fig. VI.20.

The encoding function $\sigma$ and the decoding functions $\tau_i$ of the encoder $\mathcal{E}$ and decoders $\mathcal{D}_i$ for $i \in \{1, 2\}$ respectively, are given by

$$ \sigma : \mathcal{U}^n \to \Delta(\{1, ..2^{\lfloor nR_0 \rfloor}\} \times \{1, ..2^{\lfloor nR_1 \rfloor}\} \times \{1, ..2^{\lfloor nR_2 \rfloor}\}), \\ \tau_i : (\{1, 2, ..2^{\lfloor nR_0 \rfloor}\} \times \{1, 2, ..2^{\lfloor nR_i \rfloor}\}) \to \Delta(\mathcal{V}_i^n). $$

The coding triplets $(\sigma, \tau_1, \tau_2)$ are stochastic and induce a joint probability distribution

$$ \mathcal{P}_{U^n M_0 M_1 M_2 V_1^n V_2^n}^{\sigma, \tau_1, \tau_2} = \left( \prod_{t=1}^{n} \mathcal{P}_{U_t} \right) \mathcal{P}_{M_0 M_1 M_2 | U^n} \mathcal{P}_{V_1^n | M_0 M_1}^{\tau_1} \mathcal{P}_{V_2^n | M_0 M_2}^{\tau_2}. \quad (VI.68) $$

**Definition 55** Single-letter cost functions $c_e : \mathcal{U} \times \mathcal{V}_1 \times \mathcal{V}_2 \to \mathbb{R}$ of the encoder and $c_i : \mathcal{U} \times \mathcal{V}_i \to \mathbb{R}$ of
decoder $\mathcal{D}_i$ for $i \in \{1, 2\}$ induce Long-run cost functions $c_e^n(\sigma, \tau_1, \tau_2)$ and $c_i^n(\sigma, \tau_i)$,

$$c_e^n(\sigma, \tau_1, \tau_2) = \sum_{u^n, v_1^n, v_2^n} P_{U^n V_1^n V_2^n}^{\sigma, \tau_1, \tau_2}(u^n, v_1^n, v_2^n) \cdot \left[ \frac{1}{n} \sum_{t=1}^{n} c_e(u_t, v_{1,t}, v_{2,t}) \right],$$
$$c_i^n(\sigma, \tau_i) = \mathbb{E}_{\sigma, \tau_i} \left[ \frac{1}{n} \sum_{t=1}^{n} c_i(u_t, v_{i,t}) \right].$$

where $P_{U^n V_1^n V_2^n}^{\sigma, \tau_1, \tau_2}$ denotes the marginal distributions of $P^{\sigma, \tau_1, \tau_2}$ over the n-sequences $(U^n, V_1^n, V_2^n)$.

**Definition 56** Given $\sigma$ the set of best-responses strategies of decoder $\mathcal{D}_i$, $i \in \{1, 2\}$ is defined by

$$\mathrm{BR}_i(\sigma) = \{ \tau_i, \ c_i^n(\sigma, \tau_i) \le c_i^n(\sigma, \tilde{\tau}_i), \ \forall \tilde{\tau}_i \}. \qquad (\mathrm{VI}.69)$$

In case several pairs of strategies are best-responses, we consider the decoders select the worst $(\tau_1, \tau_2) \in \mathrm{BR}_1(\sigma) \times \mathrm{BR}_2(\sigma)$ for the encoder cost function. Given $(R_0, R_1, R_2) \in \mathbb{R}_+^3$ et $n \in \mathbb{N}^*$, the coding problem under study is defined by

$$C_e^n(R_0, R_1, R_2) = \inf_{\substack{\sigma \\ \tau_1 \in \mathrm{BR}_1(\sigma), \\ \tau_2 \in \mathrm{BR}_2(\sigma)}} \max_{\tau_1 \in \mathrm{BR}_1(\sigma)} c_e^n(\sigma, \tau_1, \tau_2). \qquad (\mathrm{VI}.70)$$

Equation (VI.70) corresponds to the persuasion game that plays as follow:

* The encoder $\mathcal{E}$ selects and announces the strategy $\sigma$.

* The sequence $U^n$ is drawn i.i.d. according to $\mathcal{P}_U$.

* The messages $(M_0, M_1, M_2)$ are encoded according to $\mathcal{P}_{M_0 M_1 M_2 | U^n}^\sigma$.

* The decoder $\mathcal{D}_1$ implements $\tau_1 \in \mathrm{BR}_1(\sigma)$: by knowing $\sigma$, it observes $(M_0, M_1)$, reactualises its Bayesian posterior belief $\mathcal{P}_{U^n | M_0 M_1}^\sigma$ and selects a sequence of actions $V_1^n$ that minimizes its expected cost function.

* Similarly, $\mathcal{D}_2$ implements $\tau_2 \in \mathrm{BR}_2(\sigma)$.

* We consider the players expected cost values given by $c_e^n(\sigma, \tau_1, \tau_2)$, $c_1^n(\sigma, \tau_1)$, $c_2^n(\sigma, \tau_2)$.

**Lemma 8** The sequence $(nC_e^n(R_0, R_1, R_2))_{n \in \mathbb{N}^*}$ is sub-additive, i.e. $\forall n, m \in \mathbb{Z}$, we have

$$(n+m)C_e^{n+m}(R_0, R_1, R_2) \le nC_e^n(R_0, R_1, R_2) + mC_e^m(R_0, R_1, R_2). \qquad (\mathrm{VI}.71)$$

To prove Lemma 8, we show that the concatenation of the strategy $\sigma^n$ that achieves $nC_e^n(R_0, R_1, R_2)$, with the strategy $\sigma^m$ that achieves $mC_e^m(R_0, R_1, R_2)$, leads to an upper bound on $(n+m)C_e^{n+m}(R_0, R_1, R_2)$.

## VI.3.b Main result

We investigate the asymptotic behaviour of $C_e^n(R_0, R_1, R_2)$.

**Definition 57** We consider three auxiliary random variables $W_0 \in \mathcal{W}_0$, $W_1 \in \mathcal{W}_1$ and $W_2 \in \mathcal{W}_2$ with $|\mathcal{W}_0| = |\mathcal{V}_1| \times |\mathcal{V}_2| + 1$ and $|\mathcal{W}_i| = |\mathcal{V}_i|$, for $i \in \{1, 2\}$. Given $(R_0, R_1, R_2) \in \mathbb{R}_+^3$, we define

$$\mathcal{Q}_0(R_0, R_1, R_2) = \left\{ \begin{array}{l} \mathcal{Q}_{W_0|U} \mathcal{Q}_{W_1|W_0U} \mathcal{Q}_{W_2|W_0U}, \quad R_0 \ge I(U; W_0), \\ R_0 + R_1 \ge I(U; W_1, W_0), \quad R_0 + R_2 \ge I(U; W_2, W_0) \end{array} \right\}, \qquad (\mathrm{VI}.72)$$

$$\tilde{\mathcal{Q}}_0(R_0, R_1, R_2) = \left\{ \begin{array}{l} \mathcal{Q}_{W_0 W_1 W_2 | U}, \quad R_0 \ge I(U; W_0), \\ R_0 + R_1 \ge I(U; W_1, W_0), \quad R_0 + R_2 \ge I(U; W_2, W_0) \end{array} \right\} \qquad (\mathrm{VI}.73)$$
A distribution in $Q_0(R_0, R_1, R_2)$ must satisfy the Markov chain property $W_1 \leftarrow (U, W_0) \leftarrow W_2$. For each $Q_{W_0W_1|U}$ and $Q_{W_0W_2|U}$, we define

$$Q_1(Q_{W_0W_1|U}) = \underset{Q_{V_1|W_0W_1}}{\operatorname{argmin}} \mathbb{E}[c_1(U, V_1)], \qquad (\text{VI.74})$$

$$Q_2(Q_{W_0W_2|U}) = \underset{Q_{V_2|W_0W_2}}{\operatorname{argmin}} \mathbb{E}[c_2(U, V_2)]. \qquad (\text{VI.75})$$

We define lower and upper bounds on the encoder optimal cost

$$C_e^*(R_0, R_1, R_2) = \inf_{\substack{Q_{W_0|U}, Q_{W_1|W_0|U}, Q_{W_2|W_0|U}, \\ \in Q_0(R_0, R_1, R_2)}} \max_{\substack{Q_{V_1|W_0W_1} \in Q_1(Q_{W_0W_1|U}), \\ Q_{V_2|W_0W_2} \in Q_2(Q_{W_0W_2|U})}} \mathbb{E}[c_e(U, V_1, V_2)], \qquad (\text{VI.76})$$

$$\tilde{C}_e(R_0, R_1, R_2) = \inf_{\substack{Q_{W_0W_1W_2|U}, Q_{V_1|W_0W_1} \in Q_1(Q_{W_0W_1|U}), \\ \in \tilde{Q}_0(R_0, R_1, R_2), Q_{V_2|W_0W_2} \in Q_2(Q_{W_0W_2|U})}} \max \mathbb{E}[c_e(U, V_1, V_2)]. \qquad (\text{VI.77})$$

Therefore the infimum in (VI.77) has a larger domain which implies $\tilde{C}_e(R_0, R_1, R_2) \le C_e^*(R_0, R_1, R_2)$.

**Lemma 9** If the encoder cost function satisfies

$$c_e(u, v_1, v_2) = c_{e1}(u, v_1) + c_{e2}(u, v_2), \quad \forall (u, v_1, v_2), \qquad (\text{VI.78})$$

for some $c_{e1}: \mathcal{U} \times \mathcal{V}_1 \mapsto \mathbb{R}$ and $c_{e2}: \mathcal{U} \times \mathcal{V}_2 \mapsto \mathbb{R}$, then

$$C_e^*(R_0, R_1, R_2) = \tilde{C}_e(R_0, R_1, R_2), \qquad (\text{VI.79})$$

for all $(R_0, R_1, R_2) \in \mathbb{R}_+^3$.

**Theorem 39** Let $(R_0, R_1, R_2) \in \mathbb{R}_+^3$, we have

$$\forall \varepsilon > 0, \exists \bar{n} \in \mathbb{N}, \forall n \ge \bar{n}, \quad C_e^n(R_0, R_1, R_2) \le C_e^*(R_0, R_1, R_2) + \varepsilon, \qquad (\text{VI.80})$$

$$\forall n \in \mathbb{N}, \quad C_e^n(R_0, R_1, R_2) \ge \tilde{C}_e(R_0, R_1, R_2). \qquad (\text{VI.81})$$

The proof of Theorem 39 is stated for the case $R_2 = 0$ in (Bou Rouphael and Le Treust, 2021, [IC28]) and (Bou Rouphael and Le Treust, 2022d, [W5]), and for the general case in (Bou Rouphael and Le Treust, 2022a, [NC5]). By applying Fekete's Lemma for the sub-additive sequence $(nC_e^n(R_0, R_1, R_2))_{n \in \mathbb{N}^*}$, for all $(R_0, R_1, R_2) \in \mathbb{R}_+^3$, we have

$$\tilde{C}_e(R_0, R_1, R_2) \le \lim_{n \to \infty} C_e^n(R_0, R_1, R_2) = \inf_{n \in \mathbb{N}^*} C_e^n(R_0, R_1, R_2) \le C_e^*(R_0, R_1, R_2).$$

## VI.4 Chapter summary

In this chapter, we characterize the optimal solutions of Bayesian persuasion games when the communication is passed through a noisy channel, when the decoder has side information and when there are two decoders and a common message.

In the scenarios with one encoder and one decoder, the optimal solution reformulates as the convexification of an auxiliary function, that depends on the decoder posterior beliefs. As a side result, this new formulation allows us to determine when Wyner-Ziv's auxiliary random variable for the DSBS, must be binary.
# Chapter VII

# Conclusion and perspectives

<figure><img src="image_66.png" /></figure>

Information is crucial in decision making problems, the information asymmetries in Game Theory raise new scenarios and new open questions. In this chapter, we present on-going research directions and a long-term perspectives that will deepen the connection between Game Theory and Information Theory, and also with Graph Theory and Convex Optimization.

In Sec. VII.1, we present some of Nicolas Charpenay's PhD contributions on zero-error source coding problems with decoder side information. This question is related to the long-standing open problem of the zero-error Shannon capacity of a graph, see Shannon (1956). We study the zero-error version of the coding for computing problem of Orlitsky and Roche (2001), by coloring an appropriate product of graphs. Nicolas's results are stated in (Charpenay et al., 2022b, [IC30]), (Charpenay and Le Treust, 2020, [IC25]), (Charpenay et al., 2022a, [NC11]), (Charpenay et al., 2022c, [W6]), (Charpenay et al., 2023, [W9]). In Sec. VII.2, we study the convex optimization problem of (IV.28) that involves the information constraint of Gossner et al. (2006), by using a recent convex optimization algorithm that computes efficiently the optimal cost. We will adapt this algorithm in order to compute the solution of various coordination solutions, stated in Chap. IV. In Sec. VII.3, we present a sender-receiver game in which the commitment is at the decoder side, instead of being at the encoder side. This assumption changes the strategic nature of the problem, it is a mechanism design problem, similar to the one of Jackson and Sonnenschein (2007), in which the communication is restricted. This problem can also be seen as a reformulation of the mismatched rate-distortion problem of Lapidoth (1997). The goal is to understand the incentive constraints of both players in order to generalize the cheap talk problem of Crawford and Sobel (1982).

## Contents

<table><tr><td>VII.1 Zero-error coding for computing problem</td><td>115</td></tr><tr><td>VII.1.a Problem statement</td><td>115</td></tr><tr><td>VII.1.b General setting</td><td>116</td></tr><tr><td>VII.1.c Pairwise shared side information</td><td>117</td></tr><tr><td>VII.2 Convex optimization algorithm for coordination problems</td><td>118</td></tr><tr><td>VII.2.a Problem formulation</td><td>118</td></tr><tr><td>VII.2.b Connection with Blahut-Arimoto's algorithm</td><td>119</td></tr><tr><td>VII.2.c Original optimization algorithm</td><td>120</td></tr><tr><td>VII.3 Mechanism design and cheap talk problems</td><td>120</td></tr><tr><td>VII.3.a System model</td><td>121</td></tr><tr><td>VII.3.b Upper bound</td><td>121</td></tr><tr><td>VII.4 Repeated games with imperfect monitoring and incomplete information</td><td>122</td></tr></table>
## VII.1 Zero-error coding for computing problem

Consider the source coding scenario depicted in Fig. VII.1 where two correlated sequences $(X^n, Y^n)$ of discrete i.i.d. random source symbols are drawn with a source distribution $P_{X,Y} \in \Delta(\mathcal{X} \times \mathcal{Y})$. The encoder knows the source sequence $X^n$, and has the sequence $(g(Y_t))_{t \le n}$ as side information, where $g$ is a deterministic function. The encoder transmits information to the decoder through a perfect channel of capacity $R \ge 0$. The decoder has the side information $Y^n$ and wants to reconstruct the sequence $(f(X_t, Y_t))_{t \le n}$, where $f$ is deterministic. What is the minimal capacity $R \ge 0$ such that $(f(X_t, Y_t))_{t \le n}$ can be retrieved by the decoder with probability of error 0?

<figure><img src="image_67.png" /><figcaption>Figure VII.1 – Zero-error coding for computing with side information at the encoder.</figcaption></figure>

This problem can be seen as a zero-error variant of the “coding for computing” problem of Orlitsky and Roche (2001) with side information at the encoder. This problem is difficult, as it has the “restricted inputs” zero-error problem of Alon and Orlitsky (1996) as a particular case, i.e. by taking $g$ constant and $f(X, Y) = X$.

More precisely, the optimal rate in “restricted inputs” is given by asymptotic chromatic entropies of graph products, for which no single-letter expression is known. It is shown in Koulgi et al. (2003) that this optimal rate is equal to the complementary graph entropy introduced in Körner and Longo (1973). In Marton (1993), the author show that finding a single-letter expression for the complementary graph entropy would give a single-letter formula for the Shannon capacity of a graph, see Shannon (1956), which is a wide open problem. Bounds for the “restricted inputs” zero-error setting can be obtained with achievability results in the “unrestricted inputs” zero-error setting of Alon and Orlitsky (1996), where $(X, Y)$ can take values outside the support of $P_{X,Y}$. For the “unrestricted inputs” case, the authors gave a single letter characterization of the optimal rate: the Körner graph entropy, introduced in Körner (1973).

Now the scheme of Fig. 1 has been studied for lossless, lossy and zero-error “unrestricted inputs” coding. More precisely, in Orlitsky and Roche (2001) the authors give a single-letter characterization of the lossless variant of this problem; in Yamamoto (1982), the author studies the lossy variant and determines the rate-distortion function; and the optimal rate in the zero-error “unrestricted inputs” based on an extension of the Körner graph entropy is characterized in Shayevitz (2014). The results from “unrestricted inputs” settings can only be used as bounds here: the zero-error “restricted inputs” problem depicted in Fig. VII.1 does not have a characterization of the optimal rate.

Under some hypothesis on $P_{X,Y}$ and $g$, we derive single letter characterization of the optimal rate. Our hypothesis, called “pairwise shared side information”, requires that every pair of source symbols “share” at least one side information symbol for all output of $g$. Under this hypothesis, we show that the characteristic graph is a disjoint union of OR products for which a single-letter characterization is available.

### VII.1.a Problem statement

Given the sequence length $n \in \mathbb{N}^*$, we denote by $\Delta_n(\mathcal{X}) \subset \Delta(\mathcal{X})$ the set of empirical distributions of sequences from $\mathcal{X}^n$. We denote by $\{0, 1\}^*$ the set of binary words. We say that two words $w \ne w'$ are not prefix if $w$ is not a prefix of $w'$ and $w'$ is not a prefix of $w$. Let $S \subset \{0, 1\}^*$, we say that $S$ is prefix-free if for all $w, w' \in S$, the words $w, w'$ are not prefix. The setting of Fig. VII.1 is described by:

* Four finite sets $\mathcal{X}, \mathcal{Y}, \mathcal{U}, \mathcal{Z}$, a tuple of random variables $(X, Y) \in \mathcal{X} \times \mathcal{Y}$ drawn from the distribution
$P_{X,Y}$ (with $P_X$ and $P_Y$ full-support), and deterministic functions

$$f: \mathcal{X} \times \mathcal{Y} \to \mathcal{U}, \qquad (VII.1)$$

$$g: \mathcal{Y} \to \mathcal{Z}. \qquad (VII.2)$$

* The encoder observes the realizations of $X^n$, $(g(Y_t))_{t \le n}$ and sends information to the decoder over a noiseless channel of capacity $R \ge 0$.

* The decoder recover $(f(X_t, Y_t))_{t \le n}$ based on the encoder message and the side information $Y^n$.

**Definition 58 (Zero-error source code, achievable rates)** Given $n \in \mathbb{N}^*$, a $(n, R_n)$-zero-error source code consists of an encoding function $\phi_e: \mathcal{X}^n \times \mathcal{Z}^n \to \{0,1\}^*$ and a decoding function $\phi_d: \mathcal{Y}^n \times \{0,1\}^* \to \mathcal{U}^n$ such that:

1. the set $\phi_e(\mathcal{X}^n \times \mathcal{Z}^n)$ is prefix-free;

2. $R_n = \frac{1}{n}\mathbb{E}[l \circ \phi_e(X^n, (g(Y_t))_{t \le n})]$, where $l(\cdot)$ denotes the length of a binary word;

3. the “restricted inputs” zero-error property is satisfied:

$$\forall (x^n, y^n) \in \text{supp} P_{X,Y}^n, \quad \phi_d(y^n, \phi_e(x^n, (g(y_t))_{t \le n})) = (f(x_t, y_t))_{t \le n}. \qquad (VII.3)$$

A rate $R$ is achievable if there exists a sequence of $(n, R_n)$-zero-error source codes such that $\lim_{n} R_n = R$. The optimal rate is denoted by $R^* = \inf\{R \ge 0 \mid R \text{ is achievable}\}$.

The prefix-free hypothesis guarantees that the decoder knows when the encoder's message stops and decode correctly with probability one.

### VII.1.b General setting

A probabilistic graph $G$ is a tuple $(\mathcal{V}, \mathcal{E}, P_V)$, where $\mathcal{V}$ is the set of vertices, $\mathcal{E}$ is the set of edges, and $P_V \in \Delta(\mathcal{V})$ is an underlying probability distribution on the vertices. A graph coloring is a mapping that assigns different colors to adjacent vertices. We will make use of graph colorings as the colorings of a specific graph correspond directly to zero-error encoding functions.

**Definition 59 (Coloring, independent subset)** Let $G = (\mathcal{V}, \mathcal{E}, P_V)$ be a probabilistic graph. A subset $S \subseteq \mathcal{V}$ is independent if $xx' \notin \mathcal{E}$ for all $x, x' \in S$. Let $C$ be a finite set (the set of colors), a mapping $c: \mathcal{V} \to C$ is a coloring if $c^{-1}(i)$ is an independent subset for all $i \in C$.

**Definition 60 (Chromatic entropy $H_\chi$)** The chromatic entropy of a probabilistic graph $G = (\mathcal{V}, \mathcal{E}, P_V)$ is defined by

$$H_{\chi}(G) = \inf \{ H(c(V)) \mid c \text{ is a coloring of } G \}. \qquad (VII.4)$$

The chromatic entropy of a probabilistic graph is the smallest entropy of a coloring of that graph. As in Witsenhausen (1976), we build the characteristic graph $G_{[n]}$ that captures the zero-error encoding constraints on a given number $n$ of source uses.

**Definition 61 (Characteristic graph $G_{[n]}$)** The characteristic graph $G_{[n]}$ is defined by:

* $\mathcal{X}^n \times \mathcal{Z}^n$ as set of vertices with distribution $P_{\mathcal{X},g(Y)}^n$,

* $(x^n, z^n)(x'^n, z'^n)$ are adjacent if $z^n = z'^n$ and there exists $y^n \in g^{-1}(z^n)$ such that:

$$\forall t \le n, P_{X,Y}(x_t, y_t)P_{X,Y}(x'_t, y_t) > 0, \qquad (VII.5)$$

$$\text{and } \exists t \le n, f(x_t, y_t) \ne f(x'_t, y_t); \qquad (VII.6)$$

where $g^{-1}(z^n) = \{y^n \in \mathcal{Y}^n \mid (g(y_t))_{t \le n} = z^n\}$ is the preimage of $z^n$.
The characteristic graph $G_{[n]}$, differs from the graphs used in Shayevitz (2014), as we do not need a cartesian representation of these graphs to study the optimal rates. Furthermore, it has vertices that correspond to the possible realizations of $(X^n, (g(Y_t))_{t \le n})$ known at the encoder, instead of $\mathcal{X}^n$ like in Witsenhausen (1976) and Alon and Orlitsky (1996). It is also designed to take $f$ and $g$ into account, with the same core idea: if two pairs of symbols $(x^n, z^n)$, $(x'^n, z'^n)$ are adjacent in $G_{[n]}$, then the encoder must map them to different codewords, otherwise the decoder will decode erroneously with positive probability.

**Theorem 40 (Optimal rate in general setting)** *The optimal rate writes:*

$$R^* = \lim_{n \to \infty} \frac{1}{n} H_X(G_{[n]}). \qquad (VII.7)$$

A general single-letter expression for $R^*$ is missing, due to the lack of intrinsic structure of $G_{[n]}$. In Section VII.1.c, we introduce a hypothesis called “pairwise shared side information”, that gives structure to $G_{[n]}$ and allows us to derive a single-letter expressions for $R^*$.

**Remark 31** In the case $f(X, Y) = X$ and $g$ constant, we obtain the “restricted inputs” source coding problem from Alon and Orlitsky (1996). The adjacency condition in the graph $G_{[n]}$ becomes:

$$x^n x'^n \text{ are adjacent if } x^n \neq x'^n \text{ and } \forall t \le n, \exists y_t \in \mathcal{Y}, P_{X,Y}(x_t, y_t) P_{X,Y}(x'_t, y_t) > 0. \qquad (VII.8)$$

## VII.1.c Pairwise shared side information

**Definition 62** The distribution $P_{X,Y}$ and the function $g$ satisfy the “pairwise shared side information” if

$$\forall z \in \mathcal{Z}, \forall x, x' \in \mathcal{X}, \exists y \in g^{-1}(z), P_{XY}(x, y) P_{XY}(x', y) > 0. \qquad (VII.9)$$

Every pair of source symbols “share” at least one side information symbol for all output of $g$.

Note that any distribution $P_{X,Y}$ with full support satisfies the “pairwise shared side information” hypothesis.

**Definition 63 (Characteristic graph $G_z^f$)** For all $z \in \mathcal{Z}$, we define the characteristic graph $G_z^f$ by

* $\mathcal{X}$ as set of vertices with distribution $P_{X|g(Y)=z}$,

* $xx'$ are adjacent if $f(x, y) \neq f(x', y)$ for some $y \in g^{-1}(z) \cap \text{supp } P_{Y|X=x} \cap \text{supp } P_{Y|X=x'}$.

Under the “restricted inputs” assumption of Alon and Orlitsky (1996) (resp. “unrestricted inputs”), the n-shot characteristic graph can be expressed as an iterated AND (resp. OR) product of the one-shot characteristic graph.

**Definition 64 (AND, OR product)** Let $G_1 = (\mathcal{V}_1, \mathcal{E}_1, P_{V_1})$, $G_2 = (\mathcal{V}_2, \mathcal{E}_2, P_{V_2})$ be two probabilistic graphs; their AND (resp. OR) product denoted by $G_1 \wedge G_2$ (resp. $G_1 \vee G_2$) is defined by: $\mathcal{V}_1 \times \mathcal{V}_2$ as set of vertices, $P_{V_1}P_{V_2}$ as probability distribution on the vertices, and $(v_1v_2), (v'_1v'_2)$ are adjacent if

$$v_1v'_1 \in \mathcal{E}_1 \text{ AND } v_2v'_2 \in \mathcal{E}_2, \qquad (VII.10)$$

resp. $(v_1v'_1 \in \mathcal{E}_1 \text{ and } v_1 \neq v'_1)$ OR $(v_2v'_2 \in \mathcal{E}_2 \text{ and } v_2 \neq v'_2)$;

with the convention that all vertices are self-adjacent. We denote by $G_1^{\wedge n}$ (resp. $G_1^{\vee n}$) the n-th AND (resp. OR) power.

Introduced in Körner (1973), the Körner graph entropy relates to the limit of the normalized chromatic entropy of an OR product of graphs.
**Definition 65** For all probabilistic graph $G = (\mathcal{V}, \mathcal{E}, P_V)$, let $\Gamma(G)$ be the collection of independent sets of vertices in $G$. The Körner graph entropy of $G$ is defined by

$$H_{\kappa}(G) = \min_{V \in W \in \Gamma(G)} I(W; V), \qquad (VII.11)$$

where the minimum is taken over all distributions $P_{W|V} \in \Delta(\mathcal{W})^{\mathcal{V}}$, with $\mathcal{W} = \Gamma(G)$ and with the constraint that the random vertex $V$ belongs to the random independent set $W$ with probability 1; this is denoted by $V \in W \in \Gamma(G)$ in (VII.11).

**Proposition 14** (Alon and Orlitsky, 1996, Theorem 5) For all probabilistic graphs $G$ and $G'$,

$$H_{\kappa}(G) = \lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\vee n}), \qquad (VII.12)$$

$$H_{\kappa}(G \vee G') = H_{\kappa}(G) + H_{\kappa}(G'). \qquad (VII.13)$$

There does not exists such a characterization for $\lim_{n \to \infty} \frac{1}{n} H_{\chi}(G^{\vee n})$ defined with respect to the AND product. By using a convex combination of Körner graph entropies, we provide a single-letter expression for the optimal rate $R^*$.

**Theorem 41 (Optimal rate with pairwise shared side information)** If $P_{X,Y}$ and $g$ satisfy (VII.9), the optimal rate writes:

$$R^* = \sum_{z \in \mathcal{Z}} P_{g(Y)}(z) H_{\kappa}(G_z^f). \qquad (VII.14)$$

The proof of Theorem 41 is stated in (Charpenay et al., 2023, [W8]).

**Perspective 1** Nicolas Charpenay's PhD research work focuses on zero-error coding for computing problems with two-sided state information. We will further investigate several extensions of this problem, e.g. by considering the joint source-channel coding and the coding with secrecy constraints.

**Perspective 2** Zero-error problems in Information Theory raise new questions in Graph Theory and in Combinatorial Optimization. We will investigate the design of algorithms in order to compute the obtained graph-based solutions, as in (VII.14).

## VII.2 Convex optimization algorithm for coordination problems

In this section, we propose a numerical approach for solving the cost optimization problem of (IV.28) in the empirical coordination framework, under the information constraint $I(U; V) \le H(X|U, V)$ of Gossner et al. (2006). This is a joint work with Luis Briceño Arias, Associate Prof. at Univ. Técnica Federico Santa María, Santiago, Chile and member of CMM IRL 2807.

### VII.2.a Problem formulation

**Problem 1** Let $\mathcal{U}$, $\mathcal{X}$, and $\mathcal{V}$ be nonempty finite sets such that $|\mathcal{X}| \ge 2$ and, let $(c_{xv}^u)_{u \in \mathcal{U}, x \in \mathcal{X}}_{v \in \mathcal{V}}$ that corresponds to the cost function $c: \mathcal{U} \times \mathcal{X} \times \mathcal{V} \to \mathbb{R}$ and denote by $p = (p_u)_{u \in \mathcal{U}} = P_U \in \text{ri} \Delta(\mathcal{U})$ the source distribution, where ri stands for the relative interior. The problem is to

$$\underset{q \in \mathcal{C}}{\text{minimize}} \quad \sum_{u,x,v} p_u c_{xv}^u q_{xv}^u, \qquad (VII.15)$$

where

$$C = \left\{ q \in \Delta(\mathcal{X} \times \mathcal{V})^{|\mathcal{U}|} \mid \sum_{u,x,v} p_u q_{xv}^u \ln \left( \frac{q_{xv}^u}{\sum_{x',u'} p_{u'} q_{x'v}^{u'}} \right) \le 0 \right\} \qquad (VII.16)$$

with the convention $0 \cdot \ln 0 = 0$ and the logarithm has basis e.
Problem 1 belongs to the class of optimization problems under entropy constraints, that comes to light in several fields such as Information Theory via *rate-distortion problems* Shannon (1959), *coordination problems* Cuff et al. (2010); Cuff and Zhao (2011); (Le Treust, 2017, [J6]), see Chap IV, in Economics via *rational inattention problems* Sims (2003), *Bayesian persuasion problems* (Le Treust and Tomala, 2019, [J8]) and *Repeated Games with asymmetric information* Gossner et al. (2006), with *finite automata and bounded recall* Neyman and Okada (1999, 2000), with *private observation* Gossner and Vieille (2002), or with *imperfect monitoring* Gossner et al. (2009); Gossner and Tomala (2006, 2007).

We now interpret Problem (1). For every $(u, x, v) \in \mathcal{U} \times \mathcal{X} \times \mathcal{V}$, the variable $q_{xv}^u$ represents a target conditional probability of $(x, v)$ given $u$, thus the objective function is the expected cost with respect to the joint probability distribution $\{p_u q_{xv}^u\}_{xv}^u \in \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{V})$. In Gossner et al. (2006), the authors prove that the probability distribution $\{p_u q_{xv}^u\}_{xv}^u$ satisfies the non-linear constraint of (VII.16) if and only if there exists a coding strategy $(\sigma, \tau) \in \Sigma$ that induces an empirical distribution over the sequences $(u_t, x_t, v_t)_{t \in \mathbb{N}^*} \in \mathcal{U}^\infty \times \mathcal{X}^\infty \times \mathcal{V}^\infty$, that converges to $\{p_u q_{xv}^u\}_{xv}^u$. We denote by $U, X, V$ the random variables drawn according to $\{p_u q_{xv}^u\}_{xv}^u$, thus the function appearing in (VII.16) reformulates as:

$$ \sum_{u,x,v} p_u q_{xv}^u \ln \left( \frac{q_{xv}^u}{\sum_{x',u'} p_{u'} q_{x'v}^{u'}} \right) = I(U;V) - H(X|U,V), \qquad (VII.17) $$

where

$$ I(U;V) = \sum_{u,x,v} p_u q_{xv}^u \ln \frac{\sum_{a',v'} q_{x'v}^s}{\sum_{x',u'} p_{u'} q_{x'v}^{u'}} \quad \text{and} \quad H(X|U,V) = \sum_{u,x,v} p_u q_{xv}^u \ln \frac{\sum_{a',v'} q_{x'v}^s}{q_{xv}^u} \qquad (VII.18) $$

have the following interpretation: the mutual information $I(U;V)$ measures the correlation between random variables $V$ and $U$; the conditional entropy $H(X|U,V)$ measures the capacity of a perfect channel where the input $X$ must be correlated with $(U, V)$. More details are stated in Chap. III and IV.

## VII.2.b Connection with Blahut-Arimoto's algorithm

Now assume that, for every $(u, x, v) \in \mathcal{U} \times \mathcal{X} \times \mathcal{V}$, $c_{xv}^u = c_v^u \in \mathbb{R}$ and define $q_v^u := \sum_x q_{xv}^u$. In this particular instance, it can be proved that Problem 1 is equivalent to

$$ \min_{q \in \Xi} \sum_{u,v} p_u c_v^u q_v^u, \qquad (VII.19) $$

where

$$ \Xi = \left\{ q \in \Delta(\mathcal{V})^{|\mathcal{U}|} \mid \sum_{u,v} p_u q_v^u \ln \left( \frac{q_v^u}{\sum_{u'} p_{u'} q_{v'}^{u'}} \right) \le \ln |\mathcal{X}| \right\}. $$

This problem is deeply related to the Shannon's lossy source coding problem (see, e.g., (Cover and Thomas, 2006, Chap. 10)) where the non-linear constraint reformulates as: $I(\mathcal{V};U) - \ln |\mathcal{X}| \le 0$. The set of solutions of (VII.19) is nonempty (El Gamal and Kim, 2011, Section 3.6.1) and every solution $q^*$ to (VII.19) satisfies

$$ (\forall v \in \mathcal{V})(\forall u \in \mathcal{U}) \quad q_v^{u*} = \frac{t_v^* e^{-c_v^u / \lambda^*}}{\sum_{v'} t_{v'}^* e^{-c_{v'}^u / \lambda^*}}, \qquad (VII.20) $$

where

$$ (\forall v \in \mathcal{V}) \quad t_v^* = \sum_u p_u q_v^{u*} $$

and $\lambda^* \ge 0$ is the Lagrange multiplier associated to the nonlinear constraint. In Arimoto (1972); Blahut (1972), the authors provide an algorithm for solving (VII.19) whose convergence is proved in (Csiszár,
1974, Theorem 1). Given a starting probability $(t_{v,0})_{v \in \mathcal{V}} \in \Delta(\mathcal{V})$, the algorithm iterates

$$ \text{For } n = 0, 1, 2, \dots \qquad (\text{VII.21}) $$

$$ \left| \left| \begin{array}{ll} \text{For } v \in \mathcal{V} & \\ \text{For } u \in \mathcal{U} & \\ \left| \begin{array}{l} q_{v,n}^u = \frac{t_{v,n} e^{-c_u^u / \lambda^*}}{\sum_{v'} t_{v',n} e^{-c_{v'}^u / \lambda^*}} \\ t_{v,n+1} = \sum_u p_u q_{v,n}^u \end{array} \right. & (\text{VII.22}) \\ \end{array} \right| \right. $$

Note that, in order to solve (VII.19), the previous algorithm needs the Lagrange multiplier $\lambda^*$, which is not known a priori. In order to estimate $\lambda^*$ usually some heuristics, as bisection methods, are implemented. This means that Blahut-Arimoto's algorithm has to be implemented for several values of $\lambda$. As far as we know, the problem (VII.19) cannot be solved directly by methods proposed in the literature without adding additional loops for estimating $\lambda^*$.

### VII.2.c Original optimization algorithm

Problem 1 has been solved explicitly for a specific cost function with $|\mathcal{U}| = |\mathcal{X}| = |\mathcal{V}| = 2$ (Gossner et al., 2006, Example 2.1) but, it seems that Problem 1 has not been explicitly found in its whole generality. On the other hand, since the set $C$ is convex and the objective function is smooth (even linear), Problem 1 can be solved by the projected gradient method. However, this algorithm needs to compute efficiently the projection onto $C$, which is not easy in our case.

**Perspective 3** We will provide an explicit optimization algorithm that exploits the structure of the problem for solving it.

**Perspective 4** We will generalize our optimization algorithm by considering the information constraints of the various scenario of Chap. IV, corresponding to Theorems 6, 9-18.

### VII.3 Mechanism design and cheap talk problems

We consider the sender-receiver game described in Fig. VII.2. In the Bayesian persuasion game of Kamenica and Gentzkow (2011), see Chap. VI, the encoder commits to implementing a strategy, as the leader of the Stackelberg game.

In this section, it is the decoder that is the leader of the Stackelberg game, i.e. the decoder commits to implement a decoding strategy before the game plays. This new model is closely related to the mechanism design of Jackson and Sonnenschein (2007) and to the lossy source coding with mismatch distortion functions of Lapidoth (1997).

By studying the mechanism design problem, we investigate the incentive constraints of the decoder. Then, the goal will be to characterize the set of the Nash equilibria of the cheap talk game, as in Crawford and Sobel (1982). A detailed study of the incentive constraints of both encoder and decoder is mandatory.

<figure><img src="image_68.png" /><figcaption>Figure VII.2 – The source $(\mathcal{U}, \mathcal{P}_U)$ is i.i.d. and the channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|X})$ is memoryless. The encoder and the decoder are endowed with distinct cost functions $c_e(u, v) \neq c_d(u, v)$.</figcaption></figure>
### VII.3.a System model

We consider an i.i.d. information source $(\mathcal{U}, \mathcal{P}_U)$ and a memoryless channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{\mathcal{Y}|\mathcal{X}})$, as depicted in Fig. VII.2.

**Definition 66** We define the encoding and decoding strategies by

$$ \sigma: \mathcal{U}^n \to \Delta(\mathcal{X}^n), \qquad (VII.23) $$

$$ \tau: \mathcal{Y}^n \to \Delta(\mathcal{V}^n). \qquad (VII.24) $$

The strategies $(\sigma, \tau)$ induce a distribution defined by

$$ \mathcal{P}_{U^n X^n Y^n V^n}^{\sigma, \tau} = \left( \prod_{t=1}^{n} \mathcal{P}_{U_t} \right) \sigma_{X^n|U^n} \left( \prod_{t=1}^{n} \mathcal{T}_{Y_t|X_t} \right) \tau_{V^n|Y^n}, \qquad (VII.25) $$

where $\sigma_{X^n|U^n}$, $\tau_{V^n|Y^n}$ denote the distributions of $\sigma$, $\tau$.

**Definition 67** The encoder and decoder cost functions $c_e: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ and $c_d: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ induce long-run cost functions $c_e^n(\sigma, \tau)$ and $c_d^n(\sigma, \tau)$ defined by

$$ c_e^n(\sigma, \tau) = \mathbb{E}_{\sigma, \tau} \left[ \frac{1}{n} \sum_{t=1}^{n} c_e(U_t, V_t) \right], \qquad (VII.26) $$

$$ c_d^n(\sigma, \tau) = \sum_{u^n, v^n} \mathcal{P}_{U^n V^n}^{\sigma, \tau}(u^n, v^n) \cdot \left[ \frac{1}{n} \sum_{t=1}^{n} c_d(u_t, v_t) \right]. \qquad (VII.27) $$

**Definition 68** Given $n \in \mathbb{N}^*$, we define

1. the set of encoder best responses to strategy $\tau$ by

$$ \mathcal{B}\mathcal{R}_e(\tau) = \underset{\sigma}{\operatorname{argmin}} c_e^n(\sigma, \tau), \qquad (VII.28) $$

2. the long-run decoder cost value by

$$ C_d^n = \inf_{\tau} \max_{\sigma \in \mathcal{B}\mathcal{R}_e(\tau)} c_d^n(\sigma, \tau). \qquad (VII.29) $$

The value $C_d^n$ corresponds to the optimal cost of the decoder for fixed $n \in \mathbb{N}^*$. In case there are several best responses, we assume the encoder selects the worst strategy $\sigma$ for the decoder cost. We aim at characterizing the asymptotic behaviour of $C_d^n$.

### VII.3.b Upper bound

**Definition 69** Given an auxiliary random variable $W \in \mathcal{W}$ with $|\mathcal{W}| = \min(|\mathcal{U}|+1, |\mathcal{V}|)$ with distribution $P_W$, we define

$$ \mathbb{P}(P_W) = \{ Q_{UW} \in \Delta(\mathcal{U} \times \mathcal{W}), \ Q_U = P_U, \ Q_W = P_W, \ \max_{P_X} I(X; Y) - I(U; W) \ge 0 \}. \qquad (VII.30) $$

Given $P_{WV}$, we define the single-letter encoder best responses

$$ \mathbb{A}_e(P_{WV}) = \underset{Q_{UW} \in \mathcal{P}(P_W)}{\operatorname{argmin}} \mathbb{E}_{\mathcal{P}_{V|W}} [c_e(U, V)]. \qquad (VII.31) $$

The decoder optimal cost $C_d^*$ is given by

$$ C_d^* = \inf_{P_{WV}} \max_{\substack{Q_{UW} \in \mathcal{P}_{WV} \\ \mathcal{A}_e(P_{WV})}} \mathbb{E}_{\mathcal{P}_{V|W}} [c_d(U, V)]. \qquad (VII.32) $$
In (VII.32), it is the decoder, i.e. the Stackelberg leader, who selects the marginal distribution $P_W$, whereas the incentive constraints affect the Stackelberg follower, i.e. the encoder. In both settings, the encoder selects the distribution $Q_{UW} \in \mathbb{P}(P_W)$ that satisfies the information constraint and the decoder selects $P_{V|W}$.

**Theorem 42 (Achievability)**

$$ \forall \varepsilon > 0, \exists \tilde{n} \in \mathbb{N}^*, \forall n \ge \tilde{n}, \quad C_d^n \le C_d^* + \varepsilon. \qquad (VII.33) $$

The achievability proof of Theorem 42, see (Le Treust and Tomala, 2020, [IC26]), relies on similar arguments as in (Lapidoth, 1997, Step 1) and (Scarlett et al., 2020, Lemma 4.3). The sequence $(nC_d^n)_{n \in \mathbb{N}^*}$ is sub-additive, thus Theorem 42 and Fekete's lemma show that

$$ C_d^* \ge \lim_{n \to +\infty} C_d^n = \inf_{n \in \mathbb{N}^*} C_d^n. \qquad (VII.34) $$

**Perspective 5** We investigate the converse argument in order to show that

$$ \forall n \in \mathbb{N}^*, \quad C_d^* \le C_d^n. \qquad (VII.35) $$

We already know that (VII.35) is valid under several hypotheses: when the encoder cost function $c_e(u, v)$ does not depend on the state variable $u \in \mathcal{U}$, when $c_e(u, v) = -c_d(u, v)$ or when $|\mathcal{U}| = |\mathcal{V}| = 2$.

**Perspective 6** Inspired by the model of Crawford and Sobel (1982), the cheap talk version of this problem corresponds to the scenario where neither the encoder nor the decoder is able to commit to a strategy. We will investigate the cheap talk solution of this problem when the communication is passed through an arbitrary channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|\mathcal{X}})$. The goal is to build a theory that encompasses the standard results for the joint source-channel coding problem in Information Theory, see Shannon (1948, 1959), and for the repeated sender-receiver game model, see Crawford and Sobel (1982), Kamenica and Gentzkow (2011), Jackson and Sonnenschein (2007).

## VII.4 Repeated games with imperfect monitoring and incomplete information

The information asymmetries in Game Theory raise new communication scenarios and new open questions. In a general formulation of the problem, each player $P_k$, $k \in \mathcal{K}$ senses its environment, observes signals $s_k$ that depend on the system state $s_0$ and signals $y_k$ that depend on the actions of the other players, and takes action $a_k$ in order to minimize its own cost function $c_k(s_0, a_1, \dots, a_k)$, as depicted in Fig. VII.3.

<figure><img src="image_69.png" /><figcaption>Figure VII.3 – Repeated game with imperfect monitoring and incomplete information. The states are distributed according to $P_{S_0S_1S_2} \in \Delta(S_0 \times S_1 \times S_2)$ and the observation structure $\mathcal{T}_{Y_1Y_2|S_0A_1A_2} \in \Delta(\mathcal{Y}_1 \times \mathcal{Y}_2)|_{S_0 \times A_1 \times A_2}$ depends on the state $s_0$. The players have distinct cost functions $c_1: S_0 \times A_1 \times A_2 \to \mathbb{R}$ and $c_2: S_0 \times A_1 \times A_2 \to \mathbb{R}$.</figcaption></figure>
Repeated game models focus on incentives of players involved in long-term interactions, see Sorin (1992) and Mertens et al. (2015). The players strategies induce sequences of actions which are evaluated via long-term average cost functions. The perfect monitoring of the actions is crucial to incite the players to cooperate and make the threat of long-term punishment credible. Indeed, the set of Nash equilibrium costs in repeated games of imperfect monitoring is unknown. In Lehrer (1991), the players use the observation structure, e.g. $T_{Y_1Y_2|S_0A_1A_2}$ in Fig. VII.3, in order to construct a correlation device robust to unilateral deviations, that induces a correlated equilibrium, see Aumann (1974). Note that a correlated equilibrium is a Nash equilibrium of an extended game, in which players observe correlated signals before choosing their actions.

**Perspective 7** We will revisit the jointly controlled correlation procedure of Lehrer (1991) through the lens of Information Theory. By using coding arguments, we will try to describe the set of correlation devices robust to the unilateral deviations, that the players can induce via their sequence of plays, when they have imperfect monitoring.

The players are said to have *incomplete information* when the cost functions depend on a state variable which is uncertain to some players, as in Fig. VII.3. In a repeated game of incomplete information, see Aumann and Maschler (1995), Forges (1992), and Renault (2012), the state variable remains fixed along the course of the game, whereas it evolves dynamically in response of the players’ actions in stochastic repeated games, see Neyman and Sorin (2003).

The concept of communication equilibrium, introduced in Forges (1986) and Myerson (1986), generalizes the notion of Nash equilibrium and correlated equilibrium. After partially observing the state variable, the players communicate via a communication device that generates correlated signals before they select their actions.

**Definition 70** A communication device $(\{\mathcal{X}_k\}_{k \in \mathcal{K}}, \{\mathcal{Y}_k\}_{k \in \mathcal{K}}, T_{Y|X})$ is a collection of inputs $\{\mathcal{X}_k\}_{k \in \mathcal{K}}$ and outputs $\mathcal{Y}_k$, for each player $k \in \mathcal{K}$, and a conditional probability distribution $T_{Y|X} \in \Delta(\mathcal{Y})^{|\mathcal{X}|}$ where $\mathcal{X} = \prod_{k \in \mathcal{K}} \mathcal{X}_k$ and $\mathcal{Y} = \prod_{k \in \mathcal{K}} \mathcal{Y}_k$.

In the two-player case, the communication device of Def. 70 is a two-way channel, see Han (1984), for which the capacity region is unknown. A communication device is also referred to as the multi-way channel, see van der Meulen (1977).

For infinitely repeated game with imperfect monitoring, the set of communication equilibrium costs is characterized in Renault and Tomala (2004). Such a characterization is not available for Nash and correlated equilibria. The authors reformulate the communication equilibrium of a $|\mathcal{K}|$ players repeated game by using a correlated equilibrium of an auxiliary two-player repeated game, for which the solution is characterized in Lehrer (1992).

**Perspective 8** The communication equilibrium concept of Forges (1986) and Myerson (1986) gave us keys to understand the strategic aspects in games with imperfect monitoring and incomplete information. To which extend is it possible to implement a communication equilibrium when the players have a restricted number of available messages? Are such capacity restrictions useful for characterizing the sets of correlated equilibria and Nash equilibria solution? We will explore the impact of the restricted number of messages for communication devices through the lens of information theoretical results for the two-way channel, see Han (1984) and for the multiway channel, see van der Meulen (1977).