Checking Consistency of CP-Theory Preferences in Polynomial Time
Abstract
We investigate the problem of checking the consistency of qualitative preferences expressed in CP-theory. This problem is PSPACE-Complete even when the preferences are locally consistent or the preference variables have binary domain. We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We further show how the resulting sufficient condition can be used to efficiently identify a subset of outcomes that are non-dominated with respect to a set of qualitative preferences.
Cite
Text
Rauer et al. "Checking Consistency of CP-Theory Preferences in Polynomial Time." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I14.33659Markdown
[Rauer et al. "Checking Consistency of CP-Theory Preferences in Polynomial Time." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/rauer2025aaai-checking/) doi:10.1609/AAAI.V39I14.33659BibTeX
@inproceedings{rauer2025aaai-checking,
title = {{Checking Consistency of CP-Theory Preferences in Polynomial Time}},
author = {Rauer, Erik and Basu, Samik and Honavar, Vasant G.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2025},
pages = {15126-15133},
doi = {10.1609/AAAI.V39I14.33659},
url = {https://mlanthology.org/aaai/2025/rauer2025aaai-checking/}
}