(for example, as $\ell\rightarrow\infty$, the optimal rule pointwise converges
to a polynomial), but many do not. We also prove, using techniques similar to
the Weierstrass approximation theorem [350], that each of these rules can be
approximated by polynomial proper scoring rules whose incentivization indices
approach the optimum.

Finally, beyond characterizing the optimal rules, the incentivization indices
themselves allow for comparison among popular scoring rules, such as
logarithmic, quadratic, and spherical
($s_{\text{sph}}(x):=x/\sqrt{x^{2}+(1-x)^{2}}$). We plot the predictions made
by our incentivization index (which provably binds only as $c\rightarrow 0$)
for various values of $c$, and also confirm via simulation that the index is
predictive for reasonable choices of $c$.

To summarize these results, we find that for all values of $\ell$, some
relatively well-known proper scoring rule is very close to optimal. For small
values of $\ell=1,2$, we find that the scoring rule
$s_{\text{hs}}(x):=-\sqrt{\frac{1-x}{x}}$ – prominently used by [202] to prove
a minimax theorem for randomized algorithms – is very close to optimal. For
larger values of $\ell$ (e.g. $\ell=4$), the log score is near-optimal. For
every large values of $\ell$ (e.g. $\ell=16$), the quadratic score is near-
optimal. And for much larger values of $\ell$ (e.g. $\ell=128$), the spherical
scoring rule is near-optimal. See Table 3.1 and Figure 3.4 for more details.

Generally, these scoring rules are in decreasing order of how harshly they
penalize assigning a very low probability to the eventual outcome (compare
e.g. the log and quadratic scoring rules): the smaller the value of $\ell$,
the more preferable it is to have a scoring rule that penalizes incorrect
forecasts near the extremes.

####  3.1.3 Related work

To the best of our knowledge, [315] was the first to consider scoring rules as
motivating the predictor to seek additional information about the distribution
before reporting their belief. This direction is revisited in [229], and has
gained more attention recently [345, 324, 267]. While these works (and ours)
each study the same phenomenon, there is little technical overlap and the
models are distinct: each explores a different aspect of this broad agenda.
For example, [324] consider the predictor’s incentive to outperform competing
predictors (but there is no costly effort: the predictors’ beliefs are still
exogenous). [267] (which is contemporaneous and independent of our work) is
the most similar in motivation, but still has significant technical
differences (beyond the two subsequent examples). On one hand, their model is
more general than ours in that they consider multi-dimensional state spaces
(rather than binary ones, in our model). On another hand, it is more
restrictive in that they consider only two levels of effort (versus infinitely
many, in our model).

Our work also fits into the broad category of principal-agent problems. For
example, works such as [210, 293, 219, 224] consider a learning principal who
incentivizes agents to make costly effort and produce an accurate data point.
Again, the models are fairly distinct, as these works focus on more
sophisticated learning problems (e.g. regression), whereas we perform a more
comprehensive dive into the problem of simply eliciting the (incentivized-to-
be-precise) belief.

In summary, there is a sparse, but growing, body of work addressing the study
of incentivizing effort in forming predictions, rather than just accuracy in
reporting them. The above-referenced works pose various models to tackle
different aspects of this agenda. In comparison, our model is arguably the
simplest, and we develop a deep understanding of optimal scoring rules in this
setting.

###  3.2 Our model and preliminaries

####  3.2.1 Modeling the expert’s behavior

We model the expert as Bayesian. Specifically, the expert initially believes
the coin bias is uniformly distributed in $(0,1)$. Today, the expert may flip
the coin any number of times in order to gauge its true bias, and pays $c$ per
flip.

######  Fact 3.2.1 (Laplace’s rule of succession).

After having flipped the coin $n$ times, and seen $k$ heads, the expert
believes444By this, we mean the expert believes the coin would land heads with
probability $\frac{k+1}{n+2}$, if it were flipped again. that the coin’s bias
is $\frac{k+1}{n+2}$.

Once done flipping, the expert reports their belief about the coin’s bias.
Tomorrow, the coin is flipped once, and the expert is scored with a proper
scoring rule $s$ (known to the expert in advance).

It remains to define when the expert should stop flipping. Below, an _adaptive
strategy_ simply refers to a (possibly randomized) stopping rule for the
expert, i.e. a rule that, given any number of past flips and the proper
scoring rule $s$, tells the expert whether to stop or to flip the coin again.
The payoff of an adaptive strategy is simply the expected score of an expert
who follows that strategy, minus $c$ times the expected number of coin flips.

######  Definition 3.2.2.

A _globally-adaptive expert_ uses the payoff-maximizing adaptive strategy.

Nailing down the expert’s optimal behavior as a function of $c$ is quite
unwieldy. Thus, we derive our characterizations up to $o(1)$ terms (as
$c\rightarrow 0$). When $c$ is large, one may reasonably worry that these
$o(1)$ terms render our theoretical results irrelevant. In Appendix A.6 we
simulate the expert’s optimal behavior for large $c$, and confirm that our
results hold qualitatively in this regime.

Finally, we define a natural measure of precision for the expert’s prediction.

######  Definition 3.2.3.

The _expected $\ell$-th power error_ associated with a proper scoring rule $s$
and cost $c$ is $\text{Error}_{c}^{\ell}(s):=\mathbb{E}\left[\left\lvert
p-q\right\rvert^{\ell}\right]$. The expectation is taken over the true bias
$p$ of the coin, drawn uniformly from $(0,1)$, and $q$, the prediction of a
globally-adaptive expert after flipping the coin as many times as they choose.

####  3.2.2 Scoring rule preliminaries

Our proofs will make use of fairly heavy single-variable analysis, and
therefore will require making some assumptions on $s$ such as
differentiability, but also more technical ones. We will clearly state them
when necessary, and confirm that all scoring rules of interest satisfy them.
For these preliminaries, we need only assume that $s$ is continuously
differentiable so that everything which follows is well-defined.

Lemma 3.2.4 provides a characterization of proper (and weakly proper) scoring
rules in our (binary, symmetric) setting.

######  Lemma 3.2.4.

A continuously differentiable scoring rule $s$ is weakly proper if and only if
for all $p\in(0,1)$, $ps^{\prime}(p)=(1-p)s^{\prime}(1-p)$ and
$s^{\prime}(p)\geq 0$. It is (strictly) proper if and only if additionally
$s^{\prime}(p)>0$ almost everywhere555Almost everywhere on $(0,1)$ refers to
the interval $(0,1)$ except a set of measure zero. in $(0,1)$.

###### Proof sketch.

If the expert believes that the true probability is $p$ and reports $x$, then
their expected score is $ps(x)+(1-p)s(1-x)$. For every $p$, we want this
expression to reach a maximum at $x=p$. The derivative of the expression with
respect to $x$ is $ps^{\prime}(x)-(1-p)s^{\prime}(1-x)$. Thus, for $s$ to be
proper, we should have that $ps^{\prime}(p)=(1-p)s^{\prime}(1-p)$ for all $p$.
∎

We defer the full proof of Lemma 3.2.4 to Appendix A.1.

######  Corollary 3.2.5.

Let $s$ be strictly increasing almost everywhere (resp., nondecreasing
everywhere) and continuously differentiable on $(0,\frac{1}{2}]$. Then $s$ can
be extended to a continuously differentiable proper (resp., weakly proper)
scoring rule on $(0,1)$ by defining
$s^{\prime}(p)=\frac{1-p}{p}s^{\prime}(1-p)$ for
$p\in\left(\frac{1}{2},1\right)$.

Put another way: every continuously differentiable proper scoring rule can be
defined by first providing a strictly increasing function on
$(0,\frac{1}{2}]$, and then extending it as in Corollary 3.2.5. For example,
consider the function $s(x)=x$, which is strictly increasing on
$(0,\frac{1}{2}]$. Defining $s^{\prime}(x)=\frac{1-x}{x}\cdot 1=\frac{1}{x}-1$
for $x\in[\frac{1}{2},1)$ results in $s(x)=\ln x-x+1+\ln 2$ (where $1+\ln 2$
is the necessary constant to make $s$ continuous at $x=\frac{1}{2}$). Clearly
$s^{\prime}(x)>0$ on $(0,1)$ (as promised by Corollary 3.2.5), so we have just
constructed a proper scoring rule:

$s(x)=\begin{cases}x&\text{for }x\leq\frac{1}{2}\\\ \ln x-x+1+\ln 2&\text{for
}x\geq\frac{1}{2}\end{cases}.$

####  3.2.3 First steps towards understanding incentivization

We will be working with both $s$ and its expected score function
$G_{s}(x)=xs(x)+(1-x)s(1-x)$ (see Section 2.1). Note that $G_{s}$ is
necessarily symmetric about $\frac{1}{2}$ (this is a consequence of our
assumption that $s$ is symmetric). Additionally, the fact that $s$ is
continuously differentiable implies that $G_{s}$ is as well.

######  Remark 3.2.6.

For a weakly proper scoring rule $s$, we have $G_{s}^{\prime}(x)=s(x)-s(1-x)$
and
$G_{s}^{\prime\prime}(x)=s^{\prime}(x)+s^{\prime}(1-x)=\frac{s^{\prime}(x)}{1-x}\geq
0$ on $(0,1)$.

(The last equality can be inferred by using Lemma 3.2.4.) Lemma 3.2.7 observes
how an expert’s expected score evolves with an additional flip of the coin.

######  Lemma 3.2.7.

For a proper scoring rule $s$, if the expert has already flipped the coin $n$
times, seeing $k$ heads, then their expected increase in score for exactly one
additional flip is

$\frac{k+1}{n+2}G_{s}\left(\frac{k+2}{n+3}\right)+\frac{n-k+1}{n+2}G_{s}\left(\frac{k+1}{n+3}\right)-G_{s}\left(\frac{k+1}{n+2}\right).$

This quantity is positive.

###### Proof.

This is a direct application of Laplace’s rule of succession (Fact 3.2.1).
Currently, the expert believes the probability of heads to be
$\frac{k+1}{n+2}$. So their expected score if they stop flipping now is
exactly $G_{s}\left(\frac{k+1}{n+2}\right)$. If they flip once more and stop,
then with probability $\frac{k+1}{n+2}$ they will get a heads, updating their
belief to $\frac{k+2}{n+3}$, and yielding expected score
$G_{s}\left(\frac{k+2}{n+3}\right)$. With probability $\frac{n-k+1}{n+2}$ they
will get a tails, updating their belief to $\frac{k+1}{n+3}$ and yielding
expected score $G_{s}\left(\frac{k+1}{n+3}\right)$.

The fact that the quantity in Lemma 3.2.7 is positive follows directly from
the fact that $G_{s}$ is strictly convex. ∎

Proper scoring rules remain proper when scaled by a positive affine
transformation. This presents an issue for comparing scoring rules based on
their incentivization properties. Because we are interested in incentivizing
the expert to take costly actions, so the scale of a proper scoring rule will
be relevant. For example, if $s$ is proper, then so is $2s$, and $2s$ clearly
does a better job of incentivizing the expert (since the quantity in Lemma
3.2.7 is larger by a factor of $2$). As such, we will want to first
_normalize_ any scoring rules under consideration to be on the same scale.

A natural normalization is to consider two scoring rules to be on the same
scale if they provide the same expected score to a perfect expert (one who
knows the bias exactly). This is a natural choice because the expected score
of a perfect expert is an upper bound on the expected payment that the
principal must make. Further, as $c\to 0$, the expected score of a globally
adaptive expert in fact approaches the expected score of a perfect expert (see
Proposition A.1.2). Intuitively, this is because the number of flips
approaches infinity as $c$ approaches $0$, so the expert’s forecast becomes
perfectly precise in this limit.

The expected score of a perfect expert is $\int_{0}^{1}G_{s}(x)dx$, since a
perfect expert has expected payoff $G_{s}(x)$ if the coin has bias $x$, and
the coin’s bias is chosen uniformly from $[0,1]$. For this reason, when
evaluating a proper scoring rule in terms of its incentivization properties,
we will scale it so that $\int_{0}^{1}G_{s}(x)dx=1$.

Scaling proper scoring rules in this way addresses one potential issue, but
there is another as well: consider a proper scoring rule $s$ satisfying
$\int_{0}^{1}G_{s}(x)dx=1$. Then $\tilde{s}(x):=2s(x)-1$ is also proper and
satisfies $\int_{0}^{1}G_{\tilde{s}}(x)dx=1$. However, $\tilde{s}$ clearly
does a better job incentivizing the expert (again, by the positivity of the
quantity in Lemma 3.2.7). As such, we will also normalize $s$ so that the
score of a completely uninformed expert – one who flips the coin zero times
and says $\frac{1}{2}$ – is zero.

######  Definition 3.2.8.

A weakly proper scoring rule $s$ is _normalized_ if
$\int_{0}^{1}G_{s}(x)dx=1$, and $s(1/2)=0$.

We often use the following equivalent condition (the proof of equivalence is
given in Appendix A.1).

######  Claim 3.2.9.

For a weakly proper scoring rule $s$, we have

$\int_{0}^{1}G_{s}(x)dx=s\left(\frac{1}{2}\right)+\int_{\frac{1}{2}}^{1}(1-x)s^{\prime}(x)dx.$

Thus, $s$ is normalized if and only if $s(1/2)=0$ and
$\int_{\frac{1}{2}}^{1}(1-x)s^{\prime}(x)dx=1$.

###  3.3 An incentivization index

This section presents our first main contribution: an incentivization index
that characterizes the expert’s expected error. The main result of this
section, Theorem 3.3.3, requires scoring rules to be analytically nice in a
specific way. We term such scoring rules _respectful_.

######  Definition 3.3.1.

A proper scoring rule $s$ is _respectful_ if:

  1. (1)

$G_{s}$ is strongly convex on $(0,1)$. That is, $G_{s}^{\prime\prime}(x)\geq
a$ on $(0,1)$ for some $a>0$.

  2. (2)

$G_{s}^{\prime\prime\prime}$ is Riemann integrable on any closed sub-interval
of $(0,1)$.666Note this does not necessarily require
$G_{s}^{\prime\prime\prime}$ be defined on the entire $(0,1)$, just that it is
defined almost everywhere.

  3. (3)

There exists $t>\frac{1}{4}$, and $c_{0}>0$ such that for all $c\in(0,c_{0})$:
$\left\lvert
G_{s}^{\prime\prime\prime}(x)\right\rvert\leq\frac{1}{c^{0.16}\sqrt{x(1-x)}}G_{s}^{\prime\prime}(x)$
on $[c^{t},1-c^{t}]$.777Except in places where $G_{s}^{\prime\prime\prime}$ is
undefined.

Recall that $G_{s}$ is strictly convex for any (strictly) proper scoring rule,
so strong convexity is a minor additional assumption. Likewise, the second
condition is a minor “niceness” assumption. We elaborate on the third
condition in detail in Appendix A.2, and confirm that frequently used proper
scoring rules are indeed respectful. We briefly note here that intuitively,
the third condition asserts that $G_{s}^{\prime\prime}$ does not change too
quickly (except possibly near zero and one) for small enough coin-flipping
costs $c$. The particular choice of $0.16$ is not special, and could be
replaced with any constant less than $1/6$.

######  Definition 3.3.2 (Incentivization Index).

For $\ell\geq 1$, we define the _$\ell$ -th power incentivization index_ of a
proper scoring rule $s$:

$\text{Ind}^{\ell}(s):=\int_{0}^{1}\left(\frac{x(1-x)}{G_{s}^{\prime\prime}(x)}\right)^{\ell/4}dx.$

######  Theorem 3.3.3.

If
$\mu_{\ell}:=\frac{2^{\ell/2}\Gamma\left(\frac{\ell+1}{2}\right)}{\sqrt{\pi}}$
is the $\ell^{th}$ moment of the standard normal distribution, then

$\lim_{c\to 0}c^{-\ell/4}\cdot\text{Error}^{\ell}_{c}(s)=\mu_{\ell}\cdot
2^{\ell/4}\cdot\text{Ind}^{\ell}(s).$

Intuitively, the incentivization index captures the expert’s error as
$c\rightarrow 0$. More formally, for any two respectful proper scoring rules
$s_{1},s_{2}$, $\text{Ind}^{\ell}(s_{1})<\text{Ind}^{\ell}(s_{2})$ implies
that there exists a sufficiently small $c_{0}>0$ such that
$\text{Error}_{c}^{\ell}(s_{1})<\text{Error}_{c}^{\ell}(s_{2})$ for all $c\leq
c_{0}$. As previously mentioned, Theorem 3.3.3 says nothing about how big or
small this $c_{0}$ might be, although simulations in Appendix A.6 confirm that
it does not appear to be too small for typical scoring rules.

Theorem 3.3.3 says that the expert’s expected $\ell$-th power error is
proportional to $c^{\ell/4}$. What is the intuition for this asymptotic
relationship? Speaking informally, the key facts are that the number of times
that the expert flips the coin is proportional to $c^{-1/2}$, and that the
expected absolute error is proportional to $n^{-1/2}$, where $n$ is the number
of flips. The first fact follows from the fact that the expected improvement
in the expert’s score from an extra flip is proportional to $\frac{1}{n^{2}}$
(Claim 3.3.5 below); this quantity thus falls below the cost $c$ when $n$ is
on the order of $c^{-1/2}$. The second fact follows from the fact that the
expert’s estimate of the bias $p$ is (roughly) $\frac{1}{n}$ times a binomial
random variable with $n$ trials and probability $p$ of success; the standard
deviation of this quantity is proportional to $n^{-1/2}$.

