Search

The vector-valued extension of the famous Witsenhausen counterexample setup is studied where the encoder, i.e. the first decision maker, non-causally knows and encodes the i.i.d. state sequence and the decoder, i.e. the second decision maker, causally estimates the interim state. The coding scheme is transferred from the finite alphabet coordination problem for which it is proved to be optimal. The extension to the Gaussian setup is based on a nonstandard weak typicality approach and requires a careful average estimation error analysis since the interim state is estimated by the decoder. We provide a single-letter expression that characterizes the optimal trade-off between the Witsenhausen power cost and estimation cost. The two auxiliary random variables improve the communication with the decoder, while performing the dual role of the channel input, which also controls the state of the system. Interestingly, we show that a pair of discrete and continuous auxiliary random variables, outperforms both Witsenhausen two point strategy and the best affine policies. The optimal choice of random variables remains unknown.

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 information. 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, interact, 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 communication 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., 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. Étant donnée une contrainte de capacité de communication, ce théorème caractérise le schéma de codage optimal pour compresser 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”.

International audience; Optimal design of distributed decision policies can be a difficult task, illustrated by the famous Witsenhausen counterexample. In this paper we characterize the optimal control designs for the vector-valued setting assuming that it results in an interim state, i.e. the result of the first decision maker action, that can be described by a continuous random variable which has a probability density function. More specifically, we provide a genie-aided outer bound that relies on our previous results for empirical coordination problems. This solution turns out to be not optimal in general, since it consists of a time-sharing strategy between two linear schemes of specific power. It follows that the optimal decision strategy for the original scalar Witsenhausen problem must lead to an interim state that cannot be described by a continuous random variable which has a probability density function.

We investigate the problem of strategic point-to-point communication with side information at the decoder, in which the encoder and the decoder have mismatched distortion functions. The decoding process is not supervised, it returns the output sequence that minimizes the decoder's distortion function. The encoding process is designed beforehand and takes into account the decoder's distortion mismatch. When the communication channel is perfect and no side information is available at the decoder, this problem is referred to as the Bayesian persuasion game of Kamenica-Gentzkow in the Economics literature. We formulate the strategic communication scenario as a joint source-channel coding problem with side information at the decoder. The informational content of the source influences the design of the encoding since it impacts differently the two distinct distortion functions. The side information complexifies the analysis since the encoder is uncertain about the decoder's belief on the source statistics. We characterize the single-letter optimal solution by controlling the posterior beliefs induced by the Wyner-Ziv's source encoding scheme. This confirms the benefit of sending encoded data bits even if the decoding process is not supervised.

International audience; The zero-error channel capacity is the maximum asymptotic rate that can be reached with error probability exactly zero, instead of a vanishing error probability. The nature of this problem, essentially combinatorial rather than probabilistic, has led to various researches both in Information Theory and Combinatorics. However, the zero-error capacity is still an open problem, for example the capacity of the noisy-typewriter channel with 7 letters is unknown. In this article, we propose a new approach to construct optimal zero-error codes, based on the concatenation of words of variable-length, taken from a generator set. Three zero-error variable-length coding schemes, referred to as "variable-length coding", "intermingled coding" and "automata-based coding", are under study. We characterize their asymptotic performances via linear difference equations, in terms of simple properties of the generator set, e.g. the roots of the characteristic polynomial, the spectral radius of an adjacency matrix, the inverse of the convergence radius of a generator series. For a specific example, we construct an "intermingled" coding scheme that achieves asymptotically the zero-error capacity.

