# Regret-Minimizing Bayesian Persuasion

Yakov Babichenko Technion–Israel Institute of Technology — _E-mail_ :
<EMAIL_ADDRESS>Yakov is supported by the Binational Science
Foundation BSF grant no. 2018397 and by the German-Israeli Foundation for
Scientific Research and Development GIF grant no. I-2526-407.6/2019. Inbal
Talgam-Cohen Technion–Israel Institute of Technology — _E-mail_ :
<EMAIL_ADDRESS>Inbal is a Taub Fellow supported by the Taub Family
Foundation. This research was supported by the Israel Science Foundation grant
no. 336/18.  Haifeng Xu University of Virginia — _E-mail_ :
<EMAIL_ADDRESS>Haifeng is supported by a Google Faculty Research Award.
Konstantin Zabarnyi Technion–Israel Institute of Technology — _E-mail_ :
<EMAIL_ADDRESS>
(May 28, 2021)

###### Abstract

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
Receiver’s 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 Receiver’s utilities. We measure performance
of signaling schemes via the notion of (additive) _regret_ : the difference
between Sender’s hypothetically optimal utility had she known Receiver’s
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
Receiver’s utility, then Sender has no signaling scheme that performs robustly
well. On the positive side, we show that if Sender only knows Receiver’s
ordinal preferences of the states of nature – i.e., Receiver’s 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 Receiver’s 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.

##  1 Introduction

#### Bayesian persuasion and applications.

Since the seminal paper of Kamenica and Gentzkow [33], the model of _Bayesian
persuasion_ – a.k.a.  _information design_ – has been extensively studied in
economics, computer science and operational research (for recent surveys see
[20; 32; 7; 12]). The model considers an informed _Sender_ who knows the
_state of nature_ , and an uniformed _Receiver_ who does not know the state,
but takes an action that affects both Receiver’s and Sender’s utilities.
Sender has the ability to commit, before learning the state, to an information
revelation policy called a _signaling scheme_. The main question of interest
is: what is the optimal Sender’s utility, and what scheme should Sender choose
to achieve this utility? The Bayesian persuasion model has quite a few
applications in different domains, including interactions between:

  * •

a prosecutor (Sender) and a judge (Receiver) [33]; the unknown state of nature
is whether the defendant is guilty or not; the prosecutor’s goal is to
persuade the judge to convict;

  * •

a seller of a product (Sender) and a potential buyer (Receiver) [33; 2; 11];
the unknown state is the product quality; the seller’s goal is to persuade the
buyer to purchase;

  * •

a principle (Sender) delegating a project to an agent (Receiver) [22]; the
unknown state is the project quality; the principle’s goal is to persuade the
agent to maximize the effort invested in the project.

Further application domains of Bayesian persuasion include security [55; 42],
routing [8], recommendation systems [38], auctions [24; 10], voting [1; 17],
queuing [37], etc.

#### Knowledge of Receiver’s utility.

One of the fundamental assumptions underlying the Bayesian persuasion model is
that Sender perfectly knows Receiver’s utility, and she can use this detailed
knowledge in her persuasion efforts. However, this assumption may be too
demanding in some circumstances. In particular, in all examples above, it is
reasonable to assume that Sender is uncertain about Receiver’s precise
utility. In the judge-prosecutor interaction, the prosecutor may be uncertain
of the judge’s exact utilities in the four cases of conviction vs. acquittal,
and guilty vs. innocent defendant; thus, when designing her investigation
(signaling scheme) that will convey to the judge a certain posterior
probability of guilt/innocence, the prosecutor might not know the threshold
probability above which the judge would convict. Similarly, in the seller-
buyer interaction, the seller may be unaware of the buyer’s utility as a
function of the product’s quality, and a principle may be unaware of her
agent’s utility (in particular – because she might not know how costly the
agent’s effort is). Arguably, in almost all Bayesian persuasion applications,
the scenario in which Sender is not fully aware of Receiver’s utility may
naturally arise.

#### Bayesian knowledge of Receiver’s utility.

These examples motivate the study of Bayesian persuasion in settings in which
Sender has to decide how to reveal her private information despite not having
complete knowledge of Receiver’s utility. One approach for addressing this
issue is _Bayesian_ – Sender does not know Receiver’s utility, but she has a
prior distribution on it. However, relying on precise Bayesian knowledge
raises the same brittleness issues as relying on knowledge of the utility
itself, only “one level up”. In the oft-cited words of Nobel Laureate Robert
Wilson, “I foresee the progress of game theory as depending on successive
reduction in the base of common knowledge required to conduct useful analyses
of practical problems” [54] (see also [28; 47]). As another consideration
against the Bayesian route, in our setting it turns out that Bayesian modeling
of uncertainty regarding the utility essentially reduces back to the standard
persuasion model.111For each posterior distribution of Receiver over the
states of nature, the _distribution of actions_ that Receiver would take is
determined by Sender’s prior on Receiver’s utilities. This specifies the
expected Sender’s utility for each Receiver’s posterior. Therefore, one can
analyze the interaction using the standard Bayesian persuasion setting, and so
this approach is not expected to shed new light on robust methods of
persuasion.

#### The robust approach.

An alternative way to address Sender’s uncertainty is the _robust approach_ –
a.k.a. the _adversarial approach_ or the _prior-free approach_. The goal is to
design signaling schemes that perform robustly well, that is – perform well
for _all_ Receiver’s utilities, even when an adversary is allowed to choose
the _worst case_ utility for Receiver. The adversarial lens has the potential
to provide insights on issues such as: _(a) How harmful can it be for Sender
to be unaware of Receiver’s utility? (b) What information about Receiver’s
utility is sufficient to enable “reasonably good” persuasion? (c) How should
Sender approach persuading Receiver if Receiver’s utility is unknown?_ We
shall return to these questions in Subsection 1.1.

There are several common robust approaches, which differ in their measure of
performance and the benchmark they measure against. All three approaches have
proved useful in appropriate contexts:

  1. 1.

Regret minimization. The _regret minimization approach_ compares the
performance of a signaling scheme when Sender _does not know_ the Receiver’s
utility function to the performance of an optimal scheme _with knowledge_ of
Receiver’s utility; the comparison is by considering the _difference_ between
the optimal utilities in the two cases, known as the (additive) _regret_. The
regret minimization approach is attributed to the classic work of Savage [45]
on decision theory. It is also the leading paradigm in online machine learning
[48]. In economic contexts, two recent examples adopting this approach are [3]
(in the context of information aggregation) and [26] (in the context of
monopoly regulation).

  2. 2.

Adversarial approximation. The _adversarial approximation approach_ is similar
to the previous one, but the comparison is by considering the corresponding
_ratio_. Using the ratio to measure performance is the leading paradigm in
approximation algorithms [51], partially due to it being scale-free.222The
approximation ratio does not depend on the units of measure and requires no
normalization. In economic contexts, the adversarial approximation approach
underlies the well-developed line of research on prior-independent optimal
auctions [19; 50] and their sample complexity [18] (see [44] for a survey).
Another example is the work of [30] on sharecropping contracts.

  3. 3.

Minimax. The _minimax approach_ 333Note that the name of this approach is
slightly misleading, as all three robust approaches have a minimax flavor, and
the difference is in what is being optimized within the minimax expression.
measures the _absolute performance_ of a signaling scheme with _no knowledge_
of Receiver’s utility function; this approach has no benchmark. The minimax
approach is attributed to the scholarship of Wald [52]. There are many recent
applications of the minimax approach in economics, including to auctions [5;
14; 25; 6] and contracts [13; 21] (see the comprehensive survey of Carroll
[15]).

#### Our focus on regret.

In this paper, we mainly focus on the first approach of regret minimization.
This approach is known to be less pessimistic than the minimax approach (see,
e.g., [53] for a concrete example). Indeed, Savage [46] highlights the
“extreme pessimism” of the minimax approach as a disadvantage relative to
regret minimization (see Chapters 9.8 and 13.2). In our particular setting,
minimax seems to suggest that without further assumptions there is not much
Sender can do (see more discussions in Section 5). As for the adversarial
approximation approach, we study it in Section 4 and show that it too is
overly pessimistic. In light of these negative results, one take-away from our
analysis is the merit of regret minimization as a tool for deriving economic
insights, especially in settings in which the two other (arguably more
popular) robust approaches fail to produce such insights. In this sense, our
work can be seen as close to that of Dworczak and Pavan [23], who also diverge
from the standard minimax approach to better capture the best policy for
Sender. Our motivation is very similar to that of Castiglioni et al. [16],
whose interesting work studies Bayesian persuasion in an online learning
framework with the goal of relaxing the assumption that Sender knows
Receiver’s utility. We view our approach to the problem as complementary to
theirs. In their model, Sender repeatedly faces Receiver with a non-binary
action, whose type is chosen by Adversary at each round from a finite set of
possibilities. Their regret notion is with respect to a best-in-hindsight
single signaling scheme. In contrast, we minimize the regret over a single
persuasion instance with respect to the best scheme tailored to that instance.
We consider a binary-action Receiver with a quite general class of (continuum-
many) possible utilities.

###  1.1 Our Results

#### Settings of interest.

We consider a setting with $n$ states of nature, an arbitrary prior
distribution over them and a binary-action Receiver whose possible actions are
_adoption_ and _rejection_. Sender aims to persuade Receiver to adopt. This
simple persuasion setting is aligned with the motivating examples mentioned
above (prosecutor-judge, seller-buyer and principle-agent). Note that a
binary-action Receiver is a fundamental case in Bayesian persuasion studied in
many works – two recent examples are [34; 27].

We study the following three variants:

  * •

_Arbitrary utilities_ , with a completely ignorant Sender, who has no
information whatsoever on Receiver’s utility.

  * •

_Monotonic utilities_ , with Sender knowing that Receiver’s utility upon
adoption is monotonic as a function of the state of nature. This assumption
arises naturally when the state of nature reflects possible qualities of a
certain product (higher quality yields higher Receiver’s utility upon
adoption).

  * •

_Multidimensional monotonic utilities_ , with the state representing the
qualities of several attributes (dimensions) of a product, each with a finite
set of possible qualities. We make the natural assumption that Receiver’s
utility upon adoption is monotonic in each dimension. We focus on a constant
number of attributes, as is natural when persuading to buy a certain product.

In each case, the problem is specified by the number of states $n$ and by the
prior over these states. For some of these specifications our results are able
to pin down the regret explicitly, and for others we provide asymptotic
results for $n\to\infty$.

#### Results for arbitrary vs. monotonic utilities.

Our adversarial analysis shows that Sender cannot hope for a nontrivial bound
on her regret for arbitrary utilities with a large number of states (see
Theorem 3.5). In contrast, even if the number of states tends to infinity, the
regret remains quite low (at most $\frac{1}{e}$) in the monotonic utility case
(Theorem 3.6). These two results together provide answers to questions $(a)$
and $(b)$ posed when introducing the robust approach – on the one hand, it
might be very harmful for Sender to be unaware of Receiver’s utility; on the
other hand, knowing Receiver’s ordinal preferences over the states may suffice
for Sender to persuade Receiver “reasonably well”. Our results highlight
monotonicity as the distinguishing property among settings in which Sender can
persuade and those in which she should seek additional information on Receiver
before approaching him.

Regarding question $(c)$ – how should Sender persuade Receiver without knowing
her utility – our positive results are all constructive, i.e., in their proofs
we provide a signaling scheme that achieves the claimed regret.

Interestingly, in many cases we discover that the regret-minimizing policies
use _infinitely many_ signals. This is in sharp contrast to the standard
persuasion model, in which binary-signal policies are sufficient.

Another insight from our results for monotonic utilities is that the idea of
“pooling together” the highest-utility states is useful not only in standard
persuasion, in which such threshold policies are known to be optimal [43], but
also for regret minimization. It makes our work fall within the “classic”
theme of the robust mechanism design literature, by which well-known
mechanisms have robustness properties – including linear contracts [13] and
simultaneous ascending auctions [40]. In the standard setting, the amount of
probability mass on highest-utility states that Sender pools together in an
optimal scheme is determined by Receiver’s utility. In our setting, since
Receiver’s utility is unknown, this amount should be carefully randomized to
minimize the regret. In fact, this amount is a non-negative real-valued random
variable with a continuum-sized support; hence, it translates to a signaling
scheme with a continuum of signals.

#### Further results.

In Subsection 3.3, we study multidimensional states of nature assuming that
Receiver’s utility is monotonic in every dimension. Each dimension represents
an attribute of a certain product; the value of the corresponding coordinate
of a state represents the quality level of that attribute. We focus on a
constant number of attributes. We provide a positive result for product priors
by upper-bounding the regret in terms of the number of attributes. However, as
a corollary from the arbitrary utility analysis, the regret for general priors
might approach $1$ as the number of possible quality levels grows to infinity,
even for $2$ attributes.

In Section 4, we depart from regret minimization and consider the alternative
adversarial approximation approach. We first establish that all our negative
results (from the arbitrary and multidimensional monotonic utility cases)
translate to this approach as well. Furthermore, we prove that even with
monotonic utilities, Sender can robustly achieve only a logarithmic factor of
the optimal utility upon knowing Receiver’s utility.

###  1.2 Techniques and Organization

Robust persuasion can be seen as a zero-sum game between Sender and an
adversary (see Section 2). Since both players have a rich set of strategies
(signaling schemes vs. adversarial utility functions), it is unclear how to
analyze this game to get a handle on its value. Our main positive result
(Theorem 3.6) uses the ordinal knowledge of states to reduce the complex game
to a much simpler one in which each player simply chooses a threshold real
number from which Receiver adopts. Without the ordinal knowledge, getting a
positive result requires complex analysis; in Proposition 3.4 we achieve this
via geometric arguments and analytical geometry. As some of our proofs are
technically involved, we defer many of them to the appendices and use the body
of the paper for presenting the result statements, proof intuitions, and main
takeaways. Section 5 contains several interesting directions for future
research.

###  1.3 Additional Related Work

Recently, there is a growing interest in understanding the Bayesian persuasion
model from an adversarial (robust) perspective. This recent literature focuses
on robustness with respect to different ingredients of the persuasion model.
[29; 35; 23] study robustness of persuasion with respect to private
information that Receiver might have. [31; 36; 39; 41; 56] consider persuasion
with multiple receivers and study robustness with respect to the strategic
behavior of the receivers after observing their signals. Most of the existing
literature on robust Bayesian persuasion adopts the minimax approach, while we
focus on regret minimization.

##  2 Our Setting

We start by describing the classic Bayesian persuasion setting with a single
Sender and a single Receiver. We impose two restrictions on the standard
model: (1) Receiver has binary actions, which captures choosing whether to
adopt a certain offer or not; (2) Sender’s utility is state-independent, which
captures caring only about whether Receiver adopts the offer, regardless of
the circumstances.

#### Prior, posterior and signaling scheme.

Let $\Omega=\left[n\right]=\left\\{1,...,n\right\\}$ be the _state of nature
space_ , and let $\omega\in\Omega$ be the true _state of nature_. Denote by
$\Delta\left(\Omega\right)$ the set of all the probability distributions over
$\Omega$. For every $q\in\Delta\left(\Omega\right)$, let $q_{i}$ be the
probability the distribution $q$ assigns to the state of nature $i$. Define
the _support_ of $q$ to be
${\mathrm{supp}}\left(q\right):=\left\\{i\in\Omega:q_{i}>0\right\\}$. Let
$\mu\in\Delta\left(\Omega\right)$ be the _prior distribution_ on $\Omega$ –
a.k.a. the _prior_. Assume that $\mu$ is publicly known. Furthermore, assume
w.l.o.g. that the probability of every state is strictly positive – that is,
$\mu_{i}>0$ for every $i\in\Omega$.444Otherwise, one can eliminate $i$ from
$\Omega$. Therefore, $\mu$ is an interior point of
$\Delta\left(\Omega\right)$.

The _signaling scheme_ is a stochastic mapping $\pi:\Omega\to S$, where $S$ is
a (finite or infinite) set of signals. Sender commits to signaling scheme
$\pi$ and then observes the true state $\omega$; Receiver does not observe
$\omega$. Upon learning $\omega$, Sender transmits to Receiver, according to
$\pi\left(\omega\right)$, a _signal realization_ $s\in S$. After receiving
$s$, Receiver updates his belief regarding the state of nature distribution to
a _posterior distribution_ on $\Omega$ – a.k.a. the _posterior_ – denoted by
$p\left(s\right)\in\Delta\left(\Omega\right)$, where
$p_{i}\left(s\right)=\Pr\left[\omega=i\mid
s\right]=\frac{\Pr_{s^{\prime}\sim\pi\left(i\right)}\left[s^{\prime}=s\right]\mu_{i}}{\Pr\left[s\right]}$.
Only the posterior distribution is important to the persuasion instance
outcome, rather than the signal realization itself.

