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

859$\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}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 in