Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 579–678 of 6559. Source text is displayed literally.
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}641 642The coincidence rests on a separation argument: an action is a best response to no (possibly correlated)643conjecture exactly when a mixture strictly dominates it \cite{Pea84}. The first two claims are the644Knaster--Tarski theorem on the finite lattice of product subsets. The elements of $\nu\Phi$ are the645\term{rationalizable} actions, and the fixed-point description gives a proof principle:646 647\begin{quote}648\emph{Coinduction.} To show that $a_i$ is rationalizable, exhibit a product set $R\ni a_i$ with $R\subseteq\Phi(R)$.649\end{quote}650 651\noindent Such an $R$ is a set of actions each justified by conjectures supported inside $R$---a closed circle652of reasons. Rationalizability is therefore not the outcome of a deletion procedure that happens to converge;653it is a \emph{coinductive} predicate, the largest self-justifying set, and the procedure is the standard654way of computing a greatest fixed point from above. The same pattern---greatest fixed point of a monotone655operator, proved by exhibiting a post-fixed point---returns as self-generation in repeated games656(\cref{ch:repetition}) and as common knowledge (\cref{ch:knowledge}).657 658\section{Nash equilibrium}659 660\begin{definition}\label{def:nash}661For a game $G$ let $\BR\colon A\to\Pow(A)$ be the \term{best-response correspondence},662$\BR(a)=\prod_i\argmax u_i(-,a_{-i})$. A profile $a$ is a (pure) \term{Nash equilibrium} if $a\in\BR(a)$. Thus663\[ \NE(G)=\Fix(\BR), \]664the pullback of the graph of $\BR$ along the diagonal $A\to A\times A$.665\end{definition}666 667In the language of \cref{def:decision}: each player is a selection function $\varepsilon_i$; a profile $a$668supplies each player with the context $k_i=u_i(-,a_{-i})$; and $a$ is an equilibrium when each $a_i$ is669selected in the context that the others' choices create, $a_i\in\varepsilon_i(u_i(-,a_{-i}))$. Nothing in670this formulation uses maximization, and replacing $\argmax$ by other selection functions yields the671\emph{selection equilibria} of \cite{HOSWZ17}.672 673\begin{example}[Three small games]\label{ex:three}674\[675\begin{array}{c|cc}676 & C & D\\\hline677C & 2,2 & 0,3\\678D & 3,0 & 1,1