% Journal submission

\documentclass[twoside,11pt]{article}

\newcommand{\path}{.}

\usepackage{\path/Style/jair}

\usepackage{epsfig}
%\input epsf

\usepackage{\path/Style/theapa}
\usepackage{\path/Style/smalleq}
%\usepackage{\path/Style/smallsec}
\usepackage{latexsym,amsfonts}

%\bibliographystyle{alpha}
\bibliographystyle{\path/Style/theapa}

\jairheading{19}{2003}{155-203}{1/03}{9/03}
\ShortHeadings{Representing and Aggregating Conflicting Beliefs}
{Maynard-Zhang \& Lehmann}
\firstpageno{155}


%%%%%%%%%%%%
% Preamble %
%%%%%%%%%%%%

\newcommand{\comment}[1]{}
%\newcommand{\comment}[1]{\begin{description} \item[Comment] #1
%	\end{description}}
\newcommand{\fix}[1]{}
%\newcommand{\fix}[1]{{\bf [#1]}}
\newcommand{\question}[1]{}
%\newcommand{\question}[1]{\begin{description} \item[Question] #1
%	\end{description}}
\newcommand{\answer}[1]{}
%\newcommand{\answer}[1]{\begin{description} \item[Answer] #1
%	\end{description}}

%\newcommand{\email}[1]{{\tt #1}}
\newcommand{\url}[1]{{\tt #1}}
\newcommand{\keywords}[1]{}
%\newcommand{\keywords}[1]{{\bf Keywords:} #1}

\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{exmp}{Example}
\newtheorem{cor}{Corollary}[prop]
\newtheorem{lem}{Lemma}[prop]
\newtheorem{conj}{Conjecture}
\newtheorem{claim}{Claim}

\newenvironment{pf}{\trivlist \item[\hskip \labelsep{\bf
Proof: }]}{ \endtrivlist}

\newcommand{\mc}[1]{{\mathcal{#1}}}
\newcommand{\mi}[1]{{\mathit{#1}}}
\newcommand{\mb}[1]{\mathbf{#1}}
\newcommand{\mr}[1]{\mathrm{#1}}

\newcommand{\implies}{\Rightarrow}
%\newcommand{\qed}{\rule{2mm}{2mm}}
\newcommand{\qed}{$\Box$}
\newcommand{\worlds}[1]{|#1|}

\newcommand{\mca}{{\mathcal{A}}}
\newcommand{\mcb}{{\mathcal{B}}}
\newcommand{\mcl}{{\mathcal{L}}}
\newcommand{\mcn}{{\mathcal{N}}}
\newcommand{\mcp}{{\mathcal{P}}}
\newcommand{\mcr}{{\mathcal{R}}}
\newcommand{\mcq}{{\mathcal{Q}}}
\newcommand{\mcsq}{{\mathcal{Q_<}}}
\newcommand{\mcs}{{\mathcal{S}}}
\newcommand{\mct}{{\mathcal{T}}}
\newcommand{\mcst}{{\mathcal{T_<}}}
\newcommand{\mcw}{{\mathcal{W}}}

\newcommand{\true}{{\mr{true}}}
\newcommand{\false}{{\mr{false}}}

\newcommand{\C}{\mr{ch}}

\newcommand{\Bel}{\mr{Bel}}
\newcommand{\Agn}{\mr{Agn}}
\newcommand{\Con}{\mr{Con}}
\newcommand{\agnost}{\sim}
\newcommand{\sagnost}{\approx}
\newcommand{\conflict}{\bowtie}   % change suggested by daniel
%\newcommand{\conflict}{\infty}
\newcommand{\notconflict}{\mbox{\makebox[0pt][l]{$\not$}}\conflict}

\newcommand{\rank}{\mr{rank}}
\newcommand{\ranks}{\mr{ranks}}
\newcommand{\sconflict}{\bowtie}
\newcommand{\notsconflict}{\mbox{\makebox[0pt][l]{$\not$}}\sconflict}
\newcommand{\sqeq}{\equiv}
%\newcommand{\pprec}{\stackrel{l}{\prec}}
%\newcommand{\cprec}{\prec_-}

\newcommand{\Un}{\mr{Un}}
\newcommand{\AGRUn}{\mr{AGRUn}}
\newcommand{\AGRRf}{\mr{AGRRf}}
\newcommand{\AGR}{\mr{AGR}}

%\newcommand{\refine}{\bigcirc\hspace*{-2.28ex}{<}\ }
%\newcommand{\fuse}{\bigcirc\hspace*{-2.28ex}{\vee}\ }
%\newcommand{\fuse}{\makebox[0pt][c]{$\small\vee$}\bigcirc}
%\newcommand{\fuse}{\bigcirc\hspace*{-0.8em}{\small\vee}\ }
\newcommand{\fuse}{\oplus}
\newcommand{\pfuse}{\fuse_\mr{ped}}

\newcommand{\revise}{\circ}
\newcommand{\itrevise}{\diamond}
\newcommand{\belset}{\!\!\downarrow}

\newcommand{\cnt}{\mr{count}}
\newcommand{\vt}{\mr{vt}}
\newcommand{\lev}{\mr{lev}}
\newcommand{\MC}{\mr{MC}}
\newcommand{\MT}{\mr{MT}}
\newcommand{\AGREq}{\mr{AGREq}}
\newcommand{\supp}{\mr{sup}}
\newcommand{\rtab}{\mr{rtab}}
\newcommand{\spfuse}{\fuse_\mr{sup}}

\begin{document}

\title{
	Representing and Aggregating Conflicting Beliefs}
\author{
	{\name Pedrito Maynard-Zhang} {\email maynarp@muohio.edu} \\
	{\addr Department of Computer Science and Systems Analysis\\
	Miami University \\
	Oxford, Ohio 45056, USA}
\AND
	{\name Daniel Lehmann} {\email lehmann@cs.huji.ac.il} \\
	{\addr School of Computer Science and Engineering \\
	Hebrew University \\
	Jerusalem 91904, Israel}
} 
%\date{Started: 1999 March 25, Thursday}
%\date{}

\maketitle

\begin{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.
\end{abstract}

\keywords{representation of beliefs, multi-agent systems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Introduction and Preliminaries %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}\label{sec-intro}
%_____________________

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 \cite<cf.>{Grove88,KM91} supporting the
Alchourr\'{o}n, G\"{a}rdenfors, and Makinson proposal
\cite{AGM85,Gardenfors88} (known as the {\em AGM theory}) for belief
revision.

The social choice community has dealt extensively with the problem of
representing collective preferences \cite<cf.>{Sen86}. However, the
problem is formally equivalent to that of representing collective
beliefs, so the results are applicable. The classical approach has
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
\citeS{Arrow63} 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 {\em
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 {\em
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 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.

%\comment{THE FOLLOWING PARAGRAPH IS REDUNDANT}
%
%The paper is organized as follows: After some preliminary definitions,
%we discuss the representation of beliefs used in the belief revision
%community and the problems discovered in the social choice community
%with aggregating these representations. We introduce modular,
%transitive relations as a represention for aggregate belief states
%that circumvents these problems. We then describe how to construct the
%belief state of an agent given the belief states of its informant
%sources when these sources are totally preordered. We then describe a
%simple set-theory-based operator for fusing agent belief states that
%satisfies the desirable invariants of idempotence, commutativity, and
%associativity, along with a computationally effective way of computing
%this belief state. Finally, we extend our framework to incorporate
%voting.


\section{Preliminaries}
%______________________

We begin by defining various well-known properties of binary
relations\footnote{We only use binary relations in this paper, so we
will refer to them simply as relations.}; they will be useful to us
throughout the paper.
\begin{defn}
	Suppose $\leq$ is a relation over a finite set $\Omega$, i.e.,
	\mbox{$\leq \subseteq \Omega \times \Omega$}.\footnote{For the
	reader's convenience, we have included in
	Appendix~\ref{sec:notation} a key to most of the notational
	symbols used throughout the paper.} We will use \mbox{$x \leq
	y$} to denote \mbox{$(x, y) \in \leq$} and \mbox{$x \not\leq
	y$} to denote \mbox{$(x, y) \not\in \leq$}. The relation
	$\leq$ is:
	\begin{enumerate}

	\item {\em reflexive} iff \mbox{$x \leq x$} for all \mbox{$x
	\in \Omega$}. It is {\em irreflexive} iff \mbox{$x \not\leq
	x$} for all \mbox{$x \in \Omega$}.

	\item {\em symmetric} iff \mbox{$x \leq y \implies y \leq x$}
	for all \mbox{$x, y \in \Omega$}. It is {\em asymmetric} iff
	\mbox{$x \leq y \implies y \not\leq x$} for all \mbox{$x, y
	\in \Omega$}. It is {\em anti-symmetric} iff \mbox{$x \leq y
	\wedge y \leq x \implies x = y$} for all \mbox{$x, y \in
	\Omega$}.

	\item the {\em asymmetric restriction} of a relation $\leq'$
	over $\Omega$ iff \mbox{$x \leq y \Leftrightarrow x \leq' y
	\wedge y \not\leq' x$} for all \mbox{$x, y \in \Omega$}. It is
	the {\em symmetric restriction} of $\leq'$ iff \mbox{$x \leq y
	\Leftrightarrow x \leq' y \wedge y \leq' x$} for all \mbox{$x,
	y \in \Omega$}.

	\item {\em total} iff \mbox{$x \leq y \vee y \leq x$} for all
	\mbox{$x, y \in \Omega$}.

	\item {\em modular} iff \mbox{$x \leq y \implies x \leq z \vee
	z \leq y$} for all \mbox{$x, y, z \in \Omega$}.

	\item {\em transitive} iff \mbox{$x \leq y \wedge y \leq z
	\implies x \leq z$} for all \mbox{$x, y, z \in \Omega$}.

	\item {\em quasi-transitive} iff its asymmetric restriction is
	transitive.

	\item the {\em transitive closure} of a relation $\leq'$ over
	$\Omega$ iff, for some integer $n$,
	\begin{displaymath}
	  x \leq y \Leftrightarrow \exists w_0, \ldots, w_n \in
	     \Omega.\ x = w_0 \leq' \cdots \leq' w_n = y
	\end{displaymath}
	for all \mbox{$x, y \in \Omega$}. (We generally use $\leq^+$
	to denote the transitive closure of a relation $\leq$.)

	\item {\em acyclic} iff \mbox{$\forall w_0, \ldots, w_n \in
	\Omega.\ w_0 < \cdots < w_n$} implies \mbox{$w_n \not< w_0$}
	for all integers $n$, where $<$ is the asymmetric restriction
	of $\leq$.

	\item a {\em total preorder} iff it is total and
	transitive. It is a {\em total order} iff it is also
	anti-symmetric.

	\item an {\em equivalence relation} iff it is reflexive,
	symmetric, and transitive.

	\item {\em fully connected} iff $x \leq y$ for all $x, y \in
	\Omega$. It is {\em fully disconnected} iff $x \not\leq y$ for
	all $x, y \in \Omega$.

	\end{enumerate}

\end{defn}

\begin{prop}\label{prop-Props}\hspace{0ex}\\[-0.5cm]
	\begin{enumerate}

	\item The transitive closure of a modular relation is
	modular.

	\item Every transitive relation is quasi-transitive.

	\item \cite{Sen86} Every quasi-transitive relation is
	acyclic.

	\end{enumerate}
\end{prop}

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 {\em choice set}:
\begin{defn}\label{def:choiceset}
	If $\leq$ is a relation over a finite set $\Omega$, $<$ is its
	asymmetric restriction, and \mbox{$X \subseteq \Omega$}, then
	the {\em choice set of $X$ with respect to $\leq$} is
	\begin{displaymath}
		\C(X, \leq) = \{x \in X : \not\exists x' \in X.\ x' <
			x\}.
	\end{displaymath}
\end{defn}
A {\em choice function} is one which assigns to every (non-empty) subset $X$ a
(non-empty) subset of $X$:
\begin{defn}
	A {\em choice function} over a finite set $\Omega$ is a
	function \mbox{$f : {2^\Omega}\setminus\emptyset \to
	{2^\Omega}\setminus\emptyset$} such that \mbox{$f(X) \subseteq
	X$} for every non-empty \mbox{$X \subseteq \Omega$}.
\end{defn}
Now, every acyclic relation defines a choice function, one which
assigns to each subset its choice set:
\begin{prop}\label{prop-Choice}
	\cite{Sen86} Given a relation $\leq$ over a finite set
	$\Omega$, the choice set operation $\C$ defines a choice
	function iff $\leq$ is acyclic.\footnote{Sen's uses a slightly
	stronger definition of choice sets, but the theorem still
	holds in our more general case.}
\end{prop}
If a relation is not acyclic, elements involved in a cycle are said to
be in a {\em conflict} because we cannot order them:
\begin{defn}\label{def-conflict}
	Given a relation $<$ over a finite set $\Omega$, $x$ and $y$
	are in a {\em conflict wrt $<$} iff there exist \mbox{$w_0,
	\ldots, w_n, z_0, \ldots, z_m \in \Omega$} such that \mbox{$x
	= w_0 < \cdots < w_n = y = z_0 < \cdots < z_m = x$}, where
	\mbox{$x, y \in \Omega$}.
\end{defn}

Finally, the cardinality of a set $\Omega$ will be denoted
$\|\Omega\|$.

Assume we are given some language $\mcl$ with a satisfaction relation
$\models$ for $\mcl$. Let $\mcw$ be a finite, non-empty set of
possible worlds (interpretations) over $\mcl$. For a world $w \in
\mcw$ and a sentence \mbox{$p \in \mcl$}, \mbox{$w \models p$} iff $p$
evaluates to true in $w$. Given a sentence $p$, \mbox{$|p| = \{w \in
\mcw \mid w \models p\}$}.
%If $p$ and $q$ are sentences, then \mbox{$p
%\models q$} iff \mbox{$\forall w \in |p|.\ w \models q$}.


%%%%%%%%%%%%%%%%%%
% Representation %
%%%%%%%%%%%%%%%%%%

\section{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.

\subsection{Belief Revision Representation of Conditional Beliefs}
%-----------------------------------------------------------------

Much of the belief revision field has built on the seminal work by
Alchourr\'{o}n, G\"{a}rdenfors, and Makinson \cite{AGM85,Gardenfors88}
refered to as the {\em 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 \cite{Grove88,KM91,MS01} showed that
accepting these postulates amounts to assuming that an individual's
{\em belief state} is represented by a total preorder $\preceq$ over
$\mcw$; revision of the individual's beliefs by a sentence $p \in
\mcl$ then consists of computing \mbox{$\C(|p|, \preceq)$}.

\citeA{KLM90} and \citeA{LM92} developed a similar central role for
ordered structures in the semantics of nonmonotonic logics, and
\citeA{GM94} established the relation between the two topics.
%Indeed, the role of orderings in belief revision and non-monotonic
%logics has been well established in the literature.
Semantically, $\preceq$ represents the weak relative likelihood of
possible worlds: \mbox{$x \preceq y$} means possible world $x$ is
considered to be at least as likely as possible world
$y$.\footnote{The direction of the relation symbol is unintuitive, but
standard practice in the belief revision community.}  If \mbox{$x
\preceq y$} and \mbox{$y \preceq x$}, then $x$ and $y$ are considered
equally likely.  We can also interpret $\preceq$ sententially using
the famous {\em Ramsey Test} \cite{Ramsey31}: it encodes a set of
conditional beliefs, i.e., not only what is believed now (called the
{\em 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 $\mcl$ and $q$ is satisfied by all the worlds in
\mbox{$\C(|p|, \preceq)$}; we write \mbox{$\Bel(p ? q)$}. If neither
the belief \mbox{$p ?  q$} nor the belief \mbox{$p ? \neg q$} hold in
the belief state, it is said to be {\em agnostic} with respect to
\mbox{$p ? q$}, written \mbox{$\Agn(p ? q)$}.  The belief set induced
by the belief state consists of all those sentences $q$ such that
\mbox{$\Bel(true ?  q)$} holds.

%Thus, a total preorder over the set of possible worlds is now a fairly
%well-accepted representation for a belief state in the belief revision
%community \cite{Grove88,KM91,LM92,GM94}.

\subsection{Social Choice Implications}\label{subsec-SocialChoice}
%--------------------------------------

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.

\citeS{Arrow63} celebrated Impossibility Theorem showed that no
aggregation operator over total preorders exists satisfying the
following small set of desirable properties:
\begin{defn}
Let $f$ be an aggregation operator over the relations $\preceq_1$,
\ldots, $\preceq_n$ of $n$ individuals, respectively, over a finite
set of alternatives $\Omega$, and let \mbox{$\preceq\ = f(\preceq_1,
\ldots, \preceq_n)$}.
	\begin{itemize}

	\item {\em Restricted Range}: The range of $f$ is the set of
	total preorders over $\Omega$.

	\item {\em Unrestricted Domain}: The domain of $f$ is the set
	of $n$-tuples of total preorders over $\Omega$.

	\item {\em Pareto Principle}: If \mbox{$x \prec_i y$} for all
	$i$, then \mbox{$x \prec y$}.\footnote{Technically, this is
	known as the {\em weak} Pareto principle. The strong Pareto
	principle states that \mbox{$x \prec y$} if there exists $i$
	such that \mbox{$x \prec_i y$} and \mbox{$x \preceq_i y$} for
	all $i$. Obviously, the strong version implies the weak
	version, so Arrow's theorem applies to it as well.}

	\item {\em Independence of Irrelevant Alternatives (IIA)}:
	Suppose \mbox{$\preceq'\ = f(\preceq_1', \ldots,
	\preceq_n')$}. If, for \mbox{$x, y \in \Omega$}, \mbox{$x
	\preceq_i y$} iff \mbox{$x \preceq_i' y$} for all $i$, then
	\mbox{$x \preceq y$} iff \mbox{$x \preceq' y$}.

	\item {\em Non-Dictatorship}: There is no individual $i$ such
	that, for every tuple in the domain of $f$ and every \mbox{$x,
	y \in \Omega$}, \mbox{$x \prec_i y$} implies \mbox{$x \prec
	y$}.

	\end{itemize}
\end{defn}

\begin{prop}\label{prop-Arrow}
	\cite{Arrow63} There is no aggregation operator that satisfies
	restricted range, unrestricted domain, Pareto principle,
	independendence of irrelevant alternatives, and
	nondictatorship.
\end{prop}
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 \cite{Sen86}.
%see \cite{Black58} as well.
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 {\em principle of categorical
matching} (cf.~Gardenfors and Rott's \citeyearR{GR95} survey). This
problem is closely related to the second which is that total,
quasi-transitive relations have unsatisfactory semantics.  If
$\preceq$ is total and quasi-transitive but not a total preorder, its
indifference relation is not transitive:
\begin{prop}
	Let $\preceq$ be a relation over a finite set $\Omega$ and let
	$\agnost$ be its symmetric restriction. If $\preceq$ is total
	and quasi-transitive but not transitive, then $\agnost$ is not
	transitive.
\end{prop}
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.\footnote{However, see \citeS{Luce56} work on {\em semiorders}
for some of the opposing arguments in the transitivity of indifference
debate.} 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
$\preceq$ can express four possible relationships between a pair of
alternatives $a$ and $b$: \mbox{$a \preceq b$} and \mbox{$b
\not\preceq a$}, \mbox{$b \preceq a$} and \mbox{$a \not\preceq b$},
\mbox{$a \preceq b$} and \mbox{$b \preceq a$}, and \mbox{$a
\not\preceq b$} and \mbox{$b \not\preceq a$}. Totality reduces this
set to the first three which, under the interpretation of 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 \citeS{KT79} persuasive arguments that individuals {\em are}
often ambivalent).  However, the assumption is inappropriate if we
want to represent aggregate preferences since individuals will almost
certainly have differences of opinion.

\subsection{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.

\subsubsection{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 \citeA[p.~19]{Kreps90}
who is interested in representing both indifference and
incomparability. Unlike \citeauthor{Kreps90}, 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 {\em generalized belief states}:
\begin{defn}
	A {\em generalized belief state $\prec$} is a modular,
	transitive relation over $\mcw$. The set of possible
	generalized belief states over $\mcw$ is denoted $\mcb$.
\end{defn}
We interpret \mbox{$a \prec 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
$\agnost$ defined such that \mbox{$x \agnost y$} if and only if
\mbox{$x \not\prec y$} and \mbox{$y \not\prec x$}. We define the
conflict relation corresponding to $\prec$, denoted $\conflict$, so
that \mbox{$x \conflict y$} iff \mbox{$x \prec y$} and \mbox{$y \prec
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 $\conflict$ precisely represents
conflicts in a belief state in the sense of
Definition~\ref{def-conflict}.

For convenience, we will refer to generalized belief states simply as
belief states except when to do so would cause confusion.

\subsubsection{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.

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: \mbox{$\mcw = \{a, b, c\}$} and \mbox{$\prec = \{(a,c)\}$},
so that \mbox{$\agnost = \{(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:
\begin{prop}
	Suppose a relation $\prec$ is transitive and $\agnost$ is the
	corresponding agnosticism relation. Then $\agnost$ is
	transitive iff $\prec$ is modular.
\end{prop}
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~\ref{def-conflict}), 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 $\mct$ be the set of
total preorders over $\mcw$, $\mcst$, the set of their asymmetric
restrictions.
\begin{prop}\label{prop-TPisoMTI}
	$\mcst \subset \mcb$ and is the set of irreflexive relations
	in $\mcb$.
\end{prop}
%\begin{prop}\label{prop-TPisoMTI}
%	The set of irreflexive relations in $\mcb$ is isomorphic to
%	$\mct$ and, in fact, equals $\mcst$.
%\end{prop}

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.
\begin{prop}\label{prop-rep}
	\mbox{$\prec \in \mcb$} iff there is a partition
	\mbox{$\mathbf{W} = \langle W_0, \ldots, W_n \rangle$} of
	$\mcw$ such that:
	\begin{enumerate}

	\item For every \mbox{$x \in W_i$} and \mbox{$y \in W_j$},
	\mbox{$i \neq j$} implies \mbox{$i < j$} iff \mbox{$x \prec
	y$}.

	\item Every $W_i$ is either fully connected (\mbox{$w \prec
	w'$} for all \mbox{$w, w' \in W_i$}) or fully disconnected
	(\mbox{$w \not\prec w'$} for all \mbox{$w, w' \in W_i$}).

	\end{enumerate}
\end{prop}
Figure~\ref{fig-gbs} 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 $\mcw$ which satisfy the sentence inside. An arc between
circles indicates that $w \prec w'$ for every $w$ in the head circle
and $w'$ in the tail circle; no arc indicates that $w \not\prec w'$
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.)

\begin{figure}[htb]
\centerline{\epsfig{file=\path/Figures/gbs.eps,height=1in}}
\caption{Three examples of generalized belief states: (a) a total
preorder, (b) the asymmetric restriction of a total preorder, (c)
neither.}\label{fig-gbs}
\end{figure}

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 $\prec$ is agnostic about
conditional belief \mbox{$p ? q$} (i.e., \mbox{$\Agn(p ? q)$}) if
the choice set of worlds satisfying $p$ contains both worlds which
satisfy $q$ and $\neg q$ and is fully disconnected. It is in conflict
about this belief, written \mbox{$\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~\ref{prop-TPisoMTI}, it is obvious that $\mcb$ subsumes
the class of total preorders $\mct$ and, in fact, $\mct$ is the set of
reflexive relations in $\mcb$.
\begin{prop}\label{prop-TPsubMT}
	\mbox{$\mct \subset \mcb$} and is the set of reflexive
	relations in $\mcb$.
\end{prop}
Secondly, $\mcb$ neither subsumes nor is subsumed by the set of total,
quasi-transitive relations, and the intersection of the two classes is
$\mct$. Let $\mcq$ be the set of total, quasi-transitive relations
over $\mcw$, and $\mcsq$, the set of their asymmetric restrictions.
\begin{prop}\label{prop-MTandTQ}\hspace{0ex}\\[-0.5cm]
	\begin{enumerate}

	\item \mbox{$\mcq \cap \mcb = \mct$}.

	\item \mbox{$\mcb \not\subseteq \mcq$}.

	\item \mbox{$\mcq \not\subseteq \mcb$} if $\mcw$ has at least
	three elements.

	\item \mbox{$\mcq \subset \mcb$} if $\mcw$ has one or two
	elements.

	\end{enumerate}
\end{prop}
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 $\mcst$:
\begin{prop}\hspace{0ex}\\[-0.5cm]
	\begin{enumerate}

	\item \mbox{$\mcsq \cap \mcb = \mcst$}.

	\item \mbox{$\mcb \not\subseteq \mcsq$}.

	\item \mbox{$\mcsq \not\subseteq \mcb$} if $\mcw$ has at least
	three elements.

	\item \mbox{$\mcsq \subset \mcb$} if $\mcw$ has one or two
	elements.

	\end{enumerate}
\end{prop}

\question{Point out that we can't represent the situation where we are
agnostic about two disjoint sets of worlds, each of which is ordered?}
\answer{No. Not clear that this matters. Would require partial orders
which other solutions don't support anyway.}

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.


%%%%%%%%%%%%%%%
% Aggregation %
%%%%%%%%%%%%%%%

\section{Single-Agent Belief State Construction}\label{sec-AGR}
%_______________________________________________

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.

\begin{exmp}\label{ex-robot}
	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:
	\begin{enumerate}

	\item $s_p$, 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.

	\item $s_m$, 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.

	\item $s_t$, 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.

	\end{enumerate}

	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~\ref{fig-robot}.

	\begin{figure}[htb]
	\centerline{\epsfig{file=\path/Figures/robot.eps,height=2in}}
	\caption{The belief states of $s_p$, $s_m$, and $s_t$ in
	Example~\ref{ex-robot}.}\label{fig-robot}
	\end{figure}
\end{exmp}

\subsection{Sources}
%-------------------

Let us begin the formal development by defining sources and their
belief states:
\begin{defn}\label{defn-sources}
	$\mcs$ is a finite set of {\em sources}. With each source
	\mbox{$s \in \mcs$} is associated a belief state \mbox{$<^s
	\in \mcb$}.
\end{defn}
We denote the agnosticism and conflict relations of a source $s$ by
$\sagnost^s$ and $\sconflict^s$, respectively.  It is possible to
assume that the belief state of a source is conflict-free, i.e.,
acyclic. However, this is not necessary if we allow sources to suffer
from the human malady of ``being torn between possibilities.''

We assume that the agent's credibility ranking over the sources is a
total preorder built on a totally ordered set of ranks (e.g., integers).
\begin{defn}
	$\mcr$ is a totally ordered finite set of {\em ranks}.
\end{defn}

\begin{defn}
	\mbox{$\rank : \mcs \to \mcr$} assigns to each source a
	rank. Also, for \mbox{$S \subseteq \mcs$}, \mbox{$\ranks(S)$}
	denotes the set \mbox{$\{r \in \mcr : \exists s \in S.\
	\rank(s) = r\}$}.
\end{defn}

\begin{defn}
	The total preorder over $\mcs$ induced by the ordering over
	$\mcr$ will be denoted $\sqsupseteq$. That is, \mbox{$s
	\sqsupseteq s'$} iff \mbox{$\rank(s) \geq \rank(s')$}; we say
	$s$ is {\em as credible as} $s'$. The restriction of
	$\sqsupseteq$ to \mbox{$S \subseteq \mcs$} will be denoted
	$\sqsupseteq_S$.
\end{defn}
We use $\sqsupset$ and $\sqeq$ to denote the asymmetric and symmetric
restrictions of $\sqsupseteq$, respectively.\footnote{Note that,
unlike the relations representing belief states, $\geq$ and
$\sqsupseteq$ are read in the intuitive way, that is, ``greater''
corresponds to ``better.''} The finiteness of $\mcs$ ($\mcr$) 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 $\mcr$
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 \mbox{$S
\subseteq \mcs$}. We look at two special cases---aggregation of
equally ranked and strictly ranked sources---before considering the
general case.

\subsection{Aggregating Equally Ranked Sources}
%----------------------------------------------

Suppose all the sources have the same rank so that $\sqsupseteq_S$ is
fully connected. Intuitively, we want to take all offered opinions
seriously, so we take the union of the relations:
\begin{defn}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\Un(S)$} is the
	relation \mbox{$\bigcup_{s \in S} <^s$}.
\end{defn}
By simply taking the union of the source belief states, we may lose
transitivity. However, we do not lose modularity:
\begin{prop}\label{prop-UnModnotT}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\Un(S)$} is modular
	but not necessarily transitive.
\end{prop}
Thus, we know from Proposition~\ref{prop-Props} that we need only take
the transitive closure of \mbox{$\Un(S)$} to get a belief state:
\begin{defn}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGRUn(S)$} is the
	relation \mbox{$\Un(S)^+$}.
\end{defn}

\begin{prop}\label{prop-AGRUn}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGRUn(S) \in \mcb$}.
\end{prop}
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
$\mcw$.

\begin{exmp}
	Suppose all three sources in the space robot scenario of
	Example~\ref{ex-robot} are considered equally credible, then
	the aggregate belief state will be the fully connected
	relation indicating that there are conflicts over every
	belief.
\end{exmp}

\subsection{Aggregating Strictly Ranked Sources}
%-----------------------------------------------

Next, consider the case where the sources are strictly ranked, i.e.,
$\sqsupseteq_S$ is a total order. We define a {\em lexicographic}
operator such that lower ranked sources {\em 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:
\begin{defn}\label{def-AGRRf}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGRRf(S)$} is the
	relation
	\begin{displaymath}
	  \left\{(x, y) : \exists s \in S.\ x <^s y
		\wedge \left(\forall s' \in S.\ s' \sqsupset_S s
		\implies x \sagnost^{s'} y\right)\right\}.
	\end{displaymath}
\end{defn}
%The definition of the \mbox{$\AGRRf$} operator does not rely on
%$\sqsupseteq_S$ being a total order, and we will use it in this more
%general setting in the following sub-section.
As with $\AGRUn(S)$, $\AGRRf(S)$ is not guaranteed to be transitive,
but it is always modular:
\begin{prop}\label{prop-AGRRfModnotT}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGRRf(S)$} is modular
	but not necessarily transitive.
\end{prop}
However, in the case that $\sqsupseteq_S$ is a total order, the result
of applying \mbox{$\AGRRf$} is guaranteed to be a belief state.
\begin{prop}\label{prop-AGRRf}
	If \mbox{$S \subseteq \mcs$} and $\sqsupseteq_S$ is a total
	order, then \mbox{$\AGRRf(S) \in \mcb$}.
\end{prop}

\begin{exmp}\label{ex-robot-AGRRf}
	Suppose, in the space robot scenario of
	Example~\ref{ex-robot}, the technician is considered more
	credible than the manager who, in turn, is considered more
	credible than the programmer. The aggregate belief state,
	shown in Figure~\ref{fig-robot-AGRRf}, informs the robot
	(correctly) that the feedback system has crashed, but that it
	shouldn't worry about an overload problem and should keep
	sending data.

	\begin{figure}[htb]
	\centerline{\epsfig{file=\path/Figures/robot-AGRRf.eps,height=2in}}
	\caption{The belief state after aggregation in
	Example~\ref{ex-robot-AGRRf} when \mbox{$s_t \sqsupset s_m
	\sqsupset s_p$}.}\label{fig-robot-AGRRf}
	\end{figure}
\end{exmp}

\subsection{General Aggregation}
%-------------------------------

In the general case, we may have several ranks represented and
multiple sources of each rank. It will be instructive to first
consider the following seemingly natural strawman operator,
\mbox{$\AGR^*$}: First combine equally ranked sources using
\mbox{$\AGRUn$}, then aggregate the strictly ranked results using what
is essentially \mbox{$\AGRRf$}.
\begin{defn}
	Let \mbox{$S \subseteq \mcs$}. For any $r \in \mcr$, let
	\mbox{$<_r = \AGRUn(\{s \in S: \rank(s) = r\})$} and
	$\sagnost_r$, the corresponding agnosticism
	relation. \mbox{$\AGR^*(S)$} is the relation
	\begin{displaymath}
		\left\{(x, y) :
			\exists r \in \mcr.\ x <_r y \wedge
			\left(\forall r' \in \ranks(S).\ r' > r \implies
			        x \sagnost_{r'} y\right)
		\right\}.
	\end{displaymath}
\end{defn}
$AGR^*$ indeed defines a legitimate belief state:
\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGR^*(S) \in \mcb$}.
\end{prop}

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:
\begin{exmp}\label{ex-AGR*}
	Let \mbox{$\mcw = \{a, b, c\}$}. Suppose $S \subseteq \mcs$
	such that $S = \{s_0, s_1, s_2\}$ with belief states $<^{s_0}
	= \{(b, a), (b, c)\}$ and $<^{s_1} = <^{s_2} = \{(a, b), (c,
	b)\}$, and where $s_2 \sqsupset s_1 \sqeq s_0$. Then
	$\AGR^*(S)$ is $\{(a, b), (c, b), (a, c), (c, a), (a, a), (b,
	b), (c, c)\}$. All sources are agnostic over $a$ and $c$, yet
	$(a, c)$ and $(c, a)$ are in the result because of the
	transitive closure in the lower rank involving opinions ($(b,
	c)$ and $(b, a)$) which actually get overridden in the final
	result.
\end{exmp}

Because of these undesired effects, we propose another aggregation
operator which circumvents this problem by applying refinement (as
defined in Definition~\ref{def-AGRRf}) to the set of source belief
states before inferring new opinions via closure:
\begin{defn}\label{def-AGR}
	The {\em rank-based aggregation} of a set of sources \mbox{$S
	\subseteq \mcs$}, denoted $\AGR(S)$, is $\AGRRf(S)^+$.
\end{defn}
Encouragingly, \mbox{$\AGR$} outputs a valid belief state:
\begin{prop}\label{prop-AGR}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGR(S) \in \mcb$}.
\end{prop}
The output for our running space robot example is also reasonable:
\begin{exmp}\label{ex-robot-AGR}
	Suppose, in the space robot scenario of
	Example~\ref{ex-robot}, the technician is still considered
	more credible than the manager and the programmer, but the
	latter two are considered equally credible. The aggregate
	belief state, shown in Figure~\ref{fig-robot-AGR}, still gives
	the robot the correct information about the state of the
	system. The robot also learns for future reference that there
	is some disagreement over whether or not there would have been
	a data overload if the feedback system were working.

	\begin{figure}[htb]
	\centerline{\epsfig{file=\path/Figures/robot-AGR.eps,height=1.5in}}
	\caption{The belief state after aggregation in
	Example~\ref{ex-robot-AGR} when \mbox{$s_t \sqsupset s_m
	\sqeq s_p$}.}\label{fig-robot-AGR}
	\end{figure}
\end{exmp}
Furthermore, we observe that \mbox{$\AGR$}, when applied to the set of
sources in Example~\ref{ex-AGR*}, does indeed bypass the problem
described above of extraneous opinion introduction:
\begin{exmp}
	Assume $\mcw$, $S$, and $\sqsupseteq$ are as in
	Example~\ref{ex-AGR*}; \mbox{$\AGR(S) = \{(a, b), (c, b)\}$}
	as desired. The concerned reader may note that $s_2$ is a
	``dictator'' in the sense that $s_2$'s opinions override all
	opposing opinions. However, this is reasonable in the context
	because all other sources have strictly lower rank.
\end{exmp}

We observe that \mbox{$\AGR$} behaves well in the special cases we've
considered, reducing to \mbox{$\AGRUn$} when all sources have equal rank, and
to \mbox{$\AGRRf$} when the sources are totally ranked:
\begin{prop}\label{prop-AGRSpecial}
	Suppose \mbox{$S \subseteq \mcs$}.
	\begin{enumerate}

	\item If $\sqsupseteq_S$ is fully connected, \mbox{$\AGR(S) =
	\AGRUn(S)$}.

	\item If \mbox{$\sqsupseteq_S$} is a total order,
	\mbox{$\AGR(S) = \AGRRf(S)$}.

	\end{enumerate}
\end{prop}
Another property of $\AGR$ is that its transitive closure part
minimally extends the result of $\AGRRf$ to make it complete (i.e.,
all conflicts represented explicitly) in the sense that new opinions
are only added between worlds already involved in a conflict:
\begin{prop}\label{prop-conflict}
	Suppose \mbox{$S \subseteq \mcs$}, \mbox{$\prec_* =
	\AGRRf(S)$}, \mbox{$\prec = \AGR(S)$}, and \mbox{$x \not\prec_*
	y$} for \mbox{$x, y \in \mcw$}. If \mbox{$x \prec y$}, then
	\mbox{$x \conflict y$}.
\end{prop}
One small observation: \mbox{$\AGR(\emptyset) = \emptyset$} is a
property of our definition, reflecting the fact that we should not
generate opinions out of nothing.

\subsection{Arrow, Revisited}
%----------------------------

Finally, a strong argument in favor of \mbox{$\AGR$} is that it
satisfies Arrow's conditions. Technically, our setting is slightly
different from that of Arrow's, so we need to modify each condition so
that it is appropriate for our setting, yet retains the intended
spirit of the original condition. Let $f$ be an operator which
aggregates the belief states $<^{s_1}$, \ldots, $<^{s_n}$ over $\mcw$
of $n$ sources \mbox{$s_1, \dots, s_n \in S \subseteq \mcs$},
respectively, let \mbox{$\prec\ = f(<^{s_1}, \ldots, <^{s_n})$}, and
let $\sqsupseteq_S$ be a total preorder over $S$. We consider each
condition separately.

\paragraph{Restricted range}
For our setting, the output of the aggregation function will be a
modular, transitive belief state rather than a total preorder
considered by Arrow.

\begin{defn}
	{\em (modified) Restricted Range}: The range of $f$ is $\mcb$.
\end{defn}

\paragraph{Unrestricted domain}
Similarly, the input to the aggregation function will be modular,
transitive belief states of sources rather than total preorders.

\begin{defn}
	{\em (modified) Unrestricted Domain}: For each $i$, $<^{s_i}$
	can be any member of $\mcb$.
\end{defn}

\paragraph{Pareto principle}
In Arrow's setting, the relations represented non-strict relative
likelihood (preference, actually) so that the asymmetric restrictions
of the relations were used to define the Pareto principle. However, in
our setting, generalized belief states already represent strict
likelihood. Consequently, we use the actual input and output relations
of the aggregation function in place of their asymmetric restrictions to
define the Pareto principle. Obviously, because of $\AGR$'s ability to
introduce conflicts, it will not satisfy the original formal Pareto
principle which would essentially require that if all sources have an
unconflicted belief of one world being strictly more likely than
another, this must also be true in the aggregate belief state. Neither
condition is necessarily stronger than the other.

\begin{defn}
	{\em (modified) Pareto Principle}: If \mbox{$x <^{s_i} y$} for
	all $i$, then \mbox{$x \prec y$}.
\end{defn}

\paragraph{Independence of irrelevant alternatives}
Conflicts are defined in terms of cycles, not necessarily binary. By
allowing the existence of conflicts, we effectively have made it
possible for outside worlds to affect the relation between a pair of
worlds, viz., by involving them in a cycle. As a result, we need to
weaken IIA to say that the relation between worlds should be
independent of other worlds {\bf unless} these other worlds put them
in conflict. This makes intuitive sense: if two worlds are put into
conflict after aggregation due to a cycle involving other worlds, we
may need to access these other worlds to be able to detect the
conflict.

\begin{defn}
	{\em (modified) Independence of Irrelevant Alternatives
	(IIA)}: Suppose\linebreak
	\mbox{$s'_1, \ldots, s'_n \in \mcs$} such that
	\mbox{$s_i \sqeq_S s'_i$} for all $i$, and \mbox{$\prec' =
	f(<^{s'_1}, \ldots, <^{s'_n})$}. Further suppose \mbox{$x
	<^{s_i} y$} iff \mbox{$x <^{s'_i} y$} for all $i$, \mbox{$x
	\notconflict y$}, and \mbox{$x \notconflict' y$}. Then
	\mbox{$x \prec y$} iff \mbox{$x \prec' y$}.
\end{defn}

\paragraph{Non-dictatorship}
As with the Pareto principle definition, we use the actual input and
output relations to define non-dictatorship since belief states
represent strict likelihood. From this perspective, our setting
requires that informant sources of the highest rank be ``dictators''
in the sense considered by Arrow. However, the setting originally
considered by Arrow was one where all individuals are ranked
equally. Thus, we make this explicit in our new definition of
non-dictatorship by adding the pre-condition that all sources be of
equal rank. Now, \mbox{$\AGR$} treats a set of equally ranked sources
equally by taking all their opinions seriously, at the price of
introducing conflicts. So, intuitively, there are no
dictators. However, because Arrow did not account for conflicts in his
formulation, {\em all} the sources will be ``dictators'' by his
definition. We need to modify the definition of non-dictatorship to
say that no source should always push opinions through without them ever
being contested.

\begin{defn}
	{\em (modified) Non-Dictatorship}: If \mbox{$s_i \sqeq_S s_j$}
	for all \mbox{$i, j$}, then there is no $i$ such that, for
	every combination of source belief states and every \mbox{$x,
	y \in \mcw$}, \mbox{$x <^{s_i} y$} and \mbox{$y \not<^{s_i}
	x$} implies \mbox{$x \prec y$} and \mbox{$y \not\prec x$}.
\end{defn}

We now show that \mbox{$\AGR$} indeed satisfies these conditions:
\begin{prop}\label{prop-Arrow2}
	Let \mbox{$S = \{s_1, \ldots, s_n\} \subseteq \mcs$} and
	\mbox{$AGR_f(<^{s_1}, \ldots, <^{s_n}) =
	\AGR(S)$}. \mbox{$\AGR_f$} satisfies (the modified versions of)
	restricted range, unrestricted domain, Pareto principle, IIA,
	and non-dictatorship.
\end{prop}


%%%%%%%%%%
% Fusion %
%%%%%%%%%%

\section{Multi-Agent Fusion}
%___________________________

So far, we have only considered the case where a single agent must
construct or update her belief state once informed by a set of
sources. Multi-agent fusion is the process of aggregating the belief
states of a set of agents, each with its respective set of informant
sources. We proceed to formalize this setting.

\subsection{Formalization}
%-------------------------

An agent $A$ is {\em informed by} a set of sources \mbox{$S \subseteq
\mcs$}.\footnote{Each source can be thought of as a primitive agent
with fixed belief state.} Agent $A$'s {\em induced belief state} is
the belief state formed by aggregating the belief states of its
informant sources, i.e., \mbox{$\AGR(S)$}. We will use $A_\emptyset$
and $A_\mcs$ to denote special agents informed by $\emptyset$ and
$\mcs$, respectively.

Assume the set of agents to fuse agree upon \mbox{$\rank$} (and,
consequently, $\sqsupseteq$).\footnote{We could easily extend the
framework to allow for individual rankings, but we felt that the small
gain in generality would not justify the additional complexity and
loss of perspicuity. Similarly, we could consider each agent as having
a credibility ordering only over its informant sources. However, it is
unclear how, for example, crediblity orderings over disjoint sets of
sources should be combined into a new credibility ordering since their
union will not be total.}  We define the fusion of this set to be an
agent informed by the combination of informant sources:
\begin{defn}\label{def-fusion}
	Let \mbox{$\mca = \{A_1, \ldots, A_n\}$} be a set of agents
	such that each agent $A_i$ is informed by \mbox{$S_i \subseteq
	\mcs$}. The {\em fusion} of $\mca$, written
	\mbox{$\fuse(\mca)$}, is an agent informed by \mbox{$S =
	\bigcup^n_{i=1} S_i$}.
\end{defn}
Not surprisingly given its set-theoretic definition, fusion is
idempotent, commutative, and associative. These properties guarantee
the invariance required in multi-agent belief aggregation applications
such as our space robot domain.

\subsection{Computing Fusion Efficiently}
%----------------------------------------

In the multi-agent space robot scenario described in
Section~\ref{sec-intro}, we only have a direct need for the belief
states that result from fusion. We are only interested in the belief
states of the original sources in so far as we want the fused belief
state to reflect its informant history. An obvious question is whether
it is possible to compute the belief state induced by the agents'
fusion solely from their initial belief states, that is, without
having to reference the belief states of their informant sources. This
is highly desirable because of the expense of storing---or, as in the
case of our space robot example, transmitting---all source belief
states; we would like to represent each agent's knowledge as compactly
as possible.

In fact, we can do this if all sources have equal rank. We simply take
the transitive closure of the union of the agents' belief states:
\begin{prop}\label{prop-FuseEq}
	Let $\mca$ and $S$ be as in Definition~\ref{def-fusion},
	$\prec^{A_i}$, agent $A_i$'s induced belief state, and
	$\sqsupseteq_S$, fully connected. If \mbox{$A = \fuse(\mca)$},
	then \mbox{$\left(\bigcup_{A_i \in \mca}
	\prec^{A_i}\right)^+$} is $A$'s induced belief state.
\end{prop}

Unfortunately, the equal rank case is special. If we have sources of
different ranks, we generally cannot compute the induced belief state
after fusion using only the agent belief states before fusion, as the
following simple example demonstrates:
\begin{exmp}
	Let \mbox{$\mcw = \{a, b\}$}. Suppose two agents $A_1$ and
	$A_2$ are informed by sources $s_1$ with belief state
	\mbox{$<^{s_1} = \{(a, b)\}$} and $s_2$ with belief state
	\mbox{$<^{s_2} = \{(b, a)\}$}, respectively. $A_1$'s belief
	state is the same as $s_1$'s and $A_2$'s is the same as
	$s_2$'s. If \mbox{$s_1 \sqsupset s_2$}, then the belief state
	induced by \mbox{$\fuse(A_1, A_2)$} is $<^{s_1}$, whereas if
	\mbox{$s_2 \sqsupset s_1$}, then it is $<^{s_2}$.
\end{exmp}
Thus, just knowing the belief states of the fused agents is not
sufficient for computing the induced belief state. We need to maintain
more information about each agent's informants. The question is
whether we can do better than storing all the original sources.

We might wonder whether it is possible to somehow compute a
credibility rank for each agent based on the credibility of her
informant sources, then simply apply $\AGR$ to the agents' induced
belief states. This works fine if, for every pair of agents, all the
informants of one are more credible than those of the other. However,
this does not work in general if each agent can have informants both
more and less credible than those of another agent as the following
example demonstrates:
\begin{exmp}
	Let $\mcw = \{a, b, c\}$. Suppose agent $A_1$ is informed by
	source $s_1$ with belief state $<^{s_1} = \{(a, b), (b, c),
	(a, c)\}$, and suppose agent $A_2$ is informed by sources
	$s_0$ and $s_2$ with belief states $<^{s_0} = \{(c, b), (b,
	a), (c, a)\}$ and $<^{s_2} = \{(b, a), (c, a)\}$,
	respectively. Further suppose that $s_2 \sqsupset s_1
	\sqsupset s_0$. Then $A_1$'s induced belief state is $<^{s_1}$
	and $A_2$'s is $<^{s_0}$. The belief state induced by
	$\fuse(A_1, A_2)$ is $\{(b, c), (c, a), (b, a)\}$. On the
	otherhand, if we rank $A_1$ over $A_2$ and apply $\AGR$ to
	their induced belief states, we get $<^{s_1}$; if we rank
	$A_2$ over $A_1$, we get $<^{s_0}$; and, if we rank them
	equally, we get the fully connected belief state. All of these
	are obviously incorrect.
\end{exmp}

Hence, we need to store more information about the source of each
opinion.  However, we can still do better than keeping the sources
around if sources are totally preordered by credibility. It is enough
to store for each opinion of \mbox{$\AGRRf(S)$} the rank of the highest
ranked source supporting it. We define {\em pedigreed belief states}
which enrich belief states with this additional information:
\begin{defn}\label{def-PBS}
	Let $A$ be an agent informed by a set of sources $S \subseteq
	\mcs$. $A$'s {\em pedigreed belief state} is a pair $(\prec,
	l)$ where $\prec = \AGRRf(S)$ and $l : \prec \to \mcr$ such
	that $l((x,y)) = \max(\{\rank(s) : x <^s y, s \in S\})$. We use
	$\prec^A_r$ to denote the {\em restriction of $A$'s pedigreed
	belief state to $r$}, that is, $\prec^A_r = \{(x,y) \in \prec
	: l((x,y)) = r\}$.
\end{defn}
We verify that a pair's label is, in fact, the rank of the source used
to determine the pair's membership in \mbox{$\AGRRf(S)$}, not that of
some higher ranked source:
\begin{prop}\label{prop-label}
	Let $A$ be an agent informed by a set of sources \mbox{$S
	\subseteq \mcs$} and with pedigreed belief state
	\mbox{$(\prec, l)$}. Then $\prec^A_r$ is the relation
	\begin{displaymath}
		\left\{(x,y) : \exists s \in S.\ x <^s y \wedge r =
		   \rank(s) \wedge \left(\forall s' \in
		   S.\ s' \sqsupset s \implies x \sagnost^{s'}
		   y\right)\right\}.
	\end{displaymath}
\end{prop}
The belief state induced by a pedigreed belief state \mbox{$(\prec,
l)$} is, obviously, the transitive closure of $\prec$.

Now, given only the pedigreed belief states of a set of agents, we can
compute the new pedigreed belief state after fusion. We simply combine
the labeled opinions using our refinement techniques. We call this
operation {\em pedigreed fusion}:
\begin{defn}\label{def-pfusion}
	Let $S$ and $\mca$ be as in Definition~\ref{def-fusion},
	$\sqsupseteq_S$, a total preorder, and \mbox{$\mcp_\mca$}, the
	set of pedigreed belief states of the agents in $\mca$. The
	{\em pedigreed fusion} of \mbox{$\mcp_\mca$}, written
	\mbox{$\pfuse(\mcp_\mca)$}, is \mbox{$(\prec, l)$} where
	\begin{enumerate}

	\item $\prec$ is the relation
	\begin{displaymath}
		\left\{(x,y) :
			\exists A_i \in \mca, r \in \mcr.\ x
				\prec^{A_i}_r y \wedge
			\left(\forall A_j \in \mca, r' \in
				\mcr.\ r' > r \implies x
			        \agnost^{A_j}_{r'} y\right)
		\right\} 
	\end{displaymath}
	over $\mcw$, and

	\item \mbox{$l : \prec \to \mcr$} such that \mbox{$l((x,y)) =
	\max(\{r : x \prec^{A_i}_r y, A_i \in \mca\})$}.

	\end{enumerate}
\end{defn}

\begin{prop}\label{prop-pfusion}
	Let $\mca$, $\mcp_\mca$, $S$, and $\sqsupseteq_S$ be as in
	Definition~\ref{def-pfusion}. Then $\pfuse(\mcp_\mca)$ is the
	pedigreed belief state of \mbox{$\fuse(\mca)$}.
\end{prop}
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:
\begin{prop}\label{prop-strict-pfusion}
	If $\mca$, $\mcp_\mca$, and $S$ are as in
	Definition~\ref{def-pfusion}, $\sqsupseteq_S$ is a total
	order, and\linebreak
	\mbox{$\pfuse(\mcp_\mca) = (\prec, l)$}, then
	\mbox{$\prec^+ = \prec$}.
\end{prop}

Let us return once more to the space robot scenario considered in
Example~\ref{ex-robot} to illustrate pedigreed fusion.
\begin{exmp}\label{ex-robot-fusion}
        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~\ref{ex-robot-AGR}. The
	agents' pedigreed belief states and the result of their fusion
	are shown in Figure~\ref{fig-robot-fusion}.

	\begin{figure}[htb]
	\centerline{\epsfig{file=\path/Figures/robot-fusion.eps,height=2in}}
	\caption{The pedigreed belief states of agent $A_1$
	informed by $s_m$ and $s_t$ and of agent $A_2$ informed by
	$s_p$, and the result of their fusion in
	Example~\ref{ex-robot-fusion}.}\label{fig-robot-fusion}
	\end{figure}

	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~\ref{ex-robot-AGR} 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.
\end{exmp}

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 = \|\mcw\|$, and $m = \|S\|$. Explicitly storing $S$ (along with
the rank of each source) requires \mbox{$O(n^2m)$} amount of
space; this worst case bound is reached when all the sources' belief
states are fully connected relations. On the other hand, storing a
pedigreed belief state only requires \mbox{$O(n^2)$}
space.\footnote{These bounds assume that the amount of space needed to
store each rank is bounded by some small constant.}  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 {\em agents} rather than those of all the sources in
the combined set of informants.

\question{Make more precise time bounds?}
\answer{No, would require a precise algorithm specification.}

Incidentally, if we had used the strawman \mbox{$\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:
\begin{exmp}
	Let $\mcw$, $\mcs$, and $\sqsupseteq$ be as in
	Example~\ref{ex-AGR*}. Suppose agents $A_1$, $A_2$, $A_1'$,
	and $A_2'$ are informed by sets of sources $S_1$, $S_2$,
	$S_1'$, and $S_2'$, respectively, where \mbox{$S_1 = S_2 =
	\{s_2\}$}, \mbox{$S_1' = \{s_0, s_2\}$}, and \mbox{$S_2' =
	\{s_1, s_2\}$}. \mbox{$AGR^*$} dictates that the pedigreed
	belief states of all four agents equal $<^{s_2}$ with all
	opinions annotated with \mbox{$\rank(s_2)$}. In spite of this
	indistinguishability, if \mbox{$A = \fuse(\{A_1, A_2\})$} and
	\mbox{$A' = \fuse(\{A_1', A_2'\})$}, then $A$'s induced belief
	state equals $<^{s_2}$, i.e., \mbox{$\{(a, b), (c, b)\}$},
	whereas $A'$'s is \mbox{$\{(a, b), (c, b), (a, c), (c, a), (a,
	a), (b, b), (c, c)\}$}.
\end{exmp}

Also notice that \citeA{MS01} consider essentially the special case of
fusing two agents informed by strictly-ranked sources. They show the
surprising result that standard AGM belief revision can be modeled as
the fusion of two agents, the informant and the informee, where the
informant's sources are all strictly more credible than the
informee's. Furthermore, they show that, because of its clean
set-theoretic semantics, fusion provides a very attractive,
semantically well-behaved solution to the difficult problem of
iterated belief revision. Our general fusion definition satisfies all
the examples of iterated fusion they describe.


%%%%%%%%%%
% Voting %
%%%%%%%%%%

\section{Incorporating Voting}
%_____________________________

A potential drawback of the framework we have described is it does not
account for ``strength'' of support. For example, we cannot
differentiate between the situation where one thousand sources of the
highest rank support \mbox{$a < b$} and only one source of that rank
supports \mbox{$b < a$}, and the situation where the one source
supports \mbox{$a < b$} and the thousand other sources support
\mbox{$b < a$}. In both cases our framework yields a simple conflict
between $a$ and $b$ rather than acknowledging the overwhelming support
one way or the other. This additional information about strength of
support is often sufficient to resolve what would otherwise have
appeared to be a conflict.

To address this problem, we generalize our framework to incorporate
voting. We first describe a family of aggregation operators based on
voting of which \mbox{$\AGR$} is a special case. In the process, we
introduce a novel modular closure operator. We discuss properties of
special members of this family including indiscriminate aggregation,
simple majority, and unanimity, as well as attractive properties of
the family as a whole. We then describe an extension of our setting to
accommodate ranked individuals so that individuals of higher rank are
given precedence during aggregation. Finally, we consider fusion.

\subsection{Voting Functions}
%----------------------------

We will use a pairwise voting strategy similar to the well-known
Condorcet's method. (For more on the Condorcet method and the other
methods and results from standard voting theory we cite, see
\citeS{Black58} classical reference on voting theory). Condorcet's
method considers each pair of worlds separately, ranking world $x$
over world $y$ in the aggregate if and only if there are more votes
for that ranking than there are for $y$ over $x$. If one world beats
or ties all other worlds, it is known as the {\em Condorcet
winner}. We deviate from this method in that we use a fixed threshold
proportion of support to decide on the acceptance of an opinion in the
aggregate rather than the size of its support relative to that of the
opposite opinion. Let \mbox{$\cnt_S(x, y) = \|\{s\in S : x <^s y\}\|$}
for any $S \subseteq \mcs$.
\begin{defn}\label{def-vt}
	Let \mbox{$S \subseteq \mcs$}. For \mbox{$p \in [0,1]$}, the {\em
	voting function for $p$}, written \mbox{$\vt_p$}, maps $S$ to
	the relation
	\begin{displaymath}
	  \{(x,y) : \cnt_S(x,y) > 0\ \mbox{and}\ \cnt_S(x,y)/\|S\| \geq
	  p\}.
	\end{displaymath}
	%such that \mbox{$(x, y) \in \vt_p(S)$} iff \mbox{$\cnt_S(x, y)
	%> 0$} and \mbox{$\cnt_S(x, y)/\|S\| \geq p$}.
\end{defn}
This definition falls under the class of voting systems \citeA{Black58}
calls {\em 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 {\em
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 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 {\em 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 $\vt_{0.5+\epsilon}(S)$
where $0 < \epsilon < 0.5/\|S\|$ (e.g., $\epsilon = 0.25/\|S\|$) so
that tied opinions are rejected. In general, to only accept opinions
garnering more than $p$ proportion of the vote (for $0 \leq p < 1$), it
suffices to use the function $\vt_{p+\epsilon}(S)$ where
\begin{displaymath}
  0 < \epsilon < \frac{1 - p\|S\| + \lfloor p\|S\|\rfloor}{\|S\|}
\end{displaymath}
e.g., $\epsilon = (1 - p\|S\| + \lfloor
p\|S\|\rfloor)/(2\|S\|)$.\footnote{\mbox{$\lfloor x \rfloor$} denotes
the {\em floor} of $x$, i.e., the largest integer less than or equal
to $x$.}

Second, it is immediately obvious that the aggregate relation may
contain conflicts if $p \leq 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:
\begin{exmp}\label{exmp-Condorcet}
  Let $\mcw = \{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 $\vt_p(S) = \{(a,b), (b,c), (c,a)\}$,
  a cycle, for $1/3 < p \leq 2/3$. This is known as the \em{Condorcet
  paradox} (cf.~\citeS{BF02} voting survey).
\end{exmp}
Many solutions have been proposed for resolving such conflicts --
using {\em Borda counts} or {\em instant runoff voting} (aka {\em
single transferable vote}) (cf.~\citeR{CVDIRV}) 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 {\em indiscriminate}:
\begin{prop}\label{prop-Vt0isUn}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\vt_0(S) = \Un(S)$}.
\end{prop}
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:
\begin{prop}\label{prop-Vt1isIn}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\vt_1(S) =
	\bigcap_{s \in S} <^s$}.
\end{prop}
In contrast to \mbox{$\vt_0$} which generates many conflicts,
\mbox{$\vt_1$} generates a lot of agnosticism.

Fourth, voting functions are opinion-centered; that is, if the
proportion of agnostic sources is larger than $p$, the voting function
for $p$ will not necessarily reflect this agnosticism as it would in
the case of an opinion. If, for example, the belief states of three
sources over $\mcw = \{a,b\}$ are $\{(a,b)\}$, $\{(b,a)\}$, and
$\{\}$, respectively, then the voting function for $p = 1/3$ will
produce a conflict with respect to $a$ and $b$, not agnosticism.
However, this is not to say that abstainers have no impact on the
final result. The fact that abstainers are counted among the total
number of voters has the effect that agnosticism with respect to a
pair of worlds counts as a ``no'' vote for both possible
opinions. This issue usually does not arise in standard voting schemes
because these usually assume that sources totally rank candidates.

%\begin{conj}
%	If \mbox{$p_1, p_2 \in [0,1]$} such that $p_1 \leq
%	p_2$, and \mbox{$S \subseteq \mcs$}, then \mbox{$\vt_{p_1}
%	\subseteq \vt_{p_2}$}.
%\end{conj}

However, the most important observation is that members of the family
of voting operators do not produce belief states in general. As we've
already shown, \mbox{$\vt_0$} produces a modular relation that is not
necessarily transitive. At the other end of the spectrum,
\mbox{$\vt_1$} produces a transitive relation that is not necessarily
modular:
\begin{prop}
	Suppose \mbox{$S \subseteq \mcs$}. \mbox{$\vt_1(S)$} is
	transitive but not necessarily modular.
\end{prop}
For the other members of the family, the result may be neither modular
nor transitive, as the Condorcet paradox in
Example~\ref{exmp-Condorcet} illustrates for $1/3 < p \leq 2/3$. In
fact, we can construct such a scenario for every $0 < p < 1$:
\begin{prop}
	If \mbox{$\|\mcw\| \geq 3$}, then for every \mbox{$p \in
	(0,1)$}, there exists $\mcs$ such that \mbox{$\vt_p(\mcs)$} is
	neither modular nor transitive.
	%, and \mbox{$\vt_p(\mcs)^+$} is not modular.
\end{prop}
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:
%\footnote{If we had, instead, defined
%\mbox{$\vt_p(S)$} such that \mbox{$(x, y) \in \vt_p(S)$} iff
%\mbox{$\cnt_S(x, y) \neq 0$} and
%\begin{displaymath}
%	\frac{\cnt_S(x, y)}{\cnt_S(x, y) + \cnt_S(y, x)} \geq p
%\end{displaymath}
%that is, if we ignored abstainers, then \mbox{$\vt_p(S)^+$} would be
%modular if \mbox{$p < 0.5$}. However, under this definition,
%\mbox{$\vt_1(S)$} is not necessarily equivalent to \mbox{$\AGRIn(S)$}.}.
\begin{exmp}
  Let $\mcw = \{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$, $\vt_p(S) = \vt_p(S)^+ = \{(b,c)\}$ which is not modular.
\end{exmp}

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.

\subsection{Modular-Transitive Closure}
%--------------------------------------

We start by defining a helper function which returns the {\em 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
$\mcw$. For convenience, throughout this modular-transitive closure
subsection we will use $\preceq$ to denote an arbitrary relation,
$\prec$ and $\conflict$ to denote its asymmetric and
symmetric restrictions, respectively.
\begin{defn}\label{def-lev}
	The {\em level} of \mbox{$x \in \mcw$} in a transitive
	relation $\preceq$ over $\mcw$, written
	\mbox{$\lev_\preceq(x)$}, is
	\begin{displaymath}
	  \lev_\preceq(x) =
	    \left\{\begin{array}{l@{\quad}l}
	      0 & \mbox{if}\ x \in \C(\mcw, \preceq) \\
	      1 + \max\limits_{y \in \mcw}\left(\left\{\lev_\preceq(y)
	        : y \prec x\right\}\right) & \mbox{otherwise}.
	    \end{array}\right.
	\end{displaymath}
\end{defn}
(Recall that $\C$ is the choice set function defined in
Definition~\ref{def:choiceset}.) The following simple properties
relating $\preceq$ and $\lev_\preceq$ are immediate:
\begin{prop}\label{prop-lev}
	Suppose $\preceq$ is a transitive relation over $\mcw$ and
	\mbox{$x, y \in \mcw$}.
	\begin{enumerate}

	\item If \mbox{$x \prec y$}, then \mbox{$\lev_\preceq(x) <
	\lev_\preceq(y)$}.

	\item If \mbox{$x \conflict y$}, then \mbox{$\lev_\preceq(x) =
	\lev_\preceq(y)$}.

	\item If \mbox{$\lev_\preceq(x) < \lev_\preceq(y)$}, then
	$\exists z.\ \lev_\preceq(z) = \lev_\preceq(x) \wedge z \prec
	y$.

	\item If \mbox{$\lev_\preceq(x) = \lev_\preceq(y)$}, then
	\mbox{$x \preceq y$} iff \mbox{$y \preceq x$}.

	\end{enumerate}
\end{prop}

We now define the {\em modular closure} of a relation to be the
relation that results from fully connecting all equi-level
alternatives unless they are fully disconnected:
\begin{defn}\label{def-MC}
	The {\em modular closure \mbox{$\MC(\preceq)$}} of a transitive
	relation $\preceq$ over $\mcw$ is the relation such that
	\mbox{$(x, y) \in \MC(\preceq)$} iff
	\begin{enumerate}

	\item \mbox{$\lev_\preceq(x) < \lev_\preceq(y)$} or

	\item \mbox{$\lev_\preceq(x) = \lev_\preceq(y)$} and
	\mbox{$\exists x', y'.\ \lev_\preceq(x') = \lev_\preceq(y') =
	\lev_\preceq(x) \wedge x' \conflict y'$}.

	\end{enumerate}
\end{defn}
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 \citeA{LM92} describe.
%Incidentally, we can define the asymmetric restriction of the modular
%closure using only the first part of the definition:
%\begin{prop}\label{prop-less-prec}
%	If $\preceq$ is a transitive relation over $\mcw$ and
%	\mbox{$\preceq^* = \MC(\preceq)$}, then \mbox{$x \preceq^* y$} and
%       \mbox{$y \not\preceq^* x$} iff \mbox{$\lev_\preceq(x) <
%       \lev_\preceq(y)$} for all \mbox{$x, y \in \mcw$}.
%\end{prop}

We see that \mbox{$\MC$} indeed makes any transitive relation modular
while preserving transitivity:
\begin{prop}\label{prop-MCisBS}
	If $\preceq$ is a transitive relation over $\mcw$, then
	\mbox{$\MC(\preceq) \in \mcb$}.
\end{prop}

\mbox{$\MC$} is an additive process that changes a relation minimally
to achieve modularity while preserving transitivity and the levels of
the worlds:
\begin{prop}\label{prop-MC-add}
	Suppose $\preceq$ is a transitive relation over $\mcw$ and
	\mbox{$\preceq^* = \MC(\preceq)$}.
	\begin{enumerate}

	\item \mbox{$\preceq \subseteq \preceq^*$} and \mbox{$\prec
	\subseteq \prec^*$}.

%Finally, the following propositions show that \mbox{$\MC$} changes a
%relation minimally to achieve modularity. If the relation is already
%modular, the modular closure has no effect, and, in fact, the modular
%closure is the unique smallest modular extension of the relation that
%preserves transitivity and the levels of each world:

	\item If $\preceq$ is modular, then \mbox{$\preceq^* =
	\preceq$}.

	\item \mbox{$\lev_{\preceq^*}(x) = \lev_\preceq(x)$} for all
	\mbox{$x \in \mcw$}.

	\item If $\preceq' \in \mcb$ such that $\preceq \subseteq
	\preceq'$ and $\lev_{\preceq'}(x) = \lev_\preceq(x)$ for all $x
	\in \mcw$, then $\preceq^* \subseteq \preceq'$.

	\end{enumerate}
\end{prop}

%\question{Include the following?}
%
%Note that the modular closure of $\preceq$ is {\em not} necessarily
%the smallest modular extension of $\preceq$ that preserves the
%asymmetric restriction of $\preceq$, as the following counterexample
%illustrates:
%\begin{exmp}
%	Let \mbox{$\mcw = \{a,b\}$}, \mbox{$\preceq = \{(b,b)\}$}, and
%	\mbox{$\preceq' = \{(a,b), (b,b)\}$}. $\preceq$ is transitive,
%	$\preceq'$ is modular (and transitive), \mbox{$\preceq
%	\subseteq \preceq'$} (i.e., $\preceq'$ extends $\preceq$), and
%	\mbox{$\prec \subseteq \prec'$} (i.e., $\prec$ is
%	preserved). However, \mbox{$\preceq' \subset \MC(\preceq)$}
%	since the latter is the full relation.
%\end{exmp}
%However, if the original relation is conflict-free, its modular
%closure will be a minimal modular extension that preserves its
%asymmetric restriction:
%\begin{prop}
%	If $\preceq$ is a transitive, conflict-free relation over
%	$\mcw$, $\preceq'$ is a modular relation over $\mcw$,
%	\mbox{$\preceq \subseteq \preceq'$}, \mbox{$\prec \subseteq
%	\prec'$}, and \mbox{$\preceq' \subseteq \MC(\preceq)$}, then
%	\mbox{$\preceq' = \MC(\preceq)$}.
%\end{prop}
%\begin{pf}
%
%\fix{TO DO}
%
%\qed
%\end{pf}
%Note that this may not be the only such extension, as the following
%example illustrates:
%\begin{exmp}
%	Let \mbox{$\mcw = \{a,b,c,d\}$} and \mbox{$\preceq = \{(a,b),
%	(c,d)\}$}. Then \mbox{$\MC(\preceq)$} is \mbox{$\{(a,b), (a,d),
%	(c,b), (c,d)\}$} which is a minimal modular extension of
%	$\preceq$ that preserves $\prec$. However, \mbox{$\{(a,b),
%	(a,c), (a,d), (b,d), (c,d)\}$} is also a minimal modular
%	extension of $\preceq$ that preserves $\prec$.
%\end{exmp}
%However, any other such minimal modular extension discards level
%information, making it undesirable in our estimation. For the same
%reason, even if the original relation has conflicts so that there are
%modular extensions smaller than the modular closure, the modular
%closure should still be preferred.

We now define the {\em modular, transitive closure} of an arbitrary
relation $\preceq$ as \mbox{$\MC$} applied to the transitive closure of
$\preceq$, and show that the result is a belief state:
\begin{defn}
	The {\em modular, transitive closure \mbox{$\MT(\preceq)$}} of
	a relation $\preceq$ over $\mcw$ is the relation
	\mbox{$\MC\left(\preceq^+\right)$}.
\end{defn}

\begin{prop}\label{prop-MTisBS}
	If $\preceq$ is a relation over $\mcw$, then
	\mbox{$\MT(\preceq) \in \mcb$}.
\end{prop}

\mbox{$\MT$} is also a minimally additive operator:
%First, because both stages of the
%modular, transitive closure only extend the relation, so does the
%operation as a whole:
\begin{prop}\label{prop-MTisMin}
	Suppose $\preceq$ is a relation over $\mcw$ and $\preceq^* =
	\MT(\preceq)$.
	\begin{enumerate}

	\item \mbox{$\preceq \subseteq \preceq^*$}.

%Obviously, if a relation is already transitive, we only need to apply
%the modular closure part of \mbox{$MT$}:

	\item If $\preceq$ is transitive, then \mbox{$\preceq^* =
	\MC(\preceq)$}.

%Similarly, if a relation is already modular, we only need to apply the
%transitive closure part of \mbox{$MT$}:

	\item If $\preceq$ is modular, then \mbox{$\preceq^* =
	\preceq^+$}.

%Thus, taking the closure of a relation that is already modular and
%transitive has no effect:

	\item If $\preceq$ is modular and transitive, then
	\mbox{$\preceq^* = \preceq$}.

%Finally, if a relation contains no conflicts, neither will its
%modular, transitive closure:

	\item If $\preceq$ has no conflicts, then neither does
	\mbox{$\preceq^*$}.

	\end{enumerate}
\end{prop}


\subsection{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
\mbox{$\MT$}:
\begin{defn}
	If \mbox{$S \subseteq \mcs$} and \mbox{$p \in [0,1]$}, then
	\mbox{$\AGREq_p(S) = \MT\left(\vt_p(S)\right)$}.
\end{defn}

\begin{prop}
	If \mbox{$S \subseteq \mcs$} and \mbox{$p \in [0,1]$}, then
	\mbox{$\AGREq_p(S) \in \mcb$}.
\end{prop}

%The special cases of indiscriminate aggregation and unanimity do not
%require the full application of \mbox{$\MT$}: the 
%former only requires the transitive closure part and the latter only
%requires the modular closure part:
%\begin{prop}
%	Suppose \mbox{$S \subseteq \mcs$}.
%	\begin{enumerate}
%
%	\item \mbox{$\AGREq_0(S) = \vt_0(S)^+$}.
%
%	\item \mbox{$\AGREq_1(S) = \MC(\vt_1(S))$}.
%
%	\end{enumerate}
%\end{prop}
%Note that if the original source belief states contain no
%conflicts and we use unanimity, the aggregate belief state
%will be conflict-free as well:
%\begin{prop}
%	If $\prec^s$ contains no conflicts for every \mbox{$s \in S$},
%	then neither does \mbox{$\AGR_1(S)$}.
%\end{prop}

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$:
\begin{defn}
	If \mbox{$S \subseteq \mcs$} and $p \in [0,1]$, then
	\mbox{$\AGRRf_p(S)$} is the relation
	\begin{displaymath}
		\left\{(x, y) : \exists s \in S.\ 
			x <^s y \wedge
			(x,y) \in \vt_p(\{s' \in S : s' \sqeq_S s\})
				\wedge
			\left(\forall s' \in S.\ s' \sqsupset_S s
			        \implies x \sagnost^{s'} y\right)
		\right\}.
	\end{displaymath}
\end{defn}

\begin{defn}
	If \mbox{$S \subseteq \mcs$} and $p \in [0,1]$, then
	\mbox{$\AGR_p(S) = \MT(\AGRRf_p(S))$}.
\end{defn}

\begin{prop}
        If $S \subseteq \mcs$ and $p \in [0,1]$, then $\AGR_p(S) \in
        \mcb$.
\end{prop}
All the aggregation functions we have encountered so far are special
cases of this general family:
\begin{prop}\label{prop-AGRpSpecial}
        Suppose $S \subseteq \mcs$ and $p \in [0,1]$.
	\begin{enumerate}

	\item If $\sqsupseteq_S$ is fully connected, then
	$\AGR_p(S) = \AGREq_p(S)$.

	\item If $\sqsupseteq_S$ is a total order, then $\AGR_p(S) =
	\AGRRf_p(S) = \AGRRf(S) = \AGR(S)$.

	\item $\AGR_0(S) = \AGR(S)$.

	\end{enumerate}

\end{prop}
As an obvious consequence of the last property, $\AGR_0$ satisfies the
modified Arrovian conditions.
\begin{cor}
	Let \mbox{$S = \{s_1, \ldots, s_n\} \subseteq \mcs$} and
	\mbox{$\AGR_f(<^{s_1}, \ldots, <^{s_n}) =
	\AGR_0(S)$}. \mbox{$\AGR_f$} satisfies (the modified versions
	of) restricted range, unrestricted domain, Pareto principle,
	IIA, and non-dictatorship.
\end{cor}
%\question{Include the following?}
%
%In fact, the other members of the $\AGR_p$ family satisfy all the
%modified properties except IIA.
%\begin{prop}
%	Let \mbox{$S = \{s_1, \ldots, s_n\} \subseteq \mcs$}, \mbox{$0
%	< p \leq 1$}, and \mbox{$\AGR_f(<^{s_1}, \ldots, <^{s_n}) =
%	\AGR_p(S)$}. \mbox{$\AGR_f$} satisfies (the modified versions
%	of) restricted range, unrestricted domain, Pareto principle,
%	and non-dictatorship.
%\end{prop}
%
%\question{Consider minimal generalization of IIA to accomodate MC?}
%
%\fix{THE FOLLOWING NOT QUITE RIGHT BECAUSE OF DEPENDENCE ON n.}
%Interestingly, it is easy to show that there are no dictators using
%Arrow's original sense of the word, i.e., no single source's opinions
%will always appear in the aggregate belief state regardless of the
%opinions of the other sources. It is always possible to override any
%given opinion of a particular source by having enough other sources
%not support it. This is also the reason adding voting reduces the
%number of conflicts introduced (or, equivalently, increases the number
%of conflicts resolved) compared to simple AGR.

\question{Other properties (e.g., invariances, behavior of paradoxes,
special cases of \mbox{$p=\frac{1}{2},\frac{2}{3}$} and their
asymmetric restrictions)?}

\subsection{Fusion}
%------------------

Fusion is still defined as in Definition~\ref{def-fusion}, i.e., the
belief state created by fusion of a set of agents is the
aggregate belief state of the agents' cumulative informant
sets. However, we now use \mbox{$\AGR_p$} rather than \mbox{$\AGR$} to
compute the aggregate belief state.

Once again, we want to compute fusion without storing all the belief
states of all the informant sources, if possible. Unfortunately, this
is not possible in general for aggregation functions based on
voting. The reason is we need to keep track of the actual identity of
the sources supporting each opinion so as to avoid ``double-counting''
sources shared by multiple agents.

However, we can often do better than the $O(n^2m)$ space required to
store the full sources, where $n = \|\mcw\|$ and $m$ is the number of
informant sources. We only store those parts that
matter. Specifically, for a given source, we only store those opinions
for which the source is one of the highest ranked supporting an
opinion over the corresponding worlds. We can effectively accomplish
this by extending the pedigreed belief state so that we label each
opinion not only with the rank of the highest ranking sources
supporting an opinion over the corresponding worlds, but also with the
set of unique identifiers for the sources supporting the particular
opinion. We also maintain a table that stores, for each rank
represented in the set of informant sources, the set of identifiers
for all sources at that rank.  We call the resulting representation a
{\em support pedigreed belief state}.
\begin{defn}\label{def-SPBS}
	Let $A$ be an agent informed by a set of sources \mbox{$S
	\subseteq \mcs$}. $A$'s {\em support pedigreed belief state}
	is a triple $(l, \supp, \rtab)$ where
	\begin{itemize}

	\item $l : \mcw \times \mcw \to \mcr \cup \{\clubsuit\}$ such
        that $l(x, y) = \max(\{\rank(s) : x \not\sagnost^s y,\ s \in S\} \cup
        \{\clubsuit\})$ where $\clubsuit \not\in \mcr$ and $\clubsuit
        < r$ for all $r \in \mcr$,

	\item $\supp : \mcw \times \mcw \to 2^S$ such that $\supp(x,
	y) = \{s \in S : \rank(s) = l(x, y),\ x <^s y\}$, and

	\item $\rtab : \ranks(S) \to 2^S$ such that $\rtab(r)= \{s \in
	S : \rank(s) = r\}$.

	\end{itemize}
\end{defn}
Note that $l$ is symmetric: \mbox{$l(x,y) = l(y,x)$}. On the other
hand, $\supp$ is not. Now, we can easily compute an agent's belief
state from its support pedigreed belief state. To compute the
proportion of support for a particular opinion, we simply divide the
size of the support set for that opinion by the number of informant
sources with the labeled rank.
\begin{prop}
 	Let $A$ be an agent informed by a set of sources \mbox{$S
	\subseteq \mcs$}, with support pedigreed belief state
	\mbox{$(l, \supp, \rtab)$}, and using aggregation function
	\mbox{$AGR_p$} for \mbox{$p \in [0, 1]$}. $A$'s belief state
	is the relation
	\begin{displaymath}
	    \MT\left(\left\{(x, y) : \|\supp(x,y)\| > 0\ \mbox{and}\
	      \|\supp(x,y)\|/\|\rtab(l(x,y))\| \geq p\right\}\right)
	\end{displaymath}
\end{prop}
Observe that, unlike with pedigreed belief states, support pedigreed
belief states label {\em 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, \supp, \rtab)$. $l$ requires
$O(n^2)$ space, $\rtab$ requires $\Theta(m)$ space, and, if $r_{\max}$
denotes the number of sources of a rank having the most sources with
that rank, $\supp$ requires $O(n^2r_{\max})$ space, for a total of
$O(n^2r_{\max} + m)$ space.\footnote{As before, we assume representing
ranks requires constant space. We assume that we can represent each
source label with constant space as well.} Thus, in a best-case
scenario where, for example, sources are strictly ranked, a support
pedigreed belief state only requires $O(n^2 + m)$ space since each
opinion has at most one supporter. However, in the worst-case scenario
where, for example, sources are all equally ranked so that $r_{\max} =
m$, we will still need $O(n^2m)$ 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 $\supp$ to
be the union of $\supp$ 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.
\begin{defn}\label{def-spfusion}
	Let $S$ and $\mca$ be as in Definition~\ref{def-fusion},
	$\sqsupseteq_S$, a total preorder, and \mbox{$\mcp_\mca$}, the
	set of support pedigreed belief states of the agents in
	$\mca$. The {\em support pedigreed fusion} of
	\mbox{$\mcp_\mca$}, written \mbox{$\spfuse(\mcp_\mca)$}, is
	\mbox{$(l, \supp, \rtab)$} where
	\begin{enumerate}

	\item \mbox{$l : \prec \to \mcr$} such that $l((x,y)) =
	\max(\{l'(x,y) : (l', \supp', \rtab') \in \mcp_\mca\})$,

	\item \mbox{$\supp : \mcw \times \mcw \to 2^S$} such that
	\begin{displaymath}
	  \supp(x,y) = \bigcup_{(l', \supp', \rtab') \in \mcp_\mca,\
	     l'(x,y) = l(x,y)} \supp'(x,y),
	\end{displaymath}
	and

	\item \mbox{$\rtab : \ranks(S) \to 2^S$} such
	that
	\begin{displaymath}
	  \rtab(r) = \bigcup_{(l', \supp', \rtab') \in \mcp_\mca,\ r \in
	     \mr{range}(\rtab')} \rtab'(r).
	\end{displaymath}

	\end{enumerate}
\end{defn}

\begin{prop}
	Let $\mca$, $\mcp_\mca$, $S$, and $\sqsupseteq_S$ be as in
	Definition~\ref{def-spfusion}. Then $\spfuse(\mcp_\mca)$ is
	the support pedigreed belief state of \mbox{$\fuse(\mca)$}.
\end{prop}

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.

%\comment{THE FOLLOWING ONLY WORKS IF AGENTS HAVE DISJOINT INFORMANT
%SETS!
%
%We need to record how much support each opinion received.
%
%As a first stab, we might consider the simple extension of pedigreed
%belief states in which we store with each opinion in the pedigreed
%belief state the proportion of the highest rank sources agreeing or
%disagreeing with the opinion. This solution has two problems. First,
%we generally cannot compute the proportion of support for an opinion
%after fusion using only the proportions of support from the individual
%agents as the following example illustrates:
%
%\fix{INSERT EXAMPLE}
%
%Second, we need to also record the support for opinions that don't
%appear in the agent's belief state, i.e., the 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 earlier
%votes will become relevant. Again, we illustrate this with an example:
%
%\fix{INSERT EXAMPLE}
%
%Consequently, we enrich pedigreed belief states so that each opinion
%is labeled not only with the rank of the highest ranked sources
%agreeing or disagreeing with the opinion, but also the total number of
%sources at that rank supporting the opinion. Furthermore, we supply
%each agent with a table listing the number of informant sources in
%each rank.
%\begin{defn}\label{def-SPBS}
%	Let $A$ be an agent informed by a set of sources \mbox{$S
%	\subseteq \mcs$}. $A$'s {\em support pedigreed belief state}
%	is a triple $(l, \supp, \rtab)$ where
%	\begin{itemize}
%
%	\item $l : \mcw \times \mcw \to \mcr \cup \{\clubsuit\}$ where
%	$\clubsuit \not\in \mcr$ and $\clubsuit < r \forall r \in \mcr$
%	such that
%	\begin{displaymath}
%	  l(x, y) = \max(\{\rank(s) : x <^s y, s \in S\} \cup
%	     \{\clubsuit\}),
%	\end{displaymath}
%
%	\item $\supp : \mcw \times \mcw \to \mathbb{R}$ such that
%	\begin{displaymath}
%	  \supp(x, y) = \cnt_{S'}(x, y)\ \mbox{where}\ S' = \{s \in S
%	     : \rank(s) = l(x,y)\},
%	\end{displaymath}
%	and
%
%	\item $\rtab : \ranks(S) \to \mathbb{R}^+$ such that
%	\begin{displaymath}
%	  \rtab(r)= \|\{s \in S : \rank(s) = r\}\|.
%	\end{displaymath}
%
%	\end{itemize}
%\end{defn}
%Note that, as a consequence of this definition, there may be
%information recorded in the support pedigreed belief state pertaining
%to ranks not supporting any opinion actually held by the agent.
%%Also, only recording the support size for one opinion
%%between a pair of worlds is insufficient because we allow for
%%conflicts.
%
%We can easily compute an agent's belief state from its support
%pedigreed belief state. To compute the proportion of support for a
%particular opinion, we simply divide the number of recorded votes for
%the opinion by the total number of informant sources with that rank as
%given by the table.
%\begin{prop}
% 	Let $A$ be an agent informed by a set of sources \mbox{$S
%	\subseteq \mcs$}, with support pedigreed belief state
%       \mbox{$(l, \supp, \rtab)$}, and using aggregation function
%	\mbox{$AGR_p$}. $A$'s belief state is the relation
%	\begin{displaymath}
%	    \MT\left(\left\{(x, y) : \supp(x,y) > 0\ \mbox{and}\
%	      \supp(x,y)/\rtab(l(x,y)) \geq p\right\}\right)
%	\end{displaymath}
%\end{prop}
%\begin{pf}
%
%\qed
%\end{pf}
%
%Now, computing the support pedigreed belief state resulting from
%fusion is also straightforward. For each opinion, we set $l$ to be the
%highest $l$ value for that opinion among the agents and set $\supp$ to
%be the sum of the $\supp$ values for that opinion of all agents with
%that $l$ value. And for each rank $r$ represented in some agent's rank
%table, we set $\rtab$ to be the sum of the $\rtab$ values of all
%agents for whom it is defined.
%\begin{defn}\label{def-spfusion}
%	Let $S$ and $\mca$ be as in Definition~\ref{def-fusion},
%	$\sqsupseteq_S$, a total preorder, and \mbox{$\mcp_\mca$}, the
%	set of support pedigreed belief states of the agents in
%	$\mca$. The {\em support pedigreed fusion} of
%	\mbox{$\mcp_\mca$}, written \mbox{$\spfuse(\mcp_\mca)$}, is
%	\mbox{$(l, \supp, \rtab)$} where
%	\begin{enumerate}
%
%	\item \mbox{$l : \prec \to \mcr$} such that
%	\begin{displaymath}
%	  l((x,y)) = \max(\{l'(x,y) : (l', \supp', \rtab') \in
%	     \mcp_\mca\})
%	\end{displaymath}
%
%	\item \mbox{$\supp : \mcw \times \mcw \to \mathbb{R}$} such
%	that
%	\begin{displaymath}
%	  \supp(x,y) = \sum_{(l', \supp', \rtab') \in \mcp_\mca,\
%	     l'(x,y) = l(x,y)} \supp'(x,y)
%	\end{displaymath}
%
%	\item \mbox{$\rtab : \ranks(S) \to \mathbb{R}$} such
%	that
%	\begin{displaymath}
%	  \rtab(r) = \sum_{(l', \supp', \rtab') \in \mcp_\mca,\ r \in
%	     \mr{range}(\rtab')} \rtab'(r).
%	\end{displaymath}
%
%	\end{enumerate}
%\end{defn}
%
%\begin{prop}\label{prop-spfusion}
%	Let $\mca$, $\mcp_\mca$, $S$, and $\sqsupseteq_S$ be as in
%	Definition~\ref{def-spfusion}. Then $\spfuse(\mcp_\mca)$ is
%	the support pedigreed belief state of \mbox{$\fuse(\mca)$}.
%\end{prop}
%\begin{pf}
%
%\qed
%\end{pf}
%
%Let us consider the complexity of this approach. Suppose agent $A$ has
%informant set $S$, $n = \|\mcw\|$, $m = \|S\|$, and $r =
%\|\ranks(S)\|$. $A$'s support pedigreed belief state requires
%$O(n^2\log m + r\log m)$ space; $\log m$ is the worst-case amount of
%space we need to store the size of a subset of $S$.\footnote{As
%before, we assume the storage for any given rank is $O(1)$.} This
%bound is much better than the $O(n^2m)$ space required to store all of
%an agent's sources' belief states, as long as $r = o(n^2m/\log m)$; in
%particular, since $r \leq m$, this bound will be guaranteed if $\log m
%= o(n^2)$. Thus, this approach is ideal for the many real-world
%applications where the number of sources is less than exponential in
%the number of states. Furthermore, we also earn a potentially large
%savings in computation time since, for each pair of worlds, we still
%only need to lookup the agents' labels corresponding to that pair of
%worlds and the associated entries in the rank table rather than
%accessing the opinions of all the sources in the combined set of
%informants.
%}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Related Work and Conclusions %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{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~\ref{subsec-SocialChoice}, recent attempts from
the belief revision community
\cite<e.g.>{BI84,BKMS92,LS95,Makinson97,Revesz97,KP98,Meyer01,BDKP02}
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, \citeauthor{BDKP02} and
\citeauthor{Meyer01} accommodate iterative
merging. \citeauthor{BDKP02}'s proposal is also distinct in that they
approach the problem from a possibilistic logic point of view.
%, and several papers in a special issue of {\it Theoria}
%\cite{Theoria97} which also seek to extend the AGM framework to deal
%with non-prioritized revision.
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. \citeauthor{Meyer01}'s proposal is an exception;
his belief states are {\em epistemic states}, structures in the style
of \citeS{Spohn88} ordinal conditional functions (aka
$\kappa$-rankings). In fact, \citeA{MGC01} have shown that a number of
simple aggregation operators on epistemic belief states {\em 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.

%All the same, it would be interesting to see if we can capture any of
%them in our framework, and if not, why.

\citeS{Cantwell98} 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;
\citeA{Fishburn74} gives a good survey of much of that work.
More recently, researchers in artificial intelligence have taken an
interest in these operators; examples include \citeA{Grosof91},
\citeA{MS01} and \citeA{ARS02}.

\citeauthor{Grosof91} 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 \citeauthor{Grosof91} does not allow for sources of equal
rank, he does allow for sources of {\em incomparable} rank, i.e., the
ranking on sources is a strict {\em 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).

\citeauthor{ARS02}, on the other hand, frame their work in the context
of preference aggregation. They go one step further than
\citeauthor{Grosof91} 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 {\em original}
framework, the relation with the highest priority is {\em 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 \citeauthor{MS01}'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 $\fuse$ 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
-- \citeS{Boutilier96} natural revision, \citeS{DP97} operators,
\citeS{Spohn88} ordinal conditional function revision,
\citeS{Lehmann95} widening rank model revision, and \citeS{Williams94}
conditionalization and adjustment operators. They show that $\fuse$
is the only operator among them that is semantically well-behaved: the
results of all the other operators depend on the order of iteration.

Finally, to our knowledge, none of these related approaches outside of
social choice have yet been extended to incorporate voting.


\section{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 \mbox{$\Bel$}, \mbox{$\Agn$}, and
\mbox{$\Con$} operators and how they interrelate.

\section*{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 {\em 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\'{e}l\`{e}ne
Alfassa Fund for Research in Artificial Intelligence.

%\newpage


%%%%%%%%%%%%%%
% Appendices %
%%%%%%%%%%%%%%

\begin{appendix}

%%%%%%%%%%
% Proofs %
%%%%%%%%%%

\section{Proofs}
%	 ______

\setcounter{prop}{0}

%%% Preliminaries %%%

\begin{prop}\hspace{0ex}\\[-0.5cm]
	\begin{enumerate}

	\item The transitive closure of a modular relation is
	modular.

	\item Every transitive relation is quasi-transitive.

	\item \cite{Sen86} Every quasi-transitive relation is
	acyclic.

	\end{enumerate}
\end{prop}
\begin{pf}\hspace{0ex}\\[-0.5cm]
\begin{enumerate}

\item Suppose a relation $\leq$ over finite set $\Omega$ is modular,
and $\leq^+$ is the transitive closure of $\leq$. Suppose \mbox{$x, y,
z \in \Omega$} and \mbox{$x \leq^+ y$}. Then there exist \mbox{$w_0,
\ldots, w_n$} such that \mbox{$x = w_0 \leq \cdots \leq w_n =
y$}. Since $\leq$ is modular and \mbox{$w_0 \leq w_1$}, either
\mbox{$w_0 \leq z$} or \mbox{$z \leq w_1$}. In the former case,
\mbox{$x = w_0 \leq z$}, so \mbox{$x \leq^+ z$}. In the latter case,
\mbox{$z \leq w_1 \leq \cdots w_n = y$}, so \mbox{$z \leq^+ y$}.

\item Suppose $\Omega$ is a finite set, \mbox{$x, y, z \in \Omega$},
$\leq$ is a transitive relation over $\Omega$, and $<$ is its
asymmetric restriction. Suppose \mbox{$x < y$} and \mbox{$y <
z$}. Then \mbox{$x \leq y$}, \mbox{$y \not\leq x$}, \mbox{$y \leq z$},
and \mbox{$z \not\leq y$}. \mbox{$x \leq y$} and \mbox{$y \leq z$}
imply \mbox{$x \leq z$}, and \mbox{$y \leq z$} and \mbox{$y \not\leq
x$} imply \mbox{$z \not\leq x$}, both by transitivity. So \mbox{$x <
z$}.

\end{enumerate}
\qed
\end{pf}

\begin{prop}
	\cite{Sen86} Given a relation $\leq$ over a finite set
	$\Omega$, the choice set operation $\C$ defines a choice
	function iff $\leq$ is acyclic.
\end{prop}
\begin{pf}
See \citeS{Sen86} proof.
\qed
\end{pf}


%%% Representating Collective Beliefs %%%

\begin{prop}
	\cite{Arrow63} There is no aggregation operator that satisfies
	restricted range, unrestricted domain, (weak) Pareto
	principle, independendence of irrelevant alternatives, and
	nondictatorship.
\end{prop}
\begin{pf}
See \citeS{Arrow63} proof.
\qed
\end{pf}

\begin{prop}
	Let $\preceq$ be a relation over a finite set $\Omega$ and let
	$\agnost$ be its symmetric restriction. If $\preceq$ is total
	and quasi-transitive but not transitive, then $\agnost$ is not
	transitive.
\end{prop}
\begin{pf}
Let $\preceq$ be a total, quasi-transitive, non-transitive
relation.
%UNNECESSARY - pumz 2003.05.20
%First, such a relation exits: if \mbox{$\Omega = \{a, b,
%c\}$}, it is easily verified that the relation \mbox{$\Omega \times
%\Omega \setminus \{(b,a)\}$} is total, quasi-transitive, but not
%transitive.
%
Suppose \mbox{$x \preceq y$} and \mbox{$y \preceq z$} but \mbox{$x
\not\preceq z$}. By totality, \mbox{$z \preceq x$}, so \mbox{$z \prec
x$}. If \mbox{$x \prec y$}, then \mbox{$z \prec y$} by
quasi-transitivity, a contradiction. Thus, \mbox{$x \agnost
y$}. Similarly, if \mbox{$y \prec z$}, then \mbox{$y \prec x$}, a
contradiction, so \mbox{$y \agnost z$}. But \mbox{$z \prec x$}, so
\mbox{$x \not\agnost z$}. Therefore, $\agnost$ is not transitive.
\qed
\end{pf}

\begin{prop}
	Suppose a relation $\prec$ is transitive and $\agnost$ is the
	corresponding agnosticism relation. Then $\agnost$ is
	transitive iff $\prec$ is modular.
\end{prop}
\begin{pf}
Suppose $\agnost$ is transitive and suppose \mbox{$x \prec z$},
\mbox{$x, y, z \in \mcw$}. We prove by contradiction: Suppose \mbox{$x
\not\prec y$} and \mbox{$y \not\prec z$}. By transitivity, \mbox{$z
\not\prec y$} and \mbox{$y \not\prec x$}, so \mbox{$x \agnost y$} and
\mbox{$y \agnost z$}. By assumption, \mbox{$x \agnost z$}, so \mbox{$x
\not\prec z$}, a contradiction.

Suppose, instead, $\prec$ is modular and suppose \mbox{$x \agnost y$}
and \mbox{$y \agnost z$}, \mbox{$x, y, z \in \mcw$}. Then \mbox{$x
\not\prec y$}, \mbox{$y \not\prec x$}, \mbox{$y \not\prec z$}, and
\mbox{$z \not\prec y$}. By modularity, \mbox{$x \not\prec z$} and
\mbox{$z \not\prec x$}, so \mbox{$x \agnost z$}.
\qed
\end{pf}

\begin{prop}
	$\mcst \subset \mcb$ and is the set of irreflexive relations
	in $\mcb$.
\end{prop}
%\begin{prop}
%	The set of irreflexive relations in $\mcb$ is isomorphic to
%	$\mct$ and, in fact, equals $\mcst$.
%\end{prop}
\begin{pf}
Let \mbox{$x, y, z \in \mcw$}. We first show that \mbox{$\mcst \subset
\mcb$}. Let \mbox{$\prec \in \mcst$}. Then there exists \mbox{$\preceq
\in \mct$} such that $\prec$ is the asymmetric restriction of
$\preceq$. By definition, $\preceq$ is transitive, so by
Proposition~\ref{prop-Props}, so is $\prec$. Suppose \mbox{$x \prec
y$}. Then \mbox{$x \preceq y$} and \mbox{$y \not\preceq x$}. Since
$\preceq$ is total, \mbox{$x \preceq z$} or \mbox{$z \preceq
x$}. Suppose \mbox{$x \preceq z$}. If \mbox{$y \preceq z$}, then
\mbox{$z \not\preceq x$} (otherwise \mbox{$y \preceq x$} by
transitivity, a contradiction), so \mbox{$x \prec z$}.  And if, on the
other hand, \mbox{$y \not\preceq z$}, then \mbox{$z \preceq y$} by
totality, so \mbox{$z \prec y$}. Suppose, instead, \mbox{$z \preceq
x$}. Then \mbox{$z \preceq y$} by transitivity and \mbox{$y
\not\preceq z$} (otherwise \mbox{$y \preceq x$} by transitivity, a
contradiction), so \mbox{$z \prec y$}. Thus, \mbox{$x \prec z$} or
\mbox{$z \prec y$}, so $\prec$ is modular.

Now we show that \mbox{$\prec \in \mcb$} is in $\mcst$ if and only if
it is irreflexive. If \mbox{$\prec \in \mcst$}, it is asymmetric, so
it is irreflexive. Suppose, instead, $\prec$ is irreflexive. We define
a relationship $\preceq$, show that $\prec$ is its asymmetric
restriction, and show that $\preceq$ is in $\mct$. Let $\preceq$ be
defined as \mbox{$x \preceq y$} iff \mbox{$y \not\prec x$}. We first
show that $\prec$ is the asymmetric restriction of $\preceq$. Suppose
$\prec'$ is the asymmetric restriction of $\preceq$. If \mbox{$x
\prec' y$}, then \mbox{$x \preceq y$} and \mbox{$y \not\preceq x$}, so
\mbox{$x \prec y$}. If, instead, \mbox{$x \prec y$}, then \mbox{$y
\not\preceq x$}. By totality, \mbox{$x \preceq y$}, so \mbox{$x \prec'
y$}.  We next show that \mbox{$\preceq \in \mct$}. If \mbox{$x
\not\prec y$} then \mbox{$y \preceq x$}. Otherwise, \mbox{$x \prec
y$}. But since $\prec$ is irreflexive, \mbox{$y \not\prec x$}
(otherwise \mbox{$x \prec x$} by transitivity), so \mbox{$x \preceq
y$} and $\preceq$ is total.  Next, suppose \mbox{$x \preceq y$} and
\mbox{$y \preceq z$}. Then \mbox{$y \not\prec x$} and \mbox{$z
\not\prec y$}. By modularity, \mbox{$z \not\prec x$}, so \mbox{$x
\preceq z$}, and, thus $\preceq$ is transitive.  \qed
\end{pf}

\begin{prop}
	\mbox{$\prec \in \mcb$} iff there is a partition
	\mbox{$\mathbf{W} = \langle W_0, \ldots, W_n \rangle$} of
	$\mcw$ such that:
	\begin{enumerate}

	\item For every \mbox{$x \in W_i$} and \mbox{$y \in W_j$},
	\mbox{$i \neq j$} implies \mbox{$i < j$} iff \mbox{$x \prec
	y$}.

	\item Every $W_i$ is either fully connected (\mbox{$w \prec
	w'$} for all \mbox{$w, w' \in W_i$}) or fully disconnected
	(\mbox{$w \not\prec w'$} for all \mbox{$w, w' \in W_i$}).

	\end{enumerate}
\end{prop}
\begin{pf}
We refer to the conditions in the proposition as conditions~1 and 2,
respectively. We prove each direction of the proposition separately.

$(\Longrightarrow)$ Suppose \mbox{$\prec \in \mcb$}, that is, $\prec$
is a modular and transitive relation over $\mcw$. We use a series of
definitions and lemmas to show that a partition of $\mcw$ exists
satisfying conditions~1 and 2. We first define an equivalence relation
by which we will partition $\mcw$. Two elements will be equivalent if
they ``look the same'' from the perspective of every element of
$\mcw$:
\begin{defn}
	\mbox{$x \equiv y$} iff for every \mbox{$z \in \mcw$},
	\mbox{$x \prec z$} iff \mbox{$y \prec z$} and \mbox{$z \prec
	x$} iff \mbox{$z \prec y$}.
\end{defn}

\begin{lem}
	$\equiv$ is an equivalence relation over $\mcw$.
\end{lem}
\begin{pf}
Suppose \mbox{$x \in \mcw$}. For every \mbox{$z \in \mcw$}, \mbox{$x
\prec z$} iff \mbox{$x \prec z$} and \mbox{$z \prec x$} iff \mbox{$z
\prec x$}, so \mbox{$x \equiv x$}. Therefore, $\equiv$ is reflexive.

Suppose \mbox{$x, y \in \mcw$} and \mbox{$x \equiv y$}. Then for every
\mbox{$z \in \mcw$}, \mbox{$x \prec z$} iff \mbox{$y \prec z$} and
\mbox{$z \prec x$} iff \mbox{$z \prec y$}. But then for every \mbox{$z
\in \mcw$}, \mbox{$y \prec z$} iff \mbox{$x \prec z$} and \mbox{$z
\prec y$} iff \mbox{$z \prec x$}. Therefore, \mbox{$y \equiv x$}, so
$\equiv$ is symmetric.

Suppose \mbox{$x, y, z \in \mcw$}, \mbox{$x \equiv y$}, and \mbox{$y
\equiv z$}. Suppose further that \mbox{$w \in \mcw$}. By definition of
$\equiv$, \mbox{$x \prec w$} iff \mbox{$y \prec w$} and \mbox{$w \prec
x$} iff \mbox{$w \prec y$}, and \mbox{$y \prec w$} iff \mbox{$z \prec
w$} and \mbox{$w \prec y$} iff \mbox{$w \prec z$}. Therefore, \mbox{$x
\prec w$} iff \mbox{$z \prec w$} and \mbox{$w \prec x$} iff \mbox{$w
\prec z$}. Since $w$ is arbitrary, \mbox{$x \equiv z$}, so $\equiv$ is
transitive.
\qed
\end{pf}
$\equiv$ partitions $\mcw$ into its equivalence classes. We use
\mbox{$[w]$} to denote the equivalence class containing $w$, that is,
the set \mbox{$\{w' \in \mcw : w \equiv w'\}$}. Observe that two
worlds in conflict always appear in the same equivalence class:
\begin{lem}\label{lem-conflict-is-equiv}
	If \mbox{$x, y \in \mcw$} and \mbox{$x \conflict y$}, then
	\mbox{$[x] = [y]$}.
\end{lem}
\begin{pf}
Suppose \mbox{$x, y \in \mcw$} and \mbox{$x \conflict y$}. Since
\mbox{$[x]$} is an equivalence class, it suffices to show that
\mbox{$y \in [x]$}, that is, \mbox{$x \equiv y$}. Suppose \mbox{$z \in
\mcw$}. By transitivity, if \mbox{$x \prec z$}, then \mbox{$y \prec
z$}; if \mbox{$y \prec z$}, then \mbox{$x \prec z$}; if \mbox{$z \prec
x$}, then \mbox{$z \prec y$}; and, if \mbox{$z \prec y$} then \mbox{$z
\prec x$}. Thus, \mbox{$x \prec z$} iff \mbox{$y \prec z$} and
\mbox{$z \prec x$} iff \mbox{$z \prec y$}, and since $z$ is arbitrary,
\mbox{$x \equiv y$}.
\qed
\end{pf}

We now define a total order over these equivalence classes:
\begin{defn}
	For all \mbox{$x, y \in \mcw$}, \mbox{$[x] \leq [y]$} iff
	\mbox{$[x] = [y]$} or \mbox{$x \prec y$}.
\end{defn}

\begin{lem}
	$\leq$ is well-defined, that is, if \mbox{$x \equiv x'$} and
	\mbox{$y \equiv y'$}, then \mbox{$x \prec y$} iff \mbox{$x'
	\prec y'$}, for all $x, x', y, y' \in \mcw$.
\end{lem}
\begin{pf}
Suppose \mbox{$x \equiv x'$} and \mbox{$y \equiv y'$}, \mbox{$x, x',
y, y' \in \mcw$}. By the definition of $\equiv$, for every \mbox{$z
\in \mcw$}, \mbox{$x \prec z$} iff \mbox{$x' \prec z$}. In particular,
\mbox{$x \prec y$} iff \mbox{$x' \prec y$}. Also by the definition of
$\equiv$, for every \mbox{$z' \in \mcw$}, \mbox{$z' \prec y$} iff
\mbox{$z' \prec y'$}. In particular, \mbox{$x' \prec y$} iff \mbox{$x'
\prec y'$}. Therefore, \mbox{$x \prec y$} iff \mbox{$x' \prec y'$}.
\qed
\end{pf}

\begin{lem}
	$\leq$ is a total order over the equivalence classes of $\mcw$
	defined by $\equiv$.
\end{lem}
\begin{pf}
Suppose \mbox{$x, y, z \in \mcw$}. We first show that $\leq$ is
total. By definition of $\leq$, if \mbox{$x \prec y$} or \mbox{$y
\prec x$}, then \mbox{$[x] \leq [y]$} or \mbox{$[y] \leq [x]$},
respectively. Suppose \mbox{$x \not\prec y$} and \mbox{$y \not\prec
x$}, and suppose \mbox{$z \in \mcw$}. By modularity of $\prec$,
\mbox{$x \prec z$} implies \mbox{$y \prec z$}, \mbox{$y \prec z$}
implies \mbox{$x \prec z$}, \mbox{$z \prec x$} implies \mbox{$z \prec
y$}, and \mbox{$z \prec y$} implies \mbox{$z \prec x$}, so \mbox{$x
\equiv y$}. Therefore, \mbox{$[x] = [y]$}, so \mbox{$[x] \leq [y]$} by
the definition of $\leq$.

Next, we show that $\leq$ is anti-symmetric. Suppose \mbox{$[x] \leq
[y]$} and \mbox{$[y] \leq [x]$}. Then \mbox{$[x] = [y]$} or \mbox{$x
\prec y$} and \mbox{$y \prec x$}. In the former case we are done, in
the latter, the result follows from Lemma~\ref{lem-conflict-is-equiv}.

Finally, we show that $\leq$ is transitive. Suppose \mbox{$[x] \leq
[y]$} and \mbox{$[y] \leq [z]$}. Obviously, if \mbox{$[x] = [y]$} or
\mbox{$[y] = [z]$}, then \mbox{$[x] \leq [z]$}. Suppose not. Then
\mbox{$x \prec y$} and \mbox{$y \prec z$}, so \mbox{$x \prec z$} by
the transitivity of $\prec$. Therefore, \mbox{$[x] \leq [y]$} by the
definition of $\leq$.
\qed
\end{pf}

We name the members of the partition \mbox{$W_0, \ldots, W_n$} such
that \mbox{$W_i \leq W_j$} iff \mbox{$i \leq 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 \mbox{$x \in W_i$}, \mbox{$y \in W_j$}, and
\mbox{$i \neq j$}. We want to show that \mbox{$i < j$} iff \mbox{$x
\prec y$}. Since \mbox{$i \neq j$}, \mbox{$[x] \neq [y]$}. Suppose
\mbox{$i < j$}. Then \mbox{$i \leq j$}, so \mbox{$[x] \leq
[y]$}. Since \mbox{$[x] \neq [y]$}, \mbox{$x \prec y$} by the
definition of $\leq$. Now suppose, instead, that \mbox{$x \prec
y$}. Then \mbox{$[x] \leq [y]$} by the definition of $\leq$, so
\mbox{$i \leq j$}. Since \mbox{$[x] \neq [y]$}, \mbox{$y \not\prec x$}
by Lemma~\ref{lem-conflict-is-equiv}. Since \mbox{$[x] \neq [y]$} and
\mbox{$y \not\prec x$}, \mbox{$[y] \not\leq [x]$} by the definition
of $\leq$, so \mbox{$j \not\leq i$}. Thus, \mbox{$i < j$}.

Finally, we show that each $W_i$ is either fully connected or fully
disconnected. Suppose \mbox{$x, y, z \in W_i$} so that \mbox{$x \equiv
y \equiv z$}. It suffices to show that \mbox{$x \prec x$} iff \mbox{$y
\prec z$}. By the definition of $\equiv$, \mbox{$x \prec x$} iff
\mbox{$y \prec x$}, and \mbox{$x \prec x$} iff \mbox{$x \prec
z$}. Suppose \mbox{$x \prec x$}. Then, \mbox{$y \prec x$} and \mbox{$x
\prec z$}, so \mbox{$y \prec z$} by transitivity of $\prec$.  Suppose
now, \mbox{$x \not\prec x$}.  Then, \mbox{$y \not\prec x$} and
\mbox{$x \not\prec z$}, so \mbox{$y \not\prec z$} by modularity of
$\prec$.

$(\Longleftarrow)$ Suppose \mbox{$\mathbf{W} = \langle W_0, \ldots,
W_n \rangle$} is a partition of $\mcw$ and $\prec$ is a relation over
$\mcw$ satisfying the given conditions. We want to show that $\prec$
is modular and transitive. We first give the following lemma:
\begin{lem}\label{lem-prec-imp-leq}
	Suppose $\mathbf{W}$ is a partition of $\mcw$ and $\prec$ is a
	relation over $\mcw$ satisfying condition~1. If \mbox{$W_i,
	W_j \in \mathbf{W}$}, \mbox{$x \in W_i$}, \mbox{$y \in W_j$},
	and \mbox{$x \prec y$}, then \mbox{$i \leq j$}.
\end{lem}
\begin{pf}
If \mbox{$i = j$}, we're done. Suppose \mbox{$i \neq j$}. Then, since
\mbox{$x \prec y$}, \mbox{$i < j$} by condition~1.
\qed
\end{pf}

We now show $\prec$ is modular. Suppose \mbox{$x \in W_i$}, \mbox{$y
\in W_j$}, and \mbox{$x \prec y$}. Then \mbox{$i \leq j$} by
Lemma~\ref{lem-prec-imp-leq}. Suppose \mbox{$z \in W_k$}. Then
\mbox{$i \leq k$} or \mbox{$k \leq j$} by the modularity of
$\leq$. Suppose \mbox{$i < k$} or \mbox{$k < j$}. Then \mbox{$x \prec
z$} or \mbox{$z \prec y$} by condition~1. Otherwise \mbox{$i = k =
j$}, so \mbox{$x, y, z \in W_i$}. Since \mbox{$x \prec y$}, $W_i$ is
fully connected by condition~2, so \mbox{$x \prec z$} (and \mbox{$z
\prec y$}).

Finally, we show that $\prec$ is transitive. Suppose \mbox{$x \in
W_i$}, \mbox{$y \in W_j$}, \mbox{$z \in W_k$}, \mbox{$x \prec y$}, and
\mbox{$y \prec z$}. By Lemma~\ref{lem-prec-imp-leq}, \mbox{$i \leq j$}
and \mbox{$j \leq k$}, so \mbox{$i \leq k$} by the transitivity of
$\leq$. Suppose \mbox{$i < k$}. Then \mbox{$x \prec z$} by
condition~1. Otherwise \mbox{$i = k = j$}, so \mbox{$x, y, z \in
W_i$}. Since \mbox{$x \prec y$}, $W_i$ is fully connected by
condition~2, so \mbox{$x \prec z$}.
\qed
\end{pf}
(END OF PROPOSITION~\ref{prop-rep} PROOF)


\begin{prop}
	\mbox{$\mct \subset \mcb$} and is the set of reflexive
	relations in $\mcb$.
\end{prop}
\begin{pf}
We first show that \mbox{$\mct \subset \mcb$}. Let \mbox{$\preceq \in
\mct$} and \mbox{$x, y, z \in \mcw$}. By definition, $\preceq$ is
transitive. Suppose \mbox{$x \preceq y$}. Since $\preceq$ is total,
\mbox{$x \preceq z$} or \mbox{$z \preceq x$}. If \mbox{$z \preceq x$},
then \mbox{$z \preceq y$} by transitivity, so $\preceq$ is modular.
On the other hand, the empty relation over $\mcw$ is modular and
transitive, but not total and, consequently, not in $\mct$.

Now we show that \mbox{$\prec \in \mcb$} is in $\mct$ if and only if
it is reflexive. If \mbox{$\prec \in \mct$}, it is total, so it is
reflexive. If, instead, $\prec$ is reflexive, then \mbox{$x \prec x$}
so, by modularity, \mbox{$x \prec y$} or \mbox{$y \prec x$}. Thus,
$\prec$ is total. And, since \mbox{$\prec \in \mcb$}, it is
transitive.
\qed
\end{pf}

\begin{prop}\hspace{0ex}\\[-0.5cm]
	\begin{enumerate}

	\item \mbox{$\mcq \cap \mcb = \mct$}.

	\item \mbox{$\mcb \not\subseteq \mcq$}.

	\item \mbox{$\mcq \not\subseteq \mcb$} if $\mcw$ has at least
	three elements.

	\item \mbox{$\mcq \subset \mcb$} if $\mcw$ has one or two
	elements.

	\end{enumerate}
\end{prop}
\begin{pf}\hspace{0ex}\\[-0.5cm]
\begin{enumerate}

\item Suppose \mbox{$\preceq \in \mcq \cap \mcb$}. Then $\preceq$ is
total and transitive and, hence, in $\mct$. Suppose \mbox{$\preceq \in
\mct$}. By definition, $\preceq$ is total. Also by definition, it is
transitive, so by Proposition~\ref{prop-Props}, it is quasi-transitive
and, thus, in $\mcq$. By Proposition~\ref{prop-TPsubMT},
\mbox{$\preceq \in \mcb$} and, so, in \mbox{$\mcq \cap \mcb$}.

\item The empty relation is modular and transitive, but not total and,
so, not in $\mcq$.

\item Suppose $a$ and $b$ are distinct elements of $\mcw$. The
relation \mbox{$\mcw \times \mcw \setminus \{(b,a)\}$} is total, and, since
the asymmetric restriction is \mbox{$\{(a,b)\}$} which is transitive, it is also
quasi-transitive. However, if there are at least three elements in
$\mcw$, it is not transitive and, so, not in $\mcb$.

\item Suppose $\mcw$ has one element. Then $\mcb$ contains both
possible relations over $\mcw$, whereas $\mcq$ contains only the
fully connected relation over $\mcw$.

Suppose $\mcw$ has two elements $a$ and $b$. Then $\mcb$ contains the
empty relation, the fully connected relation, and all the remaining
eight relations which contain either \mbox{$(a,b)$} or \mbox{$(b,a)$},
but not both.  $\mcq$, on the other hand, only contains the three
reflexive relations containing either \mbox{$(a,b)$} or
\mbox{$(b,a)$}.

\end{enumerate}
\qed
\end{pf}

\begin{prop}\hspace{0ex}\\[-0.5cm]
	\begin{enumerate}

	\item \mbox{$\mcsq \cap \mcb = \mcst$}.

	\item \mbox{$\mcb \not\subseteq \mcsq$}.

	\item \mbox{$\mcsq \not\subseteq \mcb$} if $\mcw$ has at least
	three elements.

	\item \mbox{$\mcsq \subset \mcb$} if $\mcw$ has one or two
	elements.

	\end{enumerate}
\end{prop}
\begin{pf}\hspace{0ex}\\[-0.5cm]
\begin{enumerate}

\item Suppose \mbox{$\prec \in \mcsq \cap \mcb$}. Since $\prec \in
\mcsq$, it is irreflexive, so since it is in $\mcb$, it is in $\mcst$
by Proposition~\ref{prop-TPisoMTI}.  Suppose, instead, \mbox{$\prec
\in \mcst$}. By Proposition~\ref{prop-TPisoMTI}, \mbox{$\prec \in
\mcb$}. Let \mbox{$\preceq \in \mct$} be a relation such that $\prec$
is its asymmetric restriction. (Obviously such a relation must exist.)  From
Proposition~\ref{prop-MTandTQ}, \mbox{$\preceq \in \mcq$}, so
\mbox{$\prec \in \mcsq$}. Thus, \mbox{$\prec \in \mcsq \cap \mcb$}.

\item The fully connected relation over $\mcw$ is in $\mcb$, but not
asymmetric and, so, not in $\mcsq$.

\item Suppose $a$ and $b$ are distinct elements of $\mcw$. If $\mcw$
has at least three elements, the relation \mbox{$\{(a,b)\}$} is not
modular and, thus, not in $\mcb$, yet it is the asymmetric restriction of the
relation \mbox{$\mcw \times \mcw \setminus \{(b,a)\}$} which is total
and quasi-transitive (since \mbox{$\{(a,b)\}$} is transitive).

\item Suppose $\mcw$ has one element. Then $\mcb$ contains both
possible relations over $\mcw$, whereas $\mcsq$ contains only the empty
relation over $\mcw$.

Suppose $\mcw$ has two elements $a$ and $b$. Then $\mcb$ contains the
empty relation, the fully connected relation, and all eight of the
remaining relations which contain either \mbox{$(a,b)$} or
\mbox{$(b,a)$}, but not both. $\mcsq$, on the other hand, only
contains the three irreflexive relations.

\end{enumerate}
\qed
\end{pf}


%%% Single-Agent Belief State Construction %%%

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\Un(S)$} is modular
	but not necessarily transitive.
\end{prop}
\begin{pf}
Let \mbox{$\prec = \Un(S)$}. Suppose \mbox{$x, y, z \in \mcw$} and
\mbox{$x \prec y$}. Then there is some \mbox{$s \in S$} such that
\mbox{$x <^s y$}. By assumption, $<^s$ is modular, so \mbox{$x <^s z$}
or \mbox{$z <^s y$}. By the definition of \mbox{$\Un(S)$}, \mbox{$x
\prec z$} or \mbox{$z \prec y$}, so $\prec$ is modular.

Suppose \mbox{$a, b, c \in \mcw$} and \mbox{$S = \{s_1, s_2\}$} such
that \mbox{$<^{s_1} = \{(a,b), (a,c)\}$} and\linebreak
\mbox{$<^{s_2} = \{(b,a), (c,a)\}$}. \mbox{$\Un(S)$} is not transitive.
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGRUn(S) \in \mcb$}.
\end{prop}
\begin{pf}
The transitive closure of any relation is transitive. Since
\mbox{$\Un(S)$} is modular, the transitive closure of \mbox{$\Un(S)$} is
also modular by Proposition~\ref{prop-Props}.
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGRRf(S)$} is modular
	but not necessarily transitive.
\end{prop}
\begin{pf}
We first prove modularity. Suppose $x, y, z \in \mcw$ and $(x,y) \in
\AGRRf(S)$. Then there exists $s \in S$ such that $x <^s y$ and for
all $s' \sqsupset_S s \in S$, $x \sagnost^{s'} y$. By modularity of
$<^s$, either $x <^s z$ or $z <^s y$. Since $S$ is finite, this
implies that either there exists $s' \in S$ such that $x <^{s'} z$ and
for all $s'' \sqsupset_S s' \in S$, $x \sagnost^{s''} z$, or there exists
$s' \in S$ such that $y <^{s'} z$ and for all $s'' \sqsupset_S s' \in S$,
$y \sagnost^{s''} z$. Thus, $(x,z) \in \AGRRf(S)$ or $(z,y) \in
\AGRRf(S)$, so $\AGRRf(S)$ is modular.

Suppose $\mcw = \{x, y, z\}$ and $S = \{s_1, s_2\}$ such that $s_1 =
\{(x,y), (z,y)\}$, $s_2 = \{(y,x), (y,z)\}$, and $s_1 \sqeq_S
s_2$. Then $\AGRRf(S) = \{(x,y), (z,y), (y,x), (y,z)\}$ which is not
transitive.
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$} and $\sqsupseteq_S$ is a total
	order, then \mbox{$\AGRRf(S) \in \mcb$}.
\end{prop}
\begin{pf}
We've already proven in Proposition~\ref{prop-AGRRfModnotT} that
$\AGRRf(S)$ is modular. Let\linebreak
\mbox{$\prec = \AGRRf(S)$} and suppose \mbox{$x,y,z \in \mcw$}.
%THE FOLLOWING HAS BEEN SUBSUMED
%We first prove that \mbox{$\AGRRf(S)$} is modular. Note that the proof
%does not depend on $\sqsupseteq_S$ being a total order.
%\begin{lem}\label{lem-AGRRfMod}
%	If \mbox{$S \subseteq \mcs$}, then \mbox{$AGRRf(S)$} is
%	modular.
%\end{lem}
%\begin{pf}
%Let \mbox{$\prec = \AGRRf(S)$}. Suppose \mbox{$x, y, z \in \mcw$} and
%\mbox{$x \prec y$}. Then there exists \mbox{$s \in S$} such that
%\mbox{$x <^s y$} and, for every \mbox{$s' \in S$}, \mbox{$s' \sqsupset_S
%s$} implies \mbox{$x \not<^{s'} y$} and \mbox{$y \not<^{s'}
%x$}. Consider a source $s'$ such that \mbox{$x <^{s'} z$}, \mbox{$z
%<^{s'} x$}, \mbox{$y <^{s'} z$}, or \mbox{$z <^{s'} y$} and, for every
%\mbox{$s'' \in S$}, \mbox{$s'' \sqsupset_S s'$} implies \mbox{$x
%\not<^{s''} z$}, \mbox{$z \not<^{s''} x$}, \mbox{$y \not<^{s''} z$},
%and \mbox{$z \not<^{s''} y$}. We know such a source exists since, by
%modularity, \mbox{$x <^s z$} or \mbox{$z <^s y$}. Furthermore, since
%$s'$ is a maximal rank such source, \mbox{$s' \sqsupseteq_S s$}. We
%consider the four cases and show that, in each, either \mbox{$x \prec
%z$} or \mbox{$z \prec y$}:
%
%{\bf Case 1}: \mbox{$x <^{s'} z$}. Since, for every \mbox{$s'' \in
%S$}, \mbox{$s'' \sqsupset_S s'$} implies \mbox{$x \not<^{s''} z$} and
%\mbox{$z \not<^{s''} x$}, \mbox{$x \prec z$}.
%
%{\bf Case 2}: \mbox{$z <^{s'} x$}. By modularity, \mbox{$z <^{s'} y$}
%or \mbox{$y <^{s'} x$}.
%
%Suppose \mbox{$z <^{s'} y$}. Since, for every \mbox{$s'' \in S$},
%\mbox{$s'' \sqsupset_S s'$} implies \mbox{$z \not<^{s''} y$} and
%\mbox{$y \not<^{s''} z$}, \mbox{$z \prec y$}.
%
%Suppose \mbox{$y <^{s'} x$}. Then \mbox{$s \sqsupseteq_S s'$}, so
%\mbox{$s \sqeq_S s'$}. Since \mbox{$x <^s y$}, \mbox{$x <^s z$} or
%\mbox{$z <^s y$} by modularity. Thus, substituting $s$ for $s'$ above,
%either \mbox{$x <^s z$} and, for every \mbox{$s'' \in S$}, \mbox{$s''
%\sqsupset_S s$} implies \mbox{$x \not<^{s''} z$} and \mbox{$z
%\not<^{s''} x$} so that \mbox{$x \prec z$}, or \mbox{$z <^s y$} and,
%for every \mbox{$s'' \in S$}, \mbox{$s'' \sqsupset_S s$} implies
%\mbox{$z \not<^{s''} y$} and \mbox{$y \not<^{s''} z$} so that \mbox{$z
%\prec y$}.
%
%{\bf Case 3}: \mbox{$y <^{s'} z$}. By modularity, \mbox{$y <^{s'} x$}
%or \mbox{$x <^{s'} z$} which we have already considered in cases 2 and
%1, respectively.
%
%{\bf Case 4}: \mbox{$z <^{s'} y$}. We have already considered this in
%case 2.
%\qed
%\end{pf}
It remains to show that $\prec$ is transitive. Suppose \mbox{$x \prec
y$} and \mbox{$y \prec z$}. Then there exists \mbox{$s_1 \in S$} such
that \mbox{$x <^{s_1} y$} and, for every \mbox{$s'_1 \in S$},
\mbox{$s'_1 \sqsupset_S s$} implies \mbox{$x \not<^{s'_1} y$} and
\mbox{$y \not<^{s'_1} x$}, and there exists \mbox{$s_2 \in S$} such
that \mbox{$y <^{s_2} z$} and, for every \mbox{$s'_2 \in S$, $s'_2
\sqsupset_S s$} implies \mbox{$y \not<^{s'_2} z$} and \mbox{$z
\not<^{s'_2} y$}. Suppose \mbox{$s_1 \sqsupset_S s_2$} (the case
\mbox{$s_2 \sqsupset_S s_1$} is similar). Then \mbox{$y \not<^{s_1} z$}
and \mbox{$z \not<^{s_1} y$}. By modularity, since \mbox{$x <^{s_1}
y$} and \mbox{$z \not<^{s_1} y$}, \mbox{$x <^{s_1} z$}. Let \mbox{$s'
\in S$} and \mbox{$s' \sqsupset_S s_1$}. Then \mbox{$x \not<^{s'} y$}
and \mbox{$y \not<^{s'} x$}. And, since \mbox{$s_1 \sqsupset_S s_2$},
\mbox{$s' \sqsupset_S s_2$}, so \mbox{$y \not<^{s'} z$} and \mbox{$z
\not<^{s'} y$}. By modularity, \mbox{$x \not<^{s'} z$} and \mbox{$z
\not<^{s'} x$}. Therefore, \mbox{$x \prec z$}.
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGR^*(S) \in \mcb$}.
\end{prop}
\begin{pf}
By Proposition~\ref{prop-AGRUn}, \mbox{$<_r \in \mcb$} for every
\mbox{$r \in \ranks(S)$}. For convenience, we assume the existence of
a ``virtual'' source $s_r$ corresponding to each $<_r$. Precisely, for
each \mbox{$r \in \ranks(S)$}, assume there exists a source \mbox{$s_r
\in \mcs$} such that \mbox{$<^{s_r} = <_r$} and \mbox{$\rank(s_r) =
r$}, and let $S'$ be the set of these sources. Then,
\begin{eqnarray*}
	\AGR^*(S) & = & \left\{(x, y) :
				\exists r \in \mcr.\ x <_r y \wedge
				\left(\forall r' \in \ranks(S).\ r' >
				        r \implies x \sagnost_{r'}
				        y\right)
			\right\} \\
		& = & \left\{(x, y) :
				\exists s \in S'.\ x <^s y \wedge
				\left(\forall s' \in S'.\ s'
				        \sqsupset_{S'} s \implies x
				        \sagnost^{s'} y\right)
			\right\} \\
		& = & \AGRRf(S').	
\end{eqnarray*}
Since there is one source in $S'$ per rank $r$, and since $>$ is a
total order over $\mcr$, $\sqsupseteq_{S'}$ is a total order. The
result follows from Proposition~\ref{prop-AGRRf}.
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\AGR(S) \in \mcb$}.
\end{prop}
\begin{pf}
By Proposition~\ref{prop-AGRRfModnotT}, \mbox{$\AGRRf(S)$} is modular.
\mbox{$\AGRRf(S)^+$} is obviously transitive, and, by
Proposition~\ref{prop-Props}, it is modular as well.
\qed
\end{pf}

\begin{prop}
	Suppose \mbox{$S \subseteq \mcs$}.
	\begin{enumerate}

	\item If $\sqsupseteq_S$ is fully connected, \mbox{$\AGR(S) =
	\AGRUn(S)$}.

	\item If \mbox{$\sqsupseteq_S$} is a total order,
	\mbox{$\AGR(S) = \AGRRf(S)$}.

	\end{enumerate}
\end{prop}
\begin{pf}\hspace{0ex}\\[-0.5cm]
\begin{enumerate}

\item Suppose $\sqsupseteq_S$ is fully connected. Then the second half
of the definition of $\AGRRf$ is vacuously true so that $\AGRRf(S)$
simplifies to $\{(x,y) : \exists s \in S.\ x <^s y\}$. But this is
exactly $\bigcup_{s \in S} <^s$, i.e., $\Un(S)$, so $\AGR(S) =
\AGRRf(S)^+ = \Un(S)^+ = \AGRUn(S)$.

\item Suppose $\sqsupseteq_S$ is an total order. By
Proposition~\ref{prop-AGRRf}, \mbox{$\AGRRf(S)$} is transitive, so
$\AGR(S) = \AGRRf(S)^+ = \AGRRf(S)$.

\end{enumerate}
\qed
\end{pf}

\begin{prop}
	Suppose \mbox{$S \subseteq \mcs$}, \mbox{$\prec_* =
	\AGRRf(S)$}, \mbox{$\prec = \AGR(S)$}, and \mbox{$x \not\prec_*
	y$} for \mbox{$x, y \in \mcw$}. If \mbox{$x \prec y$}, then
	\mbox{$x \conflict y$}.
\end{prop}
\begin{pf}
We first show the following lemma:
\begin{lem}\label{lem-conflict}
	Suppose \mbox{$S \subseteq \mcs$} and \mbox{$\prec_* =
	\AGRRf(S)$}. For every integer \mbox{$n \geq 2$}, if \mbox{$x,
	y \in \mcw$}, \mbox{$x \not\prec_* y$}, there exist
	\mbox{$x_0, \ldots, x_n \in \mcw$} such that \mbox{$x = x_0
	\prec_* \cdots \prec_* x_n = y$}, and $n$ is the smallest
	integer such that this is true, then \mbox{$x_n \prec_* \cdots
	\prec_* x_0$}.
\end{lem}
\begin{pf}
Suppose $x, y \in \mcw$, $x \not\prec_* y$, and there exist $x_0,
\ldots, x_n \in \mcw$ such that $x = x_0 \prec_* \cdots \prec_* x_n =
y$, and $n$ is the smallest integer such that this is true. Consider
any triple $x_{i-1}, x_i, x_{i+1}$, where $1 \leq i \leq n-1$. First,
$x_{i-1} \not\prec_* x_{i+1}$, otherwise there would be a chain of
shorter length than $n$ between $x$ and $y$. Now, since $x_{i-1}
\prec_* x_i$, there exists $s_1 \in S$ such that $x_{i-1} <^{s_1} x_i$
and, for all $s' \sqsupset_S s_1 \in S$, $x_{i-1} \sagnost^{s'}
x_i$. Similarly, there exists $s_2 \in S$ such that $x_i <^{s_2}
x_{i+1}$ and, for all $s' \sqsupset_S s_2 \in S$, $x_i \sagnost^{s'}
x_{i+1}$. Thus, all sources with higher rank than $\max(s_1, s_2)$ are
agnostic with respect to $x_{i-1}$ and $x_{i+1}$.

Suppose \mbox{$s_1 \sqsupset_S s_2$}. Then \mbox{$x_i \sagnost^{s_1}
x_{i+1}$} so, by modularity, \mbox{$x_{i-1} <^{s_1} x_{i+1}$}. But
then\linebreak
\mbox{$x_{i-1} \prec_* x_{i+1}$}, a contradiction. Similarly, we
derive a contradiction if \mbox{$s_2 \sqsupset s_1$}. Thus, \mbox{$s_1
\sqeq_S s_2$}.

Now, since \mbox{$x_{i-1} \not\prec_* x_{i+1}$} and all sources with
rank higher than $s_1$ and $s_2$ are agnostic with respect to
$x_{i-1}$ and $x_{i+1}$, \mbox{$x_{i-1} \not<^{s_1} x_{i+1}$}. By
modularity, \mbox{$x_{i+1} <^{s_1} x_i$}. Since \mbox{$s_1 \sqeq_S
s_2$}, and all the sources with higher rank than $s_2$ are agnostic
with respect to $x_i$ and $x_{i+1}$, \mbox{$x_{i+1} \prec_*
x_i$}. Similarly, \mbox{$x_i <^{s_2} x_{i-1}$}, so \mbox{$x_i \prec_*
x_{i-1}$}.  Since $i$ was chosen arbitrarily between $1$ and
\mbox{$n-1$}, \mbox{$x_n \prec_* \cdots \prec_* x_0$}. And, in fact,
all the opinions between these worlds originate from sources of the
same rank.
\qed
\end{pf}

Now suppose $x \not\prec_* y$. If $x \prec y$, then there exist $x_0,
\ldots, x_n$ such that $x = x_0 \prec_* \cdots \prec_* x_n = y$ and
$n$ is the smallest positive integer such that this is true. Then, by
Lemma~\ref{lem-conflict}, $y = x_n \prec_* \cdots \prec_* x_0 = x$,
so $y \prec x$ and $x \conflict y$.
\qed
\end{pf}

\begin{prop}
	Let \mbox{$S = \{s_1, \ldots, s_n\} \subseteq \mcs$} and
	\mbox{$\AGR_f(<^{s_1}, \ldots, <^{s_n}) =
	\AGR(S)$}. \mbox{$\AGR_f$} satisfies (the modified versions of)
	restricted range, unrestricted domain, Pareto principle, IIA,
	and non-dictatorship.
\end{prop}
\begin{pf}
Let \mbox{$\prec = \AGR_f(<^{s_1}, \ldots, <^{s_n})$}. Then
\mbox{$\prec = \AGR(S)$}.

{\bf Restricted range:} \mbox{$\AGR_f$} satisfies restricted range by
Proposition~\ref{prop-AGR}.

{\bf Unrestricted domain:} \mbox{$\AGR_f$} satisfies unrestricted
domain by Definition~\ref{defn-sources}.

{\bf Pareto principle:} Suppose \mbox{$x <^{s_i} y$} for all $s_i$. In
particular, \mbox{$x <^s y$} where $s$ is a maximal rank source of
$S$. Since $s$ is maximal, it is vacuously true that for every
\mbox{$s' \sqsupset_S s \in S$}, \mbox{$x \not<^s y$} and \mbox{$y
\not<^{s'} x$}. Therefore, \mbox{$x \prec y$}, so \mbox{$\AGR_f$}
satisfies the Pareto principle.

{\bf IIA:} Let \mbox{$S' = \{s'_1, \ldots, s'_n\}$}. First note that
\mbox{$\AGRRf$} satisfies IIA:
\begin{lem}\label{lem-AGRRf-IIA}
	Suppose $S = \{s_1, \ldots, s_n\} \subseteq \mcs$, $S' =
	\{s'_1, \ldots, s'_n\} \subseteq \mcs$, $s_i \sqeq_S s'_i$ for
	all $i$, $\prec_* = \AGRRf(S)$, and $\prec'_* =
	\AGRRf(S')$. If, for $x, y \in \mcw$, $x <^{s_i} y$ iff $x
	<^{s'_i} y$ for all $i$, then $x \prec_* y$ iff $x \prec'_*
	y$.
\end{lem}
\begin{pf}
Suppose \mbox{$s_i \sqeq_S s'_i$}, and \mbox{$x <^{s_i} y$} iff \mbox{$x
<^{s'_i} y$}, for all $i$. Then \mbox{$x \prec_* y$} iff \mbox{$x
\prec'_* y$} since Definition~\ref{def-AGRRf} only relies on the
relative ranking of the sources and the relations between $x$ and $y$
in their belief states to determine the relation between $x$ and $y$
in the aggregated state.
\qed
\end{pf}
Thus, IIA can only be disobeyed when the closure step of \mbox{$\AGR$}
introduces new opinions. (Note that IIA is satisfied when there are no
sources of equal rank since, by Proposition~\ref{prop-AGRSpecial}, the
closure step introduces no new opinions under these conditions.)

Now, suppose \mbox{$x, y \in \mcw$}, \mbox{$x <^{s_i} y$} iff \mbox{$x
<^{s_i'} y$} for all $i$, \mbox{$x \notconflict y$}, and \mbox{$x
\notconflict' y$}. We show that \mbox{$x \prec y$} implies \mbox{$x
\prec' y$} (the other direction is identical). Suppose $x \prec
y$. Let $\prec_* = \AGRRf(S)$ and $\prec'_* = \AGRRf(S')$. Since $x
\notconflict y$, $x \prec_* y$ by Proposition~\ref{prop-conflict}. But
then \mbox{$x \prec'_* y$} by Lemma~\ref{lem-AGRRf-IIA}, so \mbox{$x
\prec' y$}. \\
(END OF IIA SUB-PROOF)

{\bf Non-dictatorship:} Suppose $\sqsupseteq_S$ is fully connected and
suppose \mbox{$x <^{s_i} y$} and \mbox{$y \not<^{s_i} x$}. Let $s_j$
be such that \mbox{$y <^{s_j} x$}. Then \mbox{$x \prec y$} and
\mbox{$y \prec x$}, so $s_i$ is not a dictator.
\qed
\end{pf}
(END OF PROPOSITION~\ref{prop-Arrow2} PROOF)


%%% Multi-Agent Fusion %%%

\begin{prop}
	Let $\mca$ and $S$ be as in Definition~\ref{def-fusion},
	$\prec^{A_i}$, agent $A_i$'s induced belief state, and
	$\sqsupseteq_S$, fully connected. If \mbox{$A = \fuse(\mca)$},
	then \mbox{$\left(\bigcup_{A_i \in \mca}
	\prec^{A_i}\right)^+$} is $A$'s induced belief state.
\end{prop}
\begin{pf}
We will use the following lemma:
\begin{lem}\label{lem-RedundantTC}
	If $\Pi$ is a set of relations over an arbitrary finite set
	$\Omega$, then
	\begin{displaymath}
		\left(\bigcup_{\leq \in \Pi} \leq^+\right)^+ =
		\left(\bigcup_{\leq \in \Pi} \leq\right)^+
	\end{displaymath}
	where $\leq^+$ is the transitive closure of $\leq$.
\end{lem}
\begin{pf}
Let \mbox{$\preceq = \left(\bigcup_{\leq \in \Pi} \leq^+\right)^+$},
\mbox{$\preceq' = \left(\bigcup_{\leq \in \Pi} \leq\right)^+$}, and
\mbox{$a, b \in \Omega$}.  Suppose \mbox{$a \preceq b$}. Then there
exist \mbox{$\leq_0, \ldots, \leq_{n-1} \in \Pi$} and \mbox{$w_0,
\ldots, w_n \in \Omega$} such that
\begin{displaymath}
	a = w_0 \leq_0^+ \cdots \leq_{n-1}^+ w_n = b
\end{displaymath}
Thus, there exist \mbox{$x_{00}, \ldots, x_{0m_0}, \ldots$},
\mbox{$x_{(n-1)0}, \ldots, x_{(n-1)m_{n-1}}$} in $\Omega$ such that
\begin{displaymath}
	a = w_0 = x_{00} \leq_0 \cdots \leq_0 x_{0m_0} = w_1 = \cdots
	  = w_{n-1} = x_{(n-1)0} \leq_{n-1} \cdots \leq_{n-1}
		x_{(n-1)m_{n-1}}
	  = w_n
\end{displaymath}
and $w_n = b$, so \mbox{$a \preceq' b$}.

Now suppose \mbox{$a \preceq' b$}. Then there exist \mbox{$\leq_0,
\ldots, \leq_{n-1} \in \Pi$} and \mbox{$w_0, \ldots, w_n \in \Omega$}
such that
\begin{displaymath}
	a = w_0 \leq_0 \cdots \leq_{n-1} w_n = b
\end{displaymath}
Obviously, this implies that
\begin{displaymath}
	a = w_0 \leq_0^+ \cdots \leq_{n-1}^+ w_n = b
\end{displaymath}
which implies that
\begin{displaymath}
	a = w_0 \leq_*^+ \cdots \leq_*^+ w_n = b
\end{displaymath}
where \mbox{$\leq_* = \left(\bigcup_{\leq \in \Pi} \leq\right)$}, so
\mbox{$a \preceq b$}.
\qed
\end{pf}

Now, let $\prec$ be the belief state induced by
\mbox{$\fuse(\mca)$}. Then \mbox{$\prec = \AGR(S)$}. By
Proposition~\ref{prop-AGRSpecial}, \mbox{$\prec = \AGRUn(S)$}, so
\begin{displaymath}
	\prec = \Un(S)^+
	      = \left(\bigcup_{s \in S} <^s\right)^+
	      = \left(\bigcup_{s \in \bigcup^n_{i=1} S_i}
			<^s\right)^+
	      = \left(\bigcup_{A_i \in \mca}\bigcup_{s \in S_i}
			<^s\right)^+
\end{displaymath}
By the lemma,
\begin{displaymath}
	\prec = \left(\bigcup_{A_i \in \mca}\left(\bigcup_{s \in
			S_i} <^s\right)^+\right)^+
	      = \left(\bigcup_{A_i \in \mca} \AGRUn(S_i)\right)^+
	      = \left(\bigcup_{A_i \in \mca} \prec^{A_i}\right)^+
\end{displaymath}
\qed
\end{pf}

\begin{prop}
	Let $A$ be an agent informed by a set of sources \mbox{$S
	\subseteq \mcs$} and with pedigreed belief state
	\mbox{$(\prec, l)$}. Then $\prec^A_r$ is the relation
	\begin{displaymath}
		\left\{(x,y) : \exists s \in S.\ x <^s y \wedge r =
		   \rank(s) \wedge \left(\forall s' \in
		   S.\ s' \sqsupset s \implies x \sagnost^{s'}
		   y\right)\right\}.
	\end{displaymath}
\end{prop}
\begin{pf}
Suppose \mbox{$x \prec^A_r y$}. Then \mbox{$x \prec y$} and
\mbox{$l((x,y)) = r$}. By Definitions~\ref{def-AGRRf} and
\ref{def-PBS}, there exists \mbox{$s \in S$} such that \mbox{$x <^s
y$} and for every \mbox{$s' \sqsupset_S s \in S$}, \mbox{$x
\sagnost^{s'} y$}. In particular, if \mbox{$x <^{s'} y$} for some
\mbox{$s' \in S$}, then \mbox{$s \sqsupseteq_S s'$}, so \mbox{$\rank(s)
\geq \rank(s')$}. Thus,
\begin{displaymath}
	r = l((x,y)) = \max(\{\rank(s') : x <^{s'} y, s' \in S\})
	  = \rank(s).
\end{displaymath}

Now suppose there exists \mbox{$s \in S$} such that \mbox{$x <^s y$},
\mbox{$r = \rank(s)$}, and, for every \mbox{$s' \sqsupset_S s \in S$},
\mbox{$x \sagnost^{s'} y$}. Then \mbox{$x \prec y$}. Moreover, since
for every \mbox{$s' \in S$}, \mbox{$x <^{s'} y$} implies \mbox{$s
\sqsupseteq_S s'$} which implies \mbox{$\rank(s) \geq \rank(s')$},
\begin{displaymath}
	l((x,y)) = \max(\{\rank(s') : x <^{s'} y, s' \in S\})
		 = \rank(s) = r.
\end{displaymath}
Therefore, \mbox{$x \prec^A_r y$}.
\qed
\end{pf}

\begin{prop}
	Let $\mca$, $\mcp_\mca$, $S$, and $\sqsupseteq_S$ be as in
	Definition~\ref{def-pfusion}. Then $\pfuse(\mcp_\mca)$ is the
	pedigreed belief state of \mbox{$\fuse(\mca)$}.
\end{prop}

\begin{pf}
Let $\pfuse(\mcp_\mca) = (\prec, l)$, $\prec' = \AGRRf(S)$, and $l' :
\prec' \to \mcr$ such that $l'((x,y)) = \max(\{rank(s) : x <^s y, s
\in S\})$. It suffices to show that $\prec = \prec'$ and $l = l'$.

Suppose \mbox{$x \prec y$}. We show that \mbox{$x \prec' y$}, i.e.,
there exists \mbox{$s \in S$} such that \mbox{$x <^s y$} and, for
every \mbox{$s' \sqsupset_S s \in S$}, \mbox{$x \not<^{s'} y$} and
\mbox{$y \not<^{s'} x$}, and that \mbox{$l'((x,y)) = l((x,y))$}. Since
\mbox{$x \prec y$}, there exists $A_i$ and $r$ such that \mbox{$x
\prec^{A_i}_r y$} and, for every \mbox{$A_j \in \mca$} and \mbox{$r' >
r \in \mcr$}, \mbox{$x \not\prec^{A_j}_{r'} y$} and \mbox{$y
\not\prec^{A_j}_{r'} x$}. Since \mbox{$x \prec^{A_i}_r y$}, there
exists \mbox{$s \in S_i$} such that \mbox{$x <^s y$}, \mbox{$\rank(s) =
r$}, and, for every \mbox{$s_1 \sqsupset_S s \in S_i$}, \mbox{$x
\not<^{s_1} y$} and \mbox{$y \not<^{s_1} x$}. \mbox{$S_i \subseteq
S$}, so there exists \mbox{$s \in S$} such that \mbox{$x <^s y$}. Now
suppose $s'$ is a maximal rank source of $S$ with \mbox{$x <^{s'} y$}
or \mbox{$y <^{s'} x$}. Such an $s'$ exists since \mbox{$x <^s
y$}. Since $\sqsupseteq_S$ is a total preorder, it suffices to show that
\mbox{$s \sqsupseteq_S s'$}. Suppose \mbox{$s' \in S_j$}. Since
\mbox{$S_j \subseteq S$}, $s'$ is also a maximal rank source of $S_j$
with \mbox{$x <^{s'} y$} or \mbox{$y <^{s'} x$}, so \mbox{$x
\prec^{A_j}_{\rank(s')} y$} or \mbox{$y \prec^{A_j}_{\rank(s')} x$}. But
since \mbox{$x \prec^{A_i}_r y$}, \mbox{$r = \rank(s) \geq \rank(s')$},
so \mbox{$s \sqsupseteq_S s'$}. Furthermore, \mbox{$l'((x,y)) = \rank(s)
= r = l((x,y))$}.

Now suppose \mbox{$x \prec' y$}. We show that \mbox{$x \prec y$},
i.e., there exists $A_i$ and $r$ such that \mbox{$x \prec^{A_i}_r y$}
and, for every \mbox{$A_j \in \mca$} and \mbox{$r' > r \in \mcr$},
\mbox{$x \not\prec^{A_j}_{r'} y$} and \mbox{$y \not\prec^{A_j}_{r'}
x$}, and that \mbox{$l((x,y)) = l'((x,y))$}. Since \mbox{$x \prec'
y$}, there exists \mbox{$s \in S$} such that \mbox{$x <^s y$} and, for
every \mbox{$s' \sqsupset_S s \in S$}, \mbox{$x \not<^{s'} y$} and
\mbox{$y \not<^{s'} x$}. Suppose \mbox{$s \in S_i$}. Since \mbox{$S_i
\subseteq S$}, it is also the case that for every \mbox{$s' \sqsupset_S
s \in S_i$}, \mbox{$x \not<^{s'} y$} and \mbox{$y \not<^{s'} x$}, so
\mbox{$x \prec^{A_i}_{\rank(s)} y$}. Now, let $A_j$ and $r'$ be such
that \mbox{$x \prec^{A_j}_{r'} y$} or \mbox{$y \prec^{A_j}_{r'}
x$}. It suffices to show that \mbox{$\rank(s) \geq r'$}. By
Proposition~\ref{prop-label}, there exists \mbox{$s' \in S_j$} such
that \mbox{$x <^{s'} y$} or \mbox{$y <^{s'} x$} and \mbox{$\rank(s') =
r'$}. But then \mbox{$s \sqsupseteq_S s'$}, so \mbox{$\rank(s) \geq
\rank(s') = r'$}. Furthermore, \mbox{$l((x,y)) = \rank(s) =
l'((x,y))$}.
\qed
\end{pf}

\begin{prop}
	If $\mca$, $\mcp_\mca$, and $S$ are as in
	Definition~\ref{def-pfusion}, $\sqsupseteq_S$ is a total
	order, and\linebreak
	\mbox{$\pfuse(\mcp_\mca) = (\prec, l)$}, then
	\mbox{$\prec^+ = \prec$}.
\end{prop}
\begin{pf}
Since $\sqsupseteq_S$ is a total order, $\AGR(S) = \AGRRf(S)$ by
Proposition~\ref{prop-AGRSpecial}. Thus, $\prec = \AGRRf(S) = \AGR(S)
= \AGRRf(S)^+ = \prec^+$.
\qed
\end{pf}


%%% Incorporating Voting %%%

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\vt_0(S) = \Un(S)$}.
\end{prop}
\begin{pf}
Suppose $(x,y) \in \Un(S)$. Then $S \neq \emptyset$ and $x <^s y$ for
some $s \in S$. Thus, $\cnt_S(x,y) > 0$ and $\cnt_S(x,y)/\|S\| > 0$,
so $(x,y) \in \vt_0(S)$. Suppose, instead, $(x,y) \not\in
\Un(S)$. Then $x \not<^s y$ for all $s \in S$, so $\cnt_S(x,y) = 0$,
so $(x,y) \not\in \vt_0(S)$.
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$}, then \mbox{$\vt_1(S) =
	\bigcap_{s \in S} <^s$}.
\end{prop}
\begin{pf}
Suppose $(x,y) \in \bigcap_{s \in S} <^s$. Then $S \neq \emptyset$ and
$x <^s y$ for all $s \in S$. Thus, $\cnt_S(x,y) > 0$ and
$\cnt_S(x,y)/\|S\| \geq 1$, so $(x,y) \in \vt_1(S)$. Suppose, instead,
$(x,y) \not\in \bigcap_{s \in S} <^s$. Then there exists $s \in S$
such that $x \not<^s y$, so $\cnt_S(x,y) < \|S\|$. Thus,
$\cnt_S(x,y)/\|S\| < 1$, so $(x,y) \not\in \vt_1(S)$.
\qed
\end{pf}

\begin{prop}
	Suppose \mbox{$S \subseteq \mcs$}. \mbox{$\vt_1(S)$} is
	transitive but not necessarily modular.
\end{prop}
\begin{pf}
Let $\mcw = \{x,y,z\}$ and $S = \{s_1, s_2\}$ where $<^{s_1} =
\{(x,y), (y,z), (x,z)\}$ and $<^{s_2} = \{(x,y), (z,y)\}$. Then
$\vt_1(S) = \{(x,y)\}$ which is not modular.
\qed
\end{pf}

\begin{prop}
	If \mbox{$\|\mcw\| \geq 3$}, then for every \mbox{$p \in
	(0,1)$}, there exists $\mcs$ such that \mbox{$\vt_p(\mcs)$} is
	neither modular nor transitive.
	%, and \mbox{$\vt_p(\mcs)^+$} is not modular.
\end{prop}
\begin{pf}
Note that if $\|\mcw\| = 2$, every relation over $\mcw$ is either
transitive or modular (but not necessarily both), and if $\|\mcw\| =
1$ every relation over $\mcw$ is both modular and transitive. Let
$\mcw$ be a set of worlds such that $\|\mcw\| \geq 3$ and let $x$,
$y$, and $z$ denote three distinct members of $\mcw$. We will define
$\mcs$ parameterized by $p$ such that $\vt_p(\mcs)$ is the relation
$\{(x,y), (y,z)\}$ which is neither transitive or modular.

Let $\mcs = \{s_1, \ldots, s_n\}$ satisfying the following conditions:
\begin{enumerate}

\item $n = \lceil 1/p + 1 \rceil$ if $p \leq 1/3$, $\lceil 2/(1-p) + 1
\rceil$ otherwise.\footnote{\mbox{$\lceil x \rceil$} denotes the {\em
ceiling} of $x$, i.e., the smallest integer greater than or equal to
$x$.}

\item $<^{s_1} = \{(w,y) | w \in \mcw, w \neq y\}$.

\item $<^{s_2} = \{(y,w) | w \in \mcw, w \neq y\}$.

\item $\lceil pn - 1 \rceil$ of the remaining sources have belief
state $\{(x,w) | w \in \mcw, w \neq x\} \cup \{(w, z) | w \in \mcw, w
\neq z\}$.

\item The remaining sources have fully disconnected belief states.

\end{enumerate}
It is clear that $<^{s_i} \in \mcb$ for all $i$. We make two
observations: First, observe that $pn > 1$. If $p \leq 1/3$,
\begin{displaymath}
  pn = p\lceil 1/p + 1 \rceil \geq 1 + p > 1.
\end{displaymath}
If $p > 1/3$,
\begin{displaymath}
  pn = p\lceil 2/(1-p) + 1\rceil \geq 2p/(1-p) + p
\end{displaymath}
which is a monotonically increasing function, so
\begin{displaymath}
  pn > 2(1/3)/(1 - 1/3) + 1/3 = 4/3 > 1.
\end{displaymath}

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 + \lceil pn - 1 \rceil < 1 + pn$ which is less than $n$ if $n
> 1/(1-p)$. This is true if $p \leq 1/3$ since for these values
\begin{displaymath}
  n = \lceil 1/p + 1\rceil > 1/p > 1/(1-p).
\end{displaymath}
And it is also true if $p > 1/3$ since
\begin{displaymath}
  n = \lceil 2/(1-p) + 1 \rceil > 2/(1-p) > 1/(1-p).
\end{displaymath}

$(x,y)$ appears only in $<^{s_1}$ and each of the belief states
described in condition 3, so
\begin{displaymath}
  \cnt_\mcs(x,y) = 1 + \lceil pn - 1 \rceil \geq 1 + pn - 1 = pn
\end{displaymath}
so $(x,y) \in \vt_p(\mcs)$. Similarly, $(y,z)$ appears only in
$<^{s_2}$ and each of the belief states described in condition 3, so
\begin{displaymath}
  \cnt_\mcs(y,z) = 1 + \lceil pn - 1 \rceil \geq 1 + pn - 1 = pn
\end{displaymath}
so $(y,z) \in \vt_p(\mcs)$. It remains to show that $\vt_p(\mcs)$ has
no other members. We show that the count of each pair is less than
$pn$. $\cnt_\mcs(w,w) = 0 < pn$ for all $w \in \mcw$. $\cnt_\mcs(z,w) =
\cnt_\mcs(w,x) = 0$ for all $w \neq y \in \mcw$. For all $w \in \mcw -
\{x,y\}$, $(w,y)$ only appears in $<^{s_1}$, so $\cnt_\mcs(w,y) = 1 < pn$
from our first observation above. For all $w \in \mcw - \{y,z\}$,
$(y,w)$ only appears in $<^{s_2}$, so $\cnt_\mcs(y,w) = 1 < pn$. Finally,
for all $w \in \mcw - \{x,y,z\}$, $(x,z)$, $(x,w)$, and $(w,z)$ only
appear in the belief states described in condition 3, so
\begin{displaymath}
  \cnt_\mcs(x,z) = \cnt_\mcs(x,w) = \cnt_\mcs(w,z) = \lceil pn - 1 \rceil < pn.
\end{displaymath}
\qed
\end{pf}

\begin{prop}
	Suppose $\preceq$ is a transitive relation over $\mcw$ and
	\mbox{$x, y \in \mcw$}.
	\begin{enumerate}

	\item If \mbox{$x \prec y$}, then \mbox{$\lev_\preceq(x) <
	\lev_\preceq(y)$}.

	\item If \mbox{$x \conflict y$}, then \mbox{$\lev_\preceq(x) =
	\lev_\preceq(y)$}.

	\item If \mbox{$\lev_\preceq(x) < \lev_\preceq(y)$}, then
	$\exists z.\ \lev_\preceq(z) = \lev_\preceq(x) \wedge z \prec
	y$.

	\item If \mbox{$\lev_\preceq(x) = \lev_\preceq(y)$}, then
	\mbox{$x \preceq y$} iff \mbox{$y \preceq x$}.

	\end{enumerate}
\end{prop}
\begin{pf}\hspace{0ex}\\[-0.5cm]
\begin{enumerate}

\item Suppose $x \prec y$. Then
\begin{eqnarray*}
    \lev_\preceq(y) & = & 1 + \max\limits_{y' \in
      \mcw}\left(\left\{\lev_\preceq(y') : y' \prec y\right\}\right) \\
                   & \geq & 1 + \lev_\preceq(x) \\
                   & > & \lev_\preceq(x).
\end{eqnarray*}

\item Suppose $x \conflict y$. If $x \in \C(\mcw, \preceq)$ then $y
\in \C(\mcw, \preceq)$, so $\lev_\preceq(x) = \lev_\preceq(y) =
0$. Suppose $x \not\in \C(\mcw, \preceq)$. Then $y \not\in \C(\mcw,
\preceq)$ and $\lev_\preceq(x) = 1 + \max\limits_{y' \in
\mcw}\left(\left\{\lev_\preceq(y') : y' \prec x\right\}\right)$. If
$y'$ is one such element, then $y' \prec y$ by transitivity, so
\begin{displaymath}
  \lev_\preceq(y) = 1 + \max\limits_{y'' \in
    \mcw}\left(\left\{\lev_\preceq(y'') : y'' \prec y\right\}\right)
    \geq \lev_\preceq(x).
\end{displaymath}
By an identical argument, $\lev_\preceq(x) \geq
\lev_\preceq(y)$. Thus, $\lev_\preceq(x) = \lev_\preceq(y)$.

\item Suppose $\lev_\preceq(x) < \lev_\preceq(y)$. It is sufficient to
prove the following: For every non-negative integer $l <
\lev_\preceq(y)$, there exists $z \prec y$ such that $\lev_\preceq(z) =
l$. We prove by induction on $l$. If $l = \lev_\preceq(y) - 1$, there
must exist $z \prec y$ and $\lev_\preceq(z) = l$ by definition. Assume
there exists $z \prec y$ for $0 < l < \lev_\preceq(y)-1$ such that
$\lev_\preceq(z) = l$. Since $l > 0$, there exists $z' \prec z$ such that
$\lev_\preceq(z') = l-1$. By transitivity, $z' \prec y$.

\item Suppose $\lev_\preceq(x) = \lev_\preceq(y)$. If $x \preceq y$ then
$x \not\prec y$ from the first part of this proposition, otherwise
$\lev_\preceq(x) < \lev_\preceq(x)$, so $y \preceq x$. Similarly, if $y
\preceq x$ then $y \not\prec x$, so $x \preceq y$.

\end{enumerate}
\qed
\end{pf}

\begin{prop}
	If $\preceq$ is a transitive relation over $\mcw$, then
	\mbox{$\MC(\preceq) \in \mcb$}.
\end{prop}
\begin{pf}
Let $\preceq^* = \MC(\preceq)$ and $x, y, z \in \mcw$. Suppose $x
\preceq^* y$. Then $\lev_\preceq(x) < \lev_\preceq(y)$ or $\lev_\preceq(x) =
\lev_\preceq(y)$ and $\exists x', y' \in \mcw.\ (\lev_\preceq(x') =
\lev_\preceq(y') = \lev_\preceq(x) \wedge x' \conflict y')$. If
$\lev_\preceq(x) < \lev_\preceq(z)$ or $\lev_\preceq(z) <
\lev_\preceq(y)$, then $x \preceq^* z$ or $z \preceq^* y$. Otherwise,
$\lev_\preceq(x) = \lev_\preceq(y) = \lev_\preceq(z)$ and $\exists x',
y' \in \mcw.\ (\lev_\preceq(x') = \lev_\preceq(y') = \lev_\preceq(x)
\wedge x' \conflict y')$, so $x \preceq^* z$. Thus, $\preceq^*$ is
modular.

Now also suppose $y \preceq^* z$. Then $\lev_\preceq(y) <
\lev_\preceq(z)$ or $\lev_\preceq(y) = \lev_\preceq(z)$ and $\exists
y', z' \in \mcw.\ (\lev_\preceq(y') = \lev_\preceq(z') =
\lev_\preceq(y) \wedge y' \conflict z')$. If $\lev_\preceq(x) <
\lev_\preceq(y)$ or $\lev_\preceq(y) < \lev_\preceq(z)$, then
$\lev_\preceq(x) < \lev_\preceq(z)$ by transitivity of $<$, so $x
\preceq^* z$. Otherwise, $\lev_\preceq(x) = \lev_\preceq(y) =
\lev_\preceq(z)$ and $\exists x', y' \in \mcw.\ (\lev_\preceq(x') =
\lev_\preceq(y') = \lev_\preceq(x) \wedge x' \conflict y')$, so $x
\preceq^* z$. Thus, $\preceq^*$ is transitive.
\qed
\end{pf}

\begin{prop}
	Suppose $\preceq$ is a transitive relation over $\mcw$ and
	\mbox{$\preceq^* = \MC(\preceq)$}.
	\begin{enumerate}

	\item \mbox{$\preceq \subseteq \preceq^*$} and \mbox{$\prec
	\subseteq \prec^*$}.

	\item If $\preceq$ is modular, then \mbox{$\preceq^* =
	\preceq$}.

	\item \mbox{$\lev_{\preceq^*}(x) = \lev_\preceq(x)$} for all
	\mbox{$x \in \mcw$}.

	\item If $\preceq' \in \mcb$ such that $\preceq \subseteq
	\preceq'$ and $\lev_{\preceq'}(x) = \lev_\preceq(x)$ for all $x
	\in \mcw$, then $\preceq^* \subseteq \preceq'$.

	\end{enumerate}
\end{prop}
\begin{pf}
Let $x, y \in \mcw$.
\begin{enumerate}

\item Suppose $x \preceq y$. Then $\lev_\preceq(x) \leq
\lev_\preceq(y)$. If $\lev_\preceq(x) < \lev_\preceq(y)$, $x \preceq^*
y$. Suppose $\lev_\preceq(x) = \lev_\preceq(y)$. Then $x \conflict y$,
so there exist $x', y'$ such that $\lev_\preceq(x') = \lev_\preceq(y')
= \lev_\preceq(x)$ and $x' \conflict y'$, i.e., $x' = x$ and $y' = y$,
so $x \preceq^* y$.

Now suppose $x \prec y$. Then $\lev_\preceq(x) < \lev_\preceq(y)$, so
$x \preceq^* y$ and $y \not\preceq^* x$, so $x \prec^* y$.

\item From the first part of this proposition, $\preceq \subseteq
\preceq^*$, so it suffices to show $\preceq^* \subseteq
\preceq$. Suppose $x \preceq^* y$.

{\em Case 1:} $\lev_\preceq(x) < \lev_\preceq(y)$. Then, by
Proposition~\ref{prop-lev}, there exists $z$ such that
$\lev_\preceq(z) = \lev_\preceq(x)$ and $z \prec y$. By modularity, $z
\preceq x$ or $x \preceq y$. In the latter case, we're done. In the
former case, $z \conflict x$ otherwise $\lev_\preceq(z) \neq
\lev_\preceq(x)$. Thus, $x \preceq y$ by transitivity.

{\em Case 2:} $\lev_\preceq(x) = \lev_\preceq(y)$. Then there exist
$x', y'$ such that $\lev_\preceq(x') = \lev_\preceq(y') =
\lev_\preceq(x)$ and $x' \conflict y'$. By modularity, $x' \preceq x$
or $x \preceq y'$. In the former case $x' \conflict x$ by
Proposition~\ref{prop-lev}, in the latter $x' \conflict x$ by
Proposition~\ref{prop-lev} and transitivity. By modularity, $x'
\preceq y$ or $y \preceq x$. Again applying Proposition~\ref{prop-lev}
and transitivity, we have $x \conflict y$, so $x \preceq y$.

\item We prove by induction on the level of $x$ in $\preceq$.

{\em Base case:} $\lev_\preceq(x) = 0$. Then $x \in \C(\mcw,
\preceq)$. Suppose $y \preceq^* x$. Then $\lev_\preceq(x) =
\lev_\preceq(y)$ and there exist $x'$ and $y'$ such that
$\lev_\preceq(x') = \lev_\preceq(y') = \lev_\preceq(x) =
\lev_\preceq(y)$ and $x' \conflict y'$, so $x \preceq^* y$. Thus, $x
\in \C(\mcw, \preceq^*)$, so $\lev_{\preceq^*}(x) = 0 =
\lev_\preceq(x)$.

{\em Inductive case:} Assume that $\lev_{\preceq^*}(x') =
\lev_\preceq(x')$ for all $x'$ such that $\lev_\preceq(x') <
\lev_\preceq(x)$; we show that $\lev_{\preceq^*}(x) =
\lev_\preceq(x)$. Let $z = \arg\max\limits_{y' \in
\mcw}\left(\left\{\lev_{\preceq^*}(y') : y' \prec^* x\right\}\right)$;
then $\lev_{\preceq^*}(x) = 1 + \lev_{\preceq^*}(z)$. Also, let $y =
\arg\max\limits_{y' \in \mcw}\left(\left\{\lev_\preceq(y') : y' \prec
x\right\}\right)$; then $\lev_\preceq(x) = 1 + \lev_\preceq(y)$. By
the first part of this proposition, $\prec \subseteq \prec^*$, so $y
\prec^* x$. Thus, $\lev_{\preceq^*}(z) \geq
\lev_{\preceq^*}(y)$. Furthermore, $\lev_{\preceq^*}(y) =
\lev_\preceq(y)$ by the inductive hypothesis, so $\lev_{\preceq^*}(z)
\geq \lev_\preceq(y)$. Now $\lev_\preceq(z) < \lev_\preceq(x)$ by
Definition~\ref{def-MC} (otherwise $x \preceq^* z$, a
contradiction). By the inductive hypothesis, $\lev_{\preceq^*}(z) =
\lev_\preceq(z)$, so $\lev_{\preceq^*}(z) < \lev_\preceq(x) = 1 +
\lev_\preceq(y)$. Since levels are integral, $\lev_{\preceq^*}(z) \leq
\lev_\preceq(y)$, so $\lev_{\preceq^*}(z) = \lev_\preceq(y)$. Thus,
$\lev_{\preceq^*}(x) = 1 + \lev_{\preceq^*}(z) = 1 + \lev_\preceq(y) =
\lev_\preceq(x)$.

\item Suppose $\preceq' \in \mcb$, $\preceq \subseteq \preceq'$, and
$\lev_{\preceq'}(z) = \lev_{\preceq}(z)$ for all $z \in \mcw$. It is
clear that for any $\preceq'' \in \mcb$ and $x \in \mcw$, $x$ is in
the partition corresponding to its level, i.e.,
$W_{\lev_{\preceq''}(x)}$. Since both $\preceq^*$ and $\preceq'$ are
both in $\mcb$ and both preserve the levels of all worlds in
$\preceq$, the must have identical partitions. Suppose $x, y \in \mcw$
and $W_i$ and $W_j$ are the partitions (for both $\preceq^*$ and
$\preceq'$) such that $x \in W_i$ and $y \in W_j$.

Suppose $x \preceq^* y$. If $W_i \neq W_j$ then $i < j$ by
Proposition~\ref{prop-rep}, so $x \preceq' y$, again by
Proposition~\ref{prop-rep}. If, instead $W_i = W_j$, then
$\lev_{\preceq^*}(x) = \lev_{\preceq^*}(y)$. By
Definition~\ref{def-MC}, there exist $x', y' \in \mcw$ such that
$\lev_{\preceq^*}(x') = \lev_{\preceq^*}(y') = \lev_{\preceq^*}(x)$
and $x' \conflict y'$. Thus, $x', y' \in W_i$ and, since $\preceq
\subseteq \preceq'$, $x' \conflict' y'$. By
Proposition~\ref{prop-rep}, $W_i$ is either fully connected or fully
disconnected in $\preceq'$, so $W_i$ must be fully connected in
$\preceq'$. In particular, $x \preceq' y$.

\end{enumerate}
\qed
\end{pf}

\begin{prop}
	If $\preceq$ is a relation over $\mcw$, then
	\mbox{$\MT(\preceq) \in \mcb$}.
\end{prop}
\begin{pf}
Since $\preceq^+$ is transitive, $\MT(\preceq) =
\MC\left(\preceq^+\right) \in \mcb$ by Proposition~\ref{prop-MCisBS}.
\qed
\end{pf}

\begin{prop}
	Suppose $\preceq$ is a relation over $\mcw$ and $\preceq^* =
	\MT(\preceq)$.
	\begin{enumerate}

	\item \mbox{$\preceq \subseteq \preceq^*$}.

	\item If $\preceq$ is transitive, then \mbox{$\preceq^* =
	\MC(\preceq)$}.

	\item If $\preceq$ is modular, then \mbox{$\preceq^* =
	\preceq^+$}.

	\item If $\preceq$ is modular and transitive, then
	\mbox{$\preceq^* = \preceq$}.

	\item If $\preceq$ has no conflicts, then neither does
	\mbox{$\preceq^*$}.

	\end{enumerate}
\end{prop}
\begin{pf}
Let $x, y \in \mcw$.
\begin{enumerate}

\item $\preceq \subseteq \preceq^+$ and, by the first property of
Proposition~\ref{prop-MC-add}, $\preceq^+ \subseteq \MC(\preceq^+) =
\preceq^*$, so $\preceq \subseteq \preceq^*$.

\item Since $\preceq$ is transitive, $\preceq^+ = \preceq$. Thus,
$\preceq^* = \MC(\preceq^+) = MC(\preceq)$.

\item Since $\preceq$ is modular, $\preceq^+$ is modular by
Proposition~\ref{prop-Props} so, by Proposition~\ref{prop-MC-add},\linebreak
\mbox{$\MC(\preceq^+) = \preceq^+$}. Thus, $\preceq^* = \preceq^+$.

\item Since $\preceq$ is transitive, $\preceq^* = \MC(\preceq)$ and
since $\preceq$ is modular, $\MC(\preceq) = \preceq$ by
Proposition~\ref{prop-MC-add}, so $\preceq^* = \preceq$.

\item We first prove the following lemma:

\begin{lem}
  $x$ and $y$ are in conflict wrt $\preceq^+$ iff they are in conflict
  wrt $\preceq$.
\end{lem}
\begin{pf}
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 $\preceq^+$. Then there exist
$w_0, \ldots, w_n, z_0, \ldots, z_m \in \mcw$ such that
\begin{displaymath}
  x = w_0 \preceq^+ \cdots \preceq^+ w_n = y = z_0 \preceq^+ \cdots
     \preceq^+ z_m = x.
\end{displaymath}
But then, for each $0 \leq i \leq n-1$, there exist $w_{i0}, \ldots,
w_{ip_i} \in \mcw$ such that
\begin{displaymath}
  w_i = w_{i0} \preceq \cdots \preceq w_{ip_i} = w_{i+1}.
\end{displaymath}
Similarly, for each $0 \leq j \leq m-1$, there exist $z_{j0}, \ldots,
z_{jq_j} \in \mcw$ such that
\begin{displaymath}
  z_j = z_{j0} \preceq \cdots \preceq z_{jq_j} = z_{j+1}.
\end{displaymath}
Thus,
\begin{displaymath}
  x = w_0 \preceq \cdots \preceq w_n = y = z_0 \preceq \cdots \preceq
     z_m = x,
\end{displaymath}
so $x$ and $y$ are in conflict wrt $\preceq$.
\qed
\end{pf}

Now, suppose $x$ and $y$ are in conflict wrt $\preceq^*$. Then $x
\conflict^* y$ since $\preceq^* \in \mcb$ by
Proposition~\ref{prop-MTisBS}. By Propositions~\ref{prop-lev} and
\ref{prop-MC-add},
\begin{displaymath}
  \lev_{\preceq^+}(x) = \lev_{\preceq^*}(x) = \lev_{\preceq^*}(y) =
     \lev_{\preceq^+}(y)
\end{displaymath}
So, since $x \preceq^* y$, there exist $x', y' \in \mcw$ such that
$\lev_{\preceq^+}(x') = \lev_{\preceq^+}(y') = \lev_{\preceq^+}(x)$
and $x' \conflict^+ y'$ by Definition~\ref{def-MC}. Thus, $\preceq^+$
has a conflict. By the lemma above, $\preceq$ must also have a
conflict.

\end{enumerate}
\qed
\end{pf}

\begin{prop}
	If \mbox{$S \subseteq \mcs$} and \mbox{$p \in [0,1]$}, then
	\mbox{$\AGREq_p(S) \in \mcb$}.
\end{prop}
\begin{pf}
Follows immediately from the definition of $\AGREq_p$ and
Proposition~\ref{prop-MTisBS}.
\qed
\end{pf}

\begin{prop}
        If $S \subseteq \mcs$ and $p \in [0,1]$, then $\AGR_p(S) \in
        \mcb$.
\end{prop}
\begin{pf}
Again, this follows immediately from Proposition~\ref{prop-MTisBS}.
\qed
\end{pf}

\begin{prop}
        Suppose $S \subseteq \mcs$ and $p \in [0,1]$.
	\begin{enumerate}

	\item If $\sqsupseteq_S$ is fully connected, then
	$\AGR_p(S) = \AGREq_p(S)$.

	\item If $\sqsupseteq_S$ is a total order, then $\AGR_p(S) =
	\AGRRf_p(S) = \AGRRf(S) = \AGR(S)$.

	\item $\AGR_0(S) = \AGR(S)$.

	\end{enumerate}

\end{prop}
\begin{pf}
Assume $x, y \in \mcw$.
\begin{enumerate}

\item It suffices to show that $\AGRRf_p(S) = \vt_p(S)$ when
$\sqsupseteq_S$ is fully connected. Suppose $(x,y) \in
\AGRRf_p(S)$. Then, by the definition of $\AGRRf_p$, there exists $s \in
S$ such that $(x,y) \in \vt_p(\{s' \in S : s' \sqeq_S s\})$. Since
$\sqsupseteq_S$ is fully connected, $\{s' \in S : s' \sqeq_S s\} = S$,
so $(x,y) \in \vt_p(S)$.

Suppose, instead, $(x,y) \in \vt_p(S)$. By the definition of $\vt_p$,
$\cnt_S(x,y) > 0$ so there exists $s \in S$ such that $x <^s y$. Pick
one such $s$. Again, $\{s' \in S : s' \sqeq_S s\} = S$ since
$\sqsupseteq_S$ is fully connected, so $(x,y) \in \vt_p(\{s' \in S :
s' \sqeq_S s\})$. Finally, $\forall s' \in S.\ s' \sqsupset_S s
\implies x \sagnost^{s'} y$ holds vacuously, so $(x,y) \in
\AGRRf_p(S)$.

\item Suppose $\sqsupseteq_S$ is a total order. We have already shown
in Proposition~\ref{prop-AGRSpecial} that\linebreak
\mbox{$\AGRRf(S) = \AGR(S)$}.

Next we show that $\AGRRf_p(S) = \AGRRf(S)$. $\AGRRf_p(S)$ is the set
$(x,y)$ such that there exists $s \in S$ such that $x <^s y$, $(x,y)
\in \vt_p(\{s' \in S : s' \sqeq_S s\})$, and, for all $s' \sqsupset_S
s \in S$, $x \sagnost^{s'} y$. $\sqsupseteq$ is a total order, $\{s'
\in S : s' \sqeq_S s\} = \{s\}$. Since $x <^s y$, so
$\cnt_{\{s\}}(x,y) = 1 > 0$ and $\cnt_{\{s\}}(x,y)/\|\{s\}\| = 1 \geq
p$. Consequently, $(x,y) \in \vt_p(\{s' \in S : s' \sqeq_S s\})$,
proving that this requirement is redundant when $\sqsupseteq_S$ is a
total order. Thus, $\AGRRf_p(S)$ is the set $(x,y)$ such that $x <^s
y$ and, for all $s' \sqsupset_S s \in S$, $x \sagnost^{s'} y$, i.e.,
$\AGRRf_p(S) = \AGRRf(S)$.

Finally, $\AGR_p(S) = \MT(\AGRRf_p(S)) = \MT(\AGRRf(S))$. By
Proposiion~\ref{prop-AGRRf},\linebreak
$\AGRRf(S)$ is modular and transitive, so
$\AGR_p(S) = \AGRRf(S)$ by Proposition~\ref{prop-MTisMin}.

\item It suffices to show that $\AGRRf_0(S) = \AGRRf(S)$, since then
\begin{displaymath}
  \AGR_0(S) = \MT(\AGRRf_0(S)) = \MT(\AGRRf(S)) = \AGRRf(S)^+
\end{displaymath}
by Propositions~\ref{prop-AGRRfModnotT} and \ref{prop-MTisMin}, so
$\AGR_0(S) = \AGR(S)$.

Suppose $(x,y) \in \AGRRf_0(S)$. Then $x <^s y$ and, for all $s'
\sqsupset_S s \in S$, $x \sagnost^{s'} y$, so $(x,y) \in
\AGRRf(S)$. Suppose, instead, $(x,y) \in \AGRRf(S)$. Then $x <^s y$
and, for all $s' \sqsupset_S s \in S$, $x \sagnost^{s'} y$. Let $S' =
\{s' \in S : s' \sqeq_S s\}$. Since $x <^s y$ and $s \in S'$,
$\cnt_{S'}(x,y) > 0$ and $\cnt_{S'}(x,y)/\|S'\| \geq 0$, so $(x,y) \in
\vt_0(S')$. Therefore, $(x,y) \in \AGRRf_0(S)$.

\end{enumerate}
\qed
\end{pf}

\begin{cor}
	Let \mbox{$S = \{s_1, \ldots, s_n\} \subseteq \mcs$} and
	\mbox{$\AGR_f(<^{s_1}, \ldots, <^{s_n}) =
	\AGR_0(S)$}. \mbox{$\AGR_f$} satisfies (the modified versions
	of) restricted range, unrestricted domain, Pareto principle,
	IIA, and non-dictatorship.
\end{cor}
\begin{pf}
Follows immediately from Propositions~\ref{prop-AGRpSpecial} and
\ref{prop-Arrow2}.
\qed
\end{pf}

%\begin{prop}
%	Let \mbox{$S = \{s_1, \ldots, s_n\} \subseteq \mcs$}, \mbox{$0
%	< p \leq 1$}, and \mbox{$\AGR_f(<^{s_1}, \ldots, <^{s_n}) =
%	\AGR_p(S)$}. \mbox{$\AGR_f$} satisfies (the modified versions
%	of) restricted range, unrestricted domain, Pareto principle,
%	and non-dictatorship.
%\end{prop}
%\begin{pf}
%
%\fix{TO DO}
%
%\qed
%\end{pf}

\begin{prop}
 	Let $A$ be an agent informed by a set of sources \mbox{$S
	\subseteq \mcs$}, with support pedigreed belief state
	\mbox{$(l, \supp, \rtab)$}, and using aggregation function
	\mbox{$AGR_p$} for \mbox{$p \in [0, 1]$}. $A$'s belief state
	is the relation
	\begin{displaymath}
	    \MT\left(\left\{(x, y) : \|\supp(x,y)\| > 0\ \mbox{and}\
	      \|\supp(x,y)\|/\|\rtab(l(x,y))\| \geq p\right\}\right)
	\end{displaymath}
\end{prop}
\begin{pf}
Let
\begin{displaymath}
  R = \left\{(x, y) : \|\supp(x,y)\| > 0\ \mbox{and}\
	      \|\supp(x,y)\|/\|\rtab(l(x,y))\| \geq p\right\}
\end{displaymath}
It suffices to show $\AGRRf_p(S) = R$. Suppose $(x, y) \in
\AGRRf_p(S)$. Then there exists $s \in S$ such that (a) $x <^s y$, (b)
$(x,y) \in \vt_p(\{s' \in S : s' \sqeq_S s\})$, and (c) for all $s'
\sqsupset_S s \in S$, $x \sagnost^{s'} y$. By the (a) and (c), $\rank(s)
= \max(\{\rank(s) : x \not\sagnost^s y,\ s \in S\} \cup \{\clubsuit\})$, so
$l(x,y) = \rank(s)$. Thus, $\{s' \in S : s' \sqeq_S s\} = \{s' \in S :
\rank(s') = l(x,y)\} = \rtab(l(x,y))$, so $(x,y) \in
\vt_p(\rtab(l(x,y)))$ by (b). By the definition of $\vt_p$,
$\cnt_{\rtab(l(x,y))}(x,y) > 0$ and
$\cnt_{\rtab(l(x,y))}(x,y)/\|\rtab(l(x,y))\| \geq p$. But $\supp(x,y)
= \{s' \in S : \rank(s') = l(x, y),\ x <^{s'} y\} = \{s' \in \rtab(l(x,y)) :
x <^{s'} y\}$, so $\|\supp(x,y)\| = \cnt_{\rtab(l(x,y))}(x,y)$. Thus,
$\|\supp(x,y)\| > 0$ and $\|\supp(x,y)\|/\|\rtab(l(x,y))\| \geq p$, so
$(x,y) \in R$.

Now suppose $(x,y) \in R$. Then (a) $\|\supp(x,y)\| > 0$ and (b)
$\|\supp(x,y)\|/\|\rtab(l(x,y))\| \geq p$. Suppose $s \in \supp(x,y)$;
by (a), at least one such $s$ exists. By the definition of $\supp$, $x
<^s y$, satisfying the first condition of $\AGRRf_p$, and $\rank(s) =
l(x, y)$. By the definition of $l(x,y)$, $\rank(s) = \max(\{\rank(s) :
x \not\sagnost^s y,\ s \in S\} \cup \{\clubsuit\})$, so for all $s' \in S$ such
that $\rank(s') > \rank(s)$ (i.e., $s' \sqsupset_S s$), $x \sagnost^{s'}
y$. It only remains to show that $(x,y) \in \vt_p(\{s' \in S : s'
\sqeq_S s\})$. Since $\rank(s) = l(x,y)$, $\{s' \in S : s' \sqeq_S s\} =
\rtab(l(x,y))$ as we showed above, so
\begin{eqnarray*}
  \lefteqn{\vt_p(\{s' \in S : s' \sqeq_S s\})} \\
      & = & \vt_p(\rtab(l(x,y))) \\
      & = & \{(x', y') : \cnt_{\rtab(l(x,y))}(x',y') > 0,\
         \cnt_{\rtab(l(x,y))}(x',y')/\|\rtab(l(x,y))\| \geq p\}.
\end{eqnarray*}
As we showed above, $\|\supp(x,y)\| =
\cnt_{\rtab(l(x,y))}(x,y)$. Making this substitution into (a) and (b),
we see that $(x,y) \in \vt_p(\{s' \in S : s' \sqeq_S s\})$, so $(x,y)
\in \AGRRf_p(S)$.
\qed
\end{pf}

\begin{prop}
	Let $\mca$, $\mcp_\mca$, $S$, and $\sqsupseteq_S$ be as in
	Definition~\ref{def-spfusion}. Then $\spfuse(\mcp_\mca)$ is
	the support pedigreed belief state of \mbox{$\fuse(\mca)$}.
\end{prop}
\begin{pf}
Let $\spfuse(\mcp_\mca) = (l, \supp, \rtab)$, $l' : \mcw \times \mcw
\to \mcr \cup \{\clubsuit\}$ such that
\begin{displaymath}
  l'((x,y)) = \max(\{l''(x,y) : (l'', \supp'', \rtab'') \in
    \mcp_\mca\}),
\end{displaymath}
$\supp' : \mcw \times \mcw \to 2^S$ such that
\begin{displaymath}
  \supp'(x,y) = \bigcup_{(l'', \supp'', \rtab'') \in \mcp_\mca,\
    l''(x,y) = l'(x,y)} \supp''(x,y),
\end{displaymath}
and $\rtab' : \ranks(S) \to \mathbb{R}$ such that
\begin{displaymath}
  \rtab'(r) = \bigcup_{(l'', \supp'', \rtab'') \in \mcp_\mca,\ r \in
    \mr{range}(\rtab'')} \rtab''(r).
\end{displaymath}
It suffices to show that $l = l'$, $\supp = \supp'$, and $\rtab =
\rtab'$.

Suppose $x, y \in \mcw$ and agent $A_i$'s support pedigreed belief
state is $(l_i, \supp_i, \rtab_i)$.
\begin{eqnarray*}
  l(x,y) & = & \max(\{\rank(s) : x <^s y,\ s \in S\} \cup
        \{\clubsuit\}) \\
     & = & \max\left(\bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca}
        \left(\left\{\rank(s) : x <^s y,\ s \in S_i\right\} \cup
        \{\clubsuit\}\right)\right) \\
     & = & \max\left(\bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca}
        \left\{\max\left(\left\{\rank(s) : x <^s y,\ s \in S_i\right\} \cup
        \{\clubsuit\}\right)\right\}\right) \\
     & = & \max(\{l''(x,y) : (l'', \supp'', \rtab'') \in \mcp_\mca\}) \\
     & = & l'(x,y).
\end{eqnarray*}
Also,
\begin{eqnarray*}
  \supp(x,y) & = & \{s \in S : \rank(s) = l(x, y),\ x <^s y\} \\
     & = & \bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca} \{s \in
        S_i : \rank(s) = l(x, y),\ x <^s y\} \\
     & = &  \bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca} \{s \in
        S_i : \rank(s) = l'(x, y),\ x <^s y\} \\
     & = &  \bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca,\ l_i(x,y)
        = l'(x,y)} \{s \in S_i : \rank(s) = l_i(x, y),\ x <^s y\} \\
     & = & \bigcup_{(l'', \supp'', \rtab'') \in \mcp_\mca,\ l''(x,y) =
        l'(x,y)} \supp''(x,y) \\
     & = & \supp'(x,y).
\end{eqnarray*}
Finally,
\begin{eqnarray*}
  \rtab(r) & = & \{s \in S : \rank(s) = r\} \\
     & = & \bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca} \{s \in S_i
        : \rank(s) = r\} \\
     & = & \bigcup_{S_i\ \mbox{informs}\ A_i,\ A_i \in \mca,\ r \in
        \mr{range}(\rtab_i)} \rtab_i(r) \\
     & = & \bigcup_{(l'', \supp'', \rtab'') \in \mcp_\mca,\ r \in
        \mr{range}(\rtab'')} \rtab''(r) \\ 
     & = & \rtab'(x,y).
\end{eqnarray*}
\qed
\end{pf}

%\newpage

%%%%%%%%%%%%
% Notation %
%%%%%%%%%%%%

\section{Notation key}\label{sec:notation}
%	 ____________

$\Omega$: arbitrary finite set \\
$a, b, c, \ldots$: specific elements of a set \\
$x, y, z, \ldots$: arbitrary elements of a set \\
$A, B, C, \ldots$: specific subsets of a set \\
$X, Y, Z, \ldots$: arbitrary subsets of a set \\
$\Pi$: arbitrary set of relations \\
$\leq$: arbitrary relation \\
$\leq^+$: transitive closure of $\leq$ \\
$\C(X, \leq)$: choice set of $X$ wrt $\leq$ \\
$\|X\|$: cardinality of set $X$ \\

\noindent
$\mcw$: finite set of possible worlds \\
$w$, $W$: element, subset of $\mcw$, respectively \\

\noindent
$\mcb$: set of generalized belief states (modular, transitive
	relations) \\
$\prec$: element of $\mcb$, strict likelihood \\
$\preceq$: weak likelihood \\
$\agnost$: equal likelihood, agnosticism \\
$\conflict$: conflict \\
$\Bel$: belief of a conditional statement \\
$\Agn$: agnosticism over a conditional statement \\
$\Con$: conflict over a conditional statement \\

\noindent
$\mct$: set of total preorders \\
$\mcst$: strict versions of total preorders \\
$\mcq$: set of total, quasi-transitive relations \\
$\mcsq$: strict versions of total, quasi-transitive relations \\

\noindent
$\mcs$: set of sources \\
$s$, $S$: element, subset of $\mcs$, respectively \\
$<^s$: belief state of source $s$ \\
$\sagnost^s$: source agnosticism \\
$\sconflict^s$: source conflict \\
$\mcr$: set of ranks \\
$r$: element of $\mcr$ \\
$\rank(s)$: rank of source $s$ \\
$\ranks(S)$: set of ranks of sources in $S$ \\
$\sqsupseteq$, $\sqsupseteq_S$: credibility ordering over $\mcs$, $S
	\subseteq \mcs$, respectively \\

\noindent
$\Un$: union of a set of belief states \\
$\AGRUn$: aggregation via union \\
$\AGRRf$: aggregation via refinement \\
$\AGR$: general aggregation \\

\noindent
$\mca$: set of agents \\
$A$: element of $\mca$ \\
$\prec^A$: $A$'s induced belief state \\
$(\prec, l)$: pedigreed belief state \\
$\prec^A_r$: restriction of $A$'s pedigreed belief state to rank $r$ \\
$\fuse$: fusion \\
$\pfuse$: pedigreed fusion \\

\noindent
$\vt_p$: voting function for $p$ \\
$\lev$: level of a world in a transitive relation \\
$\MC$: modular closure \\
$\MT$: modular, transitive closure \\
$\AGREq_p$: aggregation with voting without refinement \\
$\AGRRf_p$: aggregation with voting via refinement \\
$\AGR_p$: general aggregation with voting \\
$(l, \supp, \rtab)$: support pedigreed belief state \\
$\spfuse$: support pedigreed fusion

\end{appendix}

%\newpage


%%%%%%%%%%%%%%%%
% Bibliography %
%%%%%%%%%%%%%%%%

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Alchourr\'{o}n, G\"{a}rdenfors,\ \BBA\
  Makinson}{Alchourr\'{o}n et~al.}{1985}]{AGM85}
Alchourr\'{o}n, C.~E., G\"{a}rdenfors, P., \BBA\ Makinson, D. \BBOP1985\BBCP.
\newblock \BBOQ On the logic of theory change: Partial meet contraction and
  revision functions\BBCQ\
\newblock {\Bem Journal of Symbolic Logic}, {\Bem 50}, 510--530.

\bibitem[\protect\BCAY{Andr\'{e}ka, Ryan,\ \BBA\ Schobbens}{Andr\'{e}ka
  et~al.}{2002}]{ARS02}
Andr\'{e}ka, H., Ryan, M., \BBA\ Schobbens, P.-Y. \BBOP2002\BBCP.
\newblock \BBOQ Operators and laws for combining preference relations\BBCQ\
\newblock {\Bem Journal of Logic and Computation}, {\Bem 12\/}(1), 13--53.

\bibitem[\protect\BCAY{Arrow}{Arrow}{1963}]{Arrow63}
Arrow, K.~J. \BBOP1963\BBCP.
\newblock {\Bem Social Choice and Individual Values\/} (2nd \BEd).
\newblock Wiley, New York.

\bibitem[\protect\BCAY{Baral, Kraus, Minker,\ \BBA\ Subrahmanian}{Baral
  et~al.}{1992}]{BKMS92}
Baral, C., Kraus, S., Minker, J., \BBA\ Subrahmanian, V.~S. \BBOP1992\BBCP.
\newblock \BBOQ Combining knowledge bases consisting of first-order
  theories\BBCQ\
\newblock {\Bem Computational Intelligence}, {\Bem 8\/}(1), 45--71.

\bibitem[\protect\BCAY{Benferhat, Dubois, Kaci,\ \BBA\ Prade}{Benferhat
  et~al.}{2002}]{BDKP02}
Benferhat, S., Dubois, D., Kaci, S., \BBA\ Prade, H. \BBOP2002\BBCP.
\newblock \BBOQ Possibilistic merging and distance-based fusion of
  propositional information\BBCQ\
\newblock {\Bem Annals of Mathematics and Artificial Intelligence}, {\Bem
  34\/}(1--3), 217--252.

\bibitem[\protect\BCAY{Black}{Black}{1958}]{Black58}
Black, D. \BBOP1958\BBCP.
\newblock {\Bem The Theory of Committees and Elections}.
\newblock Cambridge University Press, Cambridge.

\bibitem[\protect\BCAY{Borgida\ \BBA\ Imielinski}{Borgida\ \BBA\
  Imielinski}{1984}]{BI84}
Borgida, A.\BBACOMMA\  \BBA\ Imielinski, T. \BBOP1984\BBCP.
\newblock \BBOQ Decision making in committees: A framework for dealing with
  inconsistency and non-monotonicity\BBCQ\
\newblock In {\Bem Proceedings of the Workshop on Nonmonotonic Reasoning},
  \BPGS\ 21--32.

\bibitem[\protect\BCAY{Boutilier}{Boutilier}{1996}]{Boutilier96}
Boutilier, C. \BBOP1996\BBCP.
\newblock \BBOQ Iterated revision and minimal change of conditional
  beliefs\BBCQ\
\newblock {\Bem Journal of Philosophical Logic}, {\Bem 25}, 263--305.

\bibitem[\protect\BCAY{Brams\ \BBA\ Fishburn}{Brams\ \BBA\
  Fishburn}{2002}]{BF02}
Brams, S.~J.\BBACOMMA\  \BBA\ Fishburn, P.~C. \BBOP2002\BBCP.
\newblock \BBOQ Voting procedures\BBCQ\
\newblock In Arrow, K.~J., Sen, A.~K., \BBA\ Suzumura, K.\BEDS, {\Bem Handbook
  of Social Choice and Welfare}, \lowercase{\BVOL}~1 of {\Bem Handbooks in
  Economics}, \BCH~4, \BPGS\ 173--236. Elsevier Science.

\bibitem[\protect\BCAY{Cantwell}{Cantwell}{1998}]{Cantwell98}
Cantwell, J. \BBOP1998\BBCP.
\newblock \BBOQ Resolving conflicting information\BBCQ\
\newblock {\Bem Journal of Logic, Language, and Information}, {\Bem 7},
  191--220.

\bibitem[\protect\BCAY{{Center for Voting and Democracy}}{{Center for Voting
  and Democracy}}{2002}]{CVDIRV}
{Center for Voting and Democracy} \BBOP2002\BBCP.
\newblock \BBOQ Instant runoff voting\BBCQ\
\newblock http://www.fairvote.org/irv/.

\bibitem[\protect\BCAY{Darwiche\ \BBA\ Pearl}{Darwiche\ \BBA\
  Pearl}{1997}]{DP97}
Darwiche, A.\BBACOMMA\  \BBA\ Pearl, J. \BBOP1997\BBCP.
\newblock \BBOQ On the logic of iterated belief revision\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 89\/}(1--2), 1--29.

\bibitem[\protect\BCAY{Fishburn}{Fishburn}{1974}]{Fishburn74}
Fishburn, P.~C. \BBOP1974\BBCP.
\newblock \BBOQ Lexicographic orders, utilities and decision rules: A
  survey\BBCQ\
\newblock {\Bem Management Science}, {\Bem 20\/}(11), 1442--1471.

\bibitem[\protect\BCAY{G\"{a}rdenfors}{G\"{a}rdenfors}{1988}]{Gardenfors88}
G\"{a}rdenfors, P. \BBOP1988\BBCP.
\newblock {\Bem Knowledge in Flux: Modeling the Dynamics of Epistemic States}.
\newblock MIT Press.

\bibitem[\protect\BCAY{G\"{a}rdenfors\ \BBA\ Makinson}{G\"{a}rdenfors\ \BBA\
  Makinson}{1994}]{GM94}
G\"{a}rdenfors, P.\BBACOMMA\  \BBA\ Makinson, D. \BBOP1994\BBCP.
\newblock \BBOQ Nonmonotonic inference based on expectations\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 65\/}(1), 197--245.

\bibitem[\protect\BCAY{G\"{a}rdenfors\ \BBA\ Rott}{G\"{a}rdenfors\ \BBA\
  Rott}{1995}]{GR95}
G\"{a}rdenfors, P.\BBACOMMA\  \BBA\ Rott, H. \BBOP1995\BBCP.
\newblock \BBOQ Belief revision\BBCQ\
\newblock In Gabbay, D.~M., Hogger, C.~J., \BBA\ Robinson, J.~A.\BEDS, {\Bem
  Epistemic and Temporal Reasoning}, \lowercase{\BVOL}~4 of {\Bem Handbook of
  Logic in Artificial Intelligence and Logic Programming}, \BPGS\ 35--132.
  Oxford University Press, Oxford.

\bibitem[\protect\BCAY{Grosof}{Grosof}{1991}]{Grosof91}
Grosof, B. \BBOP1991\BBCP.
\newblock \BBOQ Generalizing prioritization\BBCQ\
\newblock In {\Bem Proceedings of the Second International Conference on
  Principles of Knowledge Representation and Reasoning (KR '91)}, \BPGS\
  289--300.

\bibitem[\protect\BCAY{Grove}{Grove}{1988}]{Grove88}
Grove, A. \BBOP1988\BBCP.
\newblock \BBOQ Two modellings for theory change\BBCQ\
\newblock {\Bem Journal of Philosophical Logic}, {\Bem 17}, 157--170.

\bibitem[\protect\BCAY{Kahneman\ \BBA\ Tversky}{Kahneman\ \BBA\
  Tversky}{1979}]{KT79}
Kahneman, D.\BBACOMMA\  \BBA\ Tversky, A. \BBOP1979\BBCP.
\newblock \BBOQ Prospect theory: An analysis of decision under risk\BBCQ\
\newblock {\Bem Econometrica}, {\Bem 47\/}(2), 263--291.

\bibitem[\protect\BCAY{Katsuno\ \BBA\ Mendelzon}{Katsuno\ \BBA\
  Mendelzon}{1991}]{KM91}
Katsuno, H.\BBACOMMA\  \BBA\ Mendelzon, A.~O. \BBOP1991\BBCP.
\newblock \BBOQ Propositional knowledge base revision and minimal change\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 52\/}(3), 263--294.

\bibitem[\protect\BCAY{Konieczny\ \BBA\ P\'erez}{Konieczny\ \BBA\
  P\'erez}{1998}]{KP98}
Konieczny, S.\BBACOMMA\  \BBA\ P\'erez, R.~P. \BBOP1998\BBCP.
\newblock \BBOQ On the logic of merging\BBCQ\
\newblock In {\Bem Proceedings of the Sixth International Conference on
  Principles of Knowledge Representation and Reasoning (KR '98)}, \BPGS\
  488--498.

\bibitem[\protect\BCAY{Kraus, Lehmann,\ \BBA\ Magidor}{Kraus
  et~al.}{1990}]{KLM90}
Kraus, S., Lehmann, D., \BBA\ Magidor, M. \BBOP1990\BBCP.
\newblock \BBOQ Nonmonotonic reasoning, preferential models and cumulative
  logics\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 44\/}(1--2), 167--207.
\newblock CoRR: cs.AI/0202021.

\bibitem[\protect\BCAY{Kreps}{Kreps}{1990}]{Kreps90}
Kreps, D.~M. \BBOP1990\BBCP.
\newblock {\Bem A Course in Microeconomic Theory}.
\newblock Princeton University Press.

\bibitem[\protect\BCAY{Lehmann}{Lehmann}{1995}]{Lehmann95}
Lehmann, D. \BBOP1995\BBCP.
\newblock \BBOQ Belief revision, revised\BBCQ\
\newblock In {\Bem Proceedings of the Fourteenth International Joint Conference
  of Artificial Intelligence (IJCAI '95)}, \BPGS\ 1534--1540.

\bibitem[\protect\BCAY{Lehmann\ \BBA\ Magidor}{Lehmann\ \BBA\
  Magidor}{1992}]{LM92}
Lehmann, D.\BBACOMMA\  \BBA\ Magidor, M. \BBOP1992\BBCP.
\newblock \BBOQ What does a conditional knowledge base entail?\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 55\/}(1), 1--60.
\newblock CoRR: cs.AI/0202022.

\bibitem[\protect\BCAY{Liberatore\ \BBA\ Schaerf}{Liberatore\ \BBA\
  Schaerf}{1995}]{LS95}
Liberatore, P.\BBACOMMA\  \BBA\ Schaerf, M. \BBOP1995\BBCP.
\newblock \BBOQ Arbitration: A commutative operator for belief revision\BBCQ\
\newblock In {\Bem Proceedings of the Second World Conference on the
  Fundamentals of Artificial Intelligence (WOCFAI '95)}, \BPGS\ 217--228.

\bibitem[\protect\BCAY{Luce}{Luce}{1956}]{Luce56}
Luce, D.~R. \BBOP1956\BBCP.
\newblock \BBOQ Semiorders and a theory of utility discrimination\BBCQ\
\newblock {\Bem Econometrica}, {\Bem 24\/}(2), 178--191.

\bibitem[\protect\BCAY{Makinson}{Makinson}{1997}]{Makinson97}
Makinson, D.~C. \BBOP1997\BBCP.
\newblock \BBOQ Screened revision\BBCQ\
\newblock {\Bem Theoria}, {\Bem 63\/}(1--2), 14--23.
\newblock Special issue on non-prioritized belief revision.

\bibitem[\protect\BCAY{{Maynard-Reid II}\ \BBA\ Shoham}{{Maynard-Reid II}\
  \BBA\ Shoham}{2001}]{MS01}
{Maynard-Reid II}, P.\BBACOMMA\  \BBA\ Shoham, Y. \BBOP2001\BBCP.
\newblock \BBOQ Belief fusion: Aggregating pedigreed belief states\BBCQ\
\newblock {\Bem Journal of Logic, Language, and Information}, {\Bem 10\/}(2),
  183--209.

\bibitem[\protect\BCAY{Meyer}{Meyer}{2001}]{Meyer01}
Meyer, T. \BBOP2001\BBCP.
\newblock \BBOQ On the semantics of combination operations\BBCQ\
\newblock {\Bem Journal of Applied Non-Classical Logics}, {\Bem 11\/}(1--2),
  59--84.

\bibitem[\protect\BCAY{Meyer, Ghose,\ \BBA\ Chopra}{Meyer et~al.}{2001}]{MGC01}
Meyer, T., Ghose, A., \BBA\ Chopra, S. \BBOP2001\BBCP.
\newblock \BBOQ Social choice, merging and elections\BBCQ\
\newblock In Benferhat, S.\BBACOMMA\  \BBA\ Besnard, P.\BEDS, {\Bem Proceedings
  of the Sixth European Conference on Symbolic and Quantitative Approaches to
  Reasoning with Uncertainty (ECSQARU2001)}, \BPGS\ 466--477.

\bibitem[\protect\BCAY{Ramsey}{Ramsey}{1931}]{Ramsey31}
Ramsey, F.~P. \BBOP1931\BBCP.
\newblock {\Bem Foundations of Mathematics and Other Logical Essays}.
\newblock Routledge and Kegan Paul, New York.

\bibitem[\protect\BCAY{Revesz}{Revesz}{1997}]{Revesz97}
Revesz, P.~Z. \BBOP1997\BBCP.
\newblock \BBOQ On the semantics of arbitration\BBCQ\
\newblock {\Bem International Journal of Algebra and Computation}, {\Bem
  7\/}(2), 133--160.

\bibitem[\protect\BCAY{Sen}{Sen}{1986}]{Sen86}
Sen, A. \BBOP1986\BBCP.
\newblock \BBOQ Social choice theory\BBCQ\
\newblock In Arrow, K.~J.\BBACOMMA\  \BBA\ Intriligator, M.~D.\BEDS, {\Bem
  Handbook of Mathematical Economics}, \lowercase{\BVOL}\ III, \BCH~22, \BPGS\
  1073--1181. Elsevier Science Publishers.

\bibitem[\protect\BCAY{Spohn}{Spohn}{1988}]{Spohn88}
Spohn, W. \BBOP1988\BBCP.
\newblock \BBOQ Ordinal conditional functions: A dynamic theory of epistemic
  states\BBCQ\
\newblock In Harper, W.~L.\BBACOMMA\  \BBA\ Skyrms, B.\BEDS, {\Bem Causation in
  Decision, Belief Change, and Statistics, II}, \BPGS\ 105--134. Kluwer
  Academic Publishers.

\bibitem[\protect\BCAY{Williams}{Williams}{1994}]{Williams94}
Williams, M.-A. \BBOP1994\BBCP.
\newblock \BBOQ Transmutations of knowledge systems\BBCQ\
\newblock In {\Bem Proceedings of the Fourth International Conference on
  Principles of Knowledge Representation and Reasoning (KR '94)}, \BPGS\
  619--629.

\end{thebibliography}

\end{document}