Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 2699–2798 of 6559. Source text is displayed literally.
2699solution 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 selection2701functions exist on closed sets.2702 2703\section{Renegotiation}\label{sec:renegotiation}2704 2705Subgame perfection requires each subgame to be played by \emph{some} equilibrium. When a subgame has2706several, the choice among them can depend on history, and this is how punishments are sustained: play the2707bad equilibrium if someone deviated. But if the players can talk when they reach the subgame, why would2708they agree to play an equilibrium that is worse for all of them?2709 2710\begin{example}\label{ex:pareto-perfect}2711Two players play the Prisoner's Dilemma of \cref{ex:three} and then, having observed the outcome, a2712coordination game with equilibrium payoffs $(2,2)$ and $(0,0)$. The profile ``cooperate; then play the good2713equilibrium if both cooperated and the bad one otherwise'' is subgame perfect: defecting gains $1$ in the2714first stage and loses $2$ in the second. But after a defection the players stand at the start of a2715coordination game in which both prefer the good equilibrium. If they can renegotiate, the bad equilibrium2716will not be played, the punishment is void, and cooperation in the first stage unravels.2717\end{example}2718 2719\emph{Pareto perfection} \cite{BPW87,BR89} formalizes this for finite-horizon games by a recursion on the2720tree: a profile is Pareto perfect if in every subgame the continuation is Pareto perfect and not Pareto-dominated2721by another profile that is Pareto perfect in all later subgames. In the language of the first2722section it is a fold whose algebra filters by Pareto dominance before choosing. For infinite horizons no2723last subgame anchors the recursion and several inequivalent definitions compete \cite{FM89}; this is the2724first sign of the difficulty that occupies the next chapter. Renegotiation has the unusual property of2725being a refinement that makes the players worse off, because the ability to reopen an agreement destroys2726the ability to commit to a punishment. We will meet the same phenomenon in contract theory2727(\cref{ch:moralhazard2}) and in durable-goods pricing (\cref{ch:pricing}).2728 2729\section*{Notes}2730 2731Subgame perfection was introduced by Selten \cite{Sel65} and extended to trembling-hand perfection in2732\cite{Sel75}. Backward induction is usually traced to Zermelo's analysis of chess; the general theorem for2733finite trees is in \cite{Kuh53}. The treatment of game trees as an initial algebra is standard in the2734semantics of programming languages and is the basis of the coalgebraic approach to infinite games2735discussed in \cref{ch:repetition}. Commitment is the central theme of Schelling's book \cite{Sch60}; the2736fragility of first-mover advantage to imperfect observation is due to Bagwell \cite{Bag95}. The credibility2737of threats to sue when costs are incurred in stages is analysed in \cite{Beb96}. Endogenous sharing rules2738are from \cite{SZ90}. Renegotiation-proofness and Pareto perfection are developed in2739\cite{BPW87,BR89,FM89}; the finite-horizon example is in the spirit of \cite{BK85}.2740 2741\section*{Exercises}2742 2743\begin{exercise}2744Write the entry game of \cref{ex:entry} as an element of $\mu P$ and compute its fold for (a) the2745value algebra, (b) the algebra of sets of values, (c) the algebra that computes the number of terminal nodes.2746\end{exercise}2747\begin{exercise}2748Prove items (i)--(iii) of \cref{prop:box}, and show by example that $\mathsf{Nash}$ is not hereditary.2749\end{exercise}2750\begin{exercise}2751In \cref{ex:stackelberg}, verify the profits, and compute the Stackelberg outcome for the differentiated2752price game of \cref{ex:bertrand}. Who gains from moving first, and who gains from the existence of a2753first mover?2754\end{exercise}2755\begin{exercise}2756A seller makes a take-it-or-leave-it price offer to a buyer whose value $v$ is common knowledge. Show that2757in the unique subgame perfect equilibrium the buyer accepts when indifferent. Now restrict prices to a2758grid of mesh $\epsilon$ and describe all subgame perfect equilibria.2759\end{exercise}2760\begin{exercise}2761In \cref{ex:pareto-perfect}, change the bad second-stage equilibrium to pay $(3,0)$ after a defection by2762player~2 and $(0,3)$ after a defection by player~1, where the coordination game is modified to have these2763as equilibria. Is the cooperative profile Pareto perfect?2764\end{exercise}2765\begin{exercise}2766Show that in a finite game of perfect information without ties, the backward-induction profile is the only2767profile surviving iterated elimination of weakly dominated strategies in a suitable order, and discuss2768this in light of \cref{ex:weakdom}.2769\end{exercise}2770%% ---- end ch/08-perfection.tex ----2771%% ---- begin ch/09-repetition.tex ----2772\chapter{Repetition}\label{ch:repetition}2773 2774When the same players meet repeatedly, today's behaviour can be rewarded or punished tomorrow, and2775cooperation that is impossible in one encounter can be sustained. Whether it \emph{is} sustained in2776equilibrium turns, notoriously, on whether there is a last encounter. This chapter argues that the2777dependence is not a quirk. A finitely repeated game is an element of an initial algebra and is solved by2778induction; an infinitely repeated game lives in a terminal coalgebra and is solved by coinduction; and the2779two universal properties give different answers.2780 2781\section{Finite repetition}2782 2783Let $G=(N,A,u)$ be a stage game. In the \term{repeated game} $G^T$ the players play $G$ in periods2784$t=1,\dots,T$, observing all past actions; a history is an element of $A^*=\coprod_tA^t$, a pure strategy2785of $i$ is a function $A^*\to A_i$, and payoffs are discounted sums of stage payoffs.2786 2787\begin{theorem}\label{thm:finite-rep}\Scl2788If $G$ has a unique Nash equilibrium $a^*$, then for every finite $T$ the unique subgame perfect equilibrium2789of $G^T$ is to play $a^*$ after every history.2790\end{theorem}2791 2792\begin{proof}2793Fold over the tree (\cref{thm:zermelo}, in the version for simultaneous-move stages): in the last period2794only $a^*$ is an equilibrium whatever the history; given that, the continuation value is independent of2795play in period $T-1$, so only $a^*$ is an equilibrium there; and so on.2796\end{proof}2797 2798In the Prisoner's Dilemma repeated a thousand times, the only subgame perfect equilibrium is a thousand