The rest of this section is organized as follows. Sections 3.3.1 through 3.3.6
outline our proof of Theorem 3.3.3. The key steps are given as precisely-
stated technical lemmas with mathematical intuition alongside them, to
illustrate where precision is needed for the proof to carry through. Complete
proofs of these lemmas can be found in Appendix A.3. In Appendix A.2, we
confirm that natural scoring rules are respectful (which is mostly a matter of
validating the third condition in Definition 3.3.1).

####  3.3.1 Proof outline of Theorem 3.3.3

Below, we provide an executive overview of our approach. The concrete steps
are separated out as formally-stated technical lemmas in the following
sections, with proofs deferred to Appendix A.3. Before beginning, we highlight
the main challenge: to prove Theorem 3.3.3, we need to capture the _precise
asymptotics_ of the expert’s expected error. Upper bounds can be easily shown
via concentration inequalities; however, traditional lower bounds via anti-
concentration results would simply state that the expected error tends to $0$
as $c\rightarrow 0$ (which holds for every proper scoring rule, and doesn’t
distinguish among them). So not only are we looking for two-sided bounds on
the error, but we need to gauge the precise _rate_ at which it approaches
zero. Moreover, even obtaining the order of magnitude of the error as $c\to
0$, which turns out to be $c^{-\ell/4}$, still does not suffice: we need to
compute the exact coefficient of $c^{-\ell/4}$. This difficulty motivates the
need for the technical lemmas stated in this section to be very precise. Our
outline is as follows:

  * •

All of our analysis first considers a locally-adaptive expert, who flips the
coin one additional time if and only if the expected increase in score _from
that single flip_ exceeds $c$.

  * •

Our first key step, Section 3.3.2, provides a loose asymptotic _lower bound_
on the number of times an expert flips the coin, for all respectful $s$.

  * •

Our second key step, Section 3.3.3, provides a coupling of the expert’s flips
across all possible true biases $p$. This helps prove uniform convergence
bounds over all $p$ for the expert’s error: we can now define an unlikely
“bad” event of overly-slow convergence without reference to $p$.

  * •

Our third key step, Section 3.3.4, provides tight bounds on the number of
flips by a locally-adaptive expert, up to $(1\pm o(1))$ factors. Note that the
first three steps have not referenced an error measure at all, and only
discuss the expert’s behavior.

  * •

Our fourth key step, Section 3.3.5, shows how to translate the bounds in
Section 3.3.4 to tight bounds on the error of a locally-adaptive expert, again
up to $(1\pm o(1))$ factors.

  * •

Finally our last step, Section 3.3.6, shows that the globally-adaptive expert
behaves nearly-identically to the locally-adaptive expert, up to an additional
$o(1)$ factor of flips.

We now proceed to formally state the main steps along this outline, recalling
that the first several steps consider a locally-adaptive expert, whose
definition is restated formally below:

######  Definition 3.3.4 (Locally-Adaptive Expert).

The _locally-adaptive expert_ flips one more time if and only if making a
_single_ additional coin flip (and then stopping) increases their expected
payoff.

####  3.3.2 Step one: Lower bounding the expert’s number of flips

We begin by tying the expert’s expected marginal score from one additional
flip to the second derivative of the expected score function,
$G_{s}^{\prime\prime}$. Below, $Q(n)$ denotes the random variable which is the
expert’s belief after $n$ flips. The important takeaway from Claim 3.3.5 is
that for fixed $n$, the expert’s expected belief as a function of $Q(n)$
changes (roughly) as $Q(n)\cdot(1-Q(n))\cdot G_{s}^{\prime\prime}(Q(n))$ –
this takeaway will appear in later sections.

######  Claim 3.3.5.

Let $\Delta_{n+1}(q):=\mathbb{E}\left[G_{s}(Q(n+1))\mid
Q(n)=q\right]-G_{s}(q)$ be the expected increase in the expert’s score (not
counting the paid cost $c$) from the $(n+1)^{th}$ flip of the coin, given
current belief $Q(n)=q$. Then there exist $c_{1},c_{2}\in[q-1/n,q+1/n]$ such
that:

$\Delta_{n+1}=\frac{q\cdot(1-q)}{2(n+3)^{2}}(q\cdot
G_{s}^{\prime\prime}(c_{1})+(1-q)\cdot G_{s}^{\prime\prime}(c_{2}))$

Recalling that the locally-adaptive expert decides to flip the coin for the
$(n+1)^{th}$ time if and only if $\Delta_{n+1}\geq c$, and assuming that
$G_{s}^{\prime\prime}$ is bounded away from zero (Condition 1 in Definition
3.3.1), we arrive at a simple lower bound on the number of coin flips.

######  Claim 3.3.6.

For all $s$ such that $G_{s}^{\prime\prime}$ is bounded away from zero, there
exists $\alpha,c_{0}$ such that the expert is guaranteed to flip the coin at
least $\frac{1}{\alpha c^{1/3}}$ times for all $c\leq c_{0}$ (no matter the
true bias).

Using basic concentration inequalities, Claim 3.3.6 immediately implies an
asymptotic _upper bound_ on the expert’s error. Recall, however, that we need
a two-sided bound, and moreover that we need precise asymptotics of the error.
Still, Claim 3.3.6 is the first step towards this.

####  3.3.3 Step two: Ruling out irregular coin-flipping trajectories

The expert’s coin-flipping behavior depends on $Q(n)$, which depends on the
fraction of realized coin flips which are heads, which itself depend on the
coin’s true bias $p$. Note, of course, that $Q(n)\rightarrow p$ as
$n\rightarrow\infty$. If instead we had that $Q(n)=p$ _exactly_ , we could
leverage Claim 3.3.5 to better understand the number of flips as a function of
$p$. Unfortunately, $Q(n)$ will not equal $p$ exactly, and it is even possible
to have $Q(n)$ far from $p$, albeit with low probability.

The challenge, then, is then how to handle these low-probability events, and
importantly how to do so _uniformly over $p$_. To this end, we consider the
following coupling of coin-flipping processes over all possible biases.
Specifically, rather than first drawing bias $p$ and then flipping coins with
bias $p$, we use the following identically distributed procedure:

  1. (1)

Generate an infinite sequence $r_{1},r_{2},\dots$ of uniformly random numbers
in $[0,1]$.

  2. (2)

Choose $p$ uniformly at random from $[0,1]$.

  3. (3)

For each $n$, coin $n$ comes up heads if and only if $r_{n}\leq p$.

Under this sampling procedure, $Q_{p}(n):=\frac{h_{p}(n)+1}{n+2}$ is the
expert’s estimate after flipping $n$ coins, where $h_{p}(n)$ is the number of
heads in the first $n$ flips, if $p$ is the value chosen in step (2).

With this procedure, we can now define a single bad event _uniformly over all
$p$_. Intuitively, $\Omega_{N}$ holds when, no matter what $p$ is chosen in
step (2), the expert’s Bayesian estimate of $p$ never strays too far from $p$
after $N$ flips. More formally, the complement of $\Omega_{N}$ is our single
bad event:

$\overline{\Omega_{N}}:=\bigcup_{n=N}^{\infty}\bigcup_{j=1}^{n-1}\left\\{\left\lvert
Q_{j/n}(n)-\frac{j}{n}\right\rvert>\frac{\sqrt{j(n-j)}}{2n^{1.49}}\right\\}.$

The expression on the right-hand side of the inequality can be rewritten as
$\sqrt{\frac{\frac{j}{n}\left(1-\frac{j}{n}\right)}{n}}\cdot\frac{n^{.01}}{2}$,
where the radical term gives the order of the expected difference between
$Q_{j/n}(n)$ and $\frac{j}{n}$. So intuitively, $\Omega_{N}$ holds unless the
actual difference between $Q_{j/n}(n)$ and $\frac{j}{n}$ far exceeds its
expected value.

We have defined $\Omega_{N}$ so that, on the one hand, our subsequent analysis
becomes tractable when $\Omega_{N}$ holds, and on the other hand, $\Omega_{N}$
fails to hold with probability small enough that our asymptotic results are
not affected. Below, Claim 3.3.7 gives the property we desire from
$\Omega_{N}$, and Claim 3.3.8 shows that $\overline{\Omega_{N}}$ is unlikely.
The key takeaway from Claim 3.3.7 is that when $\Omega_{N}$ holds, the
expert’s prediction is close to $p$ _for all $n\geq N$ and $p\in(0,1)$_ and
this closeness _shrinks with $n$_.

######  Claim 3.3.7.

The exists a sufficiently large $N_{0}$ such that for all $N\geq N_{0}$: if
$\Omega_{N}$ holds, then

$\left\lvert
Q_{p}(n)-p\right\rvert\leq\frac{\sqrt{p(1-p)}}{n^{.49}}\quad\text{ for all
}n\geq N\text{ and }p\in[1/n,1-1/n].$

######  Claim 3.3.8.

$\text{Pr}\left[\overline{\Omega_{N}}\right]=O\left(e^{-N^{.01}}\right).$

While it is trivial to see that $Q_{p}(n)$ approaches $p$ as
$n\rightarrow\infty$, we reiterate that Claims 3.3.7 and 3.3.8 guarantee
quantitatively that: (a) when $\Omega_{N}$ holds, $|Q_{p}(n)-p|$ _shrinks with
$n$_, (b) the probability that $\Omega_{N}$ fails _shrinks exponentially fast
in $N$_, and (c) both previous bounds are _uniform over $p$_.

####  3.3.4 Step three: Tightly bounding the expert’s number of flips

We now nail down the precise asymptotics of the number of the expert’s flips
as a function of the true bias $p$. This becomes significantly more tractable
after assuming $\Omega_{N}$ holds. Below, the random variable
$n_{\mathsf{stop}}$ denotes the number of flips that a locally-adaptive expert
chooses to make.

######  Proposition 3.3.9.

Assume that $\Omega_{N}$ holds for some $N$, and let $t$ be as in Definition
3.3.1. There exists a constant $\gamma$ and cost $c_{0}>0$ such that for all
$c\leq c_{0}$ and all $p\in[2c^{t},1-2c^{t}]$, we have

$\sqrt{\frac{p(1-p)G_{s}^{\prime\prime}(p)}{2c}(1-\gamma c^{1/300})}\leq
n_{\mathsf{stop}}\leq\sqrt{\frac{p(1-p)G_{s}^{\prime\prime}(p)}{2c}(1+\gamma
c^{1/300})}.$

Proposition 3.3.9 has two key aspects. First, the upper and lower bounds on
$n_{\mathsf{stop}}$ match up to a $1\pm o(1)$ factor. Second, the $o(1)$ term
is independent of $p$. To get intuition for why
$n_{\mathsf{stop}}\approx\sqrt{\frac{p(1-p)G_{s}^{\prime\prime}(p)}{2c}}$,
recall that Claim 3.3.5 shows after $n$ flips, the expected marginal gain is
$\Delta_{n+1}\approx\frac{p(1-p)}{2n^{2}}G_{s}^{\prime\prime}(p)$. This
quantity first falls below $c$, the cost per flip, after
$n=\sqrt{\frac{p(1-p)G_{s}^{\prime\prime}(p)}{2c}}$ flips.

####  3.3.5 Step four: Translating number-of-flips bounds to error bounds

Having pinned down $n_{\mathsf{stop}}$ quite precisely, we will now obtain a
tight bound on the error of the locally-adaptive expert’s reported prediction.
By contrast, the previous three steps performed an analysis of the locally-
adaptive expert’s coin-flipping behavior, which does not depend on the choice
of error metric. Lemma 3.3.10 below is a formal statement of the main step of
this process, which nails down the asymptotics of the error conditioned on
$\Omega_{N}$. Below, $\text{Err}_{c}(p)$ denotes a random variable equal to
the locally-adaptive expert’s error (i.e. absolute difference between their
report and the true bias) when the cost is $c$ and the true bias is $p$ (and
the scoring rule $s$ is implicit).

######  Lemma 3.3.10.

Let $\ell\geq 1$ and
$\mu_{\ell}:=\frac{2^{\ell/2}\Gamma\left(\frac{\ell+1}{2}\right)}{\sqrt{\pi}}$
be the $\ell^{th}$ moment of a standard Gaussian. Let $N=\frac{1}{\alpha
c^{1/3}}$ (so $N$ is implicitly a function of $c$). For all
$p\in[2c^{t},1-2c^{t}]$ we have

$(1-o(1))\cdot\mu_{\ell}\cdot\left(\frac{2p(1-p)}{G_{s}^{\prime\prime}(p)}\right)^{\ell/4}\leq
c^{-\ell/4}\cdot\mathbb{E}\left[(\text{Err}_{c}(p))^{\ell}\mid\Omega_{N}\right]\leq(1+o(1))\cdot\mu_{\ell}\cdot\left(\frac{2p(1-p)}{G_{s}^{\prime\prime}(p)}\right)^{\ell/4}$

where the $o(1)$ term is a function of $c$ (but not $p$) that approaches zero
as $c$ approaches zero.

Lemma 3.3.10 is the key, but far from only, step in translating Proposition
3.3.9 to tight bounds on the locally-adaptive expert’s error. Intuitively, it
states that the value of the expert’s error will be, up to a $1\pm o(1)$
factor, consistent with what one would expect from using a quantitative
central limit theorem in conjunction with the bound on $n_{\mathsf{stop}}$
from Proposition 3.3.9.

####  3.3.6 Step five: From locally-adaptive to globally-adaptive behavior

Finally, we extend our previous analysis from locally-adaptive to globally-
adaptive experts. In particular, for a scoring rule that gives a finite
expected score to a perfect expert, we prove that the globally-adaptive expert
does not flip significantly more than a locally-adaptive expert would, and
therefore their achieved errors are equal up to a $1\pm o(1)$ factor. Below,
the random variable $n_{g}$ denotes the number of flips by the globally-
adaptive expert.

######  Lemma 3.3.11.

Assume $s$ is respectful and normalizable (i.e.
$\int_{0}^{1}G_{s}(x)dx<\infty$). Let $\gamma$ be as in Proposition 3.3.9.
There exists a $c_{0}>0$, such that for all $c\leq c_{0}$: If
$\Omega_{n_{\mathsf{stop}}}$ holds and $4c^{t}\leq Q(n_{\mathsf{stop}})\leq
1-4c^{t}$, then

$n_{\mathsf{stop}}\leq n_{g}\leq(1+6\gamma c^{1/300})n_{\mathsf{stop}}.$

Lemma 3.3.11 is the key step in this portion of the analysis. The remaining
work is to bound the impact of negligible events (such as
$\Omega_{n_{\mathsf{stop}}}$ failing, or $Q(n_{\mathsf{stop}})$ being
extremely close to $0$ or $1$) on our analysis. This completes our outline of
the proof of Theorem 3.3.3.

###  3.4 Finding optimal scoring rules

Now that we have shown that the incentivization index characterizes how well
any respectful scoring rule incentivizes a globally-adaptive expert to
minimize error, we have a well-defined optimization problem: _which normalized
proper scoring rule has the lowest incentivization index_ (and therefore
minimizes the expert’s expected error)? Recall the following necessary and
sufficient set of conditions for a continuously differentiable and normalized
scoring rule $s$ to be weakly proper:888Including weakly proper scoring rules
in our optimization domain makes the analysis simpler. The optimal scoring
rules are in fact strictly proper.

  * •

(Lemma 3.2.4) For all $x\in(0,1)$, $xs^{\prime}(x)=(1-x)s^{\prime}(1-x)$ and
$s^{\prime}(x)\geq 0$.

  * •

(Definition 3.2.8, Claim 3.2.9) $s(1/2)=0$ and
$\int_{\frac{1}{2}}^{1}(1-x)s^{\prime}(x)dx=1$.

So our goal is just to find the scoring rule which satisfies these constraints
and minimizes the incentivization index:

$\text{Ind}^{\ell}(s)=\int_{0}^{1}\left(\frac{x(1-x)}{G_{s}^{\prime\prime}(x)}\right)^{\ell/4}dx=\int_{0}^{1}\left(\frac{x(1-x)^{2}}{s^{\prime}(x)}\right)^{\ell/4}dx.$

(The last step follows from Remark 3.2.6.) The main result of this section is
the following theorem, whose proof we defer to Appendix A.4.

######  Theorem 3.4.1.

The unique continuously differentiable normalized proper scoring rule which
minimizes $\text{Ind}^{\ell}(s)$ is:

$s_{\ell,\text{Opt}}(x):=\begin{cases}\kappa_{\ell}\int_{\frac{1}{2}}^{x}(t^{\ell-8}(1-t)^{2\ell+4})^{1/(\ell+4)}dt&x\leq\frac{1}{2}\\\
\kappa_{\ell}\int_{\frac{1}{2}}^{x}(t^{\ell}(1-t)^{2\ell-4})^{1/(\ell+4)}dt&x\geq\frac{1}{2}.\end{cases}$

While $s_{\ell,\text{Opt}}$ is certainly challenging to parse, importantly it
has a closed form, and can thus be numerically evaluated. Section 3.5.2
contains several plots of these scoring rules, alongside traditional ones.
Below we give an overview of our proof of Theorem 3.4.1 (the full details of
the proof can be found in Appendix A.4).

####  3.4.1 Proof overview of Theorem 3.4.1

