Colloquium Multi-Agent Systems: Hans van Ditmarsch (CNRS and LORIA) and Yanjing Wang (Peking University)

---

TIME: 13:15-14:00 (Van Ditmarsch) and 14:15-15:00 (Wang)

Speaker 1: Hans van Ditmarsch (CNRS and Loria)

Title: Asynchronous announcements

Abstract:
We propose a multi-agent epistemic logic of asynchronous announcements, where truthful announcements are publicly sent but individually received by agents uncertain about atomic propositions describing the state of the world, and about each other's uncertainty. Additional to epistemic modalities, the logic therefore contains two types of dynamic modalities, namely for sending messages and for receiving messages. The semantics defines truth relative to the current state of reception of messages for all agents, where we assume that messages are received in the order in which they are being sent. What an agent knows is a function of her initial uncertainty and of the messages she has received so far. More precisely: after an announcement an agent knows that a proposition is true, if and only if on condition of the truth of that announcement, the agent knows that after that announcement and after any number of other agents also receiving it, the proposition is true. Knowledge need not be truthful, because some messages that were already sent may not yet have been received by the knowing agent, so that her knowledge may be outdated. Interestingly, messages that are announcements may result in partial synchronization, namely when an agent learns from receiving an announcement that prior announcements must already have been received by other agents.

We show that on multi-agent epistemic models (with arbitrary accessibility relations), each formula in asynchronous announcement logic is equivalent to a formula in basic multi-agent modal logic, and we provide a complete axiomatization, and also on the class of S5 models (for initial uncertainty of agents). We then determine the complexity of model checking and of satisfiability. As is maybe to be expected, your uncertainty about other agents having received messages increases the complexity of the logic in comparison to standard public announcement logic. This is joint work with Philippe Balbiani.

---

Speaker 2: Yanjing Wang (Peking University)

Title: Call me by your name: epistemic logic with assignments and non-rigid names

Abstract:
In standard epistemic logic, agent names are usually assumed to be common knowledge. This is unreasonable for various applications, in particular in social networks. Inspired by term modal logic and assignment operators in dynamic logic, we introduce a lightweight modal predicate logic whose names are not rigid. The language can handle various de dicto / de re distinctions in a natural way. We show the decidability of the logic over arbitrary and reflexive models and give a complete axiomatization over S5 models. This is joint work with Jeremy Seligman (to appear in AiML18).