Algorithmic Persuasion with Evidence

ACM Transactions on Economics and Computation, vol. 12, pp. 1–34

Abstract

In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action (e.g., hire a job candidate, or convict a defendant). The sender’s utility depends solely on whether the receiver takes the action. The receiver’s utility depends on both the action and the sender’s private information. We study three natural variations. First, we consider the problem of computing an equilibrium of the game without commitment power. Second, we consider a persuasion variant, where the sender commits to a signaling scheme and the receiver, after seeing the evidence, takes the action or not. Third, we study a delegation variant, where the receiver first commits to taking the action if being presented certain evidence, and the sender presents evidence to maximize the probability the action is taken. We study these variants through the computational lens, and give hardness results, optimal approximation algorithms, and polynomial-time algorithms for special cases. Among our results is 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 in algorithmic economics.

Authors 3

1. Martin Hoefer Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

2. Pasin Manurangsi

   Google (United States)

   Affiliation as printed

   Google Inc, Mountain View, United States

3. Alexandros Psomas

   Purdue University West Lafayette

   Affiliation as printed

   Purdue University, West Lafayette, United States