Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models

1 Introduction

Preferences are considered in many different fields such as recommender systems and human-computer interaction [Chen and Pu, 2007; Trabelsi et al., 2013], databases [Agrawal and Wimmers, 2000; Kießling, 2002] and multi-objective decision making and social choice [Arrow and Raynaud, 1986; Lang, 2002; Sandholm and Boutilier, 2006]. They are used to, e.g., find optimal decisions, solutions or items that satisfy the wishes or needs of a user or a group. In order to reason with preferences, typically assumptions are made on the form of the relation used to model the user preferences. In this paper we restrict our considerations to lexicographic models, and we consider preference inference, which involves reasoning about the the whole set of preference models that are consistent with the input preferences, as in [Kohli and Jedidi, 2007; Wilson, 2014]; this contrasts with work that focuses on learning one lexicographic model that fits best with the given preferences [Booth et al., 2010; Br¨auning and H¨ullermeier, 2012; Dombi et al., 2007; Yaman et al., 2010].

Preference inference aims to overcome gaps of knowledge in the user preferences by analysing the given preferences and deciding whether another preference statement can be deduced. Since in this paper we allow negations of statements, preference inference can be reduced to testing consistency of a set of preference statements. We define a property, strong compositionality, that is satisfied by many natural types of preference statements and enables a simple greedy algorithm for testing consistency.

Fast computation is essential in many applications; we give a concrete instance L′pqT of a preference language that allows polynomial computation. This can represent a relatively expressive form of preference input. It can express preferences between a pair of complete assignments to a set of variables, and, more generally, between partial assignments to just a subset of the variables, allowing ceteris paribus assumptions or stronger implications on the values of other variables. We also allow non-strict statements, two forms of strict preference statements and can represent certain negated statements.

Previous work on preference inference based on standard lexicographic models have considered more restricted preference languages. Wilson [2014] considered only non-negated non-strict statements, which can only express that one assignment is at least as good as another (or equivalent). Kohli and Jedidi [2007] considers only non-negated strict statements, which can only express that one complete assignment is strictly better than another. In [Wilson et al., 2015a], preference statements are comparisons of complete assignments, and fixed value orders for the variables are given.

Other work on preference inference includes that based on weighted sum models [Wilson et al., 2015b; Montazery and Wilson, 2016], on hierarchical models [Wilson et al., 2015a], conditional lexicographic models [Wilson, 2009]; Pareto orders [George and Wilson, 2016], and on general strict total orders, as in e.g., work on conditional preference structures such as [Boutilier et al., 2004]. While lexicographic models prevent tradeoffs between variables, they usually allow better complexity results for general preference languages.

Given a set of preference inputs and a set of alternatives, there are several natural notions of optimal set; for instance being undominated with respect to the induced preference relation; or being possibly optimal, i.e., optimal in at least one model. We establish relationships between the different notions of optimality. For preference language L′pqT , we analyse the running times and set relations theoretically and experimentally, illustrating the efficiency of the algorithms.

The paper is organised as follows: Section 2 gives basic definitions. The concepts of inference, consistency and strongly compositional statements are investigated in Section 3. Section 4 introduces languages LpqT and L′pqT and an algorithm to decide consistency in this context. In Section 5, different notions of optimality are compared for general preference languages together with a discussion of computational methods and complexity results for L′pqT . The last section concludes. A longer version of this paper including proofs and additional comments can be found under [Wilson and George, 2017].

2 LexModels, Composition and Extension

In this section, we give some basic definitions; in particular, we define lexicographic models, along with a natural composition operation and extension relation, that are important in our approach. A lexicographic model has an associated ordering of (some of the) variables, along with value orderings for each such variable. This generates a (lexicographic) ordering relation, by first comparing outcomes α and β on the first (i.e., most important) variable Y ; only if α(Y ) = β(Y ) is the next most important variable considered.

Throughout the paper we consider a fixed set V of n variables, where for each X ∈ V , D(X) is the set of possible values of X. For subset of variables A ⊆ V let A = ∏X∈A D(X) be the set of possible assignments to A. For X ∈ V , we abbreviate {X} to X (which is essentially D(X)). An outcome is an element of V , i.e., an assignment to all the variables. For outcome α and subset U of V , we define α(U) to be the tuple in U generated by projecting (i.e., restricting) α to U. These definitions describe a decision scenario over a set of alternatives given by different features. Consider for example the choice between different flight connections. A set of variables to describe the flight connections could be V = {airline, time, class}. The variable domains are then given by D(airline) = airline = {KLM, LAN}, D(time) = {day, night} and D(class) = {economy, business}. Then projection of the outcome α = (KLM, day, economy) to the variables U = {airline, class} is given by α(U) = (KLM , economy).

