Communication between agents in dynamic epistemic logic_2

2025-04-27 0 0 547.25KB 42 页 10玖币

侵权投诉

arXiv:2210.04656v1 [cs.LO] 10 Oct 2022

Communication between agents in dynamic

epistemic logic *

Fernando R. Vel´azquez-Quesada

Department of Information Science and Media Studies, Universitetet i Bergen

Fernando.VelazquezQuesada@uib.no

Abstract

This manuscript studies actions of communication between epistemic

logic agents. It starts by looking into actions through which all/some agents

share all their information, deﬁning the model operation that transforms

the model, discussing its properties, introducing a modality for describing

it and providing an axiom system for the latter. The main part of the

manuscript focusses on an action through which some agents share part of

their information: they share all that they know about a topic deﬁned by

a given formula. Once again, the manuscript deﬁnes the model operation

that transforms the model, discusses its properties, introduces a modality

for describing it and provides an axiom system for the latter.

Keywords: epistemic logic ·distributed knowledge ·dynamic epistemic

logic ·full communication ·partial communication

1 Introduction

Epistemic logic (EL;Hintikka 1962) is a logical system for reasoning about the

knowledge a set of agents might have. On the syntactic side, its language ex-

tends propositional logic with a modality Kifor every agent i, with formulas

of the form Kiϕread as “agent iknows that ϕis the case”. On the semantic

side, it typically relies on relational ‘Kripke’ models, assigning to each agent

an indistinguishability relation among epistemic possibilities.1The crucial idea

is that knowledge is deﬁned in terms of uncertainty: agent iknows that ϕ

is the case when ϕholds in all situations she considers possible.2Despite its

simplicity (or maybe because of it), EL has become a widespread tool, contribut-

ing to the formal study of complex multi-agent epistemic notions in philosophy

(Hendricks 2006), computer science (Fagin et al. 1995,Meyer and van der Hoek

1995) and economics (de Bruin 2010,Perea 2012).

One of the reasons for the success of EL and its variations is that it al-

lows a natural representation of actions that aﬀect the agents’ information (e.g.,

*comm-2022-10-10-arXiv.tex,compiled 11th October 2022, 00:53. To appear in Revista Mexicana

de L´ogica 1(1).

1There are other alternatives; see Footnote 5.

2This is the “information as range” discussed in van Benthem and Mart´ınez (2008).

knowledge and beliefs). The two paradigmatic examples are public announce-

ments (Plaza 1989,Gerbrandy and Groeneveld 1997), representing the eﬀect of

agents receiving truthful information, and belief revision (van Ditmarsch 2005,

van Benthem 2007,Baltag and Smets 2008), representing actions of agents re-

ceiving information that is reliable and yet potentially fallible. These two frame-

worksarepart ofwhatis knownas dynamic epistemic logic (DEL;van Ditmarsch et al.

2008,van Benthem 2011), a ﬁeld whose main feature is that actions are se-

mantically represented not as relations (as done, e.g., in propositional dynamic

logic,Harel et al. 2000), but rather as operations that transform the underlying

semantic model.

The mentioned DEL frameworks have been used for representing commu-

nicationbetween agents (e.g., Ågotnes et al. 2010,van Ditmarsch 2014,Baltag and Smets

2013,Galimullin and Alechina 2017). Yet, they were originally designed to rep-

resent the eﬀect of external communication, with the information’s source being

some entity that is not part of the system. This can be observed by noti-

cing that, in these settings, the incoming information χdoes not need to be

known/believed by any of the involved agents.

This manuscript studies epistemic actions in which the information that is

being shared is information some of the agents already have. In this sense, the

actions studied here are true actions of inter-agent communication. For this, the

crucial notion is that of distributed knowledge (Hilpinen1977,Halpern and Moses

1984,1985,1990), representing what a group of agents would know by putting

all their information together. Distributed knowledge thus ‘pre-encodes’ the

information a group of agents would have if they were to share their individual

pieces. Then, the actions studied here can be seen as (variations of) actions

that fulﬁl this promise, doing so by deﬁning the model that is obtained after

communication takes place.

In deﬁning these communication actions, it is important to emphasise that,

under relational ‘Kripke’ models, epistemic logic deﬁnes knowledge in terms

of uncertainty. This is because these models only representthe epistemic uncer-

tainty of the agent, without ‘explaining’ why some uncertainty (i.e., epistemic

possibility) has been discarded and why some other remains. This has two

