| paper | d4-conf-ecai-2025-0357 |
| 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}\text{-hard}\) · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite menu \(A\subseteq\mathbb{Q}^p\), a rational polytope \(W\subseteq\mathbb{R}^p\), and a distribution \(\mu\) over the distinct weak-order types \(T\) induced by \(W\), choose a batch \(\Gamma\) of symmetric pairwise-comparison queries and a decoder. Every answer pattern consistent with a type \(t\in T\) must decode to an alternative optimal for \(t\); minimize the per-capita query load \(\sum_{q\in\Gamma}\sum_{t\in T}\mu_t=|\Gamma|\).
A nonatomic cohort has type distribution \(\mu\) over complete weak orders induced by the shared linear preference family \((A,W)\). Every agent receives the same comparison batch and gets an individual optimal alternative from their answers; query load is aggregated over mass.
The mirror covers Theorem 4's fixed-batch characterization for linear preference families. It leaves the paper's general query bounds, approval and lexicographic examples, adaptive query trees, and the computation time for constructing the adjacency structure outside the anchor.
The strongest case I see is a narrow one: population-scale batch preference elicitation. The paper contains no named NP-hardness or standard running-time classification result. Its computational resource is the number of queries, and its best anchor is an exact result about that resource.
Lead anchor: Theorem 4, proved in this paper (with the full proof in the longer version cited as [35]). For a linear preference family \(P\), form \(\Gamma(\mathrm{Adj})\) from symmetric comparison queries between pairs of adjacent alternatives in \(\mathrm{PSOP}\), the set of possibly strictly optimal alternatives. Theorem 4 says this is a questionnaire made entirely of simple necessary queries; after removing queries equivalent for \(P\), its size is exactly \(\mathrm{MQS}(P;\mathrm{CompSym}_A)\), the minimum number of symmetric comparison queries in any batch that guarantees an optimal alternative. That is an exact query-complexity result, though not a claim that the problem is in P.
A credible setting is a large service that gives people personalized recommendations from a fixed menu of alternatives—for example, millions of residents choosing among service plans. Each person has a linear preference order over the menu, drawn from the same known family of admissible utility weights. People with the same order are one type; their mass is their fraction of the population. The number of people can be far larger than the number \(\tau\) of distinct preference types.
Here is the continuous problem I would hand to a prover: Linear Cohort Batch Elicitation. An instance consists of a finite set \(A\subseteq\mathbb{Q}^p\), a rational polytope \(W\subseteq\mathbb{R}^p\), and rational masses \(\mu_t>0\) summing to \(1\), one for each distinct weak order \(t\) on \(A\) induced by some \(w\in W\), where \(a\succeq_w b\) exactly when \(w\cdot a\ge w\cdot b\). Choose a set \(\Gamma\) of symmetric pairwise comparison queries and a decoder assigning an alternative to each consistent answer pattern. Every person receives the same batch; their own answers determine their recommendation. A solution is valid if every possible answer pattern for every positive-mass type leads to an alternative optimal for that type. Minimize the total query mass asked: each query goes to the whole normalized society, so the cost is \(\sum_{q\in\Gamma}\sum_t\mu_t=|\Gamma|\).
This mirrors Theorem 4’s batch problem directly: the family of possible preference orders is the paper’s linear \(P\), and a successful questionnaire gives each person an optimal alternative from their answers. I expect a Class A outcome for this full linear-family version: the theorem reduces the optimum to the adjacency structure of \(\mathrm{PSOP}\), and the paper’s discussion says polynomial-time computation in \(|A|\) appears to follow. That running-time bound is not proved in the theorem, so efficiently constructing that structure from the polytope remains a question for the mirror.
The scope is the linear-family, fixed-batch result. Further questions include whether the exact characterization survives when society has only a proper subset of the preference types allowed by \(W\), and what happens if the objective is adaptive query mass, \(\sum_\sigma \mu(\text{types reaching }\sigma)\), across a query tree.
My weakest point is that the population mostly scales the paper’s single-person task: the answer is independent of the precise masses as long as every listed type has positive mass, and the output is personalized recommendations rather than one collective winner. So this case does not test whether discrete hardness dissolves in a continuum. It rests on the narrower claim that a shared questionnaire deployed across a high-multiplicity population is a sensible population mirror of the paper’s own problem.
Theorem 4 is a genuine result about minimum questionnaire size, so I would not argue that the paper has no formal result to mirror. The problem is that the proposed cohort version leaves the population outside the optimization. The theorem characterizes \(\mathrm{MQS}(P;\mathrm{CompSym}_A)\) for one decision maker’s unknown preference model.
In Linear Cohort Batch Elicitation, every positive-mass type must receive an optimal recommendation. That is the original guarantee applied to every possible model in \(P\). Since every query goes to everyone, the proposed normalized query cost is
\[
\sum_{q\in\Gamma}\sum_t\mu_t=|\Gamma|.
\]
Changing the masses while keeping the support fixed changes neither the guarantee nor the cost. That alone would be a dull answer, which is not a reason to reject the question. The more basic issue is that this formulation asks the same independent elicitation problem repeatedly; its output is a recommendation for each respondent, with no society-level outcome or constraint connecting them. If type membership and rankings are known, recommendations are already determined. If rankings are hidden from the system, \(\mu\) acts as a distribution over an individual’s possible model.
The strongest repair is an adaptive protocol that asks questions only of the unresolved answer groups and minimizes total query mass, for example
\[
\sum_{\sigma}\mu(\{t:\text{type }t\text{ reaches }\sigma\}).
\]
That is a coherent weighted decision-tree problem and gives population composition a real role. But it changes the paper’s worst-case query objective to expected aggregate workload; the distribution can then be read as a prior for one random respondent. I would argue that this is a weak fit for ChoCo’s continuous-society programme, while recognizing that a programme willing to study society-wide elicitation workload could reasonably find it worthwhile.
So the negative case is strongest against the proposed Theorem 4 mirror: its “population” supplies no population-level computational task. I cannot honestly defend the universal claim that no worthwhile mirror exists in any scenario. The adaptive, mass-weighted version is a plausible survivor, and that is where my case is weakest.
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.