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

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} canonical2579map out of the type of finite games, and each choice of algebra is a different question asked of the tree.2580The algebra of the proof gives the value. An algebra on sets of values, taking all maximizers at each2581node, gives the set of all subgame-perfect payoffs. The algebra built from the product of selection2582functions gives \cref{thm:EO}. An algebra that at each node applies a Pareto filter before maximizing gives2583the renegotiation-proof values of \cref{sec:renegotiation}. What they share is the hypothesis: the tree is2584an element of an \emph{initial} algebra, so there is a last move from which to start. \Cref{ch:repetition}2585is about what happens when there is not.2586 2587\section{Subgame perfection as a modality}\label{sec:box}2588 2589Now let $\Gamma$ be any finite extensive game. Recall that a node $h$ roots a \emph{subgame} $\Gamma_h$ when2590no information set straddles the boundary of its subtree. Subgame roots are preordered by precedence, and2591a strategy profile $\sigma$ of $\Gamma$ restricts to a profile $\sigma|_h$ of each $\Gamma_h$.2592 2593\begin{definition}\Scl[\cite{Sel65}]2594$\sigma$ is a \term{subgame perfect equilibrium} of $\Gamma$ if $\sigma|_h$ is a Nash equilibrium of2595$\Gamma_h$ for every subgame root $h$.2596\end{definition}2597 2598Let $W$ be the set of pairs $(h,\sigma)$---a profile together with a subgame at which to evaluate it---and2599let $\mathsf{Nash}\subseteq W$ be the set of pairs with $\sigma|_h\in\NE(\Gamma_h)$. For a subset $Q\subseteq W$ define2600\[ \Box Q=\{(h,\sigma)\st(h',\sigma)\in Q\text{ for every subgame root }h'\text{ at or after }h\}. \]2601 2602\begin{proposition}[Perfection is necessity]\label{prop:box}\Sob2603\begin{enumerate}[label=(\roman*)]2604\item $\Box$ is an idempotent comonad on $\Pow(W)$ preserving all intersections; it satisfies the2605  S4 axioms $\Box Q\subseteq Q$ and $\Box Q=\Box\Box Q$.2606\item $\Box Q$ is the largest subset of $Q$ that is \emph{hereditary}: closed under passing to later subgames.2607\item $\SPE(\Gamma)=\{\sigma\st(\mathrm{root},\sigma)\in\Box\,\mathsf{Nash}\}$.2608\item $\Box=p^*\forall_p$-type base change: for the projection $p\colon W^{\le}\to W$ from the set of pairs2609  $\bigl((h,\sigma),h'\bigr)$ with $h'$ at or after $h$, and the evaluation $e\colon W^{\le}\to W$, $e((h,\sigma),h')=(h',\sigma)$,2610  one has $\Box=\forall_p\,e^*$.2611\end{enumerate}2612\end{proposition}2613 2614\begin{proof}2615All four are immediate from the definition; (i) is the general fact that the universal modality of a2616preorder is an S4 necessity, and (iv) exhibits it as a composite of right adjoints.2617\end{proof}2618