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

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 are581isomorphisms, and its set of connected components $\pi_0$ is the set of isomorphism classes with which582set-level game theory works. A solution concept is a section of the bundle of strategy profiles over the583stack. What the stack remembers and the coarse space forgets is the stabilizer $\Aut(G)$ at each point;584\cref{sec:symmetry} shows that this is exactly the information that the theory of focal points is about.585\end{remark}586 587\section{Dominance as rewriting}588 589\begin{definition}590In a game $G$, an action $a_i$ is \term{strictly dominated} if some mixed action $\sigma_i\in\Dist A_i$ has591$u_i(\sigma_i,a_{-i})>u_i(a_i,a_{-i})$ for every $a_{-i}$, and \term{weakly dominated} if the inequality is592weak for every $a_{-i}$ and strict for some. A \term{restriction} of $G$ is a product subset593$R=\prod_iR_i\subseteq A$ with all $R_i$ nonempty; it is a game $G|_R$ in its own right.594\end{definition}595 596In the Prisoner's Dilemma, $D$ strictly dominates $C$ for both players, and the analysis is over: no597assumption about what a player believes of the other is needed. When domination is not immediate one598iterates. Write $R\to R'$ if $R'$ is obtained from $R$ by deleting one action that is strictly dominated in599$G|_R$. This is an abstract rewriting system on the finite poset of restrictions.600 601\begin{theorem}[Order independence]\label{thm:order-indep}\Scl[\cite{GKZ90,Apt04}]602In a finite game the rewriting system $\to$ is terminating and confluent: every maximal sequence of603deletions of strictly dominated actions ends at the same restriction $R^\infty$.604\end{theorem}605 606\begin{proof}[Proof sketch]607Termination is finiteness. For confluence it suffices, by Newman's lemma, to check local confluence: if608$a_i$ and $b_j$ are each strictly dominated in $G|_R$, then $a_i$ is still strictly dominated after $b_j$ is609deleted. If $j\neq i$ the dominating mixture for $a_i$ still dominates on the smaller set of opponent610profiles. If $j=i$ and the mixture $\sigma_i$ dominating $a_i$ puts weight on $b_i$, replace that weight by611the mixture dominating $b_i$; since the game is finite, repeating the substitution a bounded number of times612yields a dominating mixture supported off $b_i$.613\end{proof}614 615For weak dominance confluence fails, and with it the claim to be a solution concept in the sense of616\cref{prin:invariance}: the output depends on the order of deletion, which is not part of the game.617 618\begin{example}[Weak dominance is order dependent]\label{ex:weakdom}