Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1459–1558 of 6559. Source text is displayed literally.
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 1539\begin{quote}1540\emph{To show that $E$ is common knowledge at $\omega$, exhibit a self-evident event $F$ with $\omega\in1541F\subseteq E$.}1542\end{quote}1543 1544\noindent A public announcement is the canonical example: the event that the announcement was made is1545self-evident, so whatever it entails is common knowledge. No infinite regress has to be traversed.1546 1547\begin{remark}[Limits and colimits of information]\label{rem:distributed}1548Dually, let $\langle p_i\rangle\colon\Omega\to\prod_iT_i$ be the pairing and $p_\vee$ its corestriction to1549its image. The associated operator $p_\vee^*\forall_{p_\vee}$ is \term{distributed knowledge}: what the agents1550would know if they pooled their observations. Its partition is the join, the coarsest common refinement.1551So the two group-knowledge notions of epistemic logic are the two universal constructions on the diagram of1552type maps: common knowledge is its \emph{colimit}, distributed knowledge its \emph{limit}.1553\end{remark}1554 1555\section{The homotopy colimit}\label{sec:hocolim}1556 1557A pushout of sets forgets how its identifications were made. The homotopical habit is to compute the1558colimit in spaces instead, where the identifications are recorded as paths, and then to see what has been