Delegated Classification
Authors: Eden Saig
Inbal Talgam-Cohen
Nir Rosenfeld
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Delegation
Algorithmic Contract Design
Moral Hazard
Learning Curves
TL;DR: We develop a theoretical framework for incentive-aware delegation of machine learning tasks.

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.

Delegated Classification
Eden Saig, Inbal Talgam- Talgam-Cohen, Nir Rosenfeld
Technion Israel Institute of Technology Haifa, Israel
fedens, stai technion.ace ac.
Abstract
When machine learning is outsourced 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. game, in which accurate learning can be contracts. Adapting the
We model delegation as a principal- incentivized by the principal using performance-basse nomic theory of contract design to this setting, we define budget-optimal contracts and prove they take 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- PPaassnn lemma, establishing 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 eco- nomic outcomes are evaluated using synthetic and wellworld 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 practi- tioners. But machine learning has also become increasingly complex, cumbersome, and difficult to operate- and not all those who seek to learn have access the necessary expertise, infrastructure, and designated resources required for learning effectively. This gap has created a new market for outsourced machine learning, in which client interested obtaining an accurate predictive model can hire the services of specialized provider which, for 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 budget to expend on outsourced learning [51], we model the client as aiming to obtain the best possible predictive model. first glance, tempting to assume that the optimal strategy is simply to pay the provider the maximal feasible amount-and hope to get 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 provider, who interested in maximizing profit. Since the actions the provider remain private, it is in his best interest to (secretly) minimize efforts, which in turn can result in his delivering suboptimally trained model. our example, the provider can cut costs by annotating only a subset of the data, obtaining cheaper fow-quality annotations, or neglecting 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 specialized provider. Our key novelty instantiating delegated learning as problem optimal contruct design [10, 42, 47, 48). Broadly, contracts are an important monetary device that allows the client to establish payment scheme
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Principal
Agent
Private
Interaction
Private
Observe initial data; Design contract
Contract t: (0....
Reo
Strategically choose training set size n Sample data at cost ca. and learn à
Classifier i((x)
Sample validation set V ge Count correct predictions/ (b)
Payment (()
Receive (Q) monetary units
Figure I: Delegated classification interaction sequence. The principal examines initial information, and designs a contract / {Q,.....' . + Rzo. Having observed L, the agent strategically selects a dataset size n that will maximize his expected utility. He samples training set S ~ D", incurs cost On. then trains the classifier h E H and sends it to the principal. Upon receiving h. the principal evalu- ates its accuracy on a random validation set V D and pays the agent according to the contract t.
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 agent, who controls learning (in particular the training set) and is interested in maximizing profit. This allows us to model principal-agent relations Stackelberg game, in which the principal commits a contract 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 poofi-mmximizing 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 concavity, our main result here is that optimal contracts are simple, and in particular, take 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 closed-form solution for the optimal threshold contract. Providing an interpretation of the closed-form solution, our findings establish new connection between contracts and the renowned Neymon-Pearson lemma [45], which we consider as one of our central theoretical contributions.
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 and extrapolating). Using the recent LCDB dataset of learning curves [43], 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 tradeoff's 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.
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 [14], gathering information in [16], and computing a costly high-dimensional function in [5]. In the delegated task of [24], the agent provides classifier and the principal verifies its near-optimality within H. A fundamental difference is that their agent is assumed to be adversarial rather than rational, and so interactive proofs used instead of economic incentives.
The Neyman-Pearson lemma has recently been connected to economic design by [8] in the context of adverse selection rather than moral hazard. The agent has a hidden type (c.g., whether 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 Seyman-PPersonn A "moral" link between the design of contracts (for non-budgeted principal) and statistical inference (in particular likelihood ratios) was observed already in [25], but no connection was made to the power of hypothesis tests. Other intersections of ML and contracts that do not involve delegation of learning-relaan reeitiegrelledddee tasks include strategic classification [e.g., 36, 37, 3] and online learning of optimal contracts [29. 17, 52] Contract settings with a binary action and/or outcome space have been studied in [e.g., 20, 7, 22]. Not to be confused with our notion of delegation, there is a growing computational literature delegation without monetary payments [e.g.. 35].
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 function of dataset size and other exogenous factors [49]. There is growing empirical evidence that performance of modern neural networks can be predicted using simple scaling laws [e.g.. 34, 41, 50, 23, 2, 46, 30], and theoretical results that back these findings in simplified settings [11, 12, 33, 9].
Perhaps closest to ours is the concurrent work [4], which analyzes a similar setting under different assumptions: Rather than assuming budget constraints, they assume that the principal's utility is linear in accuracy and payout, and the learning curve takes specific functional form. Based on these assumptions, they derive approximately optimal linear contracts which are robust to adverse selection. In contrast, we obtain globally optimal simple contracts based on hypothesis testing, and present data-driven methods handle partial information. Together, the two studies demonstrate the important role of simple contracts in the growing ecosystem of machine learning delegation.
2 Problem Setup
The core of our setting is based on a standard supervised classification task. Let x. E X be features and y )' be labels, and assume there is some unknown joint distribution D over (x. y) pairs. Given a sample set S = {Z }= ~ D", the goal in learning is to use to find a classifier h : X + y from class H that maximizes expected accuracy, (c) = I' (a (f(rr) y/. Because the estimated by the empirical average
underlying distribution D is unknown, expected performance
on an additional held-out validation set V ~ D of size m, as accy (h) 1 Σ [h(x;) Wel. which is a consistent and unbiased estimator of accp (h). We will assume throughout that both the learning algorithm and the validation set size are known and fixed.
Learning on budget. We will be interested in studying learning when certain resources limited or costly. Our main focus will be on the setting where the main cost of learning is the number of labeled examples but we note that our approach can in principle extend to other forms of learning 'effort'.' We assume the learner has a monetary budget B to spend on samples, and is interested in maximizing accuracy under budget constraints. Let Cn. 0 be the cost of n samples (assumed to be increasing in n),, then the learner aims to solve:
nt argmax,, En., (t.))) s.t. C. B
where ha is a classifier learned from a random dataset of size |S| = n. Note that h2 is a ran- dom variable with distribution depending on n. We denote the out-of-sample accuracy of hn by on = accp monotonically in n, then n in Eq. (1) in naturally the largest affordable n (see Sec. 3). However, as we will see, when learning is delegated -hht seemingly straightforward observation can break.
When the learner is a self-sufficient entity, and when the expected a, improves
Delegation. We model the delegation of learning as conceptual partition 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 '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 know 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
For example. [34] argue that not only training-ser set size, but also computation time and model size are related accuracy through scaling laws, which have tight connections the assumptions we discuss in Sec. 3.
3

---

Delegated classification setting
Different contracts with budget
Agent's perspective: Maximize utility
Outrome dist ributiisoons f.
10
Ukilky s.ikky s.10
1.0
Action (training sin)
1000
constant
32
16
[1000 ungpettbb e2o)) 1o
thmehhald
linear
0.5
100
1000
178
Paymert
600
Action (training wet sta))
250
512
Principal's s perspective: Accuracy
1024
2048
200
0.5
4706
8192
0.0
0.0
0.5
1.0
0.00
01.25
0.00
0.77
1.00
conslant
linnar Contract
threshald
Outcome (validation sccuracy)
Outcome (validation accuracy)
Figure 2: A delegated classification setting (data from Sec. 4). (Left) Each costly action taken by the agent (training set size n) induces distribution fn. of possible outcomes (classifier accuracy). The principal seeks to construct a contract t that incentivizes a profit-maximinn entailing favorable outcomes. Note the fa exhibit increasing expectation, but decreasing variance, in (Center) Three contracts for a given budget B, mapping outcomes to payments. (Top-right) Agent's utilities th (t) and best responses nt) (stars) for each contract f. (Bottom-right) Expected accuracies for principal resulting from each contract; here the threshold contract is optimal (see Sec. 3).
agent to take actions
larger payments to entail larger n, and therefore higher-accuracy h. However, 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 an information gap between the two parties. This creates a conflict of interest for the agent known as moral hazard [10], 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 [31]: pay-per per-perffrrmacce rules that a-priori determine future payments for every possible outcome, which we formally describe next.
Contract design. A contract setting is defined by set of actions A {01,...,,ay .x)) that can be Each action a; is associated increasing
taken by the agent, and a set of possible outcomes j E {O....,m) m]. with a cost C;, and w.l.o.g. we assume ei I S cN so that actions correspond effort levels. The agent's 's choice to perform action E A yields a random outcome j ~ fo for the principal, where fa 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 (O.....m) + Rzo. according to which she pays the agent t(j) 2 0 when the materialized outcome is j. Given contract t, let ua (t) be the agent's expected utility from taking action a E A at cost Ca (via stochastic outcomes j ~ fa), and let a(t) be the agent's 's best response- an action that maximizes his expected utility (and following standard tie-breaking assumptions as in [18)). Then:
uaa (t) = Eg>s,((()) Car
a(t) E argmax,c. (t)
(2)
Every action a" that is the best response economic terms, the principal and agent are playing a Stackelberg gume, in which the principal commits to a contract i and the agent best-responds by choosing action a(t) that maximizes his expected utility u. (t). The goal of the principal is to design a contract i. which incentivizes the agent to take best-response actions yielding favorable outcomes for the principal.
a(t) to some contract is called implementable. In
Contracts for delegated learning. We propose formulate delegated learning as problem of optimal contract design, instantiated as follows. First, we relate agent actions a with the number of samples n, and denote A = .., n.N) the possible sizes of S that the learning agent can work with. The cost of acquiring samples naturally maps as Cu = Ca. and agent's 's best response a(t) ntt). 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 accy (h) = j/m. and we will therefore use j and accy (h) as 'outcomes' interchangeably. Finally, for an action we set fn to be the distribution over possible accuracies obtained when learning with n samples, namely fj) = Ph,,, Jaccy (hx, = j/m] Vj. We will also use the matrix form Fny = (j), where F E [0, (m)+)), Note that admits two sources of variation: variation in ht due to stochasticity in S D"; and (ii) a-posteriori variation in j for any fixed h.
(i) a-priori

---

