# Delegated Classification

Eden Saig
Department of Computer Science
Technion – Israel Institute of Technology
Haifa, Israel
<EMAIL_ADDRESS>Inbal Talgam-Cohen
Department of Computer Science
Technion – Israel Institute of Technology
Haifa, Israel
<EMAIL_ADDRESS>Nir Rosenfeld
Department of Computer Science
Technion – Israel Institute of Technology
Haifa, Israel
<EMAIL_ADDRESS>
###### Abstract

When machine learning is outsourced to a rational agent, conflicts of interest
might arise and severely impact predictive performance. In this work, we
propose a theoretical framework for incentive-aware delegation of machine
learning tasks. We model delegation as a principal-agent game, in which
accurate learning can be incentivized by the principal using performance-based
contracts. Adapting the economic theory of contract design to this setting, we
define _budget-optimal_ contracts and prove they take a simple threshold form
under reasonable assumptions. In the binary-action case, the optimality of
such contracts is shown to be equivalent to the classic Neyman-Pearson lemma,
establishing a formal connection between contract design and statistical
hypothesis testing. Empirically, we demonstrate that budget-optimal contracts
can be constructed using small-scale data, leveraging recent advances in the
study of learning curves and scaling laws. Performance and economic outcomes
are evaluated using synthetic and real-world classification tasks.

##  1 Introduction

The acclaimed success of machine learning at effectively solving difficult
prediction tasks across diverse problem domains has made it highly appealing
for firms, institutions, and individual practitioners. But machine learning
has also become increasingly complex, cumbersome, and difficult to operate—and
not all those who seek to learn have access to the necessary expertise,
infrastructure, and designated resources required for learning effectively.
This gap has created a new market for _outsourced machine learning_ , in which
a client interested in obtaining an accurate predictive model can hire the
services of a specialized provider which, for a price, trains the model on
their behalf. Consider for example a hospital purchasing a classifier for
deciding between hospitalization and outpatient treatment when triaging
patients. The provider invests in curating, cleaning and annotating training
data, and delivers a trained model in return to payment from the hospital.

Having a budget to expend on outsourced learning [45], we model the the client
as aiming to obtain the best possible predictive model. At first glance, it is
tempting to assume that the optimal strategy is simply to pay the provider the
maximal feasible amount—and hope to get a high-end model in return. After all,
if the client were to spend the budget directly on learning, investing the
maximal available sum would yield the best possible results. But this neglects
to account for the _incentives_ of the provider, who is interested in
maximizing profit. Since the actions of the provider remain private, it is in
his best interest to (secretly) minimize efforts, which in turn can result in
his delivering a suboptimally-trained model. In our example, the provider can
cut costs by annotating only a subset of the data, obtaining cheaper low-
quality annotations, or neglecting to meticulously remove all outliers.

Outsourced learning is hence susceptible to _moral hazard_ , an economic
situation which might occur under information asymmetry, and to the detriment
of the client. Motivated by this observation, in this paper we initiate the
study of _delegated learning_ , and aim to explore the economic, algorithmic,
and statistical implications that occur when learning is delegated to a
specialized provider. Our key novelty is in instantiating delegated learning
as a problem of _optimal contract design_ [7, 36, 41, 42]. Broadly, contracts
are an important monetary device that allows the client to establish a payment
scheme which, if properly set, serves to align incentives and guarantee that
both parties are well-off. Our main challenge is to design effective contracts
specialized to the task of delegated learning on a budget.

Towards this, we begin with a conventional supervised classification setup,
and impose economic structure by assuming that acquiring training examples is
costly. We then conceptually “split” the conventional self-sufficient learner
into two rational entities: a _principal_ , who controls the budget and is
interested in maximizing predictive accuracy; and an _agent_ , who controls
learning (in particular the training set) and is interested in maximizing
profit. This allows us to model principal-agent relations as a Stackelberg
game, in which the principal commits to a _contract_ $t$, determining _a
priori_ the amount to be paid for every possible (stochastic) level of
obtained accuracy. The agent best-responds to the contract by choosing the
profit-maximizing number of samples $n$, and training the predictive model.

Under this setting, we study the algorithmic problem of designing an optimal
contract. As is standard in economic analysis, we begin with the assumption
that the principal has full information on the distribution of possible
outcomes for each of the agent’s possible actions. In our setting, actions
correspond to the number of training samples, and outcomes to the empirical
classifier accuracy; thus, the main object of interest for contract design in
delegated learning settings is the _learning curve_ , which describes the
(stochastic) performance of learning per sample size. Under certain plausible
conditions on the learning curve, namely MLRP and a certain notion of
convexity, our main result here is that optimal contracts are _simple_ , and
in particular, take on the form of simple threshold functions. Simple
contracts are appealing because they are straightforward to understand and
communicate; in our setting, they are also easy to compute, and we give a
closed-form solution for the optimal threshold contract. Our results rely on
establishing a novel connection between contracts and the renowned Neymon-
Pearson lemma [39], which we view as our main theoretical contribution.

We then switch gears and turn to empirically studying the construction of
contracts from partial information. In particular, we consider a setting where
the principal can only estimate the learning curve from small available data
(e.g., by bootstrapping on small $n$ and extrapolating). Using the recent LCDB
dataset of learning curves [37], we show that threshold contracts generally
perform well on estimated curves despite the inherent uncertainty. We also
explore the role of different parameters of our setup, consider various
tradeoffs in curve-fitting and contract design, and discuss limitations by
pointing out certain failure modes to which contracts may be susceptible.

Taken together, our results shed light on why and how simple contracts for
delegated learning work to correctly balance between the incentives of both
delegator and delegatee in outsourced learning.

Figure 1:  Delegated classification interaction sequence. The principal
examines initial information, and designs a contract
$t:{\left\\{{0,\dots,m}\right\\}}\to\mathbb{R}_{\geq 0}$. Having observed $t$,
the agent strategically selects a dataset size $n$ that will maximize his
expected utility. He samples a training set $S\sim D^{n}$, incurs cost
$c_{n}$, then trains the classifier $h\in\mathcal{H}$ and sends it to the
principal. Upon receiving $h$, the principal evaluates its accuracy on a
random validation set $V\sim D^{m}$, and pays the agent according to the
contract $t$.

###  1.1 Related work

Previous works have considered delegation of ML-related tasks that differ from
our task of training a classifier: labeling of data points in [11], and
gathering information in [12]. The delegated task in [3] is computing a high-
dimensional function $f(x_{1},\dots,x_{n})$, where obtaining coordinates is
costly; by learning a single coordinate herself the principal can incentivize
correct computation of $f(x)$. The delegated task in [19] is the closest to
ours—the agent provides a classifier and the principal verifies its near-
optimality within $\mathcal{H}$. A fundamental difference is that their agent
is assumed to be adversarial rather than rational, and so interactive proofs
are used instead of economic incentives.

The Neyman-Pearson lemma has recently been connected to economic design by [5]
in the context of adverse selection rather than moral hazard. The agent has a
hidden type (e.g., whether a new drug is effective), and the optimal menu to
offer this agent is designed based on the theory of e-values. When the hidden
type has binary support, the method is equivalent to Neyman-Pearson. A “moral”
link between the design of contracts (for a non-budgeted principal) and
statistical inference (in particular likelihood ratios) was observed already
in [20], but no connection was made to the power of hypothesis tests. Other
intersections of ML and contracts that do not involve delegation of learning-
related tasks include strategic classification [e.g., 30, 31, 2] and online
learning of optimal contracts [23, 13, 46] Contract settings with a binary
action and/or outcome space have been studied in [e.g., 16, 4, 17]. Not to be
confused with our notion of delegation, there is a growing computational
literature on delegation without monetary payments [e.g., 29].

To extrapolate from partial data, our work builds upon recent advancements in
the study of learning curves, which characterize the expected generalization
of learning as a function of dataset size and other exogenous factors [43].
There is growing empirical evidence that performance of modern neural networks
can be predicted using simple scaling laws [e.g., 28, 35, 44, 18, 1, 40, 24],
and theoretical results that back these findings in simplified settings [8, 9,
27, 6].

##  2 Problem Setup

The core of our setting is based on a standard supervised classification task.
Let $x\in{\cal{X}}$ be features and $y\in{\cal{Y}}$ be labels, and assume
there is some unknown joint distribution $D$ over $(x,y)$ pairs. Given a
sample set $S=\\{(x_{i},y_{i})\\}_{i=1}^{n}\sim D^{n}$, the goal in learning
is to use $S$ to find a classifier $h$ from a class $\mathcal{H}$ that
maximizes expected accuracy, $\mathrm{acc}_{D}(h)=\mathbb{P}_{(x,y)\sim
D}{\left[{h(x)=y}\right]}$. Because the underlying distribution $D$ is
unknown, expected performance is estimated by the empirical average on an
additional held-out validation set $V\sim D^{m}$ of size $m$ as
$\mathrm{acc}_{V}(h)=\tfrac{1}{m}\sum_{i=1}^{m}\mathds{1}\left[{h(x_{i})=y_{i}}\right]$,
which is consistent and unbiased as an estimator of $\mathrm{acc}_{D}(h)$.
Throughout we will assume that the learning algorithm itself (i.e., which
prescribes how to obtain $h$ from $S$) is known and fixed.

##### Learning on a budget.

We will be interested in studying learning when certain resources are limited
or costly. Our main focus will be on the setting where the main cost of
learning is the number of labeled examples $n$, but we note that our approach
can in principle extend to other forms of learning ‘effort’.111For example,
[28] argue that not only training-set size, but also compute time and
architecture depth, are related to accuracy through scaling laws, which have
tight connections to the assumptions we discuss in Sec. 3. We assume the
learner has a monetary budget $B$ to spend on samples, and is interested in
maximizing accuracy under budget constraints. Let $c_{n}\geq 0$ be the cost of
$n$ samples (assumed to be increasing in $n$), then the learner aims to solve:

$n^{*}=\operatorname*{argmax}\nolimits_{n}\mathbb{E}_{h_{n}}[\mathrm{acc}_{D}(h_{n})]\quad\text{s.t.}\quad
c_{n}\leq B$ (1)

where $h_{n}$ is the classifier learned from a random dataset of size $|S|=n$.
We denote $\alpha_{n}=\mathrm{acc}_{D}(h_{n})$, and note that $\alpha_{n}$ is
a random variable, as is $h_{n}$ itself. When the learner is a self-sufficient
entity, and when $\alpha_{n}$ improves monotonically in $n$, then Eq. (1)
admits a trivial solution as the largest affordable $n$.

##### Delegation.

We model the delegation of learning as a conceptual “split” of the learner
into two distinct entities: an _agent_ , who controls learning; and a
_principal_ , who controls the validation process. The principal outsources
the learning task to the agent, who in turn uses the training set $S$ to train
the classifier $h$; once delivered, the principal validates the performance of
$h$ using the validation set $V$. Whereas the classifier’s accuracy benefits
the principal alone, the cost of learning (i.e., the cost of acquiring $S$) is
born exclusively by the agent. Importantly, the amount of invested effort
remains private to the agent; in our example, the principal cannot now how
many examples received quality labeling. Because the agent seeks to maximize
profit, the principal can use her budget as a source of monetary payment to
incentivize the agent to invest in larger $|S|=n$. Intuitively, one could
expect larger payments to entail larger $n$, and therefore higher-accuracy
$h$. However, as we will see, this is not always the case, and careful
planning is required in order to fully utilize a given budget.

###  2.1 Delegation as contract design

As the training set remains private to the agent, there is an information gap
between the two parties. This creates a conflict of interest for the agent
known as _moral hazard_ [7], in which the agent may be tempted to invest sub-
par effort, while claiming that efforts were in fact his honest best. In
economics, the celebrated solution to moral hazard are _contracts_ : pay-per-
performance rules that a-priory determine future payments for every possible
outcome, which we formally describe next [25].

##### Contract design.

A contract setting is defined by a set of actions
$\mathcal{A}={\left\\{{a_{1},\dots,a_{N}}\right\\}}$ that can be taken by the
agent, and a set of possible outcomes $j=\\{0,\dots,m\\}$. Each action $a_{i}$
is associated with a cost $c_{i}$, and w.l.o.g. we assume $c_{1}\leq\dots\leq
c_{N}$ so that actions correspond to increasing _effort levels_. The agent’s
choice to perform action $a\in\mathcal{A}$ yields a random outcome $j\sim
f_{a}$ for the principal, where $f_{a}$ describes a distribution over the
possible outcomes associated with action $a$. The principal, who does not
observe the agent’s chosen action, can incentivize the agent through a
_contract_ , $t:{\left\\{{0,\dots,m}\right\\}}\to\mathbb{R}_{\geq 0}$,
according to which she pays the agent $t(j)\geq 0$ when the materialized
outcome is $j$. Given contract $t$, let $u_{a}(t)$ be the agent’s expected
_utility_ from taking action $a\in\mathcal{A}$ at cost $c_{a}$ (via stochastic
outcomes $j\sim f_{a}$), and let $a(t)$ be the agent’s _best response_ —an
action that maximizes his expected utility (and following standard tie-
breaking assumptions as in [14]). Then:

$\displaystyle u_{a}(t)=\mathbb{E}_{j\sim
f_{n}}{\left[{t(j)}\right]}-c_{a},\qquad\qquad
a(t)\in\mathrm{argmax}_{a\in\mathcal{A}}u_{a}(t).$ (2)

Every action $a^{*}$ that is the best response $a^{*}=a(t)$ to some contract
$t$ is called _implementable_. In economic terms, the principal and agent are
playing a _Stackelberg game_ , in which the principal commits to a contract
$t$ and the agent best-responds by choosing action $a(t)$ that maximizes his
expected utility $u_{a}(t)$. The goal of the principal is to design a contract
$t$ which incentivizes the agent to take best-response actions yielding
favorable outcomes for the principal.

##### Contracts for delegated learning.

We propose to formulate delegated learning as a problem of optimal contract
design, instantiated as follows. First, we relate agent actions $a$ with the
number of samples $n$, and denote $\mathcal{A}=\\{n_{1},\dots,n_{N}\\}$ as the
possible sizes of $S$ that the learning agent can work with. The cost of
acquiring samples naturally maps as $c_{a}=c_{n}$. Next, we associate outcomes
$j$ with accuracy for the principal by defining $j$ as the number of
validation samples (out of the possible $m$) on which $h$ is correct; note
this implies $\mathrm{acc}_{V}(h)=j/m$, and we will therefore use $j$ and
$\mathrm{acc}_{V}(h)$ as ‘outcomes’ interchangeably. Finally, for an action
$n$, we set $f_{n}$ to be the distribution over possible accuracies obtained
when learning with $n$ samples, namely
$f_{n}(j)=P(\mathrm{acc}_{V}(h_{n})=j/m)\,\,\forall j$. We will also use the
matrix form $F_{nj}=f_{n}(j)$, where $F\in[0,1]^{N\times(m+1)}$. Note $F$
admits two sources of variation: (i) _a-priori_ variation in $h_{n}$ due to
stochasticity in $S\sim D^{n}$; and (ii) _a-posteriori_ variation in $j$ for
any fixed $h_{n}$ due to stochasticity in $V\sim D^{m}$. Note also that given
$h_{n}$, the latter admits a simple binomial form, namely
$j\sim\mathrm{Binomial}(m,\alpha_{n})$; empirically we observe this to be the
dominant component.

###  2.2 Delegation as an optimization problem

Recall that our principal seeks to maximize accuracy under budget constraints
(Eq. (1)). Once learning is delegated to an agent, and framed as a contract
design problem, the principal’s objective becomes:

