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

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}: structure2999that the players attach to a subgame, irrelevant to its payoffs, by which they coordinate on one3000continuation equilibrium rather than another. Whether such frames are admissible is, exactly as for focal3001points, a decision about the type of the game. In models where the state is genuinely payoff-relevant---capacity,3002installed base, reputation, the identity of the firm whose customers are locked in by switching3003costs---Markov perfection gives sharp predictions, and it is the workhorse of dynamic industrial organization3004\cite{MT88}.3005 3006\section{Evolution}3007 3008A different justification of equilibrium dispenses with reasoning altogether. A large population is3009matched at random to play a symmetric game; strategies that do well multiply.3010 3011\begin{definition}\Scl[\cite{MSP73}]3012A mixed strategy $x$ is an \term{evolutionarily stable strategy} if for every $y\neq x$ either3013$u(x,x)>u(y,x)$, or $u(x,x)=u(y,x)$ and $u(x,y)>u(y,y)$.3014\end{definition}3015 3016\begin{example}[Hawk--Dove]3017Two animals contest a resource worth $V$. Hawks fight, at cost $C>V$ to the loser; doves share or yield.3018Payoffs to the row player are $\frac{V-C}{2}$ for hawk against hawk, $V$ for hawk against dove, $0$ for dove3019against hawk and $\frac V2$ for dove against dove. Neither pure strategy is stable; the unique evolutionarily3020stable strategy plays hawk with probability $V/C$. The more costly the fight, the rarer it is.3021\end{example}3022 3023Under the \emph{replicator dynamics} $\dot x_a=x_a\bigl(u(a,x)-u(x,x)\bigr)$, every evolutionarily stable3024strategy is asymptotically stable, every stable rest point is a Nash equilibrium, and an asymptotically3025stable component of equilibria has index equal to its Euler characteristic---$+1$ for a point---in the3026sense of \cref{sec:KM} \cite{DR03}. The index, which entered as a3027topological invariant of the equilibrium correspondence, is thus also the shadow of dynamic stability.3028Axelrod's tournaments \cite{Axe84}, in which tit-for-tat prospered among strategies submitted for the3029repeated Prisoner's Dilemma, belong here: they are an evolutionary argument for a particular point of the3030folk theorem's large set, and like all such arguments they depend on the population of strategies one3031starts from.3032 3033\section{Computability}3034 3035The terminal coalgebra $A_i^{A^*}$ is uncountable; the strategies that any procedure could implement are3036countable. One might hope that restricting to computable strategies is harmless. It is not.3037 3038\begin{theorem}\label{thm:NZ}\Scl[\cite{Rab57,Kno94,NZ96}]3039\begin{enumerate}[label=(\roman*)]3040\item There is a game with computable rules in which a player has a winning strategy but no computable3041  winning strategy.3042\item In the discounted repeated Prisoner's Dilemma there are computable strategies to which a best response3043  exists but no best response is computable.3044\end{enumerate}3045\end{theorem}3046 3047The proofs are diagonal: a strategy can be built to consult what a given machine would do and to punish it,3048so that the task of responding optimally embeds an undecidable problem. A player modelled as a Turing3049machine cannot in general predict a player like herself \cite{Bin87}. This is the third appearance of the3050diagonal in this book---after the nonexistence of a universal possibility structure3051(\cref{prop:no-universal-possibility}) and alongside the non-constructive character of Nash's theorem---and3052it marks a real boundary: the equilibrium concept quantifies over the whole terminal coalgebra, while3053agents inhabit its computable part.3054 3055\section*{Notes}3056 3057Standard references for repeated games are \cite{MS06,FT91}. The chain-store paradox is \cite{Sel78}. The3058coalgebraic view of automata is expounded in \cite{Rut00}; automata as strategies were introduced by3059Rubinstein \cite{Rub86} and their complexity analysed in \cite{KS88,Ney85}. The one-shot deviation3060principle descends from Blackwell's dynamic programming \cite{Bla65}. Coinductive treatments of infinite