# Incentivizing honest performative predictions with proper scoring rules

Caspar Oesterheld Equal contribution Carnegie Mellon University  Johannes
Treutlein111 University of California, Berkeley  Emery Cooper  Center on Long-
Term Risk  Rubi Hudson  University of Toronto

###### Abstract

Proper scoring rules incentivize experts to accurately report beliefs,
assuming predictions cannot influence outcomes. We relax this assumption and
investigate incentives when predictions are _performative_ , i.e., when they
can influence the outcome of the prediction, such as when making public
predictions about the stock market. We say a prediction is a _fixed point_ if
it accurately reflects the expert’s beliefs after that prediction has been
made. We show that in this setting, reports maximizing expected score
generally do not reflect an expert’s beliefs, and we give bounds on the
inaccuracy of such reports. We show that, for binary predictions, if the
influence of the expert’s prediction on outcomes is bounded, it is possible to
define scoring rules under which optimal reports are arbitrarily close to
fixed points. However, this is impossible for predictions over more than two
outcomes. We also perform numerical simulations in a toy setting, showing that
our bounds are tight in some situations and that prediction error is often
substantial (greater than 5-10%). Lastly, we discuss alternative notions of
optimality, including performative stability, and show that they incentivize
reporting fixed points.

##  1 Introduction

As AI capabilities increase, this raises concern for safety, including how to
scalably control AI systems with superhuman capabilities [Russell, 2019, Ngo
et al., 2022]. One proposed design for safety is _oracle AI_ [Armstrong et
al., 2012; Armstrong, 2013; Bostrom, 2014, Ch. 10]. An oracle AI makes
predictions or forecasts about the world, but does not autonomously pursue
goals. It could thus be safer while still being useful for many applications.

A proper scoring rule assigns scores to forecasts in a way that incentivizes
honest reporting of beliefs [Brier, 1950; Good, 1952, Section 8; McCarthy,
1956; Savage, 1971; Gneiting and Raftery, 2007]. Proper scoring rules have
been used to incentivize honest reports from experts [Carvalho, 2016]. They
could thus be used as an objective for oracle AIs. However, prior work assumes
that predictions themselves do not influence the events they are trying to
predict. In reality, predictions may be _performative_ [Perdomo et al., 2020,
Armstrong and O’Rorke, 2017], meaning that they can influence the distribution
of outcomes. For example, an AI predicting stock market prices might be able
to influence whether people buy or sell stocks, and thus influence whether its
predictions come true or not. This makes it important to investigate
incentives and honesty of predictions when predictions are performative.

In this paper, we analyze the case of an AI model or human, henceforth called
expert, making a probabilistic forecast over a finite set of possibilities to
maximize a proper scoring rule. We say that a prediction is performatively
optimal if it maximizes expected score, and we define a prediction as a fixed
point or self-fulfilling if it is equal to the expert’s beliefs, conditional
on the expert having made that prediction. We investigate to what extent
honest predictions, i.e., fixed points, are incentivized in this setting.111We
assume that the AI model can be ascribed explicit beliefs, so that its reports
can be characterized as honest if they reflect the model’s beliefs. All else
equal, honest predictions are preferable since, assuming a sufficiently
capable expert, they provide us with more accurate information. However, if an
expert has incentives other than to predict honestly—e.g., to bring about
fixed points with lower entropy—this is undesirable even if the expert
otherwise makes approximately accurate predictions.

The setting in which a model’s predictions can influence the predicted
distribution has been discussed as _performative prediction_ [Perdomo et al.,
2020] in the machine learning literature. However, performative prediction
focuses on classification or regression tasks with arbitrary model classes and
loss functions rather than probabilistic predictions incentivized by proper
scoring rules. The literature is motivated by minimization of a given loss
function, whereas we take a mechanism design perspective, asking which scoring
rules incentivize honest predictions. Focusing on a special case and taking a
different perspective will lead to original results that are unique to our
setting.

Contributions.  In Section 3, we adapt the performative prediction formalism
to probabilistic predictions or forecasts. We allow for an arbitrary function
$f$ describing the relationship between the expert’s predictions and
distributions over predicted outcomes caused by these predictions.

In Section 4, we show that for any strictly proper scoring rule, there exist
functions $f$ from predictions to beliefs such that performatively optimal
reports are not fixed points, even if one exists and is unique. Moreover, we
show that under reasonable distributions over such functions, optimal reports
are almost never fixed points. This strengthens analogous results from the
performative prediction literature.

In Section 5, we then provide upper bounds for the inaccuracy of reported
beliefs, and for the distance of predictions from fixed points.

In Section 6, we use the bounds to develop scoring rules that make the bounds
arbitrarily small for binary predictions. We also show that when reporting a
prediction over more than two outcomes, the bounds cannot be made arbitrarily
small.

In Section 7, we perform numerical simulations using the quadratic scoring
rule, to show how the inaccuracy of predictions and the distance of
predictions from fixed points depend on the expert’s influence on the world
via its prediction. The results show that our bounds are tight in some cases.
They also show that substantially inaccurate reports (i.e., with errors
greater than $5-10$%) are common in our toy setting.

In Section 8, we discuss alternatives to performative optimality that do not
set incentives other than honest predictions. We show that _performatively
stable_ [Perdomo et al., 2020] predictions are fixed points. We then consider
repeated risk minimization, repeated gradient descent, no-regret learning and
prediction markets, and show that all of these settings lead to predictions
that are fixed points or close to fixed points.

Finally, in Section 9, we elaborate on related work, and in Section 10, we
conclude and outline avenues for future work.

Proofs are in corresponding sections in Appendix A.

##  2 Background

Proper scoring rules.  Proper scoring rules are used to incentivize an expert
to report probabilistic beliefs honestly. Consider a prediction given by a
probability distribution ${\bm{p}}\in\Delta(\mathcal{N})$ over a set
$\mathcal{N}:=\\{1,\dotsc,n\\}$ of $n\in\mathbb{N}$ disjoint and exhaustive
outcomes. We identify each distribution ${\bm{p}}\in\Delta(\mathcal{N})$ with
a vector ${\bm{p}}\in[0,1]^{n}$ and write $p_{i}$ for the probability of event
$i\in\mathcal{N}$ under distribution ${\bm{p}}$. A _scoring rule_ is a
function
$S\colon\Delta(\mathcal{N})\times\mathcal{N}\rightarrow\overline{\mathbb{R}}$,
where $\overline{\mathbb{R}}:=[-\infty,\infty]$ is the extended real line.
Given prediction ${\bm{p}}\in\Delta(\mathcal{N})$ and outcome
$i\in\mathcal{N}$, the expert receives the score $S({\bm{p}},i).$ We write
$S({\bm{p}},\bm{q}):=\mathbb{E}_{i\sim\bm{q}}[S({\bm{p}},i)]$ for the expert’s
expected score, given that outcome $i$ follows distribution
$\bm{q}\in\Delta(\mathcal{N}).$

######  Definition 1.

A scoring rule $S$ is called _proper_ if $S(\bm{q},\bm{q})\geq
S({\bm{p}},\bm{q})$ for all ${\bm{p}},\bm{q}\in\Delta(\mathcal{N}).$ It is
called _strictly proper_ if this inequality is strict whenever
${\bm{p}}\neq\bm{q}.$

######  Example 1 (Logarithmic scoring rule).

The logarithmic scoring rule is defined as $S({\bm{p}},i):=\log p_{i}$ and
$S({\bm{p}},\bm{q})=\sum_{i=1}^{n}q_{i}\log p_{i}$. This is also the negative
of the cross-entropy loss employed in training, for example, current large
language models [Brown et al., 2020]. It is strictly proper.

######  Example 2 (Quadratic scoring rule).

Another strictly proper scoring rule is the quadratic score, defined as
$S({\bm{p}},i):=2p_{i}-\|{\bm{p}}\|_{2}^{2}$ with
$S({\bm{p}},\bm{q})=2{\bm{p}}^{\top}\bm{q}-\|{\bm{p}}\|_{2}^{2}$. This is an
affine transformation of the Brier score, making them equivalent scoring
rules.

Gneiting and Raftery [2007, Theorem 1] provide a characterization of proper
scoring rules, which will be helpful for stating and proving many of our
results.

First, given a convex function
$G\colon\Delta(\mathcal{N})\rightarrow\overline{\mathbb{R}}$, a subgradient is
a function $g\colon\Delta(\mathcal{N})\rightarrow\overline{\mathbb{R}}^{n}$
such that for any ${\bm{p}},\bm{q}\in\Delta(\mathcal{N}),$ we have
$G(\bm{q})\geq G({\bm{p}})+g({\bm{p}})^{\top}(\bm{q}-{\bm{p}})$. In general,
this function may not be unique. Throughout this paper we assume that whenever
the subgradients are finite, they are normalized to lie in the _tangent space_
of $\Delta(\mathcal{N})$, i.e.,
$g({\bm{p}})\in\mathcal{T}\vcentcolon=\\{\bm{x}\in\mathbb{R}^{n}\mid\sum_{i}x_{i}=0\\}$.
This can be assumed since if $g({\bm{p}})$ is a subgradient of $G$ at point
${\bm{p}}$, so is $(g_{i}({\bm{p}})-\frac{1}{n}\sum_{j}g_{j}({\bm{p}}))_{i}$.

######  Theorem 1 (Gneiting and Raftery, 2007).

A scoring rule $S$ is (strictly) proper, if and only if there exists a
(strictly) convex function
$G\colon\Delta(\mathcal{N})\rightarrow\overline{\mathbb{R}}$ with a
_subgradient_ $g\colon\Delta(\mathcal{N})\rightarrow\overline{\mathbb{R}}^{n}$
such that $S({\bm{p}},\bm{q})=G({\bm{p}})+g({\bm{p}})^{\top}(\bm{q}-{\bm{p}})$
for all ${\bm{p}},\bm{q}\in\Delta(\mathcal{N})$.

Differentiable scoring functions.  If $G$ is differentiable at some point
${\bm{p}}$, then the subgradient $g({\bm{p}})$ is just the gradient of $G$,
$g({\bm{p}})=\nabla G({\bm{p}})$. As before we let $\nabla G({\bm{p}})$ be an
element of the tangent space $\mathcal{T}$. For any $\bm{v}\in\mathcal{T}$,
$g({\bm{p}})^{\top}\bm{v}$ then gives the directional derivative of $G$ at
point ${\bm{p}}$ in the direction $\bm{v}$. Note that since $G$ is only
defined on the simplex $\Delta(\mathcal{N})$, the partial derivatives are not
well-defined.222For example, in the case of three outcomes, the partial
derivative at $(0.3,0.4,0.4)$ w.r.t. the first entry is the limit
$\lim_{\epsilon\rightarrow
0}(G(0.3+\epsilon,0.4,0.4)-G(0.3,0.4,0.4))/\epsilon$. But
$G(0.3+\epsilon,0.4,0.4)$ is not (necessarily) defined for positive (or
negative) $\epsilon$.

Given $G,g$ as in the Gneiting and Raftery characterization, we write
$Dg({\bm{p}})\in\mathbb{R}^{n,n}$ for the Jacobian matrix of $g$, if it exists
(i.e., this is the Hessian of $G$). Note that because $g$ is only defined on
$\Delta(\mathcal{N})$, the matrix representation of $Dg({\bm{p}})$ in
$\mathbb{R}^{n,n}$ is not unique. Generally it does not matter which
representation of $Dg({\bm{p}})$ we use. Importantly, for all
$\bm{v}\in\mathcal{T}$, $Dg({\bm{p}})\bm{v}$ will always be unique and
(because we assume that $g({\bm{p}})$ is in the tangent space) in
$\mathcal{T}$.

Figure 1: Maximal inaccuracy and maximal distance to fixed point (FP) of
optimal predictions, depending on the slope of $f$, according to our
simulation and our theoretical bound.

##  3 Problem setting

In this paper, we take the stance of a principal trying to elicit honest
predictions from an expert (human or AI system). We assume that the expert
reports a prediction ${\bm{p}}$ to maximize the expected score given by a
proper scoring rule, $S({\bm{p}},\bm{q})$.

Importantly, we assume that the expert’s beliefs over outcomes, $\bm{q}$, can
themselves vary given different predictions ${\bm{p}}$, because the expert may
believe that its predictions affect the probability of outcomes. To model
this, we assume that there is a function
${f\colon\Delta(\mathcal{N})\rightarrow\Delta(\mathcal{N})}$ such that beliefs
are given by $\bm{q}=f({\bm{p}})$.333Note that any other factor influencing
the expert’s belief $\bm{q}$ can be incorporated into $f$ by marginalizing.
For example, assume $\bm{q}$ is a function $\bm{q}=g({\bm{p}};X)$ where
${\bm{p}}$ is the expert’s prediction and $X$ is some environmental factor the
expert is uncertain about. Then we can let
$f({\bm{p}}):=\mathbb{E}_{X}\left[g({\bm{p}},X)\right]$.  We assume $f$ is
known to the expert, but not to the principal.

In the case of an AI system, $f({\bm{p}})$ could also be seen as a ground
distribution from which we sample to _train_ a model (see Section D.3). In
that case, the objective is to design a training procedure that sets the right
incentives. However, in most of the following, we assume $f({\bm{p}})$ are the
subjective beliefs of a highly capable and knowledgeable expert.

We say that a prediction ${\bm{p}}$ is _performatively optimal_ [Perdomo et
al., 2020] if
${\bm{p}}\in\operatorname*{arg\,max}_{\Delta(\mathcal{N})}S({\bm{p}},f({\bm{p}}))$.
In the following, we will not assume convexity of this objective. Our bounds
will depend on differentiability of $S$ and $f$.

A point ${\bm{p}}$ is a _fixed point_ of $f$ if $f({\bm{p}})={\bm{p}}$. By
Brouwer’s fixed point theorem, if $f$ is continuous, a fixed point
${\bm{p}}\in\Delta(\mathcal{N})$ always exists. Moreover, if $f$ is Lipschitz
continuous with constant $L_{f}<1$, then by Banach’s fixed point theorem, the
fixed point is unique.

######  Example 3 (Bank Run).

A newspaper’s AI predicts whether a certain bank will suffer a bank run or
not. Readers use this information when deciding whether to withdraw their
money. Specifically, imagine that the probability of a bank run as a function
of the AI expert’s prediction $\mathbf{p}=(p_{1},p_{2})\in\Delta(\\{1,2\\})$
is given by the (monotonic) function
$f\colon\Delta(\\{1,2\\})\rightarrow\Delta(\\{1,2\\})$ whose entries are
defined by
$f_{1}(\mathbf{p})=p_{1}-3(p_{1}-\nicefrac{{1}}{{10}})(p_{1}-\nicefrac{{3}}{{5}})(p_{1}-\nicefrac{{9}}{{10}})/2$
and $f_{2}(\mathbf{p})=1-f_{1}(\mathbf{p})$ for all $\mathbf{p}$. Then $f$ has
fixed points at $\mathbf{p}=(\nicefrac{{1}}{{10}},\nicefrac{{9}}{{10}})$,
$\mathbf{p}=(\nicefrac{{3}}{{5}},\nicefrac{{2}}{{5}})$, and
$\mathbf{p}=(\nicefrac{{9}}{{10}},\nicefrac{{1}}{{10}})$.

We focus on fixed points (or approximate fixed points) as a standard of
honesty. To see why one may prefer reports that are fixed points, consider a
case in which there are no strong guarantees (upper bounds) on
$\|{\bm{p}}-f({\bm{p}})\|$. Then the actual probability of an event,
$f_{i}({\bm{p}})$, could be much higher or lower than the reported probability
$p_{i}$. This would prevent one from drawing any useful conclusions from the
report. However, if ${\bm{p}}=f({\bm{p}})$ or $\|{\bm{p}}-f({\bm{p}})\|$ is
small, then one can rely on the prediction ${\bm{p}}$ to guide decisions.

That being said, fixed points are not all one might care about, especially
when it comes to potential superhuman oracle AIs. Ideally, we would want such
systems to not think about how to influence the world at all [Armstrong and
O’Rorke, 2017]. Alternatively, they should choose good fixed points over bad
ones, hoping that such fixed points exist (we discuss preferences between
different fixed points in Appendix B). Regardless, it is still important to
understand whether and when fixed points are incentivized. For instance, if a
model reports fixed points, one could try to use it only in situations in
which a unique desirable fixed point exists.

Relation to performative prediction.  As noted in the introduction, our
setting is a special case of performative prediction [Perdomo et al., 2020].
In performative prediction, the goal is to find a model parameter that
minimizes empirical risk for a classification or regression task, assuming
that the choice of parameter can influence the data distribution. The loss-
minimizing parameter when taking into account this influence is called
performatively optimal. The analogue to fixed points in performative
prediction are _performatively stable_ predictions.

We indicate below when our results are analogous to results in the
performative prediction setting. However, most of our results are unique to
our setting. We take the perspective of a mechanism designer instead of taking
a loss function as given. Moreover, we focus on fixed points instead of
performative optima. In particular, we bound the quantity
$\|{\bm{p}}-f({\bm{p}})\|$ corresponding to the inaccuracy of predictions,
which does not have a direct analogue in performative prediction. We give a
more detailed comparison in Section 9.

Additional notation.  We use $\mathbf{1}$ to denote the vector
$(1,\dotsc,1)^{\top}\in\mathbb{R}^{n}$ and $I$ to denote the identity matrix.
We define
$\mathrm{int}(\Delta(\mathcal{N})):=\\{{\bm{p}}\in\Delta(\mathcal{N})\mid\forall
i\colon 0<p_{i}<1\\}$ and use $\|\bm{x}\|:=\sqrt{\vec{x}^{\top}\bm{x}}$ to
denote the Euclidean norm on $\mathbb{R}^{n}$.

##  4 Incentives to predict non-fixed-points

We begin by investigating whether an expert makes honest predictions, even in
the presence of performativity. In performative prediction, it has been shown
that performative optimality comes apart from performative stability (the
analogous concept to a fixed point in our setting) [Perdomo et al., 2020, Izzo
et al., 2021]. However, one may ask whether this is always the case or
whether, e.g., some scoring function would prevent this.

We show that this is not the case: fixed points are in general not optimal.
First, we show that for any strictly proper scoring rule there exist cases
where a fixed point exists but the optimal prediction is not a fixed point.
Afterwards, we show that when assuming differentiability and some reasonable
distribution over $f$, optimal predictions are almost surely not fixed points.

######  Proposition 1.

Let $S$ be any strictly proper scoring rule. For any interior fixed point
${\bm{p}}^{*}\in\mathrm{int}(\Delta(\mathcal{N}))$ there exists a function $f$
with Lipschitz constant $L_{f}<1$ and a unique fixed point at ${\bm{p}}^{*}$,
such that there exists ${\bm{p}}^{\prime}\neq{\bm{p}}^{*}$ with
$S({\bm{p}}^{\prime},f({\bm{p}}^{\prime}))>S({\bm{p}}^{*},f({\bm{p}}^{*}))$.
That is, the unique fixed point of $f$ is not performatively optimal.

Note that since the function $f$ has Lipschitz constant strictly smaller than
$1$, it represents a world that “dampens” the influence of the prediction,
leading to a unique fixed point by Banach’s fixed point theorem. It is
interesting that the expert still prefers to make a prediction that is not a
fixed point.

