Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3021–3120 of 6559. Source text is displayed literally.
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 3101When a player moves at an information set that is not the root of a subgame, subgame perfection has3102nothing to say about her, and yet she may be making an incredible threat. To test her choice one must say3103what she believes about where she is. This chapter combines the temporal modality of \cref{ch:perfection}3104with the beliefs of \cref{ch:belief}; studies the geometry of beliefs at events of probability zero; and3105then shows, through reputation and the electronic mail game, how violently equilibrium can respond to3106small changes in what is believed and known.3107 3108\section{Sequential rationality}3109 3110\begin{definition}\Scl[\cite{KW82a}]3111An \term{assessment} in an extensive game is a pair $(\sigma,\mu)$ of a behavioural strategy profile and a3112\emph{system of beliefs}: for each information set $I$ a distribution $\mu(I)$ over the nodes of $I$. It is3113\term{sequentially rational} if at every information set $I$ of every player $i$, the continuation of $\sigma_i$3114maximizes $i$'s expected payoff given $\mu(I)$ and $\sigma_{-i}$.3115\end{definition}3116 3117A system of beliefs is a section of the bundle $\coprod_I\Dist(I)\to\mathcal{I}$, just as a strategy is a3118section of the bundle of actions. Sequential rationality is the necessity modality of \cref{prop:box} with3119subgames replaced by information sets, each equipped with the belief that turns it into a decision3120problem: perfection and knowledge, composed.