Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 359–458 of 6559. Source text is displayed literally.
359\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}\\441sufficient statistic; garbling & factorization in a Markov category & \ref{ch:moralhazard}\\442market unraveling & iteration to a fixed point of a monotone map & \ref{ch:adverse}\\443incentive-compatible transfer & enriched copresheaf & \ref{ch:mechanism}\\444indirect utility & conjugate under a profunctor & \ref{ch:mechanism}\\445Bayes plausibility & fibre of the monad multiplication & \ref{ch:signalling}\\446Rubinstein uniqueness & unique guarded fixed point & \ref{ch:bargaining}\\447\bottomrule448\end{tabular}449\end{center}450 451\section*{How to read}452 453Part~I (\cref{ch:rules}--\ref{ch:dynamic}) is the theory of games; Part~II454(\cref{ch:moralhazard}--\ref{ch:signalling}) is the economics of asymmetric information; Part~III455(\cref{ch:bargaining}--\ref{ch:pricing}) contains applications; Part~IV is a single chapter of assessment.456\Cref{ch:rules,ch:open,ch:extensive,ch:knowledge,ch:belief} are the foundation and should be read in457order. After them the chapters are largely independent, with two exceptions: \cref{ch:signalling} and458Part~III lean on \cref{ch:mechanism}, and \cref{ch:bargaining} on \cref{ch:repetition}. A reader who