Chapter 17 Knowledge and Common Knowledge

As we have already seen in chapter 16, reasoning about players’ knowledge about other players’ knowledge was instrumental in understanding herding behavior. In this chapter, we introduce formal models for reasoning about such higher-level knowledge (and beliefs). But before doing so, let us first develop some more intuitions, through the famous “muddy children” puzzle.

17.1 The Muddy Children Puzzle

Suppose a group of children are in a room. Some of the children have mud on their foreheads; all of the children can see any other child’s forehead, but they are unable to see, feel, or otherwise detect whether they themselves have mud on their own forehead. Their father enters the room, announces that some of the children have mud on their foreheads, and asks if anyone knows for sure that they have mud on their forehead. All of the children say “no.”

The father asks the same question repeatedly, but the children continue to say “no,” until, suddenly, on the tenth round of questioning, all of the children with mud on their foreheads answer “yes”! How many children had mud on their foreheads?

The answer to this question is, in fact, 10. More generally, we can show the following (informally stated) claim:

Claim 17.1 (informal). All of the muddy children will say “yes” in, and not before, the $n^{th}$ round of questioning if and only if there are exactly $n$ muddy children.

Proof. (informal) We here provide an informal inductive argument appealing to “intuitions” about what it means to “know” something—later, we shall formalize a model of knowledge that will enable a formal proof. Let $P (n)$ be the statement that the claim is true for $n$ children. That is, we’re trying to prove that $P (n)$ is true for all $n \geq 1$ . We prove the claim by induction.

Base case: We begin by showing $P (1)$ . Because the father mentions that there are some muddy children, if there is only one muddy child, they will see nobody else in the room with mud on their forehead and know in the first round that they are muddy. Conversely, if there are two or more muddy children, they are unable to discern immediately whether they have mud on their own forehead; all they know for now is that some children (which may or may not include themselves) are muddy.

The inductive step: Now assume that $P (k)$ is true for $0 \leq k \leq n$ ; we will show $P (n + 1)$ . Suppose there are exactly $n + 1$ muddy children. Since there are more than $n$ muddy children, by the induction hypothesis nobody will say “yes” before round $n + 1$ . In that round, each muddy child sees $n$ other muddy children, and knows thus that there are either $n$ or $n + 1$ muddy children total. However, by the induction hypothesis, they are able to infer that, were there only $n$ muddy children, someone would have said “yes” in the previous round; since nobody has spoken yet, each muddy child is able to deduce that there are in fact $n + 1$ muddy children, including themselves.

If there are strictly more than $n + 1$ muddy children, however, then all children can tell that there are at least $n + 1$ muddy children just by looking at the others; hence, by the induction hypothesis, they can infer from the start that nobody will say “yes” in round $n$ . So they will have no more information than they did initially in round $n + 1$ , and will be unable to tell whether they are muddy as a result.

■

17.2 Kripke’s “Possible Worlds” Model

Let us now introduce a model of knowledge that allows us to formally reason about these types of problems. We use an approach first introduced by the philosopher Saul Kripke. To reason about beliefs and knowledge, the idea is to consider not only facts about the “actual” world we are in, but also to consider a set of “possible” worlds $Ω$ . Each possible world, $ω \in Ω$ , specifies some “outcome” $s (ω)$ ; think of the outcome as the set of “ground facts” that we care about—for instance, in the muddy children example, $s (ω)$ specifies which children are muddy. Additionally, each world specifies “beliefs” for all of the players. In contrast to our treatment in chapter 16, we here focus on “possibilistic” (as opposed to “probabilistic” beliefs): for each player $i$ , player $i$ ’s beliefs at world $ω$ —denoted $P_{i} (ω)$ —are specified as a set of worlds; think of these as the worlds that player $i$ considers possible at $ω$ (i.e., worlds that $i$ cannot rule out as being impossible according to him).¹ We now, intuitively, say that a player $i$ knows some statement $ϕ$ at some world $ω$ if $ϕ$ is true in every world $i$ considers possible at $ω$ (i.e., $ϕ$ holds at all the worlds in $P_{i} (ω)$ ).

