A lexicographic strategy for approximating dominance in CP-nets

To represent and reason about preferences over elements of a combinatorial domain it is necessary to have a compact preference model. One of the most extensively studied models for that setting is the conditional preference network (CP-net). A major problem with CP-nets is that some tasks that are critical to decision making are computationally hard if the preference ordering is given by a CP-net. To overcome this difficulty we propose to approximate CP-nets with other concise preference models that are equally intuitive but have better computational properties. In this paper, we focus on approximations of CP-nets using modified lexicographic preference models (LPMs). We show an acyclic CP-net's dominance relation can be approximated in polynomial time and present several results on the accuracy of the approximation.