Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1259–1358 of 6559. Source text is displayed literally.
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}:1281 1282\begin{quote}1283\emph{A solution concept on $\EFG_{\mathrm{T}}$ is a solution concept on $\EFG$ that is constant along Thompson1284moves; equivalently, one that depends only on the reduced strategic form.}1285\end{quote}1286 1287\noindent This is the \emph{invariance} requirement of Kohlberg and Mertens \cite{KM86}. The next example,1288which is theirs in spirit, shows that it has teeth.1289 1290\begin{example}[Coalescing destroys subgames]\label{ex:outside}1291In the game $\Gamma$ on the left of \cref{fig:outside}, player~1 first chooses between an outside option1292\emph{Out}, worth $(2,2)$, and \emph{In}; after \emph{In} the two players play a simultaneous game in which1293$(T,L)$ pays $(3,1)$, $(B,R)$ pays $(1,3)$, and miscoordination pays $(0,0)$. In $\Gamma'$ on the right,1294player~1's two successive choices have been coalesced into one choice among \emph{Out}, $T$, $B$. The two1295trees have the same reduced strategic form:1296\[1297\begin{array}{c|cc}1298 & L & R\\\hline1299\mathit{Out} & 2,2 & 2,2\\1300T & 3,1 & 0,0\\1301B & 0,0 & 1,31302\end{array}1303\]1304Its Nash equilibria are $(T,L)$ and the profiles in which player~1 plays \emph{Out} and player~2 plays $L$1305with probability $q\le\tfrac23$. In $\Gamma$ the simultaneous game after \emph{In} is a proper subgame, with1306three equilibria: $(T,L)$, $(B,R)$, and a mixed one in which player~1 plays $T$ with probability $\tfrac34$ and1307player~2 plays $L$ with probability $\tfrac14$, worth $\tfrac34$ to player~1. A subgame perfect equilibrium1308(\cref{ch:perfection}) must induce one of these, so the subgame perfect equilibria of $\Gamma$ are $(\mathit{In},T;L)$ and1309\emph{Out} followed by $q\in\{0,\tfrac14\}$. In $\Gamma'$ there is no proper subgame, and every Nash equilibrium is subgame1310perfect, including \emph{Out} with $q=\tfrac12$. The set of subgame perfect equilibria is not constant along a1311coalescing move.1312\end{example}1313 1314\begin{figure}[ht]\centering1315\begin{tikzpicture}[x=1cm,y=1cm]1316 % Gamma1317 \node[dec,label=above:{\small 1}] (r) at (0,0) {};1318 \node[leaf] (o) at (-1.4,-1.2) {$(2,2)$};1319 \node[dec,label=right:{\small 1}] (i) at (1.1,-1.2) {};1320 \node[dec] (t) at (0.1,-2.4) {};1321 \node[dec] (b) at (2.1,-2.4) {};1322 \node[leaf] (tl) at (-0.45,-3.6) {$(3,1)$};1323 \node[leaf] (tr) at (0.65,-3.6) {$(0,0)$};1324 \node[leaf] (bl) at (1.55,-3.6) {$(0,0)$};1325 \node[leaf] (br) at (2.65,-3.6) {$(1,3)$};1326 \draw[thick] (r)--node[left,lab]{\emph{Out}}(o) (r)--node[right,lab]{\emph{In}}(i) (i)--node[left,lab]{$T$}(t) (i)--node[right,lab]{$B$}(b);1327 \draw[thick] (t)--node[left,lab]{$L$}(tl) (t)--node[right,lab]{$R$}(tr) (b)--node[left,lab]{$L$}(bl) (b)--node[right,lab]{$R$}(br);1328 \draw[infoset] (t)--node[above,lab]{2}(b);1329 \node at (0.6,-4.3) {$\Gamma$};1330 % Gamma'1331 \begin{scope}[xshift=6.2cm]1332 \node[dec,label=above:{\small 1}] (r) at (0.6,0) {};1333 \node[leaf] (o) at (-1.5,-1.8) {$(2,2)$};1334 \node[dec] (t) at (0.1,-2.4) {};1335 \node[dec] (b) at (2.1,-2.4) {};1336 \node[leaf] (tl) at (-0.45,-3.6) {$(3,1)$};1337 \node[leaf] (tr) at (0.65,-3.6) {$(0,0)$};1338 \node[leaf] (bl) at (1.55,-3.6) {$(0,0)$};1339 \node[leaf] (br) at (2.65,-3.6) {$(1,3)$};1340 \draw[thick] (r)--node[left,lab]{\emph{Out}}(o) (r)--node[left,lab,pos=0.6]{$T$}(t) (r)--node[right,lab]{$B$}(b);1341 \draw[thick] (t)--node[left,lab]{$L$}(tl) (t)--node[right,lab]{$R$}(tr) (b)--node[left,lab]{$L$}(bl) (b)--node[right,lab]{$R$}(br);1342 \draw[infoset] (t)--node[above,lab]{2}(b);1343 \node at (0.6,-4.3) {$\Gamma'$};1344 \end{scope}1345\end{tikzpicture}1346\caption{Two extensive games related by coalescing player~1's moves. They have the same reduced strategic1347form and different sets of subgame perfect equilibria.}\label{fig:outside}1348\end{figure}1349 1350\begin{corollary}\label{cor:spe-evil}\Scl[\cite{KM86}]1351Subgame perfect equilibrium is not a solution concept on $\EFG_{\mathrm{T}}$. The same example shows this1352for sequential equilibrium.1353\end{corollary}1354 1355What should one conclude? Two positions are coherent, and the type-theoretic framing makes clear that they1356disagree about the domain, not about rationality.1357 1358\emph{The invariance position} \cite{KM86}: the Thompson moves do not change the decision problem any