# Almost-Bayesian Quadratic Persuasion (Extended Version)

Olivier Massicot and Cédric Langbort Submitted on .O. Massicot is with the
Coordinated Science Laboratory, Urbana, IL 61801 USA (e-mail:
om3@illinois.edu). C. Langbort is with the Coordinated Science Laboratory,
Urbana, IL 61801 USA (e-mail: langbort@illinois.edu).

###### Abstract

In this article, we relax the Bayesianity assumption in the now-traditional
model of Bayesian Persuasion introduced by Kamenica & Gentzkow. Unlike
preexisting approaches—which have tackled the possibility of the receiver
(Bob) being non-Bayesian by considering that his thought process is not
Bayesian yet known to the sender (Alice), possibly up to a parameter—we let
Alice merely assume that Bob behaves ‘almost like’ a Bayesian agent, in some
sense, without resorting to any specific model.

Under this assumption, we study Alice’s strategy when both utilities are
quadratic and the prior is isotropic. We show that, contrary to the Bayesian
case, Alice’s optimal response may not be linear anymore. This fact is
unfortunate as linear policies remain the only ones for which the induced
belief distribution is known. What is more, evaluating linear policies proves
difficult except in particular cases, let alone finding an optimal one.
Nonetheless, we derive bounds that prove linear policies are near-optimal and
allow Alice to compute a near-optimal linear policy numerically. With this
solution in hand, we show that Alice shares less information with Bob as he
departs more from Bayesianity, much to his detriment.

Bayesian persuasion, Game theory, Communication networks, Uncertain systems

##  1 Introduction

Over the past few years, problems related to strategic information
transmission (SIT), which were originally introduced and studied in the field
of Information Economics, have gained relevance and garnered interest in the
decision & control, information theory, and computer science communities as
well. New applications of SIT ideas, concepts and modeling paradigms in these
domains include, e.g., adversarial sensing and estimation [1, 2, 3],
persuasive interactions between humans and autonomous agents/vehicles [4, 5,
6] and congestion mitigation [7, 8, 9, 10, 11, 12, 13], while tools from these
fields have made it possible to investigate richer SIT problem formulations
such as communication over limited communication channels [14, 15] and
algorithmic approaches [16].

The now canonical model of Bayesian Persuasion introduced by Kamenica &
Gentzkow [17] considers two actors, one of whom, the Sender, has access to the
state of the world and wants to convince the other actor, the uninformed
Receiver, to take actions that benefit her. In accordance with Information and
Computer Theoretic practice we will henceforth refer to the Sender as “Alice”
and to the Receiver as “Bob.”

The setup of [17] has two crucial features. First, Alice is assumed to commit
to a signaling strategy, which makes the game she plays with Bob a Stackelberg
one in which she acts as the leader, and distinguishes it from the cheap-talk
formulation of [18] which is concerned with perfect Bayesian equilibria. This
commitment assumption essentially defines the Bayesian Persuasion framework
and is present in all extensions of [17], from those considering multiple
senders [19] and/or receivers [20, 21], to costly messages [22] and online
settings [23, 21, 24], to the possibility of Bob acquiring additional
information [25, 26, 27].

The second crucial element in [17] is the assumption that Bob is Bayesian,
i.e., that he updates his prior into a posterior using Bayes’ rule upon
receiving Alice’s message. This Bayesianity not only delineates the kind of
situations captured by the model, but also plays a central role in enabling
the computation of Alice’s signaling policy. Indeed, exploiting a result of
Aumann & Maschler [28], Kamenica & Gentzkow show how to fully parametrize the
set of posteriors that can be held by Bob upon receiving a message from Alice
which, in turn, makes it possible to reformulate her program into a
theoretically tractable form. This reformulation and, hence, Bob’s
Bayesianity, have been instrumental in most methods aimed at determining
Alice’s policy (such as, e.g., [16, 29, 25, 30]).

Given the importance of the specific way in which Bob is assumed to update his
prior in [17], multiple recent works such as, e.g., [31, 26, 27, 32, 33] have
tried to reconcile the framework of [17] with the empirical fact (confirmed in
many behavioral economics experiments such as [34, 35]) that human decision
makers can and often do fail to be perfectly Bayesian, either through lack of
access to a correct prior, or by accessing or incorrectly (according to Bayes’
rule) processing information.

The present work is closest in spirit to [31] in the sense that we directly
consider Bob to be non-Bayesian. In contrast with most of this article,
however, we do not make any explicit assumption regarding the process
replacing Bayes rule. Instead, we model Bob’s possible posteriors via a
generic _robust hypothesis_ , in a manner resembling the notion of an almost-
maximizing agent [36]. More precisely, we assume that, upon receiving Alice’s
message, Bob’s posterior lies in a suitably defined neighborhood of the
correct Bayesian posterior, regardless of the specific way in which it was
computed. In so doing, we formalize the notion of “almost-Bayesianity”
suggested at the end of [31] and set ourselves apart from other models which
either rely on parametric uncertainty (which assume that Bob’s thought process
is known to Alice, save for a set of parameters such as unknown mismatched
prior [32, 33]) or make Alice account for the fact that Bob may receive
private side information, be it before [27] or after [26] her message.

While we believe that this robust hypothesis approach has potential to model
lack of Bayesianity in general persuasion and SIT problems, we focus on a
particular linear quadratic setting in this work. This is to emphasize that
the operationalization of the notion of neighborhood of posteriors held by Bob
matters for the resolution of Alice’s program, as well as because even this
relatively simple case presents interesting non-trivial features: much like
the celebrated Witsenhausen’s counterexample [37], it presents a “linear-
quadratic-Gaussian” situation in which linear policies may not be optimal. In
addition, and in contrast with Witsenhausen’s counterexample, finding the
optimal linear policy is itself challenging.

More precisely, we consider the specific class of Bayesian persuasion games
introduced by [38], which has also seen many variants and applications [39,
40, 41]. In this setting, the state of the world $x$ is a random vector, Bob’s
action $a$ is an affine function of his estimation, and Alice receives a
reward quadratic in $(x,a)$. Naturally, this is referred to as linear-
preference quadratic-reward Bayesian persuasion, or quadratic persuasion to
remain concise. Under these assumptions, Alice’s objective is linear in the
covariance of the estimate, although the set of covariances Alice can induce
is unclear for general priors. When the prior $\nu$ is Gaussian, this set is
simply determined by two linear matrix inequalities, as shown in [38]. Little
is known otherwise, and in fact, even when $\nu$ is finitely supported, one
must resort to a relaxation of the program, [40]. We first extend the results
of [38] to slightly richer priors, then set to study the case where Bob is
almost Bayesian.

In order to set the stage for this class of problems, we first present, in
Section 2, a solvable example of linear-quadratic communication problem in
which the receiver is not exactly Bayesian. Section 3 then presents the
general problem of interest; we recall Bayesian persuasion, introduce the
abstract notion of almost-Bayesian agent, and further develop quadratic
persuasion. In Section 4, we provide a more concrete characterization of
almost-Bayesian agents in the present context. Tractability concerns push us
to adopt an “ellispoidal” hypothesis to contain Bob’s erroneous beliefs, under
which we provide optimistic and pessimistic bounds matching up to a
multiplicative ratio. Section 5 is dedicated to analyzing the approximate
programs; we first derive important structural facts, then propose a numerical
solution. Section 6 first confronts our approximation bounds with two
analytically solvable cases, whereas its last subsection illustrates the
structural results obtained in previous sections. Finally, Section 7 discusses
the significance of our results.

##  2 A tractable example

###  2.1 A simple strategic communication problem

Let us consider the following persuasion game. The state of nature $x$ is a
random variable in $\mathbb{R}^{n}$ distributed according to the standard
multivariate Gaussian distribution $\mathcal{N}(0,I_{n})$. Alice knows the
realization of this random variable and wants to send a message $y$ so as to
lead Bob to estimate $kx$, where $k$ is a constant real number. More
precisely, if Bob estimates $\hat{x}=\mathbb{E}[x\\!\mid\\!y]$, her associated
cost is $\|\hat{x}-kx\|^{2}$.

As is customary in Bayesian persuasion, the message $y$ is a random variable
whose conditional distribution given $x$ is fixed, chosen in advance by Alice
and known to Bob. In other words, Alice commits to a disclosing mechanism (a
policy), this in turn allows a Bayesian agent to update his prior belief to a
posterior belief. The problem Alice faces is to find the optimal policy,
namely the conditional law for $y$ given $x$ that minimizes her expected cost.
In all generality, this could be a challenging problem, however in this simple
example, it is quite easy to derive.

This derivation mostly relies on the specificity of the problem: Alice’s
reward is quadratic in Bob’s action ($\hat{x}$), and Bob’s action is affine in
the estimate $\hat{x}$. The study of such problems is the scope of linear-
preference quadratic-reward persuasion as introduced by [38]. In our specific
example,

$\displaystyle\mathbb{E}[\|\hat{x}-kx\|^{2}]$
$\displaystyle=\operatorname{Tr}\Sigma-2k\operatorname{Tr}\mathbb{E}[\hat{x}x^{\top}]+k^{2}\operatorname{Tr}I_{n}$
$\displaystyle=\operatorname{Tr}\Sigma-2k\operatorname{Tr}\mathbb{E}[\mathbb{E}[\hat{x}x^{\top}\\!\mid\\!\hat{x}]]+k^{2}n$
$\displaystyle=(1-2k)\operatorname{Tr}\Sigma+k^{2}n,$

where $\Sigma$ is the covariance of $\hat{x}$. In general however, the
objective takes a more defined form, $\operatorname{Tr}(D\Sigma)+c$, where $D$
is a constant symmetric matrix and $c$ is a constant real number.

For now, notice that $\Sigma\succeq 0$ as it is the covariance of $\hat{x}$,
and notice that $I_{n}-\Sigma\succeq 0$ as it is the covariance of
$x-\hat{x}$. On the other hand $\Sigma=0$ can be produced by the “no-
information policy,” sending $y=0$ at all time, whereas $\Sigma=I_{n}$ results
from the “full-information policy,” signaling $y=x$ as then $\hat{x}=y=x$. As
a result, either $1-2k>0$, $\Sigma=0$ is the only solution, sending no
information is optimal; either $1-2k=0$, this is a degenerate case where all
policies yield the same reward; or $1-2k<0$, $\Sigma=I_{n}$ is the unique
solution, achieved by the full-information policy.

This instance is in accordance with the general theory of linear-preference
quadratic-reward persuasion with Gaussian priors: there always exists a noisy
linear policy (i.e. $y=Ax+v$ for some matrix $A$ and $v$ an independent normal
variable) that is optimal. In fact, once the mean and covariance of $x$ have
been reduced to $0$ and $I_{n}$ respectively, one can even take $A$ orthogonal
projection matrix and $v=0$ without loss of generality, we term such policies
“projective policies.” One can wonder whether this stands when Bob is not
truly Bayesian.

###  2.2 When Bob is not Bayesian

The previous derivation, and in fact linear-preference quadratic-reward
persuasion, both rely on the fact that Bob is Bayesian. For the purposes of
this motivating example, we may relax this assumption by simply assuming that
Bob’s estimate $\tilde{x}$ is never farther than $\epsilon>0$ from $\hat{x}$,
and let Alice plan for the worst.

Concretely, Alice can first express her expected cost by using the towering
property of expectation as

$\mathbb{E}[\|\hat{x}-kx\|^{2}]=\mathbb{E}[\mathbb{E}[\|\hat{x}-kx\|^{2}\\!\mid\\!y]].$

She can then assume that Bob’s erroneous estimate $\tilde{x}$ at each $y$
maximizes her conditional cost, namely her goal is to minimize

$\mathbb{E}\\!\left[\max_{\tilde{x}\in\hat{x}+\epsilon\mathcal{B}}~{}\mathbb{E}[\|\tilde{x}-kx\|^{2}\\!\mid\\!y]\right],$

having denoted the closed Euclidean unit-ball by $\mathcal{B}$. The inner
maximization can be developed, noting the error $\eta=\tilde{x}-\hat{x}$,

$\displaystyle\mathbb{E}[\|\tilde{x}-kx\|^{2}\\!\mid\\!y]$
$\displaystyle=\mathbb{E}[\|\eta+\hat{x}-kx\|^{2}\\!\mid\\!y]$
$\displaystyle=\|\eta\|^{2}+2(1-k)\eta^{\top}\hat{x}+\mathbb{E}[\|\hat{x}-kx\|^{2}\\!\mid\\!\hat{x}].$

The last term does not depend on $\eta$, we can take it out of the
maximization and average it, it becomes the original Bayesian objective. All
in all, Alice tries to minimize

$(1-2k)\operatorname{Tr}\Sigma+k^{2}n+\mathbb{E}\\!\left[\max_{\eta\in\epsilon\mathcal{B}}~{}\|\eta\|^{2}+2(1-k)\eta^{\top}\hat{x}\right].$

In this simple illustrative example (and in contrast to the general case), the
nested maximum can be analytically found. Therefore, Alice seeks to minimize

$(1-2k)\operatorname{Tr}\Sigma+k^{2}n+\epsilon^{2}+2\epsilon|1-k|\mathbb{E}[\|\hat{x}\|].$
(1)

The program is now much more complicated as the objective picked up a term in
the mean absolute deviation, $\mathbb{E}[\|\hat{x}\|]$. However, when
$k\leq\nicefrac{{1}}{{2}}$, it appears that, just like in the Bayesian case,
sending no information is optimal. When $k=1$, the last term in (1) vanishes
and so sending the information wholly is optimal, again just like when Bob is
Bayesian. In the remainder of this section, we thus consider cases where
$k>\nicefrac{{1}}{{2}}$ and $k\neq 1$, so that there is an antagonism between
maximizing $\operatorname{Tr}\Sigma=\mathbb{E}[\|\hat{x}\|^{2}]$ and
minimizing $\mathbb{E}[\|\hat{x}\|]$.

The following two subsections delve into the details of how to find the
optimal linear policy, and explore quantizations as an other alternative.
Together, they prove the following maybe surprising result.

######  Lemma 1.

The linear policy achieving the lowest value of (1) (i.e. Alice’s “optimal
linear policy”) is either no- or full-information, with value

$k^{2}n+\epsilon^{2}+\Big{(}(1-2k)n+2\epsilon|1-k|\,\mathbb{E}[\|x\|]\Big{)}^{-},$

where $(.)^{-}=\min(.,0)$. When $k>\nicefrac{{1}}{{2}}$ is different than $1$
and $\epsilon$ is large enough, this amounts to $k^{2}n+\epsilon^{2}$. For all
these $k$, there exists a quantization-based policy whose value is strictly
better.

In other words, even if we can find the optimal linear policy—and this is
quite challenging in general—, it may not be optimal over all.

###  2.3 Linear policies with noise

It is quite difficult to envision which pairs
$(\operatorname{Tr}\Sigma,\mathbb{E}[\|\hat{x}\|])$ Alice can produce through
signaling. We can nonetheless explore noisy linear policies with a certain
ease. When $y=Ax+v$ is sent, where $A$ is a matrix and $v$ an independent
normal random variable, $\hat{x}$ is normal as well so

$\mathbb{E}[\|\hat{x}\|]=\mathbb{E}[\sqrt{z^{\top}\Sigma z}],$

where $z\sim\mathcal{N}(0,I_{n})$ is a dummy standard variable. As all
covariances $0\preceq\Sigma\preceq I_{n}$ can be produced with such noisy
linear policies [38], the program of Alice can be written entirely in terms of
$\Sigma$. In other words, after dropping the constant terms, she is interested
in solving

$\min_{0\preceq\Sigma\preceq
I_{n}}~{}(1-2k)\operatorname{Tr}\Sigma+2\epsilon|1-k|\mathbb{E}[\sqrt{z^{\top}\Sigma
z}].$ (2)

Since the objective is strictly concave in $\Sigma$, solutions are all extreme
points of the constraint set, namely they are orthogonal projection matrices.
Moreover, the objective is invariant by rotation (namely $\Sigma$ and $O\Sigma
O^{\top}$ have the same value when $O$ is orthogonal), thus the objective
value at an extreme point depends only on its rank $r$. After further
inspection, the objective is concave in $r$, thus the solution is either
$\Sigma=0$ (the no-information policy), or $\Sigma=I_{n}$ (the full-
information policy). Plugging values corresponding to both policies in (2)
shows that when $\epsilon$ is large enough, Alice chooses to not disclose any
information.

The lowest cost Alice can get with linear policies is thus

$k^{2}n+\epsilon^{2}+\Big{(}(1-2k)n+2\epsilon|1-k|\,\mathbb{E}[\|x\|]\Big{)}^{-}.$

At fixed $k$, when $\epsilon$ is large enough the expression in brackets is
positive and so her optimal linear cost becomes $k^{2}n+\epsilon^{2}$.

###  2.4 An outperforming quantization-based policy

$X_{0}$$X_{+1}$$X_{-1}$$X_{+2}$$X_{-2}$$e_{1}$$e_{2}$$R$$x_{R}$ Figure 1: A
partition of $\mathbb{R}^{2}$.

Alice could consider another type of message: she sets a partition
$(X_{\alpha})_{\alpha}$ of $\mathbb{R}^{n}$, and signals $y=\alpha$ when $x\in
X_{\alpha}$. One simple partition has $X_{0}=[-R,R]^{n}$ and $X_{\pm i}$ is
the region beyond the face $\pm e_{i}$ of the cube $X_{0}$ (considering a
central projection, centered at the origin, see Figure 1 for $n=2$). In this
case, the estimate knowing that $x\in X_{0}$ is $\hat{x}(0)=0$ and the
estimate knowing that $x\in X_{\pm i}$ is

$\hat{x}(\pm i)=\mathbb{E}[x\\!\mid\\!x\in X_{\pm i}]=\pm x_{R}e_{i},$

where $x_{R}>R\geq 0$.

We let $p_{R}>0$ be the probability of $x$ belonging to each $X_{\pm i}$.
Finding an expression of $p_{R},x_{R}$ is relatively easy when $n=1$ but
rather cumbersome otherwise. Nonetheless, we know that $x_{R}>R$ and this will
be enough to illustrate our point.

We can work on the objective given in (1) without the constant terms,

$\displaystyle(1-2k)\operatorname{Tr}\Sigma+2\epsilon|1-k|\mathbb{E}[\|\hat{x}\|]$
$\displaystyle\quad=(1-2k)(2np_{R}x_{R}^{2})+2\epsilon|1-k|(2np_{R}x_{R})$
$\displaystyle\quad\leq(2np_{R}x_{R})(2\epsilon|1-k|-(2k-1)R),$

this can be made negative for $R$ large enough, no matter $\epsilon$.
Therefore, the optimal value of Alice’s program without restricting it to
linear policies is strictly better than $k^{2}n+\epsilon^{2}$, which is the
value of the best linear policy. For $\epsilon$ large enough, this means that
linear policies are not optimal.

###  2.5 Discussion and a preview of things to come

In summary, there is a class of Bayesian persuasion problems, for which
optimal solutions are easily computed. Moreover, these solutions have a
specific form: not only are they noisy linear policies, they are projective,
that is they mute some channels by projecting the state $x$ orthogonally. When
the Bayesian assumption is relaxed, however, the optimal policy fails to
remain linear.