We slightly abuse the notation and use $\pi$ also to denote the distribution
over the elements of $S$ induced by the signaling scheme $\pi$ considering the
prior $\mu$. That is, for every $s_{0}\in S$:

$\displaystyle\Pr_{s\sim\pi}\left[s=s_{0}\right]=\sum_{i\in\Omega}\mu_{i}\cdot\Pr_{s^{\prime}\sim\pi\left(i\right)}\left[s^{\prime}=s_{0}\right].$

######  Remark 2.1.

It is well-known (see, e.g., [9; 4]) that a distribution over Receiver’s
posteriors $p\in\Delta\left(\Omega\right)$ is implementable by some signaling
scheme $\pi$ if and only if $\mathbb{E}\left[p\right]=\mu$. We refer to this
condition as _Bayes-plausibility_.

#### Utilities and adoption.

In our setting, Receiver has a binary _action space_ ; that is, Receiver’s
_action_ $a$ is selected from $\left\\{0,1\right\\}$. Call action $1$
_adoption_ and action $0$ _rejection_. Sender’s utility is a function
$u_{s}:\left\\{0,1\right\\}\to\left[0,1\right]$ of Receiver’s action. We
assume $u_{s}\left(a\right):=a$, i.e., Sender wants Receiver to take action
$1$ (to adopt). Thus, the expected Sender’s utility equals the probability
that Receiver adopts.

Receiver’s utility is a function
$u_{r}:\Omega\times\left\\{0,1\right\\}\to\mathbb{R}$ of the state of nature
and Receiver’s action. W.l.o.g., we normalize Receiver’s utility
$u_{r}\left(i,0\right)$ to zero for every $i\in\Omega$. That is, _Receiver’s
utility for choosing to reject is always $0$_, regardless of the state of
nature.

Given the posterior $p\left(s\right)$, Receiver adopts if and only if:555We
assume that ties are broken in Sender’s favour, as is standard in the Bayesian
persuasion literature.

$\mathbb{E}_{\omega^{\prime}\sim
p\left(s\right)}\left[u_{r}\left(\omega^{\prime},1\right)\right]\geq 0.$ (1)

######  Definition 2.2.

The _adoption region_
$A=A\left(u_{r}\right)\subseteq\Delta\left(\Omega\right)$ is the set of
posteriors that lead to Receiver’s adoption:
$A:=\left\\{p\in\Delta(\Omega):\mathbb{E}_{\omega^{\prime}\sim
p}\left[u_{r}\left(\omega^{\prime},1\right)\right]\geq 0\right\\}$.

For a signaling scheme $\pi$ and Receiver’s utility function $u_{r}$, denote
Sender’s expected utility over $\pi$ by:

$u\left(\pi,u_{r}\right):=\Pr_{s\sim\pi}\left[p\left(s\right)\in
A\left(u_{r}\right)\right].$

#### Objective.

Given a Bayesian persuasion setting with (known) $u_{r}$ as Receiver’s
utility, the standard goal of the designer (Sender) is to compute a signaling
scheme $\pi^{*}=\pi^{*}\left(u_{r}\right)$ that maximizes Sender’s expected
utility: $\pi^{*}\in\arg\max_{\pi}\left\\{u\left(\pi,u_{r}\right)\right\\}$.
In our binary-action setting, computing the optimum $\pi^{*}$ is a well-
understood problem. One general approach to tackle the problem is by first
expressing $u_{s}$ as a function of the posterior, then taking the
concavification and evaluating it at the point representing the prior
[33].666Note that $u_{s}$ equals the indicator function
$\textbf{1}_{p\left(s\right)\in A}$; since $A$ is a half-space, the
concavification of $u_{s}$ can be computed and characterized.

###  2.1 Threshold Signaling Schemes

We now introduce a class of signaling schemes that can be used to optimally
solve the setting with a binary-action Receiver in the standard model with
Receiver’s utility function known to Sender. Interestingly, this class plays a
key part in our results for the adversarial model with unknown utility. We
begin by describing the _knapsack method_ for solving a persuasion problem;
then we formulate the class of signaling schemes that arise from this
approach.

#### The knapsack method.

An alternative to the general concavification method is a greedy approach that
reduces our problem to a fractional _knapsack_ instance. States are treated as
the knapsack items, and their prior probabilities according to $\mu$ are the
weights. Recall that every state induces utility $u_{r}\left(i,1\right)$ to
Receiver upon adoption. Sender’s goal is to add to the knapsack a maximum-
weight set of states (possibly – their fractions), while keeping Receiver’s
expected utility non-negative (the expectation is over a random state drawn
w.p. proportional to its weight in the knapsack). The knapsack instance can be
solved greedily by sorting the states $i\in\Omega$ according to
$u_{r}\left(i,1\right)$ in a non-increasing order, and then continuously
adding masses of states to the knapsack as long as the expected Receiver’s
utility stays non-negative. Such an approach has been adopted by [43].

An equivalent way to present the knapsack approach is as follows. Let
$i_{1},...,i_{n}$ be an ordering of the states s.t.
$u_{r}\left(i_{1},1\right)\leq u_{r}\left(i_{2},1\right)\leq...\leq
u_{r}\left(i_{n},1\right)$. One can interpret the state space equipped with
the prior distribution as drawing uniformly a real number in
$\left[0,1\right]$ – called the _real-valued state_ – s.t. for every
$m\in\left[n\right]$, all the realizations in the segment
$\left(\sum_{l<m}\mu_{i_{l}},\sum_{l\leq m}\mu_{i_{l}}\right]$ correspond to
the state $i_{m}$.777To demonstrate this, consider $n=4$ states
$i_{1},i_{2},i_{3},i_{4}$ with prior
$\mu\left(i_{1},i_{2},i_{3},i_{4}\right)=\left(0.2,0.3,0.1,0.4\right)$. Then,
e.g., if the real-valued state is $0.55$, the corresponding state from
$\Omega$ is $i_{3}$. Now we define the notion of a _threshold signaling
scheme_.

######  Definition 2.3.

For every $t\in\left[0,1\right]$, the _$t$ -threshold signaling scheme_ is a
binary signaling scheme that reveals whether the real-valued state is below
$t$ or not.

Equivalently, for $t\in\left(0,1\right]$, in the state space $\Omega$, let
$j\in\left[n\right]$ be s.t. $t\in\left(\sum_{l<j}\mu_{i_{l}},\sum_{l\leq
j}\mu_{i_{l}}\right]$. Then the _$t$ -threshold signaling scheme_ is a binary-
signal scheme with a _high_ and a _low_ signal, s.t. the high signal is sent
w.p. $1$ if $\omega>i_{j}$, w.p. $\frac{\sum_{l\leq
j}\mu_{i_{l}}-t}{\mu_{i_{j}}}$ if $\omega=i_{j}$ and w.p. $0$ if
$\omega<i_{j}$. For $t=0$, the $0$-threshold signaling scheme is the scheme
that reveals no information.

Given a threshold signaling scheme, we say of the states for which it sends
the high (resp., low) signal that they are _pooled together_. The knapsack
approach is based on the following fact:

######  Fact 2.4 (See, e.g., [43]).

Every persuasion problem with a binary Receiver’s action space admits an
optimal $x$-threshold signaling scheme for some $x$. Moreover, for every
$y\geq x$, Receiver adopts after observing the high signal in the
$y$-threshold signaling scheme.

###  2.2 Robust Approach

We depart from the standard model by assuming from now on that Receiver’s
utility function $u_{r}$ is _unknown_ to Sender. Besides Sender and Receiver,
we introduce a third entity called _Adversary_. Given $\mu$ and $\pi$,
Adversary aims to set Receiver’s utility $u_{r}$ in a way that makes the
performance of $\pi$ as bad as possible. Thus, Sender aims to design a
signaling scheme with a worst-case guarantee – it should perform well for
_all_ possible Receiver’s utility functions $u_{r}$.

#### Regret definition.

Here we formalize the (additive) regret minimization setting on which we
mostly focus in this paper, as mentioned in Section 1. Fix a prior
distribution $\mu$. Consider $\pi^{*}\left(u_{r}\right)$, a signaling scheme
that maximizes Sender’s expected utility in the standard persuasion setting in
which Receiver’s utility $u_{r}$ is known; denote by $u^{*}\left(u_{r}\right)$
the expected Sender’s utility $\pi^{*}\left(u_{r}\right)$ yields. In our
adversarial setting, given any signaling scheme $\pi$ ignorant to $u_{r}$,
Adversary aims to set $u_{r}$ in a way that maximizes Sender’s regret – that
is, maximizes the difference between what Sender could have gotten had she
known $u_{r}$ and what she gets with $\pi$. In other words, Adversary tries to
punish Sender for not choosing $\pi^{*}\left(u_{r}\right)$ as much as
possible. The regret of $\pi$ is, therefore, defined as:

######  Definition 2.5.

The _regret of a signaling scheme $\pi$_ is
${\mathrm{Reg}}\left(\pi\right):=\sup_{u_{r}}\left\\{u^{*}\left(u_{r}\right)-u\left(\pi,u_{r}\right)\right\\}.$

Sender aims to set $\pi$ in a way that minimizes the regret; thus, the regret
of the setting is defined as follows:

######  Definition 2.6.

The _regret of the setting_ is
${\mathrm{Reg}}:=\inf_{\pi}{\mathrm{Reg}}\left(\pi\right).$

#### The scale of regret.

Note that we always have $0\leq{\mathrm{Reg}}\leq 1$. Consider the following
possibilities.

  1. 1.

${\mathrm{Reg}}=0$, i.e., Sender can ensure utility $u^{*}\left(u_{r}\right)$
without knowing $u_{r}$. Such a result is “too good to be true”, as indicated
by our results.

  2. 2.

$0\ll{\mathrm{Reg}}\ll 1$ even when the problem becomes large (the number of
states grows to infinity), i.e., the additive loss from not knowing Receiver’s
utility is strictly less than $1$. Such a result can be viewed as positive.

  3. 3.

${\mathrm{Reg}}\to 1$ as the problem becomes large; that is, in the worst
case, Sender might lose her entire utility from not knowing $u_{r}$, as her
expected utility might approach $0$ while she could have gotten utility
approaching $1$ upon knowing $u_{r}$. Such a result is negative. One can also
study the rate of convergence of ${\mathrm{Reg}}$ to $1$ as a measure of how
negative the result is.

#### Zero-sum game perspective.

Our setting can be analyzed via the following two-player zero-sum game $G$.
The players are Adversary and Sender. Adversary’s pure strategies are mixtures
over the functions $\left\\{u_{r}\right\\}$, while Sender’s pure strategies
are the signaling schemes $\left\\{\pi\right\\}$.888Note that a mixture over
signaling schemes is a signaling scheme. We remark that our proofs do _not_
rely on the fact that $G$ has a value. Indeed, to bound ${\mathrm{Reg}}$ from
below by some bound $v$, we either describe explicitly a mixed strategy of
Adversary ensuring ${\mathrm{Reg}}\left(\pi\right)\geq v$ for every $\pi$, or
show that for every choice of $\pi$ by Sender, Adversary can ensure a regret
of $v$. To bound ${\mathrm{Reg}}$ from above by some bound $v$, we explicitly
describe a signaling scheme $\pi$ s.t. ${\mathrm{Reg}}\left(\pi\right)\leq v$.
However, for completeness, we mention that Sion’s Minimax Theorem [49] holds
in our setting.999Sion’s Minimax Theorem holds since the objective function is
linear and lower semi-continuous as a function of $\pi$ (w.r.t. the
Lévy–Prokhorov metric on $\Delta\left(\Omega\right)$), and is linear and
continuous as a function of the mixture over Receiver’s utility functions.
Therefore, while we define ${\mathrm{Reg}}$ as
$\inf_{\pi}\sup_{u_{r}}\left\\{u^{*}\left(u_{r}\right)-u\left(\pi,u_{r}\right)\right\\}=\inf_{\pi}\sup_{\Delta\left(u_{r}\right)}\left\\{u^{*}\left(u_{r}\right)-u\left(\pi,u_{r}\right)\right\\}$,
it also equals
$\sup_{\Delta\left(u_{r}\right)}\inf_{\pi}\left\\{u^{*}\left(u_{r}\right)-u\left(\pi,u_{r}\right)\right\\}$.
That is, if Sender can ensure a regret of at most $v$ after observing
Adversary’s strategy, then she has a signaling scheme that ensures $v$ even
without knowing Adversary’s strategy.

##  3 Regret Minimization

We consider three cases as described in Section 1: first, the case in which
Sender has no information at all about Receiver’s utility (Subsection 3.1);
second, the case in which Sender knows that Receiver’s utility upon adoption
is monotonic as a function of the state (Subsection 3.2); finally, a case with
a multidimensional state space and a Sender who knows that Receiver’s utility
is monotonic in each dimension (Subsection 3.3). As mentioned in Subsection
1.1, in the first case we obtain a negative asymptotic result, while in the
second case we have a positive result; in the third case, we obtain a positive
result for product priors, but a negative asymptotic result similar to the one
from the first case holds for general priors.

###  3.1 Arbitrary Utilities

Denote by ${\mathrm{Reg}}_{{\mathrm{AR}}}$ the regret for arbitrary utilities.
That is, in Definition 2.5, the supremum is taken over all Receiver’s
utilities. In this section, we start by characterizing the minimum regret for
$n=2$ states, as well as for $n=3$ states with a uniform prior $\mu$ – in both
cases, ${\mathrm{Reg}}_{{\mathrm{AR}}}=\frac{1}{2}$. Unfortunately, such
constant regret cannot be expected in general for arbitrary utilities. Indeed,
our main result of this section shows that for any $n\geq 2$, the regret
satisfies $1-\frac{2}{\sqrt{n}}\leq{\mathrm{Reg}}_{{\mathrm{AR}}}\leq
1-\frac{1}{4n^{2}}$. In particular,
${\mathrm{Reg}}_{{\mathrm{AR}}}\to_{n\to\infty}1$.

######  Observation 3.1.

With arbitrary utilities, the set of all possible choices of
$A\left(u_{r}\right)$ by Adversary coincides with the set of all the polytopes
obtained by cutting $\Delta\left(\Omega\right)$ by a hyperplane.

This observation follows from Equation 1, as for a fixed $u_{r}$, the
condition $\mathbb{E}_{\omega^{\prime}\sim
p\left(s\right)}\left[u_{r}\left(\omega^{\prime},1\right)\right]=0$ specifies
a hyperplane in $\Delta\left(\Omega\right)$ (see Figure 1 for illustration).

Figure 1: An illustration of the adoption region for arbitrary utilities and
$n=3$.$A$$\mathbb{E}_{\omega^{\prime}\sim
p\left(s\right)}\left[u_{r}\left(\omega^{\prime},1\right)\right]=0$$\omega=1$$\omega=2$$\omega=3$

For a binary state space we have the following result.

######  Proposition 3.2.

For $n=2$ and any prior $\mu$: ${\mathrm{Reg}}_{{\mathrm{AR}}}=\frac{1}{2}$.

###### Proof.

Let us show first that ${\mathrm{Reg}}_{{\mathrm{AR}}}\leq\frac{1}{2}$. For
simplicity of notation, we identify a prior/posterior with the probability it
specifies for $\omega=1$. Assume w.l.o.g. that $\mu_{1}\leq\frac{1}{2}$.
Consider a binary-signal scheme $\pi$ that induces the posteriors $0$ and
$2\mu_{1}$ with equal probability of $\frac{1}{2}$.101010$\pi$ is Bayes-
plausible, as the expected posterior probability of $\omega=1$ equals
$\mu_{1}$; therefore, by Remark 2.1, it indeed specifies a signaling scheme.
If $\left[0,2\mu_{1}\right]\cap A\neq\emptyset$, then either $0\in A$ or
$2\mu_{1}\in A$ (or both); thus, the adoption probability upon $\pi$ is at
least $\frac{1}{2}$, and ${\mathrm{Reg}}\left(\pi\right)\leq
1-\frac{1}{2}=\frac{1}{2}$. Otherwise, $A$ has the form $\left[t,1\right]$ for
some $t>2\mu_{1}$. By Markov’s inequality,
$\Pr_{s\sim\pi^{*}}\left[p\left(s\right)\in
A\right]\leq\frac{\mu_{1}}{t}<\frac{1}{2}$, and again
${\mathrm{Reg}}\left(\pi\right)\leq\frac{1}{2}$, as desired. Therefore, the
regret is at most $\frac{1}{2}$ for every fixed $u_{r}$; thus, it also holds
for every mixture over them.

