Joseph Halpern

NeurIPS Conference 2022 Conference Paper

A Causal Analysis of Harm

• Sander Beckers
• Hana Chockler
• Joseph Halpern

As autonomous systems rapidly become ubiquitous, there is a growing need for a legal and regulatory framework toaddress 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.

AAAI Conference 2018 Conference Paper

Combining Experts’ Causal Judgments

• Dalal Alrajeh
• Hana Chockler
• Joseph Halpern

Consider a policymaker who wants to decide which intervention to perform in order to change a currently undesirable situation. The policymaker has at her disposal a team of experts, each with their own understanding of the causal dependencies between different factors contributing to the outcome. The policymaker has varying degrees of confidence in the experts’ opinions. She wants to combine their opinions in order to decide on the most effective intervention. We formally de- fine the notion of an effective intervention, and then consider how experts’ causal judgments can be combined in order to determine the most effective intervention. We define a notion of two causal models being compatible, and show how compatible causal models can be combined. We then use it as the basis for combining experts causal judgments. We illustrate our approach on a number of real-life examples.

AAAI Conference 2018 Conference Paper

Information Acquisition Under Resource Limitations in a Noisy Environment

• Matvey Soloviev
• Joseph Halpern

We introduce a theoretical model of information acquisition under resource limitations in a noisy environment. An agent must guess the truth value of a given Boolean formula ϕ after performing a bounded number of noisy tests of the truth values of variables in the formula. We observe that, in general, the problem of finding an optimal testing strategy for ϕ is hard, but we suggest a useful heuristic. The techniques we use also give insight into two apparently unrelated, but well-studied problems: (1) rational inattention (the optimal strategy may involve hardly ever testing variables that are clearly relevant to ϕ) and (2) what makes a formula hard to learn/remember.

AAAI Conference 2018 Conference Paper

Towards Formal Definitions of Blameworthiness, Intention, and Moral Responsibility

• Joseph Halpern
• Max Kleiman-Weiner

We provide formal definitions of degree of blameworthiness and intention relative to an epistemic state (a probability over causal models and a utility function on outcomes). These, together with a definition of actual causality, provide the key ingredients for moral responsibility judgments. We show that these definitions give insight into commonsense intuitions in a variety of puzzling cases from the literature.

AAAI Conference 2017 Conference Paper

Incentivising Monitoring in Open Normative Systems

• Natasha Alechina
• Joseph Halpern
• Ian Kash
• Brian Logan

We present an approach to incentivising monitoring for norm violations in open multi-agent systems such as Wikipedia. In such systems, there is no crisp definition of a norm violation; rather, it is a matter of judgement whether an agent’s behaviour conforms to generally accepted standards of behaviour. Agents may legitimately disagree about borderline cases. Using ideas from scrip systems and peer prediction, we show how to design a mechanism that incentivises agents to monitor each other’s behaviour for norm violations. The mechanism keeps the probability of undetected violations (submissions that the majority of the community would consider not conforming to standards) low, and is robust against collusion by the monitoring agents.

KR Conference 2016 Conference Paper

Sequential Equilibrium in Games of Imperfect Recall

• Joseph Halpern
• Rafael Pass

Definitions of sequential equilibrium and perfect equilibrium are given in games of imperfect recall. Subtleties regarding the definition are discussed.

IJCAI Conference 2015 Conference Paper

A Modification of the Halpern-Pearl Definition of Causality

• Joseph Halpern

The original Halpern-Pearl definition of causality [Halpern and Pearl, 2001] was updated in the journal version of the paper [Halpern and Pearl, 2005] to deal with some problems pointed out by Hopkins and Pearl [2003]. Here the definition is modified yet again, in a way that (a) leads to a simpler definition, (b) handles the problems pointed out by Hopkins and Pearl, and many others, (c) gives reasonable answers (that agree with those of the original and updated definition) in the standard problematic examples of causality, and (d) has lower complexity than either the original or updated definitions.

KR Conference 2014 Conference Paper

Appropriate Causal Models and Stability of Causation

• Joseph Halpern