Define G to be the set of lexicographic models (over the set of variables V ); a lexicographic model or lex model, π (over V ), is defined to be a (possibly empty) sequence of the form (Y1,≥Y1 ), . . . , (Yk,≥Yk ), where Yi (i = 1, . . . , k) are different variables in V , and each ≥Yi is a total order on Yi. The associated relation ≽π ⊆ V ×V is defined as follows: for outcomes α and β, α ≽π β if and only if either (i) for all i = 1, . . . , k, α(Yi) = β(Yi); or (ii) there exists i ∈ {1, . . . , k} such that for all j < i, α(Yj) = β(Yj) and α(Yi) >Yi β(Yi) (i.e., α(Yi) ≥Yi β(Yi) and α(Yi) ̸= β(Yi)). Thus ≽π is a total pre-order on V , which is a total order if k = n = |V |.

The corresponding strict relation ≻π is given by α ≻π β if and only if there exists i ∈ {1, . . . , k} such that α(Yi) >Yi β(Yi) and for all j < i, α(Yj) = β(Yj). The corresponding equivalence relation ≡π is given by α ≡π β if and only if for all i = 1, . . . , k, α(Yi) = β(Yi). Thus, α ≡π β if and only if α(Vπ) = β(Vπ), where Vπ = {Y1, . . . , Yk} is set of the variables involved in π. Consider lexicographic models π =

(airline,KLM > LAN), (time, day > night) and π′ = (class, economy > business), (time, night > day) for the previous example of flight connections. In π the choice of airline decides which connection is preferred; only if these are the same, is the flight time considered. π′ first compares the classes; only if these are the same, are the flight times considered. For outcomes α = (KLM, day, economy), β = (KLM, night, business) and γ = (LAN, day, economy) we have α ≻π β ≻π γ and α ≡π′ γ ≻π′ β.

Composition of lexicographic models: We define an important composition operation on lex models, which can be shown to be associative. Let π = (Y1,≥Y1 ), . . . , (Yk,≥Yk ), and π′ = (Z1,≥Z1 ), . . . , (Zl,≥Zl ) be two lexicographic models. Let π′′ be the sequence π′ but where pairs (Zi,≥Zi ) are omitted if Zi ∈ Vπ. Define lex model π ◦ π′ to be π followed by π′′ . Note that Vπ◦π′ = Vπ ∪ Vπ′ .

Definition 1 For lex models π and π′ in G we say that π′ extends π if π′ ̸= π and the sequence π′ begins with π. We then write π′ ⊐ π, and write π′ ⊒ π to mean that π′ extends or equals π. This holds if and only if there exists a lex model π′′ such that π′ = π ◦ π′′ .

The composition of the two previously defined lex models is π ◦ π′ = (airline,KLM > LAN), (time, day > night ), (class, economy > business) and π ◦ π′ ⊒ π.

3 Lexicographic Inference and Strongly Compositional Preference Statements

In this section we define lexicographic inference, which can also be expressed in terms of (lexicographic) consistency. We define a notion of strong compositionality, and show that this property enables a greedy algorithm for checking consistency, and hence for preference inference. More specifically, a preference statement ϕ is strongly compositional if the composition of two lex models satisfies ϕ whenever the second and some extension of the first satisfy ϕ.

Throughout this section, we assume some language L, and satisfaction relation |=⊆ G×L. Here, the language L is a set of preference statements and the relation |= describes when a lex model satisfies a statement. For example, we can consider the simple language LO = {α ≥ β | α, β ∈ V } with the satisfaction relation π |= α ≥ β ⇔ α ≽π β as described in the previous section. We extend the satisfaction relation to subsets Γ of L in the usual way: for Γ ⊆ L, define π |= Γ ⇐⇒ π |= ϕ for each ϕ ∈ Γ. If π |= Γ then we say that π satisfies Γ, or π is a [lexicographic] model of Γ (and similarly, for a single preference statement ϕ). We say that Γ is consistent, if there exists some π ∈ G satisfying Γ; otherwise, Γ is inconsistent. We will sometimes use negations of preference statements: when necessary we can always extend the language L and the relation |=, by defining π |= ¬ϕ ⇐⇒ π ̸|= ϕ, when ϕ ∈ L.

A key problem is to determine if a set Γ ⊆ L of preference statements is consistent. We will derive methods for determining this in Section 3.3.