due to stochasticity in V ~ D When h, is fixed, the outcome distribution admits simple binomial form, namely j Binomial(m, a,)). Empirically, we observe this to be the dominant component.
2.2 Delegation
optimization problem
Budget-optimal contracts. Recall that the principal seeks to maximize accuracy under budget constraints (Eq. (I)). Once learning is delegated to an agent and framed as a contract design problem, the principal's 's objective becomes:
4rgmax, (m. Ex..o (acct(()())))
Contract 1* is chosen incentivize the agent to invest effort nn() (via Eq. (2)) such that the training of ha()) 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. Delegated learning settings have actions n and costs Cp. known to both sides, and outcome distribution Fnj known the agent. For the principal, 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 characterizing the optimal contract. In Sec. 4 we relax this assumption, and explore a partial-infommatin setting in which the principal relies instead on an empirically--stimatee curves F.
3
Budget-Optimal Contract Design
3.1 The problem
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 who, after delegation, received 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 received an uninformative S by chance, and delivered a low low-quality h as result; and (ii) the agent invested low effort (small n)). Since 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 strategic) agent can hide behind the uncertainty that is inherent in learning outcomes.
Contract types. To overcome this informational gap, the principal must devise a contract to align in- centives 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 to the detriment of the principal.
Linear contract (i(j)= Bj/mn m)): The agent is paid fraction of B, linear in the resulting accuracy. Linear contracts are a popular and extensively-studies class of contracts [e.g., 32, 15]. Nonetheless, and though seemingly sensible, linear contracts turn out to be sub-optimal for our setting.
Threshold contract (1(z)= = B1 [j 2 jol for some ja): The agent is paid B provided the empirical accuracy surpasses threshold jo In the example in Fig. 2, the threshold contract is optimal.
Rather than committing a-priori to some type of contract, we seek find the best budget-optimal contract by solving Eq. (3). For this it is useful to have structure.
Stochastic learning curves (and where to find them). Our approach uses the observation that there is a tight connection between the set of distributions {fn} encoded in F, and learning curves, which describe the anticipated accuracy of a classifier 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, stochastic learning curve is defined precisely by F. This connection is useful because learning curves have structure: First, expected learning curves are typically monotone [34, 1 I]; when not [43, 49], they can be monotonized [12]. Second, stochastic learning curves likely satisfy the monotone likelihood ratio property (MLRP), which states that the better the performance of classifier, the more likely it was trained on more data (see Def. 1).
'The agent also hide in the uncertainty due to V. particularly when is small; see experiment in Sec. 4.2.
5

---

Table 1: Characterization of simple min-budged contracts in different settings. Simple contract forms include all-or aul-or-non or-nothing contracts and 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 Shyman-Peaasopn lemma), or that the simple form is non-optimal or intractable.
Problem size
Structural assumptions
Actions
Outcomes
No assumptions
MLRP
Concave-MLRP
A
= 2
any size
All- All-or-nothing (T1)
Threshold (B.7.1)
m 1 2
All-or-nothing (B.5.1)
Threshold (B.7.2)
A
> 2
m 1 > 2
Simple is NP-hard (T3)
3 non-threshold (B.7.3) Threshold (T4)
3.2 Optimization via min-budget contracts
Our main technique for solving Eq. (3) relies on reduction to what we refer to as min-budget contracts. Given an (implementable) target action n* E A. mudnebudeet contract for n a contract that incentivizes the agent to employ precisely the action n', while minimizing the maximum payment by the principal ||t|| max {t()); i..., t implements n* minimum budget. Formally:
argmin, ||
s.t. nlt) n
Our reduction relies on the following claim (Proof in Appendix B.1):
Proposition 1. Every budget-optimal contract design problem has an optimal solution which is also min-budger.
Using Prop. 1, a solution to Eq. (3) can be obtained by iteratively solving Eq. (4): For all n, E A, solve Eq. (4) with target action n²" = ny. and return t" (m:) for the best implementable whose budget does not exceed B. The budget-optimal problem thus reduces to solving multiple min-budget problems.
To compute each t" (n:) in Eq. (4), we formulate a novel MIN-BUDETT linear program (LP),² detailed in Appx. B.2. One way to solve this LP is with generic solvers approach which 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 show that binary-action contracts have all-or-nothing structure (!(i) E {0, BJ), and plausible structural assumptions on the learning curve give rise to threshold contracts (f())= = B1 [j jol for some jo). Our theoretical results are summarized in Table 1, and detailed in the rest of the section.
3.3 All-or-nothing contracts: Binary action space and the statistical connection
We begin with a simple delegated learning setting in which the agent can choose one of two actions, A {n1, ( e.g.. 'small' vs. 'large" training set, and the principal seeks to incentivize training with more data. 4 This reduced case will be useful as a building block for the general case (which we re- turn in Sec. 3.4), and for making a precise connection between contract design and hypothesis tests.
Simple min-budget contracts for binary action space. Our first result shows that optimal binary-action contracts are all-or-nothing contracts whose budget determined by the total variation distance between outcome distributions fa and fI, namely f| - fillrv = Σÿ= lf2.3 fisl-
Theorem 1 (Optimal binary-action contract). In binary-action contract setting with outcome distributions fi, f2 and costs C1, C2 the min-budget contract is an all-or-nothing contract, given by:
t' tt))= B1 [f2()) 2 f101 Vj E (O....,, where B = (ea (aa--a)/lla---lll
(5)
The proof (in Appendix B.4.2) is by LP duality. Intuitively, the optimal contract pays the agent for outcomes that are more likely to come from f/ than from f1- Moreover, it requires a higher budget
the smaller the distance is between the two distributions f1, fz. At the extremes, if their distance is 1 (i.e. no overlap among their supports), the required budget for incentivizing n2 is C2 C₁ whereas their distance O (i.e. fi = f2) it becomes impossible to incentivize 122-
'The BUDGET LP is closely related to well well-known MIN-PAY PAY LP from non-budgeted contract design [e.g.. 19], but with different objective, and hence very different optimal solutions (sce Appx. B.3). When is not the target when it is not implementable, then the solution is immediate: always pay C1.

---

Formal connection to optimal hypothesis testing. Theorem 1 also uncovers a direct conre spondence between optimal contracts and optimal hypothesis tests. Intuitively, given the outcome distributions {Ji, J2]. and in order to incentivize na, the principal wishes to pay the agent if the observed outcome j E {O...., m] is more likely to have originated from f2- The principal can attempt to identify whether the outcome j is drawn from distribution f1 or f2 through hypothesis testing, where a hypothesis test & (0...., m) + {0, 1} maps a sample j to either f2 (indicated by I) or to the null hypothesis fi (indicated by 0). For our purpose it is convenient to allow tests to be non-integral, in which case & : {O...... m - [o, 1] maps j to a probability with which originates from f2- The quality of a hypothesis test is measured by summing its type-1 I and type-2 errors: f1.04 + Σm
2i=0 f2. (1 - ) The test that minimizes this sum is known as the most powerful hypothesis test, and has been characterized by Neyman and Pearson [45, 4.3].
We now turn to formally establishing the connection. For a fixed B, observe that every contract with budget B can be mapped to hypothesis test via the bijection (i) = <JY/B. Then:
Theorem (Optimal contract vs. test). Consider binary-action contract design with distributions fi, f2 and costs 01 C2- A contract t with budget B is optimal if and only if its corresponding hypothesis test 1é / is maximum power with type-1 and rype-2 errors summing to 9
The proof (Appendix B.4.2) is by a non-linear variable transformation to the MIN-BUDGET LP. Theorem 2 implies that the optimal contract for the binary-action case (Theorem 1) is equivalent to the well-known Eeyyaan-Pearoon lemma characterizing the most powerful hypothesis test:
Lemma (Neyman-Peary) Pearson [e.g., 45]). Let f1. be two discrete probability distributions. Then the most powerful hypothesis test for f1; f2 is the likelihood ratio test (i) 1 (m2(]) 2 f(()), which attains the optimal bound 1 - 1p - Ulrv on the sum of lype- and rype-2 errors.
Theorem 2 establishes a new formal connection between the two domains of contract design and hypothesis testing. In the context of contract design, it provides a statistical interpretation: A min- budget contract can be interpreted as an optimal hypothesis test, and the ability to distinguish between the two hypotheses determines the required budget. In the converse direction, it enables a new proof for the Neyman-Pearson using the min-budget contract given by Theorem 1 (see Appendix B.4.2).
3.4 All-or-nothing contracts: Beyond binary action
For general action spaces, optimal contracts are not guaranteed to be all-or-nothing. In fact, we show that determining whether there exists all-or-nohhig contract that is optimal is NP-hard:
Theorem 3 (Hardness). Finding min-budget all-or-nothing contract is NP-hard.
The proof is by reduction from 3SAT, and appears in Appx. B.5.2. Nonetheless, there are special but important cotel-notably the binary outcome case in which results from Sec. 3.3 hold, suggesting that ideas from Thm. apply more broadly. The following algorithm makes use of these ideas, showing good empirical performance, and provable performance under an MLRP condition (Sec. 3.5).
Single binding action algorithm. Revisiting the closed-form all-or-nothing contract in Eq. (5), we observe that the result is based on the fact that binary action spaces have only one alternative action. Building upon this observation, we propose the single binding action (SBA) algorithm, which computes a solution to Eq. (4) in the general (many-actions) case: Given target action n² E AA loop over all actions n # n²", and apply the closed-form formula in Eq. (5) to obtain an (all nothhing) contract t" (n. n²) If the agent's 's best response (Eq. (2)) satisfies n (t" (n.n")) = n". return t". If the loop ends without returning contract, return 'fail'. The following claim shows the algorithm sound:
Proposition (Soundness of SBA). When the single binding action algorithm terminates successfully, it returns optimal contract which is an all-or-nothing contruct.
Proof in Appendix B.6. Prop. 2 ensures that if SBA succeeds, then the returned all-or-nothing contract t" is optimal. Moreover, failure does not preclude the existence of an optimal all-or-nothing contract. If SBA fails, we solve Eq. (4) with generic LP solver. Empirically, SBA was successful in more than 85% of cases, and is ~00 times faster than the LP solver (Appendix C.3). Thus, this optimistic 'try SBA first' approach typically succeeds, adds negligible overhead if not, and guarantees correctness.
"In this case there are binary outcomes (m = 1), such as when the agent's efforts can result in either success or failure [6, 28, 21J. For this case, show that the optimal contract is also all all-oinnothing (Appx. B.5.1).
7

---

3.5 Threshold contracts: MLRP assumption
In this section we provide sufficient conditions, in the form of natural structural properties (stochas- tic) learning curves, that guarantee the optimality of even simpler contracts contracts-namely threshold contracts and the success of SBA. With inspiration from hypothesis testing [40] and contract theory [26, 19], it is natural to consider the monotone likelihood ratio property (MLRP) assumption:
Definition 1 (MLRP [e.g., 26)). A contract design setting satisfies MLRP if for every pair of actions a, such that co Ce', the likelihood ratio I,, f./ is monotonically increasing in j.
In our context, MIRP states that the better the validation-set performance of a classifier, the more likely it was trained on more data. This holds in particular for monotone learning curves with binomial outcome distribution [19, B.1]. For a binary action space, MLRP ensures that n2 is always implementable." and that the optimal contract is a threshold contract: t (G) = B1 [i 2 jol. This is by Theorem 1, and by the fact that Eio such that f2(1)/()) 2 1 iff j 2 jo (see also Appendix B.7.1)? Interestingly, this is similar to the relation between the Neyman- Paannoo lemma and the Karlin-Rubin theorem, which characterizes the most powerful hypothesis test under monotone likelihood ratio [40].
MIRP for general action space. MLRP does not guarantee threshold contracts in general: In Appendix B.7.3, we give a constructive counterexample satisfying MLRP, but for which the optimal contract is not threshold. However, refining MLRP to also capture 'diminishing returns' turns out to be sufficient for recovering guarantees generally. For target action a,, denote the survival probability of an action a; by 8, f- [i 2 j*] where j is the minimal outcome at which action ay is more likely than ax-1- These will serve as formal means for capturing the concavity of learning curves.
Definition (C-MLRP). contract design setting satisfies Concave-MLRP (C-MLRP) if satisfies MLRP, and additionally the actions' survival probability is concave as function of the actions' cost.
Our final result shows that C-MLRP guarantees optimality of threshold contracts, and success of SBA:
Theorem 4 (Sufficiency for threshold). Consider contract design setting with C-MLRP. Then the optimal contract is a threshold contract, and is recovered by the SBA algorithm.
We prove this claim by showing that concavity implies that only one alternative action is binding in the linear program equivalent to Eq. (4), reducing the problem to the two-action case. By applying Theorem 1, obtain optimality of threshold contracts in this case as well (proof in Appendix B.7.3). This also implies that SBC always terminates successfully on inputs that satisfy C-MLRP.
In practice, we believe that C-MLRP is reasonable assumption for realistic learning curves: in Appendix B. we prove it is satisfied by standard theoretical model of learning curves, and in Ap- pendix C.3, empirically demonstrate that it is (approximately) satisfied in settings where threshold contracts are optimal. Interestingly, in our empirical study, threshold contracts were often optimal even when C-MLRP did not hold- suggesting the condition is sufficient, but not necessary (see Sec. 4.1).
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) [43], 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 E {2+,2 provide with stochastic learning curves. Here focus primarily the popular MNIST dataset [39] as our case study, and on MLP and GBDT as representative classifiers, but we refer the reader to Appendix C for further experiments additional datasets and methods. Code is available at: https:/ //g thub. com/ edensaig g/ /elegated-
215) }. with multiple repetitions per n; these
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.
6 As a corollary of similar result for min-pay contracts [19, Lemma 7J.
This also holds for binary outcomes in arbitrary action space, Appendix B.7.2.
8

---

MNIST learning curves
Required budget for 85% accuracy
Which algorithm less costly to delegate?
MLP
10a
AB
Accuricy anr
0.8
Required buriget B"
90000
GBDT
dWW
102
0.6-
20000
MLP
10000
0.8
-107
1082
CRDT
-10*
10? Size of training set n
20
0.5
0.0
0.7
0.5
Size of volidation set
Target accunacy (1
Figure Delegating with full information. (Left) Typical learning curves for two learning algorithms 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 learning algo- rithms: Multi-Layere Perceptron (MIP) and Prradient-Bosster Decision Trees (GBDT). We take an arbitrary accuracy point the curve at aco(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 a larger required budget 8*, which holds for all m. As m increases, required budgets and the difference between them both decrease. 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 (target action costs ).
Budget regimes. Fig. 3 (left) also indicates two points in which the learning curves cross (dashed lines), at ~00.7 and ~0.94 accuracy. These correspond to sample sizes n for which both methods obtain matching accuracies (in expectation). For self-sufficient learner, the implication is that at each these points, both methods are equally costly, i.e., both cost Cn 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, A = B BML-- 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=217/2 samples to obtain ~0.74 accuracy, GBDT is cheaper (AB*= = 10²); for ~ 0.94 which requires n=23170022 2==22700229// from both, GBDT is significantly more expensive =10),. The reason for this that optimal budgets are determined by the ability to distinguish between distributions (Sec. 3.3).
Prevalence of simple contracts. To understand the applicability of our theoretical findings, in Appendix C.3 we conduct an empirical prevalence evaluation on additional learning algorithms, and across target actions. We observed that min- contracts assume a threshold form and the SBC algorithm returns correct results in more than 85% of cases overall. Restricting optimization to simple contracts, budget requirements were generally less than 1 % higher than that of a min- budget contract, suggesting that simple contracts may provide good approximation even when min-budget contracts do not assume simple form.
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 small 'pilot' dataset of size k. where i is considered small. Using this set, the principal creates an estimated learning curve f by fitting a curve accuracies obtained for up to some no S k. and extrapolating to larger n > vig- In particular, we experiment with fitting parametric power-law curves of the form E[a,]] empirically and theoretically [49, 34, 11]. Since plwer-law curves are monotone, composition with binomial distributions increasing in p provably results in MLRP stochastic curves [19, B.I].
be- which have been shown to provide good fit in various scenarios both
tradeoff. Given 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 ng to be small but with more samples per n < nig (low variance), or setting no to be large but with few samples per no (low bias). We define r the number of samples per n (so low means larger no)). Then, for

---

Different sampling strategies
Extrapolation convergence
Cost-efficiency
1.0
Attained (cco
0.9
Sizc nuttpler - mttl/2
30-
Rel in delogation
Expett accuracy
0.G
-0%
1.0
0.8
20-
-40%
0.5
0.7
60%
2.0
16-
0.6
Obserss.
0.5
Median
-100%
107
102
107
10P
-0.0 -04
-0.2
0. 022
Training
Exploration
Pilot cataset
Estrapolation residual mit")
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 samples due to delegation. (Right) Implications of over vs. under-esting ender-estimation.
given r, we set no such that En<no S k (i.e., such that the total number of used samples does not exceed k). Fig. 4 (left) shows different curve fits for 31,3,5 5]. and corresponding Agg Then, Fig. (center-left) shows for a certain fixed budget the accuracy level that can be attained for increasing k, and as function of r. As can be seen, having sufficient points k for constructing is important, but performance grows quickly with & (note log-scale x-axis). It is also apparent in our example that low bias (via larger no) is much more important than low variance for constructing useful F.
Cost-efficiency tradeoff. Because the pilot set provides the principal basic means for obtaining minimal accuracy, we can ask: given & examples, and for a fixed budget B, what is the added benefit of delegating learning? For this, we define yu(} n(f)/E lk to be the sample-size multiplier, i.e., the multiplicative gain in the effective number of samples due to delegation. Fig. 4 (center-right) (which superior terms of performance and outcomes), begins at ~ 10, increases to ~00 at around k = 190, and slowly decreases back to ~0 towards & = 1, 000. For r > 1, we observe that ~ 1, i.e., there effectively no gain from delegation, until around k 100, only after which some gain is restored. This highlights the importance of obtaining accurate estimate F in terms of the economic consequences of delegation.
shows (k)) for increasing i and across For
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 target incentivized number samples n(t*) the relation between the (theoretical) signed extrapolation error nttt) (i.c., over- or under-estiman 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 farvenfitting instance, with points shown for varying k. ng. and r, and with multiple independent repetitions. Results show that in the under- estimation regime (i.e., negative extrapolation error), loss in accuracy degrades gracefully with the estimation error. stark contrast, even minimal over-estimation (positive extrapolation error) causes accuracy to plummet dramatically, as the agent's rational response in those cases was to use the smallest dataset possible. We interpret this as a consequence of "setting the bar too high' aagh'-a rational decision minimize effort in response to unrealistic expectations. 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.
Discussion
Motivated by the increasingly-common practice of outsourcing learning tasks, this paper sets out 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 means for aligning them. Our analysis relies on set of assumptions, which should be carefully considered by practitioners and empiricists alike; we also believe that there are likely further fruitful connections explore between contracts and statistical hypothesis testing. As 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 to partial knowledge as is often the case [19].
10

---

The authors would like to thank Ruth Heller, Shafi Goldwasser, Jonathan Shafer, Ohad Einav, and anonymous reviewers 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 data science. Funded by the European Union (ERC, ALGOCONTRACT, 101077862, Pl: Inbal Talgam-Cohen).
Ackmowledgements.
References
[1] Milton Abramowitz, Irene A Stegun, and Robert H Romer. Handbook of mathematical functions with formulas, graphs, and mathematical tables, 1988.
[2] 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.
[3] Tal Alon, Magdalen Dobson, Ariel D. Procaccia, Inbal Talgam-Cohen, and Jamie Tucker-Foltz. Multiagent evaluation mechanisms. In AAAI 2020, pages 1774-1781, 2020.
[4] Nivasini Ananthakrishnan, Stephen Bates, Michael I Jordan, and Nika Haghtalab. Delegating data collection in decentralized machine learning, arXiv preprint arXiv:2309.01837 2023.
[5] Pablo D Azar and Silvio Micali. Computational principal-agent problems. Theoretical Eco- nomics, 13(2):553-578 2018.
[6] Moshe Babaioff, Michal Feldman, and Noam Nisan. Combinatorial agency. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 18-28, 2006.
[7] Moshe Babaioff, Michal Feldman, Noam Nisan, and Eyal Winter. Combinatorial agency. Journal of Economic Theory, 147(3):999-1033) 2012.
[8] Stephen Bates, Michael I Jordan, Michael Sklar, and Jake A Soloff. Principal-agent hypothesis testing. arXiv preprint arXiv:2205.068) 2022.
[9] Devansh Bisla, Apoorva Nandini Saridena, and Anna Choromanska. A theoretical-empiree approach to estimating sample complexity of dnns. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3270-3280, 2021.
[10] Patrick Bolton and Mathias Dewatripont. Contract theory. MIT press, 2004.
[11] 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 Theory of Computing, pages 532-541, 2021.
[12] Olivier Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, and Uri Stemmer. Monotone learning. In Conference Learning Theory, pages 842-866 PMLR, 2022.
[13] Michael L. Bynum, Gabriel A. Hackebeil, William E. Hart, Carl D. Laird, Bethany L. Nicholson, John D. Siirola, Jean-Pau Watson, and David L. Woodruff. Syomo-optimizzn modeling in python, volume 67. Springer Science & Business Media, third edition, 2021.
[14] Yang Cai, Constantinos Daskalakis, and Christos H. Papadimitriou. Optimum statistical estimation with strategic data sources. In COLT 2015, pages 280-296, 2015.
[15] Gabriel Carroll. Robustness and linear contracts. American Economic Review, 105(2):536-563, 2015.
[16] Junjie Chen, Minming Li, and Haifeng Xu. Selling data to a machine learner: Pricing via costly signaling. In International Conference Machine Learning, pages 3336-3359. PMLR, 2022.
[17] Alon Cohen, Argyrios Deligkas, and Moran Koren. Learning approximately optimal contracts. In SAGT 2022, pages 331-346, 2022.
[18] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Coheen Simple versus optimal contracts. In EC 2019, pages 369-387, 2019.

