| paper | The Computational Complexity of Dominance and Consistency in CP-Nets |
| authors | J. Goldsmith, J. Lang, M. Truszczynski, N. Wilson |
| venue | JAIR 2008 |
| filed under | frontier · tools-data |
| 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: \(\mathrm{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite library of complete CP-net types \(C_1,\ldots,C_\tau\) over \(V\), rational masses \(\mu_t\) summing to \(1\), integral outcomes \(\alpha,\beta\in\{0,1\}^{|V|}\), and a quota \(q\), decide whether there exists one finite sequence \(\pi\) of one-variable flips from \(\alpha\) to \(\beta\) such that \(\sum_{t=1}^{\tau}\mu_t\mathbf{1}[\pi\text{ is an improving sequence in }C_t]\ge q\).
Types are complete CP-net descriptions \(C_t\) with masses \(\mu_t\); the decision variable is one common integral flip sequence \(\pi\), and the objective is to maximize \(\sum_t\mu_t\mathbf{1}[\pi\text{ is improving in }C_t]\) or test whether it reaches \(q\).
The proponent never supplied an application requiring all supported types to follow one identical flip sequence, so the shared-plan repair adds a coordination objective absent from the original paper.
fatal: False
The mirror covers CP-DOMINANCE from Theorem 2 and offers an analogous shared-cycle continuation of CP-CONSISTENCY from Theorem 4; it leaves the other dominance, equivalence, incomparability, optimality, and planning results untouched.
The strongest positive case is a high-multiplicity collective version of CP-net dominance. The paper’s CP-nets represent individual preference types over discrete configurations, so the population can be continuized without making configurations themselves fractional.
My lead problem is \(\textsc{Quota-CP-Dominance}_{\infty}\). Let \(V=\{x_1,\ldots,x_n\}\), let \(\Omega=\{0,1\}^n\) be the integral configurations, and let \(T=\{1,\ldots,\tau\}\) be a finite library of CP-net types. Type \(t\) consists of a CP-net \(C_t\); \(\mu_t\) is the fraction of the population with that complete preference description, with \(\sum_t\mu_t=1\). A large configuration population may have millions of users but only a few dozen recurring CP-net templates, so \(\tau\ll N\) is a credible regime.
Given a current configuration \(\alpha\), a proposed configuration \(\beta\), and a rational quota \(q\), define
\[ d_t(\alpha,\beta)= \begin{cases} 1 & \text{if $\beta$ dominates $\alpha$ in $C_t$},\\ 0 & \text{otherwise.} \end{cases} \]
Equivalently, \(d_t(\alpha,\beta)=1\) when there is an improving sequence of integral one-variable flips from \(\alpha\) to \(\beta\). The population support for the proposed change is
\[ D_\mu(\alpha,\beta)=\sum_{t=1}^{\tau}\mu_t d_t(\alpha,\beta). \]
The problem asks whether \(D_\mu(\alpha,\beta)\ge q\). Operationally, the decision is whether to implement \(\beta\). A mass-flow formulation makes the action variable explicit: let \(x_{t,p}\) be the mass of type \(t\) assigned to an improving path \(p\) from \(\alpha\) to \(\beta\), and maximize
\[ \sum_{t}\sum_{p}x_{t,p} \]
subject to \(\sum_p x_{t,p}\le\mu_t\). The atomless population permits type mass to split across paths, but every individual still occupies an integral configuration.
This is a genuine population problem rather than merely duplicating one CP-net: the output is the fraction of a heterogeneous society that supports a proposed configuration under the paper’s own dominance semantics. It is also recognizably connected to the paper’s motivation in design, planning, and group decision making. A finite electorate with \(n_t\) agents of type \(t\) gives the same instance after setting \(\mu_t=n_t/N\), and rational masses can be expanded back into such a finite electorate.
The anchor is Theorem 2, proved in this paper:
“CP-DOMINANCE is PSPACE-complete. This holds even if we restrict the CP-nets to being consistent.”
That theorem concerns the problem of deciding, given a CP-net \(C\) and two outcomes \(\alpha,\beta\), whether \(\beta\) dominates \(\alpha\), meaning that an improving flipping sequence exists. The continuous problem inherits PSPACE-hardness immediately from the one-type instance \(\tau=1\), \(\mu_1=1\), and \(q=1\). Membership remains in PSPACE by testing the explicitly listed types one at a time and adding their rational masses. Thus \(\textsc{Quota-CP-Dominance}_{\infty}\) is expected to be PSPACE-complete.
I would classify this as Class B. The hardness is carried by the exponentially large configuration space and the planning-like dependency structure inside a CP-net, not by the number of named agents. Continuization therefore does not remove the hardness, but it produces a sensible high-multiplicity collective question and identifies exactly what survives the relaxation.
A second, weaker but still credible mirror uses Theorem 4, also proved in this paper:
“CP-CONSISTENCY is PSPACE-complete.”
Here the paper asks whether a CP-net contains an improving cycle: an outcome \(\omega\) and a nonempty improving sequence returning to \(\omega\). Define the cyclic mass of a society by
\[ K_\mu=\sum_{t:\,C_t\text{ contains an improving cycle}}\mu_t. \]
The problem \(\textsc{CP-Cycle-Mass}_{\infty}\) asks, given \(\mu\) and a tolerance \(\varepsilon\), whether \(K_\mu\le\varepsilon\). The exact mirror of the paper’s consistency question is the case \(\varepsilon=0\): is every positive-mass preference type globally consistent? A certificate of failure is a positive-mass type together with an improving cycle; a successful audit requires every supported CP-net type to be consistent.
This too is expected to be PSPACE-complete: with one type of mass \(1\), \(\varepsilon=0\) is exactly CP-CONSISTENCY, while membership follows by checking the finitely many types in polynomial space. The application is a population audit of recurring preference models: what fraction of deployed users, agents, or configuration templates exhibit self-reinforcing preference cycles? Further questions include minimum-mass cycle repair, cycle detection under bounded dependency width, and whether a small exceptional mass of inconsistent types can be isolated efficiently.
The soft spot is clear. The quota is an additional collective aggregation rule that the paper itself does not define. A critic could say that the paper studies reasoning for one CP-net, whereas quota support merely batches independent dominance queries. That criticism is serious. The defence is that a population-level social-choice problem needs some collective decision rule, and quota is the least committal one: it preserves the paper’s qualitative dominance relation exactly, introduces no cardinal utilities or fractional outcomes, and makes population mass operational rather than decorative. The mirror should therefore be presented as a high-multiplicity collective extension of Theorem 2, not as a problem already solved by the paper or as a claim that CP-net semantics themselves aggregate automatically.
The strongest case against the proposed mirrors is that both are population-weighted audits of independent CP-net computations, rather than genuinely collective computational problems.
For Theorem 2, \(d_t(\alpha,\beta)\) is already a complete answer to the individual problem. The proposed flow formulation adds no coupling: for each type, either some improving path exists or it does not, and all of that type’s mass can be assigned to such a path. The “LP” therefore reduces to summing the masses of types for which independent PSPACE queries answer yes. Rational masses can be cleared to obtain an ordinary finite electorate, so the continuum contributes no new object beyond a weighted batch of instances. The one-type reduction establishes hardness, but it also exposes the weakness: the population is computationally inert.
The same objection is sharper for Theorem 4. \(K_\mu\) is merely the prevalence of individually inconsistent preference descriptions. At \(\varepsilon=0\), the question is whether every positive-mass type passes the original consistency test; for positive \(\varepsilon\), one sums the masses of the failing types. Discarding enough mass to obtain consistency is equally immediate. Aggregating local rules by majority would produce a new CP-net and then invoke the paper’s consistency problem after a preprocessing step; editing rules would require an externally chosen repair metric. None of these is supplied by the paper’s consistency notion.
Those points make the proponent’s two formulations weak, but they do not sustain the requested universal negative. The obvious repair of Theorem 2 is a genuinely collective planning problem:
\[ \max_{\pi:\alpha\leadsto\beta} \sum_t \mu_t\,\mathbf 1[\pi\text{ is an improving sequence in }C_t]. \]
Here one common integral sequence of flips must persuade a quota of the population. The mass cannot be assigned to type-specific witnesses independently, and the distribution over CP-net types materially affects the answer. This remains a population continuization: configurations and flips stay integral, while only the population is divisible. It is also a natural extension of dominance, not an arbitrary fractionalisation of outcomes. The analogous “maximum mass sharing one improving cycle” repairs the consistency anchor in the same way.
Thus I can reject the quota and cycle-mass proposals as stated: they are weighted batches of the paper’s single-agent tests, with a largely decorative population axis. But I cannot honestly claim that no worthwhile mirror exists in any scenario. A shared-plan or shared-cycle version survives the objection and is a plausible high-multiplicity collective problem grounded directly in Theorems 2 and 4. The correct negative verdict is therefore qualified: the proposed mirrors are poor, but the paper itself is not a case where every continuous-population continuation fails.
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.