Some Basic Preference Statements

For outcomes α, β ∈ V , we can define preference statements α ≥ β and α > β, where we define π |= α ≥ β ⇐⇒

α ≽π β, and π |= α > β ⇐⇒ α ≻π β. We also define preference statement α ≡ β, with π |= α ≡ β ⇐⇒ α ≡π β, which is if and only if π |= α ≥ β and π |= β ≥ α.

We have that π |= α ≥ β ⇐⇒ π ̸|= β > α, i.e., π |= ¬(β > α). So α ≥ β and ¬(β > α) are equivalent preference statements, in that they are satisfied by exactly the same set of lex models. Similarly, α > β and ¬(β ≥ α) are equivalent preference statements.

Consider the example of lex models π, π′ and outcomes α, β, γ as before. Then π |= α ≥ β and thus π ̸|= β > α. Also, π′ |= α ≡ γ, i.e., π′ |= α ≥ γ and π′ |= γ ≥ α.

3.1 Lexicographic Inference

We define the lexicographic inference relation Γ |= ϕ ⇐⇒ π |= ϕ for all π ∈ G such that π |= Γ. For instance, we have, for Γ ⊆ L and α, β ∈ V , Γ |= α ≥ β ⇐⇒ α ≽π β holds for all π ∈ G such that π |= Γ. Similarly, Γ |= α > β ⇐⇒ α ≻π β holds for all π ∈ G such that π |= Γ.

Lexicographic inference can be reduced to checking consistency, since we have Γ |= ϕ ⇐⇒ Γ ∪ {¬ϕ} is inconsistent; and Γ |= ¬ϕ ⇐⇒ Γ ∪ {ϕ} is inconsistent. Thus, Γ |= α ≥ β ⇐⇒ Γ ∪ {β > α} is inconsistent; and Γ |= α > β ⇐⇒ Γ ∪ {β ≥ α} is inconsistent.

Consider flight connections as before. Let Γ be the set of statements {α > β, β ≥ γ} with α, β, γ defined as in the previous section. Then the lex model π satisfies Γ, π |= Γ, and thus Γ is consistent. In fact, the only preference models that satisfy Γ are: π = (airline,KLM > LAN), (time, day > night), π′′ = (airline, KLM > LAN), (class, economy > business), and any extension of either of these two models. Thus for δ = (LAN , night , business), Γ |= γ > δ.

The Induced Relation |=∗ and Maximal Models

From the relation |= we also define the derived relation |=∗ as follows, where π ∈ G and ϕ ∈ L: π |=∗ ϕ if and only if there exists π′ ∈ G either extending or equalling π such that π′ |= ϕ. Thus, π |=∗ ϕ holds either if π satisfies ϕ or some extension of π satisfies ϕ. We extend the relation to sets of statements in the usual way: for Γ ⊆ L, define π |=∗ Γ if and only if π |=∗ ϕ holds for every ϕ ∈ Γ. The following lemma follows easily from the definitions.

Lemma 1 Let π, π′ ∈ G and Γ ⊆ L.

(ii) Suppose that π′ extends π. Then π′ |=∗ Γ⇒π |=∗ Γ.

Definition 2 We say that π ∈ G is a maximal model of Γ if π |= Γ and for all lex models π′ extending π we have π′ ̸|= Γ.

Clearly, for π ∈ G such that π |= Γ, either π is a maximal model of Γ or there exists a maximal model of Γ that extends π. Thus, if Γ is consistent there exists a maximal model of Γ. Analogously, we define a maximal |=∗ -model of Γ to be an element π ∈ G such that (i) π |=∗ Γ and (ii) there does not exist π′ extending π with π′ |=∗ Γ.

Consider preference statements Γ relating to flight connections α, β, γ as before. The lex model (airline,KLM > LAN) satisfies (airline,KLM > LAN) |=∗ Γ. The model (airline,KLM > LAN), (time, day > night), (class, business > economy) is a maximal model of Γ (and a maximal |=∗ -model of Γ).

3.2 Compositional and Strongly Compositional Preference Statements

We formulate a pair of properties of preference statements that have strong implications regarding lexicographic inference and optimality.

Definition 3 ((Strongly) Compositional) Let ϕ ∈ L. We say that ϕ is compositional if for all π, π′ ∈ G,

We say that ϕ is strongly compositional if for all π, π′ ∈ G,

For Γ ⊆ L, we define Γ to be compositional if every element of Γ is compositional. Similarly, we say that Γ is strongly compositional if every element of Γ is strongly compositional.

Instances of Strongly Compositional Statements

Although being strongly compositional might appear to be quite a restrictive assumption, it turns out that it is satisfied by many natural preference statements, as illustrated by the next proposition. First, we give a lemma which, roughly speaking, states that the property of being [strongly] compositional is closed under conjunction.

Lemma 2 Let Γ ⊆ L and let ψ ∈ L. Suppose that ψ is such that for all π ∈ G, π |= ψ ⇐⇒ π |= Γ. If Γ is compositional then ψ is compositional. If Γ is strongly compositional then ψ is strongly compositional and, for all π ∈ G, [π |=∗ ψ ⇐⇒ π |=∗ Γ and Γ is consistent].

Proposition 1 For any outcomes, α, β ∈ V , statements α ≥ β and α > β are strongly compositional, and, for π ∈ G, π |=∗ α ≥ β ⇐⇒ π |= α ≥ β. Also, if α ̸= β, π |=∗ α > β ⇐⇒ π |= α ≥ β.

In addition, given R ⊆ V × V , let ϕR be some statement satisfying: π |= ϕR if and only if ≽π⊇ R. Then ϕR is strongly compositional, and, for any π ∈ G, we have π |=∗ ϕR ⇐⇒ π |= ϕR

Here, the second half of Proposition 1 follows from the first using Lemma 2. Further important examples of strongly compositional statements will be discussed in Section 4.

A Characterisation of Consistency for Strongly Compositional Γ

The definitions immediately imply the following.

Lemma 3 Let Γ ⊆ L, and let π, π′ ∈ G.

• If Γ is strongly compositional then it is compositional.
• If Γ is compositional then π |= Γ and π′ |= Γ imply π ◦ π′ |= Γ.
• If Γ is strongly compositional then π |=∗ Γ and π′ |= Γ imply π ◦ π′ |= Γ.

The last point implies that, for strongly compositional and consistent Γ, if π |=∗ Γ then there exists a model of Γ either equalling or extending π. In fact we have:

Lemma 4 Suppose that Γ is strongly compositional, and let π be an element of G. Then [there exists π′ ∈ G with π′ ⊒ π and π′ |= Γ] if and only if [Γ is consistent and π |=∗ Γ].

Suppose that π′ satisfies strongly compositional Γ and that π is a maximal |=∗ -model of Γ. Since we have π ◦ π′ |=∗ Γ (because we have π ◦ π′ |= Γ) and π ◦ π′ ⊒ π, then the maximality of π implies that π = π◦π′ , and thus, π |= Γ. We also have that Vπ ⊇ Vπ′ . This implies the following theorem and corollary:

Theorem 1 If Γ is consistent and strongly compositional then every maximal |=∗ -model of Γ satisfies Γ. Also, if π and π′ are two maximal |=∗ -models of Γ then Vπ = Vπ′ .

Corollary 1 Let π be any maximal |=∗ -model of strongly compositional Γ. Then Γ is consistent if and only if π |= Γ.

3.3 Checking Consistency of a Set of Strongly Compositional Preferences

Corollary 1 shows that we can test consistency of strongly compositional Γ, by finding any maximal |=∗ -model π of it, and checking if π satisfies Γ. In this section we show how a maximal |=∗ -model of Γ can be constructed iteratively, starting from the empty model {}. We first check if {} |=∗ Γ. The following lemma shows that this is equivalent to Γ being |=∗ - consistent, which is a very weak property, i.e., it just requires that each element of Γ is (individually) consistent.

Lemma 5 Let Γ ⊆ L. Γ is |=∗ -consistent (i.e., there exists some π ∈ G with π |=∗ Γ) if and only if, for each ϕ ∈ Γ, ϕ is consistent. This also holds if and only if {} |=∗ Γ.

We say that π′ minimally extends π if π′ extends π and |Vπ′ | = |Vπ| + 1, i.e., π′ involves one more variable than π. The next lemma implies that in building a maximal |=∗ - model, we only need consider adding one variable at a time.

Lemma 6 π is a maximal |=∗ -model of Γ if and only if π |=∗ Γ and there exists no π′ minimally extending π such that π′ |=∗ Γ.

Starting with the empty model we grow a maximal |=∗ - model of Γ, by (iteratively) replacing the model with one minimally extending it and still |=∗ -satisfying Γ, if such a model exists. Otherwise, we have a maximal |=∗ -model π of Γ. By Corollary 1, we can test if Γ is consistent by checking π |= Γ.

