Plausibility Measures: A General Approach For Representing Uncertainty

1 Introduction

The standard approach to modeling uncertainty is probability theory. In recent years, researchers, motivated by varying concerns including a dissatisfaction with some of the axioms of probability and a desire to represent information more qualitatively, have introduced a number of generalizations and alternatives to probability, including Dempster-Shafer belief functions [Shafer, 1976], possibility measures [Dubois and Prade, 1990], lexicographic probability [Blume et al., 1991], and many others. Rather than investigating each of these approaches piecemeal, I consider here an approach to representing uncertainty that generalizes them all, and lets us understand their commonalities and differences.

A plausibility measure [Friedman and Halpern, 1995] associates with a set a plausibility, which is just an element in a partially ordered space. The only real requirement is that if ✁ is a subset of ✂ , then the plausibility of ✁ is less than equal to the plausibility of ✂ . Probability measures are clearly plausibility measures; every other representation of uncertainty that I am aware of can also be viewed as a plausibility measure. Given how little structure plausibility measures have, it is perhaps not surprising that plausibility measures generalize so many other notions. This very lack of structure turns out to be a significant advantage. By adding structure on an "as needed" basis, it is possible to characterize what is required to ensure that a plausibility measure has certain properties of interest. This both gives insight into the essential features of the properties in question and makes it possible to prove general results that apply to many representations of uncertainty.

In this paper, I discuss three examples of this phenomenon.

• ✄ belief, belief revision, and default reasoning,
• ✄ expectation and decision making,
• ✄ compact representations of uncertainty (Bayesian networks).

Most of the discussion is based on earlier work (some of it joint with Nir Friedman). In the next two sections I define plausibility measures and conditional plausibility measures. The next three sections considers each of the topics above in more detail.

☎ Supported in part by NSF under grants IRI-96-25901 and IIS0090145.

Clearly probability spaces are instances of plausibility spaces. ❜ Almost all other representations of uncertainty in the literature can also be viewed as instances of plausibility measures. Here are some examples:

• ✄ A belief function on ✝ is a function ❝ ❞ ✮ ❡ ❢ ❣ ❤ ✏ ✑ ✟ ✓ ✕ satisfying certain axioms [Shafer, 1976]. These axioms certainly imply property Pl3, so a belief function is a plausibility measure. There is a corresponding plausibility function ✭ ✮ ❦ ♠ ♦ defined as ✭ ✮ ❦ ♠ ♦ ✆ ✁ ✍ ✙ ✓ a114 ❝ ❞ ✮ ✆ ✁ ✍ . 2
• ✄ A possibility measure [Dubois and Prade, 1990] on ✝ is a function Poss ❡ ❢ ❣ ❤ ✏ ✑ ✟ ✓ ✕ such that Poss ✆ ✝ ✍ ✙ ✓ , Poss✆ ✗ ✍ ✙ ✑ , and Poss✆ ✁ ✍ ✙ ♦ ♠ ① ② ③ ④ ✆ Poss✆ ⑥ ⑦ ⑨ ✍ .
• ✄ An ordinal ranking (or ⑩ -ranking) ⑩ on ✝ (as defined by [Goldszmidt and Pearl, 1992], based on ideas that go back to [Spohn, 1988]) is a function mapping subsets of ✝ to ❶ ❷ ❹ ✙ ❶ ❷ ✤ ⑥ ❻ ⑨ such that ⑩ ✆ ✝ ✍ ✙ ✑ , ⑩ ✆ ✗ ✍ ✙ ❻ , and ⑩ ✆ ✁ ✍ ✙ ❽ ❾ ❿ ② ③ ④ ✆ ⑩ ✆ ⑥ ⑦ ⑨ ✍ ✍ . Intuitively, an ordinal ranking assigns a degree of surprise to each subset of worlds in ✝ , where ✑ means unsurprising and higher numbers denote greater surprise. It is easy to see that a ranking ⑩ is a plausibility measure with range ❶ ❷ , where ➁ ✴ ➂ ➃ ➄ ➅ if and only if ➅ ✴ ➁ under the usual ordering.
• ✄ A lexicographic probability system (LPS) [Blume et al., 1991] of length ➇ is a sequence ➈ ☞ ✙ ✆ ☞ ➊ ✟ ➋ ➋ ➋ ✟ ☞ ➍ ✍ of probability measures. Intuitively, the first measure in the sequence, ☞ ➊ , is themost important one, followed by ☞ ❇ , ☞ ❉ , and so on. Very roughly speaking, the probability assigned to an event ✁ by a sequence such as ✆ ☞ ➊ ✟ ☞ ❇ ✍ can be taken to be ☞ ➊ ✆ ✁ ✍ ✩ ➐ ☞ ❇ ✆ ✁ ✍ , where ➐ is an infinitesimal. Thus, even if the probability of ✁ according to ☞ ➊ is 0, ✁ still has a positive (although infinitesimal) probability if ☞ ❇ ✆ ✁ ✍ ➑ ✑ .

In all these cases, the plausibility ordering is total. But there are also cases of interest where the plausibility ordering is not total. For example, suppose that ➓ is a set of probability measures on ✝ . Let ➓ ❹ be the lower probability of ➓ , so that ➓ ❹ ✆ ✁ ✍ ✙ ❾ ❿ ➔ ⑥ ☞ ✆ ✁ ✍ ❡ ☞ ❃ ➓ ⑨ . Similarly, the upper probability ➓ ❹ is defined as ➓ ❹ ✆ ✁ ✍ ✙ ♦ ♠ ① ⑥ ☞ ✆ ✁ ✍ ❡ ☞ ❃ ➓ ⑨ .

Both ➓ ❹ and ➓ ❹ give a way of comparing the likelihood of two subsets ✁ and ✂ of ✝ . These two ways are incomparable: it is easy to find a set ➓ of probability measures on ✝ and subsets ✁ and ✂ of ✝ such that ➓ ❹ ✆ ✁ ✍ ❆ ➓ ❹ ✆ ✂ ✍ and ➓ ❹ ✆ ✁ ✍ ➑ ➓ ❹ ✆ ✂ ✍ . Rather than choosing between ➓ ❹ and ➓ ❹ , we can associate a different plausibility measure with ➓ that captures both. Let ✻ ➛ ➄ ➝ ➛ ➄ ✙ ⑥ ✆ ➞ ✟ ➟ ✍ ❡ ✑ ✴ ➞ ✴ ➟ ✴ ✓ ⑨ and define ✆ ➞ ✟ ➟ ✍ ✴ ✆ ➞ ➢ ✟ ➟ ➢ ✍ iff ➟ ✴ ➞ ➢ . This puts a partial order on ✻ ➛ ➄ ➝ ➛ ➄ , with ✿ ✼ ➥ ➄ ➦ ➥ ➄ ✙ ✆ ✑ ✟ ✑ ✍ and ✾ ✼ ➥ ➄ ➦ ➥ ➄ ✙ ✆ ✓ ✟ ✓ ✍ . Define ✭ ✮ ➛ ➄ ➝ ➛ ➄ ✆ ✁ ✍ ✙ ✆ ➓ ❹ ✆ ✁ ✍ ✟ ➓ ❹ ✆ ✁ ✍ ✍ . Thus, ✭ ✮ ➛ ➄ ➝ ➛ ➄ associates with a set ✁ two numbers that can be thought of as defining an interval in terms of the lower and upper probability of ✁ . It is easy to check that ✭ ✮ ➛ ➄ ➝ ➛ ➄ ✆ ✁ ✍ ✴ ✭ ✮ ➛ ➄ ➝ ➛ ➄ ✆ ✂ ✍ if the upper probability of ✁ is less than or equal to the lower probability of ✂ . Clearly, ✭ ✮ ➛ ➄ ➝ ➛ ➄ satisfies Pl1-3, so it is indeed a plausibility measure, but one that puts only a partial (pre)order on events. A similar plausibility measure can be associated with a belief/plausibility function.

2 The word "plausibility" is slightly overloaded, appearing both in the context of "plausibility function" and "plausibility measure". Plausibility functions will play only a minor role in this paper, so there should not be much risk of confusion.

The trouble with ➓ ❹ , ➓ ❹ , and even ✭ ✮ ➛ ➄ ➝ ➛ ➄ is that they lose information. For example, it is not hard to find a set ➓ of probability measures and subsets ✁ ✟ ✂ of ✝ such that ☞ ✆ ✁ ✍ ✴ ☞ ✆ ✂ ✍ for all ☞ ❃ ➓ and ☞ ✆ ✁ ✍ ❆ ☞ ✆ ✂ ✍ for some ☞ ❃ ➓ , but ➓ ❹ ✆ ✁ ✍ ✙ ➓ ❹ ✆ ✂ ✍ and ➓ ❹ ✆ ✁ ✍ ✙ ➓ ❹ ✆ ✂ ✍ . Indeed, there exists an infinite set ➓ of probability measures such that ☞ ✆ ✁ ✍ ❆ ☞ ✆ ✂ ✍ for all ☞ ❃ ➓ but ➓ ❹ ✆ ✁ ✍ ✙ ➓ ❹ ✆ ✂ ✍ and ➓ ❹ ✆ ✁ ✍ ✙ ➓ ❹ ✆ ✂ ✍ . If all the probability measures in ➓ agree that ✁ is less likely than ✂ , it seems reasonable to conclude that ✁ is less likely than ✂ . However, none of ➓ ❹ , ➓ ❹ , or ✭ ✮ ➛ ➄ ➝ ➛ ➄ necessarily draw this conclusion.

