Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1639–1738 of 6559. Source text is displayed literally.
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}. Simplicial1679models for epistemic logic are due to Goubault, Ledent and Rajsbaum \cite{GLR21}, building on the1680topological theory of distributed computing \cite{HKR13}. The approximation of common knowledge by common1681$p$-belief, which matters when knowledge is replaced by high-probability belief, is taken up in1682\cref{ch:dynamic}.1683 1684\section*{Exercises}1685 1686\begin{exercise}1687Let $p\colon\Omega\to T$ be a function that is not surjective. Which clauses of \cref{prop:S5} survive?1688\end{exercise}1689\begin{exercise}1690Show directly from the adjunctions that $\K_i\K_j$ need not equal $\K_j\K_i$, and that1691$\CK E\subseteq\K_{i_1}\cdots\K_{i_m}E$ for every finite sequence of agents.1692\end{exercise}1693\begin{exercise}1694For the information structure on the left of \cref{fig:Bgraph}, compute $\K_1E$, $\K_2E$, $\K_1\K_2E$ and1695$\CK E$ for $E=\{a,b,c,d\}$. At which states does everyone know $E$ without $E$ being common knowledge?1696\end{exercise}1697\begin{exercise}1698Verify the formula for $b_1(B)$ in \cref{prop:hocolim} on both graphs of \cref{fig:Bgraph}, and prove1699\cref{ex:product-B}.1700\end{exercise}1701\begin{exercise}1702Prove the claim of \cref{rem:distributed}: distributed knowledge is $p_\vee^*\forall_{p_\vee}$ for the join1703partition. Show that for every event $\CK E\subseteq\K_iE\subseteq D E\subseteq E$, where $D$ denotes1704distributed knowledge.1705\end{exercise}1706\begin{exercise}1707Three agents, two states, with $p_1,p_2$ constant and $p_3$ injective. Draw $B$ and $\mathcal{C}$ and1708compute their fundamental groups.1709\end{exercise}1710%% ---- end ch/04-knowledge.tex ----1711%% ---- begin ch/05-belief.tex ----1712\chapter{Belief}\label{ch:belief}1713 1714Knowledge excludes; belief weighs. This chapter adds probability to the information structures of1715\cref{ch:knowledge} and treats the three classical topics that result: Harsanyi's reduction of games with1716incomplete information to games with imperfect information; the universal space of hierarchies of belief;1717and the common prior assumption with its most famous consequence, the impossibility of agreeing to1718disagree. The categorical tools are a monad, a terminal coalgebra and a cohomology class.1719 1720\section{Probability as a monad}1721 1722For a set $X$ let $\Dist X$ be the set of finitely supported probability distributions on $X$. $\Dist$ is a1723monad on $\Set$: the unit $\eta\colon X\to\Dist X$ sends a point to its Dirac distribution, and the1724multiplication $m\colon\Dist\Dist X\to\Dist X$ averages a distribution over distributions. For measurable1725spaces the same structure is carried by the \term{Giry monad} $\Giry$ on $\Meas$, which sends a space to the1726space of probability measures on it \cite{Gir82}. A map $X\to\Dist Y$ is a \term{stochastic map} or Markov1727kernel; such maps compose by integration, and form the Kleisli category of the monad, which we denote1728$\FinStoch$ on finite sets and $\Stoch$ in general.1729 1730It is often cleaner to axiomatize the Kleisli category directly. A \term{Markov category} \cite{Fri20,CJ19}1731is a symmetric monoidal category in which every object has a \emph{copy} map $X\to X\otimes X$ and a1732\emph{delete} map $X\to I$, compatibly with $\otimes$, such that deletion is natural. A morphism is1733\emph{deterministic} if it commutes with copying. In $\FinStoch$ the deterministic maps are the functions.1734Three notions will be used repeatedly, and all three are expressible in any Markov category with1735conditionals:1736\begin{itemize}1737\item the \term{marginals} of a joint state $I\to X\otimes Y$, obtained by deleting one factor;1738\item the \term{Bayesian inverse} $f^\dagger_\pi\colon Y\to X$ of a kernel $f\colon X\to Y$ with respect to a