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

HAL
open science

# Coordination et Communication Stratégique

Mael Le Treust

► To cite this version:

Mael Le Treust. Coordination et Communication Stratégique. Théorie de l'information [cs.IT]. CY Cergy Paris Université, 2022. tel-03896253

HAL Id: tel-03896253

https://hal.science/tel-03896253

Submitted on 13 Dec 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Coordination et Communication Stratégique

dont la soutenance s'est tenue le mardi 29 novembre 2022 à 14h devant le jury :

<table><tr><td>Iryna</td><td>Andriyanova</td><td>Professeure Univ. CY</td><td>Référente CY</td></tr><tr><td>Pierre</td><td>Duhamel</td><td>Directeur de Recherche CNRS L2S</td><td>Examinateur</td></tr><tr><td>Inbar</td><td>Fijalkow</td><td>Professeure ENSEA</td><td>Garante HDR</td></tr><tr><td>Françoise</td><td>Forges</td><td>Professeure Univ. Paris-Dauphine</td><td>Rapporteure</td></tr><tr><td>Jean-Marie</td><td>Gorce</td><td>Professeur INSA Lyon</td><td>Examinateur</td></tr><tr><td>Olivier</td><td>Gossner</td><td>Directeur de Recherche CNRS CREST</td><td>Examinateur</td></tr><tr><td>Mikael</td><td>Skoglund</td><td>Professeur KTH Stockholm</td><td>Rapporteur</td></tr><tr><td>Bruno</td><td>Tuffin</td><td>Directeur de Recherche Inria Rennes</td><td>Examinateur</td></tr><tr><td>Michèle</td><td>Wigger</td><td>Professeure Télécom Paris</td><td>Rapporteure</td></tr><tr><td>Aylin</td><td>Yener</td><td>Professeure The Ohio State University</td><td>Examinatrice</td></tr></table>
<figure><img src="image_3.png" /></figure>
Résumé

Ce manuscrit d'HDR présente des résultats récents de Théorie de l'Information qui apportent un éclairage nouveau sur des problèmes de Théorie des Jeux, tels que la coordination des actions des joueurs ou le traitement de l'information stratégique. Bien que la Théorie de l'Information et la Théorie des Jeux aient des champs d'application distincts, ces deux théories s'appuient sur des outils mathématiques similaires. Les problèmes de coordination et d'information stratégique se posent pour la conception de réseaux d'appareils autonomes et pour l'étude du comportement d'agents rationnels. Les nouvelles générations de réseaux de communication intègrent des appareils qui prennent des décisions avec une plus grande autonomie. Ces machines observent leur environnement, interagissent, coopèrent avec d'autres machines ou avec des humains, s'adaptent dynamiquement à leur environnement et à la topologie du réseau.

Le théorème de codage de source avec perte de Shannon (1959) est la pierre angulaire de notre étude. Etant donnée une contrainte de capacité de communication, ce théorème caractérise le schéma de codage optimal pour compressor une source d'information. Les performances du codage sont évaluées via un critère de fidélité que nous interprétons comme une fonction de coût à minimiser. Nous revisitons ce problème de codage en adoptant le point de vue de la Théorie des Jeux, dans lequel chaque joueur optimise sa propre fonction de coût qui dépend des actions des autres joueurs.

Tout d'abord, nous étudions la capacité d'un encodeur et d'un décodeur à coordonner leurs actions avec les symboles générés par une source d'information. A cet effet, la suite d'actions de l'encodeur encapsule une version dégradée des symboles de source, qui sert à coordonner les futures actions du décodeur. Nous caractérisons les solutions de plusieurs instances du problème de coordination au Chap. IV, et au Chap. V, nous étendons ces résultats dans plusieurs directions, pour des problèmes de fuite d'état de canal, pour des problèmes de contrôle décentralisé et pour des problèmes de coordination forte. Le caractère stratégique de la transmission de l'information est étudié au Chap. VI lorsque les joueurs communiquent à travers un canal bruité. Nous considérons un encodeur s'engage à mettre en œuvre une stratégie, avant que les symboles de sources soient tirés, comme dans le jeu de persuasion Bayésienne.

En guise de perspectives, nous étudierons l'impact des contraintes de communication sur la transmission d'informations stratégiques dans les problèmes de "mechanism design" de Jackson and Sonnenschein (2007), et dans les jeux de "cheap talk" de Crawford and Sobel (1982). Une autre direction de recherche consiste à approfondir les problèmes d'optimisation qui apparaissent pour le codage stratégique, en utilisant des outils issus de la Théorie des Graphes et de l'Optimisation Convexe. Nous pensons que ces résultats apporteront un point de vue nouveau sur les problèmes ouverts en jeux répétés avec observation imparfaite et information incomplète. L'objectif est de construire une théorie qui englobe les résultats de codage standard en théorie de l'information et les résultats pour les jeux "sender-receiver".
<figure><img src="image_4.png" /></figure>
Abstract

This HDR manuscript presents recent Information-Theoretic tools that bring new insights into Game
Theoretical problems, such as the coordination of players’ actions and the processing of strategic infor-
mation. Although Information Theory and Game Theory have distinct fields of application, these two
theories rely on similar mathematical tools. Such problems arise for the design of autonomous devices
and for the study of the behavior of rational agents. New generations of communication networks involve
devices that take decisions with greater autonomy. These machines observe their environment, inter-
act, cooperate with other machines or with humans, adapt dynamically to their environment and to the
topology of the network.

The lossy source coding theorem of Shannon (1959) is the cornerstone of our study. Given a com-
munication capacity constraint, this theorem characterizes the optimal coding scheme to compress an
information source. The coding performances are evaluated via a fidelity criterion which we interpret as
a cost function to be minimized. We revisit this coding problem by adopting a Game-Theoretical point of
view, in which each player optimizes his own cost function which depends on the actions of other players.

First, we investigate the capacity of an encoder and a decoder to coordinate their actions with the
symbols of an information source. For this purpose, the action sequence of the encoder encapsulates a
degraded version of the source symbols, which serves to coordinate the future actions of the decoder. We
characterize the solutions of several instances of the coordination problem in Chap. IV, and in Chap. V, we
extend these results in several directions, i.e. for channel state leakage problems, for decentralized control
problems and for strong coordination problems. The strategic nature of the information transmission is
studied in Chap. VI when the communication is passed through a noisy channel. We consider that the
encoder commits to implementing a signalling strategy before it observes the source symbols, as in the
Bayesian persuasion game.

As perspectives, we will study the impact of communication constraints on the transmission of strategic
information in mechanism design problems, as in Jackson and Sonnenschein (2007), and in cheap talk
games, see Crawford and Sobel (1982). Another direction of research consists in deepening optimization
problems that arise in strategic coding, by using tools from Graph Theory and Convex Optimization. We
believe that these results will also bring a new point of view on open problems in repeated games with
imperfect observation and incomplete information. The goal is to build a theory that encompasses the
standard coding results in Information Theory, and the results for the sender-receiver games.
<figure><img src="image_5.png" /></figure>
# Contents

Table of content 2

I Career achievements 5

I.1 List of publications 6

II Introduction 12

II.1 Research activity review 13

II.1.a Point-to-point scenario 13

II.1.b Coordination problem 14

II.1.c Coordination and channel state masking with Matthieu Bloch 15

II.1.d Coordination and decentralized control with Tobias Oechtering 16

II.1.e Persuasion game with restricted communication with Tristan Tomala 16

II.1.f HARQ protocols with Leszek Szczecinski 17

II.2 Supervision of PhD students 18

II.2.a Strong coordination with Giulia Cervia, Laura Luzzi and Matthieu Bloch 18

II.2.b Multi-decoders Bayesian persuasion with Rony Bou Rouphael 18

II.2.c Zero-error source coding problems with Nicolas Charpenay and Aline Roumy 19

II.3 Content of this manuscript 20

III Information Theory review 21

III.1 Shannon's separation results 22

III.1.a Perfect channel of restricted cardinality 22

III.1.b General noisy channel 24

III.1.c Entropy formulas 25

III.2 Perfect channel of fixed capacity 26

III.2.a Lossy source coding 26

III.2.b Rational inattention 27

III.2.c Multi-objective coding problem 28

IV Empirical coordination with a strictly causal or a causal decoder 29

IV.1 Introduction 30

IV.2 Empirical coordination with strictly causal decoder 33

IV.2.a Problem statement 33

IV.2.b Characterization of the set of achievable distributions 34

IV.2.c Evaluation of an arbitrary expected cost function 35

IV.2.d Example #1: coordination game of Gossner et al. (2006) 36

IV.2.e Example #2: Hamming distortion and channel cost 38

IV.3 General decoding functions 40

IV.3.a Causal decoding with source feedforward 40

IV.3.b Strictly causal decoding with source feedforward 42

IV.4 State-dependent source and state-dependent channel 43

IV.4.a Non-causal encoder and non-causal decoder 43

IV.4.b Causal decoder and non-causal encoder 47
<table><tbody><tr><td>IV.4.c</td><td>Causal encoder and non-causal decoder</td><td>49</td></tr><tr><td>IV.5</td><td>Chapter summary</td><td>51</td></tr><tr><td>V</td><td>Impact of empirical coordination results</td><td>52</td></tr><tr><td>V.1</td><td>State leakage and coordination with causal state knowledge at the encoder</td><td>53</td></tr><tr><td>V.1.a</td><td>Problem statement</td><td>54</td></tr><tr><td>V.1.b</td><td>Characterization of achievable triples of rate, leakage and distribution</td><td>55</td></tr><tr><td>V.1.c</td><td>Channel state estimation via cost function</td><td>57</td></tr><tr><td>V.1.d</td><td>Extensions to more general scenarios</td><td>59</td></tr><tr><td>V.1.e</td><td>Strictly causal encoding</td><td>61</td></tr><tr><td>V.2</td><td>Decentralized control: Witsenhausen's counterexample</td><td>62</td></tr><tr><td>V.2.a</td><td>System model</td><td>63</td></tr><tr><td>V.2.b</td><td>Coding Result</td><td>64</td></tr><tr><td>V.2.c</td><td>Control schemes of particular interest</td><td>65</td></tr><tr><td>V.2.d</td><td>Numerical Results</td><td>68</td></tr><tr><td>V.2.e</td><td>Discussion</td><td>69</td></tr><tr><td>V.3</td><td>Strong coordination of signals and actions</td><td>70</td></tr><tr><td>V.3.a</td><td>Inner and outer bounds for the strong coordination region</td><td>72</td></tr><tr><td>V.3.b</td><td>Strong coordination region with state and side information</td><td>73</td></tr><tr><td>V.3.c</td><td>Characterization of the strong coordination region for special cases</td><td>75</td></tr><tr><td>V.3.d</td><td>Is separation optimal?</td><td>78</td></tr><tr><td>V.4</td><td>Chapter summary</td><td>81</td></tr><tr><td>VI</td><td>Bayesian persuasion with restricted communication</td><td>82</td></tr><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><tr><td>VII</td><td>Conclusion and perspectives</td><td>114</td></tr><tr><td>VII.1</td><td>Zero-error coding for computing problem</td><td>115</td></tr><tr><td>VII.1.a</td><td>Problem statement</td><td>115</td></tr><tr><td>VII.1.b</td><td>General setting</td><td>116</td></tr><tr><td>VII.1.c</td><td>Pairwise shared side information</td><td>117</td></tr><tr><td>VII.2</td><td>Convex optimization algorithm for coordination problems</td><td>118</td></tr><tr><td>VII.2.a</td><td>Problem formulation</td><td>118</td></tr><tr><td>VII.2.b</td><td>Connection with Blahut-Arimoto's algorithm</td><td>119</td></tr><tr><td>VII.2.c</td><td>Original optimization algorithm</td><td>120</td></tr><tr><td>VII.3</td><td>Mechanism design and cheap talk problems</td><td>120</td></tr><tr><td>VII.3.a</td><td>System model</td><td>121</td></tr><tr><td>VII.3.b</td><td>Upper bound</td><td>121</td></tr><tr><td>VII.4</td><td>Repeated games with imperfect monitoring and incomplete information</td><td>122</td></tr><tr><td>Bibliography</td><td></td><td>134</td></tr></tbody></table>
I.1 List of publications

INTERNATIONAL JOURNALS (10)

[J10] Le Treust, M. and Bloch, M. *State Leakage and Coordination of Actions*, IEEE Trans. on Information Theory, Volume: 67, Issue: 2, Pages 805-823, Feb. 2021.

[J9] Cervia, G. and Luzzi, L. and Le Treust, M. and Bloch, M. *Strong coordination of signals and actions over noisy channels with two-sided state information*, IEEE Trans. on Information Theory, Volume: 66, Issue: 8, Pages: 4681-4708, Aug. 2020.

[J8] Le Treust, M. and Tomala, T. *Persuasion with limited communication resources*, Journal of Economic Theory, vol. 184, page 104940, Nov. 2019.

[J7] Le Treust, M. and Szczecinski, L. and F. Labeau *Rate Adaptation for Secure HARQ Protocols*, IEEE Trans. on Information Forensics and Security, Volume 13, Issue 12, Pages 2981 - 2994, May 2018.

[J6] Le Treust, M. *Empirical Coordination for Joint Source-Channel Coding*, IEEE Trans. on Information Theory, Volume 63, Issue 8, Pages 5087 - 5114, Aug. 2017.

[J5] Jabi, M. and Benyouss, A. and Le Treust, M. and Pierre-Doray, M. and Szczecinski, L. *Adaptive Cross-Packet HARQ*, IEEE Trans. on Communication, Volume 65, Issue 5, Pages: 2022-2035, May 2017.

[J4] Mheich, Z. and Le Treust, M. and Alberge, F. and Duhamel, P. *Rate Adaptation for Incremental Redundancy Secure HARQ*, IEEE Trans. on Communications, Volume 64, Issue 2, pp 765-777, Feb. 2016.

[J3] Le Treust, M. and Lasaulce, S. and Hayel, Y. and He, G., *Green power control in cognitive wireless networks*, IEEE Trans. on Vehicular Technology, Volume 62, Issue 4, pp 1741-1754, May 2013.

[J2] Le Treust, M. and Lasaulce, S., *Transforming Monitoring Structures with Resilient Encoders. Application to Repeated Games*, Springer journal of Dynamic Games and Applications, Volume 3, Issue 1, pp 38-67, March 2013.

[J1] Le Treust, M. and Lasaulce, S., *A repeated game formulation of energy-efficient decentralized power control*, IEEE Trans. on Wireless Communications, Volume 9, Issue 9, pp 2860-2869, Sept. 2010.

INTERNATIONAL CONFERENCES (31)

[IC31] Bou Rouphael, R., Le Treust, M., *Strategic Communication with Cost-Dependent Decoders via the Gray-Wyner Network*, IEEE Information Theory Workshop (ITW), Mumbai, 2022.

[IC30] Charpenay, N., Le Treust, M. and Roumy, A., *Zero-error source coding when side information may be present*, International Zürich Seminar (IZS), March, 2022.

[IC29] Bou Rouphael, R. and Le Treust, M., *Strategic Successive Refinement Coding for Bayesian Persuasion with Two Decoders*, IEEE Information Theory Workshop (ITW) 2021, Kanazawa, Japan.
[IC28] Le Treust, M. and Tomala, T., Strategic Communication with Decoder Side Information, IEEE Information Symposium on Information Theory (ISIT), Melbourne, Australia, July 2021.

[IC27] Le Treust, M. and Oechtering, T., Continuous Random Variable Estimation is not Optimal for the Witsenhausen Counterexample, IEEE Information Symposium on Information Theory (ISIT), Melbourne, Australia, July 2021.

[IC26] Le Treust, M. and Tomala, T., Point-to-Point Strategic Communication, IEEE Information Theory Workshop (ITW), Riva del Garda, Italy, 2020.

[IC25] Charpenay, N. and Le Treust, M., Zero-Error Coding with a Generator Set of Variable-Length Words, IEEE International Symposium on Information Theory (ISIT), Los Angeles, June 2020.

[IC24] Bou Rouphael, R. and Le Treust, M., Impact of Private Observation in Bayesian Persuasion, International Conference on NETwork Games, Control and Optimisation (NETGCOOP), Cargèse, Corsica, France on March 18-20, 2020.

[IC23] Oechtering, T. and Le Treust, M., Coordination Coding with Causal Decoder for Vector-valued Witsenhausen Counterexample Setups, IEEE Information Theory Workshop (ITW), Visby, Aug. 2019.

[IC22] Le Treust, M. and Oechtering, T., Optimal Control Designs for Vector-valued Witsenhausen Counterexample Setups, IEEE 56th Allerton Conference on Control Communication and Computing, Monticello, Illinois, 2018.

[IC21] Cervia, G. and Luzzi, L. and Le Treust, M. and Bloch, M., Strong Coordination Over Noisy Channels with Strictly Causal Encoding, IEEE 56th Allerton Conference on Control Communication and Computing, Monticello, Illinois, 2018.

[IC20] Le Treust, M. and Tomala, T., Strategic Coordination with State Information at the Decoder, International Zurich Seminar on Information and Communication, Zurich, Switzerland, 2018.

[IC19] Cervia, G. and Luzzi, L. and Le Treust, M. and Bloch, M., Strong Coordination of Signals and Actions over Noisy Channels, IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017.

[IC18] Le Treust, M. and Tomala, T., Information Design for Strategic Coordination of Autonomous Devices with Non-Aligned Utilities, IEEE Proc. of the 54th Allerton conference, Monticello, Illinois, 2016.

[IC17] Cervia, G. and Luzzi, L. and Bloch, M. and Le Treust, M., Polar coding for empirical coordination of signals and actions over noisy channels, IEEE Proc. of the Information Theory Workshop (ITW), Cambridge, UK, 2016.
[IC16] Le Treust, M. and Bloch, M., *Empirical Coordination, State Masking and State Amplification: Core of the Decoder's Knowledge*, IEEE Proc. of the International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016.

[IC15] Benyouss, A. and Jabi, M. and Le Treust, M. and Szczecinski, L., *Joint Coding/Decoding for Multi-message HARQ*, IEEE Proc. of the Wireless Communications and Networking Conference (WCNC), Doha, Qatar, 2016.

[IC14] Le Treust, M., *Empirical Coordination with Channel Feedback and Strictly Causal or Causal Encoding*, IEEE Proc. of the International Symposium on Information Theory (ISIT), Hong-Kong, China, 2015.

[IC13] Le Treust, M., *Empirical Coordination with Two-Sided State Information and Correlated Source and State*, IEEE Proc. of the International Symposium on Information Theory (ISIT), Hong-Kong, China, 2015.

[IC12] Le Treust, M., *Correlation between channel state and information source with empirical coordination constraint*, IEEE Proc. of the Information Theory Workshop (ITW2014), Hobart, Australia, 2014.

[IC11] Mheich, Z. and Le Treust, M. and Alberge, F. and Duhamel, P and Szczecinski, L., *Rate-adaptive secure HARQ protocol for block-fading channels*, IEEE Proc. of the 22nd European Signal Processing Conference (EUSIPCO), 2014.

[IC10] Varma, V. S. and Mhiri, M. and Le Treust, M. and Lasaulce, S. and Samet, A., *On the benefits of repeated game models for green cross-layer power control in small cells*, IEEE Proc. of the First International Black Sea Conference on Communications and Networking (BlackSeaCom), 2013.

[IC9] Le Treust, M. and Szczecinski L. and Labeau F., *Secrecy & Rate Adaptation for Secure HARQ Protocols*, IEEE Proc. of the Information Theory Workshop (ITW2013), Sevilla, Spain, 2013.

[IC8] Le Treust, M. and Lasaulce, S., *Resilient Source Coding*, IEEE Proc. of the international conference on network games, control and optimization (NETGCOOP11), (Paris) 2011.

[IC7] Le Treust, M. and Zaidi, A. and Lasaulce, S., *An Achievable Rate Region for the Broadcast Wiretap Channel with Asymmetric Side Information*, IEEE Proc. of the 49th Allerton conference, Monticello, Illinois, 2011.

[IC6] Meriaux, F. and Le Treust, M. and Lasaulce, S. and Kieffer, M., *Energy-efficient power control strategies for stochastic games*, IEEE Proc. of the 17th International Conference on Digital Signal Processing (DSP), 2011.
[IC5] Le Treust, M. and Lasaulce, S., *The price of re-establishing almost perfect monitoring in games with arbitrary monitoring structures*, ACM Proc. of the 4th International Workshop on Game Theory in Communication Networks (GAMECOMM11), Cachan (Paris), France, 2011.

[IC4] Le Treust, M. and Hayel, Y. and Lasaulce, S. and Debbah, M., *To Sense or not to Sense in Energy-Efficient Power Control Games*, IEEE Proc. of the 2nd International Conference on Game Theory for Networks (GAMENETS11), Shanghai, China, 2011.

[IC3] Le Treust, M. and Tembine, H. and Lasaulce, S. and Debbah, M., *Coverage games in small cells networks*, IEEE Proc. of the Future Network and Mobile Summit (FUNEMS10), Florence, Italy, 2010.

[IC2] Le Treust, M. and Lasaulce, S. and Debbah, M., *Implicit cooperation in distributed energy-efficient networks*, IEEE Proc. of the 4th International Symposium on Communications, Control and Signal Processing (ISCCSP10), Limassol, Cyprus, 2010.

[IC1] Bennis, M. and Le Treust, M. and Lasaulce, S. and Debbah, M., *Spectrum sharing games in the interference channel*, IEEE Proc. of the 1st International Conference on Game Theory for Networks (GAMENETS09), Istanbul, Turkey, 2009.

## NATIONAL CONFERENCES (11)

[NC11] Charpenay, N. and Le Treust, M. and Roumy, A., *Codage de source zéro-erreur pour un réseau de Gray-Wyner lorsque l'information adjacente peut être présente*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Nancy, France, 2022.

[NC10] Bou Rouphael, R. and Le Treust, M., *Communication stratégique via le réseau Gray-Wyner*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Nancy, France, 2022.

[NC9] Le Treust, M. and Bloch, M., *Jeu d'estimation de l'état de canal et coordination*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Lille, France, 2019.

[NC8] Le Treust, M. and Tomala, T., *Persuasion Bayésienne pour la Coordination Stratégique d'Appareils Autonomes ayant des Objectifs Non-Alignés.*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Juan-les-Pins, France, 2017.

[NC7] Cervia, Giulia and Luzzi, Laura and Le Treust, Mael and Bloch, Matthieu R., *Polar codes for empirical coordination over noisy channels with strictly causal encoding*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Juan-les-Pins, France, 2017.

[NC6] Le Treust, M., *Coordination d'appareils autonomes dans un réseau décentralisé.*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Lyon, France, 2015.
[NC5] Meriaux, F. and LeTreust, M. and Lasaulce, S. and Kieffer, M., *Jeux stochastiques et contrôle de puissance distribué*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI11), Bordeaux, France, 2011.

[NC4] Le Treust, M. and Lasaulce, S., *Codage de Source Stratégique avec Information Adjacente au Décodeur*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI11), Bordeaux, France, 2011.

[NC3] Debbah, M. and Lasaulce, S. and LeTreust, M. and Tembine, H., *Contrôle de puissance dynamique pour les communications sans fils*, Actes de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF10), Toulouse, 2010.

[NC2] Le Treust, M. and Lasaulce, S., *Approche bayésienne pour le contrôle de puissance décentralisé efficace énergétiquement*, Actes de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF10), Toulouse, 2010.

[NC1] Le Treust, M and Medina Perlaza, S. and Lasaulce, S., *Contrôle de puissance distribué efficace énergétiquement et jeux répétés*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI09), Dijon, France, 2009.

## POSTER (2)

[P2] Bou Rouphael, R. and Le Treust, M., *Impact of Private Observation in Persuasion Game*, GAMENET Conference 2019, Prague, Czech Republic, Nov. 21-22, 2019

[P1] Cervia, G., Luzzi, L., Bloch, M., and Le Treust, M., *Polar coding for empirical coordination of signals and actions over noisy channels*, European School on Information Theory, Gothenburg (ESIT), Sweden, April 4-8, 2016

## WORKING PAPERS (9)

[W9] Le Treust, M. and Oechtering, T., *Power-Estimation Trade-off of Vector-valued Witsenhausen Counterexample with Causal Decoder*, submitted to IEEE Transactions on Information Theory, [on-line] available: http://arxiv.org/abs/2211.09200, Nov. 2022.

[W8] Charpenay, N., Le Treust, M. and Roumy, A., *Zero-Error Coding for Computing with Encoder Side-Information*, submitted to IEEE Information Theory Workshop (ITW), Saint-Malo, France, [on-line] available: https://arxiv.org/abs/2211.03649, 2023.

[W7] Bou Rouphael, R. and Le Treust, M., *Strategic Communication via Cascade Multiple Description Network*, [on-line] available: https://arxiv.org/abs/2210.00533, 2022.

[W6] Charpenay, N., Le Treust, M. and Roumy, A., *Zero-error source coding with two-sided side-information*, working paper, Apr. 2022.

[W5] Bou Rouphael, R. and Le Treust, M., *Strategic Successive Refinement for Bayesian Persuasion with Cost-Dependent Decoders*, second round of review for IEEE JSAIT, Apr. 2022.

[W4] Charpenay, N. and Le Treust, M., *Variable-Length Coding for Zero-Error Channel Capacity*, preliminary draft, [on-line] available: https://arxiv.org/abs/2001.03523, Jan. 2020.

[W3] Le Treust, M. and Tomala, T., *Strategic Communication with Side Information at the Decoder*, preliminary draft, [on-line] available: https://arxiv.org/abs/1911.04950, Nov. 2019.
[W2] Le Treust, M. and Tomala, T. *Information-Theoretic Limits of Strategic Communication*, preliminary draft, [on-line] available: https://arxiv.org/abs/1807.05147, Jul. 2018.

[W1] Le Treust, M. *Coding Theorems for Empirical Coordination*, preliminary draft, [on-line] available: https://hal.archives-ouvertes.fr/hal-01865569, Apr. 2015.

MANUSCRIPTS (3)

[M3] Le Treust, M., *Coordination and Strategic Communication*, Habilitation à Diriger les Recherches (HDR), CY Cergy Paris Université, Dec. 2022

[M2] Le Treust, M., *Théorie de l'information, jeux répétés avec observation imparfaite et réseaux de communication décentralisés*, PhD Thesis, Université Paris Sud XI, Dec. 2011

[M1] Le Treust, M., *Folk theorem and Imperfect Monitoring*, Master Thesis, Université Pierre et Marie Curie Paris VI, Sept. 2008
# Chapter II

# Introduction

<figure><img src="image_6.png" /><figcaption>(The Cardsharps, Caravaggio)</figcaption></figure>

This manuscript presents an overview of the results obtained at the interplay between Information Theory and Game Theory. The goal is to build a theory that encompasses the standard coding results in Information Theory, and the results for the sender-receiver games. Our findings will be applied to decentralized decision-making problems and digital communication networks. Specific topics of interest include Convex Optimization, Graph Theory and zero-error coding, repeated game with incomplete information and imperfect monitoring.

## Contents

