Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1499–1598 of 6559. Source text is displayed literally.
1499\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 been1559gained.1560 1561\begin{definition}\label{def:B}1562The \term{knowledge graph} $B$ of an information structure $(\Omega,(p_i)_{i\in N})$ is the bipartite graph1563with vertex set $\Omega\sqcup\coprod_iT_i$ and one edge $e_{\omega,i}$ joining $\omega$ to $p_i(\omega)$ for1564each state $\omega$ and agent $i$.1565\end{definition}1566 1567\begin{proposition}\label{prop:hocolim}\Srf[\cite{Tho79}]1568$B$ is the homotopy colimit, in the $\infty$-category of spaces, of the diagram of discrete spaces1569$\{p_i\colon\Omega\to T_i\}_{i\in N}$. Consequently:1570\begin{enumerate}[label=(\roman*)]1571\item $\pi_0(B)=T_\wedge$: the connected components of $B$ are the cells of the meet, the minimal1572 self-evident events;1573\item each component is a connected graph, hence homotopy equivalent to a wedge of circles, and1574 \[ b_1(B)=(n-1)\,|\Omega|-\sum_i|T_i|+|T_\wedge| \]1575 when $\Omega$ is finite and $n=|N|$.1576\end{enumerate}1577\end{proposition}1578 1579\begin{proof}1580The homotopy colimit of a diagram of sets is the nerve of its category of elements \cite{Tho79}. Here that1581category has objects $\Omega\sqcup\coprod_iT_i$ and one non-identity arrow $\omega\to p_i(\omega)$ for each1582pair $(\omega,i)$, with no composable pairs; its nerve is the graph $B$. (i) holds because $\pi_0$ is a left1583adjoint and so carries homotopy colimits of spaces to colimits of sets. (ii) is the Euler characteristic:1584$B$ has $|\Omega|+\sum_i|T_i|$ vertices, $n|\Omega|$ edges and $|T_\wedge|$ components.1585\end{proof}1586 1587For two agents every state-vertex has degree two and may be suppressed: $B$ becomes the graph whose1588vertices are the cells of the two partitions and whose edges are the states, each state joining the two1589cells that contain it (\cref{fig:Bgraph}). A path in $B$ is a chain of the form ``at $\omega$ agent~11590cannot exclude $\omega'$, at which agent~2 cannot exclude $\omega''$,\ldots''---precisely the chains along which1591higher-order uncertainty propagates. Aumann's theorem says that only the \emph{existence} of such a chain1592matters for common knowledge. The graph also remembers \emph{how many essentially different} chains there1593are.1594 1595\begin{figure}[ht]\centering1596\begin{tikzpicture}[x=1cm,y=1cm]1597 \node[ty] (ab) at (0,1.5) {\small $\{a,b\}$};1598 \node[ty] (cd) at (2.2,1.5) {\small $\{c,d\}$};