Independent scholarship · Open accessThe monthly digest

Indexed text attachment

games-and-information-in-higher-categories.tex

Source for Games and Information in Higher Categories

View paper · Download original file

Lines 1119–1218 of 6559. Source text is displayed literally.

1119name \emph{topos of trees} in the semantics of guarded recursion \cite{BMSS12}, and we will use it in that1120role in \cref{ch:repetition}. Three pieces of tree vocabulary are topos vocabulary.1121 1122\begin{itemize}1123\item A \emph{play} of infinite length is a compatible sequence of nodes, that is, a global section1124  $1\to T$; the set of plays is $\Gamma(T)=\lim_nT(n)$. (A tree with terminal nodes is brought under this1125  description by giving each terminal node a single dummy successor forever.)1126\item The \emph{subtree} at a node $h\in T(m)$ is the forest $T_h(n)=\{t\in T(m+n)\st t\mapsto h\}$, a fibre of a1127  restriction map.1128\item A \emph{labelling} of edges by actions is a map of forests from $T$ to the forest of finite words over1129  an alphabet.1130\end{itemize}1131 1132\begin{definition}\label{def:efg}1133A finite \term{extensive game} $\Gamma$ consists of1134\begin{enumerate}[label=(\roman*)]1135\item a finite tree $T$, with node set $H$, terminal nodes $Z\subseteq H$ and decision nodes $D=H\setminus Z$;1136\item a map $\iota\colon D\to N\sqcup\{0\}$ assigning each decision node to a player or to Nature ($0$), and1137  at each node of Nature a probability distribution on its children;1138\item for each player $i$ an equivalence relation $\sim_i$ on $D_i=\iota^{-1}(i)$, whose classes are $i$'s1139  \term{information sets}, forming a set $\mathcal{I}_i$ with quotient map $q_i\colon D_i\twoheadrightarrow\mathcal{I}_i$;1140\item for each information set $I$ a set $A(I)$ of actions and, for each $h\in I$, a bijection between1141  $A(I)$ and the children of $h$;1142\item payoffs $u\colon Z\to\R^N$.1143\end{enumerate}1144\end{definition}1145 1146A pure strategy of player $i$ chooses an action at each of her information sets. The actions form a bundle1147$\coprod_IA(I)\to\mathcal{I}_i$, and a pure strategy is a section of it:1148\[ S_i=\prod_{I:\mathcal{I}_i}A(I). \]1149A \term{behavioural strategy} is a section of the bundle of lotteries, $\beta_i\in\prod_I\Dist A(I)$; a1150\term{mixed strategy} is a lottery over sections, $\mu_i\in\Dist\bigl(\prod_IA(I)\bigr)$. A profile of1151strategies of any of these kinds, with Nature's distributions, induces a distribution over terminal nodes,1152and taking expected payoffs gives the \term{strategic form} of $\Gamma$, a game in the sense of1153\cref{def:nfg}. The requirement that a strategy be a function on $\mathcal{I}_i$ rather than on $D_i$ is the1154entire formal content of ``not knowing'': a plan must factor through the quotient $q_i$.1155 1156\section{A taxonomy of information}1157 1158Informational assumptions are properties of the family of quotient maps $(q_i)$ and of the position of1159Nature's moves. The source text \cite[ch.~2]{Ras06} organizes them into four binary distinctions, which in1160the present terms read as follows.1161 1162\begin{center}\small1163\renewcommand{\arraystretch}{1.25}1164\begin{tabular}{@{}lp{0.72\textwidth}@{}}1165\toprule1166\textbf{Information is\ldots} & \textbf{Condition on $\Gamma$}\\\midrule1167\emph{perfect} & every $q_i$ is a bijection: all information sets are singletons\\1168\emph{certain} & no node of Nature lies below a node of a player\\1169\emph{symmetric} & at every node where a player moves, her information set contains every other player's1170   (the mover knows nothing that the others do not), and at terminal nodes all players' information sets1171   coincide\\1172\emph{complete} & Nature does not move at the root, or all players observe its move there\\1173\bottomrule1174\end{tabular}1175\end{center}1176 1177\noindent Perfect information implies symmetric and complete information; certainty is independent of the1178other three. Simultaneous moves are imperfect but symmetric information. The interesting distinctions for economics are1179the 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 called