Preference Trees: A Language for Representing and Reasoning about Qualitative Preferences

We introduce a novel qualitative preference representation language, preference trees , or P-trees . We show that the lan- guage is intuitive to specify preferences over combinatorial domains and it extends existing preference formalisms such as LP-trees , ASO-rules and possibilistic logic . We study rea- soning problems with P-trees and obtain computational com- plexity results.