Joseph Y. Halpern

JAIR Journal 2025 Journal Article

A Unifying Framework for Causal Modeling With Infinitely Many Variables

• Spencer Peters
• Joseph Y. Halpern

Structural-equations models (SEMs) are perhaps the most commonly used framework for modeling causality, but they do not capture all domains of interest. For example, dynamical systems that evolve in continuous time are an important class of domains that are not (naturally) captured by SEMs. A wide variety of approaches have been proposed to fill the gap, including dynamical structural causal models (Bongers, Blom and Mooij 2018), causal constraints models (Blom, Bongers and Mooij 2019), and counterfactual resimulation (Laurent, Yang, and Fontana 2018). These models complement common-sense causal interpretations of specific dynamical systems, such as systems of ODEs. All these approaches look quite different from each other and from SEMs. They are hard to compare, and concepts developed for one approach may not make sense for another. But they are capturing the same notion of causality as SEMs do, in the sense that interventions map to outcomes. We propose a class of models that are, in a certain natural sense, the most expressive generalization of SEMs. Our generalized SEMs (GSEMs) can be viewed as a unifying framework that recovers structural dynamical causal models, causal constraints models, counterfactual resimulation, and common-sense causal interpretations of systems of ODEs and hybrid automata (Alur et al. 1992) as special cases. The input-output behavior, or “interface”, of GSEMs is exactly that of SEMs, which means that definitions of concepts like actual cause, responsibility, blame, and explanation, can be immediately lifted from SEMs to GSEMs. The generality of GSEMs also makes them ideally suited to studying causality in the abstract; for example, they have been used to establish independence relationships among Halpern’s axioms for SEMs (Peters and Halpern 2022).

TARK Conference 2025 Conference Paper

Causality Without Causal Models

• Joseph Y. Halpern
• Rafael Pass

Perhaps the most prominent current definition of (actual) causality is due to Halpern and Pearl. It is defined using causal models (also known as structural equations models). We abstract the definition, extracting its key features, so that it can be applied to any other model where counterfactuals are defined. By abstracting the definition, we gain a number of benefits. Not only can we apply the definition in a wider range of models, including ones that allow, for example, backtracking, but we can apply the definition to determine if A is a cause of B even if A and B are formulas involving disjunctions, negations, beliefs, and nested counterfactuals (none of which can be handled by the Halpern-Pearl definition). Moreover, we can extend the ideas to getting an abstract definition of explanation that can be applied beyond causal models. Finally, we gain a deeper understanding of features of the definition even in causal models.

KR Conference 2024 Conference Paper

A Representation Theorem for Causal Decision Making

• Joseph Y. Halpern
• Evan Piermont

We show that it is possible to understand and identify a decision maker’s subjective causal judgements by observing her preferences over interventions. Following Pearl [2000, DOI: doi. org/10. 1017/S0266466603004109 ], we represent causality using causal models (also called structural equations models), where the world is described by a collection of variables, related by equations. We show that if a preference relation over interventions satisfies certain axioms (related to standard axioms regarding counterfactuals), then we can define (i) a causal model, (ii) a probability capturing the decision-maker’s uncertainty regarding the external factors in the world and (iii) a utility on outcomes such that each intervention is associated with an expected utility and such that intervention A is preferred to B iff the expected utility of A is greater than that of B. In addition, we characterize when the causal model is unique. Thus, our results allow a modeler to test the hypothesis that a decision maker’s preferences are consistent with some causal model and to identify causal judgements from observed behavior.

KR Conference 2024 Conference Paper

Explaining Image Classifiers

• Hana Chockler
• Joseph Y. Halpern

We focus on explaining image classifiers, taking the work of Mothilal et al. 2021 (MMTS) as our point of departure. We observe that, although MMTS claim to be using the definition of explanation proposed by Halpern 2016, they do not quite do so. Roughly speaking, Halpern’s definition has a necessity clause and a sufficiency clause. MMTS replace the necessity clause by a requirement that, as we show, implies it. Halpern’s definition also allows agents to restrict the set of options considered. While these difference may seem minor, as we show, they can have a nontrivial impact on explanations. We also show that, essentially without change, Halpern’s definition can handle two issues that have proved difficult for other approaches: explanations of absence (when, for example, an image classifier for tumors outputs “no tumor”) and explanations of rare events (such as tumors).

NeurIPS Conference 2024 Conference Paper

Intervention and Conditioning in Causal Bayesian Networks

• Sainyam Galhotra
• Joseph Y. Halpern

Causal models are crucial for understanding complex systems andidentifying causal relationships among variables. Even though causalmodels are extremely popular, conditional probability calculation offormulas involving interventions pose significant challenges. In case of Causal Bayesian Networks (CBNs), Pearl assumes autonomy of mechanisms that determine interventions to calculate a range ofprobabilities. We show that by making simple yetoften realistic independence assumptions, it is possible to uniquely estimate the probability of an interventional formula (includingthe well-studied notions of probability of sufficiency and necessity). We discuss when these assumptions are appropriate. Importantly, in many cases of interest, when the assumptions are appropriate, these probability estimates can be evaluated usingobservational data, which carries immense significance in scenarioswhere conducting experiments is impractical or unfeasible.

NeurIPS Conference 2024 Conference Paper

Qualitative Mechanism Independence

• Oliver E. Richardson
• Spencer Peters
• Joseph Y. Halpern

We define what it means for a joint probability distribution to be compatible with aset of independent causal mechanisms, at a qualitative level—or, more precisely with a directed hypergraph $\mathcal A$, which is the qualitative structure of a probabilistic dependency graph (PDG). When A represents a qualitative Bayesian network, QIM-compatibility with $\mathcal A$ reduces to satisfying the appropriate conditional independencies. But giving semantics to hypergraphs using QIM-compatibility lets us do much more. For one thing, we can capture functional dependencies. For another, we can capture important aspects of causality using compatibility: we can use compatibility to understand cyclic causal graphs, and to demonstrate structural compatibility, we must essentially produce a causal model. Finally, compatibility has deep connections to information theory. Applying compatibility to cyclic structures helps to clarify a longstanding conceptual issue in information theory.

UAI Conference 2023 Conference Paper

Inference for probabilistic dependency graphs

• Oliver E. Richardson
• Joseph Y. Halpern
• Christopher De Sa

Probabilistic dependency graphs (PDGs) are a flexible class of probabilistic graphical models, subsuming Bayesian Networks and Factor Graphs. They can also capture inconsistent beliefs, and provide a way of measuring the degree of this inconsistency. We present the first tractable inference algorithm for PDGs with discrete variables, making the asymptotic complexity of PDG inference similar that of the graphical models they generalize. The key components are: (1) the observation that PDG inference can be reduced to convex optimization with exponential cone constraints, (2) a construction that allows us to express these problems compactly for PDGs of boundeed treewidth, for which we needed to further develop the theory of PDGs, and (3) an appeal to interior point methods that can solve such problems in polynomial time. We verify the correctness and time complexity of our approach, and provide an implementation of it. We then evaluate our implementation, and demonstrate that it outperforms baseline approaches.

TARK Conference 2023 Conference Paper

Joint Behavior and Common Belief

• Meir Friedenberg
• Joseph Y. Halpern

For over 25 years, common belief has been widely viewed as necessary for joint behavior. But this is not quite correct. We show by example that what can naturally be thought of as joint behavior can occur without common belief. We then present two variants of common belief that can lead to joint behavior, even without standard common belief ever being achieved, and show that one of them, action-stamped common belief, is in a sense necessary and sufficient for joint behavior. These observations are significant because, as is well known, common belief is quite difficult to achieve in practice, whereas these variants are more easily achievable.

IJCAI Conference 2023 Conference Paper

Quantifying Harm

• Sander Beckers
• Hana Chockler
• Joseph Y. Halpern

In earlier work we defined a qualitative notion of harm: either harm is caused, or it is not. For practical applications, we often need to quantify harm; for example, we may want to choose the least harmful of a set of possible interventions. We first present a quantitative definition of harm in a deterministic context involving a single individual, then we consider the issues involved in dealing with uncertainty regarding the context and going from a notion of harm for a single individual to a notion of "societal harm", which involves aggregating the harm to individuals. We show that the "obvious" way of doing this (just taking the expected harm for an individual and then summing the expected harm over all individuals) can lead to counterintuitive or inappropriate answers, and discuss alternatives, drawing on work from the decision-theory literature.

TARK Conference 2023 Conference Paper

Sequential Language-based Decisions

• Adam Bjorndahl
• Joseph Y. Halpern

In earlier work, we introduced the framework of language-based decisions, the core idea of which was to modify Savage's classical decision-theoretic framework by taking actions to be descriptions in some language, rather than functions from states to outcomes, as they are defined classically. Actions had the form "if psi then do(phi)", where psi and phi were formulas in some underlying language, specifying what effects would be brought about under what circumstances. The earlier work allowed only one-step actions. But, in practice, plans are typically composed of a sequence of steps. Here, we extend the earlier framework to sequential actions, making it much more broadly applicable. Our technical contribution is a representation theorem in the classical spirit: agents whose preferences over actions satisfy certain constraints can be modeled as if they are expected utility maximizers. As in the earlier work, due to the language-based specification of the actions, the representation theorem requires a construction not only of the probability and utility functions representing the agent's beliefs and preferences, but also the state and outcomes spaces over which these are defined, as well as a "selection function" which intuitively captures how agents disambiguate coarse descriptions. The (unbounded) depth of action sequencing adds substantial interest (and complexity!) to the proof.

AAMAS Conference 2023 Conference Paper

Strategic Play By Resource-Bounded Agents in Security Games

• Xinming Liu
• Joseph Y. Halpern

Many studies have shown that humans are “predictably irrational”: they do not act in a fully rational way, but their deviations from rational behavior are quite systematic. Our goal is to see the extent to which we can explain and justify these deviations as the outcome of rational but resource-bounded agents doing as well as they can, given their limitations. We focus on the well-studied ranger-poacher game, where rangers are trying to protect a number of sites from poaching. We capture the computational limitations by modeling the poacher and the ranger as probabilistic finite automata (PFAs). We show that, with sufficiently large memory, PFAs learn to play the Nash equilibrium (NE) strategies of the game and achieve the NE utility. However, if we restrict the memory, we get more “human-like” behaviors, such as probability matching, and avoiding sites where there was a bad outcome, that we also observed in experiments conducted on Amazon Mechanical Turk. Interestingly, we find that adding human-like behaviors such as probability matching and overweighting significant events actually improves performance, showing that this seemingly irrational behavior can be quite rational.

AAAI Conference 2022 Conference Paper

On Testing for Discrimination Using Causal Models

• Hana Chockler
• Joseph Y. Halpern

Consider a bank that uses an AI system to decide which loan applications to approve. We want to ensure that the system is fair, that is, it does not discriminate against applicants based on a predefined list of sensitive attributes, such as gender and ethnicity. We expect there to be a regulator whose job it is to certify the bank’s system as fair or unfair. We consider issues that the regulator will have to confront when making such a decision, including the precise definition of fairness, dealing with proxy variables, and dealing with what we call allowed variables, that is, variables such as salary on which the decision is allowed to depend, despite being correlated with sensitive variables. We show (among other things) that the problem of deciding fairness as we have defined it is co- NP-complete, but then argue that, despite that, in practice the problem should be manageable.

