AppxReferences

# Loss Functions for Behavioral Game Theory

Greg d’Eon
University of British Columbia
<EMAIL_ADDRESS>
&Sophie Greenwood
University of British Columbia
<EMAIL_ADDRESS>
&Kevin Leyton-Brown
University of British Columbia
<EMAIL_ADDRESS>
&James R. Wright
University of Alberta
<EMAIL_ADDRESS>

###### Abstract

Behavioral game theorists all use experimental data to evaluate predictive
models of human behavior. However, they differ greatly in their choice of loss
function for these evaluations, with error rate, negative log-likelihood,
cross-entropy, Brier score, and L2 error all being common choices. We attempt
to offer a principled answer to the question of which loss functions make
sense for this task, formalizing desiderata that we argue loss functions
should satisfy. We construct a family of loss functions, which we dub
“diagonal bounded Bregman divergences”, that satisfy all of these axioms and
includes the squared L2 error. In fact, the squared L2 error is the only
acceptable loss that is relatively commonly used in practice; we thus
recommend its continued use to behavioral game theorists.

##  1 Introduction

Classical economic models often fail to describe human behavior: e.g., people
often choose dominated actions (Goeree and Holt, 2001), reason incorrectly
about probabilities close to 0 or 1 (Kahneman and Tversky, 2013), and fail to
account for others’ strategic decision making (Kneeland, 2015). In response to
such failures, behavioral economics aims to learn predictive models of human
behavior, fitting models to datasets describing actual human responses to
strategic situations. Such models offer cognitive scientists tools for
learning about how humans think, especially when confronted with economic or
strategic choices, and can help the designers of economic systems to tune
their designs to perform well in the face of realistic behavior.

However, evaluating the quality of such a model on a dataset requires a loss
function.111So does fitting the parameters of such a model from data. However,
directly minimizing the test loss on a training set can cause a model to
overfit, leading it to generalize poorly. To avoid overfitting, it is typical
instead to minimize some _different_ loss function on the training set—for
example, replacing the loss with a smooth or convex proxy, or regularizing to
prefer simpler models (Murphy, 2012). We set these issues aside in what
follows, focusing on the appropriate loss for practitioners to aim to minimize
on unseen test data. Researchers working in behavioral game theory have made a
wide variety of different choices about precisely which loss function to use
for such evaluations, with error rate, negative log-likelihood, cross-entropy,
and (at least two notions of) mean-squared error all being common choices.
Clearly, the choice of loss function is a substantive one: different losses
will disagree about the quality of a prediction. This leads us to ask: which
loss function(s) should behavioural game theorists use?

In this paper, we attempt to answer this question with a first-principles
argument, arguing that loss functions should satisfy five key axioms. The
first two, which we call alignment axioms, ensure that the loss function
induces a correct preference ordering among behavioral predictions. These
axioms, sample Pareto-alignment and distributional Pareto-alignment, ensure
that the loss function always penalizes predictions that are clearly worse (on
a given dataset or in expectation under draws from a generating distribution,
respectively). Our remaining three axioms impose properties on our loss
functions that make them more interpretable, better relating the quality of a
prediction to the numerical value of the loss. Exchangeability requires that
the loss be invariant to the order in which observations are made;
counterfactual Pareto-regularity ensures that the loss appropriately respects
changes in the data, and zero minimum gives the loss an interpretable optimum
by ensuring that a perfect prediction receives a loss of 0.

We show that it is possible to satisfy all of these axioms: in fact, we
identify an entire family of loss functions that do so, which we dub “diagonal
bounded Bregman divergences”. Exactly one widely used loss function belongs to
this set, the squared L2 error between the predicted and empirical
distributions; we show how each of the other commonly used loss functions
violates at least one axiom. In particular, the entire class of scoring
rules,222The term “scoring rule” is overloaded in the literature. Some authors
(e.g., Abernethy and Frongillo, 2012) use it to refer to any arbitrary loss
function. In this work, we use the more restrictive definition that a scoring
rule computes a loss for each individual observation, then aggregates these
losses by taking a mean (Section 2.1); this definition is also standard (e.g.,
Savage, 1971; Gneiting and Raftery, 2007). a class of popular loss functions
with celebrated alignment properties, all fail our interpretability axioms.
(However, every diagonal bounded Bregman divergence is equivalent to some
scoring rule, up to an additive translation. This means that some scoring
rules can safely be used as objective functions in training if their numerical
values do not need to be interpreted, and conversely that each scoring rule
can be translated into a more interpretable diagonal bounded Bregman
divergence inducing the same preferences over predictions.) In the end, since
our work gives no reason to prefer one diagonal bounded Bregman divergence
over another, we recommend that behavioral game theory researchers use squared
L2 error to evaluate models.

###  1.1 Related Work

Before we begin, we review related work on loss functions for evaluating
probabilistic predictions through the lenses of both statistics and economics.

_The statistician’s view: the likelihood principle._ It might seem that the
problem of choosing a loss function is a straightforward application of
statistical inference. The ingredients are right: given a dataset and a model
class that induces a set of probability distributions, we seek to understand
how well each distribution describes the data. Then, the standard statistics
textbook argument is that we should use the likelihood of the data to evaluate
each of these predicted distributions. This argument is known as the
“likelihood principle” (e.g., Berger and Wolpert, 1988): if the data was
generated by one of the predicted distributions, then likelihood is a
sufficient statistic for this distribution, containing all of the information
about the true generating distribution.

Should we then use likelihood to evaluate behavioral models’ predictions? The
catch is that this argument relies on the assumption that the model class is
“well-specified”, containing a model that outputs the true generating
distribution. This is not usually the case in behavioral economics, where it
is common to evaluate simple, low-parameter (or 0-parameter) models that aim
to approximate human behavior rather than to predict it perfectly. For
example, behavioral game theorists often compare their models to the classical
game theoretic prediction of Nash equilibrium, which often places 0
probability on actions that humans sometimes play, and so cannot have been the
true generating distribution. Negative log likelihood assigns a loss of
$\infty$ to this prediction, making this comparison uninformative. We
elaborate further on the problem of comparing imperfect (“misspecified”) model
classes when presenting our alignment axioms.

_The economist’s view: scoring rules._ Another closely related problem is that
of evaluating experts on their probabilistic forecasts of future events. Prior
work aims to perform these evaluations with _scoring rules_ (e.g., Gneiting
and Raftery, 2007), a class of loss functions that evaluate predictions
independently on each observation in a dataset. A large focus of this
literature has been finding axiomatic characterizations of particular scoring
rules. These characterizations agree that losses should be _proper_ —an axiom
that we refer to in our analysis as “distributionally proper”—but diverge
beyond this point: negative log likelihood is the only proper scoring rule
that satisfies a locality axiom (McCarthy, 1956), and two different neutrality
axioms characterize Brier score (Selten, 1998) and the spherical score (Jose,
2009).

We take inspiration from these axiomatic analyses, but our work differs in two
important ways. First, we do not attempt to characterize a single, ideal loss
function; we are only concerned with critical problems that arise when
training and evaluating behavioral models. We thus aim to propose axioms that
only address these critical problems, without being concerned that these
axioms leave us with an entire class of loss functions. Second, in many
applications of scoring rules, it is only possible to observe an outcome
once—for example, when evaluating weather, climate, political events, energy,
and healthcare forecasts (Carvalho, 2016). This contrasts sharply with
behavioral economics, where it is common to run laboratory experiments with
dozens or hundreds of participants, obtaining many samples of how a human
reasons in exactly the same strategic situation.

Interpretability for other tasks. Our axioms are concerned with evaluating
individual predictions. Fudenberg et al. (2022) tackle a different, related
problem of interpreting the performance of a model class, considering the
cross-validation performance of a training algorithm that selects a model from
this class. They formalize a notion of the _completeness_ of a training
algorithm, giving a score of 100% to an algorithm that gets the best possible
cross-validation performance and 0% to a baseline algorithm (for instance,
outputting a uniform random prediction on any training set). Their work
complements ours: their measure of completeness can be applied to any choice
of loss function, but they make no claims about how this loss should behave on
individual datasets, nor do they apply any analogue of our alignment axioms.
Thus, we recommend that researchers using cross-validation to evaluate a model
class should apply completeness to a base loss that satisfies our soundness
axioms.