<table><tr><td>II.1</td><td>Research activity review</td><td>13</td></tr><tr><td>II.1.a</td><td>Point-to-point scenario</td><td>13</td></tr><tr><td>II.1.b</td><td>Coordination problem</td><td>14</td></tr><tr><td>II.1.c</td><td>Coordination and channel state masking with Matthieu Bloch</td><td>15</td></tr><tr><td>II.1.d</td><td>Coordination and decentralized control with Tobias Oechtering</td><td>16</td></tr><tr><td>II.1.e</td><td>Persuasion game with restricted communication with Tristan Tomala</td><td>16</td></tr><tr><td>II.1.f</td><td>HARQ protocols with Leszek Szczecinski</td><td>17</td></tr><tr><td>II.2</td><td>Supervision of PhD students</td><td>18</td></tr><tr><td>II.2.a</td><td>Strong coordination with Giulia Cervia, Laura Luzzi and Matthieu Bloch</td><td>18</td></tr><tr><td>II.2.b</td><td>Multi-decoders Bayesian persuasion with Rony Bou Rouphael</td><td>18</td></tr><tr><td>II.2.c</td><td>Zero-error source coding problems with Nicolas Charpenay and Aline Roumy</td><td>19</td></tr><tr><td>II.3</td><td>Content of this manuscript</td><td>20</td></tr></table>
## II.1 Research activity review

Although Information Theory and Game Theory have distinct fields of application, they rely on similar mathematical tools from Probability, Statistics, Convex Optimization, Graph Theory, Combinatorial Optimization. Information Theory has applications in Electrical Engineering and Computer Science for compression, storage, image processing and digital communication problems. Game Theory has applications in Economics, in Social Sciences, in Biology and in Computer Science for decentralized decision-making problems.

This manuscript presents recent Information Theoretic tools in order to study the coordination of players' actions and the processing of strategic information in Game Theory. This question is at the intersection of many current research directions regarding the design of autonomous devices and the study of the behavior of rational agents. New generations of communication networks involve devices or agents that take into account the communication constraints and that make decisions with greater autonomy. They observe their environment, interact, cooperate with other machines or humans, adapt dynamically to their environment and to the topology of the network.

### II.1.a Point-to-point scenario

To address this problem, we revisit seminal point-to-point results such as the channel coding theorem of Shannon (1948) and the lossy source coding theorem of Shannon (1959). This last problem depends of a fidelity criterion which we interpret as a decision maker's cost function to be minimized. In this direction, the scenario depicted in Fig. III.3 is of particular interest.

In this manuscript, the sender and the receiver are referred to as the encoder and the decoder. We denote by $\Delta(\mathcal{X})$ the set of probability distributions $\mathcal{P}_X$ over the finite set $\mathcal{X}$, and by $\Delta(\mathcal{Y})^{|\mathcal{X}|}$ the set of conditional probability distributions $\mathcal{P}_{Y|\mathcal{X}}$. The information source $(\mathcal{U}, \mathcal{P}_U)$ is defined by a finite set $\mathcal{U}$ and a probability distribution $\mathcal{P}_U \in \Delta(\mathcal{U})$ such that the symbol $u \in \mathcal{U}$ is selected with probability $\mathcal{P}_U(u) \in [0, 1]$. The cost function $c: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ is evaluated over $\mathcal{U}$ and the finite set of decoder actions $\mathcal{V}$. The channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|\mathcal{X}})$ is defined by two finite sets of channel inputs $\mathcal{X}$ and channel outputs $\mathcal{Y}$, and a conditional probability distribution $\mathcal{T}_{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}_{Y|\mathcal{X}}(y|x) \in [0, 1]$. Throughout this manuscript, calligraphic fonts, e.g. $\mathcal{X}$, stand for finite sets, capital letters, e.g. $X$, denote random variables while lowercase letters, e.g. $x \in \mathcal{X}$ denote the realizations. Sequences of length $n \in \mathbb{N}^* = \mathbb{N} \setminus \{0\}$ of random variables and realizations are denoted respectively by $X^n = (X_1, \dots, X_t, \dots, X_n)$ and $x^n = (x_1, \dots, x_t, \dots, x_n)$, for $t \in \{1, \dots, n\}$.

<figure><img src="image_7.png" /><figcaption>Figure II.1 – Point-to-point scenario with an information source $(\mathcal{U}, \mathcal{P}_U)$, a channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|\mathcal{X}})$ and a cost function $c: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$.</figcaption></figure>

The information source generates an i.i.d. sequence $U^n$ of length $n \in \mathbb{N}^*$. The encoder observes the realization $u^n \in \mathcal{U}^n$ and selects a sequence of channel inputs $x^n \in \mathcal{X}^n$. The channel generates an output sequence $Y^n$ according to the i.i.d. conditional distribution $\mathcal{T}_{Y|\mathcal{X}}$ evaluated with respect to $x^n \in \mathcal{X}^n$. The decoder observes the realization $y^n \in \mathcal{Y}^n$ and selects a sequence of actions $v^n \in \mathcal{V}^n$. The encoding function $\sigma: \mathcal{U}^n \to \mathcal{X}^n$ and the decoding functions $\tau: \mathcal{Y}^n \to \mathcal{V}^n$ are selected in order to minimize the expected long-run cost. The coding problem is defined by

$$C^n = \min_{\sigma, \tau} \mathbb{E} \left[ \frac{1}{n} \sum_{t=1}^{n} c(U_t, V_t) \right]. \qquad (II.1)$$
In Shannon (1948) and Shannon (1959), the asymptotic value of $C^n$ is characterized by

$$C^* = \min_{\substack{Q_{V|U} \in \Delta(V)^{|U|}, \\ I(U;V) \le \max_{P_X} I(X;Y)}} \mathbb{E}[c(U, V)], \qquad (II.2)$$

where the mutual information

$$I(U;V) = \sum_{(u,v) \in \text{supp} P_U Q_{V|U}} P_U(u) Q_{V|U}(v|u) \log_2 \frac{Q_{V|U}(v|u)}{\sum_{u'} P_U(u') Q_{V|U}(v|u')}, \qquad (II.3)$$

measures the correlation of $U$ and $V$. An important feature of (II.2) is the restriction imposed on the set of achievable conditional distributions $Q_{V|U} \in \Delta(V)^{|U|}$, by the information constraint $I(U;V) \le \max_{P_X} I(X;Y)$. This captures the restrictions imposed by the repeated use of the channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|X})$, on the empirical distribution of the random variables $U$ and $V$.

In the Game Theory literature, the optimization problem of (II.2) gave rise to as the rational inattention problem, formulated in Sims (2003). The goal is to determine the optimal trade-off between the cost of information extraction $I(U;V)$ and the benefit of information exploitation for the minimization of $\mathbb{E}[c(U, V)]$. Note that the setting of Fig. III.3 is also related to the model of repeated game of incomplete information Aumann and Maschler (1995) and of the sender-receiver game Crawford and Sobel (1982).

We present a brief summary of the different problems under study in this manuscript and the main contributions.

## II.1.b Coordination problem

An intriguing information constraint $I(U;V) \le H(X|U, V)$ was stated in Gossner et al. (2006) for a repeated game problem with incomplete information. The encoder and the decoder are the players of the game, the decoder actions only depends on past channel outputs, and the channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|X})$ is perfect, i.e. $\mathcal{X} = \mathcal{Y}$ and $\mathcal{T}_{Y|X}(y|x) = \mathbb{1}\{y = x\}$, where the indicator function is equal to 1 if $x = y$, and 0 otherwise.

The main difference with the model of Sec. II.1.a is the cost function

$$c: \mathcal{U} \times \mathcal{X} \times \mathcal{V} \to \mathbb{R}, \qquad (II.4)$$

which also depends on the encoder action $X$, i.e. the channel input symbol.

When selecting the actions, the encoder faces a trade-off between minimizing of the cost function with $X$ and sending information to the decoder so that it can also minimize the cost function with $V$. The goal of the players is to implement sequences of actions that are empirically correlated with the source of information. The authors show that the optimal solution is characterized via the information constraint $I(U;V) \le H(X|U, V)$. This problem has given rise to a literature on empirical coordination problems in Information Theory, see Cuff et al. (2010). The key is to control the empirical distribution of symbols of source $U$ and actions $(X, V)$, induced by the coding scheme.

A series of contributions consists in characterizing the solutions of several instances of the coordination problem, when the observation of actions is imperfect, when the decoder also observes past source symbols, when the decoder or the encoder operates in a strictly causal, causal or non-causal manner, when the channel and the sources depend on state parameters partially observed by the encoder and by the decoder. We show that the coordination problem is related to the joint source-channel coding problem with two-sided state information, which is a famous object of study in Information Theory, see Merhav and Shamai (2003). We notice that the source symbol observed by the encoder must be considered as the state of a state-dependent channel, as in Gel'fand and Pinsker (1980), whereas the channel output must be considered as side information of the decoder, as in Wyner and Ziv (1976). This research work resulted in the following publications:

[J6] Le Treust, M. Empirical Coordination for Joint Source-Channel Coding, IEEE Transactions on Information Theory, Volume 63, Issue 8, Pages 5087 - 5114, Aug. 2017.
[IC14] Le Treust, M., *Empirical Coordination with Channel Feedback and Strictly Causal or Causal Encoding*, IEEE Proc. of the International Symposium on Information Theory (ISIT), Hong-Kong, China, 2015.

[IC13] Le Treust, M., *Empirical Coordination with Two-Sided State Information and Correlated Source and State*, IEEE Proc. of the International Symposium on Information Theory (ISIT), Hong-Kong, China, 2015.

[IC12] Le Treust, M., *Correlation between channel state and information source with empirical coordination constraint*, IEEE Proc. of the Information Theory Workshop (ITW2014), Hobart, Australia, 2014.

[NC6] Le Treust, M., *Coordination d'appareils autonomes dans un réseau décentralisé.*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Lyon, France, 2015.

[W1] Le Treust, M., *Coding Theorems for Empirical Coordination: Technical Report*, [on-line] available: https://hal.archives-ouvertes.fr/hal-01865569, Apr. 2015.

## II.1.c Coordination and channel state masking with Matthieu Bloch

The study of state-dependent channels can be traced back to the early works of Shannon (1958) and Gel'fand and Pinsker (1980), which identified optimal coding strategies to transmit reliably in a noisy environment when the encoder has some observation of the noise random variable, referred to as the state of the channel. In Kim et al. (2008), the authors design a coding scheme that conveys the channel state to the decoder, on top of the message transmission. They characterize the optimal trade-off between the rate capacity of reliable communication and the reduction of uncertainty about the channel state. In Merhav and Shamai (2007), the goal of the coding scheme is to hide the channel state variable from the decoder by minimizing the channel state leakage, while guaranteeing a certain transmission rate. The rate-leakage capacity region of state masking has been successfully characterized for both causal and non-causal state knowledge.

With Matthieu Bloch, Professor at Georgia Tech Atlanta and member of GeorgiaTech-CNRS IRL 2958, we revisit the problems of state masking and state amplification through the lens of empirical coordination. We introduce a channel state estimation zero-sum game in which the decoder minimizes the channel state estimation cost function. The coordination approach allows us to characterize the optimal solution of this zero-sum game, which was considered to be difficult, see (Merhav and Shamai, 2007, 2 pp. 2255). We characterize the optimal trade-offs between the coordination capacity, the channel state information leakage and the information rate transmitted to the decoder. We extend the results of (Le Treust, 2015b, [IC14]) when the encoder has noisy channel output feedback. This research work resulted in the following publications:

[J10] Le Treust, M. and Bloch, M., *State Leakage and Coordination of Actions*, IEEE Transactions on Information Theory, Volume: 67, Issue: 2, Pages 805-823, Feb. 2021.

[IC16] Le Treust, M. and Bloch, M., *Empirical Coordination, State Masking and State Amplification: Core of the Decoder's Knowledge*, IEEE Proc. of the International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016.

[NC9] Le Treust, M. and Bloch, M., *Jeu d'estimation de l'état de canal et coordination*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Lille, France, 2019.
## II.1.d Coordination and decentralized control with Tobias Oechtering

Distributed decision-making systems arise in many engineering problems where decentralized agents choose actions based on locally available information, so as to minimize a common cost function. The design of optimal strategies for such problems is considered to be notoriously difficult. In Witsenhausen (1968), the author introduces an outstanding toy example that help to grasp the fundamental difficulty when the actions serve two purposes, a control purpose affecting the system state and a communication purpose where information is sent to other agents, see Yüksel and Başar (2013). The coordination approach of Sec. II.1.b offers a new perspective on decentralized control problems.

With Tobias Oechtering, Professor at KTH Stockholm, we consider the vector version of the Witsenhausen's counterexample introduced in Grover and Sahai (2010). We extend the finite alphabet coding scheme of (Le Treust, 2017, [J6]) to continuous alphabet by adapting the notion of weak typicality. We determine new coding strategies and we evaluate their performances. Interestingly, we show that a pair of discrete and continuous auxiliary random variables, outperforms both Witsenhausen's two point strategy and the best affine policies. This research work resulted in the following publications:

[IC27] Le Treust, M. and Oechtering, T., Continuous Random Variable Estimation is not Optimal for the Witsenhausen Counterexample, IEEE Information Symposium on Information Theory (ISIT), Melbourne, Australia, July 2021.

[IC23] Oechtering, T. and Le Treust, M., Coordination Coding with Causal Decoder for Vector-valued Witsenhausen Counterexample Setups, IEEE Information Theory Workshop (ITW), Visby, Aug. 2019.

[IC22] Le Treust, M. and Oechtering, T., Optimal Control Designs for Vector-valued Witsenhausen Counterexample Setups, IEEE 56th Allerton Conference on Control Communication and Computing, Monticello, Illinois, 2018.

## II.1.e Persuasion game with restricted communication with Tristan Tomala

The nature of the problem changes when the encoder and the decoder, see Fig. III.3, selfishly optimize distinct cost functions

$$c_e : \mathcal{U} \times \mathcal{V} \to \mathbb{R} \neq c_d : \mathcal{U} \times \mathcal{V} \to \mathbb{R}. \qquad (II.5)$$

The transmission of information becomes strategic. The encoder and the decoder are the players of a game with incomplete information. This framework has been well explored in the Game Theory literature, when the encoder can send a large number of messages that are perfectly received by the decoder.

In the cheap talk game of Crawford and Sobel (1982), the encoder observes a Gaussian random variable and selects a real number, which is transmitted and perfectly received by the decoder. The communication is unrestricted and the signals do not affect the cost functions. In this model, neither the encoder nor the decoder commit to a strategy. The natural solution concept is the Nash equilibrium, see Nash (1951).

In the Bayesian persuasion game of Kamenica and Gentzkow (2011), the encoder commits to implementing a coding strategy before the game plays. By knowing the encoding scheme, the decoder selects a best response action that depends on its posterior beliefs. The natural solution is the Stackelberg equilibrium, see von Stackelberg (1934), in which the encoder is the Stackelberg leader and the decoder is the Stackelberg follower.

With Tristan Tomala, Professor at HEC Paris and member of GREGHEC UMR 2959, we investigate the Bayesian persuasion problem when the encoder and the decoder communicate through a noisy channel, when the number of messages is restricted, and when the decoder observes a degraded version of the information source. This research work resulted in the following publications:

[J8] Le Treust, M. and Tomala, T., Persuasion with limited communication resources, Journal of Economic Theory, vol. 184, page 104940, Nov. 2019.
[IC28] Le Treust, M. and Tomala, T., Strategic Communication with Decoder Side Information, IEEE Information Symposium on Information Theory (ISIT), Melbourne, Australia, July 2021.

[IC26] Le Treust, M. and Tomala, T., Point-to-Point Strategic Communication, IEEE Information Theory Workshop (ITW), Riva del Garda, Italy, 2020.

[IC20] Le Treust, M. and Tomala, T., Strategic Coordination with State Information at the Decoder, International Zurich Seminar on Information and Communication, Zurich, Switzerland, 2018.

[IC18] Le Treust, M. and Tomala, T., Information Design for Strategic Coordination of Autonomous Devices with Non-Aligned Utilities, IEEE Proc. of the 54th Allerton conference, Monticello, Illinois, 2016.

[NC8] Le Treust, M. and Tomala, T., Persuasion Bayésienne pour la Coordination Stratégique d'Appareils Autonomes ayant des Objectifs Non-Alignés., Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Juan-les-Pins, France, 2017.

[W3] Le Treust, M. and Tomala, T., Strategic Communication with Side Information at the Decoder, preliminary draft, [on-line] available: https://arxiv.org/abs/1911.04950, Nov. 2019.

[W2] Le Treust, M. and Tomala, T., Information-Theoretic Limits of Strategic Communication, preliminary draft, [on-line] available: https://arxiv.org/abs/1807.05147, Jul. 2018.

## II.1.f HARQ protocols with Leszek Szczecinski

During my post-doc at INRS, in Montreal in 2012 to 2013 under the supervision of Leszek Szczecinski, I worked on Hybrid Automatic Retransmission reQuest (HARQ) protocols for digital communication. In a fading environment, the channel capacity is a random variable which might be observed by the decoder only. When the rate parameter of the coding scheme exceeds the channel capacity, the decoder sends a NACK feedback to the encoder, that retransmits the codeword, as in Caire and Tuninetti (2001). We investigate several HARQ protocols that are able to adapt dynamically to the changes in the channel capacity. Following the work of Tang et al. (2009), we design a HARQ protocol tailored to ensure the secrecy of the transmission. This research work resulted in the following publications:

[J7] Le Treust, M. and Szczecinski, L. and F. Labeau Rate Adaptation for Secure HARQ Protocols, IEEE Transactions on Information Forensics and Security, Volume 13, Issue 12, Pages 2981 - 2994, May 2018.

[J5] Jabi, M. and Benyouss, A. and Le Treust, M. and Pierre-Doray, M. and Szczecinski, L. Adaptive Cross-Packet HARQ, IEEE Transactions on Communication, Volume 65, Issue 5, Pages: 2022-2035, May 2017.

[J4] Mheich, Z. and Le Treust, M. and Alberge, F. and Duhamel, P. Rate Adaptation for Incremental Redundancy Secure HARQ, IEEE Transactions on Communications, Volume 64, Issue 2, pp 765-777, Feb. 2016.

[IC15] Benyouss, A. and Jabi, M. and Le Treust, M. and Szczecinski, L., Joint Coding/Decoding for Multi-message HARQ, IEEE Proc. of the Wireless Communications and Networking Conference (WCNC), Doha, Qatar, 2016.

[IC11] Mheich, Z. and Le Treust, M. and Alberge, F. and Duhamel, P and Szczecinski, L. Rate-adaptive secure HARQ protocol for block-fading channels, IEEE Proc. of the 22nd European Signal Processing Conference (EUSIPCO), 2014.
[IC9] Le Treust, M. and Szczecinski L. and Labeau F., *Secrecy & Rate Adaptation for Secure HARQ Protocols*, IEEE Proc. of the Information Theory Workshop (ITW2013), Sevilla, Spain, 2013.

## II.2 Supervision of PhD students

### II.2.a Strong coordination with Giulia Cervia, Laura Luzzi and Matthieu Bloch

From 2015 to 2018, Giulia Cervia was PhD student at ETIS UMR 8051 in Cergy, under the direction of Inbar Fijalkow and the supervision of Laura Luzzi and myself. We worked in collaboration with Matthieu Bloch on the problem of strong coordination introduced in Cuff et al. (2010). Contrary to the notion of empirical coordination presented in Sec. II.1.b and II.1.c, strong coordination requires that the probability distribution of the sequences of symbols converges to a target i.i.d. probability distribution.

Giulia Cervia investigates a joint source-channel coding problem in which both encoder and decoder have state information, as in (Le Treust, 2015c, [IC13]). She proposes a practical coding scheme based on polar codes that ensures the strong coordination of the symbols of source and channel. This research work resulted in the following publications:

[J9] Cervia, G. and Luzzi, L. and Le Treust, M. and Bloch, M. *Strong coordination of signals and actions over noisy channels with two-sided state information*, IEEE Transactions on Information Theory, Volume: 66, Issue: 8, Pages: 4681-4708, Aug. 2020.

[IC21] Cervia, G. and Luzzi, L. and Le Treust, M. and Bloch, M. *Strong Coordination Over Noisy Channels with Strictly Causal Encoding*, IEEE 56th Allerton Conference on Control Communication and Computing, Monticello, Illinois, 2018.

[IC19] Cervia, G. and Luzzi, L. and Le Treust, M. and Bloch, M. *Strong Coordination of Signals and Actions over Noisy Channels*, IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, 2017.

[IC17] Cervia, G. and Luzzi, L. and Bloch, M. and Le Treust, M. *Polar coding for empirical coordination of signals and actions over noisy channels*, IEEE Proc. of the Information Theory Workshop (ITW), Cambridge, UK, 2016.

[NC7] Cervia, Giulia and Luzzi, Laura and Le Treust, Mael and Bloch, Matthieu R., *Polar codes for empirical coordination over noisy channels with strictly causal encoding*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Juan-les-Pins, France, 2017.

[P1] Cervia, G., Luzzi, L., Bloch, M., and Le Treust, M., *Polar coding for empirical coordination of signals and actions over noisy channels*, European School on Information Theory, Gothenburg (ESIT), Sweden, April 4-8, 2016

### II.2.b Multi-decoders Bayesian persuasion with Rony Bou Rouphael

From 2019 to 2022, Rony Bou Rouphael is doing a PhD at ETIS UMR 8051 in Cergy under the direction of Inbar Fijalkow and my supervision. He works on three extensions of the Bayesian persuasion model of (Le Treust and Tomala, 2019, [J8]), with several decoders and restricted communication.

In the model of successive refinement of Equitz and Cover (1991) and Rimoldi (1994), the encoder uses a common channel to both decoders and a private channel to the first decoder. Rony Bou Rouphael characterizes the single-letter solution of the Bayesian persuasion game where the encoder performs a successive refinement coding. In the model of Gray and Wyner (1974), an additional private channel is linked to the second decoder. Rony Bou Rouphael provides lower and upper bounds on the optimal cost of the encoder, by assuming that the decoder cost functions depend on the actions of the other
decoder. He also investigates the strategic version of the cascade multiple description network problem
of Yamamoto (1981). This research work resulted in the following publications:

[IC31] Bou Rouphael, R., Le Treust, M., *Strategic Communication with Cost-Dependent Decoders via the Gray-Wyner Network*, IEEE Information Theory Workshop (ITW), Mumbai, 2022.

[IC29] Bou Rouphael, R. and Le Treust, M., *Strategic Successive Refinement Coding for Bayesian Persuasion with Two Decoders*, IEEE Information Theory Workshop (ITW) 2021, Kanazawa, Japan.

[IC24] Bou Rouphael, R. and Le Treust, M., *Impact of Private Observation in Bayesian Persuasion*, International Conference on NETwork Games, Control and Optimisation (NETGCOOP), Cargèse, Corsica, France on March 18-20, 2020.

[NC10] Bou Rouphael, R. and Le Treust, M., *Communication stratégique via le réseau Gray-Wyner*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Nancy, France, 2022.

[P2] Bou Rouphael, R. and Le Treust, M., *Impact of Private Observation in Persuasion Game*, GAMENET Conference 2019, Prague, Czech Republic, Nov. 21-22, 2019

[W5] Bou Rouphael, R. and Le Treust, M., *Strategic Successive Refinement for Bayesian Persuasion with Cost-Dependent Decoders*, submitted to IEEE JSAIT, Apr. 2022.

## II.2.c Zero-error source coding problems with Nicolas Charpenay and Aline Roumy

From 2020 to 2023, Nicolas Charpenay is doing a PhD at IRISA UMR 6074 in Rennes under the direction of Aline Roumy and my supervision. He works on zero-error source coding problems with side information at the decoder, that are related to the video compression. The zero-error assumption requires that the probability of error in the coding, is exactly zero. The optimal compression rate of this difficult open problem corresponds to the minimal entropy of a coloring of the characteristic graph, see Witsenhausen (1976) and Alon and Orlitsky (1996).

Nicolas Charpenay characterizes the zero-error coding rate for the successive refinement coding problem, i.e. with several decoders, in which the encoder observes the decoder side information. This scenario arises in interactive compression, where the user can randomly access part of the data directly in the compressed domain. He also investigates the model with one decoder and two-sided state-information, i.e. when the encoder observes a degraded version of the decoder side information. Following up the work of Orlitsky and Roche (2001), he determines the appropriate graph to study the problem of zero-error coding for computing. During the Master internship, Nicolas Charpenay used to work on zero-error channel coding problem, introduced in Shannon (1956). This research work resulted in the following publications:

[IC30] Charpenay, N., Le Treust, M. and Roumy, A., *Zero-error source coding when side information may be present*, International Zürich Seminar, March, 2022.

[IC25] Charpenay, N. and Le Treust, M., *Zero-Error Coding with a Generator Set of Variable-Length Words*, IEEE International Symposium on Information Theory (ISIT), Los Angeles, June 2020.

[NC11] Charpenay, N. and Le Treust, M. and Roumy, A., *Codage de source zéro-erreur pour un réseau de Gray-Wyner lorsque l'information adjacente peut être présente*, Actes de la Conférence du Groupement de Recherche en Traitement du Signal et des Images (GRETSI), Nancy, France, 2022.

[W6] Charpenay, N., Le Treust, M. and Roumy, A., *Zero-error source coding with two-sided side-information*, submitted to IEEE JSAIT, Apr. 2022.
[W4] Charpenay, N. and Le Treust, M. *Variable-Length Coding for Zero-Error Channel Capacity*, preliminary draft, [on-line] available: https://arxiv.org/abs/2001.03523, Jan. 2020.

## II.3 Content of this manuscript

This manuscript is organized as follows.

Chap. III presents some key results from the Information Theory literature such as the lossy source coding theorem of Shannon (1959), the channel coding theorem of Shannon (1948) and show the connection to the problem of rational inattention of Sims (2003) in Game Theory.

Chap. IV introduces the coordination problem of Gossner et al. (2006) and its reformulation in Cuff et al. (2010) and Cuff and Zhao (2011). We present the main contributions to the coordination problem described in Sec. II.1.b, when the channel between the encoder and the decoder is noisy.

Chap. V presents three different research directions that are extensions of the coordination results: 1) the channel state masking problem of Merhav and Shamai (2007) described in Sec. II.1.c, 2) the decentralized control problem of Witsenhausen (1968) described in Sec. II.1.d and 3) the strong coordination problem of Cuff et al. (2010) described in Sec. II.2.a.

Chap. VI details the contributions of Sec. II.1.e and II.2.b regarding the Bayesian persuasion game of Kamenica and Gentzkow (2011) with restricted communication, with decoder side information and with several decoders.

Chap. VII presents the on-going research work on zero-error source coding of II.2.c, on convex optimization algorithms for coordination problems, and on mechanism design and cheap talk problems. Our information theoretic approach will further be used to study repeated games with imperfect monitoring and incomplete information.
Chapter III

Information Theory review

<figure><img src="image_8.png" /><figcaption>Fig. 1. — Schematic diagram of a general communication system.</figcaption></figure>

(Fig. 1 in Shannon (1948))

In this chapter, we recall the lossy source coding result of Shannon (1959), the notion of channel capacity of Shannon (1948) and the “separation result” for the joint source-channel coding problem (El Gamal and Kim, 2011, Sec. 3.9). We discuss the connection with the problem of rational inattention of Sims (2003) and we present the optimality conditions of the distortion-rate function in (Steiner et al., 2017, Theorem 1). We extend the lossy source coding result to several cost functions.

Contents

