Modeling knowledge dynamics in multi-agent systems based on informants

Luciano H. Tamargo; Alejandro J. García; Marcelo A. Falappa; Guillermo R. Simari

doi:10.1017/S0269888912000021

Modeling knowledge dynamics in multi-agent systems based on informants

Published online by Cambridge University Press: 22 February 2012

Luciano H. Tamargo ,

Alejandro J. García ,

Marcelo A. Falappa and

Guillermo R. Simari

Show author details

Luciano H. Tamargo*: Affiliation:
Department of Computer Science and Engineering, Artificial Intelligence Research and Development Laboratory, Universidad Nacional del Sur, Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Bahía Blanca, Argentina
Alejandro J. García*: Affiliation:
Department of Computer Science and Engineering, Artificial Intelligence Research and Development Laboratory, Universidad Nacional del Sur, Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Bahía Blanca, Argentina
Marcelo A. Falappa*: Affiliation:
Department of Computer Science and Engineering, Artificial Intelligence Research and Development Laboratory, Universidad Nacional del Sur, Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Bahía Blanca, Argentina
Guillermo R. Simari*: Affiliation:
Department of Computer Science and Engineering, Artificial Intelligence Research and Development Laboratory, Universidad Nacional del Sur, Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Bahía Blanca, Argentina
*: e-mails: lt@cs.uns.edu.ar, ajg@cs.uns.edu.ar, mfalappa@cs.uns.edu.ar, grs@cs.uns.edu.ar
e-mails: lt@cs.uns.edu.ar, ajg@cs.uns.edu.ar, mfalappa@cs.uns.edu.ar, grs@cs.uns.edu.ar
e-mails: lt@cs.uns.edu.ar, ajg@cs.uns.edu.ar, mfalappa@cs.uns.edu.ar, grs@cs.uns.edu.ar
e-mails: lt@cs.uns.edu.ar, ajg@cs.uns.edu.ar, mfalappa@cs.uns.edu.ar, grs@cs.uns.edu.ar

Article contents

Abstract
Introduction and motivation
Epistemic model for Multi-Source Belief Revision
Sentences plausibility
Change operators based on informants
Forwarding Information
Conclusions and Related Works
Footnotes
References

Rights & Permissions

Abstract

In this paper, we model knowledge dynamics in agents’ belief bases in a collaborative multi-agent system (MAS). Four change operators are introduced: expansion, contraction, prioritized revision, and non-prioritized revision. For all of them, both constructive definitions and an axiomatic characterization by representation theorems are given. We formally justify minimal change, consistency maintenance, and non-prioritization principles. These operators are based on an epistemic model for multi-source belief revision in which a rational way to weigh the beliefs using a credibility order among agents is developed. The defined operators can be seen as skills added to the agents improving the collective reasoning of a MAS.

Information

Type: Articles
Information: The Knowledge Engineering Review , Volume 27 , Issue 1 , 22 February 2012 , pp. 87 - 114

DOI: https://doi.org/10.1017/S0269888912000021 [Opens in a new window]
Copyright: Copyright © Cambridge University Press 2012

1 Introduction and motivation

Belief revision (BR) is the process of changing beliefs to take into account a new piece of information, observation, or evidence. The AGM paradigm (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985) has been widely accepted as a standard framework for BR; usually, Individual Belief Revision (IBR) in a single-agent environment is achieved satisfying or adapting AGM postulates.

Single-agent systems have evolved into multi-agent systems (MAS), where multiple interacting agents can collaborate, negotiate, discuss, etc., in order to achieve their goals. In many multi-agent domains and applications, each agent has its own initial beliefs as well as beliefs acquired from other informant agents. Hence, an agent can receive information from other agents which is contradictory with its own current beliefs. Therefore, IBR needs to be extended to multi-agent environments.

This paper focuses on multi-source belief revision (MSBR); that is, BR performed by a single agent that can obtain new beliefs from multiple informants. Therefore, one of the contributions of our approach is the definition of an epistemic model for MSBR that considers both beliefs and meta-information representing the credibility of the belief's source. We investigate how the belief base of an agent can be rationally modified when the agent receives information from other agents that can have different degrees of credibility. Thus, our main contribution is the definition based on the AGM model of four different belief change operators which use the credibility of informant agents in order to decide prevailing information. These operators are defined through constructive models and representation theorems that provide a complete axiomatic characterization for the proposed formalism.

An analysis of BR in MAS was developed in Liu & Williams (Reference Liu and Williams1999) where the hierarchy of Figure 1 was introduced. There, the distinction of Multi-Agent Belief Revision (MABR), MSBR and Single-agent Belief Revision (SBR) is clearly explained. In contrast to MSBR, MABR investigates the overall BR behavior of agent teams or a society in which, in order to pursue the mutual goal, the agents involved need to communicate, cooperate, coordinate, and negotiate with one another. A MABR system is a MAS whose mutual goal involves BR. Different formalisms have been presented to deal with MABR (Malheiro et al., Reference Malheiro, Jennings and Oliveira1994; Kfir-Dahav & Tennenholz, Reference Kfir-Dahav and Tennenholz1996; Liu & Williams, Reference Liu and Williams1999, Reference Liu and Williams2001). Nevertheless, in MSBR, an IBR process is carried out in a multi-agent environment where the new information may come from multiple sources that may be in conflict. The main focus of our work is this kind of BR, also studied by Dragoni et al. (Reference Dragoni, Giorgini and Puliti1994).

Figure 1

Belief Revision Hierarchy.

Consider, for instance, the following (simplified) scenario. An agent A has three informants A ₁, A ₂ and A ₃ where, for A, A ₃ is the most credible and the other two are equally credible. Agent A wants to use a resource S, but it believes that S is not available. Then A ₁ informs A that S is available and hence, A revises its beliefs to take into account this new piece of information. If then A ₃ informs A that S is not available, since A ₃ is more credible than A ₂, then A should change its belief about S. Observe that new information could be rejected if the new belief is informed by a less credible agent.

In the literature, there are several studied prioritized methods ( e.g. partial meet revision (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985) and kernel revision (Hansson, Reference Hansson1999)). In these methods, the new information has priority over the beliefs in the base of the receiver agent. However, as is mentioned in Fermé and Hansson (Reference Fermé and Hansson1999) and Falappa et al. (Reference Falappa, Kern-Isberner and Simari2002), in some scenarios a prioritized method can be unrealistic. Thus, some models of BR have been developed allowing for two options: either the new information is fully accepted or completely rejected (Hansson, Reference Hansson1997; Makinson, Reference Makinson1997; Hansson et al., Reference Hansson, Fermé, Cantwell and Falappa2001; Konieczny et al., Reference Konieczny, Grespan and Pérez2010). For instance, if information comes from different sources, and these sources are not equally credible, a non-prioritized method can be more adequate. In contrast, if an agent always acquires information from the same source, then a prioritized method can be used.

In this paper, based on kernel revision, we develop a complete change model for MSBR where both non-prioritized and prioritized BR are defined. First, we propose a formalism for knowledge representation in a MAS; and then, based on this formalism we define different change operators for MSBR, either to add beliefs (expansion), to withdraw beliefs (contraction), or to maintain consistency (revision). We will introduce a credibility order among agents and, based on this order, a comparison criterion among beliefs is defined. In the revision process, if inconsistency arises, the credibility order is used to decide which information prevails. The contraction operator is based on kernel contraction (Hansson, Reference Hansson1994) and also uses the credibility order to decide which information prevails. We show that the proposed non-prioritized revision operator satisfies the minimal change principle, and incoming information can be rejected when the agent has more credible beliefs that contradict the new information. In the literature, there are other approaches that also attach information to agents’ beliefs that represents its credibility: Benferhat et al. (Reference Benferhat, Dubois and Prade1993), Dragoni et al. (Reference Dragoni, Giorgini and Puliti1994), Cantwell (Reference Cantwell1998), and Benferhat et al. (Reference Benferhat, Dubois, Prade and Williams2002). However, our approach differs from them as we will explain in detail below.

Some preliminary works related to this paper have been reported in two workshop papers (Tamargo et al., Reference Tamargo, García, Falappa and Simari2008, Reference Tamargo, García, Falappa and Simari2009). However, here, we extend both in several ways. We will define different operators which describe a complete change model based on informants: expansion, contraction, prioritized revision, and non-prioritized revision. These operators are based on an epistemic model in which a rational way to weigh beliefs is developed. These operators can be seen as skills added to the agents which improve the collective reasoning of a MAS. For these operators we give both constructive definitions and an axiomatic characterization of them by representation theorems. We also formally justify minimal change and consistency principles. Thus, a complete change model where both prioritized and non-prioritized BR are defined. The rest of this paper is structured as follows. Next, Section 2 introduces the epistemic model for MSBR. Section 3 develops the concept of plausibility used to decide which beliefs will be preserved or erased in change operators. Section 4 defines change operators based on informants: expansion, two kinds of contractions, and two kinds of revisions. Section 5 presents forwarding information among agents. Finally, in Section 6 conclusions are given and related works are commented. All proofs can be found the Section 7.

2 Epistemic model for Multi-Source Belief Revision

In this section, we introduce an epistemic model for MSBR which is based on informants. Then, in the following sections, we will define change operators based on agents interactions to add beliefs (expansion), to withdraw beliefs (contraction), and to revise beliefs. Note that the AGM model (Alchourrón et al., Reference Alchourrón, Gärdenfors and Makinson1985) represents epistemic states by means of belief sets, that is, sets of sentences closed under logical consequence. Other models use belief bases; that is, arbitrary sets of sentences (Fuhrmann, Reference Fuhrmann1991; Hansson, Reference Hansson1992). Our epistemic model is based on an adapted version of belief bases which have additional information.

