**Instructor:**Joe Halpern, 414 Gates, halpern@cs.cornell.edu, 5-9562**Admin:**Randy Hess, 401 Gates, rbhess@cs.cornell.edu, 5-0985;-
**TA:**Meir Friedenberg, 324 Gates, mdf224@cornell.edu **Classes:**Tuesday, Thursday 1:25 - 2:40, Goldwin Smith G24**Office hours:**TBD

**Text:**Reasoning About Knowledge (Fagin, Halpern, Moses, Vardi). (The paperback version is best, but the hardcover version is OK too. The paperback version corrects a number of typos and minor errors in the hardcover version.)**Grading:**There will be no tests or final examination. There will be problems handed out, typically 3 every Thursday, from the book. Your grade will be based completely on your performance on the problems. Problems are always due two weeks after they're handed out. If you hand them in one week after they're handed out, they will graded and returned the following week. You can then redo any problem that you seriously attempted and hand it in again, to improve your grade. On a redo, you can get a maximum of 1 point less than the original value of the problem. (That is, if the problem was originally out of 10, the most you can get is 9.) I will take the higher grade.**Academic Integrity:**It's OK to discuss the problems with others, but you**MUST**write up solutions on your own, and understand what you are writing.**Course Outline:**We will be following the text very closely. Very roughly, we will be covering one chapter per week. Topics include modal logic, common knowledge, applying reasoning about knowledge in distributed systems (and economics, depending on interest), knowledge-based programming, dealing with logical omniscience, algorithmic knowledge.

- Due to popular demand (well, one person asked nicely) we have a Piazza site for this course. That's a great place to post questions about homework and course material.c We'll try to monitor it reasonably carefully and respond within 24 hours. You can also respond to each other, of course.
- For this week, Meir will hold office hours after class on Tueday until 4 PM in Gates 324, and I'll hold office hours 1:30 - 2:30 on Wednesday in Gates 414. These times might change slightly in coming weeks, although office hours will be held on Tuesdays and Wednesdays (since homework is due on Thursdays).
- You can always hand in a hardcopy of your homework in class, but if you have a pdf of your work, Meir would prefer that you email it to ReasoningAboutKnowledge18FA@gmail.com.
- Update on office hours: for the next three weeks, I'll have office hours on Tuesday after class (until 4), and Meir will have them on Wednesdays. This week, it will be 5:30-7, but the time might change next week. Starting the week of October 1, we'll have regular office hours: Meir's will be Tuesday, 10 - 11:30 AM, and mine will be Wednesday 1:30 - 2:30. If those times don't work for you, send an email to me or Meir and we'll work something out. Also, don't forget that you can post questions on Piazza!
- Another update of office hourse (Sept. 13): Next week, there will be no office hours on Wednesday; instead, Meir will have office hours on Monday 2 - 3;30. The following two Wednesdays (Sept. 26 and Oct. 3), Meir will have office hours 3;30 - 5. For the next 3 weeks (i.e., Sept. 18, Sept. 25, and Oct. 2), I'll have office hours Tuesday after class (until 4). Starting Oct. 9, we'll revert to a regular schedule of Meir having office hours Tuesday 10-11:30 and me having office 1:30 - 2:30.

- Read Chapters 1 and 2.
- Do 1.2, 2.4, 2.11. (If you have the hardcover version of the text, ignore the comment in part 2.4(d) about edges disappearing; this comment does not appear in the paperback version (for good reason).)
- If you haven't gotten a copy of the text, Chapters 1 and 2 can be found here.

- Read Chapters 3.1 and 3.2
- Do 2.9, 2.12, 3.10, and 3.14. For 2.12 I want a semantic proof. Don't use the axioms. Rather, you should do proofs in the style of the other proofs in Chapter 2, where you talk about what formulas are true at various states. You can assume that the \K_i relations are equivalence relations, because that's what's assumed in Chapter 2. On the other hand, for 3.10(b), (c) and 3.14, I want a syntactic proof. That is, you should show explicitly how the relevant formulas are derivable from the axioms (without appealing to any of the soundness and completeness theorems).

- Read Chapter 3.
- Do 3.13(c), (d),(e), 3.17, 3.20. (I did 3.13(c) iin class, but it's a good exercise to write out.)
- Read (but don't hand in) 3.16.

- Read Chapter 4
- Do 4.9, 4.18, 4.20

- Read Chapter 4
- Do 4.24, 4.25, and the problem here. (This is the problem discussed in class; it turns out the converse is indeed true.) (Warning: some of these problems require thought. Don't leave them to the last minute!) Note that there is a typo in 4.24. On line 4 of p.156, it should say r(m'-k), not r(m-k). A complete list of known typos can be found here. If you find any other errors, let me know!

- Read Chapter 5 and 6.1--6.2
- Do 4.28 and 6.2. (This is a relatively short homework, in light of fall break.)

- Read Chapter 6.3--6.4
- Do 6.6, 6.8, 6.13
- The Ariel Rubinstein paper that I talked about in the last class can be found here. The paper is short and fun to read. I strongly encourage you to take a look.

- Read Chapter 6
- Do 6.14, 6.16, 6.19, 6.23

- Read Chapter 7
- Do 7.3, 7.4, 7.7

- Read Chapter 8.1., 8.2, 9.1-9.3 (I didn't cover 8.3 and 8.4, but you're encouraged to read it!)
- Do 8.5, 8.9, 9.8, 9.14
- Here is a fun puzzle in case you're getting bored. You should be able to solve it easily using Kripke structures!
- And if that was too easy for you, here is a more challenging version

- Read Chapters 10 and 11
- Do 9.49 [5 points], 10.3 [5 points], 11.2; also show that every a.m.p and every a.r.m.p has temporal imprecision, using the updated definition of temporal imprecision (see the Piazza post).
- This is the last homework!
- If you're into challenging puzzles, here are two hard variants of
the muddy children puzzle that my son passed along (he heard it in a
topology course he's taking now):
- Suppose that there are finitely many children. There is no father. Instead the children just look at each other and have to say whether or not they have mud on their foreheads. They can can agree the night before (before they see who has mud) on a protocol. Is there a protocol that guarantees that with nontrivial probability (better than $1/2^n$ if there are $n$ children) that they all get the right answer? What's the highest probability that can be achieved?
- Now suppose that there are infinitely many children, but otherwise the setup is the same as above. Give a protocol that guarantees that all but finitely many children get the right answer. (Technically, this requires the axiom of choice. If you don't know what that is, don't worry about it. You won't realize that you're using it!)

- The slides for the material on blockchain are here. The paper on this work can be found here here. The paper that introduced agent-relative knowledge is here. A paper applying these ideas to game theory (specifically, the problem of agreeing to disagree) is here.
- The slides for the material on substative rationality discussed in Thursday's class are here. The paper on this work is here.

- The slides for adding counterfactuals to distributed
cmoputing are
here. The paper on which the talk was
based is
here.
The absent-minded driver paradox and other
paradoxes of imperfect recall was introduced by Piccione and
Rubinstein,
in this
paper. There was a whole issue of the
journal
*Games and Economic Behavior*devoted to responses to that paper. Here is my response that appeared in that special issue. (If you're interested in the topic, let me know. I've written other more recent papers on it too.)