Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1939–2038 of 6559. Source text is displayed literally.
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 of1979willingness to trade is common knowledge of disagreement \cite{MS82}. Every theory of speculative1980trade has to break one of the hypotheses, and most break the common prior.1981 1982\section*{Notes}1983 1984The monad of probability measures is due to Giry \cite{Gir82}, following Lawvere; Markov categories were1985introduced under that name by Fritz \cite{Fri20}, building on \cite{CJ19}. Games with incomplete information are1986Harsanyi's \cite{Har67}. The universal type space was constructed by Mertens and Zamir \cite{MZ85} and by1987Brandenburger and Dekel \cite{BD93}; the measure-theoretic construction, and the notion of type morphism,1988are due to Heifetz and Samet \cite{HeSa98}, and the identification with a terminal coalgebra to Moss and1989Viglizzo \cite{MV06}. An early domain-theoretic treatment is \cite{Vas92}. The role of the common prior was1990analysed by Aumann \cite{Aum87}; the characterization of its existence by the absence of agreeable bets is1991due to Morris \cite{Mor94}, Samet \cite{Sam98} and Feinberg \cite{Fei00}; the cycle equations are from1992\cite{RN09} and the genericity analysis from \cite{HeSa12}. The cohomological packaging of \cref{thm:H1}1993is, as far as we know, not in the literature in this form, but every ingredient is.1994 1995\section*{Exercises}1996 1997\begin{exercise}1998In \cref{ex:contribution}, let costs be uniform on $[0,\bar c]$ with $\bar c>1$. Find the symmetric cutoff1999equilibrium and the probability that the good is provided as $\bar c\to\infty$ and as $\bar c\to1$.2000\end{exercise}2001\begin{exercise}2002Show that a type morphism between finite type spaces preserves first- and second-order beliefs, and deduce2003by induction that it preserves hierarchies.2004\end{exercise}2005\begin{exercise}2006Verify the claims of \cref{ex:redundant}, and exhibit explicitly the unique type morphism from $\mathbb{B}$2007to $\mathbb{A}$.2008\end{exercise}2009\begin{exercise}2010For three agents and the information structure of the last exercise of \cref{ch:knowledge}, write down the2011cycle equation and interpret it.2012\end{exercise}2013\begin{exercise}2014In the setting of \cref{ex:cycle}, suppose the cycle equation fails. Construct an agreeable bet2015explicitly, and check that its existence contradicts the existence of a common prior.2016\end{exercise}2017\begin{exercise}2018Prove the tower property $\E_{rp}=\E_r\E_p$ on a finite probability space directly, and identify $\E_p$ with2019composition with the Bayesian inverse $p^\dagger_\mu$.2020\end{exercise}2021%% ---- end ch/05-belief.tex ----2022%% ---- begin ch/06-mixing.tex ----2023\chapter{Mixing and Existence}\label{ch:mixing}2024 2025Matching pennies has no equilibrium in the sense of \cref{def:nash}. The classical remedy is to let players2026randomize, and Nash's theorem then guarantees an equilibrium in every finite game. This chapter presents2027the mixed extension as a free construction, Nash's theorem as a statement about the degree of a map, and2028correlated equilibrium as what one obtains by declining to apply a certain non-invertible natural2029transformation.2030 2031\section{The mixed extension is free}2032 2033\begin{definition}2034A \term{convex space} is an algebra for the monad $\Dist$: a set $C$ with a map $\Dist C\to C$ assigning to2035each finite formal mixture of points a point, compatibly with units and with mixtures of mixtures. A map2036of convex spaces is \term{affine}. The free convex space on a set $X$ is $\Dist X$ itself.2037\end{definition}2038