We adopt a propositional language $)(--><$>{\cal L}<$><$>\{\neg, \, \wedge, \, \vee, \, \rightarrow, \, \leftrightarrow\}<$><$>B \subseteq Cn(B)<$><$>Cn(B) = Cn(Cn(B))<$><$>B \subseteq C<$><$>Cn(B) \subseteq Cn(C)<$><$>\alpha \in Cn(B)<$><$>\alpha \in Cn(B')<$><$>B' \subseteq B<$><$>\alpha \in Cn(B)<$><$>B \vdash \alpha<$><!--$ .

When interacting, agents will incorporate the received information into their knowledge base in form of information objects. An information object will associate a sentence with an agent. For the identification of the individual agents we introduce a finite set of agent identifiers that is denoted as $)(--><$>{\Bbb A} = \{A_1, \ldots, A_n\}<$><!--$ .

Definition 1 (Information object)An information object is a tuple $)(--><$>I=(\alpha,A_i)<$><$>\alpha<$><$>{\cal L}<$><$>A_i \in {\Bbb A}<$><!--$ .

Information objects are used to represent an agent's belief base. Observe that the agent identifier of an information object I can be used for representing the agent from which the information is received, or the agent that has generated the information. In Section 5, we will describe different criteria for forwarding information that will determine which agent identifier will be used.

Definition 2 (Belief base)Let $)(--><$>{\Bbb A} = \{A_1, \ldots, A_n\}<$><$>A_i \ (1\leq i \leq n)<$><$>K_{A_i}=\{I_{1}, \ldots ,I_{k}\}<$><$>(\alpha, A_j) (1\leq j \leq n)<$><$>(j \neq i)<$><!--$ and proper beliefs .

Example 1Consider the set of agent identifiers $)(--><$>{\Bbb A} = \{A_1, A_2, A_3,A_4\}<$><$>K_{A_1} = \{(\beta, A_{1}),(\alpha, A_{2}), (\alpha, A_{3}), <$><$>(\alpha \rightarrow \beta, A_{4}), (\omega, A_{3}), (\omega\rightarrow \beta, A_{4}), <$><$>(\alpha \rightarrow \delta, A_{1}), <$><$>(\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, A_{1}), (\gamma, A_{3}), (\gamma, A_{4}), (\gamma \rightarrow \epsilon,A_{2})\}<$><$>K_{A_1}<$><!--$ has two information objects with the sentence α; however, each one has a different agent identifier.

The set $)(--><$>{\cal K} = 2^{{\cal L} \times {\Bbb A}}<$><$>K\in{\cal K}<$><!--$ .

Definition 3 (Sentence function)The sentence function Sen ( $)(--><$> Sen: {\cal K} \rightarrow 2^{{\cal L}}<$><$>K \in {\cal K}<$><$>Sen(K) = \{\alpha : (\alpha, A_i) \in K\}<$><!--$ .

In our proposal, each agent $)(--><$>A \in {\Bbb A}<$><$>Cn(Sen(K))<$><!-- is consistent.

Definition 4 (Agent identifier function)The agent identifier function Ag ( $)(--><$>Ag \, : {\cal K} \rightarrow 2^{{\Bbb A}}<$><$>K \in {\cal K}<$><$>Ag(K) = \{A_i : (\alpha, A_i) \in K\}<$><!--$ .

Example 2Consider $)(--><$>K_{A_1}<$><!--$ of Example 1. Then,

• $)(--><$>Sen(K_{A_1}) = \{\beta,\alpha, \alpha \rightarrow \beta,\omega , \omega\rightarrow \beta, \alpha \rightarrow \delta,\delta \rightarrow \beta,\gamma,\gamma \rightarrow \epsilon\}<$><!--$ .
• $)(--><$>Ag(K_{A_1}) = \{A_1,A_2,A_3,A_4\}<$><!--$ .

The agent identifier of an information object can be used to evaluate the truthfulness of the received information. In our approach, an assessment function will be used for representing the credibility each agent assigns to other agents. For defining this assessment, we assume a set of credibility labels $)(--><$>{\cal C} =\{c_1,\ldots ,c_k\}<$><$>\prec_c<$><$>c_{3} \in {\cal C}<$><$>c_{1} \prec_c c_{2}<$><$>c_{2} \prec_c c_{3}<$><$>c_{1} \prec_c c_{3}<$><$>c_{1} \prec_c c_{2}<$><$>c_{2} \prec_c c_{1}<$><$>c_{1} \prec_c c_{1}<$><$>c_{1} \prec_c c_{2}<$><$>c_{2} \prec_c c_{1}<$><!--$ does not hold. That is, following (Hein, 2010), we assume an irreflexive total order (also known strict total order).

Definition 5 (Assessment)Let $)(--><$>{\Bbb A} = \{A_1, \ldots, A_n\}<$><$>{\cal C} =\{c_1,\ldots,c_k\}<$><$>c_{A_i}<$><$>c_{A_i}: {\Bbb A} \rightarrow {\cal C}<$><$>{\cal C}<$><$>A_j \in {\Bbb A}<$><!--$ .

The set of credibility labels is the same for all agents; however, each agent will have its own assessment and different agents may have different assessments. Thus, the assessment of an agent can be replaced in a modular way without changing its belief base and without affecting other agents assessments.

Example 3Consider the set of agent identifiers $)(--><$>{\Bbb A} = \{A_1, A_2, A_3,A_4\}<$><$>{\cal C} =\{c_1,c_2,c_3,c_4,c_5,c_6\}<$><$>c_1 \prec_c c_2 \prec_c c_3 \prec_c c_4 \prec_c c_5 \prec_c c_6<$><$>{\Bbb A}<$><!--$ can have the following assessments:

$)(--><$>c_{A_{1}}(A_1) = c_1<$><$>c_{A_{1}}(A_2) = c_2<$><$>c_{A_{1}}(A_3) = c_2<$><$>c_{A_{1}}(A_4) = c_3<$><!--$ .
$)(--><$>c_{A_{2}}(A_1) = c_2<$><$>c_{A_{2}}(A_2) = c_2<$><$>c_{A_{2}}(A_3) = c_2<$><$>c_{A_{2}}(A_4) = c_2<$><!--$ .
$)(--><$>c_{A_{3}}(A_1) = c_4<$><$>c_{A_{3}}(A_2) = c_3<$><$>c_{A_{3}}(A_3) = c_2<$><$>c_{A_{3}}(A_4) = c_1<$><!--$ .
$)(--><$>c_{A_{4}}(A_1) = c_4<$><$>c_{A_{4}}(A_2) = c_3<$><$>c_{A_{4}}(A_3) = c_2<$><$>c_{A_{4}}(A_4) = c_1<$><!--$ .

Observe that for agent A ₂ all agents have the same credibility, for agent A ₃ all agents have different credibility, and agents A ₃ and A ₄ have the same assessment.

Thus, based on its own assessment, each agent can have a credibility order over the set $)(--><$>{\Bbb A}<$><!--$ .

Definition 6 (Credibility order among agents)A credibility order among agents for an agent A _i, denoted by ‘ $)(--><$>\leq^{A_i}_{Co}<$><$>{\Bbb A}<$><$>A_{1} \leq^{A_i}_{Co} A_{2}<$><$>A_{2}<$><$>c_{A_i}(A_1) \prec_c c_{A_i}(A_2)<$><$>c_{A_i}(A_1)= c_{A_i}(A_2)<$><$>A_{1} \lt^{A_i}_{Co} \ A_{2}<$><$>A_{1} \leq^{A_i}_{Co} A_{2}<$><$>A_{2} \not\leq^{A_i}_{Co} A_{1}<$><$>A_{1} =^{A_i}_{Co} A_{2}<$><$>A_{1} \leq^{A_i}_{Co} A_{2}<$><$>A_{2} \leq^{A_i}_{Co} A_{1}<$><!--$ .

Since ‘ $)(--><$>\leq^{A_i}_{Co}<$><$>{\Bbb A}<$><$>A_1, A_2, A_3 \in {\Bbb A}<$><!--$ it holds:

• Reflexive: $)(--><$>A_{1} \leq^{A_i}_{Co} A_{1}<$><!--$ .
• Totality or Completeness: $)(--><$>A_{1} \leq^{A_i}_{Co} A_{2}<$><$>A_{2} \leq^{A_i}_{Co} A_{1}<$><!--$ .
• Transitivity: if $)(--><$>A_{1} \leq^{A_i}_{Co} A_{2}<$><$>A_{2} \leq^{A_i}_{Co} A_{3}<$><$>A_{1} \leq^{A_i}_{Co} A_{3}<$><!--$ .
• Antisymmetry: if $)(--><$>A_{1} \leq^{A_i}_{Co} A_{2}<$><$>A_{2} \leq^{A_i}_{Co} A_{1}<$><$>A_{1} =^{A_i}_{Co} A_{2}<$><!--$ .

Example 4Consider the set of agent identifiers $)(--><$>{\Bbb A} = \{A_1, A_2, A_3,A_4\}<$><$>{\cal C} =\{c_1,c_2,c_3\}<$><$>c_1 \prec_c c_2 \prec_c c_3<$><$>c_{A_{1}}(A_1) = c_1<$><$>c_{A_{1}}(A_2) = c_2<$><$>c_{A_{1}}(A_3) = c_2<$><$>c_{A_{1}}(A_4) = c_3<$><$>A_{1} \leq^{A_1}_{Co} A_{2}, A_{1} \leq^{A_1}_{Co} A_{3}, A_{1} \leq^{A_1}_{Co} A_{4}, A_{2} \leq^{A_1}_{Co} A_{3}, A_{3} \leq^{A_1}_{Co} A_{2}, A_{2} \leq^{A_1}_{Co} A_{4},<$><$>A_{3} \leq^{A_1}_{Co} A_{4}<$><$>A_{1} \lt^{A_1}_{Co} A_{2} =^{A_1}_{Co} A_{3} \lt^{A_1}_{Co} A_{4}<$><!--$ .

The information received by an agent can be contradictory with its current beliefs. For instance, consider again the belief base $)(--><$>(K_{A_1})<$><$>Sen(K_{A_1})\vdash \beta<$><$>\neg\beta, A_4<$><$>\neg\beta, A_4<$><$>K_{A_1}<$><$>\neg\beta, A_4<$><$>\leq^{A_i}_{Co}<$><$>K_{A_1}<$><!--$ that entail β will be considered.

Kernel contractions were introduced in (Hansson, 1994) and they are based on a selection among the sentences that are relevant to derive the sentence to be retracted. Note that kernel contractions are a generalization of safe contractions proposed in (Alchourrón and Makinson, 1985). In order to perform a contraction, kernel contractions use incision functions which cut into the minimal subsets that entail the information to be given up. Therefore, we will adapt the definition of α-kernel to our epistemic model which will be used below to define a comparison criterion among sentences (called plausibility) and to define incision functions.

Definition 7 ( $)(--><$>\bialpha<$><$>K \in {\cal K}<$><$>\alpha \in {\cal L}<$><!--$ . Then H is an α-kernel of K if and only if

1 $)(--><$>H \subseteq K<$><!--$ .
2 $)(--><$>Sen(H) \vdash \alpha<$><!--$ .
3 if $)(--><$>H′ \subset H<$><$>Sen(H′) \not\vdash\alpha<$><!--$ .

Note that an α-kernel is a minimal set of tuples from K that entails α. The set of α-kernel of K is denoted $)(--><$>K {^\kernels} \alpha<$><!--$ and is called kernel set (Hansson, 1994).

Example 5Consider $)(--><$>K_{A_1}<$><!--$ of Example 1.

$)(--><$>K_{A_1} {^\kernels} \beta = \{H_{a}, H_{b}, H_{c}, H_{d}, H_{e}, H_{f}, H_{g}, H_{h}\}<$><!--$ where

$--><$$>\matrix { \ H_{a}= \{(\beta, A_{1})\}\hfill & H_{e}= \{(\alpha, A_{2}), (\alpha \rightarrow \delta, A_{1}),(\delta \rightarrow \beta, A_{1})\} \cr H_{b}= \{(\alpha, A_{2}), (\alpha \rightarrow \beta, A_{4})\} & H_{f}= \{(\alpha, A_{3}), (\alpha \rightarrow \delta, A_{1}),(\delta \rightarrow \beta, A_{1})\} \cr H_{c}= \{(\alpha, A_{3}), (\alpha \rightarrow \beta, A_{4})\} & H_{g}= \{(\alpha, A_{2}), (\alpha \rightarrow \delta, A_{2}),(\delta \rightarrow \beta, A_{1})\} \cr \ H_{d}= \{(\omega, A_{3}), (\omega\rightarrow \beta, A_{4})\} & H_{h}= \{(\alpha, A_{3}), (\alpha \rightarrow \delta, A_{2}),(\delta \rightarrow \beta, A_{1})\}<$$><!--$

Observe that a belief base can contain the same sentence in two (or more) information objects with different agent identifiers. For instance, in Example 1 $)(--><$>\{(\alpha, A_{2}), (\alpha, A_{3})\} \subseteq K_{A_1}<$><$>(\alpha, A_j)<$><$>Sen(K_{A_i}) \not\vdash \neg\alpha<$><$>(\alpha, A_j)<$><$>K_{A_i}<$><$>Sen(K_{A_i}) \vdash \alpha<$><$>(\alpha, A_j)<$><$>K_{A_i}<$><!--$ because the credibility of the associated agent can increase the plausibility of α. From the information objects point of view, there is no redundancy due to the fact that each information object represents a different informant.

Thus, in a belief base the same sentence can be in several information objects (with different agent identifiers). Therefore, if the assessment of the agent is changed and the credibility of a particular agent is increased, then all the sentences associated to this agent automatically have more credibility. Nevertheless, it will be useful that given a belief base K, a compacted belief base K′ can be obtained; that is, a base where there are no tuples with the same sentence and the more credible associated agent remains. In order to make more efficient the construction of changes, we propose that kernel sets can be computed over compacted belief bases.

Next, a function that given a belief base returns a compacted one is introduced (Definition 10). This function needs to know which is the most credible associated agent with respect to a given sentence, and this is returned by the top agent function.

Definition 8 (Top agent function)The top agent function, $)(--><$>Top: {\cal L} \times {\cal K} \rightarrow 2^{{\cal {\Bbb A}}}<$><$>K_{A_i} \in {\cal K}<$><$>\alpha \in Sen(K_{A_i})<$><$>Top(\alpha, K_{A_i}) = \{A_{k} : (\alpha, A_{k}) \in K_{A_i}<$><$>(\alpha, A_{j}) \in K_{A_i}, A_{j} \leq^{A_i}_{Co} A_{k}\}<$><!--$ .

We assume that there is a function (see Definition 9) that based on a given policyFootnote 1 returns a single-agent identifier from a set of agent identifiers to which the assessment assigns the same label. For instance, the policy could be based on a lexicographical ordering among agent identifiers -A ₁ is lesser than A ₂.

Definition 9 (Selection function)The selection function of an agent A _i, $)(--><$>{\cal S}_{A_i}: 2^{{\Bbb A}} \rightarrow {\Bbb A}<$><!--$ , is a function such that for a given set of agent identifiers with equal credibility with respect to the assessment of A _i, it returns a single-agent identifier based on a given policy.

Definition 10 (Compact belief base function)The compact belief base function ( $)(--><$>Compact : {\cal K} \rightarrow {\cal K}<$><$>K_{A_i} \in {\cal K}<$><!--$ :

$--><$$>Compact(K_{A_i})=\{(\alpha, A_j): (\alpha, A_j) \in K_{A_i} \ and \ A_j = {\cal S}_{A_i}(Top(\alpha, K_{A_i}))\} <$$><!--$

In order to simplify the notation we use $)(--><$>K^{\uparrow}_{A_i}<$><$>Compact(K_{A_i})<$><!--$ .

Example 6Consider again the agent A ₁ of Example 1, where

$)(--><$>K_{A_1} \{(\beta, A_{1}), (\alpha, A_{2}), (\alpha, A_{3}), (\alpha \rightarrow \beta, A_{4}), (\omega, A_{3}), (\omega\rightarrow\beta, A_{4}), (\alpha \rightarrow\delta, A_{1}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta,A_{1}),<$><$>(\gamma, A_{3}), (\gamma, A_{4}), (\gamma \rightarrow \epsilon,A_{2})\}<$><$>A_{1} \lt^{A_1}_{Co} \ A_{2} =^{A_1}_{Co} \ A_{3} \lt^{A_1}_{Co} \ A_{4}<$><!--$ . Then,

• $)(--><$>Top(\gamma, K_{A_1}) = \{A_{4}\}<$><$>Top(\alpha \rightarrow\delta, K_{A_1}) = \{A_{2}\}<$><!--$ .

• $)(--><$>Top(\alpha, K_{A_1}) = \{A_{2}, A_{3}\}<$><!--$ .

• $)(--><$>{\cal S}_{A_1}(\{A_{2},A_{3}\}) = A_{2}<$><!--$ where the policy adopted is based on a lexicographical ordering among agent identifiers.

• The compact belief base is:

$--><$$>\eqalign{ K^{\uparrow}_{A_1} = \{(\beta, A_{1}), (\alpha, A_{2}),(\alpha \rightarrow \beta, A_{4}), (\omega, A_{3}),(\omega\rightarrow \beta, A_{4}), \} \ \cup \cr & \cup \{ (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, A_{1}), (\gamma, A_{4}), (\gamma \rightarrow \epsilon, A_{2})\}<$$><!--$

• $)(--><$>K^{\uparrow}_{A_1} {^\kernels} \beta = \{H_{a}, H_{b}, H_{d}, H_{g}\}<$><!--$ where

$--><$$>\matrix{ H_{a}= \{(\beta, A_{1})\} \hfill& H_{d}= \{(\omega, A_{3}), (\omega\rightarrow \beta, A_{4})\} \hfill\cr H_{b}= \{(\alpha, A_{2}), (\alpha \rightarrow \beta, A_{4})\} & H_{g}= \{(\alpha, A_{2}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta,A_{1})\}<$$><!--$

It is important to note that from the Definitions 3, 7, 8 and 10, the following proposition is straightforwardly deduced.

Proposition 1Let $)(--><$>K_{A_i} \in {\cal K}<$><$>K^{\uparrow}_{A_i} \subseteq K_{A_i}<$><$>Sen(K^{\uparrow}_{A_i}) = Sen(K_{A_i})<$><$>K^{\uparrow}_{A_i} {^\kernels} \alpha \subseteq K_{A_i}^\kernels \alpha<$><!--$ .

Consider $)(--><$>\alpha \in {\cal L}<$><$>\beta \in Sen(K_{A_i})<$><$>K_{A_i}<$><$>K^{\uparrow}_{A_i} \subset K_{A_i}<$><$>X \in K^{\uparrow}_{A_i}{^\kernels} \alpha<$><$>\beta \in Sen(X)<$><$>K_{A_i}^\kernels} \alpha<$><$>m \ \alpha{\hbox -}kernels<$><$>K^{\uparrow}_{A_i}<$><$>K^{\uparrow}_{A_i} {^\kernels} \alpha \subset K_{A_i}^\kernels} \alpha<$><$>K^{\uparrow}_{A_i}<$><$>K_{A_i}<$><!--$ .

3 Sentences plausibility

As stated above, when an agent A _i receives an information object that is inconsistent with its knowledge base (e.g. it receives ( $)(--><$>\neg\beta, A_4<$><$>Sen(K_{A_i})\vdash \beta<$><$>\leq^{A_i}_{Co}<$><$>\alpha \preceq_{K_{A_i}} \beta<$><$>c_{A_i}<$><$>K_{A_i}<$><!--$ . The plausibility of a sentence will be used to define revision and contraction operators.

The concept of plausibility is related to epistemic entrenchment (Gärdenfors and Makinson, 1988) although the epistemic entrenchment orders are structured in a very specific way, and we apply it on belief bases instead of belief sets. According to (Gärdenfors, 1992), ‘…some sentences in a belief system have a higher degree of epistemic entrenchment than others... The guiding idea for the construction is that when a belief set $)(--><$>\mathbf{K}<$><$>\mathbf{K}<$><!--$ that are given up are those having the lowest degrees of epistemic entrenchment’.

The following function characterizes all the sentences that can be entailed from a belief base.

Definition 11 (Belief function)The belief function, $)(--><$>Bel: {\cal K} \rightarrow 2^{{\cal L}}<$><$>K \in {\cal K}<$><$>Bel(K) = \{\alpha : \alpha \in {\cal L}<$><$>Sen(K) \vdash \alpha \}<$><!--$ .

Similar to Proposition 1, note that from the Definitions 8, 10 and 11, the following proposition is straightforwardly deduced.

Proposition 2Let $)(--><$>K_{A_i} \in {\cal K}<$><$>Bel(K^{\uparrow}_{A_i}) = Bel(K_{A_i})<$><!--$ .

In order to calculate the plausibility of a sentence β, all its proofs have to be analyzed. Since we adopt a cautious approach, from each β-kernel we will consider those tuples that have the agent identifiers that are less credible. Two auxiliary functions are introduced below:

Definition 12 (Least credible sources function)The least credible sources function, $)(--><$>min: {\cal K} \rightarrow 2^{{\cal K}}<$><$>K_{A_i} \in {\cal K}, \, min(K_{A_i}) = \{(\alpha, A_{k}) : (\alpha, A_{k}) \in K_{A_i}<$><$>(\delta, A_{j}) \in K_{A_i}, A_{k} \leq^{A_i}_{Co} A_{j}\}<$><!--$ .

Definition 13 (Most credible sources function)The most credible sources function, $)(--><$>max: {\cal K} \rightarrow 2^{{\cal K}}<$><$>K_{A_i} \in {\cal K}<$><$>max(K_{A_i}) = \{(\alpha, A_{k}) : (\alpha, A_{k}) \in K_{A_i}<$><$>(\delta, A_{j}) \in K_{A_i}, A_{j} \leq^{A_i}_{Co} A_{k}\}<$><!--$ .

Example 7Consider the set of agent identifiers $)(--><$>{\Bbb A} = \{A_1, A_2, A_3\}<$><$>A_{1} \lt^{A_1}_{Co} \ A_{2} \lt^{A_1}_{Co} \ A_{3}<$><$>K_{A_1} = \{(\alpha, A_1),(\alpha, A_2), (\beta, A_1),(\gamma, A_1),(\alpha\rightarrow\gamma, A_3)\}<$><!--$ be the belief base of A ₁. Then,

• $)(--><$>min(K_{A_1}) = \{(\alpha, A_{1}),(\beta, A_{1}),(\gamma, A_{1})\}<$><!--$ .
• $)(--><$>max(K_{A_1}) = \{(\alpha\rightarrow\gamma, A_3)\}<$><!--$ .

Next, based on the agent comparison criterion $)(--><$>\leq^{A_i}_{Co}<$><$>Bel(K_{A_i})<$><$>Pl(\alpha, K_{A_i})<$><$>\alpha \in Bel(K_{A_i})<$><$>\preceq_{K_{A_i}}<$><$>Bel(K_{A_i})<$><!--$ is introduced.

Definition 14 (Plausibility function)The plausibility function, $)(--><$>Pl: {\cal L} \times {\cal K} \rightarrow {\Bbb A}<$><$>K_{A_i} \in {\cal K}<$><$>\alpha \in Bel(K_{A_i})<$><!--$ :

$--><$$>Pl(\alpha, K_{A_i}) = {\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\uparrow \Vbar}_{A_i} \alpha} min(X))))<$$><!--$

Observe that the function can return more than one agent identifier, therefore uses the selection function $)(--><$>{\cal S}_{A_i}<$><$>(\gamma, A_1) \in K_{A_1}<$><$>Pl(\gamma,K_{A_1}) \not = A_1<$><$>Pl(\alpha,K_{A_1}) = A_2, \ Pl(\beta,K_{A_1}) = A_1<$><$>Pl(\gamma, K_{A_1}) = A_2<$><!--$ .

Definition 15 (Plausibility criterion)Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\{\alpha, \beta\} \subseteq Bel(K_{A_i})<$><$>\alpha \preceq_{K_{A_i}} \beta<$><$>Pl(\alpha,K_{A_i}) \leq^{A_i}_{Co} Pl(\beta,K_{A_i})<$><!--$ .

Thus, the notation $)(--><$>\alpha \preceq_{K_{A_i}} \beta<$><$>\alpha \prec_{K_{A_i}} \beta<$><$>\alpha \preceq_{K_{A_i}} \beta<$><$>\beta \npreceq_{K_{A_i}} \alpha<$><$>\alpha \simeq_{K_{A_i}} \beta<$><$>\alpha \preceq_{K_{A_i}} \beta<$><$>\beta \preceq_{K_{A_i}} \alpha<$><$>\preceq_{K_{A_i}}<$><$>{\cal L}<$><$>\preceq_{K_{A_i}}<$><$>K_{A_i}<$><!--$ (different belief bases may be associated with different orderings of plausibility).

Example 8Consider a set $)(--><$>{\Bbb A} = \{A_1, A_2, A_3\}<$><$>K_{A_2} = \{(\alpha, A_{1}), (\beta, A_{2}), (\gamma, A_{3})\}<$><$>A_{1} \lt^{A_2}_{Co} \ A_{2} \lt^{A_2}_{Co} \ A_{3}<$><$>K_{A_3} = \{(\alpha, A_{1}), (\beta, A_{3}), (\gamma, A_{2})\}<$><$>A_{1} \lt^{A_3}_{Co} \ A_{2} \lt^{A_3}_{Co} \ A_{3}<$><$>\alpha \prec_{K_{A_2}} \beta<$><$>\alpha \prec_{K_{A_3}} \beta<$><$>\gamma<$><$>\beta \prec_{K_{A_2}} \gamma<$><$>\gamma<$><$>\gamma \prec_{K_{A_3}} \beta<$><$>Sen(K_{A_2}) = Sen(K_{A_3})<$><$>K_{A_1} = K_{A_2}<$><$>A_{2} \lt^{A_1}_{Co} \ A_{1} \lt^{A_1}_{Co} \ A_{3}<$><$>\alpha \prec_{K_{A_2}} \beta<$><$>\beta \prec_{K_{A_1}} \alpha<$><!--$ .

The following example shows how the plausibility of a sentence can be calculated from a kernel set obtained from a compacted belief base.

Example 9Consider again Example 1, where the belief base of A ₁ is $)(--><$>K_{A_1} = \{(\beta, A_{1}), (\alpha, A_{2}), <$><$>(\alpha, A_{3}), (\alpha \rightarrow \beta, A_{4}), (\omega, A_{3}), (\omega\rightarrow\beta, A_{4}), (\alpha \rightarrow\delta, A_{1}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, A_{1}), (\gamma, A_{3}), (\gamma, A_{4}), (\gamma \rightarrow \epsilon,A_{2})\}<$><$>A_{1} \lt^{A_1}_{Co} \ A_{2} =^{A_1}_{Co} \ A_{3} \lt^{A_1}_{Co} \ A_{4}<$><!--$ . Then, suppose that agent A ₁ needs to calculate the plausibility of β. In order to do so, A ₁ will do the following steps.

• Step 1. Find the minimal subsets that derive β from the compacted belief base $)(--><$>K_{A_1}<$><$>K^{\uparrow}_{A_1} {^\kernels} \beta<$><!--$ ). From Example 6 we can see that:

$)(--><$>K^{\uparrow}_{A_1} {^\kernels} \beta = \{H_{a}, H_{b}, H_{d}, H_{g}\}<$><!--$ .

• Step 2. Apply ‘’ to each β-kernel $)(--><$>\in K^{\uparrow}_{A_1} {^\kernels} \beta<$><!--$ :

$)(--><$>min(H_{a}) = \{(\beta, A_{1})\}<$><$>min(H_{d}) = \{(\omega, A_{3})\}<$><!--$

$)(--><$>min(H_{b}) = \{(\alpha, A_{2})\}<$><$>min(H_{g}) = \{(\delta \rightarrow \beta, A_{1})\}<$><!--$

• Step 3. Apply ‘ ’ to the union of all the sets found in step 2.

$)(--><$>max(\{(\beta, A_{1}), (\alpha, A_{2}), (\omega, A_{3}), (\delta \rightarrow \beta, A_{1})\}) = \{(\alpha, A_{2}), (\omega, A_{3})\}<$><!--$ .

• Step 4. Find from the tuples of the previous item, the set containing the agent identifiers:

$)(--><$>{\Bbb A}(\{(\alpha, A_{2}), (\omega, A_{3})\}) = \{A_2, A_3\}<$><!--$ .

• Step 5. Find from the set of agent identifiers of the previous item, a single-agent identifier based on a given policy. For instance, if the policy is the lexicographical ordering among agent identifiers, then $)(--><$>{\cal S}_{A_1}(\{A_2, A_3\}) = A_2<$><!--$ .

Therefore, $)(--><$>Pl(\beta, K_{A_1}) = A_2<$><!--$ .

Proposition 3 shows that given a belief base $)(--><$>K_{A_i}<$><$>K_{A_i}<$><$>K^{\uparrow}_{A_i}<$><$>K_{A_i}<$><$>K^{\uparrow}_{A_i}<$><!--$ .

Proposition 3Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in Bel(K_{A_i})<$><$>K_{A_i}<$><$>K^{\uparrow}_{A_i}<$><!--$ . That is,

$)(--><$>Pl(\alpha, K_{A_i}) = {\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\uparrow \Vbar}_{A_i} \alpha} min(X)))) = {\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\Vbar}_{A_i} \alpha} min(X))))<$><!--$ .

