The question of whether knowledge is definable in terms of belief, which has played an important role in epistemology for the last 50 years, is studied here in the framework of epistemic and doxastic logics. Three notions of definability are considered: explicit definability, implicit definability, and reducibility, where explicit definability is equivalent to the combination of implicit definability and reducibility. It is shown that if knowledge satisfies any set of axioms contained in S5, then it cannot be explicitly defined in (...) terms of belief. S5 knowledge can be implicitly defined by belief, but not reduced to it. On the other hand, S4.4 knowledge and weaker notions of knowledge cannot be implicitly defined by belief, but can be reduced to it by defining knowledge as true belief. It is also shown that S5 knowledge cannot be reduced to belief and justification, provided that there are no axioms that involve both belief and justification. (shrink)

Using formal systems to represent and reason about uncertainty.

A new approach for defining causality and such related notions as degree of responsibility, degrees of blame, and causal explanation. Causality plays a central role in the way people structure the world; we constantly seek causal explanations for our observations. But what does it even mean that an event C "actually caused" event E? The problem of defining actual causation goes beyond mere philosophical speculation. For example, in many legal arguments, it is precisely what needs to be established in order (...) to determine responsibility. The philosophy literature has been struggling with the problem of defining causality since Hume. In this book, Joseph Halpern explores actual causality, and such related notions as degree of responsibility, degree of blame, and causal explanation. The goal is to arrive at a definition of causality that matches our natural language usage and is helpful, for example, to a jury deciding a legal case, a programmer looking for the line of code that cause some software to fail, or an economist trying to determine whether austerity caused a subsequent depression. Halpern applies and expands an approach to causality that he and Judea Pearl developed, based on structural equations. He carefully formulates a definition of causality, and building on this, defines degree of responsibility, degree of blame, and causal explanation. He concludes by discussing how these ideas can be applied to such practical problems as accountability and program verification. Technical details are generally confined to the final section of each chapter and can be skipped by non-mathematical readers. (shrink)

Recent work in psychology and experimental philosophy has shown that judgments of actual causation are often influenced by consideration of defaults, typicality, and normality. A number of philosophers and computer scientists have also suggested that an appeal to such factors can help deal with problems facing existing accounts of actual causation. This article develops a flexible formal framework for incorporating defaults, typicality, and normality into an account of actual causation. The resulting account takes actual causation to be both graded and (...) comparative. We then show how our account would handle a number of standard cases. 1 Introduction2 Causal Models3 The HP Definition of Actual Causation4 The Problem of Isomorphism5 Defaults, Typicality, and Normality6 Extended Causal Models7 Examples7.1 Omissions7.2 Knobe effects7.3 Causes versus background conditions7.4 Bogus prevention7.5 Causal chains7.6 Legal doctrines of intervening causes7.7 Pre-emption and short circuits8 Conclusion. (shrink)

Reasoning About Knowledge is the first book to provide a general discussion of approaches to reasoning about knowledge and its applications to distributed ...

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well examples which have caused problems for other definitions and resolves major difficulties in the traditional account.

Three notions of definability in multimodal logic are considered. Two are analogous to the notions of explicit definability and implicit definability introduced by Beth in the context of first-order logic. However, while by Beth’s theorem the two types of definability are equivalent for first-order logic, such an equivalence does not hold for multimodal logics. A third notion of definability, reducibility, is introduced; it is shown that in multimodal logics, explicit definability is equivalent to the combination of implicit definability and reducibility. (...) The three notions of definability are characterized semantically using algebras. The use of algebras, rather than frames, is shown to be necessary for these characterizations. (shrink)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion article. Essentially, an explanation is a fact that is not known for certain but, if found to be true, would constitute an actual cause of the fact to be explained, regardless of the agent's initial uncertainty. We show that the definition handles well a number of problematic examples from the literature.

