Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 321–420 of 6559. Source text is displayed literally.
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, closed401off by a payoff function. Solid wires carry moves forward; dashed wires carry utility back.}\label{fig:intro-pd}402\end{figure}403 404\emph{Third reading: an object varying over time.} Repeat the game forever with discount factor $\delta$.405A strategy is now a machine: a set of states, an output function, a transition function. Machines are406coalgebras; the space of all strategies is a terminal coalgebra; and the equilibrium payoff set is the407greatest fixed point of a monotone operator on sets of payoff vectors. That one sentence already contains408the automaton representation of strategies, the complexity measure of Kalai and Stanford, the409self-generation theorem of Abreu, Pearce and Stacchetti, and the reason the finitely repeated game---an410\emph{initial} algebra, solved by recursion from the end---behaves so differently (\cref{ch:repetition}).411 412\section*{A dictionary}413 414The table below is a map of the book. The left column is the classical vocabulary; the right column is what415the corresponding chapter claims that vocabulary was about.416 417\begin{center}\small418\renewcommand{\arraystretch}{1.25}419\begin{tabular}{@{}p{0.36\textwidth}p{0.50\textwidth}r@{}}420\toprule