AAAI Conference 2022 Conference Paper

Reasoning about Causal Models with Infinitely Many Variables

• Joseph Y. Halpern
• Spencer Peters

Generalized structural equations models (GSEMs) (Peters and Halpern 2021), are, as the name suggests, a generalization of structural equations models (SEMs). They can deal with (among other things) infinitely many variables with infinite ranges, which is critical for capturing dynamical systems. We provide a sound and complete axiomatization of causal reasoning in GSEMs that is an extension of the sound and complete axiomatization provided by Halpern (2000) for SEMs. Considering GSEMs helps clarify what properties Halpern’s axioms capture.

TARK Conference 2021 Conference Paper

Language-based Decisions

• Adam Bjorndahl
• Joseph Y. Halpern

In Savage's classic decision-theoretic framework, actions are formally defined as functions from states to outcomes. But where do the state space and outcome space come from? Expanding on recent work by Blume, Easley, and Halpern (BEH), we consider a language-based framework in which actions are identified with (conditional) descriptions in a simple underlying language, while states and outcomes (along with probabilities and utilities) are constructed as part of a representation theorem. Our work expands the role of language from that of BEH by using it not only for the conditions that determine which actions are taken, but also the effects. More precisely, we take the set of actions to be built from those of the form "do(phi)", for formulas phi in the underlying language. This presents a problem: how do we interpret the result of do(phi) when phi is underspecified (i. e. , compatible with multiple states)? We answer this using tools familiar from the semantics of counterfactuals: roughly speaking, do(phi) maps each state to the "closest" phi-state. This notion of "closest" is also something we construct as part of the representation theorem; in effect, then, we prove that (under appropriate assumptions) the agent is acting as if each underspecified action is first made definite and then evaluated (i. e. , by maximizing expected utility). Of course, actions in the real world are often not presented in a fully precise manner, yet agents reason about and form preferences among them all the same. Our work brings the abstract tools of decision theory into closer contact with such real-world scenarios.

UAI Conference 2020 Conference Paper

Bounded Rationality in Las Vegas: Probabilistic Finite Automata Play Multi-Armed Bandits

• Xinming Liu
• Joseph Y. Halpern

While traditional economics assumes that humans are fully rational agents who always maximize their expected utility, in practice, we constantly observe apparently irrational behavior. One explanation is that people have limited computational power, so that they are, quite rationally, making the best decisions they can, given their computational limitations. To test this hypothesis, we consider the multi-armed bandit (MAB) problem. We examine a simple strategy for playing an MAB that can be implemented easily by a probabilistic finite automaton (PFA). Roughly speaking, the PFA sets certain expectations, and plays an arm as long as it meets them. If the PFA has sufficiently many states, it performs near-optimally. Its performance degrades gracefully as the number of states decreases. Moreover, the PFA acts in a "human-like" way, exhibiting a number of standard human biases, like an optimism bias and a negativity bias.

AIJ Journal 2020 Journal Article

Combining experts' causal judgments

• Dalal Alrajeh
• Hana Chockler
• Joseph Y. 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 define 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 merged. We then use it as the basis for combining experts' causal judgments. We also provide a definition of decomposition for causal models to cater for cases when models are incompatible. We illustrate our approach on a number of real-life examples.

KR Conference 2020 Conference Paper

Dynamic Awareness

• Joseph Y. Halpern
• Evan Piermont

We investigate how to model the beliefs of an agent who becomes more aware. We use the framework of Halpern and Rego (2013) by adding probability, and define a notion of a model transition that describes constraints on how, if an agent becomes aware of a new formula φ in state s of a model M, she transitions to state s* in a model M*. We then discuss how such a model can be applied to information disclosure.

TARK Conference 2019 Conference Paper

A Conceptually Well-Founded Characterization of Iterated Admissibility Using an "All I Know" Operator

• Joseph Y. Halpern
• Rafael Pass

Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (IA), also known as iterated deletion of weakly dominated strategies, where uncertainty is represented using LPSs (lexicographic probability sequences). Their characterization holds in a rich structure called a complete structure, where all types are possible. In earlier work, we gave a characterization of iterated admissibility using an "all I know" operator, that captures the intuition that "all the agent knows" is that agents satisfy the appropriate rationality assumptions. That characterization did not need complete structures and used probability structures, not LPSs. However, that characterization did not deal with Samuelson's conceptual concern regarding IA, namely, that at higher levels, players do not consider possible strategies that were used to justify their choice of strategy at lower levels. In this paper, we give a characterization of IA using the all I know operator that does deal with Samuelson's concern. However, it uses LPSs. We then show how to modify the characterization using notions of "approximate belief" and "approximately all I know" so as to deal with Samuelson's concern while still working with probability structures.

AAAI Conference 2019 Conference Paper

Abstracting Causal Models

• Sander Beckers
• Joseph Y. Halpern

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.

UAI Conference 2019 Conference Paper

Approximate Causal Abstractions

• Sander Beckers
• Frederick Eberhardt
• Joseph Y. Halpern

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 prior work of Rubinstein 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 only offers 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.

AAAI Conference 2019 Conference Paper

Blameworthiness in Multi-Agent Settings

• Meir Friedenberg
• Joseph Y. Halpern

We provide a formal definition of blameworthiness in settings where multiple agents can collaborate to avoid a negative outcome. We first provide a method for ascribing blameworthiness to groups relative to an epistemic state (a distribution over causal models that describe how the outcome might arise). We then show how we can go from an ascription of blameworthiness for groups to an ascription of blameworthiness for individuals using a standard notion from cooperative game theory, the Shapley value. We believe that getting a good notion of blameworthiness in a group setting will be critical for designing autonomous agents that behave in a moral manner.

AIJ Journal 2019 Journal Article

Book review

• Joseph Y. Halpern

AAAI Conference 2019 Conference Paper

Partial Awareness

• Joseph Y. Halpern
• Evan Piermont

We develop a modal logic to capture partial awareness. The logic has three building blocks: objects, properties, and concepts. Properties are unary predicates on objects; concepts are Boolean combinations of properties. We take an agent to be partially aware of a concept if she is aware of the concept without being aware of the properties that define it. The logic allows for quantification over objects and properties, so that the agent can reason about her own unawareness. We then apply the logic to contracts, which we view as syntactic objects that dictate outcomes based on the truth of formulas. We show that when agents are unaware of some relevant properties, referencing concepts that agents are only partially aware of can improve welfare.

KR Conference 2018 Conference Paper

Combining the Causal Judgments of Experts with Possibly Different Focus Areas

• Meir Friedenberg
• Joseph Y. Halpern

In many real-world settings, a decision-maker must combine information provided by different experts in order to decide on an effective policy. Alrajeh, Chockler, and Halpern (2018) showed how to combine causal models that are compatible in the sense that, for variables that appear in both models, the experts agree on the causal structure. In this work we show how causal models can be combined in cases where the experts might disagree on the causal structure for variables that appear in both models due to having different focus areas. We provide a new formal definition of compatibility of models in this setting and show how compatible models can be combined. We also consider the complexity of determining whether models are compatible. We believe that the notions defined in this work are of direct relevance to many practical decision making scenarios that come up in natural, social, and medical science settings.

JAIR Journal 2018 Journal Article

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems

• Natasha Alechina
• Joseph Y. Halpern
• Ian A. Kash
• Brian Logan

We consider the problem of detecting norm violations in open multi-agent systems (MAS). We show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations. The cost of providing the incentives is not borne by the MAS and does not come from fines charged for norm violations (fines may be impossible to levy in a system where agents are free to leave and rejoin again under a different identity). Instead, monitoring incentives come from (scrip) fees for accessing the services provided by the MAS. In some cases, perfect monitoring (and hence enforcement) can be achieved: no norms will be violated in equilibrium. In other cases, we show that, while it is impossible to achieve perfect enforcement, we can get arbitrarily close; we can make the probability of a norm violation in equilibrium arbitrarily small. We show using simulations that our theoretical results, which apply to systems with a large number of agents, hold for multi-agent systems with as few as 1000 agents–the system rapidly converges to the steady-state distribution of scrip tokens necessary to ensure monitoring and then remains close to the steady state.

IJCAI Conference 2018 Conference Paper

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems (Extended Abstract)

• Natasha Alechina
• Joseph Y. Halpern
• Ian A. Kash
• Brian Logan

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al. , 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations.

TARK Conference 2017 Conference Paper

A Knowledge-Based Analysis of the Blockchain Protocol

• Joseph Y. Halpern
• Rafael Pass

At the heart of the Bitcoin is a blockchain protocol, a protocol for achieving consensus on a public ledger that records bitcoin transactions. To the extent that a blockchain protocol is used for applications such as contract signing and making certain transactions (such as house sales) public, we need to understand what guarantees the protocol gives us in terms of agents' knowledge. Here, we provide a complete characterization of agent's knowledge when running a blockchain protocol using a variant of common knowledge that takes into account the fact that agents can enter and leave the system, it is not known which agents are in fact following the protocol (some agents may want to deviate if they can gain by doing so), and the fact that the guarantees provided by blockchain protocols are probabilistic. We then consider some scenarios involving contracts and show that this level of knowledge suffices for some scenarios, but not others.

TARK Conference 2017 Conference Paper

An Epistemic Foundation for Authentication Logics (Extended Abstract)

• Joseph Y. Halpern
• Ron van der Meyden
• Riccardo Pucella

While there have been many attempts, going back to BAN logic, to base reasoning about security protocols on epistemic notions, they have not been all that successful. Arguably, this has been due to the particular logics chosen. We present a simple logic based on the well-understood modal operators of knowledge, time, and probability, and show that it is able to handle issues that have often been swept under the rug by other approaches, while being flexible enough to capture all the higher- level security notions that appear in BAN logic. Moreover, while still assuming that the knowledge operator allows for unbounded computation, it can handle the fact that a computationally bounded agent cannot decrypt messages in a natural way, by distinguishing strings and message terms. We demonstrate that our logic can capture BAN logic notions by providing a translation of the BAN operators into our logic, capturing belief by a form of probabilistic knowledge.

AAMAS Conference 2017 Conference Paper

Causality, Responsibility and Blame in Team Plans

• Natasha Alechina
• Joseph Y. Halpern
• Brian Logan

Many objectives can be achieved (or may be achieved more effectively) only by a group of agents executing a team plan. If a team plan fails, it is often of interest to determine what caused the failure, the degree of responsibility of each agent for the failure, and the degree of blame attached to each agent. We show how team plans can be represented in terms of structural equations, and then apply the definitions of causality introduced by Halpern [11] and degree of responsibility and blame introduced by Chockler and Halpern [3] to determine the agent(s) who caused the failure and what their degree of responsibility/blame is. We also prove new results on the complexity of computing causality and degree of responsibility and blame, showing that they can be determined in polynomial time for many team plans of interest.