As shown in Corollary 3.2.5, the equation
$xs^{\prime}(x)=(1-x)s^{\prime}(1-x)$ lets us extend $s$ uniquely in a
continuous manner to $(0,1)$ if we know $s$ on $[\frac{1}{2},1)$. Thus, we can
simply consider $s$ on $[\frac{1}{2},1)$. For $s^{\prime}$ to be nonnegative
everywhere, it suffices for it to be nonnegative on $[\frac{1}{2},1)$, because
of the relation $xs^{\prime}(x)=(1-x)s^{\prime}(1-x)$. Also, observe that the
integrand in the definition of the incentivization index is symmetric about
$\frac{1}{2}$; this is clear from the fact that $G_{s}^{\prime\prime}$ is
symmetric about $\frac{1}{2}$. This means that

$\text{Ind}^{\ell}(s)=2\int_{\frac{1}{2}}^{1}\left(\frac{x(1-x)^{2}}{s^{\prime}(x)}\right)^{\ell/4}dx.$

Thus, our question can be phrased as follows: find the continuously
differentiable function $s:[\frac{1}{2},1)\to\mathbb{R}$ satisfying
$s\left(\frac{1}{2}\right)=0$, $s^{\prime}(x)\geq 0$, and
$\int_{\frac{1}{2}}^{1}(1-x)s^{\prime}(x)dx=1$, that minimizes

$\int_{\frac{1}{2}}^{1}\left(\frac{x(1-x)^{2}}{s^{\prime}(x)}\right)^{\ell/4}dx.$

From this point, our problem is simply a continuous mathematical program. It
is not obvious that the program should admit a closed-form solution, but it
does. We defer all details to Appendix A.4, and just briefly note that we can
formulate the problem exclusively as a function of $s^{\prime}$, and then
uniquely reconstruct $s$ using $s\left(\frac{1}{2}\right)=0$. Once we have
done this, we can take a Lagrangian relaxation by putting a multiplier on the
constraint $\int_{\frac{1}{2}}^{1}(1-x)s^{\prime}(x)dx=1$, and hope that the
solution to the relaxation is continuous and satisfies $s^{\prime}(x)\geq 0$.
While this is not guaranteed to succeed, this method does in fact nail down
the optimum. Below are the main technical lemmas that yield Theorem 3.4.1.
Note that $h$ plays the role of $s^{\prime}$ in these lemmas.

######  Lemma 3.4.2.

For any $\ell\geq 1$, a function $h:[\frac{1}{2},1)\to\mathbb{R}_{\geq 0}$
satisfying $\int_{\frac{1}{2}}^{1}(1-x)h(x)dx=1$ that minimizes
$\int_{\frac{1}{2}}^{1}\left(\frac{x(1-x)^{2}}{h(x)}\right)^{\ell/4}dx$ is
$\tilde{h}_{\ell}(x)=\kappa_{\ell}(x^{\ell}(1-x)^{2\ell-4})^{1/(\ell+4)}$,
where
$\kappa_{\ell}=\left(\int_{\frac{1}{2}}^{1}(x(1-x)^{3})^{\ell/(\ell+4)}dx\right)^{-1}$.

(Note that $\kappa_{\ell}$ is simply a normalization constant, so as to make
$\int_{\frac{1}{2}}^{1}(1-x)h(x)dx$ equal $1$.)

######  Corollary 3.4.3.

The unique continuous function $h:[\frac{1}{2},1)\to\mathbb{R}_{\geq 0}$
satisfying $\int_{\frac{1}{2}}^{1}(1-x)h(x)dx=1$ that minimizes
$\int_{\frac{1}{2}}^{1}\left(\frac{x(1-x)^{2}}{h(x)}\right)^{\ell/4}dx$ is
$\tilde{h}_{\ell}$.

Theorem 3.4.1 then follows from Corollary 3.4.3 by setting
$s_{\ell,\text{Opt}}$ to the integral of $\tilde{h}_{\ell}$ on $[1/2,1)$, and
extending it to $(0,1/2)$ via Corollary 3.2.5. For some choices of $\ell$, the
particular scoring rule $s_{\ell,\text{Opt}}$ has an interesting closed form
(see Section 3.5), but this is not true for all $\ell$. Even in cases where
the particular closed form is not illuminating, the fact that
$s_{\ell,\text{Opt}}$ even exists is already interesting, and the fact that
Theorem 3.4.1 nails down the closed form allows us to compare other scoring
rules to the optimum. We conclude with a remark, confirming that our analysis
in Section 3.3 indeed is meaningful for all derived optimal scoring rules.

######  Remark 3.4.4.

For every $\ell\in[1,8]$, $s_{\ell,\text{Opt}}$ is respectful. For $\ell>8$,
and all $\varepsilon>0$, there exists a respectful normalized proper scoring
rule $s$ such that $\left\lvert
s(x)-s_{\ell,\text{Opt}}(x)\right\rvert\leq\varepsilon$ for all $x\in(0,1)$,
with
$\text{Ind}^{\ell}(s)\leq\text{Ind}^{\ell}(s_{\ell,\text{Opt}})+\varepsilon$.

We give a proof for $\ell\in[1,8]$ in Appendix A.3. Meanwhile, the proof for
$\ell>8$ follows from the proof of Theorem 3.6.1 in Appendix A.5.999More
specifically, the scoring rules $s_{\varepsilon}$ defined in the proof of
Theorem 3.6.1 uniformly converge to $s_{\ell,\text{Opt}}$.

The following corollary follows from Remark 3.4.4.

######  Corollary 3.4.5.

For $\ell\geq 1$, let

$\text{Error}_{\text{Opt}}^{\ell}:=\inf_{s}\lim_{c\to
0}c^{-\ell/4}\cdot\text{Error}_{c}^{\ell}(s)$

where $s$ ranges over all normalized, respectful, continuously differentiable
proper scoring rules. Let

$\text{Ind}_{\text{Opt}}^{\ell}:=\inf_{s}\text{Ind}^{\ell}(s)$

where $s$ ranges over all normalized, continuously differentiable proper
scoring rules. Then:

  1. (1)

$\text{Error}_{\text{Opt}}^{\ell}=\mu_{\ell}\cdot
2^{\ell/4}\cdot\text{Ind}_{\text{Opt}}^{\ell}$.

  2. (2)

For $1\leq\ell\leq 8$, the first infimum is uniquely achieved by
$s=s_{\ell,\text{Opt}}$.

  3. (3)

For $\ell>8$, no (respectful) function achieves the first infimum, but the
infimum is reached in the limit by uniform approximations of
$s_{\ell,\text{Opt}}$ (which are normalized, respectful, and continuously
differentiable).

###  3.5 Comparing scoring rules

In this section we compare various scoring rules by their incentivization
indices, for various values of $\ell$. Of particular interest are the values
$\ell=1$ (expected absolute error), $\ell=2$ (expected squared error), and the
limit as $\ell\to\infty$ (which penalizes bigger errors “infinitely more” than
smaller ones, so this regime corresponds to minimizing the probability of
being very far off).

####  3.5.1 Optimal scoring rules for particular values of $\ell$

We begin by noting some values of $\ell$ for which the function
$s_{\ell,\text{Opt}}$ takes a nice closed form. $\ell=1$ happens to not be one
such value. For $\ell=2,4,8$, the functions $s_{\ell,\text{Opt}}$ can be
written in terms of elementary functions on the entire interval $(0,1)$. For
$\ell=2$, the closed form on $(1/2,1)$ is a polynomial, although its extension
via Corollary 3.2.5 to $(0,1/2)$ is not. For $\ell=8$, the closed form on both
$(0,1/2)$ and $(1/2,1)$ is a polynomial, although they are different.
Interestingly, as $\ell\rightarrow\infty$, the closed form converges pointwise
to a single polynomial. Specifically, for these values of $\ell$:

For $\mathbf{\ell=2}$: On $[\frac{1}{2},1)$, we have

$s_{2,\text{Opt}}(x)=\kappa_{2}\int_{\frac{1}{2}}^{x}t^{2/3}dt=\frac{3}{5}\kappa_{2}\left(x^{5/3}-\left(\frac{1}{2}\right)^{5/3}\right).$

For $\mathbf{\ell=8}$: On $(0,\frac{1}{2}]$, we have

$s_{8,\text{Opt}}(x)=\kappa_{8}\int_{\frac{1}{2}}^{x}(1-t)^{5/3}dt=\frac{3}{8}\kappa_{8}\left(\left(\frac{1}{2}\right)^{8/3}-(1-x)^{8/3}\right)$

and on $[\frac{1}{2},1)$, we have

$s_{8,\text{Opt}}(x)=\kappa_{8}\int_{\frac{1}{2}}^{x}(t^{2/3}-t^{5/3})dt=\kappa_{8}\left(\frac{3}{5}\left(x^{5/3}-\left(\frac{1}{2}\right)^{5/3}\right)-\frac{3}{8}\left(x^{8/3}-\left(\frac{1}{2}\right)^{8/3}\right)\right).$

Finally, as $\mathbf{\ell\to\infty}$: on the entire interval $(0,1)$,
$s_{\ell,\text{Opt}}$ pointwise converges to

$\lim_{\ell\to\infty}\kappa_{\ell}\cdot\int_{\frac{1}{2}}^{x}t(1-t)^{2}dt=\frac{320}{3}\left(\frac{1}{4}x^{4}-\frac{2}{3}x^{3}+\frac{1}{2}x^{2}-\frac{11}{192}\right)=\frac{5}{9}(48x^{4}-128x^{3}+96x^{2}-11).$

We refer to this last rule as $s_{\infty,\text{Opt}}$. Intuitively, minimizing
the expected value of error raised to a power that approaches infinity
penalizes any error infinitely more than an even slightly smaller error. Put
otherwise, this metric judges a scoring rule by the maximum (over $p\in(0,1)$)
of the spread of the distribution of expert error. The scoring rule
$s_{\infty,\text{Opt}}$ has a very special property, which is that the
quantity
$\frac{x(1-x)}{G_{s_{\infty,\text{Opt}}}^{\prime\prime}(x)}=\frac{x(1-x)^{2}}{s_{\infty,\text{Opt}}^{\prime}(x)}$,
which appears in the incentivization index, is a constant regardless of $x$.
This means that, in the limit as $c\to\infty$, the distribution of the
expert’s error is the same regardless of $p$. It makes intuitive sense that
making the spread of the distribution of expert error uniform over all $p$
also minimizes the maximum of these spreads, which explains why
$s_{\infty,\text{Opt}}$ has this interesting property.

As some of these rules are not infinitely differentiable, a natural question
to ask is: what infinitely differentiable normalized function minimizes
$\text{Ind}^{\ell}$? While (as we have shown by virtue of
$s_{\ell,\text{Opt}}$ being the unique minimizer) achieving an incentivization
index equal to $\text{Ind}^{\ell}(s_{\ell,\text{Opt}})$ with an infinitely
differentiable scoring rule is impossible, it turns out that it is possible to
get arbitrarily close – and in fact it is possible to get arbitrarily close
with _polynomial_ scoring rules. The main idea of the proof is to use the
Weierstrass approximation theorem to approximate $s_{\ell,\text{Opt}}$ with
polynomials. See Section 3.6 for a full proof.

####  3.5.2 Plots of some relevant scoring rules

Figure 3.1 plots $s_{\ell,\text{Opt}}$ for $\ell=1,2,8,\infty$. It
demonstrates that optimal scoring rules for larger values of $\ell$ are
“flatter,” choosing to sacrifice rewarding precision near $0$ and $1$, in
favor of rewarding precision closer to $\frac{1}{2}$. An expert who is scored
by $s_{\infty,\text{Opt}}$ does not particularly care to distinguish between
98% and 99% probabilities, since the scoring rule is basically flat near the
tails; this is not the case for $s_{1,\text{Opt}}$. Conversely, because
$s_{\infty,\text{Opt}}$ is steeper than $s_{1,\text{Opt}}$ near $\frac{1}{2}$,
an expert cares more about differentiating between a 50% and a 51% chance if
scored with $s_{\infty,\text{Opt}}$ than with $s_{1,\text{Opt}}$.

Figure 3.1: Plots of $s_{\ell,\text{Opt}}$ for $\ell=1,2,8,\infty$.

Another, perhaps more enlightening way to view these scoring rules is through
the quantity $\sqrt{\frac{x(1-x)}{G_{s}^{\prime\prime}(x)}}$. Up to a constant
factor depending on the cost $c$ of a flip, this is the variance of the normal
distribution that approximates the distribution of the expert’s response if
the true bias of the coin is $x$ (for small $c$) – or, put otherwise, the
expected squared error. Figure 3.2 plots this quantity for a variety of the
scoring rules we have discussed.

Figure 3.2: Plots of $\sqrt{\frac{x(1-x)}{G_{s}^{\prime\prime}(x)}}$ for
$s=s_{\ell,\text{Opt}}$ for a variety of values of $\ell$. Up to a constant
factor, this quantity is the variance of the normal distribution that
approximates the distribution of the expert’s response if the true bias of the
coin is $x$ (for small $c$).

Figure 3.2 reinforces our previous point: optimal rules for small value of
$\ell$ result in very small errors near $0$ and $1$, but relatively large
errors in the middle. In Section 3.5.1, we discussed in brief why it makes
sense that the value of $\frac{x(1-x)}{G_{s}^{\prime\prime}(x)}$ is constant
for the scoring rule $s_{\infty,\text{Opt}}$. We see this in Figure 3.2: since
our normalization constraints force a trade-off between minimizing expert
error for different values of the coin’s bias $p$, the scoring rule whose
error is independent of $p$ will have the minimum possible value of the
maximum error over all $p$.

Finally, Figure 3.3 is similar to Figure 3.2, except that it also includes the
(normalized) logarithmic, quadratic, and spherical scoring rules. In Section
3.5.3, we noted that the logarithmic rule is near-optimal for $\ell\approx 4$,
the quadratic rule for $\ell\approx 16$, and the spherical rule for even
larger $\ell$. Figure 3.3 helps provide some intuition for this fact: the log
scoring rule is similar in shape to $s_{4,\text{Opt}}$ and similarly for the
quadratic scoring rule and $s_{16,\text{Opt}}$, and for the spherical scoring
rule and $s_{\infty,\text{Opt}}$.

Figure 3.3: Plots of $\sqrt{\frac{x(1-x)}{G_{s}^{\prime\prime}(x)}}$ for
$s=s_{\text{log}}$, $s_{\text{quad}}$, and $s_{\text{sph}}$, as well as some
optimal rules. Up to a constant factor, this quantity is the variance of the
normal distribution that approximates the distribution of the expert’s
response if the true bias of the coin is $x$ (for small $c$).

####  3.5.3 Comparison of incentivization indices of scoring rules

We compare commonly studied scoring rules such as quadratic, logarithmic, and
spherical, and in this section we refer to their normalizations as
$s_{\text{quad}},s_{\text{log}},s_{\text{sph}}$, respectively. Additionally we
include for comparison $s_{\text{hs}}$, which is the normalization of the $hs$
scoring rule: $-\sqrt{\frac{1-x}{x}}$. This scoring rule was prominently used
by [202] to prove their minimax theorem for randomized algorithms.

Table 3.1 states $\text{Ind}^{\ell}(s)$ for various scoring rules $s$ (the
lower the better). It lets us compare the performance of various scoring rules
by our metric for any particular value of $\ell$. However, as one can see,
$\text{Ind}^{\ell}$ decreases as $\ell$ increases. This makes sense, since
$\text{Ind}^{\ell}$ measures the expected $\ell$-th power of error. For this
reason, if we wish to describe how a given scoring rule performs over a range
of values of $\ell$, we need to normalize these values. We do so by taking the
$\ell$-th root and dividing these values by the $\ell$-th root of the optimal
(smallest) index (and take the inverse so that larger numbers are better).
This gives us the following measure of scoring rule precision, which makes
sense across different values of $\ell$:

$\left(\frac{\text{Ind}^{\ell}(s_{\ell,\text{Opt}})}{\text{Ind}^{\ell}(g)}\right)^{1/\ell}.$

$\text{Ind}^{\ell}(\cdot)$ | $\ell=1$ | $\ell=2$ | $\ell=4$
---|---|---|---
$s_{\text{log}}$ | 0.260 | 0.0732 | 0.00644
$s_{\text{quad}}$ | 0.279 | 0.0802 | 0.00694
$s_{\text{sph}}$ | 0.296 | 0.0889 | 0.00819
$s_{\text{hs}}$ | 0.255 | 0.0723 | 0.00658
$s_{1,\text{Opt}}$ | 0.253 | 0.0728 | 0.00719
$s_{2,\text{Opt}}$ | 0.255 | 0.0718 | 0.00661
$s_{4,\text{Opt}}$ | 0.261 | 0.0732 | 0.00639
$s_{\infty,\text{Opt}}$ | 0.311 | 0.0968 | 0.00974
Table 3.1: A table of incentivization index values for various proper scoring
rules under various error measures.

Figure 3.4, which evaluates this expression for a selection of proper scoring
rules and values of $\ell$, reveals some interesting patterns. Of the hs,
logarithmic, quadratic, and spherical scoring rules, the hs scoring rule is
the best one for the smallest values of $\ell$ and is in fact near-optimal for
$\ell=2$. The logarithmic rule is the best one for somewhat larger values of
$\ell$ and is in near-optimal for $\ell\approx 4$. For larger values of
$\ell$, the quadratic scoring rule is best, and is near-optimal for
$\ell\approx 16$. For even larger values of $\ell$, the spherical scoring rule
is the best of the four. This pattern suggests that for any given proper
scoring rule there is a trade-off between incentivizing precision at low and
at high values of $\ell$; it would be interesting to explore this further.
Figure 3.5 is a continuous version of Figure 3.4. It shows how the numbers in
the table vary over a continuum of values of $\ell$.

