Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2601–2700 of 6559. Source text is displayed literally.
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 to2661produce more makes the rival produce less. Had the variables been strategic complements, as prices are in2662\cref{ex:bertrand}, the leader would commit to be soft, and both would gain.2663\end{example}2664 2665In the calculus of \cref{ch:open} the difference between the Cournot and Stackelberg games is one wire:2666the copy of $q_1$ that runs into firm~2's decision in \cref{fig:og-seq}. Commitment is observability.2667Accordingly its value is fragile to noise in the wire: if the follower observes the leader's choice only2668imperfectly, however slightly, the pure-strategy equilibrium reverts to the simultaneous-move outcome2669\cite{Bag95}. The algebraic reading is the Escard\'o--Oliva product of \cref{sec:selection}: the leader's2670selection function is applied to the context that already contains the follower's response.2671 2672\subsection*{Sunk costs and threats}2673 2674Consider a plaintiff with a claim of expected value $J$ at trial, where going to trial costs her $c_P$ and2675the defendant $c_D$. If $J<c_P$ her threat to litigate is empty and backward induction gives a settlement2676of zero: she will drop the suit, so the defendant offers nothing. Now suppose that she can pay part $s$ of2677her costs before the settlement stage. Sunk costs are sunk: at the settlement stage only the remaining2678cost $c_P-s$ matters. If $J>c_P-s$ the threat has become credible, and the defendant will pay up to2679$J+c_D$ to avoid trial. A suit with negative expected value at the outset can extract a positive2680settlement, because the order in which costs are incurred is part of the tree \cite{Beb96}. The example2681repeats the lesson of the Thompson moves: what is strategically irrelevant in a decision problem---when a2682cost is paid---is relevant in a game.2683 2684\section{The open-set problem}\label{sec:openset}2685 2686Suppose the plaintiff makes a take-it-or-leave-it demand $S$ and the defendant accepts if $S<J+c_D$,2687rejects if $S>J+c_D$. What does the defendant do at $S=J+c_D$? If she rejects when indifferent, the2688plaintiff wishes to demand the largest number strictly below $J+c_D$, and there is none: the plaintiff's2689maximization is over an open set and the supremum is not attained. No best response exists, hence no2690equilibrium. The only subgame perfect equilibrium has the defendant accept when indifferent.2691 2692This is usually presented as a technicality, and resolved by a convention. It is better understood as a2693theorem about selection functions. $\argmax$ is a total selection function on a space of alternatives only2694when maxima exist, which for continuous contexts means that the space is compact---\emph{searchable}, in2695the terminology of \cref{sec:selection}. When a player's feasible set depends on another's tie-breaking2696rule, existence of equilibrium determines the tie-breaking rule: indifference must be resolved in the2697way that closes the first mover's feasible set. Simon and Zame \cite{SZ90} turned this observation into a2698general existence theorem for discontinuous games in which the rule for resolving ties is part of the2699solution rather than part of the data. The economic content is that an equilibrium cannot rely on a2700party's rejecting an offer to which she is indifferent; the mathematical content is that selection