Conversely, let us show that for every signaling scheme $\pi$, Adversary can
pick a Receiver’s utility function $u_{r}$ – or equivalently, an adoption
region $A$ – s.t. the regret would be at least $\frac{1}{2}$.

Indeed, fix $\pi$. If
$\Pr_{s\sim\pi}\left[p\left(s\right)\in\left[0,\mu_{1}\right]\right]\leq\frac{1}{2}$,
then Adversary can set $A=\left[0,\mu_{1}\right]$: on the one hand, $u^{*}=1$
is achieved (if Sender knows $A$) by the no-information scheme in which
$p\left(s\right)=\mu_{1}$ w.p. $1$, as $\mu_{1}\in A$; on the other hand,
$u\left(\pi,u_{r}\right)=\Pr_{s\sim\pi}\left[p\left(s\right)\in
A\right]=\Pr_{s\sim\pi}\left[p\left(s\right)\in\left[0,\mu_{1}\right]\right]\leq\frac{1}{2}$.
Hence, the regret is at least $\frac{1}{2}$, as desired.

It remains to consider the case in which
$\Pr_{s\sim\pi}\left[p\left(s\right)\in\left[0,\mu_{1}\right]\right]>\frac{1}{2}$.

Set
$\epsilon:=\frac{1}{2}-\Pr_{s\sim\pi}\left[p\left(s\right)\in(\mu_{1},1]\right]\in\left(0,\frac{1}{2}\right]$
and let Adversary take
$A=\left[\frac{\mu_{1}}{1-\epsilon},1\right]$.111111Note that
$0<\mu_{1}<\frac{\mu_{1}}{1-\epsilon}\leq\frac{\mu_{1}}{1-\frac{1}{2}}=2\mu_{1}\leq
1$, as $0<\epsilon\leq\frac{1}{2}$ and $0<\mu_{1}\leq\frac{1}{2}$. Then
$u^{*}\geq 1-\epsilon$, as upon knowing $A$, Sender could have chosen a
signaling scheme implying $p\left(s\right)=0$ w.p. $\epsilon$ and
$p\left(s\right)=\frac{\mu_{1}}{1-\epsilon}$ w.p. $1-\epsilon$ (note that this
scheme is, indeed, Bayes-plausible). Since
$u\left(\pi,u_{r}\right)=\Pr_{s\sim\pi}\left[p\left(s\right)\in
A\right]\leq\Pr_{s\sim\pi}\left[p\left(s\right)\in\left(\mu_{1},1\right]\right]=\frac{1}{2}-\epsilon$,
the regret is at least
$\left(1-\epsilon\right)-\left(\frac{1}{2}-\epsilon\right)=\frac{1}{2}$, as
needed. ∎

######  Remark 3.3.

One can show that ${\mathrm{Reg}}_{{\mathrm{AR}}}\geq\frac{1}{2}$ for any $n$
and any $\mu$ using similar methodology to the methodology we applied for
$n=2$.

Indeed, for a given $\pi$, Receiver should pick a hyperplane $H$ passing
through $\mu$ that does not pass through any atom in $\pi$ besides, probably,
$\mu$. Let $\Delta_{1}$ be one of the closed parts to which $H$ divides
$\Delta\left(\Omega\right)$. If
$\Pr_{s\sim\pi}\left[p\left(s\right)\in\Delta_{1}\right]\leq\frac{1}{2}$, then
by setting $A=\Delta_{1}$ Adversary ensures that Sender’s expected utility is
at most $\frac{1}{2}$, while the no-information scheme could have achieved
utility of $1$; and if
$Pr_{s\sim\pi}\left[p\left(s\right)\in\Delta_{1}\right]=\frac{1}{2}+\epsilon$
for some $\epsilon\in\left(0,\frac{1}{2}\right]$, then setting $A$ to be a
closed subset of $\Delta\left(\Omega\right)\setminus\Delta_{1}$ specified by a
close enough hyperplane $H^{\prime}$ to $H$ ensures that while
$u\left(\pi,u_{r}\right)\leq\Pr_{s\sim\pi}\left[p\left(s\right)\notin\Delta_{1}\right]=\frac{1}{2}-\epsilon$,
Sender could have achieved utility of $1-\epsilon$ had she known $A$ by an
appropriate binary-signal scheme.

Another case in which we characterize the optimal persuasion explicitly is
that of ternary state space and uniform prior.

######  Proposition 3.4.

For $n=3$ and $\mu=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$:
${\mathrm{Reg}}_{{\mathrm{AR}}}=\frac{1}{2}$.

Although Proposition 3.4 deals with a specific case, its proof is not trivial
at all. The explicit characterizations of the regret in case of ternary state
space with non-uniform prior and in case of any larger number of states remain
open problems. The formal proof of Proposition 3.4 is relegated to Appendix A.
We briefly describe here the main proof ideas.

###### Proof idea of Proposition 3.4.

By Remark 3.3, Adversary can ensure a regret of at least $\frac{1}{2}$. To
achieve such a regret, Adversary partitions the simplex
$\Delta\left(\left[3\right]\right)$ into two regions by drawing a line through
the prior $\mu$ (which is the centroid of the simplex). Thereafter, Adversary
sets $A$ to be the half-space that has a weight not above $\frac{1}{2}$
according to $\pi$ (for simplicity, here we ignore the possibility that $\pi$
has an atom on $\mu$).

The above argument can be applied for _every_ line passing through $\mu$ which
does not contain atoms of $\pi$. This hints at the desirable distributions of
posteriors for a regret-minimizing $\pi$: it should assign an equal weight of
$\frac{1}{2}$ for every half-space that contains $\mu$ on the boundary.
Another useful intuition from Proposition 3.2 is that it is worthwhile for
Sender to ”push” the weight to the boundary. This brings us to the (somewhat
educated) guess of considering the _unique_ distribution that is supported on
the boundary of $\Delta\left(\left[3\right]\right)$,
$\left\\{\left(p_{1},p_{2},p_{3}\right)\in\Delta\left(\left[3\right]\right):p_{1}=0\text{
or }p_{2}=0\text{ or }p_{3}=0\right\\}$, which assigns probability weight of
exactly $\frac{1}{2}$ to every half-space containing $\mu$ as a boundary
point. The complicated part of the proof is showing that this signaling scheme
indeed guarantees a regret of $\frac{1}{2}$ to Sender. Namely, to show that
Adversary cannot get a regret greater than $\frac{1}{2}$ by choosing the
adoption region to be a half-space that does not contain $\mu$. This follows
from geometric arguments and analytical geometry. ∎

The fact that the regret does not increase from binary to ternary state space
is somewhat misleading. The following theorem provides a negative asymptotic
result for large state spaces and an arbitrary prior.

######  Theorem 3.5.

For every number of states $n$ and any prior $\mu$:
$1-\frac{2}{\sqrt{n}}\leq{\mathrm{Reg}}_{{\mathrm{AR}}}\leq
1-\frac{1}{4n^{2}}$.

Theorem 3.5 indicates that not knowing Receiver’s utility in large state
spaces might be very costly for Sender. For every signaling scheme, there are
Receiver’s utilities for which adoption occurs with probability almost $0$,
while knowing Receiver’s utility allows Sender to get adoption probability of
almost $1$. This negative result is not very surprising, as we focus here on
the most general setting and assume nothing on Receiver’s utility. Now we
describe the proof idea; the full proof appears in Appendix B.

###### Proof idea of Theorem 3.5.

We prove that ${\mathrm{Reg}}_{{\mathrm{AR}}}\leq 1-\frac{1}{4n^{2}}$ by
describing an explicit signaling scheme ensuring such a regret bound. The more
interesting part of the theorem is ${\mathrm{Reg}}_{{\mathrm{AR}}}\geq
1-\frac{2}{\sqrt{n}}$. To show this part, we consider a specific scenario in
which Sender knows that most states ($\sim n-\sqrt{n}$) are _normal_ – they
yield a constant negative Receiver’s utility upon adoption. Among the
remaining $\sim\sqrt{n}$ states, a single _good_ state with very high utility
is hidden, while the other states are _bad_ ; for clarity of exposition,
assume that for bad states Receiver’s utility upon adoption is $-\infty$. Had
Sender known which state is the good one, she could have pooled it together
with all the normal states; it would have been incentive-compatible for
Receiver to adopt after receiving the signal that the state is not bad.

However, Adversary selects the state types uniformly at random; in particular,
our ignorant Sender does not know which state is good. The support of any
posterior distribution either contains a bad state or does not contain the
good state with a high probability, which would cause Receiver to reject. ∎

###  3.2 Monotonic Utilities

Let ${\mathrm{Reg}}_{{\mathrm{MON}}}$ be the regret for monotonic utilities.
That is, in Definition 2.5, the supremum is over all Receiver’s utilities that
are non-decreasing in the state of nature. In this setting, we prove a
positive result that provides a full explicit characterization of the regret,
for every number of states $n$ and for every prior $\mu$. We saw in the
previous subsection that $n$ plays a significant role for arbitrary utilities.
In particular, as the number of states increases, so does the uncertainty of
Sender in the arbitrary utility case. Hence, one might expect the regret to
always increase with the number of states. Surprisingly, our result shows that
this intuition is wrong: Sender’s partial knowledge on the monotonicity of
Receiver’s utility turns out to be sufficient to have as good guarantees as
for a binary state space.

Recall that $\mu_{n}$ is the prior probability of state $n$; for monotonic
utilities, Receiver gets the (weakly) largest utility upon adoption in this
state. The following theorem gives a full characterization of
${\mathrm{Reg}}_{{\mathrm{MON}}}$ in terms of $\mu_{n}$. In particular,
${\mathrm{Reg}}_{{\mathrm{MON}}}$ does not depend on $n$. The regret as a
function of $\mu_{n}$ is demonstrated in Figure 2.

######  Theorem 3.6.

For every number of states $n$ and every prior
$\mu=\left(\mu_{1},...,\mu_{n}\right)$:

$\displaystyle{\mathrm{Reg}}_{{\mathrm{MON}}}=\begin{cases}\frac{1}{e}&\text{
if }\mu_{n}\leq\frac{1}{e}\\\ -\mu_{n}\ln\mu_{n}&\text{ if
}\mu_{n}>\frac{1}{e}.\end{cases}$

Figure 2: The regret as a function of the prior probability of the highest
state.$\frac{1}{e}$1$\mu_{n}$${\mathrm{Reg}}_{{\mathrm{MON}}}$0$\frac{1}{e}$

An intuition for why parameters other than $\mu_{n}$ turn out to be irrelevant
appears in the proof sketch below; the relevance of $\mu_{n}$ is intuitively
connected to the observation that Adversary must choose
$u_{r}\left(\omega_{n},1\right)\geq 0$ to achieve a regret greater than 0 (as
otherwise, Receiver would never adopt). Sender can utilize this observation in
her favour: e.g., truthfully revealing that $\omega=n$ when it occurs yields
her a utility of at least $\mu_{n}$. As we shall see, she can utilize it in a
more clever manner, which decreases the regret even more. A possible
interpretation of Theorem 3.6 might be that unless the highest state is very
likely (its prior probability is greater than $\frac{1}{e}$), the regret
equals $\frac{1}{e}$ regardless of the prior and of the number of states.
Below we present the proof idea; for the full proof, see Appendix C. That
appendix also contains _an explicit description of the optimal Sender’s and
Adversary’s strategies_ (Lemma C.1).

###### Proof idea of Theorem 3.6.

The proof relies on the knapsack characterization of optimal signaling schemes
in the standard persuasion model. The characterization of optimal policies by
[43] states that every persuasion problem in the standard setting with binary-
action Receiver has an optimal $x$-threshold scheme for some $x$ (see
Definition 2.3).

In our setting, Receiver’s utility is unknown to Sender; hence, the optimal
threshold $x$ is unknown. Nevertheless, we make an educated guess that
threshold policies remain useful – and in fact, regret-minimizing – also in
our setting. More concretely, we consider signaling schemes in which the
threshold $y$ is drawn _at random_ , and thereafter the $y$-threshold scheme
is implemented. After restricting Sender’s schemes to the class of (mixed)
threshold schemes, we also can view Adversary’s choice of utility $u_{r}$
simply as a choice of an optimal threshold $x\in\left[0,1\right]$ (see Fact
2.4). Namely, instead of choosing a utility for Receiver, Adversary chooses
the threshold $x$ that is optimal in the standard persuasion model. This
reduces the complicated original zero-sum game $G$ (see Subsection 2.2), in
which Sender chooses a signaling scheme and adversary chooses a distribution
over possible functions $u_{r}$, to a much simpler zero-sum game
$G_{\mu_{n}}$, with both players simply choosing thresholds
$x,y\in\left[0,1\right]$.

The utility in $G_{\mu_{n}}$ is given by:

$\displaystyle
g\left(x,y\right):=\left(1-x\right)-\left(1-y\right)\textbf{1}_{y\geq x},$

where $1-x$ is $u^{*}$ (i.e., the optimal utility in the standard persuasion
model) and $\left(1-y\right)\textbf{1}_{y\geq x}$ is the utility of our
ignorant Sender: if $y\geq x$, then Receiver adopts after observing the high
signal and Sender gets utility of $1-y$; if $y<x$, then Receiver rejects after
observing the high signal (recall that $y$ is Receiver’s indifference point)
and Sender gets a utility of $0$; anyway, Receiver rejects when observing the
low signal.

In fact, not all thresholds $x\in\left[0,1\right]$ might be optimal for some
utility, but only $x\in\left[0,1-\mu_{n}\right]$. Indeed, the highest-utility
state should be included entirely in the knapsack, as otherwise adoption would
never occur and the regret would be zero. As Sender’s utility is decreasing in
$y$ for $y\geq x$ and we know that the optimal threshold is in
$\left[0,1-\mu_{n}\right]$, we can restrict ourselves to considering Sender’s
and Adversary’s thresholds $x,y$ from $\left[0,1-\mu_{n}\right]$.

The analysis of $G_{\mu_{n}}$ (see Lemma C.1 in Appendix C) leads to the game
value that appears in the theorem, and also provides the optimal strategies
for Sender and Adversary.

After having the (allegedly) optimal strategies of both players in hand, we
still have to verify that Sender cannot ensure a smaller regret than the value
of $G_{\mu_{n}}$. To this end, we show that for a simple, yet optimal strategy
of Adversary, Sender cannot gain more than the value of $G_{\mu_{n}}$ even by
choosing arbitrary (not necessarily threshold) schemes. ∎

It is interesting to note that the regret-minimizing signaling scheme
randomizes the threshold over a continuum-sized support
$\left[0,\min\left\\{1-\mu_{n},1-\frac{1}{e}\right\\}\right]$, and, in
particular, uses a continuum of signals; this stands in a sharp contrast to
standard persuasion in which binary signals suffice to get the optimal
utility. Inside the continuum-sized support, the density function is given by
$f\left(y\right):=\frac{1}{1-y}$ and, in particular, lower thresholds (closer
to no-information) are chosen with lower probability.121212To be precise, the
threshold distribution also has an atom of weight $1+\ln\mu_{n}$ on
$1-\mu_{n}$ (i.e., Sender reveals whether $\omega$ is the highest-utility
state $n$ or not) if $\mu_{n}>\frac{1}{e}$. Figure 3 demonstrates the density
function of Sender’s thresholds for $\mu_{n}=\frac{1}{4}$.

Figure 3: The density function of Sender’s threshold when
$\mu_{n}=\frac{1}{4}$.$1-\frac{1}{e}$1Sender’s threshold $y$$f$0

Note that our optimal robust signaling scheme is constructive and has a
closed-form description, and is, therefore, polynomial-time computable. For
example, for $\mu_{n}\leq 1/e$, one can implement the optimal robust scheme –
characterized in Lemma C.1 – by sampling $z\sim U\left[0,1\right]$ and
adopting the $F^{-1}\left(z\right)$-threshold scheme, where
$F\left(y\right)=-\ln\left(1-y\right)$ for $y\in\left[0,1-1/e\right]$.

###  3.3 Multidimensional Monotonic Utilities