It is not hard to associate yet another plausibility measure with ➓ that does not lose this important information (and does indeed conclude that ✁ is less likely than ✂ ). Suppose, without loss of generality, that there is some index set ❶ such that ➓ ✙ ⑥ ☞ ➯ ❡ ➲ ❃ ❶ ⑨ . Thus, for example, if ➓ ✙ ⑥ ☞ ❇ ✟ ➋ ➋ ➋ ✟ ☞ ➳ ⑨ , then ❶ ✙ ⑥ ✓ ✟ ➋ ➋ ➋ ✟ ➵ ⑨ . (In general, ❶ may be infinite.) Let ✻ ➂ consist of all functions from ❶ to ✏ ✑ ✟ ✓ ✕ . The standard pointwise ordering on functions-that is, ➸ ✴ ➻ if ➸ ✆ ➲ ✍ ✴ ➻ ✆ ➲ ✍ for all ➲ ❃ ❶ -gives a partial order on ✻ ➂ . Note that ✿ ✼ ➾ is the function ➸ ❡ ❶ ❤ ✏ ✑ ✟ ✓ ✕ such that ➸ ✆ ➲ ✍ ✙ ✑ for all ➲ ❃ ❶ and ✾ ✼ ➾ is the function ➻ such that ➻ ✆ ➲ ✍ ✙ ✓ for all ➲ ❃ ❶ . For ✁ ▲ ✝ , let ➸ ④ be the function such that ➸ ④ ✆ ➲ ✍ ✙ ☞ ➯ ✆ ✁ ✍ for all ➲ ❃ ❶ . Define the plausibility measure ✭ ✮ ➛ by taking ✭ ✮ ➛ ✆ ✁ ✍ ✙ ➸ ④ . Thus, ✭ ✮ ➛ ✆ ✁ ✍ ✴ ✭ ✮ ➛ ✆ ✂ ✍ iff ➸ ④ ✆ ➲ ✍ ✴ ➸ ➪ ✆ ➲ ✍ for all ➲ ❃ ❶ iff ☞ ✆ ✁ ✍ ✴ ☞ ✆ ✂ ✍ for all ☞ ❃ ➓ . It is easy to see that ➸ ➶ ✙ ✿ ✼ ➾ and ➸ ❣ ✙ ✾ ✼ ➾ . Clearly ✭ ✮ ➛ satisfies Pl1-3. Pl1 and Pl2 follow since ✭ ✮ ➛ ✆ ✗ ✍ ✙ ➸ ➶ ✙ ✿ ✼ ➾ and ✭ ✮ ➛ ✆ ✝ ✍ ✙ ➸ ❣ ✙ ✾ ✼ ➾ , while Pl3 holds because if ✁ ▲ ✂ , then ☞ ✆ ✁ ✍ ✴ ☞ ✆ ✂ ✍ for all ☞ ❃ ➓ .

To see how this representation works, consider a simple example where a coin which is known to be either fair or double-headed is tossed. The uncertainty can be represented by two probability measures on ☞ ❇ , which gives heads probability 1, and ☞ ❉ which gives heads probability ✓ ➘ ❢ . Taking the index set to be ⑥ ✓ ✟ ❢ ⑨ , this gives us a plausibility measure ✭ ✮ ➛ such that ✭ ✮ ➛ ✆ ➴ ✍ is a function ➸ such that ➸ ✆ ✓ ✍ ✙ ✓ and ➸ ✆ ❢ ✍ ✙ ✓ ➘ ❢ ; similarly, ✭ ✮ ➛ ✆ ➮ ✍ is a function ➸ ➢ such that ➸ ➢ ✆ ✓ ✍ ✙ ✑ and ➸ ➢ ✆ ❢ ✍ ✙ ✓ ➘ ❢ .

3 Conditional Plausibility

Suppose an agent's beliefs are represented by a plausibility measure ✭ ✮ . How should these beliefs be updated in light of new information? The standard approach to updating in probability theory is by conditioning. Most other representations of uncertainty have an analogue to conditioning. Indeed, compelling arguments have been made in the context of probability to take conditional probability as a primitive notion, rather than unconditional probability. The idea is to start with a primitive notion ✭ ➱ ✆ ✃ ❐ ✃ ✍ satisfying some constraints (such as ✭ ➱ ✆ ✁ ✤ ✁ ➢ ❐ ✂ ✍ ✙ ✭ ➱ ✆ ✁ ❐ ✂ ✍ ✩ ✭ ➱ ✆ ✁ ➢ ❐ ✂ ✍ if ✁ and ✁ ➢ are disjoint) rather than starting with an unconditional probability measure and defining conditioning in terms of it. The advantage of taking conditional probability as primitive is that it allows conditioning on events of unconditional probability 0. (If ✝ is the whole space, the unconditional probability of ✂ can be identified with ✭ ➱ ✆ ✂ ❐ ✝ ✍ ; note that ✭ ➱ ✆ ✁ ❐ ✂ ✍ may be well defined even if ✭ ➱ ✆ ✂ ❐ ✝ ✍ ✙ ✑ .) Although conditioning on events of measure 0 may seem to be of little practical interest, it turns out to play a critical role in game theory (see, for example, [Blume et al., 1991; Myerson, 1986]), the analysis of conditional statements (see [Adams, 1966; McGee, 1994]), and in dealing with nonmonotonicity (see, for example, [Lehmann and Magidor, 1992]).

Most other representations of uncertainty also have an associated notion of conditioning. I now discuss a notion of conditional plausibility that generalizes them all. A conditional plausibility measure (cpm) maps pairs of subsets of ✝ to some partially ordered set ✻ . I write ✭ ✮ ✆ ✁ ❐ ✂ ✍ rather than ✭ ✮ ✆ ✁ ✟ ✂ ✍ , in keeping with standard notation. An important issue in defining conditional plausibility is to make precise what the allowable arguments to ✭ ✮ are. I take the domain of a cpm to have the form ✡ ❒ ✡ ➢ where, roughly speaking, ✡ ➢ consists of those sets in ✡ on which conditioning is allowed. For example, for a conditional probability measure defined in the usual way from an unconditional probability measure ☞ , ✡ ➢ consists of all sets ✂ such that ☞ ✆ ✂ ✍ ➑ ✑ . (Note that ✡ ➢ is not an algebra-it is not closed under complementation.) A Popper algebra over ✝ is a set ✡ ❒ ✡ ➢ of subsets of ✝ ❒ ✝ satisfying the following properties:

Acc1. ✡ is an algebra over ✝ .

Acc2. ✡ ➢ is a nonempty subset of ✡ .

Acc3. ✡ ➢ is closed under supersets in ✡ ; that is, if ✂ ❃ ✡ ➢ , ✂ ▲ ✂ ➢ , and ✂ ➢ ❃ ✡ , then ✂ ➢ ❃ ✡ ➢ .

(Popper algebras are named after Karl Popper, who was the first to consider formally conditional probability as the basic notion [Popper, 1968]. This definition of cpm is from [Halpern, 2000a] which in turn is based on the definition in [Friedman and Halpern, 1995].)

A conditional plausibility space (cps) is a tuple ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ✭ ✮ ✍ , where ✡ ❒ ✡ ➢ is a Popper algebra over ✝ , ✭ ✮ ❡ ✡ ❒ ✡ ➢ ❤ ✻ , ✻ is a partially ordered set of plausibility values, and ✭ ✮ is a conditional plausibility measure (cpm) that satisfies the following conditions:

CPl1. ✭ ✮ ✆ ✗ ❐ ✂ ✍ ✙ ✿ . CPl2. ✭ ✮ ✆ ✝ ❐ ✂ ✍ ✙ ✾ . CPl3. If ✁ ▲ ✁ ➢ , then ✭ ✮ ✆ ✁ ❐ ✂ ✍ ✴ ✭ ✮ ✆ ✁ ➢ ❐ ✂ ✍ . CPl4 ✭ ✮ ✆ ✁ ❐ ✂ ✍ ✙ ✭ ✮ ✆ ✁ a209 ✂ ❐ ✂ ✍ .

CPl1-3 are the obvious analogues to Pl1-3. CPl4 is a minimal property that guarantees that when conditioning on ✂ , everything is relativized to ✂ . It follows easily from CPl1-4 that ✭ ✮ ✆ ✃ ❐ ✂ ✍ is a plausibility measure on ✂ for each fixed ✂ . A cps is acceptable if it satisfies

Acceptability is a generalization of the observation that if ✭ ➱ ✆ ✂ ✍ ❍ ✙ ✑ , then conditioning on ✂ should be defined. It says that if ✭ ✮ ✆ ✁ ❐ ✂ ✍ ❍ ✙ ✿ ✼ , then conditioning on ✂ a209 ✁ should be defined. A cps ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ✭ ✮ ✍ is standard if ✡ ➢ ✙ ⑥ ✁ ❡ ✭ ✮ ✆ ✁ ❐ ✝ ✍ ❍ ✙ ✿ ⑨ .

