Complexity of strategic reasoning under partial observability

  • Date October 30, 2017
  • Hour 2.30 PM
  • Speaker Sasha Rubin


There is a need for humans to be able to trust the decisions made by the Artificial Agents (AA) we interact with. This challenge cannot be met without having some formal guarantees on the behaviour of AA. Most practical scenarios involve multiple agents, each having partial information about the other agents.

We model such scenarios as finite-state, synchronous, perfect-recall multi-agent systems (MAS) with partial observability. Basic strategic reasoning in such MAS is long-known to be undecidable. I will advertise a class of systems in which all agent actions are public. This captures scenarios in which all agent communication is by broadcast (e.g., via shared bus, blackboard, or in face-to-face conversation), a phenomenon which is exhibited by a number of epistemic puzzles and games of imperfect information (e.g., battleships, poker, bridge). Moreover, this class can also simulate private communication between agents.

It is known that strategy synthesis of linear-temporal objectives is decidable for this class. I will show that one can handle much richer strategic-epistemic properties, including synthesising strategy-profiles that are in (e.g., Nash) equilibrium. I will argue that this class strikes a good balance between modelling power and computational complexity.