$t^{*}=\operatorname*{argmax}\nolimits_{t\in[0,B]^{m}}\mathbb{E}_{h_{n(t)}}[\mathrm{acc}_{D}(h_{n(t)})]$
(3)

Contract $t^{*}$ is chosen to incentivize the agent to invest effort $n(t)$
(via eq. 2) such that the training of $h_{n(t)}$ yields high dividends for the
principal in terms of expected accuracy. We will refer to $t^{*}$ as a
_budget-optimal contract_ , and to the general task of finding $t^{*}$ as
_budget-optimal contract design_.

##### Information structure.

Borrowing from contract theory, in a delegated learning setting actions
$\mathcal{A}$ and costs ${\left\\{{c_{n}}\right\\}}$ are known to both sides,
and the outcome distributions ${\left\\{{f_{n}}\right\\}}$ are known to the
agent. For the principal, we explore varying levels of knowledge: In Sec. 3,
we assume (as in the classic contract design literature) that the principal
has full information of $F$ (i.e., knows the learning curve), and focus on
characterizing the optimal contract. In Sec. 4 we relax this assumption, and
explore a partial-information setting in which the principal relies instead on
an empirically-estimated curves $\hat{F}$.

Figure 2:  A delegated classification setting (data from Sec. 4). (Left) Each
costly action taken by the agent (training set size $n$) induces a
distribution $f_{n}$ of possible outcomes (classifier accuracy). The principal
seeks to construct a contract $t$ that incentivizes a profit-maximizing agent
to take actions entailing favorable outcomes. Note the $f_{n}$ exhibit
increasing expectation, but decreasing variance, in $n$. (Center) Three
contracts for a given budget $B$, mapping outcomes to payments. (Top-right)
Agent’s utilities $u_{n}(t)$ and best responses $n(t)$ (stars) for each
contract $t$. (Bottom-right) Expected accuracies for principal resulting from
each contract; here the threshold contract is optimal (see Sec. 3).

##  3 Budget-optimal Contracts

We now turn to present our approach for solving budget-optimal contracts,
beginning with challenges.

##### Why agents cut corners.

The conceptual challenge in designing contracts lies in that agents cannot
reliably report _what_ they did. For example, consider a principal that, after
delegation, received a classifier attaining 0.74 (validation) accuracy. Should
she be happy? The crux is that there are two ways that this could have
happened: (i) the agent invested high effort in learning (large $n$), but (by
chance) received an uninformative $S$, and as a result, delivered a low-
quality $h$; and (ii) the agent invested low effort (small $n$). Because the
agent’s actions are private, and because outcomes are stochastic, the
principal can never know for certain which is the true underlying cause. In
other words, a ‘lazy’ (or rather rational) agent can hide behind the
uncertainty that is inherent in learning outcomes.222The agent can also hide
in the uncertainty due to $V$, particularly when $m$ is small; see experiment
in Sec. 4.2.

##### Contract examples.

To overcome this informational gap, the principal can devise a contract to
align incentives and encourage the agent to prefer certain actions over
others. But not all contracts are equally effective. Fig. 2 illustrates for a
budget $B$ three contract types and their economic implications:

  * •

Constant contract ($t(j)={B}$): The agent is paid ${B}$ regardless of the
outcome. His best-response in this case is to choose the least-costly
action—to the detriment of the principal.

  * •

Linear contract ($t(j)={B}j/m$): The agent is paid a fraction of ${B}$, linear
in the resulting accuracy. Linear contracts are a popular and extensively-
studied class of contracts [e.g., 26]. Nonetheless, and though seemingly
sensible, linear contracts turn out to be sub-optimal for our setting.

  * •

Threshold contract ($t(j)={B}\mathds{1}\left[{j\geq j_{0}}\right]$ for some
$j_{0}$): The agent is paid ${B}$ provided the empirical accuracy surpasses a
threshold $j_{0}$. In this example, the threshold contract is optimal.

Rather than committing _a priori_ to some parametric form of contract, we seek
to find the best budget-optimal contract by rigorously solving Eq. (3). This,
however, requires _structure_.

##### Stochastic learning curves (and where to find them).

Our approach relies on the observation that there is a tight connection
between the set of distributions $\\{f_{n}\\}$ encoded in $F$, and _learning
curves_ , which describe the anticipated accuracy of a classifier as a
function of the size of its training set. Learning curves typically depict
only expected accuracy, but there is also inherent variation in outcomes. We
will therefore broadly use the term ‘stochastic learning curve’ to describe
both mean trend _and_ variation in accuracy as a function of $n$; formally, a
stochastic learning curve is defined precisely by $F$. This connection is
useful because learning curves have structure: First, learning curves are
typically _monotone_ [28, 8]; when not [37, 43], they can be monotonized [9].
Second, stochastic learning curves are likely to satisfy the _monotone
likelihood ratio property_ (MLRP), which states that expected accuracy
increases, but variance decreases, with $n$; this holds in particular under
the Binomial distribution [15, B.1]. MLRP has proved useful in contract theory
[21], and will be key for us as well.

###  3.1 Optimizing (simple) contracts

Our main technique relies on a reduction to what we refer to as _min-budget
contracts_. Given an (implementable) target action $n^{*}\in\mathcal{A}$, a
min-budget contract for $n^{*}$ is a contract $t$ that incentivizes the agent
to employ precisely the action $n^{*}$, while minimizing the maximum payment
$\left\lVert{t}\right\rVert_{\infty}=\max_{j\in{\left\\{{0,\dots,m}\right\\}}}\\{t(j)\\}$
by the principal; i.e., $t$ implements $n^{*}$ at minimum budget. Formally:

$t^{*}=\operatorname*{argmin}\nolimits_{t}\left\lVert{t}\right\rVert_{\infty}\quad\text{s.t.}\quad
n(t)=n^{*}$ (4)

When the learning curve is monotone, and given a budget $B$, to find the
_budget-optimal_ contract it suffices to identify the maximum implementable
$n\in\mathcal{A}$ for which the _min-budget_ contract has payments bounded by
$B$. The budget-optimal problem thus reduces to multiple min-budget (and
implementability) problems. Our approach will therefore be to solve Equation 3
by a series of calls to a solver for Equation 4. Correctness holds due to the
following claim (proof in Section B.1):

######  Proposition 1.

There always exists a budget-optimal contract which is min-budget.

Solving Eq. (4) can be done by linear programming (LP)—see Appx. B.2 for the
MIN-BUDGET LP. 333The MIN-BUDGET LP is closely related to the well-known MIN-
PAY LP from non-budgeted contract design [e.g., 15], but with a different
objective, and hence very different optimal solutions (see Section B.3).  The
LP approach is valid but can be costly. One of our contributions is in
identifying natural cases where min-budget contracts take on _simple_ forms,
which are easier to optimize, and have practical merit. In particular, we will
show that plausible structural assumptions on the learning curve give rise to
_threshold_ contracts, namely $t(j)={B}\mathds{1}\left[{j\geq j_{0}}\right]$
for some $j_{0}$, which are a special case of _all-or-nothing_ contracts
having $t(j)\in\\{0,B\\}$. Our theoretical results are summarized in Table 1.

Table 1:  Characterization of simple min-budget contracts under different assumptions. Simple contract forms include all-or-nothing contracts and (under MLRP) their subclass of threshold contracts. The table specifies for each configuration either the simple form that is optimal (in one case through equivalence to the Neyman-Pearson lemma), or that the simple form is non-optimal or intractable.  Problem size | Structural assumptions
---|---
Actions | Outcomes | No assumptions | MLRP | MLRP + Concave
${\left|{\mathcal{A}}\right|}=2$ | any size | Neyman-Pearson (T1) | Threshold (B.6.1)
${\left|{\mathcal{A}}\right|}>2$ | $m+1=2$ | All-or-nothing (B.5.1) | Threshold (B.6.2)
$m+1>2$ | NP-hard (T2) |  $\exists$ non-threshold (B.6.3) | Threshold (T3)

###  3.2 Simple min-budget contracts for binary action space

We begin with a simple binary-action delegated learning setting where the
agent can choose one of two actions,
$\mathcal{A}={\left\\{{n_{1},n_{2}}\right\\}}$, e.g., a ‘small’ vs. ‘large’
training set. This reduced case will be useful for making a precise connection
between contract design and statistical inference, and as a building block to
be used when returning to the general-action setting in Sec. 3.3. We focus
throughout on the interesting case in which the principal wishes to
incentivize $n_{N}$, which is implementable.444For $N=2$, when $n_{2}$ is not
the target or when is not implementable, then the solution is immediate:
always pay $c_{1}$. For $N>2$, given a monotone learning curve the focus on
implementable $n_{N}$ is again without loss. We thus refer to the min-budget
contract for $n_{N}$ as the _optimal contract_. Our main result in this
section is characterizing the optimal contract as an all-or-nothing contract
whose budget is determined by the distance between $f_{1},f_{2}$ (see
Proposition 2), and establishing its equivalence (in Theorem 1) to the optimal
_hypothesis test_ according to the Neyman-Pearson lemma (Lemma 1).

##### Contracts and tests.

Towards establishing our result, we first develop intuition: Given the outcome
distributions ${\left\\{{f_{1},f_{2}}\right\\}}$, in order to incentivize
$n_{2}$ the principal would ideally like to design a contract that pays the
agent if the observed outcome $j\in{\left\\{{0,\dots,m}\right\\}}$ originates
from $f_{2}$. The principal can attempt to identify whether the outcome $j$ is
drawn from distribution $f_{1}$ or $f_{2}$ through hypothesis testing, where a
hypothesis test $\psi:{\left\\{{0,\dots,m}\right\\}}\to\\{0,1\\}$ maps a
sample $j$ to either $f_{2}$ (indicated by 1) or to the null hypothesis
$f_{1}$ (indicated by 0). For our purpose it is convenient to allow tests to
be non-integral, in which case $\psi:{\left\\{{0,\dots,m}\right\\}}\to[0,1]$
maps $j$ to a _probability_ with which it originates from $f_{2}$. The quality
of a hypothesis test is measured by summing its type-1 and type-2 errors:
$\sum_{j=0}^{m}f_{1}\psi_{j}+\sum_{j=0}^{m}f_{2}(1-\psi_{j})$. The test that
minimizes this sum is known as the _maximum power_ hypothesis test, and has
been characterized by Neyman and Pearson [39, 4.3].

The following theorem establishes the connection between the optimal contract
and the most powerful hypothesis test. For a fixed $B$, observe that every
contract with budget $B$ can be mapped to a hypothesis test via the bijection
$\psi(j)=\nicefrac{{t(j)}}{{B}}$. Then:

######  Theorem 1 (Optimal contract vs. test).

Consider binary-action delegated learning with distributions $f_{1},f_{2}$ and
costs $c_{1},c_{2}$. A contract $t$ with budget $B$ is optimal if and only if
its corresponding hypothesis test $\psi=\nicefrac{{t}}{{B}}$ is maximum power
with type-1 and type-2 errors summing to $1-\frac{c_{2}-c_{1}}{B}$.

The proof (Section B.4.2) is by a non-linear variable transformation to MIN-
BUDGET LP.

##### All or nothing.

Theorem 1 immediately implies that the following characterization of the
optimal contract for the binary-action case (Proposition 2) is equivalent to
the well-known Neyman-Pearson lemma characterizing the most powerful
hypothesis test (Lemma 1). To state these two results, let
$\left\lVert{{f_{2}}-{f_{1}}}\right\rVert_{\mathrm{TV}}$ denote the _total
variation distance_ between $f_{2}$ and $f_{1}$, namely
$\tfrac{1}{2}\sum_{j=0}^{m}{\left|{f_{2,j}-f_{1,j}}\right|}$.

######  Proposition 2 (Optimal contract for binary-action).

Consider a binary-action delegated learning setting with distributions
$f_{1},f_{2}$ and costs $c_{1},c_{2}$. The optimal contract is an all-or-
nothing contract given by
$B=\nicefrac{{(c_{2}-c_{1})}}{{\left\lVert{{f_{2}}-{f_{1}}}\right\rVert_{\mathrm{TV}}}}$
and $t^{*}(j)=B\mathds{1}\left[{f_{2}(j)\geq f_{1}(j)}\right]$ for all
$j\in{\left\\{{0,\dots,m}\right\\}}$.

######  Lemma 1 (Neyman-Pearson [e.g., 39]).

Let $f_{1},f_{2}$ be two discrete probability distributions. Then the most
powerful hypothesis test for $f_{1},f_{2}$ is the likelihood ratio test
$\psi(j)=\mathds{1}\left[{f_{2}(j)\geq f_{1}(j)}\right]$, which attains the
optimal bound $1-\left\lVert{{p}-{q}}\right\rVert_{\mathrm{TV}}$ on type-1 and
type-2 errors.

The optimal contract pays the agent for outcomes that are more likely to come
from $f_{2}$ than from $f_{1}$. Moreover, the optimal contract (resp.,
hypothesis test) has a higher budget (resp., sum of errors) the smaller the
distance is between the two distributions $f_{1},f_{2}$. At the extremes, if
their distance is 1 (no overlap among their supports), the required budget for
incentivizing $n_{2}$ is $c_{2}-c_{1}$ (the sum of errors is zero), whereas if
their distance is 0 it becomes infeasible to incentivize $n_{2}$ (the sum of
errors is one). Note that Proposition 2 can also be proved directly using LP
duality (Section B.4.1).

##### Thresholds.

As the optimal contract is based on the likelihood ratio test, it is natural
to add to our binary-action setting the MLRP assumption of increasing
likelihood ratio: If $j^{\prime}>j$ then
$\nicefrac{{f_{2}(j^{\prime})}}{{f_{1}(j^{\prime})}}\geq\nicefrac{{f_{2}(j)}}{{f_{1}(j)}}$.
The intuition behind the MLRP assumption is that the better the evaluation
result of the classifier, the more likely it was trained using more data.
Under the MLRP assumption, $n_{2}$ is always implementable, 555As a corollary
of a similar result for min-pay contracts [15, Lemma 7]. and the optimal
contract assumes a _threshold_ form. This is by Proposition 2 and the fact
that $\exists j_{0}$ such that $f_{2}(j)/f_{1}(j)\geq 1$ iff $j\geq j_{0}$
(see also Section B.6.1). Interestingly, this is similar to the relation
between the Neyman-Pearson lemma and the Karlin-Rubin theorem, which
characterizes the most powerful hypothesis test under monotone likelihood
ratio [34].

###  3.3 Beyond binary action space

For the important special case of binary-outcome space, even with more than
two actions, the results of Sec. 3.2 largely hold: the optimal contract is
again all-or-nothing, and with MLRP it becomes a threshold contract (proofs in
Appx. B.5.1 and Appx. B.6.2). However, for a general number of actions and
outcomes, this no longer holds. The optimal contract is not guaranteed to be
all-or-nothing, and in fact the problem of determining whether there exists an
all-or-nothing contract that is optimal is NP-hard:

######  Theorem 2 (Hardness).

Consider a delegated learning setting with $N$ actions in which action $a_{N}$
is implementable. Finding the budget-minimizing all-or-nothing contract for
action $a_{N}$ is NP-hard.

The proof is by reduction from 3SAT and appears in Section B.5.2. Also, simple
contracts are not guaranteed even under the MLRP assumption. In Section B.6.3,
we construct an explicit setting satisfying MLRP, for which no optimal
contract of threshold form exists. Scrutinizing the counterexample identifies
the source of failure that differentiates this case from that of binary
action: Consider for each action $n_{i}$ where $i<N$ the crossing point
$j_{i}^{*}=j^{*}_{f_{i},f_{i-1}}$ at which action $n_{i}$ becomes more likely
than $n_{i-1}$. In the counterexample, the survival probability
$\mathbb{S}_{i}(j_{i}^{*})=\mathbb{P}_{f_{i}}{\left[{j>j_{i^{*}}}\right]}$ is
not concave. Interestingly, _requiring_ concavity at this point is sufficient.

