4.1 Utility functions for ceteris paribus preferences

McGeachie and Doyle (Reference McGeachie and Doyle2002, Reference McGeachie and Doyle2004) present a set of methods for translating preference information from a qualitative representation to a quantitative representation, summarised in Table 2. Broadly, they consider ceteris paribus preferences, represented with a propositional language augmented with an ordering relation that is used to express preferences over propositional combinations of a set of elementary attributes. This qualitative representation is then converted to an ordinal utility function to be used in reasoning processes.

Table 2

Reference card: utility functions for ceteris paribus preferences

In order to specify a set of possible options, a restricted logical language $$ \cal L $$ is adopted, using only two logical operators: ¬ (negation) and ∧ (conjunction) to construct finite sentences over a set of atoms, each corresponding to an attribute from a space of binary attributes describing possible worlds. A complete consistent set of literals is a model. For example, cars may be defined in terms of four attributes, sportType, SUVtype, yellow, and red. Based on these attributes, we specify a set of four possible models below.

• ∙ m ₁: sportType, ¬SUVtype, yellow, ¬red (yellow sport cars);

• ∙ m ₂: sportType, ¬SUVtype, ¬yellow, red (red sport cars);

• ∙ m ₃: ¬sportType, SUVtype, yellow, ¬red (yellow SUV cars);

• ∙ m ₄: ¬sportType, SUVtype, ¬yellow, red (red SUV cars).

Based on this, we can specify ceteris paribus preferences: where p and q are statements in $$ \cal L $$ : p ⊵ q, when p is desired at least as much as q (formally, it is interpreted that p∧¬q is desired at least as much as q∧¬p); and p ⊳ q, when p is strictly more desired than q. Moreover, conditions may also be specified, in the form if r then p ⊵ q, meaning that the ceteris paribus preference holds, if r (also a statement in $$ \cal L $$ ) holds. For example, conditional ceteris paribus preferences may be: if sportType, then red ⊳ yellow and if SUVtype, then yellow ⊳ red. This means that in the cases where sportType holds, that is, m ₁ and m ₂, red is strictly more preferred than yellow, all else being equal; and in the cases where SUVtype holds, that is, m ₃ and m ₄, yellow is strictly more preferred than red, all else being equal (but in this example there are no other attributes).

Based on specified preferences, the goal is to derive a preference order, which is a complete preorder (reflexive and transitive relation) ≿ over the set of all models of $$ \cal L $$ . When, given two models m and m′, m ≿ m′, it is said that m is weakly preferred to m′. If m≿m′ and m′≵m, it is said that m is strictly preferred to m′, written m≻m′. If m≿m′ and m′≿m, then it is said that m is indifferent to m′, written m~m′. For instance, if we consider the preference specified above (if sportType, then red ⊳ yellow), then we can conclude that m ₂≻m ₁.

In order to do so, the general idea of the approach is to generate an ordinal utility function from a set C of ceteris paribus preferences over attributes X. An initial step is performed, which translates the provided statements represented in a logical representation of ceteris paribus preferences to an attribute-vector representation. The latter is then used to produce the utility function in the following way. The structure of preference statements in the attribute-vector representation is used to infer additive utility independence among attributes. Next, subutility functions are defined for each utility-independent set of attributes—if no utility independence was identified in the previous step, only one subutility function, associated with the set of all attributes, is defined in this step. This is done based on the representation of preorders consistent with the preferences by building a graph over assignments to the attributes. Finally, to assign relative weights of satisfaction of different attributes (i.e. to establish trade-offs among attributes), a linear programming problem is solved. In the end, a utility function that can be used to evaluate the utility of different assignments to values of X is built.

This work has two different aspects related to complexity, which are associated with (McGeachie & Doyle, Reference McGeachie and Doyle2004): (i) the time and space required to construct the utility function u and (ii) the time and space required to evaluate u(m) on a particular model m. Both take exponential time, in the worst case. Constructing u involves solving a satisfiability problem, where the time required depends on the number of rules involved in conflicts in each utility-independent set. On the other hand, computing u(m) involves computing u _i(m), where u _i is a minimising utility function, for all the utility-independent attribute sets. Each of the subutility functions can be exponential in the size of the utility-independent set.

4.2 Learning utility functions with support vector machine

The approach proposed by Domshlak and Joachims (Reference Domshlak and Joachims2006, Reference Domshlak and Joachims2007) takes a new direction for reasoning about preferences, as introduced in Table 3. First, it adopts a new form of representing preferences: instead of seeing an option as a set of values (parameters) specified for a set of attributes, it linearises the possible combinations of attribute values and each of these combinations is seen in a unified non-parametric way, that is, as a unique specification. For instance, ‘big red suitcase’ is not an option (suitcase) parameterised with values assigned to colour and size, but as a single option. Second, machine learning techniques are adopted to generate a utility function to model user preferences. Preferences are represented as qualitative preference expressions, as detailed in Table 3.

Table 3

Reference card: learning utility functions with SVM

SVM=Support vector machine.

The two main aspects of this work are the proposed underlying preference representation, that is, how the qualitative preference statements are represented, and how the utility function is generated. The situation explored in this work is when the system cannot assume a significant independence structure on attributes. So, the basic idea is that if no useful preference independence information in the original representation space is provided, a different space is adopted in which no such independence information is required. This new space is specified as follows: assuming that the attributes X are all binary valued, there is a mapping from the options χ into a new, higher-dimensional space $$ \cal F $$ using a certain mapping Φ=χ ↦ $$ \cal F $$ =ℝ⁴ⁿ.

The mapping Φ is not arbitrary, but establishes a connection between the dimensions χ and $$ \cal F $$ , in which each element of $$ \cal F $$ is a combination of values of attributes. Explaining Φ formally is outside the scope of this paper, so we limit ourselves to an informal example. Consider two attributes to describe a car: sport type (with values sportType and ¬sportType) and colour red (with values red and ¬red). The mapping Φ maps an option o=〈sportType, ¬red〉 to a value 1 when sportType or ¬red holds, or both, and to a value 0, otherwise, as shown below:

