Sam Auyeung

Sam Auyeung

Mathematical Induction and Mutual vs. Common Knowledge

7 minute read

Published:

I was talking with a friend recently about a logic puzzle. Back in college, when first learning about the Principle of Mathematical Induction, we were told the following puzzle concerning green-eyed dragons.

You visit a secluded island with 100 green-eyed, perfectly rational dragons and learn a few strange things about their society. If a dragon finds out they have green-eyes, they will turn into a sparrow at sunset that day. Every dragon can see the eye color of all the other dragons but they have no way to learn their own eye color. There are no mirrors, no reflecting pools, everyone avoids talking about the subject. On the day you leave, you say to the crowd of all 100 dragons, “At least one of you has green-eyes.” Being trusting dragons, they all believe your statement to be true and think through the logical implications of what you said. What, if anything, happens?

First of all, I’m not sure why logic puzzles are often framed in such fantastical settings. Maybe it’s to make things more entertaining and also to point out that what’s important to the puzzle isn’t the window dressing of the story. Of course, the story can also be distracting and some people will look for loopholes specific to the story that go against the spirit of the puzzle. For example, they may suggest forming a reflecting pool with seawater for the dragons and so what happens is that any dragon that looks at it will turn into a sparrow that evening. But you could easily change the scenario where the dragons live in a dry desert instead and the magical dragons don’t need water to live. Also, they must come to logical certainty in order to turn into sparrows, not merely rely on probability.

Anyways, on the face of it, it appears that no new information is being given when you make the statement. After all, any dragon can see the eye color of all the other dragons and so they already know that at least 99 of them have green eyes and de facto, know at least one has green eyes. But the result of the statement is that 100 days after you leave, all of the dragons turn into sparrows.

To see why, let’s begin with $n=2$ instead of 100. On the first day, dragon A thinks, “Dragon B has green eyes. If I do not have green eyes, then Dragon B can see that and conclude that he has green eyes. Then, he will turn into a sparrow. But if Dragon B does not turn into a sparrow this evening, that means I must have green eyes in order for him to be unsure of whether he has green eyes.” Since both dragons think this, they both wait to see what happens the first evening. When neither transforms, they deduce they both have green eyes and both turn into sparrows the second evening. With $n=3$ dragons, A, B, C, dragon A thinks, “If I don’t have green eyes, B and C will see that and I am no longer relevant to their considerations. They will simply go through their two day waiting period (as the $n=2$ case). If neither of them turns into a sparrow on the second evening, it will be because I have green eyes.” Thus all three turn into sparrows on the third day. Note that in this $n=3$ case, each dragon does not learn of their own eye color until the $n-1=2$ day passed and nothing happened. One can then apply mathematical induction and deduce that for any positive integer $n$, if there are $n$ dragons in the story, they will all turn into sparrows on the $n$th day.

Let’s return to the point about the dragons seemingly not learning anything new by your statement. Each dragon individually already knew, prior to your statement, that there are at least 99 dragons with green eyes. But after your statement was made, they now additionally know that all the other dragons also know this fact. So each dragon now knows that all the other dragons know there are at least 98 dragons with green eyes. This is because dragon A can have the following thought process: “I don’t know whether I have green eyes. Suppose I do not. Dragon B over there is unsure about her own eye color but can see that 98 other dragons, excluding myself, have green eyes. So dragon B knows at least 98 other dragons have green eyes.” This would be 2nd order knowledge. We may continue into deeper levels of knowledge, eventually getting down to a long recursive statement regarding knowledge and at least one dragon. But the 99th day is the crucial one that each dragon waits for. Each dragon know that if all the other dragons turn into sparrows on day 99, then they themselves do not have green eyes. It is after the evening of the 99th day that every dragon learns their own eye color.

So the seemingly innocuous statement “At least one dragon has green eyes” introduces information because it converts this statement from “mutual knowledge” into “common knowledge.” Mutual knowledge is just about what we all, as individuals, know. But common knowledge is about things we all know and know that each other knows, ad infinitum. In regular parlance, the terms are used synonymously but in order to do a more technical analysis, common knowledge is an extremely strong condition.