######  Theorem 3 (Sufficiency for threshold).

Consider delegated learning with MLRP and a concave survival function at the
crossing point $j_{i}^{*}$. Then the optimal contract is a threshold contract.

We prove this claim by showing that concavity implies that only one constraint
is binding in the linear program equivalent to eq. 4, reducing the problem to
the two-action case. By applying proposition 2, we obtain optimality of
threshold contracts in this case as well (proof in Section B.6.3).

##  4 Experiments

We now turn to our empirical investigation of delegated learning under full
and partial information. We base our experiments on the recently curated
Learning Curves Database(LCDB) [37], which includes a large collection of
stochastic learning curves for multiple classification datasets and methods.
For each dataset and method, the database includes held-out accuracy
measurements obtained for increasing sample sizes
$n\in{\left\\{{2^{4},2^{4.5},\dots,2^{15}}\right\\}}$, with multiple
repetitions per $n$; these provide us with stochastic learning curves. Here we
focus primarily on the popular MNIST dataset [33] as our case study, and on
MLP and GBDT as representative classifiers, but we refer the reader to Appx. C
for further experiments on additional datasets and methods. Code is available
at: https://github.com/edensaig/delegated-classification.

###  4.1 Full information

We begin with the full information setting to explore in a clean environment
how different parameters of the learning setting and environment affect
predictive performance and economic outcomes.

Figure 3:  Delegating with full information. (Left) Typical learning curves
for two methods on MNIST. (Center) Required budget for target accuracy of
$0.85{}$ per validation set size $m$. (Right) Different cost regimes,
indicating per accuracy region which of the two methods is cheaper to
delegate.

##### Validation set size.

Fig. 3 (left) presents typical stochastic learning curves for two methods:
Multi-Layered Perceptron (MLP) and Gradient-Boosted Decision Trees (GBDT). We
take an arbitrary accuracy point on the curve at $\mathrm{acc}(n)=0.85{}$
(dotted line) to examine the effects of validation set size $m$ on min-budget
contracts. Notice that MLP requires larger $n$ to obtain 0.85; Fig. 3 (center)
shows how this translates to a larger required budget $B^{*}$, which holds for
all $m$. As $m$ increases, required budgets Larger validation sets are
therefore useful for reducing required budget. Nonetheless, even for
reasonable $m$, obtained budgets still remain higher than their theoretical
lower bounds (dotted lines). In terms of compute, we were able to execute the
full LP solver only up to $m\leq 20$; in contrast, the local solver is easy to
run for larger $m$, and for small $m$ gives solutions that coincide with the
full solver.

##### Budget regimes.

Fig. 3 (left) also indicates two points in which the learning curves cross
(dashed lines), at ${\sim}0.74{}$ and ${\sim}0.94{}$ accuracy. These
correspond to sample sizes $n$ for which both methods obtain matching
accuracies (in expectation). For a self-sufficient learner, the implication is
that at each of these points, both methods are equally costly, i.e., both cost
$c_{n}$. Interestingly, and in contrast, delegation can entail different
required budgets _despite_ equal accuracies. Fig. 3 (right) shows for each
target accuracy the gap in required budgets between both methods, $\Delta
B^{*}=B^{*}_{\textsc{gbdt}}-B^{*}_{\textsc{mlp}}$. As can be seen, each method
is comparatively more (or less) costly in different accuracy regimes (up to
0.6; between 0.6 and 0.92; and above 0.92). Crucially, the budget gap can be
large even when accuracies match (dashed lines). For example, even though both
MLP and GBDT require $n{=}362{}{\approx}2^{17{}/2}$ samples to obtain
${\sim}0.74{}$ accuracy, GBDT is cheaper ($\Delta B^{*}{=}-10^{2}$); for $\sim
0.94{}$ which requires $n{=}23170{}{\approx}2^{29{}/2}$ from both, GBDT is
significantly more expensive ($\Delta B^{*}{=}10^{5}$). The reason for this is
that optimal budgets are determined by the ability to distinguish between
distributions (Sec. 3.2).

###  4.2 Partial information

We now turn to consider delegation under partial information, in which the
principal must rely on an estimated learning curve. We instantiate this idea
by assuming that the principal has access to a small ‘pilot’ dataset of size
$k$, where $k$ is considered small. Using this set, the principal creates an
estimated learning curve $\hat{F}$ by fitting a curve to accuracies obtained
for up to some $n_{0}\leq k$, and extrapolating to larger $n>n_{0}$. In
particular, we experiment with fitting parametric power-law curves of the form
$\mathbb{E}{\left[{\alpha_{n}}\right]}=a-bn^{-c}$, which have been shown to
provide good fit in various scenarios both empirically and theoretically [43,
28, 8]. Since power-law curves are monotone, composition with binomial
distributions increasing in $p$ provably results in MLRP stochastic curves
[15, B.1].

Figure 4:  Delegating with partial information. (Left) Extrapolated learning
curves for different $r$. (Center-left) Accuracy obtained via delegation per
pilot set size $k$. (Center-right) Multiplicative gain in effective number of
samples due to delegation. (Right) Implications of over vs. under-estimation.

##### Bias-variance tradeoff.

Given $k$ pilot examples, there are different ways in which the principal can
use them to construct an estimated curve. Here we consider a simple tradeoff:
setting $n_{0}$ to be small but with more samples per $n<n_{0}$ (low
variance), or setting $n_{0}$ to be large but with few samples per $n<n_{0}$
(low bias). We define $r$ as the number of samples per $n$ (so low $r$ means
larger $n_{0}$). Then, for a given $r$, we set $n_{0}$ such that $\sum_{n\leq
n_{0}}r\cdot n\leq k$ (i.e., such that the total number of used samples does
not exceed $k$). Fig. 4 (left) shows different curve fits for $r=1,3,5$, and
corresponding $n_{0}$. Then, Fig. 4 (center-left) shows for a certain fixed
budget the accuracy level that can be attained for increasing $k$, and as a
function of $r$. As can be seen, having sufficient points $k$ for constructing
$\hat{F}$ is important, but performance grows quickly with $k$ (note log-scale
x-axis). It is also apparent in our example that low bias (via larger $n_{0}$)
is much more important than low variance for constructing useful $\hat{F}$.

##### Cost-efficiency tradeoff.

Because the pilot set provides the principal a basic means for obtaining
minimal accuracy, we can ask: given $k$ examples, and for a fixed budget $B$,
what is the added benefit of delegating learning? For this, we define
$\mu(k)=n(\hat{t})/k$ to be the _sample-size multiplier_ , i.e., the
multiplicative gain in the effective number of samples due to delegation. Fig.
4 (center-right) shows $\mu(k)$ for increasing $k$ and across $r$. For $r=1$
(which is superior in terms of performance and outcomes), $\mu$ begins at
${\sim}10$, increases to ${\sim}30$ at around $k=190{}$, and slowly decreases
back to ${\sim}10$ towards $k=1,000$. For $r>1$, we observe that $\mu\approx
1$, i.e., there is effectively no gain from delegation, until around $k=100$,
only after which some gain is restored. This highlights the importance of
obtaining an accurate estimate $\hat{F}$ in terms of the economic consequences
of delegation.

##### Over vs. under-estimation.

Typically in curve-fitting, over and under-estimation are treated equally,
since both types of error can negatively affect goodness of fit and
extrapolation quality. However, for delegation, the implications of over vs.
under-estimation on contract outcomes are highly asymmetric. Fig. 4 (right)
shows for a target incentivized number of samples $n(t^{*})$ the relation
between the (theoretical) _signed_ extrapolation error $n(t^{*})$ (i.e., over-
or under-fit, measured in accuracy points) and the eventual loss in accuracy
obtained through delegation, relative to perfect estimation. Each point in the
plot corresponds to one curve-fitting instance, with points shown for varying
$k$, $n_{0}$, and $r$, and with multiple independent repetitions. Results show
that in the under-fitting regime (i.e., _negative_ extrapolation error), loss
in accuracy degrades gracefully with the estimation error . In stark contrast,
even minimal over-fitting (_positive_ extrapolation error) causes accuracy to
plummet dramatically.This has important implications for the choice of how to
fit and extrapolate learning curves, suggesting that contracts can be tolerant
to under-estimation, while over-estimation should be avoided at all costs.

##  5 Discussion

Motivated by the increasingly-common practice of outsourcing learning tasks,
this paper sets out to introduce and study the novel problem of delegated
classification. Our findings suggest that conflict of interests should not be
overlooked, and that contracts hold potential as a means for aligning them.
Our analysis relies on a set of assumptions, which should be carefully
considered by practitioners and empiricists alike; we also believe that there
are likely further fruitful connections to explore between contracts and
statistical hypothesis testing. As a problem of contract design, and when the
learning task is reasonably well-behaved, delegated learning manifests in the
form simple threshold contracts. A natural question for future work is whether
simplicity also implies _robustness_ —as is often the case [15].

##### Acknowledgements.

The authors would like to thank Ruth Heller, Shafi Goldwasser, Jonathan
Shafer, and Ohad Einav for their insightful remarks and valuable suggestions.
Nir Rosenfeld is supported by the Israel Science Foundation grant no. 278/22.
Eden Saig is supported by the Israel Council for Higher Education PBC
scholarship for Ph.D. students in data science. Funded by the European Union
(ERC, ALGOCONTRACT, 101077862, PI: Inbal Talgam-Cohen).

## References

  * Alabdulmohsin et al. [2022] Ibrahim Alabdulmohsin, Behnam Neyshabur, and Xiaohua Zhai.  Revisiting neural scaling laws in language and vision.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.
  * Alon et al. [2020] Tal Alon, Magdalen Dobson, Ariel D. Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz.  Multiagent evaluation mechanisms.  In _AAAI 2020_ , pages 1774–1781, 2020.
  * Azar and Micali [2018] Pablo D Azar and Silvio Micali.  Computational principal–agent problems.  _Theoretical Economics_ , 13(2):553–578, 2018\.
  * Babaioff et al. [2012] Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter.  Combinatorial agency.  _Journal of Economic Theory_ , 147(3):999–1034, 2012.
  * Bates et al. [2022] Stephen Bates, Michael I Jordan, Michael Sklar, and Jake A Soloff.  Principal-agent hypothesis testing.  _arXiv preprint arXiv:2205.06812_ , 2022.
  * Bisla et al. [2021] Devansh Bisla, Apoorva Nandini Saridena, and Anna Choromanska.  A theoretical-empirical approach to estimating sample complexity of dnns.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 3270–3280, 2021.
  * Bolton and Dewatripont [2004] Patrick Bolton and Mathias Dewatripont.  _Contract theory_.  MIT press, 2004.
  * Bousquet et al. [2021] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff.  A theory of universal learning.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 532–541, 2021.
  * Bousquet et al. [2022] Olivier J Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, and Uri Stemmer.  Monotone learning.  In _Conference on Learning Theory_ , pages 842–866. PMLR, 2022.
  * Bynum et al. [2021] Michael L. Bynum, Gabriel A. Hackebeil, William E. Hart, Carl D. Laird, Bethany L. Nicholson, John D. Siirola, Jean-Paul Watson, and David L. Woodruff.  _Pyomo–optimization modeling in python_ , volume 67.  Springer Science & Business Media, third edition, 2021.
  * Cai et al. [2015] Yang Cai, Constantinos Daskalakis, and Christos H. Papadimitriou.  Optimum statistical estimation with strategic data sources.  In _COLT 2015_ , pages 280–296, 2015.
  * Chen et al. [2022] Junjie Chen, Minming Li, and Haifeng Xu.  Selling data to a machine learner: Pricing via costly signaling.  In _International Conference on Machine Learning_ , pages 3336–3359. PMLR, 2022.
  * Cohen et al. [2022] Alon Cohen, Argyrios Deligkas, and Moran Koren.  Learning approximately optimal contracts.  In _SAGT 2022_ , pages 331–346, 2022.
  * Dütting et al. [2019] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen.  Simple versus optimal contracts.  In _EC 2019_ , pages 369–387, 2019.
  * Dütting et al. [2019] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen.  Simple versus optimal contracts.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 369–387, 2019.
  * Dütting et al. [2021] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim.  Combinatorial contracts.  In _FOCS 2021_ , pages 815–826, 2021.
  * Dütting et al. [2023] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim.  Multi-agent contracts.  In _STOC 2023_ , 2023.  To appear.
  * Ghorbani et al. [2021] Behrooz Ghorbani, Orhan Firat, Markus Freitag, Ankur Bapna, Maxim Krikun, Xavier Garcia, Ciprian Chelba, and Colin Cherry.  Scaling laws for neural machine translation.  _arXiv preprint arXiv:2109.07740_ , 2021.
  * Goldwasser et al. [2021] Shafi Goldwasser, Guy N Rothblum, Jonathan Shafer, and Amir Yehudayoff.  Interactive proofs for verifying machine learning.  In _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * Grossman and Hart [1983] Sanford J. Grossman and Oliver D. Hart.  An analysis of the principal-agent problem.  _Econometrica_ , 51(1):7–45, 1983.
  * Grossman and Hart [1992] Sanford J Grossman and Oliver D Hart.  An analysis of the principal-agent problem.  In _Foundations of insurance economics_ , pages 302–340. Springer, 1992.
  * Hart et al. [2011] William E Hart, Jean-Paul Watson, and David L Woodruff.  Pyomo: modeling and solving mathematical programs in python.  _Mathematical Programming Computation_ , 3(3):219–260, 2011.
  * Ho et al. [2016] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan.  Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems.  _Journal of Artificial Intelligence Research_ , 55:317–359, 2016.
  * Hoiem et al. [2021] Derek Hoiem, Tanmay Gupta, Zhizhong Li, and Michal Shlapentokh-Rothman.  Learning curves for analysis of deep networks.  In _International conference on machine learning_ , pages 4287–4296. PMLR, 2021.
  * Holmström [1979] Bengt Holmström.  Moral hazard and observability.  _The Bell Journal of Economics_ , 10(1):74–91, 1979.
  * Holmstrom and Milgrom [1987] Bengt Holmstrom and Paul Milgrom.  Aggregation and linearity in the provision of intertemporal incentives.  _Econometrica: Journal of the Econometric Society_ , pages 303–328, 1987.
  * Hutter [2021] Marcus Hutter.  Learning curve theory.  _arXiv preprint arXiv:2102.04074_ , 2021.
  * Kaplan et al. [2020] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kleinberg and Kleinberg [2018] Jon Kleinberg and Robert Kleinberg.  Delegated search approximates efficient search.  In _Proceedings of the 2018 ACM Conference on Economics and Computation_ , pages 287–302, 2018.
  * Kleinberg and Raghavan [2019] Jon Kleinberg and Manish Raghavan.  How do classifiers induce agents to invest effort strategically?  In _EC 2019_ , pages 825–844, 2019.
  * Kleinberg and Raghavan [2020] Jon M. Kleinberg and Manish Raghavan.  Algorithmic classification and strategic effort.  _SIGecom Exch._ , 18(2):45–52, 2020.
  * Lahaie [2008] Sébastien Lahaie.  How to take the dual of a linear program.  _Columbia University, New York_ , 2008.
  * LeCun [1998] Yann LeCun.  The MNIST database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * Lehmann et al. [2005] Erich Leo Lehmann, Joseph P Romano, and George Casella.  _Testing statistical hypotheses_ , volume 3.  Springer, 2005.
  * Mahmood et al. [2022] Rafid Mahmood, James Lucas, David Acuna, Daiqing Li, Jonah Philion, Jose M Alvarez, Zhiding Yu, Sanja Fidler, and Marc T Law.  How much more data do I need? Estimating requirements for downstream tasks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 275–284, 2022.
  * Martimort and Laffont [2009] David Martimort and Jean-Jacques Laffont.  _The theory of incentives: the principal-agent model_.  Princeton University Press, 2009.
  * Mohr et al. [2022] Felix Mohr, Tom J Viering, Marco Loog, and Jan N van Rijn.  Lcdb 1.0: An extensive learning curves database for classification tasks.  _Machine Learning and Knowledge Discovery in Databases, ECMLPKDD. p. accepted. Lecture Notes in Computer Science, Springer_ , 2022.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Rigollet and Hütter [2015] Phillippe Rigollet and Jan-Christian Hütter.  High dimensional statistics.  _Lecture notes for course 18S997_ , 813(814):46, 2015.
  * Rosenfeld et al. [2019] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit.  A constructive prediction of the generalization error across scales.  _arXiv preprint arXiv:1909.12673_ , 2019.
  * Royal Swedish Academy of Sciences [2016] Royal Swedish Academy of Sciences.  Scientific background on the 2016 Nobel Prize in Economic Sciences, 2016.
  * Salanie [2017] Bernard Salanie.  _The Economics of Contracts: A Primer_.  MIT press, 2017.
  * Viering and Loog [2022] Tom Viering and Marco Loog.  The shape of learning curves: a review.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Xia et al. [2022] Mengzhou Xia, Mikel Artetxe, Chunting Zhou, Xi Victoria Lin, Ramakanth Pasunuru, Danqi Chen, Luke Zettlemoyer, and Ves Stoyanov.  Training trajectories of language models across scales.  _arXiv preprint arXiv:2212.09803_ , 2022.
  * Zhao et al. [2022] Xinyi Zhao, Weixin Liang, and James Zou.  Data budgeting for machine learning.  Working paper available at https://doi.org/10.48550/arXiv.2210.00987, 2022.
  * Zhu et al. [2022] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I Jordan.  The sample complexity of online contract design.  _arXiv preprint arXiv:2211.05732_ , 2022.

