Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1379–1478 of 6559. Source text is displayed literally.
1379contained 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$.1439\end{definition}1440 1441The fibres of $p_i$ are the cells of agent $i$'s partition: at state $\omega$ she observes $p_i(\omega)$ and1442cannot exclude any state of the fibre $p_i^{-1}p_i(\omega)$. In an extensive game $\Omega$ may be taken to be the set of plays and $p_i$ the1443record of what $i$ observes; in a Bayesian game (\cref{ch:belief}) $\Omega$ is the set of type profiles and1444states of nature. We write $\Sub(\Omega)$ for the Boolean algebra of events.1445 1446\section{Knowledge is base change}1447 1448A function $p\colon\Omega\to T$ induces the inverse-image map $p^*\colon\Sub(T)\to\Sub(\Omega)$, and $p^*$ has1449adjoints on both sides,1450\[ \exists_p\ \adj\ p^*\ \adj\ \forall_p,\qquad1451 \exists_pE=\{t\st p^{-1}(t)\cap E\neq\emptyset\},\quad \forall_pE=\{t\st p^{-1}(t)\subseteq E\}. \]1452This is Lawvere's observation that quantifiers are adjoints to substitution, and it holds in any topos.1453 1454\begin{definition}\label{def:K}1455For an agent with observation map $p$ the \term{knowledge} and \term{possibility} operators on $\Sub(\Omega)$ are1456\[ \K=p^*\forall_p,\qquad P=p^*\exists_p. \]1457\end{definition}1458 1459Explicitly $\K E=\{\omega\st p^{-1}p(\omega)\subseteq E\}$ is the union of the cells contained in $E$: the set1460of states at which the agent's observation rules out every state outside $E$. This is Aumann's operator1461\cite{Aum76}. The definition as a composite of adjoints makes its properties automatic.1462 1463\begin{proposition}[S5]\label{prop:S5}\Scl[the adjoint formulation is standard in categorical logic]1464$\K$ is an idempotent comonad and $P$ an idempotent monad on the poset $\Sub(\Omega)$, with $P\adj\K$. Hence,1465for all events $E,F$:1466\begin{enumerate}[label=(\roman*)]1467\item $\K E\subseteq E$ \hfill (truth)1468\item $\K E=\K\K E$ \hfill (positive introspection)1469\item $\K(E\cap F)=\K E\cap\K F$ and $\K\Omega=\Omega$; indeed $\K$ preserves all intersections1470\item $PE\subseteq F\iff E\subseteq\K F$1471\item $\neg\K E=\K\neg\K E$ \hfill (negative introspection)1472\end{enumerate}1473The fixed points of $\K$ are exactly the events of the form $p^*D$, those measurable with respect to the1474agent's partition.1475\end{proposition}1476 1477\begin{proof}1478A composite $p^*\forall_p$ of a left adjoint after its right adjoint is a comonad, and it is idempotent