Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

National Conference on Communications

Zero-Error Communication with an Influencer

Reema Deori, Ankur A. Kulkarni

Published Feb 23, 2023• 1 citation
Publisher

Abstract

We study a problem of communication between an influencer and a receiver where the influencer has access to a sequence of facts that the receiver is interested in knowing with zero error. The influencer sends a signal to the receiver for every such sequence and it obtains a utility that is a function of the true sequence and the sequence deduced by the receiver, and incurs a cost that is a function of the true sequence and the signal sent. The influencer may choose to induce ambiguity by sending a common signal for multiple sequences, and by performing coding. The resulting problem is studied as a Stackelberg game and operational strategies are obtained as the equilibrium of this game. Our main contribution is the study of informativeness – the minimum amount of correct information that the receiver can obtain in any such equilibrium. We characterize informativeness as the limiting value of the list chromatic number of a sequence of graphs and obtain single-letter bounds on it. Our results show that the presence of cost increases informativeness and when a certain single-letter condition holds, there is no benefit to coding in the costless case.

DOI
10.1109/ncc56989.2023.10068030

Related papers

Information Extraction from a Strategic Sender: The Zero Error Case.

Anuj S. Vora, Ankur A. Kulkarni

We introduce a setting where a receiver aims to perfectly recover a source known privately to a \textit{strategic} sender over a possibly noisy channel. The sender is endowed with a utility function and sends signals to the receiver with the aim of maximizing this utility. Due to the strategic nature of the sender not all the transmitted information is truthful, which leads to question: how much true information can be recovered by the receiver from such a sender? We study this question in this paper. We pose the problem as a game between the sender and receiver, where the receiver tries to maximize the number of sequences that can be recovered perfectly and the sender maximizes its utility. We show that, in spite of the sender being strategic and the presence of noise in the channel, there is a strategy for the receiver by which it can perfectly recover an \textit{exponentially} large number of sequences. Our analysis leads to the notion of the \textit{information extraction capacity} of the sender which quantifies the growth rate of the number of recovered sequences with blocklength, in the presence of a noiseless channel. We identify cases where this capacity is equal to its theoretical maximum, and also when it is strictly less than maximum. In the latter case, we show that the capacity is sandwiched between the independence number and the Shannon capacity of a suitably defined graph. These results lead to an exact characterization of the information extraction capacity in large number of cases. We show that in the presence of a noisy channel, the rate of information extraction achieved by the receiver is the minimum of the zero-error capacity of the channel and the information extraction capacity of the sender. Our analysis leads to insights into a novel regime of communication involving strategic agents.

•Jun 18, 2020•4 citations

On the structure of equilibrium strategies in dynamic Gaussian signaling games

Muhammed O. Sayin, Emrah Akyol, Tamer Basar

This paper analyzes a finite horizon dynamic signaling game motivated by the well-known strategic information transmission problems in economics. The mathematical model involves information transmission between two agents, a sender who observes two Gaussian processes, state and bias, and a receiver who takes an action based on the received message from the sender. The players incur quadratic instantaneous costs as functions of the state, bias and action variables. Our particular focus is on the Stackelberg equilibrium, which corresponds to information disclosure and Bayesian persuasion problems in economics. Prior work solved the static game, and showed that the Stackelberg equilibrium is achieved by pure strategies that are linear functions of the state and the bias variables. The main focus of this work is on the dynamic (multi-stage) setting, where we show that the existence of a pure strategy Stackelberg equilibrium, within the set of linear strategies, depends on the problem parameters. Surprisingly, for most problem parameters, a pure linear strategy does not achieve the Stackelberg equilibrium which implies the existence of a trade-off between exploiting and revealing information, which was also encountered in several other asymmetric information games.

arXiv:1607.02864•The proceedings of the IEEE Conference on Control Applications/The proceedings of the ... IEEE Conference on Control Applications•Sep 1, 2016•2 citations

Quadratic Privacy-Signaling Games and Payoff Dominant Equilibria

Ertan Kazıklı, Sinan Gezici, Serdar Yüksel

We consider a privacy-signaling game problem in which a transmitter with privacy concerns and a receiver, which does not pay attention to these privacy concerns, communicate. In this communication scenario, the transmitter observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter constructs its message based on these random variables with the aim to hide one of them and convey the other one. In contrast, the objective of the receiver is to accurately estimate both of the random variables so as to gather as much information as possible. These conflicting objectives are analyzed in a game theoretic framework where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg equilibria. We show that a payoff dominant (i.e., most desirable for both players) Nash equilibrium is attained by affine policies and we explicitly characterize these policies. In addition, the strategies at the characterized Nash equilibrium is shown to form also a Stackelberg equilibrium. Furthermore, we show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setup. We also revisit the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the sender. We fully characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•3 citations