The appropriateness of S5 as a logic of knowledge has been attacked at some length in the philosophical literature. Here one particular attack based on the interplay between knowledge and belief is considered: Suppose that knowledge satisfies S5, belief satisfies KD45, and both the entailment property (knowledge implies belief) and positive certainty (if the agent believes something, she believes she knows it) hold. Then it can be shown that belief reduces to knowledge: it is impossible to have false beliefs. While (...) the entailment property has typically been viewed as perhaps the least controversial of these assumptions, an argument is presented that it can plausibly be viewed as the culprit. More precisely, it is shown that this attack fails if we weaken the entailment property so that it applies only to objective (nonmodal) formulas, rather than to arbitrary formulas. Since the standard arguments in favor of the entailment property are typically given only for objective formulas, this observation suggests that care must be taken in applying intuitions that seem reasonable in the case of objective formulas to arbitrary formulas. (shrink)

There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence relation (and thus transitive). It is shown that if the uncertainty perception and the question of when an agent reports that two things are indistinguishable are both carefully modeled, the problems disappear, and indistinguishability can indeed be taken to be an equivalence relation. Moreover, this model also suggests a logic of vagueness that seems (...) to solve many of the problems related to vagueness discussed in the philosophical literature. In particular, it is shown here how the logic can handle the sorites paradox. (shrink)

Galles & Pearl (l998) claimed that s [possible-worlds] framework.s framework. Recursive models are shown to correspond precisely to a subclass of (possible-world) counterfactual structures. On the other hand, a slight generalization of recursive models, models where all equations have unique solutions, is shown to be incomparable in expressive power to counterfactual structures, despite the fact that the Galles and Pearl arguments should apply to them as well. The problem with the Galles and Pearl argument is identified: an axiom that they (...) viewed as irrelevant, because it involved disjunction (which was not in their language), is not irrelevant at all. (shrink)

The question of whether knowledge is definable in terms of belief, which has played an important role in epistemology for the last 50 years, is studied here in the framework of epistemic and doxastic logics. Three notions of definability are considered: explicit definability, implicit definability, and reducibility, where explicit definability is equivalent to the combination of implicit definability and reducibility. It is shown that if knowledge satisfies any set of axioms contained in S5, then it cannot be explicitly defined in (...) terms of belief. S5 knowledge can be implicitly defined by belief, but not reduced to it. On the other hand, S4.4 knowledge and weaker notions of knowledge cannot be implicitly defined by belief, but can be reduced to it by defining knowledge as true belief. It is also shown that S5 knowledge cannot be reduced to belief and justification, provided that there are no axioms that involve both belief and justification. (shrink)

Judea Pearl (2000) was the first to propose a definition of actual causation using causal models. A number of authors have suggested that an adequate account of actual causation must appeal not only to causal structure but also to considerations of normality. In Halpern and Hitchcock (2011), we offer a definition of actual causation using extended causal models, which include information about both causal structure and normality. Extended causal models are potentially very complex. In this study, we show how (...) it is possible to achieve a compact representation of extended causal models. (shrink)

In 1960, E. P. Wigner, a joint winner of the 1963 Nobel Prize for Physics, published a paper titled On the Unreasonable Effectiveness of Mathematics in the Natural Sciences [61]. This paper can be construed as an examination and affirmation of Galileo's tenet that “The book of nature is written in the language of mathematics”. To this effect, Wigner presented a large number of examples that demonstrate the effectiveness of mathematics in accurately describing physical phenomena. Wigner viewed these examples as (...) illustrations of what he called the empirical law of epistemology, which asserts that the mathematical formulation of the laws of nature is both appropriate and accurate, and that mathematics is actually the correct language for formulating the laws of nature. At the same time, Wigner pointed out that the reasons for the success of mathematics in the natural sciences are not completely understood; in fact, he went as far as asserting that “… the enormous usefulness of mathematics in the natural sciences is something bordering on the mysterious and there is no rational explanation for it.”. (shrink)

