reveal it. The elicitor wishes to structure incentives that will encourage
each expert to reveal their signal. The elicitor puts experts on teams (but
does not immediately announce the teams). Then:

  1. 1.

Each expert either reveals their signal to the elicitor, or does not.

  2. 2.

The elicitor announces which experts revealed their signals and announces the
teams.

  3. 3.

Each team makes a prediction about the elicitor’s posterior belief (after
learning the signals of all experts who decided to reveal) and is scored using
a quadratic scoring rule (i.e. penalized by the squared distance between their
prediction of the elicitor’s belief and the elicitor’s actual belief).777Why
not elicit $Y$ directly? Eliciting each team’s best guess about the
_elicitor’s_ belief is particularly compelling in situations in which the true
value of $Y$ will never be known, or will be learned in the far future. Under
these circumstances, the elicitor’s belief serves as an approximation for $Y$
given the available information.

This mechanism incentivizes experts to reveal their signals if and only if the
information structure satisfies projective substitutes. Formally:

######  Proposition 7.2.11.

An information structure satisfies projective substitutes if and only if in
the above mechanism, revealing one’s signal is a dominant strategy for every
expert, regardless of who is on their team.

###### Proof.

First suppose that the information structure satisfies projective substitutes.
Consider any expert $i$, let $B$ be $i$’s team, and let $A$ be the set of all
other experts who reveal their signals. If $i$ does not reveal their signal,
then the elicitor’s belief will be $Y_{A}$ and $B$’s prediction of the
elicitor’s belief will be $Y_{A\to B}$. If $i$ reveals their signal, then the
elicitor’s belief will be $Y_{A\cup\\{i\\}}$ and $B$’s prediction of the
elicitor’s belief will be $Y_{A\cup\\{i\\}\to B}=Y_{A\cup\\{i\\}\to
B\cup\\{i\\}}$. Therefore, by the projective substitutes, condition, $B$’s
expected prediction error is smaller if $i$ reveals their signal to the
expert.

Conversely, suppose that the information structure does not satisfy projective
substitutes. Then there are sets $A,B\subseteq[m]$ and $i\in B$ (see Remark
7.2.12 (ii)) such that

$\mathbb{E}\left[(Y_{A}-Y_{A\to
B})^{2}\right]<\mathbb{E}\left[(Y_{A\cup\\{i\\}}-Y_{A\cup\\{i\\}\to
B\cup\\{i\\}})^{2}\right].$

Consider expert $i$, suppose their team is $B$, and suppose that the set of
experts excluding $i$ who reveal their signal is $A$. Then $i$ is incentivized
not to reveal their signal to the elicitor, as revealing their signal will
increase $B$’s expected prediction error. ∎

######  Remark 7.2.12 (Facts about projective substitutes).

  1. (i)

The weak substitutes condition is equivalent to Equation 7.2 holding for all
$B\subseteq A$, so the projective substitutes condition is stronger. In fact
it is strictly stronger, as it excludes the secret sharing information
structure.

  2. (ii)

There are several equivalent formulations of projective substitutes. One
definition replaces $\\{i\\}$ with an arbitrary set $X$. Another modifies the
definition by only requiring Equation 7.2 to hold if $i\in B$.888To see that
this is equivalent, for any $B,i$ with $i\not\in B$ define
$B^{\prime}:=B\cup\\{i\\}$. Then Equation 7.2 for $A,B^{\prime},i$ has the
same right-hand side but a smaller or equal left-hand side, and is thus more
difficult to satisfy.

  3. (iii)

The notation $Y_{A\to B}$ comes from the fact that $Y_{A\to B}$ is the
orthogonal projection of $Y_{A}$ onto the space of random variables that
depend only on the signals of the experts in $B$. As a consequence of this
alternative formulation, $Y_{A\to B}$ is the closest random variable (by
expected squared distance) to $Y_{A}$ among all random variables that depend
only on the values $(\sigma_{i})_{i\in B}$.

####  7.2.7 PIF information structures

Recall the definition of a PIF information structure from Section 2.3:

See 2.3.4

PIF information structures are natural because each $X_{S}$ can be thought of
as an (additive) piece of evidence about $Y$ that is known by the experts in
$S$. They are also quite versatile, as they capture the idea that different
experts can have overlapping pieces of evidence in a variety of ways. As we
are about to show, all PIF information structures satisfy the projective
substitutes condition. This fact further motivates the notion of projective
substitutes: it means that the class of projective substitutes information
structures is broad enough to include all PIF information structures.

######  Proposition 7.2.13.

Every PIF information structure satisfies projective substitutes.

###### Proof.

Consider a PIF information structure, and without loss of generality, assume
that every $X_{S}$ is zero-mean. Note that given $A,B\subseteq[m]$, we have

$Y_{A}=\sum_{S:S\cap A\neq\emptyset}X_{S}.$

Also,

$Y_{A\to B}=\sum_{S:S\cap A\neq\emptyset,S\cap B\neq\emptyset}X_{S},$

because $X_{S}$ counts toward $Y_{A\to B}$ if both someone in $B$ knows
$X_{S}$ and someone in $A$ knows $X_{S}$. Therefore,

$\mathbb{E}\left[(Y_{A}-Y_{A\to B})^{2}\right]=\sum_{S:S\cap
A\neq\emptyset,S\cap B=\emptyset}\mathbb{E}\left[X_{S}^{2}\right].$

Meanwhile,

$\mathbb{E}\left[(Y_{A\cup\\{i\\}}-Y_{A\cup\\{i\\}\to
B\cup\\{i\\}})^{2}\right]=\sum_{\begin{subarray}{c}S:S\cap(A\cup\\{i\\})\neq\emptyset,\\\
S\cap(B\cup\\{i\\})=\emptyset\end{subarray}}\mathbb{E}\left[X_{S}^{2}\right].$

Note that if $S\cap(B\cup\\{i\\})=\emptyset$, then $S\cap B=\emptyset$ and
also $i\not\in S$. If, furthermore, $S\cap(A\cup\\{i\\})\neq\emptyset$, it
follows that $S\cap A\neq\emptyset$. Thus, any such $S$ also satisfies $S\cap
A\neq\emptyset,S\cap B=\emptyset$. Therefore, we have

$\mathbb{E}\left[(Y_{A}-Y_{A\to
B})^{2}\right]\geq\mathbb{E}\left[(Y_{A\cup\\{i\\}}-Y_{A\cup\\{i\\}\to
B\cup\\{i\\}})^{2}\right],$

so the information structure indeed satisfies projective substitutes. ∎

We will use PIF information structures for two of our negative results.

###  7.3 A strong impossibility result for forecast aggregation

In this section, we exhibit a single PIF information structure on which no
aggregation strategy can achieve an approximation ratio of $\frac{4}{m}$. This
result thus shows that achieving an approximation ratio of $\frac{4}{m}$ is
impossible even by an aggregator who knows the entire information structure.
_(Thanks to Mark Xu of the Alignment Research Center for the discussion that
led to this result.)_

######  Theorem 7.3.1.

Consider the PIF information structure $\mathcal{I}$ defined with
$X_{\\{i\\}}\sim\mathcal{N}(0,1)$, $X_{[m]}\sim\mathcal{N}(0,1)$, and all
other $X_{S}$’s uniformly zero. No aggregation strategy achieves an
approximation ratio of more than $\frac{4m}{(m+1)^{2}}$ on $\mathcal{I}$.

###### Proof.

For convenience, we will write $X_{i}$ in place of $X_{\\{i\\}}$. We have
$Y_{i}=X_{i}+X_{[m]}$ for every $i$.

Let $Z(Y_{1},\dots,Y_{m})$ be the output of some aggregation strategy. Let
$\hat{Y}:=\mathbb{E}\left[Y\mid Y_{1},\dots,Y_{m}\right]$. By the Pythagorean
theorem, we have that
$\mathbb{E}\left[(Y-Z)^{2}\right]=\mathbb{E}\left[(Y-\hat{Y})^{2}\right]+\mathbb{E}\left[(\hat{Y}-Z)^{2}\right]\geq\mathbb{E}\left[(Y-\hat{Y})^{2}\right]$,
with equality if $Z$ is uniformly equal to $\hat{Y}$.

We claim that $\hat{Y}=\frac{2}{m+1}\sum_{i}Y_{i}$. To see this, observe that
for all $j$, $Y_{j}$ is uncorrelated with $Y-\frac{2}{m+1}\sum_{i}Y_{i}$:

$\displaystyle\mathbb{E}\left[Y_{j}\left(Y-\frac{2}{m+1}\sum_{i}Y_{i}\right)\right]$
$\displaystyle=\mathbb{E}\left[(X_{j}+X_{[m]})\left(\frac{m-1}{m+1}\sum_{i}X_{i}-\frac{m-1}{m+1}X_{[m]}\right)\right]$
$\displaystyle=\frac{m-1}{m+1}\left(\mathbb{E}\left[X_{j}^{2}\right]-\mathbb{E}\left[X_{[m]}^{2}\right]\right)=0.$

Because uncorrelated, jointly multinormal vectors are independent [294], we in
fact have that $Y-\frac{2}{m+1}\sum_{i}Y_{i}$ is _independent_ of every
$Y_{j}$. Therefore, the expected value of $Y-\frac{2}{m+1}\sum_{i}Y_{i}$
conditioned on $Y_{1},\dots,Y_{m}$ is uniformly zero, and so
$\hat{Y}=\frac{2}{m+1}\sum_{i}Y_{i}$.

Thus, let $Z=\frac{2}{m+1}\sum_{i}Y_{i}$. This is the optimal $Z$, and the
approximation ratio achieved by $Z$ is

$1-\frac{\mathbb{E}\left[(Y-Z)^{2}\right]}{\mathbb{E}\left[Y^{2}\right]}=1-\frac{\left(\frac{m-1}{m+1}\right)^{2}(m+1)}{m+1}=\frac{4m}{(m+1)^{2}},$

as desired. ∎

###  7.4 The prior-free setting

Now that we have established that no aggregator can hope to achieve an
approximation ratio of $\frac{4}{m}$, even under the projective substitutes
condition and even if the aggregator knows the information structure, we ask:
how close to $\frac{4}{m}$ can we get? We begin our investigation with the
prior-free setting: that is, we will assume that the aggregator knows
_nothing_ about the information structure, except that it satisfies the
projective substitutes condition. In this setting, what is the largest
approximation ratio that the aggregator can guarantee?

In this section we give a positive result and a negative result. The positive
result is that averaging the experts’ reports attains an approximation ratio
of at least $(1+\sqrt{3}/2)/m-O(1/m^{2})\approx 1.866/m$. The negative result
is that for all $m$, no aggregation strategy attains an approximation ratio of
more than $2/m-1/m^{2}$. Thus, projective substitutes enables a significant
improvement over the $1/m$-approximation guarantee of the random expert
strategy, but no more than by a factor of two.

####  7.4.1 Positive result for the prior-free setting

######  Theorem 7.4.1.

Let $\mathcal{I}=(\Omega,\mathbb{P},S,Y)$ be an information structure for $m$
experts that satisfies projective substitutes, and let
$Z=\frac{1}{m}\sum_{i=1}^{m}Y_{i}$. Then $Z$ attains an approximation ratio of
at least

$\frac{2}{m}-\frac{m-1}{2m(2m-1+\sqrt{3m^{2}-3m+1})}-\frac{1}{m^{2}}\geq\left(1+\frac{\sqrt{3}}{2}\right)\cdot\frac{1}{m}-O\left(\frac{1}{m^{2}}\right).$

In other words, knowing nothing about an information structure other than the
fact that it satisfies the projective substitutes condition, one can
significantly improve upon the $1/m$-approximation guarantee of choosing a
random expert.

To prove this result, we use the projective substitutes condition to show that
one of two things must be true: either (a) the experts’ forecasts are (in
expectation) fairly different from each other, or (b) the forecasts are
somewhat accurate, meaning that they improve substantially upon the prior.
(This is a reinterpretation of Lemma 7.4.2 below.) In case (a), averaging the
experts’ forecasts guarantees substantial improvement upon a random forecast;
in case (b), even though averaging the forecasts does not improve
substantially upon a random forecast, a random forecast already substantially
outperforms the prior. (Our proof does not rely on casework, instead showing
that these two cases quantitatively trade off against each other.)

###### Proof.

Let $Z=\frac{1}{m}\sum_{i=1}^{m}Y_{i}$. By Claim 7.2.5, showing that $Z$
achieves an approximation ratio of $\alpha$ is equivalent to showing that

$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]\leq(1-\alpha)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right].$
(7.3)

The first step in our proof uses the following fact: for any numbers
$y_{1},\dots,y_{m}$ and $y$, we have

$\left(y-\frac{y_{1}+\dots+y_{m}}{m}\right)^{2}=\frac{1}{m}\sum_{i=1}^{m}(y-y_{i})^{2}-\frac{1}{m^{2}}\sum_{1\leq
i<j\leq m}(y_{i}-y_{j})^{2}.$

This equality follows from rearranging terms, and applying it in expectation
for $y=Y_{[m]}$ and $y_{i}=Y_{i}$ gives us the following equality.

$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]=\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]-\frac{1}{m^{2}}\sum_{1\leq
i<j\leq m}\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right].$ (7.4)

The left-hand side here is the same as in Equation 7.3; meanwhile, the right-
hand side has a term representing the average error of a random expert and
another term representing the average expected distance between the experts’
forecasts. The following lemma allows us to get a handle on this last term.

######  Lemma 7.4.2.

For all $i,j$, and for all $a,b\geq 0$ such that $b\geq\frac{(2a-1)^{2}}{4a}$,
we have

$\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right]\geq
a\left(\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]+\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{j})^{2}\right]\right)-b\left(\mathbb{E}\left[(Y_{i}-\mathbb{E}\left[Y\right])^{2}\right]+\mathbb{E}\left[(Y_{j}-\mathbb{E}\left[Y\right])^{2}\right]\right).$
(7.5)

The proof of Lemma 7.4.2 relies on the projective substitutes assumption. The
lemma lets us flexibly lower bound the expected distance between $Y_{i}$ and
$Y_{j}$ in terms of the average expected distance from $Y_{\\{i,j\\}}$ to
$Y_{i}$ and $Y_{j}$. Intuitively, the projective substitutes condition
guarantees such a bound because expert $i$ must be able to forecast
$Y_{\\{i,j\\}}$ better than they can forecast $Y_{j}$. For now we assume the
truth of Lemma 7.4.2 and return to the proof of Theorem 7.4.1. We note that we
may rewrite

$\mathbb{E}\left[(Y_{i}-\mathbb{E}\left[Y\right])^{2}\right]=\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right],$
(7.6)

by the Pythagorean theorem. Additionally, we note that by weak substitutes
(which follows from projective substitutes), for all $i$ we have

$\sum_{j\neq
i}\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]\geq\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right].$
(7.7)

To see this, consider for example $i=1$. By weak substitutes,
$\mathbb{E}\left[(Y_{\\{1,j\\}}-Y_{1})^{2}\right]\geq\mathbb{E}\left[(Y_{[j]}-Y_{[j-1]})^{2}\right]$,
so the left-hand side of Equation 7.7 is greater than or equal to
$\sum_{j>1}\mathbb{E}\left[(Y_{[j]}-Y_{[j-1]})^{2}\right]$, which (by $m-2$
applications of the Pythagorean theorem) is equal to
$\mathbb{E}\left[(Y_{[m]}-Y_{1})^{2}\right]$. Now, combining Equations 7.4,
7.5, 7.6, and 7.7 gives us that

$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]\leq\frac{b(m-1)}{m}\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]+\left(\frac{1}{m}-\frac{a}{m^{2}}-\frac{b(m-1)}{m^{2}}\right)\sum_{i=1}^{m}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right].$
(7.8)

for any $a,b$ satisfying Lemma 7.4.2. Now, note that by weak substitutes we
have

$\sum_{i=1}^{m}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]=m\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\sum_{i=1}^{m}\mathbb{E}\left[(Y_{i}-\mathbb{E}\left[Y\right])^{2}\right]\leq(m-1)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right],$
(7.9)

where the first step uses the Pythagorean theorem and the second step follows
from Proposition 7.2.3. Therefore, if
$\frac{1}{m}-\frac{a}{m^{2}}-\frac{b(m-1)}{m^{2}}\geq 0$, we may write
Equation 7.8 as

$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]\leq\frac{m-1}{m}\left(1-\frac{a-b}{m}\right)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right].$

To make this inequality as tight as possible, we wish to make $a-b$ as large
as possible; our constraints are that $b\geq\frac{(2a-1)^{2}}{4a}$ and
$\frac{1}{m}-\frac{a}{m^{2}}-\frac{b(m-1)}{m^{2}}\geq 0$. The optimal values
are

$a=\frac{2m-1+\sqrt{3m^{2}-3m+1}}{2m}\text{ and }b=\frac{(2a-1)^{2}}{4a}.$