---

[19] 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.
[20] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In FOCS 2021, pages 815-826, 2021.
[21] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Combinatorial contracts. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 815-826. IEFE, 2022.
[22] Paul Dütting, Tomer Ezra, Michal Feldman, and Thomas Kesselheim. Multi-agent contracts. In STOC 2023, 2023. To appear.
[23] Behrooz Ghorbani, Orhan Firat, Markus Freitag, Ankur Bapna, Maxim Krikun, Xavier Gareia, Ciprian Chelba, and Colin Cherry. Scaling laws for neural machine translation. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. httpstt:::: opw.revieerreeeeeeeeeeeeee net/forum?idsee Bt-thh_SMMBxxCW
[24] Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive proofs for verifying machine learning. In /2th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl-Leibniz-Zenneee
für Informatik, 2021.
[25] Sanford J. Grossman and Oliver D. Hart. An analysis of the principal- -agent problem. Econo- metrica, 51(1):7-45, 1983.
[26] Sanford Grossman and Oliver D Hart. An analysis of the principal-agent problem. In Foundations of insurance economics, pages 302-340. Springer, 1992.
[27] William E Hart, Jean-Paul Watson, and David L Woodruff. Pyomo: modeling and solving mathematical programs in python. Mathematical Programming Computation, 333)2219-200 2011.
[28] Chien-Ju Ho. Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsoureing markets: Bandit algorithms for repeated principal-agent problems. In Proceedings of the fifteenth ACM conference Economics and computation, pages 359-376, 2014.
[29] 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.
[30] Derek Hoiem, Tanmay Gupta, Zhizhong Li, and Michal Shlapentokh- Rothomnn. Learning curves for analysis of deep networks. In International conference on machine learning, pages 4287-4296. PMLR, 2021.
[31] Bengt Holmström. Moral hazard and observability. The Bell Journal of Economics, 10(1): 91, 1979.
[32] Bengt Holmstrom and Paul Milgrom. Aggregation and linearity in the provision intertemporal incentives. Econometrica: Journal of the Econometric Society, pages 303-328, 1987.
[33] Marcus Hutter. Learning curve theory. arXiv preprint arXiv:2102.04074, 2021.
[34] 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 orX.v.2001.08361, 2020.
[35] 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.
[36] Jon Kleinberg and Manish Raghavan. How do classifiers induce agents invest effort strategi- cally? In EC 2019, pages 825 844, 2019.
[37] Jon Kleinberg and Manish Raghavan. Algorithmic classification and strategic effort. SIGe- com Exch., 18(2):45-52, 2020.
12

---

[38] Sébastien Lahaie. How to take the dual of a linear program. Columbia University, New York, 2008.
[39] Yann LeCun. The MNIST database of handwritten digits. http://yann. lecun. com/exdb/mnist/ 1998.
[40] Erich Leo Lehmann, Joseph P Romano, and George Casella. Testing statistical hypotheses, volume 3. Springer, 1986.
[41] Rafid Mahmood, James Lucas, David Acuma, Daiqing Li, Jonah Philion, Jose M Alvarez, Zhiding Yu, Sanja Fidler, and Mare 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.
[42] David Martimort and Jean-Jacques Laffont. The theory of incentives: the principal- model. Princeton University Press, 2009.
[43] Felix Mohr, Tom J Viering, Marco Loog, and Jan N van Rijn. Ledb 1.0: An extensive learning curves database for classification tasks. Machine Learning and Knowledge Discovery in Databases, ECMLPKDD, accepted. Lecture Notes in Computer Science, Springer, 2022.
[44] 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 Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-22 2830, 2011.
[45] Phillippe Rigollet and Christian Hütter. High dimensional statistics. Lecture notes for course 185997, 81 813(81 1))44., 2015.
[46] Jonathan S. Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://
[47] Royal Swedish Academy of Sciences. Scientific background on the 2016 Nobel Prize in Economic Sciences, 2016.
[48] Bernard Salanie. The Economics of Contracts: Primer. MIT press, 2017.
[49] Tom Viering and Marco Loog. The shape of learning curves: a review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[50] Mengzhou Xia, Mikel Artetxe, Chunting Zhou, Xi Victoria Lin, Ramakanth Pasunuru, Danqi Chen, Luke Zettlemoyer, and Veselin Stoyanov. Training trajectories of language models across scales. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023, pages 13711-13738. Association for Computational Linguistics, 2023. doi: 10. 10.18653/V1/0023.ACC -LONG.767.
[51] Xinyi Zhao, Weixin Liang, and James Zou, Data budgeting for machine learning. arXiv preprint arXiv:2210.00987, 2022.
[52] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I. Jordan. The sample complexity online contract design. In Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page 1 1188, ACM, 2023. doi: 10. 30771757/5
13