This fact may seem reminiscent of the Witsenhausen counterexample, but with
the important distinction that in the current situation even computing the
optimal linear strategy is challenging. Indeed, the example presented above
was chosen specifically because it could be solved in closed form, and there
are multiple hurdles in the general case. The inner maximization cannot be
solved analytically, and yet we are to take its average over all $\hat{x}$,
and finally optimize over all policies.

Nonetheless, in this article we strive to do just this, with few caveats. By
framing the non-Bayesian term between two bounds whose ratio is close to two,
we obtain a pessimistic and an optimistic program. The pessimistic program
provides an upper bound that holds for all policies, linear or not, yet
surprisingly is solved by a projective policy. Since Alice prepares for the
worst, this is the program that she solves. The bound on which the optimistic
program relies, on the other hand, is only obtained for projective policies,
thus we can only guarantee that the pessimistic solution is almost optimal
with respect to projective policies. This being said, we can still write a
meaningful optimistic program for general policies, which is stronger than the
mere Bayesian program. In some cases that are easily identified from the
parameters of the problem, the projective optimistic bound holds for general
policies as well. In these cases, this establishes that the pessimistic
solution is nearly optimal. Note that this still does not imply that
projective policies are optimal, merely that they are almost optimal.

##  3 General problem of interest

For the purposes of making this paper self-contained, we start by reviewing
the basic formulation of Bayesian persuasion from [17], before introducing and
justifying the almost-Bayesian framework. We also review and expand the
specific linear-quadratic persuasion setting first studied in [38].

###  3.1 Review of Kamenica & Gentzkow’s setup

As mentioned in the introduction, a Bayesian persuasion game consists of two
players. Alice, the sender, has access to more information than Bob, the
receiver, and reveals her information according to an established scheme.
After receiving the message, Bob interprets it and plays an action in order to
minimize his expected cost. This action defines the loss of Alice.

To fix things, consider $(\Omega,\mathcal{F},\nu)$ a probability space,
$\mathcal{A}$ an action set for Bob, $\mathcal{M}$ a message space for Alice,
and $\mathcal{P}(\mathcal{M})$ a space of probability measures on
$\mathcal{M}$. The loss of both receiver and sender, $u(a,\omega)$ and
$v(a,\omega)$ respectively, depend on the action taken by Bob $a$ and on
$\omega$, the state of the world, observed by Alice.

Alice having chosen a disclosing mechanism
$\sigma\colon\Omega\to\mathcal{P}(\mathcal{M})$, Bob, when Bayesian, can
compute his expected cost with respect to the conditional probability (the
posterior belief). His action will then be

$a(m)\in\operatorname*{arg\,min}_{a\in\mathcal{A}}~{}\mathbb{E}[u(a,\omega)\\!\mid\\!m].$

Note that this only depends on the probability law $\mathbb{P}[.\\!\mid\\!m]$.
To emphasize this, we denote by $\mu$ the posterior belief held by Bob. Thus,
the action of Bob is actually $a(\mu)$ (if he is indifferent, we let him
choose the action that is most favorable to Alice). Further denote by $\tau$
the distribution of posteriors. The expected utility of Alice is now

$\mathbb{E}_{\tau}[\mathbb{E}_{\mu}[v(a(\mu),\omega)]]=\mathbb{E}_{\tau}[\underset{\triangleq\hat{v}(\mu)}{\underbrace{v(a(\mu),\mu)}}],$

where we used the standard notation $v(.,\mu)=\mathbb{E}_{\mu}[v(.,\omega)]$.

As pointed out in [17], exploring the case where $\Omega$ is finite, it is
illuminating to write Alice’s program with the distribution $\tau$ of
posteriors as a variable for two reasons. First, the objective depends
affinely in $\tau$, second the set $\mathcal{T}_{\nu}$ of distributions of
posteriors that can be generated by a policy from the prior $\nu$, is easily
described, again affinely in $\tau$. Both facts have geometric consequences
which bring new light to the structure of the program. At a higher level, this
simply means that Alice may instead focus on $\tau$, solve

$\min_{\tau\in\mathcal{T}_{\nu}}~{}\mathbb{E}_{\tau}[\hat{v}(\mu)],$ (3)

and later retrieve $\sigma$.

Characterizing $\mathcal{T}_{\nu}$ when $\nu$ is not finitely supported is
challenging, nonetheless it is worth noting that in some cases the statistics
relevant for the objective that are embedded in $\tau$ can be described
simply. Gentzkow and Kamenica [29] explore this when $\Omega=\mathbb{R}$,
Bob’s response depends only on his estimate of the state, and Alice’s loss is
state-independent. More relevantly to the present work, in linear-preference
quadratic-reward persuasion, only the covariance of the estimate matters and
in some cases their range is well-known.

###  3.2 Approximate Bayesianity

While (3) is instrumental in revealing the structure of Alice’s optimal
messaging policy for some families of function $\hat{v}$, it is only available
when Bob is truly Bayesian. One way in which this assumption may fail to hold
is if Bob is trying to apply Bayes rule, yet fails because, e.g., he makes
computations errors in doing so, if the computation is costly, or if the
representation of the posterior distributions are not accurate in the formula.
Alternatively, if one thinks of this game as a stage of a repeated process in
which $\sigma$ is learned over time, there might be an error in Bob’s
learning, resulting in the use of an erroneous $\sigma$ in (a possibly
otherwise correct) Bayes’ rule…

A natural question, then, is to try and characterize the posterior beliefs
that Bob may hold, as a result of such errors. To this end, we consider that
Bob’s erroneous posterior lies within a given safety set, parametrized by the
Bayesian posterior, formally

$\mu^{\prime}\in\Lambda(\mu),$

without further specifying how $\mu^{\prime}$ is generated. This idea appeared
recently in the literature, for instance as a generalization of parametric
models, [31]. One can think of $\Lambda(\mu)$ as the set of posteriors Alice
finds credible. We will refer to the correspondence $\Lambda$ as Alice’s
_robust hypothesis._ Realizing Bob will fail to produce accurate posteriors,
Alice may want to account for the worst of his possible mistakes. To do so,
Alice could expect a worst-case loss for each belief $\mu$,

$\hat{v}^{\prime}(\mu)\triangleq\sup_{\mu^{\prime}\in\Lambda(\mu)}v(a(\mu^{\prime}),\mu).$

This would naturally lead to a “classical” Bayesian persuasion program such as
(3), with $\hat{v}^{\prime}$ replacing $\hat{v}$, i.e.

$\min_{\tau\in\mathcal{T}_{\nu}}~{}\mathbb{E}_{\tau}[\hat{v}^{\prime}(\mu)].$
(4)

Alternatively, Alice could want to account for the worst of Bob’s mistakes,
for every realization $\omega$. This would yield a more robust program as it
would capture the worst mistake of Bob for each realization of $\omega$, and
not merely for each message $m$. However, we deem this approach too
conservative since Bob never observes $\omega$ before taking action, and his
mistakes might thus not be correlated with $\omega$ further than through the
knowledge of $m$.

Our hypothesis also singularly differs from parametric uncertainty, where Bob
behaves in a specific coherent way, unknown to Alice. In this case, she would
rather account for this uncertainty at the root, and not at the belief level.
Informally, if $\theta\in\Theta$ is the unknown parameter and
$\hat{v}_{\theta}$ denotes the conditional utility of Alice when Bob is of
type $\theta$, the program of Alice should rather be

$\max_{\tau\in\mathcal{T}_{\nu}}~{}\inf_{\theta\in\Theta}~{}\mathbb{E}[\hat{v}_{\theta}(\mu)].$

It is nonetheless possible to consider the perhaps overtly robust program

$\max_{\tau\in\mathcal{T}_{\nu}}~{}\mathbb{E}\\!\left[\inf_{\theta\in\Theta}~{}\hat{v}_{\theta}(\mu)\right]$

which fits in our framework. It is arguably too conservative, yet it could
prove useful if more amenable to analysis than the previous approach. On this
topic, we refer the interested reader to our discussion in Appendix 9.4.

In order to make progress in characterizing how solutions of (4) would differ
from those of (3), we now consider a special setup, as introduced in [38]. We
later relax the Bayesian hypothesis, and consider the specific case of linear-
quadratic persuasion.

###  3.3 Linear-quadratic persuasion

In a general linear quadratic setting, Alice observes the state of nature
$x\in\mathbb{R}^{n}$ distributed according to $\nu$, centered and of
covariance $I_{n}$ without loss of generality. She then sends a message
$y\sim\sigma(x)$ with $\sigma\colon\mathbb{R}^{n}\to\mathcal{P}(\mathcal{M})$
fixed, known by Bob and chosen by Alice. Bob then plays his best response,
assumed to be affine in his estimation $\hat{x}=\mathbb{E}[x\\!\mid\\!y]$,

$a(\hat{x})=B\hat{x}+b\in\mathbb{R}^{k}.$ (5)

Finally, Alice suffers the quadratic loss

$v(a,x)=\begin{bmatrix}x\\\ a\end{bmatrix}^{\top}Q\begin{bmatrix}x\\\
a\end{bmatrix}+l^{\top}\begin{bmatrix}x\\\ a\end{bmatrix}+r,$ (6)

where $Q$ is symmetric and $a$ is the action played by Bob. The theoretical
appeal of this model is that 1) Bob’s response can be motivated as resulting
from a quadratic loss as well, 2) for a given policy $\sigma$, Alice’s loss
only depends on the covariance of $\hat{x}$ as detailed in the following
lemma.

######  Lemma 2 (from [38]).

For $\sigma$ fixed, Alice’s cost is

$\mathbb{E}[v(a(\hat{x}),x)]=\operatorname{Tr}(D\Sigma)+c,$

where $c$ is a constant, $D=Q_{12}B+B^{\top}Q_{21}+B^{\top}Q_{22}B$ is a
constant symmetric matrix, and $\Sigma$ is the covariance of $\hat{x}$ under
policy $\sigma$.

The covariance of $\hat{x}$ always lies in
$\mathcal{S}\triangleq\\{\Sigma\succeq 0,~{}\Sigma\preceq I_{n}\\}$, and both
bounds can be reproduced exactly with respectively no- and full-information
disclosure. If we call $\mathcal{S}_{\nu}\subset\mathcal{S}$ the set of
covariances of $\hat{x}$ produced by any policy, Alice’s quest amounts to
first finding $\Sigma$ that solves

$\min_{\Sigma\in\mathcal{S}_{\nu}}~{}\operatorname{Tr}(D\Sigma)+c,$

then retrieving a policy $\sigma$ that generates this covariance. At this
stage, it remains unclear how to perform either step.

The author of [38] notes that

$\min_{0\preceq\Sigma\preceq I_{n}}~{}\operatorname{Tr}(D\Sigma)+c$ (7)

is an upper bound on Alice’s best performance (i.e. a lower bound of her
lowest expected cost), and when $\mathcal{S}_{\nu}=\mathcal{S}$, actually
equals it. Program (7) is immediate to solve, either numerically by
recognizing it is a semi-definite program (SDP), or analytically by resorting
to the following lemma, of which we will make frequent use.111This lemma is
more or less already present under a different form in the proof of theorem 1
of [38], but this specific formulation is more helpful to us.

######  Lemma 3.

Solutions of

$\min_{0\preceq X\preceq I_{n}}~{}\operatorname{Tr}(DX),$

are exactly all $P_{D}^{<0}\preceq X\preceq P_{D}^{\leq 0}$, where
$P_{D}^{<0},P_{D}^{\leq 0}$ are respectively the orthogonal projection matrix
on the negative and on the non-positive eigenspace of $D$ (i.e. the space span
by the eigenvectors of $D$ associated to negative and respectively non-
positive eigenvalues).

A direct consequence of this lemma, when $\mathcal{S}=\mathcal{S}_{\nu}$, is
that Alice has incentive to send some information (i.e. a policy other than no
revelation) if and only if $D\not\succeq 0$.

Generically, $P_{D}^{<0}=P_{D}^{\leq 0}$ (corresponding to $D$ non-singular),
so the solution is usually unique. However, when it is not the case,
$P_{D}^{<0}$ is the only solution of minimal rank. This corresponds to the
situation in which Alice’s policy uses the minimal number of channels while
remaining optimal. It is worth noting that since (7) is a concave program (the
objective of the minimization is concave, on a convex domain), there always is
a solution that is an extreme point of the domain, thus in this case, is an
orthogonal projection matrix. It is appreciable that the unique solution of
minimal rank is also an orthogonal projection matrix.

Figuring out $\mathcal{S}_{\nu}$ for a given prior can be challenging.
Nevertheless, it is possible to check whether $\mathcal{S}=\mathcal{S}_{\nu}$
in practice. Two arguments play out: 1) $\mathcal{S}_{\nu}$ is a convex subset
of $\mathcal{S}$, hence $\mathcal{S}=\mathcal{S}_{\nu}$ if and only if
$\mathcal{S}_{\nu}$ contains all extreme points of $\mathcal{S}$, i.e. all
orthogonal projection matrices; 2) $\hat{x}$ has the orthogonal projection
matrix $P$ as covariance, if and only if (almost everywhere) $\hat{x}=Px$.

######  Lemma 4.

The three following statements are equivalent,

  1. (i)

$\mathcal{S}_{\nu}=\mathcal{S}$;

  2. (ii)

for all orthogonal projection matrix $P$,

$\mathbb{E}[x\\!\mid\\!Px]=Px;$

  3. (iii)

for all orthogonal projection matrix $P$ of rank $n-1$,

$\mathbb{E}[x\\!\mid\\!Px]=Px.$

A simple yet useful byproduct of this lemma is that when
$\mathcal{S}_{\nu}=\mathcal{S}$ and the message is $y=Px$, with $P$ an
orthogonal projection matrix, the covariance of $\hat{x}$ is $P$. Indeed,
$\hat{x}=Px$ and thus $\Sigma=PI_{n}P^{\top}=P$. Hence under any condition of
Lemma 4, (7) exactly represents Alice’s program, an orthogonal projection
matrix $P$ solution can be easily found, and a corresponding policy $y=Px$
derived. For this reason, we define the _projective policy_ of (orthogonal
projection) matrix $P$ as the signaling policy $y=Px$.

The next lemma shows that isotropic priors, once centered and reduced so that
their covariance is $I_{n}$, form a broad class of priors that enjoy this
property. In particular, the fact that all normal priors are isotropic
explains the results of [38] about Gaussian linear-quadratic persuasion.
Conversely, the counterexample of [38] relies on a prior that is not
isotropic.

######  Lemma 5.

When $n=1$, all distributions satisfy the condition of Lemma 4. When $n\geq
2$, isotropic distributions satisfy the condition of Lemma 4.

At this point, we would like to highlight a rather general fact, independent
of $\Lambda$. To prove point 1) supporting Lemma 4, we show that the set
$\mathcal{T}$ is convex as $\lambda\tau_{0}+(1-\lambda)\tau_{1}$ is realized
by first independently drawing $i\sim\mathrm{Bernoulli}(1-\lambda)$, then
messaging according to policy $\sigma_{i}$. Moreover, the objective of (4) is
linear in $\tau\in\mathcal{T}$. With this in mind, Alice could recreate any
covariance of $\mathcal{S}$ by playing a mixture of projective policies if she
so desired, however by linearity of the objective she is better off playing
one of the projective policies.

##  4 Approximating Alice’s program under an ellipsoidal hypothesis

When Bob is not exactly Bayesian, Alice’s program is not quite as simple as
explained in Section 3 since his response is not just linear in $\hat{x}$. In
order to make progress in this case, we first need to discuss the robust
hypothesis $\Lambda$ in more details. The last part of this section is
dedicated to approximating the non-Bayesian term under these hypotheses.

###  4.1 Tractable robust hypotheses

We conveniently denote the average by $\bar{\mu}\triangleq\mathbb{E}_{\mu}[x]$
when $\mu$ is a probability measure over $\mathbb{R}^{n}$. We will also call
$\Sigma_{\mu}=\mathbb{E}_{\mu}[(x-\bar{\mu})(x-\bar{\mu})^{\top}]$, the
covariance of $x$ under belief $\mu$. In particular, $\bar{\nu}=0$ and
$\Sigma_{\nu}=I_{n}$.

Let $\mu^{\prime}_{y}$ be an erroneous belief of Bob after receiving message
$y$, then $\hat{x}^{\prime}=\bar{\mu}^{\prime}_{y}$ is Bob’s inaccurate
estimation of $x$ given $y$, whereas the Bayesian estimate is
$\hat{x}=\bar{\mu}_{y}$. A cautious Alice tries to account for this
inaccuracy. She realizes that since Bob’s action only depends on
$\hat{x}^{\prime}$, she need not worry about $\mu^{\prime}_{y}$ entirely but
solely about its mean. For this reason, she only really needs to consider the
set of means induced by $\Lambda(\mu)$, i.e.

$\bar{\Lambda}(\mu)\triangleq\\{\bar{\mu}^{\prime},~{}\mu^{\prime}\in\Lambda(\mu)\\}.$

This set can take various forms depending on the specific way Bob fails to be
Bayesian, according to Alice. Several examples are discussed below.

####  4.1.1 Examples

A first natural idea is for Alice to assume that Bob’s erroneous posterior
lies within a given distance from the Bayesian posterior, as measured by some
statistical metric. In the case of the Wasserstein distance, we can state the
following result.

######  Proposition 1.

Let $W_{p}(\mu^{\prime},\mu)$ denote the usual $p^{\text{th}}$ Wasserstein
distance between $\mu^{\prime}$ and $\mu$, and let the robust hypothesis
$\Lambda$ be given by

$\Lambda(\mu)=\\{\mu^{\prime}\ll\mu,~{}W_{p}(\mu^{\prime},\mu)\leq\epsilon\\},$
(8)

then

$\bar{\Lambda}(\mu)=\bar{\mu}+\epsilon\mathcal{B}.$

In words, $\Lambda$ as in (8) corresponds to the robust hypothesis that “Bob’s
posterior is always within $p^{\text{th}}$ Wasserstein distance $\epsilon$
from the true posterior.” It is remarkable that, in terms of means, it induces
a simple Euclidean ball. Moreover, $\bar{\Lambda}(\mu)$ only depends on the
mean $\bar{\mu}$ of $\mu$.

Regarding the choice of statistical distance, one can also consider the broad
family of $f$-divergences. Let $f\colon(0,\infty)\to\mathbb{R}$ be convex with
$f(1)=0$, and interpret $f(0)$ as the limit of $f(\epsilon)$ as $\epsilon>0$
vanishes. We denote the $f$-divergence of $\mu^{\prime}$ from $\mu$ by

$D_{f}(\mu^{\prime}\;\|\;\mu)=\int_{\mathbb{R}^{n}}f\circ\frac{\mathrm{d}\mu^{\prime}}{\mathrm{d}\mu}\,\mathrm{d}\mu,$

whenever $\mu^{\prime}\ll\mu$. For simple instances, with $f(t)=t\ln t$, one
recovers the Kullback-Leibler divergence, and with a little more care, one
recovers the Rényi divergences.