This gives us

$\alpha=1-\frac{m-1}{m}\left(1-\frac{a-b}{m}\right)=\frac{2}{m}-\frac{m-1}{2m(2m-1+\sqrt{3m^{2}-3m+1})}-\frac{1}{m^{2}},$

as desired. ∎

###### Proof of Lemma 7.4.2.

Thinking of random variables as vectors (as in Section 7.2.2), let $T_{i}$ be
the projection of $Y_{j}$ onto the space of all affine combinations of $Y_{i}$
and $Y_{\emptyset}$, i.e. $\\{\beta
Y_{i}+(1-\beta)Y_{\emptyset}:\beta\in\mathbb{R}\\}$. (Recall that
$Y_{\emptyset}$ is the random variable that is always equal to
$\mathbb{E}\left[Y\right]$.) Define $T_{j}$ analogously. Note that
$\mathbb{E}\left[(Y_{j}-Y_{j\to
i})^{2}\right]\leq\mathbb{E}\left[(Y_{j}-T_{j})^{2}\right]$, since $Y_{j\to
i}$ is the closest point to $Y_{j}$ of the subspace of random variables that
depend only on $\sigma_{i}$, and the aforementioned affine space is a subset
of that subspace. Additionally, by projective substitutes (with
$A=\\{i\\},B=\\{j\\},i=i$ in Definition 7.2.9), we have that
$\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]\leq\mathbb{E}\left[(Y_{j}-Y_{j\to
i})^{2}\right]$. Therefore, we have that
$\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]\leq\mathbb{E}\left[(Y_{j}-T_{j})^{2}\right]$,
and similarly that
$\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{j})^{2}\right]\leq\mathbb{E}\left[(Y_{i}-T_{i})^{2}\right]$.
It therefore suffices to show that

$\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right]\geq
a\left(\mathbb{E}\left[(Y_{i}-T_{i})^{2}\right]+\mathbb{E}\left[(Y_{j}-T_{j})^{2}\right]\right)-b\left(\mathbb{E}\left[(Y_{i}-Y_{\emptyset})^{2}\right]+\mathbb{E}\left[(Y_{j}-Y_{\emptyset})^{2}\right]\right).$
(7.10)

By the Pythagorean theorem,999While in most cases by “Pythagorean theorem” we
mean Proposition 2.3.11, in this case we are referring to the fact that for
orthogonal vectors $\mathbf{x}$ and $\mathbf{y}$, we have
$\left\lVert\mathbf{x}\right\rVert^{2}+\left\lVert\mathbf{y}\right\rVert^{2}=\left\lVert\mathbf{x}+\mathbf{y}\right\rVert^{2}$
(and applying this fact to e.g. $\mathbf{x}=Y_{i}-T_{i}$,
$\mathbf{y}=Y_{j}-T_{i}$). we know the following four facts.

$\displaystyle\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right]$
$\displaystyle=\mathbb{E}\left[(Y_{i}-T_{i})^{2}\right]+\mathbb{E}\left[(Y_{j}-T_{i})^{2}\right];$
$\displaystyle\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right]$
$\displaystyle=\mathbb{E}\left[(Y_{j}-T_{j})^{2}\right]+\mathbb{E}\left[(Y_{i}-T_{j})^{2}\right]$
$\displaystyle\mathbb{E}\left[(Y_{i}-Y_{\emptyset})^{2}\right]$
$\displaystyle=\mathbb{E}\left[(Y_{i}-T_{i})^{2}\right]+\mathbb{E}\left[(T_{i}-Y_{\emptyset})^{2}\right];$
$\displaystyle\mathbb{E}\left[(Y_{j}-Y_{\emptyset})^{2}\right]$
$\displaystyle=\mathbb{E}\left[(Y_{j}-T_{j})^{2}\right]+\mathbb{E}\left[(T_{j}-Y_{\emptyset})^{2}\right]$

These let us rewrite Equation 7.10 as such:

$\displaystyle\frac{1}{2}\left(\mathbb{E}\left[(Y_{j}-T_{i})^{2}\right]+\mathbb{E}\left[(Y_{i}-T_{j})^{2}\right]\right)+\left(a-\frac{1}{2}\right)\left(\mathbb{E}\left[(T_{i}-Y_{\emptyset})^{2}\right]+\mathbb{E}\left[(T_{j}-Y_{\emptyset})^{2}\right]\right)$
$\displaystyle\geq\left(a-b-\frac{1}{2}\right)\left(\mathbb{E}\left[(Y_{i}-Y_{\emptyset})^{2}\right]+\mathbb{E}\left[(Y_{j}-Y_{\emptyset})^{2}\right]\right).$
(7.11)

We wish to show that this inequality holds so long as
$b\geq\frac{(2a-1)^{2}}{4a}$. To do so, we note the following fact: for any
random variables $Q,R$ and non-negative reals $c_{1},c_{2}$, we have that

$c_{1}\mathbb{E}\left[Q^{2}\right]+c_{2}\mathbb{E}\left[R^{2}\right]\geq\frac{c_{1}c_{2}}{c_{1}+c_{2}}\mathbb{E}\left[(Q+R)^{2}\right].$

This follows (after multiplying through by $c_{1}+c_{2}$ and cancelling terms)
from the fact that for all $q,r$ we have $(c_{1}q)^{2}+(c_{2}r)^{2}\geq
2(c_{1}q)(c_{2}r)$. Now, we apply this identity to $Q:=Y_{j}-T_{i}$ and
$R:=T_{i}-Y_{\emptyset}$, with $c_{1}=\frac{1}{2}$ and $c_{2}=a-\frac{1}{2}$,
and also to $Q:=Y_{i}-T_{j}$ and $R:=T_{j}-Y_{\emptyset}$. This tells us that

$\displaystyle\frac{1}{2}\left(\mathbb{E}\left[(Y_{j}-T_{i})^{2}\right]+\mathbb{E}\left[(Y_{i}-T_{j})^{2}\right]\right)+\left(a-\frac{1}{2}\right)\left(\mathbb{E}\left[(T_{i}-Y_{\emptyset})^{2}\right]+\mathbb{E}\left[(T_{j}-Y_{\emptyset})^{2}\right]\right)$
$\displaystyle\geq\frac{2a-1}{4a}\left(\mathbb{E}\left[(Y_{i}-Y_{\emptyset})^{2}\right]+\mathbb{E}\left[(Y_{j}-Y_{\emptyset})^{2}\right]\right).$

Therefore, Equation 7.4.1 holds so long as $\frac{2a-1}{4a}\geq
a-b-\frac{1}{2}$, which is equivalent to $b\geq\frac{(2a-1)^{2}}{4a}$. ∎

####  7.4.2 Negative results for the prior-free setting

######  Theorem 7.4.3.

Fix any $m\geq 1$. For $\mu\in\mathbb{R}$, let $\mathcal{I}_{\mu}$ be the PIF
information structure defined with $X_{\\{i\\}}\sim\mathcal{N}(0,1)$,
$X_{[m]}=m\mu$ deterministically, and all other $X_{S}$’s uniformly zero. No
aggregation strategy achieves an approximation ratio of more than
$\frac{2}{m}-\frac{1}{m^{2}}$ on every $\mathcal{I}_{\mu}$.

Note that by Proposition 7.2.13, $\mathcal{I}_{\mu}$ satisfies the projective
substitutes condition, and so Theorem 7.4.3 serves as a negative result for
the prior-free setting. The result would still apply if we replaced the
projective substitutes assumption with any assumption that permits the class
of all PIF information structures (or indeed, any assumption that permits the
set of all information structures $\mathcal{I}_{\mu}$).

###### Proof.

For simplicity, we write $X_{i}$ in place of $X_{\\{i\\}}$. We prove the
theorem in two steps. First, we show that taking the average of the experts’
reports yields an approximation ratio of exactly $\frac{2}{m}-\frac{1}{m^{2}}$
for all $\mu$. Second, we show that no aggregation strategy beats taking the
average for every $\mu$.

For the first step, assume without loss of generality that $\mu=0$. Then
$Y_{[m]}=\sum_{i}X_{i}$, and the average of the $Y_{i}$’s (which we will
denote $Z$) is equal to $\frac{1}{m}\sum_{i}X_{i}$. Therefore we have

$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]=\mathbb{E}\left[\left(\frac{m-1}{m}\sum_{i}X_{i}\right)^{2}\right]=\left(\frac{m-1}{m}\right)^{2}\mathbb{E}\left[\left(\sum_{i}X_{i}\right)^{2}\right].$

On the other hand, we have that
$\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]=\mathbb{E}\left[(\sum_{i}X_{i})^{2}\right]$,
so (using Claim 7.2.5) we have that the approximation ratio is

$1-\left(\frac{m-1}{m}\right)^{2}=\frac{2}{m}-\frac{1}{m^{2}}.$

This completes the first step. To complete the second step, we use the
following well-known result from statistical theory.101010This fact does not
generalize to more than two dimensions, meaning that if the $x_{i}$ are
vectors in three or more dimensions drawn independently from a normal
distribution with unknown mean and known covariance matrix, then there is an
estimator for the mean that Pareto dominates the sample mean according to
expected squared vector distance. One such estimator is the _James-Stein
estimator_ [342].

######  Proposition 7.4.4 ([207, 254, 272]).

Let $x_{1},\dots,x_{m}$ be drawn independently from a normal distribution with
unknown mean $\mu$ and standard deviation $1$. Let
$\hat{\mu}:=\frac{1}{m}\sum_{i=1}^{m}x_{i}$. Then for every function $Z$ of
$x_{1},\dots,x_{m}$, there exists $\mu$ such that
$\mathbb{E}\left[(Z-\mu)^{2}\right]\geq\mathbb{E}\left[(\hat{\mu}-\mu)^{2}\right]$.

Since $\mathbb{E}\left[(\hat{\mu}-\mu)^{2}\right]=\frac{1}{m}$ for every
$\mu$, we have the following fact as a corollary.

######  Corollary 7.4.5.

Let $x_{1},\dots,x_{m}$ be drawn independently from a normal distribution with
unknown mean $\mu$ and standard deviation $1$. Then for every aggregation
strategy $Z$ that takes as input $x_{1},\dots,x_{m}$, we have
$\max_{\mu}\mathbb{E}\left[(Z-\mu)^{2}\right]\geq\frac{1}{m}$.

(The only subtlety is that aggregation strategies are not required to be
deterministic; however, replacing a randomized aggregation strategy with the
deterministic strategy that outputs the expected value of the randomized
strategy given the inputs can only reduce expected squared error.)

Returning to our proof, observe that each $Y_{i}$ is equal to $m\mu+X_{i}$,
which is an independent draw from the normally distribution with mean $m\mu$
and standard deviation $1$. Let $Z$ be any aggregation strategy on inputs
$Y_{1},\dots,Y_{m}$. We define a new aggregation strategy:
$\tilde{Z}:=\frac{1}{m-1}(\sum_{i}Y_{i}-Z)$. We claim that if $Z$ achieves an
approximation ratio of more than $\frac{2}{m}-\frac{1}{m^{2}}$ for every
$\mu$, then $\tilde{Z}$ violates Corollary 7.4.5. Consider $\tilde{Z}$ as an
estimator for $m\mu$. We have

$\displaystyle\mathbb{E}\left[(m\mu-\tilde{Z})^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(m\mu-\frac{1}{m-1}\left(\sum_{i}Y_{i}-Z\right)\right)^{2}\right]$
$\displaystyle=\frac{1}{(m-1)^{2}}\mathbb{E}\left[\left(\sum_{i}Y_{i}-m(m-1)\mu-Z\right)^{2}\right]=\frac{1}{(m-1)^{2}}\mathbb{E}\left[(Y-Z)^{2}\right],$

where in the last step we use the fact that
$Y=m\mu+\sum_{i}X_{i}=\sum_{i}Y_{i}-m(m-1)\mu$. Now, suppose for contradiction
that $Z$ achieves an approximation ratio of more than
$\frac{2}{m}-\frac{1}{m^{2}}$ on every $\mu$. Then for all $\mu$ we have

$\left(\frac{m-1}{m}\right)^{2}=1-\left(\frac{2}{m}-\frac{1}{m^{2}}\right)>\frac{\mathbb{E}\left[(Y-Z)^{2}\right]}{\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]}=\frac{\mathbb{E}\left[(Y-Z)^{2}\right]}{m}=\frac{(m-1)^{2}}{m}\mathbb{E}\left[(m\mu-\tilde{Z})^{2}\right],$

so $\mathbb{E}\left[(m\mu-\tilde{Z})^{2}\right]<\frac{1}{m}$ for every value
of $m\mu$ (and thus for every $\mu$). This contradicts Corollary 7.4.5 and
completes the proof. ∎

Theorems 7.4.1 and 7.4.3 give us non-matching lower and upper bounds on the
optimal approximation ratio under the projective substitutes condition. In
particular, for $m=2$ experts, Theorem 7.4.1 tells us that averaging achieves
an approximation ratio of $\frac{3+\sqrt{7}}{8}\approx 0.706$, while Theorem
7.4.1 tells us that no aggregation strategy can achieve an approximation ratio
larger than $0.75$. We now show that for two experts, our positive result is
tight.

######  Theorem 7.4.6.

In the prior-free setting, no aggregation strategy achieves an approximation
ratio larger than $\frac{3+\sqrt{7}}{8}$ on every two-expert information
structure that satisfies projective substitutes.

###### Proof.

Let $\mathcal{I}_{+}$ be the following information structure, where
$p=1-\frac{\sqrt{7}}{4}$ and $x=\sqrt{14}-2\sqrt{2}$. We label the signals
$-1$ and $1$ because these are the expected values conditional on the
respective signals.

$\mathcal{I}_{+}:=\left\\{Y=\begin{tabular}[]{c|cc}&$\sigma_{2}=1$&$\sigma_{2}=-1$\\\
\hline\cr$\sigma_{1}=1$&$\frac{1-(1-2p)x}{2p}$&$x$\\\
$\sigma_{1}=-1$&$x$&$\frac{-1-(1-2p)x}{2p}$\end{tabular}\qquad\mathbb{P}=\begin{tabular}[]{c|cc}&$\sigma_{2}=1$&$\sigma_{2}=-1$\\\
\hline\cr$\sigma_{1}=1$&$p$&$\frac{1}{2}-p$\\\
$\sigma_{1}=-1$&$\frac{1}{2}-p$&$p$\end{tabular}\right\\}$

Let $\mathcal{I}_{-}$ be the same information structure, but with
$x=2\sqrt{2}-\sqrt{14}$. It is a matter of calculation to verify that these
information structures satisfy projective substitutes.111111These information
structures were found by finding values that would make the inequalities in
the proofs of Theorem 7.4.1 and Lemma 7.4.2 hold with equality.

Note that any aggregation strategy that outputs a number other than $1$ on
input $(Y_{1},Y_{2})=(1,1)$ has an approximation ratio of negative infinity on
an information structure where $Y=1$ deterministically. This is likewise true
for $-1$ in place of $1$. Thus, if Theorem 7.4.6 were false, it would be
disproved by an information structure that outputs $1$ on $\mathcal{I}_{+}$
and $\mathcal{I}_{-}$ if $(\sigma_{1},\sigma_{2})=(1,1)$ and $-1$ if
$(\sigma_{1},\sigma_{2})=(-1,-1)$. Conditional on this, the aggregation
strategy that minimizes the maximum expected squared distance to $Y_{[m]}$ on
$\mathcal{I}_{+}$ and $\mathcal{I}_{-}$ is the one that returns $0$ when
$(\sigma_{1},\sigma_{2})=(1,-1)$ or $(\sigma_{1},\sigma_{2})=(-1,1)$. It is a
matter of calculation to verify that this aggregation strategy achieves an
approximation ratio of exactly $\frac{3+\sqrt{7}}{8}$. ∎

###  7.5 The known prior setting

Let us now expand the information available to the aggregator by allowing them
knowledge of the prior $\mathbb{E}\left[Y\right]$. How might this change the
optimal aggregation strategy?

In Section 2.2, we saw that it often makes sense to extremize an aggregate
forecast – that is, to push it away from the prior. We gave the following
information structure as a motivating example: a coin comes up heads $Y$
fraction of the time, where $Y$ is selected uniformly from $[0,1]$; each of
two experts sees an independent flip of the coin. It can be calculated that an
expert who sees heads has a posterior of $\frac{2}{3}$. However, consider the
situation in which both experts report heads: collectively they have seen two
heads and zero tails, conditional on which the expected value of $Y$ is
$\frac{3}{4}$, rather than $\frac{2}{3}$.

More generally, extremization is useful when experts have private information.
For example, if many experts update upward from the prior as a result of each
of their pieces of evidence, then it stands to reason that observing _all of
the evidence_ would cause an update that is larger than the average of the
experts’ individual updates.

####  7.5.1 The extremization factor

