Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2461–2560 of 6559. Source text is displayed literally.
2461invariance 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 2541A Nash equilibrium of a dynamic game may rest on a threat that would not be carried out. Selten's remedy2542\cite{Sel65,Sel75} is to require equilibrium not only in the game but in every part of it that is itself a2543game. This chapter gives two descriptions of the resulting concept. For finite games of perfect2544information it is the value of a recursive function on trees. In general it is a modal operator applied to2545the Nash predicate---the temporal sibling of the knowledge operator of \cref{ch:knowledge}.2546 2547\section{Finite games are an initial algebra}2548 2549Fix a set $O$ of outcomes (say $\R^N$) and a countable set of action names. Consider the polynomial2550endofunctor of $\Set$2551\[ P(X)=O+\sum_{i\in N}\ \sum_{A}X^A, \]2552where $A$ ranges over finite nonempty sets of action names. An element of $P(X)$ is either an outcome or a2553triple (player, action set, assignment of an element of $X$ to each action).2554 2555\begin{proposition}\Sob2556The initial algebra $\mu P$ is the set of finite game trees of perfect information with outcomes in $O$,2557without moves of Nature. For every $P$-algebra $\alpha\colon P(V)\to V$ there is a unique map2558$\sem{-}_\alpha\colon\mu P\to V$ with $\sem{\text{leaf }o}=\alpha(o)$ and2559$\sem{(i,A,(\Gamma_a)_{a\in A})}=\alpha\bigl(i,A,(\sem{\Gamma_a})_{a}\bigr)$.2560\end{proposition}