Independent scholarship · Open accessThe monthly digest

Indexed text attachment

games-and-information-in-higher-categories.tex

Source for Games and Information in Higher Categories

View paper · Download original file

Lines 5741–5840 of 6559. Source text is displayed literally.

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 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