TARK Conference 2017 Conference Paper

From Type Spaces to Probability Frames and Back, via Language

• Adam Bjorndahl
• Joseph Y. Halpern

We investigate the connection between the two major mathematical frameworks for modeling interactive beliefs: Harsanyi type spaces and possible-worlds style probability frames. While translating the former into the latter is straightforward, we demonstrate that the reverse translation relies implicitly on a background logical language. Once this "language parameter" is made explicit, it reveals a close relationship between universal type spaces and canonical models: namely, that they are essentially the same construct. As the nature of a canonical model depends heavily on the background logic used to generate it, this work suggests a new view into a corresponding landscape of universal type spaces.

TARK Conference 2017 Conference Paper

Games With Tolerant Players

• Arpita Ghosh
• Joseph Y. Halpern

A notion of pi-tolerant equilibrium is defined that takes into account that players have some tolerance regarding payoffs in a game. This solution concept generalizes Nash and refines epsilon-Nash equilibrium in a natural way. We show that pi-tolerant equilibrium can explain cooperation in social dilemmas such as Prisoner's Dilemma and the Public Good game. We then examine the structure of particularly cooperative pi-tolerant equilibria, where players are as cooperative as they can be, subject to their tolerances, in Prisoner's Dilemma. To the extent that cooperation is due to tolerance, these results provide guidance to a mechanism designer who has some control over the payoffs in a game, and suggest ways in which cooperation can be increased.

JAIR Journal 2017 Journal Article

The Computational Complexity of Structure-Based Causality

• Gadi Aleksandrowicz
• Hana Chockler
• Joseph Y. 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 out by Hopkins and Pearl. As we show, this modification has a nontrivial impact on the complexity of computing whether {X} = {x} is a cause of Y = y. To characterize the complexity, a new family D_k^P, k = 1, 2, 3,..., of complexity classes is introduced, which generalises the class DP introduced by Papadimitriou and Yannakakis (DP is just D_1^P). We show that the complexity of computing causality under the updated definition is D_2^P -complete. Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame, and characterized the complexity of determining the degree of responsibility and blame using the original definition of causality. Here, we completely characterize the complexity using the updated definition of causality. In contrast to the results on causality, we show that moving to the updated definition does not result in a difference in the complexity of computing responsibility and blame.

AAMAS Conference 2016 Conference Paper

Decentralised Norm Monitoring in Open Multi-Agent Systems (Extended Abstract)

• Natasha Alechina
• Joseph Y. Halpern
• Ian A. Kash
• Brian Logan

UAI Conference 2016 Conference Paper

MDPs with Unawareness in Robotics

• Nan Rong
• Joseph Y. Halpern
• Ashutosh Saxena

while most actions result in the robot losing control and falling down. We formalize decision-making problems in robotics and automated control using continuous MDPs and actions that take place over continuous time intervals. We then approximate the continuous MDP using finer and finer discretizations. Doing this results in a family of systems, each of which has an extremely large action space, although only a few actions are “interesting”. We can view the decision maker as being unaware of which actions are “interesting”. We an model this using MDPUs, MDPs with unawareness, where the action space is much smaller. As we show, MDPUs can be used as a general framework for learning tasks in robotic problems. We prove results on the difficulty of learning a near-optimal policy in an an MDPU for a continuous task. We apply these ideas to the problem of having a humanoid robot learn on its own how to walk. Halpern, Rong, and Saxena [2010] (HRS from now on) defined MDPs with unawareness (MDPUs), where a decision-maker (DM) can be unaware of the actions in an MDP. In the robotics applications in which we are interested, we can think of the DM (e. g. , a humanoid robot) as being unaware of which actions are the useful actions, and thus can model what is going on using an MDPU.

TARK Conference 2015 Conference Paper

Bayesian Games with Intentions

• Adam Bjorndahl
• Joseph Y. Halpern
• Rafael Pass

We show that standard Bayesian games cannot represent the full spectrum of belief-dependent preferences. However, by introducing a fundamental distinction between intended and actual strategies, we remove this limitation. We define Bayesian games with intentions, generalizing both Bayesian games and psychological games, and prove that Nash equilibria in psychological games correspond to a special class of equilibria as defined in our setting.

TARK Conference 2015 Conference Paper

Translucent Players: Explaining Cooperative Behavior in Social Dilemmas

• Valerio Capraro
• Joseph Y. Halpern

In the last few decades, numerous experiments have shown that humans do not always behave so as to maximize their material payoff. Cooperative behavior when non-cooperation is a dominant strategy (with respect to the material payoffs) is particularly puzzling. Here we propose a novel approach to explain cooperation, assuming what Halpern and Pass call translucent players. Typically, players are assumed to be opaque, in the sense that a deviation by one player in a normal-form game does not affect the strategies used by other players. But a player may believe that if he switches from one strategy to another, the fact that he chooses to switch may be visible to the other players. For example, if he chooses to defect in Prisoner's Dilemma, the other player may sense his guilt. We show that by assuming translucent players, we can recover many of the regularities observed in human behavior in well-studied games such as Prisoner's Dilemma, Traveler's Dilemma, Bertrand Competition, and the Public Goods game.

JAIR Journal 2015 Journal Article

Weighted Regret-Based Likelihood: A New Approach to Describing Uncertainty

• Joseph Y. Halpern

Recently, Halpern and Leung suggested representing uncertainty by a set of weighted probability measures, and suggested a way of making decisions based on this representation of uncertainty: maximizing weighted regret. Their paper does not answer an apparently simpler question: what it means, according to this representation of uncertainty, for an event E to be more likely than an event E'. In this paper, a notion of comparative likelihood when uncertainty is represented by a set of weighted probability measures is defined. It generalizes the ordering defined by probability (and by lower probability) in a natural way; a generalization of upper probability can also be defined. A complete axiomatic characterization of this notion of regret-based likelihood is given.

AIJ Journal 2014 Journal Article

A logic for reasoning about ambiguity

• Joseph Y. Halpern
• Willemien Kets

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 examine the expressive power of logics of ambiguity compared to logics that cannot model ambiguity, with respect to the different semantics that we propose.

AIJ Journal 2014 Journal Article

Erratum to ‘A logic for reasoning about ambiguity’ [Artificial Intelligence 209 (2014) 1–10]

• Joseph Y. Halpern
• Willemien Kets

TARK Conference 2013 Conference Paper

Game Theory with Translucent Players

• Joseph Y. Halpern
• Rafael Pass

Keywords A traditional assumption in game theory is that players are opaque to one another—if a player changes strategies, then this change in strategies does not affect the choice of other players’ strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i. e. , all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax dominated strategies: a strategy σi is minimax dominated for i if there exists a strategy σi0 for i such that minµ0−i ui (σi0, µ0−i ) > maxµ−i ui (σi, µ−i ). Epistemic logic, rationality, counterfactuals 1.

TARK Conference 2013 Conference Paper

Language-based Games

• Adam Bjorndahl
• Joseph Y. Halpern
• Rafael Pass

theory, beginning with [6] and expanded in [3], is an enrichment of the classical setting meant to capture these kinds of preferences and motivations. In a similar vein, work on reference-dependent preferences, as developed in [7], formalizes phenomena such as loss-aversion by augmenting players’ preferences with an additional sense of gain or loss derived by comparing the actual outcome to what was expected. In both of these theories, the method of generalization takes the same basic form: the domain of the utility functions is enlarged to include not only the outcomes of the game, but also the beliefs of the players. The resulting structure may be fairly complex; for instance, in psychological game theory, since the goal is to model preferences that depend not only on beliefs about outcomes, but also beliefs about beliefs, beliefs about beliefs about beliefs, and so on, the domain of the utility functions is extended to include infinite hierarchies of beliefs. The model we present in this paper, though motivated in part by a desire to capture belief-dependent preferences, is geared towards a much more general goal. Besides being expressive enough to subsume existing systems such as those described above, it establishes a general framework for modeling players with richer preferences. Moreover, it is equally capable of representing impoverished preferences, a canonical example of which are so-called “coarse beliefs” or “categorical thinking” [9]. More specifically, our formalism provides good practical and theoretical tools for handling beliefs as discrete rather than continuous objects, an advantage that is particularly relevant in the context of psychological effects in games. Despite this expressive power, the system is easy to use: player preferences are represented in a simple and natural manner, narrowing the divide between intuition and formalism. As a preliminary illustration of some of these points, consider the following simple example. We introduce language-based games, a generalization of psychological games [6] that can also capture referencedependent preferences [7]. The idea is to extend the domain of the utility function to situations, maximal consistent sets in some language. The role of the underlying language in this framework is thus particularly critical. Of special interest are languages that can express only coarse beliefs [9]. Despite the expressive power of the approach, we show that it can describe games in a simple, natural way. Nash equilibrium and rationalizability are generalized to this setting; Nash equilibrium is shown not to exist in general, while the existence of rationalizable strategies is proved under mild conditions.

IJCAI Conference 2013 Conference Paper

Language-Based Games (Extended Abstract)

• Adam Bjorndahl
• Joseph Y. Halpern
• Rafael Pass

We introduce language-based games, a generalization of psychological games [Geanakoplos et al. , 1989] that can also capture reference-dependent preferences [Kőszegi and Rabin, 2006], which extend the domain of the utility function to situations, maximal consistent sets in some language. The role of the underlying language in this framework is thus particularly critical. Of special interest are languages that can express only coarse beliefs [Mullainathan, 2002]. Despite the expressive power of the approach, we show that it can describe games in a simple, natural way. Nash equilibrium and rationalizability are generalized to this setting; Nash equilibrium is shown not to exist in general, while the existence of rationalizable strategies is proved under mild conditions.

IJCAI Conference 2013 Conference Paper

Sequential Equilibrium in Computational Games

• Joseph Y. Halpern
• Rafael Pass

We examine sequential equilibrium in the context of computational games [Halpern and Pass, 2011a], where agents are charged for computation. In such games, an agent can rationally choose to forget, so issues of imperfect recall arise. In this setting, we consider two notions of sequential equilibrium. One is an ex ante notion, where a player chooses his strategy before the game starts and is committed to it, but chooses it in such a way that it remains optimal even off the equilibrium path. The second is an interim notion, where a player can reconsider at each information set whether he is doing the “right” thing, and if not, can change his strategy. The two notions agree in games of perfect recall, but not in games of imperfect recall. Although the interim notion seems more appealing, in [Halpern and Pass, 2011b] it is argued that there are some deep conceptual problems with it in standard games of imperfect recall. We show that the conceptual problems largely disappear in the computational setting. Moreover, in this setting, under natural assumptions, the two notions coincide.

UAI Conference 2012 Conference Paper

Weighted Sets of Probabilities and MinimaxWeighted Expected Regret: New Approaches for Representing Uncertainty and Making Decisions

• Joseph Y. Halpern
• Samantha Leung

