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
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 Microcumpters, 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. Raymod 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 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'', oceedings 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. Addinge 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.
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 artilce; 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
Tha advantages of denotational over operational semantics are argued. A denotational semantics is provded for an ALGOL-like language with finite-mode procedures, blocks with local storage, and sharing (aliasing). Porcedure 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 Semioxtics 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
Fracis 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 Procedings 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.
To appear, Games and Economic Behavior. A preliminary version
appears in Proceedings of the Eighth Conference on Theoretical
Aspects
of Rationality and Knowledge, 2001, pp. 17-30. The paper is
available
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 Proceedings Formal Aspects of Security, 2003.
The paper is available in at CoRR
and locally in
postscript and pdf.
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 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 apears 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 Reaoning 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 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
postscript and
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.
To appear in Synthese. A preliminary version appears
in Proceedings of Twenty-First Conference on Uncertainty in
AI, 2005, pp. 243-250. The full paper is available
at CoRR
and locally in
postscript and pdf.
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.
To appear, Games and Economic Behavior. 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 paper is available
at CoRR
and locally in
postscript and
pdf.
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.
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.
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.
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
postscript and
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.
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 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 Proceedings of the Eighth ACM
Conference on Electronic Commerce, 2007, pp. 305-315. Available
at CoRR
and locally in postscript and
pdf.
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 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 Quantative
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 Proceedings of
Eleventh Conference on Theoretical Aspects of Rationality and Knowledge,
2007, pp. 253-262. The full paper is available
at CoRR
and locally in
postscript and pdf.
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
infinitesmimal, 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.
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 Proceedings of the 27th
Annual ACM Symposium on Principles of Distributed Computing, 2008,
pp. 1-10;
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.
A game-theoretic analysis of updating sets of
probabilities
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.
In Proceedings of the Twenty-Fourth Conference on Uncertainty in
AI, 2008, pp. 240-247.
The paper is available
at CoRR
and locally in
postscript and pdf.
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 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 Proceedings of
the 21st International Joint Conference on Artificial Intelligence
(IJCAI 2009), 2009. The full paper is available in postscript and
pdf.
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
%the 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
connected.
Unpublished manuscript; available in postscript and
pdf.
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 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 Proceedings of the Eighth International Joint Conference on
Autonomous Agents and Multiagent Systems (AAMAS), 2009,
pp. 765-772. Available
at CoRR
and locally in
in postscript and pdf.
Manipulating scrip systems:
sybils and collusion
Ian 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.
To appear, Review of Symbolic Logic; available in postscript and
pdf.
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.
To appear, Review of Symbolic Logic; available in postscript and
pdf.
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 charaacterization of iterated admisibility
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.
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 Proceedings of Twelfth Conference on Theoretical Aspects of
Rationality and Knowledge, 2009, pp. 166-173; the full paper is
available at CoRR and
locally in postscript and
pdf.
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.
Ian Kash, Eric J. Friedman, and Joseph Y. Halpern
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.
The tools we use in the analysis give us techniques for analyzing the
effects of and dealing with hoarders, altruists, sybils, and collusion,
as well as techniques for inferring the characteristics of agents in a
system can be inferred from the equilibrium distribution of money.
This combines our earlier work on scrip systems (see
here,
here,
and here). Available in
locally in postscript and pdf.
Earlier protocols have achieved only two of these three
properties. In particular, the protocol of Bracha is not polynomially
efficient, the protocol of Feldman and Micali is not optimally
resilient, and the protocol of Canetti and Rabin does not have
almost-sure termination. Our protocol utilizes a new primitive called
shunning (asynchronous) verifiable secret sharing
(SVSS), which ensures,
roughly speaking, that either a secret is successfully shared or a new
faulty process is ignored from this point onwards
by some nonfaulty process.