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 1059–1158 of 6559. Source text is displayed literally.

1059closest to the presentation here is \cite{BHZ19}, which also introduces contexts for optics. Lenses come1060from the theory of bidirectional transformations; their systematic generalization to optics is1061\cite{Ril18,CEGLMPR20}. Alternative axiomatizations that make the proof of \cref{thm:og-smc} itself1062compositional are given in \cite{AGGKLN21}, and the translation from extensive-form games into open games1063with agency is \cite{CGLN22}. Selection functions and their products are due to Escard\'o and Oliva1064\cite{EO10,EO11}; \cite{HOSWZ17} uses them to define equilibria for agents who do not maximize. A metric1065refinement, in which equilibrium predicates are relaxed by an $\epsilon$ budget compatibly with1066composition, is \cite{Gha25}. Earlier categorical treatments of games, which take games as objects rather1067than morphisms, are surveyed in \cite{TV23}.1068 1069\section*{Exercises}1070 1071\begin{exercise}1072Verify that composition of lenses is associative, and that a lens $I\to(X,S)$ is an element of $X$ while a1073lens $(Y,R)\to I$ is a function $Y\to R$.1074\end{exercise}1075\begin{exercise}1076Using \cref{def:og-comp}, compute the equilibrium predicate of the closed game of \cref{ex:og-seq} for the1077entry game in which player~1 chooses \emph{Out} (payoffs $(0,4)$) or \emph{In}, after which player~2 chooses1078\emph{Accommodate} $(1,2)$ or \emph{Fight} $(-1,0)$. List all equilibria and identify the one that is not1079subgame perfect.1080\end{exercise}1081\begin{exercise}1082Show that $(\varepsilon\otimes\delta)\otimes\gamma=\varepsilon\otimes(\delta\otimes\gamma)$ for selection1083functions, and that $\overline{\varepsilon\otimes\delta}(q)=\overline{\varepsilon}\bigl(x\mapsto\overline{\delta}(q(x,-))\bigr)$.1084Interpret the second identity when $\overline{\varepsilon}=\max$ and $\overline{\delta}=\min$.1085\end{exercise}1086\begin{exercise}1087For $\CC=\Set$ with cartesian product, prove that the coend defining $\Optic_\CC$ reduces to the set of lenses.1088(Use the bijection $\Set(X,M\times Y)\cong\Set(X,M)\times\Set(X,Y)$ and the co-Yoneda lemma.)1089\end{exercise}1090\begin{exercise}1091Let $\mathcal{G},\mathcal{G}'\colon I\to I$ be closed games. Show that the equilibria of $\mathcal{G}\otimes\mathcal{G}'$1092are the pairs of equilibria. Then give open games $\mathcal{G}\colon I\to(Y,R)$ and $\mathcal{H}\colon(Y,R)\to I$1093such that $\mathcal{H}\circ\mathcal{G}$ has an equilibrium $(\sigma,\tau)$ although $\sigma$ is not an equilibrium of1094$\mathcal{G}$ in the context induced by any $\tau'\neq\tau$.1095\end{exercise}1096%% ---- end ch/02-open.tex ----1097%% ---- begin ch/03-extensive.tex ----1098\chapter{The Extensive Form}\label{ch:extensive}1099 1100The strategic form hides time and information inside the word ``strategy''. The extensive form displays1101them: a tree of histories, a rule saying who moves where, and for each player a partition of her decision1102nodes into sets she cannot tell apart. This chapter sets up the extensive form in a way that makes its two1103structural hypotheses---that histories form a tree, and that players remember---into statements about a1104topos; it then confronts the question of \cref{ch:rules} in its sharpest classical form: when are two trees1105the same game?1106 1107\section{Trees are presheaves}1108 1109Let $\omega$ be the poset $0<1<2<\cdots$ regarded as a category.1110 1111\begin{definition}1112A \term{forest} is a presheaf $T\colon\omega^{\op}\to\Set$: a sequence of sets $T(n)$ with restriction maps1113$T(n+1)\to T(n)$. An element of $T(n)$ is a \term{node} of depth $n$, and its image in $T(n-1)$ is its1114\term{parent}. A forest is a \term{tree} if $T(0)=1$. The category of forests is the presheaf topos1115$\Trees=\Set^{\omega^{\op}}$.1116\end{definition}1117 1118That forests are exactly presheaves on $\omega$ is an old observation; the topos $\Trees$ has acquired the1119name \emph{topos of trees} in the semantics of guarded recursion \cite{BMSS12}, and we will use it in that1120role in \cref{ch:repetition}. Three pieces of tree vocabulary are topos vocabulary.1121 1122\begin{itemize}1123\item A \emph{play} of infinite length is a compatible sequence of nodes, that is, a global section1124  $1\to T$; the set of plays is $\Gamma(T)=\lim_nT(n)$. (A tree with terminal nodes is brought under this1125  description by giving each terminal node a single dummy successor forever.)1126\item The \emph{subtree} at a node $h\in T(m)$ is the forest $T_h(n)=\{t\in T(m+n)\st t\mapsto h\}$, a fibre of a1127  restriction map.1128\item A \emph{labelling} of edges by actions is a map of forests from $T$ to the forest of finite words over1129  an alphabet.1130\end{itemize}1131 1132\begin{definition}\label{def:efg}1133A finite \term{extensive game} $\Gamma$ consists of1134\begin{enumerate}[label=(\roman*)]1135\item a finite tree $T$, with node set $H$, terminal nodes $Z\subseteq H$ and decision nodes $D=H\setminus Z$;1136\item a map $\iota\colon D\to N\sqcup\{0\}$ assigning each decision node to a player or to Nature ($0$), and1137  at each node of Nature a probability distribution on its children;1138\item for each player $i$ an equivalence relation $\sim_i$ on $D_i=\iota^{-1}(i)$, whose classes are $i$'s1139  \term{information sets}, forming a set $\mathcal{I}_i$ with quotient map $q_i\colon D_i\twoheadrightarrow\mathcal{I}_i$;1140\item for each information set $I$ a set $A(I)$ of actions and, for each $h\in I$, a bijection between1141  $A(I)$ and the children of $h$;1142\item payoffs $u\colon Z\to\R^N$.1143\end{enumerate}1144\end{definition}1145 1146A pure strategy of player $i$ chooses an action at each of her information sets. The actions form a bundle1147$\coprod_IA(I)\to\mathcal{I}_i$, and a pure strategy is a section of it:1148\[ S_i=\prod_{I:\mathcal{I}_i}A(I). \]1149A \term{behavioural strategy} is a section of the bundle of lotteries, $\beta_i\in\prod_I\Dist A(I)$; a1150\term{mixed strategy} is a lottery over sections, $\mu_i\in\Dist\bigl(\prod_IA(I)\bigr)$. A profile of1151strategies of any of these kinds, with Nature's distributions, induces a distribution over terminal nodes,1152and taking expected payoffs gives the \term{strategic form} of $\Gamma$, a game in the sense of1153\cref{def:nfg}. The requirement that a strategy be a function on $\mathcal{I}_i$ rather than on $D_i$ is the1154entire formal content of ``not knowing'': a plan must factor through the quotient $q_i$.1155 1156\section{A taxonomy of information}1157 1158Informational assumptions are properties of the family of quotient maps $(q_i)$ and of the position of