Budget-Optimized Crowdworker Allocation
Authors: Sha Lai
Prakash Ishwar
Margrit Betke
Venue: Accepted by TMLR ()

Abstract: Due to concerns about human error in crowdsourcing, it is standard practice to collect labels for the same data point from multiple internet workers. We  show that the resulting budget can be used more effectively with a flexible worker assignment strategy that asks fewer workers to analyze data that are easy to label and more workers to analyze data that requires extra scrutiny. Our main contribution is to show how the worker label aggregation can be formulated using a probabilistic approach, and how the allocations of the number of workers to a task can be computed optimally based on task difficulty alone, without using worker profiles. Our representative target task is identifying entailment between sentences. To illustrate the proposed methodology, we conducted simulation experiments that utilize a machine learning system as a proxy for workers and demonstrate its advantages over a state-of-the-art commercial optimizer.

Published in Transactions on Machine Learning Research (01/2026)
Budget-Optimized Crowdworker Allocation
Sha Lai
lais8230bu.co edu
Department of Computer Science
Boston University
Margrit Betke*
betke @bu. edu
Deportment of Computer Science Boston University
Prakash Ishwar
piubu edu
Deportment of Electrionl and Computer Engineering Boston Universily
Reviewed OpenReview: https: openreview. net/ forum? id=nMpAganRmp
Abstract
Due to concerns about human error in crowdsourcing, is standard practice collect labels for the same data point from multiple internet workers. We show that the resulting budget can be used more effectively with flezzble worker assignment strategy that asks fewer workers to analyze data that are easy to label and more workers to analyze data that requires extra scrutiny. Our main contribution is to show how the worker label aggregation can be formulated using a probabilistic approach, and how the allocations of the number of workers to a task can be computed optimally based on task difficulty alone, without using worker profiles. Our representative target task is identifying entailment between sentences. To illustrate the proposed methodology, we conducted simulation experiments that utilize machine learning system as proxy for workers and demonstrate its advantages state-of-the-art commercial optimizer.
1 Introduction
Machine learning research advanced by crowdsourcing efforts, for example, to generate training data and evaluate machine learning models (Wortman Vaughan, 2018). When deciding on how many internet workers employ to annotate data, crowd task organizers must strike a compromise between budget constraints and accuracy expectations. Multiple annotations typically collected for the same data point, out of concern for the accuracy of human annotation (Kovashka et al., 2014). Building this redundancy into the crowdsourcing experiment, however, increases its cost and cannot guarantee accuracy.
The literature describes techniques for computing optimal trade-offs between accuracy and redundancy in crowdsourcing using a fized number of crowd workers per task (Karger et al., 2013; Tran-Thanh et al., 2013). The fixed assignment is agnostic about the latent difficulty of each lask, i.e., is data independent. In this work, our focus on a flezúble and dato-dependent assignment scheme. Intuitively, tasks can be categorized based labeling difficulty: "casy" tasks are associated with high probability of correct labeling, "hard" tasks have low probability, and those in between require more scrutiny. While assigning extra workers to "hard-to-labed" tasks seems like a way to improve correctness, it is often inefficient. Often, for truly hard tasks, even experts may disagree, meaning more worker annotations do not necessarily yield better results and can waste resources. Similarly, easy tasks require minimal input. Thus, fewer internet workers should analyze easy- and hard to-label data, and more workers should analyze the remaining data.
*This author passed away prior the publication this work.

---

Published in Transactions on Machine Learning Research (01/2026)
Data Samples (Small Size)
Difficulty Predictor
Task Difficulty
Labels
Allocation Optimizer
Big Data Analytics ML
Budget
Crowdsourcing
Deployment
Labeling Framework. First, the task difficulty of each sample is assessed and used to optimize the crowdsourcing procedure. Second, the labels from the crowdworkens are used for analysis and training a ML model, which can then be deployed for large-scale tasks.
Figure 1:
Flexible schemes have not been adcquately explored in the litcrature (Samcki al., 2016a;b; Khetan Oh, 2016). Handcrafted decision-trees (Sameki al., 2016a) and random-forest predietors (Sameki et al., 2016b) have been developed to determine how many crowd workers to assign to labeling task. It was shown that provide large budget savings with small sacrifices in accuracy compared
the computed worker allocations to the traditional fixed allocation scheme. We propose an alternative approach to determine the number of crowd workers per task that directly optimiies the allocation over all data. For a given budget, we show that the optimal allocation of the number of crowd workers results both accuracy improvements and budget savings.
Consider the human-machine labeling framework shown in Figure The system first answers the question: How many crowdworkers should be assigned to label the data accuracy while not exceeding the target budget? The solution to this question provides budgel-optinized crowdsourcing method to accurately label a small dataset. This initial labeled dataset then enables the development of an ML model through a training-validation--est cycle. Finally, the developed model can deployed for label production where the model used to classify a large number of data samples. We propose a new crowdsourcing methodology as tool for ML researchers such the ones who work on computer vision or natural language processing domains relying on manual image, video, or text annotations via crowdsourcing to train their recognition systems (Nowak & Rüger,, 2010; Rashtchian et al., 2010; Russell et al., 2008; Sawant et al., 2011; Su et al., 2012; Vijaanarasimhan & Grauman, 2011; Yan el al., 2010). Following our methodology, the envisioned human- human-machine beyond what is possible with large crowdsourcing efforts.
to achieve the best average labeling
machine system could yield data analysis at a scale even
Focusing on the first phase of the human-machine labeling framework shown in Figure 1, we make three contributions in this paper:
The problem of determining a budget-optimal flexible crowdsoureing strategy formulated as an optimization problem. The variables in our formulation represent the worker-to-task allocations, the sum of the worker costs is constrained to be upper-limited by budget, and the objective function measures the average accuracy of aggregated worker labels. We first focus on the setting where the task labels are binary and then address the general scenario.
For crowdsourcing tasks with binary labels, we propose the budget-optimized crowdworker allocation (BUOCA) algorithm that can efficiently find optimal solution to the corresponding optimization problem. BUOCA is greedy algorithm that runs in polynomial time.
We extend our binary formulation to the multiclass scenario. Our simulation experiments show the advantages of our multiclass BUOCA algorithm compared commercial optimization solver in terms of label quality and time-efficiency.
2

---

Published in Transactions on Machine Learning Research (01/2026)
2
Related Works
In recent years, the meaning and the focus of crowdsourcing has shifted from the practice of hiring online workers to annotate or analyze data to almost any online cormmationggaheriing practice such as Wikipedia article creation (Raković, 2023), online voting (Wijekoon et al., 2022), Internet of Things framework (Soda- gari, 2022), and so on. While these practices share a similar process as the crowdsourcing for data annotation, the nature of these tasks create task-spocific variables, resulting in very different scenarios when rescarchers analyze and study their procedures. Therefore, we wish clarify that this study focuses specifically on the original model of crowdsourcing: the recruitment of online workers for data annotation.
Balancing the demands that accuracy requirements and budget limits place on crowdsourcing experiments has been the focus of research in various communities, including machine learning (Chen et al., 2015; Dai et al., 2010; Gao et al., 2016; Karger et al., 2013; 2014; Kolobov et al., 2013; Manino et al., 2018; Simpson & Roberts, 2014; Tran-Thanh et al., 2013), humaa computation (Gurari & Grauman, 2017; Li & Liu, 2015; Sameki et al., 2016a), data management (Bansal et al., 2016; Davtyan et al., 2015; Gao al., 2013; Parameswaran et al., 2012; Wu et al., 2018), and computer vision (Gurari et al., 2016; 2018; Jain & Grauman, 2013). The crowdsourcing mechanisms used in practice, c.g., collecting image labels to train computer vision systems, are lypically agnostic to the dilficulty of task, assigning the same fixed nunber of crowdworkers to each task. Notable exceptions are the recent works by Gurari et al. (2018), Sameki et al. (2016a), and Gurari & Grauman (2017), who proposed flexible worker assignment schemes.
If experience ratings of crowdworkers exist and the difficulty of a task can be discerned, routing easy lasks to novice workers and difficult tasks to expert annotators has also been proposed (Kolobov et al., 2013; Karger et al., 2014). Optimal task routing, however, is an NP-hard problem, and so online schemes for task-to-worker assignments have been proposed (Bragg et al., 2014; Chang et al., 2015; Fan et al., 2015; Rajpal et al., 2015). Recently, the difficulty of crowdsourcing task has been linked to its ambiguity (Gurari et al., 2018). For some datasets, there may not be "correct" but only subjective labels.
Our work is different from previousty-propssee crowdsourcing methodologies with adaptive worker assign- ments (Chen et al., 2013a; Dai et al., 2010; Simpson & Roberts, 2014; Tran-Thanl et al., 2013; Welinder & Perona, 2010) because these assume that the same workers can be employed with "user profile tracking." The worker-task allocation scheme by Dai et al. (2010) relies on being able to "incrementally estimate [the workers' accuracy] based on their previous work." The algorithm by Tran-Thane ThanhThanh et al. (2013) relies a majority-voting-effciiat "fusion method to estimate the answers to cach of the tasks," " which also requires user profile tracking. Our methodology does not include user profile tracking because in our experiments using the Amazon Mechanical Turk Internet marketplace, we cannot request the same workers in an incre- mental scheme to estimate the accuracy of their work. Our work makes use of maximum likelihood estimate under certain conditions (Soction 3.2).
Moreover, our work is distinct from prior works that employ Markov Decision Process (MDP) (Li et al., 2016b; Chen et al., 2013b; Dai et al., 2013). These works model the crowdsoureing procedure using an MDP model which estimates, in real time, the next optimal action given the worker annotations in each time step of a crowdsourcing experiment. Our work, on the other hand, is a "batch method" that focuses on estimating the optimal number of workers roquired for each task before publishing the crowdsourcing jobs to the workers.
3 Proposed Crowdsourcing Methodology
In this section, we describe our budget-optimized crowdworker allocation problem and our proposed method to solve it. Our problem is formulated in terms of a combinatorial optimization program with an objective function that captures labeling accuracy and a budget that depends on crowdworker allocations. We first focus on binary labeling tasks and then discuss the general multiclass case. For binary tasks we establish the optimality of greedy allocation strategy when the decision fusion accuracy satisfies certain conditions.
3

