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

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 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$ is