CPl1-4 are rather minimal requirements. For example, they do not place any constraints on the relationship between ✭ ✮ ✆ ✁ ❐ ✂ ✍ and ✭ ✮ ✆ ✁ ❐ ✂ ➢ ✍ if ✂ ❍ ✙ ✂ ➢ . One natural additional condition is the following.

It is not hard to show that CPl5 implies CPl4. While it seems reasonable, note that CPl5 does not hold in some cases of interest. For example, there are two well-known ways of defining conditioning for belief functions (see [Halpern and Fagin, 1992]), one using Dempster's rule of combination and the other treating belief functions as lower probabilities. They both satisfy CPl1-4, and neither satisfies CPl5.

Many plausibility spaces of interest have more structure. In particular, there are analogues to addition and multiplication. More precisely, there is a way of computing the plausibility of the union of two disjoint sets in terms of the plausibility of the individual sets and a way of computing ✭ ✮ ✆ ✁ a209 ✂ ❐ ✂ ➢ ✍ given ✭ ✮ ✆ ✁ ❐ ✂ a209 ✂ ➢ ✍ and ✭ ✮ ✆ ✂ ❐ ✂ ➢ ✍ . A cps ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ✭ ✮ ✍ where ✭ ✮ has range ✻ is algebraic if it is acceptable and there are functions a213 ❡ ✻ ❒ ✻ ❤ ✻ and a214 ❡ ✻ ❒ ✻ ❤ ✻ such that the following properties hold:

• Alg1. If ✁ ✟ ✁ ➢ ❃ ✡ are disjoint and ✂ ❃ ✡ ➢ then ✭ ✮ ✆ ✁ ✤ ✁ ➢ ❐ ✂ ✍ ✙ ✭ ✮ ✆ ✁ ❐ ✂ ✍ a213 ✭ ✮ ✆ ✁ ➢ ❐ ✂ ✍ .
• Alg2. If ✁ ❃ ✡ , ✂ a209 ✂ ➢ ❃ ✡ ➢ , then ✭ ✮ ✆ ✁ a209 ✂ ❐ ✂ ➢ ✍ ✙ ✭ ✮ ✆ ✁ ❐ ✂ a209 ✂ ➢ ✍ a214 ✭ ✮ ✆ ✂ ❐ ✂ ➢ ✍ .
• Alg3. a214 distributes over a213 ; more precisely, ➞ a214 ✆ ➟ ❇ a213 ✃ ✃ ✃ a213 ➟ ➳ ✍ ✙ ✆ ➞ a214 ➟ ❇ ✍ a213 ✃ ✃ ✃ a213 ✆ ➞ a214 ➟ ➳ ✍ if ✆ ➞ ✟ ➟ ❇ ✍ ✟ ➋ ➋ ➋ ✟ ✆ ➞ ✟ ➟ ➳ ✍ ✟ ✆ ➞ ✟ ➟ ❇ a213 ✃ ✃ ✃ a213 ➟ ➳ ✍ ❃ DomPl ✆ a214 ✍ and ✆ ➟ ❇ ✟ ➋ ➋ ➋ ✟ ➟ ➳ ✍ ✟ ✆ ➞ a214 ➟ ❇ ✟ ➋ ➋ ➋ ✟ ➞ a214 ➟ ➳ ✍ ❃ DomPl ✆ a213 ✍ , where DomPl ✆ a213 ✍ ✙ ⑥ ✆ ✭ ✮ ✆ ✁ ❇ ❐ ✂ ✍ ✟ ➋ ➋ ➋ ✟ ✭ ✮ ✆ ✁ ➳ ❐ ✂ ✍ ✍ ❡ ✁ ❇ ✟ ➋ ➋ ➋ ✟ ✁ ➳ ❃ ✡ are pairwise disjoint and ✂ ❃ ✡ ➢ ⑨ and DomPl ✆ a214 ✍ ✙ ⑥ ✆ ✭ ✮ ✆ ✁ ❐ ✂ a209 ✂ ➢ ✍ ✟ ✭ ✮ ✆ ✂ ❐ ✂ ➢ ✍ ✍ ❡ ✁ ❃ ✡ ✟ ✂ a209 ✂ ➢ ❃ a219 ➢ ⑨ .

I sometimes refer to the cpm ✭ ✮ as being algebraic as well.

There are well-known techniques for extending some standard unconditional representations of uncertainty to conditional representations. All satisfy CPl1-4, when viewed as plausibility measures. (Indeed, as shown in [Halpern, 2000a], there is a construction for converting an arbitrary unconditional plausibility space ✆ ✝ ✟ ✡ ✟ ✭ ✮ ✍ to an acceptable standard cps.) In many cases, the resulting cps is algebraic. But one important case that is not algebraic is conditional belief functions (using either definition of conditioning).

To give one example of a construction that does lead to an algebraic cps, consider LPS's. Blume, Brandenburger, and Dekel 1991 (BBD) define conditioning in LPS's as follows. Given ➈ ☞ and ✁ ❃ ✡ such that ☞ ➯ ✆ ✁ ✍ ➑ ✑ for some index ➲ , let ➈ ☞ ❐ ✂ ✙ ✆ ☞ a221 a222 ✆ ✃ ❐ ✂ ✍ ✟ ➋ ➋ ➋ ✟ ☞ a221 a223 ✆ ✃ ❐ ✂ ✍ ✍ , where ✆ a224 ➊ ✟ ➋ ➋ ➋ ✟ a224 ➍ ✍ is the subsequence of all indices for which the probability of ✁ is positive. Thus, the length of the LPS ➈ ☞ ❐ ✂ depends on ✂ . Let ✻ a221 consist of all sequences ✆ ➞ ➊ ✟ ➋ ➋ ➋ ✟ ➞ a221 ✍ ➘ ❃ ⑥ ✆ ✑ ✟ ➋ ➋ ➋ ✟ ✑ ✍ ✟ ✆ ✓ ✟ ➋ ➋ ➋ ✟ ✓ ✍ ⑨ such that ➞ ➯ ❃ ✏ ✑ ✟ ✓ ✕ for ➲ ✙ ✑ ✟ ➋ ➋ ➋ ✟ a224 , and let ✻ ✙ ⑥ a225 ✟ a226 ⑨ ✤ ✆ ✤ a227 a221 a228 ➊ ✻ a221 ✍ . Roughly speaking, 0 is meant to represent all sequences of the form ✆ ✑ ✟ ➋ ➋ ➋ ✟ ✑ ✍ , whatever their length; similarly, 1 represents all sequences of the form ✆ ✓ ✟ ➋ ➋ ➋ ✟ ✓ ✍ . Define a partial order ✴ ✼ on ✻ so that ❁ ❇ ✴ ✼ ❁ ❉ if ❁ ❇ ✙ a225 , ❁ ❉ ✙ a226 , or ❁ ❇ and ❁ ❉ are vectors of the same length and ❁ ❇ is lexicographically less than or equal to ❁ ❉ . Note that vectors of different length are incomparable.

An unconditional LPS ➈ ☞ defined on an algebra ✡ over ✝ can then be extended to a standard cps ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ➈ ☞ ✍ using the definition of conditioning above. Note that although ➈ ☞ ✆ ✁ ❐ ✂ ✍ may be incomparable to ➈ ☞ ✆ ✁ ➢ ❐ ✂ ➢ ✍ for ✂ ❍ ✙ ✂ ➢ , ➈ ☞ ✆ ✁ ❐ ✂ ✍ will definitely be comparable to ➈ ☞ ✆ ✁ ➢ ❐ ✂ ✍ . Moreover, the definition of 0 and 1 guarantees that a225 ✙ ➈ ☞ ✆ ✗ ❐ ✁ ➢ ✍ ✴ ✼ ➈ ☞ ✆ ✂ ❐ ✁ ✍ ✴ ✼ ➈ ☞ ✆ ✁ ➢ ➢ ❐ ✁ ➢ ➢ ✍ ✙ a226 if ✁ ➢ ✟ ✁ ➢ ➢ ❃ ✡ ➢ , as required by CPl1 and CPl2.

The cps ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ➈ ☞ ✍ is in fact algebraic; a213 and a214 are functions that satisfy the following constraints:

• ✄ if ❁ ❇ and ❁ ❉ are vectors of the same length, ❁ ❇ a213 ❁ ❉ ✙ ❁ ❇ ✩ ❁ ❉ (where ✩ represents pointwise addition),
• ✄ ❁ a213 a225 ✙ a225 a213 ❁ ✙ ❁ ,
• ✄ ❁ a214 a226 ✙ a226 a214 ❁ ✙ ❁ ,
• ✄ a225 a214 ❁ ✙ ❁ a214 a225 ✙ a225 ,
• ✄ ✆ ➞ ❇ ✟ ➋ ➋ ➋ ✟ ➞ ➍ ✍ a214 ✆ ➈ ✑ ✟ ➟ ❇ ✟ ➈ ✑ ✟ ➋ ➋ ➋ ✟ ➈ ✑ ✟ ➟ ➍ ✟ ➈ ✑ ✍ ✙ ✆ ➈ ✑ ✟ ➞ ❇ ➟ ❇ ✟ ➈ ✑ ✟ ➋ ➋ ➋ ✟ ➈ ✑ ✟ ➞ ➍ ➟ ➍ ✟ ➈ ✑ ✍ , where ➈ ✑ represents a possibly empty sequence of 0s, and ➟ ❇ ✟ ➋ ➋ ➋ ✟ ➟ ➍ ➑ ✑ .