---

Published in Transactions on Machine Learning Research (01/2026)
3.1 Formulation of Crowdsourcing Optimization
The goal of the budget-optimized crowdworker allocation problem is to maximize measure of overall labeling accuracy while ensuring that a measure of overall worker cost does not exceed target budget. This can be formulated as an optimization problem where the worker allocations to different data samples are positive integer variables, the overall labeling accuracy across data samples is the optimization objective, and the total worker budget the constraint.
3.1.1 Variables
In order to formalize approach, let the data samples be indexed by the positive integers i in the range (1,..., 7 and let denote the number of crowdworkers allocated to the i-th data sample. Let (ni, (,, denote the I-tuple of crowdworker allocations. We assume that every data sample is allocated at least one crowdworker and not more than N crowdworkers. Thus, for all i, we have n,, E (1,...,N} i.e., n E NI,
3.1.2 Crowdsourcing cost and budget
We only consider additive costs in this work. Specifically, the cost function fcost of the crowdsourcing experiment for crowdworker allocation tuple is defined by
feost (n) Scust (n1, n22 ..., n.)
Σ my
where e the unit cost. per sample per crowdworker.
We denote the total budget by B. Thus, feost (n) S B.
3.1.3 Crowdsourcing accuracy
We next define the measure of accuracy that use. Let Qi,, denote the probability that the decisions of crowdworkers when combined is correct for the i-th sample, i.e., it matches the ground truth of the i-th sample. Let Q be a matrix (lable) with I rows and N columns with value Q(i, n;) denoting the value in the i-th row and the nę-th column. Then, we can measure the overall accuracy of all tasks given allocation-tuple n (n1, 722 ...,,..,, ,,)" as the expected correct labeling rate (CLR) averaged across samples:
1 Σ mi) CLR(Q, n) =
(1)
We describe the computation of Q(i, m:) in the following sub-sections.
3.1.4 Problem statement
The budget-optimized crowdworker allocation problem is the following combinatorial optimization problem:
n,(Q,B1 := arg
max nE (1,...N1) Secm (nt)
CLR(Q, n)
(2)
3.2 Decision Fusion Method
The value of Q(i, nz) depends on the method used to combine decisions of crowdworkers as well as the underlying joint probability distribution of ground truth labels and labels assigned by crowdworkers. A varicty of models and methods for data aggregation have been studied in the litcrature, e.g., the survey by Li al. (2016a). In particular, some complex models can account for noise, expertise, and bias of annotators, but they have higher computational complexity and require additional information which may
4

---

Published in Transactions on Machine Learning Research (01/2026)
not be available. For example, annotator reliability on Figure Eight is based previously completed tasks which may not indicate reliability on new, completely unrelated task.
Therefore, we consider a different approach which is focused on the difficulty of the labeling task rather than worker factors. Specifically, we make the following assumptions which are motivated by the real-world unavailability of fine-grained information about task-difficllties, labeling noise, or the expertise, biases, and correlation of annotators, etc. For example, on real-world crowdsoureing platforms like Amazon Mechanical Turk, worker correlation information is not available for quality optimization.
Assumption 3.0.1. (Crowdworkers) The croudworkers are stalislically indisstinguishbble and make in- dependent decisions. In particular, the crowdworkers make independent and identically distributed (tid) decisions when annotating each sample.
Assumption 3.0.2. (Sumples) Each sample in the datasel has a single ground bruth label and the sam- ples together with their ground truth labels, are sampled in an iid manner according to some underlying distribution.
Assumption 3.0.3. (Model) We model the difficulty of labeling the i-th sample as pi, the probability of the said sample being labeled correctly by a randomly chosen crowdworker. The value of ps depends on the sample i, but we assume. that it is the same no matler what the ground truth label of the sample is which crowdworker labels it.
A high value of Ps indicates an easy labeling task, whereas a low value of ps indicates a hard labeling task.
To clarify Assumption 3.0.3, note that each task is composed of two parts: the content, e-g., text, image, etc., and the label. The assumption means that the probability of correct labeling depends directly the content and not on the label.
In Assumption 3.0.1, the probability that a decision will be correct depends on the sample. For any given sample, the probability of correctly labeling it will be the same for any crowdworker (statistical indistin- guishability of crowdworker of the sample being annotated.
making)), but the value of that probability will depend on the content
In Assumption 3.0.2, by "are sampled in iid manner according to some underlying distribution," " we mean that all workers receive tasks completely at random (neither the task requester nor the platform will inject any rules in distributing the tasks).
Additionally, we assume, for now, that the sample labels are binary, iee, the label space is y = (1, The extension multi-class cases will be discussed later Section (6).
In what follows, we will show, for the i-th task with n, worker labels, how infer the most likely label from worker annotations using the Maximum Likelihood Estimation (MLE), and how to calculate the probability that the inferred label is correct in terms of pa. This probability is precisely Q n;) under our approach.
3.2.1 Maximum Likelihood Estimate of Label from Crowdworker Annotations
Suppose data sample has been labeled by n; crowdworkers. Let the number of workers deciding classes 1 (onf(),(())
(1) and 2 be denoted by mf (1) and mn!" respectively and let M, (m, (1) mmf2)) Note that m; m n4. For
(2)
convenience we define M(n) as the set of all non-negative integer tuples that sum to n, i.e.
M(n) (m)))
((m))))))) .2)))): ml), m2)) E {0, I...., n), (1) m2) =n..
Then M, E M(n)). Let 4 E y= = {1,2) represent the true label of data sample i. Then, the probability of observing M, given 4 is given by the following:
P(M = =
n2
P: (1-p;)m--- mm
mlt) (1)
(1)
m;
P(MI7, =
T1;
(2)
P
m
(1 - -.
m
5

---

Published in Transactions on Machine Learning Research (01/2026)
more compactly by:
P(M[4) = ( 74
mm)
(1:)
Ps
m
(4)
(1 pi) pm) mm
(3)
The maximum likelihood estimate of the true label for data sample given M, is given by
UMLEE (M: arg max P(M: yE{1,2) arg max yE(1.2}
(4)
Pi (1- (1-p1) (1-pi)at-m²) mm
m.
(2)
(v)
mf9)
(1 - pp) p:)) m
arg max vE(1,2)
arg max (m! (2) log(p:) + (n: m( log(( p:))
vE(1,2)
arg max h(y, Pt) (E(1)2)
(5)
where the second equality follows from the combinatorial identity (m,,a)) = ni (m--m()) = (m)))) and
h(y, Mt) == :=m? log(p;) + (n; - m (v) log(1 ps).
(6)
We assume that if there is a tie between and 2 in Equation (5), then the tie is broken by choosing a label in {1, uniformly at random.
If the binary ground truth labels are equally likely, then the maximum likelihood estimate of the label from Mj is also the Maximum Aposteriori Probability (MAP) estimate of the label based in M, which minimizes the probability of estimation error. For simplicity and since the true label probabilities will not be available, use the maximum likelihood Estimate and make the following assumption:
Assumption 3.0.4. (Ground truth label) All values of the ground truth label are equally likely.
3.3
Computation of Q: MLE Accuracy
(0) Let Eg denote the event that MiLE ( M,) matches the ground truth 4, i.e., (ML)(MM) = 4. Then, Qii, n4) = P(Ex). When = 0.5, the probability of E, is trivially 0.5. When P: * 0.5, we can compute the P(F,) as follows:
(i)
P(E)) = -(E)== = Σ P(E.)M,,). P(MIL) P(L). 4. M.EM(n.)
In Equation (7), we only need to consider the choices of M, such that P(E. 4) > 0, i.c., choices of M, for which (() (M,) or equivalently by (5) only Mj such that the ground truth label 1, has the maximum likelihood:
Vy # 4. A(y,, Mr P.) & h(4, M,,p.).
(8)
Anticipating that there could be M, for which the likelihood of another label may be tied with that of I for the maximum, we define
In == M, E M(ni)
Vyu + 4, hyy,, Ms,p.) pr) S h11,, Pt)p:): with equality only for (d 1) values y # 4
(9)
as the of M, for which there are d labels whose likelihoods are tied for the maximum with the ground truth label 4 and where can range from through | 2. For all Mr Jnghhpads we have
P(E, 1
d
6

---

Published in Transactions on Machine Learning Research (01/2026)
We can now rewrite Equation (7) using puddipidd follows:
P(E)
d P(M(4) P(4)
(10)
By Assumption 3.0.4, P(4) follows a uniform distribution, i.e., P(I,) = 2- Moreover, the value of pt is the same no matter what the ground truth label of the sample (Assumption 3.0.3) and the crowdworkers make iid decisions (Assumption 3.0.1). It therefore follows that P(E,)4) the same for all values of 4. Therefore, Equation (10) be simplified by replacing 4 with an arbitrary label to and removing the outer summation:
2
P(E)) E
E
d ((M
(11)
d= M,E.ug
Finally, we can use (3) to express the quantity P(M](()) By doing so, we conclude the calculation of P(Fs),
which, by definition, exactly the value of Q(i,
0.5,
if p: = 0.5
@(i,m) P(E,) =
Σ
Σ
n4 (m(4))
m
Ro (1 (-p)) p:)
m
otherwise
(12)
d
(1o)
Pi
d=1
4 Greedy Algorithm for Crowdworker Allocation and its Optimality
The optimization problem defined in Section 3.1 is in general NP-hard. For the case when the task labels are binary, we propose greedy algorithm that finds an optimal solution in polynomial time.
4.1 Budget-Optimizee Crowdworker Allocation Algorithm
The algorithm, which we name as "BUdget-Opttmmized Crowdworker Allocation" (BUOCA) algorithm, takes input parameters Q, B and The first parameter is the table storing Q n,) values, while the second parameter B and the third one the budget and the unit cost respectively. The algorithm returns n, list of opti worker allocations for all tasks, as outputs. The pseudo code is described in Algorithm 1.
Algorithm BUOCA Algorithm (Q, B, c)
Initialize array n where cach entry n, stores the worker allocation for task Set all worker allocations (all entries of n) to be 1
Initialize the starting cost 3 =c cl
4: while 3 < B do
5: Find À = arg max, (Q(i,,Q(n,)) 2) Q(i, m4))
6: Set. B = 3 + 2c
7: 3 < then
Set n, nY +2
end if
10: end while
11: Return
Intuitively, the algorithu starts with the allocation of one worker per sample. This corresponds to a total allocation of I workers with a cost of cl. Then, the algorithm increases the total allocation by two workers step-by-step till the cost reaches the budget B. By the definition of CLR Equation (1), when two additional workers are allocated to task i, the CLR value changes by the amount (QQi, n, + 2) Q(i, n4)). Therefore, at each step m, the hm chooses the task sample À for additional allocation that results in the largest

---

Published in Transactions on Machine Learning Research (01/2026)
increase in CLR as follows:
arg max (a + - Q((,n)))) = arg max(i + - Q(i,..)
(13)
The algorithm finds globally optimal allocation by groedily accumulating locally optimal ones. In the next sub-section, we will show that the resulting worker allocation is indeed the globally optimal allocation.
4.2 Global Optimality of BUOCA
In this sub-section, we will prove the global optimality of BUOCA in sequence of theorems. We first relate our MLE approach to infer label from worker annotations to voting by simple majority, and then show how a simple majority vote leads to the global optimality BUOCA.
4.2.1 Relation between MLE and Simple Majority Voting
We first show that if Pi, the probability of task being correctly labeled by a random worker, is greater than half, then MLE is the same as majority voting.
Theorem 4.1. If p. > 0.5, then inferring the true label by the MLE approach from n, worker annotations is the same as voting by simple majority.
Proof. Suppose the task sample is labeled by n, workers and the worker label class counts are denoted as the tuple M, = (m,) m2). The maximum likelihood estimation of the true label of the i-th sample given by Equation (5). Let 5/ == ViLLe (M,) for convenience. Then must have the following property:
for all yi # v4, (w)) log(p:) + (n4 mi (o/) log(1 - p.) 2 m; (3+) The inequality can be simplified
log(p.) + (n4 m log( p.)
(m w/) (1)) (log) - log(11 - p:)) 2 0
- log(1 - p.)) > 0 and hence (m()) m, mm (1n) 2 In other words, m. (v)
If p; > 0.5, then (logp: majority vote in M; (m, (w/) m (1i)).
must be the
In similar manner one can show that if p: 0.5, then inferring the true label using the MLE approach from n, worker annotations the same as simple minority voting.
4.2.2 Relation between p. and (ii,
As shown in Equation (12), Q(i, nz) for ps * 0.5 is in fact, function of both pi and n. We denote this function by n:):
(ii, g(pi, n4)
Σ Σ
d
Mi (10))
PPi
m Go) (1 (1-pi)) p;) mm 0o)
(14)
d=1 MoEdin
We next show that g(pi, n.) is in fact, symmetric with respect to Theorem 4.2. Let q(p., nz) be function as defined in Equation (14), then g(pi, = 9(1 - Pi, mi).
Proof. When = 0.5 then 1-p: = case P: # 0.5. We recall the definitions of h(y, ps) from Equation (6) and Jn..oopp,dd from Equation (9):
0.5 and trivially we have q(p;, = q(l o(1-P;, n.). Now consider the
h(y, Mi, px) m!!) log(p:) (ns mn()) log(l pp))
8

---

Published in Transactions on Machine Learning Research (01/2026)
and
Unidepidd = { M, M((n)
Vy + 4, h(y, M, pc) h(4,, Mi. Mi.pi), with equality only for (d - 1) values of y + 1.5
Next observe that ,,1,M;,, M,,
M,, 1M,1-p). This implics that (m , .m: Inglimdd & (m m mm e Jn.,,,1-PP Therefore, there is bijection between Ingdupp,d and Inddel-pud such that for any element M; (m, (1) m E -n the corresponding clement in Incloped M (m, .m m Using this logether with the complementary properly of binomial distribution, have
(2)
(2)
((1 - ps. m4)
Σ
Σ
Th (1o)
(1 ps) m
0o)
P4
m (0)
mi
d=1
M,E io
Σ
Ti (1a)
a: m:
(1 pt pm) )mm (00
Pi
ni mi
(15)
d=1 McEJu, Ap.1----p
Σ
Σ
Thi
m (o)
(1 pj m 00)
(Ha))
Pi
d=1 do
=q(p;,
Therefore, we conclude that a(pi, n,) q(1 Pi, m.).
From Theorem 4.1 and Theorem 4.2, we can assume, without loss of generality, that > 0.5 when working with Equation (14). Then, In can be written as
(1) m E Z" m,
(2)
(1) (m, (m,"mm) .m.))
(2))
m
+ m; = n;i (1))
if d
(16)
for y + lo, m
m,
Jnsdoopedd
{( 74 T4
2 }}
if d 2 and nj is even
Ø
if d = 2 and n, is odd
Based on this observation, Equation (14) reduces to
m
Thi
la
Pi
m/
-p:))
if n, is odd
11
m
(ii,,,) ns)
(16)
Pi m
(1 -1--ph
P:)
mm
nns
p. (1
m1
p.)
4
otherwise
m
2
m
4.2.3 Allocation Incremental Size
Before proceeding to prove the global optimality of BUOCA, would like use the proven theorems to explain why BUOCA adds two workers for the selected task at each step. The initial number of workers allocated for each task is one, therefore, intuitively, adding two workers at each subsequent step can avoid ties. Nonetheless, we now show that adding only one worker at each step when the current worker number is odd will not change the CLR value. To do so, we first prove the following theorem.
Theorem 4.3. n zt, p [0, 1], and
Σ
pm (1 - p)
if n odd
m
(p,n)=
pd (1 p)
p- n m
p (1 +
otherwise
m
2 ?
wh= +1
If n. is odd, then n) =(0,

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. Suppose is odd, let (1) and observe that n n -a-11) a. Then, by the recurrence property of binomial coefficients and algebra, we have
(p, n + 1) = 2 a
ni + 1
p (1 1--p) p)a
Σ
n+1
n 1)
p²
(1 - p)mttlm
m
m=a+1
1
n
+
pd (1 p)c 0
Σ
n+1
+ m 1
} pTa - p) p)=
2
a
m
m=u+1
n+1
n+1
n
p
p)a +
n
p" (1 p))
n m
m -- -1 1pth - p)) )) + m
a
m
m=++1
m=a+1
n
n
1
pd (1
p)e + +(1 p)
n
pm (1 p)
m
pmt p)"
a
m
m
m
1=a+1
n
11
p
p)d
+
11
p"d (1
p)) m
m
m=a+1
13
n
p
m+1
(1 p) nm +
n
p ml (1 p) mmm
m
m
m=a
12
n
p 01 daa + a
p aat (1 p))
n a
pT (11 p)) pm
a
m
m=a+1
n1
p
1/ (1 p) ))m p + (1 p)
(=(1 p)) n
pd (1 p) n
a
m
11
p0(1 p)n nma a
pm (1 p) mm
m
m=a+1
n1
nd (1 p) n-
m
(p, n)
We now formally state the theorem regarding the incremental size.
Theorem 4.4. Let Q(i, n.) be defined in Equation (12). For any odd posilive inleger ni, Q(i, nz) = Q(i, +
1)
Proof. First of all, if p; = 0.5, then ni), = Q n4 + 1) = 0.5 is trivially true for all positive integer ny. Now, consider the case when * 0.5.
By Theorem 4.1 and Theorem 4.2, we can assume, without loss of generality, that p: > 0.5. Then, Q(i, n²) reduces to the form described in Equation (16). Finally, by Theorem 4.3, it follows that Q(i, n;) = Q(i, n4 +1) for any odd positive integer ni
4.2.4 Concavity and Monotonicity Properties of g(p,
We next prove the following theorem which establishes the concavity and monotonicity of (pp, The theorem not only serves as a stepping stone for the global optimality of BUOCA, but also suggests that, in practice, the while loop of the algorithm can stop early when no positive change of CLR can be made when choosing the next task by Equation (13).
10

---

Published in Transactions on Machine Learning Research (01/2026)
Theorem 4.5. If is an odd positive integer and p [0, 1], then
"
n)
Σ
12 m
p
(1
p)
is strielly increasing and concave with respect to the inleger variable n for all p > 0.5.
Proof. We shall first prove the monotonicity property of q(p,n)) n).
Since n is an odd positive integer, let n (2t - 1), where is a positive integer. Let X2)) ...., be independent and identically distributed Bernoulli(p) random variables. Then P(X[1] = 1) p ==
[[X = 0). Let S(4] X[1] + [ 1] denote the total number of successes in n = (21
Bernoulli(p) trials. Finally, let a[t] == P(S 2 t). Then, (p. = (p. 2t 1) alt).
Since Sit + 1] = S|d +
1], we can express (p, = alt = P(S + 1] 2 + 1) as follows:
+ -=01=~||||(000011))))))000111111
0)
- 0, X(2 + =
-124)))12 1| =0)
+ P(S[) -22(4)))((i = 1, 1|] =1)
P(S[) (1- P(S 2 t) (2p(1 p)) P(S 2 1) p²
Now, P(S 2 ()- all and P[S 2 ++1) = = = f). Also, P[S 1-1) = a|l]+ P(S -t Thus,
alt + 1] = alt] - -1-111 p0- t) + +p² P(S = -t- 1).
Since P(S 5) (1) p)> and (2t - 1), we have (i) (n"") = - and therefore
P(S = L 1) = P(S = (). p1ppp/p. Using this together with all + 1 =g(n + 2), and a q(n) in the
above equation we obtain:
(p, n + 2) = (p. + P(S t) (1 1)
The last term is positive p > 0.5, negative if < 0.5, and zero pf 0.5. This proves that p(p, n) is strictly increasing if > 0.5, strictly decreasing p < 0.5, and a constant (cqual to (0.5,, 1) = 0.5) if = 0.5.
We shall now establish the concavity property of g(p, n). From the proof monotonicity of g(p, n) we have
q(p, q(p,p) P(S t) (1 (1-p) ()p 1).
Then the ratio
(p, n + 4) (p,
P(S + 1] = ++
(2(+1) p'th))++((111 (1-+1111)22-11 2))2++1((++) (1-))((( 11-
q(, n +) 2) ((p,n)
P(S = t)
1
= 2pp pp) ++
++1
For all positive integers 1, 2(2/ 1)/(L + 1) < 4 and for all p * 0.5 have (p) < 1/4.. Tt. follows that if * 0.5, the ratio is strictly less than one. Thus, ((p,n) n) is strictly concave for all * 0.5.
4.2.5 Proof of Global Optimality of BUOCA
The final theorem states the global optimality of BUOCA:
Theorem 4.6. If for all i, Q(i, nz) is either (1) non-increasing or (2) increasing and concave with respect n,, then the greedy algorithm BUOCA returns globally optimal allocations and CLR values for all budgets from cl cNI, where is the unit cost, is the total number of tasks, and N is the marimum workers allowed for each task.
11

---

Published in Transactions on Machine Learning Research (01/2026)
Proof. First note that the monotonicity and concavity properties in the statement of the theorem only need to hold with respect to odd positive integers, as BUOCA only considers these values for nç.
For all data samples i for which Q(i, m²) is non-increasing, the optimal allocation is clearly equal to 1. The BUOCA algorithm will return this value for these samples since their initial allocation is 1 and they never get incremented because Q(i, n, 2-+))-210 ni) never positive. Thus the evolution of the BUOCA algorithm is unaffected by the presence of samples for which Q(i, is non-increasing.
Therefore, for the purpose of this proof assume, without loss of generality, that the increasing and concavity conditions in the statement of the theorem are satisfied by all data samples. Formally,
Vi E fI....,ff. Q(i,n.) n.) is increasing in ni.
(17)
and
E {1, (I....:T) [} and all odd positive integers n4: @ n4 + 4) Q my + 2) S Q(i, m, + 2) - Q(i.))))
(18)
Let us denote the iteration index (step) of BUOCA with variable m, the allocations at step n2(m], and the cost at step m as 3(m]. Since the total allocation is incremented at each step, proving the global optimality of BUOCA for all budgets from eT to cNT is equivalent to proving that when = cNT, CLR(Q, n(ml) is optimal for all m.
We have shown in Section 4.1 that the CLR value is increased step-by-step in BUOCA and the improvement is calculated
CL + 11) - (LLR(Q.((m)) } (Q(A, mx + Q(), (0(X,,)Iml) mmlm))
where I is the total number of tasks and À is selected according to Equation (13).
Since the Q(i, n''s are increasing in n, for all i, by construction, CLR(Q, n|m]) is increasing in m as well. The increasing trend only stops when the cost feost (n(ml) E/= n, [m] reaches the budget B, and we denote that final time step with my-
For convenience, we let ô; denote the tuple of length whose i-th component is and all other components are O. The proof is by induction on m.
Base case (step 1): For m 1, since there is only one feasible list of allocations namely: n ... nr[1] 1, is trivially globally optimum for the cost [[1] cJ. If my
done. If my 1, then for my we have the following induction hypothesis.
Induction hypothesis (step m): Let n[m] returned by BUOCA be globally optimum. Then, for all n' n'mm] that are feasible under the same cost,
n.R()n((m)) 2 CLR(Q, n' mm])))
Inductive step m m+ 1: Let n r''m+ + 1] be any feasible list of allocations for the next higher cost of 3 1] 8[m] 2c corresponding to two additional crowdworkers and let n(m + 1] be the corresponding allocation list returned by BUOCA. We will demonstrate that CLR(Q, n/m + 1]) 2 CLR(Q, n'(m + 1]) and thereby prove the result.
Since my, for À given by Eq. (13), we have
n/mm + 1] rl|m]] + 28x
(19)
12

