The 2000 Milner Lecture
Knowledge and Common Knowledge
in Multi-Agent Systems
Joseph Halpern
Cornell University
4.00 pm 24 May 2000Law Lecture Theatre 183
Old College, South Bridge, Edinburgh
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. |
This is a public lecture, open to all, and will be followed by a reception at 5pm in the University Conference and Training Centre, 15 South College Street. Please tell Dyane McGavin if you intend to come to the reception. This is one of a range of events comprising the University of Edinburgh Informatics Jamboree, 24-26 May 2000.
The annual Milner Lecture was founded by a donation from Robin Milner "to keep a live connection between theory and application in computer science".