# collective_belief_revision__f7992961.pdf

Journal of Artificial Intelligence Research 78 (2023) 1221-1247 Submitted 11/2023; published 12/2023

Collective Belief Revision

Theofanis I. Aravanis taravanis@upatras.gr Department of Mechanical Engineering School of Engineering University of the Peloponnese Patras 263 34, Greece

In this article, we study the dynamics of collective beliefs. As a first step, we formulate David Westlund s Principle of Collective Change (PCC) a criterion that characterizes the evolution of collective knowledge in the realm of belief revision. Thereafter, we establish a number of unsatisfiability results pointing out that the widely-accepted revision operators of Alchourr on, G ardenfors and Makinson, combined with fundamental types of merging operations including the ones proposed by Konieczny and Pino P erez as well as Baral et al. collide with the PCC. These impossibility results essentially extend in the context of belief revision the negative results established by Westlund for the operations of contraction and expansion. At the opposite of the impossibility results, we also establish a number of satisfiability results, proving that, under certain (rather strict) requirements, the PCC is indeed respected for specific merging operators. Overall, it is argued that the PCC is a rather unsuitable property for characterizing the process of collective change. Last but not least, mainly in response to the unsatisfactory situation related to the PCC, we explore some alternative criteria of collective change, and evaluate their compliance with belief revision and belief merging.

1. Introduction

An intelligent agent, either individual or collective, should be capable of gathering information about the world, and changing her state of belief in response to new evidential information.1 As a consequence, the agent should be able to implement belief change, an operation which is heavily studied in the realm of Artificial Intelligence (G ardenfors, 1988; Ferm e & Hansson, 2018). Two fundamental types of belief change are belief revision (or simply revision) and belief merging (or simply merging). Belief revision is the process by which a rational agent modifies her beliefs in the light of new information (G ardenfors, 1988), whereas, belief merging is the process by which a community of agents aggregates their beliefs, so that the collective knowledge of the community be formulated (Konieczny & P erez, 2011). To illustrate the importance of these two types of belief change, let us present the subsequent real-world

1. A collective agent could, indicatively, be an organization, a company, a scientific committee, or any multi-agent system. Yet, other, more radical, definitions of collective agency have been proposed. For instance, Minsky (1988) in his book portrays the mind of an individual agent as a society of tiny components (tiny agents), which are in fact the fundamental thinking-entities; in that sense, even a single individual can be thought of as a collective entity. We shall formally define in Section 5 the notion of collective agency adopted herein.

2023 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0.

situation related to space exploration, which at the same time highlights the motivation for this work.

Very recently, NASA s James Webb Space Telescope discovered six gigantic galaxies that emerged shortly after the Big Bang. According to experts, this is an astounding and unexpected discovery, as the uncovered galaxies have been formed at a speed that upends the current understanding of the early universe (Labb e et al., 2023).

The above scenario describes a situation where a new scientific discovery contradicts the current collective knowledge of the scientific community. In response to this contradiction, each expert of the community ought to (individually) revise her beliefs. After the revision is complete, the collective knowledge of the scientific community will have changed. The issue that will concern us in this article is whether, and under which conditions, such transitions, from an initial to a revised state of collective knowledge, satisfy certain criteria of collective belief change. While there is a substantial body of literature on the knowledge-dynamics of individuals (see (Ferm e & Hansson, 2018) or (Peppas, 2008) for two surveys on the topic), the manner in which the knowledge of collective agents evolves in response to new evidential information as illustrated in the aforementioned space-related scenario has not been studied as much. A considerable portion of works on collective knowledge focuses on its static aspects (for example on the nature, representation and attitude of collective beliefs (Gilbert, 1987, 2004; Maynard-Zhang & Lehmann, 2003; Wray, 2001)), whereas, some representative studies examining collective belief change are the works of Kfir-Dahav and Tennenholtz (1996), Malheiro, Jennings, and Oliveira (1994), Liu and Williams (2001), Paranamana, Wang, and Shafto (2022), Liu, Seligman, and Girard (2014), Tojo (2013), and Westlund (2010). From these studies, the ones of Kfir-Dahav and Tennenholtz (1996), Malheiro et al. (1994), and Liu and Williams (2001) present basic formal frameworks that model different perspectives of multi-agent belief revision. In a recent work by Paranamana et al. (2022), a theoretical framework that applies tools from Markov chain theory to analyze the evolution of societal beliefs is proposed. Liu et al. (2014), on the other hand, model the way in which the beliefs of the members of a community are influenced by their social relations. In a different vein, Tojo (2013) studies collective belief revision by means of a numerical framework of linear algebra. In our study, we shall focus on the work of David Westlund (2010), who formally addresses the problem of collective belief change, by means of well-established tools developed by Alchourr on, G ardenfors, and Makinson (1985) for modelling the dynamics of knowledge. In that work, Westlund explores the cases of contraction and expansion, which are change-operations similar in spirit to belief revision, but at the same time retain notable distinctions as a matter of fact, contraction can be defined in terms of revision, whereas, expansion is a special (degenerative) case of revision (Alchourr on et al., 1985). Confined to these change-operations, Westlund assumes that every individual of a community is rational, and, moreover, that the synthesis of individuals beliefs is employed by means of a merging operator. On these premises, he shows that interesting types of merging operators violate what he calls the Principle of Collective Change (abbreviated as PCC), a criterion that characterizes the evolution of collective knowledge (Westlund, 2010, Observations 6 10).

Collective Belief Revision

Following the route of Westlund, we study in this article the evolution of collective knowledge in the realm of belief revision; namely, in the principal case where the new information contradicts the belief corpus of each individual of a community. Accordingly, our contributions can be summarized in the following points:

By formulating Westlund s PCC in the realm of belief revision (Westlund, 2010, p. 217), we firstly establish a number of unsatisfiability results indicating that the rationality of individuals of a community formalized by the AGM model of Alchourr on et al. (1985) for belief revision and the aggregation of the beliefs of these individuals by means of fundamental merging operators including the ones of Konieczny and P erez (2002) and Baral et al. (1992) do not necessarily imply a revision of the community s collective knowledge adhering to the PCC. The obtained impossibilities essentially extend in the realm of belief revision Westlund s negative results.

At the opposite of the impossibility results, we also establish a number of satisfiability results proving that, if the individual agents of a community revise their beliefs employing operators that implement uniform belief revision (Areces & Becher, 2001; Aravanis, 2020), then the PCC is indeed respected by certain types of merging operators. These satisfiability results are of interest in their own right, but also offer a notable proof-of-concept for uniform belief revision.

Despite the obtained satisfiability results, which, as we explain, rely on strict requirements, it is argued that the PCC is a rather unsuitable property for characterizing collective belief revision.

Lastly, mainly in response to the unsatisfactory circumstance concerning the PCC, we present two alternative criteria that characterize the revision of collective knowledge, which are based on Konieczny and Pino P erez s main approach for belief merging (Konieczny & P erez, 2002). The compliance of the proposed alternative criteria of collective change with belief revision and belief merging is evaluated, and some controversial outcomes are identified, as both satisfiability and unsatisfiability results are obtained.

The remainder of this article is structured as follows. The next section introduces the formal prerequisites required for our exposition. Sections 3 and 4 present an overview of the processes of belief revision and belief merging, respectively. Thereafter, Section 5 introduces Westlund s PCC, expressed in the realm of belief revision. In Sections 6 and 7, the obtained unsatisfiability and satisfiability results concerning the PCC are presented, respectively. Section 8 explores the alluded alternative criteria of collective change, whereas, Section 9 concludes the article with a discussion on the ramifications of the derived results and some avenues of future research.

2. Formal Preliminaries

Throughout this article, we shall work with a propositional language L, built over a nonempty, finite set P of atoms (propositional variables), using the standard Boolean connectives (conjunction), (disjunction), (implication), (equivalence), (negation), and

governed by classical propositional logic. The classical consequence relation is denoted by |=. The lower-case English letters a, b and c are used to denote atoms of P. For a set of sentences Γ of L, Cn(Γ) denotes the set of all logical consequences of Γ; i.e., Cn(Γ) = φ L : Γ |= φ . An agent s corpus of beliefs shall be represented by a theory, also referred to as a belief set. A theory K is a deductively closed set of sentences of L; i.e., K = Cn(K). The set of all theories is denoted by T. For a belief set K and a sentence φ of L, K + φ denotes the set (theory) resulting from the expansion of K by φ, defined as K + φ = Cn K {φ} . A literal is an atom a P or its negation. A possible world (or simply world) r is a consistent set of literals, such that, for any atom a P, either a r or a r. The set of all possible worlds is denoted by M. For a sentence (set of sentences) φ of L, JφK is the set of all possible worlds at which φ is true. Lastly, a preorder over a set of possible worlds M is any reflexive and transitive binary relation in M. A preorder is called total iff, for any r, r M, r r or r r. The strict part of is denoted by ; i.e., r r iff r r and r r. The indifference part of is denoted by ; i.e., r r iff r r and r r. We shall call a total preorder over M indistinguishable iff, for any r, r M, r r . Lastly, min(M, ) denotes the set of all -minimal possible worlds of M; i.e., min(M, ) = n r M : for all r M, if r r, then r r o .

