Oh boys, if you only knew
Level 0: X.
Level 1: Alex knows that X.
Level 2: Bob knows that Alex knows that X.
Level 3: Alex knows that Bob knows that Alex knows that X.
And so on.
In principle, it is possible that the proposition of level n is true, but the propositions at level n+1 and all the higher above it are false, for arbitrary values of n. But is this really possible in practice, in the real world? It would seem to me that in practice between two people, either Alex's and Bob's knowledge of the other one's knowledge either stops at the level two or three at most, or it stretches all the way to infinity, as would happen when Alex explicitly tells Bob that he (Alex) knows that X.
It is hard for me to think of a communication exchange or observations between Alex and Bob that would make the propositions true up to level five, but no higher. I would be curious to see a real-world example of a situation where the knowledge reached up to even level five, but no higher. I just can't think of a practical situation where this could happen.
Things might be different in artificial microworlds such as games. In boardgames such as chess and go, not so much, but in games of incomplete information and bluffing, perhaps more. I don't know more about poker other than its rules, the fact that it is an immoral negative-sum game, and the little about strategy what I have seen on TV, but I could easily imagine that in the highest levels of play, the knowledge about some important fact X about the cards or some player's strategy could reach levels five and six. Any readers who are skilled poker players can feel free to chime in. In the artificial microworlds of sitcoms we might also theoretically get to level four or five, but any higher than that, the plot would get too complicated for the audience to follow.
In fact, somebody ought to design a game whose central defining feature was gathering and inferring information about the beliefs and meta-beliefs of the other participants, which would then determine the course of action in the game, and that in the course of the game, the players would have to manage propositions of the above nature up to level twenty or thirty or so. There might already exist games of this nature, but I can't recall ever seeing one. The canonical examples of made-up games that involve higher-level "meta" thinking, Eleusis and Mao, are really not of the nature what I am looking for here. Although now that think more about it, at least in Eleusis, reverse inference about the knowledge and beliefs of other players would come in handy in designing rules that whose complexity is just right.
Level 1: Alex knows that X.
Level 2: Bob knows that Alex knows that X.
Level 3: Alex knows that Bob knows that Alex knows that X.
And so on.
In principle, it is possible that the proposition of level n is true, but the propositions at level n+1 and all the higher above it are false, for arbitrary values of n. But is this really possible in practice, in the real world? It would seem to me that in practice between two people, either Alex's and Bob's knowledge of the other one's knowledge either stops at the level two or three at most, or it stretches all the way to infinity, as would happen when Alex explicitly tells Bob that he (Alex) knows that X.
It is hard for me to think of a communication exchange or observations between Alex and Bob that would make the propositions true up to level five, but no higher. I would be curious to see a real-world example of a situation where the knowledge reached up to even level five, but no higher. I just can't think of a practical situation where this could happen.
Things might be different in artificial microworlds such as games. In boardgames such as chess and go, not so much, but in games of incomplete information and bluffing, perhaps more. I don't know more about poker other than its rules, the fact that it is an immoral negative-sum game, and the little about strategy what I have seen on TV, but I could easily imagine that in the highest levels of play, the knowledge about some important fact X about the cards or some player's strategy could reach levels five and six. Any readers who are skilled poker players can feel free to chime in. In the artificial microworlds of sitcoms we might also theoretically get to level four or five, but any higher than that, the plot would get too complicated for the audience to follow.
In fact, somebody ought to design a game whose central defining feature was gathering and inferring information about the beliefs and meta-beliefs of the other participants, which would then determine the course of action in the game, and that in the course of the game, the players would have to manage propositions of the above nature up to level twenty or thirty or so. There might already exist games of this nature, but I can't recall ever seeing one. The canonical examples of made-up games that involve higher-level "meta" thinking, Eleusis and Mao, are really not of the nature what I am looking for here. Although now that think more about it, at least in Eleusis, reverse inference about the knowledge and beliefs of other players would come in handy in designing rules that whose complexity is just right.
In fact, somebody ought to design a game whose central defining feature was gathering and inferring information about the beliefs and meta-beliefs of the other participants, which would then determine the course of action in the game
It's called "poker", I believe...
Posted by TJIC | 7:05 PM
Yes, yes, but how high up in the levels that I defined do poker players have to consciously mentally reach and keep track of, when the game is played in the top level?
Posted by Ilkka Kokkarinen | 8:39 PM
I think I have read somewhere that top poker players could reach eight such levels.
Posted by Anonymous | 2:42 AM
I have a puzzle on similar lines: Let us say you are withdrawing money using an ATM. There is always a very small, almost negligible, but nonzero probability that any message from the ATM to your bank is lost.
The ATM sends a query to the bank, asking if you have enough money on your account. If the answer is "yes", the ATM will send a message saying "I am giving out the money".
If the message is lost, the bank only ever receives the query but not the confirmation and therefore does not know if the message sent to the ATM ever got through. Thus, the bank will log "uncertain". But shall the money be removed from the account?
Ok, what about the ATM, if it sends the "Giving money" message and expects no reply, it will happily distribute cash. But suppose the banker wants to make absolutely certain that no money is given for free? Then they add another layer of acknowledgements, where the bank will reply and say "OK, go ahead".
But, if the "go ahead" message is lost, then ....
This argument can be carried out ad infinitum. If the last message is lost, we can never know if one of the participants decided against the transaction. One of the participants is always left with some degree of uncertainty.
But suppose we implement, say, 10 layers of such "ok, Me too"-acknowledgments, but commit to the transaction say, after 7 layers have been completed.
Is there certainty?
Posted by Tiedemies | 3:20 AM
This is the classical two-army -problem. I think there is no solution to that one.
Posted by Anonymous | 3:59 AM
Read "The theory of poker" by David Sklansky. If I got it right, level 3 is normal thinking for strong players. Levels above that are not used so often unless you really know your enemy well and have played a lot with him. When the reasoning gets too hard, you go for (pseudo)optimal game theoretic play.
Posted by Anonymous | 8:20 AM
Yeah, I know there is no solution to it, but it is, in my opinion, exactly what Ilkka is asking here.
Posted by Tiedemies | 11:16 AM
The ATM problem seems to me to be one in which two actions are to be performed, each (impossibly) being conditional on the prior performance of the other. Surely the way it's actually resolved is for the bank to "take the plunge" and deduct the funds from the account, send the message to that effect to the ABM, and rely on the customer to complain if the actions of the ABM don't correspond to the withdrawal he subsequently sees on his bank statement.
In other words, the way that the banker becomes "absolutely certain that no money is given for free" is by allowing it to be less than certain that no money will be taken (from the account) for "free".
The willingness of banks to resolve such timeless logical conundrums in favour of themselves was considered by Ilkka in his post regarding his TD Canada Trust account.
Posted by andy | 1:46 PM
Tiedemies: Yeah, I know there is no solution to it, but it is, in my opinion, exactly what Ilkka is asking here.
Then I must have phrased the post in a confusing manner. I am aware of the Two Army problem and its unsolvability (becaues no message can ever be the last one), and I don't see how it is related to what I am asking, which is simply how high in this hierarchy we can get in everyday life in practice without going all the way to infinity.
In your own life, what is the highest level of such knowledge that you can remember being in, so that some other person didn't know that you know that he knows that you know... etc. and you somehow then benefited from this?
Posted by Ilkka Kokkarinen | 6:10 PM
As another afterthough, I wonder why none of my Finnish readers has said anything about the title of this post, which I think is way funnier than the earlier "Humppa eller dö".
Posted by Ilkka Kokkarinen | 6:11 PM
Maybe nobody knows where it refers to, other than the speaker knowing that the boys don't know something.
Btw. Before you advised people to google the turtle phrase, I took it for granted that it was a reference to the fact that in the Internet, nobody knows you're a dog.
Posted by Simo | 9:19 PM
I tried to respond further in my post "Know way out" which I hope is also considered a funny title in Finnish.
Posted by andy | 10:00 PM
Maybe nobody knows where it refers to, other than the speaker knowing that the boys don't know something.
Voi pojat, kun tietäisitte...
Posted by Ilkka Kokkarinen | 10:59 PM
This post has been removed by the author.
Posted by Leonard | 6:12 PM
The board game Diplomacy has something of this nature, especially when played slowly via email. There's no randomness in die-rolling or whatever to resolve turns. Instead the new state is a simply-computed result of the orders given. The orders are submitted secretly until the turn. So, the diplomatic aspect is all: convincing other players that you will support their moves, and then (maybe) not doing so. It gets complicated when you get into spinning your moves to the other players, trying to manage their impressions of which side you're really on. For example, if you do a move that objectively hurts X, you might be doing it to create the impression that you're against X even if you are actually in league, and will later support him.
I was playing once online when I got up to three levels of indirection, that is, making a move that was "really" doing one thing, helping country X. But then I spun it to another player Y as really against X (i.e., apparently-helping-X-to-lull-X), and I also spun it to a more sophisticated player (who I knew Y would talk to), as helping-X-to-appear-to-lull-X-to-lull-Y.
Good times, but a frickin' pain in the rear to do all the email socializing necessary to win.
Posted by Leonard | 6:12 PM