M2 internship: Structural properties of Dynamic Epistemic Arenas

This internship subject is purely theoretical to provide a crucial understanding of phenomena arising in multi-agent systems analysis.
Multi-agent systems behaviours can be modelled by combining two ingredients (as proposed in Dynamic Epistemic Logic [vDvHK2007]):

1. Epistemic models, that we call “situations”, represent a static situation: these are graphs whose vertices are possible worlds and whose edges represent
2. Action models represent which actions can be performed in the current situation and how actions are perceived by agents.

On this basis, the resulting of applying an action model is obtained by computing an update of the current situation by a fairly simple operation.

Now, in order to reason about strategic abilities of agents, one has to analyse a multi-player game arena arising from an initial situation and arbitrary iterations of action models updates. Mathematically, this arena is a forest of infinite trees: a branch in a tree represents the sequence of executed actions and the cross-ways relations represent the imperfect information of agents about the history that has effectively taken place in the game.
With reference to [vDvHK2007] approach, We call this arena the “Dynamic Epistemic Arena” (DEA).

As shown in [Maubert1014] for a restricted case, DEA possess noticeable structural properties that fall into classic ones, widely studied in the literature, namely DEA are “automatic structures” [BG2000,KM2007,2007,R2008]. Automatic structures are infinite graphs with a finite presentation: the infinite set of vertices is provided by a regular language (hence a finite-state automaton) and the binary relations between vertices are described by synchronous transducers (a subclass of two-tape finite state automata). Form a logical perspective, automatic structures have a decidable first-order logic theory. Moreover, according to [Maubert2014], finer analysis of the DEA structures yields decidability of the existence of a sequence of actions (a strategy) to achieve a winning objective in the game. As a consequence, epistemic planning and epistemic protocol synthesis can be applied, with impacts for many relevant real life applications (robotics, web services, etc.).

The pioneer results of [Maubert2014] are however subject to severe restrictions on the kind of action models one is allowed to consider: preconditions of actions must be fully propositional, preventing the setting from considering some realistic pictures where agents act on the basis of their knowledge, acting only if e.g. knowing something, or knowing that another agent knows something, etc.

The subject of this internship is to study the trade-off between relaxing these restrictions and the ability to perform strategic reasoning.
The roadmap for this task is to have a clear picture of the DEA structural properties in the landscape of finitely-presentable structures and by determining which logical fragment of first-order logic but also second-order logic can be decided.

[vDvHK2007] Dynamic epistemic logic. H van Ditmarsch, W Van Der Hoek, B Kooi. Springer Verlag, 2007.
[Maubert2014] Chapter 7 of Logical foundations of games with imperfect information : uniform strategies. Bastien Maubert. PhD Université de Rennes 1, 2014.
[BG2000] Automatic Structures. Achim Blumensath, Erich Grädel. LICS 2000: 51-62
[KM2007] Three lectures on automatic structures. Khoussainov and M. Minnes. Tutorial lectures on automatic structures given
at the Logic Colloquium 2007, Wroclaw, Poland.
[B2007] Automatic presentations of infinite structures. Vince Bárány. RWTH Aachen University 2007, pp. 1-146
[R2008] Automata presenting structures: A survey of the finite string case. Sasha Rubin. Bull. Symbolic Logic Volume 14, Issue 2 (2008), 169-209.

Leave a Reply

Your email address will not be published.