The above result raises the question whether a situation where fixed points
are suboptimal is a niche counterexample or whether it is common. We show that
under some relatively mild assumptions, the optimal prediction is almost
surely not a fixed point. The intuition behind this result is that if a
prediction ${\bm{p}}$ is an interior point and optimal, then
$\nabla_{{\bm{p}}}(S({\bm{p}},f({\bm{p}})))=0$. Using the Gneiting and Raftery
characterization, we can show that this is a knife-edge case in which
$g({\bm{p}})^{\top}Df({\bm{p}})=0$. Given sufficiently continuous
distributions, this happens with probability $0$. The conditions on the
stochastic field
$\\{F({\bm{p}})\\}_{{\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))}$ ensure this
continuity, i.e., that the distributions over $f$ as well as $Df({\bm{p}})$ do
not assign positive probability to any single point or subspace, hence almost
never sampling the knife edge case. The condition would hold, e.g., for a
Gaussian process with smooth kernel and mean functions (see Example 5 in
Section A.3).

######  Theorem 2.

Let $S$ be a twice differentiable strictly proper scoring rule. Let
$\mathcal{F}:=\\{F({\bm{p}})\\}_{{\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))}$
be a stochastic field with values in $\Delta(\mathcal{N})$ and let
$Y({\bm{p}},\bm{v}):=(\Pi_{n-1}F({\bm{p}}),\Pi_{n-1}\partial_{\bm{v}}F({\bm{p}}))$
for ${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$ and
$\bm{v}\in\mathcal{T}\cap S^{n-1}$. Assume that

  * •

the sample paths ${\bm{p}}\rightsquigarrow F({\bm{p}})$ are twice continuously
differentiable

  * •

for each ${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$ and
$\bm{v}\in\mathcal{T}\cap S^{n-1}$, the random vector $Y({\bm{p}},\bm{v})$ has
a joint density $h_{Y({\bm{p}},\bm{v})}$ and there exists a constant $C$ such
that $h_{Y({\bm{p}},\bm{v})}\leq C$ for all
${\bm{p}}\in\Delta(\mathcal{N}),\bm{v}\in S^{n-1}\cap\mathcal{T}$.

Then, almost surely, there is no point
${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$ such that
${\bm{p}}\in\operatorname*{arg\,max}_{{\bm{p}}^{\prime}}S({\bm{p}}^{\prime},F({\bm{p}}^{\prime}))$
and $F({\bm{p}})={\bm{p}}$.

Figure 2: Heatmap of L2 distance of optimal prediction ${\bm{p}}$ to true
probability distribution $f({\bm{p}})$ (left) and to the fixed point
${\bm{p}}^{*}$ (right), depending on fixed point position $p_{1}^{*}$ and
$\alpha$ (slope of $f$), for the quadratic scoring rule.

##  5 Bounds on the deviation from fixed points

In the previous section, we have shown that performatively optimal predictions
are generally not fixed points, i.e., they inaccurately represent the expert’s
beliefs. But how inaccurate should we expect predictions to be, and what
properties of $S$ and $f$ determine this inaccuracy? Assuming
differentiability of $f$ and $S$, this section provides upper bounds for the
inaccuracy of optimal predictions ${\bm{p}}$ (i.e.,
$\|{\bm{p}}-f({\bm{p}})\|$) and their distance from fixed points
${\bm{p}}^{*}$ (i.e., $\|{\bm{p}}-{\bm{p}}^{*}\|$). Note that, while the
latter has a direct analogue in the performative prediction literature
[Perdomo et al., 2020, Theorem 4.3], evaluating the inaccuracy of predictions
only makes sense in our context where parameters are probability
distributions.

For our bounds we will use the following notation. We use
$\|A\|_{\mathrm{op}}=\max_{\bm{v}\in\mathcal{T}}\frac{\|A\bm{v}\|}{\|\bm{v}\|}$
for the operator norm of $A$ on the tangent space. It is equal to $A$’s
largest singular value when seen as an automorphism on the tangent space. We
use $A|_{\mathcal{T}}\succeq\gamma$ to denote that $\bm{v}^{\top}(A-\gamma
I)\bm{v}\geq 0$ for all $\bm{v}\in\mathcal{T}$. If $A$ is symmetric, this is
equivalent to saying that the smallest eigenvalue of $A$ on the tangent space
is at least $\gamma$. Further, note that if $g$ is a subderivative of $G$ and
$\|g({\bm{p}})\|<L_{G}$ for all ${\bm{p}}\in\Delta(\mathcal{N})$, then $L_{G}$
is a Lipschitz constant of $G$. Similarly, if
$\|Df({\bm{p}})\|_{\mathrm{op}}\leq L_{f}$ for all
${\bm{p}}\in\Delta(\mathcal{N})$, then $L_{f}$ is a Lipschitz constant of $f$.

######  Theorem 3.

Let $S$ be a strictly proper scoring rule, and let $G,g$ as in the Gneiting
and Raftery characterization (Theorem 1). Let ${\bm{p}}\in\Delta(\mathcal{N})$
and assume $f,G,g$ are differentiable at ${\bm{p}}$. Assume
$Dg({\bm{p}})|_{\mathcal{T}}\succeq\gamma_{{\bm{p}}}$ for some
$\gamma_{\bm{p}}>0$. Then whenever ${\bm{p}}$ is a performatively optimal
report,

$\|{\bm{p}}-f({\bm{p}})\|\leq\frac{\|Df({\bm{p}})\|_{\mathrm{op}}\|g({\bm{p}})\|}{\gamma_{{\bm{p}}}}.$

In particular, if $f$ has Lipschitz constant $L_{f}$, $G$ has Lipschitz
constant $L_{G}$, and $G$ is $\gamma$-strongly convex, then we have
$\|{\bm{p}}-f({\bm{p}})\|\leq\frac{L_{f}L_{G}}{\gamma}$.

In the case where $f$ has Lipschitz constant $L_{f}<1$, we can use the above
results to derive a bound on how far the optimal report is from the (by
Banach’s fixed point theorem unique) fixed point.

######  Theorem 4.

Same assumptions as Theorem 3. Assume further that $f$ has Lipschitz constant
$L_{f}<1$. Let ${\bm{p}}^{*}$ be the unique fixed point of $f$. Then for the
performatively optimal report ${\bm{p}}$,

$\|{\bm{p}}-{\bm{p}}^{*}\|\leq\frac{\|g({\bm{p}})\|\|Df({\bm{p}})\|_{\mathrm{op}}}{(1-L_{f})\gamma_{\bm{p}}}\leq\frac{L_{f}L_{G}}{(1-L_{f})\gamma_{\bm{p}}}.$

Note that the assumption that $L_{f}<1$ ensures that $f$’s fixed point is
unique by Banach’s fixed point theorem. Without $L_{f}<1$, no trivial bound
holds, as we show in Proposition 3 in Section A.6.

This bound is analogous to a bound in [Perdomo et al., 2020, Theorem 4.3]. Our
bound differs in that we use Euclidean distance instead of Wasserstein
distance to measure the sensitivity of $f$ to the choice of report. Moreover,
assuming a $L_{\ell}$-Lipschitz and $\gamma$-strictly convex loss function
$\ell$, their bound depends on the ratio $\frac{L_{\ell}}{\gamma}$. We instead
bound this distance against the ratio
$\frac{\|g({\bm{p}})\|}{\gamma_{\bm{p}}}$, which will allow us to minimize the
bound in the two-outcome case by using exponential functions (Theorem 5). This
would not be possible when assuming $\gamma$-strict convexity, since there
exist no functions that globally make the ratio $\frac{L_{\ell}}{\gamma}$
arbitrarily small. Perdomo et al. [2020] show that their bound can be made
small by regularizing the loss function, but this would be undesirable in our
setting, since regularized scoring rules would be improper and thus cease to
incentivize honest reports even for constant $f$.

######  Example 4 (Bound for the quadratic scoring rule).

Consider the quadratic scoring rule $S({\bm{p}},i)=2p_{i}-\|{\bm{p}}\|_{2}$.
Note that we can represent this in Gneiting and Raftery’s characterization
with $G({\bm{p}})=\|{\bm{p}}\|^{2}$ and
$g({\bm{p}})=2{\bm{p}}-\frac{2}{n}\mathbf{1}$. Thus, $Dg({\bm{p}})=2I$, where
$I$ is the identity matrix. Hence $Dg({\bm{p}})\succ 2$. Further,
$\|g({\bm{p}})\|_{2}=2\|{\bm{p}}-\frac{1}{n}\mathbf{1}\|$. Thus, for $f$ with
Lipschitz constant $L_{f}$, Theorem 3 implies that for the optimal report
${\bm{p}}$ we have that $\|f({\bm{p}})-{\bm{p}}\|\leq
L_{f}\|{\bm{p}}-\frac{1}{n}\mathbf{1}\|\leq L_{f}\sqrt{(n-1)/n}$. If
$L_{f}<1$, then by Theorem 4 we further have
$\|{\bm{p}}-{\bm{p}}^{*}\|\leq\frac{L_{f}}{1-L_{f}}\|{\bm{p}}-\frac{1}{n}\mathbf{1}\|\leq\frac{L_{f}}{1-L_{f}}\sqrt{(n-1)/n}$.

##  6 Approximate fixed-point prediction with the right proper scoring rules?

The above results show that depending on the scoring rule we can obtain bounds
on the accuracy of performatively optimal predictions. Can we make these
bounds arbitrarily small by choosing an appropriate scoring rule, e.g., one
that makes $\|g({\bm{p}})\|/\gamma_{{\bm{p}}}$ very small at each point? In
this section, we show that the answer is yes in the two-outcome case and no in
the general case.

######  Theorem 5.

Consider the case of two outcomes, i.e., let $\mathcal{N}=\\{1,2\\}$. Let
$L_{f}\in\mathbb{R}$ and $\epsilon>0$. Then there exists a scoring rule $S$
s.t. under any $f$ with Lipschitz constant $L_{f}$, any optimal report
${\bm{p}}$ satisfies $\|{\bm{p}}-f({\bm{p}})\|\leq\epsilon$. If $L_{f}<1$,
then there also exists a scoring rule that additionally ensures that under any
$f$ with Lipschitz constant $L_{f}$, any optimal report satisfies
$\|{\bm{p}}-{\bm{p}}^{*}\|\leq\epsilon$, where ${\bm{p}}^{*}$ is the (unique)
fixed point of $f$.

Note that if there are multiple fixed points, then $S$ still induces
preferences between—approximately—predicting these fixed points. In
particular, because $S({\bm{p}},{\bm{p}})$ is convex, the performatively
optimal fixed point will either be the one that maximizes or the one that
minimizes $p_{1}$ among the fixed points. This may be undesirable as the
expert still has a strong incentive other than (though compatible with) honest
prediction. We discuss this in more detail in Appendix B.

Can arbitrarily good bounds be achieved with practical proper scoring rules?
Our proof of Theorem 5 uses exponential scoring rules with
$g({\bm{p}})=(e^{L_{f}p_{1}/(\sqrt{2}\epsilon)},-e^{L_{f}p_{1}/(\sqrt{2}\epsilon})^{\top}$.
For high $K$, this scoring rule seems impractical, because the stakes vary
greatly over the interval. For example,
$S((\nicefrac{{2}}{{3}}+\epsilon,\nicefrac{{1}}{{3}}-\epsilon),(\nicefrac{{2}}{{3}},\nicefrac{{1}}{{3}}))/S((\nicefrac{{1}}{{2}}+\epsilon,\nicefrac{{1}}{{2}}-\epsilon),(\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}))=e^{L_{f}/(6\sqrt{2}\epsilon)}$.
Hence, as we increase $L_{f}/\epsilon$, it becomes exponentially more
important for the expert to predict accurately near $\nicefrac{{2}}{{3}}$ than
to predict accurately near $\nicefrac{{1}}{{2}}$. In particular, an AI model
trained with this scoring rule may be much worse at predicting probabilities
near $\nicefrac{{1}}{{2}}$ than near $\nicefrac{{2}}{{3}}$. Similarly, it is
unrealistic to reward a human expert with, say, millions of dollars near
$\nicefrac{{2}}{{3}}$ and with just a few cents near $\nicefrac{{1}}{{2}}$.
Unfortunately, it turns out that all possible scoring rules that achieve bound
$\epsilon$ under Lipschitz constant $L_{f}$ have this undesirable property,
though the exact bound turns out somewhat complicated.

######  Theorem 6.

Suppose $S$ is a proper scoring rule s.t. for some $\epsilon,L_{f}>0$ we have
that whenever $f$ is $L_{f}$-Lipschitz, the optimal report ${\bm{p}}$
satisfies $\|f({\bm{p}})-{\bm{p}}\|<\epsilon$. Let $3\epsilon\leq p_{l}\leq
p_{h}\leq 1-4\epsilon$ and $\delta=\epsilon/(L_{f}+1)$. Then the ratio of the
supremum and infimum over $p_{1}\in[p_{l},p_{h}]$ of
$S((p_{1}+4\delta,1-p_{1}-4\delta),(p_{1},1-p_{1}))-S((p_{1},1-p_{1}),(p_{1},1-p_{1}))$
is at least

$\frac{L_{f}}{2L_{f}+6}\left(3\frac{L_{f}+1}{L_{f}+3}\right)^{(L_{f}+1)(p_{h}-p_{l})/(8\epsilon)-5/2}.$

In particular, for fixed positive $L_{f}$, this term is exponential in
$1/\epsilon$ and for fixed positive $\epsilon$ it is exponential in $L_{f}$.

Intuitively, the assumption on $S$ is that it ensures small accuracy bounds of
$\epsilon$ for functions with Lipschitz constant $L_{f}$. Now note that
$|S((p_{1}+4\delta,1-p_{1}-4\delta),(p_{1},1-p_{1}))-S((p_{1},1-p_{1}),(p_{1},1-p_{1}))|$
is the cost to the expert of misreporting by $4\delta$ when the true
distribution is $(p_{1},1-p_{1})$. If this term is large, then the expert
cares a lot about not misreporting by $4\delta$, and if the term is small, the
expert does not mind misreporting much. Our result shows that the value of
this term is much larger for some $p_{1}$ than it is for others, i.e., that
for some probabilities $p_{1}$ the expert cares a lot more about accurately
reporting $p_{1}$ than it does for other values of $p_{1}$. Our theorem puts a
lower bound on the ratio between the lowest and largest possible values of
that term. In particular, this does not hinge on probabilities $p_{1}$ near
$0$ or $1$ and holds even if we restrict attention to probabilities between,
say, $1/4$ and $3/4$.

Theorem 5 shows that in the binary prediction case, given a Lipschitz constant
$L_{f}$ for the environment, we can achieve arbitrarily good bounds $\epsilon$
on the inaccuracy of the performatively optimal report. Unfortunately, this
ceases to be possible in the many-outcome case. In that case, if all we know
about $f$ is that it has Lipschitz constant $L_{f}$, there is some error
$\epsilon$, linear in $L_{f}$ as $L_{f}\rightarrow 0$, that we must allow
regardless of what strictly proper scoring rule we use.

######  Theorem 7.

For any Lipschitz constant $L_{f}$, for $\epsilon>0$ sufficiently small, there
is no proper scoring rule $S$ for the three-outcome case that achieves the
following property: Whenever $f$ is $L_{f}$-Lipschitz, there is some
performatively optimal report ${\bm{p}}$ with
$\|f({\bm{p}})-{\bm{p}}\|\leq\epsilon$. In particular, there exists some
function $\epsilon(L_{f})$ with $\epsilon(L_{f})\sim cL_{f}$ as
$L_{f}\rightarrow 0$ for some fixed constant $c$, s.t. the above property
cannot be achieved with $\epsilon=\epsilon(L_{f})$. Thus, the best achievable
bound is in $\Omega(L_{f})$ as $L_{f}\rightarrow 0$, i.e. scales at least
linearly with $L_{f}$ in the limit.

Figure 3: Scatter plots showing the L2 inaccuracy (left) and the distance to a
fixed point (right) of the performatively optimal reports against the operator
norm of $A$ in our experiments. In both plots, each point corresponds to a run
of the experiments. The blue lines are found by linear regression on the
points. The red lines are the bound given in Example 4 as a function of the
Lipschitz constant $L_{f}$.

##  7 Numerical simulations

In this section, we provide some numerical simulations for the Brier score, to
see how inaccurate performatively optimal predictions might be in practice.
Throughout, we consider only affine-linear functions $f$. This in particular
means that all functions $f$ have operator norms between $0$ and $1$ and aside
from degenerate cases a unique fixed point. The Mathematica notebook for our
experiments (including some interactive widgets) is available at
https://github.com/johannestreutlein/scoring-rules-performative. Although our
experiments are set in toy models with linear $f$ and small sets of outcomes,
they provide an initial estimate of the degree to which predictions can be
off, depending on how much influence the expert can exert using their
prediction.

###  7.1 Binary prediction

Experimental setup.  We begin with the binary prediction case, i.e.,
$\mathcal{N}=\\{1,2\\}$. We consider $f$ to be affine linear with slope
$\alpha$ and fixed point ${\bm{p}}^{*}\in\Delta(\mathcal{N})$, thus yielding
the functional form $f({\bm{p}}):={\bm{p}}^{*}+\alpha({\bm{p}}-{\bm{p}}^{*})$
for all ${\bm{p}}\in\Delta(\\{1,2\\})$. Note that for all $\alpha\in[0,1]$ and
all ${\bm{p}}^{*}\in\Delta(\mathcal{N})$, a function thus defined is indeed a
function $\Delta(\mathcal{N})\rightarrow\Delta(\mathcal{N})$. For $\alpha<0$,
whether $f$ is a function $\Delta(\mathcal{N})\rightarrow\Delta(\mathcal{N})$
depends on ${\bm{p}}^{*}$. We restrict attention to $\alpha\in[0,1]$ for
simplicity.

Graphing inaccuracy and distance to fixed points.  In Figure 2 (left), we plot
the inaccuracy $\|{\bm{p}}-f({\bm{p}})\|$ of the performatively optimal report
${\bm{p}}$ against $\alpha,p^{*}_{1}$. In Figure 2 (right), we plot the L2
distance $\|{\bm{p}}^{*}-{\bm{p}}\|$ of the performatively optimal report
${\bm{p}}$ to the fixed point ${\bm{p}}^{*}$. For that plot we limit $\alpha$
to the range $[0,0.95]$, because of instability at $\alpha\approx 1$. Note
that relatively high inaccuracies can be found at various qualitatively
different points in the graphs, even when the slope of $f$ is small, i.e.,
when the oracle has little influence on the environment.

Assessing our bounds.  To evaluate our bounds, we maximize distances across
possible choices of fixed points ${\bm{p}}^{*}\in\Delta(\\{1,2\\})$, and plot
the maximal inaccuracy of the optimal prediction as well as the maximal
distance from a fixed point in Figure 1. We compare to both theoretical bounds
from Example 4, i.e., $\|p-f(p)\|_{2}\leq\alpha/\sqrt{2}$ and
$\|p-p^{*}\|_{2}\leq\alpha/((1-\alpha)\sqrt{2})$.

For both quadratic and log scoring rule (results in Appendix C), our
theoretical bounds are tight for slopes $\alpha\leq 0.5$. For higher slopes,
inaccuracy goes down, as the function $f(p)$ becomes closer to the identity
function, and optimal predictions are bounded in $[0,1]$.

###  7.2 Higher-dimensional prediction

Experimental setup.  Next, we turn to higher-dimensional predictions. We
consider a model with five possible outcomes and linear $f\colon p\mapsto Ap$
for $A\in\mathbb{R}^{n\times n}$. $f$ is an automorphism on the simplex if and
only if all of its columns are in the simplex. We hence randomly generate the
matrix $A$ by sampling each column uniformly from the simplex. Note that $A$
is the Jacobian of $f$ at every point.

For each $f_{A}$ thus created, we first find the performatively optimal report
${\bm{p}}$ and the fixed point ${\bm{p}}^{*}$. We then record the following
quantities: the operator norm of $f_{A}$; the distance of the fixed point
distribution to the uniform distribution $\|{\bm{p}}^{*}-\frac{1}{n}\bm{1}\|$;
the distance of the optimal report to the uniform distribution
$\|{\bm{p}}-\frac{1}{n}\bm{1}\|$; the distance of the performatively optimal
report to the fixed point $\|{\bm{p}}^{*}-{\bm{p}}\|$; the inaccuracy of the
performatively optimal report $\|f({\bm{p}})-{\bm{p}}\|$. We are interested in
how the second two items depend on the first two. We are also interested in
how tight our bounds (from Example 4) are.

We collected 1000 random functions $f_{A}$, but aborted 52 runs because they
didn’t terminate within 120 seconds, leaving us with 948 data points.

Inaccuracy.  Figure 3 (left) plots the L2 inaccuracy (i.e., the distances
$\|{\bm{p}}-f({\bm{p}})\|$). The blue line shows the best linear fit to the
data points, which is given by $-0.0314+0.234x$, whereas our bound is
$2L_{f}/\sqrt{5}\approx 0.8944L_{f}$. The average L2 inaccuracy is $0.100$
with a standard deviation of $0.0770$. The quartiles are
$0.0419,0.0759,0.138$. The correlation between the operator norm of $f_{A}$
and $\|{\bm{p}}-f({\bm{p}})\|$ is $0.312$.

Distance to fixed points.  Figure 3 (right) plots the L2 distance to the fixed
point against the operator norm of $f_{A}$. The linear best fit (blue line) is
given by $-0.0966+0.440x$, whereas our bound is
$2L_{f}/(\sqrt{2}(1-L_{f}))\approx 0.8944L_{f}/(1-L_{f}).$ The average L2
distance to the fixed point is $0.152$ with a standard deviation of $0.154$
and quartiles $0.0442,0.0915,0.210$. The correlation between the operator norm
of $f_{A}$ and $\|{\bm{p}}^{*}-{\bm{p}}\|$ is $0.294$.

The role of the location of the fixed point.  The graphs for the binary
prediction case show that the location of the fixed point matters a lot for
the accuracy of optimal reports (though the direction of the effect depends on
the slope of $f$). A similar effect can be observed in the many outcome case.
In fact, the effect of the location of the fixed point is actually stronger
(though less reliable) than the effect of the operator norm of $f_{A}$. We
provide more detail in Section C.2.2.

Loose bounds, tight bounds.  Figures 3 and 3 show that (in contrast to the
binary prediction case), our bounds in terms of the operator norm of $f$ are
typically quite loose. For example, the average slack of the inaccuracy bound
is $0.404$ with a standard deviation of $0.0998$ and quartiles
$0.337,0.400,0.471$. Recall from Example 4 that in addition to bounds in terms
of $L_{f}$ alone we have bounds in terms of $L_{f}$ and
$\|{\bm{p}}-\frac{1}{n}\mathbf{1}\|$. These bounds are much tighter with an
average slack of $0.0644$ with a standard deviation of $0.0597$ and quartiles
$0.0274,0.0487,0.0830$.

Discussion.  Based on our simulations, misprediction in the five outcome case
seems similarly problematic as in the binary prediction case. In contrast to
the binary case, the bounds in terms of $L_{f}$ are quite loose. The bounds in
terms of $\|{\bm{p}}-\frac{1}{n}\mathbf{1}\|$ are much tighter. Note that
because these bounds depend on the performatively optimal report, they can
only be derived a posteriori once a report has been submitted. As in the two-
outcome case, both the location of the fixed point and the operator norm/slope
of $f$ matter a lot for accuracy and distance to fixed point of the
performatively optimal report.

##  8 Fixed points via alternative notions of optimality

Here, we focus on alternative settings that lead to accurate predictions and
do not induce preferences over fixed points. The idea behind all of them is
that, instead of optimizing ${\bm{p}}$ and $f({\bm{p}})$ jointly, we keep
$\bm{q}:=f({\bm{p}})$ fixed while choosing a prediction ${\bm{p}}$ to maximize
$S({\bm{p}},\bm{q})$. Repeating this procedure leads to honest predictions,
where the choice of fixed point depends on contingent facts such as
initialization, instead of being chosen to maximize $S({\bm{p}},{\bm{p}})$. An
AI model using this procedure could be safer, because its predictions are
honest, and because it does not optimize its choice of fixed point for any
goal. In this section we give a summary of a more detailed treatment with
formal results in Appendix D.

Performative stability.  Alternatives to performative optimality have been
discussed in the performative prediction literature. Translated into our
setting, a prediction ${\bm{p}}^{*}$ is called _performatively stable_ if
${\bm{p}}^{*}\in\operatorname*{arg\,max}_{{\bm{p}}}S({\bm{p}},f({\bm{p}}^{*}))$.
This implies ${\bm{p}}^{*}=f({\bm{p}}^{*})$ whenever $S$ is strictly proper,
so performative stability is equivalent to being a fixed point.

Repeated risk minimization and gradient descent.  Perdomo et al. [2020]
consider learning algorithms that converge to performatively stable points,
including repeated risk minimization and repeated gradient descent. In
repeated risk minimization, we repeatedly update predictions via
${\bm{p}}_{t+1}:=\operatorname*{arg\,max}_{\bm{p}}S({\bm{p}},f({\bm{p}}_{t}))$.
Repeated gradient descent instead updates predictions via gradient descent on
this objective. There also exist stochastic gradient descent versions of these
algorithms [Mendler-Dünner et al., 2020]. All of these schemes lead to stable
points under appropriate conditions. We include a convergence proof for
repeated gradient descent in our setting in Section D.2.

No-regret learning and prediction markets.  We also provide results for no-
regret learning (Section D.4) and prediction markets (Section D.5). We
introduce a no-regret learning setting and show that policies have sublinear
regret if and only if they have sublinear prediction error. This differs from
the setting considered by Jagadeesan et al. [2022], in which no-regret
policies converge to performatively optimal predictions. Next, we provide a
prediction market model and show that, if the weight of each trader in the
market is small, equilibrium predictions by the market are close to fixed
points. This is analogous to a result by Hardt et al. [2022] bounding the
distance of a market equilibrium from performatively stable points.

##  9 Related work

Performative prediction.  In performative prediction, the goal is to find a
model parameter $\theta\in\mathbb{R}^{d}$ that minimizes an expected loss
$\mathbb{E}[\ell(Z;\theta)]$ where $Z$ is a stochastic sample, usually a pair
of input and target, $Z=(X,Y)$. Unlike in the vanilla supervised learning
setting, $Z\sim\mathcal{D}(\theta)$ is sampled from a distribution
$\mathcal{D}(\theta)$ that itself depends on the chosen model parameter.
Performatively optimal parameters are defined via
$\theta_{\mathrm{PO}}\in\operatorname*{arg\,min}_{\theta}\mathbb{E}_{Z\sim\mathcal{D}(\theta)}[\ell(Z;\theta)]$,
and the definition of performatively stable parameters is
$\theta_{\mathrm{PS}}\in\operatorname*{arg\,min}_{\theta}\mathbb{E}_{Z\sim\mathcal{D}(\theta_{\mathrm{PS}})}\ell(Z;\theta)$.
In general, performatively stable and optimal parameters can differ [Perdomo
et al., 2020, Ex. 2.2].

Our setting could be seen as a special case in which $\theta$ is a single
distribution ${\bm{p}}$, data points are discrete outcomes $y$, and the
distribution $\mathcal{D}(\theta)$ is given by $f({\bm{p}})$. Unlike in the
general performative prediction setting, we can determine the accuracy of a
prediction ${\bm{p}}$ as the distance from the distribution $f({\bm{p}})$ (see
Theorem 3), we can characterize predictions as honest if they are fixed
points, and loss functions can be characterized as proper if they incentivize
honest reports. As mentioned in Section 8, performatively stable points are
fixed points and are thus a more desirable solution concept in our setting.
There are some performative prediction settings in which performative optima
can also be seen as manipulative and undesirable, such as in recommendation
algorithms [Hardt et al., 2022]. However, as far as we are aware, we are the
first to link performative stability to honesty in prediction.

Scoring rules.  While the literature on scoring rules generally assumes that
predictions are not performative, a few authors in this literature have
studied agents manipulating the world after making a prediction Shi et al.
[2009], Oka et al. [2014]. To our knowledge, the cases discussed do not
involve agents influencing the world directly through their predictions. Chan
[2022] introduce performative probabilistic predictions using scoring rules.
However, they focus on particular functional forms of $f$ and binary
predictions and do not provide a more general analysis. Another related
setting in which it has been shown that no proper scoring rules exist is that
of second-order prediction, in which experts report distributions over first-
order distributions to express epistemic uncertainty [Bengs et al., 2023].

AI oracles.  Issues with performativity have been mentioned in the literature
on AI predictors or oracles Armstrong and O’Rorke [2017]. Most prior work has
focused on alleviating performativity altogether, e.g., by making the oracle
predict _counterfactual worlds_ it cannot influence. We are not aware of any
prior work on specifically the question of whether AI oracles would be
incentivized to output fixed points at all.

Decision scoring rules and decision markets.  The literature on decision
scoring rules and decision markets considers a setting in which experts make
predictions about what would happen if a decision maker were to pursue one
course of action or another. The decision maker then chooses based on these
predictions, making the predictions performative. As shown by Othman and
Sandholm [2010], the expert may thus be incentivized to mispredict when
subject to a proper scoring rule. However, this literature typically takes the
perspective of the decision maker and thus assumes some knowledge of $f$. For
example, Othman and Sandholm [2010] and Oesterheld and Conitzer [2020b] show
that the scoring rule $S$ must be chosen to align in some sense with the
decision maker’s utility function (and thus $f$). Chen et al. [2014] propose
that the decision maker could randomize to set good incentives, which in our
setting would entail manipulating $f$.

Epistemic decision theory.  A related topic in philosophy is _epistemic
decision theory_. In particular, Greaves [2013] introduces several cases in
which outcomes depend on the agent’s credences and compares the verdicts of
different epistemic decision theories (such as an evidential and a causal
version). While some of Greaves’ examples involve agents knowably adopting
incorrect beliefs, they require joint beliefs over several propositions, and
Greaves only considers individual examples. We instead consider only a single
binary prediction and prove results for arbitrary scoring rules and
relationships between predictions and beliefs.

Honest and truthful AI.  Another related topic is honest and truthful AI
[Evans et al., 2021]. In our setting, an AI that reports an inaccurate
prediction to achieve a higher score would be dishonest. Evans et al. [2021]
discuss issues around training AIs to be truthful and honest, such as
difficulties in judging truth. However, they do not explore performativity or
proper scoring rules. We simplify our analysis by assuming that a ground truth
exists and can be judged objectively. Burns et al. [2022] discuss extracting
latent knowledge from AIs without relying on incentivizing honest reporting,
but also do not address performativity.

##  10 Conclusion and future work

If predictions cannot influence which outcome occurs, then strictly proper
scoring rules incentivize experts (humans or AI systems) to report honest
predictions. This fails if predictions are performative. We showed that, in
general, strictly proper scoring rules do not incentivize accurate predictions
in a performative prediction setting. We analyzed this inaccuracy
quantitatively and gave upper bounds on inaccuracy. We showed that in the case
of binary prediction, there exist scoring rules that incentivize arbitrarily
accurate predictions. In contrast, for more than two outcomes, it is not
possible to achieve arbitrarily strong bounds on accuracy. Our numerical
simulations in a toy setting confirm that our bounds are tight in some
situations and that inaccurate performative predictions are common. Finally,
we showed that by using other types of objectives, such as minimizing regret,
we can build AI models that predict fixed points.

We hope that future work will shed further light on practical and safe uses of
AI systems as predictors, i.e., oracle AIs. First, some of our bounds could
probably be improved or generalized (to non-differentiable $f,G$). Second, it
would be valuable to have more specific models of $f$. Precise models of $f$
may allow for stronger results [cf. Othman and Sandholm, 2010, Oesterheld and
Conitzer, 2020b]. Third, we take a simplistic view of safety: we take it that
incentives to predict honestly are good and that other incentives are
problematic. We hope that future work will augment our analysis with more
fine-grained models of safety. For example, a common safety concern is power-
seeking behavior [Omohundro, 2008, Turner et al., 2021]. One could similarly
ask to what extent performative oracle AI will spend compute to improve its
ability to influence the world (cf. discussions of information acquisition,
e.g. Osband, 1989; Neyman et al., 2021; Li et al., 2022; Oesterheld and
Conitzer, 2020a). Lastly, we are interested in theoretical and experimental
evaluations of the practicality of different safe oracle AI designs and
training setups.

###### Acknowledgements.

CO acknowledges funding from the Cooperative AI Foundation, Polaris Ventures
(formerly Center for Emerging Risk Research) and Jaan Tallinn’s donor-advised
fund at Founders Pledge. JT and RH carried out most of this work as part of
the SERI MATS program under the mentorship of Evan Hubinger (JT, RH) and Leo
Gao (RH). JT is grateful for support by an Open Phil AI Fellowship and an FLI
PhD Fellowship. We sincerely thank four anonymous reviewers whose insightful
comments helped us improve our paper. We are also indebted to Meena
Jagadeesan, Erik Jenner, Adam Jermyn, and Marius Hobbhahn for their valuable
discussions and feedback, and to Alexander Pan and Bastian Stern for pointing
us to the relevant related literature.

## References

  * Agrawal et al. [2009] S. Agrawal, E. Delage, M. Peters, Z. Wang, and Y. Ye.  A unified framework for dynamic pari-mutuel information market design.  In _EC ’09 Proceedings of the 10th ACM conference on Electronic commerce_ , pages 255–264. 2009.
  * Armstrong [2013] S. Armstrong.  Risks and mitigation strategies for oracle ai.  In _Philosophy and Theory of Artificial Intelligence_ , pages 335–347. Springer, 2013.
  * Armstrong [2018] S. Armstrong.  Standard ML Oracles vs counterfactual ones.  AI Alignment Forum, 2018.  URL https://www.alignmentforum.org/posts/hJaJw6LK39zpyCKW6/standard-ml-oracles-vs-counterfactual-ones.
  * Armstrong and O’Rorke [2017] S. Armstrong and X. O’Rorke.  Good and safe uses of AI oracles.  _arXiv preprint arXiv:1711.05541_ , 2017.
  * Armstrong et al. [2012] S. Armstrong, A. Sandberg, and N. Bostrom.  Thinking inside the box: Controlling and using an oracle ai.  _Minds and Machines_ , 22(4):299–324, 2012.
  * Azaïs and Wschebor [2009] J.-M. Azaïs and M. Wschebor.  _Level sets and extrema of random processes and fields_.  John Wiley & Sons, 2009.
  * Bell et al. [2021] J. Bell, L. Linsefors, C. Oesterheld, and J. Skalse.  Reinforcement learning in newcomblike environments.  _NeurIPS_ , 34:22146–22157, 2021.
  * Bengs et al. [2023] V. Bengs, E. Hüllermeier, and W. Waegeman.  On second-order scoring rules for epistemic uncertainty quantification.  _arXiv preprint arXiv:2301.12736_ , 2023.
  * Bostrom [2014] N. Bostrom.  _Superintelligence_.  Oxford University Press, 2014.
  * Brier [1950] G. W. Brier.  Verification of forecasts expressed in terms of probability.  _Monthly Weather Review_ , 78(1), 1 1950.
  * Brown et al. [2020] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al.  Language models are few-shot learners.  _NeurIPS_ , 33:1877–1901, 2020.
  * Burns et al. [2022] C. Burns, H. Ye, D. Klein, and J. Steinhardt.  Discovering latent knowledge in language models without supervision.  _arXiv preprint arXiv:2212.03827_ , 2022.
  * Carvalho [2016] A. Carvalho.  An overview of applications of proper scoring rules.  _Decision Analysis_ , 13(4):223–242, 2016.
  * Chan [2022] A. Chan.  Scoring rules for performative binary prediction.  _arXiv preprint arXiv:2207.02847_ , 2022.
  * Chen and Pennock [2007] Y. Chen and D. M. Pennock.  A utility framework for bounded-loss market makers.  In _UAI’07 Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence_ , pages 49–56. 2007.
  * Chen and Waggoner [2016] Y. Chen and B. Waggoner.  Informational substitutes.  In _2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 239–247, 2016.  10.1109/FOCS.2016.33.
  * Chen et al. [2014] Y. Chen, I. A. Kash, M. Ruberry, and V. Shnayder.  Eliciting predictions and recommendations for decision making.  In _ACM Transactions on Economics and Computation_ , number 2, chapter 6. 6 2014.
  * Demski [2019] A. Demski.  Partial agency.  AI Alignment Forum, 2019.  https://www.alignmentforum.org/posts/4hdHto3uHejhY2F3Q/partial-agency.
  * Evans et al. [2021] O. Evans, O. Cotton-Barratt, L. Finnveden, A. Bales, A. Balwit, P. Wills, L. Righetti, and W. Saunders.  Truthful AI: Developing and governing AI that does not lie.  _arXiv preprint arXiv:2110.06674_ , 2021.
  * Foerster et al. [2018] J. Foerster, G. Farquhar, M. Al-Shedivat, T. Rocktäschel, E. Xing, and S. Whiteson.  Dice: The infinitely differentiable monte carlo estimator.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80, pages 1529–1538. PMLR, 2018.
  * Gneiting and Raftery [2007] T. Gneiting and A. E. Raftery.  Strictly proper scoring rules, prediction, and estimation.  _Journal of the American statistical Association_ , 102(477):359–378, 2007.
  * Good [1952] I. J. Good.  Rational decisions.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 14:107–114, 1952.
  * Greaves [2013] H. Greaves.  Epistemic decision theory.  _Mind_ , 122(488):915–952, 2013.
  * Hanson [2003] R. Hanson.  Combinatorial information market design.  _Information Systems Frontiers_ , 5(1):107–119, 2003.
  * Hardt et al. [2022] M. Hardt, M. Jagadeesan, and C. Mendler-Dünner.  Performative power.  In _NeurIPS_ , 2022.
  * Hubinger et al. [2019] E. Hubinger, C. van Merwijk, V. Mikulik, J. Skalse, and S. Garrabrant.  Risks from learned optimization in advanced machine learning systems.  _arXiv preprint arXiv:1906.01820_ , 2019.
  * Izzo et al. [2021] Z. Izzo, L. Ying, and J. Zou.  How to learn when data reacts to your model: performative gradient descent.  In _Proceedings of the 38th International Conference on Machine Learning_ , pages 4641–4650. PMLR, 2021.
  * Jagadeesan et al. [2022] M. Jagadeesan, T. Zrnic, and C. Mendler-Dünner.  Regret minimization with performative feedback.  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162, pages 9760–9785. PMLR, 2022.
  * Jeffrey [1990] R. C. Jeffrey.  _The logic of decision_.  University of Chicago press, 1990.
  * Kitchen [1966] J. Kitchen.  Concerning the convergence of iterates to fixed points.  _Studia Mathematica_ , 27(3):247–249, 1966.
  * Krueger et al. [2020] D. Krueger, T. Maharaj, and J. Leike.  Hidden incentives for auto-induced distributional shift.  _arXiv preprint arXiv:2009.09153_ , 2020.
  * Letcher et al. [2019] A. Letcher, J. Foerster, D. Balduzzi, T. Rocktäschel, and S. Whiteson.  Stable opponent shaping in differentiable games.  In _International Conference on Learning Representations_ , 2019.
  * Li et al. [2022] Y. Li, J. D. Hartline, L. Shan, and Y. Wu.  Optimization of scoring rules.  In _Proceedings of the 23rd ACM Conference on Economics and Computation_ , pages 988–989, 2022.
  * McCarthy [1956] J. McCarthy.  Measures of the value of information.  _Proceedings of the National Academy of Sciences of the United States of America_ , 42:654–655, 9 1956.
  * Mendler-Dünner et al. [2020] C. Mendler-Dünner, J. Perdomo, T. Zrnic, and M. Hardt.  Stochastic optimization for performative prediction.  _NeurIPS_ , 33:4929–4939, 2020.
  * Neely [2021] M. J. Neely.  Infinitely often, probability 1, Borel-Cantelli, and the law of large numbers, 2021.  URL https://viterbi-web.usc.edu/~mjneely/Borel-Cantelli-LLN.pdf.
  * Neyman et al. [2021] E. Neyman, G. Noarov, and S. M. Weinberg.  Binary scoring rules that incentivize precision.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , pages 718–733, 2021.
  * Ngo et al. [2022] R. Ngo, L. Chan, and S. Mindermann.  The alignment problem from a deep learning perspective.  _arXiv preprint arXiv:2209.00626_ , 2022.
  * Oesterheld and Conitzer [2020a] C. Oesterheld and V. Conitzer.  Minimum-regret contracts for principal-expert problems.  In _Proceedings of the 16th Conference on Web and Internet Economics (WINE)_. 2020a.
  * Oesterheld and Conitzer [2020b] C. Oesterheld and V. Conitzer.  Decision scoring rules.  In _International Workshop on Internet and Network Economics_ , page 468, 2020b.
  * Oka et al. [2014] M. Oka, T. Todo, Y. Sakurai, and M. Yokoo.  Predicting own action: Self-fulfilling prophecy induced by proper scoring rules.  In _Second AAAI Conference on Human Computation and Crowdsourcing_ , 2014.
  * Omohundro [2008] S. M. Omohundro.  The basic ai drives.  In _Proceedings of the 2008 conference on Artificial General Intelligence: Proceedings of the First AGI Conference_ , pages 483–492. IOS Press, 2008.
  * Osband [1989] K. Osband.  Optimal forecasting incentives.  _Journal of Political Economy_ , 97(5):1091–1112, 10 1989.
  * Ostrovsky [2009] M. Ostrovsky.  Information aggregation in dynamic markets with strategic traders.  In _Proceedings of the 10th ACM conference on Electronic commerce_ , pages 253–254, 2009.
  * Othman and Sandholm [2010] A. Othman and T. Sandholm.  Decision rules and decision markets.  In _Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), van der Hoek, Kaminka, Lespérance, Luck and Sen (eds.), May, 10–14, 2010, Toronto, Canada_ , pages 625–632. 2010.
  * Pennock and Sami [2007] D. M. Pennock and R. Sami.  Computational aspects of prediction markets.  In N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, editors, _Algorithmic Game Theory_ , chapter 26, pages 651–675. Cambridge University Press, 2007.
  * Perdomo et al. [2020] J. Perdomo, T. Zrnic, C. Mendler-Dünner, and M. Hardt.  Performative prediction.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119, pages 7599–7609. PMLR, 2020.
  * Rasmussen and Williams [2006] C. E. Rasmussen and C. K. I. Williams.  _Gaussian Processes for Machine Learning_.  The MIT Press, 2006.
  * Russell [2019] S. J. Russell.  _Human Compatible: Artificial Intelligence and the Problem of Control_.  Viking, 2019.
  * Savage [1971] L. J. Savage.  Elicitation of personal probabilities and expectations.  _Journal of the American Statistical Association_ , 66:783–801, 12 1971.
  * Shi et al. [2009] P. Shi, V. Conitzer, and M. Guo.  Prediction mechanisms that do not incentivize undesirable actions.  In _International Workshop on Internet and Network Economics_ , pages 89–100. Springer, 2009.
  * Turner et al. [2021] A. Turner, L. Smith, R. Shah, A. Critch, and P. Tadepalli.  Optimal policies tend to seek power.  _NeurIPS_ , 34:23063–23074, 2021.
  * Uesato et al. [2020] J. Uesato, R. Kumar, V. Krakovna, T. Everitt, R. Ngo, and S. Legg.  Avoiding tampering incentives in deep RL via decoupled approval.  _arXiv preprint arXiv:2011.08827_ , 2020.
  * Weirich [2020] P. Weirich.  Causal Decision Theory.  In E. N. Zalta, editor, _The Stanford Encyclopedia of Philosophy_. Metaphysics Research Lab, Stanford University, Winter 2020 edition, 2020.

##  Appendix A Proofs

###  A.1 Preliminaries

We begin by proving a lemma characterizing the gradient
$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))$, which we will use throughout.