As it turns out, $f$-divergences prove to be a little more difficult to work
with, and we have to restrict our attention to posteriors $\mu$ that stem from
a projective policy. Even then, unlike the case of Proposition 1, the mean set
$\bar{\Lambda}(\mu)$ also depends on the covariance $\Sigma_{\mu}$. More
precisely, we can show the following.

######  Proposition 2.

Let the robust hypothesis $\Lambda$ be given by

$\Lambda(\mu)=\\{\mu^{\prime}\ll\mu,~{}D_{f}(\mu^{\prime}\;\|\;\mu)\leq\epsilon\\},$

and let $\mu$ be a Bayesian posterior obtained by a projective policy $P$,
then

$\bar{\Lambda}(\mu)=\bar{\mu}+\delta(I_{n}-P)\,\mathcal{B},$

where the scalar $\delta$ could be infinite (in which case
$\bar{\Lambda}(\mu)=\mathbb{R}^{n}$) and implicitly depends on $f$, $\epsilon$
and $\bar{\mu}$.

When $\nu$ is Gaussian, $\mu=\mathcal{N}(\bar{\mu},I_{n}-\Sigma)$ is Gaussian
as well. What is remarkable is that once centered, all $\mu$ are the same
distribution $\mathcal{N}(0,I_{n}-\Sigma)$. In this specific case then,
$\delta$ does not depend on $\bar{\mu}$.

Another way in which a set of erroneous posteriors can be generated is if Bob
is Bayesian but that his computation costs him. In this event, he may very
well trade off accuracy for efficacy, and thus be content with a suboptimal
solution. As mentioned earlier, Bob’s in-game loss is often considered
quadratic in linear-preference persuasion, that is

$u(a,x)=\begin{bmatrix}x\\\ a\end{bmatrix}^{\top}R\begin{bmatrix}x\\\
a\end{bmatrix}+m^{\top}\begin{bmatrix}x\\\ a\end{bmatrix}+s,$ (9)

where $R_{22}\succ 0$ and, to suit our construction, $R_{12}$ is assumed non-
singular. Under belief $\mu$ and with no computation cost, Bob’s best-response
is,

$a^{*}(\bar{\mu})=-R_{22}^{-1}(\nicefrac{{m_{2}}}{{2}}+R_{21}\bar{\mu}).$

With this notation, we can state the following.

######  Proposition 3.

When Bob’s loss is as in (9),

$\\{a,~{}u(a,\mu)\leq
u(a^{*}(\bar{\mu}),\mu)+\epsilon\\}=a^{*}\\!\left(\bar{\mu}+\sqrt{\epsilon}R_{21}^{-1}\sqrt{R_{22}}\mathcal{B}\right).$

In other words, Bob being satisfied with an $\epsilon$-suboptimal solution
corresponds exactly to Bob playing optimally but with posteriors such that the
set of means is

$\bar{\Lambda}(\mu)=\bar{\mu}+\sqrt{\epsilon}R_{21}^{-1}\sqrt{R_{22}}\mathcal{B}.$

This robust hypothesis is very similar to that of the “Wasserstein distance”
case, in the sense that we would only need to rescale the Euclidean metric to
match it.

####  4.1.2 A specific class of tractable hypotheses

Among the examples of $\bar{\Lambda}$ we have discussed above, two of them—the
“Wasserstein hypothesis” and the “costly update hypothesis”—were remarkable in
that they are ellipsoids, and function of $\bar{\mu}$ only. Moreover, when
$\nu$ is Gaussian and Alice uses an “f-divergence hypothesis,” $\delta$ in
Proposition 2 does not depend on $\bar{\mu}$ and so the following conservative
inclusion holds:

$\bar{\mu}+\delta(I_{n}-\Sigma)\,\mathcal{B}\subset\bar{\mu}+\delta\mathcal{B}.$

Over all, this justifies focusing our attention on the following specific
class.

######  Definition 1.

The ellipsoidal hypothesis of parameter $C$ (and of shape $CC^{\top}$) is the
correspondence $\bar{\Lambda}$ defined by

$\bar{\Lambda}(\mu)=\bar{\mu}+C\mathcal{B}.$

Since $\bar{\Lambda}$ defined above only depends on $\mu$ through its mean
$\bar{\mu}$, we henceforth will abuse notation by writing
$\bar{\Lambda}(\bar{\mu})$. Note that the ellipsoidal hypothesis of parameter
$0$ is none other than the Bayesian hypothesis.

###  4.2 Rewriting the program under an ellipsoidal hypothesis

With this definition in hand, we are now in position to tackle Alice’s
program. For simplicity, we start by modifying her utility to include $B,b$ so
that Bob directly plays his estimate ($\bar{\mu}^{\prime}$ when he is not
Bayesian) rather than the general affine form (5). This only modifies the
coefficients $Q,l,r$ from (6), not the nature of the problem.

Recall that Alice’s objective is $\mathbb{E}_{\tau}[\hat{v}^{\prime}(\mu)]$,
where

$\hat{v}^{\prime}(\mu)=\sup_{\bar{\mu}^{\prime}\in\bar{\Lambda}(\bar{\mu})}~{}v(\bar{\mu}^{\prime},\mu).$
(10)

Since (10) only depends on $\bar{\mu}$, the objective of Alice is only a
function of the distribution $\bar{\tau}$ of estimates, rather than the
distribution $\tau$ of the whole beliefs. Accordingly, we denote by
$\bar{\mathcal{T}}_{\nu}$ the set of distributions of estimates that can be
generated by a policy from the prior $\nu$. In this context,
$\delta_{\bar{\nu}}\in\bar{\mathcal{T}}_{\nu}$ is the distribution of
estimates resulting from the no-information policy, and
$\nu\in\bar{\mathcal{T}}_{\nu}$ is the distribution of estimates resulting
from the full-information policy. With this notation in hand, we rewrite
Alice’s program in the following lemma.

######  Lemma 6.

Under ellipsoidal hypothesis of parameter $C$, the program of Alice takes the
form

$\min_{\bar{\tau}\in\bar{\mathcal{T}}_{\nu}}~{}\operatorname{Tr}(D\Sigma)+c+\mathbb{E}_{\bar{\tau}}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right],$ (11)

where explicitly

$w(\eta,\bar{\mu})=(2(Q_{21}+Q_{22})\bar{\mu}+l_{2})^{\top}\eta+\eta^{\top}Q_{22}\eta.$

The term $\operatorname{Tr}(D\Sigma)+c$ corresponds to the Bayesian case, as
can be seen by setting $C=0$. The remaining term is the penalty induced by the
imprecise knowledge of Alice over Bob’s belief.

Before exploring approximations, we should mention that under the ellipsoidal
hypothesis, Alice has no incentive to share information to an almost-Bayesian
agent if she has none to share information to a Bayesian agent.

######  Theorem 1.

When an optimal strategy is to not reveal any information to the Bayesian
agent (equivalently, when $D\succeq 0$), the same is true for almost-Bayesian
agents. More formally put, if $\Sigma=0$ is a solution of the Bayesian program
(7), then $\bar{\tau}=\delta_{\bar{\nu}}$ is a solution of (11).

In general, it remains unclear how to determine whether Alice would profit at
all from sending a message compared to not communicating any information.
Nonetheless, there are cases for which we can certify Alice wants to
communicate with Bob. Having defined

$\displaystyle\bar{\lambda}$
$\displaystyle=\overline{\lambda}(C^{\top}Q_{22}C)$ (12) $\displaystyle E$
$\displaystyle=4(Q_{12}+Q_{22})CC^{\top}(Q_{21}+Q_{22})$ $\displaystyle f$
$\displaystyle=l_{2}^{\top}CC^{\top}l_{2},$

we prove the following.

######  Theorem 2.

When $C^{\top}Q_{22}C$ is not a scaling of the identity and

$D\prec-\frac{f+\operatorname{Tr}E}{4(\bar{\lambda}-\bar{\lambda}_{2})},$

where $\bar{\lambda}_{2}$ denotes the second largest eigenvalue of
$C^{\top}Q_{22}C$, $\bar{\tau}=\delta_{\bar{\nu}}$ is _not_ a solution of
(11), even restricting to projective policies.

###  4.3 The framing programs

We will not be able to solve the program of Alice (11) in full generality.
Nonetheless, we propose to approximate this program when $Q_{22}\succeq 0$. In
spirit, this corresponds to a “persuasion” objective where Alice wants to
persuade Bob to have an estimation close to a specific target (varying
affinely in $x$), akin to the opening example in which Alice wanted Bob to
estimate $kx$. This contrasts strongly with the “dissuasion” case
$Q_{22}\preceq 0$, in which Alice would rather have Bob be far from the target
estimation.

Before presenting the approximations, we recall all the assumptions made so
far. We have assumed that the prior $\nu$ is isotropic once centered and
reduced (i.e. so that $\bar{\nu}=0$ and $\Sigma_{\nu}=I_{n}$), that Alice’s
loss is quadratic in $(x,a)$ as in (6) (and positive semidefinite in $a$, i.e.
$Q_{22}\succeq 0$), that Bob’s action is affine in his estimate
$\bar{\mu}^{\prime}$, and that

$\bar{\mu}^{\prime}\in\bar{\mu}+C\mathcal{B}.$

With all this in place, we can now focus on bounding the intricate penalty
term

$\mathbb{E}_{\bar{\tau}}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right],$

which appears in Alice’s program (11). In the first theorem, we derive a
general lower and upper bound.

######  Theorem 3.

For any $\bar{\tau}\in\bar{\mathcal{T}}_{\nu}$, namely for any policy,

$\max(\bar{\lambda},\sqrt{f})\leq\mathbb{E}_{\bar{\tau}}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]\leq\bar{\lambda}+\sqrt{f+\operatorname{Tr}(E\Sigma)},$

with $\bar{\lambda},E,f$ as in (12), and $\Sigma=\Sigma_{\bar{\tau}}$ the
covariance of the estimate under $\bar{\tau}$.

Unfortunately, the lower bound is not quite strong enough to always match the
upper bound up to a fixed ratio. However, turning to the more congenial class
of projective policies, we do find such a lower bound. In some fortuitous
instances, this lower bound also applies to general policies.

######  Theorem 4.

For any projective policy (and corresponding orthogonal covariance matrix
$\Sigma$),

$\displaystyle\gamma(\bar{\lambda}+\sqrt{f+\operatorname{Tr}(E\Sigma)})$
$\displaystyle\leq\mathbb{E}_{\bar{\tau}}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]$ (13)
$\displaystyle\leq\bar{\lambda}+\sqrt{f+\operatorname{Tr}(E\Sigma)},$

where explicitly

$\gamma=\frac{2}{1+\sqrt{5+\frac{4}{\mathbb{E}[|x_{1}|]^{2}}}}.$

Furthermore, whenever

$f\geq\mathbb{E}[|x_{1}|]^{2}\operatorname{Tr}E,$

this also applies to any general policy.

The ratio $\gamma$ depends on the prior distribution, and can never exceed
$\upsilon_{n}$, the ratio obtained for the uniform distribution on the sphere
(of radius $\sqrt{n}$). As a result, $\upsilon_{n}$ provides an upper bound on
the tightness of the approximation (13). On the other hand, there is no lower
bound on $\gamma$, which means there are priors for which the approximation
(13) is not informative. However, for Gaussian priors, $\gamma$ is independent
of the dimension and approximately equals $0.46$. More precisely, we present
the following proposition.

######  Proposition 4.

For any isotropic prior of covariance $I_{n}$,

$\gamma\leq\upsilon_{n}\triangleq\frac{2}{1+\sqrt{5+\frac{4\pi\Gamma(\nicefrac{{(n+1)}}{{2}})^{2}}{n\Gamma(\nicefrac{{n}}{{2}})^{2}}}},$

with equality if and only if the prior is the uniform distribution on the
sphere of radius $\sqrt{n}$. The sequence $(\upsilon_{n})$ decreases with
limit

$\upsilon_{\infty}=\frac{2}{1+\sqrt{5+2\pi}}\sim 0.46,$

which is the ratio $\gamma$ for Gaussian priors, regardless of the dimension.

For future reference, we now gather all four programs of interest in one list:

  1. 1.

the _Bayesian Program_ is

$\min_{0\preceq\Sigma\preceq I_{n}}~{}\operatorname{Tr}(D\Sigma)+c;$ (7)

  2. 2.

the _Pessimistic Program_ is

$\min_{0\preceq\Sigma\preceq
I_{n}}~{}\operatorname{Tr}(D\Sigma)+c+\bar{\lambda}+\sqrt{f+\operatorname{Tr}(E\Sigma)};$
(14)

  3. 3.

the _Universal Optimistic Program_ is

$\min_{0\preceq\Sigma\preceq
I_{n}}~{}\operatorname{Tr}(D\Sigma)+c+\max(\bar{\lambda},\sqrt{f});$ (15)

  4. 4.

and the _Projective Optimistic Program_ is

$\min_{0\preceq\Sigma\preceq
I_{n}}~{}\operatorname{Tr}(D\Sigma)+c+\gamma\bar{\lambda}+\gamma\sqrt{f+\operatorname{Tr}(E\Sigma)}.$
(16)

The Pessimistic Program and Universal Optimistic Program correspond to the
upper-bound and lower-bound obtained in Theorem 3, respectively. The latter
program has the same solution as the Bayesian Program—its main merit being
that it gives a better lower bound on the loss Alice must endure than the
plain Bayesian Program. Finally, the Projective Optimistic Program, which is a
lower bound on the cost of Alice when using projective policies, is derived
from Theorem 4. Although the theorem only speaks of projective policies, and
hence of covariances that are extremal in $\mathcal{S}$, the objective of the
minimization is concave, thus the constraint set can be extended to
$\mathcal{S}$ entirely. This program is mostly identical to the Pessimistic
Program, save for the constant $\gamma$ preceding the error term. In this
respect, being able to solve the Projective Optimistic Program amounts to
being able to solve the Pessimistic Program. For this reason, and since Alice
is preparing for the worst, (14) remains our main object of study.

In summary, the Pessimistic Program is a universal lower bound on Alice’s best
performance, whereas we dispose of two optimistic programs depending on
whether we allow any policy—not just projective policies—to be implemented.
The error term of the Projective Optimistic Program is well behaved,
essentially it is pinned down up to a ratio close to a half (for Gaussian
priors), so we are confident that solving the Pessimistic Program is a good
proxy for solving the true program (11). When the specific criterion of
Theorem 4 is met, this also applies to general policies. Otherwise, the
Universal Optimistic Program seems to indicate that there could be better non-
projective policies, however they remain inaccessible as it already proves
arduous to even represent such general policies.

##  5 Analysis of the Pessimistic Program

This section sheds light on the Pessimistic Program (14) and the structure of
its solutions. It also presents a numerical method to solve it. We then verify
that the structure of the numerical solutions agrees with theoretical
predictions.

###  5.1 Structural facts

Much like for the Bayesian Program, there are a few things that can be said
about the solutions of (14). First of all, the program is concave, so just
like in the Bayesian case, there exists a solution that is an extreme point of
$\mathcal{S}$, thus corresponding to a projective policy.

In contrast with the Bayesian case, it may so happen that (14) has multiple
solutions. However, as the next proposition states, all solutions of minimal
rank are orthogonal projection matrices just like in the Bayesian case. We
again use rank as a proxy for the amount of information shared by Alice, since
when $P$ is an orthogonal projection matrix, $\operatorname{rk}P$ corresponds
to the number of active channels in the policy $y=Px$.

######  Proposition 5.

Solutions of minimal rank of (14) are all orthogonal projection matrices.

Having decided to use the rank of an orthogonal projection matrix as a measure
of information provided by Alice, it is natural to inspect how the minimal
rank of a solution varies as the hypothesis grows weaker, i.e. as
$\bar{\Lambda}$ grows larger with respect to the inclusion order. In all
generality, there may be no monotonicity. Nevertheless, it turns out that the
minimal rank of a solution decreases as the hypothesis grows weaker, provided
it grows homothetically.

######  Theorem 5.

Let $\Sigma_{1},\Sigma_{2}$ be solutions of minimal rank of the Pessimistic
Program (14) under ellipsoidal hypothesis of respective shape
$\epsilon_{1}^{2}CC^{\top}$ and $\epsilon_{2}^{2}CC^{\top}$. Then
$\epsilon_{1}\leq\epsilon_{2}$ implies
$\operatorname{rk}\Sigma_{1}\geq\operatorname{rk}\Sigma_{2}$.

This theorem admits a direct corollary which, in essence, states that Alice is
willing to share more information to a Bayesian agent, less information to an
almost-Bayesian agent when she is optimistic, and the least information when
she is pessimistic.

######  Corollary 1.

The minimal rank of a solution of the Bayesian Program is larger than or equal
to that of the Projective Optimistic Program, which itself is larger than or
equal to that of the Pessimistic Program.

From this corollary, we recover the structural result of Theorem 1 about the
true program (11) in all our programs.

######  Corollary 2.

Whenever $D\succeq 0$, the minimal solution of (14), (15) and (16) is
$\Sigma=0$, corresponding to the no-information policy.

Note nonetheless that this is not to say that Alice shares information as soon
as $D\not\succeq 0$, rather that she has no incentive to do so when $D\succeq
0$. In fact, we have the following result.

######  Proposition 6.

Whenever

$E\succeq\left(\left(\sqrt{f}-\operatorname{Tr}(DP_{D}^{<0})\right)^{2}-f\right)I_{n},$

$\Sigma=0$ is a solution of (14).

We remind the reader that $P_{D}^{<0}$ denotes the orthogonal projection on
the negative eigenspace of $D$, so that $\operatorname{Tr}(P_{D}^{<0}D)\leq
0$. This proposition states that provided $E$ is large enough, not sending
information is optimal among projective policies, from a pessimistic point of
view. One can interpret this result in the light of the parametrized
hypothesis presented in Theorem 5, i.e. of shape $\epsilon^{2}CC^{\top}$. When
$E\succ 0$, the condition of Proposition 6 is satisfied for $\epsilon$ large
enough since the left-hand side grows with order $\epsilon^{2}$, whereas the
right-hand side grows with order $\epsilon$. As a result, the solution of (14)
is $\Sigma=0$, when Bob is not Bayesian enough.

This contrasts with Theorem 2 whose condition is independent of $\epsilon$,
and hence insures that there are cases where Alice benefits from signaling no
matter the value of $\epsilon$. This shows a limit of the Pessimistic Program
(14) when $\epsilon$ is very large.

###  5.2 Numerical solution

As it stands, the Pessimistic Program (14) is not in a convenient form. It is
concave, and a square-root term sits cumbersomely in the midst of the
objective. We cannot hope to directly solve the program with readily available
methods, however we can introduce, for $t\geq 0$,

$h(t)\triangleq\min_{\begin{subarray}{c}0\preceq X\preceq I_{n}\\\ \text{s.t.
}\operatorname{Tr}(EX)\leq t\end{subarray}}~{}\operatorname{Tr}(DX).$

Evaluating $h$ at a given $t$ is relatively easy, as it is a semi-definite
program (SDP). If we have a fine enough understanding and estimation of $h$
available, we may resort to the following proposition.

######  Proposition 7.

