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

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$479of outcomes. A \term{selection function} for $(X,R)$ is a map480\[ \varepsilon\colon (X\to R)\longrightarrow \Pow(X) \]481assigning to each problem $k$ the set $\varepsilon(k)\subseteq X$ of alternatives the agent is willing to482choose. When $R$ carries a total preorder, the \term{maximizing} selection function is483$\argmax(k)=\{x \st k(x)\ge k(x')\ \text{for all }x'\}$.484\end{definition}485 486The map $k$ is the agent's \emph{context}: everything about the world that matters to her, compressed into487the consequence of each alternative. Selection functions were isolated by Escard\'o and Oliva488\cite{EO10,EO11}, in single-valued form $(X\to R)\to X$, as the computational content of choice. Separating489the agent $\varepsilon$ from the context $k$ pays off twice. It lets a context be supplied by other agents,490which is what a game is. And it does not commit us to maximization: an agent who wants to be at the median,491or to pick whatever a majority picks, is a perfectly good selection function, though no utility function492on $X$ represents her \cite{HOSWZ17}.493 494\section{Games in strategic form, and their types}495 496\begin{definition}\label{def:nfg}497A (finite) \term{game in strategic form} consists of a finite set $N$ of players; for each $i\in N$ a finite498nonempty set $A_i$ of actions; and for each $i$ a payoff function $u_i\colon A\to\R$, where