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

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

Anuj S. Vora, Ankur A. Kulkarni

Published Jun 18, 2020• 5 citations
OpenAlex

Abstract

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.

Related papers

Information Extraction from a Strategic Sender over a Noisy Channel

Anuj S. Vora, Ankur A. Kulkarni

We consider a setting where a receiver tries to perfectly recover a source signal privately known to a sender who can send messages via a noisy channel. However, the sender is compromised and may have an incentive to lie about its information. We formulate the problem as a game between the sender and the receiver and show that there is a strategy for the receiver in which it can recover an exponential number of signals. We define a notion of a sender graph and the information extraction capacity of the sender which quantifies the maximum amount of information that can be extracted from the sender. We also show that the rate of information extraction is given by the minimum of the information extraction capacity of the sender and the zero-error capacity of the noisy channel.

IEEE Conference on Decision and Control (CDC)•Dec 14, 2020•19 citations

Shannon meets Myerson: Information Extraction from a Strategic Sender

Anuj S. Vora, Ankur A. Kulkarni

We study a setting where a receiver must design a questionnaire to recover a sequence of symbols known to strategic sender, whose utility may not be incentive compatible. We allow the receiver the possibility of selecting the alternatives presented in the questionnaire, and thereby linking decisions across the components of the sequence. We show that, despite the strategic sender and the noise in the channel, the receiver can recover exponentially many sequences, but also that exponentially many sequences are unrecoverable even by the best strategy. We define the growth rate of the number of recovered sequences as the information extraction capacity. A generalization of the Shannon capacity, it characterizes the optimal amount of communication resources required. We derive bounds leading to an exact evaluation of the information extraction capacity in many cases. Our results form the building blocks of a novel, noncooperative regime of communication involving a strategic sender.

arXiv:2006.10641•Jun 18, 2020•0 citations

Zero-Error Communication with an Influencer

Reema Deori, Ankur A. Kulkarni

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.

National Conference on Communications•Feb 23, 2023•1 citation

Zero-Error Channel Capacity and Simulation Assisted by Non-Local Correlations

Toby S. Cubitt, Debbie Leung, William Matthews +1 more

The theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. Finally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.

arXiv:1003.3195•IEEE Transactions on Information Theory•Aug 1, 2011•70 citations

Zero-Error Channel Capacity and Simulation Assisted by Non-Local Correlations

Toby S. Cubitt, Debbie Leung, Matthews, W +1 more

The theory of zero-error communication is re-examined \nin the broader setting of using one classical channel to \nsimulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. \nIn both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. \nFinally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.

•Jan 1, 2011•58 citations

Gaussian cheap talk game with quadratic cost functions: When herding between strategic senders is a virtue

Farhad Farokhi, Andre M. H. Teixeira, Cédric Langbort

We consider a Gaussian cheap talk game with quadratic cost functions. The cost function of the receiver is equal to the estimation error variance, however, the cost function of each senders contains an extra term which is captured by its private information. Following the cheap talk literature, we model this problem as a game with asymmetric information. We start by the single sender case in which the receiver also has access to a noisy but honest side information in addition to the message transmitted by a strategic sender. We generalize this setup to multiple sender case. For the multiple sender case, we observe that if the senders are not herding (i.e., copying each other policies), the quality of the receiver's estimation degrades rapidly as the number of senders increases.

arXiv:1402.4031•Proceedings of the ... American Control Conference/Proceedings of the American Control Conference•Jun 1, 2014•12 citations
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.
We consider a setting where a receiver tries to perfectly recover a source signal privately known to a sender who can send messages via a noisy channel. However, the sender is compromised and may have an incentive to lie about its information. We formulate the problem as a game between the sender and the receiver and show that there is a strategy for the receiver in which it can recover an exponential number of signals. We define a notion of a sender graph and the information extraction capacity of the sender which quantifies the maximum amount of information that can be extracted from the sender. We also show that the rate of information extraction is given by the minimum of the information extraction capacity of the sender and the zero-error capacity of the noisy channel.
We study a setting where a receiver must design a questionnaire to recover a sequence of symbols known to strategic sender, whose utility may not be incentive compatible. We allow the receiver the possibility of selecting the alternatives presented in the questionnaire, and thereby linking decisions across the components of the sequence. We show that, despite the strategic sender and the noise in the channel, the receiver can recover exponentially many sequences, but also that exponentially many sequences are unrecoverable even by the best strategy. We define the growth rate of the number of recovered sequences as the information extraction capacity. A generalization of the Shannon capacity, it characterizes the optimal amount of communication resources required. We derive bounds leading to an exact evaluation of the information extraction capacity in many cases. Our results form the building blocks of a novel, noncooperative regime of communication involving a strategic sender.
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.
The theory of zero-error communication is re-examined in the broader setting of using one classical channel to simulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. In both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. Finally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.
The theory of zero-error communication is re-examined \nin the broader setting of using one classical channel to \nsimulate another exactly in the presence of various classes of nonsignalling correlations between sender and receiver i.e., shared randomness, shared entanglement and arbitrary nonsignalling correlations. When the channel being simulated is noiseless, this is zero-error coding assisted by correlations. When the resource channel is noiseless, it is the reverse problem of simulating a noisy channel exactly by a noiseless one, assisted by correlations. \nIn both cases, separations between the power of the different classes of assisting correlations are exhibited for finite block lengths. The most striking result here is that entanglement can assist in zero-error communication. In the large block length limit, shared randomness is shown to be just as powerful as arbitrary nonsignalling correlations for exact simulation, but not for asymptotic zero-error coding. For assistance by arbitrary nonsignalling correlations, linear programming formulas for the asymptotic capacity and simulation rates are derived, the former being equal (for channels with nonzero unassisted capacity) to the feedback-assisted zero-error capacity derived by Shannon. \nFinally, a kind of reversibility between nonsignalling-assisted zero-error capacity and exact simulation is observed, mirroring the usual reverse Shannon theorem.
We consider a Gaussian cheap talk game with quadratic cost functions. The cost function of the receiver is equal to the estimation error variance, however, the cost function of each senders contains an extra term which is captured by its private information. Following the cheap talk literature, we model this problem as a game with asymmetric information. We start by the single sender case in which the receiver also has access to a noisy but honest side information in addition to the message transmitted by a strategic sender. We generalize this setup to multiple sender case. For the multiple sender case, we observe that if the senders are not herding (i.e., copying each other policies), the quality of the receiver's estimation degrades rapidly as the number of senders increases.