Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5719–5818 of 6559. Source text is displayed literally.
5719be 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 probability5779$1-\bigl(\frac{\bar c}{\bar c+1}\bigr)^2$: this is $\tfrac59$ at $\bar c=2$, tends to $0$ as $\bar c\to\infty$,5780and tends to $\tfrac34$ as $\bar c\to1$. Even when every cost is below the benefit, the good fails to be5781provided a quarter of the time.5782 5783\sol{5.2} The first-order belief of $t_i$ is the image of $\beta_i(t_i)$ under the projection to $\Theta$,5784and $\mathrm{pr}_\Theta\circ(\id\times h_{-i})=\mathrm{pr}_\Theta$; so $h$ preserves first-order beliefs. Let5785$b^k_i$ send a type to its $k$-th order belief, so that5786$b^{k+1}_i=\Giry(\id\times b^k_{-i})\circ\beta_i$. If $b'^k\circ h=b^k$ then5787$b'^{k+1}_i\circ h_i=\Giry(\id\times b'^k_{-i})\Giry(\id\times h_{-i})\beta_i=\Giry(\id\times b^k_{-i})\beta_i=b^{k+1}_i$.5788This is the statement that the maps to the terminal sequence commute with coalgebra homomorphisms.5789 5790\sol{5.3} A $+$ type meets a betting opponent with probability $\tfrac12$, and exactly when $\theta=1$: betting5791pays $\tfrac12>0$. A $-$ type would meet a betting opponent exactly when $\theta=0$: betting pays $-1$. So the5792profile is an equilibrium of $\mathbb{B}$. In $\mathbb{A}$ joint betting pays $\tfrac12-1<0$. The type5793morphism $\mathbb{B}\to\mathbb{A}$ is the pair of constant maps: the image of5794$\beta_i(+)=\tfrac12\delta_{(1,+)}+\tfrac12\delta_{(0,-)}$ is $\tfrac12\delta_{(1,*)}+\tfrac12\delta_{(0,*)}$, the5795belief of the single type of $\mathbb{A}$, and similarly for $-$.5796 5797\sol{5.4} The only cycle is $\omega_1t_1\omega_2t_2$, and the equation is5798$\frac{\beta_1(\omega_2)}{\beta_1(\omega_1)}=\frac{\beta_2(\omega_2)}{\beta_2(\omega_1)}$: agents~1 and~2, who5799have the same information, must hold the same beliefs. Agent~3's edges are pendant and impose nothing.5800 5801\sol{5.5} Write $O_1,O_1'$ for agent~1's odds $\mu(b){:}\mu(a)$ and $\mu(d){:}\mu(c)$, and $O_2,O_2'$ for5802agent~2's odds $\mu(c){:}\mu(a)$ and $\mu(d){:}\mu(b)$; the cycle equation is $O_1O_2'=O_2O_1'$. Suppose5803$O_1O_2'>O_2O_1'$. Let $f=(-A,B,C,-D)$ on $(a,b,c,d)$ with positive entries, agent~1 receiving $f$ and5804agent~2 receiving $-f$. All four types gain iff $A/O_1<B<DO_2'$ and $DO_1'<C<A/O_2$, which is solvable iff5805$O_2O_1'<A/D<O_1O_2'$. For instance if agent~1's posteriors and agent~2's at $t$ are even and agent~2's at5806$t'$ is $(\tfrac13,\tfrac23)$, then $f=(-3,\,3.5,\,2.5,\,-2)$ gives the four types expected gains5807$\tfrac14,\tfrac14,\tfrac14,\tfrac16$. If $\mu$ were a common prior, $\E_\mu f$ would be an average of agent~1's5808conditional expectations, hence positive, and minus an average of agent~2's, hence negative.5809 5810\sol{5.6} $(\E_pf)(t)=\sum_{\omega\in p^{-1}t}\mu(\omega)f(\omega)/\mu(p^{-1}t)$. Then5811$(\E_r\E_pf)(t')=\sum_{t\in r^{-1}t'}\mu(p^{-1}t)(\E_pf)(t)/\mu((rp)^{-1}t')=(\E_{rp}f)(t')$. The Bayesian inverse5812is $p^\dagger_\mu(\omega\mid t)=\mu(\omega)1_{p(\omega)=t}/\mu(p^{-1}t)$, and $\E_pf$ is the composite of $p^\dagger_\mu$5813with $f$ in the Kleisli category. The tower property is $(rp)^\dagger=p^\dagger r^\dagger$.5814 5815\section*{Chapter 6}5816 5817\sol{6.1} If all gains vanish, $f(\sigma)=\sigma$. Conversely $f(\sigma)=\sigma$ gives5818$\sigma_i(a_i)\sum_bg_b(\sigma)=g_{a_i}(\sigma)$ for all $a_i$. If $\sum_bg_b>0$, every action in the support of