Joseph Y. Halpern

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

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...

An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine Agreement with Optimal (2009)

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...

Great Expectations. Part II: Generalized Expected Utility as a Universal Decision Rule (2009)

Consider an asynchronous system with private channels and n processes, up to t of which may be faulty. We settle a longstanding open question by providing a Byzantine agreement protocol that...

Game Theory with Costly Computation (2009)

Abstract Many different rules for decision making have been introduced in the literature. We showthat a notion of generalized expected utility proposed in [Chu and Halpern 2003] is a universal

Characterizing Solution Concepts in Games Using Knowledge-Based Programs (2009)

Defaults and Normality in Causal Structures (2009)

We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of knowledge-based...

Secrecy in multiagent systems (2009)

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...

Joseph Y. Halpern, Kevin R. O’neill

We introduce a general framework for reasoning about secrecy requirements in multiagent systems. Our definitions extend earlier definitions of secrecy and nondeducibility given by Shannon and...

1 A Minimum-Energy Path-Preserving Topology-Control Algorithm (2009)

Li (erran Li, Joseph Y. Halpern

Abstract — The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In general, it is not energy efficient to use the communication network...

A Game-Theoretic Analysis of Updating Sets of Probabilities (2009)

Knowledge-Based Synthesis of Distributed Systems Using Event Structures (2009)

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...

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

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...

Constructive Decision Theory (2009)

Blume, Lawrence, Easley, David, Halpern, Joseph Y.

In most contemporary approaches to decision making, a decision problem is described by a sets of states and set of outcomes, and a rich set of acts, which are functions from states to outcomes over...

Reasoning About Knowledge of Unawareness Revisited (2009)

Halpern, Joseph Y., Rego, Leandro

In earlier work, 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...

A Logical Characterization of Iterated Admissibility (2009)

Halpern, Joseph Y., Pass, Rafael

Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (i.e., iterated deletion of weakly dominated strategies) where uncertainty is represented using...

Updating Sets of Probabilities (2009)

Grove, Adam J., Halpern, Joseph Y.

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...

Manipulating Scrip Systems: Sybils and Collusion (2009)

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

Game-theoretic analyses of distributed and peer-to-peer systems typically use the Nash equilibrium solution concept, but this explicitly excludes the possibility of strategic behavior involving more...

Multiagent Learning in Large Anonymous Games (2009)

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

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...

Abstract (2009)

David J. Martin, Johannes Gehrke, Joseph Y. Halpern

Internet search results are a growing and highly profitable advertising platform. Search providers auction advertising slots to advertisers on their search result pages. Due to the high volume of...

AND (2008)

E. Allen Emerson, Joseph Y. Halpern

Abstract. The differences between and appropriateness of branching versus linear time temporal logic for reasoning about concurrent programs are studied. These issues have been previously considered...

Reasoning About Common Knowledge with Infinitely Many Agents (2008)

Joseph Y. Halpern, Richard A. Shore

Abstract Complete axiomatizations and exponential-time decisionprocedures are provided for reasoning about knowledge and common knowledge when there are infinitely manyagents. The results show that...

Iterated Regret Minimization: A More Realistic Solution Concept (2008)

Halpern, Joseph Y., Pass, Rafael

For some well-known games, such as the Traveler's Dilemma or the Centipede Game, traditional game-theoretic solution concepts--and most notably Nash equilibrium--predict outcomes that are not...

Toward Expressive and Scalable Sponsored Search Auctions (2008)

Martin, David J., Gehrke, Johannes, Halpern, Joseph Y.

Internet search results are a growing and highly profitable advertising platform. Search providers auction advertising slots to advertisers on their search result pages. Due to the high volume of...

Game Theory with Costly Computation (2008)

Halpern, Joseph Y., Pass, Rafael

We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the...

An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine Agreement with Optimal Resilience (2008)

Abraham, Ittai, Dolev, Danny, Halpern, Joseph Y.

Consider an asynchronous system with private channels and $n$ processes, up to $t$ of which may be faulty. We settle a longstanding open question by providing a Byzantine agreement protocol that...

A Formal Foundation for XrML (2008)

Halpern, Joseph Y., Weissman, Vicky

XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of...

Beyond Nash Equilibrium: Solution Concepts for the 21st Century (2008)

Defaults and Normality in Causal Structures (2008)

Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However, it suffers from numerous problems. Some are well known in the game theory community; for example, the Nash...

The Lotus-Eater Attack (2008)

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...

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

Many protocols for distributed and peer-to-peer systems have the feature that nodes will stop providing service for others once they have received a certain amount of service. Examples include...

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

Journal of Arti cial Intelligence Research 10 (1999) 67{85 Submitted 6/98 � published 2/99 A Counterexample to Theorems of Cox and Fine (2008)

A first-order conditional logic is considered, with semantics given by a variant of epsilon-semantics, where p -> q means that Pr(q | p) approaches 1 super-polynomially --faster than any inverse...

Danny Dolev, Joseph Y Halpern, Barbara Simons, H Raymond Strong

Cox's well-known theorem justifying the use of probability is shown not to hold in nite domains. The counterexample also suggests that Cox's assumptions are insu cient to prove the result...

AND (2008)

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...

Jerusalem in 1971, an (2008)

Yoram Moses, Danny Dolev, Joseph Y Halpern

1986. He will be spending the 1985/6 school year as a postdoetoralfellow at MIT. His major research interests are distributed systems, artificial intelligence, and the methodological foundations of...

On the unusual effectiveness of Logic in computer science (2008)

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....

Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi, Victor Vianu

“SOMETIMES ” AND “NOT NEVER ” REVISITED: ON BRANCHING VERSUS LINEAR TIME (PRELIMINARY REPORT) (2008)

E. Allen Emersonl, Joseph Y. Halpern

systems (2008)

On the unusual effectiveness of Logic in computer science (2008)

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete...

Joseph Y. Halpern, Robert Harper, Moshe Y. Vardi, Neil Immerman

A Data-Acquisition Model for Learning and Cognitive Development and Its Implications for Autism (2008)

Lotem, Arnon, Halpern, Joseph Y.

A data-driven model of learning is proposed, where a network of nodes and links is constructed that represents what has been heard and observed. Autism is viewed as the consequence of a disorder in...

A Data-Acquisition Model for Learning and Cognitive Development and Its Implications for Autism (2008)

Lotem, Arnon, Halpern, Joseph Y.

A data-driven model of learning is proposed, where a network of nodes and links is constructed that represents what has been heard and observed. Autism is viewed as the consequence of a disorder in...

www.cwi.nl/~pdg (2008)

A Data-Acquisition Model for Learning and Cognitive Development and Its Implications for Autism (2008)

www.cs.cornell.edu/home/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...

Arnon Lotem, Zoology Dept, Joseph Y. Halpern

A data-driven model of learning is proposed, where a network of nodes and links is constructed that represents what has been heard and observed. Autism is viewed as the consequence of a disorder in...

www.cwi.nl/~pdg (2008)

Hana Chockler, Joseph Y. Halpern

www.cs.cornell.edu/home/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...

and (2008)

Even when a system is proven to be correct with respect to a specification, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the...

Characterizing Solution Concepts in Games Using Knowledge-Based Programs (2008)

We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of knowledge-based...

AND (2008)

On the unusual effectiveness of Logic in computer science (2008)

Abstract. Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of...

Joseph Y. Halpern, Ý Robert, Harper Þ Neil, Immerman Ü Phokion, G. Kolaitis

Computer Science Dept, Joseph Y. Halpern, Adam J. Grove, 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...

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

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences ϕ...

Joseph Y. Halpern, Sabina Petride

Consider a distributed system N in which each agent has an input value and each communication link has a weight. Given a global function, that is, a function f whose value depends on the whole...

Leandro C. 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...

What Causes a System to Satisfy a Specification? (2008)

Hana Chockler, Joseph Y. Halpern, Orna Kupferman

Even when a system is proven to be correct with respect to a specification, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the...

Characterizing and Reasoning about Probabilistic and Non-Probabilistic Expectation (2008)

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,...

Representation] Representation languages General Terms The[~ry (2008)

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible...

Ronald Fagin, Joseph Y. Halpern, Y. Vardi

Chuungtse and Hueltse bud strolled on to the bridge over the Har), \vhen [he fornler observed. ‘ ” See how the small fish are darting about ~ That u the happiness of the fish, ”- ‘ You are...

Int J Game Theory (1999) 28:331-365 (2008)

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...

Springer Verlag, Ronald Fagin, John Geanakoplos, Joseph Y. Halpern, Moshe Y. Vardi

International

Technical Addendum Cox's Theorem Revisited (2008)

ASYMPTOTIC CONDITIONAL PROBABILITIES: THE UNARY (2008)

The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which aCox-style theorem can be proved are provided, although all are rather strong...

THE JOURXAL OF SYMBOLIC LOGIC Volume 57. Number 3. Sept. 1992 WHAT IS AN INFERENCE RULE? (2008)

Abstract. Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given firstorder...

Ronald Fagin, Joseph Y. Halpern, Y. Vardl

Abstract. What is an inference rule? This question does not have a unique ansu'er. One usually finds two distinct standard answers in the literature: validity inference (u k> I+O if for every...

Erratum: Zero-One Laws in Modal Logic (2008)

Gossip-Based Ad Hoc Routing halpern,lili¡ (2008)

Jean-Marie Le Bars [2002] showed that the 0-1 law for frame satisfiability fails for the formula q ^ ~p ^ 22((p. q) ) ~3(p. q)) ^ 23p. (1) This, unfortunately, contradicts one of the main theorems in...

Causality, Responsibility, and Blame: A Structural-Model Approach (2008)

Abstract—Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based...

This talk will provide an overview of work that I have done with Hana Chockler, Orna Kupferman, and Judea Pearl [1, 2, 10, 9] on defining notions such as causality, explanation, responsibility, and...

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

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences ϕ...

ASYMPTOTIC CONDITIONAL PROBABILITIES: THE UNARY (2008)

A new approach to updating beliefs (2008)

Abstract. Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given firstorder...

P. P. Bonissone, M. Henrion, Ln. Kanal, Ronald Fagin, Joseph Y. Halpern

Abstract: 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...

Computer science and game theory: A brief survey (2008)

Joseph Y. Halpern, Rafael Pass

We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the...

Iterated Regret Minimization: A More Realistic Solution Concept (2008)

Lower bounds on implementing robust and resilient mediators (2008)

Abstract For some well-known games, such as the Traveler's Dilemma or the Centipede Game, traditional game-theoretic solution concepts--and most notably Nash equilibrium--predict outcomes that...

Iterated Regret Minimization: A More Realistic Solution Concept (2008)

We provide new and tight lower bounds on the ability of players to implement equilibria using cheap talk, that is, just allowing communication among the players. One of our main results is that, in...

Joseph Y. Halpern, Rafael Pass

For some well-known games, such as the Traveler’s Dilemma or the Centipede Game, traditional game-theoretic solution concepts—and most notably Nash equilibrium—predict outcomes that are not...

Generating New Beliefs From Old Fahiem Bacchus (2007)

Computer Science Dept, 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...

z (2007)

Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi

k Victor Vianu

z (2007)

Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi

k Victor Vianu

Full Abstraction and Expressive Completeness for FP (2007)

Joseph Y. Halpern, Edward L. Wimmers

ion and Expressive Completeness for FP Joseph Y. Halpern Edward L. Wimmers IBM Almaden Research Center San Jose, CA 95120 email: halpern@ibm.com, wimmers@ibm.com Abstract: We consider issues related...

Errata: "The relationship between knowledge, belief, and certainty" (2007)

Joseph Halpern Cornell, Joseph Y. Halpern, As Pr(s)(t

F51.72> = fs : PR(s)([s]) = 1g. Then F is almost-uniform if AS1. PR(s)(GF ) = 1 for all s 2 S AS2. PR(s)(t) = P u PR(s)(u) \Theta PR(u)(t). By way of contrast, F is uniform if GF = S. Note that if...

2 (2007)

Adam J. Grove, Joseph Y. Halpern

Abstract. Consider an agent (or expert system) with a knowledge base KB that includes statistical information (such as "90 % of patients with jaundice have hepatitis"), first-order...

Updating Probabilities (2007)

P. D. Gronwald, J. Y. Halpern, Peter D. Grijnwald, Joseph Y. Halpern

CWI is a founding member of ERCIM, the European Research Consortium for Informatics and Mathematics. CWI's research has a theme-oriented structure and is grouped into four clusters. Listed below...

1 Gossip-Based Ad Hoc Routing (2007)

Abstract--- Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based...

www.cwi.nl/pdg (2007)

On the unusual effectiveness of Logic in computer science (2007)

www.cs.cornell.edu/home/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...

Joseph Y. Halpern, Ý Robert, Harper Þ Neil, Immerman Ü Phokion, G. Kolaitis

www.cwi.nl/~pdg (2007)

Peter D. Grunwald, Joseph Y. Halpern

www.cs.cornell.edu/home/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...

www.cwi.nl/~pdg (2007)

Peter D. Grunwald, Joseph Y. Halpern

www.cs.cornell.edu/home/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...

By (2007)

Nit Friedman, Joseph Y. Halpern, Yoav Shoham

ii

1 Gossip-Based Ad Hoc Routing (2007)

Zygmunt Haas, Joseph Y. Halpern, Li Li

Abstract--- Many ad hoc routing protocols are based on (some variant of) flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based...

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...

z (2007)

Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion G. Kolaitis, Moshe Y. Vardi

k Victor Vianu

Journal of Arti cial Intelligence Research 14 (2001) 359{389 Submitted 10/00; published 6/01 Conditional Plausibility Measures and Bayesian Networks (2007)

1 A Decision-Theoretic Approach to Resource Allocation in Wireless Multimedia Networks (2007)

A general notion of algebraic conditional plausibility measures is de ned. Probability measures, ranking functions, possibility measures, and (under the appropriate de nitions) sets of probability...

Zygmunt Haas, Joseph Y. Halpern, Li Li, Stephen B. Wicker

Abstract--- The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless...

Forming beliefs about a changing world Fahiem Bacchus (2007)

Revisiting the Foundations of Authentication Logics (2007)

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....

Causes and Explanations: A Structural-Model (2007)

In this paper, we make the point that the problems with logics in the BAN tradition are not with the idea of basing reasoning about security protocols using epistemic notions, but with some of the...

Approach Part Ii, Joseph Y. Halpern

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

A Game-Theoretic Analysis of Updating Sets of Probabilities (2007)

Grunwald, Peter D., Halpern, Joseph Y.

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...

Fahiem Bacchus (2007)

Adam Grove, Joseph Y. Halpern, Daphne Koller

A Response to "Believing on the basis of evidence"

When Ignorance is Bliss (2007)

Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic (2007)

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...

Halpern, Joseph Y., Rêgo, Leandro Chaves

There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all...

A Knowledge-Based Analysis of Global Function Computation (2007)

Halpern, Joseph Y., Petride, Sabina

Consider a distributed system N in which each agent has an input value and each communication link has a weight. Given a global function, that is, a function f whose value depends on the whole...

Generalized Solution Concepts in Games with Possibly Unaware Players (2007)

Rego, Leandro C., Halpern, Joseph Y.

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, we proposed a framework for representing and...

Efficiency and Nash Equilibria in a Scrip System for P2P Networks (2007)

Friedman, Eric J., Halpern, Joseph Y., Kash, Ian

A model of providing service in a P2P network is analyzed. It is shown that by adding a scrip system, a mechanism that admits a reasonable Nash equilibrium that reduces free riding can be obtained....

Optimizing Scrip Systems: Efficiency, Crashes, Hoarders, and Altruists (2007)

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

We discuss the design of efficient scrip systems and develop tools for empirically analyzing them. For those interested in the empirical study of scrip systems, we demonstrate how characteristics of...

Worst-Case Background Knowledge for Privacy-Preserving Data Publishing (2007)

Martin, David J., Kifer, Daniel, Machanavajjhala, Ashwin, Gehrke, Johannes, Halpern, Joseph Y.

Recent work has shown the necessity of considering an attacker's background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what...

Lower Bounds on Implementing Robust and Resilient Mediators (2007)

Abraham, Ittai, Dolev, Danny, Halpern, Joseph Y.

We consider games that have (k,t)-robust equilibria when played with a mediator, where an equilibrium is (k,t)-robust if it tolerates deviations by coalitions of size up to k and deviations by up to...

Extensive Games with Possibly Unaware Players (2007)

Halpern, Joseph Y., Rêgo, Leandro C.

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete...

Computer Science and Game Theory: A Brief Survey (2007)

Dealing With Logical Omniscience: Expressiveness and Pragmatics (2007)

There has been a remarkable increase in work at the interface of computer science and game theory in the past decade. In this article I survey some of the main themes of work in the area, with a...

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible...

Worst-case background knowledge in privacy (2007)

We consider games that have (k, t)-robust equilibria when played with a mediator, where an equilibrium is (k, t)-robust if it tolerates deviations by coalitions of size up to k and deviations by up...

David J. Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, Joseph Y. Halpern

Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what...

Worst-case background knowledge in privacy (2007)

We consider games that have (k, t)-robust equilibria when played with a mediator, where an equilibrium is (k, t)-robust if it tolerates deviations by coalitions of size up to k and deviations by up...

David J. Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, Joseph Y. Halpern

Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what...

Worst-case background knowledge in privacy (2007)

David J. Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, Joseph Y. Halpern

Recent work has shown the necessity of considering an attacker’s background knowledge when reasoning about privacy in data publishing. However, in practice, the data publisher does not know what...

Characterizing the NP-PSPACE gap in the satisfiability problem for modal logic (2007)

Joseph Y. Halpern, Ro Chaves Rêgo

There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all...

Characterizing the NP-PSPACE gap in the satisfiability problem for modal logic (2007)

On Definability in Multimodal Logic I. Basic Notions ∗ (2007)

There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all...

Lower bounds on implementing robust and resilient mediators (2007)

Three notions of definability in multimodal logic are considered. Two are analogous to the notions of explicit definability and implicit definability introduced by Beth in the context of first-order...

On Definability in Multimodal Logic II. Defining Knowledge in Terms of Belief ∗ (2007)

We provide new and tight lower bounds on the ability of players to implement equilibria using cheap talk, that is, just allowing communication among the players. One of our main results is that, in...

The question of whether knowledge is definable in terms of belief, which has played an important role in epistemology for the last fifty years, is studied here in the framework of epistemic and...

On Definability in Multimodal Logic II. Defining Knowledge in Terms of Belief ∗ (2007)

We provide new and tight lower bounds on the ability of players to implement equilibria using cheap talk, that is, just allowing communication among the players. One of our main results is that, in...

On Definability in Multimodal Logic I. Basic Notions ∗ (2007)

The question of whether knowledge is definable in terms of belief, which has played an important role in epistemology for the last fifty years, is studied here in the framework of epistemic and...

Game Theory with Costly Computation (2007)

Three notions of definability in multimodal logic are considered. Two are analogous to the notions of explicit definability and implicit definability introduced by Beth in the context of first-order...

Joseph Y. Halpern, Rafael Pass

We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the...

Characterizing Solution Concepts in Games Using Knowledge-Based Programs (2006)

Halpern, Joseph Y., Moses, Yoram

We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of...

Rational Secret Sharing and Multiparty Computation: Extended Abstract (2006)

Halpern, Joseph Y., Teague, Vanessa

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...

Using Sets of Probability Measures to Represent Uncertainty (2006)

Expressing Security Properties Using Selective Interleaving Functions (2006)

I explore the use of sets of probability measures as a representation of uncertainty.

Halpern, Joseph Y., Petride, Sabina

McLean's notion of Selective Interleaving Functions (SIFs) is perhaps the best-known attempt to construct a framework for expressing various security properties. We examine the expressive power of...

Modeling Adversaries in a Logic for Security Protocol Analysis (2006)

Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic (2006)

Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers only...

Halpern, Joseph Y., Rego, Leandro Chaves

There has been a great of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the validity problem for all logics...

Reasoning About Knowledge of Unawareness (2006)

Halpern, Joseph Y., Rego, Leandro Chaves

Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an...

Using First-Order Logic to Reason about Policies (2006)

Halpern, Joseph Y., Weissman, Vicky

A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of (multi-sorted) first-order logic can be used to represent and reason about policies....

Reasoning about knowledge of unawareness (2006)

Joseph Y. Halpern, Leandro Chaves Rêgo

Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an...

Extensive games with possibly unaware players (2006)

Joseph Y. Halpern, Ro Chaves Rêgo

1 Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete...

Reasoning about knowledge of unawareness (2006)

Joseph Y. Halpern, Leandro Chaves Rêgo

Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an...

A nonstandard characterization of sequential equilibriu, perfect equilibrium, and proper equilibrium. Unpublished manuscript (2006)

Reasoning about knowledge of unawareness (2006)

New characterizations of sequential equilibrium, perfect equilibrium, and proper equilibrium are provided that use nonstandard probability. It is shown that there exists a belief system µ such that...

A nonstandard characterization of sequential equilibriu, perfect equilibrium, and proper equilibrium. Unpublished manuscript (2006)

Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an...

Evidence with Uncertain Likelihoods (2005)

New characterizations of sequential equilibrium, perfect equilibrium, and proper equilibrium are provided that use nonstandard probability. It is shown that there exists a belief system µ such that...

When Ignorance is Bliss (2005)

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...

Grunwald, Peter D., Halpern, Joseph Y.

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...

Interactive Unawareness Revisited (2005)

Halpern, Joseph Y., Rego, Leandro C.

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...

Probabilistic Algorithmic Knowledge (2005)

Knowledge-based synthesis of distributed systems using event structures (2005)

The framework of 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...

Mark Bickford, Robert C. Constable, Joseph Y. Halpern, Sabina Petride

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...

Interactive Unawareness Revisited (2005)

Joseph Halpern Computer, Joseph Y. Halpern, Leandro Chaves Rêgo

We analyze a model of interactive unawareness introduced by Heifetz, Meier and Schipper (HMS).

Knowledge-based synthesis of distributed systems using event structures (2005)

Mark Bickford, Robert C. 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...

Interactive unawareness revisited (2005)

Joseph Y. Halpern, Leandro Chaves Rêgo

edge (TARK05).

A cone-based distributed topology-control algorithm for wireless multi-hop networks (2005)

Li (erran Li, Joseph Y. Halpern, Paramvir Bahl, Senior Member, Senior Member, Yi-min Wang, ...

Abstract—The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed...

Probabilistic Algorithmic Knowledge (2005)

Knowledge-based synthesis of distributed systems using event structures (2005)

The framework of 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...

Mark Bickford, Robert C. 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...

Causes and Explanations: A Structural-Model Approach. Part I: Causes (2005)

Causes and Explanations: A Structural-Model Approach. Part II: Explanations (2005)

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Causes and Explanations: A Structural-Model Approach. Part I: Causes (2005)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Causes and Explanations: A Structural-Model Approach. Part II: Explanations (2005)

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Causes and Explanations: A Structural-Model Approach. Part I: Causes (2005)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Causes and Explanations: A Structural-Model Approach. Part II: Explanations (2005)

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Causes and explanations: A structural-model approach. Part I: Causes. British Journal for Philosophy of Science (2005)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Intransitivity and Vagueness (2004)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Sleeping Beauty Reconsidered: Conditioning and Reflection in Asynchronous Systems (2004)

There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence...

A Logic for Reasoning about Evidence (2004)

A careful analysis of conditioning in the Sleeping Beauty problem is done, using the formal model for reasoning about knowledge and probability developed by Halpern and Tuttle. While the Sleeping...

Anonymity and Information Hiding in Multiagent Systems (2004)

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)....

Halpern, Joseph Y., O'Neill, Kevin R.

We provide a framework for reasoning about information-hiding requirements in multiagent systems and for reasoning about anonymity in particular. Our framework employs the modal logic of knowledge...

Knowledge-Based Sythesis of Distributed Systems Using Event Structures (2004)

Bickford, Mark, Constable, Robert C., Halpern, Joseph Y., Petride, Sabina

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...

Knowledge-Based Sythesis of Distributed Systems Using Event Structures (2004)

Bickford, Mark, Constable, Robert C., Halpern, Joseph Y., Petride, Sabina

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...

A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors (2004)

Halpern, Joseph Y., Ricciardi, Aleta

It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained...

A formal foundation for XrML (2004)

Responsibility and blame: A structural-model approach (2004)

XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of...

Hana Chockler, Joseph Y. Halpern

www.cs.cornell.edu/home/halpern Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl...

Intransitivity and vagueness (2004)

Anonymity and Information Hiding in Multiagent Systems (2004)

There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence...

Joseph Y. Halpern, Kevin R. O'Neill

We provide a framework for reasoning about information-hiding requirements in multiagent systems and for reasoning about anonymity in particular.

Responsibility and blame: A structural-model approach (2004)

Hana Chockler, Joseph Y. Halpern

www.cs.cornell.edu/home/halpern Causality is typically treated as an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and...

Responsibility and Blame: A Structural-Model (2004)

Approach Hana Chockler, Hana Chockler, Joseph Y. Halpern

Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl [2001a] to take into account the...

A formal foundation for XrML (2004)

Joseph Y. Halpern, Vicky Weissman

XrML is becoming a popular language in industry for writing software licenses. The semantics for XrML is implicitly given by an algorithm that determines if a permission follows from a set of...

Representation Dependence in Probabilistic Inference (2003)

Halpern, Joseph Y., Koller, Daphne

Non-deductive reasoning systems are often {\em representation dependent}: representing the same situation in two different ways may cause such a system to return two different answers. Some have...

What Causes a System to Satisfy a Specification? (2003)

Chockler, Hana, Halpern, Joseph Y., Kupferman, Orna

Even when a system is proven to be correct with respect to a specification, there is still a question of how complete the specification is, and whether it really covers all the behaviors of the...

Characterizing and Reasoning about Probabilistic and Non-Probabilistic Expectation (2003)

Responsibility and blame: a structural-model approach (2003)

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,...

Chockler, Hana, Halpern, Joseph Y.

Causality is typically treated an all-or-nothing concept; either A is a cause of B or it is not. We extend the definition of causality introduced by Halpern and Pearl [2001] to take into account the...

Great Expectations. Part I: On the Customizability of Generalized Expected Utility (2003)

Chu, Francis C., Halpern, Joseph Y.

We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker's beliefs are represented by plausibility measures, and the decision maker's tastes are...

Great Expectations. Part II: Generalized Expected Utility as a Universal Decision Rule (2003)

Chu, Francis C., Halpern, Joseph Y.

Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in Part I of this paper is a universal decision rule,...

Using Counterfactuals in Knowledge-Based Programming (2003)

Halpern, Joseph Y., Moses, Yoram

This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi. The use of counterfactuals is illustrated by designing a protocol in which an agent...

Modeling Belief in Dynamic Systems, Part I: Foundations (2003)

Modeling Belief in Dynamic Systems, Part II: Revisions and Update (2003)

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...

A logic for reasoning about upper probabilities (2003)

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. In a...

From Statistical Knowledge Bases to Degrees of Belief (2003)

We present a propositional logic %which can be used to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability...

Bacchus, Fahiem, Grove, Adam, Halpern, Joseph Y., Koller, Daphne

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...

Secrecy in Multiagent Systems (2003)

O'Neill, Kevin R., Halpern, Joseph Y.

We introduce a general framework for reasoning about secrecy and privacy requirements in multiagent systems. Our definitions extend earlier definitions of secrecy and nondeducibility given by Shannon...

Updating Probabilities (2003)

Grunwald, Peter D., Halpern, Joseph Y.

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...

Lexicographic probability, conditional probability, and nonstandard probability (2003)

On the Relationship between Strand Spaces and Multi-Agent Systems (2003)

The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's), and nonstandard probability spaces (NPS's)...

A computer scientist looks at game theory (2003)

Strand spaces are a popular framework for the analysis of security protocols. Strand spaces have some similarities to a formalism used successfully to model protocols for distributed systems, namely...

Great expectations. Part I: On the customizability of generalized expected utility (2003)

I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c)...

www.cwi.nl/˜pdg Updating Probabilities (2003)

We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker’s beliefs are represented by plausibility measures and the decision maker’s tastes are...

Updating Probabilities (2003)

www.cs.cornell.edu/home/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...

Peter Grünwald, J. Halpern, 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...

Great Expectations. (2003)

Part Ii Generalized, Francis C. Chu, Joseph Y. Halpern

Many di#erent rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in [Chu and Halpern 2003] is a universal decision rule,...

Great expectations. Part I: On the customizability of generalized expected utility (2003)

Using first-order logic to reason about policies (2003)

Abstract We propose a generalization of expected utility that we call generalized EU (GEU), where adecision maker's beliefs are represented by plausibility measures and the decision maker's...

2003a). A logic for reasoning about evidence (2003)

