Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1421–1520 of 6559. Source text is displayed literally.
1421polytope 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.1501\end{remark}1502 1503\section{Common knowledge}1504 1505Now let there be several agents, with operators $\K_i$. Put $\K E=\bigcap_i\K_iE$ (``everyone knows $E$'').1506 1507\begin{definition}1508$E$ is \term{common knowledge} at $\omega$ if $\omega\in\CK E\defeq\bigcap_{n\ge1}\K^nE$: everyone knows $E$,1509everyone knows that everyone knows $E$, and so on. An event $F$ is \term{self-evident} (or \emph{public}) if1510$\K F=F$.1511\end{definition}1512 1513\begin{theorem}[Aumann]\label{thm:aumann-ck}\Scl[\cite{Aum76}]1514Let $q\colon\Omega\twoheadrightarrow T_\wedge$ be the pushout of the maps $p_i$ in $\Set$:1515\[\begin{tikzcd}[column sep=large]1516\Omega \arrow[r,"p_1"] \arrow[d,"p_2"'] \arrow[dr,"q" description] & T_1 \arrow[d]\\1517T_2 \arrow[r] & T_\wedge1518\end{tikzcd}\]1519(and similarly for more agents). Then $\CK=q^*\forall_q$. That is, common knowledge is the knowledge of a1520fictitious agent whose partition is the \emph{meet} of the agents' partitions, their finest common