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

2441later choice. If actions are strategic substitutes, a commitment to be aggressive makes the rival retreat;2442if complements, it makes the rival aggressive too. The whole taxonomy of strategic investment \cite{FT84}2443is the sign of a cross partial derivative composed with the sign of the effect of the investment, and we2444return to it under the heading of commitment in \cref{ch:perfection}.2445 2446\section{Ordinal conditions}2447 2448Supermodularity is a cardinal condition: it is not preserved by monotone transformations of the2449objective, although the conclusion of Topkis's theorem obviously is. From the standpoint of2450\cref{prin:invariance} this is a defect of the hypothesis, and Milgrom and Shannon repaired it.2451 2452\begin{theorem}[Monotone comparative statics]\label{thm:MS}\Scl[\cite{MS94}]2453Let $X$ be a lattice and $T$ a poset. The correspondence $(t,S)\mapsto\argmax_{x\in S}f(x,t)$ is2454increasing in $t$ and in the sublattice $S$ (in the strong set order) if and only if $f$ is2455\term{quasi-supermodular} in $x$ and satisfies the \term{single-crossing property} in $(x,t)$: for $x'>x$2456and $t'>t$, $f(x',t)\ge f(x,t)$ implies $f(x',t')\ge f(x,t')$, and likewise with strict inequalities.2457\end{theorem}2458 2459The conditions are ordinal, and the theorem is an equivalence: single crossing is exactly what monotone2460comparative statics requires, no more. For games with von Neumann--Morgenstern payoffs the relevant2461invariance is only affine and the cardinal conditions are appropriate; for decision problems under2462certainty the ordinal ones are. Single crossing will carry Part~II: it is the condition under which types2463can be sorted by their choices, and so the condition under which screening and signalling work2464(\cref{ch:mechanism,ch:signalling}).2465 2466\section{The metric analogue}\label{sec:banach}2467 2468Lawvere observed \cite{Law73} that a category enriched in the ordered monoid $([0,\infty],\ge,+)$ is a2469generalized metric space: the hom-object $d(x,y)$ is a distance, composition is the triangle inequality2470$d(x,y)+d(y,z)\ge d(x,z)$, and the identity is $0\ge d(x,x)$. Enriched functors are the maps that do not2471increase distance. The table compares the two enrichments.2472 2473\begin{center}\small2474\renewcommand{\arraystretch}{1.25}2475\begin{tabular}{@{}lll@{}}2476\toprule2477 & \textbf{enriched in $\mathbf{2}$} & \textbf{enriched in $[0,\infty]$}\\\midrule2478object & preorder & generalized metric space\\2479functor & monotone map & nonexpansive map\\2480completeness & complete lattice & Cauchy completeness\\2481good endomaps & monotone & contractions\\2482fixed-point theorem & Tarski: a lattice of fixed points & Banach: a unique fixed point\\2483proof & transfinite iteration & geometric convergence\\2484\bottomrule2485\end{tabular}2486\end{center}2487 2488\noindent Game theory uses both columns, and the difference between them is the difference between2489multiplicity and uniqueness. A monotone operator has a least and a greatest fixed point and possibly many2490between; a contraction has one. When a strategic situation is governed by a monotone operator---best2491responses in a supermodular game, the Abreu--Pearce--Stacchetti operator of \cref{ch:repetition}, the2492unraveling operator of \cref{ch:adverse}---expect a lattice of equilibria and ask which end is selected.2493When it is governed by a contraction---the Bellman operator of a discounted decision problem, the2494Shaked--Sutton recursion for alternating-offer bargaining in \cref{ch:bargaining}---expect uniqueness.2495Discounting is what turns the first kind of problem into the second, when it does.2496 2497\section*{Notes}2498 2499Tarski's theorem is \cite{Tar55}. The lattice-theoretic approach to optimization and games is due to2500Topkis \cite{Top78,Top79}; his book \cite{Top98} is the standard reference. Vives \cite{Viv90} and Milgrom2501and Roberts \cite{MR90} developed supermodular games and their applications, and Zhou \cite{Zho94} proved2502that the equilibrium set is a complete lattice. Strategic substitutes and complements were named by Bulow,2503Geanakoplos and Klemperer \cite{BGK85}. The ordinal theory is from Milgrom and Shannon \cite{MS94}. The2504instability of Cournot adjustment with three or more firms is Theocharis's observation \cite{The60}.2505Lawvere's paper \cite{Law73} is the source of the enriched view of metric spaces; the parallel between2506order-theoretic and metric fixed points is developed in the domain-theory literature, for instance2507\cite{Rut96}.2508 2509\section*{Exercises}2510 2511\begin{exercise}2512Prove \cref{thm:tarski} for finite lattices by iterating $f$ from the top and bottom elements, and give an2513example of a monotone map on a non-complete lattice with no fixed point.2514\end{exercise}2515\begin{exercise}2516Show that a function on a product of two chains is supermodular iff it has increasing differences, and2517that $f(x,y)=g(x+y)$ is supermodular iff $g$ is convex.2518\end{exercise}2519\begin{exercise}2520Verify the equilibrium quantities, price and profits in \cref{ex:cournot} for $n$ firms, and show that2521total industry profit is decreasing in $n$.2522\end{exercise}2523\begin{exercise}2524In the differentiated Bertrand game of \cref{ex:bertrand}, compute the greatest and least rationalizable2525prices by iterating the best-response map from the bounds of the interval $[c,\bar p]$ for large $\bar p$.2526Conclude that the game is dominance solvable.2527\end{exercise}2528\begin{exercise}2529A coordination game: each of $n$ players chooses effort $e_i\in\{0,1,\dots,m\}$ and receives2530$2\min_je_j-e_i$. Show that the game is supermodular, describe its lattice of pure equilibria, and2531identify the greatest and least.2532\end{exercise}2533\begin{exercise}2534Give an example of a function satisfying the single-crossing property but not increasing differences, and a2535monotone transformation of a supermodular function that is not supermodular.2536\end{exercise}2537%% ---- end ch/07-order.tex ----2538%% ---- begin ch/08-perfection.tex ----2539\chapter{Perfection}\label{ch:perfection}2540