######  Lemma 1.

Assume $G,g,f$ are differentiable. Then

$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))=Dg({\bm{p}})^{\top}(f({\bm{p}})-{\bm{p}})+Df({\bm{p}})^{\top}g({\bm{p}}).$

If $S$ is strictly proper and ${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$
an optimal report, then

$({\bm{p}}-f({\bm{p}}))^{\top}Dg({\bm{p}})=g({\bm{p}})^{\top}Df({\bm{p}}).$

###### Proof.

We have

$\displaystyle\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))$
$\displaystyle=\nabla_{\bm{p}}\left(G({\bm{p}})+g({\bm{p}})^{\top}(f({\bm{p}})-{\bm{p}})\right)$
(1)
$\displaystyle=g({\bm{p}})+Dg({\bm{p}})^{\top}(f({\bm{p}})-{\bm{p}})+Df({\bm{p}})^{\top}g({\bm{p}})-Ig({\bm{p}})$
(2)
$\displaystyle=Dg(p)^{\top}(f({\bm{p}})-{\bm{p}})+Df({\bm{p}})^{\top}g({\bm{p}}).$
(3)

Next, if ${\bm{p}}$ is an optimal report and an interior point, it must be
$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))^{\top}\bm{v}=0$ for any
$\bm{v}\in\mathcal{T}$. Since
$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))\in\mathcal{T}$, it follows that
$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))=0$. Hence, using the above, it
follows that

