We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to (...) be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)

This article takes off from Johan van Benthem’s ruminations on the interface between logic and cognitive science in his position paper “Logic and reasoning: Do the facts matter?”. When trying to answer Van Benthem’s question whether logic can be fruitfully combined with psychological experiments, this article focuses on a specific domain of reasoning, namely higher-order social cognition, including attributions such as “Bob knows that Alice knows that he wrote a novel under pseudonym”. For intelligent interaction, it is important that the (...) participants recursively model the mental states of other agents. Otherwise, an international negotiation may fail, even when it has potential for a win-win solution, and in a time-critical rescue mission, a software agent may depend on a teammate’s action that never materializes. First a survey is presented of past and current research on higher-order social cognition, from the various viewpoints of logic, artificial intelligence, and psychology. Do people actually reason about each other’s knowledge in the way proscribed by epistemic logic? And if not, how can logic and cognitive science productively work together to construct more realistic models of human reasoning about other minds? The paper ends with a delineation of possible avenues for future research, aiming to provide a better understanding of higher-order social reasoning. The methodology is based on a combination of experimental research, logic, computational cognitive models, and agent-based evolutionary models. Keywords Epistemic logic - Cognitive science - Intelligent interaction - Cognitive modeling. (shrink)

This article takes off from Johan van Benthem’s ruminations on the interface between logic and cognitive science in his position paper “Logic and reasoning: Do the facts matter?”. When trying to answer Van Benthem’s question whether logic can be fruitfully combined with psychological experiments, this article focuses on a specific domain of reasoning, namely higher-order social cognition, including attributions such as “Bob knows that Alice knows that he wrote a novel under pseudonym”. For intelligent interaction, it is important that the (...) participants recursively model the mental states of other agents. Otherwise, an international negotiation may fail, even when it has potential for a win-win solution, and in a time-critical rescue mission, a software agent may depend on a teammate’s action that never materializes. First a survey is presented of past and current research on higher-order social cognition, from the various viewpoints of logic, artificial intelligence, and psychology. Do people actually reason about each other’s knowledge in the way proscribed by epistemic logic? And if not, how can logic and cognitive science productively work together to construct more realistic models of human reasoning about other minds? The paper ends with a delineation of possible avenues for future research, aiming to provide a better understanding of higher-order social reasoning. The methodology is based on a combination of experimental research, logic, computational cognitive models, and agent-based evolutionary models. (shrink)

Theory-of-mind (ToM) involves modeling an individual’s mental states to plan one’s action and to anticipate others’ actions through recursive reasoning that may be myopic (with limited recursion) or predictive (with full recursion). ToM recursion was examined using a series of two-player, sequential-move matrix games with a maximum of three steps. Participants were assigned the role of Player I, controlling the initial and the last step, or of Player II, controlling the second step. Appropriate for the assigned role, participants either anticipated (...) or planned Player II’s strategy at the second step, and then determined Player I’s optimal strategy at the first step. Participants more readily used predictive reasoning as Player II (i.e., planning one’s own move) than as Player I (i.e., anticipating an opponent’s move), although they did not differ when translating reasoning outcome about the second step to optimal action in the first step. Perspective-taking influenced likelihood of predictive reasoning, but it did not affect the rate at which participants acquired it during the experimental block. We conclude that the depth of ToM recursion (related to perspective-taking mechanisms) and rational application of belief–desire to action (instrumental rationality) constitute separate cognitive processes in ToM reasoning. (shrink)

In everyday life it is often important to have a mental model of the knowledge, beliefs, desires, and intentions of other people. Sometimes it is even useful to to have a correct model of their model of our own mental states: a second-order Theory of Mind. In order to investigate to what extent adults use and acquire complex skills and strategies in the domains of Theory of Mind and the related skill of natural language use, we conducted an experiment. It (...) was based on a strategic game of imperfect information, in which it was beneficial for participants to have a good mental model of their opponent, and more specifically, to use second-order Theory of Mind. It was also beneficial for them to be aware of pragmatic inferences and of the possibility to choose between logical and pragmatic language use. We found that most participants did not seem to acquire these complex skills during the experiment when being exposed to the game for a number of different trials. Nevertheless, some participants did make use of advanced cognitive skills such as second-order Theory of Mind and appropriate choices between logical and pragmatic language use from the beginning. Thus, the results differ markedly from previous research. (shrink)

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. To investigate this we formalize theory of mind reasoning as updating of beliefs about beliefs using dynamic epistemic logic, as this formalism allows to parameterize ‘order of thinking.’ We prove that (...) theory of mind reasoning, so formalized, indeed is intractable. Using parameterized complexity we prove, however, that the ‘order parameter’ is not a source of intractability. We furthermore consider a set of alternative parameters and investigate which of them are sources of intractability. We discuss the implications of these results for the understanding of theory of mind. (shrink)

