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

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.1859 1860\begin{example}[A redundant type space]\label{ex:redundant}1861Let $\theta\in\{0,1\}$ be equally likely. Each of two players chooses \emph{bet} or \emph{pass}. If both bet,1862each receives $+1$ when $\theta=1$ and $-2$ when $\theta=0$; otherwise both receive $0$. In the type space $\mathbb{A}$1863each player has a single type, with the prior belief. In the type space $\mathbb{B}$ each player has a type1864$t_i\in\{+,-\}$; the pair $(t_1,t_2)$ is uniform and $\theta=1$ exactly when $t_1=t_2$. In $\mathbb{B}$ each1865type believes that $\theta=1$ with probability $\tfrac12$, believes that the other believes this, and so on:1866every type of $\mathbb{B}$ has the same hierarchy as the type of $\mathbb{A}$. In $\mathbb{A}$ there is no1867equilibrium in which both bet, since joint betting is worth $-\tfrac12$. In $\mathbb{B}$ the profile ``bet1868iff $t_i=+$'' is an equilibrium: a $+$ type meets a betting opponent exactly when the types agree, hence1869when $\theta=1$, and earns $\tfrac12$.1870\end{example}1871 1872The two type spaces are bisimilar and have different equilibrium outcomes: the types of $\mathbb{B}$ carry1873a payoff-irrelevant correlating signal that the hierarchies do not record. As with subgame perfection and1874the Thompson moves, there are two coherent responses. One may enlarge the invariant---record more than the1875hierarchy \cite{EP06,Liu09}---so that $\mathbb{A}$ and $\mathbb{B}$ become different points. Or one may change the solution concept:1876\emph{interim correlated rationalizability} depends only on the hierarchy \cite{DFM07}, and is in this sense1877the solution concept that actually lives on $T^*$.1878 1879\section{The common prior as a gluing problem}\label{sec:commonprior}1880 1881Return to a finite information structure $(\Omega,(p_i))$ as in \cref{def:infostructure}. A1882\term{posterior profile} $\beta$ assigns to each agent $i$ and type $t\in T_i$ a probability distribution1883$\beta_i(t)$ with full support on the cell $p_i^{-1}(t)$. This is what the agents have: beliefs at each1884of their types. A \term{common prior} for $\beta$ is a full-support $\mu\in\Dist\Omega$ whose conditional on each cell1885$p_i^{-1}(t)$ is $\beta_i(t)$. The common prior assumption asserts that one exists, and almost every applied1886model makes it. When is it satisfiable?1887 1888The question is a gluing problem. Each agent's posteriors are a family of ``vertical'' measures along the1889fibres of her type map; the $n$ families overlap at the states; we ask for a single measure on $\Omega$1890inducing them all. Gluing problems have cocycles. Recall the knowledge graph $B$ of \cref{def:B}, with an1891edge $e_{\omega,i}$ from the type $p_i(\omega)$ to the state $\omega$.1892 1893\begin{theorem}[Common priors and $H^1$]\label{thm:H1}\Srf[\cite{RN09,HeSa12}]1894Define a real 1-cochain on $B$ by1895\[ \lambda_\beta(e_{\omega,i})=\log\beta_i\bigl(p_i\omega\bigr)(\omega). \]1896\begin{enumerate}[label=(\alph*)]1897\item $\beta$ admits a common prior if and only if the class $[\lambda_\beta]\in H^1(B;\R)$ vanishes.1898\item If it does, the conditional of a common prior on each connected component of $B$---each cell of the1899  meet---is unique; common priors correspond to full-support distributions on $\pi_0(B)$.1900\item Every class in $H^1(B;\R)$ is $[\lambda_\beta]$ for some posterior profile. Hence if $b_1(B)=0$ every1901  posterior profile has a common prior, and if $b_1(B)>0$ those that do form a closed submanifold of1902  codimension $b_1(B)$ in the manifold of posterior profiles; in particular a nowhere dense set.1903\end{enumerate}1904\end{theorem}1905 1906\begin{proof}1907(a) If $\mu$ is a common prior with marginals $m_i(t)=\mu(p_i^{-1}t)$ then $\beta_i(t)(\omega)=\mu(\omega)/m_i(t)$,1908so $\lambda_\beta=\delta\varphi$ for the 0-cochain $\varphi(\omega)=\log\mu(\omega)$, $\varphi(i,t)=\log m_i(t)$.1909Conversely if $\lambda_\beta=\delta\varphi$, put $\mu(\omega)=e^{\varphi(\omega)}$ and $m_i(t)=e^{\varphi(i,t)}$. Then1910$\beta_i(t)(\omega)=\mu(\omega)/m_i(t)$ on each cell; summing over the cell gives $m_i(t)=\mu(p_i^{-1}t)$, so the1911conditionals of $\mu$ (normalized) are the $\beta_i$.1912(b) The potential $\varphi$ is determined up to adding a function constant on each component of $B$, that is,1913$\mu$ is determined up to a positive factor on each component.1914(c) On a graph every 1-cochain is a cocycle. Given a cochain $c$, subtract from the edges at each type vertex1915$(i,t)$ the constant $\log\sum_{\omega\in p_i^{-1}t}e^{c(e_{\omega,i})}$; this changes $c$ by a coboundary and makes it1916$\lambda_\beta$ for a posterior profile. The same computation shows that, in logarithmic coordinates, the1917posterior profiles are a slice transverse to the coboundaries supported on type vertices, so that1918$\beta\mapsto[\lambda_\beta]$ is a submersion onto $H^1(B;\R)\iso\R^{b_1}$.