##  2 Existing Losses for Behavioral Game Theory

We consider the task of evaluating predictive models of human behavior when
faced with a discrete set of options. This task is central to both decision
theory and behavioral game theory, where agents are offered a choice over a
set of lotteries or actions, respectively. In both settings, a researcher’s
task is to predict the human distribution of choices, which has elements of
randomness due both to variation between people and to inherent randomness in
individual people’s decision making.

Generally, researchers collect data and evaluate models on many different
decision-making settings at once, reporting a model’s performance across these
settings in aggregate. In this work, we focus on the simpler problem of
evaluating a model on a single decision-making setting; of course, this is an
essential first step toward the more general problem. Accordingly, we use the
terms “model” and “prediction” interchangeably, as each model only makes a
prediction on a single setting.

We model a single decision-making setting as follows. Let $A=\\{1,\ldots,d\\}$
be a fixed set of choices available to the decision maker being modelled
(e.g., experiment participants), and let $\Delta(A)$ be the set of
distributions over these choices, i.e., the $(d-1)$-dimensional simplex. We
assume that there exists a fixed but unknown distribution $p\in\Delta(A)$ of
human choices, where $p$ captures both sources of randomness just discussed.
An analyst can collect a dataset consisting of $n$ independent, identical
draws from $p$, which we denote $y\sim p^{n}$, representing actions taken by
distinct actors (for example, different participants in a psychology
experiment). We denote the set of all such datasets by
$\mathcal{D}(A)=\bigcup_{n=1}^{\infty}A^{n}$.

The analyst seeks to choose a model from some model class, which induces a set
of predicted distributions $\mathcal{F}\subseteq\Delta(A)$, that is good at
predicting the distribution of human behavior. For instance, $\mathcal{F}$
might be the set of predictions that a parametric model makes in a given
setting for various instantiations of its parameters. To make their choice,
the analyst relies on a loss function
$L:\Delta(A)\times\mathcal{D}(A)\to\mathds{R}$ representing preferences over
these predictions: that is, $L(f,y)<L(g,y)$ if and only if $f$ is a better
description of the data than $g$.333Note that objective functions can be
phrased in both “positive” and “negative” senses: for example, it is
equivalent to maximize accuracy or minimize error rate. In this paper, we use
the latter, “negative” sense.

We pause to define some additional notation. For any dataset
$y\in\mathcal{D}(A)$, let $n(y)$ denote the number of observations in $y$ (or
simply $n$, when $y$ is clear from context), and let $\bar{p}(y)\in\Delta(A)$
be its empirical distribution: that is, for all $a\in A$,
$\bar{p}(y)_{a}=\nicefrac{{\sum_{i=1}^{n(y)}\mathds{1}_{\\{y_{i}=a\\}}}}{{n(y)}}$
For any action $a\in A$, let $e_{a}\in\Delta(A)$ denote the point mass
distribution on $a$. Finally, for any finite set $X$, let $\Pi(X)$ be the set
of its permutations $\pi:X\to X$.

###  2.1 Common Loss Functions

While behavioral game theorists broadly take this approach of evaluating their
models with _some_ loss function, they largely disagree about precisely
_which_ loss function to use; in fact, it is not uncommon to for a single
paper to use multiple different losses while analyzing different experiments.
To illustrate this disagreement, we give seven examples of losses that are
common in the literature.

First, one common choice is the error rate $L_{\textrm{Err}}$ (Fudenberg and
Liang, 2019; García-Pola et al., 2020). This choice is especially common when
$\mathcal{F}$ consists only of deterministic predictions that assign
probability to only one action. A somewhat related alternative is L1 error
$L_{\textrm{L1}}$, which is also sometimes called “mean absolute deviation”
(Camerer et al., 2004; Levin and Zhang, 2019).

$\displaystyle\textstyle
L_{\textrm{Err}}(f,y)=\sum_{a=1}^{d}\bar{p}(y)_{a}(1-f_{a}),$
$\displaystyle\textstyle
L_{\textrm{L1}}(f,y)=\|f-\bar{p}(y)\|_{1}=\sum_{a=1}^{d}|f_{a}-\bar{p}(y)_{a}|.$

These two losses are attractive because of their clearly defined scale, with a
loss of 0 being achieved by a prediction that never makes mistakes (error
rate) or matches the data perfectly (L1 error), and a maximum loss of 1 or 2,
respectively, by a prediction that is never correct.

Next, several common losses are based on the likelihood of the data, given the
prediction. Perhaps the most common choice of loss in all of behavioral game
theory is negative log-likelihood (McKelvey and Palfrey, 1992; Stahl and
Wilson, 1995; Wright and Leyton-Brown, 2017).

$\displaystyle\textstyle
L_{\textrm{NLL}}(f,y)=-n\sum_{a=1}^{d}\bar{p}(y)_{a}\log(f_{a}).$

Cross-entropy (Kolumbus and Noti, 2019) differs from NLL by a factor of $n$,
and KL divergence further subtracts the entropy of the dataset.

$\displaystyle\textstyle
L_{\textrm{CE}}(f,y)=\frac{1}{n}L_{\textrm{NLL}}(f,a),$
$\displaystyle\textstyle
L_{\textrm{KL}}(f,y)=-\sum_{a=1}^{d}\bar{p}(y)_{a}\log(\frac{f_{a}}{\bar{p}(y)_{a}}).$

where $H(p)=-\sum_{a=1}^{d}p_{a}\log p_{a}$ is the entropy of a distribution.
All three of these options are rooted in statistics: they make up the core of
many statistical hypothesis tests, and all three of them agree with the
likelihood principle.

Two more losses originate from regression problems and the forecasting
literature. One is the Brier score, frequently referred to as mean-squared
error (Camerer et al., 2004; Golman et al., 2019).

$\displaystyle\textstyle
L_{\textrm{Brier}}(f,y)=\frac{1}{n}\sum_{i=1}^{n}\|f-e_{y_{i}}\|_{2}^{2}=\sum_{a=1}^{d}\bar{p}(y)_{a}((1-f_{a})^{2}+\sum_{a^{\prime}\neq
a}f_{a^{\prime}}^{2}).$

A small modification is the squared L2 error, which is often also
(confusingly) called MSE (Plonsky et al., 2019).

$\textstyle
L_{\textrm{L2}}(f,y)=\|f-\bar{p}(y)\|_{2}^{2}=\sum_{a=1}^{d}(f_{a}-\bar{p}(y)_{a})^{2}.$

Both are natural options for researchers familiar with regression problems,
where it is typical to optimize a least-squares objective. They also have
roots in forecasting, as the Brier score was originally introduced for
evaluating weather forecasts (Brier, 1950). To avoid confusion, throughout
this work, we avoid the ambiguous term “mean-squared error”, referring to the
former as the Brier score and the latter as the squared L2 error.

Finally, a unifying definition that ties together many losses is the concept
of a scoring rule. (Gneiting and Raftery, 2007, page 2.) A _scoring rule_ is a
function $S:\Delta(A)\times A\to\mathds{R}$ that maps a prediction
$f\in\Delta(A)$ and a single outcome $a\in A$ to a score $S(f,a)$. By
averaging these scores over the dataset, every scoring rule $S$ induces a loss
function $L_{S}(f,y)=\frac{1}{n}\sum_{i=1}^{n}S(f,y_{i})=\sum_{a\in
A}\bar{p}(y)_{a}S(f,a)$. Scoring rules are popular due to their simple
functional form, which simply evaluates the prediction independently on each
observation. Their alignment properties are also the subject of several
celebrated results (Savage, 1971; Gneiting and Raftery, 2007), which we
describe in detail in Section 5. Error rate, negative-log likelihood, cross-
entropy, and Brier score are all scoring rules; L1, KL, and squared L2 are
not.

##  3 Formalizing an Ideal Loss Function

Each loss function from the previous section captures the quality of a
prediction on a dataset with a single number, inducing preferences over these
predictions. Of course, these loss functions will not always agree with each
other about how to order different models. Is each of these losses an equally
acceptable choice? To answer this question, we turn to an axiomatic analysis,
formalizing axioms that a loss function in a behavioral economic setting ought
to obey. We aim to identify axioms that are as weak as possible, in order that
they will only disqualify loss functions that exhibit clearly objectionable
behavior.