We consider a setting where an agent’s uncertainty is represented by a set of probability measures, rather than a single measure. Measureby-measure updating of such a set of measures upon acquiring new information is well-known to suffer from problems; agents are not always able to learn appropriately. 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 (MWER). We provide an axiomatization that characterizes preferences induced by MWER both in the static and dynamic case.

AIJ Journal 2011 Journal Article

Dealing with logical omniscience: Expressiveness and pragmatics

• Joseph Y. Halpern
• Riccardo Pucella

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest (especially with probability in the picture), we show that they are not equi-expressive. We then consider the pragmatics of dealing with logical omniscience—how to choose an approach and construct an appropriate model.

TARK Conference 2011 Conference Paper

Reasoning about justified belief

• Adam Bjorndahl
• Joseph Y. Halpern
• Rafael Pass

Halpern and Pass [8] introduce a logic of justified belief and go on to prove that strong rationalizability is characterized in this logic in terms of common justified belief of rationality (CJBR). Their paper provides semantics for this logic but no axiomatization. We correct this deficiency by reformulating the definition of justified belief and providing a complete axiomatization of this new system. We then prove a result analogous to the characterization of strong rationalizability in terms of CJBR, and analyze the additional assumptions needed to do so.

UAI Conference 2010 Conference Paper

MDPs with Unawareness

• Joseph Y. Halpern
• Nan Rong
• Ashutosh Saxena

Markov decision processes (MDPs) are widely used for modeling decision-making problems in robotics, automated control, and economics. Traditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of interest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibilities that a DM may not be aware of all possible actions. We provide a complete characterization of when a DM can learn to play near-optimally in an MDPU, and give an algorithm that learns to play near-optimally when it is possible to do so, as efficiently as possible. In particular, we characterize when a near-optimal solution can be found in polynomial time.

IJCAI Conference 2009 Conference Paper

• Joseph Y. Halpern
• Rafael Passo

For some well-known games, such as the Traveler’s Dilemma or the Centipede Game, traditional gametheoretic solution concepts—most notably Nash equilibrium—predict outcomes that are not consistent with empirical observations. We introduce a new solution concept, iterated regret minimization, which exhibits the same qualitative behavior as that observed in experiments in many games of interest, including Traveler’s Dilemma, the Centipede Game, Nash bargaining, and Bertrand competition. As the name suggests, iterated regret minimization involves the iterated deletion of strategies that do not minimize regret.

TARK Conference 2009 Conference Paper

A logical characterization of iterated admissibility

• Joseph Y. Halpern
• Rafael Pass

Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (i. e. , iterated deletion of weakly dominated strategies) where uncertainty is represented using LPSs (lexicographic probability sequences). Their characterization holds in a rich structure called a complete structure, where all types are possible. Here, a logical characterization of iterated admissibility is given that involves only standard probability and holds in all structures, not just complete structures. Roughly speaking, our characterization shows that iterated admissibility captures the intuition that “all the agent knows” is that agents satisfy the appropriate rationality assumptions.

TARK Conference 2009 Conference Paper

An epistemic characterization of zero knowledge

• Joseph Y. Halpern
• Rafael Pass
• Vasumathi Raman

Halpern, Moses and Tuttle presented a definition of interactive proofs using a notion they called practical knowledge, but left open the question of finding an epistemic formula that completely characterizes zero knowledge; that is, a formula that holds iff a proof is zero knowledge. We present such a formula, and show that it does characterize zero knowledge. Moreover, we show that variants of the formula characterize variants of zero knowledge such as concurrent zero knowledge [Dwork, Naor, and Sahai 2004] and proofs of knowledge [Feige, Fiat, and Shamir 1987; Tompa and Woll 1987].

AAMAS Conference 2009 Conference Paper

Multiagent Learning in Large Anonymous Games

• Ian A. Kash
• Eric J. Friedman
• Joseph Y. Halpern

In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if bestreply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed.

TARK Conference 2009 Conference Paper

Reasoning about knowledge of unawareness revisited

• Joseph Y. Halpern
• Leandro Chaves Rêgo

In earlier work [Halpern and Rêgo 2006b], we proposed a logic that extends the Logic of General Awareness of Fagin and Halpern [1988] by allowing quantification over primitive propositions. This makes it possible to express the fact that an agent knows that there are some facts of which he is unaware. In that logic, it is not possible to model an agent who is uncertain about whether he is aware of all formulas. To overcome this problem, we keep the syntax of the earlier paper, but allow models where, with each world, a possibly different language is associated. We provide a sound and complete axiomatization for this logic and show that, under natural assumptions, the quantifier-free fragment of the logic is characterized by exactly the same axioms as the logic of Heifetz, Meier, and Schipper [2008].

UAI Conference 2008 Conference Paper

A Game-Theoretic Analysis of Updating Sets of Probabilities

• Peter Grünwald
• Joseph Y. Halpern

We consider how an agent should update her uncertainty when it is represented by a set P of probability distributions and the agent observes that a random variable X takes on value x, given that the agent makes decisions using the minimax criterion, perhaps the best-studied and most commonly-used criterion in the literature. We adopt a game-theoretic framework, where the agent plays against a bookie, who chooses some distribution from P. We consider two reasonable games that differ in what the bookie knows when he makes his choice. Anomalies that have been observed before, like time inconsistency, can be understood as arising because different games are being played, against bookies with different information. We characterize the important special cases in which the optimal decision rules according to the minimax criterion amount to either conditioning or simply ignoring the information. Finally, we consider the relationship between conditioning and calibration when uncertainty is described by sets of probabilities.

KR Conference 2008 Conference Paper

Defaults and Normality in Causal Structures

• Joseph Y. Halpern

A serious defect with the Halpern-Pearl (HP) definition of causality is repaired by combining a theory of causality with a theory of defaults. In addition, it is shown that (despite a claim to the contrary) a cause according to the HP condition need not be a single conjunct. A definition of causality motivated by Wright's NESS test is shown to always hold for a single conjunct. Moreover, conditions that hold for all the examples considered by HP are given that guarantee that causality according to (this version) of the NESS test is equivalent to the HP definition.

AAAI Conference 2008 Conference Paper

From Qualitative to Quantitative Proofs of Security Properties Using First-Order Conditional Logic

• Joseph Y. Halpern

A first-order conditional logic is considered, with semantics given by a variant of -semantics (Adams 1975; Goldszmidt & Pearl 1992), where ϕ→ψ means that Pr(ψ | ϕ) approaches 1 super-polynomially—faster than any inverse polynomial. This type of convergence is needed for reasoning about security protocols. A complete axiomatization is provided for this semantics, and it is shown how a qualitative proof of the correctness of a security protocol can be automatically converted to a quantitative proof appropriate for reasoning about concrete security.

TARK Conference 2007 Conference Paper

Dealing with logical omniscience

• Joseph Y. Halpern
• Riccardo Pucella

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest they are not. In particular, adding probabilities to the language allows for finer distinctions between different approaches.

TARK Conference 2007 Conference Paper

Generalized solution concepts in games with possibly unaware players

• Leandro Chaves Rêgo
• Joseph Y. Halpern

Most work in game theory assumes that players are perfect reasoners and have common knowledge of all significant aspects of the game. In earlier work [Halpern and Rêgo 2006], we proposed a framework for representing and analyzing games with possibly unaware players, and suggested a generalization of Nash equilibrium appropriate for games with unaware players that we called generalized Nash equilibrium. Here, we use this framework to analyze other solution concepts, with a focus on sequential equilibrium. We also provide some insight into the notion of generalized Nash equilibrium by proving that it is closely related to the notion of rationalizability when we restrict the analysis to games in normal form and no unawareness is involved.

UAI Conference 2005 Conference Paper

Evidence with Uncertain Likelihoods

• Joseph Y. Halpern
• Riccardo Pucella

An agent often has a number of hypotheses, and must choose among them based on observations, or outcomes of experiments. Each of these observations can be viewed as providing evidence for or against various hypotheses. All the attempts to formalize this intuition up to now have assumed that associated with each hypothesis h there is a likelihood function μh, which is a probability measure that intuitively describes how likely each observation is, conditional on h being the correct hypothesis. We consider an extension of this framework where there is uncertainty as to which of a number of likelihood functions is appropriate, and discuss how one formal approach to defining evidence, which views evidence as a function from priors to posteriors, can be generalized to accommodate this uncertainty.

TARK Conference 2005 Conference Paper

Interactive unawareness revisited

• Joseph Y. Halpern
• Leandro Chaves Rêgo

We analyze a model of interactive unawareness introduced by Heifetz, Meier and Schipper (HMS). We consider two axiomatizations for their model, which capture different notions of validity. These axiomatizations allow us to compare the HMS approach to both the standard (S5) epistemic logic and two other approaches to unawareness: that of Fagin and Halpern and that of Modica and Rustichini. We show that the differences between the HMS approach and the others are mainly due to the notion of validity used and the fact that the HMS is based on a 3-valued propositional logic.

AIJ Journal 2004 Journal Article

Great expectations. Part II: generalized expected utility as a universal decision rule

• Francis C. Chu
• Joseph Y. Halpern

Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in [F. Chu, J. Y. Halpern, Great expectation. Part I: On the customizability of generalized expected utility, in: Proc. IJCAI-03, Acapulco, Mexico, 2003] is a universal decision rule, in the sense that it can essentially all other decision rules. This approach gives us a general technique for designing new decision rules as well as providing a framework for comparing decision rules to each other.

LPAR Conference 2004 Conference Paper

Knowledge-Based Synthesis of Distributed Systems Using Event Structures

• Mark Bickford
• Robert L. Constable
• Joseph Y. Halpern
• Sabina Petride

Abstract To produce a program guaranteed to satisfy a given specification one can synthesize it from a formal constructive proof that a computation satisfying that specification exists. This process is particularly effective if the specifications are written in a high-level language that makes it easy for designers to specify their goals. We consider a high-level specification language that results from adding knowledge to a fragment of Nuprl specifically tailored for specifying distributed protocols, called event theory. We then show how high-level knowledge-based programs can be synthesized from the knowledge-based specifications using a proof development system such as Nuprl. Methods of Halpern and Zuck [15] then apply to convert these knowledge-based protocols to ordinary protocols. These methods can be expressed as heuristic transformation tactics in Nuprl.

STOC Conference 2004 Conference Paper

Rational secret sharing and multiparty computation: extended abstract

• Joseph Y. Halpern
• Vanessa Teague

We consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as possible of the other agents get it. We show that, under these assumptions, neither secret sharing nor multiparty function computation is possible using a mechanism that has a fixed running time. However, we show that both are possible using randomized mechanisms with constant expected running time.

I&C Journal 2004 Journal Article

Reasoning about common knowledge with infinitely many agents

• Joseph Y. Halpern
• Richard A. Shore

Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents. The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G−G′, where G and G′ are sets of agents. Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even when the sets of agents involved are finite. Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented.

UAI Conference 2004 Conference Paper

When Ignorance is Bliss

• Peter Grünwald
• Joseph Y. Halpern

