Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3141–3240 of 6559. Source text is displayed literally.
3141which $\sigma^k$ gives positive probability to every action and $\mu^k$ is derived from $\sigma^k$ by3142Bayes' rule. A \term{sequential equilibrium} is a consistent, sequentially rational assessment.3143\end{definition}3144 3145\begin{theorem}\Scl[\cite{KW82a,Sel75}]3146Every finite extensive game with perfect recall has a sequential equilibrium. Every trembling-hand perfect3147equilibrium is sequential, and for generic payoffs the two concepts coincide. Every sequential equilibrium3148is subgame perfect.3149\end{theorem}3150 3151\section{The geometry of conditioning}\label{sec:cps}3152 3153Consistency is a closure condition. On the open set of fully mixed strategies, beliefs are a rational3154function of strategies; the consistent assessments are the closure of the graph of that function. Taking3155the closure of the graph of a rational map is a classical operation in geometry---it is a \emph{blow-up}---and3156looking at it this way explains what off-path beliefs are.3157 3158Consider the simplest case: a finite set $\Omega$ and the map sending a fully supported $p\in\Dist\Omega$ to3159its family of conditionals $\bigl(p(\cdot\mid S)\bigr)_{S}$, one for each nonempty $S\subseteq\Omega$.3160 3161\begin{definition}\Scl[\cite{Mye86,Ren55}]3162A \term{conditional probability system} on $\Omega$ is a family $(p_S)_{\emptyset\neq S\subseteq\Omega}$ with3163$p_S\in\Dist(S)$ and $p_T(R)=p_S(R)\,p_T(S)$ for $R\subseteq S\subseteq T$.3164\end{definition}3165 3166\begin{proposition}[Conditional systems are a blow-up]\label{prop:cps}\Srf[\cite{McL89a,Mye86,BBD91}]3167The space of conditional probability systems on a finite set $\Omega$ is the closure of the image of the3168open simplex in $\prod_S\Dist(S)$. It is a compactification of the open simplex in which each face of the closed simplex has3169been replaced by the product of that face with the space of conditional systems on the complementary set3170of states. Its strata are indexed by the ordered partitions $(\Omega_1,\dots,\Omega_k)$ of $\Omega$: a point of that3171stratum is a fully supported distribution on each block, the states of $\Omega_{j+1}$ being infinitely less3172likely than those of $\Omega_j$. Topologically it is a closed ball \cite{McL89a}.3173\end{proposition}3174 3175For three states the picture is \cref{fig:cps}. A sequence of priors converging to the vertex $\delta_1$3176has, along the way, a well-defined ratio $p_2:p_3$, and different sequences converge to different limiting3177ratios. The simplex forgets the ratio; the blow-up remembers it, replacing the vertex by a segment. Each3178corner becomes an edge and the triangle becomes a hexagon. In general the face poset is that of the3179ordered partitions, which is the face poset of the permutohedron.3180 3181\begin{figure}[ht]\centering3182\begin{tikzpicture}[x=1cm,y=1cm]3183 \coordinate (A) at (0,0); \coordinate (B) at (4.4,0); \coordinate (C) at (2.2,3.81);3184 \draw[densely dotted] (A)--(B)--(C)--cycle;3185 \coordinate (a1) at ($(A)!0.2!(B)$); \coordinate (a2) at ($(A)!0.2!(C)$);3186 \coordinate (b1) at ($(B)!0.2!(A)$); \coordinate (b2) at ($(B)!0.2!(C)$);3187 \coordinate (c1) at ($(C)!0.2!(A)$); \coordinate (c2) at ($(C)!0.2!(B)$);3188 \draw[thick,fill=black!5] (a1)--(b1)--(b2)--(c2)--(c1)--(a2)--cycle;3189 \draw[very thick,accent] (a1)--(a2) (b1)--(b2) (c1)--(c2);3190 \node[lab] at (-0.25,-0.2) {$\delta_1$}; \node[lab] at (4.65,-0.2) {$\delta_2$}; \node[lab] at (2.2,4.05) {$\delta_3$};3191 \node[lab] at (2.2,1.25) {$p_1,p_2,p_3>0$};3192 \node[lab,accent,anchor=east] at (0.1,0.75) {$p_2:p_3$};3193 \node[lab,accent,anchor=west] at (4.3,0.75) {$p_1:p_3$};3194 \node[lab,accent,anchor=west] at (2.75,3.45) {$p_1:p_2$};3195\end{tikzpicture}3196\caption{Conditional probability systems on three states. Each vertex of the simplex is blown up to a3197segment recording the limiting ratio of the two vanishing probabilities.}\label{fig:cps}3198\end{figure}3199 3200A consistent system of beliefs is a point of such a blow-up, constrained by the product structure that3201independent trembles of different players impose \cite{McL89b,KR97}. The equivalent descriptions in the3202literature are different coordinate systems on the same space: \emph{lexicographic probability systems}3203\cite{BBD91} list the distributions on the blocks in order; \emph{non-Archimedean probabilities}3204\cite{Ham94,Hal10} are single distributions with values in an ordered field containing infinitesimals, the blocks3205being the orders of magnitude. The last makes the geometry algebraic: a consistent assessment is the3206shadow of a fully mixed strategy profile over a larger ordered field, and sequential rationality is ordinary3207rationality there.3208 3209\begin{remark}[What kind of infinitesimal]3210The infinitesimals needed here are invertible elements of an ordered field, so that ratios of small3211probabilities make sense. They are not the nilpotent infinitesimals of synthetic differential geometry,3212which have no ratios. The appropriate ambient setting is real-closed fields and semialgebraic geometry3213rather than a smooth topos; conversely, the fact that equilibrium conditions are semialgebraic is what3214allows the transfer of results between $\R$ and its non-Archimedean extensions.3215\end{remark}3216 3217\section{Reputation}3218 3219Return to the chain-store paradox of \cref{ch:repetition}. Kreps and Wilson \cite{KW82b} and Milgrom and3220Roberts \cite{MR82a} resolved it by a small change to the type space: with probability $p$ the incumbent is3221a \emph{tough} type who fights every entry. Take the entry game with payoffs $(0,4)$ for no entry, $(1,2)$3222for accommodated entry and $(-1,1)$ for fought entry, where the second coordinate is the payoff of the3223ordinary incumbent. An entrant enters iff she thinks the probability of a fight is at most $\tfrac12$.3224 3225\begin{example}[Two towns]\label{ex:reputation}3226In the last town the ordinary incumbent accommodates, so the last entrant enters iff her posterior that3227the incumbent is tough is at most $\tfrac12$. In the first town, suppose entry occurs. If $p\ge\tfrac12$3228the ordinary incumbent fights: this leaves the posterior at $p$, deters the second entrant, and yields3229$1+4>2+2$. If $p<\tfrac12$ she cannot fight for sure (the posterior would stay below $\tfrac12$ and the3230fight would be wasted) nor accommodate for sure (a fight would then prove toughness and be well worth it).3231She fights with probability $\varphi=\frac{p}{1-p}$, which makes the posterior after a fight exactly3232$\tfrac12$, and the second entrant then enters with probability $\tfrac12$, which makes the incumbent3233indifferent. The first entrant faces a fight with total probability $p+(1-p)\varphi=2p$ and so stays out3234iff $p>\tfrac14$.3235\end{example}3236 3237One more town halves the threshold again. With $n$ towns remaining entry is deterred whenever3238$p>2^{-n}$: a one-in-a-thousand chance of toughness protects the incumbent in all but the last ten towns,3239however many there are. The chain-store intuition is restored by an arbitrarily small departure from3240complete information.