| paper | d4-conf-aaai-2000-0073 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm P\)); exact optimization is also polynomial-time solvable. · discrete side: other · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a decision tree \(D\), outcomes \(O\), and a finite set \(T\) of complete utility profiles \(u^t\in[0,1]^O\) with rational masses \(\mu_t\), choose an outcome \(o\) and threshold \(s\) for one common question. For each answer group \(A_-=\{t:u_o^t<s\}\) and \(A_+=\{t:u_o^t>s\}\), choose a strategy maximizing that group's total expected utility, and maximize the resulting value \(W_1(o,s)-W_0\), where \(W_1(o,s)=\sum_{a\in\{-,+\}}\max_{\pi\in\Pi}\sum_{t\in A_a}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t\) and \(W_0=\max_{\pi\in\Pi}\sum_{t\in T}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t\).
A large cohort is represented by rational mass \(\mu_t\) on each complete utility type \(u^t\). A clinic asks the same standard-gamble question of the cohort and recommends a strategy for each answer group, maximizing aggregate expected utility; thresholds between the supported utility values yield at most \(\tau+1\) distinct partitions per outcome.
The cohort's expected value of information is exactly the paper's single-patient calculation with prior \(p(U)=\mu\), so the population interpretation adds little new computation and requires a cohort-level objective.
fatal: False
The mirror covers one-round selection of a shared elicitation question, related to Proposition 1; it leaves out the full adaptive process, the stopping criterion, correlated-prior approximations, and the experiments.
The strongest honest mirror is a one-round, cohort version of the paper’s value-of-information question selection. The paper’s prior \(p(U)\) describes uncertainty about one patient’s utility. In this mirror, the patient population itself is a mass distribution \(\mu\) over complete utility profiles; a randomly selected patient’s prior is that population distribution.
Take a large prenatal-care program using the same decision tree \(D\) for everyone, with \(N\) nodes and outcome set \(O\). A type \(t\) is a complete utility vector \(u^t\in[0,1]^O\); all patients of that type have exactly the same preferences. The society is given by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). A plausible regime is thousands of patients drawn from a small library of fully specified preference profiles. The number of patients is large compared with the support size \(\tau\), and \(\mu_t\) means the fraction of patients with profile \(t\).
My lead anchor is Proposition 1, proved in this paper. Under its assumption that utility variables for different outcomes are independent, it says that a split point with the highest value of information for an outcome \(o\) occurs at an intersection point: a value \(s\) where two strategies that are each optimal for some value of \(U_o\) have equal expected utility. This is a structural result about choosing the next standard-gamble question, not a result cited from another paper.
The corresponding continuous problem is Cohort One-Question VOI. Ask the same question—outcome \(o\), split point \(s\)—of everyone in the current cohort. Choose \(s\) between supported utility values so that no one is indifferent. The answers split the population into masses
\[
A_-(o,s)=\{t:u_o^t<s\},\qquad A_+(o,s)=\{t:u_o^t>s\}.
\]
For each nonempty answer group, recommend the strategy \(\pi\) maximizing that group’s total expected utility. In notation, the post-question value is
\[
W_1(o,s)=\sum_{a\in\{-,+\}}\max_{\pi\in\Pi}
\sum_{t\in A_a(o,s)}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t.
\]
The no-question value is
\[
W_0=\max_{\pi\in\Pi}\sum_{t\in T}\mu_t\sum_{z\in O}P_D(z\mid\pi)u_z^t.
\]
The requested solution is an \((o,s)\) maximizing \(W_1(o,s)-W_0\), together with the optimal recommendation for each answer group.
I expect this problem to be Class A, tractable in \(|O|,\tau,N\), and the input bit length \(L\). For a fixed outcome, thresholds between the same two consecutive supported utility values produce the same answer partition, so it suffices to check at most \(\tau+1\) partitions. Each branch recommendation is computed by evaluating the explicit decision tree. Thus the cohort question and its answer policies can be found with polynomially many tree evaluations. This is the finite-type version of the paper’s question-selection task. Since a mass distribution over exact profiles has atoms, Proposition 1’s intersection-point claim need not transfer unchanged; the precise follow-up is whether policy intersections add useful witnesses beyond the profile-value breakpoints.
The scope here is deliberately narrow: the next-question computation and its two resulting recommendations. When \(n\mu_t\) is integral, this is also the per-capita calculation for a discrete cohort with those type counts; arbitrary rational masses give its high-multiplicity relaxation. It does not cover the paper’s full multi-round process, its stopping rule, or its correlated-prior approximation. Natural next questions are whether a shared interview-time budget across types changes tractability, and how the number of response groups grows over many adaptive rounds.
The weakness is that the paper’s core problem is personalized decision support for one patient at a time. A cohort system that asks a common question and aggregates expected utility is a plausible deployment of its method, but the authors may regard the population objective as an extension rather than their original question. Also, the paper supplies no hardness anchor: this case supports a tractable mirror of its elicitation algorithm, not a claim that discrete hardness dissolves.
Proposition 1 is a real computational anchor, so I would not dismiss it for lack of a named result. The difficulty is that the proposed cohort version does not add a new question to it.
Give each patient utility profile \(u\) and write \(g_\pi(u)=\sum_{z\in O}P_D(z\mid\pi)u_z\). For a common question \(q=(o,s)\), let \(A_-\) and \(A_+\) be the profiles that answer below and above \(s\). The cohort’s per-capita gain from the question is
\[ \sum_{a\in\{-,+\}}\max_{\pi\in\Pi}\int_{A_a}g_\pi(u)\,d\mu(u) \;-\; \max_{\pi\in\Pi}\int g_\pi(u)\,d\mu(u). \]
That is exactly the paper’s expected value of information when its prior \(p(U)\) is \(\mu\): the two integrals are the probabilities of each answer times the optimal expected utility under that answer’s posterior. Asking the same question of many patients and summing their expected gains just repeats the calculation per patient. For a finite support, the answer partition changes only at supported utility values, so the proposed enumeration is a finite-prior version of the same calculation. With a continuous prior, Proposition 1 already supplies the paper’s intersection-point analysis under its stated independence assumption.
The paper’s prior is not literally a society: it represents uncertainty about one patient, informed by data from a population of similar people. But that distinction exposes the problem with the mirror. If the clinic knows each patient’s complete utility type, it has no utility question left to ask. If it knows only the type distribution, that distribution functions as the prior in the paper’s existing problem. In neither case does population mass create a new computational object for this anchor.
A genuinely population-level extension could impose a clinic-wide interview-time budget, require one protocol across patients with different contexts, or add a social-welfare objective. Those constraints could couple decisions across patients and make the population matter computationally. They would also change the question: the paper’s Proposition 1 selects a question for an individual decision problem, while the extension allocates interview resources or optimizes a collective policy. A welfare sum would additionally need a defensible rule for comparing utility across patients. That may be a worthwhile project, but it does not rescue the proposed one-question mirror without adding a new problem.
So the negative case against this anchor is fairly strong as a claim of *new continuization*: its central calculation is already the paper’s VOI calculation over a distribution of utility profiles. It is weaker as a universal claim. A cohort with genuinely shared constraints could yield a recognizable and useful extension, though I cannot rule out that the authors would see that as their problem.
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.