P. Maynard-Zhang and D. Lehmann

Volume 19, 2003

**Links to Full Text:**

We consider the two-fold problem of representing collective beliefs and aggregating these beliefs. We propose a novel representation for collective beliefs that uses modular, transitive relations over possible worlds. They allow us to represent conflicting opinions and they have a clear semantics, thus improving upon the quasi-transitive relations often used in social choice. We then describe a way to construct the belief state of an agent informed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner by accounting for the explicitly encoded conflicts. We give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants of idempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state. Finally, we extend our framework to incorporate voting.

Journal of Artificial Intelligence Research 19 (2003) 155-203 Submitted 1/03; published 9/03 Representing and Aggregating Conflicting Beliefs Pedrito Maynard-Zhang maynarp@muohio.edu Department of Computer Science and Systems Analysis Miami University Oxford, Ohio 45056, USA Daniel Lehmann lehmann@cs.huji.ac.il School of Computer Science and Engineering Hebrew University Jerusalem 91904, Israel Abstract We consider the two-fold problem of representing collective beliefs and aggregatingthese beliefs. We propose a novel representation for collective beliefs that uses modular, transitive relations over possible worlds. They allow us to represent conflicting opinionsand they have a clear semantics, thus improving upon the quasi-transitive relations often used in social choice. We then describe a way to construct the belief state of an agentinformed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner by accounting for the explicitlyencoded conflicts. We give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants ofidempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state.Finally, we extend our framework to incorporate voting. 1. Introduction We are interested in the multi-agent setting where agents are informed by sources of varying levels of reliability, and where agents can iteratively combine their belief states. This setting introduces three problems: (1) Finding an appropriate representation for collective beliefs; (2) Constructing an agent's belief state by aggregating the information from informant sources, accounting for the relative reliability of these sources; and, (3) Combining the information of multiple agents in a manner that is well-behaved under iteration. In addressing the first problem, we take as a starting point total preorders over possible worlds (i.e., interpretations of a specified language) used in the belief revision community to represent individuals' beliefs. The relations describe opinions on the relative likelihood of worlds and can be viewed as encoding all of an agent's conditional beliefs, i.e., not only what he believes now, but what he would believe under all other conditions. This representation is based on the semantical work (cf. Grove, 1988; Katsuno & Mendelzon, 1991) supporting the Alchourr'on, G"ardenfors, and Makinson proposal (Alchourr'on, G"ardenfors, & Makinson, 1985; G"ardenfors, 1988) (known as the AGM theory) for belief revision. The social choice community has dealt extensively with the problem of representing collective preferences (cf. Sen, 1986). However, the problem is formally equivalent to that of representing collective beliefs, so the results are applicable. The classical approach has cfl2003 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved. Maynard-Zhang & Lehmann been to use quasi-transitive relations - relations whose asymmetric restrictions are transitive - over the set of objects. (Total preorders are a special subclass of these relations.) However, these relations do not distinguish between group indifference and group conflict, and this distinction can be crucial. Consider, for example, a situation in which all members of a group are indifferent between movie a and movie b. If some passerby expresses a preference for a, the group may very well choose to adopt this opinion for the group and borrow a. However, if the group was already divided over the relative merits of a and b, we would be wise to hesitate before choosing one over the other just because a new supporter of a appears on the scene. We propose a representation in which the distinction is explicit. Specifically, we propose modular, transitive relations and argue that they solve some of the unpleasant semantical problems suffered by the earlier approach. (We define modularity precisely later, but it can be viewed intuitively as a sufficient relaxation of the totality requirement on total preorders to make the distinction between indifference and conflict possible.) The second problem addresses how an agent should actually go about combining the information received from a set of sources to create a belief state. Such a mechanism should favor the opinions held by more reliable sources, yet allow less reliable sources to voice opinions when higher ranked sources have no opinion. True, under some circumstances it would not be advisable for an opinion from a less reliable source to override the agnosticism of a more reliable source, but often it is better to accept these opinions as default assumptions until better information is available. We define a mechanism that does just this, relying on our generalized representation to circumvent Arrow's (1963) Impossibility Theorem when there are sources of equal reliability. To motivate the third problem, consider the following dynamic scenario: A robot controlling a ship in space receives from a number of communication centers on Earth information about the status of its environment and tasks. Each center receives information from a group of sources of varying credibility or accuracy (e.g., nearby satellites and experts) and aggregates it. Timeliness of decision-making in space is often crucial, so we do not want the robot to have to wait while each center sends its information to some central location for it to be first combined before being forwarded to the robot. Instead, each center sends its aggregated information directly to the robot. Not only does this scheme reduce dead time, it also allows for "anytime" behavior on the robot's part: the robot incorporates new information as it arrives and makes the best decisions it can with whatever information it has at any given point. This distributed approach is also more robust since the degradation in performance is much more graceful should information from individual centers get lost or delayed. In such a scenario, the robot needs a mechanism for combining or fusing the belief states of multiple agents potentially arriving at different times. Moreover, the belief state output by the mechanism should be invariant with respect to the order of agent arrivals. We will describe a simple set-theoretic mechanism that satisfies these requirements as well as a computationally effective way of computing the resulting belief state. The aggregation and fusion mechanisms described so far take into account quality of support for opinions, but completely ignore quantity of support. However, the latter often provides sufficient information to resolve apparent conflicts. Take, for example, the situation where all the sources for the robot above have equal credibility and all except a small minority suggest the robot move the spaceship to avoid a potential collision with an 156 Representing and Aggregating Conflicting Beliefs oncoming asteroid. In such a situation, we often prefer to resolve the conflict by siding with the majority. To this end, we describe how to extend our framework to allow for voting, introducing a novel modular closure operation in the process. After some preliminary definitions, we address each of these topics in turn. 2. Preliminaries We begin by defining various well-known properties of binary relations1; they will be useful to us throughout the paper. Definition 1 Suppose <= is a relation over a finite set Omega , i.e., <=` Omega * Omega .2 We will use x <= y to denote (x, y) 2<= and x 6<= y to denote (x, y) 62<=. The relation <= is: 1. reflexive iff x <= x for all x 2 Omega . It is irreflexive iff x 6<= x for all x 2 Omega . 2. symmetric iff x <= y ) y <= x for all x, y 2 Omega . It is asymmetric iff x <= y ) y 6<= x for all x, y 2 Omega . It is anti-symmetric iff x <= y ^ y <= x ) x = y for all x, y 2 Omega . 3. the asymmetric restriction of a relation <=0 over Omega iff x <= y , x <=0 y ^ y 6<=0 x for all x, y 2 Omega . It is the symmetric restriction of <=0 iff x <= y , x <=0 y ^ y <=0 x for all x, y 2 Omega . 4. total iff x <= y . y <= x for all x, y 2 Omega . 5. modular iff x <= y ) x <= z . z <= y for all x, y, z 2 Omega . 6. transitive iff x <= y ^ y <= z ) x <= z for all x, y, z 2 Omega . 7. quasi-transitive iff its asymmetric restriction is transitive. 8. the transitive closure of a relation <=0 over Omega iff, for some integer n, x <= y , 9w0, . . . , wn 2 Omega . x = w0 <=0 * * * <=0 wn = y for all x, y 2 Omega . (We generally use <=+ to denote the transitive closure of a relation<= .) 9. acyclic iff 8w0, . . . , wn 2 Omega . w0 < * * * < wn implies wn 6< w0 for all integers n, where < is the asymmetric restriction of <=. 10. a total preorder iff it is total and transitive. It is a total order iff it is also antisymmetric. 11. an equivalence relation iff it is reflexive, symmetric, and transitive. 12. fully connected iff x <= y for all x, y 2 Omega . It is fully disconnected iff x 6<= y for all x, y 2 Omega . Proposition 1 1. The transitive closure of a modular relation is modular. 1. We only use binary relations in this paper, so we will refer to them simply as relations. 2. For the reader's convenience, we have included in Appendix B a key to most of the notational symbols used throughout the paper. 157 Maynard-Zhang & Lehmann 2. Every transitive relation is quasi-transitive. 3. (Sen, 1986) Every quasi-transitive relation is acyclic. Given a relation over a set of alternatives and a subset of these alternatives, we often want to pick the subset's "best" elements with respect to the relation. We define this set of "best" elements to be the subset's choice set: Definition 2 If <= is a relation over a finite set Omega , < is its asymmetric restriction, and X ` Omega , then the choice set of X with respect to <= is ch(X, <=) = {x 2 X :6 9x0 2 X. x0 < x}. A choice function is one which assigns to every (non-empty) subset X a (non-empty) subset of X: Definition 3 A choice function over a finite set Omega is a function f : 2Omega ; ! 2Omega ; such that f (X) ` X for every non-empty X ` Omega . Now, every acyclic relation defines a choice function, one which assigns to each subset its choice set: Proposition 2 (Sen, 1986) Given a relation <= over a finite set Omega , the choice set operation ch defines a choice function iff <= is acyclic.3 If a relation is not acyclic, elements involved in a cycle are said to be in a conflict because we cannot order them: Definition 4 Given a relation < over a finite set Omega , x and y are in a conflict wrt < iff there exist w0, . . . , wn, z0, . . . , zm 2 Omega such that x = w0 < * * * < wn = y = z0 < * * * < zm = x, where x, y 2 Omega . Finally, the cardinality of a set Omega will be denoted kOmega k. Assume we are given some language L with a satisfaction relation |= for L. LetW be a finite, non-empty set of possible worlds (interpretations) over L. For a world w 2 W and a sentence p 2 L, w |= p iff p evaluates to true in w. Given a sentence p,| p| = {w 2 W | w |= p}. 3. Representing Collective Beliefs Our representation of collective beliefs generalizes the representation developed in the belief revision community for the conditional beliefs of an individual, so we briefly review it. We then consider implications from social choice for representing collective beliefs. Finally, we describe our proposal and argue for its desirability. 3. Sen's uses a slightly stronger definition of choice sets, but the theorem still holds in our more general case. 158 Representing and Aggregating Conflicting Beliefs 3.1 Belief Revision Representation of Conditional Beliefs Much of the belief revision field has built on the seminal work by Alchourr'on, G"ardenfors, and Makinson (Alchourr'on et al., 1985; G"ardenfors, 1988) refered to as the AGM theory. This work sought to formalize an "Occam's razor"-like principle of minimal change: the set of beliefs resulting from a revision should be one produced by modifying the original beliefs minimally to accomodate the new information. To capture this principle precisely, they proposed the famous AGM postulates which impose restrictions on belief change operators. Subsequent model-theoretic work (Grove, 1988; Katsuno & Mendelzon, 1991; MaynardReid II & Shoham, 2001) showed that accepting these postulates amounts to assuming that an individual's belief state is represented by a total preorder _ over W; revision of the individual's beliefs by a sentence p 2 L then consists of computing ch(|p|, _). Kraus, Lehmann, and Magidor (1990) and Lehmann and Magidor (1992) developed a similar central role for ordered structures in the semantics of nonmonotonic logics, and G"ardenfors and Makinson (1994) established the relation between the two topics. Semantically, _ represents the weak relative likelihood of possible worlds: x _ y means possible world x is considered to be at least as likely as possible world y.4 If x _ y and y _ x, then x and y are considered equally likely. We can also interpret _ sententially using the famous Ramsey Test (Ramsey, 1931): it encodes a set of conditional beliefs, i.e., not only what is believed now (called the belief set), but all counterfactual beliefs as well (what would be believed if other conditions were the case). According to this criteria, the conditional belief "if p then q" holds if p and q are sentences in L and q is satisfied by all the worlds in ch(|p|, _); we write Bel(p?q). If neither the belief p?q nor the belief p?~q hold in the belief state, it is said to be agnostic with respect to p?q, written Agn(p?q). The belief set induced by the belief state consists of all those sentences q such that Bel(true?q) holds. 3.2 Social Choice Implications Our first inclination, then, would be to use total preorders to represent collective beliefs since they work so well for individuals' beliefs. Unfortunately, such an approach is inherently problematic as was discovered early on in the social choice community. That community's interest lies in representing collective preferences rather than collective beliefs; however, the results are equally relevant since the classical representation of an individual's preferences is also a total preorder. Instead of relative likelihood, relations represent relative preference; instead of equal likelihood, indifference. Arrow's (1963) celebrated Impossibility Theorem showed that no aggregation operator over total preorders exists satisfying the following small set of desirable properties: Definition 5 Let f be an aggregation operator over the relations _1, . . . , _n of n individuals, respectively, over a finite set of alternatives Omega , and let _ = f (_1, . . . , _n). * Restricted Range: The range of f is the set of total preorders over Omega . * Unrestricted Domain: The domain of f is the set of n-tuples of total preorders over Omega . 4. The direction of the relation symbol is unintuitive, but standard practice in the belief revision community. 159 Maynard-Zhang & Lehmann * Pareto Principle: If x OEi y for all i, then x OE y.5 * Independence of Irrelevant Alternatives (IIA): Suppose _0 = f (_01, . . . , _0n). If, for x, y 2 Omega , x _i y iff x _0i y for all i, then x _ y iff x _0 y. * Non-Dictatorship: There is no individual i such that, for every tuple in the domain of f and every x, y 2 Omega , x OEi y implies x OE y. Proposition 3 (Arrow, 1963) There is no aggregation operator that satisfies restricted range, unrestricted domain, Pareto principle, independendence of irrelevant alternatives, and nondictatorship. This impossibility theorem led researchers to look for weakenings to Arrow's framework that would circumvent the result. One was to weaken the restricted range condition, requiring that the result of an aggregation only satisfy totality and quasi-transitivity rather than the full transitivity of a total preorder. This weakening was sufficient to guarantee the existence of an aggregation function satisfying the other conditions, while still producing relations that defined choice functions (Sen, 1986). However, this solution was not without its own problems. First, and perhaps most obviously, the domain and the range of the aggregation operator are different, violating what is known in the belief revision literature as the principle of categorical matching (cf. Gardenfors and Rott's 1995 survey). This problem is closely related to the second which is that total, quasi-transitive relations have unsatisfactory semantics. If _ is total and quasi-transitive but not a total preorder, its indifference relation is not transitive: Proposition 4 Let _ be a relation over a finite set Omega and let , be its symmetric restriction. If _ is total and quasi-transitive but not transitive, then , is not transitive. There has been much discussion as to whether or not indifference should be transitive. In many cases one feels indifference should be transitive; if Deb is indifferent between plums and mangoes and also indifferent between mangoes and peaches, we would be greatly surprised were she to profess a strong preference for plums over peaches.6 Thus, it seems that total quasi-transitive relations that are not total preorders cannot be understood easily as preference or indifference. Since the existence of a choice function is generally sufficient for classical social choice problems, these issues were at least ignorable. However, in iterated aggregation, the result of the aggregation must not only be usable for making decisions, but must be interpretable as a new preference relation that may be involved in later aggregations and, consequently, must maintain clean semantics. Third, the totality assumption is excessively restrictive for representing aggregate preferences. In general, a binary relation _ can express four possible relationships between a pair of alternatives a and b: a _ b and b 6_ a, b _ a and a 6_ b, a _ b and b _ a, and a 6_ b and b 6_ a. Totality reduces this set to the first three which, under the interpretation of 5. Technically, this is known as the weak Pareto principle. The strong Pareto principle states that x OE y if there exists i such that x OEi y and x _i y for all i. Obviously, the strong version implies the weak version, so Arrow's theorem applies to it as well. 6. However, see Luce's (1956) work on semiorders for some of the opposing arguments in the transitivity of indifference debate. 160 Representing and Aggregating Conflicting Beliefs relations as representing weak preference, correspond to the two strict orderings of a and b, and indifference. However, consider the situation where a couple is trying to choose between an Italian and an Indian restaurant, but one strictly prefers Italian food to Indian food, whereas the second strictly prefers Indian to Italian. The couple's opinions are in conflict, a situation that does not fit into any of the three categories. Thus, the totality assumption is essentially an assumption that conflicts do not exist. This, one may argue, is appropriate if we want to represent preferences of one agent (but see Kahneman and Tversky's (1979) persuasive arguments that individuals are often ambivalent). However, the assumption is inappropriate if we want to represent aggregate preferences since individuals will almost certainly have differences of opinion. 3.3 Generalized Belief States Because belief aggregation is formally similar to preference aggregation, it is also susceptible to the problems faced by the social choice community. We take the view that much of the difficulty encountered in previous attempts to define acceptable aggregation policies has been the lack of explicit representations of conflicts among the individuals. We generalize the total preorder representation so as to capture information about conflicts. This generalization opens the way for semantically clear aggregation policies, with the added benefit of focusing attention on the culprit sets of worlds. 3.3.1 Modular, Transitive States We take strict likelihood as primitive. Since strict likelihood is not necessarily total, it is possible to represent agnosticism and conflicting opinions in the same structure. This choice deviates from that of most authors, but is similar to that of Kreps (1990, p. 19) who is interested in representing both indifference and incomparability. Unlike Kreps, rather than use an asymmetric relation to represent strict likelihood (e.g., the asymmetric restriction of a weak likelihood relation), we impose the less restrictive condition of modularity. We formally define generalized belief states: Definition 6 A generalized belief state OE is a modular, transitive relation over W. The set of possible generalized belief states over W is denoted B. We interpret a OE b to mean "there is reason to consider a as strictly more likely than b." We represent equal likelihood, which we also refer to as "agnosticism," with the relationship, defined such that x , y if and only if x 6OE y and y 6OE x. We define the conflict relation corresponding to OE, denoted ./, so that x ./ y iff x OE y and y OE x. It describes situations where there are reasons to consider either of a pair of worlds as strictly more likely than the other. In fact, one can easily check that ./ precisely represents conflicts in a belief state in the sense of Definition 4. For convenience, we will refer to generalized belief states simply as belief states except when to do so would cause confusion. 3.3.2 Discussion Let us consider why our choice of representation is justified. First, we agree with the social choice community that strict likelihood should be transitive. 161 Maynard-Zhang & Lehmann As we discussed above, there is often no compelling reason why agnosticism/indifference should not be transitive; we also adopt this view. However, transitivity of strict likelihood by itself does not guarantee transitivity of agnosticism. A simple example is the following:W = {a, b, c} and OE= {(a, c)}, so that ,= {(a, b), (b, c)}. However, if we buy that strict likelihood should be transitive, then agnosticism is transitive identically when strict likelihood is also modular: Proposition 5 Suppose a relation OE is transitive and , is the corresponding agnosticism relation. Then , is transitive iff OE is modular. In summary, transitivity and modularity are necessary if strict likelihood and agnosticism are both required to be transitive. We should point out that conflicts are also transitive in our framework. At first glance, this may appear undesirable: it is entirely possible for a group to disagree on the relative likelihood of worlds a and b, and b and c, yet agree that a is more likely than c. However, we note that this transitivity follows from the cycle-based definition of conflicts (Definition 4), not from our belief state representation. It highlights the fact that we are not only concerned with conflicts that arise from simple disagreements over pairs of alternatives, but those that can be inferred from a series of inconsistent opinions as well. Now, to argue that modular, transitive relations are sufficient to capture relative likelihood, agnosticism, and conflicts among a group of information sources, we first point out that adding irreflexivity would give us the class of relations that are asymmetric restrictions of total preorders, i.e., conflict-free. Let T be the set of total preorders over W, T<, the set of their asymmetric restrictions. Proposition 6 T< ae B and is the set of irreflexive relations in B. Secondly, the following representation theorem shows that each belief state partitions the possible worlds into sets of worlds either all equally likely or all potentially involved in a conflict, and totally orders these sets; worlds in distinct sets have the same relation to each other as do the sets. Proposition 7 OE2 B iff there is a partition W = hW0, . . . , Wni of W such that: 1. For every x 2 Wi and y 2 Wj, i 6= j implies i < j iff x OE y. 2. Every Wi is either fully connected (w OE w0 for all w, w0 2 Wi) or fully disconnected (w 6OE w0 for all w, w0 2 Wi). Figure 1 shows three examples of belief states: one which is a total preorder, one which is the asymmetric restrictions of a total preorder, and one which is neither. (Each circle represents all the worlds in W which satisfy the sentence inside. An arc between circles indicates that w OE w0 for every w in the head circle and w0 in the tail circle; no arc indicates that w 6OE w0 for each of these pairs. In particular, the set of worlds represented by a circle is fully connected if there is an arc from the circle to itself, fully disconnected otherwise.) Thus, generalized belief states are not a big change from the asymmetric restrictions of total preorders. They merely generalize these by weakening the assumption that sets of worlds not strictly ordered are equally likely, allowing for the possibility of conflicts. Now we can distinguish between agnostic and conflicting conditional beliefs. A belief state OE is 162 Representing and Aggregating Conflicting Beliefs (c) P P P P P (b)(a) P Figure 1: Three examples of generalized belief states: (a) a total preorder, (b) the asymmetric restriction of a total preorder, (c) neither. agnostic about conditional belief p?q (i.e., Agn(p?q)) if the choice set of worlds satisfying p contains both worlds which satisfy q and ~q and is fully disconnected. It is in conflict about this belief, written Con(p?q), if the choice set is fully connected. Finally, we compare the representational power of our definitions to those discussed in the previous section. First, as a companion result to Proposition 6, it is obvious that B subsumes the class of total preorders T and, in fact, T is the set of reflexive relations in B. Proposition 8 T ae B and is the set of reflexive relations in B. Secondly, B neither subsumes nor is subsumed by the set of total, quasi-transitive relations, and the intersection of the two classes is T . Let Q be the set of total, quasi-transitive relations over W, and Q<, the set of their asymmetric restrictions. Proposition 9 1. Q " B = T . 2. B 6` Q. 3. Q 6` B if W has at least three elements. 4. Q ae B if W has one or two elements. Because modular, transitive relations represent strict preferences, it is probably fairer to compare them to the class of asymmetric restrictions of total, quasi-transitive relations. Again, neither class subsumes the other, but this time the intersection is T<: Proposition 10 1. Q< " B = T<. 2. B 6` Q<. 3. Q< 6` B if W has at least three elements. 4. Q< ae B if W has one or two elements. Note that generalized belief states as described are extremely rich and would require optimization in practice to avoid high maintenance cost. Although this issue is somewhat outside the scope of this paper, we do address (in the respective sections) ways to minimize the further explosion of this complexity when the complications of fusion and voting are introduced. In the next section, we define a natural aggregation policy based on this new representation that admits clear semantics and obeys appropriately modified versions of Arrow's conditions. 163 Maynard-Zhang & Lehmann 4. Single-Agent Belief State Construction Suppose an agent is informed by a set of sources, each with its individual belief state. Suppose, further, that the agent has ranked the sources by level of credibility. We propose an operator for constructing the agent's belief state by aggregating the belief states of the sources while accounting for the credibility ranking of the sources. Example 1 We will use a running example from our space robot domain to help provide intuition for our definitions. The robot sends to earth a stream of telemetry data gathered by the spacecraft, as long as it receives positive feedback that the data is being received. At some point it loses contact with the automatic feedback system, so it sends a request for information to an agent on earth to find out if the failure was caused by a failure of the feedback system or by an overload of the data retrieval system. In the former case, it would continue to send data, in the latter, desist. As it so happens, there has been no overload, but the computer running the feedback system has hung. The agent consults the following three experts, aggregates their beliefs, and sends the results back to the robot: 1. sp, the computer programmer that developed the feedback program, believes nothing could ever go wrong with her code, so there must have been an overload problem. However, she admits that if her program had crashed, the problem could ripple through to cause an overload. 2. sm, the manager for the telemetry division, unfortunately has out-dated information that the feedback system is working. She was also told by the engineer who sold her the system that overloading could never happen. She has no idea what would happen if there was an overload or the feedback system crashed. 3. st, the technician working on the feedback system, knows that the feedback system crashed, but doesn't know whether there was a data-overload. Not being familiar with the retrieval system, she is also unable to speculate whether the data retrieval system would have overloaded if the feedback system had not failed. Let F and D be propositional variables representing that the feedback and data retrieval systems, respectively, are okay. The belief states for the three sources are shown in Figure 2. F FD FD FD FD DF FD F s ssp m t Figure 2: The belief states of sp, sm, and st in Example 1. 164 Representing and Aggregating Conflicting Beliefs 4.1 Sources Let us begin the formal development by defining sources and their belief states: Definition 7 S is a finite set of sources. With each source s 2 S is associated a belief state= rank(s0); we say s is as credible as s0. The restriction of w to S ` S will be denoted wS. We use A and j to denote the asymmetric and symmetric restrictions of w, respectively.7 The finiteness of S (R) ensures that a maximal source (rank) always exists, which is necessary for some of our results. Weaker assumptions are possible, but at the price of unnecessarily complicating the discussion. Also observe that R can be any arbitrary totally ordered set. Thus, not only does it allow for numeric ranking systems (such as the integers), but non-numeric systems as well (e.g., military ranks). Furthermore, this generality allows our proposal to easily accommodate applications where new ranks need to be dynamically added and it is inconvenient or impossible to change the rank labels of existing sources (e.g., a large workers' union where members are ranked by relative level and quality of experience). We are now ready to consider the source aggregation problem. In the following, assume an agent is informed by a set of sources S ` S. We look at two special cases--aggregation of equally ranked and strictly ranked sources--before considering the general case. 4.2 Aggregating Equally Ranked Sources Suppose all the sources have the same rank so that wS is fully connected. Intuitively, we want to take all offered opinions seriously, so we take the union of the relations: Definition 11 If S ` S, then Un(S) is the relation Ss2S = and w are read in the intuitive way, that is, "greater" corresponds to "better." 165 Maynard-Zhang & Lehmann Thus, we know from Proposition 1 that we need only take the transitive closure of Un(S) to get a belief state: Definition 12 If S ` S, then AGRUn(S) is the relation Un(S)+. Proposition 12 If S ` S, then AGRUn(S) 2 B. Intuitively, we are simply inferring opinions implied by the conflicts introduced by the aggregation. We will show this formally when we consider the more general aggregation operator below. Not surprisingly, by taking all opinions of all sources seriously, we may generate many conflicts, manifested as fully connected subsets of W. Example 2 Suppose all three sources in the space robot scenario of Example 1 are considered equally credible, then the aggregate belief state will be the fully connected relation indicating that there are conflicts over every belief. 4.3 Aggregating Strictly Ranked Sources Next, consider the case where the sources are strictly ranked, i.e., wS is a total order. We define a lexicographic operator such that lower ranked sources refine the belief states of higher ranked sources. That is, in determining the ordering of a pair of worlds, the opinions of higher ranked sources generally override those of lower ranked sources, and lower ranked sources are consulted when higher ranked sources are agnostic: Definition 13 If S ` S, then AGRRf(S) is the relationn (x, y) : 9s 2 S. x ~~r ) x ssr0 yDelta Psi . AGR* indeed defines a legitimate belief state: Proposition 15 If S ` S, then AGR*(S) 2 B. Unfortunately, a problem with this "divide-and-conquer" approach is it assumes the result of aggregation is independent of potential interactions between the individual sources of different ranks. Consequently, opinions that will eventually get overridden may still have an indirect effect on the final aggregation result by introducing superfluous opinions during the intermediate equal-rank aggregation step, as the following example shows: Example 4 Let W = {a, b, c}. Suppose S ` S such that S = {s0, s1, s2} with belief states~~r ) x ,Ajr0 yjo over W, and 2. l :OE! R such that l((x, y)) = max({r : x OEAir y, Ai 2 A}). Proposition 22 Let A, PA, S, and wS be as in Definition 23. Then Phi ped(PA) is the pedigreed belief state of Phi (A). From the perspective of the induced belief states, we are essentially discarding unlabeled opinions (i.e., those derived by the closure operation) before fusion. Intuitively, we are learning new information so we may need to retract some of our inferred opinions. After fusion, we re-apply closure to complete the new belief state. Interestingly, in the special case where the sources are strictly-ranked, the closure is unnecessary: Proposition 23 If A, PA, and S are as in Definition 23, wS is a total order, andPhi ped(PA) = (OE, l), then OE+=OE. Let us return once more to the space robot scenario considered in Example 1 to illustrate pedigreed fusion. Example 9 Suppose the arrogant programmer is not part of the telemetry team, but instead works for a company on the other side of the country. Then the robot has to request information from two separate agents, one to query the manager and technician and one to query the programmer. Assume that the agents and the robot all rank the sources the same, assigning the technician rank 2 and the other two agents rank 1, which induces the same credibility ordering used in Example 5. The agents' pedigreed belief states and the result of their fusion are shown in Figure 5. The first agent does not provide any information about overloading and the second agent provides incorrect information. However, we see that after fusing the two, the robot has a belief state that is identical to what it computed in Example 5 when there was only one agent informed by all three sources (we've only separated the top set of worlds so as to show the labeling). Consequently, it now knows the correct state of the system. And, satisfyingly, the final result does not depend on the order in which the robot receives the agents' reports. The savings obtained in required storage space by this scheme can be substantial. Suppose S is the set of an agent's informant sources, n = kWk, and m = kSk. Explicitly storing S (along with the rank of each source) requires O(n2m) amount of space; this worst case bound is reached when all the sources' belief states are fully connected relations. On the 172 Representing and Aggregating Conflicting Beliefs ( , ) FD FD A2 FD 1 1 1 1 1 1 FD FD FD F FD 1A A21A FD 1 1 2 1 FD 2 2 1 2 2 2 FD Figure 5: The pedigreed belief states of agent A1 informed by sm and st and of agent A2 informed by sp, and the result of their fusion in Example 9. other hand, storing a pedigreed belief state only requires O(n2) space.10 Moreover, not only does the enriched representation allow us to conserve space, it also provides for potential savings in the efficiency of computing fusion since, for each pair of worlds, we only need to consider the opinions of the agents rather than those of all the sources in the combined set of informants. Incidentally, if we had used the strawman AGR* as the basis for our general aggregation, simply storing the rank of the maximum supporting sources would not give us sufficient information to compute the induced belief state after fusion. To demonstrate this, we give an example where two pairs of sources induce the same annotated agent belief states, yet yield different belief states after fusion: Example 10 Let W, S, and w be as in Example 4. Suppose agents A1, A2, A01, and A02 are informed by sets of sources S1, S2, S01, and S02, respectively, where S1 = S2 = {s2}, S01 = {s0, s2}, and S02 = {s1, s2}. AGR* dictates that the pedigreed belief states of all four agents equal 0 and countS(x, y)/kSk >= p}. This definition falls under the class of voting systems Black (1958) calls absolute majority systems. It is motivated by the observation that relative support is many times less relevant than strength of support. The support for the two possible rankings of two worlds may be so low that neither can justifiably be considered part of the aggregate belief state. Similarly, the support for both alternative rankings may be so high that it may be more reasonable to introduce both and create a conflict rather than choose one with slightly higher support. Our strategy will not be appropriate for all applications, of course, but there are many instances when it is most appropriate. Also, our method satisfies a generalization of the Condorcet criterion, a widely accepted criteria of "good" voting systems that requires the Condorcet winner, if it exists, be the most likely world in the aggregate belief state. Our method never produces a strict ranking of two worlds opposite to that of Condorcet's method, although there will be cases where Condorcet's method ranks one world strictly more likely than another and our method produces agnosticism or a conflict. As a result, the Condorcet 174 Representing and Aggregating Conflicting Beliefs winner will always be among the most likely worlds. At any rate, our aggregation results do not depend significantly on the choice of voting strategy; one could easily replace it with a different strategy if desired. That said, we make a few observations about our voting functions. First, the voting function definition requires that we accept an opinion if at least p proportion of the sources support it. However, we often want to specify that opinions only be accepted if strictly more than some cutoff proportion of sources support it. For example, the best-known voting function is the majority function where we only accept an opinion if it gets more than 50% of the vote. We can easily specify majority vote with the function vt0.5+ffl(S) where 0 < ffl < 0.5/kSk (e.g., ffl = 0.25/kSk) so that tied opinions are rejected. In general, to only accept opinions garnering more than p proportion of the vote (for 0 <= p < 1), it suffices to use the function vtp+ffl(S) where 0 < ffl < 1 - pkSk + bpkSkckSk e.g., ffl = (1 - pkSk + bpkSkc)/(2kSk).11 Second, it is immediately obvious that the aggregate relation may contain conflicts if p <= 0.5, even if the original source belief states are conflict-free. In fact, it is possible to get conflicts in the aggregate of conflict-free belief states even for larger p, as the following famous example demonstrates: Example 11 Let W = {a, b, c} and S be such that 1/3 of the sources have belief state{ (a, b), (b, c), (a, c)}, 1/3 have {(b, c), (c, a), (b, a)}, and 1/3 have {(c, a), (a, b), (c, b)}. Then vtp(S) = {(a, b), (b, c), (c, a)}, a cycle, for 1/3 < p <= 2/3. This is known as the Condorcet paradox (cf. Brams and Fishburn's (2002) voting survey). Many solutions have been proposed for resolving such conflicts - using Borda counts or instant runoff voting (aka single transferable vote) (cf. Center for Voting and Democracy, 2002) are two popular examples. As before, we do not attempt to resolve the conflicts but, instead, make them explicit in a way that supports flexibility in the choice of resolution methodology and allows for semantically well-behaved iteration of aggregation. Third, the end-point members of the family of voting functions have special significance. The voting function for 0 is equivalent to the union operator we saw earlier that takes all opinions seriously, i.e., is indiscriminate: Proposition 24 If S ` S, then vt0(S) = Un(S). At the other extreme, we have the voting function for 1. In this case, it is equivalent to taking the intersection of the sources' belief states, i.e., only accepting unanimous opinions: Proposition 25 If S ` S, then vt1(S) = Ts2S = 3, then for every p 2 (0, 1), there exists S such that vtp(S) is neither modular nor transitive. Part of the problem is that voting may introduce conflicts which may imply other conflicts. As before, we need to take the transitive closure to infer these implied conflicts. In the Condorcet paradox example, this produces the fully connected belief state as we would hope. Unfortunately, closing under transitivity does not necessarily restore modularity as well, as the following example demonstrates: Example 12 Let W = {a, b, c} and S be such that 1/3 of the sources have belief state{ (a, b), (b, c), (a, c)}, 1/3 have {(b, c), (c, a), (b, a)}, and 1/3 have {(b, a), (b, c)}. Then, for p > 2/3, vtp(S) = vtp(S)+ = {(b, c)} which is not modular. We solve this problem by defining a natural modular closure operation which converts a transitive relation into a belief state. We will then define a modular-transitive closure operation which will take the result of an arbitrary voting function and transform it into a belief state using a transitive closure followed by a modular closure. 6.2 Modular-Transitive Closure We start by defining a helper function which returns the level of a world in a relation, i.e., the length of the longest path (along strict edges) from a world to a member of the choice set of W. For convenience, throughout this modular-transitive closure subsection we will use _ to denote an arbitrary relation, OE and ./ to denote its asymmetric and symmetric restrictions, respectively. Definition 25 The level of x 2 W in a transitive relation _ over W, written lev_(x), is lev_(x) = ( 0 if x 2 ch(W, _)1 + max y2W ({lev_(y) : y OE x}) otherwise. (Recall that ch is the choice set function defined in Definition 2.) The following simple properties relating _ and lev_ are immediate: 176 Representing and Aggregating Conflicting Beliefs Proposition 28 Suppose _ is a transitive relation over W and x, y 2 W. 1. If x OE y, then lev_(x) < lev_(y). 2. If x ./ y, then lev_(x) = lev_(y). 3. If lev_(x) < lev_(y), then 9z. lev_(z) = lev_(x) ^ z OE y. 4. If lev_(x) = lev_(y), then x _ y iff y _ x. We now define the modular closure of a relation to be the relation that results from fully connecting all equi-level alternatives unless they are fully disconnected: Definition 26 The modular closure MC(_) of a transitive relation _ over W is the relation such that (x, y) 2 MC(_) iff 1. lev_(x) < lev_(y) or 2. lev_(x) = lev_(y) and 9x0, y0. lev_(x0) = lev_(y0) = lev_(x) ^ x0 ./ y0. Intuitively, as long as we have reason to doubt that some pair in a level are interchangeable, we doubt all the pairs at that level, but only then. Note that the definition of MC is similar to one of the equivalent constructions of the rational closure Lehmann and Magidor (1992) describe. We see that MC indeed makes any transitive relation modular while preserving transitivity: Proposition 29 If _ is a transitive relation over W, then MC(_) 2 B. MC is an additive process that changes a relation minimally to achieve modularity while preserving transitivity and the levels of the worlds: Proposition 30 Suppose _ is a transitive relation over W and _*= MC(_). 1. _`_* and OE`OE*. 2. If _ is modular, then _*=_. 3. lev_*(x) = lev_(x) for all x 2 W. 4. If _02 B such that _`_0 and lev_0(x) = lev_(x) for all x 2 W, then _*`_0. We now define the modular, transitive closure of an arbitrary relation _ as MC applied to the transitive closure of _, and show that the result is a belief state: Definition 27 The modular, transitive closure MT(_) of a relation _ over W is the relation MC (_+). Proposition 31 If _ is a relation over W, then MT(_) 2 B. MT is also a minimally additive operator: Proposition 32 Suppose _ is a relation over W and _*= MT(_). 1. _`_*. 2. If _ is transitive, then _*= MC(_). 3. If _ is modular, then _*=_+. 4. If _ is modular and transitive, then _*=_. 5. If _ has no conflicts, then neither does _*. 177 Maynard-Zhang & Lehmann 6.3 The Aggregation Family We are now fully equipped to solve the problem of incorporating voting into aggregation. First, consider the special case where all sources have the same rank. Our aggregation operators will construct an aggregate belief state by first applying voting, then closing under MT: Definition 28 If S ` S and p 2 [0, 1], then AGREqp(S) = MT (vtp(S)). Proposition 33 If S ` S and p 2 [0, 1], then AGREqp(S) 2 B. We can now easily generalize this definition to accommodate a ranking on the sources. We accept an opinion if enough individuals at the highest rank with an opinion support it, then close under MT: Definition 29 If S ` S and p 2 [0, 1], then AGRRfp(S) is the relationn (x, y) : 9s 2 S. x ~~0 and ksup(x, y)k/krtab(l(x, y))k >= p}) Observe that, unlike with pedigreed belief states, support pedigreed belief states label all possible opinions, not just those appearing in the agent's induced belief state, i.e., whose support falls below the threshhold. The reason is another agent may come along later with enough new votes to cross the threshold, in which case the votes from the earlier sources become relevant. Similarly, support pedigreed belief states maintain rank information even for ranks not appearing as labels. No source of a particular rank may currently support any opinion, but another agent may later bring sources of that rank supporting an opinion hitherto unsupported by any source of equal or higher rank. The correct computation of the proportion of support for this opinion must take into account the earlier sources. Before we address fusion, let us consider the space required to store a support pedigreed belief state (l, sup, rtab). l requires O(n2) space, rtab requires Theta (m) space, and, if rmax denotes the number of sources of a rank having the most sources with that rank, sup requires O(n2rmax) space, for a total of O(n2rmax + m) space.12 Thus, in a best-case scenario where, for example, sources are strictly ranked, a support pedigreed belief state only requires O(n2 + m) space since each opinion has at most one supporter. However, in 12. As before, we assume representing ranks requires constant space. We assume that we can represent each source label with constant space as well. 179 Maynard-Zhang & Lehmann the worst-case scenario where, for example, sources are all equally ranked so that rmax = m, we will still need O(n2m) space. Now, computing the support pedigreed belief state resulting from fusion is straightforward. For each opinion, we set l to be the highest l value for that opinion among the agents and set sup to be the union of sup sets for that opinion of all agents with that l value. And for each rank represented in some agent's rank table, we set rtab to be the union of the rtab sets of all agents for whom it is defined. Definition 32 Let S and A be as in Definition 21, wS, a total preorder, and PA, the set of support pedigreed belief states of the agents in A. The support pedigreed fusion of PA, written Phi sup(PA), is (l, sup, rtab) where 1. l :OE! R such that l((x, y)) = max({l0(x, y) : (l0, sup0, rtab0) 2 PA}), 2. sup : W * W ! 2S such that sup(x, y) = [ (l0,sup0,rtab0)2PA, l0(x,y)=l(x,y) sup0(x, y), and 3. rtab : ranks(S) ! 2S such that rtab(r) = [ (l0,sup0,rtab0)2PA, r2range(rtab0) rtab0(r). Proposition 37 Let A, PA, S, and wS be as in Definition 32. Then Phi sup(PA) is the support pedigreed belief state of Phi (A). Thus, in addition to the potential savings in space gained by using support pedigreed belief states, we also potentially save in the time needed to compute fusion since, for a given opinion, we do not need to consider the opinions of lesser ranked sources. 7. Related Work Much of the work in belief aggregation has been geared towards unbiased kinds of belief pooling. Besides the work in social choice we described in Section 3.2, recent attempts from the belief revision community (e.g. Borgida & Imielinski, 1984; Baral, Kraus, Minker, & Subrahmanian, 1992; Liberatore & Schaerf, 1995; Makinson, 1997; Revesz, 1997; Konieczny & P'erez, 1998; Meyer, 2001; Benferhat, Dubois, Kaci, & Prade, 2002) have sought to modify the AGM theory to capture "fair" revisions, that is, revisions where the revisee and reviser's beliefs are treated equally seriously. Like our proposal, Benferhat et al. and Meyer accommodate iterative merging. Benferhat et al.'s proposal is also distinct in that they approach the problem from a possibilistic logic point of view. Besides the restriction to equally-ranked sources, these fairness-based proposals differ from ours in that they are generally syntactic in nature in the sense that sentences are prioritized rather than possible worlds. Meyer's proposal is an exception; his belief states are epistemic states, structures in the style of Spohn's (1988) ordinal conditional functions (aka ^-rankings). In fact, Meyer, Ghose, and 180 Representing and Aggregating Conflicting Beliefs Chopra (2001) have shown that a number of simple aggregation operators on epistemic belief states also satisfy Arrow's postulates when appropriately modified for this context (unrestricted domain, restricted range, and IIA in particular need modification). Unfortunately, epistemic states are enriched total preorders and, thus, suffer from the problems we described earlier, i.e., the inability to explicitly handle conflicts. Cantwell's (1998) work is also syntactic in nature, but does allow for sources of differing credibility. Cantwell addresses a complementary problem to our own: deciding what information to reject given the subset of informing sources rejecting the information. He assumes a generalization of our credibility ordering, a partial preorder over sets of sources. He explores ways of inducing a partial preorder over sentences based on this ordering, then uses this ordering to determine a subset (although not all) of the sentences to reject. Another difference from our work is that he only considers the non-counterfactual beliefs of sources. We are not, of course, the first to consider using the lexicographic ordering for aggregation purposes. Lexicographic operators have long been studied in the fields of management and social science; Fishburn (1974) gives a good survey of much of that work. More recently, researchers in artificial intelligence have taken an interest in these operators; examples include Grosof (1991), Maynard-Reid II and Shoham (2001) and Andr'eka, Ryan, and Schobbens (2002). Grosof uses lexicographic aggregation of preorders as a means of tackling the problem of default reasoning in the presence of conflicting defaults. Besides the more general preorders being aggregated, another interesting difference from our work is that although Grosof does not allow for sources of equal rank, he does allow for sources of incomparable rank, i.e., the ranking on sources is a strict partial order. Thus, in the extreme case where the ordering is completely disconnected, the operator reduces to our Un operator (and, thus, does not necessarily preserve transitivity). Andr'eka et al., on the other hand, frame their work in the context of preference aggregation. They go one step further than Grosof and allow input relations to be arbitrary. They prove that the lexicographic operator is the only one that satisfies a variation on Arrow's properties - unanimity, IIA, preservation of transitivity, and a weaker version of non-dictatorship. (We should point out that from the perspective of Arrow's original framework, the relation with the highest priority is always a dictator.) They describe a collection of other properties besides transitivity preserved by the operator. However, as in our work, they do not preserve totality. Our work derives much of its inspiration from Maynard-Reid II and Shoham's work. They restrict their attention to total preorders, but this does not create problems because they assume sources to be totally ordered. They focus, instead, on the strong connection between belief aggregation and iterated belief revision. They show that Phi can be used as an iterated belief operator in an AGM-based setting, then compare its properties as such against those of a representative sampling of well-known iterated belief operator proposals - Boutilier's (1996) natural revision, Darwiche and Pearl's (1997) operators, Spohn's (1988) ordinal conditional function revision, Lehmann's (1995) widening rank model revision, and Williams's (1994) conditionalization and adjustment operators. They show that Phi is the only operator among them that is semantically well-behaved: the results of all the other operators depend on the order of iteration. 181 Maynard-Zhang & Lehmann Finally, to our knowledge, none of these related approaches outside of social choice have yet been extended to incorporate voting. 8. Conclusion We have described a semantically clean representation - the class of modular, transitive relations - for collective qualitative beliefs which allows us to represent conflicting opinions without sacrificing the ability to make decisions. We have proposed an intuitive operator which takes advantage of this representation so that an agent can combine the belief states of a set of informant sources totally preordered by credibility. We showed that this operator circumvents Arrow's Impossibility result in a satisfactory manner. We also described a mechanism for fusing the belief states of different agents that iterates well and extended the framework to incorporate voting. We have assumed that all agents share the credibility ranking on sources. In general, these rankings can vary among agents, and even change over time. Furthermore, an agent's ranking function can depend on the context; different sources may have different areas of expertise. Exploring the behavior of fusion in these more general settings is an obvious next step. Note that although we have described operators to incorporate voting, under no condition will any of these ever side with lower rank sources when they conflict with higher rank sources, no matter how many of these disagreeing lower rank sources there are. An aggregation scheme that behaves differently would have to be built on fundamentally different assumptions than our framework. Another problem which deserves further study is developing a fuller understanding of the properties of the Bel, Agn, and Con operators and how they interrelate. Acknowledgments We want to thank Yoav Shoham and the anonymous referees of this paper for their insightful and comprehensive feedback. A preliminary version of this paper appears in the Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning (KR2000) (the first author's last name was Maynard-Reid II at that time). This work was partially supported by a National Physical Science Consortium Fellowship and the Jean et H'el`ene Alfassa Fund for Research in Artificial Intelligence. Appendix A. Proofs Proposition 1 1. The transitive closure of a modular relation is modular. 2. Every transitive relation is quasi-transitive. 3. (Sen, 1986) Every quasi-transitive relation is acyclic. Proof: 1. Suppose a relation <= over finite set Omega is modular, and <=+ is the transitive closure of <=. Suppose x, y, z 2 Omega and x <=+ y. Then there exist w0, . . . , wn such that 182 Representing and Aggregating Conflicting Beliefs x = w0 <= * * * <= wn = y. Since <= is modular and w0 <= w1, either w0 <= z or z <= w1. In the former case, x = w0 <= z, so x <=+ z. In the latter case, z <= w1 <= * * * wn = y, so z <=+ y. 2. Suppose Omega is a finite set, x, y, z 2 Omega , <= is a transitive relation over Omega , and < is its asymmetric restriction. Suppose x < y and y < z. Then x <= y, y 6<= x, y <= z, and z 6<= y. x <= y and y <= z imply x <= z, and y <= z and y 6<= x imply z 6<= x, both by transitivity. So x < z. 2 Proposition 2 (Sen, 1986) Given a relation <= over a finite set Omega , the choice set operation ch defines a choice function iff <= is acyclic. Proof: See Sen's (1986) proof. 2 Proposition 3 (Arrow, 1963) There is no aggregation operator that satisfies restricted range, unrestricted domain, (weak) Pareto principle, independendence of irrelevant alternatives, and nondictatorship. Proof: See Arrow's (1963) proof. 2 Proposition 4 Let _ be a relation over a finite set Omega and let , be its symmetric restriction. If _ is total and quasi-transitive but not transitive, then , is not transitive. Proof: Let _ be a total, quasi-transitive, non-transitive relation. Suppose x _ y and y _ z but x 6_ z. By totality, z _ x, so z OE x. If x OE y, then z OE y by quasi-transitivity, a contradiction. Thus, x , y. Similarly, if y OE z, then y OE x, a contradiction, so y , z. But z OE x, so x 6, z. Therefore, , is not transitive. 2 Proposition 5 Suppose a relation OE is transitive and , is the corresponding agnosticism relation. Then , is transitive iff OE is modular. Proof: Suppose , is transitive and suppose x OE z, x, y, z 2 W. We prove by contradiction: Suppose x 6OE y and y 6OE z. By transitivity, z 6OE y and y 6OE x, so x , y and y , z. By assumption, x , z, so x 6OE z, a contradiction. Suppose, instead, OE is modular and suppose x , y and y , z, x, y, z 2 W. Then x 6OE y, y 6OE x, y 6OE z, and z 6OE y. By modularity, x 6OE z and z 6OE x, so x , z. 2 Proposition 6 T< ae B and is the set of irreflexive relations in B. Proof: Let x, y, z 2 W. We first show that T< ae B. Let OE2 T<. Then there exists_2 T such that OE is the asymmetric restriction of _. By definition, _ is transitive, so by Proposition 1, so is OE. Suppose x OE y. Then x _ y and y 6_ x. Since _ is total, x _ z or z _ x. Suppose x _ z. If y _ z, then z 6_ x (otherwise y _ x by transitivity, a contradiction), so x OE z. And if, on the other hand, y 6_ z, then z _ y by totality, so z OE y. Suppose, instead, z _ x. Then z _ y by transitivity and y 6_ z (otherwise y _ x by transitivity, a contradiction), so z OE y. Thus, x OE z or z OE y, so OE is modular. Now we show that OE2 B is in T< if and only if it is irreflexive. If OE2 T<, it is asymmetric, so it is irreflexive. Suppose, instead, OE is irreflexive. We define a relationship _, show that OE 183 Maynard-Zhang & Lehmann is its asymmetric restriction, and show that _ is in T . Let _ be defined as x _ y iff y 6OE x. We first show that OE is the asymmetric restriction of _. Suppose OE0 is the asymmetric restriction of _. If x OE0 y, then x _ y and y 6_ x, so x OE y. If, instead, x OE y, then y 6_ x. By totality, x _ y, so x OE0 y. We next show that _2 T . If x 6OE y then y _ x. Otherwise, x OE y. But since OE is irreflexive, y 6OE x (otherwise x OE x by transitivity), so x _ y and _ is total. Next, suppose x _ y and y _ z. Then y 6OE x and z 6OE y. By modularity, z 6OE x, so x _ z, and, thus _ is transitive. 2 Proposition 7 OE2 B iff there is a partition W = hW0, . . . , Wni of W such that: 1. For every x 2 Wi and y 2 Wj, i 6= j implies i < j iff x OE y. 2. Every Wi is either fully connected (w OE w0 for all w, w0 2 Wi) or fully disconnected (w 6OE w0 for all w, w0 2 Wi). Proof: We refer to the conditions in the proposition as conditions 1 and 2, respectively. We prove each direction of the proposition separately. (=)) Suppose OE2 B, that is, OE is a modular and transitive relation over W. We use a series of definitions and lemmas to show that a partition of W exists satisfying conditions 1 and 2. We first define an equivalence relation by which we will partition W. Two elements will be equivalent if they "look the same" from the perspective of every element of W: Definition 33 x j y iff for every z 2 W, x OE z iff y OE z and z OE x iff z OE y. Lemma 7.1 j is an equivalence relation over W. Proof: Suppose x 2 W. For every z 2 W, x OE z iff x OE z and z OE x iff z OE x, so x j x. Therefore, j is reflexive. Suppose x, y 2 W and x j y. Then for every z 2 W, x OE z iff y OE z and z OE x iff z OE y. But then for every z 2 W, y OE z iff x OE z and z OE y iff z OE x. Therefore, y j x, so j is symmetric. Suppose x, y, z 2 W, x j y, and y j z. Suppose further that w 2 W. By definition ofj , x OE w iff y OE w and w OE x iff w OE y, and y OE w iff z OE w and w OE y iff w OE z. Therefore, x OE w iff z OE w and w OE x iff w OE z. Since w is arbitrary, x j z, so j is transitive. 2 j partitions W into its equivalence classes. We use [w] to denote the equivalence class containing w, that is, the set {w0 2 W : w j w0}. Observe that two worlds in conflict always appear in the same equivalence class: Lemma 7.2 If x, y 2 W and x ./ y, then [x] = [y]. Proof: Suppose x, y 2 W and x ./ y. Since [x] is an equivalence class, it suffices to show that y 2 [x], that is, x j y. Suppose z 2 W. By transitivity, if x OE z, then y OE z; if y OE z, then x OE z; if z OE x, then z OE y; and, if z OE y then z OE x. Thus, x OE z iff y OE z and z OE x iff z OE y, and since z is arbitrary, x j y. 2 We now define a total order over these equivalence classes: Definition 34 For all x, y 2 W, [x] <= [y] iff [x] = [y] or x OE y. 184 Representing and Aggregating Conflicting Beliefs Lemma 7.3 <= is well-defined, that is, if x j x0 and y j y0, then x OE y iff x0 OE y0, for all x, x0, y, y0 2 W. Proof: Suppose x j x0 and y j y0, x, x0, y, y0 2 W. By the definition of j, for every z 2 W, x OE z iff x0 OE z. In particular, x OE y iff x0 OE y. Also by the definition of j, for every z0 2 W, z0 OE y iff z0 OE y0. In particular, x0 OE y iff x0 OE y0. Therefore, x OE y iff x0 OE y0. 2 Lemma 7.4 <= is a total order over the equivalence classes of W defined by j. Proof: Suppose x, y, z 2 W. We first show that <= is total. By definition of <=, if x OE y or y OE x, then [x] <= [y] or [y] <= [x], respectively. Suppose x 6OE y and y 6OE x, and suppose z 2 W. By modularity of OE, x OE z implies y OE z, y OE z implies x OE z, z OE x implies z OE y, and z OE y implies z OE x, so x j y. Therefore, [x] = [y], so [x] <= [y] by the definition of <=. Next, we show that <= is anti-symmetric. Suppose [x] <= [y] and [y] <= [x]. Then [x] = [y] or x OE y and y OE x. In the former case we are done, in the latter, the result follows from Lemma 7.2. Finally, we show that <= is transitive. Suppose [x] <= [y] and [y] <= [z]. Obviously, if [x] = [y] or [y] = [z], then [x] <= [z]. Suppose not. Then x OE y and y OE z, so x OE z by the transitivity of OE. Therefore, [x] <= [y] by the definition of <=. 2 We name the members of the partition W0, . . . , Wn such that Wi <= Wj iff i <= j, where n is an integer. Such a naming exists since every finite, totally ordered set is isomorphic to some finite prefix of the integers. We now check that this partition satisfies the two conditions. For the first condition, suppose x 2 Wi, y 2 Wj, and i 6= j. We want to show that i < j iff x OE y. Since i 6= j, [x] 6= [y]. Suppose i < j. Then i <= j, so [x] <= [y]. Since [x] 6= [y], x OE y by the definition of<= . Now suppose, instead, that x OE y. Then [x] <= [y] by the definition of <=, so i <= j. Since [x] 6= [y], y 6OE x by Lemma 7.2. Since [x] 6= [y] and y 6OE x, [y] 6<= [x] by the definition of <=, so j 6<= i. Thus, i < j. Finally, we show that each Wi is either fully connected or fully disconnected. Suppose x, y, z 2 Wi so that x j y j z. It suffices to show that x OE x iff y OE z. By the definition ofj , x OE x iff y OE x, and x OE x iff x OE z. Suppose x OE x. Then, y OE x and x OE z, so y OE z by transitivity of OE. Suppose now, x 6OE x. Then, y 6OE x and x 6OE z, so y 6OE z by modularity of OE. ((=) Suppose W = hW0, . . . , Wni is a partition of W and OE is a relation over W satisfying the given conditions. We want to show that OE is modular and transitive. We first give the following lemma: Lemma 7.5 Suppose W is a partition of W and OE is a relation over W satisfying condition 1. If Wi, Wj 2 W, x 2 Wi, y 2 Wj, and x OE y, then i <= j. Proof: If i = j, we're done. Suppose i 6= j. Then, since x OE y, i < j by condition 1. 2 We now show OE is modular. Suppose x 2 Wi, y 2 Wj, and x OE y. Then i <= j by Lemma 7.5. Suppose z 2 Wk. Then i <= k or k <= j by the modularity of <=. Suppose i < k or k < j. Then x OE z or z OE y by condition 1. Otherwise i = k = j, so x, y, z 2 Wi. Since x OE y, Wi is fully connected by condition 2, so x OE z (and z OE y). 185 Maynard-Zhang & Lehmann Finally, we show that OE is transitive. Suppose x 2 Wi, y 2 Wj, z 2 Wk, x OE y, and y OE z. By Lemma 7.5, i <= j and j <= k, so i <= k by the transitivity of <=. Suppose i < k. Then x OE z by condition 1. Otherwise i = k = j, so x, y, z 2 Wi. Since x OE y, Wi is fully connected by condition 2, so x OE z. 2 (END OF PROPOSITION 7 PROOF) Proposition 8 T ae B and is the set of reflexive relations in B. Proof: We first show that T ae B. Let _2 T and x, y, z 2 W. By definition, _ is transitive. Suppose x _ y. Since _ is total, x _ z or z _ x. If z _ x, then z _ y by transitivity, so _ is modular. On the other hand, the empty relation over W is modular and transitive, but not total and, consequently, not in T . Now we show that OE2 B is in T if and only if it is reflexive. If OE2 T , it is total, so it is reflexive. If, instead, OE is reflexive, then x OE x so, by modularity, x OE y or y OE x. Thus, OE is total. And, since OE2 B, it is transitive. 2 Proposition 9 1. Q " B = T . 2. B 6` Q. 3. Q 6` B if W has at least three elements. 4. Q ae B if W has one or two elements. Proof: 1. Suppose _2 Q " B. Then _ is total and transitive and, hence, in T . Suppose _2 T . By definition, _ is total. Also by definition, it is transitive, so by Proposition 1, it is quasi-transitive and, thus, in Q. By Proposition 8, _2 B and, so, in Q " B. 2. The empty relation is modular and transitive, but not total and, so, not in Q. 3. Suppose a and b are distinct elements of W. The relation W * W {(b, a)} is total, and, since the asymmetric restriction is {(a, b)} which is transitive, it is also quasitransitive. However, if there are at least three elements in W, it is not transitive and, so, not in B. 4. Suppose W has one element. Then B contains both possible relations over W, whereasQ contains only the fully connected relation over W. Suppose W has two elements a and b. Then B contains the empty relation, the fully connected relation, and all the remaining eight relations which contain either (a, b) or (b, a), but not both. Q, on the other hand, only contains the three reflexive relations containing either (a, b) or (b, a). 2 Proposition 10 1. Q< " B = T<. 186 Representing and Aggregating Conflicting Beliefs 2. B 6` Q<. 3. Q< 6` B if W has at least three elements. 4. Q< ae B if W has one or two elements. Proof: 1. Suppose OE2 Q< " B. Since OE2 Q<, it is irreflexive, so since it is in B, it is in T< by Proposition 6. Suppose, instead, OE2 T<. By Proposition 6, OE2 B. Let _2 T be a relation such that OE is its asymmetric restriction. (Obviously such a relation must exist.) From Proposition 9, _2 Q, so OE2 Q<. Thus, OE2 Q< " B. 2. The fully connected relation over W is in B, but not asymmetric and, so, not in Q<. 3. Suppose a and b are distinct elements of W. If W has at least three elements, the relation {(a, b)} is not modular and, thus, not in B, yet it is the asymmetric restriction of the relation W * W {(b, a)} which is total and quasi-transitive (since {(a, b)} is transitive). 4. Suppose W has one element. Then B contains both possible relations over W, whereasQ < contains only the empty relation over W. Suppose W has two elements a and b. Then B contains the empty relation, the fully connected relation, and all eight of the remaining relations which contain either (a, b) or (b, a), but not both. Q<, on the other hand, only contains the three irreflexive relations. 2 Proposition 11 If S ` S, then Un(S) is modular but not necessarily transitive. Proof: Let OE= Un(S). Suppose x, y, z 2 W and x OE y. Then there is some s 2 S such that x~~~~r ) x ssr0 yDelta Psi = n(x, y) : 9s 2 S0. x~~~~is a total order over R, wS0 is a total order. The result follows from Proposition 14. 2 Proposition 16 If S ` S, then AGR(S) 2 B. Proof: By Proposition 13, AGRRf(S) is modular. AGRRf(S)+ is obviously transitive, and, by Proposition 1, it is modular as well. 2 Proposition 17 Suppose S ` S. 1. If wS is fully connected, AGR(S) = AGRUn(S). 2. If wS is a total order, AGR(S) = AGRRf(S). Proof: 1. Suppose wS is fully connected. Then the second half of the definition of AGRRf is vacuously true so that AGRRf(S) simplifies to {(x, y) : 9s 2 S. x~~~~= 2, if x, y 2 W, x 6OE* y, there exist x0, . . . , xn 2 W such that x = x0 OE* * * * OE* xn = y, and n is the smallest integer such that this is true, then xn OE* * * * OE* x0. Proof: Suppose x, y 2 W, x 6OE* y, and there exist x0, . . . , xn 2 W such that x = x0 OE** * * OE * xn = y, and n is the smallest integer such that this is true. Consider any triple xi-1, xi, xi+1, where 1 <= i <= n - 1. First, xi-1 6OE* xi+1, otherwise there would be a chain of shorter length than n between x and y. Now, since xi-1 OE* xi, there exists s1 2 S such that xi-1~~= rank(s0). Thus, r = l((x, y)) = max({rank(s0) : x = rank(s0), l((x, y)) = max({rank(s0) : x r 2 R, x 6OEAjr0 y and y 6OEAjr0 x. Since x OEAir y, there exists s 2 Si such that x ~~= rank(s0), so s wS s0. Furthermore, l0((x, y)) = rank(s) = r = l((x, y)). Now suppose x OE0 y. We show that x OE y, i.e., there exists Ai and r such that x OEAir y and, for every Aj 2 A and r0 > r 2 R, x 6OEAjr0 y and y 6OEAjr0 x, and that l((x, y)) = l0((x, y)). Since x OE0 y, there exists s 2 S such that x~~~~= r0. By Proposition 21, there exists s0 2 Sj such that x~~= rank(s0) = r0. Furthermore, l((x, y)) = rank(s) = l0((x, y)). 2 Proposition 23 If A, PA, and S are as in Definition 23, wS is a total order, andPhi ped(PA) = (OE, l), then OE+=OE. Proof: Since wS is a total order, AGR(S) = AGRRf(S) by Proposition 17. Thus, OE= AGRRf(S) = AGR(S) = AGRRf(S)+ =OE+. 2 Proposition 24 If S ` S, then vt0(S) = Un(S). Proof: Suppose (x, y) 2 Un(S). Then S 6= ; and x ~~0 and countS(x, y)/kSk > 0, so (x, y) 2 vt0(S). Suppose, instead, (x, y) 62 Un(S). Then x 6~~~~0 and countS(x, y)/kSk >= 1, so (x, y) 2 vt1(S). Suppose, instead, (x, y) 62T s2S~~= 3, then for every p 2 (0, 1), there exists S such that vtp(S) is neither modular nor transitive. Proof: Note that if kWk = 2, every relation over W is either transitive or modular (but not necessarily both), and if kWk = 1 every relation over W is both modular and transitive. Let W be a set of worlds such that kWk >= 3 and let x, y, and z denote three distinct members of W. We will define S parameterized by p such that vtp(S) is the relation{ (x, y), (y, z)} which is neither transitive or modular. Let S = {s1, . . . , sn} satisfying the following conditions: 1. n = d1/p + 1e if p <= 1/3, d2/(1 - p) + 1e otherwise.13 13. dxe denotes the ceiling of x, i.e., the smallest integer greater than or equal to x. 192 Representing and Aggregating Conflicting Beliefs 2. 1. If p <= 1/3, pn = pd1/p + 1e >= 1 + p > 1. If p > 1/3, pn = pd2/(1 - p) + 1e >= 2p/(1 - p) + p which is a monotonically increasing function, so pn > 2(1/3)/(1 - 1/3) + 1/3 = 4/3 > 1. Second, note that the set described in the fifth condition is non-empty since the number of sources described in conditions 2-4 is 2 + dpn - 1e < 1 + pn which is less than n if n > 1/(1 - p). This is true if p <= 1/3 since for these values n = d1/p + 1e > 1/p > 1/(1 - p). And it is also true if p > 1/3 since n = d2/(1 - p) + 1e > 2/(1 - p) > 1/(1 - p). (x, y) appears only in = 1 + pn - 1 = pn so (x, y) 2 vtp(S). Similarly, (y, z) appears only in = 1 + pn - 1 = pn so (y, z) 2 vtp(S). It remains to show that vtp(S) has no other members. We show that the count of each pair is less than pn. countS(w, w) = 0 < pn for all w 2 W. countS(z, w) = countS (w, x) = 0 for all w 6= y 2 W. For all w 2 W - {x, y}, (w, y) only appears in = 1 + lev_(x) > lev_(x). 2. Suppose x ./ y. If x 2 ch(W, _) then y 2 ch(W, _), so lev_(x) = lev_(y) = 0. Suppose x 62 ch(W, _). Then y 62 ch(W, _) and lev_(x) = 1 + maxy02W ({lev_(y0) : y0 OE x}). If y0 is one such element, then y0 OE y by transitivity, so lev_(y) = 1 + maxy002W Gamma Phi lev_(y00) : y00 OE yPsi Delta >= lev_(x). By an identical argument, lev_(x) >= lev_(y). Thus, lev_(x) = lev_(y). 3. Suppose lev_(x) < lev_(y). It is sufficient to prove the following: For every nonnegative integer l < lev_(y), there exists z OE y such that lev_(z) = l. We prove by induction on l. If l = lev_(y)-1, there must exist z OE y and lev_(z) = l by definition. Assume there exists z OE y for 0 < l < lev_(y) - 1 such that lev_(z) = l. Since l > 0, there exists z0 OE z such that lev_(z0) = l - 1. By transitivity, z0 OE y. 4. Suppose lev_(x) = lev_(y). If x _ y then x 6OE y from the first part of this proposition, otherwise lev_(x) < lev_(x), so y _ x. Similarly, if y _ x then y 6OE x, so x _ y. 2 Proposition 29 If _ is a transitive relation over W, then MC(_) 2 B. Proof: Let _*= MC(_) and x, y, z 2 W. Suppose x _* y. Then lev_(x) < lev_(y) or lev_(x) = lev_(y) and 9x0, y0 2 W. (lev_(x0) = lev_(y0) = lev_(x) ^ x0 ./ y0). If lev_(x) < lev_(z) or lev_(z) < lev_(y), then x _* z or z _* y. Otherwise, lev_(x) = lev_(y) = lev_(z) and 9x0, y0 2 W. (lev_(x0) = lev_(y0) = lev_(x) ^ x0 ./ y0), so x _* z. Thus, _* is modular. Now also suppose y _* z. Then lev_(y) < lev_(z) or lev_(y) = lev_(z) and 9y0, z0 2W . (lev_(y0) = lev_(z0) = lev_(y) ^ y0 ./ z0). If lev_(x) < lev_(y) or lev_(y) < lev_(z), then lev_(x) < lev_(z) by transitivity of <, so x _* z. Otherwise, lev_(x) = lev_(y) = lev_(z) and 9x0, y0 2 W. (lev_(x0) = lev_(y0) = lev_(x) ^ x0 ./ y0), so x _* z. Thus, _* is transitive. 2 Proposition 30 Suppose _ is a transitive relation over W and _*= MC(_). 194 Representing and Aggregating Conflicting Beliefs 1. _`_* and OE`OE*. 2. If _ is modular, then _*=_. 3. lev_*(x) = lev_(x) for all x 2 W. 4. If _02 B such that _`_0 and lev_0(x) = lev_(x) for all x 2 W, then _*`_0. Proof: Let x, y 2 W. 1. Suppose x _ y. Then lev_(x) <= lev_(y). If lev_(x) < lev_(y), x _* y. Suppose lev_(x) = lev_(y). Then x ./ y, so there exist x0, y0 such that lev_(x0) = lev_(y0) = lev_(x) and x0 ./ y0, i.e., x0 = x and y0 = y, so x _* y. Now suppose x OE y. Then lev_(x) < lev_(y), so x _* y and y 6_* x, so x OE* y. 2. From the first part of this proposition, _`_*, so it suffices to show _*`_. Suppose x _* y. Case 1: lev_(x) < lev_(y). Then, by Proposition 28, there exists z such that lev_(z) = lev_(x) and z OE y. By modularity, z _ x or x _ y. In the latter case, we're done. In the former case, z ./ x otherwise lev_(z) 6= lev_(x). Thus, x _ y by transitivity. Case 2: lev_(x) = lev_(y). Then there exist x0, y0 such that lev_(x0) = lev_(y0) = lev_(x) and x0 ./ y0. By modularity, x0 _ x or x _ y0. In the former case x0 ./ x by Proposition 28, in the latter x0 ./ x by Proposition 28 and transitivity. By modularity, x0 _ y or y _ x. Again applying Proposition 28 and transitivity, we have x ./ y, so x _ y. 3. We prove by induction on the level of x in _. Base case: lev_(x) = 0. Then x 2 ch(W, _). Suppose y _* x. Then lev_(x) = lev_(y) and there exist x0 and y0 such that lev_(x0) = lev_(y0) = lev_(x) = lev_(y) and x0 ./ y0, so x _* y. Thus, x 2 ch(W, _*), so lev_*(x) = 0 = lev_(x). Inductive case: Assume that lev_*(x0) = lev_(x0) for all x0 such that lev_(x0) < lev_(x); we show that lev_*(x) = lev_(x). Let z = arg maxy02W ({lev_*(y0) : y0 OE* x}); then lev_*(x) = 1 + lev_*(z). Also, let y = arg maxy02W ({lev_(y0) : y0 OE x}); then lev_(x) = 1 + lev_(y). By the first part of this proposition, OE`OE*, so y OE* x. Thus, lev_*(z) >= lev_* (y). Furthermore, lev_*(y) = lev_(y) by the inductive hypothesis, so lev_*(z) >= lev_(y). Now lev_(z) < lev_(x) by Definition 26 (otherwise x _* z, a contradiction). By the inductive hypothesis, lev_*(z) = lev_(z), so lev_*(z) < lev_(x) = 1 + lev_(y). Since levels are integral, lev_*(z) <= lev_(y), so lev_*(z) = lev_(y). Thus, lev_*(x) = 1 + lev_*(z) = 1 + lev_(y) = lev_(x). 4. Suppose _02 B, _`_0, and lev_0 (z) = lev_(z) for all z 2 W. It is clear that for any _002 B and x 2 W, x is in the partition corresponding to its level, i.e., Wlev_00 (x). Since both _* and _0 are both in B and both preserve the levels of all worlds in _, the must have identical partitions. Suppose x, y 2 W and Wi and Wj are the partitions (for both _* and _0) such that x 2 Wi and y 2 Wj. 195 Maynard-Zhang & Lehmann Suppose x _* y. If Wi 6= Wj then i < j by Proposition 7, so x _0 y, again by Proposition 7. If, instead Wi = Wj, then lev_*(x) = lev_*(y). By Definition 26, there exist x0, y0 2 W such that lev_*(x0) = lev_*(y0) = lev_*(x) and x0 ./ y0. Thus, x0, y0 2 Wi and, since _`_0, x0 ./0 y0. By Proposition 7, Wi is either fully connected or fully disconnected in _0, so Wi must be fully connected in _0. In particular, x _0 y. 2 Proposition 31 If _ is a relation over W, then MT(_) 2 B. Proof: Since _+ is transitive, MT(_) = MC (_+) 2 B by Proposition 29. 2 Proposition 32 Suppose _ is a relation over W and _*= MT(_). 1. _`_*. 2. If _ is transitive, then _*= MC(_). 3. If _ is modular, then _*=_+. 4. If _ is modular and transitive, then _*=_. 5. If _ has no conflicts, then neither does _*. Proof: Let x, y 2 W. 1. _`_+ and, by the first property of Proposition 30, _+` MC(_+) =_*, so _`_*. 2. Since _ is transitive, _+=_. Thus, _*= MC(_+) = M C(_). 3. Since _ is modular, _+ is modular by Proposition 1 so, by Proposition 30, MC(_+) =_+. Thus, _*=_+. 4. Since _ is transitive, _*= MC(_) and since _ is modular, MC(_) =_ by Proposition 30, so _*=_. 5. We first prove the following lemma: Lemma 32.1 x and y are in conflict wrt _+ iff they are in conflict wrt _. Proof: The "if" direction is obvious since the transitive closure is a monotonically additive operation. For the "only if" direction, suppose x and y are in conflict wrt_ +. Then there exist w0, . . . , wn, z0, . . . , zm 2 W such that x = w0 _+ * * * _+ wn = y = z0 _+ * * * _+ zm = x. But then, for each 0 <= i <= n - 1, there exist wi0, . . . , wipi 2 W such that wi = wi0 _ * * * _ wipi = wi+1. Similarly, for each 0 <= j <= m - 1, there exist zj0, . . . , zjqj 2 W such that zj = zj0 _ * * * _ zjqj = zj+1. Thus, x = w0 _ * * * _ wn = y = z0 _ * * * _ zm = x, so x and y are in conflict wrt _. 2 196 Representing and Aggregating Conflicting Beliefs Now, suppose x and y are in conflict wrt _*. Then x ./* y since _*2 B by Proposition 31. By Propositions 28 and 30, lev_+(x) = lev_*(x) = lev_*(y) = lev_+(y) So, since x _* y, there exist x0, y0 2 W such that lev_+(x0) = lev_+(y0) = lev_+(x) and x0 ./+ y0 by Definition 26. Thus, _+ has a conflict. By the lemma above, _ must also have a conflict. 2 Proposition 33 If S ` S and p 2 [0, 1], then AGREqp(S) 2 B. Proof: Follows immediately from the definition of AGREqp and Proposition 31. 2 Proposition 34 If S ` S and p 2 [0, 1], then AGRp(S) 2 B. Proof: Again, this follows immediately from Proposition 31. 2 Proposition 35 Suppose S ` S and p 2 [0, 1]. 1. If wS is fully connected, then AGRp(S) = AGREqp(S). 2. If wS is a total order, then AGRp(S) = AGRRfp(S) = AGRRf(S) = AGR(S). 3. AGR0(S) = AGR(S). Proof: Assume x, y 2 W. 1. It suffices to show that AGRRfp(S) = vtp(S) when wS is fully connected. Suppose (x, y) 2 AGRRfp(S). Then, by the definition of AGRRfp, there exists s 2 S such that (x, y) 2 vtp({s0 2 S : s0 jS s}). Since wS is fully connected, {s0 2 S : s0 jS s} = S, so (x, y) 2 vtp(S). Suppose, instead, (x, y) 2 vtp(S). By the definition of vtp, countS(x, y) > 0 so there exists s 2 S such that x ~~0 and count{s}(x, y)/k{s}k = 1 >= p. Consequently, (x, y) 2 vtp({s0 2 S : s0 jS s}), proving that this requirement is redundant whenw S is a total order. Thus, AGRRfp(S) is the set (x, y) such that x~~~~0 and countS0(x, y)/kS0k >= 0, so (x, y) 2 vt0(S0). Therefore, (x, y) 2 AGRRf0(S). 2 Corollary 35.1 Let S = {s1, . . . , sn} ` S and AGRf (~~0 and ksup(x, y)k/krtab(l(x, y))k >= p}) Proof: Let R = {(x, y) : ksup(x, y)k > 0 and ksup(x, y)k/krtab(l(x, y))k >= p} It suffices to show AGRRfp(S) = R. Suppose (x, y) 2 AGRRfp(S). Then there exists s 2 S such that (a) x ~~0 and countrtab(l(x,y))(x, y)/krtab(l(x, y))k >= p. But sup(x, y) = {s0 2 S : rank(s0) = l(x, y), x~~0 and ksup(x, y)k/krtab(l(x, y))k >= p, so (x, y) 2 R. Now suppose (x, y) 2 R. Then (a) ksup(x, y)k > 0 and (b) ksup(x, y)k/krtab(l(x, y))k >= p. Suppose s 2 sup(x, y); by (a), at least one such s exists. By the definition of sup, x ~~rank(s) (i.e., s0 AS s), x sss0 y. It only remains to show that (x, y) 2 vtp({s0 2 S : s0 jS s}). Since rank(s) = l(x, y), {s0 2 S : s0 jS s} = rtab(l(x, y)) as we showed above, so vtp({s0 2 S : s0 jS s}) = vtp(rtab(l(x, y))) = {(x0, y0) : countrtab(l(x,y))(x0, y0) > 0, countrtab(l(x,y))(x0, y0)/krtab(l(x, y))k >= p}. As we showed above, ksup(x, y)k = countrtab(l(x,y))(x, y). Making this substitution into (a) and (b), we see that (x, y) 2 vtp({s0 2 S : s0 jS s}), so (x, y) 2 AGRRfp(S). 2 198 Representing and Aggregating Conflicting Beliefs Proposition 37 Let A, PA, S, and wS be as in Definition 32. Then Phi sup(PA) is the support pedigreed belief state of Phi (A). Proof: Let Phi sup(PA) = (l, sup, rtab), l0 : W * W ! R [ {--} such that l0((x, y)) = max({l00(x, y) : (l00, sup00, rtab00) 2 PA}), sup0 : W * W ! 2S such that sup0(x, y) = [ (l00,sup00,rtab00)2PA, l00(x,y)=l0(x,y) sup00(x, y), and rtab0 : ranks(S) ! R such that rtab0(r) = [ (l00,sup00,rtab00)2PA, r2range(rtab00) rtab00(r). It suffices to show that l = l0, sup = sup0, and rtab = rtab0. Suppose x, y 2 W and agent Ai's support pedigreed belief state is (li, supi, rtabi). l(x, y) = max({rank(s) : x~~