  In many domains it is desirable to assess the preferences of users in a
qualitative rather than quantitative way. Such representations of qualitative
preference orderings form an importnat component of automated decision tools.
We propose a graphical representation of preferences that reflects conditional
dependence and independence of preference statements under a ceteris paribus
(all else being equal) interpretation. Such a representation is ofetn compact
and arguably natural. We describe several search algorithms for dominance
testing based on this representation; these algorithms are quite effective,
especially in specific network topologies, such as chain-and tree- structured
networks, as well as polytrees.