##  Appendix A Broader implications

In this paper, we set out to formalize and study the task of delegating
classification through the lens of contract design. Given that our work is
largely motivated by the increasingly common practice of outsourcing learning
tasks to specialized service providers, we believe our algorithm, analysis,
and empirical observations carry meaningful implications for practitioners and
decision-makers alike. At the same time, it is important to remember that our
work—as others considering economic aspects of learning—studies delegation in
a simplified setting and under certain assumptions. As such, and since
devising and agreeing to legally-binding contracts can have concrete
implications on real-world outcomes, care should be taken when applying ideas
or conclusions that derive from our work in practice.

For example, consider that our formalism relies on the assumption that the
learning agent is all-knowing and rational. Yet in reality, agents must act
under partial information, face irreducible (and often unquantifiable)
uncertainty, and—being human—are subject to common behavioral biases. It is
unclear a-priori if and how our statements and conclusions carry over to this
setting. As another example, notice that our formalism considers a one-shot
setting where a single contract between a single principal-agent pair is
instantiated once. But in reality, competition and long-term reputation may
play a significant role in determining the agent’s incentive structure, and
consequently, her behavior. In such cases, naïvely applying our framework
without careful inspection of the appropriate incentives on both ends can
result in sub-optimal contracts, possibly to the detriment of all involved
parties. Nonetheless, given that our work aims to take an initial step towards
establishing delegated learning, we view its extension to non-rational agents
and temporal and competitive settings as intriguing future work.

One message that our work conveys is that in delegation, simplicity, in the
form of threshold contracts, has merit. This draws connections to other works
that similarly argue for simplicity as an important and useful property of
effective delegation mechanisms. Our work shows that simple contracts are,
under reasonable conditions, computationally feasible and theoretically
optimal. Economically, threshold contracts are practically appealing since
they are easy to understand, communicate, and regulate. Given that contracts
are in essence social constructs, we believe these properties are key for
establishing threshold contracts as effective building blocks for machine
learning markets.

##  Appendix B Min-budget contract design – deferred proofs

##### Notation.

To align with traditional contract design notation, in this section, we denote
the action space by $\mathcal{A}=[n]={\left\\{{1,\dots,n}\right\\}}$, and the
outcome space by $\Omega={\left\\{{0,\dots,m}\right\\}}$. We denote by
${\Delta\left({\mathcal{X}}\right)}$ the set of distributions over a given set
$\mathcal{X}$. For contract design problems, we denote the outcome
probabilities by $F_{i,j}$ (such that $F_{i}\in{\Delta\left({\Omega}\right)}$
is the outcome distribution associated with action $i$), and the cost of each
action by $c_{i}$. Given $x\in\mathbb{R}$, we denote
$x^{+}=\mathrm{ReLU}(x)=\max{\left\\{{0,x}\right\\}}$. We denote the indicator
function by $\mathds{1}\left[{\cdot}\right]$, the total variation distance
between distributions $P,Q$ by
$\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$ (see Definition 2), and the
survival function of $P\in{\Delta\left({\Omega}\right)}$ by
$\mathbb{S}_{{P}}({\cdot})$ (see Definition 11).

##### A note on individual rationality.

In the contract design literature, a contract is said to be _incentive
compatible_ (IC) with respect to some action $a^{*}$ if it satisfies
$u_{a^{*}}(t)\geq u_{a}(t)$ for all actions $a\in\mathcal{A}$. In the
delegated classification setting, this corresponds to the constraint
$n(t)=n^{*}$ in eq. 4. As an additional constraint, contracts in which the
agent’s expected utility is always non-negative ($u_{n^{*}}(t)\geq 0$) are
said to be _individually rational_ (IR). In the case of delegated
classification, it is natural to assume that there always exists a valid
action that the agent can take at zero cost — for example, returning a dummy
classifier that always abstains from prediction (thus having zero accuracy),
or a classifier which makes a prediction at random. As such, contracts in the
delegated classification setting can be assumed to be individually rational
without loss of generality, as any action $n$ that is chosen by the agent has
utility which is weakly larger than the utility of the zero-cost action, which
is always non-negative. Moreover, even in cases where a zero-loss action does
not exist, we show that individual rationality (IR) can be attained in a
straightforward manner, by adding the minimal cost $c_{1}$ to each entry of an
incentive compatible (IC) contract ($t_{j}\mapsto t_{j}+c_{1}$):

######  Claim 1.

Given an IC contract $t$ with $c_{1}>0$, the contract $t+c_{1}$ (add $c_{1}$
to every coordinate of the contract) is both IC and IR.

###### Proof.

An IC contract implementing action $a^{*}$ satisfies $u_{a^{*}}(t)\geq
u_{a}(t)$, for all actions $a\in\mathcal{A}$. In particular, this inequality
holds in relation to the least-costly action, denoted by $1\in\mathcal{A}$.
Plugging the definition of the agent’s expected utility (eq. 2), we obtain
$u_{a^{*}}(t)\geq\mathbb{E}_{j\sim f_{1}}{\left[{t}\right]}-c_{1}$. Thus,
under the mapping $t^{\prime}_{j}=t_{j}+c_{1}$, it holds that:

$u_{a^{*}}(t^{\prime})=u_{a^{*}}(t+c_{1})\geq\mathbb{E}_{j\sim
f_{1}}{\left[{t+c_{1}}\right]}-c_{1}=\mathbb{E}_{j\sim
f_{1}}{\left[{t}\right]}\geq 0$

and therefore the contract $t^{\prime}=t+c_{1}$ is individually rational and
still implements action $a^{*}$. ∎

###  B.1 Relation between budget-optimal and min-budget contracts

###### Proof of Proposition 1.

Given budget $B>0$, let $t$ be a budget-optimal contract, and denote the
action it implements by $n^{*}$. By definition, $t$ is a feasible solution to
the min-budget contract design problem eq. 4 implementing action $n^{*}$.
Denote by $t^{*}$ the corresponding optimal solution to eq. 4. $t^{*}$
implements the same action $n^{*}$ by definition, and satisfies
$\left\lVert{t^{*}}\right\rVert_{\infty}\leq\left\lVert{t}\right\rVert_{\infty}\leq
B$ due to the optimization objective. Hence, $t^{*}$ is a budget-optimal
contract for the given budget $B$, which is also min-budget. ∎

##### Iterative min-budget.

To find the budget-optimal contract using iterative applications of eq. 4, we
observe that any budget-limited contract $t:\Omega\to{[0,B]}$ has bounded
expected pay $\mathbb{E}_{f_{n}}{\left[{t}\right]}\leq B$ for any distribution
$f_{n}$. Hence, actions $n^{\prime}$ with cost $c_{n^{\prime}}>B$ cannot be
implemented using budget $B$, as the agent’s utility
$u_{n^{\prime}}=\mathbb{E}_{f_{n^{\prime}}}{\left[{t}\right]}-c_{n^{\prime}}<0$
will be smaller than the utility of the zero-cost action
$u_{0}=\mathbb{E}_{f_{n}}{\left[{t}\right]}-0\geq 0$. Define the reduced
action set:

$\mathcal{A}^{\prime}={\left\\{{n\in\mathcal{A}\mid c_{n}\leq B\wedge\text{$n$
is implementable}}\right\\}}$

$\mathcal{A}^{\prime}$ is finite when $\mathcal{A}$ is finite, or when the
data cost is unbounded and the learning curve is monotone. To find $n^{*}$
within this space, go over all $n\in\mathcal{A}^{\prime}$, calculate the
minimal budget $B_{n}$ required for implementation, and take
$\operatorname*{argmin}_{n\in\mathcal{A}^{\prime}}B_{n}$. This is possible
within a finite number of steps.

###  B.2 The min-budget linear program and equivalent forms

The min-budget contract (eq. 4) implementing action $i\in\mathcal{A}$ is given
by the MIN-BUDGET linear program:

$\displaystyle\min_{t\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|},B\in\mathbb{R}_{\geq 0}}B$ (5)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\forall j\in\Omega:t_{j}\leq B$
(BUDGET) $\displaystyle\forall i^{\prime}\neq
i:\sum_{j\in\Omega}F_{i^{\prime},j}t_{j}-c_{i^{\prime}}\leq\sum_{j\in\Omega}F_{i,j}t_{j}-c_{i}$
(IC)

The dual of the min-budget LP is given by:

######  Claim 2.

The dual linear program of Equation 5 is given by:

$\displaystyle\max_{\lambda\in\mathbb{R}_{\geq 0}^{n-1},\mu\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|}}\sum_{i^{\prime}\neq
i}\left(c_{i}-c_{i^{\prime}}\right)\lambda_{i^{\prime}}$ (6)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\forall
j\in\Omega:\sum_{i^{\prime}\neq
i}\left(F_{i,j}-F_{i^{\prime},j}\right)\lambda_{i^{\prime}}\leq\mu_{j}$
$\displaystyle\sum_{j\in\Omega}\mu_{j}\leq 1$

###### Proof.

We take the dual by translating the optimization problem into canonical form.
The canonical form we target:

$\min_{x\geq 0}c^{T}x\quad\text{s.t.}\quad Cx\leq d$

And its dual, as given by Lahaie [32], is:

$\max_{y\geq 0}-d^{T}y\quad\text{s.t.}\quad C^{T}y\geq-c$

To translate Equation 5, we note that in our case the components $c$,$C$,$d$
are given by:

$c^{T}=\begin{pmatrix}0&\dots&0&1\end{pmatrix}\in\mathbb{R}^{{\left|{\Omega}\right|}+1}$

$C=\left(\begin{array}[]{c|c}\begin{matrix}F_{1,0}-F_{i,0}&\dots&&&F_{1,{\left|{\Omega}\right|}}-F_{i,{\left|{\Omega}\right|}}\\\
\vdots&\ddots&&&\vdots\\\ &&F_{i^{\prime},j}-F_{i,j}&&\\\ &&&\ddots&\\\
F_{n,0}-F_{i,0}&&&&F_{n,m}-F_{i,m}\\\ \end{matrix}&\begin{matrix}0\\\
\vdots\\\ \\\ \\\ 0\end{matrix}\\\ \hline\cr I_{m+1}&\begin{matrix}-1\\\
\vdots\\\ \\\ -1\end{matrix}\\\
\end{array}\right)\in\mathbb{R}^{(n-1+{\left|{\Omega}\right|})\times({\left|{\Omega}\right|}+1)}$

$d^{T}=\begin{pmatrix}c_{1}-c_{i}&\dots&c_{n}-c_{i}&\vline&0&\dots&0\end{pmatrix}\in\mathbb{R}^{n-1+{\left|{\Omega}\right|}}$

To simplify formulation, we denote the dual optimization variable $y$ as
follows:

$y^{T}=\begin{pmatrix}\lambda_{1}&\dots&\lambda_{i-1}&\lambda_{i+1}&\dots\lambda_{n}&\vline&\mu_{0}&\dots&\mu_{m}\end{pmatrix}\in\mathbb{R}^{n-1+{\left|{\Omega}\right|}}$

Under this formulation, the dual’s objective is:

$\displaystyle-d^{T}y=\sum_{i\neq
i^{\prime}}\left(c_{i}-c_{i^{\prime}}\right)\lambda_{i^{\prime}}$ (7)

The constraints given by the first $m$ rows of $C^{T}$ are:

$\forall j\in\Omega:\sum_{i^{\prime}\neq
i}\left(F_{i^{\prime},j}-F_{i,j}\right)+\mu_{j}\geq 0$

and equivalently:

$\forall j\in\Omega:\sum_{i^{\prime}\neq
i}\left(F_{i,j}-F_{i^{\prime},j}\right)\leq\mu_{j}$ (8)

The constraint corresponding to the last row of $C^{T}$ is given by:

$\sum_{j\in\Omega}-\mu_{m}\geq-1$

and equivalently:

$\sum_{j\in\Omega}\mu_{m}\leq 1$ (9)

Combining equations (7, 8, 9) yields the linear program given by Equation 6. ∎

To map between contracts and hypothesis tests, we introduce the following
variable transformation:

######  Definition 1 (Statistical representation of contracts).

For a given contract $t:\Omega\to\mathbb{R}_{\geq 0}$, denote
$B=\max_{j}t_{j}$. The statistical representation of $t$ is given by:

$t_{j}=\phi_{j}\beta^{-1}$

where $\phi_{j}\in[0,1]$ and $\beta=B^{-1}$.

Note that the transformation $(t,B)\mapsto(\phi,\beta)$ is non-linear, and
well-defined for all $B>0$. Under this variable transformation, the MIN-BUDGET
transforms to an equivalent linear program:

######  Lemma 2.

For a feasible design problem, the min-budget contract design LP (Equation 5)
is equivalent to:

$\displaystyle\max_{\phi\in[0,1]^{\left|{\Omega}\right|},\beta\in\mathbb{R}_{\geq
0}}\beta$ (10) $\displaystyle\mathrm{s.t.}$ $\displaystyle\forall
i^{\prime}\neq
i:\sum_{j\in\Omega}F_{i,j}(1-\phi_{j})+\sum_{j\in\Omega}F_{i^{\prime},j}\phi_{j}\leq
1-(c_{i}-c_{i^{\prime}})\beta$

###### Proof.

Given Equation 5, define $\phi\in[0,1]^{\left|{\Omega}\right|}$, $\beta\geq 0$
according to definition 1:

$\displaystyle B$ $\displaystyle=\beta^{-1}$ (11) $\displaystyle t_{j}$
$\displaystyle=\phi_{j}B=\phi_{j}\beta^{-1}$

