Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1759–1858 of 6559. Source text is displayed literally.
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})$.1801A \term{type morphism} is a coalgebra homomorphism: a pair of measurable maps $h_i\colon T_i\to T_i'$ with1802$\beta'_i\circ h_i=\Giry(\id_\Theta\times h_{-i})\circ\beta_i$.1803\end{definition}1804 1805A type morphism is a map that preserves beliefs, including beliefs about beliefs, to all orders; this is1806the notion of morphism of Mertens--Zamir and Heifetz--Samet, and the coalgebraic formulation is due to Moss1807and Viglizzo.1808 1809\begin{theorem}[Universal type space]\label{thm:universal}\Scl[\cite{MZ85,BD93,HeSa98}; coalgebraic form \cite{MV06}]1810The category of type spaces over $\Theta$ has a terminal object $T^*$. By Lambek's lemma its structure map1811is an isomorphism:1812\[ T^*_i\;\iso\;\Giry\bigl(\Theta\times T^*_{-i}\bigr). \]1813When $\Theta$ is Polish (or compact Hausdorff, with regular measures), $T^*$ is the limit of the terminal1814sequence1815\[ 1\longleftarrow F1\longleftarrow F^21\longleftarrow\cdots, \]1816whose $n$-th term is the space of belief hierarchies of depth $n$ and whose limit is the space of coherent1817hierarchies.1818\end{theorem}1819 1820The isomorphism is the non-circular form of Harsanyi's idea: a universal type \emph{is} a belief about1821nature and the other's universal type. Terminality says that every type in every type space has a unique1822image in $T^*$, namely its hierarchy; two types, possibly in different type spaces, with the same image are1823\term{behaviourally equivalent} (bisimilar). The construction by the terminal sequence works when1824$F$ preserves the limit of that sequence, and this is exactly the Kolmogorov extension theorem: a1825compatible family of finite-depth beliefs extends uniquely to a belief on the limit. In the bare measurable1826category the extension theorem fails, there are coherent hierarchies that are not types \cite{HeSa99}, and1827the terminal coalgebra---which still exists \cite{HeSa98,MV06}---must be built otherwise. The analytic1828subtleties of the universal type space are thus the subtleties of when a functor is $\omega^{\op}$-continuous.1829 1830\subsection*{The price of universality}1831 1832Why should a universal space exist at all? For non-probabilistic belief it does not.1833 1834\begin{proposition}\label{prop:no-universal-possibility}\Scl[Cantor, Lambek; cf.\ \cite{BK06,AZ15}]1835There is no terminal coalgebra for the functor $X\mapsto\Pow(\Theta\times X)$ on $\Set$, for nonempty $\Theta$.1836\end{proposition}1837 1838\begin{proof}1839By Lambek's lemma a terminal coalgebra would be a set $X$ with $X\iso\Pow(\Theta\times X)$, contradicting1840Cantor's theorem.1841\end{proof}1842 1843A ``possibility type'' is a set of pairs (state, type of the other) that the player does not exclude, and1844the proposition says that there is no space of all possibility types: some conceivable belief about the1845other player is always missing. Brandenburger and Keisler \cite{BK06} sharpened this into an impossibility1846theorem with the shape of a paradox---\emph{Ann believes that Bob assumes that Ann believes that Bob's1847assumption is wrong}---and Abramsky and Zvesper \cite{AZ15} showed that it is an instance of Lawvere's1848fixed-point theorem \cite{Law69}, the common core of the diagonal arguments of Cantor, Russell, G\"odel and1849Tarski. Probabilistic beliefs escape because $\Giry$ is a small functor: a probability measure on a Polish1850space is determined by countably much data. So do possibility models with enough topology to tame the1851powerset \cite{MMP05}. Universality is bought by restricting what counts as a belief, and the restriction1852is not innocent: it is where the continuity hypotheses of the theory come from, and \cref{ch:dynamic}1853shows that strategic behaviour is \emph{not} continuous in the topology that makes the universal type space work.1854 1855\subsection*{Redundant types and invariance}1856 1857Terminality suggests an invariance principle in the style of \cref{prin:invariance}: a solution concept for1858Bayesian games should depend on a type only through its image in $T^*$. Bayesian Nash equilibrium does not.