Independent scholarship · Open accessThe monthly digest

Indexed text attachment

games-and-information-in-higher-categories.tex

Source for Games and Information in Higher Categories

View paper · Download original file

Lines 619–718 of 6559. Source text is displayed literally.

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,1679\end{array}680\qquad681\begin{array}{c|cc}682 & O & F\\\hline683O & 2,1 & 0,0\\684F & 0,0 & 1,2685\end{array}686\qquad687\begin{array}{c|cc}688 & a & b\\\hline689a & 2,2 & 0,0\\690b & 0,0 & 1,1691\end{array}692\]693The first is the Prisoner's Dilemma: $\NE=\{(D,D)\}$, found already by dominance. The second is a694\emph{Battle of the Sexes}: no action is dominated, every action is rationalizable, and695$\NE=\{(O,O),(F,F)\}$ in pure strategies. The third is a \emph{ranked coordination} game with696$\NE=\{(a,a),(b,b)\}$. Both of the latter have a third equilibrium in mixed strategies (\cref{ch:mixing}).697\end{example}698 699Rationalizability asks only that each action be justified by \emph{some} conjecture consistent with common700knowledge of rationality; equilibrium asks in addition that conjectures be \emph{correct}. The second701requirement is not a consequence of rationality, and the examples show its cost: where dominance gives702nothing, equilibrium gives several answers. The rest of this chapter is about what, if anything, the game703itself says about choosing among them.704 705\section{Symmetry and focal points}\label{sec:symmetry}706 707Let $G$ be a game. By \cref{lem:identity} the loops at $G$ in $\NFG_u$ are the automorphisms: relabellings708$(\nu,\alpha)$ of players and actions preserving payoffs. $\Aut(G)$ acts on profiles, and since it preserves709best responses it acts on $\NE(G)$ and on the mixed equilibria.710 711\begin{proposition}[Equivariance]\label{prop:equivariance}712\Sob Let $\mathcal{T}$ be a type of games and $s\colon\prod_{G:\mathcal{T}}\Sigma(G)$ a single-valued solution: a713function assigning to each game one (mixed) profile. Then for every $G$ the profile $s(G)$ is fixed by714every automorphism of $G$ in $\mathcal{T}$.715\end{proposition}716 717\begin{proof}718An automorphism is a path $p\colon G=G$. Dependent functions commute with transport: $p_*\,s(G)=s(G)$.