Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2779–2878 of 6559. Source text is displayed literally.
2779two universal properties give different answers.2780 2781\section{Finite repetition}2782 2783Let $G=(N,A,u)$ be a stage game. In the \term{repeated game} $G^T$ the players play $G$ in periods2784$t=1,\dots,T$, observing all past actions; a history is an element of $A^*=\coprod_tA^t$, a pure strategy2785of $i$ is a function $A^*\to A_i$, and payoffs are discounted sums of stage payoffs.2786 2787\begin{theorem}\label{thm:finite-rep}\Scl2788If $G$ has a unique Nash equilibrium $a^*$, then for every finite $T$ the unique subgame perfect equilibrium2789of $G^T$ is to play $a^*$ after every history.2790\end{theorem}2791 2792\begin{proof}2793Fold over the tree (\cref{thm:zermelo}, in the version for simultaneous-move stages): in the last period2794only $a^*$ is an equilibrium whatever the history; given that, the continuation value is independent of2795play in period $T-1$, so only $a^*$ is an equilibrium there; and so on.2796\end{proof}2797 2798In the Prisoner's Dilemma repeated a thousand times, the only subgame perfect equilibrium is a thousand2799defections. Selten's \emph{chain-store paradox} \cite{Sel78} makes the discomfort vivid. An incumbent faces2800the entry game of \cref{ex:entry} in twenty towns in sequence. Induction says that she accommodates in the2801last 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}]