Course 9

Reasoning about Knowledge

Joseph Yehuda Halpern
Cornell University, USA
halpern@cs.cornell.edu

Abstract

Reasoning about knowledge – particularly the knowledge of agents who reason about the world and each other’s knowledge – was once the exclusive province of philosophers and puzzle solvers. More recently, this type of reasoning has been shown to play a key role in a surprising number of contexts, from understanding conversations to the analysis of distributed computer algorithms. This course provides a general discussion of approaches to reasoning about knowledge and its applications to distributed systems, artificial intelligence, and game theory. We’ll start by examining the well-known “muddy children puzzle”, which demonstrates the subtleties of reasoning about knowledge of a group. We then consider a simple yet powerful formal semantic model for knowledge and a language for reasoning about knowledge whose underlying idea is that of “possible worlds”. The rest of the course develops the model and show how it can be used to ascribe knowledge to agents in multi-agent systems. This allows us to better understand notions such as coordination and agreement. Depending on time and interest of the students, we will consider a notion of knowledge-based programs, a high-level tool for designing and analyzing systems, and/or modeling logical omniscience and resource-bounded reasoning, which has recently proved highly relevant in both security and game theory.