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

301alarmed 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 popular339  solution concepts are functions on which types.340\item \emph{How do the terms compose?} Here the answer comes from applied category theory. Games with341  open boundaries are the morphisms of a symmetric monoidal category; the boundary data---what a game342  observes, what it does, what utility it receives and what ``coutility'' it sends back---is an object of343  a category of \emph{optics}. The same optic structure organizes Bayesian updating and contracts.344\item \emph{Where does the interpretation live?} Classical game theory is interpreted in sets. But a game345  of incomplete information is a game \emph{varying over} a space of states, and a dynamic game is a game346  \emph{varying over} time. The natural homes for variable sets are toposes: presheaves on a space of347  states, presheaves on the ordinal $\omega$. Their internal logic is modal, and its modalities are348  the knowledge operator of epistemic game theory and the ``later'' operator of guarded recursion.349\end{enumerate}350 351\section*{One game, read three times}352 353Take the most familiar object in the subject. Two players each choose $C$ or $D$; payoffs are354\[355\begin{array}{c|cc}356 & C & D\\\hline357C & 2,2 & 0,3\\358D & 3,0 & 1,1359\end{array}360\]361with the row player's payoff listed first.362 363\emph{First reading: an element of a type.} The table is a presentation. Rescale either player's payoffs by364a positive affine map and nothing a game theorist cares about changes; so the game is at best the365equivalence class. But more is true: subtract $2$ from the row player's payoffs in the column where her366opponent plays $C$ (and symmetrically), and one obtains367\[368\begin{array}{c|cc}369 & C & D\\\hline370C & 0,0 & 0,1\\371D & 1,0 & 1,1372\end{array}373\]374in which every player's ranking of her own actions against every opponent action is unchanged---$D$ is still375strictly dominant---but mutual defection is now Pareto \emph{efficient}. The two tables have the same376best-response structure and different welfare structure. So there are (at least) two types here: games up377to \emph{best-response equivalence}, on which Nash equilibrium, dominance and rationalizability are378well-defined functions; and games up to \emph{preference equivalence}, a finer type, on which efficiency is379also defined. ``The Prisoner's Dilemma'' is a point of the finer type whose image in the coarser one is380unremarkable. The dilemma is not in the strategic structure. \Cref{ch:rules} makes this precise.381 382\emph{Second reading: a composite.} Each player is a small open system: a box with an output wire carrying383her action and an input wire carrying her payoff back. The game is the two boxes side by side, capped384by a box that turns the pair of actions into the pair of payoffs (\cref{fig:intro-pd}). Nothing here is385special to two players or to this payoff function. Replace the cap by a box that feeds the actions into a386market, or into a second stage of play, and one has a different game built from the same parts.387\Cref{ch:open} develops this algebra; the equilibrium condition is defined once, for a single box, and388composed.389 390\begin{figure}[ht]\centering391\begin{tikzpicture}[x=1cm,y=1cm]392  \node[ogbox] (P1) at (0,1.1) {$\mathcal{D}_1$};393  \node[ogbox] (P2) at (0,-1.1) {$\mathcal{D}_2$};394  \node[ogbox,minimum height=3.2cm] (U) at (3.4,0) {$u$};395  \draw[fw] (P1.east|-0,1.35) -- node[above=1pt,lab,black]{$A_1$} (U.west|-0,1.35);396  \draw[bw] (U.west|-0,0.85) -- node[below=1.5pt,lab,black]{$\R$} (P1.east|-0,0.85);397  \draw[fw] (P2.east|-0,-0.85) -- node[above=1pt,lab,black]{$A_2$} (U.west|-0,-0.85);398  \draw[bw] (U.west|-0,-1.35) -- node[below=1.5pt,lab,black]{$\R$} (P2.east|-0,-1.35);399\end{tikzpicture}400\caption{A two-player simultaneous game as a composite of open games: two decisions in parallel, closed