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

481assigning to each problem $k$ the set $\varepsilon(k)\subseteq X$ of alternatives the agent is willing to482choose. When $R$ carries a total preorder, the \term{maximizing} selection function is483$\argmax(k)=\{x \st k(x)\ge k(x')\ \text{for all }x'\}$.484\end{definition}485 486The map $k$ is the agent's \emph{context}: everything about the world that matters to her, compressed into487the consequence of each alternative. Selection functions were isolated by Escard\'o and Oliva488\cite{EO10,EO11}, in single-valued form $(X\to R)\to X$, as the computational content of choice. Separating489the agent $\varepsilon$ from the context $k$ pays off twice. It lets a context be supplied by other agents,490which is what a game is. And it does not commit us to maximization: an agent who wants to be at the median,491or to pick whatever a majority picks, is a perfectly good selection function, though no utility function492on $X$ represents her \cite{HOSWZ17}.493 494\section{Games in strategic form, and their types}495 496\begin{definition}\label{def:nfg}497A (finite) \term{game in strategic form} consists of a finite set $N$ of players; for each $i\in N$ a finite498nonempty set $A_i$ of actions; and for each $i$ a payoff function $u_i\colon A\to\R$, where499$A=\prod_{j\in N}A_j$. In type-theoretic notation the type of such games is500\[ \NFG_u \;\defeq\; \sum_{N:\FinSet}\ \sum_{A:N\to\FinSet_{+}}\ \prod_{i:N}\Bigl(\prod_{j:N}A_j\to\R\Bigr). \]501\end{definition}502 503Writing the definition as a type is not decoration. A type comes with its identity types, and the identity504type of a type of structures is forced.505 506\begin{lemma}[Identity of games]\label{lem:identity}507\Sli[{\cite[\S 2.14, \S 9.8]{HoTT13}, \cite{ANST21}}]508For $G=(N,A,u)$ and $G'=(N',A',u')$ in $\NFG_u$, the identity type $G=G'$ is equivalent to the type of triples509$(\nu,\alpha,\theta)$ where $\nu\colon N\simeq N'$ is a bijection of players, $\alpha_i\colon A_i\simeq510A'_{\nu(i)}$ is a family of bijections of actions, and $\theta$ witnesses $u'_{\nu(i)}\circ\alpha=u_i$ for all $i$.511\end{lemma}512 513So an identification of games is an isomorphism: a relabelling of players and actions under which payoffs514agree on the nose. In particular $\NFG_u$ is not a set but a groupoid, and the loop space at a game $G$ is515its automorphism group $\Aut(G)$. We return to this in \cref{sec:symmetry}.516 517The identity type of $\NFG_u$ is the right one for the data, and the wrong one for the subject, because518payoff numbers are over-specified. Two coarser notions of sameness are in constant informal use.519 520\begin{definition}\label{def:equivalences}521Let $u,u'$ be payoff profiles on the same game form $(N,A)$.522\begin{enumerate}[label=(\alph*)]523\item $u$ and $u'$ are \term{preference equivalent} if for each $i$ there are $\alpha_i>0$ and $\beta_i\in\R$524  with $u'_i=\alpha_iu_i+\beta_i$.525\item $u$ and $u'$ are \term{incentive equivalent} if for each $i$ there are $\alpha_i>0$ and a function526  $\beta_i\colon A_{-i}\to\R$ with $u'_i(a)=\alpha_iu_i(a)+\beta_i(a_{-i})$.527\end{enumerate}528We write $\NFG_{\succsim}$ and $\NFG_{\mathrm{inc}}$ for the types of game forms equipped with a payoff529profile up to (a), respectively (b), so that there are quotient maps530$\NFG_u\twoheadrightarrow\NFG_{\succsim}\twoheadrightarrow\NFG_{\mathrm{inc}}$.531\end{definition}532 533Preference equivalence is the indeterminacy of von Neumann--Morgenstern utility: by the expected-utility534theorem a point of $\NFG_{\succsim}$ is a game form with, for each player, a preference relation over535lotteries on $A$ satisfying independence and continuity (\cref{ch:mixing}). Presenting it by numbers is a536choice of coordinates. Incentive equivalence is coarser. It remembers only how each player ranks her own537(mixed) actions against each conjecture about the others; adding $\beta_i(a_{-i})$ changes how much player $i$538likes what the \emph{others} do, which she cannot affect. Morris and Ui \cite{MU04} study this and neighbouring539notions under the names \emph{von Neumann--Morgenstern equivalence} and \emph{best-response equivalence}.540 541\begin{principle}[Solution concepts are functions on types]\label{prin:invariance}542A solution concept on a type $\mathcal{T}$ of games is a dependent function543\[ S\colon \prod_{G:\mathcal{T}}\Pow\bigl(\Sigma(G)\bigr), \]544where $\Sigma(G)$ is the set of strategy profiles of $G$. Consequently $S$ respects every identification in545$\mathcal{T}$: if $p\colon G=G'$ then $p_*S(G)=S(G')$. A rule defined on presentations defines a solution546concept on $\mathcal{T}$ exactly when it is invariant under the equivalence that $\mathcal{T}$ imposes.547\end{principle}548 549This is not an axiom about rational play; it is what the word ``function'' means once the domain is taken550seriously. Its force comes from choosing the domain. Which concepts live on which type?551 552\begin{proposition}\label{prop:which-type}\Sob553\begin{enumerate}[label=(\roman*)]554\item Strict dominance, rationalizability, Nash equilibrium, correlated equilibrium and (for $2\times2$555  games) risk dominance are well defined on $\NFG_{\mathrm{inc}}$.556\item Pareto efficiency and payoff dominance are well defined on $\NFG_{\succsim}$ and do not descend to557  $\NFG_{\mathrm{inc}}$.558\end{enumerate}559\end{proposition}560 561\begin{proof}562(i) Each of these is defined through differences $u_i(a_i,\mu)-u_i(a_i',\mu)$ of a player's expected payoff563between two of her own actions against a fixed distribution $\mu$ over the others' actions, and only564through the signs of such differences, or---for risk dominance---through comparisons of products over players565of such differences. A transformation $u_i\mapsto\alpha_iu_i+\beta_i(a_{-i})$ multiplies every such566difference by $\alpha_i>0$.567(ii) Invariance under positive affine maps is clear. For the failure, take the Prisoner's Dilemma of the568Introduction and subtract from each player's payoff $2$ whenever the opponent plays $C$. The result is569incentive equivalent to the original, but its unique equilibrium $(D,D)$, with payoffs $(1,1)$, is now Pareto570efficient and payoff-dominates $(C,C)$, with payoffs $(0,0)$.571\end{proof}572 573The moral is worth stating plainly. The Prisoner's Dilemma is \emph{strategically} trivial---each player has a574strictly dominant action---and what makes it a dilemma is extra structure that the strategic analysis575never consults. Game theory's most famous example is famous for a feature that is invisible to every576solution concept in part (i). Keeping two types apart keeps two kinds of statement apart: predictions577(which live on $\NFG_{\mathrm{inc}}$) and evaluations (which need $\NFG_{\succsim}$).578 579\begin{remark}[Moduli]580In geometric language $\NFG_u$ is a moduli stack of games: its points are games, its paths are