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

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 thousand2799defections. Selten's \emph{chain-store paradox} \cite{Sel78} makes the discomfort vivid. An incumbent faces2800the entry game of \cref{ex:entry} in twenty towns in sequence. Induction says that she accommodates in the2801last town, hence in the nineteenth, hence in all, and that every entrant enters. Everyone's intuition2802says that she fights early entrants to deter later ones, and that it works. Selten took the paradox to2803show a gap between the theory and reasonable behaviour. We will take it to show that the intuition is2804computing a different fixed point from the induction. (When $G$ has several equilibria the theorem fails2805and finite repetition can sustain a good deal \cite{BK85}; \cref{ex:pareto-perfect} was an instance.)2806 2807\section{Strategies are coalgebras}2808 2809Turn to the infinitely repeated game $G^\infty(\delta)$, with payoffs2810$U_i=(1-\delta)\sum_{t\ge0}\delta^tu_i(a^t)$ for a discount factor $\delta\in(0,1)$.2811 2812\begin{definition}2813An \term{automaton} for player $i$ is a set $Q$ of states with an initial state, an output map2814$f\colon Q\to A_i$ and a transition map $\tau\colon Q\times A\to Q$. Equivalently it is a pointed coalgebra2815$Q\to F(Q)$ for the functor $F(X)=A_i\times X^A$ on $\Set$.2816\end{definition}2817 2818\begin{proposition}\label{prop:final-strategy}\Sli[\cite{Rut00}]