Research map / Learning theory and algorithms / Combinatorial and search optimization
Checking Consistency of CP-Theory Preferences in Polynomial Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces cc-acyclic, a polynomial-time checkable sufficient condition for consistency of locally consistent CP-theory preferences, and uses it to compute a polynomial upper approximation of dominance.
Problem
Checking consistency of qualitative CP-theory preferences is PSPACE-complete (even for locally consistent or binary-domain preferences), and known sufficient conditions (Wilson 2011) are coNP-complete to check.
Approach
Defines a high-cardinality dependency graph over preference variables, keeping conditional edges whose source variable has at least two distinct condition values plus all relative-importance edges; if this graph is acyclic and preferences are locally consistent, a complete search tree satisfying the preferences exists, so they are consistent. The acyclicity is checkable in polynomial time, and the
Key results
- The cc-acyclic condition can be checked in O(|V|^2·|P|) or better polynomial time (Proposition 2), while checking the strong conditional acyclic and cuc-acyclic conditions is coNP-complete.
- Theorem 1 proves that locally consistent preferences with acyclic high-cardinality dependency graph H(P) are consistent.
- Theorem 2 and Proposition 4 show the cc-acyclic-based relation is a polynomial-time computable upper approximation of the dominance relation, computable in O(|V|^2·|P|^2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require locally consistent preferences and an acyclic high-cardinality dependency graph H(P) | CP-theory preferences · Locally consistent CP-theory preferences | consistency guarantee | Helped |
| Check cc-acyclicity using H(P) | CP-theory preferences · Locally consistent preferences | checking complexity: O(|V|·|P|+|V|) | Helped |
| Use the cc-acyclic upper approximation ≫cc | CP-theory preferences satisfying cc-acyclic · Outcome pairs | upper-approximation computation time: O(|V|2·|P|2) | Helped |
Surprising findings
- The cc-acyclic condition is incomparable to the strong conditional and cuc-acyclic conditions of Wilson (2011), so it is not implied by them.
Limitations
- No empirical implementation or comparison with Wilson's conditions; authors plan this as future work.
- Consistency guarantee applies only to locally consistent preferences (or binary domains); local consistency itself is coNP-complete in general.
- Only a sufficient condition; the cc-acyclic condition does not characterize consistency.
Experimental setup
Baselines: fully acyclic condition conditionally acyclic condition (Wilson 2011) strong conditional acyclic condition context-uniform conditional acyclic (cuc) condition
Builds on: CP-theories (Wilson 2004) CP-nets complete search trees (Wilson 2011) fully acyclic condition
Closest papers by meaning
- Restricted Domains of Dichotomous Preferences with Possibly Incomplete Information (AAAI 2021 · similarity 0.85)
- Aligning with Logic: Measuring, Evaluating and Improving Logical Preference Consistency in Large Language Models (ICML 2025 · similarity 0.85)
- Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion (AAAI 2024 · similarity 0.83)
- Approximation Algorithms for Preference Aggregation Using CP-Nets (AAAI 2024 · similarity 0.82)
- Back to Blackwell: Closing the Loop on Intransitivity in Multi-Objective Preference Fine-Tuning (NeurIPS 2026 · similarity 0.81)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.