important consequences.

•First, as discussed in van der Hoek et al. (1999), distributed knowledge does

not satisfy the “principle of full communication”: there are situations in

which a group knows distributively a formula ϕ, and yet ϕdoes not follow

from the individual knowledge of the groups’ members. Thus, under rela-

tional models, distributed knowledge is better understood as what a group of

agents would know (in the “information as range” sense) if they indicated

to one another which epistemic possibilities they have already discarded.

•Second, recall that an agent’s uncertainty is represented by her indistin-

guishability relation. Thus, although changes in uncertainty can be repres-

ented by changing what each epistemic possibility describes (technically, by

changing the model’s atomic valuation), they are more naturally represen-

ted by changes in the relation itself.3

3Note that changing the model’s domain (removing worlds, as when representing public an-

nouncements, or adding them, as when representing non-public forms of communication) is an

indirect way of changing indistinguishability relations.

This text is organised as follows. Section 2 recalls the basics of EL, including

the semantic model representing the agents’ uncertainty, the formal language

used for describing them and an axiom system characterising validities. Then,

while Section 3 discusses communication actions through which all/some agents

share all their information with everybody (comparing them with proposals in

the literature), Section 4 discusses a novel action through which some agents

share part of their information with everybody. Section 5 is a brief discussion of

the issues arising when only some agents receive the shared information. Finally,

Section 6 summarises the work, discussing also further research lines. While

the proofs of propositions are found within the text, the proofs of theorems can

be found in the appendix.

2 Basic system

Throughout this text, let Abe a ﬁnite non-empty set of agents, and let Pbe a

non-empty enumerable set of atomic propositions.

Deﬁnition 2.1 (Multi-agent relational model) Amulti-agent relational model (or,

simply, a model) is a tuple M=hW,R,Viwhere W(also denoted as D(M))

is a non-empty set of objects called possible worlds,R={Ri⊆W×W|i∈A}

contains a binary indistinguishability relation on Wfor each agent in A, and

V:P→℘(W) is the atomic valuation indicating the set of possible worlds in

which each atom holds. The class of (multi-agent relational) models is denoted

by MA. A pair (M,w) with Min MAand w∈D(M) is called a pointed MAmodel

(or, simply, a pointed model), with wbeing the evaluation point.

Let M=hW,R,Vibe a model. For G⊆A, deﬁne RD

G:=Tk∈GRk, with edges

in RD

Gcalled G-edges. For S⊆W×Wand w∈W, deﬁne S(w) :={u∈W|Swu}.◭

Note: in a model, the indistinguishability relations are arbitrary binary

relations. In particular, they need to be neither reﬂexive nor symmetric nor

Euclidean nor transitive, and hence knowledge here is neither truthful nor

positively/negatively introspective. The notion of knowledge used here corres-

ponds simply to “what is true in all the agent’s epistemic possibilities”.

Pointed models are described by the following language.

Deﬁnition 2.2 (Language LD)Formulas ϕ, ψ of the language LDare given by

ϕ, ψ ::=p| ¬ϕ|ϕ∧ψ|DGϕ

for p∈Pand ∅ ⊂ G⊆A. Boolean constants (⊤,⊥) and other Boolean operators

(∨,→,↔) are deﬁned as usual. Additionally, deﬁne Kiϕ:=D{i}ϕ.◭

Note how LDcontains a modality DGfor each non-empty set of agents G⊆A,

thanks to which one can build formulas of the form DGϕ, read as “the agents

in Ghave distributed knowledge of ϕ”. Thus, Kiϕis read as “agent ihas

distributed knowledge of ϕ” or, in other words, “agent iknows ϕ”.

Formulas of LDare semantically interpreted in pointed models.

Deﬁnition 2.3 (Interpreting LDon pointed models) Let (M,w) be a pointed

model with M=hW,R,Vi. The satisﬁability relation between (M,w) and a

formula in LDis deﬁned inductively. Boolean cases are as usual; for the rest,

(M,w)piﬀdef w∈V(p),

(M,w)DGϕiﬀdef for all u∈W, if RD

Gwu then (M,u)ϕ.

A formula ϕis valid on MA(notation: ϕ) if and only if (M,w)ϕfor

every w∈D(M) of every Min MA. By deﬁning the truth-set of a formula as

ϕM:=w∈W|(M,w)ϕ(so ϕMis the set of ϕ-worlds in M, that is, the

worlds in Mwhere ϕholds), one can state equivalently that ϕis valid on MAif

