Hélène Fargier
email: helene.fargier@irit.fr

Jérôme Mengin
email: jerome.mengin@irit.fr

A Knowledge Compilation Map for Conditional Preference Statements-based Languages

Conditional preference statements have been used to compactly represent preferences over combinatorial domains. They are at the core of CP-nets and their generalizations, and lexicographic preference trees. Several works have addressed the complexity of some queries (optimization, dominance in particular). We extend in this paper some of these results, and study other queries which have not been addressed so far, like equivalence, thereby contributing to a knowledge compilation map for languages based on conditional preference statements. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries. formula = ∧ = ′ is a contradiction; also, the interpretations are thus in one-to-one correspondence with X. If is such a propositional formula over X and ∈ X, we will write |= when satis es , that is when, assigning to every literal = that appears in the value true if [ ] = , and the value false otherwise, makes true.

Given a formula , or a partial instantiation , Var( ) and Var( ) denote the set of attributes, the values of which appear in and respectively.

When it is not ambiguous, we will use as a shorthand for the literal = ; also, for a conjunction of such literals, we will omit the ∧ symbol, thus = ∧ = ¯ for instance will be denoted ¯ .

Preference Relations

Depending on the knowledge that we have about a decision maker's preferences, given any pair of distinct alternatives , ′ ∈ X, one of the following situations must hold: one may be strictly preferred over the other, or and ′ may be equally preferred, or and ′ may be incomparable.

Assuming that preferences are transitive, such a state of knowledge about the DM's preferences can be characterised by a preorder over X: is a binary, re exive and transitive relation; for alternatives , ′ , we then write ′ when ( , ′ ) ∈ ; ≻ ′ when ( , ′ ) ∈ and ( ′ , ) ∉ ; ∼ ′ when ( , ′ ) ∈ and ( ′ , ) ∈ ; ⊲⊳ ′ when ( , ′ ) ∉ and ( ′ , ) ∉ . Note that for any pair of alternatives , ′ ∈ X either ≻ ′ , or ′ ≻ , or ∼ ′ or ⊲⊳ ′ .

The relation ∼ de ned in this way is the symmetric part of , it is re exive and transitive, ⊲⊳ is irre exive, they are both symmetric. The relation ≻ is the irre exive part of , it is what is usually called a strict partial order: it is irre exive and transitive.

Terminology and notations. We say that alternative dominates alternative ′ (w.r.t. ) if and only if ′ ; if ≻ ′ , then we say that strictly dominates ′ . We use standard notations for the complements of ≻ and : we write ′ when it is not the case that ′ , and ⊁ ′ when it is not the case that ≻ ′ .

• every node is labelled with a set of attributes, denoted Var( );

6 Given some pre-order over X, attribute is said to be preferentially dependent on attribute if there exist , ′ ∈ , , ′ ∈ , ∈ X \ ( { , }) such that ′ but ′ ′ ′ .

INTRODUCTION

