Reasoning about knowledge, once the exclusive arena of philosophical investigation, has in the last two decades become an active field of research in a variety of scientific disciplines. These include artificial intelligence, economics, linguistics, philosophy and theoretical computer science. While the issues arising in the different disciplines share a significant degree of commonality, the separate communities pursued their respective research efforts fairly independently for quite a while. The First Conference on Theoretical Aspects of Reasoning about Knowledge (TARK I) was organized by Joe Halpern in 1986, with the goal of bringing together researchers from these fields to discuss issues of mutual interest. It was followed by TARK conferences in 1988, 1990, 1992, and 1994. This volume represents the program of TARK V, the fifth biennial conference in the series, which was held March 13-16, 1994. All five TARK conferences have been held at the lovely, peaceful campus of the Asilomar Conference Center in Pacific Grove, California. The TARK conferences have helped bring the interdisciplinary community attending this conference closer together.
The program committee consisted of Michael Dunn (Philosophy, Indiana University), Ronald Fagin (Computer Science, IBM Almaden Research Center), Itzhak Gilboa (Economics, Northwestern University), Robert Koons (Philosophy, University of Texas at Austin), Gerhard Lakemeyer (Artificial Intelligence, University of Bonn), Barton Lipman (Economics, Queen's University), Judea Pearl (Artificial Intelligence, UCLA), Brian Skyrms (Philosophy, University of California at Irvine), Mark Tuttle (Computer Science, DEC Cambridge Research Lab), and Lenore Zuck (Computer Science, Yale University). The program committee meeting was held October 23-24, 1993, in Los Gatos, California. The committee carefully considered all of the 83 papers submitted to the conference. Only 21 papers were selected for presentation. In addition, there were 2 invited papers, by Ken Binmore and by Hector Levesque.
This volume consists of extended abstracts of those 23 papers. We believe that this volume provides a good interdisciplinary selection of state of the art research on the topic of reasoning about knowledge. Despite the careful job done by the program committee, none of the extended abstracts appearing here was formally refereed, and it is expected that most of them will appear in more polished and complete form in refereed journals. I'd like to thank Karl Shell and Ehud Kalai, the general editors of the Journal of Economic Theory and of Games and Economic Behavior, respectively, for announcing that appearance of abstracts in the TARK V proceedings will not affect the publication of full length versions of these papers in their journals. This made it easier for economists to submit papers to the conference.
Grants to help support the conference were provided by the IBM Almaden Research Center, and by Prashant Parikh. Administrative support was provided by the DEC Cambridge Research Lab, the IBM Almaden Research Center, and the NEC Research Institute.
Proceeding Downloads
Knowledge, action, and ability in the situation calculus: extended abstract
The Cognitive Robotics group at the University of Toronto has been studying various aspects of the reasoning and representation problems involving action and change. The setting is that of a (currently simulated) autonomous robot for which we wish to ...
On the logic of iterated belief revision
We show in this paper that the AGM postulates are too weak to ensure the rational preservation of conditional beliefs during belief revision, thus permitting improper responses to sequences of observations. We remedy this weakness by augmenting the AGM ...
Backwards forward induction
In this paper we isolate a particular refinement of the notion of Nash equilibrium that is characterized by (<i>i</i>) the fact that it provides a unified framework for both backwards and forward induction; and (<i>ii</i>) by the fact that it is ...
A knowledge-based framework for belief change part I: foundations
We propose a general framework in which to study belief change. We begin by defining belief in terms of knowledge and plausibility: an agent believes ϕ if he knows that ϕ is true in all the worlds he considers most plausible. We then consider some ...
Information acquisition from multi-agent resources
Rational agents, information systems and knowledge bases all share the property that they may become more effective by combining information from multiple sources. However, as was clearly indicated by the notorious "Judge puzzle" proposed by W. J. ...
Consistent belief reasoning in the presence of inconsistency
Since everything is a consequence of an inconsistency, classical logics are not useful in modeling the reasoning of an agent who has inconsistent beliefs. In this paper, we differentiate consistent beliefs from inconsistent beliefs. We propose two ...
Infinitary epistemic logic
It is known that a theory in S5-epistemic logic with several agents may have numerous models. This is because each such model specifies also what an agent knows about infinite intersections of events, while the expressive power of the logic is limited ...
An epistemic logic of situations: extended abstract
In this paper we present a first order epistemic logic that incorporates the essentially finite character of what is actually known by any knower. Our logic and language allows us to represent familiarity with individuals including individual ...
Actual truth, possible knowledge
F.B. Fitch is credited with a simple argument purporting to show that the verificationist claim: (Ver) Truth implies Knowability, leads to the unacceptable conclusion: Truth implies Knowledge.
Infinitely many resolutions of Hempel's paradox
What sorts of observations could confirm the universal hypothesis that all ravens are black? Carl Hempel proposed a number of simple and plausible principles which had the odd ("paradoxical") result that not only do observations of black ravens confirm ...
Rationality in the Centipede
The literature on refinements of Nash equilibirum is now generally acknowledged to have failed in its task of providing a viable equilibrium selection theory for games. Part of the reason for its failure lies in its shaky foundations as a theory of ...
Revising knowledge: a hierarchical approach
A tradition in economics seeks to explain behavior by identifying the underlying preferences which (in a given environment) generate that behavior. This approach was extended in the work of Savage [1954] to decision making under uncertainty. "Belief", ...
Case-based decision theory and knowledge representation
When we address the question of how should we represent knowledge, we should first ask ourselves what is there to know. It seems unarguable that "knowledge representation" should only deal with the representation of that which can be known.
An axiomatic approach to the logical omniscience problem
Standard models of knowledge have the unrealistic property that agents are logically omniscient in the sense that they know all logical implications of their information. While many nonstandard logics have been proposed to avoid this problem, none has ...
Autoepistemic logic and introspective circumscription
We investigate the relationship between two epistemic nonmonotonic formalisms: autoepistemic logic and introspective circumscription. Finitely axiomatized autoepistemic theories are shown to be equivalent to the propositional case of introspective ...
Knowledge as a tool in motion planning under uncertainty
Inspired by the success of the distributed computing community in applying logics of knowledge and time to reasoning about distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving ...
Common knowledge and update in finite environments. I: extended abstract
This paper studies the model checking problem for knowledge formulae in the S5<sub><i>n</i></sub> Kripke structures generated by finite state environments in which states determine an observation for each agent. Agents have perfect recall, and may ...
An epistemic proof system for parallel processes: extended abstract
A proof system for the correctness of parallel programs using knowledge in distributed systems is presented and proven sound and relatively complete with respect to a formal Kripke style semantics that supports truly concurrent computations.
Algorithmic knowledge
The standard model of knowledge in multi-agent systems suffers from what has been called the <i>logical omniscience problem:</i> agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this ...
Knowledge and the ordering of events in distributed systems: extended abstract
In asynchronous distributed systems logical time is usually interpreted as "possible causality", a partial order on event occurrences. We investigate the relationship between passage of time and changes in the knowledge of agents. We show that there is ...
Inductive learning, knowledge asymmetries and convention
In the classic passage quoted above, Hume observes that people are able to coordinate many of their activities without explicitly agreeing to coordinate, and he resolves this apparent paradox by explaining coordination in terms of individual ...
Coherent belief revision in games
What predictions about behavior in extensive form games can we rigorously justify as implied by rationality or mutual or common knowledge of that rationality?
Belief revision in a changing world
Several authors (Keller and Winslett 1985, Winslett 1988, Katsuno and Mendelzon 1989, Morreau and Rott 1991) have recently argued for a distinction in the way beliefs are updated with new information. They distinguish between information that tells the ...