Figure 3.4: Incentivization indices of various proper scoring rules relative
to the optimal proper scoring rule, for a variety of error measures. The
values in the table are
$\left(\frac{\text{Ind}^{\ell}(s_{\ell,\text{Opt}})}{\text{Ind}^{\ell}(s)}\right)^{1/\ell}$.
Figure 3.5: Incentivization indices of various proper scoring rules relative
to the optimal proper scoring rule. On the left, $\ell$ varies between $1$ and
$200$. The chart on the right is a zoomed-in version of the same plot, showing
values of $\ell$ between $1$ and $10$. The plotted values are
$\left(\frac{\text{Ind}^{\ell}(s_{\ell,\text{Opt}})}{\text{Ind}^{\ell}(s)}\right)^{1/\ell}$.

###  3.6 Polynomial scoring rules with almost-optimal incentivization indices

The main result of this section is the following theorem, stating that
polynomial,101010When we say a scoring rule $s$ is polynomial, we mean simply
that $s$ is a polynomial function. respectful proper scoring rules suffice to
get arbitrarily close to the optimal incentivization index.

######  Theorem 3.6.1.

For $\ell\geq 1$ and $\varepsilon>0$, there exists a respectful polynomial
normalized proper scoring rule $s$ satisfying
$\text{Ind}^{\ell}(s)\leq\text{Ind}^{\ell}(s_{\ell,\text{Opt}})+\varepsilon$.

The proof of Theorem 3.6.1 uses ideas from the Weierstrass approximation
theorem. However, the Weierstrass approximation theorem gives a particular
measure of “distance” between two functions, which does not translate to these
functions having similar incentivization indices. So one challenge of the
proof is ensuring convergence of a sequence of polynomials to
$s_{\ell,\text{Opt}}$ _in a measure related to $\text{Ind}^{\ell}$_. A second
challenge is to ensure that all polynomials in this sequence are themselves
proper, respectful scoring rules. Like previous technical sections, we include
a few concrete lemmas to give a sense of our proof outline.

For example, one step in our proof is to characterize all _analytic_ proper
scoring rules (that is, proper scoring rules that have a Taylor expansion
which converges on their entire domain $(0,1)$). A necessary condition to be
analytic is to be infinitely differentiable, which rules of the form
$s_{\ell,\text{Opt}}$ are not, for any fixed $\ell$. We therefore seek to
approximate such scoring rules with polynomial scoring rules (which are
analytic), which are also respectful and proper.

######  Theorem 3.6.2.

Let $s:(0,1)\to\mathbb{R}$ be analytic (and symmetric, as we have been
assuming). Then $s$ is a proper scoring rule if and only if $s$ is
nonconstant, $s^{\prime}(x)\geq 0$ everywhere, and

$s(x)=c_{0}+\sum_{k>0\text{\emph{
odd}}}c_{k}(2k+1-2kx)\left(x-\frac{1}{2}\right)^{k}$

for some $c_{0},c_{1},c_{3},c_{5},\dots\in\mathbb{R}$.

As an example to help parse Theorem 3.6.2, the quadratic scoring rule has
$c_{1}<0$, and $c_{i}=0$ for all other $i$. Using Theorem 3.6.2, we can
conclude the following about $G_{s}^{\prime\prime}$ for any proper scoring
rule $s$:

######  Lemma 3.6.3.

Let $s:(0,1)\to\mathbb{R}$ be analytic and symmetric. Then $s$ is a proper
scoring rule if and only if $G_{s}^{\prime\prime}$ is not uniformly zero,
nonnegative everywhere, and can be written as

$G_{s}^{\prime\prime}(x)=\sum_{k\geq 0\text{
even}}d_{k}\left(x-\frac{1}{2}\right)^{k}.$

Lemma 3.6.3 provides clean conditions on what functions $G_{s}^{\prime\prime}$
are safe to use in our sequence of approximations, and our proof follows by
following a Weierstrass approximation-type argument while keeping track of
these conditions. The rest of the details for the proof of Theorem 3.6.1 can
be found in Appendix A.5.

###  3.7 Conclusion

We proposed a simple model in which an expert can expend costly effort to
refine their prediction, and studied the effectiveness of different proper
scoring rules in incentivizing the expert to form a precise belief. Our first
main result (Theorem 3.3.3) identified the existence of a closed-form
incentivization index: scoring rules with a lower index incentivize the expert
to be more precise. Our second main result (Theorem 3.4.1) identified the
unique optimal scoring rule with respect to this index. Section 3.5 then used
the incentivization index to compare common proper scoring rules (including
our newly-found optimal ones), and Section 3.6 showed that one can get
arbitrarily close to the optimal incentivization index with polynomial proper
scoring rules.

Our model is mathematically simple to describe, and yet it captures realistic
settings surprisingly well (see Section 3.1). As such, there are many
interesting directions for future work.

First: what about measures of error other than the $\ell$-th power of absolute
distance? In Section 2.1, we introduced Bregman divergences and explained
their relationship to proper scoring rules. In particular, if an expert is
scored according to a proper scoring rule $s$, then the expert’s expected loss
relative to perfectly reporting the coin’s true bias is equal to the Bregman
divergence from the true bias to their report with respect to $G_{s}$. It is
thus natural to consider the expected Bregman divergence as a notion of the
expert’s error. One might ask several questions related to this:

  * •

For a given $G$, what is the optimal proper scoring rule for Bregman
divergence with respect to $G$? (We have already answered this question for
$G(x)=x^{2}$: namely, $s_{2,\text{Opt}}$.) The case of $G$ being the negative
of binary entropy (in which case the Bregman divergence is KL divergence)
seems particularly interesting.

  * •

Conversely, is there a Bregman divergence with respect to which the quadratic
scoring rule is optimal? What about the logarithmic scoring rule?

  * •

As a general rule, will a proper scoring rule $s$ be unusually good at
incentivizing precision, if the measure of error is Bregman divergence with
respect to $G_{s}$? We already know that a proper scoring rule $s$ isn’t
necessarily _optimal_ for Bregman divergence with respect to $G_{s}$: in
particular, $s_{\text{quad}}$ isn’t optimal for $\ell=2$. However, perhaps a
weaker statement to this effect could be true. Is there a proper scoring rule
$s$ that is optimal for Bregman divergence with respect to $G_{s}$?

Other parameters of our model can also be varied to yield interesting
questions:

  * •

In our model, the expert receives information in discrete chunks (one coin
flip at a time). The expert’s probability distribution over the bias of the
coin is always a beta distribution with integer parameters $\alpha$ and
$\beta$. Instead, we could model an expert as continually receiving
information, so that their probability distribution over the bias of the coin
is modeled as a beta distribution with continuously changing real parameters
$\alpha$ and $\beta$. (This is inspired by an approach taken by [246] for a
related problem.) In addition to being an interesting variant of our model, a
continuous model like this one may simplify the analysis. Other natural priors
and processes of information gain may also be interesting to explore.

  * •

Our work considers a globally-adaptive expert, and establishes that they
behave nearly identically to a locally-adaptive expert. What about a non-
adaptive expert, who must decide a priori how many coin flips to make before
seeing the flip outcomes?

## Arbitrage-free contract functions

_This chapter presents “Strictly Proper Contract Functions Can Be Arbitrage-
Free”[306], although all contents starting with Definition 4.5.3 are new. It
assumes background on proper scoring rules presented in Section 2.1._

_Summary:_ We consider mechanisms for truthfully eliciting probabilistic
predictions from a group of experts. The standard approach – using a proper
scoring rule to separately reward each expert – is not robust to collusion:
experts may collude to misreport their beliefs in a way that guarantees them a
larger total reward no matter the eventual outcome. It is a long-standing open
question whether there is a truthful elicitation mechanism that makes any such
collusion (also called _arbitrage_) impossible. We resolve this question
positively, exhibiting a class of proper, arbitrage-free contract functions.
These contract functions have two parts: one ensures that the total reward of
a coalition of experts depends only on the average of their reports; the other
ensures that changing this average report hurts the experts under at least one
outcome.

###  4.1 Introduction

If a principal wishes to elicit a probabilistic forecast from an expert, they
may pay the expert using a proper scoring rule. But in many settings, the
principal may want to elicit forecasts from multiple experts, so as to get a
better sense of expert opinion and the extent to which there is a consensus.
The principal could use a proper scoring rule to elicit each expert’s
forecast. If experts are not allowed to collude, then this strategy is
incentive-compatible; however, [245] observed that experts can collude in a
way that increases the sum total profit of all experts, no matter the final
outcome.

For example, recall the quadratic scoring rule from Section 2.1:

$s_{\text{quad}}(\mathbf{x};j):=-(1-x_{j})^{2}-\sum_{j^{\prime}\neq
j}x_{j^{\prime}}^{2}.$

Suppose that three experts believe that there is a 40%, 50%, and 90% chance of
rain, and that they are paid according to the proper scoring rule
$s(\mathbf{x};j)=s_{\text{quad}}(\mathbf{x};j)+1$. If it ends up raining, then
the sum of their scores will be $0.28+0.5+0.98=1.76$; if it doesn’t rain, then
the sum of their scores will be $0.68+0.5-0.62=0.56$. However, suppose that
the experts all collude to report 60%. Then the sum of their scores is
$0.68+0.68+0.68=2.04$ if it rains and $0.28+0.28+0.28=0.84$ if it doesn’t: a
larger number in both cases! The experts can agree beforehand to a
redistribution of their rewards that guarantees every expert a larger profit
than if they had not colluded.

[228] called this phenomenon – in which experts collude to misreport in a way
where their total reward is larger no matter the outcome – _arbitrage_. They
showed that every proper scoring rule admits arbitrage – indeed, that there is
an arbitrage opportunity for any group of experts so long as they do not all
agree on the probability of the event. Specifically, a coalition of experts
can risklessly make a profit by deviating to report an aggregate of their
beliefs (in the case of the quadratic scoring rule, this aggregate is the
arithmetic mean). In Chapter 5, we will extend this observation to probability
distributions over more than two possible outcomes.

For many reasons, the expert may wish to make arbitrage impossible. First, the
principal may wish to know whether the experts are in agreement: if they are
not, for instance, the principal may want to elicit opinions from more
experts. If the experts collude to report an aggregate value (as in our
example), the principal does not find out whether they originally agreed.
Second, even if the principal only seeks to act based on some aggregate of the
experts’ opinions, their method of aggregation may be different from the one
that experts use to collude. For instance, the principal may have a private
opinion on the trustworthiness of each expert and wishes to average the
experts’ opinions with corresponding weights. Collusion among the experts
denies the principal this opportunity. Third, a principal may wish to track
the accuracy of each individual expert (to figure out which experts to trust
more in the future, for instance), and collusion makes this impossible.
Fourth, the space of collusion strategies that constitute arbitrage is large.
In our example above, any report in $[0.546,0.637]$ would guarantee a profit;
and this does not even mention strategies in which experts report different
probabilities. As such, the principal may not even be able to recover basic
information about the experts’ beliefs from their reports.

As we have discussed, preventing arbitrage is impossible if the principal
chooses a proper scoring rule and uses it to reward all of the experts.
However, the principal has more freedom than this: they may choose to make
each expert’s reward depend not only on that expert’s report but also _other_
experts’ reports. [228, §5] ask whether there is any mechanism for rewarding
experts that makes arbitrage impossible, concluding that this “seems
unlikely.” [243] explore this question further, proposing a mechanism that
prevents arbitrage if the experts’ reports are guaranteed to be in the range
$[\epsilon,1-\epsilon]$ for some positive $\epsilon$ (though their mechanism
may require very large payments if $\epsilon$ is small). However, they leave
open Chun and Shachter’s question of whether an incentive-compatible,
arbitrage-free reward mechanism exists.

We resolve this question in the affirmative by exhibiting a class of
incentive-compatible mechanisms in which arbitrage from collusion is
impossible. Our mechanism takes inspiration from Brier’s quadratic scoring
rule, but modifies it to take into account the aggregate performance of the
remaining experts.

###  4.2 Related work

[243] explore the question of whether proper arbitrage-free mechanisms exist
by proving positive results under different relaxations of these constraints.
Their main result is a proper arbitrage-free mechanism under the restriction
that the range of allowed reports is restricted to $[\epsilon,1-\epsilon]$.
However, their mechanism necessitates payments that are exponentially large in
$1/\epsilon$. Alternatively, these payments can be scaled down, but at the
expense of giving essentially zero reward to each expert on the vast majority
of the interval of possible reports, thus providing little incentive for
truthful reporting. They also exhibit a positive result if the properness
criterion is somewhat relaxed to allow for some contract functions that are
weakly proper but not proper.

[217] explore the different but related topic of _arbitrage-free wagering
mechanisms._ In a wagering mechanism, each expert wagers a certain amount of
money along with their report, and the pool of wagers is redistributed among
the experts depending on each expert’s report and wager and the eventual
outcome. In this setting, they define arbitrage as any opportunity for an
individual to risklessly make a profit. That is, an arbitrage opportunity is
one in which an expert may unilaterally deviate by submitting a report that
guarantees a profit no matter the final outcome. This differs from Chun and
Shachter’s definition of arbitrage, which is concerned with riskless profit
opportunities stemming from collusion between experts.

The most well-known wagering mechanism is the _weighted score wagering
mechanism_ , which rewards each expert based on their performance compared to
other experts according to a proper scoring rule. An expert may risklessly
profit from a weighted score wagering mechanism by reporting an aggregate of
other experts’ reports. This is the same aggregate as the one that a coalition
of experts who are rewarded with a proper scoring rule may report in order to
risklessly make a profit in our setting. [217, §4.1] define _no-arbitrage
wagering mechanisms_ , which modify the reallocation rule of weighted score
wagering mechanisms to reward each expert based on their performance relative
to the performance of the aggregate of all other experts’ reports. No-
arbitrage wagering mechanisms can be re-interpreted in our setting as contract
functions that prevent the _entire group of experts_ from colluding. However,
as we discuss in the next section, this is easy to accomplish; we are instead
faced with the challenge of preventing collusion between any coalition of
experts of any size. Thus, our mechanism and theirs share some of the same
spirit, but are different mechanisms that solve different problems.

###  4.3 Preliminaries on contract functions

Contract functions, defined by [228], generalize scoring rules to multiple
experts. We say that there are $m$ experts; for $i\in[m]$, expert $i$ reports
a probability distribution $\mathbf{p}_{i}\in\Delta_{n}$ over $n$ outcomes. We
denote the $j$-th coordinate of $\mathbf{p}_{i}$ as $p_{i,j}$.

A _contract function_ is any function that takes as input the $m$ experts’
reports and the outcome, and outputs the reward of each expert. Formally, a
contract function is any function
$\Pi:(\Delta_{n})^{m}\times[n]\to\mathbb{R}^{m}$; if the experts report
distributions $\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ and the outcome is $j$,
then the vector of expert rewards is
$\Pi(\mathbf{p}_{1},\dots,\mathbf{p}_{m};j)$. We let $\Pi_{i}(\cdot)$ denote
the $i$-th coordinate of $\Pi(\cdot)$, i.e. expert $i$’s reward. We will
generally use $\mathbf{P}$ to denote the $m$-tuple of reports
$(\mathbf{p}_{1},\dots,\mathbf{p}_{m})$.

A contract function is _weakly proper_ if for each $i\in[m]$, expert $i$
maximizes their expected reward by reporting their belief $\mathbf{b}_{i}$, no
matter the reports $\mathbf{p}_{-i}$ of the other experts. Formally, $\Pi$ is
weakly proper if for all $i\in[m]$, for all $\mathbf{b}_{i}$ and all
$\mathbf{p}_{-i}$, $\sum_{j}b_{i,j}\Pi_{i}(\mathbf{x},\mathbf{p}_{-i};j)$ is
maximized at $\mathbf{x}=\mathbf{b}_{i}$. We say that $\Pi$ is _proper_ if
$\mathbf{x}=\mathbf{b}_{i}$ is the unique maximizer, i.e. that an expert does
strictly worse by misreporting their belief.

Our goal is to exhibit a proper contract function that does not permit
arbitrage from collusion. We use the definition of arbitrage given by [243],
which was adapted from [228].

A contract function $\Pi$ _admits arbitrage_ if there is a coalition (i.e.
subset) $C\subseteq[m]$ of experts and $m$-tuples of expert reports
$\mathbf{P}$ and $\mathbf{Q}$, with $\mathbf{p}_{i}=\mathbf{q}_{i}$ for all
$i\not\in C$, such that

$\sum_{i\in C}\Pi_{i}(\mathbf{Q};j)\geq\sum_{i\in C}\Pi_{i}(\mathbf{P};j)$

for all $j\in[n]$, and the inequality is strict for some $j$. We say that
$\Pi$ is _arbitrage-free_ if it does not admit arbitrage. Intuitively, $\Pi$
admits arbitrage if it is possible for a coalition of experts to collude to
misreport their values in such a way that the total reward of the experts in
the coalition ends up larger, no matter the outcome. (Above, the misreport is
$\mathbf{Q}$; the constraint that $\mathbf{p}_{i}=\mathbf{q}_{i}$ for
$i\not\in C$ means that only experts in $C$ change their reports.) If this is
possible, then the experts in $C$ can commit beforehand to a redistribution of
the extra reward in a way that makes every expert in the coalition better off
no matter the eventual outcome $j$.

######  Remark 4.3.1.

Positive affine transformations preserve both properness and arbitrage-
freeness. That is, if $\Pi$ is proper then so is $a\Pi+b$ for any $a>0$ and
$b$, and this is likewise true for arbitrage-freeness.

The question posed by [228] and explored by [243], which we answer
affirmatively in this work, is: Does there exist a proper arbitrage-free
contract function?