For bounded domain size, testing consistency of strongly compositional Γ can be performed with polynomial number of tests of the form π |= ϕ or π |=∗ ϕ. For this algorithm to be efficient we need that each preference statement allows efficient tests of π |= ϕ and π |=∗ ϕ. In Section 4 we define languages that satisfy these properties.

4 Preference Languages LpqT and L′pqT

Here we show that certain relatively expressive compact preference languages are strongly compositional. This includes forms of the statements ϕR from Proposition 1, where R is a set of pairs of outcomes. In many natural situations, R can be exponentially large; in the languages discussed here, we are able to express certain exponentially large sets R compactly.

4.1 The Language LpqT

We will consider preference statements of the form p✄q ‖ T , where ✄ is either ≥, or ≫ or >, and P , Q and T are subsets of V , with (P ∪ Q) ∩ T = ∅, and p ∈ P is an assignment to P , and q ∈ Q is an assignment to Q. The statement p ✄ q ‖ T represents that p is preferred to q if T is held constant, i.e., any outcome α extending p is preferred to any outcome β that extends q and agrees with α on variables T . Formally, the semantics of this statement relates to the set ϕ∗ which is defined to be the set of pairs (α, β) of outcomes such that α extends p, and β extends q, and α and β agree on T, i.e., α(T ) = β(T ).

Statements of the form p ≥ q ‖ T are called non-strict; statements of the form p ≫ q ‖ T , are called fully strict, and statements of the form p > q ‖ T are called weakly strict.

Let LpqT be the set of all preference statements ϕ of the form p✄q ‖ T , as defined above. For any statement ϕ ∈ LpqT equalling p✄q ‖ T , we define ϕ(≥) to be p ≥ q ‖ T , the nonstrict version of ϕ. For lex model π, we define:

• π satisfies ϕ(≥) if α ≽π β for all (α, β) ∈ ϕ∗ .
• π satisfies fully strict ϕ if α ≻π β for all (α, β) ∈ ϕ∗ .
• π satisfies weakly strict ϕ if π satisfies ϕ(≥) and if α ≻π β for some (α, β) ∈ ϕ∗ .

For outcomes α and β, a non-strict preference of α over β can be represented as α ≥ β ‖ ∅, which is equivalent to the preference statement α ≥ β introduced in Section 3, so we abbreviate it to that. Similarly, we abbreviate α > β ‖ ∅ to α > β (which is also equivalent to α ≫ β ‖ ∅).

We can write a statement ϕ ∈ LpqT as ur ✄ us ‖ T , where u ∈ U, r ∈ R, s ∈ S, and U, T and R ∪ S are (possibly empty) mutually disjoint subsets of V , and for all X ∈ R∩S, r(X) ̸= s(X). For such a representation, we write uϕ = u, rϕ = r, sϕ = s, Uϕ = U, Rϕ = R, Sϕ = S and Tϕ = T . We assume, without loss of generality, that if |X| = 1 then X ∈ Tϕ. This ensures that such a representation is unique. We also define Wϕ = V - (Rϕ ∪ Sϕ ∪ Tϕ ∪ Uϕ).

As discussed in [Wilson, 2009] (which, however, just considers non-strict statements), this is a relatively expressive preference language. As well as preferences between outcomes, preferences between partial tuples can be expressed. Ceteris paribus statements can be expressed by using ϕ with Wϕ = ∅. More generally, any variables in Wϕ are forced to be less important than variables in Rϕ and Sϕ.

The following result characterises when a lex model satisfies a non-strict preference statement in LpqT .

Proposition 2 Let ϕ be a non-strict element of LpqT (so that ϕ = ϕ(≥) ), which we write as uϕrϕ ≥ uϕsϕ ‖ Tϕ. Let π ∈ G be the model (Y1,≥1), . . . , (Yk,≥k). Let i be the smallest index such that Yi ∈ Rϕ ∩ Sϕ, or let i = k + 1 if Rϕ ∩ Sϕ ∩ Vπ = ∅. Then, π |= ϕ if and only if (i) rϕ(Yi) >i sϕ(Yi) if Rϕ ∩ Sϕ ∩ Vπ ̸= ∅, and (ii) for all j < i,

• (a) Yj /∈Wϕ;
• (b) if Yj ∈ Rϕ \ Sϕ then for all y ∈ Yj, rϕ(Yj) ≥j y, i.e., rϕ(Yj) is the best value of Yj; and
• (c) if Yj ∈ Sϕ \ Rϕ then for all y ∈ Yj, y ≥j sϕ(Yj), i.e., sϕ(Yj) is the worst value of Yj.