3. Belief Revision

The process of belief revision has been formally captured by the seminal work of Alchourr on et al. (1985). In this section, we present the axiomatic (postulational) characterization of belief revision as developed by the AGM trio, as well as its semantic characterization in terms of a special kind of total preorders over possible worlds, as subsequently developed by Katsuno and Mendelzon (1991).

3.1 Axiomatic Characterization

A revision function is a binary function that maps a belief set K and a sentence φ (also referred to as epistemic input) to a belief set K φ, representing the result of revising K by φ. We shall say that a revision function is an AGM revision function iff it satisfies the following widely-accepted rationality postulates of Alchourr on et al. (1985), known as AGM revision postulates.

(K 1) K φ is a theory of T.

(K 2) φ K φ.

(K 3) K φ K + φ.

(K 4) If φ / K, then K + φ K φ.

(K 5) If φ is consistent, then K φ is consistent.

(K 6) If Cn {φ} = Cn {ψ} , then K φ = K ψ.

(K 7) K (φ ψ) (K φ) + ψ.

(K 8) If ψ / K φ, then (K φ) + ψ K (φ ψ).

Collective Belief Revision

The AGM revision postulates circumscribe the territory of all rational strategies by means of which a belief set of an agent can be revised. Therefore, if an agent employs an AGM revision function in order to respond to new evidential information, it is considered that the agent behaves in a rational manner. The rationale behind the AGM revision postulates is concretely discussed by G ardenfors (1988, Section 3.3) and Peppas (2008, Section 8.3.1). We solely mention here that their guiding principle is the economy of information, according to which the new information φ is consistently incorporated into the belief set K, changing the latter as little as possible. Note lastly that, in the special case where φ is consistent with K, it follows from postulates (K 3) & (K 4) that revision reduces to expansion; thus, K φ = K + φ. As earlier stated however, herein we consider only the principal case of genuine revision; namely, the case where the epistemic input φ contradicts the initial belief set K.

3.2 Semantic Characterization

Katsuno and Mendelzon (1991) showed that the revision functions satisfying the AGM revision postulates are precisely those that are induced by means of faithful preorders, a special kind of total preorders over all possible worlds.

Definition 1 (Faithful Preorder). A total preorder K over M is faithful to a belief set K iff, for any possible worlds r, r M, the following two conditions hold:

(i) If r, r JKK, then r K r .

(ii) If r JKK and r / JKK, then r K r .

Intuitively, a faithful preorder K over M encodes the comparative plausibility of the possible worlds of M, relative to the belief set K. Specifically, the assertion r K r states that the world r is at least as plausible as the world r , with respect to K.

Definition 2 (Faithful Assignment, (Katsuno & Mendelzon, 1991)). A faithful assignment is a function that maps each belief set K of T to a total preorder K over M, that is faithful to K.

Based on the notion of faithful assignment, Katsuno and Mendelzon obtained the following representation theorem, which characterizes the class of AGM revision functions in terms of faithful preorders.

Theorem 3 (Katsuno & Mendelzon, 1991). A revision function satisfies postulates (K 1) (K 8) iff there exists a faithful assignment that maps each belief set K to a total preorder K over M, such that, for any φ L:

(R) q K φ y = min(JφK, K).

Hence, according to condition (R), the revised belief set K φ is specified as the theory corresponding to the most plausible φ-worlds, relative to the initial belief set K. Since revision by self-contradictory epistemic input constitutes a limiting uninteresting case, we consider in the course of this article only the principal case of consistent new information.

4. Belief Merging

Belief merging is the process of aggregating the (perhaps conflicting) beliefs of individuals. In formal terms, belief merging studies the following question: Given a collection of belief sets K1, . . . , Kn, each one representing the beliefs of an agent of a community, which is a belief set that can be considered to represent a plausible aggregation of K1, . . . , Kn? This question is particularly important in the context of many Artificial Intelligence fields, and thus, several merging operators that implement the aforementioned aggregation-process have been proposed in the literature. In this section, we review several interesting proposals of such operators, some of which were already discussed by Westlund (2010). Before presenting the alluded proposals, let us fix the required notation and terminology. A belief profile (or simply profile) E is a non-empty multi-set of belief sets; thus, E could contain multiple instances of a belief set. The set of all profiles is denoted by E. The multi-set union is denoted by . For a profile E E, we shall write JEK instead of q S E y . We denote by En the profile in which E appears n times; that is, En = E E | {z } n . Two

profiles E1, E2 are equivalent, denoted by E1 E2, iff there is a bijective function f from E1 to E2, such that, for any K E1, f(K) = K.

Definition 4 (Merging Function). A merging function M is a binary function that maps a profile E of E and a sentence µ of L (representing integrity constraints) to a belief set Mµ(E) of T; i.e., M : E L 7 T.

Hence, a merging function M generates a belief set Mµ(E) which represents the aggregation of all the belief sets of the profile E that, at the same time, respects the integrity constraints encoded into the logical sentence µ. The integrity constraints encoded into µ, essentially, may be imposed by physical constraints, unquestionable knowledge and so forth. For a profile {{K1, . . . , Kn}} of E, we shall write Mµ(K1, . . . , Kn) instead of Mµ {{K1, . . . , Kn}} . Furthermore, in case the sentence µ is a tautology, the subscript µ shall be dropped.2

In what follows, with an exception to be made in Section 8, we assume that the mergingprocess implemented by merging functions does not adhere to specific integrity constraints. In such circumstance, the sentence µ is a tautology and, thus, we shall treat (albeit abusively) a merging function as a unary function that aggregates multiple belief sets into a single belief set.

4.1 Union-When-Possible Merging Functions

Against this background, we introduce firstly the so-called union-when-possible merging functions, which were also considered by Westlund (2010).

Definition 5 (Union-When-Possible Merging Function). A merging function M is a unionwhen-possible merging function iff, for any profile E E, M(E) = Cn S E , when the union S E is consistent.

2. Notice that, for sets we use the traditional curly brackets { and } , whereas, for multi-sets we utilize double curly brackets {{ and }} .

Collective Belief Revision

A union-when-possible merging function produces a belief set resulting from the settheoretic union of all the beliefs of the members of a community, provided that there is no inconsistency among these beliefs. Thus, if the two belief sets K1 = Cn {a} and K2 = Cn {a b} ought to be aggregated by means of a union-when-possible merging function M, we would have that M(K1, K2) = Cn(K1 K2) = Cn {a, a b} = Cn {a, b} , since the union K1 K2 is consistent.

Observe that, in case the union S E is inconsistent, the aggregation implemented by a union-when-possible merging function is not constrained at all. Based on this observation, Konieczny and P erez (2002) identified a proper sub-class of the whole class of unionwhen-possible merging functions, which contains merging operators whose behaviour is constrained by certain rationality-principles. These merging operators are called Integrity Constraints quasi-merging functions, are abbreviated as IC quasi-merging functions, and are introduced subsequently.

4.1.1 IC Quasi-Merging Functions

In the spirit of the AGM trio, Konieczny and P erez (2002) characterized the class of IC quasi-merging functions in terms of a collection of rationality-postulates, which essentially encode reasonable logical properties of an aggregation-operation.

Konieczny and Pino P erez consider merging functions whose aggregation-operation adheres to specific integrity constraints, which are in turn represented by a logical formula µ. In particular, they define an Integrity Constraints quasi-merging function, or IC quasi-merging function for short, to be any merging function M that satisfies the following postulates (IC0) (IC8).3

(IC0) Mµ(E) is a theory of T containing µ.

(IC1) If µ is consistent, then Mµ(E) is consistent.

(IC2) If S E {µ} is consistent, then Mµ(E) = S E + µ.

(IC3) If E1 E2 and Cn {µ1} = Cn {µ2} , then Mµ1(E1) = Mµ2(E2).

(IC4) If µ K1 and µ K2, then Mµ {{K1, K2}} K1 is consistent iff Mµ {{K1, K2}} K2 is consistent.

(IC5) Mµ(E1 E2) Cn Mµ(E1) Mµ(E2) .

(IC6) If Mµ(E1) Mµ(E2) is consistent, then Cn Mµ(E1) Mµ(E2) Mµ(E1 E2).

(IC7) Mµ1 µ2(E) Mµ1(E) + µ2.

(IC8) If Mµ1(E) {µ2} is consistent, then Mµ1(E) + µ2 Mµ1 µ2(E).

3. We have rephrased Konieczny and Pino P erez s postulates for IC quasi-merging functions in terms of the notation adopted in this paper.

For a detailed discussion on the above postulates, the interested reader is referred to (Konieczny & P erez, 2002, 2011); in these works, one can also find the definition of several notable sub-classes of the whole class of IC quasi-merging functions, such as the IC merging functions, the majority merging functions and the arbitration functions. Konieczny and Pino P erez semantically characterized the class of IC quasi-merging functions in terms of a special kind of total preorders over possible worlds. Their semantic characterization is in the spirit of Katsuno and Mendelzon s faithful-preorders characterization for belief revision (cf. Subsection 3.2). For presenting this characterization, let us firstly introduce the notion of quasi-syncretic assignment.

Definition 6 (Quasi-Syncretic Assignment, (Konieczny & P erez, 2002)). A quasi-syncretic assignment is a function that maps each profile E to a total preorder E over M, such that, for any profiles E1, E2 E, any belief sets K1, K2 T, and any possible worlds r, r M, the following conditions hold:4

(i) If r, r JEK, then r E r .

(ii) If r JEK and r / JEK, then r E r .

(iii) If E1 E2, then E1= E2.

(iv) For any r JK1K, there is a world r JK2K, such that r {K1} {K2} r.

(v) If r E1 r and r E2 r , then r E1 E2 r .

(vi) If r E1 r and r E2 r , then r E1 E2 r .

As in the case of a faithful preorder, a total preorder E over M, as defined in Definition 6, encodes the comparative plausibility of the possible worlds of M, relative to the profile E. Similarly thus, the assertion r E r states that the world r is at least as plausible as the world r , with respect to E. Based on the notion of quasi-syncretic assignment, Konieczny and Pino P erez obtained the following representation theorem.

Theorem 7 (Konieczny & P erez, 2002). A merging function M satisfies postulates (IC0) (IC8) iff there exists a quasi-syncretic assignment that maps each profile E to a total preorder E over M, such that, for any µ L:

(M) q Mµ(E) y = min(JµK, E).

According to condition (M), the resulting merged belief set Mµ(E) is defined in terms of the most plausible (with respect to E) possible worlds satisfying µ, a scheme that strongly resembles the way that belief sets are revised according to condition (R) (cf. Section 3). As earlier mentioned, we assume herein (with an exception to be made in Section 8) that the merging-process implemented by merging functions does not adhere to integrity constraints. On that premise, the sentence µ is a tautology and, thus, the merged belief set Mµ(E), which can be denoted by M(E), is always consistent, in view of postulate (IC1). Furthermore, assuming that the sentence µ is a tautology, the following remark follows immediately from postulate (IC2).

4. E and E denote the strict and indifference part of the preorder E, respectively.

Collective Belief Revision

Remark 8. The class of IC quasi-merging functions is a sub-class of the class of unionwhen-possible merging functions.

4.1.2 Formula-Based Merging Functions

The class of union-when-possible merging functions, beyond the IC quasi-merging functions, subsumes other central types of merging operators as well, such as the formula-based merging functions (Baral et al., 1992; Benferhat, Dubois, Lang, Prade, Saffiotti, & Smets, 1998; Konieczny, 2000). Contrary to IC quasi-merging functions which are model-based operators defined in terms of possible worlds (models), formula-based merging functions are sensitive to the formulae of the belief sets to be aggregated, as they select some maximal consistent subsets of the union of these belief sets. In particular, consider the following merging operator.5

M (E) = T n M Cn S E : M = L, and if M M Cn S E , then M = L o

The operator M is a formula-based merging function that yields the intersection of every inclusion-maximal consistent subset of the belief set Cn S E . A merging operator analogous to M can also be defined when maximality is specified in terms of cardinality.6

Mcard(E) = T n M Cn S E : M = L, and if |M| < |M | and M Cn S E , then M = L o

Both merging operators M and Mcard are defined by intersecting all the consistent subsets of the belief set Cn S E that are maximal, either with respect to set inclusion or with respect to cardinality. One may argue that this scheme is not satisfactory from a merging point of view, as it does not take into account the distribution of the information among the belief sets to be aggregated. In response to this weakness, Konieczny (2000) proposed the use of particular selection mechanisms that pick up for intersection only the maximal consistent subsets of Cn S E that best fit a certain merging-criterion. These selection mechanisms, which are inspired by the so-called selection functions of Alchourr on et al. (1985) by means of which partial-meet contraction is defined, allowed the definition of a wide class of formula-based merging functions with better behaviour and, thus, better logical properties (cf. (Konieczny, 2000) for details). Now, it is easy to verify that, for any profile E E, if the union S E is consistent, then every formula-based merging function of the aforementioned class of merging operators yields the belief set Cn S E . This observation implies the following remark.

Remark 9. The class of formula-based merging functions is a sub-class of the class of union-when-possible merging functions.

We note lastly that none of the formula-based merging function considered herein respects postulate (IC3) (Konieczny, 2000). It follows then that no formula-based merging function that we study is an IC quasi-merging function, a fact which brings us to the following conclusion.

5. Contrary to the original works on formula-based merging functions (Baral et al., 1992; Benferhat et al., 1998), herein we assume that such operators do not adhere to integrity constraints. 6. For a set V , |V | denotes the cardinality of V .

Union-When-Possible Merging Functions

IC Quasi-Merging Functions

Formula-Based Merging Functions

Figure 1: The class of union-when-possible merging functions relative to the classes of IC quasi-merging functions and formula-based merging functions (cf. Remarks 8, 9 and 10).

Remark 10. The class of formula-based merging functions is disjoint with the class of IC quasi-merging functions.

Figure 1 depicts the class of union-when-possible merging functions relative to the classes of IC quasi-merging functions and formula-based merging functions, in view of Remarks 8, 9 and 10.

4.2 Other Principal Merging Operators

In the remainder of this section, we introduce three other principal types of merging operators. We begin with the consensus merging function, which is a unique merging operator also considered by Westlund (2010).

Definition 11 (Consensus Merging Function). A merging function M is the consensus merging function iff, for any profile E E, M(E) = T E.

The consensus merging function produces the consensus among all the members of a community. Thus, if the two belief sets K1 = Cn {a, b} and K2 = Cn {a, b} ought to be aggregated by means of the consensus merging function M, we would have that M(K1, K2) = K1 K2 = Cn {a} .7

We shall now elaborate on the second type of merging operators, which we refer to as radical merging functions.

Definition 12 (Radical Merging Function). A merging function M is a radical merging function iff, for any profile E E and any non-tautological sentence φ L such that φ T E, φ / M(E).

7. It is noteworthy that the consensus merging function respects postulate (Disj) of Everaere, Konieczny, and Marquis (2010, p. 828).

Collective Belief Revision

Intuitively, a merging function M is radical whenever, for every profile E, any nontautological belief that is common to all belief sets of E is not contained in the aggregated belief set M(E). Due to their reactive operation, radical merging functions may be considered unreasonable operators for combining information; yet, there are certain scenarios in which their outcome can be perfectly suitable. Consider, for instance, a profile E which is specified by the two belief sets K1 = Cn {a, b} and K2 = Cn {a b, b} . Then, there is a radical merging function M that yields the belief set M(E) = Cn {b} , which does not contain non-tautological sentences that are common to both K1 and K2.8 Arguably, the belief set M(E) represents a plausible synthesis of the belief sets K1 and K2. Finally, let us introduce the singular merging functions, which represent the last type of merging operators introduced herein.

Definition 13 (Singular Merging Function). A merging function M is a singular merging function iff, for any profile {{K1, . . . , Kn}} E, there is an i {1, . . . , n} such that M(K1, . . . , Kn) = Ki.

A singular merging function yields a single unaltered belief set of the profile it receives as input. Singular merging functions could find application in situations where it is preferable to choose one among all the possible states of belief, rather than to melt all the available states of belief in a single belief set. Suppose, for example, that three physicians propose three different medical treatments for the condition of a patient. It seems plausible that the patient should receive one of the proposed treatments, and not a mixture of them. A special kind of singular merging function is a dictator merging function, also considered by Westlund (2010).

Definition 14 (Dictator Merging Function). Let n be an arbitrary, but fixed, positive integer. A (singular) merging function M is a dictator merging function iff there is an i {1, . . . , n} such that, for any n-elements profile {{K1, . . . , Kn}} E, M(K1, . . . , Kn) = Ki.

Given an arbitrary, but fixed, positive integer n, a dictator merging function always chooses the belief set corresponding to a specific fixed index i {1, . . . , n}, irrespectively of the (n-elements) profile {{K1, . . . , Kn}} that the merging function receives as input.

5. The Principle of Collective Change

As stated in the Introduction section, Westlund introduced the Principle of Collective Change (PCC) in the realm of contraction and expansion (Westlund, 2010, p. 217). This section is devoted to the formulation of the PCC in the realm of genuine belief revision; namely, in the principal case where the new information contradicts the belief set of each individual of a collective entity. Evidently, a community of individuals could be an organization, a company, a scientific committee, or any multi-agent system. A formal definition of the notion of a community that consists of rational agents is presented in Definition 15.

8. Informally, one can think of the merged belief set M(E) as being generated as follows: The interaction of the belief a of the belief set K1 with the belief a b of the belief set K2 produced the belief b of M(E), and, at the same time, cancelled the belief b that is common to K1 and K2.

K1 . . . Kn K1 1 φ . . . Kn n φ

M K1, . . . , Kn

M K1 1 φ, . . . , Kn n φ

Figure 2: A community M, 1, . . . , n satisfies the PCC iff there exists an AGM revision function such that, for any profile {{K1, . . . , Kn}} and any sentence φ that contradicts each belief set of {{K1, . . . , Kn}}, M(K1, . . . , Kn) φ = M K1 1 φ, . . . , Kn n φ .

Definition 15 (Community of Rational Individuals). A community of n rational agents is a tuple M, 1, . . . , n , where n is an arbitrary positive integer, M is a merging function, and 1, . . . , n are the AGM revision functions that the agents 1, . . . , n employ, respectively, to implement revision.

Each AGM revision function i, where i {1, . . . , n}, of a community M, 1, . . . , n

is employed by the agent i in order to rationally respond to new epistemic input, whereas, the merging function M is used by the whole community in order to aggregate the beliefs of its agents, and formulate its collective knowledge. Based on this definition of collective agency, a belief profile {{K1, . . . , Kn}} essentially accommodates the atomic states of belief of the n members of the community, and the belief set M(K1, . . . , Kn) represents the state of collective belief of the community. On that premise, we shall say that a community M, 1, . . . , n of n rational agents satisfies Westlund s PCC iff there exists an AGM revision function such that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ Ki, for all i {1, . . . , n}, the following condition (CC) holds:

(CC) M K1, . . . , Kn φ = M K1 1 φ, . . . , Kn n φ .

Obviously, the community violates Westlund s PCC iff, for some profile {{K1, . . . , Kn}} E and some sentence φ L such that φ Ki, for all i {1, . . . , n}, there is no AGM revision function such that M(K1, . . . , Kn) φ = M K1 1 φ, . . . , Kn n φ . The PCC whose essence is graphically represented in Figure 2 constitutes a criterion that characterizes the revision of collective knowledge. This criterion concerns the case of genuine revision (that does not reduce to expansion), and requires that, if each rational agent of a community revises her beliefs by an epistemic input that contradicts her initial belief set, then the community as a whole ought to revise its collective beliefs

Collective Belief Revision

by the same epistemic input as well. More precisely, the satisfaction of PCC by a community M, 1, . . . , n boils down to the existence of an AGM revision function , such that, for any profile {{K1, . . . , Kn}} and any sentence φ that contradicts each belief set of {{K1, . . . , Kn}}, the -revision of the belief set M(K1, . . . , Kn) by φ coincides with the belief set M K1 1 φ, . . . , Kn n φ . The AGM revision function (if it exists) can be seen as the revision operator that the community employs as a collective entity, in order to modify its collective knowledge.9

6. Unsatisfiability Results

Having introduced the PCC in the realm of genuine belief revision, we establish in this section the alluded unsatisfiability results concerning this property. We begin with the case of union-when-possible merging functions and their specializations IC quasi-merging functions and formula-based merging functions (Subsection 6.1), we then turn to the consensus merging function (Subsection 6.2), and lastly we investigate the case of radical merging functions (Subsection 6.3).

6.1 Union-When-Possible Merging Functions

Our first unsatisfiability result is Theorem 16, which concerns the case of union-whenpossible merging functions, and proves that there exist communities of rational individuals that, for any union-when-possible merging function, violate the PCC.

Theorem 16. There exist AGM revision functions 1, . . . , n, such that, for any unionwhen-possible merging function M, the community M, 1, . . . , n violates the PCC.

Proof. Assume the non-trivial case where L contains at least two atoms; hence, there are at least four possible worlds in M. Let w1, w2, w3, w4 be four distinct worlds of M, and let K1, K2 be two theories such that JK1K = {w1} and JK2K = {w1, w2}. Moreover, let φ be a sentence of L such that JφK = {w3, w4}; clearly, φ contradicts both K1 and K2, as JφK JK1K = JφK JK2K = . Consider an AGM revision function 1 that assigns (via (R)) at the belief set K1 a faithful preorder 1 K1, such that w3 1 K1 w4. Moreover, consider an AGM revision function 2 that assigns (via (R)) at the belief set K1 a faithful preorder 2 K1, such that w3 2 K1 w4, and at the belief set K2 a faithful preorder 2 K2, such that w4 2 K2 w3. Then, it follows from condition (R) that JK1 1 φK = {w3, w4}, JK1 2 φK = {w3} and JK2 2 φK = {w4} (the belief sets mentioned above in this proof are graphically represented in Figure 3). Now, let M be an arbitrary union-when-possible merging function. Since JK1K JK2K = {w1}, we derive that M(K1, K1) = M(K1, K2) = K1. Furthermore, since JK1 1 φK JK1 2 φK = {w3} and JK1 1 φK JK2 2 φK = {w4}, we have that

9. In the context of the space-related scenario stated in the Introduction section, the AGM revision functions 1, . . . , n are employed by the n experts of the scientific community for individually revising their current atomic states of knowledge, which are represented by the belief sets K1, . . . , Kn. The merging function M is employed by the scientific community so that its collective knowledge be generated. Then, assuming that φ represents the new scientific discovery, the belief sets M(K1, . . . , Kn) and M K1 1 φ, . . . , Kn n φ correspond, respectively, to the initial and revised states of collective knowledge of the scientific community.

Figure 3: Graphical representation of the belief sets K1 and K2 and their revisions by φ, via the AGM revision functions 1 and 2, described in the proof of Theorem 16. The marked areas represent the sets of all possible worlds satisfying the corresponding belief sets.

q M K1 1 φ, K1 2 φ y = q Cn (K1 1 φ) (K1 2 φ) y = JK1 1 φK JK1 2 φK = {w3} and q M K1 1 φ, K2 2 φ y = q Cn (K1 1 φ) (K2 2 φ) y = JK1 1 φK JK2 2 φK = {w4}, respectively. Obviously then, it follows that M K1 1 φ, K1 2 φ = M K1 1 φ, K2 2 φ . Next, suppose towards contradiction that the community M, 1, 2 of two rational agents satisfies the PCC. Therefore, there exists an AGM revision function such that M(K1, K1) φ = M K1 1 φ, K1 2 φ and M(K1, K2) φ = M K1 1 φ, K2 2 φ . Given that M K1 1 φ, K1 2 φ = M K1 1 φ, K2 2 φ , we derive that M(K1, K1) φ = M(K1, K2) φ. This, however, contradicts the fact that M(K1, K1) = M(K1, K2). Consequently, for any union-when-possible merging function M, the community M, 1, 2 violates the PCC.

Given that union-when-possible merging functions subsume IC quasi-merging functions and formula-based merging functions (cf. Remarks 8 and 9), the following important corollary is an immediate consequence of Theorem 16.

Corollary 17. There exist AGM revision functions 1, . . . , n, such that, for any IC quasimerging function or any formula-based merging function M, the community M, 1, . . . , n

violates the PCC.

Corollary 17 points out that there exist communities of rational agents (who behave rationally at the individual level as each agent employs an AGM revision function), such that, for any IC quasi-merging function or formula-based merging function, do not adhere to the PCC.

6.2 The Consensus Merging Function

Let us now turn to the case of the consensus merging function. It turns out that an unsatisfiability result can be obtained in that circumstance too, indicating that there exist communities of rational individuals, equipped with the consensus merging function, that do not respect the PCC.

Collective Belief Revision

Theorem 18. Let M be the consensus merging function. There exist AGM revision functions 1, . . . , n, such that the community M, 1, . . . , n violates the PCC.

Proof. Assume the non-trivial case where L contains at least two atoms; hence, there are at least four possible worlds in M. Let w1, w2, w3, w4 be four distinct worlds of M, let K1, K2 be two theories such that JK1K = {w1} and JK2K = {w2}, and let φ be a sentence of L such that JφK = {w3, w4}. Clearly, φ contradicts both K1 and K2, as JφK JK1K = JφK JK2K = . Consider an AGM revision function 1 that assigns (via (R)) at the belief sets K1 and K2 two faithful preorders 1 K1 and 1 K2, respectively, such that w3 1 K1 w4 and w4 1 K2 w3. Moreover, consider an AGM revision function 2 that assigns (via (R)) at the belief sets K1 and K2 two faithful preorders 2 K1 and 2 K2, respectively, such that w4 2 K1 w3 and w3 2 K2 w4. Then, it follows from condition (R) that JK1 1 φK = {w3} and JK2 1 φK = {w4}, and moreover, JK1 2 φK = {w4} and JK2 2 φK = {w3}. Now, since M is the consensus merging function, it follows that M(K1, K2) = M(K2, K1) = K1 K2. Furthermore, it is true that M K1 1 φ, K2 2 φ = (K1 1 φ) (K2 2 φ) and M K2 1 φ, K1 2 φ = (K2 1 φ) (K1 2 φ), a fact which entails, respectively, that q M K1 1 φ, K2 2 φ y = JK1 1 φK JK2 2 φK = {w3} and q M K2 1 φ, K1 2 φ y = JK2 1 φK JK1 2 φK = {w4}. Obviously then, it follows that M K1 1 φ, K2 2 φ = M K2 1 φ, K1 2 φ . Next, suppose towards contradiction that the community M, 1, 2 of two rational agents satisfies the PCC. Therefore, there exists an AGM revision function such that M(K1, K2) φ = M K1 1 φ, K2 2 φ and M(K2, K1) φ = M K2 1 φ, K1 2 φ . Given that M K1 1 φ, K2 2 φ = M K2 1 φ, K1 2 φ , we derive that M(K1, K2) φ = M(K2, K1) φ. This, however, contradicts the fact that M(K1, K2) = M(K2, K1). Consequently, for the consensus merging function M, the community M, 1, 2 violates the PCC.

It should be noted at this point that Westlund, confined in the realm of contraction and expansion, also established impossibility results for union-when-possible merging functions and the consensus merging function. In particular, he showed that no union-when-possible or consensus merging function respects the PCC for the operations of contraction and expansion (Westlund, 2010, Observations 6 and 10). Theorems 16 and 18 and Corollary 17, essentially, come to extend in the realm of belief revision the aforementioned Westlund s impossibility results.

6.3 Radical Merging Functions

We close this section with the case of radical merging functions, which also lead to communities not adhering to the PCC. This is shown in Theorem 19, which proves that every community of rational individuals equipped with a radical merging function violates the PCC.

Theorem 19. Every community of rational agents equipped with a radical merging function violates the PCC.

Proof. Let M, 1, . . . , n be a community of n rational agents, such that M is a radical merging function. Let {{K1, . . . , Kn}} be a profile of E, and let φ be a non-tautological

sentence of L such that φ Ki, for all i {1, . . . , n}. From postulate (K 2), it follows that φ Ki i φ, for all i {1, . . . , n}. Therefore, given that M is a radical merging function, we derive that φ / M K1 1 φ, . . . , Kn n φ . Postulate (K 2) also entails that, for any AGM revision function , φ M(K1, . . . , Kn) φ. Hence, there is no AGM revision function such that M(K1, . . . , Kn) φ = M K1 1 φ, . . . , Kn n φ . Consequently, the community M, 1, . . . , n violates the PCC.

7. Satisfiability Results

The impossibility results established in the previous section are, certainly, not a good indication for the suitability of the PCC, and some notable implications of them shall be discussed later in this article. Still, in the present section, it is shown that it is possible to formulate a collection of satisfiability results too concerning the PCC. The alluded satisfiability results relate to the cases of union-when-possible, consensus and singular merging functions, and shall be established with the aid of a special kind of belief revision, called uniform belief revision. The process of uniform belief revision has been developed by Areces and Becher (2001), and was subsequently investigated by Aravanis (2020).10 We proceed subsequently to the formal definition of this kind of belief revision.

7.1 Uniform Belief Revision

Let be an arbitrary, but fixed, total preorder over the set of all possible worlds M. Intuitively, the total preorder which is belief-set-independent encodes the (stateindependent) comparative plausibility of possible worlds, which in turn reflects the dynamics of a domain, imposed by a body of pre-established background knowledge, such as objective laws of physics, legal or moral codes. In view of condition (US) presented below, the total preorder can generate a whole family { K}K T of faithful preorders over worlds, that is, one total preorder associated with each belief set of T.

(US) For any possible worlds r, r / JKK, r K r iff r r .

According to condition (US), for each belief set K T, the faithful preorder K is set identical to the total preorder , on their sub-domain M JKK M JKK . In this way, the total preorder that encodes the domain s dynamics generates a family { K}K T of faithful preorders, and thus, generates the revision-strategy for every belief set of the language. Now, the family { K}K T of faithful preorders induces, through condition (R), an AGM revision function. An AGM revision function so constructed is called uniform revision operator, or UR operator for short. As proved by Areces and Becher (2001), the proper

10. Areces and Becher named the revision operators that implement uniform belief revision iterable AGM revision functions , as the authors focus on the favourable properties of these operators related to iterated revision (Peppas, 2014). In this article, following Aravanis (2020), we adopt the term uniform revision operators which reflects the way the operators act on belief sets.

Collective Belief Revision

sub-class of AGM revision functions satisfying the subsequent postulate (UR) is precisely the class of UR operators.11

(UR) For any sentence φ K1 K2, K1 φ = K2 φ.

Hence, given a UR operator , any two belief sets of the language, which are both contradicted by an epistemic input φ, are -revised by φ in a uniform manner. As we show in the remainder of this section, this property of uniform belief revision will help us to establish our satisfiability results concerning the PCC.

7.2 Union-When-Possible Merging Functions

Against this background, we establish our first satisfiability result related to the PCC, which is Theorem 20 that refers to union-when-possible merging functions, and points out that the uniformity of the revision-process (as implemented by a UR operator) guarantees the fulfilment of the PCC.

Theorem 20. Let be a UR operator. Moreover, let M be a union-when-possible merging function such that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ Ki, for all i {1, . . . , n}, φ M(K1, . . . , Kn). Then, the community M, , . . . , of n rational agents satisfies the PCC.

Proof. To prove that the community M, , . . . , of n rational agents satisfies the PCC, it suffices to show that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ Ki, for all i {1, . . . , n}, M(K1, . . . , Kn) φ = M K1 φ, . . . , Kn φ . To that end, let {{K1, . . . , Kn}} be an arbitrary profile of E, and let φ be a sentence of L such that φ Ki, for all i {1, . . . , n}. Firstly, by the consideration (hypothesis) of M, we have that φ M(K1, . . . , Kn). Furthermore, observe that, since is a UR operator, it follows from postulate (UR) that Kj φ = Kk φ = M(K1, . . . , Kn) φ = H, for all j, k {1, . . . , n}. From our assumption that the epistemic input φ is consistent (cf. Section 3), postulate (K 5) entails that Kj φ is consistent, for all j {1, . . . , n}. Then,

the fact that Kj φ = Kk φ, for all j, k {1, . . . , n}, entails that the union n S

is consistent as well. Since M is a union-when-possible merging function, we derive then

that M K1 φ, . . . , Kn φ = n S

Ki φ = H H | {z } n = H. Combining the above, we

obtain that M(K1, . . . , Kn) φ = M K1 φ, . . . , Kn φ , as desired.

Theorem 20 assumes a union-when-possible merging function M such that the belief set M(K1, . . . , Kn) resulting from the M-aggregation of any belief sets K1, . . . , Kn is contradicted by the epistemic input φ.12 It proves, then, that a community equipped with any

11. A concrete example that outlines the construction of a UR operator is Example 4.2 by Aravanis (2020, p. 1363). Furthermore, an interesting generalization of UR operators has been recently formulated by Aravanis and Peppas (2022). 12. This means that the revision of M(K1, . . . , Kn) by φ is genuine, in the sense that revision does not reduce to expansion.

such union-when-possible merging function (thus, with any such IC quasi-merging function or formula-based merging function) satisfies the PCC, provided that all its members (individually) revise their beliefs in a uniform manner, by means of a UR operator.

7.3 The Consensus Merging Function

The second satisfiability result concerning the PCC that we establish is Theorem 21, stated below. Similarly to Theorem 20, Theorem 21 proves that any community equipped with the consensus merging function respects the PCC, provided that its agents uniformly revise their beliefs.

Theorem 21. Let be a UR operator, and let M be the consensus merging function. Then, the community M, , . . . , of n rational agents satisfies the PCC.

Proof. To prove that the community M, , . . . , of n rational agents satisfies the PCC, it suffices to show that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ Ki, for all i {1, . . . , n}, M(K1, . . . , Kn) φ = M K1 φ, . . . , Kn φ , or equivalently, n T

i=1 Ki φ = n T

To that end, let {{K1, . . . , Kn}} be an arbitrary profile of E, and let φ be a sentence

of L such that φ Ki, for all i {1, . . . , n}. Firstly, notice that φ n T

i=1 Ki . Fur-

thermore, observe that, since is a UR operator, it follows from postulate (UR) that

Kj φ = Kk φ = n T

i=1 Ki φ = H, for all j, k {1, . . . , n}. Therefore, we derive that

Ki φ = H H | {z } n = H. Combining the above, we obtain that n T

Ki φ , as desired.

In contrast to Theorems 16 and 18 of the previous section which are impossibility results concerning union-when-possible merging functions and the consensus merging function, Theorems 20 and 21 indicate that, under certain conditions, the satisfaction of the PCC is indeed feasible for the aforementioned types of merging operators. It is noteworthy that Westlund (2010) did not establish satisfiability results for unionwhen-possible merging functions and the consensus merging function although, as stated in the previous section, he did establish impossibility results for these types of merging operators.

7.4 Singular Merging Functions

Westlund (2010, Observation 5) has already shown that, for any profile of E, every dictator merging function respects the PCC, for the operations of contraction and expansion. Theorem 22 shows that this is also the case for the operation of revision, by proving that every community equipped with a dictator merging function respects the PCC.

Theorem 22. Every community of rational agents equipped with a dictator merging function satisfies the PCC.

Collective Belief Revision

Proof. Let M, 1, . . . , n be a community of n rational agents, such that M is a dictator merging function, and let {{K1, . . . , Kn}} be a profile of E. Since M is a dictator merging function and n is fixed, it follows that there is an i {1, . . . , n} such that M(K1, . . . , Kn) = Ki. Furthermore, for any sentence φ L, it is also true that M K1 1 φ, . . . , Kn n φ = Ki i φ. Combining the above, we derive that there exists an AGM revision function, and that is i, such that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ Kj, for all j {1, . . . , n}, M(K1, . . . , Kn) i φ = M K1 1 φ, . . . , Kn n φ . Therefore, the community M, 1, . . . , n satisfies the PCC, as desired.

It turns out that a result analogous to Theorem 22 can be obtained for communities equipped with the more general singular merging functions, provided that the individual agents of such a community employ a UR operator for implementing revision. This is shown in Theorem 23, stated below.

Theorem 23. Let be a UR operator, and let M be a singular merging function. Then, the community M, , . . . , of n rational agents satisfies the PCC.

Proof. To prove that the community M, , . . . , of n rational agents satisfies the PCC, it suffices to show that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ K, for all i {1, . . . , n}, M(K1, . . . , Kn) φ = M K1 φ, . . . , Kn φ . To that end, let {{K1, . . . , Kn}} be an arbitrary profile of E, and let φ be a sentence of L such that φ Ki, for all i {1, . . . , n}. Since M is a singular merging function, it follows that there is a j {1, . . . , n} such that M(K1, . . . , Kn) = Kj. Furthermore, it is also true that there is a k {1, . . . , n} such that M K1 φ, . . . , Kn φ = Kk φ.13 Given that is a UR operator, we derive from postulate (UR) that Kj φ = Kk φ. Combining the above, we have that M(K1, . . . , Kn) φ = M K1 φ, . . . , Kn φ , as desired.

7.5 Comments on the Satisfiability Results

Let us now summarize our main satisfiability results. Both Theorems 21 and 23 show that the consensus merging function or any singular merging function, combined with any UR operator, can induce a community adhering to the dictates of the PCC. Essentially, these two results indicate that a community equipped with any of the aforementioned types of merging operators fulfil the PCC, if both the community itself and all its members revise their beliefs with the exact same strategy. This can in turn be achieved when both the community and its members perceive the dynamics of the domain in the same way, as encoded into a single total preorder over possible worlds.14 Theorem 20 shows that the previous observations apply to the case of union-when-possible merging functions as well, when some weak constraints are imposed on their operation. Against the background of the established satisfiability results, the following concrete example illustrates representative scenarios of collective belief revision that respect the PCC.

13. The indices j and k are in general distinct. 14. The uniform perception of the dynamics of the domain could be possible in an homogeneous community (probably, for example, within a small scientific committee); yet, in diverge communities such a requirement is undoubtedly strong.

Example 24 (Satisfiability of the PCC). Let P = {a, b, c}, let K1, K2, K3 be three belief sets such that K1 = Cn {a, b, c} , K2 = Cn { a, b, c} and K3 = Cn {a, b, c} , and let φ be a sentence of L such that φ = c. Notice that φ contradicts each one of K1, K2 and K3. Moreover, let be a UR operator induced, through conditions (US) and (R), from the following total preorder over M:15

abc abc abc abc abc abc abc abc

Then, it follows from conditions (US) and (R) that K1 φ = K2 φ = K3 φ = Cn { a, b, c} . Lastly, let M, , , be a community (e.g., a scientific committee) of 3 rational agents, where M can be either a union-when-possible merging function, or a consensus merging function, or a singular merging function. Assume, firstly, that M is a union-when-possible merging function such that, for any profile {{K1, . . . , Kn}} E and any sentence ψ L such that ψ Ki, for all i {1, . . . , n}, ψ M(K1, . . . , Kn). In view of the fact that K1 K2 K3 is inconsistent, suppose that M is such that M(K1, K2, K3) = Cn {(a b c) ( a b c) (a b c)} . Expectedly, φ M(K1, K2, K3), and therefore, due to (US) and (R), we derive that M(K1, K2, K3) φ = Cn { a, b, c} . Since M is a union-when-possible merging function, it also follows that M K1 φ, K2 φ, K3 φ = (K1 φ) (K2 φ) (K3 φ) = Cn { a, b, c} . Observe, then, that M(K1, K2, K3) φ = M K1 φ, K2 φ, K3 φ , as it was expected due to Theorem 20. Thereafter, assume that M is a consensus merging function. Then, we have that M(K1, K2, K3) = K1 K2 K3 = Cn {(a b c) ( a b c) (a b c)} . Clearly, φ M(K1, K2, K3), and therefore, due to (US) and (R), we derive that M(K1, K2, K3) φ = Cn { a, b, c} . Since M is a consensus merging function, it also follows that M K1 φ, K2 φ, K3 φ = (K1 φ) (K2 φ) (K3 φ) = Cn { a, b, c} . Observe, again, that M(K1, K2, K3) φ = M K1 φ, K2 φ, K3 φ , as it was expected due to Theorem 21. Lastly, assume that M is a singular merging function, and suppose that it is such that M(K1, K2, K3) = K2 = Cn { a, b, c} . As φ M(K1, K2, K3), we derive from conditions (US) and (R) that M(K1, K2, K3) φ = Cn { a, b, c} . Since M is a singular merging function and K1 φ = K2 φ = K3 φ = Cn { a, b, c} , it also follows that M K1 φ, K2 φ, K3 φ = Cn { a, b, c} . Once again, M(K1, K2, K3) φ = M K1 φ, K2 φ, K3 φ , as it was expected due to Theorem 23.

Notwithstanding that the aforementioned satisfiability results show that, under certain (rather strict) conditions, the satisfaction of the PCC is indeed obtainable, the impossibilities of Section 6 are certainly not a good indication for the suitability of that property.

15. denotes the strict part of . Furthermore, for the sake of readability, possible worlds are represented as sequences (rather than sets) of literals, whereas, the negation of an atom a is represented as a, instead of a.

Collective Belief Revision

Indeed, it can be argued that the PCC is too restrictive, as it demands that, if all individual agents revise by an epistemic input, then the collective agent should revise by the same sentence as well. Yet, this strong requirement for collective change may be completely undesirable, since, in a sense, it restricts the independence of agents. Let us illustrate the restrictive requirements of the PCC through the subsequent concrete example.

Example 25 (Restrictive Requirements of the PCC). Let P = {a, b, c}, let K1, K2, K3 be three belief sets such that K1 = Cn { a, b, c} , K2 = Cn { a, b, c}

and K3 = Cn { a, b, c} , and let φ be a sentence of L such that JφK = {a, b, c}, {a, b, c}, {a, b, c}, {a, b, c} . Notice that φ contradicts each one of K1, K2 and K3. Moreover, let M, 1, . . . , 6 be a community of 6 rational agents (e.g., an organization s board of directors), where M is a Hamming-based majority merging function.16 Lastly, consider the two profiles E1 = {{K1, K1, K1, K1, K1, K1}} and E2 = {{K1, K1, K2, K2, K3, K3}} of E. On that premises, Table 1 presents the sum of the Hamming distances between each one of the possible worlds { a, b, c}, { a, b, c} and { a, b, c} (corresponding to K1, K2, K3, respectively) and each possible world of M.17 As any Hamming-based majority merging function is defined by means of the possible worlds of M to which the minimum sum of the Hamming distances corresponds, it follows that M(E1) = M(E2) = Cn { a, b, c} (cf. last line of Table 1). Now, suppose, for simplicity, that all 6 individual agents utilize a single AGM revision function , such that it assigns at K1, K2, K3 (via condition (R)) the following faithful preorders K1, K2, K3 over M, respectively:

JK1K = { a, b, c} K1 {a, b, c} K1 All other possible worlds of M

JK2K = { a, b, c} K2 {a, b, c} K2 All other possible worlds of M

JK3K = { a, b, c} K3 {a, b, c} K3 All other possible worlds of M

