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

5241which \cref{thm:H1} is the pairwise case, asks when beliefs specified on a family of coalitions are the5242marginals of a single joint belief, and its obstructions are known to be cohomological in the closely5243related setting of contextuality \cite{AB11}. Which mediated correlations among coalitions are implementable5244by local devices is a question of this kind.5245\end{problem}5246 5247\begin{problem}[Graded modalities]\Spg5248Three approximations in this book are indexed by a real parameter: common $p$-belief5249(\cref{ch:dynamic}), $\epsilon$-equilibrium, and discounting by $\delta$. The first is a graded comonad, the5250second has a compositional metric formulation \cite{Gha25}, and the third is a quantitative form of the5251later modality (\cref{thm:guarded}). Give a single quantale-graded modal type theory in which all three are5252instances, and in which the continuity theorem of Monderer and Samet and the limit theorems for5253finite-horizon approximations \cite{FL83} are theorems about grades.5254\end{problem}5255 5256\begin{problem}[Beyond quasi-linearity]\Spg5257\Cref{thm:rochet} and \cref{prop:nucleus} use transferable utility in an essential way: the base of5258enrichment is the additive reals. N\"oldeke and Samuelson \cite{NS18} extend the duality between tariffs5259and utility profiles to preferences that are not quasi-linear, by means of Galois connections. Identify the5260enriching structure for which their duality is the nucleus of a profunctor, and state implementability and5261payoff equivalence as conditions on the resulting enriched category.5262\end{problem}5263 5264\begin{problem}[A synthetic existence theorem]\Spg5265Nash's theorem requires Brouwer's, which holds synthetically in a cohesive type theory \cite{Shu18}, while5266mixed strategies require probability, which is axiomatized by Markov categories \cite{Fri20}. Find a5267setting with both: a category or type theory in which the mixed extension is a free construction, strategy5268spaces carry intrinsic topology, and the truncated existence statement of \cref{rem:truncated} is a5269theorem. Determine which classes of games admit an untruncated one: supermodular games, by5270\cref{thm:supermodular}; two-player zero-sum games, by linear programming; potential games, by5271maximization.5272\end{problem}5273 5274\begin{problem}[Effective game theory]\Spg5275\Cref{thm:NZ} shows that best responses to computable strategies need not be computable. Develop the5276theory of repeated games internally to a realizability topos, where every function is computable by5277construction. Is there a folk theorem there? The internal terminal coalgebra of the strategy functor5278consists of computable strategies, and the internal equilibrium condition quantifies only over those; the5279classical counterexamples suggest that the internal and external equilibrium sets differ, and the5280difference would be a precise measure of what bounded rationality costs.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 is