Induction puzzles are logic puzzles, which are examples of multi-agent reasoning, where the solution evolves along with the principle of induction. A puzzle's scenario always involves multiple players with the same reasoning capability, who go through the same reasoning steps. According to the principle of induction, a solution to the simplest case makes the solution of the next complicated case obvious. Once the simplest case of the induction puzzle is solved, the whole puzzle is solved subsequently. Typical tell-tale features of these puzzles include any puzzle in which each participant has a given piece of information (usually as common knowledge) about all other participants but not themselves. Also, usually, some kind of hint is given to suggest that the participants can trust each other's intelligence — they are capable of theory of mind (that "every participant knows modus ponens" is common knowledge). Also, the inaction of a participant is a non-verbal communication of that participant's lack of knowledge, which then becomes common knowledge to all participants who observed the inaction. The muddy children puzzle is the most frequently appearing induction puzzle in scientific literature on epistemic logic. Muddy children puzzle is a variant of the well known wise men or cheating wives/husbands puzzles. Hat puzzles are induction puzzle variations that date back to as early as 1961. In many variations, hat puzzles are described in the context of prisoners. In other cases, hat puzzles are described in the context of wise men.
Muddy Children Puzzle
Description A group of attentive children is told that some of them have muddy faces. Each child can see the faces of the others, but cannot tell if his or her own face is muddy. The children are told that those with muddy faces must step forward, but any child with a clean face who steps forward will be punished. At the count of three, every child who believes that his or her face is muddy must step forward simultaneously; any child who signals to another in any way will be punished. If any child with a muddy face has not stepped forward, the process will be repeated. At a given iteration, all muddy children and only them step forward. What is their thought process and on which turn does it happen?
Logical solution Assuming that each child has—and knows each of the others to have—perfect logic all children with muddy faces ( X {\displaystyle X} ) will step forward together on turn X {\displaystyle X} . The children have different information, depending on whether their own face is muddy or not. Each member of X {\displaystyle X} sees X − 1 {\displaystyle X-1} muddy faces, and knows that those children will step forward on turn X − 1 {\displaystyle X-1} if they are the only muddy faces. When that does not occur, each member of X {\displaystyle X} knows that he or she is also a member of X {\displaystyle X} , and steps forward on turn X {\displaystyle X} . Each non-member of X {\displaystyle X} sees X {\displaystyle X} muddy faces, and will not expect anyone to step forward until at least turn X {\displaystyle X} . Assume there are two children, Alice and Bob, and that only Alice is muddy ( X = 1 {\displaystyle X=1} ). Alice knows that "some" children have muddy faces but that nobody else's face is muddy, meaning that her own face must be muddy and she steps forward on turn one. Bob, seeing Alice's muddy face, has no way of knowing on turn one if his own face is muddy or not so he does not step forward for fear of punishment (only after Alice having stepped forward and the game being ended does Bob understand that his face must be clean). If both Alice and Bob are dirty ( X = 2 {\displaystyle X=2} ), each is in the position of Bob when X = 1 {\displaystyle X=1} : neither dare step forward on turn one. However, by turn two Bob knows that Alice must have seen that his face is muddy (because she did not step forward on turn one), and so he steps forward on turn two. Using the same logic, Alice also steps forward on turn two. Assume that there is a third child, Charlie. If only Alice is muddy ( X = 1 {\displaystyle X=1} ), she will see no muddy faces and will step forward on turn one. If both Alice and Bob are muddy ( X = 2 {\displaystyle X=2} ), neither can step forward on turn one but each will know by turn two that the other saw a muddy face—which they can see is not Charlie's—so their own face must be muddy and both will step forward on turn two. Charlie, seeing two muddy faces, does not know on turn two whether his own face is muddy or not until Alice and Bob both step forward (indicating that his own face is clean). If all three are muddy ( X = 3 {\displaystyle X=3} ), each is in the position of Charlie when X = 2 {\displaystyle X=2} : when two people fail to step forward on turn two, each knows that the other sees two muddy faces meaning that their own face must be muddy, and each steps forward on turn three. It can be proven that X {\displaystyle X} muddy children will step forward at turn X {\displaystyle X} .
Game-theoretic solution
… excerpt ends here. Continue reading the full article.
