# an_axiomatic_approach_to_revising_preferences__4af8fb18.pdf

An Axiomatic Approach to Revising Preferences

Adrian Haret1, Johannes P. Wallner2

1 Institute for Logic, Language and Computation (ILLC), University of Amsterdam, The Netherlands 2 Institute of Software Technology, Graz University of Technology, Austria a.haret@uva.nl, wallner@ist.tugraz.at

We study a model of preference revision in which a prior preference over a set of alternatives is adjusted in order to accommodate input from an authoritative source, while maintaining certain structural constraints (e.g., transitivity, completeness), and without giving up more information than strictly necessary. We analyze this model under two aspects: the first allows us to capture natural distance-based operators, at the cost of a mismatch between the input and output formats of the revision operator. Requiring the input and output to be aligned yields a second type of operator, which we characterize using preferences on the comparisons in the prior preference. Preference revision is set in a logic-based framework and using the formal machinery of belief change, along the lines of the well-known AGM approach: we propose rationality postulates for each of the two versions of our model and derive representation results, thus situating preference revision within the larger family of belief change operators.

1 Introduction Preferences play a central role in theories of decision making as part of the mechanism underlying rational choice: they show up in economic models of rational agency (Sen 2017), as well as in formal models of artificial agents expected to interact with the world and each other (Domshlak et al. 2011; Rossi, Venable, and Walsh 2011; Pigozzi, Tsouki as, and Viappiani 2016). Since such interactions take place in dynamic environments, it can be expected that preferences change in response to new developments. In this paper we are interested in preference change occurring when new preference information becomes available and has to be taken at face value, thereby prompting a change in the prior preference. The change, we require, should preserve as much useful information from the prior preference as can be afforded. Preference change thus described is a pervasive phenomenon, arising in many contexts spanning the realms of both human and artificial agency. One prominent example is the distinguished tradition in Economics and Philosophy looking at examples of conflict between an agent s subjective preference (what we call here the prior preference π) and a second-order preference, often standing for a commitment or moral rule (what we call

Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Figure 1: Revising π by µ can be thought of a choice between which comparisons to keep and which to give up.

here the new preference information µ): subjective versus ethical preferences (Harsanyi 1955), lack of will, or akrasia (Jeffrey 1974), moral commitments (Sen 1977), secondorder volitions (Frankfurt 1988) and second-order preferences (Nozick 1994) all fall under this heading. The same challenge can occur in technological applications, from updating CP-nets (Cadilhac et al. 2015) to changing the order in which search results are displayed on a page in response to user provided specifications, as well as, more generally, in issues related to the alignment problem (Russell 2019): an artificial agent dealing with humans will have to learn their preferences, but as it cannot do so instantaneously, it must presumably do so in intermediate steps, revising along the way. The following example illustrates the problem in its most basic form.

Example 1. An online streaming service constructs a profile tailored to a particular user, according to which the arthouse movie (a) is preferred to the biopic (b), which is preferred to the comedy (c), and thus displays them in this order, encoded here with the preference statement π = (a b) (b c). When the user volunteers information to the effect that they find the comedy better than the arthouse movie, i.e., new information µ = (c a), the streaming service must revise its model of the user s preference: it has to place c before a and, in order to display the alternatives in a neat linear fashion, it must decide on a position to slot b into. Preferences π and µ, together with possible values for the revised result, e.g., π1 = (c a) (a b), π2 = (c a) (b c) and π3 = (c a) (c b) (b a), are depicted in Figure 1. Intuitively, π3 veers far (too far) away from the input preference π, in that it does not keep any of the still permissible comparisons contained in π, and should arguably be excluded,

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

while π1 and π2 are viable contenders. If we go further and insist on a decision between π1 and π2, we can take stock of the information relayed by either choice. Accepting π1 involves giving up the comparison of b over c, and we may surmise this is because the comparison of a over b is given up more reluctantly: preference of the arthouse movie over the biopic is more intense! Acceptance of π2 implies the opposite: b over c is now the stronger preference. Thus, restricting the output of revision to a single linear order suggests that the choice can be rationalized using an implicit preference order over the comparisons. Thus, whether it is the internal conflict of a moral agent or a content provider aiming for a better user experience, many cases of preference change involve a conflict between two types of preferences, one of which has priority. But, despite the fact that the problem is often signaled, a principled approach to how to handle it is often overlooked. Our purpose here is to formalize the type of reasoning illustrated in Example 1 by rationalizing preference change as a type of choice function that utilizes the information provided by the prior preference in adapting itself to new information. In particular, we want to combine techniques from standard belief change with Sen s insight that conflicts among preferences should be resolved using preferences over the preferences themselves (Sen 1977).

Contributions. We put forward two models for preference revision. The first, called here irresolute revision, is based on minimizing distance to the input preference, expressed as a formula, while allowing the output to be represented as a set of formulas, and is the approach that follows most closely the one from propositional revision. However, in an interesting departure from the propositional model, we show that insistence on representing the revised preference as a single formula, what we call resolute revision, requires us to give up appealing distance-based operators. The second model picks up where this result leaves off, and we present a mechanism for resolute revision based on an underlying preference relation over the adjacent comparisons of the prior preference, construed here as atomic elements that can be subject to change. In both cases we present desirable normative principles, in the AGM mould (Alchourr on, G ardenfors, and Makinson 1985), and derive representation results.

Related work. Previous work dealing with preference revision has studied preference change prompted by a change in beliefs (Bradley 2007; Lang and van der Torre 2008; Liu 2011). Here we abstract away from the source of new information, focusing exclusively on a mechanism for resolving conflicts between preferences. Other work (Cadilhac et al. 2015) describes preference change when preferences are represented using CP-nets (Boutilier et al. 2004), or dynamic epistemic logic (Benthem and Liu 2014), in the context of declarative debugging (Dell Acqua and Pereira 2005), or databases (Chomicki 2003), and therefore comes with additional structural constraints. The basic phenomenon of preference change has also been raised in explicit connection to belief change (Hansson 1995; Gr une-Yanoff and Hansson 2009; Gr une-Yanoff 2013), but a representation in terms of preferences on the comparisons present in the preference

orders, along the lines suggested here, has, to the best of our knowledge, not yet been given. Much existing work proceeds by putting forward some concrete preference revision mechanism, occasionally with a remark on the similarity to belief revision (Freund 2004; Chomicki and Song 2005; Liu 2011; Ma, Benferhat, and Liu 2012). Our work adds an analysis in terms of postulates and representation results. The framework studied here is inspired by propositional belief revision (Alchourr on, G ardenfors, and Makinson 1985; Katsuno and Mendelzon 1992; Nebel 1992), and the two problems are similar in spirit. The closest analogy for Section 3 is belief revision in fragments of propositional logic (Delgrande, Peppas, and Woltran 2018), while the equivalent for Section 4 would be an attempt to characterize propositional revision operators using orders on the atoms, with similar results derived in (Haret and Wallner 2021).

Outline. In Section 2 we introduce notation and the basic elements of our model. Section 3 looks at irresolute revision operators and Section 4 looks at resolute revision. Section 5 offers concluding remarks.

2 Preliminaries We assume a finite set A of alternatives, with |A| = n. For alternatives x, y A, we call the ordered pair (x, y) a comparison, and think of it as encoding the fact that the agent prefers x to y. For ease of reading we write xy instead of (x, y). A (strict) linear order ℓon A is a binary relation (i.e., a set of comparisons) on A such that (i) xx / ℓ, for any x A (irreflexivity), (ii) if xy ℓand yz ℓthen xz ℓ (transitivity), (ii) for any distinct x, y A, either xy ℓor yx ℓ(connectedness). We write ℓas the string x1 . . . xn, where xixj ℓ, for i < j, and denote by LA the set of linear orders over A. A strict partial order s on A is an irreflexive and transitive (not necessarily complete) binary relation on A. Note that irreflexivity and transitivity imply that if xy s then yx / s (antisymmetry). Note, also, that if ℓ1 and ℓ2 are linear orders on A, then ℓ1 ℓ2 is not guaranteed to be a linear order, though it is a strict partial order on A. An atomic preference statement has the form x y, for distinct alternatives x, y A. A preference statement π is a conjunction of atomic preference statements, with PA as the set of all preference statements over A. A linear order ℓ satisfies the atomic preference statement x y if xy ℓ; ℓ satisfies a preference statement π if it satisfies every atomic preference statement in π, in which case we say that ℓis a model of π. The set [π] of models of π is defined as [π] = {ℓ LA | ℓsatisfies π}. If Π = {π1, . . . , πn} is a set of preference statements, the set [Π] of models of Π is defined as [Π] = S 1 i n[πi], i.e., as the union of the models of the formulas in Π. A preference statement π (set of preference statements Π) is consistent if [π] = ([Π] = ). Example 2. For A={a, b, c}, π = (a b) (a c) is a preference statement indicating that a is preferred, once, to b and, second, to c. The set of models of π is [π] = {abc, acb}. Note that abc acb = {ab, ac}, i.e., the intersection of abc and acb is the partial order containing the comparisons that abc and acb have in common.

3 Irresolute Preference Revision An irresolute preference revision operator is a function : PA PA 2P A, taking as input two preference statements, typically denoted π and µ, and standing for the agent s prior and newly acquired preference information, respectively, and returning a set of preference statements, denoted π µ. The representation of the result as a set of formulas is a slight departure from established revision practice, but has precedent in belief change applied to formalisms other than propositional logic, e.g., in work on the aggregation of abstract Argumentation Frameworks (Delobelle et al. 2016). Intuitively, π µ can be interpreted as a range of options, all of which, together, represent the agent s adjusted preferences in light of new information µ. We will have occasion to reflect on the format of the result later on. In typical revision fashion, we want to identify a set of desirable normative principles that (irresolute) preference revision operators ideally satisfy. To this purpose we use an adapted version of the well-known AGM postulates (Alchourr on, G ardenfors, and Makinson 1985), or rather, their KM formulation (Katsuno and Mendelzon 1992): (Ri 1) [π µ] [µ]. (Ri 2) If π µ is consistent, then π µ = {π µ}. (Ri 3) If µ is consistent, then π µ is consistent. (Ri 4) If [π1]=[π2] and [µ1]=[µ2], then [π1 µ1] = [π2 µ2]. (Ri 5) [π µ1] [µ2] [π (µ1 µ2)]. (Ri 6) If [π µ1] [µ2] = , then [π (µ1 µ2)] [π µ1] [µ2]. Even though the underlying semantics of the formulas concerns linear orders, the intuition and mechanics behind the postulates is entirely similar to that of propositional revision, and we direct the reader to standard references for more details (Alchourr on, G ardenfors, and Makinson 1985; Katsuno and Mendelzon 1992; Ferm e and Hansson 2018). Owing to the blend of different formats we write the axioms in their semantic version (i.e., using the sets of models), rather than in the more familiar syntactic formulation (i.e., using entailment relations and conjunction operators), but their motivation is otherwise unchanged from the propositional case. It turns out, as expected, that axioms Ri 1 Ri 6 characterize a broad class of revision operators, one that can be described using the familiar device of total pre-orders (i.e., complete, transitive binary relations) on the set LA of linear orders and the notion of a preference assignment f, i.e., a function f : PA TA, where TA is the set of total preorders on LA. A preference assignment maps a preference statement π to a total preorder on linear orders, denoted here as π: the preferences on preferences mentioned in Section 1. Using established revision lingo (Katsuno and Mendelzon 1992), a preference assignment is faithful if it satisfies the following properties: (fi 1) If ℓ1, ℓ2 [π], then ℓ1 π ℓ2. (fi 2) If ℓ1 [π] and ℓ2 / [π], then ℓ1 <π ℓ2. (fi 3) If [π1] = [π2], then ℓ1 π1 ℓ2 iff ℓ1 π2 ℓ2. A faithful preorder π makes the models of π as the uniquely most preferred elements of π, regardless of the syntax of π. The characterization, then, proceeds as follows.

Theorem 1. An irresolute revision operator satisfies postulates Ri 1-Ri 6 iff there exists a faithful preference assignment mapping every preference statement π to a total preorder π such that [π µ] = min π[µ]. The proof of Theorem 2 is analogous to its equivalent version in propositional revision (Katsuno and Mendelzon 1992), with one notable exception, on which more shortly. An important device for generating concrete revision operators is a distance d between linear orders, i.e., a function d: LA LA R 0, such that d(ℓ1, ℓ2) = 0 if and only if ℓ1 = ℓ2. This is a minimal requirement on d, on top of which we will add more desirable properties later on. A typical distance we will use here is the Kendall tau distance dτ (Kendall and Gibbons 1990) defined as dτ(ℓ1, ℓ2) = |{xy ℓ1 | yx ℓ2}|, i.e., as the number of disagreements (inverted pairs of alternatives) between ℓ1 and ℓ2. Less discriminating, the drastic distance d D is defined as d D(ℓ1, ℓ2) = 0, if ℓ1 = ℓ2, and k > 0, otherwise. Given a distance d, the d-induced irresolute preference revision operator d is defined, for any preference statements π and µ, as a set of preference statements π d µ such that:

[π d µ] = argminℓ [µ] min ℓ [π] d(ℓ , ℓ),

i.e., a set of preference statements whose models add up to exactly those models of [µ] that minimize the Kendall tau distance to any model of π. We write τ and D for the dτand d D-induced revision operators, respectively. Note that D can be written as:

π D µ = {π µ}, if π µ is consistent, {µ}, otherwise.

Importantly, note that d-induced revision operators are welldefined, as any individual linear order ℓ= x1. . .xn is the sole model of the formula πℓ= (x1 x2) (xn 1 xn), and any set {ℓ1, . . . , ℓm} of linear orders is the set of models of the set {πℓ1, . . . , πℓm} of preference statements. Example 3. For A = {a, b, c} and π = (a b) (b c), µ = (c a), we have that [π] = {abc} and [µ] = {cab, cba, bca}. The Kendall tau distances between the model of π and the models of µ are dτ(abc, cab) = 2, dτ(abc, cba) = 3, dτ(abc, bca) = 2, and thus [π τ µ] = {cab, bca}. We can represent [π τ µ] using preference statements π1 = (c a) (a b) and π2 = (b c) (c a), noting that [π1] [π2] = {cab} {bca} = {cab, bca}, with π τ µ = {π1, π2}. Given a distance function d we can define the d-induced preorder d π by taking ℓ1 d π ℓ2 if minℓ [π] d(ℓ, ℓ1) minℓ [π] d(ℓ, ℓ2), and it is straightforward to see that the dτand d D-induced preorders τ π and D π , respectively, are faithful; this, via Theorem 1, implies that τ and D satisfy axioms Ri 1 Ri 6. Throughout all this, though, a key detail is the fact that for any set L of linear orders we can find, as described earlier, a set Π of preference statements such that [Π] = L. At the beginning of this section we offered an intuition of what Π stands for, but we may now add to a concern about this design choice, as it introduced a mismatch between the input and output. This makes it harder, for instance, to apply a revision operator iteratively. It would be

desirable, therefore, to represent [π µ] as a single preference statement, rather than as a set. However, as Proposition 1 below shows, this is possible only in special circumstances. To state Proposition 1, we introduce one additional piece of notation. If s is a strict partial order, the linear order ℓis a completion of s if s ℓ, i.e., if ℓpreserves all the comparisons in s. We denote by comp(s) the set of completions of s. Proposition 1. If L LA, then there exists π PA such that [π] = L iff L = comp(T ℓ L ℓ).

Proof. Note that T ℓ L ℓis a strict partial order, which we denote by s L. Thus, if L = comp(T ℓ L ℓ), then π = V xy s L(x y) is the preference statement we are looking for, as [π] = L. Conversely, suppose there exists some π PA such that [π] = L. Take, first, a linear order ℓ comp(T ℓ L ℓ): we claim that ℓ [π]. To see why this is the case, assume that ℓ/ [π]: this implies that there exists a comparison xy ℓ, such that its opposite yx is implied by π. The latter fact implies that yx ℓ , for every ℓ [π], which further implies that yx T ℓ L ℓ. Thus yx ℓ , for every ℓ comp(T ℓ L ℓ): a fortiori, yx ℓ, which is a contradiction. We have thus obtained that comp(T ℓ L ℓ) L. Next, take ℓ L. Since ℓsatisfies every comparison in π, we get that T ℓ L ℓ ℓ, and thus ℓ comp T ℓ L ℓ , showing that L comp(T ℓ L ℓ).

Thus, Proposition 1 shows that a set L of linear orders can be encoded by a preference statement π only if L satisfies what we may think of as a closure operation: L must be closed under completions of the strict partial order that contains the comparisons common amongst all the orders in L.1 Coming back to the issue of whether outputs of distance-based irresolute preference revision operators can be squeezed into PA, we see that this result spells trouble. Example 4. For A, π and µ as in Example 3, we get that [π τ µ] = {cab, bca}. Note that cab bca = {ca}, and comp({ca}) = {cab, cba, bca} = [π τ µ]. Thus, using Proposition 1, there is no preference formula π PA such that [π τ µ] = [π ]. In other words, we cannot have the output of a preference revision operator be a single preference statement and, at the same time, hold on to τ. And it turns out that, under mild assumptions on the distance function d, this situation is unavoidable for any distance-based revision operator d. To state these properties, we introduce a number of new notions. A renaming r is a bijective function r: A A, with the renaming r(ℓ) of ℓ= x1. . .xn defined as r(x1). . .r(xn). For linear orders ℓ1 = x1. . .xm and ℓ2 = xm+1. . .xn on distinct alternatives, the concatenation ℓ1ℓ2 of ℓ1 and ℓ2 is the linear order defined as ℓ1ℓ2 = x1. . .xmxm+1. . .xn. The properties we expect from the distance function d are:

1This issue does not show up in propositional revision, where any set of truth-value assignments can be represented by a formula, but it does occur in belief change in fragments of propositional logic (Delgrande, Peppas, and Woltran 2018), or with respect to Argumentation Frameworks (Diller et al. 2015; Haret, Wallner, and Woltran 2018).

(D1) d(ℓ1, ℓ2) = d(ℓ2, ℓ1). (D2) d(ℓ1, ℓ2) = d(r(ℓ1), r(ℓ2)). (D3) If dτ(ℓ1, ℓ2) < dτ(ℓ1, ℓ3), then d(ℓ1, ℓ2) < d(ℓ1, ℓ3). (D4) d(ℓℓ1ℓ , ℓℓ2ℓ ) = d(ℓ1, ℓ2). Property D1 requires d to be symmetric; D2 requires d to be invariant under renamings; D3 is a monotonicity condition requiring the distance function d to be consistent with the tau distance dτ, i.e., the more adjacent pairs of alternatives we flip, starting with ℓ1, the further away from ℓ1 we end up; D4 requires the distance between ℓ1 and ℓ2 to depend only on the distinct sections of ℓ1 and ℓ2. Finally, we say that an (irresolute) preference revision operator is single-statement compliant if for any set A of alternatives and preference statements π, µ PA, there exists a preference statement π PA such that [π µ] = [π ]. Under these conditions, we can prove the following result. Theorem 2. If a distance function d satisfies properties D1 D4, the operator d is not single-statement compliant.

Proof. Assume d is single-statement compliant and take A = {a, b, c}. Using the renaming r(a) = c, r(b) = a and r(c) = b, we have that:

d(abc, bca) = d(cab, abc) by D2, applying r = d(abc, cab). by D1

By property D3, it holds that d(abc, bca) < d(abc, cba) and d(abc, cab) < d(abc, cba). Consider preference statements π = (a b) (b c) and µ = (c a) with [π] = {abc} and [µ] = {cab, cba, bca}. Using the just derived distance relationships we infer that [π d µ] = {bca, cab}. By the assumption that d is single-statement compliant there must exist some preference statement π PA such that [π ] = {bca, cab}. By Proposition 1, however, this leads to a contradiction. Using property D4, we can extend this result to any alphabet with at least three elements.

Note that dτ satisfies properties D1 D4, while d D satisfies all but D3 and thus does not fall within the scope of Theorem 2. However, d D does satisfy a weaker version of D3 where the inequality is non-strict, and a slightly more involved argument shows that d D is the only distance function that satisfies these properties and is single-statement compliant for three alternatives. In fact, we conjecture that D is the only irresolute preference revision operator that is singlestatement compliant, for any number of alternatives.

4 Resolute Preference Revision In the wake of Section 3, we want to understand how to align the formats of the prior and revised preference information. In this section we show that this is possible by assuming that the user has some preference structure on the atomic elements of its prior preference. We focus on the case in which both prior and revised preferences encode single linear orders, which makes sense in light of Example 1, where the alternatives need to be sequentially displayed, e.g., on a webpage. As users cannot be expected to be exhaustive in the information they provide, we continue to allow µ to be a regular (not necessarily complete) preference statement.

A preference statement is complete if it has exactly one model, and we denote by CA the set of complete preference statements on A. A resolute preference revision operator is a function : CA PA CA, taking as input a complete and a standard preference statement, typically denoted by λ and µ, respectively, and returning a complete preference statement, denoted by λ µ. Since λ µ has, by definition, exactly one linear order ℓas model, we often use ℓand {ℓ} interchangeably. The road to representation starts by laying down some additional items of notation. If C is a set of comparisons on A, the transitive closure C+ of C is the smallest set such that (i) C C+ and (ii) if xy, yz C+, then xz C+. Intuitively, C+ is a transitive relation on A that may, or may not, contain cycles between alternatives. If µ is a preference statement on A, the set Cµ of comparisons of µ is defined as Cµ = {xy A2 | x y is an atomic preference in µ}, i.e., Cµ contains the comparisons explicitly sanctioned by µ, while C+ µ adds the comparisons inferred by transitivity. For a complete preference statement λ, C+ λ is, by definition, a linear order: the unique model of λ. If [λ] = {x1. . .xn}, then xixi+1, for 1 i n 1 is an adjacent comparison of λ, with Aλ being the set of adjacent comparisons of λ. Adjacent comparisons are the basic atoms we will take as the basis for the preference relations guiding resolute revision operators. If µ is a preference statement, a λ-model of µ is a linear order ℓ such that ℓ = (Cµ C)+