A policy describes the conditions under which an action is permitted or forbidden. We show that a fragment of (multi-sorted) first-order logic can be used to represent and reason about policies....

A computer scientist looks at game theory (2003)

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)....

Great expectations. Part II: Generalized expected utility as a universal decision rule (2003)

Abstract I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and...

Great Expectations. (2003)

Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in [Chu and Halpern 2003] is a universal decision rule,...

Part On The, Francis C. Chu, Joseph Y. Halpern

We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker's beliefs are represented by plausibility measures and the decision maker's tastes...

A Logic for Reasoning about Evidence (2003)

2003a). A logic for reasoning about evidence (2003)

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)...

Reasoning About Common Knowledge with Infinitely Many Agents (2003)

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)....

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...

Gossip Based Ad-Hoc Routing (2002)

Haas, Zygmunt, Halpern, Joseph Y., Li, Erran L.

Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where...

Minimum-Energy Mobile Wireless Networks Revisited (2002)

Li, Erran L., Halpern, Joseph Y.

We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair $(u,v)$ of nodes connected in the original network, there is a minimum-energy path between...

Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-hop Networks (2002)

Li, Erran L., Halpern, Joseph Y., Bahl, Paramvir, Wang, Yi-Min, Wattenhofer, Roger

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...

Complete Axiomatizations for Reasoning About Knowledge and Time (2002)