Proof: See Appendix in Section 7.

Since the belief base of an agent may contain the same sentence in several different tuples, it could be natural to preserve only ‘the most plausible derivation’ of each sentence. However, in the following example it is shown that this criterion may be problematic.

Example 10Consider $)(--><$>{\Bbb A} = \{A_1, A_2, A_3\}<$><$>A_{3} \lt^{A_2}_{Co} \ A_{2} \lt^{A_2}_{Co} \ A_{1}<$><$>K_{A_2} = \{(\beta \rightarrow \alpha, A_2), <$><$>(\alpha, A_3)\}<$><$>(\beta, A_2)<$><$>K_{A_2}<$><$>Pl(\alpha, K_{A_2}) = A_2<$><$>K_{A_2}<$><!--$ in order to preserve just one derivation of α.

As we have shown in the previous example, it is very restrictive to have each sentence supported by only one derivation. For this reason, belief bases may be non-compacted. Thus, the plausibility of a sentence will be determined only by the plausibility function. Another reason for this decision is that we achieve a more dynamic framework since the evaluation of the credibility of the agent identifiers is separated by use of the assessment function.

It is important to note that the assessment function may change in time realizing dynamic assessments. Hence, the credibility order among agents can be changed without changing the knowledge base.

4 Change operators based on informants

In this section, we will define a change theory for MAS focusing on MSBR. The most widely studied model for BR is AGM model (Alchourrón et al., 1985) which distinguishes three change operators: expansions, contractions and revisions. The AGM model represents epistemic states by means of belief sets, that is, sets of sentences closed under logical consequence. Nevertheless, as introduced above, our epistemic model uses belief bases; that is, arbitrary sets of sentences. Next, in Section 4.1 we will define an expansion operator based on our epistemic model. Then in Section 4.2, we will introduce two contraction operators. In Section 4.3, we will define a prioritized revision operator and finally, in Section 4.4 we will propose a non-prioritized revision operator.

4.1 Expansion operator based on informants

In this subsection we will define an expansion operator for our epistemic model. This is the most simple operator to characterize from the logical point of view because it consists only in the addition of new information objects.

Definition 16 (Expansion using plausibility)Let $)(--><$>K_{A_i} \in {\cal K}<$><$>(\alpha, A_j)<$><!--$ an information object. The operator ‘+’, called expansion using plausibility, is defined as follows:

$--><$$>K_{A_i} + (\alpha, A_j) = K_{A_i} \cup \{(\alpha, A_j)\}<$$><!--$

In contrast to the expansion proposed in (Hansson, 1999), here we consider information objects instead of single sentences. Therefore, if $)(--><$>\alpha \in Bel(K_{A_i})<$><!--$ , then this operation could increase the plausibility of α. This operation, as Hansson’s expansion, does not guarantee a consistent epistemic state.

Let $)(--><$>K_{A_i}, K_{A_j} \in {\cal K}<$><$>A_k \in {\Bbb A}<$><!--$ . The expansion operator will be represented by ‘+’. We propose the following postulates for expansion using plausibility operator.

(EP-1) Success: $)(--><$>(\alpha, A_j) \in K_{A_i} + (\alpha, A_j)<$><!--$ .

The first postulate establishes that the expansion should be successful; that is, the result of expanding a belief base $)(--><$>K_{A_i}<$><$>(\alpha, A_j)<$><$>(\alpha,A_j)<$><!--$ .

(EP-2) Inclusion: $)(--><$>K_{A_i} \subseteq K_{A_i} + (\alpha, A_j)<$><!--$ .

Obtaining information is a very expensive process, thus avoiding the unnecessary loss of information is wished in any change operator. Since $)(--><$>K_{A_i} + (\alpha,A_j)<$><$>K_{A_i}<$><$>K_{A_i}<$><$>K_{A_i} + (\alpha,A_j)<$><!--$ .

(EP-3) Vacuity: If $)(--><$>(\alpha, A_j) \in K_{A_i}<$><$>K_{A_i} + (\alpha, A_j) = K_{A_i}<$><!--$ .

A particular case of expansion occurs when a belief base $)(--><$>K_{A_i}<$><$>(\alpha, A_j)<$><$>K_{A_i}<$><$>K_{A_i}<$><$>(\alpha, A_j)<$><$>K_{A_i}<$><!--$ .

(EP-4) Monotonicity: If $)(--><$>K_{A_j} \subseteq K_{A_i}<$><$>K_{A_j} + (\alpha, A_k) \subseteq K_{A_i} + (\alpha, A_k)<$><!--$ .

Suppose that there are two belief bases and one of these is contained in the other. If both belief bases are expanded by the same belief then the inclusion relation between them should be preserved.

(EP-5) Dynamic Plausibility: If $)(--><$>\alpha \in Bel(K_{A_i})<$><$>Pl(\alpha, K_{A_i}) \leq^{A_i}_{Co} Pl(\alpha ,K_{A_i} + (\alpha, A_j))<$><!--$ .

Suppose a belief base $)(--><$>K_{A_i}<$><$>(\alpha, A_j)<$><$>\alpha \in Bel(K_{A_i})<$><$>K_{A_i}<$><$>(\alpha, A_j)<$><!--$ should not decrease the plausibility of α. Thus, this operation could increase the plausibility of α.

The postulates EP-1 … EP-5 characterize axiomatically our expansion operator. For all belief base K and all information object $)(--><$>(\alpha,A_i), K + (\alpha,A_i)<$><!--$ is the smallest belief base which satisfies EP-1 … EP-5. Note that, EP-1 … EP-4 are defined in a similar way to those that define the expansion in AGM (Alchourron et al., 1985), whereas the new postulate EP-5 considers the case that our belief base contains a belief with different associated agents.

4.2 Contraction operator based on informants

The contraction is a change operation which withdraws beliefs without adding anything. In practice, this situation occurs when an agent believes in α and perceives that $)(--><$>\neg\alpha<$><$>\neg \alpha<$><$>\neg \alpha<$><!--$ . Below we introduce two contraction operators that are based on kernel contraction and adapted to our epistemic model.

4.2.1 Construction

In the belief base of an agent, several derivations for one sentence can exist. For instance, consider again the belief base $)(--><$>(K_{A_1})<$><$>K_{A_1}<$><!--$ that entail β are obtained.

Kernel contractions are based on a selection among the sentences that are relevant to derive the sentence to be retracted. In order to perform a contraction, kernel contractions use incision functions which cut into the minimal subsets that entail the information to be given up. We will adapt this notion to our epistemic model. An incision function only selects information objects that can be relevant for α and at least one element from each α-kernel.

Definition 17 (Incision function)An incision function $)(--><$>\sigma<$><$>K_{A_i} \in {\cal K}<$><!--$ is a function such that for all α:

1 $)(--><$>\sigma(K_{A_i}^\kernels\alpha) \subseteq \cup(K_{A_i}^\kernels\alpha)<$><!--$ , and
2 if $)(--><$>\emptyset \neq X \in K_{A_i}^\kernels\alpha<$><$>X \cap \sigma(K_{A_i}^\kernels\alpha) \neq \emptyset<$><!--$ .

In the definition of an incision function in Hansson’s work it is not specified how the function selects the sentences that will be discarded of each α-kernel. In our approach, this will be solved with the sentences plausibility that we have defined above. Thus, the incision function will select the least credible information objects of each α-kernel.

Definition 18 (Bottom incision function) $)(--><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>\sigma_{\downarrow}<$><$>\sigma_{\downarrow}(K_{A_i}^\kernels} \alpha) = \{(\delta, A_k): (\delta, A_k) \in X \in K_{A_i}^\kernels} \alpha<$><$>(\beta, A_j) \in X<$><$>\delta \preceq_{X} \beta\}<$><!--$ Footnote 2.

Example 11Consider a set $)(--><$>{\Bbb A} = \{A_1, A_2, A_3\}<$><$>A_{1} \lt ^{A_2}_{Co} \ A_{2} \lt^{A_2}_{Co} \ A_{3}<$><$>K_{A_2} = \{(\alpha, A_{3}),<$><$> (\beta, A_{2}), <$><$>(\beta\rightarrow\alpha, A_{1}), (\beta\rightarrow\alpha, A_{3}), (\omega, A_{1}),(\omega\rightarrow\alpha, A_{3}), (\delta, A_{1})\}<$><$>K_{A_2} ^\kernels} \alpha = \{H_a,H_b,H_c,H_d\}<$><!--$ where:

$--><$$>\matrix{H_a = \{(\alpha, A_{3})\}\hfill & H_c = \{(\beta, A_{2}),(\beta\rightarrow\alpha, A_{3})\} \cr H_b = \{(\beta, A_{2}),(\beta\rightarrow\alpha, A_{1})\} & H_d = \{(\omega, A_{1}), (\omega\rightarrow\alpha, A_{3})\}<$$><!--$

Then, the bottom incision function is:

$--><$$>\[ \sigma_\downarrow(K_{A_2} ^\kernels} \alpha)=\{(\alpha, A_{3}),(\beta\rightarrow\alpha, A_{1}),(\beta, A_{2}),(\omega, A_{1})\} \]<$$><!--$

Now that we have given the necessary background, two contraction operators will be defined. One of these operators (Definition 19) takes into consideration the whole belief base, and the other (Definition 20) considers its associated compacted belief base when an agent wants to apply the contraction operator.

Definition 19 (Contraction using plausibility)Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in {\cal L}<$><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>\ominus_{\sigma_{\downarrow}}<$><!--$ ’, called contraction using plausibility, is defined as follows:

$--><$$>K_{A_i}\ominus_{\sigma_{\downarrow}} \alpha = K_{A_i} \backslash \sigma_{\downarrow} (K_{A_i} ^\kernels}\alpha)<$$><!--$

Note that when an agent wishes to contract its belief base for a sentence, it applies the contraction operator over the sentence and not over an information object. Furthermore, note that, it makes sense to have a version of contraction where the object to be contracted is a determined tuple (and not a sentence); however, we consider that it is not nessesary for the aim of this article.