---

Published in Transactions on Machine Learning Research (01/2026)
and for all e fl....,f.: I}
CLR(Q. n/m] + 25x)= 2 CLR(Q, n[m] + 26.).
(20)
It is sufficient to consider only n'mm + I] that have the same cost as n/m + 1] which, since m < my equals 8[m + 1] = A[m] + 2c. This because any lower cost feasible allocation list will have CLR. that is less than equal to the CLR of n n|m] which, by the induction hypothesis, is globally optimum for its cost. Since m < my, the CLR of n(mm] is in turn strictly dominated by the CLR of n/m + 1].
Hence we can focus on n' [m + 1] such that Ei= n'(m + 1] E n. [m + 1]. If (m + 1] * n + 1] then there is at least one sample j E {I....,4} 1 for which n//lm + 1] > ny im 1] or equivalently, since allocations can only be odd positive integers,
n' Im + 1] + +1 [m] +
(21)
where the last incquality is because in step m, allocations increase by 2 for sample À and do not increase for all other samples. This leads us to the following series of inequalities
CLR(Q, n(m + 1]) (0) CLR(n[m] + 26x)
2 CLR(n|m] 26,)
@ CLR(n[m]) + (Q [m] + + - Q m(ii))(mm)
" 11 26,) + + n, n,[m] + +2) - Q(j,
(6)
& (al(nn'm++1120 + (QU. m/ + 1J) - Q n/ + 1] - 2))
@ CLR(n'(m +1)) 1))
where (a) follows from Equation (19), (b) from Equation (20), (c) and (f) follow from the definition of CLR in Equation (1), (d) follows from the global optimality of n|[m] for the cost 3[m] and the fact that the cost of n' amm++ 1] equals {[m] + 2c, and finally, inequality (e) follows from Equation (21) and the concavity condition of Equation (18). To explain inequality (e) in more detail: ny [m], ny [m] + are two consecutive odd integers and so are nm[m=+ + 1] - 2, n³ [mm++m+ + 1). Equation (21) shows that the pair nt [m + 1] - 2, n [m + 1] is not to the left of (i.e., greater than or equal 1o) the pair ny[m], my(mm [m] + 2. The concavity condition of Equation (18) shows that the Q function increment over all consecutive odd integers can only decrease or remain constant as we consider larger and larger pairs of odd consecutive integers. This implies inequality (e).
5 Simulations to Demonstrate Effectiveness of BUOCA
We conducted simulated experiments to demonstrate the effectiveness of the BUOCA algorithm. Recall that the inputs to BUOCA are the budget B and the Q table containing the probabilities {p.} of correct combined worker decisions for all allocations of workers and all samples. Given Q, BUOCA provably yields optimal crowdworker allocations for any budget B.
While users of BUOCA may have a good idea about the maximum budget B they can expend, they may not know how difficult some tasks may be for a given pool of crowdworkers. Consequently, the (px) values that make up the Q table are not directly available in practice and would need be estimated from training data using suitable ML model. The main goal of this section is to explore the impact that inaccuracies in
13

---

Published in Transactions on Machine Learning Research (01/2026)
the estimation of the {p:} values have on the CLR of allocations found by the BUOCA algorithm. Figure 2 shows the simulation workflow in detail. The simulation workflow takes a dataset, including sample contents such as images, text, etc., and true labels (one for each sample). An ML model, such as a neural network, is then trained on the labeled dataset and then used to assign soft labels, i.c., the class probability values of the final softmax layer (or equivalent values if the ML model not a neural network) to any given input sample.
The workflow then splits into two branches, each producing a CLR score. According to the top branch, for each sample i, the soft label entry corresponding to the correct (ground truth) discrete label of that sample is chosen the probability of labeling (i.e., the P: valuc). These probability values are then used to construct the Q table, denoted by Qr, which is used to determine the ideal optimal allocation Ar. Lastly, a CLR score is computed based on Qr and Ar. In the bottom branch of the workflow, for each sample i, the soft labels are used to create simulated crowdworker labels: N crowdworker labels are generated randomly according to the soft label probability distribution for that sample and then the fraction of correct ones together with the ground truth label of the sample is used to construct the table Qs which is then used to determine the optimal allocations As. Lastly, CLR score is computed with Qr and As.
Table Constructor
Optimizer
Evaluation CLR
Simulated Labels
Contents
Model
Labels
Label Simulator
Table Constructor
Qs
Optimizer
Evaluation
CLR
True Labels-
ng
Figure 2: Simulation Workflow
Once the workflow is completed, we evaluate the performance of BUOCA when run potentially inaccurate input obtained from the ML model by comparing the two CLR scores (defined in Equa- tion (1)): CLR(Qr, Ar) for the top branch indicating the performance based on using the true Q table, and CLR(Qr,As) for the bottom branch indicating the performance based on using a Q table estimated from simulated crowdworker labels. Note that for the bottom branch, the Q table used for evaluation the one from the top branch since the top branch corresponds to the true Q table in these experiments.
The whole workflow is repeated for range of budget values so that we can observe a performance trend (except we only need to train the model once). For each tested budget value, We repeatedly simulate the bottom branch 100 times to estimate confidence bounds for the CLR evaluation.
Experiments Using Simulation Workflow on Textual Entailment Task
We applicd the workflow described previously a Recognizing Textual Entailment (RTE) dataset. The original dataset (namely, RTE1) was released by Dagan et al. (2005). However, we used subset of the released by Snow et al. (2008) and has been used by previous crowdsourcing
original dataset which works. There are 800 task samples in the RTE dataset each of which contains pair of sentences, namely text and hypothesis, and a binary ground truth label annotated by experts indicating whether or not the truth of the text leads to the truth of the hypothesis. Exactly half of the 800 samples are labeled negative while the other half are labeled positive.
To generate simulated worker labels we used a pre-trained DeBERTa model released by Sileo (2023). Instead of re-training the model on the dataset, we performed fine-tuning. The fine-tuning accuracy scores for
14

---

Published in Transactions on Machine Learning Research (01/2026)
Accuracy over Epoch
0.500
0.855
WW
0.570
0.500
Figure 3: Fine-tuning accuracy
different numbers of epochs are recorded in Figure The accuracy scores vary between 0.86 and 0.9, with higher accuracy for higher epoch numbers.
We varied two impactful parameters during the experiments: the epoch number for which the DeBERTa model was fine-tuned, and N, the maximum number of simulated annotations of each task. In theory, both parameters can affect the CLR values: the epoch number affects the model's prediction power and hence the correct labeling probability for each task, and the maximum number of simulated annotations directly impacts the Q table.
Discussion of Results
Our experiments suggest that both the number of fine-tuning epochs and the number of simulated crowd- worker annotations show positive correlation with the CLR score. Plots of CLR scores with respect to budget for diffcrent numbers of epochs and different maximum numbers of simulated crowdworkers are shown in Figure 4.
The plots in the same row of Figure 4 share the same fine-tuning epoch number, while the plots in the same column have the same maximum number of simulated per-task annotations. In cach plot, the blue curve corresponds to the CLR values obtained with the model's soft labels (lop branch Figure 2), the orange curve corresponds the mean CLR values obtained with the simulated annotations (bottom branch in Figure 2), and the green and the red curves show the standard deviation of the mean CLR values. For all plots, the budget ranges from single worker assignment per task to maximum worker assignment. The "mniform-allocation budget point" is the end budget point in each curve and corresponds to assigning N crowdworkers to each task.
As these plots show, increasing the number of fine- fine-tuning epochs or the number of simulated crowdworkers not only leads greater CLR values but also narrows the gaps between the ideal values (blue curve) and the mean values based on the ML prediction (orange curve). The DeBERTa model instance we chose was well trained that fine-tuning for only three epochs already yields high performance score and increasing the number of epochs quickly leads to diminishing improvements. For example, with the maximum number of workers set to 3, the highest idcal CLR value achieved is 0.95 using model fine-tuned for mercly three epochs (first row and first column of Figure 4). After fine-tuning for two more epochs (second row and first column of Figure 4), the CLR increases by only 0.01. On the other hand, increasing the maximum number of simulated crowdworkers per task seems create slightly more noticcable changes to the CLR score. Take the bottom row in Figure 4 for example. When the maximum number of workers per task is 3, the highest ideal CLR value about 0.971, which is also the highest CLR value in the same column of the
15

---

Published in Transactions on Machine Learning Research (01/2026)
figure. Nonetheless, increasing the maximum number of workers to 9 pushes the CLR up to about 0.984 and increasing N to 20 nudges the the highest CLR value to nearly 0.99.
Additionally, in all of the plots in Figure 4 there is a budget value after which the CLR improvement with increasing budget becomes negligible. For example, with the maximum number of workers set to 9 and a model fine-tuned for 5 epochs (second row and second column of Figure 4), the ideal CLR value begins exhibiting diminishing improvements around budget of 2000 and the curve stays nearly flat for budgets greater than 3500. Should the user desire to stop the execution of BUOCA at some point before the cost reaches the total budget due to diminishing improvements, they could easily modify the algorithm by introducing threshold for the marginal incrcase in CLR value.
In general, the phenomenon of diminishing improvements of CLR with increasing budgets is a consequence of the (provably) concave shape of the ideal CLR versus budget curve. Any decision to increase the current budget will depend on the steepness of the concave-shaped tradcoff curves and will differ from application- to-application. In some cases, the rise may be steep and in others, not much. As a rough practical recommendation, it would be highly beneficial to increase the budget in the regimes where the slope is high.
6 Multi-Class Extension
Thus far, we focused on binary task labels. We now show how to extend the binary label formulation to the multi-class scenario.
6.1 MLE and Inference Accuracy
The extension starts with a new quantity Piaf, the probability of task having ground truth label 4 being labeled as class x by a random worker. We maintain Assumption 3.0.1 and Assumption 3.0.2.
Next, we again use MLE to infer the true label for given n, worker labels. Let C' be the number of label classes and let M, = (m m2 ..... m!)) be the tuple of class counts of the n, worker labels. We infer the true label for a given M2 similarly to Equation (4).
The calculation of P(M y) needs to be adjusted to the multi-class scenario as follows:
R4 m
(e)
P(M y)
(C)
P
Pianly
(22)
m
m
This leads to the new expression for DMLE (Ma):
(i)
(M. = arg max P(M = =y)
y
T2:
m Pi
arg max
(1)
(C)
m
m
m
(23)
m (x) Piaely
arg max
arg max
m log(Pc.ly)
The calculation of P(E,), the probability that FMLB (M,) matches the ground truth 4, is very similar to the binary scenario. Nevertheless, the set Ingded needs to be modified follows
(8)
16

---

Published in Transactions on Machine Learning Research (01/2026)
Epochs 3 Workers
3 Epochs 9 Workers
3 Epochs Workers
0.99
ideal
simulation mean
0.98
simulation mean std
0.97
simulation
0.96
0.95
0.94
ideal
simulation simulation mean std simulation mean std
simulation
0.93
simulation mean std
simulation mean std
0.92
Epochs 3 Workers
5 Epochs 9 Workers
5 Epochs 20 Workers
0.99
simulation
0.98
simulation mean std
simulation mean std
0.97
0.96
0.95
0.94
ideal
ideal
simulation mean simulation mean
simulation mean simulation mean simulation
0.93
simulation mean
0.92
10 Epochs Workers
10 Epochs Workers
10 Epochs 20 Workers
0.99
0.98
0.97
0.96
0.95
0.94
ideal
simulation
simulation
simulation
0.93
simulation mean std
simulation mean std
simulation mean + std simulation mean std
simulation mean std
simulation mean std
0.92
15 Epochs 3 Workers
15 Epochs Workers
15 Epochs 20 Workers
0.99
0.98
0.97
0.96
0.95
0.94
Ideal
Ideal
ideal
simulation mean
simulation mean
simulation mean simulation simulation std
0.93
simulation
simulation std
0.92
1000
1500
2000
2000
4000
6000
5000
10000
15000
Figure 4: CLR-vs-budget plots for binary-label tasks.
Jnnhidea M, E M(m))
Vy Vy $ 4, h(4,,,, Mr, Pi.ju.) ) 2 h(y, Mi.Pi.-lk with equality only for (d - 1) values of +
}
17

---

Published in Transactions on Machine Learning Research (01/2026)
where
M(n) = (m m .n.......!!)) m²) m ......))) E
+ m +... + m (C) = n2).
and
Mi, = Σ
m
log(Ps.lo))
1=1
Lastly, the new form of Q(i, P(E,) is
if Pt, = C
for any ls
=
ni (M
m P
otherwise
(24)
Pizzlo"
d= MiE Po
This completes the calculation of Q(i, nz) in the multi-class label scenario.
6.2 Simplification
The calculation shown in Equation (24) requires the knowledge of all Ptaey values. This may not be practical in practice. However, one simplify the calculation by making the following assumption: Assumption 6.0.1. For each task
Pt
fx=y
Piayy
L-p: C-1
otherwise.
Under this assumption, again the quantity pt, the probability of task being correctly labeled by random worker, to express Qi,,n,):
1
1 p =
T
Q(i,n)== = P(Fs) =
1(Ts (M
(0)
/ 1
ny m
(a)
(25)
Σ
d
Pi
C-1
otherwise
1=1 M.
6.3 Adapted BUOCA Algorithm
The original BUOCA algorithm shown Algorithm is not suitable for the multiclass scenario as is designed for binary tasks. For example, the result that the worker allocation increment can be restricted two without loss of optimality (Theorem 4.4) would not hold, in general, for non-binary tasks. We therefore propose modified greedy algorithm, Multiclass BUOCA, described in Algorithm 2. In Multiclass BUOCA, the worker increment size is not held fixed in advance to specific value (like one or two).
As demonstrated in Section 4.2, the global optimality of BUOCA algorithm for binary tasks hinged on the Q(i, n,) function being either non-increasing or increasing and concave with respect to n, for all i. The multiclass Q(i, n:), unfortunately, does not enjoy these properties general. Therefore, unlike BUOCA, Multiclass BUOCA is not guaranteed to yield a globally optimal solution; only locally optimal one (being greedy algorithm).
6.4 Simulation Experiments for Multiclass BUOCA
We conducted simulation experiments following the same workflow described in Section 5, with the ML Model, the Label Simulator and the Optimizer changed for the multi-class scenario. Since Multiclass BUOCA
18

---

Published in Transactions on Machine Learning Research (01/2026)
Algorithm 2 Multiclass BUOCA Algorithm (Q, B,
1: Initialize array n where cach entry ny stores the worker allocation for task i
2: Set all worker allocations (all entries of n) be Initialize the starting cost 3 =ccl cl
Denote I as the number of tasks (i.c., the number of rows in Q)
Denote N as the maximum number of workers of each task (i.e., the number of columns in Q)
6: while 3 < B do
7: Initialize array s of length I where each entry 8; = 0 8: Initialize array d of length I where each entry d; = 0
for each sample do Find the smallest integer & E (0, ndl s.t. Qii, n4 + k) Q(i, m.) Set 8; k and d; Qii, + k) m(i,m))
10:
11:
12:
end for
13:
Find À = arg (d)
14:
Set 8 = 3+C. + 82
15:
B < B then
16:
Set π = ny + 9X
17: end if
18:
end while
19: Return
is not guaranteed to provide the globally optimal solution, we reformulated the optimization problem as an equivalent Integer Programming (TP) problem and compared the CLR versus budget curves and associated runtimes of Multiclass BUOCA and the state-of-the-art commercial IP solver Gurobi (Gurobi Optimization, LLC, 2024).
Experiments
For our multiclass experiments we used combination of two RTE datasets: RTE2 (Haim et al., 2006) and RTE3 (Giampiccolo et al., 2007). These two datasets contain the same five entailment labels, one of which is "no relation." Since the samples labeled as "no relation" occupy about half of the dataset, creating rather unbalanced scenario, we kept only the samples with one of the remaining four labels for simulation. This led to a dataset of 810 samples and the label ratios 205 187 : 206 212 which is close to uniform. The ML model used was again the pre-trained DeBERTa model released by Silco (2023), but with a classifier layer for four classes
Moreover, in order to use the IP solver, constructed IP problem equivalent to Equation (2) follows.
Σ Ej=1 Lij Q(i,))
max
s.t.
Σ 2j=1 Uij -ij= =1
i= 1 1,2,
(26)
Σ Σラ= Tij j
Vidj, Tij 0,1
In this IP problem, each binary variable Fy an indicator for an entry in the Q table. The first constraint ensures that only one entry in cach row of the Q table selected, while the second constraint corresponds to the budget limit.
To compare the efficiency of the two optimization methods, timed their execution processes when they were computing the "target" scores. Since there are thousands of budget points in these experiments, we selected 40 points equispaced between the lowest and the highest budget points and timed the execution between all consecutive budget points. When given a budget point B, Multiclass BUOCA being a greedy algorithm can compute the (possibly suboptimal) allocations for all budget points up to B. In contrast, the Gurobi IP solver can compute an optimal allocation only for the given budget point B. We therefore compare runtimes of Gurobi and Multiclass BUOCA in terms of both the marginal execution time between
19

---

Published in Transactions on Machine Learning Research (01/2026)
two consecutive budget points of interest as well as the accumulative execution time from the starting budget point.
Discussion of Results
Our experiments show that, while Multiclass BUOCA was slightly outperformed by the Gurobi solver in terms of CLR. when N is small, it was much more efficient than the Gurobi solver, especially when there are more budget points of interest.
We compare the accuracy of Multiclass BUOCA and the commercial solver in CRL-versus-uudget plots for different maximum numbers of simulated crowdworkers in Figure 5. The three plots in the first row of Figure show the results from Multiclass BUOCA while the ones the second row show the results from the Gurobi solver. All six plots are obtained using the same DeBERTa model fine-tuned for 100 epochs. There is noticeable difference between the plots in the first. column corresponding to maximum of three workers per task. However, the difference becomes insignificant in the other two columns. This observation suggests that when the maximum number of workers per task is not too limited, the suboptimal results from Multiclass BUOCA only trail behind the optimal ones from the commercial solver by a very small margin. Moreover, as in the binary case, we observe diminishing CLR improvements with increasing budgets, although unlike in the binary case we have not mathematically proved that the ideal CLR versus budget curve will always be concave. As in the binary case, a user could incorporate a threshold on the CLR improvement into the algorithm to stop early.
We compare the execution times of the Multiclass BUOCA and Gurobi solver for different maximum numbers of simulated crowdworkers in Figure 6. From these plots, we observe that it takes the Multiclass BUOCA and Gurobi solver similar amounts of time to find the optimal allocation if only a few budget points are given. The runtime of Gurobi solver, however, will skyrocket many budget points are being considered.
7 Conclusions
We modeled the optimal worker allocation problem in crowdsourcing as an optimization problem that aims to maximize aggregated label quality while under a budget constraint. We proposed probabilistic approach based on the Maximum Likelihood principle to model the decision fusion from workers during crowdsourcing, We showed that if the task labels are binary, then our proposed approach is equivalent to voting by simple majority.
We contributed a new algorithm, BUOCA, which can be used to conduct pilot crowdsourcing studies order to compute the average correct labeling rate of crowd workers for a given budget and dataset. We proved the global optimality of BUOCA for binary task labels. Further, we showed that Multiclass BUOCA, an adaptive version of BUOCA for multiclass task labels, achieves near-optimal allocations while costing only fraction of the time it takes for commercial optimization solver to find the optimal solutions. We would, however, like to note that the near-optimality of Multiclass BUOCA is purely an empirical demonstration. Theoretically quantifying the suboptimality of BUOCA for the general multiclass setting by developing approximation guarantees or data-dependent bounds is an important direction for future research. Lastly, the pilot study results can be used to estimate, for a given budget, the expected accuracy of the results subsequent larger crowdsoureing studies, where collecting expert labels is prohibitively expensive.
Other than the suboptimal property of Multiclass BUOCA, limitation of our approach, is the challenge to estimate task difficulty accurately. This limitation applies to both binary and multi-class task settings. Since the task difficulty is the cornerstone of our formulation, reliable mechanism to accurately estimate task difficulty without incurring additional cost is essential to bring our proposed approach into practice. The design of such mechanisms is an important direction for future work.
We also modeled costs as linear and identical across items. Some deployments face heterogencous item costs, batch overheads, and latency constraints, which not addressed in this work.
20

---

Published in Transactions on Machine Learning Research (01/2026)
BUOCA Workers)
BUOCA (9 Workers)
BUOCA (20 Workers)
target
target
0.80
simulation
simulation mean
simulation std
simulation mean std simulation mean
simulation mean std
0.75
0.70
0.65
0.60
target
simulation mean simulation mean + std
0.55
simulation mean std
Solver (3 Workers)
Solver (9 Workers)
Solver (20 Workers)
target
target
0.80
simulation mean
simulation mean
simulation mean std
simulation mean std simulation std
simulation std
0.75
0.70
0.65
0.60
target
simulation mean
simulation mean + std simulation mean std
0.55
2000
4000
2000
4000
2000
4000
Figure 5: CLR-vs-budget plots for multiclass tasks.
8 Broader Impact Concerns
The proposed budgeting strategy can change how platforms value human annotators. Aggressive cost min- imization may lower per task pay or reduce available work, which raises fairness concerns and may conflict with platform policies or local labor expectations. The reliance on a single difficulty score for each item can encode model bias and may direct more resources items that match majority patterns while neglecting minority or sensitive cases. used in safety critical domains such as medical triage or content moderation, error driven by miscalibrated difficulty estimates could lead to harmful outcomes for affected users. The work does not discuss privacy risks when difficulty is estimated with models trained on user generated data. The simulation setting does not evaluate impacts on worker well being such as fatigue, rejection rates, unfair quality control.
9 Acknowledgments
We dedicate this work to the memory of our beloved lale co-author, Prof. Margrit Betke, who saw this work through completion, but sadly passed away before its publication. This work stands as a tribute to her enduring legacy in the field of Computer Science and Artificial Intelligence. We thank all the reviewers and the Action Editor for their valuable feedback. The Broader Impact Concerns section is entirely the contribution of one of the reviewers.
21