I leave it to the reader to check that these definitions indeed make the cps algebraic.

A construction similar in spirit can be used to define a notion of conditioning appropriate for the representation ✭ ✮ ➛ of a set ➓ of plausibilitymeasures; this also leads to an algebraic cps [Halpern, 2000a].

4 Belief Revision and Default Reasoning

4.1 Belief

There have been many models used to capture belief. Perhaps the best known approach uses Kripke structures [Hintikka, 1962], where an agent believes a230 if a230 is true at all worlds the agent considers possible. In terms of events (sets of worlds), an agent believes ✁ if ✁ contains all the worlds that the agent considers possible. Another popular approach is to use probability: an agent believes ✁ if the probability of ✁ is at least ✓ a114 ➐ for some appropriate ➐ a231 ✑ .

One of the standard assumptions about belief is that it is closed under conjunction: if an agent believes ✁ ❇ and ✁ ❉ , then the agent should also believe ✁ ❇ a209 ✁ ❉ . This holds for the definition in terms of Kripke structures. It holds for the probabilistic definition only if ➐ ✙ ✑ . Indeed, identifying knowledge/belief with "holds with probability 1" is common, especially in the economics/game theory literature [Brandenburger and Dekel, 1987].

A number of other approaches to modeling belief have been proposed recently, in the game theory and philosophy literature. One, due to Brandenburger 1999, uses filters. Given a set ✝ of possible worlds, a filter ✡ is a nonempty set of subsets of ✝ that (1) is closed under supersets (so that if ✁ ❃ ✡ and ✁ ▲ ✁ ➢ , then ✁ ➢ ❃ ✡ ), (2) is closed under finite intersection (so that if ✁ ✟ ✁ ➢ ❃ ✡ , then ✁ a209 ✁ ➢ ❃ ✡ ), and

(3) does not contain the empty set. Given a filter ✡ , an agent is said to believe ✁ iff ✁ ❃ ✡ . Note that the set of sets which are given probability 1 by a probability measure form a filter. Conversely, every filter ✡ defines a finitely additive probability measure ✭ ➱ : the sets in ✡ get probability 1; all others get probability 0. We can also obtain a filter from the Kripke structure definition of knowledge. If the agent considers possible the set ✁ ▲ ✝ , then let ✡ consist of all superset of ✁ . This is clearly a filter (consisting of precisely the events the agent believes). Conversely, in a finite space, a filter ✡ determines a Kripke structure. The agent considers possible precisely the intersection of all the sets in ✡ (which is easily seen to be nonempty). In an infinite space, a filter may not determine a Kripke structure precisely because the intersection of all sets in the filter may be empty. The events believed in a Kripke structure form a filter whose sets are closed under arbitrary intersection.

Another approach to modeling belief, due to Brandenburger and Keisler 2000, uses LPS's. Say that an agent believes ✁ in LPS ➈ ☞ if there is some a233 ✴ ➇ such that ☞ ➯ ✆ ✁ ✍ ✙ ✓ for all ➲ ✴ a233 and ☞ ➯ ✆ ✁ ✍ ✙ ✑ for ➲ ➑ a233 . It is easy to see that beliefs defined this way are closed under intersection. Brandenburger and Keisler give an elegant decision-theoretic justification for this notion of belief. Interestingly, van Fraassen 1995 defines a notion of belief using conditional probability spaces that can be shown to be closely related to the definition given by Brandenburger and Keisler.

Plausibility measures provide a framework for understanding what all these approaches have in common. Say that an agent believes ✁ with respect to plausibility measure ✭ ✮ if ✭ ✮ ✆ ✁ ✍ ➑ ✭ ✮ ✆ ✁ ✍ ; that is, the agent believes ✁ if ✁ is more plausible than not. It is easy to see that, in general, this definition is not closed under conjunction. In the case of probability, for example, this definition just says that ✁ is believed if the probability of ✁ is greater than ✓ ➘ ❢ . What condition on a plausibility measure ✭ ✮ is needed to guarantee that this definition of belief is closed under conjunction? Trivially, the following restriction does the trick:

I actually want a stronger version of this property, to deal with conditional beliefs. An agent believes ✁ conditional on ✂ , if given ✂ , ✁ is more plausible than ✁ , that is, if ✭ ✮ ✆ ✁ ❐ ✂ ✍ ➑ ✭ ✮ ✆ ✁ ❐ ✂ ✍ . In the presence of CPl5 (which I implicitly assume for this section), conditional beliefs are closed under conjunction if the following holds:

Amore elegant requirement is the following:

• Pl4. If ✁ ❇ , ✁ ❉ , and ✁ a234 are pairwise disjoint sets, ✭ ✮ ✆ ✁ ❇ ✤ ✁ ❉ ✍ ➑ ✭ ✮ ✆ ✁ a234 ✍ , and ✭ ✮ ✆ ✁ ❇ ✤ ✁ a234 ✍ ➑ ✭ ✮ ✆ ✁ ❉ ✍ , then ✭ ✮ ✆ ✁ ❇ ✍ ➑ ✭ ✮ ✆ ✁ ❉ ✤ ✁ a234 ✍ .

In words, Pl4 says that if ✁ ❇ ✤ ✁ ❉ is more plausible than ✁ a234 and if ✁ ❇ ✤ ✁ a234 is more plausible than ✁ ❉ , then ✁ ❇ by itself is already more plausible than ✁ ❉ ✤ ✁ a234 .

Remarkably, in the presence of Pl1-3, Pl4 and Pl4➢ are equivalent:

Proposition 4.1: ([Friedman and Halpern, 1996a]) ✭ ✮ satisfies Pl1-4 a236 iff ✭ ✮ satisfies Pl1-3 and Pl4➢ .

Thus, for plausibility measures, Pl4 is necessary and sufficient to guarantee that conditional beliefs are closed under conjunction. Proposition 4.1 helps explain why all the notions of belief discussed above are closed under conjunction. More precisely, for each notion of belief discussed earlier, it is trivial to construct a plausibility measure ✭ ✮ satisfying Pl4 that captures it: ✭ ✮ give plausibility 1 to the events that are believed and plausibility 0 to the rest.

Pl4 is required for beliefs to be closed under finite intersection (i.e., finite conjunction). It does not guarantee closure under infinite intersection. This is a feature: beliefs are not always closed under infinite intersection. The classic example is the lottery paradox [Kyburg, 1961]: Consider a situation with infinitely many individuals, each of whom holds a ticket to a lottery. It seems reasonable to believe that individual ➲ will not win, for any ➲ , yet that someone will win. If a237 ➯ is the event that individual ➲ does not win, this amounts to believing a237 ❇ ✟ a237 ❉ ✟ a237 a234 ✟ ➋ ➋ ➋ and also believing ✤ ➯ a237 ➯ (and not believing a209 ➯ a237 ➯ ). It is easy to capture this with a plausibility measure. Let ✝ ✙ ⑥ ⑦ ❇ ✟ ⑦ ❉ ✟ ➋ ➋ ➋ ⑨ , where ⑦ ➯ is the world where individual ➲ wins (so that a237 ➯ ✙ ✝ a114 ⑥ ⑦ ➯ ⑨ ). Let ✭ ✮ lot be a plausibility measure that assigns plausibility ✑ to the empty set, plausibility ✓ ➘ ❢ to all finite sets, and plausibility 1 to all infinite sets. It is easy to see that ✭ ✮ lot ratifies Pl4. Nevertheless, each of a237 ❇ is believed according to ✭ ✮ lot, as is ✤ ➯ a237 ➯ .

As shown in [Friedman et al., 2000], the key property that guarantees that (conditional) beliefs are closed under infinite intersection is the following generalization of Pl4:

Because Pl4 ❹ does not hold for ✭ ✮ lot, it can be used to represent the lottery paradox. Because Pl4 ❹ does hold for the plausibility measure corresponding to beliefs in Kripke structure, belief in Kripke structures is closed under infinite conjunction. A countable version of Pl4❹ holds for a239 -additive probability measures, which is why probability-1 beliefs are closed under countable conjunctions (but not necessarily under arbitrary infinite conjunctions).

4.2 Belief Revision

An agent's beliefs change over time. Conditioning has been the standard approach to modeling this change in the context of probability. However, conditioning has been argued to be inapplicable when it comes to belief revision, because an agent may learn something inconsistent with her beliefs. This would amount to conditioning on a set of measure 0. As a consequence, finding appropriate models of belief change has been an active area in philosophy and in both artificial intelligence [G¨ ardenfors, 1988; Katsuno and Mendelzon, 1991]. In the literature, two models have been studied in detail: Belief revision [Alchourr ´on et al., 1985; G¨ ardenfors, 1988] attempts to describe how an agent should accommodate a new belief (possibly inconsistent with his other beliefs) about a static world. Belief update [Katsuno and Mendelzon, 1991], on the other hand, attempts to describe how an agent should change his beliefs as a result of learning about a change in the world.