Halpern, Joseph Y., Van Der Meyden, Ron, Vardi, Moshe Y.

Sound and complete axiomatizations are provided for a number of different logics involving modalities for knowledge and time. These logics arise from different choices for various parameters. All the...

Causes and Explanations: A Structural-Model Approach. Part II: Explanations (2002)

A logical reconstruction of SPKI (2002)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Halpern, Joseph Y., Van Der Meyden, Ron

SPKI/SDSI is a proposed public key infrastructure standard that incorporates the SDSI public key infrastructure. SDSI's key innovation was the use of local names. We previously introduced a Logic of...

A computer scientist looks at game theory (2002)

On the Expressive Power of Dynamic Logic. II, (2002)

I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c)...

Characterizing the Common Prior Assumption (2002)

In this paper we study the expressive power of nondeterminism in dynamic logic. In particular, we show that first order regular dynamic logic without equality (hereafter abbreviated DL) is more...

Abstract: Logical characterizations of the common prior assumption (CPA) are investigated. Two approaches are considered. The first is called frame distin-guishability, and is similar in spirit to...

Abstract—Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messa ges are propagated unnecessarily. We propose a gossiping-based approa...

Zygmunt J. Haas, Senior Member, Joseph Y. Halpern, Senior Member, Li (erran Li

Abstract—Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations of flooding, many routing messages are propagated unnecessarily. We propose a...

A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks (2002)

Abstract—Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based...

Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...

Reasoning about Expectation (2002)

Modeling adversaries in a logic for security protocol analysis (2002)

Expectation is a central notion in probability theory.

Modeling Adversaries in a Logic for Security Protocol Analysis (2002)

Abstract. Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers...

Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers only...

Secrecy in multiagent systems (2002)

Zygmunt Haas, Joseph Y. Halpern, Li Li

Abstract — Many ad hoc routing protocols are based on (some variant of) flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based...

Joseph Y. Halpern, Kevin R. O’neill

We introduce a general framework for reasoning about secrecy and privacy requirements in multiagent systems. Our definitions extend earlier definitions of secrecy and nondeducibility given by Shannon...

Gossip-Based Ad Hoc Routing (2001)

Haas, Zygmunt, Halpern, Joseph Y., Li, Li

Many ad hoc routing protocols are based on(some variant of) flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach to...

On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs (2001)

Chu, Francis, Halpern, Joseph Y.

Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move. Moreover, the players have common interests: at each node, all the players get the same...

Belief Revision: A Critique (2001)

Causes and explanations: A structural-model approach (2001)

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change...

Joseph Y. Halpern, Judea Pearl

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Causes and explanations: A structural-model approach (2001)

Joseph Y. Halpern, Judea Pearl

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

www.elsevier.com/locate/geb A computer scientist looks at game theory (2001)

Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks (2001)

I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c)...

Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer

bahl~microsoft, corn ymwang~microsoft, corn rogerwa~microsoft, corn The topology of a wireless multi-hop network can be con-trolled by varying the transmission power at each node. In this paper, we...

Causes and explanations: A structural-model approach (2001)

A logical reconstruction of SPKI (2001)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks (2001)

SPKI/SDSI is a proposed public key infrastructure standard that incorporates the SDSI public key infrastructure. SDSI's key innovation was the use of local names. We previously introduced a...

Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...

A Logic for Reasoning about Upper Probabilities (2001)

Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks (2001)

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...

Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, Roger Wattenhofer

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...

Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks (2001)

Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...

A logical reconstruction of SPKI (2001)

Conditional plausibility measures and Bayesian networks (2001)

SPKI/SDSI is a proposed public key infrastructure standard that incorporates the SDSI public key infrastructure. SDSI’s key innovation was the use of local names. We previously introduced a Logic...

A logical reconstruction of SPKI (2001)

A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability...

Plausibility measures: A general approach for representing uncertainty (2001)

SPKI/SDSI is a proposed public key infrastructure standard that incorporates the SDSI public key infrastructure. SDSI's key innovation was the use of local names. We previously introduced a...

Alternative semantics for unawareness (2001)

The standard approach to modeling uncertainty is probability theory. In recent years, researchers, motivated by varying concerns including a dissatisfaction with some of the axioms

Lexicographic probability, conditional probability, and nonstandard probability (2001)

Modica and Rustichini [1994] provided a logic for reasoning about knowledge where agents may be unaware of certain propositions. However, their original approach had the unpleasant property that...

Minimum-Energy Mobile Wireless Networks Revisited (2001)

The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's) [Blume, Brandenburger, and Dekel 1991a;...

Li Li, Joseph Y. Halpern

We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair (u, v) of nodes connected in the original network, there is a a minimum-energy path between...

On the Relationship between Strand Spaces and (2001)

A Logic for Reasoning about Upper Probabilities (2001)

this paper appears in the Proceedings of the 8th ACM Conference on Computer and Communications Security, 2001. Supported in part by NSF under grant IRI96 -25901 and IIS-0090145 and by ONR under...

Sleeping beauty reconsidered: Conditioning and reflection in asynchronous systems (2001)

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...

On the relationship between strand spaces and multi-agent systems (2001)

A careful analysis of conditioning in the Sleeping Beauty problem is done, using the formal model for reasoning about knowledge and probability developed by Halpern and Tuttle. While the Sleeping...

Causes and explanations: A structural-model approach (2001)

Strand spaces are a popular framework for the analysis of security protocols. Strand spaces have some similarities to a formalism used successfully to model protocols for distributed systems, namely...

Plausibility measures: A general approach for representing uncertainty (2001)

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Causes and explanations: A structural-model approach (2001)

Causes and explanations: A structural-model approach (2001)

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Causes and explanations: A structural-model approach (2001)

We propose a new definition of actual causes, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks (2001)

www.cs.cornell.edu/home/halpern We propose a new definition of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as...

Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-min Wang, Roger Wattenhofer

The topology of a wireless multi-hop network can be controlled by varying the transmission power at each node. In this paper, we give a detailed analysis of a cone-based distributed topology control...

Minimum energy mobile wireless networks revisited (2001)

Li Li, Joseph Y. Halpern

Abstract—We propose a protocol that, given a communication network, computes a subnetwork such that, for every pair ¢¡¤£¦¥¨ § of nodes connected in the original network, there is a a...

Causes and explanations: A structural-model approach (2001)

Joseph Y. Halpern, Judea Pearl

We propose new definitions of (causal) explanation, using structural equations to model counterfactuals. The definition is based on the notion of actual cause, as defined and motivated in a companion...