Preference handling is a key component in several areas of Articial Intelligence, notably for decision-aid systems. Research in Articial Intelligence has led to the development of several languages that enable compact representation of preferences over complex, combinatorial domains. Some preference models rank alternatives according to their values given by some multivariate function; this is the case for instance with valued constraints [START_REF] Schiex | Valued Constraint Satisfaction Problems: Hard and Easy Problems[END_REF], additive utilities and their generalizations [START_REF] Braziunas | Local Utility Elicitation in GAI Models[END_REF][START_REF] Gonzales | GAI Networks for Utility Elicitation[END_REF]. Ordinal models like CP nets and their generalisations [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Brafman | On graphical modeling of preference and importance[END_REF][START_REF] Wilson | Extending CP-Nets with Stronger Conditional Preference Statements[END_REF], or lexicographic preferences and their generalisations [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF][START_REF] Bräuning | Learning Conditional Lexicographic Preference Trees[END_REF][START_REF] Fargier | Learning Lexicographic Preference Trees From Positive Examples[END_REF][START_REF] Gigerenzer | Reasoning the Fast and Frugal Way: Models of Bounded Rationality[END_REF][START_REF] Schmitt | On the Complexity of Learning Lexicographic Strategies[END_REF][START_REF] Wilson | An E cient Upper Approximation for Conditional Preference[END_REF] use sets of conditional preference statements to represent a pre-order over the set of alternatives.

Many problems of interest, like comparing alternatives or nding optimal alternatives, are NP-hard for many of these models, even PSPACE hard for some models, which makes these representations di cult to use in some decision-aid systems like congurators, where real-time interaction with a decision maker is needed. One approach to tackle this problem is Knowledge Compilation, whereby a model, or a part of it, is compiled, o -line, into another representation which enables fast query answering, even if the compiled representation has a much bigger size. This approach has rst been studied in propositional logic: [START_REF] Darwiche | Compiling Knowledge into Decomposable Negation Normal Form[END_REF][START_REF] Darwiche | A Knowledge Compilation Map[END_REF] compare how various subsets of propositional logic can succinctly, or not, express some propositional knowledge bases, and the complexity of queries of interest. [START_REF] Coste-Marquis | Expressive Power and Succinctness of Propositional Languages for Preference Representation[END_REF] follow a similar approach to compare extensions of propositional logic which associate real values to models of a knowledge base; [START_REF] Fargier | A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams[END_REF] provide such a map for value functionbased models.

The aim of this paper is to initiate such a compilation map for models of preferences based on the language of conditional preference statements. We compare the expressiveness and succinctness of various languages on these conditional preference statements, and the complexity of several queries of interest for these languages.

The next section recalls some basic de nitions about combinatorial domains and pre-orders, and introduces notations that will be used throughout. Section 3 gives an overview of various languages based on conditional preference statements that have been studied in the literature. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries. Section 4 and 5 respectively study expressiveness and succinctness for languages based on conditional preference statements. Sections 6 study the complexity of queries for these languages. Proofs can be found in [START_REF] Fargier | A Knowledge Compilation Map for Conditional Preference Statements-based Languages[END_REF].

PRELIMINARIES 2.1 Combinatorial Domain

We consider languages that can be used to represent the preferences of a decision maker over a combinatorial space X: here X is a set of attributes that characterise the possible alternatives, each attribute ∈ X having a nite set of possible values ; we assume that | | ≥ 2 for every ∈ X; then X denotes the cartesian product of the domains of the attributes in X, its elements are called alternatives. For a binary attribute , we will often denote by , ¯ its two possible values. In the sequel, is the number of attributes in X.

For a subset of X, we will denote by the cartesian product of the domains of the attributes in , called instantiations of , or partial instantiations (of X). If is an instantiation of some ⊆ X, [ ] denotes the restriction of to the attributes in ∩ ; we say that instantiation ∈ and are compatible if [ ∩ ] =

[ ∩ ]; if ⊆ and [ ] = , we say that extends . Sets of partial instantiations can often be conveniently, and compactly, speci ed with propositional formulas: the atoms are = for every ∈ X and ∈ , and we use the standard connectives ∧ (conjunction), ∨ (disjunction), → (implication), ↔ (equivalence) and ¬ (negation); we denote by ⊤ (resp. ⊥) the formula always true (resp. false). Implicitly, this propositional logic is equipped with a theory that enforces that every attribute has precisely one value from its domain; so, for two distinct values , ′ of attribute , the

LANGUAGES 3.1 Conditional Preference Statements

A conditional preference statement (aka., CP statement) over X is an expression of the form | : ≥ ′ , where is a propositional formula over ⊆ X, , ′ ∈ are such that [ ] ≠ ′ [ ] for every ∈ , and , , are disjoint subsets of X, not necessarily forming a partition of X. Informally, such a statement represents the piece of knowledge that, when comparing alternatives , ′ that both satisfy , the one that has values for is preferred to the one that has values ′ for , irrespective of the values of the attributes in , every attribute in X \ ( ∪ ) being xed. We call the conditioning part of the statement; we call the swapped attributes, and the free part.

Example 1 ((Example A in [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], slightly extended)). Consider planning a holiday, with three choices / attributes: wait til next month ( = ) or leave now ( = ¯ ), going to city 1, 2 or 3 ( = 1 , = All else being equal, I prefer to go to city 3, city 1 being my second best choice: ⊤ | ∅ : 3 ≥ 1 ≥ 2 . Also, if I go now, I prefer to y: ¯ | ∅ : ≥ ¯ . Together, the last two statements imply that if I go now, I prefer to go to city 3 by plane than go to city 1 by car; however these statements do not say what I prefer between ying to city 1 or driving to city 3. In fact, I prefer the former, this tradeo can be expressed with the statement ¯ | ∅ : 1 ≥ 3 ¯ . Finally, if I go later, I prefer to drive, irrespective of the city: |{ } : ¯ ≥ .

Conditional preference statements have been studied in many works, under various language restrictions. They are the basis for CP-nets [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF][START_REF] Boutilier | Reasoning With Conditional Ceteris Paribus Preference Statements[END_REF] and their extensions, and have been studied in a more logic-based fashion by e.g. [START_REF] Goldsmith | The Computational Complexity of Dominance and Consistency in CP-nets[END_REF] and [START_REF] Wilson | Consistency and Constrained Optimisation for Conditional Preferences[END_REF][START_REF] Wilson | Extending CP-Nets with Stronger Conditional Preference Statements[END_REF][START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]]. 1 They are closely related to CI-statements by [START_REF] Bouveret | Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods[END_REF] For the semantics sets of CP statements, we use the de nitions of [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]. Given a statement | : ≥ ′ , let = Var( ) and = Var( ) = Var( ′ ): a worsening swap is any pair of alternatives

( , ′ ) such that [ ] = ′ [ ] |= , [ ] = and ′ [ ] = ′ ,
and such that for every attribute ∉ ∪ ∪ it holds that [ ] =

′ [ ]; we say that | : ≥ ′ sanctions ( , ′ ). For a set of CPstatements , let * be the set of all worsening swaps sanctioned by statements of , and de ne to be the re exive and transitive closure of * . [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] proves that ′ if and only if = ′ or * contains a nite sequence of worsening swaps ( , +1 ) 0 ≤ ≤ -1 with 0 = and

= ′ . 2 Example 2 (Example 1, continued). Let = {⊤ |{ } : ¯ ≥ , ⊤ | ∅ : 3 ≥ 1 ≥ 2 , | ∅ : ≥ ¯ , ¯ | ∅ : 1 ≥ 3 ¯ , |{ } : ¯ ≥ }. Then ⊤ |{ } : ¯ ≥ sanctions for instance ( ¯ 2 , 3 ¯ ), so ¯ 2 3 ¯ . Also, ⊤ | ∅ : 3 ≥ 1 ≥ 2 sanctions ( ¯ 1 , ¯ 2 ), ¯ | ∅ : ≥ ¯ sanctions ( ¯ 2 , ¯ 2 ¯ ), so, by transitivity, ¯ 1 ¯ 2 ¯ . It is not di cult to check that ¯ 2 ⊲⊳ ¯ 1 ¯ .
Let us call CP the language where formulas are sets of statements of the general form | : ≥ ′ . This language is very expressive: it is possible to represent any preorder "in extension" with preference statements of the form ≥ ′ -they all have = X as set of swapped attributes, = ⊤ as condition, and no free attribute.

This expressiveness has a cost: we will see that many queries about pre-orders represented by CP-statements are PSPACE-hard for the language CP. Several restrictions / sub-languages have been studied in the literature, we review them below.

Linearisability. Although the original de nition of CP-nets by [START_REF] Boutilier | Reasoning With Conditional Ceteris Paribus Preference Statements[END_REF] does not impose it, many works on CP-nets, especially following [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF], consider that they are intended to represent a strict partial order, that is, that should be antisymmetric; equivalently, this means that the irre exive part ≻ of can be extended to a linear order. We say that a set of CP-statements is linearisable in this case. 33Notations. We write : ≥ ′ when is empty, and ≥ ′ when is empty and = ⊤. Note that we reserve the symbol ≥ for conditional preference statements, whereas "curly" symbols ≻, ⊁, , are used to represent relations over the set of alternatives.

In the remainder of this section, we present various sublanguages of CP. Some are de ned by imposing various simple syntactical restrictions on the formulas, two are languages which have been well studied (CP-nets and lexicographic preference trees); we close the section by introducing a new, parameterised class of sublanguages of CP which have interesting properties, as will be shown in subsequent subsections.

Statement-wise Restrictions

Some restrictions are on the syntactical form of statements allowed; they bear on the size of the set of free attributes, or on the size of the set of swapped attributes, or on the type of conditioning formulas allowed. Given some language L ⊆ CP, we de ne the following restrictions: L⋫ = only formulas with empty free parts ( = ∅) for every statement;4 L∧ = only formulas where the condition of every statement is a conjunction of literals; k-L = only formulas where the set of swapped attributes contains no more than attributes (| | ≤ ) for every statement; in particular, we call elements of 1-CP unary statements.

In particular, 1-CP∧ is the language studied by [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], and 1-CP⋫ is the language of generalized CP-nets as de ned by [START_REF] Goldsmith | The Computational Complexity of Dominance and Consistency in CP-nets[END_REF].

Graphical Restrictions

Given ∈ CP over set of attributes X, we de ne as the graph with sets of vertices X, and such that there is an edge ( , ) if there is | : ≥ ′ ∈ such that ∈ Var( ) and ∈ Var( ), or ∈ Var( ) and ∈ . We call the dependency graph of . Note that can be computed in polynomial time. This de nition, inspired by [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]Def. 15], generalises that of [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF], which is restricted to the case where all CP statements are unary and have no free attributes, and that of [START_REF] Brafman | On graphical modeling of preference and importance[END_REF], who study statements with free attributes. Many tractability results on sets of CP statements have been obtained when has good properties. Given some language L ⊆ CP, we de ne: L = the restriction of L to acyclic formulas, which are those such that is acyclic; 5L poly = the restriction of L to formulas where the dependency graph is a polytree.

[35] also de nes a weaker graphical restriction, called "contextuniform conditional acyclicity", but it turns out that it does gives rise to the same complexities as another, weaker restriction called "conditional acyclicity" by [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], which we generalize in section 3.6.

¯ ≥ 3 ≥ 1 ≥ 3 ¯ ≥ 1 ¯ ≥ 2 ¯ 1 ≥ 2 ≥ 2 ¯ ¯ ≥ 3 ≥ 1 ≥ 2 ¯

CP-nets

In their seminal work, [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] de ne a CP-net over a set of attributes X to be composed of two elements:

(1) a directed graph over X, which should represent preferential dependencies between attributes; 6 (2) a set of conditional preference tables, one for every attribute : if is the set of parents of in the graph, the conditional preference table for contains exactly | | rules : ≥, for every ∈ , where the ≥'s are linear orders over . Therefore, as shown by [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], CP-nets can be seen as sets of unary CP statements in conjunctive form with no free attribute. Specically, given a CP-net N over X, de ne N to be the set of all CP statements : ≥ ′ , for every attribute , every ∈ where is the set of parents of in the graph, every , ′ ∈ such that , ′ are consecutive values in the linear order ≥ speci ed by the rule : ≥ of N . Then the dependency graph of N , as de ned in Section 3.3, coincides with the graph of N . We call CPnet = the language that contains all N , for every CP-net N .

Note that CPnet ⊆ 1-CP∧⋫. For a given ∈ 1-CP∧⋫, being a CP-net necessitates a very strong form of local consistency and completeness: for every attribute with parents in , for every ∈ , for every , ′ ∈ , must explicitly, and uniquely, order and ′ .

[8] de ne TCP-nets as an extension of CP-nets where it is possible to represent tradeo s, by stating that, under some conditions, some attributes are more important than other ones. [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] describes how TCP-nets can be transformed, in polynomial time, into equivalent sets of 1-CP∧ statements.

Lexicographic Preference Trees

LP-trees generalise lexicographic orders, which have been widely studied in decision making -see e.g. [START_REF] Peter | Lexicographic Orders, Utilities and Decision Rules: A Survey[END_REF]. As an inference mechanism, they are equivalent to search trees used by [START_REF] Boutilier | Preference-Based Constrained Optimization with CP-Nets[END_REF], and formalised by [START_REF] Wilson | Consistency and Constrained Optimisation for Conditional Preferences[END_REF][START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]. As a preference representation, and elicitation, language, slightly di erent de nitions for LP-trees have been proposed by [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF][START_REF] Bräuning | Learning Conditional Lexicographic Preference Trees[END_REF][START_REF] Fargier | Learning Lexicographic Preference Trees From Positive Examples[END_REF]. We use here a de nition which subsumes the others.