<table><tr><td>III.1 Shannon's separation results</td><td>22</td></tr><tr><td>III.1.a Perfect channel of restricted cardinality</td><td>22</td></tr><tr><td>III.1.b General noisy channel</td><td>24</td></tr><tr><td>III.1.c Entropy formulas</td><td>25</td></tr><tr><td>III.2 Perfect channel of fixed capacity</td><td>26</td></tr><tr><td>III.2.a Lossy source coding</td><td>26</td></tr><tr><td>III.2.b Rational inattention</td><td>27</td></tr><tr><td>III.2.c Multi-objective coding problem</td><td>28</td></tr></table>
### III.1 Shannon's separation results

We recall some notations. We denote by $\Delta(\mathcal{X})$ the set of probability distributions $\mathcal{P}_X$ over the finite set $\mathcal{X}$, i.e. the symbol $x \in \mathcal{X}$ is selected with probability $\mathcal{P}_X(x) \in [0, 1]$. We denote by $\Delta(\mathcal{Y})^{|\mathcal{X}|}$ the set of conditional probability distributions $\mathcal{P}_{Y|\mathcal{X}}$.

#### III.1.a Perfect channel of restricted cardinality

Consider a source of information $(\mathcal{U}, \mathcal{P}_U)$ with $|\mathcal{U}| = 3$ symbols and a perfect channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|\mathcal{X}})$, i.e. $\mathcal{T}_{Y|\mathcal{X}}(y|x) = \mathbb{1}\{x = y\}$, with $|\mathcal{X}| = |\mathcal{Y}| = 2$ symbols. Is it possible to convey a source of information through a perfect channel which has fewer symbols?

Information Theory provides an answer to this question by applying the law of large numbers and by considering a repeated version of this problem. Unlikely sequences having an incorrect empirical distribution $\tilde{u}^n \in \mathcal{U}^n$ are assigned to a single sequence of channel symbols $\tilde{x}^n \in \mathcal{X}^n$, while the sequences with a correct empirical distribution $u^n \in \mathcal{U}^n$ are perfectly recovered with high probability. The number of sequences with a correct empirical distribution scales exponentially with the Shannon's entropy of the source distribution $\mathcal{P}_U \in \Delta(\mathcal{U})$. We present seminal results of Shannon (1948, 1959) addressing this question.

In this section, we consider a source of information $(\mathcal{U}, \mathcal{P}_U)$, a perfect channel $\mathcal{X}$ of fixed cardinality $|\mathcal{X}|$, a finite set of decoder actions $\mathcal{V}$, and a cost function

$$c: \mathcal{U} \times \mathcal{V} \to \mathbb{R}. \qquad (\text{III.1})$$

The information source generates an i.i.d. sequence $U^n$ of length $n \in \mathbb{N}^*$. The encoder observes the realization of the source sequence $u^n \in \mathcal{U}^n$ and selects a channel inputs sequence $x^n \in \mathcal{X}^n$. The decoder

<figure><img src="image_9.png" /><figcaption>Figure III.1 – Perfect channel of restricted cardinality $|\mathcal{X}|$.</figcaption></figure>

perfectly observes $x^n \in \mathcal{X}^n$ and returns a sequence of actions $v^n \in \mathcal{V}^n$.

In this manuscript, we define the encoding and decoding functions by

$$\sigma: \mathcal{U}^n \to \Delta(\mathcal{X}^n), \qquad (\text{III.2})$$

$$\tau: \mathcal{X}^n \to \Delta(\mathcal{V}^n). \qquad (\text{III.3})$$

Note that the encoding and decoding functions are stochastic, i.e. they generate the sequences of random variables $X^n$ and $V^n$. In some scenarios, e.g. in the Bayesian persuasion game of Kamenica and Gentzkow (2011) and in Physical Layer Security Bloch and Barros (2011), it is important to consider stochastic encoding and the decoding functions.

The coding scheme, depicted in Fig. III.1, induces a probability distribution over the sequences of symbols $(U^n, X^n, V^n)$ given by

$$\Pr((U^n, X^n, V^n) = (u^n, x^n, v^n)) = \left(\prod_{t=1}^{n} \mathcal{P}_U(u_t)\right) \sigma(x^n|u^n)\tau(v^n|x^n), \quad \forall (u^n, x^n, v^n). \qquad (\text{III.4})$$

**Definition 1** Given $n \in \mathbb{N}^*$, the minimum expected long-run cost is defined by

$$C_{\mathrm{p}}^{n}=\min _{\sigma, \tau} \mathbb{E}\left[\frac{1}{n} \sum_{t=1}^{n} c(U_{t}, V_{t})\right], \qquad (\text{III.5})$$

where the probability distribution of the random variables $(U_t, V_t)$, for $t \in \{1, \dots, n\}$, is given by (III.4).
Note that the sequence $(n \cdot C_p^n)_{n \in \mathbb{N}^*}$ is subadditive, i.e. $\forall (n, m) \in \mathbb{N}^{*2}$, $(n+m)C_p^{n+m} \le nC_p^n + mC_p^m$. This property is obtained by considering the concatenation of the optimal coding scheme $(\sigma, \tau)$ in (III.5) for some $n \in \mathbb{N}^*$, with the optimal coding scheme for some $m \in \mathbb{N}^*$.

**Definition 2** The optimal single-letter cost is defined by

$$C_p^* = \min_{\substack{Q_{V|U}, \\ I(U;V) \le \log_2 |\mathcal{X}|}} \mathbb{E}[c(U, V)], \qquad (III.6)$$

where the mutual information is defined by

$$I(U;V) = \sum_{(u,v) \in \text{supp} \mathcal{P}_U \mathcal{Q}_{V|U}} \mathcal{P}_U(u) \mathcal{Q}_{V|U}(v|u) \log_2 \frac{\mathcal{Q}_{V|U}(v|u)}{\sum_{u'} \mathcal{P}_U(u') \mathcal{Q}_{V|U}(v|u')}. \qquad (III.7)$$

Beside its definition in (III.7), the mutual information $I(U;V) = D_{KL}(\mathcal{P}_U \mathcal{Q}_{V|U} || \mathcal{P}_U \mathcal{Q}_V)$ is also the KL-divergence, see Kullback and Leibler (1951), between the joint distribution $\mathcal{P}_U \mathcal{Q}_{V|U} \in \Delta(\mathcal{U} \times \mathcal{V})$ and the product of marginal distributions $\mathcal{P}_U \mathcal{Q}_V \in \Delta(\mathcal{U}) \times \Delta(\mathcal{V})$, where $\mathcal{Q}_V = \sum_{u'} \mathcal{P}_U(u') \mathcal{Q}_{V|U}(\cdot|u')$.

**Theorem 1**

$$\lim_{n \to +\infty} C_p^n = \inf_{n \in \mathbb{N}^*} C_p^n = C_p^*. \qquad (III.8)$$

The proof of Theorem 1, see Shannon (1948, 1959), consists of two parts:

1. The achievability proof, which relies on a coding construction, shows that $\lim_{n \to +\infty} C_p^n \le C_p^*$.

2. The converse proof shows that $C_p^* \le \inf_{n \in \mathbb{N}^*} C_p^n$.

The sequence $(n \cdot C_p^n)_{n \in \mathbb{N}^*}$ is subadditive, Fekete (1923)'s Lemma shows that $\inf_{n \in \mathbb{N}^*} C_p^n = \lim_{n \to +\infty} C_p^n$. In conclusion, we have

$$C_p^* \le \inf_{n \in \mathbb{N}^*} C_p^n = \lim_{n \to +\infty} C_p^n \le C_p^*. \qquad (III.9)$$

Theorem 1 provides an answer to the question in the beginning of Sec. III.1.a. When $n \in \mathbb{N}^*$ is large enough, it is possible to convey the source random variable $U$ via the perfect channel $\mathcal{X}$ with $|\mathcal{X}| < |\mathcal{U}|$ if and only if $H(U) \le \log_2 |\mathcal{X}|$ where Shannon's entropy function is defined by

$$H(U) = \sum_{u \in \text{supp} \mathcal{P}_U} \mathcal{P}_U(u) \log_2 \frac{1}{\mathcal{P}_U(u)}. \qquad (III.10)$$

More precisely, we have the following proposition.

**Proposition 1** Consider that $\mathcal{V} = \mathcal{U}$ and $c(u, v) = \mathbb{1}\{u \ne v\}$.

$$C_p^* = 0 \iff H(U) \le \log_2 |\mathcal{X}|. \qquad (III.11)$$

*Proof.* [Prop. 1] We denote by $\tilde{\mathcal{Q}}_{V|U}$ the distribution that achieves the minimum in (III.6). Therefore

$$0 = \mathbb{E}_{\tilde{\mathcal{Q}}_{V|U}}[\mathbb{1}\{U \ne V\}] = \sum_u \mathcal{P}_U(u) \sum_v \tilde{\mathcal{Q}}_{V|U}(v|u) \mathbb{1}\{u \ne v\} \iff \forall u \in \mathcal{U}, \quad \text{supp} \tilde{\mathcal{Q}}_{V|U}(\cdot|u) = \{u\}. \qquad (III.12)$$

This implies that the conditional entropy satisfies

$$H(U|V) = \sum_{(u,v) \in \text{supp} \mathcal{P}_U \tilde{\mathcal{Q}}_{V|U}} \mathcal{P}_U(u) \tilde{\mathcal{Q}}_{V|U}(v|u) \log_2 \frac{1}{\tilde{\mathcal{Q}}_{V|U}(v|u)} = \sum_u \mathcal{P}_U(u) \log_2 1 = 0, \qquad (III.13)$$
and therefore, by definition,

$$ \log_2 |\mathcal{X}| \geq I(U;V) = H(U) - H(U|V) = H(U). \qquad (\text{III.14}) $$

The converse holds since $I(U;V) \leq H(U)$ is true for all distribution $Q_{V|U} \in \Delta(\mathcal{V})^{|U|}$. Hence the above distribution $\tilde{Q}_{V|U}$ satisfies

$$ I(U;V) \leq H(U) \leq \log_2 |\mathcal{X}|, \qquad \mathbb{E}_{\tilde{Q}_{V|U}}[\mathbb{1}\{U \neq V\}] = 0. \qquad (\text{III.15}) $$

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

**Example 1** Consider an information source with $\mathcal{U} = \{0,1,2\}$, $\mathcal{P}_U = (1-\alpha, \alpha/2, \alpha/2)$ and the perfect channel $\mathcal{X} = \{0,1\}$. Let $\alpha^* \in [0,1]$ the unique solution of $1-\alpha = h_b(\alpha)$ where the binary entropy function is defined by $h_b(\alpha) = \alpha \log_2 \frac{1}{\alpha} + (1-\alpha) \log_2 \frac{1}{1-\alpha}$ for all $\alpha \in [0,1]$ [and $h_b(\alpha) = 0$ for $\alpha \in \{0,1\}$]. Then for all $\alpha \in [0, \alpha^*]$, we have $H(U) \leq \log_2 |\mathcal{X}|$ which implies that $\lim_{n \to +\infty} C_{\mathbf{p}}^n = \inf_{n \in \mathbb{N}^*} C_{\mathbf{p}}^n = 0$. This shows that the decoder can perfectly recover the information source.

### III.1.b General noisy channel

We consider a general noisy channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|X})$, i.e. where $\mathcal{T}_{Y|X} \neq \mathbb{1}\{x=y\}$. The encoder wants to send $n \in \mathbb{N}^*$ symbols of source $(\mathcal{U}, \mathcal{P}_U)$ by using $k \in \mathbb{N}^*$ times the channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|X})$. The encoding and decoding functions are defined by

$$ \sigma: \mathcal{U}^n \to \Delta(\mathcal{X}^k), \qquad (\text{III.16}) $$

$$ \tau: \mathcal{Y}^k \to \Delta(\mathcal{V}^n). \qquad (\text{III.17}) $$

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

Figure III.2 – Point-to-point scenario with $n \in \mathbb{N}^*$ uses of the source $(\mathcal{U}, \mathcal{P}_U)$ and $k \in \mathbb{N}^*$ uses of the channel $(\mathcal{X}, \mathcal{Y}, \mathcal{T}_{Y|X})$.

The coding scheme, depicted in Fig. III.2, induces a probability distribution given by for all $(u^n, x^k, y^k, v^n)$

$$ \Pr((U^n, X^k, Y^k, V^n) = (u^n, x^k, y^k, v^n)) = \left(\prod_{t=1}^{n} \mathcal{P}_U(u_t)\right) \sigma(x^k|u^n) \left(\prod_{t=1}^{k} \mathcal{T}_{Y|X}(y_t|x_t)\right) \tau(v^n|y^k). \qquad (\text{III.18}) $$

**Definition 3** Given $n \in \mathbb{N}^*$, the minimum expected long-run cost is defined by

$$ C_c^{n,k} = \min_{\sigma, \tau} \mathbb{E} \left[ \frac{1}{n} \sum_{t=1}^{n} c(U_t, V_t) \right]. \qquad (\text{III.19}) $$

**Definition 4** Given a parameter $r \geq 0$, we define the optimal single-letter cost by

$$ C_c^*(r) = \min_{\substack{\mathcal{Q}_{V|U}, \\ I(U;V) \leq r \max_{\mathcal{P}_X} I(X;Y)}} \mathbb{E}[c(U, V)]. \qquad (\text{III.20}) $$
The channel capacity is defined by

