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

2121guaranteed 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$ and2199every pair of actions $a_i,a_i'$,2200\[ \sum_{a_{-i}}\pi(a_i,a_{-i})\bigl[u_i(a_i,a_{-i})-u_i(a_i',a_{-i})\bigr]\ \ge\ 0. \]2201\end{definition}2202 2203The interpretation is a mediator who draws a profile from $\pi$ and privately recommends to each player2204her coordinate; the inequalities say that obeying is optimal given what the recommendation reveals.2205 2206\begin{proposition}\label{prop:CE}\Scl[\cite{Aum74,Aum87}; geometry as in \cite{NGH04}]2207The set $\CE(G)$ is a nonempty convex polytope in $\Dist(A)$, defined by linear inequalities, and2208well defined on $\NFG_{\mathrm{inc}}$. The mixed equilibria of $G$ are2209\[ \NE(G)=\CE(G)\ \cap\ \nabla\Bigl(\prod_i\Dist A_i\Bigr), \]2210the intersection of the polytope with the variety of product distributions (the Segre variety of rank-one2211tensors).2212\end{proposition}2213 2214The two halves of the right-hand side divide the difficulty of the subject. The polytope is linear2215programming: a correlated equilibrium can be computed in polynomial time, and the set is a convex body2216with a centre, extreme points and a geometry one can reason about. The Segre variety is where the2217nonlinearity, the multiplicity, the non-convexity of the Nash set and the PPAD-hardness all come from.2218Categorically, $\nabla$ is the structure map that makes $\Dist$ a \emph{monoidal} monad; it would be an2219isomorphism if $\Dist$ preserved products, and it is not. Independence is not a property that a joint2220distribution has for free. Nash equilibrium imposes it; correlated equilibrium does not.