Leakage-Robust Bayesian Persuasion

This paper introduces leakage-robust Bayesian persuasion. Situated between public Bayesian persuasion [KG11] (and its multi-receiver variants [CCG23, Xu20]) and private Bayesian persuasion [AB19], it considers settings where one or more signals sent privately by a sender to receivers may be leaked. We design leakage-robust Bayesian persuasion schemes and quantify the price of robustness using two formalisms: - The first notion, $k$-worst-case persuasiveness, requires a signaling scheme to remain persuasive whenever each receiver observes at most $k$ leaked signals from other receivers. Relative to optimal private persuasion, the Price of Robust Persuasiveness ($\mathsf{PoRP}_k$) is $\Theta(\min{2^k,n})$ for supermodular sender utilities and $\Theta(k)$ for submodular or XOS sender utilities, where $n$ is the number of receivers. In some instances, $\Theta(\log k)$ leakages are sufficient for the utility of the optimal leakage-robust persuasion to degenerate to that of public persuasion. - The second notion, expected downstream utility robustness, relaxes the persuasiveness requirement and instead analyzes sender's utility when receivers best respond to their observations. We quantify the Price of Robust Downstream Utility ($\mathsf{PoRU}$) as the gap between the expected sender utility over the randomness in the leakage pattern as compared to private persuasion. For several natural and structured distributions of leakage patterns, we show that $\mathsf{PoRU}$ improves on $\mathsf{PoRP}$, becoming $\Theta(k)$ or even $\Theta(1)$, where $k$ is the maximum number of leaked signals observable to each receiver across leakage patterns in the distribution. En route to these results, we show that subsampling and masking serve as general-purpose algorithmic paradigms for transforming private persuasion schemes into leakage-robust schemes, with minmax-optimal loss in sender utility.