Signaling and information games with subjective costs or priors and privacy constraints

Ertan Kazıklı

We investigate signaling game problems where an encoder and a decoder with misaligned objectives communicate. We consider a variety of setups involving cost criterion mismatch, prior mismatch and a particular application to privacy problems. We also consider both Nash and Stackelberg solution concepts. First, we extend the classical results on the scalar cheap talk problem which is intro-duced by Crawford and Sobel. In prior work, it is shown that the encoder must employ a quantization policy under any Nash equilibrium for arbitrary source distributions. We specifically consider sources with a log-concave density and in-vestigate properties of equilibria. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. If the source has semi-unbounded support, then there may exist a finite upper bound on the number of bins in equilibrium depending on certain explicit condi-tions. Moreover, we show that an equilibrium with more bins is more informative by showing that the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove that if the encoder and decoder iteratively compute their best responses starting from a given number of bins, then the resulting policies converge to the unique equilibrium with the corresponding number of bins. Second, we model a privacy problem as a signaling game between an encoder and a decoder. Given a pair of correlated observations modeled as jointly Gaus-sian random vectors, the encoder aims to hide one of them and convey the other one to the decoder. In contrast, the aim of the decoder is to accurately estimate both of the random vectors. For the resulting signaling game problem, we show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. Moreover, we formulate the information bottleneck problem within our Stackelberg frame-work under the mean squared error criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the encoder. We show that the Gaussian information bottleneck problem admits a linear solution which is explicitly characterized. Third, we investigate communications through a Gaussian noise channel be-tween an encoder and a decoder with prior mismatch. Although they consider the same cost function, the induced expected costs as a map of their policies are misaligned due to their prior mismatch. We analyze the resulting signaling game problem under Stackelberg equilibria. We first investigate robustness of equilibria and show that the Stackelberg equilibrium cost of the encoder is upper semi continuous, under the Wasserstein metric, as the encoder’s prior approaches the decoder’s prior, and it is also lower semi continuous with Gaussian priors. In addition, we show that the optimality of affine policies for Gaussian signaling no longer holds under prior mismatch. Furthermore, we provide conditions under which there exist informative equilibria under an affine policy restriction. Fourth, we extend Crawford and Sobel’s formulation to a multidimensional source setting. We first provide a set of geometry conditions that decoder actions at a Nash equilibrium has to satisfy considering any multidimensional source. Then, we consider independent and identically distributed sources and charac-terize necessary and sufficient conditions under which an informative linear equi-librium exists. We observe that these conditions involve the bias vector that leads to misaligned costs. Depending on certain conditions on the bias vector, the existence of linear equilibria may require sources with a Gaussian or a sym-metric density. Moreover, we provide a rate-distortion theoretic formulation of the cheap talk problem and obtain achievable rate and distortion pairs for the Gaussian case. Finally, in a communication theoretic setup, we consider modulation classi-fication and symbol decoding problems jointly and propose optimal strategies under various settings. The aim is to decode a sequence of received signals with an unknown modulation scheme. First, the prior probabilities of the candidate modulation schemes are assumed to be known and a formulation is proposed under the Bayesian framework. Second, we address the case when the prior prob-abilities of the candidate modulation schemes are unknown, and provide a method under the minimax framework. Numerical simulations show that the proposed techniques improve the performance under the employed criteria compared to the conventional techniques in a variety of system configurations.

•Aug 1, 2021•0 citations

The economics of information transmission

Penélope Hernàndez Rojas, Olivier Gossner, Abraham Neyman

It is a well known phenomenon that communication between a group of players affects the set of equilibria of a repeated game. This communication can be costly. Its cost may be measured in terms of complexity, or payoffs. In particular, a payoff cost of communication occurs when players communicate through their actions, and one is interested in characterizing the optimal communication. We study a class of games that models the communication cost of online coordination. For example: A sequence X = (X(t)) of zeroes and ones is chosen at random, and announced to a player, the seer, but not to his teammate, the follower. A repeated game then proceeds in which the follower and the seer choose actions Y (t) and Z(t) in {0, 1} at stage t, and their (common) stage payoff is 1 whenever X(t) = Y (t) = Z(t). We address the question of the optimal communication level from the seer to the follower in order to maximize payoffs. We characterize this level using the notion of entropy, and provide construction of optimal strategies for the team: the seer and the follower. In particular, we prove that against a family of i.i.d. random variables (1/2, 1/2), the maximum expected payoff v to the team is the solution of the equation H(x) + log(3) (1 - x) = 1; where H is the entropy function and log is taken in basis 2. Moreover, we prove the existence of pure strategies of the prophet and the seer that guarantee v against all sequences X = X(t). Hence, the zero-sum game in which player I is the Team (no correlation is allowed between its members), player II is the opponent, and the payoff to I is as above, has a value, and this equals v. Our result has direct implications for repeated games played by finite automata, or by players with bounded recall.

