Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1179–1278 of 6559. Source text is displayed literally.
1179the failures: \emph{asymmetric} information, where a player moves knowing something that another does not,1180is the subject of Part~II; \emph{incomplete} information, where an unobserved initial move of1181Nature selects which game is played, is Harsanyi's device for uncertainty about the rules themselves and1182is taken up in \cref{ch:belief}.1183 1184\section{Perfect recall}1185 1186A player has perfect recall if she never forgets what she knew or did. The standard definition is through1187her \emph{experience}: for $h\in D_i$ let $X_i(h)$ be the sequence of pairs (information set of $i$, action1188taken there) encountered along the path from the root to $h$. Player $i$ has \term{perfect recall} if1189$h\sim_ih'$ implies $X_i(h)=X_i(h')$.1190 1191There is a more structural way to say this. Each player has her own clock, which ticks when she moves.1192 1193\begin{definition}1194The \term{personal forest} of player $i$ is the forest $P_i$ whose nodes of depth $n$ are the decision1195nodes $h\in D_i$ at which $i$ has moved exactly $n$ times before, the parent of $h$ being the last node1196$g\in D_i$ strictly before $h$. The edge from $g$ to $h$ is labelled by the action $i$ takes at $g$ on the way to $h$.1197\end{definition}1198 1199\begin{proposition}[Perfect recall is internal]\label{prop:recall}\Srf[\cite{Kuh53,vS96}]1200Player $i$ has perfect recall if and only if $\sim_i$ is a congruence on the labelled forest $P_i$: whenever1201$h\sim_ih'$, either both are roots of $P_i$, or their parents are $\sim_i$-equivalent and the connecting edges1202carry the same action. Equivalently: $\mathcal{I}_i$ carries a (unique) structure of labelled forest making1203$q_i\colon P_i\twoheadrightarrow\mathcal{I}_i$ a morphism of $\Trees$ compatible with labels.1204\end{proposition}1205 1206\begin{proof}1207If the parents $g,g'$ of $h,h'$ are equivalent with the same action $a$, then inductively1208$X_i(h)=X_i(g)\cdot([g],a)=X_i(g')\cdot([g'],a)=X_i(h')$; and two roots have empty experience. Conversely if1209$X_i(h)=X_i(h')$ the sequences have the same length, and if nonempty the same last entry, which says that1210the parents are equivalent and the actions agree. The second formulation restates the first: a quotient of1211a presheaf by a levelwise equivalence relation is a presheaf, with the quotient map natural, exactly when the1212relation is compatible with restriction.1213\end{proof}1214 1215So perfect recall is the hypothesis that \emph{a player's information is itself a tree}: her information1216sets are the nodes of a forest of their own, the forest of what she has seen and done, and the quotient1217from histories to information is a map in the topos of (her) time. Under imperfect recall the partition1218exists only level by level, or not even that, and there is no object in $\Trees$ that deserves to be called1219her point of view. This is why perfect recall is not a mere technical convenience: it is the condition for1220the player to be a \emph{single agent extended in time} rather than a team of agents sharing a payoff.1221 1222\begin{theorem}[Kuhn]\label{thm:kuhn}\Scl[\cite{Kuh53}]1223If player $i$ has perfect recall, then for every mixed strategy of $i$ there is a behavioural strategy1224inducing the same distribution over terminal nodes against every profile of the other players, and1225conversely.1226\end{theorem}1227 1228\begin{proof}[Proof sketch, via realization plans \cite{vS96}]1229By \cref{prop:recall} the information sets and actions of $i$ form a labelled forest; call a path from a1230root a \emph{sequence} of $i$. A \emph{realization plan} is a function $r$ on sequences with $r(\emptyset)=1$ and1231$\sum_{a\in A(I)}r(\varsigma_Ia)=r(\varsigma_I)$, where $\varsigma_I$ is the unique sequence leading to $I$. The1232probability of a terminal node is the product over players of the realization probabilities of the sequences1233leading to it, times Nature's probabilities; so outcomes depend on a strategy only through its realization plan. A1234mixed strategy $\mu$ has plan $r_\mu(\varsigma)=\mu\{s\st s\text{ agrees with }\varsigma\}$; a behavioural strategy1235$\beta$ has plan $r_\beta(\varsigma)=\prod_{(I,a)\in\varsigma}\beta_I(a)$; and from any plan one recovers a1236behavioural strategy by $\beta_I(a)=r(\varsigma_Ia)/r(\varsigma_I)$ wherever the denominator is positive.1237\end{proof}1238 1239\begin{remark}[The monad-theoretic content]\label{rem:kuhn-monad}1240The distribution monad $\Dist$ is monoidal: there is a natural map1241\[ \nabla\colon\prod_I\Dist A(I)\longrightarrow\Dist\Bigl(\prod_IA(I)\Bigr) \]1242forming product measures. It is not surjective---its image is the independent distributions---and this1243failure is what correlation \emph{is} (\cref{ch:mixing}). Kuhn's theorem says that when information is a tree,1244the outcome map cannot see the difference: it factors through realization plans, on which $\nabla$ becomes1245surjective. The reason is that a single play visits the information sets of $i$ along one \emph{chain} of her1246forest, so correlation between choices at incomparable information sets is never observed. Without perfect1247recall the same play can meet two information sets whose joint behaviour matters, and the theorem fails.1248\end{remark}1249 1250\begin{example}[Forgetting]1251A single player chooses $L$ or $R$, forgets which, and then chooses $l$ or $r$ at one information set1252containing both resulting nodes. The mixed strategy $\tfrac12(L,l)+\tfrac12(R,r)$ reaches the terminal nodes $Ll$ and1253$Rr$ with probability $\tfrac12$ each. A behavioural strategy randomizes independently at the two1254information sets, so it cannot give positive probability to both $Ll$ and $Rr$ without giving positive1255probability to $Lr$ or $Rl$.1256\end{example}1257 1258\section{When are two trees the same game?}\label{sec:thompson}1259 1260\Cref{def:efg} defines a type $\EFG$ of structures, and as in \cref{lem:identity} its identity type is1261isomorphism of labelled trees. Nobody believes that this is the right notion of sameness for all purposes.1262Whether Nature's move is drawn before or after a simultaneous move of the players, whether two successive1263choices of one player are drawn as one node with four branches or two nodes with two branches each---these1264are conventions of drawing. Thompson made the point precise.1265 1266\begin{theorem}[Thompson; Elmes--Reny]\label{thm:thompson}\Scl[\cite{Tho52,ER94}]1267Two finite extensive games have the same reduced strategic form, up to isomorphism, if and only if one can1268be obtained from the other by a finite sequence of four elementary transformations and their inverses:1269\emph{interchange} of two consecutive moves made in ignorance of each other; \emph{coalescing} of two consecutive1270moves of the same player into one; \emph{addition of a superfluous move}; and \emph{inflation--deflation} of information1271sets. Among games with perfect recall, the first three (suitably formulated) suffice and preserve perfect1272recall.1273\end{theorem}1274 1275Here the \emph{reduced} strategic form identifies pure strategies of a player that yield the same payoffs1276against everything. In the language of \cref{ch:rules} the theorem computes a quotient. There is a map1277\[ \EFG\longrightarrow\NFG_u,\qquad \Gamma\mapsto\text{reduced strategic form}, \]1278and its fibres are the classes of the equivalence relation generated by the Thompson moves. Let $\EFG_{\mathrm{T}}$