Supplement to Epistemic Foundations of Game Theory

1. Proof of Lemma 3.1

Lemma 3.1 Suppose that $G=\langle N, \{S_i, u_i\}_{i\in N}\rangle$ is a strategic game. A strategy $s_i\in S_i$ is strictly dominated (possibly by a mixed strategy) with respect to $X\subseteq S_{-i}$ iff there is no probability measure $p\in \Delta(X)$ such that $s_i$ is a best response with respect to $p$.

Proof: We start with some preliminary observations. Let $G=\langle S_1, S_2, u_1, u_2\rangle$ be a two-player strategic game. Recall that $\Delta(S_1)$ and $\Delta(S_2)$ denote the mixed strategies for players 1 and 2, respectively. For $p_1\in \Delta(S_1)$, $p_2\in \Delta(S_2)$, we write $U_1(p_1, p_2)$ (respectively $U_2(p_1,p_2)$) for the expected utility that player $1$ (respectively $2$) receives when $1$ uses the mixed strategy $p_1$ and $2$ uses the mixed strategy $p_2$. We assume that the players’ choices are independent, so we have the following calculation for $i=1,2$:

$$U_i(p_1, p_2)=\sum_{x\in S_1}\sum_{y\in S_2} p_1(x)p_2(y) u_i(x,y)$$

A two-player game $G=\langle S_1, S_2, u_1, u_2\rangle$ is zero-sum provided for each $x\in S_1$ and $y\in S_2$, $u_1(x,y)+u_2(x,y)=0$. We make use of the following fundamental theorem of von Neumann:

Now, we can proceed with the proof of the Lemma. Suppose that $G=\langle N, \{S_i, u_i\}_{i\in N}\rangle$ is a strategic game where each $S_i$ is finite.

Suppose that $s_i\in S_i$ is strictly dominated with respect to $X$. Then there is a $s_i \in S_i$ such that for all $s_{-i}\in X$, $u_i(s_i',s_{-i}) > u_i(s_i,s_{-i})$. Let $p\in\Delta(X)$ be any probability measure. Then for all $s_{-i}\in X$, $0\le p(s_{-i})\le 1$. This means that for all $s_{-i}\in X$, we have $p(s_{-i})\cdot u_i(s_i',s_{-i}) \ge p(s_{-i})\cdot u_i(s_i,s_{-i})$, and there is at least one $s_{-i}\in S_{-i}$ such that

$$p(s_{-i})\cdot u_i(s_i',s_{-i}) > p(s_{-i})\cdot u_i(s_i,s_{-i})$$

(this follows since $p$ is a probability measure on $X$, so cannot assign probability 0 to all elements of $X$). Hence,

$$\sum_{s_{-i}\in S_{-i}} p(s_{-i})\cdot u_i(s_i',s_{-i})> \sum_{s_{-i}\in S_{-i}}p(s_{-i})\cdot u_i(s_i,s_{-i})$$

So, $EU(s_i',p)> EU(s_i,p)$, which means $s_i$ is not a best response to $p$.

For the converse direction, we sketch the proof for two player games. The proof of the more general statement uses the supporting hyperplane theorem from convex analysis. We do not discuss this extension here (note that it is not completely trivial to extend this result to the many agent case as we must allow players to have beliefs about correlated choices of their opponents). Let $G=\langle S_1, S_2, u_1, u_2\rangle$ be a two-player game. Suppose that $\alpha\in \Delta(S_1)$ is not a best response to any $p\in\Delta(S_2)$. This means that for each $p\in \Delta(S_2)$ there is a $q\in\Delta(S_1)$ such that $U_1(q,p)>U_1(\alpha,p)$. We can define a function $b:\Delta(S_2)\rightarrow \Delta(S_1)$ where, for each $p\in\Delta(S_2)$, $U_1(b(p),p)>U_1(\alpha,p)$.

Consider the game $(S_1, S_2, \ou_1, \ou_2)$ where

$$\ou_1(s_1, s_2)=u_1(s_1,s_2) - U_1(\alpha, s_2)$$

and $\ou_2(s_1,s_2)=-\ou_1(s_1,s_2)$. This is a 2-person, zero-sum game, and so by the von Neumann minimax theorem, there is a mixed strategy Nash equilibrium $(p_1^*, p_2^*)$. Then, by the minimax theorem, for all $m\in\Delta(S_2)$, we have

$$\oU(p_1^*, m) \ge \oU_1(p_1^*, p_2^*) \ge \oU_1(b(p_2^*),p_2^*)$$

We now prove that $\oU_1(b(p_2^*),p_2^*)> \oU_1(\alpha,p_2^*)$:

$$\begin{align*} \oU_1(b(p_2^*),p_2^*) &= \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)\ou_1(x,y)\\ &= \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)[u_1(x,y) - U_1(\alpha, y)]\\ &= \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)u_1(x,y) \\ &\quad\quad\quad - \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)U_1(\alpha, y)\\ &= U_1(b(p_2^*), p_2^*) - \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)U_1(\alpha, y)\\ &> U_1(\alpha,p_2^*) - \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)U_1(\alpha, y)\\ &> U_1(\alpha,p_2^*) \end{align*}$$

