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

5341$\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 5421$\Dist$ is the monad of finitely supported distributions on $\Set$; $\Giry$ is the Giry monad on measurable5422spaces \cite{Gir82}. Both are \emph{commutative} (monoidal) monads: there is a natural5423$\nabla\colon TX\times TY\to T(X\times Y)$ forming product measures, compatible with the monad structure, and5424it is not an isomorphism. A \term{Markov category} \cite{Fri20} is a symmetric monoidal category with5425commutative comonoid structures (copy, delete) on all objects, deletion being natural. The Kleisli5426categories $\FinStoch$ and $\Stoch$ are examples. A morphism is \emph{deterministic} if it commutes with copy.5427Given a state $\pi\colon I\to X$ and $f\colon X\to Y$, a \term{Bayesian inverse} is $f^\dagger_\pi\colon Y\to X$ such5428that the joint states on $X\otimes Y$ formed from $(\pi,f)$ and from $(f\pi,f^\dagger_\pi)$ coincide5429\cite{CJ19}. For $f,g$ out of the same object, $g$ is a \term{garbling} of $f$ if $g=hf$; this preorder is5430the Blackwell order \cite{Bla51,FGPR23}. Algebras of $\Dist$ are convex spaces, and $\Dist X$ is the free5431one.5432 5433\section{Four fixed-point theorems}5434 5435\begin{center}\small5436\renewcommand{\arraystretch}{1.3}5437\begin{tabular}{@{}p{0.14\textwidth}p{0.38\textwidth}p{0.38\textwidth}@{}}5438\toprule5439\textbf{Theorem} & \textbf{Statement} & \textbf{Uses in this book}\\\midrule5440Tarski & a monotone map on a complete lattice has a complete lattice of fixed points &