Time and place: Room S10, DTU meeting centre, building 101, 13.00-15.15 + drinks afterwards.
Host: Thomas Bolander
13.00-14.00 Iris van de Pol, PhD student, ILLC, University of Amsterdam. Complexity of Theory of Mind.
14.15-15.15 Jakub Szymanik, associate professor, ILLC, University of Amsterdam. Complexity of turn-based games.
Iris van de Pol. Complexity of Theory of Mind
In this talk I will discuss the complexity of theory of mind, which is the cognitive phenomenon that people attribute mental states to each other, like beliefs, desires, and intentions, and use these to predict or explain each other’s behavior. I present a computational-level model of theory of mind—based on dynamic epistemic logic—and analyze its (parameterized) complexity. In particular I show that the model is PSPACE-complete and that the modal depth of a formula does not influence its complexity.
This talk is based on my master’s thesis. For a pdf, see: http://goo.gl/21FG2G.
Jakub Szymanik. Complexity of turn-based games
Inspired by the logical analysis of backward induction and cognitive science experiments, we investigate the computational complexity of the reasoning in extensive form dynamic games. We formalize the computational complexity of a general decision problem the players face, assuming common knowledge of rationality. We show that such defined problem is PTIME-complete. Moreover, we provide a more refined analysis of the complexity of particular game trials which takes into account alternation type of the game and pay-off distribution. We conclude with some mathematical and cognitive open problems.
Please sign up for the talk at latest on 13 January, so I know how much beer and snacks to buy.
All are welcome! (Please distribute this email to any others you think might be interested).