Then, it follows from condition (R) that JK1 φK = {a, b, c} and JK2 φK = JK3 φK = {a, b, c} . By calculating the required Hamming distances (in an analogous way as it was done in Table 1), we can derive that

M K1 φ, K1 φ, K1 φ, K1 φ, K1 φ, K1 φ = Cn {a, b, c} and

M K1 φ, K1 φ, K2 φ, K2 φ, K3 φ, K3 φ = Cn { a, b, c} .

Observe, however, that the aforementioned entirely sensible scenario is prohibited by the PCC, as condition (CC) implies that

M K1 φ, K1 φ, K1 φ, K1 φ, K1 φ, K1 φ = M K1 φ, K1 φ, K2 φ, K2 φ, K3 φ, K3 φ .

Obviously yet, the latter equality is an unreasonable requirement, which imposes unnecessary/unnatural restrictions to the process of collective belief revision.

16. A majority merging function M is an IC quasi-merging function that satisfies the following majority postulate: Mµ(E2) n Mµ(E1 En 2 ). A concrete example of the operation of Hamming-based majority merging functions is Example 4.4 of Konieczny and P erez (2002, p. 786). 17. Recall that the Hamming distance between two possible worlds is the number of atoms on which the two possible worlds disagree.

Possible World

K1 { a, b, c}

K2 { a, b, c}

K3 { a, b, c}

Sum of Hamming Distances

{a, b, c} 3 2 2 7

{ a, b, c} 2 1 1 4

{a, b, c} 2 1 3 6

{a, b, c} 2 3 1 6

{ a, b, c} 1 0 2 3

{a, b, c} 1 2 2 5

{ a, b, c} 1 2 0 3

{ a, b, c} 0 1 1 2

Table 1: The sum of the Hamming distances between each one of the possible worlds { a, b, c}, { a, b, c} and { a, b, c} (corresponding to K1, K2, K3, respectively) and each possible world of M. Observe that the minimum sum of the Hamming distances corresponds to the possible world { a, b, c} (last line of the table).

8. Alternative Criteria of Collective Change

As we showed in Section 6, the compliance of the PCC with widely-accepted tools of belief revision and belief merging is facing serious hurdles. In response to this unsatisfactory situation, we propose in this section two alternative criteria that characterize the evolution of collective knowledge, and evaluate their compliance with the aforementioned tools of belief change. We, certainly, do not claim that the proposed criteria are the only route forward; our sole aim here is to provide potential properties that the process of collective belief revision should/could respect. The proposed properties of collective change are encoded into the subsequent conditions (CP1) & (CP2), which are not captured by (i.e., do not follow from) the PCC. Both conditions (CP1) & (CP2) are properties that a community M, 1, . . . , n of n rational agents can respect, and are expressed in terms of IC quasi-merging functions that can adhere to integrity constraints.

(CP1) Mφ K1, . . . , Kn = M K1, . . . , Kn φ.

(CP2) If φ Ki for all i {1, . . . , n}, then Mφ K1, . . . , Kn = M K1 1 φ, . . . , Kn n φ .

Condition (CP1) asserts that the Mφ-aggregation of K1, . . . , Kn should coincide with the M-aggregation of K1, . . . , Kn revised by the epistemic input φ, through an AGM revision function . Condition (CP2) states that, for any sentence φ that contradicts each one

Collective Belief Revision

of the belief sets K1, . . . , Kn, the Mφ-aggregation of K1, . . . , Kn should be identical to the M-aggregation of the revised belief sets K1 1 φ, . . . , Kn n φ. It is easy to verify that, if both conditions (CP1) & (CP2) hold, then, for any sentence φ that contradicts each one of K1, . . . , Kn, there exists an AGM revision function such that

M K1, . . . , Kn φ = M K1 1 φ, . . . , Kn n φ .

The previous equality is precisely condition (CC) of Section 5 that encodes the PCC. Against this background, an unsatisfiability result can be formulated proving that there is an IC quasi-merging function M, such that, for any AGM revision function , condition (CP1) is violated.

Theorem 26. There exists an IC quasi-merging function M, for which there is no AGM revision function such that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ M(K1, . . . , Kn), Mφ(K1, . . . , Kn) = M(K1, . . . , Kn) φ.

Proof. Let M be an IC quasi-merging function such that, for a sentence φ L and two profiles {{K1, . . . , Kn}}, {{K 1, . . . , K n}} E, M(K1, . . . , Kn) = M(K 1, . . . , K n) and Mφ(K1, . . . , Kn) = Mφ(K 1, . . . , K n). Next, let be an arbitrary AGM revision function, and suppose towards contradiction that Mφ(K1, . . . , Kn) = M(K1, . . . , Kn) φ and Mφ(K 1, . . . , K n) = M(K 1, . . . , K n) φ. Since M(K1, . . . , Kn) = M(K 1, . . . , K n), we derive that Mφ(K1, . . . , Kn) = Mφ(K 1, . . . , K n), which is a contradiction.

Despite the impossibility of Theorem 26, it is noteworthy that condition (CP1) is indeed satisfied for any singleton profile of E. This observation follows from the following two remarks: Firstly, from the fact that, for any IC quasi-merging function M and any belief set K, M(K) = K. Secondly, from a result of Konieczny and P erez (2002), who showed that IC quasi-merging functions induce AGM revision functions, since, as they prove, for any IC quasi-merging function M, the revision function , defined as K φ = Mφ(K), is an AGM revision function.18

Let us now turn to the investigation of condition (CP2). For that case, we present Theorem 27 which is a satisfiability result showing that, when the individual agents of a community employ a specific UR operator for implementing revision (namely, a UR operator induced from an indistinguishable total preorder over possible worlds), there exists an IC quasi-merging function M such that condition (CP2) is satisfied.19

Theorem 27. Let be an indistinguishable total preorder over M, and let be the UR operator generated from , by means of conditions (US) and (R). Then, there exists an IC quasi-merging function M such that, for any profile {{K1, . . . , Kn}} E and any sentence φ L such that φ Ki, for all i {1, . . . , n}, Mφ(K1, . . . , Kn) = M K1 φ, . . . , Kn φ .

Proof. For proving the theorem, firstly, we shall semantically construct an appropriate IC quasi-merging function M. To that end, for any profile E E, we define a total preorder E over M, such that:

18. To be precise, this result of Konieczny and P erez (2002), which is their Theorem 5.3, concerns IC merging functions; however, it can be easily verified by the proof of this theorem that the result also holds for the more general IC-quasi merging functions. 19. Recall that a total preorder over M is indistinguishable iff, for any r, r M, r r (cf. Section 2).

For all r, r JEK, r E r .

If r JEK and r / JEK, then r E r .

For all r, r / JEK, r E r iff r r .

The total preorder E over M sets all worlds in JEK equally plausible and strictly more plausible (with respect to E) than any world outside JEK. Furthermore, E is defined to be identical to the total preorder , on their sub-domain M JEK M JEK . Next, we will show that the total preorder E satisfies all conditions (i) (vi) of Definition 6 (cf. Section 4). The fact that E satisfies conditions (i), (ii) and (iii) is obvious from the definition of E. For condition (iv), let K1, K2 be two belief sets, and let r be any world in JK1K. If JK1K JK2K = , then conditions (i) and (ii) entail that there is a world r in q {K1} {K2} y = JK1K JK2K, and thus in JK2K, such that r {K1} {K2} r. If JK1K JK2K = , then obviously, for any worlds z, z M, z, z / q {K1} {K2} y = JK1K JK2K, and thus, z {K1} {K2} z iff z z . Since the total preorder is indistinguishable, it follows that, for any worlds z, z M, z {K1} {K2} z . Hence, we derive that there is a world r JK2K, such that r {K1} {K2} r, as desired. For condition (v), let E1, E2 be two profiles of E and let r, r be two worlds of M, such that r E1 r and r E2 r . If r JE1 E2K, then conditions (i) and (ii) entail that r E1 E2 r , as desired. Assume, therefore, that r / JE1 E2K. Hence, r / JE1K JE2K, which means that either r / JE1K or r / JE2K, or both. If r / JE1K, we derive from r E1 r

that r / JE1K as well, and thus r / JE1K JE2K. Therefore, it follows from r E1 r and condition (US) that r r , and again, from r r and the same condition that r E1 E2 r . If r / JE2K, we get with a symmetric line of reasoning that r E1 E2 r . Hence, in any case, it is true that r E1 E2 r , as desired. For condition (vi), let E1, E2 be two profiles of E and let r, r be two worlds of M, such that r E1 r and r E2 r . Given that the total preorder is indistinguishable, r E1 r

entails that r JE1K and r / JE1K, and similarly, r E2 r entails that r JE2K and r / JE2K. Hence, r JE1K JE2K and r / JE1K JE2K. Since JE1K JE2K = JE1 E2K, condition (ii) implies then that r E1 E2 r , as desired. Now, let E = {{K1, . . . , Kn}} be a profile of E, and let φ be a sentence of L such that φ Ki, for all i {1, . . . , n}. Since the total preorder E over M satisfies all conditions (i) (vi) of Definition 6, it induces, via condition (M) of Theorem 7, an IC quasi-merging function M such that q Mφ(K1, . . . , Kn) y = min(JφK, E). Given that JKi K JφK = ,