ABSTRACT For changing opinion, represented by an assignment of probabilities to propositions, the criterion proposed is motivated by the requirement that the assignment should have, and maintain, the possibility of matching in some appropriate sense statistical proportions in a population. This ‘tracking’ criterion implies limitations on policies for updating in response to a wide range of types of new input. Satisfying the criterion is shown equivalent to the principle that the prior must be a convex combination of the possible posteriors. (...) Furthermore, this is equivalent to the requirement that prior expected values must fall inside the range spanned by possible posterior expected values. The tracking criterion is liberal; it allows for, but does not require, a policy such as Bayesian conditionalization, and can be offered as a general constraint on policies for managing opinion over time. Examples are given of non-Bayesian policies, both ones that satisfy and ones that violate the criterion. _1_ Introduction _2_ Alternative Updating Policies _3_ Modelling the Situation for Normal Updating _4_ Tracking: A Criterion for Updating Policies _5_ Tracking: Precise Formulation and Relation to Convexity _6_ The Spanning Criterion _7_ Non-Bayesian Policies that Satisfy the Spanning and Tracking Criteria _8_ Policies that Violate the Spanning and Tracking Criteria Appendix Appendix. (shrink)

There have been two major lines of research aimed at capturing resource-bounded players in game theory. The first, initiated by Rubinstein (), charges an agent for doing costly computation; the second, initiated by Neyman (), does not charge for computation, but limits the computation that agents can do, typically by modeling agents as finite automata. We review recent work on applying both approaches in the context of decision theory. For the first approach, we take the objects of choice in a (...) decision problem to be Turing machines, and charge players for the “complexity” of the Turing machine chosen (e.g., its running time). This approach can be used to explain well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on) and belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions) as the outcomes of quite rational decisions. For the second approach, we model people as finite automata, and provide a simple algorithm that, on a problem that captures a number of settings of interest, provably performs optimally as the number of states in the automaton increases. (shrink)

Natural conditions are provided that are sufficient to ensure that causality as defined by approaches that use counterfactual dependence and structural equations will be transitive.

For changing opinion, represented by an assignment of probabilities to propositions, the criterion proposed is motivated by the requirement that the assignment should have, and maintain, the possibility of matching in some appropriate sense statistical proportions in a population. This ‘tracking’ criterion implies limitations on policies for updating in response to a wide range of types of new input. Satisfying the criterion is shown equivalent to the principle that the prior must be a convex combination of the possible posteriors. Furthermore, (...) this is equivalent to the requirement that prior expected values must fall inside the range spanned by possible posterior expected values. The tracking criterion is liberal; it allows for, but does not require, a policy such as Bayesian conditionalization, and can be offered as a general constraint on policies for managing opinion over time. Examples are given of non-Bayesian policies, both ones that satisfy and ones that violate the criterion. 1 Introduction2 Alternative Updating Policies3 Modelling the Situation for Normal Updating4 Tracking: A Criterion for Updating Policies5 Tracking: Precise Formulation and Relation to Convexity6 The Spanning Criterion7 Non-Bayesian Policies that Satisfy the Spanning and Tracking Criteria8 Policies that Violate the Spanning and Tracking Criteria AppendixAppendix. (shrink)

Causal models have proven extremely useful in offering formal representations of causal relationships between a set of variables. Yet in many situations, there are non-causal relationships among variables. For example, we may want variables LDL, HDL, and TOT that represent the level of low-density lipoprotein cholesterol, the level of lipoprotein high-density lipoprotein cholesterol, and total cholesterol level, with the relation LDL+HDL=TOT. This cannot be done in standard causal models, because we can intervene simultaneously on all three variables. The goal of (...) this paper is to extend standard causal models to allow for constraints on settings of variables. Although the extension is relatively straightforward, to make it useful we have to define a new intervention operation that disconnects a variable from a causal equation. We give examples showing the usefulness of this extension, and provide a sound and complete axiomatization for causal models with constraints. (shrink)

