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

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 common1521coarsening. Moreover $\CK E$ is the largest self-evident event contained in $E$:1522\[ \CK E=\nu X.\,\K(E\cap X). \]1523\end{theorem}1524 1525\begin{proof}1526Each $\K_i$ preserves arbitrary intersections, hence so does $\K$, and $\K^{n+1}E\subseteq\K^nE$; therefore1527$\K(\CK E)=\bigcap_{n\ge2}\K^nE=\CK E$, so $\CK E$ is self-evident, and it lies in $E$. If $F\subseteq E$ is1528self-evident then $F=\K^nF\subseteq\K^nE$ for all $n$, so $F\subseteq\CK E$. This proves the last claim. An event1529is self-evident iff it is a union of cells of every agent's partition, iff it is saturated for the1530equivalence relation generated by all the $\ker p_i$, iff it has the form $q^*D$. The largest such event1531inside $E$ is $q^*\forall_qE$.1532\end{proof}1533 1534Two things deserve emphasis. First, common knowledge is defined by an infinite conjunction and computed by1535a \emph{finite colimit}. The iterative hierarchy ``I know that you know that\ldots'' is the standard1536computation of a greatest fixed point from above; the colimit is its closed form. Second, the greatest-fixed-point formula1537is a coinduction principle, exactly parallel to that for rationalizability in \cref{ch:rules}:1538