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 741–840 of 6559. Source text is displayed literally.

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 update819$(x,q)\mapsto c\bigl(x,c'(v(x),q)\bigr)$. Lenses form a symmetric monoidal category $\Lens$ with820$(X,S)\otimes(X',S')=(X\times X',S\times S')$ and unit $I=(1,1)$.821\end{definition}822 823Two families of lenses matter immediately. A lens $I\to(X,S)$ is an element $x\in X$: a \emph{state}, or824history. A lens $(Y,R)\to I$ is a function $k\colon Y\to R$: a \emph{costate}---which is precisely a decision825problem in the sense of \cref{def:decision}, a context assigning to each move its consequence. Composing a826lens $\lambda\colon(X,S)\to(Y,R)$ with a costate $k$ gives a costate $k\circ\lambda\colon x\mapsto c(x,k(v(x)))$827on $(X,S)$: lenses transport contexts backwards. This is the whole idea. A piece of a game is a process828that turns what it sees into what it does, and turns the value of what it does into the value of what it829saw.830 831\section{Open games}832 833\begin{definition}[Open game]\label{def:opengame}\Sli[\cite{GHWZ18}; predicate form as in \cite{BHZ19}]834An \term{open game} $\mathcal{G}\colon(X,S)\to(Y,R)$ consists of835\begin{itemize}836\item a set $\Sigma_{\mathcal{G}}$ of strategy profiles;837\item for each $\sigma\in\Sigma_{\mathcal{G}}$ a lens $\mathcal{G}_\sigma=(P_\sigma,C_\sigma)\colon(X,S)\to(Y,R)$, the838  \emph{play} and \emph{coplay} under $\sigma$;839\item an \term{equilibrium predicate} $E_{\mathcal{G}}\colon X\times(Y\to R)\to\Pow(\Sigma_{\mathcal{G}})$,840  assigning to each context $(x,k)$---a state of the source and a costate of the target---the set of