•Jan 1, 2002•0 citations

Quantum Advantage in Zero-Error Function Computation With Side Information

Ruoyu Meng, Aditya Ramamoorthy

We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources $X,Y$ with joint p.m.f. $p_{XY}(\cdot, \cdot)$. Bob wants to calculate $f(X,Y)$ with zero error. Alice encodes $m$-length blocks $(m \geq 1)$ of her observations to Bob over error-free channels, which can be classical or quantum. We consider two classical settings. (i) Alice communicates via a fixed length code (FLC), and (ii) Alice communicates via a variable length code (VLC). In the FLC scenario, the minimum communication rate depends on the asymptotic growth of the chromatic number of an appropriately defined $m$-instance ``confusion graph'' $G^{(m)}$. In the VLC scenario, the corresponding rate is characterized by the asymptotics of the chromatic entropy of $G^{(m)}$. %and has single-letter characterization in terms of Körner's graph entropy if $G^{(m)}$ is $m$-times graph OR product. In the quantum setting, we only consider fixed length codes; the corresponding rate depends on the asymptotic growth of the orthogonal rank of the complement of $G^{(m)}$. The behavior of the communication rates depends critically on $G^{(m)}$, which is shown to be sandwiched between $G^{\boxtimes m}$ ($m$-times strong product) and $G^{\lor m}$ ($m$-times OR product) respectively. Our work presents necessary and sufficient conditions on the function $f(\cdot, \cdot)$ and joint p.m.f. $p_{XY}(\cdot,\cdot)$ such that $G^{(m)}$ equals either $G^{\boxtimes m}$ or $G^{\lor m}$. Our work explores the multitude of possible behaviors of the quantum and classical (FLC/VLC) rates in the single-instance case and the asymptotic (in $m$) case for several classes of confusion graphs.

