ested in determining whether α ≻ β, i.e. α is preferred to β. Unfortunately, this query is NP-hard even for acyclic CPnets [Domshlak and Brafman, 2002] though some tractable special cases do exist.

## 3 Consistency And Satisfiability

Given a set of preference statements Ω extracted from a user, we might be interested in testing *consistency* of the induced preference relation. In general, there is no single notion of preferential consistency [Hansson, 2001].

In [Boutilier *et al.*, 1999], a CP-net N was considered consistent iff the partial ordering ≻ induced by N is *asymmetric*,
i.e. there exist at least one total ordering of the outcomes consistent with ≻. However, in many situations, we can ignore cycles in the preference relation, as long as these do not prevent a rational choice, i.e. there exist an outcome that is not dominated by any other outcome. In what follows, we refer to this as *satisfiability*1. It is easy to see that satisfiability is strictly weaker than asymmetry, and that asymmetry implies satisfiability. We will consider two cases: When the set Ω of preference statements induces a CP-net and, more generally, when preferences can take any form (and may not induce a CP-net).

When Ω defines an acyclic CP-net, the partial order induced by Ω is asymmetric [Boutilier *et al.*, 1999]. However, for cyclic CP-nets, asymmetry is not guaranteed. In the more general case, we are given a set Ω of conditional preference statements without any guarantee that they define a CP-net. Let the *dependence graph* of Ω be defined similarly to the graphs of CP-nets: the nodes stand for problem features, and a directed arc goes from Xito Xj iff Ω
contains a statement expressing preference on the values of Xj conditioned on the value of Xi. For example, the set Ω = {a : b ≻ **b, a** ∧ c : b ≻ b} does not induce a CPnet (the two conditionals are not mutually exclusive), and the preference relation induced by Ω is not asymmetric, despite the fact that the dependence graph of Ω is acyclic.

Note that while asymmetry implies satisfiability, the reverse does not hold in general. For example, the set Ω above is not asymmetric, but it is satisfiable (the assignment acb is undominated). Given such a satisfiable set of statements, we can prompt the user with one of the undominated assignments without further refinement of its preference relation. Theorem 1 shows that, in general, determining satisfiability of a set of statements is NP-complete. On the other hand, even for CP-nets, determining asymmetry is not known to be in NP [Domshlak and Brafman, 2002].

Theorem 1 SATISFIABILITY of a set of conditional preference statements Ω is NP*-complete.*
Proof: Membership in NP is straightforward, as an assignment is a polynomial-size witness that can be checked for 1In preference logic [Hansson, 2001], these notions of "consistency as satisfiability" and "consistency as asymmetry" correspond to the notions of *eligibility* and *restrictable eligibility*, respectively.

However, we will use the former terms as they seem more intuitive.

non-dominance in time linear in the size of Ω. To show hardness, we reduce 3-SAT to our problem: Given a 3-cnf formula F, for each clause (x ∨ y ∨ z) ∈ F we construct the conditional preference statement: x ∧ y : z ≻ z. This set of conditional preferences is satisfiable iff the original original formula F is satisfiable. 2 While testing satisfiability is hard in general, Theorem 2 presents a wide class of statement sets that can be tested for satisfiability in polynomial time.

Theorem 2 *A set of conditional preference statements* Ω,
whose dependency graph is acyclic and has bounded node in-degree can be tested for satisfiability in polynomial time. Proof: The proof is constructive, and the algorithm is as follows: First, for each feature X ∈ V, we construct a table TX with an entry for each assignment π ∈ D(P a(X)),
where each entry TX[π] contains all the values of X that are not dominated given Ω and π. Subsequently, we remove all the empty entries. For example, let A, B and C be a set of boolean problem features, and let Ω = {c ≻ **c, a** : b ≻
b, a ∧ c : b ≻ b}. The corresponding table will be as follows:

![0_image_0.png](0_image_0.png)

Observe that the entry TB[a ∧ c] has been removed, since, given a∧c, b and b are dominated according to the statements a ∧ c : **b > b** and a : b > b, respectively. Since the in-degree of each node X in the dependence graph of Ω is bounded by a constant k (i.e. |P a(X)| ≤ k), these tables take space and can be constructed in time O(n2 k). Given such tables for all the features in V, we traverse the dependence graph of Ω in a topological order of its nodes, and for each node X being processed we remove all the entries in TX that are not "supported" by (already processed) P a(X): An entry TX[π] is not supported by P a(X) if there exists a feature Y ∈ P a(X)
such that the value provided by π to Y appears in no entry of TY . For instance, in our example, the rows corresponding to a ∧ c and a ∧ c will be removed, since c does not appear in the (already processed) table of C. Now, if the processing of a feature X results in TX = ∅, then Ω is not satisfiable. Otherwise, any assignment to V consistent with the processed tables will be non-dominated with respect to Ω. 2 Note that, for sets of preference statements with cyclic dependence graphs, SATISFIABILITY remains hard even if the in-degree of each node is bounded by k ≥ 6, since 3-SAT remains hard even if each variable participates in at most three clauses of the formula the proof of Theorem 1). However, when at most one condition is allowed in each preference statement, and the features are boolean, then SATISFIABIL-ITY can be reduced to 2-SAT, and thus tested in polynomial time. Further study of additional tractable cases is clearly of both theoretical and practical interest.