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

2881corresponding 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 2941\section{The folk theorem}2942 2943Let $\underline{v}_i=\min_{\alpha_{-i}}\max_{a_i}u_i(a_i,\alpha_{-i})$ be player $i$'s \term{minmax} value, the2944worst the others can hold her to, and let $\mathcal{F}^*$ be the set of feasible payoff vectors (convex2945combinations of stage payoffs) with $v_i>\underline{v}_i$ for all $i$.2946 2947\begin{theorem}[Folk theorem]\label{thm:folk}\Scl[\cite{Fri71,FM86}]2948Suppose $\mathcal{F}^*$ has dimension $|N|$ (or $|N|=2$). Then for every $v\in\mathcal{F}^*$ there is2949$\underline\delta<1$ such that $v$ is a subgame-perfect payoff of $G^\infty(\delta)$, with public2950randomization, for all $\delta\ge\underline\delta$.2951\end{theorem}2952 2953So for patient players $\nu B$ is as large as it could possibly be: everything feasible and individually2954rational. Compare \cref{thm:finite-rep}. The subgame-perfect payoff sets of the finite repetitions are2955generated \emph{inductively}---start from the stage equilibria in the last period and apply the2956finite-horizon analogue of $B$---and with a unique stage equilibrium they remain a single point for every2957horizon, so their limit is a point. The infinite-horizon set is defined \emph{coinductively}, as the2958largest self-consistent set. The same operator, the two extreme fixed points:2959 2960\begin{quote}2961\emph{The folk theorem is the gap between the least and the greatest fixed point of the2962self-generation operator.}2963\end{quote}2964 2965\noindent The chain-store intuition computes the greatest fixed point; backward induction computes the2966least. Neither is an error. The modelling question is which universal property the situation2967has---whether the players' interaction is well-founded. A known last period makes it so. A horizon that is2968uncertain at every date is a discount factor and does not. And the three classical escapes from the2969paradox each move the problem from the first kind to the second, or blur the line: an infinite horizon;2970bounded complexity, so that players cannot count down from the end \cite{Ney85}; and a grain of incomplete2971information about the opponent, which is the subject of \cref{ch:dynamic}.2972 2973\section{Markov perfection}2974 2975The folk theorem's equilibria condition on history in ways that have no bearing on the future: after any2976history of the repeated game, the continuation game is the \emph{same game}. Maskin and Tirole proposed to2977forbid this.2978 2979\begin{definition}\Scl[\cite{MT01}]2980In a dynamic game with observable actions, two histories are \term{payoff-equivalent} if the continuation