| paper | d4-conf-aaai-2014-0396 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions; polynomial-time solvable iff \(\mathrm{P}=\mathrm{NP}\); \(\mathrm{NP}\)-hard under polynomial-time Turing reductions, and under polynomial-time many-one reductions iff \(\mathrm{NP}=\mathrm{coNP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given an issue set \(I\), a finite-support distribution \(\mu\) over compact P-trees on \(I\), a proposed bundle \(M^\star \in CD(I)\), and a rational threshold \(q \in [0,1]\), decide whether \(\sum_{T:\,M^\star \in \operatorname{Opt}(T)} \mu_T \ge q\).
The society is a distribution \(\mu\) over complete preference types, each type a compact P-tree on the shared issue set \(I\). For the supplied bundle \(M^\star\), each type contributes its mass if \(M^\star\) is optimal under that P-tree; the objective is the resulting support mass, compared with \(q\).
Mass-OPTTEST measures support for a supplied bundle and does not select a shared outcome; the paper's stated interest in preference aggregation and voting makes this support query recognizable, so the objection limits its scope.
fatal: False
The mirrors cover the population versions of Theorems 5 and 6. They leave the representation results in Theorems 1–3, the dominance test in Theorem 4, and the paper's broader language comparisons untouched.
The strongest mirror is a high multiplicity population of people choosing bundles. The shared issue set \(I\) describes the available bundles \(CD(I)\); each person’s type is their complete compact P-tree over that same set. A type’s mass is the fraction of the population with exactly that tree. For example, a product platform might have millions of users choosing among bundles of features, while users select from a catalog of tens or hundreds of elicited preference-tree profiles. That makes \(N\) much larger than the support size \(\tau\) for a concrete reason: the platform assigns users to shared preference templates. It is a modeling assumption, but the type is exact, not a cluster of people with merely similar preferences.
The outcomes remain ordinary Boolean assignments. What becomes continuous is the society: the input is a finite-support distribution \(\mu\) over P-tree types, with binary-rational masses summing to one. The paper itself points toward this extension when it names preference aggregation for P-trees as future work. So the mirror adds a population question to the authors’ reasoning problems; it does not claim that the paper already studies populations.
My lead is Mass-OPTPROP\(_\infty\), mirroring Theorem 6. In the paper, OPTPROP asks, given a P-tree \(T\) and a Boolean property \(\alpha\), whether there exists an optimal outcome of \(T\) satisfying \(\alpha\). Theorem 6 states that OPTPROP is \(\Delta_2^P\)-complete. The authors prove this result here: they give a polynomial-time NP-oracle algorithm and a hardness reduction from a restricted maximum satisfying assignment problem, drawing on Krentel’s cited result. In the mirror, an instance is a common issue set \(I\), a Boolean property \(\alpha\), a distribution \(\mu\) over P-trees on \(I\), and a rational threshold \(q\in[0,1]\). Define
\[ E_\alpha(T)=1 \quad\text{iff}\quad \exists M\in CD(I): M\in\operatorname{Opt}(T)\ \text{and}\ M\models\alpha. \]
The question is whether
\[ \sum_{T:E_\alpha(T)=1}\mu_T\ge q. \]
A “yes” answer means at least a \(q\) fraction of the population has some top-ranked bundle satisfying the public property—for instance, a bundle meeting an accessibility requirement. The individual outcome remains the decision variable inside the optimality question; the population-level quantity being measured is the mass of people for whom such an optimal outcome exists. This is an exact threshold decision problem, with a yes/no answer as its solution.
I expect this mirror to be \(\Delta_2^P\)-complete under standard explicit encodings. For membership, test each of the \(\tau\) supported P-trees using the paper’s \(\Delta_2^P\) procedure, then sum the corresponding rational masses and compare with \(q\). For hardness, use one type of mass \(1\) and \(q=1\); the mirror question is then exactly the paper’s OPTPROP question. This is a direct embedding, so I expect hardness to transfer from the discrete preference problem, rather than disappear with population size. It also suggests questions about which restrictions on P-trees—such as formula classes or tree structure—make the population query tractable, and whether any useful approximation guarantees become available under those restrictions.
A second, separate mirror is Mass-OPTTEST\(_\infty\), anchored in Theorem 5. OPTTEST is defined in the paper as deciding, given a P-tree \(T\) and an outcome \(M\), whether \(M\) is optimal. Theorem 5 states that OPTTEST is coNP-complete. The paper proves this here: membership follows because a better outcome is a polynomial-size witness for non-optimality, and hardness is by a reduction from SAT, whose details are omitted in the proof sketch. In the population version, the instance includes a shared proposed bundle \(M^\star\), the type distribution \(\mu\), and \(q\). Ask whether at least \(q\) mass regards \(M^\star\) as optimal:
\[ \sum_{T:M^\star\in\operatorname{Opt}(T)}\mu_T\ge q. \]
This is a top-choice share query: the “yes” answer says the proposed bundle belongs to enough users’ optimal sets. It is coNP-hard already with one type of mass \(1\). With variable support, testing each type and adding its mass gives a \(P^{NP}\) upper bound; I would leave the exact complexity of that weighted multi-type query open pending a tighter analysis. Further questions include whether aggregation over multiple types raises its complexity above the single-type bound, and which restrictions on the input trees allow efficient exact top-choice shares.
The weakest point in this case is also its boundary: the paper proves reasoning results for one P-tree at a time, and these mirrors aggregate those predicates over a population. The hardness is driven by the issue vocabulary and Boolean formulas, not by population multiplicity; a one-type society already carries it. So these mirrors are credible as computational preference-aggregation questions, but they do not show that continuization makes the paper’s hard problems easier or reveal a new optimization method. Their positive case rests on a genuine population distribution over complete preference types, and on aggregation being an explicit direction the authors themselves identify.
The strongest negative case is a scope objection. These are real computational results: Theorems 5 and 6 study coNP-complete OPTTEST and \(\Delta_2^P\)-complete OPTPROP. And a population of people choosing from a shared catalog, with many people using the same preference-tree template, is a plausible high-multiplicity regime. I would not reject the mirror on the grounds that preference types cannot repeat or that the paper has no computational results.
The proposed Mass-OPTPROP query measures a marginal property: for each person, *some* optimal bundle satisfies \(\alpha\). The witness can differ across types. For instance, two equally large groups could have disjoint top bundles, both satisfying \(\alpha\); the query reports that everyone has an acceptable optimum even though no bundle is optimal for both groups. That makes it a prevalence statistic rather than a collective choice problem.
Mass-OPTTEST has a closer social-choice interpretation: it measures support for a proposed bundle among people whose top sets contain it. But it takes the bundle as input and only reports its support. The paper’s result is about reasoning for one preference tree; adding masses aggregates the answers across the listed trees. Neither anchor, as stated, asks how a society should choose a shared outcome.
The best repair is to ask for a bundle that maximizes the mass of types for which it is optimal, perhaps subject to \(\alpha\). That gives a genuine collective decision problem. It also adds an aggregation rule—approval by membership in an agent’s top set—that the theorems themselves do not specify. The paper does point toward preference aggregation and voting rules as future work, though, so this repair is hard to dismiss as outside the authors’ interests.
That is where the negative case runs out of force. I can argue that the two stated mirrors are thin population queries and that a stronger one requires a new collective-choice formulation. I cannot credibly establish that the stronger formulation is uninteresting in every plausible regime. The paper’s own future-work direction makes a common-outcome, mass-weighted aggregation problem a plausible continuous mirror.
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.