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

5281\end{problem}5282 5283\section{A last remark on method}5284 5285The source of this book's subject matter describes its own method as modelling with the minimum of5286structure: find the simplest set of assumptions that generates the phenomenon, and stop. That is a5287principle of economy about what goes into a model. The discipline followed here adds a second economy,5288about what one may get out: only what is invariant under the equivalences of the model's type. The two5289economies are complementary. The first prevents explanation by excess detail. The second prevents5290explanation by accident of presentation. Game theory has always practised both, the second by the5291judgment of its practitioners. The claim of this book is modest: that the judgment can be written down.5292%% ---- end ch/19-coda.tex ----5293\appendix5294%% ---- begin ch/A-toolkit.tex ----5295\chapter{Categorical Toolkit}\label{app:toolkit}5296 5297This appendix fixes notation and collects, without proofs, the categorical notions used in the text. It is5298a list of what is needed, in the order in which it is needed, and not an introduction to any of the5299subjects named; references are given for each.5300 5301\section{Categories, adjunctions, (co)algebras}5302 5303We assume categories, functors, natural transformations, limits and colimits, and adjunctions5304$L\adj R$ \cite{FS19}. A \term{monad} on $\CC$ is an endofunctor $T$ with unit $\eta\colon\id\to T$ and5305multiplication $m\colon TT\to T$ satisfying the monoid laws; its \term{Kleisli category} $\Kl(T)$ has the5306objects of $\CC$ and morphisms $X\to TY$; its \term{algebras} are maps $TA\to A$ compatible with $\eta$ and5307$m$. Every adjunction $L\adj R$ gives a monad $RL$ and a comonad $LR$.5308 5309For an endofunctor $F$, an \term{$F$-algebra} is a map $F(A)\to A$ and an \term{$F$-coalgebra} a map5310$C\to F(C)$. An initial algebra $\mu F$ supports definition by recursion (the unique map to any other5311algebra is a \emph{fold}) and proof by induction; a terminal coalgebra $\nu F$ supports corecursion and5312coinduction \cite{Rut00}. \emph{Lambek's lemma}: the structure map of an initial algebra or terminal5313coalgebra is an isomorphism. When $\CC$ has a terminal object and $F$ preserves limits of5314$\omega^{\op}$-chains, $\nu F$ is the limit of $1\leftarrow F1\leftarrow F^21\leftarrow\cdots$. Two states of5315coalgebras are \term{bisimilar} (behaviourally equivalent) when they have the same image in $\nu F$.5316 5317\begin{center}\small5318\renewcommand{\arraystretch}{1.2}5319\begin{tabular}{@{}p{0.33\textwidth}p{0.27\textwidth}p{0.30\textwidth}@{}}5320\toprule5321\textbf{Functor} & \textbf{$\mu F$ or $\nu F$} & \textbf{Used for}\\\midrule5322$X\mapsto O+\sum_i\sum_AX^A$ on $\Set$ & $\mu$: finite game trees & backward induction (Ch.~\ref{ch:perfection})\\5323$X\mapsto A_i\times X^A$ on $\Set$ & $\nu$: strategies $A^*\to A_i$ & automata (Ch.~\ref{ch:repetition})\\5324$X\mapsto\Giry(\Theta\times X)$ on $\Meas$ & $\nu$: universal types & hierarchies (Ch.~\ref{ch:belief})\\5325monotone $f$ on a complete lattice & $\mu f$, $\nu f$ & Tarski (Ch.~\ref{ch:order})\\5326\bottomrule5327\end{tabular}5328\end{center}5329 5330\section{Monoidal categories, lenses, optics}5331 5332A \term{symmetric monoidal category} $(\CC,\otimes,I)$ has a tensor product that is associative, unital and5333symmetric up to coherent isomorphism. Its morphisms are drawn as \emph{string diagrams}: boxes with input and5334output wires, composed by joining wires and tensored by juxtaposition; an equation holds in all symmetric5335monoidal categories iff the diagrams are isotopic. A \emph{state} is a morphism $I\to X$; a \emph{costate} is5336a morphism $X\to I$.5337 5338The category $\Lens$ has pairs of sets as objects and, as morphisms $(X,S)\to(Y,R)$, pairs of functions5339$X\to Y$ and $X\times R\to S$ (\cref{def:lens}). For a symmetric monoidal $\CC$, the category $\Optic_\CC$ has5340hom-sets $\int^M\CC(X,M\otimes Y)\times\CC(M\otimes R,S)$ \cite{Ril18,CEGLMPR20}; for cartesian $\CC$ it is5341$\Lens$. The bicategory $\Para(\CC)$ has morphisms $X\to Y$ given by pairs $(\Pi,\ \Pi\otimes X\to Y)$ and5342reparametrizations as 2-cells \cite{CGHR22}. An open game is a family of lenses indexed by strategies with5343an equilibrium predicate (\cref{def:opengame}); open games form a symmetric monoidal category5344(\cref{thm:og-smc}).5345 5346\section{Enriched categories}5347 5348Let $(V,\le,\otimes,k)$ be a commutative quantale: a complete lattice with a monoid structure that5349preserves joins in each variable. A \term{$V$-category} is a set $C$ with $C(a,b)\in V$ such that5350$k\le C(a,a)$ and $C(a,b)\otimes C(b,c)\le C(a,c)$; a \term{$V$-functor} is a map $f$ with5351$C(a,b)\le D(fa,fb)$. Three cases are used.5352\begin{itemize}5353\item $V=\mathbf{2}$ with $\wedge$: preorders and monotone maps.5354\item $V=([0,\infty],\ge,+)$: Lawvere metric spaces and nonexpansive maps \cite{Law73}. Note the reversal5355  of order: the ``composition'' inequality is the triangle inequality.5356\item $V=\Rbar=([-\infty,\infty],\ge,+)$: the same with negative distances allowed, used for the incentive5357  category of \cref{sec:incentive-metric}. A $\Rbar$-category has $d(a,a)\in\{0,-\infty\}$.5358\end{itemize}5359$V$ is itself a $V$-category with $V(a,b)$ the internal hom (truncated subtraction $b-a$ in the metric5360cases). A \term{copresheaf} is a $V$-functor $C\to V$; the \term{Yoneda lemma} identifies $C(a,-)$ as the5361copresheaf freely generated by an element at $a$. The \term{free $V$-category} on a $V$-graph has hom-values5362given by joins over paths of tensor products of edge values; in the metric cases, shortest-path distances.5363A \term{profunctor} $\Phi\colon C\otimes D\to V$ induces an adjunction between presheaves on one side and5364copresheaves on the other, whose fixed points form its \term{nucleus}; for the pairing of a vector space5365with its dual, valued in $\Rbar$, this is the Legendre--Fenchel transform \cite{Wil15}.5366 5367\section{Toposes and modalities}5368 5369A \term{presheaf topos} is a category $\Set^{\CC^{\op}}$. We use two: presheaves on a discrete set $\Omega$,5370which is the slice $\Set/\Omega$ of families of sets indexed by states, and presheaves on the ordinal5371$\omega$, the \term{topos of trees} $\Trees$ \cite{BMSS12}. In any topos $\EE$, each object $X$ has a5372Heyting algebra $\Sub(X)$ of subobjects, and each map $p\colon X\to Y$ induces adjoints5373$\exists_p\adj p^*\adj\forall_p$ between $\Sub(X)$ and $\Sub(Y)$; on families of objects the corresponding5374adjoints are dependent sum and dependent product, $\sum_p\adj p^*\adj\prod_p$ \cite{MM92}. Composites of5375these are the modal operators of the text:5376 5377\begin{center}\small5378\renewcommand{\arraystretch}{1.2}5379\begin{tabular}{@{}p{0.36\textwidth}p{0.36\textwidth}p{0.18\textwidth}@{}}5380\toprule