$\displaystyle\phantom{\Rightarrow}0=\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))=Dg(p)^{\top}(f({\bm{p}})-{\bm{p}})+Df({\bm{p}})^{\top}g({\bm{p}})$
(4) $\displaystyle\Rightarrow
Dg({\bm{p}})^{\top}({\bm{p}}-f({\bm{p}}))=Df({\bm{p}})^{\top}g({\bm{p}}).$ (5)

∎

###  A.2 Proof of Proposition 1

See 1

###### Proof.

Figure 4: Illustration of the setup for our proof. We plot $f_{0}$ in black
and $f_{\alpha}$ for $\alpha=0.15$ in red, projected onto a single dimension.

To begin, let ${\bm{p}}^{*}\in\mathrm{int}(\Delta(\mathcal{N}))$ arbitrary and
define $f_{\alpha}({\bm{p}}):=(1-\alpha){\bm{p}}+\alpha{\bm{p}}^{*}$ for
$\alpha\in[0,1]$ and ${\bm{p}}\in\Delta(\mathcal{N})$. Note that since
$\Delta(\mathcal{N})$ is convex, $f_{\alpha}({\bm{p}})\in\Delta(\mathcal{N})$.
Let $G$ be as in the Gneiting and Raftery characterization of $S$ (Theorem 1).

To provide an intuition of how our proof will work, consider a binary
prediction setting with $f$ as given in Figure 4. For any $\alpha>0$,
$f_{\alpha}$ has a unique fixed point at ${\bm{p}}^{*}$, while $f_{0}$ is the
identity function, so all points are fixed points of $f_{0}$. By strict
convexity of $G$, there exists a point ${\bm{p}}^{\prime}$ which receives a
strictly higher score than ${\bm{p}}^{*}$ if it is a fixed point, so
$S({\bm{p}}^{\prime},f_{0}({\bm{p}}^{\prime}))>S({\bm{p}}^{*},f_{0}({\bm{p}}^{*}))$.
${\bm{p}}^{\prime}$ is not a fixed point of $f_{\alpha}$ for $\alpha>0$.
However, we will show that
$S({\bm{p}}^{\prime},f_{\alpha}({\bm{p}}^{\prime}))$ must be continuous in
$\alpha$, which means that we can choose a small enough $\alpha>0$ to make
sure that ${\bm{p}}^{\prime}$ remains preferable over ${\bm{p}}^{*}$, i.e.,
$S({\bm{p}}^{\prime},f_{\alpha}({\bm{p}}^{\prime}))>S({\bm{p}}^{*},f_{\alpha}({\bm{p}}^{*}))$,
despite it not being a fixed point.

To formalize the proof, begin by noting that

$\|f_{\alpha}({\bm{p}})-f_{\alpha}({\bm{p}}^{\prime})\|=\|(1-\alpha)({\bm{p}}-{\bm{p}}^{\prime})\|=(1-\alpha)\|{\bm{p}}-{\bm{p}}^{\prime}\|$

for any ${\bm{p}},{\bm{p}}^{\prime}\in\Delta(\mathcal{N})$, so $f_{\alpha}$
has Lipschitz constant $L:=(1-\alpha)<1$, and as mentioned, ${\bm{p}}^{*}$ is
the unique fixed point of $f_{\alpha}$.

Now consider the case $\alpha=0$. As mentioned, every point is a fixed point
of $f_{0}$. Then by strict convexity of $G,$ since ${\bm{p}}^{*}$ is an
interior point, there exists another interior point
${\bm{p}}^{\prime}\in\mathrm{int}(\Delta(\mathcal{N}))$ and $\epsilon>0$ such
that $G({\bm{p}}^{\prime})\geq G({\bm{p}}^{*})+\epsilon.$ It follows that

$S({\bm{p}}^{\prime},f_{0}({\bm{p}}^{\prime}))=S({\bm{p}}^{\prime},{\bm{p}}^{\prime})\geq
S({\bm{p}}^{*},{\bm{p}}^{*})+\epsilon=S({\bm{p}}^{*},f_{0}({\bm{p}}^{*}))+\epsilon.$
(6)

So for $\alpha=0$, the model prefers to predict ${\bm{p}}^{\prime}$ over
${\bm{p}}^{*}$ and gets at least $\epsilon$ additional expected score. Lastly,
note that since ${\bm{p}}^{\prime}$ is an interior point as well, it follows
that $G({\bm{p}}^{\prime})<\infty$.

Now we show that the model still prefers to predict ${\bm{p}}^{\prime}$, even
for some small $\alpha>0$. To that end, note that

$S({\bm{p}}^{\prime},f_{\alpha}({\bm{p}}^{\prime}))=\mathbb{E}_{y\sim
f_{\alpha}({\bm{p}}^{\prime})}[S({\bm{p}}^{\prime},y)]$

is linear in $f_{\alpha}({\bm{p}}^{\prime})$, and
$f_{\alpha}({\bm{p}}^{\prime})$ is affine-linear in $\alpha$ by construction.
This means that $S({\bm{p}},f_{\alpha}({\bm{p}}))$ is continuous in $\alpha$.
So there must exist some small $\alpha>0$ such that

$\displaystyle S({\bm{p}}^{\prime},f_{\alpha}({\bm{p}}^{\prime}))$
$\displaystyle\geq
S({\bm{p}}^{\prime},f_{0}({\bm{p}}^{\prime}))-\frac{\epsilon}{2}=S({\bm{p}}^{\prime},{\bm{p}}^{\prime})-\frac{\epsilon}{2}$
(7)
$\displaystyle\underset{\text{(\ref{eq:1})}}{\geq}S({\bm{p}}^{*},{\bm{p}}^{*})+\frac{\epsilon}{2}>S({\bm{p}}^{*},{\bm{p}}^{*})$
(8) $\displaystyle=S({\bm{p}}^{*},f({\bm{p}}^{*})).$ (9)

Choosing $\alpha$ in this way, we can define $f:=f_{\alpha}$, and have thus
provided a function that satisfies the statement that we wanted to prove. ∎

###  A.3 Proof of Theorem 2

We begin with two lemmas. In the following, we always assume a strictly proper
scoring rule $S$ and accompanying functions $G,g$ as in the Gneiting and
Raftery characterization (Theorem 1). Moreover, we let
$\Pi_{n-1}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}^{n-1}$ be the projection
onto $\mathbb{R}^{n}$, defined via $\Pi_{n-1}\bm{x}=(x_{i})_{1\leq i\leq n-1}$
for $\bm{x}\in\mathbb{R}^{n}$. We will not go into issues of measurability in
our proofs.

First, we show that if ${\bm{p}}^{*}\in\mathrm{int}(\Delta(\mathcal{N}))$ is a
fixed point of $f$, then either $g({\bm{p}}^{*})=0$ or
$Df({\bm{p}})|_{\mathcal{T}}$, i.e., the map

$Df({\bm{p}})\colon\mathcal{T}\rightarrow\mathcal{T},\bm{v}\mapsto
Df({\bm{p}})\bm{v},$

is singular.

######  Lemma 2.