Our axioms can be grouped according to two distinct roles that a loss function
serves in describing the quality of a prediction. First, loss functions are
used to compare the quality of models within a fixed experimental setting.
This occurs both during training, when a modeller aims to minimize expected
loss on future data; and when evaluating models on a given dataset, comparing
losses to see which model achieves the best performance. Our two _alignment_
axioms address this case, requiring that the loss correctly orders predictions
in cases where quality disparities are unambiguous; both are extensions of
already standard _propriety_ axioms. Second, loss functions are used to
understand model performance more broadly; studies report losses and these
values are interpreted as conveying information about how well a given model
captured human behavior. Our three _interpretability_ axioms ensure that the
loss can indeed be understood in this way, having a well-defined reference
point and changing coherently as the data varies.

###  3.1 Alignment Axioms

Our first alignment axiom pertains to the situation where two models’
predictions are compared to each other on a fixed dataset. This is a
fundamental step in behavioral modelling: to evaluate the performance of a
proposed model, one must compare its predictions on _some_ dataset to other
existing models to understand whether their proposal better captures human
behavior. Here, if one model is a better fit to the data than another, it
should receive a lower loss.

What do we mean by “better”? Reasonable people disagree about many comparisons
between models, but some are unarguable. For instance, a perfect
prediction—one that exactly matches the dataset—is better than an imperfect
one. A standard axiom in the literature, known as Propriety, captures this
intuition by requiring that a perfect prediction minimizes the loss. To
distinguish it from a Distributional Propriety axiom that will follow, we
refer to it as _Sample Propriety_.

######  Axiom 1 (Sample Propriety (SP)).

For all predictions $f\in\Delta(A)$ and sampled datasets $y\in\mathcal{D}(A)$,

$f\neq\bar{p}(y)\implies L(\bar{p}(y),y)<L(f,y).$

Unfortunately, Sample Propriety is insufficient for behavioral game theory.
The reason is that parametric behavioral models are often misspecified: there
is often no model in a given class that is able to output the empirical
distribution of an arbitrary dataset. We thus impose a stronger requirement
that implies Sample Propriety: that we should prefer one (potentially
imperfect) prediction to another whenever the first does an unambiguously
better job of fitting the data. We formalize this idea with the notion of a
Pareto improvement, which we will use extensively in what follows. [Pareto
improvement] Let $p,q,r\in\Delta(A)$ be three distributions. We say that $q$
is a _Pareto improvement_ over $p$ with respect to $r$, denoted by
$q\succ_{r}p$, if for all $a\in A$, either $p_{a}\leq q_{a}\leq r_{a}$ or
$p_{a}\geq q_{a}\geq r_{a}$, and furthermore this inequality between $p_{a}$
and $q_{a}$ is strict for at least one $a$. In other words, $q$ is a Pareto
improvement over $p$ if $q$ is at least as close to $r$ as $p$ in every
dimension, and is strictly nearer to $r$ in some dimension. Then, if a
prediction is a Pareto improvement over another prediction, i.e., all the
predicted action proportions of $f$ are uniformly closer to the empirically
observed play distribution than $g$’s predicted proportions, then $f$ clearly
is a better prediction than $g$, and so should receive a lower loss.

######  Axiom 2 (Sample Pareto-Alignment (SPA)).

For all predictions $f,g\in\Delta(A)$ and sampled datasets
$y\in\mathcal{D}(A)$,

$f\succ_{\bar{p}(y)}g\implies L(f,y)<L(g,y).$

It is also crucial that loss functions align with notions of quality in the
training process. While training, the goal of a modeller is to select the
prediction that minimizes the expected test loss over new, unseen data. Thus,
the loss function should be aligned not only on a specific sample, but in
expectation. As with SP, it is standard to insist that the expected loss must
be minimized when the true distribution is reported.

######  Axiom 3 (Distributional Propriety (DP)).

For all predictions $f\in\Delta(A)$ and all $n\geq 1$, $p\in\Delta(A)$,

$f\neq p\implies\mathop{\mathds{E}}_{y\sim
p^{n}}L(p,y)<\mathop{\mathds{E}}_{y\sim p^{n}}L(f,y).$

As above, though, Distributional Propriety is insufficient when the model
class is misspecified. In this case, it is necessary to prefer predictions
that are clearly closer to the true data-generating distribution, accurately
reflecting improvements even away from the optimum. We capture this intuition
with a second alignment axiom, which we refer to as distributional Pareto-
alignment.

######  Axiom 4 (Distributional Pareto-Alignment (DPA)).

For all predictions $f,g\in\Delta(A)$, and all $n\geq 1$, $p\in\Delta(A)$,

$f\succ_{p}g\implies\mathop{\mathds{E}}_{y\sim
p^{n}}L(f,y)<\mathop{\mathds{E}}_{y\sim p^{n}}L(g,y).$

In the same way as SPA implies SP, DPA implies DP. A similar axiom was
proposed by Lambert et al. (2008) under the name “accuracy-rewarding”. There
is only one difference: in their setting, a prediction is a vector in
$\mathds{R}^{d}$, containing independent predictions for $d$ different summary
statistics of the dataset. Because our predictions lie on the simplex, they
are not independent in this way: e.g., predicting that one action has a
probability of 1 constrains the predictions for all other actions to be 0.

###  3.2 Interpretability Axioms

Our alignment axioms constrain how the loss may vary as the prediction varies.
Our next axioms constrain how the loss may vary as the data varies. Such
constraints are important for ensuring that loss represents an understandable
measurement of a prediction’s quality. One simple way that the data could be
changed is simply by making the same observations in a different order. Since
in our setup, each observation corresponds to an independent trial involving a
distinct participant, we argue that the loss should be unaffected by such
reordering.

######  Axiom 5 (Exchangeability (Ex)).

For all datasets $y\in\mathcal{D}(A)$, permutations
$\pi\in\Pi(\\{1,\ldots,n(y)\\})$, and predictions $f\in\Delta(A)$,
$L(f,\pi(y))=L(f,y)$.

Exchangeability is a standard assumption in many statistical methods (e.g.,
Easton, 1989) and loss functions; as we will see later, none of the commonly
used BGT losses described earlier violate it.

What if the dataset varies in a more substantial way? For example, one might
replicate an experiment with a second group of participants, resulting in a
new set of observations for the same game. Alternatively, one might run slight
variations to an experiment to assess their impact on the quality of a model
Goeree and Holt (2001). In both cases, it would be undesirable if the change
in the data could cause the prediction to clearly decrease in quality, but be
awarded a better loss.

As with varying predictions, there are many ways in which datasets could vary
for which reasonable people could disagree about whether the same prediction
ought to receive a higher or lower loss. However, we can again leverage the
insight that Pareto improvements are unambiguously better: holding a
prediction fixed, if the empirical probabilities of the data are brought
closer to the predictions for at least some actions and further in none, it is
clear that this dataset is better described by the prediction. In such cases,
we require that the loss must also improve.

######  Axiom 6 (Counterfactual Pareto-Regularity (CPR)).

Let $f\in\Delta(A)$ be a fixed prediction. Suppose that
$y,y^{\prime}\in\mathcal{D}(A)$ are two datasets of equal size, where
$n(y)=n(y^{\prime})$. Then

$\bar{p}(y)\succ_{f}\bar{p}(y^{\prime})\implies L(f,y^{\prime})>L(f,y).$

Up to this point, all of the axioms have only described equalities or
inequalities between certain pairs of losses. None have constrained the
precise numerical values of the losses: indeed, if $L$ satisfies all of these
axioms, then any positive affine transformation $aL+b$ (with $a>0$) does too.
This leaves users with a free choice of how to set these two degrees of
freedom. We propose to use this freedom to constrain the minimum loss,
requiring that a perfect prediction (which must be the loss function’s
minimum, by SPA) achieves a loss of zero. This makes the loss easier to
interpret, removing the possibility for irreducible error, where even a
perfect prediction could get a positive loss.

######  Axiom 7 (Zero-Minimum (ZM)).

For all $y\in\mathcal{D}(A)$, $L(\bar{p}(y),y)=0$.

