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

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}$.1919\end{proof}1920 1921Unwinding the vanishing of a class on a graph gives a condition on cycles: \emph{around every cycle of $B$,1922the alternating product of posterior probabilities is $1$}. These are the cycle equations of Rodrigues-Neto1923\cite{RN09}. Part (c) recovers the theorem of Hellman and Samet \cite{HeSa12}, who call a partition profile1924\emph{tight} when every posterior profile has a common prior, and characterize tightness (for a connected1925structure) by the count $\sum_i|T_i|=(n-1)|\Omega|+1$. By \cref{prop:hocolim} this count is the equation1926$b_1(B)=0$: \emph{tight means that the homotopy colimit of the type maps is contractible on each component}.1927 1928\begin{example}\label{ex:cycle}1929In the product structure with two types each (\cref{fig:Bgraph}, right), write the states as1930$a=(s,t)$, $b=(s,t')$, $c=(s',t)$, $d=(s',t')$. Agent~1's posteriors give the ratios $\mu(b)/\mu(a)$ and1931$\mu(d)/\mu(c)$; agent~2's give $\mu(c)/\mu(a)$ and $\mu(d)/\mu(b)$. Four numbers are prescribed and a prior1932has three degrees of freedom; the single cycle equation is1933\[ \frac{\beta_1(s)(b)}{\beta_1(s)(a)}\cdot\frac{\beta_2(t')(d)}{\beta_2(t')(b)}\cdot1934   \frac{\beta_1(s')(c)}{\beta_1(s')(d)}\cdot\frac{\beta_2(t)(a)}{\beta_2(t)(c)}=1. \]1935Generic posteriors violate it. In the structure on the left of the figure there is no cycle and every1936posterior profile comes from a prior.1937\end{example}1938 1939The picture is that of a connection. The posteriors tell each agent how to transport relative probability1940between two states she cannot distinguish; composing along a path in $B$ transports it between any two1941states of a component; a common prior exists when transport is path-independent, that is, when the1942connection is flat with trivial holonomy. Nontrivial holonomy around a cycle means that the agents'1943relative odds, chained around the cycle, multiply to something other than $1$---which is exactly an1944arbitrage opportunity for an outsider, or a mutually agreeable bet for the insiders.1945 1946\begin{theorem}[No-betting characterization]\label{thm:nobet}\Scl[\cite{Mor94,Sam98,Fei00}]1947A finite posterior profile on a connected information structure has a common prior if and only if there is no \emph{agreeable bet}: no family of1948functions $f_i\colon\Omega\to\R$ with $\sum_if_i=0$ such that every type of every agent assigns strictly1949positive expected value to her own $f_i$.1950\end{theorem}1951 1952The classical proofs are separation arguments. Read through \cref{thm:H1}, the theorem is the familiar1953duality between potentials and circulations: either the log-odds are a gradient, or some cycle carries a1954profitable flow.1955 1956\section{Agreement}1957 1958\begin{theorem}[Agreeing to disagree]\label{thm:agree}\Scl[\cite{Aum76}]1959Let $\mu$ be a common prior, $E$ an event, and $f_i(\omega)=\mu\bigl(E\mid p_i^{-1}p_i(\omega)\bigr)$ agent $i$'s1960posterior probability of $E$. If at some state of positive probability it is common knowledge that1961$f_i=a_i$ for each $i$, then all the $a_i$ are equal.1962\end{theorem}1963 1964\begin{proof}1965For a map $p\colon\Omega\to T$ write $\E_p\colon\R^\Omega\to\R^T$ for conditional expectation with respect to $\mu$.1966Conditional expectation is functorial for composition of maps (the tower property): if1967$r\colon T\to T'$ then $\E_{rp}=\E_r\E_p$. Apply this to the two factorizations $q=r_ip_i$ of the map to the1968pushout in \cref{thm:aumann-ck}. Common knowledge of $f_i=a_i$ at $\omega$ means that $\E_{p_i}1_E$ is1969constant, equal to $a_i$, on the fibre of $r_i$ over $m=q(\omega)$. Hence1970$(\E_q1_E)(m)=(\E_{r_i}\E_{p_i}1_E)(m)=a_i$ for every $i$.1971\end{proof}1972 1973The proof uses two things and only two: the pushout square of the type maps, and the fact that a single1974measure is being pushed around it. If the posteriors descend to the pushout, they are both equal to the1975pushed-forward measure there. Without a common prior there is nothing to push, and \cref{thm:H1,thm:nobet}1976say precisely how disagreement can then be sustained. Two classical corollaries: agents who announce their1977posteriors back and forth must converge to agreement \cite{GP82}; and rational traders who begin from an1978efficient allocation cannot come to trade on private information alone, since common knowledge of