| paper | d4-conf-atal-2011-0233 |
| 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}\), even for \(\tau=1\) and \(d=2\); no polynomial-time algorithm in \(m,\tau,d,L\) exists unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite support of acyclic CP-net types \(t\), each with a complete conditional preference model and rational mass \(\mu_t>0\) satisfying \(\sum_t \mu_t=1\), and outcomes \(\alpha,\beta\), compute exactly \(p_{\alpha\succ\beta}=\sum_{t:\,N_t\models\alpha\succ\beta}\mu_t\).
Types are complete acyclic CP-net preference models; each carries population mass \(\mu_t\). Run the paper’s dominance decision procedure for \(\alpha\succ\beta\) on each supported type, then sum the masses of the types for which it holds. There is no optimization objective.
The paper does not establish that the mass of CP-net models entailing dominance is the group semantics its authors would choose; that exact-share query extends their individual reasoning task.
fatal: False
The mirror covers Theorem 2’s complete dominance search over acyclic CP-nets. It does not cover Theorem 1’s penalty property or the experimental comparisons as separate results.
The strongest honest case is a narrow collective lift of dominance testing. One qualification matters: this paper has no numbered theorem asserting a complexity class such as PSPACE-hardness or polynomial time. The closest usable algorithmic anchor is Theorem 2, proved here: DT* is complete for dominance testing on arbitrary acyclic CP-nets. It establishes that the search will not miss an improving-flip sequence; it gives no worst-case running-time bound. The paper’s introduction separately cites [5] for PSPACE-completeness, but that result is not numbered as a theorem in this paper, so I would not present it as a second anchor.
A plausible regime is a large product-configuration or recommendation platform with many recurring users but relatively few distinct conditional preference profiles. For example, users may share preferences over the same product attributes, while a complete type records one user segment’s CP-net structure and every conditional preference table. A population of hundreds of thousands of users might then have only dozens or hundreds of types. Mass means the fraction of users with each complete CP-net type.
I would call the mirror Population-Share CP-net Dominance. An instance consists of shared variables \(V\) and domains \(D(X)\), a finite support of acyclic CP-net types \(t\), rational masses \(\mu_t>0\) summing to \(1\), two outcomes \(\alpha,\beta\), and a rational threshold \(q\in(0,1]\). Define
\[
p_{\alpha\succ\beta}=\sum_{t:\,N_t\models\alpha\succ\beta}\mu_t.
\]
The question is whether \(p_{\alpha\succ\beta}\ge q\); a solution can report the exact rational value and the yes/no answer. There is no intervention variable or optimization objective: the computation is the population share supporting the paper’s original dominance relation. For a discrete population with \(n_t\) users of type \(t\), the corresponding masses are \(\mu_t=n_t/n\).
Theorem 2 is the single anchor for this mirror: its complete search procedure can be applied to each supported type, after which the resulting masses are summed. The direction I expect is hardness transfers. The paper reports that dominance testing for acyclic CP-nets is PSPACE-complete, citing [5]. A society with one type of mass \(1\) and \(q=1\) is exactly an instance of that individual dominance problem. Thus the population formulation retains the hard case; continuity does not remove the search over improving-flip sequences. Theorem 1’s penalty result supports the DT* search heuristic, but it is not a separate complexity anchor. This mirror does not make a new tractability claim for the heuristic.
The natural follow-up questions are whether the exact share can be computed efficiently for restricted CP-net structures, whether many types can share work when they have common structure, and how the complexity changes when the threshold or support size is restricted.
The weakest point is the population aggregation itself. CP-nets in this paper describe an individual’s conditional preferences, and the paper’s query concerns that model. Asking what fraction of a society’s distinct CP-net types endorses the same dominance claim is a sensible collective decision question, but it adds an aggregation layer that the authors do not study. The paper’s mention of collective decision-making applications makes the connection credible; it does not guarantee that the authors would regard this threshold query as their problem’s continuous analogue.
The case against rests on a mismatch between the paper’s result and the proposed population question. Theorem 2 proves that DT* is complete for an individual CP-net dominance query. It gives no complexity bound. Applying it to each type in a population preserves correctness, but that is a direct batch use of the individual algorithm, not a population-level result from the paper. The paper’s PSPACE-completeness statement is background cited from earlier work, not a complexity theorem proved here.
The strongest version of the proposed mirror would avoid an arbitrary threshold and ask for the exact mass of types whose CP-nets entail \(\alpha \succ \beta\):
\[
p_{\alpha\succ\beta}=\sum_{t:\,N_t\models\alpha\succ\beta}\mu_t.
\]
That is a coherent computation, and recurring preference profiles in a large platform are a plausible high-multiplicity regime. But its computation consists of testing dominance independently for each of the \(\tau\) supported types, then summing their rational masses. The theorem supplies the correctness of those individual tests; it does not supply a new population algorithm or a reason the tests interact. A one-type society recovers the original query exactly.
There is also a semantic gap. A CP-net’s failure to entail \(\alpha\succ\beta\) may mean the outcomes are incomparable under that model; it does not mean the person prefers neither or rejects the claim. So the proposed share measures the mass of models that *prove* dominance, not necessarily the share of people who prefer one outcome. A more conventional group question—whether every type entails the dominance, for example—avoids the threshold choice, but remains a collection of individual tests.
Those points weaken the claim that Theorem 2 itself motivates a continuous mirror: the mirror adds a social aggregation semantics that the paper does not define, and the theorem transfers to it mechanically. They do not establish that the resulting aggregation problem is uninteresting. The paper’s collective decision-making motivation and the possibility of repeated CP-net profiles make that a plausible question in its own right. So the negative case is strongest on the gap between the paper’s individual result and the proposed group problem, and weakest on the broader claim that no worthwhile continuous mirror exists.
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.