An LP-tree that is equivalent to the set of CP-statements of Example 2 is depicted on Figure 1. More generally, an LP-tree over X is a rooted tree with labelled nodes and edges, and a set of preference tables; speci cally

• if is not a leaf, it can have one child, or | Var( ) | children;
• in the latter case, the edges that connect to its children are labelled with the instantiations in Var( ); • if has one child only, the edge that connects to its child is not labelled: all instantiations in Var( ) lead to the same subtree; • we denote by Anc( ) the set of attributes that appear in the nodes between the root and (excluding those at ), and by Inst( ) (resp. NonInst( )) the set of attributes that appear in the nodes above that have more than one children (resp. only one child); • a conditional preference table CPT( ) is associated with : it contains local preference rules of the form : ≥, where ≥ is a preorder over Var( ), and is a propositional formula over some attributes in NonInst( ).

We assume that the rules in CPT( ) de ne their preorder over Var( ) in extension. Additionally, two constraints guarantee that an LP-tree de nes a unique preorder over X:

• no attribute can appear at more than one node on any branch of ; and, • at every node of , for every ∈ NonInst( ), CPT( ) must contain exactly one rule : ≥ such that |= .

Given an LP-tree and an alternative ∈ X, there is a unique way to traverse the tree, starting at the root, and along edges that are either not labelled, or labelled with instantiations that agree with , until a leaf is reached. Now, given two distinct alternatives , ′ , it is possible to traverse the tree along the same edges as long as and ′ agree, until a node is reached which is labelled with some such that [ ] ≠ ′ [ ]: we say that decides { , ′ }.

In order to de ne for some LP-tree , let * be the set of all pairs of distinct alternatives ( , ′ ) such that there is a node that decides { , ′ } and the only rule :

≥ ∈ CPT( ) with [NonInst( )] = ′ [NonInst( )] | = is such that [ ] ≥ ′ [ ].
Then is the re exive closure of * . P 1. Let be an LP-tree over X, then as de ned above is a preorder. Furthermore, is a linear order if and only if 1) every attribute appears on every branch and 2) every preference rule speci es a linear order.

An LP-tree is said to be complete if the two conditions in Proposition 1 hold, that is, if is a linear order. From a semantic point of view, an LP-tree is equivalent to the set that contains, for every node of labelled with = Var( ), and every rule : ≥ in CPT( ), all CP statements of the form

∧ | : ♯ ≥ ′♯ , where
• is the combination of values given to the attributes in Inst( ) along the edges between the root and , and • , ′ ∈ such that ≥ ′ , and ♯ is the set of attributes on which and ′ have distinct values, and

♯ = [ ♯ ],
and

′♯ = ′ [ ♯ ]; and • = [X -(Anc( ) ∪ )].
This set of statements indicate that outcomes that agree on Anc( ) and satisfy ∧ , but have di erent values for Var( ), should be ordered according to ≥ , whatever their values for attributes in . LPT = the language of LP-trees as de ned above; we consider that LPT is a subset of CP. 7Note that, using the notations de ned above, k-LPT = LPT ∩ -CP is the restriction of LPT where every node has at most attributes, for every ∈ N; in particular, 1-LPT is the language of LP-trees with one attribute at each node; and LPT∧ = LPT ∩ CP∧ is the restriction of LPT where the condition in every rule at every node is a conjunction of literals. Search trees of [START_REF] Wilson | Consistency and Constrained Optimisation for Conditional Preferences[END_REF][START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] and LP-trees as de ned by [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF][START_REF] Lang | Voting on Multi-Issue Domains with Conditionally Lexicographic Preferences[END_REF] are sublanguages of 1-LPT∧; LP-trees of [START_REF] Fargier | Learning Lexicographic Preference Trees From Positive Examples[END_REF] and [START_REF] Bräuning | Learning Conditional Lexicographic Preference Trees[END_REF] are sublanguages of LPT∧.

Lexico-compatible Formulas

Many graphical restrictions that have been proposed in order to enable polytime answers to some queries are in fact particular cases of a more general property which we study now. We de ne a new, parameterised family of languages. Given some language L ⊆ CP and ∈ N, we de ne:

L lex = the restriction of L to formulas such that there exists some complete LP-tree ∈ -LPT such that extends .

We say that formulas of CP lex are -lexico-compatible.8 [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] proves that acyclic formulas of 1-CP are 1-lexico-compatible when they enjoy some local consistency property; it illustrates that -lexico-compatibility is indeed a weak form of acyclicity. We will see that k-lexico-compatibility makes some queries tractable.

The next result shows that proving that some ∈ CP is -lexicocompatible, for a xed , is not always easy:

P 2. For a xed ∈ N, checking if a formula ∈ CP is -lexico-compatible is coNP-complete.
Algorithm 1 checks if a given formula is k-lexico-compatible. Given ∈ CP, it builds, in a top-down fashion, a complete ∈ k-LPT that is compatible with . The algorithm is similar to the algorithm proposed by [START_REF] Booth | Learning conditionally lexicographic preference relations[END_REF] to learn an LP-tree that sanctions a given set of pairs ( , ′ ). It starts with an empty root node at step 1; then, while there is some empty node, it picks one of them, call it , and calls at step 2b the function chooseA ribute to get a pair ( , ≥) to label , where is a set of at most attributes, none of which appear above , and ≥ is a linear order over ; if no such pair is compatible with , in a sense that will be de ned shortly, chooseAttribute returns failure and the algorithm stops at step 2c; otherwise, if there remain some attributes that do not appear in nor at any node above , then the algorithm expands the tree below at step 2e by creating a branch and a new node for every instantiation ∈ , and loops.

Note that all edges of the tree built by the algorithm are labelled, so that, at every node , NonInst( ) = ∅, so CPT( ) must contain only one rule of the form ⊤ : ≥, where ⊤ is the formula always true. This is why chooseA ribute needs to return one linear order over only, we do not need to specify the trivial condition ⊤ here. There may be a more compact -LP-tree compatible with than the one returned by the above algorithm when it does not fail, but we are only interested here in checking if is -lexico-compatible, and we have seen that the problem is coNP-complete, so it seems di cult to avoid exploring a tree with size exponential in the size of in the worst case. We now speci y some condition that chooseA ribute must verify in order for the algorithm to be correct and complete.

Given any yet unlabelled node of the tree being build, let

( ) = { | : ≥ ′ ∈ | ∧ inst( ) |= ⊥, ∩ Anc( ) = ∅}.
De nition 1. We say that chooseA ribute is -compatible if the pair ( , ≥) that chooseA ribute returns at some yet unlabelled node is such that for every | :

≥ ′ ∈ ( ): (1) if Var( ) ∩ = ∅, then ∩ = ∅; (2) if Var( ) ∩ ≠ ∅, then > ′ for every , ′ ∈ such that ∧ |= ⊥, ′ ∧ ′ |= ⊥, [X \ ( ∪ )] = ′ [X \ ( ∪ )] and ∧ |= ⊥.
If no such pair ( , ≥) can be found, then chooseA ribute must return failure. Condition (2) guarantees that will correctly decide every pair of alternatives that is sanctionned by | : ≥ ′ and that will be decided at . When the entire tree is built in this way, condition ?? guarantees that at every node , if | : ≥ ′ ∈ ( ) then ∩ Anc( ) = ∅. P 3. Given ∈ CP and some ∈ N, suppose that chooseA ribute is -compatible, then ∈ CP lex if and only if the algorithm above returns some ∈ k-LPT such that ⊇ ; otherwise, it returns FAILURE.

Note that chooseA ribute can be implemented to run in polynomial time, for xed : there are no more than =1 ≤ possibilities for the it can return, and the number of pairs , ′ that it must check against every statement in ( ) is bounded by | | 2 , and | | is bounded by , where is the size of the largest domain of the attributes in X. Also, each branch of the tree returned by the algorithm, when it succeeds, can have at most nodes, but the tree can have up to leaves.

EXPRESSIVENESS

We detail our results about expressiveness of the various languages studied here in this section, the results about succinctness are in the next section. These results are summarised on Figure 2.