---

Published in Transactions on Machine Learning Research (01/2026)
BUOCA Accumulative
Marginal
Solver Accumulaive
Solver Marginal
5
3
800
1000
1200
1400
1600
1800
2000
2200
2400
Workers
BUOCA Accumulaivve Marginal
25
Solver Accumultiive
Selver Marginal
5
0
1000
2000
3000
4000
5000
6000
7000
20 Warkers
50
DUOCA Accumulstive
BUOCA Marginal
Solver actumuaativ
Selver Marginal
2000
4000
6000
8000
10000
12000
14000
36000
Figure Runtime (in milliscconds) vs. budget plots for multiclass tasks.
References
P. Bansal, C. Eickhoff, and T. Hofmann. Active content- based crowdsourcing task selection. In CIKM '16 Proceedings of the 25th ACM International Conference Information and Knowledge Managemend,
22

---

Published in Transactions on Machine Learning Research (01/2026)
pp. 529-538, 2016.
J. Bragg, A. Kolobov, Mausam, and D. S. Weld. Parallel task routing for crowdsourcing. In Second AAAI Conference on Human Computation and Crowdsoureing (HCOMP 2014), pp. 11- 11-21, 2014.
S. Chang, P. Dai, Chen, and E. H. Chi. Got many labels? Deriving topic labels from multiple sources for social media posts using crowdsourcing and ensemble learning. In International World Wide Web Conference (IW3C2), pp. 397 406, May 2015.
X. Chen, Q. Lin, and D. Zhou. Optimistic knowledge gradient policy for optimal budget allocation in crowdsourcing. In Proceedings of the 30th International Conference on Machine Learning (ICML), Atlanta, Georgia, USA, 2013a. pages.
X. Chen, Q Lin, and D. Zhou. Statistical decision making for optimal budget allocation in crowd labeling, Journal of Machine Learning Research, 16:1-46, January 2015.
Xi Chen, Qihang Lin, and Dengyong Zhou, Optimistic knowledge gradient policy for optimal budget allo- cation in crowdsourcing. In International conference on machine learning, pp. 64 64-72. PMLR, 2013b.
Ido Dagan, Oren Glickman, and Bernardo Magnini. The pascal recognising textual entailment challenge. pp. 177-190, 01 2005. ISBN 978-3-540-33427-9, doi: 10. 10.1007/1173677 9.
P. Dai, Mansam, and D. S. Weld. Decision-theereticc control of crowd-sourced workflows. In Proceedings for the Twenty-Fourt AAAI Conference on Artificial Intelligence (AAAI-10), pp. 1168 1174, 2010.
Peng Dai, Christopher H Lin, Daniel S Weld, et al. Pomdp-based control of workflows for crowdsourcing. Artificial Intelligence, 202:52-85 2013.
M. Daviyan, C. Eickhoff, and T. Hofmann. Exploiting document content for efficient aggregation of crowd- sourcing votes. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM), pp. 783 783-790, 2015.
J. Fan, G. Li, B. C. Ooi, K. Tan, and J. Feng. icrowd: An adaptíve crowdsoureing framework. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Dala, pp. 1015 1030, 2015.
C. Gao, Y. Lu, and D. Zhou. Exact exponent in optimal rates for crowdsourcing. In M. F. Balcan and K. Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research (PMLR), pp. 603-611, 2016.
J. Gao, X. Liu, B. C. Ooi, H. Wang, and G. Chen. An online cost sensitive decision-making method in crowd- sourcing systems. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 217-228, 2013.
Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, and William B Dolan. The third pascal recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing, pp. 1-9, 2007.
D. Gurari and K. Grauman. CrowdVerge: Predicting if people will agrec on the answer to visual question. In CHI 2017: ACM CHI Conference on Human Factors in Computing Systems, pp. 8 pp., May 2017.
D. Gurari, D. Jain, M. Betke, and K. Grauman. Pull the Plug? Predicting if computers or humans should segment images. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Las Vegas, pp. 391, June 2016.
D. Gurari, K. He, B. Xiong, J. Zhang., M. Sameki, S. D. Jain, S. Sclaroff, M. Betke, and K. Grauman. Predicting foreground object ambiguity and efficiently crowdsourcing the segmentation(s). International Journal of Computer Vision, 126(7):714-78) July 2018
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https: https://www.wttt http::::://wwwwbbb..ooooo
23

