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

819$(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\}. \]901  More generally any selection function $\varepsilon$ on $(Y,R)$ gives a decision with902  $E(x,k)=\{\sigma\st\sigma(x)\in\varepsilon(k)\}$.903\item A function $f\colon X\to Y$ gives the \term{forward} game $(X,1)\to(Y,1)$, and a function904  $u\colon Y\to R$ gives the \term{payoff} game $u\colon(Y,R)\to I$, the lens with coplay $y\mapsto u(y)$.905\end{enumerate}906\end{definition}907 908\begin{proposition}[Strategic form]\label{prop:og-nash}\Sli[\cite{GHWZ18}]909Let $G=(N,A,u)$ be a game in strategic form with $N=\{1,\dots,n\}$. The closed game910\[ u\circ\bigl(\mathcal{D}_{1,A_1}\otimes\cdots\otimes\mathcal{D}_{1,A_n}\bigr)\colon I\to I \]911has strategy set $A$ and equilibrium set $\NE(G)$.912\end{proposition}913 914\begin{proof}915For $n=2$: by \cref{def:og-comp}, $(a_1,a_2)$ is an equilibrium iff it is one for916$\mathcal{D}_1\otimes\mathcal{D}_2$ in the context $k=u$, iff $a_1\in\argmax\pi_1u(-,a_2)$ and917$a_2\in\argmax\pi_2u(a_1,-)$. The general case is the same.918\end{proof}