Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 719–818 of 6559. Source text is displayed literally.
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 strictly781dominated by a mixture, and verify directly that it is a best response to no conjecture.782\end{exercise}783\begin{exercise}784An agent chooses $x\in\{1,\dots,9\}$ and wishes to be as close as possible to two-thirds of the average of all785choices. Write her as a selection function on contexts $k\colon X\to\R$, where $k$ returns the resulting786average. Show that her selection function is not $\argmax$ of any fixed utility on $X$, and find the787selection equilibria of the $n$-player game.788\end{exercise}789\begin{exercise}790Prove that the operator $\Phi$ of \cref{thm:rationalizable} is monotone, and that every Nash equilibrium is791contained in $\nu\Phi$, by exhibiting a post-fixed point.792\end{exercise}793\begin{exercise}794Show that deleting \emph{all} weakly dominated actions of all players simultaneously at each round is a795well-defined procedure, invariant under incentive equivalence, and hence a solution concept on796$\NFG_{\mathrm{inc}}$ in the sense of \cref{prin:invariance}. Compute its output on \cref{ex:weakdom} and797compare it with the two sequential orders. What has been bought, and at what price?798\end{exercise}799%% ---- end ch/01-rules.tex ----800%% ---- begin ch/02-open.tex ----801\chapter{Open Games}\label{ch:open}802 803A game in strategic form is a closed system. There is no operation that takes two such games and plugs the804outcome of one into the payoffs of the other, or runs one after the other with the second player watching805the first; each new situation is modelled from scratch. Yet informally games are built from parts all the806time---``a bargaining stage followed by a production stage'', ``the same market in each of two periods''.807This chapter presents the calculus, due to Ghani, Hedges, Winschel and Zahn \cite{GHWZ18,Hed16}, in which808that informal practice is literal: a game with open boundaries is a morphism, and games compose.809 810\section{Lenses}811 812The boundary of an open game carries information in two directions. Forwards flow observations and moves;813backwards flows value. The algebra of such two-way boundaries is the category of lenses.814 815\begin{definition}\label{def:lens}816A \term{lens} $(X,S)\to(Y,R)$ between pairs of sets is a pair $\lambda=(v,c)$ of functions817\[ v\colon X\to Y\qquad\text{(view, or play)},\qquad c\colon X\times R\to S\qquad\text{(update, or coplay)}. \]818The composite of $(v,c)\colon(X,S)\to(Y,R)$ and $(v',c')\colon(Y,R)\to(Z,Q)$ has view $v'\circ v$ and update