| paper | d4-conf-aaai-2015-0580 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3 constructs an explicit convex loss, but its numbered claim concerns loss design and convexity; it does not establish an algorithm, running-time bound, or solver formulation used to compute an inference. The cohort LP is a statable follow-up derived from that construction, but it does not supply the missing computational result of this paper.
fails bit a — no named computational result to mirror
The proposed cohort formulation uses Theorem 3's no-spammer loss; it does not cover the paper's likelihood models, its spammer-aware convexity impossibility, or guarantees for nonconvex inference.
The strongest mirror is the paper’s Theorem 3, proved in the paper. The paper has no named NP-hardness or complexity-class result, so this is an optimization-method result rather than a hardness result. Theorem 3 constructs, for \(W_{\min}=0\) and \(W_{\max}=1\), the loss
\[
\ell_1(x,w)=
\begin{cases}
-w-x-1 & \text{if } w\le 2x-1,\\
w-5x+1 & \text{if } w\ge 2x-1.
\end{cases}
\]
It satisfies the paper’s \(P1\) monotonicity in answer accuracy and \(P2\) monotonicity in worker ability, and is jointly convex in \(x,w\). The paper also sets \(\ell_0(x,w)=\ell_1(1-x,w)\); summing these losses over worker-question responses gives a convex inference objective for multiple questions and workers. The authors prove this in the paper.
Here is the continuous problem I would put to a prover: Continuous No-Spammer Crowdsourcing Inference. A platform has \(d\) binary questions and a large worker population divided into \(\tau\) cohorts. A cohort consists of workers with the same modeled ability and task assignment—for example, a large pool of credentialed annotators completing the same benchmark. Let \(\mu_t\) be cohort \(t\)’s rational share of the workforce, with \(\sum_t\mu_t=1\), and let \(q_{tj}\) be the observed fraction of that cohort answering question \(j\) with \(1\). The unknowns are soft answers \(x_j\in[0,1]\) and cohort abilities \(w_t\in[0,1]\). Find a global minimizer of
\[
\Phi_\mu(x,w;q)=
\sum_{t=1}^{\tau}\mu_t\sum_{j=1}^{d}
\left[
q_{tj}\ell_1(x_j,w_t)
+(1-q_{tj})\ell_0(x_j,w_t)
\right].
\]
The mass is the fraction of workers in each cohort; \(q_{tj}\) aggregates their integral, individual responses. This continues the worker population while retaining the paper’s questions, answer variables, ability variables, and per-response loss.
This is a plausible high-multiplicity regime: a platform could have thousands or millions of workers but only dozens of modeled skill-and-assignment cohorts. For a finite workforce of \(N\) workers, setting \(\mu_t=N_t/N\) and \(q_{tj}\) to the within-cohort response fraction recovers the normalized sum of the same per-response losses. The continuous input records those fractions directly, so its size depends on \(d\), \(\tau\), and the rational bit lengths, rather than listing every worker. I think the authors would recognize this as their inference problem on a cohort population: the responses remain binary at the worker level, while their aggregate rate can be fractional.
For this precisely stated variant, I expect Class A tractability. Each \(\ell_1\) is the maximum of two affine functions, and \(\ell_0\) is its affine reflection, so \(\Phi_\mu\) is convex and piecewise linear. An epigraph formulation gives a linear program of size polynomial in \(d\), \(\tau\), and the input bit length. The output is a global soft-inference solution, not a guarantee that the answers are statistically correct or that rounding them recovers the discrete ground truth. Natural next questions are whether the same aggregation supports useful accuracy guarantees and what guarantees survive rounding.
The paper’s Theorem 1, also proved there, is a boundary on this case: no objective satisfying both Axiom 1 (distinguishing worker abilities) and Axiom 2 (making the objective independent of the answer when the worker is a spammer) can be convex. I would not present that as a hardness anchor. It explains why the mirror is specifically the no-spammer construction of Theorem 3; it does not establish that spammer-aware inference is computationally hard.
The weakest point is that Theorem 3’s authors explicitly do not recommend their constructed loss as a real crowdsourcing objective. It meets their qualitative properties, but the theorem does not establish statistical quality, and the cohort model assumes common latent ability within each type. So this mirror supports the paper’s convex-inference result in a credible high-multiplicity setting; it does not extend the result to the paper’s likelihood models or to spammer-aware inference.
The cohort formulation is mathematically sound. With shared cohort abilities and response fractions \(q_{tj}\), the proposed objective is a weighted sum of the paper’s piecewise-linear losses, so its minimization is an LP. A finite cohort dataset gives the same objective after aggregation. I would not attack it as a bad continuization: it makes the worker population continuous in a clear, exact way.
My case against it as a ChoCo mirror is that the paper’s named results are about model design, not computational complexity. Theorem 3 constructs a convex loss with certain qualitative properties; it gives no algorithmic or complexity result. The LP for the cohort variant follows directly from that construction. Theorem 1 likewise proves an impossibility about convexity, not hardness of an inference problem. A stronger mirror of Theorem 1 could ask about the complexity of spammer-aware inference over cohorts, but that would be a new global-optimization problem, not a computational result this paper establishes.
More fundamentally, the paper estimates an external ground truth and workers’ latent reliability. Its \(x_j\) are inferred answers to factual questions, and its \(w_i\) are nuisance parameters about answer quality. Workers supply noisy measurements; they do not express preferences over a shared set of outcomes. Adding cohort masses gives a continuous statistical-inference problem, but it does not turn that problem into collective choice. A version that instead aggregates preferences or selects a social outcome would change the paper’s target and its results.
There is also a modeling cost in the proposed compression: workers must share a latent ability as well as a task assignment. Ability is inferred, so grouping workers by it is an assumption about the population, not an observable cohort definition. That assumption can be sensible, but it narrows the model; retaining individual abilities removes the claimed reduction to \(\tau\) cohorts. This is a limitation of the particular mirror, not a decisive objection to every possible population model.
So the strongest negative verdict is a scope verdict: no scenario with many similar workers changes this paper into a computational social-choice result. I would not claim the continuous mirror is ill-posed or technically uninteresting. If ChoCo includes truth-oriented crowdsourcing inference, the proponent’s LP is a credible mirror, and my case against it is weak. For the programme as stated, the paper fits continuous statistical learning more naturally than continuous social choice.
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.