Since $p_2^*(y) U_1(\alpha, y)$ does not depend on $x$, we have

$$\begin{align*} \sum_{x\in S_1}\sum_{y\in S_2} b(p_2^*)(x)p_2^*(y)U_1(\alpha, y) &= \sum_{x\in S_1} b(p_2^*)(x)\sum_{y\in S_2}p_2^*(y)U_1(\alpha,y)\\ &= \sum_{x\in S_1}b(p_2^*)(x)U_1(\alpha, p_2^*)\\ &= U_1(\alpha,p_2^*)\sum_{x\in S_1}b(p_2^*)(x)\\ &=U_1(\alpha,p_2^*) \end{align*}$$

Hence, for all $m\in\Delta(S_2)$ we have $\oU_1(s_1^*,m)>0$ which implies for all $m\in\Delta(S_2)$, $U_1(s_1^*,m) > U_1(\alpha, m)$, and so $\alpha$ is strictly dominated by $p_1^*$. QED

2. Proof of Theorem 6.1

Theorem 6.1 (Brandenburger & Keisler 2006: Theorem 5.4) There is no assumption-complete type structure for the set of conjectures that contain the first-order definable subsets.

To prove this theorem, we follow an idea recently discussed in Abramsky & Zvesper (2010). Suppose that $\C_A\subseteq\pow(T_A)$ is a set of conjectures about Ann states (similarly, let $\C_B\subseteq\pow(T_B)$ be a set of conjectures about Bob states). We start with the flowing assumption:

For all $X\in \C_A$ there is a $x_0\in T_A$ such that

1. $\lambda_A(x_0)\ne\emptyset$: “in state $x_0$, Ann has consistent beliefs”

2. $\lambda_A(x_0)\subseteq \{y \mid \lambda_B(y)=X\}$: “in state $x_0$, Ann believes that Bob assumes $X$”

To prove the theorem, we need the following lemma.

Proof of Theorem 6.1. Consider the formula $\phi$ in $\L$: $$\phi(x):=\exists y (R_A(x,y) \wedge R_B(y,x))$$

Then, the negation of $\phi$ is:

$\neg\phi(x):=\forall y(R_A(x,y)\rightarrow\neg R_B(y,x))$: “all states $x$ where any state $y$ that Ann considers possible is such that Bob does not consider $x$ possible at $y$.” That is, this formulas says that “Ann believes that Bob’s assumption is wrong.”

Suppose that $X\in\C_A$ is defined by the formula $\neg\phi(x)$.

Suppose that there is a $x_0\in T_A$ such that

1. $\lambda_A(x_0)\ne\emptyset$: Ann’s beliefs at $x_0$ are consistent.

2. $\lambda_A(x_0)\subseteq \{y \mid \lambda_B(y)=X\}$: At $x_0$, Ann believes that Bob assumes $X=\{x \mid \phi(x)\}$ (i.e., Ann believes that Bob assumes that Ann believes that Bob’s assumption is wrong.)

We have

$$\begin{align} \neg\phi(x_0) \text{ is true } &\text{iff } x_0 \in X &\text{(defn of \(X\))} \\ &\text{iff } \text{there is a } y\in T_B \text{ with } y\in\lambda_A(x_0) \\ &\quad\quad\text{and } x_0\in \lambda_B(y) &\text{(Lemma S1)}\\ &\text{iff } \phi(x_0) \text{ is true}. &\text{(defn of \(\phi(x)\))} \end{align}$$

QED