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

441sufficient statistic; garbling & factorization in a Markov category & \ref{ch:moralhazard}\\442market unraveling & iteration to a fixed point of a monotone map & \ref{ch:adverse}\\443incentive-compatible transfer & enriched copresheaf & \ref{ch:mechanism}\\444indirect utility & conjugate under a profunctor & \ref{ch:mechanism}\\445Bayes plausibility & fibre of the monad multiplication & \ref{ch:signalling}\\446Rubinstein uniqueness & unique guarded fixed point & \ref{ch:bargaining}\\447\bottomrule448\end{tabular}449\end{center}450 451\section*{How to read}452 453Part~I (\cref{ch:rules}--\ref{ch:dynamic}) is the theory of games; Part~II454(\cref{ch:moralhazard}--\ref{ch:signalling}) is the economics of asymmetric information; Part~III455(\cref{ch:bargaining}--\ref{ch:pricing}) contains applications; Part~IV is a single chapter of assessment.456\Cref{ch:rules,ch:open,ch:extensive,ch:knowledge,ch:belief} are the foundation and should be read in457order. After them the chapters are largely independent, with two exceptions: \cref{ch:signalling} and458Part~III lean on \cref{ch:mechanism}, and \cref{ch:bargaining} on \cref{ch:repetition}. A reader who459wants the classical theory only can read the statements tagged \textsf{classical} and the examples; a460reader who knows the classical theory can read the rest.461%% ---- end front.tex ----462\mainmatter463\part{Games}464%% ---- begin ch/01-rules.tex ----465\chapter{The Rules of the Game}\label{ch:rules}466 467A game is specified by its rules: the players, what each can do, what each knows when doing it, and how468each ranks the consequences. This chapter treats the simplest case, in which nobody learns anything before469acting, so that the only rules are players, actions and payoffs. Its real subject, however, is the question470that the simplest case already raises: when are two specifications \emph{the same game}? The answer organizes471the rest of the book.472 473\section{Decisions}474 475A game is several decision problems that share variables, so we begin with one.476 477\begin{definition}\label{def:decision}478A \term{decision problem} is a set $X$ of alternatives together with a map $k\colon X\to R$ into a set $R$479of outcomes. A \term{selection function} for $(X,R)$ is a map480\[ \varepsilon\colon (X\to R)\longrightarrow \Pow(X) \]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