A basic task in preference reasoning is inferring a preference between a pair of outcomes (alternatives) from an input set of preference statements. This preference inference task for comparative preferences has been shown to be computationally very hard for the standard kind of inference. Recently, a new kind of preference inference has been developed, which is polynomial for relatively expressive preference languages, and has the additional property of being much less conservative; this can be a major advantage, since it will tend to make the number of undominated outcomes smaller. It derives from a semantics where models are weak orders that are generated by objects called cp-trees, which represent a kind of conditional lexicographic order. We show that there are simple conditions, based on the notion of importance, that determine whether a weak order can be generated by a cp-tree of the given form. This enables a simple characterisation of the less conservative preference inference. We go on to study the importance properties satisfied by a simple kind of cp-tree, leading to another characterisation of the corresponding preference inference.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com