Under the transformation defined by Equation 11, the (BUDGET) constraint in
Equation 5 transforms as follows:

$\displaystyle t_{j}\leq B$
$\displaystyle\Leftrightarrow\phi_{j}\beta^{-1}\leq\beta^{-1}$ (12)
$\displaystyle\Leftrightarrow\phi_{j}\leq 1$

and the (IC) constraint in Equation 5 transforms as:

$\displaystyle\sum_{j}F_{i,j}t_{j}-c_{i}\geq\sum_{j}F_{i^{\prime},j}t_{j}-c_{i^{\prime}}$
$\displaystyle\Leftrightarrow\sum_{j}\left(F_{i,j}-F_{i^{\prime},j}\right)\phi_{j}\beta^{-1}\geq
c_{i}-c_{i^{\prime}}$ (13)
$\displaystyle\Leftrightarrow\sum_{j}F_{i,j}\phi_{j}-\sum_{j}F_{i^{\prime},j}\phi_{j}\geq\left(c_{i}-c_{i^{\prime}}\right)\beta$
$\displaystyle\Leftrightarrow
1-\sum_{j}F_{i,j}(1-\phi_{j})-\sum_{j}F_{i^{\prime},j}\phi_{j}\geq\left(c_{i}-c_{i^{\prime}}\right)\beta$
$\displaystyle\Leftrightarrow\sum_{j}F_{i,j}(1-\phi_{j})+\sum_{j}F_{i^{\prime},j}\phi_{j}\leq
1-\left(c_{i}-c_{i^{\prime}}\right)\beta$

where the first equivalence is by Equation 11, and the third equivalence is
valid as $\sum_{j}F_{i^{\prime},j}=1$ for all $i^{\prime}$. Finally, the
objective of Equation 5 transforms as:

$\displaystyle\min B\Leftrightarrow\max\beta$ (14)

Combining equations (12, 13, 14) yields the LP in Equation 10 ∎

###  B.3 Relation to min-pay contract design

Min-pay contract design aims to design a contract which minimizes the expected
pay under the implemented action $n^{*}$:

$t^{*}=\operatorname*{argmin}\nolimits_{t}\mathbb{E}_{j\sim
f_{n^{*}}}{\left[{t_{j}}\right]}\quad\text{s.t.}\quad n(t)=n^{*}$ (15)

In contrast to the min-budget contract (eq. 4), the
$\left\lVert{t}\right\rVert_{\infty}$ objective measuring maximal pay is
replaced with the $\mathbb{E}_{j\sim f_{n^{*}}}{\left[{t_{j}}\right]}$
objective measuring expected pay. Equation 15 is equivalent to the MIN-PAY
linear program:

$\displaystyle\min_{t\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|}}\sum_{j\in\Omega}F_{i,j}t_{j}$ (16)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\forall i^{\prime}\neq
i:\sum_{j\in\Omega}F_{i^{\prime},j}t_{j}-c_{i^{\prime}}\leq\sum_{j\in\Omega}F_{i,j}t_{j}-c_{i}$
(IC)

####  B.3.1 Characterization of implementability

The implementatbility of min-pay contracts is characterized in Dütting et al.
[15]. We cite the main result here for completeness:

######  Proposition 3 (Min-pay implementability; [15], A.2).

An action $i\in\mathcal{A}$ is implementable (up to tie-breaking) if and only
if there is no convex combination of the other actions that results in the
same distribution $f_{i}=\sum_{i^{\prime}\neq
i}\alpha_{i^{\prime}}f_{i^{\prime}}$, but lower cost
$c_{i}>\sum_{i^{\prime}\neq i}\alpha_{i^{\prime}}c_{i^{\prime}}$.

We leverage to proposition 3 to characterize the implementability of min-
budget contracts. This is possible due to the following connection:

######  Claim 3 (Implementability equivalence).

A contract $t$ is feasible solution of MIN-BUDGET if and only if it is a
feasible solution of MIN-PAY.

###### Proof.

A contract $t$ which satisfies MIN-BUDGET (eq. 5) satisfies the (IC)
constraint, and thus also satisfies MIN-PAY (eq. 16). Conversely, a contract
$t$ which satisfies MIN-PAY satisfies the (IC) constraint. Set
$B=\max_{j}t_{j}$ and obtain a feasible solution to MIN-BUDGET. ∎

####  B.3.2 Min-pay contracts under MLRP

The optimal min-pay contracts under the MLRP assumption are characterized in
Dütting et al. [15]:

######  Proposition 4 (Optimal min-pay contract under MLRP; [15], Lemma 7).

Consider a contract design setting for which MLRP holds. If the highest-cost
action $n$ is implementable, then there is a min-pay contract has a single
nonzero-payment, which is rewarded for the highest outcome $m$.

See fig. 5 for a qualitative comparison of min-pay and min-budget contracts.

##### Min-pay contracts in delegated learning settings with MLRP.

While simple, the min-pay contract given by proposition 4 is impractical in
realistic delegated classification scenarios. In a delegated classification
setting, the highest outcome corresponds to 100% validation set accuracy (i.e
all validation set samples classified correctly). As $m$ grows, the highest
outcome becomes exponentially less likely, and thus the min-pay contract
awards increasingly high payments with increasingly lower probabilities (See
fig. 6). In such settings, even a slight degree of risk-averseness is likely
to affect decisions: From the agent’s perspective, the probability of any
receiving payment from a min-pay contract may become small to a degree where
even a slight degree of agent risk-averseness will manifest itself. From the
principal’s side, the exponential rate of growth in required budget

Figure 5:  Qualitative comparison of min-pay and min-budget contracts under
MLRP. (Left) The contract design setting, representing two possible actions
with binomial outcome distributions ($p_{1}=0.5$, $p_{2}=0.8$, $m=15$). Action
$1$ has zero cost $c_{1}=0$, and action $2$ has unit cost $c_{2}=1$. (Right)
The resulting min-pay (red) and min-budget (purple) contracts, obtained by
solving eq. 16 and eq. 5, respectively. The min-pay awards payment only for
the highest outcome, in alignment with proposition 4; the min-budget is a
threshold contract, in alignment with 11.  Figure 6:  Comparison of min-pay
and min-budget contracts under MLRP for varying validation set size $m$. The
delegation setting is similar to the one depicted in Figure 5: two binomial-
outcome actions ($p_{1}=0.5$, $p_{2}=0.8$) and varying $m$. Action $1$ has
zero cost $c_{1}=0$, and action $2$ has unit cost $c_{2}=1$. In the left and
center plots, the cost of action $2$ is represented by an orange line
($c_{2}=1$) representing the lower bound as in fig. 3 (Center). (Left)
Expected pay $\mathbb{E}_{j\sim f_{2}}{\left[{t_{j}}\right]}$. (Center)
Required budget $\left\lVert{t}\right\rVert_{\infty}$. (Right) Probability of
getting any payment $\mathbb{P}_{j\sim f_{2}}{\left[{t_{j}>0}\right]}$.

###  B.4 Min-budget contracts with two actions

In this section, we explore min-budget settings with two actions, and prove
Theorem 1. When $n=2$, assume without loss of generality that the contract
implements action $i=2$, and denote $c=c_{2}-c_{1}>0$.

We recall the definition of total variation distance:

######  Definition 2 (Total variation distance).

Given two distributions $P,Q\in{\Delta\left({\Omega}\right)}$, the total
variation distance between $P$ and $Q$ is:

$\displaystyle\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$
$\displaystyle=\frac{1}{2}\left\lVert{P-Q}\right\rVert_{1}$

The following equivalent definition is useful:

######  Claim 4.

Let $P,Q\in{\Delta\left({\Omega}\right)}$. It holds:

$\displaystyle\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$
$\displaystyle=\sum_{j\in\Omega}\left(Q_{j}-P_{j}\right)^{+}$

where $x^{+}=\max{\left\\{{x,0}\right\\}}$.

###### Proof.

By definition:

$\displaystyle\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$
$\displaystyle=\frac{1}{2}\left\lVert{P-Q}\right\rVert_{1}$

Decompose the $L_{1}$ norm:

$\displaystyle\frac{1}{2}\left\lVert{P-Q}\right\rVert_{1}$
$\displaystyle=\frac{1}{2}\sum_{j\in\Omega}\left(\left(Q_{j}-P_{j}\right)^{+}+\left(P_{j}-Q_{j}\right)^{+}\right)$

As $\sum_{j\in\Omega}P_{j}=\sum_{j\in\Omega}Q_{j}=1$, it holds that:

$\sum_{j\in\Omega}\left(Q_{j}-P_{j}\right)^{+}=\sum_{j\in\Omega}\left(P_{j}-Q_{j}\right)^{+}$

and therefore
$\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}=\sum_{j\in\Omega}\left(Q_{j}-P_{j}\right)^{+}$
as required. ∎

####  B.4.1 Optimal two-action contract

######  Lemma 3 (Two-action min-budget contract; formal statement of
Proposition 2).

When $n=2$, the optimal min-budget contract $t^{*}$ is given by:

$t^{*}_{j}=\frac{c}{\left\lVert{{F_{2}}-{F_{1}}}\right\rVert_{\mathrm{TV}}}\mathds{1}\left[{F_{2,j}\geq
F_{1,j}}\right]$ (17)

###### Proof.

We prove this claim using LP duality, by showing that the optimal primal
objective corresponding to $t^{*}$ is identical to a feasible solution of the
dual LP.

The primal LP (Equation 5) for two actions is given by:

$\displaystyle\min_{t\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|},B\in\mathbb{R}_{\geq 0}}B$ (18)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\forall j\in\Omega:t_{j}\leq B$
(BUDGET) $\displaystyle\sum_{j\in\Omega}\left(F_{2,j}-F_{1,j}\right)t_{j}\geq
c$ (IC)

As $t^{*}$ is bounded, the optimal objective $B^{*}$ corresponds to the
maximal possible payout of $t^{*}$:

$B^{*}=\max_{j\in\Omega}t^{*}_{j}=\frac{c}{\left\lVert{{F_{2}}-{F_{1}}}\right\rVert_{\mathrm{TV}}}$
(19)

and therefore the (BUDGET) constraint is satisfied. For the (IC) constraint,
denote by $\Omega_{\geq}$ the following set:

$\Omega_{\geq}={\left\\{{j\in\Omega\mid F_{2,j}\geq F_{1,2}}\right\\}}$

using this notation, we note that $t^{*}_{j}>0$ if and only if
$j\in\Omega_{\geq}$. Plugging into the constraint, we obtain:

$\displaystyle\sum_{j\in\Omega}\left(F_{2,j}-F_{1,j}\right)t_{j}^{*}$
$\displaystyle=\sum_{j\in\Omega_{\geq}}\left(F_{2,j}-F_{1,j}\right)B^{*}$
$\displaystyle=c\frac{\sum_{j\in\Omega_{\geq}}\left(F_{2,j}-F_{1,j}\right)}{\left\lVert{{F_{2}}-{F_{1}}}\right\rVert_{\mathrm{TV}}}$
$\displaystyle=c$

Where
$\left\lVert{{F_{2}}-{F_{1}}}\right\rVert_{\mathrm{TV}}=\sum_{j\in\Omega_{\geq}}\left(F_{2,j}-F_{1,j}\right)$
by definition. This shows that $t^{*}$ is a feasible solution for the primal
LP.

To prove optimality, we show that the the dual linear program attains an
identical objective. By 2, the dual LP for two actions is given by:

$\displaystyle\max_{\lambda\in\mathbb{R}_{\geq 0},\mu\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|}}c\lambda$ (20) $\displaystyle\mathrm{s.t.}$
$\displaystyle\forall
j\in\Omega:\left(F_{2,j}-F_{1,j}\right)\lambda\leq\mu_{j}$
$\displaystyle\sum_{j\in\Omega}\mu_{j}\leq 1$

Denote the vector $\vec{v}_{j}(\lambda)\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|}$:

$\vec{v}_{j}(\lambda)=\lambda\left(F_{2,j}-F_{1,j}\right)^{+}$

We note that outcomes $j^{\prime}$ for which $F_{2,j^{\prime}}\leq
F_{1,j^{\prime}}$ (formally $j^{\prime}\in\Omega\setminus\Omega_{\geq}$)
correspond to constraints which are satisfied for any $\lambda\geq 0$.
Otherwise $j\in\Omega_{\geq}$, and in these cases $\lambda$ can be increased
until $\vec{v}(\lambda)$ saturates the simplex constraint
$\sum_{j\in\Omega}\mu_{j}=1$. The simplex constraint is binding for a value
$\lambda^{*}>0$ satisfying:

$\sum_{j\in\Omega}\lambda^{*}\left(F_{2,j}-F_{1,j}\right)^{+}=1$

and therefore the optimal value $\lambda^{*}$ of the dual LP (eq. 20) is:

$c\lambda^{*}=\frac{c}{\sum_{j\in\Omega}\left(F_{2,j}-F_{1,j}\right)^{+}}=\frac{c}{\left\lVert{{F_{2}}-{F_{1}}}\right\rVert_{\mathrm{TV}}}$
(21)

Where the second equality is given by 4. The dual objective in eq. 21 is
identical to the primal objective attained by the contract $t^{*}$ in Equation
19, and therefore $t^{*}$ is an optimal contract by strong LP duality. ∎

####  B.4.2 Contracts and hypothesis tests

We recall the formal definition of the Neyman-Pearson lemma:

######  Lemma 4 (Neyman-Pearson).

Let $P,Q\in{\Delta\left({\mathcal{X}}\right)}$ be two probability measures
over an arbitrary set $\mathcal{X}$. Then for any hypothesis test
$\psi:\mathcal{X}\to{\left\\{{0,1}\right\\}}$, it holds:

$P(\psi(x)=1)+Q(\psi(x)=0)\geq
1-\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}.$ (22)

Moreover, equality holds for the Likelihood Ratio test
$\psi^{*}(x)=\mathds{1}\left[{q(x)\geq p(x)}\right]$.

A proof of Lemma 4 is provided in Rigollet and Hütter [39, Section 4.3]. We
note that the lemma is stated for decision rules with binary output, but it
can be extended to support probabilistic decision functions
$\psi:\mathcal{X}\to[0,1]$ as well: As the sum of errors is linear in $\psi$,
the optimal fractional decision rule is a solution to the linear program
$\min_{\psi\in\left[0,1\right]^{\mathcal{X}}}\left(P(\psi=1)+Q(\psi=0)\right)$
where $P(\psi=1)=\sum_{x\in\mathcal{X}}p_{x}\psi(x)$ and
$Q(\psi=0)=\sum_{x\in\mathcal{X}}q_{x}(1-\psi(x))$. The feasible region of
this linear program is the hypercube $\left[0,1\right]^{\mathcal{X}}$ and its
vertices are the set of binary decision rules
${\left\\{{0,1}\right\\}}^{\mathcal{X}}$, which also includes the optimal
binary rule $\psi^{*}$ given by Lemma 4. As every feasible linear program
attains its optimum on a vertex, the binary $\psi^{*}$ is also the optimal
among fractional rules.

###### Proof of Theorem 1.

For a given two-action contract, denote $P_{j}=F_{1,j}$, $Q_{j}=F_{2,j}$, and
$c=c_{2}-c_{1}$. By Lemma 2, the primal LP for two actions is given by:

$\displaystyle\max_{\phi\in[0,1]^{\left|{\Omega}\right|},\beta\in\mathbb{R}_{\geq
0}}\beta$ (23) $\displaystyle\mathrm{s.t.}$
$\displaystyle\sum_{j\in\Omega}P_{j}\phi_{j}+\sum_{j\in\Omega}Q_{j}(1-\phi_{j})\leq
1-c\beta$

