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

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}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}