eduzhai > Applied Sciences > Engineering >

Information Extraction from a Strategic Sender The Zero Error Case

  • Save

... pages left unread,continue reading

Document pages: 23 pages

Abstract: We introduce a setting where a receiver aims to perfectly recover a sourceknown privately to a textit{strategic} sender over a possibly noisy channel.The sender is endowed with a utility function and sends signals to the receiverwith the aim of maximizing this utility. Due to the strategic nature of thesender not all the transmitted information is truthful, which leads toquestion: how much true information can be recovered by the receiver from sucha sender? We study this question in this paper. We pose the problem as a gamebetween the sender and receiver, where the receiver tries to maximize thenumber of sequences that can be recovered perfectly and the sender maximizesits utility. We show that, in spite of the sender being strategic and thepresence of noise in the channel, there is a strategy for the receiver by whichit can perfectly recover an textit{exponentially} large number of sequences.Our analysis leads to the notion of the textit{information extractioncapacity} of the sender which quantifies the growth rate of the number ofrecovered sequences with blocklength, in the presence of a noiseless channel.We identify cases where this capacity is equal to its theoretical maximum, andalso when it is strictly less than maximum. In the latter case, we show thatthe capacity is sandwiched between the independence number and the Shannoncapacity of a suitably defined graph. These results lead to an exactcharacterization of the information extraction capacity in large number ofcases. We show that in the presence of a noisy channel, the rate of informationextraction achieved by the receiver is the minimum of the zero-error capacityof the channel and the information extraction capacity of the sender. Ouranalysis leads to insights into a novel regime of communication involvingstrategic agents.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...