most recent 30 from http://mathoverflow.net 2013-06-19T10:37:51Z http://mathoverflow.net/feeds/question/114245 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114245/i-know-that-you-know Pietro Majer 2012-11-23T14:57:55Z 2013-05-25T11:48:24Z

<p>A bit unsure if the following vague question has enough mathematical content to be suitable upon here. In the case, please feel free to close it.</p> <p>In several circumstances of competition, a particular situation of partial information occurs, usually described as "<em>I know that you know that I know... something</em>". We may distinguish a whole hierarchy of more and more complicate situations closer and closer to a complete information. E.g. :</p> <ul> <li>$I_0$: I know $X$, but you don't know that I know.</li> <li>$I_1$: I know $X$, you know that I know, but I don't know that you know that I know.</li> <li>$I_1$: I know $X$, you know that I know, I know that you know that I know, but you don't know that I know that you know that I know.</li> <li>.... &amp;c. </li> </ul> <p>For small values of $k$, I can imagine simple situations where passing from $I_k$ to $I_ {k+1}$ really makes a difference (for instance: you are Grandma Duck, and $X$ is : "you left a cherry pie to cool on the window ledge". Clearly, $I_0$ is quite agreeable position; $I_1$ may lead to an unpleasant end (for me); $I_2$ leaves me some hope, if I behave well, and so on). But, I can't imagine how passing from $I_6$ to $I_7$ may affect my strategy, or Grandma's. </p> <blockquote> <p>Are there situations, real or factitious, concrete or abstract, where $I_k$ implies a different strategy than $I_{k+1}$ for the competitors? What about $I_{\omega}$ and, more generally, $I_\alpha$ for an ordinal $\alpha$ (suitably defined by induction)? How these situations are modeled mathematically? </p> </blockquote>

http://mathoverflow.net/questions/114245/i-know-that-you-know/114248#114248 Tony Huynh 2012-11-23T15:09:03Z 2012-11-23T15:09:03Z

<p>Check out the wikipedia page on <a href="http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29" rel="nofollow">common knowlege</a>, which includes some mathematical formalizations of the concept as well as the famous blue-eyed islander problem mentioned by Steven Gubkin. This problem was also discussed by Terrence Tao on his <a href="http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/" rel="nofollow">blog</a>. </p>

http://mathoverflow.net/questions/114245/i-know-that-you-know/114255#114255 Michael Greinecker 2012-11-23T15:51:07Z 2012-11-23T15:51:07Z

<p>The classic model of these things is due to Robert Aumann and was introduced in his 1976 <a href="http://www.ma.huji.ac.il/raumann/pdf/Agreeing%2520to%2520Disagree.pdf" rel="nofollow">Agreeing to Disagree</a>. There is a famous example due to Ariel Rubinstein, the <a href="http://arielrubinstein.tau.ac.il/papers/32.pdf" rel="nofollow">electronic mail game</a>, in which the behavior of $I_\omega$ radically differs from $I_n$ for any $n$. </p> <p>Here is a way to show that one might have to apply this reasoning up to an arbitrarily large ordinal. Let $\alpha$ be a successor ordinal. Ann and Bob play the game of picking ordinals in $\alpha$ simultaneously. The one who chooses the highest number wins. One can never win by choosing $0$, so rationality rules out choosing $0$. It is however possible to win by choosing $1$ if the other player plays $0$. But if both Ann and Bob know that they are both rational, they have to choose at least $2$. It is clear that one has to iterate this reasoning up to the predecessor of $\alpha$.</p>

http://mathoverflow.net/questions/114245/i-know-that-you-know/114265#114265 Tony Huynh 2012-11-23T17:24:50Z 2012-11-23T17:59:23Z

<p>Here is another puzzle I like which is in the spirit of the question. 100 people play a game as follows. Each person secretly writes a number between 1 and 1000000. The numbers are then all revealed and the person who is closest to 2/3 of the average wins a prize. If there is a tie, the prize is shared between the winners.</p> <blockquote> <p>What number should one write down?</p> </blockquote> <p>Now, it is clearly foolish to write down any number greater than 666667, since 2/3 of the average cannot be more than 666667. But now we can view the game as being played on the interval from 1 to 666667 instead of from 1 to 1000000. Now we can iterate again and conclude that it is foolish to choose any number greater than 444444. Ultimately (but this requires many iterations of knowledge), the only rational choice is for all players to choose 1 and to split the prize. </p>

http://mathoverflow.net/questions/114245/i-know-that-you-know/114271#114271 Joel David Hamkins 2012-11-23T18:01:48Z 2012-11-24T04:35:44Z

<p>My wife and I have a standing agreement where I pick up our son Horatio from school and she picks up our daughter Hypatia. </p> <p>One day, because I knew I would be near Hypatia's school, it was convenient to swap duties. I emailed her a message, "I'll pick up Hypatia today, and you get Horatio. Please confirm; otherwise it is as usual." She texted me back, "Let's do it. Let me know if you get this message, so that I know we're really on." I left her a voicemail, "OK, we're definitely on for the swap! ....as long as I know you get this message." She emailed me back, "Got the message. We're on! But let me know that you get this message so I can count on you." You see, without confirmation she couldn't be sure that I knew she had gotten my earlier confirmation of her acknowledgement of my first message, and she may have worried that the plan to swap was consequently off. </p> <p>And so on <em>ad infinitum</em>......</p> <p>How truly frustrating it was for us that at no stage of our conversation could we seem to know for certain that the other person had all the necessary information to ensure that the plan would be implemented! The result, of course, since we had time to exchange only at most a finite number of messages, was that the only rational course of action was for us each to abandon the plan to swap: we both independently decided just to pick up the usual child. </p> <p>To see that this was rational, observe that clearly the first message needed to have been confirmed in order for the plan to be implemented properly. Furthermore, if the $n$-th message need not have been confirmed, then it wasn't important to know that it had been received and the algorithm should have worked whether or not it was received, meaning that it didn't actually need to have been sent. So by induction, no number of confirmations suffices to implement the common knowledge that we both needed, namely, that we had each agreed to make the swap.</p> <p>See also the <a href="http://en.wikipedia.org/wiki/Two_Generals%27_Problem" rel="nofollow">two generals problem</a>. </p>

http://mathoverflow.net/questions/114245/i-know-that-you-know/114317#114317 Tim Porter 2012-11-24T07:08:33Z 2012-11-24T07:08:33Z

<p>A good source for this sort of reasoning is:</p> <p>J.-J. Meyer and W. van der Hoek, Epistemic Logic for AI and Computer Science, Number 41 in Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995.</p> <p>The question of common knowledge, and of the algorithmics of epistemic modal logics, provides a lot of good material on this sort of problem. (It is good fun to try the mathematical side of this in Popularisation activities. I used Muddy Children with various groups with a lot of laughter and appreciation of the mathematical models.)</p>

http://mathoverflow.net/questions/114245/i-know-that-you-know/114319#114319 John Bentin 2012-11-24T08:07:05Z 2012-11-24T08:07:05Z

<p>The article <a href="http://plato.stanford.edu/entries/common-knowledge/" rel="nofollow">http://plato.stanford.edu/entries/common-knowledge/</a> is more extensive than wikipedia's. However, it doesn't deal with the issue of infinite information.</p>