$Y\in\mathcal{S}$ solves (14) if and only if $Y$ solves the program defining
$h(\operatorname{Tr}(EY))$, and $\operatorname{Tr}(EY)$ solves the program

$\min_{t\geq 0}~{}h(t)+\sqrt{f+t}.$ (17)

Moreover, both (14) and (17) have the same value.

One can thus solve (17) by a simple one-dimensional grid search, then retrieve
an optimal argument of (14). In actuality however, one only obtains a
suboptimal solution through grid search, so the objective of (17) needs to be
studied in order to provide adequate guarantees as to the suboptimality.
Fortunately, $h$ enjoys many desirable properties that can be used to
establish those guarantees.

######  Lemma 7.

Let $\bar{t}=\operatorname{Tr}(EP_{D}^{<0})$ for convenience. The function $h$
is continuous and convex, decreasing on $[0,\bar{t}]$ and constant on
$[\bar{t},\infty)$. In addition, for any $0\leq a<b$

$h(b)+\sqrt{f+a}\leq\min_{t\in[a,b]}~{}h(t)+\sqrt{f+t}\leq h(b)+\sqrt{f+b}.$

Observe that the difference between the two bounds is directly controlled by
$a,b$, independently of $h$. As a result, a simple strategy for finding an
$\epsilon$-suboptimal solution consists in first cutting
$[\sqrt{f},\sqrt{f+\bar{t}}]$ into smaller intervals of length $\epsilon$ of
the form

$[\sqrt{f+u_{n}},\sqrt{f+u_{n+1}}].$

Then $h$ is evaluated at each $u_{n}$, and the point yielding the lowest value
$h(u_{n})+\sqrt{f+u_{n}}$ is selected. Over all, this takes

$\left\lceil\frac{\sqrt{f+\bar{t}}-\sqrt{f}}{\epsilon}\right\rceil$

calls to the SDP oracle. We summarize this procedure in the following
proposition.

######  Proposition 8.

Consider $(u_{n})_{0\leq n\leq N}$ an increasing sequence with $u_{0}=0$ and
$u_{N}\geq\bar{t}$. Call

$\epsilon=\max_{0\leq n<N}~{}\sqrt{f+u_{n+1}}-\sqrt{f+u_{n}},$

then

$\displaystyle\min_{t\geq 0}~{}h(t)+\sqrt{f+t}$ $\displaystyle\leq\min_{0\leq
n\leq N}~{}h(u_{n})+\sqrt{f+u_{n}}$ $\displaystyle\leq\min_{t\geq
0}~{}h(t)+\sqrt{f+t}+\epsilon.$

###  5.3 Consistency of structural and numerical results

Proposition 7 and 8 provide a numerical procedure to find _a_ suboptimum to
(14), without guaranteeing it is an orthogonal projection matrix. However,
knowing Proposition 5, it would be natural to look for solutions of (14) that
are orthogonal projection matrices. On top of that, all the policies we have
considered thus far are projective, whose covariances must be orthogonal
projection matrices.

To remedy this apparent discrepancy, consider $X^{*}$ a suboptimal solution to
(14). By diagonalizing it, it is relatively easy to write it as a convex
combination of at most $n+1$ orthogonal projection matrices:

$X^{*}=\sum_{i=0}^{n}\lambda_{i}X_{i}.$

Since the objective of (14) is concave, some $X_{i}$ must perform no worse
than $X^{*}$, this provides Alice with a suboptimal projective policy.

In practice, however, we have noted that $X^{*}$ is a convex combination of at
most two orthogonal projection matrices. Indeed, having reduced the problem so
that

$\ker D\cap\ker E=\\{0\\},$

generically $\operatorname{rk}(D-\lambda E)\geq n-1$ for all $\lambda>0$, and
the following proposition holds.

######  Proposition 9.

If $\ker D\cap\ker E=\\{0\\}$ and $\operatorname{rk}(D-\lambda E)\geq n-1$ for
all $\lambda>0$, then for all $t\in(0,\bar{t})$, the program defining $h(t)$
has a unique solution, which is a convex combination of at most two orthogonal
projection matrices.

##  6 Illustrations

In order to illustrate the tightness of our approximation bounds, we first
compare them against two cases we can entirely solve: the unidimensional case
(i.e. when $n=1$), and the opening example. Specifically, we are interested in
how the Pessimistic Program solution differs from the true optimal projective
policy. The last subsection numerically solves an arbitrary instance.

###  6.1 The unidimensional case

####  6.1.1 Tightness of approximations

Looking back at how we derived Theorem 3 and 4, the first obstacle was to
solve the inner maximization of (11). We used two lemmas to help us, Lemma 11
and 12. The first lemma turns the general $n$-dimensional optimization into a
unidimensional convex program, it is exact and relies on an S-procedure
followed by a Schur complement (see [42]). The second lemma approximates the
value of this simpler program, so that all in all, for all $\beta\in[0,1]$,

$\displaystyle(1-\beta^{2})\bar{\lambda}+2\beta\mathbb{E}[\|v\|]$
$\displaystyle\leq\mathbb{E}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]$ (18)
$\displaystyle\leq\bar{\lambda}+2\mathbb{E}[\|v\|],$

where,

$\displaystyle\bar{\lambda}$
$\displaystyle=\overline{\lambda}(C^{\top}Q_{22}C)$ $\displaystyle v$
$\displaystyle=C^{\top}((Q_{21}+Q_{22})\bar{\mu}+\nicefrac{{l_{2}}}{{2}}).$

When $n=1$ the error term can be explicitly computed as

$\mathbb{E}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]=\bar{\lambda}+2\mathbb{E}[\|v\|].$

So these first steps towards the Pessimistic Program—the one Alice ultimately
solves—are actually exact. We still cannot provide an optimal solution in all
generality, but when $n=1$ we can find the best projective policy. Indeed,
there are only two such policies: full- and no-information. In the first case,
$\hat{x}=x$ and in the second case $\hat{x}=0$.

In the no-information case, the approximation

$\mathbb{E}[\|v\|]\leq\sqrt{\mathbb{E}[\|v\|^{2}]},$

is actually exact as the distribution of $v$ is a Dirac, so the Pessimistic
Program matches the reality. In the full-information case, the relation
between $\mathbb{E}[\|v\|]$ and $\sqrt{\mathbb{E}[\|v\|^{2}]}$ is a tad more
complicated. Nonetheless, for unidimensional Gaussian priors, we have the
following result.

######  Lemma 8.

When $\nu\sim\mathcal{N}(0,1)$, $a,b\in\mathbb{R}$,

$\sqrt{\frac{2}{\pi}}\sqrt{\mathbb{E}[(a+bx)^{2}]}\leq\mathbb{E}[|a+bx|]\leq\sqrt{\mathbb{E}[(a+bx)^{2}]},$

the lower bound occurring exactly when $a=0$.

####  6.1.2 Comparing Optimistic, True and Pessimistic solutions

In the no-information case, the true objective is the same as in the
Pessimistic Program. In the full-information case however, the three programs
ascribe different values, which we want to compare to each other. To this end,
we first note that we can take $c=0$ and $D=-1$ without loss of generality
($D\geq 0$ is uninteresting as all programs make the same prediction, and
Alice’s cost can be rescaled). In addition, as discussed in Lemma 8, the
pessimistic value for the full-information policy is the most conservative
(and so the optimistic value is closer to the true value) when $l_{2}=0$. In
the interest of showing how the Pessimistic Program performs at its worst, we
study this very case.

This results in the various costs values presented in Table 1, where we let
$\epsilon=|C|$ to represent the scaling of the hypothesis. When $Q_{22}=1$,
all programs yield the same optimal policy. Otherwise—and this is in
accordance with Theorem 5—full-information is optimal for lower $\epsilon$,
and no-information becomes optimal past a threshold. The threshold
corresponding to the true program is

$q^{*}=\frac{1}{\sqrt{\frac{2}{\pi}}|Q_{22}-1|}$

while the pessimistic and optimistic thresholds are respectively

$q^{-}=\underset{\approx
0.80}{\underbrace{\sqrt{\frac{2}{\pi}}}}q^{*},~{}q^{+}=\underset{\approx
1.74}{\underbrace{\frac{1}{\gamma}\sqrt{\frac{2}{\pi}}}}q^{*}.$

The fact that $q^{-}\leq q^{+}$ agrees with the prediction of Corollary 1.
Indeed, when no-information is optimal for the Optimistic Program at a given
value of $\epsilon$, it also is the case for the Pessimistic Program.

As a result, when $\epsilon\leq q^{-}$ or $\epsilon\geq q^{+}$, all strategies
agree. When $\epsilon\in(q^{-},q^{*})$, however, the pessimistic strategy is
suboptimal whereas the optimistic strategy is optimal. When
$\epsilon\in(q^{*},q^{+})$, the opposite happens. Qualitatively, the
pessimistic solution is better in the sense that the range in which it is
dominated by the optimistic solution is smaller than the converse.

Table 1: Objective values | NI | FI
---|---|---
Optimistic | $\gamma\epsilon^{2}Q_{22}$ | $-1+\gamma\left(\epsilon^{2}Q_{22}+\epsilon|Q_{22}-1|\right)$
True | $\epsilon^{2}Q_{22}$ | $-1+\epsilon^{2}Q_{22}+\sqrt{\frac{2}{\pi}}\epsilon|Q_{22}-1|$
Pessimistic | $\epsilon^{2}Q_{22}$ | $-1+\epsilon^{2}Q_{22}+\epsilon|Q_{22}-1|$

####  6.1.3 Graphical comparisons

Figure 2: Plot of all the objectives, case $Q_{22}=0.1$. Figure 3: Plot of the
values of different strategies, case $Q_{22}=0.1$.

We plot the various objectives for $Q_{22}=0.1$, and with $\epsilon\geq 0$
varying in Figure 2. In red, we represent the values of the no-information
policy and in blue, the values of the full-information policy. The solid lines
represent the true values, the dashed lines represent the pessimistic bound,
and the dotted lines represent the optimistic value. The true values are much
closer to the pessimistic bound since the upper bound in (18) is exact.

Figure 3 represents the loss of Alice (measured by the true cost as in (11))
when she plays optimistically, optimally and pessimistically. In both figures,
the thresholds $q^{-}\leq q^{*}\leq q^{+}$ are represented by gridlines.

###  6.2 The opening example

We examine the opening example, specifically with parameter
$k>\nicefrac{{1}}{{2}}$ and $k\neq 1$, through the same lens as the
unidimensional case. For this instance, (18) becomes

$\displaystyle(1-\beta^{2})\epsilon^{2}+2\beta\epsilon|1-k|\mathbb{E}[\|\hat{x}\|]$
$\displaystyle\leq\mathbb{E}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]$
$\displaystyle\leq\epsilon^{2}+2\epsilon|1-k|\mathbb{E}[\|\hat{x}\|],$

to be compared with the exact value

$\epsilon^{2}+2\epsilon|1-k|\mathbb{E}[\|\hat{x}\|].$

Once again, the first pessimistic approximation is exact. In addition, while
proving Theorem 4 (via Lemma 13), we have obtained the following approximation

$\mathbb{E}[\|\hat{x}\|]\geq\mathbb{E}[|x_{1}|]\sqrt{\mathbb{E}[\|\hat{x}\|^{2}]}=\mathbb{E}[|x_{1}|]\sqrt{\operatorname{Tr}\Sigma}.$

This bound is slightly tighter than the one used to derive the Projective
Optimistic Program thanks to the fact that $l_{2}=0$ in this specific
instance. These two arguments strengthen our expectation that the Pessimistic
Program is more accurate than the Projective Optimistic Program.

Unfortunately, since $l_{2}=0$, $f=0$ and so Theorem 3 only offers the bounds

$\epsilon^{2}\leq\mathbb{E}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]\leq\epsilon^{2}+2\epsilon|1-k|\mathbb{E}[\|\hat{x}\|].$

In other words, the best we can say regarding general policies is that they
must cost at least $\epsilon^{2}$ more than the Bayesian value.

The Pessimistic Program is strictly concave in $\operatorname{Tr}\Sigma$,
hence the solution is either $\Sigma=0$ or $\Sigma=I_{n}$, thus it suffices to
consider these two policies. In the no-information scenario, Jensen’s
inequality is an equality and so once more, the pessimistic value of the no-
information policy is exact. In the full-information scenario, the
approximation is not exact, however

$1\geq\frac{\mathbb{E}[\|x\|]}{\sqrt{\mathbb{E}[\|x\|^{2}]}}=\underset{\to_{n}1}{\underbrace{\frac{\sqrt{2}\Gamma(\nicefrac{{n+1}}{{2}})}{\sqrt{n}\Gamma(\nicefrac{{n}}{{2}})}}}\geq\sqrt{\frac{2}{\pi}}.$

Table 2: Objective values minus the constant $-k^{2}n-\epsilon^{2}$ | NI | FI
---|---|---
Optimistic | $-(1-\gamma)\epsilon^{2}$ | $-(2k-1)n-(1-\gamma)\epsilon^{2}+2\gamma\epsilon|1-k|\sqrt{n}$
True | $0$ | $-(2k-1)n+2\sqrt{2}\epsilon|1-k|\frac{\Gamma(\nicefrac{{n+1}}{{2}})}{\Gamma(\nicefrac{{n}}{{2}})}$
Pessimistic | $0$ | $-(2k-1)n+2\epsilon|1-k|\sqrt{n}$

Table 2 contains the objective of each program for both policies, minus the
constant $k^{2}n+\epsilon^{2}$ for legibility. Once again, in each case, full-
information is optimal until a certain threshold is met. The optimal threshold
is

$q^{*}=\frac{(2k-1)n}{2\sqrt{2}|1-k|\frac{\Gamma(\nicefrac{{n+1}}{{2}})}{\Gamma(\nicefrac{{n}}{{2}})}},$

whereas the pessimistic and optimistic thresholds are

$q^{-}=\underset{\to_{n}1}{\underbrace{\frac{\sqrt{2}\Gamma(\nicefrac{{n+1}}{{2}})}{\sqrt{n}\Gamma(\nicefrac{{n}}{{2}})}}}q^{*},~{}q^{+}=\underset{\approx
2.18}{\underbrace{\frac{1}{\gamma}}}q^{-}=\frac{\sqrt{2}\Gamma(\nicefrac{{n+1}}{{2}})}{\gamma\sqrt{n}\Gamma(\nicefrac{{n}}{{2}})}q^{*}.$

The conclusion we drew for the unidimensional setting also applies to the
opening example: the Pessimistic Program is qualitatively better suited to
represent the true program.

###  6.3 A numerical example

To illustrate the numerical procedure described in Section 5.2, we consider a
case where $n=3$, there is no linear term or constant term, and

$Q=\begin{bmatrix}-1&-2&-3&-5&2&-3\\\ -2&-4&-5&4&-9&6\\\ -3&-5&-6&-7&8&-11\\\
-5&4&-7&1&0&0\\\ 2&-9&8&0&2&0\\\ -3&6&-11&0&0&4\end{bmatrix}.$

In this case,

$D=\begin{bmatrix}-9&6&-10\\\ 6&-16&14\\\ -10&14&-18\end{bmatrix}\prec 0,$

The parameters are indeed chosen so that Alice reveals the information fully
when $\epsilon=0$, though they are rather arbitrary beyond that. To keep
things simple, consider the ellipsoidal hypothesis of parameter $C=\epsilon
I_{3}$. Then, leaving $\epsilon$ out as a factor, $\bar{\lambda}=4$, $f=0$ and

$E=\begin{bmatrix}116&-192&260\\\ -192&404&-504\\\
260&-504&648\end{bmatrix}\succ 0.$

The Pessimistic Program is

$\epsilon^{2}\bar{\lambda}+\min_{0\preceq X\preceq
I_{3}}~{}\operatorname{Tr}(DX)+\epsilon\sqrt{\operatorname{Tr}(E\Sigma)}.$

Following the procedure laid out in Proposition 7 and 8, we compute the
solution at varying $\epsilon$. In Figure 4, we plot the rank of the optimal
solution of the Pessimistic Program. Just as shown in Theorem 5, the rank
never increases with $\epsilon$. At small $\epsilon$ the rank of the solution
remains equal to that of the Bayesian solution, whereas at large $\epsilon$
the rank is null as $E\succ 0$. Precisely, Proposition 6 predicts that
whenever

$\epsilon\geq\frac{(\sqrt{f}-\operatorname{Tr}(P_{D}^{<0}D))^{2}-f}{\underline{\lambda}(E)}\approx
6.72,$

$\Sigma=0$ is a solution of the Pessimistic Program. As can be seen on Figure
4, this actually occurs as soon as $\epsilon\geq 1.7$.

Figure 4: Plot of the rank of the solution to the pessimistic program.

##  7 Conclusion

We have developed and explored the concept of almost-Bayesian agent in a
specific persuasion setting: quadratic persuasion. In contrast with previous
work, our approach does not assume that the thought process of the Receiver is
given and known, but instead that his actions are relatively close to those of
a Bayesian agent. This robust concept allows the Sender to account for
possible small mistakes the Receiver could commit, either for his inaccuracy
in estimating probabilities, or for his failure to exactly optimize his
expected utility. Such description of an agent is independent of the form of
the event space, the prior or the utilities, and as such is readily
transposable to other Bayesian persuasion problems, even though the analysis
could greatly differ.

Even the simplest case of almost-Bayesian quadratic persuasion, exposed in
Section 2, proved to be exactly intractable. Indeed, linear policies—the only
practical class of policies for isotropic priors—have been shown to not be
optimal, moreover finding the optimal linear policy is more than challenging.
Nonetheless, we could approximate Alice’s program (thanks to Theorem 3 and 4)
and solve it numerically. In addition, we have uncovered some structural
properties of the program, allowed by the specific setting we have chosen.
Alice is less keen to share information as Bob’s thought process is
increasingly departing from Bayesian updating, both truly (Theorem 1) and in
approximation (Theorem 5). In this case then, failing to be rigorously
Bayesian can be detrimental to Bob.

Some of the insights gained in this article are specific to the instance on
which we chose to demonstrate the almost-Bayesian agent concept, and partly
also to the approximations we derived. In the absence of additional structure
however, we suspect that Alice’s strategy facing an increasingly less Bayesian
would not change consistently. This is similar in spirit to the findings of
[31]: over all Bayesian persuasion problems, Alice does not consistently
prefer a type of agent, yet, considering more defined instances such as
situations with common interest, comparisons can be drawn.