De nition 2. Let L and L ′ be two languages for representing preorders. We say that L is at least as expressive as L ′ , written L ⊒ L ′ , if every preorder that can be represented with a formula of L ′ can also be represented with a formula of L; we write L L ′ if L ⊒ L ′ but it is not the case that L ′ ⊒ L, and say in this case that L is strictly more expressive than L ′ . We write L ⊑ ⊒ L ′ when the two languages are equally expressive.

We reserve the usual "rounded" symbols ⊂ and ⊆ for (strict) set inclusion, and ⊃ and ⊇ for the reverse inclusions. Note that ⊒ is a preorder, and obviously L ⊇ L ′ implies L ⊒ L ′ .

Clearly, CP⋫ ⊂ CP and CP∧ ⊂ CP; however, these three languages have the same expressiveness, because of the following:

P 4. Given some preorder , de ne ∈ { [Δ( , ′ )] ≥ ′ [Δ( , ′ )] | ′ , ≠ ′ }, where Δ( , ′
) is the set of attributes that have di erent values in and ′ , then ∈ CP⋫ ∩ CP∧, and = .

A large body of works on CP-statements since the seminal paper by [START_REF] Boutilier | Preference-Based Constrained Optimization with CP-Nets[END_REF] concentrate on various subsets of 1-CP. With this strong restriction on the number of swapped attributes, CP-statements have a reduced expressiveness.

Example 3. Consider two binary attributes and , with respective domains { , ¯ } and { , ¯ }. De ne preorder such that ≻ ¯ ¯ ≻ ¯ ≻ ¯ . This can be represented in CP with = { ≥ ¯ ¯ , ¯ ¯ ≥ ¯ , ¯ ≥ ¯ }. But it cannot be represented in 1-CP: { : ≥ ¯ , ¯ : ¯ ≥ , : ≥ ¯ , ¯ : ¯ ≥ } * ⊆ * , but this is not su cient to compare ¯ with ¯ . The four remaining formulas of 1-CP over these two attributes are : ≥ ¯ , : ¯ ≥ , : ≥ ¯ , : ¯ ≥ , adding any of them to yields a preorder which would not be antisymmetric.

Forbidding free parts incurs an additional loss in expressiveness:

Example 4. Consider two binary attributes and , with respective domains { , ¯ } and { , ¯ }. De ne preorder such that ≻ ¯ ≻ ¯ ≻ ¯ ¯ . This can be represented in 1-CP with = { : ≥ ¯ , ≥ ¯ }. But the "tradeo " ¯ ≻ ¯ cannot be represented in 1-CP⋫, any formula of 1-CP⋫ that implies it will put some intermediate alternative between ¯ and ¯ However, restricting to conjunctive statements does not incur a loss in expressiveness.

P

5. CP = ∈N k-CP and, for every ∈ N:

CP∧ ⊑ ⊒ CP⋫ ⊑ ⊒ CP k-CP ⊑ ⊒ k-CP∧ k-CP⋫ ⊑ ⊒ k-CP∧⋫ k-CP (k-1)-CP.
Because an LP-tree can be a single node labelled with X, and a single preference rule ⊤ : ≥ where ≥ can be any preorder, LPT can represent any preorder. Limiting to conjunctive conditions in the rules is not restrictive. However, restricting to 1-LPT reduces expressiveness, even if one considers formulas of 1-CP that represent total, linear orders:

Example 5. Let = { ≥ ¯ , ¯ | : ¯ ≥ , ¯ : ¯ ≥ , : ≥ ¯ , : ≥ ¯ , ¯ | : ¯ ≥ }. This yields the following linear order: ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ .
No ∈ 1-LPT can represent it: could not be at the root of such a tree because for instance ¯ ¯ ¯ ¯ ¯ and ¯ ¯ ¯ ¯ ; neither could , since ¯ ¯ ¯ and ¯ ¯ ¯ ¯ ; and nally could not be at the root either, because ¯ and ¯ ¯ ¯ ¯ . P 6. LPT = ∈N k-LPT and, for every ∈ N:

CP ⊑ ⊒ LPT ⊑ ⊒ LPT∧ k-LPT ⊑ ⊒ k-LPT∧ (k-1)-LPT.
Finally, note that k-lexico-compatibility is a weaker restriction than being a -LP-tree. P 7. For every ∈ N: CP lex CP lex -1 , and CP lex k-LPT. [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] proves that 1-CP ⊆ CP lex 1 . Whether this property can be generalised, with an appropriate de nition of -acyclicity, is left for future work.

SUCCINCTNESS

Another criterion is the relative sizes of formulas that can represent the same preorder in di erent languages. [START_REF] Cadoli | Space E ciency of Propositional Knowledge Representation Formalisms[END_REF] study the space e ciency of various propositional knowledge representation formalisms. An often used de nition of succinctness [START_REF] Darwiche | A Knowledge Compilation Map[END_REF][START_REF] Gogic | The Comparative Linguistics of Knowledge Representation[END_REF] makes it a particular case of expressiveness, which is not a problem when comparing languages of same expressiveness. However, we study here languages with very di erent expressiveness, so we need a more ne grained de nition: De nition 3. Let L and L ′ be two languages for representing preorders. We say that L is at least as succinct as L ′ , written L ≦ L ′ , if there exists a polynomial such that for every ′ ∈ L ′ , there exists ∈ L that represent the same preorder as ′ and such that | | < (| ′ |). 9 Moreover, we say that L is strictly more succinct than L ′ , written L ≪ L ′ , if L ≦ L ′ and for every polynomial , there exists ∈ L such that:

• there exists ′ ∈ L ′ such that = ′ , but • for every ′ ∈ L ′ such that = ′ , | ′ | > (| |).
With this de nition, L≪L ′ if every formula of L ′ has an equivalent formula in L which is "no bigger" (up to some polynomial transformation of the size of ), and there is at least one sequence of formulas (one formula for every polynomial ) in L that have equivalent formulas in L ′ but necessarily "exponentially bigger". 10

P

8. The following hold, for languages L, L ′ , L ′′ :

• if L ⊇ L ′ then L ≦ L ′ ; and if L ≦ L ′ , then L ⊒ L ′ ; • if L ≪ L ′ then L ≦ L ′ and L ′ ≦ L; • if L ⊑ ⊒ L ′ , the reverse implication holds: if L ≦ L ′ and L ′ ≦ L then L ≪ L ′ (otherwise, it might be that L ′ ≦ L because L ′ ⊒ L); • if L ⊇ L ′ and L ′ ≪ L ′′ , then L ≪ L ′′ .
Restricting the conditioning part of the statements to be conjunctions of literals does induce a loss in succinctness. Example 6. Consider 2 + 1 binary attributes 1 , 2 , . . . , , 1 , 2 , . . . , , , and let contain 2 +2 unary CP-statements with no free attribute:

( 1 ∨ 1 ) ∧ ( 2 ∨ 2 ) ∧ . . . ∧ ( ∨ ) : ≥ ¯ , ¬[( 1 ∨ 1 ) ∧ ( 2 ∨ 2 ) ∧ . .

. ∧ ( ∨ )]

: ¯ ≥ and ¯ ≥ and ¯ ≥ for every ∈ {1, . . . , }. Then ∈ 1-CP⋫, but is not in conjunctive form. A set of conjunctive CP-statements equivalent to has to contain all 2 statements of the form 1 2 . . . : ≥ ¯ with = or = for every . 9 Where

| | = | : ≥ ′ ∈ ( | | + | | +2 | Var( ) |)
, with | | = the number of connectives plus the number of atoms of . 10 When ≪ is de ned as the strict counterpart of ≦, it can happen that L≪L ′ even if there is no real di erence in representation size in the two languages, but L L ′ . Also, free attributes enable succinct representation of relative importance of some attributes over others; disabling free attributes thus incurs a loss in succinctness:

Example 7. Consider + 1 binary attributes 1 , 2 , . . . , , , let = { 1 , 2 , . . . , }, and let = { | ≥ ¯ }. Then * = {( , ′ ¯ ) | , ′ ∈ }, and * is equal to its transitive closure, so, if ≠ ′ , then ′ if and only if [ ] = and ′ [ ] = ¯ . This can be represented, without free attribute, with formula that contains, for every ⊆ and every ∈ , the statement ≥ ¯ ¯ , where ¯ denotes the tuple obtained by inverting all values of . For every 0 ≤ ≤ there are subsets of of size , with 2 ways to choose ∈ , thus contains 0 2 = 3 statements.

