Joseph Y. Halpern (editor)
This is the proceedings of the first TARK conference, with papers by (among others) Aumann, Hintikka, Fagin, Moses, and Vardi. It includes my first overview on knowledge.
Published by Morgan Kaufmann, 1986.
Joseph Y. Halpern, Ronald Fagin, Yoram Moses, and Moshe Y. Vardi
This book covers much of my research on knowledge. Ordering information is available from MIT Press.
Published by MIT Press, 1995. A revised paperback edition was published in 2003.
Joseph Y. Halpern
This book covers much of my research on uncertainty. Ordering information is available from MIT Press.
Published by MIT Press, 2003. A slightly revised paperback edition was published in 2005.
Uncertainty in Artificial Intelligence: Proceedings of Twentieth Conference
Max Chickering and Joseph Y. Halpern (editors)
Published by AUAI Press, 2004
Hans van Ditmarsch, Joseph Y. Halpern, Wiebe van der Hoek, and Barteld Kooi (editors)
Published by College Publications, 2015
Towards a theory of knowledge and ignorance: preliminary report
Joseph Y. Halpern and Yoram Moses
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 of an intelligent agent in such circumstances becomes important. This paper addresses the problem of characterizing this state of knowledge, with the emphasis on the single-agent case. We give a number of equivalent ways to characterize this state of knowledge, as well as an algorithm for computing the formulas that are true in this state. The relationship between this work and related works by Stark, Konolige, and Moore is discussed.
In Logics and Models of Concurrent Systems (ed. K. Apt), Springer-Verlag, 1985, pp. 459-476 and in Proceedings of the Workshop on Non-Monotonic Reasoning, 1984, pp. 125-143. The paper is available in postscript and pdf. There never was a journal version, but A theory of knowledge and ignorance for many agents does the multi-agent extension that we were hoping to do in the journal version.
Using Reasoning About Knowledge to Analyze Distributed Systems
Joseph Y. Halpern
An overview of work on using reasoning about knowledge to understand and analyze distributed systems.
In Annual Reviews of Computer Science, Vol. 2 (ed. J. F. Traub, B. J. Grosz, B. W. Lampson, and N. J. Nilsson), Annual Reviews Inc., 1987, pp. 37-68. A version is available in pdf.
I'm OK if you're OK: On the notion of trusting communication
We consider the issue of what an agent or a processor needs to know in order to know that its messages are true. This may be viewed as a first step to a general theory of cooperative communication in distributed systems. An honest message is one that is known to be true when it is sent (or said). If every message that is sent is honest, then of course every message that is sent is true. Various conditions weaker than honesty are investigated with the property that provided every message sent satisfies the condition, then every message sent is true.
In Philosophical Logic and Artificial Intelligence (ed. R. H. Thomason), Kluwer, 1989, pp. 9-34 and Journal of Philosophical Logic 17:4, 1988, pp. 329-354. A preliminary version appears in Proceedings of the Second IEEE Symposium on Logic in Computer Science, 1987, pp. 280-292.
Model checking vs. theorem proving: a manifesto
Joseph Y. Halpern and 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, it may be more useful to represent this knowledge by a semantic model, and then do model checking to see if the given formula is true in that model. We discuss how to construct a model that represents an agent's knowledge in a number of different contexts, and then consider how to approach the model-checking problem.
In Artificial Intelligence and Mathematical Theory of Computation (Papers in Honor of John McCarthy) (ed. V. Lifschitz), Academic Press, 1991, pp. 151-176. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version (which includes some material not in this book) appears in Principles of Knowledge Representation and Reasoning: Proceedings of the Second International Conference (J. A. Allen, R. Fikes, and E. Sandewall, eds.), 1991, pp. 325-334.
A new approach to updating beliefs
Ronald Fagin and Joseph Y. Halpern
We define a new notion of conditional belief, which plays the same role for Dempster-Shafer belief functions as conditional probability does for probability functions. Our definition is different from the standard definition given by Dempster, and avoids many of the well-known problems of that definition. Just as the conditional probability Pr(.|B) is a probability function which is the result of conditioning on B being true, so too our conditional belief function Bel(.|B) is a belief function which is the result of conditioning on B being true. We define the conditional belief as the lower envelope (that is, the inf) of a family of conditional probability functions, and provide a closed-form expression for it. An alternate way of understanding our definition of conditional belief is provided by considering ideas from an earlier paper, where we connect belief functions with inner measures. In particular, we show here how to extend the definition of conditional probability to nonmeasurable sets, in order to get notions of inner and outer conditional probabilities, which can be viewed as best approximations to the true conditional probability, given our lack of information. Our definition of conditional belief turns out to be an exact analogue of our definition of inner conditional probability.
In Uncertainty in Artificial Intelligence 6, (eds. P. P. Bonissone, M. Henrion, L. N. Kanal, and J. F. Lemmer), 1991, pp. 347-374. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 6th Conference on Uncertainty in AI, 1990, pp. 317-325.
Reasoning about knowledge: a survey circa 1991
Joseph Y. Halpern
This is my second overview on knowledge. It's an update of the 1986 overview, and a predecessor of the 1995 survey.
Appears in both Encyclopedia of Computer Science and Technology, Vol. 27, Supplement 12 (ed. A. Kent and J. G. Williams), Marcel Dekker, 1993, pp. 275-296. and Encyclopedia of Microcomputers, Vol. 14 (ed. A. Kent and J. G. Williams), Marcel Dekker, 1994, pp. 287-308.
Reasoning about knowledge: a survey
Joseph Y. Halpern
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, artificial intelligence, and theoretical computer science, with particular emphasis on work of the past five years, particularly in computer science.
In Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 4, D. Gabbay, C. J. Hogger, and J. A. Robinson, eds., Oxford University Press, 1995, pp. 1-34. A version of the paper similar to the published version is available in postscript and pdf. This is an update of two earlier surveys, one from 1986 and one from 1991. Of course, this material is all covered much more thoroughly in our book.
A logical approach to reasoning about uncertainty: a tutorial
Joseph Y. Halpern
I consider a logical framework for modeling uncertainty, based on the use of possible worlds, that incorporates knowledge, probability, and time. This turns out to be a powerful approach for modeling many problems of interest. I show how it can be used to give insights into (among other things) several well-known puzzles.
In Discourse, Interaction, and Communication, X. Arrazola, K. Korta, and F. J. Pelletier, eds., Kluwer, 1998, pp. 141-155. The paper is available postscript and pdf.
Axiomatic definitions of programming languages: a theoretical assessment
Albert R. Meyer and Joseph Y. Halpern
A precise definition is given of how partial correction or termination assertions serve to define the semantics of program schemes. Assertions involving only formulas of first-order predicate calculus are proved capable of defining program scheme semantics, and effective axiom systems for deriving such assertions are described. Such axiomatic definitions are possible despite the limited expressive power of predicate calculus.
In Journal of the ACM 29:2, April, 1982, pp. 555-576. A preliminary version appears Proceedings of 7th Annual ACM Symposium on Principles of Programming Languages, 1980, pp. 203-212. The journal paper also includes material from Joseph Y. Halpern and Albert R. Meyer, Axiomatic definitions of programming languages, II, Proceedings of 8th Annual ACM Symposium on Principles of Programming Languages, 1981, pp. 139-148.
Deterministic propositional dynamic logic: finite models, complexity, and completeness
Mordechai Ben-Ari, Joseph Y. Halpern, and Amir Pnueli
Let p be a formula in deterministic propositional dynamic logic. A decision procedure for the satisfiability of p is given along with a construction of a finite model for every satisfiable p. The decision procedure runs in deterministic exponential time and the size of the model are both exponential in the length of p. Finally, a complete axiomatization for deterministic propositional dynamic logic is given, based on the Segerberg axioms for propositional dynamic logic.
In Journal of Computer and Systems Science 25:3, 1982, pp. 402-417. A preliminary version with the title ``Finite models of deterministic propositional dynamic logic'', appears in Proceedings of the 8th International Colloquium on Automata, Languages, and Programming, 1981, pp. 249-263.
The propositional dynamic logic of deterministic, well-structured programs
Joseph Y. Halpern and John H. Reif
We consider a restricted propositional dynamic logic, Strict Deterministic Propositional Dynamic Logic (SDPDL), which is appropriate for reasoning about deterministic well-structured programs. In contrast to PDL, for which the validity problem is known to be complete in deterministic exponential time, the validity problem for SDPDL is shown to polynomial space complete. We also show that SDPDL is less expressive than PDL, and given a complete axiomatization for it. The results rely on structure theorems for models of satisfiable SDPDL formulas, and the proofs give insight into the effects of nondeterminism on intractability and expressiveness in program logics.
In Theoretical Computer Science 27, 1983, pp. 127-165. A preliminary version appears in Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science, 1981, pp. 322-334.
Effective axiomatizations of Hoare Logics
Edmund M. Clarke, Joseph Y. Halpern, and Steven M. German
For a wide class of programming languages P and expressive interpretations I, it is shown that there exist sound and relatively complete Hoare logics for both partial correctness and termination assertions. In fact, under mild assumptions on P and I it is shown that the assertions true in I are uniformly decidable in the theory of I (Th(I)) iff the halting problem for P is decidable for finite interpretations. Moreover, the set of true terminations is uniformly recursively enumerable in Th(I) even if the halting problem for P is not decidable for finite interpretations. Since total-correctness assertions coincide with termination assertions for deterministic programming languages, this last result unexpectedly suggests that good axiom systems for total correctness may exist for a wider spectrum of languages than is the case for partial correctness.
In Journal of the ACM 30:3, 1983, pp. 612-637. A preliminary version appears in Proceeding of the 9th Annual ACM Symposium on Principles of Programming Languages, 1982, pp. 309-321.
Deterministic process logic is elementary
Joseph Y. Halpern
Process Logic (PL) is a language for reasoning about the behavior of a program during a computation, while Propositional Dynamic Logic (PDL) can only reason about the input-output states of a program. Nevertheless, we show that to each PL model M, there corresponds in a natural way a PDL model M' such that each path in M is represented by a state in M'. Moreover, to every PL formula p, there corresponds a PDL formula p', whose length is linear in that of p, such that p is true of a path in M iff p' is true of the state which represents that path in M'. We then show that p is satisfiable iff p' is satisfiable in a finite PDL model with special properties which we call a pseudomodel. The size of the pseudomodel is in general nonelementary but is bounded by both the depth of nesting of the suf operator and the alternation of the suf and diamond operators. However, for DPL, a deterministic version of PL, the pseudomodel has exponential size, giving us a deterministic exponential time procedure for deciding DPL validity. These results suggest that it is the interaction between nondeterministic programs and the suf operator that makes the general decision problem for PL so difficult.
In Information and Control 57:1, 1983, pp. 56-89. A preliminary version appears in Proceedings of 23rd Annual Symposium on the Foundations of Computer Science, 1982, pp. 204-216.
Decision procedures and expressiveness in the temporal logic of branching time
E. Allen Emerson and Joseph Y. Halpern
We consider the computation tree logic (CTL) proposed by Emerson and Clarke, which extends the unified time logic (UB) of Ben-Ari, Manna, and Pnueli by adding an until operator. It is established that CTL has the small model property by showing that any satisfiable CTL formula is satisfiable in a small finite model obtained from the small ``pseudomodel'' resulting from the Fischer-Ladner quotient construction. Then an exponential-time algorithm is given for deciding satisfiability in CTL, and the axiomatization of UB given by Ben-Ari, Manna, and Pnueli is extended to a complete axiomatization for CTL. Finally, the relative expressive power of a family of temporal logics obtained by extending or restricting the syntax of UB and CTL is studied.
In Journal of Computer and Systems Science 30:1, 1985, pp. 1-24; available in pdf. A preliminary version appears in Proceedings of the 14th ACM Symposium on Theory of Computing, 1982, pp. 169-180.
Optimal precision in the presence of uncertainty
Joseph Y. Halpern, Nimrod Megiddo, and Ashfaq Munshi
We consider the problem of achieving coordinated actions in a real-time distributed system. In particular, we consider how closely (in terms of real time) processors can be guaranteed to perform a particular action, in a system where message transmission is guaranteed, but there is some uncertainty in message transmission time. We present an algorithm to achieve optimal precision in arbitrary networks. In networks where clocks run at the rate of real time, the optimal precision achievable in a network is exactly how tightly clocks can be guaranteed to be synchronized.
In Journal of Complexity 1, 1985, pp. 170-196. A preliminary version appears in Proceedings of 17th ACM Symposium on the Theory of Computing, 1985, pp. 346-355.
Equations between regular terms and an application to process logic
Ashok K. Chandra, Joseph Y. Halpern, Albert R. Meyer, and Rohit Parikh
Regular terms with the Kleene operations union, concatenation, and * can be thought of as operators on languages, generating other languages. An equation T1 = T2 between two such terms is said to be satisfiable just in case languages exist which make this equation true. We show that the satisfiability problem even for *-free regular terms is undecidable. Similar techniques are used to show that a very natural extension of the Process Logic of Harel, Kozen, and Parikh is undecidable.
In SIAM J. Computing 14:4, 1985, pp. 935-942. A preliminary version appears in Proceedings of 13th ACM Symposium on Theory of Computing, 1981, pp. 384-390.
``Sometimes'' and ``not never'' revisited: on branching vs. linear time
E. Allen Emerson and Joseph Y. Halpern
The differences between and appropriateness of branching versus linear time temporal logic for reasoning about concurrent programs is studied. These issues have been previously considered by Lamport. To facilitate a careful examination of these issues, a language, CTL*, in which a universal or existential or existential path quantifier can prefix an arbitrary linear time assertion, is defined. The expressive power of a number of sublanguages is then compared. CTL* is also related to the logics MPL of Abrahamson and PL of Harel, Kozen, and Parikh. The paper concludes with a comparison of the utility of branching and linear time temporal logics.
In Journal of the ACM 33:1, 1986, pp. 151-178 on branching vs. linear time, Proceedings of the 10th Annual ACM Symposium on Principles of Programming Languages, 1983, pp. 127-140.
Joseph Y. Halpern, Michael C. Loui, Albert R. Meyer, and Daniel Weise
Paul and Reischuk devised space efficient simulations of logarithmic cost random access machines and multidimensional Turing machines. We simplify their general space reduction technique and extend it to other computational models, including pointer machines, which model computations on graphs and data structures. Every pointer machine of time complexity T(n) can be simulated by a pointer machine of space complexity O(T(n)/log T(n)).
In Math. Systems Theory 19, 1986, pp. 13-28.
On the possibility and impossibility of achieving clock synchronization
Danny Dolev, Joseph Y. Halpern, and H. Raymond Strong
It is known that clock synchronization can be achieved in the presence of faulty processors as long as the nonfaulty processors are connected, provided that some authentication technique is used. Without authentication the number of faults that can be tolerated has been an open question. Here we show that if we restrict logical clocks to running within some linear function of real time, then clock synchronization is impossible, without authentication, when one-third or more of the processors are faulty. However, if there is a bound on the rate at which a processor can generate messages, then we show that clock synchronization is achievable, without authentication, as long as the faults do not disconnect the network. Finally, we provide a lower bound on the closeness to which simultaneity can be achieved in the network as a function of the transmission and processing delay properties of the network.
In Journal of Computer and Systems Science 32:2, 1986, pp. 230-250. A preliminary version appears in Proceedings of the 16th ACM Symposium on the Theory of Computing, 1984, pp. 504-511.
Cheating husbands and other stories: a case study in knowledge, action, and communication
Y. O. Moses, Danny Dolev, and Joseph Y. Halpern
The relationship between knowledge and action is a fundamental one: a processor in a computer network (or a robot or a person, for that matter) should base its actions on the knowledge (or information) it has. One of the main uses of communication is passing around information that may eventually be required by the receiver in order to decide upon subsequent actions. Understanding the relationship between knowledge, action, and communication is fundamental to the design of computer network protocols, intelligent robots, etc. By looking at a number of variants of the cheating husbands puzzle, we illustrate the subtle relationship between knowledge, communication, and action in a distributed environment.
In Distributed Computing 1:3, 1986, pp. 167-176. A preliminary version appears in Proceedings of the 4th ACM Symposium on Principles of Distributed Computing, 1985, pp. 215-223. Available in pdf.
Taken by surprise: the paradox of the surprise test revisited
Joseph Y. Halpern and Yoram Moses.
We reexamine the surprise test paradox (also called the hangman paradox) and translate it into a formal logic with a fixed-point operator and a provability operator. We consider four possible translations of the paradox. The first is contradictory, the second is consistent with the test being given any day of the week including the last, the third rules out the last day (but no others), while the fourth does not even admit of a reasonable semantic interpretation, and is paradoxical in that it is consistent if and only if it is inconsistent!
In Journal of Philosophical Logic 15:3, 1986, pp. 281-304. Available in pdf.
A new look at fault-tolerant network routing
Danny Dolev, Joseph Y. Halpern, Barbara B. Simons, and H. Raymond Strong
We model a communication network as a graph in which a processor is a node and a communication link is an edge. A routing for such a network is a fixed path, or route, between each pair of nodes. Given a network with a predefined routing, we study the effects of faulty components on the routing. Of particular interest is the number of routes along which a message must travel between any two non-faulty nodes. This problem is analyzed for specific families of graphs and for classes of routings. We also give some bounds for general versions of the problem. Finally, we conclude with one of the most important contributions of this paper, a list of interesting and apparently difficult open problems.
In Information and Computation 72:3, 1987, pp. 180-196. A preliminary version appears in Proceedings of the 16th ACM Symposium on the Theory of Computing, 1984, pp. 526-535.
A logic to reason about likelihood
Joseph Y. Halpern and Michael O. Rabin
We present a logic LL which uses a modal operator L to help capture the notion of likely. Despite the fact that no use is made of numbers, LL can capture many of the properties of likelihood in an intuitively appealing way. Using standard techniques of modal logic, we give a complete axiomatization for LL and show that satisfiability of LL formulas can be decided in exponential time. We discuss how the logic might be used in areas where decision making is crucial, such as management and medical diagnosis, and conclude by using LL to give a formal proof of correctness of a protocol for exchanging secrets.
In Artificial Intelligence 32:3, 1987, pp. 379-405; a version is available in pdf. A preliminary version appears in Proceedings of the 15th ACM Symposium on the Theory of Computing, 1983, pp. 310-319. See also Likelihood, probability, and knowledge.
Belief, awareness, and limited reasoning
Ronald Fagin and Joseph Y. Halpern
Several new logics for belief and knowledge are introduced and studied, all of which have the property that agents are not logically omniscient. In particular, in these logics, the set of beliefs of an agent does not necessarily contain all valid formulas. Thus, these logics are more suitable than traditional logics for modeling beliefs of humans (or machines) with limited reasoning capabilities. Our first logic is essentially an extension of Levesque's logic of implicit and explicit belief, where we extend to allow multiple agents and higher-level belief (i.e., beliefs about beliefs). Our second logic deals explicitly with ``awareness'', where, roughly speaking, it is necessary to be aware of a concept before one can have beliefs about it. Our third logic gives a model of ``local reasoning'', where an agent is viewed as a ``society of minds'', each with its own cluster of beliefs, which may contradict each other.
In Artificial Intelligence 34, 1988, pp. 39-76. A preliminary version appears in Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI 85), 1985, pp. 491-501. The full paper is here.
The complexity of reasoning about knowledge and time, I: lower bounds
Joseph Y. Halpern and Moshe Y. Vardi
We study the propositional modal logic of knowledge and time for distributed systems. We consider a number of logics (ninety-six in all!), which vary according to the choice of language and the assumptions made on the underlying system. The major parameters in the language are whether there is a common knowledge operator, whether we reason about the knowledge of one or more than one processor, and whether our temporal operators are branching or linear. The assumptions on distributed systems that we consider are: whether or not processors forget, whether or not processors learn, whether or not time is synchronous, and whether or not there is a unique initial state in the system. We completely characterize the complexity of the validity problem for all the logics we consider. This paper focuses on lower bounds; a sequel will deal with the corresponding upper bounds. Typical results include a -completeness result for the language with common knowledge with respect to systems where processors do not forget, and a corresponding non-elementary-time result for the language without common knowledge. It is shown that, in general, the assumption that processors do not forget or do not learn greatly increases the complexity of reasoning about knowledge and time.
In Journal of Computer and Systems Science 38:1, 1989, pp. 195-237. Preliminary versions of some of the material in this paper can be found in ``The complexity of reasoning about knowledge and time'', Proceedings of 18th ACM Symposium on the Theory of Computing, 1986, pp. 304-314 and ``Reasoning about knowledge and time in asynchronous systems'', Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 53-65. We hope to bring out part II on lower bounds in the reasonably near future.
Likelihood, probability, and knowledge
Joseph Y. Halpern and David A. McAllester
The modal logic LL was introduced by Halpern and Rabin as a means of doing qualitative reasoning about likelihood. Here the relationship between LL and probability theory is examined. It is shown that there is a way of translating probability assertions into LL in a sound manner, so that LL in some sense can capture the probabilistic interpretation of likelihood. However, the translation is subtle; several more obvious attempts are shown to lead to inconsistencies. We also extend LL by adding modal operators for knowledge. This allows us to reason about the interaction between knowledge and likelihood. The propositional version of the resulting logic LLK is shown to have a complete axiomatization and to be decidable in exponential time, provably the best possible.
In Computational Intelligence, 5, pp. 151-160, 1989; a version is available in pdf. A preliminary version appears in AAAI-84 (Proceedings of the Second National Conference on Artificial Intelligence, 1984, pp. 137-141.
Reasoning about procedures as parameters in the language L4
Steven M. German, Edmund M. Clarke, and Joseph Y. Halpern
We provide a sound and relatively complete axiom system for partial correctness assertions in an Algol-like language with procedures passed as parameters, but with no global values (known traditionally as L4). The axiom system allows us to reason syntactically about programs and to construct proofs for assertions about complicated programs from proofs of assertions about their components. Such an axiom system has been sought by a number of researchers, but no previously published solution has been entirely satisfactory. Our axiom system extends the natural style of reasoning used in previous Hoare systems to programs with procedures of higher type. The details of the proof that our axiom system is relatively complete in the sense of Cook may be of independent interest, because we introduce results about expressiveness for programs with higher types that are useful beyond the immediate problem of the language L4. We also prove a new incompleteness result that applies to our logic and to similar Hoare logics.
In Information and Computation, 83:3, 1989, pp. 265-359 (the whole volume). Some material in this paper appeared in preliminary form in ``True relative completeness of an axiom system for L4'', Proceedings of the IEEE Symposium on Logic in Computer Science, 1986, pp. 11-25 and ``Reasoning about procedures with parameters'' Proceedings of the CMU Logics of Programs Conference, Lecture Notes in Computer Science, 1983, pp. 206-220.
Modelling knowledge and action in distributed systems
Joseph Y. Halpern and 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 time to global states and a global state is a tuple consisting of an environment state and a local state for each process in the system. This model is a generalization of those used in many previous papers. Actions in this model are associated with functions from global states to global states. A protocol is a function from local states to actions. We extend the standard notion of a protocol by defining knowledge-based protocols, ones in which a process' actions may depend explicitly on its knowledge. Knowledge-based protocols provide a natural way of describing how actions should take place in a distributed system. Finally, we show how the notion of one protocol implementing another can be captured in our model.
In Distributed Computing, 3:4, 1989, pp. 159-177. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of Concurrency-88, 1988, pp. 18-32; some material also appears in ``A formal model of knowledge, action, and communication in distributed systems'', Proceedings of the 4th ACM Symposium on Principles of Distributed Computing, 1985, pp. 224-236.
Completeness of rewrite rules and rewrite strategies for FP
Joseph Y. Halpern, John H. Williams and Edward L. Wimmers
We consider languages whose operational semantics is given by a set of rewrite rules. For such languages, it is important to be able to determine that there are enough rules to be able to compute the correct meaning of all expressions, but not so many that the system of rules is inconsistent. We develop a formal framework in which to give a precise treatment of these completeness and soundness issues, and then investigate them in the context of an extended version of the functional programming language FP. We show that the rewrite rules of FP are sound and complete with respect to three different notions of completeness. In the latter half of the paper we turn our attention to rewrite strategies. In order to implement a language based on rewrite rules, it does not suffice to know that there are ``enough'' rules in the language; we also need to have a good strategy for determining the order in which to apply them. But what is ``good''? Corresponding to each of our notions of completeness there is a notion of a good rewrite strategy. We examine and characterize these notions of goodness, and give examples of a number of natural good strategies. Although we have confined ourselves to FP here, we believe that our techniques (some of which are nontrivial extensions of techniques first used in the context of lambda-calculus) will apply well beyond the realm of FP rewriting systems.
In Journal of the ACM, 37:1, 1990, pp. 86-143. Some material in this paper appeared in preliminary form in ``Denotational semantics and rewrite rules for FP'', Joseph Y. Halpern, John H. Williams, Edward L. Wimmers, and Timothy C. Winkler, Proceedings of the 12th Annual ACM Symposium on Principles of Programming Languages, 1985, pp. 108-120 and ``Good rewriting strategies for FP'', Joseph Y. Halpern, John H. Williams, and Edward L. Wimmers, Proceedings of the IEEE Symposium on Logic in Computer Science, 1986, pp. 149-162.
Knowledge and common knowledge in a distributed environment
Joseph Y. Halpern and Yoram Moses
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 protocols. Communication in a distributed system can be viewed as the act of transforming the system's state of knowledge. This paper presents a general framework for formalizing and reasoning about knowledge in distributed systems. We argue that states of knowledge of groups of processors are useful concepts for the design and analysis of distributed protocols. In particular, distributed knowledge corresponds to knowledge that is ``distributed'' among the members of the group, while common knowledge corresponds to a fact being ``publicly known''. The relationship between common knowledge and a variety of desirable actions in a distributed system is illustrated. Furthermore, it is shown that, formally speaking, in practical systems common knowledge cannot be attained. A number of weaker variants of common knowledge that are attainable in many cases of interest are introduced and investigated.
In Journal of the ACM, 37:3, 1990, pp. 549-587. A version of the paper similar to the published version is available at CoRR and locally in postscript and pdf. A preliminary version appears in Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing, 1984, pp. 50-61.
A logic for reasoning about probabilities
Ronald Fagin, Joseph Y. Halpern, and Nimrod Megiddo
We consider a language for reasoning about probability which allows us to make statements such as ``the probability of E is less than 1/3'' and ``the probability of E is at least twice the probability of F'', where E and F are arbitrary events. We consider the case where all events are measurable (i.e., represent measurable sets) and the more general case, which is also of interest in practice, where they may not be measurable. The measurable case is essentially a formalization of (the propositional fragment of) Nilsson's probabilistic logic. As we show in a companion paper, the general (nonmeasurable) case corresponds precisely to replacing probability measures by Dempster-Shafer belief functions. In both cases, we provide a complete axiomatization and show that the problem of deciding satisfiability is NP-complete, no worse than that of propositional logic. As a tool for proving our complete axiomatizations, we give a complete axiomatization for reasoning about Boolean combinations of linear inequalities, which is of independent interest. This proof and others make crucial use of results from the theory of linear programming. We then extend the language to allow reasoning about conditional probability, and show that the resulting logic is decidable and completely axiomatizable, by making use of the theory of real closed fields.
In Information and Computation, 87:1,2, 1990, pp. 78-128. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 3rd IEEE Conference on Logic in Computer Science, 1988, pp. 410-421.
An analysis of first-order logics of probability
Joseph Y. Halpern
We consider two approaches to giving semantics to first-order logics of probability. The first approach puts a probability on the domain, and is appropriate for giving semantics to formulas involving statistical information such as ``The probability that a randomly chosen bird flies is greater than .9.'' The second approach puts a probability on possible worlds, and is appropriate for giving semantics to formulas describing degrees of belief, such as ``The probability that Tweety (a particular bird) flies is greater than .9.'' We show that the two approaches can be easily combined, allowing us to reason in a straightforward way about statistical information and degrees of belief. We then consider axiomatizing these logics. In general, it can be shown that no complete axiomatization is possible. We provide axiom systems that are sound and complete in cases where a complete axiomatization is possible, showing that they do allow us to capture a great deal of interesting reasoning about probability.
In Artificial Intelligence 46, 1990, pp. 311-350. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI 89), 1989, pp. 1375-1381.
Let many flowers bloom: a response to ``An inquiry into computer understanding''
Joseph Y. Halpern Two main issues are addressed in this response to Peter Cheeseman's ``An inquiry into computer understanding'' and ``In defense of `An inquiry into computer understanding' '': (1) the ``right'' approach to reasoning about uncertainty and (2) the relationship between logic and probability.
In Computational Intelligence 6, 1990, pp. 184-188. A version of the paper similar to the published version is available in postscript and pdf.
Presburger arithmetic with unary predicates is complete
Joseph Y. Halpern
We give a simple proof characterizing the complexity of Presburger arithmetic augmented with additional predicates. We show that Presburger arithmetic with additional predicates is complete. Adding unary predicate is enough to get hardness, while adding more predicates (of any arity) does not make the complexity any worse.
In Journal of Symbolic Logic, 56:2, 1991, pp. 637-642. A version of the paper similar to the published version is available in postscript and pdf.
The relationship between knowledge, belief, and certainty
Joseph Y. Halpern
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 certainty with belief, interpreted probabilistically. We show that if we assume one fixed probability assignment, then the logic KD45, which has been identified as perhaps the most appropriate for belief, provides a complete axiomatization for reasoning about certainty. Just as an agent may believe a fact p although p is false, he may be certain that a fact p is true although p is false. However, it is easy to see that an agent can have such false (probabilistic) beliefs only at a set of worlds of probability 0. If we restrict attention to structures where all worlds have positive probability, then S5 provides a complete axiomatization. If we consider a more general setting, where there might be a different probability assignment at each world, then by placing appropriate conditions on the support of the probability function (the set of worlds which have non-zero probability), we can capture many other well-known modal logics, such as T and S4. Finally, we consider Miller's principle, a well-known principle relating higher-order probabilities to lower-order probabilities, and show that in a precise sense KD45 characterizes certainty in those structures satisfying Miller's principle.
In Annals of Mathematics and Artificial Intelligence 4, 1991, pp. 301-322. A version of the paper similar to the published paper is available in postscript and pdf. There is a bug in the published version; a correction is available in postscript and pdf, and appears in Annals of Mathematics and Artificial Intelligence 26, 1999, pp. 253-256. A preliminary version appears in Proceedings of the 5th Workshop on Uncertainty in AI, 1989, pp. 142-151.
A model-theoretic analysis of knowledge
Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi
Understanding knowledge is a fundamental issue in many disciplines. In computer science, knowledge arises not only in the obvious contexts (such as knowledge-based systems), but also in distributed systems (where the goal is to have each processor ``know'' something, as in agreement protocols). A general semantic model of knowledge is introduced, to allow reasoning about statements such as ``He knows that I know whether or not she knows whether or not it is raining.'' This approach more naturally models a state of knowledge than previous proposals (including Kripke structures). Using this notion of model, a model theory for knowledge is developed. This theory enables one to interpret the notion of a ``finite amount of information''.
In Journal of the ACM, 38:2, 1991, pp. 382-428. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 25th Annual Conference on Foundations of Computer Science, 1984, pp. 268-278.
A propositional modal interval logic
Joseph Y. Halpern and 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 end we develop a modal temporal logic based on time intervals, a logic which can be viewed as a generalization of point-based modal temporal logic. We discuss related logics, give an intuitive presentation of the new logic, and define its formal syntax and semantics. We make no assumption about the underlying nature of time, allowing it to be discrete (such as the natural numbers) or continuous (such as the rationals or the reals), linear or branching, complete (such as the reals) or not (such as the rationals). We show, however, that there are formulas in the logic that allow us to distinguish all these situations. We also give a translation of our logic into first-order logic, which allows us to apply some results on first-order logic to our modal one. Finally, we consider the difficulty of validity problems for the logic. This turns out to depend critically, and in surprising ways, on our assumptions about time. For example, if we take our underlying temporal structure to be the rationals, we can show that the validity problem is r.e.-complete, if it is the reals then we can show that validity is -hard, and if it is the natural numbers, then validity is -complete.
In Journal of the ACM, 38:4, 1991, pp. 935-962. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the IEEE Symposium on Logic in Computer Science, 1986, pp. 279-292.
Clock synchronization and the power of broadcasting
Joseph Y. Halpern and 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 no upper bound on message transmission time, but that broadcast messages are guaranteed to be received within an interval of size d, for some fixed constant d. This is intended to be an idealization of what happens in multiple access networks, such as the Ethernet. We then consider tradeoffs between the type and number of broadcasts, and the tightness of synchronization. Our results include (1) matching upper and lower bounds of (1 + 1/K)d on the precision of clock synchronization attainable for processes using K (n-1)-casts, for K between 3 and n, (2) matching upper and lower bounds of (1 + 1/n)d on the precision of clock synchronization attainable for n > 2 processes using an arbitrary number of (n-1)-casts, and (3) matching upper and lower bounds of (1 + (n-2)/n)d on the precision attainable using 2-casting.
In Distributed Computing 5:2, 1991, pp. 73-83. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 28th Annual Allerton Conference on Communication, Control, and Computing, 1990, pp. 588-597.
Uncertainty, belief, and probability
Ronald Fagin and Joseph Y. Halpern
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 nonmeasurable event (one to which we do not assign a probability), we can talk about only the inner measure and outer measure of the event. In addition to removing the requirement that every event be assigned a probability, our approach circumvents other criticisms of probability-based approaches to uncertainty. For example, the measure of belief in an event turns out to be represented by an interval (defined by the inner and outer measure), rather than by a single number. Further, this approach allows us to assign a belief (inner measure) to an event without committing to a belief about its negation (since the inner measure of an event plus the inner measure of its negation is not necessarily one). Interestingly enough, inner measures induced by probability measures turn out to correspond in a precise sense to Dempster-Shafer belief functions. Hence, in addition to providing promising new conceptual tools for dealing with uncertainty, our approach shows that a key part of the important Dempster-Shafer theory of evidence is firmly rooted in classical probability theory.
In Computational Intelligence 7, 1991, pp. 160-173. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI 89), 1989, pp. 1161-1167.
What can machines know? On the properties of knowledge in distributed systems
Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi
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 notion that can be shown to satisfy all the axioms of the modal logic S5. We carefully examine the properties of this notion of knowledge and show that they depend crucially, and in subtle ways, on assumptions we make about the system and about the language used for describing knowledge. We present a formal model in which we can capture various assumptions frequently made about systems, such as whether they are deterministic or nondeterministic, whether knowledge is cumulative (which means that processes never ``forget''), and whether or not the ``environment'' affects the state transitions of the processes. We then show that under some assumptions about the system and the language, certain states of knowledge are not attainable and the axioms of S5 do not completely characterize the properties of knowledge; extra axioms are needed. We provide complete axiomatizations for knowledge in a number of cases of interest.
In Journal of the ACM, 39:2, 1992, pp. 328-376. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears with the title ``What can machines know? On the epistemic properties of machines'' appears in AAAI-86 (Proceedings of Fourth National Conference on Artificial Intelligence, 1986, pp. 428-434.
Two views of belief: belief as generalized probability and belief as evidence
Joseph Y. Halpern and Ronald Fagin
Belief functions are mathematical objects defined to satisfy three axioms that look somewhat similar to the Kolmogorov axioms defining probability functions. We argue that there are (at least) two useful and quite different ways of understanding belief functions. The first is as a generalized probability function (which technically corresponds to the inner measure induced by a probability function). The second is as a way of representing evidence. Evidence, in turn, can be understood as a mapping from probability functions to probability functions. It makes sense to think of updating a belief if we think of it as a generalized probability. On the other hand, it makes sense to combine two beliefs (using, say, Dempster's rule of combination) only if we think of the belief functions as representing evidence. Many previous papers have pointed out problems with the belief function approach; the claim of this paper is that these problems can be explained as a consequence of confounding these two views of belief functions.
In Artificial Intelligence 54, 1992, pp. 275-317. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in AAAI-90 (Proceedings of the Eighth National Conference on Artificial Intelligence, 1990, pp. 112-119.
A guide to completeness and complexity for modal logics of knowledge and belief
Joseph Y. Halpern and Yoram Moses
We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with three particular points of emphasis: (1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief, (2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, and (3) we discuss how notions of common knowledge and distributed knowledge among a group of agents fit into the possible-worlds framework, As far as complexity is concerned, we show, among other results, that while the problem of deciding satisfiability of an S5 formula with one agent is NP-complete, the problem for many agents is PSPACE-complete. Adding a distributed knowledge operator does not change the complexity, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time.
In Artificial Intelligence 54, 1992, pp. 319-379. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version, with the title ``A guide to the modal logics of knowledge and belief'' appears in Proceedings of the 9th International Joint Conference on Artificial Intelligence (IJCAI 85), 1985, pp. 480-490.
Joseph Y. Halpern and 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, the Alternating Bit protocol, and Stenning's protocol are all instances of one knowledge-based protocol that we derive. Our derivation leads to transparent and uniform correctness proofs for all these protocols.
In Journal of the ACM, 39:3, 1992, pp. 449-478. A version of the paper similar to the published version is available in postscript and pdf. of the paper similar to the published version. A preliminary version appears in Proceedings of the 6th ACM Symposium on Principles of Distributed Computing, 1987, pp. 269-280.
Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi
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 (we can infer q from p if, for every substitution T, the validity of T[p] entails the validity of T[q]) and truth inference (we can infer q from p if, for every substitution T, the truth of T[p] entails the truth of T[q]). In this paper we introduce a general semantic framework that allows us to investigate the notion of inference more carefully. Validity inference and truth inference are in some sense the extremal points in our framework. We investigate the relationship between various types of inference in our general framework, and consider the complexity of deciding if an inference rule is sound, in the context of a number of logics of interest: classical propositional logic, a nonstandard propositional logic, various propositional modal logics, and first-order logic.
In Journal of Symbolic Logic 57:3, 1992, pp. 1018-1045. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 5th Jerusalem Conference on Information Technology, 1990, pp. 391-401.
Message-optimal protocols for Byzantine agreement
Vassos Hadzilacos and 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 attempts to isolate the key features of reaching agreement. We focus here on the number of messages required to reach BA, with particular emphasis on the number of messages required in the failure-free runs, since these are the ones that occur most often in practice. The number of messages required is sensitive to the types of failures considered. In earlier work, Amdur et al. [1990] established tight upper and lower bounds on the worst- and average-case number of messages required in failure-free runs for crash failures. We provide tight upper and lower bounds for all remaining types of failures that have been considered in the literature on the BA problem: receiving omission, sending omission and general omission failures, as well as arbitrary failures with or without message authentication. We also establish a tradeoff between number of rounds and number of messages in the failure-free runs required to reach agreement in the case of crash, sending and general omission failures.
In Mathematical Systems Theory 26, 1993, pp. 41-102. A version of the paper similar to the published version is available in postscript and pdf. of the paper similar to the published version. A preliminary version of this paper appears in Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, 1991, pp. 309-323.
Vassos Hadzilacos and 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 failures are discovered. We show how a protocol for FD can be extended to one for BA, with no message overhead in the failure-free runs. We also show that, for so-called benign failures, if the FD protocol satisfies an additional property, the message-preserving extension to a BA protocol can be accomplished with minimal time overhead in the failure-free runs. Our results show that FD is a useful building block for BA; indeed, it it has been used in this way in a companion paper.
In Mathematical Systems Theory 26, 1993, pp. 103-129. A version of the paper similar to the published version is available in postscript and pdf.
Knowledge, probability, and adversaries
Joseph Y. Halpern and Mark Tuttle
What should it mean for an agent to know or believe an assertion is true with probability .99? Different papers give different answers, choosing to use quite different probability spaces when computing the probability that an agent assigns to an event. We show that each choice can be understood in terms of a betting game. This betting game itself can be understood in terms of three types of adversaries influencing three different aspects of the game. The first selects the outcome of all nondeterministic choices in the system; the second represents the knowledge of the agent's opponent in the betting game (this is the key place the papers mentioned above differ); the third is needed in asynchronous systems to choose the time the bet is placed. We illustrate the need for considering all three types of adversaries with a number of examples. Given a class of adversaries, we show how to assign probability spaces to agents in a way most appropriate for that class, where ``most appropriate'' is made precise in terms of this betting game. We conclude by showing how different assignments of probability spaces (corresponding to different opponents) yield different levels of guarantees in probabilistic coordinated attack.
In Journal of the ACM, 40:4, 1993, pp. 917-962. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 8th ACM Symposium on Principles of Distributed Computing, 1989, pp. 103-118.
Naming and identity in epistemic logics, I: The propositional case
Adam J.Grove and 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 of any logic because it prohibits, for instance, anonymous agents, agents with many names, named groups of agents, and relative (indexical) reference. Here we examine the principles involved in such cases, and give simple propositional logics that are expressive enough to cope with them all.
In Journal of Logic and Computation, 3:4, 1993, pp. 345-378. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version under the title ``Naming and identity in a multi-agent epistemic logic'' appears in Principles of Knowledge Representation and Reasoning: Proceedings of the Second International Conference (J. A. Allen, R. Fikes, and E. Sandewall, eds.), 1991, pp. 301-312. This preliminary version also contains material from Part II of the paper of which Adam Grove is the sole author; Part II appears in Artificial Intelligence 74, 1995, pp. 311-350.
A response to ``Believing on the basis of evidence''
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
This is part of a special issue of Computational Intelligence devoted to ``Believing on the basis of evidence'', a paper by Henry Kyburg, and responses to it. Kyburg addresses the issue of how we can use our information to reason to a set of conclusions that are plausible but not certain. This set of conclusions goes beyond the set of deductive conclusions. His program is certainly ambitious and the approach he suggests meets with varying degrees of success and failure when it comes to particular issues. We examine and critique a few parts of his approach.
In Computational Intelligence, 10:1, 1994, pp. 21-25 A version of the paper similar to the published version is available in postscript and pdf.
Reasoning about knowledge and probability
Ronald Fagin and Joseph Y. Halpern
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 ``according to agent i, formula p holds with probability at least a.'' The language is powerful enough to allow reasoning about higher-order probabilities, as well as allowing explicit comparisons of the probabilities an agent places on distinct events. We present a general framework for interpreting such formulas, and consider various properties that might hold of the interrelationship between agents' probability assignments at different states. We provide a complete axiomatization for reasoning about knowledge and probability, prove a small model property, and obtain decision procedures. We then consider the effects of adding common knowledge and a probabilistic variant of common knowledge to the language.
In Journal of the ACM, 41:2, 1994, pp. 340-367. A minor corrigendum appears in Journal of the ACM, 45:1, 1998, p. 214. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the Second Conference on Theoretical Aspects of Reasoning About Knowledge, 1988, pp. 277-294.
Decidability and expressiveness for first-order logics of probability
Martin Abadi and 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 in both cases it takes very little to make reasoning about probability highly undecidable. We show that when the probability is on the domain, if the language contains only unary predicates then the validity problem is decidable. However, if the language contains even one binary predicate, the validity problem is -complete, as hard as elementary analysis with free predicate and function symbols. With equality in the language, even with no other symbol, the validity problem is at least as hard as that for elementary analysis, -hard. Thus, the logic cannot be axiomatized in either case. When we put the probability on the set of possible worlds, the validity problem is -complete with as little as one unary predicate in the language, even without equality. With equality, we get -hardness with only a constant symbol. We then turn our attention to an analysis of what causes this overwhelming complexity. For example, we show that if we require rational probabilities then we drop from to In many contexts it suffices to restrict attention to domains of bounded size; fortunately, the logics are decidable in this case. Finally, we show that, although the two logics capture quite different intuitions about probability, there is a precise sense in which they are equi-expressive.
In Information and Computation, 112:1, 1994, pp. 1-36. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 30th Annual Conference on Foundations of Computer Science, 1989, pp. 148-153.
Random worlds and maximum entropy
Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
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 p holds given KB. If we are reasoning about a world or system consisting of N individuals, then we can consider all possible worlds, or first-order models, with domain 1,...,N that satisfy KB, and compute the fraction of them in which p is true. We define the degree of belief to be the asymptotic value of this fraction as N grows large. We show that when the vocabulary underlying p and KB uses constants and unary predicates only, we can naturally associate an entropy with each world. As N grows larger, there are many more worlds with higher entropy. Therefore, we can use a maximum-entropy computation to compute the degree of belief. This result is in a similar spirit to previous work in physics and artificial intelligence, but is far more general. Of equal interest to the result itself are the limitations on its scope. Most importantly, the restriction to unary predicates seems necessary. Although the random-worlds method makes sense in general, the connection to maximum entropy seems to disappear in the non-unary case. These observations suggest unexpected limitations to the applicability of maximum-entropy methods.
In Journal of Artificial Intelligence Research, 2, 1994, pp. 33-88. The paper is available in postscript and pdf. A preliminary version appears in Proceedings of Seventh Annual IEEE Symposium on Logic in Computer Science, 1992, p. 22-33.
Joseph Y. Halpern and 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 for first-order logic. However, our proof gives considerably more information. It leads to an elegant axiomatization for almost-sure structure validity and to sharper complexity bounds. Since frame validity can be reduced to a formula, the 0-1 law for frame validity helps delineate when 0-1 laws exist for second-order logics.
In Annals of Pure and Applied Logic, 69, 1994, pp. 157-193. A version similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of Seventh Annual IEEE Symposium on Logic in Computer Science, 1992 pp. 369-380 (with B. M. Kapron). Unfortunately, one of the main theorems in the paper is incorrect. An erratum appears in Annals of Pure and Applied Logic 121, 2003, pp. 281-283, and is available in postscript and pdf.
Full abstraction and expressive completeness for FP
Joseph Y. Halpern and E. L. Wimmers
We consider issues related to the expressive power of the programming language FP. In particular, we consider whether a number of variants of FP are fully abstract and expressively complete. For example, we show that a version of FP with only one-sided sequences behave similarly to PCF in that the addition of parallel or is sufficient to make it fully abstract. However, the addition of parallel or to FP (with its two-sided infinite sequences) is not sufficient to achieve full abstraction. By considering these and other variants, we obtain a better understanding of what is required of a language and semantics in order to guarantee full abstraction and expressive completeness.
In Information and Computation 118:2, 1995, pp. 246-271. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the Second IEEE Symposium on Logic in Computer Science, 1987, pp. 257-271.
Dynamic fault-tolerant clock synchronization
Danny Dolev, Joseph Y. Halpern, Barbara B. Simons, and H. Raymond 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. Assuming a fault tolerant authentication protocol, the algorithms tolerate both link and processor failures of any type. The algorithm for maintaining synchronization works for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as those of Lamport and Melliar-Smith [1985] and Welch and Lynch [1988], although, unlike them, it does require an authentication protocol to handle Byzantine faults. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement that is provably necessary.
In Journal of the ACM 42:1, 1995, pp. 143-185. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version, with the title ``Fault-tolerant clock synchronization'' appears in Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing, 1984, pp. 89-102.
Joseph Y. Halpern
A well-known result of Ladner says that the satisfiability problem for K45, KD45, and S5 is NP-complete. This result implicitly assumes that there are infinitely many primitive propositions in the language; it is easy to see that the satisfiability problem for these logics becomes linear time if there are only finitely many primitive propositions in the language. By way of contrast, we show that the PSPACE-completeness results of Ladner and Halpern and Moses hold for the modal logics K, T, S4, and for the multi-agent versions of K45, KD45, and S5 (provided there are at least two agents), even if there is only one primitive proposition in the language. We go on to examine the effect on complexity of bounding the depth of nesting of modal operators. If we restrict to finite nesting, then the satisfiability problem is NP-complete for all the modal logics considered but S4. If we then further restrict the language to having only finitely many primitive propositions, the complexity goes down to linear time in all cases.
In Artificial Intelligence, 75:2, 1995, pp. 361-372. A version of the paper similar to the published version is available in postscript and pdf.
Levesque's axiomatization of only knowing is incomplete
Joseph Y. Halpern and Gerhard Lakemeyer
Levesque introduced a notion of ``only knowing'', with the goal of capturing certain types of nonmonotonic reasoning. Levesque's logic dealt with only the case of a single agent. Recently, both Halpern and Lakemeyer independently attempted to extend Levesque's logic to the multi-agent case. Although there are a number of similarities in their approaches, there are some significant differences. In this paper, we reexamine the notion of only knowing, going back to first principles. In the process, we point out some problems with the earlier definitions. This leads us to reconsider what the properties of only knowing ought to be. We provide an axiom system that captures our desiderata, and show that it has a semantics that corresponds to it. The axiom system has an added feature of interest: it includes a modal operator for satisfiability, and thus provides a complete axiomatization for satisfiability in the logic K45.
In Artificial Intelligence 74:2, 1995, pp. 381-387. A version of the paper similar to the published version is available in postscript and pdf.
A nonstandard approach to the logical omniscience problem
Ronald Fagin, Joseph Y. Halpern, and Moshe Y. Vardi
We introduce a new approach to dealing with the well-known logical omniscience problem in epistemic logic. Instead of taking possible worlds where each world is a model of classical propositional logic, we take possible worlds which are models of a nonstandard propositional logic we call NPL, which is somewhat related to relevance logic. This approach gives new insights into the logic of implicit and explicit belief considered by Levesque and Lakemeyer. In particular, we show that in a precise sense agents in the structures considered by Levesque and Lakemeyer are perfect reasoners in NPL.
In Artificial Intelligence, 79:2, 1996, pp. 203-240. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning About Knowledge, 1990, pp. 41-55.
Asymptotic conditional probabilities: the unary case
Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
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 p and q, we consider the structures with domain {1,..., N} that satisfy q, and compute the fraction of them in which p is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown in by Liogonkii and in a companion paper), in the general case, asymptotic conditional probabilities do not always exist, and most questions relating to this issue are highly undecidable. These results, however, all depend on the assumption that q can use a nonunary predicate symbol. Liogonkii shows that if we condition on formulas q involving unary predicate symbols only (but no equality or constant symbols), then the asymptotic conditional probability does exist and can be effectively computed. This is the case even if we place no corresponding restrictions on p. We extend this result here to the case where q involves equality and constants. We show that the complexity of computing the limit depends on various factors, such as the depth of quantifier nesting, or whether the vocabulary is finite or infinite. We completely characterize the complexity of the problem in the different cases, and show related results for the associated approximation problem.
In SIAM Journal on Computing, 25:1, 1996, pp. 1-51. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version (which also includes results of a companion paper), with the title ``Asymptotic conditional probabilities for first-order logic'', appears in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 294-305.
Asymptotic conditional probabilities: the non-unary case
Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
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 p and q, we consider the structures with domain {1,..., N} that satisfy q, and compute the fraction of them in which p is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogonkii, if there is a non-unary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogonkii also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is well-defined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.
In Journal of Symbolic Logic, 61:1, 1996, pp. 250-275. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version (which also includes results of a companion paper), with the title ``Asymptotic conditional probabilities for first-order logic'', appears in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 294-305.
Should knowledge entail belief?
Joseph Y. Halpern
The appropriateness of S5 as a logic of knowledge has been attacked at some length in the philosophical literature. Here one particular attack based on the interplay between knowledge and belief is considered: Suppose that knowledge satisfies S5, belief satisfies KD45, and both the entailment property (knowledge implies belief) and positive certainty (if the agent believes something, she believes she knows it) hold. Then it can be shown that belief reduces to knowledge: it is impossible to have false beliefs. While the entailment property has typically been viewed as perhaps the least controversial of these assumptions, an argument is presented that it can plausibly be viewed as the culprit. More precisely, it is shown that this attack fails if we weaken the entailment property so that it applies only to objective (nonmodal) formulas, rather than to arbitrary formulas. Since the standard arguments in favor of the entailment property are typically given only for objective formulas, this observation suggests that care must be taken in applying intuitions that seem reasonable in the case of objective formulas to arbitrary formulas.
In Journal of Philosophical Logic, 25:5, 1996, pp. 483-494. A version of the paper similar to the published version is available in postscript and pdf.
A theory of knowledge and ignorance for many agents
Joseph Y. Halpern
We extend the notion of ``only knowing'' introduced by Halpern and Moses (see ``Towards a theory of knowledge and ignorance'') to many agents and to a number of modal logics. In this approach, all an agent knows is p is true in a structure M if, in M, the agent knows p and has the maximum number of ``possibilities''. To extend this approach, we need to make precise what counts as a ``possibility''. In the single-agent case, we can identify a possibility with a truth assignment. In the multi-agent case, things are more complicated. We consider three notions of possibility (all related). We argue that the first is most appropriate for non-introspective logics, such as K, T, and S4, the second is most appropriate for K45 and KD45, and the last is most appropriate for S5. With the appropriate notion of possibility, we show that are reasonable extensions in all cases. These results also shed light on the single-agent case. It was always assumed that one of the key aspects of Halpern-Moses approach in the single-agent case was its use of S5, rather than K45 or KD45. Our results show that the notion is better understood in the context of K45 (or KD45). In the single-agent case, the notion remains unchanged if we use K45 instead of S5. However, in the multi-agent case, there are significant differences between K45 and S5. Moreover, in some sense, the K45 variants behave better: all results proved for the single-agent case extend more naturally to the multi-agent case of K45 than to the multi-agent of S5.
In Journal of Logic and Computation, 7:1, 1997, pp. 79-108. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears as ``Reasoning about only knowing with many agents'', AAAI-93 (Proceedings of the Eleventh National Conference on Artificial Intelligence) 1993, pp. 655-661.
From statistical knowledge bases to degrees of belief
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
An intelligent agent will often be uncertain about various properties of its environment, and when acting in that environment it will frequently need to quantify its uncertainty. For example, if the agent wishes to employ the expected-utility paradigm of decision theory to guide its actions, she will need to assign degrees of belief (subjective probabilities) to various assertions. Of course, these degrees of belief should not be arbitrary, but rather should be based on the information available to the agent. This paper describes one approach for inducing degrees of belief from very rich knowledge bases, which might include information about particular individuals, statistical correlations, physical laws, and default rules. We call our approach the random-worlds method. This method is based on a principle of indifference: it treats all of the worlds the agent considers possible as being equally likely. It is able to integrate qualitative default reasoning with quantitative probabilistic reasoning by providing a language in which both types of information can be easily expressed. Our results show that a number of desiderata that arise in direct inference (reasoning from statistical information to conclusions about individuals) and default reasoning follow directly from the semantics of random worlds. For example, random worlds captures important patterns of reasoning such as specificity, inheritance, indifference to irrelevant information, and default assumptions of independence. Furthermore, the expressive power of the language used and the intuitive semantics of random worlds allow the method to deal well with problems that are beyond the scope of many other non-deductive reasoning systems.
In Artificial Intelligence 87:1-2, 1996, pp. 75-143, A version of the paper similar to the published version is available in postscript and pdf. Some material in this paper appeared in preliminary form in ``Statistical foundations for default reasoning'', Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI 93), 1993, pp. 563-569.
A critical reexamination of default logic, autoepistemic logic, and only knowing
Joseph Y. Halpern
Fifteen years of work on nonmonotonic logic has certainly increased our understanding of the area. However, given a problem in which nonmonotonic reasoning is called for, it is far from clear how one should go about modeling the problem using the various approaches. In particular, we return to the original technical definitions given in these papers, and examine the extent to which they capture the intuitions they were designed to capture.
In Computational Intelligence 13:1, 1997, pp. 144-163. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Computational Logic and Proof Theory (Proceedings of the Kurt Gödel Symposium, KGC '93), Lecture Notes in Computer Science, vol. 713, Springer, 1993, pp. 43-60.
On ambiguities in the interpretation of game trees
Joseph Y. Halpern
Piccione and Rubinstein have pointed out ambiguities in the interpretation of games of imperfect recall. They focus on the notion of time consistency, and argue that a player in a game of imperfect recall may be time inconsistent, changing his strategy despite no new information and no change in his preferences. In this paper, it is argued that the apparent time inconsistency arises from implicit assumptions made in the definition about what the driver knows when he reconsiders his strategy and what he will remember if he changes his strategy, and about how the node at which reconsideration takes place is chosen. A model is proposed, based on earlier work in the computer science literature, that allows us -- indeed, almost forces us -- to make these issues explicit. Once these issues are made explicit, time inconsistency seems less inconsistent.
In Games and Economic Behavior 20, 1997, pp. 66-96. A preliminary version appears in Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge, 1996, pp. 77-96. A version of the paper similar to the published version is available in postscript and pdf.
On the expected value of games with absentmindedness
Adam J. Grove and Joseph Y. Halpern
Piccione and Rubinstein have argued that a seemingly paradoxical form of time inconsistency can arise in games of imperfect recall. At the heart of this argument is a calculation of the expected value of a game, from the standpoint of a player who is in the middle of play. We claim that this concept is not well defined in games with absentmindedness (that is, games where two nodes in the same path can be in one information set). To make it well defined, additional assumptions must be made. We show that there are reasonable assumptions under which no time inconsistency arises. It is also possible to make assumptions that validate Piccione and Rubinstein's calculations, but the nature of these assumptions is generally such as to remove the appearance of paradox.
In Games and Economic Behavior 20, 1997, pp. 51-65. A version of the paper similar to the published version is available in postscript and pdf.
Performing work efficiently in the presence of faults
Cynthia Dwork, Joseph Y. Halpern, and 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; we want to guarantee that in every execution of the protocol in which at least one process survives, all n units of work will be performed. We consider three parameters: the number of messages sent, the total number of units of work performed (including multiplicities), and time. We present three protocols for solving the problem. All three are work-optimal, doing O(n+t) work. The first has moderate costs in the remaining two parameters, sending O() messages, and taking (n+t) time. This protocol can be easily modified to run in any completely asynchronous system equipped with a failure detection mechanism. The second sends only O() messages, but its running time is exponential in n and t. The third is essentially time-optimal in the (usual) case in which there are no failures, and its time complexity degrades gracefully as the number of failures increases.
SIAM Journal on Computing 27:5, 1998. A version of the paper similar to the published version is available at CoRR and locally in postscript and pdf. A preliminary version appears in Proceedings of the Eleventh Annual ACM Symposium on Principles of Distributed Computing, 1992, pp. 91-102.
Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi
Reasoning about activities in a distributed system at the level of knowledge allows us to abstract away from many irrelevant details. We introduce two notions to facilitate designing and reasoning about systems in terms of knowledge. The first is knowledge-based programs, which improve upon Halpern and Fagin's definition of knowledge-based protocols. Knowledge-based programs are syntactic objects: programs with tests for knowledge. The second notion is contexts, which capture the setting in which a program is executed. In a given context, a standard program (one without tests for knowledge) is represented by (i.e., corresponds in a precise sense to) a unique system. A knowledge-based program, on the other hand, may be represented by no system, one system, or many systems. We provide a condition that is sufficient to guarantee that a knowledge-based program is represented by a unique system, and covers many of the knowledge-based programs considered in the literature. We also characterize the complexity of determining whether a given knowledge-based program has a unique representation, or any representation at all, in a finite-state context.
In Distributed Computing 10:4, 1997, pp. 199-225. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995, pp. 153-163. There is significant overlap between this paper and Chapters 4, 5, and 7 of our book, although the paper has some new material.
Modeling belief in dynamic systems. Part I: Foundations
Nir Friedman and Joseph Y. Halpern
Belief change is a fundamental problem in AI: Agents constantly have to update their beliefs to accommodate new observations. In recent years, there has been much work on axiomatic characterizations of belief change. We claim that a better understanding of belief change can be gained from examining appropriate semantic models. In this paper we propose a general framework in which to model belief change. We begin by defining belief in terms of knowledge and plausibility: an agent believes p if he knows that p is more plausible than not-p. We then consider some properties defining the interaction between knowledge and plausibility, and show how these properties affect the properties of belief. In particular, we show that by assuming two of the most natural properties, belief becomes a KD45 operator. Finally, we add time to the picture. This gives us a framework in which we can talk about knowledge, plausibility (and hence belief), and time, which extends the framework of Halpern and Fagin for modeling knowledge in multi-agent systems. We then examine the problem of ``minimal change''. This notion can be captured by using prior plausibilities, an analogue to prior probabilities, which can be updated by ``conditioning''. We show by example that conditioning on a plausibility measure can capture many scenarios of interest. In a companion paper, we show how the two best-studied scenarios of belief change, belief revision and belief update, fit into our framework.
In Artificial Intelligence 95:2, 1997, pp. 257-316. A version of the paper similar to the published version is available at CoRR and locally in postscript and pdf. An earlier (and much different) version of the paper appeared under the title "A knowledge-based framework for belief change, Part I: Foundations'', in Proceedings of the 5th Conference on Theoretical Aspects of Reasoning About Knowledge, 1994, pp. 44-64.
Defining relative likelihood in partially-ordered preferential structures
Joseph Y. Halpern
Starting with a likelihood or preference order on worlds, we extend it to a likelihood ordering on sets of worlds in a natural way, and examine the resulting logic. Lewis earlier considered such a notion of relative likelihood in the context of studying counterfactuals, but he assumed a total preference order on worlds. Complications arise when examining partial orders that are not present for total orders. There are subtleties involving the exact approach to lifting the order on worlds to an order on sets of worlds. In addition, the axiomatization of the logic of relative likelihood in the case of partial orders gives insight into the connection between relative likelihood and default reasoning.
In Journal of AI Research 7, 1997, pp. 1-24. A preliminary version appears in Proceedings of the Twelfth Conference on Uncertainty in AI, 1996, pp. 299-306. The paper is available available at CoRR and locally in postscript and pdf.
Plausibility measures and default reasoning
Nir Friedman and Joseph Y. Halpern
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, belief functions, and possibility measures. We focus on one application of plausibility measures in this paper: default reasoning. In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, epsilon-semantics, possibilistic structures, and kappa-rankings, that have been shown to be characterized by the same set of axioms, known as the KLM properties. While this was viewed as a surprise, we show here that it is almost inevitable. In the framework of plausibility measures, we can give a necessary condition for the KLM axioms to be sound, and an additional condition necessary and sufficient to ensure that the KLM axioms are complete. This additional condition is so weak that it is almost always met whenever the axioms are sound. In particular, it is easily seen to hold for all the proposals made in the literature.
In Journal of the ACM 48:4, 2001, pp. 648-685. A version of the paper similar to the published version is available at CoRR and locally in postscript and pdf. A preliminary version appears in AAAI-96 (Proceedings of the Thirteenth National Conference on Artificial Intelligence), 1996, pp. 1297-1304.
On the knowledge requirements of tasks
Ronen I. Brafman, Joseph Y. Halpern, and Yoav Shoham
In order to successfully perform a task, a situated system requires some information about its domain. If we can understand what information the system requires, we may be able to equip it with more suitable sensors or make better use of the information available to it. These considerations have motivated roboticists to examine the issue of sensor design, and in particular, the minimal information required to perform a task. We show here that reasoning in terms of what the robot knows and needs to know to perform a task is a useful approach for analyzing these issues. We extend the formal framework for reasoning about knowledge, already used in AI and distributed computing, by developing a set of concepts basic and tools for modeling and analyzing the knowledge requirements of tasks. We investigate properties of the resulting framework, and show how it can be applied to robotics tasks.
In Artificial Intelligence, 98:1-2, 1998, pp. 317-349. A version of the paper similar to the published version is available in postscript and pdf.
A counterexample to theorems of Cox and Fine
Joseph Y. Halpern
Cox's well-known theorem justifying the use of probability is shown not to hold in finite domains. The counterexample also suggests that Cox's assumptions are insufficient to prove the result even in infinite domains. The same counterexample is used to disprove a result of Fine on comparative conditional probability.
In Journal of AI Research, 10, 1999, pp. 67-85. A preliminary version appears in AAAI-96 (Proceedings of the Thirteenth National Conference on Artificial Intelligence), 1996, pp. 1313-1319. The paper is available in postscript and pdf. Further discussion of Cox's Theorem can be found in Cox's Theorem revisited.
The hierarchical approach to modeling knowledge and common knowledge
Ronald Fagin, Joseph Y. Halpern, J. Geanakoplos, and Moshe Y. Vardi
One approach to representing knowledge or belief of agents, which has been explored independently by economists (Boge and Eisele; Mertens and Zamir; Brandenburger and Dekel; Tan and Werlang) and by computer scientists (Fagin, Halpern, and Vardi) involves an infinite hierarchy of beliefs. Such a hierarchy consists of an agent's beliefs about the state of the world, his beliefs about other agents' beliefs about the worlds, his beliefs about other agents' beliefs about other agents' beliefs about the worlds, etc. Economists and computer scientists differ, however, in the way they model beliefs. Economists prefer a probability-based framework, where belief is modeled as a probability distribution on the uncertainty space. In contrast, computer scientists prefer an information-based framework, where belief is modeled as a subset of the underlying space. The idea is that whatever is in the subset is believed to be possible, and whatever is not in the subset is believed to be impossible. We consider the question of when such an infinite hierarchy completely describes the uncertainty of the agents. We provide various necessary and sufficient conditions for this property. It turns out that the probability-based approach can be viewed as satisfying one of these conditions, which explains why the infinite hierarchy always completely describes the uncertainty of the agents in the probability-based approach. An interesting consequence of our conditions is that adequacy of an infinite hierarchy may depend on the ``richness'' of the states in the underlying state space. We also consider the question of whether an infinite hierarchy completely describes the uncertainty of the agents with respect to ``interesting'' sets of events and show that the answers depends on the definition of ``interesting''.
International Journal of Game Theory 28:3, 1999, pp. 331-365. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version with the title ``The expressive power of the hierarchical approach to modeling knowledge and common knowledge'' appears in Proceedings of the 4th Conference on Theoretical Aspects of Reasoning About Knowledge, 1992, pp. 229-244
Hypothetical knowledge and counterfactual reasoning
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 perfect information. He argued that while hypothetical knowledge and the extended information structures used to model it bear some resemblance to the way philosophers have used conditional logic to model counterfactuals, hypothetical knowledge cannot be reduced to conditional logic together with epistemic logic. Here it is shown that in fact hypothetical knowledge can be captured using the standard counterfactual operator and knowledge operator, provided that some assumptions are made regarding the interaction between the two. It is argued, however, that these assumptions are unreasonable in general, as are the axioms that follow from them. Some implications for game theory are discussed.
In International Journal of Game Theory 28:3, 1999, pp. 331--365. A version of the paper similar to the published version is available in postscript and pdf. A preliminary version appears in Proceedings of the Seventh Conference on Theoretical Aspects of Rationality and Knowledge, 1998, pp. 83-96.
Modeling belief in dynamic systems. Part II: Revision and update
Nir Friedman and Joseph Y. Halpern
The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper we introduced a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the changes of beliefs over time. In this paper we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method and to better understand the principles underlying them. In particular, it allows us to understand the source of Gardenfors' triviality result for belief revision and suggests a way of mitigating the problem. It also shows that Katsuno and Mendelzon's notion of belief update depends on several strong assumptions that may limit its applicability in AI.
Journal of AI Research 10, 1999, pp. 117-167. A preliminary version, with the title ``A knowledge-based framework for belief change. Part II: Revision and Update'' appears in Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning, 1994, pp. 190-201. The full paper is available at CoRR and locally in postscript and pdf.
Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi
We consider the common-knowledge paradox raised in Knowledge and common knowledge in a distributed environment common knowledge is necessary for coordination, but common knowledge is unattainable in the real world because of temporal imprecision. We discuss two solutions to this paradox: (1) modeling the world with a coarser granularity, and (2) relaxing the requirements for coordination.
In Annals of Pure and Applied Logic 96, 1999, pp. 89-105. A preliminary version appears in Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge, 1996, pp. 283-298. This material is largely taken from Chapter 11 of our book. The paper is available available at CoRR and locally in postscript and pdf.
Nir Friedman and Joseph Y. HalpernWe 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 carefully, we must be quite explicit about the ``ontology'' or scenario underlying the belief change process. This is something that has been missing in previous work, with its focus on postulates. Our analysis shows that we must pay particular attention to two issues that have often been taken for granted: The first is how we model the agent's epistemic state. (Do we use a set of beliefs, or a richer structure, such as an ordering on worlds? And if we use a set of beliefs, in what language are these beliefs are expressed?) We show that even postulates that have been called ``beyond controversy'' are unreasonable when the agent's beliefs include beliefs about her own epistemic state as well as the external world. The second is the status of observations. (Are observations known to be true, or just believed? In the latter case, how firm is the belief?) Issues regarding the status of observations arise particularly when we consider iterated belief revision, and we must confront the possibility of revising by p and then by p.
In Journal of Logic, Language, and Information 8, 1999, pp. 401-420. A preliminary version appeared in Proceedings of the Fifth Internal Conference on Principles of Knowledge Representation and Reasoning (KR '96), 1996, pp. 421-431. The paper is available at CoRR and locally in postscript and pdf.
Joseph Y. Halpern
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, arguably, not natural. This paper provides further discussion of the issues raised in A counterexample to theorems of Cox and Fine.
In Journal of AI Research 11, 1999, pp. 429-435. This is really a short note expanding on the issues raised in A counterexample to theorems of Cox and Fine. The paper is available in available at CoRR and locally postscript and pdf.
Set-theoretic completeness for epistemic and conditional logic
Joseph Y. Halpern
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 together with an interpretation of formulas in the language (the semantics), a collection of axioms and rules of inference characterizing reasoning (the proof theory), and then relate the proof theory to the semantics via soundness and completeness results. Here we consider an approach that is more common in the economics literature, which works purely at the semantic, set-theoretic level. We provide set-theoretic completeness results for a number of epistemic and conditional logics, and contrast the expressive power of the syntactic and set-theoretic approaches.
In Annals of Mathematics and Artificial Intelligence 26, 1999, pp. 1-27. A preliminary version appears in Proceedings of the Fifth International Symposium on Artificial Intelligence and Mathematics, 1998. The paper is available available at CoRR and locally in postscript and pdf.
Reasoning about noisy sensors in the situation calculus
Fahiem Bacchus, Joseph Y. Halpern, and 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. Unfortunately, sensor information is inherently noisy, and in general serves only to increase the agent's degree of confidence in various propositions. Building on a general logical theory of action formalized in the situation calculus developed by Reiter and others, we propose a simple axiomatization of the effect on an agent's state of belief of taking a reading from a noisy sensor. By exploiting Reiter's solution to the frame problem, we automatically obtain that these sensor actions leave the rest of the world unaffected, and further, that non-sensor actions change the state of belief of the agent in appropriate ways.
In Artificial Intelligence, 1999, pp. 131-169. A previous version appears in Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI 95), 1995, pp. 1933-1940. Available available at CoRR and locally in postscript and pdf.
On the adequacy of modal logic
Joseph Y. Halpern
McCarthy has argued that modal logic is too limited for various purposes. I consider the extent to which he is right.
In Electronic News Journal on Reasoning about Action and Change 3, July 1999. Available here.
A note on knowledge-based programs and specifications
Joseph Y. Halpern
We view a knowledge-based protocol as specifying a set of systems (where a system is a set of runs), in contrast to a standard protocol, which specifies a set of runs. This point of view helps clarify the relationship between standard and knowledge-based protocols. It also leads naturally to a useful notion of knowledge-based specification, a specification that, like a knowledge-based protocol, can be identified with a set of systems.
In Distributed Computing 13:3, 2000, pp. 145-153. The paper is available at CoRR and locally in postscript and pdf.
A logic for SDSI's linked local named spaces
Joseph Y. Halpern and Ronald van der Meyden
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 precisely to SDSI, however; it draws conclusions about local names that do not follow from SDSI's name resolution algorithm. Moreover, its semantics is somewhat unintuitive. This paper presents the Logic of Local Name Containment, which does not suffer from these deficiencies. It has a clear semantics and provides a tight characterization of SDSI name resolution. The semantics is shown to be closely related to that of logic programs, leading to an approach to the efficient implementation of queries concerning local names. A complete axiomatization of the logic is also provided.
In Journal of Computer Security 9:1,2, 2001, pp. 47-74. A preliminary version appears in Proceedings of the 12th IEEE Computer Security Foundations Workshop, 1999, pp. 111-122. The paper is at CoRR and locally in postscript and pdf.
CoRR: A Computing Research Repository (with commentary)
Joseph Y. Halpern
I describe how CoRR was set up and discuss some policy issues.
In ACM Journal of Computer Documentation, 24:2, 2000, pp. 41-48. There were also commentators who wrote a response to the article; my response to the commentators is on pp. 72-77. This article is based on (and borrows liberally from) two earlier articles: A Computing Research Repository, D-Lib Magazine, November 1998 and The Computing Research Repository: Promoting the Rapid Dissemination of Computer Science Research. The paper is available on CoRR (of course) and locally in postscript and pdf. My response to the commentators (which is fairly self-contained) is available in postscript and pdf.
Substantive rationality and backward induction
Joseph Y. Halpern
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 player is substantively rational if, for all vertices v, if the player were to reach vertex v, then the player would be rational at vertex v. It is shown here that the key difference between Aumann and Stalnaker lies in how they interpret this counterfactual. A formal model is presented that lets us capture this difference, in which both Aumann's result and Stalnaker's result are true (under appropriate assumptions).
In Games and Economic Behavior 37, 2001, pp. 425-435. The paper is available in postscript and pdf.
Alternative semantics for unawareness
Joseph Y. Halpern
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 nontrivial unawareness was incompatible with partitional information structures. More recently, Modica and Rustichini [1999] have provided an approach that allows for nontrivial unawareness in partitional information structures. Here it is shown that their approach can be viewed as a special case of a general approach to unawareness considered in Belief, awareness, and limited reasoning.
In Games and Economic Behavior 37, 2001, pp. 321-339. The paper is available in postscript and pdf.
Joseph Y. Halpern
Causal models defined in terms of a collection of equations, as defined by Pearl, are axiomatized here. Axiomatizations are provided for three successively more general classes of causal models: (1) the class of recursive theories (those without feedback), (2) the class of theories where the solutions to the equations are unique, (3) arbitrary theories (where the equations may not have solutions and, if they do, they are not necessarily unique). It is shown that to reason about causality in the most general third class, we must extend the language used by Galles and Pearl. In addition, the complexity of the decision procedures is examined for all the languages and classes of models considered.
In Journal of AI Research 12, 2000, pp. 317-337. A preliminary version appears in Proceedings of the Fourteenth Conference on Uncertainty in AI, 1998, pp. 202-210. The paper is available at CoRR and locally in postscript and pdf.
First-order conditional logic for default reasoning revisited
Nir Friedman, Joseph Y. Halpern, and Daphne KollerConditional logics play an important role in recent attempts to investigate default reasoning. This paper investigates first-order conditional logic. We show that, as for first-order probabilistic logic, it is important not to confound statistical conditionals over the domain (such as ``most birds fly''), and subjective conditionals over possible worlds (such as ``I believe that Tweety is unlikely to fly''). We then address the issue of ascribing semantics to first-order conditional logic. As in the propositional case, there are many possible semantics. To study the problem in a coherent way, we use plausibility structures. These provide us with a general framework in which many of the standard approaches can be embedded. We show that while these standard approaches are all the same at the propositional level, they are significantly different in the context of a first-order language. We show that plausibilities provide the most natural extension of conditional logic to the first-order case: We provide a sound and complete axiomatization that contains only the KLM properties and standard axioms of first-order modal logic. We show that most of the other approaches have additional properties, which result in an inappropriate treatment of an infinitary version of the lottery paradox.
In ACM Transactions on Computational Logic 1:2, 2000, pp. 175-207. A preliminary version, with the title "First-order conditional logic revisited" appears in AAAI-96 (Proceedings of the Thirteenth National Conference on Artificial Intelligence), 1996, pp. 1305-1312. The full paper is available available at CoRR and locally in postscript and pdf.
A decision-theoretic approach to reliable message delivery
Francis C. Chu and Joseph Y. Halpern
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 communication, showing how considerations of utility and probability can be used to decide when it is worth sending heartbeat messages and, if they are sent, how often they should be sent.
In Distributed Computing 14, 2001, pp. 1-16. A preliminary version appears in Proceedings of the 12th International Symposium on Distributed Computing, 1998, pp. 89-103. The full paper is available at CoRR and locally in postscript and pdf.
Joseph Y. Halpern and Gerhard Lakemeyer
Levesque introduced a notion of ``only knowing'', with the goal of capturing certain types of nonmonotonic reasoning. Levesque's logic dealt with only the case of a single agent. Recently, both Halpern and Lakemeyer independently attempted to extend Levesque's logic to the multi-agent case. Although there are a number of similarities in their approaches, there are some significant differences. In this paper, we reexamine the notion of only knowing, going back to first principles. In the process, we simplify Levesque's completeness proof, and point out some problems with the earlier definitions. This leads us to reconsider what the properties of only knowing ought to be. We provide an axiom system that captures our desiderata, and show that it has a semantics that corresponds to it. The axiom system has an added feature of interest: it includes a modal operator for satisfiability, and thus provides a complete axiomatization for satisfiability in the logic K45.
In Journal of Logic and Computation 11:1, 2001, pp. 41-70. A preliminary version appears in Proceedings of the Sixth Conference on Theoretical Aspects of Rationality and Knowledge, 1996, pp. 251-266. The paper is available CoRR and locally in postscript and pdf.
Conditional plausibility measures and Bayesian networks
Joseph Y. Halpern
A general notion of algebraic conditional plausibility measures is defined. Probability measures, ranking functions, possibility measures, and (under the appropriate definitions) sets of probability measures can all be viewed as defining algebraic conditional plausibility measures. It is shown that the technology of Bayesian networks can be applied to algebraic conditional plausibility measures.
In Journal of AI Research 14, 2001, pp. 359-389. A preliminary version appears in Proceedings of the Sixteenth Conference on Uncertainty in AI, 2000, pp. 247-255. The full paper is available at CoRR and locally in postscript and pdf.
On the NP-completeness of finding an optimal strategy in games with common payoffs
Francis C. Chu and Joseph Y. Halpern
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 least k is NP-complete.
In International Journal of Game Theory 30:1, 2001, pp. 99-106. The paper is available at CoRR and locally in postscript and pdf.
A characterization of eventual Byzantine agreement
Joseph Y. Halpern, Yoram Moses, and Orli Waarts
We investigate eventual Byzantine agreement (EBA) in the crash and omission failure models. The emphasis is on characterizing optimal EBA protocols in terms of the states of knowledge required by the processors in order to attain EBA. It is well known that common knowledge among the nonfaulty processors is a necessary and sufficient condition for attaining simultaneous Byzantine agreement (SBA). We define a new variant that we call continual common knowledge, and use it to provide necessary and sufficient conditions for attaining EBA. Using our characterization, we provide a technique that allows us to start with any EBA protocol and convert it to an optimal EBA protocol using a two-step process.
In SIAM Journal on Computing 31:3, 2001, pp. 838-865. A preliminary version appears in Proceedings of the 9th ACM Symposium on Principles of Distributed Computing, 1990, pp. 333-346. A version of the paper similar to the published version is available in postscript and pdf.
Characterizing the common prior assumption
Joseph Y. Halpern
Logical characterizations of the common prior assumption (CPA) are investigated. Two approaches are considered. The first is called frame distinguishability, and is similar in spirit to the approaches considered in the economics literature. Results similar to those obtained in the economics literature are proved here as well, namely, that we can distinguish finite spaces that satisfy the CPA from those that do not in terms of disagreements in expectation. However, it is shown that, for the language used here, no formulas can distinguish infinite spaces satisfying the CPA from those that do not. The second approached considered is that of finding a sound and complete axiomatization. Such an axiomatization is provided; again, the key axiom involves disagreements in expectation. The same axiom system is shown to be sound and complete both in the finite and the infinite case. Thus, the two approaches to characterizing the CPA behave quite differently in the case of infinite spaces.
In Journal of Economic Theory 106:2, 2002, pp. 316-355. A preliminary version appears in Proceedings of the Seventh Conference on Theoretical Aspects of Rationality and Knowledge, 1998, pp. 133-146. The paper is available in postscript and pdf.
Using counterfactuals in knowledge-based programming
Joseph Y. Halpern and Yoram Moses
We show how counterfactuals can be added to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi. We show that counterfactuals allow us to capture in a natural way notions like minimizing the number of messages that are sent, whereas attempts to formalize these notions without counterfactuals lead to some rather counterintuitive behavior. We also show how knowledge-based programs with counterfactuals can capture subgame-perfect equilibria in games of perfect information.
In Distributed Computing
A knowledge-theoretic analysis of uniform distributed coordination and failure detectors
Joseph Y. Halpern and Aleta Ricciardi
It is shown that if there is no bound on the number of faulty processes, then that, in a precise sense, in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes' knowledge as to which other processes are faulty plays a key role in the analysis.
In Distributed Computing
On the expressive power of nondeterminism in dynamic logic
Piotr Berman, Joseph Y. Halpern, and Jerzy Tiuryn
We show that nondeterministic first-order regular dynamic logic is strictly more powerful than its deterministic counterpart, thus settling a long-standing open question.
In Proceedings of the 9th International Colloquium on Automata, Languages, and Programming, 1982, pp. 48-60.
From denotational to operational and axiomatic semantics for Algol-like languages: an overview
Boris A. Trakhtenbrot, Joseph Y. Halpern, and Albert R. Meyer
The advantages of denotational over operational semantics are argued. A denotational semantics is provided for an ALGOL-like language with finite-mode procedures, blocks with local storage, and sharing (aliasing). Procedure declarations are completely explained in the usual framework of complete partial orders, but cpo's are inadequate for the semantic of blocks, and a new class of store models is developed. Partial correctness theory over store models is developed for commands which may contain calls to global procedures, but do not contain function procedures returning storable values.
In Proceedings of CMU Logics of Programs Conference, Lecture Notes in Computer Science, 1983, pp. 474-500 The paper is available in pdf.
A hardware semantics based on temporal intervals
Joseph Y. Halpern, Benjamin Moszkowski, and Zohar Manna
We present an interval-based logic that permits the rigorous specification of a variety of hardware components and facilitates describing properties such as correctness of implementation. Conceptual levels of circuit operation ranging from detailed quantitative timing and signal propagation up to functional behavior are integrated in a unified way. After giving some motivation for reasoning about hardware, we present the propositional and first-order syntax and semantics of the temporal logic. In addition, we illustrate techniques for describing signal transitions as well as for formally specifying and comparing a number of delay models. Throughout the discussion, the formalism provides a means for examining such concepts as device equivalence and internal states.
In Proceedings of the 10th International Colloquium on Automata, Languages, and Programming, 1983, pp. 278-291.
The semantics of local storage, or What makes the free-list free
Joseph Y. Halpern, Albert R. Meyer, and Boris A. Trakhtenbrot
Denotational semantics for an ALGOL-like language with finite-mode procedures, blocks with local storage, and sharing (aliasing) is given by translating programs into an appropriately typed lambda-calculus. Procedures are entirely explained at a purely functional level -- independent of the interpretation of program constructs -- by continuous models for lambda-calculus. However, the usual (cpo) models are note adequate to model storage allocation for blocks because storage overflow presents an apparent discontinuity. New domains of store models are offered to solve this problem.
In Proceedings of the 11th Annual ACM Symposium on the Principles of Programming Languages, 1984, pp. 245-257.
A good Hoare axiom system for an Algol-like language
Joseph Y. Halpern
Clarke [1979] has shown that it is impossible to obtain a relatively complete axiomatization of a block-structured programming language if it has features such as static scope, recursive procedure calls with procedure parameters, and global variables, provided we take first-order logic as the underlying assertion language. We show that if we take a more powerful assertion language, and hence a more powerful notion of expressiveness, such a complete axiomatization is possible. The crucial point is that we need to be able to express the weakest precondition of commands with free procedure parameters. The axioms presented here are natural and reflect the syntax of the programming language. Such an axiom system provides a tool for understanding how to reason about languages with powerful control features.
In Proceedings of the 11th Annual ACM Symposium on the Principles of Programming Languages, 1984, pp. 262-271.
Reasoning about knowledge: an overview
Joseph Y. Halpern
This is my first survey on knowledge. It was updated in 1991 and 1995.
In Theoretical Aspects of Reasoning About Knowledge: Proceedings of the 1986 Conference, Morgan Kaufmann, 1986, pp. 1-17; reprinted in Proceedings of the National Computer Conference, 1986, pp. 219-228.
A knowledge-based analysis of zero knowledge
Joseph Y. Halpern, Yoram Moses, and Mark Tuttle
While the intuition underlying a zero knowledge proof system is that no ``knowledge'' is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined by Tompa and Woll [1987] and Fiat, Feige, and Shamir [1987] are instances of weak interactive proofs.
In Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 132-147. A version of the paper similar to the published version is available in postscript and pdf.
Reasoning about knowledge and time in asynchronous systems
Joseph Y. Halpern and Moshe Y. Vardi
In Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 53-65.
Knowledge and probability in distributed systems (Abstract)
Joseph Y. Halpern
This is an abstract for an invited talk; it's a brief summary of material in ``Knowledge, probability, and adversaries''.
In TAPSOFT '91, Proceedings of the International Joint Conference on Theory and Practice of Software Development (S. Abramsky and T. S. E. Maibaum, eds.), Volume 2, 1991, pp. 50-54.
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and 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 three are applications of the principle of indifference, because they assign equal degree of belief to all basic ``situations'' consistent with the knowledge base. They differ because there are competing intuitions about what the basic situations are. Various natural patterns of reasoning, such as the preference for the most specific statistical data available, turn out to follow from some or all of the techniques. This is an improvement over earlier theories, such as work on direct inference and reference classes, which arbitrarily postulate these patterns without offering any deeper explanations or guarantees of consistency. The three methods we investigate have surprising characterizations: there are connections to the principle of maximum entropy, a principle of maximal independence, and a ``center of mass'' principle. There are also unexpected connections between the three, that help us understand why the specific language chosen (for the knowledge base) is much more critical in inductive reasoning of the sort we consider than it is in traditional deductive reasoning.
In Proceedings of AAAI-92 (Proceedings of the Tenth National Conference on Artificial Intelligence, 1992, pp. 602-608 A version of the paper similar to the published version is available in postscript and pdf.
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
This is a preliminary version of work that appears in ``Statistical foundations for default reasoning''. In Proceedings of the Fourth International Workshop on Nonmonotonic Reasoning 1992.
A logic for approximate reasoning
Daphne Koller and 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 base with imprecise information: a cautious notion, which allows only completely justified conclusions, and a bold one, which allows jumping to conclusions. Both versions of the entailment relation are shown to be decidable. We investigate the behavior of the two alternatives on various examples, and show that the answers obtained are intuitively desirable. The behavior of these two entailment relations is completely characterized for a certain sublanguage, in terms of the logic of true equality. We demonstrate various properties of the full logic, and show how it applies to many situations of interest.
In Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, 1992, pp. 153-164. A version of the paper similar to the published version is available in postscript and pdf.
Statistical foundations for default reasoning
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and 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 base KB comprised of statistical and first-order statements. We then assign equal probability to all worlds consistent with KB in order to assign a degree of belief to a statement p. The degree of belief can be used to decide whether to defeasibly conclude p. Various natural patterns of reasoning, such as a preference for more specific defaults, indifference to irrelevant information, and the ability to combine independent pieces of evidence, turn out to follow naturally from this technique. Furthermore, our approach is not restricted to default reasoning; it supports a spectrum of reasoning, from quantitative to qualitative. It is also related to other systems for default reasoning. In particular, we show that the work of Goldszmidt, Morris, and Pearl, which applies maximum entropy ideas to epsilon-semantics, can be embedded in our framework.
In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI 93), 1993, pp. 563-569. More details on these and related results can be found in ``From statistical knowledge bases to degrees of belief''.
Reasoning about only knowing with many agents
Joseph Y. Halpern
We extend two notions of ``only knowing'', that of Halpern and Moses and that of Levesque, to many agents. The main lesson of this paper is that these approaches do have reasonable extensions to the multi-agent case. Our results also shed light on the single-agent case. For example, it was always viewed as significant that the HM notion of only knowing was based on S5, while Levesque's was based on K45. In fact, our results show that the HM notion is better understood in the context of K45. Indeed, in the single-agent case, the HM notion remains unchanged if we use K45 (or KD45) instead of S5. However, in the multi-agent case, there are significant differences between K45 and S5. Moreover, all the results proved by Halpern and Moses for the single-agent case extend naturally to the multi-agent case for K45, but not for S5.
In AAAI-93 (Proceedings of the Eleventh National Conference on Artificial Intelligence, 1993, pp. 655-661. A more thorough discussion of the multi-agent version of the HM notion of only knowing appears in ``A theory of knowledge and ignorance for many agents''. ``Multi-agent only knowing'' (joint with Gerhard Lakemeyer) discusses the multi-agent version of Levesque's notion in more detail.
Generating degrees of belief from statistical information: an overview
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
This is an abridged version of material in ``From statistical knowledge bases to degrees of belief''.
In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 761, Springer, 1993, pp. 318-325.
Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi
The standard model of knowledge in multi-agent systems suffers from what has been called the logical omniscience problem: agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this turns out not to be a problem. Knowledge is viewed as being ascribed by the system designer to the agents; agents are not assumed to compute their knowledge in any way, nor is it assumed that they can necessarily answer questions based on their knowledge. Nevertheless, in many applications that we are interested in, agents need to act on their knowledge. In such applications, an externally ascribed notion of knowledge is insufficient: clearly an agent can base his actions only on what he explicitly knows. Furthermore, an agent that has to act on his knowledge has to be able to compute this knowledge; we do need to take into account the algorithms available to the agent, as well as the ``effort'' required to compute knowledge. In this paper, we show how the standard model can be modified in a natural way to take the computational aspects of knowledge into account.
In Proceedings of the 5th Conference on Theoretical Aspects of Reasoning About Knowledge, 1994, pp. 255-266. The paper in postscript and pdf. Most of the material here is taken from Chapter 10 of our book.
A knowledge-based framework for belief change, Part I: Foundations
Nir Friedman and Joseph Y. Halpern
We propose a general framework in which to study belief change. We begin by defining belief in terms of knowledge and plausibility: an agent believes p if he knows that p is true in all the worlds he considers most plausible. We then consider some properties defining the interaction between knowledge and plausibility, and show how these properties affect the properties of belief. In particular, we show that by assuming two of the most natural properties, belief becomes a KD45 operator. Finally, we add time to the picture. This gives us a framework in which we can talk about knowledge, plausibility (and hence belief), and time, which extends the framework of Halpern and Fagin for modeling knowledge in multi-agent systems. (See ``Modelling knowledge and action in distributed systems''.) We show that our framework is quite expressive and lets us model in a natural way a number of different scenarios for belief change. For example, we show how we can capture an analogue to prior probabilities, which can be updated by ``conditioning''. In a related paper, we show how the two best studied scenarios, belief revision and belief update, fit into the framework.
In Proceedings of the 5th Conference on Theoretical Aspects of Reasoning About Knowledge, 1994, pp. 44-64. The full version of the paper is Modeling belief in dynamic systems, Part I: Foundations''.
A knowledge-based framework for belief change, Part II: Revision and update
Nir Friedman and Joseph Y. Halpern
The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. In a companion paper we introduced a new framework to model belief change. This framework combines temporal and epistemic modalities with a notion of plausibility, allowing us to examine the changes of beliefs over time. In this paper we show how belief revision and belief update can be captured in our framework. This allows us to compare the assumptions made by each method and to better understand the principles underlying them. In particular, it allows us to understand the source of Gardenfors' triviality result for belief revision and suggests a way of mitigating the problem. It also shows that Katsuno and Mendelzon's notion of belief update depends on several strong assumptions that may limit its applicability in AI.
In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning, 1994, pp. 190-201. The full paper, Modeling belief in dynamic systems, Part II: Revision and Update, is available in postscript and pdf. It appears in Journal of AI Research 10, 1999, pp. 117-167.
On the complexity of conditional logics
Nir Friedman and Joseph Y. Halpern
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 discussed in the literature. We show that, in general, deciding satisfiability is PSPACE-complete for formulas with arbitrary conditional nesting and NP-complete for formulas with bounded nesting of conditionals. However, we provide several exceptions to this rule. Of particular note are results showing that (a) when assuming uniformity (i.e., that all worlds agree on what worlds are possible), the decision problem becomes EXPTIME-complete even for formulas with bounded nesting, and (b) when assuming absoluteness (i.e., that all worlds agree on all conditional statements), the decision problem is NP-complete for formulas with arbitrary nesting.
In Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning, 1994, pp. 202-213. The paper is available in postscript and pdf.
Conditional logics of belief change
Nir Friedman and Joseph Y. Halpern
The study of belief change has been an active area in philosophy and AI. In recent years two special cases of belief change, belief revision and belief update, have been studied in detail. Belief revision and update are clearly not the only possible notions of belief change. In this paper we investigate properties of a range of possible belief change operations. We start with an abstract notion of a belief change system and provide a logical language that describes belief change in such systems. We then consider several reasonable properties one can impose on such systems and characterize them axiomatically. We show that both belief revision and update fit into our classification. As a consequence, we get both a semantic and an axiomatic (proof-theoretic) characterization of belief revision and update (as well as some belief change operations that generalize them), in one natural framework.
In AAAI-94 (Proceedings of the Twelfth National Conference on Artificial Intelligence), 1994, pp. 915-921. The paper is available in postscript and pdf.
An operational semantics for knowledge bases
Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi
The standard approach in AI 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 said to know a fact if it is provable from the formulas in his knowledge base. Halpern and Vardi advocated a model-theoretic approach to knowledge representation. In this approach, the key step is representing the agent's knowledge using an appropriate semantic model. Here, we model knowledge bases operationally as multi-agent systems. Our results show that this approach offers significant advantages.
In AAAI-94 (Proceedings of the Twelfth National Conference on Artificial Intelligence), pp. 1142-1147, 1994. This material is largely taken from Chapter 4 of our book. The paper is available in postscript and pdf.
Forming beliefs about a changing world
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and 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 contexts. In particular, we often face uncertainty, due either to lack of knowledge or to some probabilistic aspects of the world. While attempts have been made to address aspects of this problem, most notably using nonmonotonic reasoning formalisms, the general problem of uncertainty in reasoning about action has not been fully dealt with in a logical framework. In this paper we present a theory of action that extends the situation calculus to deal with uncertainty. Our framework is based on applying the random-worlds approach of ``From statistical knowledge bases to degrees of belief'' to a situation calculus ontology, enriched to allow the expression of probabilistic action effects. Our approach is able to solve many of the problems imposed by incomplete and probabilistic knowledge within a unified framework. In particular, we obtain a default Markov property for chains of actions, a derivation of conditional independence from irrelevance, and a simple solution to the frame problem.
In AAAI-94 (Proceedings of the Twelfth National Conference on Artificial Intelligence), 1994, pp. 222-229. The paper is available in postscript and pdf.
Generating new beliefs from old
Fahiem Bacchus, Adam J.Grove, Joseph Y. Halpern, and Daphne Koller
In ``From statistical knowledge bases to degrees of belief'' we studied the random-worlds approach---a particular (and quite powerful) method for generating degrees of belief (i.e., subjective probabilities) from a knowledge base consisting of objective (first-order, statistical, and default) information. But allowing a knowledge base to contain only objective information is sometimes limiting. We occasionally wish to include information about degrees of belief in the knowledge base as well, because there are contexts in which old beliefs represent important information that should influence new beliefs. In this paper, we describe three quite general techniques for extending a method that generates degrees of belief from objective information to one that can make use of degrees of belief as well. All of our techniques are based on well-known approaches, such as cross-entropy. We discuss general connections between the techniques and in particular show that, although conceptually and technically quite different, all of the techniques give the same answer when applied to the random-worlds method.
In Proceedings of the Tenth Conference on Uncertainty in AI, 1994, pp. 37-45. The paper is available at CoRR and locally in postscript and pdf.
Representation dependence in probabilistic inference
Joseph Y. Halpern and Daphne Koller
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 viewed as a significant problem. For example, the principle of maximum entropy has been subjected to much criticism due to its representation dependence. There has, however, been almost no work investigating representation dependence. In this paper, we formalize this notion and show that it is not a problem specific to maximum entropy. In fact, we show that any probabilistic inference system that sanctions certain important patterns of reasoning, such as a minimal default assumption of independence, must suffer from representation dependence. We then show that invariance under a restricted class of representation changes can form a reasonable compromise between representation independence and other desiderata.
In Journal of AI Research
Plausibility measures: a user's manual
Nir Friedman and Joseph Y. Halpern
We examine a new approach to modeling uncertainty based on plausibility measures, where a plausibility measure just associates with an event its plausibility, an element is some partially ordered set. This approach is easily seen to generalize other approaches to modeling uncertainty, such as probability measures, belief functions, and possibility measures. The lack of structure in a plausibility measure makes it easy for us to add structure on an ``as needed'' basis, letting us examine what is required to ensure that a plausibility measure has certain properties of interest. This gives us insight into the essential features of the properties in question, while allowing us to prove general results that apply to many approaches to reasoning about uncertainty. Plausibility measures have already proved useful in analyzing default reasoning. In this paper, we examine their ``algebraic properties'', analogues to the use of + and x in probability theory. An understanding of such properties will be essential if plausibility measures are to be used in practice as a representation tool.
In Proceedings of the Eleventh Conference on Uncertainty in AI, 1995, pp. 175-184. The paper is available in postscript and pdf.
Irrelevance and conditioning in first-order probabilistic logic
Daphne Koller and 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 patterns of reasoning, such as indifference to irrelevant information or substitution of constants into universal rules. We show that both these patterns rely on a first-order version of probabilistic independence, and provide semantic conditions to capture them. The resulting insight enables us to understand the effect of conditioning on independence, and allows us to describe a procedure for determining when independencies are preserved under conditioning. We apply this procedure in the context of a sound and powerful inference algorithm for reasoning from statistical knowledge bases.
In AAAI-96 (Proceedings of the Thirteenth National Conference on Artificial Intelligence), 1996, pp. 569-576. The paper is available in postscript and pdf.
Using multi-agent systems to represent uncertainty
Joseph Y. Halpern
I consider a logical framework for modeling uncertainty, based on the use of possible worlds, that incorporates knowledge, probability, and time. This turns out to be a powerful approach for modeling many problems of interest. I show how it can be used to give insights into (among other things) several well-known puzzles.
In AAAI-96 (Proceedings of the Thirteenth National Conference on Artificial Intelligence), 1996. pp. 1329-1330. This is just a summary of an invited talk I gave. A slightly longer version appears in SCAI '97 (Proceedings of the Sixth Scandinavian Conference on Artificial Intelligence), 1997, pp. 1-4. The talk was largely based on A logical approach to reasoning about uncertainty: a tutorial.
A qualitative Markov assumption and its implications for belief change
Nir Friedman and Joseph Y. Halpern
The study of belief change has been an active area in philosophy and AI. In recent years, two special cases of belief change, belief revision and belief update, have been studied in detail. Roughly speaking, revision treats a surprising observation as a sign that previous beliefs were wrong, while update treats a surprising observation as an indication that the world has changed. In general, we would expect that an agent making an observation may both want to revise some earlier beliefs and assume that some change has occurred in the world. We define a novel approach to belief change that allows us to do this, by applying ideas from probability theory in a qualitative settings. The key idea is to use a qualitative Markov assumption, which says that state transitions are independent. We show that a recent approach to modeling qualitative uncertainty using plausibility measures allows us to make such a qualitative Markov assumption in a relatively straightforward way, and show how the Markov assumption can be used to provide an attractive belief-change model.
In Proceedings of the Twelfth Conference on Uncertainty in AI, 1996, pp. 263-273. The paper is available in postscript and pdf.
Common knowledge: now you have it, now you don't
Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Y. Vardi
This is a variant of Common knowledge revisited, which in turn is largely taken from Chapter 11 of our book.
In Intelligent Systems: A Semiotics Perspective, Proceedings of the International Multidisciplinary Conference ``Intelligent Systems: A Semiotic Perspective'', Vol.1, 1996, pp. 177-183.
Probability update: conditioning vs. cross-entropy
Adam J. Grove and Joseph Y. Halpern
Conditioning is the generally agreed-upon method for updating probability distributions when one learns that an event is certainly true. But it has been argued that we need other rules, in particular the rule of cross-entropy minimization, to handle updates that involve uncertain information. In this paper we re-examine such a case: van Fraassen's Judy Benjamin problem, which in essence asks how one might update given the value of a conditional probability. We argue that--contrary to the suggestions in the literature--it is possible to use simple conditionalization in this case, and thereby obtain answers that agree fully with intuition. This contrasts with proposals such as cross-entropy, which are easier to apply but can give unsatisfactory answers. Based on the lessons from this example, we speculate on some general philosophical issues concerning probability update.
In Proceedings of the Thirteenth Conference on Uncertainty in AI, 1997, pp. 208-214. Available available at CoRR and locally in postscript and pdf.
Defining explanation in probabilistic systems
Urszula Chajewska and Joseph Y. Halpern
As probabilistic systems gain popularity and are coming into wider use, the need for a mechanism that explains the system's findings and recommendations becomes more critical. The system will also need a mechanism for ordering competing explanations. We examine two representative approaches to explanation in the literature -- one due to Gardenfors and one due to Pearl -- and show that both suffer from significant problems. We propose an approach to defining a notion of ``better explanation'' that combines some of the features of both together with more recent work by Pearl and others on causality.
In Proceedings of the Thirteenth Conference on Uncertainty in AI, 1997, pp. 62-71. The paper is available in postscript and pdf.
Belief revision with unreliable observations
Craig Boutilier, Nir Friedman, and 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'' revision functions. A postulate that is rarely criticized is the success postulate: the result of revising by an observed proposition p results in belief in p. This postulate, however, is often undesirable in settings where an agent's observations may be imprecise or noisy. We propose a semantics that captures a new ontology for studying revision functions, which can handle noisy observations in a natural way while retaining the classical AGM model as a special case. We present a characterization theorem for our semantics, and describe a number of natural special cases that allow ease of specification and reasoning with revision functions. In particular, by making the Markov assumption, we can easily specify and reason about revision.
In AAAI-98 (Proceedings of the Fifteenth National Conference on Artificial Intelligence), 1998. The paper is available in postscript and pdf.
Updating sets of probabilities
Adam J. Grove and Joseph Y. Halpern
There are several well-known justifications for conditioning as the appropriate method for updating a single probability measure, given an observation. However, there is a significant body of work arguing for sets of probability measures, rather than single measures, as a more realistic model of uncertainty. Conditioning still makes sense in this context---we can simply condition each measure in the set individually, then combine the results---and, indeed, it seems to be the preferred updating procedure in the literature. But how justified is conditioning in this richer setting? Here we show, by considering an axiomatic account of conditioning given by van Fraassen, that the single-measure and sets-of-measures cases are very different. We show that van Fraassen's axiomatization for the former case is nowhere near sufficient for updating sets of measures. We give a considerably longer (and not as compelling) list of axioms that together force conditioning in this setting, and describe other update methods that are allowed once any of these axioms is dropped.
In Proceedings of the Fourteenth Conference on Uncertainty in AI, 1998, pp. 173-182. Available at HREF="http://arxiv.org/abs/0906.4332">CoRR and locally in postscript and pdf.
Sensor-assisted ALOHA for wireless networks
L. Terrence Fine, Stephen B. Wicker, Toby Berger, and Joseph Y. Halpern
In Proceedings of the 1998 International Symposium on Information Theory, 1998.
Sensor-assisted multiple-access protocols for wireless networks
L. Terrence Fine, Stephen B. Wicker, Toby Berger, and Joseph Y. Halpern
In Proceedings of the 1998 International Conference on Universal Personal Communications, 1998.
Least expected cost query optimization: an exercise in utility
Francis C. Chu, Joseph Y. Halpern and 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 to optimize for the expected case---that is, the case where various parameters (like available memory) take on their expected value. The other assumption is that the parameters are constant throughout the execution of the query. We present an algorithm based on the ``System R''-style query optimization algorithm that does not rely on these assumptions. The algorithm we present chooses the plan of the least expected cost instead of the plan of least cost given some fixed value of the parameters. In execution environments that exhibit a high degree of variability, our techniques should result in better performance.
In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Database Systems , 1999. The paper is available available at CoRR and locally in postscript and pdf.
Reasoning about common knowledge with infinitely many agents
Joseph Y. Halpern and Richard A. Shore
Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents. The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G - G', where G and G' are sets of agents. Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even with the sets of agents involved are finite. Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented.
In Information and Computation
Joseph Y. Halpern and Carl Lagoze
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 the cooperation of ACM, LANL (Los Alamos National Laboratory) e-Print archive, and NCSTRL (Networked Computer Science Technical Reference Library). Through an implementation of the Dienst protocol, CoRR combines the open and extensible architecture of NCSTRL with the reliable access and well-established management practices of the LANL XXX e-Print repository. This architecture will allow integration with other e-Print archives and provides a foundation for a future broad-based scholarly digital library. We describe the decisions that were made in creating CoRR, the architecture of the CoRR/NCSTRL interoperation, and issues that have arisen during the operation of CoRR.
In Proceedings of ACM Digital Libraries '99, 1999, pp. 3-11.
Available at CoRR (naturally!). Some material in the paper is updated in CoRR: A computing research repository.
A decision theoretic-approach to resource allocation in wireless multimedia networks
Zygmunt Haas, Joseph Y. Halpern, Li Li, and Stephen B. Wicker
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 argue that the problem is best formulated in terms of decision theory. We propose a scheme that takes decision-theoretic concerns (like preferences) into account and discuss the difficulties and subtleties involved in applying standard techniques from the theory of Markov Decision Processes (MDPs) in constructing an algorithm that is decision-theoretically optimal. As an example of the proposed framework, we construct such an algorithm under some simplifying assumptions. Additionally, we present analysis and simulation results that show that our algorithm meets its design goals. Finally, we investigate how far from optimal one well-known heuristic is. The main contribution of our results is in providing insight and guidance for the design of near-optimal admission-control policies.
In Resource Allocation in Next Generation Wireless Networks (W. Li and Y. Pan, eds.), Nova Science Publishers, 2005, pp. 1-23. A preliminary version appears in Proceedings of Dial M for Mobility, 2000, pp. 86-95. The full paper is available at CoRR and locally in postscript and pdf.
Minimum-energy topology-control algorithms in ad hoc networks
Li Li and 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 u and v in the subnetwork (where a minimum-energy path is one that allows messages to be transmitted with a minimum use of energy). The network computed by our protocol is in general a subnetwork of the one computed by the protocol given by Rodoplu and Meng [1999]. Moreover, our protocol is computationally simpler. We demonstrate the performance improvements obtained by using the subnetwork computed by our protocol through simulation.
In Handbook of Theoretical and Algorithmic Aspects of Ad Hoc,
Sensor, and Peer-to-Peer Networks, (J. Wu, editor), Auerbach
Publications, 2006, pp. 115-132. This is a slightly version of
``A minimum-energy path-preserving topology-control algorithm'', which
appears in IEEE Transactions on Wireless Communications
A logical reconstruction of SPKI
Joseph Y. Halpern and Ron van der Meyden
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 Local Name Containment that has a clear semantics and was shown to completely characterize SDSI name resolution. Here we show how our earlier approach can be extended to deal with a number of key features of SPKI, including revocation, expiry dates, and tuple reduction, without invoking nonmonotonicity. We show that these extensions add relatively little complexity to the logic. We then use our semantics to examine SPKI's tuple reduction rules. Our analysis highlights places where SPKI's informal description of tuple reduction is somewhat vague, and shows that extra reduction rules are necessary in order to capture general information about binding and authorization.
In Journal of Computer Security 11:4, 2003, pp. 581-614. A preliminary version appears in Proceedings of the 14th IEEE Computer Security Foundations Workshop, 2001, pp. 59-70. The paper is available at CoRR and locally in postscript and pdf. A talk based on the paper is available in postscript and pdf.
A logic for reasoning about upper probabilities
Joseph Y. Halpern and Riccardo Pucella
We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.
In Journal of AI Research 17, pp. 57-81, 2002. A preliminary version appears in Proceedings of the Seventeenth Conference on Uncertainty, pp. 203-210, 2001. The paper is available at CoRR and locally in postscript and pdf.
On the relationship between strand spaces and multi-agent systems
Joseph Y. Halpern and Riccardo Pucella
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 multi-agent systems. We explore the exact relationship between these two frameworks here. It turns out that a key difference is the handling of agents, which are unspecified in strand spaces and explicit in multi-agent systems. We provide a family of translations from strand spaces to multi-agent systems parameterized by the choice of agents in the strand space. We also show that not every multi-agent system of interest can be expressed as a strand space. This reveals a lack of expressiveness in the strand-space framework that can be characterized by our translation. To highlight this lack of expressiveness, we show one simple way in which strand spaces can be extended to model more systems.
In ACM Transactions on Information and System Security 6:1, pp. 43-70, 2003. A preliminary version appears in Proceedings of the Eighth ACM Conference on Computer and Communications Security, 2001, pp. 106-115. The paper is available at CoRR and locally in postscript and pdf.
Causes and explanations: a structural-model approach. Part I: Causes
Joseph Y. Halpern and Judea Pearl
We propose a new definition of actual cause, using structural equations to model counterfactuals. We show that this definition yields a plausible and elegant account of causation that handles well examples that have caused problems for other definitions and resolves major difficulties in the traditional account.
In British Journal for the Philosophy of Science
Causes and explanations: a structural-model approach. Part II: Explanations
Joseph Y. Halpern and Judea Pearl
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 defined and motivated in a companion paper. Essentially, an explanation is a fact that is not known for certain but, if found to be true, would constitute an actual cause of the fact to be explained, regardless of the agent's initial uncertainty. We show that the definition handles well a number of problematic examples from the literature.
In British Journal for the Philosophy of Science
Lexicographic probability, conditional probability, and nonstandard probability
Joseph Y. Halpern
The relationship between Popper spaces (conditional probability spaces that satisfy some regularity conditions), lexicographic probability systems (LPS's), and nonstandard probability spaces (NPS's) is considered. If countable additivity is assumed, Popper spaces and a subclass of LPS's are equivalent; without the assumption of countable additivity, the equivalence no longer holds. If the state space is finite, LPS's are equivalent to NPS's. However, if the state space is infinite, NPS's are shown to be more general than LPS's.
In Games and Economic Behavior
Plausibility Measures: A General Approach for Representing Uncertainty
Joseph Y. Halpern
This is an overview of a number of my work on plausibility, which incorporates some material from Plausibility measures and default reasoning, Conditional plausibility measures and Bayesian networks , and Modeling belief in dynamic systems. Part II: Revision and update, as well as some new material on decision making.
In Proceedings of the 17th International Joint Conference on AI (IJCAI 2001), 2001, pp. 1474-1483. I hope to write a version of the paper more accessible to economists soon. The paper is available in postscript and pdf.
A cone-based distributed topology-control algorithm for wireless multi-hop networks
Li Li, Joseph Y. Halpern, Paramvir Bahl, Yi-Min Wang, and 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 algorithm. This algorithm does not assume that nodes have GPS information available; rather it depends only on directional information. Roughly speaking, the basic idea of the algorithm is that a node u transmits with the minimum power p required to ensure that in every cone of degree d around u, there is some node that u can reach with power p We show that taking d = 5pi/6 is a necessary and sufficient condition to guarantee that network connectivity is preserved. More precisely, if there is a path from s to t when every node communicates at maximum power then, if d < 5pi/6, there is still a path in the smallest symmetric graph G containing all edges (u,v) such that u can communicate with v using power p. On the other hand, if d > 5pi/6, connectivity is not necessarily preserved. We also propose a set of optimizations that further reduce power consumption and prove that they retain network connectivity. Dynamic reconfiguration in the presence of failures and mobility is also discussed. Simulation results are presented to demonstrate the effectiveness of the algorithm and the optimizations.
In IEEE/ACM Transactions on Networks
Zygmunt Haas, Joseph Y. Halpern, and 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, where each node forwards a message with some probability, to reduce the overhead of the routing protocols. Gossiping exhibits bimodal behavior in sufficiently large networks: in some executions, the gossip dies out quickly and hardly any node gets the message; in the remaining executions, a substantial fraction of the nodes gets the message. The fraction of executions in which most nodes get the message depends on the gossiping probability and the topology of the network. In the networks we have considered, using gossiping probability between 0.6 and 0.8 suffices to ensure that almost every node gets the message in almost every execution. For large networks, this simple gossiping protocol uses up to 35% fewer messages than flooding, with improved performance. Gossiping can also be combined with various optimizations of flooding to yield further benefits. Simulations show that adding gossiping to AODV results in significant performance improvement, even in networks as small as 150 nodes. We expect that the improvement should be even more significant in larger networks.
In IEEE/ACM Transactions on
Networking
Least expected cost query optimization: What can we expect?
Francis Chu, Johannes Gehrke, and Joseph Y. Halpern
A standard assumption in the database query optimization literature is that it is adequate to optimize for the ``typical'' case -- that is, the case in which various parameters (e.g., the amount of available memory, the selectivities of predicates, etc.) take on their ``typical'' values. In an earlier paper, we argued that we could do better by choosing plans based on their expected cost. Here we investigate this issue more thoroughly. We show that in many circumstances of interest, a ``typical'' value of the parameter often does give acceptable answers, provided that it is chosen carefully and we are interested only in minimizing expected running time. However, by minimizing the expected running time, we are effectively assuming that if plan P1 runs three times as long as plan P2, then P1 is exactly three times as bad as P2. An assumption like this is not always appropriate (for example, for time-critical data). We show that the focusing on least expected cost can lead to significant improvement for a number of cost functions of interest.
In Proceedings of the 21st ACM Symposium on Principles of Database Systems, 2002, pp. 293-302. The paper is available in postscript and pdf.
Secrecy in multi-agent systems
Joseph Y. Halpern and Kevin O'Neill
We introduce a general framework for reasoning about secrecy requirements in multiagent systems. Because secrecy requirements are closely connected with the knowledge of individual agents of a system, our framework employs the modal logic of knowledge within the context of the well-studied runs and systems framework. Put simply, ``secrets'' are facts about a system that low-level agents are never allowed to know. The framework presented here allows us to formalize this intuition precisely, in a way that is much in the spirit of Sutherland's notion of nondeducibility. Several well-known attempts to characterize the absence of information flow, including separability, generalized noninterference, and nondeducibility on strategies, turn out to be special cases of our definition of secrecy. However, our approach lets us go well beyond these definitions. It can handle probabilistic secrecy in a clean way, and it suggests generalizations of secrecy that may be useful for dealing with resource-bounded reasoning and with issues such as downgrading of information.
In ACM Transactions on Information and System Security
Peter D. Grunwald and Joseph Y. Halpern
As examples such as the Monty Hall puzzle show, applying conditioning to update a probability distribution on a ``naive space'', which does not take into account the protocol used, can often lead to counterintuitive results. Here we examine why. A criterion known as CAR (``coarsening at random'') in the statistical literature characterizes when ``naive'' conditioning in a naive space works. We show that the CAR condition holds rather infrequently, and we provide a procedural characterization of it, by giving a randomized algorithm that generates all and only distributions for which CAR holds. This substantially extends previous characterizations of CAR. We also consider more generalized notions of update such as Jeffrey conditioning and minimizing relative entropy (MRE). We give a generalization of the CAR condition that characterizes when Jeffrey conditioning leads to appropriate answers, but show that there are no such conditions for MRE. This generalizes and interconnects previous results obtained in the literature on CAR and MRE.
In Journal of AI Research 19, 2003. A preliminary version appears in Proceedings of the Eighteenth Conference on Uncertainty in AI, 2002, pp. 187-196. The paper is available at CoRR and locally in postscript and pdf.
Characterizing and reasoning about probabilistic and non-probabilistic expectation
Joseph Y. Halpern and Riccardo Pucella
Expectation is a central notion in probability theory. The notion of expectation also makes sense for other notions of uncertainty. We introduce a propositional logic for reasoning about expectation, where the semantics depends on the underlying representation of uncertainty. We give sound and complete axiomatizations for the logic in the case that the underlying representation is (a) probability, (b) sets of probability measures, (c) belief functions, and (d) possibility measures. We show that this logic is more expressive than the corresponding logic for reasoning about likelihood in the case of sets of probability measures, but equi-expressive in the case of probability, belief, and possibility. Finally, we show that satisfiability for these logics is NP-complete, no harder than satisfiability for propositional logic.
In Journal of the ACM 54:3, 2007. A preliminary version, with the title "Reasoning about expectation", appears in Proceedings of the Eighteenth Conference on Uncertainty in AI, 2002, pp. 207-215. The full paper is available at CoRR and locally in postscript and pdf
Modeling adversaries in a logic for security protocol analysis
Joseph Y. Halpern and Riccardo Pucella
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 adversaries that can compose and replay messages, and decipher them with known keys. The Dolev-Yao model is a useful abstraction, but it suffers from some drawbacks: it cannot handle the adversary knowing protocol-specific information, and it cannot handle probabilistic notions, such as the adversary attempting to guess the keys. We show how we can analyze security protocols under different adversary models by using a logic with a notion of algorithmic knowledge. Roughly speaking, adversaries are assumed to use algorithms to compute their knowledge; adversary capabilities are captured by suitable restrictions on the algorithms used. We show how we can model the standard Dolev-Yao adversary in this setting, and how we can capture more general capabilities including protocol-specific knowledge and guesses.
In Logical Methods in Computer Science
Using first-order logic to reason about policies
Joseph Y. Halpern and Vicky Weissman
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. Because we use first-order logic, policies have a clear syntax and semantics. We show that further restricting the fragment results in a language that is still quite expressive yet is also tractable. More precisely, questions about entailment, such as `May Alice access the file?', can be answered in time that is a low-order polynomial (indeed, almost linear in some cases), as can questions about the consistency of policy sets. We also give a brief overview of a prototype that we have built whose reasoning engine is based on the logic and whose interface is designed for non-logicians, allowing them to enter both policies and background information, such as `Alice is a student', and to ask questions about the policies.
In ACM Transactions on Information and System Security
Anonymity and information hiding in multiagent systems
Joseph Y. Halpern and Kevin O'Neill
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 within the context of the runs and systems framework, much in the spirit of our earlier work on secrecy. We give several definitions of anonymity with respect to agents, actions, and observers in multiagent systems, and we relate our definitions of anonymity to other definitions of information hiding, such as secrecy. We also give probabilistic definitions of anonymity that are able to quantify an observer's uncertainty about the state of the system. Finally, we relate our definitions of anonymity to other formalizations of anonymity and information hiding, including definitions of anonymity in the process algebra CSP and definitions of information hiding using function views.
In Journal of Computer Security
Great expectations. Part I: On the customizability of generalized expected utility
Francis C. Chu and Joseph Y. Halpern
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 with respect to general expectation structures, where a decision maker's beliefs are represented by plausibility measures and the decision maker's tastes are represented by general (i.e., not necessarily real-valued) utility functions. We call the resulting notion of expected utility generalized EU (GEU) and show that we can represent arbitrary preference relations on acts using GEU. We then shown that each of Savage's postulates corresponds to an axiom on GEU. Thus, GEU can be customized to capture postulates of interest.
In Theory and Decision 64:1, 2008, pp. 1-36. A preliminary version appears in Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), 2003, pp. 291-296. The full paper is available at CoRR and locally in postscript and pdf.
Great expectations. Part II: Generalized expected utility as a universal decision rule
Francis C. Chu and Joseph Y. Halpern
Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in a companion paper is a universal decision rule, in the sense that it can represent essentially all other decision rules.
In Artificial Intelligence
Responsibility and blame: A atructural-model approach
Hana Chockler and 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 to take into account the degree of responsibility of for B. For example, if someone wins an election 11-0, then each person who votes for him is less responsible for the victory than if he had won 6-5. We then define a notion of degree of blame, which takes into account an agent's epistemic state. Roughly speaking, the degree of blame of A for B is the expected degree of responsibility of A for B, taken over the epistemic state of an agent.
In Journal of AI Research
Probabilistic algorithmic knowledge
Joseph Y. Halpern and Riccardo Pucella
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 algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning ``Yes'' to a query about a fact p provides evidence for p being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.
In Logical Methods in Computer Science
A logic for reasoning about evidence
Joseph Y. Halpern and Riccardo Pucella
We introduce a logic for reasoning about evidence, that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, and consider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence.
In Journal of AI Research
Sleeping Beauty Reconsidered: Conditioning and Reflection in Asynchronous Systems
Joseph Y. Halpern
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 Beauty problem has been viewed as revealing problems with conditioning in the presence of imperfect recall, the analysis done here reveals that the problems are not so much due to imperfect recall as to asynchrony. The implications of this analysis for van Fraassen's Reflection Principle and Savage's Sure-Thing Principle are considered.
In Oxford Studies in Epistemology, Vol. 1 (T. S. Gendler and J. Hawthorne, eds.), 2005, pp. 111-142. A preliminary version appears in Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), 2004, pp. 12-22. The full paper is available at CoRR and locally in pdf.
Joseph Y. Halpern
There are many examples in the literature that suggest that indistinguishability is intransitive, despite the fact that the indistinguishability relation is typically taken to be an equivalence relation (and thus transitive). It is shown that if the uncertainty perception and the question of when an agent reports that two things are indistinguishable are both carefully modeled, the problems disappear, and indistinguishability can indeed be taken to be an equivalence relation. Moreover, this model also suggests a logic of vagueness that seems to solve many of the problems related to vagueness discussed in the philosophical literature. In particular, it is shown here how the logic can handle the Sorites Paradox.
In Review of Symbolic Logic 1:4, 2009, pp. 530--547. A preliminary version appears in Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), pp. 121-129. The full paper is available at CoRR and locally in postscript and pdf.
On the expressive power of dynamic logic, II
Joseph Y. Halpern
We show that nondeterministic first-order regular dynamic logic without equality is strictly more powerful than its deterministic counterpart. This paper is subsumed by On the expressive power of nondeterminism in dynamic logic, which deals with the case with equality.
MIT/LCS/TM-204, 1981.
Rational secret sharing and multiparty computation
Joseph Y. Halpern and Vanessa Teague
We consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as possible of the other agents get it. We show that, under these assumptions, neither secret sharing nor multiparty function computation is possible using a mechanism that has a fixed running time. However, we show that both are possible using randomized mechanisms with constant expected running time.
In Proceedings of 36th ACM Symposium on Theory of Computing, 2004, pp. 623-632. The paper is available at CoRR and locally in postscript and pdf.
Joseph Y. Halpern and 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 licenses. We focus on a representative fragment of the language and use it to highlight some problematic aspects of the algorithm. We then correct the problems, introduce formal semantics, and show that our semantics matches the (corrected) algorithm. Finally, we consider the complexity of determining if a permission is implied by a set of XrML licenses. We show that the general problem is NP-hard, but it is polynomial-time computable for an expressive fragment of the language.
In Journal of the ACM 55:1, 2008. A preliminary version In Proceedings of the 17th IEEE Computer Security Foundations Workshop, 2004, pp. 251-263. The paper is available at CoRR and locally in postscript and pdf.
An efficient algorithm for fault-tolerant clock synchronization
Joseph Y. Halpern, Barbara B. Simons, and H. Raymond Strong
This paper presents an efficient distributed algorithm for synchronizing clocks in the presence of failures. It is essentially subsumed by Dynamic fault-tolerant clock synchronization.
IBM RJ 4094, 1983.
On the power of the hypothesis of expressiveness
Steven M. German and Joseph Y. Halpern
We show that if an interpretation is Herbrand definable (every element in the domain is equal to some term in the Herbrand universe over some finite type) and expressive (i.e., we can express weakest preconditions), for a sufficiently rich programming language (one with assignment statements, if ... then ... else statements, and recursive procedure declarations) then it is either finite or strongly arithmetic (in the sense of Effective axiomatizations of Hoare logics). The result follows from an observation that in such a programming language we can write a program to generate all the terms in the Herbrand universe over a given type.
IBM RJ 4079, 1983.
Complete axiomatizations for reasoning about knowledge and time
Joseph Y. Halpern, Ronald van der Meyden, and 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 logics considered involve the discrete time linear temporal logic operators `next' and `until' and an operator for the knowledge of each of a number of agents. Both the single agent and multiple agent cases are studied: in some instances of the latter there is also an operator for the common knowledge of the group of all agents. Four different semantic properties of agents are considered: whether they have a unique initial state, whether they operate synchronously, whether they have perfect recall, and whether they learn. The property of no learning essentially dual to perfect recall. Not all settings of these parameters lead to recursively axiomatizable logics, but sound and complete axiomatizations are presented for all the ones that do.
In SIAM Journal on Computing
Plausibility Measures and Default Reasoning: An Overview
Nir Friedman and Joseph Y. Halpern
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, belief functions, and possibility measures. We then consider one application of plausibility measures: default reasoning. In recent years, a number of different semantics for defaults have been proposed, such as preferential structures, epsilon-semantics, possibilistic structures, and kappa-rankings, that have been shown to be characterized by the same set of axioms, known as the KLM properties. While this was viewed as a surprise, we show here that it is almost inevitable. In the framework of plausibility measures, we can give a necessary condition for the KLM axioms to be sound, and an additional condition necessary and sufficient to ensure that the KLM axioms are complete. This additional condition is so weak that it is almost always met whenever the axioms are sound. In particular, it is easily seen to hold for all the proposals made in the literature. Finally, we show that plausibility measures provide an appropriate basis for examining first-order default logics.
This paper is a brief overview of the results of Plausibility measures and default reasoning and First-order conditional logic for default logic revisited. It is a summary of an invited talk given at the 14th IEEE Symposium on Logic in Computer Science, 1999, and appears in the proceedings (pp. 130-135). The paper is available in postscript and pdf.
On the adequacy of modal logic
Joseph Y. Halpern
McCarthy has argued that modal logic is too limited for various purposes. I consider the extent to which he is right.
In Electronic News Journal on Reasoning about Action and Change 3, July-August 1999. The paper is available in postscript and pdf. McCarthy wrote a response to my paper, and I wrote a response to his, which also appears in the the News Journal on Reasoning about Action and Change and is available in postscript and pdf.
A computer scientist looks at game theory
Joseph Y. Halpern
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) specification and verification.
In Games and Economic Behavior 45:1, 2003, pp. 114-131. The paper is available at CoRR and locally in postscript and pdf.
Magnus M. Halldorsson, Joseph Y. Halpern, Li Li, and Vahab Mirrokni
Each access point (AP) in a WiFi network must be assigned a channel for it to service users. There are only finitely many possible channels that can be assigned. Moreover, neighboring access points must use different channels so as to avoid interference. Currently these channels are assigned by administrators who carefully consider channel conflicts and network loads. Channel conflicts among APs operated by different entities are currently resolved in an ad hoc manner or not resolved at all. We view the channel assignment problem as a game, where the players are the service providers and APs are acquired sequentially. We consider the price of anarchy of this game, which is the ratio between the total coverage of the APs in the worst Nash equilibrium of the game and what the total coverage of the APs would be if the channel assignment were done by a central authority. We provide bounds on the price of anarchy depending on assumptions on the underlying network and the type of bargaining allowed between service providers. The key tool in the analysis is the identification of the Nash equilibria with the solutions to a maximal coloring problem in an appropriate graph. We relate the price of anarchy of these games to the approximation factor of local optimization algorithms for the maximum k-colorable subgraph problem. We also study the speed of convergence to equilibrium in these games.
In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing, 2004, pp. 107-114. The paper is available in postscript and pdf.
Peter D. Grunwald and Joseph Y. Halpern
It is commonly-accepted wisdom that more information is better, and that information should never be ignored. Here we argue, using both a Bayesian and a non-Bayesian analysis, that in some situations you are better off ignoring information if your uncertainty is represented by a set of probability measures. These include situations in which the information is relevant for the prediction task at hand. In the non-Bayesian analysis, we show how ignoring information avoids dilation, the phenomenon that additional pieces of information sometimes lead to an increase in uncertainty. In the Bayesian analysis, we show that for small sample sizes and certain prediction tasks, the Bayesian posterior based on a noninformative prior yields worse predictions than simply ignoring the given information.
In Proceedings of the Twentieth Conference on Uncertainty in AI, 2004, pp. 226-234. The paper is available at CoRR and locally in postscript and pdf.
A data-acquisition model for learning and cognitive development and its implications for autism
Arnon Lotem and 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 the data-acquisition component of the model---essentially, it is the result of getting an ``inappropriate'' distribution of data. It is shown how the model, given ``inappropriate'' data distributions, can reproduce the main symptoms associated with autism, including weak central coherence, impaired theory of mind, and executive dysfunction. In addition, it is shown how the model itself can explain the inappropriate data distribution as the result of an inappropriate initial network. Finally, implications of the model for treatment are discussed.
The paper is available in pdf.
What causes a system to satisfy a specification?
Hana Chockler, Joseph Y. Halpern, and 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 system. Coverage metrics attempt to check which parts of a system are actually relevant for the verification process to succeed. Recent work on coverage in model checking suggests several coverage metrics and algorithms for finding parts of the system that are not covered by the specification. The work has already proven to be effective in practice, detecting design errors that escape early verification efforts in industrial settings. In this paper, we relate a formal definition of causality given in by Halpern and Pearl to coverage. We show that it gives significant insight into unresolved issues regarding the definition of coverage and leads to potentially useful extensions of coverage. In particular, we introduce the notion of responsibility, which assigns to components of a system a quantitative measure of their relevance to the satisfaction of the specification.
In ACM Transactions on Computational Logic 9:3, 2008. The paper is available at CoRR and locally in postscript and pdf.
Knowledge-based synthesis of distributed systems using event structures
Mark Bickford, Robert L. Constable, Joseph Y. Halpern, and 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 particularly effective if the specifications are written in a high-level language that makes it easy for designers to specify their goals. We consider a high-level specification language that results from adding knowledge to a fragment of Nuprl specifically tailored for specifying distributed protocols, called event theory. We then show how high-level knowledge-based programs can be synthesized from the knowledge-based specifications using a proof development system such as Nuprl. Methods of Halpern and Zuck then apply to convert these knowledge-based protocols to ordinary protocols. These methods can be expressed as heuristic transformation tactics in Nuprl.
In Logical Methods in Computer Science 7:2, 2011. A preliminary version appears in Proceedings of the 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2004), 2005 (Lecture Notes in Computer Science, vol. 3452), pp. 449-465. The full paper is available at CoRR and locally in pdf.
Interactive awareness revisited
Joseph Y. Halpern and Leandro Rego
We analyze a model of interactive unawareness introduced by Heifetz, Meier and Schipper (HMS). We consider two axiomatizations for their model, which capture different notions of validity. These axiomatizations allow us to compare the HMS approach to both the standard (S5) epistemic logic and two other approaches to unawareness: that of Fagin and Halpern and that of Modica and Rustichini. We show that the differences between the HMS approach and the others are mainly due to the notion of validity used and the fact that the HMS is based on a 3-valued propositional logic.
In Games and Economic Behavior 62:1, 2008, pp. 232-262. A preliminary version appears in Proceedings of Tenth Conference on Theoretical Aspects of Rationality and Knowledge, 2005, pp. 78-91. The full paper is available at CoRR and locally in postscript and pdf.
Evidence with uncertain likelihoods
Joseph Y. Halpern and Riccardo Pucella
An agent often has a number of hypotheses, and must choose among them based on observations, or outcomes of experiments. Each of these observations can be viewed as providing evidence for or against various hypotheses. All the attempts to formalize this intuition up to now have assumed that associated with each hypothesis h there is a likelihood function, which is a probability measure that intuitively describes how likely each observation is, conditional on h being the correct hypothesis. We consider an extension of this framework where there is uncertainty as to which of a number of likelihood functions is appropriate, and discuss how one formal approach to defining evidence, which views evidence as a function from priors to posteriors, can be generalized to accommodate this uncertainty.
In Synthese
Redoing the foundations of decision theory
Lawrence E. Blume, Joseph Y. Halpern, and David Easley
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 which the decision maker (DM) has preferences. Most interesting decision problems, however, do not come with a state space and an outcome space. Indeed, in complex problems it is often far from clear what the state and outcome spaces would be. We present an alternative foundation for decision making, in which the primitive objects of choice are syntactic programs. A representation theorem is proved in the spirit of standard representation theorems, showing that if the DM's preference relation on objects of choice satisfies appropriate axioms, then there exist a set S of states, a set O of outcomes, a way of interpreting the objects of choice as functions from S to O, a probability on S, and a utility function on O, such that the DM prefers choice a to choice b if and only if the expected utility of a is higher than that of b. Thus, the state space and outcome space are subjective, just like the probability and utility; they are not part of the description of the problem. In principle, a modeler can test for SEU behavior without having access to states or outcomes. We illustrate the power of our approach by showing that it can capture decision makers who are subject to framing effects.
A preliminary version appears in Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), 2006, pp. 14-24. The full version, which has the title "Constructive Decision Theory". is available CoRR and locally.
Reasoning about knowledge of unawareness
Joseph Y. Halpern and Leandro Rego
Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an agent knows that there are facts of which he is unaware without there being an explicit fact that the agent knows he is unaware of. We propose a logic for reasoning about knowledge of unawareness, by extending Fagin and Halpern's Logic of General Awareness. The logic allows quantification over variables, so that there is a formula in the language that can express the fact that ``an agent explicitly knows that there exists a fact of which he is unaware''. Moreover, that formula can be true without the agent explicitly knowing that he is unaware of any particular formula. We provide a sound and complete axiomatization of the logic, using standard axioms from the literature to capture the quantification operator. Finally, we show that the validity problem for the logic is recursively enumerable, but not decidable.
In Games and Economic Behavior
Extensive games with possibly unaware players
Joseph Y. Halpern and Leandro Rego
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 structure of the game. In particular, they may not be aware of moves that they and other agents can make. We show how such games can be represented; the key idea is to describe the game from the point of view of every agent at every node of the game tree. We provide a generalization of Nash equilibrium and show that every game with awareness has a generalized Nash equilibrium. Finally, we extend these results to games with awareness of unawareness, where a player i may be aware that a player j can make moves that i is not aware of and to subjective games, where payers may have no common knowledge regarding the actual game and their beliefs are incompatible with a common prior.
In Mathematical Social Sciences {\bf 70}, 2014, pp. 42--58. A preliminary version appears in Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, 2006, pp. 744-751. The full version is available at CoRR and locally in postscript and pdf.
Efficiency and Nash equilibria in a scrip system for P2P networks
Eric J. Friedman, Joseph Y. Halpern, and Ian Kash
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. The effect of varying the total amount of money (scrip) in the system on efficiency (i.e., social welfare) is analyzed, and it is shown that by maintaining the appropriate ratio between the total amount of money and the number of agents, efficiency is maximized. The work has implications for many online systems, not only P2P networks but also a wide variety of online forums for which scrip systems are popular, but formal analyses have been lacking.
A preliminary version appears in Proceedings of the Seventh ACM Conference on Electronic Commerce, 2006, pp. 140-149, and is available at CoRR and locally in postscript and pdf. Material from this paper, the conference version of "Optimizing scrip systems: efficiency, crashes, hoarders, and altruists", and "Manipulating scrip systems: sybils and collusion" was combined and then split into two journal papers; see here and here.
Ittai Abraham, Danny Dolev, Rica Gonen, and Joseph Y. Halpern
We study k-resilient Nash equilibria, joint strategies where no member of a coalition C of size up to k can do better, even if the whole coalition defects. We show that such k-resilient Nash equilibria exist for secret sharing and multiparty computation, provided that players prefer to get the information than not to get it. Our results hold even if there are only 2 players, so we can do multiparty computation with only two rational agents. We extend our results so that they hold even in the presence of up to t players with ``unexpected'' utilities. Finally, we show that our techniques can be used to simulate games with mediators by games without mediators.
A preliminary version appears in Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006, pp. 53-62, and is available in postscript and pdf.
A knowledge-based analysis of global function computation
Joseph Y. Halpern and 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 network, the goal is for every agent to eventually compute the value f(N). We call this problem global function computation. Various solutions for instances of this problem, such as Boolean function computation, leader election, (minimum) spanning tree construction, and network determination, have been proposed, each under particular assumptions about what processors know about the system and how this knowledge can be acquired. We give a necessary and sufficient condition for the problem to be solvable that generalizes a number of well-known results. We then provide a knowledge-based (kb) program (like those of Fagin, Halpern, Moses, and Vardi) that solves global function computation whenever possible. Finally, we improve the message overhead inherent in our initial kb program by giving a counterfactual belief-based program that also solves the global function computation whenever possible, but where agents send messages only when they believe it is necessary to do so. The latter program is shown to be implemented by a number of well-known algorithms for solving leader election.
In Distributed Computing 23:3, 2010, pp. 197-224. A preliminary version appears in Proceedings of the 20th International Symposium on Distributed Computing, 2006, pp. 136-150. The full version is available at CoRR and locally in pdf.
Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
Joseph Y. Halpern and Leandro Rego
There has been a great deal of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the satisfiability problem for all logics between K and S4 is PSPACE-hard, while for S5 it is NP-complete. We show that it is negative introspection, the axiom ~Kp -> K~Kp, that causes the gap: if we add this axiom to any modal logic between K and S4, then the satisfiability problem becomes NP-complete. Indeed, the satisfiability problem is NP-complete for any modal logic that includes the negative introspection axiom.
In Journal of Logic and Computation 17:4, pp. 795-806, 2007. A preliminary version appears in Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), 2007, pp. 2306-2312. The full version is available at CoRR and locally in postscript and pdf.
Characterizing solution concepts in games using knowledge-based programs
Joseph Y. Halpern and Yoram Moses
We show how solution concepts in games such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of knowledge-based programs. Intuitively, all solution concepts are implementations of two knowledge-based programs, one appropriate for games represented in normal form, the other for games represented in extensive form. These knowledge-based programs can be viewed as embodying rationality. The representation works even if (a) information sets do not capture an agent's knowledge, (b) uncertainty is not represented by probability, or (c) the underlying game is not common knowledge.
A preliminary version appears in Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), 2007, pp. 1300-1307 The full version is available at CoRR and locally in postscript and pdf. The conference version was expanded and then split into two papers: "A procedural characterization of solution concepts in games" and "Characterizing solution concepts in terms of common knowledge of rationality".
Worst-case background knowledge for privacy-preserving data publishing
David J. Martin, Daniel Kifer, Ashwin Machanavajjhala, Johannes Gehrke, and 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 background knowledge the attacker possesses. Thus, it is important to consider the worst-case. In this paper, we initiate a formal study of worst-case background knowledge. We propose a language that can express any background knowledge about the data. We provide a polynomial time algorithm to measure the amount of disclosure of sensitive information in the worst case, given that the attacker has at most k pieces of information in this language. We also provide a method to efficiently sanitize the data so that the amount of disclosure in the worst case is less than a specified threshold.
In Proceedings of the 23rd International Conference on Data Engineering, 2007, pp. 126-135. Available available at CoRR and locally in pdf.
Optimizing scrip systems: efficiency, crashes, hoarders, and altruists
Ian A. Kash, Eric J. Friedman, and Joseph Y. Halpern
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 agents in a system can be inferred from the equilibrium distribution of money. From the perspective of a system designer, we examine the effect of the money supply on social welfare and show that social welfare is maximized by increasing the money supply up to the point that the system experiences a ``monetary crash,'' where money is sufficiently devalued that no agent is willing to perform a service. We also examine the implications of the presence of altruists and hoarders on the performance of the system. While a small number of altruists may improve social welfare, too many can also cause the system to experience a monetary crash, which may be bad for social welfare. Hoarders generally decrease social welfare but, surprisingly, they also promote system stability by helping prevent monetary crashes. In addition, we provide new technical tools for analyzing and computing equilibria by showing that our model exhibits strategic complementarities, which implies that there exist equilibria in pure strategies that can be computed efficiently.
In Distributed Computing 25:25, 2012, pp. 335-357. A preliminary version appears in Proceedings of the Eighth ACM Conference on Electronic Commerce, 2007, pp. 305-315. The conference version is available at CoRR and locally in postscript and pdf. The journal version (which also incorporates material from "Efficiency and Nash equilibria in a scrip system for P2P networks" and "Manipulating scrip systems: sybils and collusion", is available here.
Dealing with logical omniscience
Joseph Y. Halpern and Riccardo Pucella
We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest they are not. In particular, adding probabilities to the language allows for finer distinctions between different approaches.
In Artificial Intelligence 175:1, 2011, pp. 220--235. A preliminary version appears in Proceedings of Eleventh Conference on Theoretical Aspects of Rationality and Knowledge, 2007, pp. 169-176. The full paper is available at CoRR and locally in postscript and pdf.
From statistical knowledge bases to degrees of belief: an overview
Joseph Y. Halpern
This is a summary of an invited talk, which covers material from From statistical knowledge bases to degrees of belief. Available in postscript and pdf.
Causality, responsibility, and blame: a structural-model approach
Joseph Y. Halpern
This is a summary of an invited talk, which covers material from Causes and explanations: a structural-model approach. Part I: Causes, Responsibility and blame: A atructural-model approach, and What causes a system to satisfy a specification?. In Proceedings of the Third International Conference on the Quantitative Evaluation of Systems, 2006, pp. 3-6. Available in postscript and pdf.
Generalized solution concepts in games with possibly unaware players
Joseph Y. Halpern and Leandro Rego
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 analyzing games with possibly unaware players, and suggested a generalization of Nash equilibrium appropriate for games with unaware players that we called generalized Nash equilibrium. Here, we use this framework to analyze other solution concepts that have been considered in the game-theory literature, with a focus on sequential equilibrium. We also provide some insight into the notion of generalized Nash equilibrium by proving that it is closely related to the notion of rationalizability when we restrict the analysis to games in normal form and no unawareness is involved.
In International Journal of Game Theory
Joseph Y. Halpern
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 (σ,μ) is a sequential equilibrium in an extensive game with perfect recall iff there exist an infinitesimal epsilon and a strategy profile σ' consisting of completely mixed behavioral strategies (so that σ_{i} assigns positive, although possibly infinitesimal, probability to all actions at every information set) which differs only infinitesimally from σ such that at each information set I for player i, σ_{i} is an ε-best response to σ'_{-i} conditional on having reached I. Note that the characterization of sequential equilibrium does not involve belief systems. There is a similar characterization of perfect equilibrium; the only difference is that σ_{i} must be a best response to σ'_{-i} conditional on having reached I. Yet another variant is used to characterize proper equilibrium.
In International Journal of Game Theory 3838:1, 2009, pp. 37-50; available in postscript and pdf. An erratum appears here.
Computer science and game theory: A brief survey
Joseph Y. Halpern
There has been a remarkable increase in work at the interface of computer science and game theory in the past decade. Game theory forms a significant component of some major computer science conferences; leading computer scientists are often invited to speak at major game theory conferences. I survey some of the main themes of work in the area, with a focus on the work in computer science. In particular, I look at the various roles of computational complexity in game theory, including its use in modeling bounded rationality, its role in mechanism design, and the problem of computing Nash equilibria; I consider a game-theoretic problem that originated in the computer science literature, but should be of interest to the game theory community: computing the price of anarchy, that is, the cost of using decentralizing solution to a problem; and I consider interactions between distributed computing and game theory. Given the length constraints, I make no attempt at being comprehensive.
In Palgrave Dictionary of Economics (S. N. Durlauf and L. E. Blume, eds.), Palgrave MacMillan, 2008. Available at CoRR and locally postscript and pdf.
Toward expressive and scalable sponsored search auctions
David J. Martin, Johannes Gehrke, and 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 searches and the users' low tolerance for search result latency, it is imperative to resolve these auctions fast. Current approaches restrict the expressiveness of bids in order to achieve fast winner determination, which is the problem of allocating slots to advertisers so as to maximize the expected revenue given the advertisers' bids. The goal of our work is to permit more expressive bidding, thus allowing advertisers to achieve complex advertising goals, while still providing fast and scalable techniques for winner determination. We also discuss the application of our framework to advertising in massively multiplayer online games.
In Proceedings of the 24th International Conf. Data Engineering, 2008, pp. 237-246. Available at CoRR and locally.
Lower bounds on implementing robust and resilient mediators
Ittai Abraham, Danny Dolev, and Joseph Y. Halpern
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 general, it is impossible to implement three-player Nash equilibria in a bounded number of rounds. We also give the first rigorous connection between Byzantine agreement lower bounds and lower bounds on implementation. To this end we consider a number of variants of Byzantine agreement and introduce reduction arguments. We also give lower bounds on the running time of two player implementations. All our results extended to lower bounds on (k,t)-robust equilibria, a solution concept that tolerates deviations by coalitions of size up to k and deviations by up to t players with unknown utilities (who may be malicious).
A preliminary version appears in Proceedings of the Fifth Theory of Cryptography Conference, 2008, pp. 302--319 and is available at CoRR and locally in postscript and pdf.
From qualitative to quantitative proofs of security properties using first-order conditional logic
Joseph Y. Halpern
A first-order conditional logic is considered, with semantics given by a variant of ε-semantics, where p → q means that Pr(q | p) approaches 1 super-polynomially---faster than any inverse polynomial. This type of convergence is needed for reasoning about security protocols. A complete axiomatization is provided for this semantics, and it is shown how a qualitative proof of the correctness of a security protocol can be automatically converted to a quantitative proof appropriate for reasoning about concrete security.
In AAAI-08 (Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence), 2008; available at CoRR and locally in postscript and pdf.
Beyond Nash equilibrium: Solution concepts for the 21st century
Joseph Y. Halpern
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 equilibrium of repeated prisoner's dilemma is neither normatively nor descriptively reasonable. However, new problems arise when considering Nash equilibrium from a computer science perspective: for example, Nash equilibrium is not robust (it does not tolerate ``faulty'' or ``unexpected'' behavior), it does not deal with coalitions, it does not take computation cost into account, and it does not deal with cases where players are not aware of all aspects of the game. Solution concepts that try to address these shortcomings of Nash equilibrium are discussed.
In Lectures in Game Theory for Computer Scientists (K. R. Apt and E. Gradel, editors), pp. 264--289. A preliminary version appears in Proceedings of the 27th Annual ACM Symposium on Principles of Distributed Computing, 2008, pp. 1-10 and is reprinted in Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), 2008. Available at CoRR and locally in postscript and pdf.
Defaults and normality in causal structures
Joseph Y. Halpern
A serious defect with the Halpern-Pearl (HP) definition of causality is repaired by combining a theory of causality with a theory of defaults. In addition, it is shown that (despite a claim to the contrary) a cause according to the HP condition need not be a single conjunct. A definition of causality motivated by Wright's NESS test is shown to always hold for a single conjunct. Moreover, conditions that hold for all the examples considered by HP are given that guarantee that causality according to (this version) of the NESS test is equivalent to the HP definition.
In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), 2008, pp. 198-208. Available at CoRR and locally in postscript and pdf.
Making decisions using sets of probabilities: updating, time consistency, and calibration
Peter D. Grunwald and Joseph Y. Halpern
We consider how an agent should update her uncertainty when it is represented by a set P of probability distributions and the agent observes that a random variable X takes on value x, given that the agent makes decisions using the minimax criterion, perhaps the best-studied and most commonly-used criterion in the literature. We adopt a game-theoretic framework, where the agent plays against a bookie, who chooses some distribution from P. We consider two reasonable games that differ in what the bookie knows when he makes his choice. Anomalies that have been observed before, like time inconsistency, can be understood as arising because different games are being played, against bookies with different information. We characterize the important special cases in which the optimal decision rules according to the minimax criterion amount to either conditioning or simply ignoring the information. Finally, we consider the relationship between conditioning and calibration when uncertainty is described by sets of probabilities. Our results emphasize the key role of Epstein and Schneider's rectangularity condition.
In Journal of AI Research
Expressing security properties using selective interleaving functions
Joseph Y. Halpern and Sabina Petride
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 SIFs carefully. We show that SIFs cannot capture nondeducibility on strategies (NOS). We also prove that the set of security properties expressed with SIFs is not closed under conjunction, from which it follows that separability is strictly stronger than double generalized noninterference. However, we show that if we generalize the notion of SIF in a natural way, then NOS is expressible, and the set of security properties expressible by generalized SIFs is closed under conjunction.
Unpublished manuscript. Available at CoRR and locally in postscript and pdf.
Ittai Abraham, Danny Dolev, and Joseph Y. Halpern
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 simultaneously achieves three properties:
In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008, pp. 405-414. Available at CoRR and locally in in postscript and pdf.
Ian A. Kash, Eric J. Friedman, and Joseph Y. Halpern
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 BitTorrent's unchoking policy, BAR Gossip's balanced exchanges, and threshold strategies in scrip systems. An attacker can exploit this by providing service in a targeted way to prevent chosen nodes from providing service.
In Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008, p. 455. Available at CoRR.
Iterated regret minimization: A more realistic solution concept
Joseph Y. Halpern and 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 consistent with empirical observations. In this paper, we introduce a new solution concept, iterated regret minimization, which exhibits the same qualitative behavior as that observed in experiments in many games of interest, including Traveler's Dilemma, the Centipede Game, Nash bargaining, and Bertrand competition. As the name suggests, iterated regret minimization involves the iterated deletion of strategies that do not minimize regret.
In Games and Economic Behavior
Game theory with costly computation
Joseph Y. Halpern and 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 existence of a Nash equilibrium) no longer hold. Nevertheless, we can use the framework to provide psychologically appealing explanations to observed behavior in well-studied games (such as finitely repeated prisoner's dilemma and rock-paper-scissors). Furthermore, we provide natural conditions on games sufficient to guarantee that equilibria exist. As an application of this framework, we consider a notion of game-theoretic implementation of mediators in computational games. We show that a special case of this notion is equivalent to a variant of the traditional cryptographic definition of protocol security; this result shows that, when taking computation into account, the two approaches used for dealing with ``deviating'' players in two different communities -- Nash equilibrium in game theory, and zero-knowledge ``simulation'' in cryptography -- are intimately connected.
In First Symposium on Innovations in Computer Science, 2010, pp. 120-142. The full version is available in postscript and pdf. This material is largely subsumed by "A computational game-theoretic framework for cryptography" and "Algorithmic rationality: Adding cost of computation to game theory".
Shared winner determination in sponsored search auctions
David J. Martin, Johannes Gehrke, and Joseph Y. Halpern
Sponsored search auctions form a multibillion dollar industry. Search providers auction advertisement slots on search result pages to advertisers who are charged only if the end-user clicks on the advertiser's ad. The high volume of searches presents an opportunity for sharing the work required to resolve multiple auctions that occur simultaneously. We provide techniques for efficiently resolving sponsored search auctions involving large numbers of advertisers, with a focus on two issues: sharing work between multiple search auctions using shared aggregation and shared sort, and dealing with budget uncertainty arising from ads that have been displayed from previous auctions but have not received clicks yet.
In Proceedings of the 25th International Conf. Data Engineering, 2009, pp. 270-280. Available locally here.
Multiagent learning in large anonymous games
Ian A. Kash, Eric J. Friedman, and Joseph Y. Halpern
In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if best-reply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed.
In Journal of AI Research 40, 2011, pp. 571-598. A preliminary version appears in Proceedings of the Eighth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2009, pp. 765-772. Available at CoRR and locally in pdf.
Manipulating scrip systems: sybils and collusion
Ian A. Kash, Eric J. Friedman, and Joseph Y. Halpern
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 than one agent. We examine the effects of two types of strategic behavior involving more than one agent, sybils and collusion, in the context of scrip systems where agents provide each other with service in exchange for scrip. Sybils make an agent more likely to be chosen to provide service, which generally makes it harder for agents without sybils to earn money and decreases social welfare. Surprisingly, in certain circumstances it is possible for sybils to make all agents better off. While collusion is generally bad, in the context of scrip systems it actually tends to make all agents better off, not merely those who collude. These results also provide insight into the effects of allowing agents to advertise and loan money.
In Proceedings of the First Conference on Auctions, Market Mechanisms, and Multiagent Systems (AMMA), 2009. Available at CoRR.
On Definability in Multimodal Logic
Joseph Y. Halpern, Dov Samet, and Ella Segev
Three notions of definability in multimodal logic are considered. Two are analogous to the notions of explicit definability and implicit definability introduced by Beth in the context of first-order logic. However, while by Beth's theorem the two types of definability are equivalent for first-order logic, such an equivalence does not hold for multimodal logics. A third notion of definability, reducibility, is introduced; it is shown that in multimodal logics, explicit definability is equivalent to the combination of implicit definability and reducibility. The three notions of definability are characterized semantically using (modal) algebras. The use of algebras, rather than frames, is shown to be necessary for these characterizations.
In Review of Symbolic Logic
Defining knowledge in terms of belief: the modal logic perspective
Joseph Y. Halpern, Dov Samet, and Ella Segev
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 doxastic logics. Three notions of definability are considered: explicit definability, implicit definability, and reducibility, where explicit definability is equivalent to the combination of implicit definability and reducibility. It is shown that if knowledge satisfies any set of axioms contained in S5, then it cannot be explicitly defined in terms of belief. S5 knowledge can be implicitly defined by belief, but not reduced to it. On the other hand, S4.4 knowledge and weaker notions of knowledge cannot be implicitly defined by belief, but can be reduced to it by defining knowledge as true belief. It is also shown that S5 knowledge cannot be reduced to belief and justification, provided that there are no axioms that involve both belief and justification.
In Review of Symbolic Logic
A logical characterization of iterated admissibility
Joseph Y. Halpern and Rafael Pass
Brandenburger, Friedenberg, and Keisler provide an epistemic characterization of iterated admissibility (i.e., iterated deletion of weakly dominated strategies) where uncertainty is represented using LPSs (lexicographic probability sequences). Their characterization holds in a rich structure called a complete structure, where all types are possible. Here, a logical characterization of iterated admissibility is given that involves only standard probability and holds in all structures, not just complete structures. A stronger notion of strong admissibility is then defined. Roughly speaking, strong admissibility is meant to capture the intuition that ``all the agent knows'' is that the other agents satisfy the appropriate rationality assumptions. Strong admissibility makes it possible to relate admissibility, canonical structures (as typically considered in completeness proofs in modal logic), complete structures, and the notion of ``all I know''.
In Proceedings of Twelfth Conference on Theoretical Aspects of Rationality and Knowledge, 2009, pp. 146-155; the full paper is available at CoRR and locally in postscript and pdf. A version of the paper also appears in Knowing, Reasoning, and Acting: Essays in Honour of Hector J. Levesque (G. Lakemeyer and S. A. McIlraith, editors), College Publications, 2011, with the title ``That's all I know: A logical characterization of iterated admissibility''.
An epistemic characterization of zero knowledge
Joseph Y. Halpern, Rafael Pass, and Vasumathi Raman
Halpern, Moses and Tuttle presented a definition of interactive proofs using a notion they called practical knowledge, but left open the question of finding an epistemic formula that completely characterizes zero knowledge; that is, a formula that holds iff a proof is zero knowledge. We present such a formula, and show that it does characterize zero knowledge. Moreover, we show that variants of the formula characterize variants of zero knowledge such as concurrent zero knowledge and proofs of knowledge.
In Proceedings of Twelfth Conference on Theoretical Aspects of Rationality and Knowledge, 2009, pp. 156-165; available locally in postscript and pdf.
Reasoning about knowledge of unawareness revisited
Joseph Y. Halpern and Leandro Rego
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 the fact that an agent knows that there are some facts of which he is unaware. In that logic, it is not possible to model an agent who is uncertain about whether he is aware of all formulas. To overcome this problem, we keep the syntax of the earlier paper, but allow models where, with each world, a possibly different language is associated. We provide a sound and complete axiomatization for this logic and show that, under natural assumptions, the quantifier-free fragment of the logic is characterized by exactly the same axioms as the logic of Heifetz, Meier, and Schipper [2008].
In Mathematical Social Sciences
Joseph Y. Halpern
I answer five questions, including ``Why were you initially drawn to epistemology (and what keeps you interested)?'' and ``What do you see as being your main contributions to epistemology?''.
In Epistemology: 5 Questions (ed. V. F Hendricks and D. Pritchard), Automatic Press/VIP, 2008, pp. 155-166. Available locally in postscript and pdf.
Conservative belief and rationality
Joseph Y. Halpern and Rafael Pass
Brandenburger and Dekel have shown that common belief of rationality (CBR) characterizes rationalizable strategies, which are also characterized by a refinement of subjective correlated equilibrium called a posteriori equilibrium. It is possible that players' beliefs might be incompatible, in the sense that player i can assign probability 1 to an event E to which player j assigns probability 0. One way to block incompatibility is to assume a common prior. We consider here a different approach: we require players beliefs to be justified, in the sense that all players must ascribe the actual world positive probability. Aumann has shown that, under the common prior assumption (CPA), common belief of rationality characterizes strategies in the support of an objective correlated equilibrium. We can show that, if the CPA holds, then we can assume without loss of generality that players' beliefs are justified. We then consider the consequences of common justified belief of rationality (CJBR), without the common prior assumption. We show that CJBR characterize strategies in the support of a subjective correlated equilibrium where all players' beliefs have common support. We also define a notion of strong rationalizability, and show that this is characterized by CJBR.
In Games and Economic Behavior 80, 2013, pp. 186-192. Available locally in pdf.
Heuristics, Probability and Causality: A Tribute to Judea Pearl
Rina Dechter, Hector Geffner, and Joseph Y. Halpern (editors)
This is a festschrift for Judea Pearl. More details regarding the festscrift can be found here. The book was published by College Publications, 2010.
Viewpoint: Journals for Certification, Conferences for Rapid Dissemination
Joseph Y. Halpern and David C. Parkes
The publication culture in Computer Science is different from that of all other disciplines. Whereas other disciplines focus on journal publication, the standard practice in CS has been to publish in a conference and then (sometimes) publish a journal version of the conference paper. We discuss the role of journal publication in CS.
In Communications of the ACM
Joseph Y. Halpern, Nan Rong, and Ashutosh Saxena
Markov decision processes (MDPs) are widely used for modeling decision-making problems in robotics, automated control, and economics. Traditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of interest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibilities that a DM may not be aware of all possible actions. We provide a complete characterization of when a DM can learn to play near-optimally in an MDPU, and give an algorithm that learns to play In particular, we characterize when a near-optimal solution can be found in polynomial time.
In Proceedings of the Twenty-Fourth Conference on Uncertainty in AI, 2010, pp. 228-235. The paper is available at CoRR.
Joseph Y. Halpern and Nan Rong
Nash equilibrium (NE) assumes that players always make a best response. However, this is not always true; sometimes people cooperate even it is not a best response to do so. For example, in the Prisoner's Dilemma, people often cooperate. Are there rules underlying cooperative behavior? In an effort to answer this question, we propose a new equilibrium concept: perfect cooperative equilibrium . PCE may help explain players' behavior in games where cooperation is observed in practice. A player's payoff in a PCE is at least as high as in any NE. However, a PCE does not always exist. We thus consider a-PCE, where a takes into account the degree of cooperation; a PCE is a 0-PCE. Every game has a Pareto-optimal max-perfect cooperative equilibrium (M-PCE); that is, an a-PCE for a maximum a. We show that M-PCE does well at predicting behavior in quite a few games of interest. We provide further insight into M-PCE, at least in two-player games, by considering another generalization of PCE called cooperative equilibrium (CE), which takes the possibility of punishment into account. We show that a Pareto-optimal M-PCE must be a CE.
In Proceedings of the Ninth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), 2010, pp. 1465-1466. Here is a greatly expanded version of the AAMAS paper.
From causal models to counterfactual structures
Joseph Y. Halpern
Galles and Pearl claimed that ``for recursive models, the causal model framework does not add any restrictions to counterfactuals, beyond those imposed by Lewis's [possible-worlds] framework.'' This claim is examined carefully, with the goal of clarifying the exact relationship between causal models and Lewis's framework. Recursive models are shown to correspond precisely to a subclass of (possible-world) counterfactual structures. On the other hand, a slight generalization of recursive models, models where all equations have unique solutions, is shown to be incomparable in expressive power to counterfactual structures, despite the fact that the Galles and Pearl arguments should apply to them as well. The problem with the Galles and Pearl argument is identified: an axiom that they viewed as irrelevant, because it involved disjunction (which was not in their language), is not irrelevant at all.
In Review of Symbolic Logic 6:2, 2013, pp. 305--322. A preliminary version appears in Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), 2010, pp. 153-160. Available at CoRR and locally in pdf.
I don't want to think about it now: Decision theory with costly computation
Joseph Y. Halpern and Rafael Pass
Computation plays a major role in decision making. Even if an agent is willing to ascribe a probability to all states and a utility to all outcomes, and maximize expected utility, doing so might present serious computational problems. Moreover, computing the outcome of a given act might be difficult. In a companion paper we develop a framework for game theory with costly computation, where the objects of choice are Turing machines. Here we apply that framework to decision theory. We show how well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on), belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions), and the status quo bias (people are much more likely to stick with what they already have) can be easily captured in that framework. Finally, we use the framework to define some new notions: value of computational information (a computational variant of value of information) and and computational value of conversation.
In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), 2010, pp. 182-190. Available at CoRR locally in pdf.
Actual causation and the art of modeling
Joseph Y. Halpern and Christopher Hitchcock
We look more carefully at the modeling of causality using structural equations. It is clear that the structural equations can have a major impact on the conclusions we draw about causality. In particular, the choice of variables and their values can also have a significant impact on causality. These choices are, to some extent, subjective. We consider what counts as an appropriate choice. More generally, we consider what makes a model an appropriate model, especially if we want to take defaults into account, as was argued is necessary in recent work.
In Heuristics, Probability and Causality: A Tribute to Judea Pearl (editors, R. Dechter, H. Geffner, and J. Y. Halpern), College Publications, 2010, pp. 383-406. Available at CoRR and locally in pdf.
No justified complaints: On fair sharing of multiple resources
Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, and Nati Linial
Fair allocation has been studied intensively in both economics and computer science, and fair sharing of resources has aroused renewed interest with the advent of virtualization and cloud computing. Prior work has typically focused on mechanisms for fair sharing of a single resource. We provide a new definition for the simultaneous fair allocation of multiple continuously-divisible resources. Roughly speaking, we define fairness as the situation where every user either gets all the resources he wishes for, or else gets at least his entitlement on some bottleneck resource, and therefore cannot complain about not getting more. This definition has the same desirable properties as the recently suggested dominant resource fairness, and also handles the case of multiple bottlenecks. We then prove that a fair allocation according to this definition is guaranteed to exist for any combination of user requests and entitlements (where a user's relative use of the different resources is fixed). The proof, which uses tools from the theory of ordinary differential equations, is constructive and provides a method to compute the allocations numerically.
Proceedings of 3rd Conference on Innovations in Theoretical Computer Science (ITCS 2012), 2012. Available at CoRR and locally in pdf.
Alexandra Meliou, Wolfgang Gatterbauer, Joseph Y. Halpern, Christoph Koch, Katherine F. Moore, and Dan Suciu
Provenance is often used to validate data, by verifying its origin and explaining its derivation. When searching for ``causes'' of tuples in the query results or in general observations, the analysis of lineage becomes an essential tool for providing such justifications. However, lineage can quickly grow very large, limiting its immediate use for providing intuitive explanations to the user. The formal notion of causality is a more refined concept that identifies causes for observations based on user-defined criteria, and that assigns to them gradual degrees of responsibility based on their respective contributions. In this paper, we initiate a discussion on causality in databases, give some simple definitions, and motivate this formalism through a number of example applications.
In IEEE Data Engineering Bulletin 33:3, 2010, pp. 59-67. Available locally in pdf.
General cognitive principles for learning structure in time and space
Michael Goldstein, Heidi Westerfall, Arnon Lotem, Joseph Y. Halpern, Jennifer A. Schwade, Luca Onnis, and Shimon Edelman
How are hierarchically structured sequences of objects, events or actions learned from experience and represented in the brain? When several streams of regularities present themselves, which will be learned and which ignored? Can statistical regularities take effect on their own, or are additional factors such as behavioral outcomes expected to influence statistical learning? Answers to these questions are starting to emerge through a convergence of findings from naturalistic observations, behavioral experiments, neurobiological studies, and computational analyses and simulations. We propose that a small set of principles are at work in every situation that involves learning of structure from patterns of experience and outline.
In Trends in Cognitive Science
Reasoning about justified belief
Adam Bjorndahl, Joseph Y. Halpern, and Rafael Pass
Halpern and Pass introduce a logic of justified belief and go on to prove that strong rationalizability is characterized in this logic in terms of common justified belief of rationality (CJBR). Their paper provides semantics for this logic but no axiomatization. We correct this deficiency by reformulating the definition of justified belief and providing a complete axiomatization of this new system. We then prove a result analogous to the characterization of strong rationalizability in terms of CJBR, and analyze the additional assumptions needed to do so.
In Proceedings of Thirteenth Conference on Theoretical Aspects of Rationality and Knowledge, 2011, pp. 221-227; the full paper is available in pdf.
Ambiguous language and differences in beliefs
Joseph Y. Halpern and Willemien Kets
Standard models of multi-agent modal logic do not capture the fact that information is often ambiguous, and may be interpreted in different ways by different agents. We propose a framework that can model this, and consider different semantics that capture different assumptions about the agents' beliefs regarding whether or not there is ambiguity. We consider the impact of ambiguity on a seminal result in economics: Aumann's result saying that agents with a common prior cannot agree to disagree. This result is known not to hold if agents do not have a common prior; we show that it also does not hold in the presence of ambiguity. We then consider the tradeoff between assuming a common interpretation (i.e., no ambiguity) and a common prior (i.e., shared initial beliefs).
In Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), 2012, pp. 329-338. The conference version is available in pdf. The conference version was expanded and then split into two papers: "A logic for reasoning about ambiguity" and "Ambiguous language and common priors".
I'm doing as well as I can: modeling people as rational finite automata
Joseph Y. Halpern, Rafael Pass, and Lior Seeman
We show that by modeling people as bounded finite automata, we can capture at a qualitative level the behavior observed in experiments. We consider a decision problem with incomplete information and a dynamically changing world, which can be viewed as an abstraction of many real-world settings. We provide a simple strategy for a finite automaton in this setting, and show that it does quite well, both through theoretical analysis and simulation. We show that, if the probability of nature changing state goes to 0 and the number of states in the automaton increases, then this strategy performs optimally (as well as if it were omniscient and knew when nature was making its state changes). Thus, although simple, the strategy is a sensible strategy for a resource-bounded agent to use. Moreover, at a qualitative level, the strategy does exactly what people have been observed to do in experiments.
In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12), 2012, pp. 1917-1923. The paper is available here.
Joseph Y. Halpern and Samantha Leung
We consider a setting where an agent's uncertainty is represented by a set of probability measures, rather than a single measure. Measure-by-measure updating of such a set of measures upon acquiring new information is well-known to suffer from problems; agents are not always able to learn appropriately. To deal with these problems, we propose using weighted sets of probabilities: a representation where each measure is associated with a weight, which denotes its significance. We describe a natural approach to updating in such a situation and a natural approach to determining the weights. We then show how this representation can be used in decision-making, by modifying a standard approach to decision making---minimizing expected regret -- to obtain minimax weighted expected regret (MWER). We provide an axiomatization that characterizes preferences induced by MWER both in the static and dynamic case.
In Proceedings of the Twenty-Seventh Conference on Uncertainty in AI (UAI '2012). To appear, Theory and Decision. The full version of the paper is available here.
Co-evolution of learning and data-acquisition mechanisms: a model for cognitive evolution
Arnon Lotem and Joseph Y. Halpern
A fundamental and frequently overlooked aspect of animal learning is its reliance on compatibility between the learning rules used and the attentional and motivational mechanisms directing them to process the relevant data (called here data-acquisition mechanisms). We propose that this coordinated action, which may first appear fragile and error prone, is in fact extremely powerful, and critical for understanding cognitive evolution. Using basic examples from imprinting and associative learning, we argue that by coevolving to handle the natural distribution of data in the animal's environment, learning and data-acquisition mechanisms are tuned jointly so as to facilitate effective learning using relatively little memory and computation. We then suggest that this coevolutionary process offers a feasible path for the incremental evolution of complex cognitive systems, because it can greatly simplify learning. This is illustrated by considering how animals and humans can use these simple mechanisms to learn complex patterns and represent them in the brain. We conclude with some predictions and suggested directions for experimental and theoretical work.
In Philosophical Transactions of the Royal Society 367, pp. 2686-2694. The paper is available locally and on the journal website.
Joseph Y. Halpern
In Kozen Festschrift, Lecture Notes in Computer Science, vol. 7230, Springer, 2012, pp. 324--325.
The paper is available here.
Algorithmic rationality: game theory with costly computation
Joseph Y. Halpern and 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 existence of a Nash equilibrium) no longer hold. Nevertheless, we can use the framework to provide psychologically appealing explanations of observed behavior in well-studied games (such as finitely repeated prisoner's dilemma and rock-paper-scissors). Furthermore, we provide natural conditions on games sufficient to guarantee that equilibria exist.
In Journal of Economic Theory 156, 2015, pp. 246--268. 2015. Available here.
A computational game-theoretic framework for cryptography
Joseph Y. Halpern and Rafael Pass
We develop a definition of protocol security relying on game-theoretic notions of implementation. We show that a natural special case of this this definition is equivalent to a variant of the traditional cryptographic definition of protocol security; this result shows that, when taking computation into account, the two approaches used for dealing with ``deviating'' players in two different communities -- Nash equilibrium in game theory and zero-knowledge ``simulation'' in cryptography -- are intimately related. Other special cases of our definition instead lead to more practical protocols and circumvent known lower bounds with respect to the cryptographic notion of security.
Unpublished manuscript, available here.
Distributed computing meets game theory: combining insights from two fields
Ittai Abraham, Lorenzo Alvisi, and Joseph Y. Halpern
This is a discussion of work that appears here and related work by Alvisi.
In ACM SIGACT News
Solution to Exchanges 8.1 puzzle: Identifying the champion
Stephane Airiau, Ulle Endriss, and Joseph Y. Halpern
In SIGECOM Exchanges 8.2, 2009, pp. 1-2. The paper can be found here.
Awareness in games, awareness in logic
Joseph Y. Halpern
This is a summary of an invited talk, which covers material from "Reasoning about knowledge of unawareness", "Reasoning about knowledge of unawareness revisited", and "Extensive games with possibly unaware players".
In Proceedings of LPAR-17 Lecture Notes in Computer Science, vol. 6397, Springer, 2010, p. 15.
Algorithmic rationality: Adding cost of computation to game theory
In SIGECOM Exchanges 10.2, 2011, pp. 9--15. The paper can be found here. This is a summary of work in A computational game-theoretic framework for cryptography and Algorithmic rationality: Adding cost of computation to game theory.
Joseph Y. Halpern and Christopher Hitchcock
This paper extends the account of actual causation offered by Halpern and Pearl. We show that this account yields the wrong judgment in certain classes of cases. We offer a revised definition that incorporates consideration of defaults, typicality, and normality. The revised definition takes actual causation to be both graded and comparative. We then apply our definition to a number of cases.
To appear, British Journal for the Philosophy of Science; available here.
Adam Bjorndahl, Joseph Y. Halpern, and Rafael Pass
We introduce language-based games, a generalization of psychological games [Geanakoplos, Pearce, and Stacchetti 1989] that can also capture reference-dependent preferences [Koszegi and Rabin 2006]. The idea is to extend the domain of the utility function to situations, maximal consistent sets in some language. The role of the underlying language in this framework is thus particularly critical. Of special interest arey languages that can express only coarse beliefs [Mullainathan 2002]. Despite the expressive power of the approach, we show that it can describe games in a simple, natural way. Nash equilibrium and rationalizability are generalized to this setting; Nash equilibrium is shown not to exist in general, while the existence of rationalizable strategies is proved under mild conditions.
In Proceedings of Fourteenth Conference on Theoretical Aspects of Rationality and Knowledge, 2013, pp. 39--48; the full paper is available here.
Game theory with translucent players
Joseph Y. Halpern and Rafael Pass
A traditional assumption in game theory is that players are opaque to one another---if a player changes strategies, then this change in strategies does not affect the choice of other players' strategies. In many situations this is an unrealistic assumption. We develop a framework for reasoning about games where the players may be translucent to one another; in particular, a player may believe that if she were to change strategies, then the other player would also change strategies. Translucent players may achieve significantly more efficient outcomes than opaque ones. Our main result is a characterization of strategies consistent with appropriate analogues of common belief of rationality. Common Counterfactual Belief of Rationality (CCBR) holds if (1) everyone is rational, (2) everyone counterfactually believes that everyone else is rational (i.e., all players i believe that everyone else would still be rational even if i were to switch strategies), (3) everyone counterfactually believes that everyone else is rational, and counterfactually believes that everyone else is rational, and so on. CCBR characterizes the set of strategies surviving iterated removal of minimax dominated strategies, where a strategy s is minimax dominated for i if there exists a strategy s' such that the worst possible utility for s' (taken over all strategy profiles for the other players) is better than the best possible utility for s.
In Proceedings of Fourteenth Conference on Theoretical Aspects of Rationality and Knowledge, 2013, pp. 216--221. The full paper is available here.
Compact representations of extended causal models
Joseph Y. Halpern and Christopher Hitchcock
Judea Pearl was the first to propose a definition of actual causation using causal models. A number of authors have suggested that an adequate account of actual causation must appeal not only to causal structure, but also to considerations of normality. In related work, we offer a definition of actual causation using extended causal models, which include information about both causal structure and normality. Extended causal models are potentially very complex. In this paper, we show how it is possible to achieve a compact representation of extended causal models.
In Cognitive Science 37:6, pp. 986-1010, 2013. The full paper is available here.
Weighted regret-based likelihood: a new approach to describing uncertainty
Joseph Y. Halpern
Recently, Halpern and Leung [2012] suggested representing uncertainty by a weighted set of probability measures, and suggested a way of making decisions using this representation of uncertainty: maximizing weighted regret. Their paper leaves does not answer an apparently simpler question: what it means, according to this representation of uncertainty, for an event E to be more likely than an event E'. In this paper, a notion of comparative likelihood when uncertainty is represented by a weighted set of probability measures is defined. It generalizes the ordering defined by probability (and by lower probability) in a natural way; a generalization of upper probability can also be defined. A complete axiomatic characterization of this notion of regret-based likelihood is given.
In 12th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU), 2013, pp. 266--277. The full paper is available here.
Distributed protocols for leader election: a game-theoretic perspective
Ittai Abraham, Danny Dolev, and Joseph Y. Halpern
We do a game-theoretic analysis of leader election, under the assumption that each agent prefers to have some leader than to have no leader at all. We show that it is possible to obtain a fair Nash equilibrium, where each agent has an equal probability of being elected leader, in a completely connected network, in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In the asynchronous setting, Nash equilibrium is not quite the right solution concept. Rather, we must consider ex post Nash equilibrium; this means that we have a Nash equilibrium no matter what a scheduling adversary does. We show that ex post Nash equilibrium is attainable in the asynchronous setting in all the networks we consider, using a protocol with bounded running time. However, in the asynchronous setting, we require that n > 2. We can get a fair ε-Nash equilibrium if n = 2 in the asynchronous setting, under some cryptographic assumptions (specifically, the existence of a pseudo-random number generator and polynomially-bounded agents), using ideas from bit-commitment protocols. We then generalize these results to a setting where we can have deviations by a coalition of size k. n > 2k; under the same cryptographic assumptions, we can a get a k-resilient equilibrium if n=2k. Finally, we show that, under minimal assumptions, not only do our protocols give a Nash equilibrium, they also give a sequential equilibrium, so players even play optimally off the equilibrium path.
In Proceedings of the 27th International Symposium on Distributed Computing, 2013, pp. 61-75. The full paper is available here.
Sequential equilibrium in computational games
Joseph Y. Halpern and Rafael Pass
We examine sequential equilibrium in the context of computational games [Halpern and Pass, 2011a], where agents are charged for computation. In such games, an agent can rationally choose to forget, so issues of imperfect recall arise. In this setting, we consider two notions of sequential equilibrium. One is an ex ante notion, where a player chooses his strategy before the game starts and is committed to it, but chooses it in such a way that it remains optimal even off the equilibrium path. The second is an interim notion, where a player can reconsider at each information set whether he is doing the ``right'' thing, and if not, can change his strategy. The two notions agree in games of perfect recall, but not in games of imperfect recall. Although the interim notion seems more appealing, Halpern and Pass [2011b] argue that there are some deep conceptual problems with it in standard games of imperfect recall. We show that the conceptual problems largely disappear in the computational setting. Moreover, in this setting, under natural assumptions, the two notions coincide.
In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013)}, 2013, pp. 171--176. The full paper is available here.
Towards a deeper understanding of cooperative equilibrium: characterization and complexity
Nan Rong and Joseph Y. Halpern
Nash equilibrium (NE) assumes that players always make a best response. However, this is not always true; sometimes people cooperate even it is not a best response to do so. For example, in the Prisoner's Dilemma, people often cooperate. We consider two solution concepts that were introduced recently that try to capture such cooperation in two-player games: perfect cooperative equilibrium (PCE) (and an extension called maximum PCE (M-PCE)) [Halpern and Rong, 2010] and the coco value [Kalai and Kalai, 2009]. We show that, despite their definitions being quite different, these notions are closely related, both in terms of axiomatization and algebraic characterization. We also consider the problem of computing how well players do when they cooperate according to these solution concepts, and show that in both cases in polynomial time. In the case of the coco value, this follows easily from the definition; in the case of the corresponding M-PCE value, it follows from a theorem showing that bilinear programming for a class of 2x2 matrices is in constant time, a result that may be of independent interest.
In Proceedings of the Twelfth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), 2013, pp. 319--326. The paper is available here.
Decision theory with resource-bounded agents
Joseph Y. Halpern, Rafael Pass, and Lior Seeman
There have been two major lines of research aimed at capturing resource-bounded players in game theory. The first, initiated by Rubinstein [1985] charges an agent for doing costly computation; the second, initiated by Neyman [1985] does not charge for computation, but limits the computation that agents can do, typically by modeling agents as finite automata. We review recent work on applying both approaches in the context of decision theory. For the first approach, we take the objects of choice in a decision problem to be Turing machines, and charge players for the ``complexity'' of the Turing machine chosen (e.g., its running time). This approach can be used to explain well-known phenomena like first-impression-matters biases (i.e., people tend to put more weight on evidence they hear early on) and belief polarization (two people with different prior beliefs, hearing the same evidence, can end up with diametrically opposed conclusions) as the outcomes of quite rational decisions. For the second approach, we model people as finite automata, and provide a simple algorithm that, on a problem that captures a number of settings of interest, provably performs optimally as the number of states in the automaton increases.
In Topics in Cognitive Science 6:2, 2014, pp. 245-257. The paper can be found here. This paper covers material in "I don't want to think about it now: decision theory with costly computation" and "I'm doing as well as I can: modeling people as rational finite automata".
The truth behind the myth behind the folk theorem
Joseph Y. Halpern, Rafael Pass, and Lior Seeman
We study the problem of computing an ε-Nash equilibrium in repeated games. Earlier work by Borgs et al. [2010] suggests that this problem is intractable. We show that if we make a slight change to their model---modeling the players as polynomial-time Turing machines that maintain state (rather than stateless polynomial-time Turing machines)---and make some standard cryptographic hardness assumptions (the existence of public-key encryption), the problem can actually be solved in polynomial time.
In Proceedings of 5th Conference on Innovations in Theoretical Computer Science (ITCS 2014), 2014. Available at CoRR and locally.
Appropriate causal models and stability of causation
Joseph Y. Halpern
Causal models defined in terms of structural equations have proved to be quite a powerful way of representing knowledge regarding causality. However, a number of authors have given examples that seem to show that the Halpern-Pearl [2005] (HP) definition of causality gives intuitively unreasonable answers. Here it is shown that, for each of these examples, we can give two stories consistent with the description in the example, such that intuitions regarding causality are quite different for each story. By adding additional variables, we can disambiguate the stories. Moreover, in the resulting causal models, the HP definition of causality gives the intuitively correct answer. It is also shown that, by adding extra variables, a modification to the original HP definition made to deal with an example by Hopkins and Pearl [2003] may not be necessary. Given how much can be done by adding extra variables, there might be a concern that the notion of causality is somewhat unstable. Can adding extra variables in a ``conservative'' way (i.e., maintaining all the relations between the variables in the original model) cause the answer to the question ``Is X=x a cause of Y=y?'' to alternate between ``yes'' and ``no''? Here it is shown that adding an extra variable can change the answer from ``yes' to ``no'', but after that, it cannot cannot change back to ``yes''.
In Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2014), 2014. The full paper is available here.
Adam Bjorndahl, Joseph Y. Halpern, and Rafael Pass
We provide a sound and complete axiomatization for a class of logics appropriate for reasoning about the rationality of players in games. Essentially the same axiomatization applies to a wide class of decision rules.
In Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR 2014), 2014. Available here.
The role of the protocol in anthropic reasoning
Joseph Y. Halpern
It is shown how thinking in terms of the protocol used can help clarify problems related to anthropic reasoning, such as the Doomsday Argument and the Sleeping Beauty Problem. To appear, Ergo. Available here.
A logic for reasoning about ambiguity
Joseph Y. Halpern and Willemien Kets
Standard models of multi-agent modal logic do not capture the fact that information is often ambiguous, and may be interpreted in different ways by different agents. We propose a framework that can model this, and consider different semantics that capture different assumptions about the agents' beliefs regarding whether or not there is ambiguity. We examine the expressive power of logics of ambiguity compared to logics that cannot model ambiguity, with respect to the different semantics that we propose.
In Artificial Intelligence 209, pp. 1-10, 2014. Available in pdf. Some of the material in this paper appeared in preliminary form in "Ambiguous language and differences of belief"
Ambiguous language and common priors
Joseph Y. Halpern and Willemien Kets
Standard economic models cannot capture the fact that information is often ambiguous, and is interpreted in multiple ways. Using a framework that distinguishes between the language in which statements are made and the interpretation of statements, we show that ambiguity can have important consequences. We show that players can agree to disagree in the presence of ambiguity, even if there is a common prior, but that allowing for ambiguity is more restrictive than assuming heterogeneous priors. We also demonstrate that, unlike in the case where there is no ambiguity, players may come to have different beliefs starting from a common prior, even if they have received exactly the same information, unless the information is common knowledge. Taken together, these results suggest that ambiguity provides a potential explanation for heterogeneous beliefs. At the same time, it imposes nontrivial restrictions on the situations that can be modeled, so that it is not the case that ``anything goes'' once we allow for ambiguous statements.
To appear, Games and Economic Behavior. Available in pdf. Some of the material in this paper appeared in preliminary form in Ambiguous language and differences of belief
A procedural characterization of solution concepts in games
Joseph Y. Halpern and Yoram Moses
We show how game-theoretic solution concepts such as Nash equilibrium, correlated equilibrium, rationalizability, and sequential equilibrium can be given a uniform definition in terms of a knowledge-based program. In a precise sense, this program can be viewed as providing a procedural characterization of rationality.
In Journal of AI Research
Characterizing solution concepts in terms of common knowledge of rationality
Joseph Y. Halpern and Yoram Moses
Characterizations of Nash equilibrium, correlated equilibrium, and rationalizability in terms of common knowledge of rationality are well known. We show how to get analogous characterizations of sequential equilibrium and (trembling hand) perfect equilibrium, as a consequence of recent results of Halpern.
The paper can be found here.
The computational complexity of structure-based causality
Gadi Aleksandrowicz, Hana Chockler, Joseph Y. Halpern, and Alexander Ivrii
Halpern and Pearl introduced a definition of actual causality; Eiter and Lukasiewicz showed that computing whether X=x is a cause of Y=y is NP-complete in binary models (where all variables can take on only two values) and Σ^{P}_{2}-complete in general models. In the final version of their paper, Halpern and Pearl slightly modified the definition of actual cause, in order to deal with problems pointed by Hopkins and Pearl.As we show, this modification has a nontrivial impact on the complexity of computing actual cause. To characterize the complexity, a new family D^{P}_{k}, k = 1, 2, 3, ..., of complexity classes is introduced, which generalizes the class D^{P} introduced by Papadimitriou and Yannakakis (D^{P} is just D^{P}_{1}). We show that the complexity of computing causality under the updated definition is D^{P}_{2}-complete. Chockler and Halpern extended the definition of causality by introducing notions of responsibility and blame. The complexity of determining the degree of responsibility and blame using the original definition of causality was completely characterized. Again, we show that changing the definition of causality affects the complexity, and completely characterize it using the updated definition.
In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14), 2014. The paper is available here.
Alfredo Di Tillio, Joseph Y. Halpern, and Dov Samet
We study type spaces where a player's type at a state is a conditional probability on the space. We axiomatize these spaces using conditional belief operators, examining three additional axioms of increasing strength. First, introspectionM, which requires the agent to be unconditionally certain of her beliefs. Second, echo, according to which the unconditional beliefs implied by the condition must be held given the condition. Third, <\em>determination, which says that the conditional beliefs are the unconditional beliefs that are conditionally certain. Echo implies that conditioning on an event is the same as conditioning on the event being certain, which formalizes the standard informal interpretation of conditional probability. The game-theoretic application of our model, discussed within an example, sheds light on a number of issues in the analysis of extensive form games. Type spaces are closely related to the sphere models of counterfactual conditionals and to models of hypothetical knowledge.
Games and Economic Behavior 87, 2014, pp. 253-268. The paper can be found here.
An introduction to logics of knowledge and belief
Hans van Ditmarsch, Joseph Y. Halpern, Wiebe van der Hoek, and Barteld Kooi
This is the introductory chapter of the Handbook of Epistemic Logic It provides an introduction to some basic concepts of epistemic logic, basic formal languages, their semantics, and proof systems. It also contains an overview of the handbook, and a brief history of epistemic logic and pointers to the literature.
In Handbook of Epistemic Logic (H. van Ditmarsch, J. Y. Halpern, W. van der Hoek, and B. Kooi, editors), College Publications, 2015, pp. 1--51. Available here.
An equilibrium analysis of scrip systems
Ian A. Kash, Joseph Y. Halpern, and Eric J. Friedman
A game-theoretic model of scrip (artificial currency) systems is analyzed. It is shown that relative entropy can be used to characterize the distribution of agent wealth when all agents use threshold strategies -- that is, they volunteer to do work iff they have below a threshold amount of money. Monotonicity of agents' best-reply functions is used to show that scrip systems have pure strategy equilibria where all agents use threshold strategies. An algorithm is given that can compute such an equilibrium and the resulting distribution of wealth.
Material from "Efficiency and Nash equilibria in a scrip system for P2P networks", the conference version of "Optimizing scrip systems: efficiency, crashes, hoarders, and altruists", and "Manipulating scrip systems: sybils and collusion" was combined and then split into two journal papers. This is one of them; the other is here. The paper is available here.
Updating probability: tracking statistics as criterion
Bas van Fraassen and Joseph Y. Halpern
What is generally called Bayesian Conditionalization is a policy for updating probability assignments. It specifies as admissible input (“evidence”) elements of the domain of the prior probability function, and allows as possible posteriors the conditionalizations on such elements (“propositions”). Under certain ideal conditions, this is the only coherent policy. When those conditions are not met, other policies might be appropriate. Putative examples would involve updating by Richard Jeffrey’s generalized conditionalization ("Jeffrey Conditionalization'') or Edwin T. Jaynes' rule to maximize relative entropy ("MAXENT"). This raises the question of what general constraints any such policy should satisfy. We propose an answer here.
To appear British Journal for the Philosophy of Science. The paper is available here.
Cause, responsibility, and blame: a structural-model approach
Joseph Y. Halpern
A definition of causality introduced by Halpern and Pearl, which uses structural equations, is reviewed. A more refined definition is then considered, which takes into account issues of normality and typicality, which are well known to affect causal ascriptions. Causality is typically an all-or-nothing notion: either A is a cause of B or it is not. An extension of the definition of causality to capture notions of degree of responsibility and degree of blame, due to Chockler and Halpern, is reviewed. For example, if someone wins an election 11--0, then each person who votes for him is less responsible for the victory than if he had won 6--5. Degree of blame takes into account an agent's epistemic state. Roughly speaking, the degree of blame of A for B is the expected degree of responsibility of A for B, taken over the epistemic state of an agent. Finally, the structural-equations definition of causality is compared to Wright's NESS test.
To appear, Law, Probability, and Risk. This paper is meant to be a gentle introduction to some of my work on causality, particularly that in "Causes and explanations: a structural-model approach. Part I: Causes", "Responsibility and blame: A structural-model approach", and, to a lesser extent "Actual causation and the art of modeling", and "Defaults and normality in causal structures". The paper is available here.
Not just an empty threat: subgame-perfect equilibrium in repeated games played by computationally bounded players
Joseph Y. Halpern, Rafael Pass, and Lior Seeman
We study the problem of finding a subgame-perfect equilibrium in repeated games. In earlier work, we showed how to efficiently find an (approximate) Nash equilibrium if assuming that players are computationally bounded (and making standard cryptographic hardness assumptions); in contrast, as demonstrated in the work of Borgs et al. [2010], unless we restrict to computationally bounded players, the problem is PPAD-hard. But it is well-known that for extensive-form games (such as repeated games), Nash equilibrium is a weak solution concept. In this work, we define and study an appropriate notion of a subgame-perfect equilibrium for computationally bounded players, and show how to efficiently find such an equilibrium in repeated games (again, making standard cryptographic hardness assumptions). We also show that our algorithm works not only for games with a finite number of players, but also for constant-degree graphical games.
In Proceedings of WINE 2014: 10th Conference on Web and Internet Economics, 2014, pp. 249--262. The paper is available here.