## References

  * [1] F. Farokhi, A. M. Teixeira, and C. Langbort, “Estimation with strategic sensors,” IEEE Transactions on Automatic Control, vol. 62, no. 2, pp. 724–739, 2016.
  * [2] F. Farokhi, H. Sandberg, I. Shames, and M. Cantoni, “Quadratic gaussian privacy games,” in 2015 54th IEEE conference on decision and control (CDC), pp. 4505–4510, IEEE, 2015.
  * [3] E. Kazıklı, S. Gezici, and S. Yüksel, “Quadratic privacy-signaling games and the mmse information bottleneck problem for gaussian sources,” IEEE Transactions on Information Theory, 2022.
  * [4] V. Hebbar and C. Langbort, “A stackelberg signaling game for human-uav collaboration in a search-and-rescue context,” IFAC-PapersOnLine, vol. 53, no. 5, pp. 297–302, 2020.
  * [5] C. Peng and M. Tomizuka, “Bayesian persuasive driving,” in 2019 American Control Conference (ACC), pp. 723–729, IEEE, 2019.
  * [6] M. Le Treust and T. Tomala, “Information design for strategic coordination of autonomous devices with non-aligned utilities,” in 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 233–242, IEEE, 2016.
  * [7] S. Das, E. Kamenica, and R. Mirka, “Reducing congestion through information design,” in 2017 55th annual allerton conference on communication, control, and computing (allerton), pp. 1279–1284, IEEE, 2017.
  * [8] Y. Zhu and K. Savla, “On the stability of optimal bayesian persuasion strategy under a mistrust dynamics in routing games,” in 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 92–99, IEEE, 2018.
  * [9] Y. Zhu and K. Savla, “On routing drivers through persuasion in the long run,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4091–4096, IEEE, 2019.
  * [10] O. Massicot and C. Langbort, “Public signals and persuasion for road network congestion games under vagaries,” IFAC-PapersOnLine, vol. 51, no. 34, pp. 124–130, 2019.
  * [11] O. Massicot and C. Langbort, “Competitive comparisons of strategic information provision policies in network routing games,” IEEE Transactions on Control of Network Systems, 2021.
  * [12] Y. Zhu and K. Savla, “Information design in non-atomic routing games with partial participation: Computation and properties,” IEEE Transactions on Control of Network Systems, 2022.
  * [13] B. L. Ferguson, P. N. Brown, and J. R. Marden, “Avoiding unintended consequences: How incentives aid information provisioning in bayesian congestion games,” arXiv preprint arXiv:2204.06046, 2022.
  * [14] M. Le Treust and T. Tomala, “Persuasion with limited communication capacity,” Journal of Economic Theory, vol. 184, p. 104940, 2019.
  * [15] A. S. Vora and A. A. Kulkarni, “Information extraction from a strategic sender over a noisy channel,” in 2020 59th IEEE Conference on Decision and Control (CDC), pp. 354–359, IEEE, 2020.
  * [16] S. Dughmi and H. Xu, “Algorithmic bayesian persuasion,” in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 412–425, 2016.
  * [17] E. Kamenica and M. Gentzkow, “Bayesian persuasion,” American Economic Review, vol. 101, no. 6, pp. 2590–2615, 2011.
  * [18] V. P. Crawford and J. Sobel, “Strategic information transmission,” Econometrica: Journal of the Econometric Society, pp. 1431–1451, 1982.
  * [19] Y. Wang, “Bayesian persuasion with multiple receivers,” Available at SSRN 2625399, 2013.
  * [20] M. Gentzkow and E. Kamenica, “Bayesian persuasion with multiple senders and rich signal spaces,” Games and Economic Behavior, vol. 104, pp. 411–429, 2017.
  * [21] M. Castiglioni, A. Marchesi, A. Celli, and N. Gatti, “Multi-receiver online bayesian persuasion,” in International Conference on Machine Learning, pp. 1314–1323, PMLR, 2021.
  * [22] A. Nguyen and T. Y. Tan, “Bayesian persuasion with costly messages,” Journal of Economic Theory, vol. 193, p. 105212, 2021.
  * [23] M. Castiglioni, A. Celli, A. Marchesi, and N. Gatti, “Online bayesian persuasion,” Advances in Neural Information Processing Systems, vol. 33, pp. 16188–16198, 2020.
  * [24] Y. Zu, K. Iyer, and H. Xu, “Learning to persuade on the fly: Robustness against ignorance,” in Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 927–928, 2021.
  * [25] L. Matyskova, “Bayesian persuasion with costly information acquisition,” cERGE-EI Working Paper Series, no. 614, 2018.
  * [26] P. Dworczak and A. Pavan, “Preparing for the worst but hoping for the best: Robust (bayesian) persuasion,” Econometrica, vol. 90, no. 5, pp. 2017–2051, 2022.
  * [27] J. Hu and X. Weng, “Robust persuasion of a privately informed receiver,” Economic Theory, vol. 72, no. 3, pp. 909–953, 2021.
  * [28] R. J. Aumann, M. Maschler, and R. E. Stearns, Repeated games with incomplete information.  MIT press, 1995.
  * [29] M. Gentzkow and E. Kamenica, “A Rothschild-Stiglitz approach to Bayesian persuasion,” American Economic Review, vol. 106, no. 5, pp. 597–601, 2016\.
  * [30] O. Candogan and P. Strack, “Optimal disclosure of information to a privately informed receiver,” 2021.
  * [31] G. de Clippel and X. Zhang, “Non-bayesian persuasion,” Journal of Political Economy, vol. 130, no. 10, pp. 2594–2642, 2022.
  * [32] E. Kazıklı, S. Sarıtaş, S. Gezici, and S. Yüksel, “Optimal signaling with mismatch in priors of an encoder and decoder,” arXiv preprint arXiv:2101.00799, 2021.
  * [33] S. Kosterina, “Persuasion with unknown beliefs,” Theoretical Economics, vol. 17, no. 3, pp. 1075–1107, 2022.
  * [34] C. Camerer, “Bounded rationality in individual decision making,” Experimental economics, vol. 1, no. 2, pp. 163–183, 1998.
  * [35] D. J. Benjamin, “Errors in probabilistic reasoning and judgment biases,” Handbook of Behavioral Economics: Applications and Foundations 1, vol. 2, pp. 69–186, 2019.
  * [36] H. D. Dixon, Surfing Economics.  Bloomsbury Publishing, 2017.
  * [37] H. S. Witsenhausen, “A counterexample in stochastic optimum control,” SIAM Journal on Control, vol. 6, no. 1, pp. 131–147, 1968.
  * [38] W. Tamura, “Bayesian persuasion with quadratic preferences,” Available at SSRN 1987877, 2018.
  * [39] E. Akyol, C. Langbort, and T. Başar, “Information-theoretic approach to strategic communication as a hierarchical game,” Proceedings of the IEEE, vol. 105, no. 2, pp. 205–218, 2016.
  * [40] M. O. Sayin and T. Başar, “Bayesian persuasion with state-dependent quadratic cost measures,” IEEE Transactions on Automatic Control, vol. 67, no. 3, pp. 1241–1252, 2021.
  * [41] V. S. S. Nadendla, C. Langbort, and T. Başar, “Effects of subjective biases on strategic information transmission,” IEEE Transactions on Communications, vol. 66, no. 12, pp. 6040–6049, 2018.
  * [42] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear matrix inequalities in system and control theory.  SIAM, 1994.
  * [43] D. M. Grether, “Bayes rule as a descriptive model: The representativeness heuristic,” The Quarterly journal of economics, vol. 95, no. 3, pp. 537–557, 1980.
  * [44] J. T. Chang and D. Pollard, “Conditioning as disintegration,” Statistica Neerlandica, vol. 51, no. 3, pp. 287–317, 1997.
  * [45] M. Spivak, Calculus on manifolds: a modern approach to classical theorems of advanced calculus.  CRC press, 2018.
  * [46] H. Alzer, “On some inequalities for the gamma and psi functions,” Mathematics of computation, vol. 66, no. 217, pp. 373–389, 1997.

##  8 On Bayesian linear-quadratic persuasion

###  8.1 An important technical lemma

We had stressed the importance of Lemma 3. On the one hand, it is useful for
the Bayesian case, as it solves directly the lower-bound program (7). On the
other hand, it will prove a helpful tool later on as well, when we discuss the
non-Bayesian programs.

###### Proof of Lemma 3.

One way of obtaining $P_{D}^{<0},P_{D}^{\leq 0}$ is to diagonalize $D=R\Delta
R^{\top}$ with $R$ a rotation and $\Delta$ a diagonal matrix with decreasing
eigenvalues. Explicitly,

$\Delta=\begin{bmatrix}\Delta^{-}&0&0\\\ 0&0&0\\\
0&0&\Delta^{+}\end{bmatrix},$

where some of these diagonal blocks potentially have dimension $0$, and
$\Delta^{-},\Delta^{+}$ are definite. Then if $p\leq q$ are the number of
negative and non-positive eigenvalues, and $J_{r}$ is the diagonal matrix with
$r$ ones and $n-r$ zeroes in this order,

$P_{D}^{<0}=RJ_{p}R^{\top},~{}P_{D}^{\leq 0}=RJ_{q}R^{\top}.$

Define

$\displaystyle D^{-}$ $\displaystyle=-P_{D}^{<0}D\succeq 0,$ $\displaystyle
D^{+}$ $\displaystyle=(I-P_{D}^{\leq 0})D\succeq 0,$

so that $D=D^{+}-D^{-}$. Note that $P_{D}^{<0},P_{D}^{\leq 0},D$ all commute.
No matter $0\preceq X\preceq I_{n}$,

$\operatorname{Tr}(D^{+}X)\geq
0,~{}\operatorname{Tr}(D^{-}X)\leq\operatorname{Tr}(D^{-}).$

At the same time, these are equalities whenever $P_{D}^{<0}\preceq X\preceq
P_{D}^{\leq 0}$, thus all such $X$ are solution of

$\min_{0\preceq X\preceq I_{n}}~{}\operatorname{Tr}(DX).$

This condition turns out to be sufficient as well. Indeed, let $X$ be a
solution, we must have

$\operatorname{Tr}(D^{+}X)=0,~{}\operatorname{Tr}(D^{-}X)=\operatorname{Tr}(D^{-}).$

Since $\Delta^{+},\Delta^{-}$ are definite, this implies that $X$ takes the
general form

$X=R\begin{bmatrix}I_{p}&\star&\star\\\ \star&\star&\star\\\
\star&\star&0\end{bmatrix}R^{\top},$

where $\star$ are any block. Since $X\succeq 0$, we must rather have

$X=R\begin{bmatrix}I_{p}&\star&0\\\ \star&\star&0\\\
0&0&0\end{bmatrix}R^{\top},$

and since $I_{n}-X\succeq 0$, we must have

$X=R\begin{bmatrix}I_{p}&0&0\\\ 0&\star&0\\\ 0&0&0\end{bmatrix}R^{\top},$

where $0\preceq\star\preceq I_{q-p}$. All in all, this implies that
$P_{D}^{<0}\preceq X\preceq P_{D}^{\leq 0}$. ∎

###  8.2 About which covariances can be produced

###### Proof of Lemma 4.

First of all, $\mathcal{S}_{\nu}\subset\mathcal{S}$ is convex. Indeed, let
$t\in[0,1]$ and $\Sigma_{1},\Sigma_{2}\in\mathcal{S}_{\nu}$, they correspond
to the covariance of two random variables $\hat{x}_{1},\hat{x}_{2}$
respectively, which by nature satisfy

$\mathbb{E}[x\\!\mid\\!\hat{x}_{1}]=\hat{x}_{1},~{}\mathbb{E}[x\\!\mid\\!\hat{x}_{2}]=\hat{x}_{2}.$

Let $i$ be an independent random variable taking value $1$ with probability
$t$ and $2$ with probability $1-t$. Consider the message $y=\hat{x}_{i}$ and
the estimator it generates,

$\hat{x}=\mathbb{E}[x\\!\mid\\!y]=\mathbb{E}[\mathbb{E}[x\\!\mid\\!y,i]]=\mathbb{E}[y]=y,$

where the outer most expectation is taken with respect to $i$. In other words,
from the point of view of a Bayesian agent receiving $y$, either the message
was $y=\hat{x}_{1}$, in which case the estimator is $y$, or the message was
$y=\hat{x}_{2}$, in which case the estimator is still $y$. The covariance of
$\hat{x}$ is none other than

$\Sigma=\mathbb{E}[yy^{\top}]=\mathbb{E}[\mathbb{E}[\hat{x}_{i}\hat{x}_{i}^{\top}]]=t\Sigma_{1}+(1-t)\Sigma_{2}.$

Second, $\mathcal{S}$ is the convex hull of the set of orthogonal projection
matrices, thus we merely need to check that orthogonal projection matrices
belong to $\mathcal{S}_{\nu}$. Consider then $P$ an orthogonal projection
matrix. If $\Sigma=P$ is the covariance of $\hat{x}$, then the covariance of
$x-\hat{x}$ is $I_{n}-P$ and so (almost surely)

$\displaystyle x-\hat{x}$ $\displaystyle\in\operatorname{Im}(I_{n}-P)=\ker P$
$\displaystyle\hat{x}$ $\displaystyle\in\operatorname{Im}P=\ker(I_{n}-P).$

In turn,

$P(x-\hat{x})=(I_{n}-P)\hat{x}=0,$

that is,

$\hat{x}=Px.$

As a result, the message $\hat{x}$ defined just above is credible in the sense
that $\mathbb{E}[x\mid\hat{x}]=\hat{x}$. Conversely, if this message is
credible, its estimator is $\hat{x}$ itself, of covariance $P$. All in all,
checking whether $\mathcal{S}_{\nu}=\mathcal{S}$, amounts to checking that the
messages $y=Px$ with $P$ orthogonal projection matrix are credible in the
sense that

$\mathbb{E}[x\\!\mid\\!Px]=Px.$

This condition can be rewritten

$(I_{n}-P)\mathbb{E}[x\\!\mid\\!Px]=0.$

We also note that if it holds for all $P$ of rank $n-1$, then it holds for all
$P$. Indeed, assume it is so and let $P$ be just any orthogonal projection
matrix. Let $\\{e_{1},\dots,e_{n}\\}$ be an orthonormal basis of
$\mathbb{R}^{n}$ such that $\\{e_{1},\dots,e_{r}\\}$ forms a basis of
$\operatorname{Im}P$. Let then, for $i=r+1,\dots,n$,

$Q=I_{n}-P,~{}Q_{i}=e_{i}e_{i}^{\top},~{}P_{i}=I_{n}-Q_{i}.$

We have

$Q_{i}\mathbb{E}[x\\!\mid\\!Px]=\mathbb{E}[Q_{i}\mathbb{E}[x\\!\mid\\!P_{i}x]]=0,$

where the outer most expectation is taken with respect to $(P_{i}-P)x$.
Summing yields

$Q\mathbb{E}[x\\!\mid\\!Px]=0.\qed$

###### Proof of Lemma 5.

When $n=1$, the only orthogonal projection matrices are $P=0$ and $P=I_{1}$.
By the mere fact that $x$ is centered,

$\mathbb{E}[x\\!\mid\\!0]=0,~{}\mathbb{E}[x\\!\mid\\!x]=x.$

In higher dimensions, the condition is more stringent. Nonetheless, if $\nu$
is isotropic, all we have to verify is that

$\mathbb{E}[x_{1}\\!\mid\\!x_{2},\dots,x_{n}]=0.$

Since $\nu$ is invariant by the linear isometry that reverses $x_{1}$,

$\mathbb{E}[x_{1}\\!\mid\\!x_{2},\dots,x_{n}]=\mathbb{E}[-x_{1}\\!\mid\\!x_{2},\dots,x_{n}],$

directly yielding the expected result. ∎

##  9 Origins of the hypothesis class

###  9.1 Wasserstein distance

To formally set things, consider $p\geq 1$, and two Borel probability measures
$P,Q$ on $\mathbb{R}^{n}$ with finite $p$-th moment. Denote by $\Gamma(P,Q)$
the space of Borel measures on $\mathbb{R}^{n}\times\mathbb{R}^{n}$ with
marginals $P,Q$ respectively. In this article, we denote by $\|.\|$ the
standard Euclidean norm on $\mathbb{R}^{n}$. The $p$-Wasserstein distance
between $P$ and $Q$ is defined as

$W_{p}(P,Q)=\inf_{\pi\in\Gamma(P,Q)}~{}\left(\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}\|x-y\|^{p}\mathrm{d}\pi(x,y)\right)^{\frac{1}{p}}.$

These statistical distances find their origin in optimal transport: the
quantity $W_{p}(P,Q)^{p}$ corresponds to the minimal cost of displacing a pile
of sand distributed as $P$ into another pile distributed as $Q$, where
displacing a mass from $x$ to $y$ costs $\|x-y\|^{p}$. In order to prove
Proposition 1, we resort to the following intuitive lemma.

######  Lemma 9.

Denoting the mean of $P,Q$ by $\bar{P},\bar{Q}$,

$W_{p}(P,Q)\geq\|\bar{P}-\bar{Q}\|,$

with equality if $Q$ is a translation of $P$.

###### Proof of Lemma 9.

Let $\pi\in\Gamma(P,Q)$. As the map $(x,y)\mapsto\|x-y\|^{p}$ is convex,
Jensen’s inequality yields

$\displaystyle\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}\|x-y\|^{p}\mathrm{d}\pi(x,y)$
$\displaystyle\quad\geq\left\|\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}x\mathrm{d}\pi(x,y)-\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}y\mathrm{d}\pi(x,y)\right\|^{p}$
$\displaystyle\quad=\|\bar{P}-\bar{Q}\|^{p}.$

Therefore, as announced,

$W_{p}(P,Q)\geq\|\bar{P}-\bar{Q}\|.$

If $\mathrm{d}Q(y)=\mathrm{d}P(y+x_{0})$, we may consider $\pi$ defined by,

$\mathrm{d}^{2}\pi(x,y)=\mathrm{d}P(x)\mathrm{d}\delta_{x-x_{0}}(y).$

Of course, fixing $A\subset\mathbb{R}^{n}$ measurable,

$\displaystyle\pi(A\times\mathbb{R}^{n})$
$\displaystyle=\int_{A}\int_{\mathbb{R}^{n}}\mathrm{d}\delta_{x-x_{0}}(y)\mathrm{d}P(x)=\int_{A}\mathrm{d}P(x)$
$\displaystyle=P(A)$ $\displaystyle\pi(\mathbb{R}^{n}\times A)$
$\displaystyle=\int_{\mathbb{R}^{n}}\int_{A}\mathrm{d}\delta_{x-x_{0}}(y)\mathrm{d}P(x)$
$\displaystyle=\int_{\mathbb{R}^{n}}\mathds{1}_{A}(x-x_{0})\mathrm{d}Q(x-x_{0})$
$\displaystyle=Q(A),$

so $\pi\in\Gamma(P,Q)$. On the other hand,

$\displaystyle\int_{\mathbb{R}^{n}\times\mathbb{R}^{n}}\|x-y\|^{p}\mathrm{d}\pi(x,y)$
$\displaystyle\quad=\int_{\mathbb{R}^{n}}\int_{\mathbb{R}^{n}}\|x-y\|^{p}\mathrm{d}\delta_{x-x_{0}}(y)\mathrm{d}P(x)$
$\displaystyle\quad=\int_{\mathbb{R}^{n}}\|x_{0}\|^{p}\mathrm{d}P(x)=\|x_{0}\|^{p}.$

As a result,

$W_{p}(P,Q)\leq\|x_{0}\|=\|\bar{P}-\bar{Q}\|.\qed$

###### Proof of Proposition 1.

The proof is by double inclusion. Using the first implication of Lemma 9,