$$ \max_{\mathcal{P}_X} I(X;Y) = \max_{\mathcal{P}_X} \sum_{(x,y) \in \text{supp} \mathcal{P}_X \mathcal{T}_{Y|X}} \mathcal{P}_X(x) \mathcal{T}_{Y|X}(y|x) \log_2 \frac{\mathcal{T}_{Y|X}(y|x)}{\sum_{x'} \mathcal{P}_{X}(x') \mathcal{T}_{Y|X}(y|x')}, \quad (\text{III.21}) $$

where the maximum is taken over the set of probability distribution $\Delta(\mathcal{X})$. Note that when the channel is perfect, i.e. $\mathcal{T}_{Y|X}(y|x) = \mathbb{1}\{x = y\}$ for all $(x, y)$, the channel capacity satisfies

$$ \max_{\mathcal{P}_X} I(X;Y) = \max_{\mathcal{P}_X} H(X) = \log_2 |\mathcal{X}|, \quad (\text{III.22}) $$

and we recover the result of Theorem 1.

We now introduce the notation $\lfloor x \rfloor$ for the floor function, i.e. the greatest integer less than or equal to $x \in \mathbb{R}$.

**Theorem 2.** For all $(n, k) \in \mathbb{N}^{\star 2}$, we have

$$ C_c^*(\frac{k}{n}) \leq C_c^{n,k}. \quad (\text{III.23}) $$

2. Suppose that $k = \lfloor rn \rfloor$ for some parameter $r \ge 0$, we have

$$ \lim_{n \to +\infty} C_c^{n,k} \leq C_c^*(r). \quad (\text{III.24}) $$

The Theorem 1 is referred to as the “separation result” for the joint source-channel coding problem in (El Gamal and Kim, 2011, Sec. 3.9). For $k = \lfloor rn \rfloor$ with $r \ge 0$, Theorem 2(1.&2.) implies that

$$ \lim_{n \to +\infty} C_c^{n,k} = \inf_{n \in \mathbb{N}^*} C_c^{n,k} = C_c^*(r). \quad (\text{III.25}) $$

### III.1.c Entropy formulas

We recall the definitions of the entropy function and the mutual information. We present some properties, the proofs are detailed in (Cover and Thomas, 2006, Chap. 2), (El Gamal and Kim, 2011, Chap. 2), (Csiszár and Körner, 2011, Chap. 1).

**Definition 5** Given a distribution $\mathcal{P}_{UV} \in \Delta(\mathcal{U} \times \mathcal{V})$ we define the mutual information $I(U;V)$, the conditional entropy $H(U|V)$ and the entropy $H(U,V)$ by

$$ I(U;V) = \sum_{(u,v) \in \text{supp} \mathcal{P}_{UV}} \mathcal{P}_{UV}(u,v) \log_2 \frac{\mathcal{P}_{UV}(u,v)}{\mathcal{P}_U(u)\mathcal{P}_V(v)}, \quad (\text{III.26}) $$

$$ H(U|V) = \sum_{(u,v) \in \text{supp} \mathcal{P}_{UV}} \mathcal{P}_{UV}(u,v) \log_2 \frac{1}{\mathcal{P}_{U|V}(u|v)}, \quad (\text{III.27}) $$

$$ H(U,V) = \sum_{(u,v) \in \text{supp} \mathcal{P}_{UV}} \mathcal{P}_{UV}(u,v) \log_2 \frac{1}{\mathcal{P}_{UV}(u,v)}. \quad (\text{III.28}) $$

For a distribution $\mathcal{P}_{UVW} \in \Delta(\mathcal{U} \times \mathcal{V} \times \mathcal{W})$, the conditional mutual information $I(U;V|W)$ is defined by

$$ I(U;V|W) = \sum_{(u,v,w) \in \text{supp} \mathcal{P}_{UVW}} \mathcal{P}_{UVW}(u,v,w) \log_2 \frac{\mathcal{P}_{UV|W}(u,v|w)}{\mathcal{P}_{U|W}(u|w)\mathcal{P}_{V|W}(v|w)}. \quad (\text{III.29}) $$

These formulas are related through the chain rule for the entropy.
**Proposition 2** Given a discrete probability distribution $\mathcal{P}_{UV} \in \Delta(\mathcal{U} \times \mathcal{V})$, we have

$$0 \le H(U, V) = H(V) + H(U|V) = H(U) + H(V|U) \le \log_2 |\mathcal{U} \times \mathcal{V}|, \qquad (\text{III.30})$$

$$\begin{aligned} 0 \le I(U; V) &= H(V) - H(V|U) = H(U) - H(U|V) \\ &= H(U) + H(V) - H(U, V) = D_{KL}(\mathcal{P}_{UV} || \mathcal{P}_{U}\mathcal{P}_{V}) \le \min(H(U), H(V)), \end{aligned} \qquad (\text{III.31})$$

where $D_{KL}(\mathcal{P}_{UV} || \mathcal{P}_{U}\mathcal{P}_{V})$ denotes the KL-divergence Kullback and Leibler (1951). We have $H(U, V) = \log_2 |\mathcal{U} \times \mathcal{V}|$ if and only if $\mathcal{P}_{UV}$ is the uniform distribution.

**Proposition 3** For a distribution $\mathcal{P}_{UVW} \in \Delta(\mathcal{U} \times \mathcal{V} \times \mathcal{W})$, we have

$$\begin{aligned} 0 \le I(U; V|W) &= H(V|W) - H(V|U, W) = H(U|W) - H(U|V, W) \\ &= H(U|W) + H(V|W) - H(U, V|W), \end{aligned} \qquad (\text{III.32})$$

$$0 \le I(U; V, W) = I(U; W) + I(U; V|W) = I(U; V) + I(U; W|V). \qquad (\text{III.33})$$

**Definition 6** A distribution $\mathcal{P}_{UVW} \in \Delta(\mathcal{U} \times \mathcal{V} \times \mathcal{W})$ satisfies the Markov chain property $U \leftarrow V \leftarrow W$ if

$$\mathcal{P}_{U|VW} = \mathcal{P}_{U|V} \iff \mathcal{P}_{W|UV} = \mathcal{P}_{W|V}. \qquad (\text{III.34})$$

**Proposition 4** A distribution $\mathcal{P}_{UVW} \in \Delta(\mathcal{U} \times \mathcal{V} \times \mathcal{W})$ satisfies the Markov chain property $U \leftarrow V \leftarrow W$ if and only if

$$I(U; W|V) = 0. \qquad (\text{III.35})$$

## III.2 Perfect channel of fixed capacity

### III.2.a Lossy source coding

In this section, we consider the lossy source coding problem introduced in Shannon (1959). The channel is perfect and has a fixed capacity $R \ge 0$, also referred to as the “rate of the code”. This parameter $R \ge 0$ is the increase rate of the number of messages $2^{\lfloor nR \rfloor}$ used by the coding scheme.

**Definition 7** Given $n \in \mathbb{N}^*$ and $R \ge 0$, a $(R, n)$-code is a pair of functions $(\sigma, \tau)$ defined by

$$\sigma: \mathcal{U}^n \to \Delta(\{1, \dots, 2^{\lfloor nR \rfloor}\}), \qquad (\text{III.36})$$

$$\tau: \{1, \dots, 2^{\lfloor nR \rfloor}\} \to \Delta(\mathcal{V}^n). \qquad (\text{III.37})$$

We denote by $\mathcal{C}(R, n)$ the set of $(R, n)$-codes.

<figure><img src="image_12.png" /><figcaption>Figure III.3 – The source $(\mathcal{U}, \mathcal{P}_U)$ and the perfect channel of rate $R \ge 0$.</figcaption></figure>

Note that $R = \log_2 |\mathcal{X}|$ is equivalent to $2^{nR} = |\mathcal{X}^n|$. Note also that $\frac{1}{n}|nR| \to R$, when $n \to +\infty$. A $(R, n)$-code $(\sigma, \tau) \in \mathcal{C}(R, n)$ induces a probability distribution given by,

$$\Pr((U^n, M, V^n) = (u^n, m, v^n)) = \left(\prod_{t=1}^{n} \mathcal{P}_{U}(u_t)\right) \sigma(m|u^n)\tau(v^n|m), \quad \forall (u^n, m, v^n). \qquad (\text{III.38})$$
**Definition 8** Given $n \in \mathbb{N}^*$, the minimum expected long-run cost is defined by

$$C^n(\mathbf{R}) = \min_{(\sigma, \tau) \in \mathcal{C}(\mathbf{R}, n)} \mathbb{E} \left[ \frac{1}{n} \sum_{t=1}^{n} c(U_t, V_t) \right]. \qquad (\text{III.39})$$

The sequence $(n \cdot C^n(\mathbf{R}))_{n \in \mathbb{N}^*}$ is subadditive. Since $\lfloor n\mathbf{R} \rfloor + \lfloor m\mathbf{R} \rfloor \le \lfloor (n+m)\mathbf{R} \rfloor$ for all $(n, m) \in \mathbb{N}^{*2}$, the concatenation of $(\sigma^n, \tau^n) \in \mathcal{C}(\mathbf{R}, n)$ with $(\sigma^m, \tau^m) \in \mathcal{C}(\mathbf{R}, m)$ generates a strategy which belongs to $\mathcal{C}(\mathbf{R}, n+m)$.

**Definition 9** The optimal single-letter cost is defined by

$$C^*(\mathbf{R}) = \min_{\substack{Q_{V|U}, \\ I(U; V) \le \mathbf{R}}} \mathbb{E}[c(U, V)]. \qquad (\text{III.40})$$

When the cost function $c(u, v)$ is a distortion function $d(u, v)$, the expression $C^*(\mathbf{R})$ is referred to as the “distortion-rate function”, see (Cover and Thomas, 2006, pp. 306). We recover $C_p^*$, resp. $C_n^*$, by replacing by replacing $\mathbf{R} = \log_2 |\mathcal{X}|$, resp. $\mathbf{R} = \max_{\mathcal{P}_X} I(X; Y)$, in the expression of $C^*(\mathbf{R})$.

**Theorem 3**

$$\lim_{n \to +\infty} C^n(\mathbf{R}) = \inf_{n \in \mathbb{N}^*} C^n(\mathbf{R}) = C^*(\mathbf{R}). \qquad (\text{III.41})$$

Theorem 3 is stated in Shannon (1959), a proof can be found in (El Gamal and Kim, 2011, Sec. 3.6).

### III.2.b Rational inattention

The expression $C^*(\mathbf{R})$ of (III.40) is related to the rational inattention problem in (Sims, 2003, Sec. 3), in the Game Theory literature. The rate parameter $\mathbf{R} \ge 0$ captures the information-processing capacity of a decision maker who faces a signal extraction problem. She decides how much effort to put in order to get a finer information about the source $(\mathcal{U}, \mathcal{P}_U)$. The conditional distribution $Q_{V|U}$ determines the signal extraction strategy. The decision maker is rationally inattentive when she optimizes the trade-off between the information extraction cost $I(U; V)$ and the information exploitation to lower $\mathbb{E}[c(U, V)]$.

In (Steiner et al., 2017, Eq. (3)-(5)), the authors forumate the Lagrangian of $C^*(\mathbf{R})$. For all conditional distribution $Q_{V|U} \in \Delta(\mathcal{V})^{|\mathcal{U}|}$ and Langrange parameter $\lambda \ge 0$, they define

$$\mathcal{L}(Q_{V|U}, \lambda) = \mathbb{E}[c(U, V)] + \lambda I(U; V). \qquad (\text{III.42})$$

Note that

$$C^*(\mathbf{R}) = \min_{Q_{V|U}} \max_{\lambda \ge 0} (\mathcal{L}(Q_{V|U}, \lambda) - \lambda \mathbf{R}). \qquad (\text{III.43})$$

For a given Lagrange parameter $\lambda \ge 0$, the problem of interests writes

$$\min_{Q_{V|U}} \mathcal{L}(Q_{V|U}, \lambda). \qquad (\text{III.44})$$

The optimality conditions are stated in (Steiner et al., 2017, Theorem 1).

**Theorem 4** We denote by $Q_{V|U}^*$ the optimal solution to problem (III.44) with marginal distribution $Q_V^* = \sum_u \mathcal{P}_U(u) Q_{V|U}^*(\cdot|u) \in \Delta(\mathcal{V})$. For all $(u, v) \in \mathcal{U} \times \mathcal{V}$, the optimal solution satisfies

$$Q_{V|U}^*(v|u) = \frac{Q_V^*(v) \exp\left(-\frac{c(u,v)}{\lambda}\right)}{\sum_{v'} Q_V^*(v') \exp\left(-\frac{c(u,v')}{\lambda}\right)}. \qquad (\text{III.45})$$

A similar characterization of $Q_{V|U}^*$ is proposed in (Blahut, 1972, Theorem 5) for the related problem

$$\mathbf{R}^*(C) = \min_{\substack{Q_{V|U}, \\ \mathbb{E}[c(U, V)] \le C}} I(U; V), \qquad (\text{III.46})$$

which depends of a target cost value $C \in \mathbb{R}$.
### III.2.c Multi-objective coding problem

In this section, we consider a coding problem in which the encoder and the decoder are endowed with distinct cost functions

$$c_e : \mathcal{U} \times \mathcal{V} \to \mathbb{R} \neq c_d : \mathcal{U} \times \mathcal{V} \to \mathbb{R}. \qquad (III.47)$$

In this section, we assume that a unique decision-maker selects the pair of encoding and decoding strategies $(\sigma, \tau)$. Therefore the decision problem has no strategic feature. This problem is not a game, it is a multi-objective coding problem.

**Definition 10** Given the pair of strategies $(\sigma, \tau) \in \mathcal{C}(\mathbb{R}, n)$, the encoder and decoder long-run cost functions $c_e^n(\sigma, \tau)$ and $c_d^n(\sigma, \tau)$ are defined by

$$c_e^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_e(u_t, v_t) \right], \qquad (III.48)$$

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

<figure><img src="image_13.png" /><figcaption>Figure III.4 – Two cost functions $c_e : \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ and $c_d : \mathcal{U} \times \mathcal{V} \to \mathbb{R}$.</figcaption></figure>

**Definition 11** The pair $(C_e^*, C_d^*)$ is achievable if

$$\forall \varepsilon > 0, \ \exists \bar{n} \in \mathbb{N}^*, \ \forall n \ge \bar{n}, \ \exists (\sigma, \tau) \in \mathcal{C}(\mathbb{R}, n), \ |C_e^* - c_e^n(\sigma, \tau)| + |C_d^* - c_d^n(\sigma, \tau)| \le \varepsilon. \qquad (III.50)$$

We denote by $\mathcal{A}(\mathbb{R})$ the set of achievable pairs $(C_e, C_d)$.

**Theorem 5** Given $R \ge 0$,

$$\mathcal{A}(\mathbb{R}) = \left\{ (\mathbb{E}_{\mathbb{Q}}[c_e(U, V)], \mathbb{E}_{\mathbb{Q}}[c_d(U, V)]), \ Q \in \mathbb{Q}(\mathbb{R}) \right\}, \qquad (III.51)$$

where the set of probability distribution is defined by

$$\mathbb{Q}(\mathbb{R}) = \{ \mathcal{P}_U \mathcal{Q}_{V|U}, \ I(U; V) \le \mathbb{R} \}. \qquad (III.52)$$

The proof of Theorem 5 is a consequence of the lossy source coding theorem of Shannon (1959) with two cost functions. For the converse proof, we recall that the information constraint $I(U; V) \le \mathbb{R}$ needs to be satisfied. For the achievability proof, given a probability distribution $\mathcal{P}_U \mathcal{Q}_{V|U} \in \mathbb{Q}$, we use the standard arguments to show the existence of a coding scheme that achieves the pair of costs $(\mathbb{E}_{\mathbb{Q}}[c_e(U, V)], \mathbb{E}_{\mathbb{Q}}[c_d(U, V)])$.

The key aspect of the solution is the set of achievable probability distributions $\mathbb{Q}$, which is the main object of study of Chap. IV.
# Chapter IV

## Empirical coordination with a strictly causal or a causal decoder

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

In the previous chapter, we have seen that the restrictions of communication are captured by an entropy constraint that affects the set of probability distributions. In a decentralized network, it is essential that the devices or the agents cooperate and coordinate their actions in order to achieve a common goal, to ensure the reliability and the stability of the network. More specifically, it is required that the sequences of actions and states follow a prescribed empirical distribution. This problem was investigated in Gossner et al. (2006) when the encoder actions are

perfectly observed by the decoder. We extend these results by assuming that the decoder imperfectly monitors encoder actions. Our point-to-point model involves an information source, a noisy channel and a common objective function for the encoder and the decoder. We wonder how this simple network operates when the devices have incomplete information about the state and imperfect monitoring of the actions. In this chapter, we present various empirical coordination problems under study in (Le Treust, 2017, [J6]), (Le Treust, 2015b, [IC14]), (Le Treust, 2015c, [IC13]), (Le Treust, 2014, [IC12]), (Le Treust, 2015a, [NC6]) (Le Treust, 2015, [W1]),

## Contents

<table><tr><td>IV.1 Introduction</td><td>30</td></tr><tr><td>IV.2 Empirical coordination with strictly causal decoder</td><td>33</td></tr><tr><td>IV.2.a Problem statement</td><td>33</td></tr><tr><td>IV.2.b Characterization of the set of achievable distributions</td><td>34</td></tr><tr><td>IV.2.c Evaluation of an arbitrary expected cost function</td><td>35</td></tr><tr><td>IV.2.d Example #1: coordination game of Gossner et al. (2006)</td><td>36</td></tr><tr><td>IV.2.e Example #2: Hamming distortion and channel cost</td><td>38</td></tr><tr><td>IV.3 General decoding functions</td><td>40</td></tr><tr><td>IV.3.a Causal decoding with source feedforward</td><td>40</td></tr><tr><td>IV.3.b Strictly causal decoding with source feedforward</td><td>42</td></tr><tr><td>IV.4 State-dependent source and state-dependent channel</td><td>43</td></tr><tr><td>IV.4.a Non-causal encoder and non-causal decoder</td><td>43</td></tr><tr><td>IV.4.b Causal decoder and non-causal encoder</td><td>47</td></tr><tr><td>IV.4.c Causal encoder and non-causal decoder</td><td>49</td></tr><tr><td>IV.5 Chapter summary</td><td>51</td></tr></table>
IV.1 Introduction

A decentralized network is composed of communication devices that sense their environment and that choose autonomously the best transmission scheme to implement. The decision process is decentralized and does not require a central controller. However, it is essential that the communication devices cooperate and coordinate their actions, in order to ensure the reliability of the transmissions and the stability of the network. We investigate the problem of the coordination of two autonomous devices, by considering a point-to-point model, represented by Fig. IV.1, with an information source and a noisy channel. In the classical scenario, both encoder and decoder have the same objective: to implement a reliable transmission scheme. We wonder how this simple network operates when the devices are autonomous and try to coordinate their actions in order to achieve a common objective.

We study this problem using a two-step approach. First, we characterize the set of empirical distri-
butions of actions and source symbols that are achievable via a coding scheme. Second, we optimize the
expected common cost function with respect to the set of achievable distributions. In this chapter, we
focus on the first task, i.e. determining the coordination possibilities of the encoder and the decoder by
characterizing the set of achievable distributions.

Based on their observations, the encoder and the decoder choose the sequences of channel input and
decoder’s output. We require that the empirical distribution of all the sequences of symbols, converges
to a target joint probability distribution. The aim is to determine the minimal amount of information
to exchange such that the symbols of both transmitters are coordinated with the symbols of the source
and of the channel. From an information theoretic point of view, this problem is closely related to
the joint source-channel coding problem with two-sided state information and correlated source and
state (Le Treust, 2015c, [IC13]). We characterize the set of achievable joint probability distributions
using a single-letter information constraint that is related to the compression and to the transmission of
information.

<figure><img src="image_15.png" /><figcaption>Figure IV.1 – Empirical coordination problem for the source ($\mathcal{U}$, $\mathcal{P}_U$), the channel ($\mathcal{X}$, $\mathcal{Y}$, $\mathcal{T}_{Y|X}$), the cost function $c: \mathcal{U} \times \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$ and the decoder is strictly causal, i.e. at each instant $t \in \{1, \dots, n\}$, it returns a symbol $V_t = \tau_t(Y^{t-1})$. The encoder and the decoder implement a coding scheme such that, the empirical distribution of symbols $\mathcal{Q}_{\mathcal{U}}^{n}$ are close to the target joint probability distribution $\mathcal{Q}_{\mathcal{U}\mathcal{X}\mathcal{Y}\mathcal{V}}$,</figcaption></figure>

We consider that the devices are equipped with a cost function, capturing their objective. The set of achievable values of the cost function is the image, by the expectation operator, of the set of achievable probability distributions. A cost value is achievable if and only if it corresponds to the expected cost, with respect to some achievable probability distribution. This approach simplifies the optimization of the long-run cost function, since the whole set of possible codes of large block-length reduces to the set of achievable target probability distributions, expressed with a single-letter formulation. As a particular case, our results boil down to the classical results of Shannon (1948) and Shannon (1959), when considering the minimal distortion for the information source or the minimal cost for the channel inputs. The main difference with the results of Shannon (1948) and Shannon (1959) is In this chapter, we consider a cost function that is common to both encoder and decoder.

Related literature

The notion of target probability distribution has been proposed in Wyner (1975) for determining
the common information of two correlated random variables. In the framework of quantum coding, the
authors of Kramer and Savari (2002) and Kramer and Savari (2007) prove the existence of a code with
minimal amount of information exchanged, such that the empirical distribution of the sequences of symbols is close to the target probability distribution. The problem of empirical coordination is studied in Cover and Permuter (2007) for a three-node cascade network, for a multi-agent chain and for a multiple description setting. A stronger definition of coordination is considered in Cuff (2008) and Cuff (2013) for the problem of simulating and synthesizing a discrete memoryless channel, also related to the “reverse Shannon Theorem” Bennett et al. (2002) and “channel resolvability” Han and Verdú (1993). The concept of “coordination capacity” is introduced in Cuff et al. (2010), as a measure of the minimal amount of information transmitted, such that the nodes of a network can coordinate their actions. The authors consider two different notions of coordination, referred to as empirical coordination and strong coordination. For some networks, both notions coincide if the nodes have enough common randomness. Coordination over a network is also related to the multi-agent control problem with common randomness Anantharam and Borkar (2007). In Gohari and Anantharam (2011), the authors investigate strong coordination of the actions, assuming that the nodes have multiple rounds of noise-free communication. Empirical distribution of sub-codewords of length *k* of a *good code* is considered in Weissman and Ordentlich (2004) and Weissman and Ordentlich (2005), and the authors prove that it converges to the product of the optimal probability distribution Shamai and Verdú (1997). Polar codes are under investigation for empirical coordination in Blasco-Serrano et al. (2012), and for strong coordination in Bloch et al. (2012). In Chou et al. (2015), the authors provide encoding and decoding algorithms that are based on polar codes, and that achieve the empirical and the strong coordination capacity. In (Cervia et al., 2016, [IC17]), the authors construct a polar code for empirical coordination with a noisy channel. Empirical coordination for triangular multi-terminal network is investigated in Bereyhi et al. (2013). Strong coordination is studied for a multi-hop line network in Vellambi et al. (2015) and Vellambi et al. (2016), for a three-terminal line network in Satpathy and Cuff (2013) and Bloch and Kliewer (2013), for a three-terminal relay network in Bloch and Kliewer (2014), for two-way communication with a relay in Haddadpour et al. (2012), and for signal's coordination in (Cervia et al., 2017b, [IC19]). The source coding problem of Ahlswede-Körner Ahlswede and Körner (1975) is investigated in Goldfeld et al. (2014), with a coordination requirement. The results for empirical coordination are extended to general alphabets in Raginsky (2010) and Raginsky (2013), by considering standard Borel spaces. The problems of zero-error coordination Abroshan et al. (2015) and of strong coordination with an evaluation function Orlitsky and Roche (2001) are both related to graph theory.

The problem of the coordination of actions is also investigated in the Game Theory literature Gossner and Vieille (2002), Gossner and Tomala (2006), Gossner and Tomala (2007), Gossner et al. (2009), Gossner et al. (2006) using the notion of *implementable probability distribution*, that is related to empirical coordination. In Gossner et al. (2006), the authors consider a point-to-point scenario with an encoder that observes the sequence of symbols of source, called “state of the nature”, and that chooses a sequence of actions. The channel is perfect and the decoder is strictly causal *i.e.*, it returns an action based on the observation of the past actions of the encoder and past symbols of the source. The objective is to coordinate the actions of both players together with the symbols of the source. The main difference with the settings described previously is that the channel inputs are also coordinated with the symbols of the source and the decoder’s actions. The encoder chooses a sequence of channel inputs that conveys some information and that is coordinated with the sequences of symbols of source. The authors characterize the set of implementable target joint probability distributions and evaluate the long-run cost function of the players, by considering the expected cost. The results of Gossner et al. (2006) are extended in Larrousse and Lasaulce (2013), Larrousse et al. (2018), by considering a noisy channel. The authors characterize the set of implementable probability distributions and apply their result to the interference channel in which the power control is used to encode embedded data about the channel state information. This approach is further applied to the two-way channel in Larrousse et al. (2015a), and to the case of causal encoding and decoding in Larrousse et al. (2015b). The results of Gossner et al. (2006) have also been extended in Cuff and Zhao (2011) by considering the notion of empirical coordination and by removing the observation by the decoder of the past symbols of source. The tools for empirical coordination with a cascade of controllers Cuff and Zhao (2011) are also used in Asnani et al. (2013), for the problem of cooperation in multi-terminal source coding with strictly causal, causal, and non-causal cribbing. In (Le Treust et al., 2011, [IC7]), the authors investigate the empirical correlation for two dependent sources and a broadcast channel with an additional secrecy constraint. The problem of empirical coordination for a joint source-
channel coding problem is solved in Cuff and Schieler (2011), for strictly causal and causal encoder with non-causal decoder. These results are based on hybrid coding Minero et al. (2011), Lim et al. (2010), and are closely related to the problem of state communication under investigation in Choudhuri et al. (2010), Choudhuri et al. (2011), Choudhuri and Mitra (2012a). The results stated in Cuff and Schieler (2011) are extended in (Le Treust, 2015b, [IC14]) by considering channel feedback available at the encoder. Channel feedback improves the coordination possibilities and simplifies the information constraint. For this problem, the authors of (Le Treust and Bloch, 2016, [IC16]) characterize of the region of achievable triple of information rate, empirical distribution and state leakage, with and without state information and noisy channel feedback. The problem of empirical coordination for non-causal encoder and decoder is not yet completely solved, but the optimal solutions are characterized in (Le Treust, 2014, [IC12]) for lossless decoding and in (Le Treust, 2015c, [IC13]) for perfect channel and for independent source and channel, based the separation result of Merhav and Shamai (2003). The duality Cover and Chiang (2002) between the channel coding of Gel'fand Pinsker Gel'fand and Pinsker (1980) and the source coding of Wyner Ziv Wyner and Ziv (1976) induces some similarities in the information constraints for lossless decoding (Le Treust, 2014, [IC12]) and for perfect channel (Le Treust, 2015c, [IC13]). This open problem is closely related to the problem of non-causal state communication, under investigation in Sutivong et al. (2005), Choudhuri et al. (2013) and Sutivong (2003). The problem of empirical coordination is a first step towards a better understanding of decentralized communication networks, in which the devices have different cost functions (Le Treust and Tomala, 2016, [IC18]) and choose autonomously the transmission power (Le Treust and Lasaulce, 2010, [J1]), Belmega et al. (2009) and the transmission rates Berry and Tse (2011), Perlaza et al. (2012), depending on their observation structure (Le Treust and Lasaulce, 2013, [J2]).

In this chapter, we investigate a point-to-point coordination problem involving an i.i.d. information source and a memoryless channel, represented by Fig. IV.1. The encoder and the decoder choose their sequences of actions i.e., channel input and decoder output, so that the empirical distribution of the symbols converges to a target probability distribution. We assume that the decoder is strictly causal or causal i.e., at each instant, it returns a symbol, also called an action, based on the observation of the past and current channel outputs. This on-line coordination assumption is related to the game theoretical framework of Gossner et al. (2006), in which the encoder and the decoder are the players that choose their actions simultaneously, based on their past observations. We characterize the set of achievable target joint probability distributions for non-causal encoder and strictly causal decoder and we relate the corresponding information constraint to the previous results from the literature, especially with the problem of source distortion and channel cost (El Gamal and Kim, 2011, pp. 47, 57 and 66). We analyze the optimization of some cost function over the set of achievable target probability distributions and we prove that this problem is convex. We also characterize the information constraint corresponding to causal decoder instead of strictly causal decoder. In that case, the actions of the decoder may also be coordinated with the current channel output.

This chapter is organized as follows. The coordination problem with strictly causal decoder is under study in Sec. IV.2. The system model is presented in Sec. IV.2.a. In Sec. V.2.b, we characterize the set of achievable target probability distributions for non-causal encoder and strictly causal decoder. In Sec. VII.2, we characterize the set of achievable utilities and we prove that the corresponding optimization problem is convex. We investigate two examples: the coordination game in Sec. IV.2.d and the trade-off between source distortion and channel cost in Sec. IV.2.e. In Sec. IV.3, we investigate the coordination problem for general decoding functions, with causal decoding and source feedforward in Sec. IV.3.a, with strictly causal decoding and source feedforward in Sec. IV.3.b. In Sec. IV.4, we investigate the coordination problem for state-dependent source and channel. The case of non-causal encoder and non-causal decoder under study in Sec. IV.4.a is still an open problem. We characterize the sets of achievable distributions when either the decoder is causal in Sec. IV.4.b, or the encoder is causal in Sec. IV.4.c.
IV.2 Empirical coordination with strictly causal decoder

IV.2.a Problem statement

We consider the setting of Fig. IV.1 in which a sequence of random variables $U^n \in \mathcal{U}^n$ is drawn i.i.d. according to $\mathcal{P}_U \in \Delta(\mathcal{U})$, as in (IV.1). The non-causal encoder observes $U^n \in \mathcal{U}^n$ and sends a sequence of channel inputs $X^n \in \mathcal{X}^n$. The sequence of channel outputs $Y^n \in \mathcal{Y}^n$ is drawn i.i.d. according to $\mathcal{T}_{Y|X} \in \Delta(\mathcal{Y})^{|\mathcal{X}|}$, as in (IV.2).

$$ \Pr(U^n = u^n) = \prod_{t=1}^{n} \mathcal{P}_U(u_t), \quad \forall u^n \in \mathcal{U}^n, \qquad (\text{IV.1}) $$

$$ \Pr(Y^n = y^n | X^n = x^n) = \prod_{t=1}^{n} \mathcal{T}_{Y|X}(y_t|x_t), \quad \forall (x^n, y^n) \in \mathcal{X}^n \times \mathcal{Y}^n. \qquad (\text{IV.2}) $$

We consider that the decoder is strictly causal. At instant $t \in \{1, \dots, n\}$, it observes the sequence of past channel outputs $Y^{t-1} = (Y_1, \dots, Y_{t-1}) \in \mathcal{Y}^{t-1}$ and returns an output symbol $V_t \in \mathcal{V}$.

**Definition 12** Given $n \in \mathbb{N}^*$, we define the n-length code with non-causal encoder and strictly-causal decoder by a pair $(\sigma, \tau)$ where $\tau = \{\tau_t\}_{t=1}^n$ and

$$ \sigma: \mathcal{U}^n \to \mathcal{X}^n, \qquad (\text{IV.3}) $$

$$ \tau_t: \mathcal{Y}^{t-1} \to \mathcal{V}, \quad t \in \{1, \dots, n\}. \qquad (\text{IV.4}) $$

We denote by $\mathcal{C}(n)$ the set of n-length code with non-causal encoder and strictly-causal decoder.

The code $(\sigma, \tau) \in \mathcal{C}(n)$ induces a probability distribution $\mathcal{P}_{U^n X^n Y^n V^n}^{\sigma \tau}$ defined, for all $(u^n, x^n, y^n, v^n)$, by

$$ \mathcal{P}_{U^n X^n Y^n V^n}^c(u^n, x^n, y^n, v^n) = \left( \prod_{t=1}^{n} \mathcal{P}_U(u_t) \right) \mathbf{1}\{x^n = \sigma(u^n)\} \left( \prod_{t=1}^{n} \mathcal{T}_{Y|X}(y_t|x_t) \right) \left( \prod_{t=1}^{n} \mathbf{1}\{v_t = \tau_t(y^{t-1})\} \right). \qquad (\text{IV.5}) $$

We evaluate the empirical frequencies of symbols induced by the code.

**Definition 13** Given the sequences of realizations $(u^n, x^n, y^n, v^n)$, the empirical distribution $q_{UXYV}^n \in \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ is defined by

$$ q_{UXYV}^n(u, x, y, v) = \frac{1}{n} \sum_{t=1}^{n} \mathbf{1}\{(u_t, x_t, y_t, v_t) = (u, x, y, v)\}, \quad \forall (u, x, y, v) \in \mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V}. \qquad (\text{IV.6}) $$

We denote by $Q_{UXYV}^n \in \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ the random variable of the empirical distribution of $(U^n, X^n, Y^n, V^n)$.

We aim at characterizing the asymptotic behavior of the empirical distribution $Q_{UXYV}^n$ induced by sequences of codes.

**Definition 14** A target probability distribution $Q_{UXVY} \in \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ is achievable if there exists a sequence of codes $(\sigma, \tau) \in \mathcal{C}(n)$ such that $(Q_{UXVY}^n)_{n \in \mathbb{N}^*}$ converges in probability to $Q_{UXVY}$, i.e.

$$ \forall \delta > 0, \quad \lim_{n \to +\infty} \min_{(\sigma, \tau) \in \mathcal{C}(n)} \Pr\left(\left\|Q_{UXVY}^n - Q_{UXVY}\right\|_1 > \delta\right) = 0. \qquad (\text{IV.7}) $$

We denote by $\mathcal{A} \subset \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ the set of achievable distributions.
The concept of achievable distribution was introduced in (Cuff et al., 2010, Definition 5). In Gossner et al. (2006), a distribution $Q_{UXVY}$ is said to be implementable if there exists a sequence of codes $(\sigma, \tau) \in \mathcal{C}(n)$ such that the average distribution $(\frac{1}{n} \sum_{t=1}^n P_{U_t X_t Y_t V_t})_{n \in \mathbb{N}^*}$ converges to the target distribution $Q_{UXVY}$. Note that for all $(u, x, y, v)$, we have

$$ \frac{1}{n} \sum_{t=1}^{n} P_{U_t X_t Y_t V_t}^{c}(u, x, y, v) = \frac{1}{n} \sum_{t=1}^{n} \mathbb{E}[1\{(U_t, X_t, Y_t, V_t) = (u, x, y, v)\}] \quad (IV.8) $$

$$ = \mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n} 1\{(U_t, X_t, Y_t, V_t) = (u, x, y, v)\}\right] \quad (IV.9) $$

$$ = \mathbb{E}[Q_{UXVY}^{n}(u, x, y, v)]. \quad (IV.10) $$

The following Lemma is stated in (Larrousse et al., 2018, App. A).

**Lemma 1** If the distribution $Q_{UXVY}$ is achievable, then it is implementable, i.e.

$$ Q_{UXVY} \in \mathcal{A} \implies \lim_{n \to +\infty} \min_{(\sigma, \tau) \in \mathcal{C}(n)} \left| \mathbb{E}[Q_{UXVY}^{n}] - Q_{UXVY} \right| = 0. \quad (IV.11) $$

*Proof.* [Lemma 1] The convergence in probability implies the convergence in distribution. Therefore there exists a sequence of codes $(\sigma, \tau) \in \mathcal{C}(n)$ such that $(\mathbb{E}[Q_{UXVY}^{n}])_{n \in \mathbb{N}^*}$ converges to $Q_{UXVY}$. □

## IV.2.b Characterization of the set of achievable distributions

We characterize the set of achievable distributions for non-causal encoder and strictly-causal decoder. The following result is stated in (Le Treust, 2017, [J6], Theorem III.1).

**Theorem 6** A target probability distribution $Q_{UXYV} \in \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ is achievable if and only if

$$ Q_{UXYV} = \mathcal{P}_U Q_{XV|U} \mathcal{T}_{Y|X}, \quad (IV.12) $$

and there exists an auxiliary random variable $W_1 \in W_1$ with $|W_1| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}| + 1$, distributed according to some conditional distribution $\tilde{Q}_{W_1|UXV} \in \Delta(W_1)^{|\mathcal{U} \times \mathcal{X} \times \mathcal{V}|}$ such that

$$ I(W_1; Y|V) - I(U; V, W_1) \ge 0. \quad (IV.13) $$

Note that the joint probability distribution decomposes as

$$ \mathcal{P}_U Q_{XV|U} \tilde{Q}_{W_1|UXV} \mathcal{T}_{Y|X} \in \Delta(\mathcal{U} \times \mathcal{X} \times W_1 \times \mathcal{Y} \times \mathcal{V}). \quad (IV.14) $$

The proof of Theorem 6 is stated in (Le Treust, 2015, [W1]). Note that the Markov chain $Y \leftarrow X \leftarrow (U, V, W_1)$ comes from the hypothesis of strictly causal decoder. Indeed, the decoder returns a symbol $V_t = \tau_t(Y^{t-1})$ before the channel output $Y_t$ is generated.

**Remark 1** As mentioned in (IV.12), an achievable distribution $Q_{UXYV}$ must have the marginals given by the source distribution $\mathcal{P}_U$ and the channel distribution $\mathcal{T}_{Y|X}$. Otherwise, it is not achievable. This remark is valid for all the coding results in this document.

**Theorem 7** The set of achievable distributions is compact and convex, and it is characterized by

$$ \mathcal{A} = \left\{ \mathcal{P}_U Q_{XV|U} \mathcal{T}_{Y|X}, \max_{\substack{\tilde{Q}_{W_1|UXV}, \\ |W_1| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}|+1}} \left( I(W_1; Y|V) - I(U; V, W_1) \right) \ge 0 \right\}. \quad (IV.15) $$

Moreover, the function

$$ \Psi : \Delta(\mathcal{X} \times \mathcal{V})^{|\mathcal{U}|} \to \mathbb{R}, \quad (IV.16) $$

$$ Q_{XV|U} \to \max_{\substack{\tilde{Q}_{W_1|UXV}, \\ |W_1| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}|+1}} \left( I(W_1; Y|V) - I(U; V, W_1) \right), \quad (IV.17) $$

is concave in $Q_{XV|U} \in \Delta(\mathcal{X} \times \mathcal{V})^{|\mathcal{U}|}$.
The proof of Theorem 7 is stated in (Le Treust, 2017, [J6]). We compare the result of Theorem 6 with previous results from the literature. When, the channel is not noisy, i.e. $\mathcal{T}_{Y|X} = \mathbb{1}\{Y = X\}$, the set of implementable distributions of (Gossner et al., 2006, Theorems 1 and 2) coincides with the set of achievable distributions of (Cuff and Zhao, 2011, Theorem 5.1). We show that the information constraints of (Gossner et al., 2006, Eq. (1)) and of (Gossner et al., 2006, Theorem 5.1) coincide with (IV.13).

**Corollary 1** When $\mathcal{T}_{Y|X} = \mathbb{1}\{Y = X\}$, we have

$$ \max_{\substack{\tilde{Q}_{W_1|UXV} \\ |W_1| \le |U \times X \times V|+1}} \left( I(W_1; Y|V) - I(U; V, W_1) \right) = H(X|V) - I(U; X, V), \quad (IV.18) $$

and the maximum in the left-hand side of (IV.18) is achieved by $W_1 = X$.

**Proof.** [Corollary 1] When $Y = X$, for all distribution $\tilde{Q}_{W_1|UXV}$ we have

$$ I(W_1; X|V) - I(U; V, W_1) = I(W_1; X|V, U) - I(W_1; U|V, X) - I(U; V) \quad (IV.19) $$

$$ \leq H(X|V, U) - I(U; V) = H(X|V) - I(U; X, V). \quad (IV.20) $$

We obtain the equality by replacing $W_1 = X$. □

According to the separation result of Shannon (1959), the source random variables $(U, V)$ must be independent of the channel random variables $(X, Y)$.

**Corollary 2** Assume that $(U, V)$ are independent of $(X, Y)$, we have

$$ \mathcal{A} \cap \Delta(U \times V) \times \Delta(\mathcal{X} \times \mathcal{Y}) = \left\{ P_U Q_{V|U} Q_X T_{Y|X}, \quad I(X; Y) - I(U; V) \ge 0 \right\}. \quad (IV.21) $$

**Proof.** [Corollary 2] For all distribution $\tilde{Q}_{W_1|UXV}$, we have

$$ I(W_1; Y|V) - I(U; V, W_1) \leq I(W_1; V; Y) - I(U; V) \quad (IV.22) $$

$$ \leq I(X; Y) - I(U; V), \quad (IV.23) $$

where (IV.23) comes from the Markov chain property $Y \leftarrow X \leftarrow (U, V, W_1)$ of the channel. We have equality in (IV.22) and (IV.23) when choosing $W_1 = X$ independent of $(U, V)$. □