In the case of $m=2$ experts, there is a straightforward solution:

$\Pi(\mathbf{p}_{1},\mathbf{p}_{2};j)=\left(s_{\text{quad}}(\mathbf{p}_{1};j)-s_{\text{quad}}(\mathbf{p}_{2};j),s_{\text{quad}}(\mathbf{p}_{2};j)-s_{\text{quad}}(\mathbf{p}_{1};j)\right).$
(4.1)

This contract function is proper because expert 1’s reward is the (proper)
quadratic score of their report plus a term that does not depend on their
report, and likewise for expert 2. It is arbitrage-free because the total
reward of the two experts is $0$ no matter what. Indeed, this contract
function is arbitrage-free with any proper scoring rule in place of the
quadratic scoring rule.

This idea does not extend to $m>2$ experts, because an arbitrage-free contract
function must not admit arbitrage by a coalition of experts of any size. While
it is easy to construct a contract function that does not admit arbitrage by a
coalition of size $m$ (by making the total reward always equal to $0$), this
does not automatically make the contract function free of arbitrage
opportunities for coalitions of sizes between $2$ and $m-1$. In the next
section we address this challenge and exhibit a proper contract function that
is arbitrage-free for $m>2$ experts.

###  4.4 A class of proper arbitrage-free contract functions

Suppose that – as before – there are $m\geq 2$ experts who are forecasting an
event with $n\geq 2$ outcomes. Given experts with reports
$\mathbf{P}=(\mathbf{p}_{1},\dots,\mathbf{p}_{m})$ and a nonempty subset
$S\subseteq[m]$ of the experts, we will let
$\overline{\mathbf{p}}_{S}:=\frac{1}{\left\lvert S\right\rvert}\sum_{i\in
S}\mathbf{p}_{i}$ be the average of the experts’ reports. We will use
$\overline{\mathbf{p}}_{-i}$ to denote
$\overline{\mathbf{p}}_{[m]\setminus\\{i\\}}$.

We now state our main theorem, which exhibits a class of proper, arbitrage-
free contract functions.

######  Theorem 4.4.1.

Let $\alpha$ be a real number such that $\alpha<0$ or $\alpha\geq
2(m-1)^{2}n$. Let $\Pi$ be the contract function defined by

$\Pi_{i}(\mathbf{P};j)=s_{\text{quad}}(\mathbf{p}_{i};j)-(m-1)^{2}s_{\text{quad}}(\overline{\mathbf{p}}_{-i};j)+\alpha\overline{\mathbf{p}}_{-i,j}$

for each $i$, $j$. Then $\Pi$ is proper and arbitrage-free.

Note that in the case of $m=2$, setting $\alpha=0$ yields our aforementioned
solution for two experts in Equation 4.1. Unfortunately, setting $\alpha=0$
for $m>2$ experts causes arbitrage-freeness to fail in certain edge cases.

One can think of the contract function in Theorem 4.4.1 as having two parts.
The first part,
$s_{\text{quad}}(\mathbf{p}_{i};j)-(m-1)^{2}s_{\text{quad}}(\overline{\mathbf{p}}_{-i};j)$,
ensures that any coalition’s total reward depends only on the average of the
coalition’s reports. In effect this significantly limits the degrees of
freedom that a coalition has when colluding. The second part,
$\alpha\overline{\mathbf{p}}_{-i,j}$, ensures that any deviation in this
average report causes a decrease in total reward under at least one outcome.

We first present the proof of Theorem 4.4.1 for $n=2$ outcomes, as this allows
us to simplify notation while still explaining the core ideas.

###### Proof of Theorem 4.4.1 for $n=2$.

First, note that $\Pi$ is proper, because expert $i$’s reward is their
quadratic score plus a term that does not depend on their report. It remains
to show that $\Pi$ is arbitrage-free.

Let $C\subseteq[m]$ be a coalition of experts. Properness entails that no
expert can unilaterally find an arbitrage opportunity, so we may assume that
$\left\lvert C\right\rvert\geq 2$.

For an outcome $j$ and a subset $S\subseteq[m]$, let $p_{S,j}:=\sum_{i\in
S}p_{i,j}$.

######  Lemma 4.4.2.

Let $d=m-1-\frac{\alpha}{4(m-1)}$. The expression for $\Pi_{i}(\mathbf{P};j)$
is equal to

$2(p_{[m],j}-d-1)(p_{[m],j}-2p_{i,j}-d+1)+f(m,\alpha),$ (4.2)

for some function $f$.

###### Proof of Lemma 4.4.2.

For some $f$ (whose exact form does not concern us), we have

$\displaystyle\Pi_{i}(\mathbf{P};j)$
$\displaystyle=s_{\text{quad}}(\mathbf{p}_{i};j)-(m-1)^{2}s_{\text{quad}}(\overline{\mathbf{p}}_{-i};j)+\alpha\overline{\mathbf{p}}_{-i,j}$
$\displaystyle=-2(1-p_{i,j})^{2}-(m-1)^{2}\left(-2\left(1-\frac{p_{-i,j}}{m-1}\right)^{2}\right)+\frac{\alpha}{m-1}p_{-i,j}$
$\displaystyle=-2(1-p_{i,j})^{2}+2(m-1-p_{-i,j})^{2}+\frac{\alpha}{m-1}p_{-i,j}$
$\displaystyle=-2(1-p_{i,j})^{2}+2\left(d-p_{-i,j}\right)^{2}+f(m,\alpha)$
$\displaystyle=2\left(d-p_{-i,j}+(1-p_{i,j})\right)\left(d-p_{-i,j}-(1-p_{i,j})\right)+f(m,\alpha)$
$\displaystyle=2(p_{[m],j}-d-1)(p_{[m],j}-2p_{i,j}-d+1)+f(m,\alpha),$

as desired. ∎

Equation 4.2 makes it evident that rewards add nicely across experts in a
coalition $C$, as the first term of the product is the same for all experts in
$C$. We will use the notation $\Pi_{C}(\mathbf{P};j)$ to denote $\sum_{i\in
C}\Pi_{i}(\mathbf{P};j)$. The key idea is that, as we are about to show, if
the reports of experts not in $C$ are held fixed, $\Pi_{C}(\mathbf{P};j)$
depends _only_ on $p_{C,j}$. Thus, the experts in $C$ have only one degree of
freedom available for colluding: the sum of their reports.

We write $\overline{C}$ to mean $[m]\setminus C$. We have

$\displaystyle\Pi_{C}(\mathbf{P};j)$ $\displaystyle=2\sum_{i\in
C}(p_{[m],j}-d-1)(p_{[m],j}-2p_{i,j}-d+1)+\left\lvert C\right\rvert
f(m,\alpha)$ $\displaystyle=2(p_{C,j}+p_{\overline{C},j}-d-1)((\left\lvert
C\right\rvert-2)p_{C,j}+\left\lvert
C\right\rvert(p_{\overline{C},j}-d+1))+\left\lvert C\right\rvert f(m,\alpha)$
$\displaystyle=2((\left\lvert C\right\rvert-2)p_{C,j}^{2}+2((\left\lvert
C\right\rvert-1)(p_{\overline{C},j}-d)+1)p_{C,j})+g(m,\alpha,\left\lvert
C\right\rvert,p_{\overline{C},j}),$ (4.3)

for some function $g$. Now, recall the constraints on $\alpha$ in Theorem
4.4.1, and note that $\alpha<0\Leftrightarrow d>m-1$ and $\alpha\geq
4(m-1)^{2}\Leftrightarrow d\leq 0$. With this in mind, we now prove the
following claim, which is sufficient to complete our proof.

######  Claim 4.4.3.

If $d\leq 0$, then for each $j$ and for all possible reports of experts not in
$C$, $\Pi_{C}(\mathbf{P};j)$ is a strictly increasing function of $p_{C,j}$.
If $d>m-1$, it is a strictly decreasing function of $p_{C,j}$.

By virtue of deriving Equation 4.4, we have already proven the most difficult
part of Claim 4.4.3, which is that $\Pi_{C}(\mathbf{P};j)$ is a function of
(i.e. determined by) $p_{C,j}$. Why is this function’s monotonicity sufficient
to complete our proof of Theorem 4.4.1? Since $p_{C,1}+p_{C,2}=\left\lvert
C\right\rvert$, it follows from Claim 4.4.3 that for $d\leq 0$ and $d>m-1$,
colluding in a way that increases the total reward in the case of one outcome
necessarily decreases it in the case of the other outcome.

###### Proof of Claim 4.4.3.

We first consider the case of $\left\lvert C\right\rvert=2$. In this case we
have

$\Pi_{C}(\mathbf{P};j)=4(p_{\overline{C},j}-d+1)p_{C,j}+g(m,\alpha,\left\lvert
C\right\rvert,p_{\overline{C},j}).$

Now, $0\leq p_{\overline{C},j}\leq m-2$, which means that $1-d\leq
p_{\overline{C},j}-d+1\leq m-1-d$. If $d\leq 0$, this quantity is guaranteed
to be strictly positive, so $\Pi_{C}(\mathbf{P};j)$ is a strictly increasing
function of $p_{C,j}$; if $d>m-1$, it is guaranteed to be negative, so
$\Pi_{C}(\mathbf{P};j)$ is a strictly decreasing function of $p_{C,j}$.

Now assume that $\left\lvert C\right\rvert>2$. In this case, it follows from
Equation 4.4 that $\Pi_{C}(\mathbf{P};j)$ is a parabola with a minimum at

$\frac{(\left\lvert C\right\rvert-1)(d-p_{\overline{C},j})-1}{\left\lvert
C\right\rvert-2}.$

We wish to show that if $d\leq 0$ then this quantity is at most $0$, and that
if $d>m-1$ then it is at least $\left\lvert C\right\rvert$ (since the range of
possible values of $p_{C,j}$ is $[0,\left\lvert C\right\rvert]$). If $d\leq 0$
then, since $p_{\overline{C},j}\geq 0$, we have

$\frac{(\left\lvert C\right\rvert-1)(d-p_{\overline{C},j})-1}{\left\lvert
C\right\rvert-2}\leq\frac{-1}{\left\lvert
C\right\rvert-2}\leq\frac{-1}{m-2}\leq 0.$

If $d>m-1$ then, since $p_{\overline{C},j}\leq m-\left\lvert C\right\rvert$,
we have

$\frac{(\left\lvert C\right\rvert-1)(d-p_{\overline{C},j})-1}{\left\lvert
C\right\rvert-2}\geq\frac{(\left\lvert C\right\rvert-1)^{2}-1}{\left\lvert
C\right\rvert-2}=\left\lvert C\right\rvert.$

∎

Having proved the claim, we have completed the proof of Theorem 4.4.1 for
$n=2$. ∎

We note that setting $\alpha=0$ results in a contract function that is
arbitrage-free except in one edge case: in the event that all but two experts
assign a probability of zero to some outcome $j$, the remaining experts can
collude to adjust their probabilities – in particular, lowering the total
probability they assign to outcome $j$ – in a way that increases their total
reward under outcome $j$ and leaves the remaining rewards unchanged. If we are
willing to put this exception aside (e.g. if we only allow reports strictly
between $0$ and $1$), then we may regard the resulting contract function
$\Pi_{i}(\mathbf{P};j)=s_{\text{quad}}(\mathbf{p}_{i};j)-(m-1)^{2}s_{\text{quad}}(\overline{\mathbf{p}}_{-i};j)$
as arbitrage-free. This contract function has a natural interpretation: it
rewards an expert for the accuracy of their forecast but penalizes the expert
if others are accurate in aggregate. This rule is reminiscent of the no-
arbitrage wagering mechanism for the quadratic scoring rule given by [217],
except that the penalty is multiplied by a factor of $(m-1)^{2}$.

We now present the proof of Theorem 4.4.1 in full generality.

###### Proof of Theorem 4.4.1 for general $n$.

First, note that $\Pi$ is proper, because expert $i$’s reward is their
quadratic score plus a term that does not depend on their report. It remains
to show that $\Pi$ is arbitrage-free.

Let $C\subseteq[m]$ be a coalition of experts. Properness entails that no
expert can unilaterally find an arbitrage opportunity, so we may assume that
$\left\lvert C\right\rvert\geq 2$.

For an outcome $j$ and a subset $S\subseteq[m]$, let $p_{S,j}:=\sum_{i\in
S}p_{i,j}$. Let $d=m-1-\frac{\alpha}{2(m-1)}$. For some $f$ whose particular
form does not concern us, we have

$\displaystyle\Pi_{i}(\mathbf{P};j)=s_{\text{quad}}(\mathbf{p}_{i};j)-(m-1)^{2}s_{\text{quad}}(\overline{\mathbf{p}}_{-i};j)+\alpha\overline{\mathbf{p}}_{-i,j}$
$\displaystyle=(m-1)^{2}\left(1-\frac{1}{m-1}p_{-i,j}\right)^{2}-(1-p_{i,j})^{2}+\sum_{\ell\neq
j}\left((m-1)^{2}\left(\frac{1}{m-1}p_{-i,\ell}\right)^{2}-p_{i,\ell}^{2}\right)+\frac{\alpha}{m-1}p_{-i,j}$
$\displaystyle=(d-p_{-i,j})^{2}-(1-p_{i,j})^{2}+\sum_{\ell\neq
j}\left(p_{-i,\ell}^{2}-p_{i,\ell}^{2}\right)+f(m,n,\alpha)$
$\displaystyle=(d-p_{-i,j}+(1-p_{i,j}))(d-p_{-i,j}-(1-p_{i,j}))+\sum_{\ell\neq
j}(p_{-i,\ell}+p_{i,\ell})(p_{-i,\ell}-p_{i,\ell})+f(m,n,\alpha)$
$\displaystyle=(p_{[m],j}-d-1)(p_{[m],j}-2p_{i,j}-d+1)+\sum_{\ell\neq
j}p_{[m],\ell}(p_{[m],\ell}-2p_{i,\ell})+f(m,n,\alpha).$

We will use the notation $\Pi_{C}(\mathbf{P};j)$ to denote $\sum_{i\in
C}\Pi_{i}(\mathbf{P};j)$. We also write $\overline{C}$ to mean $[m]\setminus
C$ and $\mathbf{P}_{\overline{C}}$ to mean the collection of reports
$\mathbf{p}_{i}$ for $i\in\overline{C}$. We have

$\displaystyle\Pi_{C}(\mathbf{P};j)=\sum_{i\in
C}\left((p_{[m],j}-d-1)(p_{[m],j}-2p_{i,j}-d+1)+\sum_{\ell\neq
j}p_{[m],\ell}(p_{[m],\ell}-2p_{i,\ell})\right)+\left\lvert C\right\rvert
f(m,n,\alpha)$ $\displaystyle=(p_{C,j}+p_{\overline{C},j}-d-1)((\left\lvert
C\right\rvert-2)p_{C,j}+\left\lvert C\right\rvert(p_{\overline{C},j}-d+1))$
$\displaystyle\qquad+\sum_{\ell\neq
j}(p_{C,\ell}+p_{\overline{C},\ell})(\left\lvert C\right\rvert
p_{\overline{C},\ell}+(\left\lvert C\right\rvert-2)p_{C,\ell})+\left\lvert
C\right\rvert f(m,n,\alpha)$ $\displaystyle=(\left\lvert
C\right\rvert-2)p_{C,j}^{2}+((2\left\lvert
C\right\rvert-2)(p_{\overline{C},j}-d)+2)p_{C,j}$
$\displaystyle\quad+\sum_{\ell\neq j}\left((\left\lvert
C\right\rvert-2)p_{C,\ell}^{2}+(2\left\lvert
C\right\rvert-2)p_{\overline{C},\ell}p_{C,\ell}\right)+g(m,n,\alpha,\left\lvert
C\right\rvert,\mathbf{P}_{\overline{C}})$ $\displaystyle=(2-(2\left\lvert
C\right\rvert-2)d)p_{C,j}+\sum_{\ell}\left((\left\lvert
C\right\rvert-2)p_{C,\ell}^{2}+(2\left\lvert
C\right\rvert-2)p_{\overline{C},\ell}p_{C,\ell}\right)+g(m,n,\alpha,\left\lvert
C\right\rvert,\mathbf{P}_{\overline{C}})$

for some function $g$. Consider a different vector $\mathbf{Q}$ that agrees
with $\mathbf{P}$ on $\overline{C}$.

##### Case 1: $\alpha<0$.

In this case, $2-(2\left\lvert C\right\rvert-2)d<2-(2\left\lvert
C\right\rvert-2)(m-1)$. Let $\tilde{j}=\arg\max_{\ell}q_{C,\ell}-p_{C,\ell}$,
and let $\epsilon=q_{C,\tilde{j}}-p_{C,\tilde{j}}$. We note that

$\sum_{\ell}q_{C,\ell}^{2}-p_{C,\ell}^{2}=\sum_{\ell}(q_{C,\ell}-p_{C,\ell})(q_{C,\ell}+p_{C,\ell})\leq\epsilon\sum_{\ell}(q_{C,\ell}+p_{C,\ell})=2\epsilon\left\lvert
C\right\rvert.$

Thus, we have