for all i {1, . . . , n}, it follows that n T

i=1 JKi K JφK = , which means that JEK JφK =

. Then, the construction of the total preorder E entails that q Mφ(K1, . . . , Kn) y = min(JφK, ). Furthermore, since is a UR operator, it follows from postulate (UR) that Ki φ = Kj φ = H, for all i, j {1, . . . , n}.20 Therefore, we have from postulate (IC2)

that M K1 φ, . . . , Kn φ = n S

Ki φ = H H | {z } n = H. Moreover, from condi-

20. The UR operator is an AGM revision function that implements a type of revision named by Alchourr on et al. (1985) and G ardenfors (1988) full-meet revision.

Collective Belief Revision

tion (US), it is true that JHK = min(JφK, ). Combining the above, we derive that Mφ(K1, . . . , Kn) = M K1 φ, . . . , Kn φ , as desired.

Although Theorem 27 shows that condition (CP2) can be satisfied for an IC quasimerging function and an AGM revision function, it can be argued that its assumptions are rather strong; not only it demands that the alluded AGM revision function is a UR operator a fact implying a uniform perception of the domain s dynamics by the community , but also it requires this UR operator be induced (via (US) and (R)) by means of a specific type of total preorder over possible worlds i.e., an indistinguishable total preorder over M that sets all possible worlds in a single equivalence class. Summing up, in the present section, we took a first step towards the formulation of (plausible) properties to which collective change should/could adhere. Given that the knowledge-dynamics of collective agents are equally vital as the knowledge-dynamics of individual agents, further investigation towards this direction constitutes an imperative task.

9. Conclusion

In this article, we studied the dynamics of collective agents. By formulating David Westlund s PCC in the realm of genuine belief revision, we firstly established a number of unsatisfiability results concerning the combination of AGM revision functions with principal types of merging operators (namely, union-when-possible, consensus and radical merging functions). In particular, we showed that there exist communities of rational agents (who behave rationally at the individual level as each agent employs an AGM revision function), such that, for any union-when-possible or consensus merging function, violate the PCC (Theorems 16 and 18). This outcome concerns also the IC quasi-merging functions and the formula-based merging functions, as these are union-when-possible merging functions (Corollary 17). The case of radical merging functions is even worse, as the use of any radical merging function to aggregate the beliefs of rational agents always leads to the violation of the PCC (Theorem 19). All the aforementioned impossibility results come to extend in the realm of belief revision the negative results established by Westlund (2010, Observations 6 10) for the operations of contraction and expansion. At the opposite of the impossibility results, we established a number of satisfiability results too. Specifically, we showed that the satisfaction of the PCC is indeed feasible for union-when-possible, consensus and singular merging functions, if the agents of a community revise their beliefs employing operators that implement uniform belief revision (Theorems 20, 21 and 23). These satisfiability results although demand the rather strong requirement of an homogeneous perception of the dynamics of the domain are of interest in their own right, but also offer a proof-of-concept for uniform belief revision. Notwithstanding that the aforementioned satisfiability results show that, under certain (rather strict) requirements, the satisfaction of the PCC is indeed obtainable, the derived impossibilities are certainly not a good indication for the suitability of that property. Indeed, as we demonstrated in the representative Example 25, the PCC is too restrictive, as it prohibits perfectly sensible scenarios of collective belief revision.

Mainly in response to the unsatisfactory situation regarding the suitability of the PCC, two alternative criteria that characterize the revision of collective knowledge, based on Konieczny and Pino P erez s IC quasi-merging functions, were sought. The evaluation of the compliance of these alternative criteria of collective change with belief revision and belief merging showed controversial indications, as both satisfiability and unsatisfiability results were obtained. Future work shall be devoted to the investigation of (plausible) properties to which the evolution of collective knowledge should/could adhere (as earlier stated), as well as to the study of the interrelation between the results established herein and Westlund s results, by means of the well-known Levi and Harper Identities.

Acknowledgments

The author expresses his gratitude to Pavlos Peppas for the fruitful discussions on the topic of this study, as well as to the anonymous reviewers for their constructive input on previous versions of this article.

Alchourr on, C., G ardenfors, P., & Makinson, D. (1985). On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic Logic, 50(2), 510 530.

Aravanis, T. (2020). On uniform belief revision. Journal of Logic and Computation, 30, 1357 1376.

Aravanis, T., & Peppas, P. (2022). Theory-relational belief revision. Annals of Mathematics and Artificial Intelligence, 90, 573 594.

Areces, C., & Becher, V. (2001). Iterable AGM functions. In Williams, M.-A., & Rott, H. (Eds.), Frontiers in Belief Revision, Vol. 22 of Applied Logic Series, pp. 165 196. Springer, Dordrecht.

Baral, C., Kraus, S., Minker, J., & Subrahmanian, V. S. (1992). Combining knowledge bases consisting of first-order theories. Computational Intelligence, 8, 45 71.

Benferhat, S., Dubois, D., Lang, J., Prade, H., Saffiotti, A., & Smets, P. (1998). A general approach for inconsistency handling and merging information in prioritized knowledge bases. In Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR 1998), pp. 466 477.

Everaere, P., Konieczny, S., & Marquis, P. (2010). Disjunctive merging: Quota and Gmin merging operators. Artificial Intelligence, 174, 824 849.

Ferm e, E., & Hansson, S. O. (2018). Belief Change: Introduction and Overview. Springer International Publishing.

G ardenfors, P. (1988). Knowledge in Flux Modeling the Dynamics of Epistemic States. MIT Press, Cambridge, Massachusetts.

Gilbert, M. (1987). Modelling collective belief. Synthese, 73, 185 204.

Collective Belief Revision

Gilbert, M. (2004). Collective epistemology. Episteme, 1, 95 107.

Katsuno, H., & Mendelzon, A. (1991). Propositional knowledge base revision and minimal change. Artificial Intelligence, 52(3), 263 294.

Kfir-Dahav, N. E., & Tennenholtz, M. (1996). Multi-agent belief revision. In Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 1996), pp. 175 194.

Konieczny, S. (2000). On the difference between merging knowledge bases and combining them. In Proceedings of the 7th International Conference on Principles of Knowledge Representation and Reasoning (KR 2000), pp. 135 144.

Konieczny, S., & P erez, R. P. (2002). Merging information under constraints: A logical framework. Journal of Logic and Computation, 12(5), 773 808.

Konieczny, S., & P erez, R. P. (2011). Logic based merging. Journal of Philosophical Logic, 40, 239 270.

Labb e, I., van Dokkum, P., Nelson, E., Bezanson, R., Suess, K. A., Leja, J., Brammer, G., Whitaker, K., Mathews, E., Stefanon, M., & Wang, B. (2023). A population of red candidate massive galaxies 600 Myr after the Big Bang. Nature, 616, 266 269.

Liu, F., Seligman, J., & Girard, P. (2014). Logical dynamics of belief change in the community. Synthese, 191, 2403 2431.

Liu, W., & Williams, M.-A. (2001). A framework for multi-agent belief revision. Studia Logica, 67, 291 312.

Malheiro, B., Jennings, N. R., & Oliveira, E. (1994). Belief revision in multi-agent systems. In Proceedings of the 11th European Conference on Artificial Intelligence (ECAI 1994), pp. 294 298.

Maynard-Zhang, P., & Lehmann, D. (2003). Representing and aggregating conflicting beliefs. Journal of Artificial Intelligence Research, 19, 155 203.

Minsky, M. (1988). The Society of Mind. Simon & Schuster.

Paranamana, P., Wang, P., & Shafto, P. (2022). Evolution of beliefs in social networks. Collective Intelligence, 1, 1 14.

Peppas, P. (2008). Belief revision. In van Harmelen, F., Lifschitz, V., & Porter, B. (Eds.), Handbook of Knowledge Representation, pp. 317 359. Elsevier Science.

Peppas, P. (2014). A panorama of iterated revision. In Hansson, S. O. (Ed.), David Makinson on Classical Methods for Non-Classical Problems, pp. 71 94. Springer Netherlands.

Tojo, S. (2013). Collective belief revision in linear algebra. In 2013 Federated Conference on Computer Science and Information Systems, pp. 175 178.

Westlund, D. (2010). Rational belief changes for collective agents. In Olsson, E. J., & Enqvist, S. (Eds.), Belief Revision meets Philosophy of Science, Vol. 21 of Logic, Epistemology, and the Unity of Science, pp. 213 224. Springer, Dordrecht.

Wray, K. B. (2001). Collective belief and acceptance. Synthese, 129, 313 333.