Editors van Ditmarsch, Hendriks and Verbrugge of this special issue of topiCS on lying describe some recent trends in research on lying from a multidisciplinary perspective, including logic, philosophy, linguistics, psychology, cognitive science, behavioral economics, and artificial intelligence. Furthermore, they outline the seven contributions to this special issue.

Strategic games require reasoning about other people’s and one’s own beliefs or intentions. Although they have clear commonalities with psychological tests of theory of mind, they are not clearly related to theory of mind tests for children between 9 and 10 years of age “Flobbe et al. J Logic Language Inform 17(4):417–442 (2008)”. We studied children’s (5–12 years of age) individual differences in how they played a strategic game by analyzing the strategies that they applied in a zero, first, and (...) second-order reasoning task. For the zero-order task, we found two subgroups with different accuracy levels. For the first-order task, subgroups of children applied different suboptimal strategies or an optimal strategy. For the second-order task only suboptimal strategies were present. Strategy use for all tasks was related to age. The 5- and 6-year old children were additionally tested on theory of mind understanding and executive functioning. Strategy-use in these children was related to working memory, but not to theory of mind after correction for age, verbal ability and general IQ. (shrink)

Upon hearing “Some of Michelangelo’s sculptures are in Rome,” adults can easily generate a scalar implicature and infer that the intended meaning of the utterance corresponds to “Some but not all Michelangelo’s sculptures are in Rome.” Comprehension experiments show that preschoolers struggle with this kind of inference until at least 5 years of age. Surprisingly, the few studies having investigated children’s production of scalar expressions like some and all suggest that production is adult-like already in their third year of life. (...) Thus, children’s production of implicatures seems to develop at least 2 years before their comprehension of implicatures. In this paper, we present a novel account of scalar implicature generation in the framework of Bidirectional Optimality Theory: the Asymmetry Account. We show that the production–comprehension asymmetry is predicted to emerge because the comprehension of some requires the hearer to consider the speaker’s perspective, but the production of some does not require the speaker to consider the hearer’s perspective. Hence, children’s comprehension of scalar expressions, but not their production of scalar expressions, is predicted to be related to their theory of mind development. Not possessing fully developed theory of mind abilities yet, children thus have difficulty in comprehending scalar expressions such as some in an adult-like way. Our account also explains why variable performance is found in experimental studies testing children’s ability to generate scalar implicatures; moreover, it describes the differences between children’s and adults’ implicature generation in terms of their ability to recursively apply theory of mind; finally, it sheds new light on the question why the interpretation of numerals does not require implicature generation. (shrink)

Behavior oftentimes allows for many possible interpretations in terms of mental states, such as goals, beliefs, desires, and intentions. Reasoning about the relation between behavior and mental states is therefore considered to be an effortful process. We argue that people use simple strategies to deal with high cognitive demands of mental state inference. To test this hypothesis, we developed a computational cognitive model, which was able to simulate previous empirical findings: In two-player games, people apply simple strategies at first. They (...) only start revising their strategies when these do not pay off. The model could simulate these findings by recursively attributing its own problem solving skills to the other player, thus increasing the complexity of its own inferences. The model was validated by means of a comparison with findings from a developmental study in which the children demonstrated similar strategic developments. (shrink)

Behavior oftentimes allows for many possible interpretations in terms of mental states, such as goals, beliefs, desires, and intentions. Reasoning about the relation between behavior and mental states is therefore considered to be an effortful process. We argue that people use simple strategies to deal with high cognitive demands of mental state inference. To test this hypothesis, we developed a computational cognitive model, which was able to simulate previous empirical findings: In two-player games, people apply simple strategies at first. They (...) only start revising their strategies when these do not pay off. The model could simulate these findings by recursively attributing its own problem solving skills to the other player, thus increasing the complexity of its own inferences. The model was validated by means of a comparison with findings from a developmental study in which the children demonstrated similar strategic developments. (shrink)

Behavior oftentimes allows for many possible interpretations in terms of mental states, such as goals, beliefs, desires, and intentions. Reasoning about the relation between behavior and mental states is therefore considered to be an effortful process. We argue that people use simple strategies to deal with high cognitive demands of mental state inference. To test this hypothesis, we developed a computational cognitive model, which was able to simulate previous empirical findings: In two-player games, people apply simple strategies at first. They (...) only start revising their strategies when these do not pay off. The model could simulate these findings by recursively attributing its own problem solving skills to the other player, thus increasing the complexity of its own inferences. The model was validated by means of a comparison with findings from a developmental study in which the children demonstrated similar strategic developments. (shrink)