As autonomous systems rapidly become ubiquitous, there is a growing need for a legal and regulatory framework to address when and how such a system harms someone. There have been several attempts within the philosophy literature to define harm, but none of them has proven capable of dealing with with the many examples that have been presented, leading some to suggest that the notion of harm should be abandoned and "replaced by more well-behaved notions". As harm is generally something that (...) is caused, most of these definitions have involved causality at some level. Yet surprisingly, none of them makes use of causal models and the definitions of actual causality that they can express. In this paper we formally define a qualitative notion of harm that uses causal models and is based on a well-known definition of actual causality (Halpern, 2016). The key novelty of our definition is that it is based on contrastive causation and uses a default utility to which the utility of actual outcomes is compared. We show that our definition is able to handle the examples from the literature, and illustrate its importance for reasoning about situations involving autonomous systems. (shrink)

Scientific models describe natural phenomena at different levels of abstraction. Abstract descriptions can provide the basis for interventions on the system and explanation of observed phenomena at a level of granularity that is coarser than the most fundamental account of the system. Beckers and Halpern (2019), building on work of Rubenstein et al. (2017), developed an account of abstraction for causal models that is exact. Here we extend this account to the more realistic case where an abstract causal model (...) offers only an approximation of the underlying system. We show how the resulting account handles the discrepancy that can arise between low- and high-level causal models of the same system, and in the process provide an account of how one causal model approximates another, a topic of independent interest. Finally, we extend the account of approximate abstractions to probabilistic causal models, indicating how and where uncertainty can enter into an approximate abstraction. (shrink)

We consider a setting where a decision maker’s uncertainty is represented by a set of probability measures, rather than a single measure. Measure-by-measure updating of such a set of measures upon acquiring new information is well known to suffer from problems. To deal with these problems, we propose using weighted sets of probabilities: a representation where each measure is associated with a weight, which denotes its significance. We describe a natural approach to updating in such a situation and a natural (...) approach to determining the weights. We then show how this representation can be used in decision making, by modifying a standard approach to decision making—minimizing expected regret—to obtain minimax weighted expected regret. We provide an axiomatization that characterizes preferences induced by MWER both in the static and dynamic case. (shrink)

We consider a sequence of successively more restrictive definitions of abstraction for causal models, starting with a notion introduced by Rubenstein et al. (2017) called exact transformation that applies to probabilistic causal models, moving to a notion of uniform transformation that applies to deterministic causal models and does not allow differences to be hidden by the "right" choice of distribution, and then to abstraction, where the interventions of interest are determined by the map from low-level states to high-level states, and (...) strong abstraction, which takes more seriously all potential interventions in a model, not just the allowed interventions. We show that procedures for combining micro-variables into macro-variables are instances of our notion of strong abstraction, as are all the examples considered by Rubenstein et al. (shrink)

I show how thinking in terms of the protocol used can help clarify problems related to anthropic reasoning and self-location, such as the Doomsday Argument and the Sleeping Beauty Problem.

This collection of essays is a Festschrift for Ernest W. Adams, and is based on a symposium that was held in his honor in 1993. As the title suggests, most of the essays focus on probability and the logic of conditionals, and the relationship between them; they draw their inspiration from Adams’s seminal work on the subject. As a computer scientist, I was struck by just how much the topics discussed play a major role in much recent work in computer (...) science, and how relevant much recent work in computer science is to some of the issues discussed here. (shrink)

This collection of essays is a Festschrift for Ernest W. Adams, and is based on a symposium that was held in his honor in 1993. As the title suggests, most of the essays focus on probability and the logic of conditionals, and the relationship between them; they draw their inspiration from Adams’s seminal work on the subject. As a computer scientist, I was struck by just how much the topics discussed play a major role in much recent work in computer (...) science, and how relevant much recent work in computer science is to some of the issues discussed here. (shrink)