In particular, if Vπ ⊆ Tϕ ∪ Uϕ then π |= ϕ.

The next result gives the extra conditions required for satisfying strict statements.

Proposition 3 Let ϕ ∈ LpqT and π ∈ G. Then:

• if ϕ is a fully strict statement then π |= ϕ if and only if π |= ϕ(≥) and Rϕ ∩ Sϕ ∩ Vπ ̸= ∅;
• if ϕ is a weakly strict statement then π |= ϕ if and only if π |= ϕ(≥) and (Rϕ ∪ Sϕ) ∩ Vπ ̸= ∅.

Proposition 1 can be seen to imply that the non-strict elements of the language LpqT are strongly compositional. In fact this also holds for both kinds of strict statements and certain negations.

Theorem 2 Consider any ϕ ∈ LpqT . Then ϕ is strongly compositional and π |=∗ ϕ if and only if π |= ϕ(≥) . If ϕ is non-strict then ¬ϕ is compositional; if also, Rϕ = Sϕ then ¬ϕ is strongly compositional, and π |=∗ ¬ϕ if and only if either π |= ¬ϕ or Vπ ∩ Sϕ = ∅.

4.2 Checking Consistency for Subsets of L′pqT

Theorem 2 suggests the feasibility of checking consistency of subsets of the language L′pqT , which is LpqT with certain negated statements also included. Formally, define L′pqT to be the union of LpqT with {¬ϕ : ϕ ∈ LpqT , ϕ non-strict, and Rϕ = Sϕ}.

We use the method of Section 3.3 to determine the consistency of a set of preference statements Γ ⊆ L′pqT , by incrementally extending a maximal |=∗ -model π of Γ, and then checking whether or not π |= Γ holds; this makes use of Propositions 2 and 3.

Let Γ ⊆ L′pqT , let X ∈ V and let π ∈ G. We make the following definitions, where Γ is the set of all ϕ ∈ Γ ∩ LpqT such that Rϕ ∩ Sϕ ∩ Vπ = ∅.

• BestπΓ (X) = {rϕ(X) : ϕ ∈ Γ &X ∈ Rϕ \ Sϕ}.
• WorstπΓ (X) = {sϕ(X) : ϕ ∈ Γ &X ∈ Sϕ \ Rϕ}.
• PairsπΓ (X) = PosπΓ (X) ∪ NegπΓ (X), where

PosπΓ (X) = {(rϕ(X), sϕ(X)) : ϕ ∈ Γ &X ∈ Rϕ ∩Sϕ}; and NegπΓ (X) is the set of all pairs (sϕ(X), rϕ(X)) such that ¬ϕ ∈ Γ and Tϕ ∪ Uϕ ⊇ Vπ, and X ∈ Rϕ(= Sϕ).

Given Γ and π ∈ G with π |=∗ Γ, we say that X can be chosen next if: X ∈ V - Vπ and

• if ϕ ∈ Γ∩LpqT and Rϕ ∩Sϕ ∩ Vπ = ∅ then X /∈Wϕ;
• PairsπΓ (X) is acyclic;
• |BestπΓ (X)| ≤ 1 and |WorstπΓ (X)| ≤ 1;
• if x ∈ BestπΓ (X) then x is undominated in PairsπΓ (X), i.e., there exists no element of the form (x′ , x) in PairsπΓ (X);
• if x ∈ WorstπΓ (X) then x is not dominating in PairsπΓ (X), i.e., there exists no element of the form (x, x′ ) in PairsπΓ (X).

We also say that (X,≥X) is a valid extension of π if (i) X can be chosen next; and (ii) ≥X ⊇ PairsπΓ (X); (iii) if x ∈ BestπΓ (X) then x is the best element in X with respect to ≥X

(so that x ≥ y for all y ∈ X); and (iv) if x′ ∈ WorstπΓ (X) then x′ is the worst element in X with respect to ≥X.

The following result states the conditions needed for minimally extending π to maintain the |=∗ -satisfaction of Γ.

Proposition 4 Suppose that Γ ⊆ L′pqT , and that π |=∗ Γ. Let X be a variable in V - Vπ and let π′ = π ◦ (X,≥X), where ≥X is a total ordering on X. Then π′ |=∗ Γ if and only if (X,≥X) is a valid extension of π.

In summary, at each stage of the incremental algorithmwe see if there is a variable X that can be chosen next, and if so, generate a valid extension; if not, we then have generated a maximal |=∗ -model π of Γ. We check consistency of Γ by determining if π satisfies Γ. Using the fact that |PairsπΓ (X)| ≤ |Γ|, it can be shown that the overall complexity of checking that Γ (⊆ L′pqT ) is consistent is O(|V |2 |Γ|).

