  Information about user preferences plays a key role in automated decision
making. In many domains it is desirable to assess such preferences in a
qualitative rather than quantitative way. In this paper, we propose a
qualitative 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 often compact
and arguably quite natural in many circumstances. We provide a formal semantics
for this model, and describe how the structure of the network can be exploited
in several inference tasks, such as determining whether one outcome dominates
(is preferred to) another, ordering a set outcomes according to the preference
relation, and constructing the best outcome subject to available evidence.
