Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 341–440 of 6559. Source text is displayed literally.
341 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\toprule421\textbf{Classical notion} & \textbf{Structure} & \textbf{Ch.}\\\midrule422strategic equivalence; invariance & identity type of the type of games & \ref{ch:rules}, \ref{ch:extensive}\\423focal point & structure that breaks an automorphism & \ref{ch:rules}\\424simultaneous / sequential play & monoidal product / composition of open games & \ref{ch:open}\\425game tree & presheaf on $\omega$ & \ref{ch:extensive}\\426perfect recall & the information quotient is a map of forests & \ref{ch:extensive}\\427knowledge operator & comonad $p^*\forall_p$ of base change & \ref{ch:knowledge}\\428common knowledge & $\pi_0$ of a homotopy colimit & \ref{ch:knowledge}\\429universal type space & terminal coalgebra & \ref{ch:belief}\\430common prior & trivial class in $H^1$ & \ref{ch:belief}\\431mixed extension & free convex algebra & \ref{ch:mixing}\\432existence of equilibrium & a projection of degree one & \ref{ch:mixing}\\433strategic complements & enrichment in a lattice; Tarski & \ref{ch:order}\\434subgame perfection & necessity modality over subgames & \ref{ch:perfection}\\435backward induction & fold over an initial algebra & \ref{ch:perfection}\\436discounting & guard; contraction & \ref{ch:repetition}\\437self-generating set & post-fixed point; coinduction & \ref{ch:repetition}\\438Markov strategy & factors through the bisimulation quotient & \ref{ch:repetition}\\439consistent off-path beliefs & point of a blow-up of the simplex & \ref{ch:dynamic}\\440contract & costate of an optic & \ref{ch:moralhazard}\\