Multi-agent Only Knowing (2001)

Halpern, Joseph Y., Lakemeyer, Gerhard

Levesque introduced a notion of ‘only knowing’, with the goal of capturing certain types of non‐monotonic reasoning. Levesque's logic dealt with only the case of a single agent. Recently,...

Alternative Semantics for Unawareness (2001)

Causes and Explanations: A Structural-Model Approach, Part I: Causes (2000)

Modica and Rustichini [1994] provided a logic for reasoning about knowledge where agents may be unaware of certain propositions. However, their original approach had the unpleasant property that...

A Decision-Theoretic Approach to Resource Allocation in Wireless Multimedia Networks (2000)

We propose a new definition of actual cause, using structural equations to model counterfactuals. We show that the definition yields a plausible and elegant account of causation that handles well...

Haas, Zygmunt, Halpern, Joseph Y., Li, Li, Wicker, Stephen B.

The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless communication. We...

Performing work efficiently in the presence of faults (2000)

Dwork, Cynthia, Halpern, Joseph Y., Waarts, O.

We consider a system of t synchronous processes that communicate only by sending messages to one another, and that together must perform $n$ independent units of work. Processes may fail by crashing;...

Knowledge and common knowledge in a distributed environment (2000)

Halpern, Joseph Y., Moses, Yoram

Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed...

Axiomatizing Causal Reasoning (2000)

Conditional Plausibility Measures and Bayesian Networks (2000)

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)...

CoRR: A Computing Research Repository (2000)

A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability...

A response to the commentaries on CoRR (2000)

Discusses how CoRR was set up and some policy issues involved with setting up such a repository.

A Decision-Theoretic Approach to Resource Allocation in WirelessMultimedia Networks (2000)

This is a response to the commentaries on "CoRR: A Computing Research Repository".

Haas, Zygmunt, Halpern, Joseph Y., Li, Li, Wicker, Stephen

The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless communication. We...

A Decision-Theoretic Approach to Resource Allocation in WirelessMultimedia Networks (2000)

Haas, Zygmunt, Halpern, Joseph Y., Li, Li, Wicker, Stephen

The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless communication. We...

A note on knowledge-based programs and specifications (2000)

A Logic for SDSI's Linked Local Name Spaces (2000)

Knowledge-based program are programs with explicit tests for knowledge. They have been used successfully in a number of applications. Sanders has pointed out what seem to be a counterintuitive...

Halpern, Joseph Y., Van Der Meyden, Ron

Abadi has introduced a logic to explicate the meaning of local names in SDSI, the Simple Distributed Security Infrastructure proposed by Rivest and Lampson. Abadi's logic does not correspond...

Multi-Agent Only Knowing (2000)

Halpern, Joseph Y., Lakemeyer, Gerhard

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...

A note on knowledge-based programs and specifications (2000)

Conditional Plausibility Measures and Bayesian Networks (2000)

Knowledge-based program are programs with explicit tests for knowledge. They have been used successfully in a number of applications. Sanders has pointed out what seem to be a counterintuitive...

Axiomatizing Causal Reasoning (2000)

A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability...

Causes and Explanations: A Structural-Model Approach (2000)

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)...

Joseph Halpern Cornell, Joseph Y. Halpern

We propose new definitions of actual causes and explanations, using structural equations to model counterfactuals. We show that these definitions yield a plausible and elegant account of causation...

A Note on Knowledge-Based Programs and Specifications (2000)

Joseph Halpern Computer, Joseph Y. Halpern

Knowledge-based program are programs with explicit tests for knowledge. They have been used successfully in a number of applications. Sanders has pointed out what seem to be a counterintuitive...

A Note on Knowledge-Based Programs and Specifications (2000)

A decision-theoretic approach to resource allocation in wireless multimedia networks (2000)

Knowledge-based program are programs with explicit tests for knowledge. They have been used successfully in a number of applications. Sanders has pointed out what seem to be a counterintuitive...

Zygmunt Haas, Joseph Y. Halpern, Li Li, Stephen B. Wicker

Abstract — The allocation of scarce spectral resources to support as many user applications as possible while maintaining reasonable quality of service is a fundamental problem in wireless...

PROBABILITY AND CONDITIONALS: BELIEF REVISION AND RATIONAL DECISION (2000)

Cox's Theorem Revisited (1999)

Reasoning About Common Knowledge with Infinitely Many Agents (1999)

The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong and,...

Halpern, Joseph Y., Shore, Richard A.

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...

A decision-theoretic approach to reliable message delivery (1999)

Chu, Francis C., Halpern, Joseph Y.

We argue that the tools of decision theory need to be taken more seriously in the specification and analysis of systems. We illustrate this by considering a simple problem involving reliable...

Least expected cost query optimization: an exercise in utility (1999)

Chu, Francis C., Halpern, Joseph Y., Seshadri, Praveen

We identify two unreasonable, though standard, assumptions made by database query optimizers that can adversely affect the quality of the chosen evaluation plans. One assumption is that it is enough...

Hypothetical Knowledge and Counterfactual Reasoning (1999)

A hierarchical approach to modeling knowledge and common knowledge (1999)

Abstract: Salmet introduced 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...

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

vardi One approach to representing knowledge or belief of agents, used by economists and computer scientists, involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's...

Modeling Belief in Dynamic Systems. Part II: Revision and Update (1999)

Modeling belief in dynamic systems. Part II: revision and update (1999)

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. In a...

Complete Axiomatizations for Reasoning about Knowledge and Time (1999)

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. In a...

Joseph Y. Halpern, Ron Van, Moshe Y. Vardi

Sound and complete axiomatizations are provided for a number of di#erent logics involving modalities for knowledge and time. These logics arise from di#erent choices for various parameters regarding...

Cox's Theorem Revisited (1999)

Plausibility Measures and Default Reasoning: An Overview (1999)

The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong...

A Logic for SDSI's Linked Local Name Spaces (1999)

We introduce a new approach to modeling uncertainty based on plausibility measures. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures,...

Reasoning About Common Knowledge with Infinitely Many Agents (1999)

Abadi has introduced a logic to explicate the meaning of local names in SDSI, the Simple Distributed Security Infrastructure proposed by Rivest and Lampson. Abadi's logic does not correspond...

Joseph Y. Halpern, Richard A. Shore, Where G

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...

Least Expected Cost Query Optimization: An Exercise in Utility (1999)

Francis Chu, Joseph Y. Halpern, Praveen Seshadri

We identify two unreasonable, though standard, assumptions made by database query optimizers that can adversely affect the quality of the chosen evaluation plans. One assumption is that it is enough...

Cox's Theorem Revisited (1999)

A Note on Unawareness (1999)

The assumptions needed to prove Cox's Theorem are discussed and examined. Various sets of assumptions under which a Cox-style theorem can be proved are provided, although all are rather strong...

A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors (1999)

Modica and Rustichini [1994] provided a logic for reasoning about knowledge where agents may be unaware of certain propositions. However, their original approach had the unpleasant property that...

Joseph Halpern Cornell, Joseph Y. Halpern, Aleta Ricciardi

It is shown that if there is no bound on the number of faulty processes, then in a precise sense, in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be...

Modeling Belief in Dynamic Systems. Part II: Revision and Update (1999)

A Counterexample to Theorems of Cox and Fine (1999)

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. In a...

Plausibility Measures and Default Reasoning: An Overview (1999)

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...

Modeling belief in dynamic systems. Part II: revision and update (1999)

We introduce a new approach to modeling uncertainty based on plausibility measures. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures,...

The Computing Research Repository: Promoting the Rapid Dissemination and Archiving of Computer Science Research (1998)

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. In a...

Halpern, Joseph Y., Lagoze, Carl

We describe the Computing Research Repository (CoRR), a new electronic archive for rapid dissemination and archiving of computer science research results. CoRR was initiated in September 1998 through...

Reasoning Under Uncertainty. (1998)

Updating Beliefs in Incompletely Specified Situations (1998)

This report summarizes the research performed under this contract. The research can he divided into four areas: (1) Computing degrees of belief, (2) Reasoning about knowledge and communication, (3)...

Formulating and Reasoning about Security Policies (1998)

This project focused on a number of issues related to updating beliefs, both qualitative and quantitative, in incompletely specified settings. In addition, work was initiated on the topic of...

Reasoning about Noisy Sensors and Effectors in the Situation Calculus (1998)

The goal of this project was to investigate the use of first-order logic for expressing security policies and reasoning about authorization, and to apply to logic for use with digital library and...

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

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...

Plausibility Measures and Default Reasoning (1998)

First-Order Conditional Logic Revisited (1998)

We introduce a new approach to modeling uncertainty based on plausibility measures. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures,...

Friedman, Nir, Halpern, Joseph Y., Koller, Daphne

Conditional logics play an important role in recent attempts to formulate theories of default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order...

Set-Theoretic Completeness for Epistemic and Conditional Logic (1998)

A logical approach to reasoning about uncertainty: a tutorial (1998)

The standard approach to logic in the literature in philosophy and mathematics, which has also been adopted in computer science, is to define a language (the syntax), an appropriate class of models...

Hypothetical Knowledge and Counterfactual Reasoning (1998)

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...

