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

5401diagram 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 &5441 rationalizability, common knowledge, supermodular games, self-generation, lemons\\5442Banach & a contraction of a complete metric space has a unique fixed point &5443 dynamic programming, alternating-offers bargaining\\5444Brouwer, Kakutani & a continuous map (closed convex-valued correspondence) on a compact convex set has a5445 fixed point & Nash's theorem, existence of sequential equilibrium\\5446Lawvere & if $A\to B^A$ is point-surjective then every $B\to B$ has a fixed point &5447 nonexistence of universal possibility structures; limits of self-prediction\\5448\bottomrule5449\end{tabular}5450\end{center}5451 5452\noindent The first two are the enriched-categorical pair of \cref{sec:banach} and are constructive in5453content: both come with an iteration. The third is topological and is not constructive. The fourth, used5454in contrapositive form, is the diagonal argument \cite{Law69}.5455%% ---- end ch/A-toolkit.tex ----5456%% ---- begin ch/B-concordance.tex ----5457\chapter{Concordance with the Source}\label{app:concordance}5458 5459This book covers the territory of Rasmusen's \emph{Games and Information} (4th edition) \cite{Ras06} in a5460different order and a different language. The table maps the chapters of that book to the places where5461their subject matter is treated here, with the structural reading proposed. Topics are described in our5462own words; the source's examples have been replaced by others throughout, and none of its problems is5463reproduced.5464 5465{\small5466\renewcommand{\arraystretch}{1.3}5467\begin{longtable}{@{}p{0.07\textwidth}p{0.36\textwidth}p{0.09\textwidth}p{0.38\textwidth}@{}}5468\toprule5469\textbf{Src.} & \textbf{Subject matter} & \textbf{Here} & \textbf{Reading}\\\midrule5470\endhead54711 & players, actions, payoffs; dominance and iterated dominance; Nash equilibrium; focal points &5472  \ref{ch:rules}, \ref{ch:open} & types of games and their identity; dominance as confluent rewriting;5473  rationalizability as a greatest fixed point; focal points as symmetry-breaking structure; composition\\54742 & strategic and extensive forms; information sets; perfect, certain, symmetric and complete5475  information; the Harsanyi transformation; Bayesian games &5476  \ref{ch:extensive}, \ref{ch:knowledge}, \ref{ch:belief} & trees as presheaves; information as a quotient;5477  perfect recall as internality; knowledge as base change; incomplete information as a dependent sum; types5478  as a terminal coalgebra\\54793 & mixed strategies; chicken and the war of attrition; correlated strategies; many-player mixing;5480  auditing; Cournot and Bertrand; complements and substitutes; existence &5481  \ref{ch:mixing}, \ref{ch:order} & free convex algebras; the non-invertible map $\nabla$; degree of the5482  equilibrium correspondence; lattices and Tarski\\54834 & subgame perfection; entry deterrence; credible threats and sunk costs; the open-set problem; Pareto5484  perfection & \ref{ch:perfection} & folds over an initial algebra; necessity modality; commitment as a5485  morphism; searchability\\54865 & finitely and infinitely repeated games; the chain-store paradox; minimax and the folk theorem;5487  reputation and product quality; Markov equilibria; evolutionary equilibrium &5488  \ref{ch:repetition}; \ref{ch:moralhazard2} & induction versus coinduction; automata as coalgebras;5489  self-generation; Markov as bisimulation invariance. (The quality-assuring price premium is the efficiency5490  wage of \cref{ch:moralhazard2} with the roles relabelled.)\\54916 & perfect Bayesian equilibrium and its refinement; the role of common knowledge; incomplete5492  information in the repeated Prisoner's Dilemma; tournaments of strategies; reputation in credit &5493  \ref{ch:dynamic}; \ref{ch:repetition} & sections of belief bundles; conditional systems as a blow-up;5494  discontinuity in the type space; graded modalities\\54957 & classification of asymmetric-information models; the principal--agent problem; incentive,5496  participation and competition constraints; optimal contracts & \ref{ch:moralhazard} & five composites of5497  the same boxes; contracts as costates; informativeness as factorization of kernels\\54988 & efficiency wages; tournaments; institutions; renegotiation; insurance under moral hazard; teams &5499  \ref{ch:moralhazard2} & coinductive incentives; sufficient statistics; open versus closed systems;5500  idempotent operators on contracts\\