Reasoning with Preference Trees over Combinatorial Domains. Liu, X. & Truszczynski, M. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT), volume 9346, pages 19-34, 2015. Springer (Acceptance rate: <font color="red">42%</font>).
Reasoning with Preference Trees over Combinatorial Domains [pdf]Paper  abstract   bibtex   
Preference trees, or P-trees for short, offer an intuitive and often concise way of representing preferences over combinatorial domains. In this paper, we propose an alternative definition of p-trees, and formally define their compact representation that exploits occurrences of identical subtrees. We show that p-trees generalize lexicographic preference trees and are strictly more expressive. We relate p-trees to answer-set optimization programs and possibilistic logic theories. Finally, we study reasoning with p-trees and establish computational complexity results for key reasoning tasks of comparing outcomes with respect to orders defined by p-trees, and of finding optimal outcomes.

Downloads: 0