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

639\cref{thm:order-indep}.640\end{theorem}641 642The coincidence rests on a separation argument: an action is a best response to no (possibly correlated)643conjecture exactly when a mixture strictly dominates it \cite{Pea84}. The first two claims are the644Knaster--Tarski theorem on the finite lattice of product subsets. The elements of $\nu\Phi$ are the645\term{rationalizable} actions, and the fixed-point description gives a proof principle:646 647\begin{quote}648\emph{Coinduction.} To show that $a_i$ is rationalizable, exhibit a product set $R\ni a_i$ with $R\subseteq\Phi(R)$.649\end{quote}650 651\noindent Such an $R$ is a set of actions each justified by conjectures supported inside $R$---a closed circle652of reasons. Rationalizability is therefore not the outcome of a deletion procedure that happens to converge;653it is a \emph{coinductive} predicate, the largest self-justifying set, and the procedure is the standard654way of computing a greatest fixed point from above. The same pattern---greatest fixed point of a monotone655operator, proved by exhibiting a post-fixed point---returns as self-generation in repeated games656(\cref{ch:repetition}) and as common knowledge (\cref{ch:knowledge}).657 658\section{Nash equilibrium}659 660\begin{definition}\label{def:nash}661For a game $G$ let $\BR\colon A\to\Pow(A)$ be the \term{best-response correspondence},662$\BR(a)=\prod_i\argmax u_i(-,a_{-i})$. A profile $a$ is a (pure) \term{Nash equilibrium} if $a\in\BR(a)$. Thus663\[ \NE(G)=\Fix(\BR), \]664the pullback of the graph of $\BR$ along the diagonal $A\to A\times A$.665\end{definition}666 667In the language of \cref{def:decision}: each player is a selection function $\varepsilon_i$; a profile $a$668supplies each player with the context $k_i=u_i(-,a_{-i})$; and $a$ is an equilibrium when each $a_i$ is669selected in the context that the others' choices create, $a_i\in\varepsilon_i(u_i(-,a_{-i}))$. Nothing in670this formulation uses maximization, and replacing $\argmax$ by other selection functions yields the671\emph{selection equilibria} of \cite{HOSWZ17}.672 673\begin{example}[Three small games]\label{ex:three}674\[675\begin{array}{c|cc}676 & C & D\\\hline677C & 2,2 & 0,3\\678D & 3,0 & 1,1679\end{array}680\qquad681\begin{array}{c|cc}682 & O & F\\\hline683O & 2,1 & 0,0\\684F & 0,0 & 1,2685\end{array}686\qquad687\begin{array}{c|cc}688 & a & b\\\hline689a & 2,2 & 0,0\\690b & 0,0 & 1,1691\end{array}692\]693The first is the Prisoner's Dilemma: $\NE=\{(D,D)\}$, found already by dominance. The second is a694\emph{Battle of the Sexes}: no action is dominated, every action is rationalizable, and695$\NE=\{(O,O),(F,F)\}$ in pure strategies. The third is a \emph{ranked coordination} game with696$\NE=\{(a,a),(b,b)\}$. Both of the latter have a third equilibrium in mixed strategies (\cref{ch:mixing}).697\end{example}698 699Rationalizability asks only that each action be justified by \emph{some} conjecture consistent with common700knowledge of rationality; equilibrium asks in addition that conjectures be \emph{correct}. The second701requirement is not a consequence of rationality, and the examples show its cost: where dominance gives702nothing, equilibrium gives several answers. The rest of this chapter is about what, if anything, the game703itself says about choosing among them.704 705\section{Symmetry and focal points}\label{sec:symmetry}706 707Let $G$ be a game. By \cref{lem:identity} the loops at $G$ in $\NFG_u$ are the automorphisms: relabellings708$(\nu,\alpha)$ of players and actions preserving payoffs. $\Aut(G)$ acts on profiles, and since it preserves709best responses it acts on $\NE(G)$ and on the mixed equilibria.710 711\begin{proposition}[Equivariance]\label{prop:equivariance}712\Sob Let $\mathcal{T}$ be a type of games and $s\colon\prod_{G:\mathcal{T}}\Sigma(G)$ a single-valued solution: a713function assigning to each game one (mixed) profile. Then for every $G$ the profile $s(G)$ is fixed by714every automorphism of $G$ in $\mathcal{T}$.715\end{proposition}716 717\begin{proof}718An automorphism is a path $p\colon G=G$. Dependent functions commute with transport: $p_*\,s(G)=s(G)$.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 is