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

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 of2241common knowledge of rationality under a common prior is the same observation read in the other direction,2242and its generalization to genuine incomplete information is the \emph{Bayes correlated equilibrium} of2243Bergemann and Morris \cite{BM16}, which reappears in \cref{ch:signalling} as the set of outcomes an2244information designer can induce.2245 2246\section{Continuous games}2247 2248Much of economics uses games with continuous action sets. If each $A_i$ is a compact convex subset of a2249Euclidean space and each $u_i$ is continuous, and quasi-concave in $a_i$, then a pure equilibrium exists:2250best responses are convex-valued with closed graph, and Kakutani's theorem applies (Debreu, Glicksberg,2251Fan). Without quasi-concavity one needs mixed strategies over a continuum, and existence follows from2252Glicksberg's infinite-dimensional version. Discontinuous payoffs---ubiquitous in price competition, where a2253slightly lower price captures the market---require a separate theory \cite{DM86}; we will meet both the2254phenomenon and its cure in \cref{ch:perfection,ch:pricing}.2255 2256A continuous-time example shows mixing over a continuum. In the \term{war of attrition} two players2257compete for a prize $v$ by waiting; waiting costs $1$ per unit time to each, and the first to quit loses.2258In the symmetric equilibrium each player quits at a constant hazard rate $1/v$: over a short interval2259$dt$ the cost of waiting, $dt$, is balanced by the chance $dt/v$ that the opponent quits and yields $v$.2260Expected payoffs are zero. The prize is entirely dissipated by the contest for it, a theme that returns2261with rent-seeking and with signalling.2262 2263\section*{Notes}2264 2265Convex spaces as algebras of the distribution monad go back to Stone and \'{S}wirszcz; see \cite{Fri20} for2266references. Nash's two proofs are \cite{Nas50a,Nas51}. The structure theorem is due to Kohlberg and Mertens2267\cite{KM86}; generic oddness to Wilson \cite{Wil71} and Harsanyi \cite{Har73b}; the theory of index and2268essential components, and its equivalence with degree, to Govindan and Wilson (see \cite{GW05} and its2269references). The connection between dynamic stability and index is \cite{DR03}. The complexity of2270equilibrium is \cite{DGP09,CDT09}. Correlated equilibrium was introduced in \cite{Aum74}; \cite{NGH04}2271studies the position of the Nash set in the correlated polytope. Purification is from \cite{Har73}. The2272inspection game's comparative statics are sometimes called the ``Robinson Crusoe fallacy''; the2273volunteer's dilemma is \cite{Die85}; the war of attrition originates in evolutionary biology2274(\cref{ch:repetition}).2275 2276\section*{Exercises}2277 2278\begin{exercise}2279Verify that the fixed points of the map $f$ in the proof of \cref{thm:nash} are exactly the mixed2280equilibria. Why can the gain $g_{a_i}$ not be positive for every $a_i$ in the support of $\sigma_i$?2281\end{exercise}2282\begin{exercise}2283Find all mixed equilibria of the ranked coordination game of \cref{ex:three}, and determine for which2284payoff perturbations of the form $u_1(b,b)\mapsto1+t$ the mixed equilibrium survives.2285\end{exercise}2286\begin{exercise}2287Show that the set of correlated equilibria of the Prisoner's Dilemma is a single point, and that in any2288game an action that is strictly dominated receives zero probability in every correlated equilibrium.2289\end{exercise}2290\begin{exercise}2291For the $2\times2$ game of \cref{ex:chicken}, compute the polytope of correlated equilibria that are2292symmetric under exchange of the players, and find the one maximizing the sum of payoffs.2293\end{exercise}2294\begin{exercise}2295In the volunteer's dilemma, suppose the $n$ players can use a public correlating device. Describe a2296correlated equilibrium in which the good is always provided. Is it invariant under $\Aut(G)$? Find the2297best invariant correlated equilibrium.2298\end{exercise}2299\begin{exercise}2300Show that $\nabla\colon\Dist X\times\Dist Y\to\Dist(X\times Y)$ is injective, natural in $X$ and $Y$, and