In this setting, we denote the regret by ${\mathrm{Reg}}_{{\mathrm{MON-MD}}}$.
We assume that $\Omega=\times_{j\in\left[k\right]}\Omega_{j}$, where
$\Omega_{j}=\left[n_{j}\right]$. We require Receiver’s utility upon adoption
to be monotonic in every dimension $j\in\left[k\right]$. Namely, $\forall
1\leq j\leq
k\;\;\forall\omega_{j}^{\prime}\leq\omega_{j}^{\prime\prime}\;\;\forall\omega_{-j}^{\prime}:u_{r}\left(\omega_{j}^{\prime}\omega_{-j}^{\prime},1\right)\leq
u_{r}\left(\omega^{\prime\prime}_{j}\omega_{-j}^{\prime},1\right)$. We refer
to the dimension $k$ as a constant. Indeed, for the interpretation of the
dimension as the number of product attributes, it is natural to assume that
$k$ is not too large. The parameters that determine the size of the problem
are $n_{1},...,n_{k}$ (i.e., the numbers of quality levels of each
attribute/dimension). We show that the prior plays a significant role in
determining whether a constant regret (i.e., bounded away from one) can be
guaranteed: on the one hand, for arbitrary priors, the minimal regret might
not be bounded away from $1$; on the other hand, for _product_ priors, a
constant regret can be guaranteed.

For general priors, we have the following corollary from the arbitrary utility
case.

######  Corollary 3.7.

For $k=2$ and $n_{1}=n_{2}=m$ (for any $m\geq 1$), there exists a prior
$\mu_{m}\in\Delta\left(\left[m\right]^{2}\right)$ for which
$Reg_{{\mathrm{MON-MD}}}\left(m\right)=1-O\left(\frac{1}{\sqrt{m}}\right)$.

Corollary 3.7 follows from Theorem 3.5 and the fact that one can assign
arbitrarily small probability weights in the prior to all the states except
for the $m$ states
$\left\\{\left(i,j\right)\in\Delta\left(\left[m\right]^{2}\right):i+j=m+1\right\\}$.
On these $m$ states, the monotonicity in each dimension imposes no
restriction, while the remaining states have tiny weights, so their effect on
the regret is negligible.

Therefore, to obtain positive results, one must restrict attention to
particular classes of priors. One natural class is _product priors_ :
$\mu=\times_{j\in\left[k\right]}\mu_{j}$ for some
$\mu_{j}\in\Delta(\left[n_{j}\right])$. For this class of priors, we have the
following result, which might be viewed as positive for small values of $k$.

######  Proposition 3.8.

For every $k$, every sequence of attribute quality level amounts
$n_{1},...,n_{k}$ and every product prior
$\mu=\times_{j\in\left[k\right]}\mu_{j}$: $Reg_{{\mathrm{MON-MD}}}\leq
1-2^{-k}$.

The full proof appears in Appendix D; here we only sketch the main ideas. We
conjecture that a similar positive result can be obtained not only for product
priors, but also for positively correlated priors.

###### Proof idea of Proposition 3.8.

We present a simple signaling scheme that achieves the desired regret: Sender
reveals whether the product quality in all the attributes is above median,
where median is calculated according to the prior $\mu_{j}$. Depending on
$u_{r}$, such a scheme either always leads to adoption if all the attribute
qualities are above median – yielding expected Sender’s utility of at least
$2^{-k}$ – or not – and then even had Sender known $u_{r}$, her expected
utility could not have exceeded $1-2^{-k}$, as adoption could never occur with
all the attribute qualities being below median. ∎

##  4 Adversarial Approximation

In the adversarial approximation approach, the performance of a signaling
scheme $\pi$ is measured by
$\frac{u\left(\pi,u_{r}\right)}{u^{*}\left(u_{r}\right)}$, i.e., the _ratio_
between the utility Sender achieves with the scheme $\pi$ and the optimal
utility Sender can get upon knowing $u_{r}$. If $u^{*}\left(u_{r}\right)=0$
(i.e., even the knowledgeable Sender cannot achieve any positive utility), we
define the ratio to be $1$.

Analogically to Definitions 2.5 and 2.6 of the additive regret, define the
adversarial approximation guarantee via:

$\displaystyle{\mathrm{Apr}}\left(\pi\right):=\inf_{u_{r}}\left\\{\frac{u\left(\pi,u_{r}\right)}{u^{*}\left(u_{r}\right)}\right\\}\text{
and }$
$\displaystyle{\mathrm{Apr}}:=\sup_{\pi}{\mathrm{Apr}}\left(\pi\right).$

Similarly to the regret, we extend the definition of ${\mathrm{Apr}}$ to
${\mathrm{Apr}}_{{\mathrm{AR}}}$, ${\mathrm{Apr}}_{{\mathrm{MON}}}$ and
${\mathrm{Apr}}_{{\mathrm{MON-MD}}}$ according to the class of considered
Receiver’s utility functions.

Note that $0\leq{\mathrm{Apr}}\leq 1$, where ${\mathrm{Apr}}\approx 0$ means
that only a negligible fraction of the potential Sender’s utility (i.e., with
the knowledge of $u_{r}$) can be guaranteed. Our results in this section are
largely negative, motivating our focus on regret minimization.

We start with the general Proposition 4.1 that connects the notions of regret
(${\mathrm{Reg}}$) and adversarial approximation guarantee (${\mathrm{Apr}}$).

######  Proposition 4.1.

${\mathrm{Apr}}\leq\frac{1}{{\mathrm{Reg}}}-1$.

This fact holds in any adversarial setting with utilities (revenues) in
$\left[0,1\right]$ (and not only in our context of persuasion).

###### Proof of Proposition 4.1.

By Definitions 2.5 and 2.6, for every signaling scheme $\pi$ and every
$\epsilon>0$, there exists $u_{r}^{\epsilon}$ s.t.
$u^{*}\left(u_{r}^{\epsilon}\right)-u\left(\pi,u_{r}^{\epsilon}\right)\geq{\mathrm{Reg}}-\epsilon$.
In particular, $u^{*}\left(u_{r}^{\epsilon}\right)\geq{\mathrm{Reg}}-\epsilon$
and $u\left(\pi,u_{r}^{\epsilon}\right)\leq 1-{\mathrm{Reg}}+\epsilon$.
Furthermore,
${\mathrm{Apr}}\left(\pi\right)\leq\frac{u\left(\pi,u_{r}^{\epsilon}\right)}{u^{*}\left(u_{r}^{\epsilon}\right)}\leq\frac{1-{\mathrm{Reg}}+\epsilon}{{\mathrm{Reg}}-\epsilon}$.
Taking $\epsilon\to 0$ yields that
${\mathrm{Apr}}\left(\pi\right)\leq\frac{1-{\mathrm{Reg}}}{{\mathrm{Reg}}}=\frac{1}{{\mathrm{Reg}}}-1$.
As it holds for every $\pi$, the proposition follows. ∎

Proposition 4.1 allows to translate all the negative results on the regret
into negative results on adversarial approximation: if ${\mathrm{Reg}}\to 1$,
then ${\mathrm{Apr}}\to 0$, with at least the same convergence rate.
Concretely, the negative results for arbitrary utilities (Theorem 3.5) and
multidimensional monotonic utilities (Corollary 3.7) have analogues in the
adversarial approximation approach.

A natural question is whether our main positive result (Theorem 3.6) remains
valid for the adversarial approximation setting. Namely, can a constant
fraction of the optimal Sender’s utility be guaranteed without knowing the
cardinal Receiver’s preferences, but only the ordinal ones (i.e.,
monotonicity)? Our next result shows that the answer is negative. Furthermore,
we provide an exact characterization for the value in this case, for every
number of states $n$ and every prior $\mu$.

######  Theorem 4.2.

For every number of states $n$ and every prior
$\mu=\left(\mu_{1},...,\mu_{n}\right)$:
${\mathrm{Apr}}_{{\mathrm{MON}}}=\frac{1}{1+\ln\frac{1}{\mu_{n}}}$.

This result indicates that for large state spaces (under the natural
assumption that $\mu_{n}\to 0$), a constant fraction of the optimal utility
_cannot_ be guaranteed. Namely, unlike the regret approach in which Sender can
ensure a regret bounded away from $1$, Sender cannot guarantee a constant
approximation ratio. Now we describe the proof idea for Theorem 4.2; for the
full proof, see Appendix E.

###### Proof idea of Theorem 4.2.

Similar arguments to those in Theorem 3.6 proof apply. Recall that the proof
of Theorem 3.6 simplifies the complex zero-sum game $G$ with the action sets
of mixtures over Receiver’s utility for Adversary and signaling schemes for
Sender. The key observation is that one can reduce $G$ to a much simpler zero-
sum game in which both players choose thresholds (i.e., real numbers in
$\left[0,1-\mu_{n}\right]$).

The same idea works for Theorem 4.2; the only difference is in the utility
function in the simplified game, which should be
$\frac{\left(1-y\right)\textbf{1}_{y\geq x}}{1-x}$. In this game, $x$ is the
action of Adversary (the optimal threshold choice, as described in Fact 2.4),
while $y$ is the threshold specifying Sender’s strategy. Note that
$u^{*}=1-x$, while Sender’s utility in the $y$-threshold scheme is
$\left(1-y\right)\textbf{1}_{y\geq x}$.131313In this zero-sum game, the
$y$-player is the maximizer, while the $x$-player is the minimizer. The
reduction proof is analogous to Theorem 3.6; all that remains is to analyze
the continuum-action-set zero-sum game, which is done in Lemma E.1 in Appendix
E. ∎

##  5 Conclusions and Future Work

In this paper, we adopt the adversarial regret minimization approach to
Bayesian persuasion, and prove that while in the most general case the regret
approaches $1$ as the number of states grows large, assuming that Sender knows
Receiver’s ordinal preferences upon adoption ensures that the regret is always
at most $\frac{1}{e}$. We further provide an explicit formula for the regret,
and describe the optimal Sender’s and Adversary’s strategies. We also study
multidimensional monotonic utilities and upper bound the regret in this
setting for product priors, while showing that for general priors the regret
might tend to $1$.

Some problems remain open for the setting that we study. In particular, exact
characterization of the value (and the regret-minimizing schemes) in the
arbitrary utility case for more than two states (the only exception for which
we succeeded to perform such an analysis is the case of uniform prior with
ternary state space). The precise asymptotic convergence rate of
${\mathrm{Reg}}_{{\mathrm{AR}}}$ to $1$ is also unknown to us – we only bound
it between $\theta\left(\frac{1}{\sqrt{n}}\right)$ and
$\theta\left(\frac{1}{n^{2}}\right)$.

There are also quite a few natural extensions of the model: considering
Receiver with more than two actions and considering a setting with multiple
Receivers.

Finally, the minimax robust approach has not been discussed in this paper.
Recall that in the minimax approach, Sender aims to maximize her expected
utility over the signaling scheme and the unknown Adversary’s strategy – that
is, there is no benchmark for the performance of the signaling scheme.
Unfortunately, in the absence of any Sender’s knowledge about Receiver’s
utility, the minimax approach is meaningless: Adversary can choose $u_{r}$
s.t. Receiver never adopts, yielding the minimax value of $0$. An interesting
question we leave for future research is to find a well-motivated Sender’s
_partial knowledge_ about $u_{r}$, which would make the minimax approach
meaningful. Similarly, it is interesting to understand whether extra
assumptions on Receiver’s utility, rather than just monotonicity, may yield a
constant adversarial approximation ratio.

## References

  * Alonso and Câmara [2016] Ricardo Alonso and Odilon Câmara.  Persuading voters.  _The American Economic Review_ , 106(11):3590–3605, 2016.
  * Arieli and Babichenko [2019] Itai Arieli and Yakov Babichenko.  Private Bayesian persuasion.  _Journal of Economic Theory_ , 182:185–217, 2019.
  * Arieli et al. [2018] Itai Arieli, Yakov Babichenko, and Rann Smorodinsky.  Robust forecast aggregation.  _Proceedings of the National Academy of Sciences_ , 115(52):E12135–E12143, 2018.
  * Aumann et al. [1995] Robert J. Aumann, Michael Maschler, and Richard E. Stearns.  _Repeated Games with Incomplete Information_.  MIT Press, 1995.
  * Bandi and Bertsimas [2014] Chaithanya Bandi and Dimitris Bertsimas.  Optimal design for multi-item auctions: A robust optimization approach.  _Math. Oper. Res._ , 39(4):1012–1038, 2014.
  * Bei et al. [2019] Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang.  Correlation-robust analysis of single item auction.  In _Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 193–208, 2019.
  * Bergemann and Morris [2019] Dirk Bergemann and Stephen Morris.  Information design: A unified perspective.  _Journal of Economic Literature_ , 57:44–95, 2019.
  * Bhaskar et al. [2016] Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy.  Hardness results for signaling in bayesian zero-sum and network routing games.  In _Proceedings of the 2016 ACM Conference on Economics and Computation EC_ , pages 479–496. ACM, 2016.
  * Blackwell [1953] David Blackwell.  Equivalent comparisons of experiments.  _The annals of mathematical statistics_ , pages 265–272, 1953.
  * Bro Miltersen and Sheffet [2012] Peter Bro Miltersen and Or Sheffet.  Send mixed signals: Earn more, work less.  In _Proceedings of the 13th ACM Conference on Electronic Commerce_ , EC ’12, pages 234–247, New York, NY, USA, 2012. ACM.  ISBN 978-1-4503-1415-2.
  * Candogan [2019] Ozan Candogan.  Persuasion in networks: public signals and k-cores.  In _Proceedings of the 20th ACM Conference on Electronic Commerce_ , EC ’19, New York, NY, USA, 2019. ACM.
  * Candogan [2020] Ozan Candogan.  Information design in operations.  _TutORials in Operations Research_ , pages 176–201, 2020.
  * Carroll [2015] Gabriel Carroll.  Robustness and linear contracts.  _American Economic Review_ , 105(2):536–63, 2015\.
  * Carroll [2017] Gabriel Carroll.  Robustness and separation in multidimensional screening.  _Econometrica_ , 85(2):453–488, 2017.
  * Carroll [2019] Gabriel Carroll.  Robustness in mechanism design and contracting.  _Annual Review of Economics_ , 11:139–166, 2019.
  * Castiglioni et al. [2020] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti.  Online bayesian persuasion.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Cheng et al. [2015] Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, and Shang-Hua Teng.  Mixture selection, mechanism design, and signaling.  In _IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)_ , 2015.
  * Cole and Roughgarden [2014] Richard Cole and Tim Roughgarden.  The sample complexity of revenue maximization.  In _Proceedings of the 46th Annual ACM Symposium on Theory of Computing STOC_ , pages 243–252, 2014.
  * Dhangwatnotai et al. [2015] Peerapong Dhangwatnotai, Tim Roughgarden, and Qiqi Yan.  Revenue maximization with a single sample.  _Games and Economic Behavior_ , 91:318–333, 2015.
  * Dughmi [2017] Shaddin Dughmi.  Algorithmic information structure design: A survey.  _ACM SIGecom Exchanges_ , 15(2):2–24, 2017.
  * Dütting et al. [2019] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen.  Simple versus optimal contracts.  In _Proceedings of the 2019 ACM Conference on Economics and Computation (EC)_ , pages 369–387, 2019.
  * Dworczak and Martini [2019] Piotr Dworczak and Giorgio Martini.  The simple economics of optimal persuasion.  _Journal of Political Economy_ , 127(5):1993–2048, 2019.
  * Dworczak and Pavan [2020] Piotr Dworczak and Alessandro Pavan.  Preparing for the worst but hoping for the best: Robust (Bayesian) persuasion.  Working paper, 2020.
  * Emek et al. [2012] Yuval Emek, Michal Feldman, Iftah Gamzu, Renato Paes Leme, and Moshe Tennenholtz.  Signaling schemes for revenue maximization.  In _Proceedings of the 13th ACM Conference on Electronic Commerce_ , EC ’12, pages 514–531. ACM, 2012.  ISBN 978-1-4503-1415-2.
  * Gravin and Lu [2018] Nick Gravin and Pinyan Lu.  Separation in correlation-robust monopolist problem with budget.  In _Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms SODA_ , pages 2069–2080, 2018.
  * Guo and Shmaya [2019a] Yingni Guo and Eran Shmaya.  Robust monopoly regulation.  Working paper, 2019a.
  * Guo and Shmaya [2019b] Yingni Guo and Eran Shmaya.  The interval structure of optimal disclosure.  _Econometrica_ , 87(2):653–675, 2019b.
  * Hayek [1945] Friedrich A. Hayek.  The use of knowledge in society.  _American Economic Review_ , 35(4):519–530, 1945\.
  * Hu and Weng [2020] Ju Hu and Xi Weng.  Robust persuasion of a privately informed receiver.  _Economic Theory_ , 2020.  Forthcoming.
  * Hurwicz and Shapiro [1978] Leonid Hurwicz and Leonard Shapiro.  Incentive structures maximizing residual gain under incomplete information.  _Bell Journal of Economics_ , 9(1):180–191, 1978\.
  * Inostroza and Pavan [2020] Nicolas Inostroza and Alessandro Pavan.  Persuasion in global games with application to stress testing.  Working paper, 2020.
  * Kamenica [2019] Emir Kamenica.  Bayesian persuasion and information design.  _Annual Review of Economics_ , 11:249–272, 2019.
  * Kamenica and Gentzkow [2011] Emir Kamenica and Matthew Gentzkow.  Bayesian persuasion.  _American Economic Review_ , 101(6):2590–2615, 2011.
  * Kolotilin et al. [2017] Anton Kolotilin, Tymofiy Mylovanov, Andriy Zapechelnyuk, and Ming Li.  Persuasion of a privately informed receiver.  _Econometrica_ , 85(6):1949–1964, 2017.
  * Kosterina [2020] Svetlana Kosterina.  Persuasion with unknown beliefs.  Working paper, 2020.
  * Li et al. [2020] Fei Li, Yangbo Song, and Mofei Zhao.  Global manipulation by local obfuscation.  Working paper, 2020.
  * Lingenbrink and Iyer [2019] David Lingenbrink and Krishnamurthy Iyer.  Optimal signaling mechanisms in unobservable queues.  _Operations Research_ , 2019.
  * Mansour et al. [2016] Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu.  Bayesian exploration: Incentivizing exploration in bayesian games.  In _Proceedings of the 2016 ACM Conference on Economics and Computation_ , 2016.
  * Mathevet et al. [2020] Laurent Mathevet, Jacopo Perego, and Ina Taneva.  On information design in games.  _Journal of Political Economy_ , 128(4):1370–1404, 2020.
  * Milgrom [2000] Paul Milgrom.  Putting auction theory to work: The simultaneous ascending auction.  _Journal of political economy_ , 108(2):245–272, 2000.
  * Morris et al. [2020] Stephen Morris, Daisuke Oyama, and Satoru Takahashi.  Information design in binary action supermodular games.  Working paper, 2020.
  * Rabinovich et al. [2015] Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu.  Information disclosure as a means to security.  In _Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS),_ , 2015.
  * Renault et al. [2017] Jérôme Renault, Eilon Solan, and Nicolas Vieille.  Optimal dynamic information provision.  _Games Econ. Behav._ , 104:329–349, 2017.
  * Roughgarden and Talgam-Cohen [2019] Tim Roughgarden and Inbal Talgam-Cohen.  Approximately optimal mechanism design.  _Annual Review of Economics_ , 11:355–381, 2019.
  * Savage [1951] Leonard Jimmie Savage.  The theory of statistical decision.  _Journal of the American Statistical Association_ , 46(253):55–67, 1951.
  * Savage [1972] Leonard Jimmie Savage.  _The Foundations of Statistics_.  Dover Publications, 1972.
  * Scarf [1958] Herbert E. Scarf.  A min-max solution of an inventory problem.  In Kenneth J. Arrow, editor, _Studies in The Mathematical Theory of Inventory and Production_ , pages 201–220. 1958.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University press, 2014.
  * Sion [1958] Maurice Sion.  On general minimax theorems.  _Pacific Journal of Mathematics_ , 8(1):171–176, 1958.
  * Talgam-Cohen [2020] Inbal Talgam-Cohen.  Prior-independent auctions.  In Tim Roughgarden, editor, _Beyond the Worst-Case Analysis of Algorithms_ , chapter 27. Cambridge University Press, 2020.
  * Vazirani [2003] Vijay V. Vazirani.  _Approximation Algorithms_.  Springer, 2003.
  * Wald [1950] Abraham Wald.  _Statistical Decision Functions_.  John Wiley, 1950.
  * Wikipedia contributors [2020] Wikipedia contributors.  Regret (decision theory) — Wikipedia, the free encyclopedia, 2020\.  URL https://en.wikipedia.org/wiki/Regret_(decision_theory).  [Online; accessed 9-February-2021].
  * Wilson [1987] Robert B. Wilson.  Game-theoretic approaches to trading processes.  In Truman F. Bewley, editor, _Advances in Economic Theory: Fifth World Congress_ , pages 33–77. Cambridge University Press, 1987.
  * Xu et al. [2015] Haifeng Xu, Zinovi Rabinovich, Shaddin Dughmi, and Milind Tambe.  Exploring information asymmetry in two-stage security games.  In _AAAI Conference on Artificial Intelligence (AAAI)_ , 2015.
  * Ziegler [2020] Gabriel Ziegler.  Adversarial bilateral information design.  Technical report, 2020.  Working paper.

