Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2141–2240 of 6559. Source text is displayed literally.
2141consequences 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.2221 2222\begin{example}\label{ex:chicken}2223In the Battle of the Sexes, a public coin flip choosing between $(O,O)$ and $(F,F)$ is a correlated2224equilibrium worth $\tfrac32$ to each player, against $\tfrac23$ in the mixed equilibrium. It lies in the2225convex hull of the Nash equilibria. Aumann's example \cite{Aum74} shows that correlated equilibria can2226leave that hull: with payoffs2227\[2228\begin{array}{c|cc}2229 & C & D\\\hline2230C & 6,6 & 2,7\\2231D & 7,2 & 0,02232\end{array}2233\]2234the distribution putting weight $\tfrac13$ on each of $(C,C)$, $(C,D)$, $(D,C)$ is a correlated equilibrium2235worth $5$ to each player, which no mixture of Nash equilibria achieves.2236\end{example}2237 2238A correlated equilibrium is also a Bayesian Nash equilibrium of a game of incomplete information in which2239the types are payoff-irrelevant signals with a common prior---exactly the redundant types of2240\cref{ex:redundant}. Aumann's theorem \cite{Aum87} that correlated equilibrium \emph{is} the expression of