Corollary 2 also shows that strictly causal decoding has no impact on the information constraint $I(X; Y) - I(U; V) \ge 0$, stated in Shannon (1959). In fact this information constraint characterizes the optimal solution for non-causal encoding and strictly causal, causal or non-causal decoding. However, when we impose that the random variables $(X, Y)$ are correlated with $(U, V)$, the information constraint depends on whether the decoder works strictly causally, causally or non-causally.

**Remark 2 (Coordination is more restrictive than information transmission)** Equations (IV.22)-(IV.23) imply that the information constraint corresponding to $Q_{XV|U}$ is stronger than the one corresponding to the product of marginals $Q_{V|U}Q_X$. We conclude that the empirical coordination is more restrictive than lossless or lossy transmission of the information source.

### IV.2.c Evaluation of an arbitrary expected cost function

By building on the repeated game approach of Gossner et al. (2006), we consider that the encoder and the decoder implement a coding scheme in order to minimize an arbitrary cost function $\phi$ defined by

$$ \phi: \mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V} \to \mathbb{R}. \quad (IV.24) $$

This cost function $\phi$ may capture the different objectives of the encoder and the decoder. We may also consider multiple cost functions $(\phi_1, \phi_2, \dots, \phi_K)$. For example, we consider a distortion function $d: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$, a channel input cost function $c: \mathcal{X} \to \mathbb{R}$. Note that the maximization of the payoff function $\pi: \mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V} \to \mathbb{R}$ of a repeated game as in Gossner et al. (2006), corresponds to the minimization of the cost function $-\pi$. Given a code $(\sigma, \tau) \in \mathcal{C}(n)$, we define the associated n-stage cost.
**Definition 15** The n-stage cost $\phi^n(c)$ of the code $(\sigma, \tau) \in \mathcal{C}(n)$ is defined by

$$ \phi^n(c) = \mathbb{E} \left[ \frac{1}{n} \cdot \sum_{t=1}^{n} \phi(U_t, X_t, Y_t, V_t) \right]. \qquad (IV.25) $$

A cost value $\phi \in \mathbb{R}$ is achievable if for all $\varepsilon > 0$, there exists a $\bar{n} \in \mathbb{N}^*$, such that for all $n \ge \bar{n}$, there exists a code $c \in \mathcal{C}(n)$ such that

$$ \left| \phi - \mathbb{E} \left[ \frac{1}{n} \cdot \sum_{t=1}^{n} \phi(U_t, X_t, Y_t, V_t) \right] \right| \le \varepsilon. \qquad (IV.26) $$

We denote by $\Phi$ the set of achievable cost values.

**Theorem 8** We have

$$ \Phi = \left\{ \phi \in \mathbb{R}, \exists Q_{UXYV} \in \mathcal{A}, \mathbb{E}[\phi(U, X, Y, V)] = \phi \right\}. \qquad (IV.27) $$

Moreover, the optimization problem

$$ \min_{Q_{UXYV} \in \mathcal{A}} \mathbb{E}[\phi(U, X, Y, V)], \qquad (IV.28) $$

is a convex optimization problem.

The proof of Theorem 8 is stated in (Le Treust, 2017, [J6]). In Sec. IV.2.e, we study the coordination game of Gossner et al. (2006) and we investigate the trade-off between the source distortion $d: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$, and the channel input cost function $c: \mathcal{X} \to \mathbb{R}$.

## IV.2.d Example #1: coordination game of Gossner et al. (2006)

We consider the binary sets of symbols $\mathcal{U} = \mathcal{X} = \mathcal{Y} = \mathcal{V} = \{0, 1\}$, a binary information source $\mathcal{P}_U = (p, 1-p)$, with $p \in [0, 1]$ and a binary symmetric channel $\mathcal{T}_{Y|X} = (1-\varepsilon)1\{Y=X\} + \varepsilon 1\{Y \neq X\}$, with cross-over probability parameter $\varepsilon \in [0, 1]$, as depicted in Fig. IV.2.

<figure><img src="image_16.png" /><figcaption>Figure IV.2 – Binary information source $\mathcal{P}_U$ and binary symmetric channel $\mathcal{T}_{Y|X}$.</figcaption></figure>

The encoder and the decoder seek to coordinate their actions $X$ and $V$ with the information source $U$, in order to maximize the utility function $\pi: \mathcal{U} \times \mathcal{X} \times \mathcal{V} \to \mathbb{R}$ defined by Fig. IV.3.

<figure><img src="image_17.png" /><figcaption>Figure IV.3 – Utility function $\pi: \mathcal{U} \times \mathcal{X} \times \mathcal{V} \to \mathbb{R}$ of Gossner et al. (2006).</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Figure IV.4 – The optimal distribution for $\pi$, depending on $\gamma \in [0, 1]$.</figcaption></figure>

Since the decoder is strictly causal, it is clear from Gossner et al. (2006), that the distribution $P_U 1\{X = V = U\}$ which maximizes $E[\pi(U, X, V)]$ is not achievable. We suppose that the source parameter is $p = \frac{1}{2}$. By symmetry, the optimal achievable distribution $Q_{XV|U}$ is of the form of Fig. IV.3 which depends on some parameter $\gamma \in [0, 1]$. We consider lower and upper bounds on the information constraint (IV.13) that do not involve an auxiliary random variable $W_1$.

**Proposition 5** For all $Q_{XV|U} \in \Delta(\mathcal{X} \times \mathcal{V})^{|U|}$, we have

$$I(X;Y|V) - I(U;V,X) \le \max_{\substack{\tilde{\mathcal{Q}}_{W_1|UVXV}, \\ |W_1| \le |U \times X \times V|+1}} \left( I(W_1;Y|V) - I(U;V,W_1) \right) \le I(X;Y|U,V) - I(U;V). \quad (IV.29)$$

The difference between the upper bound and the lower bound in (IV.29) is equal to $I(U;X|V,Y)$. When the channel is not noisy $T_{Y|X} = 1\{Y = X\}$, the two bounds coincide since $I(U;X|V,Y) = 0$, and correspond to the information constraint $H(X|V) - I(U;V,X) \ge 0$ of Gossner et al. (2006) and Cuff and Zhao (2011).

**Proposition 6** For a distribution $Q_{XV|U} \in \Delta(\mathcal{X} \times \mathcal{V})^{|U|}$ of the form of Fig. IV.4 with $\gamma \in [0, 1]$, we have

$$I(X;Y|V) - I(U;V,X) = h_b(\gamma) + (1-\gamma) \cdot \log_2(3) - 1 - h_b(\varepsilon) - h_b\left(\frac{2}{3}(1-\gamma)\right) + h_b\left(\frac{2}{3}(1-\gamma) + \varepsilon \cdot \frac{4\gamma-1}{3}\right), \quad (IV.30)$$

$$I(X;Y|U,V) - I(U;V) = h_b(\gamma) + (1-\gamma) \cdot \log_2(3) - 1 - h_b(\varepsilon) + \frac{2\gamma+1}{3} \left( h_b\left((1-\varepsilon) \cdot \frac{3\gamma}{2\gamma+1} + \varepsilon \cdot \frac{1-\gamma}{2\gamma+1}\right) - h_b\left(\frac{3\gamma}{2\gamma+1}\right) \right). \quad (IV.31)$$

**Remark 3** Note that when $\varepsilon = 0$, the information constraints (IV.30) and (IV.31) reduce to the one stated in Gossner et al. (2006) and Cuff and Zhao (2011):

$$H(X|V) - I(U;V,X) = h_b(\gamma) + (1-\gamma) \cdot \log_2(3) - 1. \quad (IV.32)$$

Fig. IV.5 and IV.6 represent the lower and the upper bounds of equations (IV.30) and (IV.31), depending on $\gamma \in [0, 1]$, for different values of $\varepsilon \in [0, 1]$. The maximum of the information constraint is achieved by parameter $\gamma = 0.25$, that corresponds to the uniform probability distribution over the symbols $U \times X \times V$. The maximum of the cost is achieved by a distribution $Q_{XV|U}^*$ of the form of Fig. IV.4 with parameter $\gamma^* \in [0, 1]$ such that $\Psi(Q_{XV|U}^*) = 0$.

* If the channel is perfect i.e., $\varepsilon = 0$, the optimal solution corresponds to the one stated in Gossner et al. (2006) where the optimal distribution $Q_{XV|U}^*$ has parameter $\gamma^* \approx 0.81$ which is the solution of $h_b(\gamma) + (1-\gamma) \cdot \log_2(3) = 1$.
<figure><img src="image_19.png" /><figcaption>Figure IV.5 – Equations (IV.30) and (IV.31) as functions of $\gamma \in [0, 1]$ for $\varepsilon \in \{0, 0.25, 0.5\}$.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure IV.6 – Parameter $\gamma^* \in [0, 1]$ solution to $\Psi(Q_{X|U}^*) = 0$, depending on $\varepsilon \in [0, 0.5]$.</figcaption></figure>

* If the channel parameter is $\varepsilon = 0.5$, then the channel outputs are statistically independent of the channel inputs. The optimal utility is obtained when $U$, $X$ and $V$ are uniformly distributed. In that case, no information is transmitted.

* If the channel parameter is $\varepsilon = 0.25$, the optimal cost belongs to the interval $[0.54, 0.575]$. Even if the channel is noisy, the symbols of the encoder, the decoder and the source are perfectly coordinated more than half of the time.

## IV.2.e Example #2: Hamming distortion and channel cost

We investigate the relationship between the result stated in Theorem 6 for empirical coordination and the separation result of Shannon (1959) for the joint source-channel coding problem, see also (El Gamal and Kim, 2011, pp. 47, 57 and 66). We consider a distortion function $d: \mathcal{U} \times \mathcal{V} \to \mathbb{R}$ and a cost function $c: \mathcal{X} \to \mathbb{R}$.
**Definition 16** The pair of distortion-cost ($D^*, C^*$) is achievable if

$$ \lim_{n \to +\infty} \min_{(\sigma, \tau) \in \mathcal{C}(n)} \left( \left| \mathbb{E} \left[ \frac{1}{n} \sum_{t=1}^{n} d(U_t, V_t) \right] - D^* \right| + \left| \mathbb{E} \left[ \frac{1}{n} \sum_{t=1}^{n} c(X_t) \right] - C^* \right| \right) = 0. \quad (\text{IV.33}) $$

Without loss of generality, we consider exact distortion and cost rather than upper bounds on the distortion $\mathbb{E}[\frac{1}{n} \sum_{t=1}^{n} d(U_t, V_t)] \le D^* + \varepsilon$, and cost $\mathbb{E}[\frac{1}{n} \sum_{t=1}^{n} c(X_t)] \le C^* + \varepsilon$, as in (El Gamal and Kim, 2011, pp. 47 and 57). Theorem 6 provides a characterization of the achievable pairs of distortion-cost ($D^*, C^*$).

**Corollary 3** The following assertions are equivalent:

$$ 1. \quad \text{The pair of distortion-cost } (D^*, C^*) \text{ is achievable,} \qquad (\text{IV.34}) $$

$$ 2. \quad \exists Q_{UXYV} \in \mathcal{A}, \quad \mathbb{E}_Q [d(U, V)] = D^*, \quad \mathbb{E}_Q [c(X)] = C^*, \qquad (\text{IV.35}) $$

$$ 3. \quad \max_{\mathbb{Q}_{X}} I(X; Y) - \min_{\mathbb{Q}_{V|U}} I(U; V) \ge 0. \qquad (\text{IV.36}) $$

**Remark 4** Unlike in (El Gamal and Kim, 2011, pp. 43, Remark 3.5), Corollary 3 establishes that the pair of distortion-cost ($D^*, C^*$) is achievable when equation (IV.36) is also equal to zero. More details are provided in (Le Treust, 2017, [J6]).

*Proof.* [Corollary 3] The equivalence between 1. and 2. follows from Theorem 8. We prove the equivalence between 2. and 3. We consider a distribution $Q_{UXYV} \in \mathcal{A}$ that satisfy (IV.35) and we define the product of the marginal distributions $\tilde{Q}_{UXYV} = Q_{UV}Q_{XY}$. Then, $\mathbb{E}_{\tilde{Q}}[d(U, V)] = \mathbb{E}_{Q}[d(U, V)] = D^*$ and $\mathbb{E}_{\hat{Q}}[c(X)] = \mathbb{E}_{Q}[c(X)] = C^*$. Moreover,

$$ 0 \le \max_{\substack{\tilde{Q}_{W_1|U} \times V, \\ |W_1| \le |U| \times X \times V| + 1}} (I_Q(W_1; Y|V) - I_Q(U; V, W_1)) \le I_Q(X; Y) - I_Q(U; V) = I_{\hat{Q}}(X; Y) - I_{\hat{Q}}(U; V). \qquad (\text{IV.37}) $$

Therefore, (IV.36) is satisfied.

Now we consider the distributions $Q_X$ and $Q_{V|U}$ that achieve respectively the maximum and the minimum in (IV.36). By Corollary 2, we have $\mathcal{P}_U Q_{V|U} Q_X T_{Y|X} \in \mathcal{A} \cap \Delta(U \times V) \times \Delta(U \times V) \subset \mathcal{A}$. Moreover, $\mathbb{E}_Q [d(U, V)] = D^*$ and $\mathbb{E}_Q [c(X)] = C^*$, which imply (IV.35). □

**Example 2 (Trade-off distortion-cost)** We consider the coordination problem of Fig. IV.2 with $p \in [0, 1]$, $\varepsilon \in [0, 1]$ and the distortion function is $d(u, v) = \mathbb{1}\{u \ne v\}$ and cost function is $c(x) = \mathbb{1}\{x=0\}$. We consider the distributions $Q_X = (\alpha, 1-\alpha)$, with $\alpha \in [0, 1]$ and $Q_{V|U} = (1-\beta)\mathbb{1}\{V=U\} + \beta\mathbb{1}\{V \ne U\}$, with $\beta \in [0, 1]$. The expected distortion and the expected cost are given by:

$$ \mathbb{E}[d(U, V)] = p \cdot \beta + (1-p) \cdot \beta = \beta, \qquad (\text{IV.38}) $$

$$ \mathbb{E}[c(X)] = \sum_{x} Q_{X}(x) \cdot \mathbb{1}\{x=0\} = \alpha. \qquad (\text{IV.39}) $$

Note that a target pair of distortion-cost ($D^*, C^*$) induces a unique pair of parameters $(\beta, \alpha)$. The information constraint (IV.36) of Corollary 3 is equal to:

$$ I(X; Y) - I(U; V) = h_b(\alpha \cdot \varepsilon + (1-\alpha) \cdot (1-\varepsilon)) + h_b(\beta) - h_b(\varepsilon) - h_b(\beta \cdot p + (1-\beta) \cdot (1-p)). \qquad (\text{IV.40}) $$

Fig. IV.7 represents the regions of achievable pairs of exact distortion-cost, for parameters $(\varepsilon, p) \in \{(0.05, 0.5); (0.25, 0.25); (0.25, 0.5)\}$. This illustrates the trade-off between minimal source distortion and minimal channel cost. The boundary of the three regions corresponds to the pairs of distortion and cost ($D^*, C^*$), that satisfy the equality $I(X; Y) = I(U; V)$.
<figure><img src="image_21.png" /><figcaption>Figure IV.7 – The set of achievable Distortion-Cost ($D^*, C^*$) depending on source and channel parameters ($\epsilon, p) \in \{(0.05, 0.5); (0.25, 0.25); (0.25, 0.5)\}$.</figcaption></figure>

## IV.3 General decoding functions

We investigate the empirical coordination problem for general decoding functions.

### IV.3.a Causal decoding with source feedforward

We consider the setting depicted in Fig. IV.8 in which the decoder observes causally the channel output symbols, i.e. the past and the current symbols $Y^t = (Y^{t-1}, Y_t)$, and we consider four scenarios of source feedforward, i.e. the decoder observes the source symbols either strictly causally $U^{t-1}$, or causally $U^t$, or non-causally $U^n$, or does not observe any source symbol $\emptyset$.

<figure><img src="image_22.png" /><figcaption>Figure IV.8 – Causal channel output $Y^t$ and four different scenarios of source feedforward $\{\emptyset, U^{t-1}, U^t, U^n\}$.</figcaption></figure>

**Definition 17** Given $n \in \mathbb{N}^*$, we define the non-causal encoder $\sigma$ and four different decoding functions $\tau_t^c, \tau_t^{cs}, \tau_t^{cc}, \tau_t^{cn}$, for $t \in \{1, \dots, n\}$.

$$ \sigma: \mathcal{U}^n \to \mathcal{X}^n, \qquad (\text{IV.41}) $$

$$ \tau_t^c: \mathcal{Y}^t \to \mathcal{V}, \quad t \in \{1, \dots, n\}, \qquad (\text{IV.42}) $$

$$ \tau_t^{cs}: \mathcal{Y}^t \times \mathcal{U}^{t-1} \to \mathcal{V}, \quad t \in \{1, \dots, n\}, \qquad (\text{IV.43}) $$

$$ \tau_t^{cc}: \mathcal{Y}^t \times \mathcal{U}^t \to \mathcal{V}, \quad t \in \{1, \dots, n\}, \qquad (\text{IV.44}) $$

$$ \tau_t^{cn}: \mathcal{Y}^t \times \mathcal{U}^n \to \mathcal{V}, \quad t \in \{1, \dots, n\}. \qquad (\text{IV.45}) $$

We denote by $\mathcal{C}^{cs}(n)$ (resp. $\mathcal{C}^{cc}(n)$, $\mathcal{C}^{cn}(n)$, $\mathcal{C}^c(n)$) the set of n-length code with causal channel output and strictly causal (resp. causal, non-causal, absent) source feedforward.

The sets of achievable target probability distributions $\mathcal{A}^{cs} \subset \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ (resp. $\mathcal{A}^{cc}$, $\mathcal{A}^{cn}$, $\mathcal{A}^c$) are defined similarly as in Definition 14, with respect to the set of code $\mathcal{C}^{cs}(n)$ (resp. $\mathcal{C}^{cc}(n)$, $\mathcal{C}^{cn}(n)$, $\mathcal{C}^c(n)$). By definition, we have $\mathcal{A}^c \subset \mathcal{A}^{cs} \subset \mathcal{A}^{cc} \subset \mathcal{A}^{cn} \subset \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$.
When considering a code $(\sigma, \tau) \in \mathcal{C}^{\text{cn}}(n)$, both encoder and decoder have non-causal observation of the source sequence $U^n$. Therefore, the decoder can replicate the encoding function and select a sequence $V^n$ that is empirically correlated with $(U^n, X^n, Y^n)$. Thus, the set of achievable target probability distributions is given by

$$ \mathcal{A}^{\text{cn}} = \{ \mathcal{P}_U \mathcal{Q}_{X|U} \mathcal{T}_{Y|X} \mathcal{Q}_{V|UX} \}. \qquad (\text{IV.46}) $$

In the following, we characterize the sets $\mathcal{A}^{\text{cs}}$, $\mathcal{A}^{\text{cc}}$ and $\mathcal{A}^{\text{c}}$, that are subsets of $\mathcal{A}^{\text{cn}}$. The following results are stated in (Le Treust, 2015b, [IC14], Sec. IV), (Le Treust, 2017, [J6], Theorem 4), the proof is also stated in (Le Treust, 2015, [W1]).

**Theorem 9** 1. A distribution $Q_{UXYV} \in \mathcal{A}^{\text{cc}}$ if and only if $Q_{UXYV} = \mathcal{P}_U Q_{X|U} \mathcal{T}_{Y|X} Q_{V|UXY}$ and there exists an auxiliary random variable $W_2 \in W_2$ where $|W_2| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}| + 1$ and a joint distribution

$$ \tilde{Q}_{UXW_2YV} = \mathcal{P}_U Q_{X|U} \tilde{Q}_{W_2|UX} \mathcal{T}_{Y|X} \tilde{Q}_{V|UYW_2}, \qquad (\text{IV.47}) $$

that satisfies

$$ Q_{V|UXY} = \sum_{w_2} \tilde{Q}_{W_2|UX}(w_2|\cdot, \cdot) \tilde{Q}_{V|UYW_2}(\cdot, \cdot, w_2), \qquad (\text{IV.48}) $$

$$ I(X; Y|U, W_2) - I(W_2; U) \ge 0. \qquad (\text{IV.49}) $$

2. A distribution $Q_{UXYV} \in \mathcal{A}^{\text{cs}}$ if and only if $Q_{UXYV} = \mathcal{P}_U Q_{X|U} \mathcal{T}_{Y|X} Q_{V|UXY}$ and there exists an auxiliary random variable $W_2 \in W_2$ where $|W_2| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}| + 1$ and a joint distribution

$$ \tilde{Q}_{UXW_2YV} = \mathcal{P}_U Q_{X|U} \tilde{Q}_{W_2|UX} \mathcal{T}_{Y|X} \tilde{Q}_{V|YW_2}, \qquad (\text{IV.50}) $$

that satisfies

$$ Q_{V|UXY} = \sum_{w_2} \tilde{Q}_{W_2|UX}(w_2|\cdot, \cdot) \tilde{Q}_{V|YW_2}(\cdot, \cdot, w_2), \qquad (\text{IV.51}) $$

$$ I(X; Y|U, W_2) - I(W_2; U) \ge 0. \qquad (\text{IV.52}) $$

3. A distribution $Q_{UXYV} \in \mathcal{A}^{\text{c}}$ if and only if $Q_{UXYV} = \mathcal{P}_U Q_{X|U} \mathcal{T}_{Y|X} Q_{V|UXY}$ and there exists a pair of auxiliary random variables $(W_1, W_2) \in W_1 \times W_2$ where $\max(|W_1|, |W_2|) \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}| + 1$ and a joint distribution

$$ \tilde{Q}_{UXW_1W_2YV} = \mathcal{P}_U Q_{X|U} \tilde{Q}_{W_1W_2|UX} \mathcal{T}_{Y|X} \tilde{Q}_{V|YW_2}, \qquad (\text{IV.53}) $$

that satisfies

$$ Q_{V|UXY} = \sum_{(w_1, w_2)} \tilde{Q}_{W_1W_2|UX}(w_1, w_2|\cdot, \cdot) \tilde{Q}_{V|YW_2}(\cdot, \cdot, w_2), \qquad (\text{IV.54}) $$

$$ I(W_1; Y|W_2) - I(W_1, W_2; U) \ge 0. \qquad (\text{IV.55}) $$

The only difference between the sets $\mathcal{A}^{\text{cc}}$ and $\mathcal{A}^{\text{sc}}$ comes from the conditional distributions $\tilde{Q}_{V|UYW_2}$ and $\tilde{Q}_{V|YW_2}$. This is due to the observation of the current symbol $U_t$ in the decoding functions $\tau_t^{\text{cc}}$, which is not the case for the decoding functions $\tau_t^{\text{cs}}$, for $t \in \{1, \dots, n\}$. When the decoder has no source feedforward, another auxiliary random variable $W_1 \in W_1$ is needed in order to tune the state-dependent channel, as in Gel'fand and Pinsker (1980).
IV.3.b Strictly causal decoding with source feedforward

For the seek of completeness, we characterize the set of achievable distributions for strictly causal decoding with source feedforward, similarly as in Sec. IV.3.a. We consider the setting depicted in Fig. IV.9 in which the decoder observes strictly causally the channel output symbols $Y^{t-1}$, and we consider four scenarios of source feedforward, i.e. the decoder observes the source symbols either strictly causally $U^{t-1}$, or causally $U^t$, or non-causally $U^n$, or does not observes any source symbol $\emptyset$.

**Definition 18** Given $n \in \mathbb{N}^*$, we define the non-causal encoder $\sigma$ and four different decoding functions $\tau_t^s, \tau_t^{ss}, \tau_t^{sc}, \tau_t^{sn}$, for $t \in \{1, \dots, n\}$.

$$ \sigma: \mathcal{U}^n \to \mathcal{X}^n, \qquad (IV.56) $$

$$ \tau_t^s: \mathcal{Y}^{t-1} \to \mathcal{V}, \quad t \in \{1, \dots, n\}, \qquad (IV.57) $$

$$ \tau_t^{ss}: \mathcal{Y}^{t-1} \times \mathcal{U}^{t-1} \to \mathcal{V}, \quad t \in \{1, \dots, n\}, \qquad (IV.58) $$

$$ \tau_t^{sc}: \mathcal{Y}^{t-1} \times \mathcal{U}^t \to \mathcal{V}, \quad t \in \{1, \dots, n\}, \qquad (IV.59) $$

$$ \tau_t^{sn}: \mathcal{Y}^{t-1} \times \mathcal{U}^n \to \mathcal{V}, \quad t \in \{1, \dots, n\}. \qquad (IV.60) $$

We denote by $C^{sc}(n)$ (resp. $C^{ss}(n)$, $C^{sn}(n)$, $C^s(n)$) the set of n-length code with strictly causal channel output and causal (resp. strictly causal, non-causal, absent) source feedforward.

<figure><img src="image_23.png" /><figcaption>Figure IV.9 – Strictly causal channel output $Y^{t-1}$ and four different scenarios of source feedforward $\{\emptyset, U^{t-1}, U^t, U^n\}$.</figcaption></figure>