Joseph Halpern Dept, Joseph Y. Halpern

Samet introduced 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...

Belief Revision with Unreliable Observations (1998)

Craig Boutilier, Nir Friedman, J. Halpern, Joseph Y. Halpern

Research in belief revision has been dominated by work that lies firmly within the classic AGM paradigm, characterized by a well-known set of postulates governing the behavior of "rational...

Reasoning about Noisy Sensors and Effectors in the Situation Calculus (1998)

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...

Characterizing the Common Prior Assumption (1998)

On the Knowledge Requirements of Tasks (1998)

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...

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...

Substantive Rationality and Backward Induction (1998)

A Decision-Theoretic Approach to Reliable Message Delivery (1998)

Aumann has proved that common knowledge of substantive rationality implies the backwards induction solution in games of perfect information. Stalnaker has proved that it does not. Roughly speaking, a...

Updating Sets of Probabilities (1998)

We argue that the tools of decision theory should be taken more seriously in the specification and analysis of systems. We illustrate this by considering a simple problem involving reliable...

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...

Belief Revision with Unreliable Observations (1998)

Craig Boutilier, Nir Friedman, Joseph Y. Halpern

Research in belief revision has been dominated by work that lies firmly within the classic AGM paradigm, characterized by a well-known set of postulates governing the behavior of "rational...

Using Counterfactuals in Knowledge-Based Programming (1998)

Axiomatizing Causal Reasoning (1998)

: We show how counterfactuals can be added to the framework of knowledgebased programs of Fagin, Halpern, Moses, and Vardi [1995, 1997]. We show that counterfactuals allow us to capture in a natural...

Reasoning about Noisy Sensors and Effectors in the Situation Calculus (1998)

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)...

Fahiem Bacchus Dept, 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...

Reasoning about Noisy Sensors and Effectors in the Situation Calculus (1998)

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...

On the Knowledge Requirements of Tasks (1998)

Ronen 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...

On the Knowledge Requirements of Tasks (1998)

Ronen Brafman, Joseph Y. Halpern, Yoav Shoham

Sensors In [Erd94], Erdmann argues that the role of sensors is to provide sufficient information to choose "good" actions, and that they should be constructed to fulfill this task. An...

Abstract (1998)

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

Agents interacting with an incompletely known world need to be able to reason about the e ects of their actions, and to gain further information about that world they need to use sensors of some...

Using counterfactuals in Knowledge-based programming (1998)

Using counterfactuals in Knowledge-based programming (1998)

Abstract This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi [1995, 1997]. The use of counterfactuals is illustrated by designing a...

Axiomatizing causal reasoning (1998)

This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi [1995, 1997]. The use of counterfactuals is illustrated by designing a protocol in...

Modeling belief in dynamic systems. part i: Foundations (1997)

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)...

Modeling belief in dynamic systems. part i: Foundations (1997)

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...

Defining Explanation in Probabilistic Systems (1997)

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...

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...

On The Expected Value Of Games With Absentmindedness (1997)

Adam J. Grove, Joseph Y. Halpern

Piccione and Rubinstein argue that a seemingly paradoxical form of time inconsistency can arise in games of imperfect recall. Their argument depends on calculating the expected value of a game from...

Complete Axiomatizations for Reasoning about Knowledge and Time (1997)

Joseph Y. Halpern, Moshe Y. Vardi

Sound and complete axiomatizations are provided for a number of different logics involving modalities for knowledge and time. These logics arise from different choices for various parameters. All the...

Modeling Belief in Dynamic Systems. Part I: Foundations (1997)

Defining relative likelihood in partially-ordered preferential structures (1997)

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...

Knowledge-based programs (1997)

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 earlier considered such a...

Ronald Fagin, Joseph Y. Halpern, Yoram Moses, Moshe Y. Vardis

Summary. Reasoning about activities in a distributed computer system at the level of the knowledge of indi-viduals and groups allows us to abstract away from many concrete details of the system we...

A Theory of Knowledge and Ignorance for Many Agents (1997)

HALPERN, JOSEPH Y.

We extend the notion of ‘only knowing’ introduced by J. Y. Halpern and Y. Moses to many agents and to a number of modal logics. In this approach, ‘all an agent knows is α’ is true in a...

First-order conditional logic revisited (1996)

Belief revision: a critique (1996)

Conditional logics play an important role in recent attempts to formulate theories of default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order...

First-order conditional logic revisited (1996)

The problem of belief change---how an agent should revise her beliefs upon learning new information---has been an active area of research in both philosophy and artificial intelligence. Many...

Asymptotic conditional probabilities: the non-unary case (1996)

Conditional logics play an important role in recent attempts to formulate theories of default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order...

Multi-agent only knowing (1996)

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences...

A Qualitative Markov Assumption and Its Implications for Belief Change (1996)

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....

Plausibility Measures and Default Reasoning (1996)

The study of belief change has been an active area in philosophyand AI. In recent years, two special cases of belief change, belief revision and belief update, have been studied in detail. Roughly...

Plausibility Measures and Default Reasoning (1996)

this paper: default reasoning. In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, ffl-semantics, possibilistic structures, and...

A Propositional Modal Logic of Time Intervals (1996)

In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, ffl- semantics, possibilistic structures, and -rankings, that have been shown to be...

Joseph Y. Halpern, Yoav Shoham

: In certain areas of artificial intelligence there is need to represent continuous change and to make statements that are interpreted with respect to time intervals rather than time points. To this...

Belief Revision: A Critique (1996)

Dynamic Fault-Tolerant Clock Synchronization (1996)

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change...

Danny Dolev, Joseph Y. Halpern, Barbara Simons, Ray Strong

This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized....

Multi-Agent Only Knowing (1996)

What Can Machines Know? On the Properties of Knowledge in Distributed Systems (1996)

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....

Clock Synchronization and the Power of Broadcasting (1996)

It has been argued that knowledge is a useful tool for designing and analyzing complex systems. The notion of knowledge that seems most relevant in this context is an external, information-based...

Joseph Y. Halpern, Ichiro Suzuki

: We investigate the power of a broadcast mechanism in a distributed network. We do so by considering the problem of synchronizing clocks in an error-free network, under the assumption that there is...

The Failure Discovery Problem (1996)

Vassos Hadzilacos, Joseph Y. Halpern

: We define a simple variant of the Byzantine agreement (BA) problem, called the Failure Discovery (FD) problem that, roughly speaking, amounts to reaching Byzantine Agreement provided that no...

From Statistical Knowledge Bases to Degrees of Belief (1996)

Fahiem Bacchus Computer, Fahiem Bacchus, Computer Science Dept, 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...

Irrelevance and Conditioning in First-Order Probabilistic Logic (1996)

Daphne Koller, Joseph Y. Halpern

First-order probabilistic logic is a powerful knowledge representation language. Unfortunately, deductive reasoning based on the standard semantics for this logic does not support certain desirable...

A Qualitative Markov Assumption and Its Implications for Belief Change (1996)

Belief Revision: A Critique (1996)

The study of belief change has been an active area in philosophyand AI. In recent years, two special cases of belief change, belief revision and belief update, have been studied in detail. Roughly...

Plausibility Measures and Default Reasoning (1996)

We examine carefully the rationale underlying the approaches to belief change taken in the literature, and highlight what we view as methodological problems. We argue that to study belief change...

On Ambiguities In The Interpretation Of Game Trees (1996)

this paper: default reasoning. In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, ffl-semantics, possibilistic structures, and...

From Statistical Knowledge Bases to Degrees of Belief (1996)

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...

Fahiem Bacchus, Computer Science Dept, 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...

Research Report (1996)

Common Knowledge, Moshe Y. Vardi, Ronald Fagin, Ronald Fagin, Joseph Y. Halpern, Joseph Y. Halpern, ...

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...

Irrelevance and Conditioning in First-Order Probabilistic Logic (1996)

Daphne Koller, Joseph Y. Halpern

First-order probabilistic logic is a powerful knowledge representation language. Unfortunately, deductive reasoning based on the standard semantics for this logic does not support certain desirable...

Common Knowledge: Now You Have it, Now You Don't (1996)

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

this paper is an attempt to resolve the paradox of common knowledge: Although common knowledge can be shown to be a prerequisite for day-to-day activities of coordination and agreement, it can also...

From Statistical Knowledge Bases to Degrees of Belief (1996)

Fahiem Bacchus Computer, Fahiem Bacchus, Computer Science Dept, 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...

Belief revision: a critique (1996)

Common knowledge revisited (1996)

The problem of belief change—how an agent should revise her beliefs upon learning new information—has been an active area of research in both philosophy and artificial intelligence. Many...

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

Abstract: 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...

Representation dependence in probabilistic inference (1995)

Joseph Y. Halpern, Daphne Koller

Non-deductive reasoning systems are often representation dependent: representing the same situation in two di#erent ways may cause such a system to return two di#erent answers. Some have viewed this...

Levesque's axiomatization of only knowing is incomplete (1995)

Representation dependence in probabilistic inference (1995)

We show that the axiomatization given by Levesque for his logic of "only knowing" (Levesque 1990), which he showed to be sound and complete for the unquantified version of the logic...

Reasoning about noisy sensors in the situation calculus (1995)

Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. This is generally...

Joseph Y. Halpern, Hector Levesque

