| paper | d4-conf-aaai-2011-0321 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper’s numbered results are Observations 1 and 2, not the required computational Theorem, Lemma, Corollary, or Proposition; its inference runtime claims are unnumbered. The proposed mass-query model is a plausible population extension, but no qualifying result in the paper anchors it.
fails bit a — no named computational result to mirror
No qualifying named result is covered; the proposed extension concerns recommendation and query selection, while Observations 1 and 2 remain query-selection identities for the paper’s model.
The positive case has a credible population regime, but this paper has no anchor of the kind your instructions require. Its named numbered results are Observations 1 and 2, not Theorems, Lemmas, Corollaries, or Propositions classifying a problem’s complexity. Observation 1 says that, in unconstrained problems, the feature with the lowest probability of getting the best guess right is the one with maximum Naive EVPI; it is proved in the appendix. Observation 2 gives a formula for computing Naive EVPI from the current belief. The inference bounds—\(O(3^nmk)\), \(O(nm)\), and \(O(lmk)\)—are stated in the text, but are not such numbered results. So I cannot honestly give a compliant complexity anchor or a per-anchor tractability prediction.
The strongest plausible mirror is a platform with a large, recurring crowd and a small number of stable expert behavior types. A type specifies an expert’s response behavior; \(\mu_t\) is the fraction of the crowd of type \(t\). Given a prior over conjunctive concepts, feature response models, feasibility constraints, and a query-mass budget, choose how much of each type to query about each feature and a final feasible configuration. The objective is to maximize the expected probability that the recommended configuration satisfies the true concept. That keeps the paper’s central decision—learn enough from noisy experts to recommend a satisfying configuration—and makes the population itself continuous. It does not continuize the configuration space.
This is a plausible continuous-population question, but the paper’s simulations and observations do not establish its complexity, and Observation 1 does not anchor the mass-allocation problem: it concerns the value of perfect information under unconstrained, feature-factorized beliefs. The weak point is therefore substantial: the mirror is recognizable, but the required named hardness or algorithmic result is absent, so the paper offers no anchored basis for placing it in the trichotomy.
The strongest case against is that this paper offers no named computational result for a continuous mirror to inherit. Its numbered results, Observations 1 and 2, are identities for query-selection heuristics: one relates minval to Naive EVPI under unconstrained, feature-factorized beliefs; the other gives a formula for that EVPI. Neither classifies a computational problem. The paper reports inference runtimes, but the exact, Naive Bayes, and Monte Carlo methods scale linearly in the number of experts \(m\); the exponential factor in exact inference is in the number of features \(n\). The paper’s computational difficulty is not shown to come from population multiplicity.
Those two Observations do not supply a stronger anchor. Their formulas contain no population parameter, so replacing a finite expert list with a mass distribution leaves them unchanged. To make them about allocating query mass, one would need to define a batch observation model: how many responses a queried mass produces, and how sampling noise behaves. In an exact continuum, aggregate response proportions can remove the finite-sample uncertainty that makes the Bayesian updates meaningful; retaining finite batches retains a discrete sample-size parameter. Either way, the new result would concern a redesigned experiment, not a continuous version of either Observation.
The proposed mass-allocation model is more promising than those anchors. Large crowds with recurring behavior types are a sensible high-multiplicity regime, and the paper itself makes expert selection part of its problem. But a useful model must preserve why it selects particular experts: an expert’s answers reveal both the shared concept and that expert’s reliability, while their subjective concept persists across queries. Aggregating only by the paper’s coarse behavior types loses that history. Including complete response profiles or query histories can preserve it, but then the resulting measure-valued Bayesian decision problem needs new assumptions and an analysis of its own. The paper does not show that this reformulation exposes a tractable optimization problem or a meaningful complexity boundary. The final recommendation also retains the feature-level integer program, whose difficulty is not reduced by making the experts continuous.
So I would argue against treating this paper as a strong, anchored target for ChoCo: its natural crowd setting passes the population-sense test, but the results it actually proves do not turn on population size, and the more ambitious mirror would be a new Bayesian query-allocation problem. I cannot honestly support the universal claim that no worthwhile mirror exists in any scenario. A high-multiplicity Bayesian elicitation problem could be worth studying; the negative case is weak precisely at the point where it must rule out that broader, plausible formulation.
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.