Consider the following aggregation strategy, parameterized by a constant $d$
which we will call the _extremization factor_.

$Z:=\frac{1}{m}\sum_{i}Y_{i}+(d-1)\left(\frac{1}{m}\sum_{i}Y_{i}-\mathbb{E}\left[Y\right]\right).$
(7.12)

Setting $d=1$ recovers the average of the reports; setting $d=0$ simply
returns the prior. In general, setting $d>1$ extremizes the average (i.e.
pushes it away from the prior) by a factor of $d$. As an example, consider the
class of information structures in Theorem 7.4.3, where averaging achieved an
approximation ratio of $\frac{2}{m}-\frac{1}{m^{2}}$. On the other hand,
extremizing by a factor of $m$ (i.e. setting $d=m$ above) recovers $Y$ exactly
(thus achieving an approximation ratio of $1$). This approach, which is a
special case of generalized linear pooling (introduced in Section 2.2.3), is
known as _linear extremization_ [334].

We now prove that by extremizing, we can achieve an approximation ratio that
is higher than what we could hope to attain without knowledge of the prior. In
particular, we find that by applying an appropriate amount of linear
extremization, it is possible to achieve an approximation ratio of at least
$\frac{3\sqrt{3}}{2m}-O(1/m^{2})\approx 2.598/m$. This is a substantial
improvement not only over our positive result in the prior-free setting, but
also over our negative result in that setting.

####  7.5.2 Positive result for the known prior setting

######  Theorem 7.5.1.

Let $\mathcal{I}=(\Omega,\mathbb{P},S,Y)$ be an information structure for $m$
experts that satisfies projective substitutes, and let
$Z=\frac{1}{m}\sum_{i=1}^{m}Y_{i}+(d-1)\left(\frac{1}{m}\sum_{i=1}^{n}Y_{i}-\mathbb{E}\left[Y\right]\right)$,
where $d=\frac{m(\sqrt{3m^{2}-3m+1}-2)}{m^{2}-m-1}$. Then $Z$ attains an
approximation ratio of at least

$\frac{(3m^{2}-3m+1)^{3/2}-9m^{2}+9m+1}{2(m^{2}-m-1)^{2}}\geq\frac{3\sqrt{3}}{2m}-O\left(\frac{1}{m^{2}}\right).$

In Figure 7.3, we plot the values of $d$ suggested by Theorem 7.5.1. While $d$
increases with $m$, it reaches a limit – namely, $\sqrt{3}\approx 1.732$. By
contrast, the optimal response to the information structures in our negative
result for the prior-free setting (Theorem 7.4.3) was to extremize by a factor
of $m$ (i.e. to add up the experts’ updates from the prior). This is a
consequence of the fact that the signals received by each expert were
independent. By contrast, Theorem 7.5.1 suggests a smaller amount of
extremization, because it is concerned with the optimal strategy in the worst
case over information structures. This means that it must compromise between
doing well in settings with independent signals (where a large extremization
factor makes sense) and settings in which experts’ signals are highly
dependent (where little or no extremization is optimal). The extremization
factor suggested by Theorem 7.5.1 is also consistent with the Bayesian
modeling results in [330] and the empirical findings in [334].

Figure 7.3: For $m=2\dots 20$, the value
$d=\frac{m(\sqrt{3m^{2}-3m+1}-2)}{m^{2}-m-1}$ suggested by Theorem 7.5.1,
together with the asymptotic (with $m$) value $\sqrt{3}$.

The proof of Theorem 7.5.1 is similar to the proof of Theorem 7.4.1, though
with an additional degree of freedom ($d$) to optimize over.

###### Proof of Theorem 7.5.1.

Let $d>0$ and let
$Z:=\frac{1}{m}\sum_{i}Y_{i}+(d-1)\left(\frac{1}{m}\sum_{i}Y_{i}-\mathbb{E}\left[Y\right]\right)$.
As with the proof of Theorem 7.4.1, we start by upper bounding
$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]$. We have

$\displaystyle\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]$
$\displaystyle=\mathbb{E}\left[\left(d\left(Y_{[m]}-\frac{1}{m}\sum_{i}Y_{i}\right)-(d-1)\left(Y_{[m]}-\mathbb{E}\left[Y\right]\right)\right)^{2}\right]$
$\displaystyle=d^{2}\mathbb{E}\left[\left(Y_{[m]}-\frac{1}{m}\sum_{i}Y_{i}\right)^{2}\right]+(d-1)^{2}\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]$
$\displaystyle\qquad-\frac{2d(d-1)}{m}\mathbb{E}\left[\left(mY_{[m]}-\sum_{i}Y_{i}\right)\left(Y_{[m]}-\mathbb{E}\left[Y\right]\right)\right]$
$\displaystyle=d^{2}\left(\frac{1}{m}\sum_{i}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]-\frac{1}{m^{2}}\sum_{1\leq
i<j\leq m}\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right]\right)$
$\displaystyle\qquad+(d-1)^{2}\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\frac{2d(d-1)}{m}\sum_{i}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right].$

In the last step, we adapt the first term using Equation 7.4 and adapt the
last term by observing that

$\displaystyle\mathbb{E}\left[(Y_{[m]}-Y_{i})(Y_{[m]}-\mathbb{E}\left[Y\right])\right]$
$\displaystyle=\mathbb{E}\left[Y_{[m]}(Y_{[m]}-Y_{i})\right]-\mathbb{E}\left[Y\right]\mathbb{E}\left[Y_{[m]}-Y_{i}\right]$
$\displaystyle=\mathbb{E}\left[Y_{[m]}(Y_{[m]}-Y_{i})\right]=\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]$

(where the last step holds because for any given $Y_{i}$,
$\mathbb{E}\left[Y_{[m]}\mid Y_{i}\right]=Y_{i}$, so
$\mathbb{E}\left[Y_{i}(Y_{[m]}-Y_{i})\right]=0$). Grouping like terms, we have

$\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]=(d-1)^{2}\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\frac{d(d-2)}{m}\sum_{i}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]-\frac{d^{2}}{m^{2}}\sum_{1\leq
i<j\leq m}\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right].$

Now, recall Lemma 7.4.2. Consider any $a,b\geq 0$ satisfying
$b\geq\frac{(2a-1)^{2}}{4a}$; then for all $i,j$ we have

$\mathbb{E}\left[(Y_{i}-Y_{j})^{2}\right]\geq
a\left(\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]+\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{j})^{2}\right]\right)-b\left(\mathbb{E}\left[(Y_{i}-\mathbb{E}\left[Y\right])^{2}\right]+\mathbb{E}\left[(Y_{j}-\mathbb{E}\left[Y\right])^{2}\right]\right).$

Therefore we have

$\displaystyle\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]\leq(d-1)^{2}\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\frac{d(d-2)}{m}\sum_{i}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]$
$\displaystyle\qquad-\frac{d^{2}}{m^{2}}\sum_{1\leq i<j\leq
m}\left(a\left(\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]+\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{j})^{2}\right]\right)-b\left(\mathbb{E}\left[(Y_{i}-\mathbb{E}\left[Y\right])^{2}\right]+\mathbb{E}\left[(Y_{j}-\mathbb{E}\left[Y\right])^{2}\right]\right)\right)$
$\displaystyle=\left((d-1)^{2}+\frac{bd^{2}(m-1)}{m}\right)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]-\left(\frac{d(d-2)}{m}+\frac{bd^{2}(m-1)}{m^{2}}\right)\sum_{i}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right]$
$\displaystyle\qquad-\frac{ad^{2}}{m^{2}}\sum_{1\leq i<j\leq
m}\left(\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{i})^{2}\right]+\mathbb{E}\left[(Y_{\\{i,j\\}}-Y_{j})^{2}\right]\right),$

where in the last step we use the Pythagorean theorem to write
$\mathbb{E}\left[(Y_{i}-\mathbb{E}\left[Y\right])^{2}\right]$ as
$\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]-\mathbb{E}\left[(Y-Y_{i})^{2}\right]$.
Now we use Equation 7.7:

$\displaystyle\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]$
$\displaystyle\leq\left((d-1)^{2}+\frac{bd^{2}(m-1)}{m}\right)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]$
$\displaystyle\qquad-\left(\frac{d(d-2)}{m}+\frac{bd^{2}(m-1)}{m^{2}}+\frac{ad^{2}}{m^{2}}\right)\sum_{i}\mathbb{E}\left[(Y_{[m]}-Y_{i})^{2}\right].$

Now, supposing that
$\frac{d(d-2)}{m}+\frac{bd^{2}(m-1)}{m^{2}}+\frac{ad^{2}}{m^{2}}$ is not
positive, we may use Equation 7.9 to obtain:

$\displaystyle\mathbb{E}\left[(Y_{[m]}-Z)^{2}\right]$
$\displaystyle\leq\left((d-1)^{2}+\frac{bd^{2}(m-1)}{m}-\frac{m-1}{m}\left(d(d-2)+\frac{bd^{2}(m-1)}{m}+\frac{ad^{2}}{m}\right)\right)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right]$
$\displaystyle=\left(1+\frac{d^{2}-2d}{m}-(a-b)\frac{m-1}{m^{2}}d^{2}\right)\mathbb{E}\left[(Y_{[m]}-\mathbb{E}\left[Y\right])^{2}\right].$

With $d$ held fixed, our goal is to maximize $a-b$, just as in the proof of
Theorem 7.4.1. This time, our constraints are $b\geq\frac{(2a-1)^{2}}{4a}$ (as
before) and
$\frac{d(d-2)}{m}+\frac{bd^{2}(m-1)}{m^{2}}+\frac{ad^{2}}{m^{2}}\leq 0$, which
can be rewritten as $a+b(m-1)\leq\frac{2-d}{d}m$. The optimal values are

$a=\frac{\frac{2}{d}m-1+\sqrt{\left(\frac{2}{d}m-1\right)^{2}-m(m-1)}}{2m}\text{
and }b=\frac{(2a-1)^{2}}{4a}.$

Now, let $a$ and $b$ be as above. We may select $d$ as we please and seek to
minimize the expression

$1+\frac{d^{2}-2d}{m}-(a-b)\frac{m-1}{m^{2}}d^{2}.$

We choose the value of $d$ in the theorem statement (which one can verify is
optimal using a computer algebra system). This yields the desired
approximation ratio. ∎

####  7.5.3 Negative result for the known prior setting for $m=2$

We already have a negative result for the known prior setting: namely, Theorem
7.3.1. In the special case of $m=2$, Theorem 7.3.1 shows that an approximation
ratio larger than $\frac{8}{9}\approx 0.889$ cannot be achieved. By contrast,
Theorem 7.5.1 tells us that averaging and extremizing by a factor of
$2(\sqrt{7}-2)\approx 1.292$ achieves an approximation ratio of
$\frac{7\sqrt{7}-17}{2}\approx 0.760$. We prove that this positive result is
in fact tight.

######  Theorem 7.5.2.

In the known prior setting, no aggregation strategy achieves an approximation
ratio larger than $\frac{7\sqrt{7}-17}{2}$ on every two-expert information
structure that satisfies projective substitutes.

###### Proof.

Let $\mathcal{I}_{+}$ be the following information structure, where
$p=\frac{2+\sqrt{7}}{12}$ and $x=\frac{\sqrt{2+\sqrt{7}}}{3}$. We label the
signals $-1$ and $1$ because these are the expected values conditional on the
respective signals.

$\mathcal{I}_{+}:=\left\\{Y=\begin{tabular}[]{c|cc}&$\sigma_{2}=1$&$\sigma_{2}=-1$\\\
\hline\cr$\sigma_{1}=1$&$\frac{1-(1-2p)x}{2p}$&$x$\\\
$\sigma_{1}=-1$&$x$&$\frac{-1-(1-2p)x}{2p}$\end{tabular}\qquad\mathbb{P}=\begin{tabular}[]{c|cc}&$\sigma_{2}=1$&$\sigma_{2}=-1$\\\
\hline\cr$\sigma_{1}=1$&$p$&$\frac{1}{2}-p$\\\
$\sigma_{1}=-1$&$\frac{1}{2}-p$&$p$\end{tabular}\right\\}$

Let $\mathcal{I}_{-}$ be the same information structure, but with
$x=-\frac{\sqrt{2+\sqrt{7}}}{3}$. It is a matter of calculation to verify that
these information structures satisfy projective substitutes. The quantity
$\mathbb{E}\left[(Y-\mathbb{E}\left[Y\right])^{2}\right]$ is the same for
$\mathcal{I}_{+}$ and $\mathcal{I}_{-}$, so the aggregation strategy $Z$ that
guarantees the largest possible approximation ratio when the information
structure is one of $\mathcal{I}_{+}$ and $\mathcal{I}_{-}$ is the one that
minimizes the maximum value of $\mathbb{E}\left[(Y-Z)^{2}\right]$ over these
two information structures. This is achieved by outputting $0$ when
$(Y_{1},Y_{2})$ is $(1,-1)$ or $(-1,1)$, $\frac{1}{2p}$ when
$(Y_{1},Y_{2})=(1,1)$, and $\frac{-1}{2p}$ when $(Y_{1},Y_{2})=(-1,-1)$. It is
a matter of calculation to verify that this aggregation strategy achieves an
approximation ratio of exactly $\frac{7\sqrt{7}-17}{2}$. ∎

###  7.6 Future directions in robust aggregation

Robust forecast aggregation is a new area. To our knowledge, this work is the
first to demonstrate nontrivial guarantees about forecast aggregation under a
truly broad class of information structures. But the space of questions to be
asked about robust forecast aggregation is much broader than the space of
questions that we have considered.

To highlight one example: we found that averaging followed by linear
extremization is a robust aggregation method, if the aggregator’s error is
their squared distance to the truth. However, this aggregation method does not
in general make sense for probabilistic forecasts: in particular, aggregating
probabilities in this way may result in aggregates outside of $[0,1]$. A
natural question to ask, then, is: what is a robust and sensible way to
aggregate _probabilistic_ forecasts?

If we change our error measure from squared distance to KL divergence, then
answers outside of $[0,1]$ become unacceptable, as they accrue infinite error
for the aggregator. And so we can ask: what aggregation methods achieve a high
worst-case approximation ratio, if we use KL divergence as our error measure?
A natural first guess might be generalized logarithmic pooling, as introduced
in Section 2.2.3. Is this aggregation method in fact robust?

To step back from this particular suggestion for future work, let us consider
the question that we answered in this chapter. The question was: what
_approximation ratio_ can be achieved by an aggregator who learns _expected
value estimates_ of a _real-valued_ quantity $Y$ from $m$ _truthful_ experts
whose signals are drawn from an information structure that satisfies
_projective substitutes,_ if the aggregator’s loss is their _squared error_
and the aggregator _knows nothing about the information structure or only
knows the prior?_ 121212We also showed a negative result in the setting where
the aggregator knows the entire information structure.

All of the emphasized phrases in this question can be varied! For example:

  * •

What if the aggregator is judged based on their KL divergence from the true
value of $Y$, or a different Bregman divergence? What if the aggregator is
judged based on an altogether different distance function (perhaps absolute
error), such that the aggregator no longer wants to guess about the
expectation of $Y$, but a different property (perhaps as the median)?

  * •

What if we make a different set of assumptions about the information
structure? We could restrict attention to PIF information structures. Or we
could use a different notion of informational substitutes. Or – following the
lead of [191] – we could assume that the experts’ signals are independent
conditioned on the value of $Y$, or that they are Blackwell ordered.

  * •

What if the aggregator knows more about the information structure, such as the
covariance matrix of the experts’ estimates, or perhaps the entire joint
probability distribution of their estimates?131313While our $\frac{4}{m}$
negative result applies in our setting regardless of how much the aggregator
knows, in other settings there may be strong approximation guarantees if the
expert knows more information than just the prior.

  * •

What if we choose a different benchmark? The approximation ratio as we have
defined it seems like a natural choice, but there may be others as well.

  * •

What if the aggregator learns information other than the experts’ expected
values? Perhaps the aggregator instead learns the median of each expert’s
probability distribution over $Y$. Or, if the aggregator has detailed
knowledge of the information structure, then it may make sense to ask what
happens if the aggregator learns partial information about the experts’
_signals._

  * •

What if the experts are strategic? Perhaps they want to influence the
aggregate forecast. What if the experts are biased in some way?

  * •

What if $Y$ is vector-valued, rather than real-valued?

Many of these settings (and the vast majority of _combinations_ of these
settings) have yet to be considered. The field of robust forecast aggregation
has great potential to grow, and to produce results that are both
theoretically interesting and practically useful.

## When does agreement imply accuracy?

_This chapter presents “Agreement Implies Accuracy for Substitutable
Signals”[250]. It assumes background on Bregman divergence (Section 2.1.3) and
information structures (Section 2.3)._

