Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 239–338 of 6559. Source text is displayed literally.
239games a compositional algebra: a game is a morphism, and large games are built from small ones by sequential240and parallel composition. The second is the categorical understanding of \emph{information}: knowledge as a241modality arising from base change, belief as a monad, hierarchies of belief as a terminal coalgebra. The242third is the homotopical habit of mind---made systematic in higher category theory and homotopy type243theory---of asking of every object what it is \emph{up to equivalence}, of every construction whether it is244invariant, and of every existence problem what obstructs it.245 246\subsection*{What this book is}247 248The book follows the arc of a first graduate course in game theory and information economics, the arc249canonically drawn by Rasmusen's \emph{Games and Information}: strategic and extensive forms; information;250mixed strategies; dynamic and repeated games; incomplete information; moral hazard, adverse selection,251mechanism design and signalling; bargaining, auctions and pricing. On each topic it does two things. It252states the classical theory precisely, with proofs or references and at least one worked example. And it253re-reads that theory in a language in which the structural content is explicit. Sometimes the re-reading is254only a change of notation, and we say so. Sometimes it produces a statement that the classical255formulation obscures; the main instances are these.256 257\begin{itemize}258\item \emph{Solution concepts are functions on a type of games, and a type has an identity structure.}259 Invariance requirements (Kohlberg--Mertens), symmetry requirements (Harsanyi--Selten), the Markov260 restriction (Maskin--Tirole) and the insensitivity of interim rationalizability to redundant types are one261 requirement, applied to four different types (\cref{ch:rules,ch:extensive,ch:belief,ch:repetition}).262\item \emph{Common knowledge is $\pi_0$; a common prior is the vanishing of a class in $H^1$.} The meet of263 the players' partitions is the set of connected components of the homotopy colimit of their type maps;264 that homotopy colimit is a graph, and its first cohomology is exactly the obstruction to gluing the265 players' posteriors into a common prior (\cref{ch:knowledge,ch:belief}).266\item \emph{Perfection is a necessity modality.} Subgame perfection is to subgames what knowledge is to267 states: the right adjoint of a restriction (\cref{ch:perfection}).268\item \emph{Finite horizons are initial algebras; infinite horizons are terminal coalgebras.} Backward269 induction is a fold; the one-shot deviation principle and self-generation are coinduction principles;270 discounting is a guard. The folk theorem lives in the gap between least and greatest fixed points, and271 Rubinstein's uniqueness theorem is the statement that under a contraction there is no gap272 (\cref{ch:repetition,ch:bargaining}).273\item \emph{Incentive compatibility is an enriched-presheaf condition.} A social choice function induces a274 generalized metric on the type space; incentive-compatible payment rules are exactly the enriched275 copresheaves; implementability is the absence of negative cycles; revenue equivalence says the incentive276 category is a groupoid (\cref{ch:mechanism}).277\end{itemize}278 279None of the underlying theorems is ours, and the status tags described on the copyright page are meant to keep that280visible. What is offered is a unified development, a number of reformulations with their proofs, a set of281worked examples, and---in \cref{ch:coda}---an assessment of where the higher-categorical language earns its282keep and where it is, so far, only a dialect.283 284\subsection*{What ``higher'' means here}285 286A candid remark, since the title invites the question. The structures used in this book are mostly of low287categorical dimension: groupoids of games, graphs and their first cohomology, monoidal categories and288bicategories of optics, categories enriched in truth values or in extended reals, presheaf toposes.289Genuinely infinite-dimensional structure appears at the edges---in the spaces of games and equilibria of290\cref{ch:mixing}, in the simplicial models of many-agent knowledge of \cref{ch:knowledge}, and in the ambient291$\infty$-toposes in which one would like to place smooth and probabilistic games. ``Higher categorical292semantics'' is used here in the sense of the discipline rather than the dimension: objects are considered293up to equivalence; equivalences are data; constructions are required to be invariant; quotients are taken294homotopically, so that what an ordinary quotient discards is retained as higher structure. That discipline295turns out to organize a surprising amount of game theory. Whether it will prove theorems that the296classical language could not is a question the last chapter takes up without sentiment.297 298\subsection*{Prerequisites and conventions}299 300The reader should know what a category, a functor, an adjunction and a monad are, and should not be301alarmed by a string diagram. No game theory is assumed, but the classical material is covered at speed.302\Cref{app:toolkit} collects the categorical background actually used: monoidal and enriched categories,303presheaf toposes and modalities, the vocabulary of homotopy type theory, probability monads and Markov304categories, (co)algebras, optics, and the four fixed-point theorems on which the subject runs.305 306Type-theoretic notation ($\sum$, $\prod$, identity types) is used informally, as in the first chapters of307\cite{HoTT13}; nothing depends on a particular proof assistant or a particular model. A normal-form game is308written $(N, A, u)$ with $A=\prod_{i\in N}A_i$; a profile is $a=(a_i,a_{-i})$. $\Dist X$ is the set of finitely309supported probability distributions on $X$. Each chapter ends with notes on the literature and with310exercises; none of the exercises is taken from another text, and \cref{app:solutions} gives solutions to all311of them.312 313\chapter{Introduction}\label{ch:intro}314 315\section*{The method, and what is missing from it}316 317The method of applied game theory can be stated in a sentence: specify the \emph{rules of the game}---who318moves, when, knowing what, with what consequences---and then compute what follows from them under a319\emph{solution concept}. The discipline of the method is that everything must be in the rules. An320explanation that appeals to something outside the model is not an explanation in the theory.321 322Logicians will recognize the shape. The rules are \emph{syntax}; the solution concept is a \emph{semantics};323a model is good when the semantics of a simple piece of syntax matches an observed regularity. But324the comparison also shows what the classical practice lacks. In logic, syntax is generated by a325grammar, semantics is defined by recursion on the grammar, and there is a clear notion of when two pieces326of syntax \emph{mean the same thing}. In game theory the syntax is a picture of a tree or a table of numbers;327the semantics is defined on the whole object at once; and the question of when two games are the same game328has been answered case by case, by people with good taste, over several decades.329 330Categorical semantics is the systematic study of this shape, and this book applies it. We will ask the331three questions a semanticist asks of any language.332 333\begin{enumerate}334\item \emph{What are the types?} That is: what kind of thing is a game, a strategy, a belief, a contract;335 and when are two of them equal? Here the answer comes from homotopy type theory. A type is not a bare336 set but a space of things-with-identifications. The type of games is a groupoid (at least), and a337 solution concept is a function on it. Functions on a type respect its identifications; this single338 fact reproduces the invariance axioms of refinement theory, and says precisely which popular