The sets of achievable target probability distributions $\mathcal{A}^{sc} \subset \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ (resp. $\mathcal{A}^{ss}$, $\mathcal{A}^{sn}$, $\mathcal{A}^s$) are defined similarly as in Definition 14, with respect to the set of code $C^{sc}(n)$ (resp. $C^{ss}(n)$, $C^{sn}(n)$, $C^s(n)$). By definition, we have $\mathcal{A}^s \subset \mathcal{A}^{ss} \subset \mathcal{A}^{sc} \subset \mathcal{A}^{sn} \subset \Delta(\mathcal{U} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$.

When considering a code $(\sigma, \tau) \in C^{sn}(n)$, both encoder and decoder have non-causal observation of the source sequence $U^n$. Therefore, the decoder can replicate the encoding function and therefore select a sequence $V^n$ that is empirically correlated with $(U^n, X^n)$. For all $t \in \{1, \dots, n\}$, the decoder must return $V_t$ before it observes $Y_t$. Thus, we have the Markov chain property $Y \leftarrow X \leftarrow (U, V)$ and the set of achievable distributions is given by

$$ \mathcal{A}^{sn} = \{ \mathcal{P}_U \mathcal{Q}_{XV|U} \mathcal{T}_{Y|X} \}. \qquad (IV.61) $$

In the following, we characterize the sets $\mathcal{A}^s$, $\mathcal{A}^{ss}$ and $\mathcal{A}^{sc}$.

**Theorem 10** 1. A distribution $\mathcal{Q}_{UXYV} \in \mathcal{A}^{sc}$ if and only if $\mathcal{Q}_{UXYV} = \mathcal{P}_U \mathcal{Q}_{XV|U} \mathcal{T}_{Y|X}$ and there exists an auxiliary random variable $W_2 \in \mathcal{W}_2$ where $|\mathcal{W}_2| \le |\mathcal{U} \times \mathcal{X} \times \mathcal{V}| + 1$ and a joint distribution

$$ \tilde{\mathcal{Q}}_{UXW_2YV} = \mathcal{P}_U \mathcal{Q}_{X|U} \tilde{\mathcal{Q}}_{W_2|UX} \tilde{\mathcal{Q}}_{V|UW_2} \mathcal{T}_{Y|X}, \qquad (IV.62) $$

that satisfies

$$ \mathcal{Q}_{V|UX} = \sum_{w_2} \tilde{\mathcal{Q}}_{W_2|UX}(w_2|\cdot, \cdot) \tilde{\mathcal{Q}}_{V|UW_2}(\cdot|\cdot, w_2), \qquad (IV.63) $$

$$ I(X; Y|U, W_2) - I(W_2; U) \ge 0. \qquad (IV.64) $$
2. A distribution $Q_{UXYV} \in \mathcal{A}^{ss}$ if and only if $Q_{UXYV} = \mathcal{P}_U Q_{XV|U} \mathcal{T}_{Y|X}$ and

$$I(X; Y|U, V) - I(V; U) \geq 0. \qquad (IV.65)$$

3. A distribution $Q_{UXYV} \in \mathcal{A}^s$ if and only if $Q_{UXYV} = \mathcal{P}_U Q_{XV|U} \mathcal{T}_{Y|X}$ and there exists an auxiliary random variables $W_1 \in W_1$ where $|W_1| \le |U \times X \times V| + 1$ and a joint distribution

$$\tilde{Q}_{UXW_1YV} = \mathcal{P}_U Q_{XV|U} \tilde{Q}_{W_1|UXV} \mathcal{T}_{Y|X}, \qquad (IV.66)$$

that satisfies

$$I(W_1; Y|V) - I(W_1, V; U) \geq 0. \qquad (IV.67)$$

The Theorem 10 (2.) was stated for achievable distributions in (Le Treust, 2017, [J6], Corollary 3) and for implementable distributions in (Gossner et al., 2006, Eq. (11)), and (Larrousse et al., 2018, Theorem 4 and Corollary 12). The Theorem 10 (3.) corresponds to the Theorem 7 in Sec. IV.2.

**Remark 5** An inner bound to the set $\mathcal{A}^{sc}$ was stated in (Larrousse et al., 2015a, Theorem 2) with a pair of auxiliary random variables $(W_1, W_2)$. When using our notations for $(S_0, S_1, S_2, U, V, X_1, X_2, Y_1, Y_2) = (\emptyset, U, U, W_2, W_1, X, V, Y, \emptyset)$, we obtain the decomposition of the distribution

$$\tilde{Q}_{UXW_1W_2VY} = \mathcal{P}_U Q_{X|U} \tilde{Q}_{W_1W_2|UX} \tilde{Q}_{V|UW_2} \mathcal{T}_{Y|X}, \qquad (IV.68)$$

and the information constraint

$$I(W_1; Y|W_2) - I(W_1, W_2; U) \geq 0. \qquad (IV.69)$$

However, the decoder may exploit the causal observation of the source which may lead to a weaker information constraint

$$I(W_1; Y|W_2) - I(W_1, W_2; U) \le I(W_1; U, Y|W_2) - I(W_1, W_2; U) = I(W_1; Y|W_2, U) - I(W_2; U), \quad (IV.70)$$

for which it is optimal to take $W_1 = X$.

## IV.4 State-dependent source and state-dependent channel

In this section, we investigate the empirical coordination problem for state-dependent source and channels. The state-dependent source generates a triple of sequences $(U^n, S^n, Z^n) \in \mathcal{U}^n \times \mathcal{S}^n \times \mathcal{Z}^n$, drawn i.i.d. according to $\mathcal{P}_{USZ} \in \Delta(\mathcal{U} \times \mathcal{S} \times \mathcal{Z})$, as in (IV.71). We denote by $U^n \in \mathcal{U}^n$ the sequence of source symbols, $S^n \in \mathcal{S}^n$ the sequence of channel states symbols and $Z^n \in \mathcal{Z}^n$ the sequence of decoder state information symbols. The state-dependent channel generates an output sequence $Y^n \in \mathcal{Y}^n$ drawn i.i.d. according to $\mathcal{T}_{Y|XS} \in \Delta(\mathcal{Y})^{|\mathcal{X} \times \mathcal{S}|}$, as in (IV.72).

$$\Pr((U^n, S^n, Z^n) = (u^n, s^n, z^n)) = \prod_{t=1}^{n} \mathcal{P}_{USZ}(u_t, s_t, z_t), \quad \forall (u^n, s^n, z^n) \in \mathcal{U}^n \times \mathcal{S}^n \times \mathcal{Z}^n, \qquad (IV.71)$$

$$\Pr(Y^n = y^n | (X^n, S^n) = (x^n, s^n)) = \prod_{t=1}^{n} \mathcal{T}_{Y|XS}(y_t|x_t, s_t), \quad \forall (x^n, s^n, y^n) \in \mathcal{X}^n \times \mathcal{S}^n \times \mathcal{Y}^n. \qquad (IV.72)$$

In this section, we consider strictly causal, causal and non-causal encoding and decoding functions.

### IV.4.a Non-causal encoder and non-causal decoder

We consider the setting depicted in Fig. IV.10.
**Definition 19** Given $n \in \mathbb{N}^*$, we define the n-length code with non-causal encoder and non-causal decoder by a pair $(\sigma, \tau)$ of deterministic functions

$$ \sigma: \mathcal{U}^n \times \mathcal{S}^n \to \mathcal{X}^n, \qquad (IV.73) $$

$$ \tau: \mathcal{Y}^n \times \mathcal{Z}^n \to \mathcal{V}^n. \qquad (IV.74) $$

We denote by $\mathcal{C}^{\text{nc}}(n)$ the set of n-length code with non-causal encoder and non-causal decoder.

The code $(\sigma, \tau) \in \mathcal{C}^{\text{nc}}(n)$ induces a probability distribution $\mathcal{P}_{U^n S^n Z^n X^n Y^n V^n}^c$ defined, for all $(u^n, s^n, z^n, x^n, y^n, v^n)$, by

$$ \mathcal{P}_{U^n S^n Z^n X^n Y^n V^n}^c (u^n, s^n, z^n, x^n, y^n, v^n) = \left( \prod_{t=1}^n \mathcal{P}_{USZ}(u_t, s_t, z_t) \right) \mathbf{1}\{x^n = \sigma(u^n, s^n)\} \left( \prod_{t=1}^n \mathcal{T}_{Y|XS}(y_t|x_t, s_t) \right) \mathbf{1}\{v^n = \sigma(y^n, z^n)\}. \qquad (IV.75) $$

We evaluate the empirical frequencies of symbols induced by the code.

<figure><img src="image_24.png" /><figcaption>Figure IV.10 – Non-Causal Encoding function $f: \mathcal{U}^n \times \mathcal{S}^n \to \mathcal{X}^n$ and Decoding function $g: \mathcal{Y}^n \times \mathcal{Z}^n \to \mathcal{V}^n$.</figcaption></figure>

We refer to the Definition 13 for the random empirical distribution $Q_{USZXYV}^n$. We define the notion of achievable distribution similarly to Def. 14.

**Definition 20** A target probability distribution $Q_{USZXYV} \in \Delta(\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ is achievable if there exists a sequence of codes $(\sigma, \tau) \in \mathcal{C}^{\text{nc}}(n)$ such that the sequence of empirical distributions $(Q_{USZXYV}^n)_{n \in \mathbb{N}^*}$ converges in probability to $Q_{USZXYV}$, i.e.

$$ \forall \delta > 0, \quad \lim_{n \to +\infty} \min_{(\sigma, \tau) \in \mathcal{C}^{\text{nc}}(n)} \Pr \left( \left\| Q_{USZXYV}^n - Q_{USZXYV} \right\|_1 > \delta \right) = 0. \qquad (IV.76) $$

We denote by $\mathcal{A}^{\text{nc}} \subset \Delta(\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ the set of achievable distributions.

We aim at characterizing the asymptotic behavior of the empirical distribution $Q_{USZXYV}^n$ induced by sequences of codes.

**Theorem 11** 1. A target probability distribution $Q_{USZXYV} \in \Delta(\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V})$ is achievable if

$$ Q_{USZXYV} = \mathcal{P}_{USZ} \mathcal{Q}_{X|US} \mathcal{T}_{Y|XS} \mathcal{Q}_{V|USZXY}, \qquad (IV.77) $$

and there exist an auxiliary random variable $W \in \mathcal{W}$ with $|W| \le |\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{V}| + 2$ such that

$$ \max_{\substack{\tilde{Q}_{USZXYV} \\ \in \mathcal{Q}_{V|USZXY}^{\text{nc}}}} \left( I(W; Y, Z) - I(W; U, S) \right) \ge 0, \qquad (IV.78) $$

where for every $Q_{V|USZXY}$,

$$ \begin{aligned} \mathcal{Q}^{\text{nc}}(Q_{V|USZXY}) &= \left\{ \tilde{Q}_{USZWXYV} = \mathcal{P}_{USZ} \mathcal{Q}_{X|US} \tilde{Q}_{W|USX} \mathcal{T}_{Y|XS} \tilde{Q}_{V|YZW}, \right. \\ & \qquad \left. Q_{V|USZXY} = \sum_{w \in \mathcal{W}} \tilde{Q}_{W|USX}(w|\cdot, \cdot, \cdot) \tilde{Q}_{V|YZW}(\cdot|\cdot, \cdot, w) \right\}. \end{aligned} \qquad (IV.79) $$
2. If a target probability distribution $Q_{USZXYV} \in \Delta(U \times S \times Z \times X \times Y \times V)$ is achievable, then

$$Q_{USZXYV} = P_{USZ}Q_{X|US}T_{Y|XS}Q_{V|USZXY}, \qquad (IV.80)$$

and

$$\max_{\tilde{Q}_{USZWXYV} \in \mathbb{Q}^{\text{nc}}(\tilde{Q}_{V|USZXY})} \left( \min (I(X, U, S; Y, Z), I(X, S; Y) + I(U; Z)) - I(W; U, S) \right) \geq 0. \qquad (IV.81)$$

The Theorem 11 (1.) is stated in (Le Treust, 2015c, [IC13], Theorem III.1) and in (Le Treust, 2015, [W1]). The Theorem 11 (2.) is stated in (Cervia et al., 2020, [J9], Theorem 2). When there is no state information $S = Z = \emptyset$, Theorem 11 (1.) boils down to (Cuff and Schieler, 2011, Theorem 1). Any distribution $\tilde{Q}_{USZWXYV} \in \mathbb{Q}^{\text{nc}}(Q_{V|USZXY})$ satisfies the Markov chains

$$Y \leftarrow (X, S) \leftarrow (U, Z, W), \qquad (IV.82)$$

$$Z \leftarrow (U, S) \leftarrow (X, Y, W), \qquad (IV.83)$$

$$V \leftarrow (Y, Z, W) \leftarrow (U, S, X). \qquad (IV.84)$$

**Remark 6** The mutual informations in (IV.81) and (IV.81) are continuous over the set of probability distributions $\mathbb{Q}^{\text{nc}}(Q_{V|USZXY})$, for all $Q_{V|USZXY}$. Moreover, $\mathbb{Q}^{\text{nc}}(Q_{V|USZXY})$ is compact since $|W| < +\infty$. As mentioned in (Cuff, 2013, pp. 7083) and in (Wyner and Ziv, 1976, pp. 9), the supremum is a maximum in (IV.81) and (IV.81).

## Perfect Channel

We consider that the state-dependent channel is not noisy, i.e. $T_{Y|XS} = \mathbb{1}\{Y = X\}$ depicted in Fig. IV.11. We characterize the set of achievable distributions.

<figure><img src="image_25.png" /><figcaption>Figure IV.11 – The perfect channel is defined by $T_{Y|XS} = \mathbb{1}\{Y = X\}$ and the decoding is lossy.</figcaption></figure>

**Theorem 12** A target probability distribution $Q_{USZXV} \in \Delta(U \times S \times Z \times X \times V)$ is achievable if and only if

$$Q_{USZXYV} = P_{USZ}Q_{X|US}Q_{V|USZX}, \qquad (IV.85)$$

and there exist an auxiliary random variable $W_2 \in W_2$ with $|W_2| \le |U \times S \times Z \times X \times V| + 2$ such that

$$\max_{\tilde{Q}_{USZW_2XV} \in \mathbb{Q}^{\text{P}}(\tilde{Q}_{V|USZX})} \left( I(W_2; Z|X) + H(X) - I(X, W_2; U, S) \right) \geq 0, \qquad (IV.86)$$

where for every $Q_{V|USZX}$,

$$\mathbb{Q}^{\text{P}}(Q_{V|USZX}) = \left\{ \tilde{Q}_{USZW_2XV} = P_{USZ}Q_{X|US}\tilde{Q}_{W_2|USX}\tilde{Q}_{V|XZW_2}, \right. \\ \left. Q_{V|USZX} = \sum_{w_2 \in W_2} \tilde{Q}_{W_2|USX}(w_2|\cdot, \cdot, \cdot)\tilde{Q}_{V|XZW_2}(\cdot, \cdot, \cdot, w_2) \right\}. \qquad (IV.87)$$
This result is stated in (Le Treust, 2015c, [IC13], Theorem IV.1)and in (Le Treust, 2015, [W1]). Any distribution $\tilde{Q}_{USZW_2XV} \in Q^p(Q_{V|USZX})$ satisfies the Markov chains

$$ Z \leftarrow (U, S) \leftarrow (X, W), \qquad (IV.88) $$

$$ V \leftarrow (X, Z, W) \leftarrow (U, S). \qquad (IV.89) $$

**Remark 7** This result generalizes the coding theorem for state-dependent source of Wyner and Ziv (1976).

## Lossless reconstruction at the decoder

We restrict our attention to the case where the decoder must recover the source symbol, as depicted in Fig. IV.12. We characterize the set of achievable distributions $Q_{USZXYV}$ for which $Q_{V|USZXY} = \mathbb{1}\{V = U\}$.

<figure><img src="image_26.png" /><figcaption>Figure IV.12 – The decoder must recover the source symbol, i.e. $Q_{V|USZXY} = \mathbb{1}\{V = U\}$.</figcaption></figure>

**Theorem 13** A target probability distribution $Q_{USZXY} \mathbb{1}\{V = U\} \in \Delta(U \times S \times Z \times X \times Y \times V)$ is achievable if and only if

$$ Q_{USZXY} \mathbb{1}\{V = U\} = P_{USZ} Q_{X|US} T_{Y|XS} \mathbb{1}\{V = U\}, \qquad (IV.90) $$

and there exist an auxiliary random variable $W_1 \in W_1$ with $|W_1| \le |U \times S \times Z \times X \times V| + 2$ such that

$$ \max_{\tilde{Q}_{USZW_1XYV} \in Q^l} \left( I(U, W_1; Y, Z) - I(W_1; S|U) - H(U) \right) \ge 0, \qquad (IV.91) $$

where

$$ Q^l = \left\{ \tilde{Q}_{USZW_2XYV} = P_{USZ} Q_{X|US} \tilde{Q}_{W_1|USX} T_{Y|XS} \mathbb{1}\{V = U\} \right\}. \qquad (IV.92) $$

This result is stated in (Le Treust, 2015c, [IC13], Eq. (11)) and in (Le Treust, 2015, [W1]). Any distribution $\tilde{Q}_{USZW_1XYV} \in Q^l$ satisfies the Markov chains

$$ Y \leftarrow (X, S) \leftarrow (U, Z, W_1), \qquad (IV.93) $$

$$ Z \leftarrow (U, S) \leftarrow (X, Y, W_1). \qquad (IV.94) $$

Another formulation is stated in (Le Treust, 2014, [IC12]) with a more restrictive lossless decoding constraint: $P(\hat{U}^n \neq U^n) \to 0$.

**Remark 8** This result generalizes the coding theorem for state-dependent channel of Gel'fand and Pinsker (1980).
<figure><img src="image_27.png" /><figcaption>Figure IV.13 – The source random variables (U, Z, V) are independent of the channel random variables (X, S, Y).</figcaption></figure>

Separation between Source and Channel

We restrict our attention to the case where the source distribution satisfies $P_{USZ} = P_{UZ}P_S$ and we investigate the achievability of target distributions such that the random variables of the source $(U, Z, V)$ are independent of the random variables of the channel $(X, S, Y)$, as depicted in Fig. IV.13. We characterize the set of achievable distributions of the form $Q_{UZV}Q_{XSY}$.

**Theorem 14** A target probability distribution $Q_{UZV}Q_{XSY} \in \Delta(\mathcal{U} \times \mathcal{Z} \times \mathcal{V}) \times \Delta(\mathcal{X} \times \mathcal{S} \times \mathcal{Y})$ is achievable if and only if

$$Q_{UZV} = P_{UZ}Q_{V|UZ}, \quad Q_{XSY} = P_S Q_{X|S}T_{Y|XS}, \qquad (IV.95)$$

and there exist a pair of auxiliary random variables $(W_1, W_2) \in W_1 \times W_2$ with $|W_1| \le |\mathcal{U} \times \mathcal{Z} \times \mathcal{V}| + 2$ and $|W_2| \le |\mathcal{S} \times \mathcal{X} \times \mathcal{Y}| + 2$ such that

$$\max_{\tilde{Q}_{USZW_1W_2XYV} \in \tilde{Q}^s(Q_{V|UZ})} \left( I(W_1; Y) - I(W_1; S) + I(W_2; Z) - I(W_2; U) \right) \ge 0, \qquad (IV.96)$$

where for every $Q_{V|UZ}$,

$$\tilde{Q}^s(Q_{V|UZ}) = \left\{ \tilde{Q}_{USZW_1W_2XYV} = P_{UZ}\tilde{Q}_{W_2|U}\tilde{Q}_{V|ZW_2}P_SQ_{X|S}\tilde{Q}_{W_1|XS}T_{Y|XS}, \right. \\ \left. Q_{V|UZ} = \sum_{w_2 \in W_2} \tilde{Q}_{W_2|U}(w_2|\cdot)\tilde{Q}_{V|ZW_2}(\cdot|\cdot, w_2) \right\}. \qquad (IV.97)$$

This result is stated in (Le Treust, 2015c, [IC13], Theorem IV.2) and (Le Treust, 2015, [W1]). Any distribution $\tilde{Q}_{USZW_1W_2XYV} \in \tilde{Q}^s$ satisfies $(U, Z, W_2, V)$ is independent of $(S, X, W_1, Y)$ and the Markov chains

$$Z \leftarrow U \leftarrow W_2, \qquad (IV.98)$$

$$V \leftarrow (Z, W_2) \leftarrow U, \qquad (IV.99)$$

$$Y \leftarrow (X, S) \leftarrow W_1. \qquad (IV.100)$$

**Remark 9** This separation result was already stated in Merhav and Shamai (2003), given a distortion level and a channel cost.

IV.4.b Causal decoder and non-causal encoder

We consider the case where the decoder is causal, as depicted in Fig. IV.14.
**Definition 21** Given $n \in \mathbb{N}^*$, we define the n-length code with non-causal encoder and causal decoder by a pair $(\sigma, \tau)$ where $\tau = \{\tau_t\}_{t \in \{1, \dots, n\}}$) of deterministic functions

$$ \sigma: \mathcal{U}^n \times \mathcal{S}^n \to \mathcal{X}^n, \qquad (\text{IV.101}) $$

$$ \tau_t: \mathcal{Y}^t \times \mathcal{Z}^t \to \mathcal{V}, \quad \forall t \in \{1, \dots, n\}. \qquad (\text{IV.102}) $$

We denote by $\mathcal{C}^{\text{cd}}(n)$ the set of n-length code with non-causal encoder and causal decoder.

The code $(\sigma, \tau) \in \mathcal{C}^{\text{cd}}(n)$ induces a probability distribution $\mathcal{P}_{U^n S^n Z^n X^n Y^n V^n}^c$ defined, for all $(u^n, s^n, z^n, x^n, y^n, v^n)$, by

$$ \mathcal{P}_{U^n S^n Z^n X^n Y^n V^n}^c(u^n, s^n, z^n, x^n, y^n, v^n) = \left( \prod_{t=1}^n \mathcal{P}_{USZ}(u_t, s_t, z_t) \right) \mathbf{1}\{x^n = \sigma(u^n, s^n)\} \left( \prod_{t=1}^n \mathcal{T}_{Y|XS}(y_t|x_t, s_t) \right) \left( \prod_{t=1}^n \mathbf{1}\{v_t = \sigma_t(y^t, z^t)\} \right). \quad (\text{IV.103}) $$

We refer to the Definitions 13 and 14 for the random empirical distribution $Q_{USZXYV}^n$ and the notion of achievable distribution. We denote by $\mathcal{A}^{\text{cd}}$ the set of target distributions that are achievable by using a code $(\sigma, \tau) \in \mathcal{C}^{\text{cd}}(n)$ with non-causal encoder and causal decoder.

<figure><img src="image_28.png" /><figcaption>Figure IV.14 – The encoding function $\sigma$ is non-causal and the decoding function is causal $\tau_t$ for $t \in \{1, \dots, n\}$.</figcaption></figure>

**Theorem 15** A target probability distribution $Q_{USZXYV} \in \mathcal{A}^{\text{cd}}$ if and only if

$$ Q_{USZXYV} = \mathcal{P}_{USZ} Q_{X|US} \mathcal{T}_{Y|XS} Q_{V|USZXY}, \qquad (\text{IV.104}) $$

and there exist a pair of auxiliary random variables $(W_1, W_2) \in W_1 \times W_2$ with $\max(|W_1|, |W_2|) \le |U \times S \times Z \times X \times V| + 2$ such that

$$ \max_{\tilde{Q}_{USZW_1W_2XYV} \in \mathcal{Q}^{\text{cd}}(Q_V|USZXY)} \left( I(W_1; Y, Z|W_2) - I(W_1, W_2; U, S) \right) \ge 0, \qquad (\text{IV.105}) $$

where for every $Q_{V|USZXY}$,

$$ \mathcal{Q}^{\text{cd}}(Q_{V|USZXY}) = \left\{ \tilde{Q}_{USZW_1W_2XYV} = \mathcal{P}_{USZ} Q_{X|US} \tilde{Q}_{W_1W_2|USX} \mathcal{T}_{Y|XS} \tilde{Q}_{V|YZW_2}, \right. \\ \left. Q_{V|USZXY} = \sum_{w_2 \in W_2} \tilde{Q}_{W_2|USX}(w_2|\cdot, \cdot, \cdot) \tilde{Q}_{V|YZW_2}(\cdot|\cdot, \cdot, w) \right\}. \qquad (\text{IV.106}) $$

This result is stated in (Le Treust, 2015c, [IC13], Eq. (16)) and in (Le Treust, 2015, [W1]). Any distribution $\tilde{Q}_{USZW_1W_2XYV} \in \mathcal{Q}^{\text{cd}}$ satisfies the Markov chains

$$ Y \leftarrow (X, S) \leftarrow (U, Z, W_1, W_2), \qquad (\text{IV.107}) $$

$$ Z \leftarrow (U, S) \leftarrow (X, Y, W_1, W_2), \qquad (\text{IV.108}) $$

$$ V \leftarrow (Y, Z, W_2) \leftarrow (U, S, X, W_1). \qquad (\text{IV.109}) $$
Strictly causal decoder and non-causal encoder

**Definition 22** Given $n \in \mathbb{N}^*$, we define the n-length code with non-causal encoder and strictly causal decoder by a pair $(\sigma, \tau)$ where $\tau = \{\tau_t\}_{t \in \{1, \dots, n\}}$ of deterministic functions

$$ \sigma: \mathcal{U}^n \times \mathcal{S}^n \to \mathcal{X}^n, \qquad (\text{IV.110}) $$

$$ \tau_t: \mathcal{Y}^{t-1} \times \mathcal{Z}^{t-1} \to \mathcal{V}, \quad \forall t \in \{1, \dots, n\}. \qquad (\text{IV.111}) $$

We denote by $\mathcal{C}^{\text{sd}}(n)$ the set of n-length code with non-causal encoder and strictly causal decoder.

We denote by $\mathcal{A}^{\text{sd}}$, the set of target distributions that are achievable by using a code $(\sigma, \tau) \in \mathcal{C}^{\text{sd}}(n)$ with non-causal encoder and strictly causal decoder.

**Theorem 16** A target probability distribution $Q_{USZXYV} \in \mathcal{A}^{\text{sd}}$ if and only if

$$ Q_{USZXYV} = \mathcal{P}_{USZ} Q_{XV|US} \mathcal{T}_{Y|XS} \qquad (\text{IV.112}) $$

and there exist an auxiliary random variables $W_1 \in W_1$ with $|W_1| \le |\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{V}| + 2$ such that

$$ \max_{\tilde{Q}_{USZW_1XYV} \in \mathcal{Q}^{\text{sd}}} \left( I(W_1; Y, Z|V) - I(W_1, V; U, S) \right) \ge 0, \qquad (\text{IV.113}) $$

where

$$ \mathcal{Q}^{\text{sd}} = \left\{ \tilde{Q}_{USZW_1XYV} = \mathcal{P}_{USZ} Q_{XV|US} \tilde{Q}_{W_1|USXV} \mathcal{T}_{Y|XS} \right\}. \qquad (\text{IV.114}) $$

This result is stated in (Le Treust, 2015c, [IC13], Eq. (16)) and in (Le Treust, 2015, [W1]). The solution of (IV.113) can be obtained by replacing $W_2$ by $V$ in the solution of (IV.105) in Theorem 15. Any distribution $\tilde{Q}_{USZW_1XYV} \in \mathcal{Q}^{\text{sd}}$ satisfies the Markov chains

$$ Y \leftarrow (X, S) \leftarrow (U, Z, W_1, V), \qquad (\text{IV.115}) $$

$$ Z \leftarrow (U, S) \leftarrow (X, Y, W_1, V). \qquad (\text{IV.116}) $$

IV.4.c Causal encoder and non-causal decoder

We consider the case where the decoder is causal, as depicted in Fig. IV.15.

**Definition 23** Given $n \in \mathbb{N}^*$, we define the n-length code with causal encoder and non-causal decoder by a pair $(\sigma, \tau)$ where $\sigma = \{\sigma_t\}_{t \in \{1, \dots, n\}}$ of deterministic functions

$$ \sigma_t: \mathcal{U}^t \times \mathcal{S}^t \to \mathcal{X}, \quad \forall t \in \{1, \dots, n\}, \qquad (\text{IV.117}) $$

$$ \tau: \mathcal{Y}^n \times \mathcal{Z}^n \to \mathcal{V}^n, \qquad (\text{IV.118}) $$

We denote by $\mathcal{C}^{\text{ce}}(n)$ the set of n-length code with causal encoder and non-causal decoder.

The code $(\sigma, \tau) \in \mathcal{C}^{\text{ce}}(n)$ induces a probability distribution $\mathcal{P}_{U^n S^n Z^n X^n Y^n V^n}^c$ defined, for all $(u^n, s^n, z^n, x^n, y^n, v^n)$, by

$$ \mathcal{P}_{U^n S^n Z^n X^n Y^n V^n}^c (u^n, s^n, z^n, x^n, y^n, v^n) = \left( \prod_{t=1}^n \mathcal{P}_{USZ}(u_t, s_t, z_t) \right) \left( \prod_{t=1}^n \mathbb{1}\{x_t = \sigma_t(u^t, s^t)\} \right) \left( \prod_{t=1}^n \mathcal{T}_{Y|XS}(y_t|x_t, s_t) \right) \mathbb{1}\{v^n = \tau(y^n, z^n)\}. \qquad (\text{IV.119}) $$

We refer to the Definitions 13 and 14 for the random empirical distribution $Q_{USZXYV}^n$ and the notion of achievable distribution. We denote by $\mathcal{A}^{\text{ce}}$ the set of target distributions that are achievable by using a code $(\sigma, \tau) \in \mathcal{C}^{\text{ce}}(n)$ with non-causal encoder and causal decoder.
<figure><img src="image_29.png" /><figcaption>Figure IV.15 – The encoding function is causal $\sigma_t$ for $t \in \{1, \dots, n\}$ and the decoding function $\tau$ is non-causal.</figcaption></figure>

**Theorem 17** A target probability distribution $Q_{USZXYV} \in \mathcal{A}^{\text{ce}}$ if and only if

$$Q_{USZXYV} = P_{USZ}Q_{X|US}T_{Y|XS}Q_{V|USZXY}, \qquad (\text{IV.120})$$

and there exist a pair of auxiliary random variables $(W_1, W_2) \in W_1 \times W_2$ with $\max(|W_1|, |W_2|) \le |U \times S \times Z \times X \times V| + 2$ such that

$$\max_{\tilde{Q}_{USZW_1W_2XYV} \in \mathcal{Q}^{\text{ce}}(\tilde{Q}_{USZXYV})} \left( I(W_1, W_2; Y, Z) - I(W_2; U, S|W_1) \right) \ge 0, \qquad (\text{IV.121})$$

where for every $Q_{USZXYV}$,

$$\tilde{Q}^{\text{ce}}(Q_{USZXYV}) = \left\{ \tilde{Q}_{USZW_1W_2XYV} = P_{USZ} \tilde{Q}_{W_1} \tilde{Q}_{X|USW_1} \tilde{Q}_{W_2|USW_1} T_{Y|XS} \tilde{Q}_{V|YZW_1W_2}, \right. \\ \left. Q_{USZXYV} = \sum_{(w_1, w_2) \in W_1 \times W_2} \tilde{Q}_{USZW_1W_2XYV} \right\}. \qquad (\text{IV.122})$$

This result is stated in (Le Treust, 2015c, [IC13], Theorem V.1) and in (Le Treust, 2015, [W1]). Any distribution $\tilde{Q}_{USZW_1W_2XYV} \in \mathcal{Q}^{\text{ce}}$ satisfies the properties

$$(U, S) \text{ are independent of } W_1, \qquad (\text{IV.123})$$

$$X \leftarrow (U, S, W_1) \leftarrow W_2, \qquad (\text{IV.124})$$

$$Y \leftarrow (X, S) \leftarrow (U, Z, W_1, W_2), \qquad (\text{IV.125})$$

$$Z \leftarrow (U, S) \leftarrow (X, Y, W_1, W_2), \qquad (\text{IV.126})$$

$$V \leftarrow (Y, Z, W_1, W_2) \leftarrow (U, S, X). \qquad (\text{IV.127})$$

## Strictly causal encoder and non-causal decoder

**Definition 24** Given $n \in \mathbb{N}^*$, we define the n-length code with causal encoder and non-causal decoder by a pair $(\sigma, \tau)$ where $\sigma = \{\sigma_t\}_{t \in \{1, \dots, n\}}$ of deterministic functions

$$\sigma_t : \mathcal{U}^{t-1} \times \mathcal{S}^{t-1} \to \mathcal{X}, \quad \forall t \in \{1, \dots, n\}, \qquad (\text{IV.128})$$

$$\tau : \mathcal{Y}^n \times \mathcal{Z}^n \to \mathcal{V}^n, \qquad (\text{IV.129})$$

We denote by $\mathcal{C}^{\text{se}}(n)$ the set of n-length code with causal encoder and non-causal decoder.

We denote by $\mathcal{A}^{\text{se}}$, the set of target distributions that are achievable by using a code $(\sigma, \tau) \in \mathcal{C}^{\text{se}}(n)$ with non-causal encoder and strictly causal decoder.

**Theorem 18** A target probability distribution $Q_{USZXYV} \in \mathcal{A}^{\text{se}}$ if and only if

$$Q_{USZXYV} = P_{USZ}Q_X T_{Y|XS} Q_{V|USZXY} \qquad (\text{IV.130})$$
and there exist an auxiliary random variables $W_2 \in W_2$ with $|W_2| \le |U \times S \times Z \times X \times V| + 2$ such that

$$ \max_{\tilde{Q}_{USZW_2XYV} \in \mathbb{Q}^{\text{se}}} \left( I(X, W_2; Y, Z) - I(W_2; U, S|X) \right) \ge 0, \qquad (\text{IV.131}) $$

where

$$ \begin{aligned} \mathbb{Q}^{\text{se}} = & \left\{ \tilde{Q}_{USZW_2XYV} = P_{USZ} \mathbb{Q}_X \tilde{Q}_{W_2|USX} T_{Y|XS} \tilde{Q}_{V|YZXW_2}, \right. \\ & \left. \mathbb{Q}_{V|USZXY} = \sum_{w_2 \in W_2} \tilde{Q}_{W_2|USX}(w_2|\cdot, \cdot, \cdot) \tilde{Q}_{V|YZXW_2}(\cdot|\cdot, \cdot, \cdot, w) \right\}. \end{aligned} \qquad (\text{IV.132}) $$

This result is stated in (Le Treust, 2015c, [IC13], Theorem V.1) and in (Le Treust, 2015, [W1]). The solution of (IV.131) can be obtained by replacing $W_1$ by $X$ in the solution of (IV.121) in Theorem 17. Any distribution $\tilde{Q}_{USZW_1XYV} \in \mathbb{Q}^{\text{se}}$ satisfies

$$ (U, S) \text{ are independent of } X, \qquad (\text{IV.133}) $$

$$ Y \leftarrow (X, S) \leftarrow (U, Z, W_2), \qquad (\text{IV.134}) $$

$$ Z \leftarrow (U, S) \leftarrow (X, Y, W_2), \qquad (\text{IV.135}) $$

$$ V \leftarrow (Y, Z, X, W_2) \leftarrow (U, S). \qquad (\text{IV.136}) $$

## IV.5 Chapter summary

In this chapter, we investigate the coordination problem posed by Gossner et al. (2006), and revisited in the Information Theory literature by Cuff et al. (2010). We characterize the optimal solutions to various point-to-point scenarios, e.g. when the decoder or the encoder are strictly causal, causal, non-causal, when the source and the channel are state-dependent, and with source feedforward and channel output feedback.

One setting remains unsolved, when both encoder and decoder perform non-causally. This open question seems related to the distributed lossy source coding problem, in which the pair of random variables $(U, Y)$ are correlated information sources observed by the encoder and the decoder. Inner and outer bounds for the distributed lossy source coding problem are stated in Berger (1978) and Tung (1978).

In the next chapter, we present several extensions and applications of the coordination results.
# Chapter V

## Impact of empirical coordination results

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

In this chapter, we explore the consequences of the results of Chap. IV. The first section presents the contributions for the channel state masking problem, stated in (Le Treust and Bloch, 2021, [J10]), (Le Treust and Bloch, 2016, [IC16]), (Le Treust and Bloch, 2019, [NC9]). In the second section, we use coordination coding for a decentralized control problem called the Witsenhausen’s counterexample. This corresponds to (Le Treust and Oechtering, 2021, [IC27]), (Oechtering and Le Treust, 2019, [IC23]), (Le Treust and Oechtering, 2018, [IC22]),

(Le Treust and Oechtering, 2022, [W9]). The third section presents some of Giulia Cervia’s PhD contributions on strong coordination problems, i.e. when the probability distribution induced by the coding converges to a target i.i.d. probability distribution. This corresponds to (Cervia et al., 2020, [J9]), (Cervia et al., 2018, [IC21]), (Cervia et al., 2017b, [IC19]), (Cervia et al., 2016, [IC17]), (Cervia et al., 2017a, [NC7]).

## Contents

<table><tr><td>V.1</td><td>State leakage and coordination with causal state knowledge at the encoder</td><td>53</td></tr><tr><td>V.1.a</td><td>Problem statement</td><td>54</td></tr><tr><td>V.1.b</td><td>Characterization of achievable triples of rate, leakage and distribution</td><td>55</td></tr><tr><td>V.1.c</td><td>Channel state estimation via cost function</td><td>57</td></tr><tr><td>V.1.d</td><td>Extensions to more general scenarios</td><td>59</td></tr><tr><td>V.1.e</td><td>Strictly causal encoding</td><td>61</td></tr><tr><td>V.2</td><td>Decentralized control: Witsenhausen's counterexample</td><td>62</td></tr><tr><td>V.2.a</td><td>System model</td><td>63</td></tr><tr><td>V.2.b</td><td>Coding Result</td><td>64</td></tr><tr><td>V.2.c</td><td>Control schemes of particular interest</td><td>65</td></tr><tr><td>V.2.d</td><td>Numerical Results</td><td>68</td></tr><tr><td>V.2.e</td><td>Discussion</td><td>69</td></tr><tr><td>V.3</td><td>Strong coordination of signals and actions</td><td>70</td></tr><tr><td>V.3.a</td><td>Inner and outer bounds for the strong coordination region</td><td>72</td></tr><tr><td>V.3.b</td><td>Strong coordination region with state and side information</td><td>73</td></tr><tr><td>V.3.c</td><td>Characterization of the strong coordination region for special cases</td><td>75</td></tr><tr><td>V.3.d</td><td>Is separation optimal?</td><td>78</td></tr><tr><td>V.4</td><td>Chapter summary</td><td>81</td></tr></table>
V.1 State leakage and coordination with causal state knowledge at the encoder

The study of state-dependent channels can be traced back to the early works of Shannon (1958) and Gel'fand and Pinsker (1980), which identified optimal coding strategies to transmit reliably in the presence of a state known at the encoder causally or non-causally, respectively. The insights derived from the models have since proved central to the study of diverse topics including wireless communications, see Costa (1983); Keshet et al. (2008), information-hiding and watermarking as in Moulin and O'Sullivan (2003), and information transmission in repeated games in Gossner et al. (2006). The present work relates to the latter application and studies state-dependent channels with causal state knowledge from the perspective of empirical coordination Cuff et al. (2010).

Previous studies that have explored the problem of not only decoding messages at the receiver but also estimating the channel state, are particularly relevant to the present work. The state masking formulation

<figure><img src="image_31.png" /><figcaption>Figure V.1 – The memoryless channel $T_{Y|XS}$ depends on the state drawn i.i.d. according to $\mathcal{P}_S$. The encoding function is causal $f_t: \mathcal{M} \times \mathcal{S}^t \to \mathcal{X}$, for all $t \in \{1, \dots, n\}$ and the decoding functions $g: \mathcal{Y}^n \to \mathcal{M}$ and $h: \mathcal{Y}^n \to \Delta(\mathcal{V}^n)$ are non-causal.</figcaption></figure>

of the problem, see Merhav and Shamai (2007), aims at characterizing the trade-off between the rate of reliable communication and the minimal leakage about the channel state. The rate-leakage capacity region of state masking has been successfully characterized for both causal and non-causal state knowledge. The state amplification formulation of Kim et al. (2008), in which the state is conveyed to the receiver instead of being masked, aims at characterizing the trade-off between the rate of reliable communication and the reduction of uncertainty about the state. The rate-uncertainty reduction capacity region of state amplification has also been successfully characterized for causal and non-causal state knowledge. The state amplification formulation was subsequently extended in the causal case by replacing the reduction of uncertainty about the state by an average cost function in Choudhuri et al. (2013) (this model was dubbed causal *state communication*). Note that, in such a scenario, the channel output feedback at the encoder increases the region of achievable rate-cost pairs, as in Bross and Lapidoth (2018). The rate-cost capacity region of state communication has been successfully characterized for causal and strictly causal state knowledge, and has been characterized for noiseless and noisy non-causal state knowledge in the case of Gaussian channels with a quadratic cost, see Sutivong et al. (2005); Tian et al. (2015). Both formulations have been combined in Koyluoglu et al. (2016) to study the trade-off between amplification and leakage rates in a channel with two receivers having opposite objectives. The amplification-leakage capacity region has been investigated for non-causal state knowledge, via generally non-matching inner and outer bounds. As a perhaps more concrete example, in Tutuncuoglu et al. (2014), the authors have studied the trade-off between amplification and leakage in the context of an energy harvesting scenario. An extreme situation of state masking, called state obfuscation, in which the objective is to make the channel output sequence nearly independent of the channel states, has recently been investigated in Wang and Wornell (2020).

We revisit the problems of state masking and state amplification with causal and strictly causal state knowledge through the lens of empirical coordination, see Cuff et al. (2010), Kramer and Savari (2007). Empirical coordination refers to the control of the joint histograms of the various sequences such as states, codewords, that appear in channel models, and is related to the coordination of autonomous decision makers in game theory as in Gossner et al. (2006). Specifically, the study of empirical coordination over state-dependent channels is a proxy for characterizing the utility of autonomous decision makers playing a repeated game in the presence of an environment variable (the state), random Gossner et al. (2006); Gossner and Vieille (2002) or adversarial Gossner et al. (2009); Gossner and Tomala (2006, 2007),
and of an observation structure (the channel) describing how agents observe each other's actions. The characterization of the empirical coordination capacity requires the design of coding schemes in which the actions of the decision makers are sequences that embed coordination information. The empirical coordination capacity has been studied for state-dependent channels under different constraints including strictly causal and causal encoding Cuff and Schieler (2011), for perfect channel Cuff and Zhao (2011), for strictly causal and causal decoding (Le Treust, 2017, [J6]), with source feedforward Larrousse et al. (2018), for lossless decoding (Le Treust, 2014, [IC12]), with secrecy constraint Schieler and Cuff (2014), with two-sided state information (Le Treust, 2015c, [IC13]) and with channel feedback (Le Treust, 2015b, [IC14]). Empirical coordination is also a powerful tool for controlling the Bayesian posterior beliefs of the decoder, e.g. in the problems of Bayesian persuasion (Le Treust and Tomala, 2019, [J8]) and strategic communication (Le Treust and Tomala, 2019, [W3]).

The main contribution of the present work is to show that empirical coordination provides a natural framework in which to jointly study the problems of reliable communication, state masking, and state amplification. This connection highlights some of the benefits of empirical coordination beyond those already highlighted in earlier works Cuff and Schieler (2011)–(Le Treust, 2015b, [IC14]). In particular, we obtain the following.

* We introduce and characterize the notion of core of the receiver's knowledge, which captures what the decoder can exactly know about the other variables involved in the system. For instance, this allows us to characterize the rate-leakage-coordination region for the causal state-dependent channel (Theorem 19). Our definition of leakage refines previous work by exactly characterizing the leakage rate instead of only providing a single-sided bound. When specialized, our result (Theorem 20) simultaneously recovers the constraints already established both in (Merhav and Shamai, 2007, Section V) and (Kim et al., 2008, Theorem 2).

* We revisit the problem of causal state communication and characterize the normalized KL-divergence between the decoder's posterior beliefs and a target belief induced by coordination (Theorem 21). This allows us to characterize the rate-cost trade-off for a zero-sum game, in which the decoder attempts to estimate the state while the encoder tries to mask it (Theorem 22).

* We extend the results to other models, including two-sided state information (Theorem 23), noisy feedback (Theorem 24), and strictly causal encoding (Theorem 25).

The rest of the section is organized as follows. In Section V.1.a, we formally introduce the model, along with necessary definitions and notation, and we state our main results. In Section V.1.c, we investigate the channel state estimation problem by introducing the KL-divergence and the decoder's posterior beliefs. In Section V.1.d and Section V.1.e, we present some extensions of our results to different scenarios.

## V.1.a Problem statement

The problem under investigation is illustrated in Figure V.1. A uniformly distributed message represented by the random variable $M \in \mathcal{M}$ is to be transmitted over a state dependent memoryless channel characterized by the conditional distribution $\mathcal{T}_{Y|XS}$ and a channel state $S \in \mathcal{S}$ drawn according to the i.i.d. distribution $\mathcal{P}_S$. For $n \in \mathbb{N}^*$, the message $M$ and the state sequence $S^n$ are encoded into a codeword $X^n \in \mathcal{X}^n$ using an encoder, subject to causal constraints to be precised later. Upon observing the output $Y^n \in \mathcal{Y}^n$ of the noisy channel, the receiver uses a decoder to form an estimate $\hat{M} \in \mathcal{M}$ of $M$ and to generate actions $V^n \in \mathcal{V}^n$, whose exact role will be precised shortly. For now, $V^n$ can be thought of as an estimate of the state sequence $S^n$ but more generally captures the ability of the receiver to coordinate with the transmitter and the channel state. Both $\mathcal{T}_{Y|XS}$ and $\mathcal{P}_S$ are assumed known to all parties. We are specifically interested in causal encoders formally defined as follows.

**Definition 25** A code with causal encoding $(f,g,h)$ consists of

$$f_t : \mathcal{M} \times \mathcal{S}^t \to \Delta(\mathcal{X}), \quad \forall t \in \{1, \dots, n\}, \qquad (V.1)$$

$$g : \mathcal{Y}^n \to \mathcal{M}, \qquad (V.2)$$

$$h : \mathcal{Y}^n \to \Delta(\mathcal{V}^n), \qquad (V.3)$$
where $f = (f_t)_{t \in \{1, \dots, n\}}$ are stochastic encoding functions, $g$ is a deterministic decoding function and $h$ is a stochastic receiver action function. The set of codes with causal encoding with length $n$ and message set $\mathcal{M}$ is denoted $C_c(n, \mathcal{M})$.

A code $(f, g, h) \in C_c(n, \mathcal{M})$, the uniform distribution of the messages $\mathcal{P}_M$, the source $\mathcal{P}_S$ and the channel $\mathcal{T}_{Y|XS}$, induce a distribution on $(M, S^n, X^n, Y^n, V^n, \hat{M})$ given by

$$ \mathcal{P}_M \prod_{t=1}^{n} \left[ \mathcal{P}_{S_t} f_{X_t|S^t M} \mathcal{T}_{Y_t|X_t S_t} \right] h_{V^n|Y^n} \mathbf{1}\{\hat{M} = g(Y^n)\}. \quad (V.4) $$

Since the sequences $(S^n, X^n, Y^n, V^n)$ are random, the empirical distribution $Q_{SXYV}^n$ is also a random variable. The performance of codes is measured as follows.

**Definition 26** Fix a target rate $R \ge 0$, a target state leakage $E \ge 0$ and a target distribution $Q_{SXYV}$. The triple $(R, E, Q_{SXYV})$ is achievable if for all $\varepsilon > 0$, there exists $\bar{n} \in \mathbb{N}^*$, for all $n \ge \bar{n}$, there exists a code $(f, g, h) \in C_c(n, \mathcal{M})$ that satisfies

$$ \frac{\log_2 |\mathcal{M}|}{n} \ge R - \varepsilon, \\ \left| \mathcal{L}_e(c) - E \right| \le \varepsilon, \quad \text{with} \quad \mathcal{L}_e(c) = \frac{1}{n} I(S^n; Y^n), \\ \mathcal{P}_e(c) = \Pr(M \ne \hat{M}) + \Pr\left(\left\| Q_{SXYV}^n - Q_{SXYV} \right\|_1 > \varepsilon \right) \le \varepsilon. $$

We denote by $\mathcal{A}_c$ the set of achievable triples $(R, E, Q_{SXYV})$.

In layman's term, performance is captured along three metrics: i) the rate at which the message $M$ can be reliably transmitted; ii) the information leakage rate about the state sequence $S^n$ at the receiver; and iii) the ability of the encoder to coordinate with the receiver, captured by the empirical coordination with respect to $Q_{SXYV}$. The need to coordinate with receiver action $V$ is motivated by problems in which the terminals represent decision makers that choose actions $(X, V)$ as a function of the system state $S$, as in Gossner et al. (2006). The state can also be used to represent a system to control, in which case coordination also ties to the Witsenhausen's counterexample Grover et al. (2015), (Oechtering and Le Treust, 2019, [IC23]).

<figure><img src="image_32.png" /><figcaption>Figure V.2 – The region of achievable $(R, E) \in \mathcal{A}_c$ for a given distribution $Q_{SW_1W_2XYV}$ for which $H(S) < I(S, W_1; Y)$.</figcaption></figure>

## V.1.b Characterization of achievable triples of rate, leakage and distribution

We now state the main result.
**Theorem 19** Consider a target distribution $Q_{SXYV}$ that decomposes as $Q_{SXYV} = P_S Q_{X|S} T_{Y|XS} Q_{V|SXY}$. Then, $(R, E, Q_{SXYV}) \in \mathcal{A}_c$ if and only if there exist two auxiliary random variables $(W_1, W_2)$ with distribution $Q_{SW_1W_2XYV} \in \mathbb{Q}_c$ satisfying

$$I(S; W_1, W_2, Y) \le E \le H(S), \qquad (V.5)$$

$$R + E \le I(W_1, S; Y), \qquad (V.6)$$

where $\mathbb{Q}_c$ is the set of distributions $Q_{SW_1W_2XYV}$ with marginal $Q_{SXYV}$ that decompose as

$$P_S Q_{W_1} Q_{W_2|SW_1} Q_{X|SW_1} T_{Y|XS} Q_{V|YW_1W_2}, \qquad (V.7)$$

and such that $\max(|W_1|, |W_2|) \le |S \times X \times Y \times V| + 1$.

The achievability and converse proofs are provided in (Le Treust and Bloch, 2021, [J10]). The key idea behind the achievability proof is the following. The encoder operates in a Block-Markov fashion to ensure that the transmitted signals, the state, the received sequence, and the receiver actions are coordinated subject to the causal constraint at the encoder. This requires the use of two auxiliary codebooks, captured by the auxiliary random variables $W_1$ and $W_2$, where the first codebook is used for reliable communication while the second one is used to coordinate with the state. Simultaneously, the encoder quantizes the channel state and transmits carefully chosen bin indices on top of its messages to finely control how much the receiver can infer about the channel state. The region of achievable pairs $(R, E)$ is depicted in Fig. V.2 for a given distribution $Q_{SW_1W_2XYV}$, assuming $H(S) < I(S, W_1; Y)$.

**Remark 10** Equation (V.6) and the first inequality of (V.5) imply the information constraints of (Choudhuri et al., 2013, Theorem 3) for causal state communication and of (Cuff and Schieler, 2011, Theorem 2) for empirical coordination.

$$R \le I(W_1, W_2; Y) - I(W_2; S|W_1). \qquad (V.8)$$

Indeed, both Markov chains $X \leftarrow (S, W_1) \leftarrow W_2$ and $Y \leftarrow (X, S) \leftarrow (W_1, W_2)$ imply $Y \leftarrow (W_1, S) \leftarrow W_2$.

Theorem 19 has several important consequences. First, the coordination of both encoder and decoder actions according to $P_S Q_{X|S} T_{Y|XS} Q_{V|SXY}$ is compatible with the reliable transmission of additional information at rate $R \ge 0$. Second, the case of equality in the right-hand-side inequality of (V.5) corresponds to the full disclosure of the channel state $S$ to the decoder. Third, for any $(R, Q_{SXYV})$, the minimal state leakage $E^*(R, Q_{SXYV})$ such that $(R, E^*(R, Q_{SXYV}), Q_{SXYV}) \in \mathcal{A}_c$, if it exists, is given by

$$E^*(R, Q_{SXYV}) = \min_{\substack{Q_{SW_1W_2XYV} \in \mathcal{Q}_c, \\ \text{s.t. } R \le I(W_1, W_2; Y) - I(W_2; S|W_1)}} I(S; W_1, W_2, Y). \qquad (V.9)$$

The reliable transmission of information requires the decoder to know the encoding function, from which it can estimate the channel state $S$. In Section V.1.c, we investigate the relationship between the state leakage $\mathcal{L}_e(c)$ and the decoder's posterior belief $P_{S^n|Y^n}$ induced by the encoding process.

### Special case without receiver actions

We now assume that the decoder does not return an action $V$ coordinated with the other symbols $(S, X, Y)$, in order to compare our setting with the problems of “state masking” (Merhav and Shamai, 2007, Section V) and “state amplification” (Kim et al., 2008, Section IV). Note that these earlier works involve slightly different notions of achievable state leakage. In Merhav and Shamai (2007), the state leakage is upper bounded by $\mathcal{L}_e(c) = \frac{1}{n}I(S^n; Y^n) \le E + \varepsilon$. In Kim et al. (2008), the decoder forms a list $L_n(Y^n) \subseteq S^n$ with cardinality $\log_2|L_n(Y^n)| = H(S) - E$ such that the list decoding error probability $\Pr(S^n \notin L_n(Y^n)) \le \varepsilon$ is small, hence reducing the uncertainty about the state. Here, we require the leakage $\mathcal{L}_e(c) = \frac{1}{n}I(S^n; Y^n)$ induced by the code to be controlled by $|\mathcal{L}_e(c) - E| \le \varepsilon$. Nevertheless, we shall see that our definition allows us to obtain the rate constraints of Kim et al. (2008); Merhav and Shamai (2007) as extreme cases.
**Definition 27** A code without receiver actions consists of stochastic encoding functions $f_t: \mathcal{M} \times \mathcal{S}^t \to \Delta(\mathcal{X})$, $\forall t \in \{1, \dots, n\}$ and a deterministic decoding function $g: \mathcal{Y}^n \to \mathcal{M}$. The set of such codes with length $n$ and message set $\mathcal{M}$ is denoted $C_d(n, \mathcal{M})$. The corresponding set of achievable triples $(R, E, Q_{SXY})$ is defined as in Definition 26 and is denoted $\mathcal{A}_d$.

Note that the target distribution is here restricted to $Q_{SXY} \in \Delta(\mathcal{S} \times \mathcal{X} \times \mathcal{Y})$ since the receiver does not take an action.

**Theorem 20** Consider a target distribution $Q_{SXY}$ that decomposes as $Q_{SXY} = P_S Q_{X|S} T_{Y|XS}$. Then, $(R, E, Q_{SXY}) \in \mathcal{A}_d$ if and only if there exists an auxiliary random variable $W_1$ with distribution $Q_{SW_1XY} \in \mathcal{Q}_d$ that satisfies

$$I(S; W_1, Y) \le E \le H(S), \qquad (V.10)$$

$$R + E \le I(W_1, S; Y), \qquad (V.11)$$

where $\mathcal{Q}_d$ is the set of distributions $Q_{SW_1XY}$ with marginal $Q_{SXY}$ that decompose as

$$P_S Q_{W_1} Q_{X|SW_1} T_{Y|XS}, \qquad (V.12)$$

and such that $|W_1| \le |\mathcal{S} \times \mathcal{Y}| + 1$.

The achievability proof is obtained from Theorem 19 by setting $W_2 = \emptyset$ and by considering a single block coding instead of block-Markov coding. The converse proof is similar to the converse of Theorem 19 and is provided in the Supplementary Materials.

**Remark 11** When setting $W_2 = \emptyset$, (V.8) in Remark 10 simplifies to

$$R \le I(W_1; Y), \qquad (V.13)$$

which, together with the first inequality in (V.10), coincides with the information constraints of (Merhav and Shamai, 2007, pp. 2260). Furthermore, (V.13), (V.11) and the second inequality of (V.10) correspond to the region $R_0$ stated in (Kim et al., 2008, Lemma 3). Formally, the region characterized by Theorem 20 is the intersection of the regions identified in (Merhav and Shamai, 2007, pp. 2260) and (Kim et al., 2008, Lemma 3).

## V.1.c Channel state estimation via cost function

### Decoder posterior belief

In this section, we provide an upper bound on the KL-divergence between the decoder posterior belief $P_{S^n|Y^n}$ induced by an encoding, and the target conditional distribution $Q_{S|YW_1W_2}$.

**Theorem 21 (Channel state estimation)** Assume that the distribution $Q_{SW_1W_2XY}$ has full support. For any conditional distribution $P_{W_1^n W_2^n X^n|S^n}$, we have

$$\frac{1}{n} D \left( \mathcal{P}_{S^n|Y^n} \left\| \prod_{t=1}^{n} Q_{S_t|Y_t W_1, t, W_2, t} \right\| \right) \qquad (V.14)$$

$$\le \mathcal{L}_e(c) - I(S; W_1, W_2, Y) + \alpha_1 \delta + \alpha_2 \mathrm{Pr} \left( \left\| Q_{SW_1W_2Y}^n - Q_{SW_1W_2Y} \right\|_1 > \delta \right), \qquad (V.15)$$

where the constant parameters $\alpha_1 = \sum_{w_2, y} \log_2 \frac{1}{\mathcal{Q}(s|w_1, w_2, y)}$ and $\alpha_2 = \log_2 \frac{1}{\min_{s, y, w_1, w_2} \mathcal{Q}(s|y, w_1, w_2)}$ are strictly positive.

The proof of Theorem 21 is given in (Le Treust and Bloch, 2021, [J10]). Consider a target leakage $E = I(S; W_1, W_2, Y)$ and a pair $(R, Q_{SXYV})$, and assume there exists a distribution $Q_{SW_1W_2XYV} \in \mathcal{Q}_c$ with full support, satisfying (V.5) and (V.6). By Theorem 19, for all $\varepsilon > 0$ and for all $\delta > 0$, there
exists $\bar{n} \in \mathbb{N}^*$ such that for all $n \ge \bar{n}$ there exists a code $(f, g, h) \in \mathcal{C}(n, \mathcal{M})$ with two auxiliary sequences $(W_1^n, W_2^n)$, such that

$$ \left| \mathcal{L}_e(c) - I(S; W_1, W_2, Y) \right| \le \varepsilon \quad \text{and} \\ \Pr \left( \left\| Q_{SW_1 W_2 Y}^n - Q_{SW_1 W_2 Y} \right\|_1 > \delta \right) \le \varepsilon. \qquad (V.16) $$

Hence, by Theorem 21 we have

$$ \frac{1}{n} D \left( \mathcal{P}_{S^n|Y^n} \left\| \prod_{t=1}^{n} Q_{S_t|Y_t W_{1,t} W_{2,t}} \right. \right) \le \varepsilon + \alpha_1 \delta + \alpha_2 \varepsilon, \qquad (V.17) $$

where $\epsilon$ and $\delta$ may go to zero when $n$ goes to infinity. This shows that the posterior belief $\mathcal{P}_{S^n|Y^n}$ approaches the single-letter distribution $Q_{S|YW_1W_2}$. Based on the triple of symbols $(Y, W_1, W_2)$, the decoder generates action $V$ using the conditional distribution $Q_{V|YW_1W_2}$, and infers the channel state $S$ according to the conditional distribution $Q_{S|YW_1W_2}$. In that regard, the random variables $(Y, W_1, W_2)$ capture the "core of the receiver's knowledge," regarding other random variables $S$ and $V$. The bound on the KL-divergence in (V.15) relates to the notion of strategic distance (Gossner and Vieille, 2002, Section 5.2), later used in several articles on repeated game Gossner and Tomala (2006), Gossner and Tomala (2007), Gossner et al. (2009), on Bayesian persuasion (Le Treust and Tomala, 2019, [J8]) and on strategic communication (Le Treust and Tomala, 2019, [W3]).

## Channel state estimation zero-sum game

We now introduce a cost function $c: S \times V \to \mathbb{R}$ and the channel state estimation zero-sum game, in which the encoder and decoder are opponents, i.e. the decoding is selected in order to minimize the cost function, which is maximize by the encoder. Although the encoder and the decoder cooperate in transmitting reliably at rate $R$, the encoder seeks to prevent the decoder from returning a good estimate $v \in V$ of the channel state $s \in S$ by maximizing the expected long-run cost, while the decoder attempts to minimize it.

**Definition 28** A target rate $R \ge 0$ and a target cost $C \ge 0$ are achievable if for all $\varepsilon > 0$, there exists $\bar{n} \in \mathbb{N}^*$ such that for all $n \ge \bar{n}$, there exists a code in $\mathcal{C}_d(n, \mathcal{M})$ such that

$$ \frac{\log_2 |\mathcal{M}|}{n} \ge R - \varepsilon, \qquad (V.18) $$

$$ \Pr \left( M \neq \hat{M} \right) \le \varepsilon, \qquad (V.19) $$

$$ \left| \min_{h_{V^n|Y^n}} \frac{1}{n} \sum_{t=1}^{n} \mathbb{E} [c(S_t, V_t)] - C \right| \le \varepsilon. \qquad (V.20) $$

We denote by $\mathcal{A}_g$ the set of achievable pairs $(R, C) \in \mathcal{A}_g$.

**Theorem 22 (Zero-sum game)** A pair of rate and cost $(R, C) \in \mathcal{A}_g$ is achievable if and only if there exists an auxiliary random variable $W_1$ with distribution $Q_{SW_1XY} \in \mathcal{Q}_d$ that satisfies

$$ R \le I(W_1; Y), \qquad (V.21) $$

$$ C = \min_{P_{V|W_1Y}} \mathbb{E}[c(S, V)], \qquad (V.22) $$

where the set $\mathcal{Q}_d$ is defined in Theorem 20.

The proof of Theorem 22 is provided in (Le Treust and Bloch, 2021, [J10]). The achievability proof is a consequence of Theorem 20 and Theorem 21, and of (Le Treust and Tomala, 2019, [J8], Lemma A.8, Lemma A.21).
**Remark 12 (Maximin-minimax result)** The optimal cost-rate function $C^*(R)$ reformulates as a maximin problem

$$ 
\begin{aligned}
C^*(R) &= \max_{\substack{\mathbb{Q}_{W_1}, \mathbb{Q}_{X|SW_1} \\ R \le I(W_1;Y)}} \min_{\mathcal{P}_{V|W_1Y}} \mathbb{E}[c(S, V)] \\
&= \min_{\substack{\mathbb{Q}_{W_1}, \mathbb{Q}_{X|SW_1} \\ R \le I(W_1;Y)}} \max_{\mathcal{P}_{V|W_1Y}} \mathbb{E}[c(S, V)].
\end{aligned} 
\quad (V.23) $$

The maximum and the minimum are taken over compact and convex sets and the cost function is linear. Hence by Sion's Theorem Sion (1958) the maximin is equal to the minimax and the value of this channel state estimation zero-sum game is $C^*(R)$.

**Remark 13 (One auxiliary random variable)** The formulation of Theorem 22 is based on the set of distributions $Q_d$ with only one auxiliary random variable $W_1$, instead of the two random variables $(W_1, W_2)$ of the set $Q_c$. When the encoder tries to mask the channel state, it does not require the auxiliary random variable $W_2$ anymore, since

$$ C^* = \max_{\substack{\mathbb{Q}_{W_1}, \mathbb{Q}_{X|SW_1}, \mathbb{Q}_{W_2|SW_1} \\ R \le I(W_1, W_2; Y) - I(W_2; S|W_1)}} \min_{\mathcal{P}_{V|W_1W_2Y}} \mathbb{E}[c(S, V)] \quad (V.24) $$

$$ \le \max_{\substack{\mathbb{Q}_{W_1}, \mathbb{Q}_{X|SW_1}, \mathbb{Q}_{W_2|SW_1} \\ R \le I(W_1, W_2; Y) - I(W_2; S|W_1)}} \min_{\mathcal{P}_{V|W_1Y}} \mathbb{E}[c(S, V)] \quad (V.25) $$

$$ \le \max_{\substack{\mathbb{Q}_{W_1}, \mathbb{Q}_{X|SW_1} \\ R \le I(W_1;Y)}} \min_{\mathcal{P}_{V|W_1Y}} \mathbb{E}[c(S, V)] = C^*, \quad (V.26) $$

where (V.25) comes from taking the minimum over $\mathcal{P}_{V|W_1Y}$ instead of $\mathcal{P}_{V|W_1W_2Y}$; (V.26) comes from the Markov chain $Y \leftarrow (S, W_1) \leftarrow W_2$ stated in (V.7), that ensures $I(W_1, W_2; Y) - I(W_2; S|W_1) \le I(W_1; Y)$. Hence, the information constraint $R \le I(W_1, W_2; Y) - I(W_2; S|W_1)$ is more restrictive than $R \le I(W_1; Y)$.

**Remark 14 (Zero rate case)** In the special case $R = 0$, which corresponds to a channel estimation game without communication, the encoding functions reduce to $f_{X_t|S^t}$ instead of $f_{X_t|S^t M}$. The channel state estimation zero-sum game becomes the maximin problem

$$ \max_{\{f_{X_t|S^t}\}_{t \in \{1, \dots, n\}}} \min_{h_{V^n|Y^n}} \mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n} c(S_t, V_t)\right], \quad (V.27) $$

in which the encoder chooses $\{f_{X_t|S^t}\}_{t \in \{1, \dots, n\}}$ and the decoder chooses $h_{V^n|Y^n}$. Theorem 22 shows that the single-letter solution is $\max_{\mathbb{Q}_{W_1}, \mathbb{Q}_{X|SW_1}} \min_{\mathcal{P}_{V|W_1Y}} \mathbb{E}[c(S, V)]$.

If the objectives of both encoder and decoder were aligned, i.e., they would both try to minimize the long term average cost

$$ \min_{\{f_{X_t|S^t}\}_{t \in \{1, \dots, n\}}, \quad h_{V^n|Y^n}} \mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n} c(S_t, V_t)\right], \quad (V.28) $$

the problem would become the causal channel state communication studied in Choudhuri et al. (2013).

## V.1.d Extensions to more general scenarios

### Two-sided state information

The case of two-sided state information is illustrated in Fig. V.3. The channel state $S^n$, information source $U^n$ and decoder state information $Z^n$ are jointly distributed according to the i.i.d. distribution $P_{USZ} \in \Delta(U \times S \times Z)$.
**Definition 29** A code with two-sided state information consists of stochastic functions $f_t: \mathcal{M} \times \mathcal{U}^t \times \mathcal{S}^t \to \Delta(\mathcal{X})$ $\forall t \in \{1, \dots, n\}$, a deterministic decoding function $g: \mathcal{Y}^n \times \mathcal{Z}^n \to \mathcal{M}$, and a stochastic receiver action function $h: \mathcal{Y}^n \times \mathcal{Z}^n \to \Delta(\mathcal{V}^n)$. The set of codes with causal encoding with length $n$ and message set $\mathcal{M}$ is denoted $\mathcal{C}_s(n, \mathcal{M})$.

