Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2479–2578 of 6559. Source text is displayed literally.
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}2561 2562The unique map is the \emph{fold} determined by $\alpha$; it is definition by recursion on the tree, and its2563uniqueness is proof by induction on the tree.2564 2565\begin{theorem}[Zermelo--Kuhn]\label{thm:zermelo}\Scl[\cite{Kuh53}]2566Every finite game of perfect information has a subgame perfect equilibrium in pure strategies. If no player2567is indifferent between two terminal nodes, it is unique.2568\end{theorem}2569 2570\begin{proof}2571Take $V=\R^N$ and let $\alpha$ be the identity on outcomes and2572$\alpha(i,A,v)=v(a^*)$ for some $a^*\in\argmax_{a\in A}v(a)_i$. The fold $\sem{-}_\alpha$ assigns to every tree its2573\emph{backward-induction value}, and recording the maximizers chosen along the way gives a strategy profile2574that, by induction, is a Nash equilibrium of every subtree. Without ties $\alpha$ is a function with no2575choices to make.2576\end{proof}2577 2578Backward induction is therefore not an algorithm that happens to solve games; it is \emph{the} canonical