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. ... Read more

We study a setting where a detector wishes to detect and deter adversarial manipulation in an electronic voting machine. An adversary tries to win the election by tampering the votes while obfuscating its manipulation. We pose this problem as a game between the detector and the adversary and characterize the equilibrium payoffs for the players and the asymptotic nature of these payoffs. We find that if the detector is too cautious, then in equilibrium the adversary wins with a probability higher than its prior probability of winning. We derive an expression for the deterrence threshold, i.e., the minimum level of false-alarm that the detector should endure so that the adversary is not any better off by the manipulation. With this, asymptotically, the detector can ensure that the probability of missed-detection becomes zero by appropriately adjusting the rate of decay of probability of false-alarm. But if this rate of decay is too 'fast', then the adversary can get an arbitrarily high probability of winning in spite of having a vanishing prior probability of winning. We then extend the results to a setting where the detector has incomplete information about the adversary. ... Read more