Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1701–1800 of 6559. Source text is displayed literally.
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 a1739 prior $\pi\colon I\to X$, characterized by the equality of the two ways of forming the joint distribution1740 on $X\otimes Y$, and unique $\pi f$-almost surely;1741\item \term{conditional expectation} along a deterministic $p\colon\Omega\to T$, which for a prior $\mu$ is1742 integration against the Bayesian inverse $p^\dagger_\mu$.1743\end{itemize}1744Bayesian inversion is contravariantly functorial, $(g\circ f)^\dagger=f^\dagger\circ g^\dagger$ with the1745evident priors. A kernel together with its inverse is therefore a lens-like object---forward prediction,1746backward inference---and the compositional theory of such \emph{Bayesian lenses} \cite{BHS23} is what makes1747the Bayesian open games of \cref{sec:optics} work.1748 1749\section{Games with incomplete information}1750 1751Suppose the players do not know the game: payoffs depend on a state of nature $\theta\in\Theta$ about which1752they have different information. Harsanyi's proposal \cite{Har67} was to model each player's information1753by a \emph{type} and to let the uncertainty be resolved by a move of Nature.1754 1755\begin{definition}\label{def:bayesian-game}1756A \term{Bayesian game} consists of players $N$, a set $\Theta$ of states of nature, type sets $T_i$, action1757sets $A_i$, payoff functions $u_i\colon A\times\Theta\to\R$, and \emph{beliefs}1758$\beta_i\colon T_i\to\Dist(\Theta\times T_{-i})$. A strategy of player $i$ is a function $s_i\colon T_i\to A_i$.1759The profile $s$ is a \term{Bayesian Nash equilibrium} if for every $i$ and every $t_i$ the action $s_i(t_i)$1760maximizes the interim expected payoff1761\[ \E_{(\theta,t_{-i})\sim\beta_i(t_i)}\,u_i\bigl(a_i,s_{-i}(t_{-i}),\theta\bigr). \]1762The game has a \term{common prior} if there is $\pi\in\Dist(\Theta\times T)$ whose conditionals are the1763$\beta_i$.1764\end{definition}1765 1766With a common prior the Bayesian game is the extensive game in which Nature first draws $(\theta,t)$ from1767$\pi$ and each player observes her own coordinate $t_i$. Information is \emph{incomplete} in the taxonomy of1768\cref{ch:extensive}, and its incompleteness has been converted into \emph{asymmetry} about a move of Nature.1769In the language of the earlier chapters, a Bayesian game is a family $(G_\theta)$ of strategic-form games1770indexed by the states, together with an information structure $\Omega=\Theta\times T$,1771$p_i\colon\Omega\to T_i$; the Harsanyi transformation is the dependent sum $\sum_\theta G_\theta$, and the1772requirement that $s_i$ be a function of $t_i$ is the factorization through $p_i$ that defines not knowing. A1773strategy is a section over $T_i$, so $S_i=\prod_{t_i}A_i$, and when every type has positive probability the1774Bayesian equilibria are the Nash equilibria of the strategic form with these strategy sets---or equally of1775the \emph{agent form} in which each type is a separate player.1776 1777\begin{example}[A contribution game]\label{ex:contribution}1778Two players simultaneously decide whether to contribute to a public good. The good is provided if at1779least one contributes and is then worth $1$ to each. Player $i$'s cost of contributing, $c_i$, is her private1780type, drawn independently and uniformly from $[0,2]$. Look for an equilibrium in cutoff strategies:1781contribute iff $c_i\le c^*$. If the other player uses the cutoff $c^*$ she contributes with probability1782$c^*/2$. Contributing yields $1-c_i$; not contributing yields $c^*/2$. So player $i$ contributes iff1783$c_i\le1-c^*/2$, and consistency requires $c^*=1-c^*/2$, that is $c^*=\tfrac23$. The good is provided with1784probability $1-(\tfrac23)^2=\tfrac59$, although it would be efficient to provide it whenever1785$\min(c_1,c_2)<2$, which is almost always. Each player free-rides on the possibility that the other is a low-cost type.1786\end{example}1787 1788\section{Types as a terminal coalgebra}1789 1790The definition of a Bayesian game is circular in a way that troubled its first readers: a type is1791something that determines a belief about, among other things, the other players' types. Harsanyi cut the1792circle by fiat, taking the $T_i$ as primitive. The alternative is to unfold it. Player $i$ has a belief1793about $\Theta$; a belief about $\Theta$ and $j$'s belief about $\Theta$; and so on---a \emph{hierarchy}. Is1794every hierarchy a type? Is there a space containing them all?1795 1796\begin{definition}1797Fix a measurable space $\Theta$ and, for definiteness, two players. A \term{type space} is a coalgebra for1798the endofunctor1799\[ F(X_1,X_2)=\bigl(\Giry(\Theta\times X_2),\ \Giry(\Theta\times X_1)\bigr) \]1800of $\Meas\times\Meas$: a pair of measurable spaces with measurable maps $\beta_i\colon T_i\to\Giry(\Theta\times T_{-i})$.