d4-conf-ijcai-2017-0677

The best mirror I see is for Proposition 11, the paper’s result that its interactive backward-induction algorithm uses polynomially many preference queries and polynomial time in \(n_T\) and \(1/\delta\). The authors prove it here; it is not a cited result. In context, the algorithm returns a policy with regret at most \(\delta\), assuming its utility-dominance and regret calculations can be done by polynomial-time linear programming. The paper gives no named hardness result to anchor a hardness-dissolution question, so this is a positive case for extending an algorithmic result.

A plausible regime is a large health system choosing one sequential treatment protocol for a large cohort. Many patients share one of a small number \(\tau\) of preference types: the same normalized utility curve over outcomes, and the same treatment tree and chance probabilities. Each type has mass \(\mu_t\), the fraction of the cohort with that curve. A population of tens of thousands with a few dozen modeled types is a sensible high-multiplicity regime. The continuous object is the population distribution \(\mu\), not the paper’s lotteries or spline functions.

Here is the mirror I would ask a prover to study: Mass-Weighted Adaptive Elicitation for Sequential Policies. The input is an explicit decision tree \(T\), a support of \(\tau\) types with rational masses \(\mu_t\) summing to one, and for each type a rational polytope \(B_t\) of feasible coefficients for a normalized utility \(u_t(x)=\sum_{j=1}^{q} b_{tj}I_j(x)\) in a shared I-spline basis. The actual coefficients are unknown. The cohort’s welfare criterion is utilitarian average expected utility,
\[ W(\pi)=\sum_t \mu_t\sum_x p_\pi(x)u_t(x), \]
where \(p_\pi(x)\) is the probability that policy \(\pi\) yields outcome \(x\). Queries go to a society-level welfare oracle: it compares the expected average utility of two lotteries. The task is to adaptively make such queries and output one common policy \(\pi\) whose regret is at most \(\delta\) for every population utility profile consistent with the initial polytopes and the answers received. Measure time and queries in \(n_T,\tau,q,L\), and \(1/\delta\), where \(L\) covers the rational input encoding.

I expect this mirror to be tractable. With a shared basis, the average utility \(\bar u_\mu=\sum_t\mu_tu_t\) is itself a normalized vNM utility in that basis. The feasible aggregate coefficient set is a polytope, representable using the type-level variables and constraints. So the mirror retains the paper’s underlying question: adaptively elicit the utility relevant to a sequential policy choice, then use backward induction to find a near-optimal policy. Proposition 11’s approach should apply to that aggregate utility, with the aggregate polytope adding polynomial dependence on \(\tau,q,L\). The paper’s stated bound is polynomial in \(1/\delta\), which is a precision dependence, not a claim polynomial in the bit length of \(\delta\) alone.

The weakest point is the utilitarian aggregation and its query oracle. Average cardinal utility assumes comparable normalization across types, and asking the society-level oracle to compare lotteries requires an institution or welfare model that can report those comparisons. That is a substantive modeling choice beyond the paper’s single decision maker. I still think authors would recognize the resulting problem: the tree, policy choices, expected-utility criterion, regret guarantee, and elicitation method remain intact; the decision maker’s utility is the cohort’s average utility.

This mirror covers Proposition 11 only. It raises further questions about whether the result survives with type-specific query access rather than a welfare oracle, how query effort should be allocated when types have unequal masses, and what happens when types face different transition probabilities or treatment trees.