Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2841–2940 of 6559. Source text is displayed literally.
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}2919Thus $V^*=\nu B$, the greatest fixed point of $B$ on bounded sets.2920\end{theorem}2921 2922Part (i) is the coinduction rule of \cref{thm:tarski}: a post-fixed point lies below the greatest fixed2923point. But more is true, and it ties this section to the one on automata. A self-generating set $W$2924together with a choice, for each $v\in W$, of the pair $(a,w)$ that generates it is a map2925\[ W\longrightarrow A\times W^A, \]2926that is, a \emph{coalgebra} for the strategy functor, with state space the set of promised values. Its2927unique map to the terminal coalgebra is the equilibrium strategy profile: start in state $v$, play $a(v)$,2928move to state $w(v)(\text{what was played})$. Incentive compatibility makes one-shot deviations2929unprofitable in every state, and \cref{thm:osdp} does the rest. ``Use continuation values as state2930variables'', the slogan of recursive methods in dynamic games and contracts, is the instruction to build a2931coalgebra.2932 2933\begin{example}[Grim trigger]\label{ex:grim}2934In the Prisoner's Dilemma with payoffs $T=3$, $R=2$, $P=1$, $S=0$, the two-point set $W=\{(2,2),(1,1)\}$ is2935self-generating iff $\delta\ge\tfrac12$. The value $(1,1)$ is generated by $(D,D)$ with $w\equiv(1,1)$. The2936value $(2,2)$ is generated by $(C,C)$ with $w(C,C)=(2,2)$ and $w=(1,1)$ otherwise; incentive compatibility2937reads $2\ge(1-\delta)3+\delta$, that is, $\delta\ge\frac{T-R}{T-P}=\tfrac12$. The coalgebra on $W$ is the2938two-state automaton of grim trigger.2939\end{example}2940