It is commonly-accepted wisdom that more information is better, and that information should never be ignored. Here we argue, using both a Bayesian and a non-Bayesian analysis, that in some situations you are better off ignoring information if your uncertainty is represented by a set of probability measures. These include situations in which the information is relevant for the prediction task at hand. In the non-Bayesian analysis, we show how ignoring information avoids dilation, the phenomenon that additional pieces of information sometimes lead to an increase in uncertainty. In the Bayesian analysis, we show that for small sample sizes and certain prediction tasks, the Bayesian posterior based on a noninformative prior yields worse predictions than simply ignoring the given information.

UAI Conference 2003 Conference Paper

A Logic for Reasoning about Evidence

• Joseph Y. Halpern
• Riccardo Pucella

We introduce a logic for reasoning about evidence, that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, and consider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence

TARK Conference 2003 Conference Paper

Probabilistic algorithmic knowledge

• Joseph Y. Halpern
• Riccardo Pucella

The frameworkof algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning "Yes" to a query about a fact ~oprovides evidence for qobeing true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.

UAI Conference 2002 Conference Paper

Reasoning about Expectation

• Joseph Y. Halpern
• Riccardo Pucella

Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying representation of uncertainty. We give sound and complete axiomatizations for the logic in the case that the underlying representation is (a) probability, (b) sets of probability measures, (c) belief functions, and (d) possibility measures. We show that this logic is more expressive than the corresponding logic for reasoning about likelihood in the case of sets of probability measures, but equi-expressive in the case of probability, belief, and possibility. Finally, we show that satisfiability for these logics is NP-complete, no harder than satisfiability for propositional logic.

UAI Conference 2002 Conference Paper

Updating Probabilities

• Peter Grünwald
• Joseph Y. Halpern

As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space', which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR (coarsening at random) in the statistical literature characterizes when ``naive' conditioning in a naive space works. We show that the CAR condition holds rather infrequently. We then consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, but show that there are no such conditions for MRE. This generalizes and interconnects previous results obtained in the literature on CAR and MRE.

UAI Conference 2001 Conference Paper

A Logic for Reasoning about Upper Probabilities

• Joseph Y. Halpern
• Riccardo Pucella

We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.

UAI Conference 2001 Conference Paper

Causes and Explanations: A Structural-Model Approach: Part 1: Causes

• Joseph Y. Halpern
• Judea Pearl

We propose a new definition of actual causes, using structural equations to model counterfactuals.We show that the definitions yield a plausible and elegant account ofcausation that handles well examples which have caused problems forother definitions and resolves major difficulties in the traditionalaccount. In a companion paper, we show how the definition of causality can beused to give an elegant definition of (causal) explanation.

UAI Conference 2000 Conference Paper

Conditional Plausibility Measures and Bayesian Networks

• Joseph Y. Halpern

A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability measures can all be viewed as defining algebraic conditional plausibility measures. It is shown that the technology of Bayesian networks can be applied to algebraic conditional plausibility measures.

AIJ Journal 1999 Journal Article

Reasoning about noisy sensors and effectors in the situation calculus

• Fahiem Bacchus
• Joseph Y. Halpern
• Hector J. Levesque

Agents interacting with an incompletely known world need to be able to reason about the effects of their actions, and to gain further information about that world they need to use sensors of some sort. Unfortunately, both the effects of actions and the information returned from sensors are subject to error. To cope with such uncertainties, the agent can maintain probabilistic beliefs about the state of the world. With probabilistic beliefs the agent will be able to quantify the likelihood of the various outcomes of its actions and is better able to utilize the information gathered from its error-prone actions and sensors. In this paper, we present a model in which we can reason about an agent's probabilistic degrees of belief and the manner in which these beliefs change as various actions are executed. We build on a general logical theory of action developed by Reiter and others, formalized in the situation calculus. We propose a simple axiomatization that captures an agent's state of belief and the manner in which these beliefs change when actions are executed. Our model displays a number of intuitively reasonable properties.

UAI Conference 1998 Conference Paper

Axiomatizing Causal Reasoning

• Joseph Y. Halpern

Causal models defined in terms of a collection of equations, as defined by Pearl, are axiomatized here. Axiomatizations are provided for three successively more general classes of causal models: (1) the class of recursive theories (those without feedback), (2) the class of theories where the solutions to the equations are unique, (3) arbitrary theories (where the equations may not have solutions and, if they do, they are not necessarily unique). It is shown that to reason about causality in the most general third class, we must extend the language used by Galles and Pearl. In addition, the complexity of the decision procedures is examined for all the languages and classes of models considered.

TARK Conference 1998 Conference Paper

Characterizing the Common Prior Assumption

• Joseph Y. Halpern

Logical characterizations of the common prior assumption (CPA) are investigated. Two approaches are considered. The first is called frame distinguishability, and is similar in spirit to the approaches considered in the economics literature. Results similar to those obtained in the economics literature are proved here as well, namely, that we can distinguish finite spaces that satisfy the CPA from those that do not in terms of disagreements in expectation. However, it is shown that, for the language used here, no formulas can distinguish infinite spaces satisfying the CPA from those that do not. The second approach considered is that of finding a sound and complete axiomatization. Such an axiomatization is provided; again, the key axiom involves disagreements in expectation. The same axiom system is shown to be sound and complete both in the finite and the infinite case. Thus, the two approaches to characterizing the CPA behave quite differently in the case of infinite spaces.

TARK Conference 1998 Conference Paper

Hypothetical Knowledge and Counterfactual Reasoning

• Joseph Y. Halpern

Salmetintroduced a notion of hypothetical knowledge and showed how it could be used to capture the type of counterfactual reasoning necessary to force the backwards induction solution in a game of perfect information. He argued that while hypotheticalknowledgeand the extended information structures used to model it bear someresemblanceto the way philosophershave used conditional logic to model counterfactuals, hypotheticalknowledgecannot be reduced to conditional logic together with epistemic logic. Here it is shown that in fact hypothetical knowledge can be captured using the standard counterfactual operator ">" and the knowledgeoperator "K", provided that some assumptions are made regarding the interaction between the two. It is argued, however, that these assumptions are unreasonable in general, as are the axioms that follow from them. Some implications for game theory are discussed.

AIJ Journal 1998 Journal Article

On the knowledge requirements of tasks

• Ronen I. Brafman
• Joseph Y. Halpern
• Yoav Shoham

In order to successfully perform a task, a situated system requires some information about its domain. If we can understand what information the system requires, we may be able to equip it with more suitable sensors or make better use of the information available to it. These considerations have motivated roboticists to examine the issue of sensor design, and in particular, the minimal information required to perform a task. We show here that reasoning in terms of what the robot knows and needs to know to perform a task is a useful approach for analyzing these issues. We extend the formal framework for reasoning about knowledge, already used in AI and distributed computing, by developing a set of basic concepts and tools for modeling and analyzing the knowledge requirements of tasks. We investigate properties of the resulting framework, and show how it can be applied to robotics tasks.

UAI Conference 1998 Conference Paper

Updating Sets of Probabilities

• Adam J. Grove
• Joseph Y. Halpern

There are several well-known justifications for conditioning as the appropriate method for updating a single probability measure, given an observation. However, there is a significant body of work arguing for sets of probability measures, rather than single measures, as a more realistic model of uncertainty. Conditioning still makes sense in this context---we can simply condition each measure in the set individually, then combine the results---and, indeed, it seems to be the preferred updating procedure in the literature. But how justified is conditioning in this richer setting? Here we show, by considering an axiomatic account of conditioning given by van Fraassen, that the single-measure and sets-of-measures cases are very different. We show that van Fraassens axiomatization for the former case is nowhere near sufficient for updating sets of measures. We give a considerably longer (and not as compelling) list of axioms that together force conditioning in this setting, and describe other update methods that are allowed once any of these axioms is dropped

TARK Conference 1998 Conference Paper

Using Counterfactuals in Knowledge-Based Programming

• Joseph Y. Halpern
• Yoram Moses

We show how counterfactuals can be added to the framework of knowledgebasedprogramsofFagin, Halpern, Moses, and Vardi [1995, 1997]. We show that counterfactuals allowus to capture in a natural waynotions like minimizingthe numberof messages that are sent, whereas attempts to formalize these notions without counterfactuals lead to some rather counterintuitivebehavior. We also show how knowledge-basedprograms with counterfactuals can capture subgame-perfectequilibria in games of perfect information.

UAI Conference 1997 Conference Paper

Defining Explanation in Probabilistic Systems

• Urszula Chajewska
• Joseph Y. Halpern

As probabilistic systems gain popularity and are coming into wider use, the need for a mechanism that explains the system's findings and recommendations becomes more critical. The system will also need a mechanism for ordering competing explanations. We examine two representative approaches to explanation in the literature---one due to G\" ardenfors and one due to Pearl---and show that both suffer from significant problems. We propose an approach to defining a notion of "better explanation'' that combines some of the features of both together with more recent work by Pearl and others on causality.

AIJ Journal 1997 Journal Article

Modeling belief in dynamic systems, part I: Foundations

• Nir Friedman
• Joseph Y. Halpern

Belief change is a fundamental problem in AI: Agents constantly have to update their beliefs to accommodate new observations. In recent years, there has been much work on axiomatic characterizations of belief change. We claim that a better understanding of belief change can be gained from examining appropriate semantic models. In this paper we propose a general framework in which to model belief change. We begin by defining belief in terms of knowledge and plausibility: an agent believes Φ if he knows that Φ is more plausible than ¬Φ. We then consider some properties defining the interaction between knowledge and plausibility, and show how these properties affect the properties of belief. In particular, we show that by assuming two of the most natural properties, belief becomes a KD45 operator. Finally, we add time to the picture. This gives us a framework in which we can talk about knowledge, plausibility (and hence belief), and time, which extends the framework of Halpern and Fagin for modeling knowledge in multi-agent systems. We then examine the problem of “minimal change”. This notion can be captured by using prior plausibilities, an analogue to prior probabilities, which can be updated by “conditioning”. We show by example that conditioning on a plausibility measure can capture many scenarios of interest. In a companion paper, we show how the two best-studied scenarios of belief change, belief revision and belief update, fit into our framework.

UAI Conference 1997 Conference Paper

Probability Update: Conditioning vs. Cross-Entropy

• Adam J. Grove
• Joseph Y. Halpern

Conditioning is the generally agreed-upon method for updating probability distributions when one learns that an event is certainly true. But it has been argued that we need other rules, in particular the rule of cross-entropy minimization, to handle updates that involve uncertain information. In this paper we re-examine such a case: van Fraassen's Judy Benjamin problem, which in essence asks how one might update given the value of a conditional probability. We argue that -- contrary to the suggestions in the literature -- it is possible to use simple conditionalization in this case, and thereby obtain answers that agree fully with intuition. This contrasts with proposals such as cross-entropy, which are easier to apply but can give unsatisfactory answers. Based on the lessons from this example, we speculate on some general philosophical issues concerning probability update.

AAAI Conference 1996 Conference Paper

A Counterexample to Theorems of Cox and Fine

• Joseph Y. Halpern