---

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-makee alike. At the same time, it is important to remember that our work- as others considering economic aspects of soaming-studinn delegation in a simplified setting and under certain assumptions. As such, and since devising and agreeing to legally- contracts can have concrete implications on real-world out- comes, 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 unclear a-priori if and how our statements and conclusions carry over to this setting. As another ex- ample, notice that our formalism considers a one-shot setting where a single contract between 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 '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. Nonethe- less, 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.
B Min-budget contract design deferred proofs
Notation. To align with traditional contract design notation, in this section, we denote the action space by A= [n] (1..... n), and the outcome space by 5 {o...... m) We denote by (X) the set of distributions over given set X. For contract design problems, we denote the outcome probabilities by F such that F; E A (It) is the outcome distribution associated with action i, and also denote the cost of each action by Ct- Given E R. we denote x+ ReLU(xx) max {0, x).. We denote the indicator function by [.]. the total variation distance between distributions P. Q by ||P QllTy (see Definition 4), and the survival function of P A (2) by Sp(-) (see Definition 14).
A note on individual rationality. In the contract design literature, contract is said to be incentive compatible (IC) with respect to some action a if it satisfies ua- (t) 2 ua (t) for all actions a E 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 s expected utility is always nen-negative (un- (L) 2 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 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 noo-neggaivee.Morooveer even in cases where zero-loss action does not exist, we show that individual rationality (IR) can be attained in a straightforward manner, by adding the minimal cost ej to each entry of an incentive compatible (IC) contract (t, + t, + c1):
Claim 1. Given an IC contract t with C₁ > 0, the contract t c1 (add C₁ to every coordinate of the contract) is both IC and IR.
Proof. An IC contract implementing action a" satisfies u (1) 2 (4), for all actions E A. In particular, this inequality holds in relation to the least-costly action, denoted by 1 E A. Plugging the definition of the agent's s expected utility (Eq. (2)), we obtain ua- > Eynsh [t] C1- Thus, under
14

---

the mapping t33 = Egg + C1, it holds that:
No. (t') uda (t c1) 2 Bz~ +i] C1
E
and therefore the contract 1' + ci individually rational still implements action a".
B.1 Relation between budget-optimal and min-budget contracts
Proof of Proposition 1. Given budget B >> 0, denote by (B the budget-optimal contract, and denote the action it implements by n". By definition, /Bo is feasible solution to the min-budget contract design problem implementing action n". Denote by İMB the corresponding optimal solution to the min-budget problem implementing action n' (Eq. (4)). ÊMB implements the same action n² by definition, and satisfies ||tMB Il < (o <. B due to the optimization objective. Hence, (MB is budget-optimal contract for the given budget B, which also min-budget.
Iterative min-budget. To find the budget-optimal contract using iterative applications of Eq. (4), we observe that any budget-limeen limited contract Ω [0, B] has bounded expected pay E,, [t] B for any distribution fn. Hence, actions n' with cost C,'' B cannot be implemented using budget B, as the agent's 's utility u f., Cn' < 0 will be smaller than the utility of the zero-cost action M4 = E, [t] - 0 2 0. Define the reduced action set:
A' (n A Cn S n is implementable)
A' is finite when 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 E A', calculate the minimal budget B,, required for implementation, and take argmin B, This is possible within finite number of steps.
B.2 The min-budget linear program and equivalent forms
The min-budget contract (Eq. (4)) implementing action i E AA is given by the MIN-BUDGET linear program:
min
B
re BER2o
s.t.
(6)
Vj E Ω: SB
B
(BUDGET)
W +i: De cr S Σ
Figly Gi
(IC)
JEG
JER
The dual of the min-budget LP is given by:
Claim 2. The dual linear program of Eq. (6) is given by:
Σ
(a- - Cz. A
max XERY HER 20 pzi
[R]
s.t.
Vj Ω Σ (Fis - Fv.s) Ae S/4
Σ S1 $1
JEN
Proof. We take the dual by translating the optimization problem into canonical form. The canonical form we target:
min cT x s.t. Cr #20
and its dual, as given by Lahaie [38], is:
max d' s.t. yoyz- -c 920
To translate Eq. (6), note that in the components c.C,d are given by:
15

---

cf = (0
0 1) E E 11++
[+++1
Fi,0 Fi,
Fi.111 Fa
:
F Fij
C=
Fn,0 Fi.
F Fm.m Fim
0
R (m (1=1+100(((1+11)
1 m+1
df = (cI
Gp C
0
0)
E R R0-1+
To simplify formulation, we denote the dual optimization variable as follows:
y==(A (A1 Ai-1 A4t1 ...An
pm) mm--++0
no
Under this formulation, the dual's objective is:
-d
Σ
(a (a--ah cx) Av
$#
The constraints given by the first m rows of CT are:
Vj: Σ
(Frs - Fi.)) + #3 20
and equivalently:
Vj e Ω: [F Fr Si
(9)
The constraint corresponding to the last row of C is given by:
Σ
Um
JEN
and equivalently:
Σ
pm
S
(10)
JER
Combining equations (8, 9, 10) yields the linear program given by Eq. (7).
To map between contracts and hypothesis tests, we introduce the following variable transformation:
Definition 3 (Statistical representation of contracts). For a given contract t: Ω R2 denote
B = max, 15- The statistical representation of t is given by:
ty 0
where dy E [0,1] and 3 = B-1
Note that the transformation (1, B) + (d, (8) is non-linear, and well-defined for all B 0. Under this variable transformation, the MIN-BUDEET transforms to equivalent linear program:
16

---

Lemma 2. For a feasible design problem, the min bain-budget linear program (Eq. (6)) is equivalent to:
B
6 1I ,E332
s.t.
(11)
Vi' + Fis(1 - +5) - E Fe S (q cc
jEN
JEN
Proof.
Given Eq. (6), define & E [0, 10 3 2 0 according to Definition 3:
B 3 1 = 33 B = 05
(12)
Under the transformation defined by Eq. (12), the (BUDGET) constraint in Eq. (6) transforms as follows:
fj S B + , 3- S
(13)
0 1
and the (IC) constraint Eq. (6) transforms as:
Pigl a Pusty
- cv +> Σ (Fig - Pv.)) F 1 2a- -
+ Fidds E Peoog 2 (a cc) B
(14)
1
Σ [P,(1-0b))
-b)) - Fridj 2 (a: (x)-c)) 8
- -1, - Σ Frido S (c: - -c)) B
where the first equivalence is by Eq. (12), and the third equivalence valid as E, Fr. = 1 for all Finally, the objective of Eq. (6) transforms as:
min B + max 3
(15)
Combining equations (13, 14, 15) yields the linear program in Eq. (11).
B.3 Relation to min-pay contract design
Min-pay contract design aims design contract which minimizes the expected pay under the implemented action n*:
argmin, Rj-fa- [b]] s.t. nn() = n
(16)
In contrast the min-budget contract (Eq. (4)), the ||t|l objective measuring maximal pay is replaced with the E, [ty] objective measuring expected pay. Eq. (16) is equivalent to the MIN-PAY linear program:
min
Σ Fig4
ER [9] 20 JEN
s.t.
(17)
V :: FF Cy S F -4 (IC)
jEN
JEN
B.3.1 Equivalence of implementability
The implementatbility of min-pay contracts is characterized in Dütting al. [19]. We cite the main result for completeness:
Proposition 3 (Min-pay implementability; [19], A.2). An action i E A is implementable (up to tie-breaking) if and only if there no convex combination of the other actions that results the same distribution = Ex Oue fe, but lower cost e, Ever Cy Co.
17

---

Outcome distributions
Min-pay min-budget contracts
f
MIN
0.30
MIN-BUDGE
Paymunt 1,
20
0.15
0.0
2.5
7.5
12.5
0.0
3.0
10.0
12.5
15.0
Outcome
Outcome
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 (P1 = 0.5, P2 0.8, m 15). Action has zero cost c O, and action has unit cost C2 (Right) The resulting min-pay pay (red) and min-budget (purple) contracts, obtained by solving Eq. (17) and Eq. (6), respectively. The min-pay awards payment only for the highest outcome, in alignment with Proposition 4; the min-budget is threshold contract, in alignment with claim 12.
We leverage to Proposition 3 to characterize the implementability of min-budget contracts. This possible due to the following connection:
Claim (Implementabilityy equivalence). A contract is feasible solution of MIN- MIN-BUDGEE BUDGET if and only if is feasible solution of MIN-PAY.
Proof. A contract t which satisfies MIN-BUDGET (Eq. (6)) satisfies the (IC) constraint, and thus also satisfies MIN-PAY (Eq. (17)). Conversely, a contract which satisfies MIN-PAY satisfies the (IC) constraint. Set B = max, iz and obtain a feasible solution to MIN-BUDGET.
B.3.2 Functional form of min- pay contracts under MIRP
The optimal min-pay contracts under the MLRP assumption (Definition 1) characterized in [19]:
Proposition (Optimal min-pay contract under MLRP; [19), Lemma 7). Consider a contract design setting for which MLRP holds. the highest-cost action n is implementable, then there is min-pay contract has a single monzero-paymenn which is rewarded for the highest outcome m.
See Fig. for qualitative comparison of min-pay and min-budget contracts.
Min-pay contracts in delegated classification settings with MIRP. While simple, the min-pay contract given by Proposition 4 would be impractical many realistic scenarios delegated classi- fication. delegated classification setting, the highest outcome corresponds 100% validation set accuracy (i.e all validation set samples classified correctly). As m grows, the highest outcome becomes exponentially less likely, and the min-pay contract awards increasingly high payment with increasingly low probability (See Fig. 6). In such settings, even slight degree of risk-aversion is likely to affect the agent's 's decisions: From the agent's 's perspective, the probability of receiving any payment from a min- min-pay contract may become small to degree where even slight degree of agent risk-aversion will manifest itself in the decision-making process. From the principal's perspective, even though min-pay contracts guarantee small payment in expectation, the amount payment in the case of a rare event would quickly become unfeasible.
B.4 Min-budget contracts with two actions
In this section, we explore min-budget settings with two actions, and prove Theorem When = 2, assume without loss of generality that the contract implements action i = 2, and denote c = C2 C1 > 0.
We recall the definition total variation distance:
Definition 4 (Total variation distance), Given two distributions P,Q e A (12, the total variation
distance between P and Q is:
|P Ql
P Ql
18

---

Expected pay
Required budget
Probability of any payment
22 106
10
MIN BUDGET
109
18x 106
C -
10'
x 10
x4x I0P
102
122x 10
10
10
10
30
20
50
10
Validacion
Validation sEE size
Via Validation set size
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 Fig. 5: two binomial -ottooee actions (P1 0.5, Pa 0.8) and varying m. Action 1 has zero cost C1 0, and action has unit cost Co In the left and center plots, the cost of action is represented by an orange line (cy = 1) representing the lower bound as Fig. (Center). (Tefft) Expected pay [ [ty]- (Center) Required budget || (Right) Probability of getting any payment fa~fal? (t3 > 0).
The following equivalent definition is useful:
Claim 4. Let P,Q (9). holds:
PP- 11-Q E (Q,
jEN
where x max {a, 0).
Proof. By definition:
|P -P- Qllv = |P Q11
Decompose the L norm:
h |P - - Σ (10,- - PP)*
+ +P, -Q,)*
JEN
As EjER 23=E Qj = 1, holds that:
(P-
JEN
jEB
and therefore P Q1 = Ejen (Q, pT)** as required.
B.4.1
Optimal two-action contract
Theorem 5 (Two-action min- min-budget contract; formal statement of Theorem 1), When = 2, the optimal min-budget contract t" given by:
t
[F2. 2 FiJl
(18)
F2 FIlITV
Proof. We prove this claim using LP duality, by showing that the optimal primal objective corre- sponding to 1" is identical to a feasible solution the dual L...
The primal LP (Eq. (6)) for two actions is given by:
min
B
(19)
KRR RER
BER
s.t.
Vj E vJEN:455
(BUDGET)
Σ (Fay - F1,)) 2
(IC)
jen
19

---

As t" is bounded, the optimal objective B" corresponds to the maximal possible payout of t":
B max JEG
(00)
F2 F1 Fillrv
and therefore the (BUDGET) constraint is satisfied. For the (IC) constraint, denote by f2 the following set:
? = (je F2. 2 Fi,2)
using this notation, we note that > 0 if and only if E Uzz Plugging into the constraint, we obtain:
- Ez -Fes--Fi.t
E (F2. - Fi.)) B
Jenz
= Ejeag (F2.) Fi.))
|F/ FFillr
=c
Where ||2 Fi FillTy = EjEng (F2,) Fi,)) 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 identical objective. By Claim 2, the dual LP for two actions is given by:
max cA AER ZER laj 20
s.t.
(21)
VjE Ri)))
11
Denote the vector (A( E IR [0]
(A) (P2s F13)
We note that outcomes j' for which F25' Fi,"' (formally j' 2 1z2) correspond constraints which are satisfied for any X 2 0. Otherwise j E Ωzz and in these cases X can be increased until ((A) saturates the simplex constraint Σjen P. 1. The simplex constraint is binding for value
x 0 satisfying:
Σ x (F2, - FI,))= =1
JEN
and therefore the optimal value X of the dual LP (Eq. (21)) is:
ch* Ejeo (Fas - Fi.))* | Filly
(22)
Where the second equality is given by claim 4. The dual objective in Eq. (22) is identical to the primal objective attained by the contract 1" in Eq. (20), and therefore is an optimal contract by strong LP duality.
B.4.2 Contracts and hypothesis tests We recall the formal definition of the Neyman-Pcarson lemma:
Lemma 3 Dlyymnn-Peasson [e.g., 45, 4.3D). Lei P, e A (X) two probability measures over an arbitrary set X. Then for any hypothesis test v X - {0,1], it holds:
P(b(()) 1) Q(((x) 0) > - ||P Q1
(23)
Moreover, equality holds for the Likelihood Ratio test 2t (z) 1 (9(x) 2 p(.))
20

---

In our analysis, we will assume that the space A' is finite. We also note that Lemma is stated for decision rules with binary output, but its domain can be extended to fractional decision functions vb : X + [0, 1J without loss of generality: As the sum of emrors is linear in v. the optimal fractional decision rule a solution to the linear program min vefo,11 (P 1) + Q 0)) where P(t
1) = E.Ex (x) and Q = 0) ExEx Jx - (x)).. The feasible region of this linear
program is the hypercube [0, 1] and its vertices are the set of binary decision rules {0, 1)* which also includes the optimal binary rule v given by Lemma 3. As every feasible linear program attains its optimum on vertex, the binary * is also the optimal among fractional rules.
Proof of Theorem 2. For given two-action contract, denote Pj Fi.j- Qj F2.j. and c c1- We recall that the statistical min-budget LP for two actions is given by Lemma
max @E(0,1] ,3E220
s.t.
(24)
Σ
PJdj + e -1-
JER
jEN
and the Joyman-Pearsonn lemma is given by Eq. (23).
Given min- min-budget contract design problem, apply Theorem to obtain its optimal solution, as given by Eq. (18):
13
P Ql
tj QlIv
1 10, Pz]
Applying the transformation from Definition the optimal contract, obtain equivalently:
8" = -B | Qllrv
1 10 Pzl
Note that Φ is maximum likell--oioeiieoddd decision rule, similar to the optimal critical function in the Neyman-Pearson lemma. Additionally, by optimality of the contract-design optimization variable 3*' any feasible solution ø' of Eq. (24) satisfies:
m P + J=1
EP ( 3=1
with equality satisfied by the maximum likelihood rule d" Therefore, the min-budget optimality of contract implies the power optimality of the hypothesis test 6²
Conversely, let Φ Ω + [0, 1] be an maximal-powe -oower hypothesis test. This provides a lower bound on the constraint in Eq. (24):
Σ P3d + 20 JER
- ),) 2 P Q1
JEN
By the Neyman-Peune Pearson lemma, the bound is tight for the maximum likelihood rule o' = 1 iQ 2 P), and therefore the optimal objective 8 satisfies:
1 1- =1-11 Ql
and hence 3 Pl-Q Applying the transformation in Definition 3 yields the optimal contract 1 - (2, 2 Pj). showing that the corresponding contract is min-budget optimal the corresponding hypothesis has optimal statistical power.
Remark Since the proof of Theorem is independent of the Neyman-Pearson Pearson lemma, the argument proving the optimality of o" in the proof above implies the Neyman- Peerson lemma for finite X.
21

---

