This is a file in the archives of the Stanford Encyclopedia of Philosophy. |

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 set-theoretic 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 set-theoretic 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*_{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*
of a collection
_{i}, *i*
*N* of partitions is the finest common coarsening of the
partitions. More specifically, for any
, if
()
is the element of
containing
, then

_{i}() () for all*i**N*, and- For any other satisfying (i), () ().

13. *B ^{c}*
denotes the complement of

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' smooth-reasoner 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 me 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. 78-89).

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-1jk-1},s_{k+1jk+1}, … ,s_{njn})S_{-k}

Brandenburger and Dekel (1987), Skyrms (1990), and Vanderschraaf (1995) all argue that the probabilistic independence requirement is not well-motivated, 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"._{k}(s_{-k}) =_{k}(s_{1j1}) …_{k}(s_{k-1jk-1})_{k}(s_{k+1jk+1}) …_{k}(s_{njn})

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

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 equilibrium-in-beliefs.

22. Ron's private recommendations in effect partition as follows:

_{1}= { {_{1},_{2}}, {_{3}} }, and_{2}= { {_{1},_{3}}, {_{2}} }.

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}) |_{1})(_{2})= ½3 + ½2 = 5/2

> 2 = ½4 + ½0 = E(u_{1}(A_{2}) |_{1})(_{2})and

E(u_{2}(A_{2}) |_{2})(_{2})= 4 > 3 = E(u_{2}(A_{1}) |_{1})(_{2})

23. An outcome
**s**_{1} of a game Pareto-dominates 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
_{i}-measurability to allow for
cases in which
is infinite and the
_{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,
**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
third-order mutual knowledge of the game and second-order mutual
knowledge of rationality. For instance, since
**K**_{2}**K**_{1}()
is given at *I*^{22}, we have
**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 e-mail systems were constructed so that each
*n*^{th} confirmation is sent 2^{-n} seconds after
receipt of the *n*^{th} message.

*First published: June 12, 2002*

*Content last modified: June 12, 2002*