$$\qquad \qquad \qquad \qquad \qquad \qquad \quad \qquad \Phi \left( x \right)=\matrix{ {\matrix{ {\left[ {\matrix{ 1 \cr 0 \cr 0 \cr 1 \cr 0 \cr 1 \cr 0 \cr 0 \cr } } \right]} & {\matrix{ \hskip -33pt { & sportType} \cr \hskip -26pt { & \neg sportType} \cr { \hskip -59pt & red} \cr { \hskip -52pt & \neg red} \cr { \hskip -11pt & sportType,\,\,red} \cr { & \hskip -5pt sportType,\,\neg red} \cr { & \hskip -4pt \neg sportType,\,\,red} \cr { & \hskip 2pt \neg sportType,\,\,\neg red} \cr } } \cr } } & \eqalignno{ & \cr & \cr & \cr & \cr & \cr & \cr & \cr & \cr} \cr } $$

Note that there are also dimensions not shown here, with three or four elements, but they are all 0 because they include either sportType and ¬sportType, or red and ¬red.

Any preference ordering over χ is additively decomposable in $$ \cal F $$ ; that is, weights w _i can be associated with Φ(x)[i], so that they are in accordance with provided preference statements. Consequently, statements are used as constraints over weights together with an objective function in an optimisation problem. To calculate weights, techniques frequently used in machine learning in the context of support vector machines (SVMs) (Vapnik, Reference Vapnik1998) are adopted, as this mapping of inputs into high-dimensional attribute spaces, called the kernel trick, is used in SVM to perform a nonlinear classification.

Solving the optimisation problem of this approach raises several complexity issues. First, although this constraint system is linear, it is linear in the exponential space ℝ⁴ⁿ. Second, the description size of the optimisation problem and, in fact, of each individual constraint of it, can be exponential in n. Nevertheless, Domshlak and Joachims (Reference Domshlak and Joachims2007) show that these complexity issues can be overcome using optimisation techniques and some assumptions, such as that propositional formulas coming from user statements are unlikely to be of a size that would pose computational challenges in practice.

This work is strongly associated with machine learning (Alpaydin, Reference Alpaydin2010; Flach, Reference Flach2012) and recommender systems (Adomavicius & Tuzhilin, Reference Adomavicius and Tuzhilin2005; Su & Khoshgoftaar, Reference Su and Khoshgoftaar2009; Ricci et al., Reference Ricci, Rokach, Shapira and Kantor2011). It interprets each pairwise comparison as likes and dislikes of options with similar values for attributes and builds a model that generalises these comparisons, which can also be with the whole set of options, when monadic statements (those with a single referent, such as I like red) are provided. Therefore, there is a statistical generalisation and, to achieve good results here, a large number of statements may be needed. This is reflected in the future work reported by the authors, whose goal is to specify the number of preference statements that a user must provide to infer a utility function that is effective.

4.3 User-centric preference-based decision making

Nunes et al. (Reference Nunes, Miles, Luck and Lucena2012a, Reference Nunes, Miles, Luck and Lucena2012b) proposed a preference reasoning technique (detailed in Table 4) whose goal is to simulate human reasoning in making decisions, allowing exploitation of natural user expressiveness of preferences (without the need for elicitation methods) and resolve trade-offs (that cannot be resolved with the provided preferences) in the way that humans would do so. As a result, the technique is based on heuristics investigated in psychology that explain how people make decisions.

Table 4

Reference card: user-centric preference-based decision making

The input of the technique consists of a set of options over which a choice is made, and a set of preferences expressed in a language—derived from a study of how humans express preferences (Nunes et al., Reference Nunes, Barbosa, Cowan, Miles, Luck and de Lucena2013)—that allows the construction of statements such as those shown below. This is an example in a scenario in which a choice for an apartment is being made by a student, where apartments are described in terms of zone (the zone in which the apartment is located), uni (distance from the apartment to the university), station (distance from the apartment to the underground station), and brand (the brand of the company to which the apartment belongs). Numbered statements are preferences over attribute values, while unnumbered statements are priorities over attributes. Numbers in preference statements indicate their priority: the lower the number, the more important the preference.

1. 1. don’t acceptzone>2

2. 2. preferuni⩽2.5 km

3. 3. ifuni⩽2.5 km then requireprice⩽£125

4. 4. ifuni>2.5 km then needstation⩽0.7 km

5. 5. ifuni>2.5 km then requireprice⩽£105

6. 6. minimisestation

7. 7. minimiseprice

8. 8. preferbrand=A orbrand=B orbrand=C

9. 9. brand=A ≻ brand=B

10. 10. brand=B ≻ brand=C

• ∙ ifuni>2.5 km thenstation ⊳ uni

The proposed technique processes preferences to select one option, in such a way that the choice, and the decision not to choose alternatives, can be justified by the preferences. The output is a partially ordered set, organised in four different levels: (i) the chosen option; (ii) acceptable options that are close to the chosen option, but not chosen; (iii) eliminated options, discarded because of a hard constraint; and (iv) dominated options. Heuristics used by humans are applied to make the choice, specifically reason-based choice (Shafir et al., Reference Shafir, Simonson and Tversky1998), which concerns how people make decisions by identifying reasons to accept and reject options, and the principles of trade-off contrast and extremeness aversion (Simonson & Tversky, Reference Simonson and Tversky1992), so that decisions more closely mirror user choices if users are provided with sufficient time and knowledge.

In outline, the steps of the technique are as follows. In the first step, pre-processing, options are analysed to extract the essential data. This includes how well option attributes meet the preferences, and how options compare with each other in relation to individual attributes. In the second step, explication, information that is implicit in the provided preferences is extracted and incorporated into the set of provided preferences. Next, the elimination step eliminates those options that do not meet strict constraints, or that are dominated in every respect by other options. Finally, the selection step makes the choice itself. Preferences and priorities are transformed into a quantitative decision function that can be seen as a relative utility function, which relates every two options. This relative utility function consists of three factors: the costs provided by the attribute values of an option with respect to another, the trade-off contrast, and extremeness aversion, these last two being heuristics people adopt in making decisions, determined using the costs.

Although this approach requires a relatively small amount of preferences to make a decision—that is, the preferences provided need not be sufficient to derive a partial order with an optimal option—due to the adoption of heuristics of human decision making, it has parameters (such as scales for natural-language keywords) that have a significant impact on the decision-making process.

