| paper | d4-conf-ijcai-2005-0056 |
| 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: Deciding whether \(Q^*\le B\) is \(\mathrm{NP}\)-hard, even for \(B=1\), \(\tau=1\), and \(n=4\). The permitted adaptive strategies can improve the optimized independent HLG baseline by an unbounded factor: a family with \(L=\Theta(k)\) has \(Q^*=2\) and optimized baseline count \(2k\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Proposition 2
Given a finite support \(T\) with rational masses \(\mu_t\), and for each type \(t\) a feasible set \(F_t\) and uncertain GAI utility set \(U_t\), where members of that type share the same latent utility, determine the worst-case number of adaptive threshold queries needed to return recommendations \(x_t\in F_t\) such that \(\max_{(u_t)\in\prod_{t\in T}U_t}\sum_{t\in T}\mu_t[\max_{y\in F_t}u_t(y)-u_t(x_t)]\le\epsilon\). In particular, can query allocation using the masses improve on running HLG independently with per-type tolerances \(\epsilon_t\) satisfying \(\sum_t\mu_t\epsilon_t\le\epsilon\)?
A distribution over complete configuration-preference types, each with mass \(\mu_t\), shared constraints and uncertain GAI parameters; threshold queries update a type’s bounds, and the system chooses one configuration per type to minimize worst-case mass-weighted regret.
The weighted sum of regret across distinct types requires a common utility scale or other interpersonal calibration, which the paper does not provide.
fatal: False
The mirror covers Proposition 2’s HLG query guarantee, extended across types; it does not cover the empirical CS or OP strategies or their performance.
The strongest mirror I believe in is Population HLG Regret Elicitation. It extends the paper’s query guarantee to a large population whose members fall into a small number of genuinely shared preference types.
My anchor is Proposition 2, proved in this paper. In the paper’s notation, for an uncertain utility model with \(n\) parameters and \(m=\operatorname{maxspan}(U)\), the halve-largest-gap strategy guarantees minimax regret at most \(\epsilon\) after \(n\log(m/\epsilon)\) queries. This is a query-count guarantee, not a polynomial-time result. Proposition 1 supplies the span bound used in that argument; I treat it as support for this anchor, not as a separate mirror. The paper gives no named P, NP-hardness, or parameterized-complexity result.
Here is the population problem. There is a finite support \(T\) of \(\tau\) types, with rational masses \(\mu_t>0\) summing to one. A type is a cohort whose members share the same configuration constraints and the same underlying GAI utility parameters. Those parameters are unknown to the system but have known initial bounds. For type \(t\), let \(F_t\) be its feasible configurations and \(U_t\) its current set of possible utilities. The system may ask a threshold bound query about a utility parameter for that type; because the cohort shares its true parameters, one response updates the bounds for the whole cohort.
The system must return a feasible configuration \(x_t\in F_t\) for each type. Its quality is the society’s worst-case average regret,
\[
\max_{(u_t)\in\prod_{t\in T}U_t}
\sum_{t\in T}\mu_t
\left[\max_{y\in F_t}u_t(y)-u_t(x_t)\right].
\]
Given a tolerance \(\epsilon>0\), the task is to design an adaptive bound-query policy that returns these recommendations with this quantity at most \(\epsilon\), using as few queries as possible in the worst case. This is the continuous mirror: masses represent population shares, queries and recommendations operate at type level, and the objective is per-capita regret.
A plausible regime is a large procurement or configuration platform serving many organizational units governed by a small set of centrally specified preference and constraint templates. For example, \(10^5\) or more deployments might share only \(10^2\) distinct templates. The numbers are illustrative; the important feature is that the population greatly exceeds the number of complete types, so one representative response can speak for a whole cohort. That makes the mirror plausible as a repeated deployment of the paper’s decision-support problem, though it is an extension from one user to a population.
The paper’s guarantee composes across types. Let \(n_t\) be the number of utility parameters for type \(t\), and \(M_t\) its initial maxspan. Choose per-type tolerances \(\epsilon_t\) with \(\sum_t\mu_t\epsilon_t\le\epsilon\), and run HLG on each type. Proposition 2 then gives a query bound of order
\[
\sum_{t:M_t>\epsilon_t} n_t\log(M_t/\epsilon_t),
\]
after which the weighted worst-case regret is at most \(\epsilon\). This bound depends on the support and model sizes, not on the number of people in the population. Choosing the \(\epsilon_t\) to exploit very small cohort masses is a further optimization question.
I expect this mirror to be tractable in query count: the paper’s named result supplies the guarantee, and the population extension is a direct composition over types. It does not establish tractability in running time. Computing the recommendations still requires the CBO or minimax-regret optimization used by the paper, for which Proposition 2 gives no polynomial-time bound. The mirror covers the HLG query guarantee; it does not claim results for the paper’s empirical CS or OP strategies.
The weak point is the exact shared-type assumption. If people in a cohort disagree about a bound-query answer, one response no longer updates the whole mass, and the support may need to split into more types. The paper’s authors might also regard the population version as a deployment setting around their single-user problem rather than a new core problem. I think the mirror survives that objection for repeated, centrally governed configuration tasks, but I would not extend it to a general consumer population without a credible account of how those shared types arise.
Proposition 2 is a genuine anchor: it gives a worst-case bound on the number of queries needed to reduce one user’s minimax regret. I would not dismiss it as having no computational content. The trouble is that the proposed population lift does not turn that one-user problem into a meaningful population problem.
In the proposed lift, a type’s members share the same unknown utility, and the system gives each member a configuration. If those preferences really are shared, the cohort consists of repeated copies: its mass scales total regret and population size together, leaving per-capita regret unchanged. One representative’s answer can update the whole cohort only because all its members are assumed to have the same latent utility. If they instead have distinct utilities, sharing constraints and initial bounds does not imply they will give the same answer. Each needs to be elicited separately, or the cohort must split into more complete types. The claimed small-support advantage therefore depends on a strong common-preference assumption.
That assumption is especially consequential here because the paper’s unknown preference is the object elicitation is meant to discover. The system is not given a society of observed preference types; it interacts with a user whose utility is unknown. In a population setting, knowing that a cohort shares its *latent* utility is an additional input or institutional guarantee, not something supplied by the paper’s model. If a central authority already specifies one utility profile for many deployments, one can ask its representative once, but that begins to look like one principal’s preference being reused across multiple decisions, rather than a society whose preferences must be elicited.
A stronger mirror would choose one configuration for a whole population. That is a real collective decision, but it needs a social objective the paper does not provide. Aggregating utilities requires interpersonal scales and weights; aggregating each person’s regret instead makes a different normative choice. The paper’s bound queries and regret guarantee apply once an individual utility model and decision objective are fixed. They do not determine which population objective is appropriate. Supplying one would create a new social-elicitation problem, rather than reveal a population version already latent in the paper.
So the best negative case is that Proposition 2’s population extension either repeats a single-user elicitation problem across cohorts or relies on adding a social objective absent from the paper. But that is not an airtight case against every scenario. Centrally governed organizations could plausibly share a complete preference model, and a group configuration problem with an agreed aggregation rule is mathematically coherent. Since query complexity is itself a computational guarantee, I cannot honestly claim the anchor is defeated universally; the negative case is weakest precisely where the shared-preference and shared-decision assumptions are institutionally credible.
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.