Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 941–1040 of 6559. Source text is displayed literally.
941\begin{tikzpicture}[x=1cm,y=1cm]942 \node[ogbox] (P1) at (0,0.9) {$\mathcal{D}_1$};943 \node[dec] (cp) at (1.8,1.15) {};944 \node[ogbox] (P2) at (3.6,-0.9) {$\mathcal{D}_2$};945 \node[ogbox,minimum height=3.3cm] (U) at (6.6,0) {$u$};946 \draw[thick,fwd] (P1.east|-0,1.15) -- node[above=1pt,lab,black]{$A_1$} (cp);947 \draw[fw] (cp) -- (U.west|-0,1.15);948 \draw[fw] (cp) to[out=-60,in=180] (P2.west|-0,-0.65);949 \draw[bw] (U.west|-0,0.65) -- node[below,lab,black,pos=0.3]{$\R$} (P1.east|-0,0.65);950 \draw[fw] (P2.east|-0,-0.65) -- node[above=1pt,lab,black]{$A_2$} (U.west|-0,-0.65);951 \draw[bw] (U.west|-0,-1.15) -- node[below=1.5pt,lab,black]{$\R$} (P2.east|-0,-1.15);952\end{tikzpicture}953\caption{A two-stage game: the second decision observes a copy of the first move.}\label{fig:og-seq}954\end{figure}955 956\section{Selection functions and backward induction}\label{sec:selection}957 958For games of perfect information there is a second compositional structure, older than open games and in959one respect sharper. Fix a set $R$ of outcomes and consider single-valued selection functions.960 961\begin{definition}\Sli[\cite{EO10,EO11}]962Let $J_RX=(X\to R)\to X$ and $K_RX=(X\to R)\to R$. A selection function $\varepsilon\in J_RX$ has an associated963\emph{quantifier} $\overline{\varepsilon}\in K_RX$, $\overline{\varepsilon}(k)=k(\varepsilon(k))$. The964\term{product} of $\varepsilon\in J_RX$ and $\delta\in J_RY$ is $\varepsilon\otimes\delta\in J_R(X\times Y)$,965\[ (\varepsilon\otimes\delta)(q)=(a,b(a)),\qquad b(x)=\delta\bigl(q(x,-)\bigr),\quad a=\varepsilon\bigl(x\mapsto q(x,b(x))\bigr). \]966\end{definition}967 968The definition is backward induction for two moves: $b$ is the second mover's optimal reply to each first969move, and $a$ is the first mover's optimal choice given that reply rule. $J_R$ and $K_R$ are strong monads970(the latter is the continuation monad), $\varepsilon\mapsto\overline{\varepsilon}$ is a monad morphism, and971$\otimes$ is the monoidal structure of $J_R$.972 973\begin{theorem}[Backward induction is a product]\label{thm:EO}\Sli[\cite{EO11}]974Consider a sequential game of perfect information in which player $t=1,\dots,T$ chooses $x_t\in X_t$ after975observing $x_1,\dots,x_{t-1}$, with outcome $q(x_1,\dots,x_T)\in R$, where player $t$ is described by a selection976function $\varepsilon_t\in J_RX_t$ (for instance $\argmax$ with respect to her own coordinate of $R=\R^T$,977with a tie-breaking rule). Then978\[ (\varepsilon_1\otimes\cdots\otimes\varepsilon_T)(q) \]979is the play of a subgame perfect equilibrium, and the equilibrium strategies are obtained from the same980formula applied to the subgames.981\end{theorem}982 983For history-dependent selection functions the product is dependent, and the theorem is unchanged. What is984striking is the infinite case. If each $X_t$ is \emph{searchable}---admits a selection function for every985continuous predicate---and $q$ is continuous in the sense of depending on finitely many moves, then the986infinite product $\bigotimes_t\varepsilon_t$ exists and computes optimal play in a game with no last move987\cite{EO10}. The construction is a form of bar recursion, and it is at the same time a computational proof988of the countable Tychonoff theorem: a product of searchable sets is searchable. We will meet the989continuity hypothesis again in \cref{ch:repetition}, where it is called \emph{continuity at infinity}, and990the searchability hypothesis in \cref{ch:perfection}, where its failure is called the \emph{open-set991problem}.992 993\section{Optics, parameters, and the higher structure}\label{sec:optics}994 995Lenses are the cartesian case of a general construction. Let $(\CC,\otimes)$ be a symmetric monoidal996category.997 998\begin{definition}\Sli[\cite{Ril18,CEGLMPR20}]999An \term{optic} $(X,S)\to(Y,R)$ in $\CC$ is an element of the coend1000\[ \Optic_{\CC}\bigl((X,S),(Y,R)\bigr)=\int^{M\in\CC}\CC(X,M\otimes Y)\times\CC(M\otimes R,S). \]1001\end{definition}1002 1003An optic is represented by a forward map that produces a move together with a \emph{residual} $M$, and a1004backward map that consumes the residual with the returned utility. The coend identifies representatives1005that differ by sliding a map of residuals from one side to the other. When $\CC$ is cartesian the residual1006can always be taken to be $X$ itself, and optics reduce to lenses. When $\CC$ is a category of stochastic1007maps (\cref{ch:belief}) no such reduction is available---one cannot copy a random variable without1008correlating the copies---and it is optics, not lenses, that support \emph{Bayesian open games} \cite{BHZ19},1009in which the forward pass is a Markov kernel and equilibrium is Bayesian Nash equilibrium.1010 1011Three features of this more general setting are ``higher'' in the sense of the Preface.1012 1013\emph{Equality of optics is a quotient with content.} The coend is the set of connected components of a1014category whose objects are representatives $(M,\ell,r)$ and whose morphisms are maps of residuals. Two1015implementations of a game component with different internal memory are the same optic when they are1016connected by a zig-zag of such maps. The classical theory has no place for this identification because it1017has no place for internal memory.1018 1019\emph{Strategies are parameters, and parameters form a bicategory.} For a monoidal category $\CC$,1020$\Para(\CC)$ has morphisms $X\to Y$ given by a parameter object $\Pi$ and a map $\Pi\otimes X\to Y$, and10212-cells given by reparametrizations $\Pi'\to\Pi$. An open game is a lens parametrised by its strategy set1022together with a rule saying which parameters are acceptable. Capucci, Gavranovi\'c, Hedges and Rischel1023\cite{CGHR22} make this the definition: an \emph{arena} is a parametrised optic, the players are attached1024to the parameter boundary, and the equilibrium predicate is a selection function there. The reformulation1025separates the \emph{mechanics} of a game (the arena, which composes on the nose) from its \emph{agency} (who1026controls which parameters, and what they want).1027 1028\emph{Open games have morphisms.} Hedges \cite{Hed18} constructs a symmetric monoidal double category whose1029horizontal 1-cells are open games, whose vertical 1-cells are lenses and whose 2-cells are morphisms of1030open games; the identity type of the type of open games is then the type of invertible 2-cells, and1031\cref{prin:invariance} applies to it.1032 1033\section{What composition does not do}1034 1035It is important not to oversell. \Cref{def:og-comp} makes the equilibrium \emph{predicate} compositional:1036whether $(\sigma,\tau)$ is an equilibrium of $\mathcal{H}\circ\mathcal{G}$ is decided by consulting1037$E_{\mathcal{G}}$ and $E_{\mathcal{H}}$. It does not make the equilibrium \emph{set} of a composite a1038function of the equilibrium sets of its parts in any fixed contexts, because the context in which1039$\mathcal{G}$ is consulted depends on $\tau$. To compose, one must know each part's behaviour in \emph{every}1040context.