Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1181–1280 of 6559. Source text is displayed literally.
1181Nature 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}}$1279be the type obtained from $\EFG$ by adjoining a path for each Thompson move---a higher inductive type, or1280classically the quotient. Then, by \cref{prin:invariance}: