A Non-monotonic Logic for Specifying and Querying Preferences

1 Introduction

Preferences are becoming of greater interest in many areas of artificial intelligence, such as knowledge representation, multiagent systems, constraint satisfaction, decision making, and decision-theoretic planning. In the logic of preference there is a debate when a set of preferences should be consistent. For example, Bacchus and Grove [1996] criticize ceteris paribus preferences, because {p > ¬p, ¬p ∧ q > p ∧ q} should be consistent, and they criticize most existing logics of preference, because {p > ¬p, q > ¬q, ¬(p ∧ q) > p ∧ q} should be consistent. In order not to restrict the use of the logic of preference, we propose a minimal logic of preference in which any set of specified preferences is consistent. To make it useful for practical applications, we extend this logic to specify preferences with a logic to query preferences, and with a nonmonotonic reasoning mechanism.

2 New semantics for the logic of preference

We introduce a logic of preference that distinguishes between specifying and querying, inspired by preference-based deontic logic [van der Torre and Tan, 2000]. We define two types of preference statements, where p>!q can be read as "it is specified that p is preferred to q" and p>?q can be read as "the result of the query states that p is preferred to q."

Definition 1 (Language) Given a set A = {a1, . . . , an} of propositional atoms, we define the set L0 of propositional formulas and the set L of preference formulas as follows.

Moreover, disjunction ∨, material implication → and equivalence ↔ are defined as usual. We abbreviate formulas of the preference logic using the following order on logical connectives: ¬ | ∨, ∧ | >!,>? |→,↔. For example, ¬p>!q ∧ r is short for (¬p>!(q ∧ r)).

Typically many conflicts arise during the specification of preferences. Our logic of preference represents any set of preferences in a consistent way, which is achieved in two steps. First, we do not use a total pre-order on worlds in the semantics, but a partial pre-order on worlds, i.e., a reflexive and transitive relation. Incomparable worlds indicate some kind of conflict among these worlds. Secondly, and more

Leendert van der Torre

CWI Amsterdam and Delft University of Technology The Netherlands torre@cwi.nl

originally, we formalize a preference p>!q as the absence of a q world that is preferred over a p world.

Definition 2 (Specifying) Let W be the set of propositional interpretations of L0, and ⪰ a partial pre-order on W. We write w ≻ w′ for w ⪰ w′ without w′ ⪰ w, and |α| for {w ∈ W | w |= α}.

• ⪰|= p>!q iff ∀w ∈ |p| and ∀w′ ∈ |q| we do not have w′ ≻ w.

Semantic entailment for more complex formulas, logical entailment and other logical notions are defined as usual. For example, φ1, . . . , φn |= φ if and only if for all ⪰ such that ⪰|= φi for i = 1 . . . n, we have ⪰|= φ.

We define a logic for querying preferences by optimization in a specified preference relation. We use the same semantic structures, but to simplify the definitions we assume that there are no infinitely ascending chains (see, e.g., [Boutilier, 1994] for a discussion). Moreover, p is preferred to q if the optimal p ∨ q worlds are p worlds.

Definition 3 (Querying) We assume ⪰ does not contain any infinite ascending chains. We write max(⪰, p) for {w ∈ W | w |= p and ∀w′ ∈ W : w′ ≻ w ⇒ w′ ̸|= p}.

• ⪰|= p>?q iff max(⪰, p ∨ q) ⊆ max(⪰, p). We distinguish models called most connected models.

Definition 4 (Distinguished models) A model ⪰1 is at least as connected as another model ⪰2, written as ⪰1⊑⪰2, if ⪰2⊆⪰1, that is, if ∀w1,w2 ∈ W : w1 ⪰2 w2 ⇒ w1 ⪰1 w2. A model ⪰1 is most connected if there is not another model ⪰2 such that ⪰2❁⪰1, that is, such that ⪰2⊑⪰1 without ⪰1⊑⪰2.

Non-monotonic reasoning is based on distinguished models in the usual way. These distinguished models have sometimes been called preferred models, and non-monotonic entailment has been called preferential entailment. However, to avoid confusion with the preferences formalized in our logical language, we do not use this terminology in this paper.

