Computing Reviews

A note on a generalization of the muddy children puzzle
Gierasimczuk N., Szymanik J.  TARK XIII (Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, Groningen, the Netherlands, Jul 12-14, 2011)257-264,2011.Type:Proceedings
Date Reviewed: 09/09/11

The muddy children problem--more luridly known as the cheating husbands problem--is a well-known puzzle in epistemic reasoning.

In the problem, 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 the following question three times: “Do you know whether you have mud on your own forehead?” The first two times he asks, all of the children say, “I do not know”; the third time he asks, all of the children say, “Yes, I have mud on my forehead.” It is assumed that it is common knowledge among all of the children that they are all perfect reasoners.

The authors consider generalizations of this puzzle. For example, of n children, m in fact have muddy foreheads. The father announces, “The number with muddy foreheads satisfies Q,” where Q is a predicate over the numbers zero to n. The father’s announcement is thus true if and only if Q(m). They prove that the children can solve the puzzle if and only if additionally there exists ℓ < m such that Q() is false. (There is an unfortunate typo in Theorem 1: “n,” which would be vacuous, should be “ < m.”) They show that this condition is closely connected to van Benthem’s idea of an active quantifier.

Generally, the analysis of these kinds of puzzles, and of the muddy children puzzle in particular, occupies a fraction of the literature on epistemic reasoning that is altogether out of proportion to its actual importance. The paper is elegant, however, and the result is worth having.

I have one small suggestion. The paper sets up a model of linear size, in contrast to the models of exponential size that previous analyses have used. The authors list a number of reasons why 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 with muddy foreheads, and those with clean foreheads. Within those categories, the children are interchangeable. If you consider a variant of the problem where each child is assigned a distinct, publicly 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.

Reviewer:  Ernest Davis Review #: CR139441 (1204-0402)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy