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

801\chapter{Open Games}\label{ch:open}802 803A game in strategic form is a closed system. There is no operation that takes two such games and plugs the804outcome of one into the payoffs of the other, or runs one after the other with the second player watching805the first; each new situation is modelled from scratch. Yet informally games are built from parts all the806time---``a bargaining stage followed by a production stage'', ``the same market in each of two periods''.807This chapter presents the calculus, due to Ghani, Hedges, Winschel and Zahn \cite{GHWZ18,Hed16}, in which808that informal practice is literal: a game with open boundaries is a morphism, and games compose.809 810\section{Lenses}811 812The boundary of an open game carries information in two directions. Forwards flow observations and moves;813backwards flows value. The algebra of such two-way boundaries is the category of lenses.814 815\begin{definition}\label{def:lens}816A \term{lens} $(X,S)\to(Y,R)$ between pairs of sets is a pair $\lambda=(v,c)$ of functions817\[ v\colon X\to Y\qquad\text{(view, or play)},\qquad c\colon X\times R\to S\qquad\text{(update, or coplay)}. \]818The composite of $(v,c)\colon(X,S)\to(Y,R)$ and $(v',c')\colon(Y,R)\to(Z,Q)$ has view $v'\circ v$ and update819$(x,q)\mapsto c\bigl(x,c'(v(x),q)\bigr)$. Lenses form a symmetric monoidal category $\Lens$ with820$(X,S)\otimes(X',S')=(X\times X',S\times S')$ and unit $I=(1,1)$.821\end{definition}822 823Two families of lenses matter immediately. A lens $I\to(X,S)$ is an element $x\in X$: a \emph{state}, or824history. A lens $(Y,R)\to I$ is a function $k\colon Y\to R$: a \emph{costate}---which is precisely a decision825problem in the sense of \cref{def:decision}, a context assigning to each move its consequence. Composing a826lens $\lambda\colon(X,S)\to(Y,R)$ with a costate $k$ gives a costate $k\circ\lambda\colon x\mapsto c(x,k(v(x)))$827on $(X,S)$: lenses transport contexts backwards. This is the whole idea. A piece of a game is a process828that turns what it sees into what it does, and turns the value of what it does into the value of what it829saw.830 831\section{Open games}832 833\begin{definition}[Open game]\label{def:opengame}\Sli[\cite{GHWZ18}; predicate form as in \cite{BHZ19}]834An \term{open game} $\mathcal{G}\colon(X,S)\to(Y,R)$ consists of835\begin{itemize}836\item a set $\Sigma_{\mathcal{G}}$ of strategy profiles;837\item for each $\sigma\in\Sigma_{\mathcal{G}}$ a lens $\mathcal{G}_\sigma=(P_\sigma,C_\sigma)\colon(X,S)\to(Y,R)$, the838  \emph{play} and \emph{coplay} under $\sigma$;839\item an \term{equilibrium predicate} $E_{\mathcal{G}}\colon X\times(Y\to R)\to\Pow(\Sigma_{\mathcal{G}})$,840  assigning to each context $(x,k)$---a state of the source and a costate of the target---the set of841  profiles that are in equilibrium in that context.842\end{itemize}843\end{definition}844 845\begin{figure}[ht]\centering846\begin{tikzpicture}[x=1cm,y=1cm]847  \node[ogbox,minimum width=1.5cm,minimum height=1.25cm] (G) at (0,0) {$\mathcal{G}$};848  \draw[fw] (-2.4,0.3) -- node[above=1pt,lab,black]{$X$ observed} (G.west|-0,0.3);849  \draw[fw] (G.east|-0,0.3) -- node[above=1pt,lab,black]{$Y$ chosen} (2.4,0.3);850  \draw[bw] (2.4,-0.3) -- node[below=1.5pt,lab,black]{$R$ utility} (G.east|-0,-0.3);851  \draw[bw] (G.west|-0,-0.3) -- node[below=1.5pt,lab,black]{$S$ coutility} (-2.4,-0.3);852\end{tikzpicture}853\caption{An open game $\mathcal{G}\colon(X,S)\to(Y,R)$.}\label{fig:opengame}854\end{figure}855 856The four boundary sets are read as in \cref{fig:opengame}: $X$ is what the game observes of the past, $Y$857what it contributes to the future, $R$ the utility it receives from the future and $S$ the858\emph{coutility} it passes back to the past. The original definition records a best-response relation on859$\Sigma_{\mathcal{G}}$ in each context rather than its set of fixed points; nothing below depends on the860difference.861 862\begin{definition}[Composition]\label{def:og-comp}863Let $\mathcal{G}\colon(X,S)\to(Y,R)$ and $\mathcal{H}\colon(Y,R)\to(Z,Q)$. The \term{sequential composite}864$\mathcal{H}\circ\mathcal{G}$ has $\Sigma=\Sigma_{\mathcal{G}}\times\Sigma_{\mathcal{H}}$, lenses865$\mathcal{H}_\tau\circ\mathcal{G}_\sigma$, and866\[ (\sigma,\tau)\in E_{\mathcal{H}\circ\mathcal{G}}(x,k)\iff867   \begin{cases}\sigma\in E_{\mathcal{G}}\bigl(x,\,k\circ\mathcal{H}_\tau\bigr)\ \text{ and}\\[2pt]868   \tau\in E_{\mathcal{H}}\bigl(P_\sigma(x),\,k\bigr).\end{cases} \]869For $\mathcal{G}\colon(X,S)\to(Y,R)$ and $\mathcal{G}'\colon(X',S')\to(Y',R')$ the \term{parallel composite}870$\mathcal{G}\otimes\mathcal{G}'$ has $\Sigma=\Sigma_{\mathcal{G}}\times\Sigma_{\mathcal{G}'}$, lenses871$\mathcal{G}_\sigma\otimes\mathcal{G}'_{\sigma'}$, and872\[ (\sigma,\sigma')\in E_{\mathcal{G}\otimes\mathcal{G}'}((x,x'),k)\iff873   \sigma\in E_{\mathcal{G}}(x,k_1)\ \text{ and }\ \sigma'\in E_{\mathcal{G}'}(x',k_2), \]874\noindent875where $k_1(y)=\pi_1k\bigl(y,P'_{\sigma'}(x')\bigr)$ and $k_2(y')=\pi_2k\bigl(P_\sigma(x),y'\bigr)$.876\end{definition}877 878Read the two clauses of sequential composition as a sentence. The earlier game $\mathcal{G}$ is in879equilibrium when it is so in the context in which its future is \emph{the later game played according to880$\tau$}; the later game $\mathcal{H}$ is in equilibrium when it is so at the history that $\sigma$ actually881produces. In parallel composition each component faces a context in which the other's move is held at its882equilibrium value. Unilateral deviation, the defining idea of Nash equilibrium, is thus not an axiom about883profiles; it is \emph{what composition of contexts means}.884 885\begin{theorem}\label{thm:og-smc}\Sli[\cite{GHWZ18}]886Open games, identified up to bijections of their strategy sets compatible with the remaining data, are the887morphisms of a symmetric monoidal category $\OG$ whose objects are pairs of sets. Every lens is an open888game with $\Sigma=1$ and trivially true equilibrium predicate, giving a symmetric monoidal functor889$\Lens\to\OG$.890\end{theorem}891 892\section{Atoms and the strategic form}893 894Two kinds of atom generate the examples of this book.895 896\begin{definition}\label{def:atoms}897\begin{enumerate}[label=(\alph*)]898\item The \term{decision} $\mathcal{D}_{X,Y}\colon(X,1)\to(Y,\R)$ of an agent who observes $X$, chooses in $Y$899  and maximizes has $\Sigma=(X\to Y)$, play $P_\sigma(x)=\sigma(x)$, trivial coplay, and900  \[ E(x,k)=\{\sigma \st \sigma(x)\in\argmax k\}. \]