Let $G,g$, and $f$ be differentiable. Let
${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$ be a fixed point of $f$ and a
performatively optimal prediction. Then $Df({\bm{p}})|_{\mathcal{T}}$ is
singular or $g({\bm{p}})=0$.

###### Proof.

Note that $f({\bm{p}})\in\Delta(\mathcal{N})$ for all
${\bm{p}}\in\Delta(\mathcal{N})$, so
$\partial_{\bm{v}}f({\bm{p}})=Df({\bm{p}})\bm{v}\in\mathcal{T}$ for all
$\bm{v}\in\mathcal{T}$. Hence, $Df({\bm{p}})$ defines an automorphism
$Df({\bm{p}})|_{\mathcal{T}}$.

It follows from Lemma 1 that
$Dg({\bm{p}})^{\top}({\bm{p}}-f({\bm{p}}))=Df({\bm{p}})^{\top}g({\bm{p}})$.
Since $f({\bm{p}})-{\bm{p}}=0$, it must be $Df({\bm{p}})^{\top}g({\bm{p}})=0$,
so either $g({\bm{p}})=0$, or $Df({\bm{p}})^{\top}$ (and thus also
$Df({\bm{p}})$) is singular when restricted to $\mathcal{T}$. ∎

Next, we show that the fixed points of $f$ are almost surely not at points
${\bm{p}}$ such that $g({\bm{p}})=0$, under our assumptions on the
distribution over $f$.

######  Lemma 3.

Let
$\mathcal{F}\vcentcolon=\\{F({\bm{p}})\\}_{{\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))}$
be a stochastic process with values in $\Delta(\mathcal{N})$ and assume that
for each ${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$, the random vector
$\Pi_{n-1}F({\bm{p}})$ has a density $h_{\Pi_{n-1}F({\bm{p}})}$. Then almost
surely if $F({\bm{p}})={\bm{p}}$ for some
${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$ then $g({\bm{p}})\neq 0$. That
is,

$\mathbb{P}(\exists{\bm{p}}\colon F({\bm{p}})={\bm{p}}\land g({\bm{p}})=0)=0.$

###### Proof.

First note that if $S$ is strictly proper, then $G$ is strictly convex and so
there exists at most one ${\bm{p}}\in\Delta(\mathcal{N})$ with
$g({\bm{p}})=0$. If there is no such point, then we are done. Otherwise, let
that point be ${\bm{p}}^{*}$. Since we assume that $\Pi_{n-1}F({\bm{p}}^{*})$
has a density function $h_{\Pi_{n-1}F({\bm{p}}^{*})}$, it follows that

$\mathbb{P}(F({\bm{p}}^{*})={\bm{p}}^{*})=\mathbb{P}(\Pi_{n-1}F({\bm{p}}^{*})=\Pi_{n-1}{\bm{p}}^{*})=\int_{\\{\Pi_{n-1}{\bm{p}}^{*}\\}}h_{\Pi_{n-1}F({\bm{p}}^{*})}(\bm{x})d\bm{x}=0.$

∎

Lastly, we require a result about random fields. The following is adapted from
Proposition 6.11 in Azaïs and Wschebor [2009].

######  Proposition 2 (Azaïs and Wschebor [2009], Proposition 6.11).

Let $\mathcal{Y}=\\{Y(\bm{x})\\}_{\bm{x}\in W}$ be a random field with values
in $\mathbb{R}^{d}$ and $W$ an open subset of $\mathbb{R}^{d^{\prime}}$. Let
$\bm{u}\in\mathbb{R}^{d}$ and $I\subseteq W$. Assume that

  * •

the sample paths $\bm{x}\rightsquigarrow Y(\bm{x})$ are continuously
differentiable

  * •

for each $\bm{x}\in W$, $Y(\bm{x})$ has a density $h_{Y(\bm{x})}$ and there
exists a constant $C$ such that $h_{Y(\bm{x})}(\bm{y})\leq C$ for all
$\bm{x}\in I$ and $\bm{y}\in\mathbb{R}^{d}$.

  * •

The Hausdorff dimension of $I$ is strictly smaller than $d$.

Then, almost surely, there is no point $\bm{x}\in I$ such that
$Y(\bm{x})=\bm{u}$.

Now we can turn to the proof of the main result.

See 2

###### Proof.

We want to show that almost surely there does not exist
${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$ such that
$F({\bm{p}})={\bm{p}}$ and ${\bm{p}}$ is performatively optimal. I.e., we want
to show that

$\mathbb{P}(\exists{\bm{p}}\colon
F({\bm{p}})={\bm{p}}\land{\bm{p}}\in\operatorname*{arg\,max}S({\bm{p}},F({\bm{p}})))=0.$

First, let ${\bm{p}}^{*}\in\mathrm{int}(\Delta(\mathcal{N}))$ be a
performatively optimal report. By Lemma 2, either $g({\bm{p}}^{*})=0$ or
$DF({\bm{p}}^{*})|_{\mathcal{T}}$ is singular. Moreover, by assumption,
$(\Pi_{n-1}F({\bm{p}}),\Pi_{n-1}DF({\bm{p}})\bm{v})$ has a density function
for any $\bm{v}\in\mathcal{T}\cap S^{n-1}$, and thus also
$\Pi_{n-1}F({\bm{p}})$ has one. Hence, by Lemma 3, it follows that if
$F({\bm{p}})={\bm{p}}$ for some
${\bm{p}}\in\mathrm{int}(\Delta(\mathcal{N}))$, then almost surely
$g({\bm{p}})=0$.

Second, we need to show that also almost surely $DF({\bm{p}})|_{\mathcal{T}}$
is invertible at any fixed point of $F$. To that end, define the random field
$\mathcal{Y}:=\\{Y({\bm{p}},\bm{v})\\}_{({\bm{p}},\bm{v})\in W}$ where
$W:=\mathrm{int}(\Delta(\mathcal{N}))\times\mathcal{T}$ and

$Y({\bm{p}},\bm{v}):=(\Pi_{n-1}F({\bm{p}})-\Pi_{n-1}{\bm{p}},\Pi_{n-1}DF({\bm{p}})\bm{v}),$

with values in $\mathbb{R}^{n-1}\times\mathbb{R}^{n-1}$.

Note that since $F$ is in $\mathcal{C}^{2}$, $DF$ is continuously
differentiable, and thus also $Y$. Moreover

$h_{Y({\bm{p}},\bm{v})}(\bm{x},\bm{y})=h_{\Pi_{n-1}F({\bm{p}}),\Pi_{n-1}DF({\bm{p}})\bm{v}}(\bm{x}+\Pi_{n-1}{\bm{p}},\bm{y})\leq
C$

for $\bm{x},\bm{y}\in\mathbb{R}^{n-1}$ by assumption. Finally, define
$\bm{u}:=(0,0)\in\mathbb{R}^{n-1}\times\mathbb{R}^{n-1}$ and
$I:=\Delta(\mathcal{N})\times(\mathcal{T}\cap S^{n-1})$, where
$\mathcal{T}\cap S^{n-1}=\\{\bm{v}\in\mathcal{T}\mid\|\bm{v}\|=1\\}$. Note
that the Hausdorff dimension of $I$ is $n-1+n-2=2n-3$, while $Y$’s values are
$2n-2$-dimensional.

This shows all conditions of Proposition 2, so we can apply it to $Y$ to
conclude that almost surely there exists no ${\bm{p}},\bm{v}\in I$ such that
$Y({\bm{p}},\bm{v})=(0,0)$. This means that almost surely there exists no
point ${\bm{p}}\in\Delta(\mathcal{N})$ such that $F({\bm{p}})={\bm{p}}$ and
such that $DF({\bm{p}})|_{\mathcal{T}}$ is singular, since if such a point
existed, then also there would be a vector $\bm{v}\in\mathcal{T}\cap S^{n-1}$
such that $DF({\bm{p}})\bm{v}=0$ and thus $\Pi_{n-1}DF({\bm{p}})\bm{v}=0$,
implying that

$Y({\bm{p}},\bm{v})=(\Pi_{n-1}F({\bm{p}})-\Pi_{n-1}{\bm{p}},\Pi_{n-1}DF({\bm{p}})\bm{v})=0.$

Summarizing our argument, it follows that

$\mathbb{P}(\exists{\bm{p}}\colon{F({\bm{p}})={\bm{p}}}\land{{\bm{p}}\in\operatorname*{arg\,max}S({\bm{p}},F({\bm{p}}))})$
$\leq\mathbb{P}(\exists{\bm{p}}\colon{F({\bm{p}})={\bm{p}}}\land{g({\bm{p}})=0})+\mathbb{P}(\exists{\bm{p}}\colon{F({\bm{p}})={\bm{p}}}\land{DF({\bm{p}})\text{
is singular}})=0.$

This concludes the proof. ∎

We conclude by providing an example of a stochastic process that satisfies our
conditions, for the binary prediction case.

######  Example 5.

Consider a Gaussian process $\\{X(p)\\}_{p\in(0,1)}$ with values in
$\mathbb{R}$, with infinitely differentiable kernel and mean functions. We can
make it into a process $F({\bm{p}})$ by defining
$F({\bm{p}})=(X(p_{1}),1-X(p_{1}))$ for ${\bm{p}}\in\Delta([2])$. Note that
the paths of $F$ are infinitely differentiable and the values of
$\Pi_{1}F({\bm{p}})=X(p_{1})$ and its directional derivatives
$\Pi_{1}DF({\bm{p}})\bm{v}=X^{\prime}(p_{1})v_{1}$ are jointly Gaussian and
thus have a bounded density [see Rasmussen and Williams, 2006, Ch. 9.4]. To
deal with the restriction that $X(p)\in[0,1]$ for $p\in(0,1)$, we could
condition on the event $E:=\\{\forall p\colon F(p)\in[0,1]\\}$, for instance.
Then paths are still twice differentiable, and we claim that $h_{X(p)|E}$,
defined as the density of $X$ at point $p$, conditional on $E$, is still
bounded. To see that, note that if $\mathbb{P}(E)>0$, then we are done, since
then

$h_{X(p)|E}(x)=\frac{\mathbbm{1}_{E}(x)}{\mathbb{P}(E)}h_{X(p)}(x).$

We leave it as an exercise to the reader to prove that $\mathbb{P}(E)>0$.

###  A.4 Proof of Theorem 3

See 3

Recall that we assume that $g({\bm{p}})$ is normalized to be orthogonal to
$\mathbf{1}$. Note that this is also the choice that minimizes
$\|g({\bm{p}})\|$ and makes sure that
$\|g({\bm{p}})\|=\|g({\bm{p}})^{\top}|_{\mathcal{T}}\|_{\mathrm{op}}$, where
$g({\bm{p}})^{\top}|_{\mathcal{T}}$ denotes the function
$\mathcal{T}\rightarrow\mathbb{R}\colon\mathbf{v}\mapsto
g({\bm{p}})^{\top}\mathbf{v}$. This is due to the Cauchy–Schwarz inequality
and the Pythagorean theorem, since
$\|g({\bm{p}})+\alpha\mathbf{1}\|^{2}=\|g({\bm{p}})\|^{2}+|\alpha|^{2}\|\mathbf{1}\|^{2}$
for any $\alpha\in\mathbb{R}$ when $g({\bm{p}})\in\mathcal{T}$. Moreover, by
Cauchy–Schwarz, we have
$\|g({\bm{p}})^{\top}\bm{v}\|\leq\|g({\bm{p}})\|\|\bm{v}\|$ for any
$\bm{v}\in\mathcal{T}$ and if $g({\bm{p}})\in\mathcal{T}$ then
$\|g({\bm{p}})^{\top}|_{\mathcal{T}}\|_{\mathrm{op}}\geq\|g({\bm{p}})^{\top}g({\bm{p}})\|/\|g({\bm{p}})\|=\|g({\bm{p}})\|$.

###### Proof.

Assume ${\bm{p}}$ is a performatively optimal report and that
$Dg({\bm{p}})|_{\mathcal{T}}\succeq\gamma_{p}$. Note that this is equivalent
to all eigenvalues of the function $Dg({\bm{p}})|_{\mathcal{T}}$ being at
least $\gamma_{p}$, assuming $Dg({\bm{p}})|_{\mathcal{T}}$ is symmetric.
Moreover, $Dg({\bm{p}})$ must be symmetric if $G$ is twice differentiable
(note that continuous differentiability is not needed since we assume
differentiability in general, not just existence of the coordinate partial
derivatives). This can be used to calculate our bound in practice.

Consider
$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))^{\top}(f({\bm{p}})-{\bm{p}}),$ the
directional derivative of $\varphi\colon{\bm{p}}\mapsto
S({\bm{p}},f({\bm{p}}))$ in the direction $(f({\bm{p}})-{\bm{p}})$. Note that
this derivative must be at most zero: The line from ${\bm{p}}$ to
$f({\bm{p}})$ lies entirely within the probability simplex, and so if the
derivative were positive, $S({\bm{p}},f({\bm{p}}))$ could be increased by
moving in the direction of $f({\bm{p}})$ from ${\bm{p}}$. By Lemma 1, we know
that

$\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))=Dg({\bm{p}})^{\top}(f({\bm{p}})-{\bm{p}})+Df({\bm{p}})^{\top}g({\bm{p}}).$

It follows that

$\displaystyle
0\geq\nabla_{\bm{p}}(S({\bm{p}},f({\bm{p}})))^{\top}(f({\bm{p}})-{\bm{p}})=(f({\bm{p}})-{\bm{p}})^{\top}Dg({\bm{p}})(f({\bm{p}})-{\bm{p}})+g({\bm{p}})^{\top}Df({\bm{p}})(f({\bm{p}})-{\bm{p}})$
(10) $\displaystyle\Rightarrow$
$\displaystyle-g({\bm{p}})^{\top}Df({\bm{p}})(f({\bm{p}})-{\bm{p}})\geq(f({\bm{p}})-{\bm{p}})^{\top}(Dg({\bm{p}}))(f({\bm{p}})-{\bm{p}}).$
(11)

Using that $Dg({\bm{p}})|_{\mathcal{T}}\succ\gamma_{\bm{p}}$ and thus
$(f({\bm{p}})-{\bm{p}})^{\top}(Dg({\bm{p}}))(f({\bm{p}})-{\bm{p}})\geq\gamma_{\bm{p}}\|f({\bm{p}})-{\bm{p}}\|^{2}$
, it follows that

$\displaystyle\gamma_{\bm{p}}\|f({\bm{p}})-{\bm{p}}\|^{2}$ $\displaystyle\leq$
$\displaystyle(f({\bm{p}})-{\bm{p}})^{\top}Dg({\bm{p}})(f({\bm{p}})-{\bm{p}})$
$\displaystyle\leq$
$\displaystyle-g({\bm{p}})^{\top}Df({\bm{p}})(f({\bm{p}})-{\bm{p}})$
$\displaystyle\leq$
$\displaystyle|g({\bm{p}})^{\top}Df({\bm{p}})(f({\bm{p}})-{\bm{p}})|$
$\displaystyle\underset{\text{Cauchy-Schwarz}}{\leq}$
$\displaystyle\|g({\bm{p}})\|\|Df({\bm{p}})(f({\bm{p}})-{\bm{p}})\|$
$\displaystyle\leq$
$\displaystyle\|g({\bm{p}})\|\|Df({\bm{p}})\|_{\mathrm{op}}\|f({\bm{p}})-{\bm{p}}\|$

Dividing by $\gamma_{\bm{p}}\|f({\bm{p}})-{\bm{p}}\|$, we get that
$\|f({\bm{p}})-{\bm{p}}\|\leq\|Df({\bm{p}})\|_{\mathrm{op}}\|g({\bm{p}})\|/\gamma_{\bm{p}}$.

For the “in particular” part, note that if $f$ is Lipschitz continuous with
constant $L_{f}$, then $\|Df({\bm{p}})\|_{\mathrm{op}}\leq L_{f}$ for all
${\bm{p}}$. Moreover, if $G$ is Lipschitz continuous with constant $L_{G}$, we
have

$L_{G}\geq\|DG({\bm{p}})\|_{\mathrm{op}}=\|g({\bm{p}})^{\top}\|_{\mathrm{op}}=\|g({\bm{p}})\|$

for all ${\bm{p}}\in\Delta(\mathcal{N})$. Here, in the last step, we have used
that for the Euclidean norm

$\|g({\bm{p}})^{\top}\|_{\mathrm{op}}=\max_{\bm{v}\in\mathcal{T}}\frac{g({\bm{p}})^{\top}\bm{v}}{\|\bm{v}\|}=\frac{g({\bm{p}})^{\top}g({\bm{p}})}{\|g({\bm{p}})\|}=\|g({\bm{p}})\|.$

Lastly, $G$ being $\gamma$-strongly convex implies that
$D^{2}G({\bm{p}})\succeq\gamma$ for all ${\bm{p}}\in\Delta(\mathcal{N})$, and
thus also $Dg({\bm{p}})=D^{2}G({\bm{p}})^{\top}\succeq\gamma$.

Putting everything together, we get

$\|f({\bm{p}})-{\bm{p}}\|\leq\frac{\|g({\bm{p}})\|\|Df({\bm{p}})\|_{\mathrm{op}}}{\gamma_{p}}\leq\frac{L_{G}L_{f}}{\gamma}$

for all performatively optimal reports ${\bm{p}}$. ∎

###  A.5 Proof of Theorem 4

See 4

###### Proof.

For any ${\bm{p}}\in\Delta(\mathcal{N})$, we have

$\displaystyle\|{\bm{p}}-{\bm{p}}^{*}\|$
$\displaystyle\underset{\text{triangle ineq.}}{\leq}$
$\displaystyle\|{\bm{p}}-f({\bm{p}})\|+\|f({\bm{p}})-{\bm{p}}^{*}\|$
$\displaystyle\underset{p^{*}\text{ fixpoint}}{=}$
$\displaystyle\|{\bm{p}}-f({\bm{p}})\|+\|f({\bm{p}})-f({\bm{p}}^{*})\|$
$\displaystyle\leq$
$\displaystyle\|{\bm{p}}-f({\bm{p}})\|+L_{f}\|{\bm{p}}-{\bm{p}}^{*}\|$

Solving for $\|{\bm{p}}-{\bm{p}}^{*}\|$ yields

$\|{\bm{p}}-{\bm{p}}^{*}\|\leq\frac{\|{\bm{p}}-f({\bm{p}})\|}{1-L_{f}}.$

Hence, if ${\bm{p}}\in\Delta(\mathcal{N})$ is an optimal prediction, it
follows by Theorem 3 that

$\displaystyle\|{\bm{p}}-{\bm{p}}^{*}\|_{2}$ $\displaystyle\leq$
$\displaystyle\frac{\|{\bm{p}}-f({\bm{p}})\|}{1-L_{f}}$ $\displaystyle\leq$
$\displaystyle\frac{\|Df({\bm{p}})\|_{\mathrm{op}}\|g({\bm{p}})\|}{\gamma_{{\bm{p}}}(1-L_{f})}$
$\displaystyle\leq$
$\displaystyle\frac{L_{f}\|g({\bm{p}})\|}{\gamma_{{\bm{p}}}(1-L_{f})},$

which concludes the proof. ∎

###  A.6 There is no non-trivial bound on the distance to the fixed point as
$L_{f}\rightarrow 1$

We here show why Theorem 4 requires that we have some bound $L_{f}<1$ on the
function $f$. Specifically, we show that if $f$ can have Lipschitz constants
arbitrarily close to $1$, then even in the two-outcome case, only the trivial
bound on the difference to the fixed point holds. (The trivial bound is
$\lVert{\bm{p}}^{*}-{\bm{p}}\rVert\leq\sqrt{2}$, because any two points in
$\Delta(\\{1,2\\})$ are at most $\lVert(0,1)-(1,0)\rVert=\sqrt{2}$ apart.) We
prove that this holds even for the binary case.

######  Proposition 3.

Consider the case of two outcomes, i.e., let $\mathcal{N}=\\{1,2\\}$. Let $S$
be any strictly proper scoring rule. Then there exist functions $f$ with
Lipschitz constants smaller than $1$ such that
$\lVert{\bm{p}}^{*}-{\bm{p}}\rVert$ is arbitrarily close to $\sqrt{2}$, where
${\bm{p}}^{*}$ is the fixed point of $f$ and ${\bm{p}}$ is the optimal
prediction for $S,f$.

Figure 5: The blue line is the function used in the proof of Proposition 3.
The orange line is the identity function.

We here give some intuition for why the result holds. Recall that, roughly
speaking, scoring rules generally induce a preference for extreme honest
predictions over non-extreme honest predictions (see Appendix B). In
particular, in the binary case any scoring rule must either incentivize near-0
honest predictions or near-1 honest predictions (or both) over honest
relatively close-to-uniform predictions. Consider the case where $S$
incentivizes predictions close to $0$ over more uniform predictions and take
the function $f$ in Figure 5. The unique fixed point is at $0.8$. But if a
prediction close to $0$ is made, the prediction is approximately honest while
more extreme than $0.8$. It turns out that a slight dishonesty (discrepancy
between the report ${\bm{p}}$ and the true distribution $f({\bm{p}})$) can be
outweighed by the fact that the prediction is more extreme. Predicting near
$0$ may therefore be a better report than a of prediction $0.8$.

Note that in this example, the distance of the optimal report to fixed point
($\lVert{\bm{p}}-{\bm{p}}^{*}\rVert$) and the inaccuracy of the optimal report
($\lVert{\bm{p}}-f({\bm{p}})\rVert$) come apart: The optimal report might be
far from the fixed point but still very accurate.

###### Proof.

For notational convenience, we consider functions $f:[0,1]\rightarrow[0,1]$ on
a single probability and similarly scoring rules
$S:[0,1]\times[0,1]\rightarrow\mathbb{R}$.

Let $\zeta$ be a small positive real number and let $\delta$ be s.t.
$0<\delta<\zeta/2$. By the strict convexity of the function $x\mapsto S(x,x)$,
one of the following must be the case:

  1. 1.

$S(\delta,\delta)>\max_{x\in[2\delta,1-2\delta]}S(x,x)$; or

  2. 2.

$S(1-\delta,1-\delta)>S(x,x)$ for all $x$ between $2\delta$ and $1-2\delta$.

Consider the first case: Now for small positive $\epsilon$ consider the
function $f_{\epsilon}$ that starts at some small positive value and increases
linearly at rate $1-\epsilon$ from $0$ to $1-\zeta$ and is fixed at value
$1-\zeta$ from $1-\zeta$ to $1$. Figure 5 illustrates this function for
$\zeta=0.2,\epsilon=0.03,\delta=0.1$. Formally, $f_{\epsilon}(p)=1-\zeta$ for
$p\geq\zeta$ and otherwise $f_{\epsilon}(p)=1-\zeta-(1-\zeta-p)(1-\epsilon)$.
Note that $f_{\epsilon}$’s fixed point is $1-\zeta$ and $f_{\epsilon}$’s
Lipschitz constant is $1-\epsilon$. We will show that for small enough
$\epsilon$ the optimal report for $f_{\epsilon}$ and $S$ is then close to $0$
and thus almost $1$ away from the fixed point, which means the distance is
close to $\sqrt{2}$ in the simplex. Note that by continuity of $f_{\epsilon}$
and linearity (and thus continuity) of $S(p,q)$ in $q$, we have that
$S(\delta,f_{\epsilon}(\delta))\rightarrow S(\delta,\delta)$ as
$\epsilon\rightarrow 0$. Thus, for small enough $\epsilon$, we have for all
$x$ between $2\delta$ and $1-2\delta$ that
$S(\delta,f_{\epsilon}(\delta))>S(x,x)$. It follows that the optimal report
$p$ cannot have $f_{\epsilon}(p)\in[2\delta,1-2\delta]\supset[\zeta,1-\zeta]$,
because then we would have that
$S(\delta,f_{\epsilon}(\delta))>S(f_{\epsilon}(p),f_{\epsilon}(p))>S(p,f_{\epsilon}(p))$,
i.e., $\delta$ would be a better report. By construction of $f_{\epsilon}$,
this means that the optimal report cannot be in $[2\delta,1]$. Thus, the
distance of the optimal report to the fixed point is at least
$1-\zeta-2\delta$. By choosing $\delta$ and $\zeta$ to be small, we can make
this arbitrarily close to $1$.

The second case can be considered analogously, by considering a function $f$
that is constant at value $\zeta$ from $0$ to $\zeta$ and then increases
linearly at rate $1-\epsilon$. ∎

###  A.7 Proof of Theorem 5

See 5

###### Proof.

