Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3079–3178 of 6559. Source text is displayed literally.
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.3121 3122\begin{example}[Where subgame perfection is silent]\label{ex:seq-entry}3123An entrant chooses \emph{Out}, with payoffs $(0,4)$, or enters at a \emph{small} or a \emph{large} scale. The3124incumbent observes entry but not its scale, and fights or accommodates. Accommodating small entry gives3125$(1,2)$, fighting it $(-1,3)$; accommodating large entry gives $(2,1)$, fighting it $(-2,-1)$. There is no3126proper subgame. Let $m$ be the incumbent's belief that entry is small. Fighting is optimal iff3127$3m-(1-m)\ge2m+(1-m)$, that is $m\ge\tfrac23$. There are two kinds of sequentially rational assessment: the3128entrant enters large, the incumbent accommodates, $m=0$; and the entrant stays out, the incumbent would3129fight, sustained by any belief $m\ge\tfrac23$ at an information set that is never reached. Had fighting3130been worse than accommodating against both scales, no belief would support it, and the second equilibrium3131would disappear although it remains subgame perfect.3132\end{example}3133 3134On the equilibrium path beliefs are determined by Bayes' rule. Off the path, the conditioning event has3135probability zero and Bayes' rule is silent; in the example any $m$ is allowed. The various definitions of3136\term{perfect Bayesian equilibrium} \cite{FT91b} add requirements of the form ``update by Bayes' rule wherever3137possible''. Kreps and Wilson's definition is the cleanest.3138 3139\begin{definition}\Scl[\cite{KW82a}]3140An assessment $(\sigma,\mu)$ is \term{consistent} if it is the limit of assessments $(\sigma^k,\mu^k)$ in3141which $\sigma^k$ gives positive probability to every action and $\mu^k$ is derived from $\sigma^k$ by3142Bayes' rule. A \term{sequential equilibrium} is a consistent, sequentially rational assessment.3143\end{definition}3144 3145\begin{theorem}\Scl[\cite{KW82a,Sel75}]3146Every finite extensive game with perfect recall has a sequential equilibrium. Every trembling-hand perfect3147equilibrium is sequential, and for generic payoffs the two concepts coincide. Every sequential equilibrium3148is subgame perfect.3149\end{theorem}3150 3151\section{The geometry of conditioning}\label{sec:cps}3152 3153Consistency is a closure condition. On the open set of fully mixed strategies, beliefs are a rational3154function of strategies; the consistent assessments are the closure of the graph of that function. Taking3155the closure of the graph of a rational map is a classical operation in geometry---it is a \emph{blow-up}---and3156looking at it this way explains what off-path beliefs are.3157 3158Consider the simplest case: a finite set $\Omega$ and the map sending a fully supported $p\in\Dist\Omega$ to3159its family of conditionals $\bigl(p(\cdot\mid S)\bigr)_{S}$, one for each nonempty $S\subseteq\Omega$.3160 3161\begin{definition}\Scl[\cite{Mye86,Ren55}]3162A \term{conditional probability system} on $\Omega$ is a family $(p_S)_{\emptyset\neq S\subseteq\Omega}$ with3163$p_S\in\Dist(S)$ and $p_T(R)=p_S(R)\,p_T(S)$ for $R\subseteq S\subseteq T$.3164\end{definition}3165 3166\begin{proposition}[Conditional systems are a blow-up]\label{prop:cps}\Srf[\cite{McL89a,Mye86,BBD91}]3167The space of conditional probability systems on a finite set $\Omega$ is the closure of the image of the3168open simplex in $\prod_S\Dist(S)$. It is a compactification of the open simplex in which each face of the closed simplex has3169been replaced by the product of that face with the space of conditional systems on the complementary set3170of states. Its strata are indexed by the ordered partitions $(\Omega_1,\dots,\Omega_k)$ of $\Omega$: a point of that3171stratum is a fully supported distribution on each block, the states of $\Omega_{j+1}$ being infinitely less3172likely than those of $\Omega_j$. Topologically it is a closed ball \cite{McL89a}.3173\end{proposition}3174 3175For three states the picture is \cref{fig:cps}. A sequence of priors converging to the vertex $\delta_1$3176has, along the way, a well-defined ratio $p_2:p_3$, and different sequences converge to different limiting3177ratios. The simplex forgets the ratio; the blow-up remembers it, replacing the vertex by a segment. Each3178corner becomes an edge and the triangle becomes a hexagon. In general the face poset is that of the