AAAI 2025technical0 citations
Checking Consistency of CP-Theory Preferences in Polynomial Time
Erik Rauer, Samik Basu, Vasant Honavar
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.
BibTeX
@article{Rauer_Basu_Honavar_2025, title={Checking Consistency of CP-Theory Preferences in Polynomial Time}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33659}, DOI={10.1609/aaai.v39i14.33659}, abstractNote={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.}, number={14}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Rauer, Erik and Basu, Samik and Honavar, Vasant}, year={2025}, month={Apr.}, pages={15126-15133} }