And the Neyman-Pearson lemma is given by Equation 22.

Given a min-budget contract $t^{*}$, apply Lemma 3 to obtain its
characterization, as given by eq. 17:

$\displaystyle B^{*}$
$\displaystyle=\frac{c}{\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}}$
$\displaystyle t^{*}_{j}$
$\displaystyle=\frac{c}{\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}}\mathds{1}\left[{Q_{j}\geq
P_{j}}\right]$

Applying the transformation from definition 1 on the optimal contract, we
obtain equivalently:

$\displaystyle\beta^{*}$
$\displaystyle=\left(B^{*}\right)^{-1}=\frac{\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}}{c}$
$\displaystyle\phi^{*}_{j}$
$\displaystyle=t_{j}^{*}/B^{*}=\mathds{1}\left[{Q_{j}\geq P_{j}}\right]$

Note that $\phi^{*}_{j}$ is a maximum-likelihood decision rule, similar to the
optimal critical function in the Neyman-Pearson lemma. Additionally, by
optimality of $\beta^{*}$, any feasible solution $\phi^{\prime}$ of
LABEL:eq:min_budget_statistical_lp_two_actions satisfies:

$\sum_{j=1}^{m}P_{j}{\phi^{\prime}}_{j}+\sum_{j=1}^{m}Q_{j}(1-\phi^{\prime}_{j})\geq
1-c\beta^{*}=1-\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$

and therefore the min-budget optimality of the contract $t^{*}$ entails the
power optimality of the hypothesis test $\phi^{*}$.

Conversely, let $\phi:\Omega\to[0,1]$ be an maximal-power hypothesis test.
This provides a lower bound on the constraint in
LABEL:eq:min_budget_statistical_lp_two_actions:

$\sum_{j\in\Omega}P_{j}\phi_{j}+\sum_{j\in\Omega}Q_{j}(1-\phi_{j})\geq
1-\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$

By the Neyman-Pearson lemma, the bound is tight for the maximum likelihood
rule $\phi^{\star}=\mathds{1}\left[{Q\geq P}\right]$, and therefore the
optimal objective $\beta^{\star}$ satisfies:

$\displaystyle
1-c\beta^{\star}=1-\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}$

and hence
$\beta^{\star}=\frac{\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}}{c}$.
Applying the transformation in definition 1 yields the optimal contract
$t_{j}^{\star}=\frac{c}{\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}}\mathds{1}\left[{Q_{j}\geq
P_{j}}\right]$, showing that the corresponding contract is min-budget optimal
if the corresponding hypothesis has optimal statistical power. ∎

###  B.5 More than two actions

######  Definition 3 (All-or-nothing contract).

Let $B>0$. An all-or-nothing contract $t:\Omega\to\mathbb{R}_{\geq 0}$
satisfies $t_{j}\in{\left\\{{0,B}\right\\}}$ for all $j\in\Omega$.

####  B.5.1 Two outcomes

######  Lemma 5.

For any feasible min-budget contract $t^{*}$, there exists $j_{0}\in\Omega$
such that $t^{*}_{j_{0}}=0$.

###### Proof.

By contradiction, assume that $t^{*}_{j}>0$ for all $j$, and denote
$j_{0}=\operatorname*{argmin}_{j}t^{*}_{j}$. Denote $a=\min_{j}t_{j}$, and
note that $a>0$. Define the contract $\tilde{t}$ as follows:

$\forall j:\tilde{t}_{j}=t_{j}-a$

By definition, $\tilde{t}_{j}\geq 0$ for all $j$, and $\tilde{t}_{j_{0}}=0$.
Since $t^{*}$ is a feasible min-budget contract, it satisfies the min-budget
LP in eq. 5, and in particular the (IC) constraint:

$\forall
i\in[n-1]:\sum_{j}F_{i,j}t^{*}_{j}-c_{i}\leq\sum_{j}F_{n,j}t^{*}_{j}-c_{n}$

Plugging in the definition $\tilde{t}=t^{*}-a$ and using the fact that
$\sum_{j}F_{i,j}=1$ for all $i\in[n]$, we obtain:

$\forall
i\in[n-1]:\sum_{j}F_{i,j}\tilde{t}_{j}-c_{i}\leq\sum_{j}F_{n,j}\tilde{t}_{j}-c_{n}$

and therefore $\tilde{t}$ satisfies the (IC) constraint as well. This is a
contradiction, since $\tilde{t}$ is a feasible contract with a lower required
budget. From this we conclude that the optimal contract must satisfy $t_{j}=0$
for some $j$. ∎

######  Corollary 1.

In any min-budget contract design setting with two outcomes, the optimal
contract is all-or-nothing.

####  B.5.2 Computational hardness

In this section, we show that finding optimal all-or-nothing contracts is NP-
hard in the general case.

######  Definition 4 (Maximin contract design matrix).

For a given contract design problem targeting action $n$ and satisfying
$c_{i}<c_{n}$ for all $i\in[n-1]$, the maximin design matrix $A$ is defined
as:

$A_{ij}=\frac{F_{n,j}-F_{i,j}}{c_{n}-c_{i}}$ (24)

######  Claim 5.

An optimal all-or-nothing contract is a solution of the following optimization
problem:

$\displaystyle\max_{\phi\in{\left\\{{0,1}\right\\}}^{\left|{\Omega}\right|}}\min_{i\in[n-1]}\left(A\phi\right)_{i}$
(25)

Where $A$ is the corresponding maximin design matrix, as given by Definition
4.

###### Proof.

By Lemma 2, Equation 10, the min-budget contract design LP is equivalent to:

$\displaystyle\max_{\phi\in\left[0,1\right]^{\left|{\Omega}\right|},\beta\in\mathbb{R}_{\geq
0}}\beta$ $\displaystyle\mathrm{s.t.}$ $\displaystyle\forall
i<n:\sum_{j\in\Omega}\frac{F_{n,j}-F_{i,j}}{c_{n}-c_{i}}\phi_{j}\geq\beta$

As $A_{ij}=\frac{F_{n,j}-F_{i,j}}{c_{n}-c_{i}}$, it holds that
$\sum_{j\in\Omega}\frac{F_{n,j}-F_{i,j}}{c_{n}-c_{i}}\phi_{j}=A\phi$. The LP
above is therefore equivalent to:

$\displaystyle\max_{\phi\in\left[0,1\right]^{\left|{\Omega}\right|},\beta\in\mathbb{R}_{\geq
0}}\beta$ $\displaystyle\mathrm{s.t.}$ $\displaystyle\forall
i<n:A_{i}\phi\geq\beta$

as $\beta$ is a lower bound for every constraint, its optimal value is the
maximal minimum attainable through variation of $\phi$:

$\displaystyle\max_{\phi\in\left[0,1\right]^{\left|{\Omega}\right|}}\min_{i\in[n-1]}\left(A\phi\right)_{i}$

and restricting the optimization space of $\phi$ to
${\left\\{{0,1}\right\\}}^{\left|{\Omega}\right|}$ yields the desired result.
∎

######  Definition 5 (3-CNF – Conjunctive normal form).

A 3-CNF formula over $m$ variables and $n$ clauses is a boolean-valued
function $\psi:{\left\\{{0,1}\right\\}}^{m}\to{\left\\{{0,1}\right\\}}$ of the
form:

$\psi(x_{1},\dots,x_{m})=\bigwedge_{i=1}^{n}\left(z_{i1}\vee z_{i2}\vee
z_{i3}\right)$

where $z_{ik}\in{\left\\{{x_{1},\dots,x_{m},\neg x_{1},\dots,\neg
x_{m}}\right\\}}$.

######  Definition 6 (Number of positives in clause $i$).

Given a 3-CNF $\psi$ and an assignment $x\in{\left\\{{0,1}\right\\}}^{m}$,
denote by $\sigma_{i}(\psi,x)$ the number of variables $z_{ik}$ in clause $i$
which evaluate to $1$ under assignment $x$.

######  Claim 6.

A formula $\psi$ is satisfiable if and and only if there exists an assignment
$x\in{\left\\{{0,1}\right\\}}^{m}$ such that
$\min_{i\in[n]}\sigma_{i}(\psi,x)\geq 1$.

###### Proof.

If $\psi$ is satisfiable then there exists $x\in{\left\\{{0,1}\right\\}}^{m}$
such that $\psi(x)=1$. Since $\psi$ is a 3-CNF, every clause $i$ must evaluate
to $1$, and therefore $\sigma_{i}(\psi,x)\geq 1$ for all $i\in[n]$.
Conversely, if there exist an assignment $x$ such that
$\min_{i\in[n]}\sigma_{i}(\psi,x)\geq 1$ then by definition $x$ satisfies
every clause, and therefore the whole formula $\psi$. ∎

####  B.5.3 Reduction from 3SAT

Given a 3-CNF $\psi$ with $n$ clauses and $m$ variables, we define a min-
budget contract design problem over $n+1$ actions and $m+3$ variables: The
target action is $i=n+1$. The cost associated with action $i$ is:

$c_{i}=\begin{cases}1&i=n+1\\\ 0&\mathrm{otherwise}\end{cases}$ (26)

Contract outcomes are denoted
$\Omega={\left\\{{1,\dots,m,\mathrm{pos},\mathrm{neg},\mathrm{const}}\right\\}}$.
For simplicity of notations, let $\varepsilon>0$, which will be assigned a
suitable value later in the proof. The distribution of the target outcome is
denoted by $Q$ and defined as:

$\displaystyle\forall j\in[m]:Q_{j}=\frac{\varepsilon}{m}$ (27) $\displaystyle
Q_{\mathrm{pos}}=1-\varepsilon\left(1+\frac{3}{m}\right)$ $\displaystyle
Q_{\mathrm{neg}}=0$ $\displaystyle Q_{\mathrm{const}}=\frac{3\varepsilon}{m}$

For each $i\in[n]$, denote the number of negated variables in clause $i$ by
$k_{i}\in{\left\\{{0,\dots,3}\right\\}}$. The distribution corresponding to
the $i$-th action is denoted by $P^{(i)}$ and defined as:

$\displaystyle\forall j\in[m]:P^{(i)}_{j}=\begin{cases}0&\text{$x_{j}$ exists
in clause $i$ and is not negated}\\\ \frac{2\varepsilon}{m}&\text{$x_{j}$
exists in clause $i$ and is negated}\\\
\frac{\varepsilon}{m}&\mathrm{otherwise}\end{cases}$ (28) $\displaystyle
P^{(i)}_{\mathrm{pos}}=0$ $\displaystyle
P^{(i)}_{\mathrm{neg}}=1-\varepsilon\left(1+\frac{9-4k_{i}}{m}\right)$
$\displaystyle P^{(i)}_{\mathrm{const}}=(3-k_{i})\frac{\varepsilon}{m}$

These distributions are well-defined whenever $\varepsilon<\frac{1}{4}$ and
$m\geq 3$. For concreteness, set:

$\varepsilon=\frac{1}{10}$ (29)

Using Definition 4 and combining equations (26, 27, 28), the maximin design
matrix $A^{\psi}\in\mathbb{R}^{(n+1)\times(m+3)}$ corresponding to the
contract design problem above is given by:

$\displaystyle\forall
j\in[m]:A^{\psi}_{i,j}=\begin{cases}\frac{\varepsilon}{m}&\text{$x_{j}$ exists
in clause $i$ and is not negated}\\\ -\frac{\varepsilon}{m}&\text{$x_{j}$
exists in clause $i$ and is negated}\\\ 0&\mathrm{otherwise}\end{cases}$ (30)
$\displaystyle A^{\psi}_{i,\mathrm{pos}}=Q_{\mathrm{pos}}$ $\displaystyle
A^{\psi}_{i,\mathrm{neg}}=-P^{(i)}_{\mathrm{neg}}$ $\displaystyle
A^{\psi}_{i,\mathrm{const}}=k_{i}\frac{\varepsilon}{m}$

######  Definition 7.

Given an assignment $x\in{\left\\{{0,1}\right\\}}^{m}$, the corresponding
contract vector $\phi^{x}\in{\left\\{{0,1}\right\\}}^{m+3}$ is defined as:

$\displaystyle\forall j\in[m]:\phi^{x}_{j}=x_{j}$ (31)
$\displaystyle\phi^{x}_{\mathrm{pos}}=1$
$\displaystyle\phi^{x}_{\mathrm{neg}}=0$
$\displaystyle\phi^{x}_{\mathrm{const}}=1$

######  Claim 7.

Let $\psi$ be a 3-CNF, and $x\in{\left\\{{0,1}\right\\}}^{m}$ an assignment.
It holds that:

$\left(A^{\psi}\phi^{x}\right)_{i}=\frac{\varepsilon}{m}\sigma_{i}(\psi,x)+Q_{\mathrm{pos}}$

###### Proof.

To prove this claim, plug $\phi_{x}$ from Definition 7 into $A^{\psi}$ defined
in Equation 30. Here we denote $A=A^{\psi}$, $\phi=\phi^{x}$ for simplicity.
We obtain:

$\displaystyle\left(A\phi\right)_{i}$
$\displaystyle=\underbrace{\sum_{j\in[m]}A_{i,j}\phi_{j}}_{\sum_{\text{$x_{j}$
in clause}}\phi_{j}-\sum_{\text{$\neg x_{j^{\prime}}$ in
clause}}\phi_{j^{\prime}}}+\underbrace{A_{i,\mathrm{pos}}}_{=Q_{\mathrm{pos}}}\underbrace{\phi_{\mathrm{pos}}}_{=1}+A_{i,\mathrm{neg}}\underbrace{\phi_{\mathrm{neg}}}_{=0}+\underbrace{A_{i,\mathrm{const}}}_{=k_{i}\frac{\varepsilon}{m}}\underbrace{\phi_{\mathrm{const}}}_{=1}$
$\displaystyle=\frac{\varepsilon}{m}\left(\sum_{\text{$x_{j}$ in clause
$i$}}\phi_{j}+\sum_{\text{$\neg x_{j^{\prime}}$ in clause
$i$}}\left(1-\phi_{j^{\prime}}\right)\right)+Q_{\mathrm{pos}}$
$\displaystyle=\frac{\varepsilon}{m}\sigma_{i}(\psi,x)+Q_{\mathrm{pos}}$

∎

######  Claim 8.

A 3-CNF $\psi$ is satisfiable if and only if the corresponding optimization
problem in Equation 25 attains a value of at least
$Q_{\mathrm{pos}}+\frac{\varepsilon}{m}$.

###### Proof.

If $\psi$ is satisfiable by assignment $x\in{\left\\{{0,1}\right\\}}^{m}$,
then $\sigma_{i}(\psi,x)\geq 1$ for all $i\in[n]$ by 6. Let $\phi^{x}$ denote
the vector corresponding to the satisfying assignment, according to Definition
7. Apply 7 to obtain:

$\displaystyle\left(A^{\psi}\phi^{x}\right)_{i}$
$\displaystyle=\frac{\varepsilon}{m}\sigma_{i}(\psi,x)+Q_{\mathrm{pos}}$
$\displaystyle\geq Q_{\mathrm{pos}}+\frac{\varepsilon}{m}$

Conversely, assume the optimal solution to Equation 25 is at least
$Q_{\mathrm{pos}}+\frac{\varepsilon}{m}$, and denote the vector attaining the
optimal solution by $\phi^{\mathrm{opt}}$. As the corresponding matrix
$A^{\psi}$, defined in Equation 30, satisfies the following for all $i\in[n]$:

$\displaystyle A_{i,\mathrm{pos}}=Q_{\mathrm{pos}}$ $\displaystyle\geq 0$
$\displaystyle A_{i,\mathrm{neg}}=-P^{(i)}_{\mathrm{neg}}$ $\displaystyle\leq
0$ $\displaystyle A_{i,\mathrm{const}}=k_{i}\frac{\varepsilon}{m}$
$\displaystyle\geq 0$

it can be assumed that the optimal solution $\psi_{\mathrm{opt}}$ satisfies:

$\displaystyle\phi^{\mathrm{opt}}_{\mathrm{pos}}$ $\displaystyle=1$
$\displaystyle\phi^{\mathrm{opt}}_{\mathrm{neg}}$ $\displaystyle=0$
$\displaystyle\phi^{\mathrm{opt}}_{\mathrm{const}}$ $\displaystyle=1$

because otherwise the value of any $\left(A^{\psi}\phi\right)_{i}$ would
increase by setting these entries in $\phi$ to the values above. Hence, we can
denote $\phi^{\mathrm{opt}}=\phi^{x}$ according to Definition 7, and apply 7
to obtain:

$\left(A^{\psi}\phi^{x}\right)_{i}=\frac{\varepsilon}{m}\sigma_{i}(\psi,x)+Q_{\mathrm{pos}}$

as the value attained is at least $\frac{\varepsilon}{m}+Q_{\mathrm{pos}}$, it
must hold that $\sigma_{i}(\psi,x)\geq 1$ for all $i\in[n]$, and therefore $x$
satisfies $\psi$ according to 6. ∎

##### Proof of hardness.

We are now ready to prove Theorem 2:

###### Proof of Theorem 2.

By reduction from 3SAT. Given a 3-CNF $\psi$ with $n$ clauses and $m$
variable, construct in polynomial time the corresponding matrix $A^{\psi}$ as
defined by Equation 30, and apply Equation 25 to obtain the optimal solution.
According to 8, the formula $\psi$ is satisfiable if and only if the value
attained in the optimization is at least
$\frac{\varepsilon}{m}+Q_{\mathrm{pos}}$, where $m$ is the number of variables
in $x$, and $\varepsilon,Q_{\mathrm{pos}}$ are constants defined in Equation
29,Equation 27 respectively. ∎

###  B.6 MLRP

In this section, we explore contract design under the MLRP assumption, and
prove Theorem 3.

######  Definition 8 (Mononote Likelihood Ratio – MLR).

The distributions $P,Q\in{\Delta\left({\Omega}\right)}$ have Monotone
Likelihood Ratio when $\frac{Q_{j}}{P_{j}}$ is monotonically increasing for
all $j\in\Omega={\left\\{{0,\dots,m}\right\\}}$. We denote this by $P\prec Q$.

An introduction to MLR and its properties is provided in Lehmann et al. [34,
Section 3.4].

######  Definition 9 (MLRP contract; Grossman and Hart [21]).

A principal-agent problem satisfies the Monotone Likelihood Ratio Property if
$F_{i^{\prime}}\prec F_{i}$ for every pair of actions $i,i^{\prime}$ such that
$c_{i^{\prime}}<c_{i}$.

######  Claim 9.

Let $P,Q\in{\Delta\left({[m]}\right)}$ such that $P\prec Q$. Then
$P_{0}>Q_{0}$ and $P_{m}<Q_{m}$.

###### Proof.

For the first inequality, assume by contradiction that $Q_{0}\geq P_{0}$.
Combining with the MLR property, this assumption implies that $Q_{j}\geq
P_{j}$ for all $j\in{\left\\{{0,\dots,m}\right\\}}$. As the outcome
distributions $P$, $Q$ are distinct, there exists at least one $j$ for which
$Q_{j}>P_{j}$. Summing over $j$ yields:
$\sum_{j\in\Omega}Q_{j}>\sum_{j\in\Omega}P_{j}$, which is a contradiction, as
the inequality is strict while both sides sum to $1$. The proof for the second
inequality follows in the same way. ∎

######  Definition 10 (MLR crossing point $j^{*}_{P,Q}$).

Let $P,Q\in{\Delta\left({\Omega}\right)}$ such that $P\prec Q$. The _crossing
point_ of $Q$ over $P$ is the outcome $j^{*}\in{\left\\{{0,\dots,m}\right\\}}$
such that $Q_{j^{*}-1}<P_{j^{*}-1}$ and $Q_{j^{*}}\geq P_{j^{*}}$. When
distribution are not clear from context, we denote $j^{*}=j^{*}_{P,Q}$

In words, the crossing point $j^{*}$ is the outcome such that for every lower
outcome, $P$ is strictly more likely than $Q$, and starting with this outcome
$Q$ is weakly more likely. By 9, the MLR crossing point $j^{*}$ is uniquely
defined for any $P\prec Q$, and it holds that $j^{*}>0$.

######  Definition 11 (Survival function).

Given $P\in{\Delta\left({[m]}\right)}$, the survival function
$\mathbb{S}_{{P}}({\cdot}):\Omega\to[0,1]$ is defined as:

$\mathbb{S}_{{P}}({j})=\mathbb{P}_{j^{\prime}\sim
P}{\left[{j^{\prime}>j}\right]}=\sum_{j^{\prime}=j+1}^{m}P_{i}$

Informally, the survival function is 1 minus the distribution’s CDF. This
function is useful in our context, since the total variation distance between
two distributions (as appearing in lemma 3) can be represented as the
difference between their survival functions when they satisfy MLR. The
intuitive reason for this is that MLR means the distributions are “single-
crossing”.

######  Claim 10 (Total variation under MLR).

Let $P,Q\in{\Delta\left({\Omega}\right)}$ such that $P\prec Q$. It holds:

$\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}=\mathbb{S}_{{Q}}({j^{*}_{P,Q}-1})-\mathbb{S}_{{P}}({j^{*}_{P,Q}-1})$

###### Proof.

By 4, it holds that:

$\left\lVert{{P}-{Q}}\right\rVert_{\mathrm{TV}}=\sum_{j\in{\left\\{{0,\dots,m}\right\\}}}\left(Q_{j}-P_{j}\right)^{+}$

Using the $j^{*}$ notation (see definition 10), we obtain:

$\sum_{j\in{\left\\{{0,\dots,m}\right\\}}}\left(Q_{j}-P_{j}\right)^{+}=\sum_{j=j^{*}_{P,Q}}^{m}Q_{j}-P_{j}$

And the result is obtained by applying the definition of survival function
(see definition 11). ∎

####  B.6.1 Two-action contracts with MLRP

Combining Lemma 3 with 9 leads to a characterization of threshold contracts in
the case of two actions:

######  Claim 11.

For any two-action contract design problem satisfying MLRP, the optimal
contract is a threshold contract:

$t_{j}^{*}=\frac{c}{\left\lVert{{F_{2}}-{F_{1}}}\right\rVert_{\mathrm{TV}}}\mathds{1}\left[{j\geq
j^{*}_{F_{1},F_{2}}}\right]$

where
$j^{*}_{F_{1},F_{2}}=\min{\left\\{{j\in{\left\\{{0,\dots,m}\right\\}}\mid
F_{2,j}\geq F_{1,j}}\right\\}}$ as in Definition 10.

###### Proof.

Combining the result of 9 with the monontonicity assumption, the likelihood
ratio $F_{2,j}/F_{1,j}$ crosses $1$ exactly once. Denote the crossing point by
$j^{*}$, and apply Lemma 3 to obtain the optimal contract. ∎

####  B.6.2 Two-outcome contracts with MLRP

When there are more than two actions, assume without loss of generality that
the contract aims to implement the last action $n$. The following claim
establishes the existence of theshold contracts in the two-outcome setting
${\left|{\Omega}\right|}=2$. In contrast to corollary 1, the proof in
constructive, and yields a concrete contract:

######  Claim 12.

For any contract design problem satisfying MLRP with $n>2$ actions and $m=2$
outcomes, the optimal min-budget contract is a threshold contract.

###### Proof.

By 2, the dual LP for two outcomes is given by:

$\displaystyle\max_{\lambda\in\mathbb{R}_{\geq 0}^{n-1},\mu\in\mathbb{R}_{\geq
0}^{2}}\sum_{i=1}^{n-1}(c_{n}-c_{i})\lambda_{i}$ (32)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\forall
j\in{\left\\{{1,2}\right\\}}:\sum_{i=1}^{n-1}\left(F_{n,j}-F_{i,j}\right)\lambda_{i}\leq\mu_{j}$
$\displaystyle\sum_{j\in{\left\\{{1,2}\right\\}}}\mu_{j}\leq 1$

From 9, we obtain that $F_{n,1}-F_{i,1}<0$ and $F_{n,2}-F_{i,2}>0$ for all
$i\in[n-1]$, and therefore the first constraint in
LABEL:eq:min_budget_two_outcomes_lp_dual_raw is always satisfied for $j=1$.
Simplifying LABEL:eq:min_budget_two_outcomes_lp_dual_raw we obtain:

$\displaystyle\max_{\lambda\in\mathbb{R}_{\geq 0}^{n-1},\mu\in\mathbb{R}_{\geq
0}}\sum_{i=1}^{n-1}(c_{n}-c_{i})\lambda_{i}$ (33) $\displaystyle\mathrm{s.t.}$
$\displaystyle\sum_{i=1}^{n-1}\left(F_{n,2}-F_{i,2}\right)\lambda_{i}\leq 1$

which is maximized by allocating all budget to the $\lambda_{i}$ maximizing
the “bang for buck”. The dual objective is therefore given by:

$\displaystyle B^{*}$ $\displaystyle=\max_{\lambda\in\mathbb{R}_{\geq
0}^{n-1},\mu\in\mathbb{R}_{\geq 0}}\sum_{i\in[n-1]}(c_{n}-c_{i})\lambda_{i}$
(34) $\displaystyle=\max_{i\in[n-1]}\frac{c_{n}-c_{i}}{F_{n,2}-F_{i,2}}$

To see that a threshold contract is optimal, let
$t_{j}^{*}=B^{*}\cdot\mathds{1}\left[{j=1}\right]$. Primal objective is
$B^{*}$, and the contract is feasible if the primal LP is feasible. The (IC)
constraint in Equation 5 can be written as:

$\forall
i\in[n-1]:\frac{\sum_{j=1}^{2}\left(F_{n,j}-F_{i,j}\right)t_{j}}{c_{n}-c_{i}}\geq
1$

and indeed for every action $i\in[n-1]$:

$\displaystyle\frac{\sum_{j=1}^{2}\left(F_{n,j}-F_{i,j}\right)t_{j}}{c_{n}-c_{i}}$
$\displaystyle=\frac{F_{n,2}-F_{i,2}}{c_{n}-c_{i}}B^{*}$
$\displaystyle=\frac{F_{n,2}-F_{i,2}}{c_{n}-c_{i}}\max_{i\in[n-1]}\frac{c_{n}-c_{i}}{F_{n,2}-F_{i,2}}$
$\displaystyle\geq 1$

And therefore $t^{*}_{j}$ is feasible in the primal problem, and also optimal
by strong LP duality. Also note that the resulting contract coincides exactly
with the optimal min-pay contract as attained by Dütting et al. [15, Lemma 7].
∎

####  B.6.3 General contracts with MLRP

In this section, we explore min-budget contracts in MLRP settings with more
than two actions and more than two outcomes. We start with a negative example,
showing that the MLRP assumption is not sufficient for establishing the
optimality of threshold contracts:

######  Claim 13.

For ${\left|{\Omega}\right|}>2$, there exists a design problem satisfying MLRP
for which the optimal contract is not a threshold.

###### Proof.

Consider the following contract design problem:

$\begin{aligned} F_{1}&\sim\mathrm{Binomial}(10,0.5)\\\
F_{2}&\sim\mathrm{Binomial}(10,0.65)\\\
F_{3}&\sim\mathrm{Binomial}(10,0.8)\end{aligned}\qquad\qquad\begin{aligned}
c_{1}&=0\\\ c_{2}&=0.45\\\ c_{3}&=1\end{aligned}$

The distributions are binomial, and therefore the contract satisfies MLRP.
Numerically solving Equation 10 yields the following fractional contract:

$t^{*}_{\mathrm{LP}}=(0,0,0,0,0,0,0,1.1,1.46,1.46,1.46)$

Numerically solving Equation 10 while imposing integer constraints
$\phi_{j}\in{\left\\{{0,1}\right\\}}$ yields the following contract, which has
higher max payout:

$t^{*}_{\mathrm{IP}}=(0,0,0,0,0,0,0,1.51,1.51,1.51,1.51)$

Thus for this case any threshold contract is min-budget suboptimal. A
graphical illustration of the proof is provided in Figure 7.

Figure 7:  Graphical illustration of 13. (Left) Outcome distributions
$F_{1},F_{2},F_{3}$ and MLR crossing point $j^{*}_{F_{2},F_{3}}$. (Center)
Crossing-point survival $s_{i}=\mathbb{S}_{{F_{i}}}({j^{*}_{F_{i},F_{n}}-1})$
as a function of cost $c_{i}$ (see definition 12). Note that the function is
not concave, thus the sufficient condition given in Theorem 3 does not hold in
this case. (Right) The min-budget contract $t^{*}_{j}$, given by numerically
solving eq. 10 (purple), and numerically solving eq. 10 while imposing integer
constraints $\phi_{j}\in{\left\\{{0,1}\right\\}}$ (cyan). Note that the
fractional LP solution achieves lower max payout.

∎

######  Remark 1.

The proof of 13 is provided with $m=10$ outcomes for ease of graphical
interpretation, however a minimal counterexample may also be constructed using
only $m>3$ outcomes. For example:

$\begin{aligned} F_{1}&=(0.5,0.3,0.2)\\\ F_{2}&=(0.3,0.4,0.3)\\\
F_{3}&=(0.1,0.35,0.55)\end{aligned}\qquad\qquad\begin{aligned} c_{1}&=0\\\
c_{2}&=0.45\\\ c_{3}&=1\end{aligned}$

Also note that a counterexample with $m=2$ outcomes is not possible due to 12.

The negative example shows that even with MLRP, the optimal contract
incentivizing the highest implementable action needs to rule out deviations of
the agent to all other actions, and not just to the second-highest one. This
makes the contract complex. We identify a natural economic condition that is
sufficient for considering only a single deviation (to the second-highest
action), resulting in a simple contract. Note that considering a single such
deviation is equivalent to restricting the action space to actions
${\left\\{{n-1,n}\right\\}}$.

######  Definition 12 (Crossing-point survival).

For a contract design setting satsifying MLRP, denote by
$j^{*}=j^{*}_{F_{n},F_{n-1}}$ the crossing point of the outcome distribution
corresponding to the highest action $F_{n}$, and the outcome distribution
corresponding to the second-highest action $F_{n-1}$. For any action
$i\in[n]$, the _crossing-point survival_ $s_{i}$ is defined as:

$s_{i}=\mathbb{S}_{{F_{i}}}({j^{*}-1})$

In words, $s_{i}$ is the probability to get an outcome at or above crossing-
point $j^{*}$ according to $f_{i}$. From an economic perspective, for every
action $i\in[n]$, $s_{i}$ is the agent’s probability to receive any nonzero
payment from choosing action $i$, if the contract is designed by restricting
the action-space to actions ${\left\\{{n-1,n}\right\\}}$. Note however that
the definition of $s_{i}$ does not require solving the contract problem for
actions ${\left\\{{n-1,n}\right\\}}$.

