| paper | CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements |
| authors | Craig Boutilier, R. Brafman, C. Domshlak, H. Hoos, D. Poole |
| venue | JAIR 2004 |
| filed under | unclassified |
| judged by | gpt-5.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: NP-hard; indeed NP-complete under explicit binary encoding of the society and rational data. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 15
statement extracted from the paper’s text layer
Given a rational finite-support society \{(N_t,\mu_t)\}_{t=1}^{\tau} of binary-valued, directed-path singly connected CP-net types, two outcomes o,o'\in\{0,1\}^n, and a rational quota \theta\in[0,1], decide whether \sum_{t=1}^{\tau}\mu_t\mathbf{1}[N_t\models o\succ o']\ge\theta.
A society is a finite distribution \mu over complete CP-net types; outcomes remain discrete; the decision is whether the mass of types entailing o\succ o' reaches \theta, with catalogue selection as an optional downstream objective.
The quota rule is externally chosen rather than supplied by CP-net semantics, so the mirror depends on whether collective product choice by entailment support counts as the authors' problem; the proponent gives a credible setting but does not make this aggregation canonical.
fatal: False
The mirror covers dominance testing in the directed-path singly connected and polytree classes, including Theorems 15 and 14. It leaves outcome optimization, ordering queries, other flipping-sequence results, cyclic-network consistency, and the paper's representational and semantic theorems untouched.
The strongest mirror I see is a continuous-population version of CP-net dominance for collective product or configuration choice.
Fix \(n\) discrete binary attributes, so every alternative remains a discrete outcome \(o\in\{0,1\}^n\). A type is a complete CP-net \(N_t\): its graph, every CPT, and any other preference information used by the query. Two users have the same type exactly when they induce the same CP-net dominance relation. The society is a distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\) over a finite library of such types, where \(\mu_t\) is the fraction of users of type \(t\). The intended regime is a large product or configuration service with millions of users but perhaps tens or hundreds of recurring preference templates: departments, customer roles, medical specialties, or other cohorts with identical qualitative preferences. The outcomes themselves are not continuized; only the population is.
For two configurations \(o,o'\), define the population’s dominance support by
\[ D_\mu(o,o')=\sum_{t=1}^{\tau}\mu_t\mathbf{1}[N_t\models o\succ o']. \]
A type that cannot entail either comparison contributes neither for nor against. This preserves the paper’s qualitative, partial-preference semantics rather than inventing utilities.
The continuous problem I would hand to a prover is:
\(\mathrm{Quota\text{-}CP\text{-}Dominance}_\infty(\mathcal G)\). An instance consists of an explicit finite-support society \(\{(N_t,\mu_t)\}_{t=1}^{\tau}\), two discrete outcomes \(o,o'\in\{0,1\}^n\), and a rational quota \(\theta\in[0,1]\). The decision variable is whether to certify \(o\) as a \(\theta\)-dominant replacement for \(o'\). The answer is YES exactly when \(D_\mu(o,o')\ge\theta\). In an actual collective-choice system, this comparison can be used to select, from an explicit catalogue, the outcome maximizing \(D_\mu(o,o_0)\) against a status quo \(o_0\); the fixed-pair quota problem is the clean computational core.
My lead anchor is Theorem 15: “Dominance testing for binary-valued, directed-path singly connected CP-nets is NP-complete.” This theorem is proved in the paper, with the hardness proof in Appendix A. Here “directed-path singly connected” means that there is at most one directed path between any pair of variables. The result concerns a binary-valued CP-net \(N\) and two outcomes \(o,o'\), and asks whether \(N\models o\succ o'\). Under the paper’s bounded-indegree input convention, membership in \(\mathrm{NP}\) follows because a successful improving flipping sequence has polynomial length, at most \(n^2\); \(\mathrm{NP}\)-hardness is obtained by reduction from \(3\)-SAT.
The corresponding continuous problem is \(\mathrm{Quota\text{-}CP\text{-}Dominance}_\infty(\mathrm{DPS})\), where every type \(N_t\) is binary-valued and directed-path singly connected. This is not a softened version of dominance. It asks the same dominance question for every cohort and aggregates only the resulting qualitative entailments. Its high-multiplicity interpretation is direct: a very large population consists of repeated copies of finitely many CP-net types.
The discrete theorem embeds immediately. Take \(\tau=1\), \(\mu_1=1\), and \(\theta=1\). Then the continuous question is YES exactly when \(N_1\models o\succ o'\). Thus the continuous problem is at least \(\mathrm{NP}\)-hard, even when the society consists of an arbitrarily large number of identical agents. I would therefore expect this mirror to be Class B: the hard combinatorics live in the CP-net’s dependency structure, not in population multiplicity. With explicit support, the polynomial-length flipping certificates also suggest an \(\mathrm{NP}\)-membership argument for the quota version, but the inherited \(\mathrm{NP}\)-hardness is the essential anchor.
This is a particularly good mirror because it preserves the paper’s central object exactly. We do not replace CP-net dominance with a cardinal score, average local preferences, or a fractional assignment. The only new operation is a standard collective-choice question: what fraction of the population can formally justify preferring one discrete alternative to another?
A second, useful anchor is Theorem 14: “Dominance testing for binary-valued, polytree CP-nets is in P.” This theorem is proved in the paper by reducing the query to planning with unary operators and a polytree causal graph, using an algorithm from Brafman and Domshlak (2003). A polytree has an acyclic underlying undirected graph; the result assumes binary variables and bounded maximum indegree \(\kappa\). With \(\kappa\) fixed, the cited running time is polynomial in the CP-net description.
The corresponding problem is \(\mathrm{Quota\text{-}CP\text{-}Dominance}_\infty(\mathrm{PT})\): the input is the same rational distribution over CP-net types, but every \(N_t\) is a binary-valued polytree with bounded indegree, together with \(o,o'\) and \(\theta\). The required output is again YES iff
\[ \sum_{t=1}^{\tau}\mu_t\mathbf{1}[N_t\models o\succ o']\ge\theta. \]
This version is Class A. Run the polynomial dominance algorithm of Theorem 14 independently on each explicitly represented type, then add the rational masses of the successful types and compare with \(\theta\). The total running time is polynomial in the total CP-net input size and in \(\tau\). If the platform must choose from an explicitly listed catalogue of outcomes, it can evaluate every candidate pair in polynomial time as well.
The two anchors together give a meaningful continuous complexity boundary. Directed-path singly connected types retain the paper’s \(\mathrm{NP}\)-complete core; polytree types admit exact population-level aggregation because each individual dominance query is tractable. The continuous formulation therefore does not promise that every CP-net problem becomes easy. It exposes which part of the difficulty survives high multiplicity and which structural restrictions remain algorithmically usable at population scale.
The main further questions would be whether one can preprocess a fixed type distribution to answer many quota-dominance queries, whether implicit feasibility constraints on outcomes introduce a new source of hardness, and how to define continuous manipulation problems in which a minimum mass of users or types must be changed to make a target configuration meet a quota.
The weakest point is that the paper studies one decision maker’s CP-net, not a distribution of CP-nets or a quota-based collective rule. The population aggregation is therefore an added social-choice layer. A strict referee could call this a batch extension rather than the paper’s original problem. I think the case nevertheless survives: the paper explicitly motivates CP-nets by product selection, configuration, and database sorting, all of which naturally admit large cohorts of users with repeated preference templates. More importantly, the inner predicate is exactly the paper’s dominance predicate, and the one-type, unit-mass restriction recovers Theorem 15 verbatim. I would not claim that this paper already contains a continuous-population model; rather, it supplies a sharply defined per-type computational primitive whose high-multiplicity collective version is natural to ask.
The strongest negative case is that the proposed mirrors do not actually continuize a problem from this paper. They take a single-agent query and place its answer inside an externally chosen voting rule.
Every named computational result in the paper is a predicate on one CP-net \(N\) and one or more outcomes. For example, Theorem 15 asks whether \(N\models o\succ o'\). If \(N\) is copied to a million identical users, the answer does not change. Thus the proponent’s \(\tau=1\) reduction establishes only that a newly defined collective problem contains the original problem. It does not show that population mass is part of the original computational object.
For \(\tau>1\), the proposed quantity
\[ \sum_t \mu_t\mathbf{1}[N_t\models o\succ o'] \]
introduces precisely the missing object: a social aggregation rule. But that rule is not supplied by CP-net semantics. The relation \(N_t\models o\succ o'\) means that the comparison follows from every total order compatible with one user’s qualitative statements. It is not a vote, utility, probability, or degree of preference. Treating non-entailment as abstention and then applying a quota is one possible convention, but it is an additional normative model.
The difficulty cannot be repaired without changing the target. Unanimous support preserves a qualitative interpretation but makes population mass largely irrelevant. Majority or quota support makes mass relevant but can produce an intransitive collective relation, so it is no longer CP-net dominance. Averaging local orders or probabilities over linear extensions introduces cardinal or probabilistic semantics that the paper deliberately avoids. Allocating different outcomes to different users would require a new welfare, feasibility, or matching model. Each is potentially interesting, but none is a continuization of the paper’s dominance query.
This defeats the claimed significance of Theorem 15. Theorem 15 can certainly serve as an oracle inside a collective product-selection problem, but the collective problem’s substantive difficulty lies in the added aggregation rule, not in the population representation. A more ambitious version could ask for the minimum mass of users whose CP-nets must be changed before \(o\) reaches a quota. That would make mass genuinely operational, but the paper provides neither interventions on CP-nets nor prices or costs for changing a user’s qualitative preference network. Supplying them would create a campaigning or manipulation problem absent from the paper, with CP-net dominance merely used as a subroutine.
Theorem 14 is weaker still as a mirror. The proposed algorithm simply solves each polytree dominance query independently and adds the masses of the successful types. This is a weighted batch evaluation of the paper’s polynomial-time test. The polytree-versus-directed-path boundary already exists within a single CP-net; the distribution adds no coupled constraint, optimization variable, or new semantic structure. Calling this a population-level Class A result therefore overstates what the continuous formulation contributes.
There is a genuinely plausible high-multiplicity story here: a large product service may have many recurring CP-net templates. That is evidence that repeated CP-net types are sensible, not an objection to them. But it also exposes the limit of the negative case. If the programme accepts a new quota-based collective rule as enough, then the proponent has a legitimate Class B mirror of Theorem 15. I can therefore defeat the two stated formulations as thin wrappers around single-agent queries, but I cannot honestly establish the universal claim that no worthwhile continuous-population version exists. The negative case is ultimately weak because repeated preference templates and collective product choice are both credible regimes.
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.