---

Published in Transactions on Machine Learning Research (01/2026)
R. Bar Haim, Ido Dagan, Bill Dolan, Lisa Ferro, Danilo Giampiccolo, Bernardo Magnini, and Idan Szpek- tor. The second pascal recognising textual entailment challenge. In Proceedings of the Second PASCAL, Challenges Workshop on Recognising Textual Entailment, volume 7, pp. 785 794, 2006.
S. D. Jain and K. Grauman. Predicting sufficient annotation strength for interactive foreground segmentation. In IEEE International Conference on Computer Vision (ICCV), pp. 1313 1320, 2013.
D. Karger, S. Oh, and D. Shah. Efficient crowdsourcing for multi-class labeling. In Proceedings of the ACM SIGMETRICS, (GGMETiiSS/nneeeaaiionn Internaaionn Conference on Measurement and Modeling of Computer Systems, Piltsburgh, PA, USA, pp. 81-92, 2013.
R. Karger, S. Oh, and D. Shah. Budget-optimal task allocation for reliable crowdsourcing systems. Oper. Res., 62(1):1-22 24, February 2014.
A. Khetan and S. Oh. Achieving budgel-oplinaaiity with adaptive schemes in crowdsourcing, In Advances in Neural Information Processing Systems, 30th Annual Conference on Neural Information Processing Systems (NIPS), Barcelona, Spain, pp. 4851-4859, December 2016.
A. Kolobov, Mausam, and D. S. Weld. Joint crowdsourcing of multiple tasks. In 1st AAAI Conference on Human Computation and Crowdsourcing (HCOMP 2013), pp. 36-37, 2013.
A. Kovashka, O. Russakovsky, L. Fei-Fei, and K. Grauman. Crowdsourcing in computer vision. Foundations and Trends in Computer Graphics and Vision, 10(3):177-243, 2014.
Guoliang Li, Jiannan Wang, Yudian Zheng, and Michael J Franklin. Crowdsourced data management: A survey. IEEE Transactions on Knowledge and Data Engineering, 28(9):2296-231) 2319,, 2016a.
Li and Q Liu, Cheaper and better: Selecting good workers for crowdsourcing. In Works in Progress Abstracts. An Adjunct to the Proceedings of the Third AAAI Conference on Human Computation and Crowdsowrcing, pp. 20-21, 21, 2015.
Qi Li, Fenglong Ma, Jing Gao, Lu Su, and Christopher J Quinn. Crowdsourcing high quality labels with a tight budget. In Proceedings of the ninth acm international conference on web search and data mining, pp. 237 246, 2016b.
E. Manino, L. Tran-Thanke and N. R. Jennings. On the efficioncy of data collection for crowdsourced clas- sification. Proceedings of the Twenly-Sevend International Joint Conference on Arlificial Intelligence (IJCAI), pp. 1568 1575, 2018
S. Nowak and S. Rüger. How reliable are annotations via crowdsourcing: A study about inter-annotalor agreement for multi-label image annotation. In Proceedings of the International Conference on Multimedia Information Retrieval, pp. 557 566. ACM, 2010.
A. G. Parameswaran, H. Garcia Garcia-Molina, H. Park, N. Polyzotis, A. Ramesh, and J. Widom. Crowdscreen: Algorithms for filtering data with humans. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pp. 361-372, 2012.
S. Rajpal, K. Goel, and M. Mausam. of the 32nd International Conference on Machine Learning, Lille, France (ICML), 2015. 9 pages.
pool selection for crowdsourcing. In Proceedings
Slaviša Raković. Wikipedia object of research, ethnographic fieldwork and source of information (?): Netnography of the most popular online encyclopedia. Papers in Ethnology and Anthropology, 34(23): 29-50, 2023.
C. Rashtchian, P. Young, M. Hodosh, and J. Hockenmaier. Collecting image annotations using Amazon's Mechanical Turk. In Proceedings of the NAACL HLT 2010 Workshop Creating Speech and Language Data with Amazon's Mechanical Turk, pp. 139 147, 2010.
B. C. Russell, A. Torralba, K. P. Murphy, and W. T. Freeman. LabelMe: A database and web-based tool for image annotation. International Journal of Computer Vision, 77(133):157-177 2008.
24