$\displaystyle\Pi_{C}(\mathbf{Q};\tilde{j})-\Pi_{C}(\mathbf{P};\tilde{j})$
$\displaystyle=(2-(2\left\lvert
C\right\rvert-2)d)\epsilon+\sum_{\ell}(\left\lvert
C\right\rvert-2)(q_{C,\ell}^{2}-p_{C,\ell}^{2})+(2\left\lvert
C\right\rvert-2)(q_{C,\ell}-p_{C,\ell})p_{\overline{C},\ell}$
$\displaystyle\leq(2-(2\left\lvert C\right\rvert-2)d)\epsilon+(\left\lvert
C\right\rvert-2)\cdot 2\epsilon\left\lvert C\right\rvert+(2\left\lvert
C\right\rvert-2)(m-\left\lvert C\right\rvert)\epsilon$
$\displaystyle\leq(2-(2\left\lvert C\right\rvert-2)(m-1))\epsilon+(\left\lvert
C\right\rvert-2)\cdot 2\epsilon\left\lvert C\right\rvert+(2\left\lvert
C\right\rvert-2)(m-\left\lvert C\right\rvert)\epsilon$
$\displaystyle=2\epsilon(1+(\left\lvert C\right\rvert-2)\left\lvert
C\right\rvert+(\left\lvert C\right\rvert-1)(1-\left\lvert C\right\rvert))=0,$

with equality in the second step only when $\epsilon=0$, i.e.
$q_{C,\ell}=p_{C,\ell}$ for all $\ell$. Thus, either the total reward of the
experts in $C$ is the same under $\mathbf{Q}$ as under $\mathbf{P}$ for every
outcome, or it is strictly smaller under $\mathbf{Q}$ in the case of outcome
$\tilde{j}$.

##### Case 2: $\alpha\geq 2(m-1)^{2}n$.

In this case, $2-(2\left\lvert C\right\rvert-2)d\geq 2+(2\left\lvert
C\right\rvert-2)(m-1)(n-1)$. $\tilde{j}=\arg\max_{\ell}p_{C,\ell}-q_{C,\ell}$,
and let $\epsilon=p_{C,\tilde{j}}-q_{C,\tilde{j}}$. Since
$\sum_{\ell}(q_{C,\ell}-p_{C,\ell})=0$, it follows that
$q_{C,\ell}-p_{C,\ell}\leq(n-1)\epsilon$ for all $\ell$. We note that

$\displaystyle\sum_{\ell}q_{C,\ell}^{2}-p_{C,\ell}^{2}$
$\displaystyle\leq\sum_{\ell}(q_{C,\ell}+p_{C,\ell})\max(q_{C,\ell}-p_{C,\ell},0)$
$\displaystyle\leq 2\left\lvert
C\right\rvert\sum_{\ell}\max(q_{C,\ell}-p_{C,\ell},0)\leq 2\left\lvert
C\right\rvert(n-1)\epsilon.$

We also have that

$\sum_{\ell}(q_{C,\ell}-p_{C,\ell})p_{\overline{C},\ell}\leq(m-\left\lvert
C\right\rvert)\sum_{\ell}\max(q_{C,\ell}-p_{C,\ell},0)\leq(m-\left\lvert
C\right\rvert)(n-1)\epsilon.$

Therefore,

$\displaystyle\Pi_{C}(\mathbf{Q};\tilde{j})-\Pi_{C}(\mathbf{P};\tilde{j})=-(2-(2\left\lvert
C\right\rvert-2)d)\epsilon+\sum_{\ell}(\left\lvert
C\right\rvert-2)(q_{C,\ell}^{2}-p_{C,\ell}^{2})+(2\left\lvert
C\right\rvert-2)(q_{C,\ell}-p_{C,\ell})p_{\overline{C},\ell}$
$\displaystyle\leq-(2-(2\left\lvert C\right\rvert-2)d)\epsilon+(\left\lvert
C\right\rvert-2)\cdot 2\left\lvert C\right\rvert(n-1)\epsilon+(2\left\lvert
C\right\rvert-2)\cdot(m-\left\lvert C\right\rvert)(n-1)\epsilon$
$\displaystyle=2\epsilon(-1-(\left\lvert
C\right\rvert-1)(m-1)(n-1)+(n-1)(m(\left\lvert C\right\rvert-1)-\left\lvert
C\right\rvert))$ $\displaystyle=2\epsilon(-1-(n-1))=-2\epsilon n\leq 0,$

with equality in the last step only when $\epsilon=0$, i.e.
$q_{C,\ell}=p_{C,\ell}$ for all $\ell$. As in the previous case, this means
that either the total reward of the experts in $C$ is the same under
$\mathbf{Q}$ as under $\mathbf{P}$ for every outcome, or it is strictly
smaller under $\mathbf{Q}$ in the case of outcome $\tilde{j}$. This completes
the proof. ∎

###  4.5 Future directions in arbitrage-freeness

While the contract functions defined in Theorem 4.4.1 are proper and
arbitrage-free, there are other desirable notions of arbitrage-freeness that
they do not satisfy. To see this, consider the following concrete example:
suppose that there are two outcomes, and all $m>2$ experts think that Outcome
1 will happen with probability $1$. Suppose that $\alpha$ is chosen to be only
slightly negative – very close to zero. In that case, all experts reporting
their true belief is just about the _worst_ possible outcome for the experts:
they each believe that they will each receive a score of $\alpha$. By
comparison, if all experts were to instead lie and report
$\mathbf{p}_{i}=(0,1)$ (i.e. that Outcome 2 will happen with probability $1$),
then each expert believes that they will receive reward $2((m-1)^{2}-1)$. That
is, the experts are much better off if everyone lies than if everyone tells
the truth.

Why is this not a counterexample to arbitrage-freeness? Well, if Outcome 2
happens, then the experts will get reward $2((m-1)^{2}-1)$ if they tell the
truth and $\alpha$ if they lie. The experts believe that Outcome 2 will happen
with probability $0$, but if Outcome 2 _does_ happen, then they will end up
better off if they tell the truth. However, since every expert believes that
Outcome 1 is guaranteed to happen, it seems that in practice the experts would
want to collude in this situation: they believe that they can collude to
guarantee themselves a greater profit with probability 100%.

How might we expand the definition of arbitrage to include the collusion
scenario we just described? One way is to say that $\Pi$ admits arbitrage if
there is a collusion strategy for the experts in $C$ that, in the opinion of
every expert in $C$, increases the expected total reward of the experts in
$C$. Formally:

######  Definition 4.5.1.

A contract function $\Pi$ _admits expected arbitrage_ if there is a coalition
$C\subseteq[m]$ of experts and vectors of reports
$\mathbf{P}=(\mathbf{p}_{1},\dots,\mathbf{p}_{m})$,
$\mathbf{Q}=(\mathbf{q}_{1},\dots,\mathbf{q}_{m})$, with $p_{i}=q_{i}$ if
$i\not\in C$, such that for all $i\in C$ we have

$\sum_{j\in[n]}p_{i,j}\sum_{k\in
C}\Pi_{k}(\mathbf{P};j)\leq\sum_{j\in[n]}p_{i,j}\sum_{k\in
C}\Pi_{k}(\mathbf{Q};j),$

and the inequality is strict for some $i$. We say that $\Pi$ is _free of
expected arbitrage_ if it does not admit expected arbitrage.

Up to edge scenarios,111It is possible for a coalition of experts to collude
in a way that increases their total reward under an outcome to which they all
assign probability $0$. If their reward in the case of all other outcome is
unchanged, such a deviation would constitute arbitrage but not expected
arbitrage. if a contract function admits arbitrage then it also admits
expected arbitrage. On the other hand, in the case of $m>2$ experts, the
scoring rules described by Theorem 4.4.1 (which do not admit arbitrage) do
admit expected arbitrage. As an example, consider two outcomes and $m$ experts
with beliefs $(\frac{1}{2},\frac{1}{2})$. If all experts report their beliefs,
then each expert’s reward is $\frac{\alpha}{2}+\frac{1}{2}((m-1)^{2}-1)$, no
matter the outcome. If all experts instead report $(1,0)$ then each expert
expects a reward of $\frac{\alpha}{2}+(m-1)^{2}-1$, which is larger. This
raises the following question:

######  Question 4.5.2.

Is there a proper scoring rule that does not admit expected arbitrage?

We can define an even stronger notion of arbitrage-freeness:

######  Definition 4.5.3.

We say that $\Pi$ _admits redistributional arbitrage_ if there is:

  * •

A coalition $C\subseteq[m]$ of experts

  * •

A _redistribution agreement_ $A$ that takes as input a list of probability
distributions $\mathbf{X}=(\mathbf{x}_{1},\dots,\mathbf{x}_{m})$, another list
of probability distributions
$\mathbf{Y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{m})$ such that
$\mathbf{x}_{i}=\mathbf{y}_{i}$ for any $i\not\in C$,222Here, the
$\mathbf{x}_{i}$ represent the reports given to $\Pi$, the $\mathbf{y}_{i}$
represent the pre-collusion probabilities (these can be thought of as the
“true beliefs”), and $j$ represents the outcome that happens. and an outcome
$j$, and outputs a list of rewards, one for each $i\in C$, such that

$\sum_{i\in C}A_{i}(\mathbf{X};\mathbf{Y};j)=\sum_{i\in
C}\Pi_{i}(\mathbf{X};j).$

(We call this the _budget balance_ property of $A$.) …

…such that there are vectors of reports
$\mathbf{P}=(\mathbf{p}_{1},\dots,\mathbf{p}_{m})$,
$\mathbf{Q}=(\mathbf{q}_{1},\dots,\mathbf{q}_{m})$, with $p_{i}=q_{i}$ if
$i\not\in C$, so that for all $i\in C$ we have

$\sum_{j\in[n]}p_{i,j}A_{i}(\mathbf{Q};\mathbf{P};j)\geq\sum_{j\in[n]}p_{i,j}\Pi_{i}(\mathbf{P};j),$

and the inequality is strict for some $i$. We say that $\Pi$ is _free of
redistribution arbitrage_ if it does not admit expected arbitrage.

We show that every $\Pi$ that admits expected arbitrage also admits
redistributional arbitrage – that is, that if there is a misreport that each
experts believes will make the _pool_ of colluding experts better off in
expectation, then there is a way to redistribute the earnings in a way that
makes each expert believe that _they_ will be better off in expectation.

######  Theorem 4.5.4.

Every contract function $\Pi$ that admits expected arbitrage admits
redistributional arbitrage.

###### Proof.

Let $\Pi$ be a contract function that admits expected arbitrage, and let $C$,
$\mathbf{P}$, and $\mathbf{Q}$ be as in Definition 4.5.1. For any
$\mathbf{X}=(\mathbf{x}_{1},\dots,\mathbf{x}_{m})$ and
$\mathbf{Y}=(\mathbf{y}_{1},\dots,\mathbf{y}_{m})$ that coincide outside of
$C$, let

$W(\mathbf{X};\mathbf{Y};j):=\sum_{i\in C}\Pi_{i}(\mathbf{X};j)-\sum_{i\in
C}\Pi_{i}(\mathbf{Y};j)$

be the total gain of experts in $C$ by colluding to report $X$ instead of $Y$.
Thus, $\sum_{j}p_{i,j}W(\mathbf{Q};\mathbf{P};j)\geq 0$ for all $i$ and the
inequality is strict for some $i$. Define

$A_{i}(\mathbf{X};\mathbf{Y};j):=\Pi_{i}(\mathbf{Y};j)+\frac{1}{\left\lvert
C\right\rvert}W(\mathbf{X};\mathbf{Y};j).$

(Clearly $A$ is budget-balanced.) Then for any $i\in C$ we have

$\displaystyle\sum_{j}p_{i,j}A_{i}(\mathbf{Q};\mathbf{P};j)$
$\displaystyle=\sum_{j}p_{i,j}\left(\Pi_{i}(\mathbf{P};j)+\frac{1}{\left\lvert
C\right\rvert}W(\mathbf{Q};\mathbf{P};j)\right)$
$\displaystyle\geq\sum_{j}p_{i,j}\Pi_{i}(\mathbf{P};j),$

with the inequality strict for some $i$, as desired. ∎

We close with the question analogous to Question 4.5.2 for this stronger
notion:

######  Question 4.5.5.

Is there a proper scoring rule that does not admit redistributional arbitrage?

## Quasi-arithmetic pooling

_This chapter presents “From Proper Scoring Rules to Max-Min Optimal Forecast
Aggregation”[307], although the contents of Section 5.5 are original to this
thesis. It assumes background on proper scoring rules presented in Section
2.1, as well as background on forecast aggregation presented in Section 2.2._

_Summary:_ This chapter forges a strong connection between two seemingly
unrelated forecasting problems: incentive-compatible forecast elicitation and
forecast aggregation. We have previously discussed proper scoring rules as a
solution to the former problem (see Section 2.1). To each proper scoring rule
$s$ we associate a corresponding method of aggregation, mapping expert
forecasts and expert weights to a “consensus forecast,” which we call _quasi-
arithmetic (QA) pooling_ with respect to $s$. We justify this correspondence
in several ways:

  * •

QA pooling with respect to the two most well-studied scoring rules (quadratic
and logarithmic) corresponds to the two most well-studied forecast aggregation
methods (linear and logarithmic).

  * •

Given a scoring rule $s$ used for payment, a forecaster agent who sub-
contracts several experts, paying them in proportion to their weights, is best
off aggregating the experts’ reports using QA pooling with respect to $s$,
meaning this strategy maximizes its worst-case profit (over the possible
outcomes).

  * •

The score of an aggregator who uses QA pooling is concave in the experts’
weights. As a consequence, online gradient descent can be used to learn
appropriate expert weights from repeated experiments with low regret.

  * •

QA pooling can be used to define overconfidence with respect to a scoring
rule. The resulting notion of overconfidence turns out to be equivalent to
another natural definition of overconfidence.

  * •

The class of all QA pooling methods is characterized by a natural set of
axioms (generalizing classical work by Kolmogorov on quasi-arithmetic means).

###  5.1 Introduction and motivation

####  5.1.1 Choice of scoring rule as a value judgment

There are infinitely many proper scoring rules. How might a principal go about
deciding which one to use? To gain some intuition, recall the quadratic and
logarithmic scoring rules from Section 2.1:

$\displaystyle s_{\text{quad}}(\mathbf{x};j)$
$\displaystyle:=-(1-x_{j})^{2}-\sum_{j^{\prime}\neq j}x_{j^{\prime}}^{2}$
$\displaystyle s_{\text{log}}(\mathbf{x};j)$ $\displaystyle:=\ln(x_{j})$

Let us consider the quadratic and logarithmic scoring rules in the case of a
binary Yes/No outcome. In Figure 5.1, for both scoring rules, we show the
difference between the expert’s score if a given outcome happens and their
score if it does not happen, as a function of the probability that they assign
to the outcome.111We scale down the logarithmic rule by a factor of $2\ln 2$
to make the two rules comparable. The factor $2\ln 2$ was chosen to make the
range of values taken on by the expected score functions of the two scoring
rules the same.

Figure 5.1: Difference between expert’s score if an outcome happens and if it
does not happen, as a function of the expert’s report, for the quadratic and
logarithmic scoring rules. For example, if the expert reports a 70%
probability of an outcome, then under the quadratic rule they receive a score
of $-\left\lVert(0.7,0.3)-(1,0)\right\rVert_{2}^{2}=-0.18$ if the outcome
happens and $-\left\lVert(0.7,0.3)-(0,1)\right\rVert_{2}^{2}=-0.98$ if it does
not: a difference of $0.8$. If scored with the logarithmic rule, this
difference would be $0.61$.

For the quadratic scoring rule, this difference scales linearly with the
expert’s report. Meanwhile, for the logarithmic rule, the difference changes
more slowly than for the quadratic rule for probabilities near 50%, but much
more quickly at the extremes. Informally speaking, this means that the
logarithmic rule indicates a preference (of the elicitor) for high precision
close to $0$ and $1$, while the quadratic rule indicates a more even
preference for precision across $[0,1]$. Put another way, an elicitor who
chooses to use the logarithmic scoring rule renders a judgment that the
probabilities $0.01$ and $0.001$ are qualitatively quite different; one who
uses the quadratic rule indicates that these probabilities are very similar.

Now, recall from Section 2.2 the two most widely-used forecast aggregation
methods: linear and logarithmic pooling. Given probabilistic forecasts
$\mathbf{x}_{1},\dots,\mathbf{x}_{m}$, the linear pool with weights
$w_{1},\dots,w_{m}$ (adding to $1$) is given by the weighted arithmetic mean:
$\mathbf{x}^{*}=\sum_{i}w_{i}\mathbf{x}_{i}$. Meanwhile, the logarithmic pool
is given by the (renormalized) geometric mean:
$x^{*}(j)=c\prod_{i=1}^{m}(x_{i}(j))^{w_{i}}$.

On its surface, the _elicitation_ of forecasts has seemingly little to do with
their _aggregation_. However, given that the choice of scoring rule implies a
subjective judgment about how different probabilities compare to one another,
it makes sense to apply this judgment to the aggregation of forecasts as well.

As an example, consider the setting of weather prediction, with models playing
the role of experts. In such contexts we often care about low-probability
extreme events: a 0.1% chance of an imminent major hurricane may not be worth
preparing for; a 1% chance could mean significant preparations, and a 10%
chance could mean mandatory evacuations. The need to distinguish very unlikely
events from somewhat unlikely events has two consequences. First, as discussed
above, this is a reason to use the logarithmic scoring rule to assess the
quality of weather models. Second, we wish to avoid the failure mode in which
an ill-informed forecaster assigns a high probability due to lack of evidence
and thereby drowns out a better-informed low-probability forecast. We would
expect to encounter this failure mode with linear pooling; for example, if the
more informed model predicts a 0.1% chance and the less informed model
predicts a 20% chance, linear pooling with equal weights222Assigning equal
weights makes sense when there is not enough information to predict in advance
which model will be less informed. would predict roughly a 10% chance.
Logarithmic pooling, by contrast, assigns roughly a 1.6% chance to the event,
avoiding this failure mode. In general, a calibrated model that predicts a
very low probability must have good evidence, so it may make sense to give the
model more weight.