Figure 8:  Graphical intuition for the sufficiency condition in Theorem 3
(restated in Theorem 4). (Left) Outcome distribution in a contract design
setting satisfying MLRP, generated by a series of binomial distributions with
power-law expectation
$\mathrm{acc}_{D}(h_{n})=0.9-0.4\left(\tfrac{n}{100}\right)^{-0.3}$. The gray
dotted line represents the MLR crossing point $j^{*}_{F_{4},F_{5}}$ (see
definition 10). (Center) Crossing point survival $s_{i}$ as a function of cost
$c_{i}$ (see definition 12). It can be observed that the curve is concave.
(Right) The min-budget contract implementing action $5$. It is a threhsold
contract, as guaranteed by theorem 3. Compare to fig. 7, where the sufficiency
condition does not hold.

######  Theorem 4 (Concavity implies threshold contracts under MLRP; formal
statement of Theorem 3).

For a contract design problem satisfying MLRP, consider $s_{i}$ as a function
of cost $c_{i}$. If this function is concave, then the optimal contract is a
threshold contract.

###### Proof.

To prove this claim, we construct a relaxed version of the min-budget LP (eq.
5), and apply Lemma 3 in order to solve it. We then show that this solution is
also feasible for the original LP.

Given the min-budget LP, construct a relaxed LP by eliminating (IC)
constraints for all $i\leq n-2$:

$\displaystyle\min_{t\in\mathbb{R}_{\geq
0}^{\left|{\Omega}\right|},B\in\mathbb{R}_{\geq 0}}B$ (35)
$\displaystyle\mathrm{s.t.}$ $\displaystyle\forall j\in\Omega:t_{j}\leq B$
$\displaystyle\sum_{j\in\Omega}F_{n-1,j}t_{j}-c_{n-1}\leq\sum_{j\in\Omega}F_{n,j}t_{j}-c_{n}$

LABEL:eq:min_budget_lp_last_constraint only depends on $F_{n}$ and $F_{n-1}$,
and therefore 11 can be applied to obtain the optimal min-budget contract:

$t_{j}^{*}=\frac{c_{n}-c_{n-1}}{\left\lVert{{F_{n}}-{F_{n-1}}}\right\rVert_{\mathrm{TV}}}\mathds{1}\left[{F_{n,j}\geq
F_{n-1,j}}\right]$ (36)

Let $j^{*}=\min{\left\\{{j\in{\left\\{{0,\dots,m}\right\\}}\mid F_{n,j}\geq
F_{n-1,j}}\right\\}}$ as in definition 10, and denote
$s_{i}=\mathbb{S}_{{F_{i}}}({j^{*}-1})$. By 10, we obtain:

$\left\lVert{{F_{n}}-{F_{n-1}}}\right\rVert_{\mathrm{TV}}=s_{n}-s_{n-1}$

For all $i<n$, denote:

$b_{i}=\frac{c_{n}-c_{i}}{s_{n}-s_{i}}$

Using the definition of $b_{i}$, eq. 36 can be rewritten as:

$t_{j}^{*}=b_{n-1}\mathds{1}\left[{j\geq j^{*}}\right]$

By assumption, $s_{i}$ is a concave function of $c_{i}$, and therefore the
function $b_{i}$ is monotonically non-decreasing for all $i<n$:

$b_{n-1}\geq b_{i}$

Dividing both sides by $b_{i}$, we obtain:

$\frac{b_{n-1}}{b_{i}}\geq 1$

Plugging in the definition of $b_{i}$, and multiplying both sides by
$(c_{n}-c_{i})$:

$b_{n-1}\left(s_{n}-s_{i}\right)\geq c_{n}-c_{i}$ (37)

By definition of $t_{j}^{*}$, the expected payout of contract $t^{*}_{j}$
under action $i^{\prime}\in[n]$ is given by:

$\sum_{j=0}^{m}t_{j}^{*}F_{i^{\prime},j}=b_{n-1}\sum_{j=j^{*}}^{m}F_{i^{\prime},j}=b_{n-1}s_{i^{\prime}}$
(38)

Plugging eq. 37 into eq. 38 yields:

$\sum_{j=0}^{m}t_{j}F_{n,j}-\sum_{j=0}^{m}t_{j}F_{i,j}\geq c_{n}-c_{i}$ (39)

As eq. 39 is identical to the (IC) constraint in eq. 5, we obtain that
$t_{j}^{*}$ satisfies all the (IC) constraints in the original LP. From this
we conclude that $t^{*}_{j}$, which is a threshold contract, is also an
optimal contract with the respect to the full min-budget LP. ∎

##  Appendix C Experimental details

###  C.1 Data

  * •

LCDB: We base our main experimental environment on the LCDB dataset [37],
which includes a large collection of stochastic learning curves for multiple
learning algorithms and classification benchmark datasets. For each learning
method and benchmark dataset, the database includes held-out accuracy
measurements, obtained for exponentially-increasing training set sizes
$n\in{\left\\{{2^{4}=16,\dots,\mathrm{round}(2^{k/2}),\dots,2^{15}=32,768}\right\\}}$,
with multiple repetitions per $n$ obtained by cross-validation. For all
learning curves we consider in our analysis, and for each $n$, the number of
repetitions provided in the dataset is in the range
$R\in{\left\\{{5,\dots,125}\right\\}}$, where the specific number of
repetitions in LCDB depends on the algorithm and benchmark dataset (see the
dataset documentation for additional details). For each trained classifier,
each accuracy point on the learning curve is estimated using 5,000 held-out
samples. Formally, and using our notation, for each learning algorithm
$\mathrm{Alg}$ (e.g. MLP), dataset $D$ (e.g. MNIST), and training set size
$n$, LCDB provides a set of accuracy estimates
${\left\\{{a_{n}^{1,\mathrm{Alg},D},\dots,a_{n}^{R,\mathrm{Alg},D}}\right\\}}$,
such that each $a_{n}$ is distributed according to
$a_{n}\sim\mathrm{acc}_{D}(h_{n})$, where $h_{n}$ is a classifier trained
using training set $S\sim D^{n}$ and learning algorithm $\mathrm{Alg}$ (see
section 2 for definition of $\mathrm{acc}_{D}(h_{n})$).

  * •

Benchmark dataset and algorithms: In our main analysis, we focus on the
popular MNIST dataset [33, OpenML 554], and on multilayer perceptrons (MLP)
and gradient-boosted decision trees (GBDT) as representative classifiers. For
both classifiers, results are obtained for the respective default scikit-learn
[38] implementations (MLPClassifier and GradientBoostingClassifier).

  * •

Delegated learning settings from empirical data: For a given validation set
size $m$ where $m={\left|{V}\right|}$, we instantiate a contract design task
$(\mathcal{A},c,\Omega,F)$ as follows: (i) the set of actions with the set of
training set sizes provided by LCDB
($\mathcal{A}={\left\\{{2^{4},2^{4.5},\dots,2^{15}}\right\\}}$); (ii) action
costs are set to fixed per-unit cost, i.e., $c_{n}=n$; and (iii) the
distribution $F$ over outcomes $\Omega$ is associated with a binomial mixture
distribtuion, resulting from applying bootstrap sampling to empirical error
measurements:

$f_{n}=\frac{1}{R}\sum_{r=1}^{R}\mathrm{Binomial}(m,a_{n}^{r,\mathrm{Alg},D})$

where $a_{n}$ are the accuracy estimates defined above. Figure 2 (Left) shows
an example of such a setting, obtained by applying the above procedure to data
describing learning curves for the MLP algorithm trained on the MNIST
benchmark dataset.

###  C.2 Implementation details

  * •

Code: We implement our code in Python. Our code relies on Pyomo [10, 22] and
GLPK for solving linear and mixed-integer programs. Code is available at:
https://github.com/edensaig/delegated-classification.

  * •

Hardware: All experiments were run on a single laptop, with 16GB of RAM, M1
Pro processor, and with no GPU support.

  * •

Runtime: A single run consisting the entire pipeline takes roughly 10 minutes.
The main bottleneck is running the LP solvers, taking roughly 70% of runtime
to compute.

####  C.2.1 Contract design solvers

To find the optimal contracts, we implement and compare several different
solvers:

  * •

LP solver: To find min-budget contracts given outcome distributions
${\left\\{{f_{n}}\right\\}}$ and costs ${\left\\{{c_{n}}\right\\}}$, we solve
the MIN-BUDGET LP (Eq. (5)) directly using Pyomo and GLPK. Given budget $B$,
budget-optimal contracts are obtained by iterating through the actions set
$\mathcal{A}$, invoking the min-budget solver on each target action
$n\in\mathcal{A}$, enforcing incentive compatibility against all actions
$n^{\prime}<n$, and taking the action yielding the maximal expected accuracy
within budget (see section B.1). In our code, the LP solver is implemented
within the MinBudgetContract class.

  * •

MIP solver: To find optimal all-or-nothing contracts, we solve the MIN-BUDGET
LP in its statistical formulation (Eq. (10)) while restricting
$\phi_{j}\in{\left\\{{0,1}\right\\}}$. This turns the LP into a mixed-integer
program, which can be solved using GLPK in a way which is similar to the LP
solver. In our code, the IP solver is implemented within the
MinBudgetStatisticalContract class.

  * •

Local solver: To overcome numerical instability problems, we implement a
simple opportunistic solver which attempts to solve the MIN-BUDGET LP assuming
that only the last (IC) constraint is binding ($u_{n}(t)\geq u_{n-1}(t)$).
When only one (IC) constraint is binding, we can apply Eq. (3) to obtain the
min-budget two-action contract $t$. This method then checks that $t$ is indeed
incentive compatible with respect to all other actions. Figure 3 (Center)
shows that this contract leads to comparable performance to the full LP in the
case of MNIST with MLP. In our code, the local solver is implemented within
the MinBudgetLocalContract class.

  * •

Fixed-budget solver: To find budget-optimal threhsold contracts given a fixed
budget $B$, we implement a simple solver which iterates through all possible
threshold contracts $t_{j_{0}}(j)=B\mathds{1}\left[{j\geq j_{0}}\right]$ for
all $j_{0}\in{\left\\{{0,\dots,m}\right\\}}$. The solver then simulates the
agent’s rational choice (Eq. (2)) and selects the value of $j_{0}$ which
incentivizes the highest actions. In case of ties between possible values of
$j_{0}$, they are broken in favor of larger values, as this was shown to lead
to greater numerical stability. The fixed-budget solver is implemented within
the FixedBudgetThresholdContract class.

  * •

Full enumeration solver: To find all-or-nothing contracts for low-dimensional
problems and avoid numerical instabilities, we implement a solver which
performs full enumeration of all-or-nothing contracts. By the canonical
variable transformation in definition 1, the (IC) constraint in the MIN-BUDGET
LP translates to
$\sum_{j\in\Omega}\left(F_{i,j}-F_{i^{\prime},j}\right)\phi_{j}\leq(c_{i}-c_{i^{\prime}})\beta$,
where $i$ is the target action, and
$i^{\prime}\in\mathcal{A}\setminus{\left\\{{i}\right\\}}$. Thus, when
$\phi\in{\left\\{{0,1}\right\\}}^{\Omega}$ is fixed, the optimal $\beta$ is
given by:

$\beta^{*}(\phi)=\min_{i^{\prime}\in\mathcal{A}\setminus{\left\\{{i}\right\\}}}\tfrac{\sum_{j\in\Omega}\left(F_{i,j}-F_{i^{\prime},j}\right)\phi_{j}}{c_{i}-c_{i^{\prime}}}$

and optimizing $\beta^{*}$ over $\phi\in{\left\\{{0,1}\right\\}}^{\Omega}$
yields an optimal all-or-nothing contract. The full enumaration solver is
implemented within the FullEnumerationContract class.

  * •

Min-pay LP solver: To compare between min-budget and min-pay contracts
(Appendix B.3), min-pay contracts were obtained by solving the MIN-PAY LP (Eq.
(16)) using Pyomo and GLPK, similar to the full min-budget LP solver. In our
code, the min-pay is implemented within the MinPayContract class.

###  C.3 Empirical robustness estimation

Since our theoretical analysis relies on MLRP assumptions, we would like to
understand whether the results are applicable to real-world learning curves.
Towards this, we run an empirical robustness evaluation on the MNIST dataset.
For each learning algorithm $\mathrm{Alg}$, and training set size $n$, we
construct a delegated learning setting with $m=10$ and collect the following
statistics:

  * •

Min-budget: Optimal objective $B_{\mathrm{LP}}$ of MIN-BUDGET LP without
additional restrictions, implemented using the full LP solver.

  * •

Is MLRP?: Check whether all pairs $n_{1},n_{2}\leq n$ such that
$c_{n_{1}}<c_{n_{2}}$ satisfy the monotone likelihood ratio property (see
definition 9).

  * •

Is Monotone?: Check whether the resulting min-budget contract satisfies
$t_{j}\geq t_{j-1}$ for all $j\in[m]$.

  * •

Is threshold?: Check whether the resulting min-budget contract is a threshold
contract (i.e. whether there exists $j_{0}\in\Omega$,$B>0$ such that $t_{j}=0$
for all $j<j_{0}$ and $t_{j}=B$ otherwise).

  * •

Threshold budget: Optimal objective of MIN-BUDGET LP, when the resulting
contract is restricted to threshold form
$t_{j}=B_{\mathrm{Thr}}\mathds{1}\left[{j\geq j_{0}}\right]$. Implemented
using the full enumeration solver.

  * •

All-or-nothing budget: Optimal objective of MIN-BUDGET LP, when the resulting
contract is restricted to all-or-nothing form
$t_{j}\in{\left\\{{0,B_{\mathrm{AoN}}}\right\\}}$. Implemented using the full
enumeration solver.

  * •

Excess cost of threshold contract: The statistic
$\tfrac{B_{\mathrm{Thr}}-B_{\mathrm{LP}}}{B_{\mathrm{LP}}}$, indicating the
relative excess cost incurred by restricting the min-budget optimization space
to threshold contracts.

  * •

Excess cost of all-or-nothing contract: The statistic
$\tfrac{B_{\mathrm{AoN}}-B_{\mathrm{LP}}}{B_{\mathrm{LP}}}$, indicating the
relative excess cost incurred by restricting the min-budget optimization space
to all-or-nothing contracts. As all-or-nothing contracts are a superset of
threshold contracts, we expect this excess cost to be smaller than the one
associated with threshold contracts.

Table 2:  Empirical robustness estimation on the MNIST dataset. Each row corresponds to a learning algorithm, and columns are specified in section C.3. Results are averaged across all implementable actions.  | % MLRP | % Monotone | % Threshold | Threshold cost | AoN cost
---|---|---|---|---|---
MLP | 100% | 100% | 94.4% | 0.04% | 0.04%
GBDT | 100% | 100% | 82.4% | 0.71% | 0.71%
Logistic Regression | 93.8% | 93.8% | 93.8% | 0.76% | 0.02%
Perceptron | 68.8% | 93.8% | 93.8% | 0.00% | 0.00%
Linear SVM | 71.4% | 85.7% | 85.7% | 1.14% | 0.74%
Polynomial SVM | 100% | 94.4% | 88.9% | 0.24% | 0.24%
RBF SVM | 100% | 88.9% | 83.3% | 0.04% | 0.04%
K-NN | 100% | 100% | 100% | 0.00% | 0.00%

Averaging over all implementable actions, we obtain the results in Table 2.
From the table, we can observe that min-budget contracts assume a threshold
form in more than 80% of cases for all learners, indicating that our assumed
form of simple contracts is indeed present in a significant proportion of
cases. While this fraction is significantly lower than $100\%$, the associated
excess cost is relatively low (less than 1% for most algorithms). This
indicates that threshold contracts may provide good approximation to the
optimal min-budget contracts, even when min-budget contracts do not assume a
threshold form. We leave the theoretical exploration of these interesting
phenomena to future work.