5.1 Conditional preference networks

Conditional preference networks (CP-nets), the reference card for which is shown in Table 5, represent preferences in a compact graphical form and, according to Boutilier et al. (Reference Boutilier, Brafman, Hoos and Poole1999, Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004) represent preference statements in a natural way. These statements are conditional qualitative preference statements interpreted under the ceteris paribus semantics.

Table 5

Reference card: CP-nets

A CP-net over attributes X=x ₁, … , x _n is a directed graph G over x ₁, … , x _n whose nodes are annotated with conditional preference tables CPT(x _i) for each x _i∈X. Each CPT(x _i) associates a total order $${\succ}_{u}^{i} $$ with each instantiation u of x _i’s parents Pa(x _i)=U. In summary, the kinds of statements captured by CP-nets are those that establish order among attribute values, conditioned to values set to other attributes (parent attributes). Optimisation queries require only a CP-net as input, and optionally a partial assignment for attributes, while the required input for ranking queries is a CP-net N and two options o and o′.

As CP-nets are graphical structures, in order to provide a better understanding of them, we first introduce a simple example (Boutilier et al., Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004) that expresses preferences over dinner configurations. This network, depicted in Figure 1(a), consists of two attributes S and W, for soup and wine, respectively. Fish soup (S _f) is strictly preferred to vegetable soup (S _v), while the preference between red (W _r) and white (W _w) wine is conditioned on the soup to be served: red wine is preferred if served with a vegetable soup, and white wine if served with a fish soup.

Figure 1

Example of a CP-net (Boutilier et al., Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004). (a) Preferences for soup and wine. (b) Induced graph.

The semantics of a CP-net is defined in terms of the set of preference rankings that are consistent with the set of preference constraints imposed by its CPTs. Figure 1(b) shows the preference graph over options induced by the previously described CP-net. An arc in this graph directed from option o _i to o _j indicates that a preference for o _j over o _i can be determined directly from one of the CPTs in the CP-net.

CP-nets are used to answer both optimisation and ranking queries. However, ranking queries are split into two categories. (i) Dominance queries: is an option o preferred to another option o′? If so, it is said that o dominates o′ with respect to the given preference structure. (ii) Ordering queries: is an option o′ not preferred to another option o? If so, it is said that o is consistently orderable over o′ with respect to the given preference structure. Ordering queries are weaker than dominance queries, because by answering the latter we know whether o≻o′ holds, while by answering the former we only know whether o′⊁o holds, which does not imply that o≻o′ holds. Next, we briefly describe how each of the preference-related questions is answered using CP-nets.

Optimisation. In order to generate the optimal option of an acyclic CP-net, the network is swept from top to bottom, with the forward sweep procedure (Boutilier et al., Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004), which constructs the most preferred option. It considers, in order to be more general, given evidence constraining possible options in the form of an instantiation y of some subset Y⊆X of the network attributes. The algorithm sets Y=y, and instantiates each x _i∉Y in turn to its maximal value given the instantiation of its parents.

Ordering. For acyclic CP-nets, Boutilier et al. (Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004) define a corollary that provides an algorithm to answer ordering queries. The corollary states that given an acyclic CP-net N and a pair of options o and o′, if there exists an attribute x _i in N, such that: (i) o and o′ assign the same values to all ancestors of x _i in N; and (ii) o assigns a more preferred value to x _i than that assigned by o′ given the assignment provided by o (and o′) to the parents of x _i, then N ⊭ o′≻o.

Dominance. Answering dominance queries is equivalent to the task of determining the existence of an improving (or worsening) sequence of attribute value flips with respect to the given CP-net. A sequence of improving flips from one option to another provides a proof that one option is preferred, or unpreferred, to another in all rankings satisfying the network. This task can be reduced to a special subclass of classical planning problems, and several techniques can be used in a generic search procedure for an improving flipping sequence.

CP-nets were investigated for use with different algorithms related to reasoning about preferences, and their complexity analysed with different graph topologies. Optimisation queries can be answered using the forward sweep procedure, taking time linear in the number of attributes. The complexity of two of the ranking queries (dominance and ordering) has been analysed for different graph topologies of CP-nets, which can be seen in Table 6 (Boutilier et al., Reference Boutilier, Brafman, Hoos and Poole1999, Reference Boutilier, Brafman, Domshlak, Hoos and Poole2004). These results are associated with boolean attributes, but it is claimed that the ordering results also hold for multi-valued attributes. Finally, given a CP-net N over n attributes and a set of complete assignments o ₁, … , o _m, ordering these assignments consistently with N can be done using ordering queries only, in time $${\cal O}(nm^{2} )$$ .

Table 6

Complexity analysis of CP-nets (boolean attributes)

CP-nets=Conditional preference networks.

It is also proved that ordering queries are answered with CP-nets with a directed acyclic graph topology in $${\cal O}(n)$$ . However, the complexity of other queries or CP-net topologies, such as the general case, are left as open questions, which led to further investigations by other researchers (e.g. Goldsmith et al., Reference Goldsmith, Lang, Truszczynski and Wilson2005).

This work thus leaves different open theoretical questions, mainly concerned with the complexity analysis of other scenarios in which CP-nets are used to reason about preferences. In addition, CP-nets address the representation of preferences over discrete domains, but common preferences, such as price minimisation, cannot be directly represented. Moreover, this way of identifying optimal options with CP-nets first optimises parent attribute values, for later assigning values for their children. This leads to a lexicographic preference among attributes, which may capture trade-off situations in an inappropriate way. This issue is investigated in trade-offs-enhanced conditional preference networks (TCP-nets), presented in Section 5.2, which adds importance relations and conditional relative importance statements to the conditional ceteris paribus statements supported by CP-nets.

5.2 Trade-offs-enhanced conditional preference networks

CP-nets represent the class of conditional qualitative preference statements. TCP-nets (Brafman & Domshlak, Reference Brafman and Domshlak2002; Brafman et al., Reference Brafman, Domshlak and Shimony2006)—for which the reference card is presented in Table 7—address a limitation of this approach by extending CP-nets to capture another class of preference statements: those with conditional relative importance. These statements have the following form: ‘it is more important to me that the value of x be high than that the value of x′ be high’. CP-nets can thus be extended with new types of arcs, in order to investigate questions to be answered based on this new graphical representation of preferences.

