Representing and Aggregating Conflicting Beliefs

P. Maynard-Zhang and D. Lehmann

Volume 19, 2003

Links to Full Text:

Abstract:
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.

Extracted Text


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