Example 12Consider the set $)(--><$>{\Bbb A} = \{A_1, A_2, A_3, A_4\}<$><$>A_{1} \lt^{A_1}_{Co} \ A_{2}=^{A_1}_{Co} \ A_{3}\lt^{A_1}_{Co} \ A_{4}<$><$>K_{A_1} = \{(\beta, A_{1}), <$><$>(\alpha, A_{2}), (\alpha, A_{3}), (\alpha \rightarrow \beta, A_{2}), <$><$>(\alpha \rightarrow \beta, A_{4}), (\omega, A_{1}), (\omega\rightarrow \beta, A_{4}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, <$><$>A_{1}), (\gamma, A_{3}), <$><$>(\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow \beta, A_{2}), (\epsilon \rightarrow \beta, A_{3}), (\epsilon \rightarrow \beta, A_{4})\}<$><$>\ominus_{\sigma_{\downarrow}}<$><!--$ ’.

• Step 1. Find the minimal subsets that derive β from $)(--><$>K_{A_1}<$><!--$ .

$)(--><$>K_{A_1} {^\kernels} \beta = \{H_{a}, H_{b}, H_{c}, H_{d}, H_{e}, H_{f}, H_{g}, H_{h}, H_{i}, H_{j}, H_{k}\}<$><!--$ where

$--><$$>\matrix{\ H_{a}= \{(\beta, A_{1})\} \hfill& H_{g}= \{(\alpha, A_{2}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta,A_{1})\} \cr H_{b}= \{(\alpha, A_{2}), (\alpha \rightarrow \beta, A_{2})\} & H_{h}= \{(\alpha, A_{3}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta,A_{1})\} \cr H_{c}= \{(\alpha, A_{3}), (\alpha \rightarrow \beta, A_{2})\} & H_{i}= \{(\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow\beta, A_{2})\} \cr H_{d}= \{(\alpha, A_{2}), (\alpha \rightarrow \beta, A_{4})\} & H_{j}= \{(\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow\beta, A_{3})\} \cr H_{e}= \{(\alpha, A_{3}), (\alpha \rightarrow \beta, A_{4})\} & H_{k}= \{(\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow\beta, A_{4})\} \cr \ H_{f}= \{(\omega, A_{1}), (\omega\rightarrow \beta, A_{4})\}<$$><!--$

• Step 2. Apply the bottom incision function ‘ $)(--><$>\sigma_{\downarrow}<$><$>K_{A_1} {^\kernels} \beta<$><!--$ to find the set containing the least credible information objects from each β-kernel.

$--><$$>\eqalign{ \sigma_{\downarrow}(K_{A_1} {^\kernels} \beta) = & \{(\beta, A_{1}), (\alpha, A_{2}), (\alpha\!\rightarrow\!\beta, A_{2}), (\alpha, A_{3}), (\omega, A_{1}) \} \cup \cr& \cup \{ (\delta\!\rightarrow\!\beta, A_{1}),(\gamma, A_{3}), (\gamma\!\rightarrow\!\epsilon, A_{2}), (\epsilon\!\rightarrow\!\beta, A_{2}), (\epsilon\!\rightarrow\!\beta, A_{3})\}<$$><!--$

• Step 3. $)(--><$>K_{A_1}\ominus_{\sigma_{\downarrow}} \beta = K_{A_1} \backslash \ \sigma_{\downarrow} (K_{A_1} {^\kernels}\beta)<$><!--$ .

$)(--><$>K_{A_1}\ominus_{\sigma_{\downarrow}}\beta = \{(\alpha \rightarrow \beta, A_{4}), (\omega\rightarrow \beta, A_{4}), (\alpha \rightarrow \delta, A_{2}), (\epsilon \rightarrow \beta, A_{4})\}<$><!--$ .

Note that, in Example 12 there are kernels that differ only in the associated agent identifier. This occurs when a base has the same sentence in several information objects. Since the incision function selects the least credible information objects of each α-kernel, then as more information object containing the same belief are in $)(--><$>K_{A_i}<$><!--$ , more information objects will be selected by the bottom incision function. As a consequence, in some cases, this operator withdraws several information objects. In contrast, if the agent considers a compacted belief base when it applies the contraction operator, there will be less information objects selected by the incision function.

Definition 20 (Optimal contraction using plausibility)Let $)(--><$>K_{A_i}\in{\cal K}<$><$>\alpha\in{\cal L}<$><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>-_{\sigma_{\downarrow}}<$><!--$ ’, called optimal contraction using plausibility, is defined as follows:

$--><$$> K_{A_i}-_{\sigma_{\downarrow}} \alpha = K_{A_i} - X<$$><!--$

where: $)(--><$>X = \{(\omega, A_{j}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha))\ {and } \ (\omega, A_j) \in K_{A_i}\}<$><!--$ .

Example 13Consider $)(--><$>K_{A_1}<$><$>\leq^{A_{1}}_{Co}<$><$>-_{\sigma_{\downarrow}}<$><!--$ ’.

• Step 1. Find the minimal subsets that derive β from a compacted belief base $)(--><$>K_{A_1}<$><!--$ .

$--><$$>\openup 3pt\eqalign{K^{\uparrow}_{A_1}= \{(\beta, A_{1}), (\alpha, A_{2}),(\alpha \rightarrow \beta, A_{4}), (\omega, A_{1}), (\omega\rightarrow \beta, A_{4}) \} \cup \cr & \cup \{ (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, A_{1}), (\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow \beta, A_{4})\}<$$><!--$

Note that, the policy used by the selection function (Definition 9), when we apply the compact belief base function (Definition 10), is based on a lexicographical ordering among agent identifiers.

$)(--><$>K^{\uparrow}_{A_1} {^\kernels} \beta = \{H_{a}, H_{d}, H_{f}, H_{g}, H_{k}\}<$><!--$ where

$--><$$>\openup 3pt\matrix{\ \,H_{a}= \{(\beta, A_{1})\}\hfill & \ H_{g}= \{(\alpha, A_{2}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, A_{1})\} \cr H_{d}= \{(\alpha, A_{2}), (\alpha \rightarrow \beta, A_{4})\} & H_{k}= \{(\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow \beta, A_{4})\} \cr \ H_{f}= \{(\omega, A_{1}), (\omega\rightarrow \beta, A_{4})\}<$$><!--$

• Step 2. Apply the bottom incision function ‘ $)(--><$>\sigma_{\downarrow}<$><$>K_{A_1} ^\kernels} \beta<$><!--$ .

$)(--><$>\sigma_{\downarrow}(K_{A_1} ^\kernels} \beta) = \{(\beta, A_{1}), (\alpha, A_{2}), (\omega, A_{1}), (\delta \rightarrow \beta, A_{1}),(\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2})\}<$><!--$ .

• Step 3. $)(--><$>K_{A_1}-\,_{\sigma_{\downarrow}}\beta = \{(\alpha \rightarrow \beta, A_{2}), (\alpha \rightarrow \beta, A_{4}), <$><$>(\omega \rightarrow \beta, A_{4}), (\alpha \rightarrow \delta, A_{2}), (\epsilon \rightarrow \beta, A_{2}), (\epsilon \rightarrow \beta, A_{3}), <$><$>(\epsilon \rightarrow \beta, A_{4})\}<$><!--$ .

Note that, since the belief base may be non-compacted, in step 3 of Example 13, all those tuples whose beliefs were selected by the bottom incision function without regarding the respective associated agents are discarded from $)(--><$>K_{A_1}<$><!--$ . Besides, observe that in the last two examples the contracted belief bases have the same beliefs (see Proposition 4). However, in the latest example, the belief base contains more information objects than in the previous one (see Proposition 5). Then, this operator does not lose the associated agents of the belief remaining after the contraction. Consequently, this type of contraction is more conservative.

Proposition 4Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in {\cal L}<$><$>\ominus_{\sigma_{\downarrow}}<$><$>-_{\sigma_{\downarrow}}<$><!--$ ’ an optimal contraction using plausibility operator, then

$--><$$>Sen(K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha) = Sen(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$$><!--$

Proof: See Appendix in Section 7.

Proposition 5Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in {\cal L}<$><$>\ominus_{\sigma_{\downarrow}}<$><$>-_{\sigma_{\downarrow}}<$><!--$ ’ an optimal contraction using plausibility operator, then

$--><$$>K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha \subseteq K_{A_i} -_{\sigma_{\downarrow}} \alpha<$$><!--$

Proof: See Appendix in Section 7.

4.2.2 Properties

Next we will give the rationality postulates for optimal contraction using plausibility operator, adapting some of the postulates given in (Hansson, 1999), considering the following principle.

Minimal change. As much old knowledge as possible should be retained in the revised/ contracted knowledge. That is, we should give up beliefs only when forced to do so, and then we should discard as few of them as possible.

Let A _i, A _j, $)(--><$>A_k, A_p \in {\Bbb A}<$><$>K_{A_i} \in {\cal K}<$><!--$ be a belief base. The contraction operator will be represented by ‘−’. We propose the following postulates for contraction.

(CP-1) Success: if $)(--><$>\alpha \not\in Cn(\emptyset)<$><$>\alpha \not\in Bel(K_{A_i} - \alpha)<$><!--$ .

The first postulate establishes that the contraction should be successful; that is, the result of contracting a belief base $)(--><$>K_{A_i}<$><!--$ by a sentence α (that is not a tautology) should be a new belief base that does not imply α.

(CP-2) Inclusion: $)(--><$>K_{A_i} - \alpha \subseteq K_{A_i}<$><!--$ .

Since $)(--><$>K_{A_i} - \alpha<$><$>K_{A_i}<$><$>K_{A_i} - \alpha<$><$>K_{A_i}<$><!--$ .

(CP-3) Uniformity: If for all $)(--><$>K′ \subseteq K_{A_i}<$><$>\alpha \in Bel(K′)<$><$>\beta \in Bel(K′)<$><$>K_{A_i} - \alpha = K_{A_i} - \beta<$><!--$ .

This property establishes that if two sentences α and β are implied by exactly the same subsets of $)(--><$>K_{A_i}<$><$>K_{A_i}<$><$>K_{A_i}<$><!--$ by β.

Next, we propose a new postulate which is an adapted version of the postulate of core-retainment defined in (Hansson, 1994): ‘The beliefs that we give up in order to contract $)(--><$>K_{A_i}<$><$>K_{A_i}<$><$>K_{A_i} - \alpha<$><$>K_{A_i} - \alpha<$><$>K_{A_i}<$><$>K_{A_i}<$><!--$ can be removed, such that the removal of β is the crucial step by which α stops to be logically implied.’ In our contraction operator, this order is based on the credibility order among agents.

(CP-4) Minimal Plausibility Change: If $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} - \alpha<$><$>K′ \subseteq K_{A_i}<$><$>\alpha \not\in Bel(K′)<$><$>(\beta, A_j) \in K_{A_i}<$><!--$ such that:

• $)(--><$>\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><!--$ ,
• or $)(--><$>A_p \leq^{A_i}_{Co} A_j<$><!--$ , and
• for all $)(--><$>(\delta,A_k) \in K′<$><$>\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) \backslash \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

The intuition behind (CP-4) is that, if β is removed, $)(--><$>\delta<$><$>\delta<$><$>K_{A_i}<$><$>K_{A_i}<$><!--$ all the information objects containing β.

Theorem 1Let $)(--><$>K_{A_i} \in {\cal K}<$><$>-_{\sigma_{\downarrow}}<$><$>-_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ if and only if it satisfies CP-1,…, CP-4, that is, it satisfies success, inclusion, uniformity and minimal plausibility change.

Proof: See Appendix in Section 7.

Note that, from CP-4 it is straightforwardly possible verify the following remark.

Remark 1The optimal contraction using plausibility operator follows the principle of minimal change.

4.3 Prioritized revision using plausibility

In many multi-agent domains and applications, each agent has usually its own initial beliefs as well as knowledge acquired from other agents. In this Section and in Section 4.4, we develop two different ways in which the belief base of an agent can be rationally modified when the agent receives information from other agents that can have different degree of credibility. In the literature, there are several studied prioritized methods (e.g. partial meet revision (Alchourrón et al., 1985) and kernel revision (Hansson, 1999)). In these methods, the new information has priority over the beliefs in the base of the receiver agent. Our approach is based on kernel revision and the epistemic model defined above. Thus, we focus on MSBR, where agents maintain the consistency of their belief bases.

4.3.1 Construction

The revision operator is the most complex change operator. This type of change guarantees a consistent epistemic state. When a belief base $)(--><$>K_{A_i} \in {\cal K}<$><$>(\alpha,A_j)<$><!--$ we will have two tasks:

• to maintain the consistency of $)(--><$>K_{A_i}<$><$>Bel(K_{A_i})<$><$>\neg\alpha \in Bel(K_{A_i})<$><$>K_{A_i}<$><!--$ .
• to add $)(--><$>(\alpha, A_j)<$><$>K_{A_i}<$><$>\alpha \in Bel(K_{A_i})<$><!--$ then this operation could increase the plausibility of α.

The first task can be accomplished contracting by $)(--><$>\neg\alpha<$><$>(\alpha, A_j)<$><$>\neg\alpha<$><$>(\alpha, A_j)<$><$>\neg\alpha<$><$>(\alpha,A_j)<$><!--$ .

Definition 21 (Prioritized revision using plausibility)Let $)(--><$>K_{A_i} \in {\cal K}<$><$>(\alpha, A_j)<$><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>-_{\sigma_{\downarrow}}<$><$>*_{\sigma_{\downarrow}}<$><!--$ ’, called prioritized revision using plausibility, is defined as follows:

$--><$$> K_{A_i}*_{\sigma_{\downarrow}} (\alpha, A_j) = (K_{A_i} -_{\sigma_{\downarrow}} \neg\alpha) + (\alpha, A_j)<$$><!--$

Example 14Consider the set $)(--><$>{\Bbb A} = \{A_1, A_2, A_3, A_4, A_5\}<$><$>A_{1} \lt^{A_1}_{Co} A_{2}=^{A_1}_{Co} A_{3}\lt^{A_1}_{Co} A_{4}\lt^{A_1}_{Co} A_{5}<$><$>K_{A_1} = \{(\beta, A_{1}), (\alpha, A_{2}), (\alpha, A_{3}), (\alpha \rightarrow \beta, A_{2}), (\alpha \rightarrow \beta, A_{4}), (\omega, A_{1}), (\omega\rightarrow \beta, A_{4}), (\alpha \rightarrow \delta, A_{2}), (\delta \rightarrow \beta, A_{1}), <$><$>(\gamma, A_{3}), (\gamma \rightarrow \epsilon, A_{2}), (\epsilon \rightarrow \beta, A_{2}), (\epsilon \rightarrow \beta, A_{3}), (\epsilon \rightarrow \beta, A_{4})\}<$><$>(\neg \beta, A_{5})<$><$>*_{\sigma_{\downarrow}}<$><$>\beta \in Bel(K_{A_1})<$><$>K_{A_1}<$><$>K_{A_1}<$><$>(\neg \beta, A_{5})<$><$>K_{A_1} *_{\sigma_{\downarrow}} (\neg \beta, A_5) = \{(\alpha \rightarrow \beta, A_{2}), (\alpha \rightarrow \beta, A_{4}), (\omega \rightarrow \beta, A_{4}), (\alpha \rightarrow \delta, A_{2}),<$><$>(\epsilon \rightarrow \beta, A_{2}), (\epsilon \rightarrow \beta, A_{3}), (\epsilon \rightarrow \beta, A_{4})\} \cup \{(\neg \beta, A_5)\}<$><!--$ .

4.3.2 Properties

Next we will give the rationality postulates for prioritized revision using plausibility operator. We must introduce the following principle, similar to the principle proposed in (Dalal, 1988).

Maintenance of consistency. If a belief base K and a belief α are both consistent, then K revised by α is consistent.

Let A _i, A _j, A _k, A _p, $)(--><$>A_q \in {\Bbb A}<$><$>K_{A_i} \in {\cal K}<$><!--$ be a belief base. The prioritized revision operator will be represented by ‘’.

(RP-1) Success: $)(--><$>(\alpha, A_j) \in K_{A_i} * (\alpha, A_j)<$><!--$ .

Since the revision operator defined here is considered prioritized; that is, the new information has priority, the first postulate we give establishes that the revision should be successful. That is, the result of revising a belief base $)(--><$>K_{A_i}<$><$>(\alpha,A_j)<$><$>(\alpha,A_j)<$><!--$ .

(RP-2) Inclusion: $)(--><$>K_{A_i} * (\alpha, A_j) \subseteq K_{A_i} \cup \{(\alpha, A_j)\}<$><!--$ .

A particular case in the revision process occurs when a belief base $)(--><$>K_{A_i}<$><$>(\alpha,A_j)<$><$>\neg \alpha \in Bel(K_{A_i})<$><$>(\alpha,A_j)<$><$>\neg\alpha<$><$>K_{A_i}<$><$>\neg\alpha \in Bel(K_{A_i})<$><$>K_{A_i}<$><$>(\alpha,A_j)<$><$>K_{A_i}<$><$>(\alpha,A_j)<$><$>\alpha \in Bel(K_{A_i})<$><$>K_{A_i}<$><!--$ ) then the revision operation is equivalent to an expansion operation.

(RP-3) Consistency: if α is consistent then $)(--><$>K_{A_i} * (\alpha, A_j)<$><!--$ is consistent.

The main aim of the revision operator is to hold consistency in the belief base revised. However, there exist special cases in which this is not possible. If a belief base is revised by an information object containing a contradictory sentence, then the resultant belief base is inconsistent. Hence, the revision operator should preserve the consistency in the belief base if and only if an information object containing a contradictory sentence is not being added to the belief base.

(RP-4) Uniformity: If for all $)(--><$>K′ \subseteq K_{A_i}<$><$>\{\alpha\} \cup Sen(K′) \vdash \perp<$><$>\{\beta\} \cup Sen(K′) \vdash \perp<$><$>K_{A_i} \cap (K_{A_i} * (\alpha, A_j)) = K_{A_i} \cap (K_{A_i} * (\beta, A_k))<$><!--$ .

This postulate determines that if two beliefs α and β are inconsistent with the same sub-bases of $)(--><$>K_{A_i}<$><$>K_{A_i}<$><$>K_{A_i}<$><!--$ .

(RP-5) Minimal Plausibility Change: If $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} * (\alpha, A_k)<$><$>K′ \subseteq K_{A_i}<$><$>\neg\alpha \not\in Bel(K′)<$><$>(\beta, A_j) \in K_{A_i}<$><!--$ such that:

• $)(--><$>\neg\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><!--$ ,
• or $)(--><$>A_p \leq^{A_i}_{Co} A_j<$><!--$ , and
• for all $)(--><$>(\delta,A_q) \in K′<$><$>\neg\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) \backslash \{(\delta,A_q)\})<$><$>A_j \leq^{A_i}_{Co} A_q<$><!--$ .

The intuition behind this postulate is similar to that of the minimal plausibility change postulate (CP-4) for contractions introduced above.

Theorem 2Let $)(--><$>K_{A_i} \in {\cal K}<$><$>*_{\sigma_{\downarrow}}<$><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ if and only if it satisfies RP-1, …, RP-5, that is, it satisfies success, inclusion, consistency, uniformity and minimal plausibility change.

Proof: See Appendix in Section 7.

Note that, from RP-3 and RP-5, it is straightforwardly possible verify the following remark.

Remark 2The prioritized revision using plausibility operator follows the principles of minimal change and maintenance of consistency.

Proposition 6If ‘+’ satisfies EP-1,…,EP-5 and ‘ $)(--><$>-_{\sigma_{\downarrow}}<$><$>*_{\sigma_{\downarrow}}<$><!--$ ’ satisfies RP-1,…,RP-5.

Proof: See Appendix in Section 7.

4.4 Non prioritized revision using plausibility

A prioritized revision operator is characterized by success postulate from which we may infer that $)(--><$>\alpha \in Bel(K_{A_i} * (\alpha, A_j))<$><!--$ . That is, the incoming information has priority over the beliefs in the base of the receiver agent. However, as is mentioned in Fermé and Hansson (1999), this is an unrealistic feature, since actual epistemic agents, when confronted with information that contradicts previous beliefs, often reject it. Several models of BR have been developed that allow for two options: either the new information is completely accepted or it is completely rejected (Hansson, 1997; Makinson, 1997). Below, a non-prioritized revision operator for our proposed epistemic model is introduced.

When an agent always acquires information from the same source, then a prioritized method can be used. Nevertheless, if information comes from different sources, and this sources are not equally credible, a non-prioritized method can be more adequate. This occurs in many multi-agent domains and applications. Thus, we focus on a non-prioritized BR operator that is based on the credibility ordering among agents. We propose a method for analyzing the information received; if inconsistency arises, the credibility order is used to decide which information prevails. Thus, we show that, with this new revision operator, incoming information cannot be accepted when the receiver agent has more credible beliefs that contradict the new information.

4.4.1 Construction

When a belief base $)(--><$>K \in {\cal K}<$><$>I = (\alpha,A_i)<$><!--$ using a non-prioritized revision operator there are two cases:

• α is consistent with . In this case, the operator is equivalent to the prioritized version.
• α is inconsistent with , that is $)(--><$>\neg\alpha \in Bel(K)<$><!--$ . First, it is necessary to determine whether the sentence will be accepted; and then if the input is accepted, then the operator is equivalent to the prioritized version.

According to this, two options arise: completely accept all the input, or completely reject all the input. In the literature there are other operators which may partially accept the new information, for instance, Revision by a Set of Sentences defined on belief bases (Falappa et al., 2002) and Selective Revision defined on belief sets (Farmé and Hansson, 1999).

Definition 22 (Non-prioritized revision using plausibility)Let $)(--><$>K_{A_i}\!<$><$>{\cal K}<$><$>(\alpha, A_j)<$><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>*_{\sigma_{\downarrow}}<$><$>\circ_{\sigma_{\downarrow}}<$><!--$ ’, called non-prioritized revision using plausibility, is defined as follows:

$--><$$>K_{A_i}\circ_{\sigma_{\downarrow}}(\alpha, A_j) = \left\{ \matrix{ K_{A_i} + (\alpha, A_j) &\ {if } \ \neg \alpha \not\in Bel(K_{A_i}) \hfill\cr K_{A_i} \hfill& {if } \ \neg \alpha \in Bel(K_{A_i}) \ and \ A_j \lt^{A_i}_{Co} \ Pl(\neg \alpha, K_{A_i}) \cr K_{A_i} *_{\sigma_{\downarrow}} (\alpha,A_j) & if \ \neg \alpha \in Bel(K_{A_i}) \ and \ Pl(\neg \alpha, K_{A_i}) \leq^{A_i}_{Co} A_j \right<$$><!--$

Note that, if the incoming information is as credible as the beliefs which are possibly withdrawn, this operator prioritizes the input. That is, if an agent receives information from the same informant, it is natural that the more recent information will be accepted.

Example 15Consider $)(--><$>K_{A_1}<$><$>\leq^{A_{1}}_{Co}<$><$>\neg\beta, A_{5}<$><$>\circ_{\sigma_{\downarrow}}<$><$>Pl(\beta, K_{A_1}) = A_2 \lt^{A_1}_{Co} \ A_5<$><$>K_{A_1} \circ_{\sigma_{\downarrow}} (\neg \beta, A_5) = K_{A_1} *_{\sigma_{\downarrow}} (\neg \beta, A_5) = \{(\alpha \rightarrow \beta, A_{2}), <$><$>(\alpha \rightarrow \beta, A_{4}), (\omega \rightarrow \beta, A_{4}), (\alpha \rightarrow \delta, A_{2}),(\epsilon \rightarrow \beta, A_{2}), (\epsilon \rightarrow \beta, A_{3}), (\epsilon \rightarrow \beta, A_{4})\} \cup \{(\neg \beta, A_5)\}<$><!--$ .

It is important to note that if the input of Example 14 is $)(--><$>(\neg\beta, A_1)<$><$>(\neg\beta, A_5)<$><$>A_1 \lt^{A_1}_{Co} \ A_2<$><!--$ . Thus, this operator will never discard more plausible sentences than the input.

4.4.2 Properties: success postulate must be weakened

An operator defined following the Definition 22, in general, satisfies the same postulates that satisfies the prioritized version. However, we must introduce the following principle.

Non-prioritization principle. If a belief base is revised by an information object $)(--><$>(\alpha, A_j)<$><!--$ , then α will not be necessarily accepted in the revised belief base. A sentence α will be accepted in the revised belief base only when its informant A _j is sufficiently plausible or credible.

Let A _i, A _j and $)(--><$>A_k \in {\Bbb A}<$><$>K_{A_i} \in {\cal K}<$><$>K_{A_i}<$><$>\circ<$><$>\circ<$><!--$ ’ does not satisfies success and, therefore, we need weaker versions of this postulate.

(NRP-1) Weak Success: if $)(--><$>\neg \alpha \not \in Bel(K)<$><$>(\alpha, A_j) \in K_{A_i} \circ (\alpha, A_j)<$><!--$ .

This postulate establishes that α is accepted in the revised belief base if $)(--><$>\neg\alpha<$><!--$ is not derived in the original belief base.

(NRP-2) Relative Success: $)(--><$>K_{A_i} \circ (\alpha, A_j) = K_{A_i}<$><$>(\alpha, A_j) \in K_{A_i} \circ (\alpha, A_j)<$><!--$ .

This postulate, inspired in (Hansson et al., 2001), says that all or nothing is accepted. That is, α is accepted in the revised belief base or nothing changes.

Both weak success and relative success do not capture the intuitions behind the non-prioritization principle. Therefore, we propose the following postulate, called Conditional Success.

(NRP-3) Conditional Success: If $)(--><$>(\beta, A_k) \in K^{\uparrow}_{A_i}<$><$>\beta \not\in Sen(K_{A_i} * (\alpha, A_j))<$><$>(\alpha, A_j) \in K_{A_i} \circ (\alpha, A_j)<$><$>A_k \leq^{A_i}_{Co} A_j<$><!--$ .

This postulate establishes that α is accepted in the revised belief base when its informant is sufficiently plausible.

Following Definition 22 it is possible to show that let $)(--><$>K_{A_i} \in {\cal K}<$><$>\circ_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ if and only if it satisfies uniformity, consistency, conditional success, inclusion and minimal plausibility change. Hence, we can straightforwardly note that the non-prioritized revision using plausibility operator follows the principles of minimal change, maintenance of consistency and non-prioritization.

4.5 Application example

Consider the following scenario. An agent A ₁ wants to travel to a village in a mountain and knows from the Tourist Information Office (A _t) that if it rains ( $)(--><$>\rho<$><$>\neg o <$><$>K_{A_1} =\{(\rho \rightarrow \neg o, A_t)\}<$><$>A_1 \lt^{A_1}_{Co} A_r \lt^{A_1}_{Co} A_g \lt^{A_1}_{Co} A_t \lt^{A_1}_{Co} A_w \lt^{A_1}_{Co} A_c<$><$>\circ_{\sigma_\downarrow}<$><!--$ introduced above to revise its beliefs.

Then, the agent A ₁ obtains from A _g the information object $)(--><$>I_1=(\rho, A_g)<$><$>K_{A_1}\circ_{\sigma_\downarrow}(\rho, A_g) =\{(\rho \rightarrow \neg o, A_t), (\rho, A_g)\}<$><$>\neg o \in Bel(K_{A_1})<$><$>I_2=(\neg \rho, A_r)<$><$>\rho \in Bel(K_{A_1})<$><$>A_r \lt^{A_1}_{Co}\, Pl(\rho, K_{A_1}) = A_g<$><$>I_3=(\rho, A_w)<$><$>K_{A_1}<$><$>K_{A_1}<$><$>K_{A_1}\circ_{\sigma_\downarrow}(\rho, A_w) =<$><$>\{(\rho \rightarrow \neg o, A_t), (\rho, A_g), (\rho, A_w)\}<$><$>\rho<$><$>\neg o<$><!--$ are both increased.

Finally, A ₁ obtains )(--><$>I_4=(o, A_c)<$><$>\neg o \in Bel(K_{A_1})<$><$>\neg o<$><$>K^{\uparrow}_{A_1} {^\kernels}\neg o = \{\{(\rho \rightarrow \neg o, A_t), (\rho, A_w)\}\}<$><$>(\rho \rightarrow \neg o, A_t)<$><$>K_{A_1}\circ_{\sigma_\downarrow}(o, A_c) =\{(o, A_c), (\rho, A_g), (\rho, A_w)\}<$><$>o \in Bel(K_{A_1})<$><$>\neg o<$><$>K_{A_1}<$><$>(\rho \rightarrow \neg o)<$><!--$ . Then I ₄ is added to the agent belief base in a consistent way. Thus, A ₁ finally believes that the road is open. Note that the sentences selected by the incision function in the revision are less credible than o.

5 Forwarding Information

In the previous sections we have introduced a formalism for MSBR. Using that formalism, agents can acquire information objects from multiple sources and incorporate them into their proper beliefs. Both prioritized and non-prioritized revision operators were introduced using the credibility order of each agent in order to decide which information prevails. Nevertheless, nothing was said about how an agent can forward information that is obtained from others. In the following, we assume that all agents use the epistemic model introduced above, have their own credibility order, and incorporate information objects through some of the revision operators defined above.

Although the contribution of this paper is focused on the formalism presented above, in this section we briefly comment different strategies for forwarding information to other agents. In particular, we study how to rationally choose meta-information to be sent as a label in the information objects. The choice of the agent identifier to be sent with the piece of information is crucial as it influences the decision of the receiver about whether to accept the transmitted information. Thus, it is in the interest of the sending agent, and in fact in the interest of the whole coalition of agents, to choose this meta-information carefully.

As stated above, when an agent sends information to another agent, it sends information objects. Consider the set of agent identifiers $)(--><$>{\Bbb A} = \{A_1, A_2, A_3,A_4\}<$><$>A_{1} \lt^{A_1}_{Co} \, A_{2} =^{A_1}_{Co} \, A_{3} \lt^{A_1}_{Co} \, A_{4}<$><$>K_{A_1} = \{(\alpha, A_{2}), (\alpha, A_{4}), (\beta, A_{3}), (\beta \rightarrow \alpha, A_{1})\}<$><$>\alpha,Agent<$><!--$ ), and it is clear that there are several choices for the identifier ‘’ of I.

In Krümpelmann et al. (2009), we describe different criteria for forwarding information that determine which agent identifier is considered by the receiver at the moment of reasoning. That is to say, we analyze different alternatives which determine which agent identifier is sent in the information object. Some of those are: ‘Sender identifier criterion’ which, as in Dragoni et al. (1994), suggests sending the proper sender (A ₁) in the information object; ‘Source identifier criterion’ that proposes sending one of the identifiers stored with α in the sender’s base (e.g. A ₂, A ₄) that can be one of them arbitrarily or the more credible of them as is suggested by the ‘Combined criterion’. In Krümpelmann et al. (2009) is shown that there are some examples in which these simple criteria can select an unappropriated identifier.

In this section, we show a more elaborated criterion that takes the plausibility of sentences obtained from agents credibility into consideration. This criterion calculates the plausibility of a sentence α based on all its proofs before being forwarded. This calculation should return an agent identifier which will be used as the agent identifier of α. Thus, a forwarding criterion can be implemented by sending an information object $)(--><$>I = (\alpha, A_i)<$><$>Pl(\alpha, K_{A_1})<$><$>\rho<$><$>(\rho,A_w)<$><!--$ .

Example 16Let us consider Example 9 again. If the agent A ₁ wishes to send β to agent A ₄ then, according to the plausibility based criterion, A ₁ will send the information object $)(--><$>(\beta, Pl(\beta, K_{A_1}))<$><$>K_{A_1}<$><$>\leq^{A_1}_{co}<$><$>(\beta, A_2)<$><!--$ to A ₄.

An important decision we made is to forward an agent identifier with a sentence rather than a credibility label in order to give additional information to the beliefs. One reason for this decision is that we achieve a more dynamic framework since the evaluation of the credibility of the agent identifiers is separated by use of the assessment function. Note that the assessment function may change in time realizing dynamic assessments. Hence, the credibility order among agents can be changed without changing the knowledge base or the operator. That is, if the credibility order among agents changes, then the plausibility of all sentences will also change without having to modify the belief base of the agent. Another reason for this decision is that since each agent has its own assessment (as stated in Section 2), it is more suitable to send agent identifiers and then the receiver agent can evaluate the received belief based on the credibility it has according to its own assessment. This means that the sending agent expresses that it considers the information it transmits as credible as it considers the agent identifier in the information object. Now it is up to the receiver to assess how credible it considers each agent from its perspective using its own assessment function. We believe that this represents an advanced way of communication in MAS.

5 Conclusions and Related Works

In this work, we have proposed a general framework to deal with the knowledge dynamics of a MAS. We have introduced an epistemic model and a set of operators to change the belief base of each agent: expansion, contraction, prioritized revision and non-prioritized revision. We have defined a set of postulates for every operator, we have proved representation theorems for the more important changes (contractions and revisions), and we have shown some interesting principles for each of them. We have shown how these operators can be used for MSBR system weighing beliefs following a credibility order among agents, giving illustrative examples, and showing that these operators may improve the collective reasoning of a MAS.

In the literature, different formalisms have been presented to deal with MABR (Malheiro et al., 1994; Kfir-Dahav and Tennenholz, 1996; Liu and Williams, 1999, 2001) where the overall BR of agent teams is investigated. In contrast to these, we focused on MSBR which is one of the essential components of MABR. Here, the agents maintain the consistency of their belief bases. Two other approaches that cope with MSBR are Dragoni et al. (1994) and Cantwell (1998). The epistemic model in these works is similar to the one we defined in Section 2; however, our theory change is different to theirs. That is, like us, both consider that the reliability of the source affects the credibility of incoming information, and this reliability is used for making decisions. Nevertheless, these two approaches differ from ours in several issues as is detailed below.

In Dragoni et al. (1994, 1997), it is considered that agents detect and store in tables the nogoods, which are the minimally inconsistent subsets of their knowledge bases. A good is a subset of the knowledge base such that: it is not inconsistent (it is not a superset of a nogood), and if augmented with whatever else assumption in knowledge base, it becomes inconsistent. In contrast to our approach, they do not remove beliefs to avoid a contradiction, but quite more generally, they choose which is the new preferred good among them in knowledge base. In our model, we obtain the kernel sets to cut some sentences, thus we break the contradictions if it is necessary.

Like us, they propose to store additional information with each sentence. However, their tuples contain five elements: <Identifier, Sentence, Origin Set (OS), Source, Credibility>, where OS records the assumption nodes upon which it really ultimately depends (as derived by the theorem prover). In contrast to them, in our model a tuple only store a sentence and an associated agent, but a tuple does not store the credibility. That is, in our model, the plausibility of a sentence is not explicitly stored with it, as it is in Dragoni et al. (1994). Thus, when the plausibility of some sentence is needed, the plausibility function should be applied. As is shown in Example 17, given a sentence α, its plausibility depends on its proofs (α-). Therefore, if one of the sentences of these proof changes, then the plausibility of α may change. Hence, if the credibility order is replaced, then the sentence plausibility may change without changing the belief base.

Example 17Consider a set $)(--><$>{\Bbb A} = \{A_1, A_2\}<$><$>A_{1} \leq^{A_1}_{Co} A_{2}, K_{A_1} = \{(\alpha, A_{1}), <$><$>(\alpha \rightarrow \beta, A_{2})\}<$><$>K_{A_2} = \{(\alpha, A_{2})\}<$><$>Pl(\beta, K_{A_1}) = A_1<$><$>K_{A_1} = \{(\alpha, A_{1}), (\alpha, A_{2}), (\alpha \rightarrow \beta, A_{2})\}<$><$>Pl(\beta, K_{A_1}) = A_2<$><!--$ . Observe that plausibility of β is increased.

The communication policy in Dragoni et al. (1994) is that agents do not communicate the sources of the assumptions, but they present themselves as completely responsible for the knowledge they are passing on; receiving agents consider the sending ones as the sources of all the assumptions they are receiving from them. In Section 5, we showed a more elaborated criterion which proposes to calculate the plausibility of a sentence based on all its proofs before being forwarded. An important decision we made was to forward an agent identifier with a sentence rather than a credibility label in order to give additional information to the beliefs. One reason for this decision is that since each agent has its own assessment, it is more suitable to send agent identifiers so in this way, the receiver agent can evaluate the belief received based on the credibility it has according to its own assessment. Another reason is that we achieve a more dynamic framework since the evaluation of the credibility of the agent identifiers is separated by use of the assessment function.

In Cantwell (1998), a scenario (set of incoming information) presented by a source is treated as a whole and not sentence by sentence, and therefore, it can be inconsistent. A relation of trustworthiness is introduced over sets of sources and not between single sources. Besides, if two sources give the same piece of information α, and a single agent gives $)(--><$>\neg \alpha<$><$>\neg \alpha<$><$>\neg \alpha<$><!--$ will be rejected.

Our work has some link with the idea of epistemic entrenchment (Gärdenfors and Makinson,1988; Rott, 1992). Here the sentence plausibility is used in a similar way to epistemic entrenchment to modify knowledge. However, there are some differences between them. For instance, in our work the order among sentences is based on the informants, whereas in Gärdenfors and Makinson (1988) the order among sentences is implicitly defined over belief states represented by belief sets.

When we count on a MAS that has only one agent, the new operator is very drastic. In this scenario there is no order among agents. The same happens when all the agents of a MAS have equal credibility. In these cases the bottom incision function does not have enough information to select sentences and it will erase all sentences in the α-kernels. This behavior is similar to full meet revision on belief bases (Hansson, 1999). Nevertheless, when a MAS has several agents with different credibility and it is necessary to represent knowledge dynamics of the agents, plausibility seems to be a good criteria.

In Benferhat et al. (1993), several methods to deal with inconsistency are investigated by defining notions of consequence capable of inferring non-trivial conclusions from an inconsistent knowledge base. It is clear that the methods proposed here and in Benferhat et al. (1993) follow different attitudes when facing inconsistent knowledge. In (Benferhat et al., 1993) inconsistency-tolerant consequence relations in layered knowledge bases are proposed, whereas here a revision operator is defined.

It is important to note that the revision operator proposed here is similar to the revision operator proposed in Benferhat et al. (2002). However, these operators are built in a different way. In Benferhat et al. (2002), the epistemic state is represented by a possibility distribution which is a mapping from the set of classical interpretations or worlds to the [0,1] interval. This distribution represents the degree of compatibility of the interpretations with the available information and the revision is done over the possibility distribution. This revision modifies the ranking of interpretations so as to give priority to the input information. The input must be incorporated in the epistemic state; in other words, it takes priority over information in the epistemic state. They discuss the revision with respect to uncertain information; the input is of the form $)(--><$>(\phi, a)<$><$>\phi<$><!--$ should be believed to a degree of certainty of exactly a.

Both approaches differ in some interesting ways. A first difference occurs in the way they handle the epistemic state. In Benferhat et al. (2002), the authors use belief sets, whereas we use belief bases. The use of belief bases makes the representation of the agent’s cognitive state more natural and computationally tractable. That is, following Hansson (1999, page 24), we consider that agents’ beliefs could be represented by a limited number of sentences that correspond to the explicit beliefs of the agent. Another important difference, related to the intention of using the operator in a MAS environment, is the additional information added to each belief. Here, to decide whether to reject or accept a new belief, a comparison criterion among beliefs is defined. This criterion (called plausibility) is based on the credibility order among agents. We have assumed that this order is fixed; however, this order can be changed without affecting the definition of the operator. This characteristic is one of the motivations for using agent identifiers instead of representing the plausibility of a sentence as in Benferhat et al. (2002). Moreover, here a total order among agents is necessary, but this assumption can be relaxed considering a partial order among agents.

As future work, we will try to extend the applications of the proposed framework in environments in which the credibility of agents changes, and therefore, the plausibility of beliefs (and the results of changes) can be dynamically modified. That is, since the revision process is based on the credibility order among agents, it is possible to define an operator to revise the credibility order. This will allow to represent changes over the credibility order.

Acknowledgment

We would like to thank the anonymous referee for their valuable comments on an earlier version of this paper. We are also grateful to Martín Moguillansky for his useful comments on previous drafts of this work. This work was partially supported by UNS (PGI 24/ZN18) and CONICET (PIP 112-200801-02798).

Appendix A

Proposition 3. Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in Bel(K_{A_i})<$><$>K_{A_i}<$><$>K^{\uparrow}_{A_i}<$><!--$ . That is,

$)(--><$>Pl(\alpha, K_{A_i}) = {\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\uparrow \Vbar}_{A_i} \alpha} min(X)))) = {\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\Vbar}_{A_i} \alpha} min(X))))<$><!--$ .

