Notes to Common Knowledge
1. Thanks to Alan Hajek for this example, the only example in this section which does not appear elsewhere in the literature.
2. The version of the story Littlewood analyzes involves a group of cannibals, some of whom are marrried to unfaithful wives, and a missionary who visits the group and makes a public announcement of the fact.
3. Robert Vanderschraaf reminded me in conversation that a crucial assumption in this problem is that the cook is telling the diners the truth, that is, the cook's announcement generates common knowledge and not merely common belief that there is at least one messy individual. For if the agents believe the cook's announcements even if the cook does not reliably tell the truth, then should the cook mischeviously announce that there is at least one messy individual when in fact all are clean, all will wipe their faces at once.
4. The mutual knowledge characterized by (i), (ii), and (iii) is sufficient both to account for the agents' following the D^{1},D^{2}outcome, and for their being able to predict each others' moves. However, weaker knowledge assumptions imply that the agents will play D^{1},D^{2}, even if they might not both be able to predict this outcome before the start of play. As Fiona's quoted argument implies, if both are rational, both know the game, and Fiona knows that Alan is rational and knows the game, then the D^{1},D^{2}outcome is the result, even if Alan does not know that Fiona is rational or knows the game
5. Hume's analysis of the Farmer's Dilemma is perhaps the earliest example of a backwards induction argument applied to a sequential decision problem. See Skyrms (1996) and Vanderschraaf (1996) for more extended discussions of this argument.
6. See §3 for a formal definition of the Nash equilibrium concept.
7. Aumann (1976) himself gives a settheoretic account of common knowledge, which has been generalized in several articles in the literature, including Monderer and Samet (1988) and Binmore and Brandenburger (1989). Vanderschraaf (1997) gives the settheoretic formulation of Lewis' account of common knowledge reviewed in this paper.
8. This result appears in several articles in the literature, including Monderer and Samet's and Binmore and Brandenburger's articles on common knowledge.
9. I abuse notation slightly, writing ‘K_{i}K_{ j}(A)’ for ‘K_{i}(K_{ j}(A))’.
10. A partition of a set Ω is a collection of sets H = {H_{1}, H_{2}, … } such that H_{i}∩H_{j} = ∅ for i≠j, and ∪_{i} H_{i} = Ω.
11. Thanks to Chris Miller and Jarah Evslin for suggesting the term ‘symmetric reasoner’ to decribe the parity of reasoning powers that Lewis relies upon in his treatment of common knowledge. Lewis does not explicitly include the notion of A′symmetric reasoning into his definition of common knowledge, but he makes use of the notion implicitly in his argument for how his definition of common knowledge generates the mutual knowledge hierarchy.
12. The meet M of a collection H_{i}, i ∈ N of partitions is the finest common coarsening of the partitions. More specifically, for any ω ∈ Ω, if M(ω) is the element of M containing ω, then
 H_{i}(ω) ⊆ M(ω) for all i ∈ N, and
 For any other M′ satisfying (i), M(ω) ⊆ M′(ω).
13. B^{c} denotes the complement of B, that is B^{c} = ω − B = {ω ∈ Ω:ω ∉ Ω}. B^{c} can be read “notB”.
14. Gilbert does not elaborate further on what counts as epistemic normality.
15. Gilbert (1989, p. 193) also maintains that her account of common knowledge has the advantage of not requiring that the agents reason through an infinite hierarchy of propositions. On her account, the agents' smoothreasoner counterparts do all the necessary reasoning for them. However, Gilbert fails to note that Aumann's and Lewis' accounts of common knowledge also have this advantage.
16. Harsanyi (1968) is the most famous defender of the CPA. Indeed, Aumann (1974, 1987) calls the CPA the Harsanyi Doctrine in Harsanyi's honor.
17. Alan Hajek first pointed this out to the first author in conversation.
18. An agent's pure strategies in a noncooperative game are simply the alternative acts the agent might choose as defined by the game. A mixed strategy σ_{k}(·) is a probability distribution defined over k's pure strategies by some random experiment such as the toss of a coin or the spin of a roulette wheel. k plays each pure strategy s_{k j} with probability σ_{k}(s_{k j}) according to the outcome of the experiment, which is assumed to be probabilistically independant of the others' experiments. A strategy is completely mixed when each pure strategy has a positive probability of being the one selected by the mixing device.
19. Lewis (1969), p. 76. Lewis gives a further definition of agents following a convention to a certain degree if only a certain percentage of the agents actually conform to the coordination equilibrium corresponding to the convention. See Lewis (1969, pp. 7889).
20. In their original papers, Bernheim (1984) and Pearce (1984) included in their definitions of rationalizability the requirement that the agents' probability distributions over their opponents satisy probabilistic independance, that is, for each agent k and for each
s_{k} = (s_{1j1}, … , s_{k−1 jk−1}, s_{k+1 jk+1}, … , s_{njn}) ∈ S_{k}
k's joint probability must equal the product of k's marginal probabilities, that is,
μ_{k}(s_{k}) = μ_{k}(s_{1j1}) · … · μ_{k}(s_{k−1 jk−1}) · μ_{k}(s_{k+1 jk+1}) · … · μ_{k}(s_{njn})
Brandenburger and Dekel (1987), Skyrms (1990), and Vanderschraaf (1995) all argue that the probabilistic independence requirement is not wellmotivated, and do not include this requirement in their presentations of rationalizability. Bernheim (1984) calls a Bayes concordant system of beliefs a “consistent” system of beliefs. Since the term “consistent beliefs” is used in this paper to describe probability distributions that agree with respect to a mutual opponent's strategies, I use the term “Bayes concordant system of beliefs” rather than Bernheim's “consistent system of beliefs”.
21. A mixed strategy is a propbability distribution σ_{k}(·) defined over k's pure strategies by some random experiment such as the toss of a coin or the spin of a roulette wheel. k plays each pure strategy s_{kj} with probability σ_{k}(s_{kj}) according to the outcome of the experimentm which is assumed to be probabilistically independent of the others' experiments. A strategy is completely mixed when each pure strategy has a positive probability of being the one selected by the mixing device.
Nash (1950, 1951) originally developed the Nash equilibrium concept in terms of mixed strategies. In subsequent years, game theorists have realized that the Nash and more general correlated equilibrium concepts can be defined entirely in terms of agents' beliefs, without recourse to mixed strategies. See Aumann (1987), Brandenburger and Dekel (1988), and Skyrms (1991) for an extended discussion of equilibriuminbeliefs.
22. Ron's private recommendations in effect partition Ω as follows:
 H_{1} = { {ω_{1},ω_{2}}, {ω_{3}} }, and
 H_{2} = { {ω_{1},ω_{3}}, {ω_{2}} }.
These partitions are diagrammed below:
Given their private information, at each possible world ω to which an agent i assigns positive probability, following f maximizes i's expected utility. For instance, at ω = ω_{2},
E(u_{1}(A_{1})  H_{1})(ω_{2}) = ½·3 + ½·2 = 5/2 > 2 = ½·4 + ½·0 = E(u_{1}(A_{2})  H_{1})(ω_{2}) and
E(u_{2}(A_{2})  H_{2})(ω_{2}) = 4 > 3 = E(u_{2}(A_{1})  H_{1})(ω_{2})
23. An outcome s_{1} of a game Paretodominates an outcome s_{2} if, and only if,
 E(u_{k}(s_{1})) ≥ E(u_{k}(s_{2})) for all k ∈ N.
 s_{1} strictly dominates s_{2} if the inequalities of (i) are all srict.
24. While both the endogenous and the Aumann correlated equilibrium concepts generalize the Nash equilibrium, neither correlated equilibrium concept contains the other. See Chapter 2 of Vanderschraaf (1995) for examples which show this.
25. Aumann (1987) notes that it is possible to extend the definitions of Aumann correlated equilibrium and H_{i}measurability to allow for cases in which Ω is infinite and the H_{i}'s are not necessarily partitions. However, he argues that there is nothing to be gained conceptually by doing so.
26. In general, the method of backwards induction is undefined for games of imperfect information, although backwards induction reasoning can be applied to a limited extent in such games.
27. By the elementary properties of the knowledge operator, we have that K_{2}K_{1}K_{ 2}(Γ) ⊆ K_{2}K_{1}(Γ) and K_{1}K_{2}K_{ 1}K_{2}(Γ) ⊆ K_{1}K_{2}K_{ 1}(Γ), so we needn't explicitly state that at I^{22}, K_{2}K_{1}(Γ) and at I^{11}, K_{1}K_{2}K_{ 1}(Γ). By the same elementary properties, the knowledge assumptions at the latter two information sets imply that Fiona and Alan have thirdorder mutual knowledge of the game and secondorder mutual knowledge of rationality. For instance, since K_{2}K_{1}(Γ) is given at I^{22}, we have that K_{2}K_{1}K_{ 1}(Γ) because K_{1}(Γ) ⊆ K_{1}K_{1}(Γ) and so K_{2}K_{1}(Γ) ⊆ K_{2}K_{1}K_{1}(Γ). The other statements which characterize third order mutual knowledge of the game and second order mutual knowledge of rationality are similarly derived.
28. The version of the example Rubinstein presents is more general than the version presented here. Rubinstein notes that this game is closely related to the coordinated attack problem analyzed in Halpern (1986).
29. In the terminology of decision theory, A is each agents' maximin strategy.
30. This could be achieved if the email systems were constructed so that each n^{th} confirmation is sent 2^{n} seconds after receipt of the n^{th} message.
Notes to Rubinstein's Proof
1. If this does not look immediately obvious, consider that eitherE = [T_{2} = t] = my (Lizzi's) t^{th} confirmation was lost,
or
F = [T_{2} = t] = my t^{th} confirmation was received and Joanna's t^{th} confirmation was lost
must occur, and that μ_{1}(T_{1} = t  E) = μ_{1}(T_{1} = t  F) = 1 because Lizzi can see her own computer screen, so we can apply Bayes' Theorem as follows:
μ_{1}(E  T_{1} = t)  = 


= 


= 

Peter Vanderschraaf <pvanderschraaf@ucmerced.edu>
Giacomo Sillari <gsillari@sas.upenn.edu>