for some set of comparisons C C+ λ . Intuitively, a λ-model of µ is a linear order obtained by adding to µ some of the comparisons expressed, either explicitly or implicitly, by λ. We write [µ]λ for the set of λ-models of µ. Note that [µ]λ = if [µ] = : if the order between two alternatives x and y is not decided by µ, then we can complete the order by reaching into C+ λ , since C+ λ is a linear order and either xy C+ λ or yx C+ λ . If λ CA and µ PA, the cycle-free part CF µ(λ) of λ with respect to µ is defined as CF µ(λ) = {xy C+ λ | xy is not involved in a cycle in C+ λ µ}, i.e., the comparisons in λ (both explicit and implicit) that are not part of a cycle in the relation obtained when adding µ to λ. Example 5. Take λ = (a b) (b c) (c d), µ = (c a), with [λ] = {abcd}, [µ] = {cabd, cbad, bcad, cadb, . . . }, C+ λ = {ab, ac, ad, bc, bd, cd}, Cµ = C+ µ = {ca}. The adjacent comparisons of λ are Aλ = {ab, bc, cd}. The conjunction of λ µ contains a cycle between a, b and c, hence CF µ(λ) = {ad, bd, cd}. Note, next, that cabd = (Cµ CF µ(λ) {ab})+, i.e., it is the linear order obtained by adding the comparison ab abcd as well as the cyclefree part of λ to ca, and then taking the transitive closure of the resulting set of comparisons. Similarly, bcad is obtained by adding bc abc to Cµ and CF µ(λ). Adding to Cµ any set of comparisons from abc that includes ac yields a cycle between a, b and c and is therefore not fit to construct a linear order. Adding to Cµ is also no good, as the result is not complete. Thus, [µ]λ = {cabd, bcad}. The notion of a λ-model is important in allowing us to formulate desirable axioms for resolute preference revision:

(Rr 1) If µ is consistent, then [λ µ] [µ]λ.

(Rr 2) If µ is inconsistent, then λ µ = λ. (Rr 3) If [λ1]=[λ2] and [µ1]=[µ2], then [λ1 µ1] = [λ2 µ2]. (Rr 4) If (λ µ1) µ2 is consistent, then [(λ µ1) µ2] = [λ (µ1 µ2)]. Though built on familiar intuitions, axioms Rr 1 Rr 4 are particular enough to warrant discussion. Note, first, that λ µ being a preference statement allows us to connect it to other preference statements via the conjunction operator . Then, given that λ µ is a complete statement by definition, Rr 1 requires it to define a λ-model of µ, i.e., to be obtained using only comparisons from λ in addition to those of µ: a restriction meant to prevent λ µ from introducing comparisons not justified by their presence in λ, as illustrated below. Example 6. For λ and µ as in Example 5 we obtained [µ]λ = {cabd, bcad}. The linear order cbad [µ] is not desirable as a candidate for λ µ, as it is obtained by adding cb and ba to ca (in addition to the cycle-free comparisons): however, neither cb nor ca are in abcd, i.e., their addition is unjustified based on the prior preference information. Axiom Rr 2 ensures that λ µ is defined even when µ contains a cycle. Together, axioms Rr 1 and Rr 2 have the additional desirable effect of ensuring that λ µ holds on to any comparisons of λ not involved in a cycle with µ, or not explicitly ruled out by µ. Proposition 2. If λ CA µ PA, and xy C+ λ such that yx C+ µ and there is no cycle involving xy in C+ λ µ, then, if is a resolute preference revision operator satisfying axioms Rr 1 and Rr 2, it holds that xy C+ λ µ.

Proof. Assuming that xy / C+ λ µ, we conclude, by completeness of C+ λ µ, that yx C+ λ µ. By axiom Rr 1, we know that C+ λ µ = (Cµ C)+, for some set of comparisons in C+ λ . We cannot have that yx Cµ, or even that yx C+ µ , as this would contradict our assumptions. It must be the case, then, that yx is obtained as the transitive closure of comparisons yz1, x1z2, . .. , yzt, with some comparisons coming from λ and others from µ. But, since by assumption xy λ, we now have a cycle in C+ λ µ involving xy, which is again a contradiction given our assumptions.

Overall, axioms Rr 1 and Rr 2 guarantee that λ µ always produces a result of the right format, uses only information present in µ and λ to obtain it, and, by Proposition 2, preserves the acyclic part of λ µ, which we may reasonably think of as uncontroversial and deserving to be withheld. Thus, through the last observation, axioms Rr 1 and Rr 2 recover another mainstay of AGM revision: if new information µ is consistent with prior information λ, the result is, reassuringly, λ µ λ, since in this case none of the comparisons of λ is involved in a cycle with µ. Axiom Rr 3 expresses the familiar notion of irrelevance of syntax. Axiom Rr 4 can be thought of as a compressed version of axioms Ri 5 and Ri 6 and expresses the idea that if µ2 does not contradict λ µ1, then revising by µ1 and adding µ2 is equivalent to revising by (µ1 µ2). Having presented the axioms, we want to move on now to a preference-driven mechanism for performing preference

revision a mechanism that uses, as advertised, preferences over the adjacent comparisons of λ. We do this through a resolute preference assignment, i.e., a function f : CA TA mapping every λ CA to a strict linear order <λ on the set Aλ of adjacent comparisons of λ. We further require <λ to be insensitive to syntax, i.e., to satisfy property fi 3 adapted in the obvious way to the present context, in which case we call the assignment faithful. Intuitively, a faithful ranking <λ requires the adjacent comparisons of λ to be ranked in a linear fashion, with the intention of formalizing a revision mechanism that uses this ranking in order to iteratively construct the new preference order: we read a statement like xixi+1 <λ xjxj+1 as saying that xixi+1 is more intensely held, or less eagerly given up, than xjxj+1. We use preferences on adjacent comparisons under the assumption that they are basic in the sense that they cannot be inferred by transitivity using other comparisons in λ, and therefore likely to be the result of explicit information. Given a linear order <λ, level i of Aλ according to <λ, denoted levi(<λ), is defined as follows:

lev1 <λ(Aλ) = min <λ (Aλ),

levi+1 <λ (Aλ) = min <λ

1 j i levj <λ(Aλ) .

Intuitively, level i contains the ith best comparison on A according to <λ. Note that the levels of <λ partition Aλ and, since Aλ is finite, there exists an index j > 0 such that levi <λ(Aλ) = , for all i j. The addition operator addi <λ(µ) is defined as follows:2

add0 <λ(µ) = (Cµ CF µ(λ))+,

addi <λ(µ) =

