Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5661–5760 of 6559. Source text is displayed literally.
5661opponents' profiles is undominated). So the procedure involves no choices and terminates. Weak dominance5662depends only on the signs of own-payoff differences against each opponent profile, which incentive5663equivalence preserves. On \cref{ex:weakdom}: round one deletes $T$ and $B$ and neither column; round two5664deletes nothing. The output $\{M\}\times\{L,R\}$ differs from both sequential outputs, $\{M,B\}\times\{R\}$ and5665$\{T,M\}\times\{L\}$. What has been bought is a function. The price is that the function is a convention:5666it is not stable under first removing a dominated action by hand, so the dependence on order has been5667hidden in the definition rather than removed.5668 5669\section*{Chapter 2}5670 5671\sol{2.1} For lenses $(v_j,c_j)$, $j=1,2,3$, both bracketings have view $v_3v_2v_1$ and update5672$(x,p)\mapsto c_1\bigl(x,c_2(v_1x,c_3(v_2v_1x,p))\bigr)$. A lens $I\to(X,S)$ is a view $1\to X$, an element, with5673a forced update $1\times S\to1$. A lens $(Y,R)\to I$ has a forced view and an update $Y\times1\to R$.5674 5675\sol{2.2} Strategies are pairs $(a_1,s)$ with $s\colon\{\mathit{Out},\mathit{In}\}\to\{A,F\}$. The predicate5676requires $a_1\in\argmax_au_1(a,s(a))$ and $s(a_1)\in\argmax u_2(a_1,-)$. If $s(\mathit{In})=A$ then5677$a_1=\mathit{In}$ and the second condition holds; $s(\mathit{Out})$ is free. If $s(\mathit{In})=F$ then5678$a_1=\mathit{Out}$, and after \emph{Out} player~2 is indifferent, so again $s(\mathit{Out})$ is free. There are5679four 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)$