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 1261–1360 of 6559. Source text is displayed literally.

1261isomorphism 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 any1359player faces, so the type of games is $\EFG_{\mathrm{T}}$, a solution concept must descend to it, and1360subgame perfection is a property of a drawing. On this view the correct refinements are those defined on