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

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}2081 2082What does a mixed strategy mean? Four answers are in circulation: deliberate randomization; a description2083of an opponent's uncertainty about what a player will do; the distribution of pure strategies in a2084population; and Harsanyi's \emph{purification} \cite{Har73}, in which each player has a small private payoff2085shock and plays a pure strategy of her type, the mixture being the shadow of unobserved heterogeneity. The2086last has a structural gloss. In a Markov category with enough structure, every kernel $1\to A_i$ factors as2087a state on a ``noise'' object followed by a deterministic map \cite[\S11]{Fri20}: a mixed action is a pure2088function of something private. Purification is the statement that this factorization can be chosen to be2089an equilibrium of a nearby game of incomplete information.2090 2091\section{Existence}2092 2093\begin{theorem}[Nash]\label{thm:nash}\Scl[\cite{Nas50a,Nas51}]2094Every finite game has a mixed equilibrium.2095\end{theorem}2096 2097\begin{proof}[Proof sketch]2098Let $\Sigma=\prod_i\Dist A_i$, a product of simplices. For $\sigma\in\Sigma$ and $a_i\in A_i$ let2099$g_{a_i}(\sigma)=\max\{0,u_i(a_i,\sigma_{-i})-u_i(\sigma)\}$ be the gain from deviating to $a_i$, and define2100$f\colon\Sigma\to\Sigma$ by2101\[ f(\sigma)_i(a_i)=\frac{\sigma_i(a_i)+g_{a_i}(\sigma)}{1+\sum_{b_i}g_{b_i}(\sigma)}. \]2102$f$ is continuous, so by Brouwer's theorem it has a fixed point, and one checks that the fixed points are2103exactly the points where all gains vanish.2104\end{proof}2105 2106Three remarks place the theorem.2107 2108\emph{It is a topological theorem with no order-theoretic or algebraic proof.} \Cref{ch:order} will prove2109existence by Tarski's theorem for a different class of games; for general finite games one needs Brouwer,2110or its set-valued form due to Kakutani, or an equivalent.2111 2112\emph{It is not constructive.} Brouwer's theorem is not provable in constructive mathematics; what is2113provable is the existence of approximate fixed points. In homotopy type theory the situation is2114instructive: Shulman \cite{Shu18} proves Brouwer's theorem in a \emph{cohesive} extension of the theory, in2115which the topology of the disc is an intrinsic part of the type rather than a structure on a set of2116points, and the fixed point is asserted in propositionally truncated form. One learns that a fixed point2117exists; one is not handed a function that finds it.2118 2119\emph{It is computationally hard.} Finding a mixed equilibrium, even of a two-player game, is complete for2120the complexity class PPAD \cite{DGP09,CDT09}---the class of total search problems whose totality is