ZM is admittedly the most subjective of our axioms: for example, on some
problems, it might be reasonable to anchor the loss to a different baseline
instead, such as a uniform random prediction. In response to this
subjectiveness, in Section 4, we give partial results that do not refer to ZM
whenever possible. Additionally, its addition is inconsequential when
analyzing existing loss functions: in Section 5, we show that each commonly
used loss that violates ZM also violates CPR.

##  4 Diagonal Bounded Bregman Divergences

With these desiderata in mind, the obvious question is: are there loss
functions that satisfy all of our axioms? In this section, we provide a
positive answer. We first appeal to existing results to show that even asking
for a subset of the axioms gives these loss functions considerable structure:
Bregman divergences are essentially the only losses that satisfy SP, DP, Ex,
and ZM. Narrowing down this class further, we identify a family of losses,
which we coin _diagonal bounded Bregman divergences_ , that each satisfy our
whole set of axioms (SPA, DPA, CPR, Ex, and ZM).

Let us now make these claims more precise. We first define a Bregman
divergence. Let $\overline{\mathds{R}}$ denote the extended real numbers
$\mathds{R}\cup\\{\pm\infty\\}$, and adopt the convention that
$0\cdot\infty=0$. Let $B:C\to\mathds{R}$ be a closed and proper strictly
convex function on a convex set $C\subseteq\mathds{R}^{k}$. Then a
_subgradient_ of $B$ is a function $dB:C\to\overline{\mathds{R}}^{k}$ such
that

$B(x)-B(x_{0})\geq dB(x_{0})^{T}(x-x_{0})$

for all $x_{0},x\in C$. If $B$ is also differentiable, it has a unique
subgradient $\nabla B$ on the interior of $C$.

[] Given a closed and proper strictly convex function $B:C\to\mathds{R}$ and
subgradient $dB$ of $B$, the _Bregman divergence_ $\nabla_{(B,dB)}:C\times
C\to\overline{\mathds{R}}_{\geq 0}$ of $B$ and $dB$ is

$\nabla_{(B,dB)}(p,q)=B(p)-B(q)-dB(q)^{T}(p-q).$

We now leverage existing work from the field of property elicitation, which
asks: if an agent seeks to minimize their expected loss, which loss functions
will incentivize them to report their true belief about a particular property
of the distribution? In these terms, DP requires that loss functions elicit
the true underlying distribution of each sample when datasets are known to be
composed of i.i.d. samples. Abernethy and Frongillo (2012) show that, for this
property (and, in fact, for many properties), essentially all such incentive-
compatible loss functions are equivalent to Bregman divergences between some
function of the dataset and the prediction, up to a translation by some
function of the dataset. This immediately yields the following result.

######  Theorem 1 (Corollary of Theorem 11 of Abernethy and Frongillo (2012),
informal).

Under mild technical conditions, a well-behaved loss function $L$ that
satisfies DP must be of the form

$L(f,y)=\nabla_{(B,dB)}(\rho(y),f)+c(y)$

for some closed and proper strictly convex function $B$ and subgradient $dB$,
and some translation $c:\mathcal{D}(A)\to\mathds{R}$ and summary statistic
$\rho:\mathcal{D}(A)\to\Delta(A)$ of the data, where
$\mathop{\mathds{E}}_{y\sim p^{n}}\rho(y)=p$ for all $n,p$.

We extend this result, showing that adding the SP and ZM axioms additionally
determines $c$ and $\rho$. In other words, essentially every loss function
satisfying DP, SP, and ZM is a Bregman divergence between the empirical mean
of the data and the prediction.

######  Theorem 2 (Informal).

Under mild technical conditions, a well-behaved loss function $L$ that
satisfies SP and DP must be of the form

$L(f,y)=\nabla_{(B,dB)}(\bar{p}(y),f)+c(y)$

for some closed and proper strictly convex function $B$, subgradient $dB$ of
$B$, and translation $c$. If $L$ additionally satisfies ZM, then $c(y)=0$ for
all $y$.

Conversely, every loss function $L$ of this form satisfies SP and DP, and if
$c(y)=0$ for all $y$, then $L$ also satisfies ZM and Ex.

We defer a formal statement and proof of Theorem 2 to the appendix, as it
takes care to describe the technical conditions on $L$. The proof first
carefully obtains $L$ satisfying DP from Theorem 11 of Abernethy and Frongillo
(2012), and then applies standard facts about Bregman divergences to show that
the additional axioms constrain $\rho$ and $c$ as described. The reverse
direction similarly follows from standard observations from convex analysis.

However, not all Bregman divergences satisfy our remaining axioms SPA, DPA,
and CPR. For example, taking $B(f)=-H(f)=\sum_{a=1}^{d}f_{a}\log f_{a}$
recovers the KL divergence; we will show in Section 5 that this does not
satisfy SPA. Our main result is that all of our axioms are satisfied by the
restricted set of _diagonal bounded Bregman divergences_. [Diagonal bounded
Bregman divergence (DBBD)] Let $b:[0,1]\to\mathds{R}$ be a continuously
differentiable convex function where $b^{\prime}$ is bounded on $[0,1]$. Let
$B_{b}(x)=\sum_{i}b(x_{i})$ for $x\in[0,1]^{d}$. Then, a _diagonal bounded
Bregman divergence_ is a loss function
$L:\Delta(A)\times\mathcal{D}(A)\to\mathds{R}$, where
$L(f,y)=\nabla_{(B_{b},\nabla B_{b})}(\bar{p}(y),f).$

######  Theorem 3.

If $L$ is a DBBD, then $L$ satisfies SPA, DPA, Ex, CPR, and ZM.

We again defer a complete proof to the appendix. Briefly: Ex is trivial, and
ZM follows from Theorem 2; SPA, DPA, and CPR each leverage the diagonal
structure and convexity of $B_{b}$.

##  5 Evaluating Existing Loss Functions Using Our Axioms

We now revisit the loss functions introduced in Section 2. It is
straightforward to see that squared L2 error is a DBBD (set $b(x)=x^{2}$) and
so satisfies all of the axioms. Each other loss function violates at least one
axiom, as summarized in Table 1. We go through each of these losses below,
demonstrating that in each case the axiom violations produce undesirable
results under reasonable conditions.

###  5.1 Error rate

Error rate violates every axiom except Ex. We show that error rate violates
both SP and ZM with the following example. Consider a game in which a player
can choose between two actions, “defect” and “cooperate”. Suppose that in the
true distribution of human play, two-thirds of players defect: $p=(2/3,1/3)$.
Running an experiment with 10 distinct participants, an analyst finds that 6
chose to defect, while the remaining 4 chose to cooperate, yielding an
empirical distribution of $\bar{p}(y)=(0.6,0.4)$. Let $(f,1-f)$ be a
prediction in this setting. Then, the error rate on this dataset is

$\textstyle L_{\textrm{Err}}(f,y)=1-0.6f-0.4(1-f)=0.6-0.2f.$

This expression is minimized by the prediction $f=1$, which has an error rate
of 0.4. In particular, this prediction achieves a lower error rate than
reporting the empirical distribution, which has an error rate of
$L_{\textrm{Err}}(\bar{p}(y),y)=0.48$. This example illustrates a general
problem: for any dataset $y$, the empirical distribution yields an error rate
of $1-\|\bar{p}(y)\|_{2}^{2}$, while predicting the mode gives rise to a lower
error rate of $1-\max_{a}\bar{p}(y)_{a}$. Thus, preferring predictions with
lower error rates leads to incorrect conclusions, giving more credit to
predictions that overestimate the probability of the most likely action and
underestimate the probabilities of the others.

###  5.2 L1 error