_Summary:_ Inspired by Aumann’s agreement theorem, [180] studied the amount of
communication necessary for two Bayesian experts to approximately agree on the
expectation of a random variable. Aaronson showed that, remarkably, the number
of bits does not depend on the amount of information available to each expert.
However, in general the agreed-upon estimate may be inaccurate: far from the
estimate they would settle on if they were to share all of their information.
We show that if the experts’ signals satisfy a particular notion of
informational substitutes, then it is the case that if the experts are close
to agreement then they are close to the truth. We prove this result for a
broad class of agreement and accuracy measures that includes squared distance
and KL divergence. Additionally, we show that although these measures capture
fundamentally different kinds of agreement, Aaronson’s agreement result
generalizes to them as well.

###  8.1 Introduction

Suppose that Alice and Bob are honest, rational Bayesians who wish to estimate
some quantity – say, the unemployment rate one year from now. Alice is an
expert on historical macroeconomic trends, while Bob is an expert on
contemporary monetary policy. They convene to discuss and share their
knowledge with each other until they reach an agreement about the expected
value of the future unemployment rate. Alice and Bob could reach agreement by
sharing everything they had ever learned, at which point they would have the
same information, but the process would take years. How, then, should they
proceed?

In the seminal work “Agreeing to Disagree,” [193] observed that Alice and Bob
can reach agreement simply by taking turns sharing their current expected
value for the quantity. In addition to modeling communication between Bayesian
agents, protocols similar to this one model financial markets: each trader
shares partial information about their expected value on their turn (discussed
in Section 8.5). A remarkable result by [180] shows that if Alice and Bob
follow certain protocols of this form, they will agree to within $\epsilon$
with probability $1-\delta$ by communicating
$O\left(\frac{1}{\delta\epsilon^{2}}\right)$ bits.111To ensure that each
message is short, Alice and Bob share discretized versions of their estimates;
we discuss this in Section 8.2. Notably, this bound only depends on the error
Alice and Bob are willing to tolerate, and not on the amount of information
available to them.

Absent from Aaronson’s results, however, is _what estimate Alice and Bob end
up agreeing on_. In particular, there is no guarantee that Alice and Bob will
be _accurate_ , meaning their agreed-upon estimate will be close (in e.g.
expected squared distance) to what they would believe if they shared all of
their information. In fact, they might agree on an estimate that is highly
inaccurate: suppose that Alice and Bob have independent, uniformly random bits
$b_{A},b_{B}$, and wish to estimate their XOR $b_{A}\oplus b_{B}$.222In
Section 2.3.2 we introduced this example and called it the “XOR information
structure.” Alice and Bob agree from the onset, as from each of their
perspectives, the expected value of $b_{A}\oplus b_{B}$ is $\frac{1}{2}$. Yet
this expectation is far from the best estimate given their collective
knowledge, which is either $0$ or $1$. So while agreement is fundamental to
understanding communication between Bayesians – in Aumann’s terms, they cannot
“agree to disagree” – agreement is far from the whole story. An important open
problem, therefore, is what assumptions guarantee that Alice and Bob are
accurate once they agree.

We address this open problem by introducing a natural condition, called
_rectangle substitutes_ , under which agreement implies accuracy. Rectangle
substitutes is a notion of _informational substitutes_ (discussed in Section
2.3.2): the property that additional information has diminishing marginal
returns. The notion of substitutes is ubiquitous in optimization problems, and
informational substitutes conditions have recently been used to analyze
equilibria in markets [223]. In that context, [279] showed for conditionally
independent signals convergence of the popular LMSR market implies full
information aggregation, i.e. accuracy. We show that under the rectangle
substitutes condition, _any_ protocol leading to agreement will also lead to
accuracy. We then extend these results beyond the case of squared error, to a
broad family of measures of agreement and accuracy including KL
divergence.333Specifically, agreement and accuracy with respect to (almost)
arbitrary Bregman divergences.

####  8.1.1 Overview of approach and results

In [180], Alice and Bob are said to _agree_ if the squared difference between
their estimates is small. Likewise, we can say that Alice and Bob are
_accurate_ if the squared distance between each of their estimates and the
truth is small. In Section 8.3 we present our first main result: under these
definitions, if the information structure describing Alice and Bob’s signals
satisfies the rectangle substitutes condition, then agreement implies
accuracy. In other words, under this assumption, when two Bayesians agree –
regardless of how little information they have shared – they necessarily agree
_on the truth_.

The proof involves carefully partitioning the space of posterior beliefs
induced by the protocol. Agreement is used to show that Alice and Bob usually
fall into the same partition element, which means that Bob would not learn
much from learning the partition element of Alice’s expectation. Then, the
rectangle substitutes condition is used to show that if Bob were to learn
Alice’s partition element, then he would be very close to knowing the truth.

Aaronson measures agreement in terms of squared error, yet other measurements
like KL divergence may be better suited for some settings. For example, if
Alice and Bob estimate the probability of a catastrophic event as $10^{-10}$
and $10^{-2}$, respectively, then under squared error they are said to agree
closely, but arguably they disagree strongly, as reflected by their large KL
divergence. Motivated by these different ways to measure agreement, we next
ask:

  1. (1)

Can Aaronson’s protocols be generalized to other notions of agreement, such
that the number of bits communicated is independent of the amount of
information available to Alice and Bob?

  2. (2)

Do other notions of agreement necessarily imply accuracy under rectangle
substitutes?

In Section 8.4, we give our second and third main results: the answer to both
questions is yes. Specifically, the positive results apply when when measuring
agreement and accuracy using Bregman divergences, a class of error measures
that includes both squared distance and KL divergence.444The third result
holds under an “approximate triangle inequality” condition on the Bregman
divergence, which is satisfied by most or all natural choices; indeed, it is
nontrivial to construct a Bregman divergence that does not satisfy this
property.

Aaronson’s proof of his agreement theorem turns out to be specific to squared
distance. Our agreement theorem (Theorem 8.4.8) modifies Aaronson’s protocol
to depend on the particular Bregman divergence, i.e. the relevant error
measure. It then proceeds in a manner inspired by Aaronson but using several
new ideas. Our proof that agreement implies accuracy under rectangle
substitutes for general Bregman divergences also involves some nontrivial
changes to our proof for squared distance. In particular, the fact that the
length of an interval cannot be inferred from the Bregman divergence between
its endpoints necessitates a closer analysis of the partition of Alice’s and
Bob’s beliefs.

We conclude in Section 8.5 with a discussion of connections between agreement
protocols and information revelation in financial markets, and discuss an
interesting potential avenue for future work.

####  8.1.2 Related work

[251] discussed the distinction between agreement and full information
revelation. One result shown is that under a natural probability measure on
information structures, full agreement and information revelation occur in a
single round of communication with probability one. However, conditions for
accuracy and the concept of substitutes are not discussed.

Our setting is related to but distinct from communication complexity. In that
field (e.g. [321]), the goal is for Alice and Bob to correctly compute a
function of their inputs while communicating as few bits as possible and using
any protocol necessary. By contrast, [180] considered a goal of agreement, not
correctness, and focused on specific natural protocols, which he showed
achieve this goal in a constant number of bits. Our work focuses on Aaronson’s
setting. We discuss how our results might be framed in terms of communication
complexity in Appendix D.5.

Our introduction of the substitutes condition is inspired by its usefulness in
prediction markets [223]. The “expectation-sharing” agreement protocols we
study bear a strong similarity to dynamics of market prices. [316] introduced
a condition under which convergence of prices in a market implies that all
information is aggregated. This can be viewed as an “agreement implies
accuracy” condition. Similarly, [279] presented a result that, for the
logarithmic market scoring rule (LMSR) and conditionally independent signals,
convergence of the market implies full information revelation. Our results are
conceptually similar, although they are technically quite different as we rely
on the novel condition of _rectangle substitutes_. In the context of the LMSR,
the rectangle substitutes notion includes conditionally independent signals as
a special case (see discussion in Section 8.4.1). We discuss the connection of
our work to markets in Section 8.5.

###  8.2 Preliminaries

####  8.2.1 Information structures

In Section 2.3, we introduced the concept of an information structure as a
tuple consisting of a probability distribution $\mathbb{P}$ over a set
$\Omega$ of states of the world, a quantity $Y$, and a tuple of $m$ signals
that give partial information about the state of the world $\omega$ (and thus
about $Y$).

In this chapter, we specifically consider the case of $m=2$ signals and choose
notation accordingly. We will say that there are two experts, Alice and Bob.
Alice’s signal is $\sigma:\Omega\to\mathcal{S}$ and Bob’s signal is
$\tau:\Omega\to\mathcal{T}$. Thus, we will think of information structures as
5-tuples $(\Omega,\mathbb{P},\sigma,\tau,Y)$. We additionally assume
(following Aaronson) that $Y$ takes values in $[0,1]$.

We denote by $\mu_{\sigma\tau}:=\mathbb{E}\left[Y\mid\sigma,\tau\right]$ the
random variable that is equal to the expected value of $Y$ conditioned on both
Alice’s signal $\sigma$ and Bob’s signal $\tau$.555The value of $Y$ need not
be determined by $\sigma$ and $\tau$, although for our purposes the case in
which it is determined is essentially equivalent. We also define
$\mu_{\sigma}:=\mathbb{E}\left[Y\mid\sigma\right]$ and
$\mu_{\tau}:=\mathbb{E}\left[Y\mid\tau\right]$. For a measurable set
$S\subseteq\mathcal{S}$, we define $\mu_{S}:=\mathbb{E}\left[Y\mid\sigma\in
S\right]$; we define $\mu_{T}$ analogously for $T\subseteq\mathcal{T}$.
Additionally, for $T\subseteq\mathcal{T}$, we define $\mu_{\sigma
T}:=\mathbb{E}\left[Y\mid\tau\in T,\sigma\right]$, i.e. the expected value of
$Y$ conditioned on the particular value of $\sigma$ and the knowledge that
$\tau\in T$. If Alice knows that Bob’s signal belongs to $T$ (and nothing else
about his signal), then the expected value of $Y$ conditional on her
information is $\mu_{\sigma T}$; we refer to this as Alice’s _expectation_.
Likewise, for $S\subseteq\mathcal{S}$, we define
$\mu_{S\tau}:=\mathbb{E}\left[Y\mid\sigma\in S,\tau\right]$. Finally, we
define $\mu_{ST}:=\mathbb{E}\left[Y\mid\sigma\in S,\tau\in T\right]$. This is
the expectation of a third party who only knows that $\sigma\in S$ and
$\tau\in T$.

In general we often wish to take expectations conditioned on $\sigma\in
S,\tau\in T$ (for some $S\subseteq\mathcal{S},T\subseteq\mathcal{T}$). We will
use the shorthand $\mathbb{E}\left[\cdot\mid S,T\right]$ for
$\mathbb{E}\left[\cdot\mid\sigma\in S,\tau\in T\right]$ in such cases.

####  8.2.2 Agreement protocols

The notion of _agreement_ between Alice and Bob is central to our work. We
first define agreement in terms of squared error, and generalize to other
error measures in Section 8.4.

######  Definition 8.2.1 ($\epsilon$-agreement).

Let $a$ and $b$ be Alice’s and Bob’s expectations, respectively ($a$ and $b$
are random variables defined on $\Omega$). Alice and Bob _$\epsilon$ -agree_
if $\frac{1}{4}\mathbb{E}\left[(a-b)^{2}\right]\leq\epsilon$.

The constant $\frac{1}{4}$ makes the left-hand side represent Alice’s and
Bob’s squared distance to the average of their expectations.

Our setting follows [180], which examined communication protocols that cause
Alice and Bob to agree. In a _(deterministic) communication protocol_ , Alice
and Bob take turns sending each other messages (strings of bits). On Alice’s
turns, Alice communicates a message that is a deterministic function of her
input (i.e. her signal $\sigma$) and all previous communication, and likewise
for Bob on his turns. A _rectangle_ is a set of the form $S\times T$ where
$S\subseteq\mathcal{S}$ and $T\subseteq\mathcal{T}$.

The _communication transcript_ is the ordered tuple of all messages that have
been sent. The transcript _at time step $t$_ refers to the tuple consisting of
the first $t$ messages. The transcript at time step $t$ partitions $\Omega$
into rectangles: for any given sequence of $t$ messages, there are subsets
$S_{t}\subseteq\mathcal{S},T_{t}\subseteq\mathcal{T}$ such that the protocol
transcript at time $t$ is equal to this sequence if and only if
$(\sigma,\tau)\in S_{t}\times T_{t}$.666We can see this inductively: suppose
the transcript at time step $t-1$ partitions $\Omega$ into rectangles, and
(without loss of generality) that the $t$-th turn is Alice’s. Consider one of
these rectangles. Alice’s message can only depend on her input and the
transcript so far, which means that her message can only partition this
rectangle into sub-rectangles.

For a given communication protocol, we may think of $S_{t}$ and $T_{t}$ as
random variables. Alice’s expectation at time $t$ (i.e.  _after_ the $t$-th
message has been sent) is $\mu_{\sigma T_{t}}$ and Bob’s expectation at time
$t$ is $\mu_{S_{t}\tau}$. Finally, the protocol terminates at a certain time
(which need not be known in advance of the protocol). While typically in
communication complexity a protocol is associated with a final output, in this
case we are interested in Alice’s and Bob’s expectations, so we do not require
an output.

It will be convenient to hypothesize a third party observer, whom we call
Charlie, who observes the protocol but has no other information. At time $t$,
Charlie has expectation $\mu_{S_{t}T_{t}}$. Charlie’s expectation can also be
interpreted as the expectation of $Y$ according to Alice and Bob’s common
knowledge. Note that Alice and Bob each know Charlie’s expectation at any
given time.

The following definition formalizes the relationship between communication
protocols and agreement.

######  Definition 8.2.2 ($\epsilon$-agreement protocol).

Given an information structure $\mathcal{I}$, a communication protocol _causes
Alice and Bob to $\epsilon$-agree_ on $\mathcal{I}$ if Alice and Bob
$\epsilon$-agree at the end of the protocol, i.e., if
$\frac{1}{4}\mathbb{E}\left[(\mu_{\sigma
T_{t}}-\mu_{S_{t}\tau})^{2}\right]\leq\epsilon$, where the expected value is
over Alice’s and Bob’s inputs. We say that a communication protocol is an
_$\epsilon$ -agreement protocol_ if the protocol causes Alice and Bob to
$\epsilon$-agree on every information structure.

Aaronson defines and analyzes two $\epsilon$-agreement protocols.777A minor
difference to our framing is that [180] focuses on _probable approximate
agreement_ : protocols that cause the absolute difference between Alice and
Bob to be at most $\epsilon$ with probability all but $\delta$. While the
results as presented in this section are stronger than those in [180] (the
original results follow from these as a consequence of Markov’s inequality),
these results follow from a straightforward modification of his proofs. The
first of these is the _standard protocol_ , in which Alice and Bob take turns
stating their expectations for a number of time steps that can be computed by
Alice and Bob independently in advance of the protocol, and which is
guaranteed to be at most $O(1/\epsilon)$.

The fact that exchanging their expectations for $O(1/\epsilon)$ time steps
results in $\epsilon$-agreement is profound and compelling. However, the
standard protocol may require an unbounded number of bits of communication,
since Alice and Bob are exchanging real numbers. To address this, Aaronson
defines another agreement protocol that is truly polynomial-communication
(which we slightly modify for our purposes):

######  Definition 8.2.3 (Discretized protocol, [180]).

Choose $\epsilon>0$. In the _discretized protocol_ with parameter $\epsilon$,
on her turn (at time $t$), Alice sends “low” if her expectation is smaller
than Charlie’s by more than $\epsilon/4$, i.e. if
$\mu_{S_{t-1}\tau}<\mu_{S_{t-1}T_{t-1}}-\epsilon/4$; “high” if her expectation
is larger than Charlie’s by more than $\epsilon/4$; and “medium” otherwise.
Bob acts analogously on his turn. At the start of the protocol, Alice and Bob
use the information structure to independently compute the time
$t_{\text{end}}\leq\frac{1000}{\epsilon}$ that minimizes
$\mathbb{E}\left[(\mu_{\sigma
T_{t_{\text{end}}}}-\mu_{S_{t_{\text{end}}}\tau})^{2}\right]$. The protocol
ends at this time.

######  Theorem 8.2.4 ([180, Theorem 4]).

The discretized protocol with parameter $\epsilon$ is an $\epsilon$-agreement
protocol with transcript length $O(1/\epsilon)$ bits.

In general, we refer to Aaronson’s standard and discretized protocols as
examples of _expectation-sharing_ protocols. We will define other examples in
Section 8.4, similar to Aaronson’s discretized protocol but with different
cutoffs for low, medium, and high. We also interpret expectation-sharing
protocols in the context of markets in Section 8.5.

####  8.2.3 Accuracy and informational substitutes

