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

1299\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 on1361the strategic form whose pullback to every tree is well behaved. Such concepts exist. A \emph{proper}1362equilibrium of the strategic form \cite{Mye78} induces a sequential equilibrium in every extensive game1363with that strategic form \cite{vD84,KM86}; \emph{stable sets} are designed to have this and further1364properties. In \cref{ex:outside} both select $(T,L)$: \emph{Out} strictly dominates $B$, so player~2, finding1365herself called on to move, should infer $T$---the argument known as \emph{forward induction}.1366 1367\emph{The structural position}: the order of moves is part of the game; coalescing changes what1368player~2 can infer about player~1's state of mind at her information set; the type of games is $\EFG$ with1369its own identity type, and subgame perfection is a perfectly good function on it.1370 1371What is not coherent is to use both types at once: to regard the trees $\Gamma$ and $\Gamma'$ as ``the same1372game'' when drawing them and as different when solving them. The discipline of declaring the type1373does not settle the debate, but it does make it impossible to ignore, and it recurs in every later chapter1374in which a solution concept is found to depend on a presentation: redundant types in \cref{ch:belief},1375history-dependence in \cref{ch:repetition}.1376 1377\begin{remark}[Subgames]1378A node $h$ is the root of a \term{subgame} if every information set that meets the subtree $T_h$ is1379contained in it. Subgames are the subobjects of the tree to which the whole structure of \cref{def:efg}1380restricts; they are the opens of the topology in which \cref{ch:perfection} takes place. The example shows1381that this topology is not a Thompson invariant.1382\end{remark}1383 1384\section*{Notes}1385 1386The extensive form with information sets is due to Kuhn \cite{Kuh53}, generalizing von Neumann and1387Morgenstern. \Cref{thm:kuhn} is from the same paper; the realization-plan proof follows von Stengel's1388sequence form \cite{vS96}, which is also the basis of efficient algorithms for extensive games. The1389transformations of \cref{thm:thompson} were introduced by Thompson \cite{Tho52}; Elmes and Reny \cite{ER94}1390showed that inflation--deflation can be dispensed with among games with perfect recall. The invariance debate was opened by Kohlberg and1391Mertens \cite{KM86}. The relation between proper equilibria of the strategic form and sequential equilibria1392of the tree is due to van Damme \cite{vD84} and to \cite{KM86}. Presheaves on $\omega$ as trees are folklore;1393the name ``topos of trees'' is from \cite{BMSS12}. Translations of extensive games into open games are1394given in \cite{CGLN22}.1395 1396\section*{Exercises}1397 1398\begin{exercise}