Saturday, April 16, 2005

(I say (I say (I say)))...

Dad and I get into some weird arguments. Dad's an eccentric, in an endearing sort of way. This time, Dad started: "Say I know something, and you find out and then you know, and then I find out that you know. So I know that you know that I know that you know, right?"

Mum looked up from her crossword at this point, looked over her glasses and gave the kind of resigned sigh people only give when their spouse lives in a different dimension. Dad pressed on: "If you take that far enough, does it lose its meaning? Does the 'you know that I know that you know that....' process become nonsensical or just go on and on?" Dad contended that it becomes meaningless, and fairly soon. I disagreed, suggesting that such an exchange could potentially go on forever, and people only stop when the scenario they are discussing becomes too cumbersome to keep in their head.

But how to prove it? Maybe such an exchange genuinely can become meaningless and no contrived scenario can support a narrative where layering of "You know that I know" etc makes any sense. Thus, I resolved to construct a fictitious story to explore the question and see if any patterns emerged. I used as my template a pastiche of World War 2 "POW" movies, like "The Great Escape" or "Escape from Colditz".

Scenario: British troops are captive in a German POW camp. The British are digging a tunnel in order to escape.

Level 1:
British troops: “Lads; were digging a tunnel and we’re getting out of here! The Germans don’t suspect a thing, so get to it.”
Outcome: The British escape.

Level 2:
Meanwhile, in Colonel Klink’s office…
Klink: “Those rascally British are digging a tunnel! Fortunately, they don’t know we’re on to them, so we can keep them occupied until they are about to launch their escape bid. Then, we will catch them!”
Outcome: The Germans win.

Level 3:
British: “Blast! We have discovered that the Germans are on to our tunnel plans. Fortunately, they do not know that we know that they know! Thus, they believe that by monitoring the tunnel they will know where we are consuming our resources. Because they do not know that we know they are on to us, they will not expend further effort in looking for alternate plans. They think we only have one plan! Thus, let us maintain the tunnel as a “dummy” project to distract the Germans from the glider we are building out of bedsheets and porridge behind a false wall!”
Outcome: The British escape (or at least one does)

Level 4:
Klink: “One of our soldiers overheard the British saying that they know that we are aware of their escape plans! Luckily, the British did not know the soldier overheard them. If they are aware of our knowledge, then they are bound to try something different, and the tunnel is merely a diversion. If they know we know about the tunnel then the escape bid cannot come from there. We must assume they will change tactics. Be on the lookout!”
Outcome: The Germans win.

Level 5:
British: “The increased searches in the camp can only mean that the Germans know that we knew that they had discovered our original escape plans and deduced we would try something different. What an opportunity! Previously, being suspicious they would have expected any kind of escape bid, including a tunnel. Now, because they know we know they know, they will specifically exclude a tunnel as a possibility. Thus, we can continue work on the tunnel right under their noses and have them believe that the tunnel is merely being constructed as a diversion, whereas in actual fact we will be building the tunnel for real. The Germans will be off discovering our “real” escape plan, and our secret knowledge that they know about the tunnel will allow us to continue to distract them in this way. Because we do not have to be as cautious, we can work double shifts, post less guards, and make more noise as we go, knowing that the Germans will not dare shut us down because they think they have us in check and “occupied”. This means we can start work on a second tunnel going in a different direction. Set to it!”
Outcome: The British escape.

Level 6:
Klink: Our spy among the prisoners has reported that the British know that we knew that the British knew that we knew of the plan. It is therefore likely that they are assuming that, knowing we knew of the tunnel, that we have discounted it as the source of a serious escape bid. How foolish! Now we know they know, it stands to reason that they think the tunnel may again become a potential escape route. They think they can dig even though we know about it because they think that we think that it is only a diversion. We must be careful!
Outcome: The Germans win.

Level 7:
British: “Interesting news, lads. We’ve discovered that they Germans know that we know that the Germans no longer believe that the tunnel is not necessarily a diversion but may still be a legitimate escape option. This means that, if they see work on a tunnel still proceeding, they will conclude that we are still serious about a tunnel breakout. Fantastic! This diversion will allow us to put another plan into effect where we continue the tunnel as a distraction, take the stolen and faked German uniforms we’ve been hoarding and when the laundry truck…” (blah blah blah)
Outcome: the British escape

Level 8:
Klink: “The British know we know! Thus, the tunnel is a ruse!”

Level 9:
British: “The Germans know we know! Thus, they again believe the tunnel is a ruse and we can again continue the tunnel under their noses!”

1. British dig tunnel (Germans unaware)
2. Germans know of tunnel (catch British)
3. British know Germans knew (glider, tunnel is distraction)
4. German’s knew British knew the Germans knew (look for alternate escape bids)
5. British know the Germans knew the British knew the Germans knew (realise Germans are discounting tunnel and thus resume under German noses)
6. Germans know the British knew the Germans knew the British knew the Germans knew (Germans know the tunnel is not a ruse and remain vigilant)
7. British know the Germans knew the British knew the Germans knew the British knew the Germans knew (British realise above and concoct alternate plan with tunnel reverting to a diversion)
8. Germans know the British knew the Germans knew the British knew the Germans knew the British knew the Germans knew (Germans realise the tunnel is again a diversion and remain vigilant)

…and so it goes. Despite the artificiality of the narrative I have constructed, as far as I can see, an equilibrium can be set up whereby the you know that I know cycle can result in an endlessly repeating loop and does not of necessity reach a natural conclusion. Keeping the various levels “in mind” does indeed become tedious, but it can go on forever.

I feel like I’ve proven my point, but I’ll leave the reader with a final exercise. Is there a similar narrative, ignoring the cosmetic matters of setting or character, that must result in a natural conclusion after a finite number of steps as the “you know that I know” cycle unfolds? What changes to the logic or initial conditions of the scenario are necessary?


Monkeytree said...

You can express it in rules:

If I think you don't know what I'm thinking, then I'll do A.
If I think you DO know what I'm thinking, then I'll do B.

Then there's a loop forming as the "you know's" cancel each other out.

In the prisoner camp example, it loops through two different behaviours for each side - the british oscillate between focussing on the tunnel, and using the tunnel as a distraction. The Germans oscillate between watching the tunnel, and watching everywhere else.

A simpler example is where each side only has one state. So, let's say I flip a coin and it's heads, and you also see it. You say "I know that it's heads". I say "I know that you know that it's heads." You say "I know that you know that I know that it's heads." etc. This is a case in which there's only one state, and nothing changes as the conversation progresses - so it's a meaningless progression because it's trivial.

Now, maybe there's a progression of this logic that has three states per side - or more. Also, you could generalise it for more than two people. I haven't thought up an example, but it would boil down to each person having a behaviour determined by whether he thinks each other person knows what each of the others is thinking. Maybe there's a Russian spy in the prisoner camp, who is able to mess up the plans of either the Germans or the British, and so both the Germans and the british have to gather intelligence on the russian to see whether he knows what everyone is up to.

An extension that would change the dynamics a bit is to have a probabilistic approach, where each party can make a calculated guess that they think the other guy has a certain chance of knowing what's going on, and try to make the best decision by weighing up all the odds.

So, after all that ... I agree, Nathan, that the "I know that you know" discussion doesn't necessarily become meaningless quickly - but it can in the trivial case.

Justin Warner said...

This is... just... silly. :P

Paula said...

Sometimes silly conversations are the best ones - and often, they require more focus and concentration than "normal" conversation!