Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2801–2900 of 6559. Source text is displayed literally.
2801last town, hence in the nineteenth, hence in all, and that every entrant enters. Everyone's intuition2802says that she fights early entrants to deter later ones, and that it works. Selten took the paradox to2803show a gap between the theory and reasonable behaviour. We will take it to show that the intuition is2804computing a different fixed point from the induction. (When $G$ has several equilibria the theorem fails2805and finite repetition can sustain a good deal \cite{BK85}; \cref{ex:pareto-perfect} was an instance.)2806 2807\section{Strategies are coalgebras}2808 2809Turn to the infinitely repeated game $G^\infty(\delta)$, with payoffs2810$U_i=(1-\delta)\sum_{t\ge0}\delta^tu_i(a^t)$ for a discount factor $\delta\in(0,1)$.2811 2812\begin{definition}2813An \term{automaton} for player $i$ is a set $Q$ of states with an initial state, an output map2814$f\colon Q\to A_i$ and a transition map $\tau\colon Q\times A\to Q$. Equivalently it is a pointed coalgebra2815$Q\to F(Q)$ for the functor $F(X)=A_i\times X^A$ on $\Set$.2816\end{definition}2817 2818\begin{proposition}\label{prop:final-strategy}\Sli[\cite{Rut00}]2819The terminal $F$-coalgebra is the set $A_i^{A^*}$ of functions from histories to actions---the set of pure2820strategies of the repeated game---with output ``evaluate at the empty history'' and transition ``restrict2821to histories beginning with $a$''. The unique coalgebra map from an automaton sends a state $q$ to the2822strategy it implements when started at $q$.2823\end{proposition}2824 2825So the textbook definition of a strategy (a function on histories) and the working definition (a machine)2826are related as a terminal coalgebra to an arbitrary one. The image of an automaton in $A_i^{A^*}$ is its2827set of distinct \emph{continuation strategies}, and the minimal automaton implementing a strategy has2828exactly one state for each. Kalai and Stanford \cite{KS88} take this number as the \emph{complexity} of a2829strategy; it is the coalgebraic notion of the size of a behaviour, and the minimal automaton is the2830quotient by bisimilarity. \emph{Grim trigger}---cooperate until anyone defects, then defect forever---has2831two states. So does \emph{tit-for-tat}. A strategy of finite complexity is one whose orbit under the2832transition structure of the terminal coalgebra is finite.2833 2834\section{Perfection, coinductively}2835 2836Subgame perfection is defined as in \cref{sec:box}: every history roots a subgame, and $\sigma$ is subgame2837perfect when $\sigma|_h$ is a Nash equilibrium of the continuation game for every $h$. But there are now2838infinitely many subgames and no last one, and checking the definition seems to require comparing $\sigma_i$2839with every one of uncountably many alternative strategies at each of them.2840 2841\begin{theorem}[One-shot deviation principle]\label{thm:osdp}\Scl[\cite{Bla65,Abr88}; see \cite{FT91}]2842In a game that is continuous at infinity---in particular in $G^\infty(\delta)$ with bounded stage payoffs---a2843profile $\sigma$ is subgame perfect if and only if no player can gain at any history $h$ by deviating from2844$\sigma_i$ at $h$ alone and conforming to it thereafter.2845\end{theorem}2846 2847Here is the coinductive reading. For a set $Q$ of profiles let $\Psi(Q)$ be the set of profiles $\sigma$2848such that (a) no one-shot deviation at the initial history is profitable, payoffs being computed by2849letting $\sigma$ run, and (b) each continuation $\sigma|_a$ after a first-period action profile $a$ lies in2850$Q$. $\Psi$ is monotone, and its greatest fixed point $\nu\Psi$ is the set of profiles with no profitable2851one-shot deviation at any history. The theorem says $\SPE=\nu\Psi$. One inclusion is trivial. The other is2852where the hypothesis enters: a profitable deviation involving infinitely many changes must be approximated2853by a profitable deviation involving finitely many, which is then reduced to a single one by backward2854induction over the finitely many. The approximation is \emph{continuity at infinity}: payoffs depend2855arbitrarily little on what happens after a sufficiently late date.2856 2857\begin{example}[Why the hypothesis is needed]\label{ex:discontinuous}2858A single agent chooses each period whether to stop. If she ever stops she gets $0$; if she never stops she2859gets $1$. The strategy ``stop at every history'' admits no profitable one-shot deviation: continuing once and2860stopping next period still yields $0$. But it is not optimal. The payoff is discontinuous at infinity: the2861reward for never stopping is invisible at every finite stage. Coinduction certifies a profile that the2862semantics rejects.2863\end{example}2864 2865\section{Discounting is a guard}2866 2867Continuity at infinity has a clean formulation. Give the set $A^\omega$ of infinite plays the ultrametric2868$d(x,y)=2^{-t}$, where $t$ is the first period at which $x$ and $y$ differ. With bounded stage payoffs and2869$\delta<1$, the payoff $U_i$ changes by at most $\delta^t\cdot\mathrm{const}$ between plays that agree up to2870$t$: it is uniformly continuous. In the terms of \cref{ch:extensive}, $A^\omega$ is the set of global sections2871of the tree of histories, and a payoff continuous at infinity is one that can be approximated, uniformly,2872by functions on the finite levels of the tree.2873 2874The topos of trees $\Trees$ has an endofunctor $\later$, ``later'', with $(\later X)(n+1)=X(n)$ and2875$(\later X)(0)=1$, and a natural map $X\to\later X$. A map is \emph{contractive} if it factors through2876$\later$: its output at stage $n+1$ depends only on its input at stage $n$.2877 2878\begin{theorem}\label{thm:guarded}\Sli[\cite{BMSS12}]2879In $\Trees$ every contractive map $f\colon\later X\to X$ has a unique fixed point. Complete bounded ultrametric2880spaces with distances in $\{2^{-n}\}$ and nonexpansive maps embed fully in $\Trees$, contractive maps2881corresponding to maps that factor through $\later$; under the embedding the theorem is Banach's.2882\end{theorem}2883 2884Dynamic programming is the same theorem with real-valued distances. The value of a stationary decision2885problem satisfies $V=\max_a\{(1-\delta)u(a,s)+\delta V(s')\}$; the right-hand side is an operator on bounded2886functions that is monotone and discounts, hence is a $\delta$-contraction in the sup norm, hence has a2887unique fixed point \cite{Bla65}. What $\delta$ does is put the continuation value \emph{under a guard}: tomorrow's2888value enters today's only after being shrunk. In the enriched language of \cref{sec:banach}, $\delta$ makes2889the Bellman operator a contraction of a Lawvere metric space; in the topos-theoretic language it is a2890quantitative form of $\later$. Either way, a single decision maker's infinite-horizon problem has a unique2891value, and it is the limit of the finite-horizon values: under a guard, the inductive and the coinductive2892solutions agree.2893 2894For games they do not, and the reason is that equilibrium is not governed by a contraction.2895 2896\section{Self-generation}2897 2898The fundamental recursive tool for repeated games works not with a value but with the \emph{set} of2899equilibrium values. For simplicity consider pure strategies and perfect monitoring.2900