Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5321–5420 of 6559. Source text is displayed literally.
5321\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 5399A \term{homotopy type} (or space, or $\infty$-groupoid) is considered up to weak equivalence; sets are the5400discrete ones. The $\infty$-category $\Spc$ of spaces has homotopy colimits. The homotopy colimit of a5401diagram of sets $D\colon J\to\Set$ is the nerve of its category of elements \cite{Tho79}; in particular the5402homotopy pushout of $A\leftarrow C\to B$ is the graph with vertices $A\sqcup B$ and edges $C$. The functor5403$\pi_0\colon\Spc\to\Set$ is left adjoint to the inclusion and so carries homotopy colimits to colimits. For a5404graph $B$ and an abelian group $G$, $H^0(B;G)$ is the group of locally constant $G$-valued functions on5405vertices and $H^1(B;G)$ is the group of $G$-valued functions on edges modulo coboundaries5406$(\delta\varphi)(e)=\varphi(\text{head})-\varphi(\text{tail})$; a 1-cochain is a coboundary iff it sums to zero5407around every cycle, and $H^1(B;\R)\iso\R^{b_1}$ with $b_1=|E|-|V|+|\pi_0|$.5408 5409In \term{homotopy type theory} \cite{HoTT13} types are homotopy types. We use: dependent sums5410$\sum_{x:A}B(x)$ and products $\prod_{x:A}B(x)$; the identity type $x=_Ay$, whose elements are paths; transport5411of a dependent element along a path; propositional truncation $\|A\|$, the proposition that $A$ is5412inhabited; set-quotients and higher inductive types. The \term{univalence axiom} identifies the identity5413type of the universe with equivalence of types, and has as a consequence the \term{structure identity5414principle}: for a type of structured types, identifications are structure-preserving equivalences5415\cite{ANST21}. Every function respects identifications of its domain; this is \cref{prin:invariance}. A5416\term{modality} in the sense of \cite{RSS20} is an idempotent monad on the universe with a dependent5417elimination rule; comonadic modalities such as $\flat$ require a context discipline \cite{Shu18,Cor20}.5418 5419\section{Probability}5420