L1 error satisfies both SPA and ZM, but does not satisfy DPA or DP. In some
cases, a model that predicts the true population distribution gets worse
expected L1 error on unseen data than an incorrect prediction. As in Example
5.1, suppose again that the true distribution is $p=(2/3,1/3)$, However, now
suppose that the dataset is not yet available; all that is known about it is
that it consists of 10 independent observations sampled from $p$. Then, the
expected loss of predicting $(f,1-f)$ is $\mathop{\mathds{E}}_{y\sim
p^{10}}L_{\textrm{L1}}(f,y)=2\mathop{\mathds{E}}_{y\sim
p^{10}}|f-\bar{p}(y)_{D}|,$ where $10\bar{p}(y)_{D}$, the number of
participants that defect in the experiment, is a Binomial random variable with
parameters $n=10,p=2/3$. This expected loss is minimized by predicting the
median of $\bar{p}(y)_{D}$, which is $0.7$. In particular, this prediction
even receives a lower expected loss than predicting the true distribution; the
true distribution achieves an expected loss of $0.243$, while the median gets
an expected loss of $0.235$. This example, too, generalizes: in any setting
with two actions, the expected loss is minimized by reporting the median of
the empirical probability distribution, which is generally not equal to $p$;
in fact, these quantities can differ by $1/2n$. In other words, if a model is
designed to minimize expected loss, L1 error fails to elicit the true
distribution.

Axiom |  Error rate |  L1 error |  NLL |  Cross-entropy |  KL divergence |  Brier score |  Squared L2 error
---|---|---|---|---|---|---|---
Sample Pareto-Alignment (SPA) | ✗ | ✓ | ✗ | ✗ | ✗ | ✓ | ✓
Sample Propriety (SP) | ✗ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Distributional Pareto-Alignment (DPA) | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓
Distributional Propriety (DP) | ✗ | ✗ | ✓ | ✓ | ✓ | ✓ | ✓
Exchangeability (Ex) | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | ✓
Counterfactual Pareto-Regularity (CPR) | ✗ | ✓ | ✗ | ✗ | ✗ | ✗ | ✓
Zero Minimum (ZM) | ✗ | ✓ | ✗ | ✗ | ✓ | ✗ | ✓
Table 1: Existing losses and their status under the axioms.

###  5.3 Cross-entropy, negative log likelihood, and Brier score

We group the next three losses together as they suffer from the same key
issue: they all violate both CPR and ZM. A second experimenter attempts to
reproduce the results from Example 5.1. They first fit a model to the existing
dataset $y$, which has an empirical distribution of $\bar{p}(y)=(0.6,0.4)$;
their model fits perfectly, returning the exact empirical distribution.
Evaluating this model with Brier score and cross-entropy gives losses of

$L_{\textrm{Brier}}(\bar{p}(y),y)=0.48;\quad
L_{\textrm{CE}}(\bar{p}(y),y)=0.29.$

They then collect their own dataset $y^{\prime}$, re-running the experiment
with a different set of 10 participants; they find that 9 defect and only one
cooperates. They are surprised to find that, although their old model fails to
predict this new dataset perfectly, it achieves lower losses of

$L_{\textrm{Brier}}(\bar{p}(y),y^{\prime})=0.36;\quad
L_{\textrm{CE}}(\bar{p}(y),y^{\prime})=0.24.$

In general, the minimum possible Brier score is $1-\|\bar{p}(y)\|_{2}^{2}$,
and the minimum possible cross-entropy is the entropy of $\bar{p}(y)$. NLL
also fails in the same way, as it is simply a rescaling of cross-entropy.

###  5.4 KL divergence

The KL divergence is a translated version of cross-entropy that satisfies ZM,
but doesn’t satisfy SPA, DPA or CPR. The key issue is that KL divergence gives
infinite losses at the boundary. That is, when a model predicts that an action
has zero probability of being selected, but the action has support in the
data, that model will have an infinite KL divergence. This leads to situations
such as the following. Now, suppose that there are three actions, with a true
distribution of $p=(0.001,0.199,0.8)$, and that among $100$ participants we
observe $y=(1,19,80)$, yielding an empirical distribution of
$\bar{p}(y)=(0.01,0.19,0.80)$. Consider comparing two predictions on this
dataset: the very coarse prediction of $f=(0,1,0)$ and the far more precise
$f^{\prime}=(0,0.2,0.8)$. Although $f^{\prime}$ is a better prediction, as it
is closer to $\bar{p}(y)$ than $f$ on both the second and third actions, both
receive equal losses of
$L_{\textrm{KL}}(f,y)=L_{\textrm{KL}}(f^{\prime},y)=\infty$. In general, when
every action appears at least once in the dataset, KL divergence assesses
every prediction that places 0 probability on any action as equally bad, and
considers all of these predictions to be worse than any prediction having full
support. This is a serious problem, as it is common for every action to be
played at least once in sufficiently large behavioral datasets: researchers
often remark on the fact that subjects play dominated actions. This makes it
extraordinarily difficult to evaluate classical economic predictions, such as
expected utility maximization or Nash equilibrium, which assign 0 probability
to many actions. To avoid this issue, some researchers (e.g., Stahl and
Wilson, 1994) perturb the predictions of such models to yield finite losses,
but in doing so introduce an important new perturbation parameter and
sacrifice the ability to evaluate the original models.

###  5.5 Scoring rules

Recall that error rate, cross-entropy, negative log likelihood, and Brier
score—all of which are scoring rules—each violated the ZM and CPR axioms. It
turns out that these failures are common to all scoring rules, implying that
scoring rules should not be used to report model performance.

[] Every scoring rule that satisfies SPA violates ZM. Moreover, no scoring
rule satisfies CPR.

We defer the proof to the appendix. Intuitively, since scoring rules must
consider each sample independently, they must treat every sample as if it were
the entire dataset. Then, in order to satisfy SPA, scoring rules must give
positive losses to every nondeterministic prediction, causing them to violate
the ZM axiom. Moreover, scoring rules are linear in the empirical
probabilities $\bar{p}(y)$ (Section 2.1). Any such linear function is
maximized at one of its boundaries, meaning that is it not uniquely maximized
at $\bar{p}(y)=f$ unless $\bar{p}(y)$ is a unit vector; hence, all scoring
rules violate CPR.

However, while scoring rules fail the interpretability axioms, they do not
necessarily violate the alignment axioms. In fact, a classic result
characterizes the set of scoring rules satisfying DP.

######  Theorem 4.

(Gneiting and Raftery, 2007, Theorem 1.) A scoring rule satisfies DP if and
only if there exists a strictly convex function $B:\Delta(A)\to\mathds{R}$ and
subgradient $dB$ such that, for all $f\in\Delta(A)$ and $a\in A$,

$S(f,a)=-B(f)-dB(f)^{T}(e_{a}-f).$

Furthermore, every such scoring rule satisfies SP.

It is no coincidence that this characterization is strikingly similar to the
definition of a Bregman divergence, only differing by a shift of $B(p)$.
Indeed, for every DBBD, there exists a scoring rule expressing exactly the
same preferences between predictions. To be precise, suppose that
$L(f,y)=\nabla_{(B,dB)}(\bar{p}(y),f)$ is some Bregman divergence. Then,
consider the alternative loss $L^{\prime}(f,y)=L(f,y)+c(y)$, where $c(y)$ is
an arbitrary function that depends only on the data (and not on the
prediction). This shifted loss induces exactly the same preferences over
models on every dataset and every distribution. In particular, it is
straightforward to show that setting $c(y)=-B(\bar{p}(y))$ makes
$L^{\prime}(f,y)$ a scoring rule.

What’s more, these scoring rules are computationally easier to minimize than
their corresponding DBBDs. Scoring rules can be computed without explicitly
calculating $\bar{p}(y)$, which makes them ideal for training on large
datasets, as the loss can be evaluated without loading the entire dataset into
memory at once. Therefore, we do not recommend against the use of scoring
rules for model training—it may often be a good idea! We simply argue that
researchers should use a corresponding DBBD when evaluating model performance
or otherwise reporting results.

##  6 Conclusions

Our goal in this paper was to identify suitable loss functions for evaluating
behavioral economics models. We took an axiomatic approach, developing axioms
describing alignment and interpretability properties that such a loss function
should satisfy. We showed that almost all of the loss functions used in
practice, including the entire class of scoring rules, violate at least one of
these axioms. However, it is indeed possible to construct loss functions that
satisfy all of our axioms: we identified a large class of losses—the diagonal
bounded Bregman divergences—that does. Thus, we advocate that behavioral
economists use one of these loss functions in future work; in particular, the
squared L2 error, which is already used relatively widely, is a natural
incumbent.