Belief revision and belief update describe only two of the many ways in which beliefs can change. Using plausibility, it is possible to construct a general framework for reasoning about belief change (see [Friedman and Halpern, 1997]). The key point is that it is possible to describe belief changing using conditioning with plausibility, even though it cannot be done with probability. Starting with a conditional plausibility measure satisfying Pl4 (this is necessary for belief to have the right properties) and conditioning on new information gives us a general model of belief change. Belief revision and belief update can be captured by putting appropriate constraints on the initial plausibility [Friedman and Halpern, 1999]. The same framework can be used to capture other notions of belief change, such as a general Markovian models of belief change [Friedman and Halpern, 1996b] and belief change with unreliable observations [Boutilier et al., 1998]. The key point is that belief change simply becomes conditioning (and iterated belief change becomes iterated conditioning).

4.3 Default Reasoning

It has been argued that default reasoning plays a major role in commonsense reasoning. Perhaps not surprisingly, there have been many approaches to default reasoning proposed in the literature (see [Gabbay et al., 1993; Ginsberg, 1987]). Many of the recent approaches to giving semantics to defaults can be viewed as considering structures of the form ✆ ✝ ✟ a240 ✟ a241 ✍ , where ✝ is a set of possible worlds, a241 ✆ ⑦ ✍ is a truth assignment to primitive propositions for each world ⑦ ❃ ✝ , and a240 can be viewed as a "measure" on ✝ . Some examples of a240 include possibility measures [Dubois and Prade, 1991], ⑩ -rankings [Goldszmidt and Pearl, 1996], parameterized probability distributions [Pearl, 1989] (these are sequences of probability distributions; the resulting approach is more commonly known as ➐ -semantics), and preference orders [Kraus et al., 1990; Lewis, 1973].

Somewhat surprisingly, all of these approaches are characterized by the six axioms and inference rules, which have been called the KLM properties (since they were discussed by Kraus, Lehmann, and Magidor 1990). Assume (as is typical in the literature) that defaults are expressed in terms of an operator a242 , where a230 a242 a243 is read "if a230 then typically/likely/by default a243 . For example, the default "birds typically fly" is represented Birda242 Fly. We further assume for now that the formulas a230 and a243 that appear in defaults come from some propositional language a244 with a consequence relation a245 a246 .

• LLE. If a245 a246 a230 a247 a230 ➢ , then from a230 a242 a243 infer a230 ➢ a242 a243 (left logical equivalence).
• RW. If a245 a246 a243 a248 a243 ➢ , then from a230 a242 a243 infer a230 a242 a243 ➢ (right weakening).
• REF. a230 a242 a230 (reflexivity).
• AND. From a230 a242 a243 ❇ and a230 a242 a243 ❉ infer a230 a242 a243 ❇ a249 a243 ❉ .
• OR. From a230 ❇ a242 a243 and a230 ❉ a242 a243 infer a230 ❇ a250 a230 ❉ a242 a243 .
• From a230 a242 a243 ❇ and a230 a242 a243 ❉ infer a230 a249 a243 ❉ a242 a243 ❇ (cautious monotonicity).

LLE states that the syntactic form of the antecedent is irrelev a251 ant. Thus, if a230 ❇ and a230 ❉ are equivalent, we can deduce a230 ❉ a242 a243 from a230 ❇ a242 a243 . RW describes a similar property of the consequent: If a243 (logically) entails a243 ➢ , then we can deduce a230 a242 a243 ➢ from a230 a242 a243 . This allows us to combine default and logical reasoning. REF states that a230 is always a default conclusion of a230 . AND states that we can combine two default conclusions. If we can conclude by default both a243 ❇ and a243 ❉ from a230 , then we can also conclude a243 ❇ a249 a243 ❉ from a230 . OR states that we are allowed to reason by cases. If the same default conclusion follows from each of two antecedents, then it also follows from their disjunction. CM states that if a243 ❇ and a243 ❉ are two default conclusions of a230 , then discovering that a243 ❉ holds when a230 holds (as would be expected, given the default) should not cause us to retract the default conclusion a243 ❇ .

The fact that the KLM properties characterize so many different semantic approaches has been viewed as rather surprising, since these approaches seem to capture quite different intuitions. As Pearl 1989 said of the equivalence between ➐ - semantics and preferential structures, "It is remarkable that two totally different interpretations of defaults yield identical sets of conclusions and identical sets of reasoning machinery." Plausibility measures help us understand why this should be so. In fact, plausibility measures provide a much deeper understanding of exactly what properties a semantic approach must have in order to be characterized by the KLM properties.

The first step to obtaining this understanding is to give semantics to defaults using plausibility. A plausibility structure is a tuple ✆ ✝ ✟ ✭ ✮ ✟ a241 ✍ , where ✭ ✮ is a plausibility measure on ✝ . A conditional a230 a242 a243 holds in this structure if either ✭ ✮ ✆ ✏ ✏ a230 ✕ ✕ ✍ ✙ ✿ or ✭ ✮ ✆ ✏ ✏ a230 a249 a243 ✕ ✕ ✍ ➑ ✭ ✮ ✆ ✏ ✏ a230 a249 a253 a243 ✕ ✕ ✍ (where ✏ ✏ a239 ✕ ✕ is the set of worlds satisfying the formula a239 ). This approach is just a generalization of the approach first used to define defaults with possibility measures [Dubois and Prade, 1991]. Note that if ✭ ✮ satisfies CPl5, this is equivalent to saying that ✭ ✮ ✆ ✏ ✏ a243 ✕ ✕ ❐ ✏ ✏ a230 ✕ ✕ ✍ ➑ ✭ ✮ ✆ ✏ ✏ a253 a243 ✕ ✕ ❐ ✏ ✏ a230 ✕ ✕ ✍ if ✏ ✏ a230 ✕ ✕ ❍ ✙ ✿ (the implicit assumption here is that ✏ ✏ a230 ✕ ✕ ❃ ✡ ➢ iff ✏ ✏ a230 ✕ ✕ ❍ ✙ ✿ ).

While this definition of defaults in terms of plausibility is easily seen to satisfy REF, RW, and LLE, it does not satisfy AND, OR, or CM in general. It is easy to construct counterexamples taking ✭ ✮ to be a probability measure ✭ ➱ (in which case the definition boils down to a230 a242 a243 if ✭ ➱ ✆ ✏ ✏ a230 ✕ ✕ ✍ ✙ ✑ or ✭ ➱ ✆ ✏ ✏ a243 ✕ ✕ ❐ ✏ ✏ a230 ✕ ✕ ✍ ➑ ✓ ➘ ❢ ). As observed earlier, if ✭ ✮ satisfies Pl4 (which it does not in general if ✭ ✮ is a probability measure), then the AND rule is satisfied. As shown in [Friedman and Halpern, 1996a], Pl4 also suffices to guarantee CM (cautious monotonicity). The only additional property that is needed to guarantee that OR holds is the following:

A plausibility structure ✆ ✝ ✟ ✭ ✮ ✟ a241 ✍ is qualitative if ✭ ✮ satisfies Pl1-5. In [Friedman and Halpern, 1996a], it is shown that a necessary and sufficient condition for a collection of plausibility structures to satisfy the KLM properties is that they be qualitative. More precisely, given a class ➓ of plausibility structures, a default ❁ is entailed by a set a254 of defaults in ➓ , written a254 ❐ ✙ ➛ ❁ , if all structures in ➓ that satisfy all the defaults in a254 also satisfy ❁ . Let a255 a0 ✂ ✄ consist of all qualitative plausibility structures. Write a254 a245 P a230 a242 a243 if a230 a242 a243 is provable from a254 using the KLM properties.

Theorem 4.2: [Friedman and Halpern, 1996a] a255 ▲ a255 a0 ✂ ✄ if and only if for all a254 , a230 , and a243 , if a254 a245 P a230 a242 a243 then a254 ❐ ✙ ✆ a230 a242 a243 .

In [Friedman and Halpern, 1996a], it is shown that possibility structures, ⑩ -structures, preferential structures, and PPDs can all be viewed as qualitative plausibility structures. Theorem 4.2 thus shows why the KLM properties hold in all these cases. Why are there no further properties (that is, why are the KLM properties not only sound, but complete)? To show that the KLM properties are complete with respect to a class a255 of structures, we have to ensure that a255 contains "enough" structures. In particular, if a254 ❍ a245 P a230 a242 a243 , we want to ensure that there is a plausibility structure ✝ ✞ ❃ a255 such that ✝ ✞ ❐ ✙ ✂ ✄ a254 and ✝ ✞ ❍ ❐ ✙ ✂ ✄ a230 a242 a243 . The following weak condition on a255 guarantees this.

Definition 4.3: We say that a255 is rich if for every collection a230 ❇ ✟ ➋ ➋ ➋ ✟ a230 ➳ , ➵ ➑ ✓ , of mutually exclusive formulas, there is a plausibility structure ✝ ✞ ✙ ✆ ✝ ✟ ✭ ✮ ✟ a241 ✍ ❃ a255 such that:

The richness condition is quite mild. Roughly speaking, it says that we do not have a priori constraints on the relative plausibilities of a collection of disjoint sets. It is easily seen to hold for the plausibility structures that arise from preferential structures (resp., possibility structures, ⑩ -structures, PPDs). More importantly, richness is a necessary and sufficient condition to ensure that the KLM properties are complete.

Theorem 4.4: [Friedman and Halpern, 1996a] A set a255 of qualitative plausibility structures is rich if and only if for all finite a254 and defaults a230 a242 a243 , we have that a254 ❐ ✙ ✆ a230 a242 a243 implies a254 a245 P a230 a242 a243 .

