Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1401–1500 of 6559. Source text is displayed literally.
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 idempotent1479because $p$ is surjective, so that $\forall_pp^*=\id$. Dually for $P$. (iii) holds because both $p^*$ and1480$\forall_p$ are right adjoints. (iv): $p^*\exists_pE\subseteq F\iff\exists_pE\subseteq\forall_pF\iff1481E\subseteq p^*\forall_pF$. (v): $\K E$ is in the image of $p^*$, so is its complement since $p^*$ preserves1482complements, and $\K p^*=p^*$.1483\end{proof}1484 1485Properties (i)--(iii) and (v) are the axioms of the modal logic S5. The proof shows where each comes from,1486and therefore what survives in other settings. In a topos that is not Boolean, (i)--(iv) hold verbatim and1487(v) may fail: knowledge is an S4 modality whose negative introspection is a classical accident. For an1488observation \emph{relation} rather than a function one keeps only the adjunction (iv) and monotonicity. The1489literature on bounded reasoning and unawareness, which gives up partitions, is in this sense the study of1490which parts of an adjoint triple one is prepared to lose.1491 1492\begin{remark}[Proof-relevant knowledge]\label{rem:hott-K}1493In type theory the triple becomes $\sum_p\adj p^*\adj\prod_p$ on families of types, and for a family1494$E\colon\Omega\to\Type$1495\[ (\K E)(\omega)\;\equiv\;\prod_{\omega':\,\fib_p(p\,\omega)}E(\omega'). \]1496A witness that the agent knows $E$ at $\omega$ is a function producing evidence of $E$ at every state she1497considers possible. Necessity-as-dependent-product along a map is the standard account of modality in1498dependent type theory \cite{Cor20}. Note that $\K$ is a \emph{comonadic} modality; the modalities of1499\cite{RSS20} are monadic, like $P$. The comonadic ones need more type-theoretic care \cite{Shu18}, a1500technical echo of the fact that knowledge is harder to axiomatize than possibility.