Most of our main results give conditions such that if Alice and Bob
$\epsilon$-agree, then Alice’s and Bob’s estimates are accurate. By _accurate_
, we mean that Alice’s and Bob’s expectations are close to $\mu_{\sigma\tau}$,
i.e., what they would believe if they knew each other’s signals. (After all,
they cannot hope to have a better estimate of $Y$ than $\mu_{\sigma\tau}$; for
this reason we sometimes refer to $\mu_{\sigma\tau}$ as the “truth.”)
Formally:

######  Definition 8.2.5 ($\epsilon$-accuracy).

Let $a$ be Alice’s expectation. Alice is _$\epsilon$ -accurate_ if
$\mathbb{E}\left[(\mu_{\sigma\tau}-a)^{2}\right]\leq\epsilon$. We define
$\epsilon$-accuracy analogously for Bob.

One cannot hope for an unconditional result stating that if Alice and Bob
agree, then they are accurate. Consider for instance the _XOR information
structure_ from the introduction: Alice and Bob each receive independent
random bits as input, and $Y$ is the XOR of these bits. Then from the start
Alice and Bob agree that the expected value of $Y$ is exactly $\frac{1}{2}$,
but this value is far from $\mu_{\sigma\tau}$, which is either $0$ or $1$.

Intuitively, this situation arises because Alice’s and Bob’s signals are
_informational complements_ : each signal is not informative by itself, but
they are informative when taken together. On the other hand, we say that
signals are _informational substitutes_ if learning one signal is less
valuable if you already know the other signal. We introduced and motivated the
concept of informational substitutes in Section 2.3.2. In particular, we
defined _weak substitutes_ (first introduced by [223]) as a formalization of
the notion of diminishing marginal returns to learning an extra signal. An
extreme example of informational substitutes is if $\sigma$ and $\tau$ both
specify the value of $Y$ exactly. In that case, $\sigma$ becomes useless upon
learning $\tau$ and vice versa. Our definition is inspired by the definition
of weak substitutes, but we require a stronger notion for our results to hold.
For the following definition, recall that we write $\mid S,T$ as shorthand for
$\mid\sigma\in S,\tau\in T$.

######  Definition 8.2.6.

An information structure $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$
satisfies _rectangle substitutes_ if for every
$S\subseteq\mathcal{S},T\subseteq\mathcal{T}$ such that $\mathbb{P}[\sigma\in
S,\tau\in T]>0$, we have

$\mathbb{E}\left[(Y-\mu_{S\tau})^{2}\mid
S,T\right]-\mathbb{E}\left[(Y-\mu_{\sigma\tau})^{2}\mid
S,T\right]\leq\mathbb{E}\left[(Y-\mu_{ST})^{2}\mid
S,T\right]-\mathbb{E}\left[(Y-\mu_{\sigma T})^{2}\mid S,T\right].$ (8.1)

This definition is a strengthening of weak substitutes for two agents: an
information structure satisfies _weak substitutes_ if Equation 8.1 holds
specifically for $S=\mathcal{S}$ and $T=\mathcal{T}$. We will show that under
the rectangle substitutes condition, if Alice and Bob approximately agree,
then they are approximately accurate.

##### Interpreting substitutes

Both sides of Equation 8.1 represent the “value” of learning $\sigma$ as
measured by a decrease in error. The left-hand side gives the decrease if one
already knows $\tau$ and that $\sigma\in S$; the right-hand side gives the
decrease if one only knows that $\sigma\in S,\tau\in T$. Substitutes thus
says: the marginal value of learning $\sigma$ is smaller if one already knows
$\tau$ than if one does not. This statement should hold for every sub-
rectangle $S,T$. Note that the inequality can be rearranged to focus instead
on the marginal value of $\tau$ rather than $\sigma$. Note also that in the
XOR information structure, the left-hand side of the inequality is
$\frac{1}{4}$ while the right-hand side is zero: a large violation of the
substitutes condition. In the example where $\sigma$ and $\tau$ both specify
the value of $Y$, the left side is always zero.

[223] discusses three interpretations of substitutes, which motivate it as a
natural condition. (1) Each side of the inequality measures an improvement in
_prediction error_ , here the squared loss, due to learning $\sigma$. Under
substitutes, the improvement is smaller if one already knows $\tau$. (2) Each
side measures a _decrease in uncertainty_ (here, measured roughly by
_variance_) due to learning $\sigma$. Under substitutes, $\sigma$ provides
less information about $Y$ if one already knows $\tau$.888Here, uncertainty is
measured by variance of one’s belief. Under the KL divergence analogue covered
in Section 8.4.1, uncertainty is measured in bits via Shannon entropy. (3)
Each side measures the _decrease in distance_ of a posterior expectation from
the truth when learning $\sigma$. The distance to $Y$ changes less if one
already knows $\tau$.

##### Restrictiveness of substitutes

It is natural to ask about the strength of the rectangle substitutes
assumption. In the case that
$\left\lvert\mathcal{S}\right\rvert=\left\lvert\mathcal{T}\right\rvert=2$, the
condition reduces to the aforementioned and well-established weak substitutes
condition. For larger signal sets, the set of information structures
satisfying rectangle substitutes remains nontrivial. For example, it is
satisfied by a positive fraction of information structures (for a natural
choice of measure). We show this fact in Appendix D.1 by exhibiting an
information structure in which Equation 8.1 holds _strictly_ for all $S,T$
with $\left\lvert S\right\rvert,\left\lvert T\right\rvert\geq 2$ (and thus,
that all nearby information structures also satisfy rectangle substitutes).
Finally, we note that although the rectangle substitutes condition is strong
due to the quantification over sub-rectangles, in Section 8.3.3 we prove that
our main results decay gracefully for information structures that are close to
but do not quite satisfy the rectangle substitutes condition.

####  8.2.4 The Pythagorean theorem

We recall the Pythagorean theorem from Section 2.3.3: See 2.3.11

One application of the Pythagorean theorem in our context takes $A=Y$,
$B=\mu_{\sigma\tau}$ (the expected value of $Y$ conditioned on the experts’
signals), and $C=\mu_{\sigma T}$ (Alice’s expected value, which only depends
on her signal and thus on the signal pair). This particular application, along
with the symmetric one taking $C=\mu_{S\tau}$, allows us to rewrite the
rectangle substitutes condition in a form that we will find more convenient:

######  Remark 8.2.7.

An information structure $\mathcal{I}$ satisfies rectangle substitutes if and
only if

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\mid
S,T\right]\leq\mathbb{E}\left[(\mu_{\sigma T}-\mu_{ST})^{2}\mid S,T\right]$
(8.2)

for all $S,T$ such that $\mathbb{P}[\sigma\in S,\tau\in T]>0$.

###  8.3 Results for squared distance

Our main results show that, under the rectangle substitutes condition, any
communication protocol that causes Alice and Bob to agree also causes them to
be accurate. We now show the first of these results, which is specific to the
squared distance error measure that we have been discussing.

####  8.3.1 Agreement implies accuracy

######  Theorem 8.3.1.

Let $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information
structure that satisfies rectangle substitutes. For any communication protocol
that causes Alice and Bob to $\epsilon$-agree on $\mathcal{I}$, Alice and Bob
are $10\epsilon^{1/3}$-accurate after the protocol terminates.

The crux of the argument is the following lemma.

######  Lemma 8.3.2.

Let $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information
structure that satisfies rectangle substitutes. Let
$\epsilon=\mathbb{E}\left[(\mu_{\sigma}-\mu_{\tau})^{2}\right]$. Then

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\tau})^{2}\right]\leq
6\epsilon^{1/3}.$

Let us first prove Theorem 8.3.1 assuming Lemma 8.3.2 is true.

###### Proof of Theorem 8.3.1.

Consider any protocol that causes Alice and Bob to $\epsilon$-agree on
$\mathcal{I}$. Let $S$ be the set of possible signals of Alice at the end of
the protocol which are consistent with the protocol transcript, and define $T$
likewise for Bob. Intuitively, $S\times T$ is the set of plausible signal
pairs $(\sigma,\tau)$ according to an external observer of the protocol.
Observe that $S$ and $T$ are random variables, each a function of both
$\sigma$ and $\tau$. We have

$\displaystyle\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\right]$
$\displaystyle=\mathbb{E}_{S,T}\left[\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\mid
S,T\right]\right]$
$\displaystyle\leq\mathbb{E}_{S,T}\left[6\left(\mathbb{E}\left[(\mu_{\sigma
T}-\mu_{S\tau})^{2}\mid S,T\right]\right)^{1/3}\right]$ $\displaystyle\leq
6\mathbb{E}_{S,T}\left[\mathbb{E}\left[(\mu_{\sigma T}-\mu_{S\tau})^{2}\mid
S,T\right]\right]^{1/3}$ $\displaystyle=6\mathbb{E}\left[(\mu_{\sigma
T}-\mu_{S\tau})^{2}\right]^{1/3}\leq 6(4\epsilon)^{1/3}\leq 10\epsilon^{1/3}.$

In the second step, we apply Lemma 8.3.2 to the information structure
$\mathcal{I}$ restricted to $S\times T$ – that is, to
$\mathcal{I}^{\prime}=(\Omega^{\prime},\mathbb{P}^{\prime},S,T,Y)$, where
$\Omega^{\prime}=\\{\omega\in\Omega:\sigma\in S,\tau\in T\\}$ and
$\mathbb{P}^{\prime}[\omega]=\mathbb{P}[\omega\mid\sigma\in S,\tau\in T]$.
(Note that we use the fact that if $\mathcal{I}$ satisfies rectangle
substitutes, then so does $\mathcal{I}^{\prime}$; this is because a rectangle
of $\mathcal{I}^{\prime}$ is also a rectangle of $\mathcal{I}$.) The third
step follows by the concavity of $x^{1/3}$. Therefore, Bob is
$10\epsilon^{1/3}$ accurate (and Alice is likewise by symmetry). ∎

The proof of Lemma 8.3.2 relies on the following claim.

######  Claim 8.3.3.

In the setting of Lemma 8.3.2, for any $N\geq 1$, it is possible to partition
$[0,1]$ into $N$ intervals $[0,x_{1}),[x_{1},x_{2}),\dots,$ $[x_{N-1},1]$ in a
way so that each interval has length at most $\frac{2}{N}$, and

$\mathbb{P}[k(\sigma)\neq k(\tau)]\leq\sqrt{\epsilon}N,$

where $k(\sigma)$ denotes the $k\in[N]$ such that
$x_{k-1}\leq\mu_{\sigma}<x_{k}$, and $k(\tau)$ is defined analogously.999For
convenience we define $x_{0}=0$ and $x_{N}$ to be some number greater than
$1$.

Intuitively, Claim 8.3.3 is true because if
$\mathbb{E}\left[(\mu_{\sigma}-\mu_{\tau})^{2}\right]$ is small, then
$\mu_{\sigma}$ and $\mu_{\tau}$ are likely to fall into the same interval.

###### Proof.

We claim that in fact we can choose the $x_{i}$’s so that each $x_{i}$ is in
$\left[\frac{i}{N}-\frac{1}{2N},\frac{i}{N}+\frac{1}{2N}\right]$. This ensures
that each interval has length at most $\frac{2}{N}$.

For $x\in[0,1]$, let $\rho(x)$ be the probability that $x$ is between
$\mu_{\sigma}$ and $\mu_{\tau}$, inclusive. Note that
$\mathbb{P}[k(\sigma)\neq k(\tau)]\leq\sum_{i=1}^{N-1}\rho(x_{i})$.

Observe that if $x$ is selected uniformly from $[0,1]$, the expected value of
$\rho(x)$ is equal to $\left\lvert\mu_{\sigma}-\mu_{\tau}\right\rvert$,
because both quantities are equal to the probability that $x$ is between
$\mu_{\sigma}$ and $\mu_{\tau}$. Therefore, if $(\sigma,\tau)$ is additionally
chosen according to $\mathbb{P}$, we have

$\mathbb{E}_{x\leftarrow[0,1]}\left[\rho(x)\right]=\mathbb{E}\left[\left\lvert\mu_{\sigma}-\mu_{\tau}\right\rvert\right]\leq\sqrt{\mathbb{E}\left[(\mu_{\sigma}-\mu_{\tau})^{2}\right]}=\sqrt{\epsilon}.$

This means that

$\sum_{i=1}^{N-1}\mathbb{E}_{x\leftarrow\left[\frac{i}{N}-\frac{1}{2N},\frac{i}{N}+\frac{1}{2N}\right]}\left[\rho(x)\right]=(N-1)\mathbb{E}_{x\leftarrow\left[\frac{1}{2N},1-\frac{1}{2N}\right]}\left[\rho(x)\right]\leq\sqrt{\epsilon}N.$

Thus, if each $x_{i}$ is selected uniformly at random from
$\left[\frac{i}{N}-\frac{1}{2N},\frac{i}{N}+\frac{1}{2N}\right]$, the expected
value of $\mathbb{P}[k(\sigma)\neq k(\tau)]$ would be at most
$\sqrt{\epsilon}N$. In particular this means that there exist choices of the
$x_{i}$’s such that $\mathbb{P}[k(\sigma)\neq k(\tau)]\leq\sqrt{\epsilon}N$. ∎

We now prove Lemma 8.3.2.

###### Proof of Lemma 8.3.2.

Fix a large positive integer $N$ (we will later find it optimal to set
$N=\epsilon^{-1/6}$). Consider a partition of $[0,1]$ into $N$ intervals
$[0,x_{1}),[x_{1},x_{2}),\dots,[x_{N-1},1]$ satisfying the conditions of Claim
8.3.3. Let
$S^{(k)}:=\\{\sigma\in\mathcal{S}:x_{k-1}\leq\mu_{\sigma}<x_{k}\\}$.
Additionally, let $k(\sigma)$ and $k(\tau)$ be as defined in Claim 8.3.3.

Our goal is to upper bound the expectation of
$(\mu_{\sigma\tau}-\mu_{\tau})^{2}$. In pursuit of this goal, we observe that
by the Pythagorean theorem, we have

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\tau})^{2}\right]=\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S^{(k(\sigma))}\tau})^{2}\right]+\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\tau}-\mu_{\tau})^{2}\right].$

We now use the rectangle substitutes assumption: for any $k$, by applying
Equation 8.2 to $S=S^{(k)}$ and $T=\mathcal{T}$, we know that

$\mathbb{E}\left[(\mu_{\sigma}-\mu_{S^{(k)}})^{2}\mid\sigma\in
S^{(k)}\right]\geq\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S^{(k)}\tau})^{2}\mid\sigma\in
S^{(k)}\right].$

Taking the expectation over $k$ (i.e. choosing each $k$ with probability equal
to $\mathbb{P}[\sigma\in S^{(k)}]$), we have that

$\mathbb{E}\left[(\mu_{\sigma}-\mu_{S^{(k(\sigma))}})^{2}\right]\geq\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S^{(k(\sigma))}\tau})^{2}\right].$
(8.3)

Therefore, we have

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\tau})^{2}\right]\leq\mathbb{E}\left[(\mu_{\sigma}-\mu_{S^{(k(\sigma))}})^{2}\right]+\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\tau}-\mu_{\tau})^{2}\right].$
(8.4)

We will use Claim 8.3.3 to argue that each of these two summands is small. The
argument regarding the first summand is straightforward: for any $\sigma$, we
have that
$x_{k(\sigma)}\leq\mu_{\sigma},\mu_{S^{(k(\sigma))}}<x_{k(\sigma)+1}\leq
x_{k(\sigma)}+\frac{2}{N}$, which means that
$\mathbb{E}\left[(\mu_{\sigma}-\mu_{S^{(k(\sigma))}})^{2}\right]\leq\frac{4}{N^{2}}$.

We now upper bound the second summand.101010The proof below takes sums over
$\hat{\tau}\in\mathcal{T}$ and thus implicitly assumes that $\mathcal{T}$ is
finite, but the proof extends to infinite $\mathcal{T}$, with sums over $\tau$
replaced by integrals with respect to the probability measure over
$\mathcal{T}$. For any $\hat{\tau}\in\mathcal{T}$, let
$p(\hat{\tau})=\mathbb{P}[\tau=\hat{\tau}]$ and
$q(\hat{\tau})=\mathbb{P}[\tau=\hat{\tau},k(\sigma)\neq k(\tau)]$. Then
$\sum_{\hat{\tau}\in\mathcal{T}}p(\hat{\tau})=1$ and
$\sum_{\hat{\tau}\in\mathcal{T}}q(\hat{\tau})\leq\sqrt{\epsilon}N$. Observe
that

$\displaystyle\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\tau}-\mu_{\tau})^{2}\right]$
$\displaystyle=\sum_{\hat{\tau}}p(\hat{\tau})\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\hat{\tau}})^{2}\mid\tau=\hat{\tau}\right]$
$\displaystyle=\sum_{\hat{\tau}}(p(\hat{\tau})-q(\hat{\tau}))\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\hat{\tau}})^{2}\mid\tau=\hat{\tau},k(\sigma)=k(\hat{\tau})\right]$
$\displaystyle\qquad+q(\hat{\tau})\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\hat{\tau}})^{2}\mid\tau=\hat{\tau},k(\sigma)\neq
k(\hat{\tau})\right].$ (8.5)