Table 7

Reference card: TCP-nets

CP-nets=Conditional preference networks.

TCP-nets maintain the ideas of CP-nets, in that they remain focused on using only simple and natural preference statements, use the ceteris paribus semantics, and utilise a graphical representation of this information to reason about consistency and to perform, possibly constrained, optimisation. The extra expressiveness provided allows better modelling trade-offs, with attribute importance relationships. TCP-nets are annotated graphs with three types of edges:

1. 1. a first type of (directed) edge comes from the original CP-nets model and captures direct preferential dependencies (shown as arrows from S to W and S to A in Figure 2);

2. 2. a second (directed) edge type captures relative importance relations—the existence of such an edge from attribute x to attribute x′ implies that x is more important than x′ (shown as an arrow from D to S in Figure 2); and

3. 3. a third (undirected) edge type captures conditional importance relations: such an edge between nodes x and x′ exists if there is a non-empty attribute subset Y⊆X−{x, x′} for which RI(x, x′|Y) (relative importance of x and x′ conditioned on Y) holds (shown as a line connecting W and A in Figure 2).

Figure 2

Example of a TCP-net

In addition to the CPT of CP-nets, in TCP-nets, each undirected edge is annotated with a conditional importance table (CIT). The CIT associated with such an edge (x, x′) describes the relative importance of x and x′, given the value of the corresponding importance-conditioning variables Y. A CIT is illustrated on the right-hand side of Figure 2.

We show an example of a TCP-net in Figure 2, which extends the CP-net example presented in the previous section, expressing preferences over dinner configurations. Besides specifying preferences for the attributes soup and wine (S and W), we also have preferences for dessert and salad (D and A, respectively). Chocolate (D _c) is strictly preferred to fruit (D _f), while the preference between Greek salad (A _g) and Caesar salad (A _c) is conditioned on the soup to be served: Greek salad is preferred if served with a vegetable soup, and Caesar salad if served with a fish soup. In addition, we specify relative importance among attributes. Satisfying preferences for dessert is more important than satisfying preferences for soup (directed edge linking D and S), while satisfying preferences for salad and wine depends on the values of soup and dessert (an undirected edge linking A and W, labelled with S, D), and this conditionality is expressed in the CIT located on the right-hand side of the figure. For instance, satisfying preferences for wine is more important than satisfying preferences for salad, if fish soup is served with fruit for dessert.

Informally, the semantics of TCP-nets is as follows. A strict partial order ≻ satisfies the following:

• ∙ the conditional preferences for attribute x, if any two complete assignments that differ only on the value of X are ordered by ≻ consistently with the ordering on x values in the CPT of x (the ordering can depend on the parent of x in the graph);

• ∙ the assertion that x is more important than x′, if given any two complete assignments that differ on the value of x and x′ only, ≻ prefers that assignment which provides x with a better value; and

• ∙ the assertion that x is more important than x′ given some assignment y to attribute set Y, if given any two complete assignments that differ on the value x and x′ only, and in (both of) which Y is assigned y, ≻ prefers that assignment which provides x with a better value.

A particular class of TCP-nets is the main target of investigation, namely conditionally acyclic TCP-nets, because it is a class of networks that are proven satisfiable. The key property of this class of TCP-nets is that they induce an ‘ordering’ over the nodes of the network. A TCP-net is conditionally acyclic if its induced dependency graph is acyclic and for every assignment w to the union of all selector sets (i.e. sets of the attributes associated with conditional importance arcs) of the network, the induced w-directed graphs are acyclic. Therefore, verifying if a TCP-net is conditionally acyclic becomes a relevant issue. This is performed in polynomial time in certain situations, which are identified and detailed elsewhere (Brafman et al., Reference Brafman, Domshlak and Shimony2006); however, this verification is generally hard.

Optimisation. To compute the most preferred option of an acyclic TCP-net and a (possible empty) partial assignment x on its attributes, the forward sweep procedure introduced in Section 5.1 can be used. However, it is not possible if a set of hard constraints is provided. This is because the key difference between processing an acyclic CP-net and a conditionally acyclic TCP-net is that, while the former induces a single partial order of importance over attributes, the latter induces a hierarchically structured set of such partial orders. So, a branch-and-bound algorithm for computing the optimal option in this scenario consists of two parts: Search-TCP and Reduce (Brafman et al., Reference Brafman, Domshlak and Shimony2006). The Search-TCP algorithm is guided by the underlying TCP-net N. It proceeds by assigning values to the attributes in a top-down manner, ensuring that options are generated according to the preferential ordering induced by N. The Reduce algorithm, in turn, refines a TCP-net N with respect to a partial assignment K': it reduces both the CPTs and the CITs involving this attribute, and removes this attribute from the network.

Dominance. Much like in CP-nets, a dominance query 〈N, o, o′〉 with respect to a TCP-net can be treated as a search for an improving flipping sequence from the (purported) less preferred option o′ to the (purported) more preferred option o through a sequence of successively more preferred options, such that each flip in this sequence is directly sanctioned by the given TCP-net.

5.3 Graphically structured value-function compilation

Given that reasoning about preferences represented by value functions is easy as they establish an order among options by ordering computed values, Brafman and Domshlak (Reference Brafman and Domshlak2008) propose an approach for compiling the information captured by CP-nets and TCP-nets into value functions, as described in Table 8. The approach assumes that preference statements have already been elicited from or informed by users, and represented as a TCP-net—or a CP-net, in case there is no (conditional) relative importance between pairs of attributes. The graphical structure plays an important role in analysing and compiling these statements.

Table 8

Reference card: graphically structured value-function compilation

TCP-nets=Trade-offs-enhanced conditional preference networks; CP-nets=Conditional preference networks.

This work proposes to use a TCP-net to initially organise qualitative preference statements obtained from the user. Then, this information is compiled into a value function that maintains the qualitative structure and independence assumptions implicit in the TCP-net. This obtained value function is used as the model of the user’s ordinal preference and, as new information is received from the user, this value function is refined, while still maintaining the independence assumptions implied by the original TCP-net, if possible.

