Information Extraction from a Strategic Sender: The Zero Error 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 the 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 show that the information extraction capacity generalizes the Shannon capacity of a graph. While this implies that computing this quantity is hard in general, we derive lower and upper bounds that allow us to approximate this capacity. The lower bound is in terms of an optimization problem and the upper bound is in terms of the Shannon capacity of an appropriate graph. These results also lead to an exact characterization of the information extraction capacity in a 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.