We revisit the problems of state masking and state amplification through the lens of empirical coordination by considering a state-dependent channel in which the encoder has causal and strictly causal state knowledge. We show that the problem of empirical coordination provides a natural framework in which to jointly study the problems of reliable communication, state masking, and state amplification. We characterize the regions of rate-equivocation-coordination trade-offs for several channel models with causal and strictly causal state knowledge. We exploit this result to solve a channel state estimation zero-sum game in which the encoder prevents the decoder to estimate the channel state accurately., Nous étudions le problème du masquage et de l'amplification de l'état d'un canal en utilisant les outils de la coordination empirique. L'encodeur observe l'état du canal de manière causale et met en oeuvre un schéma de codage afin de contrôler la divulgation de l'état du canal tout en transmettant un débit d'information. Nous démontrons que le problème de la coordination empirique fournit un cadre naturel pour l'étude de la transmission fiable et de l'amplification ou du masquage de l'état de canal. Nous caractérisons la région réalisable de débit-divulgation-coordination lorsque l'observation de l'encodeur est causale. Nous exploitons ce résultat pour résoudre un jeu à somme nulle d'estimation de l'état du canal dans lequel l'encodeur essaie d'empêcher le décodeur d'estimer l'état du canal avec précision.

International audience; The vector-valued extension of the famous Witsen-hausen counterexample setup is studied where the first decision maker (DM1) non-causally knows and encodes the iid state sequence and the second decision maker (DM2) causally estimates the interim state. The coding scheme is transferred from the finite alphabet coordination problem for which it is proved to be optimal. The extension to the Gaussian setup is based on a non-standard weak typicality approach and requires a careful average estimation error analysis since the interim state is estimated by the decoder. Next, we provide a choice of auxiliary random variables that outperforms any linear scheme. The optimal scheme remains unknown.

We revisit the problems of state masking and state amplification through the lens of empirical coordination by considering a state-dependent channel in which the encoder has causal and strictly causal state knowledge. We show that the problem of empirical coordination provides a natural framework in which to jointly study the problems of reliable communication, state masking, and state amplification. We characterize the regions of rate-equivocation-coordination trade-offs for several channel models with causal and strictly causal state knowledge. We introduce the notion of "core of the receiver's knowledge" to capture what the decoder can infer about all the signals involved in the model. We exploit this result to solve a channel state estimation zero-sum game in which the encoder prevents the decoder to estimate the channel state accurately.

International audience; In this work, necessary and sufficient conditions for empirical coordination of vector-valued Witsenhausen counterexample two terminal setups with non-classical information structure are derived. Vector-valued processing allows to involve coding in the design of the control strategies. Optimal characterizations are obtained for the non-causal encoding and causal decoding case as well as causal encoding and non-causal decoding case. Necessary and sufficient conditions are provided for the case with both non-causal encoding and decoding. The feasible set of target distributions can serve as optimization domain for characterizing the optimal average cost, in particular using Witsenhausen's cost function.

International audience; We investigate the coordination of autonomous devices with strategic and non-aligned utility functions. The encoder and the decoder of the point-to-point network choose their coding strategy in order to maximize their own utility function. This paper extends our previous results on strategic coordination by considering state information at the decoder. We study the connexion between Wyner-Ziv source coding and the problem of Bayesian persuasion in the economics literature.

This paper investigates the strategic coordination of autonomous devices endowed with non-aligned utility functions for a source-channel point-to-point scenario. This problem is related to Game Theory, more precisely to " Bayesian Persuasion " investigated in [1]. The objectif of the encoder is not to transmit information, but to control the posterior beliefs of the decoder, in order it chooses the most favorable action. This work was presented in part at the 54th Allerton Conference 2016 [2]., Cet article s'intéresse à la coordination stratégique que des appareils autonomes peuvent mettre en oeuvre. Nous considérons le problème source-canal point-à-point lorsque l'encodeur et le décodeur sont munis de fonction d'utilité non-alignées. Ce problème fait appel aux outils de la Théorie des Jeux, notamment à la " Persuasion Bayésienne" étudiée dans [1]. L'objectif de l'encodeur n'est plus de transmettre de l'information mais de contrôler les croyance du décodeur afin de l'amener à choisir l'action la plus favorable. Ce travail a été présenté en partie, à la 54ème conférence d'Allerton en 2016 [2].

https://cloud.ensea.fr/index.php/s/X9e5x8EzJfI7I4Q