To handle the first expectation, we note that if $k(\sigma)=k(\hat{\tau})$,
then
$\left\lvert\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\hat{\tau}}\right\rvert\leq\frac{q(\hat{\tau})}{p(\hat{\tau})}$.
To see this, observe

$p(\hat{\tau})\mu_{\hat{\tau}}=(p(\hat{\tau})-q(\hat{\tau}))\mu_{S^{(k(\sigma))}\hat{\tau}}+q(\hat{\tau})\mu_{\mathcal{S}\setminus
S^{(k(\sigma))}\hat{\tau}}~{}.$

Rearranging and taking absolute values, we conclude

$p(\hat{\tau})\left\lvert\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\hat{\tau}}\right\rvert=q(\hat{\tau})\left\lvert\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\mathcal{S}\setminus
S^{(k(\sigma))}}\right\rvert\leq q(\hat{\tau}).$

Therefore, recalling $q(\hat{\tau})\leq p(\hat{\tau})$, we have

$\displaystyle(p(\hat{\tau})-q(\hat{\tau}))\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\hat{\tau}}-\mu_{\hat{\tau}})^{2}\mid\tau=\hat{\tau},k(\sigma)=k(\hat{\tau})\right]\leq(p(\hat{\tau})-q(\hat{\tau}))\left(\frac{q(\hat{\tau})}{p(\hat{\tau})}\right)^{2}\leq\frac{q(\hat{\tau})^{2}}{p(\hat{\tau})}\leq
q(\hat{\tau}).$

On the other hand, we can bound the second expectation in Equation 8.3.1 by
$1$. Therefore we have

$\mathbb{E}\left[(\mu_{S^{(k(\sigma))}\tau}-\mu_{\tau})^{2}\right]\leq\sum_{\hat{\tau}}(q(\hat{\tau})+q(\hat{\tau}))=2\sum_{\hat{\tau}}q(\hat{\tau})\leq
2\sqrt{\epsilon}N.$

To conclude, we now know that

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\tau})^{2}\right]\leq\frac{4}{N^{2}}+2\sqrt{\epsilon}N.$

Setting $N=\epsilon^{-1/6}$ makes the right-hand side equal to
$6\epsilon^{1/3}$, completing the proof. ∎

Now that we have proven Lemma 8.3.2, our proof of Theorem 8.3.1 is complete.

####  8.3.2 Consequences of Theorem 8.3.1

Theorem 8.3.1 is a general result about agreement protocols. Applying the
result to Aaronson’s discretized protocol gives us the following result.

######  Corollary 8.3.4.

Let $\mathcal{I}$ be any information structure that satisfies universal
rectangle substitutes. For any $\epsilon>0$, Alice and Bob will be
$\epsilon$-accurate after running Aaronson’s discretized protocol with
parameter $\epsilon^{3}/1000$ (and this takes $O(1/\epsilon^{3})$ bits of
communication).

######  Remark 8.3.5.

The discretized protocol is not always the most efficient agreement protocol.
For example, Proposition D.2.1 shows that if the rectangle substitutes
condition holds, agreement (and therefore accuracy) can be reached with just
$O(\log(1/\epsilon))$ bits, an improvement on Corollary 8.3.4. We discuss
communication complexity further in Appendix D.5. Even if more efficient
protocols are sometimes possible, expectation-sharing protocols are of
interest because they model naturally-occurring communication processes. For
example, they capture the dynamics of prices in markets, which we also discuss
in Section 8.5. More generally, we find it remarkable that Alice and Bob
become accurate by running Aaronson’s agreement protocol (or indeed _any_
agreement protocol), despite such protocols being designed with only agreement
in mind.

Finally, we observe the following important consequence of Theorem 8.3.1: once
Alice and Bob agree, they continue to agree.

######  Corollary 8.3.6.

Let $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information
structure that satisfies rectangle substitutes. Consider a communication
protocol with the property that Alice and Bob $\epsilon$-agree after round
$t$. Then Alice and Bob $10\epsilon^{1/3}$-agree on all subsequent time steps.

###### Proof.

If Alice and Bob $\epsilon$-agree then they are $10\epsilon^{1/3}$-accurate,
so in particular $\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\sigma
T_{t}})^{2}\right]\leq 10\epsilon^{1/3}$. Note that
$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\sigma T_{s}})^{2}\right]$ is a
decreasing function of $s$, since for any $s_{1}\leq s_{2}$ we have

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\sigma
T_{s_{1}}})^{2}\right]=\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\sigma
T_{s_{2}}})^{2}\right]+\mathbb{E}\left[(\mu_{\sigma T_{s_{2}}}-\mu_{\sigma
T_{s_{1}}})^{2}\right]$

by the Pythagorean theorem. Therefore, for any $t^{\prime}>t$, we have
$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\sigma T_{t^{\prime}}})^{2}\right]\leq
10\epsilon^{1/3}$. Symmetrically, we have
$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S_{t^{\prime}}\tau})^{2}\right]\leq
10\epsilon^{1/3}$. Therefore, $\mathbb{E}\left[(\mu_{\sigma
T_{t^{\prime}}}-\mu_{S_{t^{\prime}}\tau})^{2}\right]\leq 40\epsilon^{1/3}$,
which means that after round $t^{\prime}$, Alice and Bob
$10\epsilon^{1/3}$-agree. ∎

Corollary 8.3.6 stands in contrast to the more general case, in which it is
possible that Alice and Bob “nearly agree for the first $t-1$ time steps, then
disagree violently at the $t$-th step” [180, §2.2]. Thus, while the main
purpose of Theorem 8.3.1 is a property about _accuracy_ , an _agreement_
property falls out naturally: under the rectangle substitutes condition, once
Alice and Bob are close to agreement, they will remain in relatively close
agreement into the future.

####  8.3.3 Graceful decay under closeness to rectangle substitutes

In a sense, the rectangle substitutes condition is quite strong: it requires
that the weak substitutes condition be satisfied on _every_ sub-rectangle. One
might hope for a result that generalizes Theorem 8.3.1 to information
structures that almost-but-not-quite satisfy the rectangle substitutes. Let us
formally define a notion of closeness to rectangle substitutes.

######  Definition 8.3.7.

An information structure $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$
satisfies _$\delta$ -approximate rectangle substitutes_ if for every partition
of $\mathcal{S}\times\mathcal{T}$ into rectangles,111111There are partitions
into rectangles that cannot arise from a communication protocol. Our results
would apply equally if this condition were instead defined for every partition
that could arise from a communication protocol, but we state this condition
more generally so that it could be applicable in a broader context than the
analysis of communication protocols. the rectangle substitutes condition holds
in expectation over the partition, up to an additive constant of $\delta$,
i.e., if we have

$\mathbb{E}_{\sigma,\tau}\left[(\mu_{\sigma\tau}-\mu_{S_{\sigma,\tau}\tau})^{2}\right]\leq\mathbb{E}_{\sigma,\tau}\left[(\mu_{\sigma
T_{\sigma,\tau}}-\mu_{S_{\sigma,\tau}T_{\sigma,\tau}})^{2}\right]+\delta,$
(8.6)

where $S_{\sigma,\tau}\times T_{\sigma,\tau}$ is the rectangle containing
$(\sigma,\tau)$.

######  Remark 8.3.8.

The $\delta$-approximate rectangle substitutes property is a relaxation of the
rectangle substitutes property, in the sense that the two are equivalent if
$\delta=0$. To see this, first observe that if $\mathcal{I}$ satisfies
rectangle substitutes, then it satisfies Equation 8.6 with $\delta=0$
pointwise across all $S_{\sigma,\tau},T_{\sigma,\tau}$, and thus in
expectation. In the other direction, suppose that $\mathcal{I}$ satisfies
$0$-approximate rectangle substitutes. Let
$S\subseteq\mathcal{S},T\subseteq\mathcal{T}$ and consider the partition of
$\mathcal{I}$ into rectangles that contains $S\times T$ and, separately, every
other signal pair $(\sigma,\tau)$ in its own rectangle. For this partition,
Equation 8.6 reduces precisely to Equation 8.2 (the rectangle substitutes
condition for $S$ and $T$).

Theorem 8.3.1 generalizes to approximate rectangle substitutes as follows.

######  Theorem 8.3.9.

Let $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information
structure that satisfies $\delta$-approximate rectangle substitutes. For any
communication protocol that causes Alice and Bob to $\epsilon$-agree on
$\mathcal{I}$, Alice and Bob are $(10\epsilon^{1/3}+\delta)$-accurate after
the protocol terminates.

###### Proof.

We first observe that Lemma 8.3.2 can be modified as follows.

######  Lemma 8.3.10.

Let $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information
structure that satisfies $\delta$-approximate rectangle substitutes. Let
$\epsilon=\mathbb{E}\left[(\mu_{\sigma}-\mu_{\tau})^{2}\right]$. Then

$\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{\tau})^{2}\right]\leq
6\epsilon^{1/3}+\delta.$

The proof of Lemma 8.3.10 is exactly the same as that of Lemma 8.3.2, except
that Equation 8.3 includes an additive $\delta$ term on the left-hand side:

$\mathbb{E}\left[(\mu_{\sigma}-\mu_{S^{(k(\sigma))}})^{2}\right]+\delta\geq\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S^{(k(\sigma))}\tau})^{2}\right].$

This modified inequality follows immediately from the $\delta$-approximate
rectangle substitutes condition, noting that one partition of
$\mathcal{S}\times\mathcal{T}$ into rectangles is
$\\{S_{1}\times\mathcal{T},\dots,S_{N}\times\mathcal{T}\\}$. The extra
$\delta$ term produces the $\delta$ term in the lemma statement.

To prove the theorem, let $S$ be the set of possible signals of Alice at the
end of the protocol which are consistent with the protocol transcript, and
define $T$ likewise for Bob. Let $\delta_{ST}$ be the minimum $\delta$ such
that $S\times T$ satisfies $\delta$-approximate rectangle substitutes. Note
that $\mathbb{E}_{S,T}\left[\delta_{ST}\right]\leq\delta$: otherwise, by
taking the union over the worst-case partitions for each $S,T$ we would
exhibit a partition of $\mathcal{S}\times\mathcal{T}$ into rectangles that
would violate the $\delta$-approximate rectangle substitutes property.
Therefore we have

$\displaystyle\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\right]$
$\displaystyle=\mathbb{E}_{S,T}\left[\mathbb{E}\left[(\mu_{\sigma\tau}-\mu_{S\tau})^{2}\mid
S,T\right]\right]$
$\displaystyle\leq\mathbb{E}_{S,T}\left[6\left(\mathbb{E}\left[(\mu_{\sigma
T}-\mu_{S\tau})^{2}\mid S,T\right]\right)^{1/3}+\delta_{ST}\right]$
$\displaystyle\leq 6\mathbb{E}_{S,T}\left[\mathbb{E}\left[(\mu_{\sigma
T}-\mu_{S\tau})^{2}\mid S,T\right]\right]^{1/3}+\delta$
$\displaystyle=6\mathbb{E}\left[(\mu_{\sigma
T}-\mu_{S\tau})^{2}\right]^{1/3}+\delta=6(4\epsilon)^{1/3}+\delta\leq
10\epsilon^{1/3}+\delta.$

As in the proof of Theorem 8.3.1, the second step follows by applying Lemma
8.3.2 to the information structure $\mathcal{I}$ restricted to $S\times T$. ∎

###  8.4 Results for other divergence measures

Squared distance is a compelling error measure because it elicits the mean.
That is, if you wish to estimate a random variable $Y$ and will be penalized
according to the squared distance between $Y$ and your estimate, the strategy
that minimizes your expected penalty is to report the expected value of $Y$
(conditional on the information you have). This is in contrast to e.g.
absolute distance as an error measure, which would instead elicit the median
of your distribution. The class of error measures that elicit the mean is
precisely the class of Bregman divergences, which we introduced in Section
2.1.3. (See Proposition 2.1.8.)

In this section, our main result is a generalization of Theorem 8.3.1 to
(almost) arbitrary Bregman divergences (see e.g. Theorem 8.4.11).
Additionally, we provide a generalization of Aaronson’s discretized protocol
to arbitrary Bregman divergences (Theorem 8.4.8).

####  8.4.1 Preliminaries on Bregman divergences

Recall from Section 2.1.3 the definition of Bregman divergence: See 2.1.7

In this chapter, we are dealing with scalar quantities, so $n=1$ and in
particular $\mathcal{D}=[0,1]$. So for us, the _Bregman divergence_ from $y$
to $x$ is

$D_{G}(y\parallel x):=G(y)-G(x)-(y-x)G^{\prime}(x).$

Recall that the Bregman divergence with respect to $G(x)=x^{2}$ is precisely
the squared distance. Another common Bregman divergence is the KL divergence,
which corresponds to $G(x)=x\log x+(1-x)\log(1-x)$, the negative of the binary
entropy function.

We generalize relevant notions such as agreement and accuracy to arbitrary
Bregman divergences as follows. In the definitions below,
$G:[0,1]\to\mathbb{R}$ is a differentiable, strictly convex function.

######  Definition 8.4.1.

Let $a$ be Alice’s expectation. Alice is _$\epsilon$ -accurate_ if
$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel a)\right]\leq\epsilon$, and
likewise for Bob.121212We discuss our choice of the order of these two
arguments (i.e. why we do not instead consider the expectation of
$D_{G}(a\parallel\mu_{\sigma\tau})$) in Appendix D.4.

We now define $\epsilon$-agreement, and to do so we first define the _Jensen-
Bregman divergence_.

######  Definition 8.4.2.

For $a,b\in[0,1]$, the _Jensen-Bregman divergence_ between $a$ and $b$ with
respect to $G$ is

$\text{JB}_{G}(a,b):=\frac{1}{2}\left(D_{G}\left(a\parallel\frac{a+b}{2}\right)+D_{G}\left(b\parallel\frac{a+b}{2}\right)\right)=\frac{G(a)+G(b)}{2}-G\left(\frac{a+b}{2}\right).$

The validity of the second equality can be easily derived from the definition
of Bregman divergence. Note that the Jensen-Bregman divergence, unlike the
Bregman divergence, is symmetric in its arguments. The Jensen-Bregman
divergence is a lower bound on the average Bregman divergence from Alice and
Bob to any other point (see Proposition D.3.1 (i)).

######  Definition 8.4.3.

Let $a$ and $b$ be Alice’s and Bob’s expectations, respectively. Alice and Bob
_$\epsilon$ -agree_ with respect to $G$ if $\text{JB}_{G}(a,b)\leq\epsilon$.

In Appendix D.4 we discuss alternative definitions of agreement and accuracy.
The upshot of this discussion is that our definition of agreement is the
_weakest_ reasonable one, and our definition of accuracy is the _strongest_
reasonable one. This means that the main result of this section – that under a
wide class of Bregman divergence, agreement implies accuracy – is quite
powerful: it starts with a weak premise and proves a strong conclusion.

######  Definition 8.4.4.

Given an information structure $\mathcal{I}$, a communication protocol _causes
Alice and Bob to $\epsilon$-agree_ on $\mathcal{I}$ with respect to $G$ if
Alice and Bob $\epsilon$-agree with respect to $G$ at the end of the protocol.
A communication protocol is an _$\epsilon$ -agreement protocol_ with respect
to $G$ if the protocol causes Alice and Bob to $\epsilon$-agree with respect
to $G$ on every information structure.

We also generalize the notion of rectangle substitutes to this domain,
following [223], which explored notions of substitutes for arbitrary Bregman
divergences.

######  Definition 8.4.5.

Let $G:[0,1]\to\mathbb{R}$ be a differentiable, strictly convex function. An
information structure $\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$
satisfies rectangle substitutes with respect to $G$ if for every
$S\subseteq\mathcal{S},T\subseteq\mathcal{T}$, we have

$\mathbb{E}\left[D_{G}(Y\parallel\mu_{S\tau})\mid
S,T\right]-\mathbb{E}\left[D_{G}(Y\parallel\mu_{\sigma\tau})\mid
S,T\right]\leq\mathbb{E}\left[D_{G}(Y\parallel\mu_{ST})\mid
S,T\right]-\mathbb{E}\left[D_{G}(Y\parallel\mu_{\sigma T})\mid S,T\right].$