A TCP-net can be represented as a value function, as it defines a (partial) order among outcomes. The main challenge is to investigate whether there exists a GA value function defined over small factors ‘implied’ by the structure of the network, that is, to find a structured value function that, in some sense, is as compact as the original TCP-net. In order to do so, it is necessary to define a GA value function whose factors are the families of the CP-net. A CP-family is the set that includes a particular attribute and its parents. For instance, considering the example of Section 5.1, the CP-family of S is {S} (as it has no parents), while that of W is {W, S} (W is the attribute and S its parent). Every acyclic CP-net is GA-decomposable over its CP-families; that is, a CP-family is a utility-independent set of attributes. In order to identify the weights of the value function, a system of linear inequalities (CP-conditions) is constructed and solved. The same applies to TCP-nets; that is, every acyclic TCP-net is GA-decomposable over its TCP-families. A TCP-family, in turn, is composed of a particular attribute, its parents, and also the attributes that impose conditionality on the target attribute. For instance, in the example of Section 5.2, the TCP-family of W is {W, S, D} (W is the attribute, S is its parent, and S and D impose conditionality on W).

This value-function compilation is not only efficient and sound, but also complete; that is, the ability to generate the value function is guaranteed. A system of linear inequalities L, either for CP-nets or TCP-nets, is locally exponential. However, if the maximum cardinality of all extended CP-families (an attribute, its parents, its children, and its children’s parents) of a CP-net N is a constant k, a value function consistent with N can be constructed in time polynomial in the size of N. This also holds for TCP-nets.

Because this work relies on TCP-nets (and CP-nets), limitations regarding the representation of preferences and their interpretation are also related to this work. Moreover, the authors themselves point out that their work raises numerous open theoretical questions, including (Brafman & Domshlak, Reference Brafman and Domshlak2008): (i) when (if at all) is GA-decomposition complete for cyclic TCP-nets, or even just cyclic CP-nets and (ii) what is the most compact form of GA-decomposition that is complete for all consistent TCP-nets.

6.1 Semiring-based constraint satisfaction

Different approaches have been proposed as extensions to CSPs to deal with soft constraints, that is, when constraints are used to formalise desired (preferred) properties rather than requirements that cannot be violated (Freuder & Wallace, Reference Freuder and Wallace1992). Examples are the fuzzy (Dubois et al., Reference Dubois, Fargier and Prade1993) and weighted (Schiex et al., Reference Schiex, Fargier and Verfaillie1995) CSPs.

As many extensions to CSPs have been proposed, a constraint solving framework (Bistarelli et al., Reference Bistarelli, Montanari and Rossi1997; Meseguer et al., Reference Meseguer, Rossi and Schiex2006) has been defined (described in Table 9), where all such extensions, as well as classical CSPs, can be cast, namely the soft constraint satisfaction problem (SCSP). The main idea is based on the observation that a semiring—an algebraic structure, with a domain plus two operations satisfying certain properties—is all that is needed to describe many constraint satisfaction schemes.

Table 9

Reference card: semiring-based constraint satisfaction

CSP=Constraint satisfaction problem.

Semiring-based constraints rely on a simple algebraic structure, called a constraint-semiring or c-semiring (as it is very similar to a semiring), to formalise the notion of satisfaction degrees or preference levels. These establish if a value associated with a constraint is the degree of preference for satisfying the constraint or the penalty for not satisfying it. The structure is specified by a set E of satisfaction degrees, where two binary operators are defined: ×_s specifies how to combine preferences, while +_s is used to induce a partial ordering on E. Additional axioms, including the usual semiring axioms, are added to precisely capture the notion of satisfaction degrees in soft constraints.

A c-semiring is a 5-tuple 〈E, +_s, ×_s, 0, 1〉 such that:

• ∙ E is a set, 0∈E, 1∈E;

• ∙ +_s is an operator closed in E, associative, commutative and idempotent, for which 0 is a neutral element and 1 an annihilator;

• ∙ ×_s is an operator closed in E, associative and commutative, for which 0 is an annihilator and 1 a neutral element; and

• ∙ ×_s distributes over +_s.

Compared with a classical semiring structure, the additional properties required by a c-semiring are the idempotency of +_s (to capture a lattice ordering) and the existence of a minimum and a maximum element (to capture hard constraints).

The c-semiring is a generic framework for representing soft constraint problem solvers and, by capturing their commonalities in a generic framework, one can design generic algorithms and properties instead of several apparently unrelated, but actually similar properties, theorems, and algorithms. Examples of different specific frameworks are presented as soft constraint networks (Meseguer et al., Reference Meseguer, Rossi and Schiex2006), which are summarised in Table 10.

Table 10

Different specific frameworks modelled as c-semirings (Meseguer et al., Reference Meseguer, Rossi and Schiex2006)

c-semirings=Constraint-semirings.

Given that we now have an algebraic structure to deal with preferences, we must define two other concepts needed to specify a constraint problem—constraint system and constraint—both involving the choice of a c-semiring. Basically, an SCSP defines the c-semiring being used, a set of attributes that describe an application area, and their associated domains. In addition, there is a set of constraints, each associated with a value that is interpreted according to the chosen c-semiring. Formally, an SCSP is defined as follows (Bistarelli et al., Reference Bistarelli, Montanari and Rossi1997).

Constraint system. A constraint system is a tuple CS=〈S, F, X〉, where S is a c-semiring, F a finite set, and X an ordered set of attributes.

Constraint. Given a constraint system CS=〈S, F, X〉, a constraint over CS is a pair 〈def, con〉, where

• ∙ con⊆X is called the type of the constraint; and

• ∙ def : F ^k → A (where k is the cardinality of con and A the set of possible values representing the penalty, cost, preference, weight, etc.) is called the value of the constraint.

Constraint problem. Given a constraint system CS=〈S, F, X〉, a constraint problem P over CS is a pair P=〈C, con〉, where C is a set of constraints over CS and con⊆X. It is also assumed that 〈def ₁, con′〉∈C and 〈def ₂, con′〉∈C implies def ₁=def ₂.

In the SCSP framework, the values specified for the tuples of each constraint are used to compute corresponding values for the tuples of values of the attributes in con (set part of the constraint problem), according to the semiring operations: the multiplicative operation is used to combine the values of the tuples of each constraint to get the value of a tuple for all the attributes, and the additive operation is used to obtain the value of the tuples of the attributes in the type of the problem. More precisely, this is the definition of the operations of combination and projection over constraints.