$\displaystyle\bar{\Lambda}(\bar{\mu})$
$\displaystyle=\\{\bar{\mu}^{\prime},~{}W_{p}(\mu^{\prime},\mu)\leq\epsilon\\}$
$\displaystyle\subset\\{\bar{\mu}^{\prime},~{}\|\mu^{\prime}-\mu\|\leq\epsilon\\}$
$\displaystyle=\bar{\mu}+\epsilon\mathcal{B}.$

On the other hand, let $v=\bar{\mu}+\epsilon u$ belong to this latter set,
i.e. with $u\in\mathcal{B}$. We may consider the distribution $\mu$ shifted by
$\epsilon u$. Surely, by Lemma 9,

$W_{p}(\mu^{\prime},\mu)=\|\bar{\mu}^{\prime}-\bar{\mu}\|=\epsilon\|u\|\leq\epsilon,$

so,

$\bar{\mu}^{\prime}=\bar{\mu}+\epsilon u=v\in\bar{\Lambda}(\bar{\mu}).\qed$

###  9.2 $f$-divergences

Fix $f\colon(0,\infty)\to\mathbb{R}$ convex with $f(1)=0$, and interpret
$f(0)$ as the limit of $f(\epsilon)$ as $\epsilon$ vanishes. Given $P\ll Q$
probability measures on $\mathcal{X}$, the $f$-divergence of $P$ from $Q$ is
defined as

$D_{f}(P\;\|\;Q)=\int_{\mathcal{X}}f\circ\frac{\mathrm{d}P}{\mathrm{d}Q}\mathrm{d}Q.$

This rather general definition encompasses many statistical distances: KL-
divergence, total variation, Jensen-Shannon Divergence, and so on. Moreover,
Rényi divergences can be expressed as a composition of a $f$-divergence by an
increasing function. Explicitly, for $\alpha>1$,

$R_{\alpha}(P\;\|\;Q)=\frac{1}{\alpha-1}\ln(1+D_{f_{\alpha}}(P\;\|\;Q)),$

with $f_{\alpha}(t)=t^{\alpha}-1$ and for $\alpha\in(0,1)$,

$R_{\alpha}(P\;\|\;Q)=\frac{1}{1-\alpha}\ln\frac{1}{1-D_{f_{\alpha}}(P\;\|\;Q)},$

with $f_{\alpha}(t)=1-t^{\alpha}$.

######  Lemma 10.

Let $\phi\colon\mathcal{X}\to\mathcal{Y}$ be a measurable injection, $P,Q$ be
probability measures on $\mathcal{X}$ such that $P\ll Q$, and $f$ convex with
$f(1)=0$. Then, the $f$-divergence of the pushforward of $P$ by $\phi$ from
the pushforward of $Q$ by $\phi$ is the $f$-divergence of $P$ from $Q$:

$D_{f}(\phi_{*}P\;\|\;\phi_{*}Q)=D_{f}(P\;\|\;Q).$

###### Proof of Lemma 10.

It is a straightforward change of variable. We first verify that $Q$-almost
everywhere

$\frac{\mathrm{d}(\phi_{*}P)}{\mathrm{d}(\phi_{*}Q)}\circ\phi=\frac{\mathrm{d}P}{\mathrm{d}Q}.$

Let $A\subset\mathcal{X}$ be measurable, by injectivity $\phi^{-1}(\phi(A))=A$
and so

$\displaystyle\int_{A}\frac{\mathrm{d}(\phi_{*}P)}{\mathrm{d}(\phi_{*}Q)}\circ\phi\,\mathrm{d}Q$
$\displaystyle=\int_{\phi(A)}\frac{\mathrm{d}(\phi_{*}P)}{\mathrm{d}(\phi_{*}Q)}\,\mathrm{d}(\phi_{*}Q)$
$\displaystyle=\phi_{*}P(\phi(A))$ $\displaystyle=P(A).$

Using this fact,

$\displaystyle D_{f}(\phi_{*}P\;\|\;\phi_{*}Q)$
$\displaystyle=\int_{\mathcal{Y}}f\circ\frac{\mathrm{d}(\phi_{*}P)}{\mathrm{d}(\phi_{*}Q)}\,\mathrm{d}(\phi_{*}Q)$
$\displaystyle=\int_{\mathcal{X}}f\circ\frac{\mathrm{d}(\phi_{*}P)}{\mathrm{d}(\phi_{*}Q)}\circ\phi\,\mathrm{d}Q$
$\displaystyle=\int_{\mathcal{X}}f\circ\frac{\mathrm{d}P}{\mathrm{d}Q}\,\mathrm{d}Q$
$\displaystyle=D_{f}(P\;\|\;Q).\qed$

###### Proof of Proposition 2.

Let $\mu$ be a projective belief, it is the result of message $y=\Sigma x$. As
a result, $\mu$ is a distribution with support in $y+\ker\Sigma$. In
particular, whenever $\mu^{\prime}\ll\mu$, its support also lies in
$y+\ker\Sigma$ and by convexity, $\bar{\mu}^{\prime}\in y+\ker\Sigma$. Since
$\mu\ll\mu$, $\bar{\mu}\in y+\ker\Sigma$ as well, so we conclude that

$\bar{\Lambda}(\bar{\mu})\subset\bar{\mu}+\ker\Sigma.$

Now, consider a rotation $O\in\mathcal{O}_{\ker\Sigma}$ that leaves
$(\ker\Sigma)^{\perp}=\operatorname{Im}\Sigma$ invariant. Proceed to a
rotation of the space so that “$x^{*}=Ox$ is the new $x$.” The belief
$O_{*}\mu$ is then the belief obtained when the prior is $O_{*}\nu=\nu$ and
the message is $y=\Sigma x=\Sigma x^{*}$, in other words, it is $\mu$ itself:
$O_{*}\mu=\mu$. In particular $\bar{\mu}$ is left invariant by all
$O\in\mathcal{O}_{\ker\Sigma}$, thus $\bar{\mu}\in\operatorname{Im}\Sigma$ and
so $\bar{\mu}=y$.

We are now in a position to show that $\bar{\Lambda}(\bar{\mu})$ is invariant
by $\mathcal{O}_{\ker\Sigma}$. Let $O\in\mathcal{O}_{\ker\Sigma}$ and
$m\in\bar{\Lambda}(\bar{\mu})$. This latter is the mean of some
$\mu^{\prime}\in\Lambda(\mu)$. In turn $O_{*}\mu^{\prime}\ll O_{*}\mu=\mu$
also satisfies

$D_{f}(O_{*}\mu^{\prime}\;\|\;\mu)=D_{f}(O_{*}\mu^{\prime}\;\|\;O_{*}\mu)=D_{f}(\mu^{\prime}\;\|\;\mu)\leq\epsilon,$

that is $O_{*}\mu^{\prime}\in\Lambda(\mu)$ and so
$O\bar{\mu}=Om\in\bar{\Lambda}(\bar{\mu})$.

All in all, this shows that

$\bar{\Lambda}(\bar{\mu})=\bar{\mu}+\delta(I_{n}-\Sigma)\mathcal{B},$

where $\delta\geq 0$ could be “infinite” and the ball $\mathcal{B}$ could
actually be open. This latter point matters less to Alice since the objective
$w(.,\bar{\mu})$ is continuous. ∎

###  9.3 Costly update

###### Proof of Proposition 3.

First rewrite the cost by completing the square,

$u(a,\mu)=(a-a^{*}(\bar{\mu}))^{\top}R_{22}(a-a^{*}(\bar{\mu}))+o,$

where $o$ is a constant. As a result,

$\displaystyle\\{a,~{}u(a,\mu)\leq u(a^{*}(\bar{\mu}),\mu)+\epsilon\\}$
$\displaystyle=a^{*}(\bar{\mu})+\sqrt{\epsilon}\sqrt{R_{22}}^{-1}\mathcal{B}$
$\displaystyle=a^{*}\\!\left(\bar{\mu}+\sqrt{\epsilon}R_{21}^{-1}\sqrt{R_{22}}\mathcal{B}\right).$

∎

###  9.4 Parametric models

Finally, instead of a generic model “$\mu^{\prime}$ is close to $\mu$,” Alice
can have an idea about Bob’s thought process. For instance, she may know that
Bob holds a different prior or that he gives more importance to his prior than
a Bayesian agent would. At the same time, she may not know his prior exactly
or how conservative his belief update is. This direction was recently
suggested by [31] while studying non-Bayesian persuasion, i.e. the case where
$\Lambda$ is a univalued map, aptly called belief distortion. We discuss here
how the type of robust hypothesis introduced in this article can provide
useful over-approximation for these so-called parametric models.

As it turns out, not all belief distortion models are well-adapted to
uncountable event spaces. For instance Grether’s $\alpha-\beta$ model [43]
does not generalize to richer event spaces unless $\alpha=1$, and even then,
the formula may terminate on an undetermined form, leaving Bob’s posteriors
undefined. A mismatched prior, on the other hand, poses no apparent technical
trouble provided Bob’s prior $\nu^{\prime}$ has finite second moment, [32].

At any rate, our approach could be deemed too conservative to adequately treat
this type of uncertainty. Alice would rather place the adversarial
maximization in front of the expectation, as now the failure of Bob to be
Bayesian is “coherent” across beliefs. This being said, the merit of our
robust hypothesis lies in that we can solve the ultimate program it generates,
and one could nonetheless include parameter uncertainty in such
hypothesis—albeit conservatively.

####  9.4.1 Mismatched prior

If Bob’s prior $\nu^{\prime}\ll\nu$ is such that

$\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}\in[s,\nicefrac{{1}}{{s}}],$

for some $s>0$, we can explicitly write Bob’s erroneous belief
$D_{\nu^{\prime}}(\mu)$ as a function of the Bayesian belief $\mu$ through

$\mathrm{d}D_{\nu^{\prime}}(\mu)(x)=\frac{\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}(x)}{\int_{\mathbb{R}^{n}}\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}\,\mathrm{d}\mu}\,\mathrm{d}\mu(x).$

When Alice does not know exactly $\nu^{\prime}$, this gives rise to a robust
hypothesis $\Lambda$. However, merely knowing that $\nu^{\prime}$ is close to
$\nu$ in any statistical sense is not enough. Informally, $\nu^{\prime}$ could
differ ever so slightly from $\nu$ on a narrow band of space, thereby inducing
a wildly different estimation $\bar{\mu}^{\prime}$ from $\bar{\mu}$ when the
message specifies $x$ is in this band. In this case, thus, we require a
stronger, more uniform, notion of proximity. When $\nu^{\prime}\ll\nu$, we let
$\epsilon(\nu^{\prime},\nu)$ be the infimum of all $\epsilon>0$ such that

$\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}\in\left[\frac{1}{1+\epsilon},1+\epsilon\right].$

The smaller $\epsilon(\nu^{\prime},\nu)$ is, the closer the distributions are.
With this notation in hand, we are in a position to state the following
proposition.

######  Proposition 10.

Let the robust hypothesis $\Lambda$ be given by

$\Lambda(\mu)=\\{D_{\nu^{\prime}}(\mu),~{}\nu^{\prime}\ll\nu,~{}\epsilon(\nu^{\prime},\nu)\leq\epsilon\\},$

then

$\bar{\Lambda}(\mu)\subset\bar{\mu}+\sqrt{2\epsilon+\epsilon^{2}}\sqrt{\operatorname{Tr}\Sigma_{\mu}}\,\mathcal{B}.$

###### Proof of Proposition 10.

We first explain the formula we had announced. Bayes’ rule is better
characterized in terms of joint probabilities. The distribution $\tau$ of
posteriors $\mu_{y}$ is the essentially unique one such that

$\mathrm{d}\sigma_{x}(y)\mathrm{d}\nu(x)=\mathrm{d}\mu_{y}(x)\mathrm{d}\tau(y).$

A nitty-gritty discussion would dive into the technical details of this
definition, where notably the disintegration theorem would be of great help
(see [44]), but we choose to remain informal for the proof of this relatively
less important proposition. In this context then,

$\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}(x)=\frac{\mathrm{d}\tau^{\prime}}{\mathrm{d}\tau}(y)\frac{\mathrm{d}\mu^{\prime}_{y}}{\mathrm{d}\mu_{y}}(x).$

The formula then follows from the fact that $\mu^{\prime}_{y}$ is a
probability measure.

Let then $\nu^{\prime}\ll\nu$ be such that
$\epsilon(\nu^{\prime},\nu)\leq\epsilon$. The mean difference between the
distorted belief and the Bayesian belief is

$\overline{\mathrm{d}D_{\nu^{\prime}}(\mu)}-\bar{\mu}=\int_{\mathbb{R}^{n}}x\left(\frac{\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}(x)}{\int_{\mathbb{R}^{n}}\frac{\mathrm{d}\nu^{\prime}}{\mathrm{d}\nu}\,\mathrm{d}\mu}-1\right)\,\mathrm{d}\mu(x).$

The condition $\epsilon(\nu^{\prime},\nu)\leq\epsilon$ implies that the
bracketed term has magnitude at most $\sqrt{2\epsilon+\epsilon^{2}}$. The
Cauchy-Schwarz inequality then yields

$\left\|\overline{\mathrm{d}D_{\nu^{\prime}}(\mu)}-\bar{\mu}\right\|\leq\sqrt{2\epsilon+\epsilon^{2}}\sqrt{\operatorname{Tr}\Sigma_{\mu}}.\qed$

####  9.4.2 Affine distortion

Another model—termed affine distortion—accounts for a bias towards a specific
“ideal” belief, which may or may not be Bob’s prior. Formally, the erroneous
belief is

$\mu^{\prime}=\chi\mu+(1-\chi)\mu^{*},$

where $\chi\in[0,1]$ is a parameter such that $\chi=1$ corresponds to a
Bayesian agent, and $\mu^{*}$ is the ideal belief. This latter can be
interpreted as the belief Bob would like to hold from a motivated updating
perspective. Again, a robust hypothesis appears as soon as the parameters are
not well-known. For instance, $\chi$ belongs to some subinterval
$[a,b]\subset[0,1]$, or $\mu^{*}$ is close to some belief $\mu^{*}_{0}$ in
some statistical sense. We explore the latter possibility in the following
proposition.

######  Proposition 11.

Let the robust hypothesis $\Lambda$ be given by

$\Lambda(\mu)=\\{\chi\mu+(1-\chi)\mu^{*},~{}\mu^{*}\ll\mu^{*}_{0},~{}W_{p}(\mu^{*},\mu^{*}_{0})\leq\epsilon\\},$

then

$\bar{\Lambda}(\mu)=\chi\bar{\mu}+(1-\chi)\bar{\mu}_{0}^{*}+\epsilon\,\mathcal{B}.$

###### Proof of Proposition 11.

Observe that

$\Lambda(\mu)=\chi\mu+(1-\chi)\\{\mu^{*},~{}\mu^{*}\ll\mu^{*}_{0},~{}W_{p}(\mu^{*},\mu^{*}_{0})\leq\epsilon\\},$

the last set is none other than $\Lambda$ in the case of Wasserstein distance.
In turn,

$\bar{\Lambda}(\mu)=\chi\bar{\mu}+(1-\chi)\bar{\mu}_{0}^{*}+\epsilon\,\mathcal{B}.\qed$

When $\chi$ is allowed to vary as well, $\bar{\Lambda}$ takes a rounded
cylindrical shape which is perhaps not as convenient to fit in an ellipsoid.

##  10 The non-Bayesian programs

###  10.1 Rewriting the true program

Akin to Lemma 2, Alice first rewrites the objective of her program in the non-
Bayesian case, this is the object of Lemma 6. The proof does not use the
reduction $\bar{\nu}=0$ and $\Sigma_{\nu}=I_{n}$ to retain visibility over the
various terms at play.

###### Proof of Lemma 6.

Begin by rewriting the objective of (10) being maximized,

$\displaystyle v(\bar{\mu}^{\prime},\mu)=$
$\displaystyle~{}\mathbb{E}_{\mu}\\!\left[\begin{bmatrix}x\\\
\bar{\mu}^{\prime}\end{bmatrix}^{\top}Q\begin{bmatrix}x\\\
\bar{\mu}^{\prime}\end{bmatrix}+l^{\top}\begin{bmatrix}x\\\
\bar{\mu}^{\prime}\end{bmatrix}+r\right]$ $\displaystyle=$
$\displaystyle~{}\operatorname{Tr}\\!\left(Q\begin{bmatrix}\bar{\mu}\bar{\mu}^{\top}+\Sigma_{\mu}&\bar{\mu}\bar{\mu}^{\prime}\\!{}^{\top}\\\
\bar{\mu}^{\prime}\bar{\mu}^{\top}&\bar{\mu}^{\prime}\bar{\mu}^{\prime}\\!{}^{\top}\end{bmatrix}\right)+l^{\top}\begin{bmatrix}\bar{\mu}\\\
\bar{\mu}^{\prime}\end{bmatrix}+r$ $\displaystyle=$
$\displaystyle~{}\operatorname{Tr}\\!\left(Q\begin{bmatrix}\bar{\mu}\bar{\mu}^{\top}+\Sigma_{\mu}&\bar{\mu}\bar{\mu}^{\top}\\\
\bar{\mu}\bar{\mu}^{\top}&\bar{\mu}\bar{\mu}^{\top}\end{bmatrix}\right)+l^{\top}\begin{bmatrix}\bar{\mu}\\\
\bar{\mu}\end{bmatrix}+r$
$\displaystyle+\operatorname{Tr}\\!\left(Q\begin{bmatrix}0&\bar{\mu}\eta^{\top}\\\
\eta\bar{\mu}^{\top}&\eta\bar{\mu}^{\top}+\bar{\mu}\eta^{\top}+\eta\eta^{\top}\end{bmatrix}\right)+l^{\top}\begin{bmatrix}0\\\
\eta\end{bmatrix}.$

Clearly, this depends quadratically on $\eta$. The quadratic coefficient is
constant, and the linear coefficient solely depend on $\bar{\mu}$. If we
average the coefficient constant with respect to $\eta$, we obtain the
Bayesian objective

$\operatorname{Tr}\\!\left(Q\begin{bmatrix}\bar{\nu}\bar{\nu}^{\top}+\Sigma_{\nu}&\bar{\nu}\bar{\nu}^{\top}+\Sigma\\\
\bar{\nu}\bar{\nu}^{\top}+\Sigma&\bar{\nu}\bar{\nu}^{\top}+\Sigma\end{bmatrix}\right)+l^{\top}\begin{bmatrix}\bar{\nu}\\\
\bar{\nu}\end{bmatrix}+r=\operatorname{Tr}(D\Sigma)+c,$

where again
$\Sigma=\mathbb{E}_{\bar{\tau}}[(\bar{\mu}-\bar{\nu})(\bar{\mu}-\bar{\nu})^{\top}]$
is the covariance of the estimate, as before. On the other, we may develop the
linear and quadratic term in $\eta$,

$\displaystyle w(\eta,\bar{\mu})$
$\displaystyle=\operatorname{Tr}\\!\left(Q\begin{bmatrix}0&\bar{\mu}\eta^{\top}\\\
\eta\bar{\mu}^{\top}&\eta\bar{\mu}^{\top}+\bar{\mu}\eta^{\top}+\eta\eta^{\top}\end{bmatrix}\right)+l_{2}^{\top}\eta$
$\displaystyle=(2(Q_{21}+Q_{22})\bar{\mu}+l_{2})^{\top}\eta+\eta^{\top}Q_{22}\eta.\qed$