Cox’ s well-known theorem justifying the use of probability is shown not to hold in finite domains. The counterexample also suggests that Cox’ s assumptions are insufficient to prove the result even in infinite domains. The same counterexample is used to disprove a result of Fine on comparative conditional probability.

UAI Conference 1996 Conference Paper

A Qualitative Markov Assumption and Its Implications for Belief Change

• Nir Friedman
• Joseph Y. Halpern

The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. Roughly, revision treats a surprising observation as a sign that previous beliefs were wrong, while update treats a surprising observation as an indication that the world has changed. In general, we would expect that an agent making an observation may both want to revise some earlier beliefs and assume that some change has occurred in the world. We define a novel approach to belief change that allows us to do this, by applying ideas from probability theory in a qualitative setting. The key idea is to use a qualitative Markov assumption, which says that state transitions are independent. We show that a recent approach to modeling qualitative uncertainty using plausibility measures allows us to make such a qualitative Markov assumption in a relatively straightforward way, and show how the Markov assumption can be used to provide an attractive belief-change model.

TARK Conference 1996 Conference Paper

Common Knowledge Revisited

• Ronald Fagin
• Joseph Y. Halpern
• Yoram Moses
• Moshe Y. Vardi

We consider the common-knowledge paradox raised in [HM90]: common knowledge is necessary for coordination, but common knowledge is unattainable in the real world because of temporal imprecision. We discuss two solutions to this paradox: (1) modeling the world with a coarser granularity, and (2) relaxing the requirements for coordination.

UAI Conference 1996 Conference Paper

Defining Relative Likelihood in Partially-Ordered Preferential Structures

• Joseph Y. Halpern

Starting with a likelihood or preference order on worlds, we extend it to a likelihood ordering on sets of worlds in a natural way, and examine the resulting logic. Lewis (1973) earlier considered such a notion of relative likelihood in the context of studying counterfactuals, but he assumed a total preference order on worlds. Complications arise when examining partial orders that are not present for total orders. There are subtleties involving the exact approach to lifting the order on worlds to an order on sets of worlds. In addition, the axiomatization of the logic of relative likelihood in the case of partial orders gives insight into the connection between relative likelihood and default reasoning.

AIJ Journal 1996 Journal Article

From statistical knowledge bases to degrees of belief

• Fahiem Bacchus
• Adam J. Grove
• Joseph Y. Halpern
• Daphne Koller

An intelligent agent will often be uncertain about various properties of its environment, and when acting in that environment it will frequently need to quantify its uncertainty. For example, if the agent wishes to employ the expected-utility paradigm of decision theory to guide its actions, it will need to assign degrees of belief (subjective probabilities) to various assertions. Of course, these degrees of belief should not be arbitrary, but rather should be based on the information available to the agent. This paper describes one approach for inducing degrees of belief from very rich knowledge bases, that can include information about particular individuals, statistical correlations, physical laws, and default rules. We call our approach the random-worlds method. The method is based on the principle of indifference: it treats all of the worlds the agent considers possible as being equally likely. It is able to integrate qualitative default reasoning with quantitative probabilistic reasoning by providing a language in which both types of information can be easily expressed. Our results show that a number of desiderata that arise in direct inference (reasoning from statistical information to conclusions about individuals) and default reasoning follow directly from the semantics of random worlds. For example, random worlds captures important patterns of reasoning such as specificity, inheritance, indifference to irrelevant information, and default assumptions of independence. Furthermore, the expressive power of the language used and the intuitive semantics of random worlds allow the method to deal with problems that are beyond the scope of many other nondeductive reasoning systems.

TARK Conference 1996 Conference Paper

Multi-Agent Only Knowing

• Joseph Y. Halpern
• Gerhard Lakemeyer

Levesque introduced a notion of "only knowing", with the goal of capturing certain types of nonmonotonic reasoning. Levesque's logic dealt with only the case of a single agent. Recently, both Halpern and Lakemeyer independently attempted to extend Levesque's logic to the multi-agent case. Although there are a number of similarities in their approaches, there are some significant differences. In this paper, we reexamine the notion of only knowing, going back to first principles. In the process, we point out some problems with the earlier definitions. This leads us to reconsider what the properties of only knowing ought to be. We provide an axiom system that captures our desiderata, and show that it has a semantics that corresponds to it. The axiom system has an added feature of interest: it includes a modal operator for satisfiability, and thus provides a complete axiomatization for satisfiability in the logic K45.

TARK Conference 1996 Conference Paper

On Ambiguities in the Interpretation of Game Trees

• Joseph Y. Halpern

Piccione and Rubinstein have pointed out ambiguities in the interpretation of games of imperfect recall. They focus on the notion of time consistency, and argue that a player in a game of imperfect recall may be time inconsistent, changing his strategy despite no new information and no change in his preferences. In this paper it is argued that the apparent time inconsistency arises, in part, from an inappropriate definition of the notion. That is only part of the problem though. It is shown that in some cases the apparent time inconsistency, and, more generally, ambiguity in interpreting games of imperfect recall, stems from the fact that information sets in such games do not in general capture all the relevant features of an agent's knowledge. A model is proposed, based on earlier work in the computer science literature, that does capture all these features.

AAAI Conference 1996 Conference Paper

Using Multi-Agent Systems to Represent Uncertainty

• Joseph Y. Halpern

I consider a logical framework for modeling uncertainty, based on the use of possible worlds, that incorporates knowledge, probability, and time. This turns out to be a powerful approach for modeling many problems of interest. I show how it can be used to give insights into (among other things) several wellknown puzzles.

AIJ Journal 1995 Journal Article

A nonstandard approach to the logical omniscience problem

• Ronald Fagin
• Joseph Y. Halpern
• Moshe Y. Vardi

We introduce a new approach to dealing with the well-known logical omniscience problem in epistemic logic. Instead of taking possible worlds where each world is a model of classical propositional logic, we take possible worlds which are models of a nonstandard propositional logic we call NPL, which is somewhat related to relevance logic. This approach gives new insights into the logic of implicit and explicit belief considered by Levesque and Lakemeyer. In particular, we show that in a precise sense agents in the structures considered by Levesque and Lakemeyer are perfect reasoners in NPL.

AIJ Journal 1995 Journal Article

Levesque's axiomatization of only knowing is incomplete

• Joseph Y. Halpern
• Gerhard Lakemeyer

We show that the axiomatization given by Levesque for his logic of “only knowing” [2], which he showed to be sound and complete for the unquantified version of the logic and conjectured to be complete for the full logic, is in fact incomplete.

UAI Conference 1995 Conference Paper

Plausibility Measures: A User's Guide

• Nir Friedman
• Joseph Y. Halpern

We examine a new approach to modeling uncertainty based on plausibility measures, where a plausibility measure just associates with an event its plausibility, an element is some partially ordered set. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures, belief functions, and possibility measures. The lack of structure in a plausibility measure makes it easy for us to add structure on an "as needed" basis, letting us examine what is required to ensure that a plausibility measure has certain properties of interest. This gives us insight into the essential features of the properties in question, while allowing us to prove general results that apply to many approaches to reasoning about uncertainty. Plausibility measures have already proved useful in analyzing default reasoning. In this paper, we examine their "algebraic properties," analogues to the use of + and * in probability theory. An understanding of such properties will be essential if plausibility measures are to be used in practice as a representation tool.

AIJ Journal 1995 Journal Article

The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic

• Joseph Y. Halpern

A well-known result of Ladner says that the satisfiability problem for K45, KD45, and S5 is NP-complete. This result implicitly assumes that there are infinitely many primitive propositions in the language; it is easy to see that the satisfiability problem for these logics becomes linear time if there are only finitely many primitive propositions in the language. By way of contrast, we show that the PSPACE-completeness results of Ladner and Halpern and Moses hold for the modal logics K n, T n, S4 n, n ⩾ 1, and K45 n, KD45 n, S5 n, n ⩾ 2, even if there is only one primitive proposition in the language. We go on to examine the effect on complexity of bounding the depth of nesting of modal operators. If we restrict to finite nesting, then the satisfiability problem is NP-complete for all the modal logics considered, but S4. If we then further restrict the language to having only finitely many primitive propositions, the complexity goes down to linear time in all cases.

TARK Conference 1994 Conference Paper

A Knowledge-Based Framework for Belief change, Part I: Foundations

• Nir Friedman
• Joseph Y. Halpern

We propose a general framework in which to study belief change. We begin by defining belief in terms of knowledge and plausibility: an agent believes ~oif he knows that ~pis true in all the worlds he considers most plausible. We then consider some properties defining the interaction between knowledge and plausibility, and show how these properties affect the properties of belief. In particular, we show that by assuming two of the most natural properties, belief becomes a KD45 operator. Finally, we add time to the picture. This gives us a framework in which we can talk about knowledge, plausibility (and hence belief), and time, which extends the framework of Halpern and Fagin [HF89] for modeling knowledge in multi-agent systems. We show that our framework is quite expressive and lets us model in a natural way a number of different scenarios for belief change. For example, we show how we can capture an analogue to prior probabilities, which can be updated by "conditioning". In a related paper, we show how the two best studied scenarios, beliefrevision and beliefupdate, fit into the framework.

TARK Conference 1994 Conference Paper

Algorithmic Knowledge

• Joseph Y. Halpern
• Yoram Moses
• Moshe Y. Vardi

The standard model of knowledge in multi-agent systems suffers from what has been called the logical omniscience problem: agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this turns out not to be a problem. Knowledge is viewed as being ascribed by the system designer to the agents; agents are not assumed to compute their knowledge in any way, nor is it assumed that they can necessarily answer questions based on their knowledge. Nevertheless, in many applications that we are interested in, agents need to act on their knowledge. In such applications, an externally ascribed notion of knowledge is insufficient: clearly an agent can base his actions only on what he explicitly knows. Furthermore, an agent that has to act on his knowledge has to be able to compute this knowledge; we do need to take into account the algorithms available to the agent, as well as the "effort" required to compute knowledge. In this paper, we show how the standard model can be modified in a natural way to take the computational aspects of knowledge into account. *Current address: Dept. of Computer Science, Rice University, P. O. Box 1892, Houston, TX 77251-1892,

AAAI Conference 1994 Conference Paper

Forming Beliefs about a Changing World

• Fahiem Bacchus
• Joseph Y. Halpern

The situation calculus is a popular technique for reasoning about action and change. However, its restriction to a firstorder syntax and pure deductive reasoning makes it unsuitable in many contexts. In particular, we often face uncertainty, due either to lack of knowledge or to some probabilistic aspects of the world. While attempts have been made to address aspects of this problem, most notably using nonmonotonic reasoning formalisms, the general problem of uncertainty in reasoning about action has not been fully dealt with in a logical framework. In this paper we present a theory of action that extends the situation calculus to deal with uncertainty. Our framework is based on applying the random-worlds approach of [BGHK94] to a situation calculus ontology, enriched to allow the expression of probabilistic action effects. Our approach is able to solve many of the problems imposed by incomplete and probabilistic knowledge within a unified framework. In particular, we obtain a default Markov property for chains of actions, a derivation of conditional independence from irrelevance, and a simple solution to the frame problem.

