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

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$ 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 an