Proof

Let $)(--><$>{\Bbb A} = \{A_1,\ldots,A_n\}<$><$>K^{\uparrow}_{A_i} = K_{A_i}<$><$>K^{\uparrow}_{A_i} \subset K_{A_i}<$><$>Sen(K_{A_i})<$><$>K_{A_i}<$><$>m \geq 2<$><$>(\beta,A_i) \in X<$><$>1 \leq i \leq n<$><$>X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>K_{A_i}^\kernels} \alpha<$><$>m \ \beta–kernels<$><$>X,Y_1,\ldots,Y_{m-1}<$><$>(\beta, A_j^p) \in Y_p<$><$>1\leq p\leq m-1<$><$>j \neq i<$><$>1\leq j \leq n<$><!--$ ). Next, we will prove that will contain the only relevant tuples to compute the plausibility of α. There are three cases:

• If $)(--><$>min(X) = (\beta,A_i)<$><$>min(Y_p) = (\beta,A_j^p)<$><$>A_j^p \leq^{A_i}_{Co} A_i<$><$>X,Y_1,…,Y_{m-1}<$><$>\beta, A_i<$><$>\beta, A_j^1<$><$>\beta, A_j^{m-1}<$><$>\beta, A_i<$><$>\in X<$><$>A_j^p =^{A_i}_{Co} A_i<$><!--$ , note that the selection function follows the same policy either in compact belief base function as plausibility function. Hence, the selection function returns the same agent identifier in both cases.
• If $)(--><$>min(X) \neq (\beta,A_i)<$><$>min(Y_p) \neq (\beta,A_j^p)<$><$>X,Y_1,...,Y_{m-1}<$><!--$ differ only in the tuple containing β.
• If $)(--><$>min(X) \neq (\beta,A_i)<$><$>min(X) = (\omega,A_j)<$><$>min(Y_p) = (\beta, A_j^p)<$><$>(\omega,A_j) \in Y_p<$><$>A_j^p \leq^{A_i}_{Co} A_j<$><$>min(Y_p)\neq (\beta, A_j^p)<$><$>min(Y_p) = (\omega, A_{j})<$><$>max(min(X) \cup min(Y_1) \cup \ldots \cup min(Y_{m-1})) = (\omega,A_j) \in X<$><$>A_j^p =^{A_i}_{Co} A_i<$><!--$ , note that the selection function follows the same policy either in compact belief base function as plausibility function. Hence, the selection function returns the same agent identifier in both cases.

Therefore, from the $)(--><$>m \ \beta<$><$>X,Y_1,\ldots,Y_{m-1}<$><$>Pl(\alpha, K_{A_i})<$><!--$ is equal to:

$--><$$>{\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\uparrow \Vbar}_{A_i} \alpha} min(X)))) = {\cal S}_{A_i}(Ag(max(\bigcup_{X \in K^{\Vbar}_{A_i} \alpha}} min(X))))<$$><!--$

Proposition 4. Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in {\cal L}<$><$>\ominus_{\sigma_{\downarrow}}<$><$>-_{\sigma_{\downarrow}}<$><!--$ ’ an optimal contraction using plausibility operator, then

$--><$$>Sen(K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha) = Sen(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$$><!--$

Proof

( $)(--><$>\subseteq<$><$>\beta \in Sen(K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha)<$><$>\beta \in Sen(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$><$>(\beta, A_j) \in K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha<$><$>(\beta, A_j) \in (K_{A_i} \backslash \sigma_{\downarrow}(K_{A_i}^\kernels \alpha))<$><$>(\beta, A_j) \in K_{A_i}<$><$>(\beta, A_j) \not\in \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>K^{\uparrow}_{A_i} {^\kernels} \alpha \subseteq K_{A_i}^\kernels \alpha<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \subseteq \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>(\beta, A_j) \not\in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>\beta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha))<$><$>\beta \in Sen(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$><!--$ .

( $)(--><$>\supseteq<$><$>\beta \in Sen(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$><$>\beta \in Sen(K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha)<$><$>(\beta, A_j) \in K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>(\beta, A_j) \in K_{A_i} \backslash X<$><$>X = \{(\omega, A_{k}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha)) \text{ and } (\omega, A_k) \in K_{A_i}\}<$><$>(\beta, A_j) \in K_{A_i}<$><$>(\beta, A_j) \not\in X<$><$>(\beta, A_p) \in K^{\uparrow}_{A_i}<$><$>(\beta, A_p) \not\in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>A_j \leq^{A_i}_{Co} A_p<$><$>(\beta, A_p) \not \in \bigcup(K_{A_i}^\kernels \alpha)<$><$>(\beta, A_p) \not \in \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>(\beta, A_p) \not\in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>(\delta, A_q) \in Y \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>A_q \leq^{A_i}_{Co} A_p<$><$>(\delta, A_q) \in K^{\uparrow}_{A_i}<$><$>(\delta, A_q) \in K_{A_i}<$><$>Z \in K_{A_i}^\kernels \alpha<$><$>Sen(Y) = Sen(Z)<$><$>(\beta, A_p) \not \in Z \cap \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>(\beta, A_p) \not \in \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>(\beta, A_p) \in K_{A_i} \backslash <$><$>\sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>\beta \in Sen(K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha)<$><!--$ .

Proposition 5. Let $)(--><$>K_{A_i} \in {\cal K}<$><$>\alpha \in {\cal L}<$><$>\ominus_{\sigma_{\downarrow}}<$><$>-_{\sigma_{\downarrow}}<$><!--$ ’ an optimal contraction using plausibility operator, then

$--><$$>K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha \subseteq K_{A_i} -_{\sigma_{\downarrow}} \alpha<$$><!--$

Proof Let $)(--><$>(\beta, A_j) \in K_{A_i} \ominus_{\sigma_{\downarrow}} \alpha<$><$>(\beta,A_j) \in K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>(\beta, A_j) \in (K_{A_i} - \sigma_{\downarrow}(K_{A_i}^\kernels \alpha))<$><$>(\beta, A_j) \in K_{A_i}<$><$>(\beta, A_j) \not\in \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>K^{\uparrow}_{A_i} {^\kernels} \alpha \subseteq K_{A_i}^\kernels \alpha<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \subseteq \sigma_{\downarrow}(K_{A_i}^\kernels \alpha)<$><$>(\beta, A_j) \not\in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>\beta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha))<$><$>(\beta,A_j) \in K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><!--$ .

Next, we give a lemma used in the representation theorem of contraction operator (Theorem 1). Note that this Lemma is an adapted version of a property defined in Hansson (1999).

Lemma 1. $)(--><$>K^{\uparrow} {^\kernels} \alpha = K^{\uparrow} {^\kernels} \beta<$><$>K^{\uparrow}<$><$>\alpha \in Bel(K′)<$><$>\beta \in Bel(K′)<$><!--$ .

Proof We will use reductio by absurdum.

( $)(--><$>\Rightarrow<$><$>K^{\uparrow}<$><$>\alpha \in Bel(B)<$><$>\beta \not \in Bel(B)<$><$>K^{\uparrow}<$><$>\alpha \in Bel(B′)<$><$>K^{\uparrow} {^\kernels} \alpha<$><$>B″ \subseteq B′<$><$>B″ \subseteq B<$><$>\beta \not\in Bel(B)<$><$>\beta \not\in Bel(B″)<$><$>B″ \not \in K^{\uparrow} {^\kernels} \beta<$><$>B″ \in K^{\uparrow} {^\kernels} \alpha<$><$>B″ \not \in K^{\uparrow} {^\kernels} \beta<$><$>K^{\uparrow} {^\kernels} \alpha = K^{\uparrow} {^\kernels} \beta<$><!--$ .

( $)(--><$>\Leftarrow<$><$>K^{\uparrow} {^\kernels} \alpha \neq K^{\uparrow} {^\kernels} \beta<$><$>X \in K^{\uparrow} {^\kernels}\alpha<$><$>X \not\in K^{\uparrow} {^\kernels}\beta<$><!--$ . There are two cases:

– $)(--><$>\beta \not \in Bel(X)<$><$>\alpha \in Bel(X)<$><$>\beta \not\in Bel(X)<$><!--$ , showing that the conditions of the lemma are not satisfied.
– $)(--><$>\beta \in Bel(X)<$><$>X \not\in K^{\uparrow} {^\kernels}\beta<$><$>X′ \subset X<$><$>\beta \in Bel(X′)<$><$>X′ \subset X \in K^{\uparrow} {^\kernels} \alpha<$><$>\alpha \not\in Bel(X′)<$><$>\beta \in Bel(X′)<$><$>\alpha \not\in Bel(X′)<$><!--$ , showing that the conditions of the lemma are not satisfied.

Theorem 1. Let $)(--><$>K_{A_i} \in {\cal K}<$><$>-_{\sigma_{\downarrow}}<$><$>-_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ if and only if it satisfies CP-1,…, CP-4, that is, it satisfies success, inclusion, uniformity and minimal plausibility change.

Proof

$)(--><$>\bullet<$><$>-_{\sigma_{\downarrow}}<$><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>K_{A_i} \in {\cal K}<$><!--$ ) and for every consistent belief α, it holds that:

[Hypothesis] $)(--><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) = K^{\uparrow}_{A_i} \backslash K_{A_i} - \alpha<$><!--$ .

We must show:

– Part A.

1. ‘ $)(--><$>\sigma_{\downarrow}<$><!--$ ’ is a well defined function.
2. $)(--><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \subseteq \bigcup (K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><!--$ .
3. If $)(--><$>X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>X \neq \emptyset<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \neq \emptyset<$><!--$ .
4. If $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>(\beta, A_j) \in X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>(\delta, A_k) \in X<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

– Part B. ‘ $)(--><$>-_{\sigma_{\downarrow}}<$><$>K_{A_i} -_{\sigma_{\downarrow}} \alpha = K_{A_i} - \alpha<$><!--$ .

Part A.

1. ‘ $)(--><$>\sigma_{\downarrow}<$><!--$ ’ is a well defined function.

Let α and β two sentences such that $)(--><$>K^{\uparrow}_{A_i} {^\kernels} \alpha = K^{\uparrow}_{A_i} {^\kernels} \beta<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) = \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \beta)<$><$>K^{\uparrow}_{A_i} {^\kernels} \alpha = K^{\uparrow}_{A_i} {^\kernels} \beta<$><$>K^{\uparrow}_{A_i}<$><$>\alpha \in Bel(K′)<$><$>\beta \in Bel(K′)<$><$>Sen(K_{A_i}) = Sen(K^\uparrow_{A_i})<$><$>K^\uparrow_{A_i} \subseteq K_{A_i}<$><$>K_{A_i}<$><$>\alpha \in Bel(K″)<$><$>\beta \in Bel(K″)<$><$>K_{A_i} - \alpha = K_{A_i} - \beta<$><$>\sigma_{\downarrow}<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) = \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \beta)<$><!--$ .

