Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3221–3320 of 6559. Source text is displayed literally.
3221a \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.3241 3242\begin{theorem}\label{thm:reputation}\Scl[\cite{KMRW82,FL89}]3243\begin{enumerate}[label=(\roman*)]3244\item In the finitely repeated Prisoner's Dilemma in which one player is, with probability $\epsilon>0$, a3245 type that plays tit-for-tat, the number of periods in which either player defects in a sequential3246 equilibrium is bounded by a constant that depends on $\epsilon$ and not on the number of repetitions.3247\item A patient long-run player facing a sequence of short-run opponents, who assign positive probability3248 to her being committed to her Stackelberg action, obtains in every Nash equilibrium a payoff close to3249 her Stackelberg payoff.3250\end{enumerate}3251\end{theorem}3252 3253Two structural comments. First, the natural state variable of a reputation equilibrium is the posterior.3254The equilibrium is Markov in the sense of \cref{prop:markov} once the state space is enlarged from3255histories to beliefs: with incomplete information the continuation game depends on what is believed, so3256beliefs are payoff-relevant and the bisimulation quotient of the game is a space of posteriors. Second,3257part (ii) says that reputation \emph{selects}: out of the folk theorem's continuum it picks the outcome that3258commitment would produce. A possibility of being committed is a substitute for commitment. Both comments3259are instances of a single observation, to which we now turn: the equilibrium correspondence is3260discontinuous in the type space, and small perturbations of beliefs can have effects that small3261perturbations of payoffs cannot.3262 3263\section{Almost common knowledge}3264 3265\begin{example}[Electronic mail game]\label{ex:email}\Scl[\cite{Rub89}]3266Two players would like to coordinate on a risky action when the state is $b$ and on a safe action when the3267state is $a$; the risky action is costly unless both take it in state $b$. Player~1 learns the state. If it3268is $b$, her computer sends a message to player~2's, which sends a confirmation, which is confirmed in3269turn, and so on; each message is lost with small probability $\epsilon$, and the exchange stops at the first3270loss. Each player observes only the number of messages her own machine sent. Then in the unique3271rationalizable outcome both players take the safe action in every state, however many messages have been3272exchanged.3273\end{example}3274 3275The information structure is the simplest possible illustration of \cref{ch:knowledge}. The states are the3276pairs (number of messages sent by~1, number sent by~2), which are $(0,0),(1,0),(1,1),(2,1),\dots$; player~13277cannot distinguish $(n,n-1)$ from $(n,n)$, and player~2 cannot distinguish $(n,n)$ from $(n+1,n)$. The3278knowledge graph $B$ is a single infinite path. It is connected, so by \cref{prop:hocolim} the meet is3279trivial and \emph{no} nontrivial event is ever common knowledge, although after $2n$ messages the players3280have $n$ levels of mutual knowledge of the state. The proof of the example is an induction along the path:3281safe play at one vertex forces safe play at the next. Truncations $\K^n$ of the common-knowledge hierarchy3282do not approximate $\CK$ as far as behaviour is concerned.3283 3284What does? Monderer and Samet's answer \cite{MS89} is to weaken the modality rather than truncate the3285iteration. Let $\mathsf{B}^p_iE$ be the event that $i$ assigns probability at least $p$ to $E$, and define3286\term{common $p$-belief} from the operators $\mathsf{B}^p_i$ as common knowledge was defined from $\K_i$. Then3287equilibrium behaviour under common $p$-belief of the game converges to behaviour under common knowledge as3288$p\to1$. The family $(\mathsf{B}^p)_{p\in[0,1]}$ is a \emph{graded} modality, and the theorem says that3289strategic behaviour is continuous in the grade although not in the depth.3290 3291The same discontinuity appears on the universal type space. $T^*$ was built in \cref{thm:universal} as an3292inverse limit and carries the product topology, in which two types are close when their beliefs agree to3293high finite order.3294 3295\begin{theorem}\label{thm:WY}\Scl[\cite{WY07,DFM06}]3296For every type $t$ in the universal type space and every action $a$ that is rationalizable for $t$, there3297are types arbitrarily close to $t$ in the product topology for which $a$ is the \emph{unique}3298rationalizable action (under a richness assumption on payoffs). Consequently no refinement of rationalizability3299is robust to perturbations of higher-order beliefs, and the coarsest topology on types in which3300rationalizable behaviour is continuous is strictly finer than the product topology.3301\end{theorem}3302 3303The universal type space exists because of a continuity property of the functor $\Giry$; strategic3304behaviour is discontinuous in exactly the topology that this property provides. The semantics of types and3305the semantics of play live on the same set and disagree about its topology. One may regard this as bad3306news for refinements, or as an instrument. \emph{Global games} \cite{CvD93,MS98} use it as an instrument:3307adding small private noise to a coordination game with multiple equilibria produces a game with a unique3308rationalizable outcome, obtained by an infection argument like that of the mail game, and the outcome3309selected is the risk-dominant one. Note that this is consistent with \cref{prop:which-type}: the argument3310uses only best-response structure, and risk dominance is the selection criterion that lives on3311$\NFG_{\mathrm{inc}}$.3312 3313\section*{Notes}3314 3315Sequential equilibrium is due to Kreps and Wilson \cite{KW82a}, perfect equilibrium to Selten \cite{Sel75},3316and perfect Bayesian equilibrium in its usual form to Fudenberg and Tirole \cite{FT91b}. Conditional3317probability systems go back to R\'enyi \cite{Ren55} and were brought into game theory by Myerson3318\cite{Mye86}; McLennan \cite{McL89a,McL89b} studied the topology of the spaces of conditional systems and3319of consistent assessments, and Kohlberg and Reny \cite{KR97} characterized consistency by an independence3320condition on relative probabilities. Lexicographic and non-Archimedean representations are in