Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 681–780 of 6559. Source text is displayed literally.
681\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)$.719\end{proof}720 721The classical counterpart is the symmetry-invariance axiom of Harsanyi and Selten \cite{HS88}, and the722observation that it constrains selection is due to them and to Crawford and Haller \cite{CH90}; see723\cite{AK13} for a systematic account. What the type-theoretic phrasing adds is that the axiom is not724optional. One cannot write down a selection that violates it without consulting something that is not725in the game.726 727\begin{example}[No selection without structure]\label{ex:focal}728In the pure coordination game with payoffs $(1,1)$ on the diagonal and $(0,0)$ off it, the relabelling that729swaps both players' action names is an automorphism, and it exchanges the two pure equilibria. The only730equilibrium fixed by $\Aut(G)$ is the mixed one in which each player randomizes evenly, with expected payoff731$\tfrac12$. With $m$ actions the invariant equilibrium is uniform and pays $1/m$. In the Battle of the732Sexes of \cref{ex:three}, exchanging the players while exchanging $O$ and $F$ is an automorphism swapping the733pure equilibria; again only the mixed equilibrium is invariant. In the ranked coordination game no automorphism734moves $(a,a)$ to $(b,b)$, so each equilibrium is individually invariant and a rule such as ``play the735risk-dominant equilibrium'' is a legitimate function on $\NFG_{\mathrm{inc}}$.736\end{example}737 738People asked to meet a stranger somewhere in a city without communicating do far better than $1/m$; this is739Schelling's observation \cite{Sch60}, and his name for what they use is a \term{focal point}. The proposition740tells us what kind of thing a focal point must be. It cannot be a property of an equilibrium of $G$,741because $\Aut(G)$ permutes the candidates transitively. It is additional \emph{structure}: a labelling742$\lambda$ of the actions by descriptions that the players share and that are not all alike---``the clock743at the main station'', ``noon''---so that the game actually played is a point $(G,\lambda)$ of a different744type, of \term{framed games}, whose automorphism group $\Aut(G,\lambda)\subseteq\Aut(G)$ is smaller. In745$(G,\lambda)$ the salient equilibrium is invariant, and can be selected by a function.746 747\begin{remark}748This reading agrees with the modern formal treatments of focal points, in which frames or labels are749added to the strategic form and symmetries are restricted accordingly \cite{AK13}. It also explains a750persistent feature of the literature: every attempt to derive focal points from the unframed game751re-imports a frame under another name (a tie-breaking order on actions, a ``natural'' indexing of players).752An order on a set is exactly a structure that kills its automorphisms.753\end{remark}754 755\section*{Notes}756 757The vocabulary of players, actions, payoffs and information is standard; the general references used758throughout are \cite{OR94,FT91,Mye91,MSZ13}, and the source that this book shadows is \cite{Ras06}. Strategic759equivalence in the affine sense goes back to \cite{vNM44}. Order independence for strict dominance in760finite games is due to Gilboa, Kalai and Zemel \cite{GKZ90}; Apt \cite{Apt04} gives the rewriting-theoretic761proof used here and catalogues which elimination procedures are confluent. Rationalizability was introduced762by Bernheim \cite{Ber84} and Pearce \cite{Pea84}; its coinductive character is implicit in their763``best-response property''. Nash equilibrium is from \cite{Nas50a,Nas51}. Higher-order games and selection764equilibria are developed in \cite{HOSWZ17}. The structure identity principle that yields \cref{lem:identity}765is discussed in \cite{HoTT13} and in full generality in \cite{ANST21}.766 767\section*{Exercises}768 769\begin{exercise}770Show that incentive equivalence preserves the set of correlated equilibria (defined in \cref{ch:mixing}), and771give an example showing that it does not preserve the set of Pareto-efficient profiles other than the one772in the text.773\end{exercise}774\begin{exercise}775Let $G$ be a symmetric two-player game with action set $\{1,\dots,m\}$ and payoff $1$ if the actions agree and776$0$ otherwise. Compute $\Aut(G)$. Now add a frame in which action $1$ is distinguished and the others are777indistinguishable. Compute the automorphism group of the framed game and list its invariant equilibria.778\end{exercise}779\begin{exercise}780Give a three-action example in which an action is not strictly dominated by any pure action but is strictly