Knowledge structures Let us turn to formalizing the possible worlds model, and this notion of knowledge.

Definition 17.1. A (finite) knowledge structure is a tuple $M = (n, Ω, X, s, \vec{P})$ such that:

$[n]$ is a finite set of players.
$Ω$ is a finite set; we refer to $Ω$ as the set of “possible worlds” or “possible states of the world.”
$X$ is a set of outcomes.
$s : Ω \to X$ is a function that maps worlds $ω \in Ω$ to outcomes $x \in X$ .
For all $i \in [n]$ , $P_{i} : Ω \to 2^{Ω}$ maps worlds to sets of possible worlds; we refer to $P_{i} (ω)$ as the beliefs of $i$ at $ω$ —that is, these are the worlds that $i$ considers possible at $ω$ .
For all $ω \in Ω$ , $i \in [n]$ , it holds that $ω \in P_{i} (ω)$ . (That is, in every world $ω$ , players always consider that world possible.)
For all $ω \in Ω$ , $i \in [n]$ , and $ω^{'} \in P_{i} (ω)$ , it holds that $P_{i} (ω^{'}) = P_{i} (ω)$ . (That is, at every world $ω$ , in every world players consider possible, they have the same beliefs as in $ω$ .)

Definition 17.2. Given a knowledge structure $M = (n, Ω, X, s, \vec{P})$ , we define an event, $ϕ$ , in $M$ as a subset of states $ω \in Ω$ (think of these as the set of state where “ $ϕ$ holds”). We say that $ϕ$ holds at a world $ω$ if $ω \in ϕ$ . Given an event $ϕ$ , define the event $K_{i}^{M} ϕ$ (“player $i$ knows $ϕ$ ”) as the set of worlds $ω \subseteq Ω$ such that $P_{i} (ω) \subseteq ϕ$ . Whenever $M$ is clear from the context, we simply write $K_{i} ϕ$ . Finally, define the event $E ϕ$ (“everyone knows $ϕ$ ”) as $⋂_{i} K_{i} ϕ$ .

The last two conditions in Definition 17.1 deserve some clarification. Given our definition of knowledge (Definition 17.2), the last condition in Definition 17.1 is equivalent to saying that players “know their beliefs”—it requires that at every world $ω$ , in every world they consider possible (in $ω$ ), their beliefs are the same as in $ω$ (and thus at $ω$ , players “know their beliefs at $ω$ ”).

The second-to-last condition, on the other hand, says that at any world $ω$ , players never rule out (the true world) $ω$ . Intuitively, if $ω$ is the true state of the world, players can never have seen evidence that $ω$ is impossible and thus they should never rule it out. In particular, this condition means that players can never know something that is not true: if something holds in every world a player considers possible, then it must hold in the actual world, since the actual world is deemed possible. While this condition is appropriate for defining knowledge, it may not always be the best way to model beliefs—indeed, sometimes people may be fully convinced of false statements! We will return to this point later when discussing the difference between knowledge and beliefs.

Knowledge partitions Let us point out a useful consequence of the two conditions we just discussed. A direct consequence of last condition is that for each player $i$ , and any two worlds $ω_{1}, ω_{2}$ , we have that either $P_{i} (ω_{1}) = P_{i} (ω_{2})$ or $P_{i} (ω_{1})$ and $P_{i} (ω_{2})$ are disjoint. The second-to-last condition, in turn, implies that the beliefs of a player cover the full set of possible worlds. Thus, taken together, we have that the beliefs of a player partitions the states of the world into different disjoint “cells” where the beliefs of the player are all the same—these cells are sometime referred to as the knowledge partitions or knowledge cells of a player.

