Bayesian persuasion: Reduced form approach

We introduce reduced form representations of Bayesian persuasion problems where the variables are the probabilities that the receiver takes each of her actions. These are simpler objects than, say, the joint distribution over states and actions in the obedience formulation of the persuasion problem. This can make a difference in computational and analytical tractability, which we illustrate with two applications. The first shows that with quadratic receiver payoffs, the worst-case complexity scales with the number of actions and not the number of states. If |A| and |S| denote the number of actions and states respectively, the worst case complexity of the obedience formulation is O(|A||S|(|S|+|A|)1.5L) where L is its input size. The worst-case complexity of the reduced form representation is O(|A|2.5L). In the second application, the reduced form leads to a simple greedy algorithm to determine the maximum value a sender can achieve in any cheap talk equilibrium.