| paper | d4-conf-atal-2021-0146 |
| 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{NP}\text{-hard}\), already for \(\tau=1\) and \(\mu_1=1\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 12
statement extracted from the paper’s text layer
Given a finite alternative space \(X\), two alternatives \(o,o'\), and an explicit support of \(\tau\) fully acyclic CP-nets \(\phi_t\) with binary-rational masses \(\mu_t\ge 0\) summing to one, compute the exact population masses for which \(o\) is strictly preferred to \(o'\), \(o'\) is strictly preferred to \(o\), they are indifferent, or they are incomparable.
The society is a distribution \(\mu\) over complete preference types \(\phi_t\), each a fully acyclic CP-net over the same alternatives. For each comparison relation \(R\), the output is the exact mass \(p_R=\sum_t \mu_t\,\mathbf{1}[o\,R_{\phi_t}\,o']\).
The comparison masses can be computed as a weighted batch of per-type queries, so the population adds no interaction; the proponent acknowledges this extension but does not show that the authors would see it as more than a population statistic.
fatal: False
The mirror covers Proposition 12’s pairwise comparison results; it leaves the paper’s equivalence, optimization, compilation, expressiveness, and succinctness results alone.
The strongest case I can defend is a population lift of the paper’s comparison query. It is a natural extension of the authors’ problem, though not one the paper itself studies.
Call it Continuous Pairwise CP Comparison. All agents share a finite alternative space \(X\), such as travel plans described by destination, timing, and transport attributes. A type \(t\) is a complete conditional preference specification, given as a fully acyclic CP-net \(\phi_t\); agents of that type share its preference tables and induced preorder. The society is a distribution \(\mu\) over the \(\tau\) represented types, with rational masses \(\mu_t\) summing to one.
Given two alternatives \(o,o'\), the task is to return the exact masses of agents for whom \(o\) is strictly preferred to \(o'\), incomparable with \(o'\), indifferent to \(o'\), or strictly worse than \(o'\). For example,
\[
p_{\succ}=\sum_t \mu_t\,\mathbf{1}[o\succ_{\phi_t}o'].
\]
The other three masses are defined analogously. These exact proportions give a population-level comparison; for instance, they tell us whether a strict majority prefers one plan. A plausible regime is a large configurator or recommendation service with millions of users clustered into hundreds or thousands of recurring conditional-preference types.
The anchor is Proposition 12. It states that strict-preference comparison and incomparability comparison are NP-hard for fully acyclic CP-nets, and tractable for polytree CP-nets; indifference comparison is easy for 1-CP formulas that are 1-lexico-compatible. The paper presents this as its own proposition, with proofs deferred to the authors’ report [20]. The polytree tractability builds on the earlier result for weak comparison in [4, Theorem 14].
This mirror preserves the anchor’s central operation: for each type, determine how two alternatives compare under the conditional preference relation. It adds population mass to those answers without weakening the CP-net semantics. The hardness carries over directly: set \(\mu_t=1\) for one fully acyclic type. Then the output reveals the answer to the NP-hard comparison query. So I expect the unrestricted problem to be hard by hardness transfer; when all types are polytrees, the population masses can be computed by answering each type’s query and summing the rational weights. The mirror therefore gives a useful population question, but this anchor does not suggest that continuization dissolves the hardness.
The least secure step is moving from one decision maker in the paper to many people whose preferences are aggregated. The authors would recognize the individual comparison being computed, and the population extension keeps that computation intact. They may still regard population-level comparison rates as a new aggregation problem rather than their original query. That is the weakness of this positive case. It covers Proposition 12’s comparison results only; it does not claim a population mirror for the paper’s equivalence, optimization, or compilation questions. The mirror also raises further questions: whether majority comparisons across alternatives can cycle, and whether restrictions on the type support—such as the number of non-polytree types—yield useful parameterized algorithms.
The strongest objection to the Proposition 12 mirror is that the continuous task changes what is being asked. Proposition 12 compares two alternatives in one encoded preference preorder. The proposed population query asks for the weighted prevalence of each comparison outcome across many such preorders. With explicit support \(\{(\phi_t,\mu_t)\}_{t=1}^{\tau}\), it runs the paper’s comparison query once per type and sums the weights:
\[
p_R=\sum_{t=1}^{\tau}\mu_t\,\mathbf{1}[o\,R_{\phi_t}\,o'].
\]
The masses never interact. The computation is entirely in each type’s CP-net; the population contributes a weighted batch of queries.
That makes the exact-share version look more like a population statistic built from the paper’s oracle than a new continuous computation. A large recommendation service is plausible, but it motivates measuring how users compare two plans, rather than the paper’s task of answering how one decision maker compares them. A stronger version—use those shares to build a majority relation or choose a social winner—has a real collective-decision purpose. But it adds an aggregation problem: Proposition 12 supplies a subroutine, while the new question concerns the resulting social choice. The paper’s references to voting on multi-issue domains and preference aggregation over CP-nets make this direction credible, but also underline that it is a different layer of the problem.
This objection does not defeat the anchor. The authors might reasonably recognize population comparison rates, or a majority relation over plans, as a natural extension of their work. The type definition is sound: users with the same conditional preference model are indistinguishable for this query, and the recommender scenario can plausibly have many such users. The fact that one type of mass \(1\) transfers the hardness, or that polytrees allow summing tractable per-type answers, describes the resulting complexity; it is not a reason the question is unworthy.
So the negative case is weak where it matters most. It can argue that this is a low-coupling population lift whose computational content stays inside each type, and that the more consequential collective versions add a distinct aggregation task. It cannot honestly rule out the continuous mirror: the exact population share is well-defined, useful in a plausible setting, and close enough to the paper’s comparison query that the authors may recognize it.
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.