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

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}1399Show that for a tree $T$ in which every node has a child, the set of infinite plays is the set of global1400sections of $T$ in $\Trees$, and that the subtree $T_h$ is a pullback.1401\end{exercise}1402\begin{exercise}1403Draw an extensive game with two players in which information is symmetric but imperfect, and one in which1404it is certain but asymmetric, and verify the conditions in the table.1405\end{exercise}1406\begin{exercise}1407Give an example of a game without perfect recall in which the personal forest $P_i$ and the levelwise1408quotient both exist but the quotient map is not a map of forests. Identify the failure of naturality.1409\end{exercise}1410\begin{exercise}1411Verify the claims of \cref{ex:outside}: compute all Nash equilibria of the strategic form and all three1412equilibria of the simultaneous subgame.1413\end{exercise}1414\begin{exercise}1415Starting from the tree $\Gamma$ of \cref{ex:outside}, apply an interchange of moves to the simultaneous1416subgame so that player~2 moves before player~1's choice between $T$ and $B$. Does the set of subgame perfect1417equilibria change?1418\end{exercise}1419\begin{exercise}1420Let $r$ be a realization plan for a player with perfect recall. Show that the set of realization plans is a1421polytope whose dimension is $\sum_I(|A(I)|-1)$, and compare with the dimension of the mixed-strategy simplex.1422\end{exercise}1423%% ---- end ch/03-extensive.tex ----1424%% ---- begin ch/04-knowledge.tex ----1425\chapter{Knowledge}\label{ch:knowledge}1426 1427``Player $i$ knows $E$'' is the most heavily used undefined phrase in informal game theory. Aumann's1428partition model defines it. This chapter derives the partition model from a single categorical1429construction---base change along the map that sends a state of the world to what a player observes of1430it---and then computes \emph{common} knowledge as a colimit. Taking that colimit homotopically produces a1431graph whose components are the classical answer and whose loops are the subject of the next chapter.1432 1433\section{Information structures}1434 1435\begin{definition}\label{def:infostructure}1436An \term{information structure} for a set $N$ of agents is a set $\Omega$ of \term{states} together with, for1437each $i\in N$, a surjection $p_i\colon\Omega\twoheadrightarrow T_i$ onto a set of \term{types} (or signals).1438An \term{event} is a subset $E\subseteq\Omega$.