Abstract: Agents interacting with an incompletely known dynamic world need to be able to reason about the effects of their actions, and to gain further information about that world using sensors of...

Plausibility Measures: A User’s Guide (1995)

Plausibility Measures: A User's Guide (1995)

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...

The Effect Of Bounding The Number Of Primitive Propositions And The Depth Of Nesting On The Complexity Of Modal Logic (1995)

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...

Levesque's Axiomatization of Only Knowing is Incomplete (1995)

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...

Reasoning About Knowledge: A Survey (1995)

We show that the axiomatization given by Levesque for his logic of "only knowing" (Levesque 1990), which he showed to be sound and complete for the unquantified version of the logic and...

Knowledge-Based Programs (1995)

: In this survey, I 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,...

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

Reasoning about activities in a distributed computer system at the level of the knowledge of individuals and groups allows us to abstract away from many concrete details of the system we are...

A Logical Approach To Reasoning About Uncertainty: A Tutorial (1995)

Reasoning about Noisy Sensors in the Situation Calculus (1995)

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...

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

Agents interacting with an incompletely known dynamic world need to be able to reason about the effects of their actions, and to gain further information about that world using sensors of some sort....

Knowledge-Based Programs (1995)

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

Reasoning about activities in a distributed computer system at the level of the knowledge of individuals and groups allows us to abstract away from many concrete details of the system we are...

Representation dependence in probabilistic inference (1995)

Representation dependence in probabilistic inference (1995)

Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed...

Representation dependence in probabilistic inference (1995)

Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed...

Reasoning about noisy sensors in the situation calculus (1995)

Non-deductive reasoning systems are often representation dependent, representing the same situation in two different ways may cause such a system to return two different answers. This is generally...

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

Abstract: Agents interacting with an incompletely known dynamic world need to be able to reason about the effects of their actions, and to gain further information about that world using sensors of...

Representation dependence in probabilistic inference (1995)

Reasoning about noisy sensors in the situation calculus (1995)

Non-deductive reasoning systems are often representation dependent: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed...

Fahiem Bacchus, Joseph Y. Halpern, Hector Levesque

Abstract: Agents interacting with an incompletely known dynamic world need to be able to reason about the effects of their actions, and to gain further information about that world using sensors of...

A Knowledge-Based Framework for Belief Change - Part I: Foundations (1994)

On the Complexity of Conditional Logics (1994)

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 ' if he knows that ' is true in all the...

Conditional Logics of Belief Change (1994)

Conditional logics, introduced by Lewis and Stalnaker, have been utilized in artificial intelligence to capture a broad range of phenomena. In this paper we examine the complexity of several variants...

A Knowledge-Based Framework for Belief Change, Part II: Revision and Update (1994)

The study of belief changehas 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. Belief...

On the Complexity of Conditional Logics (1994)

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. In a...

Reasoning about Knowledge and Probability (1994)

Conditional logics, introduced by Lewis and Stalnaker, have been utilized in artificial intelligence to capture a broad range of phenomena. In this paper we examine the complexity of several variants...

Zero-One Laws For Modal Logic (1994)

: We provide a model for reasoning about knowledge and probability together. We allow explicit mention of probabilities in formulas, so that our language has formulas that essentially say...

Joseph Y. Halpern, Bruce Kapron

We show that a 0-1 law holds for propositional modal logic, both for structure validity and frame validity. In the case of structure validity, the result follows easily from the wellknown 0-1 law for...

A Response to "Believing on the basis of evidence" (1994)

Fahiem Bacchus, Adam Grove, Joseph Y. Halpern, Daphne Koller

This paper is essentially identical to one that appears in Computational Intelligence

Generating New Beliefs From Old (1994)

Fahiem Bacchus, Computer Science Dept, 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...

Conditional Logics of Belief Change (1994)

Forming Beliefs About A Changing World (1994)

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. Belief...

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

The situation calculus is a popular technique for reasoning about action and change. However, its restriction to a first-order syntax and pure deductive reasoning makes it unsuitable in many...

Zero-One Laws for Modal Logic (1994)

Joseph Y. Halpern, Bruce M. Kapron

We show that a 0-1 law holds for propositional modal logic, both for structure validity and frame validity. In the case of structure validity, the result follows easily from the well-known 0-1 law...

Generating New Beliefs From Old (1994)

Fahiem Bacchus, Computer Science Dept, 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...

Forming Beliefs About a Changing World (1994)

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

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....

Random Worlds and Maximum Entropy (1994)

An operational semantics for knowledge bases (1994)

Given a knowledge base KB containing first-order and statistical facts, we consider a principled method, called the random-worlds method, for computing a degree of belief that some formula '...

Ronald Fagin, Joseph Y. Halpern, Yoram Mosest, Moshe Y. Vardi

The standard approach in Al to knowledge representation is to represent an agent's knowledge symbolically as a collection of formulas, which we can view as a knowledge base. An agent is then...

Algorithmic knowledge (1994)

Algorithmic knowledge (1994)

Abstract. The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized...

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

Abstract: 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...

Beyond Nash Equilibrium: Solution Concepts for the 21st Century,” June 2008; http://arxiv.org/ abs/0806.2139 [3 (1994)

Naming and Identity in Epistemic Logics Part I: The Propositional Case (1993)

Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However, it suffers from numerous problems. Some are well known in the game theory community; for example, the Nash...

Adam Grove, Joseph Y. Halpern

Modal epistemic logics for many agents often assume a fixed one-to-one correspondence between agents and the names for agents that occur in the language. This assumption restricts the applicability...

Asymptotic Conditional Probabilities: The Unary Case (1993)

A Theory Of Knowledge And Ignorance For Many Agents (1993)

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences...

The Failure Discovery Problem (1993)

We extend the notion of "only knowing" introduced by Halpern and Moses [11] to many agents and to a number of modal logics. In this approach, "all an agent knows is ff" is true in...

Vassos Hadzilacos, Joseph Y. Halpern

: We define a simple variant of the Byzantine agreement (BA) problem, called the Failure Discovery (FD) problem that, roughly speaking, amounts to reaching Byzantine Agreement provided that no...

Statistical Foundations for Default Reasoning (1993)

Fahiem Bacchus, Computer Science Dept, Adam J. Grove, Joseph Y. Halpern, Daphne Koller

We describe a new approach to default reasoning, based on a principle of indifference among possible worlds. We interpret default rules as extreme statistical statements, thus obtaining a knowledge...

Asymptotic Conditional Probabilities: The Non-unary Case (1993)

Knowledge, probability, and adversaries (1993)

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences...

Joseph Y. Halpern, Mark R. Tuttle

Abstract: What should it mean for an agenttoknow or believe an assertion is true with probability:99? Di erent papers [FH88, FZ88, HMT88] give di erent answers, choosing to use quite di erent...

Naming and Identity in Epistemic Logics Part I: The Propositional Case (1993)

GROVE, ADAM J., HALPERN, JOSEPH Y.

Modal epistemic logics for many agents often assume a fixed one-to-one correspondence between agents and the names for agents that occur in the language. This assumption restricts the applicability...

What is an inference rule (1992)

A Logic for Approximate Reasoning (1992)