<figure><img src="image_33.png" /><figcaption>Figure V.3 – The causal encoding function is $f_t: \mathcal{M} \times \mathcal{U}^t \times \mathcal{S}^t \to \mathcal{X}$, for all $t \in \{1, \dots, n\}$ and the non-causal decoding functions are $g: \mathcal{Y}^n \times \mathcal{Z}^n \to \mathcal{M}$ and $h: \mathcal{Y}^n \times \mathcal{Z}^n \to \Delta(\mathcal{V}^n)$.</figcaption></figure>

A code $(f, g, h) \in \mathcal{C}_s(n, \mathcal{M})$, the uniform distribution of the messages $\mathcal{P}_M$, the source $\mathcal{P}_{USZ}$ and the channel $\mathcal{T}_{Y|XS}$ induce a distribution on $(M, U^n, S^n, Z^n, X^n, Y^n, V^n, \hat{M})$ given by

$$ \mathcal{P}_M \prod_{t=1}^{n} \left[ \mathcal{P}_{U_t S_t Z_t} f_{X_t|U^t S^t M} \mathcal{T}_{Y_t|X_t S_t} \right] h_{V^n|Y^n Z^n} \mathbf{1}\{\hat{M} = g(Y^n, Z^n)\}. \quad (V.29) $$

We denote by $\mathcal{A}_s$ the set of achievable triples $(R, E, Q_{USZXYV})$, defined similarly as in Definition 26.

**Theorem 23 (Two-sided state information)** Consider a target distribution $Q_{USZXYV}$ that decomposes as $Q_{USZXYV} = \mathcal{P}_{USZ}Q_{X|US}\mathcal{T}_{Y|XS}Q_{V|USZXY}$. Then, $(R, E, Q_{USZXYV}) \in \mathcal{A}_s$ if and only if there exist two auxiliary random variables $(W_1, W_2)$ with distribution $Q_{USZW_1W_2XYV} \in \mathcal{Q}_s$ satisfying

$$ I(U, S; W_1, W_2, Y, Z) \le E \le H(U, S), \quad (V.30) $$

$$ R + E \le I(W_1, U, S; Y, Z), \quad (V.31) $$

where $\mathcal{Q}_s$ is the set of distributions $Q_{USZW_1W_2XYV}$ that decompose as

$$ \mathcal{P}_{USZ} Q_{W_1} Q_{W_2|USW_1} Q_{X|USW_1} \mathcal{T}_{Y|XS} Q_{V|YZW_1W_2}, \quad (V.32) $$

and such that $\max(|W_1|, |W_2|) \le d+1$ with $d = |\mathcal{U} \times \mathcal{S} \times \mathcal{Z} \times \mathcal{X} \times \mathcal{Y} \times \mathcal{V}|$.

The achievability proof follows directly from the proof of Theorem 19, by replacing the random variable of the channel state $S$ by the pair $(U, S)$ and the random variable of the channel output $Y$ by the pair $(Y, Z)$. The converse proof is provided in the Supplementary Materials.

**Remark 15** The Markov chains $X \rightsquigarrow (U, S, W_1) \rightsquigarrow W_2$, $Y \rightsquigarrow (X, S) \rightsquigarrow (U, Z, W_1, W_2)$ and $Z \rightsquigarrow (U, S) \rightsquigarrow (X, Y, W_1, W_2)$ imply another Markov chain property $(Y, Z) \rightsquigarrow (W_1, U, S) \rightsquigarrow W_2$. Indeed, for all $(u, s, z, w_1, w_2, x, y)$ we have

$$ \begin{aligned} & \mathcal{P}(y, z|w_1, w_2, u, s) \\ &= \sum_{x \in \mathcal{X}} \mathcal{Q}(x|u, s, w_1) \mathcal{T}(y|x, s) \mathcal{P}(z|u, s) = \mathcal{P}(y, z|w_1, u, s). \end{aligned} $$

By combining (V.30) and (V.31) with the Markov chain $(Y, Z) \rightsquigarrow (W_1, U, S) \rightsquigarrow W_2$, we recover the information constraint of (Le Treust, 2015c, [IC13], Theorem V.1):

$$ R \le I(W_1, W_2; Y, Z) - I(W_2; U, S|W_1). \quad (V.33) $$
<figure><img src="image_34.png" /><figcaption>Figure V.4 – The noisy feedback sequence $Y_2^{t-1}$ is drawn i.i.d. according to $\mathcal{T}_{Y_1Y_2|XS}$. The encoding is $f_t: \mathcal{M} \times \mathcal{S}^t \times \mathcal{Y}_2^{t-1} \to \mathcal{X}, \forall t \in \{1, \dots, n\}$.</figcaption></figure>

### Noisy channel feedback observed by the encoder

In this section, we consider that the encoder has noisy feedback $Y_2$ from the state-dependent channel $\mathcal{T}_{Y_1Y_2|XS}$, as depicted in Fig. V.4. The encoding function becomes $f_t: \mathcal{M} \times \mathcal{S}^t \times \mathcal{Y}_2^{t-1} \to \mathcal{X}, \forall t \in \{1, \dots, n\}$ while the decoding functions and the definition of the state leakage remain unchanged. The corresponding set of achievable triples $(R, E, Q_{SXY_1Y_2V})$ is denoted $\mathcal{A}_f$.

**Theorem 24 (Noisy channel feedback)** We consider a target distribution $Q_{SXY_1Y_2V}$ that decomposes as $Q_{SXY_1Y_2V} = \mathcal{P}_S Q_{X|S} \mathcal{T}_{Y_1Y_2|XS} Q_{V|SXY_1Y_2}$. Then, $(R, E, Q_{SXY_1Y_2V}) \in \mathcal{A}_f$ if and only if there exist two auxiliary random variables $(W_1, W_2)$ with distribution $Q_{SW_1W_2XY_1Y_2V} \in \mathcal{Q}_f$ that satisfy

$$R \le I(W_1, W_2; Y_1) - I(W_2; S, Y_2|W_1), \qquad (V.34)$$

$$I(S; W_1, W_2, Y_1) \le E \le H(S), \qquad (V.35)$$

$$R + E \le I(W_1, S; Y_1), \qquad (V.36)$$

where $\mathcal{Q}_f$ is the set of distributions with marginal $Q_{SW_1W_2XY_1Y_2V}$ that decompose as

$$\mathcal{P}_S Q_{W_1} Q_{X|SW_1} \mathcal{T}_{Y_1Y_2|XS} Q_{W_2|SW_1Y_2} Q_{V|Y_1W_1W_2},$$

and such that $\max(|W_1|, |W_2|) \le d+1$ with $d = |S \times \mathcal{X} \times \mathcal{Y}_1 \times \mathcal{Y}_2 \times \mathcal{V}|$.

The achievability proof of Theorem 24 follows directly from the proof of Theorem 19, by replacing the pair $(S^n, W_1^n)$ by the triple $(S^n, W_1^n, Y_2^n)$ in order to select $W_2^n$. The decoding functions and the leakage analysis remain unchanged. The converse proof is stated in the Supplementary Materials.

**Remark 16 (Noisy feedback improves coordination)** The channel feedback increases the set of achievable triples, i.e. $\mathcal{A}_c \subset \mathcal{A}_f$, since the conditional distribution $Q_{W_2|SW_1Y_2}$ depends on channel outputs $Y_2$. The information constraints of Theorem 24 are reduced to that of Theorem 19 since $Q_{W_2|SW_1Y_2} = Q_{W_2|SW_1} \iff W_2 \leftarrow (S, W_1) \leftarrow Y_2 \iff I(W_2; Y_2|S, W_1) = 0$. This was already pointed out for the coordination problem in (Le Treust, 2015b, [IC14]), and for the rate-and-state capacity problem in Bross and Lapidoth (2018).

<figure><img src="image_35.png" /><figcaption>Figure V.5 – The strictly causal encoding function is $f_t: \mathcal{M} \times \mathcal{S}^{t-1} \to \Delta(\mathcal{X})$, for all $t \in \{1, \dots, n\}$ and the non-causal decoding functions are $g: \mathcal{Y}^n \to \mathcal{M}$ and $h: \mathcal{Y}^n \to \Delta(\mathcal{V}^n)$.</figcaption></figure>

### V.1.e Strictly causal encoding

**Definition 30** A code with strictly causal encoding consists of stochastic encoding functions $f_t: \mathcal{M} \times \mathcal{S}^{t-1} \to \Delta(\mathcal{X})$ $\forall t \in \{1, \dots, n\}$, a deterministic decoding function $g: \mathcal{Y}^n \to \mathcal{M}$, and a stochastic
receiver action function h : $\mathcal{Y}^n \to \Delta(\mathcal{Y}^n)$. The set of codes with strictly causal encoding with length n and message set $\mathcal{M}$ is denoted $C_{sc}(n, \mathcal{M})$. The corresponding set of achievable triples $(R, E, Q_{SXYV})$ is defined similarly as in Definition 26 and is denoted $A_{sc}$.

**Theorem 25 (Strictly causal encoding)** Consider a target distribution $Q_{SXYV}$ that decomposes as $Q_{SXYV} = P_S Q_X T_{Y|XS} Q_{V|SXY}$. Then, $(R, E, Q_{SXYV}) \in A_{sc}$ if and only if there exists an auxiliary random variable $W_2$ with distribution $Q_{SW_2XYV} \in Q_{sc}$ that satisfies

$$I(S; X, W_2, Y) \le E \le H(S), \qquad (V.37)$$

$$R + E \le I(X, S; Y), \qquad (V.38)$$

where $Q_{sc}$ is the set of distributions $Q_{SW_2XYV}$ with marginal $Q_{SW_2XYV}$ that decompose as

$$Q_{SW_2XYV} = P_S Q_X Q_{W_2|SX} T_{Y|XS} Q_{V|XYW_2} \qquad (V.39)$$

and such that $|W_2| \le |S \times \mathcal{X} \times \mathcal{Y}| + 1$.

The achievability proof is obtained from Theorem 19 by replacing the auxiliary random variable $W_1$ by the channel input $X$. The converse proof is provided in the Supplementary Materials.

**Remark 17 Equation (V.38), the first inequality of (V.37), the Markov chain $Y \leftarrow (X, S) \leftarrow W_2$, and the independence between $S$ and $X$ imply**

$$R \le I(X, W_2; Y) - I(W_2; S|X). \qquad (V.40)$$

**Corollary 4 (Without receiver's outputs)** A pair of rate and state leakage $(R, E)$ is achievable if and only if there exists a distribution $Q_X$ that satisfies

$$I(S; Y|X) \le E \le H(S), \qquad (V.41)$$

$$R + E \le I(X, S; Y). \qquad (V.42)$$

The achievability proof of Corollary 4 comes from the achievability proof of Theorem 25. The converse proof is based on standard arguments. Equations (V.41) and (V.42) imply $R \le I(X; Y)$.

## V.2 Decentralized control: Witsenhausen's counterexample

In this section, we investigate the impact of the coordination results of Chap. IV in decentralized control problem. In Witsenhausen (1968), the author introduce a famous counterexample that shows that the best affine policy is outperformed by non-linear policies. Since then the example serves as study object illustrating the importance of the information pattern in distributed decision making, see Yüksel and Başar (2013) for a comprehensive discussion.

The first vector-valued extension considering a non-causal setup was studied in Grover and Sahai (2008) followed by a series of works, e.g. Grover et al. (2013); Grover and Sahai (2010); Grover et al. (2015). A comprehensive overview on the corresponding results is provided in Le Treust and Oechtering (2018), where we also discuss its close relation to the coordination problem. Optimal coding schemes for relevant setups are derived in Le Treust (2017), which also provides a review on the related literature. Most of the results were derived for finite alphabet setup where the concept of strong typicality provides the Markov Lemma. A rigorous extension to the Gaussian case has been done in Grover and Sahai (2010). The main result was proved to be optimal in Choudhuri and Mitra (2012b).

In this work we extend the finite alphabet coding scheme based on the concept of weak typicality, as in Cover and Thomas (2006) that we extend so that the need of the Markov Lemma can be avoided. Conceptually, the extension is similar to an extension as done in Vu et al. (2019), where also the approach of Wyner (1978) on how to analyze the average estimation error has been used. We extend this approach in this work since the second decision maker estimates the interim state and not the i.i.d. source.

In the following we show that also in this vector-valued setup the best affine policies can be outperformed by non-linear policies. In more detail, there exists parameter configurations where our coordination coding outperforms a simple amplification strategy.
<figure><img src="image_36.png" /><figcaption>Figure V.6 – The state and the channel noise are drawn according to the i.i.d. Gaussian distributions $X_0^n \sim \mathcal{N}(0, Q\mathbb{I})$ and $Z_1^n \sim \mathcal{N}(0, N\mathbb{I})$.</figcaption></figure>

## V.2.a System model

We consider the vector-valued Witsenhausen setup depicted in Fig. V.6. The notations $\mathcal{X}_0, \mathcal{U}_1, \mathcal{X}_1, \mathcal{Y}_1, \mathcal{U}_2$ stand for the sets of states, channel inputs, interim states, channel outputs, receiver outputs, that are all equal to the real line $\mathbb{R}$. For $n \in \mathbb{N}^*$, the n-time Cartesian product of sets is denoted by $\mathcal{X}_0^n$. The sequences of states and channel noises are drawn independently according to the i.i.d. Gaussian distributions $X_0^n \sim \mathcal{N}(0, Q\mathbb{I})$ and $Z_1^n \sim \mathcal{N}(0, N\mathbb{I})$ with $\min(Q, N) > 0$, where $\mathbb{I} \in \mathbb{R}^{n \times n}$ denotes the identity matrix. We denote by $X_1$ the interim state and $Y_1$ the output of the noisy channel, defined by

$$X_1 = X_0 + U_1 \quad \text{with} \quad X_0 \sim \mathcal{N}(0, Q), \qquad (V.43)$$

$$Y_1 = X_1 + Z_1 = X_0 + U_1 + Z_1 \quad \text{with} \quad Z_1 \sim \mathcal{N}(0, N). \qquad (V.44)$$

We denote by $\mathcal{P}_{X_0} = \mathcal{N}(0, Q)$ the Gaussian probability distribution of the state random variable $X_0$, and we denote by $\mathcal{P}_{X_1 Y_1 | X_0 U_1}$ the conditional probability distribution corresponding to (V.43) and (V.44).

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

$$f: \mathcal{X}_0^n \to \mathcal{U}_1^n, \quad g_t: \mathcal{Y}_1^t \to \mathcal{U}_2, \quad \forall t \in \{1, \dots, n\}, \qquad (V.45)$$

which induces a distribution over the sequences of symbols given by

$$\left( \prod_{t=1}^{n} \mathcal{P}_{X_{0,t}} \right) f_{U_1^n | X_0^n} \left( \prod_{t=t}^{n} \mathcal{P}_{X_{1,t} Y_{1,t} | X_{0,t} U_{1,t}} \right) \left( \prod_{t=1}^{n} g_{U_{2,t} | Y_1^t} \right). \qquad (V.46)$$

We denote by $C_d(n)$ the set of control designs with non-causal encoder and causal decoder.

The counterexample of Witsenhausen (1968) allows to investigate the trade-off between two cost functions, a power cost for the channel input $U_1$, and a decoder estimation cost of the interim state $X_1$. We evaluate these two costs by considering their respective averages over the sequences of symbols.

**Definition 32** We define the n-stage costs associated with control design $c \in C_d(n)$ by

$$\gamma_{\mathbf{p}}^{n}(c) = \begin{cases} \mathbb{E}\left[\frac{1}{n} \sum_{t=1}^{n} U_{1,t}^2\right] & \text{if it exists,} \\ +\infty & \text{otherwise,} \end{cases} \qquad (V.47)$$

$$\gamma_{\mathbf{s}}^{n}(c) = \begin{cases} \mathbb{E}\left[\frac{1}{n} \sum_{t=1}^{n} (X_{1,t} - U_{2,t})^2\right] & \text{if it exists,} \\ +\infty & \text{otherwise.} \end{cases} \qquad (V.48)$$

The pair of costs $(P, S) \in \mathbb{R}^2$ is achievable if for all $\varepsilon > 0$, there exists $\bar{n} \in \mathbb{N}^*$ such that for all $n \ge \bar{n}$, there exists a control design $c \in C_d(n)$ such that

$$\left|P - \gamma_{\mathbf{p}}^{n}(c)\right| + \left|S - \gamma_{\mathbf{s}}^{n}(c)\right| \le \varepsilon. \qquad (V.49)$$

The goal is to characterize the set of achievable pair of costs $(P, S) \in \mathbb{R}^2$, which we call the Witsenhausen costs.