More-or-Less CP-Networks
This work addresses a computational bottleneck for researchers and practitioners using CP-nets in preference modeling, though it is incremental as it builds on existing binary CP-net methods.
The paper tackles the computational complexity of dominance testing in multi-valued CP-nets by introducing more-or-less CP-nets, which exploit monotonicity and intervals to achieve the same complexity as binary CP-nets, and presents a search control rule that prunes the search space while maintaining completeness.
Preferences play an important role in our everyday lives. CP-networks, or CP-nets in short, are graphical models for representing conditional qualitative preferences under ceteris paribus ("all else being equal") assumptions. Despite their intuitive nature and rich representation, dominance testing with CP-nets is computationally complex, even when the CP-nets are restricted to binary-valued preferences. Tractable algorithms exist for binary CP-nets, but these algorithms are incomplete for multi-valued CPnets. In this paper, we identify a class of multivalued CP-nets, which we call more-or-less CPnets, that have the same computational complexity as binary CP-nets. More-or-less CP-nets exploit the monotonicity of the attribute values and use intervals to aggregate values that induce similar preferences. We then present a search control rule for dominance testing that effectively prunes the search space while preserving completeness.