Algorithmic Persuasion with Evidence

We consider optimization problems faced by a sender and a receiver in a game of persuasion with evidence. The sender wishes to persuade the receiver to take one of two actions by presenting evidence. The sender’s utility depends solely on the action taken, while the receiver’s utility depends on both the action as well as the sender’s private information. We study two natural variations. The first is verification, where the sender commits to a signaling scheme and then the receiver takes an action after seeing the evidence. The second is delegation, where the receiver first commits to taking a certain action if being presented certain evidence, and then the sender presents evidence to maximize the probability that her favorite action is taken. We study these problems through the computational lens, and give hardness results, optimal approximation algorithms, as well as efficient algorithms for special cases. In particular, we provide an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm for a natural problem in algorithmic economics.

• Algorithms and Theory

• Economics and Electronic Commerce