Preferences and contexts are fundamental aspects for deciding the best choices among possible options. We formalize the problem of propagating preferences from more generic to more speci c contexts and study the key properties of propagation within an algebraic framework.
Preferences and their in uence on choices have been studied in a variety of elds, including psychology, sociology, economics, arti cial intelligence, and data management. In all of the above elds, it is widely recognized that preferences highly depend on the context, as shown in the following example. Example 1. We are ordering food at a restaurant in Italy: normally, then, we prefer pasta to beef. In Sardinia, though, we enjoy \porceddu" more than pasta. During summer, however, our preferred choice is just a fresh salad. As in the example, we consider contexts as states (such as \Italy in summer") that can be compared via a generalization hierarchy, so that, say, \Sardinia" is more speci c than \Italy". Preferences naturally propagate along the hierarchy, from the more generic to the more speci c contexts (a preference de ned for Italy normally holds in any Italian place). Things are not that simple, though. Example 2. If we are in Sardinia in the summer, all the preferences given in Example 1 apply, since they refer to more generic contexts. Yet, the preferences de ned in \Sardinia" and \Italy in summer" should take precedence over those given for \Italy", whereas the preference in \Sardinia" is on a par with the preference in \Italy in summer". Then, porceddu and salad are the best alternatives, since no other food is preferable to them in the given context.
Our research provides a principled approach to context-aware preference propagation. We develop a general framework whose only requirements are as follows: { the contexts belong to a poset, i.e., a set C with a (strict) partial order relation C on its elements: c1 C c2 means that the context c1 is more speci c than the context c2 (and that c2 is more generic than c1); Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). This volume is published and copyrighted by its editors. SEBD 2020, June 21-24, 2020, Villasimius, Italy. { preferences de ne a strict partial order on the domain of objects O, where o1 o2 means that the object o2 is preferable to the object o1; { each stated preference is associated with one or more contexts. The basic properties of the propagation process, implicitly at the basis of earlier approaches and naturally arising from the observations made for Example 2, are: 1. coherence: preferences only propagate from more generic contexts; 2. fairness : unordered contexts do not take precedence over each other; 3. speci city : a more speci c context takes precedence over a more generic one. Building on these properties, we focus on three main problems: { (CFS) Determine whether there exist well-behaved (i.e., Coherent, Fair and
Speci c) methods for the propagation of preferences. { (OrdRel) E ciently determine the preference (order relation) between any two objects in a context according to a given propagation method. { (Best) Establish the best objects in c wrt. the preferences propagated to c. We tackle these problems through an axiomatization of the properties of propagation, and do so with an algebraic framework based on two abstract binary operators that express preference propagation by means of Preference Composition (PC) expressions: for unordered contexts, and B for ordered contexts. Example 3. A possible PC-expression for propagating preferences to \summer in Sardinia" (c4) is c4 B ppc2 c3q B c1q. Here, rst the preferences in \Sardinia" (c2) and those in \summer in Italy" (c3) are combined with , since the two contexts are unordered. The result is then combined with the preferences in \Italy" (c1) using B, since this context is more generic than both c2 and c3. Finally, the result is combined with c4 using B, since this is the most speci c context.
This paper summarizes some of the main ndings reported in [
Another notable achievement is a propagation method (OC) that somehow
provides the \ultimate" semantics for preference propagation. However, we refer
to [
We consider the well-known binary relation model for expressing preferences
over a domain of objects O [
Since k , it su ces to consider the pair x ; y, collectively called a preference structure. Let be one of ; ¡; ; k, where ¡ denotes the inverse of ; we say that the order relation between objects o1 and o2 is if o1 o2. Example 4. Let us consider the objects pasta, beef, salad, and porceddu. A possible preference structure over these objects is: beef pasta, beef salad, and pasta salad. In words, pasta and salad are both preferable to beef, whereas pasta and salad are indi erent. It follows that porceddu is incomparable with all other foods, i.e., porceddu k o, for o P tpasta; beef; saladu.
For a nite domain O, the best objects (i.e., maximal elements) in O according
to can be selected by the Best operator pOq to P O | Eo1 P O; o o1u.
For instance, according to the preferences of Example 4, the best objects are
pOq tpasta; salad, porcedduu. For any non-empty domain O, pOq is never
empty [
Throughout the paper we consider a context poset C and a domain O, and assume that each context c P C is associated with a preference structure x c; cy over O, called the ground preference structure in c. We also call x C ; C y tx c; cy | c P Cu a (preference structure) con guration over C. porceddu pasta
beef c1 salad salad porceddu beef pasta c2
salad porceddu c3 beef pasta c4 salad porceddu beef pasta Example 5. The context poset in Figure 1 reports the ground preference structures discussed in Example 2. In context c4 (\summer in Sardinia") all objects are indi erent. In context c1 (\Italy"), pasta is preferable to beef and beef to salad, while, in context c2 (\Sardinia"), porceddu is preferable to both pasta and beef, and pasta c2 beef; similarly, pasta c3 beef and pasta c4 beef.
Preferences propagate along the poset C, and we call complete preference relation in c, denoted by P c, the result of combining c with the ground preferences de ned in the other contexts in C, according to a propagation method P. Such a method also de nes how indi erence of objects is propagated to c, denoted by P c (and thus also the unordered relation P c and the incomparability relation P kc), thereby de ning the complete preference structure x P c; P cy.
In abstract terms, a propagation method P is a function that associates a context poset C, a con guration x C ; C y over C, and a target context c P C, with a complete preference structure x P c; P cy. In this paper, we focus on propagation methods implemented through algebraic expressions.
We shall now capture the basic ideas underlying preference propagation.
Let us denote with Ctcu the successor poset of c, i.e., poset C1 tc1 P C | c ¤C c1u, where c1 ¤C1 c2 i c1 ¤C c2. Context c1 is relevant for c when a change in the ground preferences in c1 may a ect the propagated preferences in c.
When combining preferences in unordered contexts, a cautious approach is to propagate only the preferences that hold in both contexts. The (more exible) way we undertake just aims to avoid the propagation of con icting preferences.
ordered contexts c1 and c2 in Ctcu, all o1; o2 P O and all con guration x C ; C y: if i) o2 c1 o1, ii) o1 c2 o2, iii) @cipc¤C ci C c1 _ c¤C ci C c2q ñ o1 ci o2, then o1 and o2 are unordered in the complete preferences for c, i.e., o1 P co2.
So, if c1 and c2 disagree on the order of o1 and o2 while o1 and o2 are indi erent in all the more speci c contexts, then o1 and o2 are not ordered in P c.
When combining ordered contexts, we give more importance to preferences that hold in contexts \closer" to the target context.
holds for every c1 in Ctcu, every o1; o2 P O and every con guration x C ; C y: if i) o1 c1 o2, ii) o1 ci o2 for each c ¤C ci C c1, and iii) it is either o1 c2 o2 or o1 c2 o2 for all c2 P Ctcu such that: 1) c2 is unordered wrt. c1, and 2) o1 c3 o2 @c3 such that c ¤C c3 C c2, then o1 P c o2.
Thus if o2 is preferable to o1 in c1 and such objects are indi erent in all the more speci c contexts, then this preference does indeed propagate to context c (preferences from more generic contexts are overridden by those in more speci c contexts). The preference must not propagate if this violates fairness. Example 6. Consider Figure 1. With a fair propagation method P, pasta and porceddu must be unordered in context c4, since pasta c2 porceddu whereas porceddu c3 pasta, and similarly for beef and porceddu, i.e., pasta P c4 porceddu and beef P c4 porceddu. If P is speci c, then pasta is preferable to beef in contexts c2, c3, and c4, i.e., beef P c2 pasta, beef P c3 pasta, and beef P c4 pasta. 4
We now characterize two binary operators, (for unordered contexts) and B (for ordered contexts), combining two ground preference structures x c1 ; c1 y and x c2 ; c2 y into a new preference structure, denoted x c1 c2 ; c1 c2 y and, respectively, x c1 B c2 ; c1 B c2 y. Clearly, is commutative but B is not. Both operators are associative and idempotent and both have the full indi erence structure ; x;; O Oy as identity element, i.e., contexts in which all elements are indi erent should not in uence the result. Axiomatically: De nition 4 ( operator). A operator satis es the following axioms, for all objects o1; o2 P O and all preference structures x 1; 1y; x 2; 2y; x 3; 3y: i) x 1; 1y x 2; 2y x 2; 2y x 1; 1y (commutativity) ii) px 1; 1y x 2; 2yq x 3; 3y x 1; 1y px 2; 2y x 3; 3yq (ass.) iii) x 1; 1y x 1; 1y x 1; 1y (idempotence) iv) x 1; 1y ; x 1; 1y (identity element) v) o1 1 o2; o2 2 o1 ñ po1 1 2 o2q ^ po2 1 2 o1q (fairness)
all objects o1; o2 P O and all preference structures x 1; 1y; x 2; 2y; x 3; 3y: i) px 1; 1yBx 2; 2yq Bx 3; 3y x 1; 1yB px 2; 2yBx 3; 3yq (ass.) ii) x 1; 1y B x 1; 1y x 1; 1y (idempotence) iii) x 1; 1y B ; ; B x 1; 1y x 1; 1y (identity element) iv) o1 1 o2 ñ o1 1 B 2 o2 (speci city)
Preference structures can be combined with and B to form a PC-expression.
De nition 6 (PC-expression). A PC-expression over C is any expression E of the form: E :: c | pE Eq | pE B Eq | K, where c is a context in C.
The base case is the name of some context c, denoting the preference structure x c; cy; one can also compose PC-expressions (i.e., preference structures) via and B, and denote the full indi erence structure ; via the K symbol.
PC-expressions can be used to compute complete preference structures (and thus to implement propagation methods). Fairness and speci city can be extended to PC-expressions in a straightforward way. 5
In this section we investigate on possible interpretations of the operators and B. We start with a general result about idempotent semirings. A semiring is an algebraic structure with an associative and commutative additive operator (like ) and an associative multiplicative operator (like B), which is both leftand right-distributive over addition. Let pPRO; ; Bq be an algebraic structure, where PRO denotes the set of all preference structures over a domain O. Then, with the additional hypothesis that B distributes over , pPRO; ; Bq would be a semiring in which both operators are idempotent, i.e., an idempotent semiring.
However, the following major result rules out the possibility of using idempotent semirings for providing an interpretation to the propagation operators, since distributivity of B over turns out to be incompatible with the axioms of speci city and fairness of the operators.
The cause of incompatibility of distributivity with the axioms of the operators lies only in assuming that B right-distributes over . For this reason, here we consider the case in which pPRO; ; Bq is an idempotent left near-semiring, that is, an algebraic structure satisfying all requirements of idempotent semirings except for right-distributivity of B. We still assume that B left-distributes over .
Consider Pareto and Prioritized composition as interpretations of and B. De nition 7 (Pareto and Prioritized comp.). Let x 1; 1y and x 2; 2y be two preference structures over a domain O. The Prioritized composition of x 1; 1y and x 2; 2y, written x 1; 1y Bx 2; 2y, is de ned as o1 1 B 2 o2 ô po1 1 o2q _ po1 2 o2 ^ o1 1 o2q o1 1 B 2 o2 ô o1 1 o2 ^ o1 2 o2: and their Pareto composition, written x 1; 1y ` x 2; 2y, is: o1 1 ` 2 o2 ô po1 1 o2 ^ o1 2 o2q_po1 1 o2 ^ o1 2 o2q_po1 1 o2 ^ o1 2 o2q o1 1 ` 2 o2 ô o1 1 o2 ^ o1 2 o2: where o1 and o2 are any two objects in O.
Intuitively, Prioritized composition gives precedence to preferences in 1, while preferences in 2 are used only if two objects are indi erent according to 1. Conversely, Pareto considers the two preference relations equally important. Example 7. Consider the objects: i) o1: a comedy with Favino, ii) o2: a comedy without Favino, iii) o3: a drama with Favino, iv) o4: a drama without Favino. Let 1 be the preference relation corresponding to \I prefer comedies to all other genres" and 2 to \I prefer movies with Favino to all other movies". If we consider 1, then o1 and o2 are both preferable to o3 and o4; also, o1 1 o2 and o3 1 o4. With 2, we have instead that o1 and o3 are both preferable to o2 and o4, with o1 2 o3 and o2 2 o4. Let Par 1 ` 2; then o2 Par o1, o3 Par o1, o4 Par o2, o4 Par o3, with o2 kPar o3. Let now Pri 1 B 2; then o4 Pri o3, o3 Pri o2, o2 Pri o1. The intuition is that o1 is always the best, since it satis es both preferences, while o4 is the worst one; o2 and o3 remain unordered if no priority is assumed between 1 and 2 (if ` is used), whereas o2 is preferred to o3 when 1 has priority over 2 (via B).
Both Prioritized and Pareto composition preserve strict partial orders (both yield
a strict partial order when applied to two strict partial orders), whereas this is
not guaranteed by replacing in their de nition with [
One may wonder whether other interpretations, besides the one based on ` and B, exist for the and B operators. Our answer is negative for an important class of operators, which we call independent of irrelevant objects. De nition 8 (IIO operator). An operator is independent of irrelevant objects (IIO) if, for any two objects o and o1 in O, the order relation between o and o1 according to the combined preference structure x 1; 1y x 2; 2y only depends on the order relation between o and o1 according to x 1; 1y and x 2; 2y. Thus, to determine the order relation between o1 and o2, an IIO operator does not need to consider any other objects. Both ` and B are IIO. The following theorems show that ` and B are the only possible IIO interpretations of and B: there is no other IIO interpretation of and B that satis es all the axioms.
operator.
6
Problem CFS is solved by exhibiting a propagation method, called Objectspeci c Cover (OC) propagation, based on PC-expressions using ` and B. It can be shown that no straightforward combination of the ground preferences in a context poset attains both fairness and speci city (each pair of objects seems to require a dedicated PC-expression). However, as a major result, OC implements propagation through a single PC-expression, denoted RGC pcq, for all pairs of objects; this is obtained, algebraically, by maximally \grouping on the right". De nition 9 (PC-expression for OC propagation). Let c1 P Ctcu and let tc1; : : : ; cku be immediately more speci c than c1. The expression RGC pc; c1q is dened as RGC pc; cq c; and RGC pc; c1q pRGC pc; c1q`: : :`RGC pc; ckqq Bc1 if c C c1: Let c^1; : : : ; c^n be maximal in Ctcu. Then: RGC pcq RGC pc; c^1q`: : :`RGC pc; c^nq. For the poset in Figure 1, RGC pc4q ppc4 Bc2q`pc4 Bc3qq Bc1 c4 Bpc2`c3q Bc1.
Ultimately, OC is the only method guaranteeing both fairness and speci city. Theorem 5. For any method P, if P c OC c then P is not speci c.
only depends on c and C, if OC c P c then P is not both fair and speci c. So, the OC semantics is \ nal" and therefore used to study the other problems.
For both OrdRel and Best, the exact complexity depends on the underlying context model as well as on the language used for expressing preferences. We remain parametric wrt. these aspects and assume that two context descriptions can be compared in Op q time, and that Op q is the complexity of determining the order relation of any two objects according to ground preferences in a context.
Examples are the context model in [5{7], for which Op q Opdq, where
d is the number of contextual dimensions and the language of [
Problem OrdRel can be solved by rst computing the PC-expression RG p q given by OC and then using it against the con guration to compute the complete
C c preferences. However, materializing RG p q may be ine cient due to repeated sub-expressions, leading, in the worst case, to a size of the PC-expression that is exponential in the number of contexts in Ctcu. Yet, via e cient bookkeeping structures, we can solve Problem OrdRel in Op|A| p wpAq qq time, where A is the subset of C with only the contexts with some ground preferences, and wpAq is its width. Problem Best requires at most OpN 2q comparisons for a set of N objects, leading to a complexity of Op|A| p N 2 pwpAq qqq. 7
In this paper we have discussed how preferences propagate when they depend on the context. We have proposed an algebraic model for expressing preference propagation, based on two abstract operators, and have shown that Pareto and Prioritized composition are the only natural possible interpretations satisfying all the required algebraic properties. Finally, we have studied the problem of e ciently computing the best objects according to the preferences propagated to a target context, and have shown that this can be done with polynomial complexity in all the main involved parameters.
Further research might analyze the application of the principles of preference
propagation to numerical preferences. An example of the possibilities opened by
this line of research is discussed in [