Restricting to CP-nets induces a further loss in succinctness, as the next example shows: Example 8. Consider + 1 binary attributes 1 , 2 , . . . , , , and let be the 1-CP⋫∧ formula that contains the following statements: ≥ ¯ for = 1, . . . , ; 1 2 . . . : ≥ ¯ ; ¯ : ¯ ≥ for = 1, . . . , . The size of is linear in . Because preferences for depend on all 's, a CP-net equivalent to will contain, in the table for , 2 CP statements.

P 9.
The following hold:

• L ≪ L∧ for every L such that 1-CP⋫ ⊆ L ⊆ CP; • L ≪ L⋫ for every L such that 1-CP∧ ⊆ L ⊆ CP; • 1-CP⋫∧ ≪ CPnet.

QUERIES

Table 1 gives an overview of the tractability of the queries that we study in this section. We begin this section with the two queries that have generated most interest in the literature on CP statements.

Linearisability. Knowing that a given ∈ CP is linearisable (that is, that is antisymmetric) is valuable, as it makes several other queries easier. It also gives some interesting insights into the semantics of . The following query has been addressed in many works on CP statements: 11Given , is linearisable? [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] prove that when its dependency graph is acyclic, then a CP-net is linearisable. This result has been extended by [START_REF] Brafman | On graphical modeling of preference and importance[END_REF][START_REF] Domshlak | CP-nets: Reasoning and Consistency Testing[END_REF][START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], who give weaker, su cient syntactical conditions that guarantee that a locally consistent set of unary, conjunctive CP statements is linearisable; more generally, by de nition of -lexico-compatibility, every formula of CP lex is linearisable (since it is compatible with a complete LP-tree). [24, Theorem 3 and 4] prove that is PSPACE-complete for 1-CP⋫∧. P 10. can be checked in polynomial time for LPT.

Comparing alternatives. A basic question, given a formula and two alternatives , ′ is: how do and ′ compare, according to ? Is it the case that ≻ ′ , or ′ ≻ , or ⊲⊳ ′ , or ∼ ′ ? We de ne the following query, for any relation ∈ {≻, , ∼, ⊲⊳}:

CP CP∧ CP⋫ CP∧⋫ ≪ ≪ ≪ ≪ k-CP k-CP∧ ≪ k-LPT k-LPT∧ ≪ k-CP⋫ k-CP∧⋫ ≪ ≪ ≪ CP lex (k-1)-CP (k-1)-CP∧ ≪ (k-1)-CP⋫ (k-1)-CP∧⋫ ≪ ≪ ≪ (k-1)-LPT (k-1)-LPT∧ ≪ CP lex -1 CPnet ≪ CPnet L L ′′ : L is strictly more expressive than L ′ L ≪ L ′′ : L is strictly more succinct than L ′ For > 2.
Boxes contain languages that are equally expressive.

✘✘ ✘✘ ✘✘ ⊤ ⊤ ⊤ ✓ ✓ R , ∈ { , ≻, ⊲⊳} ✘✘ ✘✘ ✘✘ ✘• ✘• ✘ ✓ ✓ ✓ ∼ ✘✘ ✘✘ ✘✘ ⊥ ⊥ ⊥ ✓ ✓ ✘✘ ✘• ✘• ✓ ✘• ✓ ✓ ✘• ✓ ✓ ✓ ✓ ✓ ✓ . ∃ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ⊤ ∃ ✘✘ ✘✘ ✘✘ ⊤ ⊤ ⊤ ⊤ ⊤ . . ∃, . ∃ ✘✘ ✘✘ ⊤ ⊤ ✓ ✓ . , . ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ . ., ., . . ✘✘ ✘✘ ✘✘ ✓ ✓ ✓ ✓ ≻ ✘✘ ✘✘ ✘✘ ✓ ✓ ✓ ✓ ✓ ≻ ✘✘ ✘✘ ✘✘ ✓ ✓
Each column corresponds to one sub-language of CP. They are sorted in order of decreasing expressiveness from left to right, except when columns are separated by double lines. For each query and sub-language: ⊤ = always true for the language ; ⊥ = always false for the language; ✓ = polytime answer; ✘ = NP-complete query; ✘• = NP/coNP-hard query; ✘✘ = PSPACE-complete query.

Table 1: Complexity of queries.

Given formula , alternatives ≠ ′ , is it the case that ′ ?

For LP-trees, in order to compare alternatives and ′ , one only has to traverse the tree from the root downwards until a node that decides the pair is reached, or up to a leaf if no such node is encountered: in this case and ′ are incomparable. Note that checking if a node decides the pair, and checking if a rule at that nodes applies to order them, can both be done in polynomial time.

P 11.
is in P for LPT for ∈ {≻, ,∼,⊲⊳ }.

Tractability of comparisons, except in some trivial cases, comes at a heavy price in terms of expressiveness: is tractable for CP-nets when the dependency graph is a polytree [4, Theorem 14], but [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF]Theorems 15,[START_REF] Domshlak | Hard and soft constraints for reasoning about qualitative conditional preferences[END_REF] prove that is already NP-hard for the quite restrictive language of binary-valued, directed-path singly connected CP-nets, which are acyclic. [24, Prop. 7, Corrolary 1] prove that , ≻ , ⊲⊳ and ∼ are PSPACE complete for 1-CP⋫∧ and for linearisable, locally complete formulas of 1-CP⋫. More precise hardness results for acyclic CP-nets are also proved by [START_REF] Lukasiewicz | Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting[END_REF]. Proposition 12 completes the picture.

P

12. ≻ and ⊲⊳ are NP-hard for the language of fully acyclic CP-nets, and tractable for polytree CP-nets. ∼ is easy for 1-CP lex .

Comparing theories. Checking if two theories yield the same preorder can be useful during the compilation process. We say that two formulas and ′ are equivalent if they represent the same preorder, that is, if and ′ are identical; we then write ≡ ′ .

Given two formulas and ′ , are they equivalent? Consider a formula ∈ CP, two alternatives , ′ , and let ′ = ∪ { ≥ ′ }: clearly ′ ′ , thus ≡ ′ if and only if ′ . Therefore, if language L is such that adding CP statement ≥ ′ to any of its formulas yields a formula that is still in L, then has to be at least as hard as for L. This is the case of CP. The problem remains hard for 1-CP⋫, because it is hard to check the equivalence, in propositional logic, of the conditions of statements that entail a particular swap ≥ ′ . Example 9. Consider three attributes , and with respective domains { , ¯ }, { , ¯ } and { 1 , 2 , 3 }. Consider two CP statements = ¯ : 1 ≥ 2 and ′ = : 2 ≥ 3 , and let = { , ′ , : 1 ≥ 3 }. Because of statements and ′ we have ¯ 1 ≥ ¯ 2 ≥ ¯ 3 ; also, 1 ≥

3 because of statement : 1 ≥ 3 . Hence, for any ∈

× , if |= ∨ ( ¯ ) then 1 ≥ 3 . Thus ≡ { , ′ } ∪ { ∨ ( ¯ ) : 1 ≥ 3 } ≡ ∪ { : 1 ≥ 3 }. P 13.
is coNP-hard for 1-CP⋫∧ , and for 1-LPT∧, both restricted to binary attributes.

As usual, comparing two formulas is easier for languages where there exists a canonical form. This is the case of CP-nets, as shown by [START_REF] Koriche | Learning conditional preference networks[END_REF]Lemma 2]; their proof makes it clear that the canonical form of any CP-net can be computed in polynomial time. Hence:

P 14.
is in P for CP-net.

also becomes tractable if some form of canonicity is imposed for the conditions of the rules in an LP-tree; this is because, as with CP-net, it is possible to de ne a canonical form for the structure, by imposing that the labels of the node be as small as possible -which may lead, in some cases, to splitting some nodes.

Top alternatives. Given a set of alternatives and some integer , we may be interested in nding a subset ′ of that contains "best" alternatives of , in the sense that for every ∈ ′ , for every ′ ∈ \ ′ it is not the case that ′ ≻ . Note that such a set must exist, because ≻ is acyclic. The T query is usually de ned for totally ordered sets; a de nition suited to partial orders is given in [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] (where it is called ordering), we adopt this de nition here:

T

