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

5299subjects 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\toprule5381\textbf{Operator} & \textbf{Formula} & \textbf{Kind}\\\midrule5382knowledge of an agent with observation map $p$ & $p^*\forall_p$ & comonad, S5\\5383possibility & $p^*\exists_p$ & monad, S5\\5384common knowledge & $q^*\forall_q$, $q$ the pushout of the $p_i$ & comonad, S5\\5385distributed knowledge & $p_\vee^*\forall_{p_\vee}$, $p_\vee$ the joint observation & comonad, S5\\5386subgame perfection & $\forall_p\,e^*$ over later subgames & comonad, S4\\5387later (in $\Trees$) & $(\later X)(n+1)=X(n)$ & guard\\5388\bottomrule5389\end{tabular}5390\end{center}5391 5392\noindent In $\Trees$, a map $f\colon X\to X$ is \emph{contractive} if it factors through the canonical5393$X\to\later X$; contractive maps have unique fixed points, and locally contractive functors have unique5394fixed points up to isomorphism, so that for them initial algebras and terminal coalgebras coincide5395\cite{BMSS12}.5396 5397\section{Homotopy types and type theory}5398