###  10.2 The no-information theorems

###### Proof of Theorem 1.

Following Lemma 3, $\Sigma=0$ is a solution of (7) if and only if
$P_{D}^{<0}=0$, that is if and only if $D\succeq 0$. In this case, we like to
rewrite the objective of (11) as

$\mathbb{E}_{\bar{\tau}}\\!\left[\bar{\mu}^{\top}D\bar{\mu}+c+\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right].$

All the terms inside the expectation are convex in $\bar{\mu}$, this rather
clear for the two first ones. Regarding the last term, let
$\bar{\mu}_{1},\bar{\mu}_{2}\in\mathbb{R}^{n}$ and $\lambda\in[0,1]$, we have

$\displaystyle\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\lambda\bar{\mu}_{1}+(1-\lambda)\bar{\mu}_{2})$
$\displaystyle\quad=\max_{\eta\in C\mathcal{B}}~{}\lambda
w(\eta,\bar{\mu}_{1})+(1-\lambda)w(\eta,\bar{\mu}_{2})$
$\displaystyle\quad\leq\lambda\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu}_{1})+(1-\lambda)\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu}_{2}).$

Convexity being established, we may use Jensen’s inequality,

$\displaystyle\mathbb{E}_{\bar{\tau}}\\!\left[\bar{\mu}^{\top}D\bar{\mu}+c+\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]$
$\displaystyle\quad\geq\mathbb{E}_{\delta_{\bar{\nu}}}\\!\left[\bar{\mu}^{\top}D\bar{\mu}+c+\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right].$

The distribution $\delta_{\bar{\nu}}$ informally corresponds to substituting
$\bar{\mu}$ with its average, $\bar{\nu}$. This distribution is the result of
the no-information policy, for which the estimate is constantly $\bar{\nu}$. ∎

###### Proof of Theorem 2.

Consider the nested program of the error term of (11). Surely

$\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})=\max_{\eta\in\mathcal{B}}~{}2v^{\top}\eta+\eta^{\top}C^{\top}Q_{22}C\eta$

where

$v=C^{\top}((Q_{21}+Q_{22})\bar{\mu}+\nicefrac{{l_{2}}}{{2}}).$

The largest eigenvalue of $C^{\top}Q_{22}C$ is $\bar{\lambda}$, let $P$ be the
orthogonal projection on the corresponding eigenspace. If $Pv\neq 0$, consider
the argument $\eta=\nicefrac{{Pv}}{{\|Pv\|}}$, it yields

$\max_{\eta\in C\mathcal{B}}~{}w(\eta,\bar{\mu})\geq\bar{\lambda}+2\|Pv\|.$

If $Pv=0$, considering any $\eta$ of unit length in the principal eigenspace
(i.e. such that $P\eta=\eta$) as an argument yields the same lower bound.

For a converse bound, we first resort to Lemma 11, defined and proved soon
below. With the help of an S-procedure (see [42] for a survey), it shows that

$\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})=\inf_{\lambda>\bar{\lambda}}~{}\lambda+v^{\top}(\lambda
I_{n}-C^{\top}Q_{22}C)^{-1}v.$

Considering the argument $\bar{\lambda}+\|Pv\|$ when $Pv\neq 0$ yields

$\displaystyle\max_{\eta\in C\mathcal{B}}~{}w(\eta,\bar{\mu})$
$\displaystyle\quad\leq\bar{\lambda}+\|Pv\|+v^{\top}(\bar{\lambda}I_{n}-C^{\top}Q_{22}C+\|Pv\|I_{n})^{-1}v$
$\displaystyle\quad=\bar{\lambda}+\|Pv\|+(Pv)^{\top}(\bar{\lambda}I_{n}-C^{\top}Q_{22}C+\|Pv\|I_{n})^{-1}Pv$
$\displaystyle\quad\phantom{=}+(v-Pv)^{\top}(\bar{\lambda}I_{n}-C^{\top}Q_{22}C+\|Pv\|I_{n})^{-1}(v-Pv)$
$\displaystyle\quad\leq\bar{\lambda}+2\|Pv\|+\frac{\|(I_{n}-P)v\|^{2}}{\bar{\lambda}-\bar{\lambda}_{2}}.$

When $Pv=0$, for $\lambda>\bar{\lambda}$,

$\lambda+v^{\top}(\lambda I_{n}-C^{\top}Q_{22}C)^{-1}v\\\
\leq\lambda+\frac{\|v-Pv\|^{2}}{\lambda-\lambda_{2}},$

and therefore, letting $\lambda$ tend to $\bar{\lambda}$, we obtain the same
bound as before.

As $4\mathbb{E}[\|v\|^{2}]=f+\operatorname{Tr}E$, taking the expectation of
both bounds yields

$\displaystyle\bar{\lambda}+2\mathbb{E}[\|Pv\|]+\frac{f+\operatorname{Tr}E}{4(\bar{\lambda}-\bar{\lambda}_{2})}$
$\displaystyle\geq\mathbb{E}_{\bar{\tau}}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]$
$\displaystyle\geq\bar{\lambda}+2\mathbb{E}[\|Pv\|].$

The no-information policy costs at least

$c+\bar{\lambda}+2\|P\mathbb{E}[v]\|.$

On the other hand, there exists $u$ unit-vector such that

$PC^{\top}((Q_{21}+Q_{22})u=0$

since that matrix is singular. The policy projective policy $y=uu^{\top}x$
induces the estimate $\bar{\mu}=(u^{\top}x)u$ and thus costs at most

$\displaystyle
c+u^{\top}Du+\bar{\lambda}+2\|P\mathbb{E}[v]\|+\frac{f+\operatorname{Tr}E}{4(\bar{\lambda}-\bar{\lambda}_{2})}$
$\displaystyle\quad<c+\bar{\lambda}+2\|P\mathbb{E}[v]\|.\qed$

###  10.3 Technical lemmas

The first technical lemma consist in turning the inner maximization of (11)
into a univariate convex program; this is the object of the following lemma.

######  Lemma 11.

Given $Q$ a positive semi-definite matrix, $C$ a matrix and $v$ a vector of
appropriate dimensions,

$\max_{\eta\in\mathcal{B}}~{}\eta^{\top}Q\eta+2v^{\top}\eta=\inf_{\lambda>\overline{\lambda}(Q)}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v.$

This can be readily applied to our problem with $C^{\top}Q_{22}C$ instead of
$Q$ and

$v=C^{\top}((Q_{21}+Q_{22})\bar{\mu}+\nicefrac{{l_{2}}}{{2}}).$

After substitution,

$\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})=\inf_{\lambda>\bar{\lambda}}~{}\lambda+v^{\top}(\lambda
I_{n}-C^{\top}Q_{22}C)^{-1}v.$

The appeal of this expression is that it is a one-dimensional convex program,
thus for given parameters it is inexpensive to compute its value. Of course,
this is merely a first step since this value is to be averaged over all
$\bar{\mu}$. Another advantage of this program is that we can actually provide
upper and lower bounds matched up to a constant ratio not so far from $1$.

######  Lemma 12.

Given $Q$ a positive semidefinite matrix, $v\in\mathbb{R}^{n}$, for all
$\beta\in[0,1]$ we have

$\displaystyle\overline{\lambda}(Q)+2\|v\|$
$\displaystyle\geq\inf_{\lambda>\overline{\lambda}(Q)}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v$
$\displaystyle\geq(1-\beta^{2})\overline{\lambda}(Q)+2\beta\|v\|.$

Of course $\beta$ can be selected carefully so to match the bounds up to a
constant, but we will rather set $\beta$ at our convenience later to combine
better with further approximations. For Alice, this means that for all
$\beta\in[0,1]$,

$\displaystyle(1-\beta^{2})\bar{\lambda}+2\beta\mathbb{E}[\|v\|]$
$\displaystyle\leq\mathbb{E}\\!\left[\max_{\eta\in
C\mathcal{B}}~{}w(\eta,\bar{\mu})\right]$ (18)
$\displaystyle\leq\bar{\lambda}+2\mathbb{E}[\|v\|],$

where

$\displaystyle\bar{\lambda}$
$\displaystyle=\overline{\lambda}(C^{\top}Q_{22}C)$ $\displaystyle v$
$\displaystyle=C^{\top}((Q_{21}+Q_{22})\bar{\mu}+\nicefrac{{l_{2}}}{{2}}).$

The next step, of course, is to obtain a good estimate of $\mathbb{E}[\|v\|]$.
Jensen’s inequality directly yields

$\mathbb{E}[\|v\|]\leq\sqrt{\mathbb{E}[\|v\|^{2}]},$

this can readily be used for the Pessimistic Program, since it only depends on
$\Sigma$, $v$ being an affine function of $\bar{\mu}$. On the other hand,
$\bar{\mu}$ could a priori take on any form, so we cannot hope for a good
general converse inequality. Nonetheless, it is always true that

$\mathbb{E}[\|v\|]\geq\|\mathbb{E}[v]\|,$

and if $\|\mathbb{E}[v]\|$ is “large enough” (in a specific sense we will
broach later), this turns out to be useful enough. Otherwise, we can restrict
our attention to _projective policies,_ i.e. those for which $\hat{x}=Px$,
this is the object of the following lemma.

######  Lemma 13.

When $v$ is an affine function of $x$,

$\mathbb{E}[\|v\|]\geq\frac{\mathbb{E}[|x_{1}|]}{\sqrt{1+\mathbb{E}[|x_{1}|]^{2}}}\sqrt{\mathbb{E}[\|v\|^{2}]},$

noting $x_{1}$ the first coordinate of $x$.

For the sake of simplicity, we are brought to introduce

$f=l_{2}^{\top}CC^{\top}l_{2},~{}E=4(Q_{12}+Q_{22})CC^{\top}(Q_{21}+Q_{22}).$

With these notations,

$4\|\mathbb{E}[v]\|^{2}=f,~{}4\mathbb{E}[\|v\|^{2}]=f+\operatorname{Tr}(E\Sigma).$

Combining Lemma 11 and 12, as in (18), at $\beta=0$ and $\beta=1$, yields
Theorem 3. Using Lemma 11, 12 and 13 with

$\beta=\frac{\sqrt{5+\frac{4}{\mathbb{E}[|x_{1}|]^{2}}}-1}{2\sqrt{1+\frac{1}{\mathbb{E}[|x_{1}|]^{2}}}},$

so that,

$1-\beta^{2}=\beta\frac{\mathbb{E}[|x_{1}|]}{\sqrt{1+\mathbb{E}[|x_{1}|]^{2}}}=\gamma,$

we obtain the result about projective policies of Theorem 4.

Whenever

$f\geq\mathbb{E}[|x_{1}|]^{2}\operatorname{Tr}E,$

no matter the policy,

$\mathbb{E}[\|v\|]\geq\|\mathbb{E}[v]\|\geq\frac{\mathbb{E}[|x_{1}|]}{\sqrt{1+\mathbb{E}[|x_{1}|]^{2}}}\sqrt{\mathbb{E}[\|v\|^{2}]},$

which is exactly the result of Lemma 13. Hence, in this case, the lower bound
specific to projective policies also applies general policies, this is the
second result of Theorem 4.

###  10.4 Proofs of the technical lemmas

###### Proof of Lemma 11.

First let

$F_{1}=\begin{bmatrix}-1&0\\\
0&I_{n}\end{bmatrix},~{}F_{2}(t)=\begin{bmatrix}-t&v^{\top}\\\
v&Q\end{bmatrix},$

so that $\eta\in\mathcal{B}$ if and only if

$\begin{bmatrix}1\\\ \eta\end{bmatrix}^{\top}F_{1}\begin{bmatrix}1\\\
\eta\end{bmatrix}\leq 0,$

and moreover

$\eta^{\top}Q\eta+2v^{\top}\eta-t=\begin{bmatrix}1\\\
\eta\end{bmatrix}^{\top}F_{2}(t)\begin{bmatrix}1\\\ \eta\end{bmatrix}.$

By the S-lemma (see [42]),

$\displaystyle\big{(}\eta\in\mathcal{B}\implies\eta^{\top}Q\eta+2v^{\top}\eta-t\leq
0\big{)}$ $\displaystyle\quad\iff~{}\big{(}\exists\lambda\geq 0,~{}\lambda
F_{1}\succeq F_{2}(t)\big{)},$

so we can rewrite

$\displaystyle\max_{\eta\in\mathcal{B}}~{}\eta^{\top}Q\eta+2v^{\top}\eta$
$\displaystyle\quad=\begin{aligned} \min_{t}&\quad t\\\
\mathrm{s.t.}&\quad\eta\in\mathcal{B}\implies\eta^{\top}Q\eta+2v^{\top}\eta-t\leq
0\end{aligned}$ $\displaystyle\quad=\begin{aligned} \min_{\lambda,t}&\quad
t.\\\ \mathrm{s.t.}&\quad\lambda\geq 0\\\ &\quad\lambda F_{1}\succeq
F_{2}(t)\end{aligned}$

We notice that

$(\lambda+\epsilon)F_{1}-F_{2}(t+2\epsilon)=\lambda F_{1}-F_{2}(t)+\epsilon
I_{n+1},$

therefore if $\lambda F_{1}\succeq F_{2}(t)$, then for all $\epsilon>0$,

$(\lambda+\epsilon)F_{1}\succ F_{2}(t+2\epsilon).$

Conversely, if the above holds, then at the limit where $\epsilon$ vanishes,
$\lambda F_{1}\succeq F_{2}(t)$. We may thus write

$\max_{\eta\in\mathcal{B}}~{}\eta^{\top}Q\eta+2v^{\top}\eta=\begin{aligned}
\inf_{\lambda,t}&\quad t.\\\ \mathrm{s.t.}&\quad\lambda>0\\\ &\quad\lambda
F_{1}\succ F_{2}(t).\end{aligned}$

By Schur complement (see [42]), $\lambda F_{1}\succ F_{2}(t)$ if and only if

$\begin{cases}\lambda I_{n}-Q\succ 0\\\ -\lambda+t-v^{\top}(\lambda
I_{n}-Q)^{-1}v>0.\end{cases}$

The first condition boils down to $\lambda>\bar{\lambda}(Q)$, and, as a
result,

$\max_{\eta\in\mathcal{B}}~{}\eta^{\top}Q\eta+2v^{\top}\eta=\inf_{\lambda>\bar{\lambda}(Q)}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v.\qed$

###### Proof of Lemma 12.

When $v=0$, the upper bound is trivial. When $v\neq 0$, we may substitute

$\lambda=\overline{\lambda}(Q)+\|v\|,$

and obtain

$\displaystyle\inf_{\lambda>\overline{\lambda}(Q)}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v$
$\displaystyle\quad\leq\overline{\lambda}(Q)+\|v\|+v^{\top}(\|v\|I_{n}+\overline{\lambda}(Q)I_{n}-Q)^{-1}v$
$\displaystyle\quad\leq\overline{\lambda}(Q)+2\|v\|.$

Conversely, forget $Q,v$ for a second and fix some $\gamma>0$, we have

$\displaystyle\inf_{\begin{subarray}{c}Q\succeq 0\\\
\bar{\lambda}=\overline{\lambda}(Q)\\\ v\neq
0\end{subarray}}~{}\frac{\inf_{\lambda>\bar{\lambda}}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v}{\bar{\lambda}+2\gamma\|v\|}$
$\displaystyle\quad=\inf_{\begin{subarray}{c}Q\succeq 0\\\
\bar{\lambda}>\overline{\lambda}(Q)\\\ v\neq
0\end{subarray}}~{}\frac{\inf_{\lambda>\bar{\lambda}}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v}{\bar{\lambda}+2\gamma\|v\|}$
$\displaystyle\quad=\inf_{\begin{subarray}{c}\lambda>\bar{\lambda}>0\\\
\bar{\lambda}I_{n}\succeq Q\succeq 0\\\ v\neq
0\end{subarray}}~{}\frac{\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v}{\bar{\lambda}+2\gamma\|v\|}$
$\displaystyle\quad=\inf_{\begin{subarray}{c}\lambda>\bar{\lambda}>0\\\ v\neq
0\end{subarray}}~{}\frac{\lambda+\frac{v^{\top}v}{\lambda}}{\bar{\lambda}+2\gamma\|v\|}$
$\displaystyle\quad=\inf_{\lambda,r>0}~{}\frac{\lambda+\frac{r^{2}}{\lambda}}{\lambda+2\gamma
r}$ $\displaystyle\quad=\inf_{t>0}~{}\frac{1+t^{2}}{1+2\gamma t}$
$\displaystyle\quad=\frac{\sqrt{1+4\gamma^{2}}-1}{2\gamma^{2}}.$

For a more legible result, we let

$\beta=\frac{\sqrt{1+4\gamma^{2}}-1}{2\gamma}\in(0,1),$

so that

$\gamma=\frac{\beta}{1-\beta^{2}}.$

As a result, for all $Q\succeq 0$, $v\in\mathbb{R}^{n}$ and $\beta\in[0,1]$
(the result at $\beta=0,1$ is obtained by continuity of the right-hand side in
$\beta$),

$\inf_{\lambda>\overline{\lambda}(Q)}~{}\lambda+v^{\top}(\lambda
I_{n}-Q)^{-1}v\geq(1-\beta^{2})\overline{\lambda}(Q)+2\beta\|v\|.\qed$

###### Proof of Lemma 13.

Consider the linear case first, $v=Lx$ for some matrix $L\neq 0$, then

$\displaystyle\frac{\mathbb{E}[\|Lx\|]}{\sqrt{\mathbb{E}[\|Lx\|^{2}]}}$
$\displaystyle=\mathbb{E}\\!\left[\sqrt{x^{\top}\frac{L^{\top}L}{\operatorname{Tr}(L^{\top}L)}x}\right]$
$\displaystyle\geq\inf_{\begin{subarray}{c}S\succeq 0\\\
\operatorname{Tr}S=1\end{subarray}}~{}\mathbb{E}\\!\left[\sqrt{x^{\top}Sx}\right]$
$\displaystyle=\mathbb{E}[|x_{1}|],$

as $S\succeq 0\mapsto\sqrt{x^{\top}Sx}$ is concave for each $x$, and the
distribution of $x$ is invariant by rotation. As a result, even when $L=0$,

$\mathbb{E}[\|Lx\|]\geq\mathbb{E}[|x_{1}|]\sqrt{\mathbb{E}[\|Lx\|^{2}]}.$

What happens when there is an offset? We first notice that, by Jensen’s
inequality,

$\mathbb{E}[\|v\|]\geq\|\mathbb{E}[v]\|=\|v_{0}\|,$

then

$\mathbb{E}[\|v_{0}+Lx\|]=\mathbb{E}\\!\left[\frac{1}{2}\|v_{0}+Lx\|+\frac{1}{2}\|-v_{0}+Lx\|\right],$

since $x$ is symmetric by inversion. Then since $\|.\|$ is convex,

$\mathbb{E}[\|v_{0}+Lx\|]\geq\mathbb{E}[\|Lx\|]\geq\mathbb{E}[|x_{1}|]\sqrt{\operatorname{Tr}(L^{\top}L)}.$

