The Taub Faculty of Computer Science Events and Talks

Bayesian persuasion, as introduced by Kamenica and Gentzkow in 2011, is the study of information sharing policies among strategic agents. A prime example is signaling in online ad auctions: what information should a platform signal to an advertiser regarding a user when selling the opportunity to advertise to her? Practical considerations such as preventing discrimination, protecting privacy or acknowledging limited attention of the information receiver impose constraints on information sharing. Despite their importance in real-life applications, such constraints are not usually taken into account in Bayesian persuasion literature. In our work, we propose and analyze a simple way to mathematically model such constraints as restrictions on Receiver's admissible posterior beliefs. We consider two families of constraints - ex ante and ex post, where the latter limits each instance of Sender-Receiver communication, while the former more general family can also pose restrictions in expectation. For both families, we show existence of a simple optimal signaling scheme in the sense of a small number of signals; our bounds for signal numbers are tight. We then provide an additive bi-criteria FPTAS for an optimal constrained signaling scheme when the number of states of nature is constant; we improve the approximation to single-criteria under a Slater-like regularity condition. The FPTAS holds under standard assumptions, and more relaxed assumptions yield a PTAS. Finally, we bound the ratio between Sender's optimal utility under convex ex ante constraints and the corresponding ex post constraints. We demonstrate how this bound can be applied to find an approximately welfare-maximizing constrained signaling scheme in ad auctions.