| paper | d4-conf-aaai-2002-0148 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard; the deterministic-response restriction is \(\mathrm{NP}\)-complete, and the general problem belongs to \(\mathrm{PSPACE}\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 1
Given finite \(D\), \(S\), and \(T\), rational masses \(\mu_t\) summing to \(1\), rational type utilities \(u_t\), outcome distributions, response probabilities, query costs, discount factor, horizon \(H\), and value threshold \(\eta\), is there a history-contingent policy choosing standard-gamble queries \(q_i(l)\), with rational \(l\in[0,1]\), or terminal decisions, whose expected discounted per-capita utility minus query costs is at least \(\eta\)? At each response history \(h\), querying type mass \(x_{h,t}\) splits it as \(x_{h,r,t}=x_{h,t}\Pr(r\mid q_i(l),u_t)\).
Treat \(\mu\) as the actual distribution of users over complete utility and response types. Policy choices apply to each response-history cohort; query responses split cohort masses, and the objective is expected per-capita terminal decision value less per-capita query costs. The resulting recursion is numerically the same as the paper's single-user belief POMDP.
The cohort recursion is exactly the single-user Bayesian update with an additive per-capita objective, so it adds no population-driven computation; the proponent acknowledges this separability, which bounds novelty but does not defeat the mass formulation.
fatal: False
The mirror covers Proposition 1's mixture-value computation and finite-horizon policy evaluation over type masses; it does not establish a population-complexity result for the paper's approximate infinite-horizon method or its experiments.
The paper has one numbered proposition that can serve as a limited computational anchor: Proposition 1, proved here, says that for a query \(q_i(l)\), its \(Q\)-value is linear in a mixture belief state:
\[
Q_i(\alpha_1\theta_1+\alpha_2\theta_2,l)
=\alpha_1Q_i(\theta_1,l)+\alpha_2Q_i(\theta_2,l),
\]
for mixture weights \(\alpha_1,\alpha_2\). The paper uses this identity to compute query values for mixture beliefs. It does not classify a problem as polynomial-time solvable or hard, though, so it is a weaker anchor than the programme ideally wants.
The lead mirror I would try is Mass Preference Elicitation. Consider a high-volume service giving personalized recommendations from a common finite decision set \(D\), with outcomes \(S\). A type \(t\) is a complete user profile for this problem: a utility vector \(u_t\in[0,1]^S\) and the query-response behavior relevant to elicitation. The society is a known distribution \(\mu\) over a finite support \(T\), with rational masses \(\mu_t\). There may be millions of users but only a modest number \(\tau=|T|\) of distinct profiles.
For a finite horizon \(H\), the input also gives the outcome distributions for each decision, the standard-gamble queries \(q_i(l)\) with \(l\in[0,1]\), response probabilities, query costs, and a discount factor. A policy maps each response history \(h\) to either a query \(q_i(l)\) or a terminal decision \(d_h\). Let \(x_{h,t}\) be the mass of type \(t\) at history \(h\). Asking a query to that history cohort splits its mass by
\[
x_{h,r,t}=x_{h,t}\Pr(r\mid q_i(l),u_t).
\]
The solution is an optimal finite policy tree, maximizing expected per-capita utility at its terminal decisions minus the query costs paid per unit of mass. Equivalently, the prover can be asked whether a policy reaches a given value threshold. A large clinical recommendation service is one plausible regime: many users share a relatively small set of preference and response profiles, while each user’s true profile remains unknown to the system.
Proposition 1 is a useful bridge because the normalized type composition in a response-history cohort acts as a belief over a representative user’s utility. The identity lets the system aggregate query values over mixture components. It does not itself prove the population problem tractable: the proposition concerns mixture beliefs for one user, while this mirror treats masses as an actual population.
My tentative expectation is Class B for exact finite-horizon optimization. The continuous population preserves the query-policy tree: a finite population of users following the same history-contingent policy has the same expected per-capita value as the mass model. Thus increasing population size does not erase the sequential planning choices. The paper supplies no hardness theorem for that finite counterpart, so this is a forecast about the mirror, not a result established by the paper. It also raises questions about the complexity in \(H\), \(\tau\), and the bit length of \(\mu\), and whether optimizing over continuous \(l\) changes the picture.
The weakest point is that the paper studies elicitation for a specific user, whereas this mirror lifts that process to many users receiving personalized decisions. With independent users and no shared resource constraint, the population may simply replicate the single-user problem rather than create a new computational landscape. The proposition is therefore a real but modest hook, not a complexity anchor. The scope of this case is only the multistage elicitation problem and its mixture-value computation; it does not claim to mirror every aspect of the paper.
The strongest case against this mirror is that its mass process is exactly the belief process of the paper’s single-user POMDP. Proposition 1 is a numbered result, but it is an algebraic identity about mixture beliefs, not a complexity classification. The paper gives approximate value-function methods and experiments; it does not establish a worst-case complexity result for elicitation.
For the proposed population model, let \(x_{h,t}\) be the mass of type \(t\) at response history \(h\), and let \(p_h=\sum_t x_{h,t}\). When that cohort receives query \(q\), its normalized type distribution is \(\theta_h(t)=x_{h,t}/p_h\). After response \(r\),
\[ p_{h,r}=\sum_t x_{h,t}\Pr(r\mid q,t), \qquad \theta_{h,r}(t)= \frac{\theta_h(t)\Pr(r\mid q,t)} {\sum_s\theta_h(s)\Pr(r\mid q,s)}. \]
That is precisely a Bayesian belief update for one representative user with prior \(\mu\). Terminal welfare for the cohort is \(p_h\,\mathrm{EU}(d,\theta_h)\), and query costs paid per unit mass scale the same way. So the finite-horizon policy tree has the same objective and recursion as the single-user POMDP. Proposition 1’s mixture linearity is part of that correspondence; it does not establish a new population computation.
This remains true if types include different response behaviors or query costs, provided users remain independent and the objective is additive: those attributes can be included in the representative user’s latent state. The proposed service setting supplies many users, but no computational coupling between them. The mass at each history is a probability of that history under the original belief model.
A shared query budget, fairness requirement, or other cross-user constraint could make the population a genuinely coupled optimization problem. But that would add the key computational structure absent from the paper, rather than mirror Proposition 1. Such a model might be worthwhile; it also means the universal claim that no scenario could support a worthwhile mirror is too strong to defend honestly. The proponent’s stated anchor does not survive as a distinct population problem, but the broader negative case is weak against reasonable extensions that introduce population-level coupling.
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.