Talk:Common knowledge (logic)

The blue eyes people on the island example

The "textbook example" is largely an opportunity for showing off: it does not actually illuminate what is meant by common knowledge. The evolution of what is considered "common knowledge" within a society is not approached yet. Why are no vehicles of "common knowledge" mentioned? Is there no relation to proverbs for instance? A few links to the rest of Wikipedia might make this exercise appear less self-indulgent. --Wetman 22:11, 24 Jan 2005 (UTC)

The "textbook example" is not self-indulgence. That example is the one example I had to demonstrate why common knowledge is different from "general knowledge" to n-ply, with arbitrarily large n. I'm not a logician, nor an expert on this matter, and I bring forth what little knowledge I have in the hopes of contributing as best I can.

This article was intended as one on the precise "common knowledge" of modal logic (and possibly its applications to real human systems) not the informally defined "common knowledge" of proverbs, oral traditions, etc. EventHorizon talk 23:03, 24 Jan 2005 (UTC)

Where's the article defining "Common knowledge", that is, the stuff that most people know? I.E. "IT is common knowledge that the U.S. Declaration of Independence was signed in 1776." --Locarno 16:10, 3 March 2006 (UTC)

Perhaps this paper should have been called the logic of common knowledge. Pierre de Lyon 02:42, 21 March 2006 (UTC)

Moved to "Common knowledge (logic)". -- Beland 05:28, 7 May 2006 (UTC)

Is the example even correct for K>3? Isn't it common knowledge from the start that there are at least K-2 people with blue eyes? 124.176.51.232 (talk) 09:31, 3 February 2008 (UTC)

Each new day that no-one leaves adds to the knowledge of the number of blue eyed people. After day 1, everyone knows that there are at least 2 blue-eyed people. After day 2, everyone knows that there are at least 3 blue-eyed people. 216.17.5.44 (talk) 21:04, 12 February 2008 (UTC)

I know nothing of the concept of "common knowledge" that is being explained here, but to me at least, the example is flawed. For n>1, there is no knowledge introduced by the outsider's pronouncement of the existence of blue eyes. That only adds something for the trivial case of n=1 - it is simply a device to assist the induction proof. For n>1, there is the new knowledge introduced by the passing of each day. The blue-eyed people would leave n days *after they got there*. 216.17.5.44 (talk) 21:39, 12 February 2008 (UTC)

I don't think the validity of the example is in dispute. It's a well-known puzzle. But as a response to your statement, an announcement is absolutely required in this problem. When the islanders arrived, for the n=1 case the blue-eyed person would have no evidence as to the existence of blue-eyed people, and would not leave. For the n=2 case, each blue-eyed islander would not expect a single blue-eyed islander to know that blue-eyed islanders existed, and would therefore not deduce his own eye color, etc. This puzzle is tricky to think about correctly, which is why it's interesting. But its trickiness does not make it incorrect. —Preceding unsigned comment added by 58.91.12.178 (talk) 20:21, 16 February 2008 (UTC)

Most of the puzzle's "trickiness" comes from a pointless and baffling redefinition of what it means to be human. For values of n above 3 or perhaps 4, no one will leave the island unless they are extraordinarily good at logic, as evidenced by the fact that laypeople who hear this puzzle never think it's reasonable for anyone to ever leave the island. Replace the people in the puzzle with robots programmed to flawlessly follow all their knowledge to all of its logical conclusions, and you have a good puzzle (and quite correct as outlined in the article). However, as long as we postulate people instead of robots, it's simply wrong. People don't and generally can't act like robots, and it's patently unfair to present a logic puzzle in which the reader has to pretend they do. It makes the puzzle harder, but for the same reasons that describing it in 5th century Japanese would make it harder. Therefore, I say we change the presentation of the puzzle in the article to be about robots, accordingly. If no one disagrees I'll do it in a couple of days. --Ecksemmess (talk) 23:19, 16 February 2008 (UTC)

I believe the puzzle is difficult to understand because it would not seem that the visitor's statement, that there are people on the island with blue eyes, would have any effect when everyone already knows that there are such people for any case n>2. Populations of hyperrational people are very commonly used in problems of this sort, and it doesn't seem that using them here presents any special difficulty. Accepting the existence of hyperrational people would seem to be the easiest part of this puzzle. In any case, the puzzle still has its meaning if you use something other than the everyday hyperrational Joe, like hyperrational aliens, hyperrational robots, or hyperrational professors of logic. So if you feel strongly about the subject of the puzzle, change away. But a more useful task might be a clear explanation of how a statement of something which is already known adds new information to the island. This is not at all easy, but would add quite a bit to the article if someone could find a way to do it.24.57.194.211 (talk) 13:37, 19 February 2008 (UTC)

To be sure, the puzzle is difficult to understand for quite a few reasons. Whether we talk about robots or humans, you're right that the difficulty in seeing what new information the visitor brings is going to throw a lot of people off the mark. I'm working on a good way to elucidate this factor; probably the best explanation involves admitting that the visitor does bring new information, though the new information is specifically that everyone believes that everyone believes that everyone believes (...to the hundredth) that someone has blue eyes. The recursive aspect of this knowledge is the key, and is clearly new with the visitor's proclamation, assuming no one grants the possibility of a lie and assuming the visitor gathers everyone together, of course. However, I still think that for the layperson (rather than the logician or veteran of these puzzles), something should replace the hypothetical "hyper-rational human", which I'm afraid is just too counter-intuitive an entity for even many quite intelligent people to contemplate. (What's worse, the article as is doesn't even mention that the people are hyper-rational, which obviously totally invalidates everything.) I know how annoying it is when someone like me complains and complains instead of going and making improvements, so I'm sorry about that. I'll do what I can.

