Answer: The minimum-cost mass-assignment problem is exactly solvable in polynomial time in \(m,\tau,L\), including infeasibility detection and an optimal rational assignment. Its budget decision version belongs to \(\mathrm{P}\).
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateIf the distribution of yk is N yk; ajkwjk(xik + bjk), w2 jk λjk , then the poste- rior distribution of xi is xi|{yk, θjk : k ∈Ki} ∼N xi; X k:ik=i λjk(w−1 jk ajkyk −bjk) X k:ik=i λjk , X k:ik=i λjk −1 (12) where θj = {aj, wj, bj, λj} is the set of parameters of annotator j and Ki = {k ∈K : ik = i} is the set of annotations of sample i.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite sample set \(I\), initial precisions \(P_i\), variance targets \(\delta_i>0\), and a distribution \(\mu\) over calibrated worker types \(t\) with precision \(\lambda_t\), cost \(c_t\), and per-worker capacity \(h_t\), find the minimum-cost assignment masses \(x_{ti}\geq 0\) such that \(P_i+\sum_t\lambda_t x_{ti}\geq 1/\delta_i\) for every \(i\), \(x_{ti}\leq\mu_t\), and \(\sum_i x_{ti}\leq\mu_t h_t\) for every \(t\).
Let \(I\) be a nonempty sample set with \(m=|I|\). A society is given by its support: the list of the \(\tau\) worker types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has fixed calibrated precision \(\lambda_t>0\), cost per annotation \(c_t\geq0\), and integer capacity \(h_t\in\{0,\ldots,m\}\). Each sample has initial precision \(P_i\geq0\) and variance target \(\delta_i>0\). All numerical data are binary rationals; \(L\) is the total input bit length.
Initial observations come from outside the available worker population. Every available worker can annotate every sample, at most once per sample and at most \(h_t\) samples overall. Worker mass is divisible.
An assignment consists of real masses \(x_{ti}\geq0\), costs \(\sum_{t,i}c_tx_{ti}\), and gives sample precision \(P_i+\sum_t\lambda_tx_{ti}\); variance is its reciprocal, interpreted as infinite at zero precision.
Find the minimum cost subject to \(P_i+\sum_t\lambda_tx_{ti}\geq1/\delta_i\), \(x_{ti}\leq\mu_t\), and \(\sum_i x_{ti}\leq\mu_th_t\), or determine infeasibility.
Is this minimum-cost mass-assignment problem solvable in polynomial time in \(m,\tau,L\), or is its budget decision version NP-hard, with a binary-rational budget \(B\geq0\) included in \(L\)?
For finitely many calibrated annotators, independent Gaussian annotations and a flat prior give consensus posterior variance equal to the reciprocal of total annotator precision; this establishes no assignment-complexity classification.
[Hu and Frazier](https://proceedings.mlr.press/v51/hu16a.html) study Bayesian effort allocation with homogeneous workers in continuous time, a different problem. The search located no result settling exactly the mass-assignment problem defined here.
Classification. The minimum cost and an optimal assignment can be computed exactly in polynomial time in \(m,\tau,L\), or infeasibility can be determined. The budget decision version belongs to \(\mathrm{P}\).
The proof uses the stated interpretation: worker mass is divisible, and assignments are real masses. Below, we also verify that the aggregate capacity constraints faithfully represent the individual worker limits.
1. An equivalent rational linear program. Index the samples by \(i\in\{1,\ldots,m\}\) and the supported types by \(t\in\{1,\ldots,\tau\}\). Define the additional precision requirement
\(\displaystyle d_i=\max\{0,1/\delta_i-P_i\}.\)
Because \(\lambda_t x_{ti}\geq0\), the original precision constraint is equivalent to \(\sum_t\lambda_t x_{ti}\geq d_i\). Thus the required optimization is exactly the following linear program:
\(\displaystyle \text{minimize }\sum_{t=1}^{\tau}\sum_{i=1}^{m}c_t x_{ti}\)
subject to
\(\displaystyle \sum_{t=1}^{\tau}\lambda_t x_{ti}\geq d_i\qquad (i=1,\ldots,m),\)
\(\displaystyle 0\leq x_{ti}\leq\mu_t\qquad (t=1,\ldots,\tau;\ i=1,\ldots,m),\)
\(\displaystyle \sum_{i=1}^{m}x_{ti}\leq\mu_t h_t\qquad (t=1,\ldots,\tau).\)
Every feasible assignment satisfies these inequalities, and every solution of these inequalities is an assignment as defined in the question. The objective is precisely its annotation cost.
2. The encoding has polynomial length. This program has \(n=m\tau\) variables and \(r=2m\tau+m+\tau\) inequalities, counting the lower and upper bounds separately.
All its coefficients are rational. Computing the new right-hand sides requires only rational inversion, subtraction, multiplication, and comparison. These operations produce numbers of polynomial encoding length. Explicitly, if \(\delta_i=a/b>0\) and \(P_i=p/q\), with positive denominators, then
\(\displaystyle d_i=\max\left\{0,\frac{bq-ap}{aq}\right\}.\)
The numerator and denominator have \(O(L)\) bits. Likewise, multiplying \(\mu_t\) by \(h_t\) adds at most \(O(\log(m+1))\) bits.
Consequently, even a dense encoding of the constraint matrix, right-hand sides, and objective has length
\(\displaystyle O\bigl((r+1)(n+1)(L+\log(m+1))\bigr),\)
which is polynomial in \(m,\tau,L\). Repeating the coefficients of a supported type across samples causes only polynomial expansion; no unsupported types need to be enumerated.
3. Exact optimization and budget decision. We use the standard polynomial-time theorem for rational linear programming: given an explicitly encoded rational linear program, a deterministic algorithm can detect infeasibility or unboundedness, or return an exact rational optimal solution, in time polynomial in its binary encoding length. This is the bit-complexity theorem, rather than a bound that treats arbitrary-precision arithmetic as unit cost. See [David Karger’s MIT notes on linear-programming algorithms](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
Its hypotheses hold here by Sections 1 and 2. Furthermore, since \(\mu_t>0\) and \(\sum_t\mu_t=1\), every feasible coordinate lies in \([0,1]\). The feasible region is closed and bounded. Therefore, whenever it is nonempty, it is compact, and the continuous linear objective attains a finite minimum.
There is also no obstacle from potentially irrational assignments. A nonempty bounded rational polyhedron has vertices, and a linear objective attains its minimum at a vertex. At a vertex, \(n\) linearly independent active constraints determine the coordinates. Clearing denominators produces an integer linear system with polynomial-length entries. Cramer’s rule expresses each coordinate as a ratio of determinants. If the entries have absolute value at most \(2^K\), each determinant has absolute value at most \(n!2^{nK}\), hence polynomial bit length. Thus an exact optimal rational assignment has polynomial encoding length.
Applying the rational linear-programming algorithm therefore returns an exact optimum and assignment, or determines infeasibility, in polynomial time.
For the budget decision problem, append the single inequality
\(\displaystyle \sum_{t=1}^{\tau}\sum_{i=1}^{m}c_t x_{ti}\leq B.\)
This remains a rational linear program of polynomial encoding length, because the encoding of \(B\) is included in \(L\). Its feasibility is exactly the budget decision question. Hence that question belongs to \(\mathrm{P}\); NP-hardness under polynomial-time many-one reductions would imply \(\mathrm{P}=\mathrm{NP}\).
4. Individual worker limits are respected. For completeness, the aggregate constraints do not conceal an additional combinatorial feasibility condition.
Fix a type \(t\), and normalize its assignment by setting \(y_i=x_{ti}/\mu_t\). The type’s constraints become
\(\displaystyle y\in Q_h:=\left\{y\in[0,1]^m:\sum_i y_i\leq h\right\},\qquad h=h_t.\)
We prove that every vertex of \(Q_h\) is integral. Suppose a feasible point has a fractional coordinate.
If \(\sum_i y_i<h\), sufficiently small positive and negative perturbations of that coordinate remain feasible. The point is the midpoint of two distinct feasible points, so it is not a vertex.
If \(\sum_i y_i=h\), there must be at least two fractional coordinates: exactly one is impossible because \(h\) and all other coordinates would be integers. Perturb two fractional coordinates by opposite amounts. Sufficiently small perturbations in both directions preserve the sum and all coordinate bounds. Again, the point is not a vertex.
Thus the vertices are precisely incidence vectors of subsets of samples of cardinality at most \(h\). Since a bounded polyhedron is the convex hull of its vertices, write
\(\displaystyle y=\sum_S\alpha_S\mathbf{1}_S,\qquad \alpha_S\geq0,\qquad \sum_S\alpha_S=1,\qquad |S|\leq h.\)
Divide the type’s worker mass into groups of masses \(\mu_t\alpha_S\), and assign each group exactly the samples in \(S\). Every worker annotates each assigned sample once and at most \(h_t\) samples overall. The mass assigned to sample \(i\) is exactly \(\mu_t y_i=x_{ti}\).
This verifies the intended worker-level meaning as well as the polynomial-time classification.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: exact minimum-cost optimization and the budget decision problem are polynomial-time solvable in the stated binary input model. No major or minor issues were found.
\[
\sum_t\lambda_t x_{ti}\geq \max\{0,1/\delta_i-P_i\}
\]
therefore preserves feasibility in both directions. The objective, coordinate bounds, and type capacity constraints exactly match USER_TASK. Initial observations contribute through \(P_i\), without consuming available worker capacity.
\[
d_i=\max\left\{0,\frac{bq-ap}{aq}\right\}
\]
is correct, and \(aq>0\). Products and differences of these input integers have \(O(L)\) bits. Multiplication by \(h_t\leq m\) adds at most \(O(\log(m+1))\) bits. The proposed dense encoding bound is a valid polynomial upper bound. Crucially, the formulation enumerates only the \(\tau\) supported types.
The vertex argument remains valid when the feasible region has lower dimension. At a vertex, sufficiently many linearly independent active constraints determine the coordinates. Clearing rational denominators leaves integer entries of polynomial bit length. The determinant bound \(n!2^{nK}\) is valid when \(K\) bounds the bit magnitude of all entries involved, including the right-hand side for the replaced determinants. Its bit length is polynomial. This supports the claim that an optimal rational assignment has polynomial encoding length. The algorithmic conclusion relies on the stated exact LP theorem, rather than merely on the existence of a short optimum.
\[
\sum_{t,i}c_tx_{ti}\leq B
\]
expresses precisely the existence of a feasible assignment within budget. Since \(B\)'s encoding is included in \(L\), this preserves polynomial encoding length. The conclusion that the decision problem belongs to \(\mathrm{P}\) follows. The qualification concerning NP-hardness and \(\mathrm{P}=\mathrm{NP}\) is also correct.
Both perturbation cases are valid. With slack in the sum constraint, a fractional coordinate admits sufficiently small perturbations in both directions. With the sum equal to integer \(h\), exactly one fractional coordinate is impossible; opposite perturbations of two fractional coordinates preserve the sum and coordinate bounds. Thus no fractional point is a vertex.
The statement identifying the vertices with feasible incidence vectors is correct. The finite-dimensional bounded-polyhedron theorem applies because \(Q_h\) is nonempty and bounded. The resulting convex decomposition realizes precisely the required sample masses using divisible worker groups, each assigned a subset of size at most \(h_t\).
No additional clarification is needed. The Gaussian observation and the different allocation model mentioned in USER_TASK are not used as complexity evidence.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.