We consider a multi-agent Bayesian persuasion problem where a sender aims at persuading multiple receivers to maximize a global objective that depends on all the receivers' actions. We focus on one of the most basic settings in this space where each receiver takes a binary action, conveniently denoted as action $1$ and action $0$. The payoff of the sender is thus a set function, depending on the set of receivers taking action $1$. Each receiver's utility depends on his action and a random state of nature whose realization is a-priori unknown to receivers. The sender has an informational advantage, namely access to the realized state of nature, and can commit to a policy, a.k.a., a signaling scheme, to send a private signal regarding the realized state to each receiver. #R##N#Assuming the sender's utility function is monotone submodular, we examine the sender's optimization problem under different input models. When the state of nature is binary, we show that a $(1-\frac{1}{e})$-approximate signaling scheme can be explicitly constructed. This approximation ratio is tight. Moreover, the constructed signaling scheme has the following distinctive properties: (i) it signals independently to each receiver, simply to maximize the probability of persuading them to take action $1$; (ii) it is oblivious in the sense that it does not depend on the sender's utility function as long as it is monotone submodular! When there are many states of nature, we present an algorithm that computes a $(1-\frac{1}{e})$-approximate signaling scheme, modulo an additional additive loss of $\epsilon$, and runs in time polynomial in the input size and $\frac{1}{\epsilon}$. Our algorithm here relies on a structural characterization of (approximately) optimal signaling schemes.
['Shaddin Dughmi', 'Haifeng Xu']
Private Bayesian Persuasion with Monotone Submodular Objectives