---

Published in Transactions on Machine Learning Research (01/2026)
M. Sameki, M. Gentil, K. K. Mays, L. Guo, and M. Betke. Dynamic allocation of crowd contributions for sentiment analysis during the 2016 U.S. presidental election. In Work-in-progrees. The Fourth AAAT Conference on Human Computation and Crowdsourcing (HCOMP 2016), Austin, Teras, October 30 November 3 2016a. 10 pages.
M. Sameki, D. Gurari, and M. Betke. ICORD: Intelligent Collection of Redundant Data A dynamic system for crowdsourcing cell segmentations accurately and efficiently. In Workshop on Compuler Vision for Microscopy Image Analysis (CVMI), affiliated with the IEEE International Conference on Computer Vision and Pattern Recognation (CVPR), July 1, 2016, 2016b. 10 pages.
N. Sawant, J. Li, and J. Z. Wang. Automatic image semantic interpretation using social action and tagging data. Multimedia Tools Applications, 51(1):213 246, 2011.
Damien Silco. tasksource: Structured datasct preprocessing annotations for frictionless extreme multi-task learning and evaluation. Xiv preprinl arXiv:2301.05448 2023. URL https://arxiv wttp:/wwww.rg/bb//3/0000 05948.
E. Simpson and Roberts. Chapter Bayesian methods for intelligent task assignment crowdsourcing systems. In T.V. Guy al. (od.), In Scalable Decision Making: Uncertainty, Imperfection, Deliberation. Studies in Computational Intelliegence 538. Springer International Publishing Switzerland, 2014.
Rion Snow, Brendan O' O'Connor, Daniel J Jurafsky, and Andrew Ng. Cheap and fast but is it good? evaluating non-expert annotations for natural language tasks. In Mirella Lapata and Hwee Tou Ng (eds.). Proceedings of the 2008 Conference on Empirieal Methods in Natural Language Processing, pp. 254 263, Honolulu, Hawaii, October 2008. Association for Computational Linguistics. URL https://cclanthology org/ D08-1027.
Shabnam Sodagari. Trends for mobile iot crowdsourcing privacy and security in the big data cra. IEEE Transactions on Technology and Sociely, 3(3):199 225, 2022.
H. Su, J. Deng, and L. Fei-Fei. Crowdsourcing annotations for visual object detection. In Workshops at the Twenty-Ske Siath AAAI Conference on Artificial Intelligence, pp. 40-46, 2012.
L. Tran-Thanh, M. Venanzi, A. Rogers, and N. R. Jennings. Efficient budget allocation with accuracy guarantees for crowdsourcing classification tasks. In Proceedings of the 2013 International Conference Autonomous Agents and Multi-ogent Systems, pp. 901-908, 2013.
S. Vijayanarasimhan and K. Grauman. Largo-scale live active learning: Training object detectors with crawled data and crowds. In IEEE Conference on Computer Vision and Paltern Recognition (CVPR), pp. 1449-1456, 2011.
P. Welinder and P. Perona. Online crowdsourcing: rating annotators and obtaining cost-effective labels. IEFE Computer Society Conference on Computer Vision and Pattern Recognition Worksshps, pp. 25-32, June 2010.
Himesha. Wijekoon, Boris Schegolev, and Vojtëch Merunka. Online participation and crowdsourcing as a solution to mitigate news bias. International Journal of Electronic Governance, 14(1-2):112 130, 2022.
J. Wortman Vaughan. Making better use of the crowd: How crowdsourcing can advance machine learning research. Journal of Machine Learning Research, 18(193):1-46, 2018.
P. Wu, E. W. T. Ngai, and Y. Wu. Toward real-time and budget-aware task package allocation in spatial crowdsoureing. Decision Support Systems, (11(107-117)) 2018.
T. Yan, V. Kumar, and D. Ganesan. CrowdSearch: Exploiting crowds for accurate real-time image search on mobile phones. In Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services (MobiSys 10), pp. 77 90, 2010.
25

---