This result shows that if the KLM properties are sound with respect to a class of structures, then they are almost inevitably complete as well. More generally, Theorems 4.2 and 4.4 explain why the KLM properties are sound and complete for so many approaches.

The discussion up to now has focused on propositional defaults, but using plausibility, it is fairly straightforward to extend to the first-order case; see [Friedman et al., 2000].

5 Expectation and Decision Theory

Agents must make decisions. Perhaps the best-known rule for decision making is that of maximizing expected utility. This requires that agents have probabilities for many events of interest, and numerical utilities. But many other decision rules have been proposed, including minimax, regret minimization, and rules that involve representations of uncertainty other than probability. Again, using plausibility allows us to understand what is required to get various desirable properties of decision rules.

Since expectation plays such a key role in maximizing expected utility, I start by considering expectation. Given a probability measure ☞ on some sample space ✝ , the corresponding expectation function a237 ✠ maps gambles over ✝

(that is, random variables with domain ✝ and range the reals) to ☛ reals. There are a number of equivalent definitions of a237 ✠ . The standard one is

(Here I am implicitly assuming that a240 ✙ ➁ (that is, the set ⑥ ⑦ ❡ a240 ✆ ⑦ ✍ ✙ ➁ ⑨ ) is measurable.)

As is well known, a237 ✠ is linear (a237 ✠ ✆ ➞ a240 ✩ ✔ ✍ ✙ ➞ a237 ✠ ✆ a240 ✍ ✩ a237 ✠ ✆ ✔ ✍ ), monotonic (if a240 ✴ ✔ , then a237 ✠ ✆ a240 ✍ ✴ a237 ✠ ✆ ✔ ✍ ), and it maps a constant function to its value (that is, ✙ ➞ is the gamble that maps all elements of ✝ to ➞ , the a237 ✠ ✆ ✙ ➞ ✍ ✙ ➞ ). Moreover, these three properties characterize probabilistic expectation functions. If an expectation function a237 has these properties, then a237 ✙ a237 ✠ for some probability measure ☞ .

A ✝ -✻ ➢ expectation function is simply a mapping from random variables with domain ✝ and range some ordered set ✻ ➢ to ✻ ➢ . Here I focus on expectation functions that are generated by some plausibility measure, just as a237 ✠ is generated from ☞ , using a definition in the spirit of (1). To do this, we need analogues of ✩ and ❒ , much in the spirit of (but not identical to) the a213 and a214 used in the definition of algebraic cps.

Definition 5.1 : An expectation domain is a tuple ✆ ✻ ✟ ✻ ➢ ✟ ✛ ✟ ✜ ✍ , where ✻ and ✻ ➢ are sets ordered by ✴ ✼ and ✴ ✼ ✣ , respectively, ✻ is a set of plausibility values (so that it has elements ✿ and ✾ such that ✿ ✴ ✼ ❁ ✴ ✼ ✾ for all ❁ ❃ ✻ ), ✛ ❡ ✻ ➢ ❒ ✻ ➢ ❤ ✻ ➢ and ✜ ❡ ✻ ➢ ❒ ✻ ❤ ✻ ➢ .

Given an expectation domain ✆ ✻ ✟ ✻ ➢ ✟ ✛ ✟ ✜ ✍ and a plausibility measure ✭ ✮ on some set ✝ , it is possible to define a ✝ -✻ ➢ expectation function a237 ✥ ✧ by using the obvious analogue of (1), replacing ✩ by ✛ and ❒ by ✜ .

What does this buy us? For one thing, we can try to characterize the properties of ✛ and ✜ that give a237 ✥ ✧ properties of interest, such as linearity and monotonicity (see [Halpern, 2000b] for details). For another, it turns out that all standard decision rules can be expressed as expected utility maximization with respect to an appropriate choice of plausibility measure, ✛ , and ✜ . To make this precise, assume that there is a set ✩ of possible actions that an agent can perform. An action ✪ maps a world ⑦ ❃ ✝ to an outcome. For simplicity, I identify outcomes with world-action pairs ✆ ⑦ ✟ ✪ ✍ . Assume that the agent has a utility function ✬ on outcomes. In the examples below, the range of the utility function is the reals but, in general, it can be an arbitrary partially ordered set ✻ ➢ . Let ✬ ✭ be the random variable such that ✬ ✭ ✆ ⑦ ✍ ✙ ✬ ✆ ⑦ ✟ ✪ ✍ . The agent is uncertain about the actual world; this uncertainty is represented by some plausibility measure. The question is which action the agent should choose.

As I said earlier, if the agent's uncertainty is represented by a probability measure ☞ , the standard decision rule is to choose the action that maximizes expected utility. That is, we choose an action ✪ such that a237 ✠ ✆ ✪ ✍ a231 a237 ✠ ✆ ✪ ➢ ✍ for all ✪ ➢ ❃ ✩ . However, there are other well-known decision rules.

• ✄ For minimax, let worst ✆ ✪ ✍ ✙ ❽ ❾ ❿ ⑥ ✬ ✭ ✆ ⑦ ✍ ❡ ⑦ ❃ ✝ ⑨ ; worst ✆ ✪ ✍ is the utility of the worst-case outcome if ✪ is performed. This too leads to a total preference order on actions, where ✪ is preferred to ✪ ➢ if worst ✆ ✪ ✍ a231
• worst ✆ ✪ ➢ ✍ . The minimax rule says to choose the action ✪ (or one of them, in case of ties) such that worst ✆ ✪ ✍ is highest. The action chosen according to this rule is the one with the best worst-case outcome. Notice that minimax makes sense no matter how uncertainty is represented. Now take ✻ ✙ ⑥ ✑ ✟ ✓ ⑨ and ✻ ➢ ✙ ❶ ✴ , both with the standard order, and consider the plausibility measure ✭ ✮ ➍ ➍ , where ✭ ✮ ➍ ➍ ✆ ✁ ✍ ✙ ✓ if ✁ ❍ ✙ ✗ and ✭ ✮ ➍ ➍ ✆ ✗ ✍ ✙ ✑ . Let ✛ be ❽ ❾ ❿ and let ✜ be multiplication. With this choice of ✛ and ✜ , it is easy to see that a237 ✥ ✧ a223 a223 ✆ ✬ ✭ ✍ ✙ worst ✆ ✪ ✍ , so expected utility maximization with respect to ✭ ✮ ➍ ➍ is minimax.
• ✄ As a first step to defining regret minimization, for each world ⑦ , let ✪ ② be an action that gives the best outcome in world ⑦ ; that is, ✬ ✆ ⑦ ✟ ✪ ② ✍ a231 ✬ ✆ ⑦ ✟ ✪ ✍ for all ✪ ❃ ✩ . The regret of ✪ inworld ⑦ is ✬ ✆ ⑦ ✟ ✪ ② ✍ a114 ✬ ✆ ⑦ ✟ ✪ ✍ ; that is, the regret of ✪ in ⑦ is the difference between the utility of performing the best action in ⑦ (the action that the agent would perform, presumably, if she knew the actual world was ⑦ ) and that of performing ✪ in ⑦ . Finally, define regret ✆ ✪ ✍ ✙ ❽ ❦ ✺ ② ③ ❣ regret ✆ ✪ ✟ ⑦ ✍ . Intuitively, if regret ✆ ✪ ✍ ✙ a224 , then ✪ is guaranteed to be within a224 of the best action the agent could perform, even if the she knew exactly what the actual world was. The decision rule of minimizing regret chooses the action ✪ such that regret ✆ ✪ ✍ is a minimum.

To express regret in terms of maximizing expected utility, it is easiest to assume that for each action ✪ , ❽ ❦ ✺ ② ③ ❣ ✬ ✭ ✆ ⑦ ✍ ✙ ✓ . This assumption is without loss of generality: if ✬ ➢ ✆ ⑦ ✟ ✪ ✍ ✙ ✬ ✆ ⑦ ✟ ✪ ✍ a114 ❽ ❦ ✺ ② ✣ ③ ❣ ✬ ✆ ⑦ ➢ ✟ ✪ ✍ ✩ ✓ , then ❽ ❦ ✺ ② ③ ❣ ✬ ➢ ✭ ✆ ⑦ ✍ ✙ ✓ , and minimizing regret with respect ✬ ➢ gives the same result as minimizing regret with respect to ✬ . With this assumption, take ✻ ✙ ✏ a114 ❻ ✟ ✓ ✕ with the standard ordering and ✻ ➢ ✙ ❶ ✴ with the reverse ordering, that is ➁ ❆ ✼ ✣ ➅ if ➁ ➑ ➅ . Let ✭ ✮ ✽ ✿ ❀ ✆ ✁ ✍ ✙ ❽ ❦ ✺ ② ③ ④ ➝ ✭ ③ ❁ ✬ ✆ ✪ ✟ ⑦ ✍ , let ➞ ✜ ➟ ✙ ➞ a114 ➟ , and let ➞ ✛ ➟ ✙ ❽ ❾ ❿ ✆ ➞ ✟ ➟ ✍ . Intuitively, ✭ ✮ ✆ ✁ ✍ ✜ ➟ is the regret an agent would feel if she is given utility ➟ but could have performed the action that would give her the best outcome on her choice of world in ✁ . With this choice of ✛ and ✜ , it is easy to see that a237 ✥ ✧ ❃ ❅ ❆ ✆ ✬ ✭ ✍ ✙ regret ✆ ✪ ✍ , so expected utility maximization with respect to ✭ ✮ ✽ ✿ ❀ is just regret minimization (given the ordering on ✻ ➢ ).

