Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5619–5718 of 6559. Source text is displayed literally.
5619computation, the numbers below are recomputed by the script of \cref{app:computations}.5620 5621\section*{Chapter 1}5622 5623\sol{1.1} The obedience constraint for player $i$ involves payoffs only through the differences5624$u_i(a_i,a_{-i})-u_i(a_i',a_{-i})$. Under $u_i\mapsto\alpha_iu_i+\beta_i(a_{-i})$ each difference is multiplied by5625$\alpha_i>0$, so the system of inequalities is unchanged. For efficiency, take the Battle of the Sexes of5626\cref{ex:three} and add $5$ to the row player's payoff whenever the column player chooses $F$. The profile5627$(F,F)$ now pays $(6,2)$ and Pareto-dominates $(O,O)$, which pays $(2,1)$ and was efficient before; both5628remain Nash equilibria.5629 5630\sol{1.2} An automorphism is a permutation of the players together with bijections of action sets5631preserving payoffs. Payoffs depend only on whether the actions agree, so the two bijections must be the5632same permutation $\pi\in S_m$, with or without exchanging the players: $\Aut(G)\iso S_m\times\Z/2$. In the5633framed game $\pi$ must fix action $1$, and the group is $S_{m-1}\times\Z/2$. An invariant profile is5634symmetric, with each player putting weight $x$ on action $1$ and $(1-x)/(m-1)$ on each other action. A5635player's payoff from an action is the probability the other puts on it, so the support must consist of5636actions of maximal probability. This leaves three invariant equilibria: $x=1$ (both play the distinguished5637action, payoff $1$); $x=0$ (uniform on the undistinguished actions, payoff $\frac1{m-1}$); and $x=\frac1m$5638(uniform on all, payoff $\frac1m$). The first is now selectable.5639 5640\sol{1.3} Let the row player's payoffs be $T=(3,0)$, $M=(1,1)$, $B=(0,3)$ against columns $L,R$. $M$ is not5641dominated by $T$ (against $R$) nor by $B$ (against $L$), but $\tfrac12T+\tfrac12B$ pays $(1.5,1.5)$. If the5642column player chooses $L$ with probability $q$, then $T$ pays $3q$ and $B$ pays $3(1-q)$, and5643$\max\{3q,3(1-q)\}\ge1.5>1$: $M$ is never a best response.5644 5645\sol{1.4} Her selection function is $\varepsilon(k)=\argmin_x\,|x-\tfrac23k(x)|$. It is not of the form5646$\argmax(v\circ k)$ for any $v\colon\R\to\R$: on a constant context $k$, $\argmax(v\circ k)$ is all of $X$, while5647$\varepsilon(k)$ is a single point depending on the constant. Her objective depends on her action and on the5648outcome jointly. For the game, write the signed distance as $x_i(1-\frac{2}{3n})-\frac{2}{3n}\sum_{j\ne i}x_j$,5649increasing in $x_i$. If the largest choice in a profile is $M\ge2$, a player choosing $M$ is above her5650target by at least $M/3\ge\tfrac23$, and lowering her choice by one reduces the signed distance by less than $1$5651while keeping its absolute value smaller; so she deviates. Hence everyone chooses $1$, and one checks directly5652that this is an equilibrium: at $1$ the distance is $\tfrac13$, at $2$ it is $\tfrac43-\tfrac{2}{3n}\ge1$, and it grows with the choice.5653 5654\sol{1.5} If $R\subseteq R'$ then $\Dist(R_{-i})\subseteq\Dist(R'_{-i})$, so every action justified by a conjecture5655on $R_{-i}$ is justified by one on $R'_{-i}$: $\Phi(R)\subseteq\Phi(R')$. If $\sigma$ is a (mixed) Nash equilibrium5656let $R$ be the product of the supports. Each action in the support of $\sigma_i$ is a best response to5657$\sigma_{-i}\in\Dist(R_{-i})$, so $R\subseteq\Phi(R)$, and by coinduction $R\subseteq\nu\Phi$.5658 5659\sol{1.6} At each round the set of weakly dominated actions of each player in the current restriction is5660determined, and it is never all of a player's actions (an action maximizing the sum of payoffs over the5661opponents' 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 to