Agreement Implies Accuracy for Substitutable Signals

In [Aar05], Alice and Bob are said to agree if the squared distance 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 3 we present our first main result: under these definitions, if the information structure satisfies rectangle substitutes, 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 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 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.²²2The 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 4.11) 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 5 with a discussion of connections between agreement protocols and information revelation in financial markets, and discuss an interesting potential avenue for future work.

Our setting is related to but distinct from communication complexity. In that field (e.g. [RY20]), 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, [Aar05] 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 E.

Our introduction of the substitutes condition is inspired by its usefulness in prediction markets [CW16]. The “expectation-sharing” agreement protocols we study bear a strong similarity to dynamics of market prices. [Ost12] 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. We discuss these works and the connection of our work to markets in Section 5. Another similar definition of informational substitutes is used by [NR21] in the context of robust aggregation of forecasts.

Finally, we note that the “agreement protocols” we study are not related to key agreement protocols in cryptography, where the goal is for two communicating parties to jointly construct a shared string for cryptographic use.

We consider a set $\Omega$ of states of the world, with a probability distribution $\mathbb{P}$ over the world states. There are two experts, Alice and Bob. Alice learns the value of a random variable $\sigma:\Omega\to\mathcal{S}$; we call $\sigma$ Alice’s signal and $\mathcal{S}$ her signal set. Correspondingly, Bob learns the value of a random variable $\tau:\Omega\to\mathcal{T}$. These signals each convey partial information about the true state $\omega\in\Omega$. Alice and Bob are interested in a third random variable $Y:\Omega\to[0,1]$. We use the term information structure to refer to the tuple $\mathcal{I}:=(\Omega,\mathbb{P},\mathcal{S},\mathcal{T},Y)$.

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$. We also define $\mu_{\sigma}:=\mathbb{E}\left[Y\mid\sigma\right]$ and $\mu_{\tau}:=\mathbb{E}\left[Y\mod\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.

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 4.

Our setting follows [Aar05], 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. 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 transcript of the protocol at a time step $t$ (i.e. after $t$ messages have been sent) 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}$. 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.

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

Aaronson defines and analyzes two $\epsilon$-agreement protocols.³³3A minor difference to our framing is that [Aar05] 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 [Aar05] (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):

In general, we refer to Aaronson’s standard and discretized protocols as examples of expectation-sharing protocols. We will define other examples in Section 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 5.

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:

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. An extreme example is if $\sigma=\tau=X$ for any random variable $X$. Here $\sigma$ becomes useless upon learning $\tau$ and vice versa. In [CW16],⁴⁴4We recommend the ArXiv version for the most up-to-date introduction to informational substitutes. the authors discuss formalizations of several notions of informational substitutes. All of these notions capture “diminishing marginal value,” in the sense that, roughly speaking, the value of partial information is a submodular set function. The various definitions proposed by [CW16] only differ in how finely they allow decomposing $\sigma$ and $\tau$ to obtain a marginal unit. Our definition has the same format, but uses a decomposition inspired by information rectangles in communication complexity. Recall that we write $\mid S,T$ as shorthand for $\mid\sigma\in S,\tau\in T$.

We will show that under rectangle substitutes, if Alice and Bob approximately agree, then they are approximately accurate.

We will use the following fact throughout. We defer the proof to Appendix C, where we establish a more general version of this statement.

We use the phrase Pythagorean theorem in part because of its form, and in part because it is precisely the familiar Pythagorean theorem when the random variables are viewed as points in a Hilbert space⁶⁶6We do not make use of this abstraction in our work, but we refer the interested reader to [Šid57]. with inner product $\langle X,Y\rangle:=\mathbb{E}\left[XY\right]$.

Informally, $A$ is a random variable, $B$ is the expected value of $A$ conditional on some partial information, and $C$ is a random variable that only depends on this information. So the theorem applies when $B$ is a coarse estimate of $A$ and $C$ is at least as coarse as $B$, a scenario that often occurs in our setting.

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:

The crux of the argument is the following lemma.

The proof of Lemma 3.2 relies on the following claim. We defer the proof of Lemma 3.2 (and Claim 3.3) to Appendix B, and instead sketch the proofs here.

Intuitively, Claim 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.

We now sketch the proof of Lemma 3.2. To see why Claim 3.3 is relevant, recall that we wish to upper bound the expectation of $(\mu_{\sigma\tau}-\mu_{\tau})^{2}$. Let $S^{(k)}:=\{\sigma\in\mathcal{S}:x_{k-1}\leq\mu_{\sigma}<x_{k}\}$. 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].$$

By using the rectangle substitutes condition for $S=S^{(k)},T=\mathcal{T}$ for every $k$, we find 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].$$

(2)

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].$$

(3)

Claim 3.3 lets us argue that the first of these two terms is small (because $\mu_{\sigma}$ and $\mu_{S^{(k(\sigma))}}$ are always within $\frac{2}{N}$ of each other) and that the second term is also small (because conditioned on $\tau$, $k(\sigma)$ is known with high probability). We find that choosing $N=\epsilon^{1/6}$ gives us the bound in Lemma 3.2.

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

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

Corollary 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” [Aar05, §2.2]. Thus, while the main purpose of Theorem 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.

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 3.1 to information structures that almost satisfy the rectangle substitutes condition but do not quite. Let us formally define a notion of closeness to rectangle substitutes.

An intuitive formulation of Bregman divergence is that $D_{G}(y\parallel x)$ can be found by drawing the line tangent to $G$ at $x$ and computing how far below the point $(y,G(y))$ this line passes. We illustrate this in Figure 1. Note that the Bregman divergence is not in general symmetric in its arguments; indeed, $G(x)=x^{2}$ is the only $G$ for which it is.

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 Shannon entropy.

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.

We 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. We now define $\epsilon$-agreement, and to do so we first define the Jensen-Bregman divergence.

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 C.1 (i)).

In Appendix D 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.

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

The Pythagorean theorem (Proposition 2.7) generalizes to arbitrary Bregman divergences:

Although the proof of this observation is fairly straightforward, to our knowledge Proposition 4.8 is original to this work. We provide a proof in Appendix C. Just as we did with squared error, this general Pythagorean theorem allows us to rewrite the rectangle substitutes condition for Bregman divergences.

Later in this work, 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.

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 C.

Our results 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$.

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$.

The question of when $\sqrt{\text{JB}_{G}}$ satisfies the triangle inequality has been explored in previous work; we refer the interested reader to [ABB13] and [CCR08].

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},\mathcal{S},\mathcal{T},Y)$ is an information structure that satisfies rectangle substitutes with respect to $G$.

We prove generalizations of Theorem 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. The first result we state assumes that $G$ is symmetric, but is otherwise quite general.

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:¹⁰¹⁰10Corollary 4.15 as stated (without the symmetry assumption) is actually a corollary of Theorem 4.18.

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 4.14 gives us the following corollary.

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