( addi 1 <λ (µ) (levi <λ(Aλ) +, if acyclic, addi 1 <λ (µ), otherwise.

Intuitively, add starts with the comparisons of µ, plus the cycle-free part of λ with respect to µ, and, at every further step i > 0, tries to add the comparison on level i: if the resulting set of comparisons does not contain a cycle (by taking its transitive closure) the operation is successful, and the new comparison is added; if not, the addition operator does nothing. Since the addition of new comparisons follows the order <λ, this ensures that more highly valued comparisons are considered before lower quality ones. Note that add0 <λ(µ) add1 <λ(µ) . . . . Also note that the number of non-empty levels of Aλ is finite and the addition operation eventually reaches a fixed point, i.e., there exists j 0 such that addi <λ(µ) = addj <λ(µ), for any i j. We denote by add <λ(µ) the fixed point of this operator and first check that it actually results a linear order. Proposition 3. If λ CA, µ PA, and <λ is a faithful linear order on Aλ, then add <λ(µ) is a strict linear order.

Proof. The relation add <λ(µ) is irreflexive and transitive by construction. Consider, next, two distinct alternatives x and

2The addition operator is different from the eponymous operation in (Benferhat et al. 1993).

add0 <λ (µ) d

add1 <λ (µ) d

add <λ (µ) d

Figure 2: Revision according to a faithful linear order <λ. Lower comparisons are better. Comparisons inferred by transitivity are omitted.

y. If xy (or yx) is in C+ µ or CF µ(λ) then xy (or yx) is in add0 <λ(µ) add <λ(µ). If neither xy, nor yx, is in either of C+ µ or in CF µ(λ), then we can assume wlog that xy is implied by λ (either xy or yx has to be implied by λ, since λ describes a linear order), and thus there exist t 0 adjacent comparisons z0z1, . .. , zt 1zt in λ, z0 = x and zt = y, that imply xy by transitivity. By our present assumption, z0z1, . .. , zt 1zt are involved in a cycle with the edges of µ. Since they are linearly ordered in <λ, the addition operator goes through them successively: t 1 out of them eventually get chosen, and thus either xy or yx ends up inferred at some point. In all cases, though, either xy or yx is in add <λ(µ), which shows that add <λ(µ) is connected.

The proof of Proposition 3 shows that add <λ(µ) is not just a linear order, but that it is obtained using only comparisons from µ and λ, i.e., that it is a λ-model of µ. This observation will come in handy later.

Corollary 1. If λ CA, µ PA, and <λ is a faithful linear order on Aλ, then add <λ(µ) [µ]λ.

For now, Proposition 3 gives us all we need to define a resolute preference revision operator: the f-induced preference revision operator f is defined as:

[λ f µ] = {add <λ(µ)}.

Example 7. Take λ and µ as in Example 5, with [λ] = {abcd} and C+ µ = {ca}, and <λ depicted in Figure 2. The order λ µ is assembled in steps, starting with the comparisons in µ and the cyclic-free part of λ: Cµ CF µ(λ) = ({ca} {ad, bd, cd})+, depicted in Figure 2. Then, in the first step ab is added; the second step tries to add bc, but finds that this leads to a cycle with the previously added comparisons; the third step adds cd, which had been added already, and the process stops. The result is [λ f µ] = {cabd}.

The next step is to show that the constructive procedure using the addition operator fits within the framework delineated by axioms Rr 1 Rr 4. This involves proving a representation result consisting of two parts: on the one hand, we show that an f-induced revision operator satisfies axioms Rr 1 Rr 4; in the second part, we show that a resolute operator assumed to satisfy axioms Rr 1 Rr 4 can be rationalized using a resolute faithful assignment. This involves reconstructing <λ one pair of adjacent comparisons at a time, and involves

µxixi+1, xjxj+1

Figure 3: To force a choice between xixi+1 and xjxj+1 we revise by µxixi+1,xjxj+1: the comparison that survives is assumed to be the more preferred.

solving an issue taken for granted in propositional revision: how to decide which is better of two adjacent comparisons? We address this issue by creating a spcial type of preference order that, when added to λ, forces a choice between any two adjacent comparisons. Thus, if ℓ= x1. . .xn is the model of λ and xixi+1 and xjxj+1 are adjacent comparisons in ℓ, with i < j, the preference statement µxixi+1,xjxj+1 is defined as:

µxixi+1, xjxj+1 =

i+1 s j 1 (xs xs+1)

j+1 t i 1 (xt xt+1),

with the convention that xsxs is ignored, if it occurs, and that indices are computed modulo n, i.e., xn+k stands for xk. Intuitively, µxixi+1,xjxj+1 defines a partial order that includes the paths from xi+1 to xj and from xj+1 to x1 in λ (see Figure 3). Under the assumption that revision has to create a λ-model of µ, the gadget µxixi+1,xjxj+1 forces us to make a choice between xixi+1 and xjxj+1.

Proposition 4. If is a resolute preference revision operator satisfying axioms Rr 1 and Rr 2, then exactly one of xixi+1 and xjxj+1 is in x1 λ µxixi+1,xjxj+1.

Proof. At least one of xixi+1 and xjxj+1 must be added, since they are adjacent comparisons and cannot be otherwise inferred from other comparisons through transitivity; but it is impossible to add both, as this would lead to a cycle.

Thus, exactly one of the two comparisons ends up in λ µxixi+1, xjxj+1: the one, we want to say, that is held more intensely. With this we can finally prove our main result.

Theorem 3. A resolute preference revision operator satisfies axioms Rr 1 Rr 4 iff there exists a resolute faithful assignment mapping every complete preference statement λ to a linear order <λ on Aλ such that [λ µ] = {add <λ(µ)}.

Proof. For one direction we show that if f is a resolute faithful assignment, the f-induced operator f satisfies the axioms. Corollary 1 shows that f satisfies axioms Rr 1 and Rr 2. Axiom Rr 3 follows using the insensitivity to syntax of <λ. For axiom Rr 4 note that if (λ µ1) µ2 is consistent, then all the comparisons in µ2 are in λ µ1, since the latter encodes

a linear order. This means that all the comparisons in λ that get added to µ1 to form λ µ1 can be added to µ2 as well. For the other direction take a resolute operator satisfying all the postulates, and define <λ on Aλ as follows: xixi+1 <λ xjxj+1 if xixi+1 λ µxixi+1,xjxj+1. Axioms Rr 1 and Rr 2 imply, via axioms Rr 1 Rr 2, that <λ is a strict, total order on Aλ. To show that <λ is transitive, take three adjacent comparisons such that xixi+1 <λ xjxj+1 <λ xkxk+1. From the facts that xixi+1 λ µxixi+1,xjxj+1 and that xjxj+1 λ µxjxj+1,xkxk+1 we infer, using axiom Rr 4 that xixi+1 µxixi+1, xjxj+1, xkxk+1, where xixi+1 µxixi+1, xjxj+1, xkxk+1 is a preference statement defined, as expected, as a cycle going from x1 to xn to x1, from which we remove comparisons xixi+1, xjxj+1 and xkxk+1. Then, by adding xjxj+1 to xixi+1 µxixi+1, xjxj+1, xkxk+1, we infer, again using axiom Rr 4, that xixi+1 λ µxixi+1, xkxk+1. For the final step, we have to show that [λ µ] = {add <λ(µ)}. Assume, to the contrary, that there exists xy C+ λ µ and that xy / add <λ(µ). This implies that yx add <λ(µ). We further infer that neither xy nor yx is in C+ µ (if yx C+ µ , then xy could not be in C+ λ µ, which has to be, by axiom Rr 1, a λ-model of µ). Then either yx gets added by the addition operator directly, as an adjacent comparison of λ, or is inferred bt transitivity. If it is added as an adjacent comparison of λ, we first note that it must be involved in a cycle with µ (otherwise it would be in C+ λ µ, per Proposition 2), and that it must have priority in <λ over some other adjacent comparison zt, which must be sacrificed in order to break the cycle, i.e., yx <λ zt. But, from the fact that xy C+ λ µ we can infer, using axiom Rr 4, that xy C+ λ µyx,zt, which then implies that zt <λ yx, a contradiction. If yx is inferred by transitivity rather than added directly, the reasoning is similar.

5 Conclusions We have presented two models of preference change. The first works by minimizing distances, and was found to be difficult to square with the requirement that prior and revised preference information are of the same type. The second, advanced in part to address this issue, is based on the idea that revising a preference λ goes hand in hand with having preferences over the comparisons inherent in λ. In formalizing these two approaches we believe to have provided a rigorous formal treatment to intuitions found elsewhere in the literature (Sen 1977; Gr une-Yanoff and Hansson 2009). There is also ample space for future work, in particular with respect to understanding the distance functions underlying operators that are both axiom-abiding and that satisfy desirable constraints on the format of output. The initial work in Section 3 shows that combining these two types of requirements is a delicate matter, and further research is certain to yield interesting possibility or impossibility results. With respect to the framework of Section 4, an obvious way forward is to relax the assumption of linearity on the comparisons of λ in order to characterize choice mechanisms operating on a more general form of preference structure.

Acknowledgments We are grateful to the anonymous referees. This work was funded by NWO project OND1362710 and by the Austrian Science Fund (FWF): P30168.

References Alchourr on, C. E.; G ardenfors, P.; and Makinson, D. 1985. On the Logic of Theory Change: Partial Meet Contraction and Revision Functions. The Journal of Symbolic Logic, 50(2): 510 530. Benferhat, S.; Cayrol, C.; Dubois, D.; Lang, J.; and Prade, H. 1993. Inconsistency management and prioritized syntaxbased entailment. In Proceedings of IJCAI 1993, 640 645. Benthem, J.; and Liu, F. 2014. Deontic Logic and Preference Change. If Co Log Journal of Logics and their Applications, 1(2): 1 46. Boutilier, C.; Brafman, R. I.; Domshlak, C.; Hoos, H. H.; and Poole, D. 2004. CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements. Journal of Artificial Intelligence Research (JAIR), 21: 135 191. Bradley, R. 2007. The kinematics of belief and desire. Synthese, 156(3): 513 535. Cadilhac, A.; Asher, N.; Lascarides, A.; and Benamara, F. 2015. Preference Change. Journal of Logic, Language and Information, 24(3): 267 288. Chomicki, J. 2003. Preference formulas in relational queries. ACM Trans. Database Syst., 28(4): 427 466. Chomicki, J.; and Song, J. 2005. Monotonic and Nonmonotonic Preference Revision. In Proc. IJCAI 2005 Multidisciplinary Workshop on Advances in Preference Handling. Delgrande, J. P.; Peppas, P.; and Woltran, S. 2018. General Belief Revision. Journal of the ACM (JACM), 65(5): 29:1 29:34. Dell Acqua, P.; and Pereira, L. M. 2005. Preference Revision Via Declarative Debugging. In Portuguese Conference on Artificial Intelligence, 18 28. Springer. Delobelle, J.; Haret, A.; Konieczny, S.; Mailly, J.; Rossit, J.; and Woltran, S. 2016. Merging of Abstract Argumentation Frameworks. In Proceedings KR 2016, 33 42. Diller, M.; Haret, A.; Linsbichler, T.; R ummele, S.; and Woltran, S. 2015. An Extension-Based Approach to Belief Revision in Abstract Argumentation. In Proceedings of IJCAI 2015, 2926 2932. Domshlak, C.; H ullermeier, E.; Kaci, S.; and Prade, H. 2011. Preferences in AI: An Overview. Artificial Intelligence, 175(7-8): 1037 1052. Ferm e, E. L.; and Hansson, S. O. 2018. Belief Change: Introduction and Overview. Springer Briefs in Intelligent Systems. Springer. Frankfurt, H. G. 1988. Freedom of the Will and the Concept of a Person. In What is a person?, 127 144. Springer. Freund, M. 2004. On the revision of preferences and rational inference processes. Artificial Intelligence, 152(1): 105 137.

Gr une-Yanoff, T. 2013. Preference change and conservatism: comparing the Bayesian and the AGM models of preference revision. Synthese, 190(14): 2623 2641. Gr une-Yanoff, T.; and Hansson, S. O. 2009. From Belief Revision to Preference Change. In Preference Change: Approaches from Philosophy, Economics and Psychology, 159 184. Springer. Gr une-Yanoff, T.; and Hansson, S. O., eds. 2009. Preference Change: Approaches from Philosophy, Economics and Psychology, volume 42 of Theory and Decision Library A. Springer. Hansson, S. O. 1995. Changes in preference. Theory and Decision, 38(1): 1 28. Haret, A.; and Wallner, J. P. 2021. An AGM Approach to Revising Preferences. In Proceedings of NMR 2021, 41 50. Haret, A.; Wallner, J. P.; and Woltran, S. 2018. Two Sides of the Same Coin: Belief Revision and Enforcing Arguments. In Proceedings IJCAI 2018, 1854 1860. Harsanyi, J. C. 1955. Cardinal Welfare, Individualistic Ethics, and Interpersonal Comparisons of Utility. Journal of Political Economy, 63(4): 309 321. Jeffrey, R. C. 1974. Preference among preferences. Journal of Philosophy, 71(13): 377 391. Katsuno, H.; and Mendelzon, A. O. 1992. Propositional Knowledge Base Revision and Minimal Change. Artificial Intelligence, 52(3): 263 294. Kendall, M.; and Gibbons, J. D. 1990. Rank Correlation Methods. New York: Oxford University Press. Lang, J.; and van der Torre, L. W. N. 2008. Preference Change Triggered by Belief Change: A Principled Approach. In Proceedings of LOFT 8, 86 111. Liu, F. 2011. Reasoning About Preference Dynamics, volume 354 of Synthese Library. Springer. Ma, J.; Benferhat, S.; and Liu, W. 2012. Revising Partial Pre-Orders with Partial Pre-Orders: A Unit-Based Revision Framework. In Proceedings of KR 2012, 633 637. Nebel, B. 1992. Syntax-Based Approaches to Belief Revision. In G ardenfors, P., ed., Belief Revision, 52 88. Cambridge: Cambridge University Press. Nozick, R. 1994. The Nature of Rationality. Princeton University Press. Pigozzi, G.; Tsouki as, A.; and Viappiani, P. 2016. Preferences in artificial intelligence. Annals of Mathematics and Artificial Intelligence, 77(3-4): 361 401. Rossi, F.; Venable, K. B.; and Walsh, T. 2011. A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers. Russell, S. 2019. Human Compatible: Artificial Intelligence and the Problem of Control. Penguin. Sen, A. K. 1977. Rational Fools: A Critique of the Behavioral Foundations of Economic Theory. Philosophy & Public Affairs, 317 344. Sen, A. K. 2017. Collective Choice and Social Welfare: Expanded Edition. Penguin UK.