Definition 5 (Non-monotonic entailment) A preference specification is a set of specification preferences PS = {p1>!q1, . . . , pn>!qn}. A distinguished model of a preference specification PS is a most connected model of PS. A preference specification non-monotonically entails φ, written as PS |=⊑ φ, if for all distinguished models ⪰ of PS we have ⪰|= φ.

3 Logical properties

Specifying and querying preferences are complementary in the sense that the logic of the former satisfies left and right strengthening, and the logic of the latter satisfies transitivity.

3.1 Ordering

We first show that our desideratum holds. A preference specification which only contains preferences which are individually consistent, is itself consistent.

Proposition 1 If there is a model for each preference in PS, then there is a model of PS.

Proof. The identity relation {w ⪰ w | w ∈ W} is such a model of PS.

The logical relations among preference specifications are characterized by left and right additivity.

Consequently, reading the additivity formulas from left to right, specification preferences are strong preferences, in the sense that they satisfy the following properties of left and right strengthening.

Moreover, reading the additivity formulas from right to left, specification preferences satisfy left and right disjunction.

In case of a finite set of atoms, the combination of LS, RS, LOR and ROR give a simple way to derive all implied preferences from a preference specification. Call a formula a complete sentence when it implies p or ¬p for each proposition p ∈ A. Given a preference specification PS, first use LS and RS to derive preferences among complete sentences. Secondly, use LOR and ROR to derive all preferences among formulas.

Finally we consider some borderline cases. As usual, we cannot have that a proposition is preferred to itself. This is due to the fact that ⪰ is reflexive.

Moreover, an important distinction among preference logics is whether they satisfy transitivity. Our logic to specify preferences does not, because we may have r worlds preferred to p worlds, and q worlds incomparable to both p and r worlds.

3.2 Optimizing

Optimizing preferences have been studied in the context of total pre-orders. For example, Weydert [1991] defines elementary qualitative magnitude logic as follows, in a propositional preference logic extended with actual worlds:

• QM2 (p > q) ∧ (p > r) ↔ (p > q ∨ r) (additivity)
• QM3 ¬(q > p) ∧ (q > r) → (p > r) (maximality)
• QM4 ⊥ > ⊥ ∧ ((⊥ > p) ↔ (p > p)) (quasi-reflexivity)
• QM5 ⊥ > p → ¬p (correctness)

Of these formulas QM5 cannot be expressed in our logic, and the relevant properties to check are QM1, QM2 and QM3. It can be verified that QM1 and QM2 also hold for our logic based on partial pre-orders, but QM3 does not.

In some cases, it may be useful to define a stronger notion of specification preferences, as a combination of >! and >?.

Consequently, if we have ⪰|= p>0q then we also have ⪰|= p>?q, a property that does not hold for >!. That is, if we have ⪰|= p>!q, then we do not necessarily have ⪰|= p>?q.

3.3 Modal characterization

It is well known that the combination of two logics in a single logical system may be problematic, and that the axiomatization of such a combined logic is a non-trivial task. To obtain an axiomatization of our logic, we follow [Boutilier, 1994] by providing a modal characterization of the logic. We define (or simulate) the preference logic in a normal bimodal system, where ✷ is a universal modal operator and ✷′ is a normal modal operator. See, e.g., [Boutilier, 1994] for an axiomatization of the bimodal logic.

Definition 7 Let L′ be a modal logic with two modal operators ✷ and ✷′ . Moreover, let a model of L′ be a tuple M = 〈W,⪰, V 〉, with W a set of worlds, ⪰ a partial preorder on W, and V a valuation function of propositions at the worlds. The satisfiability relation for modal formulas is defined as follows.

• M, w |= ✷p when ∀w′ ∈ W we have M, w′ |= p.
• M,w |= ✷′ p when ∀w′ ∈W : w′ ⪰ w ⇒M,w′ |= p. Moreover, we add the following definitions to L′ :
• ✸p = ¬✷¬p, ✸′p = ¬✷′¬p
• p>!q = ✷(p →✷′¬q)
• p>?q = ✷(q →✸′ (p ∧¬q ∧✷′ (p ∨ q → p ∧¬q)))