Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 541–640 of 6559. Source text is displayed literally.
541\begin{principle}[Solution concepts are functions on types]\label{prin:invariance}542A solution concept on a type $\mathcal{T}$ of games is a dependent function543\[ S\colon \prod_{G:\mathcal{T}}\Pow\bigl(\Sigma(G)\bigr), \]544where $\Sigma(G)$ is the set of strategy profiles of $G$. Consequently $S$ respects every identification in545$\mathcal{T}$: if $p\colon G=G'$ then $p_*S(G)=S(G')$. A rule defined on presentations defines a solution546concept on $\mathcal{T}$ exactly when it is invariant under the equivalence that $\mathcal{T}$ imposes.547\end{principle}548 549This is not an axiom about rational play; it is what the word ``function'' means once the domain is taken550seriously. Its force comes from choosing the domain. Which concepts live on which type?551 552\begin{proposition}\label{prop:which-type}\Sob553\begin{enumerate}[label=(\roman*)]554\item Strict dominance, rationalizability, Nash equilibrium, correlated equilibrium and (for $2\times2$555 games) risk dominance are well defined on $\NFG_{\mathrm{inc}}$.556\item Pareto efficiency and payoff dominance are well defined on $\NFG_{\succsim}$ and do not descend to557 $\NFG_{\mathrm{inc}}$.558\end{enumerate}559\end{proposition}560 561\begin{proof}562(i) Each of these is defined through differences $u_i(a_i,\mu)-u_i(a_i',\mu)$ of a player's expected payoff563between two of her own actions against a fixed distribution $\mu$ over the others' actions, and only564through the signs of such differences, or---for risk dominance---through comparisons of products over players565of such differences. A transformation $u_i\mapsto\alpha_iu_i+\beta_i(a_{-i})$ multiplies every such566difference by $\alpha_i>0$.567(ii) Invariance under positive affine maps is clear. For the failure, take the Prisoner's Dilemma of the568Introduction and subtract from each player's payoff $2$ whenever the opponent plays $C$. The result is569incentive equivalent to the original, but its unique equilibrium $(D,D)$, with payoffs $(1,1)$, is now Pareto570efficient and payoff-dominates $(C,C)$, with payoffs $(0,0)$.571\end{proof}572 573The moral is worth stating plainly. The Prisoner's Dilemma is \emph{strategically} trivial---each player has a574strictly dominant action---and what makes it a dilemma is extra structure that the strategic analysis575never consults. Game theory's most famous example is famous for a feature that is invisible to every576solution concept in part (i). Keeping two types apart keeps two kinds of statement apart: predictions577(which live on $\NFG_{\mathrm{inc}}$) and evaluations (which need $\NFG_{\succsim}$).578 579\begin{remark}[Moduli]580In geometric language $\NFG_u$ is a moduli stack of games: its points are games, its paths are581isomorphisms, and its set of connected components $\pi_0$ is the set of isomorphism classes with which582set-level game theory works. A solution concept is a section of the bundle of strategy profiles over the583stack. What the stack remembers and the coarse space forgets is the stabilizer $\Aut(G)$ at each point;584\cref{sec:symmetry} shows that this is exactly the information that the theory of focal points is about.585\end{remark}586 587\section{Dominance as rewriting}588 589\begin{definition}590In a game $G$, an action $a_i$ is \term{strictly dominated} if some mixed action $\sigma_i\in\Dist A_i$ has591$u_i(\sigma_i,a_{-i})>u_i(a_i,a_{-i})$ for every $a_{-i}$, and \term{weakly dominated} if the inequality is592weak for every $a_{-i}$ and strict for some. A \term{restriction} of $G$ is a product subset593$R=\prod_iR_i\subseteq A$ with all $R_i$ nonempty; it is a game $G|_R$ in its own right.594\end{definition}595 596In the Prisoner's Dilemma, $D$ strictly dominates $C$ for both players, and the analysis is over: no597assumption about what a player believes of the other is needed. When domination is not immediate one598iterates. Write $R\to R'$ if $R'$ is obtained from $R$ by deleting one action that is strictly dominated in599$G|_R$. This is an abstract rewriting system on the finite poset of restrictions.600 601\begin{theorem}[Order independence]\label{thm:order-indep}\Scl[\cite{GKZ90,Apt04}]602In a finite game the rewriting system $\to$ is terminating and confluent: every maximal sequence of603deletions of strictly dominated actions ends at the same restriction $R^\infty$.604\end{theorem}605 606\begin{proof}[Proof sketch]607Termination is finiteness. For confluence it suffices, by Newman's lemma, to check local confluence: if608$a_i$ and $b_j$ are each strictly dominated in $G|_R$, then $a_i$ is still strictly dominated after $b_j$ is609deleted. If $j\neq i$ the dominating mixture for $a_i$ still dominates on the smaller set of opponent610profiles. If $j=i$ and the mixture $\sigma_i$ dominating $a_i$ puts weight on $b_i$, replace that weight by611the mixture dominating $b_i$; since the game is finite, repeating the substitution a bounded number of times612yields a dominating mixture supported off $b_i$.613\end{proof}614 615For weak dominance confluence fails, and with it the claim to be a solution concept in the sense of616\cref{prin:invariance}: the output depends on the order of deletion, which is not part of the game.617 618\begin{example}[Weak dominance is order dependent]\label{ex:weakdom}619In the game620\[621\begin{array}{c|cc}622 & L & R\\\hline623T & 1,1 & 0,0\\624M & 1,1 & 2,1\\625B & 0,0 & 2,1626\end{array}627\]628both $T$ and $B$ are weakly dominated by $M$. Deleting $T$ first makes $L$ weakly dominated by $R$, and the629process ends at $\{M,B\}\times\{R\}$ with payoffs $(2,1)$. Deleting $B$ first makes $R$ weakly dominated by630$L$, ending at $\{T,M\}\times\{L\}$ with payoffs $(1,1)$.631\end{example}632 633Strict dominance has a second description that will recur.634 635\begin{theorem}[Rationalizability]\label{thm:rationalizable}\Scl[\cite{Ber84,Pea84}]636For a restriction $R$ let $\Phi(R)=\prod_i\Phi_i(R)$, where $\Phi_i(R)$ is the set of actions $a_i\in A_i$ that637are a best response to some conjecture $\mu\in\Dist(R_{-i})$. Then $\Phi$ is monotone; in a finite game its greatest fixed638point $\nu\Phi$ exists, equals $\bigcap_n\Phi^n(A)$, and coincides with the set $R^\infty$ of639\cref{thm:order-indep}.640\end{theorem}