arXiv:2402.01549•IEEE Transactions on Information Theory•Jul 30, 2025•0 citations
We study a problem of communication between an influencer and a receiver where the influencer has access to a sequence of facts that the receiver is interested in knowing with zero error. The influencer sends a signal to the receiver for every such sequence and it obtains a utility that is a function of the true sequence and the sequence deduced by the receiver, and incurs a cost that is a function of the true sequence and the signal sent. The influencer may choose to induce ambiguity by sending a common signal for multiple sequences, and by performing coding. The resulting problem is studied as a Stackelberg game and operational strategies are obtained as the equilibrium of this game. Our main contribution is the study of informativeness – the minimum amount of correct information that the receiver can obtain in any such equilibrium. We characterize informativeness as the limiting value of the list chromatic number of a sequence of graphs and obtain single-letter bounds on it. Our results show that the presence of cost increases informativeness and when a certain single-letter condition holds, there is no benefit to coding in the costless case.
We introduce a setting where a receiver aims to perfectly recover a source known privately to a \textit{strategic} sender over a possibly noisy channel. The sender is endowed with a utility function and sends signals to the receiver with the aim of maximizing this utility. Due to the strategic nature of the sender not all the transmitted information is truthful, which leads to question: how much true information can be recovered by the receiver from such a sender? We study this question in this paper. We pose the problem as a game between the sender and receiver, where the receiver tries to maximize the number of sequences that can be recovered perfectly and the sender maximizes its utility. We show that, in spite of the sender being strategic and the presence of noise in the channel, there is a strategy for the receiver by which it can perfectly recover an \textit{exponentially} large number of sequences. Our analysis leads to the notion of the \textit{information extraction capacity} of the sender which quantifies the growth rate of the number of recovered sequences with blocklength, in the presence of a noiseless channel. We identify cases where this capacity is equal to its theoretical maximum, and also when it is strictly less than maximum. In the latter case, we show that the capacity is sandwiched between the independence number and the Shannon capacity of a suitably defined graph. These results lead to an exact characterization of the information extraction capacity in large number of cases. We show that in the presence of a noisy channel, the rate of information extraction achieved by the receiver is the minimum of the zero-error capacity of the channel and the information extraction capacity of the sender. Our analysis leads to insights into a novel regime of communication involving strategic agents.
This paper analyzes a finite horizon dynamic signaling game motivated by the well-known strategic information transmission problems in economics. The mathematical model involves information transmission between two agents, a sender who observes two Gaussian processes, state and bias, and a receiver who takes an action based on the received message from the sender. The players incur quadratic instantaneous costs as functions of the state, bias and action variables. Our particular focus is on the Stackelberg equilibrium, which corresponds to information disclosure and Bayesian persuasion problems in economics. Prior work solved the static game, and showed that the Stackelberg equilibrium is achieved by pure strategies that are linear functions of the state and the bias variables. The main focus of this work is on the dynamic (multi-stage) setting, where we show that the existence of a pure strategy Stackelberg equilibrium, within the set of linear strategies, depends on the problem parameters. Surprisingly, for most problem parameters, a pure linear strategy does not achieve the Stackelberg equilibrium which implies the existence of a trade-off between exploiting and revealing information, which was also encountered in several other asymmetric information games.
We consider a privacy-signaling game problem in which a transmitter with privacy concerns and a receiver, which does not pay attention to these privacy concerns, communicate. In this communication scenario, the transmitter observes a pair of correlated random variables which are modeled as jointly Gaussian. The transmitter constructs its message based on these random variables with the aim to hide one of them and convey the other one. In contrast, the objective of the receiver is to accurately estimate both of the random variables so as to gather as much information as possible. These conflicting objectives are analyzed in a game theoretic framework where depending on the commitment conditions (of the sender), we consider Nash or Stackelberg equilibria. We show that a payoff dominant (i.e., most desirable for both players) Nash equilibrium is attained by affine policies and we explicitly characterize these policies. In addition, the strategies at the characterized Nash equilibrium is shown to form also a Stackelberg equilibrium. Furthermore, we show that there always exists an informative Stackelberg equilibrium for the multidimensional parameter setup. We also revisit the information bottleneck problem within our Stackelberg framework under the mean squared error distortion criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the sender. We fully characterize the Stackelberg equilibria under certain conditions and when these conditions are not met we establish the existence of informative equilibria.
We investigate signaling game problems where an encoder and a decoder with misaligned objectives communicate. We consider a variety of setups involving cost criterion mismatch, prior mismatch and a particular application to privacy problems. We also consider both Nash and Stackelberg solution concepts. First, we extend the classical results on the scalar cheap talk problem which is intro-duced by Crawford and Sobel. In prior work, it is shown that the encoder must employ a quantization policy under any Nash equilibrium for arbitrary source distributions. We specifically consider sources with a log-concave density and in-vestigate properties of equilibria. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. If the source has semi-unbounded support, then there may exist a finite upper bound on the number of bins in equilibrium depending on certain explicit condi-tions. Moreover, we show that an equilibrium with more bins is more informative by showing that the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove that if the encoder and decoder iteratively compute their best responses starting from a given number of bins, then the resulting policies converge to the unique equilibrium with the corresponding number of bins. Second, we model a privacy problem as a signaling game between an encoder and a decoder. Given a pair of correlated observations modeled as jointly Gaus-sian random vectors, the encoder aims to hide one of them and convey the other one to the decoder. In contrast, the aim of the decoder is to accurately estimate both of the random vectors. For the resulting signaling game problem, we show that a payoff dominant Nash equilibrium among all admissible policies is attained by a set of explicitly characterized linear policies. We also show that a payoff dominant Nash equilibrium coincides with a Stackelberg equilibrium. Moreover, we formulate the information bottleneck problem within our Stackelberg frame-work under the mean squared error criterion where the information bottleneck setup has a further restriction that only one of the parameters is observed at the encoder. We show that the Gaussian information bottleneck problem admits a linear solution which is explicitly characterized. Third, we investigate communications through a Gaussian noise channel be-tween an encoder and a decoder with prior mismatch. Although they consider the same cost function, the induced expected costs as a map of their policies are misaligned due to their prior mismatch. We analyze the resulting signaling game problem under Stackelberg equilibria. We first investigate robustness of equilibria and show that the Stackelberg equilibrium cost of the encoder is upper semi continuous, under the Wasserstein metric, as the encoder’s prior approaches the decoder’s prior, and it is also lower semi continuous with Gaussian priors. In addition, we show that the optimality of affine policies for Gaussian signaling no longer holds under prior mismatch. Furthermore, we provide conditions under which there exist informative equilibria under an affine policy restriction. Fourth, we extend Crawford and Sobel’s formulation to a multidimensional source setting. We first provide a set of geometry conditions that decoder actions at a Nash equilibrium has to satisfy considering any multidimensional source. Then, we consider independent and identically distributed sources and charac-terize necessary and sufficient conditions under which an informative linear equi-librium exists. We observe that these conditions involve the bias vector that leads to misaligned costs. Depending on certain conditions on the bias vector, the existence of linear equilibria may require sources with a Gaussian or a sym-metric density. Moreover, we provide a rate-distortion theoretic formulation of the cheap talk problem and obtain achievable rate and distortion pairs for the Gaussian case. Finally, in a communication theoretic setup, we consider modulation classi-fication and symbol decoding problems jointly and propose optimal strategies under various settings. The aim is to decode a sequence of received signals with an unknown modulation scheme. First, the prior probabilities of the candidate modulation schemes are assumed to be known and a formulation is proposed under the Bayesian framework. Second, we address the case when the prior prob-abilities of the candidate modulation schemes are unknown, and provide a method under the minimax framework. Numerical simulations show that the proposed techniques improve the performance under the employed criteria compared to the conventional techniques in a variety of system configurations.
It is a well known phenomenon that communication between a group of players affects the set of equilibria of a repeated game. This communication can be costly. Its cost may be measured in terms of complexity, or payoffs. In particular, a payoff cost of communication occurs when players communicate through their actions, and one is interested in characterizing the optimal communication. We study a class of games that models the communication cost of online coordination. For example: A sequence X = (X(t)) of zeroes and ones is chosen at random, and announced to a player, the seer, but not to his teammate, the follower. A repeated game then proceeds in which the follower and the seer choose actions Y (t) and Z(t) in {0, 1} at stage t, and their (common) stage payoff is 1 whenever X(t) = Y (t) = Z(t). We address the question of the optimal communication level from the seer to the follower in order to maximize payoffs. We characterize this level using the notion of entropy, and provide construction of optimal strategies for the team: the seer and the follower. In particular, we prove that against a family of i.i.d. random variables (1/2, 1/2), the maximum expected payoff v to the team is the solution of the equation H(x) + log(3) (1 - x) = 1; where H is the entropy function and log is taken in basis 2. Moreover, we prove the existence of pure strategies of the prophet and the seer that guarantee v against all sequences X = X(t). Hence, the zero-sum game in which player I is the Team (no correlation is allowed between its members), player II is the opponent, and the payoff to I is as above, has a value, and this equals v. Our result has direct implications for repeated games played by finite automata, or by players with bounded recall.
We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources X,YX,YX,Y with joint p.m.f. pXY(⋅,⋅)p_{XY}(\cdot, \cdot)pXY​(⋅,⋅). Bob wants to calculate f(X,Y)f(X,Y)f(X,Y) with zero error. Alice encodes mmm-length blocks (m≥1)(m \geq 1)(m≥1) of her observations to Bob over error-free channels, which can be classical or quantum. We consider two classical settings. (i) Alice communicates via a fixed length code (FLC), and (ii) Alice communicates via a variable length code (VLC). In the FLC scenario, the minimum communication rate depends on the asymptotic growth of the chromatic number of an appropriately defined mmm-instance ``confusion graph'' G(m)G^{(m)}G(m). In the VLC scenario, the corresponding rate is characterized by the asymptotics of the chromatic entropy of G(m)G^{(m)}G(m). %and has single-letter characterization in terms of Körner's graph entropy if G(m)G^{(m)}G(m) is mmm-times graph OR product. In the quantum setting, we only consider fixed length codes; the corresponding rate depends on the asymptotic growth of the orthogonal rank of the complement of G(m)G^{(m)}G(m). The behavior of the communication rates depends critically on G(m)G^{(m)}G(m), which is shown to be sandwiched between G⊠mG^{\boxtimes m}G⊠m (mmm-times strong product) and G∨mG^{\lor m}G∨m (mmm-times OR product) respectively. Our work presents necessary and sufficient conditions on the function f(⋅,⋅)f(\cdot, \cdot)f(⋅,⋅) and joint p.m.f. pXY(⋅,⋅)p_{XY}(\cdot,\cdot)pXY​(⋅,⋅) such that G(m)G^{(m)}G(m) equals either G⊠mG^{\boxtimes m}G⊠m or G∨mG^{\lor m}G∨m. Our work explores the multitude of possible behaviors of the quantum and classical (FLC/VLC) rates in the single-instance case and the asymptotic (in mmm) case for several classes of confusion graphs.