##  Appendix A Proof of Proposition 3.4

###### Proof of Proposition 3.4.

By Remark 3.3, it is enough to show that
${\mathrm{Reg}}_{{\mathrm{AR}}}\left(\pi\right)\leq\frac{1}{2}$. Consider
$\pi$ supported on the boundary of $\Delta\left(\Omega\right)$ that assigns to
every line segment on the boundary probability proportional to the angle upon
which this segment is seen from $\mu$. We shall prove, using analytical
geometry, that for this $\pi$,
${\mathrm{Reg}}_{{\mathrm{AR}}}\left(\pi\right)=\frac{1}{2}$. Let
${\mathrm{at}}:\left(-\infty,\infty\right]\to\left[0,\pi\right)$ be defined as
${\mathrm{at}}\left(x\right):=\arctan\left(x\right)+\pi$ for
$x\in\left(-\infty,0\right)$,
${\mathrm{at}}\left(x\right):=\arctan\left(x\right)$ for
$x\in\left[0,\infty\right)$ and
${\mathrm{at}}\left(\infty\right):=\frac{\pi}{2}$.

Fix $A$, and let $l$ be the line (single-dimensional hyperplane) separating
$A$ from $\Delta\left(\Omega\right)\setminus A$. Note that
$\Delta\left(\Omega\right)$ is contained in a two-dimensional plane. Represent
the elements of $\Delta\left(\Omega\right)$ by Cartesian coordinates (rather
than the probabilities they assign to elements of $\Omega$). Parameterize its
extreme points by $\omega_{1}=\left(0,0\right)$,
$\omega_{2}=\left(1,0\right)$,
$\omega_{3}=\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)$ .141414We assume that
the sides of the triangle $\Delta\left(\Omega\right)$ are of length $1$ when
in fact they are of length $\sqrt{2}$; however, homothety (scratch) on
$\Delta\left(\Omega\right)$ does not affect the regret. Then
$\mu=\left(\frac{1}{2},\frac{\sqrt{3}}{6}\right)$. If the separating line $l$
is disjoint to $\Delta\left(\Omega\right)$ – the regret is $0$. Therefore,
assume that it cuts at least two line segments from the boundary of
$\Delta\left(\Omega\right)$ (possibly at the same point). Assume w.l.o.g. that
$l$ cuts $\omega_{1}\omega_{2}$ (the line connecting $\omega_{1}$ and
$\omega_{2}$) and $\omega_{1}\omega_{3}$. Then $l$ contains the points
$D:=\left(d,\sqrt{3}d\right)$ and $E:=\left(e,0\right)$ for some $0\leq
d\leq\frac{1}{2}$ and $0\leq e\leq 1$. Assume that $\mu\notin A$ – otherwise,
the adoption probability assured by $\pi$ is at least $\frac{1}{2}$ and the
regret is at most $\frac{1}{2}$.

Figure 4: Parameterization of the
points.$A$$\omega_{1}=(0,0)$$\omega_{2}=(1,0)$$\omega_{3}=(\frac{1}{2},\frac{\sqrt{3}}{2})$$E=(e,0)$$D=(d,\sqrt{3}d)$$\mu=(\frac{1}{2},\frac{\sqrt{3}}{6})$

Consider now $\pi^{*}$, an optimal signaling scheme for a Sender who knows
$A$. By pooling together all the probability mass in $A$ and all the
probability mass in $\Delta\left(\Omega\right)\setminus A$ (separately),
assume w.l.o.g. that
$\left|{\mathrm{supp}}\left(\pi^{*}\right)\right|=2$.151515$\left|{\mathrm{supp}}\left(\pi^{*}\right)\right|>1$
since we assume that $\mu\notin A$.

Let $s$ be the line segment connecting the two support elements of $\pi^{*}$.
By Bayes-plausibility, it must pass through $\mu$. As $\pi^{*}$ is optimal,
one can assume w.l.o.g. that one support element is on $l$, while the other is
on the boundary of $\Delta\left(\Omega\right)$ (outside $A$); furthermore,
$\mu$ should divide $s$ in the maximal possible ratio. A straightforward (and
a well-known) trigonometric exercise shows that the ratio in which a variable
line segment $s$ passing through a fixed point, with endpoints on two fixed
line segments $s_{1},s_{2}$, is divided, is maximized when one of the
endpoints of $s$ coincides with one of the endpoints of $s_{1},s_{2}$.
Therefore, one of the endpoints of $s$ is either an intersection point of $l$
with the boundary of $\Delta\left(\Omega\right)$, or a vertex of
$\Delta\left(\Omega\right)$.

Assume first that exactly one extreme point of $\Delta\left(\Omega\right)$ is
in $A$, and assume w.l.o.g. that $\omega_{1}\in A$ (that is, $A$ is set by $l$
as in Figure 4). Qualitatively, we have $2$ different cases to check: either
$E\in{\mathrm{supp}}\left(\pi^{*}\right)$ or
$\omega_{2}\in{\mathrm{supp}}\left(\pi^{*}\right)$. Denote the second endpoint
of $s$ (that is, the support element of ${\mathrm{supp}}\left(\pi^{*}\right)$
different from $E,\omega_{2}$) by $F$. Note that if
$E\in{\mathrm{supp}}\left(\pi^{*}\right)$, then either
$F\in\omega_{2}\omega_{3}$ or $F\in\omega_{1}\omega_{3}$.161616$F$ cannot be
on $\omega_{1}\omega_{2}$, as $s$ passes through $\mu$.

Consider first the case
$E=\left(e,0\right)\in{\mathrm{supp}}\left(\pi^{*}\right)$ and
$F\in\omega_{2}\omega_{3}$ (see Figure 5). That is,
$F=\left(f,\sqrt{3}\left(1-f\right)\right)$, for $f=\frac{3-5e}{4-6e}$; note
that as $F\in\omega_{2}\omega_{3}$ and $\mu\notin A$, we have $0\leq
e\leq\frac{1}{2}$. The regret of $\pi$ for our fixed $A$ is:

$\displaystyle\frac{\left|\mu F\right|}{\left|EF\right|}-\frac{\sphericalangle
D\mu
E}{2\pi}=\frac{1}{3-3e}-\frac{1}{2\pi}{\mathrm{at}}\left(\frac{\frac{\sqrt{3}/6}{1/2-e}-\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}{1+\frac{\sqrt{3}/6}{1/2-e}\cdot\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}\right).$

Figure 5: An illustration of the case
$E\in{\mathrm{supp}}\left(\pi^{*}\right)$,
$F\in\omega_{2}\omega_{3}$.$A$$\omega_{1}$$\omega_{2}$$\omega_{3}$$E$$D$$\mu$$F=\left(f,\sqrt{3}\left(1-f\right)\right)$$s$

For a fixed $e$, the above expression is maximal for $d=0$.171717One can
obtain this step geometrically: setting $D=\omega_{1}$ does not affect the
first term and does not increase the subtracted term. Therefore (upon
algebraic simplifications), it is enough to check that:

$\displaystyle\frac{1}{3-3e}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\frac{e}{2-3e}\right)\leq\frac{1}{2}\iff{\mathrm{at}}\left(\sqrt{3}\frac{e}{2-3e}\right)-\frac{3e-1}{3-3e}\pi\geq
0.$

Note that the above expression is continuously differentiable for
$e\in\left[0,\frac{1}{2}\right]$, and its derivative is:181818For
$e\in\left[0,\frac{1}{2}\right]$, the angle $\sphericalangle D\mu
E=\sphericalangle\omega_{1}\mu E$ is acute; thus,
${\mathrm{at}}\left(\sqrt{3}\frac{e}{2-3e}\right)=\arctan\left(\sqrt{3}\frac{e}{2-3e}\right)$.

$\displaystyle\sqrt{3}\frac{1\cdot(2-3e)-e\cdot(-3)}{(2-3e)^{2}}\cdot\frac{1}{1+\left(\sqrt{3}\frac{e}{2-3e}\right)^{2}}-\frac{3(3-3e)-(3e-1)\cdot(-3)}{(3-3e)^{2}}\pi=$
$\displaystyle\frac{2\sqrt{3}}{3e^{2}+(2-3e)^{2}}-\frac{6\pi}{(3-3e)^{2}}<0,$

where the last transition follows from:
$2\sqrt{3}(3-3e)^{2}-6\pi\left(3e^{2}+(2-3e)^{2}\right)=(18\sqrt{3}-72\pi)e^{2}+e(72\pi-36\sqrt{3})+(18\sqrt{3}-24\pi)=(18\sqrt{3}-24\pi)(1-e)^{2}+24\pi
e(1-2e)\leq_{e_{{\mathrm{OPT}}}=\frac{2\pi-\sqrt{3}}{4\pi-\sqrt{3}}}\frac{4\pi^{2}(18\sqrt{3}-24\pi)}{(4\pi-\sqrt{3})^{2}}+24\pi\frac{2\pi\sqrt{3}-3}{(4\pi-\sqrt{3})^{2}}<0$.

Thus:

$\displaystyle{\mathrm{at}}\left(\sqrt{3}\frac{e}{2-3e}\right)-\frac{3e-1}{3-3e}\pi\geq_{e_{{\mathrm{OPT}}}=\frac{1}{2}}{\mathrm{at}}\left(\sqrt{3}\frac{0.5}{2-1.5}\right)-\frac{1.5-1}{3-1.5}\pi={\mathrm{at}}\left(\sqrt{3}\right)-\frac{\pi}{3}=0,$

as needed.

Now, let us still assume that
$E=\left(e,0\right)\in{\mathrm{supp}}\left(\pi^{*}\right)$, but
$F\in\omega_{1}\omega_{3}$ (see Figure 6). That is, $F=\left(f,\sqrt{3}\cdot
f\right)$ for $f=\frac{e}{6e-2}$. Note that $\frac{1}{2}\leq e\leq 1$
(otherwise, $F$ is outside the line segment $\omega_{1}\omega_{3}$, a
contradiction). Just as in the previous case, we obtain that for a fixed $e$,
the regret is maximized when $d=0$. The regret equals for $d=0$ (here we
assume that $e\neq 1$; for $e=1\implies E=\omega_{2}$, the adoption
probability according to $\pi^{*}$ is $\frac{1}{3}$; thus, the regret is
smaller than $\frac{1}{2}$):

$\displaystyle\frac{\left|\mu F\right|}{\left|EF\right|}-\frac{\sphericalangle
D\mu
E}{2\pi}=\frac{1}{3e}-\frac{1}{2\pi}{\mathrm{at}}\left(\frac{\frac{\sqrt{3}/6}{1/2-e}-\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}{1+\frac{\sqrt{3}/6}{1/2-e}\cdot\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}\right)=_{d=0}\frac{1}{3e}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\frac{e}{2-3e}\right).$

To prove that this expression is at most $\frac{1}{2}$, it is enough to show
that:

$\displaystyle{\mathrm{at}}\left(\sqrt{3}\frac{e}{2-3e}\right)-\frac{2-3e}{3e}\pi\geq
0.$

Figure 6: An illustration of the case
$E\in{\mathrm{supp}}\left(\pi^{*}\right)$,
$F\in\omega_{1}\omega_{3}$.$A$$\omega_{1}$$\omega_{2}$$\omega_{3}$$E$$D$$\mu$$F=\left(f,\sqrt{3}f\right)$$s$

The last expression is increasing in $e$. Therefore, the minimum is attained
for $e=\frac{1}{2}$, for which the condition holds:

$\displaystyle{\mathrm{at}}\left(\sqrt{3}\frac{0.5}{2-1.5}\right)-\frac{2-1.5}{1.5}\pi={\mathrm{at}}\left(\sqrt{3}\right)-\frac{\pi}{3}=0.$

Now we should consider the case in which
$E\notin{\mathrm{supp}}\left(\pi^{*}\right)$ (see Figure 7). Then
$\omega_{2}=\left(1,0\right)\in{\mathrm{supp}}\left(\pi^{*}\right)$ and
$E\neq\omega_{2}$ (i.e., $e\neq 1$). As $E\in l$, $\omega_{1}\in A$ and $l$
separates $A$ from $\Delta\left(\Omega\right)\setminus A$, we must have
$\omega_{2}\notin A$. Since the second endpoint of $s$, $F$, must belong to
$A$ – it must be on $l$. That is, $F=\left(f,\frac{1-f}{\sqrt{3}}\right)$ for
$f=\frac{e-d-3de}{e-4d}$. Note that one must have $\frac{1}{4}\leq
d\leq\frac{1}{2}$ (otherwise, $F$ cannot be on the segment $DE$) and $0\leq
e\leq\frac{2d}{6d-1}$ (as $f\leq\frac{1}{2}$, since $\mu\notin A$). The regret
is:

$\displaystyle\frac{\left|\mu\omega_{2}\right|}{\left|F\omega_{2}\right|}-\frac{\sphericalangle
D\mu E}{2\pi}.$

Figure 7: An illustration of the case
$E\notin{\mathrm{supp}}\left(\pi^{*}\right)$.$A$$\omega_{1}$$\omega_{2}$$\omega_{3}$$E$$D$$\mu$$F=(f,\frac{1-f}{\sqrt{3}})$$s$

Fix $F$ and let $D,E$ vary so that $DE$ passes through $F$, while keeping
$\frac{1}{4}\leq d\leq\frac{1}{2}$ and $0\leq e\leq\frac{2d}{6d-1}$. Consider
the regret as a function of $d$. Note that
$e=\frac{d\left(4f-1\right)}{f+3d-1}$. The regret equals:

$\displaystyle\frac{\left|\mu\omega_{2}\right|}{\left|F\omega_{2}\right|}-\frac{\sphericalangle
D\mu
E}{2\pi}=\frac{1}{2\left(1-f\right)}-\frac{1}{2\pi}{\mathrm{at}}\left(\frac{\frac{\sqrt{3}/6}{1/2-e}-\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}{1+\frac{\sqrt{3}/6}{1/2-e}\cdot\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}\right)=$
$\displaystyle\frac{1}{2\left(1-f\right)}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{d(e-1/3)-e/6}{d(1-e)+e/2-1/3}\right)=$
$\displaystyle\frac{1}{2\left(1-f\right)}-\frac{1}{2\pi}{\mathrm{at}}\left[\sqrt{3}\cdot\frac{d\left(d(4f-1)-\frac{f+3d-1}{3}\right)-\frac{d(4f-1)}{6}}{d\left(f+3d-1-d(4f-1)\right)+\frac{d(4f-1)}{2}-\frac{f+3d-1}{3}}\right]=$
$\displaystyle\frac{1}{2\left(1-f\right)}-\frac{1}{2\pi}{\mathrm{at}}\left[2\sqrt{3}\left(2f-1\right)\frac{d^{2}-\frac{d}{4}}{d^{2}\left(4(1-f)\right)+d\left(3f-\frac{5}{2}\right)+\frac{1-f}{3}}\right].$

The regret is continuous as a function of $d$; its derivative w.r.t. $d$ has
the same sign as (apart from finitely many values of $d$ for which the
derivative of the regret is not defined):

$\displaystyle-\left(2d-\frac{1}{4}\right)\left[d^{2}\left(4(1-f)\right)+d\left(3f-\frac{5}{2}\right)+\frac{1-f}{3}\right]+\left(d^{2}-\frac{d}{4}\right)\left[8d\left(1-f\right)+\left(3f-\frac{5}{2}\right)\right]=$
$\displaystyle
d^{2}\left(\frac{3}{2}-2f\right)-d\left(\frac{2}{3}\left(1-f\right)\right)+\frac{1-f}{12}.$

Recall that $\frac{1}{4}\leq d\leq\frac{1}{2}$ and $\frac{1}{4}\leq
f\leq\frac{1}{2}$ (because $\omega_{2}F$ contains $\mu$ and $F$ is inside
$\Delta\left(\Omega\right)$). The above function is decreasing for
$\frac{1}{4}\leq d\leq\frac{2\left(1-f\right)}{3\left(3-4f\right)}$ and is
increasing for $\frac{2\left(1-f\right)}{3\left(3-4f\right)}\leq
d\leq\frac{1}{2}$.191919Note that
$\frac{1}{4}\leq\frac{2\left(1-f\right)}{3\left(3-4f\right)}\leq\frac{1}{2}$
for $\frac{1}{4}\leq f\leq\frac{1}{2}$. Furthermore, its value at
$d=\frac{1}{4}$ is:

$\displaystyle\frac{1}{16}\left(\frac{3}{2}-2f\right)-\frac{1}{4}\cdot\frac{2}{3}\left(1-f\right)+\frac{1-f}{12}=\frac{1-4f}{96}\leq
0.$

Therefore, for a fixed $f$, the regret is maximized for a boundary value of
$d$: either for $d=\frac{1}{4}$ or for $d=\frac{1}{2}$. If $d=\frac{1}{4}$,
then necessarily $F=D$ and the regret is:

$\frac{\left|\mu\omega_{2}\right|}{\left|D\omega_{2}\right|}-\frac{\sphericalangle
D\mu E}{2\pi}=\frac{2}{3}-\frac{\sphericalangle D\mu
E}{2\pi}\leq\frac{2}{3}-\frac{\pi/3}{2\pi}=\frac{1}{2},$

as needed. If $d=\frac{1}{2}$, then the value of the regret (after algebraic
simplifications) is:

$\displaystyle\frac{1}{2\left(1-f\right)}-\frac{1}{2\pi}{\mathrm{at}}\left(\frac{3\sqrt{3}\left(2f-1\right)}{2f+1}\right)$

The derivative of this expression is (note that it is well-defined for every
$\frac{1}{4}\leq f\leq\frac{1}{2}$):

$\displaystyle\frac{1}{2\left(1-f\right)^{2}}-\frac{3\sqrt{3}}{2\pi}\cdot\frac{1}{1+\left(\frac{3\sqrt{3}\left(2f-1\right)}{2f+1}\right)^{2}}\cdot\frac{2\left(2f+1\right)-2\left(2f-1\right)}{\left(2f+1\right)^{2}}=$
$\displaystyle\frac{1}{2\left(1-f\right)^{2}}-\frac{6\sqrt{3}}{\pi\left(\left(2f+1\right)^{2}+27\left(2f-1\right)^{2}\right)}=\frac{1}{2\left(1-f\right)^{2}}-\frac{3\sqrt{3}}{2\pi\left(28f^{2}-26f+7\right)}=$
$\displaystyle\frac{\left(28\pi-3\sqrt{3}\right)f^{2}-\left(26\pi-6\sqrt{3}\right)f+\left(7\pi-3\sqrt{3}\right)}{2\pi\left(1-f\right)^{2}\left(28f^{2}-26f+7\right)}>0,$

where the last transition holds as both the numerator and the denominator are
positive for every $f\in\mathbb{R}$. Thus, given that $d=\frac{1}{2}$, the
regret is maximal for $f=\frac{1}{2}$, for which the regret is exactly
$\frac{1}{2}$, as desired.

To finish the proof, it remains to consider the case in which $A$ contains two
different extreme points of $\Delta\left(\Omega\right)$.202020If $A$ contains
no extreme points or all the extreme points of $\Delta\left(\Omega\right)$ –
the regret is $0$. If $s$ intersects $l$ at a boundary point of
$\Delta\left(\Omega\right)$, then Adversary can increase the regret by
rotating $l$ around that point in a way which decreases the area of $A$; this
way $u^{*}$ cannot decrease, while $u\left(\pi,u_{r}\right)$ decreases.
Therefore, it is enough to consider the case in which $s$ contains the unique
extreme point of $\Delta\left(\Omega\right)$ that is not in $A$. Assume
w.l.o.g. that $\omega_{2},\omega_{3}\in A$, while $\omega_{1}\notin A$ is an
endpoint of $s$. Then the second element of ${\mathrm{supp}}\left(\pi\right)$,
which belongs to $l$, is of the form $F=\left(f,\frac{f}{\sqrt{3}}\right)$ for
$f=\frac{3de}{2d+e}$ (see Figure 8). We must have $\frac{1}{2}\leq
f\leq\frac{3}{4}$, as the segment $\omega_{1}F$ contains $\mu$ and
$F\in\Delta\left(\Omega\right)$. The regret is:

$\displaystyle\frac{\left|\mu\omega_{1}\right|}{\left|F\omega_{1}\right|}-\frac{\sphericalangle
D\mu
E}{2\pi}=\frac{2d+e}{6de}-\frac{1}{2\pi}{\mathrm{at}}\left(\frac{\frac{\sqrt{3}/6}{1/2-e}-\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}{1+\frac{\sqrt{3}/6}{1/2-e}\cdot\frac{\sqrt{3}/6-\sqrt{3}d}{1/2-d}}\right)=\frac{2d+e}{6de}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{d(e-1/3)-e/6}{d(1-e)+e/2-1/3}\right).$

Figure 8: An illustration of the case $\omega_{2},\omega_{3}\in
A$.$A$$\omega_{1}$$\omega_{2}$$\omega_{3}$$E$$D$$\mu$$F=\left(f,\frac{f}{\sqrt{3}}\right)$$s$

Set $x:=de$ and $y:=2d+e$. Then the above expression equals (note that
$y=\frac{3x}{f}$):

$\displaystyle\frac{y}{6x}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{x-y/6}{y/2-x-1/3}\right)=\frac{1}{2f}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{x-x/(2f)}{(3x)/(2f)-x-1/3}\right)=$
$\displaystyle\frac{1}{2f}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{x\left(2f-1\right)}{x\left(3-2f\right)-2f/3}\right).$

Note that the angle $\sphericalangle D\mu E$ is obtuse for all feasible
choices of $x,f$; thus, for a fixed $f$, the above expression is continuously
differentiable w.r.t. $x$. The derivative of the expression inside
${\mathrm{at}}\left(\cdot\right)$ w.r.t. $x$ is:

$\displaystyle\sqrt{3}\frac{\left(2f-1\right)\cdot\left(-2f/3\right)}{\left(x\left(3-2f\right)-2f/3\right)^{2}}<0,$

as $f>\frac{1}{2}$. Therefore, for a fixed $f$, the regret is maximal for the
largest possible $x$. As $f=\frac{3x}{y}$, maximizing $x$ for a fixed $f$ is
equivalent to maximizing $x$ for a fixed $y$. By the AM-GM inequality,
$x\leq\frac{y^{2}}{8}$, with equality if and only if $2d=e$.212121The
geometric interpretation of this case is – $DE$ is parallel to
$\omega_{3}\omega_{2}$. When $2d=e$, we have
$f=\frac{3x}{y}=\frac{3y}{8}=\frac{3e}{4}$ and $x=\frac{e^{2}}{2}$;
furthermore, we must have $\frac{1}{2}\leq e\leq 1$, as $\mu\notin A$.
Assuming $2d=e$, the regret as a function of $e$ is:

$\displaystyle\rho\left(e\right):=\frac{2}{3e}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{e^{2}\left(3e/4-1/2\right)}{e^{2}\left(3/2-3e/4\right)-e/2}\right)=\frac{2}{3e}-\frac{1}{2\pi}{\mathrm{at}}\left(\sqrt{3}\cdot\frac{e\left(3e/4-1/2\right)}{e\left(3/2-3e/4\right)-1/2}\right).$

We have:

$\displaystyle\rho^{\prime}\left(e\right)=-\frac{2}{3e^{2}}-\frac{\sqrt{3}}{2\pi}\frac{1}{1+3\left(\frac{e\left(3e/4-1/2\right)}{e\left(3/2-3e/4\right)-1/2}\right)^{2}}\cdot$
$\displaystyle\frac{\left(3e/2-1/2\right)\left(e\left(3/2-3e/4\right)-1/2\right)-e\left(3e/4-1/2\right)\left(3/2-3e/2\right)}{\left(e\left(3/2-3e/4\right)-1/2\right)^{2}}=$
$\displaystyle-\frac{2}{3e^{2}}-\frac{\sqrt{3}}{2\pi}\frac{3e^{2}-3e+1}{\left(3e^{2}/2-3e+1\right)^{2}+3\left(3e^{2}/2-e\right)^{2}}<0.$

Hence, the maximum of $\rho\left(e\right)$ on $\left[\frac{1}{2},1\right]$ is
obtained for $e=\frac{1}{2}$. Since
$\rho\left(\frac{1}{2}\right)=\frac{1}{2}$, the regret is always at most
$\frac{1}{2}$, which completes our proof. ∎

##  Appendix B Proof of Theorem 3.5

###### Proof of Theorem 3.5.

We start by proving the lower bound. Assume $n\geq 16$ (otherwise the result
follows from Remark 3.3). Our proof constructs a difficult instance under
which any algorithm suffers a regret of at least $1-\frac{2}{\sqrt{n}}$. Fix
$0<\delta<\frac{\min_{i\in\Omega}\mu_{i}}{2n}$. Set
${\mathrm{supp}}_{\delta}\left(p\right):=\left\\{i\in\Omega:\Pr_{\omega^{\prime}\sim
p}\left[\omega^{\prime}=i\right]>\delta\right\\}$. Depending on what
Receiver’s utility a state leads to, we divide the $n$ states in our instance
into three types: a single _good_ state, $n-\lfloor\sqrt{n}\rfloor-1$ _normal_
states and $\lfloor\sqrt{n}\rfloor$ _bad_ states. Sender’s uncertainty about
Receiver’s utilities is captured by her uncertainty on the type of the true
state of nature $\omega$.

Suppose that Adversary chooses a uniform permutation on $\Omega$; then she
sets the first state in the permutation to be good, the next
$n-\lfloor\sqrt{n}\rfloor-1$ states to be normal and the rest to be bad.
Denote by $\mu_{\text{good}}$ the prior probability of the good state and by
$\mu_{\text{normal}}$ – the sum of the prior probabilities of the normal
states. Suppose that for $i\in\Omega$, $u_{r}\left(i,1\right)$ equals
$\frac{1}{\mu_{\text{good}}}$ if $i$ is good, $-\frac{1}{\mu_{\text{normal}}}$
if $i$ is normal and $-\frac{1}{\delta\cdot\mu_{\text{good}}}$ if $i$ is bad.
The utility choices ensure that:

  1. 1.

The expected Receiver’s utility knowing that the state is not bad is $0$.

  2. 2.

A posterior $p$ with a bad state in ${\mathrm{supp}}_{\delta}\left(p\right)$
leads to rejection.

  3. 3.

A posterior $p$ s.t. the good state is not in
${\mathrm{supp}}_{\delta}\left(p\right)$ leads to rejection, as then $p$ must
assign a probability of at least $\frac{1-\delta}{n-1}$ to a certain not good
state, resulting in Receiver’s utility being smaller than:

$\displaystyle\frac{\delta}{\mu_{\text{good}}}-\frac{1-\delta}{n-1}\cdot\frac{1}{\max\left\\{\delta\cdot\mu_{\text{good}},\mu_{\text{normal}}\right\\}}=\frac{\delta}{\mu_{\text{good}}}-\frac{1-\delta}{\mu_{\text{normal}}\left(n-1\right)}<$
$\displaystyle\frac{1}{2n\mu_{\text{normal}}}-\frac{1}{\mu_{\text{normal}}\left(n-1\right)}+\frac{1}{2\mu_{\text{normal}}\left(n-1\right)}<0.$

Had Sender known the type of each state, she could have used a signaling
scheme revealing whether the true state of nature $\omega$ is bad or not. This
scheme would have made Receiver adopt exactly for not bad values of $\omega$.
Thus, $u^{*}\geq 1-\frac{\lfloor\sqrt{n}\rfloor}{n}\geq 1-\frac{1}{\sqrt{n}}$.

We shall prove that our ignorant Sender cannot get a utility above
$\frac{1}{\sqrt{n}}$; it would imply
${\mathrm{Reg}}_{{\mathrm{AR}}}\geq\left(1-\frac{1}{\sqrt{n}}\right)-\frac{1}{\sqrt{n}}\geq
1-\frac{2}{\sqrt{n}}$, completing the proof. In fact, we shall show a stronger
result: for every Receiver’s posterior $p\in\Delta\left(\Omega\right)$, the
probability of adoption, under Adversary’s strategy, is at most
$\frac{1}{\sqrt{n}}$.

Indeed, fix some posterior $p\in\Delta\left(\Omega\right)$. We have the
following cases:

  * •

If
$\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|\leq\lfloor\sqrt{n}\rfloor$,
then the probability of having the good state in
${\mathrm{supp}}_{\delta}\left(p\right)$ is:
$\frac{\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|}{n}\leq\frac{\sqrt{n}}{n}=\frac{1}{\sqrt{n}}$.

  * •

Otherwise
($\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|>\lfloor\sqrt{n}\rfloor$),
the probability of not having a bad state – and meanwhile, having the good
state – in ${\mathrm{supp}}_{\delta}\left(p\right)$ is:

$\displaystyle\left(1-\frac{\lfloor\sqrt{n}\rfloor}{n}\right)\left(1-\frac{\lfloor\sqrt{n}\rfloor}{n-1}\right)...\left(1-\frac{\lfloor\sqrt{n}\rfloor}{n+1-\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|}\right)\cdot\min\left(\frac{\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|}{n-\lfloor\sqrt{n}\rfloor},1\right)\leq$
$\displaystyle\left(1-\frac{\lfloor\sqrt{n}\rfloor}{n}\right)^{\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|}\cdot\frac{\left|{\mathrm{supp}}_{\delta}\left(p\right)\right|}{n-\lfloor\sqrt{n}\rfloor}\leq\left(1-\frac{\lfloor\sqrt{n}\rfloor}{n}\right)^{\lfloor\sqrt{n}\rfloor+1}\cdot\frac{\lfloor\sqrt{n}\rfloor+1}{n-\lfloor\sqrt{n}\rfloor}\leq$
$\displaystyle
e^{-\frac{\lfloor\sqrt{n}\rfloor\left(\lfloor\sqrt{n}\rfloor+1\right)}{n}}\cdot\frac{\lfloor\sqrt{n}\rfloor+1}{n-\lfloor\sqrt{n}\rfloor}\leq\frac{1}{e^{1-1/\sqrt{n}}}\cdot\frac{\sqrt{n}+1}{n-\sqrt{n}}\leq_{n\geq
16}\frac{1}{\sqrt{n}},$

where the second inequality holds since
$\left(1-\frac{\lfloor\sqrt{n}\rfloor}{n}\right)^{x}\cdot x$ is non-increasing
as a function of the integer variable $x$ for $x\geq\lfloor\sqrt{n}\rfloor+1$,
because $1-\frac{\lfloor\sqrt{n}\rfloor}{n}\leq\frac{x}{x+1}$ for
$x\geq\lfloor\sqrt{n}\rfloor+1$.

Therefore, the expected adoption probability over Adversary’s strategy at
every posterior is at most $\frac{1}{\sqrt{n}}$, which completes the proof of
the lower bound.

Let us prove now the upper bound. Note that the full revelation scheme _fails_
to provide any regret guarantee for priors that have tiny masses on some of
the states. The regret guarantee of full revelation is as high as
$1-\min_{i\in\left[n\right]}\mu_{i}$.222222Indeed, if for some
$i\in\left[n\right]$ we have $u_{r}\left(i,1\right)=\frac{1}{\mu_{i}}$ and
$u_{r}\left(j,1\right)=-\frac{1}{1-\mu_{i}}$ for $j\neq i$, then the no-
information scheme leads to adoption w.p. 1, while the full-revelation scheme
leads to adoption w.p. $\mu_{i}$; therefore, the regret is $1-\mu_{i}$. We
shall prove that a modification of the full-revelation scheme s.t. every
signal realization pools at most two states has a regret guarantee of
$1-\frac{1}{4n^{2}}$ _for every prior_.

Define $U:=\left\\{i\in\Omega:\mu_{i}\geq\frac{1}{2n}\right\\}$. Note that
$\sum_{i\in U}\mu_{i}=1-\sum_{i\notin U}\mu_{i}\geq
1-\frac{n}{2n}=\frac{1}{2}$ (in particular, $U\neq\emptyset$).

Consider the signaling scheme $\pi$ with the set of signals
$S=\left\\{s_{i}:i\in\Omega\right\\}\cup\left\\{s_{i,j}:i\in
U,j\in\Omega\setminus U\right\\}$, s.t.:

  * •

For every $i\in U$, the signal $s_{i}$ is assigned a probability mass of
$\left(1-\frac{1}{2n}\right)\mu_{i}$ out of the prior probability of $\mu_{i}$
for $\omega=i$.

  * •

For every $i\in\Omega\setminus U$, the signal $s_{i}$ is assigned a
probability mass of $\frac{\mu_{i}}{2}$ out of the prior probability for
$\omega=i$.

  * •

For every $i\in U$, $j\in\Omega\setminus U$, the signal $s_{i,j}$ is assigned
a probability mass of $\frac{\mu_{i}}{2n\left(n-\left|U\right|\right)}$ out of
the prior probability for $\omega=i$ and a probability mass of
$\frac{\mu_{j}}{2\left|U\right|}$ out of the prior probability for $\omega=j$.

We claim that ${\mathrm{Reg}}_{{\mathrm{AR}}}\left(\pi\right)\leq
1-\frac{1}{4n^{2}}$. Indeed, fix $u_{r}$.232323The result for a mixture over
possible functions $u_{r}$ would follow by taking the expectation over
Adversary’s strategy. Define $T:=\left\\{i\in\Omega:u_{r}\left(i,1\right)\geq
0\right\\}$. Consider the following cases:

  * •

$T\cap U\neq\emptyset$. Since $s_{i}$ leads to adoption for every $i\in T$, in
this case
$u\left(\pi,u_{r}\right)\geq\frac{1}{2n}\cdot\left(1-\frac{1}{2n}\right)\geq\frac{1}{4n^{2}}$;
thus,
${\mathrm{Reg}}_{{\mathrm{AR}}}\left(\pi\right)=u^{*}\left(u_{r}\right)-u\left(\pi,u_{r}\right)\leq
1-\frac{1}{4n^{2}}$.

  * •

$T\cap U=\emptyset$, and for every $i\in U$ there exists
$j_{i}\in\Omega\setminus U$ s.t.
$\frac{\mu_{i}}{2n\left(n-\left|U\right|\right)}\cdot
u_{r}\left(i,1\right)+\frac{\mu_{j_{i}}}{2\left|U\right|}\cdot
u_{r}\left(j_{i},1\right)\geq 0$. Then $s_{i,j_{i}}$ yields to adoption for
every $i\in U$. We saw that $\sum_{i\in U}\mu_{i}\geq\frac{1}{2}$; thus,
adoption occurs w.p. at least $\sum_{i\in
U}\frac{\mu_{i}}{2n\left(n-\left|U\right|\right)}=\frac{\sum_{i\in
U}\mu_{i}}{2n\left(n-\left|U\right|\right)}\geq\frac{1}{4n^{2}}$, and again
the regret is at most $1-\frac{1}{4n^{2}}$.

  * •

$T\cap U=\emptyset$, and there exists $i\in U$ s.t. for every
$j\in\Omega\setminus U$: $\frac{\mu_{i}}{2n\left(n-\left|U\right|\right)}\cdot
u_{r}\left(i,1\right)+\frac{\mu_{j}}{2\left|U\right|}\cdot
u_{r}\left(j,1\right)<0$. Summing over $j\in\Omega\setminus U$ and multiplying
by $2\left|U\right|$ yields: $\frac{\left|U\right|}{n}\cdot\mu_{i}\cdot
u_{r}\left(i,1\right)+\sum_{j\in\Omega\setminus U}\mu_{j}\cdot
u_{r}\left(j,1\right)<0$. If $U=\Omega$, then adoption never occurs for any
signaling scheme and the regret is $0$. Otherwise, as
$T\subseteq\Omega\setminus U$, we get that even upon the knowledge of $u_{r}$,
a probability mass greater than
$\left(1-\frac{\left|U\right|}{n}\right)\cdot\mu_{i}\geq\frac{\mu_{i}}{n}\geq\frac{1}{2n^{2}}$
from the prior probability of $\mu_{i}$ for $\omega=i$ does not lead to
adoption. Therefore, $u^{*}\leq 1-\frac{1}{2n^{2}}\leq 1-\frac{1}{4n^{2}}$,
and
${\mathrm{Reg}}_{{\mathrm{AR}}}\left(\pi\right)=u^{*}\left(u_{r}\right)-u\left(\pi,u_{r}\right)\leq
1-\frac{1}{4n^{2}}$.

In all the cases, ${\mathrm{Reg}}_{{\mathrm{AR}}}\left(\pi\right)\leq
1-\frac{1}{4n^{2}}$, as desired. ∎

##  Appendix C Proof of Theorem 3.6

We start with the following lemma.

######  Lemma C.1.

Let $\alpha\in\left(0,1\right)$ be a constant. Let $G_{\alpha}$ be a two-
player zero-sum game with continuum action sets $X=Y=\left[0,1-\alpha\right]$
of the $x$\- (maximizing) and the $y$\- (minimizing) players, respectively,
and utility

$g\left(x,y\right):=\left(1-x\right)-\left(1-y\right)\mathbf{1}_{y\geq x}.$

Denote by $v={\mathrm{Val}}\left(G_{\alpha}\right)$ the value of $G_{\alpha}$.

  * •

For $\alpha\geq\frac{1}{e}$ we have $v=-\alpha\ln\alpha$. Furthermore, there
exists an optimal strategy
$o^{*}_{x}\in\Delta\left(\left[0,1-\alpha\right]\right)$ of the $x$-player
that has an atom of weight $\alpha$ on $x=0$ and otherwise has the density
function $f_{X}\left(x\right):=\frac{\alpha}{\left(1-x\right)^{2}}$ over the
entire segment $\left[0,1-\alpha\right]$. Moreover, there exists an optimal
strategy $o^{*}_{y}\in\Delta\left(\left[0,1-\alpha\right]\right)$ of the
$y$-player that has an atom of weight $1+\ln\alpha$ on $y=1-\alpha$ and
otherwise has the density function $f_{Y}\left(y\right):=\frac{1}{1-y}$ over
the entire segment $\left[0,1-\alpha\right]$.

  * •

For $\alpha<\frac{1}{e}$ we have $v=\frac{1}{e}$. Furthermore, there exists an
optimal strategy $o^{*}_{x}\in\Delta\left(\left[0,1-\alpha\right]\right)$ of
the $x$-player that has an atom of weight $\frac{1}{e}$ on $x=0$ and otherwise
has the density function
$f_{X}\left(x\right):=\frac{1}{e\left(1-x\right)^{2}}$ over the segment
$\left[0,1-\frac{1}{e}\right]$. Moreover, there exists an optimal strategy
$o^{*}_{y}\in\Delta\left(\left[0,1-\alpha\right]\right)$ of the $y$-player
that has the density function $f_{Y}\left(y\right):=\frac{1}{1-y}$ over the
segment $\left[0,1-\frac{1}{e}\right]$.

###### Proof of Lemma C.1.

Assume first that $\alpha\geq\frac{1}{e}$. We shall show that for the strategy
couple $\left(o^{*}_{x},o^{*}_{y}\right)$, both players are indifferent
between all actions in $\left[0,1-\alpha\right]$ and the payoff is
$-\alpha\ln\alpha$; therefore, $\left(o^{*}_{x},o^{*}_{y}\right)$ is an
equilibrium and $v=-\alpha\ln\alpha$. Indeed, every fixed
$x\in\left[0,1-\alpha\right]$ yields expected (over $y$) payoff of:

$\displaystyle\int_{0}^{1-\alpha}f_{Y}\left(y\right)g\left(x,y\right)dy+\Pr\left[y=1-\alpha\right]g\left(x,1-\alpha\right)=\int_{0}^{1-\alpha}\frac{1}{1-y}\cdot\left(1-x\right)dy-$
$\displaystyle\int_{x}^{1-\alpha}\frac{1}{1-y}\cdot\left(1-y\right)dy+\left(1+\ln\alpha\right)\cdot\left(1-x-\alpha\right)=-\left(1-x\right)\ln\alpha-\left(1-\alpha-x\right)+$
$\displaystyle\left(1+\ln\alpha\right)\left(1-x-\alpha\right)=-\alpha\ln\alpha.$

Furthermore, every fixed $y\in\left[0,1-\alpha\right]$ yields expected (over
$x$) payoff of:

$\displaystyle\int_{0}^{1-\alpha}f_{X}\left(x\right)g\left(x,y\right)dx+\Pr\left[x=0\right]g\left(0,y\right)=\int_{0}^{1-\alpha}\frac{\alpha}{\left(1-x\right)^{2}}\cdot\left(1-x\right)dx-$
$\displaystyle\int_{0}^{y}\frac{\alpha}{\left(1-x\right)^{2}}\cdot\left(1-y\right)dx+\alpha\cdot
y=-\alpha\ln\alpha-\left(1-y\right)\cdot\left(\frac{\alpha}{1-y}-\alpha\right)+\alpha\cdot
y=-\alpha\ln\alpha,$

as desired.

Assume now that $\alpha<\frac{1}{e}$. We shall show that for the strategy
couple $\left(o^{*}_{x},o^{*}_{y}\right)$, both players are indifferent
between the actions in $\left[0,1-\frac{1}{e}\right]$ – resulting in payoff of
$\frac{1}{e}$ – and worse off by taking other actions. Indeed, every fixed
$x\in\left[0,1-\frac{1}{e}\right]$ yields expected payoff of:

$\displaystyle\int_{0}^{1-1/e}f_{Y}\left(y\right)g\left(x,y\right)dy=\int_{0}^{1-1/e}\frac{1}{1-y}\cdot\left(1-x\right)dy-\int_{x}^{1-1/e}\frac{1}{1-y}\cdot\left(1-y\right)dy=$
$\displaystyle\left(1-x\right)\cdot
1-\left(1-\frac{1}{e}-x\right)=\frac{1}{e},$

while for a fixed $x\in\left(1-\frac{1}{e},1-\alpha\right]$, the expected
payoff is:

$\displaystyle\int_{1-1/e}^{1-\alpha}f_{Y}{dy}\left(y\right)g\left(x,y\right)dy=\int_{1-1/e}^{1-\alpha}\frac{1}{1-y}\cdot\left(1-x\right)dy=-\left(1+\ln\alpha\right)\left(1-x\right)<$
$\displaystyle-\left(1+\ln\alpha\right)\left(1-\left(1-\frac{1}{e}\right)\right)<\frac{1}{e},$

as desired. Moreover, every fixed $y\in\left[0,1-\frac{1}{e}\right]$ yields
expected payoff of:

$\displaystyle\int_{0}^{1-1/e}f_{X}\left(x\right)g\left(x,y\right)dx+\Pr\left[x=0\right]g\left(0,y\right)=\int_{0}^{1-1/e}\frac{1}{e\left(1-x\right)^{2}}\cdot\left(1-x\right)dx-$
$\displaystyle\int_{0}^{y}\frac{1}{e\left(1-x\right)^{2}}\cdot\left(1-y\right)dx+\frac{1}{e}\cdot
y=\frac{1}{e}\cdot
1-\frac{1-y}{e}\cdot\left(\frac{1}{1-y}-1\right)+\frac{1}{e}\cdot
y=\frac{1}{e},$

while for a fixed $y\in\left(1-\frac{1}{e},1-\alpha\right]$ we have:

$\displaystyle\int_{0}^{1-1/e}f_{X}\left(x\right)g\left(x,y\right)dx+\Pr\left[x=0\right]g\left(0,y\right)=\int_{0}^{1-1/e}\frac{1}{e\left(1-x\right)^{2}}\cdot\left(\left(1-x\right)-\left(1-y\right)\right)dx+$
$\displaystyle\frac{1}{e}\cdot
y=\frac{1}{e}\cdot\left(1-\left(1-y\right)\cdot\left(e-1\right)\right)+\frac{1}{e}\cdot
y=\frac{2}{e}-1+y>\frac{1}{e},$

as desired. ∎

###### Proof of Theorem 3.6.

Consider the two-player zero-sum game $G_{\mu_{n}}$ as described in Lemma C.1
and let $v$ be its value. We shall prove that $G$ (the zero-sum game
interpretation of regret minimization; see Subsection 2.2) also has value
equal to $v$.

First, let us show that Sender can ensure regret of at most $v$ by using the
signaling scheme $\pi_{y}$ defined as follows: Sender picks a random $y\sim
o^{*}_{y}$ (where $o^{*}_{y}$ is defined in Lemma C.1); then she uses the
$y$-threshold scheme (see Definition 2.3).

Indeed, fix $u_{r}$. By Fact 2.4, it defines an optimal threshold
$x=x\left(u_{r}\right)$ (in the standard persuasion model with the knowledge
of Receiver’s utility). Note that not all the values $x\in\left[0,1\right]$
might be the optimal threshold for some $u_{r}$, but only
$x\in\left[0,1-\mu_{n}\right]$. Indeed, the highest-utility state $n$ should
be included entirely in the knapsack, as otherwise adoption never occurs and
the regret is $0$. Assume, therefore, that $x\in\left[0,1-\mu_{n}\right]$.

We have $u^{*}=1-x$, and for every $y\in\left[0,1-\mu_{n}\right]$:
$u\left(\pi_{y},u_{r}\right)=\textbf{1}_{y\geq x}$, as Receiver adopts if and
only if $y\geq x$. Therefore, the regret for $\pi_{y}$ and $u_{r}$ is (where
$g$ is as defined in Lemma C.1):