Consider the exponential scoring rule defined by
$G({\bm{p}})=\frac{2}{K}e^{Kp_{1}}$ and
$g({\bm{p}})=(e^{Kp_{1}},-e^{Kp_{1}})^{\top}$ s.t.
$Dg({\bm{p}})=\begin{pmatrix}Ke^{Kp_{1}}&-Ke^{Kp_{1}}\\\ 0&0\end{pmatrix}$ and
$\|g(\mathbf{p})\|=\sqrt{2}e^{Kp_{1}}$. The only eigenvalue of
$Dg({\bm{p}})|_{\mathcal{T}}$ is $Ke^{Kp_{1}}$. Thus, $Dg({\bm{p}})\succeq
Ke^{Kp_{1}}$. Therefore, by Theorem 3, the optimal report ${\bm{p}}$ satisfies
$\|{\bm{p}}-f({\bm{p}})\|\leq\sqrt{2}L_{f}/K$. Thus, by choosing
$K=L_{f}/(\sqrt{2}\epsilon)$, we obtain the desired bound. If $L_{f}<1$, then
by Theorem 4 we further have that
$\|{\bm{p}}-{\bm{p}}^{*}\|\leq\frac{L_{f}}{(1-L_{f})}\frac{\sqrt{2}}{K}$, so
that we can achieve the desired bound by setting
$K=(1-L_{f})/(\sqrt{2}\epsilon L_{f})$. ∎

###  A.8 Proof of Theorem 6

Throughout this section we use the following simplifying notation. Let $S$ be
a proper scoring rule for the two-outcome case with $G,g$ as per Theorem 1.
Then for a single probability $p\in[0,1]$ we define $G(p)=G(p,1-p)$ and
$g(p)=(1,-1)g(p,1-p)$. And $S(p,q)=S((p,1-p),(q,1-q))$. Then we have that
$S(p,q)=g(p)(q-p)+G(p)$, where $g$ as a function on $[0,1]$ is a subgradient
of $G$ as a function on $[0,1]$. Conversely, note that any function of this
form induces a proper scoring rule on $\Delta(\\{1,2\\})$.

First, we prove a result that reduces the claim about $S$ to a claim about
$g$.

######  Lemma 4.

Let $[p_{1},p_{2}]$ be any interval and $S$ be a proper scoring rule defined
via $g$ as usual. Then

$\frac{\sup_{p\in[p_{1},p_{2}]}S(p,p)-S(p+x,p)}{\inf_{p\in[p_{1},p_{2}]}S(p,p)-S(p+x,p)}\geq\frac{1}{4}\frac{\sup_{p\in[p_{1},p_{2}]}g(p+x)-g(p)}{\inf_{p\in[p_{1},p_{2}]}g(p+x)-g(p)}.$

###### Proof.

For our proof, we will use the following bounds:

$\displaystyle S(p,p)-S(p+x,p)$ $\displaystyle=$ $\displaystyle
xg(p+x)-\int_{p}^{p+x}g(t)dt$ $\displaystyle\geq$ $\displaystyle
xg(p+x)-xg(p+x)/2-xg(p+x/2)/2$ $\displaystyle=$ $\displaystyle
x(g(p+x)-g(p+x/2))/2$ $\displaystyle S(p,p)-S(p+x,p)$ $\displaystyle=$
$\displaystyle xg(p+x)-\int_{p}^{p+x}g(t)dt$ $\displaystyle\leq$
$\displaystyle xg(p+x)-xg(p)$ $\displaystyle=$ $\displaystyle x(g(p+x)-g(p)).$

Using these bounds, we can prove the lemma as follows:

$\displaystyle\frac{\sup_{p}S(p,p)-S(p+x,p)}{\inf_{p}S(p,p)-S(p+x,p)}$
$\displaystyle\geq$
$\displaystyle\frac{\sup_{p}x(g(p+x)-g(p+x/2))/2}{\inf_{p}x(g(p+x)-g(p))}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\frac{\sup_{p}g(p+x)-g(p+x/2)}{\inf_{p}g(p+x)-g(p)}$
$\displaystyle\geq$
$\displaystyle\frac{1}{4}\frac{\sup_{p}g(p+x)-g(p)}{\inf_{p}g(p+x)-g(p)}.$

∎

######  Lemma 5.

Let $y\geq 0$, $h>0$. Let $g\geq 0$ be strictly increasing on $[a,b]$ s.t.
$g(x+h)-g(x)\geq yg(x)$ for all $x\in[a,b]$. Then

$\frac{\sup_{x\in[a,b]}g(x+h)-g(x)}{\inf_{x\in[a,b]}g(x+h)-g(x)}\geq
y(1+y)^{\lfloor(b-a)/h\rfloor-1}.$

###### Proof.

Let $N=\lfloor\frac{b-a}{h}\rfloor$.

Note that $g(x+h)\geq(1+y)g(x)$ for $x\in[a,b]$. Thus, iterating, we get that
$g(a+Nh)\geq(1+y)^{N-1}g(a+h)$.

As a consequence, since $a+Nh\leq b$, we have:

$\displaystyle g(a+(N+1)h)-g(a+Nh)$ $\displaystyle\geq yg(a+Nh)$
$\displaystyle\geq y(1+y)^{N-1}g(a+h)$ $\displaystyle\geq
y(1+y)^{N-1}(g(a+h)-g(a))$

And so:

$\displaystyle\frac{\sup_{x\in[a,b]}g(x+h)-g(x)}{\inf_{x\in[a,b]}g(x+h)-g(x)}\geq\frac{g(a+Nh+h)-g(a+Nh)}{g(a+h)-g(a)}\geq
y(1+y)^{N-1}$

∎

######  Lemma 6.

Let $S$ defined via $g$ as usual be a proper scoring rule. Let
$\epsilon>0,L>0$. Assume that $S$ has the following property: For every $f$
with Lipschitz constant $L$, we have $|p^{*}-f(p^{*})|\leq\epsilon$ for the
optimal report(s) $p^{*}$. Let $\delta=\frac{\epsilon}{L+1}$. Then for every
$2\delta$ interval contained in $[0,1-3\epsilon+2\delta]$, there is a $p$ in
that interval such that ($p+2\delta\leq 1$ and)

$g(p+2\delta)-g(p)\geq\frac{2L}{L+3}g(p).$