[223] explore the notion of weak substitutes with respect to arbitrary convex
functions $G$ as well; just as before, $\mathcal{I}$ is said to satisfy the
weak substitutes condition if the above inequality holds for $S=\mathcal{S}$
and $T=\mathcal{T}$. The authors additionally explore in detail the weak
substitutes condition with respect to negative entropy, i.e. for $D_{G}$ equal
to the KL divergence. They show that if Alice and Bob have independent signals
conditioned on $Y$, then the information structure satisfies weak substitutes
with respect to this $G$. In fact, any such information structure also
satisfies rectangle substitutes, because an information structure with
conditionally independent signals retains the conditional independence when
restricted to any sub-rectangle. The rectangle substitutes condition thus
covers the specific case of conditionally independent signals under which
[279] prove their accuracy result. On the other hand, the greater generality
of our setting necessitates a different proof strategy.

Recall from Section 2.3.3 that the Pythagorean theorem generalizes to
arbitrary Bregman divergences: See 2.3.12 (In this chapter we are specifically
interested in real-valued random variables, i.e. we take $n=1$.) Just as we
did with squared error, this general Pythagorean theorem allows us to rewrite
the rectangle substitutes condition for Bregman divergences.

######  Remark 8.4.6.

An information structure $\mathcal{I}$ satisfies rectangle substitutes with
respect to $G$ if and only if for all
$S\subseteq\mathcal{S},T\subseteq\mathcal{T}$ we have

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{S\tau})\mid
S,T\right]\leq\mathbb{E}\left[D_{G}(\mu_{\sigma T}\parallel\mu_{ST})\mid
S,T\right].$ (8.7)

Given the interpretation of Bregman divergences as measures of error, we can
interpret the left side as Bob’s expected error in predicting the truth while
the right side is Charlie’s expected error when predicting Alice’s expectation
(with Charlie as defined in Section 8.2.2). Both sides measure a prediction
error due to not having Alice’s signal, but from different starting points.

####  8.4.2 Generalizing the discretized protocol

In Section 8.4.4, we will show that under some weak conditions, protocols that
cause Alice and Bob to agree with respect to $G$ also cause Alice and Bob to
be accurate with respect to $G$. However, this raises an interesting question:
are there protocols that cause Alice and Bob to agree with respect to $G$? In
particular, we are interested in natural expectation-sharing protocols.
Aaronson’s discretized protocol is specific to $G(x)=x^{2}$, and it is not
immediately obvious how to generalize it. We present the following
generalization.

######  Definition 8.4.7.

Let $G$ be a differentiable, strictly convex function, and let
$M:=\max_{x}G(x)-\min_{x}G(x)$. Choose $\epsilon>0$. In the _discretized
protocol with respect to $G$ with parameter $\epsilon$,_ on her turn (at time
$t$), Alice sends “medium” if $D_{G}(\mu_{\sigma
T_{t-1}}\parallel\mu_{S_{t-1}T_{t-1}})<\frac{\epsilon}{2}$, and otherwise
either “low” or “high”, depending on whether $\mu_{\sigma T_{t}}$ is smaller
or larger (respectively) than $\mu_{S_{t}T_{t}}$. Bob acts analogously on his
turn. At the start of the protocol, Alice and Bob use the information
structure to independently compute the time
$t_{\text{end}}\leq\frac{24M(4M+\epsilon)}{\epsilon^{2}}$ that minimizes
$\mathbb{E}\left[D_{G}(\mu_{\sigma
T_{t_{\text{end}}}}\parallel\mu_{S_{t_{\text{end}}}\tau})\right]$. The
protocol ends at this time.

######  Theorem 8.4.8.

The discretized protocol with respect to $G$ with parameter $\epsilon$ is an
$\epsilon$-agreement protocol with respect to $G$ that requires
$O\left(\frac{M(M+\epsilon)}{\epsilon^{2}}\right)$ bits of communication.

Our proof draws inspiration from Aaronson’s proof of the discretized protocol,
but has significant differences. The key idea is to keep track of the
monovariant $\mathbb{E}\left[D_{G}(Y\parallel\mu_{S_{t}T_{t}})\right]$. This
is Charlie’s expected error (as measured by the Bregman divergence from the
correct answer $Y$) after time step $t$ – recall that Charlie is our name for
a third-party observer of the protocol. Note that this quantity is at most $M$
and at least $0$. Hence, if we show that the quantity decreases by at least
some value $\beta$ every time Alice and Bob do not $\epsilon$-agree, then we
will have shown that Alice and Bob must $\epsilon$-agree within
$\frac{\beta}{M}$ time steps. We defer the proof to Appendix D.3.

####  8.4.3 Approximate triangle inequality

Our accuracy results in Section 8.4.4 will hold for a class of Jensen-Bregman
divergences that satisfy an approximate version of the triangle inequality.
Specifically, we will require $\text{JB}_{G}$ to satisfy the following _$c$
-approximate triangle inequality_ for some $c>0$.

######  Definition 8.4.9.

Given a differentiable, strictly convex function $G:[0,1]\to\mathbb{R}$ and a
positive number $c$, we say that $\text{JB}_{G}(\cdot,\cdot)$ satisfies the
_$c$ -approximate triangle inequality_ if for all $a,b,x\in[0,1]$ we have

$\text{JB}_{G}(a,x)+\text{JB}_{G}(x,b)\geq c\text{JB}_{G}(a,b).$

It is possible to construct functions $G$ such that there is no positive $c$
for which $\text{JB}_{G}$ satisfies the $c$-approximate triangle inequality.
However, $\text{JB}_{G}$ satisfies the $c$-approximate triangle inequality for
some positive $c$ for essentially all natural choices of $G$.

######  Proposition 8.4.10.

Let $G:[0,1]\to\mathbb{R}$ be a differentiable, strictly convex function.

  1. (i)

If $\sqrt{\text{JB}_{G}(\cdot,\cdot)}$ satisfies the triangle inequality, then
$\text{JB}_{G}$ satisfies the $\frac{1}{2}$-approximate triangle inequality.

  2. (ii)

If $G(x)=x^{2}$ (i.e. $D_{G}$ is squared distance) or if $G(x)=x\log
x+(1-x)\log(1-x)$ (i.e. $D_{G}$ is KL divergence), then $\sqrt{\text{JB}_{G}}$
satisfies the triangle inequality (and so $\text{JB}_{G}$ satisfies the
$\frac{1}{2}$-approximate triangle inequality).

###### Proof.

Regarding Fact (i), suppose that $\sqrt{\text{JB}_{G}}$ satisfies the triangle
inequality. Then for all $a,b,x$ we have
$\sqrt{\text{JB}_{G}(a,x)}+\sqrt{\text{JB}_{G}(x,b)}\geq\sqrt{\text{JB}_{G}(a,b)}$.
Squaring both sides and observing that
$\text{JB}_{G}(a,x)+\text{JB}_{G}(x,b)\geq
2\sqrt{\text{JB}_{G}(a,x)\text{JB}_{G}(x,b)}$ completes the proof.

Fact (ii) is trivial for $G(x)=x^{2}$, since $\sqrt{\text{JB}_{G}}$ is the
absolute distance metric (times a constant factor). As for $G(x)=x\log
x+(1-x)\log(1-x)$, see [238]. ∎

The question of which convex functions $G$ have the property that
$\sqrt{\text{JB}_{G}}$ satisfies the triangle inequality has been explored in
previous work [184, 215].

####  8.4.4 Generalized agreement implies generalized accuracy

In all of the results in this subsection, we consider the following setting:
$G$ is a differentiable convex function; $c$ is a positive real number such
that $\text{JB}_{G}$ satisfies the $c$-approximate triangle inequality; and
$\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ is an information structure
that satisfies rectangle substitutes with respect to $G$.

We prove generalizations of Theorem 8.3.1, showing that under the rectangle
substitutes condition, if a protocol ends with Alice and Bob in approximate
agreement, then Alice and Bob are approximately accurate.

######  Theorem 8.4.11.

Assume that $G$ is symmetric about the line $x=\frac{1}{2}$. For any
communication protocol that causes Alice and Bob to $\epsilon$-agree on
$\mathcal{I}$, and for any $\beta\geq\frac{2}{c}\epsilon$, Alice and Bob are

$\left(\frac{8}{c^{2}}\beta+16\left(G(0)-G\left(\left(\frac{\epsilon}{\beta}\right)^{1/(1-\log_{2}c)}\right)\right)\right)\text{-accurate}$

with respect to $G$ after the protocol terminates.

This result is not our most general, as it assumes that $G$ is symmetric, but
this assumption likely holds for most use cases. To apply the result
optimally, one must first optimize $\beta$ as a function of $G$. For example,
setting $\beta=\epsilon^{r/(r+1-\log_{2}c)}$ (with $r$ defined below) gives us
the following corollary:131313Corollary 8.4.12 as stated (without the symmetry
assumption) is actually a corollary of Theorem 8.4.15.

######  Corollary 8.4.12.

Assume that $G(0)-G(x),G(1)-G(1-x)\leq O(x^{r})$. For any communication
protocol that causes Alice and Bob to $\epsilon$-agree on $\mathcal{I}$, Alice
and Bob are $O\left(\epsilon^{r/(r+1-\log_{2}c)}\right)$-accurate after the
protocol terminates, where the constant hidden by $O(\cdot)$ depends on $G$.

######  Remark 8.4.13.

Concretely, if $G^{\prime}$ is bounded then we can choose $r=1$, in which case
our bound simplifies to $O\left(\epsilon^{1/(2-\log_{2}c)}\right)$. If instead
we assume that $c=\frac{1}{2}$ (as is the case if
$\sqrt{\text{JB}_{G}(\cdot,\cdot)}$ is a metric), then the bound is
$O\left(\epsilon^{r/(r+2)}\right)$. If both of these are true, as is the case
for $G(x)=x^{2}$, then the bound is $O(\epsilon^{1/3})$, which recovers our
result in Theorem 8.3.1.

For $G$ equal to the negative of Shannon entropy (i.e. the $G$ for which
$D_{G}$ is KL divergence), setting $\beta=\epsilon^{1/3}(\log
1/\epsilon)^{2/3}$ in Theorem 8.4.11 gives us the following corollary.

######  Corollary 8.4.14.

If $G(x)=x\log x+(1-x)\log(1-x)$, then for any communication protocol that
causes Alice and Bob to $\epsilon$-agree on $\mathcal{I}$, Alice and Bob are
$O(\epsilon^{1/3}(\log 1/\epsilon)^{2/3})$-accurate after the protocol
terminates.

Theorem 8.4.11 follows from our most general result about agreement implying
accuracy:

######  Theorem 8.4.15.

Let $\tilde{G}(x):=\max_{a,b:\left\lvert a-b\right\rvert\leq x}(G(a)-G(b))$ be
the maximum possible difference in $G$-values of two points that differ by at
most $x$, and let $\tilde{G}^{*}(x)$ be the concave envelope of $\tilde{G}$,
i.e.

$\tilde{G}^{*}(x):=\max_{0\leq a,b,w\leq
1:wa+(1-w)b=x}w\tilde{G}(a)+(1-w)\tilde{G}(b).$

For any communication protocol that causes Alice and Bob to $\epsilon$-agree
on $\mathcal{I}$, and for any $\beta>0$, Alice and Bob are

$\left(\frac{8}{c^{2}}\beta+16\tilde{G}^{*}\left(\left(\frac{\epsilon}{\beta}\right)^{1/(1-\log_{2}c)}\right)\right)\text{-accurate}$

after the protocol terminates.

###### Proof.

To prove Theorem 8.4.15, it suffices to prove the following lemma.

######  Lemma 8.4.16.

Let $G$ be a differentiable convex function on $[0,1]$ and $c\in(0,1)$ be such
that $\text{JB}_{G}$ satisfies the $c$-approximate triangle inequality. Let
$\mathcal{I}=(\Omega,\mathbb{P},\sigma,\tau,Y)$ be an information structure
that satisfies rectangle substitutes with respect to $G$. Let
$\epsilon=\mathbb{E}\left[\text{JB}_{G}(\mu_{\sigma}\parallel\mu_{\tau})\right]$.
Then for any $\beta>0$, we have

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{\tau})\right]\leq\frac{8}{c^{2}}\beta+16\tilde{G}^{*}\left(\left(\frac{\epsilon}{\beta}\right)^{1/(1-\log_{2}c)}\right).$

Let us first prove Theorem 8.4.15 assuming Lemma 8.4.16 is true.

Consider any protocol that causes Alice and Bob to $\epsilon$-agree on
$\mathcal{I}$. Let $S$ be the set of possible signals of Alice at the end of
the protocol which are consistent with the protocol transcript, and define $T$
likewise for Bob.

Let $\epsilon_{ST}=\mathbb{E}\left[\text{JB}_{G}(\mu_{\sigma
T},\mu_{S\tau})\mid S,T\right]$. Note that

$\mathbb{E}_{S,T}\left[\epsilon_{ST}\right]=\mathbb{E}_{S,T}\left[\mathbb{E}\left[\text{JB}_{G}(\mu_{\sigma
T},\mu_{S\tau})\mid
S,T\right]\right]=\mathbb{E}\left[\text{JB}_{G}(\mu_{\sigma
T},\mu_{S\tau})\right]\leq\epsilon.$

Therefore, for any $\beta>0$ we have

$\displaystyle\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{S\tau})\right]$
$\displaystyle\leq\mathbb{E}_{S,T}\left[\frac{8}{c^{2}}\beta+16\tilde{G}^{*}\left(\left(\frac{\epsilon_{ST}}{\beta}\right)^{1/(1-\log_{2}c)}\right)\right]$
$\displaystyle\leq\frac{8}{c^{2}}\beta+16\tilde{G}^{*}\left(\mathbb{E}_{S,T}\left[\left(\frac{\epsilon_{ST}}{\beta}\right)^{1/(1-\log_{2}c)}\right]\right)$
$\displaystyle\leq\frac{8}{c^{2}}\beta+16\tilde{G}^{*}\left({\left(\frac{\mathbb{E}_{S,T}\left[\epsilon_{ST}\right]}{\beta}\right)^{1/(1-\log_{2}c)}}\right)$
$\displaystyle\leq\frac{8}{c^{2}}\beta+16\tilde{G}^{*}\left(\left(\frac{\epsilon}{\beta}\right)^{1/(1-\log_{2}c)}\right).$

In the first step, we apply Lemma 8.4.16 to the information structure
$\mathcal{I}$ restricted to $S\times T$ – that is, to
$\mathcal{I}^{\prime}=(\Omega^{\prime},\mathbb{P}^{\prime},S,T,Y)$, where
$\Omega^{\prime}=\\{\omega\in\Omega:\sigma\in S,\tau\in T\\}$ and
$\mathbb{P}^{\prime}[\omega]=\mathbb{P}[\omega\mid\sigma\in S,\tau\in T]$. The
next two steps follow by the convexity of $\tilde{G}^{*}$ and
$x^{1/(1-\log_{2}c)}$, respectively. ∎

The basic outline of the proof of Lemma 8.4.16 is similar to that of Lemma
8.3.2. Once again, we partition $[0,1]$ into $N$ intervals. Analogously to
Equation 8.4, and with $S^{(k(\sigma))}$ defined analogously, we find that

$\mathbb{E}\left[D_{G}(\mu_{\sigma\tau}\parallel\mu_{\tau})\right]\leq\mathbb{E}\left[D_{G}(\mu_{\sigma}\parallel\mu_{S^{(k(\sigma))}})\right]+\mathbb{E}\left[D_{G}(\mu_{S^{(k(\sigma))}\tau}\parallel\mu_{\tau})\right].$

As before, we wish to upper bound each summand. However, the fact that the
Bregman divergence is now arbitrary introduces complications. First, it is no
longer the case that we can directly relate the length of an interval to the
Bregman divergence between its endpoints. Second, we consider functions $G$
that become infinitely steep near $0$ and $1$ (such as the negative of Shannon
entropy), which makes matters more challenging. This means that we need to be
more careful when partitioning $[0,1]$ into $N$ intervals: see Algorithm 3 for
our new approach. Additionally, bounding the second summand involves reasoning
carefully about the behavior of the function $G$, which is responsible for the
introduction of $\tilde{G}^{*}$ into the lemma statement. We defer the full
proof of Lemma 8.4.16 to Appendix D.3.

###  8.5 Connections to markets

In this work, we established a natural condition on information structures,
_rectangle substitutes_ , under which any agreement protocol results in
accurate beliefs. _Expectation-sharing_ protocols, where Alice and Bob take
turns stating their current expected value (or discretizations thereof) are a
particularly natural class of agreement protocols.

Expectation-sharing protocols have close connections to financial markets. In
markets, the actions of traders reveal partial information about their
believed value for an asset, i.e., their expectation. Specifically, a trader’s
decision about whether to buy or sell, and how much, can be viewed as
revealing a discretization of this expectation. In many theoretical models of
markets (e.g. [316]) traders eventually reach agreement. The intuition behind
this phenomenon is that a trader who disagrees with the price leaves money on
the table by refusing to trade. Our work thus provides a lens into a well-
studied question:141414This is related to the _efficient market hypothesis_ ,
the problem of when market prices reflect all available information, which
traces back at least to [241] and [269]. Modern models of financial markets
are often based on [282]; see e.g. [316] and references therein for further
information. when are market prices accurate? Our results can be viewed as
generalizing and conceptually supporting the result presented in [279], under
which convergence in a popular prediction market design implies full
information revelation in the prices.