UAI Conference 1994 Conference Paper

Generating New Beliefs from Old

• Fahiem Bacchus
• Adam J. Grove
• Joseph Y. Halpern
• Daphne Koller

In previous work [BGHK92, BGHK93], we have studied the random-worlds approach -- a particular (and quite powerful) method for generating degrees of belief (i.e., subjective probabilities) from a knowledge base consisting of objective (first-order, statistical, and default) information. But allowing a knowledge base to contain only objective information is sometimes limiting. We occasionally wish to include information about degrees of belief in the knowledge base as well, because there are contexts in which old beliefs represent important information that should influence new beliefs. In this paper, we describe three quite general techniques for extending a method that generates degrees of belief from objective information to one that can make use of degrees of belief as well. All of our techniques are bloused on well-known approaches, such as cross-entropy. We discuss general connections between the techniques and in particular show that, although conceptually and technically quite different, all of the techniques give the same answer when applied to the random-worlds method.

AAAI Conference 1993 Conference Paper

Reasoning about Only Knowing with Many Agents

• Joseph Y. Halpern

We extend two notions of “only knowing”, that of Halpern and Moses [1984], and that of Levesque [1990], to many agents. The main lesson of this paper is that these approaches do have reasonable extensions to the multi-agent case. Our results also shed light on the single-agent case. For example, it was always viewed as significant that the HM notion of only knowing was based on S5, while Levesque’ s was based on K45. In fact, our results show that the HM notion is better understood in the context of K45. Indeed, in the singleagent case, the HM notion remains unchanged if we use K45 (or KD45) instead of S5. However, in the multiagent case, there are significant differences between K45 and S5. Moreover, all the results proved by Halpern and Moses for the single-agent case extend naturally to the multi-agent case for K45, but not for S5.

IJCAI Conference 1993 Conference Paper

Statistical Foundations for Default Reasoning

• Fahiem Bacchus
• Adam J. Grove
• Joseph Y. Halpern
• Daphne Koller

We describe a new approach to default, reason­ ing, based on a principle oi indifference among possible worlds. We interpret default rules as extreme statistical statements, thus obtaining a knowledge base KB comprised of statistical and first-order statements. We then assign equal probability to all worlds consistent with KB in order to assign a degree of belief to a state­ ment φ. The degree of belief can be used to de­ cide whether to defeasibly conclude φ. Various natural patterns of reasoning, such as a prefer­ ence for more specific defaults, indifference to irrelevant information, and the ability to com­ bine independent pieces of evidence, turn out to follow naturally from this technique. Further­ more, our approach is not restricted to default reasoning; it supports a spectrum of reasoning. , from quantitative to qualitative. It is also re­ lated to other systems for default reasoning. In particular, we show that the work of |Goldszmidt et al. , 1990], which applies maximum entropy ideas to --semantics, can be embedded in our framework.

AIJ Journal 1992 Journal Article

A guide to completeness and complexity for modal logics of knowledge and belief

• Joseph Y. Halpern
• Yoram Moses