By contrast, a consultant whose job is to determine the closest races in an
election may not much care about the difference between a 0.1% and a 1% chance
of victory. After all, attention and resources are generally devoted to races
with highly uncertain outcomes. As such, it might make sense to assess the
qualities of forecast models using the quadratic scoring rule. Similarly,
without a compelling reason to pay extra attention to extreme probabilities,
it may make more sense to simply take the average of the forecasts’ opinions.

In the case of extreme weather prediction, we have argued in favor of using
the logarithmic scoring rule to assess the models and the logarithmic pooling
method to aggregate them, for similar reasons. In the case of political
prediction for targeting close races, we have argued in favor of the quadratic
scoring rule and linear pooling, also for similar reasons. Could there be a
formal connection between proper scoring rules and forecast aggregation
methods that captures this intuition? This brings us to the main focus of this
work: namely, we prove a novel correspondence between proper scoring rules and
forecast aggregation methods.

####  5.1.2 Our definitions

Recall from Section 2.1 the _Savage representation_ of a proper scoring rule:

$s(\mathbf{x};j)=G(\mathbf{x})+\left\langle\boldsymbol{\delta}_{j}-\mathbf{x},\mathbf{g}(\mathbf{x})\right\rangle$
(5.1)

where $G$ is the expected score function of $s$ and $\mathbf{g}$ is the
gradient of $G$. The function $\mathbf{g}$, which will be central to our work,
describes the difference in the expert’s score depending on which outcome
happens. More precisely, the vector
$(s(\mathbf{x};j_{1}),\dots,s(\mathbf{x};j_{n}))$ is exactly the vector
$\mathbf{g}(\mathbf{x})$, except possibly for a uniform translation in all
coordinates. Put otherwise, for any two outcomes $j_{1}$ and $j_{2}$, we have
$g_{1}(\mathbf{x})-g_{2}(\mathbf{x})=s(\mathbf{x};j_{1})-s(\mathbf{x};j_{2})$
(this can be verified from Equation 5.1). This is precisely the quantity
plotted in Figure 5.1 for the quadratic and logarithmic scoring rules, if
$j_{1}$ is “Yes” and $j_{2}$ is “No.” This observation about the function
$\mathbf{g}$ motivates the correspondence that we will establish between
proper scoring rules and forecast aggregation methods.

##### Quasi-arithmetic pooling

We can now define the aforementioned correspondence between proper scoring
rules and forecast aggregation methods. Given a proper scoring rule $s$ used
for elicitation, and given $m$ probability distributions
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ and expert weights $w_{1},\dots,w_{m}$,
the aggregate distribution $\mathbf{p}^{*}$ that we suggest is the one
satisfying

$\mathbf{g}(\mathbf{p}^{*})=\sum_{i=1}^{m}w_{i}\mathbf{g}(\mathbf{p}_{i}).$

(In Section 5.2 we will define this notion more precisely using subgradients
of $G$ instead of gradients; this will ensure that $\mathbf{p}^{*}$ is well
defined, i.e. that it exists and is unique.) This definition of
$\mathbf{p}^{*}$ can be restated as the forecast that minimizes the weighted
average Bregman divergence (with respect to $G$) to all experts’ forecasts.

We refer to this pooling method as _quasi-arithmetic pooling_ with respect to
$\mathbf{g}$ (or the scoring rule $s$), or _QA pooling_ for short.333This term
comes from the notion of quasi-arithmetic means: given a continuous, strictly
increasing function $f$ and values $x_{1},\dots,x_{m}$ , the _quasi-arithmetic
mean with respect to $f$_ of these values is $f^{-1}(1/m\sum_{i}f(x_{i}))$. To
get a sense of QA pooling, let us determine what this method looks like for
the quadratic and logarithmic scoring rules.

##### QA pooling with respect to the quadratic scoring rule

Recall from Section 2.1 that the expected score function $G_{\text{quad}}$ of
the quadratic scoring rule $s_{\text{quad}}$ is equal to
$\sum_{j}x_{j}^{2}-1$. We thus have
$\mathbf{g}_{\text{quad}}(\mathbf{x})=(2x_{1},\dots,2x_{n})$, so we are
looking for the $\mathbf{p}^{*}$ such that

$(2p^{*}(1),\dots,2p^{*}(n))=\sum_{i=1}^{m}w_{i}(2p_{i}(1),\dots,2p_{i}(n)).$

This is $\mathbf{p}^{*}=\sum_{i=1}^{m}w_{i}\mathbf{p}_{i}$. Therefore, _QA
pooling for the quadratic scoring rule is precisely linear pooling,_ which we
introduced in Section 2.2 as the simplest and most widely-used forecast
aggregation method.

##### QA pooling with respect to the logarithmic scoring rule

Recall that the expected score function $G_{\text{log}}$ of the logarithmic
scoring rule $s_{\text{log}}$ is equal to $\sum_{j}x_{j}\ln(x_{j})$. We thus
have $\mathbf{g}_{\log}(\mathbf{x})=(\ln x_{1}+1,\dots,\ln x_{n}+1)$, so we
are looking for the $\mathbf{p}^{*}$ such that

$(\ln p^{*}(1)+1,\dots,\ln p^{*}(n)+1)=\sum_{i=1}^{m}w_{i}(\ln
p_{i}(1)+1,\dots,\ln p_{i}(n)+1).$

By exponentiating the components on both sides, we find that
$p^{*}(j)=c\prod_{i=1}^{n}(p_{i}(j))^{w_{i}}$ for all $j$, for some
proportionality constant $c$. _This is precisely the definition of the
logarithmic pooling method,_ which we introduced in Section 2.2 as a simple,
well-motivated, and effective way of aggregating probabilistic forecasts. (The
constant $c$ comes from the fact that values of $\mathbf{g}(\cdot)$ should be
interpreted modulo translation by the all-ones vector; see Remark 5.2.2.)

The fact that this pooling scheme maps the two most well-studied scoring rules
to the two most well-studied forecast aggregation methods has not been noted
previously, to our knowledge. This correspondence suggests that – beyond just
our earlier informal justification – QA pooling with respect to a given
scoring rule may be a fundamental concept. The rest of this work argues that
this is indeed the case.

This correspondence may have practical implications for forecasters. While the
quadratic and logarithmic scoring rules are both ubiquitous in practice,
linear pooling is far more common than logarithmic pooling [320]. This is
despite empirical evidence that logarithmic pooling often outperforms linear
pooling [331]. The connection that we establish between the logarithmic
scoring rule and logarithmic pooling provides further reason to think that
logarithmic pooling has been somewhat overlooked.

####  5.1.3 Our results

##### (Section 5.3) Max-min optimality

Suppose that a principal asks you to issue a forecast and will pay you
according to $s$. You are not knowledgeable on the subject but know some
experts whom you trust on the matter (perhaps to varying degrees). You sub-
contract the experts, promising to pay each expert $i$ according to
$w_{i}\cdot s$. By using QA pooling according to $s$ on the experts’
forecasts, you guarantee yourself a profit; in fact, this strategy maximizes
your worst-case profit, and is the unique such report. Furthermore, this
profit is the same for all outcomes. This fact can be interpreted to mean that
you have, in a sense, pooled the forecasts “correctly”: you do not care which
outcome will come to pass, which means that you have correctly factored the
expert opinions into your forecast. We give an additional interpretation of
this optimality notion as maximizing an aggregator’s guaranteed improvement
over choosing an expert at random.

##### (Section 5.4) Learning expert weights

Pooling forecasts entails assigning weights to experts. Where do these weights
come from? How might one learn them from experience?

Suppose we have a fixed proper scoring rule $s$, and further consider fixing
the reports of the $m$ experts as well as the eventual outcome. One can ask:
what does the score of the aggregate distribution (per QA pooling with respect
to $s$) look like as a function of $\mathbf{w}$, the vector of expert weights?
We prove that this function is concave. This is useful because it allows for
online convex optimization over expert weights.

######  Theorem (informal).

Let $s$ be a bounded proper scoring rule.444For which QA pooling is well
defined (we discuss this below). For time steps $t=1\dots T$, $m$ experts
report forecasts to an aggregator, who combines them into a forecast
$\mathbf{p}^{t}$ using QA pooling with respect to $s$ and suffers a loss of
$-s(\mathbf{p}^{t};j^{t})$, where $j^{t}$ is the outcome at time step $t$. If
the aggregator updates the experts’ weights using online gradient descent,
then the aggregator’s regret compared to the best weights in hindsight is
$O(\sqrt{T})$.

The aforementioned concavity property is a nontrivial fact that demonstrates
an advantage of QA pooling with respect to the proper scoring rule used for
elicitation, as compared with using e.g. linear or logarithmic pooling
regardless of the method of elicitation: linear and logarithmic pooling
satisfy the concavity property for some proper scoring rules $s$ but not
others.

##### (Section 5.5) Overconfidence

Informally, an expert is _overconfident_ if the expert’s forecasts would be
more accurate if they were less extreme (closer to uniform). Much as it makes
sense to aggregate forecasts in a way that depends on the scoring rule, it
also makes sense to define overconfidence in a way that depends on the scoring
rule. We give two natural definitions of overconfidence with respect to a
proper scoring rule. The first definition says that a series of forecasts made
by an expert is overconfident if the expert’s total score is lower than the
score the expert expects. The second definition says that a series of
forecasts made by an expert is overconfident if using QA pooling to make the
forecasts less extreme would increase the expert’s total score. We prove that
these two definitions are equivalent.

##### (Section 5.6) Natural axiomatization for QA pooling methods

[277] and [301] independently came up with a simple axiomatization of quasi-
arithmetic means. We show how to change these axioms to allow for weighted
means; the resulting axiomatization is a natural characterization of all
quasi-arithmetic pooling methods in the case of $n=2$ outcomes. Furthermore,
although quasi-arithmetic means are typically defined for scalar-valued
functions, we demonstrate that these axioms can be extended to describe quasi-
arithmetic means with respect to vector-valued functions, as is necessary for
our purposes if $n>2$. This extension is nontrivial but natural, and to our
knowledge has not previously been described.555For $n>2$, these axioms
characterize the class of all QA pooling methods with respect proper scoring
rules that satisfy _convex exposure_ , a natural condition that we introduce
in Section 5.2.

####  5.1.4 Related work

Since this work’s contribution is a connection between two well-studied
problems (elicitation and aggregation of forecasts), there is naturally a
large volume of related work, some of which we have discussed in previous
chapters. In this section, we briefly discuss the most closely-related work to
ours.

##### Quasi-arithmetic means

Our notion of quasi-arithmetic pooling is an adaptation (and extension to
higher dimensions) of the existing notion of quasi-arithmetic means. These
were originally defined and axiomatized independently by [277] and [301].
[185] generalized this work to include weighted quasi-arithmetic means, though
these means have weights baked in rather than taking them as inputs, which is
different from our setting. See [261, §3.1] for an overview of this topic.

##### Arbitrage from collusion

In Chapter 4 we discussed the problem of colluding experts: suppose that a
principal uses a proper scoring rule $s$ to elicit forecasts from multiple
experts. If the experts have different opinions, they can collude to report
the forecast, thus earning them a larger total score than if they had been
honest, no matter the outcome. We did not detail how exactly this collusion
works, but the answer turns out to be precisely QA pooling: for the case of
$n=2$ outcomes, [228] showed that if all experts report what we are calling
the QA pool of their opinions with respect to $s$, then their total score is
guaranteed to increase. Our Theorem 5.3.1 recovers this result as a special
case.

##### Connections to Bregman divergence

In part, our work provides an alternative interpretation of prior work on
forecast aggregation via minimizing Bregman divergence, see e.g. [187, 318].
Concretely, [318, §4] defines a notion of aggregation analogous to ours,
though in a different context. The main focus of their line of work is on
connecting forecast aggregation to Bregman divergence; our approach connects
aggregation with proper scoring rules, and a connection to Bregman divergence
falls naturally out of this pursuit.

##### Dual averaging

One perspective on QA pooling is that, instead of directly averaging experts’
forecasts, QA pooling prescribes considering forecasts as elements in the dual
space of gradients (of the function $G$) and taking the average in this space
before converting the result back to the primal space of probabilities.
Gradient methods in online machine learning often take the _sum_ of gradients
of losses. Taking the average is of gradients is a less ubiquitous technique
known as _dual averaging,_ which was introduced by [302] and generalized
further by [356]. However, the contexts of QA pooling and dual averaging are
quite different.

##### Aggregation via prediction markets

In Chapter 1, we saw market scoring rules (MSRs) as a way of aggregating
forecasts. [220] introduced _cost-function markets_ , in which a market maker
sells $n$ types of shares – one for each outcome – where the price of a share
depends on the number of shares sold thus far according to some cost function.
They established a connection between cost-function markets and MSRs, where a
market with a given cost function will behave the same way as a certain MSR.
In particular, the cost function $C$ of a cost function market is the convex
dual of the expected score function $G$ of the proper scoring rule associated
with the corresponding MSR [181, §8.3].

QA pooling has a simple interpretation in terms of cost function markets: for
the cost function market corresponding to the scoring rule $s$, let
$\mathbf{q}_{i}$ be the quantity vector that implies each expert $i$’s
probability $\mathbf{p}_{i}$ (or in other terms, $i$ would buy a bundle
$\mathbf{q}_{i}$ of shares as the first participant in the market). Then the
QA pool with respect to $s$ is the probability implied by the weighted average
quantity vector $\sum_{i}w_{i}\mathbf{q}_{i}$.

Our work is also superficially similar to [222, 181], which tied cost-function
market making to online learning of probability distributions. Our results on
online learning are in a different context: the goal of their online learning
problem is to learn a _probability distribution over outcomes_ , whereas our
goal in Section 5.4 is to learn _expert weights._

###  5.2 Preliminaries

Throughout this work, we will let $m$ be the number of experts and use the
index $i$ to refer to any particular expert. We will let $n$ be the number of
outcomes and use the index $j$ to refer to any particular outcome. We will let
$\Delta_{n}$ be the standard in $\mathbb{R}^{n}$ and $\boldsymbol{\delta}_{j}$
be the basis-aligned unit vector with a $1$ in the $j$-th coordinate.

####  5.2.1 Proper scoring rules

We have already introduced proper scoring rules, along with their Savage
representations, in Section 2.1. However, it will serve us well to be more
precise in this chapter. First, we will clarify the range of possible scores:
we will allow $s(\mathbf{x};j)$, for $\mathbf{x}\in\Delta_{n}$ and $j\in[n]$,
to be any real number, _or_ negative infinity. For example,
$s_{\text{log}}((1,0);2)=-\infty$.

We define the _forecast domain_ $\mathcal{D}$ associated with $s$ to be the
set of forecasts $\mathbf{x}$ such that $s(\mathbf{x};j)$ is real-valued for
all $j$. For example, if $s=s_{\text{log}}$, then $\mathcal{D}$ is the
interior of $\Delta_{n}$. When discussing forecast aggregation, we will assume
that all forecasts belong to $\mathcal{D}$.666This choice removes from
consideration cases such as two experts reporting $(1,0)$ and $(0,1)$ under
the logarithmic scoring rule; aggregating these forecasts using our method is
tantamount to adding positive and negative infinity.

We will let $G$ denote the expected score function of $s$.777It will typically
be clear which scoring rule we are working with, so there is no need to write
$G_{s}$. We will assume that $s(\cdot;j)$ is continuous on $\Delta_{n}$ for
all $j$, as is $G(\cdot)$; to our knowledge, this is the case for all
frequently-used proper scoring rules.888For $s$, continuity is with respect to
the standard topology on $\mathbb{R}\cup\\{-\infty\\}$, i.e. the one that
includes sets of the form $[-\infty,r)$ as open sets. This means that e.g. the
log scoring rule is continuous on all of $\Delta_{n}$.

In Section 2.1 we introduced the Savage representation of a proper scoring
rule. We do so here again, this time more carefully.

######  Proposition 5.2.1 ([258, Theorem 2]).

A regular scoring rule $s$ is proper if and only if

$s(\mathbf{x};j)=G(\mathbf{x})+\left\langle\mathbf{g}(\mathbf{x}),\boldsymbol{\delta}_{j}-\mathbf{x}\right\rangle,$
(5.2)

for some convex function $G:\Delta_{n}\to\mathbb{R}$ and subgradient
function999That is, $\mathbf{g}$ satisfies $G(\mathbf{y})\geq
G(\mathbf{x})+\left\langle\mathbf{g}(\mathbf{x}),\mathbf{y}-\mathbf{x}\right\rangle$
for all $\mathbf{x},\mathbf{y}$. Note that $g_{i}(\mathbf{x})$ may be
$-\infty$ if $x_{i}=0$; see [348] for an examination of subgradients of
functions to the extended reals. $\mathbf{g}$ of $G$. The function $G$ is then
the expected score function of $s$.

Since we are assuming that $s$ and $G$ are continuous, it follows from
Equation 5.2 that $\mathbf{g}$ must be continuous as well.101010Continuity of
each component $g_{\ell}$ of $\mathbf{g}$ (for $\ell\in[n]$) is (as with $s$)
with respect to the standard topology on $\mathbb{R}\cup\\{-\infty\\}$. To see
that $g_{\ell}$ is continuous at a given $\mathbf{p}$, consider the limit of
Equation 5.2 as $\mathbf{x}\to\mathbf{p}$ with $j=\ell$ if $p_{j}=0$ and
$j\neq\ell$ if $p_{j}\neq 0$. A convex function with a continuous finite
subgradient is differentiable [201, Proposition 17.41], which means that $G$
is differentiable on the interior of $\Delta_{n}$, with gradient $\mathbf{g}$.

As discussed in Section 2.1, the key intuition of Equation 5.2 is that the
score of an expert who reports probability distribution $\mathbf{p}$ is
determined by drawing the tangent plane to $G$ at $\mathbf{p}$; the value of
this plane at $\boldsymbol{\delta}_{j}$, where $j$ is the outcome that
happens, is the expert’s score.

We refer to $\mathbf{g}$ as the _exposure function_ of $s$. We borrow this
term from finance, where _exposure_ refers to how much an agent stands to gain
or lose from various possible outcomes – informally speaking, how much the
agent cares about which outcome will happen. If we view
$G(\mathbf{p})-\left\langle\mathbf{g}(\mathbf{p}),\mathbf{p}\right\rangle$ as
the agent’s “baseline profit,” then the $j$-th component of
$\mathbf{g}(\mathbf{p})$ is the amount that the agent stands to gain (or lose)
on top of the baseline profit if outcome $j$ happens.

######  Remark 5.2.2.

Because the domain of $G$ is a subset of $\Delta_{n}$ (and thus lies in a
plane that is orthogonal to the all-ones vector $\mathbf{1}_{n}$), it makes
the most sense to think of its gradient function $\mathbf{g}$ as taking on
values in $\mathbb{R}^{n}$ modulo translation by the all-ones vector
$\mathbf{1}_{n}$; we will denote this space by
$\mathbb{R}^{n}/T(\mathbf{1}_{n})$. Sometimes we find it convenient to treat
$G$ as a function of $n$ variables rather than $n-1$ variables out of
convenience, thus artificially extending the domain of $G$ outside of the
plane containing $\Delta_{n}$. The component of the gradient of $G$ that is
parallel to $\mathbf{1}_{n}$ is not relevant.111111Formally, consider the
change of coordinates given by $z_{j}=x_{n}-x_{j}$ for $j\leq n-1$ and
$z_{n}=\sum_{j}x_{j}$, so that the domain of $G$ lies in the plane $z_{n}=1$.
Then for $j\leq n-1$, $\frac{\partial G}{\partial z_{j}}$ at a given point in
the domain of $G$ does not change if $1$ is substituted for $z_{n}$; only
$\frac{\partial G}{\partial z_{n}}$ changes (to zero). Equivalently in terms
of our original coordinates, the change that $\mathbf{g}$ undergoes when we
consider $G$ to be a function only defined on $\mathcal{D}$ instead of
$\mathbb{R}^{n}$ is precisely a projection of $\mathbf{g}$ onto
$\\{\mathbf{x}\in\mathbb{R}^{n}:\sum_{i}x_{i}=0\\}$.

Next, recall the Bregman divergence from Section 2.1.3: See 2.1.7

We note the following well-known facts about Bregman divergence:

######  Proposition 5.2.3 (Well-known facts about Bregman divergence).

Let $G$ be a differentiable, strictly convex function. Then:

  * •

$D_{G}(\mathbf{p}\parallel\mathbf{q})\geq 0$, with equality only when
$\mathbf{p}=\mathbf{q}$.

  * •

For every $\mathbf{q}$, $D_{G}(\mathbf{x}\parallel\mathbf{q})$ is a strictly
convex function of $\mathbf{x}$.

Finally, we make a note about interpreting the $n=2$ outcome case in one
dimension.

######  Remark 5.2.4.

Because $\Delta_{n}$ is $(n-1)$-dimensional, we can think of the case of $n=2$
outcomes in one dimension. All probabilities in are of the form $(p,1-p)$; we
map $\Delta_{2}$ to $[0,1]$ via the first coordinate. Thus, we let
$G(p):=G(p,1-p)$. We let
$g(p):=G^{\prime}(p)=\left\langle\mathbf{g}(p,1-p),(1,-1)\right\rangle$. The
tangent line to $G$ at $p$ will intersect the line $x=1$ at $s(p;1)$ (i.e. the
score if Outcome 1 happens) and intersect the line $x=0$ at $s(p;2)$ (i.e. the
score if Outcome 2 happens). See Figure 2.1 for an illustration.

The formulation in Remark 5.2.4 will be helpful when discussing the two-
outcome case, e.g. in Section 5.6.

####  5.2.2 Quasi-arithmetic pooling

We now introduce the central concept of this chapter: quasi-arithmetic
pooling.

######  Definition 5.2.5 (quasi-arithmetic pooling).

Let $s$ be a proper scoring rule with expected score function $G$ and exposure
function $\mathbf{g}$. Given forecasts
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}\in\mathcal{D}$ with non-negative weights
$w_{1},\dots,w_{m}$ adding to $1$, the _quasi-arithmetic (QA) pool_ of these
forecasts _with respect to $s$_ (or with respect to $\mathbf{g}$), denoted by
$\sideset{}{{}_{\mathbf{g}}}{\bigoplus}\limits_{i=1}^{m}(\mathbf{p}_{i},w_{i})$,
is the unique $\mathbf{p}^{*}\in\Delta_{n}$ such that
$\sum_{i=1}^{m}w_{i}\mathbf{g}(\mathbf{p}_{i})$ is a subgradient of $G$ at
$\mathbf{p}^{*}$.

If the forecasts and weights are clear from context, we may simply write
$\mathbf{p}^{*}$ to refer to their quasi-arithmetic pool; or, if only the
forecasts are clear, we may write $\mathbf{p}^{*}_{\mathbf{w}}$, where
$\mathbf{w}$ is the vector of weights.

######  Remark 5.2.6.

Equivalently [322, Theorem 23.5], we can define

$\sideset{}{{}_{\mathbf{g}}}{\bigoplus}\limits_{i=1}^{m}(\mathbf{p}_{i},w_{i}):=\arg\min_{\mathbf{x}}G(\mathbf{x})-\left\langle\mathbf{x},\sum_{i=1}^{m}w_{i}\mathbf{g}(\mathbf{p}_{i})\right\rangle.$
(5.3)

Also equivalently, we can define

$\sideset{}{{}_{\mathbf{g}}}{\bigoplus}\limits_{i=1}^{m}(\mathbf{p}_{i},w_{i}):=\arg\min_{\mathbf{x}}\sum_{i=1}^{m}w_{i}D_{G}(\mathbf{x}\parallel\mathbf{p}_{i}).$

The expression being minimized here differs from the one in Equation 5.3 by a
constant: namely,
$\sum_{i}w_{i}(\left\langle\mathbf{p}_{i},\mathbf{g}(\mathbf{p}_{i})\right\rangle-G(\mathbf{p}_{i}))$.

The QA-pool is well-defined, i.e. exists and is unique. It is unique because a
strictly convex function cannot have the same subgradient at two different
points [348, Lemma 3.11]. It exists because
$G(\mathbf{x})-\left\langle\mathbf{x},\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})\right\rangle$
is continuous and thus attains its minimum on the (compact) domain
$\Delta_{n}$.

In light of the fact that $D_{G}(\mathbf{p}\parallel\mathbf{q})$ is the
expected loss in score by an expert who, believing $\mathbf{p}$, instead
reports $\mathbf{q}$ (as discussed in Section 2.1.3), the Bregman divergence
formulation of QA pooling gives another natural interpretation.

######  Remark 5.2.7.

Consider a proper scoring rule $s$ with forecasts
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ with weights $w_{1},\dots,w_{m}$. The QA
pool of these forecasts is the forecast $\mathbf{p}^{*}$ that, if it is the
correct answer (i.e. if the outcome is drawn according to $\mathbf{p}^{*}$),
would minimize the expected loss of a randomly chosen (according to
$\mathbf{w}$) expert relative to reporting $\mathbf{p}^{*}$.

In this sense, QA pooling reflects a _compromise_ between experts: it is the
probability that, if it were correct, would make the experts’ forecast least
wrong overall.

######  Remark 5.2.8.

Since the Bregman divergence is convex in its first argument, computing the QA
pool is a matter of convex optimization. In particular, given oracle access to
$\mathbf{g}$, the ellipsoid method (see e.g. [262]) can be used to efficiently
find the QA pool of a list of forecasts.

Note that although Definition 5.2.5 only specifies that
$\mathbf{p}^{*}\in\Delta_{n}$, in fact it lies in $\mathcal{D}$:

######  Claim 5.2.9.

For any $\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ and $w_{1},\dots,w_{m}$, the QA
pool $\mathbf{p^{*}}$ lies in $\mathcal{D}$.

###### Proof.

Let $\mathbf{x}\in\Delta_{n}\setminus\mathcal{D}$. We show that
$\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})$ is not a subgradient of $G$ at
$\mathbf{x}$.

We have $s(\mathbf{x};j)=-\infty$ for some $j$ (satisfying $x_{j}=0$), so
$\left\langle\mathbf{g}(\mathbf{x}),\boldsymbol{\delta}_{j}-\mathbf{x}\right\rangle=-\infty$.
Since $\mathbf{g}$ is continuous, for sufficiently small $\epsilon$, we have

$\left\langle\mathbf{g}(\mathbf{x}+\epsilon^{\prime}(\boldsymbol{\delta}_{j}-\mathbf{x})),\boldsymbol{\delta}_{j}-\mathbf{x}\right\rangle<\left\langle\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i}),\boldsymbol{\delta}_{j}-\mathbf{x}\right\rangle$

for all $\epsilon^{\prime}\leq\epsilon$. This means that

$G(\mathbf{x}+\epsilon(\boldsymbol{\delta}_{j}-\mathbf{x}))-G(\mathbf{x})<\left\langle\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i}),\epsilon(\boldsymbol{\delta}_{j}-\mathbf{x})\right\rangle,$

so $\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})$ is not a subgradient of $G$ at
$\mathbf{x}$, as desired. ∎

While our max-min optimality result (Section 5.3) holds unconditionally, our
results in Section 5.4 and 5.6 require that our proper scoring rule $s$
satisfy a property that we term _convex exposure_.

######  Definition 5.2.10 (convex exposure).

A proper scoring rule $s$ with forecast domain $\mathcal{D}$ has _convex
exposure_ if the range of its exposure function $\mathbf{g}$ on $\mathcal{D}$
is a convex set.

The key fact about proper scoring rules with convex exposure is that for all
$\mathbf{p}_{1},\dots,\mathbf{p}_{m}$ and $w_{1},\dots,w_{m}$,
$\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})=\mathbf{g}(\mathbf{x})$ for some
$\mathbf{x}\in\mathcal{D}$. This means that
$\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})$ is a subgradient of $G$ at
$\mathbf{x}$, so $\mathbf{x}$ is the weighted QA pool of the $p_{i}$’s. In
other words, if $s$ has convex exposure, then we may write

$\mathbf{g}(\mathbf{p}^{*})=\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i}),$ (5.4)

where $\mathbf{p}^{*}$ is the weighted QA pool of the given forecasts. The
convex exposure property thus allows us to write down relations between
exposures of forecasts that would otherwise not necessarily be true.

The quadratic and logarithmic scoring rules, as well as all proper scoring
rules for binary outcomes, have convex exposure. In Appendix B.3 we explore in
more depth the question of which commonly used proper scoring rules have
convex exposure property.

###  5.3 QA pooling as a max-min optimal method

Our goal is to give a formal justification for quasi-arithmetic pooling.
Remark 5.2.7 established that the QA pool is optimizes (i.e. minimizes) the
weighted average Bregman divergence to the experts’ forecasts. This section
gives another justification for QA pooling in terms of max-min optimality. We
will give additional justifications in later sections.

######  Theorem 5.3.1.

Let $s$ be a proper scoring rule and let $\mathbf{g}$ be the exposure function
of $s$. Fix any forecasts $\mathbf{p}_{1},\dots,\mathbf{p}_{m}\in\mathcal{D}$
with non-negative weights $w_{1},\dots,w_{m}$ adding to $1$. Define

$u(\mathbf{p};j):=s(\mathbf{p};j)-\sum_{i=1}^{m}w_{i}s(\mathbf{p}_{i};j).$

Then the quantity $\min_{j}u(\mathbf{p};j)$ is uniquely maximized by setting
$\mathbf{p}$ to
$\mathbf{p}^{*}:=\sideset{}{{}_{\mathbf{g}}}{\bigoplus}\limits_{i=1}^{m}(\mathbf{p}_{i},w_{i})$.
Furthermore, this minimum (across outcomes $j$) is achieved simultaneously by
all $j$ with $p^{*}_{j}>0$. This quantity is non-negative, and is positive
unless all reports $\mathbf{p}_{i}$ with positive weights are equal.

One interpretation for this theorem statement is as follows. Consider an agent
who is tasked with submitting a forecast, and who will be paid according to
$s$. The agent decides to sub-contract $m$ experts to get their opinions,
paying expert $i$ the amount $w_{i}s(\mathbf{p}_{i};j)$ if the expert reports
$\mathbf{p}_{i}$ and outcome $j$ happens. (Perhaps experts whom the agent
trusts more have higher $w_{i}$’s.) Finally, the agent reports some (any)
forecast $\mathbf{p}$. Then $u(\mathbf{p};j)$ is precisely the agent’s profit
(utility).

The quantity $\min_{j}u(\mathbf{p};j)$ is the agent’s minimum possible profit
over all outcomes. It is natural to ask which report $\mathbf{p}$ maximizes
this quantity. Theorem 5.3.1 states that this maximum is achieved by the QA
pool of the experts’ forecasts with respect to $s$, and that this is the
unique maximizer.

A possible geometric intuition to keep in mind for the proof (below): for each
expert $i$, draw the plane tangent to $G$ at $\mathbf{p}_{i}$. For any $j$,
the value of this plane at $\boldsymbol{\delta}_{j}$ is $s(\mathbf{p}_{i};j)$.
Now take the weighted average of all $m$ planes; this is a new plane whose
intersection with any $\boldsymbol{\delta}_{j}$ is the total score received by
the experts if $j$ happens. Since $G$ is convex, this plane lies below $G$. To
figure out which point maximizes the agent’s guaranteed profit, push the plane
upward until it hits $G$. It will hit $G$ at $\mathbf{p}^{*}$ and the agent’s
worst-case profit will be the vertical distance that the plane was pushed.

###### Proof of Theorem 5.3.1.

By Equation 5.3, computing the QA pool amounts to finding the minimizer
$\mathbf{p}^{*}$ of the function
$G(\mathbf{x})-\left\langle\mathbf{x},\sum_{i=1}^{m}w_{i}\mathbf{g}(\mathbf{p}_{i})\right\rangle$
over $\Delta_{n}$. If $\mathbf{p}^{*}$ is in the interior of $\Delta_{n}$,
then this expression is differentiable at $\mathbf{p}^{*}$. If
$\mathbf{p}^{*}$ is on the boundary, then the expression can be extended to a
differentiable function in a neighborhood around $\mathbf{p}^{*}$.121212This
follows e.g. from [194, Theorem 1.8], where we take $C$ in the theorem
statement to be a compact subset of $\Delta_{n}$ containing $\mathbf{p}^{*}$
where $G$ is differentiable. Here we use that $\mathbf{p}^{*}\in\mathcal{D}$;
by continuity of $\mathbf{g}$, such a subset necessarily exists. Thus,
applying the KKT conditions (see e.g. [209, §5.5.3]) tells us that

$\mathbf{g}(\mathbf{p}^{*})=\sum_{i=1}^{m}w_{i}\mathbf{g}(\mathbf{p}_{i})+\lambda\mathbf{1}_{n}+\boldsymbol{\mu}$

for some $\lambda\in\mathbb{R}$ and $\boldsymbol{\mu}\in\mathbb{R}^{n}$ such
that $\mu_{j}\geq 0$ and $\mu_{j}=0$ if $p^{*}_{j}>0$. We therefore have

$\displaystyle u(\mathbf{p}^{*};j)$
$\displaystyle=s(\mathbf{p}^{*};j)-\sum_{i}w_{i}s(\mathbf{p}_{i};j)$
$\displaystyle=G(\mathbf{p}^{*})+\left\langle\mathbf{g}(\mathbf{p}^{*}),\boldsymbol{\delta}_{j}-\mathbf{p}^{*}\right\rangle-\sum_{i}w_{i}(G(\mathbf{p}_{i})+\left\langle\mathbf{g}(\mathbf{p}_{i}),\boldsymbol{\delta}_{j}-\mathbf{p}_{i}\right\rangle)$
$\displaystyle=G(\mathbf{p}^{*})-\sum_{i}w_{i}G(\mathbf{p}_{i})+\left\langle\sum_{i}w_{i}\mathbf{g}(\mathbf{p}_{i})+\lambda\mathbf{1}_{n}+\boldsymbol{\mu},\boldsymbol{\delta}_{j}-\mathbf{p}^{*}\right\rangle-\sum_{i}w_{i}\left\langle\mathbf{g}(\mathbf{p}_{i}),\boldsymbol{\delta}_{j}-\mathbf{p}_{i}\right\rangle$
$\displaystyle=G(\mathbf{p}^{*})-\sum_{i}w_{i}G(\mathbf{p}_{i})+\sum_{i}w_{i}\left\langle\mathbf{g}(\mathbf{p}_{i}),\mathbf{p}_{i}-\mathbf{p}^{*}\right\rangle+\left\langle\lambda\mathbf{1}_{n}+\boldsymbol{\mu},\boldsymbol{\delta}_{j}-\mathbf{p}^{*}\right\rangle$