We study a Bayesian persuasion setting with binary actions (adopt and reject) for Receiver. We examine the following question - how well can Sender perform, in terms of persuading Receiver to adopt, when ignorant of Receivers utility? We take a robust (adversarial) approach to study this problem; that is, our goal is to design signaling schemes for Sender that perform well for all possible Receivers utilities. We measure performance of signaling schemes via the notion of (additive) regret: the difference between Senders hypothetically optimal utility had she known Receivers utility function and her actual utility induced by the given scheme. On the negative side, we show that if Sender has no knowledge at all about Receivers utility, then Sender has no signaling scheme that performs robustly well. On the positive side, we show that if Sender only knows Receivers ordinal preferences of the states of nature - i.e., Receivers utility upon adoption is monotonic as a function of the state - then Sender can guarantee a surprisingly low regret even when the number of states tends to infinity. In fact, we exactly pin down the minimum regret value that Sender can guarantee in this case, which turns out to be at most 1/e. We further show that such positive results are not possible under the alternative performance measure of a multiplicative approximation ratio by proving that no constant ratio can be guaranteed even for monotonic Receivers utility; this may serve to demonstrate the merits of regret as a robust performance measure that is not too pessimistic. Finally, we analyze an intermediate setting in between the no-knowledge and the ordinal-knowledge settings.
Download