Is it possible to make a theoretical argument for a single best loss function
for behavioral economic research? If so, the path forward is to identify
additional desirable properties for loss functions in behavioral research. For
example, on “rock-paper-scissors” experiments, one might insist on loss
functions that are agnostic to the actions’ identities, ensuring that they do
not treat “rock” differently from “paper” or “scissors”. Making compelling
arguments for such new axioms and understanding how they narrow down the space
of permissible losses—indeed, whether any remain at all—is a valuable
direction for future work.

## Acknowledgements

Thanks to Frederik Kunstner and Victor Sanches Portella for helpful
discussions. This work was funded by an NSERC CGS-D scholarship, an NSERC USRA
award, an NSERC Discovery Grant, a DND/NSERC Discovery Grant Supplement, a
CIFAR Canada AI Research Chair (Alberta Machine Intelligence Institute),
awards from Facebook Research and Amazon Research, and DARPA award
FA8750-19-2-0222, CFDA #12.910 (Air Force Research Laboratory).

## References

  * Abernethy and Frongillo [2012] Jacob D. Abernethy and Rafael M. Frongillo.  A characterization of scoring rules for linear properties.  _Conference on Learning Theory_ , 2012.
  * Berger and Wolpert [1988] James O. Berger and Robert L. Wolpert.  _The likelihood principle_.  1988\.
  * Brier [1950] Glenn W. Brier.  Verification of forecasts expressed in terms of probability.  _Monthly weather review_ , 78(1):1–3, 1950.
  * Camerer et al. [2004] Colin F. Camerer, Teck-Hua Ho, and Juin-Kuan Chong.  A cognitive hierarchy model of games.  _The Quarterly Journal of Economics_ , 119(3):861–898, 2004.
  * Carvalho [2016] Arthur Carvalho.  An overview of applications of proper scoring rules.  _Decision Analysis_ , 13(4):223–242, 2016.
  * Easton [1989] Morris L. Easton.  Finite de Finetti style theorems.  In _Group invariance in applications in statistics_. 1989.
  * Fudenberg and Liang [2019] Drew Fudenberg and Annie Liang.  Predicting and understanding initial play.  _American Economic Review_ , 109(12):4112–41, 2019.
  * Fudenberg et al. [2022] Drew Fudenberg, Jon Kleinberg, Annie Liang, and Sendhil Mullainathan.  Measuring the completeness of economic models.  _Journal of Political Economy_ , 130(4):956–990, 2022.
  * García-Pola et al. [2020] Bernardo García-Pola, Nagore Iriberri, and Jaromír Kovářík.  Non-equilibrium play in centipede games.  _Games and Economic Behavior_ , 120:391–433, 2020.
  * Gneiting and Raftery [2007] Tilmann Gneiting and Adrian E. Raftery.  Strictly proper scoring rules, prediction, and estimation.  _Journal of the American statistical Association_ , 102(477):359–378, 2007.
  * Goeree and Holt [2001] Jacob K. Goeree and Charles A. Holt.  Ten little treasures of game theory and ten intuitive contradictions.  _American Economic Review_ , 91(5):1402–1422, 2001.
  * Golman et al. [2019] Russell Golman, Sudeep Bhatia, and Pat Kane.  The dual accumulator model of strategic deliberation and decision making.  _Psychological review_ , 2019.
  * Jose [2009] Victor Richmond Jose.  A characterization for the spherical scoring rule.  _Theory and Decision_ , 66(3):263–281, 2009.
  * Kahneman and Tversky [2013] Daniel Kahneman and Amos Tversky.  Prospect theory: An analysis of decision under risk.  In _Handbook of the fundamentals of financial decision making: Part I_ , pages 99–127. 2013.
  * Kneeland [2015] Terri Kneeland.  Identifying higher-order rationality.  _Econometrica_ , 83(5):2065–2079, 2015.
  * Kolumbus and Noti [2019] Yoav Kolumbus and Gali Noti.  Neural networks for predicting human interactions in repeated games.  _arXiv preprint arXiv:1911.03233_ , 2019.
  * Lambert et al. [2008] Nicolas Lambert, David Pennock, and Yoav Shoham.  Eliciting properties of probability distributions.  pages 129–138, 07 2008.
  * Levin and Zhang [2019] Dan Levin and Luyao Zhang.  Bridging level-k to Nash equilibrium.  _Review of Economics and Statistics_ , 104:1329–1340, 2019\.
  * McCarthy [1956] John McCarthy.  Measures of the value of information.  _Proceedings of the National Academy of Sciences of the United States of America_ , 42(9):654, 1956.
  * McKelvey and Palfrey [1992] Richard D. McKelvey and Thomas R. Palfrey.  An experimental study of the centipede game.  _Econometrica_ , 60:803–836, 1992.
  * Murphy [2012] Kevin P. Murphy.  _Machine learning - a probabilistic perspective_.  Adaptive computation and machine learning series. MIT Press, 2012.
  * Plonsky et al. [2019] Ori Plonsky, Reut Apel, Eyal Ert, Moshe Tennenholtz, David Bourgin, Joshua C. Peterson, Daniel Reichman, Thomas L. Griffiths, Stuart J. Russell, Evan C. Carter, James F. Cavanagh, and Ido Erev.  Predicting human decisions with behavioral theories and machine learning.  _CoRR_ , abs/1904.06866, 2019.
  * Savage [1971] Leonard J Savage.  Elicitation of personal probabilities and expectations.  _Journal of the American Statistical Association_ , 66(336):783–801, 1971.
  * Selten [1998] Reinhard Selten.  Axiomatic characterization of the quadratic scoring rule.  _Experimental Economics_ , 1(1):43–61, 1998.
  * Stahl and Wilson [1994] Dale O. Stahl and Paul W. Wilson.  Experimental evidence on players’ models of other players.  _Journal of economic behavior & organization_, 25(3):309–327, 1994.
  * Stahl and Wilson [1995] Dale O. Stahl and Paul W. Wilson.  On players’ models of other players: Theory and experimental evidence.  _Games and Economic Behavior_ , 10:218–254, 1995.
  * Wright and Leyton-Brown [2017] James R. Wright and Kevin Leyton-Brown.  Predicting human behavior in unrepeated, simultaneous-move games.  _Games and Economic Behavior_ , 106:16–37, 2017.

In the following appendices we provide proofs for the technical results in
Sections 4 and 5. Appendix A gives a formal statement and proof of Theorem 2,
our extension of a result from Abernethy2012 that characterizes all nice loss
functions that satisfy a subset of our axioms. Appendix B proves Theorem 3,
that every DBBD satisfies all of the axioms. Finally, Appendix C proves
Section 5.5, that no scoring rule can satisfy all of the axioms.

##  Appendix A Formal Statement and Proof of Theorem 2

To formally state the first half of Theorem 2, we need the following
definitions.

Fix $n\in\mathbb{N}$, and let $L:\Delta(A)\times
A^{n}\to\overline{\mathds{R}}$ be a loss function. Then
$\Gamma:\Delta(A^{n})\to\Delta(A)$ is a _minimizer_ of $L$ if for all
$\mu\in\Delta(A^{n}),$

$\Gamma(\mu)\in\arg\min_{f\in\Delta(A)}\mathop{\mathds{E}}_{y\sim\mu}L(f,y).$

When $L$ satisfies DP, then $\Gamma(p^{n})=p$. Note that Abernethy2012 defines
a loss function $L$ to be _proper for_ a given property $\Gamma$ if $\Gamma$
minimizes $L$; we instead begin with $L$ and obtain $\Gamma$ for which $L$ is
proper by construction.

Let $L:\Delta(A)\times A^{n}\to\overline{\mathds{R}}$ be a loss function
satisfying DP, and let $\Gamma$ be a minimizer of $L$. $L$ is _$\Gamma$
-differentiable_ if for all $f\in\textrm{relint}(\Delta(A))$, and
$\mu\in\Gamma^{-1}(f)$, the directional derivative

$\lim_{\epsilon\to 0}\frac{\mathop{\mathds{E}}_{y\sim\mu}L(f+\epsilon
v,y)-\mathop{\mathds{E}}_{y\sim\mu}L(f,y)}{\epsilon}$

exists for all $v$ such that $f+\epsilon v\in\Delta(A)$ for sufficiently small
$\epsilon$.

We can now formally state the second claim of Theorem 2.

######  Theorem 5 (Theorem 2, Part I (formal)).