5 Optimality with Respect to Sets of Compositional Preference Statements

We consider a finite set of alternatives A ⊆ V , and we assume that we have elicited a set Γ of preference statements; we would like to find the optimal alternatives among A. As we will see, there are several natural definitions of optimal [Gelain et al., 2010; Wilson and O'Mahony, 2011]. We compare some of these and analyse their computational cost in the context of lex models and compositional statements.

We define pre-order relation ≽Γ on outcomes by α ≽Γ β ⇐⇒ Γ |= α ≥ β, and we define equivalence relation ≡Γ by α ≡Γ β ⇐⇒ Γ |= α ≡ β, i.e., if α and β are equivalent in all models of Γ. Using a similar argument to that for Theorem 1, it can be shown that, for compositional Γ, we have Γ |= α ≡ β holds if and only if α ≡π β, where π is an arbitrary maximal model of Γ. We also define ≻Γ to be the strict part of ≽Γ, so that α ≻Γ β if and only if α ≽Γ β and α ̸≡Γ β. We then say that α strictly dominates β.

We define CSDΓ(A) ('Can Strictly Dominate') to be the set of maximal, i.e., undominated, elements of A w.r.t. ≻Γ. α ∈ CSDΓ(A) if and only if for all β ∈ A which are not ≡Γ-equivalent to α there exists some π |= Γ with α ≻π β.

We define Oπ(A) to be the subset of the alternatives that are optimal in model π, i.e., {α ∈ A : ∀β ∈ A, α ≽π β}. We say that α ∈ A is necessarily optimal in A, written α ∈ NOΓ(A), if α is optimal in every model, i.e., if for all π ∈ G with π |= Γ we have α ∈ Oπ(A).

We say that α is possibly optimal, written α ∈ POΓ(A), if α is optimal in some model of Γ, so that POΓ(A) = ⋃π|=Γ Oπ(A). Similarly, we say that α ∈ POMΓ(A) if α is optimal in some maximal model of Γ. α is possibly strictly optimal in A, written α ∈ PSOΓ(A), if there exists some π |= Γ with Oπ(A) ∋ α and Γ |= α ≡ β for all β ∈ Oπ(A). Thus α is in PSOΓ(A) if there is a model of Γ in which α is optimal, and all other optimal elements are equivalent to α.

Let OptAΓ (α) be the set of models π of Γ that make α optimal in A, i.e., {π |= Γ : Oπ(A) ∋ α}. We define α ∈ MPOΓ(A) if OptAΓ (α) is maximal, in the sense that there exists no β ∈ A with OptAΓ (β) a strict superset of OptAΓ (α). We say that α is maximally possibly optimal in A given Γ; this holds if and only if there is no alternative that is optimal in the same set of lex models and more.

Let π1, . . . , πk be a finite sequence of models. Define Aπ1 to be Oπ1 (A). For i = 1, . . . , k we iteratively define Aπ1,...,πi to be Oπi (Aπ1,...,πi-1 ). We define the extreme elements EXTΓ(A) as follows. α ∈ EXTΓ(A) if and only if there exists a sequence π1, . . . , πk of models of Γ such that Aπ1,...,πk ∋ α and for all β ∈ Aπ1,...,πk , Γ |= α ≡ β. Therefore, α ∈ EXTΓ(A) if there is a sequence of lex models such that iteratively maximising with respect to each lex model in turn leads to a set containing α and only other alternatives that are equivalent to α.

Proposition 5 For any A ⊆ V and Γ ⊆ L we have PSOΓ(A) ⊆ POMΓ(A) ∩ MPOΓ(A) ∩ EXTΓ(A). If Γ is compositional then PSOΓ(A) = POMΓ(A) = MPOΓ(A) = EXTΓ(A).

Without making assumptions about Γ we have the following properties, which follow from basic arguments, that apply in a very general context [Wilson and O'Mahony, 2011].

Proposition 6 Consider any A ⊆ V and Γ ⊆ L. Then, the following all hold. (i) NOΓ(A) ∪ PSOΓ(A) ⊆ MPOΓ(A) ∩ EXTΓ(A); (ii) EXTΓ(A) ⊆ CSDΓ(A) ∩ POΓ(A); (iii) MPOΓ(A) ⊆ POΓ(A); (iv) MPOΓ(A) ∩ EXTΓ(A) is always non-empty. (v) If NOΓ(A) is non-empty then NOΓ(A) = MPOΓ(A) = EXTΓ(A) = CSDΓ(A).

Propositions 5 and 6 imply the following result, showing that there are substantial simplifications of the optimality classes when Γ is compositional.

Theorem 3 Consider any A ⊆ V and compositional Γ ⊆ L. Then NOΓ(A) ⊆ PSOΓ(A) = EXTΓ(A) = MPOΓ(A) = POMΓ(A) ⊆ CSDΓ(A) ∩ POΓ(A).

Computational Results: One approach to compute Ω(A) for Ω ∈ {POΓ,PSOΓ,CSDΓ,NOΓ} is to test membership for every alternative. By the results in Section 4.2, we can decide consistency for g statements in L′pqT and n variables in O(n2 g). To test if α ∈ POΓ(A), we test whether Γ ∪ {α ≥ β | β ∈ A - {α}} is consistent in O(n2 (g + m)), where |A| = m. Similarly, we test if α ∈ PSOΓ(A) in O(n2 (g+m)), by checking if Γ∪{α > β | β ∈ A, β ̸≡Γ α} is consistent. To test if α ∈ CSDΓ(A), we check for all β ∈ A with β ̸≡Γ α if Γ ∪ {α > β} is consistent in O(mn2 g)). To test if α ∈ NOΓ(A), we test for all β ∈ A - {α} if Γ ∪ {α < β} is consistent in O(mn2 g)). Optimality sets can also be computed incrementally [Wilson et al., 2015b].

