Why should moral philosophers, moral psychologists, and machine ethicists care about computational complexity? Debates on whether artificial intelligence (AI) can or should be used to solve problems in ethical domains have mainly been driven by what AI can or cannot do in terms of human capacities. In this paper, we tackle the problem from the other end by exploring what kind of moral machines are possible based on what computational systems can or cannot do. To do so, we analyze normative (...) ethics through the lens of computational complexity. First, we introduce computational complexity for the uninitiated reader and discuss how the complexity of ethical problems can be framed within Marr’s three levels of analysis. We then study a range of ethical problems based on consequentialism, deontology, and virtue ethics, with the aim of elucidating the complexity associated with the problems themselves (e.g., due to combinatorics, uncertainty, strategic dynamics), the computational methods employed (e.g., probability, logic, learning), and the available resources (e.g., time, knowledge, learning). The results indicate that most problems the normative frameworks pose lead to tractability issues in every category analyzed. Our investigation also provides several insights about the computational nature of normative ethics, including the differences between rule- and outcome-based moral strategies, and the implementation-variance with regard to moral resources. We then discuss the consequences complexity results have for the prospect of moral machines in virtue of the trade-off between optimality and efficiency. Finally, we elucidate how computational complexity can be used to inform both philosophical and cognitive-psychological research on human morality by advancing the moral tractability thesis. (shrink)

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)

Each day people are presented with circumstances that may require speculation. Scientists may ponder questions such as why a star is born or how rainbows are made, psychologists may ask social questions such as why people are prejudiced, and military strategists may imagine what the consequences of their actions might be. Speculations may lead to the generation of putative explanations called hypotheses. But it is by checking if hypotheses accurately reflect the encountered facts that lead to sensible behaviour demonstrating a (...) true understanding. If evidence shows a hypothesis to be false, then people should rationally abandon it, especially if there are negative consequences. The aim of this thesis is to examine how effectively people search for evidence in their hypothesis testing to test whether or not their hypotheses are true or false in competitive games. -/- Research findings from six studies of hypothesis testing behaviour in competitive deductive tasks are explored. Chapter by chapter the thesis tests how everyday people, and master chess players, tackle hypothesis testing in mathematical tasks, such as how to solve sequential number sequence puzzles when thinking about an opponent, or how to solve chess problems in a variety of contexts. The implications of the results are discussed in light of aspects of general cognition: such as reasoning, social hypothesis testing and planning. (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)

This commentary focuses on the parts of psychological game theory dealing with preference, as illustrated by team reasoning, and supports the conclusion that these theoretical notions do not contribute above and beyond existing theory in understanding social interaction. In particular, psychology and games are already bridged by a comprehensive, formal, and inherently psychological theory, interdependence theory (Kelley & Thibaut 1978; Kelley et al. 2003), which has been demonstrated to account for a wide variety of social interaction phenomena.

Normative game theory unsatisfactorily explains rational behavior. Real people do not behave as predicted, and what is prescribed as rational behavior is normally unattainable in real-life. The problem is that current normative analysis does not account for people's cognitive limitations – their bounded rationality. However, this paper develops an account of bounded rationality that explains the rationality of more realistic behavior. I focus on the Centipede Game, in which boundedly rational players explore and test others' immediate behavior, until they can (...) apply limited backward induction. The result is that the game has a solution in the form of a subjective Nash equilibrium, which boundedly rational players can possibly realize. (shrink)

Since the early days of artificial intelligence (AI), many logics have been explored as tools for knowledge representation and reasoning. In the spirit of the Crossley Festscrift and recognizing John Crossley’s diverse interests and his legacy in both mathematical logic and computer science, I discuss examples from my own research that sit in the overlap of logic and AI, with a focus on supporting human–AI interactions.

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)

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)

I elaborate on Quilty-Dunn et al.'s integration of the language-of-thought hypothesis in social reasoning by outlining two discrepancies between the experimental paradigms referred to by the authors and the social world: Self-referential projection and deliberate thinking in experiments. Robust tests of the hypothesis in social reasoning should include observational, natural, and cross-cultural approaches.

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)

How do people reason about their opponent in turn-taking games? Often, people do not make the decisions that game theory would prescribe. We present a logic that can play a key role in understanding how people make their decisions, by delineating all plausible reasoning strategies in a systematic manner. This in turn makes it possible to construct a corresponding set of computational models in a cognitive architecture. These models can be run and fitted to the participants’ data in terms of (...) decisions, response times, and answers to questions. We validate these claims on the basis of an earlier game-theoretic experiment about the turn-taking game “Marble Drop with Surprising Opponent”, in which the opponent often starts with a seemingly irrational move. We explore two ways of segregating the participants into reasonable “player types”. The first way is based on latent class analysis, which divides the players into three classes according to their first decisions in the game: Random players, Learners, and Expected players, who make decisions consistent with forward induction. The second way is based on participants’ answers to a question about their opponent, classified according to levels of theory of mind: zero-order, first-order and second-order. It turns out that increasing levels of decisions and theory of mind both correspond to increasing success as measured by monetary awards and increasing decision times. Next, we use the logical language to express different kinds of strategies that people apply when reasoning about their opponent and making decisions in turn-taking games, as well as the ‘reasoning types’ reflected in their behavior. Then, we translate the logical formulas into computational cognitive models in the PRIMs architecture. Finally, we run two of the resulting models, corresponding to the strategy of only being interested in one’s own payoff and to the myopic strategy, in which one can only look ahead to a limited number of nodes. It turns out that the participant data fit to the own-payoff strategy, not the myopic one. The article closes the circle from experiments via logic and cognitive modelling back to predictions about new experiments. (shrink)

Franke, Dulcinati and Pouscoulous also examine a form of covert lying, by considering to what extent speakers use implicatures to deceive their addressee. The participants in their online signaling game had to describe a card, which a virtual coplayer then had to select. When the goal was to deceive rather than help the coplayer, participants produced more false descriptions (overt lies), but also more uninformative descriptions (covert lies by means of an implicature). [73].

Many social situations require a mental model of the knowledge, beliefs, goals, and intentions of others: a Theory of Mind (ToM). If a person can reason about other people’s beliefs about his own beliefs or intentions, he is demonstrating second-order ToM reasoning. A standard task to test second-order ToM reasoning is the second-order false belief task. A different approach to investigating ToM reasoning is through its application in a strategic game. Another task that is believed to involve the application of (...) second-order ToM is the comprehension of sentences that the hearer can only understand by considering the speaker’s alternatives. In this study we tested 40 children between 8 and 10 years old and 27 adult controls on (adaptations of) the three tasks mentioned above: the false belief task, a strategic game, and a sentence comprehension task. The results show interesting differences between adults and children, between the three tasks, and between this study and previous research. (shrink)

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)

The purpose of this paper is to provide a detailed technical protocol analysis of chess masters' evaluative expertise, paying particular attention to the analysis of the structure of their memory process in evaluating foreseen possibilities in games of dynamic equilibrium. The paper has two purposes. First, to publish a results chapter from my DPhil thesis (in revised journal article form) attending to the measurement of foresight in chess masters' evaluation process, testing alternative theories of cognitive expertise in the domain of (...) chess; and second to provide a subset of the technical graphical analysis that corresponds to that measurement to preserve this protocol analysis for access in the academic domain for future studies of expert memory and foresight (e.g., Ericsson & Simon, 1993). The step-by-step protocol analysis consists of: (i) an introduction to foresight cognition as hypothesis testing, (ii) a theoretical review in the domain of chess masters' expertise according to the theoretical frameworks in that field purporting hypotheses relevant to chess masters' evaluative skill processes, and (iii) summary tables and non-parametric statistical analysis corroborating chunking theory frameworks of expert cognition (e.g., DeGroot, 1965; Newell & Simon, 1972; Gobet, 1998; Gobet et al., 2004), and refuting the alternative search-evaluation models (e.g., Holding & Reynolds, 1982). Moreover, the journal article espouses the preservation of the traditional protocol analysis method core to the field of expert cognition (DeGroot, 1969; Kotov, 1971). The full protocol analysis can be found in monograph form here on my SSRN profile in ‘The role of falsification in hypothesis testing’. It takes the form of a specialist population study (e.g., detailed case study work; Luria, 1987). Thus the outline consists of a short introduction, a theoretical methodological review discussing protocol analysis methods for specialist population studies in cognition (with particular attention to the preservation of protocol analysis methods for chess studies in cognition and expert memory/ with a fresh angle on the foresight process), and the full set of protocol analyses with corresponding problem behaviour graphs. A subset of the main results has been published elsewhere (e.g., Cowley & Byrne, 2004; Cowley 2006), receiving scientific and scientific journalistic acclaim (e.g., Nature Online News 2004). (shrink)

Two main cognitive theories predict that people find refuting evidence that falsifies their theorising difficult, if not impossible to consider, even though such reasoning may be pivotal to grounding their everyday thoughts in reality (i.e., Poletiek, 1996; Klayman & Ha, 1987). In the classic 2-4-6 number sequence task devised by psychologists to test such reasoning skills in a simulated environment – people fail the test more often than not. In the 2-4-6 task participants try to discover what rule the number (...) triple 2-4-6 conforms to. The rule is ‘ascending numbers’, but it is tricky to discover this rule. Participants tend to generate hypotheses with the properties of the 2-4-6 triple, for example, ‘even numbers ascending in twos’. They must search for evidence to test whether their hypothesis is the rule. But experimental evidence has shown that they tend to generate confirming triples that they expect to be consistent with their hypothesis rather than inconsistent falsifying triples. Counter to the two main hypothesis testing theories this paper demonstrates that falsification is possible in five 2-4-6 task experiments when participants consider an Imaginary Participant’s hypothesis. Experiment 1 and 2 show that competition with an opponent hypothesis tester facilitates falsification. Experiments 3 to 5 show that the consideration of an alternative hypothesis helps this falsification of hypotheses lead to rule discovery. The implications of the results for theories of hypothesis testing and reasoning are discussed. (shrink)