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

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). \]1001\end{definition}1002 1003An optic is represented by a forward map that produces a move together with a \emph{residual} $M$, and a1004backward map that consumes the residual with the returned utility. The coend identifies representatives1005that differ by sliding a map of residuals from one side to the other. When $\CC$ is cartesian the residual1006can always be taken to be $X$ itself, and optics reduce to lenses. When $\CC$ is a category of stochastic1007maps (\cref{ch:belief}) no such reduction is available---one cannot copy a random variable without1008correlating the copies---and it is optics, not lenses, that support \emph{Bayesian open games} \cite{BHZ19},1009in which the forward pass is a Markov kernel and equilibrium is Bayesian Nash equilibrium.1010 1011Three features of this more general setting are ``higher'' in the sense of the Preface.1012 1013\emph{Equality of optics is a quotient with content.} The coend is the set of connected components of a1014category whose objects are representatives $(M,\ell,r)$ and whose morphisms are maps of residuals. Two1015implementations of a game component with different internal memory are the same optic when they are1016connected by a zig-zag of such maps. The classical theory has no place for this identification because it1017has no place for internal memory.1018 1019\emph{Strategies are parameters, and parameters form a bicategory.} For a monoidal category $\CC$,1020$\Para(\CC)$ has morphisms $X\to Y$ given by a parameter object $\Pi$ and a map $\Pi\otimes X\to Y$, and10212-cells given by reparametrizations $\Pi'\to\Pi$. An open game is a lens parametrised by its strategy set1022together with a rule saying which parameters are acceptable. Capucci, Gavranovi\'c, Hedges and Rischel1023\cite{CGHR22} make this the definition: an \emph{arena} is a parametrised optic, the players are attached1024to the parameter boundary, and the equilibrium predicate is a selection function there. The reformulation1025separates the \emph{mechanics} of a game (the arena, which composes on the nose) from its \emph{agency} (who1026controls which parameters, and what they want).1027 1028\emph{Open games have morphisms.} Hedges \cite{Hed18} constructs a symmetric monoidal double category whose1029horizontal 1-cells are open games, whose vertical 1-cells are lenses and whose 2-cells are morphisms of1030open games; the identity type of the type of open games is then the type of invertible 2-cells, and1031\cref{prin:invariance} applies to it.1032 1033\section{What composition does not do}1034 1035It is important not to oversell. \Cref{def:og-comp} makes the equilibrium \emph{predicate} compositional:1036whether $(\sigma,\tau)$ is an equilibrium of $\mathcal{H}\circ\mathcal{G}$ is decided by consulting1037$E_{\mathcal{G}}$ and $E_{\mathcal{H}}$. It does not make the equilibrium \emph{set} of a composite a1038function of the equilibrium sets of its parts in any fixed contexts, because the context in which1039$\mathcal{G}$ is consulted depends on $\tau$. To compose, one must know each part's behaviour in \emph{every}1040context.1041 1042Seen from semantics this is as it should be: the meaning of an open term is its behaviour under all1043environments, and game theory itself insists that a strategy is a complete contingent plan. But it has two1044consequences that the reader should hold on to.1045 1046\begin{itemize}1047\item Open games give compositional \emph{modelling} and compositional \emph{equilibrium checking}. They do1048  not give compositional \emph{solving}, and cannot: computing a Nash equilibrium is hard for reasons that1049  have nothing to do with notation (\cref{ch:mixing}). The software built on this theory is, accordingly,1050  an equilibrium checker that is fed candidate profiles \cite{Hed24}.1051\item The equilibria of a composite can differ in kind from those of its parts. Multiplicity, coordination1052  failure and the need for refinement are emergent. A compositional language describes emergence1053  precisely; it does not abolish it.1054\end{itemize}1055 1056\section*{Notes}1057 1058Open games were introduced in \cite{GHWZ18} and in Hedges's thesis \cite{Hed16}; the survey-style account1059closest to the presentation here is \cite{BHZ19}, which also introduces contexts for optics. Lenses come1060from the theory of bidirectional transformations; their systematic generalization to optics is1061\cite{Ril18,CEGLMPR20}. Alternative axiomatizations that make the proof of \cref{thm:og-smc} itself1062compositional are given in \cite{AGGKLN21}, and the translation from extensive-form games into open games1063with agency is \cite{CGLN22}. Selection functions and their products are due to Escard\'o and Oliva1064\cite{EO10,EO11}; \cite{HOSWZ17} uses them to define equilibria for agents who do not maximize. A metric1065refinement, in which equilibrium predicates are relaxed by an $\epsilon$ budget compatibly with1066composition, is \cite{Gha25}. Earlier categorical treatments of games, which take games as objects rather1067than morphisms, are surveyed in \cite{TV23}.1068 1069\section*{Exercises}1070 1071\begin{exercise}1072Verify that composition of lenses is associative, and that a lens $I\to(X,S)$ is an element of $X$ while a1073lens $(Y,R)\to I$ is a function $Y\to R$.1074\end{exercise}1075\begin{exercise}1076Using \cref{def:og-comp}, compute the equilibrium predicate of the closed game of \cref{ex:og-seq} for the1077entry game in which player~1 chooses \emph{Out} (payoffs $(0,4)$) or \emph{In}, after which player~2 chooses1078\emph{Accommodate} $(1,2)$ or \emph{Fight} $(-1,0)$. List all equilibria and identify the one that is not