We implemented these methods for computing POΓ,PSOΓ,CSDΓ and NOΓ and randomly generated 10 consistent instances for each configuration of g ∈ {100, . . . , 1000} (equally divided into fully strict, weakly strict, non-strict and negated non-strict) and n ∈ {100, . . . , 1000} variables with random domain sizes 2 or 3. We tested the methods on every instance for m = 100, . . . , 500 alternatives. All experiments result in NOΓ(A) ⊆ POΓ(A) = PSOΓ(A) ⊆ CSDΓ(A) which extends the relations from Theorem 3. In our experiments, CSD is computed much slower than PO, PSO and NO. Also, often PO is computed faster than NO. In practice, it is often desired to compute relatively small sets of optimal solutions, e.g., not to overwhelm a user with too many choices. Since NOΓ is usually empty in our experiments, computing PSOΓ or POΓ may be the best choice because of its size and computational cost.

6 Discussion

We have developed a new approach for preference inference based on lexicographic models, using a notion of strong compositionality that allows a greedy algorithm. This is shown to be polynomial for relatively expressive preference languages. We also examined different notions of optimality, and proved relationships between them. Our experimental results confirm that the preference inference/consistency algorithm is fast, and examined the problem of generating optimal solutions, where it was found that generating the sets of possibly optimal and possibly strictly optimal solutions were significantly faster than generating the undominated solutions.

There are other common forms of preference statement that are strongly compositional, and for which the greedy algorithm will enable checking consistency. For instance, a restriction on the allowed value orderings of each variable is always strongly compositional. This can include, for instance, highly disjunctive statements, for instance, structural properties of the value orderings, such as being single-peaked [Conitzer, 2009]. Certain kinds of restrictions on variable orderings are also strongly compositional.

A lexicographic order can also be viewed as a static variable and value search ordering, for a constraint satisfaction or optimisation problem. In a configuration problem, for instance, we may want to generate solutions in an ordering which fits in with what one knows about user preferences and the structure of the problem [Junker and Mailharro, 2003]. We can thus take, as input, past user preferences between solutions, or even partial tuples; or that all solutions of one constraint are preferred to all those satisfying another constraint. There may be natural restrictions on the set of value orderings, e.g., that there is a single peak or trough with a numerical domain. Given such inputs, which are strongly compositional, one can apply our approach to see if there is a compatible lexicographic order, which can then be used to generate solutions in a best first order.

Our approach in Section 3 was rather abstract, in that no explicit structure on the language L was assumed. In fact, a closer examination of the proofs of some of the main results suggests that these will hold more generally than for lexicographic orders: essentially they just depend on basic properties of composition and extension, but not otherwise on the structure of models. In particular, it is natural to look at the generalisation to conditional lexicographic orders, which are closely related to conditional preference languages [Wilson, 2009]. It would also be interesting to explore the potential connection with efficient classes of planning problems.

Acknowledgments

This publication has emanated from research conducted with the financial support of Science Foundation Ireland (SFI) under Grant Number SFI/12/RC/2289.