Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 1981–2080 of 6559. Source text is displayed literally.
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 2039\begin{theorem}[Expected utility]\label{thm:vnm}\Scl[\cite{vNM44}]2040Let $\succsim$ be a complete, transitive relation on $\Dist X$, with $X$ finite, satisfying independence and2041continuity. Then there is an affine map $U\colon\Dist X\to\R$ representing $\succsim$, and $U$ is unique up to2042composition with a map $x\mapsto\alpha x+\beta$, $\alpha>0$.2043\end{theorem}2044 2045The categorical reading is short. An affine map out of a free algebra is determined by its restriction to2046generators, so $U$ \emph{is} a function $u\colon X\to\R$, extended by expectation. The uniqueness clause says that the2047freedom in $U$ is the group of automorphisms of $\R$ as an ordered convex space, which is the group of2048positive affine maps. That is where the preference equivalence of \cref{def:equivalences} comes from: a2049point of $\NFG_{\succsim}$ carries, for each player, an order-and-convexity structure on lotteries, and2050utility functions are its coordinate charts.2051 2052\begin{definition}2053The \term{mixed extension} of $G=(N,A,u)$ is the game with strategy sets $\Dist A_i$ and payoffs2054\[ \prod_i\Dist A_i\xrightarrow{\ \nabla\ }\Dist\Bigl(\prod_iA_i\Bigr)\xrightarrow{\ \overline{u}_i\ }\R, \]2055where $\nabla$ forms the product distribution and $\overline{u}_i$ is the affine extension of $u_i$. A2056\term{mixed equilibrium} of $G$ is a Nash equilibrium of its mixed extension.2057\end{definition}2058 2059The payoff is affine in each player's own strategy separately. Consequently a mixed strategy is a best response iff2060every pure strategy in its support is, and all of those earn the same payoff. This \emph{indifference2061principle} is how mixed equilibria are computed.2062 2063\begin{example}[Three computations]\label{ex:mixed}2064(a) In the Battle of the Sexes of \cref{ex:three}, let the row player choose $O$ with probability $p$ and2065the column player with probability $q$. Column is indifferent when $p=2(1-p)$, row when $2q=1-q$; so2066$p=\tfrac23$, $q=\tfrac13$, and each player's expected payoff is $\tfrac23$, less than at either pure2067equilibrium.2068 2069(b) \emph{Inspection.} An agent complies at cost $e$ or cheats; an inspector inspects at cost $c$ or does2070not. A cheater who is inspected pays a fine $F>e$, and the inspector gains $b>c$ from catching one. There is2071no pure equilibrium. The inspector is indifferent when the probability of cheating is $\gamma=c/b$; the2072agent is indifferent when the probability of inspection is $\iota=e/F$. Raising the fine leaves the2073frequency of cheating unchanged and lowers the frequency of inspection: in a mixed equilibrium each2074player's behaviour is pinned down by the \emph{other's} payoffs.2075 2076(c) \emph{Volunteering} \cite{Die85}. Each of $n$ bystanders may act at cost $c$; if anyone acts all receive2077$b>c$. In the symmetric mixed equilibrium each abstains with probability $r$ where2078$b-c=b(1-r^{n-1})$, so $r=(c/b)^{1/(n-1)}$, and the probability that no one acts is $(c/b)^{n/(n-1)}$,2079which \emph{increases} with $n$ towards $c/b$.2080\end{example}