Assume that either $v_{0}\neq 0$ or $L\neq 0$. If

$\mathbb{E}[|x_{1}|]\sqrt{\operatorname{Tr}(L^{\top}L)}\geq\|v_{0}\|,$

then

$\displaystyle\frac{\mathbb{E}[|x_{1}|]\sqrt{\operatorname{Tr}(L^{\top}L)}}{\sqrt{\mathbb{E}[\|v_{0}+Lx\|^{2}]}}$
$\displaystyle=\frac{\mathbb{E}[|x_{1}|]\sqrt{\operatorname{Tr}(L^{\top}L)}}{\sqrt{\|v_{0}\|^{2}+\operatorname{Tr}(L^{\top}L)}}$
$\displaystyle\geq\frac{\mathbb{E}[|x_{1}|]}{\sqrt{1+\mathbb{E}[|x_{1}|]^{2}}}.$

Otherwise

$\displaystyle\frac{\|v_{0}\|}{\sqrt{\mathbb{E}[\|v_{0}+Lx\|^{2}]}}$
$\displaystyle=\frac{\|v_{0}\|}{\sqrt{\|v_{0}\|^{2}+\operatorname{Tr}(L^{\top}L)}}$
$\displaystyle\geq\frac{\mathbb{E}[|x_{1}|]}{\sqrt{1+\mathbb{E}[|x_{1}|]^{2}}}.$

All in all, when $v$ is an affine function of $x$,

$\mathbb{E}[\|v\|]\geq\frac{\mathbb{E}[|x_{1}|]}{\sqrt{1+\mathbb{E}[|x_{1}|]^{2}}}\sqrt{\mathbb{E}[\|v\|^{2}]}.\qed$

When $\nu$ is unidimensional and Gaussian, Lemma 8 refines the result of Lemma
13. We present its proof now.

###### Proof of Lemma 8.

The upper bound is a mere application of Jensen’s inequality, so the crux is
to prove the converse bound. The result is trivial when $b=0$, consider thus
$b\neq 0$. We may further rescale the problem by $b$ so that we merely need to
solve the case $b=1$. Finally since $\nu$ is symmetric, we only really need to
solve the case $a\geq 0$.

With these reductions in hand, we observe that whenever

$a\geq\sqrt{\frac{2}{\pi-2}}\approx 1.32,$

we can directly conclude that

$\frac{\mathbb{E}[|a+x|]}{\sqrt{\mathbb{E}[(a+x)^{2}]}}\geq\frac{\mathbb{E}[a+x]}{\sqrt{\mathbb{E}[(a+x)^{2}]}}=\frac{a}{\sqrt{1+a^{2}}}\geq\sqrt{\frac{2}{\pi}}.$

On the other hand,

$\displaystyle\mathbb{E}[|a+x|]$
$\displaystyle=\frac{1}{2}\mathbb{E}[|x+a|+|x-a|]$
$\displaystyle=\mathbb{E}[|x|]+\mathbb{E}[(a-|x|)\mathds{1}_{|x|\leq a}]$
$\displaystyle=\sqrt{\frac{2}{\pi}}+\sqrt{\frac{2}{\pi}}\left(a\int_{0}^{a}e^{-\nicefrac{{x^{2}}}{{2}}}\,\mathrm{d}x+1-e^{-\nicefrac{{a^{2}}}{{2}}}\right)$
$\displaystyle\geq\sqrt{\frac{2}{\pi}}\left(2+(a-1)e^{-\nicefrac{{a^{2}}}{{2}}}\right).$

When $\sqrt{3}\geq a\geq 1$,

$\frac{2+(a-1)e^{-\nicefrac{{a^{2}}}{{2}}}}{\sqrt{1+a^{2}}}\geq\frac{2}{\sqrt{1+a^{2}}}\geq
1,$

and when $a\leq 1$,

$\frac{2+(a-1)e^{-\nicefrac{{a^{2}}}{{2}}}}{\sqrt{1+a^{2}}}\geq\frac{a+1}{\sqrt{1+a^{2}}}\geq
1.\qed$

###  10.5 Study of $\gamma$

To prove Proposition 4, we first establish a formula for $\mathbb{E}[|x_{1}|]$
in term of $\mathbb{E}[\|x\|]$. Later we will use the Cauchy-Schwartz
inequality

$\mathbb{E}[\|x\|]^{2}\leq\mathbb{E}[\|x\|^{2}],$

which is an equality if and only if $\|x\|$ is constant.

######  Lemma 14.

When $\nu$ is isotropic,

$\mathbb{E}[|x_{1}|]=\frac{\Gamma(\nicefrac{{n}}{{2}})}{\sqrt{\pi}\Gamma(\nicefrac{{n+1}}{{2}})}\mathbb{E}[\|x\|].$

###### Proof of Lemma 14.

The case $n=1$ is trivial, we henceforth consider $n\geq 2$. The key idea is
to notice the formula is “homogeneous,” i.e., both sides are linear in $\nu$,
the distribution of $x$. Then it suffices to prove it for say $\nu$ uniform on
the sphere, then “integrating” the formula to retrieve any $\nu$. This first
step involves some differential geometry, we refer the reader to [45] for a
treatment of differential forms, whereas the second step involves some measure
theory, specifically the disintegration theorem, for which we advise
consulting [44].

Focus then for the moment on $\nu$ uniform on the unit sphere
$\mathbb{S}^{n-1}$, i.e. $\nu$ is defined through the volume form

$\mathrm{d}\nu=\frac{1}{\operatorname{vol}(\mathbb{S}^{n-1})}\mu_{\mathbb{S}^{n-1}},$

where $\mu_{\mathbb{S}^{n-1}}$ is the volume form on $\mathbb{S}^{n-1}$
derived through its embedding in Euclidean $\mathbb{R}^{n}$. This latter can
be expressed as the pull-back

$\mu_{\mathbb{S}^{n-1}}=\iota^{*}\sum_{i=1}^{n}(-1)^{i-1}x_{i}\mathrm{d}x_{1}\wedge\dots\wedge\widehat{\mathrm{d}x_{i}}\wedge\dots\wedge\mathrm{d}x_{n},$

where $\iota\colon\mathbb{S}^{n-1}\xhookrightarrow{}\mathbb{R}^{n}$ is the
canonical inclusion and the hat denotes an omission. We introduce the smooth
change of variable

$\displaystyle\phi\colon(-\nicefrac{{\pi}}{{2}},\nicefrac{{\pi}}{{2}})\times\mathbb{S}^{n-2}$
$\displaystyle\mathrel{\lhook\mkern-3.5mu\relbar\mkern-4.5mu\to}\mathbb{S}^{n-1}$
$\displaystyle(\theta,\varphi)$
$\displaystyle\longmapsto(\sin\theta,\cos\theta\iota(\varphi))$

which only misses two points, and where $\iota$ here denotes the canonical
inclusion $\mathbb{S}^{n-2}\subset\mathbb{R}^{n-1}$. We compute

$\phi^{*}\mu_{\mathbb{S}^{n-1}}=-(\cos\theta)^{n-2}\mathrm{d}\theta\wedge\mu_{\mathbb{S}^{n-2}}.$

It appears that $\phi$ reverses the orientation, therefore

$\displaystyle\operatorname{vol}(\mathbb{S}^{n-1})\mathbb{E}[|x_{1}|]$
$\displaystyle\quad=\int_{\mathbb{S}^{n-1}}|x_{1}|\mu_{\mathbb{S}^{n-1}}$
$\displaystyle\quad=\int_{(-\nicefrac{{\pi}}{{2}},\nicefrac{{\pi}}{{2}})\times\mathbb{S}^{n-2}}|\sin\theta|(\cos\theta)^{n-2}\mathrm{d}\theta\wedge\mu_{\mathbb{S}^{n-2}}$
$\displaystyle\quad=\frac{2\operatorname{vol}(\mathbb{S}^{n-2})}{n-1}$
$\displaystyle\quad=\frac{\operatorname{vol}(\mathbb{S}^{n})}{\pi}.$

Using the well-known formula for the surface of the hypersphere and
homogeneity establishes the announced formula for all $\nu$ uniform
distribution on a sphere.

Consider now $\nu$ isotropic, we may express it

$\mathrm{d}\nu(x)=\mathrm{d}\eta(\|x\|)\mathrm{d}\nu_{\|x\|},$

where $\nu_{\|x\|}$ is the uniform probability distribution on the sphere of
radius $\|x\|$ and $\eta$ is the distribution of $\|x\|$. With this
disintegration,

$\displaystyle\mathbb{E}[|x_{1}|]$
$\displaystyle=\int_{0}^{\infty}\int_{\|x\|\mathbb{S}^{n-1}}|x_{1}|\mathrm{d}\nu_{\|x\|}\mathrm{d}\eta(\|x\|)$
$\displaystyle=\int_{0}^{\infty}\frac{\Gamma(\nicefrac{{n}}{{2}})}{\sqrt{\pi}\Gamma(\nicefrac{{n+1}}{{2}})}\|x\|\mathrm{d}\eta(\|x\|)$
$\displaystyle=\frac{\Gamma(\nicefrac{{n}}{{2}})}{\sqrt{\pi}\Gamma(\nicefrac{{n+1}}{{2}})}\mathbb{E}[\|x\|].\qed$

###### Proof of Proposition 4.

When $x\sim\mathcal{N}(0,I_{n})$, $x_{1}\sim\mathcal{N}(0,1)$ is a scalar
Gaussian random variable, therefore

$\mathbb{E}[|x_{1}|]=\int_{-\infty}^{\infty}|t|\frac{e^{-\nicefrac{{t^{2}}}{{2}}}}{\sqrt{2\pi}}\,\mathrm{d}t=\sqrt{\frac{2}{\pi}},$

and so follows the value of $\gamma$ for Gaussian priors.

For any isotropic prior of covariance $I_{n}$, using Lemma 14, we may express

$\gamma=\frac{2}{1+\sqrt{5+\frac{4\pi\Gamma(\nicefrac{{n+1}}{{2}})^{2}}{\Gamma(\nicefrac{{n}}{{2}})^{2}\mathbb{E}[\|x\|]^{2}}}}.$

By Cauchy-Schwarz inequality,

$\gamma\leq\upsilon_{n}$

with equality if and only if $\|x\|$ is constant, that is if and only if the
prior is spherical.

Finally to analyze the monotonicity and limit of $(\upsilon_{n})$ we define
for $x>0$

$u(x)=2\ln\frac{\Gamma(\nicefrac{{x+1}}{{2}})}{\sqrt{x}\Gamma(\nicefrac{{x}}{{2}})}.$

Its derivative is

$u^{\prime}(x)=\psi(\nicefrac{{x+1}}{{2}})-\psi(\nicefrac{{x}}{{2}})-\frac{1}{x}>0$

where $\psi$ is the digamma function and where the positivity ensues from
Theorem 7 (with $n=0$, $s=\nicefrac{{1}}{{2}}$ and $x$ substituted with
$\nicefrac{{x-1}}{{2}}$) of [46]. In turn,

$\upsilon_{n}=\frac{2}{1+\sqrt{5+4\pi e^{u(n)}}}$

decreases with $n$. We also remark that

$u(x)+u(x+1)=\ln\frac{x}{4(x+1)},$

so $u(x)$ tends to $-\ln 2$ as $x$ goes to infinity, and thus

$\upsilon_{n}\to_{n}\upsilon_{\infty}.\qed$

##  11 Monotonicity of rank

###### Proof of Proposition 5.

In a first step, we evacuate three particular cases. First of all, if $0$ is a
solution then it is the unique solution of minimal rank and it is an
orthogonal projection matrix. We assume henceforth that $0$ is not a solution.

Second, if $E=0$, we face the same program as that of a Bayesian agent, the
minimal solution was shown to be unique and an orthogonal projection matrix
(explicitly $P_{D}^{<0}$). Assume thus that $E\neq 0$.

Third, if $D,E$ are colinear, the objective is a mere strictly concave
function of $\operatorname{Tr}(EX)$, minimized at either end of
$[0,\operatorname{Tr}E]$. Since $0$ is not a solution, it is minimized at
$\operatorname{Tr}E$. Solutions of (14) are then exactly the solutions of

$\max_{0\preceq X\preceq I_{n}}~{}\operatorname{Tr}(EX),$

that is they are $P_{E}^{<0}\preceq X\preceq P_{E}^{\leq 0}=I_{n}$. Therefore
$P_{E}^{<0}$ is the unique solution of minimal rank, and it is an orthogonal
projection matrix. Assume thus henceforth that $D,E$ are not colinear.

In a second step, we characterize solutions of (14). Since the objective
(which we shall note $g$) is concave on the convex domain, the program is
concave. The objective is smooth on the domain deprived of $0$, moreover, its
gradient never vanishes:

$\nabla g(X)=D+\frac{E}{2\sqrt{f+\operatorname{Tr}(EX)}}.$

In this case then, solutions are easily characterized. A result of concave
programming states that $X$ is a solution of (14) if and only if for all $Y,Z$
in the domain (from which we had excluded $0$), $g(Y)=g(X)$ implies that

$\operatorname{Tr}(\nabla g(Y)^{\top}(Z-Y))\geq 0.$

In particular, looking at the values at $Y=X$ tells us that if $X$ is a
solution, it also solves

$\min_{0\preceq Z\preceq I_{n}}~{}\operatorname{Tr}(\nabla g(X)^{\top}Z),$

and so,

$P_{\nabla g(X)}^{<0}\preceq X\preceq P_{\nabla g(X)}^{\leq 0}.$

Let now $X$ be a solution of minimal rank. For all $Z$ such that

$P_{\nabla g(X)}^{<0}\preceq Z\preceq P_{\nabla g(X)}^{\leq 0},$

we have

$\operatorname{Tr}(\nabla g(X)^{\top}(Z-X))=0.$

Hence, for these $Z$, $\operatorname{Tr}(DZ)$ can be rewritten as a simple
function of $\operatorname{Tr}(EZ)$. As $X$ solves (14), it is also a solution
of the same program restricting the constraint set, namely it solves

$\min_{P_{\nabla g(X)}^{<0}\preceq Z\preceq P_{\nabla g(X)}^{\leq
0}}~{}-\frac{\operatorname{Tr}(EZ)}{2\sqrt{f+\operatorname{Tr}(EX)}}+\sqrt{f+\operatorname{Tr}(EZ)}.$

The objective is concave in $\operatorname{Tr}(EZ)$ and $X$ has minimal rank,
therefore,

$X=\begin{cases}P_{\nabla g(X)}^{\leq 0}&\text{if }g(P_{\nabla g(X)}^{\leq
0})<g(P_{\nabla g(X)}^{<0})\\\ P_{\nabla g(X)}^{<0}&\text{if }g(P_{\nabla
g(X)}^{\leq 0})\geq g(P_{\nabla g(X)}^{<0}).\end{cases}$

Following through the first case, we run into a contradiction. All in all,
$X=P_{\nabla g(X)}^{<0}\succ 0$ and, in particular, it is an orthogonal
projection matrix. ∎

###### Proof of Theorem 5.

The result holds immediately if $X_{2}=0$ or if $\epsilon_{1}=\epsilon_{2}$,
we thus assume that $\epsilon_{1}<\epsilon_{2}$ and $X_{2}\neq 0$. Let us
parametrize the hypotheses more succintly:

$E=\epsilon^{2}E_{0},~{}f=\epsilon^{2}f_{0},$

with $\epsilon\geq 0$ varying. For the following, we will call

$R_{a}=P_{D+aE_{0}}^{<0}.$

Since $D+aE_{0}$ increases with $a$, the dimension of its negative eigenspace
decreases with $a$, which is none else than $\operatorname{rk}R_{a}$.

We first show that

$\operatorname{Tr}(DX_{1})\leq\operatorname{Tr}(DX_{2})<0,$

directly implying that $X_{1}\neq 0$. The second inequality is rather obvious:
if $\operatorname{Tr}(DX_{2})\geq 0$, $0$ is a solution of (14) at
$\epsilon=\epsilon_{2}$, but we explicitly ruled this out earlier. Regarding
the first inequality, since $X_{1}$ is a solution with hypothesis
$\epsilon=\epsilon_{1}$, and $X_{2}$ is a solution under the second
hypothesis,

$\displaystyle\operatorname{Tr}(DX_{1})+\epsilon_{1}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{1})}$
$\displaystyle\quad\leq\operatorname{Tr}(DX_{2})+\epsilon_{1}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{2})}$
$\displaystyle\quad=\left(1-\frac{\epsilon_{1}}{\epsilon_{2}}\right)\operatorname{Tr}(DX_{2})$
$\displaystyle\quad\phantom{=}+\frac{\epsilon_{1}}{\epsilon_{2}}\left(\operatorname{Tr}(DX_{2})+\epsilon_{2}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{2})}\right)$
$\displaystyle\quad\leq\left(1-\frac{\epsilon_{1}}{\epsilon_{2}}\right)\operatorname{Tr}(DX_{2})$
$\displaystyle\quad\phantom{=}+\frac{\epsilon_{1}}{\epsilon_{2}}\left(\operatorname{Tr}(DX_{1})+\epsilon_{2}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{1})}\right),$

therefore

$\left(1-\frac{\epsilon_{1}}{\epsilon_{2}}\right)(\operatorname{Tr}(DX_{2})-\operatorname{Tr}(DX_{1}))\geq
0.$

This fact also helps us show that

$\displaystyle\epsilon_{2}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{2})}$ (19)
$\displaystyle\quad=\epsilon_{2}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{2})}+\operatorname{Tr}(DX_{2})-\operatorname{Tr}(DX_{2})$
$\displaystyle\quad\leq\epsilon_{2}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{1})}+\operatorname{Tr}(DX_{1})-\operatorname{Tr}(DX_{2})$
$\displaystyle\quad\leq\epsilon_{2}\sqrt{f_{0}+\operatorname{Tr}(E_{0}X_{1})}.$

If $E_{0}=0$, the programs at both $\epsilon$ are essentially the same, hence
$\operatorname{rk}X_{1}=\operatorname{rk}X_{2}$. We assume thus that
$E_{0}\neq 0$. If $D,E_{0}$ are colinear, then $g(X)$ is a concave function of
$\operatorname{Tr}(E_{0}X)$ for both $\epsilon$. In this case, since $0$ is
not a solution by assumption,
$\operatorname{Tr}(E_{0}X_{1})=\operatorname{Tr}(E_{0}X_{2})=\operatorname{Tr}(E_{0})$,
and by minimality of rank,

$X_{1}=P_{\epsilon_{1}E_{0}}^{<0}=P_{E_{0}}^{<0}=P_{\epsilon_{2}E_{0}}^{<0}=X_{2},$

in particular $\operatorname{rk}X_{1}=\operatorname{rk}X_{2}$. Assume
henceforth that $D,E_{0}$ are not colinear. In this case then ($D,E_{0}$ not
colinear and $X_{1},X_{2}\neq 0$), we have characterized the solutions in the
proof of Proposition 5:

$X_{1}=R_{a_{1}},~{}X_{2}=R_{a_{2}},$

where,

$\displaystyle a_{1}$