Spohn 2008; Weslake 2014) have given examples that seem to show that the Halpern-Pearl (HP) definition of causality (Halpern & Pearl 2005) gives intuitively unreasonable answers. One contribution of this paper is to show that these “problematic” examples can be dealt with in a relatively uniform way, by being a little more careful about the choice of causal model. The need to choose the causal model carefully has been pointed out frequently (Blanchard & Schaffer 2013; Hall 2007; Halpern & Pearl 2005; Halpern & Hitchcock 2010; Hitchcock 2001; 2007). A causal model is characterized by the choice of variables, the equations relating them, and which variables we choose to make exogenous and endogenous (roughly speaking, which are the variables we choose to take as given and which we consider to be modifiable). Different choices of causal model for a given situation can lead to different conclusions regarding causality. The choices are, to some extent, subjective. While some suggestions have been made for good rules of thumb for choosing random variables (e. g., in (Halpern & Hitchcock 2010)), they are certainly not definitive. Moreover, the choice of variables may also depend in part on the variables that the modeler is aware of. In this paper, I consider the choice of representation in more detail in four examples. I show that in all these examples, the model originally considered (which I call the “naive” model) does not correctly model all the relevant features of the situation. I argue that we can see this because, in all these cases, there is another story that can be told, also consistent with the naive model, for which we have quite different intuitions regarding causality, This suggests that a more careful model is needed to disambiguate the stories. In the first four cases, what turns out to arguably be the best way to do the disambiguation is to add (quite well motivated) extra variables, which, roughly speaking, capture the mechanism of causality. In the final example, what turns out to be most relevant is the decision as to which variables to make exogenous. Once we model things more carefully, the HP approach gives the expected answer in all cases. As already observed by Halpern and Hitchcock (2014), adding extra variables also lets us deal with two other concerns that resulted in changes to the original HP definition. In Section 4, I consider an example due Hopkins and Pearl (2003) that motivated one of the changes. After showing Causal models defined in terms of structural equations have proved to be quite a powerful way of representing knowledge regarding causality. However, a number of authors have given examples that seem to show that the Halpern-Pearl (HP) definition of causality (Halpern & Pearl 2005) gives intuitively unreasonable answers. Here it is shown that, for each of these examples, we can give two stories consistent with the description in the example, such that intuitions regarding causality are quite different for each story. By adding additional variables, we can disambiguate the stories. Moreover, in the resulting causal models, the HP definition of causality gives the intuitively correct answer. It is also shown that, by adding extra variables, a modification to the original HP definition made to deal with an example of Hopkins and Pearl (2003) may not be necessary. Given how much can be done by adding extra variables, there might be a concern that the notion of causality is somewhat unstable. Can adding extra variables in a “conservative” way (i. e., maintaining all the relations between the variables in the original model) cause the answer to the question “Is X = x a cause of Y = y? ” to alternate between “yes” and “no”? Here it is shown that adding an extra variable can change the answer from “yes’ to “no”, but after that, it cannot cannot change back to “yes”.

KR Conference 2014 Conference Paper

Axiomatizing Rationality

• Adam Bjorndahl
• Joseph Halpern
• Rafael Pass

complexities of higher-order beliefs in a game-theoretic context. Formal logic furnishes a powerful and versatile class of such models; namely, modal logics of belief appropriately specialized for reasoning about games. Rationality is no less important in this setting; however, while it has been incorporated into these models both syntactically and semantically, no axiomatization of the resulting logical systems has been provided. This paper fills this gap. We take as our point of departure axioms for rationality in the sense of expected utility maximization given in (Bjorndahl, Halpern, & Pass 2011). We extend these axioms to arbitrary decision rules, under the assumption that the players’ uncertainty is represented by a probability measure. This allows us to deal with not just expected utility maximization, but other standard rules such as maximin and minimax regret (see (Halpern 2003) for a discussion of all the decision rules mentioned in this paper). We then go on to consider what happens when the players’ uncertainty is represented by a set of probabilities, which allows us to capture well-known decision rules such as maxmin expected utility and minimax expected regret. Finally, we consider situations where a player might be uncertain about which decision rules his opponents are using. The rest of this paper is organized as follows. In Section 2, we define the core concepts formally: games, modal logics of belief appropriate for reasoning about games, and the incorporation of rationality into these logics. Section 3 gives the axiomatization, and proves that it is sound and complete. In Section 4, we provide sound and complete axiomatizations for the cases where the players’ uncertainty is represented by sets of probabilities, and where players may be uncertain about the decision rules used by other players. In Section 5 we discuss the role of language. Section 6 concludes with a discussion of future work. More detailed proofs and further discussion can be found in the full paper, which is available at http: //www. math. cornell. edu/∼abjorndahl/Site/CV files/Axiomatizing%20Rationality. pdf. We provide a sound and complete axiomatization for a class of logics appropriate for reasoning about the rationality of players in games. Essentially the same axiomatization applies to a wide class of decision rules.

AAAI Conference 2014 Conference Paper

The Computational Complexity of Structure-Based Causality

• Gadi Aleksandrowicz
• Hana Chockler
• Joseph Halpern
• Alexander Ivrii

