Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1521–1620 of 6559. Source text is displayed literally.
1521coarsening. 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\}$};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}$,