Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5679–5778 of 6559. Source text is displayed literally.
5679four equilibria and two outcomes. The two with $s(\mathit{In})=F$ are not subgame perfect.5680 5681\sol{2.3} Write $c(x,y)=\gamma(q(x,y,-))$ and $b(x)=\delta\bigl(y\mapsto q(x,y,c(x,y))\bigr)$ and5682$a=\varepsilon\bigl(x\mapsto q(x,b(x),c(x,b(x)))\bigr)$. Unwinding either bracketing gives $(a,b(a),c(a,b(a)))$.5683For the second identity, with $b(x)=\delta(q(x,-))$ we have $\overline\delta(q(x,-))=q(x,b(x))$, and5684$\overline\varepsilon$ applied to $x\mapsto q(x,b(x))$ is $q(a,b(a))=\overline{\varepsilon\otimes\delta}(q)$. For5685$\max$ and $\min$ this reads $\max_x\min_yq(x,y)$: the product of the selection functions $\argmax$ and5686$\argmin$ plays a two-move zero-sum game optimally, and the product of quantifiers computes its value.5687 5688\sol{2.4} $\int^M\Set(X,M\times Y)\times\Set(M\times R,S)\iso\Set(X,Y)\times\int^M\Set(X,M)\times\Set(M\times R,S)5689\iso\Set(X,Y)\times\Set(X\times R,S)$, the last step by the co-Yoneda lemma applied to the contravariant functor5690$M\mapsto\Set(M\times R,S)$. Concretely, a representative $(M,(\ell_1,\ell_2),r)$ is equivalent, by sliding5691$\ell_1\colon X\to M$, to $(X,(\id,\ell_2),r\circ(\ell_1\times\id))$, which is the lens $(\ell_2,\,r\circ(\ell_1\times\id))$.5692 5693\sol{2.5} The only context for a game $I\to I$ is the trivial one, so by \cref{def:og-comp} the predicate of5694$\mathcal{G}\otimes\mathcal{G}'$ is $E_{\mathcal{G}}\times E_{\mathcal{G}'}$. For the second part let5695$Y=\{a,b\}$, $\mathcal{G}=\mathcal{D}_{1,Y}$, and $\mathcal{H}=u\circ(\id_Y\otimes\mathcal{D}_{1,Y})$ with $u$5696paying $(1,1)$ if the two choices agree and $(0,0)$ otherwise. Then $(a,a)$ is an equilibrium of5697$\mathcal{H}\circ\mathcal{G}$. The context that $\tau$ induces on $\mathcal{G}$ is $y\mapsto1_{y=\tau}$, and $a$5698is an equilibrium of $\mathcal{G}$ only in the context induced by $\tau=a$.5699 5700\section*{Chapter 3}5701 5702\sol{3.1} A map $1\to T$ in $\Trees$ is a family $t_n\in T(n)$ compatible with restriction, that is, an5703infinite branch; so $\Gamma(T)=\lim_nT(n)$. When every node has a child every node lies on a branch. For5704$h\in T(m)$ let $T^{+m}(n)=T(m+n)$; restriction gives a map from $T^{+m}$ to the constant presheaf $T(m)$, and5705$T_h$ is its pullback along $h\colon1\to T(m)$, since limits of presheaves are computed levelwise.5706 5707\sol{3.2} \emph{Symmetric and imperfect:} player~1 chooses $L$ or $R$; player~2, not observing this, chooses5708$l$ or $r$. Player~2's two nodes form one information set, so information is imperfect. At that set the5709mover knows less than player~1, and at the root nobody knows anything; at the end all know the play. No5710mover has an informational advantage. \emph{Certain and asymmetric:} Nature chooses one of two types at the5711root, observed by player~1 only; player~1 moves, then player~2. Nature does not move after a player, so5712information is certain. At player~1's nodes her information set is a singleton and does not contain5713player~2's, so information is asymmetric (and incomplete).5714 5715\sol{3.3} Nature chooses $a$ or $b$; player~1 observes it and moves at $g_a$ or $g_b$, which lie in different5716information sets; she moves again at $h_a$ (after $g_a$) or $h_b$ (after $g_b$), and these lie in one5717information set. Her personal forest has $g_a,g_b$ at depth $0$ and $h_a,h_b$ at depth $1$, and the5718levelwise quotient has two classes at depth $0$ and one at depth $1$. The parent of $[h_a]=[h_b]$ would have to5719be both $[g_a]$ and $[g_b]$: the square expressing naturality of the quotient with respect to restriction5720does not commute. In the ``forgetting'' example of the text the parents agree and it is the edge labelling5721that fails to descend.5722 5723\sol{3.4} Let player~2 choose $L$ with probability $q$. \emph{Out} pays $2$, $T$ pays $3q$, $B$ pays $1-q$. So5724\emph{Out} is a best response iff $q\le\tfrac23$, and $(T,L)$ is an equilibrium. Player~1 cannot mix \emph{Out}5725with $T$: indifference needs $q=\tfrac23$, but any weight on $T$ and none on $B$ makes $L$ strictly better for5726player~2. The mixed equilibrium of the subgame pays player~1 only $\tfrac34$, so it is not an equilibrium of5727the whole game. Hence the Nash equilibria are $(T,L)$ and $(\mathit{Out},q)$, $q\le\tfrac23$. In the subgame:5728$(T,L)$, $(B,R)$, and the mixed profile with $p=\tfrac34$ (from $p=3(1-p)$) and $q=\tfrac14$ (from $3q=1-q$).5729 5730\sol{3.5} No. After the interchange the subgame following \emph{In} is rooted at a node of player~2, but it5731contains the same terminal nodes and has the same strategic form. The subgame perfect equilibria are as5732before: $(\mathit{In},T;L)$ and \emph{Out} followed by $q\in\{0,\tfrac14\}$. Interchange preserved the5733collection of subgames; coalescing did not.5734 5735\sol{3.6} The variables are $r(\varsigma)$ for the empty sequence and for each pair $(I,a)$: $1+\sum_I|A(I)|$ of5736them. The equations $r(\emptyset)=1$ and $\sum_ar(\varsigma_Ia)=r(\varsigma_I)$, one for each $I$, are5737independent, each introducing variables not constrained by the earlier ones, and with $r\ge0$ they force5738$r\le1$. A fully mixed behavioural strategy gives a point with all coordinates positive, so the set is a5739polytope of dimension $\sum_I(|A(I)|-1)$. The mixed-strategy simplex has dimension $\prod_I|A(I)|-1$:5740with ten binary information sets, $10$ against $1023$.5741 5742\section*{Chapter 4}5743 5744\sol{4.1} All of them. $\K=p^*\forall_p$ is a comonad on a poset, hence idempotent, whatever $p$ is; (iii) and5745(iv) use only the adjunctions; (v) uses only that $p^*$ preserves complements. $\K$ depends on $p$ only5746through its kernel partition of $\Omega$. What fails is a step of the proof given, $\forall_pp^*=\id$:5747without surjectivity $\forall_pp^*D=D\cup(T\setminus\mathrm{im}\,p)$, statements about unrealized types being5748vacuously known.5749 5750\sol{4.2} In the structure on the left of \cref{fig:Bgraph} with $E=\{a,b,c,d\}$: $\K_1\K_2E=\{a,b\}$ but5751$\K_2\K_1E=\{a,b,c\}$ (see the next solution). For the inclusion: $\CK E$ is self-evident, so5752$\CK E=\K(\CK E)\subseteq\K_i(\CK E)\subseteq\CK E$ and $\K_i\CK E=\CK E$ for each $i$. By monotonicity5753$\CK E=\K_{i_1}\cdots\K_{i_m}\CK E\subseteq\K_{i_1}\cdots\K_{i_m}E$.5754 5755\sol{4.3} $\K_1E=\{a,b,c,d\}$, $\K_2E=\{a,b,c\}$, $\K_1\K_2E=\{a,b\}$, and $\CK E=\emptyset$ since the meet5756is trivial and $E\ne\Omega$. Everyone knows $E$ on $\K_1E\cap\K_2E=\{a,b,c\}$, and $E$ is common knowledge5757nowhere. The iterates of ``everyone knows'' shrink one state at a time: $\{a,b,c\}$, $\{a,b\}$, $\{a\}$,5758$\emptyset$.5759 5760\sol{4.4} Left: $(2-1)\cdot5-(3+3)+1=0$. Right: $4-(2+2)+1=1$. In the product structure the state $(s,t)$5761is an edge joining $s$ and $t$, so $B$ is $K_{m,n}$, connected, with $b_1=mn-(m+n)+1=(m-1)(n-1)$. If $p_1$ is5762the identity, each state is an edge from its own singleton cell, a vertex of degree one, to a cell of5763agent~2: a disjoint union of stars, and $b_1=|\Omega|-(|\Omega|+|T_2|)+|T_2|=0$.5764 5765\sol{4.5} Distributed knowledge of $E$ at $\omega$ means that the intersection of the agents' cells at $\omega$5766lies in $E$. That intersection is the fibre of the pairing $\langle p_i\rangle$ through $\omega$, a cell of the5767join; so $D=p_\vee^*\forall_{p_\vee}$. $\CK E\subseteq\K_iE$ is the case $m=1$ of Exercise~4.2;5768$\K_iE\subseteq DE$ because the join's cell is contained in agent $i$'s; $DE\subseteq E$ is the truth axiom.5769 5770\sol{4.6} $B$ has vertices $\omega_1,\omega_2$ and $t_1,t_2,t_3,t_3'$, with each state joined to $t_1$ and5771$t_2$ and to its own type of agent~3: six vertices, six edges, one component, so $b_1=1$ and5772$\pi_1(B)\iso\Z$, generated by the square $\omega_1t_1\omega_2t_2$. $\mathcal{C}$ is the two triangles5773$\{t_1,t_2,t_3\}$ and $\{t_1,t_2,t_3'\}$ glued along the edge $\{t_1,t_2\}$; it is contractible.5774 5775\section*{Chapter 5}5776 5777\sol{5.1} If the other player uses the cutoff $c^*$ she contributes with probability $c^*/\bar c$, so5778$c^*=1-c^*/\bar c$ and $c^*=\frac{\bar c}{\bar c+1}$. The good is provided with probability