| paper | d4-journals-jair-2018-0019 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
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}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
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\).
A high-multiplicity marketplace has worker-type shares \(\mu_t\), with each type specifying fixed annotator parameters, per-annotation cost \(c_t\), and capacity \(h_t\). Keep the samples finite; choose the mass \(x_{ti}\) of type-\(t\) workers assigned to sample \(i\), minimizing \(\sum_{t,i}c_t x_{ti}\) while meeting the posterior-precision targets and respecting type capacities and the one-worker-per-sample limit.
The allocation freezes calibrated worker types and omits the response-driven learning and exploration central to O-CBS+; the proponent acknowledges this omission but does not establish that the authors would recognize the offline allocation as their problem.
fatal: False
The mirror covers Proposition 1’s posterior precision and O-CBS’s precision-based sample selection; it leaves out annotator-parameter learning, O-CBS+ exploration, and the paper’s experimental comparisons.
The positive case is narrow. This paper has no named computational-complexity result of the kind your anchor rule requires. The relevant named statement is Appendix A, Proposition 1, proved here: with \(y_k\sim N(a_{j_k}w_{j_k}(x_{i_k}+b_{j_k}),w_{j_k}^2/\lambda_{j_k})\) and a flat prior on \(x_i\), the posterior of \(x_i\), conditional on its annotations and fixed annotator parameters, is Gaussian with mean
\[
\frac{\sum_{k:i_k=i}\lambda_{j_k}(w_{j_k}^{-1}a_{j_k}y_k-b_{j_k})}{\sum_{k:i_k=i}\lambda_{j_k}}
\]
and variance \(\bigl(\sum_{k:i_k=i}\lambda_{j_k}\bigr)^{-1}\).
The paper computes with this formula, but it does not assert that a computational problem is in P or establish a hardness result. The NP-hardness mentioned for Guo, Parameswaran, and Garcia-Molina is cited related work on a different problem, not a numbered result of this paper. So I would not pass Proposition 1 off as a qualifying anchor.
It does, however, support a plausible, deliberately limited mirror: Continuous Consensus-Threshold Allocation. Imagine a large annotation marketplace for repeated, standardized tasks, where workers fall into a small number of exact, calibrated contract classes. A type \(t\) completely specifies a class’s annotation parameters \((a_t,w_t,b_t,\lambda_t)\), price \(c_t\), and per-worker capacity \(h_t\). The society is the distribution \(\mu\) over these worker types; the number of workers is much larger than the number of types. The samples remain a finite set \(I\).
For each sample \(i\), let \(P_i\) be its current total precision and let \(\delta_i\) be its target posterior variance. Choose \(x_{ti}\geq 0\), the mass of type-\(t\) annotation capacity assigned to sample \(i\). The problem is to minimize \(\sum_{t,i}c_tx_{ti}\), subject to
\[
P_i+\sum_t\lambda_t x_{ti}\geq \frac{1}{\delta_i}
\quad\text{for every }i,
\qquad
\sum_i x_{ti}\leq \mu_t h_t
\quad\text{for every }t.
\]
A solution is a minimum-cost allocation meeting every sample’s precision target. Given known rational type parameters and capacities, this is an LP, so I expect this particular mirror to be Class A.
The connection is to O-CBS after annotator calibration: the paper selects samples using posterior precision and selects annotators using competence scores. This allocation problem lets interchangeable worker mass take the place of individual workers. It covers that calibrated allocation stage, not O-CBS+’s exploration of previously unknown annotators, and it is a proposed problem rather than a result established by the paper.
The weakest point is substantial: the LP optimizes the paper’s uncertainty proxy, not accuracy against an unknown ground truth, and assumes worker types are already known. The paper’s Bayesian learning and exploration decisions are central to its broader method. So there is a sensible population-continuous question here, but the paper supplies no qualifying computational anchor for it.
The strongest objection is that this paper gives no qualifying computational result to mirror. O-CBS and O-CBS+ are proposed algorithms evaluated experimentally; the paper states no complexity theorem for a computational problem. Proposition 1 is a useful posterior formula, conditional on fixed annotator parameters, but it is not a complexity result. The NP-hardness claim belongs to cited work on a different problem. So there is no named complexity result here whose continuous version would chart ChoCo’s landscape.
The proposed Continuous Consensus-Threshold Allocation is the best counterexample to that objection. A large pool of workers in standardized, interchangeable classes is a plausible high-multiplicity setting, and the finite set of samples need not itself be continuized. But the proposed LP captures only a calibrated budgeting stage. It assumes known type parameters and assigns each unit of type-\(t\) capacity a fixed precision contribution \(\lambda_t\). O-CBS and O-CBS+ instead choose annotations sequentially while learning annotator parameters from observed responses; O-CBS+ also explores new annotators. A minimum-cost allocation to meet precision thresholds leaves out that central uncertainty and decision process. It may be a useful optimization problem, but it is an added surrogate, not a continuous version of a computational result established by this paper.
A stronger mirror could put the sequential process itself over a continuum of workers, with unknown worker classes, observed annotation responses, and exploration decisions. That is more faithful, but it runs into the paper’s dependence on annotator histories: M-CBS learns \(a_j,w_j,b_j,\lambda_j\) from the responses of particular annotators. Aggregating workers into known, identical classes removes the learning problem that motivates exploration. If class membership or quality is unknown, the model must preserve enough history to link repeated annotations to the same worker; a mass allocation over classes alone does not do that. A richer state over worker histories might be possible, but the paper supplies no compact formulation or computational result to anchor it.
So the negative case is not that crowd workers cannot occur in large, repeated populations; they plainly can. It is that the proponent’s clean continuous model gets its tractability by isolating a downstream allocation question, while a faithful mirror must recover the paper’s unanalysed sequential learning problem. That makes the proposed anchor weak for this programme, though not a proof that no worthwhile extension could be built.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.