Reasoning About Knowledge

next up
Next: Reasoning About Uncertainty Up: Teaching Experience

Reasoning About Knowledge (CS 6764):
Course Description

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. The definitions lead naturally to a notion of knowledge-based programs, a high-level tool for designing and analyzing systems. One topic we focus on is logical omniscience and resource-bounded reasoning, which has recently proved highly relevant in both security and game theory.

The course follows closely the material in the book Reasoning About Knowledge, which actually was inspired by early versions of the course.