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

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,2401bank runs, arms races, team production.2402 2403\section{Quantity competition}2404 2405\begin{example}[Cournot]\label{ex:cournot}2406Two firms choose quantities $q_1,q_2\ge0$ of a homogeneous good with inverse demand $P=a-b(q_1+q_2)$ and2407constant marginal cost $c<a$. Firm $i$'s profit is $q_i(a-c-b(q_i+q_j))$, and her best response is2408\[ q_i=\frac{a-c-bq_j}{2b}\quad(\text{or }0). \]2409Best responses slope \emph{downward}: quantities are \term{strategic substitutes} \cite{BGK85}. The unique equilibrium2410is $q_1=q_2=\frac{a-c}{3b}$, with price $\frac{a+2c}{3}$. With $n$ firms each produces $\frac{a-c}{(n+1)b}$2411and the price $\frac{a+nc}{n+1}$ tends to marginal cost.2412\end{example}2413 2414The Cournot duopoly has \emph{decreasing} differences in $(q_i,q_j)$, so it is not supermodular as it2415stands. But reverse the order on firm~2's action set and it is: with two players, strategic substitutes2416become strategic complements under the duality $L\mapsto L^{\op}$ applied to one of them. All of2417\cref{thm:supermodular} then applies, with ``greatest'' meaning ``most favourable to firm~1''. The trick is2418categorical---an adjunction with one side dualized is still an adjunction---and it is special to two2419players: with three firms there is no consistent reversal, and genuinely different behaviour appears.2420The best-response map of the linear duopoly has slope $-\tfrac12$, so it is a contraction and iterated2421best responses converge; with three firms the slopes sum to $-1$ and the iteration cycles; with more it2422diverges \cite{The60}.2423 2424\section{Price competition}2425 2426\begin{example}[Bertrand]\label{ex:bertrand}2427If instead the two firms choose prices and the good is homogeneous, the lower-priced firm takes the whole2428market. Any price pair above cost invites undercutting, and the unique equilibrium is $p_1=p_2=c$: two2429firms suffice for the competitive outcome. This is the \emph{Bertrand paradox}. The payoff is discontinuous, and the2430conclusion is fragile: capacity limits, product differentiation, repeated interaction and incomplete2431information each overturn it, and \cref{ch:pricing} examines them.2432 2433With differentiated products, let demand be $q_i=a-p_i+sp_j$ with $0\le s<2$. Profit $(p_i-c)(a-p_i+sp_j)$ has best response2434\[ p_i=\frac{a+c+sp_j}{2}, \]2435which slopes \emph{upward}: prices are \term{strategic complements}. The game is supermodular, and its unique equilibrium is2436$p^*=\frac{a+c}{2-s}$. An increase in $a$ or in $c$ raises both prices, by part (iii) of the theorem,2437without any computation.2438\end{example}2439 2440The distinction between substitutes and complements governs how a firm should try to influence a rival's