| paper | d4-conf-aaai-2018-0249 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard under polynomial-time many-one reductions, already for \(\tau=2\) with Boolean domains, equal masses, and \(p_1=p_2=1\); also in \(\mathrm P_{\parallel}^{\mathrm{NP}}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 4.5
Given a finite-support distribution \(\mu\) over expert types \(t=(M_t,p_t)\), a default setting \(\vec v^*\), and a rational threshold \(q\), decide whether \(K(\mu)\ge q\), where \(K(\mu)=\sum_{t,s}\mu_t\mu_s p_t p_s\chi(t,s)\) and \(\chi(t,s)=1\) exactly when \(M_t\) and \(M_s\) are fully compatible with respect to \(\vec v^*\), and is \(0\) otherwise.
A large advisory panel has a finite catalog of expert types \(t=(M_t,p_t)\), each occurring with population fraction \(\mu_t\). Under the paper’s independent-confidence assumption, \(K(\mu)\) is the probability that two independently sampled panel members are both correct and their models are compatible.
The paper’s subset-conditioning semantics do not themselves induce this pair-sampling statistic: it is a new panel diagnostic, not the probability law used for the final merged-model decision.
fatal: False
It covers Proposition 4.5’s pairwise compatibility question and pairwise-compatible cases in Section 5; it leaves the minimal-intervention problem, intervention selection over merged models, and compatibility of larger expert groups untreated.
The best positive case is a narrow one anchored in Proposition 4.5, which the paper proves. It says that, for two compactly represented causal models, deciding whether they are fully compatible with respect to a default setting is in \(\mathrm{P}^{\mathrm{NP}}_{\parallel}\) and is co-NP-hard in the sizes of the models. The hard part is compatibility of the experts’ causal judgments; the proposition’s proof shows that the equation-agreement condition is co-NP-complete, while checking the structural condition is in \(\mathrm{P}^{\mathrm{NP}}_{\parallel}\).
A plausible high-multiplicity regime is a large policy or public-health advisory network whose members use a small catalog of standardized causal model cards and confidence levels. For example, many practitioners may share the same model and confidence because they were trained on the same template. A type is then a complete expert judgment \(t=(M_t,p_t)\): the causal model and the expert’s confidence in it. If there are \(N\) practitioners but only \(\tau\) such types, with \(N\gg\tau\), let \(\mu_t\) be the fraction of the panel of type \(t\). These are frequencies in an expert population, not probabilities over which causal model is true.
My lead mirror is Compatible Expert-Pair Mass. Its instance is a finite-support distribution \(\mu\), the types’ models and confidence levels, a default setting \(\vec v^*\), and a rational threshold \(q\). Write \(\chi(t,s)=1\) when \(M_t\) and \(M_s\) are fully compatible with respect to \(\vec v^*\), and \(0\) otherwise. Compute
\[ K(\mu)=\sum_{t,s\in T}\mu_t\mu_s p_t p_s\chi(t,s). \]
Equivalently, the decision version asks whether \(K(\mu)\ge q\). This is the prior mass, under the paper’s independent-confidence assumption, that two independently sampled experts are both right and their judgments can be merged. A solution is the exact rational value \(K(\mu)\), or the yes/no answer for the threshold version. The mass matters: it reports how much of the panel’s pairwise advice is jointly credible and mergeable, and it changes with the proportions of the expert types.
The paper’s Section 5 gives this statistic a foothold: it assigns prior weight to compatible sets of experts using products of their confidence values. Compatible Expert-Pair Mass asks for the population-level weight of the size-two cases. I think the authors would recognize it as a useful aggregate diagnostic for a large panel, though not as their main question of choosing the best intervention.
The expected direction is hardness transfers. With two types of mass \(1/2\) each and confidence \(1\), the self-pairs contribute \(1/2\) to \(K\), and the cross-pairs contribute another \(1/2\) exactly when the two models are compatible. Thus \(K\ge 3/4\) holds exactly when the models are compatible. Proposition 4.5’s co-NP-hardness therefore transfers even at \(\tau=2\). Conversely, for a support of size \(\tau\), checking the \(\tau^2\) type pairs in parallel and summing their rational weights keeps the threshold problem in \(\mathrm{P}^{\mathrm{NP}}_{\parallel}\), with the models’ encoding lengths and the mass bit lengths included in the input size. This is a useful boundary case for continuization: the aggregate mass is meaningful, but the hardness lives in the causal equations, not in the number of experts.
This mirror covers Proposition 4.5 and the pairwise-compatible cases used in the paper’s combination method. It does not recast Theorem 3.1’s minimal-intervention problem or claim to continuize the paper’s full intervention-selection objective. Natural follow-up questions are whether one can compute the mass of mutually compatible groups of three or more experts, and how to choose a cost-effective intervention across the resulting compatible merged models.
The weakest point is that this is a population-weighted diagnostic of a core subproblem, not a direct continuous version of the paper’s final policy choice. Compatibility is still determined between model types, and a single coNP-hard pair carries the hardness. The case survives that objection only in this narrower form: the paper explicitly treats compatible expert sets as inputs to its method, and a large panel with repeated standardized judgments gives the pairwise mass a concrete population interpretation.
The pair-mass proposal has a real modelling problem: the paper’s experts are epistemic sources, and their confidence values \(p_i\) are individual priors. The paper does not treat the fraction of people carrying a model card as evidence that the model is right. A large group trained on the same card could make a coherent population of practitioners, but its size may measure adoption rather than independent corroboration. If the members really are independent expert draws, then \(K(\mu)\) is a well-defined statistic about a randomly sampled pair; it still does not say which intervention the policymaker should choose.
That distinction matters because compatibility is a gate for merging models, not the paper’s objective. Two societies can have the same \(K(\mu)\) while their compatible pairs yield different merged equations and different intervention efficacies. So Compatible Expert-Pair Mass does not preserve the policy question the paper sets up. A fuller mirror would need to carry a distribution over compatible merged models through to intervention selection.
That fuller version also has no automatic continuum limit under the paper’s semantics. Correctness is a Bernoulli event for each named expert. With \(n_t\) copies of a type and fixed \(p_t>0\), the probability that at least one copy is correct is \(1-(1-p_t)^{n_t}\), which tends to \(1\) as \(n_t\) grows. Since merging duplicate models adds no new equation, positive-mass types become present with near certainty before compatibility filtering; conditioning on compatible subsets can then concentrate on admissible type supports. That is a limit over which model types are included, not a fractional version of the paper’s expert judgments. A different uncertainty model might yield a useful continuous problem, but it would need new semantics the paper does not supply.
This is the strongest case against the proposed mirror: its population mass describes panel composition, while the paper’s central computation concerns interventions under uncertainty over merged causal models. It does not establish that no useful scenario exists, though. Proposition 4.5 is a named computational result, and a weighted compatibility statistic for a standardized, repeatedly used catalog of models is mathematically coherent. The negative case is therefore weak at its hardest point: it can challenge whether that statistic matters to the paper’s policy task, but it cannot honestly rule out a worthwhile continuous mirror altogether.
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.