What is an inference rule? This question does not have a unique answer. One usually nds two distinct standard answers in the literature: validity inference ( ` v ' if for every substitution ,...

Daphne Koller, Joseph Y. Halpern

We investigate the problem of reasoning with imprecise quantitative information. We give formal semantics to a notion of approximate observations, and define two types of entailment for a knowledge...

What is an inference rule (1992)

Performing Work Efficiently In The Presence Of Faults (1992)

What is an inference rule? This question does not have a unique answer. One usually finds two distinct standard answers in the literature: validity inference (oe ` v ' if for every substitution...

Cynthia Dwork, Joseph Y. Halpern, Orli Waarts

. We consider a system of t synchronous processes that communicate only by sending messages to one another, and that together must perform n independent units of work. Processes may fail by crashing;...

From Statistics to Beliefs (1992)

Fahiem Bacchus, Computer Science Dept, Adam Grove, Joseph Y. Halpern, Daphne Koller

An intelligent agent uses known facts, including statistical knowledge, to assign degrees of belief to assertions it is uncertain about. We investigate three principled techniques for doing this. All...

A Little Knowledge Goes a Long Way: Knowledge-based derivations and correctness proofs for a family of protocols (1992)

Joseph Y. Halpern, Lenore D. Zuck

: We use a high-level, knowledge-based approach for deriving a family of protocols for the sequence transmission problem. The protocols of Aho, Ullman, and Yannakakis [AUY79, AUWY82], the Alternating...

From Statistics to Beliefs (1992)

Fahiem Bacchus, Computer Science Dept, Adam Grove, Joseph Y. Halpern, Daphne Koller

An intelligent agent uses known facts, including statistical knowledge, to assign degrees of belief to assertions it is uncertain about. We investigate three principled techniques for doing this. All...

From Statistics to Beliefs (1992)

Fahiem Bacchus, Computer Science Dept, Adam Grove, Joseph Y. Halpern, Daphne Koller

An intelligent agent uses known facts, including statistical knowledge, to assign degrees of belief to assertions it is uncertain about. We investigate three principled techniques for doing this. All...

Message-Optimal Protocols for Byzantine Agreement (1992)

Vassos Hadzilacos, Joseph Y. Halpern

: It is often important for the correct processes in a distributed system to reach agreement, despite the presence of some faulty processes. Byzantine agreement (BA) is a paradigm problem that...

Asymptotic Conditional Probabilities for First-Order Logic (1992)

A Logic for Approximate Reasoning (1992)

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order formulas. That is, given first-order...

Daphne Koller Stanford, Daphne Koller, Joseph Y. Halpern

We investigate the problem of reasoning with imprecise quantitative information. We give formal semantics to a notion of approximate observations, and define two types of entailment for a knowledge...

What can machines know? On the properties of knowledge in distributed systems (1992)

Ronald Fagin, Joseph Y. Halpern, Y. Vardi

Abstract. It has been argued that knowledge is a useful tool for designing and analyzing complex systems. The notion of knowledge that seems most relevant in this context is an external,...

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

Martín Abadi, Joseph Y. Halpern

We consider decidability and expressiveness issues for two first-order logics of probability. In one, the probability is on possible worlds, while in the other, it is on the domain. It turns out that...

A New Approach to Updating Beliefs (1991)

Presburger Arithmetic With Unary Predicates is ... Complete (1991)

: 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...

Knowledge, Probability, and Adversaries (1991)

: We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is \Pi 1 1...

Joseph Y. Halpern, Mark R. Tuttle

: What should it mean for an agent to know or believe an assertion is true with probability :99? Different papers [FH94, FZ88a, HMT88] give different answers, choosing to use quite different...

The Relationship Between Knowledge, Belief, and Certainty (1991)

Message-Optimal Protocols For Byzantine Agreement (1991)

: We consider the relation between knowledge and certainty, where a fact is known if it is true at all worlds an agent considers possible and is certain if it holds with probability 1. We identify...

Vassos Hadzilacos Computer, Vassos Hadzilacos, Joseph Y. Halpern

: It is often important for the correct processes in a distributed system to reach agreement, despite the presence of some faulty processes. Byzantine agreement (BA) is a paradigm problem that...

Model Checking vs. Theorem Proving: A Manifesto (1991)

Joseph Halpern And, Joseph Y. Halpern, Moshe Y. Vardi

: We argue that rather than representing an agent's knowledge as a collection of formulas, and then doing theorem proving to see if a given formula follows from an agent's knowledge base,...

Model Checking vs. Theorem Proving: A Manifesto (1991)

Joseph Y. Halpern, Moshe Y. Vardi

: We argue that rather than representing an agent's knowledge as a collection of formulas, and then doing theorem proving to see if a given formula follows from an agent's knowledge base,...

A Nonstandard Approach to the Logical Omniscience Problem (1990)

A Characterization of Eventual Byzantine Agreement (1990)

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...

Joseph Y. Halpern, Yoram Moses, Orli Waarts

: We investigate eventual Byzantine agreement (EBA) in the crash and omission failure modes. The emphasis is on characterizing optimal EBA protocols in terms of the states of knowledge required by...

A Logic for Reasoning about Probabilities (1990)

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...

Let Many Flowers Bloom: A Response to "An Inquiry into Computer Understanding" (1990)

A Nonstandard Approach to the Logical Omniscience Problem (1990)

This paper was written while I was on sabbatical at the University of Toronto. I'd like to thank the Computer Science Department at the University of Toronto for their kind hospitality. This...

An Analysis of First-Order Logics of Probability (1990)

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...

A Logic for Reasoning about Probabilities (1990)

: 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...

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...

A Logic for Reasoning about Probabilities (1990)

Ronald Fagin, Joseph Y. Halpern, Nimrod Meciddo

We consider a language for reasoning about probability which allows us to make statements such as “the probability of E, is less than f ” and “the probability of E, is at least twice the...

Elsevier Two views of belief: (1990)

Joseph Y. Halpern, Ronald Fagin

belief as generalized probability and belief as evidence

Reprinted from Artificial Intelligence (1990)

Ronald Fagin, Joseph Y. Halpem, Moshe Y. Vardi, Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi

problem

Uncertainty, Belief, and Probability (1989)

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

: We introduce a new probabilistic approach to dealing with uncertainty, based on the observation that probability theory does not require that every event be assigned a probability. For a...

Mart'in Abadi, Joseph Y. Halpern

We consider decidability and expressiveness issues for two first-order logics of probability. In one, the probability is on possible worlds, while in the other, it is on the domain. It turns out that...

Modelling knowledge and action in distributed systems (1989)

Joseph Y. Halpern, Ronald Fagin

years as the head of the Mathe-

Reasoning about knowledge and probability: preliminary report (1988)

A Model-Theoretic Analysis of Knowledge (1988)

Abstract: We provide a model for reasoning about knowledge anti probabil-ity together. We a.llow explicit mention of probabilities in formulas, so that our language has formulas tha.t essentia.lly...

A Knowledge-Based Analysis of Zero Knowledge (1988)

Understanding knowledge is a fundamental issue in many disciplines. In computer science, knowledge arises not only in the obvious contexts (such as knowledgebased systems), but also in distributed...

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

: While the intuition underlying a zero knowledge proof system [GMR85] is that no "knowledge " is leaked by the prover to the verifier, researchers are just beginning to analyze such proof...

Modelling Knowledge and Action in Distributed Systems (1988)

Joseph Y. Halpern, Ronald Fagin

: We present a formal model that captures the subtle interaction between knowledge and action in distributed systems. We view a distributed system as a set of runs, where a run is a function from...

Belief, awareness, and limited reasoning (1988)

Ronald Fagin, Joseph Y. Halpern, Recommended Daniel, G. Bobrow

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...

Reasoning about knowledge: An overview (1986)

Towards a Theory of Knowledge and Ignorance: Preliminary Report (1985)

Abstract: 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,...

Knowledge and Common Knowledge in a Distributed Environment (1984)

: Situations in which the information about a given domain is partial are common in many AI applications. In planning and analysis of scenarios involving partial information, the state of knowledge...

The Hierarchical Approach to Modeling Knowledge and Common Knowledge

: Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed...

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

One approach to representing knowledge or belief of agents, used by economists and computer scientists, involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs...

Characterizing the Common Prior Assumption

A computer scientist looks at game theory

Alternative Semantics for Unawareness

Substantive Rationality and Backward Induction

On the Expected Value of Games with Absentmindedness

Grove, Adam J., Halpern, Joseph Y.

On Ambiguities in the Interpretation of Game Trees

Interactive unawareness revisited

Halpern, Joseph Y., Rego, Leandro Chaves

Substantive Rationality and Backward Induction

Characterizing the Common Prior Assumption

Aumann has proved that common knowledge of substantive rationality implies the backwards induction solution in games of perfect information. Stalnaker has proved that it does not. Roughly speaking, a...

Alternative Semantics for Unawareness

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...

On the NP-Completeness of Finding an Optimal Strategy in Games with Common Payoffs

Modica and Rustichini [Theory and Decision 37, 1994] provided a logic for reasoning about knowledge where agents may be unaware of certain propositions. However, their original approach had the...

A Computer Scientist Looks at Game Theory

Given a finite game with common payoffs (i.e. the players have completely common interests), we show that the problem of determining whether there exists a joint strategy where each player nets at...

Great Expectations. Part I: On the Customizability of Generalized Expected Utility

I consider issues in distributed computation that should be of relevance to game theory. In particular, I focus on (a) representing knowledge and uncertainty, (b) dealing with failures, and (c)...

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

Many different rules for decision making have been introduced in the literature. We present a single framework in which to study and compare these rules. This is done by defining expected utility...

Hypothetical knowledge and counterfactual reasoning

Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in 'Great Expectations. Part I' is a universal decision...

The hierarchical approach to modeling knowledge and common knowledge

Samet introduced 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...

John Geanakoplos, Joseph Y. Halpern, Ronald Fagin

One approach to representing knowledge or belief of agents, used by economists and computer scientists, involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs...

On Definability in Multimodal Logic II. Defining Knowledge in Terms of Belief

Joseph Y Halpern, Dov Samet, Ella Segev

On Definability in Multimodal Logic I. Basic Notions

Joseph Y Halpern, Dov Sammet, Ella Segev

Reasoning About Knowledge

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

Reasoning about knowledge—particularly the knowledge of agents who reason about the world and each other's knowledge—was once the exclusive province of philosophers and puzzle solvers. More...

First-Order Conditional Logic Revisited

First-Order Conditional Logic Revisited

Conditional logics play an important role in recent attempts to investigate default reasoning. This paper investigates firstorder conditional logic. We show that, as for first-order probabilistic...

The Hierarchical Approach to Modeling Knowledge and Common Knowledge

Conditional logics play an important role in recent attempts to formulate theories of default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order...

Ronald Fagin Ibm, Ronald Fagin, John Geanakoplos, Joseph Y. Halpern, Moshe Y. Vardi

One approach to representing knowledge or belief of agents, used by economists and computer scientists, involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs...

The Hierarchical Approach to Modeling Knowledge and Common Knowledge

Ronald Fagin Ibm, Ronald Fagin, John Geanakoplos, Joseph Y. Halpern, Moshe Y. Vardi

One approach to representing knowledge or belief of agents, used by economists and computer scientists, involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs...

First-Order Conditional Logic Revisited