Fix $n\in\mathbb{N}$, and let $L:\Delta(A)\times
A^{n}\to\overline{\mathds{R}}$ satisfy SP and DP. Suppose that $L$ is
$\Gamma$-differentiable for some minimizer $\Gamma$ of $L$. Then there exists
some closed and proper strictly convex function $B$ and subgradient $dB$, and
some translation $c$ such that $L$ is of the form

$L(f,y)=\nabla_{(B,dB)}(\bar{p}(y),f)+c(y),$

for all $f\in\textrm{relint}(\Delta(A)),y\in A^{n}$. If $L$ also satisfies ZM,
then $c(y)=0$ for all $y\in A^{n}$.

###### Proof.

Taking $U=\Delta(A)$ and $\Omega=A^{n}$, we can apply Theorem 11 of
Abernethy2012 to find that there exists some convex function $B$ and
subgradient $dB$ as well as functions $\rho:A^{n}\to\Delta(A)$ and
$c:A^{n}\to\mathds{R}$ such that for all $f\in\textrm{relint}(\Delta(A)),y\in
A^{n}$,

$L(f,y)=\nabla_{(B,dB)}(\rho(y),f)+c(y).$

Moreover, $B$ is _strictly_ convex. This would follow immediately if reporting
the true distribution uniquely minimized the expected loss over _arbitrary_
data distributions—allowing for arbitrary correlations between samples—but our
DP axiom only requires this for i.i.d. data. However, it is possible to repair
this problem with the following modification to their proof. Given a basis
$\\{b_{i}\\}$ of $\Delta(A)$, they select a set of corresponding distributions
$\mu_{i}\in\Gamma^{-1}(b_{i})$; by the DP axiom, we know that
$b_{i}^{n}\in\Gamma^{-1}(b_{i})$, so we can pick $\mu_{i}=b_{i}^{n}$. Then,
for any linear combination $f=\sum_{i}\alpha_{i}b_{i}$, the distribution
$\hat{\mu}[f]=\sum_{i}\alpha_{i}\mu_{i}$ samples i.i.d. from $f$. Using this
choice of distributions $\mu_{i}$, the remainder of their proof only requires
that $L$ be proper for distributions of $n$ i.i.d. observations. In this case,
our DP axiom gives a strict inequality
$B(f)+dB(f)^{T}(f^{\prime}-f)<B(f^{\prime})$ for all $f\neq f^{\prime}$; by
Proposition D.6.1.3 of Hiriart-Urruty2001, this yields strict convexity of
$B$.

Since a Bregman divergence $\nabla_{(B,dB)}(p,q)$ of strictly convex $B$ is
uniquely minimized by $p=q$, for any $y\in A^{n}$, $L(f,y)$ is uniquely
minimized by $f=\rho(y)$; thus, SP constrains that $\rho(y)=\bar{p}(y)$ for
all $y$.

Finally, ZM implies that for all $y\in A^{n}$,

$L(\bar{p}(y),y)=\nabla_{(B,dB)}(\bar{p}(y),\bar{p}(y))+c(y)=0+c(y)=0,$

so $c(y)=0$ for all $y$. Thus $L(f,y)=\nabla_{(B,dB)}(\bar{p}(y),f)$ for all
$y\in A^{n}$, $f\in\textrm{relint}(\Delta(A))$. ∎

We now prove the second half of Theorem 2.

######  Theorem 6 (Theorem 2, Part II).

If $L(f,y)=\nabla_{(B,dB)}(\bar{p}(y),f)+c(y)$ for some closed and proper
strictly convex function $B:C\to\mathds{R}$ such that $\Delta(A)\subseteq C$,
subgradient $\smash{dB:C\times C\to\overline{\mathds{R}}^{d}}$ of $B$, and
translaton $c:A^{n}\to\mathds{R}$, then $L$ satisfies SP and DP. If $c(y)=0$
for all $y$, then $L$ also satisfies ZM and Ex.

All four of these axioms follow from a basic property of Bregman divergences
of all strictly convex functions, which is that $\nabla_{(B,dB)}(p,q)\geq 0$,
with equality if and only if $p=q$.

###### Proof.

SP. For any Bregman divergence with strictly convex $B$ and fixed
$\bar{p}(y)$, $\nabla_{(B,dB)}(\bar{p}(y),f)$ is uniquely minimized by
$f=\bar{p}(y)$. Since $y$ is fixed, the translation by $c(y)$ does not affect
the minimizer.

DP. This was shown by Banerjee2005 for $f,p\in\textrm{relint}(\Delta(A))$; we
show it generally below. Let $p\in\Delta(A)$; notice that
$\mathop{\mathds{E}}_{y\sim p^{n}}\bar{p}(y)=p$. Then, for all
$f\in\Delta(A)$,

$\displaystyle\mathop{\mathds{E}}_{y\sim p^{n}}L(f,y)$
$\displaystyle=\mathop{\mathds{E}}_{y\sim
p^{n}}[\nabla_{(B,dB)}(\bar{p}(y),f)+c(y)]$
$\displaystyle=\mathop{\mathds{E}}_{y\sim
p^{n}}c(y)+\mathop{\mathds{E}}_{y\sim
p^{n}}B(\bar{p}(y))-B(f)-\mathop{\mathds{E}}_{y\sim
p^{n}}(\bar{p}(y)-f)^{T}dB(f)$ $\displaystyle=\mathop{\mathds{E}}_{y\sim
p^{n}}c(y)+\mathop{\mathds{E}}_{y\sim
p^{n}}B(\bar{p}(y))-B(p)+B(p)-B(f)-(p-f)^{T}dB(f)$
$\displaystyle=\mathop{\mathds{E}}_{y\sim
p^{n}}c(y)+\mathop{\mathds{E}}_{y\sim
p^{n}}B(\bar{p}(y))-B(p)+\nabla_{(B,dB)}(p,f).$

The first three terms do not depend on $f$, and the final term is uniquely
minimized by $f=p$.

ZM. For any Bregman divergence, $\nabla_{(B,dB)}(\bar{p}(y),\bar{p}(y))=0$, so
if $c(y)=0$,

$L(\bar{p}(y),y)=\nabla_{(B,dB)}(\bar{p}(y),\bar{p}(y))+0=0.$

Ex. Let $\pi\in\Pi(\\{1,\ldots,n\\})$. Since $\bar{p}(y)=\bar{p}(\pi(y))$,
when $c(y)=0$,

$L(f,\pi(y))=\nabla_{(B,dB)}(\bar{p}(\pi(y)),f)=\nabla_{(B,dB)}(\bar{p}(y),f)=L(f,y).$

∎

##  Appendix B Proof of Theorem 3

We will now prove that every diagonal bounded Bregman divergences satisfies
all of our axioms.

First, recall the definition of a DBBD.

See 2

Note that while $b^{\prime}$ is not defined at 0, since $b$ is continuously
differentiable and convex, $b^{\prime}$ is monotonic and we can define
$b^{\prime}$ at the endpoints as the continuous extension, which we constrain
to be finite. For the remainder of this argument, we simplify
$\nabla_{(B_{b},\nabla B_{b})}$ to $\nabla_{B_{b}}$.

We are now ready to prove Theorem 3.

See 3

######  Proof 1.

Let $L$ be a DBBD, where $L(f,y)=\nabla_{B_{b}}(\bar{p}(y),f)$ for some $b$.
We establish that every such loss function satisfies each of our axioms in
turn.

SPA. We use the convexity of $b$ to prove that $L$ satisfies SPA. Here, note
that $L$ is bounded on $[0,1]$ due to continuity on $[0,1]$ and the bounded
first derivative of $b$.

Let $f,g\in\Delta(A)$, $y\in A^{n}$. Denote $\bar{p}=\bar{p}(y)$, and suppose
$f\succ_{\bar{p}}g$.

As $b$ is convex and differentiable on $[0,1]$, $b^{\prime}$ is increasing.

Let $1\leq a\leq d$, and suppose that $\bar{p}_{a}\leq f_{a}\leq g_{a}$. Then
$\bar{p}_{a}-f_{a}\leq 0$, and $b^{\prime}(f_{a})\leq b^{\prime}(g_{a})$.

