Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 901–1000 of 6559. Source text is displayed literally.
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}919 920This is \cref{fig:intro-pd}. The proposition is not deep; its content is that the classical definition has921been \emph{derived} from two generic operations and one atom, so that it is available wherever those922operations are.923 924\begin{example}[Sequential play, and a warning]\label{ex:og-seq}925Let player~1 choose $a_1\in A_1$ and player~2, observing $a_1$, choose $a_2\in A_2$, with payoffs926$u\colon A_1\times A_2\to\R^2$. The diagram is \cref{fig:og-seq}: $\mathcal{D}_{1,A_1}$, then a copy of $a_1$927alongside $\mathcal{D}_{A_1,A_2}$, then $u$. The strategy set is $A_1\times(A_1\to A_2)$, and unwinding928\cref{def:og-comp},929\[ (a_1,s)\ \text{is an equilibrium}\iff930 \begin{cases} a_1\in\argmax_{a}u_1(a,s(a))\ \text{ and}\\[2pt] s(a_1)\in\argmax u_2(a_1,-).\end{cases} \]931Player~1 optimizes against player~2's whole plan $s$; player~2 optimizes \emph{at the history that occurs}.932At histories $a\neq a_1$ the plan $s$ is unconstrained. These are the Nash equilibria of the sequential933game, including those sustained by threats that player~2 would not carry out. Sequential composition as934defined here does not by itself deliver subgame perfection. The thesis \cite{Hed16} recovers subgame935perfect equilibria of perfect-information games by a further construction, \cite{Hed18} by a notion of936state for a double category of open games, and \cite{GKLF18} for iterated games; in \cref{ch:perfection} we937will see perfection as a modality applied on top of the equilibrium predicate.938\end{example}939 940\begin{figure}[ht]\centering941\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). \]