(Note that this result doesn’t assume $g>0$. However, note that the consequent
of the lemma is vacuous if $g(p)\leq 0$ (since $g$ is monotone increasing.)

###### Proof.

We shall show, equivalently, that for every interval of width $2\delta$ in
$[2\delta,1-3\epsilon+4\delta]$ , there is some $p$ (in $[0,1]$) contained in
the interval such that:

$g(p)-g(p-2\delta)\geq\frac{2L}{L+3}g(p-2\delta)$ (12)

Given an interval of width $2\delta$ in $[2\delta,1-3\epsilon+4\delta]$ ,
write the interval as $[p_{0}-\delta,p_{0}+\delta]$, where
$p_{0}\in[3\delta,1-3L\delta]=[3\delta,1-3\epsilon+3\delta]\subseteq[0,1]$.

Then, we construct $f$ as follows.

Let

$\displaystyle k_{2}$
$\displaystyle\vcentcolon=p_{0}\left(1+\frac{1}{L}\right)$ (13) $\displaystyle
k_{1}$
$\displaystyle\vcentcolon=k_{2}-\frac{1}{L}=p_{0}-\frac{1}{L}(1-p_{0}).$ (14)

Then consider

$f(p)\vcentcolon=\left\\{\begin{array}[]{cl}1&\text{if }p\leq k_{1}\\\
0&\text{if }p\geq k_{2}\\\ \frac{k_{2}-p}{k_{2}-k_{1}}=L(k_{2}-p)&\text{if
}k_{1}\leq p\leq k_{2}\end{array}\right.$

for $p\in[0,1]$.

For $k_{1}=0.3,k_{2}=0.4,L=10$, this function looks as follows.

Note that $f$ then has Lipschitz constant L.

Moreover, note that $f$ has a unique fixed point, which occurs at
$p_{0}\in(k_{1},k_{2})$, since

$f(p_{0})=L(k_{2}-p_{0})=L\left(p_{0}+\frac{1}{L}p_{0}-p_{0}\right)=p_{0}.$

We can see that for any proper scoring rule, the optimal report under $f$ is
in $[k_{1},k_{2}]\cap[0,1]$.

Next we will show that for $p\in[k_{1},k_{2}]\cap[0,1]$ to satisfy the bound
$|f(p)-p|\leq\epsilon$, we must have that $p\in[p_{0}-\delta,p_{0}+\delta]$.
To show this, observe that, if $p\in[k_{1},k_{2}]\cap[0,1]$:

$\displaystyle f(p)-p$ $\displaystyle=$ $\displaystyle
f(p)-f(p_{0})-(p-p_{0})+f(p_{0})-p_{0}$ $\displaystyle=$
$\displaystyle-L(p-p_{0})-(p-p_{0})+f(p_{0})-p_{0}$ $\displaystyle=$
$\displaystyle-(L+1)(p-p_{0})+f(p_{0})-p_{0}$
$\displaystyle\underset{p_{0}\text{ fixed point}}{=}$
$\displaystyle-(L+1)(p-p_{0}),$

So that, for $k_{1}\leq p\leq k_{2}$ we have $|f(p)-p|\leq\epsilon$ if and
only if $|p-p_{0}|<\delta$. Thus, by assumption, we must have that the optimal
report $p^{*}$ satisfies $p^{*}\in[p_{0}-\delta,p_{0}+\delta].$ We will show
the claim of the theorem by showing that that $p=p^{*}$ satisfies equation
(12).

First, we will check that $p^{*}-2\delta$ is in $[0,1]$, and is still on the
steep section of the graph, i.e., is in $[k_{1},k_{2}]$.

We have

$p^{*}-2\delta\geq
p_{0}-3\delta\underset{\text{\lx@cref{creftypecap~refnum}{eq:def-k1}}}{=}k_{1}+\frac{1}{L}(1-p_{0})-3\delta\underset{p_{0}\leq
1-3L\delta}{\geq}k_{1}.$

Also we chose $p_{0}$ to satisfy $p_{0}-3\delta\geq 0$, so that overall
$p^{*}-2\delta\geq\max(k_{1},0)$. Also, we must have that $\max(k_{1},0)\leq
p^{*}\leq\min(k_{2},1)$.

Now we just use the optimality of $p^{*}$ and the definition of $f$ to get the
result. $S(p^{*},f(p^{*}))\geq S(p^{*}-2\delta,f(p^{*}-2\delta))$, i.e.:

$\displaystyle G(p^{*})+g(p^{*})(f(p^{*})-p^{*})$ $\displaystyle\geq
G(p^{*}-2\delta)+g(p^{*}-2\delta)(f(p^{*}-2\delta)-p^{*}+2\delta)$
$\displaystyle=G(p^{*}-2\delta)+g(p^{*}-2\delta)(f(p^{*})+2L\delta-p^{*}+2\delta)$

Now, by the fact that $g$ is a subgradient of $G$, we have that
$G(p^{*})-G(p^{*}-2\delta)\leq 2\delta g(p^{*})$. Thus, rearranging:

$\displaystyle 2\delta g(p^{*})+g(p^{*})(f(p^{*})-p^{*})\geq
g(p^{*}-2\delta)(f(p^{*})+2L\delta-p^{*}+2\delta)$

and so

$\displaystyle(f(p^{*})-p^{*}+2\delta)(g(p^{*})-g(p^{*}-2\delta))\geq 2\delta
Lg(p^{*}-2\delta).$

Thus, since $|f(p^{*})-p^{*}|\leq\epsilon$

$\displaystyle g(p^{*})-g(p^{*}-2\delta)$ $\displaystyle\geq
g(p^{*}-2\delta)\frac{2L\delta}{\epsilon+2\delta}$
$\displaystyle=\frac{2L}{L+3}g(p^{*}-2\delta).$

∎

######  Lemma 7.

Let $g$ be any monotonically increasing nonnegative function with the property
that on each interval of length $h$ fully contained in $[a,b]$ there is $p$ in
that interval such that $g(p+h)-g(p)\geq yg(p)$. Then for all $p\in[a,b-h]$,
$g(p+2h)-g(p)\geq yg(p)$, provided $g$ is defined on $[a,b+h]$.

###### Proof.

For any $p\in[a,b-h]$, we have that the interval $[p,p+h]$ must contain some
$p^{*}$ with $g(p^{*}+h)-g(p^{*})\geq yg(p^{*})$. Then, since $p\leq p^{*}$,
and $p^{*}+h\leq p+2h$, we have, by monotonicity

$g(p+2h)-g(p)\geq g(p^{*}+h)-g(p^{*})\geq yg(p^{*})\geq yg(p).$

∎

######  Lemma 8.

Let $S(p,q)=g(p)(q-p)+G(p)$ be a (strictly) proper scoring rule, and
$f:[0,1]\rightarrow[0,1]$ be $L_{f}$-Lipschitz. Let

$\displaystyle\tilde{g}(p)$ $\displaystyle\vcentcolon=-g(1-p)$
$\displaystyle\tilde{G}(p)$ $\displaystyle\vcentcolon=G(1-p)$
$\displaystyle\tilde{S}(p,q)$
$\displaystyle\vcentcolon=\tilde{g}(p)(q-p)+\tilde{G}(p)$
$\displaystyle\tilde{f}(p)$ $\displaystyle\vcentcolon=1-f(1-p)$

Then $\tilde{S}$ is a (strictly) proper scoring rule, $\tilde{f}$ is
$L_{f}$-Lipschitz and

$\tilde{S}(1-p,\tilde{f}(1-p))=S(p,f(p)).$

###### Proof.

First, we show that $\tilde{S}$ is a (strictly) proper scoring rule, by
verifying that it conforms to the Gneiting and Raftery characterization. From
the form of $\tilde{G}$, we can see that $\tilde{G}$ is (strictly) convex iff
$G$ is. It remains only to check that $\tilde{g}$ is a subderivative of $g$.
Then, we have

$\tilde{G}(p)-\tilde{G}(q)=G(1-p)-G(1-q)\geq
g(1-q)(1-p-1+q)=\tilde{g}(q)(p-q).$

as required. By inspection, $\tilde{f}$ is $L_{f}$-Lipschitz.

Finally,

$\displaystyle\tilde{S}(1-p,\tilde{f}(1-p))$
$\displaystyle=\tilde{g}(1-p)(\tilde{f}(1-p)-(1-p))+\tilde{G}(1-p)$
$\displaystyle=(-g(p))(1-f(p)-(1-p))+G(p)$ $\displaystyle=g(p)(f(p)-p)+G(p)$
$\displaystyle=S(p,f(p)).$

∎

######  Lemma 9.

Suppose $S$ is a proper scoring rule defined via $g$ s.t. for some
$\epsilon,L_{f}>0$ we have that whenever $f$ is $L_{f}$-Lipschitz, the optimal
report $p^{*}$ satisfies $|f(p^{*})-p^{*}|<\epsilon$. Let
$\delta=\frac{\epsilon}{L_{f}+1}$. Further consider $p_{l},p_{h}$ s.t.
$3\epsilon-3\delta\leq p_{l}\leq p_{h}\leq 1-3\epsilon-\delta$. Then we have:

$\frac{\sup_{x\in[p_{l},p_{h}]}|g(x+4\delta)-g(x)|}{\inf_{x\in[p_{l},p_{h}]}|g(x+4\delta)-g(x)|}\geq\frac{2L_{f}}{L_{f}+3}\left(3\frac{L_{f}+1}{L_{f}+3}\right)^{(L_{f}+1)(p_{h}-p_{l})/(8\epsilon)-5/2}.$

###### Proof.

We will, show, equivalently, that for $3\epsilon-\delta\leq p_{l}\leq
p_{h}\leq 1-3\epsilon+\delta$:

$\frac{\sup_{x\in[p_{l},p_{h}]}|g(x+2\delta)-g(x-2\delta)|}{\inf_{x\in[p_{l},p_{h}]}|g(x+2\delta)-g(x-2\delta)|}\geq\frac{2L_{f}}{L_{f}+3}\left(3\frac{L_{f}+1}{L_{f}+3}\right)^{(L_{f}+1)(p_{h}-p_{l})/(8\epsilon)-5/2}.$
(15)

Consider first the case where $g((p_{l}+p_{h})/2)<0$. Then consider
$\tilde{g}$ as specified by Lemma 8. Note that from Lemma 8 it follows that
$\tilde{S},\tilde{g}$ satisfy the claim of the Theorem in the form of equation
(15) for $[p_{l}^{\prime},p_{h}^{\prime}]\vcentcolon=[1-p_{h},1-p_{l}]$ if and
only if $S,g$ satisfy the claim of the Theorem for $[p_{l},p_{h}]$:

$\displaystyle\frac{\sup_{x\in[p_{l},p_{h}]}|g(x+2\delta)-g(x-2\delta)|}{\inf_{x\in[p_{l},p_{h}]}|g(x+2\delta)-g(x-2\delta)|}$
$\displaystyle=\frac{\sup_{x\in[p_{l},p_{h}]}|\tilde{g}(1-x+2\delta)-\tilde{g}(1-x-2\delta)|}{\inf_{x\in[p_{l},p_{h}]}|\tilde{g}(1-x+2\delta)-\tilde{g}(1-x-2\delta)|}$
$\displaystyle=\frac{\sup_{y\in[1-p_{h},1-p_{l}]}|\tilde{g}(y+2\delta)-\tilde{g}(y-2\delta)|}{\inf_{y\in[1-p_{h},1-p_{l}]}|\tilde{g}(y+2\delta)-\tilde{g}(y-2\delta)|}.$

Note further that $\tilde{g}((p_{l}^{\prime}+p_{h}^{\prime})/2)>0$. Thus, for
our proof we can assume WLOG $g((p_{l}+p_{h})/2)>0$ and thus by monotonicity
$g(x)>0$ for $x>(p_{l}+p_{h})/2$.

Note that $p_{h}\leq 1-3\epsilon+\delta\leq 1-3\epsilon+2\delta$. So, by Lemma
6, we have that in every $2\delta$ interval contained in
$[(p_{l}+p_{h})/2,p_{h}]$ there is a $p$ such that

$g(p+2\delta)-g(p)\geq\frac{2L_{f}}{L_{f}+3}g(p).$

Hence, by Lemma 7, we have that for all $p\in[(p_{l}+p_{h})/2,p_{h}-2\delta]$,

$g(p+4\delta)-g(p)\geq\frac{2L_{f}}{L_{f}+3}g(p)$

since $p_{h}+2\delta\leq 1-3\epsilon+\delta+2\delta\leq 1$. Thus, by Lemma 5,

$\displaystyle\phantom{=}\frac{\sup_{x\in[p_{l},p_{h}]}|g(x+2\delta)-g(x-2\delta)|}{\inf_{x\in[p_{l},p_{h}]}|g(x+2\delta)-g(x-2\delta)|}$
$\displaystyle=\frac{\sup_{x\in[p_{l}-2\delta,p_{h}-2\delta]}|g(x+4\delta)-g(x)|}{\inf_{x\in[p_{l}-2\delta,p_{h}-2\delta]}|g(x+4\delta)-g(x)|}$
$\displaystyle\geq\frac{\sup_{x\in[(p_{l}+p_{h})/2,p_{h}-2\delta]}g(x+4\delta)-g(x)}{\inf_{x\in[(p_{l}+p_{h})/2,p_{h}-2\delta]}g(x+4\delta)-g(x)}\geq\frac{2L_{f}}{L_{f}+3}\left(1+\frac{2L_{f}}{L_{f}+3}\right)^{\lfloor(p_{h}-p_{l})/(8\delta)-1/2\rfloor-1}.$

∎

See 6

###### Proof.

Follows from Lemmas 4 and 9. ∎

###  A.9 Proof of Theorem 7

We’ll first need a lemma that we can find a section of an isoline of
sufficient length that doesn’t turn too much:

######  Lemma 10.

Let $\Delta(\mathcal{N})$ be the probability simplex in $\mathbb{R}^{3}$ (an
equilateral triangle with side length $\sqrt{2}$ lying in a plane embedded in
$\mathbb{R}^{3}$). Let $G:\Delta(\mathcal{N})\rightarrow\mathbb{R}$ be
strictly convex, with subgradient $g$ (with entries summing to 0). Let
$r=\frac{\sqrt{6}}{12}$, and $0<l<r$. Then we can find a section of an isoline
of $G$, $\gamma$, with the following properties:

  1. 1.

$\gamma$ has length $l$.

  2. 2.

Let ${\bm{p}}$ be one endpoint of $\gamma$, and $\bm{n}$ be the unit vector
parallel to $g({\bm{p}})$, i.e.
$\bm{n}=g({\bm{p}})/\left\|g({\bm{p}})\right\|$. Then,
${\bm{p}}-2r\bm{n}\in\Delta(\mathcal{N})$, and $G({\bm{p}}-2r\bm{n})\leq
G({\bm{p}})$.

  3. 3.

For all ${\bm{p}}^{\prime}\in\gamma$, the angle $\theta$ between $g({\bm{p}})$
and $g({\bm{p}}^{\prime})$ satisfies $\theta\leq\frac{2l}{r}$.

  4. 4.

Each point on $\gamma$ has distance at least $r-l$ from the boundary of the
simplex.

Moreover, let $\gamma$ be an isoline section with the above properties. Let
${\bm{p}}$ and $\bm{n}$ be defined as above, and $\bm{t}$ a unit vector
perpendicular to $\bm{n}$ (and to $\bm{1}$). Let $\bm{q}$ be the other
endpoint of $\gamma$. Then $|\bm{t}^{\top}(\bm{q}-{\bm{p}})|\geq
l\left(1-\frac{2l}{r}\right)$. I.e. the length of $\gamma$ in the direction
orthogonal to $\bm{n}$ is at least $l\left(1-\frac{2l}{r}\right)$.

###### Proof.

Note that each isoline $\\{\bm{x}\in\Delta(\mathcal{N}):G(\bm{x})=y\\}$ forms
part of the boundary of the set $\\{\bm{x}\in\Delta(\mathcal{N}):G(\bm{x})\leq
y\\}$, which by strict convexity of $G$ is a convex set. Call this the
enclosed set of the isoline. Then, at each point ${\bm{p}}$ on an isoline,
there is at least one supporting line to the isoline, i.e., a straight line
that touches the isoline but does not contain any of the interior points of
the enclosed set. Moreover, $g({\bm{p}})$ is always perpendicular to a
supporting line to the isoline through ${\bm{p}}$, and points out of the
enclosed set.

We will proceed by finding an isoline tangent to and enclosing a circle at the
center of $\Delta(\mathcal{N})$, and then arguing that a section of this
isoline has the desired properties.

First, consider the circle of radius $r$ at the center of
$\Delta(\mathcal{N})$. Let ${\bm{p}}$ be a point on the boundary of this
circle at which $G$ is maximal, and consider the isoline of $G$ through
${\bm{p}}$.

$O$$r$${\bm{p}}$$g({\bm{p}})$

Observe that, by construction, the enclosed set of this isoline contains the
circle. Moreover, the isoline is tangent to the circle at ${\bm{p}}$. Note
further that the tangent line to the circle at ${\bm{p}}$ must be the unique
supporting line to the isoline through ${\bm{p}}$, so that $g({\bm{p}})$ is
perpendicular to this tangent. As a consequence, we know that if
$\bm{n}=\frac{g({\bm{p}})}{\left\|g({\bm{p}})\right\|}$, then
${\bm{p}}-2r\bm{n}$ is the point on the opposite side of the circle. Thus, we
must have $G({\bm{p}}-2r\bm{n})\leq G({\bm{p}})$, as required.

Now, we have two cases: either the isoline stays within the interior of the
simplex, or it reaches the boundary of the simplex. In the former case, the
total length of the isoline is at least the circumference of the circle, i.e.,
$2\pi r>l$. Thus, we may choose a section (with two distinct endpoints) of the
isoline, $\gamma$, with length $l$ and endpoint ${\bm{p}}$.

Now, note that the distance from the centre of the simplex to the (nearest
point on the) boundary is $\frac{\sqrt{6}}{6}=2r$. Hence, the minimum distance
from the circle to the boundary of the simplex is at least the $2r-r=r>l$.
Thus, in the latter case, the isoline must have a connected section starting
at ${\bm{p}}$ of length $l$. Call this section $\gamma$.

In either case, $\gamma$ has distance at least $r-l$ from the boundary of the
simplex.

Now, we will bound the change in the angle of supporting lines, moving along
$\gamma$. WLOG assume ${\bm{p}}$ is the anticlockwise-most point of $\gamma$.

$O$${\bm{p}}$$\gamma$$\bm{q}$$r$$C$$B$$r$$\theta$$l$$l$$g({\bm{p}})$

Let the center of the circle be $O$. Consider the tangent to the circle at the
point $C$, where $C$ is such that $OC$ is at an angle of $\theta$ from the
line from $O$ to ${\bm{p}}$. Let the intersection of the tangents through $C$
and ${\bm{p}}$ be $B$. Let $\theta$ be such that the line from ${\bm{p}}$ to
$B$ has length $l$. Note that $\theta<\pi/2$, since $l<r$. Let $\bm{q}$ be the
other (clockwise-most) endpoint of $\gamma$.

Note then that since the isoline must lie below the line ${\bm{p}}B$, and the
length of $\gamma$ is $l$, $\gamma$ never crosses the line $BC$.

Meanwhile, consider a point ${\bm{p}}^{\prime}$ on $\gamma$. Note that since
the enclosed set of the isoline contains the circle, no supporting line to the
isoline through ${\bm{p}}^{\prime}$ contains interior points of the circle.
The angle of such a line must then lie between the angles of the tangents at
${\bm{p}}$ and $C$ (ie, is at most as steep as $BC$, on the diagram), and so
makes angle at most $\theta$ with ${\bm{p}}B$. Since $g$ points out of the
enclosed set of the isoline, orthogonal to its supporting lines, the
difference in angle between $g({\bm{p}}^{\prime})$ and $g({\bm{p}})$ is then
at most $\theta$.

Therefore, we have that:

$\frac{\theta}{2}\leq\tan\left(\frac{\theta}{2}\right)=\frac{l}{r}$

since $\tan x\geq x$ for $x\in[0,\pi/2)$. Thus, $\theta\leq\frac{2l}{r}$, as
required. We have now established that $\gamma$ has the stated properties.

We need then only check the final part of the statement, i.e., that $\gamma$
with these properties has sufficient length in the direction orthogonal to
$\bm{n}$. Let $\bm{t}$ be as in the statement of the lemma, i.e., parallel to
the supporting line through ${\bm{p}}$. We have by convexity that $\gamma$
lies within the triangle defined by supporting lines to the isoline at
${\bm{p}}$ and $\bm{q}$ and the straight line from ${\bm{p}}$ to $\bm{q}$.
Hence, since $\theta<\pi/2$, $\gamma$ lies entirely within the triangle
defined by the supporting line at ${\bm{p}}$ parallel to $\bm{t}$, the line
through $\bm{q}$ parallel to $\bm{n}$, and the line from ${\bm{p}}$ to
$\bm{q}$, as depicted in the diagram below.

${\bm{p}}$$\gamma$$\bm{q}$$\bm{n}$$\bm{t}$

Moreover, the maximum possible length of a convex path, within this triangle,
from ${\bm{p}}$ to $\bm{q}$ is just the combined length of the two shorter
sides, i.e.
$|\bm{n}^{\top}({\bm{p}}-\bm{q})|+|\bm{t}^{\top}({\bm{p}}-\bm{q})|$. Thus,
$\left|\bm{t}^{\top}({\bm{p}}-\bm{q})\right|\geq
l-\left|\bm{n}^{\top}({\bm{p}}-\bm{q})\right|$. Then, note that the straight
line from ${\bm{p}}$ to $\bm{q}$ makes angle at most $\theta$ with the line
parallel to $\bm{t}$, since its angle must lie between the angle of supporting
lines at ${\bm{p}}$ and $\bm{q}$.

Thus,

$|\bm{n}^{\top}({\bm{p}}-\bm{q})|\leq\sin\theta\left\|{\bm{p}}-\bm{q}\right\|\leq
l\sin\theta\leq l\theta.$

Hence, we have

$|\bm{t}^{\top}({\bm{p}}-\bm{q})|\geq l-l\theta=l\left(1-\frac{2l}{r}\right)$

and we are done. ∎

Now, our main result: We can’t get arbitrarily good bounds for fixed Lipschitz
constant, and the bound one can at best get scales linearly with $L_{f}$ in
the limit $L_{f}\rightarrow 0$.

See 7

###### Proof.

Let $g$ and $G$ be as in the Gneiting and Raftery characterization of $S$. Let
$\lambda=\min(L_{f},2)$.

We will proceed as follows:

  * •

Find an isoline of $G$ on which the angle of $g({\bm{p}})$ doesn’t change
much. On this isoline, we are then able to move along the isoline without
$g({\bm{p}})$ changing much in the direction of movement, and hence without
$g({\bm{p}})^{\top}{\bm{p}}$ changing much.

  * •

Construct a $\lambda$-Lipschitz (and hence $L_{f}$-Lipschitz) function $f$
with fixed point ${\bm{p}}_{0}$ such that as we move sideways along the
isoline, $f({\bm{p}})$ moves upwards, incentivising us to misrepresent in the
direction of the isoline.

  * •

We will then show that for a point $\bm{q}$, with
$\left\|f(\bm{q})-\bm{q}\right\|\geq\epsilon$, reporting $\bm{q}$ gives higher
score than any point ${\bm{p}}$ for which
$\left\|f({\bm{p}})-{\bm{p}}\right\|<\epsilon$ (for $\epsilon$ which we will
choose).

Let $\theta=\arctan(\lambda/4)\leq\lambda/4\leq 1/2$. Note that then
$\theta\sim L_{f}/4$ as $L_{f}\rightarrow 0$.

Let $r=\frac{\sqrt{6}}{12}$. Then, let $\gamma$ be an isoline satisfying the
properties of Lemma 10 with $l=\frac{\theta r}{2}$. Let the end points of
$\gamma$ be ${\bm{p}}_{1}$ and $\bm{q}$ (chosen such that $\bm{q}$ is the same
end as $\bm{q}$ in the statement of the Lemma),
$\bm{n}\vcentcolon=\frac{g({\bm{p}}_{1})}{\left\|g({\bm{p}}_{1})\right\|}$,
and $\bm{t}$ a unit vector orthogonal to both $\bm{n}$ and $\bm{1}$. Then we
have, in particular:

  1. (P1)

${\bm{p}}_{1}-2r\bm{n}\in\Delta(\mathcal{N})$ and
$G({\bm{p}}_{1}-2r\bm{n})\leq G({\bm{p}}_{1})$.

  2. (P2)

For all ${\bm{p}}\in\gamma$, the angle between $g({\bm{p}})$ and
$g({\bm{p}}_{1})$ (equivalently, $\bm{n}$) is at most $\frac{2l}{r}=\theta$.

  3. (P3)

Each point on $\gamma$ has distance at least $r-l\geq 3l$ from the boundary of
the simplex.

  4. (P4)

$|t^{\top}(\bm{q}-{\bm{p}}_{1})|\geq l(1-\frac{2l}{r})=l(1-\theta)$.

Let $\epsilon=\frac{1}{2}|t^{\top}(\bm{q}-{\bm{p}}_{1})|$. We have, by (P4),
$\epsilon\geq l(1-\theta)/2\geq l/4>0$. Note that
$l(1-\theta)/2\leq\epsilon\leq l/2$, and $l\theta=o(L_{f})$, and so
$\epsilon\sim\frac{1}{2}l=\frac{1}{4}\theta
r\sim\frac{1}{16}L_{f}r=\frac{\sqrt{6}}{192}L_{f}$ as $L_{f}\rightarrow 0$.

Let ${\bm{p}}_{0}={\bm{p}}_{1}-\epsilon\lambda\bm{n}$. Note that since
$\epsilon\lambda\leq 2\epsilon\leq l$, we have by (P3) that ${\bm{p}}_{0}$ is
within the simplex.

${\bm{p}}_{1}$$\bm{q}$${\bm{p}}_{0}+2\epsilon\bm{t}$${\bm{p}}_{0}$2$\epsilon$$\bm{n}$$\bm{t}$$g(\bm{q})$$g({\bm{p}}_{1})$

By construction, there is a supporting line to $\gamma$, parallel to $\bm{t}$,
through ${\bm{p}}_{1}$. Thus, $(\bm{q}-{\bm{p}}_{1})^{\top}\bm{n}\leq 0$.

Now, let
$f({\bm{p}})={\bm{p}}_{0}+\lambda\min(|\bm{t}^{\top}({\bm{p}}-{\bm{p}}_{0})|,2\epsilon)\bm{n}$.
Note that the image of $f$ is the line segment
$[{\bm{p}}_{0},{\bm{p}}_{0}+2\epsilon\lambda\bm{n}]$, which has maximum
distance $\lambda\epsilon\leq l$ from $\gamma$, and hence by (P3) is entirely
within the probability simplex. Also, $f$ has Lipschitz constant $\lambda\leq
L_{f}$.

Then, if $\left\|f({\bm{p}})-{\bm{p}}\right\|\leq\epsilon$, we must have

$\epsilon\geq|\bm{t}^{\top}(f({\bm{p}})-{\bm{p}})|=|\bm{t}^{\top}({\bm{p}}_{0}-{\bm{p}})|$

and hence $f({\bm{p}})$ must in fact lie in the line segment
$[{\bm{p}}_{0},{\bm{p}}_{0}+\epsilon\lambda\bm{n}]=[{\bm{p}}_{0},{\bm{p}}_{1}]$.
Moreover, $\left\|f(\bm{q})-q\right\|\geq 2\epsilon>\epsilon$.

Meanwhile, we have by convexity and (P1) that for
${\bm{p}}\in[{\bm{p}}_{1}-2r\bm{n},{\bm{p}}_{1}]$,
$G({\bm{p}})\leq\max(G({\bm{p}}_{1}-2r\bm{n}),G({\bm{p}}_{1}))=G({\bm{p}}_{1})$.
Hence, since $\lambda\epsilon<2r$, the maximum of $G$ on
$[{\bm{p}}_{0},{\bm{p}}_{1}]$ is $G({\bm{p}}_{1})$.

Therefore, whenever $\left\|f({\bm{p}})-{\bm{p}}\right\|\leq\epsilon$:

$S({\bm{p}},f({\bm{p}}))\leq S(f({\bm{p}}),f({\bm{p}}))=G(f({\bm{p}}))\leq
G({\bm{p}}_{1})$

that is, the maximum achievable score is at most the score of honestly
reporting ${\bm{p}}_{1}$.

We will now show that the score of reporting $\bm{q}$ is greater than
$G({\bm{p}}_{1})$.

First, we have that

$\displaystyle S(\bm{q},f(\bm{q}))$
$\displaystyle=g(\bm{q})^{\top}(f(\bm{q})-\bm{q})+G(\bm{q})$ (Gn&Raf)
$\displaystyle=g(\bm{q})^{\top}({\bm{p}}_{0}+2\epsilon\lambda\bm{n}-\bm{q})+G({\bm{p}}_{1})$
$\displaystyle\text{(Def. of }f,\bm{q})$

It is left to show that the left summand is positive. We have that

$\displaystyle g(\bm{q})^{\top}({\bm{p}}_{0}+2\epsilon\lambda\bm{n}-\bm{q})$
$\displaystyle=(2\epsilon\lambda+({\bm{p}}_{0}-\bm{q})^{\top}\bm{n})g(\bm{q})^{\top}\bm{n}+(({\bm{p}}_{0}-\bm{q})^{\top}\bm{t})g(\bm{q})^{\top}\bm{t}$
$\displaystyle\geq\epsilon\lambda
g(\bm{q})^{\top}\bm{n}-2\epsilon|g(\bm{q})^{\top}\bm{t}|$
$\displaystyle\text{(Def. of }\bm{q},{\bm{p}}_{0})$
$\displaystyle\geq\left\|g(\bm{q})\right\|\epsilon(\lambda\cos\theta-2\sin\theta)$
$\displaystyle\text{(By \ref{p:small_angle}})$
$\displaystyle=2\left\|g(\bm{q})\right\|\epsilon\cos(\theta)(\lambda/2-\tan\theta)$
$\displaystyle\geq\left\|g(\bm{q})\right\|\epsilon\cos(\theta)\lambda/2>0$
$\displaystyle\text{(Choice of }\theta)$

∎

##  Appendix B Preferences between different fixed points

######  Proposition 4.

Let $F=\\{{\bm{p}}\colon f({\bm{p}})={\bm{p}}\\}$ be a set of fixed points of
$f$. Let ${\bm{p}}\in F$ such that ${\bm{p}}$ is the convex combination of
elements of $F-\\{{\bm{p}}\\}$. (In other words, ${\bm{p}}$ is in the interior
of the convex hull of $F$). Then if $S$ is strictly proper, there exists a
${\bm{p}}^{*}\in F$ s.t. $S(p^{*},f(p^{*}))>S(p,f(p))$. Thus,
$\operatorname*{arg\,max}_{p\in F}S(p,f(p))$ is a subset of the extreme points
of $F$.

This follows directly from the convexity of the expected score under honest
reporting as per Theorem 1, but for completeness we provide a detailed proof.

###### Proof.

Let ${\bm{p}}=\sum_{i=1}^{k}c_{i}{\bm{p}}_{i}$ for $c_{i}\in[0,1]$ with
$\sum_{i=1}^{k}c_{i}=1$ and ${\bm{p}}_{i}\in F-{{\bm{p}}}$. Then

$\displaystyle S({\bm{p}},f({\bm{p}}))$ $\displaystyle=$ $\displaystyle
g({\bm{p}})(f({\bm{p}})-{\bm{p}})+G({\bm{p}})$
$\displaystyle\underset{\text{${\bm{p}}$ fixed point}}{=}$ $\displaystyle
G({\bm{p}})$ $\displaystyle=$ $\displaystyle
G\left(\sum_{i=1}^{k}c_{i}{\bm{p}}_{i}\right)$ $\displaystyle\underset{\text{G
strictly convex}}{<}$ $\displaystyle\sum_{i=1}^{k}c_{i}G({\bm{p}}_{i})$
$\displaystyle\underset{\text{${\bm{p}}_{i}$ fixed point}}{=}$
$\displaystyle\sum_{i=1}^{k}c_{i}(g({\bm{p}}_{i})(f({\bm{p}}_{i})-{\bm{p}}_{i})+G({\bm{p}}_{i}))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k}c_{i}S({\bm{p}}_{i},f({\bm{p}}_{i})).$

Now for the average of the $S({\bm{p}}_{i},f({\bm{p}}_{i}))$ to be greater
than $S({\bm{p}},f({\bm{p}}))$, at least one of the
$S({\bm{p}}_{i},f({\bm{p}}_{i}))$ must be greater than
$S({\bm{p}},f({\bm{p}}))$. ∎

##  Appendix C Additional experimental results

###  C.1 Two outcomes

Figure 6: Maximal inaccuracy and maximal distance to fixed point (FP) of
optimal predictions, depending on the slope of $f$, according to our
simulation and our theoretical bound. Figure 7: Heatmap of the L2 inaccuracy
of optimal predictions, depending on fixed point position and slope of $f$,
for the logarithmic scoring rule. Figure 8: Heatmap of the L2 distance to the
fixed point of optimal predictions, depending on fixed point position and
slope of $f$, for the logarithmic scoring rule.

Figures 6, 8 and 7 give the same graphs that we give for the Brier scoring
rule in the main text.

Here the bounds for the log scoring rule are obtained as follows. First, note
that for the log scoring rule we have that $g(p)=(\log
p_{i}-\nicefrac{{1}}{{2}}(\log p_{1}+\log p_{2}))_{i}$. So,
$\|g({\bm{p}})\|=\frac{|\log(p_{1})-\log(p_{2})|}{\sqrt{2}}$ and
$Dg(p)=\begin{pmatrix}\frac{1}{2p_{1}}&-\frac{1}{2p_{2}}\\\
-\frac{1}{2p_{1}}&\frac{1}{2p_{2}}\\\ \end{pmatrix}.$ The eigenvalue of this
on the tangent space is $1/(2p_{1}p_{2})$. Thus, since $Dg$ is symmetric,
$DG({\bm{p}})\succeq 1/(2p_{1}p_{2})$. By Theorem 3,
$\|{\bm{p}}-f({\bm{p}})\|\leq
L_{f}\|g(p)\|2p_{1}p_{2}=\sqrt{2}L_{f}p_{1}p_{2}|\log(p_{1})-\log(p_{2})|$.
Numerically this bound seems to be maximized at $p=0.824$ so that we get a
bound $\|{\bm{p}}-f({\bm{p}})\|\leq 0.316L_{f}$. Similarly, by Theorem 4,
$\|{\bm{p}}-{\bm{p}}^{*}\|\leq 0.316L_{f}/(1-L_{f})$.

For the logarithmic scoring rule, we also give the same plot for the absolute
distance between the logits or log odds of the two probabilities (logit
distance), see Figure 9. It is defined as
$d({\bm{p}},{\bm{p}}^{\prime}):=|\sigma^{-1}({\bm{p}})-\sigma^{-1}({\bm{p}}^{\prime})|$,
where $\sigma^{-1}({\bm{p}}):=\log\frac{p_{1}}{p_{2}}$ is the logit of
${\bm{p}}$ (or the inverse sigmoid transform). If probabilities are close to
$0$ or $1$, then L2 distance will always evaluate to very small distances. In
contrast, the logit distance depends on order of magnitude differences between
probabilities, which may be the more useful quantity.

Figure 9: Heatmap of logit distance inaccuracy of optimal predictions for the
log scoring rule.

We can see that inaccuracy remains high in logit space for fixed points close
to $0$ and $1$. We don’t plot logit distances for the quadratic score, since
for that score, optimal predictions often take values close to or equal to
$\\{(0,1),(1,0)\\}$ (even if neither $f({\bm{p}})$ nor ${\bm{p}}^{*}$ lie in
$\\{(0,1),(1,0)\\}$), so the corresponding distances become very large or
infinite. The fact that logit distances are bounded for the log score is an
advantage of that scoring rule.

###  C.2 Many outcomes

####  C.2.1 Inaccuracy and ditance to fixed point are strongly correlated

Throughout this paper we consider two measures of how wrong a prediction a
prediction is, the inaccuracy, i.e., distance of the performatively optimal
report ${\bm{p}}$ to $f({\bm{p}})$, and the distance of the performatively
optimal report to the fixed point. Our experiments show that these measures
are closely but not perfectly correlated, see Figure 10. The correlation is
$0.958$.

Figure 10: Scatter plot showing the L2 inaccuracy of the performatively
optimal report against the L2 distance of the performatively optimal report to
the fixed point report.

####  C.2.2 The effect of fixed point location

Figure 11 scatter-plots the distance to fixed points against the distance of
the fixed points from the uniform distribution. The blue line is the best
linear fit, which is $0.0274+0.751x$. Similarly Figure 12 scatter-plots the
inaccuracy of the performatively optimal report against the distance of the
fixed point report to the uniform distribution. The blue line is again given
by the best linear fit, which is $0.0231+0.468x$.

The overall effect of the distance of ${\bm{p}}^{*}$ from uniform actually
seems larger than the effect of the operator norm, as indicated by the
correlation coefficients in Table 1.

Figure 11: Scatter plot showing the L2 distance of the performatively optimal report to the fixed point report against distance of the fixed point to the uniform distribution in our experiments. The blue line is found by linear regression on the points. Figure 12: Scatter plot showing the L2 inaccuracy of the performatively optimal report against the distance of the fixed point of $f$ to the uniform distribution in our experiments. The blue line is found by linear regression on the points. | $\|{\bm{p}}-{\bm{p}}^{*}\|$ | $\|{\bm{p}}-f({\bm{p}})\|$
---|---|---
$\|f_{A}\|_{\mathrm{op}}$ | 0.294 | 0.311
$\|p^{*}-\frac{1}{n}\mathbf{1}\|$ | 0.331 | 0.411
Table 1: Each entry shows the empirical correlation between the quantities
determined by the row and column.

##  Appendix D Fixed points via alternative notions of optimality

In this section, we will review alternatives to performance optimality under
which fixed points are incentivized. We will elaborate on the settings
introduced in Section 8 and provide formal statements and proofs.

To motivate the following, consider an expert AI that chooses its prediction
to match its world model, but without explicitly considering the effect of its
prediction. For instance, such cognition could arise in an AI trained via a
purely supervised objective on historical data. This AI may not learn to take
into account effects of its predictions on the outcome of the prediction. If
it nevertheless has a world model that generalizes correctly to performative
predictions, this could put the AI in a game in which it is trying to make a
prediction to match its world model, while the world model updates its beliefs
conditional on the AI’s prediction. The only equilibria of this game would be
fixed points.

Alternatively, fixed points could also result from different training schemes
that explicitly optimize an AI’s prediction to track empirical outcomes,
without also incentivizing influencing the outcomes themselves, such as
repeated risk minimization or repeated gradient descent [Perdomo et al.,
2020].

Such expert AIs would likely be safer than ones optimizing for performative
optimality. First, they report their true beliefs, which gives us better
information to base decisions on. This also enables approaches in which we
ensure that there is only one safe fixed point. Second, they do not explicitly
optimize the choice of fixed point for a goal such as decreasing entropy.
Instead, which fixed point is chosen will be contingent on initialization and
specifics of the fixed point finding procedure.

###  D.1 Performative stability and game theory

We begin by defining performative stability and relating it to an equilibrium
in a two-player game. This represents the core idea behind all of the
following settings. A prediction ${\bm{p}}^{*}$ is called _performatively
stable_ [Perdomo et al., 2020] if

${\bm{p}}^{*}\in\operatorname*{arg\,max}_{{\bm{p}}}S({\bm{p}},f({\bm{p}}^{*})).$
(16)

First, it is clear that in our case, this is equivalent to ${\bm{p}}^{*}$
being a fixed point.

######  Proposition 5.

Assume $S$ is strictly proper. Then a prediction ${\bm{p}}^{*}$ is a fixed
point if and only if it is performatively stable.

###### Proof.

“$\Rightarrow$”. Assume $f({\bm{p}}^{*})={\bm{p}}^{*}$. Then
$S({\bm{p}}^{*},f({\bm{p}}*))=S({\bm{p}}^{*},{\bm{p}}^{*})\geq
S({\bm{p}},{\bm{p}}^{*})=S({\bm{p}},f({\bm{p}}^{*}))$ for any ${\bm{p}}$ since
$S$ is proper. Hence,
${\bm{p}}^{*}\in\operatorname*{arg\,max}_{{\bm{p}}}S({\bm{p}},f({\bm{p}}^{*})).$

“$\Leftarrow$”. Assume
${\bm{p}}^{*}\in\operatorname*{arg\,max}_{{\bm{p}}}S({\bm{p}},f({\bm{p}}^{*}))$.
Then since $S$ is strictly proper, it must be ${\bm{p}}^{*}=f({\bm{p}}^{*})$.
∎

Next, the above objective is equivalent to the definition of a Nash
equilibrium in the following game.

######  Definition 2 (Oracle game).

Consider a two-player continuous game in which the first player controls
${\bm{p}}\in\Delta(\mathcal{N})$ and the second player controls
$\bm{q}\in\Delta(\mathcal{N})$, with payoff functions
$U_{1}({\bm{p}},\bm{q}):=S({\bm{p}},\bm{q})$ and
$U_{2}({\bm{p}},\bm{q}):=S(\bm{q},f({\bm{p}}))$ for the two players,
respectively.

If ${\bm{p}}^{*},\bm{q}^{*}$ is a Nash equilibrium of the oracle game, we have
$p^{*}=\operatorname*{arg\,max}_{\bm{p}}S({\bm{p}},\bm{q})$ and
$\bm{q}^{*}=\operatorname*{arg\,max}_{\bm{q}}S(\bm{q},f({\bm{p}}^{*}))$.
Substituting the optimal value $\bm{q}^{*}=f({\bm{p}}^{*})$ for the second
player gives us exactly above definition of performative stability in Equation
16. Conversely, if a prediction ${\bm{p}}^{*}$ is performatively stable, then
setting $\bm{q}^{*}:=f({\bm{p}}^{*})$ yields a Nash equilibrium.

######  Proposition 6.

Assume $S$ is a proper scoring rule. Then ${\bm{p}}\in\Delta(\mathcal{N})$,
$\bm{q}:=f({\bm{p}})$ is a Nash equilibrium of the oracle game, if and only if
${\bm{p}}$ is performatively stable. By Proposition 5, this is equivalent to
${\bm{p}}$ being a fixed point.

The oracle game could arise in an agent that uses a causal decision theory
[Weirich, 2020] to maximize its score and that believes that $S$ is influenced
causally by ${\bm{p}}$, but only acausally by $f({\bm{p}})$. In that case, the
only _ratifiable_ [Jeffrey, 1990, Bell et al., 2021, Ch. 1.7] decision is a
Nash equilibrium of the above game. Similarly, the deliberational causal
epistemic decision theory discussed by Greaves [2013] would output Nash
equilibria of this game (whereas performative optimality would correspond to
an agent using evidential epistemic decision theory in this case).

Note that it is important that both players act simultaneously. Perdomo et al.
[2020] introduce a Stackelberg version of the oracle game that produces
performatively optimal instead of performatively stable reports. Consider a
game in which player $1$ acts first and chooses ${\bm{p}}$, after which player
$2$ responds with a prediction $\bm{q}$. Then player $2$ responds
$\bm{q}=f({\bm{p}})$ to player $1$’s action, and player $1$’s optimization
problem becomes

$p^{*}=\operatorname*{arg\,max}_{{\bm{p}}}S({\bm{p}},\operatorname*{arg\,max}_{\bm{q}}S(\bm{q},f({\bm{p}})))=\operatorname*{arg\,max}_{\bm{p}}S({\bm{p}},f({\bm{p}})).$

###  D.2 Repeated risk minimization and repeated gradient descent

Above, we have defined performative stability and a related game which yield
fixed points, but we have not defined methods for solving these problems. In
the performative prediction context, Perdomo et al. [2020] introduce _repeated
risk minimization_ and _repeated gradient descent_ , both methods that
converge to performatively stable points. In this section, we review both
schemes and show how repeated gradient descent can be seen as gradient descent
on a _stop-gradient_ [Foerster et al., 2018, Demski, 2019] objective.

We assume direct access to $\bm{q}$, instead of having only access to samples
distributed according to $\bm{q}$. In the next section, we discuss online
learning when we only have access to samples. One way to understand this
distinction is that the former corresponds to the internal cognition of an
agent with a belief $\bm{q}=f({\bm{p}})$ optimizing a prediction ${\bm{p}}$.
The latter instead corresponds to a machine learning training setup for an
oracle AI, where $\bm{q}$ is the ground truth environment distribution instead
of the oracle’s belief. Of course, there is no strict divide between the two.
Any optimization algorithm could be used either by the agent itself or to
train the agent.

First, _repeated risk minimization_ is a procedure by which we start with a
prediction ${\bm{p}}_{0}$ and then iteratively update the prediction as
${\bm{p}}_{t+1}=\operatorname*{arg\,max}_{{\bm{p}}}S({\bm{p}},f({\bm{p}}_{t}))$.
This is also the same as alternating best response learning in the oracle
game, where player $1$ iteratively updates their prediction, responding to
predictions $\bm{q}_{t}=f({\bm{p}}_{t})$ from player $2$. If $S$ is strictly
proper, ${\bm{p}}_{t+1}=f({\bm{p}}_{t})$, and this results in _fixed point
iteration_ for $f$. Fixed point iteration converges globally to a fixed point
if $f$ has Lipschitz constant $L_{f}<1$. It also converges locally to a fixed
point ${\bm{p}}^{*}$ if $f$ is continuously differentiable at ${\bm{p}}^{*}$
and $\rho(Df({\bm{p}}^{*}))<1$, where $\rho(Df({\bm{p}}^{*}))$ is the spectral
radius of the Jacobian matrix $Df({\bm{p}}^{*})$.

Second, assume that $S$ is differentiable. Then _repeated gradient ascent_
updates points via

${\bm{p}}_{t+1}:=\Pi_{\Delta}({\bm{p}}_{t}+\alpha\mathbb{E}_{y\sim
f({\bm{p}}_{t})}[\nabla_{\bm{p}}S({\bm{p}}_{t},y)]),$

where $\Pi_{\Delta}$ is the Euclidean projection onto the probability simplex
$\Delta(\mathcal{N})$, and $\alpha>0$ is the learning rate.

Using the definition of $S({\bm{p}},\bm{q})$, we have

$\mathbb{E}_{y\sim
f({\bm{p}}_{t})}[\nabla_{\bm{p}}S({\bm{p}}_{t},y)]=\nabla_{\bm{p}}(\mathbb{E}_{y\sim\bm{q}}[S({\bm{p}}_{t},y)])|_{\bm{q}=f({\bm{p}}_{t})}=\nabla_{\bm{p}}(S({\bm{p}}_{t},\bm{q}))|_{\bm{q}=f({\bm{p}})}$

We can express this as

$\nabla_{\bm{p}}(S({\bm{p}}_{t},\bot
f({\bm{p}}_{t}))):=\nabla_{\bm{p}}(S({\bm{p}}_{t},\bm{q}))|_{\bm{q}=f({\bm{p}})},$

where $\bot$ is the _stop-gradient operator_ , which evaluates to the identity
function but sets gradients to zero, $\nabla_{x}(\bot x)=0$ [Foerster et al.,
2018, Demski, 2019].444This is not a mathematical function (there is no
function that is equal to the identity but has gradient zero everywhere), but
rather a notational convention in reference to the stop_gradient or detach
functions from the tensorflow or pytorch python libraries. Interestingly, one
can perform valid derivations using the stop-gradient operator (e.g., using
the chain rule). We leave it to future work to explore the mathematics behind
stop-gradients further. In the following, we call $S({\bm{p}},\bot
f({\bm{p}}))$ the _stop-gradient objective_.

Importantly, it matters that the gradient in repeated gradient ascent lies
inside instead of outside the expectation:

$\mathbb{E}_{y\sim
f({\bm{p}}_{t})}[\nabla_{\bm{p}}S({\bm{p}}_{t},y)]=\nabla_{\bm{p}}(S({\bm{p}}_{t},\bot
f({\bm{p}}_{t})))\neq\nabla_{p}(S({\bm{p}}_{t},f({\bm{p}}_{t})))=\nabla_{\bm{p}}\mathbb{E}_{y\sim
f({\bm{p}}_{t})}[S({\bm{p}}_{t},y)]).$

