That is, after updating, we should ascribe probability 1 to the evidence we have obtained. 

Another reasonable principle to require is what van Fraassen calls symmetry. We can also think of it as representation independence, in the sense of [Halpern and Koller 1995]. Intuitively, suppose we represent a situation using the worlds in W' rather than those in W. Let f transform W to W'; there is a corresponding transformation f* of a probability Pr on W to a probability f*(Pr) on W'. Then we would expect upd to respect this transformation. Roughly speaking, this means that if Pr' = upd(Pr, B), then we would expect f*(Pr') = upd(f*(Pr), f(B)). More precisely, if B � W' and Pr' = upd(Pr, f-1 (B)), then we would expect f*(Pr') = upd(f*(Pr), B). The formal definition is given in Section 3, but an example here might help explain the intuition. 

Example 1.1: Consider two agents who are reasoning about a given situation. One uses the primitive propositions p, q, and r; the second uses p and q. Let W consist of the eight truth assignments to p, q, and r, and let W' consist of the four truth assignments top and q. We take the eight worlds in W to be of the form Wijk, i, j, k E {0, 1 }, where i, j, and k give the truth value of p, q, and r, respectively. Thus, for example, in w101, p and r are true while q is false. 

Similarly, we take the worlds in W' to have the form w�j
. We now consider the obvious mapping f from W 
toW' that maps Wijk to w�j· Given a measure Pr on W, f induces a measure f*(Pr) on W' in the natural way, i.e., by taking f*(Pr)(w�j
) = Pr( { Wijo, Wijd ). 

We want it to be the case that our updating rule respects this transformation. In this case, that would mean that f*( upd(Pr, f-1(B))) = upd(f*(Pr), B) for each B � W'. Thus, for example, we would have f*( upd(Pr, { Wijo, Wijl}) = upd(f*(Pr), {wij} ). I 
Van Fraassen showed that the only updating rule that is representation independent in this sense and satisfies 
(1) is conditioning. 

We can apply van Fraassen's approach to the sets-ofmeasures case in a straightforward way. We again consider update functions that take two arguments, but now the first argument is a set of probability measure rather than a single probability measure, and the output is also a set of probability measures. Van Fraassen's two postulates have obvious analogues in this setting (which we formalize in Section 3). However, as we show by example, they are no longer strong enough to characterize conditioning. 

One interesting update function that satisfies both conditions is what Voorbraak [1996] has called constraining. This updating function is defined as follows: given a set X of probability measures and an observation B, it returns all the measures in X that assign B probability 1. That is, the observation B is viewed as placing a constraint on the set of probability measure-namely, that B must be assigned probability 1. We then return all the measures in the set that satisfy this new constraint. Voorbraak argues that constraining is actually more appropriate than conditioning when it comes to capturing a probabilistic analogue of the notion of expansion in the AGM [Alchourron, Gardenfors, and Makinson 1985] theory of belief change (where expansion is how beliefs change when we get extra information that is consistent with previously-held beliefs). 

In Section 3, we provide seven postulates on update functions that suffice to guarantee that an update function on sets of measures acts like conditioning. Besides van Fraassen's postulates, our postulates include a "homomorphism" postulate, which says that the result of updating a set X of measures is the union of the result of updating each element in X separately, and a compositionality postulate, which says that updating by B and then by C is the same as updating by B n C (and hence also the same as updating by C and then by B). We also include a postulate that limits the amount by which the post-update probability of an event can exceed the value it would obtain under conditioning. The intuition for this is that an extremely improbable event should not receive a postupdate probability that is "too large". The postulate that we use to capture this intuition is arguably too strong; it is an open problem to what extent it can be weakened. 

Although our postulates are quite strong, we show that no subset of them suffices to force conditioning. Interestingly, if we drop our last postulate, then there are exactly two update functions that are consistent with the remaining six: conditioning and constraining. 

We believe we are the first to try to axiomatize the updating of sets of probability measures, but others have certainly examined the issue of updating other notions of uncertainty that are related to sets of probability measures. Besides the work of Voorbraak cited above, we briefly mention three other lines of research: 
- It is well known that a Dempster-Shafer belief function Bel [Shafer 1976] can be associated with the set of probability measures that dominate it, that is, the set PBel = {Pr : 
Pr(A) 2:: Bel(A) for all A}. In fact, Bel(A) = 
infPrEPBel Pr(A). One way of defining the update of Bel by a set B, considered in [Fagin and Halpern 1991; Jaffray 1992], is to take Bel(·IB) = 
infPrEPBel Pr(AIB). This approach to updating is quite different from Dempster's Rule of Conditioning [Shafer 1976]. (See [Halpern and Fagin 1992] for a discussion of the differences.) Moral and de Campos [1991] consider yet other approaches to updating belief functions. 

- Gilboa and Schmeidler (1993] consider update rules for non-additive probabilities (of which belief functions are a special case, as are convex sets of probability measures). They show that under certain assumptions, the maximum-likelihood up-