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

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 that2639is not a best response. Only $(\mathit{In},\mathit{Accommodate})$ is subgame perfect, and it is the2640backward-induction solution. This is the equilibrium that the composite of open games in \cref{ex:og-seq}2641failed to exclude.2642\end{example}2643 2644\section{Commitment}2645 2646The incumbent of \cref{ex:entry} would like the entrant to believe that entry will be fought. Subgame2647perfection says the entrant will not believe it, because once entry has occurred fighting is not in the2648incumbent's interest. The only way to make the threat credible is to change the game: to take an earlier,2649observable, irreversible action after which fighting \emph{is} optimal, or accommodation unavailable. This is2650Schelling's insight \cite{Sch60}: \emph{a player can gain by reducing her own options or her own payoffs}.2651In a decision problem, deleting alternatives never helps. In a game it can, because it changes the2652context that others face. Formally a commitment device is a morphism of games---a new first stage2653composed in front---and its value is the difference between two backward-induction values.2654 2655\begin{example}[Stackelberg]\label{ex:stackelberg}2656In the linear market of \cref{ex:cournot}, let firm~1 choose its quantity first and firm~2 observe it.2657Firm~2 plays its best response $q_2=\frac{a-c-bq_1}{2b}$, so firm~1 maximizes2658$q_1\bigl(a-c-bq_1-bq_2\bigr)=\tfrac12q_1(a-c-bq_1)$ and chooses $q_1=\frac{a-c}{2b}$; then2659$q_2=\frac{a-c}{4b}$. The leader's profit $\frac{(a-c)^2}{8b}$ exceeds the Cournot profit2660$\frac{(a-c)^2}{9b}$, and the follower's is lower. Quantities are strategic substitutes: committing to