Now suppose that $\bar{p}_{a}\geq f_{a}\geq g_{a}$. Then
$\bar{p}_{a}-f_{a}\geq 0$, and $b^{\prime}(f_{a})\geq b^{\prime}(g_{a})$.

In either case,
$(\bar{p}_{a}-f_{a})b^{\prime}(f_{a})\geq(\bar{p}_{a}-f_{a})b^{\prime}(g_{a})$.
Then

$\displaystyle L(g,y)-L(f,y)$
$\displaystyle=\nabla_{B_{b}}(\bar{p},g)-\nabla_{B_{b}}(\bar{p},f)$
$\displaystyle=B_{b}(\bar{p})-B_{b}(g)-(\bar{p}-g)^{T}\nabla B_{b}(g)$
$\displaystyle\quad-\left(B_{b}(\bar{p})-B_{b}(f)-(\bar{p}-f)^{T}\nabla
B_{b}(f)\right)$
$\displaystyle=\sum_{a=1}^{d}b(f_{a})-b(g_{a})+(\bar{p}_{a}-f_{a})b^{\prime}(f_{a})-(\bar{p}_{a}-g_{a})b^{\prime}(g_{a})$
$\displaystyle\geq\sum_{a=1}^{d}b(f_{a})-b(g_{a})+(\bar{p}_{a}-f_{a})b^{\prime}(g_{a})-(\bar{p}_{a}-g_{a})b^{\prime}(g_{a})$
$\displaystyle=\sum_{a=1}^{d}\nabla_{b}(g_{a},f_{a})$

For all $a$, $\nabla_{b}(g_{a},f_{a})\geq 0$. For some $\tilde{a}$,
$g_{\tilde{a}}\neq f_{\tilde{a}}$, so
$\nabla_{b}(g_{\tilde{a}},f_{\tilde{a}})>0$, and $L(g,y)-L(f,y)>0$.

DPA. Let $p\in\Delta(A)$ and notice that $\mathop{\mathds{E}}_{y\sim
p^{n}}\bar{p}(y)=p$.

For any $f,g\in\Delta(A)$,
$\nabla_{B_{b}}(\bar{p}(y),f)-\nabla_{B_{b}}(\bar{p}(y),g)$ is linear in
$\bar{p}(y)$ as the term $B_{b}(\bar{p}(y))$ in each cancels. Thus

$\mathop{\mathds{E}}_{y\sim p^{n}}L(f,y)-\mathop{\mathds{E}}_{y\sim
p^{n}}L(f,y)=\mathop{\mathds{E}}_{y\sim
p^{n}}\left[\nabla_{B_{b}}(\bar{p}(y),f)-\nabla_{B_{b}}(\bar{p}(y),g)\right]=\nabla_{B_{b}}(p,f)-\nabla_{B_{b}}(p,g).$

Thus if $f\succ_{p}g$, we can repeat the argument that $L$ satisfies SPA with
$\bar{p}$ replaced by $p$, and conclude that $\mathop{\mathds{E}}_{y\sim
p^{n}}L(f,y)-\mathop{\mathds{E}}_{y\sim p^{n}}L(g,y)>0$.

Ex. This follows from Theorem 2.

CPR. This argument follows a similar structure to the proof of SPA.

Let $n\in\mathbb{N}$, and $y,y^{\prime}\in A^{n}$. Let $f\in\Delta(A)$. Denote
$\bar{p}:=\bar{p}(y)$, $\bar{p}^{\prime}:=\bar{p}(y^{\prime})$, with
$\bar{p}\succ_{f}\bar{p}^{\prime}$.

As $b$ is convex and differentiable on $[0,1]$, $b^{\prime}$ is increasing.

Let $1\leq a\leq d$, and suppose that $\bar{p}_{a}^{\prime}\leq\bar{p}_{a}\leq
f_{a}$. Then we know that $\bar{p}_{a}^{\prime}-\bar{p}_{a}<0$, and
$b^{\prime}(f_{a})\geq b^{\prime}(\bar{p}_{a})$.

On the other hand, if $\bar{p}_{a}^{\prime}\geq\bar{p}_{a}\geq f_{a}$, then
$\bar{p}_{a}^{\prime}-\bar{p}_{a}>0$, but $b^{\prime}(f_{a})\leq
b^{\prime}(\bar{p}_{a})$.

Thus in both cases,
$(\bar{p}_{a}^{\prime}-\bar{p}_{a})b^{\prime}(f_{a})\leq(\bar{p}_{a}^{\prime}-\bar{p}_{a})b^{\prime}(\bar{p}_{a})$.
Then

$\displaystyle L(f,y^{\prime})-L(f,y)$
$\displaystyle=\nabla_{B_{b}}(\bar{p}^{\prime},f)-\nabla_{B_{b}}(\bar{p},f)$
$\displaystyle=B_{b}(\bar{p}^{\prime})-B_{b}(f)-(\bar{p}^{\prime}-f)^{T}\nabla
B_{b}(f)$
$\displaystyle\quad-\left(B_{b}(\bar{p})-B_{b}(f)-(\bar{p}-f)^{T}\nabla
B_{b}(f)\right)$
$\displaystyle=B_{b}(\bar{p}^{\prime})-B_{b}(\bar{p})-(\bar{p}^{\prime}-\bar{p})^{T}\nabla
B_{b}(f)$
$\displaystyle=\sum_{a=1}^{d}b(\bar{p}_{a}^{\prime})-b(\bar{p}_{a})-(\bar{p}_{a}^{\prime}-\bar{p}_{a})b^{\prime}(f_{a})$
$\displaystyle\geq\sum_{a=1}^{d}b(\bar{p}_{a}^{\prime})-b(\bar{p}_{a})-(\bar{p}_{a}^{\prime}-\bar{p}_{a})b^{\prime}(\bar{p}_{a})$
$\displaystyle=\sum_{a=1}^{d}\nabla_{d}(\bar{p}_{a}^{\prime},\bar{p}_{a}).$

For all $a$, $\nabla_{d}(\bar{p}_{a}^{\prime},\bar{p}_{a})\geq 0$, and for
some $\tilde{a}$, $\bar{p}_{\tilde{a}}\neq\bar{p}_{\tilde{a}}^{\prime}$, so
$\nabla_{d}(\bar{p}_{\tilde{a}}^{\prime},\bar{p}_{\tilde{a}})>0$. Thus
$L(f,y^{\prime})-L(f,y)>0.$

ZM. This also follows from Theorem 2.

##  Appendix C Proof of Section 5.5

For convenience, we restate the proposition here.

See 5.5

######  Proof 2.

We begin by showing that a scoring rule cannot satisfy both SPA and ZM.
Suppose $S$ is such a scoring rule; we will derive a contradiction. First, for
all $a\in A$, if $f\neq e_{a}$, SPA requires that
$S(f,a)=L_{S}(f,\\{a\\})>L_{S}(e_{a},\\{a\\})=S(e_{a},a)$. Second, for all
$a\in A$, ZM requires that $S(e_{a},a)=L_{S}(e_{a},\\{a\\})=0$. Then, for any
dataset $y$ such that $\bar{p}(y)$ has support on at least 2 elements, we have

$0=L_{S}(\bar{p}(y),y)=\sum_{a\in A}\bar{p}(y)_{a}S(\bar{p}(y),a)>\sum_{a\in
A}\bar{p}(y)_{a}S(e_{a},a)=0,$

a contradiction.

Now, we show that an arbitrary scoring rule does not satisfy CPR. Let $S$ be a
scoring rule. Suppose $y$ is a set of observations in which not all players
select the same action. Define $a^{*}$ to be an action in $A$ with the best
score, i.e.,

$a^{*}\in\arg\min_{a\in A}S(\bar{p}(y),a).$

Let $y^{\prime}$ be another set of observations of the same size where all
players play $a^{*}$. Then

$L_{S}(\bar{p}(y),y)=\sum_{a\in A}\bar{p}(y)_{a}S(\bar{p}(y),a)\geq
S(\bar{p}(y),a^{*})\sum_{a\in
A}\bar{p}(y)_{a}=S(\bar{p}(y),a^{*})=L_{S}(\bar{p}(y),y^{\prime}),$

but $\bar{p}(y)\succ_{\bar{p}(y)}\bar{p}(y^{\prime})$.

plainnat references