Published in Transactions on Machine Learning Research (01/2026)
A Appendix
A.1 Notations
To improve readability, we summarize important notations in Table 1 for quick reference.
Table 1: Notations
Notation
Mcaning
i
sample/tasi index
I
number of samples/tasks
C
number of classes
72
number of workers for task
N
maximum number of workers for a task
7
(M0, 122 .... n2) that is, worker allocation list
M,
(m, (1) (2) my (()), the class counts of certain list of worker labels for task
m.
pi
probability of correct labeling task by random worker
Pyz
probability of labeling task with label x given the ground truth label y
9y
probability of labeling task correctly given the ground truth label y
Q(i, n4)
probability of correct labeling task by the aggregation of random workers
26


Reviews:
[{"review_id": "9ffoTtRdnT", "reviewer": "Reviewer_U2vB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of worker allocation in a crowdsourcing setting. The problem is posed as an optimization problem, where the goal is to maximize the average accuracy of worker labels, while respecting the budget constraint on worker costs. The authors have proposed a BUOCA algorithm (a polynomial-time greedy algorithm) for binary labels and proved its optimality. Subsequently, the authors extend the algorithm for multiclass classification, and show its utility via experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "- The authors prove the global optimality of BUOCA algorithm for binary variables in Section 4.2. They also explain why no. of additional workers assigned to each task during the algorithm increases by 2 at each step (Theorem 4.3).\n- Results on multi-class extension are in Section 6.", "audience_yn": "Yes", "audience_explanation": "Crowdsourcing problems have seen a lot of work in past decade or so. The problem setting studied in the paper (albeit too simplistic), might be interesting.", "requested_changes": "Major\n- Surprisingly, almost all the references in the paper (except 2) are all pre-2019. This is concerning. What about the work that has happened in recent years? If there is recent work, the authors need to comment on how their work compares to it. If there is none (which I doubt), that raises questions about whether the TMLR audience is really interested in this problem. For example, some papers on a quick search include [1,2].\n- I'm also puzzled by the assumptions in Section 3.2. The crowdworkers are assumed i.i.d. since the authors only care about finding the number of workers per task. However, each sample is also assumed i.i.d. In that case, shouldn't $p_i$ (the probability $i$-th sample being labeled correctly) be the same across samples? The authors state that \"it is the same no matter what the ground truth label of the sample is or which crowdworker labels it.\" In combination, Assumption 3.0.1-3.0.3 seem too simplistic.\n- Also, give the assumptions, Theorem 4.1 is hardly surprising - if all workers are iid, of course MLE estimate is majority/minority voting (depending on $p_i$).\n\nThese are comments based on my very limited knowledge of the recent crowdsourcing literature. I would love to be corrected if I am mistaken.\n\n[1] Ding, Xingjian, et al. \"Optimizing worker selection in collaborative mobile crowdsourcing.\" IEEE Internet of Things Journal 11.4 (2023): 7172-7185.\n[2] Hikima, Yuya, et al. \"An improved approximation algorithm for wage determination and online task allocation in crowd-sourcing.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.", "broader_impact_concerns": "n/a", "additional_comments": "My main concern is regarding the absence of discussion on recent work, post-2019. This feels like a major omission.", "extra_scores": {}, "extra_text": {}}, {"review_id": "stFsyfzmlX", "reviewer": "Reviewer_39Dj", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**Summary**\n\nThe paper studies budget aware crowd labeling and frames worker allocation as an optimization problem that maximizes the expected correct labeling rate under a hard budget. Item difficulty is represented by a per item probability that a random worker answers correctly. From these probabilities the authors build a table $Q(i,n)$ giving the expected accuracy after aggregating n annotations for item $i$. They show how $Q(i,n)$ can be derived from maximum likelihood aggregation and its equivalence to majority voting in the binary case. Based on this structure they propose BUOCA, a greedy algorithm that starts with one worker per item and repeatedly assigns two additional workers to the item with the largest marginal gain in expected accuracy until the budget is exhausted. For multiclass labels they design Multiclass BUOCA that increases the number of workers by the smallest positive integer that improves Q for some item. Multiclass BUOCA is not guaranteed to be globally optimal but is efficient. Experiments follow a simulation workflow on textual entailment datasets. A fine-tuned DeBERTa model serves as a proxy for single worker accuracy. The results show that increasing model quality and the maximum workers per item improves the accuracy versus budget curves. Multiclass BUOCA is close to the Gurobi optimum when per item worker caps are not tight and is much faster in runtime across many budget points.\n\n**Strengths**\n\n- The problem is formulated with clarity by maximizing expected accuracy under an explicit budget constraint, which keeps the objective and constraints easy to interpret.\n\n- A precise link between maximum likelihood aggregation and majority voting in the binary case grounds the definition of Q(i,n) and supports later analysis.\n\n- BUOCA in the binary setting is simple to implement yet enjoys a global optimality guarantee under stated conditions, which gives the method strong theoretical footing.\n\n- Runtime efficiency is highlighted through an allocation path that naturally delivers solutions for many intermediate budgets, which is valuable for planning studies.\n\n- The multiclass extension is designed with a clear greedy rule and is compared against an exact integer program, providing a credible upper bound reference for accuracy.\n\n- Experimental design follows a transparent simulation pipeline that varies model quality and per item worker caps, making trends on accuracy versus budget straightforward to read.\n\n- Reproducibility is aided by a self contained setup for building the Q table from difficulty proxies, which lowers the barrier for future comparisons and ablations.\n\n\n**Weakness**\n\n1. This paper frames the goal as maximizing expected accuracy under a fixed budget. The analysis surveys multiple budget points, yet it does not present a clear Pareto frontier with marginal gains or guidance on how to choose a budget in practice.\n\n2. In this study item difficulty is represented by a per item correctness probability and workers are treated as homogeneous and independent. The modeling choice is neat, but there is no robustness check for correlated annotators, systematic bias, or learning effects.\n\n3. The proposed binary case theory is complete and well argued. External validity remains uncertain because the assumptions that enable optimality are strong and may not hold in many platforms.\n\n4. For the multiclass setting the manuscript introduces a greedy allocator that is efficient in runtime. The absence of approximation guarantees or data dependent bounds leaves the potential suboptimality unquantified beyond solver based comparisons.\n\n5. The experimental setup relies on textual entailment simulations with a classifier used as a proxy for worker accuracy. Evidence from real platforms and from other task families is missing, which limits confidence in generalization.\n\n6. Difficulty is estimated with a fine tuned language model and better proxies yield better curves. Calibration quality, estimation error, and distribution shift are not measured, so the sensitivity of the method to proxy quality is unclear.\n\n7. Costs are modeled as linear and identical across items. Many deployments face heterogeneous item costs, batch overheads, and latency constraints, which are not addressed in the current analysis.\n\n8. Figures report averages and spreads across budgets. Confidence intervals at representative points and simple significance tests are not provided, and diminishing returns are not quantified for decision making.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The binary setting includes a clear derivation of Q(i,n) from maximum likelihood aggregation and a proof that BUOCA is optimal under stated monotonicity and concavity conditions. The multiclass setting is evaluated against an exact integer program that serves as a credible upper bound, and the greedy method is shown to be close in accuracy while much faster. The simulation pipeline is transparent and varies both model quality and the cap on workers, which makes the accuracy versus budget trends convincing and easy to read.\n\nThat said, the evidence is narrower than ideal. Assumptions about homogeneous and independent workers are strong and robustness is not tested. The evaluation is simulation based on textual entailment and does not include a real platform study or additional task families. Multi-class results lack approximation guarantees or data dependent bounds. These gaps limit generality but do not undermine the main claims as framed by the paper.", "audience_yn": "Yes", "audience_explanation": "Parts of the TMLR audience that work on crowdsourcing, label aggregation, and resource allocation would be interested. The paper gives a clear objective and an optimal greedy method for binary labels. It also offers an efficient multi-class variant that is close to an exact solver in simulations. The results help readers who plan annotation budgets and need accuracy versus budget guidance. The methods and curves can serve as baselines for future work on budget aware labeling.", "requested_changes": "1. Can you provide a Pareto analysis across budgets with frontier plots and marginal gain per unit cost, plus a short guide for choosing a budget point.\n\n2. Please run robustness studies on the worker model by simulating correlated annotators and mixed skill groups, then report the stability of allocations and sensitivity to misspecified item difficulty.\n\n3. Is it possible for you to add calibration checks for the difficulty proxy. Compare raw probabilities with temperature calibrated versions, test both weaker and stronger proxy models, and show the impact on the Q table and the final curves.\n\n4. Can you include a small real platform study. Compare uniform allocation, a simple sequential stopping baseline, BUOCA, and the integer program when feasible. Report accuracy, unit cost, and latency distributions.\n\n5. Strengthen statistical reporting with confidence intervals at representative budgets and simple significance tests at selected points. Identify budget regions where marginal gains become small for decision making.\n\n6. Can you offer a brief multi-class theory note. Provide a data dependent bound or a condition under which the greedy allocation matches the optimum, narrowing the gap between the binary and multiclass results.", "broader_impact_concerns": "The proposed budgeting strategy can change how platforms value human annotators. Aggressive cost minimization may lower per task pay or reduce available work, which raises fairness concerns and may conflict with platform policies or local labor expectations. The reliance on a single difficulty score for each item can encode model bias and may direct more resources to items that match majority patterns while neglecting minority or sensitive cases. If used in safety critical domains such as medical triage or content moderation, an error driven by miscalibrated difficulty estimates could lead to harmful outcomes for affected users. The work does not discuss privacy risks when difficulty is estimated with models trained on user generated data, nor does it cover transparency to workers about how allocations are decided. The simulation setting does not evaluate impacts on worker well being such as fatigue, rejection rates, or unfair quality control.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4NcOVPdVRe", "reviewer": "Reviewer_LCGK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a method to optimize on worker assignment for crowd sourcing data labeling. The authors formulated this problem into a combinator optimization problem with an objective of labeling accuracy with a budget constraints. The authors firstly model the MLE accuracy with multiple workers and propose a greedy algorithm for crowd worker allocations. The authors further shows the global optimality of BUOCA and demonstrate the method can be applied to multi-class problem as well. The authors conducted experiments with simulated workers.", "claims_and_evidence_yn": "No", "claims_explanation": "The simulated experiment is over simplified with three workers and limited amount of data points. The performance improvements are also marginal. The reviewer cannot directly confirm the validity of the proposed method as there is no direct comparison with different conditions or previous methods/ baselines.\nIt’s also less intuitive to the reader that how the accuracy of MLE method is computed without knowing the labels from crowdsourcing labels. There have been many studies on uncertainties, active learning and active sampling that tries to quantify the uncertainty in model predictions or optimize data budget for machine learning without knowing the ground truth label. It’s unclear if they share similarities with the proposed method to help understand the validity of the proposed method.", "audience_yn": "Yes", "audience_explanation": "Some fields such as data optimization and uncertainty quantification can be potentially benefited by the research.", "requested_changes": "The writing can be improved as it’s hard to follow the keybindings on definition of MLE accuracy etc. The introduction also did not cover how the method is presented to solve the problems. The proposed method would be more sound if it’s validated by large-scale real-world experiments.", "broader_impact_concerns": "There is no immediate border impact on the proposed method as a general machine learning method.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)