Shannon meets Myerson
Information extraction from a strategic sender
A. S. Vora (TU Delft - Team Peyman Mohajerin Esfahani)
Ankur A. Kulkarni (Indian Institute of Technology Bombay)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
We study a setting where a receiver must design a questionnaire to recover a sequence of symbols known to a 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 while communicating with a strategic sender. 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, non-cooperative regime of communication involving a strategic sender.