Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 3181–3280 of 6559. Source text is displayed literally.
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.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: