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

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 is2121guaranteed by the parity argument that underlies Sperner's lemma, hence Brouwer. The complexity result is2122the quantitative form of the logical one: the only general reason an equilibrium exists is topological, and2123topology does not come with an algorithm.2124 2125\section{The equilibrium correspondence}\label{sec:KM}2126 2127Fix the players and action sets and let the payoffs vary. The space of games is then a Euclidean space2128$\mathcal{U}=\R^{N\times A}$, and the object of interest is the \term{graph of the equilibrium correspondence}2129\[ \mathcal{E}=\{(u,\sigma)\in\mathcal{U}\times\Sigma\st\sigma\text{ is a mixed equilibrium of }u\}, \]2130with its projection $\mathrm{pr}\colon\mathcal{E}\to\mathcal{U}$. The fibre of $\mathrm{pr}$ over a game is2131its set of equilibria.2132 2133\begin{theorem}[Structure theorem]\label{thm:KM}\Scl[\cite{KM86}]2134There is a homeomorphism $h\colon\mathcal{E}\to\mathcal{U}$ such that $\mathrm{pr}\circ h^{-1}$ is homotopic2135to the identity by a homotopy that extends to the one-point compactification. In particular2136$\mathrm{pr}$ is a proper map of degree $+1$.2137\end{theorem}2138 2139The total space of equilibria is as simple as possible---a Euclidean space, lying over the space of games2140with degree one, like a sheet of paper that has been folded but not torn. All of the following are2141consequences of this one statement.2142 2143\begin{itemize}2144\item \emph{Existence.} A map of degree one is surjective. This is Nash's theorem.2145\item \emph{Oddness.} Over a regular value the fibre is finite, and its points, counted with the sign of2146  the local degree, sum to $+1$. Hence generic games have an odd number of equilibria \cite{Wil71,Har73b}.2147\item \emph{Index.} The local degree at an isolated equilibrium, or more generally on a connected2148  component of the fibre, is its \term{index}; indices sum to $+1$ over every game. A component of nonzero2149  index cannot disappear under small perturbations of the payoffs: it is \emph{essential}.2150\end{itemize}2151 2152\begin{example}\label{ex:index}2153The ranked coordination game of \cref{ex:three} has three equilibria: the two pure ones, each of index2154$+1$, and the mixed one, of index $-1$; and $1+1-1=1$. The mixed equilibrium is the fold in the paper.2155Perturb the payoffs until the game has a dominant action, and the mixed equilibrium and one pure2156equilibrium approach each other, merge, and vanish, leaving a single equilibrium of index $+1$. Indices2157are computed numerically for this game in \cref{app:computations}.2158\end{example}2159 2160What the structure theorem does not give is as important.2161 2162\begin{proposition}[No continuous selection]\label{prop:noselection}\Sob2163There is no continuous map $s\colon\mathcal{U}\to\Sigma$ with $s(u)$ an equilibrium of $u$ for all $u$, as soon2164as some player has two actions.2165\end{proposition}2166 2167\begin{proof}2168Restrict to a one-parameter family of one-player games with two actions and payoffs $(t,0)$. For $t>0$ the2169unique equilibrium is the first action, for $t<0$ the second. A selection has no limit at $t=0$.2170\end{proof}2171 2172So $\mathrm{pr}$ has degree one and no section. The equilibrium correspondence is upper but not lower2173hemicontinuous; its fibres change homotopy type from point to point. They can be arbitrarily complicated:2174by a theorem of Datta \cite{Dat03}, every real algebraic variety is isomorphic to the set of totally mixed2175equilibria of some three-player game. The situation is summarized by saying that $\mathrm{pr}$ is as far2176from a fibration as a degree-one map of Euclidean spaces can be.2177 2178\begin{remark}[Existence is a truncated statement]\label{rem:truncated}\Spg2179In a type theory whose functions are continuous, \cref{thm:nash} and \cref{prop:noselection} together say2180that the type $\prod_{u}\bigl\|\sum_\sigma\mathsf{isNash}(u,\sigma)\bigr\|$ is inhabited while