B.5 More than two actions
Definition (All-or-nothing contract). Let B O. An all-or-nothing contract &: Ω -> Rgo satisfies E (0, BJ for all j E f
B.5.1
Binary outcomes
In this section, we show that every binary-outcome min-budget contract is all-or-nothing. This is corollary of more general lemma:
Lemma 4. For wny feasible min-budget contract 1", there exists jo Z such that 17 O.
Proof. By contradiction, assume that 1j 0 for all j. and denote jo argmin, 4j. Denote a = miny 1y, and note that a > 0. Define the contract as follows:
Vj: ty
By definition, f 2 for all j. and to = O. Since is feasible min-budget contract, it satisfies the min-budget LP in Eq. (6), and in particular the (IC) constraint:
E [n 1]: R S
Fastj
Plugging in the definition i == t* and using the fact that Ej Fig 1 for all i [n], obtain:
Vie in 1] F a $ Σ Fn,tt Cn
and therefore 7 satisfies the (IC) constraint as well. This is a contradiction, since i feasible contract with a lower required budget. From this we conclude that the optimal contract must satisfy = 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 Hardness: Basic definitions and construction
In this section, we show that finding optimal all-or-nothing contracts NP-hard in the general case, by reduction from 3SAT.
Definition 6 (Maximin design matrix). For a contract design setting with action set A, outcome space Q target action A, and Ca < Ca for all a E A \ {a*}, the maximin design matrix A is defined as:
Far
Fa,w
Aas
(25)
Claim 5. For contract design problem, denote the maximin design matrix A. An all-or-nothing min-budget contract 1" can be wrillen as 1" = 0" 13", where:
o² argmax min (Aø)
(26)
8 min (Ae"), (EA)(e)
Proof. By Lemma 2, Eq. (11), the min-budget contract design LP is equivalent to:
0
6E(0.1) R
s.t.
Va A [a'):
Σ
Fat w Faw
Oh 3
Ca+ - Ca
22

---

Where B-1 As An, therefore equivalent to:
Pau it holds that Ewer
Par
Dw = Ad. The LP above
Ca--Ca
max 6E(0,1] BER
s.b.
Va A {a")= A.0
8 is a lower bound for every constraint, its optimal value is the maximal minimum attainable through variation of Φ::
max $E[o,1] nEAA((a))
min
(Ae)
and restricting the optimization space of Φ to {0, [ yields the desired result.
n
Definition 7 (3-CNF Conjunctive normal form). A 3-CNF formula over m variables and clauses is a boolean-valued fumction fumction & 1), + {0,1) 1} of the form:
, mm) A
(za V 222 23)
where 2n E {Z1,...... Fm. 2
We assume that variables in each clause are distinct. v is satisfiable and only there exists {0, 1)"" such that (b(z) 1.
Definition 8 (Number of positives in clause i). Given a 3-CNF ub and an assignment x E {0, 13", denote ()) E .0.....3) the number of variables 24k in clause which evaluate 1 under assignment I.
Claim 6. A formula vb is satisfiable if and and only if there exists an assignment {0, 13th th such that minje[n] (1 x) 1.
Proof. If &b is satisfiable then there exists x E 10, such that (xx) = 1. Since 3-CNE, every clause must evaluate to and therefore az (w. x) for all [n]] Conversely, if there exist an assignment I such that min,e (1b,,, x) 2 then by definition r satisfies every clause, and therefore the whole formula v/.
B.5.3 Hardness: Reduction from 3SAT
Given a 3-CNF & with n clauses and m variables, we define a min-budget contract design problem over actions A [n + 1] and outcome space f [m] {pos, neg, const). The target action is a" = n + 1, and the cost associated with action é is:
{
i=n+1
=
(27)
otherwise
For simplicity of notations, let e >> which will be assigned suitable value later in the construction. The outcome distribution of the target action is denoted by Q, and defined as:
E
Vj E [m]] Q,
3
Q pos
1 -
1 +
(28)
Q Qneg = 0
const 36
772
Note that Q is well-defined for > 3 and 1
23

---

For each i E [z), denote the number of negated variables in clause i by & E {.....,3) 3). The
distribution corresponding to the i-th action is denoted by p(), and defined as:
Jy exists clause
Vj E [m] Pja
25
I exists in clause
otherwise
p() = =0
pos
(29)
p(3 1
m
p( (3
ki)
const
The distributions p() well-defined when and
2- For concreteness, set:
(30)
10
and note that Qpos and Prog are both strictly positive for m 2 3 and this value s.
Plugging equations (27, 28, 29) into Definition 6, the maximin design matrix A R corresponding to the contract design problem above is given by:
I exists in clause and is not negated
Vj E [m]] A
I exists in clause and is negated otherwise
1 i.pos = Q pas
(31)
A Ai.ee
p(()
nigg
A /const k;
Definition (Assignment normalized contract). For an assignment & E {0, 1)"h the corresponding m+3
normalized contract 6t E 1) is:
Vj
E
[m]
$ = Izj
pos
(32)
P
uee
Pconst
Claim 7. Let dh be a 3-CNF, and E (0, 1)th an assignment. For all i E [m]: (A*
(, Q Qpos
m
Proof. To prove this claim, plug &r from Definition 9 into A defined in Eq. (31). To simplify notations, here denote A A oz {2,1, 422 233. We obtain:
(AØ); =
Σ
Aww
wE(m] Ufpus (ews, cog.
Aig
A Ai,pos Spos Aineg pueg
Ai.onnt Dconst
jE(m]
Qpor
=ks
Er, e b3- E E-ggrEn 03')
Σ 0
Σ (1-6,) + Opos
m
B3 E
-.,, E 21
(3/),, x))
pos
77
24

---

Claim 8. For given 3-CNF tb, denote by 6" the optimal solution for Eq. (26), with == A There exists an assignment x² such that o" o=
Proof. For the maximin matrix A defined in Eq. (31), the optimization objective in Eq. (26) is:
min (A* 1);
ieIn
By the choice of e in Eq. (30), A satisfies the following for all E [x]]
A pos
Q pos > 0
Aineg
p(()
0
neg
A,,onst
Ks
0
m
Thus, any optimal solution o² must satisfy:
Φ pos
0 neg
const
Otherwise, the value of any (A*Φ); would strictly increase by changing the value of 8i at the coordinates {pos, neg, const) to the values specified above. This would increase the optimization objective (in. (A*h (6) contradiction the optimality of s-.
Hence, denoting 2 = 6 for all E [m], we obtain ø² 6² as required.
Claim 9. A 3-CNF va is satisfiable if and only if the optimization problem in Eq. (26) with A A satisfies 3 2 Qpos +
Proof. If sp is satisfiable by assignment x E f0. 1}"h, then (v), 2 for all E [n]] by Claim 6. Observe that 3 = (A**") for some i" E [n] by construction. Let 6² denote the vector corre- sponding the satisfying assignment, according Definition 9. Apply Claim 7 to obtain:
8 = (A **))
e
x) + Qpes
E 2 Q pos +
Conversely, assume the optimal solution to Eq. (26) satisfies 3* 2 Qpos -, and denote the vector attaining the optimal solution by o' By Claim there exists an assignment such that d² d" Combining the lower bound on the value of the optimal solution with the result of Claim 7, we obtain that the following holds for all i [m]:
(A" 1000") ),
E
E Qpos
0, x²) + Q 2
Therefore, must hold that a; (1/, x²) 2 1, and thus satisfies y according to Claim
B.5.4 Proof of hardness
Proof of Theorem 3. By reduction from 3SAT. Given a 3-CNF 1b with clauses and m variables. construct in polynomial time the corresponding matrix A as defined by Eq. (31), and apply an optimal solution. The validity of the LP is given by Eq. (26). By Claim 9, the formula & is satisfiable if and only if the value attained in the optimization
all-or-nothing min-budget contract solver according to Eq. (26) to obtain
least 5 + Qposs where m the number of variables z and Q pos constants defined in Eq. (30), Eq. (28) respectively.
D
25

---

B.6 The single binding action algorithm
To prove the soundness of SBA, we first make the following definition:
Definition 10 ((i'ICC relaxation). Consider a MIN-BUDOS LP with target action A, as given by Eq. (6). For any action i' & i, the (V-ICC relaxation of the min-budgel problem is given by eliminating all (IC) constraints except for the one corresponding to action i'
Proof of Proposition 2. Denote the target action by E A. On each iteration of the loop, the algorithm considers some action i' * i, and applies Theorem on the (i'ICC relaxation of the original MIN-BUDGET LP. Since the relaxed LP has only one (IC) constraint, its optimal solution, denoted by to (i', i), is given by Eq. (5).
By Definition 10, the feasible region of the original LP lies within feasible region corresponding to its (i'-IC) relaxation. Thus, if an optimal solution of the relaxed LP lies within the feasible region of the original LP, then it also global optimum of the original LP. (i', .) lies within the feasible region of the original LP is it satisfies the remaining (IC) constraints- condition equivalent to the
notation att" (1', i)) = by Eq. (2). The SBA algorithm terminates successfully only in such cases,
and therefore it is sound.
L
note on ties in SBA. Denote the target action by i. To simplify presentation, the algorithm presentation in Section 3.4 implicitly assumes that required budgets (i', i) are distinct for every pair of actions (i', i), and therefore the return value of SBA is well-defined. In case of ties, the return value is not well-defined (as the iteration order is not well-defined), but small modification the algorithm allows ties to be broken explicitly without affecting other properties of the algorithm: In case of ties in optimal required budget, the soundness of the algorithm and the all-of-nothing property of the returned contracts is not affected. However, the exact functional form of the returned contract may be affected by the iteration order. case such issue becomes relevant, the SBA algorithm can be modified to first collect set of optimal contracts (instead of immediately returning when an optimal feasible contract found), and then select one of the optimal contracts based on the desired criteria. As the proof of Proposition 2 does not depend on iteration order, soundness will not be affected, and worst-case time complexity will remain the same.
B.7 MIRP
In this section, we explore contract design under the MLRP assumption, and prove Theorem 4. We first recall the statistical notion of monotone likelihood ratio:
Definition 11 (Mononote Likelihood Ratio - MLR). The distributions P.Q E A (S) have Monotone Likelihood Ratio when Q, is monotonically increasing for all E Ω = {O..... m). We denote this P,
by P < Q
An introduction to MLR and its relation to statistical hypothesis testing is provided in Lehmann et al. [40, Section 3.4]. Using this notation, we can reformulate Definition 1:
Definition 12 (MIRP; reformulation of Def. 1 using MLR notation). A principal-agen problem every
satisfies the Monotone Likelihood Ratio Property if Fv eorerr pair of actions i, such that
Cy < Ct.
Claim 10. Let P.Q E A ([m)) such that P x Q. Then Po > Qo and Pm < Qm.
Proof. For the first inequality, assume by contradiction that Qo 2 Po. Combining with the MLR property, this assumption implies that Q, 2 P, for all j E {0..... .......... As the outcome distributions P.Q are distinct, there exists at least one for which Q, > P.. Summing over j yields: Σjen Q, > Ejen P3. which is contradiction, as the inequality is strict while both sides sum to 1. The proof for the second inequality follows in the same way.
Definition 13 (MLR crossing point jp.q)) Let Let P.Q E A (9)) such that x QQQ. The crossing point of Q over P is the outcome j' E (O...., m. such that Q5- < P and Q2- 2 Pj.. When distribution are not clear from context, we denote j = Jr.q
26

---

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 weakly more likely. By claim 10, the MLR crossing point j" is uniquely defined for any P x Q, and it holds that j > 0.
Definition 14 (Survival function), Given P E A ([m]), the survival function Sp(.) :2 + [0, is defined as:
Sp(1) = PPy>PPi 5
Σ
P.
y'j++1
Informally, the survival function is minus the distribution's 's CDF This function useful in our context, since the total variation distance between two distributions (as appearing in Theorem 5) 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-crossingg.
Claim 11 (Total variation under MLR). Let P,Q E A (9t such that P - Q. It holds:
P - QU Solinq - 1) - -p 1)
Proof. By Claim 4, holds that:
|P - Q1 = Σ
(Q) -
jE (o......
Using the j* notation (see Definition 13), obtain:
Σ (Q-- Σ
Q- P3
j=
And the result obtained by applying the definition survival function (see Definition 14).
B.7.1 Two-action contracts with MIRP
Combining Theorem with Claim 10 leads to characterization threshold contracts in the case of two actions:
Claim 12. For any two-action contract design problem satisfying MLRP, the optimal contract is threshold contract:
13 F2 Fillav 11 [j jr. Jm.
where jF. = min (j E (O...., m.. F2. 2 Fi.s) as Definition 13.
Proof. Combining the result of Claim 10 with the monontonicity assumption, the likelihood ratio F2.j/ Fi, crosses exactly once. Denote the crossing point by j", and apply Theorem 5 to obtain the optimal contract.
B.7.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 [S] 2. In contrast to corollary 1, the proof in constructive, and yields concrete contract:
any contruct design problem satisfying MLRP with > actions and m outcomes, the optimal min- nin-budget contract is threshold contract.
Claim 13.
27

---

Proof. By Claim 2, the dual LP for two outcomes is given by:
Ele - -c)1
max X PERS 20 i=1
s.t.
(33)
VjE (1,2)
Σ
(Fr.. Fa.)) X S
t=1
Σ 14 51
JE(1.2)
From Claim 10, we obtain that Fn, - F < and Fn.2 - F12 > 0 for all E [n - 1], and therefore
the first constraint in Eq. (33) is always satisfied for 1. Simplifying Eq. (33) obtain:
Σ (cn c)
max
AER
#E 20 iml
s.t.
(34)
Σ (12)
which is maximized by allocating all budget to the x maximizing the "hang for buck". The dual objective is therefore given by:
B
max
(cn
AER ME 200 iE/n-1]
(35)
Gp Gi
max xE
Fn, - Fs,2
To see that a threshold contract is optimal, let t = B 1 1 = 1]. Primal objective is B", and the contract is feasible if the primal LP is feasible. The (IC) constraint in Eq. (6) can be written
Σ3=1 (Fn. - F(j)
Vi E In - 1]:
Cn -
and indeed for every action i E [n 1]:
Σ F Fsg) 1g
Fn.2 - Fi, B"
Cn Ci
Cn Ci
Fn. Fi2
Gn Cj
max
Gn
Ca
ie
Fn.
Fi2
And therefore f 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. [19, Lemma 7).
B.7.3 General contracts with MIRP
In this section, we explore min- munee contracts in MLRP settings with more than two actions and more than outcomes. We start with a negative example, showing that the MLRP assumption is not sufficient for establishing the optimality of threshold contracts:
Claim 14. For |S2] > 2, there exists a design problem satisfying MLRP for which the optimal contract not a threshold.
Proof. Consider the following contract design problem:
Fi Binomial (10, 0.5)
C1 = 0
F2 Binomial(10) 0.65)
C₂ 0.45
Fg Binomial(10,, 0.8)
C3 = 1
28

---

Outcome distributions
Min-budget vs. integer solutions
Non-concavity crossing point survival
Prebibity mass
MIP
Crassing point survoal N.
0.0
0.2
Payout 5
1.0
0.4
0.1
0.5
0.2
0.0
0100
0.0
2.5
3,0
7.5
10.0
0.0
2.5
5.0
7.5
20.0
0.00
0.25
0,50
0.75
1.00
Outcomn
Figure 7: Graphical illustration Claim 14. (Left) Outcome distributions Fi, F2, P3 and MLR crossing point FF. (Center) The min-budget contract Ej, given by numerically solving Eq. (11) (purple), and numerically solving Eq. (11) while imposing integer constraints dj E {0, 1] (cyan).
Note that the fractional LP solution achieves lower max payout. (Right) Crossing-point survival 8t Sp, (F.. 1) function of cost O (see Definition 15). Note that the function is not concave, thus the sufficient condition given in Theorem does not hold this case.
The distributions are binomial, and therefore the contract satisfies MIRP. Numerically solving Eq. (11) yields the following fractional contract:
LL (0, 0, 0, 0, 0, 1.1, 1.46, 1.46, 1.46)
Numerically solving Eq. (11) while imposing integer constraints db (0,1) yields the following contract, which has higher max payout:
ip = (0, 0, 0, 0,0,0,0000000 1.51,
Thus for this case any threshold contract min- budget suboptimal. graphical illustration of the proof is provided in Fig. 7.
L
[0) Remark 2. The proof of Claim is provided with outcomes ([St = 10) ease of graphical interpretation, however minimal counterexample may also be constructed using only 3 outcomes. For example, consider the following design problem:
Fi (0.5,0.3.0.2)
C1
F2 = 0.4.00.4.0.33
C2 0.45
F3 = 0.35, 0.55)
C3
The proof for this case case follows the same way, where numerical computation yields the contracts:
L (0, 1.9, 2.6)
tip = (0.2.7.2.7)
Remark We also note that a counterexample with 2 outcomes is not possible due to Claim 13.
The negative example shows that even with MLRP, the optimal contract incentivizing the highest agent to other actions, and not just to
implementable action needs to rule out deviations the second-highest one. This makes the contract complex. We identify natural economic condition that is sufficient for considering only a single deviation (to the second-highest action), resulting in simple contract. Note that considering single such deviation is equivalent to restricting the action space to actions {n 1,
B.8 Sufficiency condition for more than two actions
For the following definition, recall the definition of MLR crossing point j" (Def. 13), and survival function S (Def. 14):
Definition 15 (Concave-MLRP: Formal statement of Definition 2). For contract design setting sat- sifying MLRP, denote by j = ji-.. the crossing point of the outcome distribution corresponding to the highest action F,. and the oulcome distribution corresponding to the second- second-highhst action Fn-1. 1. For any action E [n], the crossing- point survival is defined as:
S (j" -1)
29

---

In words, is the probability to get an outcome at or above crossing point j" according to outcome distribution F,. From an economic perspective, for every action E [m]. S; 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 {n n. Note however that the definition 8; only depends on the outcome distribution Paj, and does not require solving the contract design problem.
B.8.1 Binomial power-law curves satisfy Concave-MLRP
Recent theoretical work on learning curves has focused mainly on power-law expected learning curves of the form 0y 1 3n [11, 33). In addition, these curves were also found to provide a good fit for certain practical applications [49, POW2]. In this section, we show that a stochastic generalization of these curves satisfies the Concave-MLRP property:
Definition 16 (Power-law stochastic learning curve). Let 3,7 E Rzo, and m E delegated learning setting with actions A has realizable power-law stochastic learning curve with parameters 3, if F; Binomial (1 3n."" .m) for all n; E A.
For the proof, we also recall the definition of the regularized incomplete beta function:
Definition 17 (Regularized incomplete beta function). For k1 la 2 the regularized incomplete beta function is defined as:
(p1 k2) = So (k -1 - di
So th 11 (1 -) lct
We also recall that Ip related the survival function of the binomial distribution [e.g.. 6.6.4]: lp(k + 1,n k) P "e-BBioniallp.a k]
Claim 15. Let B, R2o. m N. A delegated learning setting with a power- stochastic learning curve F; Binomial(1 - , action costs C; = Thi, and min; ns 2 (8(m4+""1/147"))
satisfies the Concave-MLRP assumption.
Proof. Denote the expected accuracy of each action by On - -m. The survival function of the binomial distribution is given by:
Sn = (j" -mmm++
Where Ta,, is the regularized incomplete beta function (Definition 17). With slight abuse of notation, we treat a, and 8n as continuous functions of n. Taking the derivative by and ignoring the constant denominator, we obtain:
dsn x -1 -1-a)
mm dan dn
dn
Plugging the functional form of an:
d8n
(1 - In 77-77---- (Bn m-5 8yn- (1+1)
dn
x (Bn 13 m- +1+7 (1 -1- (1-Bn Bn
As function of 3n 7,, 7, the function daa attains its extremum at: dn
Y + 1 - m + +
B(m 7m++
ñ
m + 1- +
+
And therefore the function s, has an inflection point at (see Fig. 8). From the upper bound j* S m obtain:
(3(mm +
(1mm
S
1+
n2
And as min; n, 2 no, the function s, is convex as a function of c, for all n E A.
The proof is illustrated in Fig. 8.
30

---

Expected accuracy
Survival transition
derivative
2-
Sirvial
0.5
0.4
Power- law
11.
20000
20000
40000
C0000
Artion cost
Action cost
Action cost
Figure 8: Graphical intuition for the sufficiency condition in Claim 15. (Left) Expected accuracy curve for MNIST-784 MLP. Blue dots represent empirical data from the LCDB dataset, cyan curve represents power-law fit (a,, 1 - fn with 3 = 1.89, 7 = 0.33). (Center) Crossing point survival 8; function of cost c; (see Definition 15), for m 30. Cyan dot represents inflection point ñ. = 2022. Red vertical line represents the inflection point bound no = 3957 suggested by the proof. can be observed that the curve is concave for all n > (Right) Second derivative of the survival function Sn, illustrating the position of the bound no in relation to the inflection point ň.
B.8.2 Proof sufficiency theorem
Theorem (Concave-MLRP implies threshold contracts; formal statement of Theorem 4). For a contract design problem satisfying MLRP, consider function of cost C.. If this function is concave, then the optimal contract is a threshold contract. Furthermore, the contract is successfully recovered by the SBA algorithm.
Proof. To prove this claim, we construct relaxed version of the min- min-budget LP (Eq. (6)), and apply Theorem in order 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 S n 2:
min
B
18 BER BER
s.t.
(36)
vj
E Q: 1g S B
Σ Pn-15l5 Cn-1 S E Ca
JER
JER
Eq. (36) only depends on Fn and Fa and therefore claim 12 can be applied to obtain the optimal min-budget contract:
Cn Gn-1
t
[Fn. 2 Fn-1a]
(37)
| F Fn-ilITV
Let j = min { E {o......
m] Fn.j 2 Fn-15) as Definition 13, and denote s, = Syp (j* 1).
By claim 11, obtain:
F - FR-1lll Ill 8n - 8n-1
For all < n, denote:
b, Cp Ci
8n 8;
Using the definition of b, Eg. (37) can be rewritten as:
= bn [j 2
By assumption, 8; a concave function of cs and therefore the function by is monotonically non- decreasing for all i < n:
b 2 b;
Dividing both sides by b, we obtain:
b
> 1
by
31

---

Outcome distributions crossing point
Crossing-point survival R;
Optimal min-budget contract
0.25
40000
Probatitty K3
0.15
F5
0.6
Poymant 8:
30000
FL
20000
0.2
10000
0.00
0--
15
2300
30000
7500
10000
0
10
15
Outcome J
Figure 9: Graphical intuition for the sufficiency condition in Theorem (restated Theorem 6). (Left) Outcome distribution in contract design setting satisfying MLRP, generated by series
of binomial distributions with power-law expectation (h,) = 0.9 - 0.4 _a 0.3
The gray dotted line represents the MLR crossing point J', Fr. (see Definition 13). (Center) Crossing point survival 8; as a function of cost G (see Definition 15). can be observed that the curve concave. (Right) The min-budget contract implementing action 5. It threshold contract, guaranteed by Theorem 4. Compare to Fig. 7, where the sufficiency condition does not hold.
T00
Plugging in the definition of b, and multiplying both sides by (cn c)):
b (sn s;) Cn
(38)
By definition of tj, the expected payout of contract t2 under action i' E [r]] is given by:
m
Σ
Frs bn- Σ
F b1p
(39)
1=0
j=1"
Plugging Eq. (38) into Eq. (39) yields:
m
m
Σ
Fy
tjFis Cn C4
(40)
As Eq. (40) is identical to the (IC) constraint in Eq. (6), we obtain that satisfies all the (IC) constraints in the original LP. From this we conclude that f which is threshold contract, also an optimal contract with the respect to the full min-budget LP.
For the second part of the claim, note that the SBA algorithm also attempts solve Eq. (36) on the iteration corresponding to action N 1. As the solution of Eq. (36) is guaranteed to be feasible for the original LP under Concave-ML.n MLRP, the SBA successfully recovers it.
B.9 Min-budget contracts with guaranteed minimum payout
Our problem setting assumes that the agent selects its action rationally, as described in Eq. (2). However, some practical settings the agent may be risk averse to some extent, and require guaranteed minimum payment from the contract. In this section, we show that the rationality assumption made without loss of generality in such cases: Lemma which we prove below, shows that any optimal contract with guaranteed minimum payout can be represented as the sum of min-budget contract without guaranteed payout, and constant representing the payout guarantee.
has guaranteed payout Definition 18 (Guaranteed minimum payout). Let 8 2 0. A contract E R [0] of size 8 if 2 8 for all j e Ω.
Lemma contract f. a min-bulget contract with guaranteed payout requiring budget if any only if there exist min-budget contract t' (without guaranteed payout) requiring budget B3 such that t = + and B B' 6
Proof. When agents require a guaranteed minimum payout 2 O, we add constraint to the BIN-BUDGET linear program defined in Eq. (6), such that optimal min-budget contract t with
32

---

guaranteed payout 8 is an optimal solution to the following linear program:
min
B
ER R 20 BER
s.t.
Vj SiER:Ai SB
(BUDGET)
(41)
Vi' : Σ Feglo co S Σ Figly JEG
(IC)
JEN
vj E Ω tj 2
(MINWAGE)
To prove the first direction of the equivalence, assume that is min-budget contract with guaranteed payout 8 and budget B, and thus an optimal solution of Eq. (41). Define the variable transformation:
t' = 8 B' B
(42)
By Eq. (42), the (BUDGET) constraint in Eq. (41) transforms into:
Vj NjE 2 S B
t 8 < +8 + SB' B'
(43)
The (IC) constraint transforms into:
Vi' :
Σ
Fecst cr S Σ Pictz- -;
jEn
JEN
Σ
Fy. sty +0) ccp
FF. + -;
jeN
JEN
Σ jen
Fy. ot Cy + Σ
Fr. S
Fist'
Cs + 8
Fij
(44)
iEN
jEN
jEN
Σ jen
Fe - S Σ
Flst Co
jER
And the (MINWAGE) constraint transforms into:
Vj E 2
(45)
+
Plugging back the transformed constraints (44, 43, 45) into Eq. (41), we obtain that (t', B3) is an optimal solution of the original MIN-BUDGET linear program Eq. (6), and therefore e is an optimal min-budget contract without minimum guaranteed payout.
Conversely, assume that t' is an optimal min-budget contract (without minimum guaranteed payout), satisfying the BIN-BTT linear program in Eq. (17) with budget B'. Apply the inverse transfor- mation + and = B' + 5, and the equivalence relations (44, 43, 45) in the inverse direction obtain that 1, B is an optimal solution to Eq. (41).
C Experimental details
C.1 Data
LCDB. We base main experimental environment on the LCDB dataset [43], which includes a large collection stochastic learning curves for multiple learning algorithms and classifica- tion benchmark datasets. For each learning method and benchmark dataset, the database in- cludes held-out accuracy measurements, obtained for exponentially-inereaai
training set sizes n {2- = 16,..., round(2*/2), ..., 215 32, 768), with multiple repetitions per n obtained by cross-validation. For all learning curves consider in our analysis, and for each n, the number of
33

---

repetitions provided in the dataset is in the range R E (5..... 125), 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 Alg (e.g. MLP), dataset D (e.g. MNIST), and training set size n, LCDB provides set of accuracy estimates {a); A.g.A ..... an Rl..lg.D. }. such that each On is distributed according to an ~ accp (ft)), where ftn is a classifier trained using training set S ~ D and learning algorithm Alg (see Section 2 for definition accp (hx))
Benchmark dataset and algorithms. In our main analysis, focus the popular MNIST dataset [39, OpenML 554], and on multilayer perceptrons (MLP) and gradient- boosstd decision trees (GBDT) as representative classifiers. For all classifiers, results are obtained for the respective default scikit-learn [44] implementations (e.g. MLPClassifies and GradientBoost tingCl Braddeettoosttingllssss for MLP and GBDT, respectively).
Delegated learning settings from empirical data. For a given validation set size m where m [V] instantiate contract design task (A, Q, F) as follows: (i) the of actions with the set of training set sizes provided by LCDB (A {2t, 24.5
,,,,,,,,1 (ii) action costs set to fixed per-unit cost, i.e., Gn = n; and (iii) the distribution F over outcomes is associated with binomial mixture distribtuion, resulting from applying bootstrap sampling empirical error measurements:
R Σ
fn =
Binomial(m, a Alg.D
where an are the accuracy estimates defined above. Fig. (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 [13, 27] and GLPK for solving linear and mixed- integer programs.
Code is available at: https: //github. www./oom/cceeeeeeeeee
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 5 minutes. The main bottleneck 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 [fn] and costs (c,), solve the MIN-BUDGET LP (Eq. (6)) directly using Pyomo and GLPK. Given budget B, budget- optimal contracts are obtained by iterating through the actions set AA invoking the min-budget solver on each target action E A, enforcing incentive compatibility against all actions n' which satisfy a, < Oup and taking the action yielding the maximal expected accuracy within budget (see Appendix B. In our code, the LP solver is implemented within the MinBudgetContracct class. Typical running time for a single problem instance: 10 10-1s.
SBA solver: Implementation of the single binding action algorithm presented in Section 3.4. The class.
local solver is implemented within the MinBudget.Sing Typical running time for single problem instance: 10 As.
Hybrid solver: A meta-solver implementing the 'try SBA first' computational approach. The solver starts by invoking the SBA solver, and applies the LP solver if the former fails. In our class. Running time
code, the LP solver is implemented within the MinBudgethybriidontree depends whether SBA is applicable.
MIP solver: To find optimal all-or-nothing contracts, we solve the MIN-BUDGET LP in its statistical formulation (Eq. (11)) while restricting Φb E (0, 1}. This turns the LP into a mixed- integer program, which can also be solved using GLPK. In our code, the IP solver is implemented within the MinBudget.Statisttt wtw.:Statttssiillnnonnt..oee calContract class. Typical running time for single problem
instance: 10-1s.
34

---

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. (17)) using Pyomo and GLPK, similar to the full min-budget LP solver. In our code, the min-pay is implemented within the MinPayContract class. Running time similar the other L.P-aased methods.
Full enumeration solver: To find all-or-nothing contracts for low-dimensional problems and avoid numerical instabilities, implement solver which performs full enumeration of all-or-nothing contracts. By the statistical variable transformation in Definition 3, the (IC) constraint in the MIN-BUDGET LP translates to Ejen (F.. F) 0j I (c: Cy 38 where is the target action,
i' E \ {i), and the objective is minimize (see Eq. (11)). Thus, when Φ E {0, 13, is fixed, the optimal is given by:
(Pey 4 4-
(b)
min PEA)(()
and optimizing 3 over {0, 1) yields an optimal all-or-nothing contract. The full enumaration class. For for enumeration of all-
solver is implemented within the wwweeleeeeeiennooiee or-nothing contracts, this solver is mostly applicable for small problem instances (m < 20) due its exponential complexity. In contrast, for threshold contracts the number of possible configurations is linear in m, and therefore enumeration more efficient.
Fixed-budget solver: To find budget-optimal threhsold contracts given fixed budget B, we imple- ment simple solver which iterates through all possible threshold contracts io (i) B1 [ jol for all jo E .O,....70 m. The solver then simulates the agent's 's rational choice (Eq. (2)) and selects the value of ju which incentivizes the best action. In case ties between possible values of jo- they are broken in favor of larger values, as this was shown to lead to greater numerical stability. class.
The fixed-budget solver is implemented within the FixeBBudetthheeeholllootttt
C.3 Empirical prevalence estimation
Since our theoretical analysis relies MLRP assumptions, we would like to understand whether the results are applicable to real-world learning curves. Towards this, we run an empirical prevalence evaluation on the MNIST dataset. For each learning algorithm Alg, and training set size n, we construct a delegated learning setting with m 10 and collect the following statistics:
Structural properties:
Is MLRP? (% MLRP): Check whether all pairs n1, n2 S such that Cn2 < Cnz satisfy the monotone likelihood ratio property (see Definition 1).
Computational properties:
SBA successful? (% SBA): Check whether the SBA algorithm was successful on the given
instance.
Functional form of optimal contract:
Is monotone? (% M): Check whether the resulting min-budget contract satisfies I, 2 l--1 for
all j [m].
Is all or nothing? (% AoN): Check whether the resulting min-budget contract an all-or- nothing contract (i.e. whether there exists ju Q,B 0 such that 0 for all jo and
1j B otherwise).
Is threshold? (% T): Check whether the resulting min-budget contract is threshold contract
(i.e. whether there exists jo E Q,B > such that tú = for all j < jo and ty = otherwise).
Excess cost:
Min-budget: Optimal objective BiP of MIN-BUDGET LP without additional restrictions, implemented using the full LP solver.
All-or-nothing budget: Optimal objective of MIN-BUDGET LP, when the resulting contract is restricted to all-or-nothing form t, { Implemented using the full enumeration solver.
Threshold budget: Optimal objective of MIN-BUDGET LP, when the resulting contract is restricted threshold form Ij B [j 2 jo]- Implemented using the full enumeration solver.
35

---

Table 2: Empirical robustness estimation on the MNIST dataset. Each row corresponds to learning algorithm, and columns are specified in Appendix C.3. Results are averaged across all implementable actions.
Structure
Compute
Functional form of opt. contract
Excess
MLRP
% SBA
% M
AoN % T
AoN
MLP
100%
94.4%
100%
94.4%
94.4%
0.04%
0.04%
GBDT
100%
76.5%
100%
82.4%
82.4%
0.71%
0.71%
Logistic
93.8%
81.2%
93.8%
93.8%
93.8%
0.00%
0.00%
Perceptron
68.8%
75%
93.8%
93.8%
93.8%
0.00%
0.00%
Linear SVM
71.4%
78.6%
85.7%
85.7%
85.7%
0.95%
1.45%
Poly SVM
100%
94.4%
100%
94.4%
94.4%
0.24%
0.24%
RBF SVM
100%
94.4%
100%
94.4%
94.4%
0.04%
0.04%
KNN
100%
100%
100%
100%
100%
0.00%
0.00%
Overall
92.6%
87.4%
97%
92.6%
92.6%
0.22%
0.26%
-hee excess cost columns in Table 2 indicate the relative excess cost incurred by restricting the min-budget optimization space to simple contracts BiAoN, -Br) As aolhong contracts are superset of threshold contracts, we expect this excess cost to be smaller than the one associated with threshold contracts. The averaging in table 2 is performed on problem instances where both all-or-nothing and threshold contracts are feasible.
BLP
Averaging over all implementable actions, we obtain the results in Table 2. The results show that threshold contracts are relatively common this dataset (more than 85%), and that excess cost of simple contracts is relatively low (around I 1%), indicating that threshold contracts may provide good approximation to the optimal min-budget contracts some cases. All simple optimal contracts in our dataset had threshold functional form, and some simple optimal contracts were not recovered by SBA, indicating that a tighter characterization of simple contracts may possible.
Fig. 10 provides qualitative interpretation of the analysis for a selected subset of learners. While the survival functions are not perfectly concave (and thus don't satisfy Concave-MLRP), the SBA algorithm successfully terminates in three cases (MLP, Logistic, KNN). The binding action is ax-1 for two of the classifiers (MLP, KNN), similar to the condition implied by Theorem Note that SBA also terminated successfully on Logistic Regression data, despite the learning curve having distinctive non-concave shape. In the case of GBDT, the survival function concave, and the optimal contract does not assume a threshold form.
36

---

Qualitative comparison of delegation problems
Expected accuracy [(acop(Haa))
Survival transition
Optimal fj
MLP
0.75
200000
Learning algorithm
G801
200000
0.50
0.25
0..0
Logistc:
0.70
0.5
200000
0.50
230000
0.50
0.25
0.0
10000
15000
10000
15000
Action cost is,
Action cost
Outcome 3
Figure 10: Qualitative comparison of optimal contract computation on LCDB MNIST data (n* 16384, m 25). Each row represents a learning algorithm. (Left column) Expected accuracy curves On. (Center column) Survival function at transition 8,, whenever SBA is successful, the binding actions are marked with triangles. (Right column) Optimal contract 17.
37


Reviews:
[{"review_id": "Ikijpoqbfa", "reviewer": "Reviewer_EHyc", "summary": "The paper studies the problem of a decision maker (the principal) delegating the task of training a machine learning model to an agent.  Both parties are strategic, and the principal must commit to a contract to encourage the agent to invest effort (e.g., labeling training samples).  The authors consider the principal's problem of designing the optimal contract subject to a budget constraint, which maximizes the expected performance of the model trained by the agent given that the agent best responds to the contract.  Technically, they give (1) an LP-based algorithm for computing the optimal contract, (2) a characterization connecting the optimal contract to hypothesis testing when the agent has only 2 possible actions, and (3) another characterization stating that optimal contracts have a simple form when the learning curve satisfies certain conditions.  They validate these findings with experiments, and also empirically study a setting where the principal does not have enough information and therefore must estimate the learning curve.", "questions": "(also putting minor comments here)\n\nFigure 1: at this point it's not totally clear to me what role m plays in the model.  In particular, how should m be chosen (either by nature or by the principal), and how does the choice affect the performance of the contract?  I'm sure this will become clear later, but it might make sense to briefly comment earlier, perhaps in a footnote.\n\nLine 56, \"MLRP\": what does this mean?\n\nLine 93: broken citation\n\nLine 120: \"... principal cannot now how many examples ...\"\n\nLine 130: \"a-priory\"\n\nLine 266, \"under MLRP n_2 is always implementable\": I'm not sure I get this --- what if c_2 - c_1 > B?\n\nLine 272, \"important special case of binary-outcome\": this (corresponding to m = 1) sounds less practical to me.  Any justification for the importance of this case?\n\nTheorem 2: I feel the way this result is presented in Table 1 is somewhat misleading.  The impression I initially got from the table is that the problem of computing the unconditional, unrestricted optimal contract is NP-hard.  Or is this actually implied by Theorem 2?\n\nLine 307, \"as m increases, required budgets\": unfinished sentence?\n\nLine 310, \"the local solver is easy to run\": what does the local solver do?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The problem is natural and exhibits quite some theoretical depth.  The paper is well written, and in particular, the introduction nicely motivates the problem.  The technical results are nice and clean, and they also appear to be practically meaningful, as supported by experimental results.", "weaknesses": "While I like the paper overall, one concern is regarding the model: the model is quite specific, and I wonder if / to what extent the results can be generalized and remain (approximately) valid.  Another practical concern is regarding scalability: in the experimental section the authors say that their full LP solver works for m no larger than 20, which doesn't sound like a very practical number; there is the local solver but it's not totally clear what it does, or how reliable it is.  Also see detailed comments for some minor points.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and the great suggestions! We address your questions below:\n\n> Figure 1: at this point it's not totally clear to me what role $m$ plays in the model. In particular, how should $m$ be chosen (either by nature or by the principal), and how does the choice affect the performance of the contract? I'm sure this will become clear later, but it might make sense to briefly comment earlier, perhaps in a footnote.\n\nThanks for the suggestion. We will add clarification for the role of $m$ in the caption of figure 1, and in the problem setup section.\n\n> Line 56, \"MLRP\": what does this mean?\n\nMLRP stands for “monotone likelihood ratio property”. It is a common assumption in statistics [LR05] and contract design literature [DRT18]. In our setting, the MLRP assumption can be taken to state (informally) that the better the evaluation result of the classifier, the more likely that it was trained using more data. A formal definition of MLRP is given in Line 264. We will clarify the definition and the intuition behind it, and better connect the two.\n\n> Line 93: broken citation;\nLine 120: \"... principal cannot now how many examples ...\";\nLine 130: \"a-priory\"\n\nTypos fixed. Thank you for pointing them out!\n\n> Line 266, \"under MLRP n_2 is always implementable\": I'm not sure I get this --- what if c_2 - c_1 > B?\n\nThe meaning of “implementable” is that the min-budget optimization problem (eq. (4)) is guaranteed to have a solution. The min-budget optimization problem finds the minimal budget $B^*$ required for incentivizing training with a certain dataset size (in the case described above - $n_2$). We also note that $B^* \\\\ge c_2 - c_1$ for every implementable contract incentivizing $n_2$, as the expected payout must cover the agent’s additional cost. \n\n$B$ represents the total budget available to the principal, and we treat it as an external constraint in order to maintain parity with the contract design literature (e.g [S15]). When $B^*>B$, the solution is considered economically infeasible. \n\n> Line 272, \"important special case of binary-outcome\": this (corresponding to m = 1) sounds less practical to me. Any justification for the importance of this case?\n\nThis case captures a coarse measurement of the agent’s performance - the agent’s effort can either succeed or fail. It is an important case since it is a primary focus of many works in the literature, such as [BFNW12, HSV16, DEFK21]. It is also practical in situations where the principal can either accept the agent’s work and pay the agreed upon price, or altogether reject the work and not pay. \n\n> Theorem 2: I feel the way this result is presented in Table 1 is somewhat misleading. The impression I initially got from the table is that the problem of computing the unconditional, unrestricted optimal contract is NP-hard. Or is this actually implied by Theorem 2?\n\nTable 1 focuses on characterization of contracts that take a simple form. In our context, simple-form contracts have the “all-or-nothing” property ($t_j \\\\in \\\\{0, B\\\\}$), as opposed to paying arbitrary amounts ($t_j \\\\in [0,B]$). Theorem 2 implies that optimal simple contracts are NP-hard to find in the general case, by reduction from 3-SAT. In contrast, the problem of computing the unconditional, unrestricted optimal contract is not NP-hard. We will make sure to clarify this better in the next version.\n\n> Line 307, \"as m increases, required budgets\": unfinished sentence?\n\nThanks for pointing this out! This was a typo (now fixed), and the complete sentence is “As $m$ increases, required budgets and the difference between them both decrease.”.\n\n> Line 310, \"the local solver is easy to run\": what does the local solver do?\n\nThe local solver computes the optimal contract using a relaxed version of the MIN-BUDGET linear program (eq. (5)).\n\nIn more detail, the MIN-BUDGET linear program (eq. (5)) can in principle be solved with general-purpose numerical solvers (e.g. GLPK), but is prone to numerical instabilities; we observed these starting at around $m\\approx 20$. To overcome this, the local solver relaxes some of the incentive compatibility constraints (Appendix C.2.1). This leads to a closed-form solution (given by Proposition 2) which can be computed efficiently and at scale. Under the conditions of Theorem 3, namely MLRP + concave survival, the local solver is provably optimal. We will clarify this and add a discussion of the different solvers in the revision.\n\n—\n\nReferences:\n* [LR05] Lehman & Romano, 2005 - Testing Statistical Hypotheses (Section 3.4)\n* [DRT18] Dütting et al., 2018 - Simple versus Optimal Contracts\n* [S15] Salanié, 2015 - The economics of contracts: a primer (Chapter 5)\n* [DEFK21] Dütting et al., 2021 - Combinatorial Contracts\n* [HSV16] Ho et al., 2016 - Adaptive Contract Design for Crowdsourcing Markets\n* [BFNW12] Babaioff et al., 2012 - Combinatorial Agency\n"}, {"review_id": "YW8JfVC9Nr", "reviewer": "Reviewer_au5P", "summary": "This paper presents a novel theoretical principal-agent framework for examining the incentive-aware delegation of machine learning tasks. In this context, a principal can design a monetary contract to stimulate an agent to exert private efforts towards training a classifier. In the proposed framework, the agent's private actions is the number of samples he/she can process, while the principal operates within a monetary budget $B$. Importantly, the contract design is entirely based on observed outcomes, modeled as the prediction accuracy of the agent's trained classifier against the validation samples.\n\nThe paper first shows that the budget-optimal contract is essentially an all-or-nothing contract when the agent has only binary actions. Then the paper also provides several (structural) characterizations on the optimal contract if the action-to-outcome distributions satisfy certain regularity assumptions (e.g., monotone likelihood ratio property, concavity). Finally, the paper also provides empirical results to study how the model parameters affect the design of the contracts and the resulting agent’s trained classifier. ", "questions": "See above", "limitations": "No", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is rigorous and very well-written. I largely view this work as an modeling paper. The proposed principal-agent framework is novel and interesting, and it provides an economic view to understand the dynamics when a training task is delegated to another entity, potentially possessing conflicting interests. The paper also provides several characterizations on the optimality of contract when the considered problem has some certain structure (e.g., binary-action, binary-outcome), and also some characterizations for the general action/outcome space but with imposing some additional assumptions. The empirical section also adequately evaluates the proposed framework. ", "weaknesses": "My main concern regarding the paper lies within the technique results. It is noted that many of the characterizations about the optimal contract align closely with, or can be derived from, recent research on the algorithmic principal-agent problem.\n\nFor instance, as noted by the author (line 262), the optimal contract for binary-action can be derived using the Linear Programming (LP) duality. The paper instead uses a proof approach related to hypothesis testing. It could enhance the paper's value if the author elucidated the advantages of this particular approach. Can it illuminate more complex instances, and if so, how?\n\nIn addition, in my humble opinion, it seems that the current characterizations could also be derived by merely considering a pure principal-agent problem, thereby bypassing any classification or machine learning elements. Since the primary aim of this paper is to frame the delegated training problem as a principal-agent problem, I believe the exploration could be enriched if it delves deeper into how typical tradeoffs (e.g., the number of samples used by the agent has some implications on the prediction accuracy in a quantitive way via some generalization error) in standard machine learning tasks affect the considered game. \n\nOther questions:\n\n1. missing refs in Line 93\n2. it is a bit confusing in Proposition 2, is that $B$ the budget? If so, then by definition of all-or-nothing contract, there should be only one outcome that has positive payment? \n3. In Program (5) in Appendix B.2, the objective should be $t$? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and insightful feedback!\n\n> My main concern regarding the paper lies within the technique results. It is noted that many of the characterizations about the optimal contract align closely with, or can be derived from, recent research on the algorithmic principal-agent problem.\n\nThis is imprecise, and we apologize if this was the impression conveyed. Let us clarify:\n\nThe contract design literature deals predominantly with minimizing expected payment. This turns out to be inappropriate for modeling delegation of learning (see response to reviewer ybdo), and motivates the introduction of *budget-optimal contracts*. To the best of our knowledge, there is no prior work on budget-optimal contracts, and therefore existing results do not necessarily apply.\n\nBudgets make the contract design problem challenging because they introduce an additional hard constraint. At the same time, properties of the underlying learning task, which motivate monotonicity and concavity, can make the problem feasible (see below). The fact that budget-optimal contracts admit a simple form (“all-or-nothing”) is a novel result, which we prove using duality theory (see below). Such techniques are also used in min-pay contracts, but the connection is not immediate.\n \n> For instance, as noted by the author (line 262), the optimal contract for binary-action can be derived using the Linear Programming (LP) duality. The paper instead uses a proof approach related to hypothesis testing.\n\nThis is also imprecise, though in re-reading this section, we see how this could have been implied from our formulation of line 262 (which we will correct). We apologize, and again wish to clarify:\n\nThe connection to hypothesis testing is not a proof technique, but rather a result:\n* We prove Prop. 2 (optimal contract for binary-action) by a stand-alone proof that relies entirely on LP duality (Appx. B.4.1). \n* Prop. 2 is not directly connected to hypothesis testing, but the functional form of the optimal contract suggests a possible connection to Neyman-Pearson (NP).\n* Based on this observation, we formalize the equivalence between optimal contracts and optimal tests in Thm. 1, where one direction of the proof makes use of Prop. 2 (Appx. B.4.2).\n\n“Loose” connections between moral hazard and hypothesis testing have been known for some time, but formal evidence has been limited: (i) the maximal likelihood ratio appearing in optimal min-pay contracts [S15], and (ii) a connection established by Bates et al. [BJSS22] in a setting distinct from ours (adverse selection, rather than moral hazard), and to a different variant of the NP lemma (asymmetric rather than symmetric). Thm. 1 provides a direct correspondence between optimal contracts and optimal hypothesis tests, and as such, establishes a clean formal connection. Our hope is that this will enable tighter future connections, and transfer between the two domains.\n\nWe will clarify both of the above points in the forthcoming revision of the paper.\n\n> It seems that the current characterizations could also be derived by merely considering a pure principal-agent problem, thereby bypassing any classification or machine learning elements.\n\nThe structure of a delegated contract derives from the structure of the underlying machine learning problem, coupled with the incentives of the different parties involved. For example:\n* Expected outcomes in the delegated task are determined by the *learning curve* of the underlying learning task. The study of learning curves has drawn recent interest in the learning community (e.g., see [VL22]). Our results leverage recent results in this field, such as scaling laws [K20] and monotonization [BDKMMS22].\n* The variance in outcomes in delegated learning is induced (in part) by the randomness of the training set $S$. This is also a key element in PAC analysis, manifested differently in our setup (i.e., as variance rather than as a probabilistic guarantee).\n* The principal evaluates outcomes using a *validation set*. This affects the design of the contract by imposing structure that we leverage. Validation is a fundamental concept in learning, and to the best of our knowledge, is unique to delegation of ML.\n\nAll of the above play important roles in our modeling choices and analysis.  \n\n> I believe the exploration could be enriched if it delves deeper into how typical tradeoffs … in standard machine learning tasks affect the considered game.\n\nWe fully agree. In Sec. 3, our analytic results rely on several basic properties of learning tasks, as discussed above. In Sec. 4, we move beyond this, and empirically study how additional elements of the underlying classification problem affect delegation and its outcomes, such as:\n* Using \"empirical\" contracts, computed on the basis of an outcome-probability matrix estimated from finite data\n* Extrapolating to large-sample actions from small-sample data, and for different extrapolation approaches\n* Differences in contracts and outcomes for the same data but using different model classes (e.g., MLP vs. GBDT)\n* Sensitivity and implications of different error types (i.e., under- vs. over-estimation) for the principal\n\n> Missing refs in Line 93\n\nFixed. Thank you!\n\n> In Proposition 2, is $B$ the budget?\n\nYes. In all-or-nothing contracts, payment takes one of two values ($t_j\\\\in\\\\{0,B\\\\}$), and multiple $t_j$’s can be positive.\n\n> In Program (5), the objective should be $t$?\n\nObjective is $B$ because we minimize the $l^\\infty$ norm of $t$. This is similar to a technique presented in [BV14; Sec. 4.3.1].\n\n—\n\nReferences:\n* [VL22] Viering & Loog, 2022 - The shape of learning curves: a review\n* [K20] Kaplan et al., 2020 - Scaling Laws for Neural Language Models\n* [BDKMMS22] Bousquet et al., 2022 - Monotone Learning\n* [S15] Salanié, 2015 - The Economics of Contracts: A Primer (Chapter 5)\n* [BJSS22] Bates et al., 2022 - Principal-Agent Hypothesis Testing\n* [BV14] Boyd & Vandenberghe, 2004 - Convex Optimization\n"}, {"review_id": "leD8bSH68u", "reviewer": "Reviewer_ybdo", "summary": "The paper introduces an interesting problem, and provides interesting theoretical results based on a connection to classical result on statistics. The problem setup follows the standard principal-agent problem with moral hazard, and the principal commits to a contract to incentivize the agent behaving favor of the principal. They mainly analyze that thresholded structure is optimal in case of contract for classification task, and provide some fruitful implications upon it.", "questions": "Model\n* Section 2.1 describes contract design without budget constraint, but the problem setup actually involves budget constraint. I wonder why the authors consider this problem setup, and what happens if the principal does not have a budget constraint (though I understand that both may have plausible applications)\n* It seems the agent should be aware of the distribution $f_a$ to compute the expected payment; distribution over possible outcomes from action a. How can this be made practically? Also, $f_a$ corresponds to $f_n(j)$?\n\nResults\n* Given the vast literature on contract theory, why the existing techniques cannot be applied to the presented problem setup? I couldn't find the authors discussing on it.\n\nMinor comments\n* Reference unresolved in L93", "limitations": "* Thresholded rule is optimal - Yes, it makes sense that thresholded contract would be efficient against expected utility maximizer, however, it would carry over a huge amount of variance for the agent's reward. How would the optimal structure change if the agent exhibits risk-averse nature?\n* Again, such an extreme thresholded contract is not widely applied in practice - at least some amounts of minimal wage exist, or rather a linear contract is typical (e.g., Carroll15). Besides, finding an agent who admits such a thresholded contract would be difficult than that via posting more conservative/safer contract, thereby possibly inducing the quality of agent to be lower than expected. I'd like to see some discussions on it.\n* In the above context, if the budget constraint is given in ex-post manner, given the use of constant/linear/threshold with the same maximal payment (as in Fig 2), I doubt that the quality of the agent would be endogenous depending on the pricing rule to be exploited (e.g., giving constant B would attract highest-quality agent), rather than being exogenous. I'd appreciate some (empirical or theoretical) discussions on it.\n* As the paper contributes to an applied modeling of real-world scenario with claiming the efficiency of thresholded rule, I expected to see some comparisons between various contract structures in the experiment.\n* Also, the title of delegated classification looks a bit overly abstract to me. \bI would (though weakly) suggest making it more explicit, e.g., including contract sort of notions.\n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, the paper is well-written and easy to follow.\nThe problem setting they considered is novel and of interest to NeurIPS community, especially given the increasing attention to contract theory/delegation mechanism.\nThe analysis looks sound and the results are thorough.", "weaknesses": "I'm not entirely sold on the main results and their implications/takeaways, though I agree its technical soundness.\nDetails are presented below on questions/limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and insightful questions!  \n\n> What happens if the principal does not have a budget constraint?\n\nIn the non-budgeted setting, and when MLRP holds, min-pay optimal contracts take on a rather extreme form: a single non-zero payment that can be arbitrarily large and arbitrarily rare [DRT18]. In particular, Appendix B.3 shows a concrete setting where the maximal payment of an optimal non-budgeted contract is exponential in the validation set size $m$. Every entity has bounds on the payment it can make, and exponential growth makes such contracts unscalable. Given that MLRP is likely to hold for reasonable learning tasks, we believe this justifies the exploration of budgeted contracts.  \n\nWithout a budget constraint - and if willing to forgo global optimality - a linear contract may be a viable alternative, as such contracts are known to have appealing robustness properties (e.g. [C15]). However, they also have significant shortcomings, such as arbitrarily-inferior performance compared to optimal contracts [DRT18]. They also require the principal to attach a precise monetary value to each possible outcome, which for some settings may be unrealistic (e.g., when the principal is a government or non-profit organization).  \n\nA contract design that requires the principal only to set a budget, and guarantees the best-in-class classifier given this budget, is thus arguably more natural in many situations. We will add to the paper a discussion comparing the different approaches.\n\n> It seems the agent should be aware of the distribution $f_a$ to compute the expected payment; distribution over possible outcomes from action a. How can this be made practically? \n\nWe envision two avenues through which the distribution $f_a$ could be estimated by the agent. First, prior experience - as a service provider, the agent is likely to have past experience training classifiers in different scenarios, and thus may have the ability to generalize across learning curves. This approach has been applied in the empirical learning curves literature [LB05]. Second, extrapolation - similar to the partial information model introduced in Sec. 4.2, the agent may also train exploratory models and make a decision based on the extrapolated learning curve. Due to the agent's ability to collect data and train models in-house, we expect their extrapolation quality to be higher than that of the principal.\n\n> Also, $f_a$ corresponds to $f_n(j)$?\n\nThank you, there was a typo in eq. (2), and $f_a$ should come in place of $f_n$.\n\n$f_n(j)$ is the $j$-th component in the outcome probability distribution corresponding to action $n$.\n\n> Given the vast literature on contract theory, why the existing techniques cannot be applied to the presented problem setup?\n\nExisting results from the contract design literature cannot be directly applied because min-budget contract design problems have a different structure. We discuss similarities and differences in Appendix B.3, and will expand the discussion in the forthcoming revision. Our LP duality proof is distinct but inspired by [DRT18], and understanding whether additional techniques can be transferred from the theory of budget-unconstrained contracts to min-budget ones is a very interesting direction for future work.\n\n> Reference unresolved in L93\n\nFixed. Thanks for pointing this out!\n\n> How would the optimal structure change if the agent exhibits risk-averse nature?\n\nThis is an interesting question, for which the answer is not immediate. For comparison, note that in auction theory, answering questions regarding the incorporation of behavioral aspects has warranted substantial empirical and theoretical work, e.g. [VW21]. Our work focuses on a standard rational agent model, which we believe is reasonable as a first step. Hopefully our work can help establish the necessary foundations for extending to more elaborate agent models.\n\n> Such an extreme thresholded contract is not widely applied in practice - at least some amounts of minimal wage exist, or rather a linear contract is typical (e.g., Carroll15).\n\nThanks for this question! While working on it, we found a proof showing that the rationality assumption is made without loss of generality with respect to minimum wage: We show that any min-budget contract with minimum wage can be represented as a sum of a min-budget contract (eq. (4)), and a constant representing the minimum wage. In other words, an optimal contract with minimum wage can be obtained by adding a constant to a solution of eq. (3). The proof follows by constructing a modified version of the MIN-BUDGET linear program (eq. (5)), and introducing a change of variables. The full statement and proof will be added to the paper.\n\nWe also add that threshold contracts are common in many practical scenarios. For example, a salesperson may get a bonus upon selling a certain amount of units, and a student may earn a certificate upon exceeding a certain grade average.\n\n> Besides, finding an agent who admits such a thresholded contract would be difficult than that via posting more conservative/safer contract, thereby possibly inducing the quality of agent to be lower than expected.\n\nYour question seems to imply a more elaborate setup in which there exists a population of agents, and where agents have types (i.e., “quality”). Again, this is a very intriguing question, but remains outside our scope.\n\n> I expected to see some comparisons between various contract structures in the experiment.\n\nIn Appendix B.3, we compare the performance of min-budget to min-pay contracts, illustrating the impracticality of the latter as discussed above.\n\n—\n\nReferences:\n* [LB05] Leite & Brazdil, 2005 - Predicting relative performance of classifiers from samples\n* [C15] Caroll, 2015 - Robustness and Linear Contracts\n* [DRT18] Dütting et al., 2018 - Simple versus Optimal Contracts\n* [VW21] Vasserman & Watt, 2021 - Risk Aversion and Auction Design: Theoretical and Empirical Evidence\n"}, {"review_id": "xfZ50rbtNI", "reviewer": "Reviewer_dRCD", "summary": "This work provides a framework for incentive-aware delegation of machine learning tasks. It considers a principal-agent game, where the principal can spend a limited budget on the outsourcing the training of a machine learning model, with the hope of getting the most accurate model, and the agent provides a machine learning model to the principal, but aims to invest minimal effort in training. This work considers the problem of optimal contract design, where the principal commits to a contract that determines how much the agent will be paid for every possible accuracy level of the model, and the agent chooses a profit-maximizing number of samples to use to train the model in response to the contract. This contract design problem requires that the “learning curve”--a function that maps the number of samples to the accuracy of the model is known to both the principal and agent. When the learning curve has a nice structure, it is possible to leverage a connection to the Neyman-Pearson lemma to see that the optimal contracts have a simple threshold form.", "questions": "1. In Section 2 Lines 110-113, the authors discuss that $h_{n}$ is a stochastic quantity. It would be helpful to add a sentence here that $h_{n}$ is distributed according to a distribution that depends on $n$ (and more details on how to evaluate the expectation will be provided later in the work). At first glance, this equation is somewhat unclear because we have not yet defined the distribution over $h_{n}$ for a given $n$? \n\n2. The second plot of Figure 3 is somewhat hard to parse. Could the authors add some clarifications?\n\n3. It may be helpful to emphasize that the contract $t$ is a function that takes on a different value depending on each possible value of the validation accuracy. (The connection between the domain of $t$ and the sample size of the validation set can easily be missed).\n\n4. What do the authors mean by “robustness” in Line 372?\n\n5. Nit writing: Line 120 “the principal cannot now” -> “the principal cannot know.”\n\n6. Nit: Should the subscript of $f_{n}$ in Equation 2 be $f_{a}$?\n\n7. Nit writing: Line 308 has an incomplete sentence.\n", "limitations": "Yes.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper proposes an interesting new problem. The framing of the problem is well-motivated, clear, and sensible. \nFigure 2 is a great figure! It nicely captures the motivation for this problem and demonstrates possible contract types. \n\n2. The main contribution of this work is demonstrating that under easy to understand assumptions (Monotone Likelihood Ratio Property, concavity), the optimal contract of the proposed principal-agent game takes on a simple threshold form. The technical contribution of this paper is closely related to the connection between optimal contracts and the Neyman-Pearson lemma established by Bates et al., 2022. It is great to see this work build on the direction of Bates et al, 2022 and demonstrate a connection between optimal contract design and statistical hypothesis testing. The taxonomy given in Table 1 is helpful. \n\n3. The discussion in Lines 352-363 of how overestimation and under-estimation can have quite different implications is useful beyond the scope of this work. It suggests that when estimating learning curves, not all errors should be treated equal and we may want to penalize overestimation more strongly. This may be of interest to communities that aim to estimate/learn scaling laws.\n", "weaknesses": "A potential weakness of the model that the authors propose is the assumption that the principal has access to a learning curve– which captures the stochastic performance of a machine learning model as a function of sample size. Nevertheless, the authors address this weakness quite thoroughly–the authors cite many related works that suggest that the learning curve can be predicted from scaling laws and also analyze the construction of contracts in the partial information setting, where the learning curve is not known and must be estimated. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the encouraging review and positive feedback! We address your questions below:\n\n> In Section 2 Lines 110-113, the authors discuss that $h_n$ is a stochastic quantity. It would be helpful to add a sentence here that $h_n$ is distributed according to a distribution that depends on $n$ (and more details on how to evaluate the expectation will be provided later in the work).\n\nThank you for this suggestion! We will add a clarification.\n\n> The second plot of Figure 3 is somewhat hard to parse. Could the authors add some clarifications?\n\nFigure 3 (Center) shows the budget required for incentivization of a classifier with accuracy $\\\\ge 85\\\\%$, as a function of validation set size $m$. With increasing $m$, the required budget decreases, as the principal is able to gather more information about the agent's chosen action. Asymptotically, the required budget approaches the action cost under full information (“first-best”), indicated by the horizontal dotted lines. \nSolid/dashed curves compare different implementations of the numerical LP solver (local/full solver), as described in Appendix C.2.1.\n\nWe believe what may be confusing is that the plot blends economic aspects with optimization aspects. In the final version of the paper we will simplify the plot to focus on the economic aspects, and include a separate discussion on optimization.\n\n> It may be helpful to emphasize that the contract $t$ is a function that takes on a different value depending on each possible value of the validation accuracy. (The connection between the domain of $t$ and the sample size of the validation set can easily be missed).\n\nThank you for this suggestion! We will clarify this in the paper.\n\n> What do the authors mean by “robustness” in Line 372?\n\nIn this context, robustness refers to the ability to design optimal contracts even when the contract design setting has parameters which are uncertain to some extent (e.g when the outcome distribution of each action is estimated from data).\n\n> Nit writing: \nLine 120 “the principal cannot now” -> “the principal cannot know.”; \nShould the subscript of f_n in Equation 2 be  f_a?; \nLine 308 has an incomplete sentence.\n\nThank you for pointing out these typos! They will be corrected in the forthcoming revision.\n"}]

Author rebuttal:

Meta-review: The reviewers were in agreement regarding this paper. The paper studies a model of incentive-aware design for delegated classification, which may be of interest to folks in the federated learning community. Some of the paper's strong traits are: the modeling approach, the rigorous theoretical approach, and the presentation. The paper also evaluates the results empirically, although there was some reviewer-author discussion about the scalability of the empirical results. The authors agreed to add a discussion about this, so I don't think it's going to be a problem for the final version. Their key contribution is theoretical. I'm suggesting this paper for a spotlight; although the techniques are more Econ-oriented, I think the conference audience will greatly benefit from being exposed to the model and the idea of using contract theory to solve it.
Decision: Accept (spotlight)