As semiring-based constraints properly generalise classical constraints, this task is NP-hard. As in the classical case, perhaps the most direct way to solve a soft constraint network is searching in its state space, exploring the set of all possible assignments. As an optimal solution is an assignment that minimises the violation degree (or equivalently, maximises the satisfaction degree), optimally solving a soft constraint network is an optimisation problem, and is thus harder than solving classical constraint networks. Different techniques have been proposed to optimise the resolution of this problem, such as defining lower and upper bounds of branch-and-bound algorithms.

Although constraints provide a means of representing qualitative preferences, most of the soft constraint-based approaches also involve the specification of quantitative preferences for each constraint, which is often less intuitive for users. Another limitation of this approach is that it does not deal with multiple objectives; the only objective is to maximise the constraints that are satisfied (considering their weight), but additional objectives such as minimising price cannot be represented. Only intervals for acceptable prices can be provided as constraints.

6.2 Combining conditional preference networks and soft constraints

Domshlak et al. (Reference Domshlak, Rossi, Venable and Walsh2003, Reference Domshlak, Prestwich, Rossi, Venable and Walsh2006) establish a connection between CP-nets and soft constraints machinery, with an approach introduced in Table 11. As dominance queries are hard to answer using a CP-net structure (Section 5.1), they propose constructing a semiring structure with a given acyclic CP-net, in order to be able to do so.

Table 11

Reference card: combining CP-nets and soft constraints

CP-nets=Conditional preference networks; SCSP=Soft constraint satisfaction problem.

This approach thus consists of approximating CP-nets via soft constraints, that is, defining an SCSP based on a CP-net. This provides a uniform framework that combines user preferences with both hard and soft constraints. Thus, given an acyclic CP-net, a corresponding SCSP is constructed in two steps. First, a constraint graph, named SC-net, is built. Second, preferences and weights for the constraints in the SC-net are computed, where this computation depends on the actual c-semiring framework being used. Basically, the SC-net constructed consists of one node for each node of the CP-net plus new nodes for nodes from the CP-net that have more than one parent. Arcs correspond to hard and soft constraints, where the latter are associated with weights and penalties. To calculate these values, two alternative c-semiring frameworks can be used (perhaps other may be used): the min+c-semiring is used for weighted soft constraint satisfaction problems (WSCP), and the S _SLO c-semiring is used for soft constraint lexicographic ordering (SLO):

$${\bf WSCP}:S_{{\min \!\!\plus}}}=\left\langle {R\!_{{\plus}}\!,\min ,\,{\plus}\!,\,{\plus}\!\infty,0} \right\rangle $$

$${\bf SLO}:S_{{{\rm SLO}}} =\left\langle {A,{\rm max}_{S} ,{\rm min}_{S} ,{\bf MAX},\bf 0} \right\rangle $$

where A is the set of sequences of n integers from 0 to MAX, MAX the sequence of n elements all equal to MAX, and 0 the sequence of n elements all equal to 0; max_S and min_S the additive and multiplicative operators, respectively; max_S selects the maximum of two sequences, while min_S selects the minimum of two sequences, both considering a lexicographic order.

In both cases, the computation of preferences and weights ensures information preservation and satisfies the CP-condition, that is, approximations preserve the ceteris paribus property.

Precision is compromised to some degree. Different approximations of CP-net ordering via soft constraints (such as min+ and SLO) can be characterised by how much of the original ordering they preserve, the time complexity of generating the approximation, and the time complexity of comparing outcomes in the approximation. Incomparable outcomes with min+ are considered equal or ordered in either way, and with SLO, a strict order will always be defined.

6.3 Preference-based problem solving for constraint programming

Junker (Reference Junker2008) points out that traditional optimisation approaches compile preferences into a single utility function and use it as the optimisation objective when solving the problem, but they do not explain why the resulting solution satisfies the original preferences, and do not indicate the trade-offs made during problem solving. He then argues that the whole problem-solving process becomes more transparent and controllable by the user if it is based on the original preferences.

The problem of multi-objective optimisation was thus tackled by decomposing it into alternative sequences of single-criterion optimisation problems, which can be solved by standard optimisers, with an approach detailed in Table 12. The chosen sequence gives information that explains the optimality of the solution. Based on the explanation, the user can either accept the solution or modify the preferences. The problem solver then modifies the solution correspondingly. Preferences thus allow the user to interact with the problem solver and to control its behaviour.

Table 12

Preference-based problem solving for constraint programming

CSPs=Constraint satisfaction problems.

This work considers a finite set of attributes X where each attribute x∈X has a domain D(x). The problem space of X is restricted by defining constraints on attributes in X. A constraint c has a scope X _c⊆X and a ‘relation’, which is expressed by a set R _c of assignments to the scope X _c. Such constraints define the set of available options. Consider our example of dinner configurations used to explain TCP-nets, where we have four different attributes: soup (S), wine (W), salad (A), and dessert (D), and each of these attributes has two possible values in its domain. In this scenario, we have 16 possible different configurations, and we can restrict our problem space to the available options, for example, all configurations that serve chocolate as dessert, serve red wine to drink.

Users must provide as input preferences on certain properties of the option. These criteria are mathematical functions from the problem space to an option domain. Formally, a criterion z with domain Ω is an expression f(x ₁, … , x _n) where x ₁, … , x _n are attributes from X and f is a function of signature D(x ₁)× … ×D(x _n)→Ω. Function f can be formulated with the operators of the constraint language (e.g. sum, min, max, conditional expression) or by a table. For example, suppose we are interested in specifying preferences over dishes. A function f may map the dishes to types of dishes, such as light, vegetarian, and so on, so that users may specify their preferences over dish types, and not only over particular attribute values.

Given this, the user can compare different options in a domain Ω and formulate preferences between them. Preferences are modelled in the form of a preorder ≳ on Ω, which consists of a strict part ≻ and an indifference relation ∼. The user may also formulate wishes about the properties that an option should have. Such a wish is a soft constraint which should be satisfied if possible. A wish for constraint c can thus be modelled by a preference 〈z _c,>〉, which is abbreviated by wish(c). For example, if the user wants chocolate for dessert (c=D _c), then the wish is wish(D _c).