We can understand and act upon the beliefs of other people, even when these conflict with our own beliefs. Children’s development of this ability, known as Theory of Mind, typically happens around age 4. Research using a looking-time paradigm, however, established that toddlers at the age of 15 months old pass a non-verbal false-belief task (Onishi and Baillargeon in Science 308:255–258, 2005). This is well before the age at which children pass any of the verbal false-belief tasks. In this study (...) we present a more complex case of false-belief reasoning with older children. We tested second-order reasoning, probing children’s ability to handle the belief of one person about the belief of another person. We find just the opposite: 7-year-olds pass a verbal false-belief reasoning task, but fail on an equally complex low-verbal task. This finding suggests that language supports explicit reasoning about beliefs, perhaps by facilitating the cognitive system to keep track of beliefs attributed by people to other people. (shrink)

We can understand and act upon the beliefs of other people, even when these conflict with our own beliefs. Children’s development of this ability, known as Theory of Mind, typically happens around age 4. Research using a looking-time paradigm, however, established that toddlers at the age of 15 months old pass a non-verbal false-belief task (Onishi and Baillargeon in Science 308:255–258, 2005). This is well before the age at which children pass any of the verbal false-belief tasks. In this study (...) we present a more complex case of false-belief reasoning with older children. We tested second-order reasoning, probing children’s ability to handle the belief of one person about the belief of another person. We find just the opposite: 7-year-olds pass a verbal false-belief reasoning task, but fail on an equally complex low-verbal task. This finding suggests that language supports explicit reasoning about beliefs, perhaps by facilitating the cognitive system to keep track of beliefs attributed by people to other people. (shrink)

This paper presents an attempt to bridge the gap between logical and cognitive treatments of strategic reasoning in games. There have been extensive formal debates about the merits of the principle of backward induction among game theorists and logicians. Experimental economists and psychologists have shown that human subjects, perhaps due to their bounded resources, do not always follow the backward induction strategy, leading to unexpected outcomes. Recently, based on an eye-tracking study, it has turned out that even human subjects who (...) produce the outwardly correct ‘backward induction answer’ use a different internal reasoning strategy to achieve it. The paper presents a formal language to represent different strategies on a finer-grained level than was possible before. The language and its semantics help to precisely distinguish different cognitive reasoning strategies, that can then be tested on the basis of computational cognitive models and experiments with human subjects. The syntactic framework of the formal system provides a generic way of constructing computational cognitive models of the participants of the Marble Drop game. (shrink)

Editors van Ditmarsch, Hendriks and Verbrugge of this special issue of topiCS on lying describe some recent trends in research on lying from a multidisciplinary perspective, including logic, philosophy, linguistics, psychology, cognitive science, behavioral economics, and artificial intelligence. Furthermore, they outline the seven contributions to this special issue.

In recent years, the human ability to reasoning about mental states of others in order to explain and predict their behavior has come to be a highly active area of research. Researchers from a wide range of fields { from biology and psychology through linguistics to game theory and logic{ contribute new ideas and results. This interdisciplinary workshop, collocated with the Thirteenth International Conference on Theoretical Aspects of Rationality and Knowledge (TARK XIII), aims to shed light on models of social (...) reasoning that take into account realistic resource bounds. People reason about other people's mental states in order to understand and predict the others' behavior. This capability to reason about others' knowledge, beliefs and intentions is often referred to as theory of mind. Idealized rational agents are capable of recursion in their social reasoning, and can reason about phenomena like common knowledge. Such idealized social reasoning has been modeled by modal logics such as epistemic logic and BDI (belief, desire, intention) logics and by epistemic game theory. However, in real-world situations, many people seem to lose track of such recursive social reasoning after only a few levels. The workshop provides a forum for researchers that attempt to analyze, understand and model how resource-bounded agents reason about other minds. (shrink)

This chapter presents a new semantics for inductive empirical knowledge. The epistemic agent is represented concretely as a learner who processes new inputs through time and who forms new beliefs from those inputs by means of a concrete, computable learning program. The agent’s belief state is represented hyper-intensionally as a set of time-indexed sentences. Knowledge is interpreted as avoidance of error in the limit and as having converged to true belief from the present time onward. Familiar topics are re-examined within (...) the semantics, such as inductive skepticism, the logic of discovery, Duhem’s problem, the articulation of theories by auxiliary hypotheses, the role of serendipity in scientific knowledge, Fitch’s paradox, deductive closure of knowability, whether one can know inductively that one knows inductively, whether one can know inductively that one does not know inductively, and whether expert instruction can spread common inductive knowledge—as opposed to mere, true belief—through a community of gullible pupils. (shrink)