Halpern and Pearl introduced a definition of actual causality; Eiter and Lukasiewicz showed that computing whether X = x is a cause of Y = y is NP-complete in binary models (where all variables can take on only two values) and ΣP 2 complete in general models. In the final version of their paper, Halpern and Pearl slightly modified the definition of actual cause, in order to deal with problems pointed by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing actual cause. To characterize the complexity, a new family DP k, k = 1, 2, 3, .. ., of complexity classes is introduced, which generalizes the class DP introduced by Papadimitriou and Yannakakis (DP is just DP 1 ). We show that the complexity of computing causality under the updated definition is DP 2 -complete. Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame. The complexity of determining the degree of responsibility and blame using the original definition of causality was completely characterized. Again, we show that changing the definition of causality affects the complexity, and completely characterize it using the updated definition.

KR Conference 2012 Conference Paper

Ambiguous Language and Differences in Beliefs

• Joseph Halpern
• Willemien Kets

believes that her interpretation is how everyone interprets the announcement is but one assumption we can make about ambiguity. It is also possible that player i may be aware that there is more than one interpretation of p, but believes that player j is aware of only one interpretation. For example, think of a politician making an ambiguous statement which he realizes that different constituencies will interpret differently, but will not realize that there are other possible interpretations. In this paper, we investigate a number of different semantics of ambiguity that correspond to some standard assumptions that people make with regard to ambiguous statements, and investigate their relationship. Our interest in ambiguity is motivated by a seminal result in game theory: Aumann’s 1976 theorem showing that players cannot “agree to disagree”. More precisely, this theorem says that agents with a common prior on a state space cannot have common knowledge that they have different posteriors. 1 This result has been viewed as paradoxical in the economics literature. Trade in a stock market seems to require common knowledge of disagreement (about the value of the stock being traded), yet we clearly observe a great deal of trading. One well known explanation for the disagreement is that we do not in fact have common priors: agents start out with different beliefs. We provide a different explanation here, in terms of ambiguity. It is easy to show that we can agree to disagree when there is ambiguity, even if there is a common prior. We then show that these two explanations of the possibility of agreeing to disagree are closely related, but not identical. We can convert an explanation in terms of ambiguity to an explanation in terms of lack of common priors. 2 Importantly, however, the converse does not hold; there are models in which players have a common interpretation that cannot in general be converted into an equivalent model with ambiguity and a common prior. In other words, using heterogeneous priors may be too permissive if we are interested in modeling a situation where differences in beliefs are due to differences in interpretation. Although our work is motivated by applications in eco- Standard models of multi-agent modal logic do not capture the fact that information is often ambiguous, and may be interpreted in different ways by different agents. We propose a framework that can model this, and consider different semantics that capture different assumptions about the agents’ beliefs regarding whether or not there is ambiguity. We consider the impact of ambiguity on a seminal result in economics: Aumann’s result saying that agents with a common prior cannot agree to disagree. This result is known not to hold if agents do not have a common prior; we show that it also does not hold in the presence of ambiguity. We then consider the tradeoff between assuming a common interpretation (i. e., no ambiguity) and a common prior (i. e., shared initial beliefs).

AAMAS Conference 2010 Conference Paper

Cooperative Equilibrium

• Joseph Halpern
• Nan Rong

We propose a new equilibrium concept, perfect cooperativeequilibrium (PCE), which may help explain players' behaviorin games where cooperation is observed in practice. We alsoconsider a few related equilibrium concepts that take intoaccount the degree of cooperation.

KR Conference 2010 Conference Paper

From Causal Models To Counterfactual Structures

• Joseph Halpern

Galles and Pearl [1998] claimed that “for recursive models, the causal model framework does not add any restrictions to counterfactuals, beyond those imposed by Lewis’s [possibleworlds] framework. ” This claim is shown to be false. Indeed, the opposite claim is true: 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. 1 In sum, for recursive models, the causal model framework does not add any restrictions to counterfactuals beyond those imposed by Lewis’s framework; the very general concept of closest worlds is sufficient. Put another way, the assumption of recursiveness is so strong that it already embodies all other restrictions imposed by structural semantics. When we consider nonrecursive systems, however, we see that reversibility [a particular axiom introduced by Galles and Pearl] is not enforced by Lewis’s framework. This conclusion seems to have been accepted by the community. For example, in the Wikipedia article on “Counterfactual conditional” (en. wikipedia. org/wiki/Counterfactual conditional; Sept., 2009) it says “[The definition of counterfactuals in causal models] has been shown to be compatible with the axioms of possible world semantics. ” In this paper I examine these claims more carefully, and show that they are false. First, Galles and Pearl show that all the axioms of causal reasoning in the possible-worlds framework that they view as relevant (specifically, axioms that do not mention disjunction, since it is not in their language) hold in recursive causal models, and conclude that “for recursive models, the causal model framework does not add any restrictions to counterfactual statements beyond those imposed by Lewis’s framework”. The only conclusion that can be drawn from their argument is just the opposite: that the possible-worlds approach does not add any restrictions to causal reasoning beyond those imposed by causal models, since causal models satisfy all the axioms that possibleworlds models do, and perhaps more. Indeed, Galles and Pearl already show that causal models add a restriction: the reversibility axiom is valid in recursive models and is not valid in possible-worlds models. I show that the conclusion opposite to that claimed by Galles and Pearl is true: I identify a subclass of (possible world) counterfactual structures that I call recursive structures, and show that every recursive causal model can be as-

