Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2899–2998 of 6559. Source text is displayed literally.
2899equilibrium 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 continuation2981games they root are strategically equivalent, compatibly at all future histories; the2982classes of the coarsest such equivalence are the \term{Markov states}. A strategy is \term{Markov} if it is2983measurable with respect to this partition, and a \term{Markov perfect equilibrium} is a subgame perfect2984equilibrium in Markov strategies.2985\end{definition}2986 2987\begin{proposition}[Markov means invariant]\label{prop:markov}\Srf[\cite{MT01}]2988The dynamic game is a coalgebra whose states are histories; the Markov states are its quotient by2989bisimilarity, the image of the histories in the terminal coalgebra of game behaviours. A strategy is Markov2990iff it factors through this quotient, that is, iff it is a function on the type of continuation games2991\emph{with its identity type}, in the sense of \cref{prin:invariance}.2992\end{proposition}2993 2994Markov perfection is thus the invariance principle of \cref{ch:rules} applied to subgames: equivalent2995subgames must be played alike. In a repeated game every continuation game is equivalent to every other, a2996Markov strategy is constant, and the Markov perfect equilibria are the repetitions of stage equilibria. All2997of the folk theorem's cooperation is therefore sustained by strategies that distinguish2998indistinguishable subgames. This is \cref{sec:symmetry} once more. The history is a \emph{frame}: structure