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

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 2619Compare with \cref{def:K}. Knowledge is $p^*\forall_p$ for the map from states to an agent's observations:2620a proposition is known when it holds at every state the agent cannot distinguish from the actual one.2621Perfection is the same construction for the relation ``is a later subgame of'': a profile is perfect when2622it is an equilibrium at every subgame that could be reached. The first modality is S5 because2623indistinguishability is symmetric; the second is only S4 because time is not. \emph{Subgame perfection is to2624histories what knowledge is to states.} The parallel is exact enough to predict the next refinement: when2625no subgame begins at an information set, one must combine the two modalities and ask for optimality at2626every information set given what the player believes there. That is sequential rationality2627(\cref{ch:dynamic}).2628 2629Item (ii) deserves a second look. The Nash predicate is not hereditary---an equilibrium of the whole game2630may restrict to nonsense off the path---and $\Box$ repairs this in the only possible way, by passing to the2631hereditary core. \Cref{cor:spe-evil} can now be read as saying that the preorder of subgames, and with it2632the modality $\Box$, is not an invariant of the reduced strategic form.2633 2634\begin{example}[Entry]\label{ex:entry}2635An entrant chooses \emph{Out}, ending the game with payoffs $(0,4)$, or \emph{In}; the incumbent then chooses2636\emph{Accommodate}, giving $(1,2)$, or \emph{Fight}, giving $(-1,0)$. The strategic form has two pure2637equilibria, $(\mathit{In},\mathit{Accommodate})$ and $(\mathit{Out},\mathit{Fight})$. The second is Nash2638because the incumbent's choice is never tested; at the subgame after \emph{In} it prescribes an action that