The Freudenthal problem and its ramifications (Part III)

The movie "Romanoff and Juliet" (Universal International Studios, 1961) shows Peter Ustinov as the Prime Minister of the tiny, peaceful, sleepy nation of Concordia, only a few miles across somewhere in Europe. It is the time of the cold war, and Concordia is squeezed between East andWest. Americans and Soviets are fiercly determined to dominate the neutral country. Prime Minister Ustinov learns by chance from the American Ambassador that the Americans know about the latest top secret Soviet manoeuvre in this contest to control Concordia. After a bit of reflection, Ustinov visits the Soviet Ambassador and tells him in a voice fraught with significance: "They know." The Soviet Ambassador is not impressed: "We know they know." Ustinov goes back to the American Ambassador: "They know you know." The American Ambassador smiles: "But we know they know we know." Ustinov returns to the Soviet Ambassador: "They know you know they know." The Soviet Ambassador replies triumphantly: "We know they know we know they know!" Once again Ustinov returns to the American Ambassador. Wearily he says: "Well, they know you know they know you know." The American Ambassador repeats it after him, counting on his fingers. "What?" he suddenly cries in horror. "They know we know they know we know?" This is the third article—in a series of three—dedicated to the many variants and variations of the Freudenthal problem [10]. The common crux in all these problems is how to draw the right conclusions from strange conversations that mainly consist of "I-do-not-know" and "Now-I-do-know" and "I-know-that-youknow" statements. In two predecessor articles [4, 5] we have surveyed a number of knowledge propagation puzzles with short conversations of strictly bounded length. In the current article we consider knowledge propagation puzzles with long conversations, where the number of statements comes as a parameter. Typically, the answer to such a problem varies with the length of the conversation. In all these problems it is crucial to recognize the difference between what is true and what a player knows to be true. Aumann [1] elaborated on this distinction by introducing the notion of common knowledge, that is, facts that are true, that each player knows to be true, that each player knows that each player knows to be true, that each player knows that each player knows that each player knows to be true, that each player knows that each player knows that each player knows that each player knows to be true, and so forth. The article is structured in the following way. We first introduce and analyze three concrete knowledge propagation puzzles: The consecutive integer game, the arithmetic mean game, and the sum game. Then we discuss in detail a fairly general result on a fairly general game due to Conway and Paterson [8], and finally we review some of the history of the considered problems.