Unlike repeated gradient ascent, the latter implements gradient ascent on
$S({\bm{p}},f({\bm{p}}))$ and thus leads to performatively optimal reports.

Perdomo et al. [2020] show that, given their assumptions, repeated gradient
descent globally converges to stable fixed points. They also provide
convergence rates. We will show an analogous result relating repeated gradient
ascent to fixed points in our setting, though we won’t analyze global
convergence or rates of convergence.

To begin, we show that repeated gradient descent is equivalent to Naive
Learning [Letcher et al., 2019] in the oracle game, assuming that player $2$
always plays $\bm{q}=f({\bm{p}})$.

######  Proposition 7.

Assume player $1$ is performing gradient ascent on its objective with learning
rate $\alpha$, under the assumption that player $2$ always plays
$\bm{q}=f({\bm{p}})$. Then player $1$’s update is

${\bm{p}}_{t+1}=\Pi_{\Delta}({\bm{p}}_{t}+\alpha\nabla_{\bm{p}}(\mathbf{S}({\bm{p}}_{t},\bot
f({\bm{p}}_{t})))).$

###### Proof.

The proof follows immediately from the definitions. Player $1$’s update is, by
assumption,

${\bm{p}}_{t+1}=\Pi_{\Delta}({\bm{p}}_{t}+\alpha\nabla_{\bm{p}}(U_{1}({\bm{p}}_{t},\bm{q})))=\Pi_{\Delta}({\bm{p}}_{t}+\alpha\nabla_{\bm{p}}(S({\bm{p}}_{t},\bm{q})))$

where $\bm{q}$ is player $2$’s action. Assuming player $2$ plays
$\bm{q}=f({\bm{p}}_{t})$, we get

${\bm{p}}_{t+1}=\Pi_{\Delta}({\bm{p}}_{t}+\alpha\nabla_{\bm{p}}(S({\bm{p}}_{t},\bm{q})))=\Pi_{\Delta}({\bm{p}}_{t}+\alpha\nabla_{p}(S({\bm{p}}_{t},\bot
f({\bm{p}}_{t}))))$

∎

Next, we show that fixed points are critical points of the stop-gradient
objective.

######  Proposition 8.

Assume $S$ is proper and let $G,g$ as in the Gneiting and Raftery
characterization of $S$ (Theorem 1) be differentiable. Then for any
${\bm{p}}\in\Delta(\mathcal{N})$, we have

$\nabla_{\bm{p}}(S({\bm{p}},\bot
f({\bm{p}})))=Dg({\bm{p}})^{\top}(f({\bm{p}})-{\bm{p}}).$

In particular, if ${\bm{p}}$ is a fixed point, it follows that
$\nabla_{\bm{p}}(S({\bm{p}},\bot f({\bm{p}})))=0$. The reverse is true if
$Dg({\bm{p}})|_{\mathcal{T}}\succ 0$.

###### Proof.

$\nabla_{\bm{p}}(S({\bm{p}},\bot
f({\bm{p}})))=\nabla_{\bm{p}}(S({\bm{p}},\bm{q}))|_{\bm{q}=f({\bm{p}})}=\nabla_{\bm{p}}(G({\bm{p}})+g({\bm{p}})^{\top}(\bm{q}-{\bm{p}}))|_{\bm{q}=f({\bm{p}})}\\\
=(g({\bm{p}})+Dg({\bm{p}})^{\top}(\bm{q}-{\bm{p}})-g({\bm{p}}))|_{\bm{q}=f({\bm{p}})}=Dg({\bm{p}})^{\top}(f({\bm{p}})-{\bm{p}}).$
(17)

If ${\bm{p}}$ is a fixed point, it follows that
$\nabla_{\bm{p}}(S({\bm{p}},\bot f({\bm{p}})))=0$. Moreover, if
$Dg({\bm{p}})|_{\mathcal{T}}\succ 0$, then if $f({\bm{p}})-{\bm{p}}\neq 0,$

$\nabla_{\bm{p}}(S({\bm{p}},\bot