CS 6764: Reasoning About Knowledge - Fall 2018
- 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.
Announcements and Breaking News:
- 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.
Homework
Note: you can find your grades and solutions to the homework at
CMS.
Week 1: handed out 8/30; due 9/13 (hand it in 9/6 for a second chance)
- 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.
Week 2: handed out 9/6; due 9/20; hand it in 9/13 for a second
chance)
- 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).
Week 3: handed out 9/13; due 9/27; hand it in 9/20 for a second
chance)
- 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.
Week 4: handed out 9/20; due 10/4 (hand it in 9/27 for a second chance)
- Read Chapter 4
- Do 4.9, 4.18, 4.20
Week 5: handed out 9/27; due 10/11 (hand it in 10/4 for a second chance)
- 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!
Week 6: handed out 10/4; due 10/18 (hand it in 10/11 for a second chance)
- 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.)
Week 7: handed out 10/11; due 10/25 (hand it in 10/18 for a second chance)
- 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.
Week 8: handed out 10/18; due 11/1 (hand it in 10/25 for a second chance)
- Read Chapter 6
- Do 6.14, 6.16, 6.19, 6.23
Week 9: handed out 10/25; due 11/8 (hand it in 11/1 for a second chance)
- Read Chapter 7
- Do 7.3, 7.4, 7.7
Week 10: handed out 11/1; due 11/15 (hand it in 11/8 for a second chance)
- 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
Week 11: handed out 11/8; due 11/27 (hand it in 11/15 for a second chance)
- Read Chapter 9
- Do 9.22, 9.42, 9.45
- The slides on awareness that I used in classes on 11/8 can be found
here. The papers on which the lecture was based
can be found
here and
here. (These papers were written after the book was published.)
Week 12: handed out 11/15; due 11/29 (hand it in 11/27 for a second chance)
- 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!)
Week 13: no homework :-)
- 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.
Week 14: still no homework :-)
- 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.)