Knowledge networks To reason about knowledge structures it is convenient to represent them as “knowledge networks/graphs”: The nodes of the graph corresponds to the possible state of the world, $ω \in Ω$ ; we label each node $ω$ by the outcome, $s (ω)$ , in it. The edges in the graph represent the players’ beliefs: we draw a directed edge with label $i$ between nodes $ω, ω^{'}$ if $ω^{'} \in P_{i} (ω)$ (that is, if player $i$ considers $ω^{'}$ possible in $ω$ ). Note that this graph has two important features:

Self-loops: By the second-to-last condition in Definition 17.1, each node has a self-loop labeled by every player identity

i \in [n]

Bidirectional edges: By a combination of the second-to-last and the last conditions, we have that every edge is bidirectional: if a player $i$ considers $ω^{'}$ possible at $ω$ (and we draw an edge from $ω$ to $ω^{'}$ with label $i$ ), then by the last condition (i.e., that players know their beliefs), player $i$ must consider possible the same worlds at $ω^{'}$ and $ω$ , and then by the second-to-last condition (i.e., that players know the true state of the world), player $i$ must consider $ω$ possible at $ω$ , and thus player $i$ must also consider $ω$ possible at $ω^{'}$ (and consequently, we need to draw an edge from $ω^{'}$ to $ω$ with label $i$ ).

To gain some familiarity with knowledge structures and their network representations, let us consider two examples. We first consider a simple example in the context of single-good auctions, and then return to the muddy children puzzle.

Example (A single-good auction) Consider a single-item auction with two buyers. Let the outcome space $X$ be the set of pairs $(v_{1}, v_{2}) \in ℕ \times ℕ$ (where $v_{i}$ specifies the valuation of player $i$ ). Consider a knowledge structure with just two possible worlds, $ω_{1}$ and $ω_{2}$ , such that $s (ω_{1}) = (10, 5)$ , $s (ω_{2}) = (10, 3)$ , and $P_{1} (ω_{1}) = P_{1} (ω_{2}) = {ω_{1}, ω_{2}}$ , $P_{2} (ω_{1}) = ω_{1}$ , and $P_{2} (ω_{2}) = ω_{2}$ . See Figure 17.1 for an illustration of the knowledge network corresponding to this knowledge structure.

**Figure 17.1:** A knowledge network for a single-item auction, where the world state is dependent on player 2’s valuation. This captures the fact that player 2 is fully aware of his valuation, but player 1 is not.

Note that in both worlds, player 1 knows his own valuation ( $10$ ), but he does not know player 2’s valuation—as far as he knows it may be either $3$ or $5$ . In contrast, player 2 knows both his own and player 1’s valuation for the item in both worlds.

Also, note that if we were to change the structure so that $P_{1} (ω_{2}) = {ω_{2}}$ , this would no longer be a valid knowledge structure, as the last condition in Definition 17.1 is no longer satisfied (since $ω_{2} \in P_{1} (ω_{1})$ but $P_{1} (ω_{1}) \neq P_{1} (ω_{2})$ ); in particular, in $ω_{1}$ player 1 would now consider it possible that he knows player 2’s valuation is 3 whereas he does not actually know it.

Note that a world determines not only players’ beliefs over outcomes (valuations, in the above example), but also players’ beliefs about what other players believe about outcomes. We refer to these beliefs about beliefs (or beliefs about beliefs about beliefs $\dots$ , etc.) as players’ higher-level beliefs. Such higher-level beliefs are needed to reason about the muddy children puzzle as we shall now see.

Example (the muddy children) Assume for simplicity that we have two children. To model the situation, consider an outcome space $X = {M, C}^{2}$ (i.e., an outcome specifies whether each of the children is muddy (M) or clean (C)), and the set of possible worlds $Ω = {ω_{1}, \dots, ω_{4}}$ such that:

$s (ω_{1}) = (M, M)$
$s (ω_{2}) = (M, C)$
$s (ω_{3}) = (C, M)$
$s (ω_{4}) = (C, C)$

By the rules of the game, we have some restrictions on each player’s beliefs. Player 1’s beliefs are defined as follows:

$P_{1} (ω_{1}) = P_{1} (ω_{3}) = {ω_{1}, ω_{3}}$ (player 1 knows player 2 is muddy, but cannot tell whether or not he himself is);
$P_{1} (ω_{2}) = P_{1} (ω_{4}) = {ω_{2}, ω_{4}}$ (player 1 knows player 2 is clean, but cannot tell whether or not he himself is).

Analogously for player 2:

$P_{2} (ω_{1}) = P_{2} (ω_{2}) = {ω_{1}, ω_{2}}$ ;
$P_{2} (ω_{3}) = P_{2} (ω_{4}) = {ω_{3}, ω_{4}}$ .

The knowledge network corresponding to this situation is depicted in Figure 17.2. To reason about this game, define the event ${MUDDY}_{i}$ as the set of worlds where player $i$ is muddy, and let the event $SOMEONE_MUDDY = ⋃_{i} {MUDDY}_{i}$ . Consider now a situation where both children are muddy; that is, the true state of the world, $ω$ is $ω_{1}$ . Notice that

ω \in K_{1} SOMEONE_MUDDY

**Figure 17.2:** *Left*: the knowledge network for the muddy children example. *Right*: The knowledge network when the father announces that at least one child is muddy. Notice that, unless the state is $ω_{1}$ , one of the two children is now able to determine the current state.

since player 1 knows that someone (player 2) is muddy. (Recall that $K_{1}$ $SOMEONE_MUDDY$ denotes the set of states where player 1 knows that the event $SOMEONE_MUDDY$ holds.) Similarly,

ω \in K_{2} SOMEONE_MUDDY

and thus, we have

ω \in E SOMEONE_MUDDY .

Furthermore, note that for both players $i \in [2]$ ,

ω \in \neg K_{i} {MUDDY}_{i},

where for any event $ϕ$ , $\neg ϕ$ denotes the complement of the event $ϕ$ , since nobody initially knows whether they are muddy or not.

17.3 Common Knowledge

Does the father’s announcement that there is some muddy child tell the children something that they did not already know? At first sight it may seem like it does not: the children already knew that some child is muddy! However, since the announcement was public, they do actually learn something new, as we shall now see.

Before the announcement, player 1 considers it possible that player 2 considers it possible that the true state of the world is $ω_{4}$ and thus that nobody is muddy. But after the announcement, this is no longer possible: we know that under no circumstances, $ω_{4}$ can never be deemed possible; that is, in the knowledge network, we should now remove all arrows that point to $ω_{4}$ , as seen in the right of Figure 17.2. In particular, we now have that everyone knows that someone is muddy (which previously was not known); that is,

ω \in E E SOMEONE_MUDDY .

In fact, since the announcement was public, the fact that “someone is muddy” becomes commonly known—that is, everyone knows it, everyone knows that everyone knows it, everyone knows that everyone knows that everyone knows it, and so on. We formalize this notion in the straightforward way:

Definition 17.3. Define the event $E^{i} ϕ$ (“level- $k$ knowledge of $ϕ$ holds”) as follows:

E^{i} ϕ = E E \dots (i times) \dots E ϕ .

Define the event $C ϕ$ (“ $ϕ$ is common knowledge”) as follows:

C ϕ = ⋂_{i} E^{i} ϕ .

So, after the announcement, we have

ω \in C SOMEONE_MUDDY .

The important takeaway here is that:

if a statement $ϕ$ gets communicated in private, the statement becomes known to the receiver; whereas,
if the statement is publicly announced, the statement gets commonly known among the recipients.

There is an interesting graph-theoretic way to characterize common knowledge using the knowledge network corresponding to the knowledge structure:

Proposition 17.1. Given a knowledge structure $M = (n, Ω, X, s, \vec{P})$ , and a state $ω \in Ω$ , we have that common knowledge of $ϕ$ holds at $ω$ (i.e., $ω \in C ϕ$ ) if and only if $ϕ$ holds at every state that is reachable from $ω$ in the knowledge network induced by $M$ .

Proof. We prove by induction that $E^{i} ϕ$ holds at some state $ω$ if and only if $ϕ$ holds at at every state that is reachable through a path of length $i$ from $ω$ . The base case $j = 0$ is trivial. To prove the induction step, consider some state $ω$ .

We first show that if $ω \in E^{j + 1} ϕ$ , then $ϕ$ must hold at every state that can be reached through a path of length $j + 1$ from $ω$ . Consider some length- $(j + 1)$ path $(ω^{0} = ω, ω^{1}, \dots, ω^{j + 1})$ . By the definition of $E$ , we have that $ω^{1} \in E^{j} ϕ$ , and thus by the induction hypothesis we have that $ϕ \in ω^{j + 1}$ (as $ω^{j + 1}$ can be reached through a length $j$ -path (namely, $ω^{1}, \dots, ω^{j + 1})$ from $ω^{1}$ ).

We next show that if $ϕ$ holds at every state that can be reached through a path of length $j + 1$ from $ω$ , then $ω \in E^{j + 1} ϕ$ . To show that $ω \in E^{j + 1} ϕ$ , we need to show that for every $i \in [n]$ , and every $ω^{'} \in P_{i} (ω)$ , we have that $ω^{'} \in E^{j} ϕ$ . Consider any such state $ω^{'}$ . By our assumption that $ϕ$ holds at every state that can be reached through a path of length $j + 1$ from $ω$ , it follows that $ϕ$ also holds at every state that can be reached through a path of length $j$ from $ω^{'}$ (as any such state can be reached through a path of length $j + 1$ from $ω$ ). By the induction hypothesis, it thus follows that $ω^{'} \in E^{j} ϕ$ .

■

Back to the muddy children Let us return to the muddy children puzzle. Does the announcement of the father enable anyone to know whether they are muddy? The answer is no. In fact, by inspecting the knowledge network resulting from removing $ω_{4}$ , we still have for $i \in [2]$ ,

ω \in \neg K_{i} {MUDDY}_{i} .

So, everyone will reply “no” to the first question. How do these announcements (of the answers “no”) change the players’ knowledge? The players will now know that states $ω_{2}$ and $ω_{3}$ are impossible, since $ω_{2} \in K_{1} {MUDDY}_{1}$ and $ω_{3} \in K_{2} {MUDDY}_{2}$ ; hence, if either of these states were true, one of the two children would have answered “yes” to the first question.

So, when the father asks the second time, the graph is reduced to only the state $ω_{1}$ , and so both children know that they are muddy and can answer “yes.” The same analysis can be applied to a larger number of players; by using an inductive argument similar to the one at the start of the chapter, we can prove using this formalism that after $k$ questions all states where $k$ or fewer children are muddy have been removed. And so, in any state where there exist $m$ muddy children, all of them will respond “yes” to the $m^{th}$ question.

17.4 Can We Agree to Disagree? [Advanced]

Consider some knowledge structure $Γ = (n, Ω, X, s, \vec{P})$ , and let $f$ be some probability mass function over the set of states $Ω$ ; think of $f$ as modeling players’ “prior” probabilistic beliefs “at birth” before they receive any form of information/signals about the state of the world. This probability mass function is referred to as the common prior over states, as it is common to all players.

In a given world $ω \in Ω$ , a player $i$ may have received additional information and then potentially “knows” that not every state in $Ω$ is possible—they now only consider states in $P_{i} (ω)$ possible. Consequently, we can now define a player $i$ ’s (subjective) posterior beliefs in $ω$ by conditioning $f$ on the set of states $P_{i} (ω)$ . Concretely, given some event $H$ ,

Let ${[Pr (H) = ν]}_{i}$ (read “i assigns probability $ν$ to the event $H$ ”) denote the set of states $ω$ such that $\underset{(Ω, f)}{Pr} [H ∣ P_{i} (ω)] = ν$ ; that is, the set of states where $\frac{\sum_{ω^{'} \in H \cap P_{i} (ω)} f (ω^{'})}{\sum_{ω^{'} \in P_{i} (ω)} f (ω^{'})} = ν$
holds.

A natural question that arises is whether it can be common knowledge that two players disagree on the probability of some event holding. Aumann’s “agreement theorem” shows that this cannot happen. Formally,

Theorem 17.1. Let $M = (n, Ω, X, s, \vec{P})$ be a knowledge structure, and let $f$ be a common prior over $Ω$ . Suppose there exists some world $ω \in Ω$ such that

ω \in C ({[Pr (H) = ν_{i}]}_{i} \cap {[Pr (H) = ν_{j}]}_{j}) .

Then, $ν_{i} = ν_{j}$ .

Before proving this theorem, let us first state a simple lemma about probabilities:

Lemma 17.1. Let $F_{1}, \dots F_{m}$ be disjoint events and let $F = F_{1} \cup F_{2} \dots \cup F_{m}$ (that is, $F_{1}, \dots, F_{m}$ partition, or “tile,” the set $F$ ). Then, for any event $H$ , if for all $i \in [m]$ we have that $Pr [H ∣ F_{i}] = ν$ , it follows that $Pr [H ∣ F] = ν$ .

Proof. The lemma follows directly by expanding out the definition of conditional probabilities. In particular, by Claim A.4, we have:

\begin{array}{rcl} Pr [H \cap F] = \sum_{i \in [m]} Pr [H \cap F ∣ F_{i}] Pr [F_{i}] = \sum_{i \in [m]} Pr [H ∣ F_{i}] Pr [F_{i}] = \\ = \sum_{i \in [m]} ν Pr [F_{i}] = ν Pr [F], \end{array}

which concludes the claim.

■

We now turn to the proof of the agreement theorem.

Proof of Theorem 17.1. Let $H_{i, j}^{ν_{i}, ν_{j}} = {[Pr (H) = ν_{i}]}_{i} \cap {[Pr (H) = ν_{j}]}_{j}$ denote the event that $i$ assigns probability $ν_{i}$ to $H$ and $j$ assigns probability $ν_{j}$ to $H$ . Consider some state $ω$ where $H_{i, j}^{ν_{i}, ν_{j}}$ is common knowledge; that is,

ω \in C H_{i, j}^{ν_{i}, ν_{j}} .

As noted above, this means that $H_{i, j}^{ν_{i}, ν_{j}}$ holds at every state that is “reachable” from $ω$ in the network graph; let $C$ denote the set of states that are reachable from $ω$ .

Let $ω_{1}^{i}, \dots ω_{m_{i}}^{i}$ denote a sequence of states such that the beliefs of $i$ in those states “tile” all of $C$ ; that is,

C = P_{i} (ω_{1}^{i}) \cup P_{i} (ω_{2}^{i}) \dots \cup P_{i} (ω_{m_{i}}^{i})

and for any two $k_{1}, k_{2}$ , we have that $P_{i} (ω_{k_{1}}^{i})$ is disjoint from $P_{i} (ω_{k_{2}}^{i})$ . Since, as noted above, the beliefs of a player partitions the states of the world, such a set of states is guaranteed to exist. Since $H_{i, j}^{ν_{i}, ν_{j}}$ holds at every state in $C$ , we have that for every $k \in [m_{i}]$ ,

Pr [H ∣ P_{i} (ω_{k}^{i})] = ν_{i} .

By Lemma 17.1 (since the beliefs “tile” $C$ ), it follows that $Pr [H ∣ C] = ν_{i}$ . But, by the same argument, it also follows that $Pr [H ∣ C] = ν_{j}$ and thus we have that $ν_{i} = ν_{j}$ .

■

Let us remark that it suffices to consider a knowledge structure with just two players—thus, when we say that it is common knowledge that the players disagree on the probability they assign to some event, it suffices to say that it is common knowledge only among them. In other words, the players cannot “agree that they disagree” on the probability they assign to the event.

17.5 The “No-Trade” Theorem [Advanced]

So far, when we have been discussing markets and auctions, we have not considered the value the seller has for the item they are selling, and thus whether the seller is willing to go through with the sale. This was actually without loss of generality, since the seller could simply also act as an additional buyer to “buy-back” the item in case nobody is bidding high enough.

However, in our treatment so far we assume that (1) the players always know how much the item is worth to them, and (2) the players may have different private valuations of items. Indeed, the reason the trade takes place is because of the difference in these private valuations. For instance, if the seller of a house in NYC is moving to California, the house is worth less to him than to a buyer who wants to live in NYC.

Let us now consider a different scenario. We have some financial instrument (e.g., a stock) with some true “objective” value (based on the dividends that the stock will generate). Players, however, have uncertainty about what the value of the instrument is. To model this, consider now a random variable $X$ on the probability space $(Ω, f)$ —think of $X$ as the value of the financial instrument. (Note that in every state $ω$ , $X (ω)$ is some fixed value; players, however, are uncertain about this value since they do not know what the true state of the world is.) Assume that one of the players, say $i$ , owns the financial instrument and wants to sell it to player $j$ . When can such trades take place? A natural condition for a trade to take place is that there exists some price $p$ such that $j$ ’s expected valuation for the instrument is at least $p$ and $i$ ’s expected valuation for the instrument is less than $p$ (otherwise, if $i$ is “risk-neutral,” $i$ would prefer to hold on to it). In other words, we say that the instrument defined by random variable $X$ is $p$ -tradable between $i$ and $j$ at $ω$ if $𝔼 [X ∣ P_{i} (ω)] < p$ and $𝔼 [X ∣ P_{j} (ω)] \geq p$ . Let ${TRADE}_{p}^{X} (i, j)$ denote the event that the instrument (modeled by $X$ ) is $p$ -tradable between $i$ and $j$ .

Using a similar proof to the agreement theorem, we can now obtain a surprising no-trade theorem, which shows that it cannot be common knowledge that an instrument is tradable! The intuition for why this theorem holds is that if I think the instrument is worth $> p$ , and then find out that you are willing to sell an instrument at $p$ (and thus must think it is worth $< p$ ), I should update my beliefs with the new information that you want to sell, which will lower my own valuation.

Theorem 17.2. Let $M = (n, Ω, X, s, \vec{P})$ be a knowledge structure, let $f$ be a common prior over $Ω$ , and let $X$ be a random variable over $(Ω, f)$ . There does not exist some world $ω \in Ω$ and price $p$ such that $ω \in C {TRADE}_{p}^{X} (i, j)$

Proof. Assume for contradiction that there exists some $ω \in C {TRADE}_{p}^{X} (i, j)$ . Again, let $C$ denote the set of states that are reachable from $ω$ , and let $ω_{1}^{i}, \dots ω_{m_{i}}^{i}$ denote a set of states such that the beliefs of $i$ in those states “tile” all of $C$ . Since ${TRADE}_{p}^{X} (i, j)$ holds at every state in $C$ , we have that for every $k \in [m_{i}]$ ,

𝔼 [X ∣ P_{j} (ω_{k}^{j})] < p .

By expanding out the definition of conditional expectation (using Claim A.6), we get:

𝔼 [X ∣ C] = \sum_{k \in [m_{i}]} 𝔼 [X ∣ P_{j} (ω_{k}^{j})] Pr [P_{i} (ω_{k_{i}}^{i}) ∣ C] < \sum_{k \in [m_{i}]} p Pr [P_{i} (ω_{k_{i}}^{i}) ∣ C] = p .

But, by applying the same argument to player $j$ , we instead get that

𝔼 [X ∣ C] \geq p,

which is a contradiction.

■

So, how should we interpret this surprising result? Obviously people are trading financial instruments! We outline a few reasons why such trades may be taking place.

We are assuming that both players perceive the value of the instrument as the expectation of their actual value (where the expectation is taken according to the players’ beliefs)—that is, we assume both players are risk-neutral. But, in reality, different players may have different “risk profiles,” and may thus be willing to trade even if they have exactly the same beliefs. For instance, an institutional investor (who is risk-neutral) would be very happy to buy an instrument that is worth $$ 10 M$ with probability $\frac{1}{2}$ and $0$ otherwise, for $$ 4 M$ , but a small investor (who is risk-averse) maybe be very happy to agree to sell such an instrument for $$ 4 M$ (thus, agreeing to take a “loss” in expected profits for a sure gain).
Another reason we may see trades taking place is that the common knowledge assumption may be too strong. While it is natural to assume that I must know that you want to trade with me in order for the trade to take place, it is not clear that we actually must have common knowledge of the fact that we both agree to the trade; thus trades can take place before common knowledge of the trade taking places “has occurred.”
Finally, and perhaps most importantly, the theory assumes that all players are rational. In reality, there are lots of noise-traders whose decision to trade may be “irrational” or “erratic”; noise-traders do not necessarily trade based on their expected valuation of the instrument—in fact, such a valuation may not even be well-defined to them. Indeed, many private persons buying a stock (or index fund) probably have not done enough research to even establish a reasonable belief about the value of the company (or companies in the case of an index fund), but rather buy based on the “speculative” belief that the market will go up.

17.6 Justified True Belief and the Gettier Problems

In our treatment of knowledge and beliefs, we are assuming that the knowledge structure is exogenously given—for instance, in the muddy children example, it was explicitly given as part of the problem description. Coming up with the right knowledge structure for a situation, however, is nontrivial.

In fact, even just defining what it means for a player to know something is a classic problem in philosophy; without a clear understanding of what it means for a player to know some statement $ϕ$ , we cannot come up with knowledge structure where $ϕ$ holds in all the worlds the player considers possible. The classic way of defining knowledge is through the, so-called, justified true belief (JTB) paradigm: according to it, you know $ϕ$ if (a) you believe $ϕ$ , (b) you have a “reason” to believe it (i.e., the belief is justified), and (c) $ϕ$ is actually true.

However, there are several issues with this approach, as demonstrated by the now-famous “Gettier problems”: Let us say that you walk into a room with a thermometer. You observe that the thermometer say 70 degrees, and consequently you believe that the temperature is 70 degrees; furthermore, the temperature in the room is 70 degrees. According to the JTB paradigm, you would then know that the temperature is 70 degrees, since (a) you believe it, (b) you have a reason for doing so (you read it off the thermometer), and (c) the temperature indeed is 70 degrees. Indeed, if the thermometer is working, then this seems reasonable.

But what if, instead, it just so happened that the thermometer was broken but stuck on 70 degrees (by a fluke). In this case, would you still “know” that it is 70 degrees in the room? Most people would argue that you do not, but according to the JTB paradigm, you do “know” it. As this discussion shows, even just defining what it means to “know” something is nontrivial.

Notes

The muddy children puzzle is from [Lit53]. As mentioned above, our approach to modeling beliefs and knowledge follows that of the philosopher Saul Kripke [Kri59]. A similar approach was introduced independently, but subsequently, by the game-theorist Robert Aumann [Aum76]. (Aumann received the Nobel Prize in Economic Sciences in 2005.)

Our treatment most closely follows the works of Kripke [Kri59], Hintikka [Hin62], and Halpern and Moses [HM90]. The analysis of the muddy children puzzle is from [HM90]. An extensive treatment of knowledge and common knowledge can be found in [FHMV95].

Aumann’s agreement theorem was proven in [Aum76] and the “no-trade theorem” was proven by Milgrom and Stokey [MS82] (although our formalization of this theorem is somewhat different).

The JTB approach is commonly attributed to the works of Plato (from approximately 2,400 years ago), but it has also been argued that already Plato pointed out issues with this approach; the “Gettier problems” were introduced by the philosopher Gettier [Get63].

¹Later on, we will be able to extend the model to also incorporate probabilistic beliefs over worlds.