KR Conference 2010 Conference Paper

I Don't Want to Think About it Now: Decision Theory With Costly Computation

• Joseph Halpern
• Rafael Pass

Computation plays a major role in decision making. Even if an agent is willing to ascribe a probability to all states and a utility to all outcomes, and maximize expected utility, doing so might present serious computational problems. Moreover, computing the outcome of a given act might be difficult. In a companion paper we develop a framework for game theory with costly computation, where the objects of choice are Turing machines. Here we apply that framework to decision theory. We show how well-known phenomena like first-impression-matters biases (i. e., people tend to put more weight on evidence they hear early on), belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions), and the status quo bias (people are much more likely to stick with what they already have) can be easily captured in that framework. Finally, we use the framework to define some new notions: value of computational information (a computational variant of value of information) and computational value of conversation.

IJCAI Conference 2007 Conference Paper

• Joseph Halpern
• Yoram Moses

We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of knowledge-based programs. Intuitively, all solution concepts are implementations of two knowledge-based programs, one appropriate for games represented in normal form, the other for games represented in extensive form. These knowledge-based programs can be viewed as embodying rationality. The representation works even if (a) information sets do not capture an agent's knowledge, (b) uncertainty is not represented by probability, or (c) the underlying game is not common knowledge.

IJCAI Conference 2007 Conference Paper

• Joseph Halpern
• Leandro Rego

There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all logics between K and S4 is PSPACE-hard, while for S5, it is NP-complete. We show that it is negative introspection axiom that causes the gap: if we add this axiom to any modal logic between K and S4, then the satisfiability problem becomes NP-complete. Indeed, the satisfiability problem is NP-complete for any modal logic that includes the negative introspection axiom.

AAMAS Conference 2006 Conference Paper

Games with Possibly Unaware Players

• Leandro Rego
• Joseph Halpern

KR Conference 2006 Conference Paper

Reasoning About Knowledge of Unawareness

• Leandro Rego
• Joseph Halpern

Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an agent knows that there are facts of which he is unaware without there being an explicit fact that the agent knows he is unaware of. We propose a logic for reasoning about knowledge of unawareness, by extending Fagin and Halpern's Logic of General Awareness. The logic allows quantification over variables, so that there is a formula in the language that can express the fact that "an agent explicitly knows that there exists a fact of which he is unaware". Moreover, that formula can be true without the agent explicitly knowing that he is unaware of any particular formula. We provide a sound and complete axiomatization of the logic, using standard axioms from the literature to capture the quantification operator. Finally, we show that the validity problem for the logic is recursively enumerable, but not decidable.

KR Conference 2006 Conference Paper

Redoing the Foundations of Decision Theory

• Joseph Halpern
• Larry Blume
• David Easley

In almost all current approaches to decision making, it is assumed that a decision problem is described by a set of states and set of outcomes, and the decision maker (DM) has preferences over a rather rich set of acts, which are functions from states to outcomes. However, most interesting decision problems do not come with a state space and an outcome space. Indeed, in complex problems it is often far from clear what the state and outcome spaces would be. We present an alternate foundation for decision making, in which the primitive objects of choice are syntactic programs. A program can be given semantics as a function from states to outcomes, but does not necessarily have to be described this way. A representation theorem is proved in the spirit of standard representation theorems, showing that if the DM's preference relation on programs satisfies appropriate axioms, then there exist a set S of states, a set O of outcomes, a way of viewing program as functions from S to O, a probability on S, and a utility function on O, such that the DM prefers program a to program b if and only if the expected utility of a is higher than that of b. Thus, the state space and outcome space are subjective, just like the probability and utility; they are not part of the description of the problem.

KR Conference 2004 Conference Paper

Intransitivity and Vagueness

• Joseph Halpern

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.

KR Conference 2004 Conference Paper

Sleeping Beauty Reconsidered

• Joseph Halpern