Given ⊆ X, < | |, and , nd 1 , 2 , . . . , ∈ such that for every ∈ 1, . . . , , for every ′ ∈ , if ′ ≻ then ′ ∈ { 1 , . . . , -1 }.

Note that if 1 , 2 , . . . , is the answer to such query, if 1 ≤ < ≤ , then it can be the case that ⊲⊳ , but it is guaranteed that ⊁ : in the context of a recommender system for instance, where one would expect alternatives to be presented in order of non-increasing preference, could be safely presented before . [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] prove that is tractable for acyclic CP-nets for the speci c case where | | = 2. More generally, ≻ queries can be used to compute an answer to a query (by asking ≻ queries for every pair of elements of , the number of such pairs being in Θ(| | 2 )). However, [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] shows that an upper approximation of ≻ is su cient, and proves that such an approximation can be obtained in time polynomial in | | for a restricted class of lexico-compatible formulas of 1-CP∧ [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]Th. 5]. We prove that this result does indeed hold for the full class of lexicocompatible formulas of 1-CP∧. The query is also tractable for LPT.

P

15. can be answered in time which is polynomial in the size of and the size of for k-lexico-compatible formulas (for xed ); and for LPT.

Optimization. Instead of ordering a given set, we may want to nd a globally optimal alternative. Following [START_REF] Goldsmith | The Computational Complexity of Dominance and Consistency in CP-nets[END_REF], given , we say that alternative is:

• weakly undominated if there is no ′ ∈X such that ′ ≻ ;

• undominated if there is no ′ ∈ X, ′ ≠ , such that ′ ; • dominating if for every ′ ∈ X, ′ ; • strongly dominating if for every ′ ∈ X with ′ ≠ , ≻ ′ .

Note that is strongly dominating if and only if it is dominating and undominated; and that if is dominating or undominated, then it is weakly undominated. This gives rise to several types of queries:

[ | ] ( | ) Given , is there a [weakly | strongly] (undominated | dominating) alternative? [ | ] ( | ) Given , , is a [weakly | strongly] (undominated | dominating) alternative?
All these queries are easily shown to be tractable for LPT. The problem has been shown to be tractable for CP-nets [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] and for 1-CP⋫ [START_REF] Goldsmith | The Computational Complexity of Dominance and Consistency in CP-nets[END_REF]. This can be generalized:

P 16.
is in P for CP.

The existence of a weakly undominated alternative is trivially true for CP (in any nite directed graph, at least one vertex has no "strict" predecessor). Linearisability also ensure that there is at least one undominated alternative.

For CP-nets, [START_REF] Boutilier | CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] give a polytime algorithm that computes the only dominating alternative when the dependency graph is acyclic; in this case, this alternative is also the only strongly dominating one and the only undominated one, since the CP-net is linearisable: this implies that ∃, . ∃, ∃, .

, and . are tractable for acyclic CP-nets. [START_REF] Goldsmith | The Computational Complexity of Dominance and Consistency in CP-nets[END_REF]Prop. 8,9 and 11] prove that . , , .

, ∃ and . ∃ are PSPACE-complete for 1-CP⋫, and their reductions for proving hardness of . , , .

indeed yield formulas of 1-CP⋫∧. NP-hardness of ∃ for 1-CP⋫∧ is proved by [START_REF] Domshlak | Hard and soft constraints for reasoning about qualitative conditional preferences[END_REF],

Cuts. Cuts are sets of alternatives that are at the same "level" with respect to . For rankings de ned with real-valued functions, cuts are de ned with respect to possible real values. In the case of preorders, we de ne cuts with respect to some alternative : given ∈ CP, for any ∈ {≻, }, for every alternative , we de ne

• CUT , ( ) = { ′ ∈ X | ′ ≠ , ′ } .
Following [START_REF] Fargier | A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams[END_REF], we de ne two families of queries: Given , , count the elements of CUT , ( ) Given , , return an element of CUT , ( ) (or that it is empty)

P 17.
is tractable for CP. ≻ and ≻ are PSPACE-hard for 1-CP⋫∧. For CP lex , ≻ is equivalent to and is tractable. ≻ is tractable for LP-trees.

CONCLUSION

The literature on languages on CP statements has long focused on statements with unary swaps. Several examples in Section 4 show that this strongly degrades expressiveness. We have introduced a new parameterised family of languages, CP lex , which permits to balance expressiveness against query complexity: the lower is, the less expressive the language is, but the faster answering most queries will be. Table 1 shows that comparison queries seem to resist tractability, even for CP lex , but queries like the query may be su cient in many applications. Tractability of the query relies on the existence of canonical form: it is the case when the language enforces a structure like a dependency graph or a tree, and when the conditions of the statements are restricted to some propositional language with a canonical form.

We have not studied here transformations, like conditioning or other forms of projection for instance. Some initial results on projections can be found in [START_REF] Besnard | Variable forgetting in preference relations over combinatorial domains[END_REF]. This is an important direction for future work, as well as properties of the various languages studied here with respect to machine learning.

A PROOFS P 1. Let be an LP-tree over X, then as de ned above is a preorder. Furthermore, is a linear order if and only if 1) every attribute appears on every branch and 2) every preference rule speci es a linear order.

P

. By de nition, is re exive. For transitivity, the proof given by [START_REF] Booth | Learning various classes of models of lexicographic orderings[END_REF] is for a restricted family of LP-trees, so we recast it here for our more general family of LP-trees. Suppose that ′ ′′ and , ′ , ′′ are distinct. There must be a node at which { , ′ } is decided, let be the set of attributes that labels , then = ′′ [Anc( )] and ≥ = ≥ ′ is transitive (it is a preorder) thus [ ] ≥ ′′ [ ] hence ′′ . If ≠ ′ , note that both nodes are in the unique branch in that corresponds to ′ , so one of , ′ must be above the other. Suppose that is above ′ , then, it must be the case that ′′ . The case where ′ is above is similar. For the second part of the proposition, suppose rst that every attribute appears on every branch and that every preference rule speci es a linear order: we will show that is antisymmetric and connex. For antisymmetry, consider distinct alternatives , ′ ∈ X: because every attribute appears on every branch, there must be a node , labelled with some ⊆ X, that decides { , ′ }, and a unique rule : ≥ at such that [NonInst( )] = ′ [NonInst( )] |= ; ≥ must be a linear order over , so either [ ] > ′ [ ] and ≻ ′ , or ′ [ ] > [ ] and ′ ≻ : is connex and antisymmetric. For the converse, assuming that either there is some branch where some attribute does not appear, or that there is some rule at some node that does not de ne a linear order, it is not di cult to de ne two distinct alternatives that cannot be compared with . P 2. For a xed ∈ N, checking if a formula ∈ CP is -lexico-compatible is coNP-complete.

P

. For membership in coNP: a certi cate that some given is not lexico-compatible is a branch of a tree built using the algorithm above where failure occurs. coNP-completeness can be proved using the same reduction of 3 used by [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]Prop. 24] to prove that checking cuc-acyclicity is coNP-hard. Consider clauses 1 , . . . , over binary attributes 1 , . . . , . Let X = { 1 , . . . , , 0 , 1 , . . . , }, where the s are new binary attributes. De ne

= { | : -1 ≥ ¯ -1 | ∈ , 1 ≥ ≥ } ∪ {| 0 : ≥ ¯ }.
and consider some complete LP tree over set of attributes X. Every attribute appears in the free part of at least one rule of , thus cannot be at the root of any complete LP tree that is compatible with . On the other hand, any of the 's can be at the root, or at any level, in any branch of . Suppose now that 1 ∧ . . . ∧ is satis able: let be an instantiation of 1 , . . . , that satis es this CNF, and consider a branch of where all the s have the same value as in : at every node in such a branch, for every , inst( ) is consistent with the condition of at least one rule which has as free part; therefore, no ordering of the s in such a branch can be compatible with condition 1 in Proposition 18. On the other hand, if 1 ∧ . . . ∧ is unsatis able, then it is not difcult to see that it is possible to build in such a way that the conditions of Proposition 18 are satis ed w.r.t. , by taking, for instance, the s for the nodes at the rst levels of : then, since

Figure 1 :

 1 Figure 1: An LP-tree equivalent to the set of CP-statements of Example 2.

Figure 2 :

 2 Figure 2: Rel. expressiveness and succinctness

  [Anc( )] = ′ [Anc( )], and there is one rule : ≥ such that [NonInst( )] = ′ [NonInst( )] | = and [ ] ≥ ′ [ ].Similarly, let ′ be the node at which { ′ , ′′ } is decided, let ′ be the set of attributes that labels ′ , then [Anc(′ )] = ′ [Anc( ′ )],and there is one rule′ : ≥ ′ s.t. ′ [NonInst( ′ )] = ′′ [NonInst( ′ )] | = ′ and ′ [ ′ ] ≥ ′ ′′ [ ′ ]. If = ′ , then [Anc( )] = ′ [Anc( )]

  ′ [ ] = ′′ [ ], and [ ] ≠ ′ [ ], thus decides { , ′′ }; moreover, since NonInst( ) ⊆ NonInst( ′ ), ′ [NonInst( )] = ′′ [NonInst( )] |= , and [ ] ≥ ′ [ ] = ′′ [ ]; hence

  Algorithm 1: Build complete LP tree Input: ∈ CP; ∈ N; Output: ∈ k-LPT, complete, s.t.

	⊇	, or FAILURE;
	(1) ← {an unlabelled root node};
	(2) while contains some unlabelled node:
	(a) choose unlabelled node of ;
	(b) ( , ≥) ← chooseA ribute( , , );
	(c) if = FAILURE then STOP and return FAILURE;
	(d) label with ( , ≥);
	(e) if Anc( ) ∪ ≠ X, for each ∈ : add new unlabelled
	node to , attached to with edge labelled with ;
	(3) return .

or =

), travelling by plane ( = ) or by car ( = ¯ ). I would rather go now, irrespective of the other attributes: ⊤ |{ } : ¯ ≥ .

The formula | : ≥ ′ is written : > ′ [ ] by[START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF].

Actually,[START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] proves that ( , ′ ) is in the transitive closure of * if and only there is such a worsening sequence from to ′ , but adding the re exive closure to this transitive closure does not change the result, since we can add any pair ( , ) to, or remove it from, any sequence of worsening swaps without changing the validity of the sequence.

Such sets of CP-statements are often called consistent in the standard terminology on CP-nets, but we prefer to depart from this de nition which only makes sense when one asserts that should indeed represent a strict partial order.

In the literature, the symbol ⊲ is sometimes used to represent an importance relation between attributes; and, as explained by[START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], statement | : ≥ ′ is a way to express that attributes in Var( ) are more important than those in (when is true).

This is full acyclicity in[START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF].

Strictly speaking, for LPT ⊆ CP to hold, we can add the possibility to augment every formula in CP with a tree structure.

This de nition generalises conditionally acyclic formulas of[START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], which are the formulas of CP lex 1 .

This query is often called consistency.

∧. . . ∧ is unsatis able, in every branch of the tree there must be one clause that is not satis ed by the corresponding instantiation of the s, so none of the conditions of the corresponding rules | : -1 ≥ ¯ -1 is satis ed; then attribute -1 can be chosen for the label of the node at the next level, then -1 , and so on. . .

ACKNOWLEDGMENTS

We thank anonymous referees for their valuable comments on previous versions of this paper. This work has bene ted from the AI Interdisciplinary Institute ANITI. ANITI is funded by the French "Investing for the Future -PIA3" program under grant agreement ANR-19-PI3A-0004. This work has also been supported by the PING/ACK project of the French National Agency for Research, grant agreement ANR-18-CE40-0011.

P

3. Given ∈ CP and some ∈ N, suppose that chooseA ribute is -compatible, then ∈ CP lex if and only if the algorithm above returns some ∈ k-LPT such that ⊇ ; otherwise, it returns FAILURE.

In order to prove Proposition 3, we rst state and prove the following result, similar to that of [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]Prop. 13], which shows that it is possible to check in polynomial time, given ∈ CP and some complete ∈ LPT, if extends . For ease of presentation, we introduce the following de nition: De nition 4. Statement | : ≥ ′ is relevant at node of some LP-tree if Var( ) ∩ Anc( ) = ∅, and ∧ inst( ) |= ⊥, and Var( ) ∩ Var( ) ≠ ∅.

Informally, | : ≥ ′ is relevant at node if it sanctions some swap ( , ′ ), with ∈ Var( ) such that | = and ∈ , which may be decided at .

P 18 (G P . 13 [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF]). Let ∈ CP and let be some complete LP-tree. Then ⊇ if and only if for every node ∈ , for every | : ≥ ′ ∈ that is relevant at , the following two conditions hold:

(1) ∩ Anc( ) = ∅; and

(2) for every rule : ≥ ∈ CPT( ) such that ∧ |= ⊥, for every ∈ Var( ) such that ∧ ∧ ∧ inst( ) |= ⊥, for every ∈ Var( ) \ (Var( ) ∪ ∪ Var( )), for every 1 , 2 ∈ , it must be the case that 1 [Var( )] >

P .

Let us rst prove that conditions 1 and 2 are necessary for every node of labelled with and every statement | : ≥ ′ ∈ that is relevant at , assuming that ⊇ . Let = X \ (Var( ) ∪ ∪ Var( )). Suppose rst that there is some ∈ ∩ Anc( ): there must be some node 0 between the root and in such that is in the label of 0 . Choose some ∈ Var( ),