We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with three particular points of emphasis: (1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief, (2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, and (3) we discuss how notions of common knowledge and distributed knowledge among a group of agents fit into the possible-worlds framework, As far as complexity is concerned, we show, among other results, that while the problem of deciding satisfiability of an S5 formula with one agent is NP-complete, the problem for many agents is PSPACE-complete. Adding a distributed knowledge operator does not change the complexity, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time.

STOC Conference 1992 Conference Paper

Asymptotic Conditional Probabilities for First-Order Logic

• Adam J. Grove
• Joseph Y. Halpern
• Daphne Koller

TARK Conference 1992 Conference Paper

The Expressive Power of the Kierarchical Approach to Modeling Knowledge and Common Knowledge

• Ronald Fagin
• John Geanakoplos
• Joseph Y. Halpern
• Moshe Y. Vardi

One approach to representing knowledge or belief of agents, which has been explored independently by economists (BSge and Eisele; Mertens and Zamir; Brandenburger and Dekel; Tan and Werlang) and by computer scientists (Fagin, Halpern, and Vardi) involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs about the state of the world, his beliefs about other agents' beliefs about the worlds, his beliefs about other agents' beliefs about other agents' beliefs about the worlds, etc. Economists and computer scientists differ, however, in the way they model beliefs. Economists prefer a probability-based framework, where belief is modeled as a probability distribution on the uncertainty space. In contrast, computer scientists prefer an information-based framework, where belief is modeled as a subset of the underlying space. The idea is that whatever is in the subset is believed to be possible, and whatever is not in the subset is believed to be impossible. We consider the question of when such an infinite hierarchy completely describes the uncertainty of the agents. We provide various necessary and sufficient conditions for this property. It turns out that the probability-based approach can be viewed as satisfying one of these conditions, which explains why the infinite hierarchy always completely describes the uncertainty of the agents in the probability-based approach. An interesting consequence of our conditions is that adequacy of an infinite hierarchy may depend on the "richness" of the states in the underlying state space. We also consider the question of whether an infinite hierarchy completely describes the uncertainty of the agents with respect to "interesting" sets of events and show that the answers depends on the definition of "interesting".

AIJ Journal 1992 Journal Article

Two views of belief: belief as generalized probability and belief as evidence

• Joseph Y. Halpern
• Ronald Fagin

Belief functions are mathematical objects defined to satisfy three axioms that look somewhat similar to the Kolmogorov axioms defining probability functions. We argue that there are (at least) two useful and quite different ways of understanding belief functions. The first is as a generalized probability function (which technically corresponds to the inner measure induced by a probability function). The second is as a way of representing evidence. Evidence, in turn, can be understood as a mapping from probability functions to probability functions. It makes sense to think of updating a belief if we think of it as a generalized probability. On the other hand, it makes sense to combine two beliefs (using, say, Dempster's rule of combination) only if we think of the belief functions as representing evidence. Many previous papers have pointed out problems with the belief function approach; the claim of this paper is that these problems can be explained as a consequence of confounding these two views of belief functions.

I&C Journal 1990 Journal Article

A logic for reasoning about probabilities

• Ronald Fagin
• Joseph Y. Halpern
• Nimrod Megiddo

We consider a language for reasoning about probability which allows us to make statements such as “the probability of E 1 is less than 1 3 ” and “the probability of E 1 is at least twice the probability of E 2, ” where E 1 and E 2 are arbitrary events. We consider the case where all events are measurable (i. e. , represent measurable sets) and the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) Nilsson's probabilistic logic. As we show elsewhere, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.

UAI Conference 1990 Conference Paper

A new approach to updating beliefs

• Ronald Fagin
• Joseph Y. Halpern

We define a new notion of conditional belief, which plays the same role for Dempster-Shafer belief functions as conditional probability does for probability functions. Our definition is different from the standard definition given by Dempster, and avoids many of the well-known problems of that definition. Just as the conditional probability Pr (lB) is a probability function which is the result of conditioning on B being true, so too our conditional belief function Bel (lB) is a belief function which is the result of conditioning on B being true. We define the conditional belief as the lower envelope (that is, the inf) of a family of conditional probability functions, and provide a closed form expression for it. An alternate way of understanding our definition of conditional belief is provided by considering ideas from an earlier paper [Fagin and Halpern, 1989], where we connect belief functions with inner measures. In particular, we show here how to extend the definition of conditional probability to non measurable sets, in order to get notions of inner and outer conditional probabilities, which can be viewed as best approximations to the true conditional probability, given our lack of information. Our definition of conditional belief turns out to be an exact analogue of our definition of inner conditional probability.

TARK Conference 1990 Conference Paper

A Nonstandard Approach to the Logical Omniscience Problem

• Ronald Fagin
• Joseph Y. Halpern
• Moshe Y. Vardi

We introduce a new approach to dealing with the well-known logical omniscience problem in epistemic logic. Instead of taking possible worlds where each world is a model of classical propositional logic, we take possible worlds which are models of a nonstandard propositional logic we call NPL, which is somewhat related to relevance logic. This approach gives new insights into the logic of implicit and explicit'belief considered by Levesque and Lakemeyer. In particular, we show that in a precise sense agents in the structures considered by Levesque and Lakemeyer are perfect reasoners in NPL.

AIJ Journal 1990 Journal Article

An analysis of first-order logics of probability

• Joseph Y. Halpern

We consider two approaches to giving semantics to first-order logics of probability. The first approach puts a probability on the domain, and is appropriate for giving semantics to formulas involving statistical information such as “The probability that a randomly chosen bird flies is greater than 0. 9. ” The second approach puts a probability on possible worlds, and is appropriate for giving semantics to formulas describing degrees of belief such as “The probability that Tweety (a particular bird) flies is greater than 0. 9. ” We show that the two approaches can be easily combined, allowing us to reason in a straightforward way about statistical information and degrees of belief. We then consider axiomatizing these logics. In general, it can be shown that no complete axiomatization is possible. We provide axiom systems that are sound and complete in cases where a complete axiomatization is possible, showing that they do allow us to capture a great deal of interesting reasoning about probability.

AAAI Conference 1990 Conference Paper

Two Views of Belief: Belief as Generalized Probability and Belief as Evidence

• Joseph Y. Halpern

Belief functions are mathematical objects defined to satisfy three axioms that look somewhat similar to the axioms defining probability functions. We argue that there are (at least) two useful and quite different ways of understanding belief functions. The first is as a generalized probability function (which technically corresponds to the lower envelope or i&mum of a family of probability functions). The second is as a way of representing evidence. Evidence, in turn, can be understood as a mapping from probability functions to probability functions. It makes sense to think of tipdating a belief if we think of it as a generalized probability. On the other hand, it makes sense to combine two beliefs (using, say, Dempster’ s t%Zeof combination) only if we think of the belief functions as representing evidence. Many previous papers have pointed out problems with the belief function approach; the claim of this paper is that these problems can be explained as a consequence of confounding these two views of belief functions.

FOCS Conference 1989 Conference Paper

Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract)

• Martín Abadi
• Joseph Y. Halpern

Decidability and expressiveness issues for two first-order logics of probability are considered. In one the probability is on possible worlds, whereas in the other it is on the domain. It turns out that in both cases it takes very little to make reasoning about probability highly undecidable. It is shown that, when the probability is on the domain, if the language contains only unary predicates, then the validity problem is decidable. However, if the language contains even one binary predicate, the validity problem is Pi /sub 1//sup 2/ as hard as elementary analysis with free predicate and function symbols. With equality in the language, even with no other symbol, the validity problem is at least as hard as that for elementary analysis, Pi /sub infinity //sup 1/. Thus, the logic cannot be axiomatized in either case. When the probability is on the set of possible worlds, the validity problem is Pi /sub 1//sup 2/ complete with as little as one unary predicate in the language, even without equality. With equality, Pi /sub infinity //sup 1/ hardness with only a constant symbol is obtained. In many applications it suffices to restrict attention to domains of a bounded size; it is shown that the logics are decidable in this case. >

I&C Journal 1989 Journal Article

Reasoning about procedures as parameters in the language L4

• Steven M. German
• Edmund M. Clarke
• Joseph Y. Halpern

We provide a sound and relatively complete axiom system for partial correctness assertions in an Algol-like language with procedures passed as parameters, but with no global variables (traditionally known as the language L4). The axiom system allows us to reason syntactically about programs and to construct proofs for assertions about complicated programs from proofs of assertions about their components. Such an axiom system for a language with these features had been sought by a number of researchers, but no previously published solution has been entirely satisfactory. Our axiom system extends the natural style of reasoning used in previous Hoare axiom systems to programs with procedures of higher type. The details of the proof that our axiom system is relatively complete in the sense of Cook may be of independent interest, because we introduce results about expressiveness for programs with higher types that are useful beyond the immediate problem of the language L4. We also prove a new incompleteness result that applies to our logic and to similar Hoare logics.

IJCAI Conference 1989 Conference Paper

Uncertainty, Belief, and Probability Ronald

• F agin
• Joseph Y. Halpern

STOC Conference 1988 Conference Paper

A Knowledge-Based Analysis of Zero Knowledge (Preliminary Report)

• Joseph Y. Halpern
• Yoram Moses
• Mark R. Tuttle

TARK Conference 1988 Conference Paper

Reasoning about Knowledge and Probability

• Ronald Fagin
• Joseph Y. Halpern

We provide a model for reasoning about knowledge anti probability together. We a. llow explicit mention of probabilities in formulas, so that our language has formulas tha. t essentia. lly say "a. ccording to agent i, formula. (p holds with probability a. t least o~. " The language is powerfid enough to allow reasoning a~bout higher-order probabilities, as well as allowing explicit comparisons of the probabilities an agent places on distinct events. We present a general framework for interpreting such formulas, a. nd consider various properties that might hold of the interrelationship between agents' subjective probability spaces at different states. We provide a. complete a. xiomatiza. tion for rea. soning about knowledge a. nd probability, prove a. small model property, and obtain decision procedures. We then consider the effects of adding common knowledge and a. probabilistic va. ria. nt of common knowledge to the language.

STOC Conference 1988 Conference Paper

Reasoning about Knowledge and Time in Asynchronous Systems

• Joseph Y. Halpern
• Moshe Y. Vardi

TARK Conference 1988 Conference Paper

Reasoning About Knowledge: A Tutorial

• Joseph Y. Halpern

In this tutorial talk, we will first review the standard possible-worlds definition of knowledge. We then give a method of modelling interactive systems as sets of runs, where a run is a complete description of what happens in the system over time. This appraoch is applicable to modelling a wide range of phenomena, including distributed protocols, games, and conversations. We show how to interpret knowledge in a distributed system and use this approach to analyze the coordinated attack problem. All the material in this talk is taken from [HF85, HM84] and the overview paper [Ha187].

AIJ Journal 1987 Journal Article

A logic to reason about likelihood

• Joseph Y. Halpern
• Michael O. Rabin

We present a logic LL which uses a modal operator L to help capture the notion of being likely. Despite the fact that likelihood is not assigned quantitative values through probabilities, LL captures many of the properties of likelihood in an intuitively appealing way. We give a possible-worlds style semantics to LL, and, using standard techniques of modal logic, we give a complete axiomatization for LL and show that satisfiability of LL formulas can be decided in exponential time. We discuss how the logic might be used in areas such as medical diagnosis, where decision making in the face of uncertainties is crucial. We conclude by using LL to give a formal proof of correctness of some aspects of a protocol for exchanging secrets.

I&C Journal 1987 Journal Article

A new look at fault-tolerant network routing

• Danny Dolev
• Joseph Y. Halpern
• Barbara Simons
• H.Raymond Strong

We model a communication network as a graph in which a processor is a node and a communication link is an edge. A routing for such a network is a fixed path, or route, between each pair of nodes. Given a network with a predefined routing, we study the effects of faulty components on the routing. Of particular interest is the number of routes along which a message must travel between any two non-faulty nodes. This problem is analyzed for specific families of graphs and for classes of routings. We also give some bounds for general versions of the problem. Finally, we conclude with one of the most important contributions of this paper, a list of interesting and apparently difficult open problems.

AIJ Journal 1987 Journal Article

Belief, awareness, and limited reasoning

• Ronald Fagin
• Joseph Y. Halpern

Several new logics for belief and knowledge are introduced and studied, all of which have the property that agents are not logically omniscient. In particular, in these logics, the set of beliefs of an agent does not necessarily contain all valid formulas. Thus, these logics are more suitable than traditional logics for modelling beliefs of humans (or machines) with limited reasoning capabilities. Our first logic is essentially an extension of Levesque's logic of implicit and explicit belief, where we extend to allow multiple agents and higher-level belief (i. e. , beliefs about beliefs). Our second logic deals explicitly with “awareness, ” where, roughly speaking, it is necessary to be aware of a concept before one can have beliefs about it. Our third logic gives a model of “local reasoning, ” where an agent is viewed as a “society of minds, ” each with its own cluster of beliefs, which may contradict each other.

TARK Conference 1986 Conference Paper

Reasoning About Knowledge: An Overview

• Joseph Y. Halpern

In this overview paper, I will attempt to identify and describe some of the common threads that tie together work in reasoning about knowledge in such diverse fields as philosophy, economics, linguistics, artificial intelligence, and theoretical computer sciencce. I will briefly discuss some of the more recent work, particularly in computer science, and suggest some lines for future research.

STOC Conference 1986 Conference Paper

The Complexity of Reasoning about Knowledge and Time: Extended Abstract

• Joseph Y. Halpern
• Moshe Y. Vardi

IJCAI Conference 1985 Conference Paper

A Guide to the Modal Logics of Knowledge and Belief: Preliminary Draft

• Joseph Y. Halpern
• Yoram O. Moses

IJCAI Conference 1985 Conference Paper

Belief, Awareness, and Limited Reasoning: Preliminary Report

• Ronald Fagin
• Joseph Y. Halpern

STOC Conference 1985 Conference Paper

Optimal Precision in the Presence of Uncertainty (Preliminary Version)

• Joseph Y. Halpern
• Nimrod Megiddo
• Ashfaq A. Munshi

FOCS Conference 1984 Conference Paper

A Model-Theoretic Analysis of Knowledge: Preliminary Report

• Ronald Fagin
• Joseph Y. Halpern
• Moshe Y. Vardi

Understanding knowledge is a fundamental issue in many disciplines. In computer science, knowledge arises not only in the obvious contexts (such as knowledge-based systems), but also in distributed systems (where the goal is to have each processor "know" something, as in Byzantine agreement). A general semantic model of knowledge is introduced, to allow reasoning about statements such as "He knows that I know whether or not she knows whether or not it is raining. " This approach more naturally models a state of knowledge than previous proposals (including Kripke structures). Using this notion of model, a model theory for knowledge is developed. This theory enables one to interpret such notions as a "finite amount of information" and "common knowledge" in different contexts.

STOC Conference 1984 Conference Paper

A New Look at Fault Tolerant Network Routing

• Danny Dolev
• Joseph Y. Halpern
• Barbara Simons
• H. Raymond Strong

AAAI Conference 1984 Conference Paper

Likelihood, Probability, and Knowledge

• Joseph Y. Halpern

The modal logic LL was introduced by Halpern and Rabin [HR] as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible.

STOC Conference 1984 Conference Paper

On the Possibility and Impossibility of Achieving Clock Synchronization

• Danny Dolev
• Joseph Y. Halpern
• H. Raymond Strong

NMR Workshop 1984 Conference Paper

Towards a Theory of Knowledge and Ignorance: Preliminary Report

• Joseph Y. Halpern
• Yoram Moses

STOC Conference 1983 Conference Paper

A Logic to Reason about Likelihood

• Joseph Y. Halpern
• Michael O. Rabin

We present a logic LL which uses a modal operator L to help capture the notion of likely. Despite the fact that no use is made of numbers, LL can capture many of the properties of likelihood in an intuitively appealing way. Using standard techniques of modal logic, we give a complete axiomatization for LL and show that satisfiability of LL formulas can be decided in exponential time. We discuss how the logic might be used in areas where decision making is crucial, such as management and medical diagnosis, and conclude by using LL to give a formal proof of correctness of a protocol for exchanging secrets.

TCS Journal 1983 Journal Article

The propositional dynamic logic of deterministic, well-structured programs

• Joseph Y. Halpern
• John H. Reif

We consider a restricted propositional dynamic logic, Strict Deterministic Propositional Dynamic Logic (SDPDL), which is appropriate for reasoning about deterministic well-structured programs. In contrast to PDL, for which the validity problem is known to be complete in deterministic exponential time, the validity problem for SDPDL is shown to be polynomial space complete. We also show that SDPDL is less expressive than PDL, and give a complete axiomatization for it. The results rely on structure theorems for models of satisfiable SDPDL formulas, and the proofs give insight into the effects of nondeterminism on intractability and expressiveness in program logics.

STOC Conference 1982 Conference Paper

Decision Procedures and Expressiveness in the Temporal Logic of Branching Time

• E. Allen Emerson
• Joseph Y. Halpern

FOCS Conference 1982 Conference Paper

Deterministic Process Logic Is Elementary

• Joseph Y. Halpern

Process Logic (PL) is a language for reasoning about the behavior of a program during a computation, while Propositional Dynamic Logic (PDL) can only reason about the input-output states of a program. Nevertheless, we show that to each PL model M there corresponds in a natural way a PDL, model Mt such that every path in M is represented by a state in Mt. Moreover, to every PL formula p there corresponds a PDL formula pt, whose length is linear in that of p, such that p is true of a path in M iff pt is true of the state which represents that path in Mt. We then show that p is satisfiable iff pt is satisfiable in a finite PDL model with special properties which we call a pseudomodel. The size of the pseudomodel is in general nonelementary, and depends on the depth of nesting of the suf operator in PL. However, for PDL, a deterministic version of PL, the pseudomodel has size 2|p|2, giving us a decision procedure for PDL which runs in deterministic time O(2cn2). These results suggest that it is the interaction between nondeterministic programs and thc suf operator that makes the general decision problem for PL so difficult.

STOC Conference 1981 Conference Paper

Equations between Regular Terms and an Application to Process Logic

• Ashok K. Chandra
• Joseph Y. Halpern
• Albert R. Meyer
• Rohit Parikh

FOCS Conference 1981 Conference Paper

The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract)

• Joseph Y. Halpern
• John H. Reif

We consider a restricted propositional dynamic logic, Strict Deterministic Propositional Dynamic Logic (SDPDL), which is appropriate for reasoning about deterministic well-structured programs. In contrast to PDL, for which the validity problem is known to be complete in deterministic exponential time, the validity problem for SDPDL is shown to be polynomial space complete. We also show that SDPDL is less expressive than PDL. The results rely on structure theorems for models of satisfiable SDPDL formulas, and the proofs give insight into the effects of nondeterminism on intractability and expressiveness in program logics.