# 2000 Milner Lecture

## Knowledge and Common Knowledge

in Multi-Agent Systems

Joseph Halpern, Cornell University

Reasoning about knowledge -- what I know about what you know about what I know ... -- is the type of reasoning that is often seen in puzzles and paradoxes, and has been studied at length by philosophers. Recently, it has been shown to play a key role in a surprising number of other contexts, from understanding conversations to the analysis of distributed computer algorithms.

We can begin by considering a number of well-known puzzles and paradoxes, which both illustrate the subtleties of reasoning about knowledge and the advantages of having a good framework in which to make this reasoning precise. These puzzles also turn out to be closely related to important problems in distributed computing and game theory. In particular, they emphasize the importance of the notion of common knowledge, which turns out to be essential for reaching agreements and coordinating action. Unfortunately, we can prove that in practical multi-agent systems, common knowledge is not attainable. This seems somewhat paradoxical. How can common knowledge be both necessary and unattainable? The paradox gets resolved (to some extent) by examining a number of variants of common knowledge that turn out to be both attainable and sufficient for many applications.

Professor Halpern has for the last twenty years been one of the world's most productive researchers in the area of logic in computer science. His current work focuses on reasoning about knowledge and uncertainty, and its applications to distributed computing, Artificial Intelligence, and game theory.