An important caveat, however, is that traders behave strategically, and may
not disclose their true expected value. For example, a trader may choose to
withhold information until a later point when doing so would be more
profitable. Therefore, to interpret the actions of traders as revealing
discretized versions of their expected value, one first has to understand the
Bayes-Nash equilibria of the market. [223] study conditions under which
traders are incentivized to reveal all of their information on their first
trading opportunity. They call a market equilibrium _all-rush_ if every trader
is incentivized to reveal their information immediately. Their main result,
roughly speaking, is that there is an all-rush equilibrium if and only if the
information structure satisfies _strong substitutes_ – another strengthening
of their weak substitutes condition. This result is specific to settings in
which traders have the option to reveal all of their information on their turn
– a setting that would be considered trivial from the standpoint of
communication theory.

An exciting question for further study is therefore: under what information
structure conditions and market settings is it a Bayes-Nash equilibrium to
follow an agreement protocol that leads to accurate beliefs? In other words,
what conditions give not only that agreement implies accuracy, but also that
the market incentivizes participants to _follow_ the protocol? Together with
[223], our work suggests that certain substitutes-like conditions could
suffice.

## Deductive circuit estimation

_This chapter presents work done at the Alignment Research Center, in
collaboration with Paul Christiano, Jacob Hilton, Václav Rozhoň, and Mark Xu.
It builds on the ideas of “Formalizing the Presumption of Independence”[227].
The chapter assumes basic familiarity with theoretical computer science. The
idea of forecast aggregation in the context of experts holding partial
information – especially as in Section 2.4 – may be useful for context._

_Summary:_ In this chapter, we turn our attention to estimating formal
mathematical expressions – such as the acceptance probability of a boolean
circuit – using deductive arguments. Much as it is possible to be uncertain
about whether it will rain next week due to missing information or bounded
computational resources, one can also be uncertain about the fraction of
inputs on which a boolean circuit will output $1$. While there are simple
_inductive_ methods for estimating this number, such as by running the circuit
on a random sample of inputs, in this chapter we are interested in _deductive_
estimation. In other words, we are interested in designing an algorithm that
takes as input formal arguments and observations about the structure of a
circuit, and uses those observations in order to estimate the circuit’s
acceptance probability. Deductive estimates have the advantage that they may
give insight about the _reasons why_ a circuit tends to accept certain classes
of inputs.

Deductive estimates of mathematical quantities abound in fields such as number
theory, theoretical computer science, and discrete mathematics, but there is
little understanding of the rules that govern such estimation. Much as there
is a formal definition of a mathematical proof and an algorithm that checks
proofs for validity, there may be a formal definition of a valid deductive
argument and an algorithm that uses such arguments to estimate mathematical
quantities.

In this chapter, we search for such a formalization, focusing our attention on
deductively estimating the acceptance probabilities of boolean circuits. We
define two properties – _linearity_ and _respect for proofs_ – that a
deductive estimation algorithm ought to satisfy, and then provide an efficient
algorithm that satisfies those properties. We then show a negative result:
that no efficient algorithm can satisfy linearity, respect for proofs, and
another property that we call _0-1 boundedness,_ assuming that $P\neq PP$. We
discuss additional desirable properties for a deductive estimation algorithm
and then conclude with a discussion of potential applications to detecting
anomalous neural network behavior.

More so than any previous chapter, this one shows a work in progress. It
raises more questions than it answers, and some of the raised questions are
not formally stated. However, the question of whether deductive estimation can
be formalized seems like a fundamental one, and further progress in this
direction may have important applications for building advanced AI systems
safely.

###  9.1 Introduction

Suppose we wish to estimate the acceptance probability $p(C)$ of a boolean
circuit $C:\\{0,1\\}^{n}\to\\{0,1\\}$ on a uniformly random input – that is,
the fraction of inputs $x$ for which $C(x)=1$. We can contrast two different
types of approaches to such an estimation problem: _inductive_ approaches and
_deductive_ approaches.

By an _inductive_ approach, we mean an approach based on observing the input-
output behavior of $C$ on some inputs. For example, one inductive approach is
to sample inputs to $C$ uniformly at random and observe the fraction of inputs
that $C$ accepts (outputs $1$ on).111We consider pseudorandom sampling to also
be inductive. The use of randomness is not required for an argument to be
considered inductive. Such an estimation procedure is very effective, at least
in terms of estimating $p(C)$ with a small additive error. However, it does
not provide any insight about _why_ $C$’s acceptance probability is what it
is.

By a _deductive_ approach, we mean an approach that uses structural
observations about $C$ in order to estimate $p(C)$. We call such structural
observations _deductive arguments._ 222We use the term “deductive argument”
instead of the term “heuristic argument” (as used in e.g. [227]) to stress the
difference with inductive arguments (which we do not consider in this chapter)
and to emphasize that a proof is a special type of deductive argument. While
an inductive approaches would generally treat a circuit as a black box and
estimate its acceptance probability using input-output behavior, deductive
arguments treat circuits as white boxes. Let us illustrate with a few
examples.

######  Example 9.1.1.

Suppose that $C$ takes as input a triple $(a,b,c)$ of positive integers,
computes $\max(a,b)$ and $\max(b,c)$, and accepts if they are equal. A
deductive argument about $p(C)$ might point out that if $b$ is the largest of
the three integers, then $\max(a,b)=b=\max(b,c)$ and so $C$ will accept, and
that this happens with probability roughly $\frac{1}{3}$.

######  Example 9.1.2.

Suppose that $C(x)$ computes $\text{SHA-256}(x)$ (the output of SHA-256 is a
256-bit string) and accepts if the first 128 bits (interpreted as an integer)
are larger than the last 128 bits. One can make a deductive argument about
$p(C)$ by making repeated use of the _presumption of independence_ [227]. In
particular, the SHA-256 circuit consists of components (such as the majority
circuit, or addition modulo $2^{32}$) that produce uniformly random outputs on
independent, uniformly random inputs. Thus, a deductive argument that
repeatedly presumes that the inputs to each component are independent
concludes that the output of SHA-256 consists of independent, uniformly random
bits. It would then follow that the probability that the first 128 bits of the
output are larger than the last 128 bits is $\frac{1}{2}$.

######  Example 9.1.3.

Suppose that $C$ is a particular CNF with $k$ clauses of three literals each.
A deductive argument about $p(C)$ might point out that $C$ is a CNF with $k$
clauses of three literals each, and that on average, CNFs with this structure
accept $\left(\frac{7}{8}\right)^{k}$ fraction of inputs. A more sophisticated
argument might point out particular structural patterns in $C$ (e.g. that the
variable $x_{1}$ appears with positive sign in every clause) and reason about
the average acceptance probability of CNFs with that structure.

######  Example 9.1.4.

Suppose that $C$ takes as input an integer $k$ between $e^{100}$ and $e^{101}$
and accepts if $k$ and $k+2$ are both prime. A deductive argument about $p(C)$
might point out that the density of primes in this range is roughly $1\%$, so
if we presume that the event that $k$ is prime and the event that $k+2$ is
prime are independent, then we get an estimate of $0.01\%$. A more
sophisticated argument might take this one step further by pointing out that
if $k$ is prime, then $k$ is odd, so $k+2$ is odd, which makes $k+2$ more
likely to be prime (by a factor of $2$), suggesting an estimate of $0.02\%$. A
yet more sophisticated argument might point out that additionally, if $k$ is
prime, then $k$ is not divisible by $3$, which makes $k+2$ _more_ likely to be
divisible by $3$, which reduces the chance that $k+2$ is prime, and would make
similar arguments for divisibility by $5$, $7$, and so on.

In a sense, deductive arguments generalize proofs. A formal proof about the
value of $p(C)$ is a type of deductive argument, but in many cases it is
infeasible to prove even basic facts about a circuit’s acceptance probability.
In Example 9.1.2, for instance, there is likely no short proof that $p(C)$ is
between $\frac{1}{3}$ and $\frac{2}{3}$, but there is a very simple deductive
argument. Deductive arguments let us draw conclusions based on circuits’
structural properties in many cases where proofs do not.

Inductive approaches to circuit estimation hold some obvious advantages over
deductive ones. First, they are fast and straightforward. Second, they have
strong accuracy guarantees: by sampling random inputs, one can efficiently
estimate $p(C)$ with a small additive error with high probability. By
comparison, a deductive estimate can be incorrect (for example, the naïve
argument that gave the $0.01\%$ estimate in Example 9.1.4 was substantially
wrong). So why bother with deductive estimates?

One answer is that deductive estimation may be helpful in situations where
sampling-based approaches will fail. For example, suppose we wish to estimate
the acceptance probability of a CNF $C$ that has a low acceptance probability,
with a small multiplicative error. Sampling inputs will likely fail to find
any satisfying assignments. On the other hand, one could hope to be able to
reason deductively about $C$’s acceptance probability if given deductive
arguments based on $C$’s structure.

More importantly, however, deductive arguments can give us a _mechanistic
understanding_ of a circuit and provide insight about _why_ the circuit has a
certain acceptance probability. Such understanding allows us to answer
questions like: does $C$ accept inputs $\mathbf{x}$ and $\mathbf{y}$ “for the
same reason” or “for different reasons”? In Example 9.1.1, $C$ might accept an
input because $b$ is larger than both $a$ and $c$, or because $a=c$. Deductive
arguments can allow us to draw such distinctions; inductive arguments do not.
Gaining such a mechanistic understanding is an important motivation for
exploring deductive circuit estimation.

The purpose of this line of work is to create a deductive estimation
algorithm. A _deductive estimation algorithm_ takes as input a boolean
circuit,333We are also interested in the more general problem of estimating
the expected outputs of arithmetic circuits and of computer programs more
generally, but in this chapter we focus on boolean circuits. Boolean circuits
are a special case that may capture the core difficulties of the more general
problem. Further, boolean circuits have a canonical choice for the
distribution of inputs (uniformly random bit strings), and some of our
discussion (e.g. our definition of linearity in Section 9.3) is simplified in
the case of boolean cirucits. together with a list of deductive arguments
about the circuit, and outputs an estimate of the circuit’s acceptance
probability based on the provided arguments. Creating such an algorithm
requires surmounting several challenges. First, it is necessary to specify a
formal language in which deductive arguments may be stated; deductive
arguments given as input to the estimation algorithm will be written in this
formal language. Second, desiderata for the algorithm should be defined: what
properties should a deductive estimation algorithm satisfy? Finally, the third
challenge is to create an algorithm that satisfies those properties.

An analogy to formal proof verification may be instructive. The central task
of proof verification is the (solved) problem of finding a verification
algorithm that, given a mathematical statement and an alleged proof of the
statement, verifies the proof. In our setting, the circuit (whose acceptance
probability we want to estimate) is analogous to the mathematical statement,
and the list of deductive arguments is analogous to the proof. Table 9.1
describes the analogy in more detail.

Deductive circuit estimation | Formal proof verification
---|---
Deductive estimation algorithm | Proof verifier
Boolean circuit | Formal mathematical statement
List of deductive arguments | Alleged proof of statement
Formal language for deductive arguments | Formal language for proofs
Desiderata for estimation algorithm | Soundness and completeness
Algorithm’s estimate of circuit | Proof verifier’s output (accept or reject)
Table 9.1: We are interested in developing a deductive estimation algorithm
for boolean circuits. There are similarities between this task and the
(solved) task of developing an algorithm for verifying formal proofs of
mathematical statements. This table illustrates the analogy. Importantly, the
purpose of a deductive estimation algorithm is to incorporate the deductive
arguments that it has been given as input, rather than to generate its own
arguments. The output of a deductive estimation algorithm is only as
sophisticated as the arguments that it has been given.

In Section 9.2, we begin with a discussion of deductive circuit estimation via
linear regression. That is, we will be interested in producing a linear
estimator for a class of circuits in terms of a list of features. We
illustrate this approach with an example of CNF estimation. The purpose of
this section is to provide an example of what deductive arguments for circuit
estimation might look like, and how a deductive estimation algorithm might
incorporate those arguments into an estimate of the acceptance probability of
a circuit.

In Section 9.3, we examine the problem of deductive circuit estimation in more
generality, asking the question: what properties should a deductive estimation
algorithm satisfy? We introduce two properties – which we call _linearity_ and
_respect for proofs_ – and describe an algorithm that satisfies both
properties. Then, in Section 9.4, we discuss additional properties. We
introduce a basic property called _0-1 boundedness_ and show that it is
impossible to satisfy in addition to linearity and respect for proofs, unless
$P=PP$. We discuss two other properties – _iterated estimation_ and _pulling
out known factors_ – that it would be desirable to satisfy, and leave open the
question of whether they can be satisfied.

Finally, in Section 9.5, we conclude with a discussion of potential
applications to detecting anomalous behavior in neural networks.

####  9.1.1 Related work

The work most closely related to ours is [227], which posed the question of
whether it is possible to formalize the process of deductively estimating the
value of a mathematical expression, such as the expectation of a random
variable. The authors posited the _presumption of independence_ as an
underlying principle of deductive estimation: two random variables should be
presumed independent until an argument to the contrary is presented. Thus, a
deductive estimation algorithm might start by assuming that all sub-
expressions are independent, and then update its estimate after incorporating
knowledge about various dependencies. This chapter attacks the problem of
deductive estimation from a different perspective, but is a continuation of
that work.

There has not been much other prior work on formalizing deductive estimation.
Perhaps the closest is [343], which also posits that two quantities should be
presumed independent unless there is a good reason to the contrary, and uses
this principle to give a heuristic justification for the ABC conjecture from
number theory. Heuristic arguments for mathematical claims are common in
fields such as number theory, theoretical computer science, and discrete
mathematics. For example, [239] give a heuristic argument for the truth of
Fermat’s last theorem; [296] use heuristic methods to analyze random $k$-SAT
instances; and [231] heuristically estimate the frequencies of certain
patterns in Conway’s game of life. However, little prior work attempts to
formalize the rules governing such arguments.

[197, 198] are also closely related to our work. Barak asks whether it is
possible to construct an estimation algorithm for a given quantity that
appears reasonable to a broad class of observers. By contrast, in our framing,
“observers" are deductive arguments that are given as input. Our perspective
is in some ways less ambitious and in some ways more: on the one hand, we want
our estimate to appear reasonable to an observer (i.e. incorporate a deductive
argument) only if the observer is explicitly given as input; on the other
hand, this may allow us to consider a much wider range of possible observers.

More recently, [260] posited a _no-coincidence principle:_ “If an apparently
outrageous coincidence happens in mathematics, then there is a reason for it.”
In the language of this chapter, we might instead write: “If a circuit
exhibits a surprising behavior, then there is a short deductive argument that
explains the behavior.” (An example of a surprising behavior might be that the
acceptance probability of a circuit is much larger than a naïve estimate would
suggest.444Informally speaking: for a circuit that always outputs $1$, there
should be a deductive argument that makes it seem _plausible_ that the circuit
always outputs $1$. On the other hand, for most circuits that do not always
output $1$, no such deductive argument should exist. See [227, §C] for further
discussion.)

There is a significant literature on the problem of circuit estimation.
Inductive estimates are common, often under the name _approximate model
counting._ Beyond straightforward uniform sampling, there are more algorithms
based on more sophisticated methods such as Markov chain Monte Carlo [349]. If
given access to an NP oracle, hashing-based approaches can give strong
guarantees [357]. See [213] for a survey of this area. There has also been
work on derandomization-based deterministic algorithms for approximate DNF
counting [259].

There has also been extensive research into heuristic methods for the
satisfiability problem (see e.g. [264]). This work is similar in spirit to
ours, but our goal is different. Rather than finding particular heuristic
algorithms and validating them on particular instances, we are seeking a
unified theoretical framework for making estimates based on a very large class
of arguments.

###  9.2 Circuit estimation via linear regression

Often, families of circuits are easier to reason about than the individual
circuits they contain. For example, it may be difficult to compute the
acceptance probability of a given 3CNF with $k$ clauses, but it is easy to
compute the average acceptance probability of _all_ 3CNFs with $k$ clauses.
For this reason, estimating the acceptance probability of a circuit $C$ is
made easier by instead estimating the acceptance probabilities of _all_
circuits in a family that contains $C$.

Let us denote the average acceptance probability of a (finite) family of
boolean circuits $\mathscr{C}$ as $p(\mathscr{C})$. That is,
$p(\mathscr{C}):=\mathbb{E}_{C\sim\mathscr{C}}\left[p(C)\right]$. Consider a
circuit $C:\\{0,1\\}^{n}\to\\{0,1\\}$ for which $p(C)$ is difficult to