Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3001–3100 of 6559. Source text is displayed literally.
3001points, 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 infinite3061games and their equilibria, including cases without discounting, are \cite{LP12,AW17}; the infinite product3062of selection functions of \cref{sec:selection} is another. The topos of trees and its guarded fixed points3063are from \cite{BMSS12}. Self-generation is due to Abreu, Pearce and Stacchetti \cite{APS90}, building on3064\cite{Abr88}. The folk theorem with Nash reversion is Friedman's \cite{Fri71}; the general3065perfect-monitoring result is Fudenberg and Maskin's \cite{FM86}. Markov perfect equilibrium is defined in3066general in \cite{MT01}. Evolutionary stability is from \cite{MSP73}. Computability limits on strategic3067reasoning are discussed in \cite{Rab57,Bin87,Kno94,NZ96}.3068 3069\section*{Exercises}3070 3071\begin{exercise}3072Write tit-for-tat and ``win-stay, lose-shift'' as coalgebras for $F(X)=A_i\times X^A$ and compute the3073unique maps to the terminal coalgebra on the histories of length at most two.3074\end{exercise}3075\begin{exercise}3076In the Prisoner's Dilemma of \cref{ex:grim}, for which $\delta$ is the profile ``both play tit-for-tat'' a3077Nash equilibrium? Show that it is not subgame perfect for generic $\delta$, by exhibiting a history at which a one-shot3078deviation is profitable.3079\end{exercise}3080\begin{exercise}3081Compute $B(W)$ for $W=\{(1,1)\}$ and for $W=\{(2,2)\}$ in the Prisoner's Dilemma, and conclude that3082$\{(2,2)\}$ is not self-generating for any $\delta$.3083\end{exercise}3084\begin{exercise}3085Show that the operator $B$ is monotone, and give an example of a stage game and a $\delta$ for which3086$\bigcup_nB^n(\emptyset)\neq\bigcap_nB^n(W_0)$.3087\end{exercise}3088\begin{exercise}3089Consider the entry game of \cref{ex:entry} repeated infinitely against a sequence of short-lived entrants,3090with the incumbent discounting at $\delta$. Find the least $\delta$ for which there is a subgame perfect3091equilibrium with no entry on the path.3092\end{exercise}3093\begin{exercise}3094Verify that in Hawk--Dove the strategy ``hawk with probability $V/C$'' satisfies the definition of3095evolutionary stability, and compute the mean fitness of the population at that point.3096\end{exercise}3097%% ---- end ch/09-repetition.tex ----3098%% ---- begin ch/10-dynamic.tex ----3099\chapter{Dynamic Games of Incomplete Information}\label{ch:dynamic}3100