As I was writing this post, I spent some time thinking of examples where 2nd or higher order knowledge comes into play in the “real” world. I do have a relevant example but will leave out some details to the story. Many years ago, a college professor wrote and published a book about a country with a strict regime that punished political dissidents. The book included some stories of people who were, at the time, still alive and living in this country. Moreover, their real names were used. In various ways, some of these people had already suffered punishment at the hands of the regime. For example, some had been imprisoned and then released on the condition that they not talk about their experiences and also denounce their political ideologies. Now, some people told the author that publishing those stories could possibly disrupt and even endanger the lives of the subjects of the stories. The author’s response was that the regime knew those people anyway so he was not giving away new information to the regime. But the thing is, once the stories and identities became public knowledge, the government knows that the public knows about these people and the public knows that the government knows about these people. If any of the individuals were seen by the public, then some may perceive that as weakness of the regime for allowing dissidents to walk freely. Thus, there was a chance the publication of the author’s book would lead the regime to arrest the indivuals a second time in order to avoid looking weak. I don’t know if anything happened to those individuals; I certainly hope their lives were not negatively impacted. This story illustrates the importance of responsibily communicating or ommitting knowledge. Curiously, I’ve shared this story with a few people who (as far as I can tell) have spent their whole lives in the US and are unfamiliar with oppressive regimes. As such, this example did not seem to carry much weight with them.

You May Also Enjoy

A Calculus Problem About Finding a Cubic

5 minute read

Published:

I’m teaching Calculus 1 this semester and one of my former students introduced me to the following problem which needs only Calculus 1 ideas.

The Circular Restricted Three Body Problem and the Poincaré-Birkhoff Theorem

23 minute read

Published:

In October 2023 ago, I wrote a post about the Three Body Problem and how it’s an example of a chaotic system and moreover, is not completely integrable. Recently, I’ve been reading Agustin Moreno’s wonderful lecture notes on the subject, particularly because his aim is to show how symplectic and contact topology apply to the study of the Three Body Problem. I wanted to write down some of what I learned; nothing here is original to me. In particular, I want to write about the Circular Restricted Three Body Problem (CR3BP). This is a version of the traditional problem where three point masses live in a system where only Newtonian gravity is at play. One of the masses is assumed to be much smaller than the others so that it is essentially negligible; i.e. it’s movement is influenced by the two primary masses but it does not affect the movement of the primaries. Moreover, it is assumed that the other two masses move in circles around their common center of mass.

An Application of Differential Equations to Plane Geometry

2 minute read

Published:

This is a somewhat different post from my previous ones about applying topology. However, the spirit of those posts was to illustrate unexpected applications and this post will remain in this spirit, if only because we’ll be doing things in a backwards and needlessly complicated way which perhaps breaks expectations. Here is a question: given the ellipse defined by $(ax+by)^2+(cd+dy)^2 = r^2$ in $\mathbb{R}^2$, what are the lines which contain its major and minor axes? I actually never took a formal geometry class in high school nor college so I don’t know what the usual pedagogical approach is to learning this.

An Application of Topology to Gravitational Lensing

5 minute read

Published:

Here is an interesting application of topology that I learned from Cumran Vafa. In astronomy, there is the phenenomenon of gravitational lensing which is when light shining from some star or galaxy gets bent as it travels towards us on earth. The bending is due to a strongly gravitating object such as a black hole (the light doesn’t “fall in” if it doesn’t cross the event horizon). Thus, we sometimes see multiple images of the same object because of this effect. We may even see the images inverted, similar to how when you look at your own reflection in a spoon, depending on the distance you hold it from yourself, you might see your image flipped. Here is an image, courtesy of NASA. Note that around the center, we have four bright white spots which look similar. I believe these should actually all be the same object, just seen more than once due to this effect.