Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5759–5858 of 6559. Source text is displayed literally.
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 of5819$\sigma_i$ would have positive gain, that is, would do strictly better than $\sigma_i$ against $\sigma_{-i}$.5820But the payoff of $\sigma_i$ is the average of the payoffs of the actions in its support, and not all of5821them can exceed their average. So all gains vanish.5822 5823\sol{6.2} $(a,a)$, $(b,b)$, and the mixed profile in which each plays $a$ with probability $\tfrac13$5824(from $2p=1-p$), worth $\tfrac23$. With $u_1(b,b)=1+t$ the column player's mixture must satisfy5825$2q=(1+t)(1-q)$, so $q=\frac{1+t}{3+t}$, while $p=\tfrac13$ is unchanged. The mixed equilibrium exists iff5826$t>-1$. At $t=-1$ it merges with $(b,b)$ into a segment of equilibria, and for $t<-1$ action $a$ is dominant5827for the row player and only $(a,a)$ remains: indices $+1$ and $-1$ have cancelled.5828 5829\sol{6.3} Obedience for a row player told $C$ reads $-\pi(C,C)-\pi(C,D)\ge0$, so $\pi(C,\cdot)=0$; likewise5830$\pi(\cdot,C)=0$. In general let $\sigma_i$ strictly dominate $a_i$ and average the obedience constraints5831for $a_i$ over $a_i'\sim\sigma_i$: $\sum_{a_{-i}}\pi(a_i,a_{-i})[u_i(a_i,a_{-i})-u_i(\sigma_i,a_{-i})]\ge0$ with every5832bracket negative, so $\pi(a_i,\cdot)=0$.5833 5834\sol{6.4} Put $\pi(C,C)=x$, $\pi(C,D)=\pi(D,C)=y$, $\pi(D,D)=z$, $x+2y+z=1$. Obedience after $C$ is5835$-x+2y\ge0$ and after $D$ is $y-2z\ge0$. In the $(x,z)$ plane the polytope is $2x+z\le1$, $x+5z\le1$,5836$x,z\ge0$, with vertices $(0,0)$, $(\tfrac12,0)$, $(\tfrac49,\tfrac19)$ and $(0,\tfrac15)$; the third is the5837mixed Nash equilibrium. The sum of payoffs is $12x+18y=9+3x-9z$, maximal at5838$(x,y,z)=(\tfrac12,\tfrac14,0)$, worth $5.25$ to each player. This improves on the distribution of5839\cref{ex:chicken}, which is interior to an edge of the polytope.5840 5841\sol{6.5} Let a public device name one player uniformly at random, who then acts alone. The named player5842gets $b-c>0$ rather than $0$; the others get $b$ rather than $b-c$. The good is always provided, and each5843player expects $b-c/n$. The distribution over profiles is invariant under all permutations of the players.5844It maximizes total surplus, so it is the best invariant correlated equilibrium. The symmetric mixed5845equilibrium, also invariant, gives each player only $b-c$. Correlation can respect a symmetry \emph{ex ante}5846while breaking it \emph{ex post}, which independent randomization cannot.5847 5848\sol{6.6} The marginals of $\mu\otimes\nu$ are $\mu$ and $\nu$, so $\nabla$ is injective; and5849$\Dist(f\times g)(\mu\otimes\nu)=\Dist f(\mu)\otimes\Dist g(\nu)$. If $x\ne x'$ and $y\ne y'$, the distribution5850$\tfrac12\delta_{(x,y)}+\tfrac12\delta_{(x',y')}$ is not a product, since a product with its marginals gives5851$(x,y')$ probability $\tfrac14$. If $X$ or $Y$ is a point the map is a bijection, and if one is empty both5852sides are empty.5853 5854\section*{Chapter 7}5855 5856\sol{7.1} $\bot\le f(\bot)$, so $f^k(\bot)$ is increasing and stabilizes in a finite lattice at a fixed point,5857which lies below every fixed point $y$ because $f^k(\bot)\le f^k(y)=y$. Dually from $\top$. For fixed points5858$x,y$, $z=x\vee y$ satisfies $z\le f(z)$, and iterating $f$ from $z$ reaches the least fixed point above both;