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

2099$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 while2181$\prod_u\sum_\sigma\mathsf{isNash}(u,\sigma)$ is not: equilibria merely exist. This is more than a manner of2182speaking. It locates the problem of \emph{equilibrium selection} exactly: a selection is an untruncation,2183and by \cref{prop:equivariance} and \cref{prop:noselection} it must be both equivariant and discontinuous. It also2184suggests what a refinement should be. An index, or the property of lying on an essential component, is2185a function on $\mathcal{E}$ that is locally constant where it should be and invariant under the homeomorphism2186$h$. The programme of characterizing refinements by such invariants was begun by Kohlberg and Mertens and2187carried furthest by Govindan and Wilson \cite{GW05}; whether it can be phrased as the study of2188\emph{homotopy-invariant} functions on the map $\mathrm{pr}$, in a precise $\infty$-categorical sense, is2189taken up in \cref{ch:coda}.2190\end{remark}2191 2192\section{Correlation}\label{sec:correlated}2193 2194The mixed extension passes through the map $\nabla\colon\prod_i\Dist A_i\to\Dist(\prod_iA_i)$, which is not2195surjective. Suppose we do not apply it.2196 2197\begin{definition}\Scl[\cite{Aum74}]2198A \term{correlated equilibrium} of $G$ is a distribution $\pi\in\Dist(A)$ such that for every player $i$ and