Jakub Szymanik - Multi-agent information exchange

Epistemic modal logics and their extensions are concerned with global and abstract problems in reasoning about information. They  are designed to model a wide range of epistemic scenarios so it is not surprising that there are many intractability and even undecidability results in the literature. In this talk, we zoom in into some epistemic reasoning and take a more agent-oriented perspective. Instead of investigating the complexity of a given logic that can be used to describe certain tasks in epistemic reasoning, we turn towards a complexity study of the concrete tasks themselves, determining what computational resources are needed in order to perform the required reasoning.

In particular, I will discuss two case studies of multi-agent information exchange in which agents successfully converge to knowledge on the basis of the information about the knowledge of others. First, I will present a generalization of the famous Muddy Children puzzle by allowing public announcements with arbitrary generalized quantifiers and propose a new concise logical modeling of the puzzle based on the number triangle representation of quantifiers. As a result I will be able to characterize the solvability of the puzzle with respect to the used public announcement. In a similar vein, I will also study the Top Hat puzzle. I observe that in this case an announcement needs to satisfy stronger conditions in order to guarantee solvability.