# Algorithmic Persuasion with No Externalities

arXiv: https://arxiv.org/abs/1609.06825 · HTML: https://mlsanity.com/paper/1609.06825/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2016.

## Built on by (most cited first, 9 of 9)

- [Bayesian Persuasion for Algorithmic Recourse](https://mlsanity.com/paper/2112.06283/) (2021)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Multi-Receiver Online Bayesian Persuasion](https://mlsanity.com/paper/2106.06480/) (2021)
- [Multi-Sender Persuasion: A Computational Perspective](https://mlsanity.com/paper/2402.04971/) (2024)
- [Learning in Online Principal-Agent Interactions: The Power of Menus](https://mlsanity.com/paper/2312.09869/) (2023)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Algorithmic Information Design in Multi-Player Games: Possibility and Limits in Singleton Congestion](https://mlsanity.com/paper/2109.12445/) (2021)
- [Quantifying Theoretical AI Alignment Guarantees: Receiver-Utility Bounds in Bayesian Persuasion](https://mlsanity.com/paper/2606.22226/) (2026)
- [On Incentivized Exploration beyond Bayesianism and Full-Information](https://mlsanity.com/paper/2607.18300/) (2026)

## Abstract (arXiv)

We study the algorithmics of information structure design -- a.k.a. persuasion or signaling -- in a fundamental special case introduced by Arieli and Babichenko: multiple agents, binary actions, and no inter-agent externalities. Unlike prior work on this model, we allow many states of nature. We assume that the principal's objective is a monotone set function, and study the problem both in the public signal and private signal models, drawing a sharp contrast between the two in terms of both efficacy and computational complexity. When private signals are allowed, our results are largely positive and quite general. First, we show polynomial-time equivalence between optimal signaling and the problem of maximizing the objective function plus an additive function. This yields an efficient implementation of the optimal scheme when the objective is supermodular or anonymous. Second, we exhibit a (1-1/e)-approximation of the optimal private signaling scheme, modulo an additive loss of ε, when the objective function is submodular. These two results simplify, unify, and generalize results of [Arieli and Babichenko, 2016] and [Babichenko and Barman, 2016], extending them from a binary state of nature to many states (modulo the additive loss in the latter result). Third, we consider the binary-state case with a submodular objective, and simplify and slightly strengthen the result of [Babichenko and Barman, 2016] to obtain a (1-1/e)-approximation via an explicitly constructed scheme. When only a public signal is allowed, our results are negative. First, we show that it is NP-hard to approximate the optimal public scheme, within any constant factor, even when the objective is additive. Second, we show that the optimal private scheme can outperform the optimal public scheme, in terms of maximizing the sender's objective, by a polynomial factor.