As opposed to combinatorial problems with preferences, which are classically solved by compiling all preferences into a single utility function and by determining an option satisfying the constraints with maximal or nearly maximal utility, Junker (Reference Junker2008) uses individual preferences with constraint solvers, in order to allow the optimiser to give an explanation of optimality in terms of the original preferences. First, an atomic optimisation step is performed, which finds options satisfying the constraints C that assign a ≻-maximal value to a single criterion z. This is possible if the user provides a total order over the domain of z, otherwise all possible total orders are generated based on the provided partial order, and the constraint solver runs for each possible total order. Maximal options in this case are the union of maximal options of each of them.

In order to address multiple criteria optimisation, an importance order is introduced on the preferences, also to decide trade-offs in favour of more important preferences. Lexicographic optimisation is then used to define an ordering on the option space based on this importance principle, which leads to finding a lexicographically optimal option. As the importance among the criteria is unknown, permutations of all possible orders are done. If users are not satisfied with the results, they can establish the importance among the criteria, which is a strict partial order I⊆Z×Z, so that only permutations that respect this strict partial order will be considered.

Finally, pareto-optimality is adopted to capture all the possible trade-offs, because using a lexicographic approach gets the best value for a more important criterion z ₁, while a less important criterion z ₂ is completely penalised, which is a limitation discussed for some of the previously presented approaches. In this case, pareto-optimal options are found, which are those that pareto-dominate other options, that is, optional options are better for at least one criterion, and equally good for the others. As there is no direct way to transform a pareto-optimisation problem into a solved form of the optimisation problem even if it is based on totally ordered preferences, wishes establish penalty limits for criteria.

One of the most challenging problems in preference reasoning is dealing with trade-offs. When a solution is optimal for all criteria, it is trivially optimal. However, requiring users to establish penalty limits for resolving trade-offs has two main drawbacks: (i) for domains that users are not very familiar with, they might only have a vague idea of what is a good limit to establish for the trade-off and (ii) this solution may lead to a situation in which the most important criterion is maximised to a value that sets the maximum penalty to the least important criterion, yet users may prefer something in between. It is important to note that this trade-off resolution involves user interaction.

7.1 Winnow

An extension to relational algebra was proposed by Chomicki (Reference Chomicki2003) as a preference query formalisation, in which preferences are expressed as binary relations between tuples from the same database relation; these tuples represent options to be selected. The approach, whose reference card is shown in Table 13, defines a central algebraic operator (winnow), which selects the set of dominant options from a database according to provided preferences. This operator has algebraic properties analysed, such as commutativity, commutation of selection or projection, and distribution of winnow over union and difference. Analysing such properties of winnow is important as they can be exploited for formulating efficient database query execution plans.

Table 13

Reference card: winnow

In order to identify the pareto-optimal set, this work requires a database with available options and a set of preference formulas. The database is specified in a relation schema R(x ₁, … , x _n), where each x _i is an attribute. Each attribute x _i is associated with a domain D _i, which is one of two infinite domains: U (uninterpreted constants) and Q (rational numbers). A relation ≻ is a preference relation over R if it is a subset of (D ₁× … ×D _n)×(D ₁× … ×D _n). In addition, this preference relation has the following properties: irreflexivity, asymmetry, transitivity, negative transitivity, and connectivity. A preference formulaC(o ₁, o ₂), on the other hand, is a first-order formula defining a preference relation ≻ in the standard sense, namely o ₁ ≻_co ₂ iff C(o ₁, o ₂). An intrinsic preference formula (ipf) is a preference formula that uses only built-in predicates.

Because two specific domains are considered, U and Q, there are two kinds of attributes, U-attributes and Q-attributes, and two kinds of atomic formulas: (i) equality constraints and (ii) rational-order constraints. It is assumed that ipfs are in DNF (Disjunctive Normal Form) and quantifier-free. Moreover, atomic formulas are closed under negation. Indifference is also defined: every preference relation ≻_c generates an indifference relation ~_c: two options o ₁ and o ₂ are indifferent (o ₁ ~_co ₂) if neither is preferred to the other, that is, o ₁ ≻_co ₂ and o ₂ ≻_co ₁. We show an example of a preference formula below, which expresses ‘I prefer white wine with fish, and red wine with meat’. In this example, d and d′ are dishes, dt and dt′ are dish types, w and w′ are wines, and wt and wt′ are wine types:

$$\eqalignno{ (d,dt,w,wt)\ {\succ}_{C} (d',dt',w',wt')\,\equiv\,(d=d' & \wedge dt = ‘{\rm fish}’ \wedge wt=‘{\rm white}’ \cr &\! \wedge dt'={\rm ‘ fish} ’ \wedge wt'={\rm ‘red} ’) \cr \vee(d=d' & \wedge dt={\rm ‘ meat} ’ \wedge wt={\rm ‘red} ’ \cr & \wedge dt'=\! {\rm ‘ meat} ’ \wedge wt'={\rm ‘ white} ’ ) $$

Note that in this preference formula any white wine is preferred over any red wine for fish or meat (as there is no w=w′ in the formula), while only equal dishes are compared (because of the d=d′). As d=d′, stating only a value for dt or for dt′ would have been enough.

In order to reason about provided preferences, an algebraic operator called winnow, whose definition is presented below, picks from a given relation the set of the most preferred (dominant) options, according to a given preference formula. A preference query is a relational algebra query containing at least one occurrence of the winnow operator.

Winnow. If R is a relation schema and C a preference formula defining a preference relation ≻ _Cover R, then the winnow operator is written as ω _C(R), and for every instance r of R:

$$\omega _{C} (R){\rm =}\{ o\in r\,\mid\,\neg \exists o'\in r.o'{\succ}_{C} o\} $$

There are three possible algorithms (Chomicki, Reference Chomicki2003) to evaluate winnow. The first is a nested-loops algorithm, which compares every two options and discards dominated ones. This algorithm is correct for any preference relation ≻. The second, BNL, is an algorithm proposed by Börzsönyi et al. (Reference Börzsönyi, Kossmann and Stocker2001) in the context of a specific class of preference queries, namely skyline queries, but the algorithm is considerably more general than the previous one. The third (Chomicki et al., Reference Chomicki, Godfrey, Gryz and Liang2005), SFS, is a variant of the second, in which a presorting step is used. The BNL and SFS algorithms require the preference relation to be a strict partial order.

7.2 Best-matches-only query model

Kießling (Reference Kießling2002) defines preferences as strict partial orders and proposes several preference constructors in order to support the accumulation of single preferences into more complex ones. He also provides a collection of algebraic laws to manipulate such preference constructions, and specifies how to evaluate preference queries under the best-matches-only (BMO) query model (which is very similar to the winnow operator) and decomposition algorithms for complex preference queries. The reference card of his approach is presented in Table 14.

Table 14

Reference card: best-matches-only query model

The input needed for querying the pareto-optimal set is a database with available options and a set of preferences. The database specifies a set X of attribute names x _i, each associated with a domain D _i. A preference P is a strict partial order P=(x _i, <P), where <P⊆D _i×D _i. <P is irreflexive and transitive (which imply asymmetry), and ‘p<P q’ is interpreted as ‘I like p better than q’.

In order to build preferences, many constructors are provided. To build base preferences, there are two classes of constructors: (i) non-numerical base preferences, which include positive and negative preferences, to specify for instance a desired laptop brand and (ii) numerical base preferences, which include preferences that specify preferred numerical values of an attribute using, for example, intervals, such as indicating a desired laptop price range. A preference term (i.e. a preference that is valid according to the provided constructors) can also be composed of other preferences. This can be used to express complex preferences, indicating that two preferences are equally important or that one is more important than another, for example.

The BMO result set contains only the best matches with respect to the strict partial order of a preference P. It is a selection of options that are unordered. All options o, o′∈BMO have equal or incomparable values regarding the preference P. A preference query is defined by σ[P](R) declaratively as follows: σ[P](R)={o∈R|o[x _i]∈max(P ^R)}. σ[P](R) evaluates P against a database set R by retrieving all maximal values from P ^R. Preference queries behave non-monotonically, in that they are sensitive to the quality of a collection of values. In addition, operators used to specify combined preferences can be manipulated, according to their properties, in order to evaluate preference queries.

7.3 SPARQL Preference

SPARQL Preference (Siberski et al., Reference Siberski, Pan and Thaden2006), introduced in Table 15, is a query language used for querying semantic data. It is based extensively on the winnow operator (Chomicki, Reference Chomicki2003), which was described in Section 7.1.

Table 15

Reference card: SPARQL Preference

The input of this approach is a database with available options and an SPARQL Preference query, which is expressed in SPARQL with the PreferringClause extension, shown below.

Users can specify preferences that do not overwrite each other, by using the preferring clauses with the definitions of independent preferences separated by the ‘AND’ construct. In each of the preferences connected by the end construct, atomic preferences can be nested using the ‘CASCADE’ construct (which establishes a lexicographic preference among the specified preferences). Atomic preferences can express desired attribute preferences, or indicate that an attribute should be maximised or minimised.

The SPARQL Preference syntax allows the modelling of two kinds of preferences and two kinds of preference interactions, the semantics of which is described informally as follows. For a formal definition, we refer the reader elsewhere (Siberski et al., Reference Siberski, Pan and Thaden2006).

• ∙ Boolean preferences: boolean preferences are specified by a boolean expression over options (solutions) of an ontology defined in OWL DL (Patel-Schneider et al., Reference Patel-Schneider, Hayes and Horrocks2004). An option o ₁ dominates an option o ₂, if the boolean expression evaluates to true for o ₁, and false for o ₂.

• ∙ Scoring preferences: a scoring preference is specified by an expression, which evaluates to a number or a value in other SPARQL domains that have a total ordering. It expresses the preference for maximising or minimising a certain value. Therefore, an option o ₁ dominates o ₂, if o ₁ has a higher (lower) value than o ₂, when a HighestPreference (LowestPreference) is defined.

• ∙ Multi-dimensional preferences: this kind of preference interaction indicates that two preferences must be addressed in a combined form. For any solutions o ₁ and o ₂, the domination relation to combine independent preferences ${\succ}_{{\,\mid\,C1\,AND\,C2\,\mid\,}} $ establishes that o ₁ is dominated by o ₂ in neither C1 nor C2, and that o ₁ dominates o ₂ in either C1 or C2.

• ∙ Cascaded preference: a cascaded preference indicates that a preference C1 has a higher priority than C2. So, for any options o ₁ and o ₂, the domination relation to combine prioritised preferences ${\succ}_{{\,\mid\,C1\,CASCADE\,C2\,\mid\,}} $ states that either o ₁ dominates o ₂ according to C1, or they are incomparable according to C1, and o ₁ dominates o ₂ according to C2.

An example of a SPARQL query is shown below, in which hotels are being searched using an ontology whose prefix is ht. The query specifies a hard constraint (FILTER (?stars=pt : two || ?stars=pt:three)), which states that only hotels with two or three stars should be selected. The PREFERRING clause states that: (i) 3-star hotels are preferred and (ii) hotels whose check-in time is before 14:00, and from these, those with the lowest price are preferred.

SELECT ?hotel

WHERE {?hotel ht:has-stars ?stars .

?hotel ht : checkin ?checkin .

?hotel ht : price ?price.

FILTER (?stars=ht : two || ?stars=ht:three)}

PREFERRING

?stars=pt : three

AND

?checkin <= 14:00 CASCADE LOWEST(?price)

Based on the definition of dominance among options, a SPARQL Preference query returns as result all non-dominated options (skyline queries). If an option o ₁ dominates o ₂ according to a preference C1, but o ₂ dominates o ₁ according to a preference C2, both options are presented as the result of the query.

The major problem of this approach, and of the other query-based approaches, occurs when the best options are not found, according to the stated preferences, which is a typical situation, because trade-off among conflicting preferences is very common. For instance, consider a user that wants to buy a laptop and prefers to minimise price and maximise performance. The typical case here is that price increases as performance increases and, therefore, according to these preferences no laptop dominates another (there is none, or only a few laptops, that are more expensive and have worse performance), and consequently the approach cannot select among these laptops.