-The aim of this paper is to propose a logical framework for reasoning about signed information. That is, as long as agents receive information in a multi-agent system, they keep track of the information source. The main advantage is that by considering a reliability relation over the sources of information, agents can justify their own current belief state. Agents believe at first information issued from the most reliable sources. Keeping track of belief's origin also enables agents to improve communication by asking and gaining details about exchanged information. This is a key issue in trust handling and improvement: an agent believes some statement because it may justify the statement's origin and its reliability.
An agent embedded in a multi-agent system gets
information from multiple origins; it captures information from its
own sensors or, through some communication channels it may
receive messages issued by other agents. Based on this set
of basic information the agent then defines its beliefs and
performs actions [
The aim of this paper is to propose a modal framework
for representing agent’s belief state and its dynamics by
considering signed information, that is information associated
to its source. If many work has been made in order to show
how an agent can merge information issued from multiple
origins [
The dynamics is usually described in terms of performative
actions based on KQML performatives [
The paper is structured as follows: In section II, we present the intuitive meaning of signed information and belief state. Next in section III, we present the technical details of the modal logic framework. In section IV, we then represent an intuitive and common policy for relating signed information and belief which consists in the adoption as belief of all consistent information. Next, in section V, we extend the logical system with actions of the form “agent a tells to agent b that a certain fact p is true”. We conclude the paper in section VI by summing up the contribution and considering some open issues.
Handling the source of information leads to the notion of signed statement, that is some statement is true according to some source. From a semantics perspective, we want to be able to represent, w.r.t. some initial state of affairs, for each agent, what are the possible states that can be signed by each source. Agents build their own belief state using information signed by each source and the reliability of the source.
are blue (bc), red (rc) and yellow (yc). Now suppose a police detective who is interviewing the witnesses of the accident. Let po be the police detective. The first witness w1 tells to the police detective that the blue car is responsible of the accident while the second one (w2) states that the red car has caused the collision. Both of them tell to the police detective that yc is not responsible of the accident. In that context of information gathering, the police detective does not need to assume that the witnesses tell the truth or believe in information they provide. The police detective just needs to assume that w1 provides or signs information bc ∧ ¬rc ∧ ¬yc and w2 provides or signs information ¬bc ∧ rc ∧ ¬yc. Next, based on these pieces of information, the police detective will build his opinion, i.e. his belief about the accident. The police detective faces contradicting information about the blue and red cars, but because the witnesses both agree about the yellow one, the police detective should believe that the yellow car is not the responsible of the collision. That is, the detective is willing to root his belief upon the set of signed statements he handles.
Signed statements can be represented through Kripke models using one accessibility relation per source of information. Let Sign(b, p) be a modal operator stating that statement p is true according to source b. Sign(b, p) is true in state w if p holds in all states reachable from w through a relation denoted Sb describing the possible information states issued from b.
tion which might be signed by the two witnesses are bc and rc which leads to the signed statements Sign(w1, bc),
ple, hereafter we will focus on the two signed statements Sign(w1, bc ∧ ¬rc ∧ ¬yc) and Sign(w2, ¬bc ∧ rc ∧ ¬yc).
The aim is to represent formulas such as Bel(a, Sign(b, ϕ0)) or, in a more general way Bel(a, ϕ0), which respectively stands for agent a believes that agent b signs ϕ0 and agent a believes ϕ0. As for signatures, we use an accessibility relation denoted Ba to represent the possible belief states of agent a.
We assume that signed statements represent the rationales for beliefs. That is, if agent a believes ϕ0 it is because some signed statement Sign(b, ϕ0) holds in every possible belief state of agent a and agent a is willing to commit to this signed statement. Let a, b and c be three agents and p be a propositional symbol; Figure 1 illustrates the possible belief states of agent a w.r.t. some initial state w0 using accessibility relation Ba (if p holds in a state, p is mentioned between brackets). Agent a considers two possible belief states, w1 and w2. In state w1, the two possible states given by Sb contain p which entails that p is signed by b. On the other hand, the two possible states given by Sc contain p and ¬p: no information can be signed by agent c. In all states related to w2 with Sb and Sc, p is true. From this figure we can conclude that in state w0 Sc Sb agent a believes that p is signed by b that is Bel(a, Sign(b, p)) while it does not believe that p or ¬p is signed by c. Since p is signed by b and agent c says nothing about p, agent a should believe p: Bel(a, p). Hence, it follows that in order to prevent adoption of inconsistent statements, hereafter we will assume that signed statements are always consistent (and thus relation Sa is serial).
Notice that the way we consider the link between beliefs
and signed statements differs from the way this link is defined
in [
tioned, we assume that the detective is willing to adopt as belief statements signed by the witnesses: Bel(po, Sign(w1, bc ∧ ¬rc ∧ ¬yc)) and Bel(po, Sign(w2, ¬bc ∧ rc ∧ ¬yc)). Since both witnesses agree on ¬yc, agent po also adopts as belief ¬yc.
In order to know how to handle mutually inconsistent
signed statements, agents consider extra information stating
which signed statement they prefer. Agents may determine
themselves their preferences by considering the sources of
information [
Sc Sb w0 w3 Ba Ba
Sb b < c (p) Sc w1
Sb (p) b < cw2
Sc Sc w24
In this paper, for the sake of conciseness and following
numerous contributions such as [
That is, if agent a believes that b is more reliable than c, then agent a adopts statement p as a belief even if agent c has signed ¬p. Suppose that reliability is represented with the help of a pre-order relation (or <): a b stands for a is at least as reliable as b. In semi formal terms, we get that:
Bel(a, (Sign(b, p) ∧ Sign(c, ¬p) ∧ b < c)) ⇒ Bel(a, p)
It follows that in each state, we do not only consider the value
of propositional symbols but also a pre-order relation which
characterizes a reliability order over information sources.
Using extra-information on reliability and by considering signed
statements rather than statements, the problem of belief change
[
pose agent po considers that the first witness is at least as reliable as the second one and he is himself willing to adopt as belief the signed statements issued by the two witnesses, i.e. we have the following belief:
Bel(po, w1 w2 po)
previously given, the police detective should believe that the blue car (bc) has caused the accident. Notice that the willingness attitude is translated in terms of preferences: po has no opinion and considers as more important information provided by w1 and w2.
Dynamics is viewed as restriction on agents’ belief states.
We interpret the tell performative as a private announcement
[
Sc Sb w0 Ba Ba (p) w1
Sb Sb Sc
Sb Sc w2 Sc (p) w11 (p) w12 w21 w22 (p) tell(c,a,p)
Sc Sb w0 Ba (p) w1
Sb Sb Sc
Sb Sc w2 Sc (p) w11 (p) w12 w21
(p) w22 Example 5 In the context of our motivating example, the dynamics is represented by the sequence of interviews. For instance, agent po interviews at first w1, action represented by T ell(w1, po, bc ∧ ¬rc ∧ ¬yc) and then interviews the second witness (T ell(w2, po, ¬bc ∧ rc ∧ ¬yc)). After these two announcements, the detective believes: Bel(po, Sign(w1, bc ∧ ¬rc ∧ ¬yc)) and Bel(po, Sign(¬bc ∧ rc ∧ ¬yc)).
The proposed language for reasoning about signatures, beliefs and preferences is a restricted first order language which enables quantification over agent ids. In this section, we focus on these three notions, tell actions will be introduced later. Quantification allows agents to reason about anonymous signatures. For the sake of conciseness, we restrict signed statements to propositional statements. Let L0 be the propositional language built over a set of propositional symbols P and L be the logical language. Language L is based on doxastic logic. Modal operator Bel represents beliefs: Bel(a, ϕ) means agent a believes L-formula ϕ. Modal operator Sign represents signed statements: Sign(t, ϕ0) means t (an agent id or a variable of the agent sort) signs propositional statement ϕ0. In order to represent agent’s opinion about reliability, we introduce the notation a b which stands for: agent a is said to be at least as reliable as b.
Definition 1 (Syntax of L) Let P be a finite set of propositional symbols. Let A be a finite set of agent ids. Let V be a set of variables s.t. A ∩ V = ∅. Let T = A ∪ V be the set of agent terms. The set of formulas of the language L is defined by the following BNF: ϕ ::= p | ¬ϕ | ϕ ∧ ϕ | Sign(t, ϕ0) | Bel(a, ϕ) | ∀xϕ | t t′ Writing a < b stands for a is strictly more reliable than b: a b ∧ ¬(b a). Writing a ∼ b means that a and b are equally reliable. Operators → and ∃ are used according to their usual meaning.
The semantics of L-formulas is defined in terms of
possible states and relations between states [
Definition 2 (Model) Let M be a model defined as a tuple: )W, Si, Bi, I, *+ i∈A
i∈A where W is a set of possible states. Si ∈ W × W is an accessibility relation representing signatures, Bi ∈ W × W is an accessibility relation representing beliefs. I is an interpretation function of the propositional symbols w.r.t. each possible state, I : W × P -→ {0, 1}. * is a function which represents total pre-orders; these pre-orders are specific to each state, that is *: W -→ 2A×A.
A variable assignment is a function v which maps every variable x to an agent id. A t-alternative v′ of v is a variable assignment similar to v for every variable except t. For t ∈ T , [[t]]v belongs to A and refers to the assignment of agent terms w.r.t. variable assignment v, such that: if t ∈ A then [[t]]v = t if t ∈ V then [[t]]v = v(t) We define the satisfaction relation |= with respect to some model M , state w and variable assignment v as follows. Definition 3 (|=) Let M be a model and v be a variable assignment: v : V → A. M satisfies an L-formula ϕ w.r.t. a variable assignment v and a state w, according to the following rules: • M, v, w |= t t′ iff ([[t]]v, [[t′]]v) ∈* (w). • M, v, w |= p iff p ∈ P and I(w, p) = 1. • M, v, w |= Sign(t, ϕ0) iff M, v, w′ |= ϕ0 for all w′ s.t.
(w, w′) ∈ S[ t] v • M, v, w |= Bel(a, ϕ) iff M, v, w′ |= ϕ for all w′ s.t.
(w, w′) ∈ Ba • M, v, w |= ∀tϕ iff for every t-alternative v′, M, v′, w |= ϕ.
We write |= ϕ iff for all M , w and v, we have M, v, w |= ϕ. The semantics for operators ¬, →, ∨, ∧ and ∃ is defined in the standard way. Let us now detail the constraints that should operate on the model. We only require that signature has to be consistent which entails that all relations Si have to be serial. Belief operator is a K45 operator and thus all Bi are transitive and euclidian. Interwoven relations between signatures and beliefs are detailed in the next section.
every agent holds belief about reliability without any
uncertainty. That is, agent’s beliefs about reliability can be
represented as a total pre-order. However, it does not mean
that we consider a fixed notion of reliability: we propose to
handle multiple pre-orders by indexing reliability with worlds.
That is, in each possible world or believable world, an agent
considers how it ranks the agents. In that context, each rank is
considered as a possible rank and thus it is natural that each of
them should be total. However, we enforce a stronger notion
(KS) Sign(a, ϕ0 → ψ0) → (Sign(a, ϕ0) → Sign(a, ψ0))
(DS) Sign(a, ϕ0) → ¬Sign(a, ¬ϕ0)
(KB) Bel(a, ϕ → ψ) → (Bel(a, ϕ) → Bel(a, ψ))
(4B) Bel(a, ϕ) → Bel(a, Bel(a, ϕ))
(5B) ¬Bel(a, ϕ) → Bel(a, ¬Bel(a, ϕ))
(R) t t
(T r) t t′ ∧ t′ t′′ → t t′′
(T) t t′ ∨ t′ t
(T o) Bel(a, t t′) ∨ Bel(a, t′ t)
(M P ) From ϕ and ϕ → ψ infer ψ
(G) From ϕ infer ∀tϕ
(NS) From ϕ0 infer Sign(t, ϕ0)
(NB) From ϕ infer Bel(a, ϕ)
of totality which states that the aggregation of all believable
ranks over agents (which are total) leads to a total preorder.
This will then help the agent to integrate all signed statements.
In other words, we require that the integration (or merging)
of signed statements should be based on an underlying total
preorder over statements (as it is commonly assumed in the
belief revision and merging areas—see [
The first constraint enforces that pre-orders are total in all states; the second constraint expresses that totality should hold in all belief states. Moreover, preorder definition entails that reflexivity and transitivity hold.
Let us now translate these constraints in terms of proof theory. Axiomatization of logic L includes all tautologies of propositional calculus. Table I details the axioms and inference rules describing the behavior of belief, signed statement and reliability. Notice axiom schema (T o) which reflects that reliability relations have to be believed as total. Let ⊢ denotes the proof relation. We conclude by giving results about soundness and completeness.
There are multiple ways to switch from information to
beliefs. These different ways may follow principles issued
from the belief merging principle [
Perrussel/lads2010-long.pdf. believe in information they provide. This is a key issue when information is propagated from one agent to another. At some stage, an agent may just broadcast some information without committing to that information in terms of belief.
A common and rational way to proceed is to consider as belief all non mutually inconsistent signed statements. All signed statements are considered in an incremental way, that is “ from the most reliable to the less reliable statements”. To describe the signed statements adoption stage, we first characterize agents which are equally reliable. Agents can be ranked since we always consider a total preorder; agents which are equally can be gathered in a same group. Each group can then be ranked. Let us at first characterize the most reliable set of agents; this set is denoted as C1:
a ∈ C1 =def ∀t(a t) The formula characterizing members of C1 can then be used for characterizing membership to a set Ci such that i > 1.
a ∈ Ci =def (¬(a ∈ Ci−1) ∧ ∀t¬(t ∈ Ci−1)) → (a t) Hence, all agents belonging to a set Ci are equally reliable and for all a ∈ Ci, b ∈ Cj if i <N j then a b. Next, the following definition stands for each agent tk belonging to some specific set Ci believes statement ϕk:
0 Sign(tk, φ0k) =def
(tk ∈ Ci) → Sign(tk, φ0k) tk∈Ci
tk∈A Using these shortcuts, we can now describe the merging process. The following axiom states that if a propositional statement ϕ0 is believed by agent a if the conjunction of the statements signed by the agents belonging to the same set Ci entails ϕ0 is believed by agent a (line 1), if statement ¬ϕ0 is not already believed by a(line 2) and ¬ϕ0 cannot be entailed with the help of statements signed by agents which are at least as reliable as agents belonging to Ci (line 3).
(Bel(a,
Sign(tk, ϕ0k)) ∧ Bel(a, ϕ0k → ϕ0)∧ tk∈Ci ( 0<j<i ¬Bel(a, tl∈Cj ¬Bel(a, ¬ϕ0)∧
Sign(tl, ϕl0) ∧
ϕl0 → ¬ϕ0))) → Bel(a, ϕ0) (IB) In terms of semantics, it means that, w.r.t. some initial state w0, all belief states are related to some signed states. Hence, it requires to consider the state’s interpretation, that is to express the relation by using worlds, i.e. a state and its associated interpretation. We represent a world as a set of propositional symbols, symbols that hold in the associated state. Let w be a state and [w] the associated world:
[w] = {p|I(w, p) = 1} In a more general way, if W is a set of states, then [W ] denotes the set of associated worlds. At first, from the belief states, we rank agent ids based on reliability relations believed by the agent. Suppose an agent a and a world w0; using relation Ba, we extract the total preorder representing reliability relation believed by agent a at w0. Notice that the constraints shown section III-A1 ensures that this preorder is total and thus agents ids could be ranked for building a partition of set of agents. Let C be a partition of A such that in every set Ci of C, all agents are equally reliable and for all a ∈ Ci, b ∈ Cj if i <N j then a ≺ b. Second, from each set Ci, we consider common information, that is statements that are signed by every agents belonging to Ci. Let [Ci]w0 be the set of worlds commonly signed by all agents belonging to Ci and related to w0: [Ci]w0 = ! {[w] | (w0, w) ∈ Sa} a∈Ci Next all sets of worlds [Ci]w0 are merged in a consistent way, the resulting set of worlds is denoted as reliable worlds. By consistent way, we mean an incremental process which considers as reliable worlds at first the whole set of possible worlds [W ]. Next for each part Ci, the set of reliable worlds is intersected with [Ci]w0 only if it does not lead to an empty set, i.e. an inconsistent result.
Definition 4 (Reliable worlds) Let M be a model and w0 a state such that w0 ∈ W . The set of reliable worlds Ωw0 is defined in an incremental way such that: • Ω0 = [W ] • Ωi = Ωi−1 ∩ [Ci]w0 if Ωi−1 ∩ [Ci]w0 1= ∅ and i > 0 • Ωi = Ωi−1 if Ωi−1 ∩ [Ci]w0 = ∅ and i > 0 The resulting set Ωw0 is equal to Ωk such that k = |C|. Since the sets of worlds and agents are finite, we do not have to consider the infinite case. Reliable worlds represent information that should be actually believed. Let us consider agent a and an initial world w0; from w0, we extract the belief states, and from these belief states, the set of reliable worlds. Beliefs of agent a are rational if all its believed worlds are included in its set of reliable worlds:
(w0,w)∈Ba
In the previous section, we have detailed a policy for building belief based on signed information. This policy considers belief and signed information from a static point of view. Let us now consider a more dynamic view by introducing actions of the form “agent a tells to agent b that a certain fact ϕ0 is true” (alias tell actions). This kind of action ensures that agent b will believes that agent a signs p, that is, a tell action is responsible for updating an agent’s beliefs about other agents’ signatures and, consequently, for the agent’s acquisition of new information and for updating the agent’s beliefs about objective facts. We note tell actions by Tell(a, b, ϕ0). Let LT be the extended language which embeds tell statements.
ϕ ::=p | ¬ϕ | ϕ ∧ ϕ′ | Sign(t, ϕ0) | Bel(a, ϕ) |
∀xϕ | t t′ | [Tell(a, b, ϕ0)]ϕ In other terms, LT just extends L with dynamic operators [Tell(a, b, ϕ0)]. The intuitive meaning of statement [Tell(a, b, ϕ0)]ϕ is after a tells ϕ0 to b, ϕ holds.
The truth conditions are those given above for the formulas
p, ¬ϕ, ϕ ∧ ϕ′, Sign(t, ϕ0), Bel(a, ϕ), ∀xϕ, t t′ and
[Tell(a, b, ϕ0)]ϕ. The truth condition for [Tell(a, b, ϕ0)]ϕ is
defined in a way which is closed to the semantics of dynamic
epistemic logic [
• M, v, w |= [Tell(a, b, ϕ0)]ϕ iff M |#a,b,ϕ0$, v, w1 |= ϕ. M |#a,b,ϕ0$ = )W ∗, "i∈A Si∗, "i∈A Bi∗, I∗, *∗+ is defined as follows: • W ∗ = {w1|w ∈ W } ∪ {w2|w ∈ W }; • Bb∗ = {(w1, w1′)|(w, w′) ∈ Bb and M, v, w′ |= Sign(a, ϕ0)} ∪ {(w2, w2′)|(w, w′) ∈ Bb}; • Bi∗ = {(w1, w2′)|(w, w′) ∈ Bi}∪
{(w2, w2′)|(w, w′) ∈ Bi} for all i ∈ A such that i 1= b; • Si∗ = {(w1, w2′)|(w, w′) ∈ Si}∪
{(w2, w2′)|(w, w′) ∈ Si} for all i ∈ A; • *∗ (w1) =*∗ (w2) =* (w) for all w ∈ W ; • I∗(w1, p) = I∗(w2, p) = I(w, p) for all w ∈ W . Basically, the effect of a’s action of telling to b that ϕ0 is to shrink the set of belief accessible states for b to the states in which a signs ϕ0, while keeping constant the set of belief accessible states for all other agents. Note that a’s action of (TAP ) [Tell(a, b, ϕ0)]p ↔ p (TN ) [Tell(a, b, ϕ0)]¬ϕ ↔ ¬[Tell(a, b, ϕ0)]ϕ (TC ) [Tell(a, b, ϕ0)](ϕ ∧ ϕ′) ↔
([Tell(a, b, ϕ0)]ϕ ∧ [Tell(a, b, ϕ0)]ϕ′) (TB) [Tell(a, b, ϕ0)]Bel(b, ϕ) ↔
Bel(b, (Sign(a, ϕ0) → [Tell(a, b, ϕ0)]ϕ)) (TB= ) [Tell(a, b, ϕ0)]Bel(i, ϕ) ↔ Bel(i, ϕ) if i %= b (TS) [Tell(a, b, ϕ0)]Sign(t, ϕ′0) ↔ Sign(t, ϕ′0) (T≤) [Tell(a, b, ϕ0)](t ≤ t′) ↔ (t ≤ t′) (T∀) [Tell(a, b, ϕ0)]∀xϕ ↔ ∀x[Tell(a, b, ϕ0)]ϕ telling to b that ϕ0 also keeps constant agents’ signatures and the reliability order over agents.
model.
Theorem 4 If M is a L-model in which constraint IB holds then M |#a,b,ϕ0$ is also a L-model in which constraint IB holds.
Let us now focus on the axiomatics of the logic LT . Table II details the reduction axioms describing the behavior of the operator [Tell(a, b, ϕ0)]. (TAP ) denotes the atomic permanence, (TN ) denotes negation handling, and (TC ) denotes conjunction handling. (TB ) describes the interplay between a tell action and the beliefs of the message receiver. (TB= ) describes the interplay between a tell action and the beliefs of all agents different from the message receiver. In particular, (TB= ) highlights the permanence of the beliefs of all agents different from the message receiver. (TS ) describes signature permanence, (T≤) describes preferences permanence, and (T∀) describes the interplay between tell action and quantification over variable assignments.
We then state the theorem about completeness of the logic LT .
ciples of the logic L together with the schemata in Table II and the rule of replacement of proved equivalence.
We write ⊢T to denote the proof relation for the logic LT determined by the principles of the logic L, the schemata in table II and the rule of replacement of proved equivalence.
For instance, the following theorem of the logic LT captures the essential aspect of the tell action. It says that, after agent a tells to agent b information ϕ0, agent b believes that agent a signs ϕ0:
⊢T [Tell(a, b, ϕ0)]Bel(b, Sign(a, ϕ0)) Once agent b starts to believe that agent a signs ϕ0 (as an effect of a’s act of telling to b that ϕ0), agent b might also start to believe that ϕ0. As we have shown above, this depends on the reliability of agent a according to agent b and on principles linking signatures with beliefs such as principle (IB).
represent in the system ⊢T , how agent po concludes that the blue car has caused the collision. At first, assume that (IB).
⊢T [Tell(w1, po, bc)][Tell(w2, po, ¬bc)]Bel(po, w1 w2)
⊢T [Tell(w1, po, bc)][Tell(w2, po, bc)] Bel(po, Sign(w1, bc) ∧ Sign(w2, ¬bc))
⊢T [Tell(w1, po, ¬bc∧rc)][Tell(w1, po, bc∧¬rc)]Bel(po, bc)
In this paper we have shown how information and its
source can be processed by an agent so that at first, it just
acquires information from sensors or other agents and second,
it builds its belief state by considering signed information. By
splitting information and belief, an agent is able to handle
clear rationales to construct its belief state both from a
static and dynamic perspectives. From a static perspective we
have applied our formal framework to characterize a possible
attitude for agents in the process of building their belief
state from the basic signed information they hold. From this
perspective this work is close to what has been done in belief
merging [
Concerning the dynamic perspective we have shown how
the basic signed information held by an agent may change as
it receives tell statements from another agent processed in a
similar way to private announcements in the sense of dynamic
epistemic logic (DEL) [
Our short term goal is to consider more sophisticated ways
to set the reliability relations. That is, our aim is to consider
agent skills [