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

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 2901\begin{definition}\Scl[\cite{APS90,Abr88}]2902For $W\subseteq\R^N$ let $B(W)$ be the set of payoff vectors $v$ for which there are an action profile $a$2903and a map $w\colon A\to W$ of \emph{promised continuation values} with2904\begin{align*}2905 v&=(1-\delta)u(a)+\delta\,w(a),\\2906 (1-\delta)u_i(a)+\delta\,w_i(a)&\ge(1-\delta)u_i(a_i',a_{-i})+\delta\,w_i(a_i',a_{-i})2907\end{align*}2908for all $i$ and $a_i'$: \emph{promise keeping} and \emph{incentive compatibility}. A set $W$ is \term{self-generating} if $W\subseteq B(W)$.2909\end{definition}2910 2911\begin{theorem}[Abreu--Pearce--Stacchetti]\label{thm:APS}\Scl[\cite{APS90}]2912Let $V^*$ be the set of subgame-perfect payoff vectors of $G^\infty(\delta)$.2913\begin{enumerate}[label=(\roman*)]2914\item (Self-generation.) If $W$ is bounded and $W\subseteq B(W)$ then $B(W)\subseteq V^*$.2915\item (Factorization.) $V^*=B(V^*)$.2916\item $B$ is monotone and preserves compactness; $V^*$ is compact and equals $\bigcap_nB^n(W_0)$ for any2917  compact $W_0\supseteq V^*$.2918\end{enumerate}