| paper | d4-conf-ijcai-2018-0413 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a worker pool of size \(N\), rational type fractions \(\mu_t\) over a finite set \(T\), each type’s response model, a task-label distribution, an aggregation rule, and targets \(\epsilon,\eta,\delta\), choose a common participation share \(\alpha\in[0,1]\) and task intensity \(r\ge 0\) to minimize \(Q=N\alpha r\). Require the paper’s guarantees that the learned aggregator disagrees with the target rule on at most an \(\epsilon\) fraction of tasks with probability at least \(1-\delta\), and that the aggregation error is at most \(\eta\); report infeasibility if the available pool cannot meet them.
A finite supply of worker types \(T\) carries mass \(N\mu_t\), with each type specified by its response probabilities and any task eligibility used by the planner. The decision recruits mass \(N\alpha\mu_t\) from each type and assigns task intensity \(r\); the objective is total request mass \(Q=N\alpha r\), subject to the paper’s learning and error guarantees.
With the worker mix fixed, \(\alpha\) and \(r\) enter through \(Q=N\alpha r\), so the formulation adds little choice beyond inverting the paper’s cost bound.
fatal: False
The mirror covers Theorem 1’s query-cost guarantee and can include Theorem 2’s error certificate under a fixed type mix. It leaves the corollaries and the empirical comparisons of MV, WMV, and HDS outside the stated question.
The best case is a mirror of the paper’s worker-side query cost. A large crowdsourcing pool can naturally be treated as a population: many workers belong to a small number of ability cohorts, and the planning question is how much of each cohort to recruit and how many tasks to send them. That keeps the society continuous while leaving the paper’s answer noise and task distribution in place.
A type \(t\) would be a complete worker model for the problem: the worker’s confusion matrix across answers and true labels, along with any price or task eligibility the planner uses. Let \(\mu_t\) be the fraction of an eligible pool of size \(N\) in type \(t\), with \(\tau\ll N\). This is plausible for large microtask pools organized by qualification or latent ability class. The crowd still returns stochastic answers; the continuum describes the supply of workers, not their responses.
Theorem 1, proved in this paper, is the strongest anchor. It defines cost complexity \(O_W(\epsilon,\eta,\delta,f)\) for learning and using an aggregation function. For workers with answer probabilities \(\pi^{ij}_{kl}\), score contributions \(As_j(i,k,l)\in[a,b]\), and
\[
\nu_i=\sum_l \pi^{ij}_{kl}\bigl(As_j(i,g,l)-As_j(i,k,l)\bigr),
\]
the theorem says the cost can be computed from the worker distribution \(W\), the variance \(D_W(\nu_i)\), and expectation \(E_W(\nu_i)\), using the displayed formula
\[
O_W(\epsilon,\eta,\delta,f)=
-\frac{2}{\epsilon^2(1-2\eta)^2\ln(2|H|/\delta)}
\cdot
\frac{2\ln\!\left(\frac{\eta}{K-1}\right)(a-b)^2-D_W(\nu_i)}
{E_W(\nu_i)^2}.
\]
Here \(K\) is the answer-set size and \(H\) is the hypothesis class. The paper presents this as the number of requests needed to meet the stated parameter-learning and aggregation-error requirements.
Its continuous mirror is Continuous Crowdsourcing Cost. An instance gives \(N\), rational type masses \(\mu_t\), the type confusion matrices, a task-label distribution, an aggregation rule and hypothesis class, and targets \(\epsilon,\eta,\delta\). Choose a common participation share \(\alpha\in[0,1]\) and a task intensity \(r\ge0\) per participating worker; type \(t\) then contributes mass \(N\alpha\mu_t\). Minimize total request mass
\[
Q=N\alpha r,
\]
subject to the paper’s guarantees: the learned aggregator disagrees with the target rule on at most an \(\epsilon\) fraction of the task distribution with probability at least \(1-\delta\), and the rule’s aggregate error is at most \(\eta\). A solution is \((\alpha,r)\), the resulting estimated aggregator, and a certificate for those bounds. Fractional participation and task intensity are meaningful here as cohort averages; at finite scale they can be implemented by splitting workers of the same type across adjacent integer workloads.
For this fixed-mixture version, I expect the mirror to be tractable: it preserves \(W\), and the paper’s formulas reduce the question to computing type averages and choosing participation and task intensity. The next question is whether selecting different participation shares by type materially improves the cost, and whether the resulting query-planning problem remains tractable.
Theorem 2, also proved here, supports a distinct, narrower mirror. It bounds the mean error of a score-based aggregation rule: when each score contribution lies in \([a,b]\), the error is at most
\[
(K-1)\exp\!\left(
-\frac{\left(\sum_{i=1}^{m}\nu_i\right)^2}{2m(a-b)^2}
\right),
\]
where \(\nu_i=\sum_l\pi^{ij}_{kl}(As_j(i,g,l)-As_j(i,k,l))\) is the expected score difference for worker \(i\), true label \(k\), and alternative answer \(g\). The theorem’s proof requires a favorable expected margin for the truth; the squared expression alone would not certify low error if the expected margin favored a wrong answer.
Its mirror, Continuous Error-Mass Certification, takes a type mix \(\rho_t\) for the workers assigned to each task, the available pool masses \(\mu_t\), the scoring rule and response models, and a target error \(\eta\). It asks for the minimum participating worker mass \(M\), or reports infeasibility under the pool capacities, so that the continuous version of this bound is at most \(\eta\). For example, with positive truth-favoring margins \(\Delta_{k,g}=\sum_t\rho_t\Delta_{t,k,g}\), the bound at scale \(M\) is
\[
B(M)=\max_{k:D_k>0}(K-1)
\exp\!\left(
-\frac{M\left(\min_{g\ne k}\Delta_{k,g}\right)^2}{2(b-a)^2}
\right).
\]
A solution is the minimum \(M\) satisfying \(B(M)\le\eta\) and \(M\rho_t\le N\mu_t\) for every type. This inverse form is tractable for a fixed type mix; optimizing the mix is a further question.
The authors should recognize both as mirrors of their own problem. Their paper already uses a distribution over worker abilities \(W\), but the mirror gives that distribution a high-multiplicity interpretation: it is the supply of interchangeable workers in each cohort, with fractional cohort use and a query budget. This matches their central concern—how many workers and requests are needed for a chosen quality level. The mirror covers Theorems 1 and 2, not the paper’s whole empirical comparison of MV, WMV, and HDS. The corollaries credited to earlier work are useful context, but I would not count them as new anchors.
I expect both fixed-mixture questions to be tractable. The further type-allocation variant could be harder: its variables must jointly trade off available cohort mass against margins for several labels and alternatives. That is an open algorithmic question, not a hardness result in this paper.
The weakest point is that these anchors give statistical cost and error bounds; the paper does not prove a worst-case complexity result for solving a query-planning problem. The full mirror may therefore be a modest continuous optimization companion to the paper, rather than a new complexity landscape. There is also a close-neighbor concern: the paper already models worker ability through \(W\), so the positive case depends on distinguishing a distribution used to model random worker draws from an explicit continuous pool whose type masses constrain recruitment. The large-pool, few-cohort regime makes that distinction meaningful, but the paper does not itself develop it.
The strongest negative case is that neither anchor, as stated, asks the kind of computational question ChoCo is set up to classify. Theorem 1 bounds the number of human responses needed for a fixed aggregation rule and worker distribution; Theorem 2 bounds the resulting statistical error. Neither gives the running time or algorithmic complexity of choosing a recruitment plan. The paper’s \(W\) is already a distribution over worker abilities, and its formulas use \(E_W(\nu_i)\) and \(D_W(\nu_i)\). Replacing that law with rational masses on finitely many worker types would largely restate the fixed-mixture analysis in population language.
That is a limited objection: query complexity is a legitimate resource measure, and the paper explicitly cares about how many workers to hire. But the proponent’s fixed-mixture problem does not add a meaningful choice between \(\alpha\) and \(r\): with no further constraints, the cost depends on their product \(N\alpha r\). The nontrivial version chooses different amounts of each worker type. That version adds cohort capacities and makes \(W\) a decision variable. It could be a useful task-allocation problem, but it is an extension of the paper’s results, not a continuous mirror of Theorem 1’s fixed-distribution guarantee.
The same distinction weakens the Theorem 2 anchor. For a fixed worker mix, substituting type masses into the margin bound is a distributional calculation; the paper already expresses that calculation through worker abilities and their distribution. Minimizing the mass needed to meet the bound under type-specific availability constraints would be a clearer optimization problem, but the availability constraints and recruitment decision are added by the mirror. The theorem itself only certifies error for a specified set of workers.
There is also a mismatch with the programme’s subject. These workers are noisy labelers, and the target is an external ground-truth label. Majority voting appears, but the paper studies statistical inference and annotation cost, not a social-choice rule selecting a collective outcome from preferences. One could construct a crowd that votes among alternatives, but that changes what the answers mean and what error is being measured.
This is the best case against, not a decisive one. A large pool with a few ability cohorts is plausible, and the paper itself discusses task allocation and hiring, so its authors might recognize a capacity-constrained cohort-planning problem as theirs. That stronger version survives my objections. I cannot honestly make the universal claim that no worthwhile mirror exists; the negative case is strongest against treating Theorems 1 and 2 themselves as computational-complexity results over a continuous society.
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.