which is impossible since is a complete LP-tree, and so, by de nition, every rule at every node assigns a linear order. This proves that ∩ Anc(

′ , and the pair { 1 , 2 ′ } is decided in at with the rule : ≥ , so it must be the case that 1 [Var( )] > Let us now prove that the condition is su cient: it is in fact sufcient to prove that, if the condition above holds, then for every statement | : ≥ ′ ∈ , for every pair of alternatives { , ′ } sanctioned by the statement, it is the case that ′ . We must have that = 1 and ′ = 2 ′ for some ∈ Var( ) such that | = , some 1 , 2 ∈ , some ∈ X \ (Var( ) ∪ ∪ Var( )).

Let be the node that decides { , ′ } in , let us prove that | : ≥ ′ is relevant at . That Var( ) ∩ Anc( ) = ∅ follows from the fact that { , ′ } is not decided at some other node between the root and ; also, the common part of and ′ must be consistent with inst( ) (otherwise, the pair would have taken another branch on the tree), so ∧ inst( ) |= ⊥, and is a model of , so ∧ inst( ) |= ⊥; there remains to prove that Var( ) ∩ Var( ) ≠ ∅. Suppose rst that 2 = 1 , then it must be the case that [Var( )] ≠ ′ [Var( )] (since { , ′ } is decided at , so Var( ) ∩ Var( ) ≠ ∅: | : ≥ ′ is indeed relevant at , and condition 1 implies that ∩Anc( ) = ∅. Suppose now that 2 ≠ 1 , let ′′ = 1 ′ , let ′ be the node that decides { , ′′ }, from what we have just seen, in particular that ∩ Anc( ′ ) = ∅ we can conclude that ′ also decides { , ′ }, thus = ′ : it follows that ∩ Anc( ) = ∅, thus, since decides { , ′ }, it must be the case that Var( ) ∩ Var( ) ≠ ∅: statement | : ≥ ′ is again relevant at . Consider now the unique rule :

Let ∈ CP, suppose that chooseA ribute is -compatible, that the algorithm above terminates without failure on , , and returns some complete -LP-tree , then ⊆ .

P . Let

∈ , let | : ≥ ′ ∈ that is relevant at , we only need to prove that conditions 1 and 2 in Proposition 18 hold.

Let us rst prove that ∩ Anc( ) = ∅. Let ′ be any node between the root and , excluding ; it is labelled with some ′ ⊆ X and a linear order ≥ ′ over ′ that have been returned by chooseA ribute when called at ′ . We know that ∧ inst( ) |= ⊥, so, since inst(

and Var( ) ∩ Anc( ) = ∅, we also have that ′ ∩ Var( ) = ∅; thus, according to condition ?? that must be veri ed by chooseA ribute, it must be the case that ∩ ′ = ∅. This holds for every label of every node above , hence ∩ Anc( ) = ∅.

Let us now prove that condition 2 holds. Since the algorithm returns LP-trees with no unlabelled edge, it can be rewritten as follows:

2'. for every ∈ Var( ) such that | = and ∧ inst( ) |= ⊥, for every ∈ Var( ) \ (Var( ) ∪ ∪ Var( )), for every 1 , 2 ∈ , it must be the case that

We know that Var(

and ∧ |= ⊥ (because |= ), thus, according to condition ?? in the speci cation of chooseA ribute, it must be the case that > ′ , that is

Let ∈ CP, let ∈ N, let be some complete -LPtree, with no uninstantiated edge, such that ⊆ . Let be some node of , and let ( ) be the subtree of rooted at . Suppose that, when called at , chooseA ribute returns a pair ( , ≥) di erent than the one that labels . Then ∈ ′ , where ′ is a new -LP-tree obtained by replacing ( ) in with a new subtree as follows:

• is replaced with a new node ′ , labelled with ( , ≥); in the sequel, in order to avoid confusion, we denote ≥ ′ this ordering associated with returned by chooseA ribute; • we create copies of ( ), each attached to ′ with an edge labelled with some ∈ ; • for each node in one of these copies, in the branch below ′ corresponding to , we do as follows, where ( , ≥ ) is the set of attributes and the associated linear ordering that label :

all subtrees below that correspond to paths incompatible with are deleted; -if ⊆ , then there remain only one subtree of , we can safely remove node ; -otherwise, we replace ( , ≥ ) with ( \ , ≥ | ), where ≥ | is the linear order over \ de ned as follows: for every

P . We prove rst that ′ ∈ k-LPT: • the nodes not in ( ) are unchanged;

• since is returned by chooseA ribute, | | ≤ ;

• the set of attributes that labels any node below ′ is diminished, since the attributes in are removed. Thus, since ∈ k-LPT, ′ ∈ k-LPT.

Consider now a swap ( , ′ ) sanctioned by rule | : ≥ ′ ∈ , and let be the node in where { , ′ } is decided. If ∉ ( ), then ′ ′ if and only if ′ , and extends , thus ′ ′ . Let us now consider the case where ∈ ( ), and let ( , ≥ ) be the label of . We will consider two subcases.

Suppose rst that

, thus there is in the subtree that replaces ( ) in ′ a node ′ , with inst( ′ ) compatible with , obtained from by removing attributes in ∩ , thus getting new set of attributes = \ , and by conditioning ≥ with . { , ′ } is not decided at ′ , nor at any other node above ′ , it is now decided at ′ , and [ ] and ′ [ ] are of the form ˜ and ˜ ′ , where ˜ = [ ]; since ′ , it must be the case that ˜ > ˜ ′ , thus > | ′ . Therefore ′ ′ . Let us nally consider the case where [ ] ≠ ′ [ ]: { , ′ } is now decided at ′ . Since { , ′ } is decided at in , we know that Var( ) ∩ Anc( ) = ∅ and that ∧ inst( ) |= ⊥, thus, since is above in , and since inst( ) = inst( ′ ), we have that ∧ inst( ′ ) |= ⊥. Therefore, | : ≥ ∈ ( ′ ). Recall that has been returned by chooseA ribute called at ′ : thus, if we had Var( ) ∩ = ∅, we would also have ∩ = ∅, which is impossible because, since ( , ′ ) is sanctioned by | : ≥ , [ \ ( ∪ Var( )] = ′ [ \ ( ∪ Var( )], thus the pair would not be decided at ′ . But, since Var(

they are compatible with respectively and ′ (since and ′ respectively extend and ′ ), and [ \ ( ∪Var( )] = ′ [ \ ( ∪ Var( )], thus it must be the case, according to condition ?? in the speci cation of chooseA ribute, that > ′ ′ , thus ≻ ′ ′ . P P 3. Suppose rst that the algorithm succeeds and returns a -LP-tree: lemma 1 proves that ⊆ , and we have mentioned that all labels returned by chooseA ribute have no more than attributes, so it is in k-LPT, so ∈ CP lex . Now, suppose that ∈ CP lex : there is some -LP-tree such that ⊇ . Consider the execution of the algorithm with and as inputs. Let be the rst node such that chooseA ribute returns a pair ( , ≥) that is not in at : then lemma 2 proves that there is some ′ ∈ k-LPT that is equal to except for the subtree rooted at , and that is equal to for the part built before , and that has ( , ≥) at : this shows that the algorithm cannot run into a dead end.

P

5. CP = ∈N k-CP and, for every ∈ N:

Restricting to conjunction of literals does not induce a loss in expressiveness because, given a statement | : ≥ ′ , it is possible to compute a DNF logically equivalent to , and then consider a set of statements, each statement having one disjunct of the DNF as conditioning part. Example 3 prove that CP 1-CP. Example 4 proves that 1-CP 1-CP⋫.

P

10. can be checked in polynomial time for LPT.

P

. This is because ∈ LPT is linearisable if and only for every rule : ≥ at every node, ≥ is antisymmetric.

P

12. ≻ and ⊲⊳ are NP-hard for the language of fully acyclic CP-nets, and tractable for polytree CP-nets. ∼ is easy for 1-CP lex .

Proposition 12 is proved using these simple observations: ; if the answer is no, then one can ask to order { , ′ }: if the answer is that ′ , then we have the answer to the initial query; if the answer is that ′ , since we know that and ′ are not incomparable, it must be the case that ′ . The remaining properties are elementary.

That ≻ is NP hard for the language of fully acyclic CP-nets follows from the fact that is hard for this language [4, Theorems 15, 16] and from property 3 in lemma 3. Property 2 shows that ⊲⊳ too is NP hard for this language because is easy for this language [4, Theorems 5] and is hard. These two queries are tractable for polytree CP-nets because is (property 1 in lemma 3). ∼ is easy for 1-CP lex because lexico-compatible formulas are linearisable.

is coNP-hard for 1-CP⋫∧ , and for 1-LPT∧, both restricted to binary attributes.

Given a propositional language P we de ne P ∨ to be the set of nite disjunctions of formulas in P, and: 1-CP⋫P is 1-CP⋫ restricted to those statements such that the condition is in P 1-LPTP is 1-LPT restricted to those LP-trees such that the condition of every rule is in P.

The proof of the proposition is based on the following lemma, which a formalizes the intuition suggested by Example 9. if and only if 1 = 2 , 1 = , 2 = ¯ and 1 | = ′ . Thus ≡ ′ if and only if for every ∈ X, |= ⇔ |= ′ , i for every ∈ X, ¯ ⇔ ′ ¯ , if and only if ≡ ′ . Similarly, we can de ne two linear 1-LP-trees and ′ as follows: the top | X | nodes are labelled with attributes from X, in any order and with no rule; then there is one node labelled with , and the same preference rules as above.

P

15. can be answered in time which is polynomial in the size of and the size of for k-lexico-compatible formulas (for xed ); and for LPT. The fact that the query is tractable for LPT in this case is a simple consequence of the fact that ≻ is tractable for LPT. For -lexico-compatible formulas, given some ∈ CP known to be -lexico-compatible, and given a pair of alternatives { , ′ }, we can run the algorithm proposed in Section 3.6 that builds a complete LP tree that extends , but build one branch only, the one that corresponds to the pair { , ′ }, as long as the chosen attributes have equal values for and ′ : when reaching a node where the chosen set of attributes si such that [ ] ≠ ′ [ ], the node decides the pair, and and ′ can be ordered accordingly, as in the case of LP trees:

then it cannot be the case that ≻ ′ . The algorithm will not return FAILURE because is known to be -lexico-compatible. The branch has no more that | X | nodes, and there is, for xed , a polynomial number of possible labels to try at each node. is easy for CP: given and , in order to return an element of CUT , ( ), it is su cient to nd one statement in which sanctions an improving swap for .

Note that alternative is weakly undominated i CUT ≻, ( ) = ∅, i | CUT ≻, ( ) | = 0; therefore, ≻ and ≻ are at least as hard as , they are therefore PSPACE-hard for 1-CP⋫∧. For acyclic CP-nets, and more generally for cuc-acyclic CP theories, ≻ is the irre exive part of , thus ≻ is equivalent to and is easy. Finally, ≻ is tractable for LP-trees: given some , when going down some LP-tree in the branch that corresponds to , it is possible, at each node encountered, labelled with , to count the number of ′ in such that > [ ′ ] (according to the preference rule : ≥ at such that | = ), and to multiply this number by the sizes of the domains of the attributes that have not been encountered yet; adding these sums of products along the branch will give the number of alternatives such that ′ ≻ .