PhD Project 16

The Game of Language: Complex Communication and Mental States

PhD-candidate: Iris van de Pol
PIs: Johan van Benthem (WP2)  and Ivan Toni (WP1)
Start date: 01 April 2015

(last update 2019-06-27)

Research Content

Humans can communicate about factual states of the world, and can also convey and interpret information about mental states. Everyday communication largely depends on this ability to represent, to strategize, and to act upon information about mental states of other people. Using interactive game-theoretical scenarios, this project combines two levels of investigation: logic-based models to capture the structure and the complexity of reasoning about mental states underlying communication, and cognitive research to define the cognitive mechanisms supporting those complexity demands. In particular, this project uses a variety of formal tools and measures to study the complexity of communication, meaning, and reasoning and applies this in various domains such as theory of mind, novel conventions, deductive games, and semantic universals.


Parameterized Complexity of Theory of Mind Reasoning in Dynamic Epistemic Logic
Team members: Van de Pol, Van Rooij, and Szymanik

Theory of mind refers to the human capacity for reasoning about others’ mental states based on observations of their actions and unfolding events. This type of reasoning is notorious in the cognitive science literature for its presumed computational intractability. A possible reason could be that it may involve higher-order thinking (e.g., ‘you believe that I believe that you believe’). To investigate this, this project formalizes theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’

Overview of the parameterized complexity results for the different parameterizations of DBU, and the line between fp-tractability and fp-intratractability. For the readability of this illustration, this graph describes the case where {a, c, p}-DBU and {c, f, p, u}-DBU are fp-tractable, which we leave as open problems.

This project proves that theory of mind reasoning, so formalized, indeed is intractable (specifically, PSPACE-complete). Using parameterized complexity, this project proves, however, that the ‘order parameter’ is not a source of intractability. Furthermore, a set of alternative parameters is considered and it is investigated which of them are sources of intractability. Implications of these results are discussed for the understanding of theory of mind.
This project combines techniques from several different disciplines, such as computational complexity theory, dynamic epistemic logic, and computational-level analysis to arrive at the first mathematical proofs about the complexity of higher-order theory of mind, which is a long standing question in philosophy and cognitive science. Understanding the complexity of theory of mind is crucial to understanding pragmatic communication. This project is a showcase for how logic and complexity theory can be used to address questions in cognitive science.

Progress 2018

A Dynamic Epistemic Logic model for the educational game Deductive Mastermind and complexity results based on this model that predicted cognitive difficulty of playing different game items was presented together with Master of Logic student Zhao at the annual meeting of the Cognitive Science Society, 2018. A formal framework was prepared for studying the speed and combinatorics of converging on novel conventions in the tacit communication task. A project was set up to investigate the complexity of quantifiers in the context of explaining semantic universals in the domain of quantifiers.

Groundbreaking characteristics

This project brings tools from the formal study of logic and computer science to cognitive neuroscience of human communication. The fact that it investigates how much higher-order knowledge of what the other participants of the conversation believe and desire is required for successful communication is highly innovative.