Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1539–1638 of 6559. Source text is displayed literally.
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\}$};1599 \node[ty] (e1) at (4.4,1.5) {\small $\{e\}$};1600 \node[ty] (a2) at (-1.1,0) {\small $\{a\}$};1601 \node[ty] (bc) at (1.1,0) {\small $\{b,c\}$};1602 \node[ty] (de) at (3.3,0) {\small $\{d,e\}$};1603 \draw[thick] (ab)--node[left,lab]{$a$}(a2) (ab)--node[right,lab]{$b$}(bc) (cd)--node[left,lab]{$c$}(bc) (cd)--node[right,lab]{$d$}(de) (e1)--node[right,lab]{$e$}(de);1604 \node[lab] at (-2.4,1.5) {$T_1$}; \node[lab] at (-2.4,0) {$T_2$};1605 \begin{scope}[xshift=7.6cm]1606 \node[ty] (s) at (0,1.5) {\small $s$};1607 \node[ty] (sp) at (1.8,1.5) {\small $s'$};1608 \node[ty] (t) at (0,0) {\small $t$};1609 \node[ty] (tp) at (1.8,0) {\small $t'$};1610 \draw[thick] (s)--(t) (s)--(tp) (sp)--(t) (sp)--(tp);1611 \end{scope}1612\end{tikzpicture}1613\caption{Knowledge graphs for two agents (state-vertices suppressed). Left: five states, partitions1614$\{ab\mid cd\mid e\}$ and $\{a\mid bc\mid de\}$; $B$ is a tree, so no nontrivial event is common knowledge and1615$b_1=0$. Right: the product structure $\Omega=T_1\times T_2$ with two types each; $B$ is a 4-cycle and $b_1=1$.}\label{fig:Bgraph}1616\end{figure}1617 1618\begin{example}\label{ex:product-B}1619For the product structure $\Omega=T_1\times T_2$ with $|T_1|=m$, $|T_2|=n$---independent private types with1620full support, the standard setting of auction theory---$B$ is the complete bipartite graph $K_{m,n}$,1621connected with $b_1=(m-1)(n-1)$. If agent~1 is fully informed ($p_1=\id$), every state is a leaf hanging from a cell of1622agent~2, and $B$ is a disjoint union of stars: $b_1=0$.1623\end{example}1624 1625So $\pi_0$ of the homotopy colimit is common knowledge, and there is a $\pi_1$ about which the classical1626theory of knowledge is silent. That silence is justified: \cref{prop:S5} shows that knowledge operators1627factor through $\Sub$, and subobjects cannot detect loops. The loops become visible as soon as one puts1628something over $B$ that can have monodromy. Probabilistic beliefs are such a thing, and \cref{ch:belief}1629shows that the first cohomology of $B$ is exactly the obstruction to a common prior.1630 1631\section{Many agents: simplicial models}1632 1633For $n$ agents there is a second geometric object in the literature, coming from distributed computing.1634 1635\begin{definition}\Sli[\cite{GLR21,HKR13}]1636The \term{simplicial model} of an information structure is the simplicial complex $\mathcal{C}$ with vertex1637set $\coprod_iT_i$---a vertex is a pair (agent, local state), ``coloured'' by its agent---in which each state1638$\omega$ spans the $(n-1)$-simplex $\{p_1(\omega),\dots,p_n(\omega)\}$.