Review of "A note on a generalization of the muddy children problem" by N. Gierasimczuk and J. Szymanik, TARK 13, 2011. Review #139441 in Computing Reviews, Sept. 9, 2011.

The "Muddy Children" problem, also known, more luridly, as the "Cheating Husbands" problem is a well-known puzzle in epistemic reasoning:

There are three children and a father. All three of the children have mud on their foreheads. They can each see the others' foreheads, but not their own. The father announces, "At least one of you has mud on your forehead." He then asks, three times, "Do you know whether you have mud on your own forehead?" The first two times he asks, all the children say "I do not know"; the third time he asks, all the children say "Yes, I have mud on my forehead." It is assumed that it is common knowledge among all the children that they are all perfect reasoners.

Gierasimczuk and Szymanik consider generalizations of this puzzle in which there are N children of whom M in fact have muddy foreheads, and the father announces "Q of you have muddy foreheads" where Q is a predicate over the numbers 0 to N. The father's announcement is thus true iff Q(M). Gierasimczuk and Symanik prove that the children can solve the puzzle iff additionally there exists L < M such that Q(L) is false. (There is an unfortunate typo in theorem 1: "L <= N", which would be vacuous, should be "L <= M"). They show that this condition is closly connected to Van Benthem's idea of an ``active'' quantifier.

The analysis of these kinds of puzzles generally, and of the Muddy Children puzzle in particular, occupy a fraction of the literature on epistemic reasoning that is altogether out of proportion to their actual importance. However, the paper is elegant, and the result is worth having.

One small suggestion: The paper sets up a model of linear size, in contrast to the models of exponential size that have been used in previous analyses. The authors list a number of reasons that this is possible. It seems to me that another important feature of the puzzle that makes this possible is that, for each of the children, the other children are divided into two categories --- those that see M muddy foreheads and those that see M-1 --- and within those categories, the children are interchangeable. If you consider a variant of the problem where each of the children is assigned a distinct, publically known large integer, and the father announces,"The sum of the muddy children is more than X" or something similar, then I suspect that one might well need a model of exponential size.