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

2301surjective only if $X$ or $Y$ has at most one element.2302\end{exercise}2303%% ---- end ch/06-mixing.tex ----2304%% ---- begin ch/07-order.tex ----2305\chapter{Order}\label{ch:order}2306 2307Nash's theorem needs topology and gives little information about the equilibria it produces. For a large2308and economically central class of games---those in which actions are ordered and a player wants to do more2309when others do more---existence, structure and comparative statics all follow from order alone. This2310chapter is about that class. Categorically it is the decategorified case of everything else in the book:2311categories with at most one arrow between two objects, where the theory of fixed points of functors2312collapses to Tarski's theorem.2313 2314\section{Posets as categories}2315 2316A preorder is a category with at most one morphism between any two objects; equivalently, a category2317enriched in the two-element lattice $\mathbf{2}=\{\bot\le\top\}$. Under this dictionary a monotone map is a2318functor, a Galois connection is an adjunction, a meet is a limit and a join a colimit, and a complete2319lattice is a category that is complete and cocomplete. An algebra for a monotone $f\colon L\to L$ is a2320pre-fixed point $f(x)\le x$, a coalgebra is a post-fixed point $x\le f(x)$, and Lambek's lemma says that an2321initial algebra or a terminal coalgebra is a fixed point.2322 2323\begin{theorem}[Knaster--Tarski]\label{thm:tarski}\Scl[\cite{Tar55}]2324Let $L$ be a complete lattice and $f\colon L\to L$ monotone. Then the set $\Fix(f)$ is a nonempty complete2325lattice. Its least element is $\mu f=\bigwedge\{x\st f(x)\le x\}$, the initial algebra, and its greatest is2326$\nu f=\bigvee\{x\st x\le f(x)\}$, the terminal coalgebra.2327\end{theorem}2328 2329We have already used the theorem twice: rationalizability is $\nu\Phi$ (\cref{thm:rationalizable}) and common2330knowledge is $\nu X.\K(E\cap X)$ (\cref{thm:aumann-ck}). The associated proof rules---\emph{induction}: to show2331$\mu f\le x$ show $f(x)\le x$; \emph{coinduction}: to show $x\le\nu f$ show $x\le f(x)$---are the thin-category2332versions of the universal properties of initial algebras and terminal coalgebras, which in2333\cref{ch:perfection,ch:repetition} will govern finite and infinite horizons.2334 2335\section{Complementarity}2336 2337\begin{definition}2338Let $X$ be a lattice and $T$ a poset. A function $f\colon X\to\R$ is \term{supermodular} if2339$f(x\vee y)+f(x\wedge y)\ge f(x)+f(y)$ for all $x,y$. A function $f\colon X\times T\to\R$ has2340\term{increasing differences} in $(x,t)$ if $f(x',t)-f(x,t)$ is nondecreasing in $t$ whenever $x'\ge x$.2341\end{definition}2342 2343On a product of chains, supermodularity is equivalent to increasing differences in each pair of2344coordinates, and for smooth functions on $\R^k$ to nonnegative cross partial derivatives. Increasing2345differences is a second-order condition: it constrains not how $f$ varies but how the \emph{variation}2346of $f$ in one argument varies with another. It is the discrete form of complementarity.2347 2348\begin{theorem}[Topkis]\label{thm:topkis}\Scl[\cite{Top78,Top98}]2349Let $X$ be a lattice, $T$ a poset, and $f\colon X\times T\to\R$ supermodular in $x$ with increasing2350differences in $(x,t)$. Then $t\mapsto\argmax_xf(x,t)$ is increasing in the strong set order: if $t\le t'$,2351$x\in\argmax f(-,t)$ and $x'\in\argmax f(-,t')$, then $x\wedge x'\in\argmax f(-,t)$ and2352$x\vee x'\in\argmax f(-,t')$. In particular the greatest and least maximizers, when they exist, are2353monotone in $t$.2354\end{theorem}2355 2356The theorem makes no use of concavity, differentiability, convexity of $X$, or uniqueness of the2357maximizer. It converts a hypothesis about the objective directly into a conclusion about the selection2358function $\argmax$: under complementarity, $\argmax$ is a \emph{monotone} selection.2359 2360\section{Supermodular games}2361 2362\begin{definition}\Scl[\cite{Top79,Viv90,MR90}]2363A \term{supermodular game} is a game in which each $A_i$ is a complete lattice (in applications a compact2364sublattice of $\R^k$), and each $u_i$ is supermodular and upper semicontinuous in $a_i$ and has increasing2365differences in $(a_i,a_{-i})$.2366\end{definition}2367 2368Supermodularity of a game is preserved by the transformations $u_i\mapsto\alpha_iu_i+\beta_i(a_{-i})$ of2369\cref{def:equivalences}, so it is a property of a point of $\NFG_{\mathrm{inc}}$ together with an order on2370each action set.2371 2372\begin{theorem}\label{thm:supermodular}\Scl[\cite{Top79,Viv90,MR90,Zho94}]2373In a supermodular game:2374\begin{enumerate}[label=(\roman*)]2375\item the set of pure Nash equilibria is a nonempty complete lattice; in particular there are a greatest2376  equilibrium $\overline{a}$ and a least equilibrium $\underline{a}$;2377\item every rationalizable action, and the support of every mixed or correlated equilibrium, lies in the2378  order interval $[\underline{a},\overline{a}]$; the game is dominance solvable iff the pure2379  equilibrium is unique;2380\item if payoffs depend on a parameter $t$ with increasing differences in $(a_i,t)$, then2381  $\overline{a}(t)$ and $\underline{a}(t)$ are nondecreasing in $t$.2382\end{enumerate}2383\end{theorem}2384 2385\begin{proof}[Proof sketch]2386By \cref{thm:topkis} the greatest best response $\overline{b}_i(a_{-i})$ is well defined and monotone. The2387map $\overline{b}\colon A\to A$ is monotone on a complete lattice, so by \cref{thm:tarski} it has a greatest2388fixed point, which is a Nash equilibrium and is $\ge$ every equilibrium; dually for the least. For (ii),2389iterate $\overline{b}$ from the top element: the sequence decreases to $\overline{a}$, and at each step the2390actions above the current point are strictly dominated. (iii) is \cref{thm:topkis} again, applied to the2391fixed-point operator.2392\end{proof}2393 2394Compare with \cref{ch:mixing}. Existence is in pure strategies, by an order-theoretic fixed-point theorem2395whose proof is a transfinite iteration rather than a topological degree; the extremal equilibria are found2396by iterating best responses from the top and the bottom, which is both an algorithm and a model of2397adaptive learning \cite{MR90}; and comparative statics, which for general games founders on multiplicity2398and on the sign-indefiniteness of the index, is monotone for the extremal equilibria without further2399assumptions. The price is the hypothesis. But the hypothesis is satisfied by a remarkable share of the2400models economists care about: price competition with differentiated products, technology adoption, search,