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

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)\}$.1639\end{definition}1640 1641Two states are indistinguishable to agent $i$ exactly when their simplices share the $i$-coloured vertex,1642and indistinguishable to every member of a coalition $J$ when they share a $J$-coloured face. Goubault,1643Ledent and Rajsbaum \cite{GLR21} show that such complexes correspond to (proper) Kripke models of1644multi-agent S5, and that standard communication protocols act on them by subdivision. The topology1645matters: in the theory of distributed computing \cite{HKR13} a task is solvable only if a certain map of1646complexes exists, and the obstructions are higher connectivity conditions---the impossibility of1647wait-free consensus is the statement that a protocol complex is connected and so cannot be mapped1648compatibly onto a disconnected output complex.1649 1650The graph $B$ and the complex $\mathcal{C}$ are related by a map $B\to\mathcal{C}$ sending each1651state-vertex to the barycentre of its simplex, and they have the same $\pi_0$. They do not have the same1652$\pi_1$. Take three agents and two states that agents~1 and~2 cannot distinguish and agent~3 can: $\mathcal{C}$1653is two triangles glued along an edge, which is contractible, whereas $B$ has a cycle. Both are legitimate1654invariants: $B$ is the homotopy colimit of the type maps and controls gluing problems for data attached to1655individual agents; $\mathcal{C}$ additionally fills in what coalitions distributedly know. Which higher1656invariants of $\mathcal{C}$ are game-theoretically meaningful is, as far as we know, open1657(\cref{ch:coda}).1658 1659\section{Knowledge and time}1660 1661In an extensive game with perfect recall, each player's information refines as play proceeds: by1662\cref{prop:recall} her information sets form a forest, and the map from plays to her information at her1663$n$-th move is a tower of quotients $\Omega\to\cdots\to T_i^{(n+1)}\to T_i^{(n)}$---classically, a filtration. Each stage has its own1664knowledge operator $\K_i^{(n)}$ and these increase with $n$. The object underlying the tower is a1665presheaf on $\omega$, that is, an information structure \emph{in the topos of trees}; the internal1666knowledge modality of that topos packages all the $\K_i^{(n)}$ at once. We shall not need this internal1667formulation in detail, but it explains why the temporal modality of \cref{ch:perfection,ch:repetition} and1668the epistemic modality of this chapter have the same algebraic form: both are $p^*\forall_p$ for a suitable1669map $p$.1670 1671\section*{Notes}1672 1673The partition model and the characterization of common knowledge by the meet are due to Aumann1674\cite{Aum76}; the notion itself is usually credited to Lewis. The fixed-point formulation is standard in1675epistemic logic. Quantifiers as adjoints are due to Lawvere; the systematic reading of modal operators as1676base-change (co)monads in dependent type theory is expounded in \cite{Cor20}, and modalities in homotopy type1677theory are studied in \cite{RSS20}. The identification of the homotopy colimit of a diagram of sets with1678the nerve of its category of elements is a special case of Thomason's theorem \cite{Tho79}. Simplicial