• ✄ Suppose that uncertainty is represented by a set ➓ of probability measures indexed by some set ❶ . There are two natural ways to get a partial order on actions from ➓ and a real-valued utility ✬ . Define ❈ ❇ ➛ so that ✪ ❈ ❇ ➛ ✪ ➢ iff ❽ ❾ ❿ ✠ ③ ➛ a237 ✠ ✆ ✬ ✭ ✍ a231 ❽ ❦ ✺ ✠ ③ ➛ a237 ✠ ✆ ✬ ❋ ❍ ✍ . That is, ✪ is preferred to ✪ ➢ if the expected utility of performing ✪ is at least that of performing ✪ ➢ , regardless which probability measure in ➓ describes the actual probability. Naturally, ❈ ❇ ➛ is only a partial order on actions. A more refined partial order can be obtained as follows: Define ✪ ❈ ❉ ➛ ✪ ➢ if a237 ✠ ✆ ✬ ✭ ✍ a231 a237 ✠ ✆ ✬ ✭ ✣ ✍ for all ☞ ❃ ➓ . It is easy to show that if ✪ ❈ ❇ ➛ ✪ ➢ then ✪ ❈ ❉ ➛ ✪ ➢ , although the converse may not hold. For example, suppose that ➓ ✙ ⑥ ☞ ✟ ☞ ➢ ⑨ and actions ✪ and ✪ ➢ are such

that a237 ✠ ✆ ✬ ✭ ✍ ✙ ❢ , a237 ✠ ✣ ✆ ✬ ✭ ✍ ✙ ▲ , a237 ✠ ✆ ✬ ✭ ✣ ✍ ✙ ✓ , and a237 ✠ ✣ ✆ ✬ ✭ ✣ ✍ ✙ ◆ . Then ✪ and ✪ ➢ are incomparable according to ❈ ❇ ➛ , but ✪ ❈ ❉ ➛ ✪ ➢ .

Let the set ✻ of plausibility values be that used for ✭ ✮ ➛ , that is, the functions from ❶ to ✏ ✑ ✟ ✓ ✕ , with the pointwise ordering. Let ✻ ➢ be the functions from ❶ to ❶ ✴ , let ✛ be pointwise addition, and let ✜ be pointwise multiplication. The difference between ❈ ❇ ➛ and ❈ ❉ ➛ is captured by considering two different orders on ✻ ➢ . For ❈ ❇ ➛ , order ✻ ➢ by ➑ ❇ ✼ ✣ , where ➸ a231 ❇ ✼ ✣ ➻ if ❽ ❾ ❿ ➯ ③ ➂ ➸ ✆ ➲ ✍ a231 ❽ ❦ ✺ ➯ ③ ➂ ➻ ✆ ➲ ✍ , while for ❈ ❉ ➛ , order ✻ ➢ by ➑ ❉ ✼ ✣ , where ➸ a231 ❉ ✼ ✣ ➻ if ➸ ✆ ➲ ✍ a231 ➻ ✆ ➲ ✍ for all ➲ ❃ ❶ . If a237 ✥ ✧ ➥ is the expectation function corresponding to this definition of ✛ and ✜ , then it is easy to see that

It can be shown that every partial order on actions can be represented as the ordering induced by expected utility according to some plausibility measure on ✝ . That is, given some partial order ❈ on actions that can be taken in some set ✝ of possible worlds, there is a plausibility measure ✭ ✮ on ✝ and expectation domain ✆ ✻ ✟ ✻ ➢ ✟ ✛ ✟ ✜ ✍ such that the range of ✭ ✮ is ✻ and a utility function on ✝ ❒ ✩ with range ✻ ➢ such that a237 ✥ ✧ ✆ ✬ ✭ ✍ a231 a237 ✥ ✧ ✆ ✬ ✭ ✣ ✍ iff ✪ ❈ ✪ ➢ . Thus, viewing decision rules as instances of expected utility maximization with respect to the appropriate expectation function provides a general framework in which to study decision rules. For example, it becomes possible to ask what properties of an expectation domain are needed to get various of Savage's 1954 postulates. I hope to report on this in future work.

6 Compact Representation of Uncertainty

Suppose that ✝ is a set of possible worlds characterized by ➵ binary random variables ❱ ✙ ⑥ a240 ❇ ✟ ➋ ➋ ➋ ✟ a240 ➳ ⑨ (or, equivalently, ➵ primitive propositions). That is, a world ⑦ ❃ ✝ is a tuple ✆ ➁ ❇ ✟ ➋ ➋ ➋ ✟ ➁ ➳ ✍ , where ➁ ➯ ❃ ⑥ ✑ ✟ ✓ ⑨ is the value of a240 ➯ . That means that there are ❢ ➳ worlds in ✝ , say ⑦ ❇ ✟ ➋ ➋ ➋ ✟ ⑦ ❉ ❲ . A naive description of a probability measure on ✝ requires ❢ ➳ a114 ✓ numbers, ❳ ❇ ✟ ➋ ➋ ➋ ✟ ❳ ❉ ❲ ❩ ❇ , where ❳ ➯ is the probability of world ⑦ ➯ . (Of course, the probability of ⑦ ❉ ❲ is determined by the other probabilities, since they must sum to 1.)

If ➵ is relatively small, describing a probability measure in this naive way is not so unreasonable, but if ➵ is, say, 1000 (certainly not unlikely in many practical applications), then it is completely infeasible. One of the most significant recent advances in AI has been in work on Bayesian networks [Pearl, 1988], a tool that allows probability measures to be represented in a compact way and manipulated in a computationally feasible way. I briefly reviewBayesian networks here and then discuss the extent to which the ideas can be applied to other representations of uncertainty. More details can be found in [Halpern, 2000a].

Recall that a (qualitative) Bayesian network (sometimes called a belief network) is a dag, that is, a directed acyclic graph, whose nodes are labeled by random variables. Informally, the edges in a Bayesian network can be thought of as representing causal influence.

Given a Bayesian network ❬ and a node a240 in ❬ , think of the ancestors of a240 in the graph as those random variables that have a potential influence on a240 . This influence is mediated through the parents of a240 , those ancestors of a240 directly connected to a240 . That means that a240 should be conditionally independent of its ancestors, given its parents. The formal definition requires, in fact, that a240 be independent not only of its ancestors, but of its nondescendants, given its parents, where the nondescendants of a240 are those nodes ✔ such that a240 is not the ancestor of ✔ .

Definition 6.1: Given a qualitative Bayesian network ❬ , let ✭ ❦ ➱ ❭ ✆ a240 ✍ be the parents of the random variable a240 in ❬ ; let ❬ ❪ ❴ ❛ ✆ a240 ✍ be all the descendants of a240 , that is, a240 and all those nodes ✔ such that a240 is an ancestor of ✔ ; let ❜ ❝ ❭ ✆ a240 ✍ , the nondescendants of a240 in ❬ , consist of ❱ a114 ❝ ❞ ♦ ❭ ✆ a240 ✍ . The Bayesian network ❬ (qualitatively) represents the probability measure ☞ if a240 is conditionally independent of its nondescendants given its parents, for all a240 ❃ ❱ .

A qualitative Bayesian network ❬ gives qualitative information about dependence and independence, but does not actually give the values of the conditional probabilities. A quantitative Bayesian network provides more quantitative information, by associating with each node a240 in ❬ a conditional probability table (cpt) that quantifies the effects of the parents of a240 on a240 . For example, if a240 's parents in ❬ are ✔ and ❢ , then the cpt for a240 would have an entry denoted ❁ ❣ a228 a80 ➝ ✐ a228 a221 for all ✆ a233 ✟ a224 ✍ ❃ ⑥ ✑ ✟ ✓ ⑨ ❉ . As the notation is meant to suggest, ❁ ❣ a228 a80 ❦ ✐ a228 a221 ✙ ☞ ✆ a240 ✙ ✓ ❐ ✔ ✙ a233 a209 ❢ ✙ a224 ✍ for the plausibility measure ☞ represented by ❬ . (Of course, there is no need to have an entry for ☞ ✆ a240 ✙ ✑ ❐ ✔ ✙ a233 a209 ❢ ✙ a224 ✍ , since this is just ✓ a114 ☞ ✆ a240 ✙ ✓ ❐ ✔ ✙ a233 a209 ❢ ✙ a224 ✍ .) Formally, a quantitative Bayesian network is a pair ✆ ❬ ✟ ➸ ✍ consisting of a qualitative Bayesian network ❬ and a function ➸ that associates with each node a240 in ❬ a cpt, where there is an entry in the interval ✏ ✑ ✟ ✓ ✕ in the cpt for each possible setting of the parents of a240 . If a240 is a root of ❬ , then the cpt for a240 can be thought of as giving the unconditional probability that a240 ✙ ✓ .

