| paper | d4-conf-ijcai-2018-0313 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact minimization is polynomial-time solvable; an exact rational optimizer and optimum value can be computed in polynomial bit complexity. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 1
Given a pool size \(B\) and the error moments \(v,a,b,d\), choose recruited mass \(q\in[0,1]\) to minimize \(F_x(Bq)=\frac{Bqa+v+Bq(Bq-1)b+2Bqd}{(Bq+1)^2}\).
Represent the human pool as one type of mass \(\mu_h=1\), with available capacity \(B\); recruit mass \(q\), so the effective group size is \(n=Bq\). The machine remains external, and the objective is the paper’s expected squared error \(F_x(n)\).
As \(B\to\infty\), every fixed positive recruitment fraction \(q\) has limiting error \(b\), while the nontrivial finite group-size choice corresponds to \(q=O(1/B)\).
fatal: False
The mirror covers Proposition 1’s optimal group-size result. It leaves Proposition 2 and the empirical forecast-accuracy comparisons unmirrored.
The strongest positive case is a narrow mirror of the paper’s optimal group formation problem. Proposition 1, proved here, is the anchor. The paper has no named result classifying a problem as NP-hard, in P, or otherwise; this proposition instead gives a closed-form optimum for an expected-error minimization problem.
A plausible high-multiplicity setting is a recurring crowdsourced inflation forecast. Suppose a service can draw on a large pool of screened forecasters, all receiving the same prompt and compensation and sharing the same error behavior. That makes them one type for this problem, even though their individual forecasts differ. The machine forecaster remains a single external component, as in the paper. The authors themselves discuss crowdsourcing as a way to obtain human forecasts.
Here is the mirror I would put to a prover: Continuous Human–Machine Group Formation. An instance gives an input \(x\), the machine’s forecast-error variance \(v=\operatorname{var}(\varepsilon_\theta\mid x)\), the human error variance \(a=\operatorname{var}(\varepsilon_h)\), the average covariance \(b=\operatorname{cov}(\varepsilon_h)\) between two humans, the average machine–human error covariance \(d=\operatorname{cov}(\varepsilon_\theta,\varepsilon_h)\), and a large human pool of \(B\) equivalent forecaster units. The society has one human type with mass \(1\); the decision is what fraction \(q\in[0,1]\) of that mass to recruit, so the recruited effective group size is \(n=Bq\). The machine and recruited humans contribute to the same equally weighted ensemble as in the paper. Using its moment model, the expected squared error is
\[
F_x(n)=\frac{na+v+n(n-1)b+2nd}{(n+1)^2}.
\]
A solution is a recruiting fraction \(q\) minimizing \(F_x(Bq)\), together with the resulting expected error. To match Proposition 1’s stated regime, take instances satisfying \(d<(3b-a)/2\).
Proposition 1 says that when this condition holds, the unconstrained real-valued minimizer is \(n^\star=0\) if \(N^\star\le 0\), and \(n^\star=N^\star\) otherwise, where
\[
N^\star=\frac{2v-a+b-2d}{3b-a-2d}.
\]
For a pool of capacity \(B\), the corresponding solution is \(q^\star=\min(B,\max(0,N^\star))/B\). The proposition also says that if group size must be an integer, an optimum is one of the two integers bracketing \(N^\star\). These claims are proved in this paper.
I expect this mirror to be tractable: its stated objective has a direct formula for the optimum, so the mass version adds no difficult optimization step. The scope is just the paper’s question of how many humans to combine with the machine; it does not extend to choosing among different human categories. The type and regime are plausible, and the paper’s own real-valued analysis makes the continuous version recognizable to its authors.
The weak point is that the continuum contributes little new computation: Proposition 1 already optimizes over real \(n\) before relating the result to integer group sizes. Also, although the paper motivates the method partly by recruitment costs, its proposition minimizes forecast error rather than error plus cost; adding a recruitment budget or cost objective would be a different anchor. This is a credible high-multiplicity mirror, but not a case where discrete hardness might dissolve in the continuum.
The proponent’s anchor is Proposition 1, and its proposed continuous variable is already in the paper: \(n\) ranges over all nonnegative reals, with a closed-form optimum \(N^\star(x)\). Writing \(n=Bq\) for a recruitment fraction \(q\) of a pool of size \(B\) changes the units, not the optimization problem. The paper even explains how to round the real-valued optimum when a group must contain an integer number of people. So this particular mirror adds no new continuous question for the programme to chart.
A genuine population limit creates a different problem. For a pool of size \(B\), the proposed objective is \(F_x(Bq)\). As \(B\) grows, for every fixed \(q>0\), this converges to \(b=\operatorname{cov}(\varepsilon_h)\); at \(q=0\), it is \(v\). The limit therefore erases the interior choice of recruitment fraction: any positive mass has the same limiting error. Keeping the paper’s nontrivial dependence on group size requires keeping finite effective sample size \(Bq\), which returns us to the paper’s scalar problem. Adding a recruitment-cost tradeoff might restore an interior choice, but Proposition 1 does not optimize error and cost together.
There is a better possible mirror: split forecasters into categories, such as academic and industry experts, and choose masses from each. That is more than renaming \(n\). It would require type-specific and cross-type error covariances and a group-composition model the paper does not analyze. The paper does say that considering multiple types is future work, so this extension could be recognizable to the authors. Yet the current result does not establish that its covariance data support such a population model; with interchangeable forecasters, the continuum limit washes out the individual sampling variance that drives the group-size decision.
The negative case is therefore strong against the anchor actually offered: its continuous scalar optimization is already solved in the paper, while a high-multiplicity limit removes the decision the proposition studies. The universal claim is weaker. The authors’ own mention of multiple forecaster types leaves a plausible, recognizable extension, and I cannot honestly rule out every useful continuous model built around it.
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.