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

379also 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 who459wants the classical theory only can read the statements tagged \textsf{classical} and the examples; a460reader who knows the classical theory can read the rest.461%% ---- end front.tex ----462\mainmatter463\part{Games}464%% ---- begin ch/01-rules.tex ----465\chapter{The Rules of the Game}\label{ch:rules}466 467A game is specified by its rules: the players, what each can do, what each knows when doing it, and how468each ranks the consequences. This chapter treats the simplest case, in which nobody learns anything before469acting, so that the only rules are players, actions and payoffs. Its real subject, however, is the question470that the simplest case already raises: when are two specifications \emph{the same game}? The answer organizes471the rest of the book.472 473\section{Decisions}474 475A game is several decision problems that share variables, so we begin with one.476 477\begin{definition}\label{def:decision}478A \term{decision problem} is a set $X$ of alternatives together with a map $k\colon X\to R$ into a set $R$