Oh, and I don't see any trolls here, Pierre de Lyon. --Ecksemmess (talk) 10:12, 22 February 2008 (UTC)

The fact that visitor does bring new info is completely counter-intuitive. Leaving that fact from an article does not help, put it back as a comment/notice or mention that they never thought about that before visitor came to an island. --83.237.2.228 (talk) 22:31, 26 January 2010 (UTC)

"Please do not feed the troll" Pierre de Lyon (talk) 22:03, 19 February 2008 (UTC)

First order logic

Beware of the use first order logic which has a precise meaning in logic. As second order logic and higher order logic, see section Comparison with other logics in article first order logic for a classification. Pierre de Lyon (talk) 21:54, 19 February 2008 (UTC)

New knowledge

For k>1, how would the outsider's statement add anything not already known? 75.118.170.35 (talk) 16:17, 12 August 2009 (UTC)

This puzzle is bogus

This puzzle and its proof are completely bogus.

As no new knowledge was introduced, and everybody could easily infer what was said, it cannot possibly have any effects. Everybody could logically tell that everybody knows that some people have blue eyes, and everybody could already logically tell than everybody knows that everybody knows, and so ad infinitum. This fact is already common knowledge. Taw (talk) 02:38, 22 September 2009 (UTC)

Wrong. If k=2 then not everyone knows that everyone knows that there is a blue eyed.Scineram (talk) 19:49, 13 November 2009 (UTC)

The example is correct

Those who are arguing that the example is incorrect are confusing our common knowledge (as observers) and the common knowledge of the participants.

Bot observers and participants know that:

• On an island, there are k people who have blue eyes, and the rest of the people have green eyes.
• If a person ever knows herself to have blue eyes, she must leave the island at dawn the next day.
• Each person can see every other person's eye color, there are no mirrors, and there is no discussion of eye color.

However, we as observers also know:

• There is at least one blue-eyed person on the island (k ≥ 1).

This means that the participants do not know whether , as a logical necessity, there are any blue eyed people on the island. In their common knowledge k could in principle be zero. Now this might seem splitting hairs, but there is a difference between an observation that there are blue eyed people, and a logical requirement that blue eyed people must necessarily exist.

In the case where the number of people on the island is 1, this islander does not know that k ≥ 1, and therefore still holds onto the the possibility that k = 0. In this case, the islander cannot conclude anything. When the external person arrives, the statement k ≥ 1 cvhanges things, and the islander must then leave.

In the case where the number of people on the island is 2, we as observers know that the number of blue eyed people is either 1 or 2. However, for participants, this number could be 0, 1 or 2. The participants will therefore reason as follows:

Suppose A has blue eyes, B has green eyes.

• A sees B, and notes that B has green eyes. Since A does not know whether there are any blue eyed people on the island, A concludes that k is either zero or 1.
• B sees A, and notes that A has blue eyes. Since B does not initially have information about the value of k (the number of blue eyed people), B concludes that k is either 1 or 2.

Now since the islanders cannot discuss this with one another, although they collectively have enough information to resolve the problem, the shared information (common knowledge) is insufficient to resolve the issue. When the external person arrives, and declares that k ≥ 1, this changes matters. A now knows that k cannot be zero, and must therefore leave.

Suppose A and B both have blue eyes

• Both islanders conclude from observation that k is either 1 or 2. This appears to provide the same information as the outsider introduces. However, this information does not entail any logical necessity. We can see this if we follow A's reasoning (B could reason identically: "Suppose I have green eyes, then B would see a green eyed person. In this case, B would conclude that k is either 0 or 1." Now, in this scenario, A has concluded that k = 1 or 2, and also has concluded that B will conclude that k = 0 or 1, in other words, k = 1. Therefore, under this scenario, B should appear to conclude that he has blue eyes and leave. However B cannot do this, as (a) by transplanting the problem into a hypothetical scenario, the initial observation now has no force, and (b) in any case, B does not not have access to A's initial observation that k ≥ 1. This means that although B concludes (in this hypothetical case) that k = 0 or 1, this is as far as B can go. (Even if B now were to think "suppose I have green eyes", this does not help, as this simply means that B now replicates A's reasoning ans ends up in the same stalemate position.)

However, when the external person arrives and declares k ≥ 1, in A's hypothetical scenario, B could now justifiably conclude that k = 1, and that he has blue eyes, and would leave the following day. As B has not done this the day after the external arrived, A must at that point conclude that k cannot be 1 and leave on the second morning after the external arrives.

The cases where the number of islanders is 3 or more follows the same reasoning.

--91.109.11.90 (talk) 09:32, 8 July 2010 (UTC)

Common versus Mutual Knowledge

I think there is an important mistake in the Steven Pinker reference from Stuff of Thought. It currently states "...the notion of common knowledge (dubbing it mutual knowledge, as it is often done in the linguistics literature)". In fact, Pinker and linguists specifically differentiate mutual knowledge - that which we all know - from common knowledge - that which we all know that we all know (and we all know that we all know that we all know, ad infinitum). Unless I'm misunderstanding it, I'd like to change it. Dashing Leech (talk) 19:39, 18 December 2010 (UTC) — Preceding unsigned comment added by Dashing Leech (talk • contribs) 19:34, 18 December 2010 (UTC)