and only if ϕM=D(M) for every Min MA.◭

The semantic interpretation of DGϕdeserves some comments. Recall: RD

is the intersection of the relations of agents in G. Thus, RD

Gwu holds if and only

if Riwu holds for every iin G, that is, if and only if every agent in Gconsiders

upossible when at wor, equivalently, if and only if no agent in Gcan discard

uwhen at w. Using the notation ~·, the semantic interpretation of DGϕis

equivalently stated as

(M,w)DGϕiﬀRD

G(w)⊆ϕM.

Note also that the abbreviation Kiϕbehaves as expected:

(M,w)Kiϕiﬀ(M,w)D{i}ϕiﬀRD

{i}(w)⊆ϕMiﬀRi(w)⊆ϕM,

so agent iknows ϕat (M,w) if and only if every world she cannot distinguish

from wis a ϕ-world.

Example 2.1 Here are some examples of this setting.

(i) Take A={a,b,c}and P=p,q,r. Consider M1=h{w0,w1,w2,w3},R,Vi, a

model whose indistinguishability relations and valuation function are as in

the diagram below (each world shows exactly the atoms true at it); take w0

to be the evaluation point (double-circled in the diagram).

M1:

p,q,rw0

p,r

p,q

q,r

a,b,c

a,c

a,bb,c

a,b,c

At (M1,w0) all atoms are true; yet, no agent knows this. First, agent aknows

that pholds, but knows the truth value of neither qnor r:

(M1,w0)Kap∧(¬Kaq∧ ¬ Ka¬q)∧(¬Kar∧ ¬ Ka¬r).

Then, bknows that qholds, but knows the truth value of neither pnor r:

(M1,w0)(¬Kbp∧ ¬ Kb¬p)∧Kbq∧(¬Kbr∧ ¬ Kb¬r).

Finally, cknows that rholds, but knows the truth value of neither pnor q:

(M1,w0)(¬Kcp∧ ¬ Kc¬p)∧(¬Kcq∧ ¬ Kc¬q)∧Kcr.

Still, each agent knows that aknows p’s truth-value, that bknows q’s truth-

value, and that cknows r’s truth-value:

(M1,w0)^

i∈{a,b,c}

Ki(Kap∨Ka¬p)∧(Kbq∨Kb¬q)∧(Kcr∨Kc¬r).

Finally, agents would beneﬁt from sharing their individual information. In

particular, if they all shared, they would know which the real situation is:

(M1,w0)D{a,b}(p∧q)∧D{a,c}(p∧r)∧D{b,c}(q∧r)∧D{a,b,c}(p∧q∧r).

(ii) Let Aand Pbe as in Item (i); consider the pointed model depicted below.

M2:p,q,r

pw1

a,b,ca

a,b,c

Again, all atoms are true in the real situation; yet, no agent knows this. On

the one hand, aknows p∨qwithout knowing the truth-value of por q,

(M2,w0)Ka(p∨q)∧(¬Kap∧ ¬ Ka¬p)∧(¬Kaq∧ ¬ Ka¬q).

On the other hand, bknows q∨rwithout knowing the truth-value of qor r:

(M2,w0)Kb(q∨r)∧(¬Kbq∧ ¬ Kb¬q)∧(¬Kbr∧ ¬ Kb¬r).

Agent chas slightly more information, as she knows that qis true but still

ignores the truth-value of pand r:

(M2,w0)(¬Kcp∧ ¬ Kc¬p)∧Kcq∧(¬Kcr∧ ¬ Kc¬r).

This time, while communicating would help aand b, it would not help c.

In fact, collectively, the agents do not have enough information to ﬁnd out

which the real situation is:

(M2,w0)D{a,b}q∧D{a,c}q∧D{b,c}q∧ ¬ D{a,b,c}(p∧r).

(iii) Take A={a,b}and P=p,q; consider (M3,w0) depicted below.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.04656v1[cs.LO]10Oct2022Communicationbetweenagentsindynamicepistemiclogic*FernandoR.Vel´azquez-QuesadaDepartmentofInformationScienceandMediaStudies,UniversitetetiBergenFernando.VelazquezQuesada@uib.noAbstractThismanuscriptstudiesactionsofcommunicationbetweenepistemiclogicagents.Itstartsbyl...

展开>> 收起<<

Communication between agents in dynamic epistemic logic_2.pdf

共42页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Communication between agents in dynamic epistemic logic_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: