# Multi-Receiver Online Bayesian Persuasion

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 11 Jun 2021.

## Builds on (most cited first, 15 of 15)

- [Bayesian Exploration: Incentivizing Exploration in Bayesian Games](https://mlsanity.com/paper/1602.07570/) (2016)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Algorithmic Bayesian Persuasion](https://mlsanity.com/paper/1503.05988/) (2015)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [Algorithmic Persuasion with No Externalities](https://mlsanity.com/paper/1609.06825/) (2016)
- [Targeting and Signaling in Ad Auctions](https://mlsanity.com/paper/1708.00611/) (2017)
- [On the Tractability of Public Persuasion with No Externalities](https://mlsanity.com/paper/1906.07359/) (2019)
- [Mixture Selection, Mechanism Design, and Signaling](https://mlsanity.com/paper/1508.03679/) (2015)
- [Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games](https://mlsanity.com/paper/1512.03543/) (2015)
- [Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry](https://mlsanity.com/paper/2002.05190/) (2020)
- [Regret-Minimizing Bayesian Persuasion](https://mlsanity.com/paper/2105.13870/) (2021)
- [Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud](https://mlsanity.com/paper/1908.10620/) (2019)
- [Persuading Voters in District-based Elections](https://mlsanity.com/paper/2012.05002/) (2020)
- [Computational Aspects of Private Bayesian Persuasion](https://mlsanity.com/paper/1603.01444/) (2016)

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

- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Sequential Information Design: Learning to Persuade in the Dark](https://mlsanity.com/paper/2209.03927/) (2022)
- [Markov Persuasion Processes: Learning to Persuade from Scratch](https://mlsanity.com/paper/2402.03077/) (2024)
- [Persuading a Behavioral Agent: Approximately Best Responding and Learning](https://mlsanity.com/paper/2302.03719/) (2023)
- [Mediated Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.08419/) (2023)
- [Algorithmic Persuasion Through Simulation](https://mlsanity.com/paper/2311.18138/) (2023)
- [Information Design with Unknown Prior](https://mlsanity.com/paper/2410.05533/) (2024)
- [Navigating Decision Landscapes: The Impact of Principals on Decision-Making Dynamics](https://mlsanity.com/paper/2312.16230/) (2023)
- [Provably Efficient Algorithm for Best Scoring Rule Identification in Online Principal-Agent Information Acquisition](https://mlsanity.com/paper/2505.17379/) (2025)
- [Meta-Learning for Repeated Bayesian Persuasion](https://mlsanity.com/paper/2603.20408/) (2026)
- [Learning to Persuade Privately Informed Receivers](https://mlsanity.com/paper/2607.28342/) (2026)
- [Learning to Price with Persuasion](https://mlsanity.com/paper/2608.16699/) (2026)

## Abstract (arXiv)

Bayesian persuasion studies how an informed sender should partially disclose information to influence the behavior of a self-interested receiver. Classical models make the stringent assumption that the sender knows the receiver's utility. This can be relaxed by considering an online learning framework in which the sender repeatedly faces a receiver of an unknown, adversarially selected type. We study, for the first time, an online Bayesian persuasion setting with multiple receivers. We focus on the case with no externalities and binary actions, as customary in offline models. Our goal is to design no-regret algorithms for the sender with polynomial per-iteration running time. First, we prove a negative result: for any 0 < α ≤ 1, there is no polynomial-time no-α-regret algorithm when the sender's utility function is supermodular or anonymous. Then, we focus on the case of submodular sender's utility functions and we show that, in this case, it is possible to design a polynomial-time no-(1 - frac1e)-regret algorithm. To do so, we introduce a general online gradient descent scheme to handle online learning problems with a finite number of possible loss functions. This requires the existence of an approximate projection oracle. We show that, in our setting, there exists one such projection oracle which can be implemented in polynomial time.