Definition 6.2 : A quantitative Bayesian network ✆ ❬ ✟ ➸ ✍ (quantitatively) represents, or is compatible with, the probability measure ☞ if ❬ qualitatively represents ☞ and the cpts agree with ☞ in that, for each random variable a240 , the entry in the cpt for a240 given some setting ✔ ❇ ✙ ➅ ❇ ✟ ➋ ➋ ➋ ✟ ✔ a221 ✙ ➅ a221 of its parents is ☞ ✆ a240 ✙ ✓ ❐ ✔ ❇ ✙ ➅ ❇ a209 ➋ ➋ ➋ a209 ✔ a221 ✙ ➅ a221 ✍ if ☞ ✆ ✔ ❇ ✙ ➅ ❇ a209 ➋ ➋ ➋ a209 ✔ a221 ✙ ➅ a221 ✍ ❍ ✙ ✑ . (It does not matter what the cpt entry for ✔ ❇ ✙ ➅ ❇ ✟ ➋ ➋ ➋ ✟ ✔ a221 ✙ ➅ a221 is if ☞ ✆ ✔ ❇ ✙ ➅ ❇ a209 ➋ ➋ ➋ a209 ✔ a221 ✙ ➅ a221 ✍ ✙ ✑ .)

It can easily be shown using the chain rule for probability (see, for example, [Pearl, 1988]) that if ✆ ❬ ✟ ➸ ✍ quantitatively represents ☞ , then ☞ can be completely reconstructed from ✆ ❬ ✟ ➸ ✍ . More precisely, the ❢ ➳ values ☞ ✆ a240 ❇ ✙ ➁ ❇ a209 ➋ ➋ ➋ a209 a240 ➳ ✙ ➁ ➳ ✍ can be computed from ✆ ❬ ✟ ➸ ✍ ; from these values, ☞ ✆ ✁ ✍ can be computed for all ✁ ▲ ✝ .

Bayesian networks for probability have a number of important properties:

1. Every probability measure is represented by a qualitative Bayesian network (in fact, in general there are many qualitative Bayesian networks that represent a given probability measure).

1. A qualitative Bayesian network that represents a probability measure ☞ can be extended to a quantitative Bayesian network that represents ☞ , by adding cpts.
2. A quantitative Bayesian network represents a unique probability measure. This is important because if a world is characterized by the values of ➵ random variables, so that there are ❢ ➳ worlds, a quantitative Bayesian network can often represent a probability measure using far fewer than ❢ ➳ numbers. If a node in the network has a224 parents, then its conditional probability table has ❢ a221 entries. Therefore, if each node has at most a224 parents in the graph, then there are at most ➵ ❢ a221 entries in all the cpts. If a224 is small, then ➵ ❢ a221 can be much smaller than ❢ ➳ a114 ✓ .
3. A Bayesian network supports efficient algorithms for computing conditional probabilities of the form ✭ ➱ ✆ a240 ➯ ✙ ➁ ➯ ❐ a240 a80 ✙ ➁ a80 ✍ ; that is, they allow for efficient evaluation of probabilities given some information.

To what extent is probability necessary to achieve these properties? More precisely, what properties of probability are needed to achieve them? Here again, plausibility measures allow us to answer this question.

Given a cps ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ✭ ✮ ✍ , ✁ ✟ ✂ ❃ ✡ are plausibilistically independent given ✂ ➢ (with respect to ✭ ✮ ), written ❶ Pl ✆ ✁ ✟ ✂ ❐ ✂ ➢ ✍ , if ✂ a209 ✂ ➢ ❃ ✡ ➢ implies ✭ ✮ ✆ ✁ ❐ ✂ a209 ✂ ➢ ✍ ✙ ✭ ✮ ✆ ✁ ❐ ✂ ➢ ✍ and ✁ a209 ✂ ➢ ❃ ✡ ➢ implies ✭ ✮ ✆ ✂ ❐ ✁ a209 ✂ ➢ ✍ ✙ ✭ ✮ ✆ ✂ ❐ ✂ ➢ ✍ . This definition is meant to capture the intuition that (conditional on ✂ ➢ ) ✁ and ✂ are independent if learning about ✁ gives no information about ✂ and learning about ✂ gives no information about ✁ . Note the explicitly symmetric nature of the definition. In the case of probability, if learning about ✁ gives no information about ✂ , then it is immediate that learning about ✂ gives no information about ✁ . This does not hold for an arbitrary plausibility measure. 3

If ♠ ✙ ⑥ a240 ❇ ✟ ➋ ➋ ➋ ✟ a240 ➳ ⑨ , ♥ ✙ ⑥ ✔ ❇ ✟ ➋ ➋ ➋ ✟ ✔ ➍ ⑨ , and ♦ ✙ ⑥ ❢ ❇ ✟ ➋ ➋ ➋ ✟ ❢ a221 ⑨ are sets of random variables, then ♠ and ♥ are conditionally independent given ♦ (with respect to ✭ ✮ ) if a240 ❇ ✙ ➁ ❇ a209 ➋ ➋ ➋ a209 a240 ➳ ✙ ➁ ➳ is conditionally independent of ✔ ❇ ✙ ➅ ❇ a209 ➋ ➋ ➋ a209 ✔ ➍ ✙ ➅ ➍ given ❢ ❇ ✙ ♣ ❇ a209 ➋ ➋ ➋ a209 ❢ a221 ✙ ♣ a221 for all choices of ➁ ❇ ✟ ➋ ➋ ➋ ✟ ➁ ➳ ✟ ➅ ❇ ✟ ➋ ➋ ➋ ✟ ➅ ➍ ✟ ♣ ❇ ✟ ➋ ➋ ➋ ✟ ♣ a221 .

With these definitions, the notion of a qualitative Bayesian network as defined in Definition 6.1 makes perfect sense if the probabilitymeasure ☞ is replaced by a plausibilitymeasure ✭ ✮ everywhere. The following result shows that representation by a qualitative Bayesian network is possible not just in the case of probability, but for any algebraic cps.

3 An equivalent definition of ◗ and a114 being independent with respect to a probability measure a80 is that a80 ❨ ◗ a115 a114 ✉ a114 ✇ ❪ ❴ a80 ❨ ◗ ✉ a114 ✇ ❪ ① a80 ❨ a114 ✉ a114 ✇ ❪ . However, I want to give a definition of independence that does not require an analogue to multiplication. But even in an algebraic cps, the requirement that a80 ❨ ◗ a115 a114 ✉ a114 ✇ ❪ ❴ a80 ❨ ◗ ✉ a114 ✇ ❪ ④ a80 ❨ a114 ✉ a114 ✇ ❪ is not always equivalent to the definition given here (see [Halpern, 2000a]). Also note that if a114 a115 a114 ✇ ⑥ ⑧ ⑨ ✇ (in the case of probability, this would correspond to a114 a115 a114 ✇ having probability 0), then ❶ ❷ ❨ ◗ ✉ a114 a115 a114 ✇ ❪ is not defined. In this case, there is no requirement that ❶ ❷ ❨ ◗ ✉ a114 a115 a114 ✇ ❪ ❴ ❶ ❷ ❨ ◗ ✉ a114 ✇ ❪ . A similar observation holds if ◗ a115 a114 ✇ ⑥ ⑧ ⑨ ✇ .

Theorem 6.3: ([Halpern, 2000a]) If ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ✭ ✮ ✍ is an algebraic cps, then there is a qualitative Bayesian network that represents ✭ ✮ .

Clearly a qualitative Bayesian network that represents ✭ ✮ can be extended to a quantitative Bayesian network ✆ ❬ ✟ ➸ ✍ that represents ✭ ✮ by filling in the conditional plausibility tables. But does a quantitative Bayesian network ✆ ❬ ✟ ➸ ✍ represents a unique (algebraic) plausibility measure? Recall that, for the purposes of this section, I have taken ✝ to consist of the ❢ ➳ worlds characterized by the ➵ binary random variables in ❱ . Let PL ✼ ➝ ❹ ➝ ❺ consist of all algebraic standard cps's of the form ✆ ✝ ✟ ✡ ✟ ✡ ➢ ✟ ✭ ✮ ✍ , where ✡ ✙ ❢ ❣ , so that all subsets of ✝ are measurable, and the range of ✭ ✮ is ✻ . With this notation, the question becomes whether a quantitative Bayesian network ✆ ❬ ✟ ➸ ✍ such that the entries in the cpts are in ✻ determines a unique element in PL✼ ➝ ❺ ➝ ❹ . It turns out that the answer is yes, provided that ✆ ✻ ✟ a213 ✟ a214 ✍ satisfies some conditions. The conditions are similar in spirit to Alg1-4, except that now they are conditions on ✆ ✻ ✟ a213 ✟ a214 ✍ , rather than conditions on a plausibility measure; I omit the details here (again, see [Halpern, 2000a]). The key point is that these conditions are sufficient to allow an arbitrary plausibility measure to have a compact representation. Moreover, since the typical algorithms in probabilistic Bayesian networks use only algebraic properties of ✩ and ❒ , they apply with essentially no change to algebraic plausibility measures.

7 Conclusions

There is no reason to believe that one representation of uncertainty is best for all applications. This makes it useful to have a framework in which to compare representations. As I hope I have convinced the reader, plausibility measures give us such a framework, and provide a vantage point from which to look at representations of uncertainty and understand what makes them tick-what properties of each one are being used to get results of interest. More discussion of these and related topics can be found in [Halpern, 2000c].