2. $)(--><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \subseteq \bigcup (K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><!--$ .

Let $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>\sigma_{\downarrow}<$><$>(\beta, A_j) \in <$><$>(K^{\uparrow}_{A_i} - K_{A_i} - \alpha)<$><$>(\beta, A_j) \in K^{\uparrow}_{A_i}<$><$>(\beta, A_j) \not\in K_{A_i} - \alpha<$><$>K′ \subseteq K^{\uparrow}_{A_i}<$><$>\alpha \not\in Bel(K′)<$><$>\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><$>\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>\alpha \not\in Bel(K′)<$><$>\alpha \not\in Bel(K″)<$><$>\alpha \not\in Bel(K″)<$><$>\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>(\beta, A_j)<$><$>(\beta, A_j) \in \bigcup(K^{\uparrow}_{A_i} {^\kernels}\alpha)<$><!--$ .

3. If $)(--><$>X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>X \neq \emptyset<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \neq \emptyset<$><!--$ .

Let $)(--><$>\emptyset \neq X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \neq \emptyset<$><$>(\beta,A_j) \in X<$><$>(\beta,A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>\alpha \not \in Bel(K_{A_i} - \alpha)<$><$>X \neq \emptyset<$><$>\alpha \in Bel(X)<$><$>X \not\subseteq K_{A_i} - \alpha<$><$>(\beta, A_j)<$><$>(\beta, A_j) \in X<$><$>(\beta, A_j) \not \in K_{A_i} - \alpha<$><$>X \subseteq K^{\uparrow}_{A_i}<$><$>(\beta, A_j) \in (K^{\uparrow}_{A_i} - K_{A_i} - \alpha)<$><$>\sigma_{\downarrow}<$><$>(\beta,A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \neq \emptyset<$><!--$ .

4. If $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>(\beta, A_j) \in X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>(\delta, A_k) \in X<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Suppose that $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>\sigma_{\downarrow}<$><$>(\beta, A_j) \in (K^{\uparrow}_{A_i} \backslash K_{A_i} - \alpha)<$><$>(\beta, A_j) \in K^{\uparrow}_{A_i}<$><$>(\beta, A_j) \not\in K_{A_i} - \alpha<$><$>K′ \subseteq K^{\uparrow}_{A_i}<$><$>\alpha \not\in Bel(K′)<$><$>\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><$>(\delta,A_k) \in K′<$><$>\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) - \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><$>\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>\alpha \not\in Bel(K′)<$><$>\alpha \not\in Bel(K″)<$><$>\alpha \not\in Bel(K″)<$><$>\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>(\beta, A_j)<$><$>(\delta,A_k) \in X<$><$>\alpha \not \in Bel(X - \{(\delta,A_k)\})<$><$>X \subseteq K′<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Part B. ‘ $)(--><$>-_{\sigma_{\downarrow}}<$><$>K_{A_i} -_{\sigma_{\downarrow}}\alpha = K_{A_i} - \alpha<$><!--$ .

Let ‘ $)(--><$>-_{\sigma_{\downarrow}}<$><$>K_{A_i} -_{\sigma_{\downarrow}}\alpha = K_{A_i} \backslash X<$><$>X = \{(\omega, A_{j}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha)) \ {\rm and} \ (\omega, A_j) \in K_{A_i}\}<$><$>\sigma_{\downarrow}<$><!--$ defined as in the hypothesis.

( $)(--><$>\supseteq<$><$>(\delta, A_j) \in K_{A_i} - \alpha<$><$>K_{A_i} - \alpha \subseteq K_{A_i}<$><$>(\delta, A_j) \in K_{A_i}<$><$>(\delta, A_j) \in K_{A_i} - \alpha<$><$>(\delta, A_j) \in K_{A_i}<$><$>(\delta, A_j) \not \in (K_{A_i} \backslash K_{A_i} - \alpha)<$><$>K^{\uparrow}_{A_i} \subseteq K_{A_i}<$><$>(\delta, A_j) \not \in (K^{\uparrow}_{A_i} \backslash K_{A_i} - \alpha)<$><$>\sigma_{\downarrow}<$><$>(\delta, A_j) \not \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha)<$><!--$ . We have two cases:

– $)(--><$>(\delta, A_j) \in K^{\uparrow}_{A_i}<$><$>\delta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha))<$><!--$ .
– $)(--><$>(\delta, A_j) \in K_{A_i}<$><$>(\delta, A_k) \in K^{\uparrow}_{A_i}<$><$>A_j \leq^{A_i}_{Co} A_k<$><$>(\delta, A_k) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>(\delta, A_k) \in (K^{\uparrow}_{A_i} \backslash K_{A_i} - \alpha)<$><$>\sigma_{\downarrow}<$><$>(\delta, A_k) \not \in K_{A_i} - \alpha<$><$>(\delta, A_j) \in K_{A_i} - \alpha<$><$>(\delta, A_k) \in K^{\uparrow}_{A_i}<$><$>(\delta, A_k) \not\in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>\delta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha))<$><!--$ .

Hence, it follows from definition that $)(--><$>(\delta, A_j) \in K_{A_i} -_{\sigma_{\downarrow}}\alpha<$><!--$ .

( $)(--><$>\subseteq<$><$>(\delta, A_j) \in K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>(\delta, A_j) \in K_{A_i} - X<$><$>X = \{(\omega, A_{k}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha))<$><$>(\omega, A_k) \in K_{A_i}\}<$><$>(\delta, A_j) \in K_{A_i}<$><$>(\delta, A_j) \not \in X<$><$>\delta \not \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha))<$><$>\sigma_{\downarrow}<$><$>\delta \not \in Sen(K^{\uparrow}_{A_i} \backslash (K_{A_i} - \alpha))<$><$>\delta \in Sen(K_{A_i} - \alpha)<$><$>(\delta, A_j) \in K_{A_i} - \alpha<$><!--$ .

$)(--><$>\bullet<$><$>-_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ . We need to show that it satisfies the four conditions of the theorem.

(CP-1) Success: if $)(--><$>\alpha \not\in Cn(\emptyset)<$><$>\alpha \not\in Bel(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$><!--$ .

Proof. Suppose to the contrary that $)(--><$>\alpha \not \in Cn(\emptyset)<$><$>\alpha \in Bel(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$><$>K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>\alpha \in Bel(K′)<$><$>K″ \subseteq K′<$><$>K′ \subseteq K_{A_i} -_{\sigma_{\downarrow}} \alpha \subseteq K_{A_i}<$><$>K_{A_i}<$><$>K″ \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>K″ \subseteq K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>\alpha \not\in Cn(\emptyset)<$><$>K″ \neq \emptyset<$><$>\beta \in Sen(K″)<$><$>\beta \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha))<$><$>\beta \not \in Sen(K_{A_i} -_{\sigma_{\downarrow}} \alpha)<$><$>\beta \in Sen(K″)<$><$>K″ \subseteq K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><!--$ .

(CP-2) Inclusion: $)(--><$>K_{A_i} -_{\sigma_{\downarrow}} \alpha \subseteq K_{A_i}<$><!--$ .

Proof. Straightforward by definition.

Proof. Suppose that for all subset of $)(--><$>K_{A_i}<$><$>\alpha \in Bel(K′)<$><$>\beta \in Bel(K′)<$><$>K^{\uparrow}_{A_i} {^\kernels} \alpha = K^{\uparrow}_{A_i} {^\kernels} \beta<$><$>\sigma_{\downarrow}<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha) = \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\beta)<$><$>K_{A_i} -_{\sigma_{\downarrow}} \alpha = K_{A_i} -_{\sigma_{\downarrow}} \beta<$><!--$ .

(CP-4) Minimal Plausibility Change: If $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>K′ \subseteq K_{A_i}<$><$>\alpha \not\in Bel(K′)<$><$>(\beta, A_j) \in K_{A_i}<$><!--$ such that:

• $)(--><$>\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><!--$ ,
• or $)(--><$>A_p \leq^{A_i}_{Co} A_j<$><!--$ , and
• for all $)(--><$>(\delta,A_k) \in K′<$><$>\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) - \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Proof. Suppose $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} -_{\sigma_{\downarrow}} \alpha<$><$>(\beta, A_p) \in Y<$><$>Y = \{(\omega, A_{q}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\alpha)) \ and \ (\omega, A_q) \in K_{A_i}\}<$><$>\beta \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha))<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \alpha) \subseteq \bigcup (K^{\uparrow}_{A_i} {^\kernels} \alpha)<$><$>(\beta, A_j)<$><$>(\beta, A_j) \in X \in K^{\uparrow}_{A_i} {^\kernels} \alpha<$><$>(\beta, A_j) \in K^{\uparrow}_{A_i}<$><$>A_p \leq^{A_i}_{Co} A_j<$><$>K′ \subseteq K_{A_i}<$><$>X - \{(\beta, A_j)\} \subseteq K′<$><!--$ . We have two cases:

– $)(--><$>K′ = X \backslash \{(\beta, A_j)\}<$><$>\alpha \not \in Bel(K′)<$><$>\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><$>(\delta,A_k) \in K′<$><$>\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) - \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .
– $)(--><$>X \backslash \{(\beta, A_j)\} \subset K′<$><$>\{(\beta, A_j)\} \not\in K′<$><$>(\delta,A_k)\in K′<$><$>A_k \lt^{A_i}_{Co} A_j<$><$>(\delta, A_k) \not \in X<$><$>\alpha \in Bel((K′\cup \{(\beta,A_j)\}) - \{(\delta,A_k)\})<$><!--$ .

Theorem 2. Let $)(--><$>K_{A_i} \in {\cal K}<$><$>*_{\sigma_{\downarrow}}<$><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ if and only if it satisfies RP-1,…, RP-5, that is, it satisfies success, inclusion, consistency, uniformity and minimal plausibility change.

Proof

$)(--><$>\bullet<$><$>*_{\sigma_{\downarrow}}<$><$>\sigma_{\downarrow}<$><$>K_{A_i}<$><$>K_{A_i} \in {\cal K}<$><!--$ ) and for every consistent belief α, it holds that:

[Hypothesis] $)(--><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) = K^{\uparrow}_{A_i} - K_{A_i} * (\alpha, A_j)<$><!--$ .

We must show:

– Part A.

1. ‘ $)(--><$>\sigma_{\downarrow}<$><!--$ ’ is a well defined function.
2. $)(--><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \subseteq \bigcup (K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><!--$ .
3. If $)(--><$>X \in K^{\uparrow}_{A_i} {^\kernels} \neg\alpha<$><$>X \neq \emptyset<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \neq \emptyset<$><!--$ .
4. If $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>(\beta, A_j) \in X \in K^{\uparrow}_{A_i} {^\kernels} \neg\alpha<$><$>(\delta, A_k) \in X<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

– Part B. ‘ $)(--><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i} *_{\sigma_{\downarrow}}(\alpha, A_j) = K_{A_i} * (\alpha, A_j)<$><!--$ .

Part A.

1. ‘ $)(--><$>\sigma_{\downarrow}<$><!--$ ’ is a well defined function.

Let $)(--><$>\neg\alpha<$><$>\neg\beta<$><$>K^{\uparrow}_{A_i} {^\kernels} \neg\alpha = K^{\uparrow}_{A_i} {^\kernels} \neg\beta<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) = \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\beta)<$><$>K^{\uparrow}_{A_i} {^\kernels} \neg\alpha = K^{\uparrow}_{A_i} {^\kernels} \neg\beta<$><$>K^{\uparrow}_{A_i}<$><$>\neg\alpha \in Bel(K′)<$><$>\neg\beta \in Bel(K′)<$><$>K^{\uparrow}_{A_i}<$><$>Sen(K′) \vdash \neg\alpha<$><$>Sen(K′)\vdash \neg\beta<$><$>K^{\uparrow}_{A_i}<$><$>\{\alpha\}\cupSen(K′) \vdash \bot<$><$>\{\beta\}\cupSen(K′) \vdash \bot<$><$>K^{\uparrow}_{A_i} \subseteq K_{A_i}<$><$>Sen(K^{\uparrow}_{A_i}) = Sen(K_{A_i})<$><$>K_{A_i}<$><$>\{\alpha\}\cupSen(K″) \vdash \bot<$><$>\{\beta\}\cupSen(K″) \vdash \bot<$><$>K_{A_i} \cap (K_{A_i} * (\alpha ,A_j)) = K_{A_i} \cap (K_{A_i} * (\beta ,A_k))<$><$>K_{A_i} \backslash (K_{A_i} * (\alpha ,A_j)) = K_{A_i} - (K_{A_i} * (\beta ,A_k))<$><$>\sigma_{\downarrow}<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) = \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\beta)<$><!--$ .

2. $)(--><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \subseteq \bigcup (K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><!--$ .

Let $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>\sigma_{\downarrow}<$><$>(\beta, A_j) \in (K^{\uparrow}_{A_i} \backslash K_{A_i} * (\alpha,A_k))<$><$>(\beta, A_j) \in K^{\uparrow}_{A_i}<$><$>(\beta, A_j) \not\in K_{A_i} * (\alpha, A_k)<$><$>K′ \subseteq K^{\uparrow}_{A_i}<$><$>\neg\alpha \not\in Bel(K′)<$><$>\neg\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><$>\neg\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>\neg\alpha \not\in Bel(K′)<$><$>\neg\alpha \not\in Bel(K″)<$><$>\neg\alpha \not\in Bel(K″)<$><$>\neg\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>\neg\alpha<$><$>(\beta, A_j)<$><$>(\beta, A_j) \in \bigcup(K^{\uparrow}_{A_i} {^\kernels}\neg\alpha)<$><!--$ .

3. If $)(--><$>X \in K^{\uparrow}_{A_i} {^\kernels} \neg\alpha<$><$>X \neq \emptyset<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \neq \emptyset<$><!--$ .

Let $)(--><$>\emptyset \neq X \in K^{\uparrow}_{A_i} {^\kernels} \neg\alpha<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \neq \emptyset<$><$>(\beta,A_j) \in X<$><$>(\beta,A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>K_{A_i}<$><$>K_{A_i} * (\alpha, A_k)<$><$>X \neq \emptyset<$><$>X \not\subseteq K_{A_i} * (\alpha, A_k)<$><$>(\beta, A_j) \in X<$><$>(\beta,A_j) \not\in K_{A_i} * (\alpha,A_k)<$><$>X \subseteq K^{\uparrow}_{A_i}<$><$>(\beta, A_j) \in (K^{\uparrow}_{A_i} \backslash K_{A_i} * (\alpha,A_k))<$><$>\sigma_{\downarrow}<$><$>(\beta,A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>X \cap \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \neq \emptyset<$><!--$ .

4. If $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>(\beta, A_j) \in X \in K^{\uparrow}_{A_i} {^\kernels} \neg\alpha<$><$>(\delta, A_k) \in X<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Suppose that $)(--><$>(\beta, A_j) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>\sigma_{\downarrow}<$><$>(\beta, A_j) \in (K^{\uparrow}_{A_i} - K_{A_i} * (\alpha,A_p))<$><$>(\beta, A_j) \in K^{\uparrow}_{A_i}<$><$>(\beta, A_j) \not\in K_{A_i} * (\alpha,A_p)<$><$>K′ \subseteq K^{\uparrow}_{A_i}<$><$>\neg\alpha \not\in Bel(K′)<$><$>\neg\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><$>(\delta,A_k) \in K′<$><$>\neg\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) - \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><$>\neg\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>\neg\alpha \not\in Bel(K′)<$><$>\neg\alpha \not\in Bel(K″)<$><$>\neg\alpha \not\in Bel(K″)<$><$>\neg\alpha \in Bel(K″ \cup \{(\beta, A_j)\})<$><$>\neg\alpha<$><$>(\beta, A_j)<$><$>(\delta,A_k) \in X<$><$>\neg\alpha \not \in Bel(X \backslash \{(\delta,A_k)\})<$><$>X \subseteq K′<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Part B. ‘ $)(--><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i} *_{\sigma_{\downarrow}}(\alpha, A_j) = K_{A_i} * (\alpha, A_j)<$><!--$ .

Let ‘ $)(--><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i} *_{\sigma_{\downarrow}}(\alpha,A_j) = (K_{A_i} - X) \cup \{(\alpha, A_j)\} <$><$>X = \{(\omega, A_{p}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\neg\alpha)) \text{ and } (\omega, A_p) \in K_{A_i}\}<$><$>\sigma_{\downarrow}<$><!--$ defined as in the hypothesis.

( $)(--><$>\supseteq<$><$>(\delta, A_k) \in K_{A_i} * (\alpha, A_j)<$><$>K_{A_i} * (\alpha, A_j) \subseteq K_{A_i} \cup \{(\alpha, A_j)\}<$><$>(\delta, A_k) \in K_{A_i} \cup \{(\alpha, A_j)\}<$><$>(\delta, A_k) = (\alpha, A_j)<$><$>(\delta, A_k) \in K_{A_i} *_{\sigma_{\downarrow}}(\alpha,A_j)<$><$>(\delta, A_k) \neq (\alpha, A_j)<$><$>(\delta, A_k) \in K_{A_i} \cup \{(\alpha, A_j)\}<$><$>(\delta, A_k) \in K_{A_i}<$><$>(\delta, A_k) \in K_{A_i} * (\alpha, A_j)<$><$>(\delta, A_k) \in K_{A_i}<$><$>(\delta, A_k) \not \in (K_{A_i} \backslash K_{A_i} * (\alpha, A_j))<$><$>K^{\uparrow}_{A_i} \subseteq K_{A_i}<$><$>(\delta, A_k) \not \in (K^{\uparrow}_{A_i} - K_{A_i} * (\alpha, A_j))<$><$>\sigma_{\downarrow}<$><$>(\delta, A_k) \not \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\neg\alpha)<$><!--$ . We have two cases:

– $)(--><$>(\delta, A_k) \in K^{\uparrow}_{A_i}<$><$>\delta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha))<$><!--$ .
– $)(--><$>(\delta, A_k) \in K_{A_i}<$><$>(\delta, A_p) \in K^{\uparrow}_{A_i}<$><$>A_k \leq^{A_i}_{Co} A_p<$><$>(\delta, A_p) \in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>(\delta, A_p) \in (K^{\uparrow}_{A_i} \backslash K_{A_i} * (\alpha,A_j))<$><$>\sigma_{\downarrow}<$><$>(\delta, A_p) \not \in K_{A_i} * (\alpha,A_j)<$><$>(\delta, A_k) \in K_{A_i} * (\alpha,A_j)<$><$>(\delta, A_p) \in K^{\uparrow}_{A_i}<$><$>(\delta, A_p) \not\in \sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>\delta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha))<$><!--$ .

Therefore, it follows from definition that $)(--><$>(\delta, A_k) \in K_{A_i} *_{\sigma_{\downarrow}}(\alpha,A_j)<$><!--$ .

( $)(--><$>\subseteq<$><$>(\delta, A_k) \in K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)<$><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j) \subseteq K_{A_i} \cup \{(\alpha, A_j)\}<$><$>(\delta, A_k) \in K_{A_i} \cup \{(\alpha, A_j)\}<$><$>(\delta, A_k) \in K_{A_i}<$><$>(\delta, A_k) = (\alpha, A_j)<$><!--$ . We have two cases:

• $)(--><$>(\delta, A_k) = (\alpha, A_j)<$><$>(\delta, A_k) \in K_{A_i} * (\alpha,A_j)<$><!--$ .
• $)(--><$>(\delta, A_k) \in K_{A_i}<$><$>(\delta, A_k) \neq (\alpha, A_j)<$><$>\delta \not\in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\neg\alpha))<$><$>\sigma_{\downarrow}<$><$>\delta \not\in Sen(K^\uparrow_{A_i} \backslash (K_{A_i} * (\alpha,A_j))<$><$>(\delta, A_k) \in K_{A_i}<$><$>\delta \in Sen(K_{A_i})<$><$>Sen(K_{A_i}) = Sen(K^\uparrow_{A_i})<$><$>\delta \in Sen(K_{A_i} * (\alpha,A_j))<$><$>(\delta, A_k) \in K_{A_i} * (\alpha,A_j)<$><!--$ .

$)(--><$>\bullet<$><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><!--$ . We need to show that it satisfies the five conditions of the theorem.

(RP-1) Success: $)(--><$>(\alpha, A_j) \in K_{A_i} *_{\sigma_{\downarrow}}(\alpha, A_j)<$><!--$ .

Proof. Straightforward by definition.

(RP-2) Inclusion: $)(--><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j) \subseteq K_{A_i} \cup \{(\alpha, A_j)\}<$><!--$ .

Proof. Straightforward by definition.

(RP-3) Consistency: if α is consistent then $)(--><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)<$><!--$ is consistent.

Proof. Straightforward by definition.

(RP-4) Uniformity: If for all $)(--><$>K′ \subseteq K_{A_i}<$><$>\{\alpha\} \cup Sen(K′) \vdash \perp<$><$>\{\beta\} \cup Sen(K′) \vdash \perp<$><$>K_{A_i} \cap (K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)) = K_{A_i} \cap (K_{A_i} *_{\sigma_{\downarrow}} (\beta, A_k))<$><!--$ .

Proof. Suppose that for all subset of $)(--><$>K_{A_i}<$><$>\{\alpha\} \cup Sen(K′) \vdash \perp<$><$>\{\beta\} \cup Sen(K′) \vdash \perp<$><$>Sen(K′) \vdash \neg \alpha<$><$>Sen(K′) \vdash \neg \beta<$><$>\neg \alpha \in Bel(K′)<$><$>\neg \beta \in Bel(K′)<$><$>K_{A_i}^{\uparrow} {^\kernels} \neg \alpha = K_{A_i}^{\uparrow} {^\kernels} \neg \beta<$><$>\sigma_{\downarrow}<$><$>\sigma_{\downarrow}(K_{A_i}^{\uparrow} {^\kernels}\neg\alpha) = \sigma_{\downarrow}(K_{A_i}^{\uparrow} {^\kernels}\neg\beta)<$><$>K_{A_i} -_{\sigma_{\downarrow}} \neg\alpha = K_{A_i} -_{\sigma_{\downarrow}} \neg\beta<$><$>K_{A_i} \cap (K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)) = K_{A_i} \cap (K_{A_i} *_{\sigma_{\downarrow}} (\beta, A_k))<$><!--$ .

(RP-5) Minimal Plausibility Change: If $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_k)<$><$>K′ \subseteq K_{A_i}<$><$>\neg\alpha \not\in Bel(K′)<$><$>(\beta, A_j) \in K_{A_i}<$><!--$ such that:

• $)(--><$>\neg\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><!--$ ,
• or $)(--><$>A_p \leq^{A_i}_{Co} A_j<$><!--$ , and
• for all $)(--><$>(\delta,A_k) \in K′<$><$>\neg\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) \backslash \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Proof. Suppose $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_k)<$><$>(\beta, A_p) \not\in <$><$>(K_{A_i} -_{\sigma_{\downarrow}} \neg\alpha) + (\alpha, A_k)<$><$>(\beta, A_p) \in \{(\omega, A_{q}): \omega \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels}\neg\alpha)) <$><$>and \ (\omega, A_q) \in K_{A_i}\}<$><$>\beta \in Sen(\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha))<$><$>\sigma_{\downarrow}(K^{\uparrow}_{A_i} {^\kernels} \neg\alpha) \subseteq \bigcup (K^{\uparrow}_{A_i} {^\kernels} \neg\alpha)<$><$>(\beta, A_j)<$><$>(\beta, A_j) \in X \in K^{\uparrow}_{A_i} {^\kernels} \neg\alpha<$><$>(\beta, A_j) \in K^{\uparrow}_{A_i}<$><$>A_p \leq^{A_i}_{Co} A_j<$><$>K′ \subseteq K_{A_i}<$><$>X \backslash \{(\beta, A_j)\} \subseteq K′<$><!--$ . We have two cases:

– $)(--><$>K′ = X \backslash \{(\beta, A_j)\}<$><$>\neg\alpha \not \in Bel(K′)<$><$>\neg\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><$>(\delta,A_k) \in K′<$><$>\neg\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) \backslash \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .
– $)(--><$>X \backslash \{(\beta, A_j)\} \subset K′<$><$>\{(\beta, A_j)\} \not\in K′<$><$>(\delta,A_k)\in K′<$><$>A_k \lt^{A_i}_{Co} A_j<$><$>(\delta, A_k) \not \in X<$><$>\neg\alpha \in Bel((K′\cup \{(\beta,A_j)\}) \backslash \{(\delta,A_k)\})<$><!--$ .

Proposition 6. If ‘+’ satisfies EP-1,…,EP-5 and ‘ $)(--><$>-_{\sigma_{\downarrow}}<$><$>*_{\sigma_{\downarrow}}<$><!--$ ’ satisfies RP-1,…,RP-5.

Proof

Let ‘ $)(--><$>*_{\sigma_{\downarrow}}<$><$>K_{A_i}<$><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j) = (K_{A_i} -_{\sigma_{\downarrow}} \neg \alpha) +<$><$> (\alpha, A_j)<$><!--$ . We need to show that it satisfies RP-1,…,RP-5 from the postulates of expansion using plausibility and from the postulates of optimal contraction using plausibility.

(RP-1) Success: $)(--><$>(\alpha, A_j) \in K_{A_i} *_{\sigma_{\downarrow}}(\alpha, A_j)<$><!--$ .

Proof. Straightforward by Definition 21 and EP-1.

(RP-2) Inclusion: $)(--><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j) \subseteq K_{A_i} \cup \{(\alpha, A_j)\}<$><!--$ .

Proof. It follows from CP-2 that $)(--><$>K_{A_i} -_{\sigma_{\downarrow}} \neg \alpha \subseteq K_{A_i}<$><$>(K_{A_i} -_{\sigma_{\downarrow}} \neg \alpha) \cup \{(\alpha,A_j)\} \subseteq <$><$>K_{A_i} \cup \{(\alpha,A_j)\}<$><$>(K_{A_i} -_{\sigma_{\downarrow}} \neg \alpha) + (\alpha,A_j) \subseteq K_{A_i} \cup \{(\alpha,A_j)\}<$><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j) \subseteq K_{A_i} \cup \{(\alpha,A_j)\}<$><!--$ .

(RP-3) Consistency: if α is consistent then $)(--><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)<$><!--$ is consistent.

Proof. By Definition 21, $)(--><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j) = (K_{A_i} -_{\sigma_{\downarrow}} \neg \alpha) + (\alpha, A_j)<$><$>K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)<$><!--$ is consistent.

(RP-4) Uniformity: If for all $)(--><$>K′ \subseteq K_{A_i}<$><$>\{\alpha\} \cup Sen(K′) \vdash \perp<$><$>\{\beta\} \cup Sen(K′) \vdash \perp<$><$>K_{A_i} \cap (K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_j)) = K_{A_i} \cap (K_{A_i} *_{\sigma_{\downarrow}} (\beta, A_k))<$><!--$ .

• $)(--><$>\neg\alpha \in Bel(K′ \cup \{(\beta, A_j)\})<$><!--$ ,
• or $)(--><$>A_p \leq^{A_i}_{Co} A_j<$><!--$ , and
• for all $)(--><$>(\delta,A_k) \in K′<$><$>\neg\alpha \not \in Bel((K′\cup \{(\beta,A_j)\}) - \{(\delta,A_k)\})<$><$>A_j \leq^{A_i}_{Co} A_k<$><!--$ .

Proof. Suppose $)(--><$>(\beta, A_p) \in K_{A_i}<$><$>(\beta, A_p) \not\in K_{A_i} *_{\sigma_{\downarrow}} (\alpha, A_k)<$><$>(\beta, A_p) \not\in K_{A_i} -_{\sigma_{\downarrow}} \neg\alpha<$><!--$ . Thus, it follows by CP-4 that all conditions of the postulate are satisfied.

Footnotes

¹ A policy can be seen as a design decision.

² We assume that, given a relation $)(--><$>{{\preceq}_{{{K}_{{{A}_i}}}}}<$><$>{\cal L}\times{\cal L}<$><$>{{\preceq}_X}<$><$>X\, \subseteq \,{{K}_{{{A}_i}}}.<$><!--$

References

Alchourrón, C., Makinson, D. 1985. On the logic of theory change: safe contraction. Studia Logica 44, 405–422.Google Scholar

Alchourrón, C., Gärdenfors, P., Makinson, D. 1985. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic 50(2), 510–530.CrossRef Google Scholar

Benferhat, S., Dubois, D., Prade, H. 1993. Argumentative inference in uncertain and inconsistent knowledge bases. In The Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI'03), 411–419. Morgan Kaufmann.Google Scholar

Benferhat, S., Dubois, D., Prade, H., Williams, M. A. 2002. A practical approach to revising prioritized knowledge bases. Studia Logica 70(1), 105–130.Google Scholar

Cantwell, J. 1998. Resolving conflicting information. Journal of Logic, Language and Information 7(2), 191–220.Google Scholar

Dalal, M., 1988. Investigations into a theory of knowledge base revision. Proceedings of Seventh International Conference on Artificial Intelligence, (AAAI-88), 475–479.Google Scholar

Dragoni, A., Giorgini, P., Puliti, P. 1994. Distributed belief revision versus distributed truth maintenance. In Proceedings of the Sixth IEEE International Conference on Tools with Artificial Intelligence (TAI 94), 499–505. IEEE Computer Society Press.Google Scholar

Dragoni, A., Giorgini, P., Baffetti, M. 1997. Distributed belief revision vs. belief revision in a multi-agent environment: first results of a simulation experiment. In Multi-agent Rationality, Boman M. & Van de Velde W. (eds.) Springer-Verlag, 45–62.Google Scholar

Falappa, M. A., Kern-Isberner, G., Simari, G. R. 2002. Explanations, belief revision and defeasible reasoning. Artificial Intelligence 141(1), 1–28.Google Scholar

Fermé, E. L., Hansson, S. O. 1999. Selective revision. Studia Logica 63(3), 331–342.Google Scholar

Fuhrmann, A. 1991. Theory contraction through base contraction. Journal of Philosophical Logic 20(2), 175–203.Google Scholar

Gärdenfors, P. 1981. An epistemic approach to conditionals. American Philosophical Quarterly 18(3), 203–211.Google Scholar

Gärdenfors, P. 1992. Belief Revision, chapter Belief Revision: an introduction Cambridge University Press, 1–28.Google Scholar

Gärdenfors, P., Makinson, D. 1988. Revisions of knowledge systems using epistemic entrenchment. In Second Conference on Theoretical Aspects of Reasoning about Knowledge Conference, 83–95.Google Scholar

Hansson, S. O. 1992. In defense of base contraction. Synthese 91(3), 239–245.CrossRef Google Scholar

Hansson, S. O. 1994. Kernel contraction. Journal of Symbolic Logic 59(3), 845–859.Google Scholar

Hansson, S. O. 1997. Semi-revision. Journal of Applied Non-Classical Logic 151–175.Google Scholar

Hansson, S. O. 1999. A Textbook of Belief Dynamics: Theory Change and Database Updating. Kluwer Academic Publishers.Google Scholar

Hansson, S. O., Fermé, E., Cantwell, J., Falappa, M. 2001. Credibility limited revision. The Journal of Symbolic Logic 66(4), 1581–1596.CrossRef Google Scholar

Hein, J. L. 2010. Discrete Structures, Logic, and Computability, Chapter Equivalence, Order, and Inductive Proof, third edition. Jones and Bartlett.Google Scholar

Kfir-Dahav, N. E., Tennenholz, M. 1996. Multi-agent belief revision. In Theoretical Aspects of Rationality and Knowledge: Proceeding of the Sixth Conference (TARK 1996). Morgan Kaufmann Publishers Inc. 175–196.Google Scholar

Konieczny, S., Grespan, M. M., Pérez, R. P. 2010. Taxonomy of improvement operators and the problem of minimal change. In Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR'10).Google Scholar

Krümpelmann, P., Tamargo, L. H., García, A. J., Falappa, M. A. 2009. Forwarding credible information in multi-agent systems. Proceedings of the 3rd International Conference on Knowledge Science, Engineering and Management (KSEM 2009), 5914/2009: 41–53.Google Scholar

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

Liu, W., Williams, M-A. 1999. A framework for multi-agent belief revision, part i: the role of ontology. In Australian Joint Conference on Artificial Intelligence, 168–179.Google Scholar

Makinson, D. 1997. Screened revision. Theoria: Special Issue on Non-Prioritized Belief Revision.Google Scholar

Malheiro, B., Jennings, N., Oliveira, E. 1994. Belief revision in multi-agent systems. Proceeding of the 11th European Conference on Artificial Intelligence (ECAI 94), 294–298.Google Scholar

Rott, H. 1992. Preferential belief change using generalized epistemic entrenchment. Journal of Logic, Language and Information 1(1), 45–78.Google Scholar

Tamargo, L. H., García, A. J., Falappa, M. A., Simari, G. R. 2008. Consistency maintenance of plausible belief bases based on agents credibility. 12th International Workshop on Non-Monotonic Reasoning (NMR), 50–58.Google Scholar

Tamargo, L. H., García, A. J., Falappa, M. A., Simari, G. R. 2009. A belief revision approach to inconsistency handling in multi-agent systems. The IJCAI-09 Workshop on Nonmonotonic Reasoning, Action and Change (NRAC), 63–70.Google Scholar

Figure 1 Belief Revision Hierarchy.

Article contents

Modeling knowledge dynamics in multi-agent systems based on informants

Abstract

Information

1 Introduction and motivation

2 Epistemic model for Multi-Source Belief Revision

3 Sentences plausibility

4 Change operators based on informants

4.1 Expansion operator based on informants

4.2 Contraction operator based on informants

4.2.1 Construction

4.2.2 Properties

4.3 Prioritized revision using plausibility

4.3.1 Construction

4.3.2 Properties

4.4 Non prioritized revision using plausibility

4.4.1 Construction

4.4.2 Properties: success postulate must be weakened

4.5 Application example

5 Forwarding Information

5 Conclusions and Related Works

Acknowledgment

Appendix A

Footnotes

References

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests