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

2759\end{exercise}2760\begin{exercise}2761In \cref{ex:pareto-perfect}, change the bad second-stage equilibrium to pay $(3,0)$ after a defection by2762player~2 and $(0,3)$ after a defection by player~1, where the coordination game is modified to have these2763as equilibria. Is the cooperative profile Pareto perfect?2764\end{exercise}2765\begin{exercise}2766Show that in a finite game of perfect information without ties, the backward-induction profile is the only2767profile surviving iterated elimination of weakly dominated strategies in a suitable order, and discuss2768this in light of \cref{ex:weakdom}.2769\end{exercise}2770%% ---- end ch/08-perfection.tex ----2771%% ---- begin ch/09-repetition.tex ----2772\chapter{Repetition}\label{ch:repetition}2773 2774When the same players meet repeatedly, today's behaviour can be rewarded or punished tomorrow, and2775cooperation that is impossible in one encounter can be sustained. Whether it \emph{is} sustained in2776equilibrium turns, notoriously, on whether there is a last encounter. This chapter argues that the2777dependence is not a quirk. A finitely repeated game is an element of an initial algebra and is solved by2778induction; an infinitely repeated game lives in a terminal coalgebra and is solved by coinduction; and the2779two 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 she