$\displaystyle
u^{*}\left(u_{r}\right)-u\left(\pi_{y},u_{r}\right)=\mathbb{E}_{y\sim
o^{*}_{y}}\left[\left(1-x\right)-\left(1-y\right)\mathbf{1}_{y\geq
x}\right]=\mathbb{E}_{y\sim o^{*}_{y}}\left[g\left(x,y\right)\right].$

By Lemma C.1, the last expression is at most $v$. Therefore, Sender can ensure
that the regret is at most $v$ for any fixed $u_{r}$; thus, it holds also for
any mixture over $u_{r}$, as needed.

It remains to prove that Adversary can ensure a regret of at least $v$.
Consider the following strategy of Adversary: she deterministically sets
$u_{r}\left(i,1\right):=-\mu_{n}$ for all $1\leq i\leq n-1$; then she chooses
a random $t\sim o_{x}^{*}$ (with $o_{x}^{*}$ from Lemma C.1) and sets
$u_{r}\left(n,1\right):=1-\mu_{n}-t$. For this Adversary’s strategy, the
optimal threshold $x$ is distributed according to $o_{x}^{*}$. To bound the
regret that Sender can guarantee against this Adversary’s strategy, fix a
signaling scheme $\pi$. As $u_{r}\left(i,1\right)$ is the same for $1\leq
i\leq n-1$, one can refer to the states $1,2,...,n-1$ as a single state that
we call state $0$. Concretely, $\pi$ induces a signaling scheme $\pi^{\prime}$
in a persuasion scenario with a binary-state space $\left\\{0,n\right\\}$ s.t.
$\mu_{0}:=1-\mu_{n}$; a posterior
$p\left(s\right)\in\Delta\left(\left[n\right]\right)$ is mapped to the
posterior $\left(\sum_{1\leq i\leq n-1}p_{i},p_{n}\right)$. Therefore,
computing ${\mathrm{Reg}}_{{\mathrm{MON}}}\left(\pi\right)$ in our original
setting is reduced to computing
${\mathrm{Reg}}_{{\mathrm{MON}}}\left(\pi\right)$ in this binary-state
setting, with Adversary’s strategy being setting
$u_{r}\left(0,1\right):=-\mu_{n}$ deterministically and choosing
$u_{r}\left(n,1\right)=1-\mu_{n}-t$, where $t\sim o_{x}^{*}$.

From now on, we shall refer to a posterior
$p\in\Delta\left(\left\\{0,n\right\\}\right)$ as a real number
$q\in\left[0,1\right]$, where $q:=p_{0}$. To understand the optimal Sender’s
utility in this binary-state persuasion problem, we compute her expected
utility $u^{\prime}\left(q\right)$ (when the expectation is over Adversary’s
mixed strategy) for each possible posterior $q\in\left[0,1\right]$; then we
evaluate the concavification of $u^{\prime}$ at the prior $1-\mu_{n}$.

We shall prove that there exists Sender’s best-reply signaling scheme that is
a threshold signaling scheme. It would complete the proof, as the optimal
threshold $x$ is distributed according to $o_{x}^{*}$, which gives for a
Sender’s $y$-threshold scheme expected regret of:

$\displaystyle\mathbb{E}_{x\sim
o^{*}_{x}}\left[\left(1-x\right)-\left(1-y\right)\mathbf{1}_{y\geq
x}\right]=\mathbb{E}_{x\sim o^{*}_{x}}\left[g\left(x,y\right)\right],$

(with $g$ defined in Lemma C.1) which is, by Lemma C.1, at least $v$ for every
$y\in\left[0,1-\mu_{n}\right]$.242424We can assume w.l.o.g. that
$y\in\left[0,1-\mu_{n}\right]$, as the optimal threshold $x$ is at most
$1-\mu_{n}$; thus, choosing $y>1-\mu_{n}$ gives a greater regret than choosing
$y=1-\mu_{n}$.

Indeed, to understand Sender’s best-reply we shall consider a standard
Bayesian persuasion instance in which Sender’s utility is the expected (over
Adversary’s strategy) adoption probability. Sender’s expected utility, as a
function of Receiver’s posterior $q$, is:

$u^{\prime}\left(q\right):=\Pr_{t\sim
o^{*}_{x}}\left[-\mu_{n}q+\left(1-\mu_{n}-t\right)\left(1-q\right)\geq
0\right]=\Pr_{t\sim o^{*}_{x}}\left[t\leq 1-\frac{\mu_{n}}{1-q}\right].$

Straightforward calculations show that for $\mu_{n}\geq\frac{1}{e}$:

$\displaystyle u^{\prime}\left(q\right)=\begin{cases}1-q&\text{ if }0\leq
q\leq\mu_{0}\\\ 0&\text{ if }\mu_{0}<q\leq 1,\end{cases}$

while for $\mu_{n}<\frac{1}{e}$:

$\displaystyle u^{\prime}\left(q\right)=\begin{cases}1&\text{ if }0\leq
q<1-\mu_{n}e\\\ \frac{1-q}{\mu_{n}e}&\text{ if }1-\mu_{n}e\leq q\leq\mu_{0}\\\
0&\text{ if }\mu_{0}<q\leq 1.\end{cases}$

Figure 9: The function $u^{\prime}\left(q\right)$ and its concavification. The
function appears in blue; its concavification appears in red.

$\mu_{0}$1$q$$u^{\prime}$0$1$The case of $\mu_{n}\geq\frac{1}{e}$.

$\mu_{0}$1$q$$u^{\prime}$0$1$The case of $\mu_{n}<\frac{1}{e}$.

In both cases, $u^{\prime}\left(q\right)=0$ for $q>\mu_{0}$ and
$u^{\prime}\left(q\right)>0$ otherwise. Therefore, the graph of the
concavification of $u^{\prime}$ (see Figure 9) includes a line segment
connecting the point $\left(q=1,u^{\prime}\left(q\right)=0\right)$ with a
point having a value of $q$ smaller than $\mu_{0}$. Thus, there exists an
optimal Sender’s signaling scheme with binary signals s.t. one of them leads
to the posterior $q=1$ (i.e., certainty that $\omega=0$); this scheme is a
threshold scheme (see Definition 2.3), as desired. ∎

##  Appendix D Proof of Proposition 3.8

###### Proof of Proposition 3.8.

To describe the proof, we use the _fractional multidimensional knapsack
approach_. Consider the $k$-dimensional cube
$P:=\times_{j\in\left[k\right]}\left[1,n_{j}\right]$ with integer points
representing the elements of $\Omega$. A _knapsack_ $K$ is a closed subset of
$P$ s.t. for every $p\in K$, all the points that _Pareto-dominate_ $p$ are
also in $K$.252525A point $q=\left(q^{1},...,q^{k}\right)$ _Pareto-dominates_
$p=\left(p^{1},...,p^{k}\right)$ if $q^{j}\geq p^{j}$ for every $1\leq j\leq
k$. We define a _knapsack signaling scheme_ – the multidimensional variant of
a threshold scheme (see Definition 2.3) – as follows. Interpret $\Omega$,
equipped with the prior $\mu$, as drawing uniformly $p\in P$ – called the
_continuous state_ – s.t. all the realizations in
$\times_{j\in\left[k\right]}\left(\sum_{l_{j}<m_{j}}\Pr_{\omega_{j}^{\prime}\sim\mu_{j}}\left[\omega_{j}^{\prime}=l_{j}\right],\sum_{l_{j}\leq
m_{j}}\Pr_{\omega_{j}^{\prime}\sim\mu_{j}}\left[\omega_{j}^{\prime}=l_{j}\right]\right]$
correspond to the state $\left(m_{1},...,m_{k}\right)$ (when $1\leq m_{j}\leq
n_{j}$ for every $1\leq j\leq k$). For a knapsack $K$, the _$K$ -knapsack
signaling scheme_ is a binary-signal scheme revealing whether $p\in K$ or
not.262626The knapsack scheme specified by a knapsack with zero volume is the
no-information signaling scheme.

Consider the signaling scheme $\pi$ specified by the knapsack
$K_{\pi}:=\left\\{\left(p^{1},...,p^{k}\right)\in
P:p^{j}\geq\frac{n_{j}+1}{2}\forall 1\leq j\leq k\right\\}$. We claim that
$\pi$ ensures a regret of at most $1-2^{-k}$.

Indeed, if Adversary chooses $A$ s.t. every continuous state realization in
$K_{\pi}$ leads to adoption – Sender earns exactly $2^{-k}$. Since always
$u^{*}\left(u_{r}\right)\leq 1$, the regret is at most $1-2^{-k}$, as desired.

Otherwise, there exists some continuous state realization
$p=\left(p^{1},...,p^{k}\right)\in K$ leading to rejection. As
$\left(p^{1},...,p^{k}\right)\in K$, we have $p^{j}\geq\frac{n_{j}+1}{2}$ for
every $1\leq j\leq k$. Thus, no realization with the $j$-th coordinate being
at most $\frac{n_{j}+1}{2}$ for every $j$ leads to adoption. Similarly to the
single-dimensional setting, for a given $u_{r}$, there exists an optimal
knapsack signaling scheme. Had Sender known $A$, her optimal knapsack strategy
would have been specified by a knapsack $K^{*}$ disjoint to
$S:=\left\\{\left(q^{1},...,q^{k}\right)\in
P:q^{j}\leq\frac{n_{j}+1}{2}\forall 1\leq j\leq k\right\\}$. Such a strategy
yields adoption probability of at most
$1-\frac{{\mathrm{Vol}}\left(S\right)}{{\mathrm{Vol}}\left(P\right)}=1-2^{-k}$.
Therefore, the regret is at most $u^{*}\leq 1-2^{-k}$, as desired. ∎

##  Appendix E Proof of Theorem 4.2

We start with the following lemma.

######  Lemma E.1.

Let $\alpha\in\left(0,1\right)$ be a constant. Denote
$\beta=\beta\left(\alpha\right):=\frac{1}{1+\ln\frac{1}{\alpha}}$. Let
$G_{\alpha}^{\prime}$ be a two-player zero-sum game with continuum action sets
$X=Y=\left[0,1-\alpha\right]$ of the $x$\- (minimizing) and the $y$\-
(maximizing) players, respectively, and utility

$h\left(x,y\right):=\frac{\left(1-y\right)\mathbf{1}_{y\geq x}}{{1-x}}.$

Then the value of $G_{\alpha}^{\prime}$ is $\beta$. Furthermore, there exists
an optimal strategy
${o^{*}_{x}}^{\prime}\in\Delta\left(\left[0,1-\alpha\right]\right)$ of the
$x$-player that has an atom of weight $\beta$ on $x=0$ and otherwise has the
density function $f_{X}\left(x\right):=\frac{\beta}{1-x}$ over the entire
segment $\left[0,1-\alpha\right]$. Moreover, there exists an optimal strategy
${o^{*}_{y}}^{\prime}\in\Delta\left(\left[0,1-\alpha\right]\right)$ of the
$y$-player that has an atom of weight $\beta$ on $y=1-\alpha$ and otherwise
has the density function $f_{Y}\left(y\right):=\frac{\beta}{1-y}$ over the
entire segment $\left[0,1-\alpha\right]$.

###### Proof of Lemma E.1.

We shall show that for the strategy couple
$\left({o^{*}_{x}}^{\prime},{o^{*}_{y}}^{\prime}\right)$, both players are
indifferent between all actions in $\left[0,1-\alpha\right]$ and the payoff is
$\beta$; therefore, $\left({o^{*}_{x}}^{\prime},{o^{*}_{y}}^{\prime}\right)$
is an equilibrium and the game value is $\beta$. Indeed, every fixed
$x\in\left[0,1-\alpha\right]$ yields expected (over $y$) payoff of:

$\displaystyle\int_{0}^{1-\alpha}f_{Y}\left(y\right)h\left(x,y\right)dy+\Pr\left[y=1-\alpha\right]h\left(x,1-\alpha\right)=\int_{x}^{1-\alpha}\frac{\beta}{1-y}\cdot\frac{1-y}{1-x}dy+\beta\cdot\frac{1-\left(1-\alpha\right)}{1-x}=$
$\displaystyle\frac{\beta\left(1-\alpha-x\right)}{1-x}+\frac{\alpha\beta}{1-x}=\beta,$

as needed. Furthermore, every fixed $y\in\left[0,1-\alpha\right]$ yields
expected (over $x$) payoff of:

$\displaystyle\int_{0}^{1-\alpha}f_{X}\left(x\right)h\left(x,y\right)dx+\Pr\left[x=0\right]h\left(0,y\right)=\int_{0}^{y}\frac{\beta}{1-x}\cdot\frac{1-y}{1-x}dx+\beta\cdot\frac{1-y}{1-0}=$
$\displaystyle\beta\left(1-y\right)\left(\frac{1}{1-y}-1\right)+\beta\left(1-y\right)=\beta,$

as desired. ∎

###### Proof of Theorem 4.2.

Using the notations of Lemma E.1, consider the two-player zero-sum game
$G_{\mu_{n}}^{\prime}$; by the lemma, it has value of
$\beta:=\beta\left(\mu_{n}\right)=\frac{1}{1+\ln\frac{1}{\mu_{n}}}$. We claim
that the two-player zero-sum game interpretation of adversarial approximation
maximization, in which Sender is the maximizing player and her possible
strategies are the signaling schemes, and Adversary is the minimizing player
and her possible strategies are the mixtures over Receiver’s utility
functions, has value of $\beta$.

Using similar arguments to Theorem 3.6 proof, Sender can ensure adversarial
approximation of at least $\beta$ by using the signaling scheme $\pi_{y}$
defined as follows: Sender picks a random $y\sim{o^{*}_{y}}^{\prime}$; then
she uses the $y$-threshold scheme. The only difference from Theorem 3.6 proof
is that in the current proof, for a fixed $u_{r}$ and the corresponding
optimal threshold $x$, the expected adversarial approximation over $\pi_{y}$
is $\mathbb{E}_{y\sim o^{*}_{y}}\left[h\left(x,y\right)\right]$ (for $h$ from
Lemma E.1).

It remains to prove that Adversary can ensure an adversarial approximation of
at most $\beta$. As in Theorem 3.6 proof, it is enough to prove that Adversary
can ensure an adversarial approximation of at most $\beta$ in a persuasion
scenario with a binary-state space $\left\\{0,n\right\\}$ s.t.
$\mu_{0}:=1-\mu_{n}$ by using the following strategy:
$u_{r}\left(0,1\right):=-\mu_{n}$ deterministically;
$u_{r}\left(n,1\right):=1-\mu_{n}-t$, where $t\sim o_{x}^{*}$.

We shall refer to a posterior $p\in\Delta\left(\left\\{0,n\right\\}\right)$ as
a real number $q\in\left[0,1\right]$, where $q:=p_{0}$. As in Theorem 3.6
proof, we compute Sender’s expected utility $u^{\prime}\left(q\right)$ (the
expectation is over Adversary’s mixed strategy) for each possible posterior
$q\in\left[0,1\right]$, and then we evaluate the concavification of
$u^{\prime}$ at the prior $1-\mu_{n}$. Again, it is enough to prove that there
exists Sender’s best-reply signaling scheme that is a threshold scheme.

Indeed, to understand Sender’s best-reply we can consider a standard Bayesian
persuasion instance in which Sender’s utility is the expected – over
Adversary’s strategy – ratio of the indicator whether adoption occurs at the
posterior $q$ to the optimal adoption probability upon knowing $t$. Sender’s
expected utility, as a function of the posterior $q$, is:

$u^{\prime}\left(q\right):=\mathbb{E}_{t\sim
o^{*}_{x}}\left[\frac{\mathbbm{1}_{-\mu_{n}q+\left(1-\mu_{n}-t\right)\left(1-q\right)\geq
0}}{1-t}\right]=\mathbb{E}_{t\sim o^{*}_{x}}\left[\frac{\mathbbm{1}_{t\leq
1-\frac{\mu_{n}}{1-q}}}{1-t}\right].$

Straightforward calculations show that (see Figure 10):

$\displaystyle
u^{\prime}\left(q\right)=\begin{cases}\frac{\beta\left(1-q\right)}{\mu_{n}}&\text{
if }0\leq q\leq\mu_{0}\\\ 0&\text{ if }\mu_{0}<q\leq 1.\end{cases}$

Therefore, there exists an optimal signaling scheme at the prior that uses the
posterior $q=1$, which is, in particular, a threshold scheme, as needed.

Figure 10: The function $u^{\prime}$ (appears in blue) and its concavification
(appears in red).$\mu_{0}$1$q$$u^{\prime}$0$\frac{\beta}{\mu_{n}}$

∎