Supplement to Epistemic Foundations of Game Theory
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:
Theorem S2 (von Neumann’s minimax theorem) For every two-player zero- sum game with finite strategy sets \(S_1\) and \(S_2\), there is a number \(v\), called the value of the game such that:
- \(v =\max_{p\in\Delta(S_1)}\min_{q\in \Delta(S_2)} U_1(p,q)\) \( = \min_{q\in \Delta(S_2)}\max_{p\in\Delta(S_1)} U_1(p,q)\)
The set of mixed Nash equilibria is nonempty. A mixed strategy profile \((p,q)\) is a Nash equilibrium if and only if
\begin{align} &p\in \mathrm{argmax}_{p\in\Delta(S_1)}\min_{q\in\Delta(S_2)} U_1(p,q) \\ & q\in \mathrm{argmax}_{q\in\Delta(S_2)}\min_{p\in\Delta(S_1)} U_1(p,q) \end{align}-
For all mixed Nash equilibria \((p,q)\), \(U_1(p,q)=v\)
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
\(\lambda_A(x_0)\ne\emptyset\): “in state \(x_0\), Ann has consistent beliefs”
\(\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.
Lemma S1 Under the above assumption, for each \(X\in \C_A\) there is an \(x_0\) such that \[x_0\in X\text{ iff there is a \(y\in T_B\) such that \(y\in \lambda_A(x_0)\) and \(x_0\in\lambda_B(y)\)}\]
Proof of Lemma S1: Suppose that \(X\in\C_A\). Then there is an \(x_0\in T_A\) satisfying 1 and 2.
Suppose that \(x_0\in X\). By 1., \(\lambda_A(x_0)\ne\emptyset\) so there is a \(y_0\in T_B\) such that \(y_0\in\lambda_A(x_0)\). We show that \(x_0\in\lambda_B(y_0)\). By 2., we have \(y_0\in\lambda_A(x_0)\subseteq \{y \mid \lambda_B(y)=X\}\). Hence, \(x_0\in X=\lambda_B(y_0)\), as desired.
Suppose that there is a \(y_0\in T_B\) such that \(y_0\in\lambda_A(x_0)\) and \(x_0\in \lambda_B(y_0)\). By 2., \(y_0\in\lambda_A(x_0)\subseteq \{y \mid \lambda_B(y)=X\}\). Hence, \(x_0\in\lambda_B(y_0)=X\), as desired.
Consider a first-order language \(\L\) whose signature contains binary relational symbols \(R_A(x,y)\) and \(R_B(x,y)\) defining \(\lambda_A\) and \(\lambda_B\) respectively. The language \(\L\) is interpreted over qualitative type structures where the interpretation of \(R_A\) is the set \(\{(t,s) \mid t\in T_A, s\in T_B, \text{ and }s\in\lambda_A(t)\}\). QED
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
\(\lambda_A(x_0)\ne\emptyset\): Ann’s beliefs at \(x_0\) are consistent.
\(\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